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.