PEARL: Parallel Speculative Decoding with Adaptive Draft Length

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score (3: reject). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

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.

Thank you for bringing up the insightful comment. We answer it in three folds:

1. Clarification of Definition of Draft Length and Window Size: We apologize for any confusion regarding the definition of the draft length. As in Line 48 of the original manuscript, the draft length refers to the number of tokens generated by the draft model in a continuous execution. This definition indicates that theoretically there is no upper limit to the draft length, as the draft model may generate draft tokens as much as possible. However, the mentioned lookahead length, i.e., window size in Line 47, is fixed at any step. In our PEARL, we theoretically show in Section 5.4.1 that the optimal window size should be $c$, i.e., the inference speed ratio between the draft model and the target model, which aligns well with the empirical results in Table 5 of the original manuscript.
2. Motivation of the Post-verify Strategy: the key idea of post-verify is to allow the draft model to generate more than $\gamma$ tokens without waiting for the target model's verification. For example, given that "the latency of verifying a 70B model is about generating 2.5 tokens on the 8B model and we set the window size as 3" and if the optimal draft length is 12, post-verify fully exploits the drafting ability of the small model to continually generate 4 windows of draft tokens without been interrupted by the target model verification. In this case, the de facto draft length is adaptively adjusted to 12.
3. Effectiveness of the Post-verify Strategy: As illustrated in Figure 2 (b) in the original manuscript, the optimal draft length dramatically changes in different steps. Using a fixed window size to generate draft tokens cannot fit this change, while our post-verify allows the draft model to generate more tokens when the optimal draft length is larger than $\gamma$. Besides, we also performed an ablation study, as shown in Table 4 (for your convenience, we quote Table 4 as Table R1 here). The results also demonstrate that the absence of the post-verify strategy leads to a substantial reduction in the speedup, which further validates the effectiveness of our post-verify strategy.

Table R1. Ablation study of post-verify strategy on HumanEval and GSM8K datasets. PEARL w/o post-verify denotes PEARL without post-verify strategy.

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.

We appreciate the reviewer's feedback regarding parameter specification in Table 7 (for your convenience, we quote Table 7 as Table R2 here). In the mean accepted tokens experiments, we select the optimal $\gamma$ for each model pair. Below, we provide a detailed comparison across different $\gamma$ values in Table R3. Our reported baseline results align closely with the most optimal parameters.

Table R2. Comparison of mean average accepted tokens of vanilla SD methods and PEARL. We run experiments to search the optimal $\gamma$ for SD and report their best results.

Table R3. Optimal $\gamma$ values of SD for each model pair. (Unit: tokens / second)

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.

Thank you for your insightful feedback. We acknowledge the benefits of TP in reducing inference latency. We clarify how our PEARL adapts to TP setting and emphasize its contributions as follows:

1. Our primary application scenarios are those with sufficient resources, including adequate GPU capacity, to deploy both the large and small models on separate devices. In this situation, enabling tensor parallelism for both the draft model and the target model is normal and brings no significant overhead. For example, deploy the draft model with 1 A100 GPU with TP=1 and the target model with 7 A100 GPUs with TP=7. We emphasize this scenario is very common and promising in the industry. For example, Mooncake uses prefill-decode separation techniques to further improve the serving efficiency [1].
2. While our proposed solution in Appendix E can help PEARL to apply in PP settings, it remains possible to integrate PEARL with both PP and TP. Take an instance of our toy example in Lines 849 and 857, in the first 12 micro-steps, theoretically, we can enable tensor parallelism for the target model with TP=3 on GPUs 0, 1, and 2; while in the last 8 micro-steps on GPUs 1, 2, 3. However, we acknowledge that the implementation of tensor parallelism in the speculative setting is challenging, even if the vllm team cannot support vanilla speculative decoding with TP [2]. Moreover, many SD methods also do not support TP implementation as well [3]. We believe that constructing a general TP framework for SD methods is essential, and we think this framework deserves its own publication.
3. We emphasize that the main contribution of our work is the discovery of the mutual waiting problem. This problem is very common, and will even be exacerbated in TP settings. An observation listed in Table R4 shows that the running speed ratio $c$ between the draft model and the target model is even smaller in TP settings, which leads to a more severe mutual waiting problem. We believe this is a fundamental obstacle for existing SD frameworks to deploy in real-world applications, and our PEARL stands as a pioneer in work to eliminate the mutual waiting problem.

