Block Verification Accelerates Speculative Decoding

## Abstract

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.

## 1 Introduction

Large language models (LLMs) (Chowdhery et al., ; Touvron et al., ; Achiam et al., ; Gemini Team et al., ) are often decoded through autoregressive sampling, where
generating $k$ tokens requires $k$ costly serial evaluations of the model.
To improve generation latency, Leviathan et al. () proposed *speculative decoding*, which enables an LLM to generate several tokens concurrently.
In each iteration, conditioned on the current decoded prefix, a guess of the next block of $\gamma$ tokens is made by a fast drafter (e.g., a small model or a heuristic).
Each of the resulting $\gamma+1$ prefixes are 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 are rejected.
The accepted tokens(^1^11With an extra token sampled from either a residual distribution or the large model distribution.) are then appended to the prefix, and the process repeats until generation ends.
See Figure 1 and Algorithm 3.

Figure: 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.
Refer to caption: x1.png

In Leviathan et al. (), the drafts are verified through a sequence of token-level rejection steps.
More specifically, given a prefix ${\bm{c}}$, let $X_{1},X_{2},\ldots,X_{\gamma}$ be one sample block of length $\gamma$ from the draft model ${\cal M}_{s}$, where $\forall i\leq\gamma$,
$X_{i}\sim{\cal M}_{s}(\cdot\mid{\bm{c}},X^{i-1}).$
Using the conditional distributions under the target large model ${\cal M}_{b}$ returned by the parallel evaluation step ($\forall i\leq\gamma$,
${\cal M}_{b}(\cdot\mid{\bm{c}},X^{i-1})$)
, the algorithm iterates over the draft tokens sequentially, and accepts each token $X_{i}$ with probability

$$ $\min\left\{1,\frac{{\cal M}_{b}(X_{i}\mid{\bm{c}},X^{i-1})}{{\cal M}_{s}(X_{i} \mid{\bm{c}},X^{i-1})}\right\},$ (1) $$

The process continues until a token is rejected, at which point an extra token is sampled, for free, according to a residual distribution (see Algorithm 1 and Leviathan et al. () for more details). We refer to this algorithm as *Token Verification*.
Since its introduction in Leviathan et al. (), this
token-by-token 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, is not optimal*, and propose a *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 use. The algorithm is a plug-and-play replacement of the standard token verification algorithm of speculative decoding. It
does not incur additional computation or code complexity costs.
- •
Strict 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 an optimal verification procedure (Theorem 2).
- •
Identical distribution. Importantly, our method is not an approximation and maintains the identical distribution guarantee of speculative decoding.

We empirically test *block verification* and compare it 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 ${\cal M}_{s}$ than from ${\cal M}_{b}$. This is necessary to guarantee that the generated tokens follow the same distribution as that of ${\cal M}_{b}$. 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 a simple example.

Consider the following trivial language model whose token space consists only of 2 tokens: a and b. Further, assume that both the large model ${\cal M}_{b}$ and the small model ${\cal M}_{s}$ are context-independent, and specifically that $\forall{\bm{c}}$,

$$ ${\cal M}_{b}({\textsc{a}})=1/3,\quad{\cal M}_{b}({\textsc{b}})=2/3,\quad{\cal M }_{s}({\textsc{a}})=2/3,\quad{\cal M}_{s}({\textsc{b}})=1/3.$ $$

In this setting, token verification will accept each draft token $X$ independently with probability 1 if $X={\textsc{b}}$ and $1/2$ if $X={\textsc{a}}$.
With a block size of $\gamma=2$, since the total variation (TV) distance $d_{\rm TV}({\cal M}_{b},{\cal M}_{s})=1/3$, the expected number of accepted tokens(^2^22This is different from the number of generated token in one iteration, which is the number of accepted tokens plus one (corrected token).) from ${\cal M}_{s}$ with the token verification algorithm is $1-1/3+(1-1/3)^{2}=10/9$ (see analysis in Leviathan et al. ()).

An ideal algorithm with full information. Suppose an algorithm can decide on what tokens to accept from ${\cal M}_{s}$ based on the full joint distributions of both tokens, i.e.,

$$ ${\cal M}_{b}({\textsc{a}}{\textsc{a}})=1/9,\quad{\cal M}_{b}({\textsc{a}}{ \textsc{b}})=2/9,\quad{\cal M}_{b}({\textsc{b}}{\textsc{a}})=2/9,\quad{\cal M} _{b}({\textsc{b}}{\textsc{b}})=4/9,$ $$

$$ ${\cal M}_{s}({\textsc{a}}{\textsc{a}})=4/9,\quad{\cal M}_{s}({\textsc{a}}{ \textsc{b}})=2/9,\quad{\cal M}_{s}({\textsc{b}}{\textsc{a}})=2/9,\quad{\cal M} _{s}({\textsc{b}}{\textsc{b}})=1/9.$ $$

