CS Paper Radar

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

Shaoang Li, Jian Li

cs.AI ·submitted 2026-10-01 03:57 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Which Answers Agree? Evaluating Self-Consistency from Incomplete Logs

cs.LG ·2026-10-19 ·Zhengtao Gui, Zexi Chen, Weining Shen
similarity 0.65
Abstract · 20 pages, 2 figures, including appendices

Self-consistency answers a question by generating multiple responses and selecting the most frequent answer. Its evaluation requires both correctness labels and information about which responses agree; correctness labels alone generally determine neither voting accuracy nor the benefit of additional votes. For tasks in which all correct responses map to the same normalized answer, we derive sharp accuracy bounds using classical stochastic majorization, refined by abstention counts and answer-category limits. We also derive sharp bounds on accuracy changes across voting budgets that share a response pool. When answer-category counts are available, we introduce Plurality-U, a count-based dynamic program that exactly averages voting accuracy over all fixed-size subsets, eliminating finite-pool Monte Carlo error. On 1,403,520 stored outputs from recent reasoning models in Scorio Lite and Scorio Trace, recording abstention counts and answer options cuts the width of SuperGPQA accuracy intervals by more than half. For moving from 9 to 17 votes, our bounds reduce interval width by a median of 77.7% on SuperGPQA and 72.3% on 14 GPQA and Adaptive-Consistency pools, compared with a baseline that combines separate accuracy bounds. Exact computation has lower paired median runtime than 2,000-subset Monte Carlo in 14 of 15 tested pool-budget settings. These results clarify what incomplete logs can establish and provide an exact evaluation procedure when answer counts are retained.

0.39

Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling

cs.LG cs.CLstat.ML ·2026-11-16 ·Xiaoyu Li, Jiangxuan Long
top venue similarity 0.61
Abstract · Accepted at NeurIPS 2026. Xiaoyu Li and Jiangxuan Long contributed equally. 31 pages, 7 figures, 15 tables

Test-time scaling systems often choose how much to sample, which prompt to use, and which verifier or aggregation rule to trust after repeatedly inspecting a calibration set. Standard validation error bars are not valid after this adaptive selection. We model a test-time scaling recipe as a randomized predictor with a random cost and prove a time-uniform PAC-Bayes certificate that holds simultaneously over all calibration times, all posterior mixtures over recipes, and all data-dependent stopping rules. Thus the same event covers the recipe search that precedes deployment, not merely the fixed recipe finally reported. For a finite grid of budgets and verifiers, the penalty is the familiar $\log M/n$, which in the worst case no certificate valid after selection can avoid, while non-uniform priors and localized posterior mixtures can give sharper certificates for structured searches. We specialize the result to self-consistency and show a complementary margin law: plurality voting improves exponentially in the sample budget only on examples where the correct answer is the generator's unique mode; otherwise more compute can provably amplify errors. The same margin analysis yields an oracle water-filling law for compute allocation. A synthetic audit quantifies the optimism caused by adaptive budget selection, and a 192-example GSM8K audit using gpt-4.1-mini generations illustrates risk-cost reporting for a real inference pipeline. At scale, with two models on GSM8K and MATH-500, selected-best error bars fall below the out-of-split GSM8K risk in up to 22.5% of random splits at a nominal 5% while the certificate never does, and on the full GSM8K test split it tightens to 0.109 (held-out risk 0.039). The results give a lightweight, distribution-free way to report risk and compute claims for adaptive inference systems.

0.52

Selection, Recombination, or a Fresh Solve? A Candidate-Free Control for Single-Pass Test-Time Aggregation

cs.LG cs.AIcs.CL ·2026-08-18 ·Guiv Farmanfarmaian
benchmark similarity 0.61
Abstract · Accepted at the COLM 2026 Workshop on Efficient Reasoning. 24 pages

