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

1 Introduction

• Inference-time alignment selects a response from base-policy samples using an imperfect reward model, with regret and query complexity measuring quality and compute.The framework distinguishes true reward from modeled reward and counts sampling, reward-evaluation, and log-probability queries.Source: §1 · p. 2

1.1 Contributions

• Best-of-N can achieve optimal regret under stringent uniform coverage when N is tuned, but overoptimizes beyond a critical N and lacks tight guarantees under weaker average-case coverage.Tail reward-model errors can select responses with high modeled reward but poor task performance.Source: §1 · p. 2, §1.1 · p. 3
• InferenceTimePessimism matches the framework’s best possible reward and remains scaling-monotonic, avoiding overoptimization as N grows beyond a regularization-determined threshold.It implements χ2-regularization through inference-time rejection sampling, applying pessimism in the face of uncertainty, and uses near-optimal compute.Source: §1.1 · p. 3
• Across tasks, base policies, and reward models, InferenceTimePessimism is scaling-monotonic while BoN-Alignment degrades as N increases, with some untuned-budget cases favoring InferenceTimePessimism.Figure 1 illustrates BoN-Alignment’s initial improvement followed by accuracy degradation and reward overoptimization, versus monotonic behavior for InferenceTimePessimism.Source: Figure 1 · p. 2, §1.1 · p. 3

1.2 Related Work

• The work provides a first framework connecting inference-time overoptimization to coverage and differs from prior alignment analyses by guaranteeing downstream performance under reward-model and true-reward mismatch.It abstracts away reward-model training, treating the model as given and optimizing per prompt; InferenceTimePessimism implements χ2-regularization at inference time, related to χPO (Huang et al., 2024b).Source: §1.2 · pp. 3–4

2 A Statistical Framework for Inference-Time Alignment

• Inference-time alignment uses a base policy πref, imperfect reward model br, and unknown true reward r⋆ to produce responses with low regret relative to a high-reward comparator policy π⋆.Regret is defined as the comparator’s expected true reward minus the algorithm-induced response distribution’s expected true reward.Source: §2 · p. 4
• Reward-model fidelity is required for low regret, with quality measured by expected squared error on responses drawn from πref; this formulation may yield conservative bounds.The framework treats the reward model’s error ε²_RM as given and abstracts away its training.Source: §2 · pp. 4–5
• Computational efficiency is modeled through sample-and-evaluate query complexity: algorithms sample responses from πref and observe each response’s likelihood and reward-model value.The total number of sampled and labeled responses, N, measures computation, encompassing Best-of-N and rejection-sampling schemes.Source: §2 · p. 5

2.1 A Skyline for Performance: The Necessity of Coverage

• Proposition 2.3 shows that coverage of high-reward comparator responses by πref is necessary: for any alignment algorithm, reward model, and comparator coverage level, a corresponding regret lower bound exists.The result makes base-policy coverage central to inference-time alignment, extending its established role in offline alignment.Source: §2.1 · p. 5

3.1 A Sharp Analysis of Best-of-N Alignment

• Best-of-N selects the highest-reward response among N i.i.d. samples from the reference policy, with guarantees governed by sample size, coverage, and reward-model error.Its regret reflects whether sampled candidates contain responses competitive with the comparator policy.Source: §3.1 · p. 6, §3 · p. 6
• Increasing N improves the chance of sampling high-quality responses but eventually amplifies overfitting to reward-model errors, causing regret to grow arbitrarily.Large N reaches farther into the reference-policy tail, where the imperfect reward model is more error-prone.Source: §3.1 · p. 6
• Best-of-N’s optimal N must balance quality gains against overoptimization, yet its best achievable regret scales as εRM(x)^2/3 and may miss the optimal skyline.The lower bound shows this dependence is tight even when the comparator has near-constant coverage, so additional computation cannot remove the limitation.Source: §3.1 · p. 7

3.2 Stronger Guarantees for Best-of-N Alignment under Uniform Coverage

