We sincerely appreciate the reviewer’s insightful suggestions and we hope our responses can address your concerns.

Results with Llama-3 Models

To address your concern about the results with newer models, we have added a more comprehensive evaluation using Llama-3 series models, with 8B (8B-Instruct) as the target model and 1B (1B-Instruct) as the draft model. These results are detailed in the "Common Reply on Perplexity and Downstream Performance" and demonstrate the robustness and generality of our proposed method across state-of-the-art models.

Comparisons with Recently Published Methods

We have also incorporated additional baselines for comparison. Specifically, we include typical decoding from MEDUSA-2 as an additional baseline. Regarding "Better & Faster Large Language Models via Multi-token Prediction," this paper proposes new model architecture to generate draft tokens while using existing speculative decoding algorithms for inference. So it is orthogonal to our work, and our method is applicable to its new model architecture. Notably, many recently published papers in this area focus on improving draft models rather than introducing new decoding algorithms. For example, EAGLE-2 [1] proposes a new model architecture to generate draft tokens, but still use SpecInfer as the decoding method. These works are orthogonal to our paper. To our knowledge, the baselines used in our paper and rebuttal are still state-of-the-art speculative decoding algorithms.

Experiments with MTJD

We also acknowledge the importance of providing analytical experiments to support our claims about multi-token joint decoding (MTJD). As suggested, we report the output quality of MTJD and multinomial sampling on benchmarks such as Spider, MTBench, and HumanEval (Pass@1) in the "Common Reply on Perplexity and Downstream Performance." These results further validate the effectiveness of our method in reducing perplexity and improving task performance.

We hope these additional experiments and clarifications address your concerns and demonstrate the robustness, effectiveness, and self-consistency of our work. Please feel free to refer to the common response for further details, and let us know if additional information is needed.

[1] Eagle-2: Faster inference of language models with dynamic draft trees

Correlation between Perplexity and Output Quality

We appreciate your concern regarding the relationship between lower perplexity and downstream performance. While we acknowledge that this correlation may vary across tasks, we provide strong evidence supporting it within the context of our work.

1. Empirical Evidence: As detailed in our "Common Reply on Perplexity and Downstream Performance," we compare multi-token joint decoding (MTJD, k=4) with single-token multinomial sampling across multiple datasets. MTJD consistently achieves significantly lower perplexity and better downstream performance. Furthermore, newly added Figure 4 in the Appendix C.4 illustrates a clear correlation between perplexity and downstream task performance across baselines, datasets, and models used in our experiments.
2. Established Decoding Principles: The connection between likelihood and quality is well-recognized in decoding strategies like beam search, which selects sequences with the highest likelihood (i.e., lowest perplexity). Previous works [4] confirm that beam search generally outperforms greedy decoding in terms of output quality, further validating the correlation.
3. Analysis of Figure 1: While perplexity values from different models (e.g., OPT and Llama-2) are not directly comparable due to varying likelihood functions, the trend of lower perplexity correlating with better performance holds true within each model family.

We acknowledge that in some cases, lower perplexity may not correspond to improved performance, often due to limitations in the target model itself. However, our theoretical insights, experimental results, and the broader literature collectively demonstrate that lower perplexity generally correlates with better output quality and downstream performance for our method.

Comprehensive Evaluation of Downstream Performance

We appreciate the suggestion to include additional downstream performance metrics. In response, we conducted a comprehensive evaluation using Llama-3 models (Llama-3-8B, Llama-3-1B, and their instruct variants) across Spider, HumanEval, and MT-Bench. These results, provided in the "Common Reply on Perplexity and Downstream Performance," demonstrate that MJAD improves downstream performance while achieving the fastest speed among all methods.

Advantage over Multi-Draft Speculative Sampling Methods

We appreciate the reviewer’s concern and provide clarification on why MTAD significantly outperforms multi-draft speculative decoding methods like Spectr and SpecInfer.

Superior Design of MTAD

In Spectr and SpecInfer, despite having multiple draft sequences, for each draft sequence, the verification terminates as soon as a token is rejected. In contrast, when a token is rejected, MTAD’s verification continues to seek if future tokens can pass the verification. So as shown in Table 5, it allows our method to get a higher acceptance length than the baselines. Additionally, multi-draft methods increase the number of draft sequences to enhance acceptance rates, but this incurs substantial computational and memory overhead for target model verification. The tree-attention mechanism only alleviates this issue, but the extra overhead is still unavoidable. On the other hand, MTAD only outputs one draft sequence, so there is no extra overhead in verification. Based on these two factors, it is not surprising MTAD is more efficient.