An aggregation pass gives a language model two things: candidate solutions and another chance to answer. We ask whether the candidates improve that attempt, and whether aggregation improves on selecting an existing answer. Our candidate-free control asks the same model to solve the problem again from the problem alone, using the same decoding settings and maximum output-token allowance. On AIME-2025 and HMMT-2025, Qwen3-4B-Instruct-2507 reaches 15.5% accuracy when all four candidates are wrong, compared with 27.7% for a fresh solve. When at least two candidates are correct, the ordering reverses: 88.7% for aggregation versus 59.7% for a fresh solve. With exactly one correct candidate, the benefit remains unresolved under the specified test. Yet plurality voting reaches 96.0% in the multiple-correct regime without another model generation; its accuracy difference from aggregation is inconclusive (raw $p = 0.180$). The all-wrong accuracy loss and multiple-correct gain survive a statistical correction for adding the second benchmark, developed after data collection, and persist when fresh responses are scored by their final answers. These findings concern one 4B model, two mathematics benchmarks, and a single aggregation pass over candidates truncated at their first answer. All-wrong recovery can arise from solving the problem afresh. The fresh-solve control tests whether candidates improve accuracy. Comparing with selection asks whether the additional generation improves on an existing answer.

0.26

Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

cs.AI cs.IT ·2026-09-24 ·Yezhou Cheng, Runjia Du, Zeming Liu, Qibai Chen, Hang Lyu +3 more
benchmarkhot direction similarity 0.61
Abstract

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of $M$ tasks with $L$ binary paths per task under the hard budget $(M+t)K$, where each path costs at most $K$ responses or episodes. For fixed $L \ge 3$ and $0 < α\le 1/12$, the optimal expected width on the worst pure cohort is $Θ_{α,L}([M(t+1)]^{-1/2})$ when every task is observed and $Θ_{α,L}([M(t+\sqrt{M})]^{-1/2})$ when omission is allowed. The lower bounds cover adaptive hard-budget policies, and fixed random-subset designs attain both rates through disagreement certificates. A joint mean/disagreement interval turns the task-covering law into practical finite-budget inference. In an equal-budget LiveCodeBench replay with 16 models, 880 tasks, and five outputs per task, the task-covering design reduces median point-estimation MSE by 87.0\% relative to pooled uniform sampling, while the Joint certificate produces narrower confidence intervals in 15/16 panels and reduces median interval width by 30.6\%. Finite-regime analyses identify task coverage as the effective choice at the evaluated scale and characterize how cohort size and within-task agreement determine the useful operating region. Together, the sharp laws and fixed-budget evidence make replication and task coverage explicit design variables for information-efficient repeated evaluation.

0.58

Same Winners, Different Success Rates: Evaluating How LLM Agents Recover from Failures

cs.AI cs.LGcs.MA ·2026-09-28 ·Dong Xu, Zhangfan Yang, Jiantao Wu, Shipeng Zhang, Zexuan Zhu +3 more
similarity 0.61
Abstract · 44 pages, 2 figures

Evaluating how LLM agents recover from mid-task failures is central to deploying reliable agentic systems. Existing checkpoint-based benchmarks measure recovery by comparing which action is selected as best across independent runs, a quantity known as set agreement. However, set agreement is a purely ordinal measure that records which action wins without reflecting the absolute level of performance. When all actions fail, they tie at zero reward, and independent runs produce the same tied set with high probability, creating an illusion of stability that masks near-zero recovery success. We formalize this limitation through a set-path symmetry result, proving that for equal-cost Bernoulli actions the success probabilities (0.9, 0.8) and (0.2, 0.1) yield identical best-action-set distributions at every sample size. No procedure based solely on which action wins can distinguish these two regimes. We further prove that certifying exact population ties is impossible in finite time, and that the assignment of outcomes to checkpoints carries information beyond marginal outcome distributions. The pooled success probability is the missing scalar that resolves the ordinal ambiguity. Experiments on 864 frozen RecoveryBench episodes and two planning cohorts totaling 3,456 responses confirm the theoretical predictions. Agreement and held-out quality can move in opposite directions, and permuting checkpoint-to-action bindings changes 8 to 13 percent of cell-level conclusions. Based on these findings, we propose reporting four diagnostic quantities (agreement, all-zero fraction, held-out success, and pooled success) that expose this failure mode with no additional data collection.

