cs.LGMar 5, 2026

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

Authors: Ved Sriraman, Adam Block

Organizations: Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

More in this topic

Best-of-N Sampling

Best-of-N sampling generates multiple candidate outputs and selects one using reward, confidence, agreement, or task-specific evidence.

See all 32 papers

Explore similar work

CardsList
Mar 6, 2026

Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment

Inference-time alignment effectively steers large language models (LLMs) by generating multiple candidates from a reference model and selecting among them with an imperfect reward model. However, current strategies face a fundamental dilemma: optimistic'' approaches like Best-of-$N$ suffer from reward hacking, while pessimistic'' regularized methods often stifle the exploration needed to discover high-quality responses. In this work, we formalize this trade-off through the lens of regret minimization, demonstrating that the optimal strategy depends critically on the tail behavior of the reward distribution. We show theoretically that light-tailed regimes favor optimism to unearth high-quality outliers, whereas heavy-tailed regimes require pessimism to guard against reward mis-calibration in the extremes. Guided by this insight, we introduce Best-of-Tails (BoT), an adaptive inference-time alignment framework that uses Tsallis divergence as a tunable regularizer to provide a finer granularity of interpolation between these extremes. BoT uses the Hill estimator to characterize reward-tail heaviness on a per-prompt basis and dynamically adjusts its selection rule to balance exploration gains against alignment error. Across math, multiple-choice reasoning, and human-preference evaluations, BoT improves alignment performance across a range of reference and reward model configurations relative to fixed-strategy baselines.

Hsiang Hsu, Eric Lei, Chun-Fu Chen

JPMorganChase Global Technology Applied Research

Reward Over-OptimizationInference-Time Language Model AlignmentBest-of-N Sampling
AskPDF
Oct 7, 2026

Efficient Best-of-N policy evaluation for inference-time alignment

Best-of-N (BoN) is a common inference-time alignment method that selects the highest-scoring response among N samples from a reference model. Evaluating BoN policies from logged data is challenging under sample-only access because standard off-policy estimators require density ratios that depend on unavailable response likelihoods. In this paper, we propose a sample-only framework for evaluating and selecting BoN policies without access to these likelihoods. We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities that are estimable from samples alone. We then develop a doubly robust estimator of the BoN policy value (BoN-DR) that efficiently reuses a shared auxiliary sample pool across candidate budgets. We establish valid asymptotic inference even under reward estimator misspecification and prove the efficiency of our BoN-DR estimator. Since larger budgets can amplify errors in the score function and lead to reward overoptimization, we derive two selection rules: (i) maximizing the estimated policy value and (ii) maximizing a lower confidence bound on the improvement over the reference policy, which accounts for estimation uncertainty and provides a no-harm guarantee. Across synthetic experiments and GSM8K with multiple reference and reward models, our framework accurately estimates BoN policy values and selects effective sampling budgets.

Jonas Schweisthal, Yuxin Wang, Athiya Deviyani +2

LMU Munich & MCML · Carnegie Mellon University · Meta (work in personal capacity)

Best-of-N SamplingOff-Policy EvaluationInference-Time Language Model AlignmentDoubly Robust Estimation
AskPDF
Aug 26, 2026

Privacy Without Regret: Differentially Private Inference-Time Alignment

Best-of-N (BoN) sampling is the simplest and most widely deployed inference-time alignment strategy, but it suffers from two distinct problems: reward hacking, in which the selected response exploits errors in the proxy reward model, and the absence of any privacy protection for the sensitive human preference data used to train that reward model. We show that a single intervention-adding calibrated noise to reward scores before selection-resolves both. Our first result, Private Best-of-N (PrivBoN), establishes that Gumbel noise at an appropriate scale simultaneously provides εε-differential privacy and implements KL-regularized alignment. Whenever the privacy budget exceeds a critical threshold ε∗ε^*, the privacy-mandated noise is the regret-optimal regularization, and privacy imposes zero additional alignment cost-matching the information-theoretic skyline of Huang et al. (2025). Because ε∗ε^* depends on an unknown coverage coefficient, we introduce Private Inference-Time Pessimism (PrivITP), which combines χ2χ^2-regularized rejection sampling with a two-phase Gaussian mechanism. PrivITP achieves ex-post (ε,δ)(ε,δ)-DP with a privacy cost independent of the number of responses nn, cleanly decouples the regularization parameter from the privacy parameter, and attains the skyline up to a noise-inflation term. Experiments across several language models, datasets, and reward models confirm our results: PrivBoN and PrivITP are scaling-monotonic (unlike BoN, which degrades past a critical nn), and PrivITP matches or outperforms PrivBoN at equivalent privacy levels, with the largest gains in the strong-privacy regime.

Ishi Jain, Nandini Bhattad, Sayak Ray Chowdhury

Indian Institute of Technology Kanpur

Inference-Time Language Model AlignmentBest-of-N SamplingPrivacy-Preserving MLDifferential PrivacyReward Hacking
AskPDF