PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Best-of-N policy evaluation for inference-time alignment

Jonas Schweisthal, Yuxin Wang, Athiya Deviyani, Stefan Feuerriegel, Dennis Frauen

arXiv:2610.09250v1cs.LGcs.AIstat.ML

TL;DR

BoN policy evaluation from logged data is challenging when response likelihoods are unavailable under sample-only access. The paper develops a doubly robust estimator and uncertainty-aware budget-selection rules using sample-estimable score-rank probabilities. In realistic LLM settings, BoN-DR estimates values more accurately than alternatives and gives substantially narrower confidence intervals than BoN-IPW at N = 256.

  • Problem

    Under sample-only access, standard off-policy estimators cannot directly evaluate BoN because the required density ratios depend on unavailable response likelihoods.

    Source: §1 · p. 1

  • Method

    The paper uses BoN's order-statistic structure to estimate density ratios from score-rank probabilities and develops BoN-DR plus value-maximizing and lower-confidence-bound budget rules.

    Source: §1 · p. 2, §4 · p. 4

  • Results

    At N = 256, BoN-DR gives the most accurate policy-value estimates in the realistic LLM comparison, with BoN-IPW intervals 1.7–5.5× wider.

    Source: §6 · p. 9

  • Takeaways & Limitations

    Safe Improvement accounts for uncertainty in budget comparisons and provides an asymptotic no-harm guarantee relative to the reference policy.

    Source: §1 · p. 2

    The method requires logged data, and density-ratio estimation for high-dimensional text actions can have high variance and numerical instability.

    Source: §4 · p. 4, §6 · p. 10

Abstract

from arXiv · show

Best-of-N (BoN) is a common inference-time alignment method that selects the highest-scoring response among N samples from a reference model. Evaluating BoN policies from logged data is challenging under sample-only access because standard off-policy estimators require density ratios that depend on unavailable response likelihoods. In this paper, we propose a sample-only framework for evaluating and selecting BoN policies without access to these likelihoods. We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities that are estimable from samples alone. We then develop a doubly robust estimator of the BoN policy value (BoN-DR) that efficiently reuses a shared auxiliary sample pool across candidate budgets. We establish valid asymptotic inference even under reward estimator misspecification and prove the efficiency of our BoN-DR estimator. Since larger budgets can amplify errors in the score function and lead to reward overoptimization, we derive two selection rules: (i) maximizing the estimated policy value and (ii) maximizing a lower confidence bound on the improvement over the reference policy, which accounts for estimation uncertainty and provides a no-harm guarantee. Across synthetic experiments and GSM8K with multiple reference and reward models, our framework accurately estimates BoN policy values and selects effective sampling budgets.

1 INTRODUCTION

The introduction frames BoN budget selection as a sample-only evaluation problem: response likelihoods are unavailable, while larger budgets can amplify score errors and make value estimates noisy. It presents BoN-DR and uncertainty-aware selection rules, with guarantees and experiments supporting the framework.

1 INTRODUCTION

  • Standard off-policy estimators cannot directly evaluate BoN under sample-only access because their density ratios require unavailable response likelihoods.The framework uses BoN's order-statistic structure to express these ratios through score-rank probabilities estimable from samples.Source: §1 · pp. 1–3
  • Larger budgets can amplify score errors, while noisy value estimates—especially at large N—can make direct maximization harmful.Figure 1 shows selected-response scores rising with N while downstream accuracy can peak and decline.Source: §1 · p. 2, Figure 1 · p. 2
  • BoN-DR separates the selection score from the reward estimator, reuses one auxiliary sample pool across budgets, and supports valid asymptotic inference despite reward-estimator misspecification.It is unbiased for any finite pool size and attains exact-ratio doubly robust efficiency as the pool grows when the reward estimator is consistent.Source: §1 · p. 2
  • Value Maximization selects the largest estimated value, while Safe Improvement selects the largest lower confidence bound on improvement and falls back to N = 1 if none is positive.Both rules asymptotically attain the best value on the candidate grid; Safe Improvement additionally has an asymptotic no-harm guarantee, using simultaneous bounds valid after selection.Source: §1 · p. 2
  • BoN-DR estimates policy values from logged data using only reference-model samples, and the paper evaluates it in synthetic experiments and on GSM8K.The estimator is doubly robust and unbiased; the paper also establishes statistical guarantees.Source: §1 · p. 3
  • The paper distinguishes its logged-data approach from prior budget tuning that requires true rewards for every sampled candidate and lacks uncertainty quantification.Here, selection uses one observed reward per prompt and provides statistical guarantees.Source: §1 · p. 3

3 PROBLEM SETUP

