Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification

Thank you for your review.

The main contribution of the paper.

We view our main contribution as showing that scaling search with self-verification works on frontier models and providing an explanation for why: implicit scaling. While it may seem obvious that “increasing verification samples leads to higher accuracy”, many papers (including Snell et al.) have studied self-consistency and self-verification and attempted to scale them up, but none have reported the same success. In fact, we aren’t aware of any prior works that have successfully applied self-verification to frontier models in a way that actually beats self-consistency. Instead, to beat self-consistency, the field has turned to training process-based reward models, using RL to learn verifiers, and other complicated interventions. “Increasing verification samples” sounds like a simple panacea but making it work is a different matter.

This has led to a general belief that simple self-verification isn’t enough, whereas we show that it is—you just need to hit a certain threshold of scale and obey some important principles. It's also noteworthy that direct self-verification can successfully and reliably extract o1-level performance from a non-reasoning model without any finetuning, distillation, RL, or custom-trained verifiers (again, no other works/methods—verification-based or otherwise—have achieved this).

We therefore respectfully, but strongly disagree with the assessment that “the key problem is what is the optimal allocation between the two factors given a limited compute budget”; prior to this work, it wasn’t even known that near-unbounded compute budget is sufficient to recover o1-level performance without interventions like RL.

“The difference with Snell et al., 2024.”

Our paper differs from Snell et al. in several important ways. First, we study entirely different questions: Snell et al. asks what the optimal test-time scaling trade-off is between pretraining versus inference-time scaling; we ask what the scaling trends and limits of sampling with self-verification are. Second, we study qualitatively different regimes: making verification improve on self-consistency is easy when trying to improve e.g. MATH performance from 10-40% (as is done in Snell et al. 2024); making verification improve on self-consistency on the last 90% of MATH or on actually challenging benchmarks like AIME is significantly more difficult (we aren’t aware of any works prior to ours that were able to do so without RL). Third, Snell et al. 2024 trains a process-based verifier reward model; we show that direct self-verification works fine.

“The benchmark consists of only responses from Gemini-1.5-pro. I think it is insufficient to evaluate frontier models.”

Gemini 1.5 Pro-002 was released in September 2024, making it one of the main frontier models at the time of this submission. Our paper also includes results on Gemini-1.5-Flash (a significantly smaller model with major qualitative differences) in Appendix B.1. We also note for context that the Snell et al. 2024 paper ran experiments only on the Palm-2 model and on a single benchmark (MATH).

Omit questions that Consistency@200 answers correctly to reduce noise. It might also change the results.

On MATH for example, 98% of “ambiguous questions” are easy questions that Consistency@200 answers correctly and hence Verification@200 answers correctly. When we plot Figure 2 without omitting these questions, we end up with a line that goes from 98% to 99% which entirely misses the point of the plot (which is to highlight implicit scaling). To fulfill the reviewer’s request, we will include an analog of Figure 2 in the Appendix where Consistency@200 filtering is not done. However, no trends change. For example, on AIME, Consistency@200 only gets 1-2/15 questions correct—omitting those questions has no material impact on the trends observed in Figure 2.

MATH trend on Figure 2.

Increasing the number of generated samples makes verification on ambiguous questions harder; this follows from basic probability: if you allow students more attempts at an exam, the average pass-rate of a student who passes at least one exam decreases. Similarly, as you increase the number of attempts, the average number of correct attempts/question decreases. Thus, if implicit scaling didn’t exist, all lines in Figure 2 should be strictly decreasing. The fact that we observe the opposite proves that implicit scaling must be happening. The fact that there is a 63->61% drop on the right-hand side of the MATH plot is not evidence against this and is—if anything—expected: we can’t expect implicit scaling is universally powerful enough to completely reverse the natural bias of increasing verification difficulty.

Thank you for your review! We address your questions/comments below.

“I would suggest the authors to also report the token consumption of baselines (e.g., Consistency@k) as well for a more fair comparison”.

We appreciate the suggestion and agree it would be useful. As our focus was identifying broader scaling trends rather than computational efficiency, we chose to study a minimalist implementation of sampling-based search that leaves significant room for optimization e.g. via prompt caching, delegated search, small verifiers, etc.—all exciting directions for future work as the reviewer has accurately noted.

