Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies

Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies

Speakers: Nadav Timor, Weizmann Institute; Jonathan Mamou; Daniel Korat; Moshe Berchansky; Gaurav Jain; Oren Pereg; Moshe Wasserblat; David Harel

Conference: ICML 2025

YouTube: https://slideslive.com/39043990

Overview

Large Language Model (LLM) inference, particularly the autoregressive decoding process, remains a significant bottleneck in many applications. Each token generation typically requires a full forward pass through the LLM, leading to high latency and limiting throughput. Speculative decoding has emerged as a promising technique to mitigate this, offering substantial speedups while preserving the target model's output distribution, making it a lossless acceleration method. However, a critical practical limitation has historically hindered its widespread adoption: the requirement that the smaller, faster drafter model must share the exact same vocabulary as the larger target model.

This talk, presented by Nadav Timor from the Weizmann Institute and his collaborators, addresses this fundamental challenge by introducing novel speculative decoding algorithms designed to operate effectively with heterogeneous vocabularies. By removing the restrictive shared vocabulary constraint, these innovations unlock the full potential of speculative decoding, allowing practitioners to leverage any off-the-shelf drafter model, thereby eliminating the costly and time-consuming process of training custom drafters from scratch. The work presents a "free lunch" for LLM inference, offering significant performance gains without compromising output quality or requiring specialized model development.

The presented algorithms not only overcome a major practical hurdle but also deliver substantial performance improvements, achieving up to 2.8 times faster inference speeds or higher throughput compared to traditional autoregressive decoding. Crucially, these advancements maintain the lossless property of speculative decoding, ensuring that the generated output remains faithful to the target model's distribution. The impact of this research is already evident, with two of the proposed algorithms integrated as defaults into Hugging Face Transformers, making them readily accessible to thousands of open-source projects and libraries, fundamentally changing how LLM inference can be accelerated in production environments.

Background

▶ Watch: Introduction to speculative decoding and its limitations (0:00)

The core challenge in deploying Large Language Models (LLMs) efficiently lies in their inherent autoregressive decoding nature. During inference, LLMs generate text token by token, where each new token is conditioned on all previously generated tokens. This sequential process necessitates a complete forward pass through the large target model for every single token produced, leading to high computational costs, increased latency, and reduced throughput, especially for long sequences. As LLMs grow in size and complexity, this bottleneck becomes increasingly pronounced, impacting the responsiveness of AI applications from chatbots to code generation.

To combat this, speculative decoding (also known as speculative sampling or lookahead decoding) emerged as an innovative acceleration technique. The fundamental idea behind speculative decoding is to leverage a smaller, faster model—referred to as the drafter model—to "guess" a sequence of future tokens. This process involves two main phases:

1. Drafting: The drafter model runs autoregressively for n steps, generating n speculative "draft" tokens.
2. Verifying: These n draft tokens, along with the preceding context, are then fed into the larger, more accurate target model in a single parallel forward pass. The target model evaluates the probability of each draft token given the full context up to that point. Tokens whose probabilities align sufficiently with the target model's distribution are accepted, while others are rejected, and the process restarts from the last accepted token.

The primary advantage of speculative decoding over other acceleration methods, such as distillation or quantization, is its lossless nature. It guarantees that the sequence of tokens ultimately produced is exactly what the target model would have generated through standard autoregressive decoding, preserving the target model's original probability distribution and output quality. This makes it a highly attractive option for applications where fidelity to the original model is paramount.

However, a major practical limitation has historically constrained the utility of speculative decoding: the requirement for the drafter model to share the exact same vocabulary as the target model. This constraint creates several significant hurdles for practitioners:

