acceptodds
Under review as a conference paper at ICLR 2027

Verify Until Decided: Exact Early Stopping for Weighted Voting

Abstract

Test-time reasoning systems sample multiple solutions, score them with a verifier, and select the parsed answer with the largest aggregate score. Dense execution verifies every solution even when the remaining scores cannot change the decision. We introduce Verify Until Decided (VUD), a sparse executor that avoids unnecessary verification while preserving the weighted-vote decision. For a fixed candidate pool, VUD uses a tie-aware certificate that is necessary and sufficient for winner invariance under all bounded assignments to the unseen verifier scores. A signed certificate extends this guarantee to candidates not yet generated, while a deferred controller preserves the dense finite-budget decision without increasing candidate generation or verifier calls on any instance. Across three public 8–9B generators and six reasoning benchmarks, covering 2,304 model–question instances, VUD reproduces every dense ThinkPRM decision at N = 8 for the same verifier-score realization while using 52.4% fewer verifier calls than a matched dense executor. One full-matrix online pass reduces verifier-only wall time by 18.8–40.3% across three scorer interfaces. With CISC, FutureCert saves 15.3% of candidates, and the full two-layer executor saves 9.1–17.5% of generation-plus-scoring wall time across generators. Prospective ThinkPRM runs save up to 48.7% end-to-end wall time at N = 16. VUD changes execution, not the scoring rule, terminal budget, or decision for a fixed realization.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Test-time scaling, Efficient inference, Selective verification, Weighted self-consistency, Certified early stopping

Reviews

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

The paper proposes Verify Until Decided (VUD), an executor that reduces computation while preserving the result of a specified finite weighted vote. The authors introduce "ScoreCert", which stops acquiring verifier scores once bounded score intervals establish an invariant winner; and "FutureCert" which extends this reasoning to candidates not yet generated. The certificates account for tie priority and signed scores, and a deferred controller combines generation stopping with terminal score acquisition. Experiments report identical decisions on 2,304 fixed candidate pools, with 52.4% fewer ThinkPRM calls beyond a shared zero-call gate. Additional experiments measure verifier-only and generation-plus-scoring wall time. The guarantee preserves the dense selector’s decision under common score realizations and numerical semantics; it does not guarantee answer correctness.

Critical strengths
  1. The preserved target and stopping guarantee are precise. The fixed-pool certificate is necessary and sufficient under the declared interval information. The future-candidate extension handles unseen answer groups and negative scores, while explicitly distinguishing safe termination from optimal query selection. This provides a checkable execution contract rather than relying only on observed agreement.
Critical weaknesses
  1. The presentation makes the core contribution unnecessarily difficult to understand. The introduction moves into VUD, ScoreCert, and FutureCert before giving a sufficiently concrete explanation of the problem and proposed solution. CISC is used without expanding the acronym. I had to reconstruct the basic algorithm from definitions, theorems, and scattered experimental descriptions. A worked example before the formalism would help distinguish the central idea from its implementation details and extensions.

  2. The novelty and practical significance are not sufficiently established. The central principle - stop once the remaining unknown outcomes cannot change the winner - is intuitive and closely related to existing bound-based stopping methods. The paper does not clearly identify the nontrivial technical advance beyond applying this principle to LLM weighted voting. The experiments demonstrate savings against complete execution, but provide limited evidence about the value of the proposed query policy relative to simpler policies. Furthermore, execution details and cost scopes are scattered across the manuscript, making it difficult to determine when the reported savings would translate into a meaningful practical benefit.

Questions for authors
  1. What is the principal technical novelty? Please explain, using a concrete example and plain langauge, what your method adds beyond maintaining bounds on partial totals and stopping when the winner is fixed. How does this differ technically from existing exact aggregation and partial-evaluation methods?

  2. What does the proposed query policy contribute? With the same stopping certificate, how does the largest-upper-bound policy compare with simple fixed or random query orders in verifier calls and wall time?

  3. How should a practitioner interpret the timing results? Please provide a consolidated description of the execution setup for each timing experiment: scorer interface, batching and concurrency, caching, included costs, and whether candidate generation is independently executed or shared between paths. Under which configurations does the method deliver substantial end-to-end savings?

  4. What explains the gap between frozen-score and online CISC results? Table 2 reports 81.96% versus 42.44% call savings. Appendix G mentions fresh score acquisition, but were the score transformations, bounds, and batch-check schedules otherwise identical? Which result best represents the intended deployment setting?

  5. What is the setup of the experiment? It is very hard to interpret from the paper about the actual experimental setup.

