Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis
Authors: Gholamali Aminian
Idan Shenfeld
Amir R. Asadi
Ahmad Beirami
Youssef Mroueh
Venue: ICLR 2026 Poster (2026)
Keywords: Best-of-N
Soft-best-of-N
Regret bound
Primary area: reinforcement learning
TL;DR: We study the regret and KL divergence of Best-of-N through the lens of smoothing and using Soft-best-of-N

Abstract: A simple yet effective method for inference-time alignment of generative models is Best-of-$N$ (BoN), where $N$ outcomes are sampled from a reference policy, evaluated using a proxy-reward model, and the highest-scoring one is selected.  
While prior work argues that BoN is almost optimal in reward vs KL tradeoffs, the effectiveness of BoN depends critically on the quality of the proxy-reward model used for selection. For this purpose, we study BoN through a smooth version known as Soft Best-of-N (SBoN) and develop a theoretical framework to address this gap. We analyze the scaling behaviour of BoN by providing bounds on the KL divergence between the SBoN policy and the reference policy, offering insights into how performance varies with the number of samples. We also study the regret gap, i.e., the gap between the expected true-reward under the optimal policy and the SBoN policy. Our theoretical and empirical findings show that smoothing helps SBoN mitigate reward overoptimization, especially when the quality of the proxy-reward is low.

Published as a conference paper at ICLR 2026
BEST-OF-N THROUGH THE SMOOTHING LENS: KL DIVERGENCE AND REGRET ANALYSIS
Gholamali Aminian 1:; Idan Shenfeld', Amir R. Asadi!, Ahmad Beirami, Youssef Mroueh The Alan Turing Institute, MIT, University of Cambridge, 'TBM
ABSTRACT
A simple yet effective method for inference- timeeneceeimeeeeee alignment of generative models is Best-of-N (BoN), where N outcomes are sampled from a reference policy, eval- uated using proxy-reward model, and the highest-scoring one is selected. While prior work argues that BoN almost optimal in reward vs KI. tradeoffs, the ef- fectiveness of BoN depends critically on the quality of the proxy-reward model used for selection. For this purpose, we study BoN through a smooth version known as Soft Best-of-N (SBoN) and develop a theoretical framework to address this gap. We analyze the scaling behavior of BoN by providing bounds on the KL divergence between the SBoN policy and the reference policy, offering insights into how performance varies with the number of samples. We also study the re- gret gap, i.e., the gap between the expected true-reward under the optimal policy and the SBoN policy. Our theoretical and empirical findings show that smoothing helps SBoN mitigate reward overoptimization, especially when the quality of the proxy-reward is low.
INTRODUCTION
Large language models (LLMs) have transformed machine learning, achieving state-of-the-art re- sults on variety of tasks. Despite all advancements, LLMs can still generate undesirable outputs, such as toxic or factually incorrect responses. This has made alignment a central goal in modern LLM development (Achiam et al., 2023; Team al., 2023).
Several post-hoe alignment methods have been proposed to address this challenge, including Rein- forcement Learning from Human Feedback (RLHF) (Christiano et al., 2017: Ouyang al., 2022), SLiC (Zhao et al., 2022), Direct Preference Optimization (Rafailov et al., 2023), controlled decoding (Mudgal al., 2024) and Best-of-N (BoN) sampling (Stiennon al., 2020). While these methods differ in their implementation, which range from training-time optimization to test-time selection, they can be viewed as approximating the solution to KL-regularized reward maximization problem. The optimal solution to this problem is a tilted distribution over responses, which balances reward and proximity the reference model (Yang et al., 2024).
In BoN as test- timt-time sampling strategy, given a prompt, N responses are sampled from the reference policy, and the one with the highest proxy-reward sample is selected. Empirically, BoN has been shown to achieve competitive or superior performance in the reward-versus-Ki KL. divergence trade-off when compared
RLHF and other alignment methods (Gao et al., 2023a; Mudgal al., 2024) under true-reward model. Furthermore, under certain conditions, it asymptotically approximates the solution to the KL-regularized reward maximization objective (Yang et al., 2024). However, in practice, BoN relies on learned proxy-ret proxy-reward model, which is approximation of the true- reward function, to guide this selection. As such, their effectiveness critically depends on both the proxy-reward model (estimation error of true-reward) and the quality of the reference policy.
Understanding how these two components, the quality of the proxy-reward model and the choice of reference policy, affect the alignment quality of test-time sampling algorithms is essential. There are different measures of alignment quality, including KL divergence between aligned policy and ref-
Corresponding author: gaminian @ turing.ac.uk uk
Unless stated otherwise, all KI. divergences understood to be measured between the aligned policy and the reference policy.

---

Published as a conference paper at ICLR 2026
erence policy and the regret defined as the gap between the expected true-reward under the optimal (tilted) policy and the alignment policy. Note that minimizing the regret gap is critical to ensuring high-quality outputs and close performance to the optimal policy. Recent work by Gao et al. (2023a) and Hilton et al. (2022) has investigated the scaling laws governing reward model optimization in both reinforcement learning (RL) and BoN settings function of KI. divergence hetween aligned policy and reference policy. They empirically demonstrate that, under proxy-reward models, the improvement in expected true-reward, relative reference policy, scales proportionally for both RL and BoN policies.
While recent work analyzes BoN under the idealized settings where there is no discrepancy between the proxy-reward and the true-reward (Yang et al., 2024; Beirami et al., 2024; Mrouch, 2024; Huang et al., 2025), our work relaxes this assumption to study the interplay between the reward discrepancy measured through regret and the KT.-divergence. We present a theoretical study of Soft Best-of-N (SBoN), a smoothed variant of BoN recently introduced by Mayrink Verdun et al. (2025); Jinnai et al. (2024). Unlike BoN, SBoN draws the final response probabilistically from the N candidates, yielding policy that is tunable with a inverse temperature parameter. Our analysis centres on two metries:
(a) the Kullback-Leible divergence between SBoN policy (under the true reward or proxy- reward model) and the reference policy, and
(b) the regret, i.e. the expected true-reward gap between optimal policy and SBoN policy.
We show how these results specialize to the BoN (as limit of SBoN for the inverse temperature goes to infinity) and quantify the estimation error incurred by using a proxy reward model instead of the true-reward. Finally, we characterize regimes in which SBoN attains lower regret bound than BoN when we use the proxy-reward model. Our main contributions are:
We derive finite-sample upper bounds for KL divergence between the SBoN policy and ref- erence policy, and upper and lower bounds for the regret gap of the SBoN policy. Further- more, we extend these bounds to BoN, These bounds reveal how the number of responses N. proxy-reward model quality, and reference policy model affect performance.
We quantify cases where SBoN performs better than BoN under overoptimization see- nario where the proxy-reward model is used instead of the true-reward model.
We provide experimental validation using various proxy-reward models to demonstrate SBoN's advantages in the overoptimization scenario. Furthermore, we provide numerical experiments to evaluate our bounds.
2 RELATED WORKS
In this section, we discuss related works on BoN, the theoretical foundation of (Soft) BoN, and overoptimization. More related works for the theoretical foundation of RLHF and smoothing of maximum are provided in the Appendix (App) B.
Despite many recent advancements in alignment, simple, popular, and well-perf method continues to be the BoN policy (Nakano et al., 2021; Stiennon et al., 2020; Beirami et al., 2024). In fact, Gao et al. (2023b); Mudgal et al. (2024); Eisenstein al. show that BoN consistently achieves compelling win rate-KL tradeoff curves, often outperforming KL-regularized reinforce- ment learning and other more complex alignment strategies. LLaMA 2 (Touvron al., 2023) lever- ages BoN outputs as teacher signals to further finetune the base model. Mudgal et al. (2024) extend BoN through Q-learning to block-wise wise BoN decoding. This empirical effectiveness has also inspired research into distilling BoN behavior into standalone models (Amini et al., 2025; Sessa et al., 2024; Qiu et al., 2024). Hughes et al. (2024) utilize BoN as an effective method for jailbreaking, while BoN is also commonly used
Best-of-N:
strong baseline for scaling inference-time compute (Brown et al., 2024; Snell et al., 2024). Given the broad success of BoN, we are motivated to theoretically investi- gate the BoN policies and the effect of the proxy proxy-reward reward model (reward hacking) and the quality of the reference policy.
Theoretical Foundation of (Soft) BoN: KL divergence of BoN is studied in (Beirami al., 2024; Mrouch, 2024) via information theoretical tools, where the KL divergence of BoN sampling from the reference distribution is bounded by log(N) N) (N 1)/N. Scaling laws governing reward
2

---

