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
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
α
Δα
α
Δα
α
Δα
OPT-125M OPT-6.7B
With Replacement
RRS
85.4±0.1
−1.5↓
77.3±0.1
−3.3↓
70.6±0.1
−1.5↓
K-SEQ
85.8±0.1
−1.1↓
78.4±0.1
−2.2↓
71.1±0.1
−0.9↓
αK-SEQ
85.9±0.1
−0.9↓
78.5±0.1
−2.2↓
71.0±0.1
−1.0↓
α∗
86.9±0.1
-
80.7±0.1
-
72.0±0.1
-
Without Replacement
RRS (SS)
88.9±0.1
−0.9↓
81.5±0.1
−2.8↓
75.1±0.1
−1.0↓
Table 1: Acceptance rates of different MDSD methods across various models and tasks. Δα 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.
Figure 1: Comparison of acceptance rate α for different temperatures across datasets.
Figure 2: Comparison of acceptance rate α for different number of drafts across datasets.
Method
# Drafts = 2, # Steps = 4
# Drafts = 4, # Steps = 3
EAGLE default sparse tree
α
Speed
α
Speed
α
Speed
T=0.1
RRS w/ replacement
75.3 ± 0.3
-
78.4 ± 0.3
-
74.7 ± 0.3
-
RRS w/o replacement
79.4 ± 0.3
1.04 ( ± 0.02) ×
80.4 ± 0.3
1.03 ( ± 0.01) ×
76.8 ± 0.3
1.04 ( ± 0.02) ×
SpecHub
84.0 ± 0.3
1.11 ( ± 0.02) ×
-
-
-
-
Greedy
84.7 ± 0.3
1.13 ( ± 0.02) ×
88.8 ± 0.2
1.17 ( ± 0.01) ×
79.1 ± 0.3
1.08 ( ± 0.02) ×
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
Figure 3: Different directions for improving speculative decoding.
Method
# Drafts = 2, # Steps = 4
# Drafts = 4, # Steps = 3
EAGLE default sparse tree
τ
Δ
τ
Δ
τ
Δ
T=0.1
RRS w/ replacement
3.04 ± 0.02
-
2.83 ± 0.02
-
3.19 ± 0.03
-
RRS w/o replacement
3.27 ± 0.02
1.07 ( ± 0.02) ×
2.96 ± 0.02
1.05 ( ± 0.01) ×
3.42 ± 0.03
1.07 ( ± 0.02) ×
SpecHub
3.63 ± 0.02
1.19 ( ± 0.02) ×
-
-
-
-
Greedy
3.62 ± 0.02
1.19 ( ± 0.02) ×
3.39 ± 0.01
1.20 ( ± 0.02) ×
3.70 ± 0.03
1.16 ( ± 0.02) ×
Appendix
Table 3: Average generation length τ of different MDSD methods and their ratio Δ on MT-Bench based on Eagle framework.
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.
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 (SD) accelerates large language model (LLM) inference by using a smaller model to draft future tokens, which are then verified by the target LLM. This preserves generation quality by accepting only aligned tokens. However, individual drafters, often trained for specific tasks or domains, exhibit limited effectiveness across diverse applications. To address this, we introduce MetaSD, a unified framework that integrates multiple drafters into the SD process. MetaSD dynamically allocates computational resources to heterogeneous drafters by leveraging alignment feedback and framing drafter selection as a multi-armed bandit problem. Extensive experiments show MetaSD consistently outperforms single-drafter approaches.
Speculative Decoding (SD) accelerates large language model inference by allowing a lightweight draft model to propose tokens that are subsequently verified in parallel by a larger target model. Recent approaches introduce lossy verification schemes to further improve efficiency by relaxing strict distributional matching. Yet such relaxation silently rewrites the decoding distribution, and the resulting acceleration can come at the cost of unstable, sometimes severely degraded generation quality. In this work, we present a principled analysis of the distributions induced by lossy verification methods. We show that many seemingly distinct approaches differ only superficially and can be classified into two categories: truncation-based verification and collaborative verification. We further construct a diagnostic evaluation framework across curated benchmarks. For truncation-based methods, we identify a fundamental pitfall: performance can degrade significantly compared to the true truncation sampling baseline due to distributional distortion. For collaborative verification, we uncover a key principles: controlling the overshoot of draft probabilities relative to target probabilities is essential to prevent low-quality outputs. Our code is available at https://github.com/ZhouYuxuanYX/Fast-HSD.
Tianyu Wang, Yuxuan Zhou, Wenbin Wang +3
1Independent Researcher · 2Baidu Inc. · 3Zhejiang University