# Towards Optimal Multi-draft Speculative Decoding arXiv: https://arxiv.org/abs/2502.18779 ยท HTML: https://mlsanity.com/paper/2502.18779/ ## Key facts - Cited by 19 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 26 of its 37 references that are in the map. - First posted on arXiv 26 Feb 2025. ## Placed in - Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/) ## Builds on (most cited first, 26 of 26) - [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020) - [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023) - [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023) - [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021) - [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022) - [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024) - [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022) - [Teaching Machines to Read and Comprehend](https://mlsanity.com/paper/1506.03340/) (2015) - [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) - [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024) - [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023) - [DistillSpec: Improving Speculative Decoding via Knowledge Distillation](https://mlsanity.com/paper/2310.08461/) (2023) - [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023) - [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023) - [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023) - [Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding](https://mlsanity.com/paper/2402.12374/) (2024) - [TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding](https://mlsanity.com/paper/2404.11912/) (2024) - [Cascade Speculative Drafting for Even Faster LLM Inference](https://mlsanity.com/paper/2312.11462/) (2023) - [Inference with Reference: Lossless Acceleration of Large Language Models](https://mlsanity.com/paper/2304.04487/) (2023) - [PaSS: Parallel Speculative Sampling](https://mlsanity.com/paper/2311.13581/) (2023) - [Multi-Candidate Speculative Decoding](https://mlsanity.com/paper/2401.06706/) (2024) - [Block Verification Accelerates Speculative Decoding](https://mlsanity.com/paper/2403.10444/) (2024) - [Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement](https://mlsanity.com/paper/2402.14160/) (2024) - [Lossless Acceleration of Large Language Model via Adaptive N-gram Parallel Decoding](https://mlsanity.com/paper/2404.08698/) (2024) - [SpecHub: Provable Acceleration to Multi-Draft Speculative Decoding](https://mlsanity.com/paper/2411.05289/) (2024) ## Built on by (most cited first, 19 of 19) - [Speculative Decoding and Beyond: An In-Depth Survey of Techniques](https://mlsanity.com/paper/2502.19732/) (2025) - [Traversal Verification for Speculative Tree Decoding](https://mlsanity.com/paper/2505.12398/) (2025) - [Beyond Decoder-only: Large Language Models Can be Good Encoders for Machine Translation](https://mlsanity.com/paper/2503.06594/) (2025) - [Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs](https://mlsanity.com/paper/2510.20064/) (2025) - [SelfJudge: Faster Speculative Decoding via Self-Supervised Judge Verification](https://mlsanity.com/paper/2510.02329/) (2025) - [Overcoming Joint Intractability with Lossless Hierarchical Speculative Decoding](https://mlsanity.com/paper/2601.05724/) (2026) - [Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization](https://mlsanity.com/paper/2511.15898/) (2025) - [SpecTr-GBV: Multi-Draft Block Verification Accelerating Speculative Decoding](https://mlsanity.com/paper/2604.25925/) (2026) - [Accelerating Diffusion Sampling via Speculative Draft Trees](https://mlsanity.com/paper/2609.17691/) (2026) - [Polybasic Speculative Decoding Through a Theoretical Perspective](https://mlsanity.com/paper/2510.26527/) (2025) - [UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding](https://mlsanity.com/paper/2605.04543/) (2026) - [ResiSpec: Enhancing Multi-Candidate Speculative Sampling via Residual Distribution Shaping](https://mlsanity.com/paper/2608.24411/) (2026) - [RheoSampling: Resolving the One-Hot Dilemma in Stochastic Dynamic-Tree Speculative Decoding](https://mlsanity.com/paper/2609.21827/) (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) - [Reason What Matters: Retrieval-Grounded Reasoning for Universal Multimodal Embeddings](https://mlsanity.com/paper/2609.15296/) (2026) - [Tsubame: Tree Replay for Diffusion-Based Speculative Decoding](https://mlsanity.com/paper/2609.33652/) (2026) - [CAST: Cost-Aware Speculative Trees from One-Pass Block Drafters](https://mlsanity.com/paper/2610.00321/) (2026) - [Rank-Aware Speculative Sampling for Diffusion Draft Trees](https://mlsanity.com/paper/2610.02251/) (2026) ## Abstract (arXiv) Large Language Models (LLMs) have become an indispensable part of natural language processing tasks. However, autoregressive sampling has become an efficiency bottleneck. Multi-Draft Speculative Decoding (MDSD) is a recent approach where, when generating each token, a small draft model generates multiple drafts, and the target LLM verifies them in parallel, ensuring that the final output conforms to the target model distribution. The two main design choices in MDSD are the draft sampling method and the verification algorithm. For a fixed draft sampling method, the optimal acceptance rate is a solution to an optimal transport problem, but the complexity of this problem makes it difficult to solve for the optimal acceptance rate and measure the gap between existing verification algorithms and the theoretical upper bound. This paper discusses the dual of the optimal transport problem, providing a way to efficiently compute the optimal acceptance rate. For the first time, we measure the theoretical upper bound of MDSD efficiency for vocabulary sizes in the thousands and quantify the gap between existing verification algorithms and this bound. We also compare different draft sampling methods based on their optimal acceptance rates. Our results show that the draft sampling method strongly influences the optimal acceptance rate, with sampling without replacement outperforming sampling with replacement. Additionally, existing verification algorithms do not reach the theoretical upper bound for both without replacement and with replacement sampling. Our findings suggest that carefully designed draft sampling methods can potentially improve the optimal acceptance rate and enable the development of verification algorithms that closely match the theoretical upper bound.