acceptodds
Under review as a conference paper at ICLR 2027

Test-Time Scaling Is Bounded by Verification, Not Generation

Abstract

Test-time compute methods draw many candidate solutions and return one. What sampling makes available, coverage, is fixed by single-sample accuracy; what a user receives depends on selection, and selection is governed by other quantities. We prove that a verifier's AUC does not determine its best-of- accuracy: with one correct candidate among , a verifier of AUC selects it with probability anywhere between and , so no verifier can recover a lone correct answer more often than its AUC, and the AUC needed for a fixed accuracy rises with the budget. For voting, whose success depends on whether the most common wrong answer outnumbers the right one, we show that the usual way of measuring difficulty, stratifying problems on the same samples used for evaluation, understates voting on hard problems in every model we test, enough to make it look worse than random for some, and overstates it on easy ones. With a held-out protocol across six models from three families, 1,400 problems and 32 samples each, real verifiers sit well inside the interval, so that their AUC leaves best-of-8 accuracy undetermined over tens of points, voting's held-out gains follow its error condition, and 32 samples predict coverage and reward-model accuracy at 128, including where selection levels off. On the 10,000 samples per problem released by Brown et al., the voting condition predicts the height of the voting plateau to within a point for 8B and 70B models. On hard problems, even a trained process reward model leaves 38–66% of the correct answers added by doubling the budget unselected. Sampling has outrun our ability to tell which sample is right.

Primary area:
foundation or frontier models, including LLMs
Keywords:
test-time compute, inference scaling, repeated sampling, majority voting, self-consistency, verifiers, process reward models, best-of-N, evaluation methodology

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cS61OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper tries to show that test-time scaling in language models is "bounded by verification, not by generation". To this end, the authors look at two common test-time scaling paradigms, both of which rely on a pool of nn generated responses: voting (where the most common response amongst the nn samples is returned) and using a process-reward model (PRM), which scores responses, and the response with the highest score is returned. The authors establish a lower and upper bound on the probability that a PRM selects a correct answer, given its AUC. In experiments, they show that both methods can "lack behind" coverage, that is, correct solutions could be added to the pool of solutions without either method selecting them.

Critical strengths
  • while easy to prove, proposition 3 seems like an interesting and potentially useful result
Critical weaknesses

The paper lacks clear motivation in my opinion, for several reasons:

  • authors suggest verifiers are "usually compared" by AUC; however, to my knowledge, a much more common metric would be downstream accuracy of a verifier when used in best-of-nn test-time scaling. The authors don't provide any references to support this claim
  • authors claim that "the usual way of measuring difficulty, stratifying problems on the same samples used for evaluation, understates voting on hard problems [...] and overstates it on easy one. Again, I'm not familiar with works doing this, and the authors provide no references supporting the claim
  • it's well-known (and trivial) that test-time scaling methods like voting or PRM-guided best-of-nn don't always select correct solutions amongst a pool containing correct solutions (i.e., that they lack behind pass@nn)

Furthermore, the paper has the following issues:

  • theoretical results (propositions 1, 2, and 3) are all trivial (while the result of proposition 3 could be of relevance to the research community)
  • presentation could be improved; it is not clear what the exact contributions and motivations are. Experimental results are difficult to read; for example, just in Table 1, I see the following issues: authors define the "Unselected" columns as "share of the correct answers added by doubling the budget [...] that the selector does not return", which I interpret as "amongst problems that contain no correct solutions at n=4n=4, but do contain correct solutions at n=8n=8, on what share of such problems does the PRM fail to return a correct solution?", but it could also be "1 - (PRM accuracy at 8 - PRM accuracy at 4) / (coverage at 8 - coverage at 4)", or something else. β\beta is said to be the "calibrated held-out slope for Proposition 2", but Proposition 2 never defines β\beta, and there's no formula anywhere else either defining β\beta as far as I can see. Some entries are missing but it is unclear why. It is unclear what PRM is used for Table 1, I'm assuming Qwen2.5-Math-PRM-7B across all generation models. And it would be helpful if the caption contains a more descriptive explanation for what the last column says (although the text in Section 3 makes it clear)
  • one of the main claims is that "A verifier's AUC does not determine what it can select" (section 4.1), and that it "understates the difference between verifiers". It is not entirely clear what is meant with these claims to me, or how the authors intend to validate them with their evidence in this section. Table 1 does not compare different verifiers, as far as I can tell, but only different generation models with the same verifier. Furthermore, Table 1 actually shows very strong correlation between the verifier's AUC across models, and its downstream accuracy on best-of-8 (0.96 pearson, and 1.00 rank correlation).
  • the paper is missing closely related prior work: [1] characterizes best-of-nn in terms of the verifier's ROC curve and also includes extrapolation to larger nn from small budgets, and how extreme scores can affect limiting behaviour, but is not discussed at all
  • the authors claim proposition 3 would explain why PRM accuracy plateaus as nn grows (e.g. in the introduction under Contributions), but proposition 3 fixes the number of correct samples mm, while in practice, mm would grow as nn does, so this result does not really apply

