Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment

Scaling inference-time computation has become a primary driver of performance gains in modern language models. A common approach is Best-of-N sampling, which generates multiple candidate responses and selects the one with the highest score from a learned reward model. However, because reward models are imperfect proxies for true human intent or task correctness, naively generating more candidates often leads to reward overoptimization or reward hacking. In these cases, the model selects responses that score artificially high under the reward model but perform poorly on the actual task.

The article aims to establish the theoretical performance limits of inference-time alignment with imperfect reward models and introduce an algorithmic method that guarantees consistent performance improvements as computational resources increase.

The authors analyze the problem through a statistical query-complexity framework, evaluating how response quality scales with query count under various coverage conditions. They complement their mathematical proofs with empirical evaluations across standard reasoning benchmarks—including GSM8K, MATH, and MMLU—testing several open-source base language models paired with multiple reward models.

The article presents four primary findings. First, Best-of-N sampling provably degrades once the sample size exceeds a critical threshold because the sample size acts simultaneously as a compute budget and an ineffective regularizer. Second, under realistic coverage conditions, Best-of-N fails to achieve optimal performance, scaling suboptimally at the two-thirds power of the reward model error. Third, the authors introduce a new algorithm, InferenceTimePessimism, which applies a chi-squared regularizer via rejection sampling purely during inference. Fourth, InferenceTimePessimism achieves optimal performance bounds and exhibits scaling-monotonicity, meaning its accuracy does not drop as the candidate pool expands.

These findings demonstrate that increasing compute budget alone does not guarantee better AI outputs and can actively introduce risk into automated systems. Relying solely on Best-of-N sampling creates hidden reliability hazards in production pipelines. By decoupling the computational budget from the statistical regularization parameter, developers can safely increase inference compute without triggering severe reward hacking.

Organizations deploying inference-time alignment should adopt conservative, regularized selection mechanisms such as InferenceTimePessimism rather than unconstrained Best-of-N search. Teams should tune the regularization parameter to the expected reliability of their reward models. Future development should focus on co-designing training-time and inference-time alignment procedures, as well as leveraging the internal representations of base models rather than treating them as black boxes.

The analysis relies on an expected squared-error model for reward estimation, which may be conservative in some operational contexts. Additionally, empirical evaluations focused largely on binary correctness benchmarks where coverage gaps are less pronounced. Nevertheless, the theoretical guarantees and consistent empirical results provide high confidence in the method's effectiveness.