Thank the reviewer for the detailed reading and helpful comments. Below we address the reviewer's questions.

Q1: Comparison to tree Monte Carlo

The independent work of tree Monte Carlo (Hu and Huang, 2024) shares a similar intuition with our algorithm that more tokens can be accepted by coordinating the acceptance rule of multiple draft tokens. We have proved in our work that our algorithm achieves the optimal speedup among all valid verification algorithms, including theirs (see Theorem 2). We note that Hu and Huang, (2024) does not provide a similar optimality guarantee for their algorithm. Moreover, our algorithm requires minimal changes to the standard token verification algorithm, making it easy to implement in practice. Given that Hu and Huang (2024) did not release their implementation in the paper, it was not possible for us to make an empirical comparison.

Q2: Given the empirical results that block verification only brings 5%~8% speedup, I doubt the technical contributions of block verification. The block verification seems more like a trick with theoretical support.

While the wall clock speedup improvement over standard speculative decoding is modest, the improvement is obtained only through changing the verification algorithm with a few lines of code change and negligible additional computational overhead. In the single-draft case, the standard for this in the literature is the well-established token verification algorithm (Leviathan et al., 2023), which is adopted by almost all follow-up works of speculative decoding in the single-draft case while the drafting mechanism has been improved upon in many works. See Section 6 for a summary of prior works. In fact, we show that our proposed algorithm obtained the provably optimal speedup for all valid verification algorithms under natural assumptions (Theorem 2). Hence while the improvement is modest, no other algorithm can do better by just changing the draft verification algorithm, and our algorithm addresses this optimality gap. We believe the simplicity, wide applicability and strong theoretical guarantee of the algorithm’s optimality makes this a significant theoretical and algorithmic contribution.

Q3: There lacks a significant discussion about the decoding temperature T in LLM inference, and the authors do not report the temperature in the experiment details. In my understanding, the block verification can only bring speedup with T>0, as the block verification degenerates to the token verification in greedy decoding (T=0). ...additional experiments to investigate the influence of different decoding temperatures are necessary.

