Block Verification Accelerates Speculative Decoding

Authors: Ziteng Sun, Uri Mendlovic, Yaniv Leviathan, Asaf Aharoni, Jae Hun Ro, Ahmad Beirami, Ananda Theertha Suresh
Primary area: learning theory
Keywords: llm efficiency, speculative decoding, distribution coupling

Abstract:
Speculative decoding is an  effective method for lossless acceleration of large language models during inference. It uses a fast model to draft a block of tokens which are then verified in parallel by the target model, and provides a guarantee that the output is distributed identically to a sample from the target model. In prior works, draft verification is performed independently token-by-token. Surprisingly, we show that this approach is not optimal. We propose *Block Verification*, a simple draft verification algorithm that verifies the entire block jointly and provides additional wall-clock speedup. We prove that the proposed mechanism is optimal in the expected number of tokens produced each iteration and specifically is never worse than the standard token-level verification.
Empirically, block verification provides modest but consistent wall-clock speedups over the standard token verification algorithm of 5\%-8\% in a range of tasks and datasets.
Given that block verification does not increase code complexity, maintains the strong lossless guarantee of the standard speculative decoding verification algorithm, cannot deteriorate performance, and, in fact, consistently improves it, it can be used as a good default in speculative decoding implementations.

Decision: accept (poster)
Reviewer scores: 6, 6, 8, 6

Reviews and discussion:
<thread>
creation date:
1729068122169

thread_type:
official_review

<thread_object>
creator: reviewer_csee

<content>
summary:
This paper studies the problem of optimizing speculative decoding from an algorithm level to achieve inference acceleration. The key idea behind this paper is the observation that verifies multiple draft tokens in a block jointly, rather than token-by-token, can bring improvement in mean accepted tokens, which leads to the wall-clock speedup for LLM inference. Based on the idea, the paper proposes a simple block verification algorithm, which is plug-and-play for some existing speculative decoding methods. The authors theoretically show that block verification is lossless and better than standard speculative decoding, making it a stronger default implementation of speculative decoding. The experiments demonstrate that block verification modestly but consistently improves the mean accepted tokens and the final wall-clock speedup.

strengths:
1. The introduction of the block verification in the full distribution is clear and easy to understand, and the paper is well-written with clear explanations to the block verification algorithm.
2. This method shows great simplicity and is easy to use. It does not incur additional computation or memory overhead, and is very easy to implement. 
3. The authors theoretically show that block verification is lossless and better than standard speculative decoding, making block verification a stronger default verification for speculative decoding.

weaknesses:
While I really appreciate the simplicity of the method, the novelty and the contributions of the paper are a little weak for me. The reasons are:

1. The motivation that *"verifying multiple draft tokens token by token is not optimal"* is very similar to the motivation in Tree Monte Carlo (TMC) [1], which alleviates the novelty of this paper. Given the empirical results that block verification only brings 5%~8% speedup, I doubt the technical contributions of block verification. The block verification seems more like a trick with theoretical support.
2. There lacks a significant discussion about the decoding temperature $T$ in LLM inference, and the authors do not report the temperature in the experiment details. **In my understanding, the block verification can only bring speedup with $T > 0$, as the block verification degenerates to the token verification in greedy decoding ($T=0$).** Please correct me if I have any misunderstanding. While speculative decoding provides maximal speedup in greedy decoding settings for some specific tasks, such as coding and math reasoning, block verification cannot provide improvement on these tasks. Besides, additional experiments to investigate the influence of different decoding temperature are necessary.
3. Currently, I think there exists a large room (more than 1 page) to conduct more experiments.
   - Experiments for more LLM combinations (e.g. Llama family [2] and Vicuna [3]) across more benchmarks (e.g. MT-Bench [4] and SpecBench [5]) **with different temperature settings**.
   - Experiments for combining block verification to some latest speculative decoding methods (e.g. Medusa [6] and Eagle [7]).

I know that conducting a wide range of evaluation experiments are costly and time consuming, and I will increase my score if the authors clearly address my concerns.



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

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

[3] Chiang, Wei-Lin, et al. "Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023." *URL https://lmsys. org/blog/2023-03-30-vicuna* 3.5 (2023).

[4] Zheng, Lianmin, et al. "Judging llm-as-a-judge with mt-bench and chatbot arena." *Advances in Neural Information Processing Systems* 36 (2023): 46595-46623.

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

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

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

questions:
I would like to raise some questions to improve the manuscripts.

1. Could you provide a more detailed explanation to the motivating example with partial information? You have mentioned "with block verification" in Line 124, but it is not clear how block verification works in this section.
2. Existing speculative decoding methods mainly adopt a tree-based verification manner, which can significantly enhance the mean accepted tokens. Could you provide some explanation how block verification works in a tree-based verification manner?
3. Could you provide a more detailed theoretical assumptions for Definition 1, Theorem 1 and Theorem 2? Besides, I think the section Theoretical Guarantees can be further improved by providing some intuitive explanation (e.g. why block verification is optimal for any valid draft verification algorithm), as this can help readers to understand the advantages of block verification over TMC.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721218023

