Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment
Authors: Audrey Huang
Adam Block
Qinghua Liu
Nan Jiang
Akshay Krishnamurthy
Dylan J Foster
Venue: ICML 2025 poster (2025)
Keywords: inference time alignment
best of n
pessimism
reinforcement learning theory
offline reinforcement learning
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We analyze the Best-of-N algorithm for choosing among language model generations and demonstrate that it is suboptimal, before introducing a new, optimal algorithm motivated by the principle of pessimism in the face of uncertainty.

Abstract: Recent work on inference-time alignment has established benefits of increasing inference-time computation in language models, but naively scaling compute through techniques like Best-of-N sampling can cause performance to degrade due to reward hacking. Toward a theoretical understanding of how to best leverage additional computation, we formalize inference-time alignment as improving a pre-trained policy’s responses for a prompt of interest, given access to an imperfect reward model. We analyze the performance of inference-time alignment algorithms in terms of (i) response quality, and (ii) compute, and provide new results that highlight the importance of the pre-trained policy’s coverage over high-quality responses for performance and compute scaling: (1) We show that Best-of-N alignment with an ideal N can achieve optimal performance under stringent notions of coverage, but provably suffers from reward hacking when N is large, and fails to achieve tight guarantees under more realistic coverage conditions; (2) We introduce InferenceTimePessimism, a new algorithm which mitigates reward hacking through deliberate use of inference-time compute, implementing pessimism in the face of uncertainty; we prove that its performance is optimal and scaling-monotonic, i.e., does ot degrade as N increases. We complement our theoretical results with experiments that demonstrate the practicality of our algorithm across a variety of tasks and models.