Table R4. Inference speed ratio in TensorRT LLM (with TP) and Huggingface (without TP).

[1] https://github.com/kvcache-ai/Mooncake

[2] https://docs.vllm.ai/en/v0.5.5/models/spec_decode.html

[3] https://github.com/dilab-zju/self-speculative-decoding/issues/21

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.

Thanks for your constructive comments.

1. Clarification of TP and PP. TP and PP are both effective ways for inference acceleration and can be combined for better efficiency. Several LLM inference frameworks, such as TRTLLM [5] and VLLM [6], demonstrate successful implementations where TP and PP are used in tandem. In our implementation, we choose PP as basic parallelism due to its wider applications and simpler implementations.
2. The potential of integrating PEARL into the existing TP framework. We also provide an idea of TP implementation as an alternative parallelism strategy in response to weakness 3. To clarify, the key idea of PEARL is to utilize the underutilized GPU computations due to the mutual waiting problem, and this does not conflict with tensor parallelism. Therefore, our PEARL can be integrated with the existing TP framework and we leave it as a future work.
3. The batchsize issue. It is important to note that the speculative decoding (SD) framework performs suboptimally in high-batch settings, as outlined in recent findings from the VLLM blog [4]. SD leverages redundant compute capacity, but in high batch-size regimes, the amount of redundancy diminishes, leading to an overhead from token rejection that outweighs the benefits of SD. This issue is exacerbated as the number of rejected tokens increases, resulting in a significant slowdown. In contrast, PEARL, with its adaptive draft length mechanism, reduces this overhead by adaptively adjusting the draft length, allowing it to better accommodate larger batch sizes and improving efficiency compared to SD.

[4] https://blog.vllm.ai/2024/10/17/spec-decode.html

[5] https://github.com/NVIDIA/TensorRT-LLM

[6] https://github.com/vllm-project/vllm

We humbly hope our response has addressed your concerns. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.

I still have some doubts about the authors' responses.

The author claims, "Our primary application scenarios are those with sufficient resources". However, this does not address the issue at hand. Given any amount of hardware resources, if the intermediate memory cost is not carefully studied or addressed, a workload that used to fit on n GPUs (say 2 or 4) would now require 2n GPUs (say 4 or 8), which would cause a direct reduction in overall throughput. That was the concern raised in the original rebuttal, which is that the authors picked a setting known to be resource-inefficient, and the technique that the authors proposed only works in that specific setting.

Then the authors claim that they chose PP due to simplicity in implementation. This is a very bizarre claim given that PP is known to be difficult to manage and implement due to the complexity associated with layer sharding (Compared to TP/DDP/FSDP, which one can implement with a one-line or few-line wrappers, using PP would require manual sharding of models and carefully written code for placement and deployment. For all the benefits that PP can have, simplicity in implementation is not known to be one of them). However, I will not dive into this further since this is not the topic of the paper.