3 comments
Reviewer_9X6EOpenReview ↗

Two follow-up questions

Thank you for your thorough answer and the added tables. I appreciate your effort to polish the article and pull out extra information to clarify your novelty and technical challenges.

First, I acknowledge that the presentation has slightly improved. Adding worked examples in the Introduction, walking through Figure 2, and consolidating serving/batching setups in Appendix M (Table 23) make the paper clearer, though there is still room for writing improvement.

However, because the revised exposition and new ablations (Tables 4, 12, 19, 20, 22, 26) lay out the mechanics and numbers transparently, they also expose fundamental contradictions between the paper's theoretical selling points and empirical results. I am maintaining my score for now, and look forward to the authors' response to convince me to increase it:

Q1. Contradiction in the Signed-Weight Certificate (FutureCert with ℓ<0\ell < 0)

In Question 1, you emphasize that a key contribution beyond standard interval bound-checking is Theorem 2's handling of negative weights during generation (e.g., totals A=0.8,B=0.1A=0.8, B=0.1 with weights in [−1,0.2][-1, 0.2], where a future candidate joining AA at −1-1 changes the winner).

Yet across all real scorers evaluated, the only negative-weight rule is centered CISC wi=2pi−1∈[−1,1]w_i = 2p_i - 1 \in [-1, 1] (Tables 2B, 26). For your deployed controller (Deferred VUD, Sec. 3.2, making no verifier calls before Nmax⁡N_{\max}), whenever ℓ<0<u\ell < 0 < u, the score-free bound is Lg=∣Cg∣ℓ<0L_g = |C_g|\ell < 0 and c=min⁡{0,ℓ,−u}<0c = \min\{0, \ell, -u\} < 0. Thus, the new-group condition in Theorem 2 (Lg−u+(r−1)c≥0L_g - u + (r-1)c \ge 0) is strictly negative for all r≥1r \ge 1 and never holds -- so score-free FutureCert saves 0% of generation whenever ℓ<0<u\ell < 0 < u.

In Sec. 3.2 (lines 248-253), you note Theorem 2 could still hold with observed scores (as in your A=0.8,B=0.1A=0.8, B=0.1 example) or "in some nonpositive-score regimes." However:

  1. In any non-trivial nonpositive regime (ℓ<u≤0\ell < u \le 0), every score is ≤u≤0\le u \le 0, so even with observed scores, Lg≤∣Cg∣u≤uL_g \le |C_g|u \le u and c=ℓ<0c = \ell < 0. Thus Lg−u+(r−1)c≤(∣Cg∣−1)u+(r−1)ℓ<0L_g - u + (r-1)c \le (|C_g|-1)u + (r-1)\ell < 0, which is impossible for all r≥2r \ge 2 (and for r=1r = 1 score-free), since adding candidates makes a group's sum more negative while a new singleton group can score uu.
  2. As for querying scores online during generation under ℓ<0<u\ell < 0 < u, the paper never deploys or evaluates such a controller.

Meanwhile, for fixed-pool ScoreCert (Table 26), switching from exp⁡(pi−1)∈[1/e,1]\exp(p_i - 1) \in [1/e, 1] to 2pi−1∈[−1,1]2p_i - 1 \in [-1, 1] yields the exact same dense winners on all 2,304 pools while cutting call savings nearly in half (81.96% to 42.41%).

Given that (i) deployed score-free FutureCert never stops early when ℓ<0<u\ell < 0 < u, (ii) the nonpositive regime (ℓ<u≤0\ell < u \le 0) cannot stop early for r≥2r \ge 2 even with observed scores, and (iii) your only real-data signed rule (2pi−12p_i - 1) yields identical winners to exp⁡(pi−1)\exp(p_i - 1) on all 2,304 pools while halving ScoreCert savings, in what realistic LLM test-time scaling scenario is the signed-weight formulation actually useful?

