acceptodds
Under review as a conference paper at ICLR 2027

From Discovery to Decision: Finite-Budget Recoverability in LLM Voting

Abstract

Voting over multiple LLM responses is a common primitive in test-time scaling and ensemble inference. Collecting more responses can expand the candidate pool and increase the chance that a correct answer is discovered. Under a fixed call budget, a discovered answer still needs to accumulate enough support within the remaining calls to become the final plurality winner, creating a discovery-to-decision gap. In this work, we characterize this gap through the realized vote state and remaining call budget. We derive a sharp recoverability threshold and show that, as sampling proceeds, the observed candidate set can only expand while the set of reachable endpoint winners can only contract, inducing a candidate-level conversion window. Under a specified iid response law, the same state yields exact finite-horizon endpoint probabilities. We further show that merging wrong-answer identities preserves single-call correctness and cannot improve plurality accuracy, and that the effect of redistributing wrong-answer probability depends on the realized vote state. Singleton reachability yields a gold-free exact locking certificate. For a known answer universe, its first trigger is the earliest prefix at which all admissible continuations yield the same fixed-budget output. Empirically, most discovered-but-unselected correct answers lose reachability only after discovery. In a controlled Word16 study, input permutation improves raw-plurality accuracy by 21.1 points with essentially unchanged single-call correctness. Exact locking saves 28–30% of calls at a 16-call budget while preserving every fixed-budget output.

Primary area:
foundation or frontier models, including LLMs
Keywords:
test-time scaling, LLM voting, finite-budget recoverability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.60 over 5 reviews, above 70% of the others.
Reviewer_znyoOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper examines plurality voting for repeated LLM responses with a fixed call limit. It distinguishes between two events: a correct answer occurs in the sample set, and the voting process selects that answer as the final output. The authors use the current vote totals and the number of remaining calls to calculate whether each candidate can still win. They show that, as sampling continues, the set of candidates that can win can only decrease. The authors also examine how the distribution of incorrect answers affects plurality accuracy. They propose a change to the input order for each call. This method increases the variation in incorrect answers.

Critical strengths

The empirical evaluation is complete and clear. It includes multiple models, tasks, and studies that the authors specified before the evaluation. The authors also report results that are inconclusive or negative.

Critical weaknesses
  1. The reachability threshold compares the differences between vote totals with the remaining call budget. The authors state that this method is the classical deterministic curtailment method from sequential analysis.
  2. The claim about the earliest safe stop follows directly from the definition of the certificate. The lock-time law uses standard renewal theory.
  3. The ensemble-learning literature has established that repeated and correlated incorrect answers decrease the accuracy of majority voting. Thus, the error-competition analysis gives little new conceptual information.
  4. The method operates only after sampling. It does not help the model find correct answers. Finding correct answers is the main unresolved problem in test-time scaling.
  5. Input permutation gives a large improvement on one synthetic task. However, this improvement is small on new MMLU-Pro inputs. Thus, the results do not show that this method applies generally.
Questions for authors

Please address the concerns in the Weaknesses section. Specifically, clearly explain how the concept differs from classical deterministic curtailment. Also explain how the framework can improve the sampling process and not only the aggregation process. These explanations could significantly change my assessment.

3 comments

Short answers to the two explanations you ask for.

How does the concept differ from classical deterministic curtailment? The curtailment stopping criterion asks whether the current leader can still be overtaken. The paper tracks the set of answers that can still win, for every candidate at every call (Proposition 2.1). The stopping rule of Section 5 is the special case in which that set has one element, and there the two coincide. The additional analyses concern when candidates lose reachability and how their endpoint probabilities respond to changes in the response law. Of 553 failures in which the correct answer was sampled, 479 still had a reachable correct answer when it was found and lost it during the remaining calls (Appendix E.1, Table 3).

How can the framework improve sampling? It shows where the loss is and gives the sampler a target for it. On public MATH samples from Llama-3-70B at a budget of 16, 20.0 points of accuracy are lost because the correct answer is never sampled and 21.4 points because it is sampled and then not selected. At a budget of 1,024, more sampling has cut the first loss to 4.8 points, and the second has grown to 34.8 points (Appendix E.4, Table 6). Sampling more closes most of the discovery gap on this benchmark and leaves the larger loss in place. That loss depends on which wrong answers the sampler produces and how often (Section 4). A sampling-side change aimed at this target, input permutation, raised Word16 accuracy by 21.1 points [14.1,28.1][14.1, 28.1], with a small transfer to MMLU-Pro that we discuss under Weakness 5. On 384 fresh MMLU-Pro inputs it also raised the share of inputs on which the correct answer is sampled, from 84.9% to 89.1% (+4.2+4.2 points [1.8,6.8][1.8, 6.8], Appendix G.4, Table 17).

The responses below give the details for each weakness.

Weakness 1 and Question: Difference from classical deterministic curtailment

Weakness 1: The reachability threshold compares ...

Question: Please address the concerns ...

Response: The difference is the object of study. Curtailment is a stopping rule: it asks at each call whether the current leader can still be overtaken. Our analysis tracks, for every candidate answer at every call, whether that answer can still win. The stopping rule of Section 5 is the special case in which one answer remains, and it coincides with classical deterministic curtailment, as the paper states in its related-work section.

Classical deterministic curtailmentThis paper
QuestionCan sampling stop without changing the result?Which answers can still win, and at which call is each one lost?
ObjectThe current leaderEvery candidate answer at every call (the reachable set, Proposition 2.1)
What it yieldsA stopping timeThe stopping time (Section 5, where the two coincide), the timeline of lost correct answers (Section 3), and the effect of changing the wrong-answer distribution (Section 4)
SettingA fixed set of outcomesAbstentions that consume budget, answers not yet seen, fixed tie-breaking, weighted votes

Tracking every candidate yields the set of answers that can still win and, for each answer, the last call at which it can still be rescued. Four results follow from this wider view.

  • A timeline of failure. In forced-choice MMLU-Pro, 74 of the 553 failures in which the correct answer was sampled are already out of reach when it first appears, 311 by call 12 and 507 before the final call (Appendix E.1, Table 3). In the other 479 the answer was still reachable when found and was lost during the remaining calls.
  • Effects of interventions. The same state gives the effect on the final outcome of changing the wrong-answer distribution (Proposition 4.2). A controlled recoding of the wrong answers was predicted to raise accuracy by 1.03 points and raised it by 1.06 [0.46, 1.82] (Appendix F.5, Table 14).
  • The LLM setting. Classical treatments fix the set of outcomes. Our statements explicitly address abstentions that consume budget, answers not yet seen, fixed tie-breaking, weighted votes, and adaptive or dependent calls (Sections 2 and 5), distinguishing the assumptions needed for pathwise guarantees from those needed for probability calculations. For unit votes, the unseen-answer guard costs at most one additional call relative to the known-universe certificate.
  • A quantitative law for this setting. The certificate's saving tends to m/(1+m)m/(1+m) for modal margin mm (Theorem 5.3). The paper adds a central limit theorem and plug-in finite-budget predictions that match observed savings within 0.1 points at budgets from 16 to 1,024 (Appendix H.2, Table 23). As far as we know, previous LLM voting work that uses the rule reports its savings empirically.

Section 5 of the revised paper now names the rule as deterministic curtailment where the certificate is introduced, and Appendix J.1 (Table 32) contains the comparison above.

Weakness 2: Earliest safe stop and lock-time law

The claim about the earliest safe stop follows directly from the definition of the certificate. The lock-time law uses standard renewal theory.

Response: We agree that the earliest-stop characterization is direct and that the renewal argument is standard, as the paper notes. The results matter for what they settle in practice.

Under the retained-unit-vote information model, the earliest-stop result gives a hard limit: no universally output-preserving prefix rule can save more than half of the calls (Theorem 5.3(iii)). For users of adaptive self-consistency (ASC) or early-stopping self-consistency (ESC), which save more, it settles what is traded: in the known-universe setting, any rule that stops before the certificate gives up the universal guarantee that its output equals the full-budget answer (Remark 5.2).

