A Theoretical Perspective for Speculative Decoding Algorithm
Authors: Ming Yin
Minshuo Chen
Kaixuan Huang
Mengdi Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: probabilistic analysis
theory for large language models
Primary area: other

Abstract: Transformer-based autoregressive sampling has been the major bottleneck for slowing down large language model inferences. One effective way to accelerate inference is Speculative Decoding, which employs a small model to sample a sequence of draft tokens and a large model to validate. Given its empirical effectiveness, the theoretical understanding of Speculative Decoding is falling behind. This paper tackles this gap by conceptualizing the decoding problem via markov chain abstraction and studying the key properties, output quality and inference acceleration, from a theoretical perspective. Our analysis covers the theoretical limits of speculative decoding, batch algorithms, and output quality-inference acceleration tradeoffs. Our results reveal the fundamental connections between different components of LLMs via total variation distances and show how they jointly affect the efficiency of decoding algorithms.

A Theoretical Perspective for Speculative Decoding Algorithm
Ming Yin* Princeton University my0049@princeton. edu
Minshuo Chen Northwestern University minshuo. chen@morthwesteem..co edu
Kaixuan Huang Princeton University kaixuann@pprncetton. edu
Mengdi Wang Princeton University mengdiw@princeton. edu
Abstract
Transformer-base autoregressive sampling has been the major bottleneck for slowing down large language model inferences. One effective way to accelerate inference Speculative Decoding, which employs small model sample sequence of draft tokens and a large model to validate. Given its empirical effec- tiveness, the theoretical understanding of Speculative Decoding is falling behind. This paper tackles this gap by conceptualizing the decoding problem via markov chain abstraction and studying the key properties, output quality and inference acceleration, from a theoretical perspective. Our analysis covers the theoretical limits of speculative decoding. batch algorithms, and output quality-inferenc acceleration tradeoffs. Our results reveal the fundamental connections between different components LLMs via total variation distances and show how they jointly affect the efficiency of decoding algorithms.
Introduction
The recent surge of scaling Transformer models has led to the flourishing of AI, where success has been witnessed in wide areas such natural language [39, 1J, computer vision [12, 17]. video generations [3, 19], and robotics [8, 31]. In the meantime, the decoding process also becomes more and more consuminn the model size scales up. This is mainly due to the autoregressive nature of Transformers, where each generated token also serves as the input for future generations. As result, decoding 7 tokens would take T forward passes of the full model.
recent effort to tackle this challenge is speculative decoding (SD) [10, 24], where the autoregressive sampling is performed on small draft model and the large language model verifies tokens generated by draft model to decide whether should be accepted/rejected. Once a token rejected, the generation process will start from the most recently accepted token, until full response is completed. Speculative decoding achieves 2-2.5x LLM inference speedup empirically, while preserving the quality of generation.
Subsequently, numerous studies [26, 25, 23, 46] have expanded this methodology, enabling further inference acceleration. Intuitively, for speculative decoding, when the generation distribution of small model p and large model q are close to each other, decoding is faster (since less rejection occurs), and when the distribution overlap between p and is small, the opposite happens. However, precise understanding of inference accelerating given the small model and large model remains elusive. This motivates to ask the following question:
Coorespondence to: my00496princeton edu, nengdiw@princeton. edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

What is the fundamental limit for inference acceleration via speculative decoding? ? In addition, what the best trade-ofy off between inference acceleration and output quality for speculative decoding?
His first Final was in Rio. Brazil. 2014.
His first Final was in Lusall, Gatar, 2024.
and
Q: When and where was Messi's first World Cup Finalh
where was Messi's first Cup Final+
Figure I: Left: Standard Regresegree Decoding (Algorithm 3) v.s. Right: Speculative Decoding (Algorithm 1), where large model is used to validate the responses of the small model.
In this paper, we answer these questions from the theoretical lens. Our contributions are summarized as follows.
We formalize the decoding problem through the Markov Chain abstraction that establishes the theoretical setup. We draw the connection runtime # rejections and use it to measure efficiency. We derive the exact formula, fully characterized by distribution p and q, for the expected rejections [[NNej] for Speculative Decoding (Theorem I). This renders a theoretical reference for understanding the acceleration rate [/E[N
Next, to understand whether Speculative Decoding be further improved, generalize it to class of rejection-basee based algorithms 2 where probability by and distribution Pa can be customized. We prove in Theorem 2 that any unbiased algorithm cannot have fewer rejections than Speculative Decoding. This indicates its optimality among the class, and having fewer rejections needs to suffer quality loss requires extra information.
Furthermore, we consider a batch version of Speculative Decoding (Algorithm that utilizes multiple draft sequences. We show our batch algorithm is unbiased. We derive the expected rejections that is fully expressed by p and y and exhibit the improvement over non-batch version in Theorem 3. We provide examples and detailed discussion to explain how our theory characterize the improvement.
In section 4, we shift from unbiased algorithms and study the tradeoff between inference cost and quality degradation. We formulate this into an optimization model (1). Theorem 5 established a linear Pareto front that characterizes the tradeoff between inference cost and quality degradation (Figure 4). A simple experiment in Section 4.2 is also consistent with our theoretical finding.
Last but not least, technical results involve novel analysis, for instance, the design of V+, V_ in the lower bound proof C and the iterative computation for f in D.1. They are the first of its kind and consist of our technical contributions. We provide proof sketch section in Appendix A.
1.1 Related works
Speculative Decoding and applications. Speculative execution, where performing speculative work can expedite computation on parallel machines by allowing certain tasks to commence before their necessity is confirmed, can date back to [9. 15]. Recently. [10, 24] formalize this idea with rejection sampling based design for LLM Decoding and achieve multiple-time inference acceleration compared to vanilla auto-regressive decoding. There are fruitful studies [41, 26, 25, 37, 23, 46, 32, 27, 18, 4, 34, 2, 30, 43, 11, 42, 45, 29, 35, 5, 44, 40, 20] since then, and they improve speculative decoding from different angles such as online updating [25], multiple candidates [45], retrieval technique [18), Multimodality [16] even decoding without draft models [14, 6].
Theoretical endeavor for Speculative Decoding. There are also works that study the theoretical properties for speculative decoding (SD). In particular, [37] considers speculative decoding from the optimal transport perspective and show it optimal in the single token regime. further extends to the k multiple draft token setting and formulates the optimal transport solution via linear programming

---

with exponential in k computation time. An approximate sequential selection algorithm is also proposed with linear time. [2] further proposes the improved plan, and [36] extends [37] to the block-level optimal transport for SD. [34] investigates the synergy between draft length and batch size for Speculative Decoding and formulate the optimal speculation length as the root of a polynomial equation. [26] proposes the SpecInfer, a batch algorithm that uses small speculative models to form the token tree, and proves its output matches the distribution of the large model. [45] considers batch speculative decoding without replacement to avoid repeatedly sampling rejected tokens and proves it keeps the decoding quality. Nevertheless, the findings for inference acceleration of these works are mostly empirical, lacking theoretical guarantees.
Algorithm 1 Speculative Decoding [10, 24] Algorithm 2 Framework for Rejection-basel Decoding
1: Input: Set probability b, min %
1: Init: Horizon Z', models qt, Pt. Lookahead K = T.
and the distribution P. [g: pr]++ Algorithm 2.
Prompt Ty. n = 2: Require: Probability b, distribution Pt.
2: Require: pc(-) = Pe 1in- -
while < T do
(x(+) gr qr(-(21mm111 In)- Vt n.
4: for / = n 7 do
3: for = n : do
5:
Sample drafts 3. ~ pe (-(-1/11m-1 Bnct-1). end for
4: Sample
Uniform[0, 1].
6:
5: if < min (1, ((e) then
7:
Obtain the target logits in parallel for En.T as
((.)
qn g-(((x1mm-1), .... 9r(-|=im-11 In:T)
6: Accept with Fn Ft. +
8:
for n T do
7:
else
9:
Accept 2n ãn with prob. b, n nl + 1.
8:
Sample Un 19: - p (-).
10:
Else REJECTION:
9:
n+ 1. Break.
11:
Sample Fn distribution Ps. +
10: // Recall [9e- pcl+ in Section 2.1
Break.
11: end if
12:
end for
12:
end for
13: end while
2 Preliminaries
2.1 Background for decoding problems
In this section, we provide the mathematical formulation for decoding problems using Markov Chains, and we explain rugo-regressive models and speculative decoding algorithm based upon that.
Markov Chain Model for Decoding. We denote Zg as the prompt. 2 Fn is the n-th token output and T1.7 is the trajectory output by the algorithm with T to be the fixed decoding horizon. 3. Then any decoding algorithm can be characterized by a Markov Chain: state at is described by history To.t. the initial state is zo; the state transition P; maps state No.t to state To.++ In the context of decoding problem, the transition matrix is defined as P(r0++1 ( :- p(xe+ 1.). particular, we use p to denote the (conditional) distribution for the draft model that resembles small speculative model, and for the target model that represents large language model. We use [4 - p]+ + to denote the normalized distribution for max g(z) - p(x)), Vx E V with V being the token vocabulary. We also denote [g]] = Σ, (x)g(x).
Auto- Regreseveee Decoding. Consider sampling a trajectory 21.T from an rego-segressive model, where for the given F1mn-1, 11, the next token x,, follows the conditional distribution q. This decoding mechanism (Algorithm 3) is the prototype for Transformer-basee L.MSs (e.g. GPT-4). As mentioned in [29], the accuracy performance of Transformer--asse L.MSs has been shown scale with model size, with larger models demonstrating improved capabilities [22]. However, this improvement comes at the cost of higher latency during inference and increased computational requirements.
Speculative Decoding, Different from large models, small models are usually much faster at the inference stage. Consequently, we can use small model to perform auto-regressive sampling and assign large model as a verifier, where the goal of the large model is to check whether the
We use the abstraction æ := (V1, V2...., ( with ys 's heing the tokens in the prompt. In general, I is random variable. However, we append [EOS] tokens to keep the output length fixed.
3

---

token sampled by the small model should be accepted/rejected. Concretely, this procedure can be summarized into the following three steps:
Draft sampling: given the verified tokens 21m--1, the draft model obtains K sequential candidate tokens Tna++ K-1 via sampling from 11, [K - 1];
Conditioonal score compulation: given Enan+ K-1, computing the logits of the K tokens 11, i E [K - in parallel;
Token validation: Accept the candidate token ā. (as v.,) with some probability b, $ 1. If accepted, continue validate the next candidate T++1, otherwise reject and sample In from some designed distribution Pt.
The above process repeats until 21.7 are generated, and the whole algorithm is summarized as the general rejection-baat based decoding 2. Specifically, Speculative Decoding [10, 24] designs by := g((āa) and distribution P+(-) [d (-) (see Algorithm I and Figure 1).
m (r()e)
2.2 Problem Setup
Speculative Decoding has two key merits. First, it maintains output quality, meaning the output distribution by the algorithm is identical to the output distribution of the large model q, and we term distribution unbiasedness. Second, it has fast inference property since the auto-regressive sampling is performed on the small model and the target model only verifies. With (possibly) multiple draft tokens being accepted very round, Speculative Decoding can be much faster than direct decoding on large models, and its inference is bottlenecked by the parallel score computation q( (imm-1 &nn++s) n]. To highlight this, defined it the oracle call and make assumption based on that. Definition 1. We define one trigger of obtaining logits for Tn.T in Step 7 of 2 as one Oracle call.
i e [T
Assumption 1. We assume that: (1) compared to the large model, the computational cost of the draft/small model is negligible. (2) each oracle call has runtime O(1).
Remark 1. We assume the above only for the theoretical cleanliness. lookhead K- T in Algorithm 2. In other words. given Fin-1, instead of sampling the next K draft tokens Tn.n K 1,, we are allowed to sample until the end, i.c. Σn.T. In practice, Assumption 1(1) also holds true in many cases. One example of negligible-cost model z O n-gram models, and the empirical evidence in [24, 28] shows n-gram draft model speeds up inference pretty well. In addition, for summarization tasks where long sequences are likely to repeat, any draft model that reuses tokens from the context with matching prefix, is also cost negligible. Assumption 1(2) is also standard abstraction, since parallelization consumes (roughly) equal computation as for a single logit. It will consume more memory, but such aspect is beyond the scope of our theoretical study.
With negligible draft model. the
Metric for measuring efficiency. Desired algorithms should preserve the output quality and be efficient for decoding. To formalize, our theory aims to study the following quantities:
Inference acceleration; the ratio between the inference time of decoding large model q and the inference time of decoding the algorithm;
Output quality: the distribution bias between the algorithm and the large model distribution q. An algorithm maintains the output quality if it is distribution unbiased.
Rejections, and why consider it? A third metric for decoding is the number of draft tokens being rejected. With more draft tokens being accepted, the fewer rejections would occur. Therefore, algorithms with large number of rejections are slower than those with fewer rejections. This means Rejections serves as an alternative metric for the inference speedups. Throughout the paper, we use number of rejections for measuring inference acceleration.
To further motivate why choosing Rejections appropriate, we draw its connection to inference run- time. For Speculative Decoding, the runtime is dominated by the number of oracle calls (Definition 1). After each rejection (Step 10 of Step 7 of I), there is one oracle call, thus we obtain
inference time = # oracle calls # rejections.
Notice the runtime for reto-regeessive decoding (3) is T, therefore we have the relation: inference acceleration = T/# rejections. Based on this setup, we present our main results in next sections.

---

3 Analysis on Efficiency and Optimality for Speculative Decoding
We start with the following theorem at the beginning of the section. It covers output quality, which is measured by distribution bias, and expected number of rejections for speculative decoding. Its proof deferred to Appendix B.
Theorem 1. We have the following two results for Speculative Decoding.
(1) We define random variables R. {0. 1) that indicates whether the n-th token is rejected (with 1 being rejected). Here rejection meuns Line 7 of Algorithm executed. Then, the total number of rejections Naj- = _m== Rm. For Speculative Decoding (here TV denote the TV distance):
B[N Σ E. Ee (VVpn (in (19mm))))))
(2) The output distributions of Algorithm and the target model q are identical, i.e. for any outpur sequence v1.7 VL, the joint the distributions over JA. satisfies: (SD(T).)) q(xi.)..
The first part of Theorem 1, to our knowledge, is the first result that characterizes the expected rejection for speculative decoding sequence of length T using p and q. The second part of Theorem shows the distribution unbiasedness for SD, which has been presented in [10, 24]. There are three interesting indications:
If B|TV(pn gn) (-)=1m-11] 0 for all n, all tokens accepted and the accelerate rate =T:
for all n, all tokens are rejected and the accelerate rate 1, i.e. all T tokens are sampled from the large model g:
If EE[TV(p, gn) (-(=2imm)1)
In general, the accelerate rate for SD is T/ E
4n (-
Remark 2. [24] derive the expected number of token generated per run of Speculative De- coding as L/E[TV((, q)] for K 00. Their result equals T/ T/22 [TTV(pn, (-1221m11)) when (pTV (-)(-121mn1))))
identical for all n, and this is due their assumption that the acceptance rates 3 are i.i.d. In contrast, our guarantee holds for the case that allows the sequential dependence between different decoding steps.
Simulation. We also provide simulation of Speculative Decoding and compare with Theorem in the left panel of Figure 2(a) with horizon T 50, Pn. 9n, n = 1...., 50 are nonstationary Markoy Chains. The green line is the empirical average rejections among 100 N runs of Algorithm 1 and the orange line the theoretical value computed via Theorem 1. From the simulation, after 5000 runs the empirical average rejections converge our theoretical value 16.41. In this example, the acceleration rate is 50/ 16.41 = 3.05. The specifications of the simulation is included in Appendix F.
3.1 Optimality of Speculative Decoding
Now we have analyzed the efficiency of speculated decoding and provided mathematical characteri- zation of the number of expected rejections, which depicted by the TV distance and scales linearly with the inference time. A natural next-step question to ask is: Is there any other rejection-bass algorithm 2 that can do better? We answer this question in the next theorem.
Theorem (Inttance-dependent Rejection Lower Bound). For an instance := (p, q), where p. q stand for the distributions of the draft model and the target model respectively, defining the family of algorithms as F === [A A specification of Algorithm 2 that satisfies P,A. Vt (i.e. unbiased)). For an algorithm A. denote Nog as the number of rejections. Then we have the lower bound
inf AEF
Σ
E Brim-1ng [TV(pa on (1
'This is from their equation (1) that has 1/(1 - a) with = B(min(p, g)) and 1 E(min(p, q))
ETTV(p,)))
5

---

15.5
Coeoding
Toak Spei Dood
Expocted Rajectins
142
10.5
Exprodeed
18.4
13.8
The Wilen kabin M
Soudlopee K
Delr SpecDacoce K
Valee balin a
200
500
1000
1500
2003
Nanber of Box0wou.
Figure 2: The numeric instance in this figure chooses p, q to be nonstationary Markov Chains with horizon T 50. Left (a): A simulation of Speculative Decoding. The green line is the empirical average rejections among 100N runs and the orange line the theoretical value computed via Theorem 1. Middle (b): Batch Speculative Decoding simulations with batch M 4, 5. The green/purple lines are the empirical average rejections among 100N runs and the orange/pink lines the theoretical values computed via Theorem 3. Right (c): The scaling law of expected rejections for Batch SD as a function of M. It converges to a limit as M - co.
Takeaways. Via Theorem 2, the answer to the key question is: No rejection improvement can be made Algorithm by changing the acceptance probability b, and the distribution Pe if we wanr to keep the distribution unbiasedress. We point out that lower bound of Theorem 2 matches the complexity upper bound of Speculative Decoding given by Theorem This result confirms that speculative decoding is optimal in the class of all rejection-based methods.
The practical implication is that there is no need to tweak acceptance probability, as it will not make performance better. In the next Section 3.2, we will see that Speculative Decoding can be provably improved, long as one can decode and verify multiple sequence of tokens in parallel.
Connection to optimal transport. We mention [37] nicely consider maximizing the acceptance probability from the optimal transport perspective. For single token, the optimal transport cost is Ene min(p(æ), qx))) which corresponds to the optimal expected rejection TV(p, q). However, for the sequential 7' tokens, their Section 5,6 does not provide explicit formulation for optimal acceptance/rejections In this sense, their optimality result can be cast as a special case of ours. However, we do emphasis there are differences in the settings, where [37] consider the optimal transport and we study the class F.
3.2 Analysis for Batch Speculative Decoding
To further improve the provable efficiency, consider batch algorithms that extend the speculative
decoding with multiple candidate draft sequences. Most the existing works [32, 34, 26, 45, 21] formulates batch sequences via speculation tree structure. In particular, the representative work [26] propose the merged token tree structure that combines sequences with the same prefix. A depth-first search is designed for speculation to ensure the unbiasedness of the algorithm. In addition, [33] devise the parallel decoding structure that speculate the token of each responses given its previous tokens are accepted. Motivated by these works, we consider batch version of speculative decoding algorithm using a simpler parallel structure (Left of Figure 3). Our Algorithm 4 can be viewed as simplified approximation those batch algorithms. There are several differences that distinguish batch algorithm from the non-batch version. We highlighting them as follows.
Differencel: Oracle call. At the beginning of batch speculation, M draft sequences are generated in parallel as well as the corresponding logits g. This corresponds to Step 4-9 of Alg 4 and is defined as one oracle call which we assume have unit computation (1));
Difference2:
Speculation procedure. follows the DFS principle: If the first token of response is accepted, only that response will be speculated until rejection. For instance in the Left panel of Figure 3, if the token 'deep' is accepted, the algorithm will keep verifying token 'learn', 'ing' until rejection and the rest of sequences won't be examined; if 'deep' is not verified, then the algorithm will keep examing 'rein'. In this case, rejection happens only 'deep', 'rein' and 'atten' are all
'We mention batch drafting in parallel will cause more memory and arithmetic operations, but not computa-
tion time.

---

rejected. Once rejection happens, the process will restart. By this design, it still holds true that: inference time oracle calls rejections.
Again, we measure the output quality and rejections for the batch algorithm. The following main result (Theorem 3) provides the explicit characterization for rejections and batch improvement. Detailed proof's and discussions can be found in D.
What important components
0.2
So-10 51
Verify
Fein
ccar
1.00
3.25
aterro
aicn
0.00
0.75
Large Model Decoder
D.03
202
Figure 3: Left: Batch Speculative Decoding. Right: Batch Improvement Batch size M. Upper: Bernoulli distributions with = (er(..5). Lower: >~ Unif(V), q Unif(V') with r = V/V..
Theorem 3 (Unbiasedness and efficiency of batch SD). Recall the definition of Ru and Nug in Thm 1, and iteratively define: gm = 1qth -p]_, Vmn E [M] with q² = q being the target distribution. Then, for Batch Speculative Decoding 4. phachh (IITT) = (((1T)). VILT VT, Moreover,
B[N Σ Ean-- [V
E B (TV(g (3 Σ
[II TV(a" (x(mm)))))) 10-1
Batch Improvement
where (#1m)) == P( O (n-th draft token rejected)). I can be iteratively computed via p, q-
Takeaways. The expected rejection of Batch Decoding composes of two parts: (i) ΣnH [TV[ p]] which is the rejection that matches the non-bateh batch speculative decoding; (ii) the batch improvement (BI) which comes from our design and is always nen-nega.ive. To better understand how the batch
improvement scale with M, we instantiate the single token BI(q.p) TV[g.p) -I TV[q"", .r] with two simple examples.
Uniform Distribution. For the whole space V. let p be uniform distribution with support V and q be a uniform distribution over a subset of V with size V < V. Let V/V" = r. in this case V/V'. Its pattern is visualized in the lower right panel of Figure 3. The improvement converges to 1 - 1/r and is always positive as long as batch size is at least 2. Also, when the vocabulary size V scales up, i.e. goes up, the improvement is going to zero. This is not surprising, since the probability of draft sample to fall within in the support of target distribution is very small.
(I(Unif(VV"), Unif(V))
(1 - )) (1 1
Bernoulli Distribution. Suppose u 3 v and p Ber(u), 4 BI(Ber(v), Ber(u)) = Iu- el (1 W-1).. Its pattern is exhibited in the upper right panel of Figure Notice for both cases, the limiting batch improvement is TV(p, 9). which is only significant when p deviates from q. This provides the practical design heuristic: batch design reduce the number of rejections when the draft distribution and target distribution q are different from each other and won't 't make too much improvement when p and are close.
Ber(v). Then
significantly
Batch Simulation. The Middle panel of Figure 2(b) shows Batch Speculative Decoding simulations with batch M = 4, 5. The green/purple lines are the empirical average rejections simulated via Algorithm and the orange/pink lines are the theoretical values computed via Theorem The right panel of Figure 2(c) plots the rejection vs. batch size. In particular, the the black dot with coordinate The numeric example shows when M oc, [[N] O. Intuitively, this is partial due to, if the distribution mismatch between p and q is large,
(1, 16.41) represents the Speculative Decoding
7

---

TV[p.e]
0.4
Rejection Probas bilny
Rejection probaliitt
04
Migecbon TVp=-M.g
0.3
Attainable Region
0.3
0:2
0.2
Unattainable Region
TV(p.e]
0.1
0.1
0.0
Distribution Distance TV[F-1.u
0.0
Quality decrease measured by TVGpA02 g]
0.0
Over Acceptance Thresholde
0.1
0.2
0.3
0.4
Figure 4: Left (a): The Pareto Front between Rejection Probability (-(jeccct) vs. Distribution bias TV[PA, V/] For given rejection probability, the black line denotes the optimal deviation Losstv- Middle (b) and Right (c): numeric example. the plot, the over acceptance c's are set as positive constants that define b(x) = m 2(2)+c)
p(#)
rejection is unavoidable no matter how many draft responses are sampled from p. We also formally prove this in Proposition 1. This theoretical discovery indicates that having very large draft batches does not necessarily result in significant inference speedups compared to small batches.
4 Analysis on the Optimal Rejection-Distriitionn Bias Tradeoff
In earlier sections, we focus on analyzing SD or Batch SD which are distribution unbiased. To further reduce rejections, the algorithm may have to compromise on output quality. Nevertheless, it usually acceptable for many real-world applications. For instance, for the family of Gemini models [38], Google may deploy the small model Gemini Nano as the draft model and Gemini Ultra as the target model and tune the acceptance probability b (in Algorithm 2) higher such that Gemini Nano is applied more often for the purpose of less expenditure. Therefore, an intriguing question to ask is: For biased algorithms, what is the optimal tradeoff between rejection and distribution bias?
4.1 An Optimization Formulation and Pareto-optimal Characterization
We measure the distribution bias between ydd and via TV distance. 6 Concretely, for any algorithm A = (b, P) in 2 with acceptance probability and rejection distribution P, we fix and aim to optimize the following objective
Losstv(b) = min TV[PA, 41. where A: (b,P).
P
We wish solve the above since characterizes the minimal distribution bias for any design b. We present our solution in the next.
Theorem (Optimal solution to optimization (1)). We can show the objective (1) is equivalent to
(bs)tv(b)= = 2
s.l. ΣP(s) - p(xx) 3 0, Va. min Σ 9(e) b(x)p(a) - P(x) En b(z))p())
P
Suppose E.11 - b(x))p(<) > 0. Define A(x) = b(x))p()))
E.11 Ee[l-bia)lp(a) and the sets A+ = {e E V
A(x) 0), A_ (x e V: A(x) =0). Then the of optimal distributions of objective (1) is
characterized as (p* : p A_ ()) 0:0 P*1 1* & A(-)), and the optimal value is Lossty(b) (b)
Σ. (x(x)= - b(z)p(x)) E,(1 b(x))p(r) 2 O.
Theorem 4 is universal characterization that contains both biased and unbiased situations. 1. b is less than Speculative Decoding threshold, i.e. b min 1,1/1//// q/p) then A becomes probability distribution and the optimal distribution pa equals A which is also unbiased (Losstv(b) = 0); 2. If exceeds the Speculative Decoding threshold, then A is no longer distribution and there are multiple optimal distributions p* In this case, the optimal distribution bias Lossty > for Algorithm 2.
"We mention TV distance is only one metric for measuring distribution bias. In general, any distribution distance be considered. We leave thorough study for all other distances future work.

---

Main Takeaways. Via Theorem 4, we derive the pareto front (the optimal tradeoff) between rejection probability' P(reject) vs. distribution distance TV[FA, g] (Left panel of Figure 4). The blue region can be realized by some algorithm 2, and the red region cannot. (0, 0) is the "perfect algorithm" (no rejection, no bias) which does not exists, and, particular, (0, TV[p, q)) stands for Speculative Decoding. Surprisingly, the pareto front is a straight line connecting (0, [V[p, g]) and (TV[p, g). 0), which represents a linear relationship between the rejection probability and the optimal TV deviation. This is guaranteed by the following theorem.
Theorem 5 (Pareto front). For any Algorithm A the class 2 that satisfies min 1, 2(() & b(x) &
1, Vx e V. Then
(reject) (os TV[p, Here (reject) -1-- Di b())p(z) and (b)) == minp TV[ .g].
We plot the numerical example using two Markov Chains in the middle and right panel of Figure 4 that coincides with our theoretical finding. the figure, the acceptance probability is set to be b(z) = min ) The orange line in (c) and the green boundary in (6) are computed via (b) from Theorem 4. The complete proofs for Theorem 5 and Theorem 4 are deferred to Appendix E. For the clearness of illustration, we focus on the pareto front between rejection vs. the
minimal TV deviation for single token.
4.2 Experiment
We provide an additional simple experiment to show the effectiveness of our Pareto-optimal solution in Theorem 4. Consider objective (I). For the given acceptance probability b > min(1, g/p). we have two options for P: 1. Baseline: select P to be suboptimal to (1), i.e. simply set P == which is the target distribution; 2. Set P p* be the optimal distribution of Theorem 4. We call the first method Decoding-Uns UNO and the latter one Decoding -PP.. Instead of TV distance, we measure the quality via WinRate in our experiment. Concretely, for each prompt, we let Decoding- and Decoding-OPT to generate responses independently, and use score models to compare whose generation has higher quality. We specify draft model p as pythia-Th a-0m and target model q as pythia-2.8 8b from EleutherAl [7]. We apply the score model to be RM-Mistral-77 -BB or GPT-4. We test 200 prompts from Alpaca-Farm Eval Dataset [13] with 500 responses/comparrson per prompt. Table shows that Decoding-OPT achieves better performance than Decoding-UNO across different choice of e's. Due space constraint, the missing details are deffered to Appendix G.
RM-Mistral-PP 1B
GPT-4
Method
0.1
0.2
0.4
0.8
c- 0.1
0.2
0.4
0.8
Decoding-QPT 53%
53.5%
57.5%
52.5%
54.5%
53%
53.5%
55%
Decoding UNO
47%
46.5%
42.5%
47.5%
45.5%
47%
46.5%
45%
Table 1: WinRate for Decoding-OPT OPT vs Decoding-UNO with different over-acceptance threshold c. The acceptance probability b(xr) min 1, g(z)+e) 3.
p(z)
Discussions
On the optimality for batch algorithms. Unlike their non-batch counterparts, our batch algorithm studies do not come with optimality guarantees. This is largely due to the diverse and arbitrary nature of batch algorithm designs, making it challenging to define comprehensive class that encompasses wide range of batch algorithms. While [37] investigate optimal batch algorithms through an optimal transport lens, their work does not extend to calculating optimal rejection rates developing an efficient algorithm to achieve this (they only propose an approximate solution). Consequently. the pursuit of batch optimality remains an open field. Identifying the optimal batch algorithm could yield valuable insights for enhancing practical applications in real-world scenarios.
Here the rejection probability is computed as P(reject) Σ, P(reject, 2) = Σn IP (reject(] (Z) =
E1 (()))

---

Extending Speculative Decoding to other studies. Speculative Decoding is a generic sampling approach that extends beyond mere decoding tasks. holds potential for wider applications such as search engines and recommendation systems, where it can be employed to quickly generate and refine search outcomes or content suggestions, enhancing the overall efficieccy and user experience of these systems. We leave these as future works.
Acknowledgments
The authors would like to thank anonymous reviewers for their valuable feedback. Mengdi Wang acknowledges the support by NSF IIS-2107304, NSF CPS-2312093, and ONR 1006977.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08 08774, 2023.
[2] Kwangjun Ahn, Ahmad Beirami, Ziteng Sun, and Ananda Theertha Suresh. Spectr++: Improved transport plans for speculative decoding of large language models. In NeurIPS 2023 Workshop Optimal Transport and Machine Learning, 2023.
[3] Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid. Vivit: A video vision transformer. In Proceedings of the IEEE/CVF international conference on computer vision, pages 6836-6846, 2021.
[4] Sangmin Bae, Jongwoo Ko, Hwanjun Song, and Se- Young Yun. Fast and robust early-exiting framework for autoregressive language models with synchronized parallel decoding. arXiv preprint arXiv:2310.05422 2023.
[5] Benjamin Bergner, Andrii Skliar, Amelie Royer, Tijmen Blankevoort, Yuki Asano, and Babak Ehteshami Bejnordi. Think big, generate quick: Llm-to-sim for fast autoregressive decoding. arXiv preprint arXiv:2402. 16844, 2024.
[6] Nikhil Bhendawade, Irina Belousova, Qichen Fu, Henry Mason, Mohammad Rastegari, and Mahyar Najibi. Speculative streaming: Fast Ilm inference without auxiliary models. arXiv preprint 13X1v:2402.11131, 2024.
[7] Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling, In International Conference on Machine Learning, pages 2397-2430. PMLR, 2023.
[8] Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, et al. Rt-1: Robotics transformer for real-world control at scale. arXiv preprint arXiv:2212.06817 2022.
[9] F Warren Burton. Speculative computation, parallelism, and functional programming. IEEE Transactions on Computers, 100(12):1190-11
1985.
[10] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving. Jean-Bapiie Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013 2023.
[11] Ziyi Chen, Xiaocong Yang. Jiacheng Lin, Chenkai Sun, Jie Huang. and Kevin Chen- Chuan Chang. Cascade speculative drafting for even faster Il inference. arXiv preprint WxXiv:2312.11466 2023.
[12] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. image is worth 16x 16 words: Transformers for image recognition scale. arXiv preprint arXiv: 2010.11999, 2020.
10

---

[13] Yann Dubois, Chen Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani. Jimmy Ba, Carlos Guestrin, Percy S Liang, and Tatsunori Hashimoto. Alpacafarm: A simulation framework for methods that learn from human feedback. Advances in Neural Information Processing Systems, 36, 2023.
[14] Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. Break the sequential dependency of Ilm inference using lookahead decoding. arXiv preprint (XXi:22402.020555 2024.
[15] Freddy Gabbay and Avi Mendelson. Speculative execution bused on value prediction. Technion- IIT, Department of Electrical Engineering, 1996.
[16] Mukul Gagrani, Raghavy Goel, Wonseok Jeon, Junyoung Park, Mingu Lee, and Christo- pher Lott. On speculative decoding for multimodal large language models. arXiv preprint arXiv:2404.0883 0888666,. 2024.
[17] Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey vision transformer. IEEE transactions pattern analysis and machine intelligence, 45(1):877-10,, 2022.
[18] Zhenyu He, Zexuan Zhong, Tianle Cai, Jason D Lee, and Di He. Rest: Retrieval-based speculative decoding. arXiv preprint arXiv:2311.08222 2023.
[19] Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poole, Mohammad Norouzi, David J Fleet, al. Imagen video: High definition video generation with diffusion models. arXiv preprint arXiv:2210.02300: 2022.
[20] Kaixuan Huang, Xudong Guo, and Mengdi Wang. Specdec++: Boosting speculative decoding via adaptive candidate lengths. arXiv preprint 1.ki::2400.197155 2024.
[21] Wonseok Jeon, Mukul Gagrani, Raghavv Goel, Junyoung Park, Mingu Lee, and Christopher Lott. Recursive speculative decoding: Accelerating IIm inference via sampling without replacement. arXiv preprint a4Xiv: /4/60, 2024.
[22] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint Ttt::0001.0836. 2020.
[23] Schoon Kim, Karttikeya Mangalam, Suhong Moon, Jitendra Malik, Michael W Mahoney, Amir Gholami, and Kurt Keutzer. Speculative decoding with big little decoder. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[24] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.
[25] Xiaoxuan Liu, Lanxiang Hu, Peter Bailis, Ion Stoica, Zhijie Deng, Alvin Cheung, and Hao Zhang. Online speculative decoding. arXiv preprint 10.00:2310.07117, 2023.
[26] 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 Ilm serving with speculative inference and token tree verification. arXiv preprint arXiv:2305.09781, 2023.
[27] Eric Mitchell, Rafael Rafailov. Archit Sharma, Chelsea Finn, and Christopher D Manning. An emulator for fine-tuning large language models using small language models, arXiv preprint arXiv:2310. 10. /262,, 2023.
[28) Jie Ou, Yueming Chen, and Wenhong Tian. Lossless acceleration of large language model via adaptive n-gram parallel decoding. arXiv preprint arXiv:2404.088: 086998, 2024.
[29] Haifeng Qian, Sujan Kumar Gonugondla, Sungsoo Ha, Mingyue Shang, Sanjay Krishna Gouda, Ramesh Nallapati, Sudipta Sengupta, Xiaofei Ma, and Anoop Deoras. Bass: Batched attention- optimized speculative sampling. arXiv preprint arXiv:2404.15778 2024.
11

---

[30] Andrea Santilli, Silvio Severino, Emilian Postolache, Valentino Maiorea, Michele Mancusi, Riccardo Marin, and Emanuele Rodolà. Accelerating transformer inference for translation via parallel decoding, arXiv preprini arXiv:2305. 2.Xi::2300510422,, 2023.
[31] Mohit Shridhar, Lucas Manuelli, and Dieter Fox. Perceiver-actor: A multi-task transformer for robotic manipulation. In Conference on Robot Learning, pages 785-799. PMLR, 2023.
[32] Benjamin Spector and Chris Re. Accelerating Ilm inference with staged speculative decoding. arXiv preprint arXiv:2308. 044333 2023.
[33] Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31, 2018.
[34] Qidong Su, Christina Giannoula, and Gennady Pekhimenko. The synergy of speculative decoding and batching serving large language models. arXiv preprint arXiv:2310. 18813, 2023.
[35] Hanshi Sun, Zhuoming Chen, Xinyu Yang, Yuandong Tian, and Beidi Chen. Triforce: Lossless accelcration of long sequence generation with hierarchical speculative decoding. arXiv preprint 111122 2024.
[36] Ziteng Sun, Jae Hun Ro, Ahmad Beirami, and Ananda Theertha Suresh. Optimal block-level draft verification for accelerating speculative decoding. arXiv preprint arXiv:2403. 2024.
[37] 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.
[38] Gemini Team, Rohan Anil, Sehastian Borgeaud, Yonghui Wu, Jean-Baptise Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312. 11805 2023.
[39] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Tim- othée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint 13777 2023.
[40] Siqi Wang, Hailong Yang, Xuezhu Wang, Tongxuan Liu, Pengbo Wang, Xuning Liang, Kejie Ma. Tianyu Feng, Xin You, Yongjun Bao, et al. Minions: Accelerating large language model inference with adaptive and collective speculative decoding. arXiv preprint arXiv:2402.1560 2024.
[41] Heming Xia, Tao Ge, Peiyi Wang, Si-Qing Chen, Furu Wei, and Zhifang Sui. Speculative decoding: Exploiting speculative execution for accelerating seq2seq generation. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 3909-3925, 2023.
[42] Heming Xia, Zhe Yang, Qingxiu Dong, Peiyi Wang, Yongqi Li. Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui. Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding. arXiv preprint S.V::2401.0785..1 2024.
[43] 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.04255. 2023.
[44] Minghao Yan, Saurabh Agarwal, and Shivaram Venkataraman. Decoding speculative decoding. arXiv preprint arXiv:2402.01528, 2024.
[45] Sen Yang, Shujian Huang. Xinyu Dai, and Jiajun Chen. Multi-candidate speculative decoding. arXiv preprint arXiv:2401.067066 2024.
[46] Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Ros- tamizadeh, Sanjiv Kumar, Jean-François Kagy, and Rishabh Agarwal. Distillspec: Improving speculative decoding via knowledge distillation. arXiv preprint ar arXiv:23 10,08411, 2023.
12

---

Appendix
A Proof Sketch
A.1 Proof sketch of Theorem 2.
For any algorithm A F, its design b, can be written a function of any sequence 21:n- 1, T. with
O & (T -in-1) & 1. Based on this, we can further define the new function En V x ym-1 m IR
according to the following equation:
bn (Ān, JIn--) 1) min On (2n + en (in--)
(2)
Po (T (fmmmm
Indeed, we can choose en == bn Pn qn. and the validity of the definition is guaranteed by the Lemma 1. Then, the acceptance probability b, min(1, @n implies c, > 0.
p.
Next, show for any A it must satisfy bn min pa for all To this end, design the two token sets V- = {x : In s.l. (n(x) > 0} and V_ {a s.l. en (x) & Ofand prove V+ = Ø, =.
Finally, by Lemma 2 in Appendix, any algorithm satisfies b, & min 9n Vn [T] must have ES [Neij] > Ex E, (V[TV(pn (-1m)-mm-)]] Since F is arbitrary, this concludes the proof. The full proof is included in C.
A.2 High Level Proof Sketch for the second part of Theorem 3
The derivation for the number of expected rejections using the batch speculative decoding is more involved than the Algorithm due to the parallel response structure. The key step to compute the intermediate quantity ( acc, F. Fn (i11:1n)))..... Let un p(-(x11--2). then there are two cases: ăn-1 accepted or rejected. We have
P (Tn acc, In In (nl
(T., acc, In In, in acc/ + ( acc, In In, Fn rej
(a acc, H, In En acc, T1:n p.
Pa (Tt, acc, ān vn T x1n PA (
Pb
In the process finding Ps. we need to compute the the quantity f(I1.) := P( 0 (n-th draft token rejected)) and it can be recursively computed via (22) using p, q.
A.3 Proof sketch for Theorem 4
Due space constraint, only summarize the high-level proof ideas for Theorem 4. Since Σ A(x) 1, the original objective (1) be equivalently rewritten
1 A(x)- s.t. p(x) 11, P(x) 20, VreV.
min
(4)
2
We now find the solution of objective (4) in steps.
Stepl: Recall A, = {x V: V A(x) > 0} and A_ = fa e V: A(x) < 0), then any optimal p* must satisfy (xxx)) = 0 for all x A_. This can be shown by contradiction via alternative construction P' to reason p* is suboptimal to P'.
Step2: We characterize the optimal solutions of the objective. By Step1, we can show any optimal solution p satisfies Σ, A((x) p* (xx) > ||A|]] and the equal sign can be achieved. Then we can convert ||A||] 1 back to Loss This also helps identify the optimal set of **
It needs to follow b,, [0, since bn is probability.
13

---

Algorithm 3 Auto-Regressive Model Decoding
1: Init: Horizon T. Distribution Prompt To. n 0.
2: while n < T do
3: Sample 2n ((1121m-1)... n n+ 1.
4: end while
B Proof of Theorem 1
Theorem (Restatement of the first part of Theorem 1). We define random variables R. E {0, 13 indicating whether the n-th token is rejected with being rejected (here rejection means Line 6 of Algorithm is executed). Then, the total number of rejections Nuj En Rn. For Speculative Decoding,
T E = Σ Ex
(1
Here TV denote the TV distance between two distributions.
Proof. Given the verified the tokens 11 we first compute P P(Reject at mlfamm-i). Denote the candidate draft token o pr(((x1in-1), then by law of total probability
PRRject n m/210-11
Σ P(Reject n, n.8(11n-1)
P(Reject 1F
P(Reject 11 (())1)
9n fn(0@11m11 1) (i/11m-1)
(1 min
pa 11m-1)
(0 p.. -.. (G] TV(p., qu (-11mm)))))
where the third equal sign uses draft token is sampled from pn and the fourth equality is by design of Speculative Decoding (Algorithm 1, Line 4).
Lastly, by law of total expectation and above
E [[N
E B
Σ
E E [1a-1]]
Σ
E 21 -1
E M[Rajma-ll(tn
Flw-1
P(Reeect at 11
T
Here the fourth equal sign comes from Speculative Decoding keep the distribution q (Proposition ??). Li
the fifth equal sign comes from the event RR, 1} = (Reject at n).
Theorem 7 (Restatement of the second part of Theorem 1). The output distributions of Speculative Decoding Algorithm and the large model g are identical, i.e. for any output sequence Fur E VT, the joint the distributions over ZA: satisfies: ppSpeDeccoding (I1.T) q(I1TT).
14

---

The proof of Theorem 7 is very similar to [10] except we have K = s. In addition, [10] proves the distribution match for a single token, we complement the proof to show the distribution match holds for sequence of tokens TY.T
Remark 3.
Proof. In particular, we use induction to show the stronger result that V & [T], Væi, .2.............................. 3t. E V. it holds P. (x1, (2,.,, 2x) ge (x), 22,...,
Step1: Since z0 the prompt, its distribution independent to p. q. Then for 1, applying Theorem 1 of [10] (with K = x)) directly with and to be conditional distributions Pi(-Izo) qı (a (zo), which further implies (x121) qı(1)) (since the distribution of To is independent of p.
and qı (-11r) gives IP (2)
Step2: assume (x .2....,, 22)
qe (11, T2. ................................ 2t), first show P (x(++1))21)) ((1++1 Indeed, let 8441 ~ p( [ıt), then by law of total probability
PA (xxx) = (
acc| = I1:1,
(5)
( rejl PP (re+ (8441 rej,
By Algorithm
( 2141/111) acc|0r+1 re+1,
=p(a (11) min (1, g( (eml (1, p(2(+1
(6)
Next, the probability of rejection is:
P( rejlara:) P( acc|
E x', Se+1 acc|
=1 minn (111=11))))) Σ max(0, (11)) -p(x'(maa)
where the second equal sign comes from (6). Lastly, by the construction of the algorithm,
( rej, x1:) = max (0, g( +1 (1I.)) - p(
(8)
Σ. max x1:)) - p(x1(=1a))
Combining (8) and (7) yields
(ā rej (Pt4 rej, +ir)) = max(0, (00 p(
Plugging (6) and the above equation into (5) obtain
(1 (1:)) min x [21a), ((1141/21:)) + max(0, g(1141/71))) - p(1441/21a) = ((1111)11))
Finally, applying the above we obtain
(1144)))))) PA (z1.) (Z4441) Fz(.)) g(1441/211)) = (0+1(11441).
where the last equal sign uses the induction hypothesis.
15

---

C Lower Bound
Theorem (Restatement of Theorem 2). Define the arbitrary instance P (p,4), and define the family of algorithms as
= (A: A is specification of Algorithm 2 that satisfies P.A. qi Vt (i.e., distribution unbiased)). For algorithm A, denote Nuj as the number of rejections. Then have
T
inf EP [N AeF
Σ Bein-ing [TV(pn:
Pitn-ingTV((pn,, qn (n)(( C(P).
Remark 4. Theorem 8 shows the rejections of Algorithm is tight at the instance level (over the family of algorithms F). Therefore, it attains the instance-optimality over sequential decoding algorithms family F.
Proof. For any algorithm AE F,, its b, can be written function of the sequence 21:--1 Zn with & (in--) & 1. Based on this, we define the new function E,, : ya- + IR according to the following equation:
bn (Tn 11n- = min {T, qn (a( ((:n((1:n11) + en Cn T1:
Pr (1m--1)
Indeed, we can choose en == bn Pr to and the validity of the definition is guaranteed by Lemma 1. Recall A E F is distribution unbiased algorithm w.r.t. Let .,,-..;2, be the validated sequence A, then we have
(T(:1))) = On (111)))) On En(anl21mm- PA (21m-11) (n(xin-1)
(10)
On the other hand, let in ~ p 1), the decomposition holds pA (am( TPr (xn, fn accept/ (mm-)) + Pr (Z, on reject)x1=a-1)
A (ăn accept = Inas fin- )P (it, = In 1m1
+ p (2, reject, F1:n 1 )P (ū, reject)xim=-)
=bn (In, 11m 1) Pm (In ( 1m) + ( reject, x1mn-1) PA(in (?n reject|#11
=b, (2n, 11m Pm (In 11) + (2, @. reject, 11:n-1) (1 > bn (z, Fim- 1)p (1mmm)))))
(11)
where the third equal sign uses (ā = wn xm( = Pr (zm 11 1) and last equal sign is due to
PA (on reject|x1:n-2 1- PA (ccept/21mm-1) Σ p. (ān accept, R, x)x1m-1)
Σ (Tn accept/an = x, F1 PA ( x/ >
Let's do some further simplifications. First off, (M,, 11ma-1) Pa ( (1) =p (x (mm(-1mmmm))) min (1, In (I (mmmm + ex( x1m-1)
pn Pn(#n (1=n-1)
min (pm q. + en 11m=-1)
(12)
and Σ by (2, (000) =1 Σ min (om (x, x1mm
c
Σ max (0, p. (x/ gn (n -0
(13)
For Speculative Decoding, its by (ān: Fim--1) = min {1, (n(an|
pa (aa
16

---

Plug (12) and (13) into (11), and then plug (11) into (10) to obtain
In (#nnk (mmm))) min (1n(x, (rim 1), (Tn (mmm-)) en( ximn
+ +P (Inl reject, Tim-1) Σ (Pn(22/211m)) - (2( (0022mmm-1) - 6n( Fim-1)) (14)
Now, we define the token set V+ = fx : 3 n, T Fim-1 s.t. (2, f1m=1) > 0] and similarly the token set V/- = {2 n, I1m-11 s.t. ( F1nn-1) & 03. Next, we show V4 Ø, and V_ V.
Casel. If pn (1mm))) 3 on (0 (2n] (11m 1) + en (Ins I1mm-1), then by (14) we have (m(=n/(1m=11) en (zn F1:n-1)
On (n
- en (1mm)1m1)) + +PA (In (pn(znla reject, T. = on. 1l) Σ ((n(()(rinn)) gn (n(x(/1i=11) -n
(nn(anlaiin + en (nn Fin--1); and this implies 0 3 (Zn 2 1i 1). which means Fn V-;
Case2. pn (In (Imm) < 9n (2n (ann 11mm + Cn(InnIInnnl then by (14) have
on ( mm-))) Pm( (1
+ Iad (an [.n reject, In = znz x1m-1) ((pn(rlrim-n)- - on (x( - en (1m-))m))))
>pr (1m))1) and this implies
=b (Fns Fimn (Fn - On (Fn 11m-
Epr (In (0mp1mmm1)) on (2m & 0,
which means Zn E V_.
Therefore, combining the two cases we always have x E V-, which indicates V+ = By (9), this implies for n, b, & min(1, 8n Finally, by Lemma 2, this implies TE [Nre]] > C(P). Since A E F is arbitrary, this concludes the proof.
Corollary 1. For any algorithm A F, follows V [T]. 2 V and Tin-1 (1(1,T1nn1) Finn-1) & min 1, ga
Pa (000111)))) }. In this case, the distribution Pn is defined as:
Pn(x/1im-1)= (n((//aimn1) min (pm( 1), (n (2/ + cn(a,, (1n-1)
(x( - (1(x1(1mmm1) en (x (1mm11)+
Applying en = bnpn Yn this is equivalent to
Pn(x)21m-1) On 2z im- by (x: 2. (2, 1p
Σg ba, -im 1))pm (x/
Proof of Corollary I. We reutilize (14) here and call it (15).
4n (n(2n|ain-e min {pa (I, Immm (n 1m) + En(nn T1m-1))
+PA reject, 11nm11) (p) - qn qn (2/21mm-1) (1
(15)
By two cases discussion as in the proof of Theorem 8, we have v A F, it follows V E [T], V
and 11:n-1, bn 11) & min (1, gn (x( Then we can directly solve (15) to obtain
P. (m
IA (2]ā,, reject, 21m-1) (2/ 10 - min (p((m)/mmm)) gn (x/ en #1m-1)) qu ( 1mm-)) - En ( (x)x1n=)))
Lastly, we verify such IA (1r f. reject, 31m-1) is valid distribution. First of all, since 6n bn Pa -n, then by implies
& min 1, en (n(xlmi--)) implies (1:n-) & 0, and this further Pa (=(
qn (1((//inn1) - min (pm (2/ 1) oo (2f21mm-1) en(r, 11m-
2q (x( - min ( 1) 4n (2 > 0
17

---

which implies (a reject, 11mn-1) 2 O. Second,
On fn(xf1im-11 - min (0 + En(x, 11n-1)
(x (z)ā reject, x1m--1) Σ
2x (pn (2) (n((((mm1)) =x(x((1mm1))+
1 E, min
11 Cn (1m))11
Ex (Pn (z0( 9n ( En 2 (1:m-1))
1 + Ex max
qu (a) (m=)) - en (im-1]]
(P (21 on (z) x1mm
En in (m( + Σn max ( Pm (2) 2 1m yn [ En (im
Ex (1Pnno//11n1)
on (0 - cn 11mm
Σ. max (0, Pm (1 ( (1m- gr (1 (1mm 1.
(P 1in-1) - On (x - (x)
This concludes the proof.
Lemma For any (Tn; 11m-1) 1, there exists (,(nn Fim-1) such that (9) holds true.
Proof of Lemma 1. Indeed, set cn = bn Pn. Ins then
min (1.
[n([n|]imm- (1mm 1) + en (n T1mm-)) min(1, b, (ā x1m- (5 Fim--1
Pn(In (In(v1mm-1)
where the first equal sign uses that in is sampled from pm. (-121m-1) so Pm pm 11m-)) 0, and the second equal sign uses 0 & bn 1.
Lemma 2. For any instance P = (p.g). q). let F {A: A is a realization of Algorithm s.t. IPA- ae Vt (i.e., unbiased)). Suppose there is an A F such that E [Nrej] < C(P), then there exists bn in Line 8 of Template 2 such that 3x, Fi:n-1
ba ba(x(ximm1) min (1, on (n(x((11=111)
Pa (1<(01mm-1))
Proof of Lemma 2. Suppose for all n, x, Tim-1, (=(==imm1) & min {1,
pm (a (mmmm--)) S. We define
2a (zl
random variables R, E (0, 1) indicating whether the n-th token rejected is rejected). Therefore, the expected number of rejection
BA
Rm
E
Σ E Em
[Rn [11m |
Σ E Eaim-rn
[Rn [1m-
Here the second to last equality comes from the tower property and the last equal signs is due to A is unbiased. Next, denote Zn P.-(- (x((((1mm-1) to be the candidate token, we have
E
[A 11mmm1mmm11- PA[R, = 1|21m-1] = Σ P [R, = -1,2n 1.1m111m-11]
Rn
Σ RR.. = 1|āng Dian -1:n ] 2n
( [i [1:n
Σ T Pr = 1| Fi:n [in
Zn
min {
On (T (1mm-))) )) Pe Ta [11
E( bn) Pru Prl[Enl 10ll-1mmm1 > E 16immin/
Pr (on (1mm
2n
= "P (2, - (2n 1)4 TVI(P, (000))g-((f (0m0))mmm))))))))))
Zn
and this implies
T
EX [Nej] = E
I'
Ezin-1ng rg TV[(pa(-lIan-- 1:000-gg---aaaa (n(-(ammm-1)) = C(P)
18

---

contradicts E (Nyl < C(P) This concludes the proof.
19

---

Algorithm 4 Batch Speculative Sampling
1: Init: Horizon T, Distributions dt. and Pt, with q PLLM PDraft Lookahead K
2: while n < T do
3: Reset q: PLuM Vt. no n.
4: for m = 1 : M Saample M draft responses in parallelo do
5: for
T do
6:
Sample 2,tT Pe(-(ai:-11 Fm
7:
end for
8:
end for
9:
Obtain logits yn (-121mn-)) .... 11, Vm E [M] in parallel for mnr-
10:
Verification Begins Set Sample- False
12:
for 1, ................................ M do
13:
for 1 = n T do
14:
Sample
(niform(00. 1].
if r & min {1,
9: (3." m1.m 1 1) then
15:
(#2" lmi. 1. 1
16:
Accept with In 8: 12 n + 1. Sample True.
else
18:
= no then
Update qn - L (- (-1x1m=11) Pa (-121mm-)]4 Break. //Here no equals n.
20:
else
Rejection Sample In [anl (11-111:1-1) Pn Pu(-(a1m-1)44 n n 1. Break.
22:
end if end
24:
end for
Sample TRUE then Break.
26:
27: else
28:
Rejection Sample vn, [gn(112mmm1 Pa(-(11im-1)44- < + 1. Break.
29: end if
30: end for
31:
end while
20

---

D Batch Speculative Decoding
We split the proof' for unbiasedness and rejections in two parts. Theorem (Unbiasedness of Theorem 3). Denote the Algorithm 4 as Ag. For any sequence T.T (where 2, E V), we have
PAA (I1,...,,Tr) .r.
T (01,...,,77)
Proof. Stepl: Let 1im-1 be the accepted tokens up to n 1. We first show PAs (In (1m-1) = PL (2:mm) Vzn E V.
We partition the generation of zn into two cases: (i). accepted as the first token of the m-th responses
(m = 1,.., M), or rejected by all M responses and sampled by Line 28 of Algorithm 4; (ii).
accepted/rejecte as the f-th token of the m-th responses (m 1,..., M) for >
For the second case. Similar to the standard speculative decoding, let in ~ Pm (-1121mm-1). then PAA (In (1mm-1) PAA (n, ay acc) + TAAA (In, " rejl
PAee ( = an xal MPA (#t accli, = Fn, F1m-1)
+ PAs((?) rejl IP (In 1 rej, m1m--1)
P min 1, Jn (In (11:n11)
Pr. (3 (1
max qn (xn]/2mmm1) - Pn (xn = (1m-)))
Σ max (1 (dnl - Po (x' (0in Ex max 4n (2' (11=)==-1) Pn (= (0i])1
By the construction of Algorithm 4 (Line 3), when x,, is accepted/rejected the t(> 2)-th draft token of certain response, we have Qn (In///inn1)) = ( (xn|<xmm-)) This gives PAA (In|
FLLM FLLM(,, (.n((1
For the first case. This part of the proof largely follows Theorem 4.2 of [26]. In this case, the n-th generated token Fn has M + 1 possibilities: accepted at the m-th response rejected by all M responses and sample at Line 28. Since the algorithm will iterate all M responses not accepted, we denote q." as the In for the m-th response. Then we have the recursion
m+1 max 9T d
Pn
Im
where oh PLLM and is the rejection probability satisfies I'm =1 PAs (3 acc|#1.n-1) 1 - > p- (am x/ PP (3.7 acc| x, 11n-1)
min(1, (1, Lnd (I) 11
=1 - -
Σ max (aaox( (x/41n-1) Pno (2/2211m-111
pm 11)
Denote F... (m-th response rejected) and Fr.m {1 m-th responses all rejected), then A (Ix ((mn))) = pA (xn, E9 (1 + IpAA (Ir,, E (4im-1)
min(pp (x (1 9 (I (1:=-1)) 1)) TA (Mr,; ( Fn (11m-1))
= mmin(pn (xn (2n o (In -m) + +
1 (æn. (im-))
Denote PAA ( (1)]) = (x,, Eg, 11m by similar calculation we have in general
IAAe (zn 1,
min(pn (I (1 (1)m q6l (In (n]=imm-1)] + rm pAs (Inl Eom 11m--1).
Next we prove Inde (-) x1:n-1 = d. m++1 (21m-1) Vm E {0, 10.,,...,4 M3 by back- [a:44 (0ff((/21mm111 Pa+1 (1)m =
ward induction. First of all, (- (EEarr,,Inn1
max(0.... -Po -P.--laa M-lm--lamm1)
oh M+1, Suppose IPAs (-) Pomm1::1nm-
m+ (11m1mm11) then
PM pAa (-IEom: xim PAs (., F Form; F1mm-1) + PAB (., Fm Form: Fimn-1)
min(pa (-12/m1m1m1)) 1), In
m+1 (1(1snn1)) + RAs (., Em-+l Eorm, Fi:n-1)
= =minfpa( (-1opp/((1111mm)) oh m-+1 (((mmm1)) + Tm+1 pad (. (.Imm (1m-1)
= min(pp (-12 17 au= (1)mm))) + max/0, g=t1 pn) = g=1
21

---

In particular, we take m = 0 to obtain
A (-121:n-1)
PLLM (.1211m-1).
Combining both cases finish the proof of Stepl.
Step2: For any n, first of all we have puse (m0) (LLM(F0) since zo the prompt. Suppose
FAt (Fim-1) = - 1)) V then by Stepl
PA8 (I1m)) 1AA (z (1mm-1) 1 (Z1m-1) PA (an -1 (-im-11 PLLM (Iim)
where the second equal sign by induction and the third equal sign by Stepl. This finish the proof.
D.1 Expected Rejections for Batch Speculative Decoding (Proof for the second part of Theorem 3)
In this section, we derive the number of expected rejections using the batch speculative decoding. However, the analysis is more involved than the Algorithm 4 due to the parallel response structure, since, given the verified token Z1mn-1. the probability of n-th token being rejected does not possess unified expression and depends on the location of Jn-1- We detail this below.
We recall the notion in Theorem that random variables R. {0, indicates whether the n-th token is rejected (1 is rejected). Therefore, the expected number of rejection is
E
Σ n=
Rm
E
E
Σ
E E Rm
11=-
(16)
n=1
n=1
where the last equality comes from the tower property of expectation and we assume is given initial token and 01:0
{x Then
RR [1]== (n-th token rej = - 1Md (n-th (n-th token acc| acc|
In this scenario, we cannot obtain p-(n-tt token 11)-) (V(pn (1 PH (-1211=11)
since the conditional rejection probability implicitly encodes the location of (n- 1) token: whether accepted (at the
Æn-1 (f-1= 1) is rejected (at the root of the tree) or Φn p(-1#1m--) branch of the tree). To formalize this, given validated token T1:--1, we denote q." (-(x1==11) to be the m-th rejection distribution, then by the construction of Algorithm 4 (Line 19),
max (0, ah pn) I'
Vm [M].
Here I'm = Ene' max(0, 9h" (x" 11) - Pv (dmm 1)} is normalizing factor and dh = PLLM Let In ~ p(-1 then IP- (n-th token acc/#1mm11 = (ā, acc acc(#1m-1). Next, we compute the quantity (Hx, acc/21.n-1).
We begin by first considering IP (i,, acc, in In (ml181n-1) 1). Let in-1 p( (2)mm22), then there are two cases: - accepted or rejected. We have
p.d (ān acc, In 2n//iin
I acc, In Iny In- 1ac IP (ān acc, In. In rej iin-)
Man acc, In = Fn jn acc, x -l:m
Po
pA acc, on nn - rej, 11 P. (in--1rejjlmmm
P6
(17)
For Pa. Given that - is accepted, 3n Zn can only be accepted as the t-th token within the certain response for > This because _ is accepted and has to be at least the first token in the response. In this case, 9m (-((((1mm-1)
pl (- 1 q (1) then
Pa (p acc|ãn = In. In- acc, x x )IAA (īn = xn, f2- jace 21m-1)
= =min On (2 (an2nl11n (11m-1) Pro (I ( min (1. 1), gn ( (2m/amm-11)) (18)
Pn (x 11mm
= min(pp((x, |1 g (2mm/1mm-))
22

---

For Pb- Given that žn-1 is rejected, Σn = 2n can only be accepted as the first token within the certain response. This because - is rejected will restart the parallel tree. Then
pb = I (In [n 1rej, x1m- - pu (Tn rej, 2n 2n rejj, Xin-1)
= LLLL (z (1mm1) - (2n rej, an [ irej, I1:n-1)
(19)
1pLL (1mm)1mm-1)
I1
In M+ (In (xn|=imm1).
since 1nej implies In represents the first token of the parallel tree, then it is identical to the proof of the first case of Stepl in Theorem 9. The second equal sign is from: nn is rejected means all M responses since In is the first token of the tree. The conditional rejection probability
where the first equal sign comes from:
P(an rejl "il
1.1mm11 rej, -1:n-1) = 1 P( acc|_i... 11:m- rej, #1m--1
Σ
pAx (I x|7 1m rej, Iinm SIP (I acc| 7.mm-1 rej, T 2, x1m11)
=1
In (2) (21211mm1))
1) =1 () min min(1
Σ max o. (x/x pa(2((x1mm11) mm:
Pr (
so by chain rule, the total rejection probability is [I Tmm
Plug (18), (19) into (17) obtain
[T acc, (n( = minfpa (F (01m0- an (In pri (fn-
M
+ Iq (2m121m-1) - II]
M+ (2m (3n-
rm)
mm1
(20)
which is equivalent to
a (In (1))))m-1) - P rej, an htgp://maaaa..a..aa..//o//o/aaaa
min(p. (mm
(ej
-Igh (In (1m1)11-11)
II
rm)
M+1 (2m
m=-1
(Tn rej, on (1m--1) = max(0, 0, ql (xn (11m-1)m)))) (a) (2x
mmax(0, af (am//amm--) Pm (xm|(()m=1))
(ll rm)an m-1
M+ (2n (enn (mmm-) p (ān
(an rej, - (Tim-1) max qn 2h (on/-1mm11) (T. (1 (1 ()))P
M mm) (1mp))mm)))) p (in- un 21 (2
max(0, a (In (am 11) pa (w (1
m=1
<> (ūn rej, 1) max(0, (Zm (11m-1) Pm
M
[ax (sm pa pa(an (1mm)))mmm)))))
mm)g M+1 ( ((m() p (in- In-1 xn
21m- 2 (21m-2))
m=1
(21)
where the first line uses n (Mnn//1 = q) (zn (inlxmmm)) the second equivalence uses Bayes rule, the third equivalence uses pA (Ztm) (IIm) = gn (x again. Now denote f(x1m)
pA (Øn rej, vn 1 ( and sum over Ti:n for the above to obtain
E Brin- ol [Pd (ā,
E. rej majjiimm111 E Emi..ngg
(-12m--1.P(-22mm
-Erya 1~f
TV(''.2) (()':p)(mmm1)) - [[ TV(g" ((((")))((mmmm))))
m=1
23

---

where by (21) pseudo-measure f satisfies Vain
f(11n) = max (2m - (a
[max((0 ( - (n( - II
Tm M+ (Roletm-i) ( ((lm-1). (22)
m=
Here we used T.m- Σ. max oh (af(tmm-)) Pm (x) Plug the above back (16), we finally have
B
Rm
E Si (
M II m=1
E TV(a" (p)()-))))))1))))
TV(4" ())mm
The formulation for f is iteratively obtained in (22).
D.2 Increasing batch size to inf doesn't help
Proposition 1. Let fM be the f in Theorem 3 with batch M, and let f lim M Then
have:
MM (-) g-).
(1) VM
(x(()))) h(2 2 (Iimn-) fth (21m-1)]
lim 1ann-==[[[Nep Ney = (E, [TV['' -1]1=11pppp (y ,)]).
M - Nryl + O. This indicates increasing batch size to an doesn't 't help.
Proof. First item: Recall in the proof of Theorem
defined as f(xim) : =ā rej, on 10 -1 1) (x (m1mn-1) =p-(an rej, on -i PP (x1m-1)) =PA(A, rej. 1I.) & (2 g (x
where the second equality is due to Batch algorithm is unbiased (Theorem 3).
Second item: by
[(1mm) (g (M
m=1
since ITM ((qm.p)(xee - 0 as M 0 (note TV (x = 1 iff there no overlap between 9thh and p), implics fd (IIm) = h(I,/==enlq' (#1m-1) - f00
Third item: Similar to the second item, it holds true via taking M - ap. For proving E[ > 0, suppose E[N 0. Then it holds g² f By the second item, this further implies f which is impossible.
Fourth item: We prove by contradiction. Suppose E[]N,]] -+ 0. then by the first item and the third item this implies q² f Plug this back the second item, this further implies f 0, so q² f = 0 is contradiction (q is a probability distribution)!
24

---

E
Proofs of Section
E.1 Proof of Theorem 4
For the sampling scheme where the acceptance probability 6n goes beyond min In (
Pr. (- ). there
a quality degradation for the output sequence as the algorithm leaning towards the draft model (smaller model). In this case, the objective is to minimize the quality degradation via considering the TV distance
min TV[ (- (-1Fiim-1) 1), qn (1(==1==-)]] VTim- E Vn
Under the above, via equation (14) the objective is equivalent to the following (note that according to Algorithm Pd (z,, draft token rejected, 11m Pn (n.aallainn is an algorithmic choice)
1
In (m())) - min(p)(()) + (n)))) (x) Iinn(E) gn(#)) cn (+)]+
min P.
2
(23)
s.t.
Σ (n()) 1, Pa(x) O, V.EV.
where we removed Ti:n-1 for notation simplicity. and recall again 6n := bnPr 9n. When
En 9n (ō) nn [+)]- O, the objective degenerates to the constant (in P.)) TV(gn. Pr.). Therefore, for the rest of the section, we focus on the case where Ex[p,,0) - qn( G, (+) 0.
We have the following Theorem that characterizes the solution of (23).
Theorem 10 (Restatement of Theorem 4). Suppose [p In - (x)+(x) > 0. Define
An(x) (n(x) min(pm (x) (z), (x) + En(x))
Σx (x) On (8) cn (+)]+
and define the positive token set A_ = fa E V (x) > 0) and the negative token set A_ for V : (x)x) < 0). Then the set of optimal distributions of objective (23) is characterized as
(P* P. 0, E A-; (*) (n( Mx A+: PP(()) =1),
and the optimal value is
(b)) 2 Σ (x)(x) (x). + cn(x))] [(pn(z) (n(x) - cn(z)]+.
Remarks 5. the main context (Theorem 4) we define An(x) == g. (1)))))
ba and Losstv(b) =
En (n((x) (x))))(())) E. (x()))p(()) This is equivalent to the above since en
OnPn On.
Proof of Theorem 10. In this case, note min(pn (2))) <n(2))) + [v,(1)) (x(x)) (n(x))
Pn(z), we have
- min(p. (n), (n(x)) ΣIp, - (x) c, (+)]+
(24)
By definition of An then Σx An = 1, and the original objective (23) can be equivalently written as
1 - s.t. Pp())= Pa(x) > O, Vx Pn.
min P.
(25)
We now find the solution of objective (25) in two steps.
Step1: Let the positive token set A, = {z Ax > 0} and the negative token set A_ {ar V Ax(x) (x) < 0). then any optimal p must satisfy Ptt 0 for all A..
First, since Σ (x) = 1, implies A, * Ø. Suppose for some optimal P there exists E A_
such that p*1 Z) 0, then we show there exists ă E A+ such that A, (ā) > P* (ø). Suppose this is
25

---

not the case, i.c. Ax(x) & (x) Vx é A+, then
1 Σ An(x) = Σ An(a) + Σ An(x) & +
Σ An(x) SEA+
uEA_
xEA+
Σ An(x) & Σ (x) & Σ Px(x)= =1
aEA1
sEA
reV
Contradiction! Hence, there exists á A+ such that (x) (2).
Second, by Ax( > PA (z). (T) 0, and triangular inequality, we have
- PP (+) + (a) (+) > (a, - (+) - (a)).
Note (z) < 0, the above is equivalent to
A 1 (z)) + (x) (*( A.. (An(2) P - -P)
(26)
Now set
(x)()), 2 (a.
Pa(x)= = 0, x= Z
P*( (t) ==
then apply (26) we have
Σ [A(i) - (x)]= Σ (x) (2) + (z) - P - (+)
xf
Σ -P())))(())1-) + A P. + (1
(*)
(a.a)
Σ x(
|n(x)) P(((') |A.()) + (A) (3) (T)
Σ
- -P))) A (7) ( + |4 (8) P(( |l) - -1) (x)())
This contradicts P* is the optimal solution! Therefore, for any optimal P*, it holds (*)
Vx A..
Step2: We characterize the optimal solutions of the objective. Indeed, by Stepl, any optimal solution P satisfies
Σ Amxx)) (+(x) Σ (z) +
Σ (z)
Px)(2))
8EA
ZeA
Σ [A,(2)) + xEA_
Σ An(x)) P Σ
A (x))++
Σ An(x) P+)x)
zeΛ+
ZeA+
zeA+
Σ
[A,())) +|
Σ
An(x) 1|= Σ |An())) Σ An(x) -1 ||
ZeA+
DEA.
The inequality becomes equality if and only if (z) (x)) 0. Finally, recall the definition of An we receive the optimal value for the original objective is
1 Ela((1) min(px(()) (x) + (z)))
_ Elpn(1) -0(()) en (x)]+
2
2
Replace en by by gives the desired result.
Remark 6. The general optimization should
(bss) min
where A == (bI.T, PIT)).
(27)
Meanwhile, our current anulysis only considers the single token setting. We mention that solving the (27) challenging as it corresponds to dime-siins discrete optimization with dimension T and it might not have closed-form solutions in the general cases.
26

---

E.2
Proof of Theorem 5
Proof. For an algorithm AA with the rejection probability b(-). Let p()), then the rejection probability is computed as
P(reject) Σ Prreeect, .) Σ P()) Σ ((1-b())p(3))
Also, from Theorem 4
Los) -(((x)- - b(x)p(x)) - Ea b()))((2)
Next, we show
- + (1 b())p()) Elp(z) g(x)))
Indeed, since min(1, 2(z) & b(x)) & 1, Vz E V. then (xx)((z) 3/ min(p(x), q(x)). Then we prove the following stronger claim
l4(x)
+ (1 bx))p((a) = lp(x) (=x)
If q(x)) > p(x), then = min [هاه
)ー) < b(x) < 1 implies b(x)) = 1, so the above is
equivalent [g(z) - p(x) = [p(z) - [ is always true;
If (()) < p(x), then ((z)p(2) > min(p(2). g(x). In this case
= p(z)-g(x) 1p(x))
This concludes the proof.
27

---

Numerical Simulation Details
To validate the correctness of our theory, we provide the numeric simulations that are displayed in Figure 4,2. We model the distribution P1:2" and Q1.r to be two non-stationary Markov Chains with 7 states/tokens. Instead of being ((=n( for Markov Chain, the one step transition Markovian with p [11:n=1) p(z, (n-1). We set the random seed to be 10. The prompt distribution Po is set to Uniform distribution. For Figure 2, the true value computed via Theorem 1,3 respectively, and solid line is computed by
N
Neej =
N
N
rej
and the shaded regions are error bars.
Below presents the simulation for horizon = 100. Left panel of Figure 5 is the standard speculative decoding, the middle panel is batch speculative decoding with batch size M and Right panel shows the expected rejections with varying batch sizes M computed from Theorem 1.
Spec Desxing
31.6
Thonmtieal Σ (p)l
Average Rejections
Expected Rejections
31.4
33.6
31.2
33.4
31.0
30.8
Retch SpadDaenda
Value. batch M
100
150
200
50
100
Number of runs 100
Number runs N 100
Expected Rejactions
2
10
M0
28
55
200
M 1000
500
1000
1500
2000
Figure 5: A simulation of (Batch) Speculative Decoding with horizon T 100.
28

---

G
Details for Experiment Section 4.2
Consider objective (I)
(o)) = min TV[P=, g]. where A (b.
(28)
For any biased algorithm with the given acceptance probability b> min(1, g/p), we can rewrite:
min 1, + () for some 0.
p
We consider the following two decoding options for P:
Baseline:
select to be suboptimal (28), i.e. simply set P := g, which is the target distribution; 10 We call this method Decoding-UNO.
Set P := pd to be the optimal solution of (28), whose solution presented in Theorem We call this method Decoding-
Measuring performance. Instead of TV distance, we measure the quality via WinRate in our experi- ment. Concretely, for each prompt, let Decoding-UNV and Decoding-OPT generate responses independently, and use score models to compare whose generation has higher quality. We specify draft model p as pythia- the score model to be RM-Misstal-77 atstttraallaaa or GPT-4. We test 200 prompts from Alpaca-Farm Farm Eval Dataset [13] with 500 responeescoopaarions per prompt. For given prompt, Decoding OPT wins if for more than 250 comparisons, score model prefer its response" over Decoding Then the WinRate for each method is computed as #wins/200.
and target model q as pythia-2. .b from EleutherA[ [7]. We apply
Sanity Check for the experiment. To validate having smaller distance w.r.t. the large model q (pythia-2.8) 8b) indicates higher performance, we preform the WinRate test for decoding via pythia-70m only against decoding via pythia-2. only. Table 2 shows that there is significant performance gap between large model and small model, therefore validate the legitimacy of the experiment in Table 1.
Method
RM-Mistral-7B
GPT-4
pythia-2.88
64.5%
69%
pythia-70m 35.5%
31%
Table 2: WinRate for pythia-2.88 2.8b vs pythia-2.288
Implementation detail for Table Concretely, we leverage EleutherAT/pythia-2 8b and EleutherA[/pythia-7000 from HuggingFace. To perform speculative decoding. spec- ify assistant httpeeeeeeeeeaerea//ttattaaaaaa. in the generation function for target model EleutherAT/pythia-2
Notice that for the biased speculative decoding with b(x) min(1, d(a)+ A(x) in Theorem 4 can p(r)
equivalently expressed as A(x) : Σg max (g(x) p()))
and we can select p = [A]+ (recall [+]+ max(a(x) ((()))
in Section 2.1), which satisfies 1 A = 0:0 p* A (+) {
To implement DeC, we modify the .speculative wereeeesaplinngg function in HuggingFace transformers/ sransformers//goerrtiioool conducted single A 100 GPU.
py file as follows (where variable eps is in Table 1). This
= [g - p]+ as the baseline since P = [g - p]+ might fall in the optimal solution sets of pp defined in Theorem 4.
1"To be rigorous, we mention we didn't i choose :=
We mention RM-Mistral-78 output values, outputs preference.
response with higer value wins. For GPT-4, Note the HuggingFace code p target model and the draft model, which is different from us.

---

def _
Seddidate_input_ite
#*#*#
## The following modification happens at Line 4727
## of the original file
mode_ = 1 // mode_=1 denotes Decoding-OPT, OPT, else denotes Decoding-UNO
eps_ 0.1 // This is the epsilon in Table 1.
eps eps_ torch. ones (p_1. shape, wtt.pddttrcc...llooii.eo f1oa332,, rrriceetorch.deviice (endaviecccccuaa00) cuda:01)) probability_ratio (p_i _eps_) q-i
#####
if gest__ssistantttooeee trtttanttttte__iiee is_ and n_matches == candidate_lengthn
n n_matches
yalid_tokens = nev_candidate__nnitt.dd
n_matches + 1]
else:
n_matches = min (n__matcchhes, max_matches)
gamma min (caadiddate_ wwwpeellooosstt.eeeeeeeee [1], max_ max_matches)
p_n_plus_1 pl:, n_matches, :]
if n_matches < gamma:
q_n_plus_1 q[: n_matches, :]
The following modification happens at Line 4760 ## of the original file
mode_ 1:
## The following two lines compute Axx)
p-prime torch. torch.clampl (paap((p___ppuut) wwt.meedd___pppp_______
q.n_plus_1), min -eps
sum
## The following two lines compute P* [A]_+
P-prime torch. torch.claappp......... www.ppp..mpppppppcee..e f_pprime, min= 0)
p-prime. div
else:
## Baseline Decoding-UNO p-prime = q_n_plus_1
30

---

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: We study the theoretical properties for Speculative decoding, which is identical what is stated in abstract.
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 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 be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the discussion section, we mentioned that we don't have lower bound the batch SD algorithms.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiitiinn asymptotic approximations only holding locally). The authors should reflect on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
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 impor- tant 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
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification:
We provide the full proof in appendix.
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 proofs can either appear in 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 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 ex- perimental 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 or not)?
Answer: [Yes]
Justification:
The code is written down in the appendix.
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 dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution 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.
specific model and empirical evaluation, may
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) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
32

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is in the appendix, the Alpaca data also public.
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/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ctcpp.cccppblic///eeecc geaiiiigggie/////eee /Coddeeumdmsmai cebbbmisssiioo sgionPolicy) for more details.
The authors should provide instructions on 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 baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have detailed section in Appendix.
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 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: [Yes]
Justification:
We have error bars in Figure 2.
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, confi- dence 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
33

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is 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 are out of range (e.g. negative emrr 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 or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of 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 well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp::://///.p.//eeeee
Answer: [Yes]
Justification: Yes, we followed that.
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.. if there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work most theoretical.
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 why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper has no such risks.
Guidelines:
The answer NA means that the paper poses 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 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. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: All the materials open- open-sourced.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if 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 (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
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.
35

---

If this information is not available online, the authors are encouraged to reach out to 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: [NA]
Justification: NO assets intorduced.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of 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. Crowdsourcing and Research with Human Subjects
Question: 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)?
Answer: [NA]
Justification:
No crowdsourcing involved.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, 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
Question: 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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on 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.
36


Reviews:
[{"review_id": "Pt4vqjpoz9", "reviewer": "Reviewer_Ceup", "summary": "This paper provides detailed analysis to speculative decoding and batch speculative decoding. The conclusions of the paper are: (1) speculative decoding is unbiased and it shows the expected rejection rate; (2) speculative decoding has the lowest rejection rate in all the unbiased algorithm that belongs to the familty defined in Algorithm 2; (3) batch speculative decoding has lower rejection rate than speculative decoding; (4) it analyzes the trade-off between efficiency and effectiveness of the family of algorithm defined in Algorithm 2.", "questions": "see weakness above", "limitations": "see weakness above", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides comprehensive theoretical analysis.\n\n2. The findings in Theorem 4 and 5 are interesting.\n\n3. The paper is easy to understand.", "weaknesses": "1. Although the paper provides lots of theoretical analysis. But I find only Theorem 4 and 5 are somewhat interesting. Theorem 1 is already derived in the original speculative decoding paper. For Theorem 2, although speculative decoding is proven to be optimal in the family of algorithms defined in Algorithm 2, but I don't think there are a lot of existing algorithms can be formulated in Algorithm 2. In fact, is there any algorithm that belongs to Algorithm 2 and is unbiad and it not speculative decoding? For Theorem 3, the finding that batch speculative decoding has lower rejection rate than vanilla speculative decoding is not surprising. \n\n2. Although Theorem 4 and Theorem 5 are interesting, it only solves half of the problem: given b, what should P be. It would be better if the authors could also discuss the design of b.\n\n3. I think the paper can also be improved if the authors could summarize a new speculative algorithm from Theorem 4 and 5 and running experiments to compare with vanilla speculative decoding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing detailed feedback. We have read your comments carefully and below are our detailed responses.\n\n**Q1:** ---- Although ... Theorem 1 derived in the original speculative decoding paper. For Theorem 2, is there any algorithm that belongs to Algorithm 2 and is unbiased and it not speculative decoding? For Theorem 3, ... is not surprising. ----\n\n**Response:** Thanks, but we respectfully disagree that only Theorem 4 and 5 are interesting, and we believe Theorem 1-3 have their own and new merits for understanding the theoretical properties for speculative decoding, which we detail below. \n\n**On Thm 1:** The key distinction between our Thm1 and [Leviathan et al.] is that their derivation assumes i.i.d. generation of LLMs (see “If we make the simplifying assumption that the beta’s are i.i.d.” under their Definition 3.1), which almost never holds in practice since the distribution of the next token depends on the past generations which is not i.i.d. From the theoretical aspect, our metric $T/\\sum_T E_{x_{1:n-1}~q}[TV(p_n,q_n)(\\cdot|x_{1:n-1})]$ captures the sequential dependence via the conditional dependence on $x_{1:n-1}$. In this sense, our result is a precise theoretical measurement of sequence (that have dependence between tokens), and the result in [Leviathan et al.] only holds for a single token or a fully i.i.d sequence which is not practical (also see our Remark2).\n\n**On Thm 2:** The significance of our optimality result is that it tells practitioners no improvement can be made over SpecDecoding if no other information can be leveraged. This is a theoretical guidance that can save time for practitioners who want to improve the efficiency of SpecDecoding. In addition, there are many algorithms that belongs to Algorithm 2 and is unbiased (i.e. in $\\mathcal{F}$) but is not speculative decoding. This is summarized in our **Corollary 1** in appendix. For any $b_n$ satisfies $b_n\\leq \\min\\\\{1,\\frac{q_n}{p_n}\\\\}$ for all $n\\in[T]$, we can find an Algorithm 2 that is unbiased. This exactly provide the intuition why is SpecDecoding is optimal: if an Algorithm 2 wants to be unbiased, it needs to have smaller acceptance probability $b_n$ than speculative decoding $\\min\\{1,\\frac{q_n}{p_n}\\}$. We were not able to include this in the main paper due to space constraint, and we will add a comment in the final revision. \n\n**On Thm3:** We agree with the reviewer’s intuition that batch algorithm can reduce the rejection rate, however, such a reduction the rejection rate is only observed empirically and a precise theoretical understanding of how much it can improve given the structure $p_n,q_n $ remains unknown. For instance, the nice work SpecInfer [Miao et al.] only prove the unbiasedness but there is no guarantees for decoding efficiency. To this end, we design a different parallel tree structure (Line 213) for batch setting. In order to derive the Batch Improvement term in Theorem 3, we design the novel intermediate quantity $f(x_{1:n})$ in D.1 with recursive computation for solving it, and the numerical simulation validates our theory. The significance of our batch theory is that: their is a scaling law for even using huge number of batches, meaning that the rejection rate won’t goes to zeros even the number of batch goes to infinity (see Figure 2 Right and D.2 in appendix). We believe all those insights are new.   \n\n**Q2:** ---- Although Theorem 4 and Theorem 5 are interesting, it only solves half of the problem: given b, what should P be. It would be better if the authors could also discuss the design of b. ----\n\n**Response:** Thanks. This is a good question. The design of $b$ is more heuristic since with higher $b$ (accpeatance probability), there will be less rejections and the decoding is faster, but it will suffer quality loss according Theorem 4. It is a matter of how much response quality one is willing to suffer for gaining better efficiency. In our simulations and experiments in 4.2, we specify $b(x)=\\min \\\\{1, \\frac{q(x)+\\epsilon}{p(x)}\\\\} $ for $\\epsilon$ ranging from 0 to 1. We will add more discussions in the final revision.\n\n**Q3:** ----if the authors could summarize a new speculative algorithm from Theorem 4 and 5 and running experiments to compare with vanilla speculative decoding.----\n\n\n**Response:** Thanks. Indeed, the new algorithm that summarizes Theorem 4&5 is exactly Algorithm 2. Concretely, with the choice of $b(x)=\\min \\\\{1, \\frac{q(x)+\\epsilon}{p(x)}\\\\}$, we specify the $\\mathcal{P}_t $ in Algorithm 2 to be the optimal one $\\mathcal{P}_t^\\star$ which is defined in Line 756 in appendix and the code implementation is in page 30 starting from ```if mode_ ==1```). We compare our optimal algorithm ```Decoding-OPT``` with a suboptimal algorithm ```Decoding-UNO``` to show higher WinRate across different $\\epsilon $s in section 4.2. In addition to that, as the reviewer requested, we conduct extra experiment below to compare the performance of ```Decoding-OPT``` and vanilla SD. The draft model is still ```pythia-70m``` and the target model is still ```pythia-2.8b```. The following table is the WinRate measured by GPT-4. We test 200 prompts from ```Alpaca-Farm-Eval``` Dataset with 500 responses per prompt. Since the standard SD preserves the quality of the large model, the WinRate of our biased algorithm ```Decoding-OPT``` will decrease as the over-acceptance parameter $\\epsilon$ goes large. On the other hand, the average runtime over 200 prompts for SD is much higher than ```Decoding-OPT``` in the third line of the table. This empirically validates ```Decoding-OPT``` provides a tradeoff between quality and efficiency against SD. Running the experiments in the table spent 50+ A100 GPU hours. \n\n| WinRate  | $\\epsilon=0.1$ | $\\epsilon=0.4$ | $\\epsilon=0.8$ |\n| --- | --- | --- | --- |\n| Decoding-OPT | 48% | 42% | 35.5% |\n| SD | 52% | 58% | 64.5% |\n| **Inference Acceleration rate:** Time(SD)/ Time(Decoding-OPT)  | 1.54 | 2.97 | 6.32 |", "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": "gobKxgntbI", "reviewer": "Reviewer_XUMm", "summary": "The author aim to develop theoretical understanding of speculative decoding. The authors assume that given a large and small model participating in speculative decoding, the computation complexity of the small model is negligible. Under this assumption, they characterize the expected rejection rate of speculative decoding. They show that this bound depends on the total variation distance between the generations from small and large model. Next, the authors show that spectral decoding gives optimal rejection bounds in class of all rejection based methods. Motivated by recent works analyzing batch speculative decoding, where the rejection is done only if M tokens are rejected from a given sample. Finally, given an acceptance probability, the authors show an optimal solution solution to the total variation loss between the distributions of large model and the one found by speculative decoding. This objective changes linearly with the rejection probability. This provides insights on selecting the optimal value of rejection threshold as per requirement. The presented theoretical results are backed up with appropriate experiments validating them.", "questions": "I request the authors to kindly address the questions in the weaknesses section.", "limitations": "Yes, the authors have addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The theoretical analysis presented by the authors provide several interesting insights about the inference efficiency observed by spectral decoding.\n\n2) All the results are backed up with simulation experiments, which strengthen the results presented in the paper.", "weaknesses": "1) It is not completely clear, why making the assumption about negligible compute of the small model is not a strong assumption. Since the small model needs to generate the tokens autoregressively therefore even though its single pass could be small as compared to the larger model but it the context length is high i.e. several autoregressive passes are made, the compute of small model might not be negligible. It would be great if the authors can provide some empirical evidence to justify this assumption.\n\n2) It would have been great if the authors provided evidence using real world models in support of their theory. Although, this is not a major weakness, but authors should consider it in the camera ready version.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive judgement and the detailed feedback. Here are the detailed responses. \n\n***Q1:*** It is not completely clear, why making the assumption about negligible compute of the small model is not a strong assumption. Since the small model needs to generate the tokens autoregressively therefore even though its single pass could be small as compared to the larger model but it the context length is high i.e. several autoregressive passes are made, the compute of small model might not be negligible.\n\n**Response:** Thank you for the question about our assumption. First, we fully agree that, in practice, all draft models cost some time. However, the main study goal of this paper is to understand the theoretical/probabilistic property of speculative decoding, and the cost-negligible assumption is an abstraction for the theoretical cleanliness. The assumption we made highlights that the cost is only negligible compared to the large model, rather than assuming it has zero cost. These two have fundamental differences since cost-negligible means there is some cost, and the cost is theoretically abstracted in the notation O(1) (see second part of Assumption 1) when compared to some costly large model. This is some known concept summarized in [Leviathan et al., Jie Ou et al.]. Empirically, this is also very meaningful. For instance, when measuring the inference time over 200 responses of Alpaca-Farm-Eval for model ```pythia-70m``` and model ```pythia-12b``` separately, the ratio ```Time(pythia-12b)/Time(pythia-70m)```$\\approx$ 12.8 for T=128 tokens, and for T=1028tokens, the ratio$\\approx $18.3 is even larger (this is not surprising since the decoding time for auto-regressive model is super-linear in its decoding length and large model would be even slower compard to the small models). In this case, the decoding time for ```pythia-70m``` is not cost zero, but is smaller than ```pythia-12b``` by magnitude, therefore cost-negligible.\n\n***Q2:*** It would have been great if the authors provided evidence using real world models in support of their theory. Although, this is not a major weakness, but authors should consider it in the camera ready version.\n\n**Response:** Thank you for the kind question. We believe the models we used in experiment 4.2 (```pythia-70m``` and ```pythia-12b```) are real-world models, and our experiment 4.2 shows that, for different level of $\\epsilon$  (over-accpetance), the optimal solution derived from Theorem 4 (```Decoding-OPT```) outperforms other suboptimal solutions (```Decoding-UNO```) consistently under the WinRate metric maresued by ```RM-Mistral-7B``` and GPT4. We will highlight this in the final version. Besides, we conducted two extra experiments as explicitly asked by reviewer Ceup and reviewer GGsr. Here we summarize it for you. \n\n1. In addition to experiment 4.2 where we validate the optimality of Theorem 4, we also compare the optimal algorithm (```Decoding-OPT```) with vanilla speculative decoding. Since the standard SD preserves the quality of the large model, the WinRate of our biased algorithm ```Decoding-OPT``` will decrease as the over-acceptance parameter $\\epsilon$ goes large. On the other hand, the average runtime over 200 prompts for SD is much higher than Decoding-OPT in the third line of the table. This empirically validates Decoding-OPT provide a tradeoff between quality and efficiency against SD. For more detail please see our response to reviewer Ceup ***Q3.***\n\n| WinRate  | $\\epsilon=0.1$ | $\\epsilon=0.4$ | $\\epsilon=0.8$ |\n| --- | --- | --- | --- |\n| Decoding-OPT | 48% | 42% | 35.5% |\n| SD | 52% | 58% | 64.5% |\n| Inference Acceleration rate: Time(SD)/ Time(Decoding-OPT)  | 1.54 | 2.97 | 6.32 |\n2. Empirically, we also compare the Batch SD with vanilla SD and compute WinRate (measured by GPT4) over 200 prompts from Alpaca-Farm-Eval Dataset with 500 responses per prompt and the inference acceleration. The table shows that the quantity of batch algorithm is nearly the same as the vanilla SD, but the decoding is faster. However, when batch is very large (e.g. 10), the decoding speed can slow down (1.392<1.416) and this might due to batch processing cost, suggesting that using a large batch is not ideal in the real-world scenarios. For more detail please see our response to reviewer GGsr ***Q1.*** \n\n| WinRate  | Batch = 2  | Batch = 4 | Batch = 8 | Batch = 10 |\n| --- | --- | --- | --- | --- |\n| Batch SD  | 48.5% | 49.5% | 49% | 49.5% |\n| Speculative Decoding | 51.5% | 50.5% | 51% | 50.5% |\n| Inference Acceleration rate: Time(SD)/ Time(Batch SD)  | 1.223 | 1.357 | 1.416 | 1.392 |", "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": "duKcJyPU8i", "reviewer": "Reviewer_GGsr", "summary": "The paper presents a theoretical perspective on speculative sampling. Through Theorems 1 and 2, the authors demonstrate that the sampling method employed by speculative sampling is optimal and unbiased. Subsequently, Theorem 3 introduces a multi-candidate approach to enhance the acceptance rate of speculative sampling.", "questions": "see weakness", "limitations": "na", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The writing is very clear, with takeaways provided under each theorem to explain the theory.\n\nTheorems 1 and 2 are crucial for speculative sampling. In paper [23], the authors showed that speculative sampling is unbiased but did not prove its efficiency compared to other rejection sampling methods. The proof provided here is very important.", "weaknesses": "The experiments are not sufficient. I would like to see improvements in batch speculative sampling in real-world scenarios.\n\nI am curious if batch speculative sampling can be combined with tree-style methods, e.g., [1] CaPE and [2] Medusa?\n\n[1] Du, C., Jiang, J., Yuanchen, X., Wu, J., Yu, S., Li, Y., ... & You, Y. GliDe with a CaPE: A Low-Hassle Method to Accelerate Speculative Decoding. In Forty-first International Conference on Machine Learning.\n[2] Cai, T., Li, Y., Geng, Z., Peng, H., Lee, J. D., Chen, D., & Dao, T. (2024). Medusa: Simple LLM inference acceleration framework with multiple decoding heads. In Forty-first International Conference on Machine Learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive comments and for the precise understanding of the theoretical contribution of our paper! Here are the detailed responses.\n\n***Q1:*** I would like to see improvements in batch speculative sampling in real-world scenarios.\n\nResponse: Thank you for the question. First, we want to mention that the main purpose of batch speculative sampling study is to understand its theoretical efficiency improvement. The key term we derived, the “Batch Improvement” in Theorem 3, is the net gain compared to the vanilla speculative decoding. When implementing the Batch algorithm 4 via the Markov Chain simulation, the plot in Figure 2 Right shows the improvement for the rejection rate as number of batches $M$ goes large. In addition, as the reviewer requested, we add the experiments for batch speculative decoding LLM decoding. Concretely, the speculative decoding of existing Hugging Face LLMs does not support batches, (i.e. the function ```_speculative_sampling``` in ```transformers/generation/utils.py```), so we modify the ```_speculative_sampling``` in page 30 by augmenting the related quantities such as ```candidate_input_ids``` with one extra dimension that contains batches. We then implement the batch algorithm 4 in the same function, and also modify the assisted_decoding function in transformers/generation/utils.py. We compare the Batch SD with vanilla SD and compute WinRate (measured by GPT4) over 200 prompts from Alpaca-Farm-Eval Dataset with 500 responses per prompt and the inference acceleration. The draft model is still ```pythia-70m``` and the target model is still ```pythia-2.8b```. The table shows that the quantity of batch algorithm is nearly the same as the vanilla SD, but the decoding is faster. However, when batch is very large (e.g. 10), the decoding speed can slow down (1.392<1.416) and this might due to batch processing cost, suggesting that using a large batch is not ideal in the real-world scenarios. Running the experiments in the table spent 70+ A100 GPU hours. \n\n| WinRate  | Batch = 2  | Batch = 4 | Batch = 8 | Batch = 10 |\n| --- | --- | --- | --- | --- |\n| Batch SD  | 48.5% | 49.5% | 49% | 49.5% |\n| Speculative Decoding | 51.5% | 50.5% | 51% | 50.5% |\n| Inference Acceleration rate: Time(SD)/ Time(Batch SD)  | 1.223 | 1.357 | 1.416 | 1.392 |\n\n***Q2:*** I am curious if batch speculative sampling can be combined with tree-style methods, e.g., [1] CaPE and [2] Medusa?\n\nResponse: Thank you for the in-depth question! This is an interesting aspect since the current Batch SD (Algorithm 4) is mostly suitable for theoretical study and might not be optimal for practical application. For instance, the batch rejection scheme in Algorithm 4 is to simply iterate over the next batch when the previous batches are rejected. It does not distinguish the unique characterizations of the batch candidate tokens. In this sense, CAPE [1], which uses uncertainty metric such as confidence score to adaptively choose the next token could further improve the chance of the token being accepted. Besides, Batch Algorithm 4 represents a simple parallel tree structure (Figure 3 Left), modify it with some tailor-designed tree-based methods such as tree-based attention in Medusa [2] is very likely to make batch decoding more efficient. We promise to add the discussions on [1],[2] in the final revision and leave how to make it work as future work.", "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": "SIeernQtsD", "reviewer": "Reviewer_qBZ2", "summary": "This paper presents a theoretical study on speculative decoding, an efficient inference method for large autoregressive models. It highlights practical implications, proposing a Pareto-optimal solution for the rejection-distribution bias tradeoff.", "questions": "NA", "limitations": "The results may not guarantee optimality in practical situations because real-world circumstances are more complex and varied than those considered in the theoretical analysis.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors provide a robust theoretical foundation, illustrating the practical implications of speculative decoding, such as the improvement of rejection accuracy, which cannot be achieved by simply changing the acceptance probability.\n - The study explores the trade-offs between inference cost and quality degradation, supported by an optimization model. This analysis is valuable for practical applications.", "weaknesses": "- The main figure does not clearly communicate the core concept of speculative decoding. It might lead readers to believe that speculative decoding primarily addresses hallucination, which is not its main advantage.\n - The experimental results are not distinctly highlighted, and the authors do not explain how these results support their theoretical analysis. While the theoretical contributions are significant, the paper would benefit from more extensive empirical validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive judgement and the great questions. Here are the detailed responses.\n\n***Q1:*** The main figure does not clearly communicate the core concept of speculative decoding. It might lead readers to believe that speculative decoding primarily addresses hallucination, which is not its main advantage.\n\n**Response:** Thank you very much, this is a very good suggestion! The purpose of Figure 1 is to show that, instead of direct decoding from the large model, speculative decoding will apply small model to decode and use large model as a verifier. We agree that without careful explanation the current figure might be confusing. We believe it is a easy fix and will modify it in the final revision.  \n\n***Q2:*** The experimental results are not distinctly highlighted, and the authors do not explain how these results support their theoretical analysis. While the theoretical contributions are significant, the paper would benefit from more extensive empirical validation.\n\n**Response:** We thank the reviewer for judging our theoretical contribution as significant. Regarding how the experimental results support our theory, our experiment 4.2 shows that, for different level of $\\epsilon$  (over-accpetance), the optimal solution derived from Theorem 4 (```Decoding-OPT```) outperforms other suboptimal solutions (```Decoding-UNO```) consistently under the WinRate metric maresued by ```RM-Mistral-7B``` and GPT4. We will highlight this in the final version. Besides, regrading the paper would benefit from more extensive empirical validation, we conducted two extra experiments as explicitly asked by reviewer Ceup and reviewer GGsr. Here we summarize it for you. \n\n1. In addition to experiment 4.2 where we validate the optimality of Theorem 4, we also compare the optimal algorithm (```Decoding-OPT```) with vanilla speculative decoding. Since the standard SD preserves the quality of the large model, the WinRate of our biased algorithm ```Decoding-OPT``` will decrease as the over-acceptance parameter $\\epsilon$ goes large. On the other hand, the average runtime over 200 prompts for SD is much higher than ```Decoding-OPT``` in the third line of the table. This empirically validates ```Decoding-OPT``` provide a tradeoff between quality and efficiency against SD. For more detail please see our response to reviewer Ceup ***Q3.***\n\n| WinRate  | $\\epsilon=0.1$ | $\\epsilon=0.4$ | $\\epsilon=0.8$ |\n| --- | --- | --- | --- |\n| Decoding-OPT | 48% | 42% | 35.5% |\n| SD | 52% | 58% | 64.5% |\n| Inference Acceleration rate: Time(SD)/ Time(Decoding-OPT)  | 1.54 | 2.97 | 6.32 |\n2. Empirically, we also compare the Batch SD with vanilla SD and compute WinRate (measured by GPT4) over 200 prompts from Alpaca-Farm-Eval Dataset with 500 responses per prompt and the inference acceleration. The table shows that the quantity of batch algorithm is nearly the same as the vanilla SD, but the decoding is faster. However, when batch is very large (e.g. 10), the decoding speed can slow down (1.392<1.416) and this might due to batch processing cost, suggesting that using a large batch is not ideal in the real-world scenarios. For more detail please see our response to reviewer GGsr ***Q1.*** \n\n| WinRate  | Batch = 2  | Batch = 4 | Batch = 8 | Batch = 10 |\n| --- | --- | --- | --- | --- |\n| Batch SD  | 48.5% | 49.5% | 49% | 49.5% |\n| Speculative Decoding | 51.5% | 50.5% | 51% | 50.5% |\n| Inference Acceleration rate: Time(SD)/ Time(Batch SD)  | 1.223 | 1.357 | 1.416 | 1.392 |", "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:

Meta-review: This paper provides detailed analysis of speculative decoding and batch speculative decoding. The conclusions of the paper are: (1) speculative decoding is unbiased and it shows the expected rejection rate; (2) speculative decoding has the lowest rejection rate in all the unbiased algorithm that belongs to the family defined in Algorithm 2; (3) batch speculative decoding has lower rejection rate than speculative decoding; (4) it analyzes the trade-off between efficiency and effectiveness of the family of algorithm defined in Algorithm 2.
The paper is well written and easy to understand. The theoretical analysis presented by the authors provide several interesting insights about the inference efficiency observed by speculative decoding. All the results are backed up with simulation experiments, which strengthen the results presented in the paper. After the author rebuttal, the only major remaining ask would be to see improvements in batch speculative sampling in real-world scenarios which is currently impossible.
Decision: Accept (poster)