• Expensive Drafter Training: Often, a suitable drafter model with the identical vocabulary does not exist, forcing developers to train a smaller model from scratch specifically to serve as a drafter. This is a computationally intensive and time-consuming process.
• Limited Model Family Options: To circumvent custom training, practitioners often resort to using the smallest available model within the same model family as the target model (e.g., a 7B Llama 2 as a drafter for a 70B Llama 2). However, this is not always feasible. Some popular models, such as DeepSeek-V1 or Phi-4, may not have smaller family members. Even when they do, the smallest model might still be too large or slow to provide meaningful acceleration, as observed with distilled versions of R1, Llama 3.1, and Gemma 2.
• Lack of Reusability: The rapid pace of LLM development means new, more capable target models are released frequently. When a practitioner wishes to upgrade their target model, the previously trained or selected drafter model becomes incompatible due to vocabulary mismatch, necessitating the acquisition or training of a new drafter. This cycle leads to significant operational overhead.

The problem, therefore, is how to enable speculative decoding to function effectively and losslessly when the drafter model and the target model possess heterogeneous vocabularies. This talk directly addresses this critical challenge, aiming to democratize speculative decoding by making it accessible with any off-the-shelf drafter, regardless of its vocabulary.

Key Findings

▶ Watch: How to use our algorithms in Hugging Face today (3:00)

The core contribution of this research is the development of a suite of novel algorithms that effectively address and resolve the long-standing limitation of speculative decoding: the requirement for shared vocabularies between the drafter and target models. By tackling the heterogeneous vocabularies problem, the authors have made speculative decoding significantly more flexible, accessible, and cost-effective, without sacrificing its primary advantage of being lossless.

The key findings can be summarized as follows:

• Removal of Shared Vocabulary Constraint: The most significant finding is the successful elimination of the restrictive shared vocabulary requirement for speculative decoding. This breakthrough means that practitioners are no longer compelled to train custom drafters from scratch or to rely solely on smaller models from the same family. Instead, they can utilize any off-the-shelf drafter model, regardless of its specific tokenizer or vocabulary.
• Lossless Acceleration: Despite operating under the more challenging heterogeneous vocabulary setup, the proposed algorithms maintain the lossless property of speculative decoding. This guarantees that the final output generated is precisely what the larger target model would have produced through standard autoregressive decoding, ensuring no degradation in quality or fidelity to the target model's distribution.
• Significant Inference Speedups: The algorithms deliver substantial performance gains, achieving up to 2.8 times faster inference or higher throughput compared to traditional autoregressive decoding. This translates directly to lower latency for real-time applications and greater capacity for high-volume workloads.
• Three Alternative Algorithms: The research introduces three distinct, alternative algorithms to solve the heterogeneous vocabulary problem, each with its own approach and trade-offs:
• A token-level algorithm based on vocabulary pruning and a sampling trick, which has proven highly effective and practical.
• A string-level algorithm that utilizes string exact matching and addresses complexities arising from non-injective tokenizers.
• A generalized speculative decoding algorithm that considers probabilities over string concatenations, offering theoretical improvements but currently facing practical computational challenges.
• Empirical Validation and Practicality: Extensive empirical evaluations across diverse hardware and tasks (including summarization, coding, and long context understanding) confirm the effectiveness and robustness of the algorithms. Notably, the practical utility of these methods is underscored by their adoption as defaults within Hugging Face Transformers, a widely used library, making them immediately available to a vast community of developers.
• Theoretical Guarantees: Beyond empirical success, the authors provide theoretical proofs demonstrating that all proposed algorithms are lossless. They also offer analyses of expected acceptance rates and show that these rates are increased over a natural baseline, providing a strong theoretical foundation for their practical efficacy.
• Ease of Adoption: For practitioners, adopting these advancements is remarkably simple. As demonstrated with Gemma 2 and Vicuna 1, a single line of code change in Hugging Face Transformers can yield significant lossless speedups (e.g., 1.5x) by simply swapping out a same-family drafter for a faster, heterogeneous one. This ease of integration is a critical factor for widespread impact.

In essence, the key findings present a comprehensive solution to a major bottleneck in LLM inference, making speculative decoding a more versatile and universally applicable technique for accelerating large language models while upholding the highest standards of output quality.

Technical Deep Dive