The reviewer is correct that block verification is the same as token verification for greedy decoding and no further speedup could be provided. However, we want to emphasize that most modern uses of language models uses temperature sampling with temperature with a positive temperature (see https://community.openai.com/t/cheat-sheet-mastering-temperature-and-top-p-in-chatgpt-api/172683). To study the impact of temperature, we have added further experiments to numerically quantify the additional speed-up from block verification for temperatures in [0.2, 0.6, 1.0]. Our algorithm also achieves consistent speedups over token verification in these settings. See Section 6.1 in the updated draft and the global response for more detailed results.

We thank the reviewer for the helpful comments. Below we answer the reviewers' questions.

Q1: Consistency in final distribution does not guarantee identical generation sequences. For instance, the large model might generate "ABC" while the small model generates "ADC." It’s possible that in the context of "ADC," the next token’s distribution aligns between the models, but under greedy decoding, the large model should ideally follow "ABC" rather than "ADC." The authors state that block verification accepts more tokens than token verification. In the case of greedy decoding, does this imply potential token differences? Would such differences impact the accuracy of the answer, or would block verification revert to token-by-token verification?

Thanks for the great question. The reviewer is absolutely correct that in the case of greedy decoding, token verification and block verification algorithm will be the same since the distributions will be reduced to a one-hot distribution. Hence, there will be no token differences between the two methods for greedy decoding. However, we want to emphasize that most modern uses of language models uses temperature sampling with positive temperatures (see discussions in https://community.openai.com/t/cheat-sheet-mastering-temperature-and-top-p-in-chatgpt-api/172683 ), and we have now added further experiments to numerically quantify the additional speed-up from block verification for temperature in this range (see Section 6.1 and the global response for discussions on the results). Hope this resolves the reviewer’s question.

Q2: The explanations of the formulas and algorithms lack intuitive clarity, making comprehension more challenging, even though the modifications from token verification are not large

Thanks for the useful comment. We have updated the draft with more intuitions on the algorithms parameter choices of the algorithm and how the theoretical guarantees are achieved in Section 4 after stating the theoretical guarantees. The updated discussions are marked in red. We hope this will improve the understandability of the proposed algorithm and its theoretical guarantees.

Q3: In the appendix, a batch size of 8 was used to compare with tree attention. What batch size was used in the main experimental section? Batch size is 1 in all of the main experimental sections. Note that since our method only modifies the verification phase of the algorithm and doesn't introduce additional draft tokens, the speedup we get is independent of the batch size. We have updated the submission to clarify this in the main paper.

Q4: How does the performance compare with Medusa/Eagle's static tree attention?

Medusa and Eagle are multi-draft speculative decoding models. Extending the block verification idea to the multi-draft case like SpecTr and SpecInfer requires non-trivial efforts and is beyond the scope of our work. Combining block verification with tree-based verification is an interesting question for future work. While block verification is only designed for single-draft speculative decoding, we have compared the algorithm with SpecTr and SpecInfer (see Appendix D.1) as two representative multi-draft speculative methods where we observed that for a relatively large batch size, block verification is more effective than these methods. This is important since in practical LLM serving systems, batching is a common technique to increase the throughput of the system. Moreover, the one-draft case is an active research area. Notably, this is the case that have been studied by a lot of follow-up works including Chen et al [2023b], Sun et al [2024], Zhou et al [2023], Liu et al [2023], Gloeckle et al. [2024], Zhang et al. [2024], Elhoushi et al. [2024] (see a survey of recent of works in Section 6 and Table 2). These works all use token verification as the draft verification algorithm.

Typos. We have fixed the typos in the revised draft.

Thank the reviewer for the acknowledging the novelty and strength of our work. Below we answer the reviewers' questions.

Q1: The depth of proofs might be challenging for practitioners without a strong mathematical background, potentially limiting the paper's audience.

Thanks for the useful comment. We have updated the draft with more intuitions on the algorithms parameter choices of the algorithm and how the theoretical guarantees are achieved in Section 4 after stating the theoretical guarantees. The updated discussions are marked in red. We hope this will improve the understandability of the proposed algorithm and its theoretical guarantees.

Q2: Are there specific conditions or types of LLM architectures where the performance gains of Block Verification may be more pronounced or limited?

Our proposed block verification algorithm is independent of the LM architecture and could provide provably optimal speed-up over token verification for any drafter and verifier model. To further demonstrate this, we have added a new set of experiments on Spec-Bench (Xia et al. 2024} with Vicuna family of models implemented in PyTorch. Combined with the original experiments on the PALM-2 family of models implemented in JAX, this demonstrates the advantage of our approach across various LM families, benchmark datasets, and development platforms (see Section 6.1 and the global response for discussions on the result). Through experiments, we have identified two factors that affect the speed-up of our proposed method. (1) Draft length, as shown in Figure 5 and the newly added Table 2, the improvement over token verification is higher for longer block length; (2) Temperature: in Table 2, we also conduct various experiments with different temperatures, and we observe that the improvement also increases as the temperature increases. The observation is consistent with the intuition behind the algorithm, which coordinates the randomness in the acceptance decisions at different token locations to obtain further improvement. The randomness in the per-token decision increases as the temperature increases and the overall randomness further increases as the draft length increases.

Q3: How does the algorithm handle edge cases where the distributions of the drafting and target models diverge significantly?

When the draft and target model diverge, the verification algorithm will reject the draft tokens with high probability and sample from a residual distribution that is close to the target model. We would like to mention that even when all the tokens are rejected, speculative decoding will still produce a residual token, and hence at least one sample is generated in each decoding iteration; leading to a block efficiency of at least 1.

We thank the reviewer for the helpful comments and acknowledging the soundedness of our work. Below we answer the reviewer's questions.

Q1: How will the speedup results scale when using larger models? The paper is using PALM-2-XXS and XXXS. At this model size, answers tend to be quite bad, which makes it hard for actual response evaluation.

We would like to first clarify that the target model (the model where the final generated sequences are following) we use is PALM-2-S. We are using the smaller PALM-2-XXS and XXXS only as fast drafter models, which is typical for speculative decoding implementations.

The number of parameters of the Palm-2-S mode is not publicly known. However, based on the tech report [1], it is a capable model in modern standards. For example, the performance on various benchmarks reported in Table 2 is slightly worse than the previous generation of PALM model with a size of 540B. Additionally, the one-shot performance of PALM-2-S reported in [1] exceeds or is on-par with the multi-shot performance of Gemma 2 9B model, Mixtral 7B, LLaMA-3 8B (as reported in [2]) for a few benchmarks including TrivialQA (5-shot), NaturalQuestions (5-shot), HellaSwag (10-shot), and WinoGrande(5-shot).

In the updated draft, we also provide experiments with the open-sourced Vicuna models with Vicuna-7B as the target model and Vicuna 68M as the drafter model, similar to the setting in Spec-Bench [3], as suggested by reviewer CsEe, and we observe similar consistent speedup results (see Section 6.1 in the revised draft and the global response for discussions on the new experimental results).

We hope the above could resolve the reviewer’s concern on the applicability of the method for large models.

Q2: How are probabilities of all subblocks calculated?

After obtaining the next-token probabilities conditioned on the prefixes, the probability of the draft subblocks could be computed by taking the product of each individual draft tokens, e.g., $M(X^k | c) = M(X_1 | c) M(X_2 | c, X_1)... M(X_k | c, X^{k-1})$. In fact, in our implementations of the algorithm, we don’t explicitly compute the probability of these subblocks. Instead, we compute the quantities $p_i$’s as defined in step 4 of Algorithm 2 (line 171), which contains sufficient information the algorithm needs from the probabilities of sub-blocks. A python implementation of the algorithm is described in Appendix A.

Q3: Page 7, line 334: How realistic is this experimental setting? How many drafts are usually produced during speculative decoding, and how many copies of the model would we need for evaluating

As discussed in Leviathan et al., (2023), in practice, the choice of the block length $\gamma$ depends on (1) the improvement in block efficiency when $\gamma$ increases; (2) the increase in drafting time and verification time when $\gamma$ increases. There is usually a sweet spot, which depends on the hardware and similarity of the models. In our experiments, the $\gamma$ that leads to the best speed up is usually 6, and $\gamma = 8$ also achieves a similar speedup. Hence $\gamma = 8$ is a realistic setting in practice. At the optimal $\gamma = 6$, the algorithm also achieves an additional 6.1% increase in block efficiency and 4.67% in wall clock speedup on average compared to token verification (Leviathan et al., 2023), see Table 7 in the Appendix for the detailed numbers.

Regarding copies of the model during evaluation, if we understand the question clearly, the question is about the number of copies of target model parameters to be loaded into memory during inference. In fact, the parallel evaluation of multiple next-token distributions is implemented through proper setting of the attention mask, and only one copy of the model parameters is loaded during inference.

We hope the above resolves the reviewer’s question. We are happy to answer further questions from the reviewer.

Minor comments. We have fixed the typos and updated the title of Figure 4 in the revised draft.

[1] PALM-2 technical report. https://arxiv.org/pdf/2305.10403

[2] Gemma 2: Improving Open Language Models at a Practical Size. https://arxiv.org/pdf/2408.00118

[3] Spec-Bench: A Comprehensive Benchmark and Unified Evaluation Platform for Speculative Decoding https://github.com/hemingkx/Spec-Bench