The algorithm would have performed the following improved acceptance logic: always accept $X_{1}X_{2}$ when $X_{1}X_{2}=$ ab, ba, or bb since ${\cal M}_{b}(X_{1}X_{2})\geq{\cal M}_{s}(X_{1}X_{2})$, and accept aa with probability ${\cal M}_{b}({\textsc{a}}{\textsc{a}})/{\cal M}_{s}({\textsc{a}}{\textsc{a}})=
1/4$ (correcting the samples to bb).
The expected number of accepted tokens from ${\cal M}_{s}$ now becomes: $2({\cal M}_{s}({\textsc{a}}{\textsc{b}})+{\cal M}_{s}({\textsc{b}}{\textsc{a}}
)+{\cal M}_{s}({\textsc{b}}{\textsc{b}})+1/4\times{\cal M}_{s}({\textsc{a}}{
\textsc{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 is intractable to calculate. Instead, we only have access to the conditional distributions of the next token along the *sample path* of the draft block, ${\cal M}_{b}(\cdot\mid{\bm{c}},X^{i}),{\cal M}_{s}(\cdot\mid{\bm{c}},X^{i})$ for various $i$’s. To 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.

With block verification, when the draft tokens $X_{1}X_{2}={\textsc{a}}{\textsc{b}}$ or bb, $\Pr{\left({\text{Accept }X_{1}X_{2}}\right)}=1$ similar to the idealized algorithm. When $X_{1}X_{2}={\textsc{a}}{\textsc{a}}$, $\Pr{\left({\text{Accept }X_{1}X_{2}}\right)}=1/4$, and else the algorithm rejects both tokens and only corrects the first token to b since the algorithm doesn’t have access to ${\cal M}_{b}(\cdot\mid{\textsc{b}})$. When $X_{1}X_{2}={\textsc{b}}{\textsc{a}}$, it always accepts b, and then accepts a with probability $1/2$ (else it corrects the second token to b). Importantly, the marginal distributions of the generated tokens at the first token and the second token are always ${\cal M}_{b}(\cdot)$. We then simply add the generated tokens to the prefix and proceed to the next iteration. The expected number of accepted tokens is $2\times({\cal M}_{s}({\textsc{a}}{\textsc{b}})+{\cal M}_{s}({\textsc{b}}{
\textsc{b}}))+(1+1/2)\times{\cal M}_{s}({\textsc{b}}{\textsc{a}})+1/4\times 2
\times{\cal M}_{s}({\textsc{a}}{\textsc{a}})=11/9$, which is 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$) is 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.

Figure: Algorithm 1 Token Verification

###### Lemma 1 .

## 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 to 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 to 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.

Figure: Figure 2: The acceptance probabilities and residual distributions in Algorithms 1 and 2.

See Algorithm 2 for a sketch implementation of block verification, and Algorithm 1 for a sketch implementation of the standard token verification for comparison.
Note that the implementations follow the same overall structure (the differences are highlighted).
See Algorithm 3 for the outer loop of the speculative decoding algorithm, which remains unchanged for both verification methods.
See Figure 2 for additional definitions. See Appendix A for sketch Python implementations.

Importantly, note that token verification stops as soon as a token is rejected (the break in Line 9 of Algorithm 1), while block verification always operates on the full block.

Figure: Algorithm 3 Speculative decoding (SpecDec) (Leviathan et al., )

#### 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 speculative decoding (Algorithm 3), resulting in a strict improvement over the standard token verification (Theorem 2). We defer the formal statements to Section 4. Below we give some intuitions on the parameter choices.

#### Intuition on parameter choices.

The key quantities for achieving the theoretical guarantees are $p_{i}$’s, which correspond to the probability that the sub-block $X^{i}$ will be kept in the final output (see Lemma 3 in Section B.1). The per-step acceptance probability $h_{i}$ in Equation 4 is then decided based on $p_{i}$’s since block verification keeps the longest accepted sub-block.

Intuition: $p_{i}$’s. To start, we ignore the minimum operation in the recursion. Then each $p_{i}$ is simply ${\cal M}_{b}(X^{i}\mid{\bm{c}})/{\cal M}_{s}(X^{i}\mid{\bm{c}})$, which is an upper bound on the actual $p_{i}$’s. This guarantees that the probability of getting $X^{i}$ by accepting it from the draft will be at most ${\cal M}_{b}(X^{i}\mid{\bm{c}}),$ and hence the algorithm is not accepting $X^{i}$ more than needed.

Moreover, the minimum operation also guarantees that for any prefix $X^{j}$ that could be obtained from multiple draft sample paths, the distribution over subsequent tokens are always the same ${\cal M}_{b}(\cdot\mid{\bm{c}},X^{j})$.
This enables block verification to be used as a plug-and-play replacement of token verification in speculative decoding (Algorithm 3).

Intuition: $p_{\rm res}^{\rm block}$. As shown in Lemma 3, for any $X^{i}$, the probability that it is in the accepted block is ${\cal M}_{s}(X^{i})p_{i}(X^{i})$. The goal of choosing $p_{\rm res}^{\rm block}$ is to make sure that the distribution on the next token follows ${\cal M}_{b}(\cdot\mid X^{i})$. For any possible next token $x$, $(X^{i},x)$ could also be obtained by accepting $X^{i+1}$ when $X_{i+1}=x$,
with a probability of ${\cal M}_{s}(X^{i},x)p_{i+1}(X^{i},x)$,
which should be subtracted to obtain the residual mass on $(X^{i},x)$. This leads to the choice of $p_{\rm res}^{\rm block}$ in Equation 3.

## 4 Theoretical Guarantees

In this section, we present the formal theoretical guarantees of block verification. Notably, that it produces the correct distribution and that it is optimal in terms of the expected number of generated tokens.
Let ${\cal M}^{*}(\cdot\mid{\bm{c}})$ denote the distribution of the sequence up to the end of the generative process under model ${\cal M}$ and context ${\bm{c}}$.

###### Definition 1 (Valid draft verification algorithm.) .

An algorithm Verify is said to be a valid draft verification algorithm if $\forall{\bm{c}}$, models ${\cal M}_{s},{\cal M}_{b}$, and block length $\gamma$, the outputs of Algorithm 3 (SpecDec) with verification algorithm Verify satisfy

$$ $\textsc{SpecDec}({\bm{c}},{\cal M}_{b},{\cal M}_{s},\gamma,\textsc{Verify}) \sim_{\rm p}{\cal M}_{b}^{*}(\cdot\mid{\bm{c}}),$ (5) $$

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.1 in Leviathan et al. ()). We now claim the following:

###### Theorem 1 .

Block verification is a valid draft verification algorithm.

I.e. 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>0$, let $N(i)$ be the number of decoded tokens after $i$ iterations in Algorithm 3.
For any valid draft verification algorithm Verify in Definition 1, we have $\forall{\bm{c}},{\cal M}_{s},{\cal M}_{b}$, $\gamma$, and $i$,

$$ $\mathbb{E}_{\textsc{BlockVerify}}[N(i)]\geq\mathbb{E}_{\textsc{Verify}}[N(i)],$ $$

where the randomness is over the randomness of the draft block and the randomness of the algorithm.

In particular,

$$ $\mathbb{E}_{\textsc{BlockVerify}}[N(i)]\geq\mathbb{E}_{\textsc{TokenVerify}}[N (i)].$ $$

In other words, among all valid verification algorithms(^4^44We use BlockVerify and TokenVerify to denote block verification and token verification respectively.), speculative decoding with block verification decodes the highest number of tokens in expectation in a 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 a greater speedup than the standard token verification. We defer the proofs to Appendix B.

Note that the optimality guarantee holds for all verification algorithms that can be used in Algorithm 3 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*. Note that 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.

###### Definition 1 (Valid draft verification algorithm.) .

###### Theorem 1 .

###### Theorem 2 .

## 5 Experiment Setup

We use PALM-2 models (Chowdhery et al., ) for the drafter and target models, with PALM-2-S as the large target model and PALM-2-XXS / PALM-2-XXXS 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 on prompts from a wide range of datasets and tasks, including Language modeling with one-billion language benchmark (LM1B) (Chelba et al., ),
ChatGPT prompts sourced from LearnGPT (GPT Prompt) (Rashad, ), reasoning questions (WebQA) (Berant et al., ), physical commonsense reasoning questions (PIQA) (Bisk et al., ), scraped conversations with ChatGPT (ShareGPT) (Rashad, ; RyokoAI, ), summarization tasks (XSum) (Narayan et al., ), grade school math problems (GSM8K) (Cobbe et al., ), and German to English translation (WMT DeEn) (Bojar et al., ).
For all datasets, we decode the first $1000$ prompts using a max input prompt length of $512$ and decode up to $128$ output tokens.

## 6 Results

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 a wide range of settings, both when measuring idealized *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.
I.e. 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 $\gamma=8$ with PALM-2-XXS as 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., ; Chen et al., ) for a more detailed discussion of these overheads.
For $\gamma=8$ with PALM-2-XXS as the drafter, the improvement in block efficiency ranges from $5.36\%$ to $8.14\%$ with an average of $6.49\%$. The detailed numbers for this setting are listed in Table 1.

**Table 1: Speedup comparison between token verification (TokenV) and block verification (BlockV) with $\gamma=8$ 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.**
| Dataset | Block efficiency | Wall clock time speedup over baseline |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| TokenV | BlockV | Improve. $\uparrow$ % | TokenV | BlockV | Improve. $\uparrow$ % |  |
| LM1B | $3.21\pm 0.01$ | $3.49\pm 0.02$ | $8.68\pm 0.79$ | $2.17\pm 0.01$ | $2.32\pm 0.01$ | $6.85\pm 0.74$ |
| GPT Prompt | $3.41\pm 0.04$ | $3.76\pm 0.02$ | $10.06\pm 1.66$ | $2.30\pm 0.02$ | $2.48\pm 0.01$ | $8.14\pm 1.55$ |
| WebQA | $3.44\pm 0.01$ | $3.70\pm 0.01$ | $7.53\pm 0.24$ | $2.32\pm 0.00$ | $2.45\pm 0.01$ | $5.75\pm 0.22$ |
| PIQA | $3.40\pm 0.02$ | $3.68\pm 0.00$ | $8.30\pm 0.62$ | $2.29\pm 0.01$ | $2.44\pm 0.00$ | $6.52\pm 0.58$ |
| ShareGPT | $3.34\pm 0.01$ | $3.62\pm 0.03$ | $8.45\pm 0.98$ | $2.25\pm 0.01$ | $2.40\pm 0.02$ | $6.68\pm 0.91$ |
| XSum | $3.49\pm 0.02$ | $3.76\pm 0.01$ | $7.63\pm 0.94$ | $2.35\pm 0.01$ | $2.49\pm 0.01$ | $5.82\pm 0.88$ |
| GSM8K | $3.81\pm 0.01$ | $4.15\pm 0.03$ | $8.74\pm 0.56$ | $2.55\pm 0.01$ | $2.73\pm 0.02$ | $6.84\pm 0.51$ |
| WMT-DeEn | $3.19\pm 0.01$ | $3.41\pm 0.02$ | $7.00\pm 0.78$ | $2.15\pm 0.01$ | $2.27\pm 0.01$ | $5.36\pm 0.73$ |
| Average | $3.41$ | $3.70$ | $8.30$ | $2.30$ | $2.45$ | $6.49$ |

#### The effect of draft length γ 𝛾 \gamma italic_γ .

We also perform comparisons of the algorithms for other block lengths ($\gamma=4$ and $\gamma=6$) and observe consistent improvements. We plot the average improvement over all datasets in Figure 4. With the same drafter, the relative improvement of block verification over token verification increases as $\gamma$ increases. This is consistent with our intuition since when $\gamma=1$, the two algorithms are the same and as $\gamma$ increases, block verification would benefit more from coordinating the acceptance rule considering the realization of all tokens in the draft block.

#### The effect of the drafter.

We also consider the effect of the quality of the drafter on the improvement. 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 a larger model than PALM-2-XXXS, and hence a better drafter in terms of quality, as demonstrated by the better average block efficiencies in the table.
In Figure 4, 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 is greater than that under PALM-2-XXXS.
This shows that the improvement obtained from block verification can be combined with the improvement on the quality of the drafter, and the improvement might be more significant under better drafters.

Figure: Figure 3: Average block efficiency (BE) and wall clock speedup (WS) across all datasets for token verification (TokenV) and block verification (BlockV) with different $\gamma$. The large model is PALM-2-S and the drafter model is either PALM-2-XXS (XXS) or PALM-2-XXXS (XXXS).
Refer to caption: x2.png

Detailed results for experiments performed with different drafters, different datasets, and different draft lengths are listed in Appendix D.

## 7 Related work

Parallel decoding. Our work improves speculative decoding (Leviathan et al., ), a framework for decoding several tokens concurrently. *Draft and verify* (Stern et al., ) was an earlier work, which proposed to independently predict and decode several tokens in parallel, for the greedy decoding case (zero temperature). Speculative decoding has later also been proposed in Chen et al. ().

Single draft improvements.
There have been many works aiming to improve speculative decoding without making use of more than one deocding draft. In Table 2, we list a set of works in the draft and verify framework with a breakdown of their drafting and verification algorithms. See Xia et al. () for a comprehensive study.
In the single-draft case, despite several works have worked on
improving the drafting phase of speculative decoding (He et al., ; Chen et al., ; Sun et al., ; Zhou et al., ; Liu et al., ; Gloeckle et al., ; Zhang et al., ; Elhoushi et al., ).
However, all existing algorithms use the token verification algorithm, and little has been done to improve the verification phase. Our proposed block verification algorithm can be used in tandem with the drafting techniques in Table 2, yielding combined gains.
We leave a more systematic study of the improvement of block verification in these cases for future study.

Multiple drafts. Recently, speculative decoding is extended to multiple drafts (Sun et al., ; Miao et al., ) and new verification algorithms for the multi-draft scenario are proposed (Li et al., ; Chen et al., ). While increasing the number of draft sequences has shown to improve the overall speedup, it comes at the cost of more computation. In all of these works, the verification algorithm is a generalization of the token verification procedure. Extending block verification to the multi-sample case is an interesting future direction.

**Table 2: Recent works based on the draft and verify framework. Temperature 0 refers to greedy decoding and non-zero temperature refers to sampling.**
| Work | # drafts | Temp. | Drafting | Verification |
| --- | --- | --- | --- | --- |
| Stern et al. () | $1$ | 0 0 | parallel softmax layers | token matching |
| Yang et al. () | $1$ | 0 0 | additional<br>text | token matching |
| Leviathan et al. () | $1$ | $\geq 0$ | small LM | TokenVerify  (Algorithm 1) |
| Chen et al. () | $1$ | $\geq 0$ | small LM | TokenVerify  (Algorithm 1) |
| He et al. () | $1$ | $\geq 0$ | database retrieval | TokenVerify  (Algorithm 1) |
| Chen et al. () | $1$ | $\geq 0$ | cascade of small LMs | TokenVerify  (Algorithm 1) |
| Sun et al. () | $1$ | $\geq 0$ | hierarchical drafters | TokenVerify (Algorithm 1) |
| Zhou et al. () | $1$ | $\geq 0$ | distilled small LMs | TokenVerify (Algorithm 1) |
| Liu et al. () | $1$ | $\geq 0$ | distilled small LMs | TokenVerify (Algorithm 1) |
| Gloeckle et al. () | $1$ | $\geq 0$ | parallel softmax layers | TokenVerify (Algorithm 1) |
| Zhang et al. () | $1$ | $\geq 0$ | layer skip | TokenVerify (Algorithm 1) |
| Elhoushi et al. () | $1$ | $\geq 0$ | early exit | TokenVerify (Algorithm 1) |
| This work | $1$ | $\geq 0$ | small LM | BlockVerify  (Algorithm 2) |
| Sun et al. () | $\geq 2$ | $\geq 0$ | small LM | SpecTr |
| Miao et al. () | $\geq 2$ | $\geq 0$ | small LM | multi-round TokenVerify |
| Li et al. () | $\geq 2$ | $\geq 0$ | small LM | multi-round TokenVerify |
| Chen et al. () | $\geq 2$ | $\geq 0$ | small LM | multi-round TokenVerify |

## 8 Discussion

We showed that the standard *token verification* algorithm used by speculative decoding is not optimal.
Further, we proposed a new verification algorithm, *block verification* and proved that it is an optimal verification algorithm.
We also demonstrated empirically that block verification consistently outperforms token
verification in a range of tasks.
While the theoretical proofs are somewhat involved, the actual implementation of block verification is not more complex than the standard algorithm (see Appendix A), and since our proposed algorithm can only perform better, never worse, than the standard token verification algorithm (see Theorem 2), it can be used as a good default in speculative decoding implementations.

## Appendix A Python Implementation

In this section we provide a sketch implementation of block verification (Algorithm 2) in Python (Figure 5).
Note that these are meant for illustration purposes only and are not fit for practical use.

Let $V=|{\cal X}|$ be the size of the vocabulary.
The inputs to the algorithm are:

- •
ps: an $(\gamma+1)\times V$ numpy array with the distributions from the large model ${\cal M}_{b}(\cdot\mid{\bm{c}},X^{i})$;
- •
qs: an $\gamma\times V$ numpy array with the distributions from the draft model ${\cal M}_{s}(\cdot\mid{\bm{c}},X^{i})$;
- •
drafts: a length-$\gamma$ numpy array with the ids of the draft tokens $X^{\gamma}$;

Figure: Figure 5: A sketch implementation of block verification (Algorithm 2)
Refer to caption: extracted/5755566/neurips/blockverify.png

For reference, Figure 6 is a sketch implementation of the token verification algorithm (Algorithm 1):

Figure: Figure 6: A sketch implementation of token verification (Algorithm 1)
Refer to caption: extracted/5755566/neurips/tokenverify.png

## Appendix B Formal Proofs

We start by setting up a few necessary notations. Let ${\cal X}$ be the space of output tokens. For $\ell>1$, we use ${\cal M}^{\ell}(\cdot\mid{\bm{c}})$ to denote the joint distribution of the next $\ell$ tokens conditioned on the prefix under ${\cal M}$, i.e., for all $x_{1},\ldots x_{\ell}\in{\cal X}^{\ell}$,
${\cal M}^{\ell}(x_{1},\ldots,x_{\ell}\mid{\bm{c}})=\prod_{i=1}^{\ell}{\cal M}(
x_{i}\mid{\bm{c}},x^{i-1}).$
We use ${\cal M}^{*}(\cdot\mid{\bm{c}})$ to denote the distribution of the sequence up to the end of the generative process. Below we first describe a necessary and sufficient condition for a valid draft verification algorithm in Algorithm 3.

###### Lemma 2 .

$\forall{\bm{c}},{\cal M}_{s},{\cal M}_{b}$, $\gamma$, let $X^{\gamma}$ be generated from ${\cal M}_{s}^{\gamma}(\cdot\mid{\bm{c}})$, and

$$ $X^{\tau},Y=\textsc{Verify}(X^{\gamma},\{{\cal M}_{s}(\cdot\mid{\bm{c}},X^{i}) \}_{i=0}^{\gamma-1},\{{\cal M}_{b}(\cdot\mid{\bm{c}},X^{i})\}_{i=0}^{\gamma}).$ $$

Let $Z^{\gamma-\tau}$ be generated from ${\cal M}_{b}^{\gamma-\tau}(\cdot\mid{\bm{c}},X^{\tau},Y)$.

Verify is a valid draft verification algorithm (Definition 1) if and only if $\forall{\bm{c}},{\cal M}_{s},{\cal M}_{b}$, $\gamma$,

$$ $X^{\tau},Y,Z^{\gamma-\tau}\sim_{\rm p}{\cal M}_{b}^{\gamma+1}(\cdot\mid{\bm{c} }).$ (6) $$

###### Proof.

We first prove the forward direction by induction on the maximum generation length of ${\cal M}_{b}(\cdot\mid{\bm{c}})$. When the maximum generation length is 0 0, for all new context ${\bm{c}}^{\prime}$, we have the next token is a point mass over ${\rm E.O.S}$, i.e.,

$$ ${\cal M}_{b}(x\mid{\bm{c}},{\bm{c}}^{\prime})=\delta\{x={\rm E.O.S}\}.$ $$

Then Equation 6 implies that Verify will only output ${\rm E.O.S}$, which is the same as Definition 1. Suppose Equation 5 holds for all context and ${\cal M}_{b}$ with generation length at most $T$, for a context ${\bm{c}}$ and ${\cal M}_{b}$ with maximum generation length at most $T+1$, we have that the output of $\textsc{SpecDec}({\bm{c}},{\cal M}_{b},{\cal M}_{s},\gamma,\textsc{Verify})$ is

$$ $X^{\tau},Y,\textsc{SpecDec}(({\bm{c}},X^{\tau},Y),{\cal M}_{b},{\cal M}_{s}, \gamma,\textsc{Verify}).$ $$

Let $Z^{\gamma-\tau}$ be the first $\gamma-\tau$ tokens from $\textsc{SpecDec}(({\bm{c}},X^{\tau},Y),{\cal M}_{b},{\cal M}_{s},\gamma,
\textsc{Verify})$, and $O^{*}$ be the tokens after. Since $X^{\tau},Y$ is at least of length one, the generation length of ${\cal M}_{b}(\cdot\mid{\bm{c}},X^{\tau},Y)$ is at most $T$. By the induction hypothesis, we have

$$ $Z^{\gamma-\tau}\sim_{\rm p}{\cal M}_{b}^{\gamma-\tau}(\cdot\mid{\bm{c}},X^{ \tau},Y),$ $$

and

$$ $O^{*}\sim_{\rm p}{\cal M}_{b}^{*}(\cdot\mid{\bm{c}},X^{\tau},Y,Z^{\gamma-\tau}).$ $$

And hence by Equation 6,

$$ $\displaystyle\textsc{SpecDec}({\bm{c}},{\cal M}_{b},{\cal M}_{s},\gamma, \textsc{Verify})$ $\displaystyle=X^{\tau},Y,\textsc{SpecDec}(({\bm{c}},X^{\tau},Y),{\cal M}_{b},{ \cal M}_{s},\gamma,\textsc{Verify})$ $\displaystyle=X^{\tau},Y,Z^{\gamma-\tau},O^{*}$ $\displaystyle\sim_{\rm p}{\cal M}_{b}^{*}(\cdot\mid{\bm{c}}).$ $$

This completes the proof for the forward direction.

For the backward direction, we have Equation 5 implies that for all $X^{\tau},Y$,

$$ $\textsc{SpecDec}(({\bm{c}},X^{\tau},Y),{\cal M}_{b},{\cal M}_{s},\gamma, \textsc{Verify})[:\gamma-\tau]\sim_{\rm p}{\cal M}_{b}^{\gamma-\tau}(\cdot\mid {\bm{c}},X^{\tau},Y).$ $$

Let $Z^{\gamma-\tau}$ be a draw from ${\cal M}_{b}^{\gamma-\tau}(\cdot\mid{\bm{c}},X^{\tau},Y)$, then

$$ $Z^{\gamma-\tau}\sim_{\rm p}\textsc{SpecDec}(({\bm{c}},X^{\tau},Y),{\cal M}_{b} ,{\cal M}_{s},\gamma,\textsc{Verify})[:\gamma-\tau].$ $$

And hence when $X^{\tau},Y$ is the output of Verify,

$$ $\displaystyle X^{\tau},Y,Z^{\gamma-\tau}$ $\displaystyle\sim_{\rm p}X^{\tau},Y,\textsc{SpecDec}(({\bm{c}},X^{\tau},Y),{ \cal M}_{b},{\cal M}_{s},\gamma,\textsc{Verify})[:\gamma-\tau]$ $\displaystyle\sim_{\rm p}\textsc{SpecDec}({\bm{c}},{\cal M}_{b},{\cal M}_{s}, \gamma,\textsc{Verify})[:\gamma+1]$ $\displaystyle\sim_{\rm p}{\cal M}_{b}^{\gamma+1}(\cdot\mid{\bm{c}}).$ $$

∎

In all proofs below, we fix the context ${\bm{c}}$, and the models ${\cal M}_{s}$ and ${\cal M}_{b}$. We note that the proofs won’t use specific information about these choices and hence can be easily extended to all cases.

###### Lemma 2 .

###### Proof.

### B.1 Proof of Theorem 1

By Lemma 2, it would be enough to prove that BlockVerify satisfies Equation 6.
For simplicity, we often refer to the sequence $(X^{\tau},Y,Z^{\gamma-\tau})$ by $O^{\gamma+1}$. Since $O_{\gamma+1}\sim{\cal M}_{b}(\cdot\mid{\bm{c}},O^{\gamma})$ always holds, it is enough to prove the following

$$ $\forall\ell\leq\gamma,\forall x^{\ell}\in{\cal X}^{\ell},\quad\Pr{\left({O^{ \ell}=x^{\ell}}\right)}={\cal M}_{b}^{\ell}(x^{\ell}\mid{\bm{c}}),$ (7) $$

Note that in BlockVerify, $p_{i}$’s depend on the draft tokens $X^{\gamma}$. The following definition makes this explicit. Let $p_{i}$ be such that $p_{0}=1$, and $\forall 1\leq i\leq\gamma$, $x^{i}\in{\cal X}^{i}$,

$$ $p_{i}(x^{i}\mid{\bm{c}})=\min\left\{p_{i-1}(x^{i}\mid{\bm{c}})\frac{{\cal M}_{ b}(x_{i}\mid{\bm{c}},x^{i-1})}{{\cal M}_{s}(x_{i}\mid{\bm{c}},x^{i-1})},1 \right\}.$ (8) $$

For most cases, when the prefix ${\bm{c}}$ is clear, we will ignore ${\bm{c}}$ and simply use $p_{i}(x^{i})=p_{i}(x^{i}\mid{\bm{c}})$. We will only make the prefix explicit when necessary.

We first state the following lemma on the output distribution of BlockVerify.

###### Lemma 3 .

Let $X^{\gamma}\sim{\cal M}_{s}^{\gamma}(\cdot\mid{\bm{c}})$, and

$$ $X^{\tau},Y=\textsc{BlockVerify}(X^{\gamma},\{{\cal M}_{s}(\cdot\mid{\bm{c}},X^ {i})\}_{i=0}^{\gamma-1},\{{\cal M}_{b}(\cdot\mid{\bm{c}},X^{i})\}_{i=0}^{ \gamma}).$ $$

Then we have $\forall i\leq\gamma$, and $x^{i}\in{\cal X}^{i}$,

$$ $\Pr{\left({\tau\geq\ell\mid X^{i}=x^{i}}\right)}=p_{i}(x^{i}).$ $$

We first prove Theorem 1 based on Lemma 3 and defer the proof of the lemma to LABEL:sec:lemm\pab_acc_prob_proof.
We prove Equation 7 by induction on the time index $\ell$.
When $\ell=1$, $O_{1}$ is either $X_{1}$, or a residual sample from $p_{\rm res}^{\rm block}(\cdot\mid{\bm{c}})$ where

$$ $p_{\rm res}^{\rm block}(\cdot\mid{\bm{c}})=\frac{\max\{{\cal M}_{b}(x\mid{\bm{ c}})-{\cal M}_{s}(x\mid{\bm{c}}),0\}}{\sum_{x^{\prime}}\max\{{\cal M}_{b}(x^{ \prime}\mid{\bm{c}})-{\cal M}_{s}(x^{\prime}\mid{\bm{c}}),0\}},$ $$

Hence we have $\forall x\in{\cal X}$, by Lemma 3,

$$ $\displaystyle\quad\Pr{\left({O_{1}=x}\right)}$ $\displaystyle=\Pr{\left({O_{1}=x,\tau\geq 1}\right)}+\Pr{\left({O_{1}=x,\tau=0 }\right)}$ $\displaystyle=\Pr{\left({X_{1}=x}\right)}\Pr{\left({\tau\geq 1\mid X_{1}=x} \right)}+\sum_{x^{\prime}}\Pr{\left({X_{1}=x^{\prime}}\right)}(1-\Pr{\left({ \tau\geq 1\mid X_{1}=x^{\prime}}\right)})\cdot p_{\rm res}^{\rm block}(x\mid{ \bm{c}})$ $\displaystyle={\cal M}_{s}(x\mid{\bm{c}})\cdot p_{1}(x)+\sum_{x^{\prime}}{\cal M }_{s}(x^{\prime}\mid{\bm{c}})(1-p_{1}(x^{\prime}))\cdot p_{\rm res}^{\rm block }(x\mid{\bm{c}})$ $\displaystyle=\min\{{\cal M}_{b}(x\mid{\bm{c}}),{\cal M}_{s}(x\mid{\bm{c}})\}+ \sum_{x^{\prime}}\max\{{\cal M}_{b}(x^{\prime}\mid{\bm{c}})-{\cal M}_{s}(x^{ \prime}\mid{\bm{c}}),0\}\cdot p_{\rm res}^{\rm block}(x\mid{\bm{c}})$ $\displaystyle=\min\{{\cal M}_{b}(x\mid{\bm{c}}),{\cal M}_{s}(x\mid{\bm{c}})\}+ \max\{{\cal M}_{b}(x\mid{\bm{c}})-{\cal M}_{s}(x\mid{\bm{c}}),0\}$ $\displaystyle={\cal M}_{b}(x\mid{\bm{c}}).$ $$

Hence the Equation 7 holds for $\ell=1$. Suppose Equation 7 holds up to an arbitrary $\ell<\gamma$. For $\ell=\ell+1$, we have $O_{\ell+1}$ is either equal to $X_{\ell+1}$ when $\tau\geq\ell+1$, or a sample from $p_{\rm res}^{\rm block}(\cdot\mid{\bm{c}},X^{\ell})$ when $\tau=\ell$, or a sample from ${\cal M}_{b}(\cdot\mid{\bm{c}},O^{\ell})$ when $\tau<\ell$. Hence $\Pr{\left({O^{\ell+1}=x^{\ell+1}}\right)}$ can be broken down below:

$$ $\displaystyle\quad\Pr{\left({O^{\ell+1}=x^{\ell+1}}\right)}=$ $\displaystyle\Pr{\left({O^{\ell+1}=x^{\ell+1},\tau\geq\ell+1}\right)}+\Pr{ \left({O^{\ell+1}=x^{\ell+1},\tau=\ell}\right)}+\Pr{\left({O^{\ell+1}=x^{\ell+ 1},\tau<\ell}\right)}$ (9) $$

For the first term ($\tau\geq\ell+1$), we have

$$ $\displaystyle\quad\Pr{\left({O^{\ell+1}=x^{\ell+1},\tau\geq\ell+1}\right)}$ $\displaystyle=\Pr{\left({X^{\ell+1}=x^{\ell+1}}\right)}\cdot\Pr{\left({\tau \geq\ell+1\mid X^{\ell+1}=x^{\ell+1}}\right)}$ $\displaystyle={\cal M}_{s}(x^{\ell+1}\mid{\bm{c}})\cdot p_{\ell+1}(x^{\ell+1})$ $\displaystyle={\cal M}_{s}(x^{\ell}\mid{\bm{c}})\cdot\min\{p_{\ell}(x^{\ell}){ \cal M}_{b}(x_{\ell+1}\mid{\bm{c}},x^{\ell}),{\cal M}_{s}(x_{\ell+1}\mid{\bm{c }},x^{\ell})\}.$ (10) $$

For the second term ($\tau=\ell$), we have

$$ $\displaystyle\quad\Pr{\left({O^{\ell+1}=x^{\ell+1},\tau=\ell}\right)}$ $\displaystyle=\Pr{\left({X^{\ell}=x^{\ell}}\right)}\cdot\Pr{\left({\tau=\ell \mid X^{\ell}=x^{\ell}}\right)}\cdot\Pr{\left({O_{\ell+1}=x_{\ell+1}\mid O^{ \ell}=x^{\ell},\tau=\ell}\right)}$ $\displaystyle=\Pr{\left({X^{\ell}=x^{\ell}}\right)}\cdot\Pr{\left({\tau=\ell \mid X^{\ell}=x^{\ell}}\right)}\cdot p_{\rm res}^{\rm block}(x_{\ell+1}\mid{ \bm{c}},x^{\ell})$ $$

Note that,

$$ $\displaystyle\quad\Pr{\left({\tau=\ell\mid X^{\ell}=x^{\ell}}\right)}$ $\displaystyle=\Pr{\left({\tau\geq\ell\mid X^{\ell}=x^{\ell}}\right)}-\sum_{x}{ \cal M}_{s}(x\mid{\bm{c}},x^{\ell})\cdot\Pr{\left({\tau\geq\ell+1\mid{\bm{c}}, X^{\ell+1}=x^{\ell},x}\right)}$ $\displaystyle=p_{\ell}(x^{\ell})-\sum_{x}{\cal M}_{s}(x\mid{\bm{c}},x^{\ell}) \cdot p_{\ell+1}(x^{\ell},x)$ $\displaystyle=p_{\ell}(x^{\ell})-\sum_{x}\min\{p_{\ell}(x^{\ell}){\cal M}_{b}( x\mid{\bm{c}},x^{\ell}),{\cal M}_{s}(x\mid{\bm{c}},x^{\ell})\}$ $\displaystyle=\sum_{x}\max\{p_{\ell}(x^{\ell}){\cal M}_{b}(x\mid{\bm{c}},x^{ \ell})-{\cal M}_{s}(x\mid{\bm{c}},x^{\ell}),0\}.$ $$

And hence

$$ $\displaystyle\quad\Pr{\left({O^{\ell+1}=x^{\ell+1},\tau=\ell}\right)}$ $\displaystyle={\cal M}_{s}(x^{\ell}\mid{\bm{c}})\cdot\max\{p_{\ell}(x^{\ell}){ \cal M}_{b}(x_{\ell+1}\mid{\bm{c}},x^{\ell})-{\cal M}_{s}(x_{\ell+1}\mid{\bm{c }},x^{\ell}),0\}.$ (11) $$

For the third term ($\tau<\ell$), by induction, and the generation process of $O^{\gamma+1}$, we have

$$ $\displaystyle\Pr{\left({O^{\ell+1}=x^{\ell+1},\tau<\ell}\right)}$ $\displaystyle=\Pr{\left({O^{\ell}=x^{\ell},\tau<\ell}\right)}\cdot\Pr{\left({O _{\ell+1}=x_{\ell+1}\mid O^{\ell}=x^{\ell},\tau<\ell}\right)}$ $\displaystyle={\left({\Pr{\left({O^{\ell}=x^{\ell}}\right)}-\Pr{\left({O^{\ell }=x^{\ell},\tau\geq\ell}\right)}}\right)}\cdot{\cal M}_{b}(x_{\ell+1}\mid{\bm{ c}},x^{\ell})$ $\displaystyle={\left({{\cal M}_{b}(x^{\ell}\mid{\bm{c}})-{\cal M}_{s}(x^{\ell} \mid{\bm{c}})p_{\ell}(x^{\ell})}\right)}\cdot{\cal M}_{b}(x_{\ell+1}\mid{\bm{c }},x^{\ell})$ (12) $$

Plugging Equations 10, 11 and 12 into Section B.1, we get $\forall x^{\ell+1}\in{\cal X}^{\ell+1}$,

$$ $\Pr{\left({O^{\ell+1}=x^{\ell+1}}\right)}={\cal M}_{b}(x^{\ell+1}\mid{\bm{c}}),$ $$

completing the induction step and hence the proof of Equation 7 and Theorem 1.

###### Lemma 3 .

### B.2 Proof of Theorem 2

We first state the following lemma, which shows that in one iteration, among all valid draft verification algorithms, BlockVerify accepts each subsequence with the highest probability.

###### Lemma 4 .

For draft verification algorithms that satisfy the constraints in Lemma 2, we have $\forall i\leq\gamma$, and $x^{i}\in{\cal X}^{i}$,

$$ $\Pr{\left({\tau\geq i\mid X^{i}=x^{i}}\right)}\leq p_{i}(x^{i}).$ $$

We defer the proof of the lemma to Section B.4 and first prove Theorem 2 based on the lemma.

We start by breaking down the expected number of decoded tokens $\mathbb{E}_{\textsc{Verify}}[N(i)]$ into the distribution of $N(i)$ on different sample paths. Let $O^{*}=O_{1},O_{2},\ldots,$ be the complete output sequence from speculative decoding. We set all tokens after E.O.S to be E.O.S as well. Then we have

$$ $\displaystyle\mathbb{E}_{\textsc{Verify}}[N(i)]=\sum_{\ell=1}^{\infty}\Pr_{ \textsc{Verify}}{\left({N(i)\geq\ell}\right)}=\sum_{x^{*}\in{\cal X}^{*}}\sum_ {\ell=1}^{\infty}\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},N(i)\geq\ell}\right)}.$ $$

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 $\forall{\bm{c}}$, and output $x^{*}$,