The law turns the saving into a prediction from a reference sample of the response law. Predictions match public GSM8K runs within 0.1 points at every budget from 16 to 1,024 (Appendix H.2, Table 23). The law also explains why savings on public MATH level off at 15.8% and 26.3%: the margins there are small (means 0.24 and 0.45), and the per-problem asymptotes average 15.75% and 26.25% (Table 24).

In LLM voting the savings of this rule have so far been reported from experiments alone, to our knowledge. What the paper adds for this setting is the almost-sure form, a central limit theorem with explicit variance σ2/(1+m)3\sigma^2/(1+m)^3, budget-consuming abstentions, the open-universe rule, validated finite-budget predictions and, since submission, dependent votes.

Weakness 3: Error competition and the ensemble literature

The ensemble-learning literature ...

Response: The ensemble literature already establishes the average statement: correlated errors hurt majority voting. Proposition 4.2 is sharper: whether concentrating errors hurts depends on the current vote state, and the effect can go in either direction.

Take one remaining call and probabilities (0.3,0.6,0.1)(0.3, 0.6, 0.1) for the correct answer and two wrong answers aa and bb. Moving 0.1 of probability from aa to bb makes the errors more diverse. It lowers the probability that the correct answer wins from 0.9 to 0.8 at vote counts (2,0,1)(2,0,1) and raises it from 0.4 to 0.5 at counts (2,1,0)(2,1,0). No statistic of the response distribution alone, such as diversity, correlation or collision probability, can therefore order accuracy.

The data also caution against interpreting concentration alone. A validity filter on Word16 removed 85% of wrong votes and made the remaining wrong answers more concentrated (collision probability up by 0.24), yet accuracy rose from 74.2% to 92.2% and no input was damaged.

The state-dependent account is also predictive: where forecasts frozen before generation predicted an effect above 0.02 in magnitude, the sign was right in 29 of 32 states. More directly, the full-state forecast improves squared error over a control that preserves the wrong-answer probability spectrum and collision but shuffles the identities carrying that mass by 0.0030 [0.0004, 0.0068] (Appendix F.5, Table 12).

The revised Section 4.1 states this contrast with the ensemble literature directly after Proposition 4.2, and the related work repeats it.

Weakness 4 and Question: Improving the sampling process

Weakness 4: The method operates only after sampling. It does not help the model find correct answers. Finding correct answers is the main unresolved problem in test-time scaling.

Question: Also explain how the framework can improve the sampling process and not only the aggregation process. These explanations could significantly change my assessment.

Response: The framework changes what a sampler should be optimized for, in four concrete ways.

  1. Finding the correct answer is often not the binding step. At B=16B=16, between 2% and 46% of trajectories that sample the correct answer still end with a wrong output. On public MATH samples from Llama-3-70B, the correct answer is sampled in 80.0% of trajectories at a budget of 16 and in 95.2% at 1,024, while plurality accuracy moves from 58.6% to 60.4% (Appendix E.4, Table 6). At 1,024 calls, 4.8 points are lost to never finding the answer and 34.8 points to finding it and not selecting it. A sampler tuned for coverage alone leaves this gap untouched.
  2. The sampler gets a second target: which wrong answers it produces. At a fixed single-call accuracy of 0.3, splitting one wrong answer into 32 raises 16-call accuracy from 7.4% to 88.7%. Input permutation is a change on the sampling side. On Word16 it raises accuracy by 21.1 points [14.1, 28.1] with no change in mean single-call accuracy, which is consistent with this second target. On 384 fresh MMLU-Pro inputs it also raises the share of inputs on which the correct answer is sampled, from 84.9% to 89.1% (+4.2+4.2 points [1.8,6.8][1.8, 6.8], Appendix G.4, Table 17).
  3. A sampling change can be scored from a reference sample. In a controlled recoding, the state forecast predicted that dispersing the leading wrong answer would raise accuracy by 1.03 points, and the observed gain was 1.06. For permutation, where forecasts predicted an effect, the sign was right in 29 of 32 states.
  4. Samples can be directed. Calls released by the lock on settled inputs can go to undecided ones. In a replay run after submission, this raises accuracy over a fixed 16-call budget by 0.6 points [0.2, 1.0] on GSM-Symbolic and 1.2 points [0.5, 1.7] on public MATH within the same total budget.

We agree that finding correct answers is central. In a large share of failures the answer was found and then lost, and changing the sampler's response distribution can affect that loss.

Weakness 5: Generality of input permutation

Input permutation gives a large improvement on one synthetic task. However, this improvement is small on new MMLU-Pro inputs. Thus, the results do not show that this method applies generally.

Response: We agree, and the paper makes no claim that permutation is a general method. It reports the transfer directly, including +0.26+0.26 points on the 768-input MMLU-Pro hold-out. In the paper permutation is a controlled perturbation of error competition: it shifts the vote distribution while mean single-call accuracy stays the same.

Proposition 4.2 characterizes the effect of wrong-answer probability transfers under its stated assumptions, and we test whether the state-based calculation predicts intervention effects. A controlled recoding of the wrong answers on MMLU-Pro was predicted to raise accuracy by 1.03 points and raised it by 1.06 [0.46, 1.82]. In a prospective test on 128 MMLU-Pro inputs, forecasts of the permutation effect were frozen before generation. Where an effect was predicted, the sign was right in 29 of 32 states, and the other three states did not move. The same forecasts put the effect within ±0.02\pm0.02 in 224 of the 256 states, where the mean observed effect was 0.000 (Appendix F.5, Table 13). The small average effect on MMLU-Pro is what the state-based account predicts for these inputs. Reference samples of the two response laws, together with the gold label, therefore support offline forecasts of where a sampling change of this kind may help.

Section 4.2 of the revised paper now ends with a paragraph that states this scope.

If any part of the two explanations at the top of this response remains unclear, we would be glad to elaborate.

Reviewer_SPQjOpenReview ↗
Rating
3
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper examines why finding a correct answer among several LLM responses does not necessarily lead to a correct voting result. Given the current vote counts and the remaining budget, it identifies which answers can still win and when the final output can no longer change. It also studies how repeated wrong answers affect voting and derives a relationship between the response distribution and the stopping time. The experiments cover recovery prediction, input permutation, and the computational savings from stopping early.

Critical strengths
  1. The discussion of wrong answers is one of the more interesting parts of the paper. Voting depends on which errors repeat, not just on how often the model is correct. The merging result and the probability transfer analysis make this distinction precise and explain why a single concentration statistic cannot fully describe the outcome.

  2. The empirical reporting is also reasonably balanced. The authors include fresh cohorts where permutation does not show a statistically significant improvement in accuracy and show that stronger selectors reduce the Word16 gain. These results help establish the limits of the explanation rather than leaving the reader with only the largest improvement.

Critical weaknesses
  1. The permutation experiment supports the proposed explanation, but it does not fully isolate it. Similar average single call accuracy can hide changes in correctness on individual inputs, and voting is nonlinear in those probabilities. The controlled merging result fixes the correct responses, whereas input permutation can change the entire response distribution. I would therefore be cautious about attributing the observed gain specifically to changes in wrong answer identities.

  2. The latency results are encouraging, although each input has only one timing in the initial physical study. The intervals capture variation across inputs, but they do not tell us how sensitive the smaller gains are to variation between repeated executions.

Questions for authors
  1. Can the uncertainty in the estimated response distribution be reflected in intervals for the endpoint forecasts? The errors in the extreme forecast ranges make it difficult to judge how much confidence to place in an individual prediction.

  2. How stable are the measured latency savings across repeated executions of the same inputs? A small number of repeated timing runs, especially for the microbatched setting, would help assess whether the smaller improvements persist under backend variability.

  3. The MMLU Pro permutation effect becomes much smaller in the fresh cohorts. Since the cohorts differ in both inputs and implementation, is there a matched comparison that helps explain this difference? Evidence separating these factors would strengthen the case that the observed mechanism transfers across settings.

4 comments

Weakness 1: Isolating the permutation mechanism

The permutation experiment supports the proposed explanation, but it does not fully isolate it ...