Q2. Contradiction in Positive-Floor Stopping (Tables 12 & 22) and Query Order (Tables 4 & 19)

When weights are non-negative (ℓ≥0\ell \ge 0), certificates reduce to simple interval checks (Lg>UhL_g > U_h). For ScoreCert (Table 4), naive Input Order captures 84.2% of call savings on ThinkPRM (7,279→4,1307,279 \to 4,130 vs. 3,5143,514 for Max-upper) and 91.4% on CISC (7,279→1,8257,279 \to 1,825 vs. 1,3131,313) across 2,304 pools (in Table 19, 1.5B verifier Input Order takes 4.497s4.497\text{s} vs. 4.186s4.186\text{s}, and the 48-pool ThinkPRM gap rests on just 11 non-gated questions -- 31 vs. 44 calls -- amplified by 8,172-token outliers). End-to-end savings with the 1.5B verifier are ~1.5% (Table 20).

For FutureCert, score-free stopping requires a high positive floor ℓ=exp⁡(−1/T)\ell = \exp(-1/T), tested via CISC. Comparing full accuracy (Table 12) with held-out TT tuning (Table 22) reveals a clear dilemma:

  1. On Qwen and Granite, unweighted SC (ℓ=u=1\ell = u = 1) achieves higher accuracy than CISC in Table 12 (86.59% vs. 86.33% on Qwen; 70.83% vs. 70.57% on Granite), while saving 37.59% of generation (Table 6, vs. 15.29% for CISC) with 0 verifier calls. In Table 22, T=1T = 1 is chosen only because all 10 temperatures (T∈[0.01,10]T \in [0.01, 10]) tied on dev accuracy (165/192 and 138/192) and your tie-breaker minimized ∣log⁡T∣|\log T| instead of choosing T=10T = 10 or unweighted SC (which has identical dev accuracy and doubles generation savings).
  2. On GLM -- the only model in Table 12 where CISC beats SC (77.21% vs. 76.95%) and dev accuracy varies with TT -- tuning selects T=0.05T = 0.05 (ℓ=e−20\ell = e^{-20}), where FutureCert saves 0.00% of candidates and -0.17% of time.

Across the entire paper, is there even a single generator where (a) CISC at its accuracy-selected temperature beats unweighted SC (or T=10T = 10), and (b) FutureCert delivers non-zero generation savings at that temperature?

AuthorsOpenReview ↗

Response — follow-up

Thank you for the follow-up. We have clarified the role of the signed extension and added matched execution experiments.

Q1

Support for negative weights is an extension of VUD's guarantee, not its principal contribution. Your analysis of the original deferred controller is correct: with mixed-sign bounds and no observed scores, it cannot stop generation early. In a nontrivial nonpositive interval, the new-group condition also fails with two or more slots remaining, even with observed scores. We have removed “some nonpositive-score regimes” and clarified the contribution in the Introduction.

The signed condition is useful when executing a rule that already uses negative contributions. It preserves that rule while accounting for a future candidate lowering the leader's total. Simply shifting every weight upward can change the winner, because larger answer groups receive a larger bonus.

We also checked this use case on the same 2,304 centered-CISC score vectors as Table 26, keeping the weights 2p−1, bounds [−1,1], and N=8. The added interleaved schedule queries scores once two answer groups are visible and a certificate could become attainable. Table 29 reports counts on these score vectors:

Centered-CISC executionGenerated candidatesScoring calls
Dense18,4327,279
Original deferred VUD18,4324,192
Interleaved VUD17,4085,194

All 2,304 selected answers match dense. Interleaving saves 5.56% of candidates and 28.64% of scoring calls relative to dense. It uses more calls than deferred, in exchange for fewer generations. Seven of the early-stopped pools include an observed negative score. Thus the observed-score case occurs in the evaluated data; the zero-generation-saving result applies to the score-free controller. This comparison measures counts, not online time.

This does not change the comparison between voting rules in Table 26: exponential CISC at T=1 gives the same winners with fewer queries, so these data do not favor choosing centered CISC. The signed extension preserves an existing signed rule; it is not a reason to introduce negative weights.

