Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers

A simple strategy for improving LLM accuracy, especially in math and reasoning problems, is to sample multiple responses and submit the answer most consistently reached. In this paper we leverage Bayesian prior information to save on sampling costs, stopping once sufficient consistency is reached. Although the exact posterior is computationally intractable, we further introduce an efficient ``$L$-aggregated'' stopping policy that tracks only the $L-1$ most frequent answer counts. Theoretically, we prove that $L=3$ is all you need: this coarse approximation is sufficient to achieve asymptotic optimality, and strictly dominates prior-free baselines, while having a fast posterior computation. Empirically, this identifies the most consistent (i.e., mode) LLM answer and achieves similar answer accuracy using fewer samples.

To improve AI accuracy on complex problems, a common trick is to ask the same question multiple times and take a "majority vote". However, generating many answers is slow and expensive. To save time and compute, we should stop asking as soon as a clear winning answer emerges. Our paper introduces a smart, efficient way to decide exactly when to stop by learning from the AI's past behavior. Because tracking every unique answer is mathematically too heavy, we discovered a powerful shortcut: we only need to track the top two most frequent answers and group everything else together. This simple method drastically reduces computing costs while maintaining high accuracy, making AI faster and cheaper to use.