thread_type:
official_review

<thread_object>
creator: reviewer_jhoe

<content>
summary:
The paper introduces a novel verification algorithm called the block verification method, which enhances the efficiency of speculative decoding in large language models (LLMs). This method contrasts with the traditional Token Verification, which optimizes the verification of token blocks to increase efficiency. The study demonstrates that Block Verification outperforms existing methods regarding the expected number of generated tokens (called the block efficiency) and wall-clock times while providing a theoretical guarantee of optimal performance under given conditions. Empirical evaluations show improvements across various tasks, confirming its effectiveness without additional code complexity.

strengths:
- The paper provides solid theoretical guarantees, ensuring that the proposed method does not compromise the output distribution.
- The experiments validate the practical benefits, with performance gains across a diverse set of tasks.
- The proposed algorithm does not increase code complexity, making it easy to integrate into existing LLM architectures.
- The paper highlights how Block Verification compares favorably to related methods, strengthening its contribution.

weaknesses:
- The depth of proofs might be challenging for practitioners without a strong mathematical background, potentially limiting the paper's audience.
- There is a typo in the manuscript: page 8, line 413: deocding -> decoding

questions:
- Are there specific conditions or types of LLM architectures where the performance gains of Block Verification may be more pronounced or limited?
- How does the algorithm handle edge cases where the distributions of the drafting and target models diverge significantly?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730729448452

thread_type:
official_review

<thread_object>
creator: reviewer_eih8

<content>
summary:
This paper introduces Block Verification, a novel algorithm designed to accelerate speculative decoding in large language models. Unlike traditional token-by-token verification, Block Verification evaluates and accepts a group of tokens (a "block") together. This method achieves faster generation speeds without compromising output quality.

strengths:
1. **Block Verification** improves efficiency by verifying token blocks rather than individual tokens in speculative decoding, preserving the same distribution.

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

3. Block verification is easy to implement, with minimal modifications to existing speculative decoding systems.

weaknesses:
1. Consistency in final distribution does not guarantee identical generation sequences. For instance, the large model might generate "ABC" while the small model generates "ADC." It’s possible that in the context of "ADC," the next token’s distribution aligns between the models, but under greedy decoding, the large model should ideally follow "ABC" rather than "ADC." The authors state that block verification accepts more tokens than token verification. In the case of greedy decoding, does this imply potential token differences? Would such differences impact the accuracy of the answer, or would block verification revert to token-by-token verification?
2. The explanations of the formulas and algorithms lack intuitive clarity, making comprehension more challenging, even though the modifications from token verification are not large.

questions:
1. In the appendix, a batch size of 8 was used to compare with tree attention. What batch size was used in the main experimental section?
2. How does the performance compare with Medusa/Eagle's static tree attention?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730772692060

thread_type:
official_review

<thread_object>
creator: reviewer_1noe

<content>
summary:
This paper presents a new algorithm for draft verification for speculative decoding for LLMs. Speculative decoding is a method that accelerates the inference process of LLMs using predictive heuristics to produce “drafts” of the likely next tokens the LLM will generate. These drafts must go through a verification process to determine whether or not they should be accepted, depending on how well they fit the target model’s distribution. The authors argue that the prior state-of-the-art approach for draft verification, Token Verification, is not optimal, since it considers the tokens one by one. The authors instead propose a method to consider the tokens as a block by considering their joint probabilities. The authors also demonstrate that their method accepts more tokens on average than the original Token Verification approach, which is more efficient in the long run. Their experimental results demonstrate that despite the standard overheads of LLM inference, the Block Verification algorithm outperforms the Token Verification algorithm in terms of wall clock speedup.

strengths:
Overall, the paper is well written and the problem is clearly stated.

The theoretical proofs are sound to the best of my knowledge.

weaknesses:
The paper does not provide sufficient evidence that it provides a considerable speedup.
Speedup is from a higher acceptance rate. The paper is using  PALM-2-XXS and XXXS. At this model size, answers tend to be quite bad, which makes it hard for actual response evaluation. 

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

# Minor comments 

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

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

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

questions:
- How will the speedup results scale when using larger models?

- How are probabilities of all subblocks calculated?

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

## Post-rebuttal comment

The authors addressed the questions raised in my review, and I have increased my score accordingly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732291766247

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response and additional experimental results

comment:
We thank all the reviewers for their detailed reading and constructive comments. We have revised the paper accordingly based on the suggestions (the new additions are in red color). 
We apologize for the delay in the response since addressing the reviewers’ suggestions required us to implement our algorithm in PyTorch (the original implementations are in JAX) based on codes from Spec-Bench (Xia et al 2024). We are planning to open-source our implementation in a future revision.