Algorithm 1

We appreciate the feedback and will revise the algorithm description accordingly. The notation 1[is correct] would indeed benefit from clarification.

Adding analyses of R1/R1-Zero models.

This is a great suggestion and something we hope to do. Unfortunately, since R1 was released only 3 days before the ICML deadline, we were unable to include an analysis in this submission but agree that it’s valuable to analyze R1’s sampling-based search trends.

On Table 4

Table 4 depicts the implications of ablating the rewriting step from the verification process, showing a significant drop. We include in Appendix 3 a few examples of the outcomes of the rewriting step, which illustrate the rigor and structure that result. We will add a more detailed discussion to this effect as well.

Thank you for your review.

To address your comments on “predictability”: Many papers have studied self-consistency and self-verification, and attempted to scale them up. None have reported the same success that we have; in fact, we aren’t aware of any prior works that have successfully applied self-verification to frontier models in a way that actually beats self-consistency. Instead, to beat self-consistency, the field has turned to training process-based reward models, using RL to learn verifiers, and other complicated interventions.

This has led to a general belief that direct self-verification isn’t enough, whereas we show that it is—you just need to hit a certain threshold of scale and obey some important principles. While this may be intuitive, it’s not at all “predictable”. It's also noteworthy that direct self-verification can successfully and reliably extract o1-level performance from a non-reasoning model without any finetuning, distillation, RL, or custom-trained verifiers (again, no other works/methods—verification-based or otherwise—have achieved this).

To your second concern: As we note above, our main contribution is showing that scaling search with self-verification does work on frontier models and providing an explanation for why: implicit scaling. Methods like direct comparisons are ways of taking advantage of implicit scaling, and are a big reason why our attempts at scaling self-verification were uniquely successful. For example, it is notoriously difficult to beat self-consistency when it comes to the MATH performance of frontier models that already get 90%+ accuracy (hence our paper is the first to do so). As we show in Table 3, direct comparison plays a key role in overcoming this “last-mile” barrier, enabling self-verification to actually beat self-consistency.

—

Individual questions:

“The relatively small gap between Pass@1 and Consistency@5 in Table 5.”

The small gap between Pass@1 and Consistency@5 indicates that scaling self-verification accuracy via self-consistency is limited in effectiveness—this doesn’t contradict any of our findings. In fact, it’s part of our core argument: the techniques we propose (like direct comparisons) allow for more effective test-time scaling of self-verification than self-consistency.

"In Table 5, the random guessing entries show an 80/20 split for Correct/Wrong responses rather than the expected 50/50. Could the authors explain?"

50/50 and 80/20 are both attainable with random guessing (just change the bias of the coin you flip). Because the prior of frontier models is skewed towards 80/20, we wanted to provide a similarly calibrated random baseline and so opted to display 80/20 instead of 50/50.

"Is there the evaluation result for Gemini v1.5 in Verification Benchmark?"

Good question; we exclude Gemini v1.5 from the benchmark since we use Gemini v1.5 to generate the candidate solutions. Evaluating Gemini v1.5 on the benchmark seemed unsound given the potential confounding.

Thank you for your review! We address your questions below.

Computational cost compared to alternative reasoning frameworks such as Tree-of-Thoughts (ToT) and reinforcement learning-based approaches.

Optimizing computational efficiency was not the main focus of this paper, which focuses on understanding the broader scaling trends underlying sampling-based search via self-verification. While we chose to study a minimalist implementation of sampling-based search, we expect our insights to generalize to alternative implementations that place a premium on computational efficiency. In fact, there are several avenues along which the effectiveness and efficiency of our minimalist sampling-based search implementation can be improved: prompt caching, delegated search, training smaller verifiers, etc.—all exciting directions for future work. Regarding ToT and RL, these are complementary techniques: you can always apply sampling-based search and self-verification to RL-trained models that use ToT for inference. As a result, comparing between two methods that can be used in concert imposes an unnecessary trade-off.

Application of Verification@200 on other LLMs.

