Towards Optimal Multi-draft Speculative Decoding
Authors: Zhengmian Hu
Tong Zheng
Vignesh Viswanathan
Ziyi Chen
Ryan A. Rossi
Yihan Wu
Dinesh Manocha
Heng Huang
Venue: ICLR 2025 Poster (2025)
Keywords: speculative sampling
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: we compute maximal acceptance rate for multi-draft speculative decoding

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.

Published as a conference paper at ICLR 2025
TOWARDS OPTIMAL MULTI-DRAFT SPECULATIVE DECODING
Zhengmian Hu 12.x, Tong Zheng Vignesh Viswanathan Ziyi Chen', Ryan A. Rossi" Yihan Wu', Dinesh Manocha Heng Huang'
Department of Computer Science, University of Maryland, College Park, MD, USA 2 "Adobe Research, San Jose, CA, USA
e "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 indispensable part of natural language processing tasks, However, autoregressive sampling has become an ef- ficiency bottleneck. Multi- Speculative Decoding (MDSD) is a recent ap- proach where, when generating each token, small draft model generates mul- tiple 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 solution to an op- timal transport problem, but the complexity this problem makes it difficult to solve for the optimal acceptance rate and measure the gap between existing veri- fication algorithms and the theoretical upper bound. This paper discusses the dual of the optimal transport problem, providing way efficiently compute the op- timal 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 differ- ent 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 replace- ment. 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 potentially improve the optimal acceptance rate and enable the development of verification algorithms that closely match the theoretical upper bound.
INTRODUCTION
Autoregressive language models have achieved state-of-the--rt results in various language tasks (Brown et al. 2020, Touvron et al., 2023), including chatbots (Luo et al.) (022) and code gener- ation (Chen et al. 2021). These models generate outputs by predicting the next token sequentially. However, this autoregressive decoding process leads to significant computational resource require- ments and high latency, posing challenges for user experience and limiting potential applications.
Speculative decoding (Leviathan et al. 2023 Chen et al.) 2023a) has been proposed to address the high inference cost issue. The method uses a small, fast draft model to generate candidate results, which are then verified and corrected by a large, accurate target model to maintain the model output distribution. Compared to other acceleration methods, such as knowledge distillation, model quantization, and model pruning, speculative decoding has the advantage of significantly reducing inference latency without sacrificing quality of the generated content.
"Co-first authors.

---

Published as a conference paper at ICLR 2025
Multi-Drafe Speculative Decoding (MDSD) (Miao al. 2024 Cai al. 2024 Li al. 2024
Spector & Re 2023) is a recent advancement in speculative decoding. When generating each token, the small draft model generates multiple draft tokens instead of a single one, in vanilla speculative decoding. The target LLM verifies these tokens in parallel, ensuring that the final output aligns with the target model's distribution while achieving higher overall acceptance speculative decoding, as the multiple drafts provide better coverage of the target model's possible outputs.
than vanilla
MDSD algorithms have two main design choices: (1) The draft sampling method. Common ap- proaches include sampling with replacement, where each token independently sampled from the draft model output distribution, and sampling without replacement, where the probability of select- ing token is updated after each draw to exclude previously selected tokens. (2) The verification
algorithm design. Examples include Recursive Rejection Sampling (RRS) (Yang et al. 2024b Jeon jet al., 2024), which sequentially verifies the draft tokens, and K-SEQ (Sun et al. 2024e), which designed to improve acceptance rate for sampling with replacement.
The acceptance rate, a measure of MDSD algorithm performance, also depends on these two design choices. Any verification algorithm that guarantees the final output aligns with the target model distribution can be viewed as a transport from the draft tokens' distribution to the target model's s distribution. For a fixed draft sampling method, the optimal verification algorithm is solution an optimal transport problem (Sun et al. 2024e), corresponding to an optimal acceptance rate.
However, the complexity of this optimal transport problem, with the number of variables and con- straints growing exponentially with the number of draft tokens, makes it difficult to find efficient solutions. This difficulty has led to open questions:
(1) For modern LLMs, where the vocabulary size is typically in the thousands, the optimal accep- been computed, the best of our knowledge. Simple linear program (L.P)
tance rate has solvers can only compute the optimal transport for small toy models, making it challenging to mea- sure the optimal acceptance rate in practical scenarios.
(2) Although it is widely known that existing verification algorithms are only approximate solu- tions to the optimal transport problem, the gap between their performance and the theoretical upper bound has never been quantified with respect to real text distribution. Without knowing the optimal acceptance rate, difficult assess how suboptimal these algorithms are.
This paper addresses these two open questions. Our contributions include:
We transform the problem of solving the optimal acceptance rate corresponding to the optimal transport into a subset selection problem by considering the dual the problem and then applying total unimodularity. This provides novel perspective for understanding the efficiency of MDSD.
For certain special cases, we propose efficient methods to solve the subset selection problem by noticing convexity-like structures in the set function. This includes sampling with replacement and sampling without replacement. For the first time, provide practical method to compute the theoretical acceptance rate upper bound of MDSD for a draft distribution.
For the first time, we measure the theoretical upper bound of MDSD efficiency on real text, and the gap of existing verification algorithms. We compare different draft sampling methods through their optimal acceptance rates and observe that sampling without replacement outperforms sam- pling with replacement. We evaluate cxisting verification algorithms, including K-SEQ for with replacement and RRS for without replacement and with replacement sampling, and find that they still have significant gaps from the theoretical upper bound.
We propose novel draft sampling method that greedily selects tigh-probability drafts, with only the last draft being random. In some cases, it achieves an even higher optimal acceptance rate than without replacement. We also propose corresponding verification algorithm that perfectly reaches the theoretical acceptance rate upper bound.
2 PRELIMINARIES
2.1 SPECULATIVE DECODING FOR ACCELERATING LLM INFERENCE
Let E denote the vocabulary set. We have target model Ptarget (-|21, Z2, ... Fm). which is prob- abilistic model that predicts the probability of the next word. Our goal is to sample from this model as the output.
2

---

