PEARL: Parallel Speculative Decoding with Adaptive Draft Length

## Abstract

Abstract Speculative decoding (SD), where an extra draft model is employed to provide multiple draft tokens first and then the original target model verifies these tokens in parallel, has shown great power for LLM inference acceleration.
However, existing SD methods suffer from the mutual waiting problem, i.e., the target model gets stuck when the draft model is guessing tokens, and vice versa. This problem is directly incurred by the asynchronous execution of the draft model and the target model, and is exacerbated due to the fixed draft length in speculative decoding.
To address these challenges, we propose a conceptually simple, flexible, and general framework to boost speculative decoding, namely P arallel sp E culative decoding with A daptive d R aft L ength (PEARL).
Specifically, PEARL proposes pre-verify to verify the first draft token in advance during the drafting phase, and post-verify to generate more draft tokens during the verification phase.
PEARL parallels the drafting phase and the verification phase via applying the two strategies, and achieves adaptive draft length for different scenarios, which effectively alleviates the mutual waiting problem.
Moreover, we theoretically demonstrate that the mean accepted tokens of PEARL is more than existing draft-then-verify works.
Experiments on various text generation benchmarks demonstrate the effectiveness of our PEARL, leading to a superior speedup performance up to 3.79 × \times × and 1.52 × \times × , compared to auto-regressive decoding and vanilla speculative decoding, respectively. Our code is available at https://github.com/smart-lty/ParallelSpeculativeDecoding.

## 1 Introduction

Large language models (LLMs) such as GPT-4, LlaMA, and Claude 3 (Achiam et al., ; ; Bommasani et al., ; Touvron et al., ) have dominated the natural language understanding and generation (Khurana et al., ) over a wide range of applications. However, the substantial inference latency of these LLMs has emerged as a significant obstacle bounding their broader application in scenarios with restricted computational resources. This latency primarily originates from the auto-regressive token-by-token decoding process wherein decoding $K$ tokens requires $K$ serial runs of LLMs, incurring exacerbated latency with both the length of generated tokens and the model scale.

Figure: Figure 1: An overview of speculative decoding and our PEARL. (a) SD employs a draft model to provide multiple drafts and then the target model verifies the drafts in parallel. However, SD suffers from the mutual waiting problem, i.e., the target model gets stuck when the draft model is guessing tokens, and vice versa. (b) PEARL parallels the drafting and verification process to alleviate the mutual waiting problem. (c) PEARL can utilize adaptive draft length to further mitigate the mutual waiting problem. PEARL can generate less draft tokens if they will be rejected (left in (c)), while PEARL can generate more draft tokens if they can be accepted (right in (c)).
Refer to caption: x1.png

To address this challenge, extensive research efforts have been devoted to accelerating LLM inference. One innovative inference paradigm, Speculative Decoding (SD),
has emerged as a new trend and shown superior performance. As shown in Figure. 1(a), the key idea of SD algorithm is to employ an extra small model (referred as the draft model) to firstly generate $\gamma$ draft tokens for the original large model (referred as the target model), and then the target model verifies these draft tokens in parallel within a single forward. Here, $\gamma$ is a fixed hyperparameter window size.
Draft length is the number of tokens generated by the draft model in a continuous execution. Therefore, the draft length is set to $\gamma$ in SD.
Following-up works effectively extend this framework by either removing the necessity of the draft model (Cai et al., ; Fu et al., ; Zhang et al., ) or identifying compact draft model with high distribution alignment (Zhou et al., ; Zhao et al., ; Miao et al., ).
Extensive experiments demonstrate that this draft-then-verify framework effectively enhances the concurrency of the target model, thereby significantly accelerating the inference process.

Albeit with multiple benefits of this draft-then-verify framework, it confronts one significant challenge that may hinder its performance and deployment—the mutual waiting problem. That is, the target model will be idle when the draft model is generating the draft tokens and the draft model will be idle when the target model is verifying the previously drafted tokens. This mutual waiting problem primarily stems from two limitations inherent in speculative decoding: (i) the asynchronous execution of the draft and verify phases, which directly results in the mutual waiting problem; and (ii) the fixed draft length, which cannot adapt to most decoding steps and thus exacerbate the mutual waiting problem.

Therefore, in this paper, we seek to answer the question: Can we draft and verify in parallel and adaptively adjust draft length?
With this consideration, we
propose a conceptually simple, flexible, and general framework to boost speculative decoding, namely Parallel spEculative decoding with Adaptive dRaft Length (PEARL). Specifically, PEARL consists of two strategies pre-verify and post-verify: (i) pre-verify uses the target model to verify the first draft token during drafting phase, which allows the draft model to generate less draft tokens in difficult scenarios; (ii) post-verify uses the draft model to continue generating draft tokens during verification phase, which provides more draft tokens in simple situations. As shown in Figure.1(b)(c), PEARL effectively alleviates the mutual waiting problem with parallelism and adaptive draft length via these two strategies. Moreover, we theoretically show that PEARL can eliminate the burden of tuning the hyperparameter $\gamma$, and the mean accepted tokens of PEARL is more than existing draft-then-verify works.

Our key contributions can be summarized as follows:

- (i)
We propose PEARL, a novel inference acceleration framework, which can effectively alleviate the mutual waiting problem with parallelism and adaptive draft length.
- (ii)
We theoretically derive the optimal window size and
the mean accepted tokens of our PEARL, which demonstrates the effectiveness of our PEARL.
- (iii)
We conduct extensive experiments on various text generation benchmarks, leading to a superior speedup performance up to 3.79$\times$ and 1.52$\times$, compared to auto-regressive decoding and speculative decoding, respectively.

## 2 Background

Figure: Figure 2: Motivated experiments. (a) The time of both drafting phase and verification phase is non-negligible, therefore the asynchronous execution of the draft model and the target model directly incurs the mutual waiting problem. (b) We observe that the optimal draft length changes significantly in different iterations, which exacerbates the mutual waiting problem.
Refer to caption: x2.png

Notations. In this paper, we use $M_{q}$ to denote the draft model and $M_{p}$ to denote the target model. $M_{q}(\cdot),M_{p}(\cdot)$ denotes the logits of the next token of a single forward of $M_{q},M_{p}$ respectively. $\gamma$ is a hyperparameter to control the window size during speculative decoding. We denote the running speed between $M_{q}$ and $M_{p}$ as $c$, which is defined as the ratio between the time for a single forward of $M_{p}$ and the time for a single forward of $M_{q}$, i.e., $c=T(M_{p}(\cdot))/T(M_{q}(\cdot))$.

