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 ( r^ ) as the sample size N increases from 20 to 210 , 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 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 κ^(x) and the corresponding adaptive parameter α(x) . By design, BoT minimizes inference regret by shifting α→2 under heavy tails (large κ^ ) to enforce robustness, while allowing α→1 under light tails (small κ^ ) 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 ( r^ ) as the sample size N increases from 20 to 210 , 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 ( r^ ) as the sample size N increases from 20 to 210 , 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 ( r^ ) as the sample size N increases from 20 to 210 , 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 ( r^ ) as the sample size N increases from 20 to 210 , 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 r^ versus the sample size N increases (top row), alongside the trade-off (bottom row) between proxy reward and policy distortion (KL, χ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 r^ versus the sample size N increases (top row), alongside the trade-off (bottom row) between proxy reward and policy distortion (KL, χ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 r^ versus the sample size N increases (top row), alongside the trade-off (bottom row) between proxy reward and policy distortion (KL, χ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 λ ( left two figures ) and tail pivot κ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 κ^(x) across all prompts.
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.
Ved Sriraman, Adam Block
Department of Computer Science, Columbia University · Department of Electrical Engineering, Columbia University
Ensuring the reliability of Large Language Models (LLMs) under distribution drift requires inference-time adaptation. While inference-time alignment methods such as Best-of-N and rejection sampling are widely used, they frame the task as a sampling-intensive, reward-guided search, leading to two key limitations: their performance is bounded by the base model's generation quality, and their reliance on imperfect reward models makes them vulnerable to reward hacking. To address these challenges, we introduce Gradient-Guided Reward Optimization (GGRO), a lightweight inference-time method that performs targeted, minimal intervention during decoding via gradient guidance. Specifically, GGRO monitors token-level entropy to identify high-uncertainty regions indicative of drift or misalignment. Upon detection, it responds by injecting nudging tokens, generated using gradient signals from an off-the-shelf reward model, to steer the generation trajectory rather than merely re-ranking samples. Experiments show that GGRO consistently improves inference-time alignment across safety, helpfulness, and reasoning benchmarks. It also increases coverage of high-quality responses and robustness to reward hacking, with minimal computational overhead. Code is available at https://github.com/lhk2004/GGRO.
Inference-time alignment steers a frozen language model during decoding using auxiliary reward signals, avoiding the cost of repeated weight updates. However, existing inference-time alignment methods typically optimize a single scalar score, so explicit safety constraints must either be ignored or encoded through manually tuned penalties. We propose Lagrangian Reward Augmentation (LARA), a general inference-time alignment framework under safety constraints. Starting from a KL-regularized constrained objective with a reward model and a cost model, LARA dualizes the constraint and reduces the optimization problem to a one-dimensional convex problem over a nonnegative dual variable. Estimated on a small calibration set, this dual variable defines an augmented reward that can be used as a drop-in scoring signal within existing inference-time alignment methods. For sequence-level sampling methods, such as Best-of-N reranking, the calibrated dual variable corresponds to the solution of the expected-cost constrained problem. For token-level reward-guided decoding methods, the same construction yields a principled dual-calibrated heuristic rather than an exact constrained-policy guarantee. We evaluate LARA on both sequence-level and token-level inference-time alignment methods, and find that LARA improves the helpfulness-harmlessness tradeoff, with Best-of-N achieving the best performance among inference-time methods, approaching finetuning-based direct alignment baselines.
Yaswanth Chittepu, Ativ Joshi, Sohini Chintala +1
University of Massachusetts Amherst · Independent Researcher