On the self-verification limitations of large language models on reasoning and planning tasks

We sincerely appreciate reviewer jfRh for their feedback. Below, we provide clarifications in response to the major concerns raised in the review.

Choice of domains:

We would like to first point out that our work’s primary aim is to caution the community on using LLM self-verification methods for reasoning tasks. As mentioned in our related work section, we believe that reasoning is a fraught term. In previous work it has been unclear as to what definition of reasoning the works presuppose when making claims about LLM reasoning capabilities. Due to these shifting definitions and implicit assumptions, making concrete claims or pinning them down becomes a lot more difficult. This is why we restrict ourselves to focus on fully specified, verifiable problems that can be solved by deductive methods and have oracle verifiers. This allows us to check the quality of both binary verification and critique generated by the LLM. Furthermore, the algorithmic abilities these domains test are fundamental—any other reasoning task must include components that test these same capabilities, or else be only a retrieval task. We have made this explicit in the introduction section of the revised version of the paper.

Our results show that using LLMs as verifiers and within a self-verification loop is harmful in general and much more care should be taken when deploying LLMs in such a loop, specifically in reasoning tasks. Per our conclusion, we expect our results to be applicable to many overall ambiguous and complex tasks, because partial verifiers can be constructed and used together. Most real-world tasks contain a mixture of formally verifiable and tacit aspects. For example, see the TravelPlanning benchmark which combines “hard” and “soft” critics of LLM-generated plans. Or consider linters, unit tests, etc in software development.

While we reported all our experiments on GPT4, our partial empirical studies with other LLMs (as shown in the table below), including GPT-4o, have largely been in line with the results we reported on GPT4. Nevertheless, we are currently in the process of replicating the experiments on LLaMA, and hope to have the results incorporated before the end of the discussion period, but certainly for the camera-ready version.

Oracle verifiers

The oracle case is useful because it allows us to carefully and systematically ablate the self-verification system. Note that there are two components to the oracle case: the sound verification which is an external system that ensures that any output is guaranteed correct, and the sound feedback which can be passed back to the LLM in part or in whole. In section 5.2, we use this distinction to test how much of the increased improvement is due to the LLM itself conditioning on both the claim that the answer is incorrect and the feedback passed back. What we find is that it doesn’t seem to matter much. When we remove the feedback entirely, we retain most of the performance improvement. This further shows that previous claims that LLMs improve because they effectively take in feedback are misleading.

Thank you for your thoughtful comments and especially the recognition that our experimental study sheds considerable light on if and when self-verification can be helpful.

Unfortunately however, the rest of the review suffers from two serious misunderstandings of the paper–that we bring up and clarify below.

In weakness 1 you say:

The authors attempt to challenge the assumption that verifying correctness is easier than generating solutions, suggesting that self-verification does not improve performance

We are afraid that this interpretation is off the mark. Our paper is not concerned with the question of whether or not verification is easier than generation. We specifically choose tasks on which we know that verification is easier than generation. Formalizing this in terms of complexity theory, across all these tasks, generation is in a higher complexity class than verification. Proposed solutions can be verified in polynomial time, but generating these solutions is NP-complete (graph coloring) or even PSPACE-complete (planning).

What we challenge instead is the prevailing wisdom that LLMs are somehow sensitive to the lower computational complexity of verification. We argue that there is no reason to believe that LLMs will be better at verification than generation. Specifically, we challenge the claim that in these scenarios LLMs can verify proposed solutions better than they can generate them, and thus robustly bootstrap their performance to higher levels.

Our results indeed validate our belief/hypothesis, and show that—in fact—the gains seen in previous studies may be worse than illusory: in many cases, we see performance worsen with LLM self-critiques.

Continuing on, the reviewer says

more nuanced conclusion could be that in tasks where verification is easier than generation, self-verification helps

As you can see from the clarification above, the paper in fact showcases the opposite of the reviewer’s proposed conclusion!

About the concern that we are testing on benchmarks where the LLM accuracy is not very high to begin with

However, task difficulty should be considered. Apart from Blocksworld, the accuracy in other tasks is quite low.

We would argue that in practice, self-verification is most useful when base performance is low, which reinforces the validity of our testing on tasks that range from 4 to 40% standard prompting accuracy. Some of the previous studies have focused on tasks on which LLM performance is already very high, sometimes as high as 98%--which makes the whole evaluation of effectiveness of self-verification a moot point.

We specifically chose a set of tasks where the initial accuracy of LLMs is low to begin with, in order to gain more significant resolution in our analysis of how much the self-verification scheme does or does not improve. Note that,

With ground-truth verification, the model can eliminate incorrect answers and focus on sampling correct ones, or at least provide ground-truth information.

Our paper also addresses this point. As we discuss, ground-truth verification is providing two things: 1) an external system that decides whether an answer is correct and thus outputs it only if it is guaranteed and 2) some feedback to the LLM in the form of a backprompt. The claim that the model is itself eliminating incorrect answers is also tested—we compare ground truth verification with all, some, or even zero critique given in section 5.2. We find that, in fact, we can gain most of the performance improvement without providing anything about the previous wrong answers to the model! This indicates that the performance improvements seen are mainly from rejection sampling the model, rather than from any inherent LLM ability to “focus on sampling correct ones” when given feedback.

The improvement limit for self-verification is thus bounded by the effectiveness of the “sound” verifier.

A sound verifier will, by definition, perfectly discriminate between correct and incorrect answers. The term “sound” here is borrowed from mathematical logic, where it essentially means that a system preserves truth. It is one of a desirable pair of properties for a system that together guarantee it will output all and only correct answers. The other property is completeness, which, in this case, would apply to the LLMs (are they capable of guessing all plausible solution candidates?). In general, such completeness is not guaranteed (as we discuss, approaches like ToT can be seen as externally inducing LLMs to generate a diverse set of candidate solutions through prompt diversification).

