Introduction
Large Language Models (LLMs) have revolutionized natural language processing but remain computationally expensive during inference. The primary bottleneck is memory bandwidth: generating each token requires moving massive model weights from memory to the processor. Speculative decoding addresses this by using a smaller, faster "draft" model to predict a sequence of tokens, which the larger "target" model then verifies in parallel. While single-draft speculative sampling is well-understood, extending this to multiple drafts—where several candidate sequences are proposed—presents a significant challenge in selecting the optimal token to maximize acceptance probability.
The Challenge of Multi-Draft Sampling
In multi-draft scenarios, the system must choose one token from $K$ candidates generated by the draft model(s). Previous approaches like SpecTr and SpecInfer attempted to solve this, but they often relied on suboptimal heuristics or computationally expensive optimization problems that could negate the speed gains of speculative decoding. This research establishes the theoretical limits of multi-draft sampling and proposes a computationally efficient, optimal selection scheme.
Methodology: The Two-Step Canonical Decomposition
A core contribution of this work is the "Two-Step" theorem, which proves that any optimal multi-draft selection rule can be decomposed into a canonical two-stage process.
As illustrated in Figure 1, the process involves:
- Step 1: Importance Weighted Sampling. A representative token $Y_I$ is selected from the $K$ draft candidates $X_1, \dots, X_K$ using weights $\beta_y$ derived from the draft and target distributions.
- Step 2: Standard Speculative Sampling. The chosen token $Y_I$ is then subjected to standard single-draft speculative sampling against the target model.
To make this mathematically optimal approach practical for real-time inference, the authors introduced Truncated Linear Programming (LP). Instead of optimizing over the entire vocabulary (often 50,000+ tokens), the algorithm focuses on the top $s$ most likely tokens. This truncation maintains near-optimal performance while drastically reducing computational overhead.
Empirical Evaluation and Results
The proposed Importance Sampling (IS) scheme was evaluated using the OPT model family (125M draft, 13B target) across three benchmarks: Databricks-Dolly-15k (instruction following), XSum (summarization), and WMT18 (translation).
As shown in Figure 5, the IS scheme consistently outperforms existing methods:
- Block Efficiency: The IS scheme achieved higher average tokens accepted per step (e.g., ~2.48 on Dolly) compared to SpecTr (~2.43) and SpecInfer (~2.38).
- Token Rate Improvement: Unlike some multi-draft methods that can actually slow down inference due to complexity, the IS scheme provided a 5% to 10% improvement in actual token rate over single-draft baselines.
- Robustness: The method proved robust across different sampling temperatures, maintaining its advantage even as the randomness of the draft model varied.
Conclusion
By establishing the theoretical limits and a canonical architecture for multi-draft speculative sampling, this work provides a rigorous foundation for accelerating LLM inference. The proposed IS scheme with Truncated LP offers a practical path to achieving higher throughput without sacrificing mathematical optimality. Future research may extend these proofs to non-independent (tree-based) drafts and further optimize hardware implementations for production environments.
Summary updated