Towards Optimal Multi-draft Speculative Decoding

Zhengmian Hu; Tong Zheng; Vignesh Viswanathan; Ziyi Chen; Ryan A. Rossi; Yihan Wu; Dinesh Manocha; Heng Huang

cs.CLFeb 26, 2025

Towards Optimal Multi-draft Speculative Decoding

Authors: Zhengmian Hu, Tong Zheng, Vignesh Viswanathan, Ziyi Chen, Ryan A. Rossi, Yihan Wu, Dinesh Manocha, Heng Huang

Organizations: Department of Computer Science, University of Maryland, College Park, MD, USA · Adobe Research, San Jose, CA, USA · Manning College of Information & Computer Sciences, University of Massachusetts Amherst, MA, USA · Department of Electrical and Computer Engineering, University of Maryland, College Park, MD, USA

Abstract

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.

Figures & tables

Model Pairs	Draft Sampling	Method	Alpaca		CNN-DailyMail		WMT’14
Model Pairs	Draft Sampling	Method	$\alpha$	$\Delta\alpha$	$\alpha$	$\Delta\alpha$	$\alpha$	$\Delta\alpha$
OPT-125M OPT-6.7B	With Replacement	RRS	$85.4\pm 0.1$	$-1.5\downarrow$	$77.3\pm 0.1$	$-3.3\downarrow$	$70.6\pm 0.1$	$-1.5\downarrow$
		K-SEQ	$85.8\pm 0.1$	$-1.1\downarrow$	$78.4\pm 0.1$	$-2.2\downarrow$	$71.1\pm 0.1$	$-0.9\downarrow$
		$\alpha^{\operatorname{K-SEQ}}$	$85.9\pm 0.1$	$-0.9\downarrow$	$78.5\pm 0.1$	$-2.2\downarrow$	$71.0\pm 0.1$	$-1.0\downarrow$
		$\alpha^{\ast}$	$\bm{86.9}\pm 0.1$	-	$\bm{80.7}\pm 0.1$	-	$\bm{72.0}\pm 0.1$	-
	Without Replacement	RRS (SS)	$88.9\pm 0.1$	$-0.9\downarrow$	$81.5\pm 0.1$	$-2.8\downarrow$	$75.1\pm 0.1$	$-1.0\downarrow$

Table 1: Acceptance rates of different MDSD methods across various models and tasks.

\Delta\alpha

means the difference between a verification method and the displayed theoretical upper bound, with statistically significant differences indicated by directional arrows. For RRS (SS), this is a comparison with the CPS optimum, not an optimality gap.

Panel of Figure 1 — Figure 1: Comparison of acceptance rate $\alpha$ for different temperatures across datasets.

Panel of Figure 2 — Figure 2: Comparison of acceptance rate $\alpha$ for different number of drafts across datasets.

Method	# Drafts = 2, # Steps = 4		# Drafts = 4, # Steps = 3		EAGLE default sparse tree
Method	$\alpha$	Speed	$\alpha$	Speed	$\alpha$	Speed
$T=0.1$
RRS w/ replacement	75.3 $\pm$ 0.3	-	78.4 $\pm$ 0.3	-	74.7 $\pm$ 0.3	-
RRS w/o replacement	79.4 $\pm$ 0.3	1.04 ( $\pm$ 0.02) $\times$	80.4 $\pm$ 0.3	1.03 ( $\pm$ 0.01) $\times$	76.8 $\pm$ 0.3	1.04 ( $\pm$ 0.02) $\times$
SpecHub	84.0 $\pm$ 0.3	1.11 ( $\pm$ 0.02) $\times$	-	-	-	-
Greedy	84.7 $\pm$ 0.3	1.13 ( $\pm$ 0.02) $\times$	88.8 $\pm$ 0.2	1.17 ( $\pm$ 0.01) $\times$	79.1 $\pm$ 0.3	1.08 ( $\pm$ 0.02) $\times$

Table 2: Acceptance rates of different MDSD methods on MT-Bench based on Eagle framework.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Different directions for improving speculative decoding.