Response: We agree. The permutation result is consistent with the error-competition explanation and does not isolate it. The controlled results test specific changes to wrong-answer identities while holding correct responses fixed.

You are right that equal average single-call accuracy can hide changes on individual inputs, and a new accounting on the stored per-input counts shows how much it hides. Of the 21.1-point gain on Word16, 14.1 points [10.1, 18.3] come from a weaker strongest wrong answer and 7.0 points [2.3, 11.8] come from changes in the correct answer's votes on individual inputs, which is the hidden component you describe. On average the correct answer's votes do not move (-0.04 of 16) while the strongest wrong answer loses 1.20 votes, and in 12 of the 74 inputs that permutation corrects the correct answer's votes did not rise. Temperature shows the opposite mix: 7.5 and 9.3 points of its 16.8-point gain, with correct votes up by 0.55.

This accounting is descriptive and does not establish causal mediation. The controlled evidence is in two results. The merging construction fixes the correct responses. The oracle recoding relabels half of the leading wrong answer's responses as the least-voted wrong answer, which was predicted to raise accuracy by 1.03 points and raised it by 1.06 [0.46, 1.82] (Appendix F.5, Table 14). This tests the specified recoding intervention, rather than identifying the mechanism of natural permutation. The prospective permutation forecasts add predictive support: where an effect was predicted, the sign was right in 29 of 32 states (Table 13).

Section 4.2 of the revised paper now states that the Word16 gain is consistent with the error-competition account and does not by itself isolate it, and Appendix J.3 (Table 35) gives the accounting.

Weakness 2 and Question 2: Stability of latency savings across repeated executions

Weakness 2: The latency results are encouraging, although each input has only one timing in the initial physical study. The intervals capture variation across inputs, but they do not tell us how sensitive the smaller gains are to variation between repeated executions.

Question 2: How stable are the measured latency savings across repeated executions of the same inputs ...

Response: The savings persist. We ran the repeated timing study you suggest after submission, with three seeds and two independent executions per seed in the microbatch-four setting. The certificate saves 15.2% [10.6, 19.5] of request time on Qwen3.5-2B and 21.1% [16.5, 25.1] on Qwen3.5-4B. The saving is positive in all six seed-by-execution blocks for each model, with block values of 12.0–19.2% and 19.6–22.1%. The single-timing values in the submission were 14.4% and 19.7%.

Backend variability is small next to these savings. Across 288 repeated same-seed pairs per model the outputs are identical in every pair, and the timing of the two executions differs by a median of 0.9% and 0.5%.

Appendix J.6 (Table 39) of the revised paper reports the pooled savings and all six blocks for each model.

Question 1: Uncertainty intervals for endpoint forecasts

Can the uncertainty in the estimated response distribution be reflected in intervals for the endpoint forecasts ...

Response: Yes. We place a Dirichlet posterior on each problem's response law, compute QrQ_r exactly for each posterior draw, and report the resulting interval. We evaluated this after submission on 255,000 call-8 states from the public GSM8K and MATH samples. The 90% intervals contain the long-sample value of QrQ_r in 90.4% of states when the law comes from 128 reference calls and in 85.1% with 16. The mean interval width falls from 0.10 with 16 calls to 0.01 with 2,000.

The intervals help identify a subset with more reliable predicted directions, while remaining imperfectly calibrated. Take the states where the correct answer has been sampled and is not currently selected, an offline stratum because it uses the gold label. With 16 reference calls the 90% interval excludes one half in 65.7% of these states, and the predicted direction is right in 90.7% of that subset. Without the interval, the direction of the point forecast is right in 80.1% of all such states. Small-sample intervals still under-cover in states whose long-sample value is strictly between 0 and 1 (78% with 16 calls, 86% with 128). The extreme bins you point to remain the weakest part, with 62.5% coverage at 16 calls in the top forecast bin of the sampled-but-unselected states.

Appendix J.2 of the revised paper describes the method and reports coverage and width by number of reference calls (Table 34).

Question 3: Smaller MMLU-Pro effect in the fresh cohorts

The MMLU Pro permutation effect becomes much smaller in the fresh cohorts...

Response: We do not have a fully matched comparison, and the current data cannot separate the input sample from the implementation. We examined one candidate explanation. The first cohort applied a stricter input filter than the fresh cohorts, and stratifying the fresh inputs by that filter shows no detectable difference: +0.85+0.85 [−1.00-1.00, 2.70] for inputs that pass against +1.34+1.34 [−1.34-1.34, 4.01] for inputs that fail, a difference of −0.48-0.48 [−3.75-3.75, 2.74] (Appendix J.3 of the revised paper). The gap between the first cohort and the pooled fresh cohorts is 5.2 points [1.7, 8.9].

We therefore treat the pooled fresh estimate, +1.04+1.04 [−0.52-0.52, 2.60] on 1,152 inputs, as the transfer estimate for MMLU-Pro. The evidence that the mechanism transfers is on MMLU-Pro itself. A controlled recoding of the wrong answers was predicted to raise accuracy by 1.03 points and raised it by 1.06 [0.46, 1.82]. In the prospective test, where forecasts frozen before generation predicted a permutation effect, the sign was right in 29 of 32 states. The same forecasts put the effect within ±0.02\pm0.02 in 224 of the 256 states, where the mean observed effect was 0.000 (Appendix F.5, Table 13). This is consistent with a small average effect in that prospective cohort. These checks support the state-dependent calculation but do not separate the causes of the earlier-to-fresh cohort difference.

Thank you for your responses, which have addressed some of my concerns. I will maintain my score in the acceptance range.

Dear Reviewer SPQj,

Thank you for considering our responses and for your continued positive assessment. We appreciate your careful review and constructive feedback, which helped us improve the paper.

Best,

Authors of Paper #4739

Reviewer_FqZ7OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper analyzes fixed-budget plurality voting over repeated LLM calls through the realized vote state and the remaining budget. It derives a sharp threshold for whether a candidate can still become the endpoint winner, shows that the reachable-winner set only contracts as calls are spent (yielding a contiguous "conversion window" per candidate), and gives exact endpoint probabilities under an iid response law. It also proves that merging wrong-answer identities cannot improve plurality accuracy, which motivates permuting input representations across calls, and derives a gold-free exact locking certificate (a form of deterministic curtailment) whose savings obey an LLN and CLT governed by the modal margin. Empirically, most covered failures lose reachability only after discovery, input permutation improves Word16 plurality accuracy by 21.1 points, and exact locking saves 28–30% of calls at B=16B=16 without changing any output.

Critical strengths
  1. The formulation is precise and the theory is correct. I checked the proofs (reachability threshold, contraction, locking characterization, Propositions 4.1–4.2, Theorem 5.3) and reproduced the numerical examples without finding errors. Abstentions, tie-breaking, unseen candidates and adaptive proposal policies are handled carefully.
  2. The empirical methodology is rigorous. Many studies are pre-specified, use held-out cohorts and multiplicity correction, and null or negative results (e.g., the MMLU-Pro hold-out and the judge study) are reported transparently.
  3. The lock-time law is validated convincingly: on public GSM8K and MATH samples, predicted savings match observed savings within about 0.2 points for budgets up to 1,024.
  4. Distinguishing discovery, recoverability, current selection, endpoint selection and locking provides a useful vocabulary for test-time voting, and the certificate is simple, gold-free and easy to deploy.
