cs.AINov 10, 2026

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

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.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. ARBITER: Reasoning Trajectory Basins and Majority Vote Failures in Test-Time Sampling

    May 25, 2026Meng Cai, Lars Kulik, Farhana ChoudhurySelf-Consistency DecodingTest-Time Scaling

  2. Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback

    Sep 30, 2026Jingkai Huang, Yunfan Zhang, Will Ma +2LLM Inference EfficiencyAdaptive Inference

  3. Uncertainty-Aware Budget Allocation for Adaptive Test-Time Reasoning

    May 26, 2026Manh Nguyen, Sunil Gupta, Hung LeEfficient Language Model ReasoningAdaptive Sampling