CoChat
Sign Up
PreprintCited by 6Topic ModelingAI-based Problem Solving and PlanningNatural Language Processing Techniques

On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks

Open access
Stechly, Kaya, Valmeekam, Karthik, Kambhampati, Subbarao·2024·arXiv
DOI 10.48550/arxiv.2402.08115arXiv 2402.08115
Open this paper in CoChat — free accountOpen PDF

Abstract

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--ranging from multiplication to simple planning--there persists a wide spread belief that LLMs can self-critique and improve their own solutions in an iterative fashion. This belief seemingly rests on the assumption that verification of correctness should be easier than generation--a rather classical argument from computational complexity--which should be irrelevant to LLMs to the extent that what they are doing is approximate retrieval. In this paper, we set out to systematically investigate the effectiveness of iterative prompting in the context of reasoning and planning. We present a principled empirical study of the performance of GPT-4 in three domains: Game of 24, Graph Coloring, and STRIPS planning. We experiment both with the model critiquing its own answers and with an external correct reasoner verifying proposed solutions. In each case, we analyze whether the content of criticisms actually affects bottom line performance, and whether we can ablate elements of the augmented system without losing performance. We observe significant performance collapse with self-critique and significant performance gains with sound external verification. We also note that merely re-prompting with a sound verifier maintains most of the benefits of more involved setups.

AI snapshot

Written from the paper’s full text.

TL;DR

This paper systematically tests whether GPT-4 can iteratively self-critique and improve its answers on formal reasoning and planning tasks. It finds that LLM self-verification often degrades performance, while replacing the LLM verifier with a sound external verifier yields large gains—most of which can be retained by simply resampling guesses until a sound verifier accepts one.

Key findings

  • Self-critique (LLM+LLM) worsened performance in three of four domains versus standard prompting: Game of 24 5% → 3%, Graph Coloring 16% → 2%, Mystery Blocksworld 4% → 0%; Blocksworld improved modestly from 40% → 55%, but remained far below sound-verifier setups.
  • Sound external verification produced large gains: Game of 24 36–38%, Graph Coloring 34–38%, Blocksworld 60–87%, and Mystery Blocksworld 6–10%, depending on feedback level.
  • LLM-as-verifier had high false-negative rates in several domains: Graph Coloring 95.8% (113/118), Mystery Blocksworld 97.09% (100/103), Game of 24 20.7% (213/1029), and Blocksworld 15.48% (24/155).
  • Feedback content mattered little: binary, first-error, and all-error feedback gave similar results, and sampling with a sound verifier but no critique retained most gains (e.g., Game of 24 28% at k=15 and 42% at k=25; Graph Coloring 40% at k=15 and 44% at k=25).

Methods

  • Empirical study of GPT-4 on three formal domains: Game of 24, Graph Coloring, and STRIPS planning (Blocksworld and Mystery Blocksworld), with 100 instances per domain.
  • Iterative prompting architecture: the LLM generates a solution, then either the same LLM or a sound verifier critiques it; feedback is appended to a backprompt and the cycle repeats up to a timeout (15 rounds in main experiments).
  • Comparisons include LLM+LLM self-critique, LLM+sound verifier with binary/first-error/all-error feedback, sampling k=15 and k=25 without critique, self-consistency k=15, and separate verification/critique-generation experiments with chain-of-thought prompts.

Limitations

  • The paper does not include a dedicated limitations section. It states that it restricts focus to fully specified, formally verifiable problems and argues these are fundamental, though it acknowledges they may seem narrow compared with commonsense or language-based benchmarks.
  • Evident from the text: results are based on GPT-4 only, 100 instances per domain, and a 15-round timeout; the approach assumes access to a sound external verifier, which may not be available for many real-world tasks.
  • Evident from the text: the domains are formal reasoning/planning puzzles, so findings may not generalize to informal reasoning, creative tasks, or other LLMs; chain-of-thought verification improved some verification accuracy but at large token cost (e.g., 17× output tokens in Game of 24).

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