[1] Florian E. Dorner, Yatong Chen, André F. Cruz, and Fanny Yang. ROC-n-reroll: How verifier imperfection affects test-time scaling. arXiv preprint arXiv:2507.12399, 2025.

To summarize, unfortunately I don't see sufficient motivation for the paper, nor sufficient evidence for the stated claims.

Questions for authors
  • what is the lower gray curve in Figure 1(b)?
  • the authors should consider including a definition of AUC for a verifier
1 comment
AuthorsOpenReview ↗

Revised version uploaded

We have uploaded a revised PDF. In response to your review:

  • The abstract and introduction are rewritten in plainer language and follow one line of argument: voting depends on which wrong answers repeat; stratifying difficulty on the evaluated samples misstates voting on hard problems; AUC does not determine best-of-k; and shared errors limit where selection levels off.
  • Sec. 5 includes the corrections we described in our last reply (ROC-n-reroll, Kuhn et al.).
  • We checked every citation against its source, and corrected nine statements and one bibliography entry.
  • Sec. 4.4, 4.6 and 4.7 are rewritten in plainer language.

If any part is still hard to follow, a pointer to it would help us fix it. We can revise until Nov 18.

Reviewer_w4jQOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Large language models often adopt test time scaling to boost reasoning ability: generating multiple candidate solutions via repeated sampling and selecting the optimal one from them. The industry generally believes that increasing sampling compute and expanding the size of candidate sets (improving coverage) can continuously raise the model’s reasoning accuracy. However, the research community has largely overlooked the performance mismatch between candidate generation and result selection. Although raising the sampling budget can increase the probability that a correct answer exists in the candidate pool, it cannot guarantee that the selection mechanism will accurately pick out the correct answer. Focusing on this core tension, this paper conducts theoretical derivations and empirical analyses from three perspectives: coverage, majority voting, and verifier based selection. Its main contributions are as follows. First, it derives the bounds for best of k selection accuracy based on a verifier’s AUC, proving that AUC alone cannot fully measure a verifier’s practical selection capability. Second, it identifies the circular evaluation bias caused by re using the same sampled candidates both for difficulty stratification and performance evaluation, and proposes a sample splitting held out evaluation protocol. Third, drawing on six models from three model families, together with large scale public sampled datasets, it verifies the feasibility of predicting performance under large sampling budgets using selection outcomes obtained under small sampling budgets.

Critical strengths
  1. The paper addresses an important problem in test-time scaling. It clearly distinguishes coverage and selection accuracy: Pass@k only checks whether sampling generates a correct candidate, while final task performance depends on whether the selection mechanism can retrieve that correct candidate. This distinction offers a principled explanation for diminishing returns when increasing sampling budget, and helps separate the limitations of candidate generation and candidate evaluation for reward-model selection and self-consistency.
  2. The verifier analysis provides a useful characterization of AUC's limitations. Proposition 3 proves that under given distribution assumptions, the best-of-k selection accuracy is bounded within [a^{k-1},a] where a denotes the verifier’s AUC. This highlights a key insight: pairwise ranking metrics like AUC cannot fully capture the ability to select the correct answer from a candidate pool, and score tail distributions strongly affect the selection performance. It delivers valuable theoretical support for verifier evaluation in practice.
  3. The paper identifies a meaningful evaluation pitfall in voting analysis. Reusing the same samples for difficulty stratification and performance evaluation creates bias: it underestimates voting gains on hard problems and overestimates gains on easy ones. The proposed held-out protocol is methodologically sound. The authors transparently reported this bias and revised their analysis accordingly, which improves the credibility of the empirical results.
