Repeated sampling with majority voting is an effective way to enforce self‑consistency in large language models. A recent variant can stop early when the output distribution is favorable, yet it still cannot provide a reliable confidence estimate from the answer distribution. To address this, we formalize the problem as majority identification under an unknown distribution with a fixed budget and a target error rate, and introduce BARS – a sequential rule. BARS certifies the gap between the top two candidates and returns one of three outcomes: an early stop, a budgeted majority vote, or a refusal when feasibility cannot be guaranteed. The refusal is a statement about the rule and its budget, not a claim that the question is unanswerable, and it signals practitioners to increase the budget or switch models. The certified mode offers provable bounds on the joint answering error and on the probability of refusing an instance that the budget could have handled; in our experiments the practical mode replaces these bounds with empirical calibration. On synthetic instances drawn from known distributions over thousands of seeds, BARS reproduces difficulty‑driven behavior and we measure the cost of the certified mode. On GSM8K the practical mode draws 22.3% fewer samples than fixed‑8 sampling (including refused questions) while declining 18.8% of the questions. On MATH it raises answer accuracy to 82.5% at the cost of honestly refusing half of the difficult questions that the model itself cannot solve.
Review: BARS balances cost and reliability by leveraging budget‑aware sequential sampling and a principled refusal mechanism, offering a practical safety net especially for challenging tasks.