$$ $\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},N(i)\geq\ell\mid{\bm{c}}}\right)}\leq \Pr_{\textsc{BlockVerify}}{\left({O^{*}=x^{*},N(i)\geq\ell\mid{\bm{c}}}\right)}$ (13) $$

We prove the lemma by induction on the number of iterations $i$. When $i=1$, we have that $N(i)=\tau+1$, where $\tau$ is the number of accepted tokens. Hence by the guarantee in Lemma 2,

$$ $\displaystyle\quad\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},N(1)\geq\ell\mid{ \bm{c}}}\right)}$ $\displaystyle=\Pr_{\textsc{Verify}}{\left({O^{\ell}=x^{\ell},N(1)\geq\ell\mid{ \bm{c}}}\right)}\cdot{\cal M}_{b}^{*}(x^{\ell+1:*}\mid{\bm{c}},x^{\ell})\quad \quad\quad\quad\quad\quad\triangleleft\text{\lx@cref{creftype~refnum}{eqn:dist _accepted_path}}$ $\displaystyle=\Pr_{\textsc{Verify}}{\left({O^{\ell}=x^{\ell},\tau\geq\ell-1 \mid{\bm{c}}}\right)}\cdot{\cal M}_{b}^{*}(x^{\ell+1:*}\mid{\bm{c}},x^{\ell})$ $\displaystyle=\Pr_{\textsc{Verify}}{\left({X^{\ell-1}=x^{\ell-1},\tau\geq\ell- 1\mid{\bm{c}}}\right)}\cdot{\cal M}_{b}(x_{\ell}\mid{\bm{c}},x^{\ell-1})\cdot{ \cal M}_{b}^{*}(x^{\ell+1:*}\mid{\bm{c}},x^{\ell})$ $\displaystyle={\cal M}_{s}(x^{\ell-1}\mid{\bm{c}}){\cal M}_{b}^{*}(x^{\ell:*} \mid{\bm{c}},x^{\ell-1})\Pr_{\textsc{Verify}}{\left({\tau\geq\ell-1\mid X^{ \ell-1}=x^{\ell-1},{\bm{c}}}\right)}$ $\displaystyle\leq{\cal M}_{s}(x^{\ell-1}\mid{\bm{c}}){\cal M}_{b}^{*}(x^{\ell: *}\mid{\bm{c}},x^{\ell-1})\Pr_{\textsc{BlockVerify}}{\left({\tau\geq\ell-1\mid X ^{\ell-1}=x^{\ell-1},{\bm{c}}}\right)}\;\;\;\triangleleft\text{\lx@cref{ creftypeplural~refnum}{lem:accept_prob} and~\lx@cref{refnum}{lem:accept_prob_u pper}}$ $\displaystyle=\Pr_{\textsc{BlockVerify}}{\left({O^{*}=x^{*},N(1)\geq\ell\mid{ \bm{c}}}\right)}.$ (14) $$