▶ Watch: Algorithm 2: String-level exact matching for verification (4:50)

The core technical innovation presented in this talk lies in overcoming the heterogeneous vocabularies constraint in speculative decoding. Traditionally, speculative decoding relies on the assumption that both the smaller drafter model and the larger target model share an identical tokenizer and vocabulary. This allows for direct comparison of token probabilities and seamless verification. When vocabularies differ, a token generated by the drafter might not exist in the target model's vocabulary, or it might correspond to a different underlying string or meaning, thus breaking the standard verification process. The authors propose three distinct algorithms to solve this problem, each with a different approach to bridging the vocabulary gap.

Algorithm 1: Token-Level Approach with Vocabulary Pruning and Sampling Trick

This algorithm operates directly at the token level, making it the most straightforward and often the most efficient in practice. Its core ideas are:

1. Vocabulary Pruning: When the drafter model proposes a sequence of tokens, the algorithm ensures that only tokens present in the target model's vocabulary are considered or sampled. If the drafter proposes a token that is not in the target vocabulary, it is effectively "pruned" or discarded from consideration. This necessitates mapping the drafter's output probabilities to the target vocabulary space. This can be achieved by zeroing out probabilities for tokens not in the target vocabulary or by re-normalizing probabilities over the intersection of the two vocabularies. The talk implies a direct mechanism to avoid sampling these out-of-vocabulary tokens.
2. Sampling Trick to Boost Acceptance Rate: Simply pruning tokens might lead to lower acceptance rates if many of the drafter's high-probability tokens are outside the target vocabulary. To mitigate this, a "sampling trick" is employed. While the precise details are not explicitly elaborated in the transcript, such tricks often involve:

• Resampling: If an initial draft token is out-of-vocabulary, the drafter might resample from its remaining high-probability tokens that are within the target vocabulary.
• Proactive Bias: During drafting, the drafter's sampling process might be subtly biased towards tokens that are known to be in the target vocabulary, without altering the drafter's underlying distribution too drastically.
• Fallback Mechanism: A robust fallback mechanism when a drafter token cannot be mapped or is deemed unviable, potentially reverting to a single-token autoregressive step or a more conservative selection.

This algorithm is noted to work "pretty well in practice" and has been adopted as the default speculative decoding method in Hugging Face Transformers since February of the current year. Its simplicity and effectiveness make it a strong candidate for general use cases.

Algorithm 2: String-Level Approach with Exact Matching and Common Representation

The second algorithm takes a different approach by using strings as a common representation to bridge the vocabulary gap. This method replaces the standard token-based verification of speculative decoding with string exact matching.

1. String as Common Representation:

• The drafter model generates a sequence of n draft tokens.
• These tokens are then detokenized into a string. This string serves as the common ground between the heterogeneous vocabularies.
• The target model then tokenizes this string using its own tokenizer.
• The verification then proceeds by comparing the target model's generated tokens (or probabilities) against the sequence derived from the string.

1. String Exact Matching Verification: Instead of comparing individual token IDs or their log probabilities directly, the verification process checks if the string generated by the drafter (and then tokenized by the target) matches the string that the target model would produce. This is a stricter form of verification compared to the probabilistic checks in standard speculative decoding.
2. Addressing Non-Injective Tokenization: A significant challenge with string-level approaches is that tokenizers are not always non-injective functions. This means that detokenize(tokenize(string)) might not yield the original string. For example, different token sequences might map to the same string, or a string might be tokenized differently depending on preceding context or tokenizer specifics. This non-injectivity can lead to low acceptance rates, as the target model might not "agree" with the drafter's string representation even if the underlying meaning is similar.
3. Heuristic to Boost Acceptance Rates: To combat the issue of non-injective tokenizers and the strictness of string exact matching, the authors developed a heuristic. While the specific details of this heuristic are not provided, it likely involves:

• Fuzzy Matching: Allowing for minor discrepancies in string representation that don't alter semantic meaning.
• Contextual Re-tokenization: Smarter re-tokenization strategies that account for the target model's preferences.
• Backtracking/Correction: Mechanisms to adjust the string or token sequence if initial exact matching fails but a close alternative exists.

This string-level algorithm also proved effective in practice and became a default in Hugging Face Transformers in October of the previous year. Its primary drawback, as noted by the speaker, is that "string exact matching is a pretty strict verification method compared to the standard verification method of speculative decoding," which can inherently limit acceptance rates.

Algorithm 3: Generalized Speculative Decoding

To address the limitations of Algorithm 2's strict verification, the authors designed a third algorithm focused on provably boosting acceptance rates. This method generalizes the speculative decoding verification process.

1. Generalized Drafter Considering String Concatenations: Instead of just considering probabilities over individual tokens, this algorithm proposes a generalized drafter that considers probabilities over string concatenations or sequences of tokens. In standard speculative decoding, the target model verifies P(t_i | context, t_1...t_{i-1}). A generalized drafter would effectively consider P(string_segment | context), where string_segment corresponds to multiple tokens.
2. Probabilistic String Verification: This approach would allow for a more nuanced verification than strict string exact matching, potentially accepting a sequence if its overall probability as a string segment (or concatenation of tokens) is sufficiently high according to the target model, even if individual token probabilities don't align perfectly. This moves closer to the original probabilistic verification of standard speculative decoding but adapted for heterogeneous vocabularies via a string-level abstraction.

However, the major limitation of this conceptually powerful algorithm is its computational expense. The speaker explicitly states that "it's pretty computationally expensive to compute this generalized drafter so it's impractical with today's vocabularies." This suggests that calculating probabilities over all possible string concatenations or managing such a generalized drafter's state is too demanding for current hardware and vocabulary sizes. The authors suggest that this algorithm might become practical with a redesign of vocabularies in the future.

Theoretical and Empirical Support

All three algorithms are backed by both theoretical and empirical results. Theoretically, they are proven to be lossless, ensuring that the generated output distribution remains identical to that of the target model. The authors also analyzed the expected acceptance rates and demonstrated that their algorithms increase these rates compared to a natural baseline, confirming their efficiency. Empirically, the algorithms achieve up to 2.8x faster inference, validated across various hardware platforms and diverse tasks such as summarization, coding, and long context understanding. The independent evaluation by Hugging Face before merging the algorithms further solidified their effectiveness.

For practical deployment, the choice between Algorithm 1 and Algorithm 2 often depends on the specific model pair and task, requiring empirical testing to determine the optimal configuration, as Algorithm 3 is currently impractical. The token-level approach (Algorithm 1) is generally favored for its simplicity and directness, while the string-level approach (Algorithm 2) offers an alternative when token-level mapping is particularly challenging.

Experimental Setup & Results

▶ Watch: Algorithm 3: Generalized speculative decoding (computationally expensive) (6:00)

The talk highlights the robust empirical validation conducted for the proposed lossless speculative decoding algorithms for heterogeneous vocabularies, demonstrating their effectiveness across various scenarios. While a detailed breakdown of every experimental configuration is not provided in the transcript, the key aspects and headline results are clearly articulated.

Datasets and Tasks

The algorithms were evaluated on a diverse set of natural language processing tasks to ensure broad applicability:

• Summarization: A common LLM application, testing the ability to condense information efficiently.
• Coding: Tasks involving code generation or completion, which often have specific tokenization patterns and require high fidelity.
• Long Context Understanding: Benchmarks designed to test the models' ability to process and generate output based on extended input sequences, where inference speed is particularly critical.

The use of varied tasks suggests that the solutions are generalizable and not limited to specific types of text generation, reinforcing their utility for a wide range of LLM applications.

Baselines

The primary baseline for comparison is traditional autoregressive decoding, where each token is generated sequentially by the target model. This is the standard, unaccelerated method that the speculative decoding algorithms aim to improve upon. The authors also implicitly compare against a "natural baseline" for acceptance rates, indicating that their algorithms achieve higher token acceptance compared to naive heterogeneous vocabulary handling.

