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

arXiv: https://arxiv.org/abs/2503.21878 · HTML: https://mlsanity.com/paper/2503.21878/

## Key facts

- Cited by 97 papers in the map (data through 14 Oct 2026).
- Placed in LLM preference optimization methods, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 64 of its 102 references that are in the map.
- First posted on arXiv 27 Mar 2025.

## Placed in

- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

## Builds on (most cited first, 30 of 64)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone](https://mlsanity.com/paper/2404.14219/) (2024)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment](https://mlsanity.com/paper/2304.06767/) (2023)
- [Interpretable Preferences via Multi-Objective Reward Modeling and Mixture-of-Experts](https://mlsanity.com/paper/2406.12845/) (2024)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Statistical Rejection Sampling Improves Preference Optimization](https://mlsanity.com/paper/2309.06657/) (2023)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Meta-Rewarding Language Models: Self-Improving Alignment with LLM-as-a-Meta-Judge](https://mlsanity.com/paper/2407.19594/) (2024)
- [Helping or Herding? Reward Model Ensembles Mitigate but do not Eliminate Reward Hacking](https://mlsanity.com/paper/2312.09244/) (2023)
- [Regularizing Hidden States Enables Learning Generalizable Reward Model for LLMs](https://mlsanity.com/paper/2406.10216/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Theoretical guarantees on the best-of-n alignment policy](https://mlsanity.com/paper/2401.01879/) (2024)
- [BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling](https://mlsanity.com/paper/2406.00832/) (2024)
- [Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer](https://mlsanity.com/paper/2405.16436/) (2024)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [ARC Prize 2024: Technical Report](https://mlsanity.com/paper/2412.04604/) (2024)
- [ARGS: Alignment as Reward-Guided Search](https://mlsanity.com/paper/2402.01694/) (2024)

## Built on by (most cited first, 30 of 97)

- [Chasing the Tail: Effective Rubric-based Reward Modeling for Large Language Model Post-Training](https://mlsanity.com/paper/2509.21500/) (2025)
- [Inference-Time Reward Hacking in Large Language Models](https://mlsanity.com/paper/2506.19248/) (2025)
- [Energy-Based Transformers are Scalable Learners and Thinkers](https://mlsanity.com/paper/2507.02092/) (2025)
- [Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening](https://mlsanity.com/paper/2601.21590/) (2026)
- [RewardAnything: Generalizable Principle-Following Reward Models](https://mlsanity.com/paper/2506.03637/) (2025)
- [Incentivizing Agentic Reasoning in LLM Judges via Tool-Integrated Reinforcement Learning](https://mlsanity.com/paper/2510.23038/) (2025)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [ROC-n-reroll: How verifier imperfection affects test-time scaling](https://mlsanity.com/paper/2507.12399/) (2025)
- [Guided Speculative Inference for Efficient Test-Time Alignment of LLMs](https://mlsanity.com/paper/2506.04118/) (2025)
- [PiCSAR: Probabilistic Confidence Selection And Ranking for Reasoning Chains](https://mlsanity.com/paper/2508.21787/) (2025)
- [Token Hidden Reward: Steering Exploration-Exploitation in Group Relative Deep Reinforcement Learning](https://mlsanity.com/paper/2510.03669/) (2025)
- [AdaBoN: Adaptive Best-of-N Alignment](https://mlsanity.com/paper/2505.12050/) (2025)
- [Revisiting Test-Time Scaling: A Survey and a Diversity-Aware Method for Efficient Reasoning](https://mlsanity.com/paper/2506.04611/) (2025)
- [When Life Gives You Samples: The Benefits of Scaling up Inference Compute for Multilingual LLMs](https://mlsanity.com/paper/2506.20544/) (2025)
- [Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling](https://mlsanity.com/paper/2510.03199/) (2025)
- [Enhancing Large Language Model Reasoning with Reward Models: An Analytical Survey](https://mlsanity.com/paper/2510.01925/) (2025)
- [Learning to Answer from Correct Demonstrations](https://mlsanity.com/paper/2510.15464/) (2025)
- [Likelihood-Based Reward Designs for General LLM Reasoning](https://mlsanity.com/paper/2602.03979/) (2026)
- [Building Coding Agents via Entropy-Enhanced Multi-Turn Preference Optimization](https://mlsanity.com/paper/2509.12434/) (2025)
- [Making, not Taking, the Best of N](https://mlsanity.com/paper/2510.00931/) (2025)
- [On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference](https://mlsanity.com/paper/2512.04558/) (2025)
- [Learning a Pessimistic Reward Model in RLHF](https://mlsanity.com/paper/2505.20556/) (2025)
- [Information-Theoretic Reward Modeling for Stable RLHF: Detecting and Mitigating Reward Hacking](https://mlsanity.com/paper/2510.13694/) (2025)
- [In Good GRACEs: Principled Teacher Selection for Knowledge Distillation](https://mlsanity.com/paper/2511.02833/) (2025)
- [Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo](https://mlsanity.com/paper/2604.16453/) (2026)
- [Understanding Reasoning from Pretraining to Post-Training](https://mlsanity.com/paper/2607.16097/) (2026)
- [A*-Decoding: Token-Efficient Inference Scaling](https://mlsanity.com/paper/2505.13672/) (2025)
- [Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality](https://mlsanity.com/paper/2510.18982/) (2025)
- [Demystifying LLM-as-a-Judge: Analytically Tractable Model for Inference-Time Scaling](https://mlsanity.com/paper/2512.19905/) (2025)
- [Jailbreak Scaling Laws for Large Language Models: Polynomial-Exponential Crossover](https://mlsanity.com/paper/2603.11331/) (2026)

## Abstract (arXiv)

Inference-time computation offers a powerful axis for scaling the performance of language models. However, naively increasing computation in techniques like Best-of-N sampling can lead to performance degradation due to reward hacking. Toward a theoretical understanding of how to best leverage additional computation, we focus on inference-time alignment, which we formalize as the problem of improving the quality of responses drawn from a pre-trained policy, given a prompt of interest and access to an imperfect reward model. We analyze the performance of inference-time alignment algorithms in terms of (i) response quality, and (ii) compute, and provide new results that highlight the importance of the pre-trained policy's coverage over high-quality responses for performance and compute scaling: 1. We show that Best-of-N alignment with an ideal choice for N can achieve optimal performance under stringent notions of coverage, but provably suffers from reward hacking when N is large, and fails to achieve tight guarantees under more realistic coverage conditions. 2. We introduce textttInferenceTimePessimism, a new algorithm which mitigates reward hacking through deliberate use of inference-time compute, implementing the principle of pessimism in the face of uncertainty via rejection sampling; we prove that its performance is optimal and does not degrade with N, meaning it is scaling-monotonic. We complement our theoretical results with an experimental evaluation that demonstrate the benefits of textttInferenceTimePessimism across a variety of tasks and models.