CS Paper Radar

BARS: Budget-Aware Sequential Sampling with Refusal for Majority Identification under Unknown Distributions

Shenxi Liu, Yiwei Li, Mingyang Zhao, Yuhang Tian, Kan Li

cs.AI ·submitted 2026-11-10 15:00 UTC · v1

Abstract

Repeated sampling with majority selection is an effective means of enforcing self-consistency in large language models. Recently, a variant has also been introduced that terminates early to save costs when the output distribution is favorable. But it still cannot yield a correct confidence estimate from the answer distribution. For this issue, we formalize this as majority identification under an unknown distribution with a budget and a target error rate, and propose BARS, a sequential rule certifying the top-two gap and returning an early stop, a budgeted majority vote, or a refusal when feasibility cannot be established. A refusal is a statement about the rule and its budget, not a claim that a question is unanswerable, and it tells practitioners when to widen the budget or switch models. A certified mode carries proven bounds on the joint answering error and on refusing an instance the budget could handle, while a practical mode, used in our experiments, replaces them with empirical calibration. On synthetic instances drawn from known distributions over thousands of seeds, the difficulty-driven behavior is recovered and the price of the certified mode is measured.On GSM8K the practical mode draws 22.3\% fewer samples than fixed-8 sampling over the same pool, refused questions included, at the cost of declining 18.8\% of the questions. On MATH, it greatly improves the accuracy of its output answers into 82.5\% at the cost of honestly refusing to answer half of the difficult questions that the model itself is unable to solve.

Comment
23 pages (17 pages without appendix), 7 tables, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

When Self-Consistency Hurts: The Hidden Cost of Majority Voting in Small Language Models

cs.AI ·2026-11-08 ·Wanrong Yang, Lingfang Li, Jun Zhang, Dominik Wojtczak
publishedtheorycode/data similarity 0.63
Abstract · 15 pages, 3 figures, 2 tables. Accepted by the 33rd International Conference on Neural Information Processing (ICONIP 2026)