Speculative decoding. Given an input sequence $\mathbf{x}$ as prefix, a speculative decoding step consists of a drafting phase and a verification phase. During the drafting phase, the draft model $M_{q}$ is employed to give $\gamma$ draft tokens $x_{1},x_{2},...,x_{\gamma}$ by running $\gamma$ times model forward and sample. Here, we denote $M_{q}(\mathbf{x}+[x_{1},...,x_{i-1}])$ as $q_{i}$, then each draft token is given by
$x_{i}\sim q_{i},i=1,...,\gamma$. During the verification phase, the prefix $\mathbf{x}$ together with $\gamma$ draft tokens are sent to $M_{p}$ for verification. The target model $M_{p}$ inputs $\mathbf{x}+[x_{1},...,x_{\gamma}]$ and outputs the logits $p_{1},p_{2},...,p_{\gamma+1}$. Then SD sequentially verifies $x_{i}$ via speculative sampling, where the acceptance rate is given by:

$$ $\alpha_{i}=\left\{\begin{aligned} &1\qquad\quad p_{i}[x_{i}]\geq q_{i}[x_{i}], \\ &\frac{p_{i}[x_{i}]}{q_{i}[x_{i}]}\quad p_{i}[x_{i}]<q_{i}[x_{i}],\\ \end{aligned}\right.$ (1) $$

If SD rejects $x_{i}$, it will resample a token from $norm(\max(0,p_{i}-q_{i}))$, otherwise SD accepts all the draft tokens and samples an additional token from $p_{\gamma+1}$. In this way, each SD step generates tokens with a number of at least 1 and at most $\gamma+1$, leading to the efficiency acceleration.

Window size and draft length. We emphasize that the window size is a hyperparameter that controls the drafting behavior. Draft length is the number of tokens generated by the draft model in a continuous execution, which is fixed and same as the window size in SD, while draft length is adaptive and may be not equal to window size in PEARL.

Choices of model combinations. There are several ways to obtain the draft model for speculative inference. On the one hand, existing open-source LLMs typically include corresponding off-the-shelf smaller architectures pre-trained on the same datasets (e.g., Codellama 7B as the draft model of Codellama 34B (Roziere et al., )). On the other hand, it is feasible to train a highly aligned draft model. However, the training process is typically resource-consuming, and the resulting model often lacks generalizability across different tasks. Therefore, in this paper, we focus primarily on leveraging existing open-source model families to assess our PEARL.

## 3 Methodology

### 3.1 Motivated Observation

We conduct some experiments to directly illustrate the mutual waiting problem. As shown in Figure. 2(a), we observe that the time consumed during the drafting phase and the verification phase is usually non-negligible. Take the instance of Codellama 7B & 70B, at each decoding step, the draft model will be inactive for 0.07s during the verification phase, while the target model will be inactive for 0.14s during the drafting phase. Therefore, the mutual waiting problem exists at any timestamp.

The asynchronous execution of the draft model and the target model is the direct cause of the mutual waiting problem, which is determined by two requirements of speculative decoding: (1) the drafting phase requires the input prefix to be verified; (2) the verification phase requires the draft model to complete generating draft tokens. This implies the great potential for alleviating the mutual waiting problem through parallelism: if we can remove the two requirements and parallel the drafting phase and the verification phase, a substantial acceleration can be possible.

Another limitation that aggravates the mutual waiting problem is the fixed draft length in SD, which is not appropriate for all the decoding steps. As shown in Figure 2(b), the optimal draft length changes significantly in different iterations. On the one hand, when the optimal draft length is less than the fixed draft length, the draft model will generate meaningless draft tokens that stucks the target model. On another hand, when the optimal draft length is more than the fixed draft length, the draft model could have generated more draft tokens that can be accepted by the target model with a single forward. However, a fixed draft length will interrupt the longer drafting phase and take an additional verification phase, which strengths the mutual waiting problem as well. This motivates our PSD to further alleviates the mutual waiting problem with adaptive draft length.

Together with the two motivations, we propose two simple and effective strategies, pre-verify and post-verify. The pre-verify removes requirement 2 and allows the target model to verify the first draft token in advance. The post-verify removes requirement 1 and allows the draft model to continue generating draft tokens during the verification phase. The two strategies enable parallelism and achieve adaptive draft length to effectively alleviate the mutual waiting problem.

Figure: Figure 3: Illustration of our PEARL. At $T=0$, $M_{q}$ generates $x_{1},x_{2},x_{3}$ and $M_{p}$ rejects $x_{1}$ with the pre-verify strategy. At $T=3t$, $M_{p}$ accepts $x_{4}$ and switches to the post-verify strategy. At $T=6t$, $M_{p}$ accepts all draft tokens $x_{4},x_{5},x_{6}$ in the last decoding step, while $M_{q}$ continues drafting $x_{7},x_{8},x_{9}$. At $T=9t$, $M_{p}$ rejects $x_{9}$, drops $x_{10},x_{11},x_{12}$ and switches to the pre-verify strategy. The final output is $[y_{1},x_{4},x_{5},x_{6},x_{7},x_{8},y_{2}]$.
Refer to caption: x3.png

### 3.2 Pre-verify: verify the first draft token in advance.

The pre-verify strategy aims at removing the requirement that the verification phase requires the draft model to complete generating draft tokens. Therefore, we seek to verify some draft tokens in advance during drafting phase. We delve explicitly into the drafting stage. During the drafting phase, the draft model tries to give $\gamma$ draft tokens by running $\gamma$ times model forward. We find that the input of the draft model in $\gamma$ times forward is $\mathbf{x}$, $\mathbf{x}+[x_{1}]$, …, $\mathbf{x}+[x_{1},x_{2},...,x_{\gamma-1}]$, respectively. Only the origin prefix $\mathbf{x}$ can be acquired by the target model for parallel verification. Therefore, we propose to run the target model to output the logits $M_{p}(\mathbf{x})$ in parallel. In this way, we can verify the first token $x_{1}$ before the verification phase. We implement the same lossless verification method following (Leviathan et al., ) as illustrated in Section 2.

By applying such a pre-verify strategy, we can verify the first draft token before the verification phase. If the first token is rejected, all of the following draft tokens are meaningless and should be dropped. Hence we could skip the verification phase and directly conduct the next drafting phase with the prefix $\mathbf{x}+[y_{1}]$. If the first token is accepted, all the draft tokens will be sent to the target model in the verification phase. In Figure. 3, at the timestamp of $T=0$, the draft model generates $x_{1},x_{2},x_{3}$ while the target model outputs $p_{0}^{t}$, rejects the first token $x_{1}$ and sample another token $y_{1}$. At the timestamp of $T=3t$, the draft model generates $x_{4},x_{5},x_{6}$ while the target model accepts the first token $x_{4}$. Then $x_{4},x_{5},x_{6}$ is sent to the target model in the next verification phase.

### 3.3 Post-verify: continue drafting during verification.

The post-verify strategy aims at removing the requirement that the drafting phase requires the input prefix to be verified. However, this assumption brings the limitation that the draft model should be stuck until the target model finishes verification.

Therefore, we discard this assumption and make another assumption: we directly assume that all the draft tokens can be accepted. In this way, We find that when all the $\gamma$ draft tokens are accepted, sampling a new token from $M_{p}(\mathbf{x}+[x_{1},...,x_{\gamma}])$ is not necessary, as the draft model could have generated more draft tokens that can be accepted. Hence we can use the draft model to continue drafting $x_{\gamma+1},...,x_{2\gamma}$ during the verification phase.

If all the $\gamma$ draft tokens are accepted, we can skip the next drafting phase as we have already get the draft tokens in the next drafting phase. The last logit $M_{p}(\mathbf{x}+[x_{1},...,x_{\gamma}])$ can be used to verify $x_{\gamma+1}$, which is a "pre-verify" process as well. In Figure. 3, at the timestamp of $T=6t$, the target model takes in $x_{4},x_{5},x_{6}$ and outputs $p^{t}_{x_{4}},p^{t}_{x_{5}},p^{t}_{x_{6}}$, while the draft model continues to guess next draft tokens $x_{7},x_{8},x_{9}$. Fortunately, all the draft tokens are accepted, and we can directly conduct next verification phase with prefix $\mathbf{x}+[y_{1},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9}]$. At the timestamp of $T=9t$, the target model takes in $x_{7},x_{8},x_{9}$ and outputs $p^{t}_{x_{7}},p^{t}_{x_{8}},p^{t}_{x_{9}}$, while the draft model continues to guess the next draft tokens $x_{10},x_{11},x_{12}$. Unfortunately, only $x_{8}$ is accepted, and the draft tokens $x_{10},x_{11},x_{12}$ will be dropped. Finally, the prefix $\mathbf{x}+[y_{1},x_{4},x_{5},x_{6},x_{7},x_{8},y_{2}]$ is input to the next drafting phase.