In addition, the example that the authors gave on TP also would not work in practice since most of the existing frameworks would require layer width to be divisible by TP size (which would not work with TP=3/7 as shown in the author's example). This further validates my concern that the proposed approach only works in the PP setting, which is sub-optimal for deploying SD.

Therefore, my concern that the proposed method only works in a setting that is known to be resource-inefficient still stands and I am inclined to keep my rating.

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score (5: marginally below the acceptance threshold). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

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

We appreciate the reviewer's insightful comments. In response, we will expand the discussion of resource-constrained scenarios in the main body of the paper, specifically in Section 4.5 (Case Studies). We also revise the PDF accordingly. For other weakness, we answer as follows:

1. Clarification of application scenarios. The core idea of SD series methods is to leverage redundant computational resources for acceleration. Our PEARL is motivated by the mutual waiting problem, which indicates that SD methods cannot fully utilize the computational resources. Based on this idea, the main application scenarios of PEARL focus on multi-GPU settings, where adequate computational resources can be exploited. We also would like to emphasize that multi-GPU applications, such as high-throughput inference scenarios and edge computing, are highly relevant in practical deployments, where sufficient resources can be allocated for parallel drafting and verification. These settings are important for scaling the approach to large, complex models.
2. PEARL in resource-constrained scenarios. While our experiments are conducted primarily on multi-GPU settings, we acknowledge that resource-constrained scenarios are very common, and we provide an adaptive method to deploy PEARL in such scenarios. Regarding the details mentioned in the appendix, we provide further clarification on the memory and communication costs.
   1. (Additional Memory Cost) In the strategy provided in the appendix, PEARL requires loading only 1 additional copy of the draft model. Given that the scale of the draft model is typically smaller than 7B, this additional memory cost is lower than 14GB GPU memory (e.g., Llama 2 7B with bfloat 16). It can be further reduced to < 1B with EAGLE draft heads.
   2. (Additional KV cache Sync Cost) Our strategy does incur additional KV cache sync costs to transport the KV cache. However, as the draft model is relatively small, the KV cache itself does not incur significant memory overhead. For example, with Llama 3.1 8B, batch size=1 and input length=1024, the size of the kv cache is $2\times 2 \times 32\times 1\times 8\times 1024\times 128 \approx 0.13$ GB. With NVlink, the theoretical time cost for transporting the KV cache is $0.13/300\approx 0.43$ ms, which is significantly lower than the computational time cost. Other techniques such as KV cache compression/quantization can further reduce communication costs. Besides, this time cost can be parallelized with the target model verification process. We provide empirical results of the KV cache transport time cost in Table R1. Note that in our implementation, the kv cache is sequentially transported, leading to a significantly larger time cost. However, this time cost can still be ignored (<5% of total time cost). These results demonstrate the effectiveness of our approach in mitigating resource contention and supporting efficient multi-task execution in resource-constrained environments.

Table R1. The empirical time cost of transporting KV cache with different input length. The experiments are conducted with Llama 3.1 8B on HumanEval.

Table R5. Comparisons of different SD methods on MGSM with Llama 2 7&70b. The highest speedups are bolden.

4. Other questions

Phew! Thanks for your time and detailed feedback! Thanks for your clear effort to think critically about how to improve our paper! We answer them respectively.

Q1: 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)

As shown in Table R2, the additional communication overhead incurred by running drafting and verification on separate accelerators is negligible.

Q2: There are 5 baselines listed but Table 2 and Table 3 only report Auto-regressive and SPEED?

We conduct additional experiments accordingly in Tables R4 and R5.

Q3: What is the assisted generation baseline exactly? Does it adjust draft length depending on the number of tokens accepted in the previous iteration?

Assisted generation [3] is an improved speculative decoding algorithm. It initially sets the window size as 5, and increases it by 2 if all draft tokens are accepted, or decreases it by 1 otherwise. In our experiments, this strategy cannot handle the dynamic draft length well, sometimes brings additional overhead, and incurs more severe mutual waiting problems.

Q4: What value of gamma was used for the baselines on each task? Was it fixed according to the optimal gamma values determined for PEARL?

For vanilla speculative decoding, we search the optimal $\gamma$ and report its best performance. For other baselines, we either use the reported number in their original manuscript or using their official codes with default parameters for reproduction.

Q5: 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)?

We apologize for any confusion that may have arisen from the discrepancy between Tables 5 and 6. To clarify, the results presented in Table 5 correspond to the CodeLlama model, whereas the results in Table 6 correspond to the Llama2 model.

Q6: 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

The draft length corresponds to the maximal number of draft tokens that can be accepted at a specific speculative step. Theoretically, there is no fixed upper bound of the draft length, as the draft model can generate draft tokens as many as possible. In PEARL, the verification of a large draft length is split into many windows, and each window contains a fixed number of draft tokens. This chunked verification is parallelized with the drafting process, hence it does not incur additional verification time cost.

Q7: 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)

Thanks for your suggestions. We have added the statistics accordingly.

Other typos in the manuscript.

Thank you for pointing out these typos, we will update them together into the revised PDF.

We humbly hope our response has addressed your concerns. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.

[3] https://huggingface.co/blog/assisted-generation

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

Thank you for your insightful feedback. We measure the time cost of each component in one PEARL step with different sizes of model pairs in Table R2. For a more distinct comparison, we also provide the measurement of SD in Table R3. As shown in these 2 tables, the communication overhead within PEARL is negligible.

