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

Hsiang Hsu; Eric Lei; Chun-Fu Chen

cs.AIMar 6, 2026

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

Authors: Hsiang Hsu, Eric Lei, Chun-Fu Chen

Organizations: JPMorganChase Global Technology Applied Research

Abstract

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.

Figures & tables

Figure 1: Conceptual illustration of selection probabilities (colored solid lines) for optimistic, pessimistic, and the proposed BoT strategies. The plots depict how these strategies re-weight candidates under light-tailed ( left ) versus heavy-tailed ( right ) reward distributions (black dashed lines). While optimism consistently concentrates mass on the highest rewards (risking reward hacking) and pessimism remains conservative (risking under-exploration), BoT adaptively shifts its strategy: it mimics optimism in light-tailed regimes to exploit safe gains, but pivots toward robust, conservative selection in heavy-tailed regimes to prevent over-optimization.

Figure 2: Optimistic ( sBoN / BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies on GSM8K, MMLU, and MATH ( rows ) across different reference models and proxy rewards ( columns ). Each curve traces the trajectory of True Reward ( $r^{*}$ ) vs. Proxy Reward ( $\hat{r}$ ) as the sample size $N$ increases from $2^{0}$ to $2^{10}$ , with marker size proportional to $N$ . The smallest marker represents $N=1$ (standard sampling), while the largest represents $N=1024$ . Optimistic strategies typically over-optimize the proxy reward as $N$ grows, leading to reward hacking (where $r^{*}$ degrades despite increasing $\hat{r}$ ). Conversely, ITP tends to saturate early, failing to leverage larger $N$ for further gains. The proposed BoT successfully navigates this trade-off, achieving higher true and proxy rewards without succumbing to reward hacking.

Figure 3: Left: Performance comparison of optimistic ( sBoN / BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies on AlpacaFarm, using Llama-RM as the proxy and Alpaca-RM as the true reward. Right: The prompt-specific Hill estimates $\hat{\kappa}(x)$ and the corresponding adaptive parameter $\alpha(x)$ . By design, BoT minimizes inference regret by shifting $\alpha\to 2$ under heavy tails (large $\hat{\kappa}$ ) to enforce robustness, while allowing $\alpha\to 1$ under light tails (small $\hat{\kappa}$ ) to enable aggressive exploration.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure A.4: Comparison of optimistic ( sBoN / BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies on GSM8K across different reference models and proxy rewards. Each curve traces the trajectory of True Reward ( $r^{*}$ ) vs. Proxy Reward ( $\hat{r}$ ) as the sample size $N$ increases from $2^{0}$ to $2^{10}$ , with marker size proportional to $N$ . The smallest marker represents $N=1$ (standard sampling), while the largest represents $N=1024$ .

Figure A.5: Comparison of optimistic ( sBoN / BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies on MMLU across different reference models and proxy rewards. Each curve traces the trajectory of True Reward ( $r^{*}$ ) vs. Proxy Reward ( $\hat{r}$ ) as the sample size $N$ increases from $2^{0}$ to $2^{10}$ , with marker size proportional to $N$ . The smallest marker represents $N=1$ (standard sampling), while the largest represents $N=1024$ .

Figure A.6: Comparison of optimistic ( sBoN / BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies on MATH across different reference models and proxy rewards. Each curve traces the trajectory of True Reward ( $r^{*}$ ) vs. Proxy Reward ( $\hat{r}$ ) as the sample size $N$ increases from $2^{0}$ to $2^{10}$ , with marker size proportional to $N$ . The smallest marker represents $N=1$ (standard sampling), while the largest represents $N=1024$ .

Figure A.7: Comparison of optimistic ( sBoN / BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies on AlpacaFarm across different reference models and proxy rewards. Each curve traces the trajectory of True Reward ( $r^{*}$ ) vs. Proxy Reward ( $\hat{r}$ ) as the sample size $N$ increases from $2^{0}$ to $2^{10}$ , with marker size proportional to $N$ . The smallest marker represents $N=1$ (standard sampling), while the largest represents $N=1024$ .

Figure A.8: The trajectory of true reward $r^{*}$ and proxy reward $\hat{r}$ versus the sample size $N$ increases (top row), alongside the trade-off (bottom row) between proxy reward and policy distortion (KL, $\chi^{2}$ , and Tsallis divergences) on GSM8K. We compare optimistic ( sBoN , BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies using select configurations from Figure 2 .

Figure A.9: The trajectory of true reward $r^{*}$ and proxy reward $\hat{r}$ versus the sample size $N$ increases (top row), alongside the trade-off (bottom row) between proxy reward and policy distortion (KL, $\chi^{2}$ , and Tsallis divergences) on MMLU. We compare optimistic ( sBoN , BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies using select configurations from Figure 2 .

Figure A.10: The trajectory of true reward $r^{*}$ and proxy reward $\hat{r}$ versus the sample size $N$ increases (top row), alongside the trade-off (bottom row) between proxy reward and policy distortion (KL, $\chi^{2}$ , and Tsallis divergences) on MATH. We compare optimistic ( sBoN , BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies using select configurations from Figure 2 .

Figure A.11: Ablation analysis of steering temperature $\lambda$ ( left two figures ) and tail pivot $\kappa_{0}$ ( right two figures ). We compare optimistic ( sBoN , BoN ), pessimistic ( ITP ), and adaptive ( BoT ) strategies. The black dashed line marks the median of the estimated tail indices $\hat{\kappa}(x)$ across all prompts.

Reward Over-Optimization

See all 14 papers

Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment
Mar 5, 2026Ved Sriraman, Adam BlockBest-of-N Sampling Inference-Time Language Model Alignment
Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University
Gradient-Guided Reward Optimization for Inference-time Alignment
Jun 8, 2026Hankun Lin, Ruqi ZhangReward Hacking LLM Alignment
Department of Computer Science, Purdue University
Safe Inference-Time Alignment via Lagrangian Reward Augmentation
Jul 2, 2026Yaswanth Chittepu, Ativ Joshi, Sohini Chintala +1LLM Alignment LLM Safety Alignment
University of Massachusetts Amherst · Independent Researcher

Mar 5, 2026J/K move · Enter open · S save

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

Ved Sriraman, Adam Block

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

Best-of-N Sampling Inference-Time Language Model Alignment Reward Hacking

Open paper AskPDF arXiv

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.

Abstract

Reward Over-Optimization

Explore similar work

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

Gradient-Guided Reward Optimization for Inference-time Alignment

Safe Inference-Time Alignment via Lagrangian Reward Augmentation