• Under bounded uniform coverage, Best-of-N attains the statistical rate in the Proposition 2.3 skyline when N is tuned appropriately.This shows Best-of-N can be sufficient when the stronger coverage condition holds and the sample size can be selected optimally.Source: §3.2 · pp. 7–8
• Uniform-coverage guarantees can nevertheless be highly suboptimal because Cπ⋆∞(x) may greatly exceed Cπ⋆(x), including exponentially for softmax policies.The lower-bound construction illustrates this gap through an exponentially upweighted reference policy.Source: §3.2 · p. 8

4.1 The Inference-Time Pessimism Algorithm

• The algorithm samples an approximately χ2-regularized policy whose pessimism suppresses misleading low-probability, high-reward-model-error responses.β controls the tradeoff: small values yield greedier policies, while large values produce conservative, heavy-tailed response distributions; normalization uses O(N log N) computation and rejection sampling.Source: §4.1 · pp. 8–9

4.2 Theoretical Guarantees

• InferenceTimePessimism achieves regret-optimal performance under the coverage coefficient Cπ⋆(x), with a bound matching Proposition 2.3 up to absolute constants.The regularization parameter β balances overoptimization against bias, and the optimal guarantee requires N ≥ eΩ(...).Source: §4.2 · p. 10
• For any fixed β > 0, the guarantee holds for all sufficiently large N, so performance cannot fall below its bound as computation scales.This scaling-monotonicity provides robustness to reward-model overfitting, although performance may decay from an initially higher level.Source: §4.2 · p. 10
• The query-complexity lower bound shows that achieving the optimal regret rate requires N ≳ 1/εRM(x), matching InferenceTimePessimism’s guarantee.When N ≲ 1/εRM(x), regret can exceed the reward-estimation error εRM, establishing the necessity of this dependence for sample-and-evaluate algorithms.Source: §4.2 · p. 10
• Separating β from N lets users tune statistical performance independently of computational budget, unlike Best-of-N’s single-parameter design.Empirically, fixed β yields essentially monotonic performance as N increases, making β the primary parameter to tune when N uses the available budget.Source: §4 · p. 8, §4.2 · pp. 10–11

• The evaluation spans GSM8K, MMLU, and MATH, four reward models, four base policies, and bootstrapped subsamples of 20K generated responses per task-policy-reward triplet.A preliminary AlpacaEval-2.0 study and further experiments are deferred to Appendix B.Source: §5 · pp. 11–13
• InferenceTimePessimism’s accuracy increases monotonically with N, whereas BoN-Alignment exhibits a characteristic accuracy dip caused by reward overoptimization.On GSM8K, the comparison evaluates true reward as accuracy and estimated reward using OASST.Source: §5 · p. 12
• At fixed N = 213, increasing β improves InferenceTimePessimism’s true reward, reduces responses required for acceptance, and significantly decreases reward overoptimization.Figure 2 compares compute-normalized performance against BoN-Alignment; the estimated reward decreases as β increases.Source: §5 · p. 12, Figure 2 · p. 12
• Across GSM8K, MMLU, and MATH with four reward models, InferenceTimePessimism tends to outperform BoN-Alignment at a fixed computational budget, though many differences are not statistically significant.The comparison uses Phi-3-Mini as the base policy, BoN-Alignment with N = 213, and InferenceTimePessimism with the best β.Source: §5 · p. 12, Table 1 · p. 12
• The limited empirical separation is attributed to binary correctness rewards and optimal-policy settings where BoN is already predicted to be near-optimal.More refined metrics, such as proof correctness in addition to final-answer correctness, may produce a different comparison because their coverage conditions differ.Source: §5 · pp. 12–13

6 Conclusion