We study prompted chain-of-thought (CoT) with self-consistency (SC), i.e. sampling N traces and plurality-voting, on small language models, a regime where per-query compute budgets are tight yet SC is commonly applied with a fixed sample budget inherited from large-model practice, regardless of instance difficulty. Across two model families (Qwen-2.5-0.5B, Gemma-3-1B) at FP16 and MLX-Q4 (4-bit quantisation in Apple's MLX framework), on GSM8K and MATH-500, we run 8 per-task and 4 task-pooled experiments at n=200-400 with 1,000x paired-bootstrap confidence intervals (CIs). Our first result is an upper bound: an oracle gate deciding per prompt whether to invoke SC reaches 109-174% of always-SC's accuracy at 23-30% of its compute in all 12/12 cases, so at N=5 always-SC is dominated everywhere on our grid. That margin is exactly the rate at which SC flips correct greedy answers to wrong, here 3-10.5% of prompts, which on Qwen-Q4 x MATH-500 exceeds the wrong-to-right rate and leaves always-SC 3 pt worse than always-greedy. Our second result is a deployable approximation: a gate over greedy-pass signals skips 45-99% of SC calls, with bootstrap CI half-widths under 5 pt, removing 36-79% of always-SC compute. Accuracy retention at those operating points has point estimates of 98.1-98.8%, which we report as point estimates because their CIs are wide (lower bounds 76-86%) over an SC accuracy of only 15-36%. The evidence covers N=5 on two <=1B families and two math benchmarks, which is the scope we claim. Code is available at https://github.com/heywanrong/SiftSC.

0.38

Sample, Mix, or Verify? Allocating Test-Time Compute under Imperfect Verifiers

cs.LG cs.CL ·2026-10-16 ·Srinivasan Iyengar
similarity 0.62
Abstract · 27 pages (18 main + appendix), 14 figures, 11 tables. Code will be released

A common way to make language models and agents more accurate is to spend more compute at inference time: generate many candidate solutions and submit the one a verifier prefers. Success then requires that some candidate is correct and that the verifier picks it. The first grows predictably with the number of samples; the second does not, because real verifiers (unit tests, majority votes, LLM judges, reward models) accept wrong answers, reject right ones, and make correlated mistakes. With a fixed budget, a practitioner must decide how many samples to draw, which models to draw them from, and how much to spend on verification, and today these choices are made by rules of thumb. We introduce SPLIT, which makes them from a small labelled pilot. It rests on an exact formula for the probability of submitting a correct answer under accept/reject and top-score selection that accounts for varying task difficulty, blind spots shared across models, and correlated repeated verifier calls. SPLIT fits the formula by empirical Bayes and uses it to plan budgets on unseen tasks. Across seven benchmarks spanning math, science QA, code and software-engineering agents, 26 models, 175 agent systems and six kinds of real verifiers, all from public releases, SPLIT lands within 0.02-0.8 percentage points of the best allocation in hindsight, while every fixed rule we test loses at least 2.5 points in some setting. Regret depends only on how well SPLIT ranks configurations, and it stays near-optimal under compute, price and latency costs and online. The formula also explains when asking more LLM judges lowers precision. As a forecaster far beyond the pilot, SPLIT beats power-law fitting when the verifier caps success, and we report where it loses.

0.56

Uncertainty-Aware Budget Allocation for Efficient LLM Tree Search

cs.CL cs.AI ·2026-10-16 ·Jianguo Huang, Zhiyi Lyu, Fuxiang Zhang, Yanchen Deng, Deheng Ye +1 more
similarity 0.61
Abstract

Tree search enhances multi-step reasoning in large language models (LLMs), yet prevailing methods expand every step with a fixed budget, irrespective of the marginal utility of expansion. We first show, across existing search algorithms, that continuations sampled from a shared intermediate state are largely duplicates and collapse to a few distinct answers. Critically, we find that the semantic dispersion of sibling actions predicts the redundancy of their downstream continuations, permitting a subtree's budget to be fixed before expansion. An information-theoretic analysis motivates this: treating the per-step budget as the Monte Carlo sample size for estimating a step's residual answer entropy, we derive a sufficient budget that shrinks with sibling dispersion. We accordingly propose $\textbf{Uncertainty-Aware Allocation}$ (UAA), a training-free framework that decouples value from uncertainty: values determine which candidates are promising, while uncertainty, estimated from sibling dispersion at no additional model cost, determines how many merit expansion, via uncertainty-aware pruning and uncertainty-aware budgeting. Across mathematical reasoning, logical reasoning, and planning benchmarks, UAA reduces token usage by up to $90\%$ and latency by up to $9\times$ at comparable accuracy, generalizing across four tree search algorithms and both open- and closed-source LLMs.

0.22

Sequential Anytime Valid Tests for Efficient Inference-Time Alignment

cs.LG ·2026-11-19 ·Vishesh Kumar Singh, Sayak Ray Chowdhury
similarity 0.61
Abstract

Inference-time alignment methods, such as Best-of-N (BoN), improve language model outputs by generating multiple candidates per prompt and selecting among them using a reward model. Much of this cost is wasted: a fixed budget is applied to every prompt, although the computation required by prompts varies widely. Adaptive methods halt once sampled answers appear settled, but their thresholds are tuned heuristics with no statistical control over early-stopping errors. We instead seek an anytime-valid stopping rule that takes an error tolerance $α$ as input and halts only once an answer is certified to hold a majority ($θ_a > 1/2$) under the generator's distribution. We aggregate candidates by final answer with a reward-weighted self-consistency (RWSC) score and treat stopping as a sequential test over the resulting clusters. Applying Wald's sequential probability ratio test to these clusters yields SPRT-RWSC, which performs well empirically, but its guarantee fails because the leading answer shifts during sampling, and the run is continuously monitored. Our main contribution, e-RWSC, replaces Wald's test with a betting supermartingale (an e-process) for every answer the policy produces, bounding the probability of ever certifying a non-dominant answer by $α$, uniformly over time and across all answers. The RWSC scores drive the bets, so they affect only how quickly a dominant answer $a^\star$ is certified, not validity; certification takes $O(\log(1/α)/d_{\mathrm{KL}}(θ_{a^\star}\|1/2))$ samples. Experiments across several language models, datasets, and reward models confirm the predicted $1/d_{\mathrm{KL}}$ scaling of cost and show that accuracy improves over baselines at substantially lower token cost.

0.17

Priced Guidance: Can Language Models Generate Future Research Ideas?

cs.LG ·2026-10-04 ·Kaiyue Wen, Tengyu Ma, Percy Liang
theorycode/datahighly cited similarity 0.61
Abstract · 80 pages, 12 figures. Code available at https://github.com/WhenWen/priced-guidance

We evaluate language models' capability to generate novel research ideas through the lens of compression. We aim to lower-bound the potentially tiny probability that a language model generates the essence of a future research idea without any hints. Rather than estimate this probability through expensive repeated sampling, our Priced Guidance framework measures the compression cost: how many additional bits of information are needed to guide the model to recover the target idea. We prove that if the model can recover the target idea with at most K bits of guidance in expectation, then it can generate the idea without any guidance with probability at least $2^{-K}$. In our framework, the language model, called the generator, can pose a sequence of multiple-choice questions and specify a probability distribution over possible answers. A guide, which is a language model with access to the target idea, selects answers. If a selected answer has prior probability p, the generator pays $-\log_2 p$ bits. The generator aims to produce an idea that matches the essence of the target idea with minimal cumulative cost. This cumulative cost equals, up to an additive constant, the number of bits of information sent by the guide. Using this methodology, we evaluate five generator LLMs (Opus 5, Fable 5.1, GPT-6 Astra, GPT-5.6 Sol, and GLM 5.3) on the core ideas in 87 recent high-quality deep learning papers and we use LLM as judge to determine whether the generated idea matches the target in terms of the central research object and defining mechanism. Fable 5.1 achieves the lowest median compression cost at 69.9 bits, substantially lower than gzip's median of 5,712 bits for losslessly compressing the summary of the target idea. A uniform ensemble of Fable 5.1, Opus 5, and Astra further reduces the median compression cost to 55.8 bits and improves the generation probability lower bound by 18,000 times.

0.70

Adaptive Resource Allocation for Effective and Efficient LLM Social Survey Simulation

cs.CY ·2026-09-28 ·Yuanzi Li, Xueyang Feng, Junhao Wang, Lei Wang, Xu Chen
code/data similarity 0.61
Abstract

Large Language Models (LLMs) enable scalable social survey simulation, yet existing pipelines typically use the same strong general-purpose model and a fixed, often large, respondent history for every respondent-question request. This uniform approach overlooks three factors. First, stronger models may rely on their own knowledge rather than respondent-specific evidence while costing more. Second, additional history can help when evidence is limited, but irrelevant responses may add noise and increase input length. Third, the preferred model and history budget can depend on each other. We propose E2Sim, an adaptive resource allocation framework that jointly selects a model and history budget for each request. Given a respondent persona, ranked response history, and target question, a lightweight policy predicts the accuracy and cost of each configuration and selects the most suitable one. We use respondent-history drop-and-swap augmentation to improve robustness to incomplete or variable histories, and a margin-based curriculum that progresses from easier allocation decisions to harder ones. Experiments on four real-world social survey datasets, multiple model pools, and different history-budget spaces show improvements over the oracle best-fixed configurations, with accuracy gains of up to 6.3 percentage points and cost reductions of up to 55.3 percent. Code is available at https://anonymous.4open.science/r/E2Sim-DE66.

0.60

Efficient Best-of-N policy evaluation for inference-time alignment

cs.LG cs.AIstat.ML ·2026-10-07 ·Jonas Schweisthal, Yuxin Wang, Athiya Deviyani, Stefan Feuerriegel, Dennis Frauen
similarity 0.60
Abstract · Preprint

Best-of-N (BoN) is a common inference-time alignment method that selects the highest-scoring response among N samples from a reference model. Evaluating BoN policies from logged data is challenging under sample-only access because standard off-policy estimators require density ratios that depend on unavailable response likelihoods. In this paper, we propose a sample-only framework for evaluating and selecting BoN policies without access to these likelihoods. We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities that are estimable from samples alone. We then develop a doubly robust estimator of the BoN policy value (BoN-DR) that efficiently reuses a shared auxiliary sample pool across candidate budgets. We establish valid asymptotic inference even under reward estimator misspecification and prove the efficiency of our BoN-DR estimator. Since larger budgets can amplify errors in the score function and lead to reward overoptimization, we derive two selection rules: (i) maximizing the estimated policy value and (ii) maximizing a lower confidence bound on the improvement over the reference policy, which accounts for estimation uncertainty and provides a no-harm guarantee. Across synthetic experiments and GSM8K with multiple reference and reward models, our framework accurately estimates BoN policy values and selects effective sampling budgets.

0.18

One Temperature to Rule Them All?

cs.LG cs.AIcs.CL ·2026-11-09 ·Aviv Orly, Ori Shem-Ur, Yaron Oz
top venuecode/data similarity 0.60
Abstract · Accepted at NeurIPS 2026. 82 pages, 45 figures, 6 tables. Code: https://github.com/avivorly/one-temperature

Inference-time sampling is a central mechanism for improving large language models, with temperature controlling the tradeoff between reliability and diversity. While recent work suggests that varying temperature across samples can improve multi-sample inference, simple fixed-temperature schemes remain the standard in practice. We investigate this discrepancy in the canonical pass@K setting, asking when temperature diversity is useful, and when a single tuned temperature suffices. To this end, we analyze per-question success probabilities across multiple models and datasets, tracking how they vary with sampling temperature. We identify several consistent properties of these profiles, including that harder questions are less likely to share efficient sampling temperatures, although this trend is only logarithmic in hardness. We then derive an efficient method for evaluating the theoretically optimal multi-temperature allocation scheme, and show that although such a scheme improves performance, its gains over single-temperature baselines are typically modest when temperature is tuned as a function of the sampling budget K. We explain this phenomenon through mathematical mechanisms that we call dulling effects, and show how they ensure the robustness of temperature choices across different question distributions. Our results clarify when multi-temperature sampling is useful, and how temperatures should ideally be chosen.

0.41