Method	# Drafts = 2, # Steps = 4		# Drafts = 4, # Steps = 3		EAGLE default sparse tree
Method	$\tau$	$\Delta$	$\tau$	$\Delta$	$\tau$	$\Delta$
$T=0.1$
RRS w/ replacement	3.04 $\pm$ 0.02	-	2.83 $\pm$ 0.02	-	3.19 $\pm$ 0.03	-
RRS w/o replacement	3.27 $\pm$ 0.02	1.07 ( $\pm$ 0.02) $\times$	2.96 $\pm$ 0.02	1.05 ( $\pm$ 0.01) $\times$	3.42 $\pm$ 0.03	1.07 ( $\pm$ 0.02) $\times$
SpecHub	3.63 $\pm$ 0.02	1.19 ( $\pm$ 0.02) $\times$	-	-	-	-
Greedy	3.62 $\pm$ 0.02	1.19 ( $\pm$ 0.02) $\times$	3.39 $\pm$ 0.01	1.20 ( $\pm$ 0.02) $\times$	3.70 $\pm$ 0.03	1.16 ( $\pm$ 0.02) $\times$

Appendix

Table 3: Average generation length

\tau

of different MDSD methods and their ratio

\Delta

on MT-Bench based on Eagle framework.

Speculative Decoding

Speculative decoding accelerates generation by drafting multiple tokens and verifying them in parallel with a larger target model.

See all 331 papers

UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding
May 6, 2026Yepeng Weng, Qiao Hu, Takehisa YairiSpeculative Decoding LLM Inference Acceleration
The University of Tokyo · 2Lenovo AI Technology Center · National Center for Mathematics and Interdisciplinary Sciences (NCMIS), AMSS, CAS
Multi-Drafter Speculative Decoding with Alignment Feedback
Apr 7, 2026Taehyeon Kim, Hojung Jung, Se-Young YunSpeculative Decoding LLM Inference Acceleration
LG AI Research · KAIST AI
Revisiting Lossy Verification in Speculative Decoding: Mechanisms, Trade-offs, and Failure Modes
Jul 29, 2026Tianyu Wang, Yuxuan Zhou, Wenbin Wang +3Speculative Decoding LLM Inference Acceleration
1Independent Researcher · 2Baidu Inc. · 3Zhejiang University

May 6, 2026J/K move · Enter open · S save

UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding

Yepeng Weng, Qiao Hu, Takehisa Yairi

The University of Tokyo · 2Lenovo AI Technology Center · National Center for Mathematics and Interdisciplinary Sciences (NCMIS), AMSS, CAS

Speculative Decoding LLM Inference Acceleration Optimal Transport

Open paper AskPDF arXiv

Speculative decoding accelerates Large Language Models via draft-then-verify, where verification can be framed as an Optimal Transport (OT) problem. Existing approaches typically handle multi-draft and multi-step aspects in isolation, applying either flat OT to single-step drafts or per-token rejection sampling to tree-structured candidates. This separation leaves the joint regime (where multi-step dependencies meet multi-draft branching) poorly optimized, as local verification rules fail to exploit the coupling between horizontal and vertical dimensions of candidate trees. In this paper, we propose a unified perspective that casts tree-based verification as a conditional OT problem. Our key insight is that vertical dependencies can be abstracted through prefix acceptance probabilities, which act as dynamic scaling factors to actively guide horizontal draft selection. Based on this principle, we introduce UniVer, a verification algorithm that jointly optimizes across tree levels by composing local optimal transport plans under prefix constraints. We prove that UniVer remains lossless and achieves the optimal acceptance rate under the proposed conditional framework. Extensive experiments across different tasks and models demonstrate that UniVer improves acceptance length by 4.2% to 8.5% over standard recursive rejection sampling without replacement, while maintaining exact distributional alignment with the target model.

Abstract

Speculative Decoding

Explore similar work

UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding

Multi-Drafter Speculative Decoding with Alignment Feedback

Revisiting Lossy Verification in Speculative Decoding: Mechanisms, Trade-offs, and Failure Modes