The setup treats logged responses and rewards as data from a reference policy, with inference-time alignment constrained to sample access rather than model weights or response likelihoods. It formulates BoN evaluation and budget selection as two challenges, while noting that larger budgets can amplify score errors.

3 PROBLEM SETUP

  • The logged-data setup defines context X, action A, scalar reward Y, reward function µ(x, a), and policy value as expected reward under a policy.The observed action is generated by a behavior or reference policy, and logged observations are i.i.d.Source: §3 · pp. 3–4
  • For API-based inference-time alignment, the reference model can be sampled but its weights and response likelihoods cannot be accessed.The goal is to improve the deployed policy using samples and logged data.Source: §3 · p. 3
  • BoN samples N actions from the reference policy and selects the action with the highest score for each context.The score may be an LLM judge or an estimator of the reward function.Source: §3 · p. 3
  • Increasing N concentrates BoN on high-scoring actions, but larger budgets can amplify score errors and lead to reward overoptimization.Such actions may be rare under the reference policy and weakly represented in logged data.Source: §3 · pp. 3–4
  • The setup poses two questions: how to estimate BoN policy value from reference-policy data under sample-only access, and how to select N with statistical guarantees.The target policy value is denoted V(π^s_N).Source: §3 · p. 4

4 EFFICIENT OFF-POLICY EVALUATION FOR BON

The section develops a sample-only doubly robust estimator for BoN by expressing its density ratio through score-rank probabilities and reusing auxiliary samples across budgets. It establishes valid inference under reward-estimator misspecification and efficiency when the reward estimator is consistent.

4 EFFICIENT OFF-POLICY EVALUATION FOR BON

  • Standard DR estimation is not directly applicable because the BoN policy probabilities and target-to-behavior density ratio are unavailable in the high-dimensional text action space.Sequence probabilities may be extremely small, making density-ratio estimation prone to high variance and numerical instability.Source: §4 · p. 4

4.1 INFERENCE-TIME DR SCORE

  • The BoN DR score can be expressed using score-rank probabilities, avoiding evaluation of the reference or BoN response likelihoods.The density ratio becomes a function of relative score ranks, which are probabilities of comparison events estimable from reference-policy samples.Source: §4.1 · pp. 4–5

4.2 POOLED BON-DR ESTIMATOR

  • A single auxiliary sample pool estimates both DR components and can be reused to evaluate BoN policies across candidate budgets N.The pooled estimator applies U-statistics by averaging over subsets of a larger sample pool.Source: §4.2 · pp. 5–6

4.3 THEORETICAL GUARANTEES

  • BoN-DR gives valid root-n inference without requiring the reward estimator to be consistent; with a consistent reward estimator, it attains the oracle DR estimator’s first-order efficiency bound.For fixed N, the stated condition for vanishing first-order bias is M_n → ∞, with no particular growth rate relative to n required.Source: §4.3 · pp. 6–7

5 SELECTING THE OPTIMAL SAMPLING BUDGET N FOR BON

The paper proposes Value Maximization and Safe Improvement to choose a BoN budget from candidate policies. Both target the best policy on the candidate grid, while Safe Improvement adds a no-harm safeguard relative to the reference policy.

5 SELECTING THE OPTIMAL SAMPLING BUDGET N FOR BON

  • The two rules select among candidate budgets using estimated policy values or lower confidence bounds on improvement over the reference policy.Safe Improvement uses simultaneous bounds because budgets are selected adaptively from a shared candidate grid.Source: §5 · p. 7, §5.2 · p. 7

5.1 VALUE MAXIMIZATION

  • Value Maximization chooses the budget with the largest estimated policy value and asymptotically recovers the best value on the fixed candidate grid.This guarantee inherits BoN-DR's robustness and does not require the reward estimator to consistently estimate the true reward, but finite-sample noise can still select a policy worse than the reference.Source: §5.1 · p. 7

5.2 SAFE IMPROVEMENT

  • Safe Improvement selects a budget only when its simultaneous lower confidence bound supports improvement, otherwise falling back to N = 1.Asymptotically it combines a no-harm guarantee with recovery of the best policy value on the fixed candidate grid; finite-sample conservatism can lead it to select smaller budgets than Value Maximization.Source: §5.2 · pp. 7–8

6 EXPERIMENTS

The experiments test estimator robustness and accuracy, budget-selection safety, and the paper's theoretical properties. BoN-DR remains robust under reward-estimator misspecification, is most accurate in the realistic GSM8K comparisons, and Safe Improvement makes fewer harmful selections than Value Maximization.