In Appendix B.2, we include results that apply Verification@200 to the significantly smaller Gemini 1.5 Flash model. Computational concerns were a limiting factor in the number of LLMs studied, but we find no reason for the trends we observed with 1.5 Pro and 1.5 Flash to not generalize to models like GPT4o.

Thank you for your review. We address your questions below.

“I’m skeptical of the author’s implicit scaling claim… it is unclear if increased generations improves generation quality or simply increases generation coverage.”

We understand this concern and provided Figure 2 for exactly this reason. Figure 2 explicitly controls for the fact that coverage (Pass@k) increases with k by limiting our evaluation to questions on which the model has at least one correct answer (i.e., “ambiguous questions”). In fact, we also provided Figure 4 for this reason, which is exactly the same as Figure 1 except that it controls for “generation coverage”. Re Brown et al.: Brown et al. is concerned with the scaling of Pass@k (usually an unrealistic upper bound and not an operative metric); we are concerned with how much of the Pass@k - Pass@1 gap can actually be attained.

“I don’t follow the authors’ claim that increasing generations will increase the verifier’s likelihood of error, given that pass@k is known to increase.”

The only problems on which verification can err are ambiguous problems (where there is at least one correct answer) and increasing k can make verification on ambiguous questions harder. This latter claim follows from basic probability: if you allow students more attempts at an exam, the average pass-rate of a student who passes at least one exam decreases. Similarly, as you increase k, the average number of correct solutions/question decreases. Thus, if implicit scaling didn’t exist, the lines in Figure 2 should all provably be non-increasing or even decreasing.

“The observation that reasoning models have weak out-of-box verification capabilities has been previously reported”

We agree and note in the paper that “the limitations of model self-verification capabilities are well-studied”. This is why we believe our results are so surprising: while prior works have attempted to scale self-verification on frontier models, none have succeeded in beating self-consistency with direct self-verification and instead needed to turn to masking techniques, learning verifiers, process-based rewards, etc. In contrast, we show that direct self-verification can be scaled to reliably achieve o1-level performance without finetuning, RL, distillation, or custom models—something that our paper is the first to do. While we already cite 30+ papers on LLM self-verification, we will add a brief discussion on Wu et al. which is largely orthogonal to this work.

Paper structure.

We appreciate the feedback and will look at revising the structure of the paper per your advice. Since the algorithm we present is fairly minimal, we wanted to highlight the scaling trends first.

—

Questions:

Are the results in Section 2 doing the same process as in Section 3.1?

Section 2 omits tie-breaking for computational reasons but is otherwise the exact same process as Section 3.1 (including rewriting). Regarding rewriting, we see it as just part of the verification process—one that is sadly often overlooked. We don’t see how it undermines/confounds any of our reported results, e.g. implicit scaling. We provide the rewriting process in the source code (it’s pretty generic; we use the exact same instructions for all benchmarks), but will revise to include a copy in the Appendix.

Do you have a FLOPs comparison of the different settings of k_inf and k_ver?

We are unable to publicly report the FLOPs used in closed-source models, but do detail the number of output tokens used (from which FLOPs can be extrapolated) and will include a more involved discussion. We focused on closed-source models in this paper as—at the time of this submission—no OSS models had reached the minimum level of capability needed for self-verification to scale.

For the questions in which the number of solutions which reached the correct are very low (eg. 1-2 generations), what fraction does Verification@k get correct?

We will run a more formal analysis, but we can give some preliminary numbers. In particular, the AIME exam falls in the regime you’re asking about: on 12/15 questions, less than 4% of Gemini Pro solutions are correct. Nonetheless, Verification@200 gets >50% accuracy. On the 7/15 questions where exactly 1-4% of questions are correct, Verification@200 gets 5/7 correct. We agree that this would be impactful to include and appreciate the suggestion.

Could the authors clarify what is prompted during self-verification...? Why are the FP and FN rates missing for the LiveBench questions? Does the difference in FP and FN rates translate to... Verification@k accuracy?

The full prompts for all four options referenced in Table 4 can be found in the source code; we will revise to include a copy in the Appendix. We added LiveBench at a later date and had not yet re-run Table 4, but will include them in our revision. We informally observed Verification@k accuracy to be especially sensitive to FN rates, and will add a formal table to this effect.