Published as a conference paper at ICLR 2025
The process of single step Multi-Draft Speculative Decoding is as follows:
"2,,"", 1. For draft model Paratt (-|r,, , -., Fm). sample n draft tokens a01) .... (....((),
2. Compute the probabilities of the target model in parallel: Piarger (- I2,,.., Fm)) Piarget( 1, ..,,..,
.... Im, _(1),, ... (- Im ).)) Due to parallel computation,
this step is not much slower than computing P Pearget (-121, 42 11, F2,,.., Tm) alone.
Run the verification algorithm #m+1 ~ Pverity (-1x(1), .... ..()).
If accepted, for some draft 2(0) we have Im+1 = Z(1), In this case, we can perform another sampling step fm+2 ~ Ptarget (- L2 Imn I( generating two tokens in one step and achieving acceleration.
Speculative Decoding can generate multiple steps, with multiple drafts at each step and all drafts forming a tree. However, we only consider the single-step case this paper. For following analysis, we use p(-) Ptarget (-|21, #2, -... -.:: Fmm) to denote the target distribution and Paraft for distribution of draft tokens.
2.2 SPECULATIVE DECODING WITH A SINGLE DRAFT TOKEN
Informally, the verification algorithm depends on two distributions p and Paraft. and one draft token j ~ Paraft The goal is to output i ~ p such that the objective max P(i = j) is achieved, that is to maximize the probability of random variable to the same as random variable j.
More formally, given p E Ag and Påraft E Ay representing two probability distributions over the space Σ, we seek joint distribution и E [p,, Paraf:) such that the marginal distributions are p and Paraft, respectively, and the objective max Ligr, T (i, is maximized. This forms optimal transport problem. The optimal transport is denoted as "p.Parn E II(p. Pdraft), and the optimal objective function value is a" (p, Pdraft) = Erey Tppparm (i,
The problem can be formulated as an LP by representing the joint distribution as matrix:
max
ΣC,,
C..
S.I.
cw=
- (i) Ci.s 2 20Vi, e E.
(1)
CEREXE
RE
JEZ
iED
The optimal transport has the following closed-form expression
min(p(i), Peraft (i)) (p(t) -prrats (1)+ (Parat p()-)) Eee (
i=
p.paran (i,j) = C
(2)
i
and the optimal objective function value is a" (p, Pdraft)
Σ min(p(i), Paraft (i))
The conditional distribution of given j when (i,j) is denoted as ((bi)) E G(E), where
t (ili) = Σ iEx Tij
Tij
Tijj Pärast (j)
(4)
For the optimal transport, this leads to
P.Paraa (il)) min
n(() Paratt (i) 1) p(j)
i i=
(5)
(p(t)- Parate (0))
Parnn
E.ex (Pdratt (=)-
The basic single-step, single-draft speculative decoding can be improved in two directions. Multi step methods generate a draft sequence. Some improvements (Sun et al. 2024d] Hu & Huang 2024| [un et al. 2024c) in this scenario are discussed in Appendix B33] Our paper focuses on the multi-draft direction, where multiple draft tokens generated at each step.
2.3 MULTI-DRAFT SPECULATIVE DECODING
For i E Σ, define the incidence set A, == (7 E Σ" E [n),ū,= i).
Informally, the verification algorithm depends on two distributions p and Parafu. where Pdraft is now a joint distribution of tokens. Common constructions of Paraft include:
Sampling with replacement: Given a draft model with output distribution q(-), independently sample n times. For i (N1,...,3,, E" have Paraft (7) II (()))
3

---

Published as a conference paper at ICLR 2025
Sampling without replacement: Páraft (i) [Iy= 9 R 1 (ty), where
g(ar)
$ (4.
(x) 1-2 11 1()(
(6)
x .........-11)
Product different draft distributions: Parast (i) IT g,(),)
Given multiple draft tokens objective max P(3j E i = iz) or equivalently max P(i E A,) achieved, that is to maximize the probability of random variable i be the same as one of random variable in (n).
-i,....;n) Pdraft: the goal is output ~ such that the
More formally, given p E As; and Páraft E Ay" representing a probability distribution over the space Σ and a probability distribution E [p Pdraft) such that the marginal distributions are p and Påraft, respectively, and the objective max Eies LiEA. (i, is maximized. The optimal transport is denoted as pp.Parans [I(,, Pdraft), and the optimal objective function value is a' (p, Paraft)
the space Σ", respectively, we seek a joint distribution
Eier: EiE,, "p. (1,
The problem can be formulated as an LP by representing the joint distribution as tensor:
ΣΣ C2ai CEREXE"
max
PED
iE
S.L. Σ
--1=p(1 ViEΣ, Σ
Paraft
vi E l",
NE
RE
0 eie E
The difficulty lies in the exponential number of variables and constraints.
Several approximation have been proposed for the multi-draft speculative decoding problem, includ- ing Recursive Rejection Sampling (RRS) (Yang et al.) 2024b] Jeon et al. (024) and K-SEQ (Sun al. 2024e). RRS recursively verifies the draft tokens, while K-SEQ improves the acceptance rate for sampling with replacement. Due to space constraints, we move the details of these methods (Appendix Aj. other related work (Appendix B and all proofs (Appendix C to the appendix.
3
OPTIMAL ACCEPTANCE RATE AS SUBSET SELECTION PROBLEM
We show that the optimal acceptance rate can be expressed subset selection problem:
a (p, Páraft)
min HCE
Σ p()) Σ
Paraft (
(8)
3.1 DUAL PROBLEM
YEH
iEH
We start from the linear programming formulation 7 and derive an equivalent formulation:
ΣΣ St SEREX
max
REE JE
s.t. Σ S. S p(i) S()
SS.
Vi ES S Paraf (
Vi E 2""
(9)
5 Vi ViE - vi E Σ, A.
Lemma 1. The two formulations and P are equivalent.
This equivalent formulation transforms the transportation problem (Hitchcock 1941 into b-
matching problem, whose dual is a w-vertex cover problem (Schrjjver et al. 2003 (with detailed derivation Appendix C.T.:
min HERE ZERE" Σ Vap(i) +
Σ 2jParan (i)
IEE
(10)
s.t. Vi 2
Vi NE
V: 20 ViEE, 220 0 EI
3.2 TOTAL UNIMODULARITY
The coefficient matrix of the constraints in 10) is totally unimodular (TUM). The first set con- straints forms incidence matrix of bipartite graph, where side of the nodes corresponds to E and the other side corresponds to Σ". There is an edge between and if and only if A. There- fore, it is totally unimodular matrix (Biggs) 1993). The second and third sets of constraints have
4

---

Published as a conference paper at ICLR 2025
coefficient matrices that are identity matrices, with | The concatenation of a TUM matrix and an identity matrix is also TUM (Commoner 1973).
- variables and Σ + | constraints.
Since the right-hand side of the constraints are integers, the dual problem 10 always has integer
optimal solution (Hoffman & Kruskal 2010).
3.3
SUBSET SELECTION FORMULATION
By restricting the variables in (10) to integers, we obtain:
min Jupp(i) + Σ (iPaaa()))
yE2 FE
XEX2
(11)
S.L. + 21
VI 20 WEE,, =20 Vi En.
In the optimal solution, yi and z; will not exceed 1, they can only take values 0 Therefore, the problem can be further simplified as:
min =E (0.1) S
min
Σ
U:p(i))
+
Σ
2:Pdraft (
YE
(12)
s.t. y/ 21
E E,
Define // = {i Ely = 1}. The problem becomes:
min
min (0
Σ
p(i) +
Σ
Pdrrff (i)
ER
iEHl
(13)
s.t. 24 21
vi WiE Hi
The optimal solution for is
1 i UnexAH As i UsEr As
2" (H); =
(14)
Substituting this solution, we obtain the subset selection formulation:
min HCY iEH
Σ p(i)+ +
Σ
Pdraft (7)
(15)
iEUneRy As
Finally, note that
Σ
Paraft (i) +
Σ Parafi (7) 1.
(16)
REUSERUN A
H
This completes the derivation of the subset selection formulation {
COMPUTING OPTIMAL ACCEPTANCE RATE IN SPECIAL CASES
In this section, we discuss how to efficiently compute the optimal acceptance rate for certain special cases of the draft distribution Pdraft- For any function we define the marginal value of an element & with respect to a set H as [xx H) = [(H U (x)) J(H). We also define the following shorthand notations: P(H)= Eien p(i), Q(H) Σie Paraft (i), S(H) P(H) Q(H).
The optimal acceptance rate can be expressed a" (p, Påraft) = 1 minucr f(H).
4.1 q- CONVEX FUNCTIONS
Definition 2 (g-Convex Function), A set function Q 2 + R. is called funccittiioooonn if there exists a function g + Rzo such that for all H Σ and x, y E E H with æ o y. we have
((xHH)
Q (U)))
(17)
(x))
9(v)
Intuitively, we order the elements of arbitrarily and construct a sequence of sets H; by adding elements one by one, then the curve of Q (HH,) against the sum of q values is always convex.
5

---

Published as a conference paper at ICLR 2025
Theorem 3.
For sampling with replacement, the function Q is q-convex function.
Theorem 4. For sampling without replacement, the function Q is a q-convex functonn. funcctionn functions.
Theorem 5. All q-convex functions are supermodular
For both sampling with replacement and without replacement, computing a" a"(p, Påraft) be for- mulated as an unconstrained submodular minimization problem, which has polynomial-time algo- rithms (Iwatal 2008). However, by fully exploiting the properties of g-convex functions, we can solve the problem even faster, as shown in the next section.
4.2 EFFICIENT COMPUTATION
Theorem 6. Suppose that Q a q-convex function, Q monotone increusing, and p(x) 0 for all x E E. For all H c Σ and T, E ) H with x + if A(x) siv) and f(x S 0, then fl H (
p(z)
p(a)
The above theorem requires p(x) > 0. When p(x) = 0, there exists an optimal set H for that contains because Q is monotone increasing.
4.2.1 ALGORITIM
Inspired by Theorem 6 we can compute the optimal acceptance rate efficiently as follows:
1. Find an ordering a of Σ such that 2(01)
p(m) 2 ... 2 p(pp))
p(ap))
Construct sequence of H4 -ol,... 0:).
3. Compute a (p, Paran) = + min, f(H,).
Intuitively, we sort the elements by the ratio of g and p in non-increasing order and then perform a linear search.
4.2.2 COMPLEXITY OF COMPUTING Q AND a*
For sampling with replacement, Q has simple expression Q(H) = (EEE {(x))" The time complexity for computing a" (p, Paraft) is O log [=]) for the sorting step, plus O(EE)) for the linear scan.
For sampling without replacement, we can compute Q(H) W..H based on the coefficient of W..s
generating function Wn.h Coeff,- Gz Coeff,, IIEH (())t) and apply dynamic pro- gramming with recurrence relation W Hu,f(() Wn,H + q(z)W The time complexity is O([E) log Σ) for the sorting step, plus O(n E)) for computing coefficient of generating function with dynamic programming.
A GREEDY APPROACH FOR SELECTING DRAFT TOKENS
In this section, we propose novel method for constructing the draft distribution Paraft and a corre- sponding verification algorithm that achieves the optimal acceptance rate for this distribution.
5.1 DRAFT CONSTRUCTION
Given a draft model output distribution g E Ag, we construct the draft tokens (i,,..., follows:
...,..,, 7n) as
The first n 1 tokens are deterministically set to be the top n - tokens according to the probability in q. i.c., .1,...,ūn_
Top,-1(4). such that q(í))
q(?n-1) and
max4ex) (f.....,, 1) (i) S q(fn-1).
Only the last token 7, randomly sampled from without replacement (i.e., is different from the previous n tokens): 7, q Top, 1(0) I-Σ (6.)
The resulting draft distribution is
Pdraft Top.- (Tx)
21 J Top
(18)
i1.... i * Top, (

---

Published as a conference paper at ICLR 2025
5.2 VERIFICATION ALGORITHM
The corresponding optimal transport problem for this draft distribution is simple because only one draft token is random. We can design verification algorithm that strictly achieves the optimal acceptance rate for this draft distribution (, with unfolded definition in Appendix D):
Greedy p.Parrte
(il?)
p.q 114) (ili))
(19)
Theorem 7, The optimal acceptance rate for the greedy draft distribution is
(p, Påraft) Greedy (p. pdraft)
Σ
p(i)
min(p(i), Top, (i))
(20)
(ETOP=-199)
Our subset selection formulation (
provides a convenient way to prove the above theorem.
5.3 CONNECTION TO SPECHUB
SpecHub (Sun et al. 2024b) a recently proposed MDSD method that is only applicable the case
of n = 2. The draft construction in SpecHub is as follows:
First, sample the first draft token i1.
If Top, (q) is the token with the highest probability in g, then sample the second draft token
i2 without replacement to ensure it is different from i1.
1 * Topı(9 (q) is not the token with the highest probability in g. then deterministically set the second draft token to be the token with the highest probability, i.c., i2 = Top, (4).
The resulting draft distribution is:
g(11) (6)
i2 Top (g)
Prirate (2)
2 1-1
2 = Top, (q)
(21)
otherwise
We note that the greedy method for n is essentially equivalent to SpecHub because both methods ensure that at least one draft token is the token with the highest probability in q. However, the specific draft distributions are different, leading to a simpler verification algorithm for the greedy method.
EXPERIMENTS
The goal of our experiments is to measure the acceptance rates of various MDSD methods on real text distributions and compare them with the theoretical upper bounds. In the previous sections, we analyzed the theoretical acceptance rate a a" Paraft) for three different draft distributions: sam- pling with replacement, sampling without replacement, and greedy approach (Section (5). We also discussed some existing verification methods (Appendix [A), such as RRS and K-SEQ, whose ac- ceptance rates expected be lower than the theoretical upper bound. For K-SEQ, its average acceptance rate a K-SEQ can be derived theoretically (see Appendix A.2 for details). Our efficient computation methods (Section 4 make it possible, for the first time, to obtain the theoretical upper bound of MDSD for vocabulary sizes of thousands.
To obtain realistic distributions p and Päraft. we select real-world datasets for various tasks, includ- ing Alpaca (Taori et al. 2023) for instruction- citructtio-followingg. WMT" 14 De-En (Bojar et al.) 2014) for translation, and Maly (Hermann al. 2015) for summarization. For each task, we use an LLM generate responses on 1024 data samples, with a maximum length of 128 tokens. We then measure the logits of the target model and the draft model on these generated responses to construct p and Paraft.
We evaluated different approaches based on four publicly available large language models, including 1) LLaMA Touvron et al. 2023), 2) Vicuna (Chiang et al. 2023), the instruction fine-tuned version of LLaMA models, 3) OPT (Zhang et al. 2022). and 4) Qwen2 (Yang et al. 2024a). Specifically, for the LLaMA family, model. which is consistent with previous work (Miao et al.) 2024). For the OPT family, we select OPT-6.7B the target model and OPT-125M the draft model. Moreover, for the Vieuna family
select LLaMA-7B
the target model and
as the draft

---

Published as a conference paper at ICLR 2025
Table 1: Acceptance rates of different MDSD methods across various models and tasks, Aa means the gap between a verification method and the theoretical upper bound, with statistically significant differences indicated by directional arrows.
Alpaca
CNN-DailyMai
WMT14
Model Pairs
Draft Sampling
Method
a
a
A
α
A
RRS
85.4
-1. 7..
3.3
70.6 0.1
-15 $
With
K-SEQ
=..8
-1.1 4
78.4
-22 +
71.1
-099 4
Replacement
K-SBQ
85.9
-0.94
0.1
-22 4
7..0
-1.04
OPT-125M OPT-6.7B
xx"
8.1
80.7
72.0
Without
RRS
88.9
-..
815
-28
7..1
-104
Replacement
0.1
84.3
76.0
Verify
90.7 0.1
0.0
84.2
-011
17.0=001
-0.0
Greedy
90.7 0.1
84.3
77.1
RRS
71.6
-1.5
6.1
-22
5.1
-10
With
K-SEQ
7119
-1.1
66.0
-1.5
6..0
-08
Replacement
a K.SEQ
7.1
-1.0
66.2
-13
6..2
-0.6
LLaMA-68M LLaMA-7B
a²'
7..0
67.5
60.8 0.1
Without Replacement
RRS
0.1
-088
70.5
=
0.1
71.8
63.4 0.1
Verify
0.14
-0.1
73.2
0.1
66.1 0.1
0.0
Greedy
a²
0.1
7..1
66.1#00
RRS
6.2
-1.0
5..7
-1.1
32.9 0.2
- -0.2
With
K-SEQ
63.9
-0.5 4
5..
-0.8
33.0 0.2
-0.1
Replacement
K-SBQ
6.1
-0.7
5..1
-0.7
82.9 0.2
0.1
Eagle-0.24B Vicuna-7B
a²
6.1
57.8
$3.1
Without
RRS
70.9
-0.6
6.1
-088
36.9 0.2
0.4
Replacement
a²
0.1
64.2
36.4 0.2
Verify
0.2
-0.2
65.7
001
39.5 0.2
0.1
Greedy
0.1
65.8
39.5
RRS
59.6
-1.0
46.7
-1.6
38.3
0.4
With
K-SEQ
59.9
-0.8
4.1
-1.1
38.3 0.1
-0.4
Replacement
K-SEQ
0.1
-0.7
4.1
-1.0
38.3
-03
Eagle-0.26B Qwen2-7B
6.1
48.
38.7
Without
RRS
68.3
-1.1
5.1
-1.7
43.9
-0.1
Replacement
a²
69.4 1..4+0.11 0.1
54.1 0.1
44.0 0.1
Verify
69.9
0.2
-0.0
54.0
0.0
+
0.1
Greedy
a²
70.0 + 0.1
53.9
45.4
and the Qwen family, select Vicuna-7B-v1.3 and Qwen2-7B-Inntruuc as target models, and use paired draft models provided by EAGEL (Li et al. 2024). with 0.24B parameters and 0.26B parameters, respectively.
Unless otherwise specified, we use default generation temperature 0.7 and draft token number of 3. The total computational cost is less than 50 GPU hours RTXA6000.
6.1 MAIN EXPERIMENT
In the main experiment, we compare the acceptance rates of different MDSD methods across various LLMs and tasks. The results are shown in Table We observe that the existing verify methods, RRS and K-SEQ, still have gaps compared to the theoretical acceptance rate upper bound. Sampling without replacement achieves higher acceptance rates than sampling with replacement, both in terms of the theoretical upper bound and the existing verification algorithms. We can attribute this to the fact that sampling with replacement may lead to duplicate draft tokens, which are less helpful for acceleration. The greedy method obtains the highest acceptance rate. but this is not always the case, as we will see the ablation study below that the greedy method performs worse when the temperature is 1.
8

---

Published as a conference paper at ICLR 2025
Greedy Optimal _
Without Replacement Optimal
With Replacement Optinal With Replacement RRS
K-SEQ Theory K-SEQ
Greedy
Without Replacement RRS
0.75
0.8
8.7
0.6
0.65
0.7
0.1 0.3 0.5 0.7 0.9 Temperatures
0.1
0.3 0.5 0.7
0.9
0.1
0.3 0.5 0.7 Temperatures
0.9
Temperatures
(a) WMT 14 De-En Figure 1: Comparison of acceptance rate for different temperatures across datasets.
(b) CNN-DailyMail
(c) Alpaca
Greedy Optimal Greedy
Without Replacement Optimal
With Replacement Optimal
K-SEQ Theory K-SBQ
Without Replacement RRS
With Replavement RRS
0.9
0.7
0.8
0.3
0.6
0.7
0.6
0.5
10
10
Drafts
Drafts
(c) Alpaca Figure 2: Comparison of acceptance rate for different number of drafts across datasets.
(a) WMT' De-En
(b) CNN-DailyMail
6.2 ABLATION STUDY I: IMPACT OF TEMPERATURE
We study the impact of different temperatures the acceptance rates. The temperature affects the distributions of the target model and the draft model, even if the logits remain unchanged. It also affects the output text during the sampling process, resulting in different responses. Figure T shows the results. We use LLaMA-7B as the target model and LLaMA-68M as the draft model for our ablation studies. We have the following observations:
The impact of temperature is non-monotonic. Moreover, different methods respond differently to
temperature changes.
At low temperatures, all methods fall into categories. The first includes methods that allow duplicate tokens. When T 0, these methods essentially have only one effective draft token, the one with the largest logits the draft model. The second includes methods that prevent duplicate tokens. When 7 = O, these methods always select the top n tokens on the draft model.
The gap between the optimal acceptance rate and acceptance rates for previously existing verifi- cation methods, RRS and K- K-SEQ, gradually increases as the temperature rises.
As temperature increases, the gap between methods with replacement sampling and methods with- out replacement sampling decreases. We can attribute this to the fact that, at high temperatures,
the probability distribution is less concentrated, making with replacement sampling strategies have less probability to generate duplicate tokens.
6.3 ABLATION STUDY II: IMPACT OF NUMBER OF DRAFTS
We investigate the impact of different numbers of drafts the acceptance rates. The results shown in Figure We have the following observations:
As the number of drafts increases, the coverage the target model's possible outputs improves, therefore leading to better acceptance rate. This trend holds for all methods.
The draft sampling strategy significantly impacts the benefits derived from an increase in the number of drafts. Sampling without replacement generally benefit more from increase in drafts compared to sampling with replacement. This is because sampling with replacement can lead to redundant drafts, which do not fully leverage the advantages of increasing the number of drafts.

---

Published as a conference paper at ICLR 2025
Table 2: Acceptance rates different MDSD methods on MT-Bench based Eagle framework.
# Drafts 2, # Steps =4
Drafts = 4, # Steps
EAGLE default sparse tree
Method
Speed
Speed
Speed
= 0.1
RRS w/ replacement
75.3 0.3
78.4 0.3
74.7 1 0.3
RRS w/o replacement
79.4 0.3
1.04 (# 0.02) x
80.4 0.3
1.03 (+
76.8 + 0.3
1.04 (# 0.02)
SpecHub
84.0 + 0.3
1.11 (# 0.02) x
Greedy
84.7 + 0.3
1,13 0.02) x
88.8 0.2
1.17
79.1 + 0.3
1.08 (# 0.02)
0.6
RRS w/ replacement
78.8 + 0.3
84.7 = 0.3
76.2 + 0.3
RRS w/o replacement
82.4 +: 0.3
1.07 (#: 0.02) x
88.6 0.2
1.07 (1 x 77.6 - 0.3 1.05 (# 0.02) x
SpecHub Greedy
82.3 + 0.3
1.02 (# 0.02) x
82.8 1 0.3
1.04 (1: 0.02) x 90.0 0.2
(1.000)) x 78.3 1 0.3
1.01 (1 0.02) x
7= 1.0
RRS replacement
76.7 0.3
83.5 =
72.1 +
RRS w/o replacement
76.4 +
1.00 (- 0.02) x
85.3 = 0.3
1.05 (+: 0.01) x
74.1 + 0.3 1.03 (# 0.02) x
SpecHuu Greedy
79.5 0.3
1.01 0.02) x
79.2 +.3
1.02 0.02)
87.8 0.2 1.08 (+ 0.01) 72.9 + 0.97 0.02)
The gap between the optimal acceptance rate and acceptance rates for previously existing verifi- cation methods, RRS and K-SEQ, gradually increases as the number of drafts rises.
6.4 EVALUATING THE GREEDY SAMPLING METHOD ON GENERATION TASKS
In this section, we evaluate the effectiveness and generation efficiency of the proposed Greedy draft sampling method (Section 5) on real-world generation tasks and compare with other MDSD meth- ods.
We implement the Greedy method within the EAGLE Framework (Li et al. 2024), which supports multi-step MDSD with draft tree structure. We experiment with three types of tree structures: (1) drafts = depths 4; (2) drafts = 4, depths= = 3; and (3) a sparse tree with up to 4 drafts and steps, which is the default setting in EAGLE. We conduct experiments
the MT-Bench dataset (Zheng) ett al. 2023) using Vicuna-7B-v133 (Chiang et al. 2023) as the target model and its corresponding Eagle model with 0.24B parameters the draft model.
presenss the results. As discussed in Section the Greedy method and SpecHub have equal acceptance rates when the number of draft tokens 2. Our experiments confirm this theoretical insight, showing no statistically significant difference between the two methods for any temperature.
The Greedy method demonstrates improved performance at low temperatures. For example, T=0.1, it achieves a higher acceptance rate compared to RRS without replacement, leading to faster generation. However, as the temperature increases, the performance gain of the Greedy method diminishes. This observation is consistent with the ablation study in Figure
CONCLUSION
In this paper, we studied the acceptance rate of Multi-Draft Speculative Decoding (MDSD).
On the theoretical side, we discovered an equivalence between the optimal acceptance rate and subset selection problem. We also provided efficient methods to compute the optimal acceptance rate for common draft distributions.
On the practical side, for the first time, measured the optimal acceptance rate under real text distributions and quantified the gap between existing algorithms and the optimal acceptance rate.
Furthermore, we proposed practical greedy draft construction method that, in some cases, achieves an even higher acceptance rate than sampling without replacement.
We hope that our work will stimulate further research improving the efficiency of large language model inference and make these powerful models more accessible and applicable real-world scenarios.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
This work was partially supported by NSF IIS 2347592, 2348169, DBI 2405416, CCF 2348306,
CNS 2347617.
REFERENCES
Norman Biggs. Algebraic graph theory. Number 67. Cambridge university press, 1993.
Ondřej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Lev- eling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, et al. Findings of the 2014 workshop on statistical machine translation. Proceedings of the ninth workshop on statistical machine translation, pp. 12-58, 2014.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel herbert-Voss,, Gretchen Krueger. Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Fric Sigler, Mateusz. Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Iya Sutskever, and Dario Amodei. Language models few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020.
Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason Lee, Deming Chen, and Tri Dao. Medusa: Simple IIm inference acceleration framework with multiple decoding heads. arXiv preprint arXiv:2401.10774, 2024.
Charlic Chen, Sebastian Borgeaud, Geoffrey Irving, fcan-Baptise Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013/8, 2023a.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained code. arXiv preprint arXiv:2107.03372 2021.
Zhuoming Chen, Avner May, Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and Beidi Chen. Sequoia: Scalable, robust, and hardware-aware speculative decoding. arXiv preprint arXiv:2402.12374 2024.
Ziyi Chen, Xiaocong Yang, Jiacheng Lin, Chenkai Sun, Jie Huang, and Kevin Chen-Chuan Chang. Cascade speculative drafting for even faster I1m inference. arXiv preprint 1114:223 2023b.
Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng. Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, lon Stoica, and Eric P. Xing. Vicuna, March 2023.
Frederic G Commoner. sufficient condition for a matrix to be totally unimodular. Networks, 3(4): 351-365, 1973.
Zhenyu Hc, Zexuan Zhong, Tianle Cai, Jason Lee, and Di He. Rest: Retrieval-basel speculative decoding. arXiv preprint arXiv:2311.08252. 2023,
Karl Moritz Hermann, Tomás Kociský, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. In Twenty-eighth Conference on Neural Information Processing Systems, pp. 1693-1701, 2015.
Frank L Hitchcock. The distribution of a product from several sources to numerous localities. Jour- nal of mathematics and physics, 20(1-4):224-330 1941.
Alan J Hoffman and Joseph B Kruskal. Integral boundary points of convex polyhedra. 50 Years of Integer Programming 1958-2008: From the Early Years the State-of-the-Art, pp. 49-76, 2010.
11

---

Published as a conference paper at ICLR 2025
Zhengmian Hu and Heng Huang. Accelerated speculative sampling based tree monte carlo. In Forty-first International Conference on Machine Learning, 2024.
Satoru Iwata. Submodular function minimization. Mathematical Programming. 112:45-64, 2008.
Wonseok Jeon, Mukul Gagrani, Raghavv Goel, Junyoung Park, Mingu Lee, and Christopher Lott. Recursive speculative decoding: Accelerating IIm inference via sampling without replacement. arXiv preprint arXiv:2402. 14160, 2024.
Ashish J Khisti, Arash Behravesh, Hassan Dbouk, Arash Behboodi, Roland Memisevic, and Chris- tos Louizos. Importance weighted multi-draft speculative sampling, In ICML 2024 Workshop on Theoretical Foundations of Foundation Models, 2024.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286. PMLR, 2023,
Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle: Speculative sampling requires rethinking feature uncertainty. arXiv preprint arXiv:2401. 2024.
Bei Luo, Raymond YK Lau, Chunping Li, and Yain-Whar Si. A critical review of state-of of- late-of-theear the-art chatbot designs and applications. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(11)e 1434, 2022.
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rac Ying Yee Wong, Alan Zhu, Lijie Yang. Xiaoxiang Shi, et al. Specinfer: Accelerating large lan- guage model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3. pp. 932-949, 2024.
Giovanni Monea, Armand Joulin, and Edouard Grave. Pass: Parallel speculative sampling. arXiv preprint arXiv:2311.1358) 2023.
Jie Ou, Yueming Chen, and Wenhong Tian. Lossless acceleration of large language model via adaptive n-gram parallel decoding. arXiv preprint vrXiv:2404.08666 2024.
Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
Benjamin Spector and Chris Re. Accelerating IIm inference with staged speculative decoding. arXiv preprint arXivv2308.. 200.02233, 2023.
Hanshi Sun, Zhuoming Chen, Xinyu Yang, Yuandong Tian, and Beidi Chen. Triforce: Lossless acceleration of long sequence generation with hierarchical speculative decoding. arXiv preprint 2.X1::2404.11912. 2024a.
Ryan Sun, Tianyi Zhou, Xun Chen, and Lichao Sun. SpecHub: Provable acceleration to multi-draft speculative decoding. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceed- ings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 20620- 20641, Miami, Florida, USA. November 2024b. Association for Computational Linguistics. doi: 1148.
18.18653/v 1
Ziteng Sun, Uri Mendlovic, Yaniv Leviathan, Asaf Aharoni, Ahmad Beirami, Jae Hun Ro, and Ananda Theertha Suresh. Block verification accelerates speculative decoding. In Workshop on Efficient Systems for Foundation Models II@ ICML2024, 2024c.
Ziteng Sun, Jae Hun Ro, Ahmad Beirami, and Ananda Theertha Suresh. Optimal block-level draft verification for accelerating speculative decoding. arXiv preprint arXiv:2403. 10444, 2024d.
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36, 2024e.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction -oollooinnn llama model, 2023.
12

---

Published as a conference paper at ICLR 2025
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arX1v:2302.13971, 2023,
An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, et al. Qwen2 technical report. arXiv preprint arXiv:2407.10671 2024a.
Nan Yang, Tao Ge, Liang Wang, Binxing Jiao, Daxin Jiang, Linjun Yang, Rangan Majumder, and Furu Wei. Inference with reference: Lossless acceleration of large language models. arXiv preprint arXiv:2304. 04487, 2023.
Sen Yang, Shujian Huang. Xinyu Dai, and Jiajun Chen. Multi-candidate speculative decoding. arXiv preprint arXiv:2401.067 2024b.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0106. 2022.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang. Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36:46595-46622 2023.
Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Rostamizadeh, Sanjiv Kumar, Jean-François Kagy, and Rishabh Agarwal. Distillspec: Improving speculative decoding via knowledge distillation. arXiv preprint arXiv:2310.08460 2023.
13

---

Published as a conference paper at ICLR 2025
A APPROXIMATE SOLUTIONS
A.1
RECURSIVE REJECTION SAMPLING (RRS)
Yang et (2024b and Jeon et (2244) use the Recursive Rejection Sampling method. Define the
residual distribution Res E Ag for P. E Ay as:
(p(1) g())+
Res P (1) (pe))p(z)
(22)
- - (2)))+
When 9, Res" can be defined as an arbitrary distribution.
For Paraft from sampling with replacement, the RRS algorithm is recursively defined as:
(i P.Pdraae
RRS.W
=RRS,w (il7) P.a
(23)
where
min p(i1)
1)
i= i i i is
RRS. pp2
(i(z)
2(31
(24)
(1
p(h1
RRS,
(ili2.)
7(11)
Res 4.
and
pp.q
-RRS, w (110) = p(i)
(25)
Here i2. denotes the sequence i with the first element removed.
For Paraft from sampling without replacement, the RRS algorithm defined as:
π P-Paran
RRS,
(ili
π P-2
-RSS wo (2lb)
(26)
where
min p(51) g(Es)
1)
= i
RRS. P.9
(1/p)
(27)
p(ds)
RRSS wo
Res Res (i)b2.)
+ i
g(vl)
and
RRSS wo (i)()= = p(i)
(28)
The acceptance rates are denoted as a IRR. (p, Páraft) and a RRtS, (p, Pdraft), respectively.
A.2 K-SEQ
Sun et al. (024e)) proposed the K-SEQ method to verify drafts sampled with replacement. Define
pp-(p) Σ min( p(1) .1))
(29)
IED
and let p be the solution to the equation
1 1 (1 Bp)( p8pa(e)
(30)
The K-SEQ algorithm is defined as:
K-SEQ (ili) =K.SEQ P.Pradi
(31)
where
p(11)
min p(u)
1)
i= 71
(KSSQQ(1)))
# #K-SBQ (z) +
p
(32)
(1))
+ i1
and
p(1) - min (()), p(a)
Pp)())))
KKSBQ (K-SBQ((())
(i)
Spi(pp)
(33)
(1 (1-3po(()))
The acceptance rate is denoted as a K-SRQ (p,, Parat)) 1 (1- Bp.g(p)) which is theoretically guaranteed achieve (1 --))aapproiimation of the optimal acceptance rate.
14

---

Published as a conference paper at ICLR 2025
B RELATED WORKS
B.1 DRAFT MODEL DESIGN
Numerous studies have explored the design of better draft models for speculative decoding. In prin- ciple, any autoregressive probabilistic model can serve as draft model. The simplest approaches in- clude using n-gram models (Ou et al. (024) or document retrieval as draft models (Yang et al.) [2023] He al., 2023). Small transtormer-basee language models have also been employed (Leviathan et al. 2023 Chen et al. 2023a), often with distillation techniques to further increase the overlap between the draft and target models (Zhou et al. 2023).
The design of a good draft model involves a trade-off between its similarity to the target model and its computational complexity. More complex draft models lead higher acceptance rates due to their closer resemblance to the target model, but they also incur higher computational overhead. To achieve a better trade-off, some works have proposed reusing the target model's computational results. For example, Monea et al. (2023) use the original model with "look ahead" tokens, while Cai et al. (2024) add new heads to the last hidden layer of the original model to predict tokens further ahead. [i al. (2024) reuse the last layer hidden state computation of the large model and introduce a new attention layer to predict the next token. [Snn et al. (2024a) employ the target model with a partial key-value cache the draft model.
B.2 MULTI-DRAFT SPECULATIVE DECODING
Many related works on Multi-Drai Speculative Decoding (MDSD) have been introduced other sections. This paper focuses on the single-step Multi-Draft scenario. When MDSD generates mul- tiple steps, with each step involving multiple drafts, forms tree structure. Sequoia (Chen al.] 2024) propose dynamic programming algorithm to search for the optimal tree topology.
As the tree grows deeper, acceptance probability of certain branches decreases. Cascade Spec- ulative Drafting (Chen et al. (023b) addresses this issue by assigning the largest draft model to generate draft tokens at shallower levels, which are more likely to be accepted, and gradually using smaller models to generate drafts for less relevant branches.
Khisti et al. (2024) studied the optimal acceptance rate for special case of sampling with replacement for = 2 drafts, and obtained the following result:
)}
a" (dp.arr
min
Σ p(i) iEH
Σ VEEAH
((s)
+
Σ a(s) iEH
Σ VEEAH
g(s)
(34)
HCY
This is essentially the same result (8) under this special case. However, theory is more general, without any assumption on the draft sampling methods or the number of draft tokens.
B.3 MULTI-STEP SPECULATIVE DECODING
The basic single-step, single-draft speculative decoding, as introduced in Section can be ap- plied to multiple steps, with each step having only one draft and independent verification process (Leviathan et al., 2023) Chen et al. 2023a). However, such an approach of repeatedly applying single-step verification is not optimal for the multi-step scenario. Some works, such as Sun et al. (2024d); Hu & Huang (004)); (Sun et al. (2024c), have designed better verification algorithms specif- ically for the multi-step setting. These algorithms are tailored for the multi-step scenario while re- maining compatible with the single-step case, reducing to the basic speculative sampling algorithm when applied to a draft sequence of length 1.
Multi-step speculative decoding and dulti-draft speculative decoding represent different directions for improvement.
As shown in Figure Sun al. (2024e;; Khisti al. (2044) and our work improve speculative decoding from the mu mulltidee draft perspective. When there is only a single draft, it reduces to the case
in Leviathan al. 2023 Chen al. (2023a). On the other hand, (Snn al. (2024d); Hu & Huang
15

---

Published as a conference paper at ICLR 2025
Speculative Decoding
multi-step
Sun al. (2024d)
Leviathan et al. 20233)
Hu & Huang (2024)
Chen al. (023a)
Sun al. (2024c)
multi-draft
Sun et al. (2024c)
Khisti et al. (2024)
This paper
Figure 3:
Different directions for improving speculative decoding.
Sun al. (2024c) enhance speculative decoding from the multi-step perspective. When there is only a single step, it reduces to the case in Leviiiatnnn et al. (2023); Chen et al. (2023a).
2024
Combining both improvements in the multi-draft and multi-step scenario would be ideal, and could be a direction for future research.
C PROOFS
Proof of Lemma 7 Let (C) and f2(S) denote the objective function values of 7 and 9 respec- tively. Let 11 FC("") and 02 f2(8*) be the optimal objective function values.
First, we show that the optimal solution of (7) is feasible for ( Define S = C for A; and S = 0 for $ A; This solution maintains the objective function value, i.e., f2(S) fi(C)). Therefore, 2/2 = f2(S*) 2 fz(S) = fi(C") = U1.
Next, we show that the optimal solution of (9) feasible for Eieg Si; 0 for i E Σ and Paran (?) Pdrast (i) Σier S 2 for i Σn. We have
Define "r=(i) p(i)
Eiero Paran
R S This solution has larger objective function value, i.e., (C) 2 (i(S). Therefore, = fi(C") 2 (i(C) 2 f2(S*) U2. 02
Eierp" Define C₁₁ S Eien (r
Combining the two parts, we have 11 = U2, which proves the equivalence of the two formulations.
Proof of Theorem For i (fI...., 3.) Σ", we have (r)aft Iī= g(t)). The function Q(H) Eiehn (d)an: (7) represents the probability that all samples drawn with replacement are in the H. Therefore, Q(H) (E q(x))"
Consider the convex function gzz) x=. To prove the q-convexity of Q, it suffices show that for all H C Σ and x, E Σ H with x * y, we have:
- +Q(H)+((z)) (Q(H) + q(x))= Q(x)² (Q(H) + g(x) + -()))"
(35)
((x)
((v)
This can be rewritten as:
(Q((H) + 4(x)) (((())) (Q(H))+((a) +
(36)
q(x)
q(v)
Note that both sides are finite differences of the convex function g. Define Q(x), b Q(x) + q(x), and e = ((x) + q(x) + q(v). It suffices to show that:
g( g(a)
g(c) ((b)
(37)
b
b
This follows directly from the convexity of
16

---

Published as a conference paper at ICLR 2025
Proof of Theorem 4
The function Q(H) Lieh" Pdraft (i) represents the probability that all
samples drawn without replacement are the set H. To handle the more complex case sampling without replacement,
generating functions.
Define the generating function G (t) = Ile + a())t) and the coefficient Wn,
Co (t). Note that Q(H)
Wa.
W.,x
The coefficients satisfy the following recurrence relation:
W Hu( Co GHu(z)())
(38)
Coeffy" G + ((z)(Gn((t
(39)
Wn,H + q(z))
(40)
To prove the g-convexity of Q, it suffices to show that for all H C 2 and y E E \ H with x # y,
we have:
W Wn,no - Wn,H (<)W,.F
S Wn.HUfa.tt W HuRg)
(41)
W,,
Applying the recurrence relation, it suffices to show that:
Wn-1.H S Wn-1,
(42)
Applying the recurrence relation again, it suffices to show that:
S ((x)
(43)
This holds because the coefficients of G are always non-negative, i.e., Wn-2,H 2 0.
Proof of Theorem
It suffices to show that for all H C E and P. EVE E \ H with * y. we have: Q(+|H) S (( H {y))
(44)
By the q-convexity of Q, we have:
((+lH)
Qullu
(45)
((x) (w)
Therefore,
Q(r H) Q(+[H) Q(g g(x) + 43y)
U Q(H)
Q H {z))
(46)
g(z)
q(x) + q(v)
g(v)
Similarly, by symmetry, we can reverse a and y to obtain:
QyiA Q(HU (x, Q(H)
(
(47)
(vv) ((x) q(v)
q(x)
Therefore,
(x
(r,,), - Q(H)
U (1))
(48)
((x)
q(x) 4())
(x))
This implies that:
Q(+ < Qx u
(49)
Proof of Theorem 6
We have:
{(x p(x) Q(+lHH
(50)
p1 q(x) Q(a
<
(51)
p(x) ((x)
17

---

Published as a conference paper at ICLR 2025
Therefore,
[(]
g(x) Q(a
0
(52)
p(x)
p(x) ((x)
By assumption, g(a) p(z) p(y)
g(v)
By the q-convexity of Q, we have 2
Therefore,
{(m)
2(w)
g(v) QQy H U fa+)
((x) (z)
(53)
p(v)
g(v)
p(z) ((x)
follows that:
fly H Hl (x})
9(v) Q() U {x})
(54)
p(y)
p(u) ((v)
[(x((1]
50 0
(55)
p(x)
Proof of Theorem
7
We first prove that the acceptance rate of the greedy method is:
a Greedy (p.Prrftt
(56)
Σ
T ppPaactt (i,
Greedy
(57)
iE iEA
ΣΣ
Greedy P.parrt
(irratt) (i)
(58)
IE TEA,
Σ
Σ
T
Greedy
(il)) Petraft (i)
(59)
iETopa-i(4)) TEA:
Σ
Σ
T.PPacaii (z/2) (drate)) (1)
(60)
Top,,op,... 10) iEA,
Σ
Σ
n p.q
Too, (4) (1lāng9 (00
(61)
iεTop
+
Σ
Greedy P.Parats
(i) (o)(Top)-1(()))))) Top, 1hpp-1100 - (1)
(62)
TE Top, (1)) (4)
Σ
p(i)
(63)
iEToP
Σ
n²a p.g
Topn 100 (oph))g1
(64)
Te>T.Topp (1()
Σ
p(i)+ +
Σ
min(p(i), 9- Top, 164) (i))
(65)
TETOP.
(
TEE (g)
Note that ΣieTop...() min(p(i), Top.- (2) (i) ExE ( min(p(i), O.
Next, we compute the optimal acceptance rate. Note that when Top,- (44 g H, we must have Q(H) 0. When Topn-1(9) C H, we have Q(H) Σieh 9 (1)()1 Therefore,
a" (p. Pdrrat)
(66)
=1 min P(H) Q(H)
(67)
BCE
=1 HCE.st Top, (0)CH
min
Σp(1 p(i) 9 Top, (())
(68)
iCH
The optimal set is H (i Top (4) p()) U Top)-1(g). In this case,
a" (p. Páraft)
(69)
18

---

Published as a conference paper at ICLR 2025
=1
Top,. (i)
Σ
p(i)
(70)
iEToP (9)
min(p(t), Top, (1))
Σ
p(t)
(71)
TETop=-199)
C.I DERIVATION OF THE DUAL PROBLEM We start from the primal problem
O
ΣΣ S
mAx SEREXE
VED IE
s.t. Σ
S S p(i)
EE
E
(72)
Σ
S
Paraft (i)
Vi E .
iE
8 2 0
Vi E Σ" E E, & A;
S 0
We introduce dual variables y/ for each constraint Σieso S S p(1) and 2; for each constraint
Eier S1,3 S Parast (1). The Lagrangian function is:
L(S, ((S, = Σ Σ
SL,
(73)
iEN, PE
+
Σ
yi (p(1)
Σ S.ai)
(74)
3E
+ Σ
(P (1)
Σ S1,)) 1E
(75)
ie
The dual function is:
g(y.2)=
max SEREXE"
L(S, v.2)
S 2 0 -
Vi Σ,i Σ"
(76)
Ei E A
Rearranging the Lagrangian function:
1(S,
Σ (1 yi S
(77)
NESTEE"
Σ
Dip(i)
Σ
PaPrff (
(78)
iEE
For the dual function to be bounded, we must have:
1 1 - - S.
(79)
Therefore, the dual problem is:
min Σ Vip(i) Σ
PiPdrafe (i)
VERE,
1EE
7E
s.t.y/ + 2 2
Vi E E, A
(80)
/ 2
VEE
2 2
This completes the derivation of the dual problem.
19

---

Published as a conference paper at ICLR 2025
D ADDITIONAL ILLUSTRATION
Illustration of single-step draft tokens generation and verification:
Input
(Context)
Draft Model Paran
Generate Drafts
Parallel Computation
Generate Draft Tokens ((1)
Compute Probabilities
())
Punger()
Draft Tokens Probabilities
Verification Algorithm Pverity
Probabilities
Target Model
P Parget
Output Token
Pseudo code for apply multi-draft speculative sampling for multiple steps, with arbitrary tree topol- ogy.
def multi muti.dhaf..spcullavv.ddddii
(prompt, tree topolooy draft model, target_model):
-Dati Speculative Decoding algorithm for accelerating language model inference.
Example free Iree_ topology:
lopollog = =
[0], [1], [2]. [31, # First level: 4 branches
[0,0], [0,1]. [0,2]. [1,0]. [1,1].
[2,0], [2,1]. [3,0]. # Second level
[0,0,0], [0,0,1], [0,0,2], 10,1,0].
[0,1.1], [0,2,0], [0,2,1], [1,0,0]. # Third level Fourth level 10,0.0.0,11 # Fifth level
[0,0,0.0], 10,0,0,1), [0,0,0.2],
1
This is the default EAGLE tree structure where each number represents which draft token to use at each level.
20

---

Published as a conference paper at ICLR 2025
# Initialize dictionaries store drafts and distributions drafts = f}
draft distributions
target distributions = 0
# Generate drafts for each prefix in the tree topology for prefix in [[]] + tree.topology:
children get.children (tree- topology prefix) if not children:
continue # Skip if expandable children paths # Generate drafts and corresponding distributions
# e.g. sampling with/without replacement or Section 5.1
drafts [tuple (prefix )
draft cofffdddsstibbtion. tuple (prefix)]
generate _dw.fttttokeennttt (draft_ prefix)
# Compute probability distributions from larget model for all drafts target-distributions
(tareatiiiinnnntntttneeee (target drafts)
# Start verification and generation process prefix =
while True:
break # End if available drafts if
not in drafts:
# e.g. RRS or K-Seq or Section 5.2 output.token verification(
drafts draft distributions (prefix) ) larget.distributio tuple prefix))
prefix append (oken))
# Return the generated sequence return prefix
def get_children (tree_topology, prefix):
Get all child paths in tree topology that extend the given prefix by token.
Examples:
tree_ = [10]. [1], [0,0], [0,1] [1,0]]
get-children ([], tree-topology) -> [[0], [1]]
get-children ([0], tree.topology -> [[0.0] [0,11]
get children ([1], tree topology)
[[1.0]]
get children ([0,0], tree topology) -> []
return
path for path in tree trpoolopy
if len path)) len (prefix) + and path [: len (prefix)] prefix
]
21

---

Published as a conference paper at ICLR 2025
Unfolded definition of verify algorithm for greedy draft construction.
Greedy (2)0)
"
π1
1(0) (2)1mn)
P-9
p() (0l1-2 1997 {(1))
min
,1)
i in i Top (
9(1)
(1 P(n](1 2 ((9) ((1)
p())
m())
((m))
Cxc(((())1 JoeTo (0) a() (0)
Pbn(11 jeepon ((1)
(p(i)(1 E Top - -()))
(1
$ + in. $ Topp-1 (4)
((,))
2ee -ex(Pte)1-- 100 901) K
(81)
E
SUMMARY OF NOTATIONS
Σ: The vocabulary set
Ag: The probability simplex over vocabulary Σ
[n]: The set I.....n
Pearget( (- [-121, T2,, ..., Fmm): The target model, a probabilistic model that predicts the proba- bility of the next word given the context
Parat (-|21, 22, T2..... mm): The draft model used to generate candidate tokens
Pverity (-10(1) ;.... .(m)): The verification algorithm that selects the final output token from the draft tokens
p(-) = Ptarget( (-121 (2, .2,,,,, Tm)) Shorthand for the target distribution
Pdraft:
The distribution of draft tokens
a E [T,, Pdraft:: A joint distribution with marginal distributions p and Paraft
P.Paran II(p, Pdraft): The optimal transport joint distribution
a (ppattt)t:: The optimal acceptance rate
A = (i E Æッ E [m], 2 a}: The incidence set for token
q()): The shorthand notation of the output distribution of the draft model
q --1 (z)) The probability of token x when sampling without replacement, excluding
previously selected tokens
ResP E As: The residual distribution
π w Th "P:Paraf"
wo, The RRS verification algorithms for with/without replacement sampling
"PPParai"
RRS.w (p. Páraft), RRS, (p. Paraft): Acceptance rates for RRS with/without replacmment
3pa(p): function used in the K-SEQ algorithm
K-SBQ, The K-SEQ verification algorithm
PiParaai
K-SEQ (p, Pdraat): Acceptance rate for the K-SEQ algorithm
P(H)) = EiEN p(i): Sum of target probabilities over set H
Q(H) = Σienn Parat (i): Sum of draft probabilities over set H
J(H) P(H) - QH)): Difference between target and draft probabilities over set H
T Greedy The greedy verification algorithm
"PPPara"'
Greedy (p, Pdratt:: Acceptance rate for the greedy draft sampling method
Czyy Matrix representation of joint distribution
(p(i) Parat Pdra)(i)))+ The positive part of the difference
(t)(): Generating function defined as I + g())))
W Coefficient of (2 in Gt
22

---

Published as a conference paper at ICLR 2025
f(x H): The marginal value of element x with respect H
Topn-1(g): The top n-1 tokens according to probability in
S R Variables in the equivalent LP formulation
y E Dual variables
π (-li): The conditional distribution given j
x,z² Individual elements of the joint distribution matrix
12: The sequence with the first element removed
Hj: Sets constructed by adding elements one by one
An ordering of Σ used in the efficient computation algorithm
Coeff Coefficient of 1 in generating function
F ADDITIONAL EXPERIMENTS
Table 3: Average generation length of different MDSD methods and their ratio A on MT-Beneh based on Eagle framework.
# Drafts 2, Steps =
Drafts 4, # Steps
RAGLE default sparse tree
Method
A
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 (= (=00)) x
3,42 0.03
1.77 (= 0.02) X
Specllub Greedy
3.63 1 0.02
1.19 (1 0.02) x
3.62 0.02
1.19 (# 0.02)
3.39 0.01
1.20 0.02)
3.70 1.16 (#= 0.02) X
T
RRS w/ replacement
0.02
3.11 + 0.01
3.41 + 0.02
RRS w/o replacement
3.52 : 0,02
1.09 0.02)
3.39 = 0.01
(=000) x 3.71 + 0.02
1.09 (= 0.02) x
SpecHub Greedy
3.52 = 0.02
1.09 (= 0.02)
3,52 1 0.02
1.09 (1 0.02) x
3.45 0.01
(1.00) x 3.66 L 0.02
1.07 (1 0.02) x
1==10
RRS w/ replacement
0.02
3,09 0.01
3.22 0.02
RRS w/o replacement
3.22 + 0.02
1.02 (+ 0.02)
3.25 + 0.01
1.05 (= (=00)))
3.43 0.02
1.06 (+ 0.02) x
SpecHub Greedy
3.35 - 0,02
1.07 (= 0.02)
3.33 1: 0.02
1.06 0.02)
3.34 1 0.01
1.08 (1 0.01) x 3.33 1 0.02 1.03 (1 0.02) x
Remark 8. For # Drafts 2, # Steps = 4, and T 0.6, three methods RRS without replacement, SpecHub, and Greedy show similar average generation lengths. After truncating to two decimal places, they appear to be the same. However, they are actually different numbers: 3.51781, 3.51944, 3.51975.
23


Reviews:
[{"review_id": "STvr8WjVlj", "reviewer": "Reviewer_q6tv", "summary": "The paper presents several new results about Multi-Draft Speculative Sampling. \n1. It transforms the problem of computing the optimal acceptance rate into a subset selection problem.\n2. For some cases it provides a practical solution of the problem. This provides a theoretical upper bound on the acceptance rate.\n\nThe authors then measure the theoretical upper bound on some datasets, and measure the gap between the upper bound and previous algorithms on these datasets.\nThey present a greedy algorithm which is able to match the theoretical upper bound in many cases.", "questions": "Do your results extend to trees of drafts in a straightforward way?\n\nI would like to see a comparison to https://openreview.net/forum?id=N1L5TgtkAw", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper makes progress on understanding the acceptance rate of Multi-Draft Speculative Sampling. The authors show a clever transformation of the transportation problem formulation of optimal acceptance rates to a subset selection problem, and then show an algorithm to solve the subset selection if the draft distribution satisfies certain properties. \nThey then propose a new greedy Multi-Draft Speculative Sampling algorithm, which is closer to the optimal acceptance rate on some datasets.\n\nThe results in the paper seem to me to be quite novel and significant.", "weaknesses": "The paper takes a bit of effort to read, partly because of a lot of notation, and partly because of results that may not be familiar to a lot f readers. I am not sure if the authors can do much about this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SU6JVG12gT", "reviewer": "Reviewer_ayAW", "summary": "The paper works on the dual problem of the transport problem of multi-draft speculative decoding and show that the optimal acceptance rate is equivalent to a subset selection problem. Then, the paper provides several methods to compute such rates for commonly used multi-draft proposal methods (sampling with replacement, sampling without replacement). The paper proposes a greedy draft construction method and provides several empirical results that showcase the benefit of the proposed algorithm.", "questions": "N/A.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "It is interesting to see that two existing verification approaches (K-Seq and the widely used RRS) can be unified as solving the same optimal transport problem coresponding to sampling without replacement $p_{draft}$. Therefore, they share the same upper bound. Table 1 shows that for a variety of models and settings, the two methods are close enough to the optimal acceptance rates.\n\nThe proposed \"greedy\" draft generation approach and verification method is an interesting combination of the greedy decoding method and ordinary sampling method.\n\nThe ablation studies are informative with a clear comparison with other baseline methods across different temperature and number of draft tokens.", "weaknesses": "### significance\n\nMuch portion of the paper is dedicated to theoretical derivations of the optimal acceptance rate. However, the description and the development of the proposed algorithm is underplayed. \n\nThe proposed methods deserve a proper name, clear demonstration of the verification algorithm (is the algorithm practical for $n>2 as compared to SpecHub?) and more thorough theoretical and experimental investigations to demonstrate the pros and cons compared with previous algorithms.\n\n\n### clarity \n\nThe clarity of the paper can be significantly improved, including but not restricted to:\n\n(1). In Section 2.2, the informal description of speculative decoding is very confusing. This seems to be a short summary of the formal description below, but it is hard to understand what $\\max P(i=j)$ means before going into the details of the optimal transport problem.\n\n(2). The same problem also applies to Section 2.3, where the informal description of multi-draft speculative decoding is confusing. I would suggest reframing the descriptions and move the examples of $p_{draft}$ after the definition.\n\n(3). Section 3 is dedicated to provide the proof for the subset selection problem (Eq. 8). I would suggest move the proof details to the appendix and optionally write a short proof sketch section that only displays the important idea behind the proof and/or the part of the proof that is needed for the development of the later sections. \n\n(4). The description of Theorem 3 and 4 can be improved. What is the definition of $Q$ and $q$ in these cases? What are the consequences of the special cases (with replacement and without replacement)? \n\n(5). In Table 1, are \"greedy\" and \"verify\" the proposed methods in Section 5.1 and 5.2?\n\n\n----\n\nGiven the above review, I would recommend the authors to further refine the writing and the presentation of the paper and put more efforts into both the theoretical part and the empirical results that supports the proposed algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JUjpczPsgL", "reviewer": "Reviewer_WnL3", "summary": "This paper is concerned with acceptance rate of MDSD in LLMs. Authors derive the dual problem, and then prove it has an integer optimal solution, furthermore, they provide a greedy algorithm that, in some cases, perform better without replacement.", "questions": "You stated that problem (equation 7) is intractable/difficult to solve. What algorithms did you use? modern LP algorithms such as interior point methods are quite capable at handling large problems (with exponential constraints), and recently there have been solvers implemented on GPU (see cuPDLD-C). Your greedy algorithm is another version of coin problem, in order for it to be optimal, the environment has to be canonical (see “Error Bounds and the Applicability of the Greedy Solution to the Coin-Changing Problem,”), I suggest you incorporate that in your proof. You have mentioned theoretical upper bound multiple times, however it is not explicitly defined, is it $\\alpha^*$? I suggest you use Radix sort, which is linear in the size of input, and helps with the overall complexity of your problem.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Paper is mathematically rigorous; it is relatively easy to follow and grasp new concepts. Authors do a good job of highlighting the drawbacks of previous work and offer solutions.", "weaknesses": "Some claims are optimistic, such as \"the upper bound has never been computed before\", I personally refrain from making such certain statements. Some contributions are minor, as an example, deriving the dual of an LP is not a contribution, yet it is claimed to be in the first bullet point of contributions. Although paper is mathematically mature, it borrows a lot from previous publications, in other words, novel theoretical contribution is minor.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uZzSmp8HyN", "reviewer": "Reviewer_DHWn", "summary": "This paper studies the problem of multi-draft speculative decoding (MDSD), where the draft model provides multiple draft tokens for each draft position. The authors first provide a way to compute the optimal acceptance rate. Then, they measure the theoretical upper bound of MDSD with large vocab size and quantify the gap between existing verification algorithms and this bound. Besides, the authors also provide a greedy draft sampling methods to approach the theoretical upper bound of MDSD.", "questions": "1. In the real-world applications of speculative decoding, the acceptance rate of different position is usually not i.i.d. I wonder if this will affects the proposed theory and greedy draft sampling methods.\n2. In Table 1, some results of empirical $\\alpha$ is even higher than the theoretical upper bound. Could you please provide a detailed explanation? \n3. In ablation study 1, the authors show an interesting phenomenon that the impact of temperature is non-monotonic. Different methods consistently show a turn around temperature $T=0.9$. Could you please provide a detailed explanation?\n4. Can proposed greedy draft sampling methods adapt to other retrieval-based speculative decoding methods? (e.g. Lookahead Decoding [1] and REST [2])\n\n[1] Fu, Yichao, et al. \"Break the sequential dependency of llm inference using lookahead decoding.\" arXiv preprint arXiv:2402.02057 (2024).\n\n[2] He, Zhenyu, et al. \"Rest: Retrieval-based speculative decoding.\" arXiv preprint arXiv:2311.08252 (2023).", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The idea of transforming the problem into a subset selection problem and considering the dual of the problem is novel and makes sense. \n2. The authors rigorously give some theoretical findings, including the upper bound of MDSD and a efficient method to compute the theoretical acceptance rate.\n3. The authors propose a greedy draft sampling method and conduct extensive experiments to demonstrate its effectiveness.", "weaknesses": "While this paper provides rigorous theory and analysis, I think there exists some weakness to further improve the manuscript.\n\n1. The motivation and background should be clearly illustrated, and the authors could consider add some intuitive examples and figures to improve the presentation. \n2. Please discuss the connections to the related works. It is confusing for readers without the knowledge about SpecTr. Besides,  please give a clear notation section. For example, the number of draft tokens for each draft position and the number of draft length should be clarified. \n3. Please describe the whole algorithm of the greedy draft sampling method. For example, after constructing the first  $n$ draft tokens for the first draft position, how we can construct the following draft tokens? Besides, this algorithm is similar to the top-k sampling, with only an additional random sampled token. The authors should discuss their difference.\n4. The experiments could be strengthen by evaluating the block-wise mean accepted tokens and real-world speedup. Besides, more experiments with different model scales (e.g. 33B, 70B) and different benchmarks (e.g. MT-Bench [1] and Spec-Bench[2]) are necessary to demonstrate the conclusions.\n\n[1] Zheng, Lianmin, et al. \"Judging llm-as-a-judge with mt-bench and chatbot arena.\" Advances in Neural Information Processing Systems 36 (2023): 46595-46623.\n\n[2] Xia, Heming, et al. \"Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding.\" arXiv preprint arXiv:2401.07851 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)