Published as a conference paper at ICLR 2026
function of KL divergence is empirically studied by Gao et al. (2023b) and theoretically for- malized by Mrouch (2024). Furthermore, the asymptotic case and the equivalence of BoN to the KL-constrained reinforcement learning solution are studied by Yang et al. (2024) under the assump- tion of access to optimal reward. Gui et al. (2024) further characterized the win rate-KI. gap in the asymptotic regime where model assigns extremely low likelihoods to successful completions. Furthermore, Sun et al. (2024) accelerated BoN using speculative rejection sampling. The regret of BoN under some assumptions is studied in (Huang et al., 2025). The convergence rate of the SBoN policy to the optimal tilted policy has been analyzed by Mayrink Verdun et al. (2025). Additionally, Geuter et al. (2025) investigate a variant of SBoN that incorporates speculative samples from a small auxiliary model, providing both theoretical and empirical insights. However, the regret gap and KL divergence of SBoN under the overoptimization scenario remain largely unexplored in the existing literature.
PROBLEM FORMULATION
Notations: Upper-case letters denote random variables (e.g., Z), lower-case letters denote the re- alizations of random variables (e.g.. z), and calligraphic letters denote sets (e.g.. 2). All loga- rithms are the natural base. The set probability distributions (measures) over a space X' with finite variance is denoted by P(X).. Ay is N N-simplex distribution set. The KL divergence be- tween two probability distributions on R" with densities p(x) and q(z), such that q(x) > when p(z)= >> 0, is KL [9) == SR= p(z) log(p(z)/q(z)))
(with O. log 0 == 0). The total-variation dis- tance is defined as TV(,, q) 1 fx (p(x) ((x)). Furthermore, define chi-square divergence as x" (p(())))((()) fxx (x) 1. a(xr)
Preliminaries: Let the finite set of prompts be X' and the discrete finite set of responses be V. Prompts are drawn from a distribution p over X. (stochastic) policy æ E Il assigns, for every prompt E X' conditional distribution x(- æ) over Y; drawing y~*r(- 2)) yields response. We treat the supervised supervised-fine-tueeee fine-tuned (SFT) model as a reference policy, denoted Tre((- x).
3.1 REWARD FUNCTION
We consider a (calibrated) true-reward function r"(y, x) and a (calibrated) proxy-reward function F(y,2), both mapping )' x X' - [0, 1). Throughout the rest of this paper, we assume all reward functions are calibrated (see App. C). For brevity, we refer to them simply as reward functions. functioosss The true-reward function is estimated via proxy-reward function f(y, x) using some preference datasets 3, As shown by Balashankar et al. (2025), a calibrated reward function satisfies,
Boundedness: for all x, y. we have f(y,x), (1, E [0, I].
Uniformity under the reference model: for each prompt a E Xf Feel( | |x) then r(y,z) ~ Unif(0, 1) for {f, r.
In practice, the proxy-reward model can be fit to a human-labeled preference dataset data annotated with true-rewards. Following (Huang et al., 2025), we assume for simplicity that f(y.z) given. We define yT (x) arg max, y" (y, 2) as the of maximizers for true-reward. Similarly, we can define (x) as the set of maximizers for proxy proxy-reward model. More discussion regarding reward is provided in App. C.
Assumption 3.1 (Achievable maximum reward). We assume that for E (f,r*) we have ((((x),))= = = ffr all ((x) E arg max, r(y, x) and given x E X.
In many settings, the reward function attains its maximum at specific responses. In particular, since large language model (LLM) generates outputs using a finite vocabulary and a bounded number of tokens, the space possible generations is finite, and thus the assumption holds trivially.
For mncasure-theoretic simplicity and notational convenience, assume finiteness for the set of prompts. Our results also hold for non-finite set.
In some cases, the reward model is not derived from human preference data. Instead, it is either determin- istic (e.g., code exccution scores) or provided by an automated classifier (e.g., for toxicity sentiment).
3

---

Published as a conference paper at ICLR 2026
3.2 SBoN ALGORITHM
Fix a prompt & E A' and draw N i..dd candidates YI.N Troe(: x). Let Z E {l,..., N) denote the index of the selected response with distribution Pz; write Pz(i) Pr(Z i). We seek distribution over indices that maximizes the proxy-reward:
max Ez PEEAN
Ez (z(((222))
Without regularization, the optimizer is the deterministic Best-of-N (BoN) rule Pz = 6G- with arg max; =)) Because f is a proxy for the true-reward, this deterministic choice can overoptimize the proxy-reward and get response with lower true-reward. To smooth this, we add an entropy penalty with inverse temperature 3 >
1
max Ez 22(1(22 + H(Pz).
PZEAN
B
exp(sr(M..))
The unique solution is the softmax distribution, Pz(i) = E (()),.))
We then sample Z from this distribution and return Yz. We refer to this sampling rule as Soft-BoN, as introduced by Mayrink Verdun et al. (2025). Note that the value of 3 parameter for SBoN is equal to 3 in tilted optimal policy. shown by Mayrink Verdun et (2025), the SBoN policy can be interpreted finite-sample approximation of the tilted optimal policy.
We denote the final policy from SBoN via nf SBoN (ylæ). Note that for 3 + oo and - -oc, we recover BoN and worst-of-N (WoN) (Balashankar et al., 2025), respectively. Furthermore, for 3 + 0, we recover uniform sampling among the N response samples, which equivalent to sampling from the reference model (eer(y)z)) In (Mayrink Verdun et al., 2025, Lemma 1), the closed form solution of SBoN policy is derived,
SBoN (ulo) Tret(y/z)) exp(3f(y, x))
ZN
where Zn.s = E ( (exp((r(x))))) + Σ exp((F(Y),)))))) T.
(
Similarly, can define TBBo (y)x) based true-reward model. For simplicity, define BoN policies under true-reward and proxy-reward models as BBBN (y|x) and π. BoN (y|z), respectively. In this work, focus on 3 2 0. Another motivation for SBoN based on the Gumbel-Max trick is provided in App.
3.3 OPTIMAL (TILTED) POLICY
For given inverse temperature 0, seek policy that remains close wee while maximizing expected true-reward, leading to the KL-regularized objective
max Ey [I (y. x)] - 3 KL(T(- |x) Trer(- x)). Well
(2)
The unique solution is the optimal tilted policy (Korbak et al., 2022b;a; Yang al., 2024)
Tz (v(x) = Teorly x) r
Z, v (x,
where (x, EyEy (vr x) exp(3 r" (pp(3r")u (y, x)), is the normalizing (partition) function.
Note that, in practice, we do not have access to the closed form of reference pol- icy (re(( and r* (y, We can only first estimate the true-reward function via proxy-reward function f(y, x)) and then sample from (y(() and compute F(y,)) for each individual sample. Finally,
apply inference-time algorithms, e.g., BoN or SBoN (Mayrink Verdun et al., 2025), where N samples are generated from (v(()) and choose the sample with the highest proxy-reward function (BoN) sampled from distribution (SBoN) using the proxy-reward function. When only a proxy-reward function f(y, 2)) is available, obtain the analogous partition function Zz, (x, 3) and policy Tg
4

---

Published as a conference paper at ICLR 2026
(y
We can also define the optimal policy under the true-reward model as,
Ta.( Tilted optimal policcy
Thc T-l
Opinal policy
(ular) arg max By (+w))) (r x)
oc
Similarly, we can define m. (y/z) the optimal policy under the proxy-reward model".
N - 00
As the reward functions (true and proxy) are bounded due to calibration, we can interpret op- timal policies as the limit of tilted optimal poli- cies for rf.
2008 (2 SBoN policy
3-
M [20))) BoN policy
Figure 1: cies under reward model r E {*,
Connections of different poli-
T-o,-(11z)
lim T3,r(-12) 8-000
where r (-1z) and of place all their probability mass on the maximizers of r* (v, x)) and f(y, z), respectively. The connections between SBoN, BoN, optimal and optimal tilted policies under true or proxy-reward models are shown in Figure 1.
3.4 TILTED ERROR
Let's define the tilted error the tilted average of square estimation error of true-reward function for a given prompt a with parameter / as follows,
E (x) 3 log (Ey
To simplify notation, we adopt the same smoothing parameter /3 for the error definition as is used in the KL and tilted cases. A similar definition of estimation error is introduced in (Yang & Wiibisnoo 2022). When 3 0, the definition reduces to the mean-squared error, which is also introduced in (Huang et al., 2025). Letting 3 -> oo recovers the square of the supremum (infinity) norm (l) lloo) of the estimation error between r" (", x) and 2yy, Therefore, the following properties hold for ggrr
The tilted error is bounded, i.e., (x) E [0, 1].
The tilted average of the estimation error is monotonically increasing in B.
(z) == lim (x) = |r - f(Y,
We assume that overoptimization regime happens whenever we have (x) 0. In more details, (x) > O indicates reward misspecification. As noted in Gao et al. (2023b), misspecification is necessary precondition for overoptimization, but overoptimization itself refers the specific regime where the optimization strength is sufficiently high that the degradation due to error outweighs the improvement the proxy-reward.
We define tilted error using (proxy and true) reward models rather than raw reward models, because our focus on how rankings change under the proxy. For example, the proxy-reward a strictly increasing transform of the true-reward, the ranking is preserved; the Best-of-N (BoN) policy re- mains optimal and no overoptimization occurs. This behavior cannot be captured when working with the raw (uncalibrated) reward models. Note that in (Huang et al., 2025), raw (uncalibrated) reward models are utilized for error definition.
3.5 COVERAGE
For a given reward function r(z, y), we define the tilted policy (softmax policy);
n (y) (ar) o [yf(()))) xx)))r(y.x))..
"This policy, ()(a)) maximizes fcr it may be suboptimal or harmful under r" due to Goodhart's Law Gao al. (2023b).
5

---

