Block Verification Accelerates Speculative Decoding
Authors: Ziteng Sun
Uri Mendlovic
Yaniv Leviathan
Asaf Aharoni
Jae Hun Ro
Ahmad Beirami
Ananda Theertha Suresh
Venue: ICLR 2025 Poster (2025)
Keywords: llm efficiency
speculative decoding
distribution coupling
Primary area: learning theory

Abstract: Speculative decoding is an  effective method for lossless acceleration of large language models during inference. It uses a fast model to draft a block of tokens which are then verified in parallel by the target model, and provides a guarantee that the output is distributed identically to a sample from the target model. In prior works, draft verification is performed independently token-by-token. Surprisingly, we show that this approach is not optimal. We propose *Block Verification*, a simple draft verification algorithm that verifies the entire block jointly and provides additional wall-clock speedup. We prove that the proposed mechanism is optimal in the expected number of tokens produced each iteration and specifically is never worse than the standard token-level verification.
Empirically, block verification provides modest but consistent wall-clock speedups over the standard token verification algorithm of 5\%-8\% in a range of tasks and datasets.
Given that block verification does not increase code complexity, maintains the strong lossless guarantee of the standard speculative decoding verification algorithm, cannot deteriorate performance, and, in fact, consistently improves it, it can be used as a good default in speculative decoding implementations.