The main contribution is the stopping characterization: ScoreCert handles unknown scores in a fixed pool, and FutureCert also handles candidates that may join existing groups or introduce unseen answers. Both retain the original tie rule and give necessary and sufficient conditions under the stated score bounds. The nonnegative-score experiments below test their practical value without relying on the signed extension.

AuthorsOpenReview ↗

Response — follow-up

Q2

GLM provides the requested case with the added interleaved schedule, at the original development-selected CISC temperature T=0.05. The original deferred schedule still saves no generation at this temperature. Scoring during generation lets FutureCert stop with the same temperature and voting rule.

Using Table 22's original split and grading convention, CISC at T=0.05 answers 153/192 development questions and 443/576 test questions correctly, compared with SC's 151/192 and 440/576. GLM's T=0.02 and T=0.05 tie on development accuracy; we retain T=0.05 from the original tie rule. For Qwen, SC and all ten CISC temperatures tie at 165/192; for Granite, SC scores 139/192 versus CISC's 138/192. Extending selection to include SC, with lower execution cost resolving accuracy ties, selects SC for Qwen and Granite and retains CISC T=0.05 for GLM. These accuracy differences belong to the voting rules. VUD's contribution is to preserve the selected rule's answers while reducing its execution cost.

For GLM/CISC, we check FutureCert after each candidate. Once two answer groups are visible, we query scores in max-upper order if they could establish the certificate; otherwise, we continue generating. Weights remain in [exp(−20), 1], and the budget remains N=8.

GLM/CISC, T=0.05, N=8; 576 test questionsGenerated candidatesScoring calls
Dense4,6082,051
Original deferred VUD4,6081,121
Interleaved VUD4,4171,540

All three return the same answer on every test question. Relative to dense, interleaving saves 4.14% of candidates and 24.91% of scoring calls. Dense already skips scoring single-answer pools. Waiting for two groups retains this optimization: every queried score is needed by dense. Deferred saves more calls here; interleaving also avoids 191 generations.

For example, after six candidates on one online GSM8K question, the leading answer's observed total is 2.996 and the rival's is 0.556. The two remaining candidates can raise the rival to at most 2.556, or give a new answer at most 2. Neither can overtake the leader, so both generations are skipped.

We ran the same controller online on the existing 48-question, six-task GLM roster. Both paths independently generated candidates and acquired scores. Total time fell from 53.90 to 52.74 seconds per question (2.14%), with all 48 answers unchanged. Appendix O, Tables 27–28 reports the full-test counts and paired timing.

The released 1.5B verifier gives a larger generation and total-time benefit, using its original probabilities and bounds [0,1]. Scoring with one visible answer group can establish a lead earlier, but may require scores that dense would skip. Across all 2,304 pools, candidates fall from 18,432 to 14,514 (21.26% fewer), while calls rise from 7,279 to 12,189. Every dense answer is preserved.

Table 30 compares both paths on the six-task roster, with 48 questions per generator:

Generator, released 1.5B, N=8Candidates: dense / VUDCalls: dense / VUDSeconds/question: dense / VUDTime saved
Qwen384/29388/26141.72/33.8918.76%
Granite384/311186/24150.74/42.7315.78%
GLM384/301158/24254.30/46.5714.23%

Both new online experiments use one paired pass, matched per-candidate seeds, singleton BF16 requests, and no prefix cache. Each dense/VUD pair runs independently on the same H800, with execution order alternated across questions. Time includes generation, parsing, all scoring used by the controller, and certification; loading, warm-up, and post-run checks are excluded. All 144 released-verifier pairs return identical answers, with matching common candidate prefixes and independently acquired scores. The earlier approximately 1.5% total-time saving concerned fixed-pool ScoreCert, which leaves generation unchanged. Each new timing comparison uses matched dense settings and includes generation.

For query order, the certificate supplies most of the savings; max-upper adds a further reduction. We fix the certificate, scores, and candidate order across all 2,304 pools. Further reduction is (input-order calls − max-upper calls) / input-order calls:

ScorerInput-order callsMax-upper callsFurther reduction
ThinkPRM4,1303,51414.92%
CISC, T=11,8251,31328.05%
Released 1.5B4,4453,97410.60%

For ThinkPRM, max-upper uses fewer calls on 384 of the 954 multi-answer pools, the same number on 547, and more on 23; each generator's total falls. This full-matrix result does not depend on critique length. In the released-verifier timing control, mean scoring time over the 128-pool roster falls from 4.497 to 4.186 seconds across five repeats (Table 19).

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

This work proposes a framework for early stopping of verification for a fixed candidate pool of generations. The authors propose a sparse execution paradigm, Verify Until Decide (VUD), which mitigates unnecessary verification. It proposes ScoreCERT, which decides when one can stop querying the verifier on a fixed candidate pool and FutureCERT, which helps decide when to stop generating more candidates. Empirical results show that FUTURECERT+SCORECERT provided savings in number of generations, verifier calls and end-end latency.

Critical strengths
  1. i think the focus on saving verification compute cost and also mitigate latency is crucial for sustainable test-time scaling.

  2. This would also help scale to larger pools and potentially break past palteauing effect of TTS due to verifier bottlenecks through more coverage at a sustainable cost .

Critical weaknesses
  1. The paper is quite hard to read, and some introduced jargon do not contribute much to the technical understanding and seems to lack meaning without additional context. Figures are not referred to or broken down with explanations. For instance, I could not see Figure 2 referred to anywhere in the sections. For instance. Figure 2 mentions a deterministic parser, but it is not clear as to which parser was employed and how its outputs were consumed downstream. Hence, Figure 2 causes more confusion rather than clarifying the technical aspects of the paper. Also, the term "legal" is overloaded. When it refers to generations, does it mean generations that are complete or if they conform to a certain format ?. And what does the term " legal " mean in context of "legal group intervals" ? In lines 44-45 ?

  2. In continuation to the above point, firstly, it is not clear how the groups are formed. is it based on semantic matching of answers? How are subtle differences in answers handled that may not be captured by semantic matching? Or are you enforcing only strict exact matches for the grouping?

  3. While I agree that with ThinkPRM the verification cost and latency may be significant, I think it is necessary to establish how much of the inference latency and computational cost verification contributes to. This is essential for the core motivation of this work, which is to optimize verification savings on unnecessary calls. And I think it is also useful to use your proposed VUD framework with diverse generative and discriminative PRMs to establish how the savings vary across different verifier paradigms, to ensure the results are not an artifact of just ThinkPRM-based verification.

  4. Experimental details are lacking in the current version of the paper. Is the wall clock time reported for latency the average one per query (averaged across queries in test set) ? If so, why is only the mean time reported without the standard deviation?

  5. From Table 11 ThinkPRM only seems marginally better than self-consistency and sometimes worse (QWEN, MMLU). This again brings me back to the premise of this work, which is that ThinkPRM is probably required for superior TTS performance, which might be.

Questions for authors

Please check my points in weaknesses

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

The paper studies how to execute a finite verifier-weighted vote while avoiding computations that cannot affect its result. For a known candidate pool, SCORECERT maintains lower and upper bounds on each answer group's total score and stops verification once the winner is fixed under every legal assignment of the remaining scores. FUTURECERT extends this reasoning to candidates that have not yet been generated, including new answer groups and signed scores. A deferred controller either certifies the answer without verification or reaches the terminal budget and invokes SCORECERT. The guarantees preserve the specified dense decision for a fixed score realization and numerical contract. Experiments across three generators, six reasoning benchmarks, and several scoring interfaces measure decision agreement, verifier calls, and wall time.