Critical weaknesses
  1. The incremental contribution on the theoretical side is limited, though the theoretical results are practically valuable. The core theoretical conclusions derived in this work offer useful insights for understanding test-time scaling, yet most mathematical foundations for the derivations build upon existing established theory. Proposition 1 follows directly from properties of independent Bernoulli sampling; Proposition 2 is closely related to prior results on plurality voting and the Condorcet jury theorem, as already acknowledged by the authors in the manuscript. Proposition 3 relies mainly on probabilistic inequalities and Jensen’s inequality. Therefore, the theoretical contribution of this paper lies primarily in performing targeted derivations tailored to the specific setting of test-time scaling for large models and delivering domain-level analytical insights, rather than introducing an entirely new mathematical framework.

  2. Mixed performance of the small-budget prediction framework The paper’s small-budget prediction framework reliably estimates coverage and reward-model selection performance, including the accuracy plateau, at larger sampling budgets. However, it systematically underpredicts voting accuracy by up to 4.3%. Since predicting test-time scaling trends is a core empirical motivation of this paper, this inconsistency is non-negligible. The robustness of the prediction procedure across models, sampling distributions, and task settings remains unclear. The authors should explicitly distinguish reliably predictable large-budget behaviors from hard-to-estimate selection properties, and avoid equating successful coverage prediction with accurate selection-performance prediction.

  3. The practical implications of the AUC result remain underdeveloped. The paper convincingly demonstrates that AUC alone cannot pin down best-of-k accuracy. However, it does not identify alternative metrics for practitioners. Exploring supplementary statistics including score-tail behavior, calibration and problem-conditional ranking performance could explain the residual variance unaccounted for by AUC. Such analysis would convert the theoretical findings into a practical protocol for verifier evaluation. This point is critical: the core claim is not simply that verifiers are imperfect, but that conventional metrics may mispredict selection performance under large sampling budgets.

Questions for authors
  1. Robustness of Proposition 3: Which parts of the AUC-based selection bounds remain valid if candidate scores are dependent or if their distributions vary across problems?

  2. Prediction failure: Why does the small-budget procedure systematically underpredict voting performance at larger budgets, and can the authors identify the conditions under which this failure occurs?

  3. Held-out protocol: How sensitive are the voting conclusions to the number of samples reserved for estimating difficulty? Is the proposed protocol reliable when only a small number of samples is available per problem?

Reviewer_3bHjOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper separates the availability of a correct sample from the accuracy of selecting one. Its main theoretical result gives tight bounds on best-of-k selection conditional on m correct candidates and per-problem verifier AUC a: a^(k-m) ≤ selection accuracy ≤ 1-(1-a)^m, under independent class-conditional scores. It also identifies selection bias from defining problem-difficulty strata on the same samples used to evaluate voting, and uses held-out halves instead. Experiments cover six models on 1400 mathematics problems, a 32-to-128-sample prediction study, and a reanalysis of released 10000-sample pools. The main contribution is a theoretical and empirical account of why coverage gains need not translate into selection gains.

Critical strengths
  1. The AUC bound is precise, interpretable and useful. Proposition 3 clearly distinguishes pairwise discrimination from ranking against an entire pool. The proof through V=F_minus(S_plus) is short, the extremal constructions establish tightness, and the paper appropriately notes that applying the bound to empirical score distributions is a computation check rather than experimental validation of the theorem. This is a useful warning against interpreting a single AUC as a sufficient selector-quality metric (Section 2.3 and 4.1).

  2. The held-out evaluation provides a consequential methodological lesson. The comparison between circular and held-out stratification changes the apparent sign of voting gains on hard problems for several models. The additional large-pool reanalysis, robustness checks and disclosure of failed voting predictions and failed aggregation experiments improve the evidential value. The paper also acknowledges that the voting condition itself is known, locating the contribution in measurement rather than claiming a new voting theorem.

Critical weaknesses
  1. The voting implementation appears to use correctness labels to define answer classes. Section 3 and Appendices A/H merge all samples judged correct into one class, while grouping incorrect answers using a separate normalization procedure. If equivalent correct answers can retain different normalized forms, this gives the correct class a label-dependent advantage unavailable to a deployed voter. The held-out sample split does not remove that issue. The magnitude needs to be checked with one answer-equivalence procedure applied to every sample without consulting correctness. This matters directly for the reported voting gains and plateau prediction, although it does not invalidate Proposition 3.

  2. The broad scaling interpretation is stronger than the established generality. The distribution-free AUC interval is informative about underdetermination, but a plateau prediction requires additional upper-tail assumptions. The 32-to-128 extrapolation fits logit-normal score distributions with empirical-Bayes shrinkage on 144 selected problems from one generator, and voting fails its prediction criterion. Synthetic validation under a specified model does not establish robustness to real tail misspecification. A modest nonparametric/tail-fit sensitivity check, predictive uncertainty, and a sharper separation between the general theorem and this specific extrapolation would make the claimed explanation more convincing (Section 3, 4.4 and Appendix F).

Questions for authors

Can voting classes be constructed without correctness labels, using exactly the same canonicalization or pairwise answer-equivalence rule for all outputs? Please report whether the hard-stratum signs and large-budget plateaus change.

Ranking multiple candidate solutions generated at test time has also received attention in LLM-based code generation, with some approaches explicitly optimizing pass@k. Although this paper focuses on mathematical problems, I suggest that the authors add a discussion of related work to highlight the broader relevance and importance of the research question. Relevant references include:

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.