GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problems
Open accessAbstract
There has been considerable divergence of opinion on the reasoning abilities of Large Language Models (LLMs). While the initial optimism that reasoning might emerge automatically with scale has been tempered thanks to a slew of counterexamples, a wide spread belief in their iterative self-critique capabilities persists. In this paper, we set out to systematically investigate the effectiveness of iterative prompting of LLMs in the context of Graph Coloring, a canonical NP-complete reasoning problem that is related to propositional satisfiability as well as practical problems like scheduling and allocation. We present a principled empirical study of the performance of GPT4 in solving graph coloring instances or verifying the correctness of candidate colorings. In iterative modes, we experiment with the model critiquing its own answers and an external correct reasoner verifying proposed solutions. In both cases, we analyze whether the content of the criticisms actually affects bottom line performance. The study seems to indicate that (i) LLMs are bad at solving graph coloring instances (ii) they are no better at verifying a solution--and thus are not effective in iterative modes with LLMs critiquing LLM-generated solutions (iii) the correctness and content of the criticisms--whether by LLMs or external solvers--seems largely irrelevant to the performance of iterative prompting. We show that the observed increase in effectiveness is largely due to the correct solution being fortuitously present in the top-k completions of the prompt (and being recognized as such by an external verifier). Our results thus call into question claims about the self-critiquing capabilities of state of the art LLMs.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Recent work shows the inability of LLMs to self-verify their own reasoning.
“However, recent work shows the inability of LLMs to”
From MAgICoRe: Multi-Agent, Iterative, Coarse-to-Fine Refinement for Reasoning (2025) · cites this paper as Stechly et al., 2023
The Introduction and Conclusion report that LLMs were poor at verifying solutions and that self-critiquing did not improve results. The experiments concerned GPT-4 on graph-coloring problems, so they do not establish a general inability of LLMs to self-verify reasoning across tasks. (LLM, conf=0.84)
Experimental — accuracy not yet measuredRecent follow-up studies support the finding that self-correction in LLMs is unreliable and add further evidence.
“These studies corroborate the findings regarding the unreliability of self-correction in LLMs and provide additional insights.”
From CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing (2023) · cites this paper as Stechly et al., 2023
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 7
- Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and Fate: Limits of Transformers on Compositionality. 2023. Publisher: arXiv Version Number: 2.
- Takeshi Kojima, S. Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large Language Models are Zero-Shot Reasoners. ArXiv, May 2022.
- Zhan Ling, Yunhao Fang, Xuanlin Li, Zhiao Huang, Mingu Lee, Roland Memisevic, and Hao Su. Deductive verification of chain-of-thought reasoning. arXiv preprint arXiv:2306.03872, 2023. · arXiv
- Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach (4th Edition). Pearson, 2020.
- Tomohiro Sawada, Daniel Paleka, Alexander Havrilla, Pranav Tadepalli, Paula Vidas, Alexander Kranias, John J. Nay, Kshitij Gupta, and Aran Komatsuzaki. ARB: Advanced Reasoning Benchmark for Large Language Models. 2023. Publisher: arXiv Version Number: 2.
- Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language Agents with Verbal Reinforcement Learning, June 2023. arXiv:2303.11366 [cs]. · arXiv
- Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Large Language Models Still Can't Plan (A Benchmark for LLMs on Planning and Reasoning about Change), apr 2023. arXiv:2206.10498 [cs]. · arXiv
Cited by
Sorted by citations
ChatGPT: The End of Online Exam Integrity?
Susnjak, T. (2022) · arXiv · doi:10.48550/arxiv.2212.09292 · Cited by 370 · see citing works
“Perceptions that advanced LLMs exhibit limited reasoning abilities still prevail [31,32,49].”
Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. (2023) · arXiv · doi:10.48550/arxiv.2311.05232 · Cited by 2,516 · see citing works
“Although self-correction has shown promise for achieving faithful and accurate reasoning, especially in iterative settings, certain studies (Stechly et al., 2023; Huang et al., 2023a; Valmeekam et al., 2023) question the effectiveness of the self-correction mechanism, pointing out that LLMs still…”
Kamoi, R., Zhang, Y., Zhang, N., Han, J., & Zhang, R. (2024) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00713 · Cited by 82 · see citing works
CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing
Gou, Z., Shao, Z., Gong, Y., Shen, Y., Yang, Y., Duan, N., & Chen, W. (2023) · arXiv · doi:10.48550/arxiv.2305.11738 · Cited by 57 · see citing works
LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks
Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Saldyt, L., & Murthy, A. (2024) · arXiv · doi:10.48550/arxiv.2402.01817 · Cited by 11 · see citing works
“For exmaple, both Valmeekam et al. (2023c) and Stechly et al. (2023) describe and evaluate a backprompting interaction between an LLM and an external verifier.”
BackgroundResultSelf-citationConfidence v.s. Critique: A Decomposition of Self-Correction Capability for LLMs
Yang, Z., Zhang, Y., Wang, Y., Xu, Z., Lin, J., & Sui, Z. (2025) · Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2025.acl-long.203 · Cited by 5 · see citing works
MAgICoRe: Multi-Agent, Iterative, Coarse-to-Fine Refinement for Reasoning
Chen, J., Prasad, A., Saha, S., Stengel-Eskin, E., & Bansal, M. (2025) · Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2025.emnlp-main.1660 · Cited by 3 · see citing works
Rethinking Mixture-of-Agents: Is Mixing Different Large Language Models Beneficial?
Li, W., Lin, Y., Xia, M., & Jin, C. (2025) · arXiv · doi:10.48550/arxiv.2502.00674
“For example, Stechly et al. (2023), Valmeekam et al. (2023) Wang et al. (2024b) shows that a single model with carefully designed prompts can sometimes match the performance of agent discussions.”
- Authors
- Stechly, K., Marquez, M., & Kambhampati, S.
- Affiliations
- Arizona State University (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2023
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2310.12397
- OpenAlex
- W4387838288
- Cited by
- 11
- References
- 0
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 7 · 2023: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Constraint Satisfaction and Optimization
- Keywords
- GPT-4, iterative prompting, self-criticism, large language models, graph coloring, NP-complete problems, solution verification, propositional satisfiability, reasoning skills
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