Hardware

The algorithms were tested over various hardware, implying evaluations across different GPU types (e.g., NVIDIA A100, H100, etc.) or potentially even different cloud environments or on-premise setups. This demonstrates that the speedups are not specific to a particular hardware configuration but are robust across typical ML inference infrastructure.

Metrics

The key performance metrics focused on were:

• Inference Speed: Quantified as "up to 2.8 times faster" than autoregressive decoding. This directly translates to reduced latency per token or per sequence.
• Throughput: Implied by "higher throughput," meaning more tokens or sequences can be processed per unit of time, which is crucial for large-scale deployments.
• Losslessness: A critical qualitative metric, theoretically proven and empirically confirmed, ensuring the output distribution remains identical to the target model's original distribution. This means the quality of the generated text is preserved, unlike methods that might trade off quality for speed.
• Acceptance Rates: While not given specific numbers, the talk mentions analysis of expected acceptance rates and showing that they "increase acceptance rates over the natural baseline," indicating the efficiency of the drafting and verification process even with heterogeneous vocabularies.

Headline Numbers & Ablations

The most compelling headline number is the up to 2.8x speedup in inference. This is a significant improvement that can drastically reduce operational costs and enhance user experience.

A concrete example of practical performance improvement is provided:

• When using Gemma 2 as the target model and a smaller, faster Vicuna 1 model as the drafter (a classic heterogeneous vocabulary scenario), a 1.5x lossless speedup was observed. This demonstrates that even with a simple setup and a single line of code change in Hugging Face Transformers, substantial benefits are immediately accessible. This specific example highlights the immediate practical value of the research.

Furthermore, the talk mentions that Hugging Face conducted its own independent evaluation of the algorithms before merging them into their library. This independent validation found the algorithms to be "highly effective," providing strong external endorsement of their performance and reliability. The fact that these algorithms are now default in Hugging Face Transformers for speculative decoding is perhaps the strongest testament to their practical success and impact. This signifies that they have met rigorous standards for stability, performance, and correctness within a widely used production framework.

The overall experimental findings underscore that the presented algorithms not only theoretically solve the heterogeneous vocabulary problem but also deliver tangible, significant, and lossless performance enhancements in real-world LLM inference scenarios.

Practical Implications

▶ Watch: Summary: Free, lossless speedups, powering Hugging Face (7:50)

The development of lossless speculative decoding algorithms for heterogeneous vocabularies represents a paradigm shift for LLM inference, offering profound practical implications for a wide array of stakeholders, from individual model builders to large infrastructure teams. The core message is clear: the previously restrictive barrier to entry for speculative decoding has been removed, democratizing access to significant inference speedups.

For Practitioners and Model Builders

• Elimination of Drafter Training: The most immediate and impactful benefit is the complete removal of the need to train a custom drafter model from scratch. Training even a small LLM can be computationally intensive, time-consuming, and expensive. This innovation frees up valuable GPU resources, developer time, and budget, allowing teams to focus on core model development and application logic rather than auxiliary acceleration models.
• Unrestricted Drafter Choice: Practitioners are no longer constrained to selecting drafters from the same model family or struggling to find one with an identical vocabulary. They can now use any off-the-shelf drafter model, regardless of its origin or tokenizer. This flexibility allows for optimal drafter selection based purely on performance characteristics (e.g., smallest size, fastest inference speed, specific architecture) rather than compatibility. For instance, being able to pair a large Gemma 2 model with a fast, lightweight Vicuna 1 drafter, as demonstrated, opens up new avenues for optimization.
• Future-Proofing and Reusability: As new, more powerful target models are released, practitioners can upgrade without fear of rendering their existing drafters obsolete. The ability to reuse an already efficient drafter across different target models, even those with new vocabularies, significantly reduces technical debt and accelerates model deployment cycles.
• Ease of Adoption: The integration of these algorithms as defaults in Hugging Face Transformers is a game-changer. It means that thousands of open-source repositories and libraries, and by extension, countless applications, can benefit from these speedups with minimal effort—often a "single line change" in code. This low barrier to entry ensures rapid and widespread adoption across the ML ecosystem.

