mlsanityData to 7 Oct 2026

Theoretical guarantees on the best-of-n alignment policy

arXiv 2401.01879 ↗First posted 3 Jan 2024cs.LG cs.CL cs.ITcited by 116

On the map: LLM reasoning → Test-time compute and efficient thinking

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.

Key facts. Cited by 116 papers in the map (data through 7 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.

Builds on

19 of 38 references.

References · 19

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  3. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  4. 2017Deep reinforcement learning from human preferencescited by 3,846
  5. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,634
  6. 2020Learning to summarize from human feedbackcited by 2,562
  7. 2021WebGPT: Browser-assisted question-answering with human feedbackcited by 1,722
  8. 2022Scaling Laws for Reward Model Overoptimizationcited by 1,056
  9. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 906
  10. 2021FUDGE: Controlled Text Generation With Future Discriminatorscited by 374
  11. 2023Reward Model Ensembles Help Mitigate Overoptimizationcited by 225
  12. 2023Helping or Herding? Reward Model Ensembles Mitigate but do not Eliminate Reward Hackingcited by 195
7 more
  1. 2023Controlled Decoding from Language Modelscited by 133
  2. 2022RL with KL penalties is better viewed as Bayesian inferencecited by 130
  3. 2023Training Language Models with Language Feedback at Scalecited by 125
  4. 2022Calibrating Sequence likelihood Improves Conditional Language Generationcited by 121
  5. 2022On Reinforcement Learning and Distribution Matching for Fine-Tuning Language Models with no Catastrophic Forgettingcited by 80
  6. 2021On Tilted Losses in Machine Learning: Theory and Applicationscited by 42
  7. 2023Compositional preference models for aligning LMscited by 25

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 28; 2025: 51; 2026: 37.

116 papers.

Sort:

By area:

  1. 2024RLHF Workflow: From Reward Modeling to Online RLHFcited by 265
  2. 2025The Unreasonable Effectiveness of Entropy Minimization in LLM Reasoningcited by 160
  3. 2024WARM: On the Benefits of Weight Averaged Reward Modelscited by 145
  4. 2024From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Modelscited by 136
  5. 2024Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decodingcited by 127
  6. 2024BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Samplingcited by 120
  7. 2024Fast Best-of-N Decoding via Speculative Rejectioncited by 112
  8. 2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignmentcited by 91
  9. 2025Test-time Alignment of Diffusion Models without Reward Over-optimizationcited by 89
  10. 2024Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Modelscited by 86
  11. 2024BOND: Aligning LLMs with Best-of-N Distillationcited by 73
  12. 2024Learning How Hard to Think: Input-Adaptive Allocation of LM Computationcited by 67
38 more
  1. 2025Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decodingcited by 62
  2. 2024TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Samplingcited by 61
  3. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  4. 2025Does Thinking More always Help? Mirage of Test-Time Scaling in Reasoning Modelscited by 52
  5. 2024Variational Best-of-N Alignmentcited by 49
  6. 2024Asymptotics of Language Model Alignmentcited by 46
  7. 2025Evaluation of Best-of-N Sampling Strategies for Language Model Alignmentcited by 38
  8. 2025Dynamic Search for Inference-Time Alignment in Diffusion Modelscited by 36
  9. 2025Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Modelscited by 36
  10. 2024Bayesian Reward Models for LLM Alignmentcited by 35
  11. 2024InfAlign: Inference-aware language model alignmentcited by 34
  12. 2025Theoretical Physics Benchmark (TPBench) -- a Dataset and Study of AI Reasoning Capabilities in Theoretical Physicscited by 33
  13. 2024Weak-to-Strong Search: Align Large Language Models via Searching over Small Language Modelscited by 32
  14. 2025Inference-Time Reward Hacking in Large Language Modelscited by 32
  15. 2024Steering Masked Discrete Diffusion Models via Discrete Denoising Posterior Predictioncited by 28
  16. 2025Soft Best-of-n Sampling for Model Alignmentcited by 28
  17. 2024Reuse Your Rewards: Reward Model Transfer for Zero-Shot Cross-Lingual Alignmentcited by 26
  18. 2024Regularized Best-of-N Sampling with Minimum Bayes Risk Objective for Language Model Alignmentcited by 24
  19. 2025Training-Free Guidance Beyond Differentiability: Scalable Path Steering with Tree Search in Diffusion and Flow Modelscited by 23
  20. 2024Information Theoretic Guarantees For Policy Alignment In Large Language Modelscited by 22
  21. 2025Sample, Don't Search: Rethinking Test-Time Alignment for Language Modelscited by 21
  22. 2026How RLHF Amplifies Sycophancycited by 20
  23. 2024Inference-Time Language Model Alignment via Integrated Value Guidancecited by 19
  24. 2024DMoERM: Recipes of Mixture-of-Experts for Effective Reward Modelingcited by 15
  25. 2025Psi-Sampler: Initial Particle Sampling for SMC-Based Inference-Time Reward Alignment in Score Modelscited by 15
  26. 2025CoDe: Blockwise Control for Denoising Diffusion Modelscited by 14
  27. 2025T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Modelscited by 13
  28. 2025Certified Self-Consistency: Statistical Guarantees and Test-Time Training for Reliable Reasoning in LLMscited by 12
  29. 2025KL-Regularized RLHF with Multiple Reference Models: Exact Solutions and Sample Complexitycited by 11
  30. 2025ROC-n-reroll: How verifier imperfection affects test-time scalingcited by 11
  31. 2024Faster WIND: Accelerating Iterative Best-of-N Distillation for LLM Alignmentcited by 9
  32. 2025Truthful or Fabricated? Using Causal Attribution to Mitigate Reward Hacking in Explanationscited by 9
  33. 2025Guided Speculative Inference for Efficient Test-Time Alignment of LLMscited by 9
  34. 2025Stackelberg Learning from Human Feedback: Preference Optimization as a Sequential Gamecited by 9
  35. 2024A Survey on Responsible Generative AI: What to Generate and What Notcited by 8
  36. 2025Robust Multi-Objective Controlled Decoding of Large Language Modelscited by 8
  37. 2025AdaBoN: Adaptive Best-of-N Alignmentcited by 8
  38. 2025Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scalingcited by 8

50 most cited of 116 All 116 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis
  2. 2026Efficient Best-of-N policy evaluation for inference-time alignment
  3. 2026Revisiting the (Sub)Optimality of Best-of-N for Inference-Time Alignment
  4. 2025The Best of N Worlds: Aligning Reinforcement Learning with Best-of-N Sampling via max@k Optimisation
  5. 2026Best-of-Better-N: Generating Pre-Aligned Responses with In-Context Learning
  6. 2026Predicting Inference-Time Scaling Gains from Labeled Validation-Set Output Statistics
  7. 2026Asymptotic Universal Alignment: A New Alignment Framework via Test-Time Scaling
  8. 2026Why Self-Rewarding Works: Theoretical Guarantees for Iterative Alignment of Language Models