Self-Improvement in Language Models: The Sharpening Mechanism
Authors: Audrey Huang
Adam Block
Dylan J Foster
Dhruv Rohatgi
Cyril Zhang
Max Simchowitz
Jordan T. Ash
Akshay Krishnamurthy
Venue: ICLR 2025 Oral (2025)
Keywords: Learning theory
Sample complexity
Self-Improvement
Language Models
Primary area: learning theory
TL;DR: We offer a new theoretical perspective on the possibility of self-improvement in language models.

Abstract: Recent work in language modeling has raised the possibility of “self-improvement,” where an LLM evaluates and refines its own generations to achieve higher performance without external feedback. It is impossible for this self-improvement to create information that is not already in the model, so why should we expect that this will lead to improved capabilities? We offer a new theoretical perspective on the capabilities of self-improvement through a lens we refer to as “sharpening.” Motivated by the observation that language models are often better at verifying response quality than they are at generating correct responses, we formalize self-improvement as using the model itself as a verifier during post-training in order to ‘sharpen’ the model to one placing large mass on high-quality sequences, thereby amortizing the expensive inference-time computation of generating good sequences. We begin by introducing a new statistical framework for sharpening in which the learner has sample access to a pre-trained base policy. Then, we analyze two natural families of self improvement algorithms based on SFT and RLHF. We find that (i) the SFT-based approach is minimax optimal whenever the initial model has sufficient coverage, but (ii) the RLHF-based approach can improve over SFT-based self- improvement by leveraging online exploration, bypassing the need for coverage. We view these findings as a starting point toward a foundational understanding that can guide the design and evaluation of self-improvement algorithms.

Published as a conference paper at ICLR 2025
SELF-IMPROVEMENT IN LANGUAGE MODELS: THE SHARPENING MECHANISM
Audrey Huang"
Adam Block'
Dylan J. Foster*
UTUC
Microsoft Research
Microsoft Research
audreyh56i ilinois. edu
bl ockadam@mi crosoft. com
Dhruv Rohatgi
Cyril Zhang
Max Simchowitz
MIT
Microsoft Research cyr pyrilzhangemicroofft.comm
CMU
drohatgiemic
msimchow@andrew.co cmu. edu
Jordan T. Ash
Akshay Krishnamurthy
Microsoft Research ash. wth.jjordanmmicrosfft.cccm
Microsoft Research
akshaykr@microooff. com
ABSTRACT
Recent work language modeling has raised the possibility of self-improvement, where a language models evaluates and refines its own generations to achieve higher performance without external feedback. It is impossible for this self-impnn leff-improvement to create information that is not already in the model, so why should expect that this will lead to improved capabilities?
We offer a new perspective on the capabilities of self-improvement through a lens we refer to as sharpening. Motivated by the observation that language models are often better at verifying response quality than they are at generating correct responses, formalize self-improvement as using the model itself as verifier during post-training in order to "sharpen" the model to one placing large mass on high-quality sequences, thereby amortizing the expensive inference-time computation of generating good sequences. We begin by introducing new statistical framework for sharpening in which the learner aims to sharpen a pre-trained base policy via sample access, and establish fundamental limits. Then, we analyze two natural families of self-improvement algorithms based on SFT and RLHF. We find that (i) the SFT-based approach is minimax optimal whenever the initial model has sufficient coverage, but (ii) the RLHF-based approach can improve
SFT-based seff-improvement by leveraging online exploration, bypassing the need for coverage. Finally, we empirically validate the sharpening mechanism via inference-time and amortization experiments. We view these findings as a starting point toward a foundational understanding that can guide the design and evaluation of seff-improvement algorithms.
INTRODUCTION
Contemporary language models are remarkably proficient on a wide range of natural language tasks (Brown al., 2020; Ouyang et al., 2022; Touvron et al., 2023; OpenAI, 2023; Google, 2023), but inherit shortcomings of the data on which they were trained. A fundamental challenge to achieve better performance than what directly induced by the distribution of available, human-genen -enerraed training data. To this end, recent work (Huang et al., 2022; Wang et al., 2022: Bai et al., 2022b; Pang et al., 2023; Yuan al., 2024) has raised the possibility of iepfo-improvement"" where model tapicallyy through forms of self-play or self-training in which the model critiques its own generations- to improve on its own, without external feedback. This phenomenon is somewhat counterintuitive; at first glance it would seem to disagree with the well-known data-processing inequality (Cover, 1999), which implies that no form of self-training should be able to create
"Equal contribution.

---

Published as a conference paper at ICLR 2025
BoN: % Lift over Gready
MATH
145
P5B (Mini) on MATH
PMB (Mbo
0.7
-2.8
17.0
4.2
4.5
3.8
Conrect
Plas (Nau
9.9
4.1
3.2
5.9
6.0
-0.9
% Lift mvrr Droady
Incocrett
100
thoath
(Miz)
Count
82-
PAD (Nfedaan)
-2.1
-4.4
1.8
-1.5
3.3
-0.7
PN2 (NDm0
1913 mamai
00-
Matral/8
28.6
PR13 (MAdiuu))
126.0
6
Mismi/711
45-
Liaradd
020-3.5
3.4
.1.88
-1044
-0.5
6.7
-7.0
0.7.3.3
10
25
50
Probability
130
(b)
(c)
Figure I: Validation of maximum-likclihodd sharpening, via Best-of-N (BoN) sampling, at inference time. (a) Percent accuracy improvement over greedy decoding for BoN sharpening with N 50 on 6 tasks and 7 models, colored by performance. (b) Percent accuracy improvement over greedy for BoN sharpening as function of N for 7 different models on the MATH dataset.
(c) Distribution of Sequence-levee log probabilities for responses sampled from 5-Mini (N = 1) on the MATH dataset, conditioned on correctness. Correct completions have noticeably higher likelihood than incorrect completions, demonstrating the utility of inference-time sharpening.
information not already in the model. This motivates the question of why we should expect such supervision-free interventions will lead to stronger reasoning and planning capabilities.
A dominant hypothesis for why improvement without external feedback might be possible is that models contain "hidden knowledge" (Hinton al., 2015) that is difficult access. Self-improvement, rather than creating knowledge from nothing, is means of extracting and distilling this knowledge into a more accessible form, and thus is a computational phenomenon rather than a statistical one. hypothesis (Furlanello
While there is growing body of empirical evidence for this hidden-knowledd et al., 2018; Gotmare et al., 2019; Dong et al., 2019; Abnar et al., 2020; Allen-Zhu & Li, 2020), particu- larly in the context of self-distillation, a fundamental understanding of self improvement remains miss- ing. Concretely, where in the model is this hidden knowledge, and when and how can it be extracted?
1.1 OUR PERSPECTIVE: THE SHARPENING MECHANISM
In this paper we posit source of hidden knowledge, and offer formal perspective on how to extract it. Our starting point is the widely observed phenomenon that language models are often better at ver- ifying whether responses
correct than they are at generating correct responses (Huang et al., 2022; Wang et al., 2022; Bai et al., 2022b; Pang et al., 2023; Yuan et al., 2024). This gap may be explained by the theory of computational complexity, which suggests that generating high-quality responses can be less computationally tractable than verification (Cook, 1971; Levin, 1973; Karp, 1972). In autore- gressive language modeling, computing the most likely response for given prompt is NP-hard the worst case (Appendix E), whereas the model's 's likelihood for a given response can be easily evaluated.
We view self-improvement as any attempt to narrow this gap, i.e., use the model as its own verifier to improve generation and sharpen the model toward high-quality responses. Formally, consider a learner with access to a base model Toase X' + A()) representing conditional distribution that maps a prompt æ E X' to a distribution over responses (i.e., Toase (y ar) the probability that the model generates the response given the prompt x). We posit that Wbase has already been trained in some manner (e.g., through next-token prediction or additional post-training steps such as SFT or RLHF), with the key feature being that Tbase is a good verifier, as measured by some self-reward function Tsalf (y I;; Thase) measuring model certainty. The self-reward function derived purely from the base model Toase. without external supervision feedback. Examples include normalized and/or regularized sequence likelihood (Meister et al., 2020), models-as-jun ausjuge (Zheng et al., 2024; Yuan et al., 2024; Wu et al., 2024a; Wang al., 2024), and model confidence (Wang & Zhou, 2024).
'Our general results are agnostic to the structure X. X.Y. Yr and Thase. but an important special case for language modeling is the autoregressive setting where y = 1 for a vocabulary space V and sequence length H, and where wasse has the autoregressive structure Trase (V1:27 .)) = T Tosse, Vi:h-1, 2)) for y = 91:1 y.
2

---

Published as a conference paper at ICLR 2025
Sharpening
We refer sharpening as any process that tilts Thase toward responses that more certain in the sense that they enjoy greater self-reward sself- That is, a sharpened model I is one that (approximately) maximizes the self-reward:
(a) z arg max TseiF x;; Masse)
yEY
An important special case for sharpening is in language/autoregressive modeling. Here, have y = VHH for a vocabulary space V and sequence length H, and Taase has the autoregressive structure (V: x) = I (y). (1:A-1.2) for y y1-H y Sharpening in this setting pertains to entire responses, i.e., the optimization over responses in Eq. (1) is the sequence level. In contrast, popular decoding strategies such as greedy, low-temperature sampling, and beam search operate at the token-level; nevertheless, they can viewed as heuristics for inference-time sharpening. ? The combinatorial response space can make sharpening computationally demanding and so, an appealing alternative to inference-time sharpening is amortization via self-training (Section 2). The latter captures many existing self-training schemes (Huang et al., 2022; Wang et al., 2022; Bai et al., 2022b; Pang et al., 2023; Yuan et al., 2024), and is the main focus of this paper; we use the term sharpening without further qualification to refer to the latter.
We refer to the sharpening mechanism as the phenomenon where responses from model with the highest certainty (in the sense of large self-reward rseir) exhibit the greatest performance on a task of interest. Though it is unclear a-priori whether there are self-rewards related to task performance, the successes of seff-improvement in prior works (Huang et al., 2022; Wang et al., 2022; Bai et al., 2022b; Pang et al., 2023; Yuan et al., 2024) give strong positive evidence. These works suggest that, in many settings, models do have hidden knowledge: the model's own self-reward correlates with response quality, but it is computationally challenging to generate high self-rewarding and thus responses. It is the role of (algorithmic) sharpening to leverage these verifications to improve the quality of generations, despite computational difficulty.
high
1.2 CONTRIBUTIONS
We initiate the theoretical study of self- aef-immrrvvement via the sharpening mechanism. We disentangle the choice of self-reward from the algorithms used to optimize it, and aim to understand: (i) When and how does self-training achieve sharpening? (ii) What the fundamental limits for such algorithms?
Algorithms for sharpening (Section 2). The starting point for our work is consider natural families of self-improvement algorithms based on supervised fine-tuning (SFT) and reinforcement learning (RL/RLHF), respectively, SFT-Sharpening and RLHF- LLHF--Shappening Both algorithms amor- tize the sharpening objective (1) into a dedicated post-trrininggfine-tuiiin tuning phase:
SFT-Sharpening filters responses where the self-reward [seir(y)
x;; Moase is large and fine-tunes on the resulting dataset, invoking common SFT pipelines (Amini et al., 2024; Sessa et al., 2024).
RLHF-Shar SaHF-Shhrpeniig directly applies reinforcement learning techniques (e.g., PPO (Schulman et al., 2017) or DPO (Rafailov et al., 2023)) to optimize the self-reward function (seir(y) 2; Mbase).
In the remainder of the paper, we introduce a theoretical framework to analyze the performance of these algorithms. Our main contributions are follows.
hisimum--ikelihoodd sharpening objective (Section 3.1). As a concrete proposal for one source of hidden knowledge, we focus on self-rewards defined by the model's sequence- log bog-rrbbabilities:
Tseir (1 | x Toase) := log Tbase(y) (x)
(2)
This is a stylized self-reward function, which offers perhaps the simplest objective for self- improvement in the absence of external feedback (i.e., purely supervision-free), yet also connects self-improvemmnn to a rich body of theoretical computer science literature on computational trade-offs for optimization (inference) versus sampling (Appendix B). Despite its simplicity, meximum-likkllhen sharpening is already sufficient to achieve non-trivial performance gains over
Moor sophisticated decnding strategies like normalizee/hegularized sequence likelihood (Meister et al., 2020) tffain-of-thoughh decnding (Wang& & Zhou, 2024) also admit an interpretation sharpening; see Appendix B.
3

---

Published as a conference paper at ICLR 2025
greedy decoding on range of reasoning tasks with several language models; (Figure 1). We believe can serve as a starting point toward understanding forms of self-improvement that use more sophisticated self-rewards (Huang et al., 2022; Wang et al., 2022; Pang al., 2023; Yuan et al., 2024).
A statistical framework for sharpening (Sections 3.2 and 3.3). Though the goal of sharpening sharpening
is computational in nature, we recast self-training according to the minximum-likelliban objective Eq. (2) statistical problem where we aim to produce a model upproximating (1) using polynomial number of (i) sample prompts x ~ μt, (ii) sampling queries of the form y Thase (2:) and (iii) likelihood evaluations of the form Tasse (y x). Evaluating the efficiency of the algorithm through the number of such queries, this abstraction offers a natural way to evaluate the performance of smmproeemen/sharpeing algorithms and establish fundamental limits; we use our framework to prove new lower bounds that highlight the importance of the base model's Isss coverage.
Analysis of sharpening algorithms (Section 4). Within statistical framework for sharpening, we show that SFT-Sharpening and RLHF-Sharpenin provably converge to sharpened models, establishing several results: (i) SFT-Sharpenimg is minimax optimal, and learns sharpened model whenever Tasse has sufficient coverage (we also show that a novel variant based on adaptive sampling can sidestep the minimax lower bound); (ii) RLHF-Sharpening benefits from on-policy exploration, and can bypass the need for coverage improving over SFT -harphappnn
Empirical investigation (Appendix A). We explore empirically the extent which our theoretical framework and methods improve language model performance in a variety of tasks. We consider three choices of self-reward an extensive list of model-dataset pairs and conclude that sharpening can often improve performance. We then implement one of our algorithms, SFT-Sharpening, on subset of these model-dataset pairs and observe significant positive effect on performance. A summary of our inference-time experiments can be found in Figure 1.
1.3 RELATED WORK
Our work is most directly related growing body of empirical research that studies self-training for language models in a supervision-free setting with no external feedback (Huang et al., 2022; Wang et al., 2022: Bai al., 2022b; Pang et al., 2023; Yuan et al., 2024). The specific algorithms we study can be viewed as applications of standard alignment algorithms (Amini et al., 2024; Sessa al., 2024; Christiano et al., 2017: Bai et al., 2022a; Ouyang et al., 2022; Rafailov et al., 2023) with specific choice of reward function. However, the maximum likelihood sharpening objective (2) used for our theoretical results has been relatively unexplored within the alignment and self-improvement literature.
for
Theoretical understanding of self-training is currently limited. One line of work analyzes the convergence of self-training for classification and regression with the self-distillation objective, but is limited to stylized setups such as linear models (Mobahi et al., 2020; Frei et al., 2022; Das & Sanghavi, 2023; Das et al., 2024; Pareek et al., 2024), feedforward neural networks (Allen-Zhu & Li, 2020). and a general PAC-style framework (Boix-Adsera, 2024). To the best of our knowledge, our work is the first to study self-training in a general framework that subsumes language modeling. extensive discussion of related work.
See Appendix B for
2 SHARPENING ALGORITHMS FOR SELF-IMPROVEMENT EMENT
This section introduces the two families of seff-improvement algorithms for sharpening that we study, Going forward, we omit the dependence of rself on Thase when it is clear from context. We use the notation arg maxxem or arg min E to denote exact optimization over user-specified model class for theoretical results (Agarwal et al., 2019; Foster & Rakhlin, 2023); empirically, these operations can be implemented by training neural network to low loss.
2.1 SELF-IMPROVEMENT THROUGH SFT: SFT-Sharpening
SFT-Sharpening filters responses for which the self-reward (serr x)) is large, and applies standard supervised fine-tuning on the resulting dataset (Amini et al., 2024; Sessa et al., 2024; Gui et al., 2024; Pace et al., 2024). This can be viewed as amortizing inference- via the effective-but-costt best-of-NV sampling approach (Brown et al., 2024; Snell et al., 2024; Wu et al., 2024b). Concretely, suppose we have a collection of prompts Ti....,Ty. For each prompt, we sample N responses Vi, :..1:-...ii... MiNN Thase I.2), then compute the best-of-N response
sharpening
4

---

Published as a conference paper at ICLR 2025
yfth = arg ja (Vs. 24)), scoring via the model's self-reward function. We compute
the sharpened model via supervised fine-tuning on the best-of-N responses:
BoN
arg TEll
log π (v)
BoN
This is simple, flexible self-training scheme, and converges to sharpened model as n, N - oc.
2.2 SELF-IMPROVMMENT THROUGHI RLHF: RLHF-Sharpening
drawback of the SFT-Sharpening algorithm is that it may ignore useful information contained in the self-reward function (1 x). Fixing a regularization parameter 3 > 0 throughout, our second class of algorithms solve a KL-regularized reinforcement learning problem in the spirit of RLHF and other alignment methods (Christiano et al., 2017; Rafailov et al., 2023). Defining
E.
(x and DKL ( Tbase) Ex, [log
x(y(z) we choose (a0a)
î arg max |rser (y/ x)] 3D (T m
#ell
The exact optimizer T arg m E ( x)] DKL (- (aase)) for this objective has the form (V 2)) x Thase (y 2)) exp (3 see (y x)). which converges the solution to the sharpening objective in Eq. (1) as f O. Thus, Eq. (3) can be seen to encourage sharpening.
There are many choices for what RLHF/alignment algorithm one might use to solve (3). For our theoretical results, we implement Eq. (3) using an approach inspired by DPO and its reward-based variants (Rafailov et al., 2023; Gao et al., 2024). Given a dataset 'D = {(x, v'}} } of n examples sampled via x ~ μ and y, y ~ Tbase (y x), we consider the algorithm that solves
arg min well
Σ (s.V.)))
( log
T [y x))
B log
T(y x) Thase (y/
(rser((y) [x) (sarr [x)) l=))) (4)
Wouse (y x)
x)
In Section 4, we show that this approach achieves guarantees similar to SFT-Sharpening, while a more sophisticated DPO variant with online exploration (Xie et al., 2024) provides provable benefits.
A STATISTICAL FRAMEWORK FOR SHARPENING
This section introduces the thcoretical framework within which will analyze the SFT-Sharpening and RLHF-Sharpening algorithms. We first introduce the maximum-likelihow sharpening objective stylized self-reward function, then introduce our statistical framework for sharpening. We write Ögg) to denote f = O(g max polylog(g))) and S as shorthand for a O(b).
SHARPENING Our theoretical results foeus the
3.1 MAXIMUM-LIKELIERS
sharpening objective given by
Fyerr(y xx) := llog Tuase xx),
which we aim to maximize using conditional samples y ~ Tbase (- x) from the base model. This is simple and stylized self-reward function, but we will show that it enjoys rich theory. In particular, we can restate the problem of sharpening with this self-reward through the lens of amortization.
Can efficiently amortize maximum likelihood inference (optimization) for conditional distribution Toase (y z)) given access to a sampling oracle that can sample ~ T x)?
The tacit assumption in this framing is that the -ikiimmm-iikkehhood response constitutes a useful form of hidden knowledge. Maximum-likelliowe sharpening connects the study of self-improvement to large body of research in theoretical computer science demonstrating computational reductions between optimization (inference) and sampling (generation) (Kirkpatrick al., 1983; Lovász & Vem- pala, 2006; Singh & Vishnoi, 2014; Ma et al., 2019; Talwar, 2019). Our sharpening framework offers a new learning-theee -thhorect perspective by focusing on the problem amortizing this type of reduction.
We evaluate the quality of an approximately sharpened model as follows. Let
y (x) == arg max log Wease (y z);;
5

