On the self-verification limitations of large language models on reasoning and planning tasks
Authors: Kaya Stechly
Karthik Valmeekam
Subbarao Kambhampati
Venue: ICLR 2025 Poster (2025)
Keywords: Large Language Models
Reasoning
Planning
Self-Critique
Verification
Primary area: foundation or frontier models, including LLMs

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.

Published as a conference paper at ICLR 2025
ON THE LANGUAGE MODELS ON REASONING AND PLANNING TASKS
S VELFFVERIFICATION LIMITATIONS OF LARGE
Kaya Stechly* Arizona State University thstechl@asu.
Karthik Valmeekam"
Subbarao Kambhampati Arizona State University raoßasu. edu
Arizona State University
kvaimeek@asu. edu
ABSTRACT
There has been considerable divergence of opinion on the reasoning abilities Large Language Models (LLMs). While the initial optimism that reasoning might emerge automatically with scale has been tempered thanks to slew of counterexamples-range from multiplication to simple planning- there persists a widespread belief that L.MSs can, in general fashion, self-critique and improve their own solutions iteratively. This belief seemingly rests on the assumption that verification of correctness should be easier than generation-a rather classical argument from computational complexity -wichh should be irrelevant to LLMs to the extent that what they 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 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. Across most of our domains, we observe significant performance collapse with self-critique and significant performance gains with sound external verification. We also note that merely re-prompting with sound verifier maintains most of the benefits of more involved setups.
INTRODUCTION
Large Language Models (LLMs) have rapidly captured the attention of the Al research community with their exceptional natural language completion capabilities. Trained on web-scale language corpora, these models have demonstrated the ability generate seemingly valuable completions across a wide range of topics. This has led to a surge of interest in determining whether such models able perform well on reasoning tasks. Though initial anecdotal results showed promise, further systematic studies revealed inconsistencies and significant issues when applied to reasoning tasks-such as simple arithmetic or logic (Dziri et al. (202) and planning (Valmeekam al. (023b). These results have questioned the robustness of their reasoning abilities and led researchers to explore ways to augment and improve these systems.
Of particular interest to us are emerging claims about LLM self eeff-critiuiig. In a typical setup, an LLM is iteratively prompted so that both generates candidate solutions and, in response to separate queries, evaluates them. This process is looped until some stopping condition is met in hopes of potentially generating refined answer. Current works (Yao et al. 2023a Shinn et al. 2023 Weng et al. 2023 Chen et al.) Madaan et al. (023), while admitting that LLMs are not good reasoners on their own, still exhibit considerable optimism about such self-critique systems. This belief seems to rest largely the assumption that verification of correctness should be casier than generation for many reasoning problems-a rather classical argument from computational complexity. However, think there grounds to be skeptical of this assumption. The complexity of the reasoning task
"Equal Contribution

---

Published as a conference paper at ICLR 2025
should be largely irrelevant to LLM performance, especially if what they are doing is better modeled as approximate retrieval (Kambhampati 2024).
Intrigued by the prevailing optimism, in this paper set out to systematically investigate the effecttiveness of using LLMs to critique their own generations in the context of planning and reasoning. To gain meaningful insights into the verffication/crtiiuinng abilities of LLMss for reasoning tasks, it is ground truths are available for both generation and criticism. Note that such verification not feasible in tlyle-baaee/qualitttiv tasks like creative writing (Yao et al. 2023a) where there is no formal notion of correctness and critique can vary widely. With this understanding, we select three distinct reasoning problems (Game of 24, Graph Coloring, and STRIPS planning), in which there exist formal notions of correctness that allow us to automatically check the veracity and quality of both (binary) verification and critique generated by the L.M.. Furthermore, these domains are chosen so that the algorithmic abilities they test are fundamental any other reasoning task must include components that test these same capabilities, or else be only a retrieval task.
crucial to test them on formal tasks-ones where
Our methodology employs a system (which we refer to as LLM+LLM) that uses the same LLM 1337-4-0613 (Achiam et al. 2023)) for both solution and feedback generation. A generation prompt is sent to the LLM. Its response is used to create a verification prompt, which is then sent back to the same LLM. We use the feedback generated in this way then create backprompt, thus restarting the cycle.
Across most of our domains, this self- system worsens performance. We find that the number of backprompts increases, this kind of self-correction consistently degrades output quality. Our analysis reveals that the verifier LLM's false negative rate is significant across our domains. In essence, even when the LLM generates a valid solution, the verifier LLM rejects it often enough that overall performance suffers.
We contrast this performance collapse with two baselines. The first is an ablated variant of the system (which we refer to LLM+Sound Verifier), where an external sound verifier evaluates the LLM's generations and produces critique. This setup gives substantial performance gains across all domains, but closer analysis shows that the level of feedback often doesn't 't seem to matter-at as long as the verifier is sound, improvement remains regardless of how much or how little feedback the LLM receives.
We ablate the system further, and remove critique entirely. In this setup, the LLM is repeatedly queried with the exact same base prompt until a sound verifier certifies its solution. Within this impoverished setting, prompts no longer maintain past history of guesses, yet can maintain most, not all, of the gains shown by our previous, more complicated, more expensive setups.
Our empirical results suggest that the benefits of iterative prompting and verification can easily be misattributed to opaque self-critique and seemingly rich feedback. Thus, future implementations of LLMs for reasoning tasks should take the form of LLM-Modulo systems (Kambhampati et al.) b)) where verification is done by external sound systems. In the rest of the paper, we first review related work and discuss domain backgrounds. Then, we explain our methodology, and finally closely analyze LLM self-verification abilities on our domains.
RELATED WORK
Following the release of GPT-4, anecdotal accounts of performance on reasoning tasks (Bubeck et al.
2023) spurred much research into the capabilities of LLMs on various reasoning domains, from
menagerie of benchmarks covering basic problems (Kojima et al. (022) to planning (Valmeekam
ct al. 2023b), logic and arithmetic (Dziri et al.) 2023). analogical reasoning (Webb et al. [023). ) and
even math puzzles (Yao et al. (023a). Though these seemed initially promising, systematic studies began to generate negative results across many of these domains (Valmeekam et al.) 2023b Silver
ct al. 2022 Abdin et al.) Ullman 2023 Gendron et al. 2024), claiming that LLM scaling shows much lower returns for reasoning tasks (Rae et al., 2021 1). and showcasing brittle performance in the face of minor problem permutations (McCoy al. 2023 Dziri et al. 2023 Arakelyan et al. 2023).
In response, researchers created augmented systems which embed the LLM in larger frameworks in attempt to improve performance. These take many forms: common search algorithms with the LLM cast in the role of heuristic (Yao et al.) [203a]] Hao et al. 2023), approaches which reduce error rates by enforcing various consistency conditions (Du et al. Cohen et al. 2023
[Jiag et al.
2

---

Published as a conference paper at ICLR 2025
)023). and direct LLM self-critique (Shinn et al. 2023: Weng et al. 2023 Chen al. Huang et al.
b: Madaan et al.) 2023 Yao et al. (2023b).
In the current work, are interested in examining this third approach: LLM self-critique. In the most basic case, the LLM is queried for an answer, and then is re-queried with its own response together with some instructions to critique or improve it, with this process looped until some stopping condition. This is fundamentally based on the intuition that verification is easier than, or at least different enough from, generation that such a process can improve performance-in analogy to human self-critique (eeeen et al. 2023).
The literature abounds with strong, well-cited, and well-referenced claims about the efficacy of these techniques. (Shinn et al., 2023) claims there is an "emergent property of self-reflection in LLMs" and that "self-reflection is extremely useful to learn complex tasks over handful of trials." " Their experiments claim that every variety they try leads to improvement, and that this is because "self-reflective feedback acts as 'semantic' gradient signal by providing the agent with a concrete direction to improve upon, helping it learn from prior mistakes to perform better on the task. task: Other works claim this self-correction does not require "any human feedback" (Chen et al.) and that "even when an LLM cannot generate an optimal output on its first try. the LLM can often provide useful feedback and improve its own output accordingly." " (Madaan et al. 2023) seeming to indicate that these claims generalize beyond the domains, problems, and prompts they were originally made for.
However, some further systematic investigations have found less impressive results in logical fallacy detection (Hong et al. 2024) and HotpotQA (Huang et al. a) demonstrating very brittle improvement at best, some of which could be replicated sans self critique by merely including missing domain- general information into the original prompt. The authors of the CRITIC framework (Gou et al.) were the first to notice that, in some cases, LLM self-critiuee can lead to decreases in performance when compared to sound verification. Contemporaneous to our work P (Huang al., a investigate two-round self-correction schemes in the GSM8K, CommonSenseQAA and HotpotQA domains. They compare which answers were changed (from correct to incorrect or incorrect to incorrect) and which weren't I, and discuss extensions of their argument to multiagent debate.
Our own work focuses on autonomous multi-round veffiverinication within three formally verifiable domains that reflect reasoning tasks. We extend previous work by ablating the self self-critique system thoroughly to pinpoint the source of performance deterioration, considering more prompting rounds (up to 15), and by examining a new set of domains which we argue are better and more broadly applicable tests of reasoning and self-correction capability.
Reasoning is fraught term. Previous work has used it to refer, among others, to the human ability to draw conclusions(Leighton & Sternberg 2004), to the ability to apply common sense to simple scenarios, to positive performance on thort-form written tasks, and to formal deductive inference. However, it is often unclear which definition given set of authors presupposes when making claims about LLM reasoning capabilities. This muddies the discussion and contributes to strange duality: highly cited papers claim that LLMs are general-purposs reasoners (Kojima et al. 2022] Wei et al..
2022: Bubeck al., 2023 Zhou et al.);; that they have strong, human-like self-reflection capabilities
which allow them to correct reasoning mistakes they do make (Shinn et al. 2023 Chen et al. Madaan
cet al., 2023;; ; that they can answer difficult, never-before-sece questions via in-context learning
as long as they are allowed to use chain of thought to generate intermediate scratch work (Dong
al. al.]| (202)); that they can pass or come close on many high school and college-level examinations
(Achiam et al.] 2023 Gilson et al.] 22033 Raimondi et al. 2023 Thaker et al.] 2024 Yeadon & Halliday 2023; de Winter 2023] Kortemeyer 2023) and that performance on such standardized exams i8 evidence about their reasoning capabilities and domain expert knowledge (Wang et al. a)) Yet, responses to counterexamples and negative results, anecdotally, fall back on a much weaker, seemingly contradictory constellation of premises: LLMs only perform well on things they were trained on, and-in fact-if a model performs poorly, we can only conclude wasn't 't trained on that (but if it performs well, it is generalizing); the average non-expert human would fail this task if presented it with zero context or training, therefore it's unsurprising that the LLM fails; no good
I Note that our results ablate away much of this signal (especially the 'concrete direction' that exists in explicit critique) to find that most of the improvement in our domains comes from the soundness of the verifier. Prelliinaay results from our work were originally presented in two papers NeurlPS 2023 workshop.
3

---

