Paper deep dive

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

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

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 114

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%

Last extracted: 10/8/2026, 7:24:35 AM

Summary

This paper proposes a sample-only framework for evaluating and selecting Best-of-N (BoN) policies in inference-time alignment without access to response likelihoods. The authors introduce BoN-DR, a doubly robust estimator that exploits the order-statistic structure of BoN to express density ratios via score-rank probabilities. They also derive two selection rules, Value Maximization and Safe Improvement, to determine the optimal sampling budget N while guarding against reward overoptimization.

Entities (7)

Best-of-N · method · 99%BoN-DR · method · 98%GSM8K · dataset · 97%Safe Improvement · selectionrule · 95%Value Maximization · selectionrule · 95%Reward Overoptimization · problem · 92%Off-Policy Evaluation · task · 90%

Relation Signals (6)

BoN-DR → isa → Doubly Robust Estimator

confidence 98% · We then develop a doubly robust estimator of the BoN policy value (BoN-DR)

BoN-DR → solves → Off-Policy Evaluation

confidence 95% · Evaluating BoN policies from logged data is challenging under sample-only access... We propose a sample-only framework... BoN-DR

Safe Improvement → provides → No-Harm Guarantee

confidence 94% · Safe Improvement... provides a no-harm guarantee relative to the reference policy with high probability.

BoN-DR → uses → Score-Rank Probabilities

confidence 93% · We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities

Larger Budgets → causes → Reward Overoptimization

confidence 92% · Since larger budgets can amplify errors in the score function and lead to reward overoptimization

Value Maximization → selects → Sampling Budget N

confidence 90% · (i) Value Maximization chooses the budget with the largest estimated policy value

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

110,402 characters extracted from source content.

Expand or collapse full text