Suppose the lemma holds for all iterations up to $i$, for the $(i+1)$th iteration, let $\tau_{i}$ be the number of tokens accepted in the $(i+1)$th iteration, we have

$$ $\displaystyle\quad\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},N(i+1)\geq\ell\mid{ \bm{c}}}\right)}$ $\displaystyle=\sum_{\ell^{\prime}<\ell}\Pr_{\textsc{Verify}}{\left({O^{*}=x^{* },N(i)={\ell^{\prime}}\mid{\bm{c}}}\right)}\Pr_{\textsc{Verify}}{\left({O^{*}= x^{*},\tau_{i+1}\geq\ell-\ell^{\prime}-1\mid{\bm{c}},N(i)=\ell^{\prime}}\right)}$ $\displaystyle=\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*}\mid{\bm{c}}}\right)} \sum_{\ell^{\prime}<\ell}\Pr_{\textsc{Verify}}{\left({N(i)={\ell^{\prime}}\mid O ^{*}=x^{*},{\bm{c}}}\right)}$ $\displaystyle\qquad\qquad\qquad\qquad\cdot\Pr_{\textsc{Verify}}{\left({O^{*}=x ^{*},\tau_{i+1}\geq\ell-\ell^{\prime}-1\mid{\bm{c}},N(i)=\ell^{\prime}}\right)}$ $\displaystyle={\cal M}_{b}(x^{*}\mid{\bm{c}})\sum_{\ell^{\prime}<\ell}\Pr_{ \textsc{Verify}}{\left({N(i)={\ell^{\prime}}\mid O^{*}=x^{*},{\bm{c}}}\right)} \Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},\tau_{i+1}\geq\ell-\ell^{\prime}-1 \mid{\bm{c}},N(i)=\ell^{\prime}}\right)}$ (15) $$

Let $\eta_{\textsc{Verify}}$ be a random variable distributed according to $\Pr_{\textsc{Verify}}{\left({N(i)={\ell^{\prime}}\mid O^{*}=x^{*},{\bm{c}}}
\right)}$, and

$$ $f_{\textsc{Verify}}(\eta)=\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},\tau_{i+1} \geq\ell-\eta-1\mid{\bm{c}},N(i)=\eta}\right)}.$ $$

Plugging these into Equation 15, we have

$$ $\displaystyle\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},N(i+1)\geq\ell\mid{\bm{c }}}\right)}={\cal M}_{b}(x^{*}\mid{\bm{c}})\mathbb{E}_{\eta_{\textsc{Verify}}} \left[f_{\textsc{Verify}}(\eta)\right]$ $$

Note that let ${\bm{c}}^{\prime}={\bm{c}},x^{\ell^{\prime}}$, we have

$$ $\displaystyle f_{\textsc{Verify}}(\eta)$ $\displaystyle=\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},\tau_{i+1}\geq\ell-\ell ^{\prime}-1\mid{\bm{c}},N(i)=\ell^{\prime}}\right)}$ $\displaystyle=\Pr_{\textsc{Verify}}{\left({O^{*}=x^{\ell^{\prime}:*},\tau\geq \ell-\ell^{\prime}-1\mid{\bm{c}}^{\prime}}\right)}$ $\displaystyle\leq\Pr_{\textsc{BlockVerify}}{\left({O^{*}=x^{\ell^{\prime}:*}, \tau\geq\ell-\ell^{\prime}-1\mid{\bm{c}}^{\prime}}\right)}$ $\displaystyle=\Pr_{\textsc{BlockVerify}}{\left({O^{*}=x^{*},\tau_{i+1}\geq\ell -\ell^{\prime}-1\mid{\bm{c}},N(i)=\ell^{\prime}}\right)}$ $\displaystyle=f_{\textsc{BlockVerify}}(\eta).$ $$

Hence we have

$$ $\displaystyle\Pr_{\textsc{Verify}}{\left({O^{*}=x^{*},N(i+1)\geq\ell\mid{\bm{c }}}\right)}\leq\mathbb{E}_{\eta_{\textsc{Verify}}}\left[f_{\textsc{BlockVerify }}(\eta)\right].$ $$

Note that $\Pr_{\textsc{BlockVerify}}{\left({O^{*}=x^{*},N(i+1)\geq\ell\mid{\bm{c}}}
\right)}=\mathbb{E}_{\eta_{\textsc{BlockVerify}}}\left[f_{\textsc{BlockVerify}
}(\eta)\right]$. It would be enough to prove that

$$ $\mathbb{E}_{\eta_{\textsc{Verify}}}\left[f_{\textsc{BlockVerify}}(\eta)\right] \leq\mathbb{E}_{\eta_{\textsc{BlockVerify}}}\left[f_{\textsc{BlockVerify}}( \eta)\right].$ (16) $$

By the induction hypothesis, we have $\eta_{\textsc{BlockVerify}}$ stochastically dominates [Quirk and Saposnik, ] $\eta_{\textsc{Verify}}$ for any valid verification algorithm. Moreover, by definition and Lemma 3,

$$ $f_{\textsc{BlockVerify}}(\eta)=\begin{cases}0&\text{ if }\eta<\ell-\gamma-1,\\ p_{\ell-\eta-1}(x^{\eta+1:\ell-1}\mid{\bm{c}},x^{\eta}),&\text{ if }\ell- \gamma-1\leq\eta\leq\ell-1\\ 1&\text{ if }\eta>\ell-1,\end{cases}$ $$

which is an increasing function of $\eta$. To see this, for $\eta^{\prime}=\eta+1$, we can obtain $p_{\ell-\eta^{\prime}-1}(x^{\eta^{\prime}+1:\ell-1}\mid{\bm{c}},x^{\eta^{
\prime}})$ by following the same recursion steps as in Equation 8 but replacing $p_{1}(x^{\eta+1:\ell-1}\mid{\bm{c}},x^{\eta})$ with $p_{0}(x^{\eta+2:\ell-1}\mid{\bm{c}},x^{\eta+1})=1$, and hence only increasing the values.

Hence Equation 16 holds  [Quirk and Saposnik, ]. This completes the induction step and the proof of Theorem 2.

###### Lemma 4 .

###### Lemma 5 .

### B.3 Proof of Lemma 3

Note that in Algorithm 2, $p_{i}=p_{i}(X^{i})$.
We prove the statement by backward induction. When $i=\gamma$, we have by definition of $h^{\rm block}_{\gamma}$, $\forall x^{\gamma}\in{\cal X}^{\gamma}$,

$$ $\Pr{\left({\tau\geq\gamma\mid X^{\gamma}=x^{\gamma}}\right)}=p_{\gamma}(x^{ \gamma}).$ $$

Suppose the statement holds for $i\geq\ell$. When $i=\ell-1$, we have