Critical weaknesses
  1. Limited incremental technical novelty across a broad set of contributions. The paper combines three related threads (reachability, error competition and locking), and several foundational results are elementary or closely related to classical arguments. The threshold and contraction follow from direct vote counting, the certificate is deterministic curtailment (as acknowledged), and its optimality among universally output-preserving rules follows almost directly from the characterization of reachable winners. Theorem 5.3 rests on standard first-passage arguments, and Proposition 4.1 formalizes the familiar intuition that merging wrong answers hurts plurality voting. Although Proposition 4.2 provides a more specific state-dependent characterization, the overall incremental contribution remains insufficiently clear. The main text is also very dense and number-heavy, which makes the core contribution harder to identify.

  2. The incremental insight beyond the known coverage–selection gap remains unclear. That coverage keeps growing while plurality voting plateaus has been documented before (e.g., Brown et al., 2024; Bay & Yearick, 2026). The finding that most covered failures are recoverable at discovery and lose reachability later provides a finer decomposition, but it remains unclear how much this pattern adds beyond the behavior predicted by each item's iid response law. Plurality accuracy on MATH at (B=1024) essentially equals the estimated fraction of problems whose mode is correct (43.2% vs. 43.0%; 60.4% vs. 60.2%), consistent with the known modal ceiling. The decomposition is precise, but its actionable insight beyond exact locking is unclear; the judge study itself notes that the gold-aware strata supply no routing rule.

  3. The broader practical advantage is setting-dependent. The 21.1-point permutation gain is obtained on Word16, a synthetic sorting task; it shrinks to 5.9 and 2.7 points under a validity filter and Borda fusion, is similar in size to the gain from raising the temperature in the reported comparisons, and is not detected on the fresh MMLU-Pro hold-out (+0.26 [−1.56, 2.08]). Under the stated setting, exact locking can never save more than half of the budget (τB≥B/2\tau_B \ge B/2), and it saves fewer calls than ASC (28.4% vs. 40.8% in the forced-choice replay, where ASC changes 0.30% of outputs; 45.1% vs. 84.5% in the Qwen3-14B thinking-mode replay at (B=32), where neither changes an observed output). ASC and ESC also changed none of the outputs across 432 executions in the fresh online study. Although these finite-sample observations do not provide the certificate's universal output-preservation guarantee, the additional practical value of exactness over low-change statistical stopping remains unclear.

References

[1] Bay, Y. Y. and Yearick, K. A. When more sampling hurts: The modal ceiling and correlation ceiling of test-time scaling. arXiv:2606.28661, 2026.

[2] Brown, B., Juravsky, J., Ehrlich, R., Clark, R., Le, Q. V., Ré, C., and Mirhoseini, A. Large language monkeys: Scaling inference compute with repeated sampling. arXiv:2407.21787, 2024.

Questions for authors
  1. Can the state-based quantities (reachability or the forecasts QrQ_r) yield a gold-free rule for stopping, routing or allocating additional calls that improves on ASC/ESC at matched cost, with any additional response-law estimation counted within the budget? Appendix H.5 already evaluates a gold-free, prefix-estimated stopping rule, but its nominal risks are miscalibrated and it does not dominate ASC/ESC. The separate forecasting studies use additional reference samples (up to 2,000 per problem), so their practical value beyond offline diagnostics would benefit from clarification.
  2. How does the observed failure decomposition (infeasible at discovery / feasible but never selected / selected then lost) compare with the decomposition predicted by each item's iid plug-in law? Agreement would clarify how much of the “decided after discovery” pattern is captured by the multinomial response model, whereas systematic discrepancies, after accounting for response-law estimation error, could indicate departures from the iid assumption.
7 comments

Weakness 1: Incremental technical novelty

Limited incremental technical novelty across a broad set of contributions ...

Response: Thank you for checking the proofs and reproducing the examples. We agree with each attribution: the threshold and the contraction follow from vote counting, the certificate is deterministic curtailment, and Theorem 5.3 uses first-passage arguments. These components provide a common description in terms of the vote state and remaining budget. The proofs are short because the formulation does the work. Once the vote state and the remaining budget are the primitive, each result follows in a few lines. The contribution is what this formulation predicts about LLM voting, and that the predictions hold. Three of them are new to the study of LLM voting.

  1. When a sampled correct answer is lost. The state gives the call at which each loss becomes irreversible under continued fixed-budget voting. Of 553 failures in which the correct answer was sampled, 479 still had a reachable correct answer when it was found and lost it during the remaining calls (Appendix E.1, Table 3). The composition of these failures can be computed in advance from a reference sample of each problem's response law (your Question 2, answered below).
  2. Proposition 4.2 and its test. You single this result out, and we regard it as the conceptual core. Redistributing probability among wrong answers moves accuracy in a direction set by the vote state, so a state-independent concentration statistic cannot determine the direction across all prefixes. The statement is predictive: where forecasts frozen before generation predicted an effect above 0.02 in magnitude, the sign was right in 29 of 32 states, and the other three states did not move (Appendix F.5, Table 13). The full-state forecast also improves squared error over a wrong-identity shuffle that preserves the wrong-answer probability spectrum and collision probability by 0.0030 [0.0004, 0.0068] (Appendix F.5, Table 12).
  3. What exact stopping saves. The certificate's saving tends to m/(1+m)m/(1+m). The paper gives a central limit theorem with variance σ2/(1+m)3\sigma^2/(1+m)^3, coverage of budget-consuming abstentions and unseen answers, and adds an extension to dependent votes since submission. Plug-in finite-budget predictions match observed savings within 0.1 points at budgets from 16 to 1,024 on public GSM8K samples. We are not aware of earlier work on LLM voting that predicts the saving of this rule in advance. Remark 5.2 also settles what statistical stopping rules trade: in the known-universe setting, a prefix-only rule that stops before the certificate gives up universal output preservation.

The general response lists eight such predictions next to their observed values.

We agree that the main text is dense. In the revised paper each contribution in Section 1 leads with the question it answers, and all new analyses are collected in Appendix J so that the main text gains no table.

Weakness 2 and Question 2: Insight beyond the coverage–selection gap and the iid law

Weakness 2: The incremental insight beyond the known coverage–selection gap remains unclear...

Question 2: How does the observed failure decomposition ...

Response: The two decompositions agree closely, and this agreement is the result the framework is built to deliver, indicating that the observed failure pattern is largely captured by the per-item iid response law.

We ran the comparison you describe after submission on the public Llama-3 samples, estimating each problem's law from samples 1–2,000 and comparing with trajectories built from samples 2,001–10,000. The table gives MATH with Llama-3-8B at B=16B=16, and Appendix J.2 (Table 33) of the revised paper gives both models on both tasks.

Share of covered failuresObservedPredicted by the iid law
Infeasible at discovery9.5%9.2%
Feasible, never selected55.4%55.1%
Selected, then lost35.2%35.7%

Across models, tasks and budgets, 1 of 48 share differences has an interval that excludes zero, and predicted per-problem failure rates correlate with observed rates at 0.98–1.00. When the law is estimated from only 16–40 reference calls, none of 172 comparisons rejects after Holm correction. These comparisons detect no departure from the iid model. The "decided after discovery" pattern is therefore predictable. A sample of each problem's response law gives the composition of failures before any vote is run, through the endpoint calculation of Section 2.3.

We also agree that the plateau is the modal ceiling. As you note, Brown et al. (2024) and Bay and Yearick (2026) document that coverage keeps growing while plurality accuracy plateaus. Those results describe the endpoint. The decomposition adds three things to that picture.

  • Timing. Of 553 covered failures in forced-choice MMLU-Pro, 74 are out of reach at discovery, 311 by call 12 and 507 before the final call (Appendix E.1, Table 3). The state gives the call at which each failure becomes irreversible under continued fixed-budget voting.
  • Action. In the 268 call-12 states where the sampled correct answer was out of reach, further votes recovered none and one judge call selected it in 34.2% of states (14.8% for direct solving, Appendix E.5). You are right that these strata use the gold label and supply no routing rule. The gold-free use of the same computation is the lock.
  • Intervention forecasts. Given a reference sample, the same state and law predict the effect of a change to the wrong-answer distribution. In a controlled recoding, dispersing the leading wrong answer was predicted to raise accuracy by 1.03 points and raised it by 1.06 [0.46, 1.82] (Appendix F.5, Table 14).

Weakness 3 and Question 1: Setting-dependent practical advantage and gold-free rules

Weakness 3: The broader practical advantage is setting-dependent...

Question 1: Can the state-based quantities ...