6 EXPERIMENTS

  • The experiments use synthetic data and GSM8K, comparing three estimators on shared logged data and auxiliary samples, and assess estimation and selection performance.The GSM8K setting uses three reference models, two external reward models, exact-match correctness as reward, and a stored pool of 512 responses per prompt.Source: §6 · p. 8
  • As reward-estimator error increases with δ, Plug-in becomes biased, while BoN-DR and BoN-IPW remain nearly unbiased and maintain confidence-interval coverage close to nominal 95% across considered misspecification levels.The experiment varies δ without changing the induced policy; Figure 2 shows absolute bias, nominal 95% pointwise-CI coverage, and Safe Improvement gain for the selected budget over N = 1.Source: §6 · p. 8, Figure 2 · p. 9
  • On GSM8K, BoN-DR gives the most accurate policy-value estimates and at N = 256 has intervals 1.7–5.5× narrower than BoN-IPW.Plug-in remains biased even when the score function ranks responses accurately in the Skywork setting; Figure 3 compares estimates with oracle values across reward-model rows and reference-model columns.Source: Figure 3 · p. 9, §6 · p. 9
  • Safe Improvement makes fewer harmful selections than Value Maximization, while both proposed rules outperform Plug-in and Naïve BoN overall.The comparison is for Qwen3.5-4B with OASST-RM-2.1; harm means negative gain relative to N = 1.Source: §6 · p. 10, Figure 4 · p. 10

A EXTENDED RELATED WORK

  • Earlier OPE methods require behavior-policy action probabilities, while the closest cited BoN budget-tuning approach requires rewards for every sampled response.This paper instead selects N from logged data with simultaneous confidence bounds and a no-harm guarantee.Source: A EXTENDED RELATED WORK · p. 14

B.1 REGULARITY CONDITIONS

  • The efficiency result avoids a nuisance-function product-rate condition because pooled weights are conditionally unbiased; independent training data also avoids Donsker or entropy conditions.The efficiency statement treats the behavior sampler and, conditional on training, the induced BoN policy as fixed.Source: §B.1 · p. 15

B.2 PROOF OF PROPOSITION 4.1

  • When candidates tie in score, the proof averages over tied competitors to calculate selection probability and express the BoN density ratio.The tie probability is positive for an action in the behavior-policy support.Source: §B.2 · p. 16

B.3 FINITE-POOL UNBIASEDNESS

  • Averaging across auxiliary-pool subsets reproduces fresh BoN candidate sets, and Q_J/N represents the logged response's selection probability in a given subset.The proof uses this representation to establish the finite-pool result.Source: §B.3 · pp. 16–17

B.4 PROOF OF THEOREM 4.2

The proof establishes asymptotic properties of BoN-DR, including efficiency without requiring a rate condition between the logged sample size and auxiliary-pool size. It also establishes value consistency for Value Maximization and asymptotic no-harm behavior for Safe Improvement.

B.4 PROOF OF THEOREM 4.2

  • BoN-DR’s influence function is efficient, and its finite-pool approximation needs no rate condition between pool size and logged sample size.The approximation is mean zero for every pool size; it suffices for its per-observation variance to vanish as the pool grows.Source: §B.4 · p. 18

B.5 PROOF OF COROLLARY 5.1

  • The Value Maximization rule attains the best policy value on the finite candidate grid asymptotically, without requiring a unique maximizing budget.The conclusion concerns the selected policy value, not the selected budget index.Source: §B.5 · p. 19

B.6 PROOF OF THEOREM 5.2

  • Safe Improvement asymptotically selects the best positive grid improvement, while reverting to the reference policy when no positive improvement is supported.When the best improvement is zero, the selected policy either is the baseline or has population improvement converging to zero.Source: §B.6 · p. 19

C.1 SYNTHETIC EXPERIMENTS

The experiments define controlled synthetic and GSM8K settings, then assess estimator accuracy, uncertainty, efficiency, and budget selection. Across the reported checks, increasing validation data improves stability, while weak overlap at extreme budgets can degrade coverage.

C.1 SYNTHETIC EXPERIMENTS

  • The main experiments used n = 4,096 logged observations per repetition, 300 repetitions, and candidate budgets N = {1, 2, 4, ..., 256}, with M ≥ Nmax independent auxiliary draws per logged context; shared random streams paired data across estimators and error settings.The oracle budget is the smallest maximizer of VN(γ) over N; population values were used only for evaluation.Source: §C.1 · p. 20

C.2 GSM8K ENVIRONMENT

  • GSM8K uses 3,973 validation prompts, with one logged response per prompt and remaining stored responses forming the auxiliary pool.The study fits its reward calibration on 3,500 training prompts and holds it fixed; this favors Plug-in because calibration uses the same score defining the target policy.Source: §C.2 · pp. 20–21