$$ $\displaystyle\;\;\;\;\;\Pr{\left({\tau\geq\ell-1\mid X^{\ell-1}=x^{\ell-1}} \right)}$ $\displaystyle=\sum_{x_{\ell}\in{\cal X}}{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{ \ell-1})\cdot\Pr{\left({\tau\geq\ell-1\mid X^{\ell}=x^{\ell}}\right)}$ $\displaystyle=\sum_{x_{\ell}\in{\cal X}}{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{ \ell-1})\cdot{\left({\Pr{\left({\tau\geq\ell\mid X^{\ell}=x^{\ell}}\right)}+ \Pr{\left({\tau<\ell\mid X^{\ell}=x^{\ell}}\right)}\cdot h^{\rm block}_{\ell}} \right)}$ $\displaystyle=\sum_{x_{\ell}\in{\cal X}}{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{ \ell-1})\cdot{\left({p_{\ell}(x^{\ell})+(1-p_{\ell}(x^{\ell}))\cdot h^{\rm block }_{\ell}}\right)},$ $\displaystyle=\sum_{x_{\ell}\in{\cal X}}{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{ \ell-1})\cdot p_{\ell}(x^{\ell})+h^{\rm block}_{\ell}\cdot\sum_{x_{\ell}\in{ \cal X}}{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{\ell-1})\cdot(1-p_{\ell}(x^{\ell} )).$ (17) $$

Note that in the definition of $h^{\rm block}_{\ell}$ (Equation 4),

$$ $\displaystyle\;\;\;\;\sum_{x}\max\{p_{\ell-1}(x^{\ell-1}){\cal M}_{b}(x\mid{ \bm{c}},x^{\ell-1})-{\cal M}_{s}(x\mid{\bm{c}},x^{\ell-1}),0\}$ $\displaystyle=\sum_{x}{\left({p_{\ell-1}(x^{\ell-1}){\cal M}_{b}(x\mid{\bm{c}} ,x^{\ell-1})-\min\{p_{\ell-1}(x^{\ell-1}){\cal M}_{b}(x\mid{\bm{c}},x^{\ell-1} ),{\cal M}_{s}(x\mid{\bm{c}},x^{\ell-1})\}}\right)}$ $\displaystyle=p_{\ell-1}(x^{\ell-1})-\sum_{x}\min\{p_{\ell-1}(x^{\ell-1}){\cal M }_{b}(x\mid{\bm{c}},x^{\ell-1}),{\cal M}_{s}(x\mid{\bm{c}},x^{\ell-1})\}$ $$

Hence

$$ $\displaystyle h^{\rm block}_{\ell}=\frac{p_{\ell-1}(x^{\ell-1})-\sum_{x}\min\{ p_{\ell-1}(x^{\ell-1}){\cal M}_{b}(x\mid{\bm{c}},x^{\ell-1}),{\cal M}_{s}(x \mid{\bm{c}},x^{\ell-1})\}}{1-\sum_{x}\min\{p_{\ell-1}(x^{\ell-1}){\cal M}_{b} (x\mid{\bm{c}},x^{\ell-1}),{\cal M}_{s}(x\mid{\bm{c}},x^{\ell-1})\}}.$ (18) $$

Moreover, we have

$$ $\displaystyle\sum_{x_{\ell}\in{\cal X}}{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{ \ell-1})\cdot p_{\ell}(x^{\ell})$ $\displaystyle=\sum_{x_{\ell}\in{\cal X}}{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{ \ell-1})\cdot p_{\ell}(x^{\ell})$ $\displaystyle=\sum_{x_{\ell}\in{\cal X}}\min\{p_{\ell-1}(x^{\ell-1}){\cal M}_{ b}(x_{\ell}\mid{\bm{c}},x^{\ell-1}),{\cal M}_{s}(x_{\ell}\mid{\bm{c}},x^{\ell- 1})\}$ $\displaystyle=\sum_{x\in{\cal X}}\min\{p_{\ell-1}(x^{\ell-1}){\cal M}_{b}(x \mid{\bm{c}},x^{\ell-1}),{\cal M}_{s}(x\mid{\bm{c}},x^{\ell-1})\}.$ (19) $$

Plugging (19) and (18) into (17), we get

$$ $\Pr{\left({\tau\geq\ell-1\mid X^{\ell-1}=x^{\ell-1}}\right)}=p_{\ell-1}(x^{ \ell-1}),$ $$

as desired. The lemma hence follows by induction.

### B.4 Proof of Lemma 4

Recall that we use $O^{\gamma+1}$ to denote the sequence $(X^{\tau},Y,Z^{\gamma-\tau})$ in Equation 6.
We prove the lemma by induction. When $i=1$, the lemma holds since else the output probability of $x_{1}$ will be higher than ${\cal M}_{b}(x_{1}\mid{\bm{c}})$. Suppose the lemma holds for all $i\leq\ell-1$. When $i=\ell$, we prove that it also holds by contradiction. Suppose there exists $x^{\ell}\in{\cal X}^{\ell}$ such that

$$ $\Pr{\left({\tau\geq\ell\mid X^{\ell}=x^{\ell}}\right)}>p_{\ell}(x^{\ell}).$ (20) $$

If $\forall i\leq\ell-1$, it satisfies that
$p_{i}(x^{i}){\cal M}_{b}(x_{i+1}\mid{\bm{c}},x^{i})\leq{\cal M}_{s}(x_{i+1}
\mid{\bm{c}},x^{i}),$
then we have in the recursive formula of $p_{i}$’s, we always have

$$ $p_{i}(x^{i})=p_{i-1}(x^{i-1})\frac{{\cal M}_{b}(x_{i}\mid{\bm{c}},x^{i-1})}{{ \cal M}_{s}(x_{i}\mid{\bm{c}},x^{i-1})},$ $$

and hence

$$ $p_{\ell-1}(x^{\ell-1})=\frac{{\cal M}_{b}(x^{\ell-1}\mid{\bm{c}})}{{\cal M}_{s }(x^{\ell-1}\mid{\bm{c}})},$ $$

And for $x^{\ell}$, we have

$$ $p_{\ell}(x^{\ell})=\min\{\frac{{\cal M}_{b}(x^{\ell}\mid{\bm{c}})}{{\cal M}_{s }(x^{\ell}\mid{\bm{c}})},1\}.$ $$

This would imply that

$$ $\displaystyle\Pr{\left({O^{\ell}=x^{\ell},\tau\geq\ell}\right)}$ $\displaystyle=\Pr{\left({X^{\ell}=x^{\ell}}\right)}\Pr{\left({\tau\geq\ell\mid X ^{\ell}=x^{\ell}}\right)}$ $\displaystyle>{\cal M}_{s}(x^{\ell}\mid{\bm{c}})\cdot\min\{\frac{{\cal M}_{b}( x^{\ell}\mid{\bm{c}})}{{\cal M}_{s}(x^{\ell}\mid{\bm{c}})},1\}$ $\displaystyle=\min\{{\cal M}_{b}(x^{\ell}\mid{\bm{c}}),{\cal M}_{s}(x^{\ell} \mid{\bm{c}})\},$ $$

which leads to a contradiction.

In the other case, if there exists $i<\ell$ such that, $p_{i}(x^{i})=1$. Let $i$ be the largest such index. In this case, we have ${\cal M}_{b}(x^{i}\mid{\bm{c}})>{\cal M}_{s}(x^{i}\mid{\bm{c}})$ since otherwise, we won’t have $p_{i}(x^{i})=1$. And we have

$$ $p_{\ell}(x^{\ell})=\frac{{\cal M}_{b}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}},x^{i}) }{{\cal M}_{s}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}},x^{i})}.$ $$

Then by the induction hypothesis, we have

$$ $\Pr{\left({O^{i}=x^{i},\tau\geq i}\right)}=\Pr{\left({X^{i}=x^{i}}\right)}\Pr{ \left({\tau\geq i\mid X^{i}=x^{i}}\right)}\leq{\cal M}_{s}(x^{i}\mid{\bm{c}})< {\cal M}_{b}(x^{i}\mid{\bm{c}}).$ $$

Hence

$$ $\Pr{\left({O^{i}=x^{i},\tau<i}\right)}=\Pr{\left({O^{i}=x^{i}}\right)}-\Pr{ \left({O^{i}=x^{i},\tau\geq i}\right)}={\cal M}_{b}(x^{i}\mid{\bm{c}})-{\cal M }_{s}(x^{i}\mid{\bm{c}})>0.$ $$

Note that when $O^{i}=x^{i},\tau<i$, by constraints in Equation 6, we have

$$ $\Pr{\left({O^{i+1:\ell}=x^{i+1:\ell}\mid O^{i}=x^{i},\tau<i}\right)}={\cal M}_ {b}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}},x^{i}).$ $$

This implies

$$ $\displaystyle\Pr{\left({O^{\ell}=x^{\ell}}\right)}$ $\displaystyle=\Pr{\left({O^{i}=x^{i},\tau<i}\right)}\cdot{\cal M}_{b}^{\ell-i} (x^{i+1:\ell}\mid{\bm{c}},x^{i})$ $\displaystyle\quad\quad\quad\quad+\Pr{\left({O^{i}=x^{i},\tau\geq i}\right)} \Pr{\left({O^{i+1:\ell}=x^{i+1:\ell}\mid O^{i}=x^{i},\tau\geq i}\right)}$ $$

Moreover, we have

$$ $\Pr{\left({O^{\ell}=x^{\ell}}\right)}={\cal M}_{b}(x^{i}){\cal M}_{b}^{\ell-i} (x^{i+1:\ell}\mid{\bm{c}},x^{i})$ $$

Combining both, we get

$$ $\displaystyle 1$ $\displaystyle=\frac{\Pr{\left({O^{\ell}=x^{\ell}}\right)}}{{\cal M}_{b}(x^{i}) {\cal M}_{b}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}},x^{i})}$ $\displaystyle=\Pr{\left({\tau<i\mid O^{i}=x^{i}}\right)}+\Pr{\left({\tau\geq i \mid O^{i}=x^{i}}\right)}\frac{\Pr{\left({O^{i+1:\ell}=x^{i+1:\ell}\mid O^{i}= x^{i},\tau\geq i}\right)}}{{\cal M}_{b}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}},x^{i })},$ $\displaystyle=1-\Pr{\left({\tau\geq i\mid O^{i}=x^{i}}\right)}{\left({\frac{ \Pr{\left({O^{i+1:\ell}=x^{i+1:\ell}\mid O^{i}=x^{i},\tau\geq i}\right)}}{{ \cal M}_{b}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}},x^{i})}-1}\right)},$ $$

and this implies that

$$ $\Pr{\left({O^{i+1:\ell}=x^{i+1:\ell}\mid O^{i}=x^{i},\tau\geq i}\right)}={\cal M }_{b}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}},x^{i}).$ (21) $$

Hence

$$ $\displaystyle\Pr{\left({O^{\ell}=x^{\ell},\tau\geq\ell}\right)}$ $\displaystyle\leq\Pr{\left({O^{\ell}=x^{\ell},\tau\geq i}\right)}$ $\displaystyle=\Pr{\left({O^{i}=x^{i},\tau\geq i}\right)}\Pr{\left({O^{i+1:\ell }=x^{i+1:\ell}\mid O^{i}=x^{i},\tau\geq i}\right)}$ $\displaystyle\leq{\cal M}_{s}(x^{i}\mid{\bm{c}})p_{i}(x^{i}){\cal M}_{b}^{\ell -i}(x^{i+1:\ell}\mid{\bm{c}},x^{i})$ $\displaystyle={\cal M}_{s}(x^{i}\mid{\bm{c}}){\cal M}_{b}^{\ell-i}(x^{i+1:\ell }\mid{\bm{c}},x^{i}).$ $$

However, by assumption,

$$ $\displaystyle\Pr{\left({O^{\ell}=x^{\ell},\tau\geq\ell}\right)}$ $\displaystyle=\Pr{\left({X^{\ell}=x^{\ell}}\right)}\Pr{\left({\tau\geq\ell\mid X ^{\ell}=x^{\ell}}\right)}$ $\displaystyle>{\cal M}_{s}(x^{\ell}\mid{\bm{c}})p_{\ell}(x^{\ell})$ $\displaystyle={\cal M}_{s}(x^{\ell}\mid{\bm{c}})\frac{{\cal M}_{b}^{\ell-i}(x^ {i+1:\ell}\mid{\bm{c}},x^{i})}{{\cal M}_{s}^{\ell-i}(x^{i+1:\ell}\mid{\bm{c}}, x^{i})}$ $\displaystyle={\cal M}_{s}(x^{i}\mid{\bm{c}}){\cal M}_{b}^{\ell-i}(x^{i+1:\ell }\mid{\bm{c}},x^{i}),$ $$

which leads to a contradiction. This completes the proof.

## Appendix 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 in
Algorithm 3 that allows the decoding
logic to
depend on the previous accept/reject decisions. We start by introducing
the greedy block verification algorithm
(Algorithm 4) and then discuss the necessary
modifications to maintain the identity distribution
guarantee.

Figure: Algorithm 4 Greedy block verification

The above greedy block verification algorithm has a similar procedure as
block verification (Algorithm 2) with differences in the setting of
of acceptance probabilities and residual distributions, as highlighted.

Similar to Algorithm 2, Algorithm 4 maintains a
list of probabilities $\tilde{p}_{i}$’s, which satisfies that $\min\{1,\tilde{p}_{i}\}$ is
the probability that the subblock $X^{i}$ is accepted. $h_{i}$’s are chosen to achieve the above acceptance
guarantee, and $p_{\rm res}^{\rm greedy}$’s are chosen to maintain the
identical
distribution guarantee.

