# Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis

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

## Key facts

- Cited by 17 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.
- First posted on arXiv 8 Jul 2025.

## Placed in

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

## Built on by (most cited first, 17 of 17)

- [Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling](https://mlsanity.com/paper/2510.03199/) (2025)
- [Why Pass@k Optimization Can Degrade Pass@1: Prompt Interference in LLM Post-training](https://mlsanity.com/paper/2602.21189/) (2026)
- [ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference](https://mlsanity.com/paper/2602.23681/) (2026)
- [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)
- [Reinforcement Learning from Human Feedback: A Statistical Perspective](https://mlsanity.com/paper/2604.02507/) (2026)
- [Best-of-Tails: Bridging Optimism and Pessimism in Inference-Time Alignment](https://mlsanity.com/paper/2603.06797/) (2026)
- [Reward Learning from Best-of-N Preference Data: Targets, Tradeoffs, and Design Principles](https://mlsanity.com/paper/2605.30619/) (2026)
- [Certifiable Safe RLHF: Semantic Grounding and Fixed Penalty Constraint Optimization for Safer LLM Alignment](https://mlsanity.com/paper/2510.03520/) (2025)
- [Temper and Tilt Lead to SLOP: Reward Hacking Mitigation with Inference-Time Alignment](https://mlsanity.com/paper/2605.13537/) (2026)
- [Towards a theory of inference-time alignment with unknown rewards](https://mlsanity.com/paper/2608.15402/) (2026)
- [Privacy Without Regret: Differentially Private Inference-Time Alignment](https://mlsanity.com/paper/2608.26324/) (2026)
- [ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment](https://mlsanity.com/paper/2609.21899/) (2026)
- [Uniform Race: Parameter-Free Approximate Rejection Sampling](https://mlsanity.com/paper/2609.34639/) (2026)
- [Revisiting scaling laws for reward optimization](https://mlsanity.com/paper/2609.38526/) (2026)
- [Universal Bounds for Self-Normalized Kullback-Leibler Estimation](https://mlsanity.com/paper/2610.12851/) (2026)
- [Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems](https://mlsanity.com/paper/2610.19362/) (2026)

## Abstract (arXiv)

A simple yet effective method for inference-time alignment of generative models is Best-of-N (BoN), where N outcomes are sampled from a reference policy, evaluated using a proxy reward model, and the highest-scoring one is selected. While prior work argues that BoN is almost optimal in reward vs KL tradeoffs, the effectiveness of BoN depends critically on the quality of the proxy reward model used for selection. For this purpose, we study BoN through a smooth version known as Soft Best-of-N (SBoN) and develop a theoretical framework to address this gap. We analyze the scaling behaviour of BoN by providing bounds on the KL divergence between the SBoN policy and the reference policy, offering insights into how performance varies with the number of samples. We also study the regret gap, i.e., the gap between the expected true reward under the optimal policy and the SBoN policy. Our theoretical and empirical findings show that smoothing helps SBoN mitigate reward overoptimization, especially when the quality of the proxy reward is low.