Response: What exactness buys over low-change statistical stopping. Exactness makes the certificate a component that can be placed under any pipeline with nothing to validate, and a low observed change rate does not give that. A measured change rate also depends on arrival order. When concurrent calls are consumed as they complete, short responses arrive first. In thinking-mode runs added after submission (Qwen3-8B, 14B and 32B on AIME and MMLU-Pro, 32 calls per sequence) we read the stored votes in order of response length. Adaptive self-consistency (ASC) at 0.95 then changes 4.84% of outputs on AIME with Qwen3-14B, against 0.42% under random order. Across 24 Holm-corrected tests (two tasks, three models, four settings of ASC and early-stopping self-consistency, ESC), the statistical rules change more outputs under this order in 13 and fewer in none. The certificate's output is unchanged in all 342,720 orders tested (Appendix J.6, Table 38). In the submission's 1,200-input replay ASC and ESC change 1 and 6 outputs (Appendix H.4, Table 27).

The paper does not propose the certificate as a replacement for ASC or ESC. It gives the exact boundary on the axis where they operate. Under the retained-unit-vote information model, the half-budget bound applies to every rule that preserves the full-budget output, and ASC exceeds it by giving up that guarantee (Remark 5.2). The rules also compose. On the same vote sequence and budget, adding the certificate as a second stopping condition to ASC or ESC never introduces an additional disagreement with the full-budget output and never uses an additional call, because a stop at the certificate returns the full-budget answer.

Question 1. At matched cost the answer is parity, and we read parity as the result. After submission we tuned ASC and ESC on a development split to the certificate's number of calls and compared on held-out inputs. Accuracy differs from the certificate's by −0.04-0.04 to +0.15+0.15 points over 21 settings, and no interval excludes zero (Appendix J.6, Table 37). The guarantee therefore costs nothing at that operating point. The extra savings of ASC and ESC come from stopping at prefixes where some continuation would still change the output. For allocating additional calls, state-based priorities beat round-robin allocation in 1 of 36 comparisons, so we make no claim for their superiority (Appendix J.6, Table 37). What the state-based quantities add is of a different kind: the exact boundary with a proof, a prediction of the saving for a given model and task from a reference sample (within 0.1 points at every budget on public GSM8K), and forecasts of where a change to the sampling process may help.

Permutation. We agree that the gain is setting-dependent. In the paper permutation is a controlled perturbation of error competition, and the fresh MMLU-Pro cohorts give its transfer estimate. The small MMLU-Pro effect is also what the state-based forecast predicts. Forecasts fixed before generation put the permutation effect within ±0.02\pm0.02 in 224 of 256 vote states and at both signs in the rest, and the observed effects track the forecast in every bin (Appendix F.5, Table 13). The smaller gain under the validity filter and Borda fusion is consistent with their reducing the error competition available for permutation to change: the filter already removes about 85% of wrong votes on Word16. Temperature reaches a similar size by a different route. In a new accounting on the stored per-input counts, the 21.1-point permutation gain splits into 14.1 points from a weaker strongest wrong answer and 7.0 points from changes in the correct answer's votes, with mean correct votes unchanged (−0.04-0.04 of 16). The 16.8-point temperature gain splits into 7.5 and 9.3 points, with correct votes up by 0.55.

Forecasts and their estimation cost. We now attach posterior intervals to QrQ_r and measure their coverage on 255,000 call-8 states from the public samples. With the law estimated from the 8-call prefix alone, 90% intervals contain the long-sample value in 82.1% of states. Coverage is 85.1% with 16 reference calls and 90.4% with 128. Prefix-only intervals under-cover, so we position the forecasts as an offline tool: they evaluate an intervention on a given model and task from reference samples and gold labels, rather than an online policy whose reference cost is included in the original call budget.

These results are in the revised paper: the arrival-order analysis (Table 38) and the matched-cost comparison and reallocation (Table 37) in Appendix J.6, the accounting of the permutation gain in Appendix J.3 (Table 35), and the forecast intervals in Appendix J.2 (Table 34).

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

The authors propose a solution for test-time scaling that treats the model as a black box and formulates a conservative, safety-preserving theory of stopping. Specifically, they ask the following question: Given a budget B, when can we stop sampling early with mathematical certainty that the plurality winner will not change? They note that discovering a correct answer does not guarantee its final selection. Under a fixed call budget B, a discovered correct answer must still accumulate enough support to defeat rival incorrect answers. Toward this goal, this paper studies this discovery-to-decision gap through a state-based, finite-budget recoverability framework.

Critical strengths
  1. The paper shifts the view of LLM voting from static curve-fitting (e.g., estimating scaling laws or generic pass@k) to a dynamic, sequential-state process. Formulating a sharp recoverability threshold L_y(v) and the contracting reachable-winner set R_r(v) provides a mathematical foundation to analyze what additional inference can realistically achieve at any point in a trajectory.
  2. Input permutation : Shifting these repeated errors to diverse, non-colliding wrong answers via input permutation is a clever idea and a practical contribution.
  3. The gold-free exact locking certificate yields a 28–30% reduction in inference calls (and 41.9% token savings on thinking models). And is more robust compared to the traditional statistical stopping rules.
Critical weaknesses
  1. The asymptotic saving fraction m / (1+m) is very strongly dependent on the modal margin m. A strongly correlated set of responses would limit this fraction to 1/2. How does one get around this problem?
  2. Generalization of their model to long running or open-ended problems often seen in math tasks will not help with amount of saved calls. In such cases, the certificate must defensively require v(w) > r to protect against unseen competitors.
  3. While input permutation shows dramatic, highly significant improvements on structured tasks like Word16 (+21.1 pp) and moderate gains on MMLU-Pro (+6.25 pp), the authors note that on a fresh 768-input MMLU-Pro hold-out, the permutation effect was only +0.26 pp (practically equivalent to Base). This suggests that input permutation is highly task-dependent and may not generalize as well to open-ended natural language reasoning where error distributions are already naturally diverse.
Questions for authors
  1. For open-universe generation tasks, your stopping certificate must require v(w) > r to guard against unseen competitors, which reduces savings. Since open-ended wrong answers are often semantically equivalent but syntactically diverse strings, have you considered combining the locking rule with a fast semantic clustering step?
  2. The asymptotic Lock-time law (Theorem 5.3) is proved under the assumption of iid calls. However, in thinking-mode reasoning models or when using sequential prompt-dependent trajectories, subsequent calls may exhibit strong positive correlation (e.g., local state persistence). How does positive autocorrelation among sequential votes affect the asymptotic convergence rate and the fluctuations of the lock-time τ_B?
  3. Finally, how do you compare your results to those in https://arxiv.org/pdf/2502.01839?
6 comments

Weakness 1: Dependence on the modal margin

The asymptotic saving fraction m/(1+m)m / (1+m) is very strongly dependent on the modal margin mm ...

Response: The dependence on mm is the content of the law, and one half is a limit that applies to every universally output-preserving prefix rule in our fixed-budget setting with retained unit votes, at least two possible answers and unrestricted continuations. Before half of the budget is spent, the remaining calls can still overturn any leader, so no rule that always returns the full-budget answer can stop earlier (Theorem 5.3(iii) and Remark 5.2). Strongly agreeing responses are the favorable case and bring the saving close to that limit: on public GSM8K samples from Llama-3-70B the certificate saves up to 47.1%. When mm is small the vote is contested, the remaining calls can change the output, and continuing to sample is the correct behavior.

There are three practical responses.

  • Accept a small change rate. Adaptive self-consistency (ASC) at threshold 0.95 saves 40.8% against 28.4% for the certificate and changes 0.30% of outputs (Table 30). The price is the guarantee: in the known-universe setting, a prefix-only rule that stops before the certificate returns a different answer on some continuation (Remark 5.2).
  • Raise mm by merging equivalent answers before counting. This is your Question 1, and it adds about 8 points of savings on an open-ended task (see our answer there).
  • Move the calls. Calls released on high-margin inputs can go to contested ones. In a replay run after submission, this raises accuracy over a fixed 16-call budget by 0.6 points [0.2, 1.0] on GSM-Symbolic and 1.2 points [0.5, 1.7] on public MATH within the same total budget.

Weakness 2 and Question 1: Open-ended tasks, unseen competitors, and semantic clustering

Weakness 2: Generalization of their model to long running or open-ended problems often seen in math tasks will not help with amount of saved calls ...