Note that compared to $p_{i}$ in block verification, the recursive
definition of
$\tilde{p}_{i}$ doesn’t have a
minimum over one term, hence it
is always an upper bound on $p_{i}$’s. This leads to a higher acceptance
probability 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:

Accept $X_{1}X_{2}={\textsc{a}}{\textsc{b}},{\textsc{b}}{\textsc{a}},{\textsc{b}}{
\textsc{b}}$ with probability one, and sample an
extra token from ${\cal M}_{b}(\cdot).$ Accept
$X_{1}X_{2}={\textsc{a}}{\textsc{a}}$
with
probability 1/4 and sample an extra token from ${\cal M}_{b}(\cdot).$ When
$X_{1}X_{2}={\textsc{a}}{\textsc{a}}$ is rejected, accept no tokens and sample a correction
token $Y={\textsc{b}}$. Note that in this case, if the algorithm uses $Y$ as the
context for the next iteration and sample based on
${\cal M}_{b}$, the next token
will be a with probability $1/3$. This makes the total probability of
generating ba as the first two tokens

$$ $\displaystyle{\cal M}_{s}({\textsc{b}}{\textsc{a}})\Pr{\left({\text{Accept }{ \textsc{b}}{\textsc{a}}}\right)}+{\cal M}_{s}({\textsc{a}}{\textsc{a}})\Pr{ \left({\text{Reject }{\textsc{a}}{\textsc{a}}\text{ and }Y={\textsc{b}}}\right )}{\cal M}_{b}({\textsc{a}})$ $\displaystyle=2/9\cdot 1+4/9\cdot 3/4\cdot 1/3$ $\displaystyle=1/3,$ $$

which is higher than ${\cal M}_{b}({\textsc{b}}{\textsc{a}})=2/9$. This violates the identical
distribution guarantee. Below we introduce a distribution
modification algorithm, which can be used with
Algorithm 4 to maintain the identical distribution
guarantee.

Figure: Algorithm 5 Distribution modification

It can be shown that if $X^{\tau},Y$ are returned in
Algorithm 4, and the next $\tau-\gamma-1$ tokens are sampled
according to $\mathcal{M}_{\rm new}$ from Algorithm 5, the
identical distribution
guarantee is maintained. In particular, we have the following lemma:

###### Lemma 6 .

Let $X^{\gamma}\sim{\cal M}_{s}^{\gamma}(\cdot\mid{\bm{c}})$ be the
draft tokens and $X^{\tau},Y$ be the output from
Algorithm 4. Let $\mathcal{M}_{\rm new}$ be the modified distribution
based on Algorithm 5, and
$Z^{\gamma-\tau-1}\sim\mathcal{M}_{\rm new}^{\gamma-\tau-1}(\cdot\mid{\bm{c}},X
^{\tau},Y)$. Then we have

$$ $X^{\tau},Y,Z^{\gamma-\tau-1}\sim{\cal M}_{b}^{\gamma}(\cdot\mid{\bm{c}}).$ $$

The proof is presented in Section C.3. The above leads to
the following speculative decoding algorithm with
greedy block verification, presented in
Algorithm 6. Note that
Lemma 6 implies that it maintains the identical distribution guarantee.

Figure: Algorithm 6 Speculative decoding with greedy block verification

###### Lemma 6 .

### C.1 Comparison to block verification.

In one draft iteration, with
the same pair of draft and target distributions, greedy block verification is
always better.

###### Theorem 3 (Informal) .

In one draft
iteration with the same models ${\cal M}_{s},{\cal M}_{b}$ and draft length
$\gamma$, greedy block verification
decodes at least as many tokens as block verification.

The theorem is proved in Section 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 $X_{1}X_{2}={\textsc{a}}{\textsc{a}}$ and
they
are rejected by greedy block verification. It can be shown that the modified
distribution will be a point mass on token b. And in future iterations,
if the algorithm still uses ${\cal M}_{s}$ as the draft model, there is lower
chance that the draft tokens will be accepted. Hence, theoretically it is
unclear
whether one approach dominates the other.

Empirical comparison. We conduct the same set of experiments in
Section 6 on
greedy
block verification to compare the two approaches empirically. We list the
block efficiency comparison when PALM-2-XXS is used as the drafter and
$\gamma=8$ in Table 3. As 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 in other
parameter settings. Hence
we recommend using block verification instead of the greedy
version.

**Table 3: Block efficiency comparison between among token verification, block verification, and greedy block verification with $\gamma=8$. Each statistic is computed using $1000$ test prompts from different datasets on various tasks (each run is an average with 3 different random seeds).**
| Dataset | Token Verification | Block verification | Greedy block<br>verification |
| --- | --- | --- | --- |
| LM1B | $3.21$ | $\mathbf{3.49}$ | $3.30$ |
| GPT Prompt | $3.41$ | $\mathbf{3.76}$ | $3.51$ |
| WebQA | $3.44$ | $\mathbf{3.70}$ | $3.52$ |
| PIQA | $3.40$ | $\mathbf{3.68}$ | $3.49$ |
| ShareGPT | $3.34$ | $\mathbf{3.62}$ | $3.44$ |
| XSum | $3.49$ | $\mathbf{3.76}$ | $3.59$ |
| GSM8K | $3.81$ | $\mathbf{4.15}$ | $3.96$ |
| WMT-DeEn | $3.19$ | $\mathbf{3.41}$ | $3.26$ |

###### Theorem 3 (Informal) .

### C.2 Proof of Lemma 6

In the proof, we ignore the context ${\bm{c}}$ and the proof will generalize
to arbitrary ${\bm{c}}$. We start by introducing two useful quantities.

$$ $\displaystyle p_{\rm remain}(x^{i})$ $\displaystyle{:=}\sum_{x}\max\{{\cal M}_{b}(x^{i},x)-{\cal M}_{s}(x^{i},x),0\},$ (24) $\displaystyle p_{\rm rej}(x^{i})$ $\displaystyle{:=}\sum_{x}\max\{{\cal M}_{s}(x^{i},x)-{\cal M}_{b}(x^{i},x),0\}.$ (25) $$

Note that $p_{i}$ in Algorithm 4 depends on the draft
block $x^{i}$, and by the recursive definition of $\tilde{p}_{i}$’s, we have
$\tilde{p}_{i}=\frac{{\cal M}_{b}(x^{i})}{{\cal M}_{s}(x^{i})}.$ Hence we have

$$ $h_{i}=\frac{\sum_{x}\max\{\tilde{p}_{i}{\cal M}_{b}(x\mid{\bm{c}},X^{i})-{\cal M }_{s}(x\mid{\bm{c}},X^{i}),\,0\}}{\sum_{x}\max\{{\cal M}_{s}(x\mid{\bm{c}},X^{ i})-\tilde{p}_{i}{\cal M}_{b}(x\mid{\bm{c}},X^{i}),\,0\}}=\frac{p_{\rm remain} (x^{i})}{p_{\rm rej}(x^{i})}.$ $$

Moreover, the expression for $\tilde{p}_{i}$ also implies that $p_{\rm res}^{\rm greedy}(\cdot\mid{\bm{c}},X^{\tau})=\mathcal{M}_{\rm new}(
\cdot\mid{\bm{c}},X^{\tau})$.

We now prove the following lemma about the acceptance length
$\tau$ in Algorithm 4.

###### Lemma 7 .

For all $\ell\in[1,\gamma]$, and $x^{\ell}\in{\cal X}^{\ell}$,

$$ $\Pr{\left({X^{\ell}=x^{\ell},\tau\geq\ell}\right)}=\min\{{\cal M}_{b}(x^{\ell} ),{\cal M}_{s}(x^{\ell})\}.$ $$

###### Proof.

We prove this by induction in the backward direction. When $\ell=\gamma$, Step 12-14 in
Algorithm 4 accepts $X^{\gamma}$ with probability

$$ $\Pr{\left({\tau=\gamma\mid X^{\gamma}=x^{\gamma}}\right)}=\min\{1,\tilde{p}_{ \gamma}\}=\min\left\{1,\frac{{\cal M}_{b}(x^{\gamma})}{{\cal M}_{s}(x^{\gamma} )}\right\},$ $$

and hence

$$ $\displaystyle\Pr{\left({X^{\gamma}=x^{\gamma},\tau\geq\gamma}\right)}$ $\displaystyle=\Pr{\left({X^{\gamma}=x^{\gamma}}\right)}\Pr{\left({\tau=\gamma \mid X^{\gamma}=x^{\gamma}}\right)}=\min\left\{{\cal M}_{s}(x^{\gamma}),{\cal M }_{b}(x^{\gamma})\right\}.$ $$

Suppose the equation holds for $\ell\geq\ell_{0}$, for $\ell=\ell_{0}-1$, we have

$$ $\displaystyle\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\geq\ell_{0}-1} \right)}=\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\geq\ell_{0}}\right)}+ \Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau=\ell_{0}-1}\right)}.$ $$

Next we consider the two terms separately. For the first term, due to
the induction assumption, we have

$$ $\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\geq\ell_{0}}\right)}=\sum_{x\in{ \cal X}}\min\{{\cal M}_{b}(x^{\ell_{0}-1},x),{\cal M}_{s}(x^{\ell_{0}-1},x)\}$ $$

For the second term, we have

$$ $\displaystyle\;\;\;\;\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau=\ell_{0}-1} \right)}$ (26) $\displaystyle=\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\leq\ell_{0}-1} \right)}\cdot\Pr{\left({X^{\ell_{0}-1}\text{ is accepted.}}\right)}$ (27) $\displaystyle=\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\leq\ell_{0}-1} \right)}\cdot\Pr{\left({\eta_{\ell_{0}-1}\leq h_{\ell_{0}-1}}\right)}$ (28) $\displaystyle={\left({\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1}}\right)}-\Pr{ \left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\geq\ell_{0}}\right)}}\right)}\cdot \min\left\{1,\frac{p_{\rm remain}(x^{\ell_{0}-1})}{p_{\rm rej}(x^{\ell_{0}-1}) }\right\}$ $\displaystyle=\sum_{x\in{\cal X}}{\left({{\cal M}_{s}(x^{\ell_{0}-1},x)-\min\{ {\cal M}_{b}(x^{\ell_{0}-1},x),{\cal M}_{s}(x^{\ell_{0}-1},x)\}}\right)}\cdot \min\left\{1,\frac{p_{\rm remain}(x^{\ell_{0}-1})}{p_{\rm rej}(x^{\ell_{0}-1}) }\right\}$ (29) $\displaystyle=p_{\rm rej}(x^{\ell_{0}-1})\cdot\min\left\{1,\frac{p_{\rm remain }(x^{\ell_{0}-1})}{p_{\rm rej}(x^{\ell_{0}-1})}\right\}$ (30) $\displaystyle=\min\left\{p_{\rm remain}(x^{\ell_{0}-1}),p_{\rm rej}(x^{\ell_{0 }-1})\right\}.$ (31) $$

In the above derivation, (27) is due to that Algorithm 4 is outputing the longest accepted subblock.
(29) is due to the induction hypothesis.
(30) is due to the definition of $p_{\rm rej}$ in
(25).

Combining the two terms, we have

$$ $\displaystyle\;\;\;\,\,\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\geq\ell_{ 0}-1}\right)}$ $\displaystyle=\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau\geq\ell_{0}}\right )}+\Pr{\left({X^{\ell_{0}-1}=x^{\ell_{0}-1},\tau=\ell_{0}-1}\right)}$ $\displaystyle=\sum_{x\in{\cal X}}\min\{{\cal M}_{b}(x^{\ell_{0}-1},x),{\cal M} _{s}(x^{\ell_{0}-1},x)\}+\min\left\{p_{\rm remain}(x^{\ell_{0}-1}),p_{\rm rej} (x^{\ell_{0}-1})\right\}$ $\displaystyle=\min\{\sum_{x\in{\cal X}}\min\{{\cal M}_{b}(x^{\ell_{0}-1},x),{ \cal M}_{s}(x^{\ell_{0}-1},x)\}+p_{\rm remain}(x^{\ell_{0}-1}),$ $\displaystyle\qquad\qquad\qquad\sum_{x\in{\cal X}}\min\{{\cal M}_{b}(x^{\ell_{ 0}-1},x),{\cal M}_{s}(x^{\ell_{0}-1},x)\}+p_{\rm rej}(x^{\ell_{0}-1})\}$ $\displaystyle=\min\left\{\sum_{x\in{\cal X}}{\cal M}_{b}(x^{\ell_{0}-1},x), \sum_{x\in{\cal X}}{\cal M}_{s}(x^{\ell_{0}-1},x)\right\}$ (32) $\displaystyle=\min\left\{{\cal M}_{b}(x^{\ell_{0}-1}),{\cal M}_{s}(x^{\ell_{0} -1})\right\},$ $$

which is the desired quantity in the lemma. This concludes the proof.
Here (32) is due to the definition of
$p_{\rm remain}$ and $p_{\rm rej}$ in (24) and
(25).
∎

