Research map / Reinforcement learning / RL from feedback

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

ICML 2025 · Reinforcement learning › RL from feedback · approach: GRPO stability and variants · 0 citations (OpenAlex)

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.

Formalizes inference-time alignment as a sample-and-evaluate problem, proves Best-of-N is suboptimal under average coverage, and proposes InferenceTimePessimism (chi-square-regularized rejection sampling at inference time) that is regret-optimal and scaling-monotonic.

Problem

Best-of-N sampling at inference time improves a pre-trained policy's responses but degrades due to reward overoptimization as N grows; the paper asks how well inference-time alignment can perform given an imperfect reward model and how much compute is needed.

Approach

Replace the single-parameter Best-of-N with a chi-square-regularized target distribution pi(y|x) proportional to pi_ref(y|x) times relu((r_hat - lambda)/beta), sampled at inference time via rejection sampling with an estimated normalizer, implementing pessimism in the face of uncertainty and separating compute (N) from regularization (beta).

Key results

• InferenceTimePessimism's accuracy increases monotonically with N on GSM8K while Best-of-N dips at large N due to reward overoptimization.
• With N=2^13, InferenceTimePessimism tends to have higher average accuracy lift than BoN across tasks, e.g., Mistral-7B on GSM8K with OASST reward: 4.15 vs -12.10 percent lift.
• Theory: BoN regret scales as sqrt(N*eps) for large N (degrades), while InferenceTimePessimism achieves sqrt(C*eps) regret, matching a lower bound.

Measured effects reported in the paper

Surprising findings

• Best-of-N with a tuned N performs similarly to InferenceTimePessimism on binary-reward tasks, since coverage measures coincide there.
• KL-regularized rejection sampling requires exponentially many samples in Rmax/beta, unlike the chi-square approach.

Limitations

• Experiments use binary correctness rewards, where BoN and the proposed method perform similarly, so the advantage is not clearly shown in realistic settings.
• Requires tuning beta, and defaults to BoN when rejection sampling accepts no responses for small N.
• Analysis is worst-case over the reward model error and abstracts away reward training.

Experimental setup

Datasets: GSM8K MMLU MATH AlpacaEval-2.0

Benchmarks: GSM8K MMLU MATH AlpacaEval-2.0

Metrics: accuracy lift over base policy win rate

Baselines: Best-of-N

Builds on: best-of-n sampling chi-PO approximate rejection sampling KL-regularized RLHF

Closest papers by meaning

• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference (ICML 2026 · similarity 0.92)
• Inference-Time Reward Hacking in Large Language Models (NeurIPS 2025 · similarity 0.92)
• Inference-time Alignment in Continuous Space (NeurIPS 2025 · similarity 0.91)
• Compute Aligned Training: Optimizing for Test Time Inference (NeurIPS 2026 · similarity 0.91)
• Fast Best-of-N Decoding via Speculative Rejection (NeurIPS 2024 · similarity 0.91)
• Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems (NeurIPS 2026 · similarity 0.90)