Is Best-of-N the Best of Them?
Coverage, Scaling, and Optimality in Inference-Time Alignment
Audrey Huang' Adam Block² Qinghua Liu Nan Jiang'
Akshay Krishnamurthy? Dylan J. Foster?
Abstract
improvements in their capabilities (Brown et al., 2024; Snell et al., 2024; Wu et al., 2024b; OpenAI, 2024b; DeepSeek-AI, 2025) and played a central role in recent AI breakthroughs (Chollet et al., 2024). While there are multitude of ways in which additional computation can be utilized during inference e.g., to generate long chains of thought (Wei al., 2022; Li al., 2024b), have the model rate correct its own responses (Zheng et al., 2023; Wu et al., 2024a), implement planning and search (Yao et al., 2024; Zhang et al., 2024) exceedingly simple methods like Best-of-N (parallel) sampling can provide significant performance gains (Lightman et al., 2023; Brown et al., 2024), and enjoy provable representational benefits (Huang et al., 2024a). Such algorithms are also widely used throughout post-training for frontier models (DeepSeek-AI, 2025; Yang et al., 2024a), and thereby serve as comnersonn of fine-tuning and inference.
Recent work on inference-time alignment has established the benefits of increasing inference- time computation in language models, but naively scaling compute through techniques like Best-of-N sampling can cause performance to de- grade due to reward hacking. Toward a theoreti- cal understanding of how to best leverage addi- tional computation, we formalize inference-time alignment as improving pre-trained policys sponses for prompt of interest, given access to an imperfect reward model. We analyze the per- formance of inference-time aligmment algorithms in terms of (i) response quality, and (ii) compute, and provide new results that highlight the impor- tance of the pre-trained policys coverage over high-quality responses for performance and com- pute scaling: (I) We show that Best-of-N align- ment with an ideal N can achieve optimal perfor- mance under stringent notions of coverage, but provably suffers from reward hacking when N is large, and fails to achieve tight guarantees un- der more realistic coverage conditions; (2) We introduce InferenceT TincceTimmeee imePess sm, new al- gorithm which mitigates reward hacking through deliberate use of inference-time compute, imple- menting pessimism in the face of uncertainty; we prove that its performance is optimal and scaling- monotonic, i.c., does not degrade as N increases. We complement our theoretical results with ex- periments that demonstrate the practicality of our algorithm across variety of tasks and models.
Toward developing a deeper understanding of the algorith- mie landscape for inference-time computation, in this pa- per, we focus on the problem of inference-time alignment: given a task and reward model that is a proxy for task performance, how can we best use inference-time computa- tion to improve the quality of a response chosen from many candidates generated by the base model? The Best-of-N heuristic one of the most widely used inference-time alignment methods, and proceeds by generating N can- didate responses for a given prompt, then returning the response with the highest reward under a reward model (Stiennon et al., 2020; Nakano et al., 2021; Touvron et al., 2023; Gao et al., 2023; Eisenstein et al., 2023; Mudgal et al., 2024). While attractive its simplicity, Best-of-N and related heuristics are known to suffer from reward overoptimization or reward hacking when N increases (Gao et al., 2023; Stroebl et al., 2024; Chow et al., 2024; Frick et al., 2024). While one might hope that increasing computation to generate a larger number of candidates will increase the likelihood of selecting a high-quality response, reward model errors at the tail of the response distribution can cause Best-of-N return generations with high (modeled) reward, but poor task performance.
1. Introduction
Inference-tine -ime computation has emerged as new axis for scaling in language models, which has led to dramatic
'Computer Science Department, University of Illinois at Urbana-Chand Champaan,,,,,,,,, Champaign, Illinois, USA "Mierosoft Re- scarch, New York, New York, USA. Correspondence to: Audrey Huang caudreyh5 @ @duu.
This overoptimization phenomenon raises two fundamen- tal questions, which we investigate in this paper: (1) what is the extent to which the imperfect reward model limits
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
the performance of inference-time aligament methods; and (2) can more deliberate algorithm design lead to performance gains that scale monotonically with increased computation? Beyond guiding practical interventions for inference-time alignment, answers to these questions con- tribute to a foundational understanding of inference-time computation more broadly.
Our formal framework, summarized above, reformulates inference-time alignment statistical problem via query complexity. This allows us to derive fundamental limits on the performance of any inference- timeeete-emmeeee alignment algorithm. We show that the best possible reward one can achieve, ir- respective of computational cost, is determined by the base policy's coveruge over high-quality responses, along with the mean-squared error of F. This serves as a skyline for our investigation into improved algorithmic interventions.
Our framework. To address the questions above, we pose inference-time alignment' as the task of extracting a high- quality response y for a prompt x from a pre-trained lan- guage model, or base policy Tref X + A()), that maps a prompt a distribution over responses y E V. The qual- ity of the response ÿ is determined by an underlying true reward function r* X' y + [0, Rmax], that expresses, for example, the conrectnsss of math proof or the help- fulness of a chat response. The algorithm designer does not know r" and instead uses an imperfect reward model F (c.g., one Iearned from preference-basee feedback (Chris- tiano et al., 2017: Ouyang et al., 2022; Wang et al., 2024b)) to maximize performance as follows. Using black-box ac- cess to re and f. i.e., sampling queries y Trer(- z) and evaluation queries F(I,)) y) and (y Ir), we aim to pro- duce response y that approximately maximizes the true reward (thereby minimizing regrel to the optimal policy),
Tight analysis of BoN-Alignment (Sec. 3). Within our framework, we offer the first theoretical analysis of the regret of Best-of-N alignment (BoN-Alige) Alignment). We show that BoN- ainnAlltn can achieve optimal regret under a stringent notion of coverage ("uniform" or -type) when N is tuned appropriately, but:
1. provably suffers from overoptimization, degrading in performance once N scales past a critical threshold; and
2. fails to achieve tight guarantees under weaker notions of coverage ("average-case" or -tyye)), thereby falling short of the skyline established in Section 2. (Sec. 4).
Optimal algorithm: inferenceTimePessiiiie Motivated by the shortcomings of Best-of-N, we introduce an improved algorithm, inferenceTineen immeeessieeeeeiiie We prove that Inference weeeessimiiiiieeee
r" (x,
max (x,x)"(x)y). yEV
(1)
is regret-optimal, in the sense that it can achieve the best possible reward in our framework, thereby match- ing the skyline in Section 2; and
This formulation presents two central questions:
Q1: Regret. How close to optimal can we make the reward r* 7) in Eq. (1), as a function of the quality of the model F?
2. is scaling- monotonic, in the sense that it is guaran- teed to avoid overoptimization beyond certain point (determined by the regularization parameter), even as N x..
Q2: Compute. What is the computational cost measured by the number of sampling queries y ~ Tiee(- x)) and evaluation queries v) and (y x) used by the algorithm-require for optimal reward?
To achieve this, our algorithm uses a novel rejection sampling scheme to implement x-rreularrization which is known to mitigate overoptimization via the principle of pessimism in the face of uncertainty (Huang et al., inference time. Beyond achieving optimal regret, we show that InferenceTine www.nneeeeeeeesmmm..... uses near-optimal compute under our framework.
Note that while our goal is to maximize the true reward r" the quality of the reward model f creates an inherent, information-theoreti barrier to optimizing r", since the lat- ter unobserved. Intuitively, we should not be able to maxi- mize quality under y* if f is highly inaccurate.
Empirical evaluation (Sec. 5). To demonstrate the benefits of InferenceTiimeeessini sm, we compare the algorithm to BoN-Alignment across several tasks, base policies, and reward models. As predicted by our theory, BoN-Alignment degrades in performance as computation increases (via N), while Inference inferreceTimePesiiiin ieeeeessieeeeieee sm is ocaling-monotont and does not suffer from this character- istic overoptimization phenomenon (Figure 1). We also ob- serve several instances where Inference wiw.eeeimmmeesmmmmm..m outperforms BoN-Alignment in terms of maximal reward achieved when the computational budget is untuned, demonstrating the robustness of our algorithm. Ap- pendix contains further empirical results, including
1.1. Contributions
We show that Best-of-N alignment and related heuristics may fail to achieve optimal regret, but that more sophis- ticated use of inference-time computaiion-nmmely to extract additional information from the reward model and quantify its uncertainty-oe can mitigate overoptimization, and achieve optimal regret and compute scaling.
Statistical framework & necessity of coverage (Sec. 2).
Following prior work (e.g., Rafailov et al. (2023); Ye et al. (2024)), we adopt contextual bandit/reinforcmmett leamnigg termi- nology, interpreting the language model as a policy.
2

---

Coverage, Scaling, and Optimality in Inference- Alignment
30
250
% Lift in Accuracy over firef
Gemma (2B)
Estimated Reward (
Liama (3B)
20
200
Phi-3 Mini
Mistral (7B)
10
150-
0-
100
-20
27
2
2 2
2
2a
24
N
Figure I. Comparison between performance of aonmmeltnmennt (dashed lines) and wwnferenceTimeeeseeeeee
algorithm (solid lines) on
GSM8K with reward model OASST as f and several different choices of The. Left: BoN-Alignmen initially improves accuracy Tee but eventually degrades as increases, while Inferencel inferenceTmmePesiine imePessimiss is monotone, as predicted by our theory. Right: BoN-Alignmen Alignment overoptimizes the reward model, with high but lower accuracy N increases, whereas InferenceTion Pessssim sm stops increasing 7 with beyond certain threshold determined by regularization parameter.
examinations of the reward model's tail behavior and robustness
basis, with respect to the true reward r* and the prompt X.
demonstrations of InferenceTimePesseeeeee to choice of hyperparameter.
Our algorithm, InferenceTimePessiimie is closely related XPO (Huang al., 2024b). training- time offline alignment algorithm that aims to miti- gate overoptimization via regularization with the x²- divergence. inferenceTTmePesiiiii sm also leverages x²- regularization, but implements this purely at inference-time via novel rejection sampling scheme.See Appendix A.1 for a detailed discussion of connections alignment.Finally,
1.2. Related Work
To our knowledge, our work provides the first theoretical framework for understanding and mitigating overoptimiza- tion in inference-time alignment. Various works have analyzed specific properties of the Best-of-N alignment algorithm (Yang et al., 2024b; Beirami et al., 2024; Mroueh, 2024) such as tradeoff's between reward and KL-divergence, but do not ultimately provide guarantees on performance when the estimated reward model and true reward are mismatched. We focus on analyzing Best-of-N specifically because it is the most widely used and foundational inference-time alignment technique, but other algorithms (Welleck et al., 2024) including variants of rejection sampling (Khanov et al., 2024; Chen et al., 2024: Shi et al., 2024; Liu et al., 2024a; Jinnai et al., 2024) and Monte-Carlo Tree Search (Feng et al.; Yao et al., 2024; Zhang al., 2024), are also used in practice.
offline analysis draws on the treatment of approximate rejection sampling in Block & Polyanskiy (2023), which tightly characterizes the performance of rejection sampling with unbounded likelihood ratios.
2. Inference-Time Alignment Framework
In this section, we formally introduce our inference-time alignment framework, then use to prove lower bounds that highlight the necessity of coverage. In our frame- work, the algorithm designer begins with base policy Tef X + A()),, which is conditional distribution mapping prompis
Our work also closely related to research on offtine align- ment training time (Christiano, 2014; Ouyang al., 2022; Rafailov et al., 2023), which involves fitting a re- ward model F (typically through pairwise feedback), and then maximizing it using RL. A growing body of theoret- ical works on offline alignment provide theoretical guar- antees for mitigating reward overoptimization that-like our work- depend on notions of coverage for the base pol- al., 2023b: Xiong al., 2024; Liu et al., 2024b; Cen al., 2024; Fisch et al., 2024; Ji et al., 2024; Huang et al., 2024b). Our formu- lation for inference-time alignment can be viewed as a vari- ant of this problem that abstracts away the reward model training, in particular, we take as given and ask how to achieve the best possible performance on a per-instance
X to distributions over responses E y, and Trer | x) is the probability that the base policy generates a response given the prompt x.? The algorithm designer also access to an imperfect reward model F X y -> [0, Rmax], where Rmax 2 1, and the reward label f(xx, v) estimates the quality of the response y for the prompt This serves as a proxy for the true reward model r' X x y [0, Rmax], which is unknown.
icy (Zhu et al., 2023; Zhan et al., 2023a;
Given the base policy Fref, the reward model F, and
"The motivating special case is autoregressive language mod- cling, where y y for vocabulary space and sequence length H, and nie has the autoregressive structure nie (2):H x) = =I Tee 91---1 for y = 91:1 E y.

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
prompt x X, the goal is produce high quality response 7 E y' measured by the true reward r*, in the
et al. (2024a) and abstract it as statistical problem, where computational efficiency is quantified via the number of samples and labels queried from the base policy and reward model.
sense that the following inference-time regret is small.
Reg.- (7;x)= := J ;x) (fix) E,
(2)
Definition 2.2 (Sample-and-evaluate framework), In the sample-and-evaluate framework, the algorithm designer does not have explicit access to the base policy Tret or the reward model F. Instead, they access Tee and through sample-and-evaluate queries: For given prompt I E X, they can sample N responses y1, y2.... yy Tres(- | x)) and observe the likelihood (ve | ()) and reward model value F(z,, V:) for each such response. The efficiency of the algorithm is measured by the total number of queries N.
Here, x²* can be viewed as a comparator policy with high reward, and J(T:: 2) := Ex
(r (z. y)] denotes the expected reward under r- for any policy л. When the response y is chosen by a randomized algorithm A, we use TA(- z) to denote the conditional distribu- tion over responses induced by A, and write regret as (f: == J(TT: :)) - -(
In applications, the base policy re represents a language model trained in some manner. The true reward r" can represent the extent to which y agrees with human pref- erence, passes a proof checker, or passes unit test suite. The reward model f can be an open source reward model, a model trained by the algorithm designer themselves, or even derived directly from Tee itself (Wang et al., 2022; Huang et al., 2024a; Song et al., 2024).
This is a natural statistical abstraction for computation- analogous to oracle/query complexity in optimization (Nemirovski et al., 1983; Traub et al., 1988; Raginsky & Rakhlin, 2011; Agarwal al., 2012), and learning theory (Blum et al., 1994; Kearns, 1998; Feldman, 2012; 2017) and encompasses Best-of-N alignment and other schemes such as rejection sampling (Khanov et al., 2024; Chen et al., 2024; Shi et al., 2024; Liu et al., 2024a; Jinnai et al., 2024).
Reward model quality versus regret. There is no hope of making the regret in Eq. (2) small without requirements on the fidelity of the reward model F. For prompt x E X, we measure the quality of P via the expected squared error with respect to r-, where responses are drawn by the base policy Tee
2.1. A Skyline: The Necessity of Coverage
To motivate main algorithmic results, and as step to- ward answering question Q1, we begin by proving a lower bound on the best possible regret one can hope to achieve, as determined by the reward model's error (x). This lower bound highlights the importance of the base policy's coverage, defined formally for a comparator policy x² via
ex((x)= = By-ana(( (m) (f(a,V)- (x.))))) -a.
(3)
Empirically and in theory, one can minimize Eq. (3) by fitting i' to rewards or human preference data for responses generated from ref (cf. Appendix A. which is already standard in post-training pipelines. As our focus is inference-time interventions, we simply abstract the reward model training step away and assume we have reward model f with error e as defined in Eq) We aim to understand how small we can make the regret in Eq. (2) as a function of the reward model quality eăm, and what algo- rithmic interventions are required to achieve this (cf. Q1).
n (y
x) x))
C (x) := E Ey (11)) Fref (y
(4)
Proposition 2.3 (Necessity of coverage). Fix a prompt x e
X, and Fee X - A(Y)) For any aligument algorithm A and any 16 S C* S max reward function r* and reward model 7 satisfying Eq. (3) and comparator policy It" with C* (x) S C" such that
C* (x)), there exists
1 4 V V (Z)( 2
Remark 2.1. In practice the reward estimation error in Eq. (3) may not be the tightest notion of reward error, and thus our bounds may be conservative. Nevertheless, it is ar- guably the most common formulation of reward mismatch (Zhu et al., 2023; Zhan et al., 2023a; Xiong et al., 2024; Gao el al., 2024; Huang et al., 2024b), and serve as a foun- dation for future investigations into other notions of error.
J(
Coverage in the sense of Eq. (4) plays a central role in the theoretical study of offline alignment (Zhu et al., 2023; Zhan et al., 2023a; Li et al., 2023b; Xiong et al., 2024; Liu et al., 2024b; Cen al., 2024; Fisch et al., 2024; Ji et al., 2024; Huang et al., 2024a:b), and Proposition 2.3 shows that it plays a similar role for inference- alignment. Re- cent works show that standard language models can indeed exhibit favorable coverage over desirable responses in stan- dard tasks of interest, which translate to performance gains at inference time (Brown et al., 2024; Snell et al., 2024; Wu et al., 2024b). In the remainder of the paper, we will
Measuring computational efficiency via query complexity. The next question we consider (cf. Q2) is how much com- putation is required to minimize the inference-time regret in Eq. (2) for a given prompt x. To allow for computational understanding that is agnostic to the architecture or description of re and P, we draw inspiration from Huang
4

---

Geverage,Scalinggg and Optimality in inference-Time Alignment
Algorithm 1 Best-of-N Alignment (BoN-Alignment
The main regret bound in Eq. (5) has two terms of interest. The first, which scales as roughly c (a), decreases as the sample size increases, and reflects the extent to which the set of responses y1..... UN ~ Teee(- | 2)) contains enough information to compete with x². Intuitively, as N grows, there is a higher probability of drawing a response that, under the true reward r", is at least as good as one from the comparator '². However, r* is not available to the learner, who instead evaluates response quality using the imperfect proxy F. There becomes a greater risk of overfitting to errors in F as N increases, and candidates are drawn from the tail of the base distribution where f is more error- proore. The cost of this overoptimization is expressed in the second term of Eq. (5), VN N.E. (T)( which increases with sample size and leads to arbitrarily large regret as N is scaled.
input: Prompt æ, queries N, reference policy Trofs
reward model F
1: Draw VN = (31..... yN) ~ [rer(-] (- [x) i..d.
2: Query F for reward labels (F(2, y1), ..... F(a, UN))
3: return response = arg max ye f(z, Us)
explore the extent to which this skyline can be achieved through existing techniques, or through new interventions.
Additional notation. We adopt standard big-oh notation, and write ff S as shorthand for f = Ogg) and f = (gg) to denote f = Ogg max(1, (1, polylog(g))).
3. Understanding Best-of-N Alignment As our first result, we give a sharp analysis of Best-of-N alignment, highlighting the role of coverage in determining its scaling properties and (sub-) optimality.
Because sample size is the only parameter in BoN-Alignment, it plays dual, but opposing, roles in both performing regularization (smaller N to stay on- support) and increasing response quality (larger N to draw good responses). The optimal choice of N must balance gains in quality with risk of overoptimization and be large but not too large, which leads to the second guarantee in Theorem 3.1. Eq. (6) resembles the idealized lower bound in Proposition 2.3 but has slower rate, scaling with ERM (z) this dependence is fact tight.
3.1. A Sharp Analysis of Best-of-N Alignment In Algorithm we display the Best-of-N algorithm for an input prompt x E X. BoN-Alignment draws N candidate responses V1 .......2 BN ~ (rer(- x) i.i.d., and returns the response y E Fyy that has the largest reward under the reward model F. Next, for a fixed prompt x and sample size parameter N, let (x))(()) E A()) denote the policy corresponding to the distribution over responses output by BoN-Alignment, which is random variable depending on draws of candidate VNN ~ Teef. which, given x E X, draws N responses y/,,... YN ~ Tree(- x) i.i.d., and returns the response 9 = arg max,, f(zz y.). Our main guarantee for BoN-Alignment bounds the regret in terms of the sample size N, the coverage coefficient C=" (x), and the reward model error (x).
2/3 2/3(2) instead of (=)()). 4 The following result shows that
Theorem 3.2 (Lower bound for BoN- CON-Alignment) For any ERM E (0, t] and N Z 1, there exists problem instance with Em(()) S ERM and comparator policy x² with C (x) = Ö()), such that, for any x E X, BoN-Alignment
has regret
J(n" ;x)) [[TTON ; xx) 2 π N e
Theorem 3.1 (Guarantee for BoN-Alignment), For any prompt I X, reward model error (=)(x) (0, 1]. and comparator x², whenever N 2 c Cx
Further, for all N E N. there exists problem instance sat- isfying the same conditions such that BoN-Al BoN-Alignment has
log( (Rmax/ERM(22 for a sufficiently large constant the
J(T ;z)= - [[ ;x) 2 Q 2/3) ERM
(8)
BoN-Alignman policy Tin salisfies
J (x=; -J I))
(5)
Eq. (7) shows that the regret indeed grows as N is scaled, and is an algorithm-dependent lower bound that reflects the consequences of overfitting in BoN-Al MoN-Aliggment. This is a serious concern since, when scaling N in practice, it may be impossible to know the sample size beyond per-prompt which overoptimization occurs, especially basis. Then, building on Eq. (7), the bound in Eq. (8) shows that E 2/3((r) is the best possible error achievable by BoN-Alignment, which matches the upper bound in
CF (x) (Rmae/
X Rmax
VN- N (x))
N
$ er" log( Rmmse/ / (z)(
In particular, as long as N x ( (RmnnCC*
RRmm
(m(
;x - J (TFBNN :z)
(6)
1/3
< RRmax Ca (2))))((1)))
ex)( log( (Rmm/sm(x)))
*The bound in (6) is larger than the bound in Proposi- tion 2.3 in the non-trivial regime where (C" (x) - 1/2 < Rmax-
'ee use N x D to indicate that C < N s C2 -0 for any
sufficiently large absolute constants Ci S Cz.
5

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Eq. (6). In other words, irrespective of the amount of computation, BoN- BoN-Alignment may fail to achieve the optimal skyline for regret in Proposition 2.3.
Algorithm 2 Inference immeresncciimeeessmmiii....
input: Prompt x, reference policy Rref reward model f. query size N, regularization coeff. 0.
1: Draw VN := (yI.... ................................ yN) Lid. Trer(- x). (Algorithm 3), compute
The suboptimality stems from the dual role of N, which serves as the regularizer, but is only a weak one at best. In particular, .V cannot be safely increased to sample bet- ter candidates without disproportionately increasing the risk of overfitting. This insight motivates the algorithms we develop in Section 4, which mitigate overoptimization through more refined form of regularization and use of
Using ComputeNormCons normalization constant A(x)) such that
1
Σ relu (8 (F(a,)) -x(x))) =1. WEiN
(9)
inference-tine time computation.
3: Sample resp- y RejectionSamplingg (Algorithm 5), where M = Ban [((s) and
Teef,
Remark 3.3 (Proof technique). The lower bound in Eq. (7) is algorithm-specifee and the construction exposes the cost of overfitting to errors in f, specifically, for responses with small probability under The that are drawn when N is relatively large. To prove Eq. (8), first leverage an iifommttion-theoretii argument showing that if N < poly (c" (x), ) no algorithm can extract enough information compete with n². Combining this regime with the one in Eq. (7) yields Eq. (8).
w(y σ) == relu (F(,,)) -((,,,))((ss))
return: response y.-
4. Inference-Time Pessimism
We now present InferenceTimeeesto inference-time alignment method that implements a statistically sound regularizer purely at inference time. In contrast to GoN-Alignment separates the scaling parameter (N) from the regularization parameter, and is thereby able achieve the performance skyline in Proposition 2.3. It is, as result, also scaling- monotone- as N is increased, it does not overfit or lose performance. We first give an algorithm overview, then state the main theoretical guarantee.
an optimal
3.2. Stronger Guarantees under Uniform Coverage Per Theorem 3.2, the regret of BoN-Alignment must scale with 2/3 (z) in general. However, it does enjoy tighter guarantees when a stronger form of coverage the uniform coverage coefficient- bounded: ="((aa)
inferenceeiiePessiiii
C (1) == supyEy (n(()=))
Theorem 3.4 (BoN-Alignment under uniform coverage). For any x E X' and comparator policy x², if 2 C% (I:).
4.1. The Inference-Time Pessimism Algorithm
the Bol-Alige Aliggment policy TBON satisfies
The imffeeeceeimePesiiiie Algorithm 2. For a regularization parameter 3 > O, the algorithm is designed to sample from the distribution
algorithm is displayed in
=(T";z) x) - JJ x)
x Rmax exp(-N/oz' (m)) V N .
T u) == Ter u) relu(3-'(Aaa.)) (F(a.)) X(=)),, (10)
In particular, as long as N x CT (loo//
where relu(z) == max (2, 0}. and A(x) is a normalization constant chosen such that
J(x" ((=";=)= J (fron x) E Cz (x) (x)(x) (og((Re//eenn (n)))
Σ TreFly x) DEy
A(x))) = 1. (1))
When we are willing pay for uniform coverage, the re- gret of BoN-Alignment scales (z), which matches the statistical rate in the skyline of Proposition 2.3. This suggests that BoN may already be sufficient in some cases, at least when it is possible to tune N optimally; we revisit this point empirically Section 5. Generally, however, we expect that C% (x) > C" (z)) making Theorem 3.4 highly suboptimal relative to the skyline. For example, softmax policies, which normalized exponentials of the logits, can have exponentially large C% while C*" is Õ(1). This is (loosely) the case in the lower bound construction The- orem 3.2, where re is an exponential policy, and is up- weighted by an exponential multiplier to form a x* that is more sharply peaked on r*
The distribution in Eq. (10) is the exact solution to the
x2 reguulrrie reinforcement learning objective: defining
(=(((( |I (x) = E Ey-ra((1z)) x(ylz) - 1)
[(( 1) as the x2 -ivvergee,e,, we have
D2e(p) Tz(x) = arg max (ByppF((x - -BDD (x)) pEA())
As we discuss in the sequel, the x² rreeulrarre adapts to the uncertainty in the reward model f(x, y). so that the regular- ized policy in Eq. (10) implements pessimism in the face of uncertainty, a principle from offline reinforcement learning
6

---

Theorem 4.2 (Query complexity lower bound). For any ERM E (0, 1/4] and N S 1, there exists a problem instance with Rmax 1, Eam (r) S Ean- and comparator policy x² with Ca (x) = Ca' ō(1) such that any algorithm A queries must have Coverage, Scaling, and Optimality in Inference-Ting Alignment
that carries strong guarantees (Jin et al., 2021; Rashidine- jad al., 2021; Huang et al., 2024b). In particular, Huang et al. (2024b) showed that xerreaularization at training time can achieve the skyline in Proposition 2.3; our method im- plements similar regularization but at inference-time, and attains those same guarantees.
InferenceTimeeessiine satisfies
; - [TPes: 2))
(12)
S v CT (x) - (x)(
3- C* (z) + ( (
Setting B x
(x)
as long as N 2 5(V
R -C (a)
2 (a)
The pessimistic ze-reuulaiization prevents the algorithm from overfitting to potentially misleading responses, e.g., those in the tail of the base distribution for which (ref x) small and F(x,, y) is erroneously estimated to be large. The parameter 3 > 0 controls the degree of pessimism, with small values inducing a greedier policy, and large values inducing a conservative, heavy-tailed distribution over responses. For any choice of B. however, there is a set performance level the algorithm will never drop below, even as N oc.
we have
a());a)) - J (TTe: & V (('((() (I) o (x).
(13)
On the statistical side, for any choice of the regularization parameter 3 > O, the regret bound in Eq. (12) balances overoptimization (reflected in the term B-1, x (x)) with bias (reflected in the term B C (z)). Choosing B to balance these terms leads to the regret bound in Eq. (13), which matches the lower bound in Proposition 2.3 up to ab- solute constants, showing that inferencceTiePPessee is regret-optimal.
To (approximately) sample from the optimal x² regularized policy in Eq. (10), Algorithm proceeds in two steps. First, since the normalization constant (xx) in Eq. (11) is unknown, the algorithm computes an approximate normalizer X(z). It draws N responses IN (y1,....y' i.dd Teer( 2) and uses them to solve Eq. (9), an empirical approximation to Eq. (11). This is accomplished via the dynamic programming subroutine in ComputeNormConstaan Cont (Algorithm 3), in ONN log N) time. See Appendix C for details.
Computationally, achieving the regret bound in Eq. (12) re- quires N 2 [2 (2(Raz) In contrast to Best-of-N (Theo- rem 3.1), infferenceTimePesiiiiii mization, in the sense that for any fixed 3 >> 0, the guaran- tee in Eq. (12) holds for all N sufficiently large, and there is no risk of dropping below the bound on the right-hand side of Eq. (12) we scale computation; we refer this property as mondiin-monotonicttyy
is robust to overopti-
Next, Inference imtressimmmeessiiiiii generates samples from (approximately) the policy Eq. (10) using classical rejection sampling (Von Neumann, 1963; Block & Polyan- skiy, 2023); Algorithm 5 in Appendix D. Given rejection sampling threshold M > 0, the algorithm draws another set of responses 2N = V1.-.., UN- For each response i, it samples a Bernoulli random variable & ~ Ber (FF0)8-((((a.))--) M
Lower bounds InferenceT InfeernneeTimPessee TimePessimsm requires N
and compute-optimality.
>
s VCC (z) Ranox samples to achieve the optimal (ax(*)
regret bound Eq. (13), where 9 x
(a)a (z) The following
result shows that the ()M(x) dependence is necessary for any algorithm in the sample-and-evallie framework.
A 11). and returns y: as the final response if & 1. By the heavy-tailed nature of the idealized reeeuluard distribution in Eq. (10), rejection threshold of M Rs Ran is sufficient. Accounting for both the normalization constant computation and re- jection sampling phase, a total of N = Ō Ress samples
5m
using at most N sample-and-evalln
9
ensures that the response distribution of Algorithm is good approximation of Eq. (10).
J(T)) - J( =((/N).
This result implies that any algorithm achieving the lower bound in Proposition 2.3 requires N 2 [.u(a]] which is matched by the guarantee for InferenceTimePessinn (Thcorem 4.1). Morcover, when N S _ the regret can be even larger than the reward estimation error Ew.- since 1/ 2 Emn- We remark that the computational cost here is comparable (though slightly larger) than the cost of achieving the sub-optimal bound in Eq, (6) using Best-of-N
4.2. Theoretical Guarantees
We now bound the regret for InferenceTimePessi sm, which achieves the skyline rate of Proposition 2.3 with coverage coefficient C*. (z:).
Theorem 4.1 (Guarantee for For any 8 0 and (z) E 10. if N >
Rmw Rmo log [2))((2)
for sufficiently large constant e,
(roughly N 2 e (
(x) versus
2 ERM
-2/3 (I)))
7

---

Coverage, Scaling, and Optimality in Inference-Ting Alignment
30
21a
225
Lin in Accuracy over firt
212
200
210
Estimated Reward
175-
150
2a
125
Gemma (2B)
24
Llama (3B)
-10
Phi-3 Mini
Mistral (7B)
10
20
10-3
10-1
260
10-2
10
Figure 2. Compute-normalize comparison of InferenceTimePessiiiss (solid lines) and BoN-Alignment (dashed lines) on GSM8K with OASST as F2 as function of regularization parameter We run BoN-Al with N 2 and run Inference weannceimeeeesmiiee can improve significantly over BoN-Al All-All gnneett for large N due to the reward overoptimization. Center: Number of responses required for InferenceTimePess
until rejection sampling accepts (capped to N = 2 Left: ieeerenceTmePeesinnee
to accept an answer decreases as B increases, as predicted by our theory. Right: Estimated reward F for Inference imeeessimis sm decreases as / increases.
Parameter tuning and practicality. As presented has two
and policy n. (2,
in Algorithm InferenceTimePessiii parameters, 3 and N, compared to the single param- eter N used by BoN-Alignment. This separation enables the optimal and scale-monotonic guarantees for imePessimism, and we also view it as a beneficial feature from a practical perspective: by using two parameters, we achieve clear separation between tuning the computational budget (through N) and tuning the statistical performance (through B). While to achieve Eq. (13) 3 must be chosen based on potentially unknown parameters (C* (x) and (z)), this represents a meaning- ful improvement over BoN-Ali aoi-meig,,,n,, which cannot be tuned to achieve Eq. (13) even when these parameters are known (Theorem 3.2). This is because BoN-Alignment conflates computational and statistical considerations in its single parameter N.
V1+ || Tee(()))) Ey (A v)].
Of course, we cannot sample from Th itself because the distribution depends on the "true" normalization constant A(x) in Eq. (11). To address this, we prove robustness result showing that, given a X that approxi- mately normalizes the distribution in Eq. (10), the policy relly))))rell( ((P(a.))-1I)
7 x) = Eye Farr re) (Flu (F(a..")-))) X)) achieves a regret bound that matches Eq. (12) up to absolute constants. From here, a concentration argument implies that the A(x) computed in Eq. (9) is an approximate normalizer whenever 2 Pag,, with high probability.
Finally, we leverage analysis for rejection sampling to " x)
show that, as long as N 2 max,ey (ally log(1/5), the rejection sampling procedure will terminate and return y 3 (- x)) with probability at least 1 - 8. Critically, due to the heavy-tailed nature of the x²-regularizer, this density ra-
Empirically, we find that for any fixed choice of 8, inferenceTTmePessiiie
is robust to overfitting when computation and sample size is increased, with perfor- mance essentially monotonic as N grows (Figure 10), as predicted by the guarantee in Eq. (12). Because of this robustness, is easier to tune the parameter 3, which also find is important to achieve strong performance; further discussion and practical guidance is provided in Section 5. Altogether, we believe it is most natural to in- terpret Inference imeeesssmise im as a "single-parameter" algorithm where only needs to be tuned, and N is as large as the computational budget allows.
(xla) Rime, which yields the claimed tio is bounded as (gla)) B query complexity bound. This observation highlights an important computational benefit of xr=regularizztion that goes beyond its statistical benefits, illustrated below.
Remark 4.3 (Comparison to KL-regularization) Liu et al. (2023); Li et al. (2024a) use rejection sampling to simulate samples fromle the KL-regularized distribution:
XL (y x) == arg max (TEx(TE (T (0 v)) B DRL(P (x)) T
PEA())
which satisfies This has two issues. First, as shown by Huang et al. (2024b), this distribution can fail to achieve the guarantee in Eq. (13), no matter how 3 is chosen. Second, the density ratio exponential in general, i.e. " (b(())) [a[by) 2 exp Runz which means that N Z exp( BBy queries are required to simulate it with rejection sampling.
Overview of analysis. The proof of Theorem 4.1, and has three parts. First, we show that the idealized rregulariz distribution in Eq. (10) achieves the regret bound in Eq. (12), This follows the same reasoning as the analysis of training-tin time interventions based on <erreulaarization in Huang et al. (2024b), and uses the property that for any function (x, y) (we use A(x, y) [(( v) (x, v)
sample-and-evall
8

---

does not terminate. As we scale N, observe the characteristic dip (e.g., Gao et al. Coverage, Scaling, and Optimality in Inference-Time Alignment
Table I. Performance of re -Phi-3-Minn (% Lift in Accuracy over Teef).
Task
OASST
GEMMA-RM RM
LLAMA-RM
ARMO-RM
GSMBK (Pessimism)
0.87 + 0.94
5.61 = 0.92
12.03 = 0.90
12.44 - 0.88
GSMBK (BoN)
-5.61 + 1.13
4.10 + 1.08
12.12 = 0.95
13.12 + 0.96
MMLU (Pessimism)
-0.71
14.29 5.24
24.48 = 5.55
21.12 5.58
MMLU (BoN)
5..61
7.57 + 6.05
25.41 + 6.10
16.20 6.42
MATH (Pessimism)
3.41 3.84
18.36 + 4.02
41.47 + 4.30
26.72 + 3.98
MATH (BoN)
3.32 + 3.98
15.36 + 4.27
41.74 + 4.35
21.72 + 4.19
5. Experiments
Table collects similar results across all tasks GSM8K, MMLU, and MATH and reward models OASST, GEMMA-RM, LLAMA-RM, and ARMO-RM, with Phi-3-Mini as the base policy Teef- We use fixed computational budget, and compare the naive BoN-Alignment for N 218 with InferenceTimmPessimme Appendix B for further details). Here, we find that Inf InferenceTimePessiinn performance than MoN-Alignment, although in many instances this difference is not statistically significant; we suspect this is because, when r* is binary (as it is in all tasks we use), there is no separation between C* and C% when x' is the optimal policy (uniform over the set of correct answers); thus, we are in the regime where Theorem 3.4 predicts near-optimal performance for BoN, However, a different story may emerge under more refined evaluation metrics, such as the correctness of proofs in addition to the final answer. Here we should expect C >> C=', and we leave evaluation in more realistic environments to future work. For the sake of space, we defer further empirical results Appendix B, including plots and tables analogous to Figures I and 2 and Table for other policies, tasks, and rewards (Appendix B.2) as well as additional experiments (Appendix B.3).
In this section, we complement our theoretical results with suite of experiments that investigate the practicality of Inference ieereneeiieeeeemimii
and compare its performance to that of BoN-Al BoN-Alignment, We consider three standard tasks: the test split of the elementary school math dataset GSM8K (Cobbe et al., 2021); math and chemistry splits of MMLU (Hendrycks
for the best 3 (see
al., 2020), and the test split of the advanced math problems dataset MATH (Hendrycks et al., 2021). We also present preliminary study with A1pacaEval-2.0 (Li et al., 2023a) in Appendix B. We consider four reward models in increasing order of size: OASST (1.4B) (Köpf et al., 2024), GEMMA-RM (2B) (Dong et al., 2023), LLAMA-RM (3B) (Yang et al., 2024c), and ARMO-RM (7B) (Wang et al., 2024a). Finally, for each task we consider subset of four policies for the base model: GEMMA-2-2B (Team et al., 2024), LLAMA-3-38 (Dubey et al., 2024), Mistral-7B (Jiang et al., 2023), and Phi-3-Mini (Abdin et al., 2024). For each task-policy- reward triplet, and each prompt, we generate a large number of responses (20K) and conduct experiments by bootstrapping subsamples of this large set. all cases, we reuse the same samples for normalization constant estimation as for the rejection sampling step.
tends to have higher average
To produce Figure we compare the performance of InferenceTimePessimgg BoN-Alignment for a range of N in terms of both true reward (accuracy) and estimated reward (f is OASST) on GSM8K, defaulting to BoN-Alignment if InferenceTimepesse
6. Conclusion
(with tuned (8) and
Our results reveal the interplay between coverage, scal- ing, and optimality in inference-time alignment, and high- light the benefits of deliberate compute scaling. Beyond providing optimal algorithms and insights into the performance of BoN-Al innmennt,,,, our framework can serve as starting point toward a founda- tional understanding of inference-time computation more broadly. In particular, our work raises a number of in- teresting directions for future research, including mov- ing beyond the worst-case assumption 7 and design- ing inference-aware training procedures that optimize for Inference T imeesss intesssmiiss imism at generation time.
(2023)) in accuracy of BoN-Al MoN-AAlgmet igneett in the left panel; from the right panel, we can infer that this is caused by reward overoptimization. On the other hand, we find that the accuracy of increases with N, as predicted by Theorem 4.1. To further investigate the effect that regularization has on Inference wwweenceiiePeeeimmm.. sm, in Figure 2, we fix compute budget of N 2 and compare the performance of MoN-Alignment to inferenceTimePesse the regularization parameter B. As we increase B, we see that infereencTiieeesssiini leads to improved true reward (Left), a smaller computational budget (Center) and significantly less reward overoptimization (Right).
monotonically
we vary
9

---

Coverage, Scaling, and Optimality in Inference- Time Alignment
Impact Statement
Chang, J. D., Shan, W., Oertell, O., Brantley, K., Misra, D., Lee, J. D., and Sun, W. Dataset reset policy optimization for RLHF, arXi::244.008995 2024.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, R., Zhang, X., Luo, M., Chai, W. and Liu, Z. Pad: Personalized alignment decoding-timm time. arXiv:2410.04070 2024.
References
Chen, X., Zhong, H., Yang. Z., Wang, Z. and Wang, L. Human- th-thp-loop: Provably efficient preference-basee reinforcement learning with general function approxima- tion. In International Conference on Machine Learning. PMLR, 2022.
Abdin, M., Aneja, J., Awadalla, H., Awadallah, A., Awan, A. A., Bach, N., Bahree, A., Bakhtiari, A., Bao, J., Behl, H., et al. Phi-3 technical report: A highly capable lan- guage model locally on your phone. arXiv:2404.14119, 2024.
Agarwal, A., Bartlett, L., Ravikumar, P., and Wainwright, M. Information-theone lower bounds on the ora- cle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58(5):3235-3249, 2012.
Chollet, F,, Knoop, M., Kamradt, G., and Landers, B. Arc prize 2024: Technical report. arXiv:2412.04604, 2024.
Chow, Y. Tennenholtz, G., Gur, I., Zhuang, V., Dai, B., Thiagarajan, S., Boutilier, C., Agarwal, R., Kumar, A., and Faust, A. Inference-aware fine-tuning for best-of-n sampling in large language models. arXiv:2412.15287. 2024.
Amini, A., Vieira, T., and Cotterell, R. Variational best-of- alignment. (tt.:2407.00077 2024.
Balashankar, A., Sun, Z.., Berant, J., Eisenstein, J., Collins, M., Hutter, A., Lee, J., Nagpal, C., Prost, F., Sinha, A., et al. Infalign: Inference-aware language model align- ment.
Christiano, Online local learning via semidefinite pro- gramming. In Proceedings of the 46th Anmual ACM Sym- posium on Theory of Computing, pp. 468-474. ACM, 2014.
2024.
Beirami, A., Agarwal, A., Berant, J., D'Amour, A., Eisenstein, J. Nagpal, C., and Suresh, A. T. The- oretical guarantees on the best-of-n alignment policy. arXiv:2401.01879 2024.
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from hu- man preferences. Advances in Neural Information Pro- cessing Systems, 2017.
Block, A. and Polyanskiy, Y. The sample complexity of approximate rejection sampling with applications to smoothed online learning. In The Thirty Sixth Annual Conference on Learning Theory, pp. 228-273. PMLR, 2023.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M.. Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXh::21 2021.
Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., and Rudich, S. Weakly learning DNF and characteriz- ing statistical query learning using Fourier analysis. In Symposium Theory of Computing, 1994.
Das, N., Chakraborty, S., Pacchiano, A., and Chowdhury, S. R. Provably sample efficient RLHF via active prefer- ence optimization. arXiv:2402. 10500, 2024.
DeepSeck-AI. DeepSeek-RI: Incentivizing Reason- ing Capability in L.IMs via Reinforcement Learn- ing. 2025. URL https: thub. com demm/eeepeek-all Rd.p
Brown, B., Juravsky, J., Ehrlich, R., Clark, R., Le, Q. V., Ré, C., and Mirhoseini, A. Large language mon- keys: Scaling inference compute with repeated sampling. arXiv:2407.21787, 2024.
Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang, T., Yang, S., Schuurmans, D., Chi, Y., and Dai, B. Value-incentivized preference optimization: A unified approach to online and offline RLHF. arXiv:2405. 19320, 2024.
Dong, H. Xiong, W., Goyal, D., Zhang, Y., Chow, W., Pan, R., Diao, S., Zhang, J., Shum, K., and Zhang, T. Raft: Reward ranked finetuning for generative founda- tion model alignment. 2rXiv:2304.06767, 2023.
Chakraborty, S., Ghosal, S. S., Yin, M., Manocha, D., Wang. M., Bedi, A. S., and Huang. Trans- fer q star: Principled decoding for Ilm alignment. -XXi:2405.20499 2024.
Du, Y., Winnicki, A., Dalal, G., Mannor, S.. and Srikant, R. Exploration- driven policy optimization in RLHF: Thcoretical insights on efficient data utilization. arXiv:2402. 10342, 2024.
10

---

Coverage, Scaling, and Optimality in Inference-Tims Alignment
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The Ilama 3 herd of models. arXiv:2407.21788, 2024.
Huang, A., Block, A., Foster, D. Rohatgi, D., Zhang, C., Simchowitz, M., Ash, J. T., and Krishnamurthy, A. Self-improvement in language models: The sharpening mechanism. arXiv:2412.01955/ 2024a.
Eisenstein, J., Nagpal, C., Agarwal, A., Beirami, A.,
Huang, A., Zhan, W., Xie, T., Lee, J. D., Sun, W., Kr- ishnamurthy, A., and Foster, D. J. Correcting the mythos of kl-reulaarizaton: Direct alignment without overoptimization via chi-squared preference optimiza- tion. arXiv:2407.13332 2024b.
D' D'Amour, A., Dvijotham, D., Fisch, A., Heller, K., Pfohl, S., Ramachandran, D., al. Helping or herding? reward model ensembles mitigate but do not eliminate reward hacking.
2023.. 2023.
Feldman, V. A complete characterization of statistical query learning with applications to evolvability. Journal of Computer and System Sciences, 2012. 2012
Ji, X., Kulkarni, S., Wang, M., and Xie, T. Self-play with adversarial critic: Provable and scalable offline align- ment for language models. arXiv:2406.04274, 2024.
Jiang, A. Q. Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. 1., Bressand, F,, Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b. arXh::3310.06825 2023.
Feldman, V. A general characterization of the statistical query complexity. In Conference on Learning Theory, 2017.
Feng, X., Wan, Z., Wen, M., Wen, Y., Zhang, W., and Wang, J. Alphazero-like tree-search can guide large language model decoding and training. In NeurlPS 2023 Founda- tion Models for Decision Making Workshop.
Jin, Y., Yang. Z., and Wang, Z. Is pessimism provably ef- ficient for offline RL? In International Conference on Machine Learning. 2021.
Jinnai, Y., Morimura, T., Ariu, K., and Abe, K. Regular-
Fisch, A., Eisenstein, J., Zayats, V., Agarwal, A., Beirami, A., Nagpal, C., Shaw, P., and Berant, Robust pref- erence optimization through reward model distillation. arXiv:2405. /9316, 2024.
ized best-of-n sampling to mitigate reward hacking for language model alignment. arXiv:2404.01054, 2024.
Kearns, M. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 1998.
Frick, E., Li, T., Chen, C., Chiang, W.-L., Angelopou- los, A. N., Jiao, J., Zhu, B., Gonzalez, J. E., and Stoica, How to evaluate reward models for rlhf. 2rXiv:2410.14872 2024.
Khaki, S., Li, J., Ma, L., Yang, L., and Ramachandra, P. Rs-dpo: hybrid rejection sampling and direct pref- erence optimization method for alignment of large lan- guage models. arXiv:242..100:0 2024.
Gao, L., Schulman, J., and Hilton, J. Scaling laws for ward model overoptimization. In International Confer- ence on Machine Learning, 2023.
Khanov, M., Burapacheep. J., and Li, Y. Args: Alignment reward-guided search. arXiv:2402.01694 2024.
Köpf, A., Kilcher, Y., von Rütte, D., Anagnostidis, S., Tam, R., Stevens, K., Barhoum, A., Nguyen, D., Stan- ley, O., Nagyfi, R., et al. Openassistant conversations- democratizing large language model alignment. Ad- vances in Neural Information Processing Systems, 36, 2024.
Gao, Z., Chang, J. D., Zhan, W., Oertell, O., Swamy, G., Brantley, K., Joachims, T., Bagnell, J. A., Lee, J. D., and Sun, W. REBEL: Reinforcement learning via regressing relative rewards. arXiv:2404.16700 2024.
Gui, L., Gârbacea, C., and Veitch, V. BoNBoN alignment for large language models and the sweetness of best-of-n sampling. arXiv:2406.0m 008320 2024.
Li B., Wang, Y., Grama, A., and Zhang, R. Cascade reward sampling for efficient decoding- time alignment. arXiv:2406. 16306, 2024a.
Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J. Measuring massive mul- titask language understanding. 1xXi:20099003000 2020.
Li, X., Zhang, T., Dubois, Y., Taori, R., Gulrajani, I., Guestrin, C., Liang, P., and Hashimoto, T. B. Alpacaeval: An automatic evaluator of instruction-follooiing mod- els.
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring mathematical problem solving with the MATH dataset. In Thihty-fithh Conference on Neural Information Pro- cessing Systems Datasets and Benchmarks Track (Round 2), 2021.
5 2023a.
Li, Z., Yang, Z., and Wang, M. Reinforcement learning with human feedback: Learning dynamic choices via pessimism, arXiv:2305. 18438, 2023b.

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Li, Z., Liu, H., Zhou, D., and Ma, T. Chain of thought em- powers transformers to solve inherently serial problems. MIXi::2402.12875, 2024b.
Pacchiano, A., Saha, A., and Lee, J. Dueling RL: Reinforcement learning with trajectory preferences. arXiv:2111.04850, 2021.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. The Twelfth Inter- national Conference on Learning Reprexentations, 2023.
Pace, A., Mallinson, J., Malmi, E., Krause, S., and Sev- eryn, A. West-of-n: Synthetic preference generation for improved reward modeling. arXiv:2401.12085 2024.
Polyanskiy, Y. Channel coding: tal limits. Princeton University, 2010.
Liu, T., Zhao, Y., Joshi, R., Khalman, M., Saleh, M., Liu, P. J., and Liu, J. Statistical rejection sampling improves preference optimization. arXiv:2309.0665/ 2023.
Qiu, J., Lu, Y., Zeng, Y., Guo, J., Geng, J., Wang. H., Huang, K., Wu, Y., and Wang. M. Treebon: Enhancing inference-time alignment with speculative tree-search and best-of-n sampling. arXiv:2410.16033 2024.
Liu, T., Guo, S., Bianco, L., Calandriello, D., Berthet, Q., Llinares, F., Hoffmann, J., Dixon, I.., Valko, M., and Blondel, M. Decoding-tine time realignment of language models. ar Xii::2442.00992 2024a.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. Er- mon, S., and Finn, C. Direct preference optimization: Your language model secretly a reward model. Ad- vances in Neural Information Processing Systems, 2023.
Liu, Z. Lu, M., Zhang, S., Liu, B., Guo, H., Yang. Y., Blanchet, J., and Wang. Z. Provably mitigating overopti- mization in RLHF: Your SFT loss is implicitly an adver- sarial regularizer. arXiv:2405. 16436, 2024b.
Mroueh, Y. Information theoretic guarantees for policy alignment in large language models. arXiv:2406.05883, 2024.
Raginsky, M. and Rakhlin, A. Information-base com- plexity, feedback and dynamics in convex programming. IEEE Transactions on Information Theory, 2011.
Mudgal, S., Lee. J., Ganapathy, H., Li, Y., Wang, T., Huang, Y., Chen, Z., Cheng. H.-T., Collins, M., Strohman, T., et al. Controlled decoding from language models. In Forty-first International Conference on Machine Learn- ing, 2024.
Rashidinejad, P. and Tian, Y. Sail into the headwind: Align- ment via robust rewards and dynamic labels against re- ward hacking. arXiv:2412.0955 12.04444, 2024.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, Bridging offline reinforcement learning and imitation learning: tale of pessimism. Advances in Neural Infor- mation Processing Systems, 2021.
Nakano, R., Hilton, J., Balaji, S., Wu, J.. Ouyang, L., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., et al. Webgpt: Browser-assisted anestion-answeriig with hu- man feedback. arXiv: /2.0933, 2021.
Sessa, P. G., Dadashi, R., Hussenot, L., Ferret, J., Vieil- lard, N., Ramé, A., Shariari, B., Perrin, S., Friesen, A.. Cideron, G., et al. Bond: Aligning LLMs with Best-of-N distillation. UrXiv:247.11662. 2024.
Nemirovski, A., Yudin, D. B., and Dawson, E. R. Problem complexity and method efficiency in optimization. 1983.
Novoseller, E., Wei, Y.. Sui, Y., Yue, Y., and Burdick, Du- eling posterior sampling for preference-based reinforce- ment learning. In Conference on Uncertainty in Artificial Intelligence, 2020.
Shi, R., Chen, Y., Hu, Y., Liu, A., Smith, N., Hajishirzi, H., and Du, S. Decoding-time language model alignment with multiple objectives. arXiv:2406. 2.X.::4406.18853, 2024.
OpenAl. Gpt-4o-mini: A scaled-down variant of gpt-4, 2024a. URL https://openai.com com. Accessed: 2025- 01-24.
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. arXiv:2408.03314, 2024.
OPenAI. Introducing openai ol. Blog, 2024b. URL https: //openai. /o
Song. Y.. Swamy, G., Singh, A., Bagnell, J. A., and Sun. W. Understanding preference fine-tuning through the lens of coverage. arXiv:2406.014 044422 2024.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L.,, Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow in- structions with human feedback. Advances in Neural In- formation Processing Systems, 2022.
Stiennon, N., Ouyang, L.., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. Ad- vances in Neural Information Processing Systems, 33: 3008-3021, 2020.
12

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Stroebl, B., Kapoor, S., and Narayanan, A. Inference scal- ing faws:: The limits of IIm resampling with imperfect 2024.
Welleck, S., Bertsch, A., Finlayson, M., Schoelkopf, H., Xie, A., Neubig, G., Kulikov, I., and Harchaoui, Z. From decoding to meta-generation: Inference-time algorithms for large language models. UrXiv:2406.168388 2024.
verifiers. arXiv:2411.
Team, G., Riviere, M., Pathak, S., Sessa, P. G., Hardin, C., Bhupatiraju, S., Hussenot, L., Mesnard, T., Shahriari, B., Ramé, A., et al. Gemma 2: Improving open language models at a practical size. arXiv:2408.001/6 2024.
Wu, R. and Sun, W. Making RL with preference-based feedback efficient via randomization. arXiv:2310.14554, 2023.
Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaci, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C., Chen, M., Cucurull, G. Esiobu, D. Fernandes, J., Fu, J., Fu, W. Fuller, B., Gao, C.. Goswami, V., Goyal, N., Hartshorn, A., Hosseini, S., Hou, R., Inan, H., Kardas, M. Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P., Molybog, I., Nie, Y., Poulton, A., Reizen- stein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, E. M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, J. X., Xu, P., Yan, Z., Zarov, I., Zhang. Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T. Llama 2: Open foundation and fine-tuned chat models. arXiv:2307.09228 2023.
Wu, T., Yuan, W., Golovneva, O., Xu, J., Tian, Y., Jiao, J., Weston, J., and Sukhbaatar, S. Meta-rewarding language models: Self-improving alignment with um-as-a-meta- judge. arXiv preprint vrXiv:2407.195%4 2024a.
Wu, Y., Sun, Z., Li, S., Welleck, S., and Yang, Y. An empir- ical analysis of compute-optimal inference for problem- solving with language models. arXiv:2408.00724, 2024b.
Xie, T. Foster, D. J., Krishnamurthy, A., Rosset, C., Awadallah, A., and Rakhlin, A. Exploratory preference optimization: Harnessing implicit Qr-approximation for sample-efficient rlhf. arXiv:2405.21046. 2024.
Xiong, W., Dong, H., Ye, C., Wang. Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Con- ference on Machine Learning, 2024.
Traub, J. F., Wasilkowski, G. W., and Wožniakowski, H. Information-batt complexity. Academic Press Profes- sional, Inc., 1988.
Xu, Y., Wang, R., Yang, L., Singh, A., and Dubrawski, A. Preference-hasee reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 2020.
Von Neumann, J. Various techniques used in connec- tion with random digits. John von Neumann, Collected Works, 3:768-770, 1963.
Xu, Y., Sehwag. U. M., Koppel, A., Zhu, S., An, B., Huang, F., and Ganesh, S. Genarm: Reward guided genera- tion with autoregressive reward model for test-time align- ment. arXiv:2410.08199, 2024.
Wang, H., Xiong, W. Xie, T., Zhao, H., and Zhang, T. In- terpretable preferences via multi-objective reward mod- eling and mixture-of-expprts, In EMNLP, 2024a.
Wang, H., Xiong, W., Xie, T., Zhao, H., and Zhang, T. In- terpretable preferences via multi-objective reward mod- eling and mfxture-of-experts. arXiv:2406. /2845, 2024b.
Yang. A., Yang, B., Zhang. B., Hui. B., Zheng, B., Yu, B., Li, C., Liu, D., Huang, F., Wei, H., et al. Qwen2. 5 tech- nical report. arXiv preprint arXiv:2412.151155 2024a.
Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A., and Zhou, D. Self-consistency im- proves chain of thought reasoning in language models. 11X1v:2203.11171, 2022.
Yang. J. Q., Salamatian, S., Sun, Z., Suresh, A. T., and Beirami, A. Asymptotics of language model alignment. MDNiv:2404.0177 2024b.
Yang. R., Ding, R., Lin, Y., Zhang, H., and Zhang, T. Reg- ularizing hidden states enables learning generalizable re- ward model for 1lms. arXiv preprint 10221 2024c.
Wang, Y., Liu, Q., and Jin, C. Is RLHF more difficult than standard RL? arXiv:2306.1411 2023.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thoughh prompting elicits reasoning in large language models. Advances in neural information processing systems, 35: 24837, 2022.
Yao, S., Yu, D., Zhao, J. Shafran, I., Grifliths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances Neural Information Processing Systems, 36, 2024.
13

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Ye, C., Xiong, W. Zhang, Y., Jiang, N., and Zhang, T. A theoretical analysis of Nash learning from hu- man feedback under general KL-regularized preference. arXiv:2402.0731,, 2024.
Zhan, W., Uehara, M.. Kallus, N., Lee, D., and Sun, W. Provable offiine preference-based reinforcement learn- ing. In International Conference Learning Represen- tations, 2023a.
Zhan, W., Uchara, M., Sun, W., and Lee, D. Provable reward-agnostic preference-based reinforcement learn- ing. arXiv:2335518830, 2023b.
Zhang, D., Zhoubian, S., Hu, Z., Yue, Y., Dong, Y., and Tang, J. Rest-mets*: Llm self-training via process re- ward guided tree search. arXiv:2406.0380 03816, 2024.
Zhao, S., Brekelmans, R., Makhzani, A., and Grosse, R. Probabilistic inference language models via twisted sequential monte carlo. arXiv:2404.17546, 2024.
Zheng, L., Chiang, W.-L., Sheng. Y., Zhuang, S., Wu, Z., Zhuang, Y., Lin, Z., Li, Z., Li, D., Xing, E., et al. Judg- ing llm-as-a-judge with mt-bench and chatbot arena. Ad- vances in Neural Information Processing Systems, 36: 46595-46623, 2023.
Zhu, B., Jordan, M., and Jiao, J. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning, 2023.
14

---

Contents of Appendix
I Additional Discussion and Results
16
Additional Related Work
16
A.1
Connection Offline (Training-Time Alignment
16
Further Empirical Results
17
B.1
Further Experimental Details
17
B.2 Results for Further Policies and Tasks
18
B.3 Further Experiments
23
B.4 Results for AlpacaEval-2.e
23
II Proofs
25
Normalization Constant Computation
25
C.1 Background
25
C.2 Guarantee for ComputenlormConntant
26
D Rejection Sampling
27
D.I
Background
27
D.2
Guarantee for RejectionnSmpling
29
D.3
Lower Bounds..
31
Proofs from Section 2
32
Proofs from Section 3
34
F.1
General Regret Decomposition for iignmentt
34
F22
General Lower Bounds on Regret
................................
36
F.3
Proof of Theorem 3.1
44
F.4
Proof of Theorem 3.2
45
F.5 Proof of Theorem 3.4
45
F6
Additional Results..
45
G Proofs from Section 4
47
G.1 Proof of Theorem 4.1
47
G.2 Proof of Theorem 4.2
51
15

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Part I
A Additional Discussion and Results
A. Additional Related Work
In this section, we discuss additional related work in greater detail.
Theoretical analysis of inference-time alignment. Inference-tine alignment has received limited theoretical investigation so far. Most notably, various works have analyzed specific properties of the Best-of-N alignment algorithm (Yang et al., 2024b; Beirami et al., 2024; Mroueh, 2024) such as tradeoff's between reward and KL-divergence, but do not ultimately provide guarantees on downstream performance in the presence of mismatch between the estimated reward model and true reward. Our theoretical framewok-whhch abstracts the role of the base policy through caaple-and-evaluaal access is inspired by Huang et al. (2024a), who used a similar framework to give guarantees for the complementary problem of language model self-improvement, but our specific problem formulation and techniques are quite different.
Empirical algorithms for inference-time alignment. Empirically, the Best-of-N alignment heuristic (Stiennon et al., 2020; Nakano et al., 2021; Touvron et al., 2023; Gao et al., 2023; Eisenstein et al., 2023; Mudgal et al., 2024) is perhaps the most widely used inference-time time alignment heuristic; specific works that have observed the overoptimization phenomenon for Best-of-N include Gao et al. (2023, Figure 1), Chow et al. (2024, Figure 3), Frick et al. (2024, Figure 7), and Stroebl et al. (2024). There are also other algorithms based on more sophisticated variants of Best-of-N or other techniques such as rejection sampling (Liu et al., 2023; Chen et al., 2024; Chakraborty et al., 2024; Xu et al., 2024; Shi al., 2024; Qiu et al., 2024; Jinnai et al., 2024; Zhao al., 2024), though few of these works are explicitly designed to address these issue of over-optimization. For example, most algorithms based inference-time search, such Monte-Carlo Tree Search (MCTS) and relatives (Feng et al.; Yao al., 2024; Zhang et al., 2024), are designed with the complementary goal of maximizing fixed reward function of interest given exact access, and do not account for overoptimization or mismatch between the reward function and task performance. Specific algorithms that make use of rejection sampling include Liu et al. (2023); Li et al. (2024a); Xiong et al. (2024); Zhao et al. (2024); Khaki et al. (2024), though the specific distributions these works aim to sample from are quite different from that used in InferenceTimePern inssssiiiio sm. See also Welleck et al. (2024) for a survey of anference-time algorithms.
Other related but complementary line of work include (1) distilling inference-time procedures into policies, thereby giving training time procedures (Amini et al., 2024; Sessa et al., 2024; Gui et al., 2024; Pace et al., 2024), and (2) designing "inference-aware" training procedures which change the training process to optimize performance of downstream inference- time such as Best-of-N (Balashankar et al., 2024; Chow et al., 2024).
A.1. Connection to Offline (Training-Time Alignment
As discussed in Section 1.2, our problem formulation and algorithms are closed related to a growing body of research on theoretical algorithms for offline alignment (Zhu et al., 2023; Zhan et al., 2023a; Li et al., 2023b; Xiong al., 2024; Liu et al., 2024b; Cen et al., 2024; Fisch et al., 2024; Ji et al., 2024; Huang et al., 2024b; Rashidinejad & Tian, 2024), which give training-time interventions that enjoy robustness to reward model overoptimization under various notions of coverage. In particular, our InferenceTimer imi sm algorithm can be viewed as implementing an "idealized" version of the x2 regulazzie RLHF algorithms introduced by Huang et al. (2024b) at inference-
Our formulation of inference-tine time alignment can be viewed variant of the offline alignment problem that abstracts away the process of training the reward model. Rather than concerning ourselves with the details of training F from Dprer to minimize Eq. (3), we take ñ as a given (in the process, abstracting away the dataset Dpret), and ask how to achieve the best possible regret on a per-instance basis, both with respect to the reward model f itself, and with respect to the prompt a E X (which arbitrary and fixed, rather than assumed to be i.i.d. as x ~ p). Naturally, our algorithms and analyses can be combined with any reward estimation procedure that minimizes Egpup (x) complexity guarantees for offline alignment.
(x) from Dpref to derive end-to-end sample
Online alignment. A complementary line of theoretical research which is somewhat less related to our work studies alignment with online feedback (Xu et al., 2020; Novoseller et al., 2020; Pacchiano et al., 2021; Wu & Sun, 2023; Zhan et al., 2023b; Chen et al., 2022; Wang et al., 2023; Du et al., 2024; Das et al., 2024; Ye al., 2024; Xie et al., 2024; Cen
16

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
al., 2024; Xiong al., 2024; Gao et al., 2024; Chang al., 2024; Song et al., 2024), where feedback from the true reward model r* (x: y) is available.
B. Further Empirical Results
In this section, we expand on the experiments discussed in Section 5. We begin by providing a complete description of our expeirmental setup in Appendix B.I, before proceeding to expand the breadth of empirical results reported in the main body to more policies, tasks, and reward models in Appendix B.2. We continue by conducting a further investigation into the robustness of InferenceTimePesse estimated rewards f sampled from ref in Appendix B.3. Finally, present preliminary results for the AlpacaEval-2.6 task in Appendix B.4.
sm to the regularization parameter 3 as well as distributional study of the
B.1. Further Experimental Details
As we summarized in the main text, we conduct an extensive empirical suite by considering many tasks, reference policies, and estimated reward models. We now detail each of these in turn. The four tasks we consider are the following:
1. GSM8K: We consider the test split of the popular grade-school math dataset introduced in Cobbe al. (2021). This dataset consists of about 1K short math word problems. We prompt all of our policies with Chain of Thought (CoT) prompting (Wei et al., 2022) but do not include any example demonstrations, i.e., correctness in the sense that we assign r* (x, y) = if the resulting policy gets the correct mathematical answer and r* r"(2, 3) otherwise.
zero-shot. We measure
2. MMLU: We consider the college math and college chemistry splits of the MMLU dataset introduced in Hendrycks et al. (2020). This dataset consists about 100 questions each math and chemistry at the college level with multiple choice answers. Again, we use CoT with zero-shot prompting for all policies. Correctness is measured in the sense that the resulting policy gets the correct multiple-choice answer.
3. MATH: We consider the randomly sampled set of 512 questions from the test split of the MATH dataset introduced in Hendrycks et al. (2021). This dataset consists of hard mathematics problems. As above, prompting, with correctness measured in the sense that the resulting policy gets the correct mathematical answer.
CoT and zero-shot
4. AlpacaEval-2.1 2... 0: For a small subset of our policies and rewards, we consider the AlpacaEval-2.1 0 task introduced in Li et al. (2023a), with 128 randomly sampled questions. This task is challenging LM benchmark where we compare a policy's ' generation to that of a benchmark LM, and define r* according to win rate against an evaluator LM. In order to collect a denser signal, we compare win rate against generations sampled from Tef for each 7eef we evaluate. We use GPT-4o-mini (OpenAI, 2024a) as our evaluator.
For each of our tasks, we consider a subset of the following four reward models for use as the estimated reward f::
1. OASST: the OpenAssistant reward model based Pythia-1.4b (Köpf et al., 2024).
2. GEMMA-RM: reward model based on Gemma-2-2b (Dong al., 2023).
3. LLAMA-RM: reward model based on Llama-3-3b (Yang et al., 2024c).
4. ARMO-RM: reward model based on Llama-3-8b (Wang et al., 2024a).
Finally, we consider the following policies for Tref:
1. GEMMA-2-2B: the Gemma-2-2b model introduced in Team et al. (2024).
2. LLAMA-3-20 3-3B: the Llama-3-3b model introduced in Dubey et al. (2024).
3. Mistral-7B: the Mistral-7b model introduced in Jiang et al. (2023).
4. Phi-3-Mini: the Phi-3-mini model (3.8b parameters) introduced in Abdin et al. (2024).
5. Phi-3-Small: the Phi-3-small model (7b parameters) introduced in Abdin et al. (2024).
In all of our experiments, for each prompt in each task and each policy, we generate about 20K responses sampled with temperature from the chosen Te.. For a given number M of replicates (M = 50 in all tasks except for AlpacaEval-22 0, where M- due to resource constraints), we then bootstrap M subsets of N samples each from this large set and run our
17

---

Coverage, Scaling, and Optimality in Inference- Time Alignment
algorithm these subsampled responses. We define the accuracy of given algorithm on prompt as the average number of correct answers produced over the number of replicates; exception to this is AlpacaEval-2.0 0, where we measure the win rate according to the evaluator LM. The reported accuracy of policy is given by the average accuracy over all prompts in the task, and the standard error is estimated by marginalizing over the prompts in the task. As stated in the main body, in all cases for fixed N, we use the same N samples to estimate the normalization constant (Algorithm 3) as we do to run the rejection sampling.
In what follows, we first present additional plots for the experiments described in Section 5, omitted from the main body for the sake of space (Appendix B.2), then describe results of additional experiments (Appendices B.3 and B.4).
B.2. Results for Further Policies and Tasks
We complement Figures and 2 well as Table with analogous figures and tables for the remaining tasks, reward models, and policies described above. First, we investigate how the compute budget N affects performance and estimated reward of the response in GSM8K (Figure 3), MMLU (Figure 4), and MATH (Figure 5), In all cases, we see that inferenceTimele wweeeseeeiisisseeeee sm is essentially monotonic in compute budget, as predicted by our theory. In some cases, we see monotonicity the performance BoN-Alin Alignment, which consistent with the observation (c.g., Figure 9) that some (task, policy) pairs appear to be more in-distribution for some rewards (such as ARMO-RM) than others; for such cases, we expect BoN- Aligmennt perform well.
We also display the effect of the regularization parameter on performance, average compute, and estimated f for each of GSMSK (Figure 6), MMLU (Figure 7). and MATH (Figure 8); we again compare our performance BoN-Alignment with the same compute budget of N 213 To be precise, we fix N and compare the naïve BoN-Alignment approach with this large N to InferenceTimePessiin
where we use all N samples to estimate the normalization constant and then run rejection sampling until acceptance for each fixed B and prompt; in this case all prompts across all tasks, policies, reward models, and Ios terminate within the N samples. As discussed in Section 5, increasing / leads to a smaller average required responses before rejection sampling terminates as well as a smaller estimated reward f.
Finally, we display analogues of Table 1 for the remaining policies we consider: For each of Phi-3-Small (Table 2), Mistral-7B (Table 3), and LLAMA-3-38 (Table 4), we compare the performance of compute-normalize BoN-Alignment with N 213 to InferenceTiment only consider the first tasks) for our four reward models. We continue to find that the performance of BoN-Alignment with properly tuned N and Inference IetreenceTmeeeesse imeeessiiiiissssss sm is similar, which we believe is caused by the fact that C* C when r" is binary and n' is uniform over the set of correct answers; by Theorem 3.4, BoN-A MAN-AAligment will perform near-optimally in this regime.
imi
GSM8K, MMLU, and MATH (with the exception of LLAMA-3-3B, where we
1L..0 Accuracy
28-
(a) OASST
(b) GEMMA-PA RM
(c) LLAMA- RM
(d) ARMO-RM
Eettaated Roward 00
Ronudd
40
28-- Mii
780-3 Seall
10
Hatzal
(e) OASST
(1) GEMMA-RR RM
(g) LLAMA-RM
(h) ARMO-RM
Figure 3. Comparison of Inference iwwreenceeieePestteeee timeeessimi imm sm (solid lines) and BoN-Al BoN-Alignment (dashed lines) in accuracy and estimated reward P for GSM8K for four reward models and choices of nw..
18

---

Coverage, Scaling, and Optimality in Inference-Timg Alignment
To-mmtte 30.6 25 Accuscy OOU
Accurccy
(a)
(b) GEMMA-RM
(c) LLAMA-RY RM
(d) ARMO-RM
6 ih
Dismuee (amment
Testmated Sowwnd
Ma- Mexil Matri (700
(c) DASST
(f) GEMMA-RM
LLAMA-RM
(h) ARMO-RM
Figure 4, Comparison of Teeeeenceeimmeeeeeeeee sm (solid lines) and BoN-Al coN-mAlggmennt (dashed lines) in accuracy and estimated reward F for MMLU for four reward models and choices of Teef-
L10 10 wwc.nccccyy
Latt Aecuunccy
48-
Lin
DASST
(b) GEMMA-RR
(c) LLAMA-RM
(d) ARMO-RM
Eetmmted (onvert (1
Eetiated Swwarti
15o-3 Seall
-10
DASST
(f) GEMMA-RM
(g)
LLAMA-RM
(h) ARMO-RM
Figure 5. Comparison of InferenceTinee imeeessiiisiiiie sm (solid lines) and BoN-Al ignment (dashed lines) in accuracy and estimated reward for MATH for four reward models and choices of Teef-
Table Performance of -mal3- (% Lift in Accuracy Teef).
Task
OASST
GEMMA-RN
LLAMA-RM
ARMO-RM
GSM8K (Pessimism)
0.25 0.88
1.29 + 0.97
5.43 + 0.93
4.79 + 0.84
GSM8K (BoN)
-3.06 1.21
1.19 + 1.08
5.71
5.87 + 0.93
MMLU (Pessimism)
-2.18 5.37
5.31
14.47 5.60
6.74 + 5.52
MMLU (BoN)
-3.65 5.66
5.776
14.12
8.27 + 5.84 5.84
MATH (Pessimism)
-1.93
9.94
20.23
3.54
12.71 3.37
MATH (BoN)
-4.85 + 3.45
5.27 3.66
19.99 - 3.61
8.39 + 3.56
19

---

Coverage, Scaling, and Optimality in Inference-Timg Alignment
15
1un to SerE
(a) OASST
(b) GEMMA-RO RM
(c) LLAMA- RM
(d) ARMO-RM
21
27
Avergg N.
1/
1243
12
1031
10:2
(e) OASST
(f) GEMMA-RM
(g) LLAMA-RM
(h) ARMO-RM
Entiratedd Ineoant
Enttrated Remant
Esirrated
Lixza (2)
25.3 54zc.
Miar (70h 1
ii OASST
(i) GEMMA-RM
(k) LLAMA-RM
(l) ARMO-RM
Figure 6. Compute-normalized comparison for N 21 between BoN-Alignment and InfereecceTimeeessiiiee GSM8K for four
reward models and choices of Tref, function of regularization B.
Table 3. Performance of Reef Mistral-7B (% Lift Accuracy over Teet).
Task
OASST
GEMMA-RM
LLAMA-RM
ARMO-RM
GSMBK (Pessimism)
4.15 + 1.77
25.41 1.87
57.30 + 1.77
53.19 + 1.77
GSM8K (BoN)
-12.10 +: 1.96
22.46 2.08
58.31 + 1.86
63.69 + 1.76
MMLU (Pessimism)
1.28
14.56 7.66
35.01 9.16
24.63 8.21
MMLU (BoN)
8.87
12.71 + 9.92
37.43 + 9.70
22.23 + 9.89
MATH (Pessimism)
10.32 6.51
46.15
129.58 + 11.55 11.55
91.41 + 9.42
MATH (BoN)
-20.13 + 8.26
47.49 + 9.12
133.13 + 12.15
102.10 + 10.32
Table 4. Performance of mhat
LLAMA-3 3-3B (% Lift in Accuracy over ITat)).
Task
OASST
GEMMA-RM
LLAMA-RM
ARMO-RM
GSM8K (Pessimism)
5.20 +: 1.33
14.38 1.32
27.54 + 1.28
29.66 + 1.18
GSM8K (BoN)
-4.35 + 1.94
11.45 1.78
27.43 + 1.52
30.49 + 1.44
MMLU (Pessimism)
16.82 + 10.21
21.77 + 9.89
46.55 + 10.49
46.87 + 7.94
MMLU (BoN)
16.82 + 10.44
20.48 + 10.42
44.13 + 10.71
52.86 + 10.54
20

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
10
15P
100
(a) DASST
(b) GEMMA-RK RM
(c) LLAMA-RM RM
(d) ARMO-RM
311
25
21
(e) OASST
(I) GEMMA-
(g) LLAMA-RM
(h) ARMO-RM
Brinand (7)
Drcinates Poward
Lame 2300
Nttra (7S)
(i) DASST
(i) GEMMA-RM
(k) LLAMA-RM
(l) ARMO-RM
Figure 7. cemmpute-normalized comparison for 2 between BoN-Alignment and InferenceT InferenceTimePessiiin www.eessieeeiis............... MMLU for four
reward models and choices of Teet as a function of regularization B3
21

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
100
(a) DASST
(b) GEMMA-RM
(c) LLAMA-RN RM
(d) ARMO-RM
21
24
20
15
27
12
(e) OASST
(I) GEMMA-RM
(g) LLAMA-RM
(h) ARMO-RM
Enieaaed Rowazd 1
Eetimattd flewadt D9
Mittie (75)
2ai3
17
(i) OASST
(i) GEMMA-RM
(k) LLAMA-RM
(I) ARMO-RM
Figure 8. Compute-normaliin comparison for N 23 hetween BoN-Alignment and InferenceT TeceeTTieeeeee imPesssimi sm on MATH for four
reward models choices Tef, a function of regularization B.
22

---

Coverage, Scaling, and Optimality in Inference-Tims Alignment
B.3. Further Experiments
We performed several additional experiments to (i) validate the basic modeling assumptions in our inference- alignment the assumed reward model accuracy bound in Eq. (3); and (ii) probe the behavior and robustness of ieterenneeimePestieieee sissm,mmmmm sm, and. We begin by examining the distribution of the reward model scores f(z, y) under rref then explore the robustness of InferenceTimenn wwrrrenceeieeessiiie ieeesssimss to the choice of regularization parameter 3.. we also present preliminary results on the AlpacaEval-2.1 0 task in Appendix B.4.
Reward distribution under Tref- In order to get a more fine- fine-grained sense for the extent which reward overoptimization is problem, in Figure 9 we plot the distribution of the reward model value F(z, v) for single representative prompt from GSM8K for all GEMMA-2-20 SeMvA-2-B--geerateee responses, according to each of our four reward models, and conditioned on whether or not the response is correct. The more separated the distributions are, and the further to the right the correct (blue) distribution is, the better the reward model is at estimating the true reward. As we see, ARMO-RM is by far the best reward model in this respect. In particular, one reason to expect that would not observe reward overoptimization in BoN-Alignment for ARMO-RM with this task is the fact that the maximal value in the support of the incorrect distribution is, empirically, strictly smaller than that of the correct distribution; thus for sufficiently large N, BoN-Al BoN-Alignment will always choose the correct answer, at least for the prompt we visualize. This observation is consistent with our theoretical results, but suggests that in some cases our assumptions may be too pessimistic; indeed, Inference imePessimiiiii sm may be overly conservative in situations where already underestimates r* by a large margin (since pessimism, or under-estimating the true reward value, precisely what the regularization
ieterenceeimePesse insssmmisii sm is designed to enforce).
6:50
6.5
1.14
6.5-
Cornett Iscumedt
0.5
20
0.15
15
030
0.0
6.0
0.30
GASST (1433)
Gemmmn RX (23)
Liana RM (3B)
ARMD RM (7B)
(a)
(b)
(c)
(d)
Figure 9. Distribution of estimated rewards of responses generated by GEMMA-2-22 on GSM8K prompt number 100 conditioned on whether the response correct for (a) OASST, (b) GEMMA-RM, (c) LLAMA-RM, and (d) ARMO-RM. Greater separation of the distributions with the correct (blue) further to the right than incorrect (orange) indicates the reward model is more informative.
to B. In addition to the theoretical suboptimality under general notions of coverage, the central drawback to BoN-Al BoN-Alignment iggment is the lack of monotonicity, requiring careful tuning the computa- tional budget N in order avoid over-optimization. In Figure 10, we plot the accuracy of InferenceTimePPsso on Mistral- generations for representative subset of the tasks and reward models f consider, evaluating the ef- fect of the regularization parameter 3 performance. We find (Figures 10(a) and 10(c)) that InferenceTimePee experiences less over-optimization than CoN-Alignmen fairly robustly across range of 3 values, though tuning |3 is typ- ically required to avoid over-optimization entirely. We also observe that in some cases, where the reward model remains in-distribution for all task responses, BoN-Al in is monotonic without further interventions (Figures 10(b) and 10(d)).
Robustness of inferenccTTimeeesiiine
sm
Note that for small values of the regularization 8, we do observe small dip in performance for infferenceTiePessiiii (cf. Figures 10(a) and 10(c)). This is caused by our heuristic of defaulting to BoN-Alignment when no responses are accepted by rejection sampling in InferenceTiment wweeeessieiiiiisieeeeeeeeeesss which more likely to occur when the computational budget N is small relative to the inverse of regularization 1/3 according to our theory (Lemma D.4). We should like to remark that this is reasonable heuristic, as it is precisely in the small N regime that Aol-meign is expected still perform well according our theoretical results.
B.4. Results for AlpacaEval-2.0
In addition to the experiments with GSM8K, MATH, and MMLU, we conduct a preliminary investigation on the performance of InferenceT CoeneeTimePeseee immeesssmmsn on AlpacaEval-2.0 (cf. Appendix B.1 for an explanation of this task). Because evaluation requires many queries to the proprictary OpenAl models, we consider a significantly smaller scale experiments for this task, and use only replicates for each prompt as opposed to 50. The results are displayed in Figure 11. Due to the
23

---

Coverage, Scaling, and Optimality in Inference-Timg Alignment
C.001C
000:
10
3.000000
ELOGS2
0.002
% Lift in Accunner onee
0.0013
0.002
Lin la AccusDcy
1-0.0
5.000055
J 0,3002
5.5000
E.Eca0
N in Accumery
0.0012
2002
0LE02
OLOG2
5 (24b)
0.3002
10
0.10002
10
2T
(a) (GSMBK, OASST)
(b) (GSM8K, ARMO-RM)
(c) (MATH, OASST)
(d) (MMLU, LLAMA-RM)
Figure 10. Demonstration that monotonicity is robust to the choice regularization parameter / for Mistral-7B generations with a representative sample of tasks and estimated rewards f.
noise the evaluation, coupled with the significantly smaller number replicates and prompts, difficult to separate the performance of BoN-Al iinmmnt and InferenceTimmeessiii in a statistically significant way, although the broader trends agree with those found in our other tasks.
100
120
% Lift in Accuracy over Thet
Estimated Reward (
60
40
20
-50
Gemma-Rke RM (2B)
Llama-RM (3B)
-75
ARMO-RO RM (7B)
-100
24
26
23
210
2
-20
2
24
2
2
(a)
(b)
Figure 11. Performance of BoN-Alignment and ittpereenceTieeesssiiiiii AlpacaEval-22. with GEMMA-2-22 Reef for several
reward models.
24

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Algorithm 3 ComputeNNrmmCCnstant
input: Prompt 2, reward model regularization coefficient O, set of responses YN- (3)1 ........ yN).
1: Sort and bucket Dy into bins , V/s according to the value of F(x, y). in ascending order, such that
F(z, v) = Fi:
Vy E J4, Vi [M], and R < f4t
Vi [M]
2: Initialize Po = 000 J E im P
DE N
and + 1.
3: for = 1........ M
4: Set - J-B
3.
5: iffi-1 & X < P; or = M then
6: return
7: else
8:
Update J + J p.
and Z +- Z D4
Algorithm ComputeNNrmmConstann for general base measures
input: Prompt x, reward model F, reference policy Tref, regularization coefficient | > 0, set of responses 5N
(yi....,, .N)).
1: Sort and bucket Di into bins V4..... .i....../y V's according to the value of f(x:, y) in ascending order, such that
f(z,0) = Pi,
Vy E 34, Vi E [M]
F < Fitl,
E [M].
and denote (re x)) = E Eey, (yef (y xx)
2: Initialize Po = -00, J + Σ i= Feet (Y/ x) F3 and + E Tref (V/s x).
3: for = M...M... do
4: A +- 7
5: if if S < P3 o M then
6: return
7: else
8:
Update J + J - F. Tee (1/ 2) and Z +- Z -Te lx).
Part II
Proofs
C. Normalization Constant Computation
C.1. Background
This section gives guarantees for the ComputeNormmConstant subroutine (Algorithm 3) used within Inference CnnerenceTimmPesee imeeessiimss sm. Given set of response 2N and æ X. the algorithm computes normalization constant À such that
(A)) = Σ relu ( ( A)) BESIN
in time O(N log N) using dynamic programming-like procedure. Note that such a À always exists because क(A) is continuous, piecewise linear function that is decreasing in X, with $(-x)) and @(20) 0. In what follows, state and prove the main guarantee for the algorithm. En route, will also prove guarantee for more general version of ComputeNormConstaan (Algorithm 4), which computes normalization constant such that o(A) = Eyey Teat (y (r)r (B- (F(x,, y) 2)) in time O(N log N).
25

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
C.2. Guarantee for ComputelNormConstaan
Lemma C.1 (Main guarantee for ComputenNormConstantt) For any f, B, SN. and E &, Algorithm 3 finds X such that ((A) = t EyeDy relu(8- (f(z, v) X)) = in ON log N) time.
Proof of Lemma C.1.
Algorithm 3 is equivalent to running Algorithm 4 with F, B, y = 5N and and so we can directly apply Lemma C.2.
(y 2) = N I E |N]
Lemma C.2 (Guarantee for generalized ComputeNoormConstaan))) For any 9, B. DN, and X, Algorithm finds X such that (A) Σyeei (y (e) (F(x, y) ))) in ON log N) time.
Proof of Lemma C.2. Let x: E X be fixed; we omit dependence on x going forward to keep notation compact. We begin by defining a surrogate problem with response space Vas := { JM where yi is any response from 3% surrogate reward function fr with (1)) =: P. = P.. and surrogate reference policy Teer where for i E [M] we set
(B:)
Σ (y)r
VE
Note that all responses in this collection have unique values under a surrogate reward function F. Since Algorithm 4 sorts rewards in ascending order, we also have that the surrogate rewards are indexed in ascending order, i.., Fj < P(tt for all i. We also define the following function, which is the analog of (A) defined over the M surrogate responses,
M
2((A)
Σ
क The (1)reel(B -)))
For any A, can be seen that (A()) (A) since
3'(A)
(v)) relu(3 -Fi-
Σ Fiat (v)el())e 1)) a()),
MENx
M because each y E NN is binned into one of (21) i- and within each V& all responses share the reward label F.
Next, define x to be such that ('(x²) = 1, that is, the true constant that normalizes the distribution over the M surrogate responses. Our goal is to show that Algorithm 4 computes 'r, which, given the previously shown equivalence, then proves the lemma statement since
= +'(2*) (>*).
Note that such A is guaranteed to exist because (A) is continuous and decreasing in X. Moreover, from the form of V' can be seen that there exists some index j such that X 2 P3 and
1 1 80 (A*) = 3 Σ T (F) X²).
In other words, there exists index j E [M] such that A Pjal which also shows that X E [J(reet) -, 3,FM)
Then to find X*, that is, a such that (A()) 1, it is sufficient to find an index such that for
Ei>s T'er (1.) -B Eisy ((er(1))
P", B, which breaks at an index that we have P7, S X P. This is exactly the output of Algorithm run on Dm P' satisfies the above conditions, and outputs the corresponding A. By inspection, such a satisfies (((A) and therefore also satisfies ((A)= = 1.
Lastly, we discuss the computational complexity of Algorithm 4. Sorting DN and f require O(N log N) time, while binning is O(N). Finally, we make one forward pass through the responses, which requires at most N iterations, each with (1)) computations, before termination.
26

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
D. Rejection Sampling
This section includes background on and guarantees for approximate rejection sampling, which forms the basis for our analysis for BoN and inferreneTimePessee
The organization is as follows. First, in Appendix D.I, we describe the approximate rejection sampling algorithm (AI- gorithm 5)-which is used within InferenceT SeeencTiimeeen imePessimi sm, as well as within the analysis of BoN-Alignment-arr introduce the fundamental concepts that we will use to analyze the sample complexity of RejectionSampling Then, in Appendix D.2 we provide upper bounds on the sample complexity of RejectionSampling with matching lower bounds in Appendix D.3, in terms of the aforementioned measure, demonstrating its fundamental nature and the tightness of our results.
Algorithm 5 Rejection Sampling (RejectiionSamllingy. (w: TT)r
input: Prompt z, base policy Tief, importance weight wo truncation level M.
1: Draw VN = (Ui,...,UN UN+1) ~ T.ee(: x)) i.i.d.
2: for = 1.....NN N do
3: Sample Bernoulli random variable & such that P(ç: 1 y1) min w((x M
1
4: if & 1 then
5: return response y y/
6: return response = +1
D.1. Background
The rejection sampling algorithm RejectionSampling is shown in Algorithm 5. The input parameters are the sample size N and the rejection threshold M, a prompt æ, and an importance sampling weight w.
The algorithm first draws N samples from the conditional distribution of Teo for the fixed prompt x, i.e., it draws IN (uI...., .,v where y T-e | x) for each i E [N.. Then, for each E YN, it samples Bernoulli random variable & where the probability of observing & = 1 is given by the importance weight w(y, x)) divided by the rejection threshold M. truncated to be at most 1. The algorithm returns any ys for which & = 1, and if no such event is observed, returns the first response (which is equivalent to randomly sampling from the base policy).
If ([| | (z) w((1 1T) (- x)) is a valid distribution, and the rejection threshold M upper bounds the importance weight (or now, likelihood ratio) uniformly, that is, . 2 =<yl=)
[)]())=)) for all æ and y, then Algorithm 5 is identical to classical rejection
sampling, where is known that the law of accepted samples matches the target distribution æ, i.e. P(y) | = 1, x) = x rr). If M is not a uniform upper bound on the likelihood, the law of the accepted samples is not identical to m. This because Algorithm 5 effectively truncates the distribution of π to be at most M Teef and any mass above this threshold effectively lost. Nonetheless, the law of accepted responses is close approximation Approximate rejection sampling under this regime was first analyzed in Block & Polyanskiy (2023), and our results in this section below borrow from their analysis.
when M is sufficiently large.
For the remainder of this section, we will consider the problem of sampling from a target distribution or policy X A()), by calling RejectionSampling:: ( Teef ; 2)), where - is its importance weight (or here, likelihood Tuy
concerned with analyzing how close the RejectionSamplin function of the truncation level M. For example, if there exists such that w(y x)) > 0 but (yr x) = 0 then it is not possible information-tie -heoreicilt to sample from this portion of the target distribution, and similar reasoning applies to with poor coverage under Tref-
ratio) over the base policy. Concretely, distribution is to π
response
Preliminaries: Exr divergenee Based on the intuition above, central object in our analysis will be the ENs -i--divegeence in Definition D.1 (Polyanskiy, 2010; Block & Polyanskiy, 2023), which, for an input rejection threshold M, quantifies the mass of the target distribution that is lost by truncating the importance weight Reet to M.
Definition D.1 dEveeeiveg,, For a prompt x, base policy Tref : X A(V), and target policy π : X + A(Y), let (σ) := x( | x) refer to the distribution conditioned on x, and define Te (I)) similarly. Then for any rejection threshold
27

---

Coverage, Scaling, and Optimality in Inference-Tims Alignment
M 2 1, the Ex-diieeeencc is defined as
(
T x)) (eel(
)
(xr(T(x), (x) = E By (x))
M)
Σ
M x) M
(Teer x),
x
vEVM(()
where (M(x)= - (y EV: E x x)) > M. Tee x.). In addition, the expected Eas-divergence over the prompt distribu- tion p is defined as
(T, Tref) == PxxplEar((T(e (Ter (x)]]
Note that (x)) (x)) and Em (IT, Fref) are non-increasing in M in the sense that they do not increase as M gets larger, and we will show in the sequel that they control the approximation error for RejectionSampling the parameter M strikes a bias- haasvvarancce tradeoff the RejectionSampl ing procedure. When M is large, the algorithm requires large number samples in order to terminate; but for M small, incurs larger bias from failing to sample from regions of the target density.
In particular,
For the results that follow, it will be useful to define the smallest parameter M that guarantees E (T(x)) Teed (2)) S for some error tolerance of interest E [0, l].
Definition D.2. Given the base policy Teef. for a target policy prompt x, and any e E [0, 11, define the smallest rejection threshold M that ensures E (x)) I E to be
M = min{M (M((TT)) Tret (ee((()) S {E}.
Similarly, define the smallest rejection threshold M that ensures Ess (T,, Tref) S E to be
M == min M (T, Ee).
Though the Ex-divergence is perhaps the most natural object by which to quantiy the error of aproximate rejection sam- pling, it can also be upper bounded by other information-theorett divergences, such as C and C", which will be useful in the later analysis for BoN-Al non-mlignment and imferenceeimeeesssiinn immiessssmssmmmmmmmm sm. We state the result below for M 2, for fixed x, which can be stated for M in similar manner.
mvvl=) Proposition D.3. Given the base policy Tref for any target policy x and prompt x, recall that C (I) = supyey Rar
and define C. (x) == 1 a
Eysx
x(ylz)
a-11
for any a > 1, so that C3 (z) = C (z). Then for any e E [0, 1] and
(0), we have
C
(T())
M S min Cτ,(x)
In particular, for the coverage coefficient (x) CJ (x), the above result shows that MM < CD)x) The proof below utilizes Block & Polyanskiy (2023, Example 7) and the fact that C controls the Renyi divergence of order a between and Tref-
Proof of Proposition D.3. As the prompt is fixed, we omit x dependencies for notational compactness. Recall that for any M. EM (x, Trat) = x ()²m) M (.)) The statement for M C% follows directly from the definition of Exr (TT, Rref) C%
since Egy, (TT, Tref) = 0. For Cg it can be seen that π ()'m)) - M since
Tly)a
C Σ
Traf (y) Tly E Vas) Ma-1 Σ (v) Tly VMl Ma-1. x()as)
Then for M to satisfy
CT
C
8 < Ens( Feef) < Ma-1
M ned (1ar) S
M
CT --1
suffices to have M
28

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
D.2. Guarantee for RejectionSampling
This section contains sample complexity upper bounds for Algorithm 5, which express the size of N required to ensure that the total variation distance between the law of responses drawn from Algorithm and the target distribution small. The main result, Lemma D.4, that expresses sample complexity in terms of M and E (TTx), (z)(
For fixed N, Lemma D.4 shows that the total variation distance is bounded by the Eas- divergeeeee corresponding to the input rejection threshold M, as well as an exponential in N term that bounds the error when the algorithm fails to terminate. As expected, the former term decreases as M increases, while the lattter increases. In addition, while increasing N can reduce error from the latter term, the former term is irreducible even as N tends too infinity, and this too we expect given that a (T, ref) is an cetemaatiootthhoreee measure of error that is property of the distributions and the choice of M.
Lemma D.4 (Per-prompt rejection sampling upper bound; adapted from Theorem in Block & Polyanskiy (2023)). For any valid policy X A()), N E, and M E R+, for given prompt E X, let πR( A()) be the law of responses induced by running RejectionSamplinge .M( Rie TTe, 2) (Algorithm 5). We have
Ted (x)) + exp ( N (1 Els (TT(T))) Tret (Te())))) M
Div(T(2), ((()) S
In particular, if M = MG and 2 M lt) for some E E (0, 2 we have that Drv (T)()()), (x) Se.
Proof of Lemma D.4. As the prompt is fixed, we omit dependencies for notational compactness. Define the truncated pseudo-distribution मं min( [T, M -. Define Am Ey (v) be the total mass of the truncated policy. Recalling that VM (z) {y E y ( 2) > M Tree (y r)). AM can be equivalent expressed
Am Σ min( M mtd(()}}
y
Σ M (v) +
Σ ((y
BEVN
(MT rret).
Recall that, for a single sample ~ Tref, Algorithm 5 samples & ~ Ber(py), where Py == min random variable such that (e (5 y) = Py. Then the expected probability of acceptance for a single sample is
m(v)
is a Bernoulli
P Py (- = 1) = Ey [P(5- = 1 y)]
TTV) M Tree (y)
1
(v) -iinn
Σ min(
M (1)
M
Am
M
and it can be seen that the law of the response conditioned on acceptance, Eyevs M. (T) Eyerr, T(y), equivalent to the normalized version of से since
Py Py (1 = = = =)= Symomee-BBrrppp = =1 Pyrnawe Berrp,) =1)
Trer(y) min
Mi (9))
T(y)
Am/
AM
Next, given DN = ......., u. let En = EN be the random draw of Bernoulli random variables, where & ~ (er(py.) for all [N]. For short, we write P5x. Ex (-) = Py Bi (er((gg (-). Define also the
following event, which is a random variable over the draw of DiN and ÊNv, under which rejection sampling accepts one of the N responses and Algorithm outputs the i*th response Line 5.
stop = Eir E [N] s.t. & = =1)
(14)
29

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Let SnjjectionSSmllnngy.... M pee ()) be the response output by Algorithm 5, which is random variable over draws of DN and εv. Due independence, have that the law of responses is given by
T(V)
Sv. En (ū - y stop) = PS..& EN (vi- y 3i E [N] s.t. Ei- = =1 = Aas
(15)
It can be observed that via union bound,
P Ps..Er (-stop) = -P
NNNtE EN (Ei = 0, Vi E [N])
= (1 P Pywraark-Berro)) (5 = 1))
Am
M
N.AM
S e
(16)
Recall that TR(U) = PS.. Ex (1). Now for the upper bound, we first decompose the total variation distance using म.
1 Σ (v) - π TR( DTv(W, = -
- 2
Σ
(v)
#(v)
+ + Σ TR()) - #()))
2
21
(T1)
(T2)
where, via Definition D.I, the first term is equivalent to
(TI) = Σ π(y) min(f(y), M (v)) = Σ T(V) I[T(v) > M - (e)l ESS( Tret).
and we further bound the second term as
(T2) Σ
P Pon En (U = y ssto)) + Py.. Ev (0 y -stop) 7(0)
- Σ PSW.EN (i = stop) - -i() +Ip +Ip Bw. En (
(T3)
From Eq. (16), have P P (-stop) se
In addition, using Eq. (15) and the fact that AM 1, have that
(33) =
PStw Ex (T = stop)) F(v)
7(V) 7(0) = Σ F(v)
7(v)
Am
Am = (T, Trat),
so that
NAN
(T2) < (M, Teat) + exp
Combining (T1) and (T2),
1 DTv( Tret) 7 ((T1) + (T2))
1 N.AM
$ EM Tref) +
2 exp
and substituting the expression for AM = 1 - (M,(T, Teet) gives the result.
30

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
D.3. Lower Bounds
For a fixed prompt x, Lemma D.6 shows N 2 M log(e-*) samples are sufficient guarantee that (rv(=(x), (x)) I e. The information-theoretii lower bound in Lemma D.6 shows that this dependence is tight for any selection strategy that selects a response from NN. defined more formally below.
Definition D.5 (Selection strategy A). A selection strategy A is any method that, given prompt and N responses DN (y), (y).-.... -000: yN) sampled i.i... from Tef relurns some (possibly random) y YN-
Lemma D.6 states that selection strategy (Definition D.5) must obtain at least M M,s samples in order to induce response distribution that is e-close to π. We will later use this result as component within our main regret lower bounds (Theo- rems 3.2 and 4.2).
Lemma D.6 (TV lower bound, adapted from the proof Theorem 5 in Block Polyanskiy (2023)), Fix the base policy Tref target policy n, prompt z, and sample size N. Let be any selection algorithm (Definition F.2) that, given VN Tees(- x)) in the sample-and-evaluatt framework (Definition 2.2), outputs response YN. Let aA X A())
denote the distribution of responses induced by A. Then if N < MM we have
DIv(Ta(E), >E
Proof of Lemma D.6. In the proof below we omit dependencies, including in M MM. and Ens (T())) Teet mee((a)) EM(T, Trer). First fix M. Suppose N < M. Then
2. DTV(TA,
N
Σ (T( A
NEV
Σ T(y)
P(y E Si))
VE
Σ T(y) m(y)
M
Σ
T(y) M 1())
VEVM
(T,
follows that N < M S ME we have
DTV(TA, >
from the definition of M since Em (T,, Teat) is non-decreasing as M decreases.
31

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
E. Proofs from Section 2
Proof Proposition 2.3. Let us write (, 2) == By-r( (x) y) to denote the expected reward under a function r(z,3) .). We first state an elementary technical lemma.
Lemma E.1. For any prompt x E X, reward model F X y I. and policies गt, क X ( and 0, there exists r* X x + R such that
( y 2)
Fyy x))²
Jr [T) J,- (T;z) ==(==;²) - Jx(+;() +s-
Σ DEY
Wrof (y) x)
and (1))m (f(2, v) - (x, v)) =?
Proof of Lemma E.1. We use the choice
-1/2
r"(,,) y) = F(z, te- T xz) 7ly x)
(T (y x))
7 x²))
Tref(1 x)
Teeff (3
x)
DEY
from which the result is immediate.
Going forward, we omit dependence on x X' to keep notation compact. Define Cuax max max C and Tnax arg max C=, and let C 2 C be given. Throughout the proof, we will use the fact that C 1 for all We set F(x, y) = 0 and consider two for the analysis.
Case 1: C
1 C** In this case, we invoke Lemma E.1 with x² Tref and & = SaM, which shows that there exists some 8
r* for which
(Tet (1) 7(y))²
Jx-((T) Jr- (T) 2 ERM
(Tee(()
DEy
The result now follows by noting that
Σ VEY
(Trel( (y) - [1)))²
C² -12
1 0 1 12 C*.
Tref (v)
8
16
Case 2: C C In this case, set
n Amaax + (1 A)Ttef
for X2 = 20 E (0, 1). We compute directly that
Cx* cax + (1 - X²),
so that CT' E C* We invoke Lemma E.I with n' and s = EaH, which gives that there exists some r" for which
n (v) - #(y))²
JT-(T") J, (T) 2 Ean
Σ ycy
Tref
We further compute that
(T) #()))²
x (g)
1 cx -ca
Ca" +C² 22
(y)
Traf Tra (1)
VEV
DEy
where the last step follows by the AM-GM inequality, i.e.
(v)
(x))
(7)))
Noae (1)
4
(1)
Traf (v)
VEY
vEy
DEY
32

---

Coverage, Scaling, and Optimality in Inference-Ting Time Alignment
By the assumption for this case, have Ca c that
c C² 1 c+
1 0
1 0"
c
completing the result.
33

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
F. Proofs from Section 3
This section gives proofs for the guarantees for CoN-Alignment in Section 3. These results in this section build on the guarantees for rejection sampling in Appendix D, and are organized as follows:
Appendices F.1 and F.2 provide general tools to analyze BoN-Alignment. In Appendix F.I, we provide general upper bound on the regret of BoN-Al Annmett in terms of the EMs -ivergeene introduced in Appendix D, and in Appendix F.2 we give general lower bounds the regret.
In Appendices F.3 to F.5, we instantiate these results to prove the main theorems in Section 3. Namely, these results leverage Proposition D.3 to translate the Ex -iveeeeeee to the C" and Co coverage coefficients, which are standard measures of distribution shift offline alignment (cf. Proposition 2.3).
F.1 General Regret Decomposition for BoN-Al CoN-Alignn Alinnentt
Recall that the diveerereee (Definition D.1) is defined for a parameter M > O via
( T (())x)) x)) Tree(y x))
)
Σ
x x) M MTee | x)) E By-
M)
(x)'
Our central technical result for the analysis of BoN-Alignment is Lemma F.1 below, which quantifies the regret of the BoN policy given N samples. This result will later be instantiated to prove Theorem 3.1 and Theorem 3.4. Even though Lemma F.1 concerns BoN-Alignment, its analysis makes use of the rejection sampling algorithm (Algorithm 5) as tool to analyze certain intermediate quantities. As a result, the lemma statement contains an extra parameter M. which corresponds to a rejection sampling threshold (ef. Algorithm 5), and the regret upper bound is expressed in terms of the information- Ei--eeeeeeence (Definition D.I) which appears in the analysis of rejection sampling in Appendix D.
Lemma F.1 (dv-eiieeeeence regret bound for BoN-Alignment). Fix a prompt x. For any comparator policy and N Z and M RR, such that Em (xtxx* (1:), (x)) I 2. the BoN policy TeaN satisfies
(- N
J(x;zz)= J ( x) Rmax
(TM(TT(x) (re))))( exp
(TM M
(1-Ex Terr) (e)
+ + y (T) (1)) (22 + ERM(x)
+ v N (x)
2
Because Lemma F.1 holds for any choice of M R4, M can be viewed as a parameter (within the analysis) that trades off between the best regret achievable -which is upper bounded by Ens (TT (x), Teer())) which decreases with M- and the sample complexity required to achieve it, which increases with M. Indeed, when we later prove Theorem 3.1 and Theorem 3.4 later, will choose M to make the RHS of Lemma F.I tight when EM (T(x), (z)r is translated to our coverage coefficients of interest.
sketch, sketch. The high-level idea of the proof is to use as an intermediate comparator the response distribution कर induced simulating sampling from x* via Rejectionn tiooSamllnnggy. m ( "n
Aean Tref, z). with the parameter M from the lemma statement. The utility of using such comparator that, because the BoN procedure always chooses the response with largest reward label, Ae is always able compete with mR under F (in the sense of having larger expected estimated reward).
We can then translate this observation to the desired bound by recalling that 전r approximates x* in total variation distance (from Lemma D.4), which means that BON is also approximately as good as π" under F. Lastly, we translate the performance under to the performance under the true reward r*, which is penalized by the reward estimation error (nv()) on the BoN response distribution, and the gap between the two is quantified by the reward estimation error under the distribution of responses drawn from Taon which is the source of the VN term.
Proof of Lemma F.1. For simplicity in this proof, we will assume WLOG that f(y) is unique for all y V, otherwise we can perturb Fly) with miniscule E(y) < ERu, as long as it is within floating-poii precision to break ties.
Let (1) be the distribution of responses induced by running RejectionSamplinge inttsammpligg,... (- ar) which we use to decompose the regret as follows:
[iT x)) [T x) -[m===)))))))) [m x) + J(TT:2) 2) -J -[ 2))
< Rmax DTV(T (x), mx())) + J ( x)) (TTBON5 2)..
34

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
We next bound the last pair of terms function of the reward estimation error. Below, we use Es ( (x)) to refer expectations over N samples PN :......:: MN) drawn i.idd from (x), and, given NN. we use E yyan (x) [=] refer to the expectation over responses induced by running
RejectionSamlling
(" / 2)) conditioned on the realization of the set DN = (Vi...., yN) drawn by the algorithm. We define F. (x))) analogously.
We begin by decomposing the second term above as follows:
J x) - [[TToN x)- = Bynaa (w)) [r* y) - [1) + B Bur P B (Fx.)) v)I - E m)))m( [F m)]
+ By Ram (n) ((x, y) - r" (2(2,))) y)]
I B (1)) (r* () - f(z,8)] + Byrnao (x) [[2 y) - (x,
B (o (x. - ((x,,))] + B (x) [F r" (",,, vill
(TT)
(T2)
Note that above we use the linearity of expectation in the first inequality, so that
Eg [ P [(x,, v)] 5x
Da ((x,
couples the set DN drawn by the two algorithms, and compares the performance of MSON and करे for a fixed set of N responses. Then, because the BoN policy always chooses the response with the largest value under F for any fixed 5x, i.e., Ily E supp("fen(-) x))] = F(z, v) 2 F(x,8'), Vy E 5ix]. it can be seen that
E y 1i [[x,,)) - E yyuitm (c) (y (f) [))
For (T2), we first show that CRa (x: < Caan (x) & N. Letting Esw refer to the sum over all possible sequences of N responses VN (y1..... yN) E yN, and Trei (y1 ........ UN x) II li=1 (rer | x)) to be its probability, we can express the BoN policy in closed form as
Taon(y (y (x) =
Σ D (x)
(yn... UN x) I I E Di] n(F(a,)) 2 F(,,,'), Vy E {Nw
since, conditioned on set of samples Dr. the BoN algorithm deterministically outputs the one with the largest F value. The base policy Tet can be written in similar form, by marginalizing over the process through which we sample YN, then sample y uniformly from this set:
Tl -w==)/ v)
Tref (y)
x+)=
Tref Teef (VI........
..... UN x))
Σ
N
VEE
Then for any y. we can upper bound the likelihood ratio between the BoN policy and कiत by N,
ESewmn Teee (11, ................................ UN x)) I y 5ix] I[F(a,)) 2 f(z, Vy E sN)
TOoN y x))
Traf (y) x)
E Eseoma Teee (y.,..., UN xt) Eves. 111 = vl
< N Esanmie(t)) (y UN x) I y DN] I I[ v) 2 f(x,,/), Vy E 5N
Esxoma(e) Tee (ya.... UN
x)) I E NN
N.
Now, to bound the reward estimation error in (T2), we combine this result with the Cauchy-Schward incquality, giving
(22)= S (Fee(x)) En (F(z, v) r (x. (2.)))² S V/N. N. (x).
35

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
For (TI), leverage results from Appendix D. Recall the random event from Eq. (14) random draws of IN and EN (GI,---,EN)) under which Algorithm 5 returns response in Line 5,
stop E3i
[N] S.L. E.- = =}.
From the proof of Lemma D.4 (Appendix D.2), recall that write the induced policy as
( σ) Ex (y 2, stop)
Pyx, Ex (stop æ)) Sx. (v -stop) PDN. EN stop x))
On the event of -soop, Algorithm returns a randomly drawn response uN+1 ~ Trer( x)) Line thus
P W. (y x ssopp) Tea z)
As result,
(R 1) PyN. Ex (stopl x)) .Py EN (w xtstop) Pyx. (-stop x)) Teat (y x)
S PPrm Pp Ex (y) æ stop) + 2 Trer(y) x)
min ( (y) x)), M Tvr x)}
1
+ 2
Trer(y) x)
1 1 EM (I)), Teer (z))
1
2 min( w)) M Terr( x)} +
Teerl x)
where the last inequality we have used the assumption that Eas (x), (x)( S 1. and in the first we use the ob-
2.
servation that P jyy Ev (-stop | x)) s since e (stop w) 1-Ear( (a) and M We can then M
Cauchy-Schwer bound
(T1) E Fy [1,""( (I, F(x, v)ll
1 < 2 E (x) (x, -(z wlll
2 (1)r"") f(zz v)ll
< v C (x)
(z) =x (x))
2
Combining all the preceding bounds, we obtain
x( - [ (TDONN x) 22 / ((((x))ee)())) + Epm(2)
2 + v N ex)(2))
thus the regret is bounded as
(<=";a) J(FBBNN x) S Rmax (x)( + 2. Ve ( + Sen(x)
N (x)
Finally, we apply Lemma D.4, which bounds
Drv(=*(z), (x)) (z), + exp (
2M (1 11-EEMTTT (x)) Tee (x))
to give the lemma statement.
F.2. General Lower Bounds on Regret
This section contains two regret lower bounds that apply to both BoN and Inference sm across a range of parameter values, for single prompt æ. Each bound contains an information-theereiiic component that applies to any selection algorithm, which is defined formally in Definition F.2, and takes the general form that if N < (threshold), the regret of any selection algorithm will be least poly(C** (x), (m)))) The results also have a component that specific BoN, that when N 2 (threshold), BoN has at least /N N (x) regret.
36

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Theorem F.3 in Appendix F.2.1 shows that (threshold) & Co (2r), and for smaller N any algorithm pays VC (z) ( regret, and for larger BoN incurs /N - (x)(() 2 v Cz (a) (x) regret.
Theorem R44 in Appendix F.2.2 utilizes a construction where Che (x:) is exponentially larger than C* (x)( and any algorithm has regret at least (cr (x) for range of 2 (x)()), unless N 2 (threshold) or (=)) -P. BoN
again pays / N ( (x) in this regime.
The latter result is later used to prove Theorem 3.2, where 1 to balance the terms, and Theorem 4.2, where p 2'
3
Proof techniques. The information theoretic component of the results reflects the difficulty of simulating sample from the target policy's ' distribution, which is required for any selection algorithm A to be able compete with the target policy, Recall that the lower bound for rejection sampling (Lemma D.6) states that any selection algorithm requires at least M samples to be g-close to the target distribution in TVV distance. To convert this result to regret lower bounds, we a) construct a pair of distributions for which the conversion from M to coverage coefficient C* (z) in Proposition D.3 is tight, and b) specify reward functions r* and that the regret maximally witnesses the reward estimation error (x)(2) where rejection sampling fails approximate n², and where NooN overfits
While the construction used for the 5 (x) result is relatively simple and has |>| = O(1), the construction for the C* (x) utilizes countable infinite response space V/ which is necessary to create the exponential separation between C" (x) and ..... the ratio x² increases exponentially in i, and r* increases in while
CT. (a)). If we label the responses the reward model F decreasess. Because n² here is exponential tilting of ree with respect to the true reward, the lower bound construction reflects the structure of language modeling, where policies are parameterized as softmax functions and the response space is exponentially large, which we believe may be of independent interest.
Teal
The lower bound constructions below utilize only single prompt x, and in the proofs (not the theorem statements), we drop the a dependence for notational compactness. For example, т(v) < x) since X = {²), C" = C² etc. Lastly, we formally define what we mean by "any selection algorithm" in the samplc-and-evaluate framework.
Preliminaries.
Definition F.2 (Inference-time time selection algorithm A). Under the sample-and-evaluad framework (Definition 2.2), an inference-time selection algorithm A is any mapping from DN = (y,,,..,, WN) ~ Teee(- x) and (f(z,))) to response E DN; we define X + A(V) to be the law over responses that the algorithm induces.
F.2.1. LOWER BOUNDS UNDER Loe COVERAGE
Theorem F.3 (Regret lower bound for C% ). For any can E [0.1] and C 2 1, there exists comparator policy nt" over contexts X' = } and responses y for which the following statements hold.
1. There exists problem instance (Tref: ()) with (x) EAn and
C (x) = C (x) C
such that, for any N < C, any inference-time selection algorithm A (Definition F:2) has regret
J(x";z)= - ((TAAx)) > min 2/ C (z) (z) =x) 1
2. For any N 2 1, there exists a problem instance (Tref, r" r",F) with =2)(2) < SaM and
C (x) = C* (x) C
such that BoN-Alignment suffers regret
(x) 1 J(m);z) J(Hooni x) 2 e-mnng V
where e is universal constant.
37

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Proof of Theorem F.3. Because we condition single prompt x, omit x dependencies for ease of presentation; in particular, abbreviate M = z,et and &M (x**, Teee) &M (1r (x), (x)).
Fix N and EaR and C. The response space is ) {yo. y" Ubad I. the comparator policy x T²()) = Iy = yy] plays y* deterministically, and the reference policy is
(30)
2N c. (yt C. Tref (ybad) 2N
for which we have Co C"' C. Next, for some 2 recall Definition D.2,
M min Eas(",, Aret) S $}.
For our choice of policies we can compute M in closed form, since for any M,
M
(T :reft) = 1 - M (Te = C
Then any M 2 C (1 - E) is sufficient to have E (TT Tret) S E, therefore
M. C. (1 (1- s).
(17)
Part 1 (Small N). Define the reward functions
r" (20) = 0 r*(²*) =1
r (ybad) = 0 F(Ubad) 0
F(yo) 0 = - min C cmm 1}
=
is easy to see that
Ex. (Fly) - (2))²
<
C
2
ERM
For some e that we will set shortly, when N < MM the regret is lower bounded as
J(T") (TTBN) = x (v²) FBOON (y²)
2 1 P(y* DNN)
> 28 28 (n² rree)-
Then setting & = min VC .
6Rms 2 and using the closed form of M in Eq. (17), Lemma D.6 states that when
N < =c (1-minf C
sam: 2 C max { v C.
1
2
we have E (It (rer) > = mink V sgg 2 } and thus
J(TT) -[(TBe)) > min 2 C. e 1
Part 2 (Large N). Define the gap on Ybad to be = min 1, v N E and set the reward functions
("O)) = r*()*)
r* (Ybad) =
F()o) =0 f(y*) = min { / = F(ybad) =
and we can check that
E Bii
(F(y) - r" (v)))²
C. RH
A
SMM
min
1, N - I
&pm-
2C
2N
2
2N
38

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Note that for this construction, F(ybad) is the largest reward under so TBON will always play Ybad if ybad NN. which is event that occurs with least constant probability under our choice for Tref
P(ybad E 1xx) -
2 1 1
2N
Using this, we lower bound the regret as
( (( P(ybadd E [NN) E53, ((Tt) - J ( Ybad E DNN
+ P(ybad & DN) B8,, J(x²) -[(TBoN)
Ybad & DNN
> Plybad E (x) E5ix [Tx") - J(FrRo))
Ubad E VNN
Plybad 5N)
c min
N Eken
where in the first inequality we the fact that x* is optimal for r", and in the last inequality we plug in the definition of A.
F,2.2. LOWER BOUNDS UNDER L1 -OVERAEE
Theorem F.4 (Regret lower bound for C" ). For any ERM E (0, 1/4) and C 2 GAM there exists a comparator policy x²
over contexts X = {z} and response space y = zt, and universal constants C1, C22 C3 such that the following statements hold for any p E (0, 1/2].
1. For any E [EAM, }. there exists problem instance r", F) with (x)
CAM and
C (x) Olog
C (x) O(C),
such that, for any < ci (c) (x) any selection algorithu A (Definition F.2) suffers regret J(a)=a) J(TAii)) C2 (cT² (x) (2)) P
2. For any N Z 1, there exists a problem instance (Tref; r"; P) with eZn(x) S SAM and
Ca' (x) = Ollog C)
C% (σ) O(C),
such that the BoN- BoN-Alignen Alignment policy RaoN has regret
=(====)= J [ x)) > C3 N (x)
Proof of Theorem F4. As in the proof of Theorem F.3, x-ddepedenccees are ommitted in the proof below, inclusive of complexity measures such as Em((T" (x)) Tie (x)) and (I)( since there is only a single prompt.
Part 1 (N small). We prove the statement for Ca" I ' otherwise /C= 2 = 2(
For all E [EAM, 1), we will define &ref and n to be the distributions from the construction in Lemma E.5 with C. These policies are defined as follows for all E y = (1. (where we use instead of y to index responses).
3
rie (i)
4
if ifi == [log C7, otherwise.
(1)
2' Tres (i),
39

---

Coverage, Scaling, and Optimality in Inference-Tine Time Alignment
From the proof of Lemma E.5, know that
C
Olog C) and C O(C).
Now fix a choice of E E [ERM: 1 We will now define the reward functions for the construction. Let kg E y is an index that will be specified shortly, and, for i VW define De (i) = 2'
and
k.ke
i < Ke: otherwise.
(1)
if < lis. otherwise.
F(1)
(ke))
(ke)))
For this choice of and r*, we verify that the estimation error is upper bounded as E
E Exger
(F(i) r()))
=3
Σ 4
22(1) + (kka))
Σ 4-
E +
tke EaM
3 ke
.4" -h-
lie
lig
Ek21
3 Kie
S EM
Next, we set
.2. (c=)..)))))
kg
log
We can check that kg S I flog C7, again using the precondition that C' 4 cm 2 1
1
kg S log
S log
[log(C)).
(C*
=22m)²
CAM
Then Lemma D.6 applied with s' = 2 (Ca* 2)) where is an absolute constant, states that, if N c. (CTT -=2) "" any selection algorithm (Definition F.2) has
Drv(m", 2 E (rot) 2 (ert .e?).
(18)
We conclude by lower bounding the regret using Eq. (18). When N < c. (Cat .2)
- = Σ
(1) - m + +r+
Σ
(x* (i))
1=1
1=
r- (ke)
(T (i))
i +1
2 1 (ke)
Ey Eg(( (TT Fret)
> (cT .2)) D
:²)²²
where we have applied Eq. (18) in the last line, and in the first inequality we use the definition of EM (TT", Taat) with M = 1 = 2h, since {hr + 1,...} = {i:
x (() (+)
> 2kz }.
Part (N large). Fix N E zt. We prove the result for N S +. otherwise the stated bound holds trivially. Let
ky = (logg((N) < 7 == [lg C7, so that Thet (kx) 2
40

---

Coverage, Scaling, and Optimality in Inference-Ting Alignment
Next, let AN(i) 2',
and define the reward functions S.kw"
A Ax(i)
i KN if ky, otherwise.
A Ax(i)
if KN if kw. otherwise.
(1)
VKN-AN
f(1)
VkN (x(k))
2
(NN-Ax((kN)
VaN (k()
First, we check the reward ranges, and observe that VhN- (N(())) = V/ .N. have
E2n S 1. For the reward model error, we
Ayy
20 4 (1) + Kv D (kN)
E Es
((())-((1))*
=3
Σ 4- i=NN
3(KiN- 1) EpM
+ KN (kx( -2-
8KN
3(kN - -1)
+
8
li
< Eppe
Second, we show that J(=*) J (Tret) 2 0 long as hN 2 by computing the policies in closed form. Recall that
(i) = 2 if S I, and n" (i) 3 2 4- otherwise. Then by plugging in this expression and the definition of ri
above, we calculate its return as
An -1
(1
An(i)
1
J(m²) = Σ 2-1
+22²
g-hx +
Σ
2.2
Σ 4-1
2
2
i=1
k=
I++
v AKN
A N [k()
α
Σ
2--3
Σ
22-22-ka
2
i=kN+1
/=/+
Recall that
8 Σ 4-
1=
Σ
[v)
Σ
2 43
E
1=1
Am T411
Then grouping terms and substituting this identity,
hy
by
((*))
1 1+
2
AN(() + VAN AN(KN)
Σ 2 2 KN
-Kk
by -1
222
kx
1 +
2 2$
+ 2kN
2 2 KN
8. KNN
8
1=1
d=1
2
1 (ke
1/1
+ 2hv
Eam
(2-Rw 2 2-kxx
KN
8
2
= 2
+ (Ki 1)V/
32 KN

---

Coverage, Scaling, and Optimality in Inference-Ting Alignment
Also, for ree We have
[TTer = 3
KN -1
Σ
4
+
(i)
+ 2
4 kN +
Σ
4-1
+
v VkN AN(KN)
Σ i=
4 - 4
)
))
2
2
1=1
i= +1
ky 1
VkN AN(KN)
+31
+
RM
2 +
(4-RN - 4-
2
32kN
2
i=1
1 V
RM
(1 - kl-kN)
2
32kN
1
EPM
$
+
VV
2
32kN
Together, we obtain that
J(TT) - - 2 (KN - 4) V
32 AN
which is nonnegative whenever ky = [log, N) > 4, or 2 256.
Lastly, we lower bound the regret by considering two cases.
If kN E DN. then BoN will choose KN since kN arg max, f(i), and
1 E [(T)') J(TToN) INN {NN] 2
VEN
A
VkN AN(KN))
-1 32
N Epo
2 2
2
If ky & DN. our design of r- and f ensures that BoN will always choose the response y E 5N with the smallest reward r", while Te is equivalent to choosing E VN uniformly, thus
E (TTee) (froo) KN DNv] 2 0.
Formally, combining these cases gives
J(TT) J(TROo) PKNN E fw) E [(TT) - J((aoo))) | KN Div] + P
P(KN KN $ (iw) B B[J(TT) - ((FRON) INN & Dix) 2 PpKN E fix) VkN AN AN(NNN) + +P(KN & 3iv) (J(T*) - -((Tro)))
2
VkN (N(NN)
P(KN E :ix).
2
(1-c ))
N =
32
where in the last inequality we use the fact that, since Tref Tref (kix) #.
IPkk E 5N) = - P(k & ww)= =1 -11-- - 3
> 1 - -3
N
42

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
F.2.3. SUPPORTING LEMMAS
The following lemma identifies pair of distributions и and Wee where the upper bound M S tight up to loga- rithmic factors, and where it is information-thhooreiiallyy hard approximate using samples from Tref- particular, the distributions exhibit M =( )) and C Ollog(C*)).
Lemma F.5. For any E (0, }] and C z distributions n, Tref X + (()) with
1 2:g there exists a prompt space X {2), response space Y and two
(*)x) (x) = OOlog())); and
C (z) = O(C);
such that N 12.8 any selection algorithm A (Definition F.2) has (rv(T()),mTa(o)) e.
Proof of Lemma F.5. We omit all dependencies given that there is a single prompt, and all instances of log are base
2. The construction is as follows. The response space y = N is countably infinite and indexed by i E {1,2.3, ......... ... Let
= [ogg(C] (the preconditions on e and C are to ensure that 2 1). and define
if < I, and Teef (i) if > 1,
4
(i)
Rrof (i)
7TT
Z
where
7 =
-
and
3
i=1
20
4 (1-2-1) +2 .4-
3x
2- 2
Znd
i=1+1
The coverage coefficient has C Olog C)) since
2
4 2
4-1 Z (I + 1),
C Tref
ref (i)
1
(Z,) y2
(Z,)²
(Z₂)²
(Z,)²
while C OC),, since 5
Zua Z,
2 21og Cl, Next, recall that for any M 1,
(()) Tref
4-
(((h)) Zinet )
(M Traf) Σ (ia
M
To
7
1=1
Note that =(i) ma(li) increases with i. Motivated by this, will set M M shortly, which effectively zeroes out terms S le in the sum above:
2ttt for some index k < to be specified
4
2((A1)
ZTim
Ene. (T,, Fret)
Mk
Z
Z
--
22
Mr
7
7x
20
2-1
0
4-
Ms
Z
Z
1=11
2
4
2
Zo
-
4
Un
Zera
2 -
Z
43

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Now let Z 2 for short, and set [log (z) check that I log (2g) S log(C) S 7, since C 2 2c by
Zx 3
assumption. For this choice of have
E, (T,, Tret) 2 2 (og( - Z) = E.
Recall that MM. = min(M EM (T, Teer) S E}. Since larger M has smaller EM (T,, Tret), we conclude that
M Mr 2 ( Z
Z
4
12
The theorem statement then follows by applying Lemma D.6, which states that when N must have DTV(T, TA)
12. any selection strategy A
E3. Proof of Theorem 3.1 Proof of Theorem 3.1. Recall from Definition D.1 that for given prompt æ and target policy æ,
T(((()) =
Σ
z x) M Trer(y) / x) = E By-mrar(-la))
(
(
TTy x))
M
Trer x))
(x)
C" (x)
Proposition D.3 states that for any M we can upper bound Em (MT(T())) [xe((()) Lemma F.1 results in
which when combined with
M
x)) ((Toovi x))
(c*) (I))
(1 Ess (x), mel(=)))) + 2 VC cz)) M
N
ERn(x)
+ / N INN.Gn c2n(x)
< Rmaxx
+ exp
2
as long as M is large enough such that Ex (I (x),, [))(()) S (x) s 1/2. We will M check that as long as 2 2.20. C='
M
log(4 (x)) we can
(*'())) (x) log( (4 (422 / then EM (x), Tiat (x)) S since
CT (x)
C= (z) log (R max/ (x))
1
Ex((T' (x), (z))
S 2
M
N
Then for any N 2- C=2 (x) log( (R (z)). we have
(Cr
(x:)
N
)) + c/ (x)))((())) + San(a:)
=(m":x)= J [(HooNi x) S Rmaxx
exp
+ v N (x)(
M
2M
Cx' (x) log
1R22
Rmax
+ 2 v (/(((x))
(x) s2x(x) - ERM(Z) + N (x),
N
which completes the first statement of the theorem. The second part of the theorem statement follows from by set- ting N to minimize the RHS of the regret bound above, by balancing the two N-dependent terms. Namely, if
N ca (z) Rmm:
then
(x)
Rmax ERm(x) (x)
;(x;;²)) [TTaoni x) $ Rmax C= (x)) - log
44

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
F.4. Proof of Theorem 3.2
Proof of Theorem 3.2. The first part of the theorem statement follows from Theorem F.3 with C 2, which then states that
; (Toon) 2 c. min VainnVV--ealae =fa(()), }
as long as 2 1, where a universal constant.
The second part of the theorem statement follows from invoking Theorem F.4 with p 1 and C ERM( which states
that if N = 0 RM (xx)
then
J [ x)) - J (TBBNi x) > c1 (f) log(Em(()))
while = =5 (5(5mn (x) then
;(=";²) [ x)) >>00 V N ( 2 5 =<)((t))
F.5. Proof of Theorem 3.4 Proof Theorem 3.4. When M C (x) we have En (T* (x)) (x)( = and using this choice of M Lemma F.1 gives
N
+ + / C (x) (x) + ERN(I)
xx==2))= -J (Rsoon x) S Rmax exp
+ V N Ex)()))
C (x)
2
which proves the first part of the theorem statement. For the second, we observe for any N 2 C (x)) log Rmax/ Ean (1)), we have
[ xx) - (FTsNNi x) S ExM(Z) + VN (x),
and if N x C (x) log( Rmax/ /mmp///m(()))))))) (x) additionally, then
J(T x)) J ( x)) 2 C 3 (x) =bx(x) log( Rmax/ SMM (a)()))))))))))))))) (x))
F6. Additional Results
Here, additional result, we prove regret guarantee for BoN-Alignment in terms of the information-theorrticc quan- tities M and M. (Definition D.2). Our main theorems, Theorem 3.1 and Theorem 3.4, can be viewed as more inter- pretable relaxations that isolate the dependencies on coverage coefficients and N.
Theorem F66 (BoN regret with M ). Given prompt x, for any [0, and N and comparator policy म the BoN policy TeON satisfies
J(m x) - [(TooNi x) S Rmax E (E+exp) exp
N
)) +2 V (x) + ERM(I)
+ V N (r).
2M
2
In particular, N = 2M log Can(ar) 2floo
(T)) (TTENN x²) S Rmax.E E (+ (x) + MM'' =x)(2) log (x)(2)
2.
45

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
Proof of Theorem F. We will apply Lemma E.1 with M MM for [0, 3/- Whenever (m(xx(x) (x)( & 2 by definition, since
S 1/2 have
1 2 E Emg (2), (e)(())) S
As result, - Emg; (T" (2)), Trat (x)) 2 2. and Lemma F.1 states that, for any N.
(=texp/ (- (-2 )) + y y (x)))((()) + ERM(x)
N
J(x"; - [TTzoN: 2) S Rmax
2 + v N . (x)(
Setting N 2M log
Corlat) 21lmrr
we obtain
[RM(I)) Rmmax
=xx);=)) x I Rmax 8 + (* (x) eff(ar) em(()) 1 2.M ekllar) log
Rmax 8 + / (x((x) (2)))())))))))) ME'' =x)( -log ERn(x)
Rmxx
46

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
G. Proofs from Section 4
The proof' below are conditioned on a single prompt æ, and as a result we omit & dependencies to simplify presentation throughout. We refer x-dependent quantities via their z-independent analogs, e.g.. J(;;,) (T),, ((x) = etc.
G.1. Proof of Theorem 4.1
Proof of Theorem 4.1. In the proof below, for a reward model r we define the expected return under it to be J,(T;; (; == (ay (r, y)], and using this definition we can also write J(x; x) = J,- (T; x). With prompt dependencies ommitted, we equivalently write J, x) = (x)
Given reward function f. define for normalization constant À the following functions:
(y) Tree ( A))
(19)
$(1)
(AA) Ee [relu (8 (f(y) A))],
(20)
and
1 (elu((31(F(u)) 1))
(AA)
N
We analyze the regret using the following decomposition, where Ā = X(x) is the output of Eq. (9) in Algorithm 2.
J(T²) ((F) -[mm((
Jz(m²)
Jz(#=) JF((T)) J J(TT) ( J(T)
(TI)
(T2)
(T3)
(T4)
For (T2), recall that À computed using using Algorithm in Eq. (9), which Lemma C.1 shows obtains À such that (A) 1. Further, the procedure in Algorithm 3 is equivalent to solving the optimization problem in Lemma G.2 with ree unif (Dx) and 1, and, result, we have X E [-8, Rmax f.. Now for a fixed N, the bound in Lemma G.3 states that with probability at least 1 - 8, for any d E (0,1) 1) we have
7
9 EN S {() S EN.
where EN : 12 Amm
log
is the expression the RHS of the bound. Then to have (A)
[
with
probability 2
is sufficient to choose large enough such that x S 1 which is satisfied when
4-
N 2 48 Rmax + B log
6
38
Next, let 3 (2) [[2 }]}
denote the aforementioned high probbbiibby event. Using Lemma G. we may bound
Jx(TT) - 1x(Tx) S (P()) -[()( - Jz(TT) El +P((-E) [[J+(T") 1z(TT) E
< { - JF(TT) El + 8 Rmax
30
8 CTS + 5 Rmax:
< 4
Cx'
By setting 8- =
Cou Raw
we obtain that
(T2) = Jz(mT) J)((T)) S Cx B Cx EAM
33
4
N N = 112(() (2((22111
Rmyz)
log
Rmiz TT-m
47

---

Coverage, Scaling, and Optimality in Inference-Tine Time Alignment
For (T4), from Lemma D.4 with M
Rage
we have
N.
(T5( S exp
2 Rmax
thus as long as N 2
Rax
log
Rias Eim
have
DTv OTV(TT) S
ERM Rmaa
As result,
(T4) = J(TT) - J( & Rmax Drv Div( I ERM-
For (TI), we know from the standard Cauchy-Schward bound that
(TI) = J(m)) J=(=*) = Eyy-a (v) S Ve c
Lastly, for (T3), Cauchy-Schwarz and the AM-GM inequality imply that
E
(T3) (+(5s) J(T)) Eyywx ((v) r" r²)l S VTT E2H S 4
C +
Putting things together, long N 2 57 (1(11 Rig
Rap
g
log
Rix B-5m
have
- J(F) S
v exp +
33
C
+
ERM
25
3
We set 8 balance the terms for the final result.
G.1.1. SUPPORTING LEMMAS
Throughout this section, we consider fix prompt æ E X and omit dependence on æ as above.
Lemma G.I. Suppose we have such that (()) = a for some a > (ef. Eg. (20)). Then for a defined Eg. (19), holds for any policy n that
aB C
aB
J=(T) - JF(TA)
S
Ca.
2
2
In particular, a E [1. [ then
33
3
Je(m)= JF(Tx) 5
C
4
Proof of Lemma G. Let = (A) and define n = relu (elu(331((i))
))) = a xx, so that n E ()') (cf. Eq. (21)).
Further, for the comparator policy म, define = a x E ()). We know from Lemma G.2 that
8 c fer
Jx(m') J=( /
2
It can be observed that C=' = a² c and C=x' = = C as well as (JJ((T) - J=(Tx)) J+(TT) - J=(Tx'), therefore
a8
a3
JT(T): - ((TA) v
c
2
2
For the second statement, for any E [ 3
we have
3
1
3
33
J+(T) - ((()) <
mm
e
c
2
2
4
48

---

Coverage, Scaling, and Optimality in Inference- Time Alignment
Lemma G.2. Let reward function and parumeter a >> 0 be given, and define
Aa(3) { RR (v)
(21)
Then there exists a choice of À E [J(Tret) - a33, maxyey r(y) - a.8 such that Eyey T(1) = a. Furthermore, given any such that Eyey Tty) a.
T(V) (v) relu(3-1(r()) 2))
the optimal solution to
arg max =)),
( ca
(22)
Proof of Lemma G.2. First we rewrite the objective in Eq. (22) in primal form,
8 cm -J(
arg min
TERV
Σ yEY
(1)
( 5 0, Vy
and we can verify that Slater's condition holds, because the objective is convex, since ((T) is affine and C is (strongly) convex, and there exists at least one strictly feasible point, an example being the function n' that sets T T'(y) = 137 for all
E V.
Under strong duality, the KKT conditions are both necessary and sufficient for optimality; further, the objective has unique minimum due to strong convexity, and therefore, to prove the theorem statement, is sufficient to show that the proposed æ satisfies the KKT conditions.
For primal variable æ and dual variables (v, A), the Lagrangian is given by
min TERV
max AER
((T, = Σ [(())(()) c + 2
3
A
Σ T(V) a - -
- ->(())(
DEV
yEy
DEY
and under strong duality, we know that the optimal primal and dual variables (T,, v, A) satisfy
π 2 0
Σ, (y) a v 22
T(y) v(y) for all (complementary slackness).
V=L(m, (v, ) = 0 (first-order condition).
From the first-order condition V, (,,,,,AAA
O, know that satisfies for all y Y:
T(y)
r(v) B Trel(y)
A + v(v) 0,
or after rearranging,
M ( niet (v) 8 (r(v) X v(v)).
(23)
Now consider a fixed y E V. We consider three cases:
49

---

Coverage, Scaling, and Optimality in Inference-Time Alignment
If r(v) x < O, then we must have v(v) 2 - (r(y) X) 0 to satisfy mty) 0 by Eq. (23). By complementary slackness, this implies that (t) 0.
If r(v) À O, then Eq. (23) gives (1) (Tar( ( which implies π (vy) by complementary slackness.
r À > O. then r(y) - À + v(y) > 0 (since v(y) 2 0), which in turn gives ( > by Eq. (23). This implies that v(y) = by complementary slackness.
Combining these cases, we conclude that
Tvy) = {
O, Tret (v) X)
r(y) x 50 r(y) X>
This is equivalent to (t) = (v) relu(3 - A)), which is also optimal under strong duality. Finally, the condition Ey π (y) = a implies that À must be chosen such π E ())) normalizes to a.
Lemma G.3. Recall (A) Bynrr
,])], and given N samples from y1......h YN rief define
1 N ((1) = N
Σ
relu relu( (r(v)) A)).
1=1
Fix any 7 R4. With probability at least for all X E [-7; Rimax 7), have
log
60
max [
(000-6(()) (()) (()) (()) - {0)) -
Rmax + y
35
12
B
N
Proof Lemma G.3. We start with Bernstein's ' inequality, which states that for a bounded random variable X E [a, b). with probability at least - 8', the empirical mean ž[x] = Em X, satisfies
V[X] ())(3)
4(b a) log(3)
[[x] - [[X] 2
where V[X] is the variance of X. Now fix A, and let the random variable X relu(r(y) A). Since [-7, Rmax - 7], the random variable X [0, Rmgtt and henceforth refer the range R Rm We can bound the variance of this random variable as
< R- B R- (AA.
Then with probability at least 1 8', have
(ogg)
4Rlog(
2(A) S(1)| 522
N
N
{(>)
8Rlog( 2)
4Rlog( 2))
+
N
N
+(A)
loglog
N
where the AM-GM inequality in the second inequality. This then implies that
((A)
12R 12Rlog
(AA) $(1) -
+
and
8
N
$(A) +(1) < (())
12R log 2)
8
N
50

---

Coverage, Scaling, and Optimality in Cnference-Time Alignment
which after rearranging and plugging in the expression for R. results in
7 (A) ((A) - 12
Rmax + 7
log z
and
(24)
8
B
NV
Rmax + 7
log (
(AA) ((A)= 12
B
N
which proves that the desired inequality holds for any x fixed a-priori.
We now convert this guarantee into a uniform-in-A bound. Consider the interval [->; Rmax 7], and, for some fixed e, let
A { Y + e E..i :i:i= I,.... [ax]] }. which has cardinality |Ael < 2R Then for any À E [-7,, Rmax - 7]. we can always find X E Ag such that | X1 S c, for which
(elu(331(r1()) 2]) - relu (3 - X)) s 1-- -
Applying Eq. (24) and taking union bound, with probability at least we have that for all X E Ag.
7 ( ((x)= S 12
Rmmax 7
log
eo N
Rmax + ?
log
1.eaa 66 N
((A) 8
(xx) s 12
B
thus for all A E [-y, Rmax 7/.
7 (A) ((A)= s
15
Rmax + 7
log 4R
8
8 3
3
9 (A)) <
15
Rmax + 7
log
4a ed
((A)
+ 12
8
8
3
N
and choosing E = 15
8
results in
log
60 5
7 ((A) $(1)=
1
Rmax + ?
+ ++12
B
N
log
60 BM
((A) 9 (())
Rmax +
S 8
+
12
8
N
which when combined proves the lemma statement.
G.2. Proof of Theorem 4.2
Proof Theorem 4.2. Fix N S 1. We apply the first part of Theorem F.4 with ERN = ERH, p= 2. C = ( ) and
N (20 Note that the construction has C (x) O(log C). With this set of parameters, any algorithm A using N' such that
N' << (c (x) = C1
2N
2o
must suffer regret at least
(C (z) -2)
> >
1
Cx (x)
02
2c
C (x) N
02
1
20
N
51

---

Coverage, Scaling, and Optimality in Inference-Timg Alignment
which is therefore a lower bound that applies N' = N.
52


Reviews:
[{"review_id": "tV948TwbRB", "reviewer": "Reviewer_jQEp", "summary": "The paper analyzes the Best-of-N (BoN) algorithm for selecting among language model generations and introduces InferenceTimePessimism, a new algorithm that mitigates reward hacking. The authors formalize inference-time alignment as improving a pre-trained policy’s responses using an imperfect reward model. They show that BoN can achieve optimal performance under strict coverage but suffers from reward hacking when N is large. InferenceTimePessimism is proven to be optimal and scaling-monotonic, with empirical validation across tasks like GSM8K, MMLU, and MATH.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "The claims are well-supported by theoretical proofs and empirical results. The authors demonstrate BoN's limitations and prove InferenceTimePessimism's optimality and robustness through experiments on multiple tasks and models.", "methods_and_evaluation_criteria": "The methods are appropriate, focusing on inference-time alignment and evaluated using standard benchmarks (e.g., GSM8K, MMLU). The criteria, including accuracy and estimated reward, effectively measure performance.", "theoretical_claims": "The theoretical claims are supported by rigorous proofs. The authors prove InferenceTimePessimism achieves optimal regret and is scaling-monotonic, with detailed proofs in the supplementary material.", "experimental_designs_or_analyses": "The experiments are well-designed, covering multiple tasks and models. The results show InferenceTimePessimism avoids reward hacking and outperforms BoN in many cases.", "relation_to_broader_scientific_literature": "The paper connects well to prior work on reward overoptimization and offline RL, extending ideas like pessimism to inference-time alignment.", "essential_references_not_discussed": "The paper could reference more recent work on preference-based learning and scaling laws for language models to provide additional context.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Addresses a timely problem with theoretical insights and practical algorithms.\n\n2. InferenceTimePessimism is a novel contribution with rigorous proofs and empirical validation.\n\n3. The proposed methods work reasonably well.\n\nWeaknesses:\n\n1. Limited guidance on tuning the regularization parameter $\\beta$\n\n2. Experiments focus on mathematical tasks; more diverse tasks (e.g., dialogue) would strengthen generalizability.\n\nQ1. How should practitioners choose $\\beta$ in InferenceTimePessimism?\n\nQ2. Have you considered evaluating on more diverse tasks like open-ended dialogue?\n\nQ3. What are the computational costs of InferenceTimePessimism compared to BoN?", "other_comments_or_suggestions": "Please see above", "questions_for_authors": "Please see above", "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": "VWw6slrl9X", "reviewer": "Reviewer_KBSW", "summary": "The paper first theoretically shows the overoptimization problem is inevitable with the well-known best-of-N algorithm, especially when N increases. Then they propose Inference-Time Pessimism Algorithm, and show that the proposed algorithm resolves the overoptimization problem and also achieves optimal regret rate in terms of the reward approximation error. The paper also provides experiments to validate their theoretical findings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "**Claims with evidences**\n- On the Best-of-N (BoN) algorithm, the paper shows that (i) it causes overoptimization in the worst cases when N increases (Theorem 3.2), and (ii) the regret achieved by BoN is also suboptimal in terms of $\\epsilon_{RM}$, the approximation error of an estimated reward. (Theorem 3.1, 3.2)\n- To resolve these issues, the paper proposes Inference-Time Pessimism Algorithm (Algorithm 1), which is a sampling procedure from $\\chi^2$-regularized reward maximizing distribution, by rejection sampling with N samples from the reference model. The proposed algorithm does not cause overoptimization by its nature, and also achieves optimal regret bound in terms of $\\epsilon_{RM}$. (Theorem 4.1, 4.2)\n- Experimental results:\n  - Figure 1 validates that the proposed algorithm with tuned hyperparameter $\\beta$, the strength of $\\chi^2$ regularization, successfully avoids the overoptimization issue caused in BoN when N increases.\n  - Figure 2 investigates the behavior of the proposed algorithm with varying $\\beta$ compared to the BoN algorithm, with fixed $N=2^{13}$. However, this is an extreme setting and also unfair for BoN.\n\nOverall, the claims are theoretically well-supported, and experiments validate the benefits of the proposed algorithms as predicted from their theories. However, I still have some concerns especially about the experimental evidences:\n- The paper claims that the proposed algorithm is superior to BoN because (i) it avoids overoptimization and (ii) it achieves the improved regret rate. However, experimental results only verify the first benefit (i), and it is unclear how the second benefit (ii) appears in the real-world experiments.\n- The performance of the proposed algorithm seems to depend on the choice of the hyperparameter of regularization strength $\\beta$, but the behavior with changing $\\beta$ is only shown with the extreme setting of $N=2^{13}$.", "methods_and_evaluation_criteria": "The proposed method makes sense and is well-motivated. The experimental settings follow the standard ones.", "theoretical_claims": "I read some proofs in Appendix to understand the theoretical results, but did not check all of them.", "experimental_designs_or_analyses": "The experimental designs and analyses seem sound.", "relation_to_broader_scientific_literature": "The proposed algorithm successfully resolves the overoptimization problem caused with the BoN algorithm, which is a widely used method for inference-time alignment. In addition to analyses of the proposed algorithm, the theoretical results on BoN themselves are also novel and insightful.", "essential_references_not_discussed": "Yang et al. [1] also investigates the theoretical properties of the BoN algorithm in relation to KL-regularized reward-maximizing distribution, but not cited in this paper.\n\n[1] Yang et al., \"Asymptotics of Language Model Alignment\" (ISIT'24)", "other_strengths_and_weaknesses": "See Claims and Evidences.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See Claims and Evidences.", "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": "PuDOboj6Dg", "reviewer": "Reviewer_WiRT", "summary": "This paper examines inference-time alignment, where additional computation at generation time is used to improve language model outputs. Specifically, the authors focus on the widely used best-of-$n$ approach, which generates multiple responses and selects the one with the highest reward according to a (possibly imperfect) reward model.\nThe key contribution is a theoretical framework that explains when and why best-of-$n$ works, and more importantly, when it fails. The authors show that while best-of-$n$ can be effective with proper tuning, it inevitably suffers from \"reward hacking\" when scaled too aggressively. This happens because imperfections in the reward model become amplified when $n$ is large.\nTo address this, they introduce InferenceTimePessimism, an algorithm that deliberately uses inference-time computation to quantify and account for uncertainty in the reward model. Their theoretical analysis proves this approach is optimal in terms of regret and maintains performance even with increased computation.\nThe authors validate their theoretical findings with experiments on benchmarks using various language and reward models, demonstrating that their algorithm can mitigate reward overoptimization.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "TBA", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "### Strengths\n\n- **Novel Theoretical Framework:** The paper is the first to build the theoretical framework of best-of-$n$ with ideas from offline RL, with the core notion of coverage.\n- **Theoretical Guarantees:** The authors first give comprehensive results (both upper and lower bounds) of best-of-$n$. The results can be stronger when a uniform converage is guaranteed. Then they prove their algorithm, InferenceTimePessimism, is regret-optimal within their framework, which is a significant theoretical contribution.\n- **Practical Algorithm:** The authors give the practical implementation for InferenceTimePessimism and perform extensive experimental validation on multiple tasks, reward models, and language models.\n\n### Weaknesses\n\n- **Lacking some cases in theory:** For Theorem 3.1, the authors didn't discuss the case where $\\varepsilon_{RM} (x) = 0$. If we directly apply the results, then the regret is unbounded, which seems counter-intuitive. For Theorem 4.1, the authors didn't give a dependency on $N$, which makes it hard to compare with Theorem 3.1.", "other_comments_or_suggestions": "No", "questions_for_authors": "Regarding the weakness, what is the bound for best-of-$n$ when $\\varepsilon_{RM} (x) = 0$? What is the dependency on $N$ for InferenceTimePessimism?", "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": "lOOGyRMfFo", "reviewer": "Reviewer_rHW3", "summary": "This paper investigates inference-time alignment in language models and demonstrates that naively scaling the Best-of-N heuristic leads to reward hacking, causing performance degradation beyond a certain computational threshold. The authors introduce a new algorithm, InferenceTimePessimism, which leverages χ²-regularization and rejection sampling to mitigate reward hacking effectively. The authors provide theoretical guarantees showing InferenceTimePessimism achieves optimal regret.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "The paper's claims are supported by theoretical proofs and experimental results. The paper clearly shows that the fundamental limitations of Best-of-N alignment through explicit regret analysis. In addition, it also show the robustness and optimal regret guarantees of InferenceTimePessimism.", "methods_and_evaluation_criteria": "The methods and evaluation criteria selected are appropriate and justified. The use of standard benchmark datasets such as GSM8K, MMLU, and MATH is suitable to validate alignment effectiveness and reward model quality.", "theoretical_claims": "The correctness of the theoretical claims was found to be solid. The proofs of lower bounds establishing the necessity of coverage and the limitations of the Best-of-N approach are rigorous and correct.", "experimental_designs_or_analyses": "The experimental designs were found to be sound. Experiments effectively demonstrate the robustness of InferenceTimePessimism in mitigating reward hacking and improving performance across multiple reward models and tasks.", "relation_to_broader_scientific_literature": "Not sure about the relation To broader scientific literature.", "essential_references_not_discussed": "Not sure about the essential references not discussed.", "other_strengths_and_weaknesses": "- Novel theoretical insights significantly advancing understanding of inference-time alignment.\n- Clearly articulated and robust theoretical framework that provides meaningful guidance for practical algorithm design.\n- Empirical validation effectively demonstrates theoretical predictions, enhancing practical relevance.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Have you tested or analyzed the performance and robustness of InferenceTimePessimism with significantly noisier or weaker reward models? If so, how sensitive is the algorithm to degradation in reward model accuracy? Similarly, have you experimented with or considered extending InferenceTimePessimism to more open-ended, subjective, or complex tasks, and what challenges might arise in these settings?", "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:

Meta-review: This paper provides a theoretical analysis of Best-of-N (BoN) sampling for inference-time alignment, formalizing the problem and highlighting BoN's key limitations regarding reward hacking and suboptimality. The introduction and analysis of their pessimistic algorithm is a good contribution, and includes regret guarantees and scaling-monotonicity, which are mostly supported by empirical results. It is still unclear how to optimally tune the hyperparameter of the proposed approach without an oracle. Also, an analysis of the computational overhead compared to standard BoN is missing. While the work is self-contained and focuses correctly on inference-time mechanisms, a direct comparison to inference-aware training methods (like those in the IAFT paper) may add additional context.
Decision: Accept (poster)