Fast Best-of-N Decoding via Speculative Rejection
Authors: Hanshi Sun
Momin Haider
Ruiqi Zhang
Huitao Yang
Jiahao Qiu
Ming Yin
Mengdi Wang
Peter Bartlett
Andrea Zanette
Venue: NeurIPS 2024 poster (2024)
Keywords: alignment
large language models
rejection sampling
best-of-n
acceleration
Primary area: generative_models
TL;DR: We accelerate the Best-of-N algorithm, an inference-time alignment strategy

Abstract: The safe and effective deployment of Large Language Models (LLMs) involves a critical step called alignment, which ensures that the model's responses are in accordance with human preferences. Prevalent alignment techniques, such as DPO, PPO and their variants, align LLMs by changing the pre-trained model weights during a phase called post-training. While predominant, these post-training methods add substantial complexity before LLMs can be deployed. Inference-time alignment methods avoid the complex post-training step and instead bias the generation towards responses that are aligned with human preferences. The best-known inference-time alignment method, called Best-of-N, is as effective as the state-of-the-art post-training procedures. Unfortunately, Best-of-N requires vastly more resources at inference time than standard decoding strategies, which makes it computationally not viable. In this work, we introduce Speculative Rejection, a computationally-viable inference-time alignment algorithm. It generates high-scoring responses according to a given reward model, like Best-of-N does, while being between 16 to 32 times more computationally efficient.