### 3.4 PEARL: parallel speculative decoding with adaptive draft length

Figure: Algorithm 1 Parallel Speculative Decoding with Adaptive Draft Length.

Take together the two strategies, our PEARL framework consists of a draft model, a target model and two strategies to decode tokens. The two strategies are switched according to the verification results in the last decoding step. Algorithm. 1 provides a summary of our PEARL. We also provide more details in Algorithm. 2. Then we show how our PEARL achieves parallelism and adaptive draft length to alleviate the mutual waiting problem.

Parallelism. With the two strategy pre-verify and post-verify, At any timestamp, the draft model and the target model are running in parallel, which directly breaks the asynchronous execution of the draft model and the target model.

Adaptive draft length. In our PEARL, the drafting process can be seen as segmented drafting process. If the draft model cannot generate any "right" tokens, the pre-verify strategy will avoid the additional drafting process. If the draft model could have generated more "right" tokens, the target model will not interrupt the drafting phase, where the draft model can generate more draft tokens with post-verify strategy. Therefore, PEARL can utilize the two simple yet effective strategies to implement adaptive draft length to alleviate the mutual waiting problem.

## 4 Analysis

In this section, we give some interesting theoretical findings to demonstrate the generalization ability and effectiveness of our PEARL.

### 4.1 Eliminating the burden of tuning γ 𝛾 \gamma italic_γ

During a standard speculative decoding step, the draft model takes $\gamma$ model forward to decode $\gamma$ draft tokens and then the target model takes 1 model forward to verify the draft tokens. If $\gamma$ is set too small, we cannot fully exploit the ability of the draft model, and the realistic speedup will be tiny. If $\gamma$ is set too large, the extra overhead of running draft model will cover the acceleration of speculative decoding, leading to an undesirable speedup. Hence it is crucial to find an optimal value of $\gamma$ for considerable acceleration.

Assuming the acceptance rate is $\alpha$, the optimal value $\gamma^{\prime}$ of $\gamma$ in SD is given as follows:

$$ $\gamma^{\prime}=\mathop{\arg\max}_{\gamma}SD(\gamma)=\mathop{\arg\max}_{\gamma }\frac{1-\alpha^{\gamma+1}}{(1-\alpha)(\frac{\gamma}{c}+1)}$ (2) $$

However, there lies some issues in finding $\gamma^{\prime}$ with this equation. On the one hand, this equation makes an important assumption that the acceptance rate of each token is i.i.d.. Actually, this assumption is only an approximation, leading to difficulties in finding an appropriate $\gamma$. On another hand, the value of $\alpha$ may vary in different scenarios, as the draft model and the target model may show different alignments in different scenarios. Therefore, for a specific downstream application, one needs to search an optimal value of $\gamma$, which brings severe burden and limits the application of speculative decoding.

In our PEARL, $\gamma^{\prime}$ can be theoretically found without these issues. We give Theorem. 1 to show that the optimal value of $\gamma$ is exactly $c$.

###### Theorem 1

Given a draft model $M_{q}$ and a target model $M_{p}$, the optimal value of the window size $\gamma$ is the ratio of the running speed of the draft model and the target model, i.e.,

$$ $\gamma^{\prime}=\mathop{\arg\max}_{\gamma}\ \text{PEARL}(\gamma)=c.$ (3) $$

