# Multi-Draft Speculative Sampling: Canonical Decomposition and Theoretical Limits

arXiv: https://arxiv.org/abs/2410.18234 · HTML: https://mlsanity.com/paper/2410.18234/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 24 of its 37 references that are in the map.
- First posted on arXiv 23 Oct 2024.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 24 of 24)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [Fast Transformer Decoding: One Write-Head is All You Need](https://mlsanity.com/paper/1911.02150/) (2019)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [DistillSpec: Improving Speculative Decoding via Knowledge Distillation](https://mlsanity.com/paper/2310.08461/) (2023)
- [Quantizable Transformers: Removing Outliers by Helping Attention Heads Do Nothing](https://mlsanity.com/paper/2306.12929/) (2023)
- [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023)
- [Locally Typical Sampling](https://mlsanity.com/paper/2202.00666/) (2022)
- [Sparse is Enough in Scaling Transformers](https://mlsanity.com/paper/2111.12763/) (2021)
- [Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement](https://mlsanity.com/paper/2402.14160/) (2024)
- [Lossless Acceleration for Seq2seq Generation with Aggressive Decoding](https://mlsanity.com/paper/2205.10350/) (2022)

## Built on by (most cited first, 11 of 11)

- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs](https://mlsanity.com/paper/2510.20064/) (2025)
- [List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression](https://mlsanity.com/paper/2506.05632/) (2025)
- [Trees from Marginals: Autoregressive drafting with factorized priors](https://mlsanity.com/paper/2607.06763/) (2026)
- [Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization](https://mlsanity.com/paper/2511.15898/) (2025)
- [Accelerating Diffusion Sampling via Speculative Draft Trees](https://mlsanity.com/paper/2609.17691/) (2026)
- [UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding](https://mlsanity.com/paper/2605.04543/) (2026)
- [Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling](https://mlsanity.com/paper/2602.16961/) (2026)
- [Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding](https://mlsanity.com/paper/2602.16994/) (2026)
- [Watermarkable Multi-Draft Speculative Sampling via Poisson Processes](https://mlsanity.com/paper/2609.21858/) (2026)
- [Rank-Aware Speculative Sampling for Diffusion Draft Trees](https://mlsanity.com/paper/2610.02251/) (2026)

## Abstract (arXiv)

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.