• The work identifies coverage, scaling, and optimality as central to inference-time alignment and highlights deliberate forms of inference-time computation.Its contributions include efficiently approximating regularized distributions, lower bounds on query complexity, regret analysis for approximate rejection sampling, and the optimal InferenceTimePessimism algorithm.Source: §6 · p. 13
• A key future direction is opening the base policy black box to exploit properties such as learned representations beyond coverage.The current formulation treats πref as a black box and uses only sample-and-evaluate access.Source: §6 · p. 13
• Another direction is co-designing training-time and inference-time alignment because inference-time Best-of-N can be suboptimal in general.Recent inference-aware training work includes Balashankar et al. (2024) and Chow et al. (2024).Source: §6 · p. 13
• Inference-time exploration could extend the offline-reward-model formulation to online settings where learners access the true reward function or a high-quality verifier.This direction is motivated by online reinforcement learning and aims to learn as quickly as possible through exploration.Source: §6 · p. 13

A Additional Related Work

• Prior theory analyzes Best-of-N properties such as reward–KL tradeoffs but generally lacks downstream guarantees under reward-model mismatch.The paper’s sample-and-evaluate framework is inspired by Huang et al. (2024a)’s language-model self-improvement framework, while using different problem formulations and techniques.Source: A Additional Related Work · p. 21
• Best-of-N is widely used empirically, and multiple studies report overoptimization, while other rejection-sampling and search methods rarely target mismatch-driven overoptimization.Inference-time search methods such as MCTS typically maximize a fixed reward with exact access, whereas rejection-sampling methods target distributions different from InferenceTimePessimism’s.Source: A Additional Related Work · p. 21
• Related complementary work distills inference-time procedures into policies or trains policies specifically to optimize downstream inference-time procedures such as Best-of-N.These lines include Amini et al. (2024), Sessa et al. (2024), Gui et al. (2024), Pace et al. (2024), Balashankar et al. (2024), and Chow et al. (2024).Source: A Additional Related Work · p. 21

A.1 Connection to Offline (Training-Time) Alignment

• InferenceTimePessimism is an inference-time analogue of χ2-regularized RLHF, whereas related online-alignment work assumes access to feedback from the true reward model.The offline-alignment connection includes robustness to reward-model overoptimization under coverage assumptions.Source: §A.1 · pp. 21–22
• Inference-time alignment abstracts offline alignment by treating the reward model as fixed and optimizing per-instance regret for each arbitrary prompt, with respect to both estimated and true rewards.The framework can be combined with reward-estimation procedures to derive end-to-end offline-alignment sample-complexity guarantees.Source: §A.1 · pp. 21–22

B Further Empirical Results

• The expanded empirical study covers more policies, tasks, and reward models, plus robustness to β, estimated-reward distributions, and preliminary AlpacaEval-2.0 results.These experiments extend the evaluations introduced in the main text.Source: B Further Empirical Results · p. 22

B.1 Further Experimental Details

• The benchmark suite includes GSM8K, college-level MMLU math and chemistry, hard MATH problems, and a 128-question AlpacaEval-2.0 subset.GSM8K, MMLU, and MATH use zero-shot chain-of-thought prompting with correctness-based rewards; AlpacaEval-2.0 uses evaluator-model win rate against πref generations.Source: §B.1 · p. 22
• For each task, experiments consider a subset of four estimated reward models: OASST based on Pythia-1.4b, GEMMA-RM on Gemma-2-2b, LLAMA-RM on Llama-3-3b, and ARMO-RM on Llama-3-8b.Source: §B.1 · p. 22
• For every prompt, task, and policy, the experiments generate about 20K temperature-1 responses, then bootstrap M subsets of N responses, using M = 50 except M = 5 for AlpacaEval-2.0.The same N samples estimate the normalization constant and run rejection sampling for fixed N.Source: §B.1 · p. 23
• Reported policy accuracy averages correct answers across prompts and replicates with prompt-marginalized standard errors, while AlpacaEval-2.0 reports evaluator-model win rate.The appendix first adds omitted plots, then presents the additional experiments described for later subsections.Source: §B.1 · p. 23