Question 1: For open-universe generation tasks, your stopping certificate must require v(w)>rv(w) > r to guard against unseen competitors ...

Response: Yes, and dynamic clustering adds about 8 points of savings, although it sacrifices exact output preservation. Both analyses below were run after submission.

The guard itself is cheap. For unit votes, the open-universe rule stops at most one call later than the known-universe rule on the same sequence, provided the known universe contains at least two possible answers. On public MATH samples from Llama-3-8B it costs 0.03 points of saving at B=16B=16 and nothing at B=1,024B=1{,}024. The largest cost we measured is 1.9 points at B=16B=16 on GSM8K with Llama-3-70B, and it falls to 0.02 points at B=1,024B=1{,}024. What limits savings on MATH is the small margin between the top two answers (means 0.24 and 0.45 for Llama-3-8B and 70B, with savings of 15.8% and 26.3%). Merging equivalent answers acts on that margin.

Clustering with the lock. We tested this on open-ended answers, in an exploratory replay on stored responses to 600 NQ-Open test questions with supplied passages from Qwen3-8B and Qwen3-32B. The guarantee carries over unchanged whenever each response is mapped to its class by a fixed rule, because the certificate then runs on class counts. A fixed bag-of-tokens canonicalizer changed no class-level output in 36,000 replayed sequences. With an off-the-shelf cross-encoder that groups semantically equivalent answers, savings at B=16B=16 rise from 29.6% to 37.6% on Qwen3-8B and from 27.2% to 35.2% on Qwen3-32B, with no detected change in full-budget accuracy. The price is exactness, since clusters can merge as new answers arrive. In about 7% of sequences the answer string returned at the early stop differs from the full-budget clustered output. In all but at most 0.25% of sequences it still belongs to the final winning cluster, and accuracy is lower by about half a point in one of six settings.

In the revised paper, Appendix J.5 reports the cost of the guard (Table 36) and the clustering replay.

Weakness 3: Task dependence of input permutation

While input permutation shows dramatic...

Response: We agree that the size of the permutation effect is task-dependent, and the fresh cohorts give the estimate to use for MMLU-Pro (+0.26+0.26 on the hold-out you cite, +1.04+1.04 [−0.52-0.52, 2.60] over all 1,152 fresh inputs). The paper's claim concerns the state-dependent effect of error competition, and it is tested on MMLU-Pro itself. At a fixed probability of the correct answer, which wrong answers compete changes accuracy, in a direction that depends on the vote state (Proposition 4.2).

Two tests on MMLU-Pro support this. In a controlled intervention, relabeling half of the leading wrong answer's responses as the least-voted wrong answer was predicted to raise accuracy by 1.03 points and raised it by 1.06 [0.46, 1.82] (Appendix F.5, Table 14). In a prospective test on 128 inputs, with each arm's law estimated from 256 reference calls, we froze the forecast of the permutation effect for every 8- and 12-call prefix before generating the continuations. Where the forecast predicted an effect above 0.02 in magnitude, its sign was right in 29 of 32 states, and the other three states did not move. The same forecasts put the effect within ±0.02\pm0.02 in 224 of the 256 states, where the mean observed effect was 0.000 (Appendix F.5, Table 13). A small average effect on these MMLU-Pro inputs is therefore what the state-based account predicts. Permutation is one inexpensive way to change the response law, including error competition, and forecasts using reference samples of both arms and the gold label indicate where it is expected to help in this offline analysis.

Section 4.2 of the revised paper now ends with a paragraph on the scope of the permutation result, which presents permutation as a controlled perturbation of error competition next to the pooled fresh MMLU-Pro estimate.

Question 2: Lock-time law under positive autocorrelation

The asymptotic Lock-time law (Theorem 5.3) ...

Response: For short-range dependence the limit is unchanged and positive autocorrelation widens the fluctuations. Persistent dependence changes the limit itself. The output guarantee and the bound τB≥B/2\tau_B\geq B/2 are pathwise, so they hold under any dependence. For the law itself we proved the following extension after submission.

  • Stationary ergodic votes with a unique mode. On a finite answer universe, τB/B→1/(1+m)\tau_B/B\to 1/(1+m) almost surely, the same limit as in the iid case.
  • Strong mixing. For stationary votes with summable strong-mixing coefficients, a unique runner-up and positive long-run variance, the central limit theorem holds at the same B\sqrt{B} rate, with the long-run variance σ∞2\sigma_\infty^2 in place of σ2\sigma^2, so the limiting variance is σ∞2/(1+m)3\sigma_\infty^2/(1+m)^3. Positive cumulative autocovariance increases this variance relative to iid sampling.
  • Sticky votes that repeat the previous answer with probability ρ\rho. σ∞2=σ2(1+ρ)/(1−ρ)\sigma_\infty^2=\sigma^2(1+\rho)/(1-\rho). At ρ=0.6\rho=0.6 the variance is four times the iid value.
  • Stronger persistence. A latent state Θ\Theta shared by the whole run, with conditionally iid votes and a unique conditional mode, makes the limit random, 1/(1+M(Θ))1/(1+M(\Theta)). Long-memory dependence can leave the limit of τB/B\tau_B/B unchanged while giving fluctuations of order BHB^H, under a corresponding functional limit theorem for the top-minus-runner-up vote contrast.

A simulation with p=(0.6,0.3,0.1)p=(0.6,0.3,0.1), ρ=0.6\rho=0.6 and B=2,048B=2{,}048 gives τB/B=0.770\tau_B/B=0.770 against the limit 0.769, and Var(τB)/B=1.54\mathrm{Var}(\tau_B)/B=1.54 against the predicted 1.47.

In our data we detect no positive dependence between independent calls and clear dependence between interacting ones. New thinking-mode runs (Qwen3-8B, 14B and 32B on AIME and MMLU-Pro) match the iid prediction of the mean saving within 0.7 points in all 18 settings, and 23 independent-call cohorts show no positive lag-1 dependence. Protocols in which a call sees earlier answers do show positive autocorrelation. In the two with the strongest dependence the certificate locks 5–6% of the budget earlier than the iid prediction, with about twice the variance. In the others the lock time moves by at most 1.5 points.

The extension is Proposition J.1 in Appendix J.4 of the revised paper, with its proof, the simulation and these checks on our data.

Question 3: Comparison with arXiv 2502.01839

Finally, how do you compare your results to those in https://arxiv.org/pdf/2502.01839?

Response: The two papers are complementary. Zhao et al. scale sampling with self-verification as the selector and report continued gains where self-consistency levels off. Our framework identifies a region where voting cannot succeed: the states in which the correct answer has been sampled and can no longer win the vote within the budget. A different selector is the only option there.

Our judge study measures this at small scale. In the 268 call-12 states where the sampled correct answer was out of reach for the vote, continued voting recovered none and one judge call by the same model selected it in 34.2% of states (Appendix E.5). Direct solving by that model reached 14.8%, a difference of 19.4 points [12.4, 26.8]. The same judge discards the correct answer in 29% of the states where the vote is already right, and over all states one judge call and four further votes are level (+0.05+0.05 [−2.35-2.35, 2.50]). Verification therefore helps in a specific region of the state space. Our strata are defined with the gold label, so this is a diagnosis of where verification helps, and a deployable routing rule remains open. We have not replicated their setting at its scale of 200 candidates and 50 verifications per question.

The related work of the revised paper (Appendix A) cites Zhao et al. and states this relation.

Reviewer_PHeQOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how repeated LLM sampling and plurality voting work under a fixed budget, identifying when an answer can still win and calculating its probability of winning. It also examines how incorrect answers affect voting accuracy and introduces an early stopping method that guarantees the final result will not change, along with a statistical analysis of when this happens. Overall, the paper is a good empirical verification of the theory, however the novelty lies more in the empirical verification part than the theory.

Critical strengths
  • The authors provide strong statistical guarantees on the results. There is pre-specification of paired exact tests, Holm and Bonferroni corrections, and candid disclosure of what was post hoc.

