SANE: Selector-Agnostic Nonparametric Early Stopping for Efficient Repeated Sampling

Repeated sampling improves the accuracy of large language models by generating multiple outputs from the model and selecting one of them as the final answer. Using a fixed sampling budget wastes computation on the easier tasks that require fewer samples. Early-stopping algorithms address this issue by stopping the sampling process once they detect additional samples are unlikely to improve the final answer. Existing algorithms are limited to the single selection mechanism they are designed for, such as self-consistency (SC) or best-of-$N$ (BoN), and some require modeling the underlying distribution of rewards or answers, which may be challenging. We introduce SANE, a practical early-stopping algorithm for repeated sampling that is nonparametric and compatible with any black-box selector that satisfies a union-consistency property: if the selector's choice is the same for two disjoint sets of samples, its choice remains the same over their union. This is satisfied by the commonly used SC, BoN, and weighted BoN algorithms. After sampling $n$ outputs, we lower bound the probability that the selector's choice remains the same with $M$ additional samples. SANE bounds this probability by partitioning the $n+M$ samples into disjoint blocks and estimating the selector's choice for each of them through subsampling. We empirically show that SANE provides a superior cost-accuracy trade-off across a variety of tasks, models, reward models, and selector algorithms and can match the accuracy of fixed-budget sampling with 42%-73% fewer samples.