From Discovery to Decision: Finite-Budget Recoverability in LLM Voting
Voting over multiple LLM responses is a standard test-time scaling primitive, but discovering a correct answer does not guarantee it wins the final plurality under a fixed call budget. This paper formalizes the discovery-to-decision gap through the realized vote state and remaining budget, deriving sharp reachability thresholds, exact finite-horizon endpoint probabilities, a gold-free exact locking certificate, and demonstrating that representation diversity can dramatically improve plurality accuracy without changing single-call correctness.
The paper delivers a rigorous finite-horizon theory for LLM self-consistency voting. Its central insight—that a discovered answer must remain reachable given current vote tallies and the remaining budget—is both theoretically sharp and practically actionable. The exact locking certificate and the controlled Word16 study are particular strengths, though empirical generalizability beyond synthetic or forced-choice tasks remains mixed.
The combinatorial reachability threshold $L_y(v)=\max\{0,1-v(y),\max_{a\neq y}(v(a)-v(y)+\delta_{a,y})\}$ and the induced monotonicity properties are elegant and exactly derivable. The exact decision locking rule is a genuinely useful contribution: it is deterministic, requires no gold labels or response-law estimates, and preserves the full-budget output while saving 28-30% of calls in replay. The prospective forecasting experiments provide convincing evidence that the vote state carries substantial predictive signal about the endpoint.
The lock-time law connecting asymptotic savings to the modal margin $m=p_{w^\star}-\max_{a\neq w^\star}p_a$ is a clean theoretical result: $\tau_B/B\to 1/(1+m)$ and no exact prefix-only rule can save more than half the budget.
The dramatic 21.1-point Word16 permutation gain is likely an artifact of an extremely controlled synthetic task where shuffling inputs directly breaks structural error modes; on MMLU-Pro the same intervention yields at most +6.25 points on a filtered set and effectively zero (+0.26) on a larger hold-out. The iid response law assumed for exact endpoint probabilities and the lock-time central limit theorem is a strong idealization that ignores adaptive sampling, correlated errors, and temperature effects. The plug-in forecasts suffer materially from small-sample estimation: 16-call laws miss extreme ranges by up to 11.9 percentage points, and dependence among calls remains unresolved. Finally, exact locking is output-preserving but not truth-preserving—it locks in wrong answers just as readily as correct ones, so its utility depends heavily on the base plurality policy being acceptable.
A more subtle limitation is that the classification of failure modes (infeasible at discovery, feasible but never selected, selected then lost) relies on offline gold labels, which are unavailable at deployment time; the locking certificate itself is gold-free, but the empirical decomposition of the coverage-accuracy gap is retrospective.
The evidence supports the theoretical claims well within the scope of the experiments. The prospective state-conditioned forecasting (AUC 0.825 at call-8) and the large-budget public-data validation of the lock-time law (predictions within 0.1-0.7 points of observed savings) are strong. Comparisons to related work are adequate but not exhaustive: while the paper connects its exact locking to classical deterministic curtailment and possible-winner reasoning, it does not directly benchmark against contemporary statistical stopping rules such as ESC or PETS under a unified output-fidelity metric, instead noting only that stochastic rules trade fidelity for savings. The generator-selector interaction is well-demonstrated but rests heavily on the Word16 synthetic regime.
The paper’s treatment of error competition—proving that merging wrong-answer identities preserves single-call correctness while weakly decreasing plurality accuracy—is precise, and the state-dependent pivotality formula $\frac{d}{d\epsilon}Q_r(v;p+\epsilon(e_b-e_a)) = r\{\Pr(a\text{ pivotal}) - \Pr(b\text{ pivotal})\}$ is a genuinely novel analytical tool.
Reproduction is partially blocked by the absence of explicit code and data release links in the manuscript. Generation settings are documented in Appendix D (BF16 weights, Hugging Face Transformers or vLLM 0.13.0, temperature 0.7), but the exact parsing scripts, random seeds, and model-specific answer-extraction heuristics are embedded in appendices without a public repository pointer. The reliance on specific checkpoints (Qwen3.5-4B, Gemma-4-E2B) and proprietary inference setups means independent reproduction requires substantial reimplementation, though the underlying datasets (MMLU-Pro, GSM-Symbolic) are public. No training is involved, but the exact programmatic Word16 solver and the rationale-processing rules for forced-choice scoring are implementation details that would need to be reverse-engineered.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.