Cascade Speculative Drafting for Even Faster LLM Inference
Authors: Ziyi Chen
Xiaocong Yang
Jiacheng Lin
Chenkai Sun
Kevin Chang
Jie Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: Speculative Decoding
Large Language Models
Efficient NLP
Primary area: natural_language_processing

Abstract: Introduced to enhance the efficiency of large language model (LLM) inference, speculative decoding operates by having a smaller model generate a draft. A larger target model then reviews this draft to align with its output, and any acceptance by the target model results in a reduction of the number of the target model runs, ultimately improving efficiency. However, the drafting process in speculative decoding includes slow autoregressive generation and allocates equal time to generating tokens, irrespective of their importance. These inefficiencies collectively contribute to the suboptimal performance of speculative decoding. To further improve LLM inference, we introduce Cascade Speculative Drafting (CS Drafting), a speculative execution algorithm that incorporates two types of cascades. The *Vertical Cascade* eliminates autoregressive generation from neural models, while the *Horizontal Cascade* optimizes time allocation in drafting for improved efficiency. Combining both cascades, CS Drafting achieves greater speedup compared to the baselines in our experiments, while preserving the same output distribution as the target model. Our code is publicly available at https://github.com/lfsszd/CS-Drafting.

Cascade Speculative Drafting for Even Faster LLM Inference
Ziyi Chen
Xiaocong Yang Kevin Chen-Chuan Chang Jie Huang
Jiacheng Lin Chenkai Sun
University of Illinois at Urbana- Chhama--ha {ziyic2, kcchang, jeffhj jelliiiiinnooi iil
Abstract
Introduced enhance the efficiency of large language model (LLM) inference, speculative decoding operates by having a smaller model generate a draft. larger target model then reviews this draft to align with its output, and any acceptance by the target model results in a reduction the number of the target model runs, ulti- mately improving efficiency. However, the drafting process in speculative decoding includes slow autoregressive generation and allocates equal time to generating tokens, irrespective their importance. These inefficiencies collectively contribute to the suboptimal performance of speculative decoding. To further improve LLM inference, we introduce Cascade Speculative Drafting (CS Drafting), a speculative execution algorithm that incorporates two types of cascades. The Vertical Cascade eliminates autoregressive generation from neural models, while the Horizontal Cascade optimizes time allocation in drafting for improved efficiency. Combining both cascades, CS Drafting achieves greater speedup compared to the baselines our experiments, while preserving the same output distribution as the target model
Introduction
The advent of Large Language Models (LLMs), like GPT-4 [17] has marked significant milestone in the field of natural language processing (NLP). These models have not only excelled in various NL.P tasks but have also found widespread applications user-interactive settings, such as chatbots and virtual assistants. However, these applications involve an extremely high number of users, up to hundreds of millions daily. To serve real-time at this scale, low-latency system not only cost-saving but also crucial for keeping the service running. In addition, the sheer scale of the service means that even slight improvement in the latency LLMs can greatly contribute to both the service provider and the community. Consequently, optimizing the latency of LLMs has become critical area of research.
Unfortunately, the ever weer-growing size of LLMs significantly increases the latency, especially in long-form generation, as autoregressive LLMs generate tokens one by one. An emerging solution, known speculative decoding [1]] 25 shows potential to mitigate this issue. In speculative decoding, draft model (which is smaller and faster) generates & tokens in each step (with being hyperparameter) autoregressively. and these tokens are then reviewed by target model (which larger and slower) in parallel. In one single run, the target model will accept any tokens aligned with its output and further generate one token. The drafting process in speculative decoding enables the target model to generate multiple tokens in a single run while maintaining its output distribution unchanged. With properly sized draft model, speculative decoding achieves a speedup of to times, making a potential method for solving high latency issues.
Code publicly available at
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Vertical Cascade
Horizontal Cascade
M
Cascade for Efficiency CS Draft employs larger models for crucial tokens and smaller models for less important ones. This time allocation enhances efficiency.
Twice the number
of books
that
Ma
M4z
Mds
M+
M12
Mág
Mds
Ma
Mds
CS Drafting
Mdr
Figure I: The CS Drafting algorithm features a recursive and resource-efficient design, implemented through two cascades: the horizontal cascade and the vertical cascade. The horizontal cascade involves using larger draft models to generate the earlier tokens and smaller models for the later tokens. The vertical cascade requires each model review drafts from smaller models with the exception of the smallest model, which is statistical language model. As the horizontal cascade and vertical cascade are orthogonal, CS Drafting combines both approaches for optimal efficiency. The figure shows an example of Cascade Speculative Drafting with target model M, and draft models Ma Mdg. and Mag-
However, since draft models are typically required to generate multiple tokens in multiple steps, where each generation still involves inefficient autoregressive decoding, the performance of speculative decoding could be limited by drafting latency. This inefficiency also indicated by Leviathan et al. [14,, where it was observed that very small models (e.g., around two orders of magnitude smaller than the target model) are usually the best choice for drafting because their inference cost is lower compared to that of a larger draft model, despite the fact that larger draft models usually have higher-quality generation. This underscores that improving drafting efficiency is crucial for further enhancing the performance of speculative decoding.
In light of this, one key strategy to address this bottleneck to avoid the inefficient autoregressive generation of neural draft models. Based on this consideration, it is noted that statistical language models, such as bigram language models, incur negligible latency and computational resource costs compared to neural language models, owing to their simple structure. However, because the tokens generated by statistical language models usually not have a high probability being accepted by the target model, speculative decoding with statistical language models alone may not yield optimal results compared to using a well-sized neural language model from the same family as the draft model. Nonetheless, notice that it is not necessary to only one draft model in speculative decoding-statistiien statistical language models can serve as the "draft" model for the neural draft model, thereby eliminating autoregressive generation from the neural draft model.
Furthermore, our analysis Figure 2 reveals pattern during the drafting step: tokens generated later in the sequence by the draft model show progressively lower probability of being accepted by the target model. This is because the probability of a token being accepted conditioned on the acceptance of the previous tokens. It indicates that later tokens from draft models are more prone to rejection, contributing less to the expected number of accepted tokens per draft step. yet incurring the same latency.
Inspired by the above observations, we propose Cascade Speculative Drafting (CS Drafting), speculative execution algorithm that comprises multiple draft models, with the smallest being statistical language model. Each neural draft model reviews generations from a smaller model and then proposes its reviewed content to either larger draft model or the target model. In this design, drafting of each neural model accelerated by drafting from a smaller model, avoiding the inefficiency of autoregressive generation from neural models. We refer to this tiered speculative decoding approach as the Vertical Cascade. In addition, we suggest the use of smaller, faster draft models for generating high-rejection tokens that are trailing in drafting generation, forming the

---

Acceptance
Te-amal 11.00-T--ara
FLAN-TS- base
0.6
0.5
0.4
0.3
0.8
15 Tokan posiioo
Tokan position
Figure 2: The probability of acceptance of draft tokens in relation to their positions in a single step of speculative decoding, evaluated on FLAN-TS-SMALL, BASE, and LARGE models on GSM8K and MMLU. The draft model generates 30 tokens at each step.
Horizontal Cascade. Along with the aforementioned Vertical Cascade, these strategies compose our complete CS Drafting approach, as illustrated in Figure
Through theoretical analysis and empirical studies, demonstrate that the CS Drafting algorithm outperforms speculative decoding in terms of latency across various tasks and settings, achieving an additional speedup of up to 81 % over speculative decoding. These findings highlight the practical advantages and efficiency enhancements offered by both vertical and horizontal cascades.
The main contributions are summarized as follows:
We introduce Cascade Speculative Drafting (CS Drafting), speculative seweiiiv--exeettoonn--ee based algorithm that improves language model inference speed without sacrificing generation quality.
We provide theoretical analyses supporting the effectiveness the proposed CS Drafting approach.
We conduct empirical experiments showing that CS Drafting achieves further speedup over specu- lative decoding across different tasks and settings.
2
Preliminary
The core concept of speculative decoding [14] involves the utilization of small draft model for sequential token generation with validation by larger target model resulting in reduced latency. This design accelerates sampling from autoregressive models without altering output distributions. At its heart, there are two key observations: 1) certain generations in language modeling are simpler than others and can be predicted by more efficient models correctly. and 2) using speculative execution along with new sampling method enables faster, exact decoding from large models.
Specifically, let x be the input tokens at a run and M₁ and Ma are the target and the draft model respectively, & be the number of draft tokens generated per step, and Mz(x) and Ma(x)) be their probability output at i-th token when input is x. We interpret speculative sampling as a two-stage operation. In the proposing stage, we sample (2e4,1..., from draft model Ma autoregressively and append them to x. In the reviewing stage, let 4; E (I.
Dr+k) represents
the token at the current position, and accept it if Ma(x) - 1] M.(x) 1]: in the event that
Mz(x){i 1] Mc(z)(i - 1). we reject x; with a probability of resample z; from recalibrated distribution norm norm(max(0, M,(x) Mo
Mi(x]ii1 and proceed to
Ma(( 1])) and reject any token following z4. At the end, the target model will generate one additional token following the accepted tokens. Such design guarantees the output is the same sampling autoregressively using the target model alone [1].
Speculative decoding was empirically validated on various tasks and model sizes, demonstrating a significant acceleration in inference times (2x-3x faster) compared to standard implementations, without affecting the outputs. Importantly, it does not require task-specific training, altering model architectures, or changing training procedures, making it a practical solution for reducing the latency of LLM inference.
3

---

Algorithm CascadeSpecclliiveerrttnnggg
Require: draft models (Mar..... ................................ Ma, target mode Mrs prefia, flag isFirslCall, hyperpa-
rameters Knns
draftList + [Md ....,..... Ma.]]
Initialize curGen and curProb.
curGen +- piefiz, curProbs +- a list of ones with the same length prefix
Unpack the list of k for the current function call.
[k1, -n..1]1 first row of K
Generate using MaG for the Base case of the recursive call.
if draftList is empty then
MM < first element of draftList
res M(curGen)
return res. res..enerationn.eee res.ogiit
end if
Perform the horizontal cascade with the for loop. for i to do
>> Prepare the arguments for the next recursive call.
curTarget < the i-th item of draftList
curDraftList + the sublist of diaftList starting from index i + curK + the submatrix of K from with the top-left corner at 1, + 1) extending the bottom-right corner curPrefix <-
curGen
while curGen.length curPrefix.length curPrefix <- curGen
less than k; do
Perform the vertical cascade with the recursive call.
Tuul [P1, P2, ... Po] + ChreadeSppeaaatiiiDDooiieeeeeees
cur curTarget, cur-
Prefix, False, curK, ()
curGen < [x1..., T.u
s + curProbs.length +
Add elements of [P1, P2, .... Pol to curProbs
end while end for
> Set lenience to when the original target model reviews.
if isll then 1+1
end
> Use Mr to review the draft generation.
[1 "i.. Fouth [p1. ..., Poue! review(M,, curGen, curProbs, return [I1, Tout [p', P2, Poutl
Cascade Speculative Drafting
In this section, we introduce our proposed method, Cascade Speculative Drafting (CS Drafting). speculative execution algorithm that incorporates two types of cascades: vertical cascade and horizontal cascade.
3.1 Vertical Cascade
A notable inefficiency of the speculative decoding algorithm is the reliance on the autoregressive generation of smaller draft model. Since the draft model must run & times for each target model run, the cost can still be significant despite its smaller size. In light of this, we reduce the drafting inefficiency by using an even smaller model to assist in drafting and employing the original draft model to review the generation of this smaller model. In addition, since this process can be performed again on the draft model that drafts for the original model, we recursively perform this process until reaches statistical draft model that involves negligent cost, such bigram language model. In this approach, we expect each recursion step will reduce the drafting latency without altering the output distribution. We refer to this recursive speculative approach Vertical Cascade.

---

Additionally, we incorporate lenience, hyperparameter that loosens the review process by the target model, allowing for faster speed at the trade-off of potentially differing results from the target model [14]. Lenience can be adopted during sampling or greedy decoding with speculative decoding. Let lenience E D.). When sampling, the acceptance condition for token o; is transformed to [a S i x M..a)(j. If the acceptance condition is not satisfied, with (x)
probability of Ma(a) we reject H, and any following tokens, When performing greedy decoding, the acceptance condition becomes deterministic and is simply either argmax.Maxx) (] or Mi( S </ Mz)
For the speculative decoding algorithm, the reduced quality introduced by lenience is generally undesirable. However, for the vertical cascade approach, lenience affects the final output only if it is applied when the target model reviews. Therefore, we can limit the application of lenience in the vertical cascade only when draft models review and do not apply lenience when the target model reviews. This can ensure the final output is not altered while further reducing latency.
3.2 Horizontal Cascade
Another key observation is that during the drafting steps of speculative decoding. not all drafting tokens are created equal, as illustrated in Figure 2 The first draft token is more likely to be accepted as it only depends on itself; the last token is rarely accepted, as it has chance of being reviewed only if all preceding tokens are accepted. From a theoretical perspective, assume the event of acceptance of each token being a Bernoulli distribution with probably p. the probability of n-th token being accepted is p", implying an exponential decrease of value for tokens generated later in the sequence.
Inspired by this observation, we designed Horizontal Cascade, an approach that improves time allocation by draft token allocation. Horizontal Cascade assigns the largest draft model to perform the generation of the first draft token due its highest output alignment with the target model, and progressively uses smaller as the new draft token to be generated is less likely to be accepted. This process stops after the smallest model, i.e., statistical language model finishes. This design reduces the time cost of generating unimportant draft tokens with costly draft model, leading to a reduction in overall latency.
3.3 Max-Gram for Better Statistical Drafting
As both Vertical Cascade and Horizontal Cascade remark cascade toward faster draft models, statistical language model, which is the basis of the cascade, becomes essential for the efficiency of both approaches. In our pursuit of more effective statistical language model, we noticed general patterm: in language model generation, some words and phrases from the input query frequently reappear in the generated content. In light of this observation, we designed the Max-Gram (MaG) algorithm. It greedily identifies maximal matches between the initial input (or existing generation) and tokens from the end of the generation. In cases where there is match, we resort to bigram model based on the probability distribution of Wikipedia (chosen to maintain the generality). We include GPU-friendly version of the Max-Gram algorithm Appendix A
3.4 Algorithm
Combining the horizontal and vertical cascades, the algorithm of cascade speculative decoding is presented in Algorithm[]] [ At its center, the horizontal cascade is realized by the for loop, while the vertical cascade is implemented through recursive calls. Notably, the MaG model is incorporated as the smallest draft model to avoid autoregressive generation from a neural model. An example of CS Drafting is shown in Figure
The algorithm requires an upper-triangular hyperparameter, K K with each row serving as the stop criteria for a layer of recursive calls. For simplicity, we assume the lenience is universal for the algorithm, except when the target model under review; thus, the algorithm can benefit from the speedup of lenience without altering the output distribution.
Forr simplicity, we assume the probability outputs are not standardized, We refer the readers to the speculative decoding paper [44] for the discussion on standardized sampling.
5

---

Analysis
In this section, we provide theoretical analyses for Cascade Speculative Drafting. We begin with some notions. Let M, be the target model, Ma be the draft model, and & be the number of draft tokens generated per step.
Expected acceptance rate a(Me, is the probability of draft generation by Ma being accepted by target model Mr-
Cost coefficient c(M,, is the ratio of time for a single run of draft model Ma over target model Mr.
Expected walltime improvement factor (EWIF) is the expected time improvement achieved by algorithm under the i.idd assumption of token acceptance.
Despite the simple setting of EWIF, it is demonstrated that it aligns with the experimental results in most instances [4. Therefore, our analysis will concentrate on EWIF
4.1 Vertical Cascade
We analyze EWIF of vertical cascade using generating functions, a well-studied topic in combinatorial mathematics 24 The properties of generating functions are useful in the recursion and evaluation process making our final expression simple.
We begin with the derivation of the probability generating function for speculative decoding.
Theorem 4.1. For speculative decoding between M, and Ma. let be the probability of generating tokens. The probability generating function of p. satisfies the following equation:
((a,)) + (x 1) 1 - a k+1 +
(1)
(1 a.)
where a a(M,;
Proof in Appendix C.I
(1a,)(1) 1-o
Corollary 4.2. The EWIF of speculative decoding is
(ck+1)
[T-a)ak+1)*
We use the generating function to derive the EWIF of a vertical cascade and analyze the case involving two draft models, Ma, and M&z-
Theorem 4.3. Assume k to be the speculative decoding parameter between Ma, and Ma and n to
be the number of steps M, reviews. The EWIF by this system
aΦ (ax)
(2)
(1-a)(1 + + nkcass'
where x(x) (in(MM Mag),)) M(Me, and cdi, Cdd be c(Mi, Ma,), M(Me) respectively.
Corollary 4.4. ((a) < a for any a 0,1 d' > 0, 0, so if cd. < 1. the EWIF of Md, and Mag is higher than EWIF Ma₃ alone.
Proof Appendix
Therefore, with the statistical model having negligible cost (i.e., ca, & 1), it can almost always improve the efficiency of an SD system.
4.2 Horizontal Cascade
We also present an analysis of the walltime improvement offered by the horizontal cascade.
To assist the analysis, we establish the notions. Let Mr be the target model, {M,} be the draft models assisting generation with M; being the draft model generating the i-th token. In the simpler case of the speculative decoding, M; = =Ma for any i. Let be the input to the model at a single run, (a( and M; are then the output probability distribution with input æ. To simplify notation, let a; ((M and e ((M)))).

---

Dataset
Mdi
M&s
k2
EWIF
CNNDM
SMALL
9
2.65
CNNDM
BASE
8
2.96
CNNDM
BASE
SMALL
5
3
3.03
ENDE
SMALL
12
3.61
ENDE
BASE
11
3.75
ENDE
BASE
SMALL
5
8
3.93
Table 1: Simulated EWIF under the assumption that the acceptance distribution is a Bernoulli distribution. BASE and SMALL refer to FLAN-T5-BASFF and FLAN-T5-SMATLL the simulation, speculative sampling with horizontal cascade exceeded the performance of the vanilla speculative decoding on both CNN Dailymail []6] and WMT EnDe datasets.
Theorem 4.5. The expected walltime improvement factor (EWIF) of the horizontal cascade is T(k, (1, o1,,... OKk C1,..,, (k) Σ 13
1+2
Furthermore, theorem 4.5 can be used to analyze the importance of the tokens in the drafting step.
Corollary 4.6. The probability of i-th token being accepted is IT Otj- The derivative EWIF og Specifically, dT(k (1 dog
with respect to oq is dT (1.mm0)))))))
Ei.
deg
1+22-1
Ei and ar (h...ts) 1+
11:=110
dosk
1+
Using the information provided by Leviathan et al. [4], we calculate a simulated EWIF under the assumption that the event of acceptance by the target model is Bernoulli trial. The results, shown Table indicate that speculative sampling with a horizontal cascade achieved better EWIF than vanilla speculative sampling under this assumption.
Experiments
5.1 Experimental Setup
Metries We use both our proposed standardized walltime improvement and walltime for evaluation:
Standardized walltime improvement (SWI) assumes each forward run of a model takes constant amount of time which can be recorded data of previous work [14] heuristics such the total number of the parameters of model. Under this assumption, the value of SWI is the speedup of the speculative method over autoregressive generation. SWT alleviates hardware variation and features full reproducibility of experiment results.
Walltime refers to the actual elapsed time taken to complete a specific task or operation real- world scenario. Despite being less reproducible and sensitive to noise, walltime better represents the performance for individual users. our experiment, walltime measured in the form of the number of tokens generated per second on our GPU.
Datasets We chose commonly used datasets for our experiments. For both datasets, we conducted experiments in a zero-shot chain-of-thought setup 13 23
GSM8K 7 is dataset comprising 8,500 high- linguistically diverse, grade-school math word problems. It focuses on multi-step reasoning with problems that are typically solvable using basic arithmetic in 8 steps.
MMLU 10], or Massive Multitask Language Understanding, is a benchmark for testing how well large language models grasp knowledge. It encompasses 57 diverse subjects, ranging from elementary science to advanced law.
Baselines To verify the effectiveness of both vertical and horizontal cascade strategies intuitively, we first compare the performance of CS Drafting with different numbers of cascades, as well as its performance against standard speculative decoding [1]. Additionally, CS Drafting can also operate

---

Dataset
Algorithm
{Ma,}
Speedup (MS)
Speedup (PW)
GSMSK
Autoregressive
GSM8K
S Decoding
BASE
3.38
2.99
GSMSK
S Decoding
SMALL
3.06
2.76
GSM8K
CS Drafting
BASE, MAG
3.70
3.27
GSM8K
CS Drafting
SMALL, MAG
3.19
2.82
GSM8K
CS Drafting
BASE, SMALL, MAG
3.88
3.43
MMLU
Autoregressive
MMLU
S Decoding
BASE
3.97
3.42
MMLU
S Decoding
SMALL
4.12
3.51
MMLU
CS Drafting
BASE, MAG
4.56
4.21
MMLU
CS Drafting
SMALL, MAG
4.39
3.99
MMLU
CS Drafting
BASE, SMALL, MAG
4.88
4.32
Table 2: The experimental results on FLAN-T5. Speedup (MS) is the standardized walltime improve- ment with the assumption that the latency of each run of model is its number of parameters (model size). Speedup (PW) the SWI with the assumption that the latency each run of a model the time cost data reported from previous work [14
vertically by combining with other advanced decoding methods. To verify this, we also leverage tree attention, as used in Medusa [3), and compare its performance with Medusa.
Implementation Details To ensure the generality of our findings, we perform experiments on both encoder-decoder and decoder-only models. For encoder-decoder models, we choose our target and draft models from the FLAN-T5 [6] family for our experiment, as there is large variation in model sizes within the FLAN-T5 family (ranging from 77 million to 11 billion parameters). We use FLAN-T5-XXL our target model, FLAN-T5-BASH and FLAN-T5-SM models. For decoder-only models, we select Vicuna-78 28) a fine-tuned version of LLaMA [2] as the target model. We use 68M model with the same tokenizer the reviewing draft mode 3 We also leverage tree attention [S 3 with CS Drafting for the experiments on Vicuna-7B.
as our reviewing draft
both cases, the Max-Gram algorithm is used as the generating draft model. Since we do not observe any significant difference between sampling with temperature and greedy decoding in previous speculative decoding experiments [14), and to ensure our experiments are fully reproducible, we perform sampling at temperature O, i.c. using greedy decoding by default. To align our experiment with current common usage, do not perform fine-tuning for CS Drafting, and the generation conducted in a zero-shot manner. We include hyperparameter details in Appendix B All of our experiments involving walltime are performed single NVIDIA A40 GPU.
5.2 Experimental Results
Table 2 presents the main experimental results. In two settings SWI, Cascade Speculative Drafting has outperformed the speculative decoding algorithm. For GSM8K, CS Drafting achieved maximum additional speedup of 44% over the fastest speculative algorithm; for MMLU, the maximum additional speculative decoding is 81%.
speedup improvement
Effectiveness of MaG When comparing CS Drafting with one neural model and MaG against the fastest speculative decoding setup, we found that CS Drafting with one neural model gained up to 70% speedup on MMLU and a 32% speedup on GSM8K. Notably, the MaG algorithm only involves bigram model with parameters equal to the tokenizer size, making its memory cost negligible." In addition, the speedup gained using CS Drafting with one neural model involves no additional deployment overhead while reducing both latency and computational cost, making it superior choice over speculative decoding.
Draft Model Size Despite FLAN-T5- mostly outperforming FLAN-T5-BASE as draft
model for speculative decoding, in CS Drafting with the aid of MaG, FLAN-T5-BASS consistently
8

---

Algorithm
GSM8K Walltime (Tokens/s)
MMLU Walltime (Tokens/s)
Autoregressive
33.34
33.11
S Decoding
44.31
43.65
CS Drafting
56.72
55.60
Medusa
61.87
56.19
CS Drafting Tree Attention
63.81
63.37
Table 3: The experimental results Vicuna-7B.
Koo
Walltime (tokens/s)
56.16
55.51
3
53.73
Table 4: Results GSM8K with Vicuna-7B under different generation length limits.
outperforms FLAN-TS-SMALL. This implies that with the limitation of single draft model, the ideal size of the draft model might increase with the assistance of the MaG model.
Results of Decoder-only Models As shown in Table B CS Drafting achieves significant walltime improvement over speculative decoding. Moreover, CS Drafting exceeds Medusa when combined with tree attention [15 3 This suggests that CS Drafting can be integrated with other efficient designs for speculative decoding further accelerate inference. We leave the exploration of more advanced combinations as future work.
Ablation Study We perform hyperparameter study Koo, the hyperparameter with the greatest effect on our experiments. As shown in Table 4 the performance of CS Drafting only decreases slightly when this hyperparameter is sub-optimal. Therefore, end users who do not require maxi- mum performance can use a simple setup to achieve near-optimal performance with CS Drafting. Furthermore, conduct ablation study by removing the horizontal cascade. On GSM8K, with Vicuna-7B and Koo = 1, this results a performance drop from 56.16 to 53.55.
Related Work
6.1
Efficienct Methods for Language Model Inference
In the of large language models, efficiency during inference becomes key model service. To reduce the model inference cost and speed up. several efficient methods have been proposed, including pruning, knowledge distillation and quantization (21). Model pruning takes structured (26) [2 un- structured
[ methods to remove the redundant model parameters to reduce the storage memory and increase inference speed. Knowledge distillation takes the approach of transferring knowledge from superior teacher model to a smaller student model [ 8) Quantization maps high-precision data rep-
resentations (e.g. bits) into low-precision ones (e.g. 8 bits) to reduce memory consumption [
6.2 Speculative Decoding
With the success of Speculative Decoding 4 14 in reducing the large language model inference latency, some recent works have attempted improve Speculative Decoding by reducing the rejection rate. Zhou et al. [29] propose using generalized knowledge distillation and achieve a lower rejection rate compared other knowledge distillation methods. Avoiding an additional draft model, self-drafting is an approach to speculative decoding by reusing part of the target model together with added weight to perform drafting [2]. Tree attention involves generating multiple candidates during drafting to increase the chance of acceptance [19 15]. Besides reducing the rejection rate, improving drafting efficiency can also reduce latency. Spector al. [9 propose using speculative decoding for drafting, showing similarities to the vertical cascade; however, their method only has two layers of speculative decoding and does not observe the recursive nature of the vertical cascade nor the lenience among draft models, two crucial aspects for the performance of vertical cascade.

---

7 Conclusion
In this work, we propose a novel algorithm, CS Drafting, which involves two cascades: the vertical cascade and the horizontal cascade. The vertical cascade eliminates the necessity of autoregressive generation from neural language model, while the horizontal cascade effectively allocates the cost of drafting tokens different positions. CS Drafting achieves additional speedup over baselines in various settings while maintaining the same output distribution as the target model.
Limitations
Our experiments demonstrate strong performance for methods. However, it is possible, though unlikely, that the outcome might differ on a system with different hardware configurations. To account for this, we report both standardized walltime improvement and raw walltime for a more robust evaluation. Additionally, we provide theoretical analyses to justify the improvements, which is independent of the hardware configurations.
Acknowledgement
This material is based upon work supported by the National Science Foundation IIS 16-19302 and IIS 16-33755, Zhejiang University ZJU Research 083650, IBM-IIlinois Center for Cognitive Computing Systems Research (C3SR) and IBM-IIlinois Discovery Accelerator Institute (IIDAI), grants from eBay and Microsoft Azure, UIUC OVCR CCIL Planning Grant 434S34, UIUC CSBS Small Grant 434C8U, and UIUC New Frontiers Initiative. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the funding agencies.
References
[1] Aishwarya Bhandare, Vamsi Sripathi, Deepthi Karkada, Vivek Menon, Sun Choi, Kushal Datta, and Vikram Saletore. Efficient 8-bit quantization of transformer neural machine language translation model, 2019.
[2] Ondřej Bojar, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Philipp Koehn, and Christof Monz. Findings of the 2018 conference machine transla- tion (WMT18). In Ondřej Bojar, Rajen Chatterjee, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Koehn, Christof Monz, Mattco Negri, Aurélie Névéol, Mariana Neves, Matt Post, Lucia Specia, Marco Turchi, and Karin Verspoor, editors, Proceedings of the Third Conference Machine Translation: Shared Task Papers, pages 272-303, Belgium, Brussels, October 2018. Association for Computational Linguistics.
[3] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason Lee, Deming Chen, and Tri Dao. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads, 2024.
[4] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXivv2302.01311$ 2023.
[5] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks, 2020.
[6] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, al. Scaling instruction-finetuned language models. arXiv preprint arXiv:22100 10. /416, 2022.
[7] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers solve math word problems, 2021.
10

---

[8] Jianping Gou, Baosheng Yu, Stephen J. Maybank, and Dacheng Tao. Knowledge distillation: A survey, International Journal of Computer Vision, 12966;1789-1819, March 2021.
[9] Demi Guo, Alexander M. Rush, and Yoon Kim. Parameter-efffiient transfer learning with diff pruning. 2021.
[10] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt, Measuring massive multitask language understanding, 2021.
[11] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network, 2015.
[12] Coleman Hooper, Schoon Kim, Hiva Mohammadzadch, Hasan Gene, Kurt Keutzer, Amir Gholami, and Sophia Shao. Speed: Speculative pipelined execution for efficient decoding, 2024.
[13] Takeshi Kojima. Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners, Advances in neural information processing systems, 35:22199-22213, 2022.
[14] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.
[15] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, Chunan Shi, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. Specinfer: Accelerating generative large language model serving with tree-based speculative inference and verification, 2024.
[16] Ramesh Nallapati, Bowen Zhou, Cicero Nogueira dos santos, Caglar Gulcehre, and Bing Xiang. Abstractive text summarization using peuuence-to-equemee rnns and beyond, 2016.
[17] OpenAL. Gpt-4 technical report, 2023.
[18] Clemens JS Schaefer, Elfic Guo, Caitlin Stanton, Xiaofan Zhang, Tom Jablin, Navid Lambert- Shirzad, Jian Li, Chiachen Chou, Siddharth Joshi, and Yu Emma Wang. Mixed precision post training quantization of neural networks with sensitivity guided search, 2023.
[19] Benjamin Spector and Chris Re. Accelerating Ilm inference with staged speculative decoding. arXiv preprint arXiv:2308. 0466334 2023.
[20] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale. Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiao- qing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023.
[21] Marcos Treviso, Ji-Ung Lee, Tianchu Ji, Betty van Aken, Qingqing Cao, Manuel R. Ciosici, Michael Hassid, Kenneth Heafield, Sara Hooker, Colin Raffel, Pedro H. Martins, André F. Martins, Jessica Zosa Forde, Peter Milder, Edwin Simpson, Noam Slonim, Jesse Dodge. Emma Strubell, Niranjan Balasubramanian, Leon Derczynski, Iryna Gurevych, and Roy Schwartz. Elficient methods for natural language processing: survey, 2023.
[22] Flena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned, 2019.

---

[23] Jason Wei, Xuezhi Wang. Dale Schuurmans. Maarten Bosma, Brian Ichter. Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of oftth-ughttttt prompting elicits reasoning in large language models, 2023.
[24] D.B. West. Combinatorial Mathematics. Cambridge University Press, 2021.
[25] 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 1909-3925, 2023.
[26] Mengzhou Xia, Zexuan Zhong, and Danqi Chen. Structured pruning learns compact and accurate models, 2022.
[27] Jun Zhang, Jue Wang, Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mchrotra. Draft verify: Lossless large language model acceleration via self-speculative decoding, 2023.
[28] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin. Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt- bench and chatbot arena, 2023.
[29] 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, 2023.
12

---

A Max-Gram Implementation
Listing 1: Max-Gram Algorithm
def forch_inders value)
return (t value) nonzero (as_ (as_tuple-True [0] [o]
def max_ goxx_gram(innut___. encoder_ida n=1):
matches (encoder_ ids [0] input_ide [0, -1]) (int()
if matches. sum
return None
for in range (2, input_ shape [-1] 1):
10
new_matches = lencoder_ide [0, (-1 * (i 1))] == input_idss -1 .inn()
11
cestched_matches (2 new_matchee
matches [1:]).int
if mumbined_matcheed sum < 1:
13
index torch_indes (torch. cat
15
torch. tensor(( (i 1), device=torch, devicc (encoder_ide (ids.devic))) matches
17
)
dim=-1
19
), 1)
return encoder_ide [;, index: : index + n]
21
else:
matches = combined_matchhe
23
index torch_index (torch. cat torch. tensor ([o] (encoder_ ids shape [-1] matches. shape shape(-1])), [-1])), matches), dim=-1
25
), 1)
return encoder ids [;, index+1:inder + n+1]
B Hyperparameters
To reduce the number of hyperparameters to tune, we use MaG to generate 10 tokens at once, as it is rare for more than tokens to be accepted with the exception when CS Drafting is combined with tree attention. We do not use lenience when the reviewer is M, to ensure the output distribution does not change. We also avoid lenience between MaG and its reviewer, since there is still a significant performance gap between MaG and a neural model. With these constraints, four hyperparameters: K11. k12, k22, and (. For the CS Drafting step where the target model the reviewer, k1 and 412 used. 121 and / are used in the step where Ma, is the reviewer. The results of experiments on encoder-decoder models with hyperparameters are shown Table 5
are left with at most
When performing experiments with the decoder-only model, we fixed the hyperparameters of CS Drafting for different datasets better align with most users who do not perform hyperparameter tuning. The k-matrix for CS Drafting is [[2, 10], J0, 10]]. When adding tree attention, we limit it to only the lead node with the highest probability having children; the k-matrix is [[1,3], [0, 1]] with the number of children for each leading node being 8, while the other nodes have no children.
C Proof
C.1 Proof for Theorem 4.1
Proof. The probability of accepting i tokens a² c++1, with the exception of the k + 1-th token, which has probability of & of being accepted. This is because it requires all the first tokens to be accepted and the + 1-th token to be rejected for this to happen. Therefore,
(x),))(x) = k42
Σ (a - a 1+1 )
13

---

Dataset
Algorithm
{Ma,}
Speedup (MS)
K11
k12
122
U
GSM8K
Autoregressive
GSM8K
S Decoding
BASE
3.38
10
GSM8K
Decoding
SMALL
3.06
11
GSM8K
CS Drafting
BASE, MAG
3.70
10
GSM8K
CS Drafting
SMALL, MAG
3.19
11
GSM8K
CS Drafting
BASE, SMALL, MAG
3.88
13
1
3
MMLU
Autoregressive
MMLU
S Decoding
BASE
3.97
13
MMLU
Decoding
SMALL
4.12
19
MMLU
CS Drafting
BASE, MAG
4.56
13
MMLU
CS Drafting
SMALL, MAG
4.39
MMLU
CS Drafting
BASE, SMALL, MAG
4.88
5
19
5
Dataset
Algorithm
(Ma;)
Speedup (PW)
k1
112
1/22
1
GSM8K
Autoregressive
GSM8K
Decoding
BASE
2.99
GSM8K
S Decoding
SMALL
2.76
8
GSM8K
Drafting
BASE, MAG
3.27
GSM8K CS Drafting
SMALL, MAG
2.82
11
GSM8K CS Drafting
BASE, SMALL, MAG
3.43
3
MMLU
Autoregressive
MMLU
Decoding
BASE
3.42
10
MMLU
S Decoding
SMALL
3.51
11
MMLU
CS Drafting
BASE,
4.21
MMLU
CS Drafting
SMALL, MAG
3.99
13
MMLU
CS Drafting
BASE, SMALL, MAG
4.32
5
Table 5: The experimental results FLAN-T5 with hyperparameter details. Speedup (MS) is the standardized walltime improvement with the assumption that the latency each run model its number of parameters (model size). Speedup (PW) is the SWI with the assumption that the latency of each run of a model is the time cost data reported from previous work [4] k11, kig, k22, are the hyperparameters. æ11 and 112 represent the step limitation target model and the draft models, k22 is the step limitations between the first and second draft model, and is lenience as shown in algorithm 1. For speculative decoding, the kn is simply the k.
By rearranging the terms, we can achieve an expression much easier to work with
h a ( x²)
(x))) = x
(4)
1=1
= x + (x - 1)
a (x*)
(5)
i=1
a + i
x +
(x 1)
(6)
C.2 Proof for Theorem 4.3
Proof. Let = aMMa, Ma.). We first calculate the expected number of tokens being generated in a step of vertical cascade with , Maz- With the property of generating function, the coefficient of term xd of (x)))) is the probability of the sum of acceptance length of speculative step being j. Therefore, d² (x: represents the probability generating function right before Mr performs the generation.
14

---

To achieve the expected number of token acceptances of betbabbiliy-generatinn function, we seek for an operator that can map the probability grobabilty-geneeraiin function into the desired expectation.
To achieve the operator, we begin with a single polynomial term of oz. Fortunately, given the end I-o I=af(o) will convert x to (I-a) In addition, due to the linearity of the operator, this be extended to any polynomial. Therefore, achieved the desired operator to map mrobabilit--generate function into the desired expectation.
result of 1-gوي (I-a) [4]. the operator To (f())) (1-a)
(I-a) Apply operator T to 6 (x)), we achieved the result of (o) for the expected number of accepted tokens. Furthermore, since the number of Ma, calls is and Ma, is called k time for each Ma, call given a total nkk calls of MMg. The time cost + ncd, + nkca, which implied the EWIF of 1-ad"((a) the system being [I-a)[1+noa; 4
a < ad', meaning that For Corollary 4.4 since both < a < 1 and 0 < < 1, we have ++
201 1. Together with 1 < O, we have (a) < + (a 1) a. If we also 1-aod
1-as"(a) let nkca, = 0. we have (I=a) +nkce2)
(1 (1-a)((-ncs,)" which is the EWIF for speculative
1-aa"
decoding with step size n.
15

---

NeurIPS Paper Checklist
You should answer (Yes]. [No], or [NA].
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper is focused on the scope introduced the abstract and introduction.
We provided experiments and analysis that fully support claim in the abstract and introduction.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We included limitation section to discuss the potential limitation of our work.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We introduced the assumptions and all notions used. We included proofs for non-trivial claims.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed 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)?
Question:
Answer: [Yes]
Justification: We provided our code and implementation details which is sufficient for reproducing the experiments in the paper.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We included our code and instructions the code. We also provided details such as hyperparameters in the appendix.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We included the experimental details in the main paper well as the appendix.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We reported the results across different metrics and explained the assumptions made.
8. Experiments Compute Resources
16

---

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: We discussed the GPU we used to run our experiments.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://ttw/ppappp.....c.////a//s
Answer: [Yes]
Justification: Our work focuses on efficiency, it's unlikely to violate any code of ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Our work focuses efficiency, do not think it will incur societal impacts.
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We did not release any models or datasets.
12. Licenses 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: [Yes]
Justification: We provided proper citations the datasets and models we use.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We did not release new asset.
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 as details about compensation (if any)?
Answer: [NA]
Justification: Our paper did not involve any crowdsourcing research with human subjects. 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: Our paper did not involve any research with human subjects.
17


Reviews:
[{"review_id": "l4SnfziQ9G", "reviewer": "Reviewer_LRu7", "summary": "This study introduces a novel method to accelerate large language model (LLM) decoding by integrating speculative decoding with two types of model cascades: vertical and horizontal. The horizontal cascade utilizes larger draft models for generating initial tokens, while smaller models assist in producing subsequent tokens. The vertical cascade implements a series of verification steps using a stack of cascaded models of varying sizes. Through the integration of these approaches, the authors report notable improvements in decoding speed across benchmarks.", "questions": "Please see the \"Weaknesses\" section.", "limitations": "Ok.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Originality** This paper demonstrates originality by expanding on speculative decoding. It introduces two novel techniques - horizontal and vertical cascades - that effectively factorize the draft-and-verification steps of speculative decoding across multiple models.\n\n**Quality and Clarity** The authors base their approach in intuitive assumptions, like the complexity of first token generation. The speed improvements over vanilla speculative decoding illustrate the effectiveness of the proposed methods.\n\n**Significance** The paper makes a considerable contribution to the community. Although CS drafting alone underperforms compared to Medusa (the multiple decoding heads method), the authors successfully combined their technique with Medusa, achieving superior performance. This suggests that their technique could be useful when integrated with other decoding methods.", "weaknesses": "**Algorithmic Complexity**: The paper discusses the use of horizontal and vertical cascades, but each additional cascade increases the algorithmic complexity of the decoding process. This complexity can become particularly challenging with larger models. The paper does not address how to balance this increased complexity with the potential speedup gains. Important questions such as the optimal number of cascades and the comparative usefulness of horizontal versus vertical cascades remain unanswered.\n\n**Ablation Study**: The max-gram drafting technique appears to be quite efficient for generating many tokens without needing to invoke other medium-sized models. However, the paper lacks an ablation study to analyze the impact of different model combinations on decoding performance. Including such a study would provide valuable insights into the efficiency and effectiveness of the proposed method.\n\n**Memory and Compute Constraints** The use of multiple models in complex scenarios poses challenges related to memory and computational limits. With limited memory and bandwidth, adding more cascades might not lead to faster end-to-end latency, especially as the target models grow in size. The paper does not consider this factor or provide a discussion on its implications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the significance of our contribution. We appreciate the insightful feedback provided and would like to address each of your questions.\n\n> Q1: Algorithmic Complexity\n\nTo make an additional smaller draft model meaningful in the CS Drafting algorithm, it needs to be much smaller than the smallest used draft model, typically by a factor of at least 10. This represents an exponential relationship between the number of draft models and the size of the target model, so the total number of draft models should ideally be capped at 6, even for trillion-parameter models.\n\nUnfortunately, we do not have sufficient GPU capacity to conduct inference with models large enough to establish the relationship between the number of parameters and the ideal number of draft models. While it’s unclear how much additional performance gain can be achieved by further increasing the number of draft models, we expect a similar performance boost by our algorithm on larger models while keeping the same level of system complexity.\n\n\n\n\n\n> Q2: Ablation Study\n\nWe have provided a thorough analysis on different combinations in Table 2. We are also happy to share the performance of various combinations of draft models for Vicuna-7B on GSM8K below:\n\n| Draft model | Walltime (Tokens/s) |\n| --- | --- |\n| MaG  |  52.89 | \n| Vicuna-68m | 44.31  | \n| Vicuna-68m & MaG | **56.72** | \n\n\nWe observe the effectiveness of MaG as it exceeds the performance of Vicuna-68m due to its nearly zero latency. The optimal performance in our experiment is achieved by using both MaG and Vicuna-68m as draft models.\n\n\n> Q3: Memory and Compute Constraints \n\nWe conducted an experiment to monitor memory usage across different systems accelerating Vicuna-7B on GSM8K:\n\n| Method | GPU Memory(MiB) |\n| -------- | ------- |\n| Huggingface Generation  | 14,016 | \n| CS Drafting | 16,154  | \n| Speculative Decoding | 16,118 |\n\nWhile both Speculative Decoding and CS Drafting utilize a moderate amount of memory compared to Huggingface generation, there is little difference between the performance of CS Drafting and Speculative decoding due to the additional draft models used by CS Drafting being much smaller than the first draft model.", "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": "YMxgpO14UA", "reviewer": "Reviewer_FGcM", "summary": "The paper proposes to use multiple draft model for speculative decoding. Specifically, the smallest model could be the statistic language model which has negligible latency therefore reducing the cost of autoregressive regression. Experiments show the proposed method works better than baselines.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The idea is very interesting and supported by analysis such as Figure 2.\n\n(2) Experiments show the proposed method works well.", "weaknesses": "(1) Algorithm 1 is heavy and should be simplified for the reader.\n\n(2) The whole pipeline seems to introduce lots of engineering work. For instance, we need to set hyperparameters for how to choose model size for each token position. Lenience is also used which is good but increases the complexity of the pipeline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for highlighting the idea, analysis, and experiments of our paper. We appreciate the feedback provided and would like to address the weaknesses mentioned.\n\n> Q1: Algorithm 1 is heavy and should be simplified for the reader.\n\nWhile we made numerous attempts to simplify the algorithm, we always found that simplified versions missed essential details needed by end users. To better help readers understand our algorithm, we would like to add the following summary as a caption to the algorithm:\n\nThe heart of the CS Drafting algorithm involves using smaller models as drafters for larger draft models (vertical cascade) as well as allocating smaller draft models to continue drafting less important tokens after larger draft models (horizontal cascade). \nAlgorithm 1 implements these two cascades by using a for loop and recursion. The for loop is responsible for the horizontal cascade by gradually limiting the usable draft models to smaller models. The recursion calls smaller draft models to perform drafting for the target model or large draft models.\n\nWe will also add more explanations of the variables to make them easier for the readers to understand.\n\n> Q2: The whole pipeline seems to introduce lots of engineering work. For instance, we need to set hyperparameters for how to choose model size for each token position. Lenience is also used which is good but increases the complexity of the pipeline.\n\n\n We understand your concern about the number of hyperparameters. However, having additional hyperparameters is an intrinsic problem of algorithms utilizing speculative execution as hyperparameters are usually necessary to be adjusted based on the probability of acceptance.\n \nAs a remedy to the additional hyperparameters, during our experiments with Vicuna-7B, we used the same hyperparameter across different datasets for each model. This represents the performance of CS Drafting without meticulous hyperparameter tuning.\n\nWe also include the experiment results with different $K_{00}$ (the entry limiting the generation length of the largest draft model. This is the hyperparameter that has the largest effect on our experiments) on GSM8K using Vicuna-7B:\n\n\n| $K_{00}$ | Walltime (tokens/s) |\n| -------- | ------- |\n| 1  | 56.16 | \n| 2  | 55.51 |\n| 3 | 53.73 |\n\n\nAs shown in our experimental results, the performance of CS Drafting only decreases slightly when the hyperparameter is sub-optimal. Therefore, the end user who does not require maximum performance can use a simple setup to achieve near-optimal performance with CS Drafting.", "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": "fz1dGIJHXC", "reviewer": "Reviewer_qvRP", "summary": "This paper concentrates on the inference efficiency of LLMs and thinks that the autoregressive generation contained in drafting process of speculative decoding leads to the suboptimal performance of speculative decoding.  It introduces a novel speculative execution algorithm,  Cascade Speculative Drafting (CS Drafting), which containes Vertical Cascade and Horizontal Cascade to achieve better speedup, while preserving the same output distribution as the target model.", "questions": "1. The description of the core algorithm, Algorithm 1, in this paper is not clear. It would be helpful to include an explanation of the overall logic of the algorithm and add descriptions of some variables. \n2. The paper lacks relevant ablation experiments to illustrate the relationship between the two cascade methods and lacks analytical experiments to demonstrate the robustness of the method with different numbers of candidate tokens.", "limitations": "The authors adequately addressed the limitations and, if applicable, potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed model introduces a new framework that fully considers the acceleration at different granularities and varying capabilities of the model to complete decoding. \n2. The method proposed in this paper is model-agnostic and does not require additional training of the model.\n3. Experimental results indicate that compared to the vanilla model, the proposed model can achieve better speedups.", "weaknesses": "1. The model employs a heuristic approach, involving a large number of hyperparameters, especially the $k$-matrix, whose quantity is related to the involved drift models. \n2. The experimental results are not sufficient. On one hand, it does not compare with the latest speculative decoding methods. On the other hand, the model does not explore performance with different number of candidate tokens. It also lacks ablation studies and does not individually investigate the different impacts of the two cascade methods.\n3. There are writing issues in the article, such as the first line of Algorithm 1, line 178, and line 292. Additionally, many variables in Algorithm 1 are not explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for highlighting the advantages of our method. We appreciate the insightful and detailed feedback, and would like to address each of your concerns.\n\n> W1: The model employs a heuristic approach, involving a large number of hyperparameters, especially the K-matrix, whose quantity is related to the involved drift models.\n\n We understand your concern about the number of hyperparameters. However, having additional hyperparameters is an intrinsic problem of algorithms utilizing speculative execution as hyperparameters are usually necessary to be adjusted based on the probability of acceptance.\n \nAs a remedy to the additional hyperparameters, during our experiments with Vicuna-7B, we used the same hyperparameter across different datasets for each model. This represents the performance of CS Drafting without meticulous hyperparameter tuning.\n\nWe also include the experiment results with different $K_{00}$ (the entry limiting the generation length of the largest draft model. This is the hyperparameter that has the largest effect on our experiments) on GSM8K using Vicuna-7B:\n\n\n| $K_{00}$ | Walltime (tokens/s) |\n| -------- | ------- |\n| 1  | 56.16 | \n| 2  | 55.51 |\n| 3 | 53.73 |\n\n\nAs shown in our experimental results, the performance of CS Drafting only decreases slightly when the hyperparameter is sub-optimal. Therefore, the end user who does not require maximum performance can use a simple setup to achieve near-optimal performance with CS Drafting.\n\n\n>  W2: The experimental results are not sufficient. On one hand, it does not compare with the latest speculative decoding methods. On the other hand, the model does not explore performance with different number of candidate tokens. It also lacks ablation studies and does not individually investigate the different impacts of the two cascade methods.\n\nThank you for your comment! We have included extensive results for different settings in Table 2 and have conducted a different set of experiments shown in Table 3. Following your suggestion, we include additional experimental results with different $ K_{00} $ (refer to response to W1 above).\n\nAs an ablation study, we removed the horizontal cascade from CS Drafting. This results in a performance decrease from 56.16 to 53.55 when $ K_{00} = 1$. This demonstrates the effectiveness of the horizontal cascade. For the vertical cascade, the reviewer may refer to our results in Table 2. The performance usually decreases when we remove a draft model, indicating the effectiveness of the vertical cascade. Additionally, our theoretical analysis in Section 4 also supports the improvement of both cascades when isolating one of them.\n\nRegarding the comparison with other speculative decoding methods, we have compared our results with both Medusa and speculative decoding. While we are aware of newer methods such as Eagle or Hydra, we would like to remind you that our experiments were performed before their introduction and our preprints were available months earlier than theirs.\n\n\n>  W3: There are writing issues in the article, such as the first line of Algorithm 1, line 178, and line 292. Additionally, many variables in Algorithm 1 are not explained.\n\nThank you for the detailed feedback on writing. We will do a more careful proofread to fix typos and add explanations of the variables.\n\n>  Q1: The description of the core algorithm, Algorithm 1, in this paper is not clear. It would be helpful to include an explanation of the overall logic of the algorithm and add descriptions of some variables.\n\nWe would like to adopt the suggestion to improve the clarity. The following is the overview of our algorithm.\n\nThe heart of the CS Drafting algorithm involves using smaller models as drafters for larger draft models (vertical cascade) as well as allocating smaller draft models to continue drafting less important tokens after larger draft models (horizontal cascade). \nAlgorithm 1 implements these two cascades by using a for loop and recursion. The for loop is responsible for the horizontal cascade by gradually limiting the usable draft models to smaller models. The recursion calls smaller draft models to perform drafting for the target model or large draft models.\n\nWe will also ensure that all variables in the algorithm are properly defined and are easy to understand to the readers.\n\n> Q2: The paper lacks relevant ablation experiments to illustrate the relationship between the two cascade methods and lacks analytical experiments to demonstrate the robustness of the method with different numbers of candidate tokens.\n\nThank you for your suggestion! Please refer to our response to W1 and W2.\n\nThank you again for reviewing our paper! We hope our response addresses your questions. Please let us know your thoughts, and we are more than happy to answer any further questions.", "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 introduces a novel approach to accelerating LLM decoding by combining speculative decoding with vertical and horizontal model cascades. The originality is evident in the innovative techniques: horizontal cascades, which use larger models for initial tokens and smaller ones for subsequent tokens, and vertical cascades, which verify outputs through a series of cascaded models. The authors effectively demonstrate speed improvements over traditional speculative decoding and show that their method can enhance performance when integrated with existing techniques.

To further strengthen the paper, the authors should incorporate valuable discussions from the review period into the final version. This addition would address any remaining gaps and improve the clarity of the proposed methods. Overall, the paper is an original contribution to the field, and I recommend it for acceptance.
Decision: Accept (poster)