Why our experiment configuration is fair.

(1) Our baselines are SOTA. Although there are some recent papers about speculative decoding, most of them focus on how to obtain a better draft model and they simply adopt the existing decoding algorithms. For example, EAGLE-2 [2] and Gloeckle et al [3] propose new model architectures to generate draft tokens, but still use SpecInfer or other existing decoding methods. These works are orthogonal to our paper. To our knowledge, the baselines used in our paper and rebuttal are still state-of-the-art speculative decoding algorithms.

(2) The configuration is fair. In MTAD, the number of draft sequences is always 1, regardless of the number of beams, because beam decoding only returns the beam with the highest likelihood. So a higher beam number only increases the computation cost of the small model, but not the target model. Meanwhile, if we increase the number of draft sequences in Spectr and SpecInfer, there are more sequences to verify for the target model, which is much more expensive than increasing the beam number of the small model. The setting reported in Table 13 achieves best efficiency for Spectr and SpecInfer. We tried setting the number of sequences to match the number of beams as suggested by the reviewer, it causes out-of-memory errors.

Lack of Quality Guarantee

We agree that being “lossless” is an appealing feature of speculative decoding. However, while MTAD is "lossy," the loss in accuracy is measured against MTJD, a decoding paradigm that is both theoretically and empirically superior to multinomial sampling (see results in the "Common Reply on Perplexity and Downstream Performance").

1. Different Design Objectives: Unlike lossless methods that aim to replicate multinomial sampling, MTAD is designed to achieve higher output quality and efficiency by approximating MTJD.
2. Theoretical Bounds: We provide a theoretical bound on the approximation error between MTAD and MTJD, ensuring that MTAD closely adheres to the benefits of MTJD.
3. Empirical Performance: With MTAD's "starting point" already outperforming multinomial sampling, our results consistently demonstrate better output quality and faster speeds compared to lossless speculative decoding methods.

This distinction in design objectives positions MTAD as a fundamentally different approach, focused on achieving superior efficiency and effectiveness.

Comparison with Method [1]

We appreciate the reviewer for highlighting the relevance of method [1]. While it shares a similarity with MTAD in allowing verification to continue after token rejection, the objectives and methodologies differ significantly. Specifically, since [1] aims to have identical distribution as multinomial sampling, its verification scheme significantly differs from the original speculative decoding and our method.

Since [1] is a preprint paper and its code is not open-sourced, we use the reported results in the paper for comparison. According to [1], it consistently achieves a 5–8% speed improvement over vanilla speculative decoding while maintaining an identical sampling distribution. In contrast, as shown in Table 4 and the supplementary experiments, MTAD achieves a 1.42x speedup on Llama-2 and OPT models, and a 1.16x speedup on Llama-3 models, compared to vanilla speculative decoding. Moreover, MTAD delivers higher output quality due to its design focus on approximating multi-token joint decoding (MTJD) rather than adhering to multinomial sampling.

These results highlight MTAD’s advantages in both efficiency and effectiveness, underscoring the benefits of its distinct design objectives.

[1] Sun, et al. Optimal Block-Level Draft Verification for Accelerating Speculative Decoding.

[2]Eagle-2: Faster inference of language models with dynamic draft trees

[3] Better & Faster Large Language Models via Multi-token Prediction

[4] A Thorough Examination of Decoding Methods in the Era of LLMs

Thank you for providing a more detailed reference and clarification regarding the experiments. Based on your suggestion, we implemented Multi-Candidate Speculative Sampling (MCSS) from [2] with sampling without replacement. The updated results are shown below and included in the table within the common response (a new "MCSS" column in the second table). While MCSS is slightly faster than SpecInfer, our method, MTAD, still outperforms it both in efficiency and output quality.

Additionally, as discussed at the end of Section 3.2, multi-draft speculative sampling methods (e.g., Spectr, SpecInfer, MCSS) are compatible and orthogonal to our approach for the following reasons:

• Extensibility of MTAD: MTAD can be easily extended to generate multiple draft sequences, making it compatible with multi-draft methods.
• Distinct Design Objectives: Multi-draft methods aim to be lossless with respect to multinomial sampling, while our primary design objective is to approximate multi-token joint decoding (MTJD) to achieve superior output quality and efficiency.

We hope these clarifications and updated results address your concerns. Please let us know if further explanation is needed.

Thank you for your thoughtful questions and observations.

Temperature setting

The temperature is set to 1 in the experiments above.

Efficiency Patterns: "MCSS > Spectr > SpecInfer"