Compute-budget effects

• InferenceTimePessimism is essentially monotonic in compute budget across GSM8K, MMLU, and MATH, while BoN-Alignment is monotonic for some more in-distribution task-policy pairs.The BoN-Alignment behavior is consistent with some rewards, such as ARMO-RM, matching certain task-policy pairs better than others.Source: §B.2 · p. 23

Regularization effects

• Increasing β reduces the average responses required before rejection sampling terminates and lowers the estimated reward when using the same N = 2^13 sample budget.InferenceTimePessimism uses all N samples to estimate the normalization constant before rejection sampling, and all evaluated prompts terminate within the budget.Source: §B.2 · p. 23

Cross-policy and task comparisons

• Across the evaluated policies, tasks, and four reward models, properly tuned BoN-Alignment and InferenceTimePessimism achieve similar performance.This comparison covers Phi-3-Small, Mistral-7B, and LLAMA-3-3B, with LLAMA-3-3B evaluated only on GSM8K and MMLU.Source: §B.2 · p. 23

B.3 Further Experiments

• ARMO-RM most clearly separates correct from incorrect responses, and its incorrect-response reward support is below the correct-response maximum for the illustrated GSM8K prompt.This makes large-N BoN-Alignment select the correct answer for that prompt, while InferenceTimePessimism can be overly conservative when the reward model already substantially underestimates true reward.Source: §B.3 · p. 28, Figure 9 · p. 28
• InferenceTimePessimism experiences less over-optimization than BoN-Alignment across a range of β values, though avoiding over-optimization entirely typically requires tuning β.In some in-distribution reward-model settings, BoN-Alignment is itself monotonic without further intervention.Source: §B.3 · p. 28
• Small β values can cause a performance dip because rejection sampling may accept no responses, triggering the fallback to BoN-Alignment, especially when N is small relative to 1/β.The fallback is reasonable because theory predicts BoN-Alignment should perform well in the small-N regime.Source: §B.3 · p. 28

B.4 Results for AlpacaEval-2.0

• AlpacaEval-2.0 results do not statistically distinguish BoN-Alignment from InferenceTimePessimism because evaluation is noisy and uses only 5 replicates per prompt with fewer prompts.The broader trends nevertheless agree with those observed on the other tasks.Source: §B.4 · pp. 28–29, Figure 11 · p. 29

C Normalization Constant Computation

• ComputeNormConstant sorts responses into reward-value bins and computes the normalization constant by iteratively updating weighted sums over those bins.Algorithm 5 takes x, reward model br, reference policy πref, regularization coefficient β > 0, and sampled responses as input.Source: C Normalization Constant Computation · p. 30

C.1 Background

• The normalization constant always exists because the relevant function is continuous, piecewise linear, decreasing in λ, and ranges from ∞ at −∞ to 0 at ∞.The subroutine computes it in O(N log N) time using a dynamic-programming-like procedure.Source: §C.1 · p. 30

C.2 Guarantee for ComputeNormConstant

• Lemma C.1 states that Algorithm 3 finds λ such that bΦ(λ) := 1, while Lemma C.2 gives a corresponding generalized guarantee for Algorithm 5.Source: §C.2 · p. 30
• The ComputeNormConstant proof relies on continuity and monotonicity of bΦ, locating λ⋆ between sorted surrogate rewards before Algorithm 5 performs a linear pass after sorting.Sorting and binning take O(N log N) and O(N), respectively, while the final scan uses at most N constant-time iterations.Source: §C.2 · p. 31

D Rejection Sampling

• RejectionSampling draws N responses from πref, accepts each using a truncated importance weight divided by M, and returns the first response if none is accepted.When M uniformly bounds the likelihood ratio, accepted samples match π; otherwise, truncation removes target mass above M · πref.Source: §D.1 · p. 32

D.1 Background

