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

Shenxi Liu, Yiwei Li, Mingyang Zhao, Yuhang Tian, Kan LiarXiv 2026 · arXiv

TL;DR

BARS (Budget-Aware Refusal Sampling) is a new sequential sampling rule that makes Large Language Model (LLM) self-consistency more efficient and reliable. By monitoring the "top-two gap" in answer distributions, it allows systems to stop sampling early on easy questions and—crucially—to refuse to answer when a reliable majority cannot be found within a given compute budget.

What Problem Does This Paper Address?

"Self-consistency"—running an LLM multiple times on the same prompt and taking the majority vote—is a powerful way to boost reasoning accuracy. However, standard implementations use a fixed number of decodes for every question. This is inherently inefficient: easy questions (like "What is 2+2?") waste compute on redundant samples, while hard questions might result in a "majority" that is actually just a random guess among several plausible-looking wrong answers.

Existing adaptive sampling methods often lack formal error guarantees or a way to signal that a question is simply too hard for the current model and budget. The authors of BARS tackle this by framing the problem as majority identification under an unknown distribution. They want to know: How many samples are enough to trust an answer, and when should the system refuse to answer at all?

Methods

The authors model LLM decoding using a bag-of-balls abstraction. Each decode is like drawing a colored ball from a bag where the number of colors and their proportions are unknown.

Figure 1: The bag-of-balls abstraction. (a) Answer distribution obtained by repeatedly decoding the same question at temperature 𝑇; the top-two gap Δ = 𝑝(1) −𝑝(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.

The BARS algorithm operates in three potential stages:

  1. Exploration: The system draws samples and maintains an online estimate of the top-two gap ($\Delta$)—the difference in probability between the most frequent and second-most frequent answers.
  2. Fast Branch: If the system observes a sufficiently long "run" of identical answers (calculated via a Markov dynamic program), it stops early and returns that answer.
  3. Naive Branch & Refusal: If the exploration hits a pre-set cap without a clear winner, the system checks if a reliable majority can be found with the remaining budget. If yes, it finishes the budget and votes; if no, it issues a formal refusal.

BARS offers two modes: a Certified mode that uses rigorous "time-uniform confidence sequences" to provide provable error bounds, and a Practical mode that uses empirical calibration for better performance in real-world deployments.

Datasets

The researchers evaluated BARS using:

  • Synthetic Instances: Controlled distributions used to audit the algorithm's behavior across a mathematical grid of difficulties.
  • GSM8K: A benchmark of grade-school math word problems.
  • MATH: A significantly more challenging dataset of high-school competition-level math problems.
  • Qwen2.5-7B: The underlying LLM used for the real-world benchmark tests.

Key Insights and Ideas

  • Refusal as a Budget Statement: A refusal in BARS isn't a claim that a question is "unanswerable" in an absolute sense. Instead, it's a specific statement: "Given this model and this budget, I cannot guarantee a reliable answer." This allows a system to escalate difficult cases to a human or a larger, more expensive model.
  • The "Certification Tax": One of the paper's most striking findings is the cost of certainty. The Certified mode requires two to three orders of magnitude more samples than the Practical mode to reach a conclusion. Proving a result is statistically sound is much harder than simply being right.
  • Difficulty-Driven Efficiency: BARS naturally allocates more compute where it's needed. On easy synthetic tasks, it can reduce sample counts by over 90% compared to fixed-budget baselines.

Key Results

  • GSM8K Performance: The practical mode of BARS used 22.3% fewer samples than a fixed-8 sampling baseline while achieving higher accuracy on the questions it chose to answer (93.8% vs 88.8%).
  • MATH Performance: On the much harder MATH dataset, BARS improved the accuracy of its output answers to 82.5% (compared to ~74% for the full-budget baseline) by honestly refusing to answer the most difficult 50% of the questions.
  • Reliability: In synthetic tests, BARS concentrated its errors almost exclusively on the most difficult "refusal-range" questions, ensuring that when it did provide an answer, it was highly likely to be correct.

Limitations and Future Work

  • Majority vs. Truth: BARS identifies the model's most probable response. If a model is "confidently wrong" (consistently outputting the same incorrect answer), BARS will identify that wrong answer with high confidence. It cannot detect flaws in the model's underlying knowledge.
  • Semantic Similarity: The current "bag-of-balls" model treats answers as discrete colors. It doesn't yet account for the fact that two different-looking strings might mean the same thing semantically.
  • GPU Scheduling: The authors suggest that future work could use BARS's stopping-time distributions as a signal for more efficient online batching and scheduling on shared GPUs.

Summary updated

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.
BibTeX
@misc{liu2026bars,
  author = {Shenxi Liu and Yiwei Li and Mingyang Zhao and Yuhang Tian and Kan Li},
  title = {{BARS: Budget-Aware Sequential Sampling with Refusal for Majority Identification under Unknown Distributions}},
  year = {2026},
  eprint = {2611.14171},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14171},
}
Figure