Below we discuss *theoretical and practical contributions* of our work, and present the *additional experimental results* on open-sourced models. We will then address each reviewer’s comments in individual responses.

**Theoretical contribution**  We would like to start by highlighting that the main contribution of this work is of  *algorithmic and theoretical* nature. The standard token verification algorithm in speculative decoding proposed by Leviathan et al. (2023) is used in virtually all single draft speculative decoding works (see Section 7 for a summary of related work). We show that this widely adopted algorithm can be improved with theoretical guarantees by proposing block verification. We prove that the algorithm preserves the distribution of the target model (Theorem 1), and it is *optimal* in the expected number of tokens produced in a fixed number of iterations for all possible verification algorithms that guarantee matching output distribution (Theorem 2). Specifically, the expected number of accepted tokens is never worse than the standard token verification algorithm. The theoretical contribution demonstrates the novelty and significance of our work from a theoretical point of view.

**Practical contribution** Practically, our proposed algorithm, block verification, is a *simple* replacement of the standard token verification algorithm in speculative decoding with a few lines of code change, with negligible additional computation overheads, and no changes to the drafting phase. The simplicity of the algorithm makes it compatible with other works that focus on improving the drafting phase of speculative decoding in the single-draft case. Empirically, we have also demonstrated our proposed algorithm consistently achieves modest improvement over standard token verification across a wide range of tasks, models (PALM-2 family and the newly added experiments on open-sourced Vicuna models), temperature ranges (see the newly added experiments), and different mainstream development platforms (PyTorch and JAX), corroborating the theoretical guarantees. While the gains are modest, we believe the simplicity, consistency and strong optimality guarantee makes it a good default implementation in single-draft speculatively decoding.

**New experimental results with open-sourced models** To further demonstrate the effectiveness of our technique in other LLM combinations, especially open-sourced models, benchmarks, and different temperature settings, we conduct the set of experiments proposed in Spec-Bench (Xia et al. 2024) with Vicuna family of models (Chiang et al. 2023}. We use Vincuna-7B-v1.3 as the target model and Vincuna-68M as the draft model. We use a single NVIDIA H100 GPU with a batch size of 1 and a max generation length of 1024. To study the effect of temperature, we consider temperature $T \in \{0.2, 0.6, 1.0\}$ and fix $\gamma = 8$. Our algorithm obtains consistent improvement over token verification  (up to 8.70% in block efficiency (BE) and 6.07% in wall clock speedup (WS) ) across different draft lengths for all temperatures bigger than 0. The results are listed in the table below.  More details about the experiments are added to Section 6.1 in the revised draft.

| $T$  | BE (TokenV) | BE (BlockV) | BE $\uparrow $  | WS (TokenV) | WS (BlockV)| WS $\uparrow \%$  |
| -------- | ------- |------- |------- |------- |------- |------- |
|0.2 | 2.75  | 2.85 | 3.72\% | 1.22  | 1.24 | 1.66\%  |
|0.6 | 2.75  | 2.90 | 5.32\% | 1.23 | 1.29 | 4.24\%  |
|1.0 | 2.79  | 3.04 | 8.70\% | 1.27 | 1.34 | 6.07\%  |

**The effect of temperature**
For temperature 0, which corresponds to greedy decoding, our algorithm is the same as token verification and doesn't provide additional speedups. In non-zero temperature settings, the advantage is consistent, and the additional improvement is higher for larger temperatures. 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. Modern uses of language models mostly use 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
). The result shows that the gain of our algorithm could be higher for more creative generation tasks that use a larger temperature such as creative writing, chatbot response, and exploratory code writing.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733273626538

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of rebuttal and discussion

comment:
We thank the reviewers for their constructive feedback and active engagement in the discussion phase. Based on the reviewers suggestions, we have revised the submission in the following ways:
- Implemented our algorithm in PyTorch and tested it using open-sourced models (Vicuna models) and more public datasets (SpecBench). We will release the implementation in follow-up revisions.
- Included the new experimental results in the revised draft, see Section 6.1 and Table 2.
- Added experiments to study the effect of temperature on the obtained speedup of our method.
- Added more intuitions and discussions to improve the presentation of the algorithm and theoretical results, see e.g., line 285 - line 312 in the revised draft.
- Improved the presentation by fixing typos and adding more explanation in other parts. 
See other changes in the draft (highlighted in red).

We'd like to thank the reviewers again for their reviews, which greatly helped improve the submission.

Sincerely,\
Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
(a) Summary of Scientific Claims and Findings

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

(b) Strengths of the Paper

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

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

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

(c) Weaknesses of the Paper and Missing Elements

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

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

(d) Decision and Rationale

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