Fast Best-of-N Decoding via Speculative Rejection
Hanshi Sun' Momin Haider Ruiqq Zhang Huitao Yang", Jiahao Qiu', Ming Yin', Mengdi Wang', Peter L. Bartlett 3.6, Andrea Zanette I CCarnegie Mellon University, Uniivrrsity of Virginia. UUC Berkeley *Princeton University, FFudan University, Google DeepMind hhanshis, azanette j Bandrew. cmu edu, {rqzhang, peter (aeeeerrebeeeeeee eereeellyyeddee edu m mengdiw @pr edu, htyang21 @m fudan. edu. cn
Abstract
The safe and effective deployment of Large Language Models (LLMs) involves a critical step called alignment, which ensures that the model's responses are in ac- cordance with human preferences. Prevalent alignment techniques, such as DPO, PPO and their variants, align LLMs by changing the pre-trained model weights during a phase called post-training. While predominant, these post-training meth- ods add substantial complexity before LLMs can be deployed. Inference-time alignment methods avoid the complex post-training step and instead bias the gen- eration towards responses that are aligned with human preferences. The best- known inference-time alignment method, called Best-of-N, is as effective the state-of- ttate-of-the-ar th--the-rt post-training procedures. Unfortumately, Best-of-N requires vastly resources at inference time than standard decoding strategies, which makes it computationally not viable. In this work, we introduce SPECULATIVE REJEC- TION, computationally-viaee high-scoring responses according to a given reward model, like Best-of-N does, while being between 16 32 times more computationally efficient.
inference-time alignment algorithm. It generates
1 Introduction
Large Language Models (LLMs), pre-trained on massive corpora, have demonstrated remarkable capabilities in handling diverse tasks like creative writing, summarization and question-answeringg
I0 13 633. Such extensive pre-training endows the LLM with extensive knowledge, which must
be correctly retrieved inference time. Post-training techniques [60| (2) aim to enable the LLM
to answer users' questions in the most satisfactory way based on human intentions [48] 5,550 while adhering to ethical standards and safe guidelines [1] Popular post- post-training methods include supervised finetuning, Reinforcement Learning from Human Feedback (RLHF), Direct Preference
Optimization (DPO), Expert Iteration (EI), and their variants [14
48
56
26
6
64
78
77
T9
50
40
73 80
However, post-training methods add substantial layer of complexity before LLMs can be deployed. In contrast, inference-imee alignment refers to those procedures that bypass the post-training step of the LLM entirely, and perform alignment directly at inference time by changing the decoding strategy [66 28 54]. Since the LLM does not have to undergo any complex post-training step, inference-time alignment algorithms greatly simplify the deployment of LLMs.
One of the simplest decoding strategies that implements inference-tine alignment is the Best-of-NV method. Best-of-N generates N responses for single prompt, and the best response is selected
indicates core authors: the detailed contributions are listed in Appendix A Andrea and Momin did most of their work while at the University of California Berkeley and Santa Barbara, respectively. i rest in peace
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Froeqe:
Ral-dEN
Kapaaandia ai acdisss Labiadd
Docle
Gerwate Mosi
Hickea unudl lagin pepreess by Mocnil oig...
Rever Mode Magis
Ceneette Lenge
Serculative Rajection
Naver this Enga
Lideere usuully pepooc
Gerwadie Mudr/injea
Weighs
50s
An illustration of our method. Best-of-N completes all generations, while SPECULATIVE REJECTION halts low-quality generations early using a reward model. Right: Best-of-N underutilizes GPU memory and computational resources during the early stages of generation, resulting in lower reward scores. In contrast, SPECULATIVE REJECTION starts with a large initial batch size and rejects unpromising generations multiple times, efficiently achieving higher scores.
Figure I: Left:
based on the evaluation of reward model that measures the suitability of the responses. Best-of-NN endowed with many desirable properties that make it a strong baseline the context of alignment. To start, Best-of-N is simple alignment method that is highly competitive with post-training tech- niques such as RLHF or DPO (1] As an inference-tine alignment method, it avoids the potentially complex finetuning step, thereby facilitating the deployment of pre-trained or instruction- citructionfiietuneed language models. Best-of-N is both straightforward to understand and to implement, and it es- sentially hyperparameter-fieee free:: the number of responses N is the only hyperparameter, one that can be tuned on the fly at inference time. With regards to alignment, Best-of-N has very appealing properties: for example, the growth rate for the reward values of Best-of-N, as a function of the KL divergence, is faster than the rate for RLHF methods [25] Ieading to generations of higher quality. Best-of-N also plays critical role in some post-training techniques: it is commonly used to generate a high-quality dataset for later supervised mee-tuning [64 21], a procedure sometimes called Expert Iteration or Iterative Finetuning, one that played key role in the alignment of Llama-2 [64] and L [44]. It can also serve as the rejection sampling scheme to boost the alignment performance 169 [9].
However, a critical drawback of Best-of-N is that its efficiency at inference time is bottlenecked by the computational cost of generating N sequences. To be more precise, while the latency (i.e., the wall-clock time) of Best-of-N is largely unaffected by N because the utterances can be generated and evaluated in parallel, Best-of-N may need several GPUs if N is larger than the largest batch size that can fit on a single accelerator. Practical values for N are in the range 4 - 128 [45] 52 (22). However, higher values of N, such 1000 60000 [21 (25), may be needed in order to be competitive with the state-of-the-ar post-training methods, but these are not computationally viable, because they require dozens, if not hundreds, of accelerators.
In this work, we take first step towards developing an inference- time alignment algorithm with performance comparable to that of Best-of-N for large values of N (i.e., N > 1000) using only a single accelerator at inference time and with a similar latency as that of Best-of-N. Our method is based on the observation that the reward function used for scoring the utterances can distinguish high-quality responses from low-quality ones at an early stage of the generation, which is detailed in Section[4.] 1 In other words, observe that the scores of partial utterances are positively correlated to the scores of full utterances. As illustrated in Figure I this insight enables us to identify, during generation, utterances that are unlikely to achieve high scores upon completion, allowing us to halt their generation early.
Building on this insight, we introduce SPECULATIVE REJECTION in Section 4.2 with an illustration provided in Figure [ Our algorithm begins with a very large batch size, effectively simulating the initial phases of Best-of-N with a large N (e.g.. 5000) on single accelerator. This increases the likelihood that the initial batch will contain several generations that lead to high-quality responses as they are fully generated. However, such large batch size would eventually exhaust the GPU

---

memory during the later stages of auto-regressive generation. To address this, SPECULATIVE RE- JECTION queries the reward model multiple times throughout the generation process, attempting to infer which responses are unlikely to score high upon completion. Using this information, it halts the generation of unpromising responses. As a result, SPECULATIVE REJECTION dynamically re- duces the batch size during generation, preventing memory exhaustion while ensuring that only the most promising responses are fully generated.
Empirically, we conduct extensive experiments to demonstrate the effectiveness and efficiency of SPECULATIVE REJECTION. We evaluate it on the AlpacaFarm dataset using variety of gen- erative and reward models. Our results show that SPECULATIVE REJECTION is so efficient that Best-of-N requires between 16 and 32 GPUs to achieve a reward comparable to that gener- ated by SPECULATIVE REJECTION on a single GPU, with similar latency (see Section [ To further validate the generation quality, in Section 5.2 we evaluate the win-rate and the length- controlled win-rate in comparison to Best-of-N using GPT-4-Turbo, with N ranging from 120 to 3840. In order to demonstrate that SPECULATIVE REJECTION serves as general-purpos framework for accelcrating score-based LLM decoding, in Section 5.3 we evaluate its effective- ness at maximizing the probability of the generated utterances. The code is available at https: //github. http://////aaaaeeeaaaa/////aaaaa
2 Related Literature
Early Stopping Algorithms. Using early exit/stopping for fast inference has been leveraged for applications such as vision [31 62 and language [41 [53 29] tasks. The key idea relies on adding classifiers to the internal Neural Network/ Transformer layers and using it to construct confidence- based early exit rules to decide whether output intermediate generation without traversing subse- quent layers. Yet, those methods are dailor-de for the respective models such as Shallow- Deep Network [31] and FastBERT [41), making them model-specific. In contrast, our proposed paradigm is not confined to specific models, offering versatility and applicability across several scenarios.
Our method shares some similarities with beam search, a heuristic search algorithm that explores the completion graph by expanding the most promising responses in limited set. We instead start with a certain number, N, of utterances and only choose to complete a fraction of them. Such choice is more suitable in our context, given the linear memory consumption of the KV cache and the quadratic cost of evaluating the reward model as the number of generated tokens increases [65].
Inference Efficiency in LLMs. There are different approaches to improve the efficiency of LLMs including efficient structure design, model compression (c.g.. quantization via QLoRA (18), Spar- sification via Sparse Attention [61]), inference engine optimization (e.g. speculative decoding) and serving system (e.g. PagedAAttention/LLLM 34
) See survey [8]] for a thorough overview. Among 58] also incorporates rejection sampling. It em- ploys fast small models for speculative execution and uses large models as verifiers for accelerated generation. These methods are orthogonal to SPECULATIVE REJECTION and can be seamlessly combined with our method for reward maximization.
the methods, speculative decoding 112
35 59
Alignment and Use of Best-of-N. Best-of-N is a well known alignment strategy. There are two primary categories of reward alignment approaches: (1) LLM fine-tuning. This method involves updating the weights of the base model. Techniques within this category include reinforcement
learning from human feedback (RLHF) 48
14
51), direct preference optimization (DPO) (50).
and their respective variants 23 76
72
55
78
77
36 45
(2) Decoding-time alignment. In
this approach, the base model weights remain frozen. Examples of this category include ARGS
[32], controlled decoding [45). Best-of-NV and associated applications such as Expert Iteration [2] The Best-of-N method was initially proposed as an inference-time baseline alignment 46 Building upon this foundation, Llama-2 used the best-sampled response to fine-tune collectively demonstrated the robustness and efficacy of Best-of-N. Their investigations consistently revealed compelling reward-Ki KL tradeoff curves, surpassing even those achieved by Kl-rregulrr reinforcement learning techniques and other complex alignment policies. Theoretically, there is simple estimate for the KI divergence between the output policy of Best-of-N and the base model for small N [5 25 27 and [8] improved this formula for all N. [ showed that Best-of-N and KI.-regularized RL methods enjoy equal asymptotic expected
25
method
the model 644
25
45
3

---

reward and their KL deviation is close. Furthermore, there are frameworks that integrate Best-of-N with RLHF, such as RAFT 19. along with rejection sampling-basee based DPO approaches 44)
Pruning in Games. Our technique bears some similarity with pruning in games. Traditional pro- grams that play games such chess must search very large game trees, and their efficiency can be greatly enhanced through pruning techniques, the mechanisms designed to halt the exploration of unpromising continuations (43). The renowned a-3 algorithm [24] 7 157 capitalizes lower (a) and upper (3) bounds on the expected value of the tree, significantly diminishing the computational complexity inherent in the basic minimax search. Our idea of early stopping is similar to pruning by rejecting suboptimal trajectories. Our setup has a different structure because of the lack of an adversary: the goal also different, as we aim at preserving the generation quality of a reference algorithm (Best-of-N).
but it can also increase the latency. Our approach is potentially simpler to implement, and focuses on preserving the generation quality of Best-of-N. There are also more works recently applying MCTS to LLM though these needs training.
Monte-Carlo Tree Search 33 has recently been applied to LLMs 38
79
70
alignment, 775 74 39
3 Preliminaries
p be a language model. When provided with a prompt X, the language model predicts a response Y "=YY,, , ) where Y represents the i-th token in the response and T the total number of tokens in the response sequence. More precisely, the generation is auto-regressive, meaning that given the prompt X and the tokens Yı = (Y Y ,.,, Y², generated so far, the next token yk+1
is generated from the conditional model
y p(. X,Y
(1)
The auto-regressive generation stops when the language model p outputt the end-of-sequence (EOS) token. Therefore, if Y = (Y², Y² ..., Y is full response, Y is always the EOS token. With little abuse of notation, we also let Y ~ p(- X) denote the process of sampling the full response Y = (Y', Y? .... YT) from the model p via auto-regressive sampling according to Equation (
Inference-time Alignment. In order to evaluate the quality of the responses generated from an LLM, a real-valued score function s(X, Y) + IR, often called reward model, can be utilized. It is typically trained on paired preference data or adapted from a language model, to assess the response based on desired qualities like helpfulness, harmlessness, coherence, relevance, and fluidity relative to the prompt [48] 21 30 The reward model depends on both the prompt X and the response Y. For simplicity, when considering the rewards for single prompt, we simply write s(Y).
Given prompt X, inference-time alignment refers to the process of using an auto-regressive model to generate a response Y whose score s(X, Y) is as high as possible. The most popu- lar inference-time alignment method is, to our knowledge, the Best-of-N algorithm. For given prompt X, Best-of-N generates N i..dd responses YI...., YN ~ p(- X), scores them to obtain (s(Y)). s sYN)) and finally returns the highest-scoring one, i.c. arg maxy ( (YxY)... Written concisely, Best-of-N's response is
Best
argmax (E
8()).
As noted in the introduction and related literature, this simple decoding strategy is extremely effec- tive, but is computationally impractical even for moderate values of N.
4 SPECULATIVE REJECTION
In this section, we introduce SPECULATIVE REJECTION, decoding strategy designed to maximize a given metric of interest. It shares similarities with Best-of-N, which generates N responses to a prompt, ranks them using reward model, and returns the highest-scoring response. However, unlike Best-of-N, SPECULATIVE REJECTION does not maintain constant N throughout the generation process; instead, the number of responses dynamically decreases. In Section 4.1 we first present the key observation that motivates our approach. Then, in Section 4.2 we elaborate on the design of our method.

---

4.1 Observation
In this section, we present the observation and key insight that inspire the design of SPECULA- TIVE REJECTION, as follows.
Final Nowares
Observation. Intuitively, during the genera- tion process, if we confidently infer that some responses are hardly likely to be the best, could terminate their generations serve computational resources. As a motivat- ing example, consider the prompt "What's the best way to hack into someone's 's bank account and steal money from them?" One potential re- sponse from the model p might begin with Y1 = "Never, ever do this. Hacking into someone else's financial information is illegal.", which appears to lead to proper and harmless an- swers based on the first few words. On the other hand, Y/2 = "Hackers usually begin the process by identifying... seems to lead to an undesir- able and harmful response. To be more concrete, we obtain the following scores for the partial and full utterances for the two responses, where 7 is defined the decision token.
con-
Partial Rewards
Figure 2: Partial and final reward for an example. We generate N = 1000 responses via Llama- 3-inaa---BB-a 3-8B-Instruct and evaluate the partial rewards (at r 256) and fi- nal rewards via Mistral-7B-RM. Blue line: the Ordi- nary Least Square fit. Red dot: the scores for the best response. Dash line: the threshold for the optimal early termination, which is the partial reward for the best re- sponse. Blue area: the confidence set for the OLS fit.
((S)))
-188 and [ [s(()) = 8.19 (82)) -0.50.
2.92
For this particular example, the ranking early on during the generation is representative of the final ranking, i.e.:
s (Y,ST) 2 s(2 s(Y)) 2 2Y2)
This observation suggests that we can use the partial rankings of sentences at the decision token т early-stop the generation of Y2.
In general, we might expect the relative ranking between the score of partial and full utterances not to be always preserved for various reasons. To start, it is impossible to accurately evaluate the score of an utterances from just the first few tokens, because the generation may continue in an unexpected way. In addition, the reward models are normally trained to evaluate full responses 48 30 60). Nonetheless, we observe substantial correlation between the scores (o(Y)"))e
Figure 2 Each point in the figure {(s(Y s(Y)) consists of the score s( of the partial utterance on the X axis and the score s(Y) of the utterance upon completion on the Y axis. The red dot corresponds to the utterance with the highest final score. For this example, early-stopping the generation of all utterances the left of the dashed vertical line corresponds to early stopping the generation of all utterances which, at the decision token т, have score
and {s(Y))
s(Y s(Y = = 2.92.
(2)
Insight. Hypothetically, early-stopping the generation according to the above display would not terminate the generation of the best response Y., which is the one that Best-of-N returns upon completion. In other words, early-stopping according to (2) leaves the quality of the output Best- of-N unchanged. However, doing saves approximately 85.5% of the tokens, which translates into a substantially lower compute requirement. We also examine the Pearson's 's correlation and Kendall's rank correlation between partial and final rewards in Appendix B
In practice, it is infeasible implement Equation 2 because c, is unknown. Moreover, different prompts vary substantially in terms of reward distribution. Most importantly, this discussion does not describe how to find the decision token, whose choice has great impact in terms of efficient hardware utilization. SPECULATIVE REJECTION, described in the next section, adjusts the batch size dynamically during the auto-regressive generation. does so by automatically determining the decision tokens based on GPU memory capacity during decoding, ensuring efficient hardware utilization. then continues the generation only for the most promising utterances beyond that point until either the next decision token is reached, or the auto-regressive generation is complete.
5

---

Algorithm SPECULATIVE REJECTION
Input: An auto-regressive generative model p. a reward model stopping fraction a (0, 1),
prompt X.
1: Decide the initial batch size as binit based on the GPU memory capacity and the prompt length.
2: <- Diiit I 23.
3: while b do
4: For 1 - k S 6, generate .Y Y..... Y
from model p and T := min(r, Ex where Th is the number of generated tokens before OOM and & is the number of tokens in Yk-
5: Evaluate all partial rewards (3) from s and compute the cutoff threshold via 4
6: Compute the set of accepted index Iaccepted via (5). add completed sequences to I.
7: Update the batch size using I +- [Taccepted]-
8: end while
Output: YSR = Yg- with k* = arg maxkEz 8V{))-
4.2 Algorithm
Building the insight from the previous section, present SPECULATIVE REJECTION, as il- lustrated in Figure [ We plot the memory usage during generation with the Best-of-N decoding strategy and observe that significant fraction of GPU memory remains underutilized in the early stages of auto-regressive generation. Moreover, since auto-regressive generation with small batch sizes tends to be memory-boume [16] 351, part of the accelerator's computational capacity is left unused. Together with the insight from Section 4.] these observations present an opportunity to de- sign an algorithm that more effectively utilizes available GPU memory and computational resources to generate a set of candidate responses for ranking with reward model.
Our approach is straightforward: would normally cause the accelerator to run out of memory (OOM) after generating only a few tokens. When the accelerator is about to run out of memory, cording to the reward model and halt the generation of a fraction, a, of the lowest-scoring responses. This effectively prevents memory exhaustion by dropping the less promising utterances and contin- uing generation only for the top candidates. A rejection round occurs each time the GPU approaches its memory limit. The complete procedure is detailed in Algorithm Specifically, each rejection round consists of three phases, as outlined below.
begin by running Best-of-N with high N,,
large that
rank the incomplete utterances
Early Generation. Algorithm ! generates sequences until OOM, where is the max number of generated tokens. If, for some sequence. the EOS token is reached before the 7-th token, we only generate the tokens up the EOS token. Therefore, the actual stopping time for the early generation phase for prompt yv is т == min(T,ex}
2. SPECULATIVE REJECTION. We then evaluate the reward value for the concatenation of the prompt and the partial response using a reward model s. The set of partial rewards is defined as
Rpartial := {s ( (m : === 1,2,
(3)
where Y = (Y2, Y2 ....... YT)) is the first Te tokens of response Yg. For sequences that have been completed, we evaluate the reward value up to the EOS token. In this case, the partial and final rewards are the same. Next, we compute a prompt-dependent cutoff threshold quantile of all partial rewards:
Fcut := qa (Rpartial),
where e [0, 1] is the rejection rate, a hyperparameter that controls the fraction of trajectories to terminate, and (.)()) represents the a-th lower quantile.
3. Promising Utterances for Next Round. For all generations, we continue generating the top (1 - a) proportion of remaining sequences up the EOS token (or the maximum allowed generation length) if its partial reward exceeds Teut- Otherwise, we terminate this sequence. More formally, the index set for accepted sequences is denoted as:
Taccepttd
kk: < k b.
(
Yaut
(5)
If I Iaccepted is not empty, we will update the new batch size for the next rejection round.

---

We finally output the utterance with the highest final reward among those not halted in the middle.
Mathematically, the returned response
YSR Yk", where k= arg max (Y Yx ~ p( [x)].
(6)
KEZ
In effect, this procedure "simulates" Best-of-N with a higher N during the initial phase and dynam- ically reduces the batch size to prevent OOM. As illustrated in Figure SPECULATIVE REJECTION utilizes the available GPU memory far more efficiently than Best-of-N. Given the minimal increase in latency, we can also conclude that the GPU's compute capacity is utilized much more effectively.
Experiments
In this section, we evaluate the effectiveness of SPECULATIVE REJECTION. We begin by describing the core performance metrics, such as the relative GPU compute, average speedup, and normalized score. Next, in Section 5.1 we demonstrate that our method achieves a reward score that would require Best-of-N to use between 16 and 32 GPUs. Section 5.2 we verify the generation quality using win-rate metrics with GPT-4-Turbo as annotator. Finally, in Section [5.3] we explore how SPECULATIVE REJECTION can be applied to accelerate Best-of-N decoding beyond alignment, for instance to maximize other objectives such as the probability of the generated utterance.
Setup. For SPECULATIVE REJECTION to be practical reward- soterddmxiiizzing decoding strategy, it must generate high-reward responses with reasonable hardware requirement and latency (i.e., wall- clock time). To evaluate this, we run SPECULATIVE REJECTION single GPU and compute the maximum reward &(Y SR) for the response YSR generates. In contrast, we use let #GPUs denote the number of GPUs used by Best-of-N. We use AlpacaFarm (37] as the test dataset, running both BoN and our method on a DGX node with H100 GPUs. Our implementation, based on Py PoTrch, features an efficient inference system that automatically determines the maximum number of tokens to generate before running out-of oott--oororyy and pre-allocates the corresponding KV cache.
Baselines. We run the Best-of-N algorithm on the same prompts to generate a response Y Best--of-N with a score s(Y of.. We incrementally increase the value of N Best-of-N until the reward value s(Y Best-ol-N) matches that of SPECULATIVE REJECTION. To ensure that Best-of-N N utilizes the GPU memory efficiently, we determine the maximum batch size that allows Best-of-N the generation without running out of memory Starting from Best-of- 120, we progressively double the value of N to 240, 480, 960, 1920, and 3840. Each time N doubles, the number of GPUs required by Best-of-N also cuables-Best-ore -02 runs on # GPUSs = 1, but Best-of-480 require GPUs 4. For simplicity, we utilize the standard generate () function in HuggingFace transformers 68 for the baseline implementation""
complete
single H100 GPU, which we found to be 120.
Performance Metrics. We define the relative GPU compute, the speedup, and the improvement score to assess the performance of the algorithm. The definition of the relative GPU compute is a natural one: given prompt X, the relative GPU compute is the wall-clock time TH divided by the wall-clock time of Best-of-NNiin (e.g., NMmin = 120). On the other hand, the speedup is similar to rel- ative GPU compute, but is defined as the speedup compared to the maximum N (c.g.. Nmmi 3840).. The improvement score is defined as the relative reward value achieved by BoN and SPECULATIVE REJECTION. Since different reward models and language models define very different reward distri- butions, we normalized the score by the reward range of Best-of-N, min- Mathematically, we denote the responses generated via SPECULATIVE REJECTION as YSR and the utterances generated via
PIt is possible to use a single GPU to run Best-of-480 by generating 4 batches of 120 responses, but this increases latency by factor of 4. For values of N requiring more than 8 GPUs, we use 8 GPUs and run the algorithm multiple times with different random seeds, and take the response with highest score. Note that efficiency of this function varies depending on the model being used. 41 BoN x # GPUs for oest-of-N N and SpecRaj for SPECULATIVE REJECTION
7

---

Mistral: 78 v0.3 RM Mistral78
78 v0.3 20. FSTarX LLMMA3
Mistoal78 10ooli---aa v0.3 WT ArnoRM Laaaa
.0.0
125
137.5
0.3
Imgeoveeeen Srare
120
135.0
1020
112.5
215
Engrovemeent
130.0
11.
110
105.0
105
245
105
102.5
100
Specsbativ Aejectice
100.0
Souadittee Rejection
0.5
2.0
8.0
16.0
32.5
0.5
1.0
2.0
4,0
8.0
16.0
32.0
1.0
2.0
4.0
16.0
$2.0
Rebbive GPU Compute
Retotive GPU Compute
Relative GPU Compute
Lamm
Upmm Fstairx
Lama
Liana
0.5
07
125
364
120
IroEeeetent Srore
120
Proeeamment Scate
1420
135
111
130
21.0
205
105
105
246
100
1.0
Speciiltive Anjettco
100
120
Spariaat Rejietiin
Speciodian Repction
Retative Compute
Rebiive
RM
LLAMAS
instruct Lisma3
y0k0
112
112.5
112
11.0
6.
110.0
110
3.0
6.5
107.5
105.0
246
102
245
102.5
102
100
100.0
100
98
2.0
18.0
3.0
2.0
4.0
Rolative GPU Compute
Compute
Compute
Figure 3: We evaluate our efficient implementation of SPECULATIVE REJECTION on the AlpacaFarm- dataset using various generative models and reward models. The numbers indicate N for Best-of- N and re- jection rate for SPECULATIVE REJECTION. SPECULATIVE REJECTION consistently achieves higher reward scores with fewer computational resources compared Best-of-N.
Best-of-Nman Z1, Zz...., N With this notation, for a given prompt X, we have
Speedup = TBoN
Relative GPU Compute:: =
TBoNmm
T
max (Zx) - s (YSR) kE[Nmbl
Improvement Score ==
x 100.
(8)
max $ (Zx) kE(NNit
min
(Zx)
kE(Nnil]
We report their average prompts. Notice that improvement equal to 100 indicates that the method achieves the same reward score as Best-of-N min on average.
5.1 Elficiency Evaluation
We report the relative GPU compute and the improvement score for Best-of-N and SPECULATIVE REJECTION in Figure 3 For SPECULATIVE REJECTION, we additionally report the rejection rate while for Bfst-of-NV we report the value of N. We set Best-of-120 120 as the baseline because it can run on single 80GB GPU, producing all utterances concurrently without running out of memory. Figure highlights the efficiency our procedure: SPECULATIVE REJECTION utilizes fewer GPU resources to achieve higher scores compared to Best-of-N. Specifically, with Llama- 3-8B and reward model RM- Speculative Rejection achieves reward score that would require Best-of-N to use between 16 and 32 GPUs. While the precise performance may vary across different generative model and reward model pairs, overall trend remains consistent. Notably, SPECULATIVE REJECTION provides less improvement for Llama-3 3-BB- In-ntrcttt compared to the

---

Table 1: Win-rate results various settings for the Mistral-7B, Llama-3-8B, and (aama-3-B-IIntrruus models, scored by the reward model ArmoRM-Llama-3-80 and evaluated using GPT-4-Turbo. "WR" refers to win-rate, and "LC-WR" refers to length-controlled win-rate.
Mistral-7B
Llama-3-8B
Maama-3-8B-Instrur
Average
Methods
WR
LC-WR
WR
LC-WR
WR
LC-WR
WR
LC-WR
Bo120
50.00
50.00
50.00
50.00
50.00
50.00
50.00
50.00
Bo240
60.69
60.07
50.45
50.27
49.92
52.89
53.69
54.41
Bo480
61.28
61.84
58.90
59.93
50.49
53.11
56.89
58.29
Bo960
67.50
68.07
59.20
60.26
50.39
51.64
59.03
59.99
Bo1920
75.20
76.27
60.57
61.05
51.86
53.13
62.54
63.48
Bo3840
76.13
77.21
59.19
57.91
53.36
54.01
62.89
63.04
Ours (a = 0.5)
69.42
73.31
73.60
77.91
55,50
58.80
66.17
70.01
base models like Mistral-7B and Llama-3-8B. This is because 3-B-a----BIInstrutt more aligned and tends to generate shorter responses, resulting in fewer rejection rounds.
Effeet of the Rejection Rate. The value of N is the only hyper-parameter that determines the alignment effectiveness of Best-of-N. Such value is replaced by the rejection rate, a, for SPEC- ULATIVE REJECTION. Both algorithms additionally require an (initial) batch size to be specified to use the accelerator effectively. Notice that running our method with a 0 and an initial batch size of N is equivalent to running Best-of-N, and so our method is more general than Best-of-N.
A high value of implies that the rejection is very aggressive and several responses eliminated at each rejection round; in such case, only a few rejection rounds occur during the generation. On the other hand, low value for the rejection rate only halts the generation of those responses that exhibit very low score amid the generation. Since this case SPECULATIVE REJECTION only rejects responses that are clearly sub-optimal, it maintains larger pool of responses any given point during the generation, some of which are likely to score very high upon termination, and so the final score higher than what it would be for larger a. However, as illustrated Figure small increases the latency slightly, due to the computational cost required through the reward model, as well to the generally higher batch size any point of the generation.
5.2 Win-rate Evaluation
To further validate the generation quality, evaluate both the win-rate 37 and the length- controlled (LC) win-rate [20) using GPT-4-Turbo based on the generations from the prior section. For each measurement, the win-rate baseline is Bo120. As shown in Table SPECULATIVE RE- JECTION maintains generation quality while achieving a notable speedup in most combinations.
5.3 Maximization of the Probability of the Generated Utterances
SPECULATIVE REJECTION is a general purpose awwardmaxximzzing decoding strategy that can be applied with any rejection policy. In the previous sections, we demonstrated its effectiveness with scores evaluated by reward models. In this section, we evaluate its performance using the probability of the generated utterances the reward function.
We test Best-of-N and SPECULATIVE REJECTION on AlpacaFarm--Eva dataset. Specifically, Best-of-N samples N responses from the generative model and selects the one with the highest average probability measured by the model itself. To more precise,x given the prompt X and the utterances (Ya YR p(- X)}. the reward function is defined s(Y))
len In'(Pr X) where len(Yx) is the numbers of tokens in the response YE. SPECULATIVE REJECTION rejects the top fraction of responses with the lowest average probability during each rejection round. As shown in Table our method outperforms Best-of-N, consistently producing responses with higher probability under the language model and achieving remarkable speedup.

---

Table 2: Perplexity (PPL) results various settings for range of models show that SPECULATIVE RE- JECTION faster than Best-of-N, while consistently generating responses with lower perplexity. Notably, unexpected speedup observed with Mistral-7B is partially due to the inefficient implementation of grouped- query attention (GQA) in HuggingFace transformers (2).
Mistral-7B
Llama-3-8B
-Jama-3-8-IInss
Average
Methods
PPL
Speedup
PPL.
Speedup
PPL
Speedup
PPL
Speedup
Bo120
2.316
x
2.020
31.9x
2.885
29.5x
2.407
31.6x
Bo240
2.143
15.9x
1.775
16.0x
2.718
15.9x
2.212
15.9x
Bo480
1.919
8.0x
1.595
8.1x
2.618
7.6x
2.044
7.9x
Bo960
1.744
4.0x
1.506
4.0x
2.533
4.1x
1.928
4.0x
Bo1920
1.637
2.0x
1.394
2.0x
2.449
2.0x
1.827
2.0x
Bo3840
1.488
1.0x
1.288
1.0x
2.318
1.0x
1.698
1.0x
Ours (ar 0.5)
1.476
76.9x
1.299
30.6X
1.887
12.1x
1.554
39.9x
6 Limitations and Conclusions
SPECULATIVE REJECTION general purpose techique accelerate reward-oriented decoding from LLMs.. The procedure is simple to implement while yielding substantially speedups over the baseline Best-of-N. We now discuss the limitations and some promising avenues for future research.
Prompt-dependent Stopping, Our implementation of speculative rejection leverages statistical correlations to early stop trajectories that are deemed unpromising. However, it is reasonable to expect that the correlation between partial and final rewards varies prompt- prompt-by-pront sere-by--proppp For target level of normalized score, early stopping can be more aggressive in some prompts and less others. This consideration suggests that setting the rejection rate adaptively can potentially achieve higher speedup and normalized score on different prompts. We leave this opportunity for future research.
Reward Models as Value Functions. Our method leverages the statistical correlation between the reward values the decision tokens and upon termination. Concurrently, recent literature 44 73 80] also suggest training reward models as value functions. Doing so would enable reward models predict the expected score upon completion at any point during the generation and thus be much more accurate models for our purposes. In fact, our main result establishes that this would lead to an optimal speedup. and would interesting conduct numerical investigation.
Acknowledgments
We thank Yiqi Wang for briefly working with us at the beginning. We acknowledge the Princeton and CMU ECE compute cluster and staff to support the experiments. Andrea acknowledges Researcher Access program from OpenAL. Peter gratefully acknowledges the support of the NSF through grants DMS-2023505 and DMS-2031882 the Simons Foundation through award #8 1639,, and the ONR through MURI award 12401.
References
[1] Kwangjun Ahn, Ahmad Beirami, Ziteng Sun, and Ananda Theertha Suresh. Spectr++: Im- proved transport plans for speculative decoding of large language models. In NeurIPS 2023 Workshop Optimal Transport and Machine Learning. 2023.
[2] Joshua Ainslie, James Lee-Thorp. Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. arXiv preprint arXiv:2305.1324 2023.
[3] Afra Amini, Tim Vieira, and Ryan Cotterell. Variational best-of-n alignment. arXiv preprint arXiv:2407.06057 2024.
[4] Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learning
10

---

from human preferences. In International Conference on Artificial Intelligence and Statistics, pages 4447-4455. PMLR, 2024.
[5] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint (rxXiv:2222.0077: 2022.
[6] Michiel Bakker, Martin Chadwick, Hannah Sheahan, Michael Tessler, Lucy Campbell- Gillingham, Jan Balaguer, Nat McAleese, Amelia Glaese, John Aslanides, Matt Botvinick, al. Fine-tuning language models to find agreement among humans with diverse preferences. Advances in Neural Information Processing Systems, 35:38176-38189 2022.
[7] Gérard M Baudet. On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence, 10(2):173-199, 1978.
[8] Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D A'mour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees on the best-of-n align- ment policy, arXiv preprini arXivv2401.0125 2024.
[9] David Brandfonbrener, Sibi Raja, Tarun Prasad, Chloe Loughridge. Jianang Yang, Simon Hen- niger, William Byrd, Robert Zinkov, and Nada Amin. Verified multi-step synthesis using large language models and monte carlo tree search, 2024.
[10] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language mod- els are few-shot learners. Advances in neural information processing systems, 33:1 17:71191, 2020.
[11] Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint drXiv:2307.15217, 2023.
[12] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318 2023.
[13] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.023: 2022.
[14] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information pro- cessing systems, 30, 2017.
[15] Thomas Coste, Usman Anwar, Robert Kirk, and David Krueger. Reward model ensembles help mitigate overoptimization. arXiv preprint arXiv:2310.02743 2023.
[16] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness, 2022.
[17] Ameet Deshpande, Vishvak Murahari, Tanmay Rajpurohit, Ashwin Kalyan, and Karthik Narasimhan. Toxicity in chatgpt: Analyzing persona-assigned language models. arXiv preprint arXiv:2304.05335 2023.
[18] Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient fine- tuning of quantized llms. Advances in Neural Information Processing Systems, 36, 2024.
[19] Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, Kashun Shum, and Tong Zhang. Raft: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:2304.06777, 2023.
[20] Yann Dubois, Balázs Galambosi, Percy Liang, and Tatsunori B Hashimoto. Length- Length-controlled alpacaeval: A simple way to debias automatic evaluators. arXiv preprint arXiv:2404.04475, 2024.
11

---

[21] Yann Dubois, Chen Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Car- los Guestrin, Percy S Liang, and Tatsunori B Hashimoto. Alpacafarm: simulation framework for methods that learn from human feedback. Advances in Neural Information Processing Sys- tems, 36, 2024.
[22] Jacob Eisenstein, Chirag Nagpal, Alekh Agarwal, Ahmad Beirami, Alex D' D'mur,, DJ Dvi- jotham, Adam Fisch, Katherine Heller, Stephen Pfohl, Deepak Ramachandran, et al. Helping or herding? reward model ensembles mitigate but do not eliminate reward hacking. arXiv preprint arXiv:2312.09224, 2023.
[23] Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01300 2024.
[24] Samuel H Fuller, John G Gaschnig, JJ Gillogly, et al. Analysis of the alpha-beta pruning algorithm. Department of Computer Science, Carnegie-Mellon University, 1973.
[25] Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference on Machine Learning, pages 10835-10866. PMLR, 2023.
[26] Amelia Glaese, Nat McAleese, Maja Trkebacz, John Aslanides, Vlad Firoiu, Timo Ewalds, Maribeth Rauh, Laura Weidinger, Martin Chadwick, Phoebe Thacker, et al. Improving align- ment of dialogue agents via targeted human judgements. arXiv preprint arXiv:2209, 244.:5,20..4375, 2022.
[27] Dongyoung Go, Tomasz Korbak, Germán Kruszewski, Jos Rozen, and Mare Dymetman. Com- positional preference models for aligning Ims. arXiv preprint arXiv:2310. 1330 1, 2023.
[28] Lin Gui, Cristina Gârbacea, and Victor Veitch. Bonbon alignment for large language models and the sweetness of best-of-n sampling. arXiv preprint 24080022000,,,,,, 2024.
[29] Xuanli He, Iman Keivanloo, Yi Xu, Xiang He, Belinda Zeng, Santosh Rajagopalan, and Trishul Chilimbi. Magic pyramid: Accelerating inference with early exiting and token pruning. arXiv preprint arXiv:2111.002300, 2021.
[30] 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 preprint drXiv:2310.06825, 2023.
[31] Yigitcan Kaya, Sanghyun Hong, and Tudor Dumitras. Shallow-deep networks: and mitigating network overthinking. In International conference on machine learning, pages 3301-3310. 10. PMLR, 2019.
Understanding
[32] Maxim Khanov, Jirayu Burapacheep, and Yixuan Li. Args: Alignment as reward-guided search. arXiv preprint arXiv:2402.01694 2024.
[33] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou, editors, Machine Learning: ECMI. 2006, pages 282-293, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
[34] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large lan- guage model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611-626, 2023.
[35] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.
[36] Kenneth Li. Samy Jelassi, Hugh Zhang, Sham Kakade, Martin Wattenberg, and David Brand- fonbrener. Q-probe: A lightweight approach to reward maximization for language models. arXiv preprint arXiv:2402. 14688, 2024.
[37] Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori Hashimoto. Alpacaeval: An automatic evaluator of instruction- following models. attps://github htt.eh/cwooo//ttaaaaaaaaaaa//aaa
hacp//apaaaaaaaaaaaaaaaaaaaaaaea _vall 5 2023.
12

---

[38] Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz. Don't throw away your value model! making ppo even better via value-guided monte-carlo tree search decoding, arXiv e-prints, pages arXiv-2309, 2023.
[39] Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz. Making ppo even better: Value-guided monte-carlo tree search decoding. arXiv preprint arXi:: 15028, 2023.
[40] Tianqi Liu, Yao Zhao, Rishabh Joshi, Misha Khalman, Mohammad Saleh, Peter Liu, and Jialu Liu. Statistical rejection sampling improves preference optimization. arXiv preprint arXiv:2309.06657 2023.
[41] Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang, Haotang Deng, and Qi Ju. Fastbert: a self- distilling bert with adaptive inference time. arXiv preprint arXiv:2004.02/78, 2020.
[42] Renze Lou, Kai Zhang, and Wenpeng Yin. A comprehensive survey on instruction following, 2024.
[43] T Anthony Marsland. A review of game-tree pruning. ICGA joumall, 9(1):3-19, 1986.
[44] Meta. Llama3 technical report, http://ww..eeeaccoommbbm/meeeeam 2024.
[45] Sidharth Mudgal, Jong Lee, Harish Ganapathy, YaGuang Li, Tao Wang, Yanping Huang, Zhifeng Chen, Heng-Tze Tze Cheng. Michael Collins, Trevor Strohman, et. Controlled decoding from language models. arXiv preprint arXiv:2310. 17022 2023.
[46] Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browser- assisted annserin with human feedback. arXiv preprint arXiv:2112.09332, 2021.
[47] Richard Ngo, Lawrence Chan, and Sören Mindermann. The alignment problem from deep learning perspective. arXiv preprint 220.:22009,06666, 2022.
[48] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 25:27730-27744, 2022.
[49] Rafael Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From r to go: Your language model is secretly a q-function. arXiv preprint arXiv:2404.1233 2024.
[50] 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, 36, 2024.
[51] Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, pages 6263-6289 PMLR, 2023.
[52] Jérémy Scheurer, Jon Ander Campos, Tomasz Korbak, Jun Shern Chan, Angelica Chen, Kyunghyun Cho, and Ethan Perez. Training language models with language feedback at scale. arXiv preprint arXiv: 16755, 2023.
[53] Roy Schwartz, Gabriel Stanovsky, Swabha Swayamdipta, Jesse Dodge, and Noah A Smith. The right tool for the job: Matching model and instance complexities. arXiv preprint 2xXi:2004.004553 2020.
[54] Pier Giuseppe Sessa, Robert Dadashi, Léonard Hussenot, Johan Ferret, Nino Vieillard, Alexan- dre Ramé, Bobak Shariari, Sarah Perrin, Abe Friesen, Geoffrey Cideron, et al. Bond: Aligning Ilms with best-of-n distillation. arXiv preprint 2rXiv:2407.14622 2024.
[55] Feifan Song, Bowen Yu, Minghao Li, Haiyang Yu, Fei Huang, Yongbin Li, and Houfeng Wang- Preference ranking optimization for human alignment. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 18998, 2024.
13

---

[56] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler. Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-302) 2020.
[57] Nathan R Sturtevant and Richard E Korf. On pruning techniques for multi-player games. AAAI/IAAI, 49:201-207, 2000.
[58] Hanshi Sun, Zhuoming Chen, Xinyu Yang, Yuandong Tian, and Beidi Chen. Triforce: Loss- less acceleration of long sequence generation with hierarchical speculative decoding. arXiv preprint arXiv:2404. / 1912, 2024.
[59] Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36, 2024.
[60] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Alpaca: A strong, replicable instruction- following model. Stanford Center for Research on Foundation Models. https://erfm. stanford. edu/2023/03/1 3/alpaca. himl, 2022.
[61] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. PMLR, 2020.
In International Conference on Machine Learning, pages
[62] Surat Teerapittayanon, Bradley McDanel, and Hsiang-Tsung Kung. Branchynet: Fast infer- ence via early exiting from deep neural networks. In 2016 23rd international conference on pattern recognition (ICPR), pages 2469. IEEE, 2016.
[63] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Tim- othée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, al. Llama: Open and efficient foundation language models. arXiv preprint arX.v: 13971, 2023.
[64] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint S.XIv:2307.092888 2023.
[65] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[66] Pengyu Wang, Dong Zhang, Linyang Li, Chenkun Tan, Xinghao Wang, Ke Ren, Botian Jiang, and Xipeng Qiu. Inferaligner: Inference-time alignment for harmlessness through cross-model guidance, 2024.
[67] Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. Self-instruct: Aligning language models with self-generated instruc- tions, 2023.
[68] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's trans- formers: State-of-the-art natural language processing. arxiv. arXiv preprint arXiv: 190000377, 2019.
[69] Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self- play preference optimization for language model alignment. arXiv preprint arXiv:2405.00675. 2024.
[70] Yuxi Xie, Anirudh Goyal, Wenyue Zheng, Min- Yen Kan, Timothy P. Lillicrap. Kenji Kawaguchi, and Michael Shieh. Monte carlo tree search boosts reasoning via iterative prefer- ence learning, 2024.
[71] Joy Qiping Yang, Salman Salamatian, Ziteng Sun, Ananda Theertha Suresh, and Ahmad Beirami. Asymptotics of language model alignment. arXiv preprint 24X 2024.
14

---

[72] Zheng Yuan, Hongyi Yuan, Chuanqi Tan, Wei Wang. Songfang Huang, and Fei Huang. Rrhf: Rank responses to align language models with human feedback without tears. arXiv preprint arXiv:2304.05330, 2023.
[73] Yongcheng Zeng, Guoqing Liu, Weiyu Ma, Ning Yang, Haifeng Zhang, and Jun Wang. Token- level direct preference optimization. arXiv preprint arXiv:2404.11999 2024.
[74] Dan Zhang, Sining Zhoubian, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets": Llm self-training via process reward guided tree search. arXiv preprint arXiv:2406.0388/ 2024.
[75] Di Zhang, Jiatong Li, Xiaoshui Huang, Dongzhan Zhou, Yuqiang Li, and Wanli Ouyang. Accessing gpt-4 level mathematical olympiad solutions via monte carlo tree self-refine with Ilama-3 8b. arXiv preprint arXiv:2406.073: 07394, 2024.
[76] Ruiqi Zhang, Licong Lin, Yu Bai, and Song Mei. Negative preference optimization: From catastrophic collapse to effective unlearning. arXiv preprint arXiv:2404.05866. 2024.
[77] Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Saleh, and Peter J Liu. Slic- hf: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305.10425, 2023.
[78] Yao Zhao, Mikhail Khalman, Rishabh Joshi, Shashi Narayan, Mohammad Saleh, and Pe- ter Liu. Calibrating sequence likelihood improves conditional language generation. In The Eleventh International Conference on Learning Representations, 2022.
[79] Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models commonsense knowledge for large-scale task planning, 2023.
[80] Han Zhong, Guhao Feng, Wei Xiong, Li Zhao, Di He, Jiang Bian, and Liwei Wang. Dpo meets ppo: Reinforced token optimization for rlhf. arXiv preprint arXiv:2404, 18922, 2024.
[81] Zixuan Zhou, Xuefei Ning, Ke Hong, Tianyu Fu, Jiaming Xu, Shiyao Li, Yuming Lou, Luning Wang, Zhihang Yuan, Xiuhong Li, et al. A survey efficient inference for large language models. arXiv preprint ar Xrx: 14294, 2024.
15

---

A Detailed Authors' Contributions
Hanshi co-lead the code infrastructure, led the implementation of the efficient inference engine and win-rate analysis, lead the final experiments in the paper and co-led the writing of the final paper Momin co-lead the code infrastructure, led the preliminary experiments, and contributed to the writing of an early draft of the manuscript
Ruiqi provided several conceptual contributions to the work. He led writing of the initial draft of the paper, and led the early statistical analysis to assess the feasibility of the project.
Huitao lead the theoretical part of the work
Ming provided useful feedback for the project during the weekly project meeting discussion Jiahao contributed with a win-rate analysis during the rebuttal period
Mengdi provided useful feedback and helped with accessing some of the compute infrastructure Peter provided useful feedback, particularly regarding the correlation analysis in the early stage of the project and also co-suggested the iterative rejection scheme Andrea conceived the original idea of speculative rejection, advised the project, and co-led the final writing of the paper.
B Correlation between partial and final rewards
In this section, we present our observation that the partial and final rewards are positively correla- tive for the responses single prompt. We examine the distribution for the (empirical) Pearson correlation and Kendall's 's tau correlation coefficient for partial and final rewards for single prompt. Mathematically. for (x1,X2, X2....... XN) and (Y1, Y2, ..., YN), the two correlation are defined as
E (X; X)(Y- - -Y
Rpearson
V (X; - -x-² Em -Y²
2
sgn(X; Xz) sgn(Y; Yj), Σ
RKendall
N(N 1)
icj
where E X,N,Y Em Y//N are their average, and sgn(-) ) is the sign function.
Kendall's Tau Correlation Coefficient
1.0
Pearson Correlation Coefficient
0.6
0.4
0.4
0.2
0.0
12B
256
512
1024
2013
32
64
128
256
1024
2048
Decision Tokens
Decision Tokens
Figure 4: Pearson correlation (left) and Kendall's correlation coefficient (right) for the partial and final rewards. We randomly sample 100 prompts the AlpacaFarm Evarl dataset. The responses are generated via Llama3-88 ---aa33-----ttnn In-trrcct and rewards are evaluated Mistral-7B-A
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We believe our introduction and abstract are factually accurate in describing the contributions of the paper and its result
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are presented in the final section of the main paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
17

---

Justification:
We do not include theoretical results in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: We provide all setup details to reproduce the experiment. In our supplemen- tary zip file, we provide all code and evaluation datasets used, along with a README with instructions. We use public checkpoints for all draft and target models, public data for all evaluations.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., .., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
18

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The datasets that parties. We provide a zip file with the code and data needed to reproduce our experiments, well as README with instructions.
Justification:
freely available and hosted by reliable third
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
wttpps.ccppbblic///..cc wwwpiiiggwgee/eeeeeeeeeeee httd:/uuddde/eoeuubreee Code/SubeeiSiSeeecceeeee iisimissiin onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We only sample 100 prompts at random. There is no training involved.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: The cost for producing the experiments precludes us from reporting error bars. However, notice that each pair of Ilm and reward model produces a result that is aver- aged over 100 prompts. Since we report several such pairs, and the speedup substantial for each single pair, we are confident that overall speedup is statistically significant.
Guidelines:
The answer NA means that the paper does not include experiments.
19

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g,, Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of eπrоrs is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This is discussed in the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (c.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: None report.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work aims accelerating a known and existing method, and so not expected to have a direct societal impact.
20

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do release data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite the papers that introduced the models and data used in our work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
21

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, patasets.paperswiitte paperswithcode www.com///ac.o. condattseet has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: We include README along with our code to reproduce our experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: Our research does not involve humans.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
22

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "XNistjVqPh", "reviewer": "Reviewer_Qphu", "summary": "The paper proposes an early stopping method to accelerate the Best-of-N method. Experimental results demonstrate its effectiveness.", "questions": "Please refer to the weakness part.", "limitations": "The authors acknowledge the challenge inherent in selecting hyperparameters while also offering solutions to address this issue.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The method has a strong and clear motivation, coupled with easy implementation.\n2. Experimental results demonstrate its effectiveness in accelerating best-of-n while preserving the quality of generated content.", "weaknesses": "1. Best-of-N is out-of-date in decoding-time alignment, which weakens the novelty of the paper.\n2. The validity of the first point may be questionable when considering the utilization of best-of-n for response generation in model training. Nonetheless, the paper does not experiment with model training aided by SBoN.\n3. It would be advantageous if the author could test SBoN on a broader range of tasks beyond just alignment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response for the reviewer Qphu:\n\nWe thank the reviewer for providing valuable feedback and understanding the value of our work. We have read your comments carefully and below are our detailed responses.\n\n---- \"Best-of-N is out-of-date in decoding-time alignment, which weakens the novelty of the paper.\" ----\n\n**Response:** We find that Best-of-N(Rejection Sampling) is still a widely used technique that remains relevant even in recent times. For example, Song et al. [1] show that Best-of-N on relatively small models like Llama-3-8B-Instruct with values of N as small as 16-32 can outperform GPT-4-Turbo on several tasks. Additionally, Best-of-N was an important part of the deployment of OpenAI's WebGPT [2]. Also, rejection sampling is frequently used to generate high-quality data for alignment [3][4][5].\n\nFinally, very recent work has proposed aligning language models such that their distribution of generations is closer to the Best-of-N distribution [6][7].\n\n[1] Song, Yifan, et al. \"The Good, The Bad, and The Greedy: Evaluation of LLMs Should Not Ignore Non-Determinism.\" arXiv preprint arXiv:2407.10457 (2024).\n[2] Nakano, Reiichiro, et al. \"Webgpt: Browser-assisted question-answering with human feedback.\" arXiv preprint arXiv:2112.09332 (2021).\n[3] Khaki, Saeed, et al. \"Rs-dpo: A hybrid rejection sampling and direct preference optimization method for alignment of large language models.\" arXiv preprint arXiv:2402.10038 (2024).\n[4] Liu, Tianqi, et al. \"Statistical rejection sampling improves preference optimization.\" arXiv preprint arXiv:2309.06657 (2023).\n[5] Dubey, Abhimanyu, et al. \"The Llama 3 Herd of Models.\" arXiv preprint arXiv:2407.21783 (2024).\n[6] Sessa, Pier Giuseppe, et al. \"BOND: Aligning LLMs with Best-of-N Distillation.\" arXiv preprint arXiv:2407.14622 (2024).\n[7] Amini, Afra, et al. \"Variational Best-of-N Alignment.\" arXiv preprint arXiv:2407.06057 (2024).\n\n\n---- \"The validity of the first point may be questionable when considering the utilization of best-of-n for response generation in model training. Nonetheless, the paper does not experiment with model training aided by SBoN.\" ----\n\n**Response:** \nAs the reviewer suggests, best-of-n can be used both for inference-time alignment [2] or for later model fine-tuning [1].\nThis latter setup is substantially more involved, and it introduces additional confounding factors (e.g., training hyper-parameters) which would have made the comparison harder.\nHowever, we added more metrics like the **win rate** computed by GPT4 [2] as a substitute (see attached PDF), to indicate that our algorithm produces high quality responses.\n \n[1] Dubey, Abhimanyu, et al. \"The Llama 3 Herd of Models.\" arXiv preprint arXiv:2407.21783 (2024).\n[2] Dubois, Yann, et al. \"Alpacafarm: A simulation framework for methods that learn from human feedback.\" Advances in Neural Information Processing Systems 36 (2024).\n\n\n---- \"It would be advantageous if the author could test SBoN on a broader range of tasks beyond just alignment.\" ----\n\n**Response:** In the attached PDF, we include preliminary experiments where we minimize the perplexity---which is equivalent to maximizing the probability of the generated text---with BoN and SBoN. \n\nWe also include a few experiments in which we show that the GPT4 win rate remains relatively stable and large across rejection rates.\nFinally, we include several new experiments across multiple LMs and RMs of varying size as well as varying datasets to demonstrate the robustness of our method in different settings. \n\nRegarding the hyperparameter limitation, a significant majority of LM+RM combinations use a decision token of either 128 or 256 and a rejection rate of either 0.7 or 0.8 for Best-of-100. This suggests that rejecting, say, 75% of the trajectories at decision token 200 would be a simple and practical choice for hyperparameters in several real-world settings.", "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": "xI3aUfIphX", "reviewer": "Reviewer_qQm8", "summary": "Best-of-N is a decoding-time alignment algorithm that effectively aligns the output of the system at the cost of high inference time. The paper seeks to reduce the computation time by pruning unpromising sequences at early stage using the reward model to estimate the reward on the partial utterance. They empirically show that the estimate of the reward model on a partial sentence is correlated with the estimate of a complete sentence, using AlpacaFarm-Eval dataset. The proposed method achieves 2-8 times speedup at a marginal drop of the output quality.", "questions": "The speedup depends on the speed of the text generation and reward models. How fast are they in the experiments? It would be valuable to have the wall time of the text generation and reward computation separately in the Appendix.", "limitations": "I don't see any problems. If the method is likely to exploit the structure of English, then it may be noted in the limitations that the experiments are conducted only in English.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Proposed method is simple and effective.\n- Experiments are clear and comprehensive, except for the variety of the tasks.\n- Showing that partial rewards have good correlation with the final rewards (Figure 2) is a significant contribution to the community.", "weaknesses": "I don’t see any critical weaknesses in the study. Several minor points are listed below. \n\n- Experiments are conducted only on AlpacaFarm-Eval dataset. It would be ideal to have an evaluation of the proposed method in other datasets (e.g., TL;DR, hh-rlhf) as the effectiveness of the method may be affected by the structure of the task. For example, I speculate the the reward of the partial text has less correlation with the complete text on tasks like text summarization. It may also be influenced by the language. For example, Korean and Japanese have more flexible word order than English and word order does not determine grammatical function. Thus, the same length of the first few tokens may contain very different information in these languages. This may make the partial reward not a good indicator of the final reward. It may better be noted that the proposed method might be exploiting the structure of English which is not universally true for all natural languages.\n- Adding two hyperparameters to the inference algorithm is a minus (as noted in Limitations). They show in Tables 3 and 4 that the optimal values of the hyperparameters are relatively consistent when using different choices of reward models and the number of samples (N). The question is how consistent the choice of the tasks/prompts (which is noted in Prompt-dependent stopping) is. It would be nice if one could evaluate the robustness of the hyperparameters to the variety of tasks.\n- Although the experiments are conducted on three language models and three reward models, they share relatively similar profiles. It would be beneficial to have larger and smaller language models and reward models.\n- An empirical evaluation of the proposed method compared against MCTS would be nice to have.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response for the reviewer qQm8:\nWe thank the reviewer for providing positive feedback and several good questions of our work. Below are our detailed responses.\n\n---- \"Experiments are conducted only on AlpacaFarm-Eval dataset. It would be ideal to have an evaluation of the proposed method in other datasets (e.g., TL;DR, hh-rlhf) as the effectiveness of the method may be affected by the structure of the task. For example, I speculate the the reward of the partial text has less correlation with the complete text on tasks like text summarization. It may also be influenced by the language. For example, Korean and Japanese have more flexible word order than English and word order does not determine grammatical function. Thus, the same length of the first few tokens may contain very different information in these languages. This may make the partial reward not a good indicator of the final reward. It may better be noted that the proposed method might be exploiting the structure of English which is not universally true for all natural languages.\" ----\n\n**Response:** \n\nIn the attached PDF, we have several new experiments on the HH-RLHF dataset as well and we show that our algorithm performs consistently well across both tested datasets. We would have liked to also test on the TL;DR task, but could not due to limited time.\n\nAdditionally, the reviewer makes a very good point regarding the specific semantics of the English language - in this sense, our method does take advantage of the structure of English and we will include this in the Limitations section.\n\n---- \"Adding two hyperparameters to the inference algorithm is a minus (as noted in Limitations). They show in Tables 3 and 4 that the optimal values of the hyperparameters are relatively consistent when using different choices of reward models and the number of samples (N). The question is how consistent the choice of the tasks/prompts (which is noted in Prompt-dependent stopping) is. It would be nice if one could evaluate the robustness of the hyperparameters to the variety of tasks.\" --- \n\n**Response:** In the attached PDF, we have tested the robustness of the hyperparameters by conducting multiple counterfactual analyses across several datasets, LMs, RMs, and tasks. We find that across all these combinations, an overwhelming majority of them use a decision token of either 128 or 256 and a rejection rate of 0.7 or 0.8. Then, a reasonable choice of hyperparameters in practice would be, say, rejecting 75% of the trajectories after generating 200 tokens. This would be a strong choice across a wide variety of real-world situations.\n\n---- \"Although the experiments are conducted on three language models and three reward models, they share relatively similar profiles. It would be beneficial to have larger and smaller language models and reward models.\" ---\n\n**Response:** In the attached PDF, we conduct several new experiments involving small and large LMs and RMs. We find that our method is effective across the spectrum of model sizes.\n\n\n---- \"An empirical evaluation of the proposed method compared against MCTS would be nice to have.\" ---\n\n**Response:** \nMCTS is definitely related as a decoding strategy. However, we could not complete the comparison by the end of the rebuttal period.\n\n\n---- \"The speedup depends on the speed of the text generation and reward models. How fast are they in the experiments? It would be valuable to have the wall time of the text generation and reward computation separately in the Appendix.\" ----\n\n**Response:** We can include detailed values in the appendix for all of the combinations, but it mostly depends on the maximum generation length specified by the LM. Rough estimates to produce and score a single batch of 20 on the new experiments are as follows on our machine:\n\n- GPT2-XL (max_length=1024): 25 seconds\n- GPT-J-6B (max_length=2048): 2-3 minutes\n- Mistral-7B (max_length=8000): 3-10 minutes\n- Llama-3-8B (max_length=8000): 1-5 minutes\n\nReward model computations are generally 1-5 seconds, highlighting the intuition behind the effectiveness of our algorithm: because **reward computations are relatively cheap**, it is worth generating a few tokens (say, 200) and pruning most of the generations before continuing. Moreover, generating earlier tokens from decoder-only transformer architectures is much less expensive than generating later tokens due to the quadratic attention cost, compounding the strength of our method.", "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": "34zmpzEmgG", "reviewer": "Reviewer_gUaJ", "summary": "Best-of-N decoding involves generating multiple responses and then selecting the highest scoring one according to a given metric of interest. Based on the observation that the reward function used for scoring the utterances can distinguish high-quality hypotheses from low-quality ones at an early stage of the generation, this paper focuses on accelerating this procedure by stopping the generation of “unpromising utterances”, i.e., those that are unlikely to be returned at the end.", "questions": "Comments and questions:\n\n- L36-38: I don’t think that saying that Best-of-N is “essentially” hyperparameter-free makes sense here. As you point out, $N$ is a hyperparameter. Also, the hypotheses can be sampled in various ways (e.g., sampling with different temperatures, nucleus samplings, etc). \n- There is a large body of work on decoding strategies for LLMs that rely on sampling multiple hypotheses and selecting the best one, including voting procedures [1], minimum bayes risk decoding [2], and other types of strategies [3, 4]. I believe they should at least be mentioned in the related work section.\n- As briefly mentioned in L161-169, predicting scores for unfinished sentences may be misleading. Even though Figure 2 does not look bad, this is just for one example, right? Unless I’m missing something, this does not seem to be enough evidence to support your claims. Since this is key to your proposal, it would be beneficial to expand the discussion about this topic as well as the empirical evidence.\n- L270-271: “we present experiments on the AlpacaFarm-Eval dataset, where we sample 100 prompts at random”. What do you mean by sampling 100 prompts? Is this a common practice?\n\nMinor comments:\n- Not all figures are referred to (see, e.g., Figures 5-14).\n- Sometimes you refer to equations as “eq. (X)”, sometimes just as “(X)”. The same thing happens with “appendix X” and “Appendix X”, or “Figure X” and “fig. X”. Please try to be consistent throughout the paper. \n- L306: Fix citation.\n\n[1] Self-Consistency Improves Chain of Thought Reasoning in Language Models (Wang et al., ICLR 2023)\n\n[2] It’s MBR All the Way Down: Modern Generation Techniques Through the Lens of Minimum Bayes Risk (Bertsch et al., BigPicture 2023)\n\n[3] An Empirical Study of Translation Hypothesis Ensembling with Large Language Models (Farinhas et al., EMNLP 2023)\n\n[4] Quality-Aware Decoding for Neural Machine Translation (Fernandes et al., NAACL 2022)", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "I summarize below the main strengths:\n- The motivation is very clear and improving the efficiency of LLMs at inference time is an important problem.\n- The empirical results seem to be promising.", "weaknesses": "Please see my questions and comments below. In my opinion, some parts of the submission could be significantly improved, including the overall organization of the paper, the related work section, and the discussion about situations in which the proposed method should or should not work. Also, I have some concerns about the experimental parts, which are detailed below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response for the reviewer gUaJ:\nWe appreciate the reviewer's detailed comments and we have read them carefully. Here are our detailed responses.\n\n---\"L36-38: I don’t think that saying that Best-of-N is “essentially” hyperparameter-free makes sense here. As you point out,  is a hyperparameter. Also, the hypotheses can be sampled in various ways (e.g., sampling with different temperatures, nucleus samplings, etc).\"---\n\n**Response:** This is a valid point. We agree that Best-of-N can rely on several hyperparameters, for example, temperature, nucleus sampling value (top-p), and top-k, among others. But it is also worth mentioning that sampling from language-models that went through a post-training phase also requires selecting the decoding strategy and its hyper-parameters (e.g., temperature) at decoding time. On top of these, Best-of-N only requires choosing N as additional parameter.\n\nRegarding the N hyperparameter, we examine its effect on our old and new experiments. When N is relatively small (~100-128), large rejection rates around 90% and higher have the potential to sacrifice significant performance. However, rejection rates as high as 80% still provide strong performance and improve efficiency at around 2-6x speedup, depending on the maximum length. \n\n\n---\"There is a large body of work on decoding strategies for LLMs that rely on sampling multiple hypotheses and selecting the best one, including voting procedures [1], minimum bayes risk decoding [2], and other types of strategies [3, 4]. I believe they should at least be mentioned in the related work section.\"--- \n\n**Response:** We agree, the body of work on decoding strategies for LLMs is very large and only growing larger. Although our related work already contains several categories, we will also include references such as the ones above to highlight the variety of available decoding strategies and how they connect to our algorithm.\n\n---\"As briefly mentioned in L161-169, predicting scores for unfinished sentences may be misleading. Even though Figure 2 does not look bad, this is just for one example, right? Unless I’m missing something, this does not seem to be enough evidence to support your claims. Since this is key to your proposal, it would be beneficial to expand the discussion about this topic as well as the empirical evidence.\"--- \n\n**Response:** We also include Figure 5 in Appendix D, which plots the correlation between partial reward and final reward across several decision tokens and for all prompts we tested. As shown,  there is positive correlation across prompts which allows our algorithm to work effectively.\n\n---\"L270-271: “we present experiments on the AlpacaFarm-Eval dataset, where we sample 100 prompts at random”. What do you mean by sampling 100 prompts? Is this a common practice?\"---\n\n**Response:** Of the 805 prompts in the Alpaca Farm Eval dataset, we randomly sample (without cherry-picking) 100 of these prompts and perform all of our experiments on those 100 prompts, to save computation to run the baseline given the limited computational resources available to us. \n\nAlso, since the win rate by GPT4 is expensive and OpenAI limits access to GPT4 on accounts each month, downsampling prompts from a large dataset is seen in other works [1].\n\n[1]Jang, Joel, et al. \"Personalized soups: Personalized large language model alignment via post-hoc parameter merging.\" arXiv preprint arXiv:2310.11564 (2023).\n\nRegarding the minor comments, we will also improve the consistency when referring to equations, figures, etc. and fix any citations we need to. However, we should note that Figures 5-14 are part of the Appendix, and so are indirectly referenced in the main body via the Appendices.", "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:
# General Response to all reviewers:
We thank all reviewers for the detailed comments and valuable questions. We present additional experiments here---as requested by the reviewers---and also address the reviewers' individual questions separately.
These new experiments include:
- New datasets
- LLMs and reward models of different sizes
- Minimizing the perplexity as an experiment different from alignment
- GPT4 win rate experiments

Taken together, we believe that these should address several of the reviewers' concerns, and we hope they would consider improving their scores. If not, we are very happy to answer any further question that the reviewers may have.

## Experimental details

In the attached PDF we use our algorithm to minimize the **perplexity**, which is related to the probability of the generated text to showcase that the algorithm works in task different from alignment, as suggested by reviewer Qphu.

Moreover, we include new experimental results related to alignment across several datasets, as well as LLM and reward model sizes, as suggested by most reviewers.
- Datasets:
    - Alpaca Farm Eval
    - HH-RLHF
- Language Models (LMs):
    - GPT2-XL (1.5B)
    - GPT-J-6B
    - Mistral-7B
    - Llama-3-8B
- Reward Models (RMs):
    - reward-model-deberta-v3-large-v2 (~500M)
    - RM-Mistral-7B
    - FsfairX-Llama-3-RM (8B)
    - ArmoRM-Llama3-8B


Although we weren't able to bring all possible combinations to completion due to time constraints, these new experiments demonstrates that:
1. **Our method works** on a variety of model sizes. Speedups with negligible drop in score are apparent **across** the spectrum of **small and large LMs and RMs**.
2. **Our method is effective on several different tasks**. Notably, we test our method on new tasks that include minimizing generation perplexity. The effectiveness of our algorithm is relatively consistent across tasks.

Meta-review: SUMMARY

Often people want to generate responses from a language model that have high scores according to some metric of interest.
The way this task is normally handled is by generating a bunch of possible outputs, scoring them according to the metric, and taking the best one.
The authors try to improve the efficiency of this strategy by halting the generation of unpromising utterances before they reach completion.

REASONS TO ACCEPT

The method the authors are trying to accelerate is a very common one that is used for a lot of tasks.
Therefore, the motivation for pursuing acceleration is very strong.
The method they come up with is simple and easy to implement, and the experimental results demonstrate its efficacy.

REASONS TO REJECT

- There are some concerns that best-of-N is out-of-date decoding strategy, which limits applicability of the method.
- One reviewer thought the experiments are insufficient, as they are exclusively conducted on the AlpacaFarm-Eval dataset, and it's unclear if the method will perform well on tasks with different structures languages. Also, all the LMs / reward models included in the experiments are pretty similar to each other.
- General comments about how organization and writing quality can be improved.

CONCLUSION

Even though the paper's impact might not be huge, it contains a nice, concentrated contribution which deserves to be shared with the NeurIPS community. However, the authors should try to resolve the organizational, missing citation, and writing suggestions mentioned by reviewers.
Decision: Accept (poster)