Next we proceed to prove Lemma 6. Let $O^{\gamma}=(X^{\tau},Y,Z^{\gamma-\tau-1})$. It would be enough to show that for all $i\leq\gamma$
and $x^{i}\in{\cal X}^{i}$,

$$ $\Pr{\left({O^{i}=x^{i}}\right)}={\cal M}_{b}(x^{i}).$ $$

We prove this via induction. Note that the corollary holds for $i=0$,
which is the trivial case and both sides are equal to 1.
Suppose the claim holds for $i\leq i_{0}$. This means $\forall x^{i_{0}}\in{\cal X}^{i_{0}}$, we have

$$ $\Pr{\left({O^{i_{0}}=x^{i_{0}}}\right)}={\cal M}_{b}(x^{i_{0}}).$ $$

When $i=i_{0}+1$, by the algorithm, we have that either $\tau\geq i_{0}+1$, where $O_{i_{0}+1}$ is
an accepted token, or $\tau\leq i_{o}$, where $O_{i_{0}+1}$ is sampled according to $\mathcal{M}_{\rm new}(\cdot\mid O^{i_{0}})$. By Lemma 7, we have

$$ $\displaystyle\;\;\;\;\Pr{\left({O^{i_{0}+1}=x^{i_{0}+1}}\right)}$ $\displaystyle=\Pr{\left({O^{i_{0}+1}=x^{i_{0}+1},\tau\geq i_{0}+1}\right)}+\Pr {\left({O^{i_{0}+1}=x^{i_{0}+1},\tau\leq i_{0}}\right)}$ $\displaystyle=\Pr{\left({X^{i_{0}+1}=x^{i_{0}+1},\tau\geq i_{0}+1}\right)}+\Pr {\left({O^{i_{0}}=x^{i_{0}},\tau\leq i_{0}}\right)}\cdot p_{\rm res}^{x^{i_{0} }}(x_{i_{0}+1})$ $\displaystyle=\Pr{\left({X^{i_{0}+1}=x^{i_{0}+1},\tau\geq i_{0}+1}\right)}+{ \left({\Pr{\left({O^{i_{0}}=x^{i_{0}}}\right)}-\Pr{\left({O^{i_{0}}=x^{i_{0}}, \tau\geq i_{0}+1}\right)}}\right)}\cdot\mathcal{M}_{\rm new}(x_{i_{0}+1}\mid x ^{i_{0}}))$ $\displaystyle=\min\{{\cal M}_{b}(x^{i_{0}+1}),{\cal M}_{s}(x^{i_{0}+1})\}+{ \left({{\cal M}_{b}(x^{i_{0}})-\sum_{x}\min\{{\cal M}_{b}(x^{i_{0}},x),{\cal M }_{s}(x^{i_{0}},x)\}}\right)}\cdot\mathcal{M}_{\rm new}(x_{i_{0}+1}\mid x^{i_{ 0}}))$ (33) $\displaystyle=\min\{{\cal M}_{b}(x^{i_{0}+1}),{\cal M}_{s}(x^{i_{0}+1})\}+\sum _{x}{\left({{\cal M}_{b}(x^{i_{0}},x)-{\cal M}_{s}(x^{i_{0}},x)}\right)}_{+} \cdot\mathcal{M}_{\rm new}(x_{i_{0}+1}\mid x^{i_{0}}))$ $\displaystyle=\min\{{\cal M}_{b}(x^{i_{0}+1}),{\cal M}_{s}(x^{i_{0}+1})\}+{ \left({{\cal M}_{b}(x^{i_{0}},x_{i_{0}+1})-{\cal M}_{s}(x^{i_{0}},x_{i_{0}+1}) }\right)}_{+}$ (34) $\displaystyle={\cal M}_{b}(x^{i_{0}+1}).$ $$

Here (33) follows by the induction
hypothesis, and (34) follows by the
definition of $\mathcal{M}_{\rm new}$ in (23). By
induction, this concludes the proof.

###### Lemma 7 .

###### Proof.

### C.3 Proof of Theorem 3

To prove Theorem 3, we first observe the following: For Algorithm 4, let $\tau$ be the number of accepted tokens, due to Lemma 7, we have

$$ $\displaystyle\mathbb{E}_{X^{\gamma}\sim{\cal M}_{s}^{\gamma}}[\tau]$ $\displaystyle=\sum_{\ell=1}^{\gamma}\Pr{\left({\tau\geq\ell}\right)}=\sum_{ \ell=1}^{\gamma}\sum_{x^{\ell}\in{\cal X}^{\ell}}\Pr{\left({X^{\ell}=x^{\ell}, \tau\geq\ell}\right)}$ $\displaystyle=\sum_{\ell=1}^{\gamma}\sum_{x^{\ell}\in{\cal X}^{\ell}}\min\{{ \cal M}_{s}(x^{\ell}),{\cal M}_{b}(x^{\ell})\}.$ $$

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.
Formally, let $\pi$ be a joint distribution over ${\cal X}^{\gamma}\times{\cal X}^{\gamma}$, then Algorithm 4 solves the following optimization problem.

$$ $\displaystyle\max_{\pi}\mathbb{E}_{X^{\gamma},y^{\gamma}\sim\pi}\left[\beta(X^ {\gamma},y^{\gamma})\right],$ (35) $$

subject to constraints

$$ $\displaystyle\sum_{y^{\gamma}}\pi(x^{\gamma},y^{\gamma})$ $\displaystyle={\cal M}_{s}(x^{\gamma}),\;\;\forall x^{\gamma}\in{\cal X}^{ \gamma},$ (36) $\displaystyle\sum_{x^{\gamma}}\pi(x^{\gamma},y^{\gamma})$ $\displaystyle={\cal M}_{b}(y^{\gamma}),\;\;\forall y^{\gamma}\in{\cal X}^{ \gamma}.\vspace{-.1in}$ (37) $$

For all $x^{\gamma},y^{\gamma}\in{\cal X}^{\gamma}$, let the *maximum common prefix length* be defined as

$$ $\beta(x^{\gamma},y^{\gamma}){:=}\max_{\ell\leq\gamma}\{\forall i\leq\ell,x_{i} =y_{i}\}.$ $$

In this above formulation, the marginal distributions satisfy $X^{\gamma}\sim{\cal M}_{s}^{\gamma}$ and $Y^{\gamma}\sim{\cal M}_{b}^{\gamma}$. And the maximum common prefix length refers to the number of accepted tokens in one iteration of speculative decoding.
Note that the optimization problem can be viewed as an optimal transport problem [Villani et al., ] between distributions ${\cal M}_{s}^{\gamma}(\cdot)$ and ${\cal M}_{b}^{\gamma}(\cdot)$ with the cost function being $(\gamma-\beta(X^{\gamma},Y^{\gamma})$. The next lemma establishes the optimality of Algorithm 4 in solving this problem.

###### Lemma 8 .

The solution to Equation 35 is upper bounded by

$$ $\displaystyle\sum_{\tau=1}^{\gamma}\sum_{x^{\tau}\in{\cal X}^{\tau}}\min\{{ \cal M}_{s}(x^{\ell}),{\cal M}_{b}(x^{\ell})\}$ $$

Proof of Lemma 8:
For all $\pi\in\Pi({\cal M}^{\gamma}_{s},{\cal M}^{\gamma}_{b})$ and $X^{\gamma},Y^{\gamma}\sim\pi$, we have

$$ $\displaystyle\mathbb{E}_{X^{\gamma},Y^{\gamma}}[\beta(X^{\gamma},Y^{\gamma})]$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{\ell\leq\gamma}\text{Pr}_{ X^{\gamma},Y^{\gamma}}\left(\beta(X^{\gamma},Y^{\gamma})\geq\ell\right)$ $\displaystyle=\sum_{\ell\leq\gamma}\sum_{x^{\ell}}\text{Pr}_{X^{\gamma},Y^{ \gamma}}\left(X^{1:\ell}=Y^{1:\ell}=x^{\ell},\beta(X^{\gamma},Y^{\gamma})\geq \ell\right)$ $\displaystyle\leq\sum_{\ell\leq\gamma}\sum_{x^{\ell}}\text{Pr}_{X^{\gamma},Y^{ \gamma}}\left(X^{1:\ell}=Y^{1:\ell}=x^{\ell}\right)$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{\ell\leq\gamma}\sum_{x^ {\ell}}\min\left\{\text{Pr}\left(X^{1:\ell}=x^{\ell}\right),\text{Pr}\left(Y^{ 1:\ell}=x^{\ell}\right)\right\}$ $\displaystyle=\sum_{\ell\leq\gamma}\sum_{x^{\ell}}\min\{{\cal M}_{s}^{\ell}(x^ {\ell}),{\cal M}_{b}^{\ell}(x^{\ell})\}.$ $$

Here $(a)$ follows from the fact that for a positive integer random variable $\mathbb{E}[X]=\sum_{i}\Pr(X\geq 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^{\gamma}$ to be the draft tokens and $Y^{\gamma}=(X^{\tau},Y^{\prime},Z^{\gamma-\tau-1})$ where $(X^{\tau},Y^{\prime})$ are the outputs from Algorithm 2 and $Z^{\gamma-\tau-1}\sim{\cal M}_{b}(\cdot\mid{\bm{c}},X^{\tau},Y)$.

###### Lemma 8 .

## Appendix D Additional Results

In this section, we present experimental results for the same set of experiments described in Section 6 with different block lengths ($\gamma=4,6,8$) and different drafters (PALM-2-XXS and PALM-2-XXXS):

- •
Table 4. Drafter: PALM-2-XXS, $\gamma=4$.
- •
Table 5. Drafter: PALM-2-XXS, $\gamma=6$.
- •
Table 6. Drafter: PALM-2-XXXS, $\gamma=4$.
- •
Table 7. Drafter: PALM-2-XXXS, $\gamma=6$.
- •
Table 8. Drafter: PALM-2-XXXS, $\gamma=8$.

**Table 4: Speedup comparison between token verification (TokenV) and block verification (BlockV) with $\gamma=4$ 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 3 different random seeds). Numbers after $\pm$ represent standard deviation.**
| Dataset | Block efficiency | Wall clock time speedup over baseline |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| TokenV | BlockV | Improve. $\uparrow$ % | TokenV | BlockV | Improve. $\uparrow$ % |  |
| LM1B | $2.78\pm 0.01$ | $2.88\pm 0.01$ | $3.48\pm 0.24$ | $2.36\pm 0.00$ | $2.42\pm 0.01$ | $2.51\pm 0.22$ |
| GPT Prompt | $2.88\pm 0.01$ | $3.00\pm 0.00$ | $4.33\pm 0.25$ | $2.43\pm 0.01$ | $2.51\pm 0.00$ | $3.43\pm 0.24$ |
| WebQA | $2.91\pm 0.01$ | $2.99\pm 0.01$ | $2.83\pm 0.65$ | $2.45\pm 0.01$ | $2.50\pm 0.01$ | $1.94\pm 0.61$ |
| PIQA | $2.89\pm 0.00$ | $2.99\pm 0.01$ | $3.48\pm 0.21$ | $2.44\pm 0.00$ | $2.50\pm 0.01$ | $2.66\pm 0.20$ |
| ShareGPT | $2.85\pm 0.01$ | $2.95\pm 0.00$ | $3.48\pm 0.19$ | $2.41\pm 0.01$ | $2.47\pm 0.00$ | $2.63\pm 0.17$ |
| XSum | $2.94\pm 0.01$ | $3.03\pm 0.01$ | $3.24\pm 0.51$ | $2.48\pm 0.01$ | $2.54\pm 0.01$ | $2.35\pm 0.48$ |
| GSM8K | $3.12\pm 0.01$ | $3.21\pm 0.02$ | $3.06\pm 0.95$ | $2.62\pm 0.01$ | $2.68\pm 0.02$ | $2.19\pm 0.89$ |
| WMT-DeEn | $2.75\pm 0.01$ | $2.83\pm 0.01$ | $2.99\pm 0.09$ | $2.33\pm 0.01$ | $2.38\pm 0.01$ | $2.18\pm 0.09$ |
| Average | $2.89$ | $2.99$ | $3.36$ | $2.44$ | $2.50$ | $2.49$ |

**Table 5: Speedup comparison between token verification (TokenV) and block verification (BlockV) with $\gamma=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 3 different random seeds). Numbers after $\pm$ represent standard deviation.**
| Dataset | Block efficiency | Wall clock time speedup over baseline |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| TokenV | BlockV | Improve. $\uparrow$ % | TokenV | BlockV | Improve. $\uparrow$ % |  |
| LM1B | $3.08\pm 0.01$ | $3.27\pm 0.01$ | $6.42\pm 0.07$ | $2.32\pm 0.01$ | $2.43\pm 0.01$ | $5.00\pm 0.06$ |
| GPT Prompt | $3.22\pm 0.01$ | $3.44\pm 0.02$ | $6.55\pm 0.83$ | $2.42\pm 0.00$ | $2.54\pm 0.02$ | $5.06\pm 0.77$ |
| WebQA | $3.26\pm 0.01$ | $3.44\pm 0.01$ | $5.60\pm 0.22$ | $2.45\pm 0.01$ | $2.55\pm 0.01$ | $4.24\pm 0.21$ |
| PIQA | $3.22\pm 0.02$ | $3.43\pm 0.02$ | $6.36\pm 0.78$ | $2.42\pm 0.01$ | $2.54\pm 0.01$ | $4.92\pm 0.72$ |
| ShareGPT | $3.18\pm 0.02$ | $3.37\pm 0.01$ | $6.13\pm 0.53$ | $2.39\pm 0.02$ | $2.50\pm 0.01$ | $4.74\pm 0.49$ |
| XSum | $3.29\pm 0.01$ | $3.48\pm 0.01$ | $5.91\pm 0.82$ | $2.47\pm 0.01$ | $2.58\pm 0.01$ | $4.47\pm 0.77$ |
| GSM8K | $3.56\pm 0.01$ | $3.80\pm 0.03$ | $6.86\pm 0.60$ | $2.66\pm 0.01$ | $2.80\pm 0.02$ | $5.38\pm 0.56$ |
| WMT-DeEn | $3.04\pm 0.01$ | $3.19\pm 0.01$ | $4.92\pm 0.29$ | $2.29\pm 0.01$ | $2.37\pm 0.01$ | $3.57\pm 0.27$ |
| Average | $3.23$ | $3.43$ | $6.10$ | $2.43$ | $2.54$ | $4.67$ |