---

Published as a conference paper at ICLR 2025
interpret y (x) C y as set to accommodate non-unique maximizers, and will write y* (2) to indicate a unique maximizer when exists (i.e., when y (z) = (v"(x)))
Definition 3.1 (Sharpened model). We say that a model āt is (e, -h-aarpeed relative to Thase if P (y (x) x) 2 5] 2 1
That is, an (e, 80-8)))-- -hhappendd model places at least 1 - 6 mass on max responses on all but an e-fraction of prompts under μ.. For small ó and e, we are guaranteed that म is high-quality generator: sampling from the model will produce an arg-max response with high probability for most prompts.
Maximum-likee likelihood sharpening for autoregressive models. Though our most general results are agnostic to the structure of X, y. and Toase. our primary motivation is the autoregressive setting in which y/ '" for vocabulary space V and sequence length H, and where Tbase has the autoregressive structure Thase (H x) - I Thase, h (yh 91:h-1, x) for y y1.H V. We observe that when the response y (1/1... WH) E y yH is a sequence of tokens, the maximum-likelihood sharpening objective (2) sharpens toward the sequence-level arg-max response:
arg max log Tbaee 2z).
(5)
Although somewhat stylized, Eq. (5) is non-trivial (in general, computationally intractable; see Appendix E) solution concept. We view the sequence-level arg-max as form of hidden knowledge that cannot necessarily be uncovered through naive sampling or greedy decoding.
Role of 8 for autoregressive models. As can be verified through simple examples, beam-search and greedy tokenwise decoding do not return an exact (or even approximate) solution to (5) in general. There is one notable exception: If the model has already been sharpened to 8 < 1/2 and the arg-max sequence is unique, then greedy decoding will succeed.
Proposition 3.1 (Greedy decoding succeeds for sharpened policies). Let TI.H be an au- toregressive model defined over response space y yH For given prompi a E X, if y y²(x) (x)) is a singleton and (zy(x) x)) 1/2, then the greedy decoding strategy that se- lects ynh arg max Th (yh
".......hh--.. x) guarantees that ÿ (z). This result is tight, in the sense that there exist with π (yy (x) x) S f/r which greedy decoding fails to recover y (x).
This means that if we start from an un-sharpened model, simply sharpening 1/2 may suffice.
3.2 SAMPLE COMPLEXITY FRAMEWORK
Sharpening, as described in Definition 3.1, is a purely computational problem, which makes it difficult to evaluate the optimality of celf-improvement algorithms. To address this, we introduce novel statistical framework for sharpening, inspired by the oracle complexity in optimization (Nemirovski et al., 1983; Traub al., 1988; Raginsky & Rakhlin, 2011; 1; Agarwal al., 2012) and statistical query complexity in computational learning theory (Blum et al., 1994; Kearns, 1998; Feldman, 2012; 2017).
Definition 3.2 (Sample-and -edeluuuatee framework). In the sample-and-evaluate framework, the al- gorithm designer does not have explicit access to the base model waase- Instead, they access Thase only through sample-an and-evaluate queries: The learner is allowed to sample n prompts x ~ p. For each prompt x. they sample N responses y1, V2.
T-ase z)) and observe the likelihood Tyose x) for each such response. The efficiency, or sample complexity, of the algorithm is measured through the total number of andeell-nn-evaluate queries
n. N.
This framework can be seen to capture algorithms like SFT-Sharpening and RLHF- -LHF-Sharpening (implemented with DPO), which only access the base model base through i) sampling responses via y ~ Thase( (- | æ)) (generation), and ii) evaluating the likelihood Thase (y x)) (verification) for these responses. We view the sample complexity m for the computational complexity of relf-improvement (a clear parallel to oracle complexity for optimization algorithms), one which is amenable aim to show that, under appropriate assumptions, SFT- SFT-Sharpening and PLHF-Sharpenn can learn an 8) ( sharpened model with sample complexity (o -1,-1 (Cor'
N natural statistical abstraction
dnformation-thhorede lower bounds. 3 We will
where Corob is potentially problem-dependent constant.
*Coneeeelly, the sample complexity m n N is lower bound on the running time of any algorithm that operates in the sample-and-evaluat framework.

---

Published as a conference paper at ICLR 2025
3.3 FUNDAMENTAL LIMITS
Before diving into our analysis of SFT-Sharpening and RLHF-Sharpening in the sample-and- evaluate framework, let us take a brief detour give sense for how sample complexity guarantees for sharpening should scale. To this end, we will prove a lower bound or fundamental limit on the sample complexity of any algorithm in the cample-and-evaluse framework.
Intuitively, the performance of any sampling-base based sharpening algorithm should depend on well the base model base covers the arg-man arg-max response y (x:). To capture this, we use the coverage coefficient
Ccov
Enzy
(6)
Thase (y' (x) xx)
and, for a model g, we define y (x) = arg yay Tl x) and (TT = E (v))a)
Our main lower bound shows that for a worst-case choice of II, the coverage coefficient serves as lower bound on the sample complexity of any sharpening algorithm.
Theorem 3.1 (Lower bound for sharpening). Fix an integer d 2 1 and parameters e E 10,1) and C 2- 1. There exists class of models II such that (i) log [II] x d(1 + log(Ce (ii)
sup=en (T) X C, and (iii) y" (z) a singleton for all π E II. x E X. Any sharpening
algorithm āे that achieves E[ x-lpz=lll (y Thoe (x) x)) 1/2]] 2 1 for all Those E 11 must collect a total number of samples m = n at least
C log ITI
m Z
2 (1 + (C=2)))
This result shows that the complexity of any (e, 1/2 -harrpennn algorithm (for d >> 0) in the -anll--nndeevaluate framework must depend polynomially the coverage coefficient Ccovs well as the accuracy e. The lower bound also depends on the expressivity of Thase, as captured by the model class complexity term log IT] We will show in the sequel that it is possible match this lower bound, Note that this result also implies a lower bound for the general sharpening problem (i.c., general rs) since maximum-likelinn
sharpening is special case.
Remark 3.1 (Relaxed notions of sharpening and coverage). The notion of coverage in Eq. (6) is somewhat stringent, since it requires that Taase place large mass on y" (xx) on average. Appendix we introduce a more general and permissive notion of approximate sharpening (Definition F.1) which leads to weaker coverage requirements, and use this to give generalized versions of our main results.
We close this section by noting that numerous recent works computation-sheer that standard language models exhibit favorable coverage with respect to desir- able responses (Brown et al., 2024; Snell et al., 2024; Wu et al., 2024b). We replicate these findings in our experimental setup in Appendix A. These works suggest that, despite the exponentially large response space, the coverage coefficient Caov may be small in standard language modeling tasks.
on inference-time
4 ANALYSIS OF SHARPENING ALGORITHMS
Equipped with the sample complexity framework from Section 3, we now prove that the SFT-Sharpening ng and ShaFF-Sharpening families of algorithms provably learn sharpened model for the maximum likelihood sharpening objective. We treat the model class II as fixed, user-specified input. the tradition of statistical learning theory, our results allow for general classes II and are agnostic to its structure beyond standard generalization arguments.
4.1 ANALYSIS OF SFT-Sharpening
Recall that when we specialize to the maximum-likelihood sharpening self-reward, the SFT Sharppaann algorithm takes the form gooo arg max Σn log Tuase BoN | [.)), where
FON arg ma (log Toase (Wi.) | xx)] for y..,. WN,N Toase x.).
To analyze SFT-Sharpening we first make a realizability assumption. Let 7 BoN (x) be the distribution of the random variable BoN (x) ~ arg max max(log Thase (3/ x) "1,..., yN ~ Taase (x)}.
'This quantity can be interpreted as a special case of the L1 Li-connentrability coefficient (Farahmand et al., 2010; Xie & Jiang, 2020; Zanette et al., 2021; Amortila et al., 2024) studied in the theory of offline reinforcement learning.
7

---

Published as a conference paper at ICLR 2025
Assumption 4.1. The model class II satisfies "N II.
Our main sample complexity guarantee for SFT-Sharpening is as follows.
Theorem 4.1 (Sample complexity of SFT-Sharpeming) Let e, d, E (0,1) be given, and sup-
pose we set n. = c. [og( and N = c Con 1og for an appropriate constant e. > 0. Then with probability at least - p. SET-Sharpening produces a model āt such that that Pa (T (x) = 11-0 -] S e, and has total sample complexity
-
m O Ccov log (00((1Ip=]) log(d (
8c2
This result shows that SFT-Sharpening is minimax optimal in the sample-and-evaluat framework when 5 is constant. In particular, the bound in Eq. (7) matches the lower bound in Theorem 3.1 up to polynomial dependence on 5 and logarithmic factors. Whether the 1/5 factor in Eq. (7) can be removed is interesting technical question, but may not be practically consequential because-as as dis- cussed in Section 3.2 regime 6 < 1/2 is most meaningful for autoregressive language modeling.
Remark 4.1 (On realizability and coverage). Realizability assumptions such Assumption (which asserts that the class 11 is powerfil enough to model the distribution of the best-of-N responses) are standard in learning theory (Agarwal et al., 2019; Foster & Rakhlin, 2023), though certainly non-trivial (see Appendix E for natural example where they may not hold). The coverage assumption, while also standard, when combined with the hypothesis that high- gig-liiellhood responses are desirable. suggests that Thase generates high-quality responses with reasonable probability. In general, doing so muy require leveraging non-trivial serial computation at inference time via procedures such as Chain-of-Thouyye (Wei el al., 2022). Although recent work shows that such serial computation cannot be amortized (Li et al., 2024; Malach, 2023). SFT-Shar pening instead amortizes the parallel computation of best-of-N sampling, and thus has different representational considerations.
Benefits of adaptive sampling. SFT-Sharpening is optimal in the sample-and-evaluate framework, but we show in Appendix D that variant which selects the number of responses adaptively based on the prompt x can bypass this lower bound, improving the e-dependence in Eq. (7) from to ---
Empirical validation. In Appendix A, we empirically investigate the benefits of BoN on a variety of dodel-dataset pairs. Our results, summarized in Table and Figs. 7 and 8, broadly show that the aforementioned benefits of inference-ting time sharpening, to an extent, amortized training time.
4.2 ANALYSIS OF RLHF-Sharpening
We now turn our attention to theoretical guarantees for the RLHF-Sharpening algorithm family, which uses tools from reinforcement learning to optimize the self-reward function. When specialized to mexximum-likellhooe
takes the form क s arg max [En logg Toase (y []]] 3DKL (T Thase)} for 3 > O. The exact optimizer g = arg max [15 llgg Thase (y x)] 3D ( Taase) } for this objective has the form
sharpening, the RL objective used by RLHFFSharppene
( x) x
(y) xx), which converges to a sharpened model (per Definition 3.1) as 3 + 0. 1+3 base
The key challenge we encounter in this section is the mismatch between the RL reward log Tasse (y a:) and the sharpening desideratum म F(yy (x:) IT). For example, suppose a unique argmax-sap say, y (z)) socond-t--argmax---t say, y (xr) ((r)aare are nearly as likely under Thase- Then the RL reward Ea [lol (y =)] must be optimized extremely high precision before गे can be guaranteed to distinguish the two. To quantify this effect, we introduce a margin condition.
Assumption 4.2 (Margin). For margin parameler "imargin >> 0, the base model Thase satisfies
max Thase (y x)) 2 (1 + "margin)) Thase (1/' | x)) Vy & y (xx), Vo E supp(u). yEY
SFT-Sharpening does not suffer from the pathology in the example above, because once y (x) and a (x( are drawn in batch of N responses, we have yaaN "xx,) regardless of margin. However, as we shall show in Section 4.2.2, the -LHF-Shhrpening algorithm is amenable to online exploration, which may improve dependence other problem parameters.
We focus finite classes for simplicity, following convention in reinforcement learning theory (Agarwal al., 2019; Foster & Rakhlin, 2023), but our results extend infinite classes through standard arguments.
8

---

Published as a conference paper at ICLR 2025
4.2.1 GUARANTEES FOR RLHF-Sharpening WITH DIRECT PREFERENCE OPTIMIZATION
The first of our theoretical results for RLHF-Sharpening takes an offline reinforcement learning approach, whereby we implement Eq. (3) using reward-based variant of Direct Preference Opti- mization (DPO) (Rafailov et al., 2023; Gao et al., 2024). Let Dpref (xr, y, y')} dataset of n examples sampled via p. y' Tasee ().. For a parameter 3 >> O, we solve म arg min
x Tly' x) Tγy x) 3 log Tass x)
Σ
(1ogg
(log Thase x) log Tass (V/ | xx)
(8)
Toaso (y' x))
(2-0--0 Dpper
Assumptions. Per Rafailov et al. (2023), the solution to Eq. (8) coincides with that of Eq. (2) asymptotically. To provide finite-sample guarantees, we make a number of statistical assumptions. First, we make a natural realizability assumption (e.g.. Zhu et al. (2023); Xie et al. (2024)).
Assumption 4.3 (Realizability). The model class IT satisfies 3 IT.
Next, we define two concentrability coefficients for a model n.
π (y
x²) x3)
π x) T' x))
97
C =
F
and Ca/r1 == En
(9)
Taase
The following result shows that both coefficients are bounded for the KL-regularized model Tे.- Lemma 4.1. The model n3 satisfies Crz I Ceov and Crmon/f S 1
Motivated by this result, we assume the coefficients in Eq. (9) are bounded for all π E IT. Assumption 4.4 (Concentrabilltyy) All II satisfy C, S Ceane parameter Crone 2 Ceov. and Crene/TiB S Closs for a parameter Closs 2 |3/]
By Lemma 4.1, this assumption is consistent with Assumption 4.3 for reasonable bounds on Ceone and Classi note that our sample complexity bounds will only incur logarithmic dependence on Closs-
Main result. Our sample complexity guarantee for RLHF- Sharpening (via Eq. (8)) as follows.
Theorem 4.2. Let e, 5, E (0, 1) be given. Set 3 S Óearginoe, and suppose that Assumptions 4.2 4.4 hold with parameters Cconer Closs: and Tmargin O. For an appropriate choice for n, the DPO
algorithm (Eq. (8)) ensures that with probability at least 1 - Pawy ( (yy (x) 2) S 8) S c, and has sample complexity
= (CCone (Cioss IT|
Imargin 526²
Compared to the guarantee for SFT-Sharpening, RLHF-Sharpening learns sharpened model with the same dependence on the accuracy c, but a worse dependence on 5; as we primarily consider 8 constant (cf. Proposition 3.1), we view this as relatively unimportant. We further remark that RLHF-Sharpening uses N = 2 responses per prompt, while SFT-Sharpening uses many (N Ccow/e) responses but fewer prompts. Other differences include:
SSHF-Sharpening requires the margin condition in Assumption 4.2, and has sample complexity scaling with ?margin We believe this dependence natural for algorithms based on reinforcement learning, as relates suboptimality with respect to the reward function (seir(y) (r) = log Toase (y
I)) (i.e., En mmxxyey log Tbase (y x)) Ex- [log Tbase (y x)]] S e, the objective minimized by reinforcement learning) approximate sharpening error P Parayl i (Ty (x) x)) < 1 8). However, it is not clear if the precise dependence we pay is necessary.
LLHF-Sharpennin requires a bound on the uniform coverage parameter Ceonc, which is generally larger than the parameter Ccev required by SFT-Sharpening We expect that this assumption can be removed by incorporating pessimism (Liu al., 2024; Huang al., 2024). Also, RLHF LLHF-Sharpeniig requires a bound on the parameter Closs. which grants control over the (otherwise unbounded) range of the reward function log Tbase (y zz). Since the dependence on Class is only logarithmic,, we view this as fairly mild. Overall, the guarantee in Theorem 4.2 may be somewhat pessimistic; it would be interesting the result can be improved to match the sample complexity of SFT-Sharpening.
"See Remark 4.1 for discussion of this assumption.

---

Published as a conference paper at ICLR 2025
4.2.2 BENEFITS OF EXPLORATION
The guarantee in Theorem 4.2 scales with the coverage parameter Ccov = - Toae ( (I)] which in general is unavoidable in the sample-and-evaluate framework via our lower bound, The- orem 3.1. Although Ceov is a woblem--dependee as [3]] (which is exponential in sequence length for autoregressive models). Fortunately, unlike SFT-Sharpening, the SLHF--hhapenning objective (3) is amenable to RL algorithms employing active exploration, leading to improved sample complexity when the class IT has additional structure.
parameter, in the worst case can be as large
Our below guarantees for RLHF RLHF-Sharpening replace the assumption of bounded coverage with boundedness of a structural parameter for the model class known as the "sequential extrapolation coefficient" (SEC) (Xie et al., 2023; 2024), which denote by SEC(IT). The formal definition is deferred to Appendix J.2. Conceptually, SEC(IT) may thought of as a generalization of the eluder dimension (Russo & Van Roy. 2013; Jin et al., 2021). It can always be bounded by the coverability coefficient of the model class (Xie et al., 2024) and can be as large as Ceone in the worst case, so that bounds based on the SEC reflect improvements that are possible in favorable instances.
Beyond boundedness of the SEC, require bound the range of the pog-prbbabilities of Taase.
Assumption 4.5 (Bounded log probabiliiiies) For all π E 11, (z,y) X y log TTaee (p)o)) S Rmaa-
We expect that the dependence on Rmax in our result can be replaced with log(C1oss) (Assump- tion 4.4), but we omit this extension to simplify presentation.
We appeal to (a slight modification of) XPO, iterative language model alignment algorithm due to Xie et al. (2024). XPO is based on the objective in Eq. (8), but unlike DPO, incorporates a bonus term encourage exploration leverage online interaction. See Appendix J.2 for detailed overview.
Theorem 4.3 (Informal version of Theorem J.2). Suppose that Assumptions 4.2 and 4.5 hold with parameters "imargin Rmax > O, and that Assumption 4.3 holds with 3 = Tmarriin (2 (og(21)))/8) For any m E N and p (0, 1). XPO (Algorithm 1), when configured appropriately, produces an (e, 8) -'sharpedd model ßे E II with probability at least 1 - P. and uses sample complexity"
m = SEC(IT)) log( log(1()))
2 imargin 6222
The takeaway from Theorem 4.3 3 is that there is no dependence on the coverage coefficient for Thase- Instead, the rate depends the complexity of exploration, governed by the sequential extrapolation coefficient SEC( We expect similar guarantees can derived for other active exploration algorithms and complexity measures (Jiang et al., 2017; Foster al., 2021; Jin et al., 2021: Xie al., 2023).
5 CONCLUSION
We view theoretical framework for sharpening starting point toward foundational under- standing of self self-improvemmnt that can guide the design and evaluation of algorithms. To this end, we raise several directions for future research.
Representation learning. A conceptually appealing feature of our framework is that it is agnostic to the structure of the model under consideration, but an important direction for future work is to study the dynamics of self-in ielf-improvement for specific models/arcciitecturs and understand the representations that these models learn under self-training.
Richer forms of self-reward. Our theoretical results study the dynamics of self-training in a stylized framework where the model uses its own log- probabilities self- infrommppoeeettt leverages more sophisticated approaches (c.g.. specific prompting techniques) (Huang al., 2022; Wang et al., 2022; Bai et al., 2022b; Pang al., 2023; Yuan et al., 2024) and it is important to understand when and how these forms of self-improvement are beneficial.
self-reward Empirical research on
Teecnicallly, Algorithm operates a slight generalization of the sample-and-evaluee framework (Defini- tion 3.2). where the algorithm is allowed to query Muase (y 22) for arbitrary We expect that our lower bound (Theorem 3.1) can be extended to this more general framework, in which case Algorithm is fundamentally using additional structure of IT (via the SEC) avoid dependence on Ceoe-
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Sivaraman Balakrishnan, Miro Dudík, Susan Dumais, John Langford, Qinghua Liu, and Yuda Song for helpful discussions.
REFERENCES
Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, al. Phi-3 technical report: A highly capable language model locally on your phone. arXiv:2404.14219 2024.
Samira Abnar, Mostafa Dehghani, and Willem Zuidema. Transferring inductive biases through knowledge distillation. arXiv:2006.0055: 00555, 2020.
Alekh Agarwal, Peter Bartlett, Pradeep Ravikumar, and Martin Wainwright. Information-theorer lower bounds the oracle complexity of stochastic convex optimization. IEEE Transactions Information Theory, 2012.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, 2014.
Alekh Agarwal, Nan Jiang. Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. https://rlthhory////
gi chub.ioo/ 2019. Version: January 31, 2022.
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv:2012.09886, 2020.
Afra Amini, Tim Vieira, and Ryan Cotterell. Variational best-of-n alignment. arXiv:2407.06057 2024.
Philip Amortila, Dylan Foster, and Akshay Krishnamurthy. Scalable online exploration via coverability. In Forty-first International Conference on Machine Learning. 2024.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, 7ac Hatfield-Dedds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom Brown, Jack Clark, Sam McCandlish, Chris Olah, Ben Mann, and Jared Kaplan. Training a helpful and harmless assistant with reinforcement learning from human feedback. 20X4::2004.05862.. 2022a.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, al. Constitutional ai: Harmlessness from ai feedback. 2rXiv:2212.08073, 2022b.
Francisco Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 1982.
Matthew James Beal. Variational algorithmms for approximate Bayesian inference. University of London, University College London, 2003.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 2021.
Yoav Benjamini and Yosef Hochberg. Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society: Series B, 1995.
Adam Block, Dylan J Foster, Akshay Krishnamurthy, Max Simchowitz, and Cyril Zhang. Butterfly ef- fects of SGD noise: Error amplification behavior cloning and autoregression. arXiv:2310.11420 2023.
11

---

Published as a conference paper at ICLR 2025
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Symposium Theory of Computing, 1994.
Enric Boix-A Towards a theory of model distillation. arXiv preprint arXiv:2403.00003 2024.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv:2407.21787, 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mize Model compression. SIGKDD International Conference Knowledge Discovery and Data Mining, 2006.
Zixiang Chen, Yihe Deng, Huizhuo Yuan, Kaixuan Ji, and Quanquan Gu. Self-play fine-tuning converts weak language models to strong language models. arXiv:2401.01335, 2024.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems, 2017.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers solve math word problems. arXiv:2 10. 14168, 2021.
Stephen A Cook. The complexity of theorem-proving procedures. In Symposium Theory of Computing, 1971.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Rudrajit Das and Sujay Sanghavi. Understanding self-distillation in the presence of label noise. In International Conference on Machine Learning, 2023.
Rudrajit Das, Inderjit S Dhillon, Alessandro Epasto, Adel Javanmard, Jieming Mao, Vahab Mirrokni, Sujay Sanghavi, and Peilin Zhong. Retraining with predicted hard labels provably increases model accuracy. arXiv:2406. /226, 2024.
Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. veXiv:1810.04500 2018.
Bin Dong, Jikai Hou, Yiping Lu, and Zhihua Zhang. Distillation early stopping? Harvesting dark knowledge utilizing anisotropic information retrieval for overparameterizee neural network. 1rX1v:191. 2019.
Abhimanyu Dubey, Abhinay Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv:2407.21788. 2024.
Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. A spectral condition for spectral gap: Fast mixing in high-temperature Ising models. Probability Theory and Related Fields, 2022.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. Advances in Neural Information Processing Systems, 2010.
Vitaly Feldman. A complete characterization of statistical query learning with applications to evolvability. Journal of Computer and System Sciences, 2012.
12

---

Published as a conference paper at ICLR 2025
Vitaly Feldman. A general characterization of the statistical query complexity. In Conference Learning Theory, 2017.
Dylan Foster and Alexander Rakhlin. Foundations of reinforcement learning and interactive decision making. arXiv:2312.16734 16730, 2023.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. 1rXiv:2112.13487, 2021.
Spencer Frei, Difan Zou, Zixiang Chen, and Quanquan Gu. Self-training converts weak learners to strong learners in mixture models. In International Conference on Artificial Intelligence and Statistics, 2022.
Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. Born again neural networks. International Conference on Machine Learning. 2018.
Zhaolin Gao, Jonathan D Chang, Wenhao Zhan, Owen Oertell, Gokul Swamy, Kianté Brantley, Thorsten Joachims, J Andrew Bagnell, Jason D Lec, and Wen Sun. REBEL: Reinforcement learning via regressing relative rewards. 44X11:240.116677 2024.
Samuel Gershman and Noah Goodman. Amortized inference in probabilistic reasoning. In Annual Meeting of the Cognitive Science Society, 2014.
Google. Palm 2 technical report. arXiv:2305. 10403, 2023.
Akhilesh Gotmare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. A closer look deep learning heuristics: Learning rate restarts, warmup and distillation. International Conference on Learning Representations, 2019.
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. Advances in Neural Information Processing Systems, 2004.
Lin Gui, Cristina Gårbacea, and Victor Veitch. BoNBoN alignment for large language models and the sweetness best-of-n sampling. arXiv:2406.0088 00832, 2024.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. urXiv:2009.03340 2020.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv:2103.03874, 2021.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. 1rXiv:1503.02531, 2015.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv:2106.0966 2021.
Edward Hu, Moksh Jain, Eric Elmoznino, Younesse Kaddar, Guillaume Lajoie, Yoshua Bengio, and Nikolay Malkin. Amortizing intractable inference in large language models. 03.0:22310.04363, 2023.
Audrey Huang. Wenhao Zhan, Tengyang Xie, Jason Lee, Wen Sun, Akshay Krishnamurthy, and Dylan Foster. Correcting the mythos of KL-regularization: Direct alignment without overparameterization via Chi-squared Preference Optimization. arXiv:2407.1 13399, 2024.
Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang. Hongkun Yu, and Jiawei Han. Large language models can self-improve. arXiv:2210.11610, 2022.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv:23/0006822 2023.
13

---

Published as a conference paper at ICLR 2025
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low Bellman rank are PAC-leamable. In International Conference on Machine Learning, 2017.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman Eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 2021.
Richard M Karp. Reducibility among combinatorial problems. Springer, 1972.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 1998.
Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing. Science, 1983.
Leonid Anatolevich Levin. Universal sequential search problems. Problemy peredachi informatsit, 1973.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. axXiv:2402.12875 2024.
Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang. Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization in RLHF: Your SFT loss is implicitly an adversarial regularizer. arXiv:2405. 2024.
László Lovász and Santosh Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. Symposium on Foundations of Computer Science, 2006.
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I Jordan. Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 2019.
Eran Malach. Auto-regressive next-token predictors are universal learners. arXiv:2309.00999, 2023.
Clara Meister, Tim Vieira, and Ryan Cotterell. If beam search is the answer, what the question? arXiv:2010.026500 2020.
Hossein Mobahi, Mehrdad Farajtabar, and Peter Bartlett. Self-distillation amplifies regularization in hilbert space. Advances in Neural Information Processing Systems, 2020.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang. Yanping Huang, Zhifeng Chen, Heng-Tze Tze Cheng, Michael Collins, Trevor Strohman, et al. Controlled decoding from language models. arXiv:2310.17022, 2023.
Arkadii Nemirovski, David Borisovich Yudin, and Edgar Ronald Dawson. Problem complexity and method efficiency in optimization. Wiley, 1983.
OpenAl. GPT-4 technical report. arXiv:2303.08774, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 2022.
Alizée Pace, Jonathan Mallinson, Eric Malmi, Sebastian Krause, and Aliaksei Severyn. West-of-n: Synthetic preference generation for improved reward modeling. arXiv:2401.12085 2024.
Jing-Cheng Pang, Pengyuan Wang, Kaiyuan Li, Xiong-Hui Chen, Jiacheng Xu, Zongzhang Zhang, and Yang Yu. Language model seff-improvement by reinforcement learning contemplation. arXiv:2305.14443. 2023.
Divyansh Pareck, Simon Du, and Sewoong Oh. Understanding the gains from repeated self- distillation. arXiv:2407.04660 2024.
14

---

Published as a conference paper at ICLR 2025
Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V Le. Meta pseudo labels. In Conference Computer Vision and Pattern Recognition, 2021.
Ori Press, Ravid Shwartz-Ziv, Yann LeCun, and Matthias Bethge. The entropy enigma: Success and failure of entropy minimization. arXiv:2405.0555 05012, 2024.
Yuxiao Qu, Tianjun Zhang, Naman Garg, and Aviral Kumar. Recursive introspection: Teaching language model agents how to self-improve. arXiv:2407.18219 2024.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 2023.
Maxim Raginsky and Alexander Rakhlin. Information- complexity, feedback and dynamics in convex programming. IEEE Transactions on Information Theory, 2011.
Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S Rawat, and Mubarak Shah. In defense of pseudo- labeling: An uncertaint--aware pseudo-label selection framework for semi-supervised learning. arXiv:2101.06329, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 2013.
Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of mhain-of-thoughy In International Conference on Learning Representations, 2023.
Igal Sason and Sergio Verdú, f-divergence inequalities. IEEE Transactions on Information Theory, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv:1707.06347 2017.
Pier Giuseppe Sessa, Robert Dadashi, Léonard Hussenot, Johan Ferret, Nino Vieillard, Alexandre Ramé, Bobak Shariari, Sarah Perrin, Abe Friesen, Geoffrey Cideron, et al. Bond: Aligning LLMs with Best-of-N distillation. arXiv:2407. 14622, 2024.
Max Simchowitz, Kevin Jamieson, and Benjamin Recht. The simulator: Understanding adaptive sampling in the moderate-confideecc regime. In Conference Learning Theory, 2017.
Mohit Singh and Nisheeth K Vishnoi. Entropy, optimization and counting. In Symposium on Theory of Computing, 2014.
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. arXiv:2408.03314 2024.
Yuda Song, Gokul Swamy, Aarti Singh, Andrew Bagnell, and Wen Sun. Understanding preference fine-tuning through the lens of coverage. arXiv:2406.0144 01462, 2024.
Kevin Swersky, Yulia Rubanova, David Dohan, and Kevin Murphy. Amortized bayesian optimization over discrete spaces. In Conference on Uncertainty in Artificial Intelligence, 2020.
Kunal Talwar. Computational separations between sampling and optimization. Advances in Neural Information Processing Systems, 32, 2019.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cris- tian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian. Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen
15

---

Published as a conference paper at ICLR 2025
Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. arXiv:2307.09288, 2023.
Joseph Traub, Grzegorz W Wasilkowski, and Henryk Wožniakowski. Information-bused complexity Academic Press Professional, Inc., 1988.
A. van de Geer. Empirical Processes M-Estimation. Cambridge University Press, 2000.
Ziyu Wan, Xidong Feng, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. International Conference on Machine Learning, 2024.
Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. arXiv:2006. 10726, 2020.
Tianlu Wang, Ilia Kulikov, Olga Golovneva, Ping Yu, Weizhe Yuan, Jane Dwivedi- Yu, Richard Yuanzhe Pang, Maryam Fazel-Zarandi, Jason Weston, and Xian Li. Self-taught evaluators. arXiv:2408. 02666, 2024.
Xuezhi Wang and Denny Zhou. Chain-of- Chain-of-thought reasoning without prompting. arXiv:2402.10200, 2024.
Yizhong Wang, Yeganch Kordi, Swaroop Mishra, Alisa Liu, Noah A Smith, Daniel Khashabi, and Hannaneh Hajishirzi. Self-instruct: Aligning language models with self-generated instructions. arXiv:2212.10566 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models, Advances in Neural Information Processing Systems, 2022.
Wing Hung Wong and Xiaotong Shen. Probability inequalities for likelihood ratios and convergence rates of sieve mles. The Annals of Statistics, 1995.
Tianhao Wu, Weizhe Yuan, Olga Golovneva, Jing Xu, Yuandong Tian, Jiantao Jiao, Jason Weston, and Sainbayar Sukhbaatar. Meta-rewarding language models: Self-improving alignment with manet-----et--judeee arXiv:2407.19594 2024a.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analysis of compute-optimal inference for problem-solving with language models. arXiv:2408.0077 2024b.
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv:2405.00675, 2024c.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty Artificial Intelligence, 2020.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in
online reinforcement learning. In International Conference on Learning Representations, 2023.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and
Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit Q appaproxinatooon for sample-efficient RLHF. arXiv:2405.21044 2024.
Wei Xiong, Hanze Dong, Chenlu Ye, Han Zhong, Nan Jiang, and Tong Zhang. Gibbs sampling from human feedback: A provable Kl--constrained framework for RLHF. arXiv: 1456, 2023.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 2024.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of Nash leamning from human feedback under general KL-regularized preference. arXiv:2402.073/ 14, 2024.
16

---

Published as a conference paper at ICLR 2025
Weizhe Yuan, Richard Yuanzhe Pang, Kyunghyun Cho, Sainbayar Sukhbaatar, Jing Xu, and Jason Weston. Self-rewarding language models. arXiv:2401.10020, 2024.
Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in Neural Information Processing Systems, 2021.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 2022.
Tong Zhang. From e-entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 2006.
Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse. Probabilistic inference in language models via twisted sequential monte carlo. International Conference Machine Learning, 2024.
Lianmin Zheng, Wei-Lin Chiang. Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging LLM-as-a-judge with MT-bench and chatbot arena. Advances in Neural Information Processing Systems, 2024.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning 2023.
17

---

Published as a conference paper at ICLR 2025
CONTENTS OF APPENDIX
I Additional Discussion and Results
19
Additional Experiments and Details
19
A.1
Inference-time validation experiments
19
A.2 Experiments with other self reward functions
23
A.3 Effect of SFT-Sharpening
25
B Detailed Discussion of Related Work
26
Guarantees for Inference-Time Sharpening
29
Guarantees for SFT-Sharpening with Adaptive Sampling
30
Computational and Representational Challenges in Sharpening
31
E.1 Computational Challenges
32
E.2
Representational Challenges
32
II Proofs
34
F
Preliminaries
34
F.I Guarantees for Approximate Maximizers
34
F22
Technical Tools
34
G Proofs from Section 3.1
36
Proofs from Section 3.3
36
I Proofs from Section 4.1 and Appendix D
39
J Proofs from Section 4.2
42
J.1 Proof of Theorem 4.2
42
J.2 Proof of Theorem 4.3 and Theorem J.3
47
18

---

Published as a conference paper at ICLR 2025
Part I
Additional Discussion and Results
A ADDITIONAL EXPERIMENTS AND DETAILS
In this section detail the precise setup required replicate empirical results. All of our experi- ments were run either on 40G NVIDIA A100 GPUs, 192G AMD MI300X GPUs, or through the Ope- nAl API. We considered the following models. All models, except for gpt-3. tettuuurissttutt are available on https: htpps://huuginge.e
co and we provide HuggingFace model identifiers below.
1. Phi models: We experiment with several models from the Phi family of models (Abdin et al., 2024), specifically Phi3-Mini
Phi3-Small ("microsoft/Phi- D-small-Sk-instruutt), Phi3-Medium "mmicnnoti/hhii---eeiii--------- ("microsat//hhh333-mmiin--imm
and Phi3. Phi3.5-Mini 5-Mini
2. Llama3. 2- (amear/nsstuuttmmtallliaa ("mett-laamm/LLame I--strtttstttt") (Dubey al., 2024)
3. Mistral-7B--Instruct--0 3 ("mistralai/Miittall-B--B (Bntsiuttttnstttu (Jiang al., 2023)
4. 30t-3.5-turboo-nnstrucc (Brown et al., 2020): We access this model via the OpenAl API.
5. 11ama2-7b-gamed -00-gam------c--hh ('OMCheeryFie//lamm--haamaae (aame24-policy-h")) We use the model of Wan et (2024), which is a Llama-2 model finetuned on the GameOf24 task (Yao et al., 2024). We use this model only the GameOf24 task.
We consider the following tasks:
1. MATH: We use the above models to generate responses to prompts from the MATH (Hendrycks et al., 2021), which consists of more difficult math questions. We consider "all" subsets and take the first 256 examples of the test set where the solution matches the regular expression (Ad+).*
2. GSM8K: We use the above models to generate responses to prompts from the GSM-Sk dataset (Cobbe et al., 2021) where the goal to generate correct answer an elementary school math question. We take the first 256 examples from the test set in the main subset."
3. ProntoQA: We use the above models to generate responses to prompts from the ProntoQA dataset (Saparov & He, 2023), which consists of chain-of-thought--e reasoning questions with boolean answers. We take the first 256 examples from the training set."
4. MMLU: We use the above models to generate responses to prompts from three subsets of the MMLU dataset (Hendrycks et al., 2020), specifically and college_cheml stry (Chem) all of which consist of multiple choice questions!! We take the first 256 examples of the test set.
coloe, _eeepphssccssssseee (Phys),
Game0f24: We use only the model of Wan al. (2024) (i.e., 1ammaa2---gam22-ppollo on the GameOf24 task (Yao et al., 2024). The prompts are four numbers and the goal is to combine the numbers with standard arithmetic operations to reach the number '24.' Here we use both the train and test splits of the dataset.
A.1 INFERENCE-TIMGE VALIDATION EXPERIMENTS
To form the plots in Figure and in Figures 3 and 4, for each (model, task) pair, we sampled N generations per prompt with temperature and returned the best of the N generations according the maximum-likell -ikeuun-ikkelhoodd sharpening self-reward function rseif (y x)) = log Maase (y xx); we compare against greedy decoding baseline, whose accuracy is displayed in Figure 2(d).
"nttps://hugginggaace http:///nnaaaccoctttttttss/////s co//atassts/llhhtevva//Mtttt
httpp/////gggnnn/eeeeoo////////s co/dattasets/oppeaa//ggmeee.
11 http:////.ggnngee.....eeeeet//te
19

---

Published as a conference paper at ICLR 2025
BoN-Norm: % Lift over Greedy
Majority: % Lift over Greedy
Ph13 (Min))
4.4
-0.4
7.0
-1.2
7.2
5.2
Phi3 (Mini)
19.7
5.1
0.3
7.1
12.5
8.7
Ph13.5 (Min))
0.8
5.0
1.5
6.0
4.9
0.7
Ph13.5 (Mini)
19.4
12
11.1
6.9
1.5
Phi3 (Small)
2.1
7.3
-4.6
3.3
2.4
-11.8
Phi3 (Small)
17.1
11.4
-14.4
2.5
7.9
-9.4
Phil (Medium)
0.1
-1.7
0.5
0.2
6.5
-1.3
Phi3 (Medium)
16.0
6.1
5.0
3.6
13.2
1.3
Mistral-7B
28.6
17.1
2.8
7.6
25.9
4.0
Mistral-78
72.2
48.8
38.5
19.8
19.5
10.5
Llama3.22
4.3
3.6
-12.7
79.3
20.3
Llama3.22 2--38
17.5
59.7
GPT-3.5
3.4
1.2
-5.9
-1.8
7.1
-7.9
GPT-3.5
35.5
18.2
4.6
7.0
11.0
7.4
MATH GSMBK
ProntoQA Blo
Pbys
Chem
MATH
GSM8K
ProntoQA Bia
Pbas
Chae
(a)
(b)
Pass @50: Accuracy (%)
Greedy: Accuracy (%)
Phi3 (Mini)
96.6
97.3
98.8
99.2
99.9
98.1
Phi3 (Mini)
66.0
87.1
50.4
80.6
65.7
52.0
Phi3.5 (Mini)
97.0
96.8
90.9
97.3
98.8
96.7
Ph:3.5 (Min))
67.6
84.4
50.8
77.1
68.6
55.0
Phi3 (Smal))
97.9
97.3
90.3
98.8
97.2
96.3
Phi3 (Small)
72.3
79.3
59.4
85.4
74.5
66.0
Phil (Mediu))
98.4
98.3
83.3
99.0
99.0
94.7
Phi3 (Medrum)
73.4
86.7
47.3
88.2
70.6
60.0
Mistral-7B
81.9
94.0
99.7
98.8
98.2
98.0
Mistral-78
23.0
46.9
50.0
61.8
36.3
42.0
Llama3.2.3p 2-33
93.8
95.8
100.0
99.6
99.8
99.2
Llama3.2-38
58.2
76.6
47.7
61.8
14.7
30.0
GPT-3.5
96.0
96.6
95.1
98.5
99.9
99.4
GPT-3.5
55.9
70.3
49.6
68.8
51.0
53.0
MNTH CSMBK
PrantoOA Bio
ylys
Chema
MATH GSM8K
ProntoDA
Bia
pbys
Cham
(c)
(d)
Figure 2: Performance of alternative decoding schemes beyond BoN. Percent accuracy improvement over greedy decoding for self eeff-improvement with length-normalized log probability (a) and majority voting (b), with both demonstrating efficacy on a range of model-task pairs. (c) Measure of coverage of correct answer, demonstrating that most model-task pairs produce the correct answer most of the time with at least one completion out of 50. (d) Accuracy of greedy decoding baseline on each model-task pair.
Implementation details. For all models and datasets except for GameOf24, we used 1-shot prompt- ing ensure that models conform to the desired output format and to elicit chain of thought reasoning (for GameOf24 24 we do not provide demonstration in the prompt). We set the maximum length of decoding be 512 tokens. We used 10 seeds for all (model, task) pairs with a maximum value of N = 50 in ofst-of-N sampling. We simulated N responses for N < 50 by subsamping the 50 generated samples. For Best-of-N sampling, we always use temperature 1.0. Since greedy decoding is deterministic strategy, we only use seed for each (model, task) pair. In all experiments, we collect both the responses and their log-likelihnne likelihoodss under the reference model (i.e., the original model from which samples were generated).
Results. Results for most datasets are presented in Figures and 4. Because we only consider a single model for GameOf24, we separate this task into Figure 5 For all datasets, we visualize both performance- meeasureddeeeeeeeeeeeeeeeee as normalized improvement in accuracy over greedy decoding and log- lieliiieiihodss--- under base of the selected responses.
In all cases, Best-of-N sampling (using (seir(y) x) log Tbase (y | x:)) improves over the naïve sampling strategy, wherein we simply sample a single generation with temperature 1.0. In all datasets, we also see improvements over the standard greedy decoding strategy, at least for some models. Analogously, for every model, there is at least one dataset for which Best-of-N sampling improves over greedy decoding.
We further explore the relationship between sequence level log probabilities and generation quality in Figure 6, where we plot the empirical distributions of responses sampled with temperature from
20

---

Published as a conference paper at ICLR 2025
MATH
GSM8K
120
110
Lift over Greedy
Lift over Greedy
(Mini)
80
100
Phi3.5 (Mini)
60
Phi3 (Small)
95
Phi3 (Modium)
Mistral-7B
Llama3.2-33 3.B3BB
20
85
GPT-3.5
80
10
20
30
40
50
10
20
30
40
50
N
(b)
ProntoQA
Bio
Log Probability over Greedy
115
% Lift over Greedy
0
110
-50
Ph13 (Mini)
-100
Phi3.5 (Mini)
100
-150
Phi3 (Small)
Ph13 (Medium)
93
-200
Mistral-7B
90
-250
Llama3.2-38
GPT-3.5
85
-300
10
20
30
50
10
20
30
40
50
N
(c)
(d)
Phys
Chem
250
125
225
Lift over Greedy
% Lift over Greedy
115
200
110
105
150
100
125
90
85
75
80
10
30
50
10
20
30
40
N
N
(e)
(f)
Figure 3: Percent lift in accuracy of inference- time BoN-sharpening over greedy decoding in each task N is varied. For many task-model pairs, the accuracy improves N increases, demonstrating the efficacy of maximum likelihood sharpening.
21

---

Published as a conference paper at ICLR 2025
MATH
GSM8K
Log Probabilit over Greedy
Log Probability over Greedy
0
-25
-25
-50
Ph13 (Mini)
Ph13 (Mini)
-50-
-75
Ph13.5 (Mini)
Ph13.5 (Mini)
Phi3 (Small)
-75
Phi3 (Small)
-100
Phi3 (Medium)
-100
(Medium)
125
Mistral-7B
-125
Mistral-7B
Llama3.2-38
Alama3.2-3p
GPT-3.5
-150
GPT-3.5
-175
-175
10
20
50
10
20
30
N
(a)
(h)
ProntoQA
40
50-
Log Probability over Greedy
Log Probablity over Greedy
20
Phi3 (Mini)
Ph13 (Mini)
40
-100
Ph13.5 (Mini)
Ph13.5 (Minl)
60
Phi3 (Small)
150
Phi3 (Small)
Phi3 (Medium)
Phi3 (Medium)
Mistral-7B
200
Mistral-7B
Llama3.2-38
Llama3.2-3B
120
GPT-3.5
GPT-3.5
140
-300
10
20
10
20
30
N
(d)
Phys
Chem
Log Probability over Greedy
Log Probability over Greedy
-50
-100
Phi3 (Mini)
Phi3 (Mini)
-100
Phi3.5 (Mini)
-200
Phi3.5 (Mini)
Ph13 (Small)
Ph13 (Small)
Phi3 (Medium)
-300
Phi3 (Medium)
-200
Mistral-7B
Mistral-7B
-50
Llame3.2-38
-400
Llama3.2-3B
GPT-3.5
GPT-3.5
-300
-500
10
20
30
40
50
10
20
30
40
50
(e)
Figure 4: Effect of N on average sequence level log- probabbibilises for inference-time BoN-sharpening on various model-task pairs, compared greedy decoding baseline. As predicted by theory, the likelihood of sequences sampled with BoN-sharpening increases with N.
22

---

Published as a conference paper at ICLR 2025
the base model for variety of model- pairs, conditioned whether not the response is correct. It is clear from the figures that the distribution of log probabilities conditioned on correctness stochastically dominates that conditioned incorrectness in each case, which provides yet more evidence that log likelihoods represent reasonable sel-improvement target.
We mention several other observations from the experiments. First, in most cases, performance and log-likelihood saturate relatively small values of N, typically around 10 20. This suggests that significant improvements can be obtained with relatively low computational overhead. Second, in some cases, performance can degrade N increases. We found that this happens for two reasons: (1) the performance of the reference model is quite low and so Tself provides poor signal (e.g.. with Llama3. 2-33-Instructt and (2) the Best-of-N criteria selects for short responses, which have higher log- seglikklihood but cannot leverage the compuutational/eppreenttiii thought, and thus yield worse performance (e.g., with gpt-3. i-turbo-instruct on GSM8k).
benefits of chain-of-
Game24: % Lift over Greedy
Game24: Lift over Greedy
140
Llama (SFT)
Log Probability over Greedy
130
0.0
% Lift over Greedy
120
-0.5
110
-1.5
90
-2.0
80
-2.5
70
-3.0
10
20
30
50
30
N
N
Figure
Effect
inference-time BoN-sharpening on GameOf24 with the finetuned from Wan et al. (2024).
A.2 EXPERIMENTS WITH OTHER SELF REWARD FUNCTIONS
Although focus (y æ) log Taase z) throughout the paper, the sharpening frame- work is significantly more general. As such, we also ran experiments with other choices for Tseff- specifically:
1. normalied log- lig-likelihood: Tyeir(y log Tbase (y x=)/ul where lyl is the length, in tokens, of the response.
Majority (self-consistency)::: All datasets except GameOf24 have multiple-choice, boolean, or numerical answers. Although allow responses contain chain-of-thought tokens, we answer. This can
extract the answer from each response and use the most- seatf--ruunnll-occeeee be seen sample-based approximation to the following self-reward function: rseir (y x) Ey'wh..==a
Toase (1/ z), where yans are the "answer" tokens in the full response
Finally, as a skyline we consider the coverage criterion (Brown et al., 2024), where we simply check if any of the sampled responses corresponds to the correct answer. This criterion is skyline and does not fit into the self-imprrvement framework due to the fact that it uses knowledge of the ground truth (external) task reward function.
Results are displayed in Figure 2. For length-normalized log-likelihood and majority, we see qualitatively similar behavior to (unnormalized) log-likelihood in the sense that inference-time sharpening via these self-reward functions offers improvements over both vanilla (temperature 1.0) sampling and greedy decoding. In both cases, the improvements are generally much larger than those obtained with log-likeline likelikoeoood. Finally, examining the coverage criteria, samples, these models almost always produce correct answer on these tasks, raising the possibility of other self-reward functions that further improve performance.
that with N 50
23

---

Published as a conference paper at ICLR 2025
Phi3.5 (Mini) on MATH
Phi3.5 (Mini) on GSM8K
140
350
Correct
Correct
120
Incorrect
300
Incorrect
Count
80
Count
200
60
40
100
50
-300
-000
0
-300
-250
-200
-150
-100
Log Probability
Log Probability
(b)
Phi3.5 (Mini) on ProntoQA
Mistral-7B on MATH
70
90
Correct
Correct
60
Incorrect
Incorrect
70-
50
60-
Count
40
Count
40
30
20
10
10
0
0
-500
-400
300
-200
-100
-500
-400
300
220
-100
Log Probability
Log Probability
Figure 6: Distribution of sequence-level log-probabilities for responses sampled with tempera- ture 1, conditioned on whether or not the response is correct. We consider four model-dataset pairs: (a) (Phi3 5-Mini,, MATH); (b) (Phi3.5-14 5-Mini, GSM8K); (c) (Phi3.5-Mini. ProntoQA); (d) 3, MATH). In all cases except perhaps (c), conditioning on correctness of the response leads noticeable increase in prebbbbbbiliiies, further justifying the use of sequence- level bog-probabilities as self-reward for self-improvement.
24

---

Published as a conference paper at ICLR 2025
Model
Dataset
% Lift over Greedy (Accuracy)
Lift over Greedy (Likelihood)
Phi3.5-Mimg 5-Mini
MATH
19.24 + 2.41
48.33 + 0.17
Phi3.5-Ming
GSM8K
1.82 + 0.64
1.49 + 0.55
ProntoQA
12.46 = 1.08
5.64 + 0.01
Mistral-7B
MATH
8.88 + 5.55
5.71 + 3.00
Table Experimental results for SFT-Sharpening
Model
Dataset
Weight Decay
LoRA Rank
Thi3.5-Mingg
MATH
0.1
16
Phi3.5-Ming
GSM8K
0.5
16
Phi3.5-Ming
ProntoQA
0.0
16
Mistral-7B-IIssrrutt--.
MATH
1.0
8
Table 2: Hyperparameters for SFT-Sharpening
A.3 EFFECT OF SFT-Sharpening
In addition to inference-time experiments demonstrating the validity of the amortization objective considered in our theory, we also demonstrate empirically that amortization can be effected with SFT-Sharpening. Due to the realities of limited computational resources, we choose strict subset of the model-task pairs considered in Appendix A. that have particularly promising inference-time BoN performance and apply SFT-Sharpening to amortize the inference time cost of multiple generations.
For each of the chosen model-dataset pairs (cf. Table 1), we sample N 50 responses with temperature 1 for each prompt in the dataset and select the most likely (according to the relevant reference model). We then combine these likely responses with the prompts in order to form a training corpus and train Low Rank Adaptation (Hu et al., 2021) to the model, sweeping over LoRA rank, learning rate scheduler, and weight decay in order to return the best optimized model. 13 We report the specifie hyperparamters chosen in Table 2. On all models, we used a learning of 3 x 10-4 with linear decay to zero and gradient clamping at 0.1.
Results. In Table we report our results for the best model during training of each model-dataset pair, averaged across 3 random seeds, where responses are sampled with temperature from the fine-tuned model. We report both the percent lift in accuracy on the dataset with respect to the greedy generation of the reference model and the increase in average sequence level log likelihood with respect to the same. In all cases, we see improvement on both metrics, demonstrating that some amortization is possible with SFT-Sharpening In Figures 7 and 8, display the evolution throughout training of these same metrics for each of the model-dataset pairs. While Phi3. 5-Mini is quite well-behaved on MATH and ProntoQA, there appears to be fair amount of noise in the training on GSM8k, with the log probability being a significantly less useful proxy for accuracy on this dataset than the others, has been previously found in Block et al. (2023). In the case of on MATH, while we do see some improvement after sufficient training, the optimization suffers initial substantial drop and then spends 90% of the gradient steps recov- ering; we speculate that this is a function of insufficient hyper-paramene tuning of the optimization itself, rather than a fundamental barrier.
-tral-7--Inssruct
Finally, in Figure 9, we investigate the effect that the choice of has on SFT-Sharpening for MATH. In particular, in forming our training set, choose N E {10, 25, 50) and repeat the procedure described above, averaging our results over three seeds. We find that increasing N leads modest increase the sequence-level likellhodo and a consequent increment the accuracy of the fine-tuned model, in accordance with our theory.
In all experiments involving Phi3.5-Ming 5-Mini we use a batch size of 4: unfortunately, due to known numerical issue with LoRA on Mistral-78- Mettral-7BIInseeee Instruct-ve 3 involving batch size > 1. we use batch of I in this case. Be- cause of this choice, instead of the 30 epochs use to train our other models, for Mistral-P7 Instruct-vō. 3, only 10 epnchs.
25

---

Published as a conference paper at ICLR 2025
Phi3.5 (Mini) MATH
Phi3.5 (Mini) MATH
60
70
Accuracy over Greedy (%)
Log Probability over Groedy
40
SFT Inference
30-
20-
9000
0000000e0
20-
10
10-
SFT Inference
-10
0K
5K
10K
15K
20K
26K
30K
-10
0K
5k
10K
15K
20K
25K
30K
Checkpoint
Checkpoint
(a)
(b)
Phi3.5 (Mini) on GSM8K
Phi3.5 (Mini) on GSM8K
Accuracy over Greedy (%)
Log Probability over Greedy
4-
2-
SFT Inference BoN
-2-
SFT
Inference BoN
-10
0K
5K
10K
15K
20K
25K
5K
10K
15K
20K
25K
Checkpoint
Checkpoint
(c)
(d)
Phi3.5 (Mini) ProntoQA
Phi3.5 (Mini) on ProntoQA
Accuracy over Greedy (%6)
120
Log Probability over Greedy
SFT
100
Inference
60
SFT Inference
2
0-
20
-2-
-20
5K
10K
15K
20K
25K
-4
5K
10K Checkpoint
20K
25K
Checkpoint
Figure 7: Evolution of Phi3.5-Mini under SFT-Sharpening (N 50) on different datasets, as measured by (i) % lift over Greedy in accuracy; and (ii) difference in average sequence-leve log- probability of generated responses under the reference model. The fine-tuned model learns to produce generations with high probability under the reference model, and consequently enjoys an increase in accuracy compared the base model. However, the model does not fully reach the performance of inference-time BoN sharpening.
B DETAILED DISCUSSION OF RELATED WORK
In this section, discuss related work in greater detail, including relevant works already covered.
26

---

Published as a conference paper at ICLR 2025
80
Mistral-7B on MATH
200
Mistral-7B on MATH
Accuracy over Greedy (%)
Log Probability over Greedy
100
-100
20
M
-200-
-40
SFT
-300
SFT
Inference
Inference
400
0K
20K
40K
60K
80K
100K
120K
0K
20K
40K
60K
80K
100K
120K
Checkpoint
Checkpoint
Figure 8: Evolution of Mistral-77-IIntrucct under SFT-Sharpening (N 50) on MATH, as measured by (i) lift over Greedy accuracy; and (ii) difference in average sequence-level log-probability of generated responses under the reference model.
% Lift in Accuracy Greedy
Lift in Log Probability Greedy
25
60
Log Probability over Greedy
% Lift. over Greedy
20
50-
40-
30
20
N=10
N=10
N=25
10-
N-25
N=50
N=50
OK
5K
10K
15K
20K
25K
30K
0K
5K
10K
15K
20K
25K
30K
Checkpoint
Checkpoint
(a)
Figure Effect of N SFT-Sharpening for Phi3. 5-Mini MATH. We report (a) % lift in accuracy over greedy; and (b) lift in sequence-level log-likelihood (averaged over the dataset). In both cases, we see that increasing N leads to greater lift, in accordance with theory.
27

---

Published as a conference paper at ICLR 2025
delf-improvement and self-training. Our work is most directly related to growing body of empirical research that studies inproveeeeeet traatinnn for language models in supervision- free setting in which there is external feedback (Huang et al., 2022: Wang al., 2022; Bai et al., 2022b; Pang et al., 2023), and takes a first step toward providing a theoretical understanding for these methods. There is also closely related body of research on "LL.M-as-a-Judge techniques, which investigates approaches to designing self-reward functions Fself. often based on specific prompting techniques (Zheng et al., 2024; Yuan et al., 2024; Wu et al., 2024a; Wang et al., 2024).
A somewhat complementary line of research develops algorithms based on self-training and self-play (Zelikman et al., 2022; Chen et al., 2024; Wu et al., 2024c; Qu al., 2024), but leverages various forms of external feedback (e.g., positive examples for SFT or explicit reward signal). These methods typically outperform feedback-free self-improvement methods (Zelikman et al., 2022). However, in many scenarios, obtaining external feedback can be costly or laborious; it may require collecting high-quality labeled/annotated data, rewriting examples in a formal language, etc. Thus, these two approaches are not directly comparable.
We also mention that the self-improvement problem we study related to a classical line of research on self-distillation (Buciluă et al., 2006; Hinton et al., 2015; Devlin, 2018; Pham et al., 2021; Rizve et al., 2021), but this specific form of self-training has received limited investigation in the context of language modeling.
Entropy minimization. Sharpening is also closely related to a line of work on entropy minimization or minimum entropy regularization, where we seek models that have high predictive accuracy and low entropy/unceetaintyy. This line of work originated in the semi-supervised learning literature (Grand- valet & Bengio, 2004) and was popularized as test-time adaptation method in computer vision (c.f., Wang et al., 2020; Press et al., 2024). Maximum-likeliine likelihood sharpening, especially via RL, is closely related in that Eq. (3) with 3 - and r'serr = log base maximizes E,, [log Tasse =)) rather than ( [log (v x)). (It is important that the latter is optimized continuously with whase as
- (TT) = an initialization, but when this is done can be seen to sharpen Thase, at least heuristically. Prior work in this direction is largely empirical, focused on computer vision domains with small output spaces y, and hence studies statistical benefits of entropy minimization. In contrast, we initiate a theoretical study of sharpening. are primarily motivated by applications to language modeling with exponentially large output spaces, and view sharpening primarily as a computational phenomena. However, it would be interesting to understand whether statistical benefits observed in computer vision translate to the language modeling setting.
Alignment and RLHE The specific algorithms for seff-immpovementtharpennnn we study can be viewed as special cases of standard alignment algorithms. including classical RLHF methods (Christiano et al., 2017; Bai et al., 2022a; Ouyang et al., 2022), direct alignment (Rafailov et al., 2023), and (inference-time 2024; Gui et al., 2024; Pace et al., 2024). However, the maximum likelihood sharpening objective (2) used for our theoretical results has been relatively unexplored within the alignment literature.
training- time)) best-of-N methods (Amini et al., 2024; Sessa et al.,
Inference-time decoding. Many inference-time decoding strategies such as Seeedyllowteempertuure decoding. beam-search (Meister et al., 2020), and of-thuht decoding (Wang & Zhou, 2024) can be viewed as instances of inference-time sharpening for specific choices of the self-reward function rs More sophisticated inference-time search strategies such tree search and MCTS (Yao et al., 2024: Wan et al., 2024; Mudgal et al., 2023; Zhao al., 2024) are also related, though this line of work frequently makes use of external reward signals or verification, which is somewhat complementary our work.
Theoretical guarantees for self-training. On the theoretical side, current understanding of self- training is limited. One line of work, focusing on the self-distillation objective (Hinton al., 2015) for binary classification and regression, aims to provide convergence guarantees for self-training in stylized setups such as linear models (Mobahi et al., 2020; Das & Sanghavi, 2023; Das et al., 2024; Pareek et al., 2024), with Allen-Zhu & Li (2020) giving guarantees for feedforward neural networks. Perhaps most closely related to our work is Frei et al. (2022), who show that self-training on a model's 's pseudo- labels can amplify the margin for linear logistic regression. However, to the best of our knowledge, our work is the first to study self-training in a general framework that subsumes language modeling.
28

---

Published as a conference paper at ICLR 2025
Our results for RLHF RLHf-Sharpening are related to a body of work that provides sample complexity
guarantees for alignment methods (Zhu et al., 2023; Xiong et al., 2023; Ye et al., 2024; Huang et al., 2024; Liu et al., 2024; Song et al., 2024; Xie et al., 2024), but our results leverage the structure of the
sharpening self-reward function Fs x)) = log Thase (y | x), and provide guarantees for the sharpening objective in Definition 3.1 instead of the usual notion of reward suboptimality used in reinforcement learning theory.
Lastly, we mention that our pestill-parr our amortization perspective on self-improvement- are related to work that studies representational advantages afforded by additional inference time (Malach, 2023; Li et al., 2024). These work focus on truly sequential tasks, while our work focuses on the complementary question of amortizing parallel computation. Thus the representational implications are quite different.
Optimization versus sampling. The maximum- moximum--ikelihood sharpening objective we introduce in Section connects the study of self-improvement to a large body of research in theoretical computer science computational tradeoffs (e.g., separations and equivalences) between optimization and sampling (Barahona, 1982; Kirkpatrick et al., 1983; Lovász & Vempala, 2006; Singh & Vishnoi, 2014; Ma al., 2019; Talwar, 2019; Eldan al., 2022). On the one hand, this line of research highlights that there exist natural classes of distributions for which sampling is tractable, yet maximum likelihood optimization is intractable. and vice-versa. On the other hand, various works in this line of research also demonstrate computational reductions between optimization and sampling, whereby optimization can be reduced to sampling and vice-versa.
Our setting indeed includes natural model classes where one should not expect there to be a com- putational reduction from optimization (arg max Tyase x)) to sampling (y basse x) and hence inference-ting sharpening is computationally intractable (Proposition E.1). Of course, coverage assumptions eliminate this intractability. For training- amortize across prompts by training sharpened model, as formulated in Section 3) the obstacle in natural, concrete model classes is not just computational but in fact representational (Proposition E.2). Regarding the latter point, we note that while amortized Bayesian inference has received extensive investigation empirically (Beal, 2003; Gershman & Goodman, 2014; Swersky et al., 2020; Bengio et al., 2021; Hu et al., 2023), we unaware of theoretical guarantees outside of this work.
sharpening (where the goal is to
C GUARANTEES FOR INFERENCE-TEE TIME SHARPENING
In this section, give theoretical guarantees for the inference- time best-of-NN sampling algorithm for sharpening described in Section 3.1, under the maximum- maximum-likelibood sharpening self-reward function
Tseir(y Ix; Toase) = log Tasse (y) zz).
Recall that given prompt E X, the inference-tine best-of-N sampling algorithm draws N responses .i..... yn ~ ( z). then return the response D = arg max,, log Thase (y: z). We show that this algorithm returns approximate maximizer for the maximum-likelihood sharpening objective whenever the base policy Thase has sufficient coverage. For a parameter y E [0, 1) we define
{"/ Thase (y x)) 2 (1 - 7) max Thase (y xx)
yEy
as the set of (1 7) approximate maximizers for log Mbase (v I) (see Appendix F.1 for background on (x)). Proposition C.I. Let a prompt X be given. For any p E (0, and 7 [0, 1), as long as
log(p-1)
N
Tbase (y, x))
inference-time best-of-N sampling produces a response ÿ (7 with probability at least 1 -
Proof of Proposition C.I. Fix a prompt & E X, failure probability E (0, 1). and parameter 7 (0, 1). By definition of the (z), y E (x) if and only if there exists i E [N] such that V: E y (z). The complement of this event, i.e., that yi (x) for all E [N], has probability
P(u: (x). Vi E [N]) = Tuase (v) x=))*²
29