DataCite · 10.48550/arxiv.2402.08115

Cites

48 of 48 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

25 of 25 cited sources checked · 12 supported · 0 flagged · accuracy not yet measured

  • Premisecitation
    § 2 Related Work · p. 4

    There is compelling evidence that LLMs have memorized significant chunks of common benchmark sets.

    “there is compelling evidence that they have memorized significant chunks of common benchmark sets [34].”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [34] [34] Manley Roberts, Himanshu Thakur, Christine Herlihy, Colin White, and Samuel Dooley. Data contamination through the lens of time. arXiv preprint arXiv:2310.10628 , 2023. - source

      Section 5.1 (Pass Rate; page unavailable) calls the post-cutoff performance drop evidence of significant contamination and/or memorization of pre-cutoff Codeforces and Project Euler problems by GPT-3.5-Turbo and GPT-4. That supports concern about benchmark exposure, but it does not establish memorization specifically or show that significant chunks of common benchmark sets were memorized. (LLM, conf=0.86)

      Experimental — accuracy not yet measured
  • Interpretationreasoning
    § A.2 On Tree of Thoughts · p. 15

    The remaining difference is likely due to ToT implementing a classical breadth-first search algorithm, only prompting the LLM to generate intermediate steps and heuristic evaluations rather than full solutions and reflections.

    “The remaining difference is likely due to the fact that ToT implements a classical breadth-first search algorithm, only prompting the LLM to generate (much easier) intermediate steps and heuristic evaluations rather than full solutions and reflections.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source

      Section 3 describes generating intermediate thoughts, evaluating partial solutions, and using breadth-first search (Algorithm 1), which supports much of the description. But it also presents depth-first search (Algorithm 2), used for mini crosswords in Section 4.3, so ToT does not exclusively implement breadth-first search. Algorithm 1 also generates a final output; the paper does not establish that ToT only prompts for intermediate steps and evaluations rather than full solutions and reflections. (LLM, conf=0.88)

      Experimental — accuracy not yet measured
  • Interpretationown data
    § A.2 On Tree of Thoughts · p. 15

    The apparent contradiction is mainly because the self-verification setting presented in the main text is not directly comparable to that of [52].

    “However, this is mainly because the self-verification setting presented in the main text of this paper is not directly comparable to that of [52].”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source

      The cited paper’s “State evaluator” section describes how Tree of Thoughts uses an LM to assess partial solutions, and its “Self-reflection” section compares that approach with other methods. Neither section addresses the citing paper’s self-verification setting or says that the two settings are not directly comparable. I searched for self-verification, comparability, and the proposed explanation for the apparent contradiction. (LLM, conf=0.72)

      Experimental — accuracy not yet measured
  • Interpretationreasoning
    § A.2 On Tree of Thoughts · p. 15

    By reducing compositionality and offloading it to a proven classical algorithm, ToT sidesteps some of the major hurdles to LLM reasoning.

    “By reducing compositionality and offloading it to a proven classical algorithm, ToT sidesteps some of the major hurdles to LLM reasoning.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source
  • Findingown data
    § 5.2 Critique consideration · p. 9

    The self-consistency baseline, selecting the most common answer from the 15 generated ones, shows no improvement over standard prompting.

    “This baseline is listed under 'S.C.” and shows no improvement over standard prompting.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [46] [46] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171 , 2022. - source
  • May combine two claims. 18
  • Classified as probably not a substantial claim. 13

  • May combine two claims.

    Premisecitation
    § 2 Related Work · p. 4

    Many benchmark sets do not allow for arbitrary generation of novel questions, or draw data from publicly available sources that LLM trainers have access to.

    “Many benchmark sets do not allow for arbitrary generation of novel questions, or worse, draw data from publicly available sources-the same sources LLM trainers have access to [51, 39].”
    Quote in the paperSubstantial claim2 of 2 sources checked
    • cites [51] [51] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing , pages 2369-2380, 2018. - source

      The Introduction and “KB-based multi-hop datasets” section say that fixed knowledge-base schemas limit the diversity of questions, supporting the point about restrictions on novel questions. The Data Collection section says HotpotQA uses Wikipedia, but the paper does not say that LLM trainers have access to those sources. (LLM, conf=0.87)

      Experimental — accuracy not yet measured
    • cites [39] [39] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research , 2023. - source

      Section 2.3.1 says many BIG-bench tasks use text available on the internet, making indirect training-data leakage possible. Section 2.1 says about 80% of BIG-bench tasks use fixed lists of inputs and targets, which supports the concern about generating novel questions. The paper does not establish that many benchmark sets generally lack that capability. (LLM, conf=0.82)

      Experimental — accuracy not yet measured

  • Classified as probably not a substantial claim.

    Premisereasoning
    § Abstract · p. 1

    The belief that LLMs can self-critique and improve their own solutions in an iterative fashion rests on the assumption that verification of correctness should be easier than generation.

    “This belief seemingly rests on the assumption that verification of correctness should be easier than generation-a rather classical argument from computational complexity”
    Quote in the paperSubstantial claim5 of 5 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source

      The Self-reflection section describes LLMs assessing their own predictions, and the State evaluator section describes using those assessments to guide further search (page numbers unavailable). These passages support the self-critique aspect, but neither states that verifying correctness is easier than generating a solution nor gives a computational-complexity argument for that assumption. (LLM, conf=0.82)

      Experimental — accuracy not yet measured
    • cites [37] [37] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik R Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source

      Section 3 (p. 4) describes agents improving through iterative trial, self-reflection, and feedback. The Introduction says self-evaluation can provide that feedback but also calls generating useful reflective feedback challenging; it does not say the approach rests on verification being easier than generation or invoke a computational-complexity argument. (LLM, conf=0.82)

      Experimental — accuracy not yet measured
    • cites [50] [50] Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao. Large language models are better reasoners with self-verification. In Findings of the Association for Computational Linguistics: EMNLP 2023 , pages 2550-2575, 2023. - source

      The paper’s analysis of verification accuracy reports that selecting a correct answer from candidates outperformed standalone chain-of-thought reasoning on six datasets. That supports a limited comparison between verification and generation, but the paper does not state that verification is generally easier than generation or ground its method in a computational-complexity argument. Its method reranks candidate answers rather than iteratively revising a solution. (LLM, conf=0.78)

      Experimental — accuracy not yet measured
    • cites [5] [5] Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXiv:2304.05128 , 2023. - source

      The Abstract and “Self-debugging with explanation” section support the premise that LLMs can iteratively identify and correct errors in their own code. They do not say that this ability rests on verification being easier than generation, or invoke a computational-complexity argument; searches for that comparison found no supporting passage. (LLM, conf=0.82)

      Experimental — accuracy not yet measured
    • cites [29] [29] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651 , 2023. - source

      The Abstract and Refine Feedback section describe an LLM using feedback on its own output to improve it iteratively. They do not say this approach rests on verification of correctness being easier than generation, or invoke computational complexity as its rationale. The Results section also notes that identifying errors in math reasoning can be difficult. (LLM, conf=0.84)

      Experimental — accuracy not yet measured

  • May combine two claims.

    Premisecitation
    § 2 Related Work · p. 4

    Some benchmarks used in evaluations of self-verification (e.g., HotPotQA, GSM-8k) are easy, with SoTA LLM performance already high, making them less informative about refinement procedures.

    “Some of the benchmarks (e.g. HotPotQA [18], GSM-8k [29], ) used in evaluations of self-verification are easy-that is, SoTA LLM performance is already high-and are therefore much less informative about the effects of the refinement procedure.”
    Quote in the paperSubstantial claim2 of 2 sources checked
    • cites [18] [18] Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet. arXiv preprint arXiv:2310.01798 , 2023. - source

      The Experimental Setup (p. 3) confirms that the paper evaluates self-correction on GSM8K and HotpotQA. Table 3 in Results (p. 4) shows high baseline GPT-4 accuracy on GSM8K (95.5%), but 49.0% on HotpotQA. The paper does not say that both benchmarks are easy or that high performance makes them less informative about refinement; its stated concern about HotpotQA is the small sample size (p. 5). (LLM, conf=0.88)

      Experimental — accuracy not yet measured
    • cites [29] [29] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651 , 2023. - source

      Appendix O identifies GSM-8k as a SELF-REFINE evaluation benchmark, and Table 1 reports high GPT-4 baseline accuracy (92.9%) with only a 0.2-point gain after refinement. But Section 3.3 attributes the modest math gains to difficulty detecting errors, not to the benchmark being easy or less informative; the cited passages also do not evaluate HotPotQA. (LLM, conf=0.83)

      Experimental — accuracy not yet measured

  • May combine two claims.

    Premisereasoning
    § 2 Related Work · p. 4

    A number of tasks that LLMs are evaluated on are problems without a well-defined ground truth, and this makes conclusions much harder to draw.

    “A number of tasks that LLMs are evaluated on (e.g. writing prompts [52], constrained text generation [28], toxicity control [49, 14] , etc.) are problems without a well-defined ground truth.”
    • Also stated in: § 2 Related Work · p. 4 · plain
      “This makes conclusions much harder to draw.”
    Quote in the paperNot a substantial claim4 of 4 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source
    • cites [28] [28] Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. Commongen: A constrained text generation challenge for generative commonsense reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2020 , pages 1823-1840, 2020. - source
    • cites [49] [49] Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. In The Eleventh International Conference on Learning Representations , 2022. - source
    • cites [14] [14] Zhibin Gou, Zhihong Shao, Yeyun Gong, Yelong Shen, Yujiu Yang, Nan Duan, and Weizhu Chen. Critic: Large language models can self-correct with tool-interactive critiquing. arXiv preprint arXiv:2305.11738 , 2023. - source

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 6 Conclusion · p. 9

    Previous work has proposed the general LLM-Modulo framework, which the current work fits into.

    “previous work has proposed the general LLM-Modulo framework [23] which the current work fits into.”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [23] [23] Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Kaya Stechly, Mudit Verma, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. Llms can't plan, but can help planning in llm-modulo frameworks. arXiv preprint arXiv:2402.01817 , 2024. - source

  • Classified as probably not a substantial claim.

    Study design and conductcitation
    § A.5.1 Accuracy of Planning Critique · p. 31

    The evaluation of binary verification and critique compared LLM outputs to ground truth provided by VAL [17].

    “We evaluate the binary verification and the critique by comparing it to the ground truth provided by V AL [17].”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [17] [17] Richard Howey, Derek Long, and Maria Fox. VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL. In 16th IEEE International Conference on Tools with Artificial Intelligence , pages 294-301. IEEE, 2004. - source

  • May combine two claims.

    Premisecitation
    § A.2 On Tree of Thoughts · p. 15

    Per problem, 100 CoT prompts costs $0.47, but running Tree of Thoughts averages $0.74, cost-equivalent to about 150 CoT prompts.

    “Per problem, 100 CoT prompts costs $0.47, but running Tree of Thoughts (ToT) averages $0.74-cost-equivalent to about 150 CoT prompts.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source

      Table 7 (Cost analysis on Game of 24; page unavailable) reports $0.47 per case for the best of 100 CoT trials and $0.74 for ToT. The roughly 150-trial equivalence follows from those figures, but the citing sentence omits that they apply to Game of 24, not ToT problems generally; Table 8 reports a different ToT cost for Creative Writing. (LLM, conf=0.88)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationown data
    § A.2 On Tree of Thoughts · p. 15

    The paper's results on the Game of 24 setting seem to contradict the results shown in [52].

    “Our results on the Game of 24 setting seem to contradict the results shown in [52].”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation
    § A.1 Prompt Variation and Chain of Thought · p. 14

    In reasoning domains like Blocksworld, previous work has shown that CoT fails to generalize and is not particularly robust.

    “In particular, in reasoning domains like Blocksworld, previous work has shown that they fail to generalize and are not particularly robust [40].”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [40] [40] Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. Chain of thoughtlessness: An analysis of cot in planning. arXiv preprint arXiv:2405.04776 , 2024. - source

  • May combine two claims.

    Findingown data
    § A.2 On Tree of Thoughts · p. 15

    On the exact same test set, extending experiments to 150 direct non-CoT queries with a sound verifier reaches 70%, comparable to ToT's reported 74%.

    “On the exact same test set, we extend our experiments to 150 (direct, non-CoT) queries with a sound verifier, and we reach 70%, comparable to ToT's reported 74%.”
    Quote in the paperSubstantial claim1 of 1 sources checked
    • cites [52] [52] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023. - source

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 6 Conclusion · p. 9

    Similar architectures have already shown some success.

    “Similar architectures have already shown some success [35]”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [35] [35] Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, MPawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature , pages 1-3, 2023. - source

  • May combine two claims.

    Findingown data
    § 5.1 Critique generation · p. 8

    In Graph Coloring, the LLM's critiques of proposed solutions are riddled with non-existent edges and include many spurious claims about the colors of vertices, often missing the violated constraint in favor of them.

    “In Graph Coloring, the LLM's critiques of proposed solutions are riddled with non-existent edges and include many spurious claims about the colors of vertices, often missing the violated constraint in favor of them.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5 Examining Self-Verification · p. 7

    In Blocksworld, the LLM+LLM self-critique system shows a modest improvement over standard prompting, though still significantly worse than using a sound verifier.

    “In Blocksworld, we even see a modest improvement, though that improvement is still significantly worse than having a sound verifier.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5 Examining Self-Verification · p. 7

    When using a sound verifier, performance is much higher in all sound critique cases but still falls short of 100%.

    “As shown in Table 1, performance is much higher in all sound critique cases, though it still falls short of 100%.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 5.1 Critique generation · p. 8

    In Game of 24, when restricted to equations guaranteed to equal 24, the LLM labels 79.1% of them as correct, but evaluates 81.6% of them to 24.

    “In fact, when we restrict ourselves to only looking at verification of equations that are guaranteed to equal 24, and therefore must be correct, it labels 79 . 1% of them as correct, but evaluates 81 . 6% of them to 24.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 6 Conclusion · p. 9

    Across the hard reasoning domains evaluated, LLMs did poorly in all three roles, with stacked errors often making the LLM self-critiquing loop perform worse than just having the LLM guess the solution up front.

    “Across the hard reasoning domains we evaluated, LLMs did poorly in all three roles, with the stacked errors often making the LLM self-critiquing loop perform worse than just having the LLM guesse the solution up front.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.1 Prompt Variation and Chain of Thought · p. 14

    In Game of 24, CoT verification leads to a 17-fold increase in necessary output tokens, which more than doubles the cost of verification.

    “Furthermore, these improvements come with a large cost increase: in G24, this leads to a 17 times increase in necessary output tokens, which more than doubles the cost of verification.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.4.1 Hallucinations in Graph Coloring Critique · p. 19

    The model never hallucinates new vertex names; it only misstates the colors of vertices that are in the graph.

    “Note that it never hallucinates new vertex names , only that vertices which are in graph have colors differing from reality.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingreasoning
    § A.4.1 Hallucinations in Graph Coloring Critique · p. 18

    In graph coloring critique, hallucinations decrease proportionally as the error rate of the domain increases; when there are more incorrect edges, the model is more likely to point to one of them.

    “Note that, proportionally, hallucinations decrease when the error rate of the domain increases. That is to say, when there are more incorrect edges, the model is more likely to point to one of them.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § A.1 Prompt Variation and Chain of Thought · p. 14

    In Game of 24, CoT increases verification accuracy from 87% to 99% and shrinks the difference between sound verifier and LLM-verifier in the full pipeline, but a 6 percentage point gap still remains.

    “In G24, CoT increases verification accuracy from 87% to 99%, and does shrink the difference between sound verifier and LLM-verifier in the full pipeline, but a 6 percentage point gap still remains!”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.4.1 Hallucinations in Graph Coloring Critique · p. 19

    The model sometimes loses track of the question and reverses it, explicitly claiming that two same-colored vertices violate the conditions because they are not connected.

    “At times the model lost track of the question being asked and reversed it, explicitly claiming that two same-colored vertices violate the conditions because they aren't connected;”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Findingnone given
    § [STATEMENT] · p. 40

    The GPT-4 Verifier response shown in the example is incorrect.

    “GPT-4 Verifier Incorrect Response”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § 2 Related Work · p. 4

    Many benchmark sets over-constrain the solution space, usually by putting questions into multiple choice format, which trivializes refinement and makes conclusions unlikely to generalize.

    “Additionally, many such sets over-constrain the solution space, usually by putting the question into multiple choice format. Not only does this make valuable and interesting critique hard to produce and evaluate, but it trivializes refinement: even a very simple agent can solve an n -choice problem with n -1 critiques-just don't repeat the same answer. Conclusions drawn over reduced problem spaces”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S2 (checkable), S4 (based).

    Interpretationnone given
    § 2 Related Work · p. 3

    Formal tasks are fundamental for evaluating reasoning because any other reasoning tasks must include components that test these same capabilities-otherwise they are merely testing recall.

    “we argue that they are fundamental, as any other reasoning tasks must include components that test these same capabilities-otherwise they are merely testing recall.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § 5.1 Critique generation · p. 8

    The LLM introduces errors in two places: verification, where it can pass over correct answers and accept wrong ones; and critique generation, where it can produce misleading feedback and bias future outputs away from the correct answer.

    “In other words, the LLM introduces errors in two places: verification, where it can pass over correct answers and accept wrong ones; and critique generation, where it can produce misleading feedback and bias future outputs away from the correct answer.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Interpretationreasoning
    § A.4.1 Hallucinations in Graph Coloring Critique · p. 18

    It is easier to guess one edge which is wrong when half of all the edges are miscolored, as is the case on average among randomly colored graphs.

    “Intuitively, this makes sense: it's easier to guess one edge which is wrong when half of all the edges are miscolored, as is the case on average among randomly colored graphs.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning
    § 6 Conclusion · p. 9

    The paper's results add depth to contemporaneous studies that focused on benchmarks that were too easy for LLMs to begin with, lacked clear ground truth, and did not account for test set memorization.

    “They also add depth to contemporaneous studies that focused on benchmarks that were too easy for LLMs to begin with, lacked clear ground truth, and didn't account for test set memorization.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationreasoning
    § 5.2 Critique consideration · p. 9

    Because prompts do not grow additively with iteration number, the token cost of these prompts is quadratically lower.

    “Note that, because prompts do not grow additively with iteration number, the token cost of these prompts is quadratically lower.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S2 (checkable).

    Interpretationown data
    § 5.2 Critique consideration · p. 9

    The LLM is primarily an idea generator.

    “We therefore see the LLM primarily as an idea generator.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S2 (checkable).

    Interpretationreasoning
    § 6 Conclusion · p. 9

    Failures of verification could potentially be very detrimental to a system's dependability, especially in domains where high reliability is paramount.

    “These failures of verification could potentially be very detrimental to a system's dependability, especially in domains where high reliability is paramount.”
    Quote in the paperNot a substantial claim