Published as a conference paper at ICLR 2025
prompt engineer would query the LLM in this fashion. (How to tell if prompt is good? It follows one of several anthropomorphized design patterns and, most importantly, the result is positive.)
These shifting definitions and implicit assumptions make it very difficult to make concrete claims and expect to be understood, and they make it even more difficult to pin down claims made by others or attempt to falsify them. In the current work address this by restricting our focus to fully specified, formally verifiable problems which can be solved directly by deductive methods. Though these may first seem like a very narrow class, especially when compared the coruucopia of commonsense, language-based, and domain-specific benchmarks in the literature, we argue that they are fundamental, as any other reasoning tasks must include components that test these same capabilities supabilitiss-otheriiee otherwise they are merely testing recall. Our work extends studies that have looked at similar problems, especially those that examined L.LM planning capabilities and other classical reasoning problems (Valmeekam et al. 2023a by Stechly et al., 2024 Dziri et al. 2023). However, no previous work has looked carefully at broad range of formal verification problems. Filling in lack of benchmark coverage contributes to the illusion that LLMs possess
this gap is important, greater competency than they really do (Saxon 2024).
Furthermore, common domains fall short for evaluating the reasoning and self-critique abilities of LLMs for additional reasons: test set memorization, lack of problem difficulty, and lack of ground truth.
Test set memorization: Due to the black box nature of state of the art models, ensuring that they weren't 't trained on those problems is difficult, and there is compelling evidence that they have memorized significant chunks of common benchmark sets (Roberts et al., 2023). 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 (Yang et al. 2018 Srivastava et al.) 2023). We consider arbitrary generation of new instances of varying difficulty key desideratum for any evaluation domain.
Lack of problem difficulty: Some of the benchmarks (e.g. HotPotQA (Huang et al. (Madaan al.] (023) Jused in evaluations of velf-verification are easy-that is, SoTA LLM already high-and are therefore much less informative about the effects of the refinement procedure, especially we are interested in how much generalization this procedure allows beyond baseline direct prompting. 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 produce and evaluate, but trivializes refinement: even a very simple agent can solve an n-choice problem with n - critiques-jut don't 't repeat the same answer. Conclusions drawn over reduced problem spaces of this type unlikely to generalize.
GSM-8k performance
Lack of ground truth: A number of tasks that LLMs are evaluated on (e.g. writing prompts Yao et al.) (2023a), constrained text generation (Lin et al. 2020), toxicity control (Welleck et al. 2022 Gou et al.) etc.) are problems without a well-defined ground truth. Instead, they are evaluated by couple of indirect methods. Some require assorted set of metrics which may not be well-validated for L.LMs (e.g. see Ullman (2023) for discussion on problems with transferring results from human- validated tests). Some are scored by humans (aao et al. 2023a). And some are evaluated by another
pre-trained language model (Madaan et al. (2023) or black box AI evaluator (Welleck et al. 2022). This makes conclusions much harder to draw.
BACKGROUND ON TEST TASKS
We evaluate GPT-4's self-critique abilities over three distinct tasks, chosen because we believe they are good proxies for harder reasoning tasks, and because they allow freedom in arbitrary generation of additional instances while providing casy-to-deploy formal verifiability and guaranteed quality.
This gives more than just flcxibility-it also decreases the chance that our instances are represented in the black box model's opaque training sets. This strengthens our results by reducing the likelihood that the model can substitute approximate retrieval for more general reasoning ability.
Any given problem in sets also has the property that it has large number of potential solutions, and this solution space cannot be substantially reduced through simple pattern- matching. As we interested in serfiiiriiia loops where the L.LM has access to its previous guesses, it is very
4

---

Published as a conference paper at ICLR 2025
important that removing handful of possible solutions does not trivialize the problem. Compare this to common multiple choice question datasets, where any n-option problem can solved in n exclusive guesses.
3.1 GAME OF 24
Game of 24 arithmetical operations (addition, multiplication, subtraction, and division) to create an expression that evaluates 24. The numbers are typically constrained the range 1-12, a nod to game' playing card roots. Previously, it has been used as domain of evaluation for other LLM self- self-verification schemes Yaoo et al. 2023a) and fulfills our domain desiderata (see We use it here to enable direct
24 is math puzzle where the goal is combine four numbers with parentheses and basic
comparisons between previous work and the current paper.
Following Yao et al., 2023ap, we use data scraped from 4nums com This list of problems is ordered from shortest to longest average human solution time. Like (Yao et al. (203a)), we evaluate our generation tasks on instances 901-1000. However, when evaluating verification and critique alone, we use instances 1-1000.
Verification this domain is straightforward: given a proposed expression, simplify it using basic arithmetic and check if it is equal to 24. As a sound verifier, library for symbolic mathematics, and handle any errors that throws (for instance, if there are unbalanced parentheses) by outputting feedback that says the LLM's generation malformed.
SymP a common Python
3.2
GRAPH COLORING
Graph coloring is canonical NP-complete reasoning problem that related to both propositional satisfiability as well as practical problems like scheduling and allocation. The complexity class NP contains problems that are hard solve, but easy verify, so this allows give insights into reasoning more generally, yet simple enough that it can be specified and evaluated by a human basic pattern matching.
is broad enough to
In this work, an instance of graph coloring problem consists of planar graph together with an optimal coloring number n. The goal output a solution that assigns one of n colors to each vertex such that no two edge-connected vertices share a color.
Using Grinpy to handle common graph operations, we built test set of 100 graphs of varying small sizes. Each graph was constructed using variant of the Erdös-Rédt method (p = 0.4), with any non-planar or repeat graphs discarded. These were compiled into the standard DIMACS format (DIMACS) together with the graph's 's precalculated chromatic number.
Verifying that proposed coloring is correct is also easy: just check the colors of every edge. If any of them has two vertices of the same color, reject the coloring. Our sound verifier is simple, single for-loop implementation of this idea in Python: for each edge in the graph description, we check that both of its vertices different.
Domains
Self- celf-critquinn System
Game of 24
4nums.com
Seneration Prompt
Generating
whan CorreCt
Graph Coloring
Calaring Problem
Prompt Generctor
Prepooues solutions
Bacapromstt Incomoot
Sound Esternal Evoluator
PDOL Files
Planning
Domain
Instonner F-les
Verffcction prompt
Varifynng LIM
Figure 1: Overall Backprompting and Evaluation Architecture
5

---

Published as a conference paper at ICLR 2025
3.3 STRIPS PLANNING
STRIPS planning is formalism used in automated planning that operates in a discrete, deterministic space. Such problems, commonly known as classical planning problems, involve finding a sequence of actions that when executed in certain world state will take the agent to a desired goal state. STRIPS planning has a long history of featuring in various planning challenges and competitions, and is formally represented using the PDDL (Planning Domain and Definition Language) framework (MDDeroott et al.) 1998). We consider two domains in STRIPS planning. One is Blocksworld, a simple common-senss domain used in International Planning Competitions (IPC) 1998) and Mystery Blocksworld, which is an obfuscated version of Blocksworld. For both the domains, we draw instances from Valmeekum et al., 2023a) for our evaluations.
A PDDL specification consists of three components. The domain doesn't 't change between problems and consists of a set of predicates, which can be used to describe the state of the world, and a set of actions-
with their preconditions and effects-tha the agent is allowed to take. The initial state is a list of predicates that are true at the outset of the specific problem (an example predicate, in natural language: "the red block is on the table"). The goal is boolean expression of predicates.
of actions which can be executed from the initial state without violating any of their preconditions and which arrive final state that satisfies the goal. Verifying proposed plans is a matter of following the actions in order and checking that these two desiderata are achieved. For our experiments, we use VAL (Howey et al. 2004) as the sound external critique that evaluates and critiques LLM generated plans.
Solutions to PDDL problems take the form of correct
4 METHODOLOGY
As our results are about ablations of self-critique architectures, our basic test framework is general prompting architecture informed by interchangeable domain-specific components. Our intent is to give the I.M as much information as possible, so we design prompts that include the entire history of previously proposed solutions and the feedback they received.
A problem instance is a domain -ppecffc formal description. In attempting problem, our system (as shown in Figure proceeds as follows: (1) The instance is processed by a simple, hard-coded natural language translator into prompt and sent to the LLM. (2) The LLM's response is wrapped in domain-specific critique prompt, which is separately sent as another LLM query. (3) If the following response claims that the proposed solution is correct, we stop the system and output the proposed solution. If it doesn't, 't the critique is extracted, wrapped in instruction text, and appended to a prompt containing the entire history of interactions so far. This is then sent to the LLM,, and the cycle repeats, potentially until we enforce timeout.
Though only two types of prompts are sent, the LLM can be seen as playing three separate roles: as an answer guesser, a (binary) verifier, and a critique generator. In order to better understand which of these roles contribute increased performance, we will examine variations of this system where one or more of them are changed or removed.
To examine LLM verification abilitics, we first measure the performance of the entire system, and then evaluate false positive and false negative rates across domains. To better understand the guesser role, and the LLM's ability to consider and implement critique, we will modify the loop so that the verification and critique roles are played by a provably sound verifier that provides rich, correct feedback. We will then reduce and eventually eliminate the amount of provided information (e.g. rich feedback: explicitly giving an evaluation of proposed Game of 24 expression; minimal feedback: "the previous answer was wrong": no feedback: re-querying with the base prompt), while keeping track of changes in the performance of the entire system.
For LLM critique generation, we construct subdomains of our original domains. In these prompts, we provide problem description and proposed solution, and we ask the LLM provide domain- specific critique of the solution if it is incorrect. We parse the output using a hard-coded script and measure accuracy compared to the sound verifier's output.
Note that sound verifiers output task specific critiques: for Game of 24, the evaluation of the provided expression (*1 1+4+6=12 not 24"); constraint violations for graph coloring ("vertices and were

---

Published as a conference paper at ICLR 2025
Game24 wyKound eval
eval
Graph Coloring wisound evol
Graph Colorina
% or instancas coreet
Mystery Biockswurld- abound eval
60
Mystery Bocksworld arlm eval
Blocksworld wisound eval
Blacksworld willm eval
0
beckprompting
Figure 2: Performance vs Number of Iterations Before Timeout. We measure performance at iteration n by evaluating how many instances are currently correctly solved (whether the LLM has verified them or not. In other words, we evaluate as if the timeout were n) and adding that to the number the LLM has correctly verified so far. Note that the verifier incorrectly rejects an answer and the followup is wrong, the next round's percent correct may decrease. When paired with sound verifier, the L.MM monotonically improves its performance as the number of backprompts increase up to some asymptote. The top three lines show this for each of our domains. On the other hand, when the LLM itself is used as a verifier, performance collapses immediately.
both colored red despite sharing edge"); and precondition violations (the second action "succumb object a" is invalid because the succumb action requires the pain object to be true, which not the case after the first action.) and failure reach goal ("this plan does reach the goal") for planning.
EXAMINING SELF-VERIFIE VERFFICATIO
Domain
S.P.
LLM+LLM LLM+Sound Critique
Sampling
S.C.
B.F.
F.F.
A.E.F
k=15
k=25
k=15
Game of 24
5%
3%
36%
38%
N/A
28%
42%
6%
Graph Color-
16%
2%
38%
37%
34%
40%
44%
14%
ing
Blocksworld
40%
55%
60%
87%
83%
68%
72%
42%
Mystery
4%
0%
10%
8%
6%
9%
14%
4%
Blocksworld
Table 1: Accuracy across prompting schemes over 100 instances per domain. S.P.-Stadaard Prompting. B. B.F.-Binary Feedback. F.F.F-First Error Feedback, e.g. first wrong edge, first mistaken action, the non-24 evaluation of the proposed expression. A.E.F-All Error Feedback, e.g. every wrong edge, every mistaken action and error. Note that there is no third critique type for Game of 24 due to the simplicity of the domain. We include two examples of sampling, the other at 25, to show that completely ablating critique retains the performance increases critique. We also include S.C.-Self Consistency results, where the most common answer in pool of 15 is the one that is output by the model, as another comparison point.
at 15 samples,
We evaluate our system over 100 instances in each domain. In standard prompting we send single query to the LLM and treat whatever outputs as its final answer. We use this as our baseline. As shown in Table I when augment this condition with the full self-critique setup, performance decreases. In fact, Figure Figure[]shows shows that as the number of backprompts increases, this kind of self- correction consistently degrades output quality. If the L.M were good verifier, then would have
7

---

Published as a conference paper at ICLR 2025
expected it to recognize instances which already right, and thus at worst- maintaniinnin the baseline score.
The LLM-as- veriffer ranges in accuracy depending on the domain, illustrated in Table 2 Notably, Game of 24 and Blocksworld maintain lower rates of both false positives and false negatives, and this is reflected in LLM+LLM performance on those domains, which doesn't t fail as drastically it does in cases. In Blocksworld, we even see a modest improvement, though that improvement is still significantly worse than having a sound verifier. In the remaining two domains, the false negative rates are very high. In effect, the system rejects most answers and then times out on set of later, worse generations.
When we replace the LLM verifier with a sound verifier, every correct answer will be accepted properly. Intuitively, it can do no worse than standard prompting-any correctly initially must be accepted. As shown in Table 1 performance is much higher in all sound critique cases, though still falls short of 100%. Due the setup, this can't 't be due the verifier, but must be the fault of the answer generating LLM. After 15 rounds, any instance that has yet to been answered correctly will time out, and this process is the only source of inaccuracy arising from the LLM-sound verifier loop.
that was generated
In general, it clear that the verifier requires high accuracy or else the overall system will encounter compounding errors. In the reasoning domains considered, LLMssas-verifien are mostly insufficient to prevent these
Domain
Accuracy
F.P.R
F.N.R
Game of 24
87.0% (3567/4100)
10.4% (320/3071)
20.7% (213/1029)
Graph Coloring
72.4% (362/500)
6.5% (25/382)
95.8% (113/118)
Blocksworld
71.8% (359/500)
18.55% (64/345)
15.48% (24/155)
Mystery Blocksworld
79.6% (398/500)
0.5% (2/397)
97.09% (100/103)
Table 2: LLM Verification results. F.P.R. False Positive Rate, F.N.R. False Negative Rate.
5.1 CRITIQUE GENERATION
We consider the quality of L.M -egerrrre free-form critiques separately from that of their binary verification signals, and find that they full of unhelpful hallucinations and mistakes. To obtain the following results, we ran a further suite of experiments with specially crafted proposed solutions wrapped in verification prompts. The exact breakdown of which types of solutions were generated is available in each domain's 's appendix.
In Game of 24, without any further instructions, the LLM tends to output incorrect suggestions for the answer. When prompted to give an evaluation of the proposed expression first, its accuracy varies. In fact, when we restrict ourselves only looking at verification of equations that are guaranteed to equal 24, and therefore must be correct, it labels 79.1% 1% of them as correct, but evaluates 81.6% of them to 24. That is, there are problems which it will evaluate correctly but still mark wrong.
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. A breakdown and detailed examples provided in appendix A.4.1
In the planning domains, the critiquing LLM often hallucinates whether action preconditions are met or not. In Mystery Blocksworld, the LLM incorrectly assumes the state of these preconditions as well. This leads to lower accuracy of the critiques provided by the LLM. A further breakdown is in appendix[A.5.
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. When they compound sufficiently, these errors
Prompt and response examples be found in the Appendix.
8

---

Published as a conference paper at ICLR 2025
actually reduce the performance of the LLM- self-critique loop below that of just taking the LLM's very first guess.
5.2 CRITIQUE CONSIDERATION
Our results also imply that the generator LLM often isn't sensitive to varying levels of feedback. We use sound verifier to critique the LLM's output, and compare the results over three levels of feedback for graph coloring and planning, and over two levels for game of 24. Examples of prompts
containing each sort of feedback can be found in appendices A.3.3 A.4.3 and A.5.7
Binary feedback is the same for all domains: either the verifier accepts the solution, stopping the system, we create a backprompt which says the previous answer was wrong but doesn't elaborate.
First error feedback mentions the first error that was found when evaluating the response from top to bottom (e.g. an incorrect edge in graph coloring, an inexecutable step in planning, the evaluation of the proposed expression in game of 24).
All errors feedback includes every error that was found. Note that due to the simplicity of game of 24, we do not implement a third feedback level for it.
Perhaps surprisingly, Table D shows very little difference between these three conditions. And in two of our domains, increasing the amount of feedback actually leads decrease in performance.
The intuition underlying the entire critique system is that sending a history of previous failed attempts together with information about why those attempts were failures should guide the LLM toward better future answers. If this were true, then we would expect the performance jump to be tied to the content of the backprompts. With only the data discussed so far, it might seem like the relevant content is actually the history of failed attempts the LLM receives rather than any feedback on those attempts. However, for our domains, our final experiments contradict this interpretation as well.
We take our ablation of critique consideration to the logical extreme, and remove the availability of critique entirely. In this sampling setup, we keep the verifier but don't 't change the prompt at all between iterations. The LLM (at t 1) is asked the same question over and over until the verifier certifies it or hits some pre-established timeout.
Represented in Table I the "Sampling" columns, this gives comparable gains to feedback condi- tions. Note that, because prompts do not grow additively with iteration number, the token cost of these prompts is quadratically lower. This allows us increase performance further by just increasing further. As a sanity check, we compare this to a self-consistency baseline (Wang et al. [b. where instead select the most common answer from the 15 generated ones. This baseline is listed under "S.C." and shows no improvement over standard prompting.
Our final results show that, in our domains, the information in critiques does not have much of an effect on performance as previous literature claimed it should. In fact, our performance increases seem stem in large part just from having enough guesses and a sound verifier. In reasoning problems we therefore cast the LLM primarily as an idea generator.
6 CONCLUSION
In this paper, we conducted a systematic evaluation of the self-critique abilities of Large Language Models on three reasoning and planning tasks. We separated self-critique into three components: verification, critique generation, and critique consideration. Across the hard reasoning domains we evaluated, LLMss did poorly in all three roles, with compounding errors from across these roles often making the LLM self-critiquing loop perform worse than just having the LLM guess the solution up front. These failures of verification could potentially be very detrimental to system's dependability, especially in domains where high reliability is paramount. In contrast, we saw performance gains when external sound verifier provides the verification signal and critique. We also found that good performance can be achieved without any critique whatsoever: just let the LLM make many guesses, and have sound verifier pick any that is actually correct.

---

Published as a conference paper at ICLR 2025
Our results throw serious doubt earlier work that very optimistic about LLM self-critique abilities. They also add depth to contemporancous 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.
Our proposal, based on the case studies we' ve performed in this paper is, when possible, to embed LLMs in systems which allow them to guess solutions multiple times, but which provide some kind of signal for when a guess is good enough. Ideally, this takes the form of a sound verifier, like VAL (Howey al. 2004) for STRIPS planning, basic expression simplification for Game of 24, or a constraint checker for constraint satisfaction problems. In real-world applications we expect this role be played by menagerie partial critics evaluating plans or solutions based on criteria that they have access to, designed so that consensus is considered verification. Similar architectures have already shown some success (Romera- Paredes et al., 2023). and previous work has proposed the general LLM-Mooull framework (Kambhampati et al. a) which our stance fits into.
ACKNOWLEDGEMENTS
This research is supported in part by ONR grant N0001423-1-2409, DARPA grant HR001 HR001125220 12520016. and gifts from Qualcomm, J.P. Morgan and Amazon.
REFERENCES
Marah I Abdin, Suriya Gunasekar, Varun Chandrasekaran, Jerry Li, Mert Yuksekgonul, Rahee Ghosh Peshawaria, Ranjita Naik, and Besmira Nushi. Kitab: Evaluating Ilms on constraint satisfaction for information retrieval. In The Twelfth International Conference on Learning Representations.
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint ar arXiv:2303.08772 2023.
Shushan Arakelyan, Rocktim Das, Yi Mao, and Xiang Ren. Exploring distributional shifts in large language models for code analysis. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 16298-16314, 2023.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Fric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv: 2023.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. In The Twelfth International Conference on Learning Representations.
Roi Cohen, May Hamri, Mor Geva, and Amir Globerson. Lm vs Im: Detecting factual errors via cross examination. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp- 1 12621-12640, 2023.
Joost CF de Winter. Can chatgpt pass high school exams english language comprehension? International Journal of Artificial Intelligence in Education, pp. 1-16, 2023.
DIMACS, DIMACS Implementation ChalengessR//mtttp///rrroiiiee ruttess
URL
edu/Cha l Archive available at httt::/ dimass. rutgers. eduu
Challenges/
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Jingyuan Ma, Rui Li, Heming Xia, Jingjing Xu, Zhiyong Wu, Baobao Chang, et al. A survey on in-context learning. Proceedings of the 2024 Conference Empirical Methods in Natural Language Processing, pp. 1107-1128, 2024.
Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. In Forty-first International Conference Machine Learning.
10

---

Published as a conference paper at ICLR 2025
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers compositionality. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
URL http:tttpp::/ppeneeeieee. wwtp:/wwwwweeeeeeenreeeeeee www.nee//ooooooiieoooeerr htt.pp/rreereeeeeoeeeoooooooooor
Gaël Gendron, Qiming Bao, Michael Witbrock, and Gillian Dobbie. Large language models not strong abstract reasoners. In Proceedings of the Thirty-Thin International Joint Conference on Artificial Intelligence, pp. 6270-6278, 2024.
Aidan Gilson, Conrad W Safranek, Thomas Huang, Vimig Socrates, Ling Chi, Richard Andrew Taylor, David Chartash, et al. How does chatgpt perform on the united states medical licensing examination (usmle)? the implications of large language models for medical education and knowledge assessment. JMIR medical education, 91):e45312, 2023.
Zhibin Gou, Zhihong Shao, Yeyun Gong, Yujuu Yang. Nan Duan, Weizhu Chen, et al. Critic: Large language models can self-correct with tool-interactive critiquing. In The Twelfth International Conference on Learning Representations.
Shibo Hao, Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. Reasoning with Language Model is Planning with World Model. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 8154 8173, Singapore, December 2023, Association for Computational Linguis- tics. doi: /ttp:6/////2222.ml1mmm.ooo 507. URL https:
emr ma immin.500 507
Ruixin Hong, Hongming Zhang, Xinyu Pang. Dong Yu, and Changshui Zhang. A closer look at the self-verification abilities of large language models in logical reasoning. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume I: Long Papers), pp. 900-925, 2024.
Richard Howey, Derek Long, and Maria Fox. VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL. In 16th IEEE International Conference Tools with Artificial Intelligence, pp. 294-301. IEEF, 2004.
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. In The Twelfth International Conference on Learning Representations, a.
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al. Inner monologue: Embodied reasoning through planning with language models. In 6th Annual Conference on Robot Learning, b.
IPC. International planning competition, 1998. URL https: www www.icccp--ccofeeeeeee
org/ competiiionn
Weisen Jiang, Han Shi, Longhui Yu, Zhengying Liu, Yu Zhang, Zhenguo Li, and James T Kwok. Backward reasoning in large language models for verification. arXiv preprint 2rXiv:2308.07758.
2023.
Subbarao Kambhampati. Can large language models reason and plan? Annals of the New York Academy of Sciences. 2024.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy. Position: Lims can't 't plan, but can help planning in llm-modulo frameworks. Forty-first International Conference on Machine Learning, a.
Subbarao Kambhampati, Karthik Valmeekam, Matthew Marquez, and Lin Guan. On the role of large language models in planning, july 2023. tutorial presented at the international conference on automated planning and scheduling (icaps), prague, b.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35: 22 2219-222213 2022.
11

---

Published as a conference paper at ICLR 2025
Gerd Kortemeyer. Could an cuuficial-intellieeee agent pass an introductory physics course? Physical Review Physics Education Research, 19(1):010132, 2023.
Jacqueline Leighton and Robert Sternberg. The nature of reasoning. Cambridge University Press, 2004.
Bill Yuchen Lin, Wangchunshu Zhou, Ming Shen, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. Commongen: constrained text generation challenge for generative commonsense reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp.
1823-1840, 2020.
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. Advances Neural Information Processing Systems, 08:465344465599 2023.
Thomas McCoy, Shunyu Yao, Dan Friedman. Matthew Hardy, and Thomas Griffiths. Embers of autoregression: Understanding large language models through the problem they are trained to solve. arXiv preprint arXiv:2309. 13638, 2023.
Drew McDermott, Malik Ghallab, Adele E. Howe, Craig A. Knoblock, Ashwin Ram, Manuela M. Veloso, Daniel S. Weld, and David E. Wilkins. Pddl-the planning domain definition language. 1998.
Jack Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring. Susannah Young, et al. Scaling language models: Methods, analysis & insights from training gopher. arXiv preprint arXiv:2112.11440 2021.
Raffaele Raimondi, Nikolaos Tzoumas, Thomas Salisbury, Sandro Di Simplicio, and Mario R Romano. Comparative analysis of large language models in the royal college of ophthalmologists fellowship exams. Eye, 37(17):3530-355 2023.
Manley Roberts, Himanshu Thakur, Christine Herlihy, Colin White, and Samuel Dooley, Data contamination through the lens of time. arXiv preprint arXiv:2310.10628 2023.
Bernardino Comera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan 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, pp. 1-3, 2023.
Michael Saxon. Benchmarks as Microscppes: A Call for Model Metrology, 2024.
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.
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. NeurIPS 2022 foundation models for decision making workshop. 2022.
Aarohi Srivastava, Abhinay Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam 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.
Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. Chain of thoughtless- ness? analysis of cot in planning. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, Paquet, J. Tomczak, and C. Zhang (eds.), Advances in Neural In- formation Processing Systems, volume 37, pp- 29106-29141. Curran Associates, Inc., 2024. URL ht http:pss/proooeeengggnnuuuuuuuue http:////aaaee.ii.eeeee///e/////
fi F1223355577e10012220000002022220
12

---

Published as a conference paper at ICLR 2025
Nikhil G Thaker, Navid Redjal, Arturo Loaiza-Bonile David Penberthy, Tim Showalter, Ajay Choudhri, Shirnett Williamson, Gautam Thaker, Chirag Shah, Matthew C Ward, et al. Large language models encode radiation oncology domain knowledge: Performance on the american college of radiology standardized examination. Al in Precision Oncology, 1(1):43-50, 2024.
Tomer Ullman. Large language models fail on trivial alterations to theory-of-mind tasks. arXiv preprint wrXiv:2302.08399 2023.
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambham- pati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. In Thirty-seventh Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2023a. URL BttLhttts///opeeeiieeee wwwp:errwwwee..eeeooorree
YXoq14u0UO
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models a critical investigation. Thirty-seventh Confer- ence on Neural Information Processing Systems, 2023b.
Eorum?1d=x6ddgXLE
Xiaoxuan Wang, Ziniu Hu, Pan Lu, Yanqiao Zhu, Jieyu Zhang. Satyen Subramaniam, Arjun Loomba, Shichang Zhang, Yizhou Sun, and Wei Wang. Scibench: Evaluating college-level scien- tific problem-solving abilities of large language models. In Forty-first International Conference on Machine Learning, a.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain thought reasoning in language models. In The Eleventh International Conference on Learning Representations, b.
Taylor Webb, Keith J Holyoak, and Hongjing Lu. Emergent analogical reasoning in large language models. Nature Human Behaviour, (99::522-114) 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thouuht prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837, 2022.
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.
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. pp. 2550-2575, 2023.
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. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369-236222222 2260, 2018
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, 2023a. URL https
//openreview.net net. (aggenervssu.neeffeoooiiiieseees 2ot.:/mmmdmdddddeme0ol..
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023b.
Will Yeadon and Douglas P Halliday. Exploring durham university physics exams with large language models. arXiv preprint arXiv:2306. /5609, 2023.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe V Le, et al. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 PROMPT VARIATION AND CHAIN OF THOUGHT
LLM results are well-known to be brittle to choice and phrasing of prompt. We ran experiments across multiple prompts to ensure the robustness of our results. Table shows the results for the full pipeline where verification prompts are modified to ask for CoT reasoning first. Results from the main paper provided for easy comparison. Prompts be found in each domain's 's prompt section in this appendix, under the header "Prompt to Elicit CoT Verification".
Performance does improve in some, though not all, cases. However, seemingly near-perfect im- provements in verification ability do not translate into near-sound-verifee performance. In G24, CoT increases verification accuracy from 87% 99%, and does shrink the difference between sound verifier and LLM-verifier in the full pipeline, but 6 percentage point gap still remains! Furthermore, these improvements come with large cost increase: in G24, this leads 17 times increase in necessary output tokens, which more than doubles the cost of verification.
Note that Chain of Thought techniques themselves vary greatly in their effectiveness across domains. In particular, in reasoning domains like Blocksworid, previous work has shown that they fail to generalize and are not particularly robust (Stechly al. 2024).
On the rest of the tasks, where verification is also fairly simple and linear, and thus theoretically amenable to CoT, we do not see nearly significant improvements.
Domain
S.P.
Sampling
LLM+LLM
LLM+LLM-C
F.E.F.
Game of 24
5%
28%
3%
32%
38%
Coloring
16%
40%
2%
0%
37%
Blocksworld
40%
68%
55%
53%
87%
Mystery
4%
9%
0%
5%
6%
Table Al: Accuracy across prompting schemes including CoT verification schemes over 100 instances per domain. S.P.-Standard Prompting. Sampling-ker -=15. LLM+LLM-Main paper result. LLM+LLM-C-FUl pipeline with chain of thought verification. F.E.F F.E.F((Sund) First Error Feedback.
We also reran our verification-only experiments with these new prompts, as well as with variations on the original (non-CoT) prompts. Table A2 has these results, presented alongside the original ones.
A.2 ON TREE THOUGIITS
Our results on the Game of 24 setting seem to contradict the results shown in (Yao et al. 2023a).
However, this is mainly because the self-verification setting presented the main text of this paper is not directly comparable to that of (Yao et al. 2023a). We ran an additional analysis to provide direct comparison.
Our external verifier results are all done with only 15 queries to the LLM. Yao et al. 2023a) isn t entirely clear on the number of queries used, but table 7 in the appendix does give cost breakdown. Per problem, 100 CoT prompts costs $0.47, but running Tree of Thoughts (ToT) averages $0.74-cost- equívalent to about 150 CoT prompts. On the exact same test set, we extend our experiments 150 (direct, non-CoT) queries with sound verifier, and we reach 70%, comparable to ToT's s reported 74%.
The remaining difference is likely due to the fact that ToT implements classical breadth-firs search algorithm, only prompting the LLM to generate (much easier) intermediate steps and heuristic evaluations rather than full solutions and reflections. By reducing compositionality and offloading it to a proven classical algorithm, ToT sidesteps some of the major hurdles to LLM reasoning. Our results highlight why such techniques do not scale beyond the simplest toy instances.
14

---

Published as a conference paper at ICLR 2025
Domain
Accuracy
F.P.R
F.N.R
Game of 24
87.0% (3567/4100)
10.4% (320/3071)
20.7% (213/1029)
Game of 24-CoTT
98.8% (4051/4100)
0.2% (6/3071)
4.3% (44/1029)
Graph Coloring
72.4% (362/500)
6.5% (25/382)
95.8% (113/118) 18)
Graph Coloring CoT
77.6% (388/500)
10.7% (41/382)
60.2% (71/118)
Blocksworld
71.8% (359/500)
18.55% (64/345)
15.48% (24/155)
Blocksworld-S
71.2% (356/500)
22.1% (76/345)
8.4% (13/155)
Blocksworld-CoT
77.6% (388/500)
7.6% (26/345)
23.9% (37/155)
Mystery
79.6% (398/500)
0.5% (2/397)
97.09% (100/103)
Mystery-S
79.0% (395/500)
1.26% (5/397)
96.1% (99/103)
Mystery-CoT
81.8% (409/500)
3.2% (13/397)
72.8% (75/103)
Table A2: LLM Verification results across prompts. F.P.R. False Positive Rate, F.N.R- False Negative Rate. The -S cases are non-CoTT prompts with the answer and reasoning swapped for those domains where answer was originally asked for first. The -CoT cases are those in which verification is done with COT.
Correct Evaluation
Correct Verification
correct
81.6%
79.1%
correct-no-info
84.4%
ablated_gg op
47.5%
92.1%
ablated numberr
52.2%
82.9%
random
48.8%
95.5%
random-no-infe
60.3%
LLM
55%
71%
Table A3: GPT-4's evaluation vs. verification on Game of 24 across expression types.
A.3
GAME OF 24
A.3.1
EVALUATION VS. BINARY VERIFICATION FOR GAME OF 24
The following is more in-depth comparison of GPT-4'ss critique and verification abilities on game of 24.
For each instance, we generated five different kinds of proposed expressions: correct, ablated operation (exactly one operation is wrong), ablated number (exactly one number is wrong), random, and I.LM (sampled from L.LM generations). For each of these proposed expression, we sent a query to the LLM asking it to first evaluate the expression and then to say if it is correct, that is equals 24. We also generated two more "no info" cases: correct and random. These two are the exact same as the previous, but only ask for the evaluation of an expression without mentioning the associated goal state (=24) or asking for verification.
Table A.3.I summarizes the results. Note that generated 1000 expressions for each type, from every problem in the full set, but only 100 for the LLM case, as our generations were constrained in the main paper instances 9000
15

---

Published as a conference paper at ICLR 2025
A.3.2 PROMPTS
All of following examples are built on the same Game of 24 problem, except for the LLM Self- CritiCritique examples.
Raw text format of Game of 24 instance
Baseline, Direct Prompt
Use numbers and basic arithmetic operations (+ to cbtain
24. You must write your response. write your answer first, followed by [ANSWER END]
Input: 1
Answer:
Example L.M Response
(1 4)) 24
Prompt To Elicit Verification
Please check if the following expressien uses only the given numbers (and others) and evaluates to 24: (4-9))
Respond only in JSON format as described below:
"evaluation": "number the expressicn evaluated to", "correct": boolean)
Ensure that Python's s json. loads can parse this.Do not provide anything clse in your response."
Prompt To Elicit CoT Verification
Using each of the numbers 7 exactly as many times as they
appear in the 1ist and the basic arithmetic operations (t
/1, it is possible to write an expression that evaluates to 24. only the correct
Please check if the following expression numbers (and no others) and evaluates to 24: (11 7) (9 1) 24
If it is not correct, please give feedback on what is wreng and how correct it. First, think step by step. Check that the expression uses enly the correct numbers, has exactly the right number instances each number, and evaluates to 24. Then decide what your final answer is.
When outputting your final answer, first print the [Answer] tag, then put your final answer after the [Anseer] tag and respond only in JSON format as described below:
"feedback"; "Feedback",
"correct": boolean]
Ensure that Python's s json. loads can parse this.
Let's think step by step. [Thoughts]
16