Critical strengths
  1. The paper defines its exactness target carefully and follows through on the details needed to support it. The fixed-pool certificate is both sufficient and necessary under the declared interval information, and the future-candidate extension handles a subtle issue with signed scores: future candidates can hurt the current leader by joining its own group. Tie priority, invalid parses, and numerical arithmetic are treated explicitly. I also appreciate the distinction between agreement conditional on the same scores and reproducibility across independent model runs. These details make the guarantee useful as an execution contract, with a clear account of what must be preserved by an implementation.

  2. The empirical evidence for reducing verification is convincing. Across 2,304 pools, ThinkPRM calls fall from 7,279 to 3,468, a 52.36% reduction, with no changes to the dense answers on the common score vectors. Both methods already skip scoring single-answer pools, so this is a meaningful gain beyond that simple optimization. The full-matrix timing experiment reports a 40.29% reduction in ThinkPRM verification time. On the 48-question repeated timing study at N=16N=16, the reported savings including generation are 48.7% for Qwen and 43.6% for Granite. The shared candidate pools, counterbalanced timing, and reporting of unfavorable cases make these results more persuasive than call counts alone.

Critical weaknesses
  1. The algorithmic advance is modest, and the experiments do not establish the value of the proposed acquisition policy. For a fixed pool, the central argument is a direct comparison of attainable lower and upper aggregate scores. This has a close conceptual precedent in exact aggregate query processing, such as Fagin et al. [1], although the access models differ. The tie handling and signed extension are useful, but I see the main contribution as adapting and evaluating this approach for verifier-weighted reasoning.

    That makes it particularly useful to know how much the proposed query order contributes. The experiments largely compare against dense scoring, without comparing simple query orders that use the same certificate. Querying the group with the largest upper bound and its earliest unscored candidate is reasonable, but the results do not establish how it compares with input order, random order, or a round-robin policy. The paper derives the hindsight-minimal certificate size, yet does not report the empirical gap to it. These comparisons would distinguish the benefit of stopping as soon as a certificate holds from the benefit of choosing which score to acquire next.

  2. The practical benefit depends strongly on the scoring interface, and the evidence leaves the broader accuracy–cost trade-off unresolved. The substantial ThinkPRM savings are valuable, but at N=16N=16 the released 1.5B verifier saves 28.6% of verification time and only 1.5% of total time. With bounds [0,1][0,1] and no observed scores, the deferred controller cannot stop generation early. The reported generation savings come from settings with a useful positive score floor: CISC saves 15.29% of candidates at T=1T=1, but none at T=0.5T=0.5 (Table 8). Since the main temperature is fixed rather than selected on held-out accuracy, it remains unclear how much generation can be saved at the temperature one would choose for answer quality.

    The fixed-budget comparisons isolate the execution savings well, but a practical choice also involves selecting the candidate budget and scoring method. The paper's cross-budget control is informative: certified N=8N=8 remains 27.89% slower overall than optimized dense N=4N=4. These systems have different target decisions and accuracies, so this does not establish that the smaller pool is preferable. It does, however, show why savings at a fixed budget are insufficient to establish a better accuracy–cost trade-off. A common comparison across candidate budgets and scoring interfaces would help determine where the method improves that trade-off. The paper acknowledges these boundaries, but they limit the practical evidence available to compensate for the modest algorithmic advance.

I lean toward weak rejection. The paper specifies its correctness conditions carefully and demonstrates real savings, particularly with an expensive verifier. My reservation is whether this amounts to a sufficiently strong contribution. The stopping certificate is straightforward, the acquisition policy lacks basic comparisons, and the practical gains depend on the scoring interface and operating point. Stronger acquisition controls and a clearer comparison of total cost at comparable answer quality could change my assessment.

References

[1] R. Fagin, A. Lotem, and M. Naor. Optimal Aggregation Algorithms for Middleware. Proceedings of the ACM Symposium on Principles of Database Systems, 2001.

Questions for authors
  1. How does the proposed query policy compare with input order, random order, and round-robin querying when all use the same stopping certificate? Since the hindsight-minimal certificate is already derived, could you also report the gap to that lower bound on the existing score vectors?

  2. What generation and total-time savings remain when the CISC temperature is chosen on held-out answer accuracy? Please report the selected temperature and the corresponding dense accuracy alongside the savings, since changing temperature changes both the score floor and the target vote.

  3. Could you place dense and VUD execution on common accuracy-versus-total-time curves across the evaluated candidate budgets, including generation and using matched scoring settings? The existing certified N=8N=8 versus dense N=4N=4 comparison is useful. Which operating points improve the observed trade-off, and how does this depend on whether ThinkPRM or the released verifier is used?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.