Completeness would require that, for any problem of interest, the LLM would eventually output the correct answer (even if this answer were low probability and thus unlikely). However, even when we sample 150 answers per prompt in the case of Game of 24 (mentioned in A.2), the LLM only approaches 70% accuracy, and this accuracy asymptotes sharply. In short, we argue that it is not the effectiveness of the verifier that limits the improvement, but the incompleteness of the LLM.

Finally, the issue of availability of sound verifiers is not as insurmountable as the reviewer seems to think it is. Most LLM verification systems are indeed tested on tasks where they already have external sound solvers/verifiers to provide synthetic data with correct verification labels.

Furthermore, there are works in the literature (e.g. [1]) that show how verifiers can be teased out from the LLMs themselves with partial help of human or automated critics. Another idea is to learn verifiers from synthetic labeled data and use them to verify solutions.

The point of our work is to show that LLMs, out of the box, are no better at verification than generation.

[1] Guan, Lin, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. "Leveraging pre-trained large language models to construct and utilize world models for model-based task planning." Advances in Neural Information Processing Systems 36 (2023): 79081-79094.

[2] Zhang, Lunjun, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. "Generative verifiers: Reward modeling as next-token prediction." arXiv preprint arXiv:2408.15240 (2024).

The exact GPT version should be specified and more models

Thank you for pointing this out. The exact model snapshot was GPT-4-0613. We have made this explicit in the revised version of the paper. While we reported all our experiments on GPT4, our partial empirical studies with other LLMs (as shown in the table below), including GPT-4o, have largely been in line with the results we reported on GPT4. Nevertheless, we are currently in the process of replicating the experiments on LLaMA, and hope to have the results incorporated before the end of the discussion period, but certainly for the camera-ready version.

We thank reviewer Dj2B for their valuable comments. We are gratified that the reviewer found our work to be novel, significant and well-structured. Here are some clarifications for the concerns raised.

Choice of domains and applicability of results:

We would like to direct the reviewer to lines 139-174 and in particular to the following:

In the current work we address this by restricting our focus to fully specified, formally verifiable problems which can be solved directly by deductive methods. Though these may at first seem like a very narrow class, especially when compared to the cornucopia 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–otherwise they are merely testing recall.

Furthermore, we specifically chose domains on which the classical argument mentioned in line 53 holds. To clarify what we mean by this: Our domains all have the property that it is easier to check potential answers than it is to generate correct ones. Formalizing this in terms of complexity theory, generation is in a higher complexity class than verification. This holds true for all our tasks, over which verification is polynomial, but generation is NP-complete or even PSPACE-complete! [1,2]

What should be surprising here is that, despite this gap in the computational complexity of verification versus generation, using the LLM as a verifier is just as brittle and inaccurate as using it just to guess solutions.

In other words, previous claims that LLMs can bootstrap themselves on arbitrary problems are misleading and not robust, even when the playing field is skewed in their favor. Even worse, we've shown that the LLM self-verification loop can in some cases significantly decrease performance.

Finally, we expect our conclusions to be applicable to many overall ambiguous and complex tasks, because partial verifiers can be constructed and used together. Most real-world tasks contain a mixture of formally verifiable and tacit aspects. For example, see the TravelPlanning benchmark [3] which combines “hard” and “soft” critics of LLM-generated plans. Or consider linters, unit tests, etc in software development.

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?

In our view, verification/critique mechanisms can provide three things: a (potentially inaccurate) binary signal about correctness, feedback that hopefully elicits the correct answer, and guarantees over the output of the complete system. While the first two can be improved either with customized pre-training/fine tuning that is most relevant to the task, they would remain brittle and sensitive to minor distributional shifts despite them being semantics-preserving. The third–giving guarantees on verification status–will be out of reach for pre-trained systems.

While LLMs may improve on the first points over time, especially within domains that are well-represented in synthetic training data geared towards verification, their nature as uninterpretable black boxes precludes them from fulfilling the final role. Even when we intuitively think we have a grasp on how they fare on some problem class, they may in fact just be learning brittle distributional features that eventually fail in novel situations [4].

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?

The self-critiquing limitations of LLMs are of particular danger in safety-critical applications–where the system might send out a potentially incorrect solution for deployment. As we discussed in the conclusion and introduction, we believe that verification should be offloaded to sound systems when feasible, and LLMs should not be trusted in their current form in other scenarios without significant oversight.

Most complex tasks contain a mixture of explicitly verifiable and tacit aspects. We believe that partial verifiers can be constructed and used together for such problems [5]. Any sort of LLM verification must be tested thoroughly as there are cases like the ones we’ve shown where they actually worsen performance.

Thank you for the encouraging review; we are gratified that you see the importance of the contribution.

Regarding your question about the generality of the experiments, and whether we think they will stand the test of time on other LLMs: We believe that all autoregressive LLMs trained via teacher forcing–which is basically all the LLMs since GPT2–will have fundamental limitations on reasoning tasks (a fact that is being appreciated more widely thanks to several critical studies). In the end, verification is a reasoning task as much as generation is–and thus we are confident that our experimental results will hold on all such LLMs.

While we reported all our experiments on GPT4, our partial empirical studies with other LLMs (as shown in the table below), including GPT-4o, have largely been in line with the results we reported on GPT4. Nevertheless, we are currently in the process of replicating the experiments on LLaMA, and hope to have the results incorporated before the end of the discussion period, but certainly for the camera-ready version.

The use of \citep and \citet is not correct. Also there are some small spelling/typesetting issues here there that should be easily fixable.

We’ve fixed the citet/citep issue, as well as updating the typesetting and fixing a few commas in the revised version. Thank you for pointing this out!