acceptodds
Under review as a conference paper at ICLR 2027

From Coverage to Accuracy: Making Independent Sampling Competitive with Guided Search

Abstract

Verifier-guided search can raise accuracy while narrowing generation onto a few reasoning paths. We ask how that narrowing changes the answer a method returns, separating coverage (a correct answer is in the pool) from selection (the decision rule returns it). On GSM8K and MATH, independent sampling covers correct answers about as often as guided search, yet turns less of that coverage into correct votes: on MATH it leads guided coverage by 6 to 11 points while its vote trails by 12 to 14. Guidance raises the share of correct candidates, and it makes wrong answers agree more often. Conditional comparisons and controlled answer-group interventions show the agreement can outweigh the enrichment for a correct minority, even while guidance lifts the vote overall. This points to improving selection as an alternative to spending compute on guided generation. We introduce certified selective verification, which returns the exact weighted-voting winner for a fixed bounded score vector while scoring only the candidates needed to decide it. In live end-to-end runs it reproduces every full-verification decision using 70 to 83% fewer verifier tokens on GSM8K, 36 to 62% on MATH. Sweeping the pool size gives certified independent sampling competitive accuracy–compute trade-offs: it matches REBASE's best observed GSM8K accuracy at about a third less compute, and reaches higher observed accuracy on MATH (62.2% versus 60.3%) at 27% less compute.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Test-time scaling, verifier-guided search, answer selection, self-consistency, large language models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_WVZZOpenReview ↗
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, w=exp⁡(β(s−1))∈[e−β,1]w=\exp(\beta(s-1))\in[e^{-\beta},1], 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
  1. 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.
  2. 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 2N×2N\timestokens, 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 β=8\beta=8, e−β≈3×10−4e^{-\beta}\approx 3\times10^{-4}, 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
  1. (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?
  2. 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.
  3. How sensitive are the savings and the frontier to β\beta, and to the policy/verifier size ratio, e.g. a 7B policy with the same PRM, or a smaller verifier?
  4. 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.
  5. (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
AuthorsOpenReview ↗

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.

How do the accuracy–compute frontiers in Figure 6 change under a cache-aware accounting … Does the certified advantage over REBASE survive?

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:

RunCertified NCertified / best REBASE (%)Cost with both caches (TFLOPs)
Qwen2.5/Granite MATH, run 12061.7 / 60.4118.9 / 243.5
Qwen2.5/Granite MATH, run 22063.9 / 59.3102.8 / 226.1
Phi/Granite MATH2072.6 / 70.1231.8 / 394.8
Phi/Granite OlympiadBench2037.7 / 31.6344.1 / 577.3
Qwen3.5 MATH, depth 122060.5 / 52.2157.8 / 338.5
Qwen3.5 MATH, depth 242075.8 / 75.6290.6 / 503.9
Qwen2.5/Qwen PRM GSM8K (original)8087.5 / 87.5157.7 / 117.5
Qwen2.5/Qwen PRM MATH (original)8062.2 / 60.3368.1 / 197.6
Qwen2.5/Granite OlympiadBenchnonenot reachedn/a
Qwen2.5/Granite GSM8Knonenot reachedn/a

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).

Can you add DVTS (and beam search) to the live frontier?

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.

AuthorsOpenReview ↗

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.

Reviewer_WVZZOpenReview ↗

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.

Reviewer_EFGBOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary
  • This paper looks at independent sampling vs guided search for math reasoning. The main idea is that independent sampling often finds the right answer, but doesn't always pick it.
  • Guided search gets more correct answers into the final vote, but it also makes wrong answers more similar. This creates a tradeoff between finding diverse solutions and getting enough support for the right answer.
  • The authors analyze this by separating coverage from final accuracy. They also look at how often incorrect answers cluster together and how that affects voting.
  • They then propose certified selective verification, which only verifies as many candidates as needed to guarantee the same result as full verifier-weighted voting.
  • They test on GSM8K and MATH with Qwen models. The method matches full verification while using significantly fewer verifier tokens. It also gets competitive accuracy compared to REBASE at lower estimated compute.
Critical strengths
  1. The coverage vs accuracy analysis is probably the strongest part of the paper. I like that the authors don't just compare final accuracy and call it a day. They actually try to explain why guided search performs better despite sometimes having lower coverage.
  • The breakdown into correct answer enrichment and wrong answer clustering is pretty convincing. For example, on MATH, independent sampling has higher coverage than the guided methods but still performs substantially worse under majority voting. That makes it clear that simply finding the correct answer isn't enough.
  • The conditional analysis is especially interesting. With three correct answers out of ten on GSM8K, independent sampling selects the right answer 88.9% of the time, while REBASE only does so 47.7% of the time. I thought this was a pretty useful way to isolate the effect of answer clustering. I also like that the authors go beyond correlations with the controlled wrong-answer splitting experiment. It gives more evidence that the grouping of incorrect answers matters for both voting accuracy and verification cost. To me, this is the part that makes the paper more than just another inference-time efficiency method. It gives a useful explanation of what's actually happening during guided search, and that seems relevant to future work on test-time scaling.
  1. The selective verification method is simple but has pretty meaningful results. I think the idea of moving verification to the final selection stage rather than using it throughout generation makes sense given the earlier analysis. The paper does a good job connecting the proposed method back to the original motivation. The exactness guarantee is also a nice property. Rather than approximating full weighted voting, the method gives the same answer for a fixed set of verifier scores. It just avoids checking candidates that can't change the outcome.
  • The savings are pretty substantial. Cutting verifier input tokens by 70–83% on GSM8K and 36–62% on MATH while preserving the full-verification decision is a solid result.
  • The end-to-end comparison with REBASE also helps. On GSM8K, they reach the same best observed accuracy with about a third less estimated compute. On MATH, they report 62.2% accuracy compared to REBASE's 60.3%, again with lower compute. I wouldn't say the certification algorithm itself is super novel or complicated, since it's based on fairly straightforward score bounds. But I think the value comes from showing that this approach actually works well in the context of independent sampling. The simplicity is honestly a plus here.
Critical weaknesses
  1. The evaluation is pretty narrow for the broader claims being made. My biggest concern is that everything uses Qwen2.5-1.5B-Instruct and Qwen2.5-Math-PRM-7B. That's a pretty specific setup, especially for a paper making broader claims about independent sampling and guided search.
  • I would really like to see whether the coverage vs selection gap looks similar with stronger policy models. A larger model might already produce more consistent correct answers, which could change how useful independent sampling is. It could also change how much guided search helps.
  • The verifier choice matters too. The proposed method guarantees the same decision as full weighted voting, but it doesn't guarantee that the decision is actually correct. If the verifier is bad at distinguishing correct and incorrect solutions, the method would just reproduce that bad decision more efficiently.
  • Both benchmarks are also math problems with fairly well-defined final answers. That makes grouping candidates and voting relatively straightforward. I'm not sure how this would translate to tasks where answers are less structured or where multiple different answers could all be valid. The authors do acknowledge these limitations, and I appreciate the breakdown by MATH difficulty. Still, I think testing at least one additional model or verifier would make the main argument a lot stronger. Right now, it's hard to tell how much of the result is a general property of guided search versus something specific to this setup.
  1. The practical advantage over guided search isn't completely convincing yet. The compute savings look good, but they're based on a token-count and model-size FLOPs estimate. The paper doesn't report actual wall-clock latency or throughput. I think this matters because the two approaches use verification differently, and their real inference costs could depend on batching, caching, and implementation details.
  • I also think the accuracy comparison with REBASE is a little less decisive than the headline results suggest. On GSM8K, the accuracy differences are within the confidence intervals. On MATH, the best reported accuracy is higher for certified sampling, but the differences at nearby compute budgets aren't always statistically clear.
  • The harder MATH results make this even more interesting. On Levels 4–5, the certified method is basically tied with REBASE, and on Level 5, REBASE actually does a bit better at the largest tested budget. This makes me wonder whether the proposed approach is mainly strongest on easier questions where independent sampling already has a lot of correct candidates.
  • There's also still a pretty big gap between coverage and selected accuracy on hard problems. At N=80 on Level 5, coverage is 67.2%, but certified accuracy is only 27.6%. So the proposed method makes verification cheaper, but it doesn't really solve the underlying problem of selecting correct answers in difficult cases. I think the paper could make a stronger case with measured runtime results and a broader comparison against different guided-search or answer-selection methods. The current results are promising, but I'm not sure they establish that independent sampling with certified selection is generally the better way to spend inference-time compute.
Questions for authors
  • Have you tested the coverage vs selection gap with larger policy models or different verifiers? I'm particularly curious whether guided search still gets most of its advantage from correct answer enrichment as the base model improves.
  • How do the estimated compute savings translate to actual wall-clock latency? Would the advantage over REBASE still hold with realistic batching and caching?
  • On the hardest MATH problems, coverage keeps increasing with more samples, but certified accuracy barely improves. Do you think this is mostly a limitation of the verifier, or is there something more fundamental about the candidate distributions that makes these cases difficult to select from?
3 comments
AuthorsOpenReview ↗

Answer to Reviewer EFGB

Reviewer EFGB

Thank you for the constructive review and for the clear questions. They guided our new experiments, and the revised PDF reports all of them.

Have you tested the coverage vs selection gap with larger policy models or different verifiers?

Yes: Qwen3.5-2B, Phi-4-mini and the Granite verifier (general response). The gap appears in every setting. At matched uncached cost, certified selection beats REBASE in four of the five new MATH and OlympiadBench settings, with intervals excluding zero. With Qwen3.5 the N=80 margin over REBASE width 20 shrinks from 15.0 points at depth 12 to 5.0 at depth 24, so we now report every ranking with its depth.

If the verifier is bad at distinguishing correct and incorrect solutions, the method would just reproduce that bad decision more efficiently.

Yes, the certificate inherits the selector's errors. It also makes better selectors affordable, since it works with any bounded weighting rule. Two examples: weighted selection beats best-of-N (80.6% vs 77.3% with Qwen3.5, +3.3 [1.9, 4.8]), and on GSM8K the selector chosen on Granite's own development split lifts certified accuracy by 3.9 points [2.4, 5.5] over our initial frozen rule.

How do the estimated compute savings translate to actual wall-clock latency?

We measured three things.

  • Verification alone: on 10 Phi MATH questions with N=20, certified verification took 0.23 s against 0.87 s for full verification in a single batch, a 3.8× speedup [2.7, 7.3].
  • Verification with a cache: on 50 Phi MATH questions, REBASE width 20 spent 6.7 s per question on verification with 83.5% of its verifier input cached, against 0.23 s for certified N=20.
  • End to end: with a prefix-cached policy and a batched verifier (Phi MATH and Qwen OlympiadBench, 50 questions, two seeds), certified N=20 answered 13% and 24% faster than REBASE width 5, and 22% and 27% faster than DVTS 8, with accuracy differences within noise.

The large verifier savings translate into a smaller end-to-end gain over full verification, 4–9%, because generation takes most of the time. Against guided search, the gain depends on budget: at N=20, certified sampling was faster than REBASE width 5 and DVTS 8 in both settings, while at N=40, DVTS 8 was faster than certified sampling in both settings, as was REBASE width 10 on Phi MATH.

The accuracy comparison with REBASE is a little less decisive than the headline results suggest.

The new settings give clearer margins. At matched uncached cost, the paired differences exclude zero in four settings: +4.0 [1.5, 6.6] (Phi MATH), +7.75 [5.2, 10.5] (Phi OlympiadBench) and +11.2 [8.0, 14.4] (Qwen2.5/Granite MATH) at high budget, and +3.6 [1.7, 5.5] (Qwen3.5 MATH) at low budget. With both models cached, certified N=20 reaches REBASE's best accuracy at lower cost in all four. The original runs showed small margins, and we revised those claims. REBASE leads on GSM8K with Granite, and DVTS matches or leads at high budgets (see general response).

On the hardest MATH problems … Do you think this is mostly a limitation of the verifier, or … the candidate distributions?

Both: the wrong-group splitting experiment holds every score fixed and disperses wrong answers; MATH ordinary-vote accuracy rises from 46.5% to 58.4%. The rest of the gap comes from how the verifier ranks candidates. On Phi OlympiadBench, coverage rises from 54.5% to 65.1% between N=20 and N=80 while accuracy moves from 37.7% to 39.4%. Closing that gap needs better selection, and certification makes stronger selectors cheaper.

We believe the new models, verifier and latency measurements address your questions, and we would be grateful if you would consider updating your score. We are happy to clarify anything further.

Thanks for the detailed response and for running the additional experiments! I think the new results address a lot of my original concerns, especially around generalization across models and verifiers. It's good to see that the coverage vs selection gap holds across the new settings, and the stronger accuracy margins on MATH and OlympiadBench make the empirical results more convincing.

I also appreciate the actual latency measurements. The distinction between verification speedups and end-to-end gains is useful, and I think the new results give a much clearer picture of where certified selection helps in practice.

That said, I still have some reservations about how broadly the efficiency advantages generalize. The results seem fairly dependent on the model, budget, and search depth. In particular, DVTS and REBASE remain competitive or better in some settings, and the end-to-end improvements are more modest than the verifier-only savings suggest. I also think the persistent gap between coverage and accuracy on harder problems shows that better answer selection is still a pretty substantial open problem.

Overall, I think the rebuttal strengthens the paper and addresses several of my main concerns. I still see the coverage vs selection analysis as the strongest contribution, and the additional experiments make a better case for the proposed method. I'm happy to maintain my 3. I think it's a worthwhile contribution, but struggle to see the case for a 4 unfortunately.

Thank you for the thoughtful follow-up. We are glad the new experiments address your concerns on generalization.

On the advantage depending on model, budget and depth: one regime 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. Outside this regime, the results follow the analysis: certified sampling leads where guidance narrows coverage, and the stronger DVTS baseline is competitive when it keeps coverage high at higher budgets.

On end-to-end gains being smaller than verifier savings: against full verification, generation dominates wall time, so a 3.8× faster verifier gives a 4–9% end-to-end gain with identical answers. Against guided search, the gains are larger. In both timed settings, certified N=20 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 the gap on hard problems: we agree that selection remains open, and the analysis shows where it lies. On MATH Level 5 at N=80, independent sampling finds the correct answer on 67.2% of questions but selects it on only 27.6%. OlympiadBench shows the same with a different policy and verifier: from N=20 to N=80, Phi-4-mini's coverage rises from 54.5% to 65.1%, while its accuracy moves only from 37.7% to 39.4%. Because certification keeps weighted voting cheap, a stronger verifier or decision rule can be applied where the vote is close.

Reviewer_4o75OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper analyzes diversity and the dynamics of the answer histogram through guided search. The method proposes an algorithm for scoring independently sampled that scores samples until a threshold is reached and using these for a weighted majority vote. The intuition is that not every solution must be verified to decide the winner. They select solutions to verify based on the largest upper bound at a given point and stop once the winner is mathematically decided. This outperforms guided search and weighted voting. It conducts experiments on MATH and GSM8K with Qwen2.5 models.

Critical strengths
  • The motivation that guided search decreases the diversity of sampled outputs is sounds and correct. This is why majority voting or pass@K are worse after a guided search compared to independent sampling. REBASE is also a strong choice of guided search baseline.
  • The analysis on search methods and diversity is nice. I believe this is known by many people in the area but it is nice to show it in some clean experiments. I especially liked decomposing the performance gain in terms of enrichment and conditional voting.
  • I appreciate that the authors have made their code available in an anonymous repository during the review process.
  • I also think the idea behind the method is well-founded based on the analysis. The method outperforms guided search and weighted voting baselines at matched compute.
Critical weaknesses
  • The primary models and benchmarks used in this work have been extensively reported for data contamination eg. in the Qwen2.5 models on math benchmarks such as GSM8K and MATH (eg. https://arxiv.org/pdf/2507.10532). These models are also known to show strange behaviors on math RL tasks (eg. https://arxiv.org/abs/2506.10947). Additionally, I do not think it is acceptable to use Qwen2.5 models for the primary experiments in late 2026 now that there have been several strong open-source alternatives released in the last 2 years. Finally, for a work focusing on reasoning and test-time search, it is very important to have results on thinking models for the results to be meaningful for the community at this stage. These are absent in the work.
  • Besides the specific choice of benchmarks and models, it would be good to see a greater diversity of experimental settings. For example a few different models, domains other than math etc.
  • Some of the writing is confusing to read and not all of experiments are very clearly described.
  • Many of the ideas in this work revolve around majority voting, as does the primary introduced method. Though this is fine, it is worth noting many relevant domains today for parallel test-time scaling do not have identifiable answer classes (eg. code, proofs, open-ended problems), and this has resulted many of the prominent parallel test-time scaling methods today to support open-ended answer selection (eg. https://arxiv.org/abs/2509.26626). This weakens the relevance of this work for practical applications.
  • Though the method outperforms guided search and weighted voting baselines at matched compute, it ensures to give the same answer as weighted voting, though possibly at less compute. This is fine but it means that this is primarily a method for improving the efficiency of weighted voting and can't improve the performance ceiling. I don't find this to be a particularly exciting result since for reasons mentioned above, weighted voting cannot be used in many scenarios people care about.
  • There is one important downside of their algorithm which does not appear in the compute-matched plots. The algorithm presented is sequential as far as I understand in that it needs to select the next solution to score based on the current state. This goes against the ethos of parallel test-time scaling in that, though the method will be cheaper than weighted voting in terms of FLOPs, it cannot be obviously parallelized so I expect the wall-time would be much longer. This defeats the purpose of parallel test-time scaling to some extent since practically we want to be able to submit a large batch of requests to an inference engine and get the results in parallel. It also raises a number of other sequential scaling baselines that may be stronger. This is an important issue.
Questions for authors

See above.

5 comments
AuthorsOpenReview ↗

Answer to Reviewer 4o75

Thank you for the careful review and for pushing us toward newer models and harder settings. The additions below, most of which the revised PDF includes, made the paper stronger.

These models are also known to show strange behaviors … I do not think it is acceptable to use Qwen2.5 models for the primary experiments in late 2026.

We agree, and we added Qwen3.5-2B and a pipeline with no Qwen component, Phi-4-mini with Granite. Following the advice to validate across model families, we checked that the Phi-4-mini/Granite pipeline reproduces the coverage–selection gap, the enrichment and clustering decomposition, and the certificate’s savings. All methods in a comparison also share the policy and questions, so memorization lifts every method together.

It is very important to have results on thinking models.

We ran two small thinking models with independent sampling on MATH-500 (two seeds, N up to 32, an 8,192-token thinking budget), scoring only the final solution. With Phi-4-mini-reasoning and Granite, weighted selection reaches 93.4% at N=32 and certification uses 92% fewer verifier tokens than full verification, against 77% for Phi-4-mini-instruct. Answers agree so often that majority voting is as accurate (93.5%), and the certificate needs about two verifier calls per question; where weighting helps, as in our non-thinking settings, it scores more. Qwen3.5-2B mostly failed to finish within the budget (85% of samples hit the cap), so we draw no conclusion from it. Methods that search over long traces, such as Value-Guided Search, finish with a weighted majority vote, so our certificate could be applied to their final step as well.

Many relevant domains … do not have identifiable answer classes.

The certificate needs a mapping from candidates to answer classes. Math, code and many structured tasks provide one; for code, clustering by execution output gives the classes. The introduction now states this scope.

It ensures to give the same answer as weighted voting … can't improve the performance ceiling.

For a fixed pool, certification returns the same answer. At a fixed budget, its savings buy a larger pool, and the larger pool raises accuracy: at the uncached cost of REBASE width 20, certified N=80 scores 4.0 points higher on Phi MATH and 7.75 points higher on Phi OlympiadBench. With both models cached, certified N=20 reaches REBASE's best accuracy at 40–55% lower cost in six of our ten runs. Weighted selection also beats best-of-N (+3.3 points with Qwen3.5), and certification keeps that gain at lower cost.

The algorithm presented is sequential … I expect the wall-time would be much longer.

We submit all N chains at once, and they never wait for the verifier. The certificate then scores candidates in batches: with batches of four at N=80 it needs about four rounds or fewer on average in the new settings (3.8 on GSM8K and 7.6 on MATH in the original runs). REBASE and DVTS wait for the verifier at every level, up to 24 times per question at depth 24. We measured the result end to end, with a prefix-cached policy and a batched verifier (50 questions, two seeds). On Phi MATH and Qwen OlympiadBench, certified N=20 answered 13% and 24% faster than REBASE width 5, and 22% and 27% faster than DVTS 8, with accuracy differences within noise. Other pairings went the other way: at N=40, DVTS 8 was faster than certified sampling in both settings, as was REBASE width 10 on Phi MATH, and DVTS 4, which scores lower, was faster than certified N=20.

Some of the writing is confusing to read and not all of experiments are very clearly described.

Thank you for pointing this out. We added a protocol table (Appendix A.5) that lists, for each experiment, the population, budgets, depth and cost accounting, and we revised Sections 2 and 7 to state the setup of each comparison.

We hope these additions address your concerns, and we would be glad to answer any further questions.

Thank you for the new experiments. They did address some of my concerns.

Many relevant domains … do not have identifiable answer classes.

Thanks for clarifying this in the introduction. I think this is a major reason why weighted voting is not too commonly used. If the authors think code is a good domain for their method (I have seen some papers here but it is not widely done as far as I know) then they should test on it.

It ensures to give the same answer as weighted voting … can't improve the performance ceiling.

I understand that at a fixed budget you can run larger batches, I more so meant asymptotic performance at high compute (arguably more important as compute continues to grow) is bounded by weighted voting. This is not necessarily true for other baselines.

The algorithm presented is sequential … I expect the wall-time would be much longer.

I understand guided search is also sequential to some extent. I think overall the paper frames guided search as the main baseline but weighted voting is the more relevant baseline and the proposed method should be slower here. Eg. if 4 passes for verification are needed then verification wall time increases 4x when ample parallelism is available. This becomes more important when using an expensive LLM-judge model for the verifier (required for more realistic settings since we don't always have a PRM for tasks we care about).

My main concerns remain that:

  1. the analysis comparing to guided search is interesting but is already widely known in the community
  2. the method makes weighted voting (which is already not widely used because of the need for identifiable answer classes) cheaper in terms of FLOPs but more expensive in terms of wall-time. This doesn't seem like a very significant contribution to me.
  3. Only evals on math.

Thank you for the follow-up. We are glad the new experiments addressed some of your concerns.

On wall time against weighted voting: on the same GPU, with full verification run as a single batch, certified verification took 0.23 s against 0.87 s to producer the same answers, and needed only 1.2 rounds on average with batches of four (Appendix D.6). Certification can also apply to LLM judges that score each solution separately, such as generative verifiers that output the probability that a solution is correct [6]. When such a judge writes a verification rationale before scoring, each call is expensive, so every call the certificate skips saves correspondingly more.

On how widely weighted voting is used: it is a standard final step in test-time scaling, from weighted best-of-N [1] to the weighted majority vote that ends Value-Guided Search [2], and it beats best-of-N in our runs (+3.3 points [1.9, 4.8] with Qwen3.5). Certification makes it cheaper without changing a single answer.

On math only: we follow the standard evaluation for this comparison. The methods we compare against were themselves evaluated on math: REBASE [3], DVTS [1], and the compute-optimal scaling study of [4], because step-level guided search relies on process reward models, which exist mainly for math. Within that standard, we cover three policies, two verifiers, and three benchmarks of increasing difficulty, up to OlympiadBench.

On the analysis: prior work reports the coverage gap [5] and the loss of diversity under guided search [1]. We identify the mechanism, splitting guided search's voting gain into enrichment and error clustering with a controlled intervention, and it holds in every new setting, DVTS included.

References:
[1] Beeching, Tunstall and Rush. Scaling test-time compute with open models. Hugging Face blog, 2024.
[2] Wang et al. Value-Guided Search for Efficient Chain-of-Thought Reasoning. arXiv:2505.17373, 2025.
[3] Wu et al. Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving. ICLR 2025.
[4] Snell et al. Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Parameters for Reasoning. ICLR 2025.
[5] Brown et al. Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. arXiv:2407.21787, 2024.
[6] Zhang et al. Generative Verifiers: Reward Modeling as Next-Token Prediction. ICLR 2025.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response (1/2): new results

We thank all reviewers for their feedback. All three asked for broader evaluation, wall-clock evidence and stronger guided baselines. We added two policies, Qwen3.5-2B (non-thinking mode) and Phi-4-mini, a second verifier, IBM's Granite-3.3-8B-Math-PRM, and OlympiadBench (574 questions). All MATH results use the paper's MATH-500 questions. We ran DVTS at six budgets with four selectors and REBASE at widths 5, 10 and 20, and measured latency end to end. We also ran two thinking models (reply to 4o75).

The table gives accuracy (%) and mean uncached cost per question in TFLOPs. Each row pairs certified N=20 (low) or N=80 (high) with each baseline at its closest-cost budget. Appendix D.4 has the full grids. All rows use depth 24 except GSM8K (depth 12).

Policy / verifierDatasetBudgetCertifiedREBASEDVTS (weighted)
Phi-4-mini / GraniteMATHlow72.6 (967)66.5 (945)67.2 (652)
high74.1 (3,743)70.1 (3,718)75.8 (3,258)
Phi-4-mini / GraniteOlympiadBenchlow37.7 (1,608)29.2 (1,560)not run
high39.4 (6,224)31.6 (6,232)not run
Qwen2.5 / GraniteMATHlow63.9 (296)50.0 (442)not run
high67.0 (1,105)55.8 (862)†not run
Qwen2.5 / GraniteOlympiadBenchlow28.3 (604)25.7 (1,209)25.0 (859)
high30.6 (2,226)30.1 (2,533)31.8 (2,552)
Qwen2.5 / GraniteGSM8Klow78.3 (175)77.5 (220)no budget this low
high78.8 (656)§84.8 (821)81.6 (828)
Qwen3.5-2B / Qwen PRMMATHlow75.8 (1,716)72.2 (2,004)not run
high80.6 (6,848)75.6 (3,911)‡not run

†REBASE width 20: 59.3% at 1,699 TFLOPs. A second Qwen2.5/Granite MATH run (depth 12) gives 65.6% for certified N=80 and 60.4% for REBASE width 20. ‡Largest REBASE width, 43% cheaper, so not cost-matched. Certified N=40 reaches 78.5% at 12% lower cost. §Frozen last-step β=8 rule, tuned with the Qwen PRM. Granite's development split picks mean aggregation with β=14, which gives 82.7% (+3.9 [2.4, 5.5]).

Paired 95% intervals, certified minus baseline, in table order:

  • REBASE, low: +6.1 [3.5, 8.8], +8.5 [6.0, 11.2], +13.9 [10.9, 16.9], +2.6 [0.3, 5.0], +0.8 [−1.3, 3.0], +3.6 [1.7, 5.5].
  • REBASE, high: +4.0 [1.5, 6.6], +7.75 [5.2, 10.5], +11.2 [8.0, 14.4], +0.4 [−2.1, 3.0], −6.0 [−8.2, −3.9].
  • DVTS: low +5.4 [2.6, 8.2] and +3.3 [1.0, 5.7]; high −1.7 [−3.8, 0.4], −1.2 [−3.5, 1.0], −2.8 [−4.8, −0.8].

The proxy charges tree search for re-reading shared prefixes. With nominal FLOPs and both models cached, closest-cost pairing favors the guided methods on Qwen OlympiadBench and GSM8K, and DVTS throughout (Appendix D.5), so we also measured latency.

1. At low budget, certified sampling ran faster end to end than guided search at similar accuracy. With a prefix-cached policy and a stateless batched verifier (Phi MATH and Qwen OlympiadBench, 50 questions, two seeds), certified N=20 answered 13–24% faster than REBASE width 5 and 22–27% faster than DVTS 8, whose accuracy is within two points. At N=40 the picture is mixed: DVTS 8 was faster than certified sampling in both settings, and REBASE width 10 on Phi MATH. With a caching verifier, REBASE width 20 still spent 6.7 s per question on verification against 0.23 s for certified N=20. In six of our ten runs, certified N=20 reaches REBASE's best accuracy at 40–55% lower cost with both models cached.

2. Certification makes weighted selection cheap in every setting. At N=80 it used 78–92% fewer verifier tokens than full verification and cut total cost by 7–48%. The certificate is exact by construction, so any system that samples in parallel and votes with a verifier gets these savings with the same decisions.

3. Our analysis predicts when guided search wins. Across 32 matched pairs, the guided method's coverage relative to independent sampling correlates with certified sampling's margin (Spearman −0.49 [−0.64, −0.38]). DVTS keeps coverage high and matches or beats certified sampling at high budgets. REBASE at depth 24 shrinks coverage almost to its accuracy (33.6% vs 31.6% on Phi OlympiadBench), and certified sampling beats it there under every accounting.

These results support the paper’s main message: independent sampling already finds the answers, and certification lets a verifier select among them cheaply. Guided search remains a strong option when it preserves coverage, as DVTS does.

AuthorsOpenReview ↗

General response (2/2): changes to the paper

We uploaded a revised PDF. The main changes:

Claims

  • Abstract, introduction and conclusion. We replaced the single-accounting compute claims ("about a third less", "27% less") with the broader evidence from the new experiments: certified selection gives parallel sampling an exact, cheap way to use a verifier, reaches guided search's best accuracy at lower cost in most runs, answers faster end to end at similar accuracy at low budgets. The revised text also states when guided search competes (when it preserves coverage) and names the accounting behind every cost figure.
  • Scope. The introduction and limitations state that the certificate applies wherever candidates map to answer classes, as in math or in code grouped by execution output.

Main text

  • Section 2 introduces the new policies, verifier and dataset, and states the depth of every setting.
  • Section 7 adds a table of paired differences against REBASE and DVTS across the new settings, a paragraph on latency and caching, and a paragraph on when guided search wins. The Figure 6 caption names the uncached proxy.
  • Related work adds speculative rejection and early-stopping self-consistency.
  • Limitations and future work cover model scale, thinking models at full reasoning budgets, the policy-to-verifier size ratio, possible MATH-500 exposure for Qwen2.5 and the non-Qwen pipeline we added in response, and the dependence of rankings on depth and budget.

Appendix

  • A.5 Experiment protocols: for every experiment, the population, budgets, depth and cost accounting, with the answer-extraction rules in the text.
  • B.4 Decomposition across models: the enrichment and clustering decomposition on every new cohort, DVTS included, and the coverage-retention correlation.
  • D.4 New settings: full accuracy, coverage and cost grids for certified sampling, REBASE and DVTS (four selectors), every closest-cost pairing with intervals, and certification savings.
  • D.5 Cost with prefix caching: policy-only and two-model accountings, the matched-accuracy comparison across ten runs, and closest-cost pairings under caching.
  • D.6 Timing: verification-only timing, batched certification, the cached verifier replay, and end-to-end latency with paired ratios.
  • D.7 Anytime certification: the offline simulation of stopping generation early.
  • E.4 Selector sensitivity: REBASE with its best rule in hindsight, a rule selected on Granite's development split, and certification savings across rules.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.