Draft Model Knows When to Stop: A Self-Verification Length Policy for Speculative Decoding

↗ arXiv ↗ Hugging Face ↗ Papers with Code

TL;DR

#

Key Takeaways

#

Why does it matter?

#

This paper is important because it significantly improves the speed of large language model inference by addressing a key limitation of existing speculative decoding methods. Its novel self-verification length policy (SVIP) is training-free and easily adaptable to various models and frameworks, making it highly relevant to the broader NLP community. The findings open avenues for developing more efficient and faster LLM inference systems, particularly beneficial for resource-intensive applications.

Visual Insights

#

🔼 The figure illustrates how the difficulty of generating tokens varies within a sequence. A draft model is used to predict tokens which are then verified by a more powerful target model. Some tokens, like common greetings, are easy for the draft model to predict and thus have high acceptance rates (many draft tokens are accepted and verified). Other tokens, such as those requiring complex reasoning or domain-specific knowledge, are much harder for the draft model to accurately predict. This results in a lower acceptance rate, with fewer draft tokens being accepted for these more difficult parts of the sentence.

read the caption

Figure 1: The “difficulty” of tokens varies in a sequence, resulting in different numbers of accepted draft tokens at different positions.

🔼 This table presents the speedup achieved by using the Self-Verification length Policy (SVIP) for speculative decoding compared to a baseline approach of using only the target language model for autoregressive decoding. The speedup is calculated across six different tasks within the SpecBench benchmark, using three different large language models (Pythia, Qwen, and LLaMA) with their corresponding smaller draft models. Results are shown for two baseline methods (‘Const’ for constant draft length and ‘Heuristics’ for a heuristic-based draft length) and SVIP. The percentage improvement of SVIP over the target-model-only approach is indicated in parentheses.

read the caption

Table 1: Speedup over target-model-only autoregressive decoding on SpecBench.

In-depth insights

#

SVIP: Core Algorithm

#

The core algorithm of SVIP revolves around dynamically adjusting the length of draft sequences in speculative decoding. Instead of a fixed draft length, SVIP leverages the entropy of the draft model’s token distribution to determine when to stop drafting and begin verification. A lower bound on the system’s acceptance rate, approximated by the draft model’s entropy, guides this decision. High entropy indicates difficult tokens, prompting earlier termination of the draft sequence, while low entropy signals easier tokens, allowing for longer drafts. This adaptive approach aims to optimize speed without sacrificing accuracy, achieving significant wall-clock time improvements over baseline methods. SVIP is inherently training-free, requiring only the draft model’s probability distribution. The algorithm’s simplicity and compatibility with various existing speculative decoding frameworks highlight its practical value for enhancing LLM inference efficiency.

Entropy-Based Policy

#

An entropy-based policy for speculative decoding offers a novel approach to optimizing the efficiency of large language models. The core idea revolves around dynamically adjusting the length of draft sequences generated by a lightweight model based on the inherent uncertainty, or entropy, of the predicted token distributions. By analyzing the entropy of each draft token, the policy can intelligently decide when to continue drafting or to verify the draft with a more powerful model. This avoids the limitations of fixed-length draft policies, which often fail to account for the varying difficulty of token generation across different tasks and contexts. A low entropy signifies high confidence, thus justifying longer drafts to enhance efficiency. Conversely, high entropy signals uncertainty, prompting early verification to minimize wasted computation on uncertain predictions. The policy’s adaptability improves both speed and acceptance rates compared to fixed-length counterparts, yielding substantial wall-clock speedups across various benchmarks and model sizes. The training-free nature further enhances its practicality and compatibility with existing speculative decoding frameworks.

Speculative Decoding

#

Speculative decoding is a crucial technique accelerating large language model (LLM) inference. It leverages a faster, lightweight draft model to predict token sequences, which are subsequently verified by a more powerful, but slower, target model. This approach avoids the computationally expensive autoregressive generation of every token by the target model. The efficiency gains are significant, especially for longer sequences. However, traditional methods employ a fixed draft length, failing to account for varying levels of difficulty in generating different tokens. This limitation can reduce efficiency, as some tokens are easily predicted, while others may require significant computation. Dynamic draft length policies address this by adjusting the length of the draft sequence based on the difficulty of the tokens. Such policies offer a self-verifying approach, adapting based on the probability of acceptance by the target model. This adaptability leads to substantial speed improvements over methods with fixed draft lengths, maximizing the advantages of speculative decoding without compromising generation quality. The use of entropy, as an indicator of draft token uncertainty, is particularly insightful for controlling the length of draft sequences. It provides a practical, training-free method for optimizing efficiency. The research demonstrates consistent improvements across multiple LLMs and speculative decoding frameworks, proving the effectiveness and general applicability of dynamic draft length policies.

Dynamic Draft Length

#

The concept of “Dynamic Draft Length” in speculative decoding addresses a critical limitation of traditional methods. Fixed-length draft sequences ignore the inherent variability in token generation difficulty. Some tokens are easier for the draft model to predict (e.g., common words, simple phrases), while others are significantly more complex (e.g., knowledge-intensive, reasoning-heavy). A dynamic approach, therefore, allows the model to adapt its draft length based on this difficulty. By considering factors like token entropy or acceptance probability, the model can generate longer drafts for simpler tokens (improving efficiency) and shorter drafts for complex tokens (reducing unnecessary computation). This results in significant improvements in speed and efficiency without compromising the quality of the generated text. The key benefit is a system that is more robust and adapts to different generation tasks, offering better wall-clock speedups compared to approaches relying on fixed-length drafting.