-The locking method works even when responses are dependent, some responses are abstentions, proposals are adaptive, or votes have different weights. It was tested on over 253,000 public trajectories, with no changes observed in the final output. I feel this is a strength of the paper.

Critical weaknesses
  • I believe that reachability is a weak measure because an answer can still be mathematically capable of winning even when its actual chances are extremely low. The paper’s finding that most failures remain recoverable is therefore unsurprising, and it does not show whether reachability provides any useful insight beyond the winning probability (Q_r) or a simple vote-deficit measure.

  • The practical value of the method is quite limited: For e.g., “majority lock” saves 22.25% versus 28.35% for the certificate (Table 30), so the certificate adds ~6 points over a rule one line long. Can the authors comment more on the practical value of the method?

  • The paper has some presentation errors: the Fig. 5 axis and caption have typesetting glitches (“m/ˆ(1+ˆm)”), and several figures have unreadably small labels.

Questions for authors

My general thought is that the theoretical novelty is limited -- however I would like the authors to comment more on the practical value of their method. In particular: The users care about accuracy per unit cost, not agreement with an arbitrary B-call plurality, which is often debatable and which the authors show plateaus at the modal ceiling. Table 30 shows this tension. I would like if the authors can comment on this in the rebuttal.

6 comments

Weakness 1: Reachability as a measure

I believe that reachability is a weak measure ...

Response: The three quantities you name are layers of one framework, and the paper's predictor is the strongest of them. Reachability is a feasibility test, while QrQ_r provides the probability prediction. The vote deficit is our threshold L(v)L(v) (Equation 1): an answer is reachable exactly when the votes it still needs are at most the remaining budget. QrQ_r adds a response law to the same deficit (Section 2.3), and Qr>0Q_r > 0 exactly when the answer is reachable.

We ran the comparison you ask for after submission. For predicting whether a candidate answer wins at the final call, QrQ_r under a held-out response law has AUC 0.993 across 11 model and task settings, the raw vote deficit has 0.975 and the reachability indicator has 0.665 (Appendix J.2 of the revised paper). An answer that can still win but is very unlikely to is the case the probability layer handles: QrQ_r gives it a small probability.

Reachability is the layer that needs no estimated law and no independence assumption, and that is what makes it a guarantee. In 7.77 million candidate states the answer was unreachable, and in none of them did it go on to win, as Proposition 2.1 requires. This checks the implementation of the feasibility boundary. By seven eighths of the budget the test rules out 28–74% of the answers observed so far. The stopping certificate is the moment at which one answer remains reachable.

That most failures are recoverable when the correct answer first appears is the starting point of the analysis. The finding is when recoverability ends. In forced-choice MMLU-Pro, 74 of the 553 failures in which the correct answer was sampled are out of reach when it first appears, 311 by call 12 and 507 before the final call (Appendix E.1, Table 3). In 479 of the 553 the correct answer was still reachable when found and was lost during the remaining calls. Once an answer is out of reach, further votes within the budget cannot recover it under retained-vote plurality, although a different selector may. In the 268 call-12 states where the sampled correct answer was out of reach, continued voting recovered none and one judge call selected it in 34.2% of states (Appendix E.5). This is an offline, gold-defined subset rather than a routing rule.

The revised Section 2.3 states this role of reachability.

Weakness 2 and Question: Practical value and accuracy per unit cost

Weakness 2: The practical value of the method ...

Question: My general thought is that the theoretical novelty ...

Response: The practical value is a saving that requires no response-law estimation or stopping-threshold calibration, and the calls it frees can then be spent on accuracy. Accuracy per unit cost is the right criterion, and we answer in those terms.

What the certificate offers. A system that already runs BB-call self-consistency gets the same answer on every input with 28.4% fewer calls in the replay of Table 30. Nothing is tuned, no validation data is needed to calibrate the stopping condition, and no independence assumption is made about the responses, so the saving can be switched on without re-evaluating the system. In accuracy per unit cost this is an improvement with certainty: the accuracy is identical and the cost is lower. BB-call plurality is the reference because it is what such a system has deployed and evaluated.

Majority lock. Majority lock is the same test restricted to the case in which the leader already holds a majority of the budget. It is a sufficient condition, and the certificate is the complete one in the known-universe setting. The certificate is just as short to state: stop when no rival can still overtake the leader in the remaining calls. It never stops later, and its advantage is particularly relevant where no answer holds a majority. In a replay added after submission on public MATH samples from Llama-3-8B, where the most frequent answer has probability at most one half on 72.7% of problems, the certificate saves 13.3% against 7.1% for majority lock at B=16B=16, and 15.8% against 8.2% at B=1,024B=1{,}024 (Appendix J.6, Table 36).

ASC and ESC. The paper does not propose the certificate as a replacement for adaptive self-consistency (ASC) or early-stopping self-consistency (ESC). It gives the exact boundary on the axis where those rules operate: in the known-universe setting, any prefix-only rule that stops before the certificate gives up the guarantee that the output equals the full-budget answer (Remark 5.2). ASC at 0.95 saves 40.8% and changes 0.30% of outputs in Table 30, so it stops earlier than the certificate, illustrating this tradeoff. The rules also compose. On the same vote sequence and budget, adding the certificate as a second stopping condition to ASC or ESC never introduces an additional disagreement with the full-budget output and never uses an additional call. At the certificate's own cost the guarantee is free. With each rule tuned on a development split to the certificate's number of calls, test accuracy differs from the certificate's by −0.04-0.04 to +0.15+0.15 points over 21 settings, and no interval excludes zero (Appendix J.6, Table 37). Thus, this comparison detects no accuracy difference at the evaluated operating points.

Beyond the modal ceiling. Stopping earlier cannot lift accuracy above BB-call plurality, and two parts of the work address accuracy itself. Section 4 studies what moves the ceiling: input permutation raises Word16 accuracy by 21.1 points with no change in mean single-call accuracy. The calls the certificate releases can also go to inputs that are still undecided. In a replay run after submission, this reallocation raises accuracy over a fixed 16-call budget by 0.6 points [0.2, 1.0] on GSM-Symbolic and 1.2 points [0.5, 1.7] on public MATH within the same total budget, with no detectable change on MMLU-Pro and GSM8K (Appendix J.6, Table 37).

A new paragraph in Section 5 of the revised paper summarizes these comparisons.

Weakness 3: Figure typesetting and label size

The paper has some presentation errors: the Fig. 5 axis and caption have typesetting glitches ("m/^(1+^m)"), and several figures have unreadably small labels.

Response: Thank you for flagging these. In the PDF, the caption of Figure 5 reads m^/(1+m^)\hat m/(1+\hat m) and the axis of panel (c) reads 1/(1+m^)1/(1+\hat m), where m^\hat m is the estimated margin. The accent can be displaced when the text is copied out of the PDF, which gives the string quoted above. If a particular figure was hard to read, please point us to it.

AuthorsOpenReview ↗

Follow-up on our response

Dear Reviewer PHeQ,

Thank you again for your thoughtful review. We wanted to follow up on our responses, particularly your question about accuracy per unit cost. Appendix J.6 reports the ASC/ESC comparisons and the experiment reallocating saved calls within the same total budget, and Appendix J.2 addresses the distinction between reachability and endpoint prediction.

We would appreciate knowing whether these clarifications and additional results address your main concerns, or whether a specific point remains unresolved. We would be happy to discuss it further before the discussion closes.

Best,

Authors of Paper #4739

Comments on the paper

6 comments
AuthorsOpenReview ↗

General Response II

Input permutation (Reviewers qEYW, FqZ7, SPQj and znyo). Permutation is in the paper as a controlled perturbation of error competition, and we agree that it is not a general method. Its estimate on the 768-input MMLU-Pro hold-out is +0.26+0.26 points [−1.56,2.08][-1.56, 2.08]. The state-based calculation predicts this small average. On 128 separate MMLU-Pro inputs, forecasts fixed before any validation call put the permutation effect within ±0.02\pm0.02 in 224 of 256 vote states and at both signs in the rest, and the observed effects track the forecast in every bin (the last two prediction rows above, Appendix F.5, Table 13). The same calculation identifies the states predicted to have larger effects. The forecasts use reference samples of both arms and the gold label, so they are an offline tool for assessing where a change to the sampling process may help.