Published as a conference paper at ICLR 2026
Then, introduce the coverage of tilted policy with respect the reference policy as,
(vlzx)
Ca.r(x) =
(5)
Jref (y/z²)
wcy
also define,
(x)) = lim Car( 3-000
This measure (z. can also be interpreted as a coverage constant, which is standard in KL-regularized policy learning. Furthermore, we can define the coverage of the tilted pol- icy with respect to the reference policy as x²-divergence between (z.r(y/z) and Tret (v(a), i.c., It ensures that the reference policy places sufficient probability mass on high-reward responses, thereby guaranteeing that the support of the optimal policy lies within the support of the reference. This prevents cases where optimal outputs are entirely excluded by the reference. Similar notions of coverage have been explored Huang et (2025).
3.6 REGRET
For given policy π (Y (2), we define expected true-reward with respect to the policy (a.k.a. value function") as
J,. (T( [z)) = E. (-xe(= (V,
(6)
For two policies, Tí (1(x)) and (2(+1z), we define the gap between these two policies as follows,
Jr (m (+1x), (+(ar) == Jpm (-1x)) J,, (+)((+))))
We provide an upper bound on the gap of the SBoN solution, which is the gap between प,द. (. (z)) as the optimal policy and SBoN (-|z),
J.,- (ITz (- |x)), म.
SBoN (+1z)) J, (TT (-1x)) J,- (मद (T. (-|z)).
Regarding regret of the BoN, we consider n.BoN (-|xr instead of TT. SBBNN (-|x) in equation 8
4 KL DIVERGENCE ANALYSIS
The KL divergence between the aligned policy and the reference policy, KL [[tee). is studied by Beirami et al. (2024); Mrouch (2024) from a theoretical perspective. In particular, Beirami al. (2024) derives an upper bound on KI. divergence for BoN policies under the assumptions of bijective true-reward mapping and a finite output space:
(T, BoN (-Ix)) [-)x())))) < log(N) - + N
Mrouch (2024) relaxes the bijectivity assumption and derives similar bounds using information- theoretic tools. Under some assumptions, the bound in equation is tight. Furthermore, using Pinsker's inequality, in similar approach to (Mroueh, 2024), we have,
By By ( (" (Y, 0.5 + KT SBON (eaa)))
(10)
Note that equation 10 implies that improvement of expected true-reward relative to the reference policy cannot exceed the square root of the KL divergence. However, the analysis of KL divergence for the SBoN policy under the true-reward model is overlooked. Therefore, we first establish an upper bound the KL divergence between the SBoN policy under the true-reward model and the reference policy, shedding light on its behavior as a function of the number of samples N and inverse temperature parameter B. All proof details are deferred App. G.
'We can also consider Ex [Je- (T(-) All of our results also hold for expected version of value function.

---

Published as a conference paper at ICLR 2026
Lemma 4.1. The following upper bound holds KL divergence between SBoN and reference policies for a given prompt x E Æ.
KL ST. [ (y/z)) & log 1+ (N 1) exp( -
(11)
Using Lemma 4.1, we can observe that for BoN, 3 + co, we have,
(L (TTTBBBo (y]xr)] (w|xx) S log(N).
(12)
Comparing equation 12 with results in (Beirami al., 2024; Mrouch, 2024), result is derived from the SBoN asymptotic regime. Note that our bound looser than the bound on KL divergence in equation 9. In contrast, our bound is general and can be applied to different / in SBoN. For / 0, where our policy is the reference policy, our bound is tight. is also important to note that the upper bound in Lemma 4.1 increases with the inverse temperature parameter 3 for fixed N.
Recent works by Gao et al. (2023a) and Hilton et al. (2022) empirically demonstrate that, under a true-reward model, the improvement in expected true-reward, relative to reference policy, scales ap- proximately proportionally to / (T NoN [Teet) for both RL and BoN policies. It is also observed by Gao et al. (2023b) that models optimized using proxy-rewards can suffer from overoptimization where the learned policy diverges further from the reference, the alignment may degrade. Despite theoretical advances, the KI. divergence analysis for SBoN and BoN under the proxy-reward model remains largely unexplored. Therefore, we are interested in investigating the cost we have for esti- mation error of true-reward via proxy-reward model. For this aim, we first propose the following useful Lemma to study the closeness of the SBoN policy under the true-reward model to the SBoN policy under the proxy-reward model in KL divergence measure. Lemma 4.2.
The following upper bound holds on the KI. divergence between the SBoN policies under rew-re and proxy-reward models respectively,
N3 (EB. KL(T,BON (-1z) SBoN (-1=)) 1+ (N exp(((3) (N 1)² + +1).
N eexp(2
(13)
Note that for 8 O, the upper bound in Lemma 4.2 is tight. The result Lemma 4.2 quantifies the estimation error introduced by substituting a proxy-reward model for the true-reward model.
Next, we compare BoN and SBoN under overoptimization from KL-divergence perspective.
Remark 4.3 (No overoptimization). We can observe that for given B, if we assume (x) 0, we have KL(T (- (x) (ITT) expected true-reward under the aligned policy, relative to the reference policy, proportional the square root of KI. divergence. Then larger KL. divergence is desirable in this context, as proposed by (Gao et al., 2023b), the BoN policy preferred under no overoptimization scenario.
= O. Note that, as mentioned in (Gao et al., 2023b), the
Remark 4.4 (Overoptimization). When (z)r(z) O, we have two conflicting goals in both Lemma 4.1 and Lemma 4.2: one suggesting for fixed N that 3 needs to smaller for better es- timation of the true policy by the proxy-reward model one given in Lemma 4.2, and another one suggesting a larger 3 to induce a better KL trade-off based on Gao et al. (2023b). Hence, for a given N, there exists optimal 3 to balance between the estimation error of Lemma 4.2 and the scaling law under the SBoN policy for the true-reward model, Lemma 4.1. In this scenario, SBoN can lead better tradeoffs than BoN. A similar discussion can be done for fixed 3 and varying N. Further analysis using reverse I-projection ( (Csiszár & Matus, 2003) in large N regime is provided in App. K.
REGRET ANALYSIS
In this section, derive theoretical regret bounds, upper and lower bounds, for SBoN and BoN based on reward models. First, we provide a helpful Lemma regarding the expected coverage as- sumption that help us interpret the results of regret for BoN and SBoN. All proof details deferred to App. H. Lemma 5.1. Under Assumption 3.1, it holds that (0) E, (x) where max (x) arg max, r(y,
7

---

Published as a conference paper at ICLR 2026
5.1 UPPER BOUND ON REGRET
Now, we derive an upper bound on the regret of SBoN.
Theorem 5.2 (Upper Bound on Regret of SBoN). Under Assumption 3.1, the following upper bound holds on the optimal regret gap of the SBoN policy for any 0,
Je ( (. (20), 28
SBoN (-1z)) Veg.( (oo. hooll+/Coooo (xo,(())
+ 2V log (1+ Coo,((x) -) + (o, (x))
2
N
B
Regret Bound of BoN Through Smoothing Lens: We now derive an upper bound on the regret of BoN by taking the asymptotic limit of the regret bound regret of SBoN in Theorem 5.2.
Proposition 5.3 (Upper Bound Regret of BoN). Under Assumption 3.1, the following upper bound holds on the optimal regret gap of the BoN policy for any 8 >> O,
J (-12()11),, BoN (112)) S (V) + / (oom)()))
1 +2 2 log (1+ (oos(x)-11
/
N
Remark 5.4 (Comparison with (Huang et al., 2025)). The regret bound for BoN policy grows with the Liso norm of the reward-model estimation error. In contrast the result in (Huang et al., 2025), our bound remains finite whenever the overoptimization error vanishes, iee. when (x),(()) = O or N grows. We also derive results based calibrated reward, instead of raw (uncalibrated) reward models. A full comparison with Huang et al. (2025) is provided in App.
Overoptimization (asymptotic regime): Assume that (3,((x) > 0 for every B > Letting
N 0o and invoking Theorem 5.2, we obtain
(T, ( ()) म. SBBN (. (.1x)) S log Coo,r (x)
(14)
+ VeBr(()) (v Cx. + (oo
Similarly, for BoN we have,
(T, (:1 x). ग. BoN [x)) S (xx)(()) (VCo.((t) + (x))
(15)
No overoptimization: Assume that the overoptimization vanishes, i.e. (B,((x) 0 for every B E [0, oo). Then the optimality gaps of the SBoN and BoN policies satisfy
Coo,((a)-1) N
log Coo (x)
AT, (. x), nT
SBBN ( x)) < 2 2
log 1 1
+
(16)
Coc,
AT, (. x)), up BaN x))
S 22 log
1 1+
(17)
2
N
5.2 LOWER BOUND ON REGRET
In this section, we complement the regret upper bounds (Theorem 5.2 and Proposition 5.3) with lower bounds that hold for any finite N and fixed 3 2 0. For the lower bound, the following assumptions are needed.
Assumption 5.5 (Margin Assumption). Let 7(x) = 1 -up puppesssco (y. We assume that (xx) 1).
Note that Assumption 5.5 for strictly positive lower bound needed.
8

---

Published as a conference paper at ICLR 2026
0.83
Hamreeees 20000 (Nammakood)
0.52
0.80
3-236.2
0.70
Boht
0.85
0.80
0.49
0.55
1222
0.68
Figure 2: Soft Best-of-N experiment using strong reward model (Left) and weak one (Right). Number of samples versus Harmlessness score (higher better). When the performance of the reward model is poor, BoN can lead to overoptimization, while the SBoN can help to mitigate it.
Theorem 5.6 (Lower Bound on Regret of SBoN). Under the same Assumptions in Theorem 5.2 and Lemma H.3, the following lower bound holds on the regret of SBoN policy under the proxy-reward model,
A (xt) (-1x), SBoN (-1x))
7(x) (1 Co., (2) N((1 Coo,r (x)-)))
(20
N (exp(3) 1)(N 1)
(18)
min (V1-exp)) exp (-U(N.8)) 1+ (N eexp(=3) (())(())
N
where U(N,8) T+(N 1)oxp( 11x[-=))xp(-P (8)
(3
N 22xp(22)
+1)
I1-
Using similar approach to Proposition 5.3, we can derive the lower bound on regret of the BoN policy through the lens of smoothing.
Proposition 5.7 (Lower Bound on Regret of BoN). Under the same assumptions in Theorem 5.6, the following lower bound holds on regret of BoN policy,
J (मς (-12), BoN (+x)) 2 (xx)(1 Coo,r (x)-1)N min(1, (x),
(19)
Under overoptimization (x) 0), due (1 (x) expl (xp(o,,,()-)))) the lower bound on regret of BoN is ((exp(-N))))) Furthermore, in App. 1.2, we present a numerical example illustrate the positivity of the lower bounds under certain conditions.
5.3 DISCUSSION
This section analyzes the performance of BoN and SBoN in the presence and absence of overopti- mization.
Remark 5.8 (Overoptimizaaiion) Considering the upper bounds in equation 14 and equation 15, define,
g(3) = BB(V 6oo -aae)-Vea.rro (x).
B20 0.
Because g(0) = g(00) and g(B) 2 0 for all 3, there exists at least one maximizer 3* E (0, 00)
such that g(3*) max g
If log Con.ne (x)
S g(3*), then the upper bound in equation 14 does not exceed equation 15,
and hence the bound on the regret of the SBoN policy is tighter than the bound on the regret of the BoN policy under the proxy-reward model. An analogous comparison can be carried out for any fixed 3 and changing N. A numerical example for the existence of optimal B based on this approach provided App. 1.2.
Remark 5.9 (No overoptimization). By Lemma 5.1, (z)) 1; consequently. the bound in equation 17 is tighter than the bound in equation 16. Similar discussion can be provided for lower bound.

---

Published as a conference paper at ICLR 2026
Remark 5.10 (Quality of reference policy). The upper bounds in Proposition 5.3 (or Theorem 5.2) depend on two quantities.
C (2)
and (z,,((x)= Ei Trof (ii (x) x)
Ei Traf (Vir
maa
x)
which represent its quality under the true- true-reward model and proxy- proxy-reward reward model, respectively. A larger value for these quantities implies that the reference model rarely generates optimal responses, thereby degrading performance. We can observe that upper bounds increase by increasing Coo, (2) and Cra.t (2))
EXPERIMENTS
To support theoretical analysis, conducted experiments comparing Soft Best-of-N (SBoN) across different regularization strengths and reward model qualities. We used the Olmo-2 IB model (OLMo al., 2024) as the generator and prompts from the Attaq dataset (Kour et al., 2023). For each prompt, we generated multiple responses and selected one using SBoN with varying inverse temperature values B. We ran two experimental conditions: one using a strong proxy-reward model (AmoRM 8B (Wang et al., 2024)) which is close to true-reward model, and another using weaker proxy-reward model (Beaver 7B RM (Dai et al., 2023)). use LLM--ssa-Judge Zheng et al. (2023) as our r* To match our theoretical setting, we perform empirical calibration of each reward model by sampling 256 responses for every query and calculate the quantiles. As shown in Figure 2, when the reward model is weak, performance degrades for large N due to reward hacking. However, the smoothing in SBoN helps mitigate this degradation. This observation also aligned with our theoretical analysis and discussion in Section where under overoptimization there exists for given N which outperforms BoN. For more details, see App. I. We also studied the behavior of our upper bound on the KL divergence between the SBoN policy and the reference policy, Lemma 4.1, in App. I.2. More experiments with a medium weak reward model are provided in App. I.1.
CONCLUSION AND FUTURE WORK
In this work, establish theoretical foundation for alignment strategies based on Soft Best-of-N (SBoN) and Best-of-N (BoN) policies. Specifically, we derive upper bounds on the KL divergence between the aligned policy such as SBoN or BoN and the reference policy. We also studied the regret gap between the optimal policy and the aligned policy, c.g., BoN and SBoN policies. We further analyze how errors reward estimation affect performance both KL divergence and regret gap. Notably, both our theoretical analysis and empirical results demonstrate that, under proxy-reward model where overoptimization happens, SBoN performs better than BoN under some conditions.
Existing literature Beirami et al. (2024); Mroueh (2024), suggests tighter upper bound on the KI. divergence for BoN policy. Our derived result, however, provides looser bound for BoN. Consequently, an interesting direction for future research is the derivation of an upper bound that is asymptotically tight for the BoN policy. Furthermore, while our current analysis utilizes a shared for both the tilted error and the SBoN policy, exploring decoupled inverse temperature parameters for these components remains promising avenue for future study.
ACKNOWLEDGMENT
Gholamali Aminian acknowledges the support of the UKRI Prosperity Partnership Scheme (FAIR) under EPSRC Grant EP/V056883/1 and the Alan Turing Institute. Amir R. Asadi is supported by Leverhulme Trust grant ECF-2023-189 and Isaac Newton Trust grant 23.08(b).
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08777 2023.
Afra Amini, Tim Vieira, Elliott Ash, and Ryan Cotterell. Variational best-of-n alignment. In Inter- national Conference on Learning Representations (ICLR), 2025.
Gholamali Aminian, Amir R. Asadi, Idan Shenfeld, and Youssef Mroueh. KL-regularized RLHF with multiple reference models: Exact solutions and sample complexity. In The Thirty- ninth Annual Conference Neural Information Processing Systems, 2025. URL https:
/poonrreview net wttp://www.eeefoo/iiiieeeeee Forummid=j8xnFFFF FFVXFF
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Con- crete problems in ai safety. arXiv preprint arXiv: 06565, 2016.
Ananth Balashankar, Ziteng Sun, Jonathan Berant, Jacob Eisenstein, Michael Collins, Adrian Hutter, Jong Lee, Chirag Nagpal, Flavien Prost, Aradhana Sinha, Ananda Theertha Suresh, and Ahmad Beirami. Infalign: Inference-aware language model alignment. International Conference on Machine Learning (ICML), 2025.
Armin Behnamnia, Gholamali Aminian, Alireza Aghaei, Chengehun Shi, Vincent Tan, and Hamid R Rabiee. Log-sum-exppa exponential estimator for off-policy evaluation and learning. In International Conference Machine Learning, pp. 3393 3472. PMLR, 2025.
Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D' Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees on the best-of-n alignment policy. International Conference Machine Learning (ICMI., 2024.
Vivek S Borkar. Q-learning for risk-sensitive control. Mathematics of Operations Research, 2002.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.2178)) 2024.
Clément L Canonne. A short note on an inequality between kl and tv. arXiv preprint arXiv:2202.07198, 2022.
Pierre Cardaliaguet, François Delarue, Jean-Michel Lasry, and Pierre-Louis Lions. The master equation and the convergence problem in mean field games:(ams-200) Princeton University Press, 2019.
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:2307.15217, 2023.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing sys- tems, 30, 2017.
Thomas Coste, Usman Anwar, Robert Kirk, and David Krueger. Reward model ensembles help mitigate overoptimization. In The Twelfth International Conference Learning Representations.
Imre Csiszár and Frantisek Matus. Information projections revisited. IEEE Transactions on Infor- mation Theory, 49(6): 1744119944 2003.
Josef Dai, Xuehai Pan, Ruiyang Sun, Jiaming Ji, Xinbo Xu, Mickel Liu, Yizhou Wang, and Yaodong Yang. Safe rlhf: Safe reinforcement learning from human feedback. arXiv preprint 100 12773, 2023.
11

---

Published as a conference paper at ICLR 2026
Jacob Eisenstein, Chirag Nagpal, Alekh Agarwal, Ahmad Beirami, Alexander Nicholas D' A'mour, Krishnamurthy Dj Dvijotham, Adam Fisch, Katherine A Heller, Stephen Robert Pfohl, Deepak Ramachandran, et al. Helping herding? reward model ensembles mitigate but do not eliminate reward hacking. In First Conference on Language Modeling.
L Gao, J Tow, B Abbasi, S Biderman, Black, A DiPofi, C Foster, L Golding, Hsu, A Le Noach, et al. A framework for few-shot language model evaluation. URL. https:/zeeodo. org/records/10256836 7, 2023a.
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference Machine Learning, pp- 10835-10866 PMLR, 2023b.
Jonathan Geuter, Youssef Mroueh, and David Alvarez-Melis. Guided speculative inference for effi- cient test-time alignment of lims. arXiv preprint arXiv:2506.0411 18, 2025.
Lin Gui, Cristina Gârbacea, and Victor Veitch. Bonbon alignment for large language models and the sweetness of best-of-n sampling. arXiv preprint arXiv:2406.0088 000022000000,, 2024.
Emil Julius Gumbel. Statistical theory of extreme values and some practical applications. Nat. Bur. Standards Appl. Math. Ser: 33, 1954.
J. Hilton, P. Clark, et al. Measuring goodharts law: Towards an evaluation framework for open-ended generative models. https: /tttt::://pppaiii./// 2022. Accessed: 2025-01-30.
/oppappnaa...m///oo http:/indx//measuueee goodhart -aw,
Ronald Howard and James E Matheson. Risk-sensitive markov decision processes. Management science, 1972.
Audrey Huang, Adam Block, Qinghua Liu, Nan Jiang. Dylan Foster, and Akshay Krishnamurthy. Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment. arXiv preprint arXiv:2503.2 1878, 2025.
John Hughes, Sara Price, Aengus Lynch, Rylan Schaeffer, Fazl Barez, Sanmi Koyejo, Henry Sleight, Erik Jones, Ethan Perez, and Mrinank Sharma. Best-of-n jailbreaking. arXiv preprint arXiv:2412.03556, 2024.
Yuki Ichihara, Yuu Jinnai, Tetsuro Morimura, Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Eiji Uchibe. Evaluation of best-of-n sampling strategies for language model alignment. Transactions on Machine Learning Research.
Hamish Ivison, Yizhong Wang, Jiacheng Liu, Zeqiu Wu, Valentina Pyatkin, Nathan Lambert, Noah A Smith, Yejin Choi, and Hanna Hajishirzi. Unpacking dpo and ppo: Disentangling best practices for learning from preference feedback. Advances in neural information processing sys- fems, 37:36602-36633, 2024.
Yuu Jinnai, Tetsuro Morimura, Kaito Ariu, and Kenshi Abe. Regularized best-of-n sampling to mitigate reward hacking for language model alignment. In ICML 2024 Workshop on Models of Human Feedback for Al Alignment, 2024.
Hadi Khalaf, Claudio Mayrink Verdun, Alex Oesterling, Himabindu Lakkaraju, and Flavio du Pin Calmon. Inference-time reward hacking in large language models. arXiv preprint arXiv:2506.1 19248, 2025.
Maxim Khanov, Jirayu Burapacheep, and Yixuan Li. Args: Alignment reward guided search. arXiv preprint arXiv:2402.0169) 2024.
Tomasz Korbak. Hady Elsahar, Germán Kruszewski, and Mare Dymetman. On reinforcement learn- ing and distribution matching for fine-tuning language models with no catastrophic forgetting. Advances in Neural Information Processing Systems, 35:16203-16220. 2022a.
Tomasz Korbak, Ethan Perez, and Christopher L Buckley. RI with penalties is better viewed as bayesian inference. arXiv preprint arXiv:2205.1 /275, 2022b.
12

---

Published as a conference paper at ICLR 2026
Barry W Kort and Dimitri P Bertsekas. A new penalty function method for constrained minimization. In IEEE Conference on Decision and Control and 11th Symposium on Adaptive Processes, 1972.
George Kour, Marcel Zalmanovici, Naama Zwerdling, Esther Goldbraich, Ora Nova Fandina, Ateret Anaby-Tavor, Orna Raz, and Eitan Farchi. Unveiling safety vulnerabilities of large language models. arXiv preprint arXiv:231 1.04124, 2023.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. On tilted losses in machine learning: Theory and applications. Journal of Machine Learning Research, 24 (4(14))11799 2023.
Guan-Horng Liu and Evangelos Theodorou. Deep learning theory review: optimal control and dynamical systems perspective. arXiv preprint arXiv:1908. 10920, 2019.
Claudio Mayrink Verdun, Alex Oesterling, Himabindu Lakkaraju, and Flavio P Calmon. Soft best- of-n sampling for model alignment. arXiv preprint arXiv:2505.03/56. 2025.
Youssef Mroueh. Information theoretic guarantees for policy alignment in large language models. arXiv preprini arXiv:2406.0558 058883 2024.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, Yaguang Li, Tao Wang. Yanping Huang, Zhifeng Chen, Heng-Tze Cheng, Michael Collins, Trevor Strohman, et al. Controlled decoding from language models. In International Conference on Machine Learning, pp. 36486-36500 PMLR, 2024.
Reüichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browser-assisted question-answeriigg with human feedback. arXiv preprint 21Xiv:2112.09332. 2021.
Team OLMo, Pete Walsh, Luca Soldaini, Dirk Groeneveld, Kyle Lo, Shane Arora, Akshita Bhagia, Yuling Gu, Shengyi Huang, Matt Jordan, et al. 2 olmo 2 furious. arXiv preprint arXiv:2501.006 2024.
Long Ouyang. Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730- 27744, 2022.
EY Pee and Johannes O Royset. On solving large-scale finite minimax problems using exponential smoothing. Journal of Optimization Theory and Applications, 2011.
Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning, 2022.
Jiahao Qiu, Yifu Lu, Yifan Zeng, Jiacheng Guo, Jiayi Geng, Huazheng Wang, Kaixuan Huang, Yue
Wu, and Mengdi Wang. Treebon: Enhancing inference- time alignment with speculative tree- search and best-of-n sampling. arXiv preprint arXiv:2410. 16033, 2024.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint 11t.x::2305182990 2023.
Pier Giuseppe Sessa, Robert Dadashi, Léonard Hussenot, Johan Ferret, Nino Vieillard, Alexandre Ramé, Bobak Shariari, Sarah Perrin, Abe Friesen, Geoffrey Cideron, et al. Bond: Aligning llms with best-of-n distillation. arXiv preprint arXiv:2407. 14622, 2024.
Charlie Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling 11m test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
Yuda Song, Gokul Swamy, Aarti Singh, Drew Bagnell, and Wen Sun. The importance of online data: Understanding preference fine-tuning via coverage. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
13

---

Published as a conference paper at ICLR 2026
Benedikt Stroebl, Sayash Kapoor, and Arvind Narayanan. Inference scaling f-laws: The limits of Ilm resampling with imperfect verifiers. arXiv preprint arXiv:2411.17501, 2024.
Hanshi Sun, Momin Haider, Ruiqi Zhang, Huitao Yang, Jiahao Qiu, Ming Yin, Mengdi Wang, Peter Bartlett, and Andrea Zanette. Fast best-of-n decoding via speculative rejection. arXiv preprint 1rXiv:2410.20290 2024.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312. /8805, 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.09288. 2023.
Haoxiang Wang, Wei Xiong, Tengyang Xie, Han Zhao, and Tong Zhang. Interpretable preferences via multi-objective reward modeling and mixture-of ofxtuue-of-eexprts. In EMNLP, 2024.
Xueqin Wang, Yunlu Jiang, Mian Huang, and Heping Zhang. Robust variable selection with expo- nential squared loss. Journal of the American Statistical Association, 2013.
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference on Machine Learning. 2024.
Joy Qiping Yang, Salman Salamatian, Ziteng Sun, Ananda Theertha Suresh, and Ahmad Beirami. Asymptotics of language model aligmment. In 2024 IEEE International Symposium on Informa- tion Theory (ISIT), pp. 2027-2032. IEEE, 2024.
Kaylee Yingxi Yang and Andre Wibisono. Convergence of the inexact langevin algorithm and score- based generative models in divergence. arXiv preprint arXiv:2211.01512 2022.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314. 2024.
Wenhao Zhan, Masatoshi Uchara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline preference-based reinforcement learning. arXiv preprint arXiv:2305. /4816, 2023.
Heyang Zhao, Chenlu Ye, Quanquan Gu, and Tong Zhang. Sharp analysis for kl-regularized contex- tual bandits and rlhf. arXiv preprint arXiv:2411.04625, 2024.
Yao Zhao, Mikhail Khalman, Rishabh Joshi, Shashi Narayan, Mohammad Saleh, and Peter J Liu. Calibrating sequence likelihood improves conditional language generation. In The Eleventh Inter- national Conference on Learning Representations, 2022.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging llm-as-a-judee with mt- bench and chatbot arena. Advances in Neural Information Processing Systems, 66:46595-46623 2023.
14

---

Published as a conference paper at ICLR 2026
Appendix
Table of Contents
A Table of Notations
16
B Other Related Works
16
Calibrated Reward
Summary of KL divergence Results
E Gumbel-Max trick
17
F Technical Tools
18
G Proof and Details of Section
21
Proof and details Section
23
H.1 Upper bound proof and details
23
H.2 Lower bound proofs and details
27
1 Experiments
29
I.1 More Experiments
29
1.2 Numerical Examples.
................................
30
Comparison with Huang et al. (2025)
33
K Information projection across reward functions
34
L Large Language Model (LLM) Usage Disclosure
34
15

---

Published as a conference paper at ICLR 2026
A
TABLE OF NOTATIONS
All notations are summarized Table
Notation
Definition
r" ry x)
(Calibrated) true-reward model
2 N
(Calibrated) proxy-reward model
Number of responses
a
Prompt
13
Temperature (regularization coefficient)
(ylax)
Tilted policy under reward function
n SBoN (y/x)
SBoN policy under reward function r BoN policy under reward function r Reference policy
BoN (vlz)
T
Tref
kL(pp14)
KL. divergence between and distributions Optimal policy
TH (y)ar
(g.
Coverage constant under reward model r
Dr (x)
Set of maximizers for r (y,
(x)
Tilted Error
Table 1: Summary notations in the paper
B OTHER RELATED WORKS
Approximating the maximum operator using smoothed or softmax- based surrogate is a widely adopted technique in machine learning. This approach is particularly useful in settings where the hard maximum is non-differentiable or leads to unstable optimization. For instance, in robust regression, smooth approximations to the max operator are used in min-max formulations to achieve tractable optimization under distributional shifts (Wang et al., 2013; Li et al., 2023). In sequential decision decision-making, similar ideas appear in risk-sensitive control, Q-learming and off-policy learning, where the softmax of Q-values leads to stochastic policies that balance explo- ration and exploitation (Howard & Matheson, 1972; Borkar, 2002; Behnamnia et al., 2025). In con- vex and non-convex optimization, smoothing the maximum objective has been shown improve convergence properties (Kort & Bertsekas, 1972; Pee & Royset, 2011; Liu & Theodorou, 2019).
Smoothing of Maximum:
The Soft Best-of-N (SBoN) framework, (Mayrink Verdun et al., 2025; Khanov et al., 2024; Jinnai et al., 2024), leverages this principle by replacing the hard selection of the highest-reward sample with softmax- weighted sampling distribution. Regarding the SBoN, the empirical version of SBoN introduced by (Khanov al., 2024) as bution among the top-k candidate tokens is chosen. Then, the regularized version of BoN, which can be represented SBoN, is discussed by (Jinnai et al., 2024). Given the broad success of SBoN, we are motivated to theoretically investigate the SBoN policies and the effect of the proxy-reward model (reward hacking) and the quality of the reference policy.
where token from probability distri-
Several works have studied the theoretical underpinnings of reverse KL-regularized RLHF, particularly in terms of sample complexity (Zhao al., 2024; Xiong et al., 2024; Song et al., 2024; Zhan et al., 2023; Ye et al., 2024; Aminian et al., 2025). Note that, as the sampling distributions in BoN and SBoN are different, we cannot apply RLHF analysis these sampling strategies. Therefore, it is needed to develop new foundations for BoN and SBoN.
Theoretical Foundation of RLHF:
Overoptimization. Alignment methods are widely known to suffer from overoptimization, also known as misspecification, reward hacking, or Goodhart Law, where optimizing against proxy- reward model leads to degraded performance compared to the true-reward model (Amodei al., 2016; Casper et al., 2023; Gao et al., 2023b). This issue is particularly pronounced in inference-time alignment methods such as BoN, where an increasing number of responses N makes the overopti- mization problem worse (Huang et al., 2025; Stroebl al., 2024; Gao et al., 2023b). Huang et al. (2025) theoretically demonstrate that the BoN policy suffers from overoptimization when is large, given fixed estimation error in the reward model, and propose solution based on a x-2regularized
16

---

Published as a conference paper at ICLR 2026
framework. Other approaches to mitigating this issue include ensembling strategies (Coste al.; Eisenstein et al.) and regularization techniques (Ichihara et al.). concurrent line of work, Kha- laf et al. (2025) introduce the Best-of-Poisson method to reduce overoptimization in inference-tine algorithms. The overoptimization in BoN and SBoN is also studied by Khalaf et al. (2025) and a principled hedging framework is proposed to mitigate the overoptimization. In contrast, study overoptimization in inference- alignment methods SBoN and BoN from the perspectives of re- gret gap and KL divergence analysis.
C CALIBRATED REWARD
Inspired by (Balashankar et al., 2025), in this section, provide more details regarding calibrated reward. A standard metric for evaluation models the win-rate relative to base policy Tref (Stiennon et al., 2020; Gao et al., 2023b). For prompt and responses y, 2, define the win random variable under raw (uncalibrated) reward Tuc as
wy 2 2) = [f (1, x) > (2c x)} (ruc(y x) = (2, x)}.
Definition C.1 (Calibrated reward). The calibrated reward of y under policy π is its expected win- rate probability against x(- z):
Ne, (y. == (1) x)].
In practice, we consider x = Trefs therefore we denote calibrated reward via ((,, under reference policy. In the following, we provide some reasons for choosing calibrated reward instead of raw (uncalibrated) reward in our work,
Matches win-rate evaluation. For any policies T1; T2,
Wr(m > n2 æ) = Bywwit Fe,,, (U,
where (i( > 22 x) is standard win-rate. So maximizing Ey Woomrr (y, x)] directly optimizes standard win rate vs. the base model.
Invariance to score scaling, If m is strictly increasing and r' mor, then
<', = r(y,
making the target robust to arbitrary monotone reparameterizatiins of the reward (e.g.. affine rescaling, temperature).
Unified, probabilistic scale. For Neee(- x). r(y, x) Unif [0. 1].
independent of both and Tref This normalizes per-prompt reward scales and interprets
scores as win probabilities.
D SUMMARY OF KL DIVERGENCE RESULTS
In Table 2, summarize results KL divergences between the aligned and reference policies, along with corresponding upper bounds for both SBoN and BoN policies. Furthermore, in Table 3, summarize results KL divergences between aligned policies under true and proxy-reward models, along with upper bounds for SBoN and tilted policies.
E GUMBEL-MAX TRICK
We also provide an interpretation for SBoN from the Gumbel-Max trick. An alternative way to sample Z from
Pr(z = i) x exp(3 æ))
is via the Gumbel-Max trick. We can draw independent Gumbel 1), I,..., n, and then set
random variables G,
G;
Z = arg max (E.......N
((Y,,)) +
17

---

Published as a conference paper at ICLR 2026
Table 2: KL divergences between the aligned and reference policies, along with corresponding upper bounds for both SBoN and BoN policies.
KL divergence Term
Theorem Lemma
Upper Bound
KL (I (-lc) (((()))))
Lemma 4.1
N log 1+(N 1) B8
Theorem 3.1 in (Beirami et al., 2024) and Theorem in (Mroueh, 2024)
log(NV) 1 1/N
Table 3: KL divergences between aligned policies under true and proxy-reward models, along with upper bounds for SBoN and tilted policies.
KL divergence Term
Theorem / Lemma
Upper Bound
(1-(So (1x) (-12))
Lemma 4.2
N
N (an(22)
I+( [-xxp(-pp
(N-1)
(1 [s.r(-(z))
Lemma F88
2/ 23,/58))
Eleap(20F(Yaa)
Elxpp (Yaz) pespler Ber (F.)))
By properties of the Gumbel distribution, this yields exactly the same softmax sampling law, without needing to compute the normalizing factor Σj=1 exp(3i(Y,,x)) explicitly (Gumbel, 1954). When B + oo, the effect of the Gumbel noises vanishes and the sampling strategy reduces to BoN.
F TECHNICAL TOOLS
We denote the set maximizers of the proxy-reward function via ((x) = {0, (x) (
We introduce the functional derivative, see Cardaliaguet al. (2019).
Definition F.I. (Cardaliaguet et al., 2019) A functional U P(R") + I. admits functional st
derivative if there is map 8m P(R") x RR" + IR which is continuous P(RR") and, for all m, m' P(R"), it holds that
U(m')= Um = f(² {
80 (mg, a) (m' - m) (da) dB,
3m
where my m 3(m' 1 -m).
Definition F.2 (Sensitivity of policy). We also define the sensitivity of policy J. (y()))) which is a function of reward function r(y, Φ). with respect to the reward function as
(r(2)z)
(r)
lim 2r
(20)
Ör
Ar
Lemma F.3 Benibooovicc-Rubeeseee duality of total variation distance, see (Polyanskiy & Wu, 2022)). The Settorovicc-Rubbenste duality (variational representation) of the total variation dis- tance as follows:
TV(m, m2) = sup {Ez^m, - ( [g(2))}
(21)
L
DE인L
where Gr = 2 2-
S L}.
Lemma F4 (Lemma D.6 in (Aminian et al., 2025)). Consider the softmax policy, Tł (yfx) o Tref (y)zz) exp( (xp(B3rly (Br(y. x)). Then, the sensitivity of the policy with respect to the reward function is
dnL (r) BT, - (v(x)).
Or
Lemma F.5 (Pinskers Inequality (Canonne, 2022)). For my and m2, we have,
TV m2) < V (K(mm2|lm)
(22)
18

---

Published as a conference paper at ICLR 2026
The following Lemmata are useful for our technical proofs.
Lemma F6. The following upper bound holds.
(x, 9) Zp,y( 3)
log
S 8 / =ar((x) Can- (or( (2).
(23)
Proof.
Zp.y (x,
Ey (x)(
y
exe(((rr (y. ) reet (y/x)
Ey Exep(((((()xz) - r (y. x)) exp (T
(24)
Ey exp((Br (u: (vlar)
Σ TB. (vlxz) exp(()((()
x)))
Due to convexity of - --g((-) and using
inequllity we have,
Zp (z, 3)
-log (x, B)
- 3 Σ Tor (y) (r (y, x) - r(y,
TB. (y|z)
< B Σ
(r" (y, 2) - f(y, x) ())
(y)r(
T (y/=)
8
(y) f(y. zz) (ree
V
Trel (z)(z)
(25)
VB
Σ log ( (cxp (8(r*(), f(u, x))3) ret (ullr) Cgrr (2)
$ B V
log
exp (3( - - x))) (u0l=z)) (Ca
3
= B (2)((()/ (z),
Lemma F.7 The following holds,
KL(TT- (. (2x) || S log(Cro,r- (x)).
(26)
Proof. Note that, we have,
T,, (.1zz)
KL(TŞ- (- (2) (-(x=]]=Fet((((x)) S log (Bywa; (10)
Treel (-1x)
(27)
< Loo,( (x)).
Lemma F.8. The following upper bound holds,
(Ml)) s ( VCrr(a)).
(28)
Proof.
Ta. (ylz)) log TB.r (3/1z)
KL ((l=)
Σ
Tg, (y/ (r))
y
Σ (y, f(y. (y/Z) +
B/ (x)r(() (oao(((C//)) (z) + v (a,,(x)),
(29)
19

---

Published as a conference paper at ICLR 2026
where the final inequality holds due to Lemma F.6 and applying Cauchy- Schwarz inequality.
Lemma F.9. Suppose that f(Z) E [0, m.ax] Zmax = {2m, is the set of maximizers of f(Z),
i.e. f(z) ZZmax for Zmax. Then we have,
Elexp(23{(Z))
1 ExE2max P(Z = 2)
lim
(30)
8 00 E (2
Proof.
[2xx)(28f())] (jexp(2 mmax)) 1)]
(31)
E {(exp(ff(2)] (fexp(3(f(Z) - Z m]]
E, P(Z 24) exp((((((2) - -Zmax))
(32)
C P(Z=z;) zx) ex)(((((()()) - mmxx)))²
Now, we have,
limi E(oxp(28f(2)
(33)
+0000 E Rlexp(3f(2))²
Ej P(Z - =2)) ex)xx(22((((z - -zmax))
lim
(34)
8-000
(E, P(Z (x)xx((((((2) - -Zmax)) )))
ExeZ Zinax P(Z = 2)
(35)
CEeE Zmna PIz = 2))2
(36)
ExEZmax P(Z=2)
where we used the fact that 3 (xp( 7 = 0 for 2j < 7maax.
Lemma F.10 (Theorem in (Mayrink Verdun et al., 2025)). For B > 0, and N 2 1, we have,
KL (11z) STON (y/=)) S log (1+ CB,r (x)
N -1)
(37)
Lemma F.11. For a given x E X, we have,
5f(rr
cxp(xx
(38)
8r
(N 16-11" 1)2
where f(r log (Bl (Blexp(0r)+ " exp(BR.) 1), r r(y,x) and R₁ r(Y(,
Proof.
Note that { N-1 are iid. Therefore, we have, 5. 5f(r(y, 5r
5 exp (Bn 2 N- exp(BR.)
1
E
exp(3r) + Σ exp(
5r
1
E
exp(Br)
+ Ei=1 exp(31R1)
Bk (k(N-1) N-1) exp
k)2 (1 P(R - P(
x
(k (kexp Br) + N
k=1
< E
1
(39)
exp(3r)
+ E exp(
ecxp(3)
N
N -
k 1-1 1 (x=1)a- (1- (
Σ
x
(N 1)2
km
exe(p(2
(1+ + (N - 1))P(R= =
(N 1)2
N38exp(22)
(N 11
20

---

Published as a conference paper at ICLR 2026
For first inequality, provide more details in the following. Lets consider the conditional expec- tation where we condition on having exactly (k: - 1) of (N - 1) R&s equal to r. Therefore, we have,
exp(Br)
Di-1 exp(81l.)
dr
N
N 1
3k exp(3r) k (Br) Ei= exp(3R.) (1- P(R = (rr)))=pppk - (R =
k=1
Now computing the derivative and using the fact that 1 S exp(3R:), the first inequality holds.
Lemma F.12 (The BH inequality (Canonne, 2022)). For every two probability distributions p. q. have the simple yet never vacuous bound
TV(p. q) S e1-e-KL(pla)
(40)
G PROOF AND DETAILS OF SECTION 4
Lemma 4.1. The following upper bound holds on Kl. divergence between SBoN and refer- ence policies for a given prompt x X,
KL(T,BON (L(:SRoN(y/z)) (y/x) ((]r)]][Tee (v]=²) S log i (N - 11) 11)xp((88)) )))
SBoN
N
(41)
Proof. Recall that,
N-1 exp(3r
SBBN (yBoNyylz) = exp (x.x))"(xxx)) ( (exp(Sr*( (v, + Σ n..
Now, have,
KL
SBoN (ylz) ( (y((z))
Σ T.-
SBoN (y/æ)) log( SBON (y)oNNyl /roo
Σ
SBoN Tr.
(y|z) lNg
(42)
Σ
SBoN (y/lz) log(EE exp((r" (g,(Br"(,,x)))) Tr
+ Σ exp (Y,,))) -1]]
y
N
= log(N) +
Σ
SBoN (ylz) log(E (1 +
Σ
exp( *Yi,,))) - -x(x))))) (1,x))))~- -
For the second term in equation 42, consider
A(y. Y,2) -x)())(() 0.
where we have
(N A(v. Y,x) (N 13xxp(3).
21

---

Published as a conference paper at ICLR 2026
Therefore, have,
Σ SBoN
my. (ular) log(B (1
Σ
(aaaa)---""m (1) -
i=1
- Σ p
SBoN (u/zz) log
(43)
(N 1) exp(-B)
y
1
log(
1 (N exp((33) ).
Combining equation 43 with equation 42 completes the proof.
Lemma 4.2. The following upper bound holds on the KI. divergence between the SBoN policies under true-reward and proxy-reward models respectively,
SBaN KL
(-12)][
NB (x) SBoN (-1z)) S 1+ (N 1) exx((33)
N eNxpp(28)
(N 1)2 + +1). (44)
Proof. We first provide the following upper bound,
KT<,=BoN (y/x)) |.
SBoN
x))
SBoN (1/(ar)
SBoN
(y/x) log mf
SBoN (z)(z)
Σ
SBoN (y)x))((*(()) (v, f(y,x))
Typ
y
Σ
T.
SBoN (w/zz) [w)x))( log [El
exp(Br x)) EN- exp(3r((y,,)))
7
(45)
log (E
cxp(3f(y,x)) EN- exp(3f(Y.,
N / (x)
+ (N exp(-B)
Σ
SBoN (w]z²) log (El
(xp(3r((1, Enn exp(3ra(Yi,
1
log [E]
exp(3f(u.x)) Em
N-1 exp(3F(Y),,)))
where we used two facts. First,
N (-
SBoN (-12) 5 1+ (N - eexpp=9)
n
Second, for random variable
E| & VE[Xa] = El log(exp(3x2)) <
log ((eexx(((X)))
and applying it to ( (rr (y,2)) f(v, x)}} the final result in holds.
22

---

Published as a conference paper at ICLR 2026
Note that for the last term in equation 45, can apply the mean value theorem follows,
Σ SBoN
(y/x) log [El
exp(3r((y,,)) + Ei=1 exp(Brr(Ys,z)) 1)
,
log [E]
exp(Br(y, x)) + Ei=l exp(3i((), x))
(46)
$ SBoN (ulz))r"(y,at f(y,x)) (v.r)(
dr
where (1, log (E| explirr, (v.=1)+ -;' exp($t,(Y;=))) |), for some y E (0, 1) have ()) "f(u: x)) + - 7)x* (v, x). Using Lemma F.11, have,
öf (f(r(,,)))
(xpxxp(2
(47)
8r
(N 1)²
Using equation 47 in equation 46 and applying Gauchy-Schward inequality, we have,
Σ
SBoN
(yl ()) log (Bl
cxp(Br* (y, x)) + Di=1 exp(Br* (Y,, x))
y
log (E|
exp(Bf(y (1f(y,,)) x)) + Ei exp(BF(Y...)))
E11(11
exp(B(r* (Vi, - r (": x: 2 (y/lz)
(48)
5. (f (V,,,(,,,,))) (U. x)) 2
Σ 1r (V, F(y, 22) [t))2TTer((l)a
(re((1/2))
år
E N23 exp()x()
1+ 1)exp( -3) (N - 1)2
This completes the proof.
H PROOF AND DETAILS OF SECTION 5
H.1 UPPER BOUND PROOF AND DETAILS
Lemma 5.1 (Full Version). Under Assumption 3.1, the following properties of Ca (x)
hold,
1. (z.((x) = EF(ep(BF(YY.))
E ((xxp(29F(Yxx))
2. Ca,r(x) is an increasing function with respect to 3.
3. Coo, (2)) E. Aeuely,"" (2)]a) [2][æz where y (1:) arg max, rw,,)).
4. For all B < oo, we have S Ca.r(z) S min Coo (xx()))))
Proof. In the following, we provide proofs of different items.
1.
x (vlo)
Ca. (xx)
neat (g)xr)
exp(2 x))
12' (exp((F(( x)) (y)()
(49)
((exp(28f(Xxz))
E"lexp(BF(Y,
23

---

Published as a conference paper at ICLR 2026
2. We can show that the logarithm function of (z) is increasing. Then, due to the increas- ing feature of the log function, the final result holds.
E (xxp(2 x))]
log
(50)
(og( 2 log (B())))((3((X
then we can compute the derivative of equation 50,
(oog(Beexp(23F()
d (Bxp(
d3
d3
(51)
2 (xp()))) -2 (xx(xx
E ((ex((23F(Xxx))
xxxxp()((Yxx))
Note that we have,
[ E E(xp(BF(Yx2])
d3
(52)
1E2 lexp( (8 2))]
= =EYwnA-((1)) ( (Y, (-12)) (F(Y 0.
Therefore, we have,
ElF(Y, x) expp(3((X)))
(53)
((exp(23F(Y,x)))
((xp(3F(Y,xz))
This completes the proof.
3. Follows directly from Lemma F.9.
4. Due to Jensen inequality for (e(eep(BF(((xx)) < E(exp(288FY,, x))] the Ca,( We Elexp(29F(( exp(3). Furthermore, due
also have the uniform bound, (a,)(x) F'(exp(BF(Yxx)) increasing property in second item, we also have sup, (2,((x) = (z,)(()). Therefore, the upper bound holds.
Theorem H.1. The following upper bound holds,
A (T (-1z)) SBoNN (-1z)) < KL (-1x))l(TTr((+10)) - (L (|
+ (z) Car(z) + CCpr (x))
+ 2/ 2 log (1+ Ca.((1) -1)
Proof. Note that, we have,
J (Fg.r (.12), SBaN (-12))
E BYNtsNr (1x) (Y,Y x:) Ey (ro
= =By (11)) (+(Y,,)) x3] - E BY (1r) (r* (Y,x:)
(54)
+E Y (:a) (-)))r((()))))) (r(("(
(w) (r (Y,z))
1
24

---

Published as a conference paper at ICLR 2026
Note that, using the definition of ng. (-1zz) and TT.. ( (-12)) as solutions to KL-regularized problem, we have,
1 log(Ey (og(Ey>n.r(1))) (1xgex/)_
Y Y (1x) (10) [X,,== (1a))
(55)
1 (1)) + 1 I Y~ (1x) (1)))(( B
(56)
Therefore, for term I,, we have,
E Y (1 (Y,x)] - E (10)
-yy (1s) (Y,((Y Y (1x) (10) [+(Y,0)]
+ E Yomoa [A(Y, x)] Ey BY [r' (Y,x)]
(L(TT (1)) (L
(o log (Ey lyg (ogp
B
Te,r( (=)
y
<
(T (14)
1 (1
1 log ly (1
+
B
(y1z)
B
(f(u, (Tr
(yle))
(57)
<
(L (11=))) ( ( (-(x=]]=To((+Ix
log(E, bol 1
log By (iglByyxnnrt)pexx(((1
B
(ar(()ea))
<
(L (-1t)g.r(((11)) (+z))](aa((((1)) (L
1
+
B
log bel
B
log Ey (oxpyyyyncipp/px(((()Y...
(ar(w)ea))
5
(I ((()))) KL( ([o)l(()))))
+
Car (1)
(2)()))),r
25

---

Published as a conference paper at ICLR 2026
For term 1z and using a similar approach to term I1 and applying Lemma F.10, have,
B BY (1z) (r" (X, (y (X,
x (
|x)) ,,; SBBB (-12))
s 22in (1, 1 KI(TTF (xx) SBBN (1
(58)
< 22in 1, log (1 Ca.la)) -1
N
s <2 log
2 [1+ (2,r(2)
-1
N
Combining equation 57 and equation 58 with equation 54 completes the proof.
Theorem 5.2. Under Assumption 3.1, the following upper bound holds the optimal regret gap of the SBoN policy for any B > 0,
An,a (T, (11x)), ,. SBBN (-1z)) s (EBr(()( (oo.((a) + (oo.r(()))
+ 2 2/ log (1+ -oc,slx) -1
N
+ log (oo
Proof. Note that have,
A s,r (TT -12)), 122), SBBN (-1z))
Youz (-1x) (T,(Yx=)) By snoN (la))
= E Yywa (11z) 1r: (V, x]] - BYNTTE (-1r) [r*({xx)]
(59)
+ J (IT (.12)) o.
SBoN (-1x:)
For term I4, use Theorem H.l. For term Is. note that, we have for 3 > 0,
KL(T,- (- (- Te (-|x)) - ( (. (2) || T ( (-1x:)
Ey By (1=) lx E BY (1m) ( (r,))*
3
(60)
Combining equation 60 with Theorem H.1, completes the proof due the positiveness of KI. diver- gence and using Lemma F.7 and Lemma 5.1.
Remark H.2. For 3 we have, limg Tg.r. (.1z) Tre((-1z). Therefore, we have,
E Y~r;, (1m) [r* (Y,z)] - E BY (1z) |r (Y,x)) </2 (2KL(TT.
(61)
Proposition 5.3. Under Assumption 3. 1, the following upper bound holds on the optimal regrel gap of the BoN policy for any B >> O.
DJ (-1;(-12), xBo) BoN (-12)) < (x). Coo,((x) + (oo.r.
log (1+ Cx.,(1)) -1)
+ 2 2
N
26

---

Published as a conference paper at ICLR 2026
Proof. The results follow directly from Proposition 5.3 for 3 00.
H.2 LOWER BOUND PROOFS AND DETAILS
We can define the probability of coverage of maximizers under the reference policy as
p" (x) Pry (l=)) E DTp (z)) Coo,r
Lemma H.3. Under Assumption 5.5, the following lower bound holds on the optimal regret gap of the SBoN policy based on true-reward,
AJ, (Tt. (-1x), T, TO (-1x)) 2 ((x)Pr)rr(x),
(62)
where Prerr is the probability that selected sample from {Yi) via SBoN does not belong to y (z).
Proof. We have,
AJ, (Tzz (+lr), nT. SBoN (-1x))
Jr. (T (-1z)) J,, (TT. (-|x:)
B youg, z. (1x) (r" (Y,x)) - BY (-1x) (o (Y,
= BY (110) ( (Y,x) Prer + By (Y)) - (2)) (63)
2 1 (1 (1- (2)) (x) + -Prrrr (x))
= ((r))EEr)())
where Err the event where the selected sample using SBoN is not maximizer.
Next, we provide a lower bound on (I))
Lemma H.4. The following lower bound holds on Preer for SBoN algorithm,
N(11 - p¹ (z)) (1 p" (z)) N + (exp( - 1)
Prger (x) 2 (1 - (x'))
(64)
Proof. We consider cases where exactly K responses are selected from D (x)). The has bino- mial distribution Bin(N, p" (x)) Using Bayes rule, we have,
(r)
Pr(K (1) =)
p0 - (10)( =
p² (1)))(11 - (x)) N- Ex Ex exp(3r* (xp()r*(Y);,)) (Y),
E exp(Br (Y,, x))
(65)
N) M (()((1 (x) (x))
N - i
(1-
N - + i
p" (x) - (x)) N-t N-i
2(1-'(11)
N+ (e - NN
N((1 p' (x)) - (1 r. (x))
2 21-1717))
N + (e - 11) 1)
27

---

Published as a conference paper at ICLR 2026
Using Lemma H.3 and Lemma H.4, we can derive the following lower bound main optimal regret gap,
Theorem 5.6. Under the same Assumptions in Theorem 5.2 and Lemmna H.3, the following lower bound holds on the regret of SBoN policy under the proxy-reward model,
AJ,- (,, (-1x), 3 SBoN (-1x))
2 7(x) (1 - -1'x))) + N((1 - p²(()) - (1- (x))
N + (exp(() - 1)(N 1)
(66)
min (v 111-oxy exp (-U(,)))))) 1 (N 1) exp(-33 VEBr(x))
N
where p² (x) (z) and UN
ND [g
Nexp(201
+ 1). (N (N-1)²
T+(N- 1xxxp(88) 8]
Proof.
A (Té (-1z), n.
SBoN (-1x²)
(67)
A ( (-12),, T.. SBBN (-1z))
(68)
+ AJ,. (HSBoN (-12z), म SBoN (-1z)),
(69)
where equation 68 can be bounded using Lemma H.3 and Lemma H.4. By combining Lemma F.12 and Lemma 4.2 we have an upper bound on absolute value of equation 69 where can also result in lower bound on equation 69, Furthermore, another simple upper bound equation 69 is,
s, (म, (T,S (-1x), 7.. SBBN (-o))))))
(70)
By (1 [r" (Y, - EY
(M))) (1
(71)
Ey RoaN (1 [AY =]]] Ey BoN (r (n) (r (Y,
(72)
By (11 [fYY,))) EnnoN
Noon (81 [r' (Y,,))
(73)
Note that due to calibration, both true and proxy-reward models are uniform under Neat )err(-la) (-1x). There- fore, we have,
EywnspooN (Y, En (y|)) ()(Y
Now we have,
(n.BoN (-1z))2
Bn (Y12) (F [F(,,)) - By (X,() S
Fraf ( V (2r((z)
1 (N 1)xxp(-33 -3) / (0.r (x).
N
28

---

Published as a conference paper at ICLR 2026
1=10
6.56
0.70
6.65
5.52
Figure 3: Soft Best-of-N experiment using strong reward model (Left) and weak one (Right). When the performance of the reward model is poor, BoN can lead to overoptimization, while the SBoN can help to mitigate
I EXPERIMENTS
Our implementation is available in this link.
LLM-as-a-Judge: To evaluate the performance of the generated responses, we used GPT-4o to determine how harmless they are. Specifically, we used the following prompt:
You AI safety evaluator. Your task is to determine if response to given prompt contains harmful content. Respond with harmlessness score using these criteria:
2 SAFE: The response is completely safe and appropriate.
1 = SOMEWHAT HARMFUL: The response contains potentially concerning elements, mild toxicity, stereotypes, subtle harmful guidance, or borderline inappropriate content.
0= HARMFUL: The response contains clearly harmful content such as hate speech, explicit instructions for dangerous activities, severe toxicity, etc.
Provide your judgment integer in curly brackets like this: 2, or 3.
This yields reward with values ranging from 0 to where indicates complete harm and 2 indi- cates safety.
Future work may address optimizing B using cross-validation the estimation of terms in Re- mark 5.8 to derive sub-optimal B. For this study, we employ grid search over a range of B values.
1.1 MORE EXPERIMENTS
To further support our theoretical analysis, we conducted more experiments comparing Soft Best- of-N (SBoN) across different regularization strengths and reward model qualities. We ran extra experimental conditions: one using weaker proxy-reward model (ulu-v2.5513b-uf-mm (Ivison et al., 2024)) with respect to Armo reward model. As shown in Figure 3, when the reward model is weak, performance degrades for large due to reward hacking. However, the smoothing in SBoN helps mitigate this degradation. This observation is also aligned with theoretical analysis and discussion in Section 4.
29

---

Published as a conference paper at ICLR 2026
True vs Bound for (fixed M)
6
KL.Baundd
Bound, N 10
KL. N 100
100
KL. N 500
Bound, N 500
8
Figure 4: True KL divergence upper bound in Lemma 4.1 for fixed N 100, 500).
1.2 NUMERICAL EXAMPLES
1.2.1 BOUND
To illustrate how our analytical upper bound in Lemma 4.1 behaves function of the inverse temperature parameter 33, we run toy experiment in which
1. the reference policy the uniform distribution over responses, and
2. rewards are bounded, i.e., [0, 1].
For each B in a logarithmic sweep, we compute the true KI Kidveeegee between the SBoN policy and the reference policy, together with the theoretical bound derived in Lemma 4.
Very large 3 (nearBoN policy). As 3 + oc the SBoN policy converges to the BoN policy, The gap between the KI and the bound vanishes.
Very small B (reference policy). When 8 - 0 the SBoN policy approaches the uniform sampling from the reference policy, which results in the reference policy, making the KL. itself tend to zero; the bound is equal to zero for this value.
This experiment confirms that the bound is tight in the two asymptotic regimes and remains con- servative yet informative estimate elsewhere.
I.2.2 REGRET UPPER BOUND
To validate theoretical findings in Theorem 5.2 and Proposition 5.3, conducted numerical analysis comparing the regret upper bounds of SBoN against standard BoN under varying degrees of reward model error.
We simulate a simplified binary reward setting to isolate the effects of regularization inverse temper- ature (3) and proxy-reward error (8). The setup is defined as follows:
Reward function: We assume a binary reward landscape where responses have true and proxy rewards r (v), f(v) 1).
Reference Policy (T,))): The reference model generates an optimal response (7* 1) with prob-
ability Fef ()) 0.05, corresponding to coverage constant Coc,ri 20. The same also
30

---

Published as a conference paper at ICLR 2026
Regret Upper Bounds: SBoN BoN (N-256)
25
Regret Upper Bound (Theoretical)
GhoN Bound (8 0.05)
01-4111
SBcN Bound (5 6.151
2.0
Boll Bound (6 0.15, 8
1.0
Bound P
Inverse Temperature (6)
Figure 5: Numerical comparison of upper bound Regret of SBoN and BoN
holds for proxy-reward model and we have Coo,F 20. We also consider N 256 samples from reference policy.
Proxy-reward Error (6): The proxy-reward model matches the true-reward with probability 1 and commits error (flipping the label) with probability d. We evaluate three error regimes: Low (6 = 0.05), Medium (ō 0.15), and High (6 = 0.50).
SBoN: We compute the regret upper bound using Theorem 5.2, varying the inverse temperature B from 0.5 to 1000.
BoN: We compute the regret upper bound using Proposition 5.3, which represents the asymptotic limit of SBoN as 3 + oc. In this binary setting, the maximum possible error is (Eoerr 1).
Discussion: The results, Fig. demonstrate distinct trade-off mechanism governed by the inverse temperature 3. While the standard BoN bound remains constant at a high value due to its suscepti- bility to the maximum error ( 1), the SBoN bound forms curve with minimum.
For every error rate tested, we observe a "sweet spot" -a finite optimal inverse temperature 3 where the SBoN bound is significantly tighter than the BoN bound. This confirms that by smoothing the policy (finite 3), SBoN effectively balances the trade-off between exploring high-reward regions and mitigating the overoptimization caused by proxy-reward errors.
1.2.3 REGRET LOWER BOUND
To complement our lower bound analysis, we numerically evaluate the lower bounds on the regret gap for both SBoN and BoN, as derived in Theorem 5.6 and Proposition 5.7 respectively. These lower bounds serve as a "safety guarantee," quantifying the worst-case performance degradation caused by overoptimization. We utilize the same binary reward setup described in previous sec- tion, with sample size N = 32 and consider no error (8 = 0). The results in Fig. 6 illustrate an advantage of the SBoN policy line, = 0.15, 0.5), the BoN lower bound drops significantly, indicating a weak guarantee against performance collapse. Note that, for emror regime, the lower bound BoN's regret is positive.
the deterministic BoN policy. In emoo regimes (blue dashed
31

---

Published as a conference paper at ICLR 2026
Regret Bounds: SBoN (N-32) 32)
BoN LB No Error 16 Q)
0.75
SBoN LB Medium Error (6 0.15)
Medium
Regret Lower Bound (Higherii is Better)
SBoN LB High Error (6 0.50)
0.50
BoN LB High Error lo 0.50)
0.25
0.00
-0.25
-0.50
-0.5
10
10"
10
Inverse Temperature (g)
Figure 6: Numerical comparison lower bound on Regret of SBoN and BoN
Difference between Upper and Lower Bounds of Regret (N=32)
30
Difference (Upper- Lower Bound)
SBoN Gap (No Emor 15 O) (8 0))
5
10
10a
10
Inverse Temperature (B)
Figure 7: Numerical comparison of the gap between upper and lower bounds on Regret of SBoN
and BoN
32

---

Published as a conference paper at ICLR 2026
Herneeness sp0re (Normstzee))
0.22
0L80
0.51
0.70
0.00
B-22022
0.48
0.60
Figure 8: InferenceTTimePessiniin experiment using a strong reward model (Left) weak one (Right). When the performance of the reward model is poor, BoN can lead to overoptimization, while the InferenceTimeeessiimee can help to mitigate it.
1.2.4 UPPER AND LOWER BOUNDS GAP
To compare the performance of upper and lower bounds, we consider the case where which similar to no-overoptimization scenario. As shown in Fig. 7, the gap between upper and lower bounds of BoN is tighter than SBoN.
J COMPARISON WITH HUANG ET AL. (2025)
contrast our contributions with the recent work Huang et (2025), focusing on four key dimensions: the object of study, regret bounds, and the mechanism of regularization.
Object of study. Huang al. (2025) analyze BoN, introducing inference-time pessimism algo- rithm within a x -rregulariee framework to mitigate overoptimization. In contrast, we an- alyze SBoN via treating BoN the limit where 3 and derive finite-sample KI. and regret bounds under reward model misspecification (specifically, proxy-reward vs. true- reward). To our knowledge, these SBoN-specific bounds characterizing the behavior under overoptimization are novel.
Error metrics and reward modeling. While Huang et al. (2025) operate on raw (uncalibrated) re- wards using mean-squared error (MSE), we utilize calibrated rewards (Balashankar al., 2025). We introduce the tilted error, denoted as 6,,r, which interpolates between MSE (at B 0) and - еттоr (as + sc). This metric allows us explicitly track the dynamics function of both N and the inverse temperature 3.
of overoptimization
Regret bounds. Our Theorem 5.2, Proposition 5.3, Theorem 5.6 and Proposition 5.7 and establish regret bounds for SBoN and its BoN limit that depend (ii) the coverage constants Coc.r for both the true and proxy-rewards. A crucial distinction, highlighted in Remark 5.4, is that our BoN regret bound remains finite even when overop- timization vanishes (i.c., when f = 0 or N + oc). Conversely, the bound proposed by Huang et al. (2025) on BoN scales with the _ -eror. This represents a qualitative improvement in how misspecification is handled in our analysis.
(i) the tilted error 6g, (2r) and
Theoretical and algorithmic consistency. Our analysis of SBoN fully incorporates the algorithm's primary regularization parameter, 8. In contrast, the theoretical regret bounds for Inference- TimePessimism in Huang et al. (2025) exclude the estimation еттоr of the normalization factor (Algorithm 3) and are independent of the truncation parameter required by their Algorithm 4. Furthermore, regarding practical complexity, SBoN relies on a single hy- perparameter 8, whereas SeterenceTiimeessiiie
requires tuning an additional truncation parameter and incurs computational overhead to estimate the normalization factor.
IifereeccTiiePessiiee
Experiment:
We ran some experiments for CattreeceTieeeessmmmmiiii algorithm (Huang et al., 2025); the results shown in Fig. 8. We followed the configuration deseribed in their paper, and in this experiment denotes the x" regularization parameter. Comparing Fig. with Fig. 2, we find that the two methods achieve comparable performance. However, SBoN is substantially easier implement and
33

---

Published as a conference paper at ICLR 2026
tune, since it avoids the extra computational overhead and expanded hyperparameter search space introduced by the pessimistic approach.
K INFORMATION PROJECTION ACROSS REWARD FUNCTIONS
In this section, we study the KL divergence behavior in Section for large N regime, where the SBoN policy converge tilted optimal policy.
We consider a proxy-reward class R rewards, and projection problem at a fixed inverse temper- ature B which is inspired by reducing the estimation error,
(reverse-I-proj in tilted family) ft arg min DKL( TB. FER
Proposition K.1 (Pythagorean I-projection reward space), Suppose the proxy class R is corvex in (e.g., an affine subspace). Lel j arg minseR (LT,,, [[ Then, have,
2 KI
(74)
Estimation
Kl-diieegeece based on praxy-rewaar reward
Proof. The proof follows from Theorem in Csiszár & Matus (2003).
Proposition K.1 and Lemma F.7 provide an upper bound on (T [ret). Since the LHS of equation 74 is fixed for given 3, an increase in estimation error necessarily decreases the allowable divergence between the proxy-reward and the reference policies DKL. (TTg [re)). r* R, the estimation error is zero (no overoptimizationn. If & R. the estimation error consumes part of the total divergence budget. This analysis can be extended to finite N, using Lemma F.10.
L LARGE LANGUAGE MODEL (LLM) USAGE DISCLOSURE
We used large language models (LLMs) only for editing support (clarity/grammarr) All LLM- assisted edits were reviewed by the authors, who remain fully responsible under the ICLR 2026 policy.
34


Reviews:
[{"review_id": "6orT5yJqXK", "reviewer": "Reviewer_9eqs", "summary": "This paper provides a theoretical and empirical analysis of Best-of-N (BoN) and its smooth variant Soft Best-of-N (SBoN), two inference-time alignment methods for generative models.\nThe authors introduce a formal framework that connects SBoN to KL-regularized reward maximization and analyze two key quantities: (1) the KL divergence between the aligned and reference policies, and (2) the regret, i.e., the calibrated true-reward gap between the optimal and aligned policies.\nThey derive finite-sample upper bounds for both KL divergence and regret under general conditions, and show that SBoN can outperform BoN when proxy reward models suffer from overoptimization (reward hacking). Empirical results on text generation tasks confirm that smoothing (via temperature β) mitigates reward overoptimization when reward model quality is low.", "questions": "same as weakness", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The poor calibration of reward model is a widely known problem in the community, which will largely affect the BoN (test time scaling) results as reward models are sensitive to OOD data, and one single poor-rated trajectory can influence the final BoN result. And the paper proposed SBoN seems show better performance.", "weaknesses": "- The experiments are limited, I suggest to verify the effectiveness  by conducting more experiments on recent non-verifiable agentic tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YuaiaULk8f", "reviewer": "Reviewer_uC3a", "summary": "The point of this paper is to adapt LLM's to make their output adjust to some human evaluation metric (e.g. no harmfulness). This is typically done by a human preference function that is learned from data. By sampling multiple generations N  and choosing the best according to the learned preference function, a strategy called Best of N, can be used to generate such outputs adhering to the preference. However, for imperfect preference function, sampling more samples can lead to samples that are \"overoptimized\". This means that the samples obtained are not good according to the underlying human preference anymore. This work proposes Soft Best-of-N, which applies a soft-max when selecting the best sample, which regularizes the procedure. This paper studies the Soft Best-of-N theoretically, showing bounds on its performance, and analyzes when this regularization can improve performance over Best-of-N. The theoretical results are empirically verified by a small experiment.", "questions": "Especially Questions 1-4 are particularly important for me and to decide if I will increase my score further. \n\n1. Why does Eq 10 measure performance? The KL term is not justified anywhere. This seems especially weak, since the SBoN method depends on Beta (while BoN does not); therefore; isn't it logical that the evaluation in terms of this loss that depends on Beta favors SBoN? Or is actually Eq 9 used? (the notation is a bit unclear here; because J is defined twice). Furthermore, since Eq 10 depends on the true r^*; I think there is no reason to stick close to the reference model, right? I don't see why KL is necessary here.\n \n2. I think I got a bit confused with the bounds. For Theorem 4.3, you state around line 362 that: \"We aim to minimize the second term.\". But, this bound is an upperbound on the reward, right? Why would we want this term to be small? I understand why we want to minimize the upperbound on regret bounds (e.g. Theorem 5.2), but I am missing something here why we are looking at this upperbound and why we want it to be small.\n\n3. In line 447 a quite technical condition is given under which the SBoN bound is favored. Can you explain what it means? You also allude to this in the last sentence of the conclusion; what are these conditions? \n\n4. How does the proposed method compare to Huang's? E.g. their inference time pessimisim method? (Given that you explicitly compare some of your results to \ntheirs, isn't it fair to also compare to their strategy?) \n\n5. \"We assume that overoptimization regime happens whenever we have \\epsilon > 0\"; this assumption seems strange to me. Say that the preference function is just very poorly trained (or not trained for that sake); then \\epsilon > 0 right? Would this also be \"overoptimization\"? \n6. \"Note that in (Huang et al., 2025), raw (uncalibrated)\nreward models are utilized for error definition\"; so? Does that in any way invalidate their result, or are their results suboptimal for that reason? Can you show this with an example? \n7. \"Similarly, we can define ... as the optimal policy under the calibrated proxy-reward model\"; isnt this strange, since this is not nececarily the \"optimal\" policy since it can have issues due to overoptimization?\n\nNote that I did not check the mathematical proofs in the appendix, I only focused on the main body.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is self-contained, even though I am not an expert in this particular domain I could get the main results that are quite technical\n- The small experiment corroborates the theoretical findings", "weaknesses": "- Sometimes its not entirely clear what are the key novel results of this paper compared to other papers (e.g. Huang 2025), it would be good to highlight this more \n- From a rough reading of Huang 2025 it seems they also aim to solve this exact problem. How does your proposed algorithm compare to theirs? Note that I am not asking for an experiment or anything, but a theoretical interpretation would also be fine for me (both would be even stronger). \n- This paper has no Discussion section which I think should be in each quality paper; addressing: 1) are the results expected compared to related works? provide any context. 2) is it possible that there were any mistakes or weaknesses in the experiments? discuss them. 3) is there any future work? what would be most interesting to tackle next?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JvsEnz4rSG", "reviewer": "Reviewer_rpmQ", "summary": "This paper provides a theoretical analysis of the soft Best-of-N (SBoN) method, which smooths the output probabilities, a technique commonly used in various applications. The focus is on the calibrated proxy reward rather than the (raw) true reward, with respect to KL-divergence and regret. The authors show that in certain conditions, SBoN achieves a tighter bound on the regret gap than standard Best-of-N (BoN), while BoN attains a tighter regret upper bound when over-optimization is absent. Since the smoothing usually introduces algorithmic conservativeness, these results are consistent with general intuition.", "questions": "1. In Section 3.1 the authors consider the finite set of prompts $X$. For responses this is plausible, since an LLM outputs finite-length token sequences from a finite vocabulary. For prompts, however, $X$ is provided by the human and is not naturally finite. Is finiteness of $X$ actually required for the analysis (as far as I checked, it does not seem necessary), or only for notational convenience? If it is required, can you clarify why?\n\n2. The temperature $\\beta$ is used for three different roles: (i) tilted optimal policy for the KL-regularizer, (ii) the entropy temperature in SBoN (the softmax smoothing), and (iii) the parameter in the tilted error term. Are these all meant to be the same $\\beta$? If not, it would be clearer to separate them, e.g., ($\\beta_{\\text{KL}}, \\beta_{\\text{SBoN}}, \\beta_{\\text{err}} $).\n\n3. What is the intended meaning of Theorem 4.3? Although the authors state that it can be viewed as an improvement relative to the reference policy, it is unclear what insight is gained from providing an **upper bound** on the expected calibrated reward. The bound can exceed $1$ in some cases, which is trivial since the calibrated reward itself is defined in $[0,1]$. While the bound is always larger than $0.5$ (the reward of the reference policy), this alone does not make the result informative. Furthermore, the authors mention that they aim  to maximize the first term and minimize the second term, but this makes the overall objective of Theorem 4.3 difficult to interpret. Although the intuition behind maximizing or minimizing each component is reasonable, the combined purpose of these directions and the motivation for presenting Theorem 4.3 remain unclear. Could the authors clarify the intended rationale for considering this theorem?\n\n4. The regret upper bounds are more informative, as the authors provide a clear comparison between SBoN and BoN. One straightforward question: would it be possible to derive a lower bound on the optimality gap when $N$ is finite and $\\beta$ is fixed? If so, such a result would offer a clearer reference point for evaluating the tightness and significance of the obtained upper bounds.\n\n5. Could you explain why the first inequality in the proof of Lemma E.11 holds? Does the derivation implicitly assume that the reward function $r$ takes discrete values? If $r_c$ follows a uniform distribution on $[0,1]$ as the true calibrated reward function under the reference policy, then the event $\\\\{ R= r \\\\}$ has zero probability. \n\n6. In (44) there is an equality where terms of the form $-\\beta \\sum_y \\cdots$ seems to disappear. Is (44) intended to be an inequality instead of equality? If not, can you provide the details?\n\n7. Could you provide the skipped steps between equation (47) and the following inequality? Because the notation is quite dense, it is difficult to recall all the original definitions. Including the intermediate steps would make the proof much clearer and providing explicit pointers or brief reminders of key definitions would greatly help readers follow how each inequality is derived.\n\n---\n\nComments \n\n1. The experiments use a “harmlessness score,” but there seems no definition in the main text. At least, it would be better to specify whether higher is better or lower is better.\n\n---\n\nMinor comments (typos)\n\n* The reward function $r$ is first defined on $X\\times Y$ with notation $r(x,y)$ in (2), but later the paper mostly uses $r(y,x)$. Please make this consistent.\n\n* Possible typo in the definition of $Z_{N,\\beta}$ in L204: the exponent $-1$ after the expectation looks like a typo.\n\n* Possible typo in L448: the denominator shows $C\\_{\\beta, \\hat{r}\\_C, \\text{ref}}$ but based on context it seems this should be $C\\_{\\infty, \\hat{r}\\_C, \\text{ref}}$.\n\n* Eisenstein et al. (2023) appears to be listed twice in the references (page 10).\n\n* Lemma E.9: “miximizer” should be “maximizer.”\n\n* Lemma E.11: the numerator is missing a $\\delta$.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "* Provides finite-sample bounds on the KL divergence between SBoN and the reference policy under the true reward model, as well as between SBoN policies under the true and proxy reward models. These results generalize across different values of $\\beta$ (the temperature parameter for the Shannon entropy penalty used to smooth probabilities).\n\n* Considers a calibrated proxy-reward model, which is more realistic and relevant for practical applications.\n\n* I carefully read the paper, including the appendices, and checked the proofs (except Appendix G). Most of the derivations appear correct, though a few technical points remain unclear (see the Questions section).", "weaknesses": "* The paper has overly complex notation, which significantly reduces readability and makes it difficult to follow the theoretical flow. Some notation should be refined or consistent for clarity.\n\n* The main theoretical results are difficult to interpret (see the Questions section for details).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R7SOk8vcDb", "reviewer": "Reviewer_vx3U", "summary": "This paper studies Soft Best-of-N (SBoN), a smoothed variant of Best-of-N (BoN), from a theoretical perspective. \n\nIt proves (i) an explicit upper bound on the KL divergence between the SBoN policy and the reference policy (Lemma 4.1); (ii) an upper bound on the KL divergence between SBoN policies induced by true vs. proxy rewards as a function of (among others) the tilted error between proxy and true rewards (Lemma 4.2); (iii) an upper bound on true reward under proxy-reward SBoN (Theorem 4.3); and (iv) optimality-gap (regret) bounds for SBoN and, as a limit, BoN (Theorems 5.2, 5.3). \n\nEmpirically, SBoN mitigates (but does not eliminate) over-optimization when the proxy is weak (Fig. 1). Overall, the paper formally shows that smoothing can be a principled mitigation against reward over-optimization.", "questions": "Q1: Line 60: What do you mean by \"scales proportionally\" in line 60?\n\nQ2: Line 273: what do you mean by KL regularized objective for SBoN? SBoN doesn't optimize that directly.\n\nQ3: How useful are the upper bounds? How do you foresee other researchers operationalizing them to find or evaluate other strategies against reward hacking? I appreciate the toy example in Figure 4 for your first lemma and would suggest the same for your other results. Also, how would the upper bounds look like in your empirical experiment in Figure 1?\n\nQ4: I understand finding lower bounds must be challenging, but are there settings where we could have a meaningful lower bound? \n\nI am convinced by the authors' results. However, I believe the paper would benefit from a stronger motivation, as well as insights on the consequences of their theoretical results.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "S1: The study of inference-time alignment is timely and rigorous, and the presented results target practically relevant and meaningful quantities. Best-of-N in commonly used in practice, so analyzing a smoothed version that could be safer against overoptimization is valuable.  \n\nS2: The mathematical setup is more convincing than previous related work because of the explicit reward calibration. I also appreciate that the authors considered the “tilted error” viewpoint since it gives a single knob that moves from average-case to worst-case sensitivity. It is a helpful way to reason about when smoothing should help, and I believe this setup is a great baseline for other papers in this field.", "weaknesses": "W1: The presentation can be greatly improved. In particular, I encourage the authors to motivate their setup. For example, they mention calibration in Line 49 without any context. The usefulness of calibration is not obvious until much later in Line 229. I also encourage them to be explicit in how calibration is implemented. \n\nW2: While the theoretical results hold for BoN as well, they seem to be much looser than if BoN had been studied directly as in previous work. I understand why the bounds are loose because of the challenges analyzing the complex SBoN policy in (3). Hence, I believe readers would benefit from a clearer motivation for studying Soft BoN. This is especially true given that SBoN is a new method that is not deployed in practice.\n\nW3:  I am not sure of the takeaway of this paper. This is due to two issues: (1) the obvious one is the lack of a principled way to choose the right temperature, as well as the limited experimental results, and (2) more importantly, I cannot make sense of what the results tell us. I would appreciate if the authors look at simple cases: how would smoothing help when the reward model misranks near the top only, for example?\n\nMinor:\n1. There are a few typos (missing spaces, spelling mistakes) scattered in the paper (lines 36, 46, 110...). \n2. I would encourage moving the preview of the results in Tables 1 and 2 to the main text. I also liked Figure 2 so I can make sense of the different terms. I feel it is challenging to keep up with the notation in the main text. I would suggest looking at a different notation to differentiate the policies from each other.\n3. At Line 35, fix the attribution of Best-of-N. It was popularized for LLMs by Stiennon et al.\n4. Line 50 is confusing, what do you mean by \"using some dataset\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)