BARS: Budget-Aware Sequential Sampling with Refusal for Majority Identification under Unknown Distributions
Authors: Shenxi Liu, Yiwei Li, Mingyang Zhao, Yuhang Tian, Kan Li
Organizations: Beijing Institute of Technology, Beijing, 100081, China · Department of Computing, The Hong Kong Polytechnic University, 999077, Hong Kong
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.
Figures & tables
Figure 1: The bag-of-balls abstraction. (a) Answer distribution obtained by repeatedly decoding the same question at temperature T ; the top-two gap Δ=p(1)−p(2) measures the separation between the two most probable answers. (b) Each decode is viewed as drawing a ball, with replacement, from a bag whose size and composition are unknown; the color of the ball is the parsed answer.
Family
Answer space
Outputs
Hard budget
Guarantee, and on what
Self-consistency and its adaptive variants [ 32 , 21 , 1 , 25 , 5 ]
discrete
answer
no (stop rule free to grow)
empirical savings; heuristic margin criteria
Conformal abstention [ 35 , 33 , 20 ]
fixed batch
answer, abstain
not applicable
distribution-free risk and abstention bounds for a one-shot decision
Agreement-based selective prediction [ 19 ]
fixed features
answer, abstain
not applicable
certified selective risk in a version space
Certified self-consistency [ 7 ]
discrete
answer, continue
no
concentration bound uniform over sample size
Best-arm identification [ 18 , 10 ]
discrete arms
arm
fixed-confidence or fixed-budget
sample complexity; no refusal
BARS (this paper)
unknown discrete
early stop, answer, refuse
yes ( E∗ )
joint answering-error and mis-refusal bounds (certified mode), plus a two-point lower bound
Table 1: Nearest families along five dimensions. “Hard budget” means that the total number of samples is bounded by a constant fixed before the run; “refusal bounded” means that the probability of refusing an instance the budget could have handled carries a stated bound.
Symbol
Meaning
Notes
p,p(1)>p(2)≥⋯
true distribution (desc.)
p(1) is the majority
K
number of colors (unknown)
estimated online by K^t
Kˉ
known upper bound on K
required by the certified mode only (Assumption 1 )
Δ=p(1)−p(2)
top-two gap, the difficulty of the instance
larger is easier
σ2
per-sample variance of the gap
p(1)(1−p(1))+p(2)(1−p(2))+2p(1)p(2)
E∗
sampling budget
at most this many samples
Table 2: Notation. p denotes the true distribution, with probabilities arranged in descending order; ⋅^ denotes the online estimate of the corresponding quantity, and ⋅ˉ a known bound used by the certified mode.
Figure 2: Results across the Δ sweep under the practical mode, with the competing rules on the same instances. Left: conditional error rate, that is the error over the instances each rule answers (the BAI rules and Fixed- N answer every instance, so their conditional and total error coincide). Right: expected sample count. Every curve is averaged over 2000 seeds per cell; the fixed-budget baseline draws exactly 200 samples on every instance.
Figure 3: Branch composition and refusal quality as functions of Δ . Left: the refusal region marks the instances for which the criterion cannot establish feasibility within the budget; the transition to the fast branch is consistent with the (Δ−Δhigh)−2 certification cost of Section 3.4 . Right: refusal correctness against the oracle feasibility criterion of Section 5.1 , that is the fraction of infeasible instances that are refused and of feasible ones that are not.
Figure 4: Decision map of the practical mode on the (Δ,E∗) plane, 400 seeds per cell. Left: answer rate. Right: conditional error on the answered instances (a dash marks a cell in which the rule answered nothing). The dashed contour in both panels is the oracle feasibility boundary of Section 5.1 : cells above and to the right of it are instances a budget-feasible answer exists for.
Figure 5: Parameter-tuning heatmaps for the practical width mode, three panels per row (conditional error, answer rate, expected sample count). Top: an easier instance with Δ=0.4 . Bottom: a harder instance with Δ=0.05 . Axes are the width multiplier z and the trigger threshold Δhigh ; 600 seeds per cell. Cells in which fewer than five instances were answered are drawn but their conditional error is not interpretable.
z
Δhigh
easy ( Δ=0.4 )
hard ( Δ=0.05 )
Cond. err.
Answer
Mean n
Cond. err.
Answer
Mean n
1.5
0.05
0.0052
0.970
30.8
0.2930
0.427
101.8
1.5
0.1
0.0017
0.987
31.6
0.2976
0.342
110.8
1.5
0.15
0.0017
0.977
35.9
0.3025
0.198
126.6
1.5
0.2
0.0017
0.967
40.9
0.3061
0.163
130.5
1.5
0.3
0.0000
0.815
64.8
0.2157
0.085
139.0
Table 3: Parameter-tuning grid for the practical width, 600 seeds per cell. “easy” is Δ=0.4 and “hard” is Δ=0.05 ; the conditional error in cells with few answered instances is not interpretable and is reported only for completeness.
Figure 6: Budget sufficiency in the certified mode. Left: at a given budget the answer rate increases with Δ ; no incorrect answer was observed in these runs, so no conditional-error panel is drawn. Right: the theoretical certification time Tcert , computed from wt≤Δ−Δhigh under the two conventions of Lemma 1 .
Δ
square-root term
two-term (Lemma 1 )
ratio
0.2
2.05×104
2.18×104
1.06
0.3
4.27×103
4.81×103
1.13
0.4
1.60×103
1.96×103
1.22
0.6
3.82×102
5.68×102
1.49
0.8
9.20×101
1.99×102
2.16
Table 4: Certification time Tcert under the square-root convention used by the implementation and the figures, and under the two-term convention of Lemma 1 , with δ=0.05 , Δhigh=0.1 , Kˉ=10 and σ2=1−Δ2 . All values are closed-form and follow from Section 3.4 ; no experiment is involved, so there is no sampling uncertainty to report.
Config
Δ
Answer
Refusal
Mean samples
Mean trigger
Cond. err.
Deg. trig.
C1
0.05
0.000
1.000
250.0
250.0
0.0000
0
C1
0.1
0.000
1.000
250.0
250.0
0.0000
0
C1
0.2
0.013
0.987
253.5
247.4
0.0000
2
C1
0.4
0.743
0.257
784.5
156.6
0.0000
7
C1
0.8
1.000
0.000
838.1
18.9
0.0000
45
C2
0.05
0.000
1.000
250.0
250.0
0.0000
0
Table 5: The four configurations defined in this subsection, on a shared Δ grid with 300 seeds per cell, E∗=1000 , Tcap=250 , min_t=8 , p∗=0.05 , δ=0.05 , Δhigh=0.1 and K=10 ; the four share one seed batch. C1: certified width, pessimistic chooser, square-root-only convention. C2: certified width, pessimistic chooser, two-term width (the configuration the theorems cover). C3: certified width, optimistic chooser, two-term width. C4: practical width ( z=2 ), optimistic chooser. “Deg. trig.” counts the seeds whose trigger fired on a batch with zero plug-in variance.
Figure 7: Trajectory-majority benefit in synthetic fast-branch experiments without a language model. Left: the exact gain W−V against the remaining budget N for Δ=0.1,0.2,0.4 and run lengths w=10 (solid) and w=8 (dashed); markers are Monte Carlo estimates over 40,000 seeds. Right: conditional error rates of the run-color and trajectory-majority rules, given that a run completes ( Δ=0.2 , w=10 ); lines are exact chain values and markers are Monte Carlo estimates.
Figure 8: Real-LLM results on GSM8K and MATH in the practical mode, with a pre-generated pool of E∗=16 decodes per question and 80 questions per dataset. (a) GSM8K and (b) MATH: accuracy on the answered questions against the mean number of samples, one marker per rule, with the fixed- N majority joined by a dashed line as a reference and the rule under test drawn as a filled square.
Rule
GSM8K
MATH
ans. (%)
acc. (%)
n
ans. (%)
acc. (%)
n
Fixed-1
100.0
81.2
1.00
100.0
48.8
1.00
Fixed-2
100.0
81.2
2.00
100.0
48.8
2.00
Fixed-4
100.0
86.2
4.00
100.0
62.5
4.00
Fixed-8
100.0
88.8
8.00
100.0
70.0
8.00
Fixed-16
100.0
88.8
16.00
100.0
73.8
16.00
Table 6: Real-LLM results, Qwen2.5-7B , 80 questions per dataset, pre-generated pool E∗=16 , all rules on the same pool. “ans.” is the answer rate, “acc.” the accuracy on the answered questions, and n the mean sample count over all questions of the dataset, refused questions included. Accuracy intervals are Wilson 95% intervals and are reported in the text.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Δ
Rule
Answer
Cond. err.
Total err.
Mean n
Miss (feas.)
OK (infeas.)
0.02
BARS (practical)
0.134
0.3806
0.9170
134.0
0.0000
0.8660
0.02
Fixed-N
1.000
0.3345
0.3345
200.0
—
—
0.02
SR
1.000
0.4445
0.4445
200.0
—
—
0.02
SH
1.000
0.4160
0.4160
150.0
—
—
0.02
LUCB
1.000
0.3760
0.3760
200.0
—
—
0.02
lil’UCB
1.000
0.3850
0.3850
200.0
—
—
Appendix
Table 7: Behavior across the difficulty sweep, 2000 seeds per cell, all rules on the same instances. “Answer” is the answer rate, “cond. err.” the error on answered instances (for the rules with no refusal output this equals the total error), “miss (feas.)” the rate at which a feasible instance is refused, and “OK (infeas.)” the rate at which an infeasible instance is correctly refused; the last two are defined only for BARS.
When language models use test-time sampling, they generate multiple reasoning trajectories and select an answer by majority vote. We show that these trajectories are not independent: for a given question, they concentrate into a small number of clusters, or reasoning basins, each defined by a normalized final answer and the solutions that reach it. A majority vote therefore selects the most stable basin rather than the most accurate one, which creates wrong-majority failures where the correct answer is present but outvoted. We introduce ARBITER, a model-agnostic approach that models interactions between basins using only the base model's own sampled outputs, hidden states, and derived evidence. Most direct correction strategies fail; ARBITER instead uses conservative additive evidence on top of consensus. In its simplest parameter-free form, ARBITER-Δ adds same-model evidence to the majority prior, while ARBITER-Enc augments this with bounded residual signals from hidden states over complete solutions. On GSM8K with Qwen3-4B, consensus over K=24 samples achieves around the mid-94% range, while a same-pool top-2 oracle reaches around the mid-96% range. ARBITER recovers a subset of these cases using zero external information. Across three model families and three math benchmarks, it yields consistent gains with no net-negative cases; for example, on Llama-3.1-8B MMLU-HS-Math, it improves accuracy from the mid-78% range to the mid-82% range, recovering about 22% of the available oracle headroom, indicating that this headroom can be partially recovered from the sample pool itself.
Meng Cai, Lars Kulik, Farhana Choudhury
School of Computing and Information Systems University of Melbourne
Self-consistency samples many reasoning trajectories and aggregates their final answers, treating the LLM as a black box that returns one answer per trajectory. Yet the final answer of each trajectory is sampled from a softmax vector that is available from the model's log-probabilities. We refer to this as the grey-box setting in which each trajectory reveals this answer distribution rather than a single draw from it. We formulate efficient inference in this setting as sequential mode identification with distribution-valued observations: sample trajectories one at a time and stop as soon as the LLM's modal answer is identified at a prescribed confidence level. We characterize the asymptotic stopping rate of mode identification with distribution-valued observations exactly and show that it is never worse than the black-box rate. We then propose the ASC-D algorithm, a betting stopping rule that attains this asymptotic stopping rate. On MMLU-Redux, ASC-D uses 46.4--95.6% fewer trajectories than answer-only adaptive self-consistency baselines and achieves the highest fixed-budget correct-certification rate across three open-source models.
Jingkai Huang, Yunfan Zhang, Will Ma +2
Stern School of Business New York University · School of Management Zhejiang University
Sampling multiple responses improves language model reasoning, but uniform compute allocation is inefficient because easy questions are over-sampled while hard questions remain under-explored. We propose Uncertainty-Aware Budget Allocation (UAB), a concave integer optimization framework that reallocates a fixed sampling budget using uncertainty estimated from the initial samples themselves. In Phase-1, every question receives a small fixed number of generations. Their answer disagreement, measured by vote entropy, provides a difficulty signal while these generations contribute to the final vote. In Phase-2, the remaining budget is allocated by a marginal-greedy algorithm that optimally solves a concave coverage-maximization surrogate, concentrating samples on questions whose initial answers disagree. Across five open-weight models (1.5B--27B parameters) and five reasoning benchmarks of varying difficulty, UAB improves average accuracy by +2.3% over uniform allocation, and achieves gains of up to +5.5% on individual benchmarks, with the largest gains in low-resource settings. Moreover, UAB meets the target budget exactly and requires no auxiliary model or additional LLM calls. Code is publicly available at https://github.com/manhitv/UAB.
Manh Nguyen, Sunil Gupta, Hung Le
Applied Artificial Intelligence Initiative Deakin University, Australia