---

Published as a conference paper at ICLR 2025
Rearranging the right-hand side, we have
-basa (y, x)) )0/ = exp (-N log
Tbase (y x3) ))
(1 - Tbase
exp(-N
Thase (2 x)),
since log(x) 2 1 for x >> O, which implies that log 1- 2 Tasse (3, | x). Thus, as long as N 2 log(p Musse 1x) we have
P(y $ (z) [N]) & expp Toase (yz x)) S exp(- 1isp(-log(p Log(p-
We conclude that with probability at least p, there exists i [N] such that yi y and y, (2) as result.
D GUARANTEES FOR SFT-Sharpening WITH ADAPTIVE SAMPLING
SFT-Sharpening is simple and natural self-training scheme, and converges to a sharpened policy However, using fixed response sample size N may be wasteful for prompts where the model confident. To this end, in this section we introduce and analyze, a variant of SFT-Sharpening based adaptive sampling, which adjusts the number of sampled responses adaptively.
+ N
Algorithm. We present the adaptive SFT-Sharpening algorithm only for the special case of the maximum likelihood sharpening self-reward. Let stopping parameter μ > 0 be given. For a4 E X, and Bt, V1,2 T- 2;), define stopping time (e.g.. Benjamini & Hochberg (1995)) via:
(xx) = inf k: maxigisk Tbase (Vi.) Zi)
(10)
fz
The adaptive SFT- ShTr-hhppnning algorithm computes adaptively sampled responses y AdaBoN via
Vi
AdaBoN
arg max log Mause [x;) Vi,ly... J...,.......,,....... (e.))
then trains the sharpened model through SFT:
AddaBoN arg max HE
Σ log n (y
AdaBoN x;)).
Critically, by using scheme in Eq. (10), this algorithm can stop sampling responses for the prompt a; if it becomes clear that the confidence is large.
Theoretical guarantee. We now show that adaptive OFT-Sharpening enjoys provable benefits over its non-adaptive counterpart through the dependence on the accuracy parameter c >> O.
Given X, and Vı, 1/2 ... Tbase (x), let Na(x1) inf
maxis SISK Thase (2A [x) S k/uJ. and
define random variable (x) ~ arg max max Tuase (V: I x)) Vi,..., . UN,, Tbase (base( (x)) Let
AdaBoN (x) denote the distribution over y AdaBo (z)). We make the following realizability assumption. 2
Assumption D.1. The model class satisfies oT
AdaBoN II.
Compared to SFT-Sharpening, we require a somewhat stronger coverage coefficient given by
1
Coo = Ezzg
max Taase (v x))
This definition coincides with Eq. (6) when the arg-max response is unique, but is larger in general.
Our main theoretical guarantee for adaptive SFT-Sharpening is as follows.
30

