Research map / Reinforcement learning / RL from feedback
Theoretical guarantees on the best-of-n alignment policy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that the widely used closed-form KL formula log(n) - (n-1)/n for best-of-n is only an upper bound, bounds the gap, proposes a new KL estimator and win-rate bounds (n/(n+1)) and analyzes rewind-and-repeat.
Problem
Commonly used analytical expression for the KL divergence between the best-of-n policy and the reference policy (log(n) - (n-1)/n) is assumed exact, yet its validity and tightness are unclear, and win-rate guarantees for best-of-n are lacking.
Approach
Derives the exact PMF of best-of-n via order statistics of i.i.d. uniform variables, proves the log(n)-(n-1)/n formula is an upper bound on KL, bounds the gap in terms of Rényi entropy and the top-reward outcome probability, proposes a new per-sample KL estimator d_n(eps_n) that closely tracks the true KL, and bounds win rate by n/(n+1).
Key results
- The analytical formula log(n)-(n-1)/n is shown to be an upper bound on the true KL, and the gap is unbounded when n*epsilon_inf >> 1 (e.g., in the two-outcome example the true KL is bounded by log 2 while the formula diverges).
- The proposed estimator d_n(eps_n) is strictly bounded by log(n)-(n-1)/n and empirically tracks the exact KL across uniform and cherry-picked distributions; conjectured to upper-bound the KL in expectation.
- Win rate of best-of-n against the reference is proven upper bounded by n/(n+1), with gap at most (n-1)/2 * exp(-H_2) and lower bounded away from zero by about epsilon_inf/2 as n grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Treat log(n) - (n-1)/n as an upper bound rather than the exact KL divergence | Best-of-n · General finite-support outcomes | KL divergence: ≤ log(n) - (n-1)/n | Mixed |
| Use the proposed estimator d_n(ε_n) instead of the analytical formula | Best-of-n KL estimation · Uniform and cherry-picked outcome distributions | KL divergence estimate accuracy | Helped |
| Use the alternate estimator based on ε_n instead of the analytical formula | Best-of-n KL estimation · n/L ≫ 1 | KL divergence estimate accuracy | Helped |
| Use the alternate estimator based on ε_n instead of the analytical formula | Best-of-n KL estimation · n/L ≪ 1 | KL divergence estimate accuracy: (n-1)/n | Hurt |
| Increase n while nε_n ≪ 1 | Best-of-n · Low-probability outcomes | KL divergence gap from analytical formula | No clear effect |
| Increase n while nε_n ≫ 1 | Best-of-n · Outcomes with non-negligible reference probability | KL divergence gap from analytical formula: log(n ε_∞ )+ o_n(\log n) | Hurt |
| Increase n for a δ-bound reference model while n²δ ≪ 1 | Best-of-n · δ-bound reference model | KL divergence gap from analytical formula: 2n (n-1) \delta | No clear effect |
| Use best-of-n instead of rewind-and-repeat | Alignment policies · Win rate versus KL tradeoff | Win rate at a given KL divergence | Helped |
| Use rewind-and-repeat instead of best-of-n | Alignment policies · Fixed compute budget | Reward | Helped |
| Increase n for best-of-n against the reference policy | Best-of-n · General | Win rate: ≤ n/(n+1) | Helped |
| Use the analytical formula to plot reward-KL tradeoffs instead of the actual KL divergence | Best-of-n tradeoff evaluation · Binary-output example | Win rate at a given KL divergence: 0.75 | Hurt |
Surprising findings
- The widely used KL formula for best-of-n is false in general and grows unboundedly while true KL saturates at log(L) for L outcomes.
- Best-of-n's win rate-KL tradeoff is more favorable than the formula suggests, and rewind-and-repeat is worse than best-of-n on the reward-KL tradeoff.
Limitations
- The KL-estimator upper-bound property is only conjectured, supported by numerical experiments rather than proof.
- Experiments are small-scale (toy distributions and four Alpaca prompts with one 9B model).
- Win-rate upper bound and gap bounds rely on the per-prompt discrete outcome assumptions (finite support, unique rewards).
Experimental setup
Datasets: Alpaca
Benchmarks: Alpaca prompts (exact KL estimation) machine translation prompts
Metrics: KL divergence win rate gap to analytical formula
Baselines: log(n) - (n-1)/n analytical formula rewind-and-repeat win rate optimal policy
Builds on: best-of-n sampling KL-regularized RL IPO
Closest papers by meaning
- Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment (ICML 2025 · similarity 0.90)
- BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling (NeurIPS 2024 · similarity 0.89)
- Variational Best-of-N Alignment (ICLR 2025 · similarity 0.88)
- Theoretical Limits of Language Model Alignment (NeurIPS 2026 · similarity 0.88)
- Learnable Chernoff Baselines for Provable Inference-Time Alignment (NeurIPS 2026 · similarity 0.87)
- BOND: Aligning LLMs with Best-of-N Distillation (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.