Evidence added since submission. The analyses run after the submission deadline are identified as such in each thread and are collected in Appendix J of the revised paper.

Changes in the revised PDF. Changes are marked in blue. The numbers of existing sections, tables and theorems are unchanged, and all new analyses are collected in the new Appendix J.

  • Section 1: each contribution leads with the question it answers, and the stopping rule is stated to coincide with deterministic curtailment.
  • Sections 2 and 3: the three layers of the state description, with reachability as the guarantee and QrQ_r as the predictor, the failure decomposition under the iid law, and posterior intervals for the forecasts (Appendix J.2).
  • Section 4: the contrast with the ensemble literature, and a new paragraph on the scope of the permutation result (Appendix J.3).
  • Section 5: the rule is named as deterministic curtailment (comparison table in Appendix J.1), the lock-time law is extended to dependent votes (Proposition J.1 in Appendix J.4), and a new paragraph places the certificate next to statistical stopping rules (Appendices J.5 and J.6).
  • Appendix A (related work): Zhao et al. (2025), the ensemble literature, and the relation to curtailment.
  • Appendix J: six subsections with Tables 32 to 39.
AuthorsOpenReview ↗

General Response I

We thank the five reviewers for careful and specific reports. Each reviewer thread below can be read alone. This note states what the paper is, summarizes its predictive checks, addresses the two comparisons that recur in the reviews, and lists the changes in the revised PDF.

What the paper is. The paper asks one question about voting over repeated LLM calls: given the votes so far and the calls that remain, what can further calls still change? It answers at three levels, all using the same vote state.

  • Which answers can still win. This is reachability (Section 2.2). It characterizes the possible winners across all admissible continuations and needs no model of the responses.
  • How likely each answer is to win. This is QrQ_r, the exact endpoint probability under a specified iid response law (Section 2.3).
  • When the output is already decided. This is the locking certificate (Section 5), the moment at which one answer remains reachable.

The stopping certificate and reachability indicator follow from this calculus; input permutation provides a test case for its error-competition analysis. These address stopping, sampling, and prediction through the same state description. The contribution is the calculus connecting them, together with tests of its quantitative predictions.

Its predictions hold. No review reports an error in a proof or in a reported number. Reviewer FqZ7 checked the proofs and reproduced the numerical examples "without finding errors", and Reviewers PHeQ, FqZ7 and znyo note that the studies were specified in advance. The formulation also delivers quantitative predictions about LLM voting from the vote state and a reference sample of the response law. The table below reports these comparisons alongside an implementation audit of reachability.

QuantityPredictedObservedSource
Calls saved by exact stopping on public GSM8K, at every budget from 16 to 1,024from a law of 2,000 held-out sampleswithin 0.1 pointsTable 23
Saving on public MATH at B=1,024B=1{,}024 against its predicted limit, two models15.75%, 26.25%15.8%, 26.3%Table 24
Variance of the lock time on public GSM8K at B=1,024B=1{,}024, two models151, 155150, 130Section 5
Shares of the three failure classes on public MATH at B=16B=169.2%, 55.1%, 35.7%9.5%, 55.4%, 35.2%Table 33
Accuracy gain from dispersing the leading wrong answer on MMLU-Pro+1.03+1.03 points+1.06+1.06 [0.46,1.82][0.46, 1.82]Table 14
Sign of the permutation effect in the 32 vote states with a forecast effectone sign per state29 right, 3 unchangedTable 13
Permutation effect in the other 224 of 256 vote stateswithin ±0.02\pm0.02mean 0.000Table 13
Unreachable answers that go on to winnone0 of 7.77 million statesApp. J.2

Earlier studies of the gap between coverage and accuracy describe the endpoint gap. To our knowledge, earlier uses of this stopping rule in LLM voting report measured savings only. Here, the state-based analysis also describes how the gap evolves along a trajectory and predicts stopping savings from a reference sample of the response law.

The certificate and statistical stopping rules (Reviewers PHeQ, qEYW and FqZ7). The paper does not propose the certificate as a replacement for adaptive self-consistency (ASC) or early-stopping self-consistency (ESC). It gives the exact boundary on the axis where those rules operate. Under retained unit votes, at least two admissible answers and unrestricted continuations, no universal rule that always returns the full-budget answer can save more than half of the calls (Theorem 5.3). In the known-universe setting, every prefix-only rule that stops before the certificate gives up that guarantee (Remark 5.2). ASC and ESC stop earlier than the certificate, at prefixes where some continuation would still change the output. Three facts place the two kinds of rule next to each other.

  • They compose. On the same vote sequence and budget, adding the certificate as a second stopping condition to any statistical rule never introduces an additional disagreement with the full-budget output and never uses an additional call, because a stop at the certificate returns the full-budget answer.
  • At the certificate's cost the guarantee is free. With ASC and ESC tuned on a development split to the certificate's number of calls, test accuracy differs from the certificate's by −0.04-0.04 to +0.15+0.15 points over 21 settings, and no interval excludes zero (Appendix J.6, Table 37).
  • A measured change rate depends on the arrival order. When stored votes are read in order of response length, as happens when concurrent calls are consumed on completion, ASC at 0.95 changes 4.84% of outputs on AIME with Qwen3-14B against 0.42% in random order. The certificate's output is the same in every order (Appendix J.6, Table 38).

Thank you for the follow-up.

In brief, the answer to both parts of your question is yes. Input permutation (Section 4.2) changes what the model generates and uses no labels. For Qwen3.5-4B it raised 16-call raw-plurality accuracy by 21.1 points in the pre-specified Word16 study (Appendix G.1) and by 14.6 points on 384 fresh Word16 inputs (Appendix G.4). The paper uses it as a controlled perturbation of error competition, and its transfer to fresh MMLU-Pro inputs is small, as Section 4.2 reports. The certificate of Section 5 is label-free as well. It decides when generation can stop with the full-budget output unchanged. The procedures that the paper runs at inference time use no labels.

What the paper says about the sampler. The paper develops a finite-budget theory of the vote. Under the stated voting rules, its reachability and stopping guarantees need only the vote state and the remaining budget. Its probability results additionally take the sampler's response distribution as input and characterize how the outcome changes with it. It answers three questions: when a sampled correct answer can still win (Sections 2 and 3), how the outcome changes when the sampler's distribution of wrong answers changes (Section 4), and when the output is already determined (Section 5). On the second, Proposition 4.2 gives the effect of moving probability between wrong answers. With single-call accuracy unchanged, the same move can help in one vote state and hurt in another.

Reachability and the certificate hold for every sequence of calls, including dependent and adaptive ones. The endpoint-probability calculations specify an iid response distribution, and Appendix J.4 extends the lock-time law to stated forms of dependence. A new prompting strategy or a reasoning model can change the response distribution, and a different allocation can change per-question budgets. The guarantees and the probability results apply to each under their assumptions. The experiments include five checkpoints from three model families, public samples from Llama-3-8B and 70B, Qwen3 in thinking mode and permuted inputs.

The effect forecasts and the recoding. You are right that these two studies need labels and run offline, and the paper describes them in these terms: Appendix F.5 calls the forecast study "an offline diagnostic" and notes that the recoding "uses gold". Gold defines the correctness target and identifies the wrong answers to recode. The forecast study tests the state-based prediction of a sampling change, and the recoding tests Proposition 4.2 directly. The underlying endpoint calculation also forecasts each candidate's probability of winning without gold, given the vote state and an estimated response distribution (Appendix J.2).

Reallocation. Appendix J.6 evaluates reallocation of the calls that the certificate releases, which are the calls that can be omitted without changing the fixed-budget output. Allocation across questions is the subject of PETS, which the paper cites in its related work (Appendix A), and the two fit together: the certificate identifies those calls, and an allocator decides where they go.

We share the view that improving what the model generates is an important problem. This paper contributes to it from the side of the vote: it characterizes how the outcome responds to changes in the sampler and gives an exact, label-free stopping rule. We would be glad to clarify anything further.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.