---

Published as a conference paper at ICLR 2025
Theorem D.1. Let 6, (0,1) be given. Set μ In(26-1) and assume Assumption D.I holds. Then with probability at least 1 p. the adaptive SFT-Sharpening algorithm has
log( [1I)-')
P Pawul (Ty (x)
x) I 8]
8n
and has sample complexity [[m]] n Can log (6-1))1) 1- Taking n 2 probability at least Pb P xm p (T (y" (ar) x))
ensures that with
be
8) S and gives total sample complexity
m Coov log l ( log(6
dc
Compared to the result for SFT-Sharpening in Theorem 4.1, this shows that adaptive SFT-Sharpening achieves sample complexity scaling with instead of z.2 We believe the dependence on Cevv for this algorithm tight, the adaptive stopping rule used in the algorithm can be overly conservative when [x)] is large.
matching lower bound. We now prove a complementary lower bound, which shows that the e-dependence in Theorem D.I is tight. To do so, consider the following adaptive variant of the sunle--ndd-evalatt framework.
Definition D.1 (Adaptive sample-and-evaluus and-evaluate framework). In the Adaptive Sample-and-Evaar Evaluaa framework, the learner is allowed to sample n prompts x ~ i4, and sample an arbitrary, adaptively chosen number of samples Y1 1/.- Tbase x) before sampling new prompt x' p.. In this framework we define sample complexity m as the total number of pairs (x, v) sampled by the algorithm, which is a random variable.
Our main lower bound as follows.
Theorem D.2 (Lower bound for sharpening under adaptive sampling). Fix an integer d 2 1 and parameters E (0, 1) and C 2 1. There exists class of models II such that (i) log [II 2 C, and (iii) (x) singleton for all a II, for which any sharpening algorithm ãे in the adaptive
d(1 + log(Ce- (ii) sup (cov(T))
framework that achieves x) > 1/2]] 2 1 for all Taase must collect a total number of samples
E[F x (y
n.. N at least
C Coo III
m
(1+ log(Ce-1)))
Theorem D.2 is a special case of a more general theorem, Theorem 3.1', which is stated and proven in Appendix H.
E COMPUTATIONAL AND REPRESENTATIONAL CHALLENGES IN SHARPENING
In this section, we make several basic observations about the inherent computational and repre- sentational challenges of maximum-likelihood sharpening. First, in Appendix E.I, we focus on computational challenges, and show that computing a sharpened response for given prompt x can be computationally intractable general, even when sampling y ~ Taase (: 2) can performed efficiently. Then, in Appendix E.2, we shift our focus to representational challenges, and show that even if Taase is an autoregressive model, the "sharpened" version of Toase may not be representable as autoregressive model with the same architecture. These results motivate the statistical assumptions (coverage and realizability) made in our analysis of SST-SSharpninggggg and RLHF LL.F--Sharpening in Section 4.
To make the results in this section precise, we work in perhaps the simplest special case autore- gressive language modelling, where the model class consists of multi-layer linear softmax models. Formally, let be the space of prompts, and let y == y be the space of responses, where V is the vocabulary space and H is the horizon. For collection of fixed/known d-dimensional feature mappings on X' x yh + Rd and a norm parameter B, we define the model class II B, as the set of models
H
To(UI.H xx)
II A=1
ma, (yh I, V1-h-1)
(1I)
31

---

Published as a conference paper at ICLR 2025
where
To(yk I x, (P,1.n-1) x exp((ó(a, yha)). Bx)) and = -01,...,00) On) E (IR is any tuple with |0x,12 S for all h E [M].
E.1 COMPUTATIONAL CHALLENGES
Given query access to é. for any given parameter vector @ and prompt æ, sampling from a linear softmax model Te (Eq. (11)) is computationally tractable, since it only requires time poly (H, [V], d). Similarly, evaluating ( | x) for given prompt æ and response V1&H is computationally tractable. However, the following proposition shows that computing the sharpened response arg max " (8(11 z) for a given parameter 0 and response x is NP-hard. Hence, even inference-time sharpening is computationally intractable in the worst case.
Proposition E.1. Set X = { and V = 13, Ser d = d(H) == H + H² + H Identifying [d] with [H] u [ Li [H] we define on : :X' x Vh - Rd by da (L. yi:k); = y) and Φn(L, ) ycyi and on (L, (1..) = Mclj There is function B(H) S poly(H) such that the following
problem is NP-hard: given 0 = (01...., .0)) with ma |0all2 S B(),, compute any element
of arg y w T x).
Note that our results in Section 4 and Appendix C bypass this hardness through the assumption that the coverage parameter Ceov is bounded.
Proof of Proposition E.1. Fix H and recall that d(H) H + H2 H H² We define three collection of basis vectors: {en hei)) cover the first H coordinates, {ew.re))a cover the next H² coordinates, and {<(M,N,,N)) ) MM cover the last H3 coordinates. Suppose we define 0,,..., On-2 O, so that To (2, 11:h-1) = 112 for all 1 < h S H - 2. Define 0 = -isiisH (isC(k...H-) for matrix J E (2-
to be specified later, and define 1) S 1/2 for any VI:H with yи-1 -1 or VH = 1, since this implies that Ten (yH 1, 11) s 1/2. Meanwhile, for any yı.H with
H B (e(H-1,H) + eH). Then 2H-2 TO TT(11.
H8 = VH = 1, we have
exp E Eissn 21yVets)
exp( B) exp - + eexp +exp(-Ensh --Engnn- Jiyke.) exp(BB + exp(- (BB)
2"-2 To 1)
Let G be any graph on vertex set [ - 2] and let J = -A(G) where A(G) is the adjacency matrix of G. Then among V1-H with - уи 1, 2H- T -) is maximized when 91:H-2 corresponds to a max-cut in G. G has an odd number of edges, then some max-cut removes strictly more than half of the edges, and for the corresponding sequence yı-и have 2 - T0(Hi:
1) 2 (1/2 + ((1)) (1 cxp(-S(BB)), which is greater than 1/2 when we take B : H and H is sufficiently large. Thus, computing arg max ye
it Th (y1. 1) yields max-cut of G. It is well-known that computing a max-cut in graph is NP-hard, and the assumption that G has an odd number of edges is without loss of generality.
E.2 REPRESENTATIONAL CHALLENNES
To give provable guarantees for our sharpening algorithms, we required certain realizability assump- tions, which in particular posited that the model class actually contains "sharpened" version of Toase (Assumptions 4.1 and 4.3). In the simple example of single-layer linear softmax model classes (corresponding
H in the above definition), Assumption 4.3 is in fact satisfied, and the sharpened model can be obtained by increasing the temperature of Taase. However, multi-layer linear softmax models with H > 1 are more realistic. The following proposition shows that as soon as H 2 2, multi-layer linear softmax model classes may not be closed under sharpening. This illustrates a potential drawback of training-time sharpening compared to inference-tine sharpening. which requires no realizability assumptions. It also provides a simple example where greedy decoding does not yield a sequence-leve arg-ma max response (since increasing temperature in a multi-layer softmax model class exactly converges to the greedy decoding).
Proposition E.2. Let X = {1}. V [n]. and H = d = 2. For any n sufficiently large, there is multi-layer linear softmax policy class 1I, H. and policy Taase E To, H such that yi.H
32

---

Published as a conference paper at ICLR 2025
arg y NVN (V1:1 T (VT. 1) S 1/2.
1) is unique, but for all B' B and π B H. it holds that
Proof Proposition E.2. Throughout, we omit the dependence on the prompt T for notational clarity, Since H 2, the model class consists of models of the form
T = no, (v1) (u2 vn) exp((0) (v)), (xp(()i(v)))0)) 01)) exp (02(1)22) 02)) Zo,
(12)
Zo, (v1)
for Zo. := (xp(((((()) 01)) and (oz(vi) = Eyee exp(((2(112) 02)).
Define Φi by:
E1 =fi=1
(1)
if = 2.
e2
2 3
Define @e by:
61
if 2,j if
(2(1.))
22
2,j #1. 1.
0
#
Define Tbase Tg. where 8 0 = BBee for parameter B log(n). Then Tasse (1) Tasse (2) and Thase (1) S e Thage (2) for all i E [3.....n} Moreover, Trase (: i) = Unif [m) for all + 2,
and Thase (j 2) < e Thase 2) for all + Thus,
1
Tasse (2, 1) = Taase (base (1 2) 2
2 + (n 2)--B 1 (n 1)e 2 2(1)
whereas Taase (i,j) = O(1/n) for all (i.j) + (2, 1). Thus, (2, 1) is the sequence-level argmax for sufficiently large n. However, for any Ty of the form described in Eq. (12), we have
(2)
me (2, 1) (2)
(1 (2)
since (i(1 ((2). This means that there is B' for which H. n contains an (c, -)sharpened policy for Tbss for any 8 > 1/2.
33

---

Published as a conference paper at ICLR 2025
Part II Proofs
F PRELIMINARIES
F.1 GUARANTEES FOR APPROXIMATE MAXIMIZERS
Recall that the theoretical guarantees for sharpening algorithms in Section provide convergence to the set y (xx) == arg max yEy (bs x) of (potentially non-unique) maximizers for the maximum-likelihodd sharpening self-reward function log bbsee I). These guarantees require that the base model Thsse places sufficient provability mass on (x), which may not always be realistic. To address this, throughout this appendix we state and prove more general versions of our theoretical results that allow for approximate maximizers, and consequently enjoy weaker coverage assumptions
For parameter
[0, 1) we define
(7) = {u Taase (y [1)]=)
) 2 (1 -7 max Thase (y/ x)) yEy
as the set of (1 7) approximate maximizers for log (y x)). We quantify the quality of sharpened model follows.
Definition F.1 (Sharpened model). We say that a model ãt is (e, (, -harpened relative to Thase if
P Pawu (x), 2) 2 1-6 8| 2
That is, an (e, 6, -haapeeeed policy places at least 1 - mass on (1 - 7) approximate arg-max responses on all but an e-fraction of prompts under μ..
Lastly, we will make use of the following generalized coverage coefficient
1
Ccov. Buwn
Thase (g7 x))
which has Ceavyy I Crov-
F.2 TECHNICAL TOOLS
For pair of probability measures IP and Q with a common dominating measure w, Hellinger distance is defined via
2
DR /
dP
dQ
dw.
dw
dw
Lemma F.1 (MLE for conditional density estimation (e.g., Wong & Shen (1995); van de Geer (2000);
Zhang (2006))). Consider conditional density x² : :X - A(Y). Let D = (z),, y be dataset in which (I4, y1) are drawn i.i.d. as x4 a E ((X) and yı x x). Suppose we have finite function class II C (X + A(V)) such that n TT. Define the maximum likelihood estimator
arg max senl
Σ (La))D
log ( xx).
Then with probability at least 1
2 2log([[Tpp
Exnop D2 x), x² xx)] <
n
Lemma F2 (Elliptic potential lemma). Let X, K and let A..... Ar dddd be positive
semi-da defiite matrices with Tr(A,) & K for all t (T]. Fix To AIa and T, Ala + -i= for
t E (T). Then
T Σ T(TZ)A <
dK log (T+1)
Alog(1 K/X)
34

---

Published as a conference paper at ICLR 2025
Proof of Lemma F.2.
Fix [T]. Since Tr(A)) 1, there is some pt A(R") such that Ag = Eappp aa and P|laa| $ 1 = Now observe that
log (T) = log det(T,-11 + A,)
log (e + log del 1, A,T,1111
1/2 2-1
log det + log det Earp I 1-122 aa T
2 log det((T,-)) + Earp, log det (oo + 1- ua 3
log det(Tr-1) + Eawp, log(1 + a rT
Now TerTrre a S 1/A with probability 1, where X = (Too. We know that Xr log(1 1/A) S log(1 + x)) for æ E [o, 1/ Thus,
log det(TT) 2 logdet(Fr-1) A + 1/A) Tr
Summing over t E [T], we get
log det (Tr) 2 log det (To) + +Alog(1 1/1) Σ TT(TT11))
Finally note that Amax (Tr) T so log (T) d dllog T, whereas log det(To) 2 dlog A. Thus,
d dlog X
Σ Tr(T S Alog(1 1 + 1/A)
as claimed.
Lemma F.3 (Freedman's 's inequality, e.g. Agarwal et al. (2014)). Let (Z,)T= be a martingale
difference sequence adapted filtration (Fr) Suppose that [2,] S R holds almost surely for all I. For any 5 E (0, 1) and n E (0, 1/R), it holds with probability at least - 8 that
T
T
E| log(1/8)
Σ 2. 1 t=1
1=1
Corollary F.1. Let (Z,).=, be sequence of random variables adapted to filtration (Fi)
Suppose that Ze E [0, R] holds almost surely for all For any 8 E (0. 1), holds with probability at least 1 - 8 that
T Σ
EZ
Σ Z, 1Rogg(1/))
Proof of Corollary F.. Observe that for any E TT]
B[(Z, Z 1 F(-1] < E E F(-1]
- R Z F.-1).
Applying Lemma F.3 to the sequence (, Fi-1] sequence with elements supported almost surely on [RR, Rt.. we get for any 1 E (0, 1/R) that with probability at least 1 - 5,
2:) which martingale difference
B[(Z. - B|2, F= [e-1]+ + log(1/8)
Σ (B|Z Fc-1] - 2c) < n
1=1
T
E|2, Fr-1]+ + log(1/5)
< n
1=1
Set 17 1/(2R). Simplifying gives
Σ
Z
Fz-1]
Σ
Z. 4Rlog(1/6)
t=1
as claimed.
35

---

Published as a conference paper at ICLR 2025
G PROOFS FROM SECTION 3.1
Proof of Proposition 3.1. We prove the result by induction. Fix I E X, and let yi..... Vi y-)) Fix h [H], and assume by induction that Th Vh. for all h' < h. We claim that in this case,
(y ..,.... 7h-1, 2) TA (vh Vi...... 16, 1/2,
which implies that Dn yh. To see this, we observe that by Bayes' rule, <Vi..... VH x)) S π (vi.
Vi x)
h
The (yi vi 11, S TA (17 yi ..... 1 #==1
II
we were to have (v6 .i..... 0, x) = (yh vi...., vh-1: S 1/2, it would contradict the assumption that (vi..... x) 1/2. This proves the result.
H PROOFS FROM SECTION 3.3
Below, we state and prove generalization of Theorems 3.1 and D.2 which allows for approximate maximizers the sense Definition F.1, as well as a more general coverage coefficient.
To state the result, for model we define
y (x) y T(y (2) 2) (1-7)
max ( 1x) vEy'
Next, for any integer p N, define
(pp))==(((( (B((T(()())))
x)); ))²
1/8
Coov.y.(
with the convention that Coow.r.p Ccov v. (bass)). Our most general lower bound, Theorem 3.1', holds in the regime where 7 = 1/2, and thus the best responsey has bounded margin away from suboptimal responses.
Theorem 3.1' (Lower bound for sharpening). Fix integers d 2 1 and p 2 1 and parameters e E (0, and 2 1, and set 7 = 1/2. There exists a class of models such that i) log [TT] x d(1 + log(Cc-1/P)), ii) suprem (cov.n.((T) S C, and iii) y,, (x) for which any sharpening algorithm के that attains E [T [Tly (x)) > 1/2]] 2 - - all Thase E II must collect total number samples m N at least
singleton for all E II,
llg [II] Cle C' log III
cample-and-evalin oracle,
m 2
adaptive comple-and-evalee oracle.
Proof of Theorem 3.1'. Let parameters d, p and be given, and 7 1/2. Let M and A >> 0 be parameters to be chosen later. Let X = { T1,... val and y = {Wos $1..... MM be arbitrary discrete sets (with | = d and | M + 1).
Construction of prompt distribution and model class. We use the same construction for the non-adaptive and adaptive lower bounds in the theorem statement. We define the prompt distribution via
# = (1
where 6 denotes the Dirac delta distribution on element ...
As the first step toward constructing the model class II, we introduce family of distributions
(Po, Pt. Pi...., PMr) on y as follows
Po S
Vi z 1, (1 - 7)M
1
Sq.
Σ
7 M
1 (1-
(M 1)(1 - -7) 8
JE(M)E(
36

---

Published as a conference paper at ICLR 2025
Next, for any index I
[M]] define model
Po i=
π (x,)
Pr
i> 0
We define the model class as which we note has
= { [M]*].
log |T| dlog M.
Preliminary technical results. Define
(x) = tv : =" x)) 2 (1 7) max 7" x)}.
yEy
The following property is immediate.
Lemma H.1. Let I = ,J Ja) [d]M. Then y (xx) {uj if 0, and (Z())) = {yo}-
In view of this result, define (x) arg max, x y x) the unique arg max response for
Going forward, let us fix the algorithm under consideration. Let P denote the law over the dataset used by the algorithm when the true instance is x (including possible randomness and adaptivity from the algorithm itself), and let [= denote the corresponding expectation. The following lemma a basic technical result.
Lemma H.2 (Reduction to classification). Let क be the model produced by an algorithm with access to (adaptive) sample-ande
oracle for x². Suppose that for some e Z O,
EI~unit E² (a
x) > 1/2] 2 1
Define ī GI,..., 3d)) via Jr = arg max, $ 7V; z.), and write I = (Ji..... Then,
E Enii E
[ + j s/A.
7
Proof of Lemma H.2. As established in Lemma H.1, under instance I, (x:) = {リr} for any i [d]. Thus, whenever म (y (1:)) 1/2. arg max, 7(y; (x:) =:
Te. The result follows by
noting that the event I E [d] x x; occurs with probability least A under J.. I
Lower bound under sample-and-evaluse oracle. Recall that in the non-adaptive framework, the sample complexity vn is fixed. In light of Lemma H.2, it suffices to establishes the following claim.
Lemma H.3. There exists universal constant e such that for all M 2 8, m S cdM/ A, then EI-unif E [G # 1 2 1/8 for all i.
With this, the result follows by selecting A 16c, with which Lemma H.2 implies that any algorithm with Ez-uniF BAT ( (a) x) > 1/2] 2 1 - must have m 2 dM/A. To conclude, we choose M x 1 + -1/1/p, which gives x dM/A A x dCe d1+1/)) x e -1++1/p) log II/ log(1
(P). Finally, check that with this choice, all II satisfy
Coov.y.p (TT) (Par~ll [x Nol + (M(1 - Pa-ppl * xol)
((1-)) = =((1 - A) + (M) 1/P
$ ((1-A) + (8C(1- 7)) S.
Proof of Lemma H.3. Let i E [d] be fixed. Of the m n .N tuples (x, y, log Taase x)) that are observed by the algorithm, let m; denote the (random) number of such examples for which æ = Iz. From Markov's inequality, we have
1 P(m; S 22m/d] 2 2
(13)
37

---

Published as a conference paper at ICLR 2025
Going forward, let D {xx y, log Tysse yy =)}} denote the dataset collected by the algorithm. which has (D) = m. Let & denote the event that, for prompt I = 2s, (1) there are at least two distinct responses Yj for which (2), D; and (ii) there no pairs (Iz, y) D for which Trase (y x44) M- Since is measurable function of D,
write
Ez E² [R # J:3] > EI~uniP E²
[ ) [{
= BIzuunif E²
[(()) RI~PLI= D) [TG: + + mm]]]
(14)
where I ~ PIZ = | D] is sampled from the posterior distribution over I conditioned on the dataset D. Observe that conditioned on & the posterior distribution over j under I PIZ = D) is uniform over the set of indices j E [M] for which (Ir, DD and this set has size at least Hence,
[{E;) EI~HI=-DD
[ + 573
2 2. and resuming from Eq. (14), we have
1
Ez~unif
E
[ + 11
2 EI-unif E
2
2 EI IP' [8 n {m; S 2Am/d]]
2 RI-unif TPZ [& my S 2Am/d],
where the last inequality is from Eq. (13), Finally, we can check that under the law PT. the probability of the event & conditiooe on the value m,- is at least the probability that (x4, 8ot ), (I Uy & D for an arbitrary fixed index j' * jr, which on the event {m, S 2Am/d is at least
1
3
m,
3 M
20m/d
2
M
where we have used that = 1/2. The value above is at least 1 whenever m I c. dM/A for sufficiently small absolute constant c > 0. For this value of m, we conclude that p [E {m, < 2Am/d)] 2
Ez-unif E
16: #
1 2 1 EI.unif
Lower bound under adaptive sample-and-evaluat oracle. In the adaptive framework, we let my denote the (potentially random) number of tuples (z, y, log (y =)) observed by the algorithm in which æ Note that unlike the non-adaptive framework, the distribution over m, depends on the underlying instance I with which the algorithm interacts.
To begin, from Lemma H.2 and Markov's inequality, if ā satisfies the guarantee Ez-unif B² Przaa (T() (x:) 1/2] c, then there exists set of indices Sgoad [d] such that
2x [ +13
Sgooo 2 [d/2],
Vi E Sgaod, Er IEZ
(15)
A
We now appeal to the following lemma.
Lemma H.4. As long as M 2 6. it holds that for all i E [d].
Ex E [113 + 5o
Ezaunir E7 [1,m; S M/33].
4e
Combining Lemma H.4 with Eq. (15), follows that there exist absolute constant C12 02, C3 > 0 such that if A = Ci e, then for all E Sgood.
Exaunit pd [m, 2 c2M] 2 e3.
Thus, with this choice for A, have that i Sgood:
EI- TTT [m:] Ž M,
Weee emphasize that the set Spood is random variable, and depends only the algorithm itself.
38

---

Published as a conference paper at ICLR 2025
and we can lower bound the algorithm's expected sample complexity by summing over i Sgoos!
Br-unif E [m] 2 Ez-ini E²
Σ
mi
good M 2 d.M
iE
iES
The result now follows by tuning M 1 + Cc Cc-1/p in the proof of the lower bound for non-adaptive sampling, which gives [/m] 2 dM x dCe x e- log 11/ log Ce!/) and Ccov.r. (T) & C for all x E II.
Proof of Lemma H.4. Let [d] be fixed. Let D {xx, y, log (ys x))} denote the dataset collected by the algorithm at termination, which has [D] = m. Let & denote the event that, for prompt 34 (i) there
least two distinet responses yj for which (z,, by) D: and (ii) there no pairs (z4, y) E D for which Tbsse (y x;))
I Since & is measurable function of D, M
can write
En EZ
11 + 153]
2 EI~unir E²
1 + 1...I [{4)]
= =Iz~unir E²
[[E BI-MfI= d) [GG. * 11
(16)
where I ~ PIZ = | is sampled from the posterior distribution over I conditioned on the dataset
D. Observe that conditioned on & the posterior distribution over j under I P D] is uniform over the set of indices j E [M] for which (I,, Mj) $ DD and this set has size at least 2. Hence,
[(&)) EI~HH=1D)
[1 + } 2
2. and resuming from Eq. (16), we have
EIaunif B²
[15 + 573
EI-unif E² [1{8;]]
1
2 EI-unit pz [& {m, S M/33]
2 Er-unif
[ mi S M/3) P= S M/3]].
The event & is superset of the event E that (Ia,3;;) (1., Uy) & 'D for an arbitrary fixed index j' # jr. Thus,
ps [E m, S M/3 2 pd [E m, M/3]
realize the law of TPZ considering infinite tape, associated index i, of i..d. samples ~ Thase(: (. | x.), and taking the first m, elements on this tape to be the samples (x, y, log Toase (y x)) E D with = x; (see, e.g. Simchowitz et al. (2017) for an argument of this form). On the event {m, < M/3), the m, samples in (z, y. log Toase (y x)) E D with æ 2, are subset of the first M/3 samples from the index-i tape. Viewed in this way, we can lower bound the probability of &., by the probability of the event E that the first M y's on the index-i tape contain neither jr, nor the designated index j'. As these first M/3 y are not chosen adaptively, the probability of E is least
Moreover,
(1-
3
m,
3 M
M/3
1
>
1
>
M
2c
as long as M 2 and 1/2. We conclude that
Er-unir E²
[1 # o73]
2
Ezaunse
E²
[11m S M/3]].
4e
I PROOFS FROM SECTION 4.1 AND APPENDIX D
The following theorem is a generalization of Theorem 4.1 which allows for approximate maximizers in the sense of Definition F.1.
39

---

Published as a conference paper at ICLR 2025
Theorem 4.1'. Let p. 8 E (0, 1) be given, and suppose set N N log(28-))) for a parameter
N E N. Then for any n E N, SFT-Sharpening ensures that with probability at least - p. for any y (0,1), the output model ît satisfies
1 Pr~p ()))(() 2) 51
log( 1og((11[p_)) Ceov,y N
n
log III and N Ca.1 In particular, given (c, 6, 7) by setting n Ca.1
Can. for sufficiently large
&e
absolute constant C4.1 > O, we are guaranteed that
Pawa 7 [2) se
The total sample complexity is
(Ceorry lo 1ogg0 1og(d-1)
m O
8c2
Proof of Theorem 4.1'. Under realizability of T (Assumption 4.1), Lemma F.1 implies that the output of SFT-Sharpening satisfies, with probability at least -p. P.
2 loo l1/p)
D 1)) M
x))]
S stat
(17)
n
Henceforth condition on the event that Eq. (17) holds. Let
x [ I
X gaod
Tbase y (1)) x))
denote the of prompts for which Thase places sufficiently high mass on y (I). We can bound
P Pawu (xy x) _ 8 6]
Pa (T (x) x)) S - 5, E Xgood] Pa-pul [xr & Xgood]
(18)
To bound the first term in Eq. (18), note that if Xgood then BaN (y (x) x)) 1- 8/2. Indeed,
observe that y ~ x z) & (z) if and only y1..... UN Taase (z) have ys & (z for all i, which happens with probability (1 Toase (x) x)) < (1 - 1/N*) )N < 8/2 since x E Rgoad
follows that for any such æ,
lower bound (using the data processing inequality)
2
Da ( I)), ( x))
(V F(U x) v1 11 N (y (ar) x))
8 (1)(()))))))
(19)
By Eqs. (17) and (19), it follows that
Etat
PIzp [ ( 1
5, x E Xgood] $
8
For the second term in Eq, (18), we bound
P PaNu(x & Xgood]
N
Tbase (37(x)) xx)
1
Pxwu
N Thase (y (x) xx)
N*
Tbase (M) (x)
Ccou. N
via Markov's 's inequality and the definition of Ccow,y. Substituting both bounds into Eq. (18) completes the proof.
40