First, based on our experiment results, the average speed of MCSS is 25.73 tokens/s, the speed of spectr is 25.57 tokens/s, the speed of SpecInfer is 24.97 tokens/s. These results align with the reviewer’s claim that MCSS demonstrates slightly higher efficiency, followed by Spectr and then SpecInfer.

Second, the differences in speed between these methods are relatively small. For example, Table 4 of the MCSS paper reports that MCSS without replacement is on average only 4% faster than MCSS with replacement (equivalent to SpecInfer). On Llama-13 models—the most similar to the Llama-3 models used in our experiments—the speed up is just 1%. In our experiments, MCSS is on average 3% faster than SpecInfer, which is consistent with these findings. Besides, given these small differences, it is not surprising that Spectr can sometimes be faster than MCSS without replacement.

Thrid, the assertion that "MCSS > Spectr > SpecInfer" appears to be an empirical observation rather than a theoretical guarantee. As suggested by the reviewer, sampling without replacement improves efficiency most greatly when the effective number of unique drafts is significantly smaller than the total number of draft sequences. This efficiency gain depends on the sampling distribution, which is affected by draft and target models, as well as the datasets used. Therefore, it is expected that MCSS without replacement is not always the fastest.

We hope this explanation clarifies the observed results. Please feel free to reach out if you have further questions or need additional details.

Comparison with Lossy Verification Methods

We appreciate your feedback regarding the comparison between MTAD and lossy verification methods. In the original submission we have one lossy baseline, BiLD. Additionally, we have included Medusa's typical sampling algorithm as a baseline. These results, detailed in the "Common Reply on Perplexity and Downstream Performance," demonstrate that MTAD consistently achieves superior efficiency and output quality compared to other lossy verification methods.

More rigorous evaluation for output quality

We understand your concern about relying on perplexity (PPL) as a primary performance metric. In our original submission (Table 6), we showed that MTAD delivers improved output quality across multiple datasets using diverse metrics. To address your request for more rigorous evaluations, we have conducted additional experiments on downstream tasks, including HumanEval's Pass@1 and Spider’s execution accuracy (execution accuracy = 1 if the returned SQL result is correct, otherwise it is 0), as shown in the common response. These experiments confirm that MTAD improves not only perplexity but also downstream task quality, bridging the gap between theoretical and practical performance.

Impact of Fixed Thresholds in Speculative Decoding

You raised a good question about whether the same speedup achieved by MTAD can be replicated in vanilla speculative decoding using a fixed threshold. To explore this, we evaluated speculative decoding (SpD) with a fixed threshold (thres=0.1), alongside the original lossless SpD and MTAD (thres=0.1). We run Llama-3-8B model (with Llama-3-1B as the draft model) on Spider dataset. The results are summarized below:

These results demonstrate that while employing a fixed low threshold in vanilla SpD increases acceptance rates and speed, it renders the decoding algorithm lossy, leading to a significant decline in downstream accuracy. Furthermore, even with a fixed threshold, SpD remains less efficient than MTAD. It is because SpD terminates verification immediately after rejecting a token, whereas MTAD continues the process to evaluate whether subsequent tokens can still pass verification.

Dear Reviewer h4X4,

Thank you for your valuable contributions to the review process for the paper! The authors have submitted their rebuttal, and I would greatly appreciate it if you could take a look and provide your response.

Thanks for your response. I appreciate your addressing my concerns and will raise my score.

Relationship Between Perplexity and Output Quality, and Qualitative Generations

We appreciate your thoughtful feedback and understand your concerns about the relationship between perplexity and output quality. For a comprehensive explanation, we kindly refer you to our "Common Reply on Perplexity and Downstream Performance," where we provide detailed analyses and additional experiments demonstrating that MTAD's lower perplexity correlates with higher output quality.

We also include qualitative examples below to illustrate that MTAD avoids generating repeated tokens. We provide examples from the HumanEval and Spider datasets using Llama-3-8B and Llama-3-1B models.

Prompts:

from typing import List
def filter_by_substring(strings: List[str], substring: str) -> List[str]:
""" Filter an input list of strings only for ones that contain given substring
>>> filter\_by\_substring(
$

$
, 'a')
[]
>>> filter_by_substring(['abc', 'bacd', 'cde', 'array'], 'a')
['abc', 'bacd', 'array']
"""

Output:

return 
$
str for str in strings if substring in str
$
  

Prompt:

[INST] <<SYS>> You are a SQL expert. You need to write the correct SQL based on the user question and database schemas. <</SYS>>  
Schema:  
Table concert, columns = [*,concert_ID,concert_Name,Theme,Stadium_ID,Year]  
Table singer, columns = [*,Singer_ID,Name,Country,Song_Name,Song_release_year,Age,Is_male]  
Table singer_in_concert, columns = [*,concert_ID,Singer_ID]  
Table stadium, columns = [*,Stadium_ID,Location,Name,Capacity,Highest,Lowest,Average]

Question: How many singers do we have?
SQL:

Output:

SELECT count(*) FROM singer;

Use Sub-section for Energy Analysis

We appreciate your suggestion and we will consider to merge it into a sub-section. Nevertheless, previous studies neglect the energy efficiency of SpD, a critical aspect in the real world. Our analysis addresses this gap and is applicable to MTAD and other SpD approaches, which we believe adds significant value to the community.

Are Draft and Target Models Different or Fine-tuned?

We apologize for the lack of clarity on this point. In all the experiments, our method and all baselines use the same draft and target models. In all experiments reported in the main paper, we used open-sourced pre-trained draft and target models without any fine-tuning. To further investigate the impact of fine-tuning, we conducted additional experiments (Appendix C.3) where draft models or both draft and target models were fine-tuned.

Performance with Larger Draft Model

If you are referring to ablation studies where the target model is fixed while the draft model size varies, we now add an evaluation of MJAD with Llama-3-8B as the target model and Llama-3-1B and Llama-3-3B as draft models. As expected, Llama-3-3B aligns better with the 8B model, resulting in a higher number of accepted tokens and improved perplexity, which aligns with our analysis in Section 3.2. However, running Llama-3-3B is significantly slower than Llama-3-1B, leading to a noticeable drop in speed.

Correlation between Energy and Speed

We appreciate your question, but we do observe a correlation between speed and energy as shown in the Figure 5, which is newly added to the Appendix C.5, whether considering the entire table or focusing on a specific dataset and model. For fairness,all methods for a given dataset and model were run on the same machine nodes. However, for a fixed method (e.g., Spectr), experiments on different datasets and models might be conducted on different nodes (all equipped with L40 GPUs). We did notice that the same configuration run on different machines may have varied energy consumption. This variation introduces some randomness, which could make the correlation appear less consistent across datasets and models.

In addition, it is possible that a method has a higher acceptance rate but also a higher energy consumption. For example, Spectr increases the acceptance rate by increasing the number of draft sequences, which also increases the cost of verification with the large model. So Spectr might have higher energy consumption in total.

Acceptance Threshold vs Acceptance Rate

In Table 5 of the paper, we show the average number of tokens generated per iteration across all datasets. Furthermore, we provide additional results below, showing how the number of tokens per iteration changes with varying acceptance thresholds on the HumanEval dataset using Llama-3 models. These results show that as the acceptance threshold increases, the acceptance rate decreases, leading to fewer tokens generated per iteration.

Dear Reviewers,

We hope this message finds you well. We have submitted a comprehensive evaluation demonstrating that our method enhances output quality while being the fastest and most energy-efficient. Additionally, we have addressed all specific questions raised.

If you have any further inquiries or require additional information, please let us know. We are committed to providing any necessary clarifications before the discussion phase concludes.

Thank you for your time and consideration.

Best regards, Authors

Thanks for the additional results. Here I have further questions about the results.

What is the sampling method you used in Specinfer method to construct the token trees, e.g., with replacement sampling or without replacement sampling?

Thank you for your thoughtful suggestions. We appreciate your perspective and conduct experiments incorporating sampling without replacement as suggested. The detailed results are included in our separate response to you (reviewer v4L1). The results show that the effect of sampling without replacement is not significant, and MJAD is still the fastest method with highest output quality.

However, we want to clarify some issues regarding to sampling without replacement:

In Spectr and SpecInfer, both methods assume that draft tokens are sampled independently to ensure the output token aligns with the target distribution (Theorem 4.2 in the SpecInfer paper and Theorem 2 in Spectr paper). Sampling without replacement breaks this assumption because the probability of selecting a token is affected by previous selections. While this deviation may not significantly impact output quality in practice, it does invalidate the assumption that each draft sample is drawn independently. As a result, the formal losslessness guarantee cannot be directly extended to the without-replacement case without revisiting and modifying the theoretical framework.

We hope this explanation and additional results address your concerns, and we sincerely appreciate your thoughtful feedback and encouragement.

Thanks for the additional results.

Do you know why do the lossless methods in above table have different accuracies? From my understanding the lossless speculative methods are known to maintain the accuracy with the accuracy of autoregressive target model. Even if we run the target model in sample-mode, if seed is fixed, then the outputs generated should be same, which should result in same accuracy.