Table R2. The time cost of each component in one PEARL step. The experiments are conducted on HumanEval.

Table R3. The time cost of each component in one SD step. The experiments are conducted on HumanEval.

For the additional computations and power consumptions within PEARL, we first measure the computations of a single model forward with thop [1]. For Llama 2 7b, the computation is 6.607 GFLOPS per token, while the computation is 68.713 GFLOPS per token for Llama 2 70b. Combining the results in Table 9, PEARL will take more computations of about 41.75% than SD, as well as the power consumption. However, our experiments demonstrate that PEARL significantly outperforms SD with up to 1.5$\times$ inference acceleration, which takes the duty of these additional computations and power consumptions.

[1] https://github.com/ultralytics/thop

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

We update the experiments to include results for the additional baselines (Lookahead, Ouroboros, Assisted Generation with LLaMA 2 7&70B) on the MT-Bench and MGSM tasks in Tables R4 and R5. These results will be added to Tables 2 and 3. Regarding Lookahead and Ouroboros, it is important to note that these methods currently do not support the LLama 3.1 models, as their official codes only support transformers<=4.36.2 [2], but the Llama 3.1 models require transformers>=4.43. For DistillSpec, the source code has not been made publicly available, and therefore, we are unable to include it as a baseline in our experiments in a short period. We will actively try to communicate with the authors of DistillSpec and reproduce its performance in the future for a more detailed comparison.

[2] https://github.com/hao-ai-lab/LookaheadDecoding/tree/main

Table R4. Comparisons of different SD methods on MT-bench with Llama 2 7&70b. The highest speedups are bolden.

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

Thanks for your insightful comments. We answer the question in three-fold:

1. Clarification of the application scenarios. As illustrated, the key idea of speculative decoding is to exploit the computation redundancy for acceleration. Based on this idea, we observe the mutual waiting problem, which hinders speculative decoding to fully utilize the redundant computational resources. Therefore, the main application scenarios of PEARL focus on the scenarios with adequate computational resources, where speculative decoding cannot sufficiently use these resources.

2. PEARL in resource-adequate scenarios. In such scenarios, the draft model and the target model can be deployed separately, and simultaneously running the draft model and the target model would not bring additional latencies in both drafting and verification stages. We have conducted experiments to verify this conclusion, by running the draft model and the target model in parallel (PEARL) and sequentially (SD) in Table R2 and R3, where we set all the hyper parameters the same for fair comparison. From the results, we can see that running the draft model and the target model in parallel only incurs negligible additional latencies.

3. PEARL in resource-constrained scenarios. While our experiments are conducted mainly on resource-adequate scenarios, we acknowledge that the resource constrained scenarios are very common, and we make our effort to provide a strategy to exploit the underutilized resources in PP settings. We also provide experiments to demonstrate the effectiveness of PEARL in multi-GPU resource constrained scenarios using proposed strategy in PP implementation in Table R4. However, when the resources are too limited to implement PP, our PEARL will degenerate to vanilla SD. The explanations are as follows:

   1. pre-verify in single-GPU: the pre-verify requires the target model to take an additional verification simultaneously during the drafting stage. However, the GPU resources are occupied by the draft model, and the target model remains idle until the draft model finishes its drafting process. As the drafting process has finished, the target model will directly verify these draft tokens. In this situation, the pre-verify strategy degenerates to the drafting phase in vanilla SD.
   2. post-verify in single-GPU: the post-verify requires the draft model to generate additional draft tokens simultaneously during the verification stage. However, the target model occupies all GPU resources in single-GPU setting, and no GPU resources can be utilized for drafting. In this situation, the post-verify strategy degenerates to the verification phase in vanilla SD.

   To summarize, when there is no underutilized computational resources in single-GPU settings, PEARL will degenerate to vanilla SD, but is still faster than auto-regressive decoding.

   However, we notice that in resource-constrained setting, offloading the draft model to CPU is also possible [3]. Therefore, offloading the draft model to CPU to run drafting and verification in parallel is an alternative and promising solution in such scenario. Other CPU-concentrated drafting methods (e.g. retrieval-based drafting) can also consider adopting PEARL framework for further acceleration. We believe that PEARL can help improve the inference efficiency in most scenarios.