---

Published as a conference paper at ICLR 2025
Proof of Theorem D.I. The proof begins similarly to Theorem 4.1. By realizability of NN,
Lemma F.1 implies that the output of SFT-Sharpening satisfies, with probability at least - P.
2 (11pp)
BRnn [D (f( TN, x))] S E
Condition on the event that this guarantee holds. We invoke the following lemma, proven in the sequel.
Lemma L.I Let P be a distribution on a discrete space V. Let y = arg max P(y) and let p = maxyey P(y). Let V1, U2. P, and for any stopping time т, define
Ør E arg max (P(u) y (vi...., U-}}
Next. for a parameter μ > O, define the stopping time
N₂ = inf k: maxisisk P(ve)
1
S sk/N)
Then
B[N S + (1/19"1)
pa
In addition, for any stopping time N₂ (including N2 itself), have P(ur $ yn S e ww This lemma, with our choice of μ., ensures that for all x E X.
TN, (1"((x) x) 21 - e = 1 56/2.
Following the reasoning (19), this implies that
( a), ( x)) 2 6 -1
so that
2
Pawp (f( x) < - 8]
stat
8
as desired.
To bound the expected sample complexity, we observe that
1 1
E[m] = n (x)]
E
= =(1 + Cconn
Tasse (1 (x) x))
where inequality (1) invokes Lemma I.1 once more.
Proof of Lemma L1. Define N := ppPp To bound the tails of N,, define
T inf {k: 2 N and y n (v,,..,, yh * Ø).
It follows from the definition that N₂ T, since for any l N if there exists & such that Y: E yy, then
1
P())
p
Thus, for ls > No, bound
P[N > k] k) SPT k| PD* n tyi..... x
and consequently
E[N < E < E|T[(T < N [ N
< N + Σ (1 - PT)
b>
+ 1/19*
$ N* P(r") P(y*)
41

---

Published as a conference paper at ICLR 2025
To prove correctness, observe that N₂ 2 N*. because for all y y Ply) 2 / Hence, any stopping time 2 N₂ also satisfies 5 2 N*, and moreover has Dr E y¹ whenever y (11, 32..32..... Vr / * Ø. This fails to occur with probability no more than
1
y4' P
N
-11-
y2
u/P
S Se
11
p
J PROOFS FROM SECTION 4.2
J.1 PROOF OF THEOREM 4.2
We state and prove a generalized version of Theorem 4.2. In the assumptions below, we fix parameter y E [0, 1): the setting = corresponds to Theorem 4.2.
II satisfy C. S for parameter Ceane 2 (1 2 cov.7" and / & for a parameter Closs 2 |//.
Assumption J.1 (Coverage). All
By Lemma 4.1', Assumption J.1 is consistent with the assumption that zz II.
Assumption J.2 (Margin). For all x supp(μ)). the initial model Thase satisfies
Thase (x) xx) Tmargin) Thase (y x)) Vy $ (x)
for parameter "/margin 0.
Theorem 4.2'. Assume that v TI (Assumption 4.3), and that Assumption 4.4 and Assumption 4.2 hold with respect to some 7 E [0, 1), with parameters Ccanes Closs: and Tmargin > For any 5, p E (0, 1), the DPO algorithm in Eq. (4) ensures that with probability at least p.
Cronc Lonnlooogsasss (Crass Mlp-1)
IP 22mup (T)((()) x:) 21 -6]
(log(Ccanc) +
imargin
n
where Ō(-) hides factors logarithmic in n and Ceone and doubly logarithmic in II, Crassy and pm
We first state and prove some supporting technical lemmas, then proceed the proof of Theorem 4.2'.
J.1.1 TECHNICAL LEMMAS
The following result a generalization of Lemma 4.1.
Lemma 4.1'. For all y (0, 1), the model xīz satisfies C23 -1-o)--Coov
CCoory and
Cmmal+ S 12%
42

---

Published as a conference paper at ICLR 2025
Proof of Lemma 4.1'.
For any fixed x E X, we have
-1
E (+12)
x (y x))
E (112)
bose
1+3
(y x))
base
1+9-1
(s' 2x)
Tbase (y x))
Tbase
x))
V'EY
I max
9-1 (y (x)
Σ
base
(v/ 1
yEy
N'EY
I (1--)) (1- 1----maae 9-1
base (1) | [x:)
Σ
1+8-1
(0' xx)
base
B'EV
14.9 base
(y (2r) (x)
= - 7)
Thase (2, (xx) x.)
Σ
base
1+8-
(0' x))
B'EY
-1 7)-1 EyEN (w)
1+9 bass
(y (x)
Σ
1+0
(y/ (x)
Thase (2) x))
n
base
V'Ey
- (1 7)
Tbase (1) x)
It follows that Cr; S (1 (1-7) 71- as claimed.
For the second result, we have
87 '0''(00
Cupnee/3 Ex
Σ
1+8 "ass
x))
B
E
12%
Thase (y x))
Toase (3) x3)
V'EY
The next lemmas provide bounds on the tails of the self-rewards used in the algorithm.
Lemma J.1. Suppose 3 E [0, 1]. For any model æ, with probability at least 1 over the draw of ~ Toase (- ()), we have that for all s 0,
I us y.y
TT a:) Toase (y mm) )
(B) 1m)) )
( | x))
P
B Blog
3log
log (2C / m + cxp(-ss).
Proof of Lemma J.1. Define
T④ |x)
و(35 xx)
X x= B log
B log
Toase (y x))
Tbaso (3// x))
By the Chernoff method, we have that with probability at least - 8. X log(E(cxp(X))) + log(5-1)
Moase (y (x)) ) log
TTV (x)
< | [x)
)]) log(d-1)
log
E
exp
Blog
Toase (2/ xx)
IT |x)
क (v) [x)
log
E (x)
exp B log
B log
Abase (y .x)
Toase |x)
TT(3'/ x))
T(y (r)
Eg to (xx)
E
exp log
3log
+ log(d-)
Tbasa (1// xx)
Tbaso (1 [x)
n ( x²)
TT(y' x))
log
exp 3 log
log
+ log(o
Moasa (1) x))
Tbasa (y/ [x)
Toase(s' [x] 97 '))
T x))
log
+ log(28-1) 1)
Thase (v/ x))
( xx)
43