Long-Form Generation

#

The section on “Long-Form Generation” in this research paper is crucial because it tests the scalability and generalizability of the proposed Self-Verification Interval Policy (SVIP) beyond the typical short-sequence tasks. By evaluating SVIP on the generation of sequences up to 8K tokens, the authors move beyond the limitations of previous speculative decoding methods that mostly focus on shorter outputs. This is important because long-form generation poses unique challenges due to increased computational cost and the potential for cumulative errors in draft sequences. The results demonstrate that SVIP not only maintains its effectiveness but also shows an even greater speedup in this scenario, particularly highlighting the advantage of dynamically adapting the draft length according to the inherent difficulty of the tokens. This validates the robustness of SVIP and suggests its wider applicability in various practical applications dealing with the generation of longer text, such as document summarization, story writing, or code generation, where the ability to efficiently produce high-quality long-form content is crucial.

More visual insights

#

More on figures

🔼 This figure displays the relationship between draft model entropy and two key aspects of speculative decoding: the probability of draft tokens being accepted by the target model, and the lengths of accepted draft sequences. The top row shows that lower draft model entropy correlates with higher acceptance probabilities, while the bottom row reveals that lower entropy also corresponds to longer sequences of accepted draft tokens. This visualization underscores the variability in drafting difficulty and motivates the need for a dynamic draft length policy that adapts to varying levels of prediction uncertainty.

read the caption

Figure 2: The correlation between draft model entropy and draft token acceptance probability (top) and lengths of accepted draft seqeunces (bottom).

🔼 Figure 3 presents histograms showing the distribution of the ratio between the cross-entropy (Hq,p) and the draft entropy (Hq) for three different large language models. The cross-entropy measures the dissimilarity between the probability distributions generated by the draft and target language models. The draft entropy quantifies the uncertainty in the draft model’s predictions. The histograms reveal that for the vast majority of tokens, this ratio remains within a narrow range. This key observation supports the paper’s approximation that the cross-entropy (Hq,p) can be estimated efficiently using only the draft entropy (Hq) multiplied by a constant value. This simplification is crucial for the algorithm’s efficiency.

read the caption

Figure 3: Distribution histograms of the entropy ratio Hq,p/Hqsubscript𝐻𝑞𝑝subscript𝐻𝑞H_{q,p}/H_{q}italic_H start_POSTSUBSCRIPT italic_q , italic_p end_POSTSUBSCRIPT / italic_H start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT. For most tokens, this ratio falls into a narrow range, indicating that the cross entropy Hq,psubscript𝐻𝑞𝑝H_{q,p}italic_H start_POSTSUBSCRIPT italic_q , italic_p end_POSTSUBSCRIPT can be approximated by a constant multiplication of the draft entropy Hqsubscript𝐻𝑞H_{q}italic_H start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT.

🔼 Figure 4 illustrates the relationship between the theoretical acceptance probability of draft tokens and their entropy. The figure compares three values: the actual acceptance probability calculated using Equation (2) from the paper; a lower bound on this probability derived from Equation (5), which uses the cross-entropy between the draft and target language models; and an estimated lower bound that simplifies Equation (5) by approximating cross-entropy as a constant multiple of draft model entropy. The tokens are ordered on the x-axis according to their actual acceptance probability, enabling a visual comparison of the actual and estimated probabilities.

read the caption

Figure 4: Comparison between the actual acceptance probability from Equation (2), the acceptance probability lower bound from Equation (5), and the estimated lower bound after approximating the cross entropy Hq,psubscript𝐻𝑞𝑝H_{q,p}italic_H start_POSTSUBSCRIPT italic_q , italic_p end_POSTSUBSCRIPT with a constant multiplication of Hqsubscript𝐻𝑞H_{q}italic_H start_POSTSUBSCRIPT italic_q end_POSTSUBSCRIPT. Each position on the x-axis corresponds to a token, which has been sorted according to the actual acceptance probability.

🔼 Figure 5 presents a comparison of the performance of three different draft length policies (Constant, Heuristics, and SVIP) on the SpecBench benchmark using Qwen-2.5 and LLaMA-3 language models. The top half shows results for Qwen-2.5, while the bottom half shows results for LLaMA-3. For each model and policy, the figure displays three key metrics: the average generated draft length (the average number of tokens generated by the draft model before verification), the average accepted draft length (the average number of tokens accepted by the target model after verification), and the overall acceptance rate (the percentage of draft tokens accepted by the target model). The figure clearly demonstrates that SVIP consistently leads to shorter generated draft lengths and significantly higher acceptance rates compared to both the Constant and Heuristics baselines, thereby indicating its superior efficiency in speculative decoding.

read the caption

Figure 5: The average generated draft length, accepted draft length, and acceptance rate of Qwen2.5 (top) and LLaMA-3 (bottom) on SpecBench. Compared with the two baselines, SVIP leads to a shorter draft length and a much higher acceptance rate.

Full paper

#