C.3 BASELINE ESTIMATORS

  • BoN-IPW uses logged rewards with the estimated BoN density ratio, whereas Plug-in uses only the estimated reward function and does not correct its errors.These are the two component baselines of pooled BoN-DR.Source: §C.3 · p. 21

C.4 CONFIDENCE STATEMENTS; C.5 METRIC DEFINITIONS; C.6 REPRODUCIBILITY

  • The evaluation reports pointwise Wald intervals, simultaneous bootstrap bounds, defined error and harm metrics, and paired comparisons from a frozen result set.The confidence procedure shares multiplier draws across budgets; estimators are compared on the same per-repetition inputs.Source: §C.4 · p. 21, §C.5 · p. 21, §C.6 · p. 22

D.1 REWARD OVEROPTIMIZATION UNDER SCORE FUNCTION MISSPECIFICATION

  • With score-function misspecification, selected scores keep rising with N while true policy value can peak and then decline as overlap weakens.The experiment fixes reward-function error at δ = 0.4 and varies score-function error γ.Source: §D.1 · p. 22, Figure 5 · p. 22

D.2 SENSITIVITY TO VALIDATION-SET SIZE

  • As logged validation size grows, BoN-DR and BoN-IPW RMSE decreases, coverage approaches 95%, and BoN-DR reaches high oracle-budget selection accuracy sooner.Plug-in bias persists as validation size increases.Source: §D.2 · p. 22, Figure 6 · p. 23

D.3 FINITE-M EFFICIENCY

  • At N = 256, the finite-M DR variance ratio falls from 1.335 at M = 256 to 1.019 at M = 4096; DR stays near the efficiency bound while IPW exceeds it by up to 4.9×.The synthetic efficiency experiment uses a correctly specified reward function, γ = 0.65, n = 4,096, and 300 repetitions.Source: §D.3 · p. 23, Figure 7 · p. 23

D.4 REAL COVERAGE

  • On GSM8K, BoN-DR and BoN-IPW cover near the nominal 95% level over most budgets, but DR coverage falls at the largest budgets; Plug-in coverage is zero from N = 4.The largest-budget DR undercoverage coincides with weak rank-weight overlap.Source: §D.4 · p. 23, Figure 8 · p. 24

D.5 ERROR DECOMPOSITION OVER THE BUDGET GRID

The GSM8K error decomposition shows distinct estimator trade-offs across budgets, while overlap diagnostics reveal that extreme budgets concentrate rank weights on very few prompts.

D.5 ERROR DECOMPOSITION OVER THE BUDGET GRID

  • Across the budget grid, Plug-in has large nearly constant bias, while DR and IPW are essentially unbiased but become more dispersed as overlap deteriorates.Plug-in becomes competitive in RMSE only at the largest budgets, trading its constant bias against negligible variance.Source: §D.5 · p. 24, Figure 9 · p. 24

D.6 OVERLAP DIAGNOSTICS

  • Rank-weight effective sample size falls from 3,973 prompts at N = 1 to about 25 at N = 256 and about 10 at N = 512, where only 0.5% receive non-zero weight.Extending the grid to N = 512 roughly doubles DR residual harm under Safe Improvement on the two OASST configurations, while IPW remains at 0.00 and 0.01.Source: §D.6 · p. 25, Figure 10 · p. 25

D.7 ROBUSTNESS TO THE REWARD FUNCTION

The GSM8K robustness comparison uses independently trained reward functions and reports zero Plug-in coverage for both, indicating that the reported coverage failure is not specific to the score-calibration spline.

D.7 ROBUSTNESS TO THE REWARD FUNCTION

  • Plug-in coverage is zero with both independently trained reward functions, so the reported failure is not an artifact of the score-calibration spline.The comparison uses a TF–IDF logistic regression and an embedding-based LightGBM reward model.Source: §D.7 · p. 26
  • The zero-coverage finding supports robustness of the Plug-in failure across reward-function choices, rather than dependence on the main-text calibration spline.The passage specifically attributes the result to estimator misspecification.Source: §D.7 · p. 26
  • Table 3 evaluates GSM8K estimation at N = 256 with the OASST score function and independently trained reward functions.Its caption identifies nominal 95% pointwise interval coverage and marks the lowest RMSE within each reference-model and reward-function combination.Source: Table 3 · p. 26

E ADDITIONAL RESULTS FOR SELECTION

Table 4 compares budget-selection outcomes in a synthetic setting and on GSM8K; the Safe Improvement results show how uncertainty-aware selection behaves when increasing the budget can help or harm.