We prove this theorem in Appendix B. Intuitively, increasing or decreasing $\gamma^{\prime}$ does not contribute for better efficiency. We conduct experiments in Section 5.4.1 to empirically demonstrate this theorem, which is important for our PEARL to eliminate the burden of tuning $\gamma$.

###### Theorem 1

### 4.2 Expectation of the number of accepted tokens

As our PEARL is based on the standard speculative decoding, we theoretically compare the decoding step of our PEARL and standard SD. Suppose the draft model $M_{q}$ and the target model $M_{p}$ are same in the two algorithms. We do not introduce any extra training or fine-tuning, hence the acceptance rate for each token $\alpha$ is same and can be seen as a constant in the following analysis.

We begin our analysis by computing the expectation of the number of accepted tokens within a drafting phase and a verification phase. Note that in our PEARL, if all the draft tokens in a drafting phase are accepted, PEARL will continue drafting more draft tokens. We regard the process that the draft model decodes draft tokens until some tokens are rejected as a drafting phase when computing the expectation.

###### Theorem 2

Assuming the acceptance rate of each draft token is $\alpha$, and $\alpha$ is i.i.d., the expectation of the number of accepted tokens of PEARL is

$$ $E(\#accepted\ tokens)=\frac{1}{1-\alpha}+1.$ (4) $$

We prove this theorem in Appendix B. We give a more intuitive explanation of this theorem: given a prefix, if the draft model $M_{q}$ can decode $\delta$ draft tokens at most that can be accepted by the target model, then $M_{q}$ will continue to decode $\delta$ tokens without been interrupted by the target model verification. It can be explained as an adaptive "$\gamma$" for each prefix to achieve better speedup.

Note that the expectation of accepted tokens of other draft-then-verify works is $\frac{1-\alpha^{\gamma+1}}{1-\alpha}$. With Theorem. 2, it is easily to show that the expectation of accepted tokens of PEARL is more than standard SD, i.e., $\frac{1}{1-\alpha}+1\geq\frac{1-\alpha^{\gamma+1}}{1-\alpha}$. From this perspective, we can demonstrate the effectiveness of our PEARL. We will conduct experiments in Section 5.4.2 to show the empirical results of mean accepted tokens in both standard SD and our PEARL.

###### Theorem 2

## 5 Experiments

### 5.1 Experimental setup

Tasks and Datasets. We conduct experiments on various text generation tasks to evaluate the effectiveness of our PEARL, including code generation, arithmetic reasoning, and multi-round dialogue. For code generation task, we utilize HumanEval (Chen et al., ), which is composed of 164 code generation problems. For arithmetic reasoning, we employ the GSM8K (Cobbe et al., ) dataset with the first 100 math problems. For multi-round dialogue, we use MT-bench (Zheng et al., ) with 80 multi-round conversation problems in different scenarios.

Models and Metrics. We evaluate the effectiveness of our PEARL with some state-of-the-art LLMs. For HumanEval, we employ both code-specialized LLMs and general LLMs, including CodeLlama-hf (Roziere et al., ), Deepseek-Coder(Guo et al., ) and Llama 2(Touvron et al., ). For GSM8K and MT-bench, we employ Llama 2 to conduct text generation. In our experiments, the models with size of 1.3B and 6/7B are used as the draft models and the models with size of 33/34B and 70B are used as the target models. We report the text generation speed to compute the walltime speedup ratio as the metric. We provide more evaluation details in Appendix C.

Baseline Methods. We implement four variants of LLM inference methods as our baselines.
(i) Speculate decoding: standalone SD methods (Leviathan et al., ; Chen et al., ) resort to a draft model to draft future tokens and then verify them in parallel. (ii) Ouroboros: ouroboros (Zhao et al., ) proposes phrase candidate pool from the verification process to generate more precise and longer drafts. (iii) Lookahead Decoding: look ahead decoding (Fu et al., ) caches the generation trajectory (n-grams) as drafts to reduce the number of total decoding steps.
(iv) Distillspec: DistillSpec (Zhou et al., ) distillates and derives a better aligned and compact draft model.

### 5.2 Main results.

**Table 1: Experiment results on the code generation task. The results of speculative decoding and Ouroboros are taken from Zhao et al. (). We bold the best results for each model combination. * Some results of ouroboros and lookahead decoding are reproduced in our implementation.**
|  | Codellama7B&34B | Codellama7B&70B | Llama 2 7B&70B | Deepseek 7B&33B | Deepseek 1.3B&33B |
| --- | --- | --- | --- | --- | --- |
| Auto Regressive | 1.00$\times$ | 1.00$\times$ | 1.00$\times$ | 1.00$\times$ | 1.00$\times$ |
| Speculative Decoding | 1.69$\times$ | 2.76$\times$ | 2.14$\times$ | 2.07$\times$ | 2.54$\times$ |
| Ouroboros | 2.14$\times$ | * 3.28$\times$ | * 2.10$\times$ | * 2.66$\times$ | * 3.25$\times$ |
| Lookahead | 1.72$\times$ | * 1.04$\times$ | * 1.01$\times$ | * 1.05$\times$ | * 1.05$\times$ |
| Ours | 2.35$\times$ | 3.79$\times$ | 3.01$\times$ | 2.75$\times$ | 3.48$\times$ |

**Table 2: Experiment results using Llama 7B&70B on GSM8K and MT-bench. The results of speculative decoding and Ouroboros are taken from Zhao et al. (). The symbol ‘ - ’ denotes that the results has not been report in original papers. We bold the best results.**
|  | Speculative Decoding | Ouroboros | Lookahead Decoding | Distillspec | PEARL (ours) |
| --- | --- | --- | --- | --- | --- |
| GSM8K | 1.99$\times$ | 2.68$\times$ | 1.00$\times$ | - | 2.87$\times$ |
| MT-bench | 1.63$\times$ | 1.40$\times$ | 1.45$\times$ | 2.13$\times$ | 2.48$\times$ |

Table 1 shows that PEARL significantly outperforms vanilla speculative decoding, ouroboros, and lookahead decoding in all backbone model configurations on the HumanEval dataset. Specifically, PEARL can achieve up to 3.79 $\times$ speed up compared with vanilla auto-regressive methods. These experimental results demonstrate that PEARL effectively addresses the mutual waiting issue, thereby achieving significant inference acceleration results compared to methods based on the traditional draft-then-verify framework. PEARL can also achieve significant inference acceleration in conventional natural language processing tasks, whereas vanilla speculative decoding, lookahead decoding yield only limited improvements acceleration. As shown in Table 2, PEARL leads to superior performances on the GSM8K and MT-bench datasets.

### 5.3 Ablation studies

**Table 3: Ablation results of PEARL on HumanEval and GSM8K datasets on the speed up metric.**
|  | HumanEval | GSM8K |  |  |
| --- | --- | --- | --- | --- |
| Methods | CodeLlama 7B&34B | CodeLlama 7B&70B | DeepSeek 1.3B&33B | Llama 2 7B&70B |
| PEARL w/o pre-verify | 2.21$\times$ | 3.53$\times$ | 3.19$\times$ | 2.51$\times$ |
| PEARL w/o post-verify | 1.64$\times$ | 2.57$\times$ | 2.37$\times$ | 2.15$\times$ |
| PEARL | 2.35$\times$ | 3.79$\times$ | 3.48$\times$ | 2.87$\times$ |

To provide more insights of the two proposed strategies, we conduct the ablation study. We denote PEARL without pre-verify as PEARL w/o pre-verify and PEARL without post-verify as PEARL w/o pre-verify and present the main results of ablation studies.

As shown in Table 3, the absence of any strategy of PEARL results in a performance degradation of the entire framework. The absence of the post-verify strategy exhibits a pronounced impact on the performance of PEARL than the pre-verify strategy.
Intuitively, the pre-verify strategy makes more contributions when the acceptance rate is relatively low, while the post-verify strategy makes more contributions when the two model is effectively aligned. Therefore, the two strategies are complementary and accelerate inference together. In our experiments, all the model combinations show great alignment, which leads to the superiority of the post-verify strategy.

### 5.4 Case studies

**Table 4: Comparison of mean average accepted tokens per second of vanilla SD methods and PEARL.**
| Methods | CodeLlama 7B&34B | CodeLlama 7B&70B | DeepSeek 1.3B&33B | DeepSeek 6.7B&33B |
| --- | --- | --- | --- | --- |
| SD | 5.27 | 8.32 | 7.23 | 5.69 |
| PEARL | 27.95 | 26.53 | 29.65 | 39.90 |

#### 5.4.1 Optimal results of the window size γ 𝛾 \gamma italic_γ

**Table 5: Results on the optimal $\gamma$ of different mo- del combinations on HumanEval.**
| $\gamma$ | CodeLlama 7&34 | CodeLlama 7&70 | DeepSeek 6.7&33 |
| --- | --- | --- | --- |
| (c=3) | (c=5) | (c=3) |  |
| 2 | 48.67 | 25.07 | 41.47 |
| 3 | 65.59 | 38.57 | 65.12 |
| 4 | 63.25 | 49.07 | 65.07 |
| 5 | 57.26 | 58.10 | 64.42 |
| 6 | 58.64 | 57.05 | 63.60 |

As mentioned in Section 4.1, PEARL eliminates the need for tuning the hyperparameter of window size and can theoretically predetermine the optimal value of $\gamma$. In this section, we conduct experiments with various gamma values in our PEARL to demonstrate the impact of the optimal $\gamma$ on accelerating LLM inference. As shown in Table 6, we can observe that with the predetermined optimal $\gamma$, PEARL achieves the maximum inference acceleration. In certain cases involving suboptimal $\gamma$, the inference acceleration improvement in PEARL is less significant, underscoring the importance of predetermining the gamma value.

#### 5.4.2 Mean accepted tokens

In Section 4.2, we theoretically demonstrate that the expected number of accepted tokens in PEARL exceeds that of the vanilla SD method. To further illustrate the real mean accepted tokens in PEARL under real-world complex conditions, we conduct experiments on the HumanEval, GSM8K, and MT-Bench datasets. As shown in Table 6, we still empirically observe that that PEARL obtains more accepted tokens compared to vanilla SD methods, which further demonstrates the effectiveness of the PEARL framework. Specifically, PEARL achieves the max number of mean accepted tokens to 39.9, which significantly outperforms vanilla SD methods by a large margin. These results demonstrate that our PEARL can fully exploit the inference ability of the draft model for further acceleration.

## 6 Related Work

Transformer inference acceleration.
There exists extensive works for transformer inference acceleration. This includes efforts of model compression (Zhu et al., ), efficient architecture design (Chitty-Venkata and Somani, ), and hardware optimization and implementation (Dao et al., ). Model compression methods such as quantization (Choi et al., ), knowledge distillation (Hinton et al., ), and structure pruning (Han et al., ) aim at reducing the number of computational operations. Efficient architecture design is proposed to develop lightweight transformer architectures. Hardware optimization and implementation is proposed for efficient execution to fully exploit the hardware devices. These methods have achieved great success, while they are orthogonal to speculative decoding algorithms, which can be integrated for further speedup.

Draft-then-verify framework. While SD exhibits great acceleration effectiveness and lossless generalization quality, it remains a challenge to find a compact draft model with high distribution alignment. Some works focus on removing the necessity of the draft model. Self-speculative decoding (Zhang et al., ) proposes to skip some intermediate layers of the target model for drafting. Medusa (Cai et al., ) adds extra decoding heads at the top of the target model to generate drafts. Lookahead decoding(Fu et al., ) caches the generation trajectory (n-grams) as the drafts.
DistillSpec (Zhou et al., ) utilizes distillation method to identify a compact draft model. Ouroboros (Zhao et al., ) combines the standard SD and lookahead decoding to generate more precise and longer drafts. Besides these works, SpecInfer (Miao et al., ) proposes tree attention, which is widely used to verify more drafts and increase the acceptance rate. However, all of them do not address the parallelism issue. From this perspective, our PEARL is orthogonal to these methods and can be integrated with these methods, which is left as a future work.

## 7 Conclusion and Future Work

Limitations. As our PEARL is a parallel acceleration framework, it remains a challenge to schedule the GPU resources to avoid resource competitions.

Conclusion. In this paper, we propose a novel inference acceleration framework, called PEARL, which significantly improves LLM inference efficiency. PEARL consists of two simple and effective strategies, i.e., pre-verify and post-verify, which effectively alleviates the mutual waiting problem with parallelism and
adaptive draft length. Moreover, We theoretically derive the optimal window size and the mean accepted tokens of our PEARL, which demonstrates the effectiveness of our PEARL. Extensive experiments demonstrate that our proposed PEARL outperforms existing state-of-the-art methods on various text generation benchmarks.

Future work.
For future research, we aim to integrate PEARL with existing accelerated inference methods to explore more efficient and resource-friendly acceleration approaches for LLM inference. Hopefully, PEARL will facilitate the future development of LLM inference acceleration.

## Appendix A Algorithm of PEARL

Here, we give the whole algorithm of our PEARL in details in Algorithm. 2.

Figure: Algorithm 2 Parallel Speculative Decoding with Adaptive Draft Length.

## Appendix B Proof of Theorem 1 and Theorem 2

As illustrated in Section 4, we have two theorems to demonstrate the effectiveness of our PEARL. Here we give the proof of these two theorems.

Theorem 1
Given a draft model $M_{q}$ and a target model $M_{p}$, the optimal value of the window size $\gamma$ is the ratio of the running speed of the draft model and the target model, i.e.,

$$ $\gamma^{\prime}=\mathop{\arg\max}_{\gamma}\ \text{PEARL}(\gamma)=c.$ (5) $$

Proof.
We discuss the situation that $\gamma<c$ and $\gamma>c$.

If $\gamma$ is smaller than $c$, the draft model will wait for the target model until it finishes the verification. The draft model could have generated more draft tokens to be verified without extra time consumed, That is to say, the situation $\gamma<c$ decreases the number of verified tokens, where PEARL needs to take more steps for inference.

If $\gamma$ is larger than $c$, the target model will wait for the draft model until it finishes generating draft tokens. Theoretically, the drafting phase takes $\max(\gamma t,ct)$ and the verification phase takes $ct$, while the verification phase can verify $\gamma$ tokens. Therefore, the verification speed is $\frac{\max(\gamma t,ct)+ct}{\gamma}$. As $\gamma>c$, the verification speed is $\frac{(\gamma+c)}{\gamma}t$. Obviously, the optimal value of $\gamma$ is $c$.

$\square$

Theorem 2
Assuming the acceptance rate of each draft token is $\alpha$, and $\alpha$ is i.i.d., the expectation of the number of accepted tokens of PEARL is

$$ $E(\#accepted\ tokens)=\frac{1}{1-\alpha}+1.$ (6) $$

Proof. While vanilla speculative decoding can decode $\gamma+1$ tokens at most, our PEARL can decode infinity tokens due to the adaptive draft length, therefore the expectation of accepted tokens is given by:

$$ $\displaystyle E$ $\displaystyle=\sum_{k=0}^{\infty}kP(acc=k)$ (7) $\displaystyle=(1-\alpha)\sum_{k=0}^{\infty}k\alpha^{k}$ $$

Let $S=\sum_{k=0}^{\infty}k\alpha^{k}$, $\alpha S=\sum_{k=1}^{\infty}(k-1)\alpha^{k}$, we have:

$$ $\displaystyle E$ $\displaystyle=(1-\alpha)S=S-\alpha S$ (8) $\displaystyle=\sum_{k=0}^{\infty}k\alpha^{k}-\sum_{k=1}^{\infty}(k-1)\alpha^{k}$ $\displaystyle=\frac{1}{1-\alpha}$ $$

Counting the additional token generated by the target model, the expectation is:

$$ $E=\frac{1}{1-\alpha}+1$ (9) $$

$\square$

## Appendix C Evaluation Details

### C.1 Model Configurations

We select some representative models for evaluation, including Llama 2 Touvron et al. [], Codellama Roziere et al. [] and Deepseek-Coder Guo et al. []. We summarize the model configuration in Table 7. In our experiments, all models are loaded in the precision of bfloat-16. Our PEARL does not introduce any additional training, and directly uses these models to evaluate our algorithm. The running speed is measured on the code generation tasks.

**Table 7: Detailed model configurations.**
| Models | Layers | dim | FFN dim | speed (tok/s) |
| --- | --- | --- | --- | --- |
| Codellama-7B | 32 | 4096 | 11008 | 73.38 |
| Codellama-34B | 48 | 8192 | 22016 | 27.96 |
| Codellama-70B | 80 | 8192 | 28672 | 15.33 |
| Deepseek-1.3B | 24 | 2048 | 5504 | 102.36 |
| Deepseek-6.7B | 32 | 4096 | 11008 | 73.17 |
| Deepseek-33B | 62 | 7168 | 19200 | 23.64 |
| Llama-2-7B | 32 | 4096 | 11008 | 71.10 |
| Llama-2-70B | 80 | 8192 | 28672 | 15.30 |

### C.2 Evaluation Details

All of our experiments including latency measurement, ablation studies, and case studies are conducted on NVIDIA H800 GPUs. For models with size of 1.3B and 7B, we put them on a single H800, while 34B models are deployed on 2 H800, 70B models are deployed on 3 H800. For inference, we use batch size 1, which is commonly used in other speculative decoding works. For the compared baselines, including Lookahead decoding and Ouroboros, we reproduce the results of them on the code generation tasks with the default parameters as described in their paper or code. When evaluating these methods, the model configuration and GPU usage is the same as our PEARL. For HumanEval, we set the number of max generated tokens as 1024. For the other two tasks, we set the number of max generated tokens as 512.

As our PEARL is a parallel inference acceleration framework, we implement the parallel algorithm in accelerate, which can be further optimized with other parallel techniques. We leave this as a potential future work to acquire more acceleration.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: * The range of 1.50x to 4.43x represents a significant gap. Is there any analysis explaining the reasons for such large differences?
* Considering that pre-verifying a single token may not be the most accurate method for estimating difficulty, can the authors provide empirical evidence or analysis on how effectively the pre-verification of the first token compares to that of other tokens? For example, could there be potential pitfalls when using a very large gamma?
* Could the authors illustrate a few examples of profiling PEARL on real data, similar to Figure 3, but using actual data?
soundness: 3
strengths: * The motivation is clear, with strong supporting evidence, such as in Figure 2.
* Effective visualization of the PEARL algorithm, as shown in Figure 3.
* Reduction in manual parameter tuning for gamma, which previously required significant effort in SD (Section 4.1), even if the estimation remains somewhat approximate.
* Extensive evaluation across various tasks, including code generation, reasoning, and multi-round dialogue.
summary: This paper aims to accelerate LLM decoding by building on top of the popular Speculative Decoding (SD) algorithm. It addresses a key bottleneck in SD, the mutual waiting problem: the draft model and target model often get stuck waiting for each other because of sequential execution of the two logic with fixed draft lengths.

Unlike traditional SD, the proposed algorithm PEARL (Parallel spEculative decoding with Adaptive dRaft Length) generates variable draft lengths and supports asynchronous execution through two new operations: pre-verify and post-verify. The authors evaluated PEARL across various tasks (e.g., HumanEval, GSM8k), observing significant speedups in performance.
weaknesses: * The window size for each chunk (gamma) appears to remain fixed, which means the draft length will still be determined by the multiplication of gamma. While this may be unavoidable in the current algorithm, the abstract and introduction suggest that the authors intend to eliminate the need for gamma entirely.
* Pre-verify with only a single token might not be the most reliable method. See below for a question.
* While Section 5 presents a study on various datasets, the paper does not include a detailed analysis, such as step-by-step profiling or the failure rate in pre-verification.

---

confidence: 5
contribution: 4
initial_rating: 6
presentation: 3
questions: I find the following concerns and would like further clarification from the authors. 

The core idea behind SPD is to utilize hardware computation redundancy; therefore, running forward passes on drafter and target models simultaneously has to bring additional latencies for both the drafting and verification stages. I am glad to see the paper presents theoretical and empirical analysis, but none of them discussed this. Profiling the latency overhead brought by overlapping two stages could strengthen this paper. (I noticed Appendix E, an engineering technique to get around the resource competition issues, but still, some analysis is expected; let’s say we don’t have a multi-GPU environment to implement the PP solution.
soundness: 4
strengths: 1. The idea is novel to some extent: while the community has noticed that the drafting stage is the bottleneck of the current SPD system and has proposed works to either dynamically adjust the draft length or decode draft tokens in parallel, attempts to pre-verify and post-verity are innovative to lower the proportion of drafting latency in the SPD process.
2. The illustrations are self-explanatory in Figure 3. 
3. PERAL eliminates the need to tune the drafting window size according to Section 4.1, a desirable property for other SPD frameworks.
summary: This paper presents an interesting speculative decoding (SPD) paradigm, PEARL, that attempts to overlap the drafting and verification stages in the standard SPD framework, thereby mitigating the so-called mutual waiting issues. As a training-free SPD method, PERAL achieves a state-of-the-art acceleration ratio with different pairs of LLMs on different domains by switching between pre-verify and post-verify stages to adjust the draft length dynamically.
weaknesses: 1. Missing baselines: while comparison with SPD methods that require training (Medusa, EAGLE, etc.) is not expected, there is still a line of works that focus on training-free SPD, such as Self-Speculative [1], Parallel Decoding [2] and REST [3]. Adding these should be able to strengthen this submission, but please do not focus on this during the discussion stage.

Other than these, I don’t find obvious weaknesses in this submission. Please refer to the question section regarding my main concern.

[1]: Jun Zhang, Jue Wang, Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mehrotra. Draft & verify: Lossless large language model acceleration via self-speculative decoding.
[2]: Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorca, Michele Mancusi, Riccardo Marin, and Emanuele Rodolà. Accelerating transformer inference for translation via parallel decoding.
[3]: Zhenyu He, Zexuan Zhong, Tianle Cai, Jason D. Lee, and Di He. REST: retrieval-based speculative decoding.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: - Is additional communication overhead costs incurred when running drafting and verification on separate accelerators? (e.g. logits transport from 2 devices for rejection sampling/verification)
- There are 5 baselines listed but Table 2 and Table 3 only report Auto-regressive and SPEED?
- What is the assisted generation baseline exactly? Does it adjust draft length depending on the number of tokens accepted in the previous iteration?
- What value of gamma was used for the baselines on each task? Was it fixed according to the optimal gamma values determined for PEARL?
- Why do Table 5 and Table 6 differ for HumanEval with gamma=5 for Llama2 7B&70B (40.72 in Table 5 and 30.34 in Table 6)?
- Is there a cap on draft length given the fixed optimal verification window size? Something like 2x? Large gamma values aren’t only detrimental to drafting phase but also incur additional computational cost in verification (verifying 4 tokens vs. 32 can be a significant difference) even for vanilla SD
- Table 9 should clarify that it’s not inference speed time but is the number of model runs? Perhaps good to report the ratio on the side (PEARL has ?x more model runs than SD)
- Line 034: remove “the” in “the natural language”
- Line 046-047: rewrite to “draft tokens that the original large model (referred as the target model) then verifies in parallel…”
- Line 161: “generating” not “generation”
- Line 199: “that stucks the target model” ? Do you mean “blocks”?
- Line 240 remove “have”
- Line 331 “being” not “been”
- Line 352: speed up ratio relative to baseline auto-regressive?
- Line 410: Pearl without post-verify as Pearl w/o “pre-verify”
- Line 412: “exhibits a more pronounced”
- Line 691: “reject some” not “someone”
soundness: 2
strengths: - Authors clearly present their ideas and propose their PEARL framework with solid working examples and motivations. In particular, the analysis into the mutually blocked asynchronous execution of drafting and verification as well as optimal draft length per decode step were helpful in understanding the potential headroom for a parallelized framework of SD.
- Experiments with PEARL yield a solid speed up of 1.5x over vanilla speculative decoding on common text generation tasks as well as in comparison to other baselines for the HumanEval code generation task
- The paper examined each of the component strategies of PEARL, pre-verify, post-verify, and adaptive length, independently via ablation studies and analysis to isolate and highlight the relative impacts and relationships between each strategy
- Authors provide code implementation for reproducibility
summary: The paper describes and addresses the problem of "mutual waiting" in Speculative decoding (SD) for LLM inference acceleration, where typically, the target model and draft model are mutually blocked by each other since verification can only occur after drafting is completed and vice-versa (draft-then-verify). The authors propose a novel framework to address this mutual waiting problem called "Parallel Speculative Decoding with Adaptive Draft Length" (PEARL) that coordinates the drafting and verification steps partially in parallel by using “pre-verify” and “post-verify” strategies for verifying the first draft token in advance during drafting and generating more drafts during verification, respectively. This can be thought of as a shift from the “draft-then-verify” sequential paradigm into a more parallelized “draft-and-verify” paradigm. In addition to the “pre-verify” and “post-verify” strategies, the authors explore the use of an adaptive draft length to further reduce the mutual-waiting scenario where suboptimal draft lengths are used, whether too short or too long. Using these proposed strategies, the authors are able to showcase relative speedups on top of vanilla SD on a variety of text generation tasks.
weaknesses: - The main paper assumes execution scenarios where there are enough resources to run drafting and verification in parallel (e.g. multiple GPUs). However, in many instances, drafting and verification happen in co-located settings (e.g. single GPU) where it is more resource constrained. While the authors do make brief mentions in the main paper about these resource constrained scenarios, their discussion and strategies to address this are limited to a relatively short section in the appendix with not much details on their experimental results. It would be much more fitting to have this section filled with more detail and part of the main paper. For example, the strategy mentioned in the appendix involved copying the drafter model across multiple chips which incurs greater memory cost as well as potential communication cost in having to transport and sync intermediate attention KV caches.
- Additionally, given the fact that drafting and verification is assumed to occur on separate devices in parallel, it would be good to see a mention into the communication overhead of data transfer (i.e. logits for adjusted sampling during verification rejection) as well as a breakdown into the additional computational and power consumption in practice from added drafting and verification calls that PEARL conducts in comparison to SD
- While a variety of tasks (HumanEval, GSM8K & MGM, MT-bench) and baselines (SD, Ouroboros, Lookahead Decoding, Distillspec, Assisted Generation) were mentioned in the experiments, the variety of baselines were only used for the HumanEval code generation task while the remaining GSM8K & MGM and MT-bench tasks only used auto-regressive (AR) and SD baselines.

---

confidence: 4
contribution: 3
initial_rating: 3
presentation: 3
questions: My concerns are raised above.
soundness: 3
strengths: The paper is clearly written and provides several contributions: 

1. PEARL allows the drafting and verification phases to occur simultaneously

2. Instead of using a fixed draft length, PEARL adapts the number of draft tokens generated based on the context and complexity of the task. This flexibility ensures that the draft model generates an appropriate number of tokens, reducing unnecessary computations and improving the acceptance rate of tokens by the target model. This adaptability helps to optimize the inference process for different scenarios.

3. PEARL theoretically demonstrates that it can achieve a higher mean number of accepted tokens compared to existing draft-then-verify methods. This means that more of the generated tokens are useful, leading to better performance overall
summary: The authors aim to address two challenges: 1. The mutual waiting problem, which arises when the target model becomes idle while waiting for the draft model to generate tokens, and vice versa. The asynchronous execution of the draft and verification phases leads to inefficiencies. 2. Fixed draft model length.

The authors introduced two strategies to solve this issue: 1. Pre-verification: This strategy involves using the target model to verify the first draft token during the drafting phase. By doing this, PEARL can determine whether the drafted token will likely be accepted or rejected.
If the first draft token is verified and accepted, the draft model can generate additional tokens more confidently. Conversely, if the first token is likely rejected, the draft model can generate fewer tokens, thus saving computational resources and time. 

2. Post-verification: In this phase, the draft model generates additional draft tokens while the target model verifies the previously drafted tokens. This allows for a more continuous flow of token generation and verification. By enabling the draft model to produce more tokens during the verification phase, PEARL capitalizes on situations where the target model is actively processing the earlier drafts. This strategy ensures that the draft model is not idle while waiting for the target model to complete its verification, thus maximizing throughput.
weaknesses: The author claims that they can continue doing draft generation while doing the verification. This raises many questions:

1. The latency of verifying a 70B model is about generating 2.5 tokens on the 8B model. Based on the speedup that the authors provided, this parallel approach would not work beyond a lookahead length of 3, which is shown to be suboptimal empirically. Therefore it is not clear how much this post-verify step improves the performance. 

2. Some parameters are underspecified in the tokens accepted per second table (Table). It is not clear under what lookahead length are the baseline numbers achieved, or if they are optimal.

3. The authors picked pipeline parallelism for their implementation. However, while this is a convenient setup for solving the "resource contention" challenge, this is an unreasonable setting and introduces much higher latency in the first place. In deploying a 70B target model with a 7B draft model, using tensor parallelism (TP) can reduce the latency of the target model by leveraging more parallelism in each layer. Therefore, this casts doubt on all the speedup that the authors reported as this causes both the baseline and their reported results to be slower than in a TP setup. Also, with TP, the proposed solution to resource contention in Appendix E would not apply and it is not clear whether the authors can show a similar speedup with their algorithm.

4. Furthermore, using PP instead of TP causes a higher activation memory footprint, reducing the effective batchsize the model can accommodate during decoding, effectively reducing the overall throughput.

Meta-review: This paper makes an observation that the drafting phase and the verification phase of speculative decoding can further be parallelized as the current implementations lead to verification stage being on hold when drafting is being done and vice versa. The proposal in the paper makes sense and the empirical evidence in the case with no resource constraints demonstrates the effectiveness of the method. There were several questions by the reviewers that were successfully addressed. I also think the remaining concerns of Reviewer dgRU about tensor parallelism is not a blocker for publication and can be acknowledged in the paper. After reading the paper, the AC finds that the theoretical claims of the paper are questionable, and even likely wrong. 
* Theorem 1 claims that the optimal $\gamma = c$; here \gamma must be an integer whereas c is an arbitrary positive real number so the claim cannot hold true in the general form claimed here. 
* With reading the proof, Theorem 2 seems to assume that $c -> \infty$ in which case the same result holds for standard SD as well.
* The conclusion after Theorem 2 is wrong because the discussion is missing the free token accepted for standard SD. In fact, the two quantities should agree when $\gamma \to \infty$.

Despite these issues, the AC tends to recommend the paper for acceptance and believes that the empirical results are sufficient for acceptance. However, **the paper is accepted under the condition that Theorem 1 and Theorem 2 are removed; with their proofs removed from appendix as well** and the approximate derivations are used to shed insight and intuition on where the gains come from. Congratulations to the authors!

Decision: Accept (Poster)