**Table 6: Speedup comparison between token verification (TokenV) and block verification (BlockV) with $\gamma=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 3 different random seeds). Numbers after $\pm$ represent standard deviation.**
| Dataset | Block efficiency | Wall clock time speedup over baseline |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| TokenV | BlockV | Improve. $\uparrow$ % | TokenV | BlockV | Improve. $\uparrow$ % |  |
| LM1B | $2.24\pm 0.00$ | $2.33\pm 0.01$ | $4.23\pm 0.44$ | $2.25\pm 0.00$ | $2.34\pm 0.01$ | $3.89\pm 0.41$ |
| GPT Prompt | $2.41\pm 0.02$ | $2.48\pm 0.01$ | $2.96\pm 1.00$ | $2.42\pm 0.02$ | $2.48\pm 0.01$ | $2.72\pm 0.94$ |
| WebQA | $2.38\pm 0.01$ | $2.45\pm 0.01$ | $2.87\pm 0.13$ | $2.39\pm 0.01$ | $2.45\pm 0.01$ | $2.63\pm 0.12$ |
| PIQA | $2.36\pm 0.01$ | $2.43\pm 0.01$ | $3.22\pm 0.37$ | $2.37\pm 0.01$ | $2.44\pm 0.01$ | $2.97\pm 0.35$ |
| ShareGPT | $2.34\pm 0.00$ | $2.42\pm 0.01$ | $3.49\pm 0.12$ | $2.35\pm 0.00$ | $2.42\pm 0.01$ | $3.16\pm 0.12$ |
| XSum | $2.38\pm 0.01$ | $2.45\pm 0.01$ | $2.91\pm 0.63$ | $2.39\pm 0.01$ | $2.45\pm 0.01$ | $2.68\pm 0.60$ |
| GSM8K | $2.51\pm 0.01$ | $2.58\pm 0.02$ | $2.99\pm 0.47$ | $2.51\pm 0.01$ | $2.58\pm 0.02$ | $2.74\pm 0.44$ |
| WMT-DeEn | $2.22\pm 0.00$ | $2.28\pm 0.00$ | $2.59\pm 0.09$ | $2.24\pm 0.00$ | $2.29\pm 0.00$ | $2.37\pm 0.08$ |
| Average | $2.35$ | $2.43$ | $3.16$ | $2.36$ | $2.43$ | $2.89$ |

**Table 7: Speedup comparison between token verification (TokenV) and block verification (BlockV) with $\gamma=6$ 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 3 different random seeds). Numbers after $\pm$ represent standard deviation.**
| Dataset | Block efficiency | Wall clock time speedup over baseline |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| TokenV | BlockV | Improve. $\uparrow$ % | TokenV | BlockV | Improve. $\uparrow$ % |  |
| LM1B | $2.36\pm 0.01$ | $2.48\pm 0.00$ | $4.93\pm 0.46$ | $2.27\pm 0.01$ | $2.37\pm 0.00$ | $4.55\pm 0.43$ |
| GPT Prompt | $2.58\pm 0.04$ | $2.72\pm 0.02$ | $5.57\pm 1.29$ | $2.46\pm 0.03$ | $2.59\pm 0.01$ | $5.10\pm 1.22$ |
| WebQA | $2.54\pm 0.00$ | $2.68\pm 0.02$ | $5.46\pm 0.50$ | $2.43\pm 0.00$ | $2.55\pm 0.01$ | $5.02\pm 0.47$ |
| PIQA | $2.50\pm 0.00$ | $2.62\pm 0.01$ | $5.06\pm 0.39$ | $2.39\pm 0.00$ | $2.50\pm 0.01$ | $4.66\pm 0.37$ |
| ShareGPT | $2.47\pm 0.01$ | $2.60\pm 0.01$ | $5.10\pm 0.49$ | $2.37\pm 0.01$ | $2.48\pm 0.01$ | $4.69\pm 0.46$ |
| XSum | $2.54\pm 0.01$ | $2.67\pm 0.01$ | $4.83\pm 0.47$ | $2.43\pm 0.01$ | $2.54\pm 0.01$ | $4.45\pm 0.44$ |
| GSM8K | $2.71\pm 0.03$ | $2.83\pm 0.00$ | $4.27\pm 0.89$ | $2.58\pm 0.02$ | $2.69\pm 0.00$ | $3.92\pm 0.84$ |
| WMT-DeEn | $2.31\pm 0.01$ | $2.43\pm 0.02$ | $5.38\pm 0.57$ | $2.21\pm 0.00$ | $2.32\pm 0.01$ | $4.99\pm 0.54$ |
| Average | $2.50$ | $2.63$ | $5.07$ | $2.39$ | $2.50$ | $4.67$ |

**Table 8: Speedup comparison between token verification (TokenV) and block verification (BlockV) with $\gamma=8$ 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 3 different random seeds). Numbers after $\pm$ represent standard deviation.**
| Dataset | Block efficiency | Wall clock time speedup over baseline |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| TokenV | BlockV | Improve. $\uparrow$ % | TokenV | BlockV | Improve. $\uparrow$ % |  |
| LM1B | $2.40\pm 0.01$ | $2.55\pm 0.01$ | $6.19\pm 0.43$ | $2.13\pm 0.01$ | $2.25\pm 0.01$ | $5.28\pm 0.40$ |
| GPT Prompt | $2.66\pm 0.01$ | $2.82\pm 0.02$ | $6.28\pm 1.01$ | $2.35\pm 0.01$ | $2.47\pm 0.02$ | $5.37\pm 0.95$ |
| WebQA | $2.61\pm 0.01$ | $2.78\pm 0.00$ | $6.27\pm 0.49$ | $2.31\pm 0.01$ | $2.43\pm 0.00$ | $5.39\pm 0.46$ |
| PIQA | $2.57\pm 0.01$ | $2.76\pm 0.01$ | $7.48\pm 0.51$ | $2.27\pm 0.01$ | $2.42\pm 0.01$ | $6.51\pm 0.47$ |
| ShareGPT | $2.54\pm 0.01$ | $2.71\pm 0.01$ | $6.63\pm 0.72$ | $2.25\pm 0.01$ | $2.38\pm 0.01$ | $5.68\pm 0.68$ |
| XSum | $2.60\pm 0.01$ | $2.77\pm 0.00$ | $6.46\pm 0.49$ | $2.30\pm 0.01$ | $2.43\pm 0.00$ | $5.53\pm 0.46$ |
| GSM8K | $2.82\pm 0.02$ | $2.98\pm 0.03$ | $5.48\pm 1.18$ | $2.49\pm 0.01$ | $2.60\pm 0.03$ | $4.62\pm 1.11$ |
| WMT-DeEn | $2.37\pm 0.00$ | $2.49\pm 0.01$ | $5.33\pm 0.46$ | $2.10\pm 0.00$ | $2.20\pm 0.01$ | $4.53\pm 0.43$ |
| Average | $2.57$ | $2.73$ | $6.27$ | $2.28$ | $2.40$ | $5.36$ |

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: - How will the speedup results scale when using larger models?

- How are probabilities of all subblocks calculated?

 - 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?

## Post-rebuttal comment

The authors addressed the questions raised in my review, and I have increased my score accordingly.
soundness: 4
strengths: Overall, the paper is well written and the problem is clearly stated.

The theoretical proofs are sound to the best of my knowledge.
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.
weaknesses: The paper does not provide sufficient evidence that it provides a considerable speedup.
Speedup 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. 

It was not clear how the probabilities for all subblocks are calculated. 

# Minor comments 

Page 7, line 336: “I.e., it measures” should be “Specifically, it measures”

Page 8, line 425: “all valid verification algorithm” should be “all valid verification algorithms”

Page 8: I think Figure 4 should be labeled as a Table instead of a figure

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
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?
2. How does the performance compare with Medusa/Eagle's static tree attention?
soundness: 3
strengths: 1. **Block Verification** improves efficiency by verifying token blocks rather than individual tokens in speculative decoding, preserving the same distribution.

2. Block verification achieves consistent 5–8% speedup and is broadly applicable across models and datasets.

3. Block verification is easy to implement, with minimal modifications to existing speculative decoding systems.
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.
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?
2. The explanations of the formulas and algorithms lack intuitive clarity, making comprehension more challenging, even though the modifications from token verification are not large.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: - Are there specific conditions or types of LLM architectures where the performance gains of Block Verification may be more pronounced or limited?
- How does the algorithm handle edge cases where the distributions of the drafting and target models diverge significantly?
soundness: 3
strengths: - The paper provides solid theoretical guarantees, ensuring that the proposed method does not compromise the output distribution.
- The experiments validate the practical benefits, with performance gains across a diverse set of tasks.
- The proposed algorithm does not increase code complexity, making it easy to integrate into existing LLM architectures.
- The paper highlights how Block Verification compares favorably to related methods, strengthening its contribution.
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.
weaknesses: - The depth of proofs might be challenging for practitioners without a strong mathematical background, potentially limiting the paper's audience.
- There is a typo in the manuscript: page 8, line 413: deocding -> decoding

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: I would like to raise some questions to improve the manuscripts.

1. 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.
2. 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?
3. 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.
soundness: 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.
2. 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. 
3. 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.
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.
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:

1. 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.
2. 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.
3. Currently, I think there exists a large room (more than 1 page) to conduct more experiments.
   - 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**.
   - Experiments for combining block verification to some latest speculative decoding methods (e.g. Medusa [6] and Eagle [7]).

I 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.



[1] Hu, Zhengmian, and Heng Huang. "Accelerated Speculative Sampling Based on Tree Monte Carlo." *Forty-first International Conference on Machine Learning*.

[2] Dubey, Abhimanyu, et al. "The llama 3 herd of models." *arXiv preprint arXiv:2407.21783* (2024).

[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).

[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.

[5] Xia, Heming, et al. "Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding." *arXiv preprint arXiv:2401.07851* (2024).

[6] Cai, Tianle, et al. "Medusa: Simple llm inference acceleration framework with multiple decoding heads." *arXiv preprint arXiv:2401.10774* (2024).

[7] Li, Yuhui, et al. "Eagle: Speculative sampling requires rethinking feature uncertainty." *arXiv preprint arXiv:2401.15077* (2024).

Meta-review: (a) Summary of Scientific Claims and Findings

The paper introduces a novel approach to draft verification in speculative decoding that processes multiple tokens as a block rather than individually. The authors demonstrate that this method preserves the target model’s output distribution and achieves optimal performance in terms of tokens accepted per iteration. Empirical results across various datasets indicate a consistent 5%-8% reduction in wall-clock time compared to traditional token-by-token verification, particularly at non-zero decoding temperatures.

(b) Strengths of the Paper

1. Simplicity and Integration: The proposed method is straightforward, requiring minimal changes to existing systems, and integrates easily into speculative decoding workflows.

2. Theoretical Soundness: The approach is backed by rigorous theoretical guarantees, ensuring reliability and optimality.

3. Broad Applicability: The method has demonstrated consistent effectiveness across multiple models (e.g., PALM-2, Vicuna) and development platforms (PyTorch, JAX).

(c) Weaknesses of the Paper and Missing Elements

1. Modest Speedups: The reported 5%-8% improvement in wall-clock time, while consistent, raises questions about the practical significance of the contribution.

2. Limited Experimental Scope: The experiments lack diversity, with no exploration of multi-draft speculative decoding or comparisons to tree-based verification methods.

(d) Decision and Rationale

The method’s simplicity, consistency, and strong theoretical guarantees support its use as a default approach for speculative decoding. However, the modest speedup and limited novelty relative to prior work remain as the weakness of this work.

Decision: Accept (Poster)