E ADDITIONAL RESULTS FOR SELECTION

E.1 SAFE IMPROVEMENT REDUCES HARMFUL BUDGET CHOICES.

  • In the synthetic setting, BoN-IPW and BoN-DR Value Maximization recover nearly all attainable gain with no observed harm, while Naive BoN and Plug-in harm in every repetition.Safe Improvement retains most of the gain and also avoids harmful selections.Source: §E.1 · p. 27, Figure 11 · p. 27
  • On GSM8K, Value Maximization loses 0.84 accuracy percentage points with BoN-IPW and 0.82 with BoN-DR, while Safe Improvement cuts harm rates to 1% and 14%, respectively.The reference policy is optimal in this regime, so the best attainable gain is zero; the remaining BoN-DR harm is consistent with finite-sample undercoverage at the largest budgets.Source: §E.1 · p. 27, Figure 11 · p. 27

E.2 COMPLETE RESULTS ON GSM8K

Across six GSM8K configurations, Safe Improvement reduces harm under OASST in key estimator settings, while outcomes differ under the aligned Skywork reward model.

E.2 COMPLETE RESULTS ON GSM8K

  • Under OASST, Safe Improvement reduces the harm incurred by Value Maximization with DR and IPW, though DR retains residual harm on Llama and Qwen.The table covers all six configurations, including aligned configurations omitted from RQ3.Source: §E.2 · p. 28, Table 5 · p. 28
  • Under the aligned Skywork reward model, no rule incurs harm, and Safe Improvement reduces gain without reducing observed harm, most visibly for IPW.Source: §E.2 · p. 28, Table 5 · p. 28
  • Table 5 reports gain in accuracy points against N = 1 and harm rate for the complete GSM8K selection results.Naive BoN is reported once per configuration because it does not depend on the selection rule.Source: Table 5 · p. 28

E.3 COMPLETE RESULTS IN THE SYNTHETIC EXPERIMENTS

The synthetic results show that selection outcomes depend on reward-function error: Plug-in becomes harmful at the largest tested error, whereas DR and IPW retain positive gains.

E.3 COMPLETE RESULTS IN THE SYNTHETIC EXPERIMENTS

  • At δ = 0.6, Plug-in selects Nmax and harms in every repetition, while DR and IPW retain positive gains with zero observed harm across tested δ values.Source: §E.3 · p. 28, Table 6 · p. 29
  • All estimator-based selection rules have zero observed harm through δ = 0.4 because Plug-in bias has not yet pushed its selected budget beyond the point where value falls below N = 1.This illustrates that a biased estimator can still select a safe budget.Source: §E.3 · p. 28
  • Table 6 reports policy-value gain and harm against N = 1 across reward-function error values, with score error fixed at γ = 0.65.Source: §E.3 · p. 28, Table 6 · p. 29

E.4 SELECTION ACROSS THE RANGE OF SCORE ERROR

The paper compares selection across score-error levels and extends BoN evaluation to pairwise preferences, specifying the objective, estimator construction, and conditions for sample-based density ratios.

E.4 SELECTION ACROSS THE RANGE OF SCORE ERROR

  • Across tested score errors, estimator-based rules maintain nonnegative mean gain, and DR has the lowest regret against the optimal budget.Naive BoN is optimal when the score is aligned but collapses once the score becomes exploitable.Source: §E.4 · p. 29, Figure 12 · p. 29

F EXTENSION TO PREFERENCE REWARDS

  • The preference-reward extension requires factorized logged comparisons, with the first behavior marginal supplying BoN candidates; otherwise the required ratio generally depends on the full joint response distribution.Source: F EXTENSION TO PREFERENCE REWARDS · p. 29, §F.3 · p. 32

F.1 PAIRWISE WIN-RATE OBJECTIVE

  • The pairwise win-rate objective is the probability that a BoN response beats a response from the reference distribution, and it does not require a Bradley–Terry model for identification.Identification requires the conditional preference regression to be identified on the relevant support.Source: §F.1 · pp. 30–31

F.2 DOUBLY ROBUST ESTIMATION

  • The preference-setting estimator has a plug-in component estimable by Monte Carlo using independent replicates, each with N candidate draws and an independent opponent draw.This is a direct Monte Carlo construction rather than the pooled estimator described in Section 4.2.Source: §F.2 · p. 31

F.3 BON DENSITY RATIOS

  • When the comparison policy factorizes, the BoN density ratio needed for debiasing can be estimated using samples from the reference model alone.The plug-in ratio estimate is generally biased at finite L; the passage identifies an unbiased alternative when M = L ≥ N − 1.Source: §F.3 · p. 32

Related papers

Loading 2610.09250v1…