30 of 30

  • The paper relies on this without support.

    LLM results are brittle to the choice and phrasing of prompt.

    “LLM results are well-known to be brittle to choice and phrasing of prompt.”

  • The paper relies on this without support.

    The verifier used to generate the sound verifier backprompts is sound.

    “Backprompt Generated From Sound Verifier (First)”
    “Backprompt Generated From Sound Verifier (Full)”
2 of 2

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?

  • Uniformly refining all instances can cause over-refinement, where solutions that were already correct before refinement are flipped to incorrect, reducing overall performance.

    “Uniformly refining all instances can cause over-correction and reduce overall performance.”

    From MAgICoRe: Multi-Agent, Iterative, Coarse-to-Fine Refinement for Reasoning (2025) · cites this paper as Stechly et al., 2024

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Mystery-S false-negative numerator exceeds its denominator

    Major

    The stated 149 false negatives among 103 positive cases would be a 144.7% false-negative rate, not 96.1%.

    Reported 96.1 · recomputed 144.660194

  • Mystery-CoT false-negative numerator exceeds its denominator

    Major

    The stated 113 false negatives among 103 positive cases would be a 109.7% false-negative rate, not 72.8%.

    Reported 72.8 · recomputed 109.708738

  • Mystery-CoT false-positive percentage is miscalculated

    Minor

    Eleven false positives out of 397 cases is about 2.8%, rather than the reported 3.2%.

    Reported 3.2 · recomputed 2.770781

  • Mystery Blocksworld critique percentage does not match 59/100

    Minor

    Table A6 reports 59 correct critiques out of 100 random plans but labels this 100%; the fraction is 59%.

    Reported 100 · recomputed 59

  • Graph-coloring error-column total does not add up

    Minor

    The Coloring Errors entries of 187, 736, and 240, with zero in the other two rows, sum to 1163, not the reported total of 282.

    Reported 282 · recomputed 1163

  • Mystery-S false-positive percentage is miscalculated

    Minor

    Four false positives out of 397 cases is about 1.0%, rather than the reported 1.3%.

    Reported 1.3 · recomputed 1.007557

  • Mystery first-error-feedback accuracy differs between tables

    Minor

    Table A1 identifies its first-error-feedback column as the main-paper result, but gives 6% for Mystery; Table 1 gives 8% for Mystery Blocksworld under the same feedback scheme.

