- 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 generated responses: voting (where the most common response amongst the 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- 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- don't always select correct solutions amongst a pool containing correct solutions (i.e., that they lack behind pass@)
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 , but do contain correct solutions at , 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. is said to be the "calibrated held-out slope for Proposition 2", but Proposition 2 never defines , and there's no formula anywhere else either defining 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- in terms of the verifier's ROC curve and also includes extrapolation to larger 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 grows (e.g. in the introduction under Contributions), but proposition 3 fixes the number of correct samples , while in practice, would grow as 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
Revised version uploaded
We have uploaded a revised PDF. In response to your review:
If any part is still hard to follow, a pointer to it would help us fix it. We can revise until Nov 18.