We humbly hope our response has addressed your concerns. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.

[3] Miao, Xupeng, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong et al. "Specinfer: Accelerating large language model serving with tree-based speculative inference and verification." In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, pp. 932-949. 2024.

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

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.

We appreciate the reviewer's insightful comments. We update the experiments to include results for additional training-free speculative decoding baselines (self-speculative, parallel decoding and REST) on the GSM8K benchmark in Table R1. Note that the results of self-speculative decoding and parallel decoding are copied from a recent work [1]. The result of REST is reproduced with their official code [2] and default parameter settings. PEARL outperforms these training-free methods by a large margin. All of these experiments validate the effectiveness of PEARL.

Table R1. Comparison between some training-free speculative decoding baselines and our PEARL. We report the inference speedup as the evaluation metric. The experiments are conducted on GSM8K with Llama 2 7&70B.

[1] Xia, Heming, Yongqi Li, Jun Zhang, Cunxiao Du, and Wenjie Li. "SWIFT: On-the-Fly Self-Speculative Decoding for LLM Inference Acceleration." arXiv preprint arXiv:2410.06916 (2024).

[2] https://github.com/FasterDecoding/REST

Table R2. The time cost of each component in one PEARL step. The experiments are conducted on HumanEval.

Table R3. The time cost of each component in one SD step. The experiments are conducted on HumanEval.

Table R4. Performance comparison of Llama 2 and Llama 3.1 models for PEARL on 4 benchmarks with and without RC (resource competitions). Using proposed strategy in the appendix, PEARL can work well in RC settings with only a slight performance decrease ($\approx 5\%$).

Table R5. Performance comparison of Llama 2 and Llama 3.1 models for PEARL on MGSM with and without RC. Using proposed strategy in the appendix, PEARL can work well in RC settings with only a slight performance decrease ($< 10\%$).

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

Thanks for your constructive comments, and we will add a detailed analysis including step-by-step profiling and the strategy changes analysis in the revised manuscript.

4. The range of 1.50x to 4.43x represents a significant gap. Is there any analysis explaining the reasons for such large differences?

We apologize for any confusion in the abstract. $1.50\times$ is the speedup ratio of PEARL over vanilla speculative decoding, and $4.43\times$ is the speedup ratio of PEARL over auto-regressive decoding.

5. Could the authors illustrate a few examples of profiling PEARL on real data, similar to Figure 3, but using actual data?

We provide a simple step-by-step profiling of PEARL with a real data prompt "x+y = 4z, x*y = 4z^2, express x-y in z" in Table R2. To understand the effectiveness of PEARL, we give some explanations about the whole process.

