Sequoia: Scalable and Robust Speculative Decoding
Authors: Zhuoming Chen
Avner May
Ruslan Svirschevski
Yu-Hsun Huang
Max Ryabinin
Zhihao Jia
Beidi Chen
Venue: NeurIPS 2024 spotlight (2024)
Keywords: LLM inference; Speculative Decoding
Primary area: natural_language_processing
TL;DR: Accelerate LLM inference with a scalable and robust tree based speculative decoding algorithm

Abstract: As the usage of large language models (LLMs) grows, it becomes increasingly important to serve them quickly and efficiently. While speculative decoding has recently emerged as a promising direction for accelerating LLM serving, existing methods are limited in their ability to scale to larger speculation budgets and adapt to different hyperparameters. This paper introduces Sequoia, a scalable and robust algorithm for speculative decoding. To improve scalability, Sequoia introduces a dynamic programming algorithm to find an optimal tree structure for the speculated tokens. To achieve robust speculative decoding, Sequoia uses a novel sampling and verification method that outperforms prior work across different decoding temperatures. Sequoia improves the decoding speed of Llama2-7B, Llama2-13B, and Vicuna-33B on an A100 GPU by up to $4.04\times$, $3.73\times$, and $2.27 \times$. To serve Llama3-70B-Instruct on a single L40 GPU through offloading, Sequoia reduces the per-token decoding latency to 0.60 s/token, $9.5\times$ faster than DeepSpeed-Zero-Inference.