---

Published as a conference paper at ICLR 2025
A.3.3 BACKPROMPTS
Backprompt Generated From Self-Critique
Feedback: This is not correct.
The expression is incorrect. The correct expression should bei (11
- 2) 5 8 = 24
with this feedback, please try again. Using the numbers 11 please provide a correct expression that evaluates to 24. write your answer first. At the end of your answer, write [ANSWER END]
Answer:
Backprompt Generated From Sound Verifier (Pass/Fail)
Feedback: This not correct. Using the numbers 1 6 please provide a correct expression that evaluates to 24. Write your answer first. At the end of your answer, write [ANSWER KND] Answer:
Backprompt Generated From Sound Verifier
Feedback: This is not correct. This expression consists the numbers 6, 1, 4, but it has to consist of only and exactly
['1', '1', '4', ] Using the nurbers 1 1 4 6 please provide
correct expression that evaluates to 24. Write your answer first. the end of your answer, write [ANSWER BND]
Answer:
Backprompt Generated From Sound Verifier Where the Answer Was Malformed (Missing Parenthesis)
Use numbers and basic arithmetic operations (+ to chtain 24. Write your answer first. At the end of your answer, write [ANSWER END]
Input:
Answer:
((6 (1 1/4)) 24IANSEER END
Feedback: This is not correct. This expression is malformed. Using the numbers 1 4 6 please previde correct expression that evaluates to 24. Write your answer first. the end of your answer, write [ANSWER END]
Answer:
A.3.4 COMPLETE EXAMPLE OF ITERATIVE PROMPT SEQUENCE
Full Sequence of (Sound Verifier Generated) Backprompts Stopping at Successful Comple- tion of the Task
Use numbers and basic arithmetic operations (+ /) to obtaín 24. Write your answer first. At the end of your answer, write [ANSWER END]
Input:
Answer:
(16 / (1 1/4)) = 24 [ANSWER END]
Feodback: This is not correct. This expression is malformed. Using the numbers 1 6 please provide correct expression that
17

---

Published as a conference paper at ICLR 2025
evaluates to 24. Write your answer first. the end of your answer, write [ANSWER END]
Answer:
((6 / (1 1)) 4 24 [ANSWER END]
Feedback: This not correct. This expression is malformed. Using the numbers 1 6 please provide correct expression evaluates to 24. Write your answer first. At the end of your answer, write [ANSWER END]
Answer:
((6 (1 1))
is undefined because involves divisicn by zero. A correct solution could be:
(6 (1 4))
24 [ANSWER END]
Feedback: This
correct. This expression is mal formed. Using
the numbers 1 6 please provide correct expression
evaluates to 24. Write your answer first. At the end of your answer, write JANSHER END]
Answer:
(1 4)) 24 [ANSWER END]
Feedback: This is not correst. This expression consists of the numbers 6, 1, 4, but it has to consist of only and exactly
['1' '1', '4', '6']. Using the nurbers 1 1 4 please provide expression that evaluates 24. Write your answer first. the end of your answer, write [ANSWER END]
Answer:
(6 1) (4 1) = 24 [ANSWER END]
Feedback: This is not correct. This expression evaluates to 15 instead of 24. Using the numbers 4 please provide correct expression that evaluates to 24. write your answer first. At the end of your answer, write [ANSWER END
Answer:
(1 (4 1111 [ANSWRR END
Feedback: This not correct. This expression evaluates to instead of 24. Using the numbers 1 4 please provide a correct expression that evaluates to 24. Write your answer first. At the end of your answer, write [ANSWER END]
Answer:
(4 1))
24 [ANSSER END]
Feedback: This is not correct. This expression evaluates to 17 instead of 24. Using the numbers 1 4 6 please provide a correct expression that evaluates to 24. Write your first. the end of your answer, write [ANSWER BND]
Answer:
A.4 GRAPH COLORING
A.4.1 HALLUCINATIONS IN GRAPH COLORING CRITIQUE
The following is a more in-depth look at GPT-4's critique abilities on the graph coloring problem.
For each instance, we generated five different kinds colorings: correct, ablated (exactly one edge is wrong), non-optimal (a coloring with no constraint violations except that it uses too many colors), random, and I.LM (sampled from L.M generations). For each of these 500 proposed colorings. we sent query to the LLM asking verify if the answer was right, and-if not-to output free-form critique. We then parsed these to determine what edges it said were colored the same at both vertices.
Table A4 summarizes the results. 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 of them. 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.
18

---

Published as a conference paper at ICLR 2025
Table A4: Distribution of hallucinations during verification task. This table counts the number of instances that featured each type of hallucination and compares it to the total number of erroneous edges encountered across all coloring instances in each subset. Note that the correct column tracks the number of colorings where the ground truth is that the coloring is correct.
Hallucinations
Coloring
Vertex
Edge
Both
None
Errors
Correct
Correct
29
72
100
Ablated
24
52
5
24
187
Non-optimal
18
65
Random
10
26
5
66
736
0
LLM
27
240
18
Total
107
256
26
129
282
118
Edge hallucinations are more common than vertex. Essentially, typical behavior is to pick two vertices that the same color in the coloring, but which aren't associated by edge in the graph description, and claim that they are connected and thus illegally colored. Vertex color hallucination when the reverse happens: instead of ascribing edge same-color nodes, the colorings of two connected vertices are misstated. The overlap between the two cases, where a non-existent edge is declared to be violated by non-existent colorings is much rarer than either. Note that it never hallucinates new vertex names, only that vertices which are in graph have colors differing from reality.
Even rarer cases did spring up in the response data. 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; about a vertex's 's color.
began to contradict itself mid-deduction, making multiple claims
We present these examples here. In the following, multiple equals signs in ("==") dividers between separate examples, not parts of the examples.
Examples of LLM Output on the Verification Task
The vertices 1 and are both coler 0 and share an edge.
The vertices 9 and 12 are both colored with Color 1 and they share edge.
Vertex 1: Color 2 connected to Vertex 2: Color 2.
Vertex and vertex 10 are both Coler 2 and share an edge.
Same-color vertices 0 and share an edge.
Vertex (Color 0) and vertex (Color 0) share an edge. Vertex (Color and vertex 2 (Color share edge. Vertex 4 (Color and vertex 8 (Color
share edge. Vertex 2 (Color vertex 4 (Cclor 1) share an edge. Vertex 4 (Color 1) and vertex 11 (Color 0) share an edge. Vertex 12 (Color 2) and vertex 15 (Color 2) share an edge.
and
The vertices 3 and both have Color and they adjacent. The vertices and 11 both have Color and they are adjacent. The vertices and 5 both have Color 0 and they are adjacent. Therefore, the given coloring is incorrect.
0: Color 0 and 9: Color 0 share edge.
0: Color 0 and 10: Color share an edge.
0: Color 0 and 14: Color 0 share an edge.
9: Color 0 and 13: Color 0 share an edge.
19

---

Published as a conference paper at ICLR 2025
Vertex is colored with Color 4, which exceeds the optimal coloring number of 4, Therefore, this coloring is non-optimal.
Vertex is missing in the coloring, Missing assignment.
Vertex (color 3) is connected to vertex (color 2), sharing an edge. Vertex (color 3) is also connected to vertex 4 (color 0), and to vertex 5 (color 0), and to vertex 9 (color 0), and to vertex 12 (color 2), sharing edge with them. Therefore, correctly colored with color 0, color 2, and color 3, making use of 3 different colors.
this assignment
Vertex (color 2) is connected to vertex 4 (color 0), and to vertex 5 (cclor 0) and vertex 6 (color 0), and vertex (color 3), and to vertex (color 0), and to vertex 10 (color 1), and to vertex 11 (color 1), sharing an edge with them. Therefere, this assignment is also correctly colored.
Vertex (color 0) connected to vertex (color 2), sharing an edge. Therefore, this assignment is correctly colored.
Vertex (color 2) is connected to vertex (color 0), and to vertex 8 (color and vertex 10 (color 1), sharing an edge correctly colored.
with them. Therefore, this assignment
Vertex (color 0) is connected to vertex 7 (color 3), and to vertex 11 (coler 1), sharing an edge. Therefore, this assignment is correctly colored.
Vertex (color 0) is connected to vertex 7 (color 3), sharing an edge. Therefore, this assignment is correctly colored.
Vertex (color 0) connected to vertex 10 (color 1), vertex 12 (color 2), sharing an edge. Therefore, this assignment is correctly colored.
Vertex (color 0) is connected edge. Therefore, this assignment is correctly colored.
10 (color 1), sharing
Vertex 9 (color 0) is connected to vertex 11 (color 1), sharing edge. Therefore, this assignment is correctly colored.
Vertex 10 (color 1) is connected to vertex 12 (color 2), sharing an edge. Therefore, this assignment is correctly colored.
Vertex (color isn't connected vertex 10 (color 1), hence, this assignment correctly colored.
Vertex 12 (color 2) isn't connected to vertex 2 (color 0), hence, this assignment is correctly colored.
No adjacent vertices share a same color, and no colors exceed the optimal celering number. Hence, the coloring is correct.
Verifier confi rmed success.
Examples of (Rare) Mangled, Illogical, and Otherwise Strange Output on the Verification Task
Vertex 10, colored 4, connected to vertex 11, also colered 1. However, it is also colored 4, which is greater than the optimal colering of 4. So, this coloring is non-optimal.
20

---

Published as a conference paper at ICLR 2025
Vertex (Color 2) and Vertex (Color are connected and share the same color. Vertex 9 (Color 2) and Vertex 11 (Color 1) are also connected and share the same color.
Vertex (Color 0) connected to Vertex (Color 0)
Vertex (Color 0)
connected to Vertex (Color and Vertex 14 (Color 1), but also to Vertex 7 (Color 1).
Vertex 6 (Color 0) is connected to Vertex 3 (Color 2), Vertex 10 (Color and 13 (Color 2), but also to Vertex (Color 2).
The coloring is incorrect. Vertex (Color 2) and Vertex (Color 3) are connected but have different colors. Vertex 3 (Color 3) is connected to Vertex 6 (Color 3).
Vertex 10, colored 4, connected to vertex 11, also colered 1. However, it is also colored 4, which is greater than the optimal colering of 4. So, this coloring is non-optimal.
A.4.2 PROMPTS
All of following examples are built on the same graph instance.
DIMACS Format For Graphs
0
0
8
0
9
11
13
e
2 9
3 8
3 11
12
4 12
5 11
6 9
10
7
13
9
11
10
13
11
13
OPTIMAL CHROMATIC NUMBER
Baseline, Direct Prompt
Color the following graph, described set of edges, such that
no two vertices on the same edge share color.
You may use at most 3 colors.
Vertex is connected to vertex 7.
Vertex is connected Vertex is connected to vertex Vertex is connected to vertex 11.
vertex 8.
Vertex is connected to vertex 13.
Vertex is connected to vertex 9.
Vertex is connected vertex Vertex is connected to vertex 11.
Vertex is connected to vertex 12.
Vertex is connected to vertex 12.
Vertex is connected to vertex 11.
21

---

Published as a conference paper at ICLR 2025
Vertex is connected to vertex 9.
Vertex is connected to vertex 10.
Vertex is connected to vertex 13.
Vertex is connected to vertex 11. Vertex
connected to vertex 13.
Vertex 11
connected to vertex 13.
There are a total of 14 vertices. Please label every vertex, even if it is disconnected from the rest of the graph.Please provide each vertex's s color. Do not skip any vertices. Each color must be provided on a new 1ine in the response and should formatted as "(VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT)". Please de not provide anything else in your response.
Example LLM Response
0: Colorl
1: Colorl
2: Colorl
3: Color2
4: Colorl
5: Color2
6: Color2
7: Color2
8: Color3
9: Color3
10: Color3
11: Color3
12: Color3
13: Colorl
Prompt To Elicit Verification
The following graph, described as set of edges, has an optimal coloring number of 3:
Vertex is connected to vertex 7.
Vertex is connected vertex 8. Vertex is connected Vertex is connected to vertex 11.
Vertex is connected to vertex 13.
Vertex is connected to vertex 9.
Vertex is connected vertex Vertex is connected to vertex 11.
Vertex is connected to vertex 12.
Vertex is connected to vertex 12.
Vertex is connected vertex 11.
Vertex is connected vertex Vertex is connected to vertex 10.
Vertex is connected to vertex 13.
Vertex 9 is connected to vertex 11.
Vertex 10 is connected to vertex 13. Vertex Please check if this coloring is correct:0: Colorl
connected to vertex 13.
1: Colorl
2: Colori
3: Color2
4: Colorl
5: Color2
6: Color2
7: Color2
22

---

Published as a conference paper at ICLR 2025
8: Color3
9: Color3
10: Color3
11: Color3
12: Color3
13: Colorl
If it is, say 'Verifier confirmed success.' Do not provide anything else in your response. If it is incorrect, please point out which same-color vertices share edge.
Prompt Elicit CoT Verification
[Instruction]]
when outputting your final answer, first print the [Answer] tag, then put your final answer after the [Answer] tag. Respond only the follewing format:
Wrong Edges: a list of incorrect edges
Al1 Vertices Colored: boolean representing if every vertex is colored
Optimal Or Less: boolean representing if the number of colers is no more than the optimal
Correct: boolcan
[Graph]
The following graph, dascribed as of edges, has optimal coloring number Vertex is connected to vertex 7.
Vertex is connected to vertex 8.
Vertex is connected to vertex 9.
Vertex is connected vertex Vertex is connected to vertex 13.
Vertex is connected to vertex 9.
Vertex is connected to vertex 8.
Vertex is connected vertex 11.
Vertex is connected to vertex 12.
Vertex is connected to vertex 12.
Vertex is connected to vertex 11.
Vertex is connected vertex 9.
Vertex is connected Vertex is connected to vertex 13.
Vertex 9 is connected to vertex 11.
Vertex 10 is connected to vertex 13.
Vertex 11 is connected to vertex 13.
[Coloring]
A coloring is correct if no adjacent vertices are the same color and the tctal number of colors used is more than the optimal coloring number. Please check if this coloring is correct: 0: Color1
1: Colorl
2: Colori
3: Colorl
4: Colorl
5: Color!
6: Colorl
7: Color2
8: Color2
9: Color2
10: Colorl
11: Color3
12: Color2
23

---

new Published as a conference paper at ICLR 2025
13: Color3 [ANSWER KND]]
Let's think step by step. Remember to output your final answer in the format described in the instructions. [Thoughts]
A.4.3 BACKPROMPTS
Backprompt Generated From Self-Critique
This is incorrect. Feedback: Vertices 0 and share an edge and are both colored with Colorl. Vertices and 11 share edge and are both colored with Color3.
Using this feedback, please try again. Please provide each vertex's s color. Do not skip any vertices. Each color must be provided
1ine in the response and should formatted as (VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT; Please do not provide anything else in your response.
Backprompt Generated From Sound Verifier (Pass/Fail)
This is not correct. Using the previcusly provided graph, please provide a correct coloring. Please provide each vertex's color. Do not skip any vertices. Each color must be provided on new line in the response and should be formatted as "(VERIEX NUMBER); (VERTEX COLOR ASSIGNMENT) " Please do not provide anything clse in your response.
Backprompt Generated From Sound Verifier (First)
Vertex and vertex were both celored Color3 despite being
connected by an edge.
This is wrong. Please recolor. Please provide each vertex's color. Do not skip any vertices. Each coler must be provided line the response and should be formatted "(VERTEX NJMBER): (VERTEX coL.OR ASS GNMRNT)" Please do not provide anything else in your response.
Backprompt Generated From Sound Verifier (Full)
Vertex and vertex 11 were both colored Color3 despite being connected by an edge. Vertex 10 and vertex 13 were both colored Color3 despite being connected by an edge. Vertex 11 and vertex 13 were both colored Color3 despite being connected by This is wrong. Please recolor. Please provide each vertex's color. not skip any vertices. Each color must be provided on a new line in the response and should be formatted as "(VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT) ", Please do not provide anything else in your response.
edge.
24

---

Published as a conference paper at ICLR 2025
A.4.4 COMPLETE EXAMPLE OF ITERATIVE PROMPT SEQUENCE
Full Sequence of 15 (LLM-Generated) Backprompts
Color the following graph, described as a set of edges, such that no two vertices on the same edge share color.
You may use at most 3 colors.
Vertex is connected to vertex 7.
Vertex is connected Vertex is connected to vertex 9.
vertex
Vertex is connected to vertex 11.
Vertex is connected to vertex 13.
Vertex is connected vertex 9.
Vertex is connected to vertex Vertex is connected to vertex 11.
Vertex is connected to vertex 12.
Vertex is connected vertex 12.
Vertex is connected vertex Vertex is connected to vertex 9.
Vertex is connected to vertex 10.
Vertex is connected to vertex 13.
Vertex is connected vertex 11. Vertex
connected to vertex 13.
Vertex 11 is connected to vertex 13.
There are a total of 14 vertices. Please label every vertex, even if it is disconnected from the rest of the graph. provide each vertex's color. Do be provided on a new line in the response and should formatted as "IVERTEX NUMBER): (VERTEX COLOR ASSIGNMENT)". Please do not provide anything else in your response.
skip any vertices. Each color must
0: Colorl
1: Colorl
2: Colorl
3: Colorl
4: Colorl
5: Color2
6: Color2
7: Color2
8: Color2
Color3
10: Color3
11: Color3
12: Color2
13: Color?
This is incorrect. Peedback: Vertices 0 and share an edge and are both colored with Celorl. Vertices and 11 share edge and are both colored with Color3.
Using this feedback, please try again. Please provide each vertex's s celor. Do not skip any vertices. Each color must be provided
1ine in the response and should be formatted as "(VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT)* Please do not provide anything else in your response.
0: Color1
1: Colorl
2: Color2
3: Color2
4: Color2
5: Color1
25

---

Published as a conference paper at ICLR 2025
6: Colori
7: Color2
8: Color3
9: Color3
10: Colorl
11: Color2
12: Color3
13: Color?
This is incorreet. Feedback:
Vertices 2 and are both colored with Color2 and share an edge. Vertices 7 and 11 are both colored with Color2 and share an edge. Vertices 9 and 13 are both colored with Color3 and share edge.
Using this feedback, please try again. Please provide each vertex's s celor. Do not skip any vertices. Each color must be provided on line in the response and should be formatted "(VERTEX NUMBER) [VERTEX COLOR ASSIGNMENT)". Please do not provide anything else in your response.
0: Colorl
1: Colorl
2: Color2
3: Color3
4: Color3
5: Color3
6: Color3
7: Color3
8: Color2
9: Colorl
10: Color2
11: Color2
12: Colorl
13: Colori
This is incorrect. Feedback:
Vertices 0 and share an edge and are both colored with Colorl. Vertices and 11 share an edge and are both colored with Color2. Vertices 1 and 13 share an edge and are both colored with Colorl. Vertices 7 and 13 share edge and both colored with Color3.
Using this feedback, please try again. Please provide each vertex's s color. Do not skip any vertices. Each color must be provided new line in the response and should be formatted as "(VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT) Please do not provide anything else in your response.
0: Color1
1: Colori
2: Color2
3: Color2
4: Color3
5: Colorl
6: Colori
7: Color2
8: Color3
9: Color3
10: Colorl
11: Color?
12: Colorl
13: Color3
26

---

Published as a conference paper at ICLR 2025
This is incorrect. reedback:
Vertices 0 and both have Colorl and share an edge. Vertices 0 and 11 both have Color3 and share edge. Vertices 7 and 10 both have Cclor2 and share edge. Vertices and 13 both have Color3 and share an edge.
Using this feedback, please try again. Please provide each vertex's s cclor. Do not skip any vertices. Each color must be provided en new line the response and should formatted as "(VERTEX NUMBER); (VERTEX COLOR ASSIGNMENT; Please do not provide anything else in your response.
0: Color1
1: Colori
2: Color2
3: Color2
4: Colorl
5: Colorl
6: Colori
7: Color2
8: Color?
9: Color3
10: Color3
11: Color2
12: Color3
13: Colorl
This is incorrect. leedbbck: Vertices 0 and both have Colorl and share an edge. Vertices 0 and 5 alsc both have Colori and share edge. Vertices 0 and also both have Colorl and have Color2
edge. Vertices and 11 both share an edge. Vertices and both have Color2 and share an edge.
Using this feedback, please try again. Please provide each skip any vertices. Each color be
vertex's s celor. provided en a new line in the response and should formatted as "(VERTEX NUMBER); (VERTEX COLOR ASSIGNMENT)" Please do not provide anything else in your response.
0: Color1
1: Color2
2: Color2
3: Color2
4: Color2
5: Color]
6: Color]
7: Color3
8: Color2
9: Color3
10: Colorl
11: Color2
12: Color3
13: Colorl
This is incorrect. Feedback:
Vertices 0 and both have Colorl and share an edge. Vertices 0 and 11 both have Colorl and share edge, Vertices 3 and both have Cclor2 and share an edge. Vertices 3 and both have Color2 and share an edge. Vertices and 13 both have Color3 and share an edge. Vertices and 11 both have Color3 and share edge. Vertices 11 and 13 beth have Color2 and share an edge.
27

---

Published as a conference paper at ICLR 2025
Using this feedback, please try again. Please provide each vertex's s color. Do not skip any vertices. Each color must be provided en new 1ine in the response and should be formatted (VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT)" Please do not provide anything else in your zesponse.
0: Colorl
1: Color2
2: Color2
3: Color3
4: Colorl
5: Colorl
6: Colorl
1: Color3
8: Color2
9: Color]
10: Color2
11: Color2
12: Color3
13: Colorl
This is incorrect. Feedback:
Vertices 0 and share an edge and are both colored with Colorl. Vertices 2 and 9 share an edge and are both colored with Color2. Vertices and 12 share an edge and are both colored with Color3.
Using this feedback, please try again. Please provide each vertex's s color. Do not skip any vertices. Each color must be provided en new 1ine in the response and should be formatted "(EETEEX NUMBER): (VERTEX COLOR ASSIGNMENT)" Please do not provide anything else in your response.
0: Color1
1: Color2
2: Color2
3: Color2
4: Color3
5: Color3
6: Color3
7: Color2
8: Color3
9: Colorl
10: Color?
11: Color?
12: Colorl
13: Colorl
This is incorrect. Feedback:
Vertices 11 and 13 both have Color3 share an edge.
Using this feedback, please try again. Please provide each vertex's a color. Do not skip any vertices. Rach color must be provided
line in the response and should formatted as "(VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT; ", Please do not provide anything else in your response.
0: Color1
1: Color2
2: Color2
3: Color2
4: Color?
28

---

Published as a conference paper at ICLR 2025
51 Color3
6: Color3
7: Color2
8: Color3
Colorl
10: Color?
11: Colorl
12: Colorl
13: Color2
This is incorrect. Feedback:
Vertices 0 and 11 share an edge and both are colored with Cclorl.
Using this feedback, please try again. Please provide each vertex's s color. not skip any vertices. Each color must provided on a new 1ine in the response and should be formatted "VEETEX NUMBER): (VERTEX COLCR ASSIGNMENT)" Please do not provide anything else in your response.
0: Color1
1: Color2
2: Color2
3: Color?
4: Colori
5: Color2
6: Color3
7: Color3
8: Color2
9: Color3
10: Colorl
11: Color2
12: Color2
13: Colorl
This is incorrect. Foodback:
Vertices 2 and share an edge and are both colored with Cclor2. Similarly, vertices and share edge and both colored with Color2.
Using this feedback, please try again. Please provide each vertex's s color. not skip any vertices. Each color must be provided en new line the response and should formatted as ((ERTEX NUMBER): [VERTEX COLOR ASSIGNMEN:)" Please do not provide anything else in your response.
0: Colorl
1: Color2
2: Color2
3: Color3
4: Color1
5: Color2
6: Color?
7: Color3
8: Color2
9: Colorl
10: Color2
11: Color3
12: Color2
13: Color1
This is incorrect. Feedback:
Vertices 2 and share an edge and are both colored with Color2. Vertices and 11 share edge and are both colored with
29

---

Published as a conference paper at ICLR 2025
Color3. Vertices and share an edge and are both colored with Color3.
Using this feedback, please try again. Please provide each vertex's s color. not skip any vertices. Each color must provided en new line the response and should formatted as (VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT)". Please do not provide anything else in your response.
0: Colori
1: Color2
2: Color2
3: Color3
4: Colorl
5: Color2
6: Color]
7: Color2
8: Color3
9: Color3
10: Colorl
11: Color2
12: Color?
13: Colorl
This is incorrect. Feedback:
Vertices 0 and 11 share an edge and are both colored with Colorl. Vertices and 8 share edge and are both co ored with Color3. vertices and 13 share edge and are both colored with Color2.
Using this feedback, please try again. Please provide each vertex's s color. Do not skip any vertices. Each color be provided en new line the response and should formatted as "(VERTEX NUMBER); (VERTEX COLOR ASSIGNMENT;" Please do not provide anything else in your response.
0: Color1
1: Color2
2: Color2
3: Color3
4: Colorl
5: Color2
6: Color3
7: Color2
8: Color?
9: Colorl
10: Color?
11: Color2
12: Colorl
13: Color3
This is incorrect. Feedback:
The coloring is incorrect. Vertices 0 and 11 share an edge and are both colored with Colorl. Vertices 7 and 13 share edge and both colored with Color2.
Using this feedback, please try again. Please provide each vertex's 3 celor. Do not skip any vertices. Each color must be provided on "(VERTEX NUMBER): (VERTEX COLOR ASSIGNMENT:" Please do not provide anything else in your response.
line in the response and should be formatted
0: Color1
30

---

0: Colori Color2 Published as a conference paper at ICLR 2025
1: Color2
2: Color2
3: Color3
4: Colorl
5: Color2
6: Color]
7: Color]
8: Color2
9: Colorl
10: Color2
11: Color3
12: Colorl
13: Colorl
This is incorrect. Feedback:
Vertices 0 and share an edge and are both colored with Colorl. Vertices 7 and 11 share edge and are both colored with Color3. Vertices and 13 share edge and are both colored with Color2.
Using this feedback, please try again. Please provide each vertex's s cclor. Do not skip any vertices. Each color must be provided
line in the response and should formatted as "(VERTEX NUMBER): (VERTEX COLOR ASSIGNMETT;" Please do not provide anything else in your response.
2: Color3
3: Color2
4: Color2
5: Colorl
Color2
7: Color3
8: Color3
9: Color2
10: Colorl
11: Color?
12: Colorl
13: Colorl
This is incorrect. Feedback:
vertices 3 and share an edge and are both colored with Color2.
Using this feedback, please try again. Please provide each vertex's s color. not skip any vertices. Each color be provided en new line the response and should formatted as (VERTEXX NUMBER) (VERTEX COLOR ASSIGNMENT)" Please do not provide anything else in your response.
0: Colori
1: Color2
2: Color?
3: Color2
4: Color3
5: Colori
6: Color2
7: Color3
8: Color2
9: Colorl
10: Color2
11: Color?
12: Colori
31

---

Published as a conference paper at ICLR 2025
Binary Verification
Type Identified
Critique Generation
Correct
78/100 (78%)
78/100 (78%)
78/100 (78%)
Inexecutable
70/100 (70%)
63/100 (63%)
8/100 (8%)
Non Goal Reaching
98/100 (98%)
12/100 (12%)
12/100 (12%)
Random
100/100 (100%)
94/100 (94%)
2/100 (2%)
Correct
53/55 (96.36%)
53/55 (96.36%)
53/55 (96.36%)
LLM
Inexecutable
25/40 (62.5%)
24/40 (60%)
0/40 (0%)
Non Goal Reaching
3/5 (60%)
2/5 (40%)
2/5 (40%)
Table AS: This table presents the verification and critique accuracy of LLM-as-verifee across five different kinds of plans over 100 instances of Blocksworld.
Binary Verification
Type Identified
Critique Generation
Correct
3/100 (3%)
3/100 (3%)
3/100 (3%)
Inexecutable
100/100 (100%)
100/100 (100%)
24/100 (24%)
Non Goal Reaching
98/100 (98%)
12/100 (12%)
12/100 (12%)
Random
100/100 (100%)
100/100 (100%)
59/100 (100%)
Correct
0/3 (0%)
0/3 (0%)
0/3 (0%)
LLM
Inexecutable
89/89 (100%)
89/89 (100%)
12/89 (13.48%)
Non Goal Reaching
8/8 (100%)
0/8 (0%) 0/8 (0%)
Table A6: This table presents the verification and critique accuracy of LeMaas-errffeer across five different kinds of plans over 100 instances of Mystery Blocksworid.
13: Colorl
A.5 PLANNING
A.5.1 ACCURACY OF PLANNING CRITIQUE
For each instance, we generated five different kind of plans: correct, inexecutable (where action is inexecutable and the plan is thus invalid), non goal reaching (all actions are executable but the plan does not reach the desired state), random, and LLM (sampled from the LLM generations). For each of these prompts, we sent a query to the LLM asking it to verify the plan and critique it in a certain format. We provide an example in the following prompts section. Specifically, if the plan is valid, the LLM has to just output that. If plan is invalid and inexecutable, it has to provide the first action that the plan rendered invalid and the unmet preconditions for that action. If the plan is invalid and non goal reaching, it has to provide the unmet goals for the plan. We evaluate the binary verification and the critique by comparing it to the ground truth provided by VAL (Howey et al.) (004). We check the binary verification, whether not the detected the type of invalidity (inexecutable or goal reaching) and if the critique valid. Tables A5 and A6 show the inability of LLMs in generating the right critique for proposed solutions though they get the label correct.
A.5.2 PROMPTS BLOCKSWORLD
All of following examples are built on the same graph instance.
32

---

Published as a conference paper at ICLR 2025
Baseline, Direct Prompt
am playing with set of blocks where I need to arrange the blocks into stacks. Here are the actions can do
Pick up block Unstack a block from on top of another block Put down a block
Stack a block on top of another block
have the following restrictions en ny actions: can only pick up or unstack one bleck at a time. I can only pick up or unstack black if my hand is empty. the table and the block is clear if the block has other blocks on top of it and the block is not picked up. I can only unstack a block from on top of another plock it the block am unstacking was really on top of the other block. only unstack block from top of another block if the block
I can only pick up block if the bleck is
block is clear.
unstacking is clear.
Once I pick up or unstack block,
am holding the block. can only put down a block that I am holding.
I can only stack block on top of another block if I am helding the block being stacked.
can only stack a block on top of another block the block onto which I am stacking the block is clear.
Once I put down or stack a block, my hand becomes empty. Once you stack block on top of second block, the second block is no longer clear.
[STATEMENT]
As initial conditions have that, the red block is clear, the yellow bleck is clear, the hand is empty, the red block is top of the blue block, the yellow block on top of the orange block, the blue block is on the table and the orange block is on the table.
My goal is to have that the orange block is on top of the red block.
My plan is as follows:
[PLAN]
unstack the yellow block from on top the orange block put down the yellow block pick up the orange block
stack the orange block on top of the red block [PLAN END]
[STATEMENT]
As initial conditions have that, the blue block is clear, the hand is eпpty, the blue block is top of the orange block, the orange block is top the yellow block, the yellow block is on top the red block and the red block is on the table.
My goal is to have that the red block is top of the orange block and the yellow block is top of the red block.
My plan is as follows:
[PLAN]
33

---

Published as a conference paper at ICLR 2025
Example LLM Response
unstack the blue block from on top of the orange block put down the blue block
unstack the orange black from top of the yel low block put down the orange block
unstack the yellow block from on tep the red block put down the yellow block
pick up the red block
stack the red block top of the orange block pick up the yellow block
stack the yellow block on top of the red block [PLAN END]
Prompt To Elicit Verification (Open Ended)
am playing with set of blocks where need to arrange the blocks into stacks, Here are the actions I can do
Pick block
Unstack block from top of ancther block Put down a block
Stack a block on top of another block
I have the following restrictions
actions:
only pick up unstack one block a time. can only pick up or unstack block if my hand empty.
I can only pick up a block if the block is on the table and the block is clear. A block is clear it the block has other blocks top of it and if the block is not picked up. can only unstack block from on top of another block if the block am unstacking was really on top of the other block. I can only unstack a block from on top of another block if the block I am unstacking is clear. Once I pick up unstack block,
holding the block. can only put down a block that am holding.
I can only stack a block on top of another block if I am helding the block being stacked.
only stack block top of another block if the black onto stacking the block is clear.
which
Once put down or stack a block, my hand becomes empty.
Once you stack block on top of second block, the secend block is no Longer clear.
[STATEMENT]
As initial conditions have that, the blue block is clear, the orange block is clear, the hand is empty, the orange block is top of the yellow block, the yellow block is on top of the red block, the red block is the table and the blue block is on the table.
My goal is to have that the red black is on top of the orange block, the blue block is on top of the red block and the yellow block is top of the blue block.
My plan is as follows:
[PLAN]
unstack the orange block from top of the yell lowlow block put down the orange block unstack the yellow block from on top the red block
put down the yellow block
pick up the blue block stack the blue block top of the red block
34

---

Published as a conference paper at ICLR 2025
pick up the orange block stack the orange block on top of the blue block pick up the yellow block stack the yellow block on top of the orange block [PLAN END]
Verify whether the above plan is valid. IE it is valid, please say "Plan is valid." and nothing else. If it is invalid, please say "Plan is invalid." and then provide feedback why the plan fails.
Prompt To Elicit Verification (Format based)
am playing with set of blocks where I need to arrange the blocks into stacks. Here are the actions can do
Pick up block
Unstack a block from on top of another block Put down a block
Stack block top of another block
I have the following restrictions on my actions: can only pick up or unstack one block at a time. I can only pick up unstack bleck if hand is empty.
only pick up block if the block is on the table and the block is clear. block clear it the block has no other blocks on top of it and if the block is not picked up. I can only unstack block from on top of another plock it the unstacking
really on top of the other block. can only unstack block from on top of another block if the block I am unstacking is clear.
block
Once I pick up or unstack block, I am holding the block. I can only put down a block that I am holding,
only stack block top of ancther block if helding the block being stacked.
I can only stack a block on top of another block if the block onto which I am stacking the block is clear.
Once I put down or stack block, my hand becomes empty. Once you stack block on top of secend block, the second block is no longer clear.
|TTATEMENT]
As initial conditions have that, the blue block is clear, the orange bleck clear, the hand empty, the orange block is on top of the yellow block, the yellow block is on top of the red block, the red block is on the table and the blue block is the table.
My goal is have that the red block is top of the crange block, the blue block is on top of the red block and the yellow block is on top of the blue block.
My plan is as follows:
[PLAN]
unstack the orange block from on top the yel low block put down the orange block unstack the yellow block from top of the red block put down the yellow block
pick up the red block stack the red block on top of the orange block pick up the blue block
stack the blue block
top of the red block
35

---

Published as a conference paper at ICLR 2025
pick up the yellow block stack the yellow block on top of the blue block [PLAN BND]
Verify whether the above plan valid. Provide JSON between tags (JSON] and (JSON END] for the verification information. The JSON should contain three main keys: (1) "valid": a binary value that tells if the plan is valid not i.e., the plan when exccuted satisfies the goal conditions. If the plan is invalid and inexecutable then include (2)
"ummet_prccenditionn
This contains two more keys; (2.1) "action": This is the name of the first action that renders the plan inexecutable (2.2) "preconditions": A iist of unmet precondite iitttiion for the mentioned action; executable but not goal reacning then include (3)
the plan is
"unmet _oseet__oosss A list of unmet goal conditions in the JSON. Include only one of the keys (2) or (3) based the plan invalidity.
Prompt Elicit Verification (Chain thought based)
I am playing with a set of blocks where I need to arrange the blocks into stacks. Here are the actions I can do
Pick up block Unstack a block from on top of another block Put down a block
Stack block top of another block
have the following restrictions on my actions:
I can only pick up or unstack one block at a time.
I can only pick up or unstack block if my hand is empty.
the table and the block is clear if the block has other blocks on top of it and the block is not picked up. I can only unstack a block from on top of another block if the block I am unstacking was really on top of the other block. only unstack block from top of another block if the unstacking is clear.
I can only pick up block if the bleck is
block is clear.
block Once I pick up or unstack block, am halding the block. can only put down a block that am helding.
I can only stack block on top of another block if I an helding the block being stacked.
can only stack a block on top of another block the black onto which I am stacking the block is clear.
Once I put down or stack a block, my hand becomes empty. Once you stack block top of second block, the second block is no longer clear.
[STATEMENT]
As initial conditions have that, the red block is clear, the yellow block is clear, the hand is empty, the red block is top the blue block, the yellow block is on top the orange block, the blue block is on the table and the orange block is on the table.
My goal is to have that the orange black is top of the red block.
My plan is as follows:
[PLAN]
unstack the yellow block from top of the orange block
36

---

Published as a conference paper at ICLR 2025
put down the yellow block pick up the orange block stack the orange block on top of the red block [PLAN END]
Verify whether the above plan valid. You will think step by step and cutput intermediate reasoning steps and thoughts for the verification after the [THOUGHTS] tag. Then, provide JSON between the tags [JSON] and [JSON_END] for the verification
informaticn. The JSON should contain three main keys: the plan is invalid and inexecutable then include (1) commet_preccnditione
This contains two more keys; (1.1)
"action": This is the name of the first action that renders the plan nexecutable (1.2) "preconditions"
A 1ist of
preconditiens for the mentioned action; If the plan is
executable but not goal reaching then include (2)
"unmet goals": A 1ist of unnet goal conditions in the JSON.
Finally include (3) "valid": binary value that tells if the plan valid or not i.e., goal conditions. Include only one of the keys (1) or (2) based on the type of plan invalidity.
plan when executed satisfies the
Let's think step by step [THOUGHTS]
Prompt To Elicit Verification (Swapping Answer and Reason Order)
playing with set of blocks where I need to arrange the blocks into stacks. Here are the actions can do
Pick up a block Unstack a block from on top of another block Put down block
Stack block top of another block
I have the following restrictions on my actions: I can only pick up or unstack one block at a time. only pick up unstack block if my hand is empty.
only pick up block if the block is on the table and the block is clear. block is clear if the block has no other blocks on tep of it and if the block is not pi ckek up.
I can only unstack block from on top of another plock if the block I unstacking
top of the other block. can only unstack a block from on top of another block the block I am unstacking is clear.
really
Once I pick up or unstack block, I am holding the block. only put down block that am holding,
only stack block top of ancther block if am helding the block being stacked.
I can only stack a block on top of another block if the block onto which I am stacking the block is clear.
Once I put down stack block, my hand becomes empty. Once you stack block on top of secend block, the second block is no longer clear.
[STATEMENT]
As initial conditions have that, the red block is clear, the yellow bleck is clear, the hand empty, the red block is on top of the blue block, the yellow block is on top of the orange block, the blue block is on the table and the orange block is the table.
37

---

Published as a conference paper at ICLR 2025
My goal is to have that the orange block on top of the red block.
My plan is as follows:
[PLAN]
unstack the yellow block from on top the orange block put down the yellow block pick up the orange block stack the orange block top of the red block [PLAN END]
Jerify whether the above plan is valid. Provide a JSON between tags [JSON] and [ISON_END] for the verification information. The JSON shculd contain three main keys: If the plan is invalid and inexecutable then include (1) "unmet "unmet_ppecondee pranedttprccon This contains two more keys; (1.1) "action": This is the name of the first actien that renders the plan inexecutable (1.2) "preconditicns",
list of unmet preconditions for the mentioned action; If the plan is executable but not goal reaching then include (2) "uamet_goals"; A 1ist of unmet goal conditions in the JSON. Finally include (3) "valid": a binary value that tells if the plan is valid not i.e., the plan when executed satisfies the goal conditions. Include only the keys (1) or (2) based on the type of plan invalidity.
A.5.3 BACKPROMPTS BLOCKSWORLLD
Backprompt Generated From Self-Critique
Plan is invalid.
The plan fails because after stack the blue block en top of the red block, you cannot unstack the yellow block from top the orange block because the yellow block is not clear. It has the blue block on top of it.
Backprompt Generated From Sound Verifier (First)
The above plan invalid. The following action at step 7 has an unmet irecondition. pick up the red block The unmet precondition is: the red block clear
Backprompt Generated From Sound Verifier (Full)
The above plan invalid.
There are unsatiafied preconditions.
The following ng act in at step 7 has an unmet precondition pick up the red block The unmet precondition is: the red block clear
The following action at step 8 has an unmet precondition: stack the red block on top of the orange block The unmet precondition is: the orange block is clear The following action at step has an unmet precondition: pick up the yellow block The unmet precondition is: the yellow block is the table
38

---

Published as a conference paper at ICLR 2025
A.5.4 COMPLETE EXAMPLE OF ITERATIVE PROMPT SEQUENCE BLOCKSWORLD
Full Sequence of (LLM-GGenrraeed) Backprompts
am playing with set of blocks where I need to arrange the blocks into stacks. Here are the actions I can do
Pick up block
Unstack block from on top of ancther block Put down block Stack block top of another block
I have the following restrictions en my actions: can only pick up or unstack one block at a time. only pick up unstack block if my hand is empty.
can only pick up block if the block is on the table and the block is clear. block clear if the block has no other blocks on top of it and if the block is not picked up.
I can only unstack block from top of another block if the unstacking
really top of the other block. can only unstack block from on top of another block the block I am unstacking is clear.
block
Once I pick up or unstack block, I am holding the block. can only put down a block that I am holding,
only stack block top of ancther block am helding the block being stacked.
I can only stack a block on top of another block if the block onto which I am stacking the block is clear.
Once put down or stack block, my hand becomes empty. Once you stack block on top is no longer clear.
second block, the second block
[STATEMENT]
As initial conditions have that, the red block is clear, the blue block is clear, the yellow block is clear, the hand empty, the blue block is on top of the orange block, the red block is en the table, the orange block is on the table and the yellow bleck is the table.
My goal is have that the red block the blue bleck is on top of the yellow block and the yel low block is on top of the orange block.
top the blue block,
My plan is follows:
[PLAN]
unstack the blue block from on top of the orange block stack the blue block top of the red block pick up the yellow block stack the yellow block on top of the orange block unstack the blue block from on top of the red block stack the blue block on top of the yellow block pick up the red block stack the red block on top of the blue block [PLAN AND]
[STATEMENT]
As initial conditions have that, the blue block is clear, the orange bleck is clear, the hand empty, the orange block is on top of the yellow block, the yellow block is on top of the red block, the red block is on the table and the blue block is the table.
39

---

Published as a conference paper at ICLR 2025
My goal is to have that the rea block on top the orange block, the blue block is on top of the red block and the yellow block is en top of the blue block.
My plan is as follows:
[PLAN]
-PT4-as-Plannee Respense unstack the orange block from top of the yellow block put down the orange block unstack the yellow block from on top of the red block stack the yellow block on top of the orange block pick up the blue black
stack the blue black on top of the red block unstack the yellow block from on top the orange block stack the yellow block on top of the blue block pick up the red block
unstack the blue block from top of the red block stack the blue block on top of the yellow block stack the red block on top of the orange block [PLAN END]
-a------V--iii Response
Plan is invalid. The plan fails because after you stack the blue block on top of the red block, you cannot unstack the yellow block from en top of the orange block because the yellow block is not clear. It has the blue bleck on top of it. Response
apologize for the oversight. Here is the corrected plan: [PLAN]
unstack the orange block from top of the yellow block put down the orange block
unstack the yellow block from on top red block put down the yellow block pick up the blue block
stack the blue block top of the red block pick up the orange block stack the orange block on top of the red block pick up the yellow block
stack the yellow block on top of the blue block [PLAN END
-ww--aa-veriiiieiee Response---...
Plan is invalid. The plan fails because after stacking the blue block on tep of the red block, you are trying to stack the orange block top of the red block. However, the red block is not clear because the blue block is top of it. Response-----
I apologize for the mistake. Here is the corrected plan:
[PLAN]
unstack the orange block from on top the yellow block put down the orange block unstack the yellow block from on top of the red block put down the yellow block pick up the blue block stack the blue block on top of the red block pick up the orange block stack the orange block on top of the blue block pick up the yellow block stack the yellow block on top the orange block [PLAN END]
-PT--a--Verifier Response
Plan is valid.
40

---

Published as a conference paper at ICLR 2025
A.5.5 LLM VERIFIER BLOCKSWORLD
Examples of LLM Output on the Verification Task
[STATEMENT]
As initial conditions have that, the blue block is clear, the orange black is clear, the hand is empty, the orange block is top of the yellow block, the yellow block is on top of the red block, the red block is on the table and the blue block is on the table.
My goal is to have that the rea block is top of the orange block, the blue block is top of the red block and the yellow block is en top the blue block.
My plan is as follows:
[PLAN]
-PT-4 Response-
unstack the orange block from on top of the yellow block put down the orange block unstack the yellow black from top of the red block stack the yellow block top the orange block pick up the blue block
stack the blue block on top of the red block unstack the yellow block from on top of the orange block stack the yellow block top of the blue block pick up the red block unstack the blue block from on top of the red block stack the blue block on top of the yellow block stack the red block on top of the orange block [PLAN END]
Plan is invalid. The plan fails because after you stack the blue Verifier Incorrect Respense
block en top of the red block, you cannot unstack the yellow plock from top of the orange block because the yellow block clear. it has the blue block top of it.
A.5.6 PROMPTS MYSTERY BLOCKKWORI.D
All of following examples are built on the same graph instance.
Baseline, Direct Prompt
am playing with set of objects. Here are the actions can
Attack object
Feast object from another object Succumb object Overcome object from another object
I have the following restrictions
actions:
To perform Attack action, the following facts need to be true: Province object, Planet object, Harmony. Once Attack action is performed the following facts will be true: Pain object.
Once Attack action is performed the following facts will be false: Province object, Planet object, Earmony.
To perform Succumb action, the following facts need be
true: Pain object.
Once Succumb action is performed the following facts will be
true: Province object, Planct object, Barmony.
41

---

Published as a conference paper at ICLR 2025
Once Succumb action is performed the following facts will be false: Pain object.
To perform Overcome action, the following needs to be true: Province other object, Pain object.
Once Overcome action is performed the following will be true: Harmony, Province object, Object Craves other object. Once Overcone action is performed the following will be false: Province other object, Pain object.
To perform Feast action, the following needs be true: Ooject Craves other object, Province object, Harmony. Once Feast action is performed the following will be true: Pain object, Province other object.
Once Feast action is performed the following will be false:, Object Craves other object, Province object, Harmony.
[STATEMENT]
As initial conditions I have that, object craves object b, object d craves object harmony, planet object b, planet object c, province object a and province object d. My goal is to have that object с craves object a.
My plan is follows:
[PLAN]
feast object d from object c succumb object
attack object
overcome object с from object [PLAN AND]
[STATEMENT]
As initial conditions have that, object craves object c, object с craves object d, object craves object a, harmony, planct object a and province object b. My goal is to have that object craves object a and object d craves object
My plan is as follows:
[PLAN]
Example LLM Response
feast object b from object
succumb object b attack object
overcome ob a from object feast object d from object a succumb object
attack object
overcome object from object [PLAN END]
Prompt To Elicit Verification (Open Ended)
playing with of objects. Here the actions
Attack object Feast object from another object Succumb object
42

---

Published as a conference paper at ICLR 2025
Overcome object from another object
have the following restrictions on actions:
To perform Attack action, the following facts need to be true: Province object, Planet object, Harmony, Once Attack action is performed the following facts will be true: Pain object.
Once Attack action is performed the following facts will be false: Province object, Planet object, Harmony. To perform Succumb action, the following facts need true: Pain object.
Once Succumb action is performed the following facts will be true: Province object, Planet object, Harmony.
Once Succumb actiion is performed the following facts will be false: Pain object.
To perform Overcome action, the following needs to be true: Province other object, Pain object.
Once Overcome action is performed the following will be true: Harmony, Prevince object, Object Craves other object. Once Overcome action is performed the following will be false: Province other object, Pain object.
To perform Feast action, the follewing needs to be true: Ooject Craves other object, Province object, Harmony. Once Feast action performed the following will be true: Pain object, Province other object.
Once Feast action is performed the following will be false:, Object Craves other object, Province object, Harmony.
[STATHMENT]
As initial conditions I have that, object b craves object c, object a craves object d, object d craves object harmony, planet object and province object b.
My goal is have that object craves object a and object craves object a.
My plan is as follows:
[PLAN]
feast object a from object succumb object a
attack object
overcome object irom object feast object с from object succumb object c attack object overcome object from object [PLAN END]
Verify whether the above plan is valid. If it is valid, please say "Plan is valid." and nothing clse. If it is invalid, please say "Plan is invalid, and then provide feedback on why the plan fails.
Prompt To Elicit Verification (Format based)
am playing with set of objects. Here are the actions can do
Attack object
Feast object from another object Succumb object Overcome object from another object
43

---

am playing with set of objects. Here are the actions can do Published as a conference paper at ICLR 2025
have the following restrictions en ny actions:
To perform Attack action, the following facts need to be true: Province object, Planet object, Harmony, Once Attack action is performed the following facts will be true: Pain object.
Once Attack action is performed the following facts will be false: Province object, Planet object, Harmony.
To perform Succumb action, the following facts need te be truc: Pain object.
Once Succumb action is performed the following facts will be true: Province object, Planct object, Harmony.
Once Succumb actioo is performed the following facts will be false: Pain object.
To perform Overcome action, the fol Fowlonnng needs Province other object, Pain object.
true:
Once Overcome action is performed the following will be true: Harmony, Province object, Object Craves other object. Once Overcome action is performed the following will be false: Province other object, Pain object.
To perform Feast action, the following needs to be true: Object Craves other object, Province object, Harmony. Once Feast action is performed the following will be true: Pain object, Province other object.
Once Feast action performed the following will be false:, Object Craves other object, Province object, Harmony.
[STATEMENT]
initial conditions have that, object craves object object d craves object c, harmony, planet object b, planet object province object a and province object d.
My goal is to have that object craves object My plan is follows:
[PLAN]
feast object d from object succumb object d attack object
overcome object a from object
[PLAN END]
Verify whether the above plan is valid. Provide JSON between tags [JSON] and [USONi_HND]] for the verificati on information. The JSON shculd contain three main keys: (1) "valid": binary value that tells if the plan is valid or not i.e., the plan when executed satisfies the geal conditions. If the plan is invalid and inexecutable then include "unmeti__reed "oauutttt_pcc This contains two more keys; (2.1) "action": This is the name of the first action that renders the plan inexccutable (2.2) "precenditions"; A 1ist of unmet preconditicns for the mentioned action; If the plan is
exccutable not goal reaching then include (3)
"unmet = list unmet goal conditions in the JSON. Include ude only one of the keys (2) or (3) based on the plan invalidity.
Prompt To Elicit Verification (Chain of thought based)
Attack object
Feast object from another object
44

---

Published as a conference paper at ICLR 2025
Succumb object
Overcome object from another object
have the following restrictions my actions:
To perform Attack action, the following facts need to be true: Province object, Planet object, Harmony. Once Attack action is performed the following facts will be true: Pain object.
Once Attack action is performed the following facts will be false: Prevince object, Planct object, Harmony, To perform Succumb action, the following facts need to be true: Pain object.
Once Succumb action is performed the following facts will be true: Province object, Planet object, Harmony.
Once Succumb action is performed the following facts will be false: Pain object.
To perform Overcome action, the following needs to be true: Province other object, Pain object.
Once Overcome action is performed the following will true: Harmony, Province object, Object Craves other object. Once Overcome action is performed the following will be false: Province other object, Pain object.
To perform Feast action, the following needs Ooject Craves other object, Province object, Harmony. Once Feast action is performed the following will be true: Pain object, Province other object.
true:
Once Feast action is performed the following will be false: Object Craves other object, Province object, Harmony.
[STATEMENT]
As initial conditions I have that, object craves object b, object d craves object c, harmony, planet object planet object c, province object a and province object d. My goal is to have that object с craves object a.
My plan is as follows:
[PLAN]
feast object d from object c succumb object
attack object
overcome object from object [PLAN BND]
Verify whether the above plan is valid. You will think step by step and cutput intermediate reasoning steps and thoughts for the verification after the [THOUGHTS] tag. Then, provide JSON between the tags [JSON] and DISO__END] for the verification information. The JSON should contain three main keys: If the plan is invalid and inexecutable then include (1) "unmet poamett__rccccntiooss"" This contains two "action": This is the name the first action that renders the plan inexecutable (1.2) "preconditions"; A iist of unmet preconditions for the mentioned action; If the plan is executable but not goal reaching then include (2)
keys; (1.1)
sunmet_goalle A list of unmet goal conditions in the JSON.
Finally include (3) "valid": a binary value that tells if the plan is valid or not i.e., the plan when executed satisfies the goal conditions. Include only one of the keys (1) or (2) based the type of plan invalidity.
Let's s think step by step [THOUGHTS]
45

---

Published as a conference paper at ICLR 2025
Prompt To Elicit Verification (Swapping Answer and Reason Order)
am playing with set of objects. Here are the actions can do Attack object Feast object from another object Succumb object
Overcome object from another object
have the following restrictions my actions:
To perform Attack action, the following facts need to be true: Province object, Planet object, Harmony. Once Attack action is performed the following facts will be true: Pain object.
Once Attack action is performed the following facts will be false: Province object, Planet object, Harmony, To perform Succumb action, the following facts need to be true: Pain object.
Once Succumb action is performed the following facts will be true: Province object, Planet object, Harmony.
Once Succumb action is performed the following facts will be false: Pain object.
To perform Overcome action, the follewing needs to be true: Province other object, Pain object.
Once Overcome action is performed the following will be truc: Harmony, Province object, Object Craves other object. Once Overcome action is performed the following will be false: Province other object, Pain object.
perform Feast action, the following needs Ooject Craves other object, Province object, Harmony. Once Feast action is performed the following will be true: Pain object, Province other object.
true:
Once Feast action is performed the following will be false:, Object Craves other object, Province object, Harmony.
[STATEMENT]
As initial conditions have that, object craves object b, object d craves object e, harmony, planet object planet object c, province object a and province object d. My goal is to have that object с craves object a.
My plan is as follows:
[PLAN]
feast object d from object c succumb object attack object
object from object [PLAN END]
Verify whether the above plan is valid. Provide a JSON between tags [JSON] and (USON_END) for the verification information. The JSON shculd contain three main keys: If the plan is invalid and inexecutable then include (1) "unmet praeee__pcccnn.ioon.... This contains two more keys; (1.1) "action": This is the name of the first actien that renders the plan inexecutable (1.2) "preconditiens""
1ist of unmet preconditions for the mentioned action; If the plan is executable but not goal reachime ng then incl ude (2) "anmet_goals"
ifst of unmet goal conditions in the JSON. Finally include (3) "valid"; a binary value that tells if the plan is valid not f.e., the plan when executed satisfies the goal conditions. Include only the keys (1) or (2) based on the type of plan invalidity.
46

---

Published as a conference paper at ICLR 2025
A.5.7 BACKPROMPTS MYSTERY BLOCKSWORLD
Backprompt Generated From Self-Critique
Plan is invalid.
The first action "Least object b from object o" is not possible pecause the initial conditions do not include "Province object b" which is required for the Feast action.
Backprompt Generated From Sound Verifier (First)
The above plan is invalid.
The following action step has unnet precondition: attack object The unmet precondition is: province object a
Backprompt Generated From Sound Verifier (Full)
The above plan is invalid.
There is an unmet goal condition. This is: object craves object There are unsatisfied preconditions.
The following action at step 3 has an unmet precondition: attack object
The unmet precondition is: province object
The following action at step 5 has an unmet preconditions feast object d from object a The unmet precondition is:
province object
A.5.8 COMPLETE EXAMPLE OF ITERATIVE PROMPT SEQUENCE -YSTERRY BLOCKSWORLD
Full Sequence of 15 (ene--eee) Backprompts
am playing with set of objects. Here are the actions can do
Attack object
Feast object from another object Succumb object
Overcome object from another object
have the following restrictions my actions:
To perform Attack action, the following facts need be true: Province object, Planet object, Harmony. Once Attack action is performed the following facts will be true: Pain object.
Once Attack action is performed the following facts will be false: Prevince object, Planet object, Harmony.
To perform Succumb action, the following facts need to be true: Pain object.
Once Succumb action is performed the following facts will be true: Province object, Planet object, Harmony.
Once Succumb action is performed the following facts will be false: Pain object.
To perform Overcome action, the following needs to be true: Province other object, Pain object.
47

---

Published as a conference paper at ICLR 2025
Once Overcome action is performed the following will be true: Ha Harmony, Prevince object, Object Craves other object. Once Overcome action is performed the following will be false: Province other object, Pain object.
To perform Feast action, the following needs Object Craves other object, Province object, Harmony. Once Feast action is performed the following will be true: Pain object, Prevince other object.
true:
Once Feast action is performed the following will be false;, Ooject Craves other object, Province object, Harmony.
[STATEMENT]
As initial conditions have that, object craves object b, object d craves object c, harmony, planet object b, planet ooject e, province object a and province object d. My goal is to have that object a craves object a.
My plan is follows:
[PLAN]
feast object d from object succumb object
attack object
overcome object с from object
[PLAN END]
[STATEMENT]
initial conditions have that, object craves object c, object с craves object d, object d craves object a, harmony, planet object a and province object b.
My goal is to have that object craves object and object d object
My plan is as follows:
[PLAN]
-at.------7-----aaaaaa Response
feast object b from object c succumb object b attack object
overcome object irom object feast object d from object succumb object
attack object overcome object from object [PLAN END]
a---------------iieee Verrifier Response
Plan is invalid.
The first action "feast object b from object e" is not possible because the initial conditions not include "Province object b" which is required for the Feast action.
-.w.------------aaeae Response---.......
apologize for the oversight. lit's correct the plan.
[PLAN]
attack object a succumb object feast object b from objest
overcome object с from object attack object
succumb object
feast object a from object
48

---

Published as a conference paper at ICLR 2025
overcome object from object [PLAN BND] -at..---------------i-eeee Response
Plan is invalid.
The first action "attack object a" cannot be performed because the conditions for the attack action are not met According to the restrictions, to perform an attack action, the following facts need to be true: Province object, Planet object, Harmony, the initial conditions, you have Province object b, not Province object a. Therefore, the attack action cannot be performed en object a.
GPT4-as-Planner Response
apologize for the confusion. let's revise the plan.
[PLAN]
attack object b succumb object feast object с from object overcome object d from object attack object a succumb object
feast object d from object overcome object a from object [PLAN END]
-----PT--as---ri--a Response
Plan is invalid.
The first action "attack object b" cannot be performed because the conditions for the attack action are not met. The attack actior requires the facts: Province object, Planet object, Harmony to true. In the initial conditions, you have Province object and Harmony, but you do not have Planet object. Therefore, the attack acticn cannot be performed.
Response----..
apologize for the confusion. Let's revise the plan.
[PLAN]
feast object b from object c succumb object b attack object
overcome object from object feast object a from object succumb object
attack object overcome object from object [PLAN END]
-P------------iiicce Response
Plan is invalid.
The first action "feast object from object e" cannot performed because the initial conditions do not satisfy the requi rements for the Feast action. According to the rules, to perform Feast action, the fol following needs to be true: Object Craves other object, Province object, Harmony. In the initial conditions, object craves object c, harmony, and province object b are true. However, the Feast action requires that the object perferming the action (object b in this case) is the Province object, which is not the case in the initial conditions. Therefore, making the plan invalid.
first action cannot performed,
-aw-----------aa-aaaaaa- Response----
apologize for the confusion. Let's revise the plan.
49

---

Published as a conference paper at ICLR 2025
[PLAN] attack object b succumb object b feast object с from object overcome object from object feast object a from object d succumb object
attack object
overcome object e from object [PLAN END]
- Response
Plan is invalid.
The first action "attack object b" is valid because the initial conditions meet the requirements for the attack action. However, the second action "succurb object b" is invalid because the "Pain object" fact is not true after the first action. The "Attack object b" action makes the "Pain object" fact true, but it also makes the "Province object" fact false, which is requirement for the "Succumb" action. Therefore, the plan fails at the second actien.
-aw.------7------aaa--a Response
apologize for the confusion. Let's revise the plan.
[PLAN]
attack object b succumb object feast object с from object d
overcome object d from object feast object a from object d succumb object
attack object
overcome object с from object
[PLAN END]
-.._=_..---G------ S8T4-as-Verifta Response
Plan is invalid.
The first action "attack object b" is valid because the initial conditions meet the requirements for the attack action: Province object, Planet object, Harmony.
However, the second action "succumb object b" is invalid. The succumb action requires the fact "Pain object" to be true, which is achieved after the attack action. But the object for the succumb action should be the attacked, which not the case in your plan.
the object that
The rest of the plan cannot be validated because it depends the outcome of the invalid succumb action.
Response---..--
apologize for the confusion. Let's revise the plan.
[PLAN]
attack object
succumb object
feast object b from object o overcome object с from object attack object
succumb object feast object a from object overcome object d from object [PLAN END]
50

---

Published as a conference paper at ICLR 2025
- Response
Plan is invalid.
The plan fails the first step "attack object b". Accerding to the rules, to perform the Attack action, the following facts need to true: Province object, Planet object, Harmony. the initial conditions, you have Province object b, Planet object and Harmony. However, for the Attack action, you need the same object for Province and Planet, which is not the case here. Therefore, you cannot perforn. the Attack action on object b.
Planees Response Response
apologize for the confusion. let's s revise the plan.
[PLAN]
attack object a succumb object feast object b from objest overcome object с from object attack object a succumb object
feast object a from object d overcome object from object [PLAN END]
-------------------- Response
Plan is invalid.
The first action "attack object cannet be performed because the initial conditions do not meet the requi rements for the attack action. The attack action requires the facts: Province object, Planet object, Harmony to be true. In the initial conditions, the Province object object not object a. Therefore, the attack actien cannot be performed on object a. -a------------------------
Response-----..
apologizc for the confusion. Let's revise the plan.
[PLAN]
attack object
succumb object
feast object a from object b overcome object b from object attack object
succumb object
feast object с from object d overcome object d from object [PLAN END]
www.-GTT----eiiii..... Response
Plan is invalid.
The first action "attack object d" cannot be performed because the conditions for the Attack action are not met. According to the rules, to perform the Ättack action, the following facts need to be true: Province object, Planet object, Harmony. In the initial conditions, you have Province object b, Planet object a, and Harmeny. However, you trying to attack object not opject a or b. Therefore, the first action your plan is not valid.
-ra-----aar----lllannee Response---...
apologize for the confusion. Let's revise the plan.
[PLAN] attack object b succumb object b
51

---

Published as a conference paper at ICLR 2025
feast object b from object overcome object c from object attack object
succumb object
feast object a from object overcome object from object [PLAN END]
Response
Plan is invalid.
The first action "attack object b" is invalid because the conditions for the attack action are not met The conditions for the attack action are: Province object, Planet object, Harmony. the initial conditions you have Province object b, Planet object a, and Harmony. The Province object and Planet object must be the same for the attack action to be valid. Therefore, you cannot attack object b with the given initial conditions.
-aa---a------------PP--aa-- Response--.....
apologize for the confusion. Let's 8 revise the plan. [PLAN]
feast object from object succumb object attack object a overcome object a from object feast object a from object d succumb object
attack object c
overcome object c from object [PLAN END]
Response
Plan is invalid.
The first action "feast object from object b" is not possible because the initial conditions state that "object b craves object c", "object craves object a". Therefore, the Feast action cannet be performed as the condition "Object Craves other object" is not met.
The plan fails the first step. -aw.-------17----aP1aaaa kesponse
apologize for the confusion. Let's s revise the plan.
[PLAN]
feast object d from object succumb object attack object d overcome object d from object feast object from object succumb object
attack object c overcome object a from object [PLAN END]
Response-
Plan is invalid.
The first action "Seast object á from object a" cannot be performed because the initial conditions do not satisfy the requirements for the Feast action. The Feast action requires that the object performing the action (in this case, object d) craves the other object (in this case, object a). However, the initial conditions state that object d craves object not the
52

---

Published as a conference paper at ICLR 2025
other way around, Therefore, the Feast action cannot be performed, and the plan is invalid.
-a1---------------1---- Kesponse--- apologize for the confusion. Let's revise the plan.
[PLAN]
feast object a from object b succumb object
attack object
overcome object a from object feast object с from object d succumb object
attack object
overcome object from object [PLAN END
-a--- Response Plan is invalid.
The first action "feast object a from object b" cannot be performed because the initial conditions state that "object b craves object c", not "object a". Therefore, the Feast action cannot be performed as it requires the fact "Object Craves would be "object
other object" to be true, which in this craves object a", -P--------A------aaaaae--- Response----.
I apologize for the confusion. Let's s revise the plan.
[PLAN]
feast object d from object c succumb object attack object d overcome object irom object feast object a from object succumb object attack object
overcome object from object [PLAN END]
-a-----------iiieeee Response--.
Plan is invalid.
The first action in your pian, "feast object from object c", cannot be performed because the initial conditi ti include "Object craves object c". The initial conditions state that "object b craves object c, object с craves object d, object d craves object a". Therefore, the first action in your plan is not valid according the restrictions the Feast action.
-aw.----aaaaa-aae Response---a
I apologizc for the confusion. Let's s revise the plan.
[PLAN]
feast object a from object
succumb object
attack object overcome object from object feast object e from object succumb object c attack object c overcome object from object [PLAN END]
-.---r-aaa--eiiiice Response
Plan is invalid.
53

---

Published as a conference paper at ICLR 2025
The first action in your pian, "feast object from object d", cannot be performed because the initial condit tintiions do not include "Object craves object d" According to the rules, to perform the Feast action, the following needs to be true: "Object Craves other object, Province object, Harmony", In your initial conditions, you have "Object b craves object c, Object a craves object d, Object d craves object a, Harmony, Planet object and Province object b". Therefore, you cannot perform the Feast action object from object d your first action.
A.5.9 LLM AS VERIFIER MYSTERY BLOCKSWORLD
Examples of LLM Output on the Verification Task
-amesse=Cuureet State=
object craves object e, object craves object d, object d craves object a, harmony, planet object and province object b.
Plan is invalid.
The first action "Seast object from object a" not possible because the initial conditions do not include "Province object b" which is required for the Feast action. -o
Plan is invalid.
The first action "Seast object b from object a cannot be performed because the initial conditions do not satisty the requirements for the Feast action. According to the rules, to perform Feast action, the following needs to be true: Object Craves other object, Province object, Ha Harmony. In the initial conditions, object b craves object c, harmony, and province object b are true. However, the Feast action requires that the ooject performing the action (object b this case) is the Province object, which not the case conditions. Therefore, the first action cannot be performed, making the plan invalid.
initial
Plan is invalid.
The first action "attack object b" is valid because the initial the requi rements for the attack action: Province object, Planet object, Harmony.
conditions
However, the second action "succumb object b" is invalid. The succumb action requires the fact "Pain object" to be true, which is achieved after the attack action. But the object for the succumb action should be the same as the object that was attacked, which is not the case in your plan.
The rest of the plan cannot be validated because depends the outcome the invalid succumb action.
54


Reviews:
[{"review_id": "yblzn2VuSB", "reviewer": "Reviewer_Dj2B", "summary": "The paper evaluates the self-verification abilities of LLMs in reasoning and planning tasks using iterative prompting and critiquing. It contrasts the performance of LLMs self-verifying their solutions against external sound verifiers across three domains: Game of 24, Graph Coloring, and STRIPS planning. Findings indicate that LLMs underperform in self-verification and that external sound verification significantly improves the accuracy of solutions. The study suggests the ineffectiveness of self-critique mechanisms in LLMs and recommends integrating external verifiers for better performance in reasoning tasks.", "questions": "1. How do the authors anticipate their findings will generalize to other complex reasoning tasks not covered in the study? Can the observed ineffectiveness of self-critique mechanisms be extrapolated to different types of LLMs or reasoning models? \n2. Could the authors elaborate on the choice of domains for the study? Why were these specific domains chosen, and how do they represent the broader spectrum of reasoning tasks applicable to LLMs? \n3. What additional mechanisms or modifications do the authors suggest could potentially improve the self-verification capabilities of LLMs? Is there ongoing work to develop more effective internal critique mechanisms within LLMs? \n4. How do the authors envision the impact of their findings on the future development and deployment of LLMs in safety-critical applications? What precautions or additional measures would they recommend based on their study’s outcomes?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses a novel aspect of LLMs—self-critique and iterative verification—that is underexplored in the existing literature. It challenges the assumption that LLMs can effectively self-critique by demonstrating that external verification offers more reliable improvements. \n2. The experimental setup is clearly described, allowing for reproducibility and understanding of how iterative prompting affects LLM performance in reasoning tasks. The paper methodically outlines its methodology and the rationale behind using specific domains for testing (Sections 4 and 3). \n3. The findings significantly contribute to understanding LLM limitations in self-verification tasks, which is critical for deploying these models in real-world applications where accuracy and reliability are paramount. \n4. The study is well-structured and robustly empirically analyzed, providing a comparative assessment of LLMs with and without external sound verifiers.", "weaknesses": "1. The paper’s focus on only three specific domains might limit the generalizability of the findings. While these domains are relevant, more varied tasks could provide a broader understanding of LLM capabilities across different reasoning types (Section 3). \n2. The analysis of the self-critique mechanism lacks depth regarding why LLMs fail at self-critique. Specific instances of LLM outputs and their failures would enrich the discussion by pinpointing the flaws in LLM reasoning strategies (Section 5.1). \n3. There is no detailed discussion on the computational cost and efficiency of using external verifiers versus self-verification. This information would be crucial for practical implementations where resource constraints are a significant consideration. \n4. The paper does not thoroughly explore the theoretical implications of its findings on the computational complexity theories surrounding LLMs and self-verification. A deeper theoretical analysis could provide insights into the fundamental limitations of LLM architectures (Section 2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dxKJW2BGu1", "reviewer": "Reviewer_R3Bw", "summary": "This is an experimental paper studying the the popular technique of self-verification of LLMs for enhancing apparent reasoning capabilities. The stringent experimental protocol shows that the self-verification does not really work and shows that other techniques like using formal (symbolic) verifiers are better suited to achieve automated reasoning with LLMs.", "questions": "See point 2) in weaknesses and more specifically: are there any arguments that the findings do not only hold for the examined LLMs but in general for transformer-based auto-regressive models, or even other models like discrete diffusion models.\n\n\nMinor comment:\nThe use of \\citep and \\citet is not correct. Also there are some small spelling/typesetting issues here there that should be easily fixable.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The paper is really well written and easy to to follow. The non-technical nature might have helped here. \n2) I enjoyed reading the (extensive) related work section where problems in prior work are made explicit.\n3) All claims made in the paper are substantiated by appropriate experiments.", "weaknesses": "1) For someone familiar with the field the findings might be a little bit obvious. However, given the amount of papers being published using self-verification, I nevertheless believe this to be an important study when it comes to combating the delusion of self-verification.\n\n2) Given that this is an experimental study it might be good to also point out weaknesses in the experimental protocol. Specifically, making explicit all the assumptions that were made and what might change if they were not to hold. Concretely, what gives the authors the confidence that their findings have a high probability of standing the test of time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cOxUsPOAnJ", "reviewer": "Reviewer_NPSN", "summary": "This paper discusses the effect of self-verification in LLM reasoning and planning, challenging the assumption that verifying correctness is easier than generating solutions. Through experiments in three domains (Game of 24, Graph Coloring, and STRIPS planning), it finds that self-verification does not improve accuracy and can even reduce performance. In contrast, a \"sound external verifier\" significantly enhances accuracy, with simpler re-prompting methods maintaining most of these benefits.", "questions": "Please discuss the points mentioned in the weakness part.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The presentation and writing are clear.\n2. The authors made adjustments to the test datasets to ensure their validity. For example, they generated new instances to prevent test set memorization and modified the task solution format to better evaluate the self-verification pipeline.\n3. The systematic analysis of self-verification provides insights into the cases where the verification module can help improve LLM performance.", "weaknesses": "1. The experiment design is not entirely persuasive.\nThe authors attempt to challenge the assumption that verifying correctness is easier than generating solutions, suggesting that self-verification does not improve performance. However, task difficulty should be considered. Apart from Blocksworld, the accuracy in other tasks is quite low. According to Table 2, \"LLM Verification Results,\" verification performance varies across tasks, especially in terms of the False Negative Rate (FNR). In Blocksworld, which has the lowest FNR, self-verification actually improves task accuracy from 40% to 55%. This suggests there are cases where verification is easier than generation and where self-verification contributes positively to task accuracy. More tasks should be added for more comprehensive results.\n\n2. The authors use a “sound” verifier as a comparison, but it’s unsurprising that a ground-truth verifier significantly improves performance. With ground-truth verification, the model can eliminate incorrect answers and focus on sampling correct ones, or at least provide ground-truth information. Taking the first point into account, a more nuanced conclusion could be that in tasks where verification is easier than generation, self-verification helps; otherwise, it has no benefit or even harms performance. The improvement limit for self-verification is thus bounded by the effectiveness of the “sound” verifier. \n\n3. The exact GPT version should be specified, and more models, particularly advanced ones, should be tested for comprehensive results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vwRenDRUvP", "reviewer": "Reviewer_jfRh", "summary": "This paper mainly evaluates the self-critique and verification capabilities of LLMs in comparison to sound verifiers. It concludes that the self-verification loop conducted by LLMs is not as helpful as previous works claimed. On the contrary, it might hurt LLM performance in some planning domains.", "questions": "I don't have more questions but authors are encouraged to address my concerns in the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper has the following strengths.\n\nOriginality:\nThis paper systematically evaluates LLMs' self-verification capability by careful ablation and comparison to symbolic processors. It finds that LLM verification is not very helpful in some planning cases. This is novel and interesting.\n\nQuality:\nThis paper considers problems of memorization and lack of ground truth during evaluation, which are important concerns.\n\nClarity:\nThe experiment setup is quite clear.\n\nSignificance:\nKnowing what LLMs are actually doing when people claim they can do a lot of things is very important.", "weaknesses": "1. Is it fair to compare LLMs with oracle verifiers? The finding that LLM self-critique can sometimes downgrade their generation performance is interesting, but oracle processors are not always accessible in all tasks (as the authors mentioned in their paper, some tasks such as creative writing do not have a ground truth answer). I'm not surprised that oracle verifier is improving LLM performance, but I wonder if it is possible that LLM can serve as a decent alternative when sound verifier is absent in general areas?\n\n2. The task domains are constrained while the general conclusion is very strong. The authors evaluated three main planning tasks and one LLM (GPT-4) with four datasets, with no clear objective as to why the conclusion drawn from these three specific tasks can be generalized. It is unclear why these tasks and datasets can represent general LLMs' lack of self-verification capability in a wide ranges of tasks.\n\n3. Some other details in this paper are also overclaimed, e.g., on page 2, the authors claim \"...the state-of-the-art GPT-4\" while GPT-4 is not SotA in many benchmarks anymore (in [1], inter alia).\n\n4. There are quite some typos. Writing needs to be done with more care.\n\n[1] Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., ... & Ganapathy, R. (2024). The llama 3 herd of models. arXiv preprint arXiv:2407.21783.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)