Efficient Best-of-N policy evaluation for inference-time alignment Jonas Schweisthal Yuxin Wang Athiya Deviyani Stefan Feuerriegel Dennis Frauencorrespondence to: jonas.schweisthal@lmu.de, yuxin.wang1@lmu.de Abstract 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 (i) 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. †footnotetext: 1LMU Munich & MCML, 2Carnegie Mellon University, 3Meta (work in personal capacity). ∗Equal contribution. 1 Introduction In inference-time alignment, the aim is to improve the behavior of a given generative model using sampled outputs and an auxiliary reward or preference signal, but without updating or accessing the model parameters (Huang et al., 2025; Khalaf et al., 2025). This is relevant in practice, where one often interacts with a model through a restricted interface and cannot modify the underlying parameters. For example, many large companies want to adapt frontier LLMs with API-only access to their own preferences and needs (Kosmas et al., 2025), such as a car manufacturer using collected user feedback to improve a third-party in-car assistant. A widely used approach is Best-of-N (BoN) sampling (Nakano et al., 2021; Beirami et al., 2025), which has two steps: (1) for a prompt x, the reference model (e.g., the LLM) generates N candidate responses; and (2) a score function s (e.g., an externally pre-trained reward model or an LLM judge) selects the highest-scoring response (Nakano et al., 2021; Beirami et al., 2025). Importantly, BoN requires only samples and no modification of the reference model. However, deploying BoN in practice is subject to two challenges: Challenge 1: Evaluating BoN policies under sample-only access. Practitioners need to know whether and, in particular, how much a BoN policy actually improves the true downstream reward (and not only the score) over the reference model. From logged responses and rewards, this is an off-policy evaluation (OPE) problem. Yet, standard OPE estimators (e.g., importance-weighted and doubly robust estimators) are not applicable. The reason is that these estimators require the density ratio between the target policy and the policy that generated the logged data (Dudik et al., 2011). Under sample-only access, however, the probabilities assigned to complete responses, i.e., the response likelihoods, are unavailable. ⇒ We therefore need an estimator that evaluates BoN policies without evaluating the response likelihoods. Challenge 2: Selecting the sampling budget N. The sampling budget N controls how strongly BoN optimizes the score: a small N limits the potential benefit, while a large N concentrates the policy on low-probability, high-scoring responses. When the score function is an imperfect proxy for the downstream reward, this can amplify its errors and reduce downstream performance. This issue is often known as reward overoptimization (Gao et al., 2023; Coste et al., 2024). Figure 1 illustrates the issue on GSM8K: the score function of the selected response increases with N, while the downstream accuracy can peak and then decline. The score function alone therefore does not reveal which N should be deployed; instead, this requires estimating the policy value of each candidate budget. However, even unbiased value estimates are noisy in finite samples, especially for large N, where the BoN policy concentrates on responses that are rarely observed in the logged data. Directly maximizing them can thus lead to harmful budget choices. ⇒ We therefore need a selection rule that accounts for uncertainty when comparing candidate budgets and guards against harmful departures from the reference policy. Figure 1: The score function does not reveal the optimal inference-time budget. Best-of-N on GSM8K (Cobbe et al., 2021) for three reference models using OASST-RM-2.1 as the score model. Black solid: task accuracy computed from 512512 stored responses for each of the 1,3191,319 held-out test prompts. Magenta dashed: mean selected-response score (right axis). Grey dotted: reference-model accuracy (N=1N=1). Red circles mark the accuracy-optimal budget N⋆N . ⇒ Takeaway: The proxy score increases with N, but accuracy peaks and then falls, showing that the score function alone cannot determine the best sampling budget. In this paper, we address both challenges by developing a sample-only framework for evaluating BoN policies and selecting the inference-time sampling budget N. We proceed in two steps: 1 Estimation (→ Section 4): To develop an estimator, we exploit a statistical property of BoN: the underlying order-statistic structure makes the otherwise unavailable density ratio between the BoN policy and the reference model expressible through the probabilities that a fresh reference-model sample scores below or at a given response, which can be estimated from samples alone. Building on this, we construct a doubly robust estimator of the BoN policy value (called BoN-DR) without access to response likelihoods. Here, BoN-DR separates the score used to select responses from the reward estimator used to evaluate them. Further, it reuses a shared auxiliary sample pool across candidate budgets and is unbiased for any finite pool size. We show that our BoN-DR yields asymptotically valid inference even when the reward estimator is misspecified, and that it attains the efficiency of an exact-ratio DR estimator as the pool grows and the reward estimator is consistent. 2 Selecting N (→ Section 5): To select the sampling budget N, we develop two selection rules: (i) Value Maximization chooses the budget with the largest estimated policy value; and (i) Safe Improvement chooses the budget with the largest lower confidence bound (LCB) on the improvement over the reference policy, with a fallback to N=1N=1 if no LCB is positive. We show that both rules asymptotically attain the best policy value on the candidate grid, while Safe Improvement additionally provides an asymptotic no-harm guarantee relative to the reference policy with high probability. To compute the LCB, we further construct simultaneous confidence bounds across candidate budgets. Unlike pointwise intervals, these bounds account for searching over the candidate grid and remain asymptotically valid after N is selected from the same data. Our contributions are fourfold:11 1 Code available at: https://github.com/JSchweisthal/Efficient-BoN. (1) We develop BoN-DR, a novel, unbiased doubly robust estimator for evaluating BoN policies from logged data, which requires only sample access to the reference model. (2) We prove statistical guarantees for BoN-DR, including robustness to reward estimator misspecification, asymptotic normality, and efficiency. (3) We propose two principled selection rules for N (i.e., Value Maximization and Safe Improvement) with consistency and a no-harm guarantee. (4) We evaluate our methods in synthetic experiments and on GSM8K across multiple reference and score models. 2 Related work22 2 We provide an extended related work in Appendix A. BoN for inference-time alignment. BoN is widely used for inference-time alignment with reward or preference models (Stiennon et al., 2020; Nakano et al., 2021). Prior work studies the induced policy, its divergence to the reference policy, and the theoretical and empirical scaling behavior (Gui et al., 2024; Yang et al., 2024; Mroueh and Nitsure, 2025; Beirami et al., 2025; Sriraman and Block, 2026, e.g.,). Larger budgets can amplify proxy errors and cause reward overoptimization, motivating methods that modify the score, selection rule, or underlying model (Gao et al., 2023; Coste et al., 2024; Huang et al., 2025; Jinnai et al., 2025). We instead keep standard BoN fixed and study how to evaluate its downstream value and select its budget from logged data. Khalaf et al. (2025) consider a closely related problem, where they tune the BoN budget using proxy and true rewards of sampled responses. However, their method requires true rewards for all sampled candidates and does not provide uncertainty quantification. In contrast, we select N from logged data with only one observed reward per prompt and provide statistical guarantees. Off-policy evaluation (OPE). Classical OPE estimates a target policy’s value from data collected under a behavior policy using replay, importance weighting, or doubly robust estimation. (Li et al., 2011; Horvitz and Thompson, 1952; Strehl et al., 2010; Dudik et al., 2011). High-confidence OPE and safe policy improvement further use lower confidence bounds to guard against underperforming a baseline (Thomas et al., 2015b; Thomas et al., 2015a; Laroche et al., 2019). These methods cannot be directly applied to BoN under sample-only access because the required target-to-behavior density ratio depends on unavailable response likelihoods. We later exploit the order-statistic structure in BoN to express this ratio through score-rank probabilities, thereby enabling policy value estimation and uncertainty-aware budget selection from sampled responses and logged rewards. 3 Problem Setup We consider a context X∈X , an action A∈A , and a scalar reward Y∈Y . We call any (possibly stochastic) decision rule π mapping a context to an action a policy. We assume that the observed action A is generated by a behavior or reference policy πb(a∣x)=ℙ⁡(A=a|X=x) _b(a x)=P(A=a|X=x). For example, in the LLM setting, πb _b is induced by a reference model that generates a text A given a prompt X, based on which we obtain downstream signal Y (e.g., task success, human preference, click-through rate, etc.). We denote the reward function as μ(x,a)=[Y|X=x,A=a]μ(x,a)=E[Y|X=x,A=a], and we observe an i.i.d. logged dataset =(xi,ai,yi)i=1nD=\(x_i,a_i,y_i)\_i=1^n from the population Z=(X,A,Y)∼ℙZ=(X,A,Y) . Inference-time alignment. We assume that we can sample from πb(⋅∣x) _b(· x) for any context x, but can neither access the model weights nor evaluate the response likelihood πb(a∣x) _b(a x). This is typical for API-based models, which return sampled responses but no token-level probabilities. Our goal is to improve the deployed policy using only such samples and the logged data D. BoN policies. A well-established method for inference-time alignment is best-of-N sampling (BoN) (Nakano et al., 2021; Beirami et al., 2025). Here, a score function s⁡(x,a)s(x,a) first ranks actions a for each context x. For example, s⁡(x,a)s(x,a) could be an LLM judge (Zheng et al., 2023) or an estimator of the reward function μ⁡(x,a)μ(x,a). Then, for a fixed context xi∈x_i , BoN samples N i.i.d. actions ai1,…,aiN∼πb(⋅∣xi)a_i1,…,a_iN _b(· x_i) from the API and chooses the one with the largest score aN⋆,s(xi)∈arg⁡maxj≤N⁡s⁡(xi,ai,j)a ,s_N(x_i)∈ _j≤ Ns(x_i,a_i,j). The induced BoN policy is defined as πNs(a∣xi):=ℙ⁡(aN⋆,s(xi)=a∣X=xi). _N^s(a x_i):=P\! (a ,s_N(x_i)=a X=x_i ). In particular, π1s=πb _1^s= _b, whereas increasing N progressively concentrates the policy on actions receiving high scores under s. Policy evaluation. Our paper primarily focuses on the evaluation of the BoN policy πNs _N^s. For example, we might be interested in the performance of πNs _N^s for a specific N, or whether πNs _N^s for N>1N>1 improves over the base model πb _b. A principled way to evaluate a policy π is via its policy value V⁡(π)=⁡[∑a∈π⁡(a∣X)μ(X,a)]V(π)=E\! [ _a π(a X)μ(X,a) ], which quantifies the expected reward under policy π (Kallus, 2018). The choice of N. Evaluating V⁡(πNs)V( _N^s) is directly tied to the choice of N, which controls how far πNs _N^s departs from πb _b: a small N yields only marginal gains, while a large N concentrates the policy on high-scoring actions that are rare under πb _b and thus weakly represented in D. As a result, errors in the score function can be amplified, which can lead to reward overoptimization (Gao et al., 2023). In this paper, we address two core challenges: 1 Off-policy evaluation (→ Section 4): How can we efficiently estimate the value V⁡(πNs)V( _N^s) of a BoN policy from data D generated by πb _b when the reference model can only be sampled?2 Selecting N (→ Section 5): How can we use these estimates to select the sampling budget N with statistical guarantees? 4 Efficient Off-Policy Evaluation for BoN In this section, we develop an estimator for the value of the BoN policy V⁡(πNs)V( _N^s). A natural starting point is the doubly robust (DR) estimator, which is widely used for off-policy evaluation due to its favorable statistical properties (Robins et al., 1994; Dudik et al., 2011). For a fixed BoN policy πNs _N^s, the DR estimator is V^DR(πNs)=1n∑i=1nψN(zi),ψN(zi)=∑a∈πNs(a∣xi)μ^(xi,a)+πNs(ai∣xi)πb(ai∣xi)(yi−μ^(xi,ai)), V_DR( _N^s)= 1n _i=1^n _N(z_i), _N(z_i)= _a [rgb]0.043,0.2383,0.5703 _N^s(a x_i) μ(x_i,a)+ [rgb]0.332,0.1328,0.5352 _N^s(a_i x_i) _b(a_i x_i) (y_i- μ(x_i,a_i) ), -5.69046pt (1) where zi=(xi,ai,yi)z_i=(x_i,a_i,y_i) and μ μ is an estimator of the reward function μ. The plug-in term (first term in the sum) evaluates the target policy under the estimated reward function, while the correction term (second term) uses the observed outcome to correct for errors in the estimated reward function, weighted by the density ratio between the BoN and behavior policies. Why the standard DR estimator is not applicable. Direct application of the DR estimator in the form of (1) is not possible in the inference-time alignment setting due to two main challenges: (i) both terms require knowledge of πNs(a∣xi) _N^s(a x_i), but the induced BoN probabilities are not available from a black-box sampler. Attempting to estimate πNs(a∣xi) _N^s(a x_i) from the data is extremely challenging in the enormous and sparse text action space A. (i) The correction term requires the density ratio wN(x,a):=πNs(a∣x)πb(a∣x)w_N(x,a):= _N^s(a x) _b(a x). Because the action space A consists of high-dimensional text sequences, individual sequence probabilities can be extremely small, and density-ratio estimation can suffer from high variance and numerical instability. To address this, we first establish an alternative representation of the DR score for the inference-time alignment setting (Section 4.1). We then construct a pooled estimator that reuses auxiliary samples across candidate budgets (Section 4.2) and establish theoretical guarantees (Section 4.3). 4.1 Inference-time DR score Our key observation is that the target policy is not arbitrary: πNs _N^s is obtained by applying a known Best-of-N selection rule to samples from πb _b. We can therefore exploit two pieces of structure jointly: (i) although πb _b cannot be evaluated, we can sample from πb(⋅∣x) _b(· x) at inference time, and (i) the construction of the BoN policy imposes a particular relationship between πNs _N^s and πb _b. In the following, we show that DR score admits a specific representation only in terms of one-dimensional score ranks under the behavior policy. For fixed x and action a, we define the strict and weak cumulative density functions (CDFs) of the score via Fx−(a)=ℙA∼πb(⋅∣x)(s(x,A)<s(x,a)) and Fx(a)=ℙA∼πb(⋅∣x)(s(x,A)≤s(x,a)).F_x^-(a)=P_A _b(· x) (s(x,A)<s(x,a) ) and F_x(a)=P_A _b(· x) (s(x,A)≤ s(x,a) ). -8.5359pt (2) Thus, Fx−(a)F_x^-(a) and Fx(a)F_x(a) describe the rank of a according to the score s among actions sampled from the behavior policy. Importantly, both quantities are probabilities of simple comparison events and can therefore be estimated using samples from πb(⋅∣x) _b(· x) without evaluating any sequence likelihoods. The following proposition shows that these rank probabilities are sufficient to express the entire DR score for a BoN policy (which we call BoN-DR score). Proposition 4.1 (BoN-DR score). Suppose that distinct actions have distinct scores, i.e., s⁡(x,a)=s⁡(x,a′)⟹a=a′,s(x,a)=s(x,a ) a=a , for any a,a′∈a,a . Define gN(u,v)=∑ℓ=0N−1uN−1−ℓvℓg_N(u,v)= _ =0^N-1u^N-1- v . Then, for z=(x,a,y)z=(x,a,y) with πb(a∣x)>0 _b(a x)>0, the DR score for the BoN policy can be written as ψN(z)=A′∼πb(⋅∣x)[gN(Fx(A′),Fx−(A′))μ^(x,A′)]+gN(Fx(a),Fx−(a))(y−μ^(x,a)). _N(z)=E_A _b(· x) [g_N\! (F_x(A ),F_x^-(A ) ) μ(x,A ) ]+g_N\! (F_x(a),F_x^-(a) ) (y- μ(x,a) ). (3) Proof. This follows by combining the BoN order-statistic identity in Beirami et al. (2025) with the DR score formula in Eq. (1). We refer to Appendix B for details. ∎ Proposition 4.1 resolves the two computational obstacles that we identified above: (i) it eliminates the need to evaluate either πb(a∣x) _b(a x) or πNs(a∣x) _N^s(a x); and (i) the density ratio is replaced by gN(Fx(a),Fx−(a))g_N(F_x(a),F_x^-(a)), which depends only on the relative rank of a under the score distribution induced by the behavior policy. Consequently, apart from evaluating the score function s and outcome model μ μ, every quantity in Eq. (3) can be approximated using only samples from the behavior policy. In particular, Fx(a)F_x(a) and Fx−(a)F_x^-(a) are expectations of bounded indicator variables, e.g., Fx(a)=A′∼πb(⋅∣x)[s(x,A′)≤s(x,a)]F_x(a)=E_A _b(· x) [1\s(x,A )≤ s(x,a)\ ], thus turning the original high-dimensional density-ratio evaluation problem into the estimation of simple rank probabilities. The remaining challenge is therefore how we should estimate the expectations and score-rank functionals in Eq. (3) given a finite number of auxiliary samples from πb(⋅∣x) _b(· x). In the next section, we show that their particular polynomial structure admits natural unbiased U-statistic estimators. 4.2 Pooled BoN-DR estimator We now construct an estimator of the DR score in Eq. (1) using a finite, reusable pool of samples from the behavior policy. Proposition 4.1 shows that the DR score can be estimated using only samples from the behavior policy. A direct Monte Carlo implementation of Eq. (3) could draw fresh samples from the behavior policy each time an expectation or score rank needs to be estimated, and repeat this procedure separately for every candidate value of N. For generative models, however, sampling may be computationally costly. Instead, we propose to draw a single reusable pool of samples for each context and use it to estimate both components of the DR score (i.e., the plug-in term and the correction term), as well as the values of other BoN policies with different N. For each context xix_i, we draw one pool of behavior-policy samples a~i=(a~i1,…,a~iM)∼iidπb(⋅∣xi) a_i=( a_i1,…, a_iM) iid _b(· x_i), where M is a user-chosen computational budget, and let us denote a¯i=(ai,a~i1,…,a~iM)∈M+1 a_i=(a_i, a_i1,…, a_iM) ^M+1 the vector of Monte Carlo samples and behavior actions. To derive our BoN-DR estimator, we leverage U-statistics (van der Vaart, 1998), which estimate a quantity defined as an expectation over r i.i.d. draws via a single larger pool of M draws. The basic idea is to estimate the quantity by averaging the same quantity over all size-r subsets of the pool. Each subset has the correct distribution, so the resulting estimator is unbiased while reusing all available samples. Below, we apply this construction separately to (i) the plug-in term and (i) correction term of the DR score and then combine the two into our pooled BoN-DR estimator. Estimator for the plug-in term. By Proposition 4.1, the plug-in term can be written as vNs(xi)=A∼πNs(⋅∣xi)[μ^(xi,A)]=[μ^(xi,AN⋆,s)∣Xi=xi],v_N^s(x_i)=E_A _N^s(· x_i) [ μ(x_i,A) ]=E [ μ(x_i,A_N ,s) X_i=x_i ], (4) where AN⋆,sA_N ,s is the action selected from N i.i.d. draws from πb(⋅∣xi) _b(· x_i) according to the score s. Since a¯i a_i contains M+1M+1 such draws, we estimate vi,Nsv_i,N^s by averaging the fitted reward of the BoN winner over all size-N subsets: v^i,Ns,M+1=(M+1N)−1∑J⊆0,…,M,|J|=Nμ^(xi,a¯i,J⋆,s). v_i,N^s,M+1= M+1N^-1 _ subarraycJ \0,…,M\,|J|=N subarray μ (x_i, a_i,J ,s ). -2.84544pt (5) This estimator can be evaluated without enumerating all subsets. Let iG_i index the unique actions appearing in a¯i a_i, and let a¯ig a_ig denote the corresponding action. We define Lig=∑m=0Ms(xi,a¯im)<s(xi,a¯ig) and Eig=∑m=0Ms(xi,a¯im)≤s(xi,a¯ig).L_ig= _m=0^M1 \s(x_i, a_im)<s(x_i, a_ig) \ and E_ig= _m=0^M1 \s(x_i, a_im)≤ s(x_i, a_ig) \. (6) Then, an alternative estimator is v^i,Ns,M+1(xi,a¯i)=∑g∈iμ^(xi,a¯ig)(EigN)−(LigN)(M+1N). [rgb]0.043,0.2383,0.5703 v_i,N^s,M+1(x_i, a_i)= _g _i μ(x_i, a_ig) E_igN- L_igN M+1N. -2.84544pt (7) Indeed, the numerator counts exactly the size-N subsets for which a¯ig a_ig is the highest-scoring action. We use the convention (uN)=0 uN=0 for u<Nu<N. Estimator for the correction term. For the correction term, we treat the logged action aia_i as fixed and use the M auxiliary samples to estimate wNs(xi,ai)=gN(Fxi(ai),Fxi−(ai))w_N^s(x_i,a_i)=g_N(F_x_i(a_i),F_x_i^-(a_i)). We define Li=∑m=1Ms(xi,a~im)<s(xi,ai), and Ei=∑m=1Ms(xi,a~im)≤s(xi,ai).L_i=Σ _m=1^M1 \s(x_i, a_im)<s(x_i,a_i) \, and E_i=Σ _m=1^M1 \s(x_i, a_im)≤ s(x_i,a_i) \. -2.84544pt (8) Under a no-score-ties assumption, Ei−LiE_i-L_i counts the number of auxiliary draws equal to aia_i. By averaging over all size-(N−1)(N-1) subsets of the auxiliary pool, we yield the estimator w^i,Ns,M(xi,a¯i)=N∑t=0min⁡Ei−Li,N−11t+1(Ei−Lit)(LiN−1−t)(MN−1). [rgb]0.332,0.1328,0.5352 w_i,N^s,M(x_i, a_i)=N _t=0 \E_i-L_i,N-1\ 1t+1 E_i-L_it L_iN-1-t MN-1. -2.84544pt (9) Here, t denotes the number of additional copies of aia_i among the N−1N-1 sampled competitors, while the factor 1/(t+1)1/(t+1) accounts for the t+1t+1 identical occurrences of the winning action. Pooled BoN-DR estimator. We define our pooled BoN-DR estimator as ψNM(zi,a~i) _N^M(z_i, a_i) =v^i,Ns,M+1(xi,a¯i)+w^i,Ns,M(xi,a¯i)(yi−μ^(xi,ai)), = [rgb]0.043,0.2383,0.5703 v_i,N^s,M+1(x_i, a_i)+ [rgb]0.332,0.1328,0.5352 w_i,N^s,M(x_i, a_i) (y_i- μ(x_i,a_i) ), (10) V^DRM(πNs) V_DR^M( _N^s) =1n∑i=1nψNM(zi,a~i). = 1n _i=1^n _N^M(z_i, a_i). -5.69046pt (11) Thus, a single pool of M additional generations per context is sufficient to estimate both components of the DR score. Moreover, the same pool can be reused across different values of N, which is particularly important for the policy-selection problem considered in the following section. 4.3 Theoretical guarantees We now establish asymptotic guarantees for our pooled BoN-DR estimator, including valid inference and efficiency. For this, we assume that s and μ μ are constructed independently of D (e.g., external models or a sample split), together with standard sampling and moment conditions (Assumption B.1). Theorem 4.2 (Validity and efficiency of the pooled BoN-DR estimator). Fix N and condition on the training sample used to construct s and μ μ. (a) Finite-M validity. For any fixed M≥N−1M≥ N-1, n(V^DRM(πNs)−V⁡(πNs))↝⁡(0,σN,M2) n ( V_DR^M( _N^s)-V( _N^s) ) (0, _N,M^2), where σN,M2=Var⁡(ψNM(Z,A~)) _N,M^2=Var ( _N^M(Z, A) ). This result does not require μ μ to be a consistent estimator of μ. (b) Infinite-M efficiency. Suppose additionally that M=Mn→∞M=M_n→∞ and that the reward function estimator μ μ is consistent for the true reward function μ in L2L_2. Then n(V^DRMn(πNs)−V⁡(πNs))↝⁡(0,σN,eff2) n ( V_DR^M_n( _N^s)-V( _N^s) ) (0, _N,eff^2), where σN,eff2 _N,eff^2 is the variance of the efficient influence function ϕNeff(Z)=∑a∈πNs(a∣X)μ(X,a)+wNs(X,A)(Y−μ⁡(X,A))−V⁡(πNs) _N^eff(Z)= _a _N^s(a X)μ(X,a)+w_N^s(X,A) (Y-μ(X,A) )-V( _N^s). Thus, conditional on the learned policy and behavior sampler, the proposed estimator attains the same first-order efficiency bound as an oracle DR estimator with access to the exact BoN density ratio. See Appendix B for the proof. Part (a) is particularly important for inference-time alignment. Valid inference does not require the reward estimator to approximate the true conditional mean. For example, s and μ μ may be given by an LLM judge that is useful for ranking responses but is not a statistically consistent model of [Y∣X,A]E[Y X,A]. The DR correction still yields a consistent, root-n estimator of the value of the resulting BoN policy. Part (b) adds that, if μ μ is additionally consistent, the BoN-DR estimator attains the corresponding first-order efficiency bound. We next clarify how the auxiliary sampling budget M affects the estimator. Because the pooled estimators are unbiased for every finite M, increasing M removes Monte Carlo variance rather than a first-order bias. For fixed N, under the boundedness conditions above, it is sufficient that Mn→∞M_n→∞; no particular rate of growth relative to n is required. 5 Selecting the optimal sampling budget N for BoN Our goal is now to select the optimal sampling budget NjN_j from a candidate grid =N1,…,NJN=\N_1,…,N_J\. In the following, we introduce two selection rules: (i) Value Maximization, which selects the budget with the largest estimated policy value, and (i) Safe Improvement, which selects the budget with the largest lower confidence bound (LCB) on improvement over the reference policy and falls back to N=1N=1 when no positive improvement is supported by the data. The latter thus guarantees improvement over the base model with high probability. 5.1 Value Maximization Value Maximization selects the budget with the largest estimated policy value: N^value∈arg⁡maxN∈V^DRM(πNs). N_value∈ _N V_DR^M( _N^s). -2.84544pt (12) The following corollary shows that, over a fixed candidate grid, this rule asymptotically recovers the best policy value in the class. Corollary 5.1 (Oracle consistency of Value Maximization). Suppose that the conditions of Theorem 4.2(a) hold uniformly over the finite candidate grid N. Then, conditional on the training sample, V⁡(πN^values)⟶maxN∈⁡V⁡(πNs)V( _ N_value^s) p _N V( _N^s). The proof is in Appendix B. Importantly, this conclusion inherits the robustness of the BoN-DR estimator: it does not require μ μ to consistently estimate the true reward function. However, the result is an oracle optimality guarantee, and, in finite samples, estimation noise can still cause N^value N_value to select a policy for which the value is below V⁡(πb)V( _b). This motivates our selection rule for safe improvement next. 5.2 Safe Improvement To obtain a no-harm guarantee relative to the behavior policy, we now formulate the selection rule directly in terms of improvement over the behavior policy. To do so, we define ΔN:=V⁡(πNs)−V⁡(π1s)=V⁡(πNs)−V⁡(πb) _N:=V( _N^s)-V( _1^s)=V( _N^s)-V( _b) -2.84544pt (13) for each N∈∖1N \1\. Safe Improvement then selects a candidate N>1N>1 only when its simultaneous lower confidence bound for ΔN _N is positive; otherwise, we fall back to N=1N=1. We use simultaneous rather than pointwise bounds because N is selected adaptively from the same candidate grid. ∙ To construct the LCB, we estimate each candidate policy’s improvement over the reference policy and its sampling variability. To do so, for each N∈∖1N \1\, we define the doubly robust improvement score Di,NM:=ψNM(zi,a~i)−ψ1M(zi,a~i)D_i,N^M:= _N^M(z_i, a_i)- _1^M(z_i, a_i), and the corresponding estimator Δ^NM:=1n∑i=1nDi,NM=V^DRM(πNs)−V^DRM(π1s) _N^M:= 1n _i=1^nD_i,N^M= V_DR^M( _N^s)- V_DR^M( _1^s). The corresponding variance is estimated by τ^N,M2:=1n∑i=1n(Di,NM−Δ^NM)2 τ_N,M^2:= 1n _i=1^n (D_i,N^M- _N^M )^2. ∙ To obtain simultaneous LCBs across candidate budgets, we need to account for the dependence induced by reusing the same evaluation data and auxiliary samples pools across all N∈N . We do so by using a joint multiplier bootstrap (Chernozhukov et al., 2013). Conditional on the sample, we thus draw independent multipliers ξi _i satisfying ⁡[ξi]=0E[ _i]=0 and ⁡[ξi2]=1E[ _i^2]=1, such as standard Gaussian variables. Formally, we define TΔ∗,+:=maxN∈∖1⁡n−1/2∑i=1nξi(Di,NM−Δ^NM)τ^N,M.T_ ^*,+:= _N \1\ n^-1/2 _i=1^n _i (D_i,N^M- _N^M ) τ_N,M. -5.69046pt (14) Let c^1−αΔ,+ c_1-α ,+ denote the conditional (1−α)(1-α)-quantile of TΔ∗,+T_ ^*,+. Thus, simultaneous LCB is given by LCB^Δ(N):=Δ^NM−c^1−αΔ,+τ^N,Mn,N∈∖1. LCB_ (N):= _N^M- c_1-α ,+ τ_N,M n, N \1\. -8.5359pt (15) Safe Improvement selects the candidate with the strongest LCB on improvement over the reference policy and falls back to N=1N=1 when no candidate has a positive LCB: N^LCB:=arg⁡maxN∈∖1LCB^Δ(N),maxN∈∖1⁡LCB^Δ(N)>0,1,otherwise. N_LCB:= cases _N \1\ LCB_ (N),& _N \1\ LCB_ (N)>0,\\[6.99997pt] 1,&otherwise. cases (16) Theorem 5.2 (Safe Improvement (“no-harm guarantee”)). Suppose that the conditions of Theorem 4.2(a) hold uniformly over the finite candidate grid N and that the variances τN,M2 _N,M^2 are uniformly bounded away from zero. Conditional on the training sample, it follows that V⁡(πN^LCBs)⟶maxN∈⁡V⁡(πNs)V( _ N_LCB^s) p _N V( _N^s) and ℙ⁡(V⁡(πN^LCBs)≥V⁡(πb))≥1−α−o⁡(1)P (V( _ N_LCB^s)≥ V( _b) )≥ 1-α-o(1). Proof in Appendix B. Theorem 5.2 formalizes the no-harm property of the Safe Improvement selection rule. A candidate N>1N>1 is selected only when the improvement over the behavior policy is supported by the simultaneous LCB; otherwise, the rule defaults to N=1N=1. The guarantee combines asymptotic no-harm with consistency; i.e., as the sample size grows, the conservatism induced by the LCB vanishes, and Safe Improvement recovers the best policy value over the fixed candidate grid. In finite samples, Safe Improvement may select smaller budgets than Value Maximization because it explicitly accounts for estimation uncertainty. 6 Experiments The purpose of our experiments is primarily to verify our theoretical properties. RQ1 We use synthetic experiments to test whether our BoN-DR estimator remains robust to reward estimator misspecification while benefiting from informative reward predictions. RQ2 We assess whether the estimators accurately recover BoN policy values across different reference models and score function regimes in realistic LLM settings. RQ3 We test whether Safe Improvement reduces harmful choices of N under reward overoptimization and thus leads to safe inference-time budget selection. Settings. We consider two settings: (1) Synthetic experiments with known ground truth, following standard practice in the OPE literature (Dudik et al., 2011; Saito and Joachims, 2022). Here, the score function errors and reward estimator errors can be varied independently through parameters γ (which increases the scores of rarely sampled, low-quality actions and thereby changes the induced BoN policy) and δ (which introduces errors in the predicted rewards without changing the induced policy). Appendix C.1 provides details. (2) Realistic LLM evaluation setting using GSM8K (Cobbe et al., 2021), with three reference models (i.e., Gemma-2-2B-IT (Team et al., 2024), Llama-3.2-3B-Instruct (Grattafiori et al., 2024), and Qwen3.5-4B) and two external reward models as score functions (i.e., OASST-RM-2.1-Pythia-1.4B (Köpf et al., 2023) and Skywork-Reward-V2-Qwen3-1.7B). Details are in Appendix C.2. The true reward is the exact-match correctness (see Appendix C.5). Each prompt has a stored pool of 512512 responses. In each evaluation, one response is treated as the logged observation where the reward is revealed, while the remaining responses form the auxiliary pool (see Appendix D.3). Baselines.44 4 Additional details on the BoN-IPW and plug-in estimators are provided in Appendix C.3. To our knowledge, there are no existing baselines that directly address OPE estimation for BoN policies from logged data. Instead, we compare three estimators based on Eq. (11): (i) Plug-in averages predictions of reward estimator under the target policy; (i) BoN-IPW weights logged rewards using estimated rank probabilities; and (i) BoN-DR uses an additional doubly robust correction. All estimators use the same logged data and auxiliary samples. For selection, we use the rules from Section 5; i.e., Value Maximization and Safe Improvement. Performance metrics. We measure bias, RMSE, interval width, and coverage of nominal 95%95\% pointwise confidence intervals. Selection is assessed by mean gain over N=1N=1 and harm rate, the fraction of repetitions with negative gain. Figure 2: Robust to reward estimator misspecification. Estimated BoN policy value at N=256N=256. We fix γ=0.65γ=0.65 and vary δ from 0 to 0.6 to increase the reward estimator error. Shown: (a) Absolute bias of policy value estimation. (b) Empirical coverage of the nominal 95%95\% pointwise CI, the dotted line shows the nominal level. (c) Gain of the budget selected by Safe Improvement, where the dotted line indicates no improvement over N=1N=1. N Estimator |Bias| CI width Coverage 8 Plug-in 0.049 0.003 0.000 BoN-IPW 0.002 0.097 0.940 BoN-DR 0.001 0.052 0.947 256 Plug-in 0.369 0.004 0.000 BoN-IPW 0.002 0.377 0.887 BoN-DR 0.003 0.455 0.940 * CI width and empirical coverage are computed for nominal 95%95\% pointwise CIs. Table 1: Sensitivity to sampling budget N. Here: γ=0.65γ=0.65, δ=0.4δ=0.4. Bold shows the lowest absolute bias and the coverage closest to 95%95\% for each N. RQ1 Robustness to reward estimator misspecification. We evaluate robustness to reward estimator misspecification by varying δ, which introduces errors in the reward estimator without changing the induced policy. We compare Plug-in, BoN-IPW, and BoN-DR in terms of absolute bias, CI coverage, and policy value gain over N=1N=1. Results are in Figure 2. Plug-in becomes biased as the errors in the reward prediction are increased. In contrast, BoN-DR and BoN-IPW remain nearly unbiased as δ increases. Further, they maintain CI coverage close to the nominal 95% level across the considered levels of misspecification. ⇒ As suggested by our theory, BoN-DR remains robust to reward model misspecification while supporting valid CIs. We next examine whether these results persist across different BoN budgets by comparing N=8N=8 and N=256N=256 in Table 1. ⇒ The results again show that the benefits of BoN-DR are robust. In Appendix D.2–D.3, we provide additional sensitivity analyses on the size of the validation set and the Monte Carlo pool. We study how the amount of validation data affects downstream policy value estimation and budget selection, and show that increasing the Monte Carlo pool reduces the additional Monte Carlo variance of BoN-DR and brings it closer to the efficiency bound under a correctly specified reward estimator. Figure 3: BoN policy value estimation for realistic LLM setting on GSM8K. Rows are external reward models used as score functions, and columns are reference models. Black dashed: oracle benchmark policy value. Lines: mean estimated policy value across repetitions. Shaded: 80%80\% pointwise CI. Plug-in CIs are not faithful wrt. nominal coverage and thus omitted. RQ2 Performance in recovering BoN policy values in realistic LLM settings. Figure 3 compares the estimated policy values from Plug-in, BoN-IPW, and BoN-DR with the oracle policy values under different configurations. BoN-DR shows the most accurate estimates. Moreover, at N=256N=256, BoN-DR yields substantially narrower CIs, with BoN-IPW intervals being 1.71.7–5.5×5.5× wider. Notably, the Plug-in estimator remains biased even though the score function ranks responses accurately in the Skywork setting. This illustrates that effective ranking does not necessarily translate into accurate policy value estimation. ⇒ BoN-DR accurately recovers BoN policy values in real-world settings while providing substantially more precise estimates than BoN-IPW. We provide additional results for CI coverage, error decomposition, overlap at large budgets, and robustness to alternative reward predictors in Appendices D.4–D.7. RQ3 Safe inference-time budget selection (“no-harm guarantee”). We study whether Safe Improvement, which explicitly accounts for estimation uncertainty, helps avoid harmful choices of N, i.e., budgets that reduce policy value relative to the reference policy. This is particularly important under reward overoptimization with a strong reference model, where larger budgets achieve higher scores but can lower downstream performance. For comparison, we also report a Naïve approach here (which chooses the response with the highest score at a fixed budget). Figure 4: Comparison of budget selection rules for Qwen3.5-4B with OASST-RM-2.1. Here, the harm rate is defined as the fraction of evaluations with negative gain relative to N=1N=1. Lower is better. Plug-in uses Value Maximization, and Naïve BoN selects Nmax=256N_ =256. We have two main findings (see Figure 4). First, both Naïve BoN and Plug-in perform poorly overall and often lead to harmful selections. In contrast, our proposed selection rules (Value Maximization and Safe Improvement) are substantially better. Second, Safe Improvement leads to fewer harmful selections than Value Maximization. Appendix E reports detailed results across various configurations. ⇒ Thanks to the uncertainty-aware approach, Safe Improvement can reduce harmful selections compared to Value Maximization, which is in line with our no-harm guarantee. Conclusion. We present, to our knowledge, the first framework for evaluating and selecting BoN policies under sample-only access, with valid inference and a no-harm guarantee. As a limitation, it requires logged data and loses precision at large budgets. Future work could use our per-prompt scores to learn prompt-specific budgets and extend likelihood-free evaluation to other inference-time methods built on black-box models. References Aminian et al. (2026) G. Aminian, I. Shenfeld, A. R. Asadi, A. Beirami, and Y. Mroueh Best-of-n through the smoothing lens: kl divergence and regret analysis. In International Conference on Learning Representations, Vol. 2026, p. 105057–105090. Cited by: Appendix A. Beirami et al. (2025) A. Beirami, A. Agarwal, J. Berant, A. D’Amour, J. Eisenstein, C. Nagpal, and A. T. Suresh Theoretical guarantees on the best-of-n alignment policy. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 3580–3602. Cited by: Appendix A, §1, §2, §3, §4.1. Bhargava et al. (2024) A. Bhargava, L. Jain, B. Kveton, G. Liu, and S. Mukherjee Off-policy evaluation from logged human feedback. arXiv preprint arXiv:2406.10030. Cited by: Appendix A. Brown et al. (2024) B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Ré, and A. Mirhoseini Large language monkeys: scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787. Cited by: Appendix A. Chen et al. (2021) M. Chen, J. Tworek, H. Jun, Q. Yuan, H. P. D. O. Pinto, J. Kaplan, H. Edwards, Y. Burda, N. Joseph, G. Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374. Cited by: Appendix A. Chernozhukov et al. (2013) V. Chernozhukov, D. Chetverikov, and K. Kato Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. The Annals of Statistics, p. 2786–2819. Cited by: §5.2. Chow et al. (2025) Y. Chow, G. Tennenholtz, I. Gur, V. Zhuang, B. Dai, A. Kumar, R. Agarwal, S. Thiagarajan, C. Boutilier, and A. Faust Inference-aware fine-tuning for best-of-n sampling in large language models. In International Conference on Learning Representations, Vol. 2025, p. 78936–78959. Cited by: Appendix A. Cobbe et al. (2021) K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: Figure 1, §6. Coste et al. (2024) T. Coste, U. Anwar, R. Kirk, and D. Krueger Reward model ensembles help mitigate overoptimization. In International Conference on Learning Representations, Vol. 2024, p. 50905–50931. Cited by: Appendix A, §1, §2. Dudik et al. (2011) M. Dudik, J. Langford, and L. Li Doubly robust policy evaluation and learning. In ICML, Cited by: Appendix A, §1, §2, §4, §6. Frauen et al. (2026) D. Frauen, A. Deviyani, M. van der Schaar, and S. Feuerriegel Nonparametric llm evaluation from preference data. In International Conference on Machine Learning, Cited by: Appendix A. Gao et al. (2023) L. Gao, J. Schulman, and J. Hilton Scaling laws for reward model overoptimization. In International Conference on Machine Learning, p. 10835–10866. Cited by: §1, §2, §3. Grattafiori et al. (2024) A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §6. Gui et al. (2024) L. Gui, C. Gârbacea, and V. Veitch Bonbon alignment for large language models and the sweetness of best-of-n sampling. Advances in Neural Information Processing Systems 37, p. 2851–2885. Cited by: Appendix A, Appendix A, §2. Hatt et al. (2022) T. Hatt, D. Tschernutter, and S. Feuerriegel Generalizing off-policy learning under sample selection bias. In UAI, Cited by: Appendix A. Hess et al. (2026) K. Hess, D. Frauen, V. Melnychuk, and S. Feuerriegel Efficient and sharp off-policy learning under unobserved confounding. In International Conference on Learning Representations, Vol. 2026, p. 57552–57587. Cited by: Appendix A. Horvitz and Thompson (1952) D. G. Horvitz and D. J. Thompson A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association 47 (260), p. 663–685. Cited by: Appendix A, §2. Huang et al. (2025) A. Huang, A. Block, Q. Liu, N. Jiang, A. Krishnamurthy, and D. J. Foster Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment. In International Conference on Machine Learning, p. 25075–25126. Cited by: Appendix A, Appendix A, §1, §2. Jin et al. (2025) Y. Jin, Z. Ren, Z. Yang, and Z. Wang Policy learning “without” overlap: pessimism and generalized empirical bernstein’s inequality. The Annals of Statistics 53 (4), p. 1483–1512. Cited by: Appendix A. Jinnai et al. (2025) Y. Jinnai, T. Morimura, K. Ariu, and K. Abe Regularized best-of-n sampling with minimum bayes risk objective for language model alignment. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 9321–9347. Cited by: Appendix A, §2. Kallus and Uehara (2020) N. Kallus and M. Uehara Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research 21, p. 1–63. Cited by: Appendix A. Kallus (2018) N. Kallus Balanced policy evaluation and learning. In NeurIPS, Cited by: Appendix A, §3. Kallus (2021) N. Kallus More efficient policy learning via optimal retargeting. Journal of the American Statistical Association 116 (534), p. 646–658. External Links: Document Cited by: Appendix A. Karampatziakis et al. (2021) N. Karampatziakis, P. Mineiro, and A. Ramdas Off-policy confidence sequences. In International Conference on Machine Learning, p. 5301–5310. Cited by: Appendix A. Khalaf et al. (2025) H. Khalaf, C. M. Verdun, A. Oesterling, H. Lakkaraju, and F. Calmon Inference-time reward hacking in large language models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, Cited by: Appendix A, §1, §2. Köpf et al. (2023) A. Köpf, Y. Kilcher, D. Von Rütte, S. Anagnostidis, Z. R. Tam, K. Stevens, A. Barhoum, D. Nguyen, O. Stanley, R. Nagyfi, et al. Openassistant conversations-democratizing large language model alignment. Advances in neural information processing systems 36, p. 47669–47681. Cited by: §6. Kosmas et al. (2025) M. Kosmas, A. Mayer, S. Feuerriegel, and F. Bodendorf From code to culture: aligning large language models with corporate values. Available at SSRN 5615933. Cited by: §1. Kuzborskij et al. (2021) I. Kuzborskij, C. Vernade, A. Gyorgy, and C. Szepesvári Confident off-policy evaluation and selection through self-normalized importance weighting. In International Conference on Artificial Intelligence and Statistics, p. 640–648. Cited by: Appendix A. Laroche et al. (2019) R. Laroche, P. Trichelair, and R. T. Des Combes Safe policy improvement with baseline bootstrapping. In International conference on machine learning, p. 3652–3661. Cited by: Appendix A, §2. Li et al. (2011) L. Li, W. Chu, J. Langford, and X. Wang Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, p. 297–306. Cited by: Appendix A, §2. Li et al. (2024) Z. Li, X. Ji, M. Chen, and M. Wang Policy evaluation for reinforcement learning from human feedback: a sample complexity analysis. In International Conference on Artificial Intelligence and Statistics, p. 2737–2745. Cited by: Appendix A. Mroueh and Nitsure (2025) Y. Mroueh and A. Nitsure Information theoretic guarantees for policy alignment in large language models. Transactions on Machine Learning Research. Cited by: Appendix A, §2. Nakano et al. (2021) R. Nakano, J. Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, et al. Webgpt: browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332. Cited by: §1, §2, §3. Narita et al. (2019) Y. Narita, S. Yasui, and K. Yata Efficient counterfactual learning from bandit feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33(01), p. 4634–4641. Cited by: Appendix A. Raman et al. (2025) V. Raman, H. Asi, and S. Kale AdaBoN: adaptive best-of-n alignment. arXiv preprint arXiv:2505.12050. Cited by: Appendix A. Robins et al. (1994) J. M. Robins, A. Rotnitzky, and L. P. Zhao Estimation of regression coefficients when some regressors are not always observed. Journal of the American Statistical Association 89 (427), p. 846–866. Cited by: §4. Ryu et al. (2025) J. J. Ryu, J. Kwon, B. Koppe, and K. Jun Improved offline contextual bandits with second-order bounds: betting and freezing. arXiv preprint arXiv:2502.10826. Cited by: Appendix A. Saito and Joachims (2022) Y. Saito and T. Joachims Off-policy evaluation for large action spaces via embeddings. In International Conference on Machine Learning (ICML), Cited by: Appendix A, §6. Schweisthal et al. (2023) J. Schweisthal, D. Frauen, V. Melnychuk, and S. Feuerriegel Reliable off-policy learning for dosage combinations. In NeurIPS, Cited by: Appendix A. Sessa et al. (2025) P. G. Sessa, R. Dadashi, L. Hussenot-Desenonges, J. Ferret, N. Vieillard, A. Ramé, B. Shahriari, S. Perrin, A. Friesen, G. Cideron, et al. Bond: aligning llms with best-of-n distillation. In International Conference on Learning Representations, Vol. 2025, p. 59040–59060. Cited by: Appendix A. Snell et al. (2024) C. Snell, J. Lee, K. Xu, and A. Kumar Scaling llm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314. Cited by: Appendix A. Sriraman and Block (2026) V. Sriraman and A. Block Revisiting the (sub) optimality of best-of-n for inference-time alignment. arXiv preprint arXiv:2603.05739. Cited by: Appendix A, §2. Stiennon et al. (2020) N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano Learning to summarize with human feedback. Advances in neural information processing systems 33, p. 3008–3021. Cited by: §2. Strehl et al. (2010) A. Strehl, J. Langford, L. Li, and S. M. Kakade Learning from logged implicit exploration data. Advances in neural information processing systems 23. Cited by: Appendix A, §2. Team et al. (2024) G. Team, M. Riviere, S. Pathak, P. G. Sessa, C. Hardin, S. Bhupatiraju, L. Hussenot, T. Mesnard, B. Shahriari, A. Ramé, et al. Gemma 2: improving open language models at a practical size. arXiv preprint arXiv:2408.00118. Cited by: §6. Thomas et al. (2015a) P. Thomas, G. Theocharous, and M. Ghavamzadeh High confidence policy improvement. In International Conference on Machine Learning, p. 2380–2388. Cited by: Appendix A, §2. Thomas et al. (2015b) P. Thomas, G. Theocharous, and M. Ghavamzadeh High-confidence off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 29(01). Cited by: Appendix A, §2. van der Vaart (1998) A. van der Vaart Asymptotic statistics. Cambridge University Press, Cambridge. External Links: ISBN 0521496039 Cited by: §4.2. Verdun et al. (2025) C. M. Verdun, A. Oesterling, H. Lakkaraju, and F. P. Calmon Soft best-of-n sampling for model alignment. In 2025 IEEE International Symposium on Information Theory (ISIT), p. 1–6. Cited by: Appendix A. Wang et al. (2017) Y. Wang, A. Agarwal, and M. Dudık Optimal and adaptive off-policy evaluation in contextual bandits. In International Conference on Machine Learning, p. 3589–3597. Cited by: Appendix A. Yang et al. (2024) J. Q. Yang, S. Salamatian, Z. Sun, A. T. Suresh, and A. Beirami Asymptotics of language model alignment. In 2024 IEEE International Symposium on Information Theory (ISIT), p. 2027–2032. Cited by: Appendix A, §2. Yu et al. (2026) Z. Yu, Z. S. Wu, and A. Block From curiosity to caution: mitigating reward hacking for best-of-n with pessimism. arXiv preprint arXiv:2604.04648. Cited by: Appendix A. Zheng et al. (2023) L. Zheng, W. Chiang, Y. Sheng, S. Zhuang, Z. Wu, Y. Zhuang, Z. Lin, Z. Li, D. Li, E. Xing, et al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in neural information processing systems 36, p. 46595–46623. Cited by: §3. Appendix A Extended related work BoN and inference-time compute. Theoretical work characterizes the BoN policy, its KL divergence to the reference policy, and its optimality and scaling behavior (Gui et al., 2024; Yang et al., 2024; Mroueh and Nitsure, 2025; Beirami et al., 2025; Huang et al., 2025; Sriraman and Block, 2026). More broadly, repeated sampling with a verifier or reward model is a central way to scale inference-time compute (Brown et al., 2024; Snell et al., 2024), where best-of-k performance is commonly estimated via the unbiased pass@k estimator (Chen et al., 2021). Our plug-in term (Eq. (5)) follows the same U-statistic principle, but such estimators require the reward of every sampled response. In our setting, rewards are observed only for logged responses, which is why BoN-DR needs its correction term. Mitigating reward overoptimization. Existing mitigations change the deployed policy by modifying (i) the score, e.g., via reward-model ensembles (Coste et al., 2024) or uncertainty penalties (Yu et al., 2026); (i) the selection rule, e.g., via regularized, pessimistic, or soft BoN (Jinnai et al., 2025; Huang et al., 2025; Verdun et al., 2025; Aminian et al., 2026); or (i) the model, via fine-tuning or distillation (Gui et al., 2024; Sessa et al., 2025; Chow et al., 2025). Some of these additionally require response likelihoods or model weights. Our work is complementary: we keep standard BoN fixed and evaluate it and select its budget from logged data. Selecting inference-time parameters. Closest to our work, Khalaf et al. (2025) tune the BoN budget via the peak of the true reward. Their method is sample-only but requires true rewards for all sampled responses and provides no uncertainty quantification. Raman et al. (2025) instead allocate a given budget adaptively across prompts. In contrast, we select N from logged data with simultaneous confidence bounds and a no-harm guarantee. Off-policy evaluation. Beyond the classical estimators (Li et al., 2011; Horvitz and Thompson, 1952; Strehl et al., 2010; Dudik et al., 2011), OPE has been extended to improve efficiency (Wang et al., 2017; Narita et al., 2019; Kallus and Uehara, 2020), handle limited overlap or distribution shift (Kallus, 2018; Kallus, 2021; Schweisthal et al., 2023; Hatt et al., 2022; Hess et al., 2026), and large action spaces via embeddings (Saito and Joachims, 2022), as well as to human-feedback and preference data (Li et al., 2024; Bhargava et al., 2024; Frauen et al., 2026). All of these require the action probabilities of the behavior policy, which are unavailable for free-form text under sample-only access. We instead exploit the known BoN selection mechanism, which expresses the density ratio through rank probabilities. Uncertainty-aware policy selection. High-confidence OPE and safe policy improvement use lower confidence bounds to avoid underperforming a baseline (Thomas et al., 2015b; Thomas et al., 2015a; Laroche et al., 2019), with related confidence-based selection methods for contextual bandits (Kuzborskij et al., 2021; Karampatziakis et al., 2021; Ryu et al., 2025; Jin et al., 2025). Safe Improvement applies this principle to BoN, with simultaneous bounds across budgets that share the same logged data and auxiliary samples. Appendix B Proofs B.1 Regularity conditions We first make precise the regularity conditions used in the asymptotic results. For the efficiency result, let sns_n and μ^n μ_n denote the fitted score and reward functions at sample size n; the main text suppresses this dependence on n. These functions may coincide. Let nT_n denote the data used to fit (sn,μ^n)(s_n, μ_n). Assumption B.1 (Regularity conditions). The following conditions hold. (i) Sampling. The evaluation observations Zi=(Xi,Ai,Yi),i=1,…,n,Z_i=(X_i,A_i,Y_i), i=1,…,n, are i.i.d., with Ai∣Xi=x∼πb(⋅∣x),[Yi∣Xi=x,Ai=a]=μ(x,a).A_i X_i=x _b(· x), [Y_i X_i=x,A_i=a]=μ(x,a). The action space A is finite or countable. The training data nT_n are independent of the evaluation sample. Conditional on XiX_i, the auxiliary actions A~i1,…,A~iM∼i.i.d.πb(⋅∣Xi) A_i1,…, A_iM i.i.d. _b(· X_i) are independent of (Ai,Yi)(A_i,Y_i), and auxiliary pools are independent across i. (i) Budgets. The BoN budget N is fixed as n→∞n→∞. For the finite-pool result, M≥N−1M≥ N-1 is fixed. For the efficiency result, M=Mn→∞M=M_n→∞. (i) Moments. For finite-M validity, ⁡[Y2]<∞,⁡[μ^n(X,A)2]<∞,E[Y^2]<∞, [ μ_n(X,A)^2]<∞, where A∼πb(⋅∣X)A _b(· X). For the efficiency result, for some δ>0δ>0, ⁡[|Y|2+δ]<∞,supn⁡[|μ^n(X,A)|2+δ]<∞.E[|Y|^2+δ]<∞, _nE[| μ_n(X,A)|^2+δ]<∞. (iv) reward function consistency. For the efficiency result, ‖μ^n−μ‖L2(PX,A)=op(1),\| μ_n-μ\|_L_2(P_X,A)=o_p(1), where PX,AP_X,A is induced by X∼PXX P_X and A∼πb(⋅∣X)A _b(· X). (v) Nondegenerate limiting variance. Define ϕN,neff(Z)=∑a∈πNsn(a∣X)μ(X,a)+wNsn(X,A)Y−μ⁡(X,A)−V⁡(πNsn). _N,n^eff(Z)= _a _N^s_n(a X)μ(X,a)+w_N^s_n(X,A)\Y-μ(X,A)\-V( _N^s_n). We assume Var(ϕN,neff(Z))⟶σN,eff2∈(0,∞).Var( _N,n^eff(Z)) _N,eff^2∈(0,∞). The finite-M variances appearing in Theorem 4.2(a) are also assumed positive and finite. The efficiency statement treats the behavior sampler πb(⋅∣x) _b(· x) and, conditional on the training sample, the induced BoN policy as fixed. Thus the unknown components relevant to the efficiency bound are the context distribution and conditional reward distribution. Unlike generic doubly robust estimators with two learned nuisance functions, no product-rate condition such as ∥μ^−μ∥2∥w^−w∥2=op(n−1/2)\| μ-μ\|_2\,\| w-w\|_2=o_p(n^-1/2) is required. The pooled weight estimator is conditionally unbiased for the exact BoN density ratio, so finite auxiliary sampling introduces mean-zero Monte Carlo variation rather than nuisance-estimation bias. The independent training sample also avoids Donsker or entropy conditions on the fitted model classes. B.2 Proof of Proposition 4.1 Proof. Fix x and a with πb(a∣x)>0 _b(a x)>0, and write F−:=Fx−(a),F:=Fx(a),q:=F−F−.F^-:=F_x^-(a), F:=F_x(a), q:=F-F^-. Here q is the probability that an independent behavior-policy draw has the same score as a, so q≥πb(a∣x)>0q≥ _b(a x)>0. Condition on one of the N BoN candidates being equal to a. If exactly t of the other N−1N-1 candidates have equal score and the remaining N−1−tN-1-t have smaller score, this occurrence of a is selected with probability 1/(t+1)1/(t+1). By exchangeability of the candidate positions, wNs(x,a) w_N^s(x,a) =N∑t=0N−1(N−1t)qt(F−)N−1−t1t+1 =N _t=0^N-1 N-1tq^t(F^-)^N-1-t 1t+1 (17) =∑k=1N(Nk)qk−1(F−)N−k = _k=1^N Nkq^k-1(F^-)^N-k (18) =FN−(F−)NF−F−. = F^N-(F^-)^NF-F^-. (19) Using uN−vNu−v=∑ℓ=0N−1uN−1−ℓvℓ u^N-v^Nu-v= _ =0^N-1u^N-1- v gives wNs(x,a)=gN(Fx(a),Fx−(a)).w_N^s(x,a)=g_N(F_x(a),F_x^-(a)). This representation also implies 0≤wNs(x,a)≤N,0≤ w_N^s(x,a)≤ N, (20) because gNg_N is a sum of N terms in [0,1][0,1]. Finally, ∑aπNs(a∣x)μ^(x,a) _a _N^s(a x) μ(x,a) =∑aπb(a∣x)wNs(x,a)μ^(x,a) = _a _b(a x)w_N^s(x,a) μ(x,a) (21) =A′∼πb(⋅∣x)[gN(Fx(A′),Fx−(A′))μ^(x,A′)], =E_A _b(· x) [g_N(F_x(A ),F_x^-(A )) μ(x,A ) ], (22) where actions outside the support of πb _b have zero probability under BoN. Substituting the same expression for the density ratio in the correction term gives (3). ∎ B.3 Finite-pool unbiasedness For a function f, define mN,f(x):=A∼πNs(⋅∣x)[f(x,A)].m_N,f(x):=E_A _N^s(· x)[f(x,A)]. Lemma B.2. For every M≥N−1M≥ N-1, ⁡[v^i,Ns,M+1∣Xi] [ v_i,N^s,M+1 X_i] =mN,μ^(Xi), =m_N, μ(X_i), (23) [w^i,Ns,M∣Xi,Ai] [ w_i,N^s,M X_i,A_i] =wNs(Xi,Ai). =w_N^s(X_i,A_i). (24) Moreover, 0≤w^i,Ns,M≤N.0≤ w_i,N^s,M≤ N. Proof. Conditional on Xi=xX_i=x, the stacked actions Ai,A~i1,…,A~iMA_i, A_i1,…, A_iM are M+1M+1 independent draws from πb(⋅∣x) _b(· x). Hence every size-N subset in (5) has the distribution of N fresh BoN candidates. The kernel hi,Jh_i,J analytically averages over uniform tie-breaking, so ⁡[hi,J∣Xi=x]=mN,μ^(x).E[h_i,J X_i=x]=m_N, μ(x). Averaging over subsets proves (23). For completeness, an N-subset has maximum score rigr_ig exactly when it is contained among the EigE_ig observations with score at most rigr_ig but not among the LigL_ig observations with strictly smaller score. There are therefore (EigN)−(LigN) E_igN- L_igN such subsets. Symmetry across the tied maximizing occurrences gives their average prediction μ¯ig μ_ig, yielding (7). For the weight estimator, fix (Xi,Ai)=(x,a)(X_i,A_i)=(x,a) and a subset J of N−1N-1 auxiliary observations. Define QJ=Ns(x,A~ij)≤s(x,a) for all j∈J1+∑j∈Js(x,A~ij)=s(x,a).Q_J=N 1\s(x, A_ij)≤ s(x,a) for all j∈ J\1+ _j∈ J1\s(x, A_ij)=s(x,a)\. The quantity QJ/NQ_J/N is exactly the probability that the distinguished logged occurrence a is selected when it is combined with the N−1N-1 candidates in J. The argument in Proposition 4.1 therefore gives [QJ∣Xi=x,Ai=a]=wNs(x,a).E[Q_J X_i=x,A_i=a]=w_N^s(x,a). Averaging over all such subsets proves (24). Grouping subsets according to the number t of equal-score competitors gives exactly (9). Since 0≤QJ≤N0≤ Q_J≤ N, the same bound holds for w^i,Ns,M w_i,N^s,M. ∎ Lemma B.3. For every M≥N−1M≥ N-1, ⁡[ψNM(Zi,A~i)]=V⁡(πNs),E[ _N^M(Z_i, A_i)]=V( _N^s), for any fixed reward function satisfying the required moment conditions. Proof. Lemma B.2 gives ⁡[v^i,Ns,M+1∣Xi]=mN,μ^(Xi).E[ v_i,N^s,M+1 X_i]=m_N, μ(X_i). Also, conditional on (Xi,Ai)(X_i,A_i), the auxiliary pool is independent of YiY_i, so [w^i,Ns,MYi−μ^(Xi,Ai)∣Xi,Ai] [ w_i,N^s,M\Y_i- μ(X_i,A_i)\ X_i,A_i ] (25) =wNs(Xi,Ai)μ⁡(Xi,Ai)−μ^(Xi,Ai). =w_N^s(X_i,A_i)\μ(X_i,A_i)- μ(X_i,A_i)\. (26) Averaging over Ai∼πb(⋅∣Xi)A_i _b(· X_i) gives mN,μ(Xi)−mN,μ^(Xi).m_N,μ(X_i)-m_N, μ(X_i). Thus ⁡[ψNM(Zi,A~i)∣Xi]=mN,μ(Xi),E[ _N^M(Z_i, A_i) X_i]=m_N,μ(X_i), and taking expectation over XiX_i proves the result. ∎ B.4 Proof of Theorem 4.2 Proof. For fixed M, conditional on the fitted functions, (Zi,A~i)(Z_i, A_i) are i.i.d. By Lemma B.3, ⁡[ψNM(Zi,A~i)]=V⁡(πNs).E[ _N^M(Z_i, A_i)]=V( _N^s). The finite-second-moment assumption and the ordinary central limit theorem therefore give n(V^DRM(πNs)−V⁡(πNs))↝⁡(0,σN,M2), n ( V_DR^M( _N^s)-V( _N^s) ) (0, _N,M^2), proving part (a). No consistency of μ μ is used. For part (b), define the exact-ratio DR score ψN,n∞(Z)=mN,μ^n(X)+wNsn(X,A)Y−μ^n(X,A). _N,n^∞(Z)=m_N, μ_n(X)+w_N^s_n(X,A)\Y- μ_n(X,A)\. A fixed-order U-statistic with a square-integrable kernel converges in L2L_2 to its expectation as the pool size increases; more precisely, its variance is O⁡(M−1)O(M^-1) for fixed kernel order. Applying this to the plug-in and weight kernels, using 0≤w^Nsn,M,wNsn≤N0≤ w_N^s_n,M,w_N^s_n≤ N, yields ‖ψNMn(Z,A~,μ^n)−ψN,n∞(Z)‖2=op(1). \| _N^M_n(Z, A; μ_n)- _N,n^∞(Z) \|_2=o_p(1). (27) The moment conditions in Assumption B.1 ensure the corresponding U-statistic second moments are uniformly bounded. Let δn(x,a)=μ^n(x,a)−μ⁡(x,a). _n(x,a)= μ_n(x,a)-μ(x,a). Since wNsn≤Nw_N^s_n≤ N, ⁡[mN,δn(X)2] [m_N, _n(X)^2] ≤X,A∼πNsn[δn(X,A)2] _X,A _N^s_n[ _n(X,A)^2] (28) =X,A∼πb[wNsn(X,A)δn(X,A)2] =E_X,A _b[w_N^s_n(X,A) _n(X,A)^2] (29) ≤N‖δn‖22. ≤ N\| _n\|_2^2. (30) Hence ‖ψN,n∞(Z)−[mN,μ(X)+wNsn(X,A)Y−μ⁡(X,A)]‖2 \| _N,n^∞(Z)- [m_N,μ(X)+w_N^s_n(X,A)\Y-μ(X,A)\ ] \|_2 (31) ≤(N+N)‖μ^n−μ‖2=op(1). ≤( N+N)\| μ_n-μ\|_2=o_p(1). (32) Combining (27) and (32), ‖ψNMn(Z,A~,μ^n)−[V⁡(πNsn)+ϕN,neff(Z)]‖2=op(1). \| _N^M_n(Z, A; μ_n)- [V( _N^s_n)+ _N,n^eff(Z) ] \|_2=o_p(1). Both scores have expectation V⁡(πNsn)V( _N^s_n). Therefore, if Ri,nR_i,n denotes their difference, ⁡[Ri,n]=0,⁡[Ri,n2]=op(1),E[R_i,n]=0, [R_i,n^2]=o_p(1), and independence across evaluation observations gives 1n∑i=1nRi,n=op(1). 1 n _i=1^nR_i,n=o_p(1). Consequently, n(V^DRMn(πNsn)−V⁡(πNsn))=1n∑i=1nϕN,neff(Zi)+op(1). n ( V_DR^M_n( _N^s_n)-V( _N^s_n) )= 1 n _i=1^n _N,n^eff(Z_i)+o_p(1). (33) The (2+δ)(2+δ) moment condition implies the Lindeberg condition, and the assumed variance convergence therefore yields 1n∑i=1nϕN,neff(Zi)↝⁡(0,σN,eff2). 1 n _i=1^n _N,n^eff(Z_i) (0, _N,eff^2). Slutsky’s theorem proves part (b). Finally, conditional on the behavior sampler and fitted score, πNsn _N^s_n is a fixed target policy. The standard AIPW influence function for its value is mN,μ(X)−V⁡(πNsn)+wNsn(X,A)Y−μ⁡(X,A).m_N,μ(X)-V( _N^s_n)+w_N^s_n(X,A)\Y-μ(X,A)\. Indeed, perturbing the context distribution produces the first term, while perturbing the conditional reward distribution produces the second; because πb _b is treated as fixed, there is no additional behavior-policy term. Thus ϕN,neff _N,n^eff is the efficient influence function in this model, and (33) establishes the claimed efficiency. The argument also shows why no rate condition between MnM_n and n is required: the finite-pool approximation is mean zero for every MnM_n, so it is enough that its per-observation variance vanish as Mn→∞M_n→∞. ∎ B.5 Proof of Corollary 5.1 Proof. Write VN=V⁡(πNs),V^N=V^DRM(πNs).V_N=V( _N^s), V_N= V_DR^M( _N^s). By Theorem 4.2(a) and finiteness of N, ϵn:=maxN∈⁡|V^N−VN|=op(1). _n:= _N | V_N-V_N|=o_p(1). Let N⋆∈argmaxN∈VNN ∈ argmax_N V_N. Since N^value N_value maximizes V^N V_N, VN⋆≤V^N⋆+ϵn≤V^N^value+ϵn≤VN^value+2ϵn.V_N ≤ V_N + _n≤ V_ N_value+ _n≤ V_ N_value+2 _n. Therefore 0≤maxN∈⁡VN−VN^value≤2ϵn=op(1),0≤ _N V_N-V_ N_value≤ 2 _n=o_p(1), which proves the result. Uniqueness of the maximizing budget is not required because the conclusion concerns policy value rather than the selected index. ∎ B.6 Proof of Theorem 5.2 Proof. Let +=∖1,N_+=N \1\, and collect the improvement scores into Di=(Di,NM:N∈+),Δ=(ΔN:N∈+).D_i=(D_i,N^M:N _+), =( _N:N _+). By Lemma B.3, ⁡[Di,NM]=ΔN.E[D_i,N^M]= _N. Since N is fixed and finite, the multivariate central limit theorem gives n(Δ^M−Δ)↝⁡(0,Σ),Σ=Var(Di), n( ^M- ) (0, ), =Var(D_i), and the empirical covariance matrix converges in probability to Σ . Conditional on the data, 1n∑i=1nξi(Di−Δ^M) 1 n _i=1^n _i(D_i- ^M) is exactly Gaussian with the empirical covariance matrix. Hence the multiplier bootstrap consistently estimates the distribution of the maximum standardized estimation error. Therefore ℙ⁡(ΔN≥LCB^Δ(N) for every N∈+)=1−α+o⁡(1).P ( _N≥ LCB_ (N) for every N _+ )=1-α+o(1). (34) On the event in (34), if N^LCB=1 N_LCB=1 then the selected value equals V⁡(πb)V( _b). Otherwise, LCB^Δ(N^LCB)>0, LCB_ ( N_LCB)>0, so simultaneous coverage implies ΔN^LCB>0. _ N_LCB>0. Thus ℙ⁡(V⁡(πN^LCBs)≥V⁡(πb))≥1−α−o⁡(1).P (V( _ N_LCB^s)≥ V( _b) )≥ 1-α-o(1). For oracle consistency, finiteness of the grid gives maxN∈+⁡|Δ^NM−ΔN|=op(1). _N _+| _N^M- _N|=o_p(1). The bootstrap critical value and estimated standard deviations are Op(1)O_p(1), so the confidence penalties are op(1)o_p(1) and therefore maxN∈+⁡|LCB^Δ(N)−ΔN|=op(1). _N _+ | LCB_ (N)- _N |=o_p(1). Let Δ⋆=maxN∈+⁡ΔN. = _N _+ _N. If Δ⋆>0 >0, the positivity threshold is eventually passed and the finite-grid argmax argument implies that the selected improvement converges to Δ⋆ . If Δ⋆<0 <0, all lower bounds are eventually negative and the procedure selects N=1N=1. If Δ⋆=0 =0, either the baseline is selected or a budget whose population improvement converges to zero is selected. In all cases, V⁡(πN^LCBs)⟶V(πb)+max⁡0,Δ⋆=maxN∈⁡V⁡(πNs).V( _ N_LCB^s) p V( _b)+ \0, \= _N V( _N^s). ∎ Appendix C Experimental details C.1 Synthetic experiments Generative model. Let X be uniform on −1,+1\-1,+1\. The action space contains 1616 main actions and eight tail actions, =main∪tail.A=A_main _tail. Their base qualities are q0(aj)=0.55+0.30(j−1)15,j=1,…,16,q0(bk)=0.05+0.20(k−1)7,k=1,…,8.q_0(a_j)=0.55+ 0.30(j-1)15, j=1,…,16, q_0(b_k)=0.05+ 0.20(k-1)7, k=1,…,8. The behavior policy is independent of context: πb(a∣x)=0.96/16,a∈main,0.04/8,a∈tail. _b(a x)= cases0.96/16,&a _main,\\ 0.04/8,&a _tail. cases Conditional rewards satisfy Y∣X=x,A=a∼Bernoulli(μ(x,a)),μ(x,a)=q0(a)+0.04x.Y X=x,A=a (μ(x,a)), μ(x,a)=q_0(a)+0.04x. Independent error controls. We specify the score function and reward function as sγ(x,a)=μ(x,a)+γ 1a∈tail,s_γ(x,a)=μ(x,a)+γ\,1\a _tail\, μ^δ(x,a)=clip(μ(x,a)+δ 1a∈tail,0,1). μ_δ(x,a)=clip\! (μ(x,a)+δ\,1\a _tail\,0,1 ). Thus, γ changes the ranking of tail actions and hence the target policy πNsγ _N^s_γ. In contrast, δ changes the reward function predictions while leaving the target policy fixed. At δ=0δ=0, the reward function is correct. The default configuration is γ=0.65γ=0.65, δ=0.4δ=0.4. The selection comparison in Figure 4 uses δ=0.6δ=0.6, and the efficiency experiment in Appendix D.3 uses δ=0δ=0. Sampling and evaluation. Each repetition contains n independent logged observations and M independent auxiliary behavior-policy draws per logged context. The main experiments use n=4,096n=4,096, 300300 repetitions, and the candidate grid =1,2,4,…,256N=\1,2,4,…,256\, with M≥NmaxM≥ N_ , satisfying the shared-pool requirement M≥Nmax−1M≥ N_ -1. Sample-size and auxiliary-pool sweeps vary the corresponding quantity. Shared random streams pair the data across estimators and error settings. We compute the population policy value exactly: VN(γ)=12∑x∈−1,+1∑a∈πNsγ(a∣x)μ(x,a).V_N(γ)= 12 _x∈\-1,+1\ _a _N^s_γ(a x)μ(x,a). The oracle budget is the smallest maximizer of VN(γ)V_N(γ) over N. Population values and infinite-pool variance benchmarks are used only for evaluation. The estimators receive sampled observations, score evaluations, and reward function predictions. Experimental regimes were fixed using population quantities before running the repetitions. C.2 GSM8K environment GSM8K provides 7,4737,473 training and 1,3191,319 test questions. We split the training questions deterministically into 3,5003,500 prompts for fitting the reward function and 3,9733,973 validation prompts for off-policy evaluation and selection, and reserve the official test set for the exact evaluation of selected policies. For each prompt we store 512512 independently sampled responses with their exact-match rewards and their scores under both reward models. We use =1,2,4,…,256N=\1,2,4,…,256\ as the candidate grid, withM≥NmaxM≥ N_ . Each validation repetition reveals the reward of one uniformly drawn response per prompt; the remaining responses of that prompt form the auxiliary pool used to estimate rank probabilities. This mimics the logged-data setting in which one response per prompt received feedback. We use 500500 logging repetitions for estimation and pointwise inference, and 100100 repetitions for policy selection. The reward function is a cubic-spline calibration of the reward model score with six quantile knots, a logistic link, fixed L2L_2 regularization, and constant extrapolation beyond the observed score range. It is fit once on the 3,5003,500 training prompts and held fixed across repetitions, budgets, and selection rules. This is a deliberately favorable choice for the Plug-in estimator: the reward function is a calibration of the same score that defines the target policy, so any bias we report is not caused by an unrelated or weak nuisance. Appendix D.7 confirms the conclusion with two independently trained reward functions. C.3 Baseline estimators We consider two baseline estimators corresponding to the two components of the pooled BoN-DR estimator in Eq. (11): BoN-IPW and Plug-in. The Plug-in estimator retains only the plug-in term, whereas BoN-IPW uses the estimated BoN density ratio appearing in the correction term. Pooled BoN-IPW estimator. BoN-IPW uses the estimated BoN density ratio from the correction term of Eq. (11). We define the pooled BoN-IPW estimator as V^IPWM(πNs) V_IPW^M( _N^s) =1n∑i=1nw^i,Ns,M(xi,a¯i)yi = 1n _i=1^n w_i,N^s,M(x_i, a_i)y_i (35) Thus, BoN-IPW relies on the logged rewards together with the estimated BoN density ratio, without using the plug-in term of BoN-DR. Plug-in estimator. The Plug-in estimator corresponds directly to the plug-in term of the pooled BoN-DR estimator in Eq. (11). We define the Plug-in estimator as V^Plug−inM(πNs) V_Plug-in^M( _N^s) =1n∑i=1nv^i,Ns,M+1(xi,a¯i) = 1n _i=1^n v_i,N^s,M+1(x_i, a_i) (36) The Plug-in estimator therefore evaluates the target BoN policy using the estimated reward function alone, without the correction based on the logged reward. Consequently, errors in the estimated reward function are not corrected by the Plug-in estimator. C.4 Confidence statements For DR, σ^N,M σ_N,M is the empirical standard deviation of the scores ψNM(zi,a~i) _N^M(z_i, a_i); the other estimators use their corresponding scores. Pointwise confidence intervals use the Wald form V^DRM(πNs)±z1−α/2σ^N,M/n V_DR^M( _N^s)± z_1-α/2 σ_N,M/ n. Simultaneous bounds over a candidate grid use the Gaussian multiplier bootstrap of Section 5 with 2,0002,000 draws and α=0.05α=0.05, with the critical value recomputed for each grid prefix rather than reused from the full grid. Multiplier draws are shared across budgets so that the dependence between value estimates is preserved. C.5 Metric definitions Bias is the mean estimate minus the exact value; RMSE is the square root of the mean squared error; the empirical dispersion uses ddof=1ddof=1; interval width is the upper minus the lower limit. Coverage is the fraction of repetitions whose interval contains the exact value, counted once per repetition. Simultaneous coverage counts one event per repetition and grid, never one event per budget. For selection, gain is the exact value of the selected policy minus the exact value at N=1N=1. On GSM8K, estimation and coverage are evaluated against the exact benchmark induced by the stored validation responses, while selected budgets are evaluated independently on the held-out test set. The reported GSM8K harm rate is therefore an empirical analogue of the theoretical no-harm criterion. In the Synthetic experiments, selected policies are evaluated on the exact population. The harm rate is the fraction of repetitions whose gain is negative beyond a numerical tolerance of 10−1210^-12; it is not the fraction of individually harmed prompts. Exact ties in a selection objective resolve to the smallest budget. The Safe Improvement rule includes a zero bound at N=1N=1, so it returns N=1N=1 whenever no budget has a strictly positive improvement bound. Monte Carlo uncertainty is binomial for coverage and harm, and the between-repetition standard deviation divided by the square root of the number of repetitions for bias and gain. To keep the tables readable these standard errors are not printed; they are retained for every reported cell in the result files described in Appendix C.6. At 300300 repetitions a coverage of 0.950.95 has a Monte Carlo standard error of 0.0130.013, and at 100100 repetitions a harm rate of 0.140.14 has one of 0.0350.035. C.6 Reproducibility All numbers in this paper are computed from a single frozen result set, which is fixed before any figure or table is produced. It contains 5,1005,100 per-repetition records for the Synthetic experiments and 3,6003,600 for GSM8K, covering every combination of environment, estimator, budget, and selection rule reported here and in the appendix. Random number generation uses named streams seeded per repetition, so contexts, logged actions, rewards, and auxiliary draws are shared across estimators and across misspecification settings. Any two estimators are therefore compared on identical data, and differences between them are not attributable to sampling variation in the inputs. Appendix D Additional results for off-policy evaluation D.1 Reward overoptimization under score function misspecification We further study how misspecification of the score function affects the induced BoN policy. In the Synthetic experiments, the parameter γ increases the scores of a small set of low-quality actions that are rarely sampled under the behavior policy. As γ increases, these actions are more likely to be selected by BoN, particularly at larger sampling budgets N. Consequently, the induced BoN policy places increasing mass on actions with low probability under the behavior policy, leading to weaker overlap and larger density ratios. Figure 5 illustrates the resulting reward overoptimization: while the expected selected score continues to increase with N, the true policy value can peak and subsequently decline when the score function is sufficiently misspecified. Throughout this experiment, we fix the reward function error at δ=0.4δ=0.4 and vary only the score-function error γ. Figure 5: Robust to score function misspecification (δ=0.4δ=0.4). Left: exact policy value V⁡(πNs)V( _N^s); circles show the optimal budget N⋆N . Right: expected score of the selected action. Colors show the score error γ. D.2 Sensitivity to validation-set size To assess the sensitivity of downstream policy evaluation and budget selection to the amount of validation data, we vary the size of the logged validation set while keeping the remaining experimental setup fixed. Figure 6 reports policy-value estimation at N=256N=256 and Value Maximization selection over the candidate budget grid. As the validation size increases, the RMSE of BoN-DR and BoN-IPW decreases and their confidence-interval coverage approaches the nominal 95%95\% level, whereas the bias of the Plug-in estimator persists. The improved estimation accuracy also translates into more reliable budget selection: the probability of selecting the oracle-optimal budget N⋆N increases with the validation size, with BoN-DR reaching high selection accuracy more quickly than BoN-IPW. Overall, the results show that the downstream evaluation and selection procedure becomes increasingly stable as more logged validation data are available. Figure 6: Estimated BoN policy value at N=256N=256 as logged sample size grows. (a) RMSE at log scale. (b) Coverage of the nominal 95%95\% pointwise confidence interval. The dotted line marks the nominal level. (c) Probability of selecting the optimal budget N⋆N under Value Maximization selection. D.3 Finite-M efficiency Figure 7 isolates the cost of the finite auxiliary pool in the Synthetic experiments with a correctly specified reward function (δ=0δ=0). The paired ratio between the finite-M and the infinite-M DR variance falls from 1.3351.335 at M=256M=256 to 1.0191.019 at M=4096M=4096 at N=256N=256, so the Monte Carlo cost of the pool vanishes as M grows, as Theorem 4.2 (b) predicts. The right panel compares the realized variance with the semiparametric efficiency bound: DR attains the bound closely, whereas IPW exceeds it by up to a factor of 4.94.9. Figure 7: Finite-M cost and efficiency in the synthetic experiments. Correctly specified reward function (δ=0δ=0), γ=0.65γ=0.65, n=4,096n=4,096, 300300 repetitions. Left: ratio of the finite-M DR variance to the paired infinite-M oracle variance. Right: ratio of the realized variance to the efficiency bound at M=256M=256. The dotted line marks a ratio of one. D.4 Real coverage Figure 8 examines interval calibration over the full budget grid on GSM8K. Across both OASST and Skywork, BoN-DR and BoN-IPW achieve coverage close to the nominal 95%95\% level over most budgets, despite the different BoN policies induced by the two score functions. BoN-DR coverage deteriorates at the largest budgets, where rank-weight overlap becomes weak, while BoN-IPW remains better calibrated at these endpoints. This undercoverage is consistent with a finite-sample limitation under increasingly extreme BoN reweighting. In contrast, Plug-in coverage drops to zero from N=4N=4 onward in all six configurations. Overall, the results suggest that BoN-DR and BoN-IPW provide reasonably well-calibrated uncertainty quantification across both score-function regimes, with the main deviations occurring at the largest budgets. Figure 8: Interval validity across budgets on GSM8K. Empirical coverage of the nominal 95%95\% pointwise confidence interval over 500500 repetitions. The dotted line marks the nominal level. Rows are external reward models used as score functions, and columns are reference models. The Plug-in estimator never covers from N=4N=4 on. DR declines at the largest budgets, where overlap deteriorates. D.5 Error decomposition over the budget grid Figure 9 decomposes the estimation error on GSM8K across all budgets, which a single-budget table cannot show. The Plug-in bias is large and nearly constant in N, whereas DR and IPW are essentially unbiased at every budget and their dispersion grows as overlap deteriorates. The Plug-in estimator therefore becomes competitive in RMSE only at the largest budgets, and only by trading a constant bias against negligible variance. Table 2 gives the per-configuration numbers at N=256N=256. Figure 9: Absolute bias, dispersion, and RMSE on GSM8K over the budget grid. Each quantity is averaged over the six configurations, 500500 repetitions, log scale. Table 2: Estimation on GSM8K at N=256N=256. 500500 repetitions with n=3,973n=3,973 logged prompts. Coverage is that of the nominal 95%95\% pointwise confidence interval. Bold marks the lowest RMSE and the coverage closest to 0.950.95 within each configuration. Reward model Estimator Bias RMSE CI width Coverage OASST-RM-2.1, reference model Gemma-2-2B Plug-in 0.097 0.097 0.002 0.000 BoN-IPW 0.002 0.156 0.625 0.932 BoN-DR 0.008 0.102 0.364 0.902 OASST-RM-2.1, reference model Llama-3.2-3B Plug-in 0.029 0.029 0.001 0.000 BoN-IPW 0.005 0.179 0.703 0.934 BoN-DR 0.003 0.079 0.280 0.880 OASST-RM-2.1, reference model Qwen3.5-4B Plug-in 0.018 0.018 0.001 0.000 BoN-IPW 0.008 0.187 0.726 0.942 BoN-DR 0.003 0.058 0.225 0.854 Skywork-Reward-V2, reference model Gemma-2-2B Plug-in 0.041 0.041 0.007 0.000 BoN-IPW 0.004 0.172 0.704 0.954 BoN-DR -0.003 0.064 0.252 0.892 Skywork-Reward-V2, reference model Llama-3.2-3B Plug-in -0.013 0.013 0.002 0.000 BoN-IPW -0.010 0.198 0.737 0.922 BoN-DR -0.002 0.040 0.134 0.754 Skywork-Reward-V2, reference model Qwen3.5-4B Plug-in 0.015 0.015 0.001 0.000 BoN-IPW 0.001 0.190 0.727 0.926 BoN-DR -0.002 0.048 0.168 0.776 D.6 Overlap diagnostics Figure 10 reports the effective sample size of the rank weights on GSM8K. It falls from 3,9733,973 prompts at N=1N=1 to about 2525 at N=256N=256 and about 1010 at N=512N=512, where only 0.5%0.5\% of prompts carry non-zero weight. The endpoint N=512N=512 uses all M+1=512M+1=512 stored responses and satisfies the boundary condition M=N−1M=N-1 in Theorem 4.2. We report it only as an overlap stress test and restrict the main text to N≤256N≤ 256. Extending the grid to Nmax=512N_ =512 roughly doubles the residual harm of DR under Safe Improvement selection, from 0.120.12 to 0.240.24 on Llama with OASST and from 0.140.14 to 0.330.33 on Qwen with OASST, while IPW is unaffected at 0.000.00 and 0.010.01. Figure 10: Overlap of the rank weights on GSM8K. Left: effective sample size, log scale, out of 3,9733,973 validation prompts. Right: fraction of prompts receiving non-zero weight. Solid lines are OASST, dashed lines are Skywork; the vertical line marks the largest budget used in the main text. D.7 Robustness to the reward function Table 3 repeats the GSM8K comparison with two reward functions trained independently of the score function, a TF–IDF logistic regression and an embedding-based LightGBM model. Plug-in coverage is zero for both, so the failure reported in RQ2 is a property of the estimator under misspecification and not an artifact of the score-calibration spline used in the main text. Table 3: Estimation on GSM8K at N=256N=256 with independently trained reward functions. OASST score function. Coverage is that of the nominal 95%95\% pointwise confidence interval. Bold marks the lowest RMSE within each reference model and reward function. Reward estimator Estimator Bias RMSE Coverage Reference model Gemma-2-2B Embedding LightGBM Plug-in 0.040 0.040 0.000 BoN-IPW 0.008 0.167 0.880 BoN-DR -0.015 0.093 0.970 TF–IDF logistic Plug-in 0.022 0.022 0.000 BoN-IPW 0.008 0.167 0.880 BoN-DR -0.011 0.101 0.940 Reference model Llama-3.2-3B Embedding LightGBM Plug-in 0.023 0.023 0.000 BoN-IPW -0.011 0.194 0.920 BoN-DR 0.005 0.090 0.800 TF–IDF logistic Plug-in 0.024 0.024 0.000 BoN-IPW -0.011 0.194 0.920 BoN-DR 0.006 0.084 0.820 Reference model Qwen3.5-4B Embedding LightGBM Plug-in 0.018 0.018 0.000 BoN-IPW 0.013 0.185 0.940 BoN-DR 0.003 0.061 0.830 TF–IDF logistic Plug-in 0.014 0.014 0.000 BoN-IPW 0.013 0.185 0.940 BoN-DR 0.002 0.058 0.830 Appendix E Additional results for selection Table 4 gives the numerical results and median selected budgets for Figure 4. The following subsections report the complete comparisons across configurations. Table 4: Selecting N under challenging conditions. Synthetic experiments: score error γ=0.65γ=0.65, reward function error δ=0.6δ=0.6, n=4,096n=4,096, 300300 repetitions; gain in policy value. GSM8K: Qwen3.5-4B with OASST, n=3,973n=3,973, 100100 logging repetitions; gain in accuracy points. Gain is measured against N=1N=1 and higher is better; harm is the fraction of repetitions with negative gain and lower is better; N~ N is the median selected budget. Nmax=256N_ =256. Bold marks the best value per column among the selection methods. The last row gives the best attainable gain on the grid. Synthetic exp (misspecified) GSM8K: Qwen3.5-4B / OASST Selection method Gain Harm N~ N Gain (p) Harm N~ N Naive BoN -0.388 1.00 256 -1.50 1.00 256 Plug-in -0.380 1.00 256 -0.28 1.00 4 BoN-IPW, Value-max 0.068 0.00 8 -0.84 0.77 32 BoN-IPW, Safe-improvement 0.062 0.00 4 0.00 0.01 1 BoN-DR, Value-max 0.069 0.00 8 -0.82 0.73 64 BoN-DR, Safe-improvement 0.067 0.00 4 -0.19 0.14 1 Oracle-best budget 0.071 0.00 8 0.00 0.00 1 E.1 Safe Improvement reduces harmful budget choices. Figure 4 expands the selection analysis in Figure 11 by reporting both the achieved gain and the harm rate in two challenging regimes. The Synthetic experiments with γ=0.65γ=0.65 and δ=0.6δ=0.6 has an interior optimal budget, N⋆=8N =8, so successful selection must exploit the benefit of increasing N without overoptimizing at larger budgets. In contrast, for Qwen3.5-4B with OASST on GSM8K, N⋆=1N =1, so any departure from the reference policy is harmful. These two regimes therefore separate the ability to capture a beneficial nontrivial budget from the ability to avoid unnecessary increases in inference-time compute. Figure 11: Safe Improvement reduces harmful budget choices. Top: Synthetic experiments with γ=0.65γ=0.65, δ=0.6δ=0.6, n=4,096n=4,096, and 300300 repetitions. Bottom: Qwen3.5-4B with OASST on GSM8K, with 3,9733,973 validation prompts and 100100 logging repetitions. Left: mean gain over N=1N=1, measured in policy value for the Synthetic experiments and accuracy percentage points for GSM8K. Higher is better. The dashed red line marks the best attainable gain on the grid. Right: harm rate. Lower is better. Light and solid bars show Value-max and Safe-improvement, respectively. Plug-in uses Value Maximization, and Naive BoN selects Nmax=256N_ =256. Labels report numerical values. In the Synthetic experiments, Value Maximization selection with BoN-IPW and BoN-DR recovers nearly all of the attainable gain and incurs no observed harm, whereas Naive BoN and Plug-in are harmful in every repetition. Safe Improvement is slightly more conservative, but retains most of the gain while likewise avoiding harmful selections. Thus, when the policy-value estimates are sufficiently accurate, both direct value maximization and uncertainty-aware selection identify useful nontrivial budgets. The GSM8K regime is more challenging because the reference policy itself is optimal, so the best attainable gain over N=1N=1 is zero. Value Maximization selection nevertheless frequently chooses larger, harmful budgets: BoN-IPW and BoN-DR lose 0.840.84 and 0.820.82 accuracy percentage points on average, with harm rates of 77%77\% and 73%73\%, respectively. Safe Improvement substantially reduces these losses and lowers the harm rates to 1%1\% for BoN-IPW and 14%14\% for BoN-DR. The remaining BoN-DR harm is consistent with its finite-sample undercoverage at the largest budgets discussed in Appendix D.4. Thus, accounting for uncertainty is particularly useful when maximization over noisy value estimates would otherwise favor unnecessarily large budgets. E.2 Complete results on GSM8K Table 5 reports every estimator with Value Maximization and Safe Improvement for all six configurations, including the aligned ones omitted from RQ3 . Two patterns hold throughout. Under the aligned Skywork reward model, no rule incurs harm, and Safe Improvement reduces gain without reducing the observed harm rate, most visibly for IPW. Under OASST, Safe Improvement reduces the harm incurred by Value Maximization selection with DR and IPW. Residual harm remains for DR on Llama and Qwen. Table 5: Complete selection results on GSM8K. Nmax=256N_ =256, 100100 logging repetitions. Gain is measured in accuracy points against N=1N=1 and higher is better; harm is the fraction of repetitions with negative gain and lower is better. Naive BoN does not depend on the selection rule and is reported once per configuration. Naive BoN Plug-in BoN-IPW BoN-DR Gain Harm Rule Gain Harm Gain Harm Gain Harm OASST-RM-2.1, reference model Gemma-2-2B 4.23 0.00 Value-max 4.84 0.00 4.45 0.00 4.51 0.00 Safe-improvement 4.84 0.00 3.25 0.00 3.98 0.00 OASST-RM-2.1, reference model Llama-3.2-3B -0.51 1.00 Value-max 0.33 0.00 -0.03 0.44 -0.09 0.53 Safe-improvement 0.33 0.00 0.01 0.00 -0.05 0.12 OASST-RM-2.1, reference model Qwen3.5-4B -1.50 1.00 Value-max -0.28 1.00 -0.84 0.77 -0.82 0.73 Safe-improvement -0.28 1.00 0.00 0.01 -0.19 0.14 Skywork-Reward-V2, reference model Gemma-2-2B 23.71 0.00 Value-max 23.71 0.00 21.86 0.00 22.91 0.00 Safe-improvement 23.71 0.00 16.17 0.00 20.57 0.00 Skywork-Reward-V2, reference model Llama-3.2-3B 15.92 0.00 Value-max 15.92 0.00 13.95 0.00 15.07 0.00 Safe-improvement 15.92 0.00 8.86 0.00 14.12 0.00 Skywork-Reward-V2, reference model Qwen3.5-4B 3.11 0.00 Value-max 3.11 0.00 2.57 0.00 2.91 0.00 Safe-improvement 3.11 0.00 0.38 0.00 2.23 0.00 E.3 Complete results in the Synthetic experiments Table 6 sweeps the reward function error at a fixed overoptimized score function. It shows why RQ1 reports δ=0.6δ=0.6: all estimator-based selection rules have zero observed harm up to δ=0.4δ=0.4, because the Plug-in bias is not yet large enough to move its selected budget past the point at which the policy value falls below the value at N=1N=1. At δ=0.6δ=0.6 the Plug-in budget jumps to NmaxN_ and harms in every repetition, while DR and IPW retain positive gains with zero observed harm across the tested values of δ. This also shows that a biased estimator can still select a safe budget, which is why estimation quality and selection quality are evaluated separately in RQ1 . Table 6: Complete selection results in the Synthetic experiments. Score error γ=0.65γ=0.65, n=4,096n=4,096, Nmax=256N_ =256, 300300 repetitions. Gain is measured in policy value against N=1N=1 and higher is better; harm is the fraction of repetitions with negative gain and lower is better. Naive BoN does not depend on the selection rule and is reported once per value of δ. Naive BoN Plug-in BoN-IPW BoN-DR Gain Harm Rule Gain Harm Gain Harm Gain Harm Reward estimator error δ=−0.2δ=-0.2 -0.388 1.00 Value-max 0.065 0.00 0.068 0.00 0.070 0.00 Safe-improvement 0.065 0.00 0.062 0.00 0.067 0.00 Reward estimator error δ=0δ=0 -0.388 1.00 Value-max 0.071 0.00 0.068 0.00 0.070 0.00 Safe-improvement 0.071 0.00 0.062 0.00 0.067 0.00 Reward estimator error δ=0.2δ=0.2 -0.388 1.00 Value-max 0.071 0.00 0.068 0.00 0.070 0.00 Safe-improvement 0.071 0.00 0.062 0.00 0.067 0.00 Reward estimator error δ=0.4δ=0.4 -0.388 1.00 Value-max 0.049 0.00 0.068 0.00 0.070 0.00 Safe-improvement 0.049 0.00 0.062 0.00 0.067 0.00 Reward estimator error δ=0.6δ=0.6 -0.388 1.00 Value-max -0.380 1.00 0.068 0.00 0.069 0.00 Safe-improvement -0.319 1.00 0.062 0.00 0.067 0.00 E.4 Selection across the range of score error Figure 12 varies the score error at a fixed reward function. Naive BoN is optimal while the score function is aligned and collapses as soon as it is exploitable, whereas every estimator-based rule has nonnegative mean gain across the tested range. DR attains the lowest regret against the optimal budget. Figure 12: Selection across the range of score error in the Synthetic experiments. Safe Improvement rule, δ=0.4δ=0.4, n=4,096n=4,096, Nmax=256N_ =256, 300300 repetitions. Left: gain over N=1N=1. Right: regret against the optimal budget on the grid, lower is better. Appendix F Extension to preference rewards Our BoN evaluation framework extends to settings in which the scalar reward encodes a pairwise preference between two model responses, as in AI alignment and RLHF. For a prompt or context X, let A=(A1,A2)A=(A_1,A_2) denote a pair of candidate responses and let Y∈0,1Y∈\0,1\ be the observed reward indicating whether the first response is preferred to the second response. Thus, Y=1Y=1 means that A1A_1 is preferred to A2A_2. We assume that the behavior comparison policy factorizes as πb(a1,a2∣x)=πb,1(a1∣x)πb,2(a2∣x). _b(a_1,a_2 x)= _b,1(a_1 x) _b,2(a_2 x). Here, πb,1 _b,1 denotes the policy from which the first candidate response is sampled, and πb,2 _b,2 denotes the policy from which the second, reference candidate response is sampled. In an RLHF application, πb,1 _b,1 could be the base, supervised fine-tuned, or previous model from which BoN samples are drawn. The policy πb,2 _b,2 is the opponent or reference policy used in the comparison. Often, the two policies are the same, so that πb,1=πb,2=πref, _b,1= _b,2= _ref, corresponding to the common design in which both candidate responses are sampled independently from the same reference model. More generally, however, the two marginals may differ, for example if the first response is sampled from a current model and the second response from a fixed baseline model. Let s⁡(x,a)s(x,a) denote the score function used for BoN selection. Given a prompt x, the BoN policy induced by πb,1 _b,1 samples A~1,…,A~N∼iidπb,1(⋅∣x) A_1,…, A_N iid _b,1(· x) and returns JN(x):=argmax1≤j≤Ns⁡(x,A~j),IN(x)|A~1,…,A~N∼Uniform⁡(JN(x)),AN⋆:=A~IN(x). gatheredJ_N(x):= argmax_1≤ j≤ Ns(x, A_j),\\ I_N(x) A_1,…, A_N (J_N(x)), A_N := A_I_N(x). gathered Ties are thus broken uniformly among maximizing sampled occurrences, including repeated responses. We denote the resulting policy by qN(⋅∣x)q_N(· x). F.1 Pairwise Win-Rate Objective In the preference-learning setting, a natural target estimand is the pairwise win rate of the BoN policy against a reference policy ρ: WN(ρ)=XA∼qN(⋅∣X),B∼ρ(⋅∣X)[μ(X,A,B)],W_N(ρ)=E_XE_A q_N(· X),\,B ρ(· X) [μ(X,A,B) ], where μ⁡(x,a,b)=ℙ⁡(Y=1∣X=x,A1=a,A2=b)μ(x,a,b)=P(Y=1 X=x,A_1=a,A_2=b) is the conditional mean reward function, here the probability that response a is preferred to response b. The reference policy ρ specifies the opponent against which the BoN policy is evaluated. A particularly convenient and practically relevant choice is ρ=πb,2.ρ= _b,2. In this case, the target asks how often a BoN response sampled from the first behavior marginal beats a response sampled from the same reference distribution that generated the second response in the logged preference data. When πb,1=πb,2=ρ=πref, _b,1= _b,2=ρ= _ref, the estimand is the probability that a BoN response beats an ordinary response sampled from the same reference model. A common modeling assumption in preference learning is the Bradley–Terry model, under which there exists a latent reward function r0(x,a)r_0(x,a) such that μ⁡(x,a,b)=σ⁡r0(x,a)−r0(x,b),μ(x,a,b)=σ\r_0(x,a)-r_0(x,b)\, where σ⁡(u)=(1+exp⁡(−u))−1σ(u)=(1+ (-u))^-1 is the logistic function. Given a sample (Xi,Ai1,Ai2,Yi)i=1n\(X_i,A_i1,A_i2,Y_i)\_i=1^n, a reward model rθr_θ can be estimated by minimizing the negative log-likelihood ℒBT(θ)= _BT(θ)= −1n∑i=1n[Yilogσrθ(Xi,Ai1)−rθ(Xi,Ai2) - 1n _i=1^n [Y_i σ\r_θ(X_i,A_i1)-r_θ(X_i,A_i2)\ +(1−Yi)logσrθ(Xi,Ai2)−rθ(Xi,Ai1)]. +(1-Y_i) σ\r_θ(X_i,A_i2)-r_θ(X_i,A_i1)\ ]. The corresponding reward function is μ^(x,a,b)=σ⁡r^(x,a)−r^(x,b). μ(x,a,b)=σ\ r(x,a)- r(x,b)\. As in Section 4.3, fitted functions are constructed independently of the evaluation data and auxiliary draws. The Bradley–Terry model is useful because it connects pairwise preferences to the reward modeling perspective common in RLHF. However, the pairwise win-rate estimand does not require the Bradley–Terry model for identification. It is identified as long as the conditional preference regression μ⁡(x,a,b)μ(x,a,b) is identified on the relevant support. F.2 Doubly Robust Estimation The target pair distribution for the win-rate estimand is qNpair(a,b∣x)=qN(a∣x)ρ(b∣x),q_N^pair(a,b x)=q_N(a x)ρ(b x), whereas the behavior pair distribution is πb(a,b∣x)=πb,1(a∣x)πb,2(b∣x). _b(a,b x)= _b,1(a x) _b,2(b x). Therefore, the pairwise density ratio is wN(x,a,b)=qN(a∣x)ρ(b∣x)πb,1(a∣x)πb,2(b∣x).w_N(x,a,b)= q_N(a x)ρ(b x) _b,1(a x) _b,2(b x). Define mN(x;ρ)=A∼qN(⋅∣x),B∼ρ(⋅∣x)[μ(x,A,B)].m_N(x;ρ)=E_A q_N(· x),\,B ρ(· x) [μ(x,A,B) ]. Then the efficient influence function for WN(ρ)W_N(ρ) in the nonparametric model for μ is ϕN(O)=mN(X,ρ)−WN(ρ)+wN(X,A1,A2)Y−μ⁡(X,A1,A2). _N(O)=m_N(X;ρ)-W_N(ρ)+w_N(X,A_1,A_2)\Y-μ(X,A_1,A_2)\. This yields the doubly robust estimator W^N(ρ)=1n∑i=1n[m^N(Xi,ρ)+w^N(Xi,Ai1,Ai2)Yi−μ^(Xi,Ai1,Ai2)]. W_N(ρ)= 1n _i=1^n [ m_N(X_i;ρ)+ w_N(X_i,A_i1,A_i2)\Y_i- μ(X_i,A_i1,A_i2)\ ]. The plug-in component can be estimated by Monte Carlo: m^N(x,ρ)=1M∑m=1Mμ^(x,A~m,N⋆,B~m), m_N(x;ρ)= 1M _m=1^M μ(x, A_m,N , B_m), where A~m,N⋆=A~m,Im,N,A~mj∼iidπb,1(⋅∣x),B~m∼ρ(⋅∣x). A_m,N = A_m,I_m,N, A_mj iid _b,1(· x), B_m ρ(· x). Here, conditional on the sampled candidates, Im,NI_m,N is drawn uniformly from argmax1≤j≤Ns⁡(x,A~mj) argmax_1≤ j≤ Ns(x, A_mj). The M terms above are independent Monte Carlo replicates, each using N candidate draws and an independent opponent draw; this is a direct Monte Carlo construction rather than the pooled estimator of Section 4.2. F.3 BoN density ratios The density ratio can be simplified using the structure of the BoN policy. Suppose qNq_N is induced by sampling N candidates independently from πb,1(⋅∣x) _b,1(· x) and selecting the response with the largest score s⁡(x,a)s(x,a). Define Fx,1−(a) F_x,1^-(a) =ℙA∼πb,1(⋅∣x)s(x,A)<s(x,a), =P_A _b,1(· x)\s(x,A)<s(x,a)\, Fx,1(a) F_x,1(a) =ℙA∼πb,1(⋅∣x)s(x,A)≤s(x,a). =P_A _b,1(· x)\s(x,A)≤ s(x,a)\. Proposition 4.1 gives, for πb,1(a∣x)>0 _b,1(a x)>0, qN(a∣x)πb,1(a∣x)=gN(Fx,1(a),Fx,1−(a)). q_N(a x) _b,1(a x)=g_N\! (F_x,1(a),F_x,1^-(a) ). Thus, wN(x,a,b)=gN(Fx,1(a),Fx,1−(a))⋅ρ⁡(b∣x)πb,2(b∣x).w_N(x,a,b)=g_N\! (F_x,1(a),F_x,1^-(a) )· ρ(b x) _b,2(b x). The strict and weak score probabilities can be estimated by Monte Carlo sampling from the first behavior marginal. Given samples A¯1,…,A¯L∼iidπb,1(⋅∣x), A_1,…, A_L iid _b,1(· x), we estimate F^x,1−(a) F_x,1^-(a) =1L∑ℓ=1Ls(x,A¯ℓ)<s(x,a), = 1L _ =1^L1\s(x, A_ )<s(x,a)\, F^x,1(a) F_x,1(a) =1L∑ℓ=1Ls(x,A¯ℓ)≤s(x,a). = 1L _ =1^L1\s(x, A_ )≤ s(x,a)\. This gives the plug-in estimate of the BoN ratio R^N(x,a)=gN(F^x,1(a),F^x,1−(a)). R_N(x,a)=g_N\! ( F_x,1(a), F_x,1^-(a) ). This plug-in ratio estimate is generally biased at finite L. The unbiased alternative is Eq. (9), applied to the first behavior marginal with M=L≥N−1M=L≥ N-1; the plug-in ratio estimate does not inherit its finite-pool unbiasedness. The resulting pairwise weight estimate is w^N(x,a,b)=R^N(x,a)⋅ρ⁡(b∣x)πb,2(b∣x). w_N(x,a,b)= R_N(x,a)· ρ(b x) _b,2(b x). A particularly important special case is ρ=πb,2.ρ= _b,2. Then the second density ratio cancels and wN(x,a,b)=qN(a∣x)πb,1(a∣x)=gN(Fx,1(a),Fx,1−(a)).w_N(x,a,b)= q_N(a x) _b,1(a x)=g_N\! (F_x,1(a),F_x,1^-(a) ). Hence the doubly robust estimator becomes W^N(πb,2)=1n∑i=1n[m^N(Xi,πb,2)+R^N(Xi,Ai1)Yi−μ^(Xi,Ai1,Ai2)]. W_N( _b,2)= 1n _i=1^n [ m_N(X_i; _b,2)+ R_N(X_i,A_i1)\Y_i- μ(X_i,A_i1,A_i2)\ ]. If, additionally, πb,1=πb,2=ρ=πref, _b,1= _b,2=ρ= _ref, then both logged responses are independent samples from the same reference model, the BoN policy is obtained by reranking samples from that same model, and the target value is WN(πref)=X,A∼qN(⋅∣X),B∼πref(⋅∣X)[μ(X,A,B)].W_N( _ref)=E_X,A q_N(· X),\,B _ref(· X) [μ(X,A,B) ]. In words, WN(πref)W_N( _ref) is the probability that a BoN response beats a standard response from the reference model. In this common case, the only density ratio required for debiasing is the BoN ratio RN(x,a)=gN(Fx,1(a),Fx,1−(a)),R_N(x,a)=g_N\! (F_x,1(a),F_x,1^-(a) ), which can be estimated using samples from the reference model alone. This extension shows that the proposed BoN evaluation approach carries over naturally to preference-learning settings. The key requirement is that the logged comparison policy factorizes, and that the first behavior marginal is the policy from which BoN candidates are sampled. If the behavior pair distribution does not factorize, then the required density ratio generally depends on the full joint distribution of (A1,A2)(A_1,A_2) and cannot be recovered from samples from the marginal policies alone.

Instant research discovery