---

Published as a conference paper at ICLR 2025
As long B & 1, by Jensen's inequality, can bound
(y) xx)
Thase (1/ xz)
99
E Eg of (amesal
Toase (y) x))
TTy x))
TTV x:)
Mbase (1/ 1x) 187
S E Ba
E By-mmanela))
Toase (y) x))
π Tly x)
Tbase (y' (2) π (1/ 27)
18
Cruse/t::tt
which proves the result.
Lemma J.2. Let B E [0, 11. For all models и,, we have
Tasse (y) (
( 2r)
TTV' xt)
Byg /o (cl0)) Blog
B log
O(log (Clog((CCaaaa (Crom//s:8)) 1).
Tbase y
x3
Proof of Lemma J.2. Define
TTy x)) Tbase (y (x)
((l x)) Tbase (y x+)
x =
B log
BBlog
Set l m2: We can bound
E
X
E
T(x² > 17
4 E
I1X fJt
=4
P[X t)
< KM + 4
P > t)t
< 4a4h +4 4
c x-143 dt.
= A²a + 4(k²
+ 31,2 + 6k 6)
0 + +1),
where the third-to-last line uses Lemma J.I.
J.1.2 PROOF OF THEOREM 4.2'
Proof of Theorem 4.2'. For any model II, define ((x) Ex log Toase (y) x)). Let II denote the model returned by the DPO algorithm in Eq. (8). Let Rr denote shorthand for define A (xx y, v.y') r(z. v) r(x,'').
By==,.y-(((ca""==/=()))) and for any r x Define
T3 x)) Tasse (y
r* (xx == log Tbase xx) = 3 log
+ Z(x).
xz)
and let f(x, = B log
*(yl()) mocc m)
By a standard argument (Huang et al., 2024), we have
क E arg max E, (F(x,, w)] 3DkL ( Tbase).
(20)
*X+100)
44

---

Published as a conference paper at ICLR 2025
Therefore for any comparator model x² : : A()) (not necessarily in the model class II), we have
( ( = E [r" (2, y]] - E# fr (x, yr,
B. [fx, y)] (DkL(TT* (-* Tosse) E [F + 3L ( Masse)
+ Ex (x, - f(z, y)1 + 3DKL ( Those) + Rx [2 y) r² (z, (x. 33DKL ( Toase)
v F (r" (a, v) - F(z, v)] + (DKL (T' Tbase)
E4 [(. y) (x, 3 ( Taase)
E mosse A (xx, ". A (xx,
[rr, y, 1/) + RE mouse
Ax, U.,.) A (2,, n/)
3D (IT" Tbase) 3Dkl (f Tbase)
(21)
where the inequality uses Eq. (20). To bound the right-hand side above, we will use the following lemma, which proven in the sequel.
Lemma J.3. For any model and any n O, we have that
E Baree
A - (x,
S C2/2. (Eruuss Toese | (I (I, - (Z, D')
1A" S <n]]]
1/2
S
PP Tasse Toase [| > n1) 1/4
C (log((CConnnno/ log log(Crwao/n3:))
Tossese Toost
Ar'
Using Lemma J.3 to bound the first two terms of Eq. (21), and using the fact that all π E II have C S Oconc and C-um//=88 S Closs, have that
J(m (
< (C.- + Ceooc) 2/22 Bintenettaon | (I. ((a..)"
14 < mn]])
1/2
+ (C.. + Cconc) 1/2 log((ioss)) (P Moaee
|
>
17
IP
bass STuae ||A9| > m))
1/4
+ BBL (TT (base)
(22)
Let us overload notation and write A M,y') = 3 log
le) Musse
(1/ 25) - 3 logg
x(x/1z)) (o'l=))
so that
A and = = - T E II, the definition of ग in Eq. (4) implies that
Σ (A,,,,) - (.,
min rlll
( (AT,,,,1))) - (I., (2.y.v/)EPoor
Σ
(x.g.v")EPeor
Σ (A, - ATO( (
(
Define Ba,p == logg(nC1osssllnn It is immediate that
(x = (..8.v)) 2 T/|109 S Bn
| S Bn S 0.
(E.
From here, Bernstein's 's inequality and union bound implies that with probability least 1 P.
[x AF 11(12 S Bn | S Bn. }
E E ST
B2 log log( (1T
=: S
In particular, if we combine this with Eq. (22) and set = Ba,p- then Lemma J.1 implies that
J(=*) J( S (C.. + Ceone) Estat + (C.. + Ceone) 1/2 1/2 log( (1oss) p²1a 3Dx((T** (aase)
45

---

Published as a conference paper at ICLR 2025
Note that the above bound holds for any 'T" X A()). We define n² by
क (y x)) Tasse (y x x)]l(y E yx
Tbase (x) x))
which can be seen to satisfy C.. I Ceovy S Ccanc and DKL(TT || Tause) & log(C>+) & log( (conc) With this choice, further bound the expression above by
J(x') - J(T) < (Ccone) Estat + (Ceonc) 1/2
) log(( (Cass) p1/4 + , (og(())ne)
Given a desired failure probability p. applying the bound above with p' == P (Estat/ log(C (loss)) then gives
x (Ccone)
Estat + 3 -staat
Finally, we observe that for our choice of n², under the margin condition with parameter y, we have
Thase (y xx)
J(x*) [(a) Exp Ey, log
Tbase (3/ x))
12
Ymargin Bawn Eyrna [I(e' & v1, -7
2 Imargin 6 En [1( x)) S 1- -6}] -
where the first inequality uses Assumption J.2 together with the fact that y E Y (x) with probability 1 over æ ~ y and y (- (-(11 x)). This proves the result.
Proof of Lemma J.3. For any >> O, we can bound
(r - I
BR Musse A' (2,
(2, (
| sn)]]
(2, - (Z. ( W >
E Tosee
For the second term above, we can use Cauchy- to bound
Ar' (W,,, - S0, (x, | ((NN))))-((cuu////////>/// > n
Es Maase
Benszoo Ar (x, - (I, T TT nV A > n))) 1/2
S C2//2
|r' > 1 + Tease Those |A 11) 1/2
S C1/2.
(P (Priee Russe
1/1
Ar (x., y. 8')
E E Trane
+ E Eiowee Thane
$ C1/2_
(P Rassn
A ? Toane Nasse
| > >)))"
1/4 (log(Cras///ss) + log(( (g0n/
where the last inequality follows from Lemma J.2.
Meanwhile, for the first term, for any À > 0 we can bound
E E,,
(x,U.V)) A (E,,,,,')
s 1
C1/2 Bruesstun Ar (x,,),,,'') -3 - / < sm))) 1/2
46

---

Published as a conference paper at ICLR 2025
J.2 PROOF OF THEOREM 4.3 AND THEOREM J.3
In this section prove Theorem 4.3 as well Theorem J.3, the application linear softmax models. For the formal theorem statements, see Theorem J.2 and Theorem J.3 respectively. The section is organized as follows.
Appendix J.2.1 gives necessary background on KL-regularized policy optimization, well as the Sequential Extrapolation Coefficient.
Appendix J.2.2 presents generic guarantee for XPO under general choice of reward function.
Appendix J.2.3 instantiates the result above with the self-reward function r(z, y) == log Tasse (y (x) to prove Theorem 4.3.
Finally, Appendix J.2.4 applies the preceding results to prove Theorem J.3.
J.2.1 BACKGROUND
To begin, give background on KL-regularized policy optimization and the Sequential Extrapolation Coefficient.
KL-regularized policy optimization. Let 3 > 0 be given, and let : X' y | R-Rmaxy Rmax] be an unknown reward function prompt/action pairs. Define a value function Jg over model class II by:
JT( = E. v)] - 3 DKL(P" [
We refer to this as KL-regularized policy optimization objective (we use the term "policy" following the reinforcement learning literature; for our setting, policies correspond to models). Given query access to r, the goal is find ßे E II such that
Ja(TT) J Se
where (V 2) Mhuse exp((xp(p- is the model that maximizes Jg over all models X + A()).
We make use of the following assumptions, as in Xie al. (2024).
Assumption J.3 (Rcalizability). holds that F E II.
Assumption J.4 (Bounded density ratios). For all a E II, (x, v) X x Blgg
m(yl=r) Whane x
V max-
Finally, we require two definitions.
Definition J.1 (Sequential Extrapolation Coefficient for RLHE, (Xie al., 2024)). For a model class II. reward function r, reference model Toase. and parameters T E N and B, X > 0, the Sequential Extrapolation Coefficient is defined as
SEC(II, r. T,B.A, Toase)
(+)
B log
(2(x)) Tame
((x, v) 3log (w'(=) Rosso (v' (x)
+ r(xx 8/) r(x
sup a()) (T)
XV
E(0
Mucsa (y/=] (
(v(())))
r(xx, w) 3 log x (
Thase (v + r(x,
where (E()) denotes expectation over μ4 (- x), and s Toase xx).
Definition J.2. Let e > 0. We say that C Il is a e-net for model class for every स II there exists n' E V such that
T x)
max max SEA DEY
log
E.
<'y
We write (II, c) to denote the size of the smallest c-net for II.
47

---

Published as a conference paper at ICLR 2025
Algorithm 1 Reward-based variant of Exploratory Preference Optimization (Xie et al., 2024)
input: Base model Taas : X + A()), reward function r :: X x y + IR, number of iterations T E N, KL regularization coefficient 8 > 0, optimism coefficient >> 0. Initialize: x(1) +- Thase D(0) <- Ø.
for iteration 1,....7 do
Generate sample: (-:(1) yy()) 7()) via r(()) u4 y(0) ~ x10( 2z(()), gith) ~ Toase (. xz(0).
Update dataset: D(t) +- D((-1) U {(x(), y²)) ())))
Model optimization with global optimism:
((+1) arg min sell
(a
Σ
log(s(y/ x))
Σ
3 Blog
T ( x)
B Blog
(ty x))
(r(x, v) -(x, r(2,
Thase (y) x)
base (3/' x))
(D
return: t arg [ (3(
Can estimate J)(((()) using validation data.
J.2.2 GUARANTEES FOR KL-REGULARIZED POLICY OPTIMIZATION WITH XPO
In this section, we give self-contained guarantees for the XPO algorithm (Algorithm 1). XPO was introduced in Xie al. (2024) for KL-regularized policy optimization in the related setting where the learner only has indirect access to the reward function through preference data (specifically, pairs of actions labeled via Bradley-Ters Terry model). Standard onfline algorithms for this problem, such as DPO, require bounds on concentrability of the model class (see e.g. Eq. (9)). Xie et al. (2024) show that the XPO algorithm avoids this dependence, and instead requires bounded Sequential Extrapolation Coefficient.
Algorithm 1 a variant of the XPO algorithm which is adapted to reward-based feedback (as opposed to preference-based feedback), and Theorem J.1 shows that this algorithm enjoys guarantees similar to those Xie et al. (2024) for this setting. Note that this is not an immediate corollary of the results in Xie et al. (2024), since the sample complexity in the preference-
setting scales with e ((Rmm)) and for our application to sharpening it is important to avoid this dependence. However, our algorithm and analysis only diverge from Xie et al. (2024) in a few places.
Theorem J.1 (Variant of Xie et al. (2024, Theorem 3.1)). Suppose that Assumptions J.3 and J.4 hold. For any T E N, édisc: (0, 1), by setting
B
log (2.22T sawe Tip) Algorithm I
Rim
SEC(nTyT
produces a model से E II such that with probability at least 1 1-pp
SEC(II) log (N (p))
3DKL (+)) mz) J2( JT( S (Rmax + Vmmx))
T
+ Bedisc / SEC(LI)T
where SEC(IT) == SEC(IT, T,,, max: Dbase)
Proof of Theorem J.1. For compactness, we abbreviate SEC(IT): SEC r, T, B, V2 Tbase) From Equation (37) of Xie et al. (2024), we have
Jo( - (0)
T
a
Rmax + Vmax)² 3
SEC((I)) +
3
Vmax
T
E
[Blg (v x)) - - T5(1 (1l x)]
aT'
T
T 1=2
B
T
n (+) (y x)) Rosse (y x))
r (1)' | x))
E mmp
B log
r(x.v) - Bog Toase (v' x2)
+ rlz, v/)
a a(Rmax + V Vmax)22
2T
1=2
w.y (+))) I
where (1)= = 1-1
1 Eise
nt @ Taase denotes the model that, given x E X, samples ~ Unif([t 1))
and then samples y 28 (60 (. and yf Thase x)). For any 2 < & T, define T,(0) II + [0, 20)
48

---

Published as a conference paper at ICLR 2025
by
(x)
E
log (y) 2) -lg (3( x)]
(u.y) Foaan
B
Blog ( x))
TT x))
27
E
rlz, y) Blog
r(x, v/)
a(V 2aVVmxx>> + Rmax) )
Tasse (y) | x)
Toase (3 | x))
Similarly, define
(T)
Σ
B3 (1/ xx) B log (v/ [x)]
(ED)
3
Σ
(8los
x T x
r((,,))) v) Blog TT x)) rr(x,
27
a( a(Vmax + Rmaa)
Thase (y xx)
Mbase (y/ xx)
(ED))
where D(1) the dataset defined iteration of Algorithm 1. By Assumption J.3 we have x3 E II. so enn (x) I O. Moreover by definition, x(() E arg min [(0)
Let V be an Edisc-net over II, of size WIII, Edise). Fix any E V and 2 < < T, and define increments X, = T,000 (T) (x) for 2 S i S I, with the notation fT()(T)) = so that
(T) Ei= X₃. Let F; be the filtration induced by D(i) and define 7/ E[X; Fi-i].
Observe that (t- (t) (T) = Ei Yi. For any note that we can write X; = Y; + Ze where Y, E
[-V Vmax] and Zi E [0, B/aa. By Corollary F.I, it holds with probability at least 1 - (2(2
Σ E Fi
log ( (Tp))
Z₁-
1=
By Hrefding, it holds with probability at least [2 that
1 V max (oog(//////)
Σ Y
Hence, with probability at least PT( we have
(t - (T) 8
log (TTp)
Vmax TT log(2 WTTTp) + +Z00 (T).
With probability least 1 1 this bound holds for all v and 2 < f T. Henceforth condition on this event. Fix any π E II and 2 s T. Since V is an c-net for II, we see by definition of (()) that there some n' E V such that
3
3
L (1)
S Bedisc +
Bedisc (Vmax Rmmx) <
BEaisc
[1
a(V + Rmax) 1
a(Vmax + Rmax
and similarly
(m) S 11)-eedsc (1+ a(Vmax + Rmaxx
B
It follows that, for all 2 2 t T, since (1((1)) O, get
8
3 log w Vmax Tlog(2 Bedise (1t a(Vmax + Rmax)
(t- (t-1)L (T(0)
Hence,
T
Jm(TT) - (1)
3
V
Vmax T
T Σ
Rmax + Vmmaa)² SEC((T +
+
(m((1)
aT
T
t=2
SEC(IT) (T/p))
S (Rmax + Vmax)
+ BEdisc / /SEC(II)T
T
49

---

Published as a conference paper at ICLR 2025
by taking
(2g(2/V(7/p) SEC(II)T
= Rmax + Vmx
Since the output र of Algorithm satisfies क E arg [T Js(x("), the claimed bound on J3(TT}) - (+) is immediate. Finally, observe that by definition of 3
(H x)
ity x))
()((T)) [)( (
r(z, 3) bog
r(æ, y) -llog
Thase (3/ x))
(x.
Thase (3/ x))
T (3) x)
T (3) (x)
3 log r(x, 8)
r(x, y) -Blog
(x.y)
Thase (3/ x))
(xr
Toase (3/ x))
7(y x))
E (2.0)~
3 log
33 33611 x>)
B log
E (a.y)
[exp(r(x, v))] 3 log
E -m
(exp(r(x, + 3DL (f m1
3DKLL (T)))
This completes the proof.
J.2.3 APPLYING XPO TO MAXIMUM-LKKLLHOOO SHARPENING
We now prove Theorem J.2, the formal statement of Theorem 4.3, which applies XPO to maxinum-likelihodd sharpening. This result is straightforward corollary of Theorem J.1 with the reward function (a, 3) := log (y | z). together with the observation that low KL- regularized regret implies sharpness (under Assumption 4.2).
Theorem J.2 (Sharpening via active exploration). There are absolute constants C1.2s CJ.2 so that the following holds. Let c, 5, Tmargin P. E (0, 1) and T E E be given. For base model Tbase. define reward function r(z, y) == log Tbase (y x). Let Rmax 2 1 1 max y log [v)]] Suppose
that Taase satisfies Assumption 4.2 with parameter "ímargin that 3 2 2% 2% 1og(2)))/8), and that there is Edisc E 1) so that
R2 R SEC(LL) (21( Edisc )T/p)
2 CJ.2
e²62,32
and
cō
Edisc I C1.2
/ /ECCLLI)T
where SEC(IT) = r,,,,,, T,3, R2 Thase). Also suppose that T E Il where Tz(y xx) x
1+8 base
(y x))
Then applying Algorithm 1 with base model Wbasa, reward function iteration count T. regularization
3, and optimism parameter a = probability at least P.
B
Iog(22 (T/88 yields model मे E II such that with SEC(II)T
Roxe
( (x) < < 21-056.
The total sample complexity is
m = δ
R2 SEC(LI) Log(N (1I,, edisc) log (121(11))))) max
2 mmrrgin 2282
Proof of Theorem J.2. By definition of r, we have |r(z, y)1 & Rmax for all x, y. By assumption, Assumption J.3 is satisfied, and by definition of Rmaxs Assumption 4.5 is satisfied with parameter
50

---

Published as a conference paper at ICLR 2025
V Rmax I Rmax- It follows from Theorem J.1 that with probability at least p. the output Algorithm satisfies
SEC( (og( (2N Edisc )T/p)
DDKL m3) & (Rmax Vmax)
T
+ Bedisc / (EC(LI)
By choice of T and <disc. so long as CJ.2 > O is chosen to be a sufficiently large constant and
c1.2 is chosen be a sufficiently small constant, we have 3DKL
i m3 S 12 Sed, so by e.g.
Equation (16) Sason & Verdú (2016), D ā. (). S c6)(1
For any x E X' and y E.y y" (a)), by Assumption 4.2 and definition of m3 we have maX (T(VIx)
1+8 1
maxxyyy Thase (y at)
x))
Thase (y' x))
2
2 + Ymargin) )
1+8
2 e Tmoggnn (28)
where the final inequality is by the assumption on 3 in the theorem statement. Therefore
क 5 (x)
21
Σ
x) 2 2
(x)
Now for any x, we lower bound
(+ 2), x), x)) 2 / Tyy (x) x) v 11 1z (x) 2
I[ x) 11-53.
12
Hence,
12
P PaNu (Tt (x) x) <
8|
E Expn Dit( (f(- 1z)
12
D (R,
<
as claimed.
J.2.4 APPLICATION: LINEAR SOFTMAX MODELS
In this section we apply Theorem 4.3 to the class of linear softmax models, proving Theorem J.3. This demonstrates that Algorithm can achieve an exponential improvement in sample complexity compared to SFT-Sharpening.
Definition J.3 (Linear softmax model). Let E N be given, and let Φ X + Rd be a feature map with (,(x,00 2)1 I for all x. y. Let Zzero X A()) be the uniform model Tzera x)) = 13/1
and let B 2 1. 15 We consider the linear softmax model class l1 := {mo 0 E 224,0012 S B}
where no X > A(Y) is defined by
Toly x) x (y) x)) exp((x(x, 2))
Theorem J.3. Let e, 8, "margin P E (0,1) be given. Suppose that Toase nz. E Il for some Or Rdd with ||0*1|2 < "Iangnn 7170- Also, suppose that Thase satisfies Assumption 4.2 with parameter "imargin- Then Algorithu with base model Tease, reward function r(x. y) log Thase (x, v), regularization parameter 3 == "imargin/ (2lrgnn/22lo222)22
and optimism parameter doug BdTT (c))) returns (c, -hsharpnne model with probability at d' log(T)
(TT) B+log( 31) V
B
least - p. and has sample complexity
(o 8-1 mmariin B, log (og((())))
We the notation zeroo highlight the fact that Tzzro Fo for 0
51

---

Published as a conference paper at ICLR 2025
Before proving the result, unpack the conditions. Theorem J.3 requires the base model Thase to lie in the model class and also satisfy the margin condition (Assumption 4.2). For any constant c, > O, the sharpening algorithm then succeeds with sample complexity poly(d, Ymargin B, log(())))). These conditions are non-vacuous; in fact, there are fairly natural examples for which non-exploratory algorithm such as SFT-Sharpening require sample complexity exp(It(d)), whereas all of the above parameters poly(d). The following is such example.
Example J.1 (Separation between RLHF-Sharpening and SFT-Sharpening), Set = {xr and let Y' C Rdd be a /4ppkakin of the unit sphere in R of cardinality (e(d)) Define : X' x - Re
by Φ(r y) == and let B = Cd log d for an absolute constant C' > O. Fix any y² E y and define Thase .g. 11 by 0 := y² Then for any y + y", we have (y, y²) S 1 2211.
Toase (y" x) exp((y (y - y. y -xp(p()))= = 1
Tuss y x)
Thus, Tbase satisfies Assumption 4.2 with Vmarrgin ((1). Moreover, |0+112
Timargn B
3 3ogg(2]] (/))
for any = 1/poly(d) (d), so long as C' is sufficiently large constant. It follows from Theorem J.3 that Algorithm I computes an (e, -shaapeeed model with sample complexity poly(e 1000----1011 However, since Taase (8* x) S Taase (y z) exp((2 for all y E V, it is clear that
Ccov IE
((DI)) exp(9(d))-
Tbase ( (3)
x:)
Thase (y"
Thus, the sample complexity guarantee for SFT SFT-Sharpening in Theorem 4.1 will incur exponential dependence on d in the sample complexity. is straightforward check that this dependence is real for SFT-Sharpening and not just an artifact of the analysis, since the model that SFT- SFT-Sharpening trying to learn (via MLE) will itself not be sharp in this example, unless exp()) samples are drawn per prompt.
We now proceed to the proof of Theorem J.3, which requires the following bounds on the covering number and the Sequential Extrapolation Coefficient of II
Lemma J.4. Let Cdisc O. Then T has an Cdise-net of size (6B/
Proof of Lemma J.4. By a standard packing argument, there is a set {81..... such that for every 0 E IRd with [|0]|2 & B there is some i E [N] with 1|0; 011 S Edisc/2. /2. Now for any X and y V.
.......,0 ONN } of size (6. cdise) d
T x) log exp((0(x,,)) 0), + log (('')))) exp((ó(x' 0.)) log To. (y x) exp((o(z; y), 0,))
B w Time (xp((((z', ,'','',' y'), 0)) E ((a yaa (exp( 1)) 0) exp( (xp(((((', v'), 0)) v))
= (0(x, v), 0,) + +lo
The first term is bounded by edisc/2 in magnitude. In the second term, we have exp((0(x', x 3/) 0: 0)) E [exp(_Edisc/ 2)) exp(edis:/2)), so the ratio of expectations lies in texp(-Ean) 2), exp(edisc/2) as well, and so the log-ratio lies in (diss In all, we get [)())))
log no, [x]
Edisc. Thus, {To,,-.., ] is nei for TI.
Lemma J.5. Letr: X + I--Rmaxs Rmax] be reward function and let T E and 0. If 2 B2 R then for any x² E &1I,B.
SEC
S dooogT 1).
Proof of Lemma J.S. Fix (1)
(T) E NT By definition, there some (11) ,..., ((T) Rd
with ||0t)||2 B and
n ( x) x (y x) exp((((x, v). 0(01))
for all E [T] and (x,y) E X x V. Similarly, there is some E Rd with ||0*1/2 I B and
(y) (r) Tzero(y) (y ex)e((((((;; v),
52

---

Published as a conference paper at ICLR 2025
Define Ø: X x y > Ro+ by ((x,)) == (0(x,)).
r(a.)) Ria
and define ((t) [3(0(t) 0¹), -Rmaxl
Then for any E [2'] we have
(ulx) E(4) [ log ("((a)) r(x, y) log
(''w) (000mm))
r(x,
e/]] }²
A E R(()
( log x((() r((,,,))) v) Blog =0(rll)
+ r((,,)')
(a(a,, y) - -,xx 3/) (()))) 2
B(0)
A E E()) (fo(z. 3) ((,,8") B(1)))
(()))
A Σ 2-1
11= (0i)) (0()
E00
where for each [T] we have defined Σ(0 E(() (a(a, ( v) -(,, - {))
Observe that |0000 < 4,2 B + R S A by assumption on A. Therefore,
(10) ( (())
(0(1)) (())
A Σ 1=1 (0() (()
A - Ei= (oit) M000)
(0(1) )(1)))
(T(o)T 11+1==1
E()
0
-1/2
-1/2
(1a+
[-1
1-1
S Amax
Σ
[(1)
Ia+
Σ
i=1
i=1
t-1 la + Σ
-1/2
1-1 Σ
-1/2
< T
20
21
l1 -
(
1=1
1=1
f-1
-1
= T
la +
i=1
Observe that Tr(E(0)= < max |, 1l H 1. Hence by Lemma F.2, we have
( Blog x(1) (v(z)) r(x,,))) v) 3 log (g'12)) (*((()) + rr 8²)
Σ 1=1
B(0) (
(Blog
r(x,y) Blog -0 + r(x; 1/) ) 2
[))))
T
1-1
Tr
la Σ
Σ(0
< dlog(T +).
Since n ..... n (T) E IT were arbitrary, this completes the proof.
The proof is now immediate from Theorem J.2 and the above lemmas.
Proof of Theorem J.3. By the assumption on 0* and choice of 3, the model #3 defined by
x)) I+0- satisfies oÿ ((1-8-110 E HI By Lemma J.4, we have (III,, Edisc) < (6B B0B/eaish edscc) Take Rmax = / + (2B log [)1])= We know that r(x,8) y) == log Thase x) satisfies |r(x,y) < 2B + log | for all æ, y. By Lemma J.5, we therefore get that SEC r, T, B, Rhaxi Abase) S dlog(T +1. Substituting these bounds into
(3 z) x Tbase (y
Theorem J.2 yields the claimed result.
53


Reviews:
[{"review_id": "wFDqIRY0JU", "reviewer": "Reviewer_6RKv", "summary": "This paper introduces a theoretical framework for analyzing language model self-improvement through the lens of \"sharpening\"—defined as the process of tilting a model's probability mass toward sequences with high self-reward (which crucially does not rely on any external information). The paper focuses mostly on the case where self-reward = log π(y|x), which has been used in previous self-improvement literature. It also focuses mostly on sharpening via self-training (as opposed to sharpening via only inference-time computation), which can be viewed as amortizing expensive inference-time computation/sharpening. With this in mind, the authors present two families of algorithms for sharpening via self-training: SFT-sharpening and RLHF-sharpening. SFT-sharpening uses Best-of-N with self-reward to generate a new SFT dataset to fine-tune the model, while RLHF-sharpening uses RLHF with self-reward as the reward function for preference scoring (the paper looks at DPO-style algorithms specifically). These families of algorithms come from previous self-improvement literature.\n\nTo analyze the sample complexity of these algorithm families, the authors introduce a \"sample-and-evaluate\" framework where sample complexity is measured in terms of m = n * N sample-and-evaluate queries (n sampled prompts with N generations sampled per prompt). They prove a lower bound on the sample complexity for any sharpening algorithm. Then, they prove that both SFT- and RLHF-sharpening can learn sharpened models under the maximum likelihood objective (ie, maximizing self-reward), and they prove the sample complexity of each (with certain assumptions about model coverage). Finally, they demonstrate that adding online exploration to RLHF-sharpening can replace the dependence of sample complexity on model coverage to a dependency on the complexity of exploration.", "questions": "- What should experimentalists take away from this work? For example, researchers working on inference-time computation scaling, or those doing self-training. Can this work help them in some way?\n- Do the authors see this work as being helpful for investigations into scaling laws for self-improvement? If so, how?\n- In the RLHF-sharpening formulation, my understanding is that the KL-term ensures that the finetuned policy stays close to the base-policy, which is required since self-reward is defined using the base-policy (i.e., to keep generations in-distribution for the reward function). Is this correct? Furthermore, I am wondering whether the self-reward can be defined using the non-stationary policy that is being fine-tuned. What would be the effect of this change?\n- Can you provide a more detailed explanation on the meaning of the coverage coefficient and how it can be problem dependent?\n- [The questions mentioned in \"Weaknesses\"]", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper is well written and easy to follow, with a detailed appendix containing proofs and additional results like guarantees for purely inference-time sharpening.\n- The work is relevant to the scope of ICLR and introduces a novel theoretical perspective and statistical framework to analyze language model self-improvement algorithms. It provides a much needed theoretical understanding of recently popularized self-improvement methods for language models.\n- The SFT-sharpening and RLHF-sharpening algorithm families are widely used in self-improvement literature, making the theoretical results immediately relevant and valuable as a foundation for future work.\n- The result showing that using online exploration with RLHF-sharpening shifts dependency from model coverage to complexity of exploration is a particularly interesting and significant result. Future works can analyze how different online exploration strategies affect sample complexity.\n- The choice to focus on log π(y|x) as self-reward is simple yet well-motivated given its use in prior self-improvement literature. The framework established by the authors provides a foundation for future work to analyze the effect of using other self-reward functions on sharpening guarantees and sample complexity.", "weaknesses": "- On lines 187 and 199, the paper states that the corresponding algorithm scheme converges to a sharpened model / sharpening objective in the limit. However, it does not seem to provide a justification or proof for these two statements (please let me know if I have missed it).\n- Although focusing on log-probability as self-reward is justified, the paper would benefit from including a survey of other self-reward functions used in prior self-improvement works. This context would provide valuable guidance for others to build on the sharpening perspective by looking at alternative self-rewards.\n- While the paper does mention the prior literature on self-distillation, it would benefit from a more complete summary of this prior line of work, including key findings and making it very clear how this work is different/novel.\n- While emperical results are shown for inference-time sharpening, there are no experiments for self-training methods (SFT-sharpening, RLHF-sharpening) which are the main focus of the theoretical analysis. The paper would greatly benefit from including experimental results for SFT-sharpening and/or RLHF-sharpening, **with a focus on whether the theoretical results can be used to correctly predict something about the emperical results.** For example, can the theoretical results be used to predict the difference between running an RLHF-sharpening setup with and without online exploration? Or between SFT- and RLHF-sharpening? I would be curious to hear the authors' views on this.\n- The conclusion focuses on future work but lacks a summary of the paper's key contributions and findings. The final manuscript would benefit from a summary of key takeaways in the conclusion. (No need to include it now in the rebuttal.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4JZnnJ1Gr1", "reviewer": "Reviewer_6usC", "summary": "The paper provides an answer to why self-improvement methods can improve model performance even if they do not increase the information the mode has access to.\nIt defines sharpening as the greedification of a model, i.e. outputting its most likely answer, which is typically hard to compute.\nSharpening can be applied at inference time (e.g. with Best of N) or at training time, and the paper identifies self-improvement as a training-time sharpening method which allows to replace or amortize inference-time sharpening.\nIt defines a framework for theoretically evaluating the sample complexity of sharpening methods and provides results for the sample complexity of SFT and RLHF sharpening/self-improvement (using the model's likelihood as a filter or a reward), giving sample complexity bounds for each method to achieve sharpening at training time.", "questions": "- Could the authors elaborate on their choice of REBEL and XPO as the algorithms studied?\n- To what extent are the results in the paper limited to these algorithms?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "### Contribution\n- The identification of self-improvement methods as sharpening methods that trade training time for inference-time search is novel and important in the discussion of self-improvement methods.\n- The sample complexity results provided for SFT-Sharpening and RLHF-Sharpening are novel and relevant to the community. The results on adding exploration to RLHF methods are relevant to the online vs offline discussion of post-training.\n- The additional results in the Appendix, such as adaptive sampling for SFT-Sharpening to improve its sampling complexity, are appreciated and can drive the design of novel practical algorithms.\n\n### Soundness \n- The sharpening objective and definition and the sample-and-evaluate framework are well-motivated and provide results that are relevant to practical settings.\n- The assumptions made in the paper seem reasonable.\n\n### Presentation\n- The paper is very well written and easy to follow. The claims and their associated evidence/results are easy to identify.\n- The remarks discussing the assumptions in depth, such as Remark 4.1, are well appreciated.", "weaknesses": "### Contribution:\n- Line 256: It's appreciated and essential that the paragraph \"Empirical validation of maximum-likelihood sharpening\" verifies that sharpening provides downstream task improvement; however, in my view, this is a fairly known fact which could be presented in a more concise way, or acknowledged as a general fact.\n- Definition 3.2: the generation-verification operation seems a bit restricted, but in a self-improvement context, this seems enough to me.\n- The results seem limited to the specific algorithms chosen IN RLHF-sharpening mainly REBEL and XPO. \n\n### Presentation:\n- It can be misunderstood from the paper that self-improvement methods should exclusively be seen as sharpening methods, from the strong questions raised in the abstract and the introduction. I suggest rephrasing those as motivation to see self-improvement as sharpening.\n- Line 194 typo: the expectation's long definition should be over $\\pi$ instead of $\\pi_{base}$.\n- Proposition 3.1 introduces an important result, which is then not discussed. The transition to the next section is too abrupt.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BxxXvCQOQD", "reviewer": "Reviewer_JzdL", "summary": "This paper analyses self-improvement in language models (LLMs) through a mechanism called \"sharpening.\" The authors focus on self-improvement where log-probabilities (of sequences of tokens) are used as the reward signal. They analyze two algorithms: SFT-Sharpening, which is optimal under sufficient model coverage, and RLHF-Sharpening, which can surpass SFT by utilizing online exploration to overcome coverage limitations.", "questions": "While theoretically sound, can your work provide any guidelines for the practical deployment of sharpening techniques?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work develops a theoretical framework for studying and understanding self-improvement. \nThey compare two approaches, SFT-Sharpening and RLHF-Sharpening, and prove their convergence.", "weaknesses": "1. While the authors empirically show there is useful signal in Best-of-N Sharpening (by sampling at inference), they do not empirically verify that SFT or RLHF training with this signal works.\n2. The authors focus their analysis on the maximum likelihood self-reward. While this objective is simple, it has not been empirically explored a lot in self-improvement literature (as the authors themselves note).\n3. The sentence in the abstract \"*Motivated by the observation that language models are often better at verifying response quality than they are at generating correct responses*\" is misleading in the context of this paper. Here, the reward is not assigned by asking the model to verify or critique its own solutions but by having access the log-probabilities of generated solutions. In general (relevant for Introduction and Related Work sections), claims of self-improvement in LLMs should be handled with more nuance.  While there are papers that LLMs can self-improve without external feedback, there is also recent evidence of the contrary:\n    -  Ryo Kamoi, Yusen Zhang, Nan Zhang, Jiawei Han, and Rui Zhang. 2024. *When can LLMs actually correct their own mistakes?\nA critical survey of self-correction of LLMs*\n    -  Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. 2024. *On the self-verification limitations of large language models on reasoning and planning tasks*\n    -  Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. 2023. *Large language models cannot self-correct reasoning yet.*\n    -  Kaya Stechly, Matthew Marquez, and Subbarao Kambhampati. 2023. *Gpt-4 doesn’t know it’s wrong: An analysis of iterative prompting for reasoning problems.*\n    -  Karthik Valmeekam, Matthew Marquez, and Subbarao Kambhampati. 2023. *Can large language models really improve by self-critiquing their own plans?*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oy7uHgdzV8", "reviewer": "Reviewer_ABNY", "summary": "This paper proposes a theoretical framework to understand self-improvement. The authors define the sharpening as the best sequence according to the model likelihood which is different than greedy decoding or temperature sampling (the theory implies greedy decoding only covers the best sequence under some constraints). They further define self-improvement via SFT and RLHF using BoN and DPO, respectively. The authors show sample complexity bounds for SFT and RLHF using a model and data dependent coverage and concentrability coefficients. For example, sample complexity for SFT is proportional to coverage coefficient and logarithmically scales with size of the policy class. Finally, by adding exploration, the dependence on the coverage coefficient is replaced by sequential exploration coefficient.", "questions": "Please see above for specific questions.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Update: Authors' rebuttal addressed my concerns. I increased my score accordingly.\n\nThe proposed theoretical framework captures a very significant class of post-training improvements, ranging from SFT to RLHF. In particular, it covers BoN and DPO that are two very popular inference-time and post-training methods. The paper is also easy to follow.", "weaknesses": "My main concern is the lack of implications of the theoretical results for practical use.\n\n1. While the theory covers many popular methods, such as BoN and DPO, there is not much connection to what this theory implies in practice.\n\nA. For example, what predictions does it make about BoN, can we choose “N” based on your theory?\n\nB. What is the minimal experimental setup to cover both SFT and RLHF?\n\nC. How should we interpret Figure-1 based on your theory? Such as, would convergence rate of BoN be explained by your method?\n\n2. While I understand that using the same context “x” for both policy and reward function is meaningful, in practice it is generally different. Can you discuss if an extension of your theory explains the sample complexity when using different contexts that are related by a function? In euclidean space, this could simply be defined as a bound on the distance between two context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)