1. At step 0, the prompt "x+y = 4z, x*y = 4z^2, express x-y in z" is input to the draft model and the target model simultaneously with strategy pre-verify. Within the left of this explanation, we omit this original prompt for simplicity. The draft model outputs [Great, I'm], while the target model outputs [I]. Then, we will use [I] to verify the first token [Great] in the draft tokens. As it is not the same, we reject the draft tokens, save a verification stage of the other draft tokens for acceleration, and the output prefix is [I]. As there exists rejected token, the next strategy is still pre-verify.
2. At step 1, the prefix [I] is input, and the draft model outputs ['m glad you] and the target model outputs [']. This time, ['] is accepted by the target model, and the next strategy is tuned to post-verify.
3. At step 2, the prefix together with the other draft tokens [I'm glad you] is input. The draft model outputs [are interested in exploring] while the target model outputs [m], i.e., the first draft token [m] is accepted, but the second draft token [glad] is rejected. The target model additionally appends [happy] to the prefix. As there exists rejected token, the next strategy is pre-verify.
4. At step 3, the prefix [I'm happy] is input, and the draft model outputs [to help you with this] and the target model outputs [to]. This time, [to] is accepted by the target model, and the next strategy is tuned to post-verify.
5. At step 4, the prefix together with the other draft tokens [I'm happy to help you with this] is input. The draft model outputs [equation! However, I] while the target model outputs [help you with], i.e., the first three draft token [help you with] is accepted, but the fourth draft token [you] is rejected. The target model additionally appends [your] to the prefix. As there exists rejected token, the next strategy is pre-verify.
6. At step 5, the prefix [I'm happy to help you with your] is input, and the draft model outputs [question! However, I] and the target model outputs [question]. This time, [question] is accepted by the target model, and the next strategy is tuned to post-verify.
7. At step 6, the prefix together with the other draft tokens [I'm happy to help you with your question! However, I] is input. The draft model outputs [notice that the equation you] while the target model outputs [! However, I notice]. All the draft tokens are accepted, and the next strategy is still post-verify. Therefore, we save $\gamma$ times of draft model forward for acceleration.
8. At step 6, the prefix together with the other draft tokens [I'm happy to help you with your question! However, I notice that the equation you] is input. The draft model outputs [provided is not correct] while the target model outputs [that the], i.e., the first two draft token [that the] is accepted, but the third draft token [equation] is rejected. The target model additionally appends [equations] to the prefix. As there exists rejected token, the next strategy is pre-verify.

We hope this step-by-step profiling example can help readers to understand our PEARL better.

We humbly hope our response has addressed your concerns. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.

Table R2. Simple step-by-step profiling of PEARL with prompt "x+y = 4z, x*y = 4z^2, express x-y in z". We only report the first 7 steps for simplicity. The prompt is selected from MT-bench, and we use Llama 2 7&70b as our base model pair.

We thank the reviewer for the insightful and valuable comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

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

Thanks for your insightful comments. We apologize for any misunderstanding regarding to the draft length.

1. Clarification on window size $\gamma$ and draft length. In our paper, the window size $\gamma$ refers to a fixed constant through every step, while the draft length refers to a dynamic number of tokens generated by the draft model in a continuous execution. Note that this draft length is theoretically unlimited, as the draft model can generate draft tokens as many as possible.
2. PEARL adjust the draft length adaptively. We acknowledge that the draft length is determined by the multiplication of $\gamma$. Suppose the optimal draft length is $\eta$, our PEARL will adjust the actual draft length to the nearest multiple of $\gamma$, i.e., $k\gamma$ such that $k\gamma \geq \eta$ and $(k-1)\gamma < \eta$. In this way, we call this mechanism as "adaptive draft length".
3. PEARL eliminates the burden of tuning $\gamma$. We apologize for any confusion regarding to this in our manuscript. In the analysis section, we claim that our PEARL eliminates the burden of tuning $\gamma$, i.e., the $\gamma$ can be theoretically derived at $c$, which is the speed ratio between the draft model and the target model. With this theorem, we can eliminate the burden of tuning $\gamma$ on different benchmarks or different models, which is a huge amount of effort to achieve best speedup. However, the window size $\gamma$ here is still important, and we do not claim to eliminate the need of this parameter entirely.

2. Pre-verify with only a single token might not be the most reliable method. See below for a question.

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

We appreciate the reviewer's insightful comments. In response, we discuss the pre-verify strategy as follows:

1. In our PEARL, the key idea of the pre-verify strategy aims at providing an additional first-token verification of the current draft tokens, and if the first token is accepted, PEARL will switch to the post-verify strategy and allows the draft model to generate more draft tokens. However, as this pre-verify process is running in parallel to the drafting process, the target model can only verify the first draft token in advance, as it only depends on the logits of the last token in the prefix. If no additional guess of the draft tokens is given, only the verification of the first draft token is possible.
2. We also appreciate the reviewer's perspective of understanding pre-verify with "estimating difficulty", which inspires a future work to enhance the performance of pre-verify. That is to say, we can employ a multi-hierarchy speculative strategy, using a smaller model to guess the tokens of the draft model, and use the target model to pre-verify multiple draft tokens if the guesses match [1]. We also conduct some experiments in Table R1 to measure the failure rate of the pre-verify strategy, i.e., the situation that the first draft token is accepted, but some of the rest draft tokens are rejected. In Table R1, this situation corresponds to the situation that last step is post-verify while next step is pre-verify. We can see that this situation is very common in practice, and improve the performance of pre-verify is a promising future work.

[1] Sun, Hanshi, et al. "Triforce: Lossless acceleration of long sequence generation with hierarchical speculative decoding." arXiv preprint arXiv:2404.11912 (2024).

Table R1. Measurement of the PEARL strategy changes on MT-bench with Llama 2 7&70b. We use an output length of 256 for experiment.