Source-linked AI summary
On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks
Kaya Stechly, Karthik Valmeekam, Subbarao Kambhampati
TL;DR
LLM reasoning research has produced conflicting evidence, while self-critique remains widely believed to improve generated solutions. This paper systematically evaluates GPT-4 self-verification and external verification on formal reasoning and planning tasks, finding that self-critique collapses performance whereas sound external verification yields gains that simple repeated prompting largely preserves.
Problem
The paper addresses limited systematic evidence about whether LLMs can reliably verify and improve their own reasoning solutions, especially on difficult formally verifiable tasks.
Method
The study evaluates GPT-4 iterative self-verification and external sound verification across Game of 24, Graph Coloring, and STRIPS planning, including ablations of critique and feedback.
Results
Across the evaluated domains, self-critique worsens performance, while external sound verification produces substantial gains that repeated base-prompt querying largely maintains.
Takeaways & Limitations
Reasoning systems should rely on externally sound verification signals rather than opaque self-critique and rich feedback alone.
Takeaways & Limitations
The evaluation focuses on three formally verifiable reasoning and planning domains, while many common tasks lack sufficient difficulty or well-defined ground truth.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper tests whether iterative self-critique improves LLM reasoning, challenging the assumption that verification is easier than generation. GPT-4 self-verification generally degrades performance, whereas sound external verification improves it and needs little feedback.
- Motivation: The study examines whether LLMs can iteratively critique and improve their own solutions on formal reasoning and planning tasks.Formal tasks provide machine-verifiable ground truth for both generation and criticism.
- Method: GPT-4’s self-verification system uses generated answers to create verification prompts, then feeds critique back through repeated solution cycles.The same model performs solution generation, verification, and critique generation.
- Results: Across almost all domains, increasing the number of self-correction backprompts consistently worsens output quality.False negatives cause the verifier to reject valid solutions often enough to reduce overall performance.
- Results: An external sound verifier produces substantial gains across all domains, regardless of how much feedback the LLM receives.The comparison suggests verifier soundness matters more than feedback richness.
- Results: Repeatedly querying the LLM with the same base prompt until sound verification maintains most, if not all, gains from more complex setups.This ablation removes critique and history of prior guesses while retaining the verification signal.
- Implication: The results support using externally verified LLM-Modulo systems rather than relying on opaque self-critique for reasoning tasks.The paper argues that iterative prompting benefits can be misattributed to rich self-generated feedback.
2 Related Work
Prior work reports optimistic self-critique results, but the paper argues that stronger evaluation requires difficult, formally verifiable domains and systematic ablations. It positions its study as addressing gaps in benchmark coverage, task difficulty, and evaluation validity.
- Prior findings: Research on LLM reasoning initially appeared promising but later found inconsistent and brittle performance across planning, logic, arithmetic, and related domains.The paper situates self-critique research within broader negative findings about LLM reasoning.
- Self-critique: Self-critique methods repeatedly query an LLM with its prior response and instructions to critique or improve it, based on the intuition that verification differs from generation.The process is typically looped until a stopping condition.
- Prior claims: Prior claims attribute self-reflection gains to feedback that provides a concrete direction for improving mistakes without human feedback.The paper presents these claims as strong but potentially broader than their original domains and prompts justify.
- Counterevidence: Other systematic studies report brittle or reduced gains, including cases where self-critique performs worse than sound verification.Some improvements can be reproduced by adding missing domain-general information without self-critique.
- Novelty: This work extends prior studies by thoroughly ablating self-critique, testing up to 15 prompting rounds, and evaluating three formally verifiable reasoning domains.The authors present these domains as broader tests of reasoning and self-correction capability.
- Evaluation scope: The paper restricts its focus to fully specified, formally verifiable problems to make claims about reasoning more concrete and falsifiable.This addresses ambiguity caused by shifting definitions of reasoning.
- Evaluation gaps: Common evaluation domains suffer from test-set memorization, insufficient difficulty, and missing ground truth.These weaknesses complicate conclusions about reasoning and self-critique abilities.
3 Background On Test Tasks
The paper evaluates GPT-4 self-critique on three formally verifiable reasoning tasks selected for flexible instance generation, easy verification, and large solution spaces. The tasks are Game of 24, graph coloring, and STRIPS planning, each paired with a sound verification procedure.
- Task selection: GPT-4 is evaluated on Game of 24, graph coloring, and STRIPS planning because these tasks support arbitrary instance generation and formal verification.The authors also argue that these properties reduce the likelihood of benchmark memorization and approximate retrieval.
- Task selection: The selected problems have many potential solutions, so removing a few prior guesses does not trivialize subsequent attempts.This distinguishes them from multiple-choice tasks, where exhaustive guessing over a small option set can solve the problem.
- 3.1 Game of 24: Game of 24 requires combining four numbers with parentheses and basic arithmetic operations to produce an expression equal to 24.The study uses instances 901–1000 for generation and instances 1–1000 for verification and critique evaluation.
- 3.2 Graph Coloring: Graph coloring assigns one of n colors to each vertex while ensuring that edge-connected vertices receive different colors.The test set contains 100 small planar graphs generated with an Erdős–Rényi variant and supplied chromatic numbers.
- Verification: Sound verification checks every graph edge for equal endpoint colors and validates STRIPS plans by simulating actions, checking preconditions, and testing goal satisfaction.The graph verifier is a simple Python loop, while VAL performs external critique for PDDL plans.
4 Methodology
The methodology uses a modular multi-round prompting loop that preserves prior solutions and feedback while varying the roles of the guesser, verifier, and critique generator. The study compares the full self-critique system with configurations using sound external verification and progressively less feedback.
- Prompting framework: The prompting framework includes domain-specific components and gives the LLM the complete history of proposed solutions and received feedback.This design supports controlled ablations of the self-critique architecture.
- Prompting framework: Each round translates a formal instance into a prompt, queries the LLM for a solution, and sends that response to a separate domain-specific critique query.A claimed-correct response ends the loop; otherwise, extracted critique is appended to the prompt for another round.
- Ablation design: The LLM plays three roles: answer guesser, binary verifier, and critique generator.The experiments vary these roles by changing or removing one or more components.
- Ablation design: The study first measures the complete system and its false-positive and false-negative verification rates, then substitutes a provably sound verifier with rich correct feedback.The researchers subsequently reduce and eliminate the information supplied to the model to isolate which components matter.
- Critique evaluation: LLM-generated critiques are evaluated on subdomains by comparing parsed domain-specific feedback with the output of the sound verifier.Sound verifiers provide task-specific feedback, including arithmetic errors, coloring conflicts, precondition violations, and failure to reach a goal.
5 Examining Self-Verification
Across the evaluated reasoning domains, self-verification often reduces performance because LLM verifiers reject correct answers and generate misleading critiques. Sound external verification improves performance, while much of the gain remains when critique is removed and the model is repeatedly sampled.
- Self-verification performance: Self-correction consistently degrades output quality as backprompts increase, contrary to the expectation that verification would at least preserve baseline performance.The evaluation covers 100 instances in each domain.
- Self-verification performance: Significant false-negative rates cause the self-verification loop to reject valid solutions and continue with worse generations until timeout.The LLM verifier’s accuracy varies by domain; the remaining domains have very high false-negative rates.
- External verification: Sound verification produces much higher performance across all domains, although results remain below 100% because some instances are not generated correctly within 15 rounds.With a sound verifier, correctly generated answers are accepted, so timeout of the answer generator is the remaining source of inaccuracy.
- Critique generation: The LLM’s verification and critique generation both introduce errors: it can reject correct answers, accept wrong ones, and provide misleading feedback that biases later outputs.Examples include mis-evaluating guaranteed Game of 24 solutions, inventing graph-coloring errors, and hallucinating planning preconditions.
- Critique consideration: Varying critique detail produces little performance difference, and increasing feedback can reduce performance in two domains.The tested feedback levels include binary, first-error, and all-errors feedback, with no third level for Game of 24.
- Critique consideration: Repeatedly sampling with an unchanged prompt and a sound verifier retains comparable gains to feedback conditions, while self-consistency shows no improvement over standard prompting.Because prompts do not grow with iteration, the sampling setup also has quadratically lower token cost.
6 Conclusion
The paper finds that GPT-4 self-critique performs poorly across three hard reasoning and planning tasks, whereas repeated generation paired with sound verification is a more reliable system design. Its proposal is to use LLMs as idea generators within systems that provide a signal for when a solution is good enough.
- Conclusion: Across three reasoning and planning tasks, LLMs performed poorly as verifiers, critique generators, and critique considerers, with compounded errors often underperforming an initial guess.The conclusion separates self-critique into verification, critique generation, and critique consideration.
- Conclusion: The findings contradict optimistic claims about LLM self-critique and address limitations in contemporaneous evaluations involving easy benchmarks, unclear ground truth, or test-set memorization.This comparison is framed as adding depth to prior studies rather than resolving all questions about reasoning.
- Conclusion: The proposed architecture lets LLMs generate multiple guesses while external sound verifiers signal when a solution is good enough.Examples include VAL for STRIPS planning, expression simplification for Game of 24, and constraint checking for constraint-satisfaction problems.
A.1 Prompt Variation and Chain of Thought
Prompt and chain-of-thought variations improve verification in some cases, but gains remain incomplete, domain-dependent, and costly. In Game of 24, CoT raises verification accuracy while leaving a substantial pipeline gap and increasing token use.
- Cost and performance: 17 times more output tokens are required for CoT verification in G24, more than doubling verification cost.The reported cost increase accompanies improved verification performance.
- Cost and performance: 87% to 99% verification accuracy in G24 with CoT still leaves a 6 percentage point gap from the sound-verifier pipeline.The improvement does not reach sound-verifier performance.
- Prompt and domain variation: Chain-of-thought effectiveness varies across domains and is not particularly robust in reasoning domains such as Blocksworld.Prior work cited in the passage reports failure to generalize in Blocksworld.
- Prompt and domain variation: Performance improves in some, though not all, cases under prompt variation and CoT verification.The appendix reports heterogeneous effects across cases.
- Evaluation setup: Table A1 compares accuracy across prompting schemes over 100 instances per domain, including standard prompting, LLM+LLM, CoT verification, and sound first-error feedback.Table A2 separately reports false-positive and false-negative verification rates across prompt variants.
A.2 On Tree of Thoughts
The Tree of Thoughts comparison suggests that sound verification can approach ToT performance with enough direct queries, while ToT gains from reducing compositional demands through classical search.
- Comparison with Tree of Thoughts: 70% accuracy is reached with 150 direct non-CoT queries and a sound verifier, compared with ToT’s reported 74% on the same test set.The sound-verifier result uses more queries than the paper’s standard 15-query experiments.
- Comparison with Tree of Thoughts: The paper reports that its external-verifier results use only 15 LLM queries, whereas the comparison source’s query count is unclear.The cited cost breakdown gives reference points for 100 CoT prompts and ToT at roughly 150 CoT prompts.
- Comparison with Tree of Thoughts: ToT reduces compositionality by having the LLM generate intermediate steps and heuristic evaluations rather than full solutions and reflections.The passage characterizes this as a classical breadth-first search approach.
A.3.1 Evaluation vs. Binary Verification for Game of 24
The Game of 24 analysis separates evaluating an expression’s numerical result from making a binary correctness judgment. It tests both abilities across several proposed-expression types and controlled no-information cases.
- Experimental design: Five proposed-expression types are evaluated: correct, ablated operation, ablated number, random, and LLM-generated expressions.The experiment also includes correct and random no-information cases.
- Evaluation versus verification: The experiment asks GPT-4 both to evaluate each expression and to classify whether it equals 24.This directly compares numerical evaluation with binary verification.
- Experimental design: 1,000 expressions are generated for each type except the LLM case, which contains 100 expressions.The LLM sample is restricted to instances 901–1000.
A.3.2 Prompts
The appendix presents the prompts used for Game of 24 generation and verification, including standard, evaluation-first, and chain-of-thought verification formats. These prompts constrain arithmetic, formatting, and correctness judgments.
- Prompt variants: The appendix labels separate formats for standard prompting, verification, and chain-of-thought verification.The prompt variants are presented as named prompt sections.
- Task and answer prompts: The Game of 24 task requires using the given numbers and basic arithmetic operations to obtain 24.The raw task prompt includes an example instance with numbers 1, 1, 4, and 6.
- Verification prompts: The verification prompt asks whether an expression uses only the given numbers and evaluates to 24.It requests JSON output containing an evaluation and a correctness boolean.
- Self-critique prompts: The self-critique prompt requests step-by-step checking of number usage, multiplicities, and the expression’s value before returning structured feedback.The requested output includes feedback and a Boolean correctness field.
A.3.3 Backprompts
The backprompts repeatedly ask GPT-4 to retry a Game of 24 solution after verifier feedback. They include both pass/fail feedback and more detailed critiques of malformed or incorrect expressions.
- Sound-verifier backprompts: Backprompts generated from a sound verifier ask the model to provide a correct expression again using the specified numbers.The prompts retain the required output format, including writing the answer first and ending with [ANSWER END].
- Sound-verifier backprompts: Some backprompts provide only a generic failure message before requesting another attempt.The feedback is followed by an instruction to try again with the task constraints still in place.
- Critique content: Other backprompts identify specific formatting or correctness problems, including malformed expressions and an allegedly correct replacement expression.The examples distinguish malformed syntax from an incorrect expression and sometimes supply a proposed correction.
A.3.4 Complete Example of Iterative Prompt Sequence
The complete iterative sequence shows a sound verifier generating successive Game of 24 backprompts until successful completion. The sequence includes feedback on incorrect values, malformed expressions, and number-use constraints.
- Sequence overview: The sequence is described as seven sound-verifier-generated backprompts that stop when the task is successfully completed.Its title explicitly frames the process as iterative and completion-based.
- Constraint checking: The verifier also checks whether the proposed expression uses the required numbers and format before requesting another answer.The prompts retain the input numbers and require the answer to end with [ANSWER END].
- Malformed attempts: Other attempts are rejected as malformed, including expressions with unbalanced syntax or division by zero.The feedback explicitly identifies malformed expressions and an undefined division-by-zero expression.
- Incorrect evaluations: Early attempts are rejected because their expressions evaluate to 15, 18, or 17 instead of 24.The examples show successive candidate expressions and the verifier's reported evaluations.
A.4.1 Hallucinations in Graph Coloring Critique
GPT-4’s graph-coloring critiques frequently hallucinate graph structure and vertex colors, sometimes reversing the verification question or contradicting themselves.
- Hallucinations decrease proportionally as the graph’s error rate increases, because denser errors make finding a genuinely wrong edge easier.Randomly colored graphs contain incorrect edges at roughly half of all edges on average.
- Graph-coloring critiques commonly invent edges between same-colored vertices that are not connected in the graph.This edge hallucination pattern is more common than misstating the colors of actually connected vertices.
- Vertex hallucinations instead misstate the colors of two connected vertices, while cases combining nonexistent edges and nonexistent color violations are rarer.The model does not hallucinate new vertex names; it assigns incorrect colors to existing vertices.
- Some responses reverse the question, claiming same-colored vertices violate constraints because they are not connected, or contradict themselves about a vertex’s color.These failures show that critique errors are not limited to isolated edge or color mistakes.
- The examples include both correct identification of violated edges and critiques containing multiple unsupported claims about graph connectivity and colors.The verification outputs illustrate how a critique may mix a valid violation with hallucinated violations.