• RejectionSampling cannot recover target mass outside πref’s support or poorly covered regions, motivating EM-divergence as a measure of truncation loss.The appendix uses this measure to analyze how closely the rejection-sampling distribution approximates π as M varies.Source: §D.1 · p. 32
• Increasing M decreases EM-divergence but raises the sample count needed for termination, whereas smaller M increases bias from truncating target-density regions.Thus, M controls a bias-variance tradeoff, and the divergence’s irreducible component reflects information-theoretic mismatch between π and πref.Source: §D.1 · p. 33

D.2 Guarantee for RejectionSampling

• Lemma D.4 bounds total variation error by an EM-divergence term determined by M plus an exponential-in-1/N termination-failure term.The EM term decreases with larger M, while the termination term decreases with larger N; the former remains even as N tends to infinity.Source: §D.2 · pp. 33–34
• Conditioned on acceptance, RejectionSampling outputs the normalized truncated policy, while failure to accept any of N samples creates the additional approximation error.The proof identifies the accepted-response law with the truncated distribution and substitutes its retained mass, 1 − EM(π, πref), into the bound.Source: §D.2 · p. 35

Implications

• The sample lower bound is tight for every selection strategy that chooses a response from the sampled set.The result is later used as a component of the main regret lower bounds in Theorems 3.2 and 4.2.Source: §D.3 · p. 36

Selection strategies

• Any selection strategy receives N i.i.d. responses from πref for prompt x and returns one response from that sample, possibly at random.This is Definition D.5’s selection-strategy framework.Source: §D.3 · p. 36

TV lower bound

• At least Mπ_x,ε samples are necessary for a selection strategy to induce a response distribution ε-close to π.Lemma D.6 gives this information-theoretic lower bound, adapted from Block and Polyanskiy (2023).Source: §D.3 · p. 36

E Proofs from Section 2

• The Section 2 proof establishes an elementary reward-function construction by perturbing the reward model with the difference between comparator and reference-policy probabilities.It defines expected reward J_r and chooses r⋆ from br, π⋆, bπ, and ε, after which the claimed result follows directly.Source: E Proofs from Section 2 · p. 37

F.1 General Regret Decomposition for BoN-Alignment

• BoN-Alignment’s central regret bound uses an intermediate rejection-sampling comparator and decomposes performance into approximation and reward-estimation errors.The comparator approximates the target policy in total variation, while BoN competes with it under the reward model; the analysis also bounds BoN’s likelihood ratio by N.Source: §F.1 · pp. 39, 41

F Proofs from Section 3

• The EM-divergence parameter M trades off lower achievable regret against higher sample complexity, enabling later instantiations through the Cπ and Cπ∞ coverage coefficients.The proofs of the Section 3 theorems translate EM-divergence bounds into standard distribution-shift coverage measures using Proposition D.3.Source: §F.1 · p. 39, F Proofs from Section 3 · p. 39

F.2 General Lower Bounds on Regret

• Any inference-time selection algorithm faces an information-theoretic regret lower bound below a coverage-dependent sample threshold, while BoN incurs an additional large-N lower bound.The lower bounds apply across parameter ranges and separate unavoidable difficulty in simulating the target distribution from BoN-specific overfitting to the reward model.Source: §F.2 · p. 42

F.2.2 Lower Bounds under L1-Coverage

• Under L1-coverage, the lower-bound construction uses an exponentially separated coverage regime on a countably infinite response space.The construction has Cπ⋆∞ exponentially larger than Cπ⋆, with response probabilities and true rewards increasing while reward-model values decrease.Source: §F.2 · p. 42, §F.2.2 · p. 44

F.2.1 Lower Bounds under L∞-Coverage

• Under L∞-coverage, any selection algorithm has a small-N regret lower bound, and BoN can suffer regret for every N when reward-model overfitting selects a bad response.The construction makes the bad response highest under the reward model, so BoN selects it whenever it appears, an event occurring with at least constant probability.Source: §F.2.1 · pp. 42–44

