# Theoretical guarantees on the best-of-n alignment policy

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

## Key facts

- Cited by 124 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 3 Jan 2024.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 19 of 19)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [FUDGE: Controlled Text Generation With Future Discriminators](https://mlsanity.com/paper/2104.05218/) (2021)
- [Reward Model Ensembles Help Mitigate Overoptimization](https://mlsanity.com/paper/2310.02743/) (2023)
- [Helping or Herding? Reward Model Ensembles Mitigate but do not Eliminate Reward Hacking](https://mlsanity.com/paper/2312.09244/) (2023)
- [RL with KL penalties is better viewed as Bayesian inference](https://mlsanity.com/paper/2205.11275/) (2022)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [Training Language Models with Language Feedback at Scale](https://mlsanity.com/paper/2303.16755/) (2023)
- [Calibrating Sequence likelihood Improves Conditional Language Generation](https://mlsanity.com/paper/2210.00045/) (2022)
- [On Reinforcement Learning and Distribution Matching for Fine-Tuning Language Models with no Catastrophic Forgetting](https://mlsanity.com/paper/2206.00761/) (2022)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Compositional preference models for aligning LMs](https://mlsanity.com/paper/2310.13011/) (2023)

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

- [RLHF Workflow: From Reward Modeling to Online RLHF](https://mlsanity.com/paper/2405.07863/) (2024)
- [The Unreasonable Effectiveness of Entropy Minimization in LLM Reasoning](https://mlsanity.com/paper/2505.15134/) (2025)
- [WARM: On the Benefits of Weight Averaged Reward Models](https://mlsanity.com/paper/2401.12187/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decoding](https://mlsanity.com/paper/2408.08252/) (2024)
- [BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling](https://mlsanity.com/paper/2406.00832/) (2024)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Test-time Alignment of Diffusion Models without Reward Over-optimization](https://mlsanity.com/paper/2501.05803/) (2025)
- [Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Models](https://mlsanity.com/paper/2412.15287/) (2024)
- [BOND: Aligning LLMs with Best-of-N Distillation](https://mlsanity.com/paper/2407.14622/) (2024)
- [Learning How Hard to Think: Input-Adaptive Allocation of LM Computation](https://mlsanity.com/paper/2410.04707/) (2024)
- [Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding](https://mlsanity.com/paper/2503.01422/) (2025)
- [TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling](https://mlsanity.com/paper/2410.16033/) (2024)
- [Does Thinking More always Help? Mirage of Test-Time Scaling in Reasoning Models](https://mlsanity.com/paper/2506.04210/) (2025)
- [Online Iterative Reinforcement Learning from Human Feedback with General Preference Model](https://mlsanity.com/paper/2402.07314/) (2024)
- [Variational Best-of-N Alignment](https://mlsanity.com/paper/2407.06057/) (2024)
- [Asymptotics of Language Model Alignment](https://mlsanity.com/paper/2404.01730/) (2024)
- [Evaluation of Best-of-N Sampling Strategies for Language Model Alignment](https://mlsanity.com/paper/2502.12668/) (2025)
- [Dynamic Search for Inference-Time Alignment in Diffusion Models](https://mlsanity.com/paper/2503.02039/) (2025)
- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [Bayesian Reward Models for LLM Alignment](https://mlsanity.com/paper/2402.13210/) (2024)
- [InfAlign: Inference-aware language model alignment](https://mlsanity.com/paper/2412.19792/) (2024)
- [Theoretical Physics Benchmark (TPBench) -- a Dataset and Study of AI Reasoning Capabilities in Theoretical Physics](https://mlsanity.com/paper/2502.15815/) (2025)
- [Inference-Time Reward Hacking in Large Language Models](https://mlsanity.com/paper/2506.19248/) (2025)
- [Weak-to-Strong Search: Align Large Language Models via Searching over Small Language Models](https://mlsanity.com/paper/2405.19262/) (2024)
- [Steering Masked Discrete Diffusion Models via Discrete Denoising Posterior Prediction](https://mlsanity.com/paper/2410.08134/) (2024)
- [Soft Best-of-n Sampling for Model Alignment](https://mlsanity.com/paper/2505.03156/) (2025)
- [Reuse Your Rewards: Reward Model Transfer for Zero-Shot Cross-Lingual Alignment](https://mlsanity.com/paper/2404.12318/) (2024)
- [Regularized Best-of-N Sampling with Minimum Bayes Risk Objective for Language Model Alignment](https://mlsanity.com/paper/2404.01054/) (2024)

## Abstract (arXiv)

A simple and effective method for the inference-time alignment and scaling test-time compute of generative models is best-of-n sampling, where n samples are drawn from a reference policy, ranked based on a reward function, and the highest ranking one is selected. A commonly used analytical expression in the literature claims that the KL divergence between the best-of-n policy and the reference policy is equal to log (n) - (n-1)/n. We disprove the validity of this claim, and show that it is an upper bound on the actual KL divergence. We also explore the tightness of this upper bound in different regimes, and propose a new estimator for the KL divergence and empirically show that it provides a tight approximation. We also show that the win rate of the best-of-n policy against the reference policy is upper bounded by n/(n+1) and derive bounds on the tightness of this characterization. We conclude with analyzing the tradeoffs between win rate and KL divergence of the best-of-n alignment policy, which demonstrate that very good tradeoffs are achievable with n < 1000.