Multi-Draft Speculative Sampling: Canonical Architectures and Theoretical Limits

Ashish Khisti, MohammadReza Ebrahimi, Hassan Dbouk, Arash Behboodi, Roland Memisevic, Christos Louizos

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.

The Two-Step Canonical Decomposition of Multi-Draft Speculative Sampling.

As illustrated in Figure 1, the process involves:

  1. 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.
  2. 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).

Performance comparison of the Importance Sampling (IS) scheme against SpecTr and SpecInfer across three benchmarks.

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

Abstract

We consider multi-draft speculative sampling, where the proposal sequences are sampled independently from different draft models. At each step, a token-level draft selection scheme takes a list of valid tokens as input and produces an output token whose distribution matches that of the target model. Previous works have demonstrated that the optimal scheme (which maximizes the probability of accepting one of the input tokens) can be cast as a solution to a linear program. In this work we show that the optimal scheme can be decomposed into a two-step solution: in the first step an importance sampling (IS) type scheme is used to select one intermediate token; in the second step (single-draft) speculative sampling is applied to generate the output token. For the case of two identical draft models we further 1) establish a necessary and sufficient condition on the distributions of the target and draft models for the acceptance probability to equal one and 2) provide an explicit expression for the optimal acceptance probability. Our theoretical analysis also motives a new class of token-level selection schemes based on weighted importance sampling. Our experimental results demonstrate consistent improvements in the achievable block efficiency and token rates over baseline schemes in a number of scenarios.
BibTeX
@inproceedings{khisti2025multi,
  author = {Ashish Khisti and MohammadReza Ebrahimi and Hassan Dbouk and Arash Behboodi and Roland Memisevic and Christos Louizos},
  title = {{Multi-Draft Speculative Sampling: Canonical Architectures and Theoretical Limits}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=N1L5TgtkAw},
}
Figure