SEQUOIA: Scalable and Robust Speculative Decoding
Zhuoming Chen'
Avner May?
Ruslan Svirschevski
Yuhsun Huang' Max Ryabinin
Zhihao Jia'
Beidi Chen 1,5 "Yandex
Carneeii Mellon University
Together AI
National Research University Higher School of Economics FAIR, Meta
zhuominc@andres cmu edu, Svoer ai, rww.ansv@gmail.comm yuhsunhGandrew. cmu edu, mryabStogether ai, {zhihaoj2, beidicc cmu edu
Abstract
As the usage of large language models (LLMs) grows, becomes increasingly important to serve them quickly and efficiently. While speculative decoding has recently emerged a promising direction for accelerating LLM serving, existing methods are limited in their ability to scale to larger speculation budgets and adapt different hyperparameters. This paper introduces SEQUOIA, scalable and robust algorithm for speculative decoding. To improve scalability, SEQUOIA introduces a dynamic programming algorithm to find an optimal tree structure for the speculated tokens. To achieve robust speculative decoding, SEQUOIA uses novel sampling and verification method that outperforms prior work across different decoding tem- peratures. SEQUOLA improves the decoding speed of Llama2-71B Llama2-133 1-BB, and Vicuna-33B on an A 100 GPU by up to 4.04x, 3.73 and 2.27x. To serve Llama3- 70B-Instruct a single L40 GPU through offloading, SEQUOIA reduces the per- token decoding latency to 0.60 s/token, 9.5x faster than
The code is available at pepetps//ggihhe httpttth..oooooeeeeooooottottttt -
Introduction
As large language models (LLMs) gain widespread adoption 3 7), efficiently serving these LLMs becomes increasingly important. However, accelerating LLM inference is challenging since generating single new token requires accessing all parameters of the LLM (34). As result of this I/O bottleneck, the hardware is poorly utilized during generation. This problem is exacerbated both small-batch and offloading--aa bradddd inference settings, where generating one token takes much time as processing a prompt with hundreds thousands tokens on modern GPUs.
To address this challenge, recent work has introduced speculative decoding to accelerate L.LM inference while preserving the L.M''s output distribution (24.
5 28 40) These approaches leverage one or multiple draft models to predict the L.M''s output; the predictions are organized in token tree, whose nodes represent different sequences of speculated tokens. The correctness of these speculated tokens is then verified in parallel through a single forward pass of the LLM. Using a token tree-insteea of sequence- increase the number of tokens accepted by the LLM by providing several options for each token position.
we see our ex- periments that they have couple of limitations. First. observe that existing token tree construction al- gorithms perform well for small token trees but are sub-optimal for large tree sizes. For example, SpecIn- fer constructs a token tree using & independent sequences, topology that is bounded by the expected number of tokens it can accept, regardless of the tree size (Figure []. Second, we observe that existing token tree sampling and verification algorithms are unable to perform well across inference hyperparam-
While there are substantial studies on tree-based speculative decoding methods 28
"Equal contribution
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

V100
1
H100
Offloading Futue
Inpe: tokens
Speculated tokens
Sequoia touns)
10
sequances
Single sequence of tokees
Binary
(d) k independent sequences of lokens
of
107
10
102
107
10
Size
(6)
(c) Full ls ary tree of tokens
Optimal tree tapology (Sequoia)
Figure 1: SEQUOIA is a scalable method for speculative decoding. Left: SEQUOIA tree construction algorithm is able to generate trees whose average number of generated tokens (after verification) continues grow with the tree size while existing tree structures asymptote. This allows SEQUOIA to perform much better than existing methods in very memory- -bound regimes like offloading. Right: A visualization to contrast SEQUOIA tree structure with other common handerafted ones.
eter configurations; for example, SpecInfer [28] and SpecTrr [40) often perform poorly at low temper- atures (Figure 3 since they can repeatedly sample an incorrect token with high draft model probability,
In this paper, we aim to answer the following research question: how tree-based speculative decoding method to maximize speedups on modern hardware? ? Realizing this goal requires addressing several technical challenges. First, for any tree size and depth, we must be able to efficiently search the exponentially large space of tree topologies to find the one that maximizes the expected number of generated tokens. Second, must design tree sampling and verification procedure that performs well across inference hyperparameters, avoids repeatedly sampling incorrect tokens, and maintains the correct output distribution.
design optimal
This paper introduces SEQUOIA, a scalable and robust speculative decoding algorithm. As shown in Figure SEQUOIA can attain up to 9.5x speedups over incremental decoding and introduces several key techniques address the aforementioned challenges.
In Section 3.1 to solve the first challenge, formulate tree construction
constrained optimization problem and employ a dynamic programming algorithm to discover the optimal speculative token tree. Theoretically and empirically, demonstrate that the number of tokens generated with this tree structure is unbounded, growing roughly logarithmically with the tree's ' size.
In Section 3.2 to address the second challenge, we build upon the SpecInfer (28 algorithm by performing sampling without replacement from the draft mtdel-thereby preventing the draft model from making the same mistake twice, while maintaining the target model's 's output distribution. We prove that this new sampling and verification method can attain high acceptance rates at both high and low temperatures and validate this claim empirically.
In Section 4 we perform extensive end-to-end experiments and ablation studies to demonstrate the effectiveness of SEQUOIA. We implement SEQUOIA on top of Hugging Face (45] with CUDA We show that SEQUOIA achieves up to 4.04x speedup for Llama2-7B on a single A100 GPU and 9.5x for L Ionttsruu in the offloading setting on an L40 GPU. The latency of Llama3 Instruct offloading on L40 can be reduced to 0.60 s/token with SEQUOIA while the Seeeppppee---eo-Ineeeeeee
Graphs B1 32
2 is 5.7 s/token. We also present ablation studies to show that: (1) the SEQUOIA tree structure can generate up 33% more tokens per decoding step compared to & independent sequences (tree size < 512), demonstrating better scalability; (2) the SEQUOIA sampling and verification algorithm is robust to the choice of hyperparameters (temperature, top-p), providing to 65% and 27% speedup compared to SpecInfer and top-k sampling and verification algorithms, respectively.
inference speed of state-offthhe-a offloading system
2 Background
Here, we review tree-based speculative decoding methods. In particular, we discuss the way existing methods choose the speculated tree structure (Section 2.T and the algorithms they use to sample and verify the token trees (Section 2.2

---

2.1 Tree construction
The primary tree structure used by existing methods one composed of independent sequences of lenghh L that branch from the tree root (which corresponds to the current prefix). The SpecTr paper additionally considers arbitrary branching patterss (k, (k)....k,) but says that this did not perform better in their experiments than independent sequences. Medusa constructs full k-ary tree, which increases the success rate at each layer but cannot form a deep tree under moderate token budgets
2.2 Tree sampling and verification
We now review how SpecInfer (28). Spec [40], naive sampling (28), and top-k sampling perform token tree sampling and verification. With regard to sampling, SpecInfer. SpecTr, and naive sampling all perform i.i.d. sampling with replacement from the draft model, while top-k sampling selects the top-k highest probability tokens from the draft model. In terms of verification, SpecInfer and SpecTr compare the draft and target model probabilities for the sampled tokens to decide which (if any) to accept; naive and top-k sampling, on the other hand, sample a token from the target model distribution and accept it if it corresponds to one of the tokens from the speculated tree. These methods all verify a speculated token tree in a recursive manner- starting at the root of the tree tree-differng only in the verification algorithm they apply at each node.
The SpecInfer method iteratively verifies tokens that were sampled from one or more draft models. Like the original speculative decoding method (24, it compares the draft model probabilities to those from the target model to decide if to accept. Note that while the SpecInfer method allows sampling from k different draft models to generate &o children for a node, in this work we consider the more common setting where only one draft model is available. Therefore, compare with the version of SpecInfer which samples from a single draft model & times instead. To pseudocode for SpecInfer, please see Igorithm@aand ignore all blue lines (lines 10-16).
SpecInfer:
SpecTTr: The SpecTr algorithm is similar in spirit to the SpecInfer algorithm. It iterates through the children of a node, and uses sampling procedure to decide if accept child, in such a way that the out- put distribution is unchanged. One important property of this algorithm is that it is within a factor of (1 - 1/e) of the best possible verification algorithm (i.e., the one with highest possible acceptance rate). For brevity, we refer readers to Algorithm 3 in the SpecTr paper for the exact pseudocode for this algorithm.
Naive sampling and top-k sampling: Given a node in a token tree, the verification algorithm for naive sampling and top-k sampling first samples from the kargel model's distribution P(: |/(n)) that node, and then accepts this sample if it is equal to one of the children of that node. This verification algorithm trivially maintains the target model output distribution -erarrdlonnrrgarrllles regardless of how the token tree
was generated- given that one always samples from the target model in this algorithm (as opposed to from the draft model, like in SpecTr and SpecInfer). This observation motivates our choice-for the top-k sampling method to populate the tree by taking the top-k children of each node, instead of the naive sampling approach of taking is i.i.d. samples (with replacement). We use the top-k sampling method in our experiments in Section 3.2 to better understand the limits of this verification algorithm.
3 SEQUOIA
We now present SEQUOIA, a scalable and robust speculative decoding algorithm.
Section 3.1 we present our scalable tree construction algorithm, which uses dynamic programming to solve for the optimal tree structure. We demonstrate both theoretically and empirically that the number of tokens generated by verifying SEQUOIA trees scales nearly logarithmically in the size of the tree, while existing tree structures asymptote in the number of tokens they can generate.
In Section 3.2, we present our robust tree verification algorithm, which modifies the SpecInfer algorithm by sampling without replacement from the draft model. We show both theoretically and empirically that SEQUOIA is robust, performing well across temperature values, while existing verification methods are not.
3.1 Tree construction
We now present the SEQUOIA tree construction algorithm (Section 3.1.1 and prove that the expected number of tokens generated when verifying for these trees scales well with the tree size (Section 3.1.2) 1.2.2)
Top-k sampling improved version of naive sampling which we introduce as baseline in this work.
3

---

3.1.1 Algorithm
To derive the SEQUOIA construction algorithm, we expstex the tree construc- tion problem
Treo 41
constrained optimization problem, and then use dynamic program- ming to solve this problem optimally and efficiently. In this optimization problem, we aim to maximize the expected num- ber of tokens F(T) generated by verify- ing a token tree T, under a constraint on the size of T. We begin by presenting closed form expression for ((T (Proposi- t.4...4p. We then present our tree construc- tion algorithm, which uses dynamic pro- gramming to find the tree of size which maximizes this expression (for any value of the speculation budget n.).
Tree #2
Recursive sub-strue structr use by the dy- namic programming algorithm. Right: Real example of SEQUOIA of size 64, and maximum depth 12. We present more examples of SEQUOIA trees in Figure 5 in Appendix
Figure 2: Left:
We first present number of important definitions:
Definition 3.1. Under the positional acceptance assumption, the probability of a verification algorithm accepting a token & which the ktth child of an already accepted token depends only on the value Definition 3.2. The acceptance vector the vector p (21.P2,... .... pk that the verification algorithm accepts a token at child position k. Under the positional acceptance assumption, the acceptance dynamics of verification algorithm can be completely described by the acceptance vector.
.k....) ................................
containing the probabilities
Definition 3.3. Given an acceptance vector p and a tree T, we define the score function f() for a node
T f(v)= = II Pt- where Path(v) (v) is equal to the list of child indices along the path from the iEPath(p)
root node V For example, if v is the 3rd child of the root's 2nd child, then Path (2))= We define [[root)=1.
We are now ready to present Proposition 3.4 (proof in Appendix F.1.2), which shows the closed form equation for the expected number tokens generated by verifying a token tree T, under the positional acceptance assumption. This is the equation which our SEQUOIA dynamic program will optimize.
Proposition 3.4. Let T be token tree that is verified with the positional acceptance assumption, and let fv) denote the score function for node v T. Then the the expected number of tokens F(T) generated by verifying T equals
F(T) - Σt(o) VET
SEQUOIA Dynamic Programing Algorithm. The SEQUOIA tree construction algorithm finds the tree T of size N which maximizes F(T), using dynamic programming. Our algorithm works by iteratively filling the following 2-dimension tensor T:
max T(n, b) T. T.,, FirstBranch()==b
F(T), YOEnEN,Osbsn
(1)
Here, FirstBranch(T) denotes the number of direct children the root of T has, and denotes an upper bound we impose on the number of direct children any node in the tree can have (we can let B B- -N N to make this constraint vacuous). Given the tensor T, the maximum expected number generated tokens for any tree of size < N can be found by searching over all possible first-branch values b: maxoga5n B T [n, b).
We now show how to iteratively fill in the tensor T (which we initialize to negative oo). Pseudocode for the full dynamic programming method is shown in Algorithm []
As the base case, we set [1.0] = 1, representing the tree composed of just the root node, because 1 token generated per iteration of speculative decoding when no tokens are speculated.
For the recursive case, we can consider the tree composed of the root node and its first h- children and their descendants (tree #1), well as the tree whose root is the last child of the root node and

---

its descendants (tree #2). Letting m 2 denote the number of nodes in tree #2, we can see that the expected number of generated tokens for tree #1 Trn-nnnnn b-11 1]. Furthermore, the expected number of generated tokens for tree #2 is maxogisB T(m, j]. but this sub-tree is only considered in the case where the 8th child of the primary root node is accepted (which happens with probability P(b)). Therefore, we can compute n, b] by searching over all possible sizes m for tree #2 to find the one which maximizes the expected number of generated tokens for the full tree:
[Tnn-
T Tnn b) max 1-m5n-1
m, b P[b] max 0SJSB
T(m, j1)
We show in Appendix F.1.1 that by keeping track of the values of m and that maximize the max expres- sions on lines and 11, we can easily reconstruct the optimal tree size N (and FirstBranch (T) S B) that attains the maximum expected number of generated tokens. We additionally demonstrate in this appendix (with python implementation) that we can extend this algorithm in a couple important ways:
Bounded tree-depth: Because the amount of time it takes to speculate a token tree is proportional the depth of the tree, it can be very beneficial to find the tree of depth D that maximizes the expected number of generated tokens. We demonstrate in Algorithm 4 that we can extend the SEQUOIA dynamic program to find the optimal tree of bounded depth.
Compatibility with self-speculation: For self-speculation methods like Medusa 4 Eagle [25), and GLIDE (I]] which leverage the target model's representations on the current prefix during decoding, the acceptance rates can meaningfully degrade as you get deeper into the speculation tree (i.e., further away from the current prefix). We demonstrate in Algorithm[4tha it is simple to extend our SEQUOIA dynamic program to take input 2-D acceptance rate matrix (instead of a 1-D vector) containing the average acceptance rate vectors at different tree depths. Thus, SEQUOIA is compatible with the latest ad advances in self-speculation methods, which can attain meaningfully higher acceptance rates than "standalone" draft models.
This algorithm can be run offline, and thus does not slow down inference.
Algorithm 1 SEQUOIA Dynamic program
1: Input: N for the maximum tree size, B for the maximum number of branches of any node. P[1], P(2).... P[B] for the probability of acceptance for each branch.
2: Output: [m,
4 0 < < N, 0 < b s B.
3: Initialize array 7, of size 11, B+1), with oc in all entries.
4: Initialize array T mazz of size (N + 1), with oo in all entries.
5: T[1, 0]= 0]=1]
6: Tmex [1]=1
7: for n 17=22 1 do
8: for borb=1-3 do smm m
9:
T(n, b) max
[Tnm [mn-m, b-1]+ P(b] Tiaa (mi)
10: end for
11: T Tmoxii [m] maxosus
12:
end for
13:
Return array
3.1.2 Theoretical Results
We now prove that the SEQUOIA tree construction algorithm scales well with the size of the speculated tree. In particular, we show that under certain assumptions on the acceptance rates of the verification algorithm, the number of generated tokens nower-bounded by function which is (roughly) loga- rithmic in the size of the tree. This is in contrast to existing tree construction algorithms, which are upper bounded the expected number of tokens they generate, regardless of the size of the tree. For example, single sequence of tokens has upper bound 1/(1 Pi) [24]; k independent sequences can only increase this upper bound by 1, because they only increase the chance of acceptance of the first token. Even an infinitely deep binary tree is upper bounded by /2)1-2).
We first define what it means for a verification algorithm to have a b power-law acceptance rale, and then present our theorem on the scalability of SEQUOIA trees, under the assumption that the verification algorithm has a power-law acceptance rate.
5

---

Draft: Pychio-400m, Target: Pythis-12b
Draft: Pytria 410m. Target: Pytha 126 (Temp: 0.5)
Draft: Pythia 410m. Target: Pytrio 12b remp: 1.0
Rejection Rate
Rejection Rate
Relection Rate
21
0.65
0.25
0.6
Sequela (ouns)
Sequola
Sequola (ours) Speciveer
0.
Speckintrr
Spectnter
SpecTh
SpecI:
Spec
x Sampling
Top k Samplh
A Samping
102
12' of Speculated Tokens
10t
100
10
10a
10e
10t of Speculated Tokens
1g
of Speculated Tokens
Figure 3: Rejection rate vs. number speculated tokens: We plot the average rejection rate (1 acceptance_ree r_tee for the different verification algorithms, as a function of the number of speculated tokens Across temperature settings (0.2,006,,..0) left to right), the SEQUOIA verification algorithm attains the lowest rejection rates, and consistently has power-law acceptance rate (Definition) 3.5
Definition 3.5.
We say that a tree verification algorithm has a power-lav acceptance rate the chance "x of the tree verification algorithm rejecting all Is speculated children of node in a tree is upper bounded by a power-law of with exponent b meaning. ny S 1 1/k Ak E: N, for > 0e R.
The above definition motivated by our observation (Figure3 that the SEQUOLA sampling/verification algorithm attains power-law acceptance rates in practice. We state the theorem (proof in App. F3)
Theorem 3.6. Using a tree verification algorithm with a power-law acceptance rate, the expected num- ber of tokens G(n)) generated by verifying the SEQUOIA tree of size n is in (owlloo(n)/lo((logg
3.1.3 Empirical Validation
In Figure I we plot the average number of tokens generated by SEQUOIA trees relative to various baseline tree structures, as a function of the number tokens n in the tree, using Pythia-2.8B as draft model for Pythia-12B, and WikiTeex--103. We see that the number of generated tokens for SEQUOIA trees is scbbunn roughly logarithmically with the tree size- the other tree structures asymptote. We show results for more draft/target model pairs in Figure 6 in Appendix G.3
3.2
Tree sampling and verification
We present our token tree sampling and verification algorithm, and prove it is the first such algorithm to satisfy two important robustness properties, while maintaining the target model's output distribution.
3.2.1 Algorithm
We present the pseudocode for the SEQUOIA Tree sampling and verification algorithm in Algorithm 2 As discussed in Section important motivation for designing the SEQUOIA verification algorithm was the observation that SpecInfer and SpecTr both perform poorly at low temperatures, due to the fact that they can repeatedly sample (and then reject) low-quality token that the draft model is confident in. Thus, we wanted to design an algorithm that would never make the same mistake twice meaning, once token was rejected, it would never propose that token again. Toward this end, SEQUOIA introduces two changes to the SpecInfer algorithm (shown in blue text in Algorithm(? 2): First, it performs sampling without replacement using the draft model distribution. Second, if all the tokens with non-zero draft model probability have already been sampled and rejected, it uses the uniform distribution over all tokens that have not yet been sampled as the new draft model distribution. These changes significantly improve the robustness of SEQUOIA relative to SpecInfer, while maintaining the guarantee that the output distribution is identical that of the target model (proof in Appendix F2.1
3.2.2 Theoretical Results
We now prove that the SEQUOTA verification algorithm robust, in the sense that it satisfies both of the properties below, while existing verification algorithms do not.

---

Algorithm 2 SEQUOIA Sampling and Verification
(The blue lines [10-16] distinguish SEQUOIA sammpiinghherrfcccctooooooooo Spechfer'' [28]
1: Input: Prefix [21,222....
and number of branches lo target model probabilitiies P(-[#tn)) draft model probabilities Q(- (.en).
2: Output: A token sampled using SEQUOIA.
Initialize residual with P. draft with Q, and set of rejected tokens
4: fori=1-1 do
5: sample 8.^0 D, Uniform((..]
6: if < 7[
Rlas] then
7: Return &
# #ccept
8: else
9:
n--nom(max R-
10:
D-s:]+-0
Ssadd(s;)
12:
sum then
13:
# Let be uniform over non-rejected set
14:
Off
en
end D4-norm(D)
17:
18:
end for
19:
Return
The optimal transport property: When 1=1, 1, the acceptance rate is equal to 1 PP-Qlh
The cover property: If the support of the draft model probability distribution Q is of size k and is superset of the support of the target model probability distribution P, at most i speculations will be needed to attain an acceptance rate of I. Furthermore, if k is equal to the vocabulary size, the acceptance rate should always be as well, regardless the draft model used.
Intuitively, satisfying the optimal transport property results in strong performance at high temperatures (because P' and Q will approach uniform distributions), while satisfying the cover property results in strong performance at low temperatures (if top target model token is in the top-k draft model tokens).
We now present our main robustness result (proof in Appendix F33
Theorem 3.7. SEQUOIA verification satisfies both properties (optimal transport, cover); Specinfer & SpecTr only satisfy the optimal transport property; top-k sampling only satisfies the cover property.
3.2.3 Empirical Validation
plot the average rejection rates (equal to 1 acceptance rates) for the different verification algorithms, as a function of the number of speculated child tokens for a fixed token prefix, for various temperatures (0.2, 0.6, 1.0), measured on Wiki'Text-103. We all temperature settings, the rejection rates for SEQUOIA decay faster than for the other algorithms. In general, observe that the rejection rates тı for SEQUOIA follow a power-law, where r%k 1/kb for some > 0. We can also see that while SpecTTr and SpecInfer perform relatively well at high temperatures. they struggle at lower temperatures, and that the opposite true for top-k sampling.
In Figure 3
that across
Evaluation
In this section, we aim to demonstrate that SEQUOIA can speed up L.LM inference by a large margin in wall-clock time. We first present our end-to-end system results showing total speedup, followed by validating our claims that SEQUOIA is scalable and robust.
Section we demonstrate SEQUOIA'S superior end-to-end performance. Specifically, SEQUOIA achieves up-to 4.04x speed-up for Llama2-7B on A100 and 9.5x for Llama3-70B on L40 offloading (achieving the latency as low as 0.60 s/token).
Section 4.2.1 we show that the SEQUOIA tree can generate on average 33% more tokens than a tree of 16 independent sequences (tree size 512).
"The SpecTr paper 40 showed that 1 ||--Q11 is the acceptance rate attained by the optimal verification
algorithm for l: =.
7

---

Table I: On-device results (A100), The optimal tree configuration and speedup for different pairs of draft and target models, and different temperatures, for SEQUOIA vs. SpecInfer. We specify the average number of generated tokens per decoding step in parentheses, next to the speedup factor. SEQUOIA attains up to 4.04x speedup on an A100. The speed of incremental decoding is 24.2ms/token with Huggingface. The draft model speed is 0. 0.5ms/token. TBT refers to time between tokens.
Tree Config. (size, depth)
TBT ms/token
SpecInfer 5x8
Speedup Spectnfer
Target L.M
Draft Model
T
Dataset
Speedup
LJama2 7B
JP6MM
C4
(128,10)
4,04 ((5088)
6.0
3.45x
1.17x
Llama2-7B
JP68M
0.6
C4
(128,7)
(.192(3.92)
7.6
2.477(2.97)
1.29x
Llama2-7B
JF68M
OpenWebText
(128,7)
(3.86)
7.5
2.79x(3.15)
1.15x
1Jama2-77 7B
JP68
0.6
OpenWe
(128.6)
(..33)
8.9
2.10x(2.54)
1.29%
Llama2-78 7B
JP68M
0
CNN Daily
(128,7)
3.41x((.05)
7.1
2.95x(3.27)
L166x
Llama2-7B
JP68M
CNN Daily
(128,6)
(3.45)
8.5
2.11x(2.58)
1.34x
1Jama2-7B
JF68M
MI Bench
(128,10)
(4.98
6.0
3.84x(4.01)
1.05x
7BB
JP68M
0.6
MT Bench
(128,7)
3.18x(3.96)
7.6
2.45((2.97)
1.30x
Table 2: Offloading results (L40): The optimal tree configuration and speedup for different pairs of draft and target models, and different temperatures, for SEQUOIA vs. SpecInfer. We specify the average number of generated tokens per decoding step in parentheses, next to the speedup factor. SEQUOIA attains up to 9.5 speedup the offloading setting on an L40. The speed of incremental decoding is 5.7s/token with DeepSpeed Zero Inference. TBT refers to time between tokens.
Tree Config. (size, depth)
TBT s/token
SpecInfer 16x48
Speedup vs Specinfer
Target LLM
Draft Model
T
Dataset
Speedup
Llama2-70B- -hahht
Llama2-7B Ba-hat
MT Bench
(768,18)
8.6x(10.30)
0.66
5.76(7.63)
151x
Jlama2-70B-chh
Llama2-7B-chhnn
0.6
MT Bench
(768,18)
8.4x(9
0.68
5.2x(7.03)
1.62
Jlamaa-70B-Insteer
Llama3-8B-Instreed
MT Bench
(768,18)
(.5x
0.60
(.0x(9.07)
1.36x
Jlana3-70B-lnstruu
Llama3-8B- -Bnssrutt
0.6
MT Bench
(768,18)
(11.3)))))
0.61
6.1x(8.29)
1.52x
In Section 4.2.2 show SEQUOIA's 's sampling and verification algorithm is robust to temperature, consistently outperforming SpecInfer (by up 1.65x) and top-k sampling (by up to 1.27x).
4.1 End-to-end Results
We now demonstrate that SEQUOIA speeds up LLM decoding in the on on-device setting by up 4.04 on an A100 GPU, and up to 9.5x with offloading on an 1.0 GPU.
Setup. Our experiments are based Llama and Vicuna models. For the on-device setting, use JackFram/Llama 68m (JF68m) (28) and princeton-nl waapitonnnn///Shaed----e- Laaedd-LLmma--ss 1.30 (SL1.3B) [6] as the draft models, and Llama2-7B
43 1lama2-13BB, and Vicuna-33B ( the target models. For
the offloading setting, we use 70B-chat/Llamaa3-055
as the draft model and Llama2-
as the target model. We evaluate results on C4(en) 35 validation dataset, OpenWebTen. WebText [14), CNN DailyMail [36] and MT Bench (52). In each experiment, we use 200 examples measure the acceptance rate vector (mentioned in Section 3.1 and sample another 200 examples for evaluation (50 for offloading). The prompt length and generation length are both set to 128 tokens except MT Bench. We evaluate SEQUOIA on different hardware including on-device experiments on L40 and A A100(-PCIE 80GB) GPUs, as well as offloading experiments on an L40 GPU (with PCIE4). We also compare SEQUOIA with SpecInfer 28 with & trees (5 independent sequences of length 8, the tree structure used in 28 for batch size 1) for the on-device setting, and 16 x 48 trees for the offloading setting.
Implementation Details. We implement the draft and target models using Transformers 451 Because we determine the optimal tree structure in advance, we are able to use PyTorch CUDA graphs 31 32 reduce the overhead of kernel launching during speculative decoding. To accelerate we use the exponential algorithm 44 combined with Py Torch CUDA graphs [31]22] For offloading setting, we used an
sampling without replacement- whichh-hcchhe is not efficient in Py Torch 2. [32] -e
DeepSpeed-Zeno--nfereene (2 as baseline, which is 5.7 s/token.
Hardware-Aware Optimization. For each hardware setting we consider in our experiments, we use the following method for selecting the size and depth of the Sequoia tree we should use to maximize speedups, while avoiding doing an exhaustive grid search. Letting G(n,d) denote the expected number of tokens generated by verifying the SEQUOIA tree of size n and depth (computed via dynamic programming), t(n) denote the (hardware-dependeen)) amount of time it takes the target model to verify
8

---

Sequoia's Scalability
Sequeia's Robustnesss
4.0
Tokens
3.0
3.0
Speeduu
2.75
Sequoia Specinter
2.5
Top sampling
Sequoia tree sequences sequences
2.0
16 sequences
1.5
64
512
0.4 0.6
1.0
Size
Temparature
Figure 4: Left: We compare the number of tokens generated on average by SEQUOIA trees vs. k independent sequences, where we use SEQUOIA sampling and verification for both tree structures. Right: We compare the speedups attained by the SEQUOIA sampling and verification algorithm relative to SpecInfer and top-k sampling, across various temperatures, holding the tree structure fixed.
tokens divided by the time verify token, and denote the (hardware-depender) dependent) time to draft 1 token divided by the time to verify token, the speedup attained by SEQUOIA can be expressed as G(n.d)
(needup(n,d)) = r(n)+die We measure t(n) and c empirically for each type of model and inference hardware, and then search over possible values of n., d to find the pair that gives the largest speedup.
Main Results. We evaluate SEQUOIA using different temperatures, draft and target model pairs, and hardware configurations. Results are shown Table (A100 on-device) and (L40 offloading). We observe that SEQUOIA consistently speeds up I.M decoding in wide range of settings. SEQUOIA reaches up 4.04x speedup for the on-device setting, and up to 9.5x speedup for the offloading setting, as a result of the huge gap between computation capacity and memory bandwidth. Notably, for the offloading setting on L40, SEQUOIA can achieve as low as 0.60 s/token latency. We present additional on-device results (100 and L40) in Appendix G
Analysis. We made several interesting observations on the interplay between SEQUOIA tree construc- tion, sampling and verification, and hardware-awan optimizer. (1) SEQUOIA selects much larger trees in the offloading setting (768 tokens) than in the on on-device setting (64 to 128 tokens). (2) In general, the average number of generated tokens is close the wall-clock time speedup (especially when JF68M tree optimizer. (3) The optimal trees found by
is used as the draft) as result of the hardware- SEQUOlA for slightly different configurations- e.g., different temperatures and model pairs can be very different from one another. (4) SEQUOIA chooses deeper trees at low temperature than high temperature, due to the acceptance rates being higher for low temperature.
4.2 Ablations
We present our ablation experiments validating the scalability of the SEQUOIA tree construction algorithm (S.ct. and the robustness of SEQUOIA tree sampling and verification algorithm (Section 4.2.2). For each of these experiments, we only vary one element at time (e.g., the tree study the gains attained by each component of SEQUOIA.
structure for Section 4.2.1
4.2.1 The Scalability of SEQUOIA
In Figure (left) we compare the average number generated tokens for the SEQUOIA tree construction method, relative i independent sequences, different budgets;
SEQUOIA' sampling and verification algorithm for all trees. The SEQUOIA tree is able to generate up to 33% more tokens per decoding step, demonstrating the effectiveness of SEQUOLA'S 's tree construction algorithm. Here, use MackFram/LLlam Lomm/lllmm-6mm as the draft model, Llama2- 13B as the target model, 0.6 as the temperature, and CNN Daily Mail as the dataset.
4.2.2 Robustness of SEQUOLA Sampling Algorithm
In Figure 4 (right) we compare the SEQUOLA sampling and verification algorithm to SpecInfer and top-k sampling across different temperature values, holding the tree structure fixed. We can see that

---

SEQUOIA achieves the largest speedups across all temperatures, attaining up to 1.65x and 1.27x speedup relative to SpecInfer and top-k sampling, respectively. Here, we use JackFram/Llama- as the draft model, I.lama-7B as the target model, CNN Daily Mail as the dataset, and the corresponding SEQUOIA tree from Table (temperature 0.6) as the tree structure. In Table Appendix [..4 we additionally show that the SEQUOTA sampling/verificttoon algorithm is robust to the top-p parameter.
Conclusion
We presented SEQUOIA, a scalable and robust speculative decoding method. By improving the topology of the token tree and the sampling algorithms, SEQUOIA is able to speed up autoregressive LLM inference up 4. 4.04x on GPU and 9.5x with offloading. In addition to providing real speedups. we believe SEQUOIA also provides insight into both the large potential and fundamental limits of speculative decoding systems. We hope that this understanding inspires future work in this area, or even informs the design of custom chips for LLM inference.
Acknowledgments
We thank Xinyu Yang, Harry Dong, Ranajoy Sadhukhan, Hanshi Sun, Silong Yong and the anonymous reviewers for their helpful discussions and feedback on the paper. This work was partially supported by the National Science Foundation under grant numbers CNS-2147909, CNS-221 1882, and CNS- 2239351, along with gift awards from Amazon, Cisco, Google, Intel, Li Auto, Meta, Moffet AI, Oracle, Qualcomm, and Samsung.
References
[1] Joshua Ainslie, Tao Lei, Michiel de Jong, Santiago Ontañón, Siddhartha Brahma, Yury Zemlyan- skiy, David Uthus, Mandy Guo, James Lee-Thorp. Yi Tay, et al. Colt5: Faster long-range transformers with conditional computation. arXiv preprint 2rXiv:2303.09752, 2023.
[2] Reza Yazdani Aminabadi, Samyam Rajbhandari, Minjia Zhang, Ammar Ahmad Awan, Cheng Li, Du Li, Elton Zheng, Jeff Rasley, Shaden Smith, Olatunji Ruwase, al. Deepspeed inference: Enabling efficient inference of transformer models at unprecedented scale. arXiv preprint arXiv:2207.0033. 2022.
[3] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 13:1877-1901, 2020.
[4] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D. Lee, Deming Chen, and Tri
Dao. Medusa: Simple 1lm inference acceleration framework with multiple decoding heads, 2024.
[5] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving. Jean- Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. CoRR, abs/2302.01318, 2023. doi:
URL https://doi. /
L8850//aXi1n 20021.22300.000 01318
[6] 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: An open-source chatbot impressing gpt-4 with 90%* * chatgpt quality, March 2023. URL
/ //mssyssrrgbbllo/2233033333 0000::////22200000--0000 30-0003-0-v000aaa000 vicuna/
[7] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung. Charles Sutton, Sebastian Gehrmann, et al. PaLM: Scaling language modeling with pathways. arXiv preprint arXiv:2204.022: 0, 2022.
[8] Tri Dao. Flashattention-2:: Faster attention with better parallelism and work partitioning. CoRR. abs/2307.0869/ 2023. doi: 10.48550/ARXIV.2300.. 188691.........
URL https:///oi..org::
48550/arXiv
[9] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NewrIPS 2022, New Orleans, LA, USA, November 28 3S-ecemmbrr 9, 2022, 2022.
10

---

[10] Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zeitlemoyer. Llm.int80: 8-bit matrix multiplication for transformers at scale. CoRR, (tbs/2208.0733// 2022. doi: 10.48550/ARXIV. 2208.07339. htt.https://do.. org/10 48550/4850/8580 arXiv 2208 .73399)
[11] Cunxiao Du, Jing Jiang. Yuanchen Xu, Jiawei Wu, Sicheng Yu, Yongqi Li, Shenggui Li, Kai Xu, Liqiang Nie, Zhaopeng Tu, and Yang You. Glide with cape: low-hassle method to accelerate speculative decoding. CoRR, abs/2402.00082 2024. doi: 10.48550/ARXI.22422.2222
URL
https://doi. org/10. 48550/ arXiv. 2402 02082
[12] Elias Frantar and Dan Alistarh. Massive language models can be accurately pruned in one-shot.
arXiv preprint www.v:2330..0072000 2023.
[13] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh, GPTQ: accurate post-training quantization for generative pre-trained transformers. CoRR, abs/2210.17323,, 2022. doi: 10. 01000/ARRXIV2220.17233.3. URLhttps://doo wrt.:0. 48550/ arwiv. 2210. 17323
[14] Aaron Gokaslan and Vanya Cohen. Openwebtext corpus, 2019,
[15] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces.
CoRR, /bbs/2312.00752. 2023. doi: 1044550/ARXXI.2311.00777 URLthttps: org/
10. 118650/arXiv.. 2312 00752
[16]
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In The Tenth International Conference on Learning Representations, ICLR 2022. Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https::/ net/
forum?id-uYLPooz.W..
[17] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural net- works with pruning, trained quantization and huffman coding. arXiv preprint arXiv: 15 10.00/49 2015.
[18] Geoffrey Hinton, Oriol Vinyals. Jeff Dean, al. Distilling the knowledge in a neural network. arXiv preprint arXiv: / 1503005533, (,,,,02511,2),,,, 2015.
[19] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Mach. Learn. Res., 22(221)::222))) 1-144, 2021.
[20] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient tittege--rithmmeicoonn inference. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 2704-27222000 2703,271,,25 2018.
[21] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5156-5165. PMLR, 2020. 1tteesssvv111//aahrrrggg os2a.. html
[22] Sehoon Kim, Karttikeya Mangalam, Jitendra Malik, Michael W. Mahoney, Amir Gholami, and Kurt Keutzer. Big little transformer decoder. CoRR, abs/2302.07863, 2023. doi: 10.48550/
ARXIV.2302.07863. URL RttLhhtts:///oo.... org/ 4805048550//0 ar.550//rXii.. 2302 07866)
[23] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Jason Flinn, Margo I. Seltzer, Peter Druschel, Antoine Kaufmann, and Jonathan Mace, editors, Proceedings of the 29th 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023, pages 61 1-6.. ACM, 2023. doi: 0001144/3600000.361333333 3611666...1 URL ///oi//oiiooo org/ 10. 1145/3600006. 065553330000666311155
[24] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. International Conference on Muchine Leurning, pages 19274-19286.
PMLR, 2023.
[25] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle:
Speculative sampling requires rethinking feature uncertainty. In International Conference on Machine Learning, 2024.
[26] Lin, Jiaming Tang, Haotian Tang, Shang Yang, Xingyu Dang, and Song Han. AWQ: activation- aware weight quantization for LLM compression and acceleration. CoRR, 0bb//2306000978.
11

---

2023. doi: 10.4550/ARRXV.233660000 00978
URL httpttts:://oo..or//////// 0ttp////11..0550///a...... 2306
[27] Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value 2018.
of network pruning. arXiv preprint
[28] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Rae Ying Yee Wong. Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. Specinfer: Accelerating generative 1mm serving with speculative inference and token tree verification. arXiv preprint arXiv:2305.0978/ 2023.
[29] Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:661 1,06440, 2016.
[30] Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling. Data-free quantization through weight equalization and bias correction. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1325-1332 2019.
[31]
NVIDIA, Péter Vingelmann, and Frank H.P. Fitzek. Cuda, release: 10.2.89, 2020. URL nvidia. com/ cuda toolkit
https://develop::
[32]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32,
2019.
[33] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. ArXiv, abs/2211 111221100011,, 2022. StRphtts::////
semanticscholar
org/Corpus 253420623
[34] Reiner Pope Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. arXiv preprint arXiv:221 1,00/00, 2022.
[35] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. arXiv e-prints, 2019.
[36] Abigail See, Peter Liu, and Christopher D. Manning. Get the point: Summarization with pointer-generatee networks. In Proceedings of the 55th Anmual Meeting of the Association for
Computationall Linguistics (Volume 1: Long Papers), pages 1073- 1083, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10. 8653/v1/PP1--109 URL httpps:/wwwy http:///wwwwwwwwbb..// wttp:/wwwwwww......eae..... wttp:/ahhoooogy//1--O0000
[37] Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang. Christopher Ré, Ion Stoica, and Ce Zhang. Flexgen: High-throughput generative inference of large language models with a single GPU. Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 31094-311 16. PMLR, 2023. URL https //proceedings. mlr. www.srreeessv.e /002//2eeng2a....m html
[38] Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31, 2018.
[39] Mingjie Sun, Zhuang Liu, Anna Bair, and Zico Kolter. A simple and effective pruning approach for large language models. arXiv preprint arXiv:2306. / 1695, 2023.
[40] Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. arXiv preprint arXiv:2310. 15141, 2023.
[41] Raphael Tang, Yao Lu, Linqing Liu, Lili Mou, Olga Vechtomova, and Jimmy Lin. Distilling task-specific knowledge from bert into simple neural networks. arXiv preprint arXiv: (otv::090 1903. 12136, 2019.
[42] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pages 10347-10355 PMLR, 2021.
12

---

[43] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Pumit Singh Koura, Marie- Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, liyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Ilama 2: Open foundation and fine-tuned chat models, 2023.
[44] Tim Vieira. Gumbel-max trick and weighted reservoir sampling, 2014.
[45] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et Huggingface's transformers: State-of-the-ar natural language processing. arXiv preprint arXiv:1910.03771, 2019.
[46] Mengzhou Xia, Tianyu Gao, Zhiyuan Zeng, and Danqi Chen. Sheared llama: Accelerating language model pre-training via structured pruning. arXiv preprini arXiv: (0.::2330.066944,, 2023.
[47] Daliang Xu, Wangsong Yin, Xin Jin, Ying Zhang, Shiyun Wei, Mengwei Xu, and Xuanzhe Liu. Llmcad: Fast and scalable on-device large language model inference. arXiv preprint arXiv:2309.042.
2023.
[48] Lu Yin, You Wu, Zhenyu Zhang, Cheng- Yu Hsieh, Yaqing Wang, Yiling Jia, Mykola Pechenizkiy, Yi Liang, Zhangyang Wang. and Shiwei Liu. Outlier weighed layerwise sparsity (owl): A missing secret sauce for pruning Iims to high sparsity. arXiv preprint arXiv:2310.0511
2023.
[49] Gyeong-In Yu and Joo Seong Jeong. Orca: A distributed serving system for hansformer-basel generative models. In USENIX Symposium on Operating Systems Design and Implementation, 2022. WtLhhttp://aagg
www.nticscoollee...ooooocccoc. org/Corpus 251734964
[50] Jun Zhang. Jue Wang. Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mchrotra. Draft & verify: Lossless large language model acceleration via self-speculative decoding. CoRR, doi: 10.483550ARXX11.2309..88 46550/arXiv 2309. 08168
abs/2309.08160 68, 2023.
URL /tttps://ao..org::
[51] Ritchie Zhao, Yuwei Hu, Jordan Dotzel, Chris De Sa, Zhiru Zhang. Improving neural network quantization without retraining using outlier channel splitting. In International conference on machine learning, pages 7543-7552. PMLR, 2019.
[52] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging llm llm-aeea-judge with mt-bench and chatbot arena, 2023.
[53] 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 arX0v:2310.08611, 2023.
13

---

A Broader Impacts
In this paper, we present a new algorithm for accelerating speculative decoding. While there are numerous application scenarios of large language models that warrant additional study regarding possible societal impact, we would like to highlight that our work does not advance the capabilities of these models. Our work is primarily an algorithmic study with no specific usage limitations, and while LLMs themselves can be used with malicious purpose, we believe that none of such use cases are specific to this paper.
B Limitations
Theoretical limitations:
On the theoretical front, there are two primary limitations to our results:
1. The positional acceptance assumption (Definition 3.1 The optimality of our dynamic program depends on this assumption. In particular, this assumption states that the only factor inftuencing the acceptance rate for token is what "number child" it to it's "parent token" (e.g.. if is the first or fifth sampled token to follow the "parent" token). This allows us model the acceptance dynamics using simple closed form equations, which ignore all contextual factors impacting acceptance rates (e.g., the current prefix, the confidence of the draft model, etc.).
2. The power law acceptance rate (Definition 3.5 While we observe in our experiments that SEQUOIA satisfies this assumption (see Figure B it's important to note that need this assump- tion for our theoretical results on the scalability of SEQUOIA trees to hold (Theorem F2).
Methodological limitations: In terms of the limitations of SEQUOIA in practice, the most important limitation//calllngee is likely that the structure of the optimal SEQUOIA tree depends on the exact (average) acceptance rate vector, which depends on the draft/target model pair, temperature value, data domain, etc. The optimal tree also depends on the batch size, which can be considered by the hardware-awan optimizer. It is relatively work-intensive have to measure the acceptance rate vector for each setting, and use this vector to compute the optimal tree. In practice, we believe computing a single tree for a typical use case work well for other use cases (e.g., higher/lower temperatures, different data domains), but we leave a more thorough analysis of this issue for future work.
C Related Work
This work introduces new algorithm in the family of speculative decoding methods that aims to maintain the exact output distribution of the target model by improving the structure and sam- pling/verification algorithm for the speculated token tree. There exist many other directions within this line of work-for example, methods which introduce leniency into the speculative decoding algorithm attain increased speed the cost of accuracy [22 (88, methods that reuse layers or representations from the target model as the draft model (50 4. etc. Alternatively, the draft model can be distilled to better approximate the target model; DistillSpec (5x] 18 42 improves that process by using model-ggenertee data and adjusting the objective depending on the task and the decoding strategy. Finally, LLMCad [47] proposes an advanced algorithm for token tree generation and verification in the context of on-device LLM inference.
In addition to speculative decoding, there exist many other methods aimed at improving the speed LLM inference. For example, model quantization is another very promising way of dealing with the I/O bottleneck during inference, by reducing the number of bits per parameter. However, unlike speculative decoding, these methods generally deteriorate the quality of the model some degree,
depending on the amount of quantization
I7
20, 30
51
26
13
10
or sparsity
29 19]
Meanwhile, various works 12 39 48 1 have studied ways to improve LLM serving throughput. Pope al. [33 investigated the batching effect in scaling up L.M.. Orea 49 proposed distributed LLM serving system that uses finegrained scheduling policy to improve GPU utilization under various request lengths. vLLM 2 used page tables to manage GPU memory to increase memory utilization, which significantly boosts inference throughput. FlexGen support larger batches to achieve high throughput.
37 proposed an offloading mechanism to
FlashAttention is another algorithm that aims to improve the speed of L.LMs (at both training and inference time) by considering the I/O cost of different operations.
14

---

Another promising upproaching to speeding up inference is to change the fundamental building blocks of the model. Recently, numerous sub-quadratic architectures iecttuureeiinnuuiinnn SSMs [6 [5] and linear attention models 21 have been proposed. These models are particularly beneficial for long inputs.
D Background: Sequence-based speculative decoding
The original speculative decoding method 224 [ proposes using small "draft model" to speculate y tokens into the future, and then using the "target model" to in parallel process these tokens and decide which of the tokens to "accept", in such way that the output distribution of the target model is unchanged. This algorithm is presented Algorithm 3
Leviathan et al. 24) analyze the performance of this algorithm, presenting equations for the expected of the algorithm, and the expected wall-clock speed up from using speculative decoding (relative to standard autoregressive inference with the target model). In this analysis, they introduce the acceptance rate E [0, 1, corresponding to the probability that token T; is accepted by Algorithm under the simplifying assumption that the acceptance decisions are iid Under this assumption, they show that the expected number of generated tokens in each run of Algorithm
number of accepted tokens from
3 is 1-ar+1
I-a Additionally, letting e denote the ratio between the time to run the draft model
and the time to run the target model, they show that the expected wall-clock speed-up from using this algorithm is 1-a7t1
(1-a)(y+11)
Algorithm 3 Sequence-based Speculative Decoding
1: Input: Prefix [x1,22,.... 1]. Target model My. draft model Mq. and number of tokens y to speculate.
2: Output: A sequence of tokens generated using speculative decoding.
3: i do
b Sample sequence of ry tokens from draft model
4: 9:(x) ( (1.....))1)
5: (.)q((z)
6: end for
7: fori=n-tn do
For loop below can run in parallel with a single forward pass of Mp
8: p.(z) + My --11)
9: end for
s+n-1
Choose how many tokens accept
11: for -
12: ri~ (n1form(0.1)
13: if p((m)) then
(ms)
14:
15: else
16: break
end if
18: end for
20: ift i then
p'(x) m00mmmm((0000))))) -c411(x)))
22: end if
(~p((>)
D. Sample final token from p/(x)
24: Return T1........
'One can think of the average acceptance many runs of this algorithm representative dataset.
15

---

E Examples of SEQUOIA trees
Below we show more examples of SEQUOIA trees various sizes. Note that for these plots we do not limit the depth of the tree. The acceptance vector used for this (shown below) computed with Llama3- 1aaaa-------nntrue target model, Llama3-8B-Inan Innttructttt draft model, on CNN daily news dataset: [0.7732, 0. 0.1999, 0.0402, 0.0206, 0.0128, 0.0081, 0.0064, 0.0043, 0.0035, 0.0026, 0.0025, 0.0021, 0.0016, 0.0014, 0.0010, 0.0010, 0.0010, 0.0007, 0.0007, 0.0006, 0.0007, 0.0006, 0.0004, 0.0004, 0.0005, 0.0006, 0.0004, 0.0003, 0.0002, 0.0004, 0.0001].
(a) node SEQUOIA tree
(b) 16 node SEQUOIA tree
(c) 32 node SEQUOIA tree
(d) 64 node SEQUOIA tree
(e) node SEQUOIA tree
(1) 256 SEQUOIA tree
Figure set of increasingly large SEQUOTA trees.
16

---

F
Method details and theoretical results
We present additional details (as well as proofs for theorems) about the SEQUOIA tree construction (Section
F.T and tree sampling and verification (Section F.2 methods.
F.1
SEQUOIA tree construction algorithm
We begin by presenting details about the SEQUOIA tree construction algorithm, and its corresponding theoretical properties.
F111 SEQUOIA dynamic program details
In this section, we present an extended version of the SEQUOIA tree construction dynamic programming (DP) algorithm (Algorithm TT. including full python implementation of this extended algorithm (Algorithm{ā) In Algorithm] I we showed how compute the expected number of generated tokens for the optimal tree of size N (and branching factor < B). Here, we extend the algorithm to be able to handle:
1. An upper bound D on the depth of the token tree, and
2. Self-speculation methods like Eagle 25 whose acceptance rates decay for tokens that are deeper in the speculated tree.
We then show how additionally generate the optimal tree structure using dynamic programming, for these more general settings.
Extensions to bounded depth and self-speculation methods: To handle the above cases, we assume that we have a 2-D array p. where P(d, 6] is the probability of acceptance for node at depth d and branch number Here we assume p is vero-indexed, so depth 0 corresponds to the direct children of the root node. We also assume has shape (D 1, B 1.B+1 1). where D is the limit on the depth of the speculated tree, and B is the limit the branch factor of the tree (max number of children per node). This allows to infer that when we are computing 7 [m., d, b) (during the internal running of the DP algorithm), ) the case where the root node has a depth limit of D, the node being considered has depth limit d it must be at depth D d; thus, D-d is the index of the P Parray (at dimension 0) that should be used at that time. Using this fact, we can show that the recursion equation for Eagle (with bounded depth) is quite similar the one from Equation (and Algorithm| in Section 3.1.1
T In, d, 6]=
max 15m5n-
d, b.--,,+
max T'm, d d-1,5)) 0S1SB v2 25d5D, 25b5
Constructing the optimal tree structure: In the python implementation below of the extended SEQUOIA DP algorithm (Algorithm(4) we show how to recursively construct the optimal tree structure for each tree size and depth limit d. Throughout the DP we maintain the following data structures:
best new _ew__ndeenn node(n, , d, b): A pointer to the root of the best sub-tree to add as the 6th child of the tree root with budget depth <= d, and b children.
best_tree A pointer to root of the best tree with n nodes and depth <=d. d.
Line 32, and then lines 40-45, demonstrate the recursive relationship between these tree structures:
If m² is the optimal number of tokens that should assigned the tree rooted at the 5th (and last) child for the tree (For the (n, (n,d,b) d) tree), then we can look up the optimal tree of that size in best_rree [m= dd-
1-11 1}, and set besl_newwnollee new__odee(n (n, d, b)= besss_s_lree (m mm"" .d-1).
If b* is the optimal number of children for tree of size n and depth < d, we can look-up _est_new new sadu___od_______ n, d, 5"] (the root of tree of size m') and assign that as the last child best, west_tree(ne (, d). To then find the optimal (b -1) 1)th child of this tree, we can look-up best_ nee sei__newwwdeeree mnidnnndddmmmmme dd,b" 5" 1), and we continue in this manner until we have added all 6* children to best_tree (n.
This demonstrates how to build the optimal tree part of the dynamic program.
17

---

Algorithm 4 SEQUOIA tree construction algorithm: Python implementation
import numpy as up
class Node:
def __init__ (self, children-None):
self children children children not None else
self wwm_mmmmodoei www.mmmmme_ssiieee in_ttreeeeeeeeeeeeeeee sum(c.
mum num _aa___odes__iii in_ tree for c in self. children)
def sequoia_tree crree_cosstuctionnee (acc_rates, max_tree size, max max_tree cree_depth, max_ branch) P, N, D, acc_rates, max sax_tree_size max pox_tree_deptha max branch
10
if P.ndim 1:
11
= np. tilee, (D 1))
assert P. Phspape == (D 1,, + + 1)
14
== up ffll (shapee (N + 1, D 1, +), fill-value=-flot ('inf )))
15
T_max = np. (shpeee (N + 1, D 1), fill_value= (inf
16
T[1, 1:, 0] 1.0
T_max[1, 1:] 1.0
18
19
best_new. node(n, d, b] pointer to the best node (tree root node) to add as the tth child of the tree root with budget n, depth <= d, and b children. # best, tree[n, d] á pointer to root of the best tree with n modes and depth <= d. beat_new_nee new_nowwwdddeeeeeeeeeee {11 0): None for d in range (1, + 1)}
20
21
23
best_tree {(1, Node() for d range 1)}
24
25
for n in range (2, N 1):
26
for d in range (2, D 1):
27
for b in range (1, 1):
28
x np www_naanntooooeon to_ntm (Tín 1: 0: -1, d, b- P d, b] T_max[1: n, 1],
29
nam=0.0, neginf=-float colnfff-llattiimm ('inf"
T T[n, d, b] mp.mmx(()) if T[n, d, b] > 0.0:
32
best prst_newwnode [n, d, b] best_tree (x) + 1, d T Tamax [n, d] mp. map.max [n, d, :])
33
34
if [n, d] 0:
beat_ np. argmax d, :1) srrdget_depth_d__eae remaining_budgert =n
37
38
39
# Find the "best_"" children of the root node, starting with the last. for b in range (best_b, -1);
41
next_child best_new_noot [remaining budget, d, best_n, n_ www.ennuueet__e.. beciining_buddgee
42
bwdget_depth__eee letts_depp_________ depth_d_tree_______eeeeeepeeeeee
t_tte_cchildee
tree_ children. insert (0, next_child)
43
- next_child, num_ num_nddes_ins latessii_______ee
assert remaining. budget ==
beat_tree [n, d] Node (children-beat.cc mndget_deptha treetrreeeee cree_children)
46
47
return T, best_tres tree
F.1.2 Proof of Proposition 3.4: Closed-form expression for F(T)
We now prove Proposition 3.4 by deriving the closed-form expression for F(T) (the expected number of tokens generated by verifying tree T), and show how use dynamic programming to find the optimal tree T under tree budget size.
Propusition F.1. Let T be a token tree that is verified with the positional acceptance assumption, and let f(v) denote the score function for node E T. Then the expected number of tokens F generated by verifying T is equal
((T=-11 VET
18

---

Proof. Let D(T) denote the expected number of tokens generated by verifying tree T. We would like to prove that D(T)== We will prove this by induction on the size of T.
Base case (N= 1): tree of size I composed solely of the root node. By definition of the score function f(v) (Definition 3.3), we know that f()) =1 for the root node, so =1. D(T)= ( 1 because verifying tree composed of a root node with no children will simply sample from the target model, and generate token.
also,
Inductive step (N> 1): For [T]=N 1, let e be leaf of T at child index i, of depth d with parent Up and sibling S. (set of sibling indices). We can then consider the tree T T'=T- {v). Based on the inductive assumption, we know that g ((T") = D(T'). Using this assumption, we can express D(T) in terms of D(T'):
- P: + +(d- 1)-1())))p)))))))))))))))))))1 (1- E Pi ) +d-s(v) iES.Ufiut
D(T) D(T--DTT)((d-)--(1t)) (1-
LES
= -D(T)-(4-1)f(()bpb, +d-(((
(d)- J'ET'
=f(T)+{(1))
=F(T)
Note that we use the inductive hypothesis, along with the fact the f(1,) Pt., = (v) (by definition of f(r)).
F.1.3 Proof of Theorem 3.6; Main scalability results for SEQUOIA trees
We now prove that, under certain assumptions on the acceptance rates of the tree verification algorithm, the expected number of tokens generated by verifying the SEQUOIA tree is lower bounded by function which is roughly logarithmic in the size of the tree. We will do this by showing that a simpler tree-the k* (n) tree (defined below) has this lower bound, and using the fact that the SEQUOIA tree is by construction the tree with the largest expected number of generated tokens.
We define the k (12) tree to be the k-ary tree with S n nodes that has the highest expected accepted sequence length. Letting G(m) denote the expected accepted sequence length for the k (n) tree, we will now prove that G(n) ES (2)oog(n)/ (og((oo(n)) (meaning, it is lower-bounder by a scalar multiple of blog(n)/ /log (log(n))), )) under the assumption that the rejection rate Fx is upper-bounded by a power-law of k. It then follows directly (as corollary) that the growth rate of the tree generated by the SEQUOIA algorithm will also be in 2 (blog(n) (n) /loo//logo//// (log(n)).
Theorem F.2. Assume the chance rk of a token tree verification algorithm rejecting all k speculated tokens (k child nodes of some node in the tree) is upper bounded by power-law of k; T S 11/²² for some > EE.. Then the growth rate G(n) for the k. (n) tree is in P
Proof. We will let k(n) = [log(n)\/} denote the branch-width chosen for tree size n., and show that under this assumption, the growth rate G' (n) of the corresponding k is at least blog(n)
10log(logín)
assuming that large enough. Given that G' (n) lower bound on G((n) (because the above
choice of k(n) might not be fully optimal), and using the definition of Ω this proves that G(n) e
Ω (blog()) /llg((lg(()))) Note that we will abbreviate k(n) as k in many places throughout the proof, for brevity.
'Recall that a-ar tree is one where every non non-leaf node has & children.
19

---

If we let d denote the depth of the tree, the number of nodes in the tree is 1 1 k h2 + K2
kdi1
R-1 S This implies d (n), which we can prove as follows:
A -1n(((()
k k S - nk
+ d S logs log (n)
~dggoge(1))
We can assume / is the largest integer such that d d= (n), so it also follows that d+ 1 2 logæ (n). Letting = - the expected length (n) of the accepted token sequence can be expressed as 1-(1 1-(1-ax)+ 2ax (1 (1-o4) + +a (1-aa) - (d+ (d+1)aaf = 1+aa+ ++ +a 1- e+1 equality is result of telescoping sums, the second is from the sum of a finite geometric series). We will now lower bound this expression, making use Lemma F.4 (defined and proven below).
(the first
d+1
G(n)2G((m)
- Ok
1-0% Ork
1 (1 -rk) dr
d+1
applying Lemma F4 and assuming ri- (x-(d+1) (1.9)
10
(n)
10
log(n)
1k)
log(n)
10log(log(n1111)
blog(n))
10log(log(n))
Now simply need to understand when (d+1))Sog(()
Tk (d+++1)
(1ogs (m)+
1.hh
2log (n)
< (log(n)1/) 1)6
using k(n) = [log(n) 1 2log(n) 110_
2logA (n)
(glo((n)1/))
2b+1log(1)
log(k:)log(f
2b+1
log(k)
if 2h11 log(k]
< <log(19)) (19), then it follows that ra- (d-((d1))
2
20-1
26+1
$log(1.9)
log(1.9) log(k) log(1.9)
<k
log(k)
20

---

Given that (()) [log(n) !/ 2log(n)' // -1, we know that if log(n) 1/6 1 exp
2
then
log(1.9)
it must hold that (<n) 2 exp
2
as well. We can see that this holds if:
1og(1.9)
2
((tesp)
2
log(n) exp
+ #m2expp exp
log(1.9)
log(1.9)
Thus, we have shown that as long as n greater than the above expression, then (" [ogg Because know that G(n) 2 G" (n), this concludes the proof that ((n) is in
blog(n)
We now prove, corollary of Theorem F2 that the growth rate of the SEQUOIA tree is also in O ( (lo((loo(()))
Corollary E.3. Under the same assumptions on the rejection rates as Theorem F2 holds that the growth rate for the SEQUOIA tree is in S2 (bblog(n)/log((oo())))
Proof. By construction, for every tree size n, the SEQUOIA tree is the tree that has the largest expected number of generated tokens. Thus, for every value of n the expected number of generated tokens for the SEQUOIA tree must be larger than that of the k (n) tree, which was shown Theorem F.2 to be in (bblog())//og(llgg((( This concludes the proof.
We now prove the lemma that we used to prove Theorem
Lemma F.4. For any real number x E (0,1), and integer m> 0 such that m.r Llg((1.9) it holds that
Proof.
1- ma
(1))
x
(3)
x 3+
(7)x2*
x -... (-1)m²
1 (1 x) m
mE
(7) x=)===
(T)) 1
4 x +.... m
x
m
m
x +
m
2
m
x +...
m
2
3
m
m
2
m
m-
VI
2
3
2
m
mp
m
2!
3!
4!
2
(mz))
)
(mz))
(mzz)
(mx)s
2!
31
4!
5!
6!
ma
(ma) 2
(mx)² 3
(mx)*
(mz))
2-1
1
2!
3!
4!
5!
6!
(mar) 2
(m 3
(max)²
(mx))
1
+ 2!
5!
6!
(mx)²
2
(mx)3
(mar)*
(ma))
m
1 1++x++
+...)
2!
3!
4!
m
Assuming m= < 1.9, which is true by our initial assumption.
10
21

---

F.2 SEQUOIA sampling and verification algorithm
We now move on to presenting proofs about the correctness and robustness of the SEQUOIA sampling and verification method.
F.21 Proof of correctness for the SEQUOIA sampling and verification algorithm
We prove now that the SEQUOIA verification algorithm maintains the output distribution of the target model. We assume we have target model and a list of draft models (d1,...d,, dn+1....,, where di in this case depends on the previously rejected samples 21...,2i-1, and where d, (u) and t(u) denote the probabilities of sampling token V from d, or respectively (where V is the token vocabulary). We let i denote the residual at iteration i of SEQUOIA loop, (after i nodes have been rejected (so t =t, can be seen in Algorithm (
We will prove by induction the number of proposed tokens that the SEQUOIA verification algorithm correct.
Base case (n= 0): SEQUOIA is trivially correct, as will simply sample from the residual 11, which is equal to t.
Recursive case: We assume SEQUOIA is correct for n n-1 proposed samples and prove it is correct for proposed samples.
We first show that stage i in the speculative algorinng the chance of SEQUOIA choosing to reject the proposed sample is equal to E, (0, (z))
Lemma F.S. P(No token accepted at iteration i) = max max (,1(())d((3))
Proof.
P(No token accepted at iteration i)
P P(sample ..). P(reject æ x is sampled)
dx)() 1-min
(
(2(x))
(d(x)))))
dx(()) Σ min (((x).
-4(x) Σ min ((x))
44(#) +mxx+maxx (44(x), d((r))
44(x) -4(x) -4()) (0, (0,(((x)) di (x)
Σ max (0,4(x) d.(x))
We are now ready to prove the recursive case of the SEQUOIA algorithm. By the inductive hypothesis, we know that for all e V.
t(u)= (uu accepted in first n iterations) P(No token accepted in first n iiterations) (u)
What this means is that in the case where we run SEQUOIA for n - iterations (and if no token
accepted we sample from the residual 4,)), this is equivalent to sampling from the target distribution /
directly. We would like to show that this output distribution is equivalent to the one we would get we run SEQUOLA for iterations (and if no token is accepted we sample from the residual t 1) The
22

---

output distribution of this scenario can be written as follows:
P(u accepted in first n iterations) + (Noo token accepted in first n iterations)-
d (.)uu.P(p P(u accepted at iteration + P(No token accepted in iteration nt) -tp+1 (u)
Thus, all we must show is that in (u) = (u) P(u accepted iteration n)) P(No token accepted in iteration n)) -b++1 (u)
We now show this desired result. We will use Lemma F5 and the fact that by definition of the SpecInfer
max O. k. (u) (u)-da, (u)) algorithm (see Algorithm ignoring blue lines), we know that fx+1 (u) Σ, max (x) (xx)
dn (u) P(u accepted at iteration r²) P(No token accepted in iteration 12)-6+11 (u)
tn(u)
=d,(u)
Σ max (dx(())))d
(r+1("))
du)
max (0 ((0dn(())))))() -dn)-dn())
-min
dn (n)) +
Σ max 0,tx du((t)) -
max (z) - (x)
-min dn(u)),n(u))
+max (1)x dn (u)
(u)
To that this last equality holds, consider two
1. Case 1 (Ln(w) 2 dn (u)) (1), (, dd du(u) (1)++(+( +()(v)-
du(u)= [ (u).
2. Case (u) htt0::/:h.........../..//./01110
This completes the proof.
E3
Proof of Theorem 3.7: Main robustness result for SEQUOIA sampling and verification
We now prove the robustness results for the SEQUOIA verification algorithm.
Theorem F6. The SEQUOIA verification algorithm satisfies both the optimal transport and the cover properties, while SpecInfer and SpecTr only satisfy the optimal transport property, and (lop-k) naive sampling only satisfies the cover property.
Proof. This proof is quite straightforward:
SEQUOIA satisfies the optimal transport property: It is clear that SEQUOIA satisfies the optimal transport property, because at k 1, is identical to the original speculative decoding algorithm (24].
SEQUOLA satisfies the cover property: To see why SEQUOIA satisfies the cover property, we will use the following two facts:
the support Q is of size and k tokens are speculated by the draft model, the set of speculated tokens will always exactly equal the & tokens in the support of Q (because SEQUOLA does sampling without replacement from the draft model).
During the verification for-loop in Algorithm be contained in the support of P intersected with the set of tokens that have not yet been rejected. This is because the support of the residual can never grow (because ps (xr) = P (x) norm(marl) - gi (z) = O, where pt and q; denote the residual and draft probabilities at iteration respectively). and because if a token is rejected will "exit" the residual (because x: rejected implies q((r) > pe(ar) which
2 the support of the residual will always
implies that P(+1(z) norm(mar q, (2) =0).
23

---

Combining these two facts, we can see that if the first k- 1 tokens were rejected, then the kth token must be accepted, because the residual must be a one-hot vector with probability at the only remaining token, and the (updated) draft probabilities will also be this same one-hot vector (and thus, accepted with probability 1). Additionally, we can see that if V tokens are sampled (where V is the vocab size), these must exactly equal the V tokens in the vocabulary, and thus one of those tokens must be accepted. In the case where the support of Q is equal to the full vocabulary, this result follows directly from the discussion above. In the case where the support of Q does not equal the full vocabulary, this is result of the fact that once all tokens in the support of Q have been sampled and rejected, we begin sampling (without replacement) from the uniform distribution over all non-rejected tokens.
SpecInfer satisfies the optimal transport property: For k = 1, SpecInfer is identical to the original speculative decoding algorithm 2
SpecInfer does not satisfy the cover property: is easy to see that SpecInfer does not satisfy
the cover property, with the following counter-cxample. Let Q = [0.5,0.5] and P= [1.00]] We can see that the support of Q is of size 2 and contains the support of P. But with probability 25%, SpecInfer will sample the second token twice in row, and will reject both of them.
SpecTr satisfies the optimal transport property: For A = 1, SpecTr is identical to the original speculative decoding algorithm [24], because
-1 1 by definition.
SpecTr does not satisfies the cover property: We can show that SpecTr (in partic- ular, the 'k-sequential selection' algorithm from (40) does not satisfy the cover prop- erty, with the following counter-example. Let P p= [1. 0] and Q = [0.5, 0.5]. Then Sp.a()) = E (z)) P(x)/7) = min 1/7) + mi.,00.,,0/1)
0.5 (because 1 1- 11-10..5) o Thus, Spec'Tr does not satisfy the cover property.
E [1,2] by assumption). We know the acceptance rate of SpecTr is 1 - (1 (p.
Top-k naive sampling does not satisfy the optimal transport property: Letting Q 00.600.4] and P- P000.6, 00.6,0.4) we can see that top-k naive sampling will accept with probability 0.6, whereas 1 P Q 1.0.
Top-k naive sampling satisfies the cover property: It's easy to see that if the support of Q is of size & and contains the support of P, then top-k naive sampling will always accept (because it will sample from the target model and accept if the sampled token is among the top-k tokens according to the draft model). Similarly, k = V. it must accept as well (because the top- V tokens must be the full vocabulary, and any sample from the target model must accept).
G Additiona Experiments
G.1 Additional end-to-end speedup results
We provide additional end-to-end results comparing SEQUOIA to baselines, extending the results from 4.c Here (Tables3annd 4. we provide on-device results on A A100 and L40 GPUs, for a more extended set of models, relative to the results in Table but on different hardware.
G.2 More Comparisons with SpecInfer
To demonstrate the optimality of SEQUOLA'S 's tree construction, we provide a sweep of tree configura- tions and corresponding speedups of SpecInfer in Tables SEQUOIA attains better speedups in both greedy decoding and stochastic decoding than tree configurations of SpecInfer.
G.3 Scalability Additional Results
Here we present additional results demonstrating the scalability of the SEQUOIA tree construction algorithm relative to baselines, for several Pythia draft and target model pairs on the 10 dataset:
24

---

Table On-device results (A100): The optimal tree configuration and speedup for different pairs of draft and target models, and different temperatures, for SEQUOIA vs. SpecInfer. We specify the average number generated tokens per decoding step in parentheses, next the speedup factor. SEQUOIA attains up 4.04 speedup on an A100. TBT refers to time between tokens.
Tree Config. (size, depth)
TBT ms/token
SpecInfer 5x8
Target LLM
Draft Model
T
Dataset
Speedup
1lBma2-7B
JF68M
0
C4
(128, 10)
4.04 (5.08)
6.0
(3.96
Llama2-7B
JF68M
0.6
C4
(128,7)
(3.92)
7.6
22.77)
Llama2-7B
JF68M
0
OpenWebText
(128,7)
(3.86)
7.5
2.79x
Llama2-78 7B
JF68M
0.6
OpenWebText
(128,6)
x.71
8.9
2.10x
Llama2-7B
JF68M
0
CNN Daily
(128,7)
(4.05)
7.1
2.95x
Llama2-7B
JF68M
0.6
CNN Daily
(128.6)
(3.45)
8.5
2.11x(2.58)
Llama2-13B
JF68M
C4
(64.9)
(4.20)
3.30x)364)
Llama2-13B
JF68M
0.6
(64.7)
(3.57)
(2.87)2.87)
Llama2-13B
JF68M
OpenWeb
(64.7)
(3.49)
9.8
2.77x(3.05)
Llama2-13B
JF68M
0.6
OpenWeTText
(64.6)
(3.06)
11.3
2.17x(2.49)
..ama2-138
JF68M
CNN Daily
(64,7)
(3.68)
9.4
(3.22)
Llama2-13B
JF68M
0.6
CNN Daily
(64,6)
(3.17)
10.8
2.17x(2.54)
Vicuna-33B
SL1.3B
0
C4
(64.6)
x4.28)
23.4
(3.86)
Vicuna-33B
SL.13B
0.6
C4
(64.6)
(4.16)
24.3
(3.53)
Vicuna-33B
SL1.3B
0
OpenWebText
(64.5)
(3.93
24.1
(3.77
Vicuna-33B
SL1.3B
0.6
OpenWebText
(64.5)
(3.82
25.0
(..3x
Vicuna-33B
SL1.3B
0
CNN Daily
(64.5)
(3.93)
24.1
(3.7
Vicuna-33B
SL1.3B
0.6
CNN Daily
(64.5)
(3.86)
24.6
(.58x(340)
Table 4: on-device results (L40): The optimal tree configuration and speedup for different pairs of draft and target models, and different temperatures, for SEQUOIA vs. SpecInfer. We specify the average number of generated tokens per decoding step in parentheses, next to the speedup factor. SEQUOIA attains up 3.95 speedup on an L40.
Tree Config. (size, depth)
SpecInfer 5x8
Target LLM
Draft Model
T
Dataset
Speedup
Llama2-78
JF68M
(64,10) 10)
3.50x 3.95x
Llama2-7B
JF68M
0.6
C4
(64.7)
3.16x
2.28x(2.89)
Llama2-7B
JF68M
0
OpenWebTex.
(64,7)
3.12x
2.79x(3.16)
Llama2-7B
JF68M
0.6
WebTeet
(64.6)
2.18x
2.08x
Llama2-7B
JF68M
0
CNN Daily
(64,7)
3..09
2.89x
Llama2-7B
JF68M
0.6
CNN Daily
(64.6)
2.81x
2.09x(2.59)
Llama2-
JF68M
C4 C4
(64.10)
3.15x
2..6x
Llama2-13B 13B
JF68M
0.6
(64.8)
2.62x
2.06x (2.81)
Ilama2-13B
JF68M
0
Open WebTeet
(64,8)
2.642
2..05
Llama2-13B
JF68M
0.6
OpenWebText
(64.6)
2.28x
(.79x(2.44)
Ilama2-13B
JF68M
0
CNN Daily
(64,7)
2.76x
23.2x
Llama2-13B
JF68M
0.6
CNN Daily
(64.7)
x..22
(2.5L
G.4
Robustness Additional Results
See Table
G.5
Evaluation of SEQUOIA hardware-awars optimizer
In this section, we demonstrate the effectiveness of the SEQUOIA hardware-aware tree optimizer. We compare the speedups attained by the SEQUOIA trees of various sizes from (lgure(4(eeft) to the trees selected by the hardware-awand aware tree-optimizer. Because the tree optimizer is able to limit the tree depth make speculation faster, it able attain larger end-to-end speedups than any of the SEQUOIA trees from Figure (left), whose structures were chosen to maximize the expected number of generated tokens (not the speedup). The optimizer is also able automatically find the tree size that produces the largest overall speedup.
25

---

Table sweep tree configurations and their corresponding speedups of SpecInfer [28] on A100. The draft model is JF68M, and the target model is Llama2-7B in greedy decoding. The evaluated dataset is C4. The default tree configuration SpecInfer 5 8, which brings 3.45 speedup while SEQUOTA achieves x.04x speedup, surpassing all tree configurations below.
Wedth/Depth
2
4
16
32
64
128
3.09
3.14x
2.75x
1.94x
1.19x
2
2.95x
3.36x
3,46x
2.69x
1.74x
4
24%
3.14x
3.46x
3.41x
2.47x
8
1,88x
2,44x
3.14x
3.70x
3.03x
16
2,00x
2.55x
3.27x
3.14x
32
1.86x
2,57x
2.81x
64
1,2x
2.22x
128
1.68x
Table 6: A sweep of tree configurations and their corresponding speedups of SpecInfer (28 on A 100. The draft model JF68M, and the target model is Llama2-7B stochastic decoding. The evaluated dataset is C4. The default tree configuration in SpecInfer is 5 x 8, which brings 2.47 x speedup while SEQUOIA achieves 3.18x speedup. surpassing all tree configurations below.
Width/Depth
32
64
2.08
1.87
1.48x
1.11x
0.69
2.14x
2.2x
1.89
1.46x
1.07
1,99x
2.3x
2.28x
1.95x
1.53x
2.09
2.42x
2.42x
2.14x
16
1.78x
2.07x
2.41x
2.18x
32
1.78x
2.08
2.24x
64
1.73x
2.04x
128
1.6x
Table 7: A sweep of tree configurations and their corresponding speedups of SpecInfer (28 L40 offloading setting. The draft model Jama2-7B-chal and the target model 1amma2-70B-chie in stochastic decoding. The evaluated dataset is MT--Bench. SEQUOIA achieves 8.4 speedup, surpassing all tree configurations below.
Tree Config.
(16,48)
(24,32)
(32,24)
Speedup
5.2x
5.3x
5.5x
Draft: 11m, Target: Pythied 2b (Temp: 1.0)
Draft Pythia 2.8b, Target Pythia 12b (Tamp: 1.0)
Draft: Ulama2-7o 7b, Target: Llama2-70b I'lempe
Generated Tokens
Sequiia
Generated Tokens
Sequola (ours)
of Cenerated Tokens
15
6
Independennt Sequercess
Indap
Inde pendent Sequencess
Single Sequence
Single Sequence
Sing Sequence
Binary Tree
Binary Thee
11
Binary Tree
4
#
1.07 Figure 6: Number of generated tokens vs. free size: We plot the average number of tokens generated for different tree structures per decoding step the target model, as function of the tree size, for different draft and target model pairs. The number of generated tokens for SEQUOIA trees continues to grow with the tree size, while other tree structures asymptote.
10a
107
100
10a
1.0
10a
10a
10a
Size
As mentioned in Section 4.1 hardware-dependee amount of time it takes the target model to verify tokens divided by the time to verify token. In Figure we show the forward pass times for different models on different hardware, for different number of tokens As you can see, the forward pass times are roughly constant for low values of n, but then eventually start growing roughly linearly the value of at which ((n) begins to grow is model and hardware dependent. In general, this value of is lower for hardware that has
one of the inputs to the hardware aware optimizer is t(n), which the
26

---

Table 8: We compare the robustness of the SEQUOIa sampling and verification algorithm to the top-p hyperparameter, relative to SpecInfer and top-k sampling. We present total speedups an A100 GPU for the different methods (number of generated tokens in parentheses). We hold the tree structure fixed across methods, use JF68M as the draft model, and Llama2-7B as the target model.
Top-p
SEQUOIA (Ours)
SpecInfer
sampling
0.8
2.14x
2.35x(2.93)
2.43x(2.90)
0.9
2.61 (3.27)
2..2x(3.01)
2.27x
(3.26)
2.55x(3.10)
2.12x(2.44)
Sequola's Hardware Awareness
2.75
Speedup
2.25
2,00
1.75
Sequoia optimized tree (A100)
1.30
Sequola optimizer (A100)
Sequoia optimized tree (L40)
1.25
Sequola optimizer (L40)
1.00
16
64
128
256
532
Tree Size
Figure We compare the wall-clock time speedup of SEQUOIA trees of various sizes (orange lines)-chosen to maximize the # generated tokens-wite the speedup of the trees selected by the hardware-aware tree optimizer (horizontal green (ines)-choseed L40 GPUs. The optimizer can select the optimal tree size and depth for each type of hardware; by limiting the depth of the tree it can make speculation faster and thus attain larger speedups than the trees with unconstrained depth (orange lines).
maximize speedup on 1100 and
Forward Pass Time
6,225
Llama2-7h (A100)
Time (in seconds)
Llama2-70 (L40)
0.175
Llama2- 13b (A100)
0.150
Vicuna-33b (A160)
0.100
6.075
0.23
2
16
32
64
128
256 512
Input Length
Figure 8: Forward pass times for different model/hardware combinations function of the number of tokens n being processed. We use these values to choose the optimal tree.
higher ratio of bandwidth (between GPU HBM and SRAM) to FLOOPS, because it is less memory bound).
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: N/A
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in Appendix B
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged create separate "I "Liimitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
For each theoretical result, does the paper provide the full set assumptions and a complete (and correct) proof?
Question:
Answer: [Yes]
28

---

Justification: All theoretical results are proven in Appendix F and all assumptions are defined in S
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question:
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: In our supplementary zip file, we provide all code and evaluation datasets used, along with a README with instructions. We use public checkpoints for all draft and target models, public data for all evaluations, and report the hardware and hyprrparameters used for each experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-souree dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
29

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, we provide a zip file with the code and data needed to reproduce our experiments, well as README with instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/guides wwweeeummisisiooooooooooooooo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ httpcccppppp.cc.eceeeee pttp:puulllguuuu gew.c//g//////eeeeeicoooiiieiee Cttee/mooeemmmiccicc inniuummisssss iitimiission wssssssoosssiio onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and basclines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We share our evaluation datasets, hyperparameters, and code. Our paper is about inference, so we do not perform training.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not reported due to computational expense.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
30

---

The method for calculating the error bars should be explained (closed form formula, call library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors). the mean.
should be clear whether the error bar is the standard deviation or the standard error of
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis
of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time execution) needed reproduce experiments?
Answer: [Yes]
Justification: We discuss computational resources used for experiments Section 4 For on-device experiments, we have reported the GPU (L40 and 1100-PCIE-80G) and for offloading experiments, we have reported the GPU (L40) and PCIE4 (31.5GB/s).
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics http:://wwwriiseccccpc/////aaaaa
Answer: [Yes]
Justification: Our paper relates to efficient inference for existing models, not to training models with new functionality.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special considera- tion due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: YYs]
Justification:
See Appendix A
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
31

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimesss considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly. harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release new data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite the papers that introduced the models and data used in our work.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, bataaetss.paperssitt paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
assets are released,
32

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
We include README along with our code reproduce experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the matasettcodemmodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our paper does not include experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "vcpuxrZMhn", "reviewer": "Reviewer_uMCB", "summary": "In this paper, the authors propose a novel speculative decoding algorithm to accelerate LLM generation. By leveraging the positional acceptance assumption and dynamic programming, they can determine an optimal tree topology with the tree size and depth. The experiments demonstrate that the proposed method outperforms previous works across various settings.", "questions": "1. What is the standalone throughput of the draft and target models under different configurations? This information would help readers understand where the speedup comes from.\n2. How do you determine the best configuration of SpecInfer for comparison?\n3. How accurate is the acceptance rate vector measuring with 200 examples?\n4. Should the dynamic programming algorithm also consider the standalone throughput of the target and draft models? For instance, if the draft model is exactly the same as the target model, each element in the acceptance rate vector would be close to one, as the draft model can generate the same output as the target model. In this case, the tree will keep growing, but the more tokens the draft model generates, the slower it will become.", "limitations": "Please refer to the previous sections.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow.\n2. The proposed method is supported by robust theoretical analysis and algorithm design.\n3. Strong and comprehensive empirical results validate the proposed methods.\n\nOverall, this paper demonstrates novelty, soundness, and a significant contribution to the field.", "weaknesses": "1. The experimental setup for offloading is not clearly explained. It is unclear if the draft model is placed on a GPU while part of the target model is on the GPU and the other part on the CPU. If this is the case, the speedup is understandable since the throughput of the target model would be very low, and the draft model can run very fast.\n2. The comparison with the SpecInfer algorithm may not be fair. In Table 1, the size of the SpecInfer tree is 5x8=40, which is much smaller than the Sequoria tree. On the other hand, in Table 2, the size of the SpecInfer tree is 16x48=768, the same as the Sequoria tree. However, the length of SpecInfer would be very long (48) in this case, which seems impractical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review. We are glad that the reviewer found our work **easy-to-follow** and having **comprehensive empirical results as well as theoretical analysis**. We have tried to carefully address your questions. We hope the reviewer can consider raising your score in light of our response.\n\n### Q1: Clarifying the offloading setting \nThank you for pointing out our unclear description. In our offloading setting, we performed a layer-wise offloading for the target model (default setting of deepspeed-zero) and the draft model is on-device.  So your understanding is correct, in this setting, the draft model is very fast (24.2ms) compared to the offloaded target model (5.7s).  With Sequoia, we can accelerate offloading based decoding from 5.7s/token to 0.6s/token, which is more tolerable for running a large model on a consumer GPU. Furthermore, the setting of offloading (a big gap between FLOPs and memory bandwidth) also simulates the trend of future hardware, as shown in Figure 1(a).  \n\n### Q2: Comparison with SpecInfer\nThank you for your question about our SpecInfer baseline. Below we show, through 3 sets of experiments, that Sequoia outperforms SpecInfer when we perform thorough sweeps for the SpecInfer tree configuration:\n\n**(1) Sweep of SpecInfer tree structure**\n\nHere, we use JF68M as the draft model, and Llama2-7b as the target, and sweep a very wide range of SpecInfer tree structures (for both greedy and stochastic):\n\nGreedy Decoding (T=0.0):\n\n|Width/Depth| 1       | 2       | 4      | 8      | 16    | 32    | 64     | 128  |\n|---------|----|----|----|----|----|----|----|----|\n|1        | N/A| N/A| N/A|3.09x|3.14x|2.75x|1.94x| 1.19x|\n|2        |N/A | N/A|2.95x|3.36x|3.46x|2.69x|1.74x|    |\n|4   \t    |N/A |2.40x|3.14x|3.46x|3.41x|2.47x|    |    |\n|8 \t    |1.88x|2.44x|3.14x|**3.70x**|3.03x|    |    |    |\n|16 \t    |2.00x|2.55x|3.27x|3.14x|    |    |    |    |\n|32       |1.86x|2.57x|2.81x|    |    |    |    |    |\n|64       |1.92x|2.22x|    |    |    |    |    |    |\n|128      |1.68x|    |    |    |    |    |    |    |\n\nStochastic Decoding (T=0.6):\n|Width/Depth| 1       | 2       | 4      | 8      | 16    | 32    | 64     | 128  |\n|---------|----|----|----|----|----|----|----|----|\n|1        | N/A| N/A| N/A|2.08x|1.87x|1.48x|1.11x| 0.69x|\n|2        |N/A | N/A|2.14x|2.20x|1.89x|1.46x| 1.07x|    |\n|4   \t    |N/A |1.99x|2.30x|2.28x|1.95x|1.53x  |    |    |\n|8 \t    |1.73x|2.09x|2.42x|**2.42x**| 2.14x |    |    |    |\n|16 \t    |1.78x|2.07x|2.41x|2.18x|    |    |    |    |\n|32       |1.78x|2.08x|2.24x|   |    |    |    |    |\n|64       |1.73x |2.04x  |    |   |    |    |    |    |\n|128      |1.61x | | ||    |    |    |    |\n\nSequoia attains speedups of 4.04x (greedy) and 3.18x (stochastic), outperforming all tree configurations of SpecInfer, including 5x8 tree (3.45x greedy, 2.47x stochastic).\n\n**(2) More SpecInfer results for A100**\n\nFor on-device settings, we add the results for the 8x8 tree and 16x8 tree (SpecInfer) as follows,\n\nGreedy Decoding (C4, T=0)\n|Draft|target|  Tree Config |   Sequoia  |  SpecInfer(5x8)   | SpecInfer(8x8)  |  SpecInfer(16x8) |\n|----|----|----|----|----|----|----|\n|JF68M| Llama-2-7b|     (128,10)    |**4.04x**|    3.45x|   3.70x| 3.16x|\n|JF68M  |  Llama-2-13b  |    (64,9)      |  **3.73x** | 3.30x |             3.10x| 2.4x|\n|SL1.3B|     Vicuna-33B  |      (64,6)     | **2.27x** |          1.83x| 1.73x|1.45x|\n\nStochastic Decoding (C4, T=0.6)\n\n|Draft|target|  Tree Config|    Sequoia  | SpecInfer(5x8)   | SpecInfer(8x8)  |  SpecInfer(16x8)  |\n|----|----|----|----|----|----|----|\n|JF68M| Llama-2-7b| (128,7)  | **3.18x**|    2.47x|   2.45x|  2.18x|\n|JF68M  |  Llama-2-13b  |  (64,7)  |**3.19x**  | 2.48x |             2.42x|1.81x|\n|SL1.3B|     Vicuna-33B  |   (64,6)   |**2.16x**     |          1.64x| 1.52x| 1.32x |\n\nSpecInfer’s performance already degrades by enlarging the tree from 5x8 to 8x8. For SpecInfer, although the accepted tokens will marginally increase, the cost of verification/draft proposing will increase more. \n\n**(3) More SpecInfer results for L40 offloading**\n\nIn Table 2 of the submission, we compare Sequoia trees of size 768 to SpecInfer trees of size 768, composed of 16 independent sequences of length 48 (\"16x48\").  Here we additionally compare to SpecInfer trees of shape 32x24 and 24x32:\n\n|Draft|target|  Tree Config| Sequoia | SpecInfer(16x48) |SpecInfer(32x24)|SpecInfer(24x32)|\n|----|----|----|----|----|----|----|\n|Llama-2-7b| Llama-2-70b|  (768, 18)|  **8.4x** (9.91) | 5.2x (7.03)|  5.5x (6.82) |  5.2x (6.66) |\n\nWe will include a larger sweep in the revised version (these experiments are time consuming and require specific CPU/PCIEs that are often not available on cloud servers). Thank you for understanding!\n\n### Q3: Standalone throughput of the draft and target models\nThank you for pointing out this missing part. We will include the numbers in the revised version.\n\nJF68M:\t0.5ms\n\nLlama-2-7b:\t24.2ms\n\nLlama-2-70b:\t5.7s\n\nOur system is implemented in Huggingface with CUDAGraph and Static KV Cache (not as optimized as frameworks such as vLLM and deepspeed).\n\n### Q4: Accuracy of acceptance vector measurement\nEmpirically, this measurement is accurate. Below, we show that when we measure the average acceptance rate vectors across 10 different groups of 200 prompts each, the variance across these groups is quite small:\n\nSetting: JF68M for Llama-2-7b, CNN, T=0.6, width=8\n\n- Variance Vector: [0.0067, 0.0030, 0.0024, 0.0015, 0.0010, 0.0011, 0.0008, 0.0007]\n- Acceptance rate Vector: [0.5608, 0.1077, 0.0539, 0.0343, 0.0236, 0.0186, 0.0146, 0.0122]\n- Relative Error [1.2%, 2.8%, 4.4%, 4.5%, 4.2%, 5.9%, 5.3%, 5.4%]\n\n### Q5: dynamic programming algorithm should consider draft/target throughput\n\nYes. We discussed this in Section 4.1 (Hardware Aware Optimizer). In the case you mentioned, the optimizer will choose the shallowest tree (depth = 0) even if the acceptance rate is high, which means we do not use speculative decoding at all.", "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": "yq1OPzesGh", "reviewer": "Reviewer_qoEg", "summary": "This paper proposed an improvement on the tree-based speculative decoding methods to make the accepted tokens scale roughly in logarithm to the number of tokens generated by the draft model.\n\nThe author provided theoretical and empirical justifications for the tree construction and verification procedures.  The experiments shows this method has a good speedup over naive method, and it can generate more tokens each time.", "questions": "1. Could the author provide more reason why they don't compare with multiple draft model version of SpecInfer?\n2. Could the author provide more justification for the validity of the positional acceptance assumption?  What's the impact of this assumption theoretically and empirically?  What is the distribution being used if the acceptance probability does not dependent on the token t?", "limitations": "The limitations are acknowledged but not fully addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper has a strong theoretical guarantee for the scalability.\n\n2. The method works for different scenarios with different temperature. \n\n3. The dynamic programming problem can be pre-computed offline.", "weaknesses": "1. The differene with existing tree-based method in algorithm is marginal.\n2. The speedups are compared against naive methods.  The speedup over SOTA is not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review. We are glad that the reviewer found our work to have strong theoretical guarantees for scalability and also have good empirical results. Also thanks for noticing that our dynamic programming algorithm can be pre-computed offline. We have tried to carefully address your questions. We hope the reviewer can consider raising your score in light of our response.\n\n### Q1: Differences between Sequoia and existing tree-based methods\n\nThank you for raising this question.\n\nSequoia is designed to be a scalable and robust speculative decoding method that can yield large speedups in settings where the speculation budget is large (e.g., small batch serving, and offloading).  In these settings, we show how we can optimally construct very large trees (e.g., 128 tokens for on-chip, and 768 for offloading), and that the number of accepted tokens keeps growing as the tree size grows—in Figures 1,4,6 (and theorem 3.6) we show that the number of accepted tokens can grow roughly logarithmically with the number of speculated tokens in the tree. We believe that Sequoia could be even more powerful on future hardware—the gap between computation and memory bandwidth is getting higher (see Figure 1), thus allowing a larger speculation budget.\n\nPrevious works like SpecInfer, Eagle, and Medusa apply shallow and small trees without studying the problem of scalability.  By leveraging Sequoia’s tree search algorithm, our empirical results show that Sequoia scales well to arbitrary tree sizes. On the offloading setting on L40, which has a large budget, Sequoia can outperform SpecInfer by 51% on average.\n\nIn our work, in addition to improving the structure of the tree, we show that an improved sampling and verification algorithm can outperform others (SpecInfer, TopK) in terms of scalability and robustness. As described in Figure 4 and Table 5 in appendix, we can see that Sequoia achieves the largest speedups across all temperatures, attaining up to **1.65×** and **1.27×**  speedup relative to SpecInfer and top-k sampling, respectively.  \n\n\n### Q2: Speed up over SOTA\n\nThank you for raising this issue. In the last columns of Table 1/2, we have presented the speedups of SpecInfer, which is a very strong baseline. \n\nIn Table 1, we show that compared to SpecInfer, Sequoia attains speedups of 5% to 30% in the A100 on-chip setting (avg 22%). In Table 2, we show that Sequoia attains speedups over SpecInfer of  36% to 62% in the L40 offloading setting (avg 51%). More A100 on-device results can be found in Table 4 in appendix. We will add relative speedups compared to SpecInfer in the revised version.\n\nIn addition, since our method does not improve/train draft models, we only compare with draft model agnostic baseline. And the draft model improvement methods, like Eagle, Glide, Medusa are orthogonal to us and can be combined to achieve a better performance. \n\n\n### Q3: Reasons for not comparing with multiple-draft version of SpecInfer\n\nThank you for raising this problem! We have the following three reasons.\n1. *Draft model availability*: Often only a single draft model is available (e.g., Llama3-8B as a draft model for Llama3-70B), and it would thus require significant time/energy for practitioners to train additional draft models.\n2. *Performance*: As compared in [SpecInfer](https://arxiv.org/pdf/2305.09781v3) (Appendix A, Table 4), most of the time one draft model outperforms multiple draft models.\n3. *System*: SpecInfer serves each draft model on one GPU. However, every experiment in Sequoia is conducted on a single GPU, which means if we want to use the multiple-draft version, we need to run these draft models sequentially. This will further reduce the performance of the multi-draft version of SpecInfer.\n\n\n### Q4: Positional Acceptance Assumption\n\n**Validity of the positional acceptance assumption**\n\nThe positional acceptance assumption states that the probability of a verification algorithm\naccepting a token $t$ which is the $k^{th}$ child of an already accepted token depends only on the value of $k$. This is a simplifying assumption, given that the probability of a specific token getting accepted additionally depends on the token and context. However, we can consider the average acceptance rates, across many tokens/contexts, for sampled tokens, as a function of their position $k$.  In practice, we observe that this average is quite stable. For example (JF68M for Llama-2-7b, CNN, T=0.6, width=8), we show that when we measure the average acceptance rate vectors across 10 different groups of 200 prompts each, the variance across these groups is quite small..\n\n- Variance Vector: [0.0067, 0.0030, 0.0024, 0.0015, 0.0010, 0.0011, 0.0008, 0.0007]\n- Acceptance rate Vector: [0.5608, 0.1077, 0.0539, 0.0343, 0.0236, 0.0186, 0.0146, 0.0122]\n- Relative Error [1.2%, 2.8%, 4.4%, 4.5%, 4.2%, 5.9%, 5.3%, 5.4%]\n\n\n**Impact of positional acceptance assumption**\n- *Theoretically*:  we pointed out that, in tree based speculation methods, the probability of getting accepted is a function of the position of the speculated token. As a result, the optimal tree cannot be a balanced one (e.g. k-independent chains). This is also the intuition why we need and why we can search for an optimal tree. \n- *Empirically*: With expected acceptance probability for each position (i.e. our acceptance vector, vector P in algorithm 1), we can pre-compute expected accepted tokens to search for the optimal tree structure (algorithm 1).\n\n     For each experiment, we sample a subset of 200 sentences to calculate acceptance vectors and feed into algorithm 1 for tree searching.", "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": "srYr7Zbsi3", "reviewer": "Reviewer_XEn9", "summary": "The paper proposes SEQUOIA, an algorithm designed to improve the efficiency of serving large language models (LLMs) through scalable and robust speculative decoding. The SEQUOIA algorithm introduces a dynamic programming method to construct optimal token trees for speculation, enhancing scalability. Additionally, a novel sampling and verification method ensures robustness across various decoding methods (top-k sampling, top-p sampling, temperature, ...). Empirical results demonstrate 4.04x speedup in a small model and 9.5x speedup in a large model with offloading inference.", "questions": "- In Figure 4, why SpecInfer shows the opposite trend compared to Sequoia & Top-k sampling? In other words, Why it shows higher speedup when the temperature increases?\n- It seems that SEQUOIA needs to conduct the dynamic programming algorithm every iteration. How long does that process take?", "limitations": "No additional limitations exist.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The simplest tree structure is a single chain (i.e., list) and the most complicated tree structure is k-ary full tree. SEQUOIA finds sweet spots between them, utilizing dynamic programming\n- SEQUOIA maintains high hit-ratio across different sampling methods. This robustness make speculative decoding more practical.\n- Paper presents extensive experimental results including ablation studies.", "weaknesses": "- Building optimal tree is more time-consuming than previous approaches (k-ary tree or k-independent sequences)\n- Due to this, the batch size that can benefit from speculation might be much smaller compared to other methods", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review. We are glad that the reviewer appreciates our dynamic programming based tree search algorithm as well as the robustness of sampling and verification algorithms. We have tried to carefully address your questions. We hope the reviewer can consider raising your score in light of our response.\n\n### Q1: Time cost for dynamic programming and building optimal tree\n\nThank you for raising this concern. The time for building a Sequoia tree has two parts:\n\n- *Offline Dynamic Programming*: Fixing the draft/target model and the workload, our dynamic programming can be conducted before inference (or offline). It is a one time preprocessing effort and does not introduce extra overhead during inference. Furthermore, our dynamic programming can run very fast, taking less than 20s to generate a tree as large as 1536, and less than 5s for trees of size 64 or 128. \n\n- *Tree building during inference*: Time for building the tree is decided by the inference cost of the draft model and the depth of the tree (as we analyzed in Section 4.1: Hardware Optimizer). In this sense, building a Sequoia-optimal tree of depth D should cost the same time as building a k-array tree of depth D.\n\n### Q2: Sequoia’s performance at various batch sizes\n\nThank you for this question. As you have correctly pointed out, Sequoia gives the largest gains for small batch sizes. This is because at small batch sizes, decoding is more memory-bound, and thus one can afford to verify a large tree without increasing verification time; by discovering the optimal structure for this large tree, Sequoia gives large speedups over baselines. Conversely, for larger batch sizes, the speculation budget is smaller, and the relative gains of Sequoia relative to other speculation tree structures (chains, k-ary trees, etc) is much smaller—we show this in Figure 1(a). In a real inference system with continuous batching, one could use Sequoia to determine the optimal tree for any batch size (as in Liu et al, 2024 [1]), thus attaining strong performance across the board.\n\n\n[1] Xiaoxuan Liu, Cade Daniel, Langxiang Hu, Woosuk Kwon, Zhuohan Li, Xiangxi Mo, Alvin Cheung, Zhijie Deng, Ion Stoica, Hao Zhang. Optimizing Speculative Decoding for Serving Large Language Models Using Goodput. CoRR abs/2406.14066, 2024.\n\n\n### Q3: Different trends for SpecInfer, Top-K and Sequoia\n\nThank you for raising this thoughtful question!\n\nIn short, SpecInfer’s performance gets worse at low temperature, whereas Sequoia and Top-K sampling improve at lower temperatures, because these methods use different sampling and verification algorithms. SpecInfer uses sampling with replacement, Top-K uses top-k sampling and Sequoia uses sampling without replacement. As a result, at low temperatures SpecInfer is the only method that would repeatedly sample an incorrect token, leading to poor performance.\n\nWe will now give a more detailed answer to your question, by first discussing how top-k sampling and SpecInfer sampling compare at both low and high temperatures, and then explaining how Sequoia is able to get “the best of both worlds” and perform well across both low and high temperatures. \n\n**In a low temp regime**, the token with largest probability in the target model’s output will take up over 95%. This token is very likely to appear in the top-k tokens of draft models (even if it is not the top-1 token). In this case, Top-K sampling can easily get accepted. However, for SpecInfer’s sampling with replacement, since the temperature is low, SpecInfer will keep drafting the same token. When the drafted token is not exactly the top-1 token of the target model, SpecInfer will get rejected. To summarize, in the low temp regime, Top-K requires the top-1 token of target model is among the top-k tokens of draft model, while SpecInfer requires the top-1 of the target model to be exactly the same as the top-1 of the draft model, leading to worse performance. Top-K method benefits from its cover property (Section 3.2.2). \n\n**In a high temp regime**, let’s consider an extreme case (temp $\\rightarrow \\infty$), i.e. the output of target model and draft model are totally random. In this case, it’s nearly impossible for Top-K to get accepted, as its total acceptance chance is just K / V, where V is the vocabulary size and K is the number of proposed tokens. However, for SpecInfer, all the draft tokens will be accepted, since the target and draft token probability is the same (1/V). SpecInfer method benefits from its optimal transport property (Section 3.2.2). \n\n\nSequoia with sampling without replacement, behaves more like Top-K in low temp and more like SpecInfer in high temp as it has both cover property and optimal transport property. That’s the reason why Sequoia is able to perform well across a wide range of temperatures. The trend of acceptance rates of three methods is shown in Figure 3, which verifies our above claims.", "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": "eUFRxhqQvS", "reviewer": "Reviewer_yRtD", "summary": "This paper introduces a speculative decoding method Sequoia, which uses a novel sampling and verification method that outperforms prior work across different decoding temperatures. The speedup of Sequoia is large.", "questions": "I notice that the speedup of speculative decoding decreases as the temperature grows (and in many previous works). Do you think this problem is solvable?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper discuss the proposed method in a detailed way. The algorithm is novel and achieves large speedup.\n2. This paper have a thorough and sound evaluation section. Sequoia outperforms SpecInfer in various datasets and temperature settings.", "weaknesses": "1.  Sequoia shows linear speedup with the tree size growing exponentially. However, it is less useful in batch serving (e.g., vllm). Do you think this problem can be solved by integrating a more efficient draft token proposing method (e.g., Medusa/Eagle) with the proposed Sequoia?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review. We are glad that the reviewer found our algorithm novel and the evaluation thorough and sound. We have tried to carefully address your questions. We hope the reviewer may consider raising their score in light of our response.\n\n### Q1: Batch serving setting\n\nThank you for this question. As you have correctly pointed out, Sequoia gives the largest gains for small batch sizes. This is because at small batch sizes, decoding is more memory-bound, and thus one can afford to verify a large tree without increasing verification time; by discovering the optimal structure for this large tree, Sequoia gives large speedups over baselines. Conversely, for larger batch sizes, the speculation budget is smaller, and the relative gains of Sequoia relative to other speculation tree structures (chains, k-ary trees, etc) is much smaller—we show this in Figure 1(a). In a real inference system with continuous batching, one could use Sequoia to determine the optimal tree for any batch size (as in Liu et al, 2024 [1]), thus attaining strong performance across the board. Furthermore, as you correctly pointed out, Sequoia can be combined with more powerful draft models (like Eagle) to attain even larger speedups (discussed briefly in Section 3.1.1).\n\n[1] Xiaoxuan Liu, Cade Daniel, Langxiang Hu, Woosuk Kwon, Zhuohan Li, Xiangxi Mo, Alvin Cheung, Zhijie Deng, Ion Stoica, Hao Zhang. Optimizing Speculative Decoding for Serving Large Language Models Using Goodput. CoRR abs/2406.14066, 2024.\n\n### Q2: Performance decreasing with temperature\n\nThank you for your insightful question!\n\nIn this work, we use sampling without replacement to make the performance more robust across temperature. However, you are correct that decreasing is still observed when temperature goes up. Generally, high temperature means a higher degree of randomness, which is more difficult for draft models to guess. Improving the performance at higher temperatures is an interesting direction for future work—perhaps methods that better align draft and target models (e.g., via distillation [2]), or more advanced sampling algorithms [3, 4], could yield improvements here. \n\n[2] Zhou et al. DistillSpec: Improving Speculative Decoding via Knowledge Distillation. ICLR 2024.\n\n[3] Sun et al. Block Verification Accelerates Speculative Decoding. Efficient Systems for Foundation Models workshop, ICML 2024.\n\n[4] Qin et al. Multi-Token Joint Speculative Decoding for Accelerating Large Language Model Inference. Arxiv 2024.", "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:
We thank all the reviewers [**R1** (uMCB), **R2** (qoEg), **R3** (XEn9), **R4** (yRTd)] for their thoughtful and highly supportive feedback! We were glad that the reviewers found the work **novel and meaningful** [R1,R3,R4], believed our theoretical analysis was **detailed, robust and strong** [R1, R2, R4], felt the experimental results were **sound and showed good speed ups** [R1, R2, R3, R4], and found the presentation **easy to follow** [R1].  We have updated the paper to incorporate constructive suggestions, which will show in the revision. We summarize the major changes:

1. **Comparison with SpecInfer/Baselines** [R1, R2]: 
    - We added relative speed up numbers over SpecInfer, achieving avg 22% for A100 and 51% for offloading.
    - We swept a wide range of tree configurations for SpecInfer for a more fair comparison. We added this part as an ablation.

2. **Positional Acceptance Assumption** [R1, R2]: To further clarify this assumption and its correlation with our algorithm, we added a discussion about the acceptance rate vector we measured for each experiment and its variance (1~5%, indicating the measurement is accurate).

Meta-review: The reviewers unanimously praise the paper's strong theoretical guarantees, novelty and extensive evaluation.
Furthermore, the reviewers either acknowledged the rebuttal addresses their concerns (uMCB) or that it is detailed and did not follow with more comments (yRtD). Given that and the initial support for the paper, there does not seem to be any outstanding issues regarding the paper. I have read it quickly and it appears to be of high quality and, importantly, the authors include discussion about limitations in the appendix. Considering all the things, and especially its theoretical grounding and resulting strong performance, it is a clear candidate for acceptance.

The only ask for the authors would be to incorporate as much as possible from the review process into a revision of their paper, since I expect a lot of those things would be interesting for potential readers as well.
Decision: Accept (spotlight)