Source-linked AI summary
GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problems
Kaya Stechly, Matthew Marquez, Subbarao Kambhampati
TL;DR
The paper asks whether iterative prompting can improve LLM reasoning, especially through self-critique. It empirically tests GPT-4 on graph coloring with self-critique and external verification, finding that GPT-4 struggles to solve and verify instances while external verification improves results without detailed feedback proving essential.
Problem
Despite challenges to LLM reasoning, optimism persists that iterative self-critique can refine incorrect answers, partly relying on the assumption that verification is easier than generation.
Source: §1 · pp. 1–2Method
The authors empirically evaluate GPT-4 solving and verifying graph-coloring instances directly and iteratively, comparing LLM self-critique with an external guaranteed-correct reasoner.
Source: §1 · p. 2Results
About 16% to nearly 40%, external-verifier prompting improved bottom-line performance; GPT-4 self-critique did worse than direct generation, and minimal feedback and top-k verification were nearly as effective as detailed feedback.
Source: §1 · p. 2Takeaways & Limitations
On graph coloring, the results call into question claims about LLM self-critique, while top-k completions recognized by an external verifier offer a competitive alternative to detailed iterative feedback.
Source: §1 · p. 2Common graph-coloring benchmarks have hundreds to thousands of nodes and edges, beyond current LLM context windows; the authors expect poor performance above 20 nodes.
Source: §3.1 · p. 3
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, 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.
1 Introduction
The paper tests whether iterative prompting improves GPT-4’s graph-coloring performance, including whether self-critique or external verification helps. GPT-4 performs poorly at both solving and verification; external-verifier prompting improves results, but minimal feedback and top-k selection are nearly as effective as detailed feedback.
1 Introduction
- The study addresses continued optimism that iterative self-critique can refine initially incorrect answers, despite earlier challenges to LLM reasoning robustness.The authors question the assumption that verification is easier than generation, noting that task complexity may be irrelevant if LLM behavior is approximate retrieval.Source: §1 · pp. 1–2
- The study compares direct and iterative GPT-4 performance on graph coloring, testing both LLM self-critique and an external guaranteed-correct reasoner.It also examines whether the criticism’s content affects bottom-line performance.Source: §1 · p. 2
- GPT-4 was poor at solving graph-coloring instances and no better at verifying solutions; self-critiquing performed worse than direct generation.The system could overlook a correct coloring it had generated and later return an incorrect one.Source: §1 · p. 2
- About 16% to nearly 40%, external-verifier backprompting improved bottom-line performance; “try again” was nearly as effective as meaningful feedback, and top-k verification was competitive.The authors suggest that correct answers may already occur among top-k completions and be recognized by an external verifier.Source: §1 · p. 2
- The authors conclude that the findings raise grounds for skepticism about iterative prompting, particularly approaches relying on LLM self-critique.Source: §1 · p. 2
2 Related Work
Prior work reports divergent conclusions about LLM reasoning and iterative prompting; this paper focuses on evaluating iterative prompting using graph coloring.
2 Related Work
- Research on LLM reasoning spans planning, logic, arithmetic, and the 24 puzzle, with studies reaching divergent conclusions about LLM limitations and iterative prompting.Source: §2 · p. 2
- This paper focuses on assessing claims about the effectiveness of iterative prompting, including claims that self-reflection can help LLMs learn complex tasks over a handful of trials [15].Source: §2 · p. 2
- The authors use graph coloring, an NP-complete problem connected to satisfiability, constraint satisfaction, resource allocation, and scheduling, as their reasoning task.Source: §2 · p. 2
3 Methodology
The methodology uses small graph-coloring instances to compare GPT-4 generation, verification, and feedback strategies, including tests of whether specific feedback adds value beyond repeated attempts.
3.1 The Graph Coloring Problem
- About 100 planar graph-coloring instances with 10–17 nodes were generated; graph coloring is human-readable, readily checked, and connected to satisfiability, constraint satisfaction, scheduling, and allocation.Graphs used an Erdős–Rényi procedure with p = 0.4, were retried if non-planar or duplicate, and were compiled in DIMACS format with a precalculated chromatic number. The authors note that common benchmark graphs are much larger and that models are unlikely to do well above 20 nodes.Source: §3.1 · p. 3
3.2 Architecture for Iterative Backprompting
- The architecture translates graph edges into natural-language prompts, has GPT-4 generate and verify colorings, and feeds verifier feedback plus conversation history into another generation round.The loop ends when GPT-4 approves a coloring or after 15 iterations, after which a sound verifier evaluates the final answer.Source: §3.2 · p. 3, Figure 1 · p. 4
3.3 Backprompt Generation
- The guaranteed-correct verifier evaluates candidate answers and supplies backprompts, while the system stops on verifier approval or after 15 rounds.The verifier can identify every contradicting edge, and feedback is wrapped in standard instructions and appended to prior message history.Source: §3.3 · p. 4
- The external verifier can report no more than the first error or provide a comprehensive list; the study also tests pass/fail feedback and LLM-generated feedback.The five feedback conditions include no backprompting as a single-iteration baseline.Source: §3.3 · p. 4
- The study compares feedback regimes with higher-temperature and multiple-answer prompts that provide no information beyond the original prompt.Top-5 responses are tested at temperatures 0.5, 1, and 1.5; top-15 responses are tested at temperature 1.Source: §3.3 · pp. 4–5
3.4 Verification
- GPT-4 is prompted to check coloring correctness, optimality, completeness, and to list conflicting edges, using five types of colorings including correct, altered, non-optimal, random, and LLM-generated examples.The verification experiments use the same graph instances and give no backprompts.Source: §3.4 · p. 5
4 Results
In graph-coloring experiments, more sampling opportunities matched iterative prompting, while richer feedback did not improve results. GPT-4 struggled to verify colorings, and its local corrections did not distinguish real errors from false ones.
4.1 Backprompting as Self-Critique
- Self-critique reduced the 16% baseline to one correct instance out of 100 because GPT-4 failed to stop when it generated correct colorings.Among 40 instances with an optimal coloring during backprompting, the verifier recognized none; it hallucinated same-colored adjacent pairs in 39 cases.Source: §4.1 · pp. 5–6
- With n=15 (t=1.0), separate sampling reached 40%, comparable to backprompting; sound-verifier feedback variants differed insignificantly, and charitable self-critique also scored about 40%.The study reports roughly similar results across the backprompting types under this charitable scoring.Source: §4.1 · pp. 6–7
4.2 Verification by LLM
- GPT-4 marked only 30 of 500 candidate colorings correct, and just 5 approvals were right; fewer than 10% of cases received its categorical responses.Rare responses also reversed the question or contradicted themselves mid-deduction.Source: §4.2 · p. 7
- Hallucination proportions fell as erroneous-edge rates rose, while fabricated edges were more common than vertex-color errors.Table 2 compares instances featuring each hallucination type with total erroneous edges across subsets.Source: §4.2 · p. 7, Table 2 · p. 7
4.3 Inside the Backprompt Chain
- GPT corrected many backprompted edges but also corrected false “evil” errors, applying local fixes without distinguishing whether the reported errors were real.The analysis counts whether listed edges were changed so their endpoints had different colors; “evil” prompts falsely label a correct edge as incorrect.Source: §4.3 · p. 8, Table 3 · p. 8
5 Conclusion
The paper finds that LLMs are poor at verifying graph colorings, undermining self-critique; a sound external verifier helps, but feedback content is not important to the observed gains.
5 Conclusion
- LLMs are very poor at verifying colorings, a capability critical to self-critiquing their solutions.With self-critique, iterative prompting does even worse than direct generation.Source: §5 · p. 8
- A sound external verifier in the loop can help, but the actual content of iterative backprompts is not important to the improvement.The improvements are also obtained by generating multiple answers and letting a verifier select a correct one that was fortuitously generated.Source: §5 · p. 8
- The results on graph coloring raise questions about claims that LLMs can effectively self-critique and about their reasoning capabilities.Source: §5 · p. 8
A.1 Prompts
The appendix gives prompt examples for generating a graph coloring, checking a proposed coloring, and requesting a revised coloring after feedback.
A.1 Prompts
- The generation prompt asks GPT-4 to color a graph described by its edges, using at most three colors and labeling every vertex.Source: §A.1 · p. 10
- The response instructions require one color assignment per vertex, formatted as “{VERTEX NUMBER}: {VERTEX COLOR ASSIGNMENT}” with no other text.Source: §A.1 · p. 10
- The verification prompt supplies an asserted optimal coloring and asks whether it is correct, requesting shared-color edges if it is not.Source: §A.1 · p. 11
A.2 Backprompts
The appendix illustrates several backprompt formats, from pass/fail instructions to feedback naming one or more conflicting edges, followed by a request to recolor the graph.
A.2 Backprompts
- The appendix also shows a backprompt generated from the model’s own critique, which names an alleged conflict and requests another coloring.Source: §A.2 · p. 11
- A pass/fail backprompt says the coloring is incorrect and asks for a correct coloring without listing a specific error.Source: §A.2 · p. 11
- A first-error backprompt identifies one same-colored connected pair and then asks the model to recolor every vertex.Source: §A.2 · p. 11
- A full-feedback backprompt lists multiple violated edges before asking the model to try again.Source: §A.2 · p. 12
A.3 Complete Example of Iterative Prompt Sequence
The appendix presents a 15-backprompt example in which the model repeatedly receives alleged edge conflicts and returns revised color assignments.
A.3 Complete Example of Iterative Prompt Sequence
- The example is labeled as a sequence of 15 LLM-generated backprompts and begins with a graph-coloring request listing the graph’s edges and a three-color limit.Source: §A.3 · p. 12
- One feedback step flags several same-colored connected vertex pairs, after which the model returns a revised assignment.Source: §A.3 · p. 13
- Later steps again identify alleged conflicts and request recoloring, with the model producing further assignments in the sequence.Source: §A.3 · p. 13
A.4 LLM as Verifier
The verification examples include outputs that check vertex-edge color assignments and conclude that some colorings are valid. The section also presents rare mangled or illogical outputs, including incorrect claims about same-colored adjacent vertices and color limits.
Examples of LLM Output on the Verification Task
- The examples report shared edges from vertex 5 to 7, 6 to 10 and 12, 8 to 10, 9 to 11, and 10 to 12; vertex 11 is not connected to vertex 10.Source: §A.4 · p. 18
- One output says no adjacent vertices share a color and no colors exceed the optimal coloring number; the verifier confirms success.Another example describes a coloring using three different colors.Source: §A.4 · pp. 17–18
Examples of (Rare) Mangled, Illogical, and Otherwise Strange Output on the Verification Task
- The rare strange outputs include claims that adjacent vertices share a color, sometimes alongside contradictory color descriptions.Examples include claims involving vertices 9 and 10, vertices 1 and 4, and vertices 0 and 1.Source: §A.4 · pp. 17–18
- Other strange outputs give faulty rationales, including calling color 4 greater than an optimal coloring number of 4 or citing connected vertices with different colors as proof of incorrectness.One example also says vertex 0 is missing, while another claims a vertex colored 4 exceeds an optimal coloring number of 4.Source: §A.4 · pp. 17–18