PaSS: Parallel Speculative Sampling

Giovanni Monea, Armand Joulin, Edouard GravearXiv 2023 · DOI · arXiv

Introduction

Large Language Model (LLM) inference is primarily constrained by memory bandwidth rather than raw computation. Standard auto-regressive decoding generates one token at a time, requiring billions of parameters to be loaded from memory for each token produced. This process is inherently inefficient because a single forward pass can process multiple tokens in parallel for nearly the same "time cost" as processing one.

Parallel Speculative Sampling (PaSS) addresses this bottleneck by accelerating LLM inference by up to 30% without the need for a separate "drafter" model. By introducing a few trainable "look-ahead embeddings" to a frozen model, PaSS enables parallel token generation while maintaining output quality identical to standard auto-regressive decoding.

Methodology

PaSS replaces the traditional secondary drafter model used in speculative sampling with a technique called parallel decoding.

  1. Look-ahead Embeddings: A small set of $L$ special tokens, termed "look-ahead embeddings" ([LA]$_1$, [LA]$_2$, etc.), are added to the model's vocabulary.
  2. The Drafting Phase: Instead of generating one token, the model is provided with the prompt followed by these [LA] tokens. In a single forward pass, the model uses these embeddings to "look ahead" and predict the next $L$ tokens simultaneously.
  3. The Validation Phase: The model then performs a second forward pass to validate these draft tokens using a rejection sampling scheme. This ensures that the final output is mathematically identical to what the model would have produced one-by-one.
  4. Minimal Training: The core LLM remains frozen. Only the new look-ahead embeddings are trained on a small dataset to learn how to predict future positions, resulting in a negligible memory overhead of $O(d_{emb})$.

Experimental Setup

The authors evaluated PaSS using a 7B parameter LLaMA model across several benchmarks:

  • Text Completion: Trained and tested on the English Wikipedia dump.
  • Code Completion: Trained and tested on the Python split of The Stack corpus.
  • Quality Benchmarking: The HumanEval dataset was used to ensure that parallel decoding did not degrade the model's coding performance.

Key Results and Insights

PaSS achieves a significant speedup in generation time while remaining "lossless" by design. Because it utilizes the same rejection sampling algorithm as traditional speculative sampling, it produces the exact same distribution as the original model.

Comparison of Auto-regressive vs PaSS performance and generation time.

As shown in Figure 3, PaSS significantly reduces generation time (e.g., from 10.52s to 7.17s for PASS@1) while maintaining performance parity. The approach is highly efficient, requiring only a few thousand additional parameters for a 7B model.

Temperature Sensitivity and Look-ahead Optimization

The efficiency of PaSS is influenced by the model's "temperature." At lower temperatures, where the model is more deterministic, parallel drafts are accepted more frequently, leading to higher speedups.

Impact of temperature and number of look-ahead tokens on generation time.

Figure 4 illustrates that the benefits of PaSS are most pronounced at lower temperatures across different datasets. Additionally, the researchers found that the optimal number of look-ahead tokens is approximately 6. Beyond this point, the accuracy of the drafts drops significantly, and the overhead of processing the longer sequence begins to diminish the returns.

Conclusion

PaSS offers a highly efficient method for accelerating LLM inference with minimal memory overhead. By leveraging the underutilized capacity of forward passes through look-ahead embeddings, it provides a 30% speedup without sacrificing output quality. Future work may focus on increasing the "acceptance rate" of draft tokens and scaling the method to even larger models (70B+) where memory bottlenecks are even more severe.

Summary updated

Abstract

Scaling the size of language models to tens of billions of parameters has led to impressive performance on a wide range of tasks. At generation, these models are used auto-regressively, requiring a forward pass for each generated token, and thus reading the full set of parameters from memory. This memory access forms the primary bottleneck for generation and it worsens as the model size increases. Moreover, executing a forward pass for multiple tokens in parallel often takes nearly the same time as it does for just one token. These two observations lead to the development of speculative sampling, where a second smaller model is used to draft a few tokens, that are then validated or rejected using a single forward pass of the large model. Unfortunately, this method requires two models that share the same tokenizer and thus limits its adoption. As an alternative, we propose to use parallel decoding as a way to draft multiple tokens from a single model with no computational cost, nor the need for a second model. Our approach only requires an additional input token that marks the words that will be generated simultaneously. We show promising performance (up to $30\%$ speed-up) while requiring only as few as $O(d_{emb})$ additional parameters.
BibTeX
@misc{monea2023pass,
  author = {Giovanni Monea and Armand Joulin and Edouard Grave},
  title = {{PaSS: Parallel Speculative Sampling}},
  year = {2023},
  eprint = {2311.13581},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.13581},
}
Figure