For Infrastructure Teams and Deployers

• Lower Latency and Higher Throughput: The demonstrated speedups of up to 2.8x directly translate to more responsive applications (lower latency) and the ability to serve more users or process larger volumes of requests with the same hardware (higher throughput). This is critical for scaling LLM-powered services efficiently.
• Cost Efficiency: By accelerating inference, the algorithms allow for more efficient utilization of existing hardware. This can potentially delay the need for costly hardware upgrades or reduce the operational expenses associated with running LLM inference at scale, especially in cloud environments where compute time is directly billed.
• Simplified Deployment Pipelines: The ability to decouple drafter selection from target model vocabulary simplifies deployment pipelines. Infrastructure teams no longer need to manage complex compatibility matrices between drafters and target models or maintain custom logic for vocabulary alignment.

Tradeoffs and Limitations

While the advantages are substantial, it's important to acknowledge practical tradeoffs and current limitations:

• Algorithm Selection Requires Empirical Testing: For practical use, practitioners need to empirically test whether the token-level algorithm (Algorithm 1) or the string-level algorithm (Algorithm 2) performs better for their specific target model, drafter model, and task. There isn't a universally superior choice between these two.
• Generalized Algorithm Impracticality: The third, generalized speculative decoding algorithm, while theoretically promising for higher acceptance rates, is currently "computationally expensive" and "impractical with today's vocabularies." This means its benefits are not immediately accessible, though it points towards future research directions in vocabulary design.
• Minor Overhead: While the speedups are significant, there is still some minor computational overhead associated with the vocabulary mapping or string conversion involved in these heterogeneous algorithms compared to a perfectly matched shared-vocabulary setup. However, this overhead is clearly outweighed by the benefits of flexibility and reduced training costs.
• Not a Universal Solution for All Bottlenecks: While addressing the autoregressive decoding bottleneck, these algorithms do not inherently solve other LLM inference challenges such as memory consumption (e.g., KV cache growth), which might require orthogonal optimization techniques.

In conclusion, these advancements offer a "free lunch" in LLM inference acceleration. They make speculative decoding a truly versatile and accessible technique, enabling practitioners to achieve substantial speedups, reduce costs, and streamline deployment without compromising the quality or fidelity of their LLM outputs.

Key Takeaways

• Problem Solved: The major limitation of speculative decoding requiring a shared vocabulary between the drafter model and target model has been effectively resolved.
• Lossless Acceleration: The new algorithms enable lossless speculative decoding with heterogeneous vocabularies, guaranteeing that the generated output preserves the target model's original distribution.
• Significant Speedups: Practitioners can achieve up to 2.8 times faster inference or higher throughput compared to traditional autoregressive decoding, leading to lower latency and improved efficiency.
• Enhanced Flexibility and Cost Savings: The ability to use any off-the-shelf drafter model eliminates the need for expensive custom drafter training and allows for greater flexibility in selecting the most efficient drafter.
• Widely Accessible: Two of the developed algorithms, a token-level approach and a string-level approach, are now default in Hugging Face Transformers, making them easily accessible and deployable with minimal code changes.
• Practical Impact: This innovation offers a "free lunch" for LLM inference, significantly reducing operational costs and accelerating deployment for a broad range of AI applications.

About the Speaker(s)

The lead speaker for this presentation is Nadav Timor from the Weizmann Institute. He presented this work alongside his collaborators: Jonathan Mamou, Daniel Korat, Moshe Berchansky, Gaurav Jain, Oren Pereg, Moshe Wasserblat, and David Harel. The team's collective effort from the Weizmann Institute and potentially other affiliated organizations has been instrumental in developing these advanced algorithms for accelerating LLM inference.