F.2.3 Supporting Lemmas

• A supporting lemma shows that the coverage upper bound is tight up to logarithmic factors and that approximating the target policy from reference-policy samples is information-theoretically hard.When N < 1/(12ε), every selection algorithm has DTV(π(x), π_A(x)) > ε.Source: §F.2.3 · pp. 48–49

F.3 Proof of Theorem 3.1

• The proof of Theorem 3.1 combines Proposition D.3 with Lemma F.1 to obtain a guarantee when M is sufficiently large and selects N by balancing N-dependent terms.The stated condition includes E_M(π⋆(x), π_ref(x)) ≤ C_π⋆(x), while the resulting sample requirement is described as N ≥ 2 · C_π⋆(x) · log … .Source: Proof of Theorem 3.1 · pp. 49–50

F.4 Proof of Theorem 3.2

• Theorem 3.2 is proved by applying Theorem F.3 with C = 2 for its first part and Theorem F.4 with p = 1 for its second part.The first argument applies when N ≥ 1, with c a universal constant.Source: Proof of Theorem 3.2 · p. 50

F.5 Proof of Theorem 3.4

• Theorem 3.4 follows by taking M = ∞, which gives E_M(π⋆(x), π_ref(x)) = 0, and then applying Lemma F.1 for the stated guarantees.Its second part considers N ≥ C_π⋆(x) and yields a bound involving ε_RM(x) · log(R_max/ε_RM(x)).Source: §F.5 · p. 50

F.6 Additional Results

• An additional result gives BoN-Alignment a regret guarantee in terms of the information-theoretic quantity Mπ, complementing interpretable bounds involving coverage coefficients and N.The main theorems are presented as relaxations that isolate coverage and computation dependencies.Source: §F.6 · p. 51

G Proofs from Section 4

• The proof of Theorem 4.1 conditions on one prompt, defines expected reward-model return, and decomposes regret into terms controlled by normalization and concentration bounds.The analysis chooses bλ through Algorithm 3, establishes its feasible λ range, and uses a high-probability bound for sufficiently large N.Source: G Proofs from Section 4 · p. 52, Proof of Theorem 4.1 · p. 52

G.1 Proof of Theorem 4.1

• Theorem 4.1’s proof controls the remaining regret components using Cauchy–Schwarz and AM–GM inequalities after enforcing the normalization condition Φ(bλ)=1.These steps yield the final bound by combining the three decomposed terms under the high-probability event.Source: Proof of Theorem 4.1 · pp. 52–53

G.1.1 Supporting Lemmas

• Lemma G.1 relates the objective gap for πλ to any comparator policy, while Lemma G.2 characterizes πλ as the unique optimizer of a strongly convex constrained problem.Strong duality and KKT conditions establish the optimizer and determine λ within the stated interval.Source: §G.1.1 · pp. 53–54
• The KKT case analysis yields the optimal policy π(y) = πref(y) · relu(β−1(r(y) −λ)), with λ selected so the policy normalizes to α.Complementary slackness determines zero mass below the threshold and the relu-weighted form above it.Source: §G.1.1 · p. 55
• Lemma G.3 provides a high-probability empirical bound uniformly over λ ∈ [−γ, Rmax −γ] for estimates formed from N samples.The proof applies Bernstein’s inequality, bounds the variance of relu(r(y) −λ), discretizes λ, and uses a union bound.Source: §G.1.1 · pp. 55–56

G.2 Proof of Theorem 4.2

• The proof fixes N ≲ 1 εRM and applies the first part of Theorem F.4 with εRM = εRM and p = 1.Source: Proof of Theorem 4.2 · p. 56
• The construction has Cπ⋆(x) = O(log C), providing the stated coverage-complexity scaling.Source: Proof of Theorem 4.2 · p. 56
• Any algorithm using N′ incurs at least the derived regret lower bound, which therefore applies to N′ = N.Source: Proof of Theorem 4.2 · p. 57