7 of 7

Cites

Flagged first, then by citations

Research works printed but not linked: 5

  1. [7][7] Joost CF de Winter. Can chatgpt pass high school exams on english language comprehension? International Journal of Artificial Intelligence in Education , pages 1-16, 2023. -
  2. [22][22] Subbarao Kambhampati. Can large language models reason and plan? Annals of the New York Academy of Sciences , 2024. -
  3. [24][24] Subbarao Kambhampati, Karthik Valmeekam, Matthew Marquez, and Lin Guan. On the role of large language models in planning. tutorial presented at the international conference on automated planning and scheduling (icaps), prague, July 2023. -
  4. [26][26] Gerd Kortemeyer. Could an artificial-intelligence agent pass an introductory physics course? Physical Review Physics Education Research , 19(1):010132, 2023. -
  5. [38][38] Tom Silver, Varun Hariprasad, Reece S Shuttleworth, Nishanth Kumar, Tomás Lozano-Pérez, and Leslie Pack Kaelbling. Pddl planning with pretrained large language models. In NeurIPS 2022 foundation models for decision making workshop , 2022. -

Cited by

Sorted by citations

Related

Authors
Stechly, K., Valmeekam, K., & Kambhampati, S.
Affiliations
Arizona State University (US)
ORCID
Kambhampati, Subbarao
Venue
arXiv
Publisher
arXiv
Published
2024
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2402.08115
arXiv
2402.08115
OpenAlex
W4391833261
Cited by
3
References
36
Citations by year
2026: 1 · 2025: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
Keywords
large language models, self-criticism, iterative prompting, verification, reasoning, planning, GPT-4, graph coloring

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.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-07.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-07.

Cited sources are checked by gpt-6-sol.

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