Published as a conference paper at ICLR 2025
BLOCK VERIFICATION ACCELERATES SPECULATIVE DECODING
Ziteng Sun' Google Research zi zitenguung
Uri Mendlovic* Google Research urimende
Yaniv Leviathan Google Research leviathan@
Asaf Aharoni* Google Research asafaharoni
Jae Hun Ro Google Research jaeroè
Ahmad Beirami* Google Research bei ramie
Ananda Theertha Suresh Google Research theerthae
ABSTRACT
Speculative decoding is an effective method for lossless acceleration large lan- guage models during inference. It which are then verified in parallel by the target model, and provides guarantee that the output distributed identically to a sample from the target model. In prior works, draft verification is performed independently token-by-token, Sur- prisingly, we show that this approach not optimal. We propose Block Verifica- tion, simple draft verification algorithm that verifies the entire block jointly and provides additional wall-clock speedup. We prove that the proposed mechanism is optimal in the expected number of tokens produced each iteration and specifi- cally is never worse than the standard token-level verification. Empirically, block verification provides modest but consistent wall-clock speedups over the standard token verification algorithm of 5%-8% a range of tasks and datasets. Given that block verification does not increase code complexity, maintains the strong loss- less guarantee of the standard speculative decoding verification algorithm, cannot deteriorate performance, and, in fact, consistently improves it, it can be used good default in speculative decoding implementations.
fast model to draft block of tokens
INTRODUCTION
Large language models (LLMs) (Chowdhery et al., 2022; Touvron et al., 2023; Achiam et al., 2023; Gemini Team et al., 2023) are often decoded through autoregressive sampling, where generating tokens requires & costly serial evaluations of the model. To improve generation latency, Leviathan et al. (2022) proposed speculative decoding, which enables an LLM to generate several tokens con- currently. In each iteration, conditioned
the current decoded prefix, guess of the next block of y tokens made by fast drafter (e.g., a small model or heuristic). Each of the resulting ? + prefixes then evaluated by the large target model in parallel. To guarantee that the final output follows the same distribution as that of the large model, some of the generated tokens are accepted while others rejected. The accepted tokens! are then appended to the prefix, and the process repeats until generation ends. See Figure and Algorithm 3.
In Leviathan et (2022), the drafts are verified through sequence of token-level rejection steps. More specifically, given prefix c, let X2, X., be one sample block of length 7 from the draft model M., where Vi < 7, X; ~ MM(- c, Xi=1). j. Using the conditional distributions under the target large model Mr, returned by the parallel evaluation step (vO < 7. MM(- c, X*)) the algorithm iterates over the draft tokens sequentially, and accepts each token X, with probability
min {1, Mo(X; xxxi M, c.Xi
(1)
All emails @ @google le com. With extra token sampled from either residual distribution the large model distribution.

---

Published as a conference paper at ICLR 2025
Tomorrow, the weather
will be mostly cloudy
Sample block of tokens from small model
Evaluate draft with large model
Prefix
Next iteration not S.O.S.)
Draft verification and correction
Add to the prefix
Tomorrow, the weather will be sunny
will be meetly sunny
Figure 1:
One iteration of speculative decoding (Algorithm 3). The prefixes and verified tokens are in blue, the unverified tokens from the draft model are in red, and the tokens sampled from the residual distribution are underlined.
The process continues until a token is rejected, at which point an extra token is sampled, for free, according to residual distribution (see Algorithm I and Leviathan et al. (2022) for more details). We refer to this algorithm as Token Verification. Since introduction in Leviathan et al. (2022), this ooken-by-toker verification procedure has been the standard for follow-up works (see Section 7).
In this work, we make the surprising observation that the standard token verification algorithm, not optimal, and propose strictly better method. Our key observation is that we can increase the number of accepted tokens, while maintaining the identical distribution guarantee, by jointly verifying the entire block of draft tokens instead of verifying each token independently. Our proposed algorithm, which we call Block Verification, has the following advantages:
Simple to The algorithm is plug-and-plan replacement of the standard token verifi- cation algorithm of speculative decoding. It does not incur additional computation or code complexity costs. See Algorithms and 2 for side-by-side comparison.
Identical distribution. Importantly, our method is not an approximation and maintains the identical distribution guarantee of speculative decoding (Theorem 1).
Optimal improvement. With the same drafting model, the speedup of block verification is no worse than that of standard token verification. Moreover, we show that block verification is optimal verification procedure (Theorem 2).
We empirically test block verification and compare with the standard token verification on a range of tasks and datasets. We show that our algorithm consistently improves over block efficiency (i.e. the expected number of generated tokens) by 7%-10% and overall empirical wall clock times by 5%-8% (see Table 1). Notably, our algorithm provides improvements only through the verification phase of speculative decoding, and hence the improvements can be combined with improvements obtained from other works that aim at improving the drafting phase. Since these improvements come for free, our block verification algorithm can be used as the draft verification algorithm by default in speculative decoding implementations.
2 A MOTIVATING EXAMPLE
The standard token verification algorithm stochastically rejects draft tokens with a higher probability from M, than from M₁. This is necessary to guarantee that the generated tokens follow the same distribution that of MM, Our main observation is that considering whether to reject a block of draft tokens jointly, instead of one-by-one, can result in accepting more tokens. We now illustrate this through simple example.
Consider the following trivial language model whose token space consists only 2 tokens: A and B. Further, assume that both the large model My and the small model M, context- intexxtinddeenndent, and specifically that Ve.
M =
Ma(B) 2/3,, M.(A) = 2/3, M.(B)= 1/33.
2

---

Published as a conference paper at ICLR 2025
In this setting, token verification will accept each draft token X independently with probability x = B and 1/2 if X = A. With a block size of y = 2, since the total variation (TV) dis- tance drv (M,, M,)) 1/3. the expected number of accepted tokens* from M, with the token verification algorithm is 1 - 1/3 + - 1/3)² = 10/9 (see analysis in Leviathan et al. (2022)).
An ideal algorithm with full information. Suppose an algorithm can decide on what tokens to accept from MM based on the full joint distributions of both tokens, i.e.,
Ma(AA) = 1/9,
MM(AB)=
2/99,
Mb(BA) = 2/9,
MM(BB) = 4/9,
(aAA 4/9, M,(AB) = 2/9, M,(BA) 2/9, MB 1/9.
The algorithm would have performed the following improved acceptance logic: always accept X, when X2X₂ = AB, BA, or BB since M,(X, 2 MM X2), and accept AA with probability (c(AA)/M,(AA) =1 1/4 (correcting the samples BB). The expected number of accepted tokens from M, now becomes: 2(M, + (BA) + (BB + 1/4 x M.(A)) = 12/9 > 10/9. This illustrates the benefit of considering the distribution of draft blocks jointly.
Verification with partial information. In general the full distribution over the next block of tokens intractable to calculate. Instead, we only have access to the conditional distributions of the next token along the sample path of the draft block, MMs-- emphasize, the ideal rejection logic does not need access to the full distribution, but care is needed in properly assigning the residual distribution. Our block verification does exactly this, as follows.
M,, c, X for various i's. To
For the simple toy example describe above, we propose the following improved algorithm, which is simplified version of the general block verification algorithm stated in Algorithm 2. When the draft tokens X2 = AB or BB, Pr (Accept X2) = similar to the idcalized algorithm. When X2 = AA, Pr (Accept X2) 1/4, and else the algorithm rejects both tokens and only corrects the first token to B since the algorithm doesn't 't have access to Ma B). When X2X, BA, it always accepts B, and then accepts A with probability 1/2 (else it corrects the second token B). Importantly, the marginal distributions of the generated tokens at the first token and the second token are always Ms(-). Moreover, the algorithm only uses distributions that are conditioned on the sample path of the draft block, and hence it works in the partial information setting. We then simply add the generated tokens to the prefix and proceed to the next iteration. The expected number of accepted tokens is 2 x (M,(AB)=a + M,, (BB) + (1 + +122) x M, +1/4 2 x M,,AA) = 11 /9, which better than the 10/9 obtained by token verification. This example proves the following result:
Lemma 1. The standard token verification algorithm of speculative decoding is not optimal.
Note that while the expected number of accepted tokens in the example for block verification (11/9) higher than that of the standard token verification algorithm (10/9), it is still less than that of the ideal algorithm with access to the full distribution (12/9). In Section 4, we show that block verification is indeed optimal in the partial information case, with natural assumptions.
3 BLOCK VERIFICATION
In this section, we extend the above intuition to develop a general block verification algorithm, which works for standard speculative decoding with partial information. The high-level idea is couple the acceptance of each draft token with other draft tokens. To do this, the algorithm considers draft sub-blocks with different lengths, and decides whether accept each sub-block independently. The final accepted draft block is the longest accepted sub-block in the above process. The acceptance probabilities for each sub-block and the residual distributions are carefully chosen to maintain the distribution guarantee of the final output, and achieve optimal speedup.
See Algorithm for a sketch implementation of block verification, and Algorithm I for sketch implementation of the standard token verification for comparison. Note that the inplementations follow the same overall structure (the differences are highlighted).
This is different from the number of generated token in one iteration, which is the number of accepted takens plus (corrected token).
3

---

Published as a conference paper at ICLR 2025
Algorithm Token Verification
Algorithm 2 Block Verification
Input: Draft block X"; small model distribu- tions Vi < 7, M.(: C, xx):: large model distributions Vi 5 7, Ma(: c, X*).
Input:
Draft block X"; small model distribu-
tions < y, M-M- c, X"); large model distributions vi S 7: Ma( c, X*).
1: Sample 171 7h ~ (0, 1).
1: Sample ,,,,..... 7/ ~ (O0, 1).
2: Set 0.
2: Set 0, Po
3: for = 1,...? do
3: for i = 1.... do
4: Set pt = min min(p:1 Ms(X,lc.X'')
- 1}.
4: Set 1, 11token min M,(X,le.X'-)
M. 1).
5: Set Abuuck as in Equation (5).
5:
if 1) S Moken then
if 1/s S h hblock then
6: Set =
7: Set T =
7: else
8: else
8: break.
9:
continue.
9: end if
10: end if
10: end for
11: end for
if m==7 then
12: if of==n then
12: Sample Y from Mol. X²).
13: Sample Y from Ma( |ee X²).
13: else
14: else
14: Sample Y from ploenn( (- c, X7) in
Sample Y from p plocck( (- c, XT) in
Equation (3).
Equation (4).
15: end if
16: end if
Return X²
Return X", X",Y. Y.
Residual distribution in Algorithm (Line 15): Vx E X,
c, x. Max M, c, X'),
Pres
token
(x c, Evex Mo(a' c, Ma x))
(3)
Residual distribution in Algorithm (Line 15): Vo E
block (a c. x²) max
{
Pi Mosx c, X²) - M,( X'),0)
Pres
EEE max Pc .Mo(x' c, x, M, cx)'),
(4)
Acceptance probability in Algorithm 2 (Line 5): hblock Pyy and when < 7
Evex max(p: Mop('' c, xx) - -Ma(x' c, xx),) Ex'Ex max Mo(x' c, X.) M,(a' c, X²), 0) +1-
block h
(5)
Figure The acceptance probabilities and residual distributions in Algorithms and
Importantly, token verification stops as soon as token is rejected (the break in Line 9 of Algo- rithm 1), while block verification always operates on the full block. Equivalently, in token verifi- cation, - arg min < [[oken] while in block verification, = arg max (17 < h.block). This difference makes block verification tend to accept longer sub-blocks compared to token verification, resulting in higher block efficiencies. In Figure 3, we plot the empirical complementary CDF of the acceptance length for both algorithms with the toy models introduced in Equation (2) to demonstrate this.
See Algorithm for the outer loop of the speculative decoding algorithm, which remains unchanged for both verification methods. See Figure for additional definitions. See Appendix A for sketch Python implementations. Due to the simplicity of the change, the algorithm can be easily imple- mented without incurring additional code complexity in practical systems.
4

---

Published as a conference paper at ICLR 2025
Token Verification
Block Verification
Frequency
0.6
0.4
0.2
0.0
1
2
5
6
7
8
9
10
Figure 3: Empirical complementary CDF of 7 for both algorithms with draft length 7 10. The draft and target models are the context-independent toy models introduced in Equation (2).
Algorithm Speculative decoding (SPEcDEC) (Leviathan et al., 2022)
Input: Prefix target model Ma, draft model M,, Draft length 7, Verification algorithm VERIFY.
1: while E.O.S & (XT,Y) do
2: Sample X XI...., , X. MM(- c) using autoregressive sampling, keep the conditional
probabilities at each step Mas- c, X*) for ...... y-
{Obtain draft block.)
3: Call the large model Mr and compute conditional probabilities M&( c, X*)
for = 0, o. 7 in parallel.
(Parallel scoring.)
4: Get the accepted tokens with draft verification
{Draft verification and correction.)
X Y VERIFY(X?, (Ma(- x))) (Ma(- X
5: c
{Add decoded tokens to the prefix.
6: end while
Theoretical guarantees. Speculative decoding with block verification preserves the distribution of its outputs (Theorem 1). Moreover, block verification achieves the optimal speedup among all valid draft verification algorithms in the outer loop of speculative decoding (Algorithm 3), resulting in a strict improvement over the standard token verification (Theorem 2). We defer the formal statements and the intuitions the parameter choices in Algorithm 2 to Section 4.
THEORETICAL GUARANTEES
In this section, we present the formal theoretical guarantees of block verification. Notably, that produces the correct distribution and that it is optimal in terms of the expected number of generated tokens. Let M (. e) denote the distribution of the sequence up to the end of the generative process under model M and context c.
Definition 1 (Valid draft verification algorithm). A draft verification algorithm VERIFY takes the draft block X", small model distributions and large model distributions along the sample path, namely Vi < 7, X²)) and vi < M, X') inputs, and outputs prefix X of X2, and an additional token Y. VERIFY said to a valid draft verification algorithm Vc, models Ms, and block length 7, the outputs of Algorithm 3 (SPECDEC) with verification algorithm VERIFY satisfy
SPECDEC(c. M,, Mc, VERIFY) ~p Mā( cc)²
(6)
i.e. the distribution of the outputs is preserved.
Note for example that the standard token verification algorithm is a valid draft verification algorithm (Appendix A. in Leviathan al. (2022)).
We ~pp denote that two distributions the same.

---

case can be obtained by an induction Published as a conference paper at ICLR 2025
We now claim the following:
Theorem 1, Block verification (Algorithm 2) is valid draft verification algorithm.
In other words, speculative decoding with block verification preserves the distribution of the output sequence.
We now further claim that block verification is optimal for all valid draft verification algorithms'.
Theorem 2. For i > O, let (()) be the number of decoded tokens after i iterations in Algorithm 3. For any valid draft verification algorithm VERIFY in Defimition I, we have Vc, May Ma. % and i,
BLOCKK VERIFY (N() 2 EVERIEY (N(1),
where the randomness is over the randomness of the draft block and the randomness of the algo- rithm.
In particular,
BBLOCKVERIFY (N(1)] ETOKENVERIYY (N()].
In other words, among all valid verification algorithms, speculative decoding with block verification decodes the highest number of tokens in expectation in fixed number of iterations. Note that since the computation overhead added by block verification is negligibly small, this establishes the overall optimality of the block verification algorithm. In particular, block verification provides greater speedup than the standard token verification. We defer the proofs to Appendix B. Below we give intuitions on the algorithm changes that contribute achieving the above guarantees.
Intuition on parameter choices and thcoretical guarantees. The key quantities for achieving the speedup and distribution matching guarantees are p.'s. In Lemma in Appendix B.1, we show that P: corresponds to the probability that the sub-block X will be kept in the final output. This is guaranteed by choosing the per-step acceptance probability properly since block verification keeps the longest accepted sub-block. Next we discuss how contribute to the distribution matching and optimality guarantees.
Distribution matching guaraniee (Theorem 1). To start, we ignore the minimum operation in the recursive definition of pt's. In such case, each p; is simply Mo(X c)/M,(Xi c). which is an upper bound on the actual p3 s.. As shown in Lemma 3, for any X", the probability that it is in the accepted block is MM )p,)), (M)())),,XX) (X'). Since the draft block X' generated with probability (x'' c). this guarantees that the probability of getting X' by accepting it from the draft will be at most M c), and hence the algorithm is not accepting X' more than needed.
The remaining part is to choose suitable residual distribution plus pblock's ' that the distribution the next token follows Ma(. X'). Note that for any possible next token x, (X*,x) could also be obtained by accepting X when X;+1 = x. with a probability of MX(X., .))p4 (X ,.). which should be subtracted to obtain the residual mass on (X*, This leads to the choice of p block in Equation (4) after proper normalization.
Optimality guarantee (Theorem 2), For optimality guarantee, the main proof is to show that for any prefix X in the draft block, (X²) is the maximum probability that valid verification algorithm can accept X which is stated in Lemma 4. This implies that in one iteration, block verification accepts the most tokens in expectation, and the argument.
To see that why P. (X') is the upper bound on the acceptance probability, we show that this is necessary to guarantee that for any prefix X that could be obtained from multiple draft sample paths, the distribution over subsequent tokens are always the same Ms(- c, X*). This enables block verification to be used plug-and-play replacement of token verification in the outer loop of speculative decoding (Algorithm 3).
'We use B1.OCK B1.OCKVERITT VERIFY and TOKEN to denote block verification and token verification respec- tively when convenient.

---

Published as a conference paper at ICLR 2025
Finally, we note that the optimality guarantee holds for all verification algorithms that can be used in Algorithm as is. Specifically, there exist verification procedures that force the decoding logic to depend on the previous accept/reject decisions that produce more accepted tokens in average in one iteration. However, this will affect the decoding speed in subsequent iterations. In Appendix C, we present such an algorithm and name it greedy block verification. We empirically observe that block verification consistently outperforms it, so we include it mainly as a theoretical result.
5
EXPERIMENT SETUP
We conduct experiments using PALM-2 models (Chowdhery al., 2022), and Vicuna models (Chi- ang et al., 2023).
PALM-2-S as the large target model and PALM-2- XXS / PALM-2-XXXXS as the small drafter model. The order of the sizes of the models is PALM-2- XXXS PALM-2-XXS PALM-2-S. We evaluate prompts from wide range of datasets and lasks, including language modeling with one-billion language benchmark (LMIB) (Chelba et al., 2013), ChatGPT prompts sourced from LearnGPT (GPT Prompt) (Rashad, 2023), reasoning ques- tions (WebQA) (Berant et al., 2013). physical commonsense reasoning questions (PIQA) (Bisk et al., 2020), scraped conversations with ChatGPT (ShareGPT) (Rashad, 2023: RyokoAI, 2023), summa- rization tasks (XSum) (Narayan et al., 2018), grade school math problems (GSM8K) (Cobbe et al., 2021), and German to English translation (WMT DeEn) (Bojar et al., 2014). For all datasets, we decode the first 1000 prompts using max input prompt length of 512 2 and decode up to 128 output tokens. We use a batch size of I in all experiments except for the experiments in Appendix D.1. Note that since our method only modifies the verification phase of the algorithm and doesn't 't introduce additional draft tokens, the speedup we get is independent of the batch size. We use a temperature of 1.0 for the experiments on PALM-2 models.
For the experiments PALM-2 models,
For Vicuna family of models (Chiang et al., 2023), we conduct the set of experiments in Spec-Bende (Xia et al., 2024). We discussed detailed settings for these expereiments in Section 6.2.
RESULTS
We focus our main experiments on the comparison between block verification and token verification. Recent works (Sun et al., 2023; Miao al., 2023) have extended speculative decoding to the case with multiple draft blocks to improve block efficiency. However, these methods also increase the required computation from the large model verify the drafts, which is undesirable when query batching is performed. We empirically show that our method outperforms these methods in the large batch setting even with only draft block. We defer the results Appendix D.1 and focus on the one draft case in the main section below.
6.1 EXPERIMENTAL RESULTS ON PALM-2 MODELS
We empirically compare speculative decoding with block verification to speculative decoding with token verification, and find that block verification provides small yet consistent improvements in wide range of settings, both when measuring idcalized block efficiency and real world wall clock time.
Block efficiency measures the speedup in an idealized settings where we neglect the evaluation time of the draft model and assume that we have enough compute capacity for evaluating the large model on all draft prefixes in parallel. Specifically, it measures the average number of decoded tokens per serial call to the target model. We observe consistent improvements for all datasets and draft models. For y 8 with PALM-2-XXS the drafter, the improvement in block efficiency ranges from 7.00% to 10.06% with an average of 8.30%.
We also observe consistent improvements in wall clock time, which measures the actual speedup, including all the real-world overheads. See (Leviathan et al., 2022; Chen et al., 2023a) for a more de- tailed discussion of these overheads. For 7 with PALM-2-XXC XXX the drafter, the improvement in block efficiency ranges from 3.36% to 8.14% with an average of 6.49%. The detailed numbers for this setting are listed in Table 1.

---

Published as a conference paper at ICLR 2025
Table 1: Speedup comparison between token verification (TOKRNV) and block verification (BLOCKV) with = 8 with PALM-2-S as the target model and PALM-2-XXS as the draft model on various datasets and tasks. We list the average and standard deviation across 3 runs with different seeds on 1000 test prompts.
Block efficiency
Wall clock time speedup over baseline
Dataset
TOKENV
BLoCKV
Improve.
%
TOKENV
BLOCKV
Improve. %
LMIB
3.21 0.01 3.49 + 0.02 8.68 + 0.79
0.01 2.32 0.01
6.85 + 0.74
GPT Prompt
3.41 = 0.04 3.76 +: 0.02
10.06 + 1.66
2.30 + 0.02
2.48 0.01
8.14 + 1.55
WebQA
3.44 = 0.01 3.70
7.53 : 0.24
2.32
2.45
5.75 + 0.22
PIQA
3.40 = 0.02 3.600
8.30
2.09
6.52 2.40
0.58
ShareGPT
3.34 = 0.01 3.02
8.98
2.25
2.00
6.98
XSum
3.49 0.02 3.76
7.63
2.35
2.49
0.88
GSM8K
3.81 = 0.01 4.15
8.74
2.55
2.73
6.84
WMT-DeEn
3.19 0.01 3.41 + 0.02
7.00 + 0.78
2.15+0001
2.27 0.01
5.36 + 0.73
Average
3.41
3.70
8.30
2.30
2.45
6.49
The effect of draft length 7, We also perform comparisons of the algorithms for other block lengths (7 and y 6) and observe consistent improvements. We plot the average improvement over all datasets in Figure with the numbers in Figure 4. With the same drafter, the relative improvement of block verification over token verification increases as y increases. This is consistent with our intuition since when = 1, the two algorithms are the same and as increases, block verification would benefit more from coordinating the acceptance rule considering the realization of all tokens in the draft block.
As shown in Figure 4, similar to token verification, the block efficiency of block verification in- creases as increases. However, the wall clock speedup peaks at a certain draft length (? 4 or y = for all settings) due to the increased computation cost in the verification phase. Hence we focus y < 8 in our experiments.
The effect of the drafter. We also consider the effect of the quality of the drafter on the improve- ment. In Figure 4, we list the average block efficiency and wall clock speed up under different draft lengths for both drafters. Note that PALM-2-XXS is larger model than PALM-2-XXXS, and hence better drafter in terms of quality, as demonstrated by the better average block efficiencies in the table. In Figure 5, we plot the average improvement under different drafter models, PALM-2-XXS and PALM-2-XXXS. The improvements hold for both drafters. And the relative improvement in block efficiency under PALM-2-XXS greater than that under PALM-2-XXXS. This shows that the improvement obtained from block verification can be combined with the improvement the quality the drafter, and the improvement might be more significant under better drafters.
Detailed results for experiments performed with different drafters, different datasets, and different draft lengths are listed in Appendix D.
6.2 EXPERIMENTAL RESULTS ON SPEC-BENCH WITH VICUNA MODELS
We also conduct the set of experiments proposed in Spec-Bench (Xia et al., 2024) with Vicuna fam- ily of models (Chiang et al., 2023). The benchmark includes various generation subtasks including multi-turn conversation, retrieval-augmeened generation, summarization. translation, question an- swering, and mathematical reasoning. See Xia et al. (2024) for a detailed discussion of the subtasks. For all experiments in this section, we use a single NVIDIA H100 GPU with batch size of I and a as the target model and Vincuna-68M as
max generation length of 1024. We use Vincuna-B--vi the draft model. To study the effect of temperature, we consider temperatures in {0.2, 0.6, 1.0] and fix 7 8. The results are listed in Table 2. The reported numbers the average of 3 runs.
8

---

Published as a conference paper at ICLR 2025
TOKENV
BLOCKV
?
Drafter
BE
WS
BE
WS
8
BE, XXS
WS, XXS
4
XXXS
XXS
2.89
2.35
2.36
2.44
2.99
2.43
2.43
2.50
Improvement
6
7
WS, XXXS
XXS
3.23
2.43
3.43
2.54
5
6
XXXS
2.50
2.39
2.63
2.50
8
XXS 3.41
2.30
3.70
2.45
3
XXXS 2.57
2.28
2.73
2.40
Draft length y
Table on average block efficiency (BE) and wall clock speedup (WS) across all datasets for token verification (TOKENV) and block verification (BLOCKV) V) with dif- ferent 7. The large model is PALM-2-S and the drafter model either PALM-2-XXS (XXS) or PALM-2-XXXS (XXXS).
Figure 4:
Figure Average relative improvement of block verification over token verification in block efficiency (BE) and wall clock speedup (WS) across all datasets for different drafters and draft lengths.
Our algorithm obtains consistent improvement compared token verification (up to 8.7% in block efficiency and up to 6.7% in wall clock speedup) across different draft lengths for all temperatures bigger than 0. This demonstrates the applicability of our method for different families of models.
The effect of temperature. Note that for temperature of O, which corresponds to greedy decoding, our algorithm degenerates token verification and doesn't provide additional speedups. In non-zero temperature settings, the advantage is consistent and the additional improvement is higher for larger temperatures. The observation is consistent with the intuition behind the algorithm, which obtains improvement on block efficiency by coordinating the randomness in the acceptance decisions at different token locations.
Table 2: Speedup comparisons between token verification (TOKENV) and block verification (BLOCKV) on Spec-Bench (Xia al., 2024) for temperature T {0.2, 0.6, 1.0]. We use Vieuna- 7B-v1.3 .3 as the target model and Vicuna-68M as the draft model. 8 for all experiments and each number is an average of 3 runs.
Block efficiency
Wall clock speedup over baseline
T
TOKENV BLOCKV Improve. 1 % ToKENV BLOCKV Improve. %
0.2
2.75
2.85
3.72
1.22
1.24
1.66
0.6
2.75
2.90
5.32
1.23
1.29
4.24
1.0
2.79
3.04
8.70
1.27
1.34
6.07
7
RELATED WORK
Parallel decoding. Our work improves speculative decoding (Leviathan et al., 2022), framework for decoding several tokens concurrently. Draft and verify (Stern et al., 2018) was an earlier work, which proposed to independently predict and decode several tokens in parallel, for the greedy de- coding case (zero temperature). Speculative decoding has later also been proposed in Chen et al. (2023a).
Single draft improvements. There have been many works aiming to improve speculative decoding without making of more than decoding draft. In Table 3, we list set of works in the draft and verify framework with a breakdown of their drafting and verification algorithms. See Xia al. (2024) for comprehensive study. In the single-draft case, several works have worked

---

Published as a conference paper at ICLR 2025
Table 3: Recent works based the draft and verify framework. Temperature 0 refers greedy
decoding and non-zero temperature refers to sampling.
Work
# drafts
Temp.
Drafting
Verification
Stern et al. (2018)
1
parallel softmax layers additional text
token matching
Yang al. (2023)
1
token matching
Leviathan ct al. (2022)
1
0
small LM
VERIFY
(Algorithm I)
Chen et al. (2023a)
1
0
small LM database retrieval cascade of small LMs hierarchical drafters distilled small LMs distilled small LMs parallel softmax layers layer skip
TOKENVERIFY (Algorithm I)
He et al. (2023)
O 2000 IV IV
TOKENVERIFY (Algorithm 1)
Chen et al. (2023b)
1
TOKENVERIFY (Algorithm 1)
Sun et al. (2024)
TOKENVERIFY (Algorithm 1)
Zhou al. (2023)
TOKENVERIFY (Algorithm
Liu et al. (2023)
TOKENVERIFY (Algorithm 1)
Gloeckle et al. (2024)
TOKENVERIPY (Algorithm
Zhang et al. (2024)
TOKENVERIFY (Algorithm I)
Elhoushi et al. (2024)
early exit
TOKENVERIFY (Algorithm
This work
1
I I
small LM
BLOCKVERIFY (Algorithm 2)
Sun et al. (2023)
22
small LM
SpecTTr
Miao al. (2023)
12
MMMM
0
small LM
multi-round TOKENVERIFY
Li et al. (2024)
122 2
0
small LM
multi-round VERIF multi-round TOKENVERIFY
Chen al. (2024)
22
small LM
on improving the drafting phase of speculative decoding (He et al., 2023; Chen et al., 2023b; Sun et al., 2024; Zhou et al., 2023; Liu et al., 2023; Gloeckle al., 2024; Zhang et al., 2024; Elhoushi et al., 2024). However, these algorithms all use the same token verification algorithm. Our proposed block verification algorithm be used in tandem with the drafting techniques in Table 3, yielding combined gains. We leave more systematic study of the improvement of block verification in these cases for future study.
The only other work that we are aware of that improves the verification step in speculative decoding the independent work of Hu and Huang (2024), which uses tree Monte Carlo improve specu- lative decoding in the single draft case, and have proved that their algorithm improves over token verification. On the contrary, we prove that our algorithm achieves the optimal speedup among all valid verification algorithms, including theirs. Our algorithm also requires minimal changes to the original token verification algorithm, making easy to implement and adapt everywhere practice.
Multiple drafts. Recently, speculative decoding is extended to multiple drafts (Sun et al., 2023; Miao et al., 2023) and new verification algorithms for the multi-draft scenario are proposed (Li et al., 2024; Chen et al., 2024). While increasing the number of draft sequences has shown to improve the overall speedup. comes the cost of more computation. In Appendix D.1, we show that in the large batch setting, where the inference is less memory bound, our method outperforms these methods without increasing the number draft blocks. In all of these works, the verification algorithm is generalization of the token verification procedure. Extending block verification to the multi-sample case is an interesting future direction.
DISCUSSION
We showed that the standard token verification algorithm used by speculative decoding is not op- timal. Further, we proposed new verification algorithm, block verification and proved that it is an optimal verification algorithm. We also demonstrated empirically that block verification consis- tently outperforms token verification in range of tasks. While the theoretical proofs are somewhat involved, the actual implementation of block verification is not more complex than the standard al- gorithm (see Appendix A), and since our proposed algorithm only perform better, never worse, than the standard token verification algorithm (see Theorem 2), it can used as a good default in speculative decoding implementations.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
J. Achiam, S. Adler, S. Agarwal, I.. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303.0877: 2023.
Berant, A. Chou, R. Frostig, and P. Liang. Semantic parsing on Freebase from question answer pairs. In D. Yarowsky, T. Baldwin. A. Korhonen, K. Livescu, and S. Bethard, editors, Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1533- 1544, Seattle, Washington, USA, Oct. 2013. Association for Computational Linguistics. URL https: htt////aaaaanttotoo.ooeeao DD1/ 1160.
Y. Bisk, R. Zellers, R. Le bras, J. Gao, and Y. Choi. Piqa: Reasoning about physical commonsense in natural language. Proceedings of the AAAI Conference Artificial Intelligence, 34(05):7432- 7439, Apr. 2020. doi: 10.1609/aaii wta.:/aaii..440...... (34105.6239) URL httpa: / /ojs. aaai org. index. php/ BAL//AAT//ON wwA./aatiieeevvie..eee..e.aaaeaa
6239.
O. Bojar, C. Buck, C. Federmann, B. Haddow, P. Koehn, J. Leveling, C. Monz, P. Pecina, M. Post, H. Saint-Amand, R. Soricut, I.. Specia, and A. s. Tamchyna. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the Ninth Workshop on Statistical Machine Translation, pages 12-58, Baltimore, Maryland, USA, June 2014. Association for Computational Linguistics. URL http://////. www. aal.lleeeee web. org/ anthology /////////// /114-3302.
C. Chelba, Mikolov, M. Schuster, Q. Ge, T. Brants, P. Koehn, and Robinson. One bil- lion word benchmark for measuring progress in statistical language modeling. arXiv preprint arXiv:1312.3005, 2013.
C. Chen, S. Borgeaud, G. Irving, J.-B. Lespiau, L. Sifre, and Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01131 2023a.
Z. Chen, X. Yang. J. Lin, C. Sun, J. Huang, and K. C.-C. Chang. Cascade speculative drafting for even faster Ilm inference. arXiv preprint arXiv:2312. 1462, 2023b.
Z. Chen, A. May, R. Svirschevski, Y. Huang. M. Ryabinin, Z. Jia, and B. Chen. Sequoia: Scalable, robust, and hardware-aware speculative decoding, 2024.
W.-L. Chiang, Z. Li, Lin, Y. Sheng, Z. Wu, H. Zhang, L. Zheng. S. Zhuang, Y. Zhuang. Gon- zalez, I. Stoica, and E. P. Xing. Vicuna: An open-source chatbot impressing gpt-4 with 90%* chat- gpt quality, March 2023. URL http::ttp//./ /tssymmsss/////////////ssmm//s.. www./oogggg//o...ooooooooooooo/o /ttbbblggg////aa2ep -3-30--3--0000000000 30- -vina/./..
A. Chowdhery, S. Narang, Devlin, M. Bosma, G. Mishra, A. Roberts, Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman. Training verifiers to solve math word problems. arXiv preprint xriv:21100141668 2021.
M. Elhoushi, A. Shrivastava, D. Liskovich, B. Hosmer, B. Wasti, L. Lai, A. Mahmoud, B. Acun, S. Agarwal, A. Roman, A. Aly, B. Chen, and C.-J. Wu. Layerskip: Enabling early exit infer- ence and self-speculative decoding, 2024.
Gemini Team, R. Anil, S. Borgeaud, Y. Wu, J.-B. Alayrac, J. Yu, R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.1 1805, 2023.
F. Gloeckle, B. Y. Idrissi, B. Rozière, D. Lopez-Paz, and G. Synnaeve. Better & faster large language models via multi-token prediction, 2024.
Z. He, Z. Zhong, T. Cai. J. D. Lee, and D. He. Rest: Retrieval-baat speculative decoding. arXiv preprint arXiv:2311.088 0.2222, 2023.
Z. Hu and H. Huang. Accelerated speculative sampling based on tree monte carlo. In Forty-first International Conference on Machine Learning, 2024. URL htttpss//pperreviee.. forum? d=stMh 1 Sn2GG.
11

---

Published as a conference paper at ICLR 2025
W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez. H. Zhang, and I. Sto- ica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium Operating Systems Principles, SOSP '23, page 611-626, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400702297. doi: 10.1145/360000636113111
URL https: / /woi. wwg/10..///.oo 00t...111/1/1010.0.0.
Y. Leviathan, M. Kalman, and Y. Matias, Fast inference from transformers via speculative decoding.
In International Conference on Machine Learning pages 19274-19286. PMLR, 2022.
Y. Li, F. Wei, C. Zhang, and H. Zhang. Eagle: Speculative sampling requires rethinking feature uncertainty, 2024.
X. Liu, L. Hu, P. Bailis, Stoica, 2. Deng, A. Cheung, and H. Zhang. Online speculative decoding, 2023.
X. Miao, G. Oliaro, Z. Zhang. X. Cheng, Z. Wang, R. Y. Y. Wong. Z. Chen, D. Arfeen, R. Abhyankar, and Z. Jia. Specinfer: Accelerating generative 1lm serving with speculative inference and token tree verification. arXiv preprint urXiv:2305.0978. 2023.
Narayan, B. Cohen, and M. Lapata. Don't give me the details, just the summary! topie-aware convolutional neural networks for extreme summarization. ArXiv, abs/1808 1os/18888,,845, 2018.
J. P. Quirk and R. Saposnik. Admissibility and measurable utility funetions. The Review of Economic Studiex, 2902):140-146, 1962.
M. Rashad. Chatgpt-prompts, ChatGPT-prompts, 2023.
RyokoAL Sharegpt. https: http:///gggggggteeetaattttt////t 2023.
M. Stern, N. Shazeer, J. Uszkoreit. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31, 2018.
H. Sun, Z. Chen, X. Yang, Y. Tian, and B. Chen. Triforce: Lossless acceleration of long sequence generation with hierarchical speculative decoding, 2024.
Z. Sun, A. T. Suresh, J. H. Ro, A. Beirami, H. Jain, and F. Yu. Spectr: Fast speculative decoding via optimal transport. arXiv preprint arXiv:2310. 15141, 2023.
H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13977 13971, 2023.
C. Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
H. Xia, Z. Yang, Q Dong, Wang, Y. Li, Ge, Liu, W. Li, and 7. Sui. Unlocking effi ciency in large language model inference: A comprehensive survey of speculative decoding. In L.-W. Ku, A. Martins, and V. Srikumar, editors, Findings of the Association for Computa- tional Linguistics ACL 2024, pages 7655-7671, Bangkok, Thailand and virtual meeting, Aug. 2024. Association for Computational Linguistics. doi: 18.588 http:////222mfmmm finnaiiiining-aal.555.. URL https: /ttl://acllla aacalcllattt ha////alaannthhcoooooo
org/ 2024. 1..4....m Findings-aci... 456.
N. Yang, T. Ge, L. Wang, B. Jiao, D. Jiang. L. Yang, R. Majumder, and F. Wei. Inference with reference: Lossless acceleration of large language models. arXiv preprint arXiv:2304.0444 2023.
Zhang, Wang, Li, L. Shou, Chen, G. Chen, and Mehrotra. Draft verify: Lossless large language model acceleration via self-speculative decoding, 2024.
Y. Zhou, K. Lyu, A. S. Rawat, A. K. Menon, A. Rostamizadeh, S. Kumar, J.-F. Kagy, and R. Agar- wal. Distillspec: Improving speculative decoding via knowledge distillation, 2023.
12

---

Published as a conference paper at ICLR 2025
A PYTHON IMPLEMENTATION
In this section we provide sketch implementation of block verification (Algorithm 2) in Python. Note that these are meant for illustration purposes only and are not for practical use.
Let V
| be the size of the vocabulary. The inputs to the algorithm are:
ps: an (y+ 1) x numpy array with the distributions from the large model Ma(- |,, Xt); qs: an V numpy array with the distributions from the draft model M,(- c, X)): drafts: a length-y numpy array with the ids the draft tokens X";
def
ps: np.ndarray, qs: np. ndarray, drafts: np. ap.nrraray) -> list[int] draft_length, vocab_size qs. qs.shape qs. resiesize (draft_length-l,
vocab_size)) # Append zero vector
token_sequence [] # Will include the token sequence we return accept_probabillt
1.0 Acceptance prob. for each sub-block probability_ratios = ps qs
Add one token to indicate rejecting the sequence
vocab_plus_one = np.arange (vocab_size + 1)
for token_index, token_value in enumerate (xs)
Unnormalized residual probability
sampling_we hegpiigg_wiighhssstoooaaa_aaasa
np. np.maximum/
0, ps [stteeen_iddex] accept_probab.litt qs [token_index]]
Unnormalized pwtplpppippppaaa of rejecting the sequence
= accept_probabillt
sampling_weights /= np. sum (ttssssmppiggeiighhhha thosen_token np. random. choice (vocab plus_one,
prsampling_weightss
Update the sequence
if chosen_token < vocab_size:
Loken_sequence xs[:token_index]
[chosen_token]
Update the acceptance probability
accept_probabiityy min probability_ratios
Loken_index: token_value) * accept_probabilig
return moken_sequenn
For reference, here sketch implementation of the token verification algorithm (Algorithm 1):
def leken_verification
ps: ap adarray, qs: np. ag.ndraray, drafts: np. ap.ndarray) 1ist [int]: draft_length, vocab_size shape resize (draft_lengthh1, vocab_size)) # Append a zero vector. token_sequentee [] # will include the token sequence return probability_ratioos = ps /
token_index
vocab_range np. arange (vocab_size) for token_ in xs:
accept_prohat accept_probability = recbasssity_ratiosttte (token index, token_value, if (not np. isfinite np.random. random() () accept_probabllity # Rejection
or
break
token_index += 1
soken_sequent append bocken_vallse
Calculate the residual distribution
sampling_weights = aap.maximmm (0, ps [token_index] - qs [token_index)
sampl sampling_weights. /= np. (samp] weghsss)
13

---

Published as a conference paper at ICLR 2025
token_ (oken_sequence. append (ap. random. choice (vocab range, besapplingwwiihhee
return token coken_sequence
B FORMAL PROOFS
We start by setting up few necessary notations. Let X' be the space of output tokens. For f >> 1, we use M c) to denote the joint distribution of the next & tokens conditioned on the prefix under M. i.e. for all . E X², (M It c) I M(x; c. c. We use MM c) denote the distribution of the sequence up to the end of the generative process. Below first describe necessary and sufficient condition for valid draft verification algorithm in Algorithm 3.
Lemma 2. Ve, Ma, let X be generated from MG(- c). and
X = VERIFY(XT, {Ma(- |,, X') (Mo(- le,')
Let Z be generated from M "(,,,,",, VERIFY is valid draft verification algorithm (Definition 1) if and only if,, Ms.
KT,Y, ~p Mp+1 ( (c)c).
Proof. We first prove the forward direction (Equation (7) implies that VERIFY satisfies Definition 1) by induction on the maximum generation length of M&(- c). When the maximum generation length is for all new context c', we have the next token is point mass over E.O.S, i.e.
Mula c') 8(x E.O.S).
Then Equation (7) implies that VERIFY will only output E.O.S, which is the same Defini- tion 1. Suppose Equation (6) holds for all context and M, with generation length at most T, for context and Ms with maximum generation length at most T + 1, we have that the output of Mb. VERIFY) is
X Y, SPECDEC(((C XT, Y), Ma VERIFY).
Let カー- be the first 7 tokens from SPECDEc((,, X M), Ms, 7, VErIfY), and O" be the tokens after. Since X", Y is at least of length one, the generation length of Mo(- XT, ,Y) is most T. By the induction hypothesis, we have
-- up MM (.
and
o p
And hence by Equation (7),
Mr, VERIFY) = X", Y. (Y), VErIfY)
X", YT-T, 0
Pp MMM--110 c).
This completes the proof for the forward direction. For the backward direction, we have Equation (6) implies that for all X", Y,
SPECDEC((C, X", Y), Mo. Ms. 7. VERIFY)[: 7] ~p Mi ".,,,,,11"", Let - be draw from M (. XT,Y), then z ~p SPECDEC((e, X Mr, VERIFY)[:>-- --
We use v/i j] to denote the entries to in v.
14

---

Published as a conference paper at ICLR 2025
And hence when X Y is the output of VERIFY,
x YY 2 ~p X", SYSEEDDDEc((e, XT,),, ,), Ms VERIFY)[: -7]
Pp Mb, VERIFY) ( 7
<p (
where the last derivation follows from Equation (6) Definition 1.
In all proofs below, we fix the context c, and the models M, and Ma. We note that the proofs won't 't specific information about these choices and hence can be easily extended to all cases.
B. PROOF THEOREM
By Lemma 2, it would be enough to prove that block verification satisfies Equation (7). For simplic- ity, we often refer to the sequence YXT,Y,Z (,) by O Note that 0y+1 ~ MM5- | c, always holds since when
Y O,+1 Ma(. c, c*O by definition and when % 0,+1=Y = Mol. X²) = -Mo c, 03). Hence is enough to prove the following
ve 7, 7, E x., Pr = 2²) Mi c).
Note that in block verification, p; 's depend on the draft tokens X7, The following definition makes this explicit. Let p; be such that po 1, and V1 S sisM y, x, Xr,
pe(x* c) = min { pp-1
Ma(a; e, e Ma C, c,r-
(9)
For most cases, when the prefix c is clear, we will ignore and simply use pe(x*) pr(x" c). We will only make the prefix explicit when necessary.
We first state the following lemma the distribution of the number of tokens accepted by block verification.
Lemma 3. Let X MI c), and
X BLOCK (M. lc, (,,
Then have Vi S 7, and x' EX
Pr(r2i X x²) pi(x)).
We first prove Theorem based on Lemma and defer the proof of the lemma to Appendix B.3. We prove Equation (8) by induction on the time index When l 1. O₁ is either X1, or residual sample from phlock| (-1 where
max(Mo(r - M, c). block (- (c1c)= Σ.. max(MMol' c) MM(x'' c).03'
Pres
Hence we have Vx E X, by Lemma 3,
Pr Pr z)
=Pr = x, 2 1) Pr = =x,
Pr z) (r = + 2x) 2 =²)) plockk (x c)
=M,(x c) pz(x) + E..(E cc) - (1())) press (x:
min[Ma(e c), Ma( c)} + Σ max{Mo(z' () -)) cc,0) -
block (x (c)
(10)
min(Mo(z c), c)} + max(MM -) |
(11)
15

---

Published as a conference paper at ICLR 2025
where Equation (10) comes from the definition of p1 in Equation (9) and Equation (11) is due to
Equation (4) with = Hence the Equation (8) holds for = 1. Suppose Equation (8) holds
up to < 7. For l + we have Oş+1 is either equal to Xe+1 when 2 l +
sample from P p (- c, X²) when r = f, or a sample from Ms(- | c, c²O²) when < Hence
Pr (O = x +1) can be broken down below:
Pr = x² x
Pr (0ft1= x tt , 2(+1) + Pr = Pr +
= , <() (12)
For the first term (T 2 + 1), we have
Pr (0 x 12
Pr (T 2 2 x 1 (et11
-rr(x+t1 = = -
=Mo(o' |c) .min (2 MMb M, (c,0),
(13)
For the second term (T = f), we have
Pr (o x. T =))
= =Pr(X*= = x²) Pr (T = -Ix = =x²). -O+s
-
= -441 10' =
= Pr Px = x²) Pr (r el e|x
= =x")
black
(It+1 c,2²)
Pres
Note that,
Pr (T= = 8 x²= =²)
=Pr X = xt) - EM. (((2llc)))-((22211111 = x0
=o((a)) MMal e,a²) peti(a',
=p((x') Σ min(pe(a (Mllpe(('MMM(r c, M, c,
Σ max(pr (p -,,,) - Mc( c, c,
And hence by the definition of pblack (I1+1 I c, xx in Equation (4), we have
Pr (0ft1 = 1+1 - =
M,, (e) max(pe ( |c,x¹) M,, c, (,,,,))))))
(14)
For the third term < f), by induction, and the generation process O++1, have
Pr Pr(ot+1 x f+1 r E) Pr Pr = of, < E) Pr (Oe+1 x4+1 0c = <<() (Pr(O' = x²) -0) - Pr PO , f)) Mo(xe+1 1,,²))
(Mo(z' c) - -M(aa' cc)p((*)) Mos c,xl)
(15)
Plugging Equations (13) to (15) into Equation (12), we get var+1 E x+11,
Pr (0++1 = x =11 Mz (+] c),
completing the induction step and hence the proof of Equation (8) and Theorem
B.2 PROOF OF THEOREM 2
We first state the following lemma, which when combined with Lemma 3, shows that in one iteration, among all valid draft verification algorithms, block verification accepts each subsequence with the highest probability.
16

---

Published as a conference paper at ICLR 2025
Lemma 4. For draft verification algorithms that satisfy the constraints in Lemma 2, we have Vi S % and E X,
Pr (T 1r21 x x²) S Pi(x").
We defer the proof of the lemma to Appendix B.4 and first prove Theorem 2 based on the lemma.
We start by breaking down the expected number of decoded tokens EVERIEY (i) into the distribu- tion of (i) on different sample paths. Let O' O1, Oz..... be the complete output sequence from speculative decoding. We set all tokens after E.O.S be E.O.S as well. Then we have
EVERIFY (VERIFY[N())
E Pr (N(1) 2
E x'EXx
Σ t=1
Pr VERIEY
(=,,((()) 2
VERIFY
Hence it would be enough to prove the following.
Lemma 5. For all draft verification algorithms that satisfy the constraints in Lemma 2, we have Vc, and output x
Pr VERIFY
(0 x², (1) 2 e c)
Pr
(0 =0=x", (i) 2 c)
(16)
BLOCKVERIFY
We prove the lemma by induction on the number of iterations i. We first prove the following lemma for all verification algorithms.
Lemma 6. For all i S %
Pr (0" ==, VERIFY
Pr VERIFY
= c) MD (attlin c, x.)
Proof. When PRVVEIFY (0 = 18, el c) 0, the bound is trivial since both sides are 0. Other-
wise we have
Pr (0* , 2(
VERIFY
Pr (0++1:+ = -1: 0 = 2 T 2 c)
Pr VERIFY
(0'= I x((c)
Pr VERIEY
(0++1* = 2++1* 10 T
would be enough to show that
Pr VERIFY
= -(+1ix ( 10 = 2 =M (2l+1* | (17)
Note that
Mî (attli c,
Pr (0e+1:0 1 141: 10 =z(c)
Pr VERIFY
(0e+1:+ = 11+1* ,T 2 E O = x) + Pr - , =
VERIFY
Pr (T2 0f =x(c)) Pr
(Ott1i*= -ftla 10 -0-
VERIFY
VERIFY
+ Pr (<<el0- = = xe(c) Pr
(O l+l: 10t ==',T<,,,
< kc,)
(18)
VERIPY
VERIPY
When PRVERIFY (T < = =()c) = we have PRVERIFY (T 2 1'2
0 = = =x(c) = 1, and hence
Pr (0++1:- = 1++1= 1:0 10== x M3 (t:: lc,x²) VERIFY
When PIVERIFY (T < l 0 = 0 x' > 0. since VERIFY is a valid verification algorithm (Defini- tion 1). we have tokens starting from location + 1 is valid draw from Ms(- c, c, i.e.
Pr VERIFY
(0++1: f+:: 1 = x < <,))== = MI ( | lc,x
Plugging this into Equation (18) completes the proof.
17

---

Published as a conference paper at ICLR 2025
When i = 1, we have that (1) + 1, where is the number of accepted tokens. Hence we have
Pr (0 = , N() 2 c)
VERIEY
Pr (0" -0-=2" (0"==",, 2 ((
VERIFY
Pr
(0 = =x 101 ,22-1 M₁ (x |c, (c,
< Lemma 6
VERIFY
= -M,(x c)M3(x 1c, x
Pr VERIFY
(r2 1 X x =x--1.c) .))
c)) is the probability of the event that Of-1 x=-1 is contained in the accepted tokens, which happens under the joint of two events: (1) The first e - 1 tokens in the draft block from the small model X = x'-1 This probability is MM,
where the last equality is because PIVERIFY
c): (2) Conditioned on X = xf-1, at least l tokens accepted,
this is PIVERIFY (T 2 6 - 1 X x xf-1, ,c), and hence
Pr VERIFY
1- 7 2 l. - (c) -M(x c))
Pr (r l - 1 = =)) VERIFY
Similarly, we have
Pr BLOCKVERIFY
2
=Ma(= c)Mg(* c, l,,x
Pr BLOOKVERRFY
(-2 = ,c).
Note that Lemmas 3 and imply that for all verification algorithm, we have
Pr VERIEY
( | x) S
.)
Pr BLOCKVERIPY
(T f - =
Combining these, we have
Pr VERIEY
(0 = =2, elc)
Pr BLOCKVERIFY
=0'= (1)) 2 2 ecc).
(19)
Suppose the lemma holds for all iterations up to i, for the (i + 1)th iteration, let Ti+1 be the number of tokens accepted the (i 1)th iteration, we have
Pr (O" = = (i+ + 1) 2 c) VERIFY
Σ
Pr (0' = (() = E,, (( VERIFY
Pr (0' x-, ,()) c) Pr VERIFY
(T++1 2 1 2- - E)
VERIFY
Pr VERIFY
(0" = x² c) Σ Pr (N(1) = 0' cc,,c)
VERIFY
Pr VERIFY
(TH1 2 = N(i) =t)
=
=Molz*' (c) Σ Pr
(N(1) = l' | 0===" xx==",e)) Pr
(TH 2 l. 8-- -1 =2, = E)
=xi,N(i) (20)
VERIEY
VERITY
pst
Let T/VERIEY be a random variable distributed according to PIVERFY (N(1) E' -0 c), and
/VERIEY (1) Pr (T++1 2 2 - 17 |e =0=,, (() = 11).
VERIFY
Plugging these into Equation (20), we have
Pr (0" = x²' VERIFY
2 C) N(
-Mol"" |c) (VVRIEY(JVERII
Note that let C, C, ",, we have
fVERUY(1)
Pr (T++1 2 f - c.0'= =x,,=(" = =))
VERIFY
Pr
(T f - 17 Cy, 0-= 2*=i0i
(21)
VERIFY
18

---

Published as a conference paper at ICLR 2025
where Equation (21) is due to the iterative structure of speculative decoding and after generating O = x" in the first iterations (N( = 17), the next iteration is the same as generating from scratch with context C, C, z", Similarly, we have
JBLOCKVERIFY (11)
Pr BLOOCVVRIFF
(T 122-11 Cy. 0 =.
Note that Vc, x² X,, and have
PIBLOCKVERIFY =x", 2 Pr (T2 c, =x) = PIBLOCKVERIFY (0' =0=="" c)
BEOCKVERIRY
PIBLOCKVERIPY (0" = 22
M₁ |c)
PIVERIFY (0' =x= x", , c) 2
(22)
Mī |c)
Pr (r 2 C₂ = =x"),
(23)
VERIFY
where Equation (22) due to Equation (19) and that N(1) = 7 + 1. Equation (23) implies that
fBLOCKVERDYS (n) 2 fVERRYY (17), and hence we have
Pr (0" = = 1=t,,(((t 2((c) = Mo(x" B [fVERUY(()) VERIFY
S <Mol"
cc) By [/BLOCVERRY(Y)]]- (1)]
Note that PEBLOCKVERIY (O+ = x,,N," Ni 1) 2) = Mb(x") ee [BBLOCKVERIYY(N (7))- It would be enough to prove that
Bxpear [BBLOCKVERIEY (1)) S E Expuooevvaur ([LOCKVERRFY(D))]
(24)
Next we prove Equation (24) using the lemma below.
Lemma 7 (Quirk and Saposnik (1962)). Let f R - TR. be an increasing function and Xı stochas- tically dominates X2, meaning Vx, we have Pr (X1 2 x) 2 Pr(X2 2 x),, then we have
E[f(xi) 2 (X2)
By the induction hypothesis, we have VERIFY stochastically dominates (Quirk and Saposnik, 1962) I/VERFY for any valid verification algorithm. It remains to show that JBLOCKVERIYY (1) is increasing function. By definition, since 0 S r 7. when 1) < 8- 7 1, (BLocKVeRIev (1)) = 0 and when 77 8- 1, BBR.CCKVRRRE (1)
2, by definition and Lemma 3, When e 7 < 17 (x-+1ee- c, (,x")
) is an increasing c, c, by following the same recursion steps as in Equation (9) but replacing Pı (x-+1:t-1 x.) with Po (1 c,x"+1)= 1, and hence only increasing the values.
JBlOCKVERIFY (1)) = Pt p 11-1 c, To see that Pt-
function of for r/ 17 + 1, can obtain Pe-r' 1x-
(1'1+1:6-1 +1:6-1
This proves that fBLOCKVERIYY is increasing and hence Equation (24) holds. This implies that the induction step holds due to Lemma 7, completing proof of Theorem 2.
B.3 PROOF OF LEMMA
Note that in Line of Algorithm 2, p; (X').. We prove the statement by backward induction. When = 7, we have by definition of block in Figure 2, Vo E X7,
Pr 27 17/11 X = x²)
h
block py (x)))
19

---

Published as a conference paper at ICLR 2025
Suppose the statement holds for i 2 L. When i == = - 1, we have
Pr ( x
Σ M2(ae c,,, Pr (T 2 l - Xx =x)
nex
Ma c,.lt1) (Pr 2 2 x===
= x + Pr P = =x))
mEX
Σ M2 c,, (rr (r 2 fl x|x = = + Pr =0 h/book)
(25)
mEX
Σ Mo c,,--1) (pe(x²) + (1 pe(x))) hbla)))
xEX
E M.(uel (elle|/e,x/-1 (, -pe(x") + h
E
Malxel c, x2-1)-1(00 - -p((x())
tEE
ZEE
Σ 22Ex
Ma(ae | c, (,,t-11) pe(x") + h (1
Σ
Ma(ue c, c, (pe()))
(26)
Equation (25) above holds since T 6- happens under the joint event of < anddd Me-1 Note that in the definition of hbark (Equation (5)),
hhlack
Σ max (x (1--niaaa c, -, - Ma( c ).0}
Σ
c,,t-1) min(p:- (z Mo 1) c,,(-1))))
M = -Pe-1(x(-1) E minfpe- ( c, 1-1 (. M, | ,
Plugging this into Equation (5),
Pe- (x=-) E,
1)- 2, c
h h1-1
block
(27)
En min Mof-1)MMaa c, c, (z( c, 1,
Moreover, we have by the definition of Pe (x²).
Σ Mo(ae I c, (e(=))))p((())))))))))))))))))))
Σ
min min Mob | c, Ma c.alt)))
Σ (o- c, M,(o c, c, SEX
(28)
Plugging Equation (28) and Equation (27) into Equation (26), get
Pr 2 1- X = =d-1)) P pz- 1 (x0-1)
as desired. The lemma hence follows by induction.
B.4 PROOF OF LEMMA 4
Recall that O++1 denote the sequence (Xr, Y, ZT-T) in Equation (7). Without loss of generality, only consider of such that Pr (O = of) and Pr (x of) 0 since otherwise Pr (T 2 é X =²) is either zero or ill-defined. We break the proof into the two cases below. If Vi < it satisfies that ()-'''-'-aM c,,i-1)= < M,(a; c,, then we have in the recursive formula of p 's in Algorithm 2, we always have
Mo(x; c, x111
(x(x') = Pi-1(00-1 11
Ma xf11)
20

---

Published as a conference paper at ICLR 2025
and hence
Mo(a cc)
(=-1
M2 cc)
And for x², we have
pe(x*) minf Mo(at c))
Ma(x* 10) 1).
Note that
Pr (O' = x',7 T
=)) 2- - -M(d' (F)
Pr
Moreover, we have
Pr = , 2 e) < Pr (0' 00'= x = =Mola" 1c),
and
= -Mo(e') (c). Pr x''==',T22/ PPr (X = x²) Pr (T x =x -
Hence
( = = = Pr (r = 72
Mo(x² c)
< minl
Ms(xt 10:11 = =pelat)
Ma(r' c)
In the other case, there must exist some i such that pi- (x Mob((t c..it11 > Ma(ai
c, 1,,, then we have
pi(x') min Pi- (x' 1) C, 1,
M2 c, 11 = 1.
WLOG, let i be the largest such index. In this case, we have Vi < j < L. (xi-1) | -) S M,(zy| c, 1)) and hence
pe(x*) = p((xz) Mg (x c,,²)
Mg M c, c,,²)
(xit c,
- c, xه)
Moreover, by definition, we have
Pi-1 S 2i-2(11 Mo( C, c
M¹² (x-11 cc)
Mo C, 2) S ....5
S
M 1 (xt-1 lc)
and hence when P:_ 1 (I² -1 Me C, x1 > Ma(Is c,x²-1),
Mb c) M₁ -1 (2--1 1
c) Mr(2; c, c.
Mo(1; c, (.
Ms c) M (xr-1 c) My(a; c 2 (1-1((x"1)
MM(x; c, -. > 1.
Hence
(0'0'=x'p T 2 1) = Pr (x'= = x²) Pr (T 2 il X = x²=='x)))) = S Ma(a' |c) <)< <Mol'' [c), and
(0'= Pr (0' =''==='+<<>) = Pr (0' x²) - Pr Pr' = x², 2 Mo(s' - -M,(x" c)> 0.
Note that when 0 = x' 5 < i, by constraints in Equation (7), we have
Pr (0 = / ++ O' ='=,, = (x +16 |,,x')
This implies
(0'==z²) Pr (0' = x <i) Pr (0 - -pاtii 0 x²,T<<))
=Pr
+ +Pr = =', 2 i) Pr (0++1= + 10 = x',
, 2 i)
=Pr(O' =() -M,
Mf-1p (z +1 c,,²'
+Pr = x', r 2 Pr Pr (0+tl =1++1: 0'==''=
21

---

Published as a conference paper at ICLR 2025
Moreover, have
Pr(0'=z)) - M lc,x²)
Combining both, we get
1= Pr xx))=xx))
Mo(rt).M (x c,,r))
=Pr(T < O' = n²) + Pr + Pr Pr = x 0' === = 2
M₁ M l,,
= - - = 21) Pr |Pr(Ottie= = 10 = x', 222) -1) 1
M |c,x²)
and this implies that (note by assumption Pr (r O x²) *0),
Pr 20 x 0'= 2 1) M₁ (x |,,x).
(29)
Hence
Pr = 24, 2(1 S Pr = x², _22 i)
= =Pr(O' = s', T 2 1) Pr = O' = 2
M,(x' c)p [M, 1 |c,x²)
=Ma('' ccMM (x c,
IFPr(T = =x > (x()))), we have
Pr = x T 2 f) = Pr = (r = =x)
Ma(a' c))p(x+))
= =Ma(e' |c) M₁ (x c,
Mr (x c,
=M,(2') c)M (a (1 c,,'),
which leads to contradiction. This completes the proof.
C GREEDY BLOCK VERIFICATION
In this section, we show that it is possible to accept more tokens than block verification (Algorithm 2) in one iteration with a modification to the speculative decoding framework Algorithm that allows the decoding logic to depend on the previous accept/reject decisions. However, as shown in Table the resulting algorithm, greedy block verification, doesn't improve over block verification. We include the description and analysis of the algorithm as a theoretical result. The claims in the main paper holds independent of the results in this section.
We start by introducing the algorithm (Algorithm 4) and then discuss the necessary modifications to maintain the identity distribution guarantee.
The above greedy block verification algorithm has similar procedure as block verification (Algo- rithm 2) with differences in the setting of of acceptance probabilities and residual distributions, as highlighted.
Similar to Algorithm 2, Algorithm maintains list of probabilities ğt's, which satisfies that min(1, is the probability that the subblock X is accepted. h, 's are chosen achieve the above acceptance guarantee, and greeddy's are chosen to maintain the identical distribution guarantee.
Note that compared to P; in block verification, the recursive definition of P. doesn't 't have minimum over one term, hence it is always an upper bound on p, 's. This leads to a higher acceptance prob- ability for every subblock in greedy block verification (Theorem 3). However, Algorithm 4 cannot be used directly in the iterative implementation of speculative decoding in Algorithm 3. To see this, consider the simple example in Section 2. Greedy block verification will perform the following:
22

---

Published as a conference paper at ICLR 2025
Algorithm 4 Greedy block verification
Input: Draft block X7; small model distributions Vi < <,,Ma(. C, X'); target model distributions
Vi < 7; Ma(- (- C, X*).
1: Sample 171 ................................ 7/- ~ (0,
2: Set 0. Po
3: for i I..... 7 do
4: Set p. = P (.
le.
5: Set
Σ. ( M..
6:
if 7J < h4 then
7: Set
8: else
9: continue.
10: end if
11: end for
12: P7 Py M,
13: if
1/- < p, then
Set r = y. and sample Y from Ms(- c, X²).
15: else
16: Sample Y from groedy (. | x
as below:
max Pt
MMu e, - MM e;
Pres
peroedy (x c, x.
(30)
Σ Ex max
-Mol'' - |,,'),0))
end if 18: Return Y.
Accept X,X2 = AB, BA, BB with probability one, and sample an extra token from Ms(.). Accept X,X2 with probability 1/4 and sample extra token from M&(-). When X,X₂ rejected, accept no tokens and sample a correction token = B. Note that in this case, the algorithm Y as the context for the iteration and sample based on Ma. the next token will be A with probability 1/3. This makes the total probability of generating BA as the first two tokens
M, (BA) Pr (Accept BA) + M,(AA) Pr (Reject AA and Y B)Ma(A) 2/9 4/9-3/4--4- 3/4-1/3
=1/3,
which is higher than Ma(BA) = 2/9. This violates the identical distribution guarantee. Below we introduce a distribution modification algorithm, which can be used with Algorithm 4 maintain the identical distribution guarantee.
It can be shown that if X Y are returndd in Algorithm 4, and the next 7 1 tokens sampled according to Mnew from Algorithm 5, the identical distribution guarantee is maintained. In partieular, have the following lemma: Lemma 8. Let X M3(- c) be the draft tokens and X", Y be the output from Algorithu 4. Let Mnew be the modified distribution based on Algorithm 5, and - - (. cY Then have
new
K,, -
The proof is presented in Appendix C.3. The above leads to the following speculative decoding algorithm with greedy block verification, presented in Algorithm Note that Lemma implics that it maintains the identical distribution guarantee.
23

---

Published as a conference paper at ICLR 2025
Algorithm 5 Distribution modification
Input: Small model M₃; target model Ms: draft length 7 generated tokens from Algorithm XT,Y.
I: Let My be such that vi 5 I, and x' X", Nnew (z, ",,T,,,
max X',,,,, - X7, V,,),, EVEN M,, "1 ,2)
(31)
M, XY,
[Modify the distribution at rejected locations.)
and Vi - 1, and x' X3,
Mnew (zt c, C, Ma(a, |c,,,,,,"""
{Keep the distributions for future locations unchanged.)
2: Return Mnew-
Algorithm Speculative decoding with greedy block verification
Input: Prefix c, large model Mr, draft model M,, Draft length 7/..
1: while E.O.S (X Y) do
2: Sample XI,..., Xy M.(- c) using autoregressive sampling, keep the conditional
probabilities at each step MM c, X*) for = o
{Ohtain draft block.)
3: Call the large model M2 and compute conditional probabilities Mo( c, X
for = 0, l,.,,., in parallel.
{Parallel scoring.} }
4: Get the accepted tokens with draft verification
[Draft verification and correction.
X x', V VERIFY(X*, (Ma(. X (Ma(. c, )
5: e
{ (Add decoded tokens to the prefix.}
6:
M, t DISTRIBBUTONMOODIYYMM, 7y
{Modify target distribution.)
7: end while
C.I COMPARISON TO BLOCK VERIFICATION.
In draft iteration, with the same pair of draft and target distributions, greedy block verification is always better.
Theorem (Informal). In one draft iteration with the same models Ma: Ma and draft length % greedy block verification decodes at least many tokens block verification.
The theorem is proved in Appendix C.3. However, due to the distribution modification step, the target distribution might change after the first iteration, which might affect the expected number of accepted tokens. For example, in the Bernoulli example considered in Section 2, when the draft block Xj AA and they are rejected by greedy block verification. It can be shown that the modified distribution will be point mass token B. And in future iterations, if the algorithm still uses M2 as the draft model, there lower chance that the draft tokens will be accepted. Hence, theoretically it is unclear whether one approach dominates the other.
Empirical comparison. verification to compare the two approaches empirically. We list the block efficiency comparison when PALM-2-XXX is used as the drafter and = Table
conduct the same set of experiments in Section 6 on greedy block
we can see, while greedy block verification still consistently improves over token verification, the improvement is less significant compared to block verification. The trend is the same for wall clock numbers as well as other parameter settings. Hence recommend using block verification instead of the greedy version.
in cases where Mg is not the original large transformer model. Ma can be obtained by evaluating using the original large model, and then perform the modification in Equation (31).
24

---

Published as a conference paper at ICLR 2025
Table 4: Block efficiency comparison between among token verification, block verification, and greedy block verification with = 8. Each statistic is computed using 1000 test prompts from different datasets on various tasks (each run an average with different random seeds).
Dataset LMIB
Token Verification Block verification Greedy block verification
3.21
3.49
3.30
GPT Prompt
3.41
3.76
3.51
WebQA
3.44
3.70
3.52
PIQA
3.40
3.68
3.49
ShareGPT
3.34
3.62
3.44
XSum
3.49
3.76
3.59
GSM8K
3.81
4.15
3.96
WMT-DeEn
3.19
3.41
3,26
C.2 PROOF LEMMA
In the proof, we ignore the context e and the proof will generalize to arbitrary introducing two useful quantities.
We start by
Premain (x"):=
Σ max(MMorrr. M,(x1,x),0)
(32)
Prej Prej(x'):
Σ max(,M,('',a)) Mo(a',
(33)
Note that p; in Algorithm 4 depends on the draft block x², and by the recursive definition of p. 's, we
have P. Ma(z")
Hence we have
M2(
h1 Σ. Max c, - -M c, 0}
Premaiu (x*)
[ax c, X P.M
c, Xt), 0}
Piej (xx)
Moreover, the expression for 9; also implies that prreedy Equation (30) and Equation (31) resepectively).
XT)
-Mnew (: cxX (defined in
We now prove the following lemma about the acceptance length in Algorithm 4. Lemma 9, For all & E [1, 7), and x' E x
(2) M,
Proof. We prove this by induction in the backward direction. When v. Step 12-14 in Algo- rithm 4 accepts X2 with probability
Pr Pr = 1 x" =x") mmin(1, min I, Mo(a?) M.(x') S
and hence
X = =x)= min (M.(r"),
Suppose the equation holds for e to for lo 1, we have
Pr =00-1 Lu 1) = Pr (x - 7 to) + Pr (X 20o-1 to 1).
Next we consider the two terms separately. For the first term, due to the induction assumption, we have
Pr f0-1 1 , Eo)
Σ min(Mssaa00-1, 12), (x))=
25

---

Published as a conference paper at ICLR 2025
For the second term, have
Pr Pr(X = x T to -11
Pr -Pr(X 100-1 ,T to -1) Pr Pr is accepted.)
(34)
Pr (x = =x 101 _ S 40 -- Pr (766-1 S heo-1)
(Pr (Pr (x = - ) - Pr (x = - , 2 (o)) -min { Premain (260-1)
(ooo (ofa
Proj
Premaiu (2
(Ma x) min M,
Ms (2 ,x)3) min 1,
Proj Proj(1c (2l0-1)
ZEA
(35)
= -Pra((x min {1, Premain Premain((foa1) (2fa-1)
(36)
Prej(afo-1) =min {Premain (2 Pro (roo(x00-11)
In the above derivation, Equation (34) is due to that Algorithm 4 is outputing the longest accepted subblock. Equation (35) due to the induction hypothesis. Equation (36) is due the definition of Prej in Equation (33).
Combining the two terms, we have
Pr Pr = f0--- _2 60 -)
= Pr =Pr(x = o0 1 (o) + +r (X = -00--
= Σ min(Mo(x< 2). M2 (2 1- x)} + min {Premain (2 11 Prej Prej (2"0-1)}
ZEX
min
min M, (2 11 x))} + Premain ( (x (1
Σ min(MM(26001 .x) M, 10- x))} (x)001,x)} + Proj Proj (260-1)3
ZEN
min
Σ Mo( 22)
E M, 22)
(37)
LEX
FEX
= min (MMox'0-1). M,
which is the desired quantity in the lemma. This concludes the proof. Here Equation (37) is due to the definition of Premain and Prej in Equation (32) and Equation (33).
Next proceed to prove Lemma 8. Let 0 = (XT, N,, It would be enough to show that for all S y and x² X
Pr Pr = r') =Mb(z').
We prove this via induction. Note that the corollary holds for i which the trivial case and both sides are equal to 1. Suppose the claim holds for i S ig. This means Vo L we have
Pr (r = x000 = MM(x'').
When = in + 1, by the algorithm. we have that either T 2 in + 1, where O is an accepted token, < i.. where O is sampled according to M |0a) (or greedy O%)), which
26

---

Published as a conference paper at ICLR 2025
is the same as Mnew (: |0")). By Lemma 9, we have
Pr PO 1)
Pr (O 2000 + - in + 1) + Pr (O' - =/o+1 S i0)
Pr (X*o+1 = x'0+1 .T
1 10 +1) Pr (0 = - -now ( x00)
Pr (Xlo+1 = 1'0t! , ,2 +1)
+ (Pr (0' =x²² - Pr (0" = i0 +1) Maew(Tiit x'²))
+ (M((ott - Σ min min(MM(r"t) (M) Mnew (Fiot xx(²))
(38)
min(Mo(()ott)) M, +
Σ max(_M M.(x', ((),,,,),,)) -now (Nig+1 x2')))
=min(Mo(z"ot)) (0 MM(x'ot1)} + max(xx>x") z1tt1) (2 rio+1). = -Mo(zfot)).
(39)
Here Equation (38) follows by the induction hypothesis, and Equation (39) follows by the definition of Mnew in Equation (31). By induction, this concludes the proof.
C.3 PROOF OF THEOREM 3
To prove Theorem we first observe the following: For Algorithm 4, let T be the number of accepted tokens, due to Lemma 9, we have
ExINMOTT|
Pr 20 = Σ
=2,
1m1
Em T'E
Σ Σ min(M,(25).MMMo3)) 2
Next we show that the above expected acceptance length is optimal for a family of draft verification algorithms that performs a coupling between sample blocks from the draft and target distributions. For all xt, y E X", let the maximum common prefix length be defined as
(<",,"):
max(Vi S l, x v.}. 6S7
Formally, let æ be a joint distribution over X7 x X2, then Algorithm 4 solves the following opti- mization problem.
max Ex 18(X7)"))
(40)
subject to constraints
Σ <(~ = Mc(x"), Vx e xx,
(41)
V7
Σ ( = = Mo(r", Vy Ex. aF?
(42)
In this above formulation, the marginal distributions satisfy X M3 and YT MM. And the maximum common prefix length refers to the number of accepted tokens one iteration of be viewed
optimal transport problem (Villani et al., 2009) between distributions (.).) and MG(-) with the cost function being (7 0(X7, YT). The next lemma establishes the optimality of Algorithm 4 in solving this problem.
speculative decoding. Note that the optimization problem
27

---

Published as a conference paper at ICLR 2025
Lemma 10. The solution Equation (40) is upper bounded by
Σ
min(Ma(x') Mn(x")
TEI PTER"
Proof of Lemma 10: For all i that satisfies Equations (41) and (42) and X², Y ~ n, we have
Ex YJ) (a)
Prxx,y (0(X)Y1) 2)
E
P (X' (X'= =x² ((X), V7) 20
85
P (X'= z²)
(8)
min (Pr (x²= = =x)) Pr (re x²)}
K5y af
ΣΣ EST
(x"),
Here (a) follows from the fact that for a positive integer random variable E|X Σ, Pr(X i): (b) follows from the fact that the joint probability is upper bounded by the minimum of the marginals.
Then Theorem 3 holds by noticing that block verification Algorithm 2 is also an instance of the coupling by setting X be the draft tokens and Y (XT, py-2--1-1 where (X", Y") are the outputs from Algorithm 2 and Z ~ Mol- c, X", YY) (Lemma 2).
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 COMPARISON TO SPECULATIVE DECODING WITH MULTIPLE DRAFTS.
Recent works (Sun al., 2023; Miao al., 2023) have extended speculative decoding to the case with multiple draft blocks to improve block efficiency. However, these methods also increase the required computation from the large model to verify the drafts. high-throughput LLM serving systems, query batching (Kwon al., 2023) is common technique where multiple prefixes are decoded at the same time. In these cases, the inference will be less memory bound and there will not be enough extra parallel compute evaluate the increased number of drafts without decreasing latency.
We empirically compare block verification and SpecTTr (Sun et al., 2023), SpecInfer (Miao al., 2023) with query batching. We set the batch size B = 8 and use PALM-2-XXS as the draft model. In Table 5, we list the wall clock speedup and block efficiency for 7 8. The number of draft blocks for SpecTTr and SpecInfer are taken to be 2, which is the one that achieves the lowest latency over {2, 4, 8} when B 8,7 8.
We observe that while SpecTr and SpecInfer can achieve higher block efficiencies, due to the in- creased computation to evaluate more candidates, our method achieves better speedup than Spec and SpecInfer, demonstrating the advantage of our method in the common practical setting with query batching.
D.2 DETAILED RESULTS WITH OTHER PARAMETER SETTINGS
In this section, present experimental results for the same of experiments described in Sec- tion 6 with different block lengths (y = 4, 6, 8) and different drafters (PALM-2-XXS and PALM-2- XXXS):
Table 6. Drafter: PALM-2-XXS, 7 = 4.
Table 7. Drafter: PALM-2-XXS,, 7 6.
28

---

Published as a conference paper at ICLR 2025
Table 5:
Speedup comparison between token verification (TOKENV) and block verification (BLOCKV) with PALM-2-XXS as the draft model on various datasets and tasks.
8,
Wall clock time over baseline
Block efficiency
Dataset
TOKENV BLOCKV SpecTr SpecInfer
TOKENV
BLOCKV SpecTrr SpecInfer
GPT Prompt
1.300
1.381
1.290
1.263
3.394
3.715
3.898
3.833
WebQA
1.302
1.368
1,279
1.274
3.451
3.7
3.933
3.894
ShareGPT
1.267
1.333
1.244
1.236
3.366
3.63
3.824
3.78
GSM8K
1.353
1.445
1.344
1.319
3,856
4.179
4.356
4.277
XSum
1.328
1.403
1.300
1.285
3.487
3.768
3,949
3.897
PIQA
1.305
1.377
1,270
1.280
3,401
3.685
3.846
3.82
LMIB
1.274
1.344
1.253
1.245
3.218
3,494
3.669
3.629
WMT-DeEn
1.222
1.293
1.204
1.194
3.165
3.422
3.603
3.56
Table 8. Drafter: PALM-2-XXXS. 7 4.
Table 9. Drafter:
PALM-2-XXXS, 7 =
Table 10. Drafter:
PALM-2-XXXS, 8.
Table 6: Speedup comparison between token verification (TOKENV) and block verification (BLockV) with 7 and PAIM-2-XXSS being the draft model. Each statistic is computed using 1000 test prompts from different datasets various tasks (each run is an average with 3 different random seeds). Numbers after represent standard deviation.
Block efficiency
Wall clock time speedup over baseline
Dataset
TOKENV
BLUCKV
Improve. 1 %
ToKENV
BLOCKV
Improve.
%
LMIB
2.78 0.01 2.88 0.01
3.48 + 0.24
2.36 + 0.00 =
2.51 + 0,22
GPT Prompt
2.88 = 0.01 1.00
4.33 = 0.25
2.43 0.01
2.00
3.43 + 0,24
WebQA
2.91 0.01
2.83 0.65
2.45 0.01
2.50
1.94 0 0.61
PIQA
2.89 = 0.00 2.09
3.21
2.44
2.00
2.26
ShareGPT
2.85 0.01 2.95
2.41 3.48
2.00
0.17
XSum
2.94 = 0.01 3.03
3.24
2.48
2.00
2.35
0.448
GSM8K
3.12 0.01 3.21 0.02
3.06
0.95
2.62 + 0.01
2.68 0.02
2.19
0.89
WMT-DeEn
2.75 = 0.01 2.83 0.01
2.99
0.09
2.33 + 0.01
2.38 0.01
2.18 + 0.09
Average
2.89
2.99
3.36
2.44
2.50
2.49
Table
Speedup comparison between token verification (TOKENV) and block verification (BLOcKV) with 6 and PALM-2-XXS being the draft model. Each statistic is computed using 1000 test prompts from different datasets on various tasks (each run is an average with different random seeds). Numbers after + represent standard deviation.
Block efficiency
Wall clock time speedup over baseline
Dataset
TOKENV
BLoocKV
Improve. 1
ToKENV
BloOcKV
Improve.
LMIB
3.08 = 0.01 3.27 + 0.01 6.42 0.07
2.32 = 0.01 2.43 1 0.01
5.00 = 0.06
GPT Prompt
3.22 0.01 3.44 0.02
6.55 0.83
2.42 0.00
5.06 2.02 0.77
WebQA
3.26 = 0.01 3.44
5
2.45
2.55 0.01
4.24
PIQA
3.22 0.02 0.02
2.42
2.01
4.72
ShareGPT
3.18 0.02 3.37
6.13
2.39 +.902....
2.50
0.74
XSum
3.29 0.01 3.08
5.91 0.82
2.47 1.77+000
2.00
0.77
GSM8K
3.56 0.01 3.80
6.86
+ 0.60
2.66 + 0.01 2.80
+.38
WMT-DeEn
3.04 0.01 3.09
4.92
0.29
2.29 0.01
2.37 0.01
3.57
Average
3.23
3.43
6.10
2.43
2.54
4.67
29

---

Published as a conference paper at ICLR 2025
Table Speedup comparison between token verification (TOKENV) and block verification (BLOCKV) with y = 4 and PALM-2-XXXS being the draft model. Each statistic is computed using 1000 test prompts from different datasets on various tasks (each run is an average with different random seeds). Numbers after + represent standard deviation.
Block efficiency
Wall clock time speedup over baseline
Dataset
TOKENV
BLOCKV
Improve.
%
TOKENV
BLOCKV
Improve.
LMIB
2.24 0.00 2.33 + 0.01
4.23
0.44
2.25 0.00
2.34 0.01
3.89 + 0.41
GPT Prompt
2.41 0.02 2.48 + 0.01
2.96
1.000
2.42
0.02 2.48 + 0.01
2.72 + 0.94
WebQA
2.38 = 0.001 2.05
2.39 0.13
2.63 2.01
0.12
PIQA
2.36 = =0.01 2.00
2.37 0.37
2.44
2.37
ShareGPT
2.34= =0.00 2.02
0.12
2.35
2.00
3.16
XSum
2.38 = 0.01 2.45
0.63
2.30
2.45
2.60
GSM8K
2.51 = 0.01
2.58 0.02
2.99
2.51
0.01
0.02
2.74
WMT-DeEB
2.22 0.00 2.28 0.00
2.59 + 0.09
2.24 + 0.00
0.00
2.37
0.08
Average
2.35
2.43
3.16
2.36
2.43
2.89
Table 9: Speedup comparison between token verification (TOKENV) and block verification (BLOcKV) with 7 = and PALM-2-XXXX being the draft model. Each statistic computed using 1000 test prompts from different datasets various tasks (each run is an average with different random seeds). Numbers after + represent standard deviation.
Block efficiency
Wall clock time speedup over bascline
Dataset
TOKENV
B1.OCK
Improve. 1 %
TOKENV
BL.0CK
Improve.
%
LMIB
2.36 0.01 2.48 + 0.00
4.93 + 0.46
2.27 0.01 2.37 = 0.00
4.55 + 0.43
GPT Prompt
2.58 = 0.04 2.72 + 0.02
5.57 + 1.29
2.46 0.03 2.59 0.01
5.10 + 1.22
WebQA
2.54 0.00 2.68 + 0.02
5.46 + 0.50
2.43
2
5.02 + 0.47
PIQA
2.50 = 0.00 2.62 0.01
5.06
2.00
2.50
4.36
ShareGPT
2.47 0.01 2.60 1
5.10 0.49
2.37
2.48 0.01
0.49
XSum
2.54 = 0.01 1677+0.0
4.47
2.43
2.54
4.44
GSM8K
2.71 0.03
2.83 0.00
4.89
2.58
2.69
0.00
3.92
WMT-DeEn
2.31 = 0.01 2.43 + 0.02
5.38
0.57
2.21 + 0.00
2.32
4.99 0.54
Average
2.50
2.63
5.07
2.39
2.50
4.67
Table 10: Speedup comparison between token verification (TOKENV) and block verification (BLockV) with 7 and PALM-2-XXXX being the draft model. Each statistic is computed using 1000 test prompts from different datasets on various tasks (each run is an average with different random seeds). Numbers after +'t represent standard deviation.
Block efficiency
Wall clock time speedup over baseline
Dataset
TOKENV
BLOCKV
Improve. 1 %
ToKENV
BLOCKV
Improve.
LMIB
2.40 = 0.01 2.55 + 0.01
6.19 + 0.43
2.13 0.01
2.25 + 0.01
5.28 + 0.40
GPT Prompt
2.66 = 0.01 0.002
6.28 + 1.01
2.35
2.47
5.37 + 0.95
WebQA
2.61 = 0.01
2.78 0.00
6.27 0.49
2.43 2.01
5.39 +: 0.46
PIQA
2.57 0.01 2.76
7.48
2.27
2.02
6.41
ShareGPT
2.54 = 0.01 2.01
0.72
2.05
2.38 0.00
5.68
XSum
2.60 0.01 2.70
6.46 0.49
2.30
2.43
5.53
GSM8K
2.82 0.02 2.98 0.03
5.48 + 1.18
2.49
+
0.01
2.60
1.11
WMT-DeEn
2.37 = 0.00
2.49 0.01
5.33 + 0.46
2.10 0.00
2.20 0.001
4.53 0.43
Average
2.57
2.73
6.27
2.28
2.40
5.36
30


Reviews:
[{"review_id": "86BbqmmUCa", "reviewer": "Reviewer_1Noe", "summary": "This paper presents a new algorithm for draft verification for speculative decoding for LLMs. Speculative decoding is a method that accelerates the inference process of LLMs using predictive heuristics to produce “drafts” of the likely next tokens the LLM will generate. These drafts must go through a verification process to determine whether or not they should be accepted, depending on how well they fit the target model’s distribution. The authors argue that the prior state-of-the-art approach for draft verification, Token Verification, is not optimal, since it considers the tokens one by one. The authors instead propose a method to consider the tokens as a block by considering their joint probabilities. The authors also demonstrate that their method accepts more tokens on average than the original Token Verification approach, which is more efficient in the long run. Their experimental results demonstrate that despite the standard overheads of LLM inference, the Block Verification algorithm outperforms the Token Verification algorithm in terms of wall clock speedup.", "questions": "- How will the speedup results scale when using larger models?\n\n- How are probabilities of all subblocks calculated?\n\n - Page 7, line 334: How realistic is this experimental setting? How many drafts are usually produced during speculative decoding, and how many copies of the model would we need for evaluating?\n\n## Post-rebuttal comment\n\nThe authors addressed the questions raised in my review, and I have increased my score accordingly.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Overall, the paper is well written and the problem is clearly stated.\n\nThe theoretical proofs are sound to the best of my knowledge.", "weaknesses": "The paper does not provide sufficient evidence that it provides a considerable speedup.\nSpeedup is from a higher acceptance rate. The paper is using  PALM-2-XXS and XXXS. At this model size, answers tend to be quite bad, which makes it hard for actual response evaluation. \n\nIt was not clear how the probabilities for all subblocks are calculated. \n\n# Minor comments \n\nPage 7, line 336: “I.e., it measures” should be “Specifically, it measures”\n\nPage 8, line 425: “all valid verification algorithm” should be “all valid verification algorithms”\n\nPage 8: I think Figure 4 should be labeled as a Table instead of a figure", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3MRZmZdgGJ", "reviewer": "Reviewer_eih8", "summary": "This paper introduces Block Verification, a novel algorithm designed to accelerate speculative decoding in large language models. Unlike traditional token-by-token verification, Block Verification evaluates and accepts a group of tokens (a \"block\") together. This method achieves faster generation speeds without compromising output quality.", "questions": "1. In the appendix, a batch size of 8 was used to compare with tree attention. What batch size was used in the main experimental section?\n2. How does the performance compare with Medusa/Eagle's static tree attention?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. **Block Verification** improves efficiency by verifying token blocks rather than individual tokens in speculative decoding, preserving the same distribution.\n\n2. Block verification achieves consistent 5–8% speedup and is broadly applicable across models and datasets.\n\n3. Block verification is easy to implement, with minimal modifications to existing speculative decoding systems.", "weaknesses": "1. Consistency in final distribution does not guarantee identical generation sequences. For instance, the large model might generate \"ABC\" while the small model generates \"ADC.\" It’s possible that in the context of \"ADC,\" the next token’s distribution aligns between the models, but under greedy decoding, the large model should ideally follow \"ABC\" rather than \"ADC.\" The authors state that block verification accepts more tokens than token verification. In the case of greedy decoding, does this imply potential token differences? Would such differences impact the accuracy of the answer, or would block verification revert to token-by-token verification?\n2. The explanations of the formulas and algorithms lack intuitive clarity, making comprehension more challenging, even though the modifications from token verification are not large.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3rk6i6wd74", "reviewer": "Reviewer_jhoE", "summary": "The paper introduces a novel verification algorithm called the block verification method, which enhances the efficiency of speculative decoding in large language models (LLMs). This method contrasts with the traditional Token Verification, which optimizes the verification of token blocks to increase efficiency. The study demonstrates that Block Verification outperforms existing methods regarding the expected number of generated tokens (called the block efficiency) and wall-clock times while providing a theoretical guarantee of optimal performance under given conditions. Empirical evaluations show improvements across various tasks, confirming its effectiveness without additional code complexity.", "questions": "- Are there specific conditions or types of LLM architectures where the performance gains of Block Verification may be more pronounced or limited?\n- How does the algorithm handle edge cases where the distributions of the drafting and target models diverge significantly?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides solid theoretical guarantees, ensuring that the proposed method does not compromise the output distribution.\n- The experiments validate the practical benefits, with performance gains across a diverse set of tasks.\n- The proposed algorithm does not increase code complexity, making it easy to integrate into existing LLM architectures.\n- The paper highlights how Block Verification compares favorably to related methods, strengthening its contribution.", "weaknesses": "- The depth of proofs might be challenging for practitioners without a strong mathematical background, potentially limiting the paper's audience.\n- There is a typo in the manuscript: page 8, line 413: deocding -> decoding", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JKLvgeEnBI", "reviewer": "Reviewer_CsEe", "summary": "This paper studies the problem of optimizing speculative decoding from an algorithm level to achieve inference acceleration. The key idea behind this paper is the observation that verifies multiple draft tokens in a block jointly, rather than token-by-token, can bring improvement in mean accepted tokens, which leads to the wall-clock speedup for LLM inference. Based on the idea, the paper proposes a simple block verification algorithm, which is plug-and-play for some existing speculative decoding methods. The authors theoretically show that block verification is lossless and better than standard speculative decoding, making it a stronger default implementation of speculative decoding. The experiments demonstrate that block verification modestly but consistently improves the mean accepted tokens and the final wall-clock speedup.", "questions": "I would like to raise some questions to improve the manuscripts.\n\n1. Could you provide a more detailed explanation to the motivating example with partial information? You have mentioned \"with block verification\" in Line 124, but it is not clear how block verification works in this section.\n2. Existing speculative decoding methods mainly adopt a tree-based verification manner, which can significantly enhance the mean accepted tokens. Could you provide some explanation how block verification works in a tree-based verification manner?\n3. Could you provide a more detailed theoretical assumptions for Definition 1, Theorem 1 and Theorem 2? Besides, I think the section Theoretical Guarantees can be further improved by providing some intuitive explanation (e.g. why block verification is optimal for any valid draft verification algorithm), as this can help readers to understand the advantages of block verification over TMC.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of the block verification in the full distribution is clear and easy to understand, and the paper is well-written with clear explanations to the block verification algorithm.\n2. This method shows great simplicity and is easy to use. It does not incur additional computation or memory overhead, and is very easy to implement. \n3. The authors theoretically show that block verification is lossless and better than standard speculative decoding, making block verification a stronger default verification for speculative decoding.", "weaknesses": "While I really appreciate the simplicity of the method, the novelty and the contributions of the paper are a little weak for me. The reasons are:\n\n1. The motivation that *\"verifying multiple draft tokens token by token is not optimal\"* is very similar to the motivation in Tree Monte Carlo (TMC) [1], which alleviates the novelty of this paper. Given the empirical results that block verification only brings 5%~8% speedup, I doubt the technical contributions of block verification. The block verification seems more like a trick with theoretical support.\n2. There lacks a significant discussion about the decoding temperature $T$ in LLM inference, and the authors do not report the temperature in the experiment details. **In my understanding, the block verification can only bring speedup with $T > 0$, as the block verification degenerates to the token verification in greedy decoding ($T=0$).** Please correct me if I have any misunderstanding. While speculative decoding provides maximal speedup in greedy decoding settings for some specific tasks, such as coding and math reasoning, block verification cannot provide improvement on these tasks. Besides, additional experiments to investigate the influence of different decoding temperature are necessary.\n3. Currently, I think there exists a large room (more than 1 page) to conduct more experiments.\n   - Experiments for more LLM combinations (e.g. Llama family [2] and Vicuna [3]) across more benchmarks (e.g. MT-Bench [4] and SpecBench [5]) **with different temperature settings**.\n   - Experiments for combining block verification to some latest speculative decoding methods (e.g. Medusa [6] and Eagle [7]).\n\nI know that conducting a wide range of evaluation experiments are costly and time consuming, and I will increase my score if the authors clearly address my concerns.\n\n\n\n[1] Hu, Zhengmian, and Heng Huang. \"Accelerated Speculative Sampling Based on Tree Monte Carlo.\" *Forty-first International Conference on Machine Learning*.\n\n[2] Dubey, Abhimanyu, et al. \"The llama 3 herd of models.\" *arXiv preprint arXiv:2407.21783* (2024).\n\n[3] Chiang, Wei-Lin, et al. \"Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.\" *URL https://lmsys. org/blog/2023-03-30-vicuna* 3.5 (2023).\n\n[4] Zheng, Lianmin, et al. \"Judging llm-as-a-judge with mt-bench and chatbot arena.\" *Advances in Neural Information Processing Systems* 36 (2023): 46595-46623.\n\n[5] Xia, Heming, et al. \"Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding.\" *arXiv preprint arXiv:2401.07851* (2024).\n\n[6] Cai, Tianle, et al. \"Medusa: Simple llm inference acceleration framework with multiple decoding heads.\" *arXiv preprint arXiv:2401.10774* (2024).\n\n[7] Li, Yuhui, et al. \"Eagle: Speculative sampling requires rethinking feature uncertainty.\" *arXiv preprint arXiv:2401.15077* (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)