0.25

ReSolve: Reusing Candidate Reasoning through Selective Generative Moderation

cs.AI ·2026-10-01 ·Bangji Yang, Jiajun Fan, Hongbo Ma, Xi Zhu, Weizhi Zhang +4 more
similarity 0.60
Abstract · Corrected a typo in an author's name. No changes to the paper content

Sampling multiple solutions spends computation on intermediate deductions and unfinished arguments as well as final answers. We introduce ReSolve, a training-free inference procedure that reuses this candidate reasoning through selective generative moderation. An answer-distribution controller invokes a model to examine existing derivations when candidates disagree or lack a parseable answer, then incorporates the generated solution into a bounded loop. Under Hybrid scoring on 130 competition-mathematics problems evaluated with two independently sampled candidate pools, ReSolve obtains 100 and 99 correct answers, compared with 91 and 92 for voting over the same four candidates, with no correct-to-incorrect changes relative to that vote in either pool. Eight-sample self-consistency obtains 94 and 96 correct answers while consuming substantially more tokens; ReSolve uses 46.3% and 47.2% fewer tokens in the two evaluations. A controlled ablation removes visible derivations while retaining answer keys, vote counts, and the per-state output-cap rule, reducing accuracy from 100 to 93 correct despite increasing computation. Selective and always-on Uniform moderation both solve 97 problems, while selectivity reduces moderation tokens by approximately 54% and total pipeline tokens by 6.2%. These results support candidate reasoning as reusable inference computation. They do not establish an accuracy advantage over additional sampling or a distinct benefit from specialized route instructions.

0.20

Value-Conditioned Proposal Acquisition for Test-Time Reasoning

cs.AI ·2026-11-02 ·Zeyan Li, Jianfeng Xu
similarity 0.60
Abstract

Sampling and selection spend test-time compute inside a candidate pool, but they cannot recover a correct answer that never enters it. We introduce ValueFormation, a test-time policy that decides after each primary-model draw whether to stop, continue sampling, or acquire one proposal from a heterogeneous reasoning specialist. The three actions are compared on one cost-regularized value scale learned from vote-state features; the calibration is frozen across tasks and primary models, and acquired proposals are accepted only through a frozen posterior comparison. On held-out MATH-500, one Llama-fitted calibration improves over the strongest of eight identically evaluated baselines by more than fifteen points for each of three 8B primaries and transfers unchanged to Qwen3-14B. Removing acquisition lowers Llama MATH accuracy by 20.43 points, while same-trace and same-access replays attribute the gain to state-conditioned acquisition rather than specialist access alone. Where primary coverage is high, as on GSM8K, acquisition is rare and gains mainly come from cheaper allocation; on MBPP, a fixed code route attains the top accuracy at the lowest interaction cost. Varying the token price monotonically reduces calls without retraining.

0.15

When Can LLM Reasoning Reliably Reuse Intermediate Results?

cs.AI ·2026-10-20 ·Deyuan Liu, Zecheng Wang, Xuanyi Liu, Jungang Li, Yihao Hu +3 more
code/data similarity 0.59
Abstract

Sampling complete solutions gives large language models more chances to solve a problem, but each attempt starts again. For tasks with several subproblems, all required answers must be correct in the same attempt. Retaining intermediate results can avoid repeating correct work, but errors in those results may affect later attempts. We study when this reuse is reliable and how much computation it requires. For local retries that stop when no candidate passes within the retry budget, we give conditions for correct completion and bound the average number of attempts. We also show how checking cost and the chance of passing a check affect total computation. Experiments across eight reasoning models examine composite mathematics and arithmetic. Across four DeepSeek models, average success on the second subproblem is 36.2 percent without first-subproblem context, 57.2 percent with its answer, and 58.3 percent with its reasoning and answer. These scores measure second-subproblem coverage and include continuations made when selection fails. Arithmetic experiments show that similar first-attempt accuracies can lead to very different coverage after repeated attempts. Code is available at https://github.com/SempraETY/Intermediate-State-Reuse.

0.47