Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment

• URL: http://arxiv.org/abs/2603.05739v1
• Date: Thu, 05 Mar 2026 22:54:19 GMT
• Title: Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment
• Abstract summary: Best-of-N (BoN) sampling is a widely used inference-time alignment method for language models.<n>Recent theoretical work has suggested that it is statistically suboptimal and vulnerable to reward hacking.<n>We show that properly tuned BoN is both computationally and statistically optimal in achieving high win-rate.
• Score: 10.749836992585363
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Best-of-N (BoN) sampling is a widely used inference-time alignment method for language models, whereby N candidate responses are sampled from a reference model and the one with the highest predicted reward according to a learned reward model is selected. Despite its widespread practical use, recent theoretical work has suggested that it is statistically suboptimal and vulnerable to reward hacking, the process by which models exploit weaknesses in the learned reward model to achieve high estimated reward without genuinely improving performance. We revisit this question under assumptions that more closely reflect practice than that of prior work. In particular, in contradistinction to earlier analyses that focused on expected true reward, which may not be meaningful in many practical settings, we investigate how inference-time alignment affects the win-rate, a pairwise comparison-based metric more closely aligned with how reward models are trained and evaluated in practice. We demonstrate that, under minimal conditions on the quality of the reference model and learned reward model, properly tuned BoN is both computationally and statistically optimal in achieving high win-rate, partially explaining its widespread practical success. Because BoN remains susceptible to reward-hacking in this setting, we propose a simple and practical variant that provably eliminates reward-hacking while maintaining optimal statistical performance. Finally, we show that prior approaches are provably suboptimal when considering win-rate, highlighting the importance of choosing appropriate objectives when analyzing inference-time alignment methods.

Related papers

• From Curiosity to Caution: Mitigating Reward Hacking for Best-of-N with Pessimism [30.96634743446629]
  We show that caution is a simple, computationally efficient approach that substantially mitigates reward hacking in BoN sampling.<n>We also provide a theoretical analysis in a simplified linear setting, which shows that caution provably improves over the standard BoN approach.
  arXiv  Detail & Related papers  (2026-04-06T12:58:11Z)
• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference [71.09125259964684]
  Test-time compute (TTC) has become an increasingly prominent paradigm for enhancing large language models (LLMs)<n>We study reward-filtered sequential inference, a simple procedure that selectively incorporates only high-reward generations into the context.<n>On the theoretical side, we show that reward-filtered sequential inference yields strictly stronger guarantees than standard TTC paradigms.
  arXiv  Detail & Related papers  (2025-12-04T08:21:33Z)
• Probing Preference Representations: A Multi-Dimensional Evaluation and Analysis Method for Reward Models [63.00458229517523]
  This work addresses the evaluation challenge of reward models by probing preference representations.<n>We construct a Multi-dimensional Reward Model Benchmark (MRMBench), a collection of six probing tasks for different preference dimensions.<n>We introduce an analysis method, inference-time probing, which identifies the dimensions used during the reward prediction and enhances its interpretability.
  arXiv  Detail & Related papers  (2025-11-16T05:29:29Z)
• Reward-Shifted Speculative Sampling Is An Efficient Test-Time Weak-to-Strong Aligner [24.152878302325508]
  We introduce the reward-shifted speculative sampling (SSS) algorithm, in which the draft model is aligned with human preferences, while the target model remains unchanged.<n>Our algorithm achieves superior gold reward scores at a significantly reduced inference cost in test-time weak-to-strong alignment experiments.
  arXiv  Detail & Related papers  (2025-08-20T20:10:56Z)
• RewardBench 2: Advancing Reward Model Evaluation [71.65938693914153]
  Reward models are used throughout the post-training of language models to capture nuanced signals from preference data.<n>The community has begun establishing best practices for evaluating reward models.<n>This paper introduces RewardBench 2, a new multi-skill reward modeling benchmark.
  arXiv  Detail & Related papers  (2025-06-02T17:54:04Z)
• Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment [54.787826863212146]
  Inference-time computation offers a powerful axis for scaling the performance of language models.<n>We analyze the performance of inference-time alignment algorithms in terms of (i) response quality, and (ii) compute.<n>We introduce $textttInferenceTimePessimism$, a new algorithm which mitigates reward hacking through deliberate use of inference-time compute.
  arXiv  Detail & Related papers  (2025-03-27T18:00:08Z)
• What Makes a Reward Model a Good Teacher? An Optimization Perspective [82.73297593767181]
  We prove that regardless of how accurate a reward model is, if it induces low reward variance, then the RLHF objective suffers from a flat landscape.<n>We additionally show that a reward model that works well for one language model can induce low reward variance, and thus a flat objective landscape, for another.
  arXiv  Detail & Related papers  (2025-03-19T17:54:41Z)
• Evaluating Robustness of Reward Models for Mathematical Reasoning [14.97819343313859]
  We introduce a new design for reliable evaluation of reward models, and to validate this, we construct RewardMATH. We demonstrate that the scores on RewardMATH strongly correlate with the results of optimized policy and effectively estimate reward overoptimization.
  arXiv  Detail & Related papers  (2024-10-02T16:39:58Z)
• Towards Understanding the Influence of Reward Margin on Preference Model Performance [8.891183078634786]
  This study introduces a novel method to estimate the preference differences without the need for detailed, exhaustive labels from human annotators. Our experimental results provide empirical evidence that incorporating margin values into the training process significantly improves the effectiveness of reward models.
  arXiv  Detail & Related papers  (2024-04-07T12:10:04Z)
• Confidence-aware Reward Optimization for Fine-tuning Text-to-Image Models [85.96013373385057]
  Fine-tuning text-to-image models with reward functions trained on human feedback data has proven effective for aligning model behavior with human intent. However, excessive optimization with such reward models, which serve as mere proxy objectives, can compromise the performance of fine-tuned models. We propose TextNorm, a method that enhances alignment based on a measure of reward model confidence estimated across a set of semantically contrastive text prompts.
  arXiv  Detail & Related papers  (2024-04-02T11:40:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.