- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper separates coverage (some candidate is correct) from selection (the decision rule returns it) in test-time scaling. The setup uses Qwen2.5-1.5B-Instruct as the policy and Qwen2.5-Math-PRM-7B as the verifier, on GSM8K and MATH-500. It compares independent sampling with soft/hard verifier-guided retention and REBASE.
The main empirical findings:
- Independent sampling matches or exceeds guided search in coverage, but its votes recover much less of that coverage.
- Guidance enriches the correct fraction of candidates, and it also makes wrong answers agree, largely within shared-prefix families.
- A Shapley-style decomposition attributes guided search's vote gain to enrichment, which outweighs a conditional-voting penalty at minority correct counts.
The method is certified selective verification. Verifier weights are bounded, , so each answer's total weight has an interval. Candidates are scored greedily until one answer's lower bound exceeds every rival's upper bound. The result is exactly the full weighted-vote winner, at a fraction of the scoring cost.
End to end, this reproduces all 8,400 full-verification decisions with 70–83% (GSM8K) and 36–62% (MATH) fewer verifier tokens. Against REBASE, it matches REBASE's best GSM8K accuracy at about a third less estimated compute, and on MATH it reaches 62.2% vs 60.3% at 27% less.
Critical strengths
- An exact, deployable, verifier-agnostic selection rule. The certificate holds for any fixed bounded score vector, however the candidates were generated and however the verifier is calibrated. It was audited on 8,400 live comparisons with zero answer mismatches. For anyone already running weighted voting, this is a free 40–80% cut in verifier cost with no change in decisions, which has direct practical value.
- Careful measurement of how guidance reshapes the candidate pool. The paper separates correct-answer enrichment from error clustering, and the controlled wrong-group splitting (Fig. 4, Table 8) holds scores and correct groups fixed. This explains mechanically why guided search's vote advantage is not a coverage advantage, and it ties error clustering to certification cost. Pairing bootstrap intervals with a replication cohort is good practice.
Critical weaknesses
W1. The compute comparison with REBASE, which drives the headline claim, is fragile.
The FLOP proxy likely overcharges guided search. Compute is tokens, explicitly omitting KV-cache reuse (A.4). With a 7B PRM verifying a 1.5B policy, verifier input dominates the budget. REBASE re-scores growing prefixes at all 12 depths. With prefix caching, which standard serving stacks provide, most of that verifier input would be reused instead of recomputed. The proxy therefore charges REBASE the full re-encoding cost, whereas the certified pipeline scores each completed solution once.
The reported margins are small:
- GSM8K: accuracy differences are all inside the intervals, and compute savings at the matched points are −0.9% to 9.5% (Table 14).
- MATH: +2.6 [0.0, 5.3] at N=80.
A cache-aware or wall-clock measurement could plausibly erase or reverse the "a third less compute" claim.
The guided-search comparison is incomplete.
- Only REBASE appears in the live frontier.
- Diverse Verifier Tree Search (Beeching et al. 2024), cited, directly targets the error-clustering failure the paper diagnoses. It is the natural competitor and is missing.
- Plain beam search is also missing.
- Cheaper selection alternatives are not compared: an ORM, or early-stopping self-consistency combined with weighting.
Generality is thin. There is one policy (1.5B), one verifier family (7B), and two largely saturated math benchmarks. The paper's conclusion is that verifier compute belongs at selection rather than in generation. That conclusion depends heavily on the policy-to-verifier size ratio and on how strong the verifier is, and it may not hold with a smaller verifier, a larger policy, or harder tasks. On MATH Level 5 the paper's own data shows REBASE catching up or edging ahead.
W2. The conceptual contributions are modest relative to prior work.
- The certificate is elementary. It is a deterministic branch-and-bound / interval argument for an argmax over bounded sums. The splitting lemma is a one-line monotonicity observation.
- Its savings come almost entirely from consensus. With , , so unscored candidates contribute essentially nothing to the lower bound. The rule then reduces to scoring until the leader's scored weight exceeds each rival's scored weight plus its unscored count.
- Missing related work. Closely related lazy- and early-stopping verification methods should be discussed and compared, e.g. speculative rejection / early-rejection best-of-N and early-stopping self-consistency.
- The certificate never adapts N. It is applied only to a fixed pool. The natural, stronger contribution would be an anytime version that stops generating once the winner is certified, rather than sweeping fixed N.
- The diagnostic findings are largely known. The coverage–selection gap was shown by Brown et al. (2024), and diversity collapse under guided search by Beeching et al. (2024). The new part is the quantification.
- The conditional analysis is weak. Table 2 and Table 6 compare different question sets in each stratum, which the authors acknowledge. Several strata rest on 5–16 questions with intervals spanning ~50–100 points, so the "competition penalty" estimates are imprecise.
Questions for authors
- (Decisive.) How do the accuracy–compute frontiers in Figure 6 change under a cache-aware accounting (prefix KV reuse for the PRM in REBASE) or measured wall-clock / GPU-seconds? Does the certified advantage over REBASE survive?
- Can you add DVTS (and beam search) to the live frontier? DVTS addresses exactly the error clustering you identify, so it is the most informative guided baseline.
- How sensitive are the savings and the frontier to , and to the policy/verifier size ratio, e.g. a 7B policy with the same PRM, or a smaller verifier?
- Have you tried an anytime variant that interleaves generation with certification and stops sampling once the winner is certified? That would test whether certification can also reduce generation cost, not just verification cost.
- (Clarification.) The live runs give ordinary-vote numbers 2–3 points lower than the saved runs (Appendix D.1). Which protocol produced the Section 3–4 diagnostics, and does any conclusion depend on mixing the two?
4 comments
Answer to Reviewer WVZZ (2/2)
How sensitive are the savings and the frontier to β, and to the policy/verifier size ratio?
Accuracy. All methods in Figure 6 share one frozen rule. Giving REBASE the best terminal rule in hindsight (three aggregations, 33 values of β, and best-of-N) moves its width-20 accuracy by at most 0.3 points: 87.50→87.75 (GSM8K), 60.30→60.40 (MATH), 75.6→75.7 (Qwen3.5) and 60.4→60.7 (Granite MATH). On Granite MATH, REBASE's pool covers 62.4% of questions, below certified N=80's 65.6% accuracy, so no rule on that pool can close the gap. The frozen rule hurts certified selection instead: for example on Granite GSM8K, the rule chosen on Granite's own development split lifts certified N=80 by 3.9 points [2.4, 5.5].
Savings. The guarantee holds for any bounded rule, and the savings vary with it. On Granite MATH at N=80, verifier-token savings range from 13% to 95% across rules with positive β, with 79% under our default. The most accurate rule we tested (68.5%) saves 30%. You can pick a rule to maximize accuracy and keep the same answer at lower cost.
Size ratio. The new pairs include a 2B policy with a 7B PRM and a 3.8B policy with an 8B PRM. This regime is the common one in test-time scaling: open PRMs are mostly 7B or larger, and studies pair them with smaller policies (for example, Beeching et al. (2024) use 1B and 3B Llama policies with an 8B PRM), since verification is the step the search relies on. It is also where certification matters most: the larger the verifier relative to the policy, the larger verification’s share of total cost, and the more the certificate saves. With a smaller verifier, total savings shrink toward the 4–9% end-to-end gain we measured, because generation dominates. A controlled ablation, such as a 7B policy with the same PRM, remains future work.
The certificate is elementary … Its savings come almost entirely from consensus.
We agree on both points. The simple rule is easy to implement and exact. With β=8 it compares the leader's scored weight with each rival's scored weight plus its unscored count, so cost tracks consensus (Figure 5). Consensus is common: at N=80 the certificate uses a median of 8 queries, with 57 eligible candidates on average.
Closely related lazy- and early-stopping verification methods should be discussed.
We added speculative rejection and early-stopping self-consistency to Related Work. Both cut generation: speculative rejection drops candidates whose partial reward scores rank low, a heuristic without a formal guarantee, and early-stopping self-consistency stops sampling once a window of answers agrees, with a statistical bound on disagreeing with full voting. The certificate acts on selection and is exact for a fixed pool, so you can combine it with either.
Have you tried an anytime variant …?
We simulated one offline on our nested pools. Generating in chunks of four up to N=80, and stopping once no ungenerated candidate could change the winner, saves 6–26% of generation tokens. Our conservative query schedule raises verifier work 2–9×, so it does not yet save overall; we leave better schedules to future work.
The diagnostic findings are largely known.
Brown et al. (2024) show coverage rising while selection plateaus; Beeching et al. (2024) show guided search losing diversity. We split the voting gain into enrichment and error clustering and tie clustering to certification cost. The decomposition reproduces in every new setting, DVTS included (Appendix B.4).
The conditional analysis is weak. Table 2 and Table 6 compare different question sets in each stratum … Several strata rest on 5–16 questions …
We agree that individual minority strata are imprecise. The aggregate decomposition pools all strata, and it reproduces in all 13 live cohorts with hundreds of eligible searches each (Appendix B.4).
Which protocol produced the Section 3–4 diagnostics, and does any conclusion depend on mixing the two?
Sections 3–4 use the saved runs and Figure 6 the live runs; no comparison mixes them. Replaying the diagnostics on the live MATH runs gives the same pattern: coverage 71.9% vs 63.9% for REBASE, ordinary voting 47.2% vs 58.4%, correct-candidate fraction 24.3% vs 40.9%.
We hope the latency measurements and the cache-aware comparison address your main concern, and we would be glad to discuss any remaining points. If they do, we would appreciate your reconsidering the score.
Thanks for the revision; keeping my score
Thanks for the new experiments and for revising the claims.
On my main question: I appreciate that you dropped the "a third less compute" claim once the cached-FLOPs comparison reversed on the original runs. The result is now: certified sampling reaches REBASE's best accuracy more cheaply in 6 of 10 runs and is faster end-to-end at small budgets, while DVTS matches or beats it at high budgets. That is more modest but more honest than the original paper.
Adding DVTS and the coverage-retention correlation helps. Together they support your point that guided search wins when it keeps coverage.
Remaining concerns: the certificate is simple and its savings come mostly from consensus (which you agree with), the anytime variant doesn't save overall yet, and the compute advantage over guided search now depends on the setting. I see the main value as the coverage/selection analysis plus a cheap, exact selection rule.
I'm keeping my score at 2.
Thank you for the follow-up. We are glad the DVTS comparison and the coverage analysis support the paper's point.
On the advantage depending on the setting: one result holds in every setting we ran. At low budget (N=20) and matched cost, certified sampling is at least as accurate as REBASE in all six settings, with intervals excluding zero in five, and more accurate than DVTS in both settings where DVTS ran at that budget. Even with both models cached, it reaches REBASE's best accuracy at 40–55% lower cost in six of ten runs. In both timed settings, it answers 13–24% faster than REBASE width 5 while scoring higher (+6.1 points on Phi MATH, +2.6 on Qwen OlympiadBench), and 22–27% faster than DVTS 8 at similar accuracy.
On savings coming from consensus: this makes the certificate spend verifier calls where answers disagree, which is where the verifier changes the outcome. With the Qwen PRM on MATH at N=80, weighting beats majority voting by 10.1 points for Qwen2.5-1.5B, and the certificate scores more there, saving 58% of verifier tokens. For Qwen3.5-2B, answers agree, weighting adds 0.4 points, and the certificate saves 92%. Figure 5 shows the same pattern question by question: the certificate scores most candidates when the vote is close and few when it is clear.
Answer to Reviewer WVZZ (1/2)
Thank you for the detailed review. Your questions on caching, DVTS and selector sensitivity led to most of the new experiments reported in the new revision.
The paper's proxy charges tree search for re-reading shared prefixes, as a server without prefix reuse would. With caching, the answer depends on what the deployment caches, so we measured it. With a prefix-cached policy and a stateless batched verifier (50 questions, two seeds), certified N=20 answered 13% faster than REBASE width 5 on Phi MATH (latency ratio 0.87 [0.78, 0.96]) and 24% faster on Qwen OlympiadBench (0.76 [0.69, 0.84]), with accuracy differences within noise. Certified N=40 ran 8% slower than REBASE width 10 on Phi MATH and 15% faster on OlympiadBench.
A caching verifier helps REBASE less than FLOP counts suggest, because each level waits for the previous level's scores. In a cached replay of our verification workloads (50 Phi MATH questions, two seeds), REBASE width 20 reused 83.5% of its verifier input and still spent 6.7 s per question on verification, against 0.23 s for certified N=20 and 0.60 s for N=80.
If we count nominal FLOPs with both models cached, the large-pool comparison on our original runs reverses: REBASE width 20 costs 117.5 TFLOPs against 157.7 for certified N=80 on GSM8K at equal accuracy, and 197.6 against 368.1 on MATH, where certified is 1.9 points more accurate. We removed the "a third less compute" claim. Under this accounting, the fair test asks what each method pays to reach the same accuracy. For each of our ten runs, we take the smallest certified budget that reaches REBASE's best accuracy at any width:
Certified sampling costs 40–55% less in six runs. In the other four, REBASE costs less or reaches higher accuracy, and closest-cost pairing under this accounting splits the same way (Appendix D.5).
We added DVTS at six budgets with four selectors and report weighted voting, the selector certified sampling uses. At matched uncached cost, certified sampling wins at low budgets (+5.4 [2.6, 8.2] on Phi MATH, +3.3 [1.0, 5.7] on Qwen OlympiadBench). At high budgets the two tie on MATH and OlympiadBench (−1.7 [−3.8, 0.4], −1.2 [−3.5, 1.0]), and DVTS leads on GSM8K (−2.8 [−4.8, −0.8]). Under nominal two-model caching, DVTS leads at both budgets. End to end, certified N=20 ran 22% and 27% faster than DVTS 8 (ratios 0.78 [0.73, 0.84] and 0.73 [0.68, 0.80]), whose accuracy is within two points. DVTS 8 was faster than certified N=40 in both settings, and DVTS 4 was faster than certified N=20 but scored lower (−5.4 and −3.3 points on the full cohorts). DVTS competes because it keeps coverage high, as our analysis predicts. We did not run plain beam search as we consider DVTS is its diversity-preserving variant and the stronger baseline.