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.
The BARS algorithm operates in three potential stages:
- 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.
- 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.
- 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