SpecExec: Massively Parallel Speculative Decoding For Interactive LLM Inference on Consumer Devices
Authors: Ruslan Svirschevski
Avner May
Zhuoming Chen
Beidi Chen
Zhihao Jia
Max Ryabinin
Venue: NeurIPS 2024 poster (2024)
Keywords: speculative decoding
offloading
large language models
inference
Primary area: natural_language_processing
TL;DR: We propose a speculative decoding algorithm that scales with large token budgets and allows running 50B+ models on a single GPU up to 15x faster than standard offloading

Abstract: As large language models gain widespread adoption, running them efficiently becomes a crucial task. Recent works on LLM inference use speculative decoding to achieve extreme speedups. However, most of these works implicitly design their algorithms for high-end datacenter hardware. In this work, we ask the opposite question: how fast can we run LLMs on consumer machines? Consumer GPUs can no longer fit the largest available models and must offload them to RAM or SSD. With parameter offloading, hundreds or thousands of tokens can be processed in batches within the same time as just one token, making it a natural fit for speculative decoding. We propose SpecExec (Speculative Execution), a simple parallel decoding method that can generate up to 20 tokens per target model iteration for popular LLM families.  SpecExec takes the most probable continuations from the draft model to build a "cache" tree for the target model, which then gets validated in a single pass. Using SpecExec, we demonstrate inference of 50B+ parameter LLMs on consumer GPUs with RAM offloading at 4--6 tokens per second with 4-bit quantization or 2--3 tokens per second with 16-bit weights. Our code is available at https://github.com/yandex-research/specexec .

SpecExec: Massively Parallel Speculative Decoding for Interactive LLM Inference on Consumer Devices
Ruslan Svirschevski-ft
Avner May**
Zhuoming Chen
Beidi Chen to Zhihao Jia Max Ryabinin
i Yandex
@ HSE University
Together AI $ Carnegie Mellon University
& Meta AI
ruslansv@gmail com, avner@together... ai, zhuominc&andrew cmu. edu,
{zhihaoj2 beidic beidic)@@ndree Candrew. cmu edu, mryabltogether.c
Abstract
As large language models gain widespread adoption, running them efficiently becomes a crucial task. Recent works on LLM inference use speculative decoding achieve extreme speedups. However, most of these works implicitly design their algorithms for high-end datacenter hardware. In this work, we ask the opposite question: how fast can we run L.LMs on consumer machines? Consumer GPUs can no longer fit the largest available models and must offload them to RAM or SSD. With parameter offloading, hundreds or thousands of tokens can be processed batches within the same time as just one token, making it natural fit for speculative decoding. We propose SPECEXEC (Speculative Execution). a simple parallel decoding method that can generate up to 20 tokens per target model iteration for popular LLM families. SpecExee takes the most probable continuations from the draft model to build "cache" tree for the target model, which then gets validated in a single pass. Using SpecExec, we demonstrate inference of 50B+ parameter LLMs consumer GPUs with RAM offloading 4-6 tokens per second with 4-bit quantization or 2-3 tokens per second with 16-bit weights.
Introduction
Open-access large language models (LLMss, such as Llama [Touvron et al., 2023 and Mistral [Jiang al., [023], have become increasingly capable the past years, and their adoption has grown dramatically. Although these models are openly available, users who are interested in running these models on consumer- -anuuee--graee GPUs (for example, due to privacy or cost reasons) face significant challenges. Many open-access LLMs are too large to fit on consumer GPUs, which necessitates offlouding them onto CPU RAM to perform inference. Given the limited memory bandwidth between the CPU and the GPU, as well as the fact that all model parameters must be transferred to the GPU for the LLM to generate each new token, offloading is extremely slow and hoandwidth-boun For example, generating single token using Llama 2-70B in 16 bit with offloading on an RTX 3090 GPU takes at least 4.5 seconds
A recent line of work that aims to speed up LLM inference is speculative decoding [Leviathan et al. 2023 Chen et al.) [023a], which uses a small draft model to predict the next tokens and a larger target model to verify which of those tokens to accept in parallel. Although speculative decoding a promising direction, the speedups that existing methods can attain in the offloading setting are relatively modest. While studying existing approaches [Leviathan et al. 2023 Miao et al. 2023 Sun et al., 2023]. we discovered that these methods do not scale well with the draft model token budget. In particular, as shown in Figure (left), the number of tokens accepted by the target model is
"qqual contribution.
'The code is available at aiggtthu.. www./yannw--eeeeeeeeeooe www.rrreseeeceeeeeeeeeeeeeeeeeee
2 AAssuming PCIe-4.0 and at least 140GB of DDRS RAM with an efficient offloading implementation.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

8 Generated tokens--lep
24
SpeeExee Speeliier
2048 Llamn227088 FP16, A100, offlowded, PCIc 4.0
Forward pass time, sec
20
Llama2-7B FP16,
8
16-
12-
8-
8
16
32
64
128
256
512
1024
4096
32
128
256
512
1024
2048 4096 8192
Deaft model outgut size tokens
Number of processed takens
Figure I: Acceptance counts vs draft size (left), forward pass GPU time vs input size (right). Llama
2-7B draft model, offloaded Llama 2-70B target model, MTBench dataset, t=0.6 and top-p=0.9.
empirically upper-bounded (approximately by 10 for this model and dataset combination) regardless of the number of speculated tokens. In turn, methods that scale better with more draft tokens Chen al.] [2024a] rely on static tree structures that may not be optimal for every setting, as they require tree structure optimization for every change in the text domain, generation parameters, and the hardware setup.
In this work, we aim to improve the effectiveness of speculative decoding for running large language models on consumer hardware with RAM offloading. We propose SpecExec, speculative decoding method that addresses the performance, flexibility and scalability issues of prior methods. SpecExed adopts powerful draft model deterministiially constrrut a large draft tree that covers the most likely continuations of the prefix with parallel search algorithm. We then apply simple verification algorithm that views this tree as a cache of potential continuations and validates with the target model in single pass.
Our main contributions be summarized follows:
1. We analyze the empirical behavior of speculative decoding algorithms with large language models and identify ways to improve their acceptance rate when scaling to thousands of draft tokens.
2. We propose SpecExec draft trees for very large token budgets. We demonstrate that this technique can produce draft trees resulting in 10-20 accepted tokens with sufficiently large budgets.
speculative decoding algorithm that improves the structure of generated
Using our observations and SpecExec, we design a system that can run Llama 2-70B or comparable models interactively at 4-6 tokens/second using 4-bit quantization or 2-3 tokens/second with 16-bit weights on consumer GPUs with offloading, with 10-18x speedups compared sequential inference on the same hardware.
2 Background
2.1 Speculative Decoding
In this study, we extend family of algorithms for speculative decoding of autoregressive LLMs Stern et al. [2018), Levitthan et al. (2023), Chen et al. [2023a] These algorithms generate tokens in two phases: drafting and verification.
During the drafting phase, the algorithm generates a candidate sequence of tokens by sampling from small draft model P(r++1 |20:,, a. In turn, the verification stage leverages the target model P( [oo:. fmmii)) to verify these draft sequences and accept all tokens that have passed the verification. The probability of accepting token is chosen in way that preserves the output distribution of sequential sampling from the original Leviathn et al. [2033 Chen et al. [2023a], Sun al. 2023). key advantage of speculative algorithms is that the main model can verify all draft tokens in parallel, which is more efficient than sequentially generating one token at time.
We chose this name because method directly applies speculative execution LLM inference. The draft model "guesses" which token prefixes the target model need to continue, and then the target model computes distrihutions continuations with single forward pass on the speculated prefix tree. In contrast, speculative sampling requires stochastic generation of the draft tree using draft probabilities.

---

Subsequent works in speculative decoding extend this idea in several directions, including generating
multiple draft sequences or draft trees, using multiple draft models, and finetuning the draft models
to improve generation speed Miao et al. [023)] Liu et al. [2023] Xuu et al. [023). Another line of
follow-up studies explores alternative sources for the draft model: namely, self self-speculative decoding
uses a subset of main model layers to produce draft /Zhang et al. [2023]. REST retrieves draft
sequences from a search index He et al. 2023). and staged speculative decoding uses multiple levels of speculation Spector and Re [023)] Leveraging these techniques, practitioners have built efficient implementations for fast LLM inference [Miao et al. 2023 Cai et al., 2023]. We refer the readers to
survey papers for more detailed coverage of speculative decoding methods Zhang et al. [2024a].
Xia et al. 2024a].
In our analysis, we focus on speculative decoding algorithms that support sampling from the target model and guarantee identical sample probabilities vs standard generation. The rationale for our choice is that most popular LLM applications (such as chat assistants) require stochastic sampling to introduce variability into their responses. This focus rules out several algorithms that only support greedy inference Fu et al. [2023] Liu et al. [2023]. Still, most works speculative decoding fit within that criterion.
2.2 Parameter Offloading
Another recent line of work explores running and training large models with limited accelerator mem- ory by "offloading" their parameters to more abundant storage, such as RAM or even SSD [Pudipeddi] et al. 2020 Ren et al.] 2021] Alizadeh et al.) [023]. This technique works by loading model parame- ters on the GPU when they are needed for computation. Since most deep learning models use layers in fixed order, offloading can pre-dispatch the next layer's parameters in the background.
This technique works particularly well when processing large batches of data, during train- ing Pudipeddi et al. [2020] Ren et al. [202T] or large-batch non-interactive inference Aminabadi et al. J022J.[Shemy et al. [2023), where each layer process multiple tokens each time is loaded. In turn, when doing interactive inference, offloading works significantly slower than on-device inference. This is because interactive inference has to process one or few tokens at a time, and therefore spends most of the time waiting for the parameters to load.
2.3 Running LLMs on Consumer Devices
While our observations are not specific to any particular L.LM, we focus on a practical case of run- ning modern instruction-tune models such as 2-7B--hhh Touvron et al. [2023) and Mixtral 8x7B Diang et al. [ To better estimate the target hardware setups, we study communities dedi- cated to running large models locally, such as LaaalLlama 2023]. A populaf populafJhardwar hardware configuration for running those models locally is a desktop or a cloud instance with a single consumer-grade GP with 12-24 GB VRAM, 4-8 CPU cores, 32-64 GB RAM, and a PCIe 3.0 4.0 x16 bus between CPU and GPU. Another popular setup is devices without a dedicated GPU, such as MacBooks with an ARM- based CPU, 16 GB RAM, and an SSD. While this survey may not be fully representative, reveals popular setups that are not targeted by most speculative decoding research.
Running the largest language models in this setup requires either extreme compression or offloading. While it is possible to fit 70B+ models into consumer GPUs by compressing them to 1.5-2 bits per parameter Chee et al. [2023]. Tseng et al. [2023), doing so causes significant accuracy losses that defeat the purpose of running large models Dettmers and Zettlemoyer [2022], J, Tseng et al. [2023). Thus, practitioners with consumer-grade hardware may find it optimal to run 50B+ models with mild
(e.g. 4-bit) quantization and offload parameters from GPU to RAM or SSD Alizadeh et al. 2023
3 Preliminary analysis
Speculative decoding with offloading benefits from the fact that is more efficient to process tokens in parallel than sequentially. In conventional inference, this is caused by the higher arithmetic intensity
5 Based on popular hardware guides such as Dettmers 2023 as well as setups examples (see
B
For example, RTX 4060 or 4090 desktops. T4 or A2 VMs.
3

---

Top-k tokens
1.0
Uoverage
008 0.4
0.2
64
256
Llama-2 70B
Llama 2 13B
Llama-2 7B
TinyLllma IB
JackFrum 160M
Figure 2: L 70B Chat model cumulative probability of most likely tokens compared to the draft model choice (all Llama draft models are chat versions), OASSTI dataset.
of GPU processing" | With offloading, there is a different bottleneck - loading model parameters from storage. Since offloading engines can dispatch model parameters in parallel with computation, the total processing time is the maximum of the time to load all parameters and the total computation time. In preliminary experiments (see Figure II right), we found that 70B models running on consumer desktop can process thousands of tokens within nearly the same time as just single token.
This leads us to a question: how does speculative decoding perform when given hundreds to thousands of draft tokens? As shown in concurrent work Chen al. (2024a], speculative decoding algorithms with single or multiple sequences, like SpecInfer, are effectively upper-bounded in the number of accepted tokens the speculation budget grows. This is confirmed by our observations (see Figure T left), where the number of accepted tokens saturates even for the more powerful Llama-2 7B.
In regular GPU inference, using 7B draft models would be impractical, as the drafting steps would take too long. However, in setting, large draft models be justified because each offloaded
forward pass takes significantly more than a second (see Figure [ right). This runs contrary to a popular intuition in speculative decoding that favors smaller draft models Miao et al. 2023 Liu et al. [2023].
We also observe that sampling from modern LLMs often results in few high-probability tokens that add up nearly to probability of (see Figure 2 for an illustration). If we can find these tokens using the draft model, we construct draft that will be accepted with similarly high probability. In preliminary experiments for 70B models, we found that running beam search with a capable draft model (c.g.. Llama-2 2 7B) recover many of these high-probabilityy tokens. Unfortunately, this kind of deterministic scarch is incompatible with speculative decoding for stochastic sampling, which called for alternative validation method.
4 Method
4.1
Speculative Execution
As we observed in Section high-probability continuations of large models are concentrated in a few tokens, and offloading benefits from running target model on hundreds or thousands of tokens. To use these observations, we formulate an alternative, simpler speculative decoding strategy. Unlike speculative decoding, SpecExec (short for "Speculative Execution") does not propose procedure: runs standard (sequential) sampling while trying to "guess" which probabilities will be needed during future steps and precomputing these continuations in parallel. This is similar to speculative execution [Lampson] 2006) in modern CPUs that predicts which operations should be computed ahead of time better utilize the compute cycles.
sampling
More specifically, whenever SpecExec uses target model probabilities, looks them up a speculative "cache". If it encounters token that is not in the cache, it queries the target model for that token and simultaneously computes probabilities for B potential future tokens chosen with the draft model, where B is the batch size. If the draft model can guess the likely next tokens accurately enough, the algorithm will be able to run multiple sampling iterations using these cached probabilities without querying the target model until it "exhausts the cache" and begins anew. A formal description of SpecExec is given in Algorithm I
To choose which future tokens should be precomputed, we run search algorithm with the draft model find B most likely tokens according their cumulative probability II. P( dran)
Parallel matrix multiplications do more useful computations per memory access for multiple tokens.

---

Algorithm SPECULATIVE EXECUTION
1: Input: prompt 2, models earget. daatt output length L, budget K, max depth D, batch size
2: Output: sequence of L tokens generated by Ourget
3: cache == PRECOMPUTE(2) Aaall, Orarget; K, D, B)
target model probabilities for likely future tokens
4: for = 1.......44 ,, do
5: if E cache then
6: cache = PRECOMPUTR(2; drali, O,nge,K,,,DB K.D,B)
7: Purget cache [a]]
Purget is equal to P(: [21,--.. -......-a Ft, uugee)
8: Tnext ~ SAMPLE(Parre
9: x x + (Nnext)
append token
10: return x
12: function PRECOMPUTE(2, A pagget Gdratts K. D. B)
I CREATEDRAFTTREE(2 draatt K, D)
T is tree with K tokens up depth D i process T tokens in parallel with offloading;
14:
next_probs := FORWARD(1 T, uurget)
note: next_probs a matrix E RR x
15:
cache := 0
for r; E do
17:
prellix == x (x;,7
>> prefix in tree [r:]
cache pretix + { next_probs
probabilities of possible next tokens
19:
return cache
The details of the search algorithm given in Section 4.2 unlike drafting with regular speculative decoding, this procedure is deterministic and always selects tokens with the highest probability.
Comparison to speculative decoding. The core advantage of SpecExec over regular speculative decoding is that the algorithm does not need the draft tree to follow a known probability distribution. In other words, SpecExec produces correct samples with any draft tree, even if it is deterministic. We use this property to construct the best possible speculative tree in ways that would break the assumptions of standard speculative decoding. For instance, our tree construction procedure, outlined Section 4.2 considers only the most likely draft tokens and aims to capture a larger portion of the total probability mass.
However, this advantage comes at the cost of lower acceptance rates for any individual token. Algorithm [ accepts token I, with probability P(x++1 [oo: Ourge)) because accepting token with SpecExee equivalent to sampling that token from the target model distribution. Meanwhile, the original speculative decoding (for example, Miao et al. [2023] accepts tokens with higher probability P(z (o.., Buurget (Panee))/((z+H To:t, Odratt).
For small number of draft tokens (for instance, just one token), SpecExec is less effective than traditional speculative decoding. However, as we increase the number of draft tokens, speculative execution generates same draft size; we verify this in Section 5.2
trees, which in practice leads to accepting more tokens for the
Next, we need to verify that SxecExec is equivalent to sequential sampling from the target model. Notably, unlike Leviathan et al. 2023), SpecExec does not change the probabilistic sampling procedure. The difference between SxecExec and sequential decoding is that SpecExec precomputes some probabilities, thus improving the GPU utilization in the case of offloading.
Correctness.
From a formal perspective, we rely on the fact that speculative generation algorithm is equivalent to sequential sampling if it is locally equivalent in every node Miao et al. [2023] in other words, samples from the same probabilities for every prefix the draft tree. Since SpecExec explicitly samples from the same probabilities as the main model, this is true by construction.
The fact that SpecExec follows the same sampling procedure has another side effect. SpecExec deterministic function that depends on pseudo-random number generator as input, we can prove a stronger degree equivalence. Namely, for every seed value of the random number generator, SpecExee produces exactly the same outputs sequential sampling with the same seed. In
view
5

---

contrast, speculative decoding does not have this properly, as it only guarantees correct probabilities for the overall generation procedure.
4.2 Search for the Optimal Draft Tree
As we discussed above, our algorithm uses the draft model to build tree T of likely future tokens for speculative caching. In this section, we describe how to find these tokens efficiently. From an optimization perspective, we seek to construct tree that will lead to the highest expected number of generated (accepted) tokens. This problem can be solved by viewing the tree construction the search for the set nodes (i.e., tokens) that have the highest cumulative probability with respect to the target model. As we show in Appendix [A] this search can be reduced to the single-source shortest path (SSSP) search problem that can be solved efficiently using modified version of the Dijkstra's algorithm Dijkstra [959], described formally in Algorithm
In summary, SpecExee follows a loop:
1. Run Algorithm
2 with the draft model select K best tokens,
2. Process them with the target model using offlodiigg
3. Follow Algorithm
D to determine which tokens are accepted.
For visual high-level representation of the SpecExec algorithm, see Appendix
While Algorithm is rather special case of SSSP over a combinatorially large tree (the tree of all token sequences up length K), the general SSSP problem well studied in the computer science community (see Appendix C Therefore, practitioners will be able to leverage existing algorithms implement Speculative Execution for broad range of setups, including GPUs, mobile CPUs, or distributed systems.
Algorithm 2 PARALLEL SSSP FOR DRAFTING
1: Input: prefix Guann budget K, depth D, batch B
2: Output: tree K likely future tokens
3:
4: function CREATEDRAFTTTREEE 0amn K, D.
5: т TREF((2))
& an empty tree with root at D stopping threshold
6:
T = 00
7:
H PRIORITYQUEUE((12 0}) b has priority 0; H is ordered by negative cumulative prgaabbbaiilitie
8:
for d= 1,1, do
9:
batch
10:
for b = 1,2, .2........ do
H nll, == EXTRACTMIN(H)
12:
if nll, < T then
T:= T:=ADDCHILDT..om
nlly) batch := batch U {m)}
14:
batch = Ø then
16:
break
SIZE((T) then T == KTHCUMUIATTVELOOPPRRR K)s ignore tokens that fall outside the budget D run Oann w/o offloading. attend to past tokens; note: probs is matrix R Bx vocab
18:
19:
probs == FORWARD(batch,, Oaran)
20:
topk == SELECT probs, T, K) select best tokens by cumulative probability for P:) topk do
21:
22:
log pretix- == CUMULATIVELOGGPOHHE: EmnErter log ((ze[T((2 T, 6aan))
23:
nill = log P prefix log H = INSERT HH, nll) H = TRIM H, K)
24:
25:
D remove all except K best
return TRIM(T, K)

---

4.3 Implementation Details
Finally, we leverage several important technical improvements that speed up inference in real-world conditions. When running the forward pass with an offloaded target model, we accelerate inference by loading the next layer parameters in parallel with computing the previous layer activations using dedicated CUDA stream, which is known speed up offloading in other use cases Pudipeddi et al.) [2020). Ren et al. [2021). Aminabadi et al. (2022). We also preload the first few layers of the target model on the GPU in the background while drafting for a further speedup. We describe additional implementation details in Appendix D
In our experiments, we also consider quantizing target models using recent post- post-training quantization algorithms Frantar et al.] [2022], Lin et al.] [2023], Dettmers et al.] [2023]. While quantization is generally popular among LLM practitioners, is particularly useful for our use case, quantized
models take less time to load from RAM to GPU and have RAM offloading requirements attainable
by consumer hardware.
5
Experiments
5.1 Probability Coverage
The core assumption behind Algorithm | is that reasonably large draft can "cover" most of the hugh-probability sequences of the target model. This is only possible if the target model predictions have low entropy (i.e., there a small number of tokens with high probability) and the draft model can guess these tokens most of the time.
To test these assumptions in isolation, we measure the total probability mass "covered" by l most likely tokens, as well as the probability of top-k tokens guessed by draft models of varying size. If a certain draft model achieves a coverage probability p for tokens, this means that taking the most likely tokens predicted by the draft model and measuring their probabilities with the main model (Llama-2-Chat 70B) would result in an average cumulative probability equal p. We evaluated multiple draft models of various size: JackFram 1 160M Miao et al. [2023), TinyLlama-1, 1.1. BB-Chat v1.0 Zhang et al. (024b)) Llama-2-Chat 7B and 13B tou We report these coverage probabilities on a sample of 512 Assisaatttnnt conversations Köpf et al. 2023). For each conversation, we generate 64 additional tokens by sampling from the target 70B model probabilities. We sample these tokens using original probabilities (without temperature or top-p sampling) and use the same tokens for every draft model.
The resulting coverage is reported in Figure 2 This leads to several important observations. First, the target model (Llama-2 Chat 70B) tends have sharp probability distributions, where the top 1-4 tokens cover 90-98% of the entire probability mass. This agrees with existing observations that language models (esp. the larger ones) are overconfident Miao et al. 2021]_ Chen et al. [2023b].
Next, we compare how effective the draft models are at predicting these While all models eventually get 90% coverage rate, Llama-2 Chat 7B makes much more accurate predictions with the first 1 1-4 tokens. This is important for our use case because, while the full draft tree contains thousands of tokens, individual tokens within that tree have much fewer children. Curiously, the 13B draft model demonstrates roughly the same accuracy as 7B despite its larger size.
tokens.
Though we evaluate coverage for "raw" probabilities from the 70B model, many practical inference scenarios use temperature or nucleus sampling Holtzman et al. (2020). In fact, thedefault generation parameters for Llama-2 70B use both temperature of 0.6 and top-0.9 nucleus sampling CamplingFFacee [2024] Generating in this way makes the model even more confident, which further improves the efficiency of parallel decoding.
5.2 Draft Acceptance Rates
Next, we study how Speculative Execution compares to existing speculative decoding variants for different token budgets. Since all algorithms guarantee that the tokens are sampled from P(a++1 [ m we compare them their ability to generate longest sequences of accepted tokens given the same budget of draft tokens.
7

---

(a) MTBench dataset, 1-0.6, top_ p-9
(b) MTBench dataset, t-0
SpecExee Speclnfer
SpecEixec SpecInfer
A Genorattd tokens
20
20
16
16
8
16
32
64
128
256
512
1024 2048 4096
8
16
32
64
128
256
512
1024 2048 4096
Draft model output size in tokens
Draft model output size in tokens
Figure Generation rate depending on the draft budget size for Llama 2-7B
Chat as the draft model and Llama 2-70B Chat the target model, MTBench Zheng al. 2023 dataset. Results obtained with an A100 GPU.
Since we are interested in very large budgets, we choose baseline algorithms that better fit this task. The original speculative decoding algorithm Leviathan al. [2023] generates single sequence, which is truncated as soon as the algorithm rejects a single token. In other words, using a single long draft sequence results in most of the draft budget being wasted. Therefore,
baseline, we choose the SpecInfer algorithm that shares the large token budget across multiple stems in a tree.
Similarly to the previous section, The draft model choice was driven both by the speed and the acceptance rate factors: we found that using draft models with 7B parameters results in significantly forward pass time is still affordable in the offloading setting. We report the effects of these draft models in more detail in Appendix
70B versions of Llama 2 and Llama 2-Chat as target models.
accepted tokens, and longer
In each setup, we compared SpecExec and SpecInfer, using the draft model, chosen based on our findings from Section 5.1] reppors the average number of accepted tokens both for the default sampling configuration (temperature 0.6, top-p 0.9) and for greedy sampling for Llama 2-70B Chat model using the MTBench dataset. Similar tests were run for non-chat models on the C4 dataset; see Figure for results.
(a) C4 dataset, 0.6, top_p-0.9
(b) C4 dataset, L-0
24
24
SpecTixec
SpecExec
Gemerrled tokens
20
Specinfer
Specinfer
16
16
12
12
2048
4096
Draft model ourpot in tokens
Draft model output tokens
Figure 4: Generation rate depending on the draft budget size for Llama 2-7B Chat the draft model and Llama 2-70B Chat as the target model, C4 dataset. Results are obtained with an A100 GPU.
For smaller draft budgets, SpecExee performs on par with SpecInfer, but eventually outscales as we increase the number of draft tokens. We attribute this not to the general verification algorithm, but to the fact that SpecExec constructs its draft out of most likely tokens, while SpecInfer must sample draft tokens guarantee correctness. We also observe that Speculative Execution achieves higher margin of improvement on MT'Benc samples than on C4. also accepts more tokens with a lower temperature. We attribute this to sharper token probability distributions, leading higher coverage rates for the same number of draft tokens.
5.3 Inference Speed
Finally, evaluate the practical inference speed of SpecExec by running with offloading in different hardware configurations. We run these evaluations for Llama 2-70B tou models, both in regular and chat (instruction -unndntunndeeee versions. For prompts, we used subsamples of size 100 from OpenAssistant conversations Köpf et al. [003)]. WikiText- [ et al. [2016). MTBench Zheng
al. 2023 and C4 Raffel et al. 2020]. measuring the speed of generating 32+ tokens per prompt. For Llama 2, we tested two setups: running the main model in 16 bits quantizing it to 4 bits using
GPTQ Frantar al. 2022]. We also tested Mixtral 8x7B Jiang et al. (024 (also quantized with
GPTQ) and Llama 3 Al 2024 target models in fewer setups.

---

Table Inference speed with RAM offloadingg A GPU, Chat Instruct models, using SxecExec (SX) and SpecInfer (SI) methods. Generation rate ("Gen. rate") denotes the average number of draft model tokens accepted one target model iteration.
Draft Target models
Dataset
Method Budget
Gen. rate Speed, tok/s Speedup
0.6
SX
2048
20.60
3.12
18.7x
0.6
SI
1024
8.41
1.34
8.0x
Llama 2-7B / 70B
OAsst
0
SX
1024
18.8
2.74
16.4x
0
SI
1024
7.86
1.18
7.1x
0.6
SX
128
12.10
6.02
8.9x
Llama 2-7B / 70B GPTQ
OAsst
0
SX
256
13.43
6.17
9.1x
Mistral-7B / Mixtral-8x7B
0.6
SX
256
12.38
3.58
3.5x
OAsst
Llama 3-8B 70B
0.6
SX
1024
18.88
2.62
15.6x
0.6
SX
1024
18.16
2.79
16.6x
Llama 3-8B 70B
MTBench
SX
2048
21.58
2.94
17.5x
We measure the inference speed with multiple GPU types: A100 (data-center GPU), RTX 4090 (current generation high-end consumer GPU), RTX 3090 (previous generation consumer GPU), and RTX 2080Ti (older consumer GPU). The first three GPUs are connected the host via PCTe Gen x16, while 3090 and 2080Ti were tested with PCIe Gen 3 x16. Note that for A 100, we report the forward pass time with offloading, even though the GPU can fit a quantized model in its memory. We run all experiments with batch size of to match the setup of running L.MSs on local machine.
The average inference speed (measured in tokens per second) for A100 GPUs reported in Tables | and 2 While the exact inference speed differs from setup to setup, Speculative Execution consistently speeds up generation with offloading by several times. These results compare favorably with recently published speculative decoding methods using fixed trees like Sequoia Chen et al. (2024b). which attains 2.2 tokens per second the Llama 3-8B/70B setup, compared 2.8 tokens per second in case of SpecExec.
In Table 3 report the results of similar experiments for range of real-world consumer GPUs. To reduce the memory requirements for the consumer setup, we replaced a 16-bit Llama-2 70B model with 4-bit GPTQ compressed variant requirements for 2080 Ti, we used Sheared-Llama-1 .3B Xia et al. [2024b] as a draft model, making the whole experiment consume just over 7 GB of VRAM. Note that while the fastest inference time is achieved on RTX 4090, slower consumer GPUs (for example, RTX 2080Ti) still generate tokens quickly enough for interactive use.
1lama-2-70BB the target model. To lower the VRAM
Table 2: Inference speed with RAM offloading. A100 GPU, base models, using SpecExec (SX) and SpecInfer (SI). Generation rate ("Gen. rate") denotes the average number of draft model tokens accepted for one target model iteration.
Draft Target models
Dataset
Method Budget Gen. rate
Speed, tok/s Speedup
0,6
SX
2048
12.9
1.97
11.8x
0.6
SI
1024
6.48
1.03
6.2x
Llama 2-7B/ 70B
C4
0
SX
2048
16.1
2.38
14.3x
0
SI
1024
4.78
0.75
4.5x
0.6
SX
2048
9.57
1.54
9.2x
0.6
SI
1024
4.69
0.77
4.6x
Llama 2-7B / 70B
WikiText-2
0
SX
2048
11.74
1.88
11.3x
0
SI
1024
3.71
0.62
3.6x
0.6
SX
256
6.99
3.72
5.5x
Llama 2-7B 70B GPTQ
WikiText-2
0
SX
256
8.81
4.54
6.7x
Mistral-7B Mixtral-8x7B
WikiText-2
0.6
SX
128
6.56
3.23
3.2x

---

Table SpecExec inference speed on consumer GPUs with offloading, chat/instruct models, Llama 2 70B-GPTQ target model, t 0.6, OpenAssistant dataset.
GPU
Draft model
Budget
Gen. rate Speed, tok/s Speedup
RTX 4090
256
13.46
5.66
8.3x
RTX 4060
Llama 2-7B
128
9.70
3,28
4.6x
RTX 3090
256
14.3
3.68
10.6x
RTX 2080Ti
ShearedLlama- 1.3B
128
7.34
1.86
6.
We also explore the relationship between the inference speed and the draft tree size. A larger draft budget allows for a greater number tokens to generated per step (see Figure F (left)) However, the model and GPU),
beyond certain size threshold (hundreds thousands of tokens, depending the time required for generation increases at an accelerating rate (see Figure ( (right)). Consequently, the optimal draft tree size is typically smaller than the size that maximizes the token acceptance rate. According to our findings, displayed in Figure (right), the optimal draft tree size is 128-512 for SpecInfer and 024-2048 for SpecExec for the A100 GPU.
GGenerated tokemsssep
24
Speclixec
Speclixee
20
SpecInfer
Speed tokeruiss
Specliffer
2.0
16
12
1.0
8-
0.0
8
16
1024 2048 Draft model output size tokens
32
64
128
256
512
4096
16
32
64
128
256
512
1024 2048 4096
Draft model output size in tokens
Figure 5: Acceptance counts (left) and generation speed (right) depending on the draft size. Llama 2-7B used the draft model, offloaded Llama 2-70B is the target model, MTBench dataset, t=0.6 and top-p=0.9. Results are obtained with an A100 GPU.
While this was not the primary focus area of our study, the SpecExec method can also deliver competitive speedups in inference without offloading; see Appendix for sample results. Additional tests SpecExee in generation with penalties show that the method robust with such conditions: Appendix H provides the results of such evaluation.
6 Conclusion and Future Work
In this work, we propose a method for fast inference of large models on consumer GPUs that unites the efficiency of offloading and speculative decoding in the large-budget setup. The resulting method, SpecExec, shows competitive performance real-world experimental setups, demonstrating the possibility of running large models locally at the speed of interactive inference.
Although we developed an offloading system to utilize SpecExec in practical settings, the goal of study was not create the fastest possible implementation of local LLM inference. Achieving that goal relies on combining our approach with orthogonal performance improvements proposed in prior work, which is beyond the scope of this paper. Importantly, given the recent trends in hardware accelerators for deep learning, inference of large models may become increasingly more constrained by the memory bandwidth even for the fastest devices. Therefore, optimizing generation time with bandwidth constraints in mind is likely to grow more important the future, and our work demonstrates novel approach to that problem.
10

---

References
Meta AL. Introducing meta llama 3: The most capable openly available Ilm to date. https:
7/ai .eta. mneta.com/blle -aaeettalllaa-----a 37| 2024.
Joshua Ainslie, James Teerph Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. GQA: Training generalized multi-query transformer models from multi-head checkpoints. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages
Singapore, December 2023, Association for Computational Linguistics. doi: 10. 10.18653/v http5/3//1/223..mmmm.. mainlp..iin.298. URL https://cclanthology org
emnlp-main. 298
Keivan Alizadeh, Iman Mirzadch, Dmitry Belenko, Karen Khatamifard, Minsik Cho, Carlo C
Del Mundo, Mohammad Rastegari, and Mehrdad Farajtabar. Llm in flash: Efficient large language model inference with limited memory. arXiv preprint arXiv:2312.11514, 2023.
Reza Yazdani Aminabadi, Samyam Rajbhandari, Ammar Ahmad Awan, Cheng Li, Du Li. Elton Zheng, Olatunji Ruwase, Shaden Smith, Minjia Zhang, Jeff Rasley, and Yuxiong He. Deepspeed- inference: Enabling efficient inference of transformer models at unprecedented scale. In Proceed- ings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC '22. IEEE Press, 2022. ISBN 9784665454445.
Scott Beamer, Krste Asanović, and David Patterson. The gap benchmark suite. arXiv preprint arXiv:1508.036799 2015. 2015.
Maciej Besta, Michat Podstawski, Linus Groner, Edgar Solomonik, and Torsten Hoefler: To push or to pull: On reducing communication and synchronization graph computations. In Proceedings of the 26th International Symposium High--eeffrmance Parallel and Distributed Computing, pages 93-104, 2017.
Guy E Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan. Parallel shortest paths using ra- dius stepping. In Proceedings of the 28th ACM Symposium on Parallelism Algorithms and Architectures, pages 443 454, 2016.
Nicolas Bbulanger-Lowandowskii Yoshua Bengio, and Pascal Vincent. Audio chord recognition with recurrent neural networks. In ISMIR, pages 335-340. Curitiba, 2013.
Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, and Tri Dao. Medusa: Simple framework for accelerating Ilm generation with multiple decoding heads. Accessed: 2023-09-08, 2023.
Jerry Chee, Yaohui Cai, Volodymyr Kuleshov, and Christopher De Sa. Quip: 2-bit quantization of large language models with guarantees, 2023.
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling, arXiv preprint arXiv:2302.01318, 2023a.
Yangyi Chen, Lifan Yuan, Ganqu Cui, Zhiyuan Liu, and Heng Ji. A close look into the calibration of pre-trained language models. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 6lst Annual Meeting of the Association for Computational Linguistics (Volume
1: Long Papers), pages 1343-1367, Toronto, Canada, July 2023b. Association for Computational Linguistics. doi: 10. 10.18653/v1/20// acl-
URL https http::::/aaclaathooogggg 2rw.aaanthoooooyooo/2222222
acl acl-long.75
Zhuoming Chen, Avner May, Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and
Beidi Chen. Sequoia: Scalable, robust, and hardware-aware speculative decoding, 2024a.
Zhuoming Chen, Avner May, Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and Beidi Chen. Sequoia: Sequoia: Serving exact llama2-70b on rtx4090 with half-second per token latency, 2024b. https::ts// lab. github. Lttp///euuiaaaaapaeee Accessed: 2024-05-21.

---

Edith Cohen. Using selective path- auth-doubling for parallel shortest-pate path computations. In [1993] The 2nd Israel Symposium on Theory and Computing Systems, pages 78-87. IEEE. 1993.
Edith Cohen. Polylog-time -iie and near- linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 47(1):132-166, 2000.
Andrew Davidson, Sean Baxter, Michael Garland, and John D. Owens. Work-efficient parallel gpu methods for single-source shortest paths. 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pages 449,,59, 2014. doi: (0.1109/IPDPS.200 2011.445.
Tim Dettmers. Which gpu(s) to get for deep learning: My experience and advice for using gpus in deep learning, 2023. URL stttps://timdettmerrs com/2023/01/30/ Accessed: 2024-002-2.
which- wtw--guuooo----e-ee---l---
Tim Dettmers and Luke Zettlemoyer. The case for 4-bit precision: k-bit inference scaling laws. arXiv
preprint arXiv:2212.099720 2022.
Tim Dettmers, Ruslan Svirschevski, Vage Egiazarian, Denis Kuznedelev, Elias Frantar, Saleh Ashk-
boos, Alexander Borzunov, Torsten Hoefler, and Dan Alistarh. Spqr: A sparse-quantized represen- tation for near-lossless IIm weight compression. arXiv preprint arXiv:2306.0300 2023.
Laxman Dhulipala, Guy Blelloch, and Julian Shun. Julienne: A framework for parallel graph algorithms using work-efficient bucketing. In Proceedings of the 29th ACM Symposium on Parallelism Algorithms and Architectures, pages 293-304, 2017.
Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 269-271, 1959. URI. htttps://apl htt.r/eeaaaaaainiiiaeieeeae wwaplllr..rrr//oo www.Corrggr............. 123284777
Hugging Face.
Meta lamaa 2-70b chat generation config at hf co/ co/meta-1 1lama/ 2024. URL hf. ho/
Ll ama 70bb chat-
jssnn
meta- 10mm:m//00mm222777-----0-a-11110
conf ig. json
Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Gptq: Accurate post-training quantization for generative pre-trained transformers. arXiv preprint arXiv:2210. 1222100.7332 17233, 2022.
Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. Break the sequential dependency of Ilm inference using lookahead decoding. Accessed: 2023-11-29 2023.
Alex Graves. Sequence transduction with recurrent neural networks. arXiv preprint arXiv: 1211::121131111 2012.
Yan Gu, Julian Shun, Yihan Sun, and Guy E Blelloch. top-down parallel semisort. Proceedings of the 27th ACM symposium Parallelism in Algorithms and Architectures, pages 24-34, 2015.
Pawan Harish and Petter J Narayanan. Accelerating large graph algorithms on the gpu using cuda. In International conference on high-performance computing, pages 197-208. Springer, 2007.
Zhenyu He, Zexuan Zhong, Tianle Cai, Jason Lee, and Di He. Rest: Retrieval- based speculative decoding. arXiv preprin! arXiv:231 0et::2331..0822.0 1.08252, 2023.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL https
//openreview. //openneeiee.nee//foorm// Fdr.forrmumidyyyyyyyyyyyy
John lacono, Ben Karsin, and Nodari Sitchinava. A parallel priority queue with fast updates for GPU architectures. CoRR, abs/1 91199998.99999 09078,9777888 2019. URL http:://rxxxxi. http://aaxvvvor./////// 1900/ 09378
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023.
Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. 2024.
Mixtral of experts. arXiv preprint
12

---

Philip N Klein and Sairam Subramanian. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms, 25(2):205-220) 1997.
Andreas Köpf, Yannic Kilcher, Dimitri von Rütte, Sotiris Anagnostidis, Zhi-Rui Tam, Keith Stevens, Abdullah Barhoum, Nguyen Minh Duc, Oliver Stanley, Richard Nagyfi, Shahul ES, Sameer Suri, David Glushkov, Arnav Dantuluri, Andrew Maguire, Christoph Schuhmann, Huu Nguyen, and Alexander Mattick. Openassistant conversations democratizing large language model alignment, 2023.
Butler Lampson. Lazy and speculative execution in computer systems. In Mariam Momenzadeh Alexander A. Shvartsman, editor, Principles of Distributed Systems, pages 1-2, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-49991- 1-6.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. 2023.
Lin, Jiaming Tang. Haotian Tang, Shang Yang, Xingyu Dang, and Song Han. Awq: Activation- aware weight quantization for Ilm compression and acceleration. arXiv preprint arXiv:3306.00978 2023.
Xiaoxuan Liu, Lanxiang Hu, Peter Bailis, Ion Stoica, Zhijie Deng, Alvin Cheung, and Hao Zhang. Online speculative decoding, arXiv preprint arXiv:2310.07177 2023.
LocaILlama. Localllaaa, 2023. URL http:::/wwwwww.dddt.m.m wtt.ddtt.coo///LoaalLMMAAA 2023-12-28.
Accessed:
Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the ACM ACM SIGMOD International Conference Management of data, pages 135-146, 2010.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint 1609,0784 2016.
Ulrich Meyer. Heaps better than buckets: parallel shortest paths on unbalanced graphs. In European Conference on Parallel Processing, pages 343-351. Springer, 2001.
Mengqi Miao, Fandong Meng, Yijin Liu, Xiao-Hua Zhou, and Jie Zhou. Prevent the language model from being overconfident in neural machine translation. arXiv preprint arXiv:2105. 1098, 2021.
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 IIm serving with speculative inference and token tree verification. arXiv preprint arXiv:2305.09781, 2023.
Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A lightweight infrastructure for graph analytics. In Proceedings of the twenty-fourth ACM symposium operating systems principles, pages 456-471, 2013.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high- tighhpeeformance deep learning library. In Conference on Neural Information Processing Systems (NeurIPS). 2019.
Bharadwaj Pudipeddi, Maral Mesmakhosroshahi, Jinwen Xi, and Sujeeth Bharadwaj. Training large neural networks with constant memory using a new execution algorithm. CoRR, 05s/2402..06645.
2020. URL htt/://ttt////atatee
org/ abs aabs/2022. 20020006644
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140): 1-67, 2020.
Jie Ren, Samyam Rajbhandari, Reza Yazdani Aminabadi, Olatunji Ruwase, Shuangyan Yang. Minjia Zhang, Dong Li, and Yuxiong He. Zero-offload: Democratizing billion-scale model training. CoRR, abs/2 101.100400..... 2021. URL // //tp///rxvvvv//////////ee/aaaav/ org//or.///......o.o
13

---

Ying Sheng, Lianmin Zheng, Binhang Yuan, Zhuohan Li, Max Ryabinin, Beidi Chen, Percy Liang, Christopher Ré, Ion Stoica, and Ce Zhang. Flexgen: High- throughput generative inference of large language models with single gpu. In International Conference on Machine Learning, pages 31094-31116, PMLR, 2023.
Hanmao Shi and Thomas H Spencer. Time-work tradeoffs of the single-source shortest paths problem. Journal of algorithms, 30(1):19-32, 1999.
Benjamin Spector and Chris Re. Accelerating Ilm inference with staged speculative decoding. arXiv preprint 0tt.::22308.0622223 2023.
Thomas Spencer. Time-work tradeoff's for parallel algorithms. Journal of the ACM (JACM), 44(5): 742-778, 1997.
Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autore- gressive models. Advances in Neural Information Processing Systems, 31, 2018.
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.1514) 2023.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
Hugo Touvron, Thibaut Lavril, Gautier Izacard. Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023. URL https://arxxi wwtreivvv.rrr/ee abs 2302. 2392.
Albert Tseng, Jerry Chee, Qingyao Sun, Volodymyr Kuleshov, and Christopher De Sa. Quip#: Quip with lattice codebooks, 2023. Accessed: 2024-01-22.
Jeffery Ullman and Mihalis Yannakakis. biobb-broaability parallel transitive closure algorithms. In Proceedings of the second annual ACM symposium Parallel algorithms and architectures, pages 200-209, 1990.
Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D Owens. Gunrock: high-performance graph processing library on the gpu. In Proceedings of the s ACM SIGPLAN symposium principles and practice of parallel programming, pages 1-12, 2016.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's 's transformers: State-of the-art art natural language processing. arXiv preprint 1910:31910 2019.
Heming Xia, Zhe Yang. Qingxiu Dong, Peiyi Wang, Yongqi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui. Unlocking efficiency large language model inference: A comprehensive survey of speculative decoding, 2024a. URL https: / arxiv. org/ brg//bs//// aas///bb/224111 22011200001111
Mengzhou Xia, Tianyu Gao, Zhiyuan Zeng, and Danqi Chen. Sheared llama: Accelerating language model pre-training via structured pruning, 2024b.
Daliang Xu, Wangsong Yin, Xin Jin, Ying Zhang, Shiyun Wei, Mengwei Xu, and Xuanzhe Liu. Llm- cad: Fast and scalable on-device large language model inference, arXiv preprint MXXi:23009.02255, 2023.
Chen Zhang, Zhuorui Liu, and Dawei Song. Beyond the speculative game: A survey of speculative execution in large language models, 2024a. URL httptt:/s///arat
abs////////2/0 14897
Jun Zhang, Jue Wang. Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mehrotra. Draft & verify: Lossless large language model acceleration via self-speculative decoding. arXiv preprins arXiv:2309. 0..30090.......... 2023.
Peiyuan Zhang, Guangtao Zeng, Tianduo Wang, and Wei Lu. Tinyllama: open-source small language model, 2024b.
14

---

Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, and Julian Shun. Optimizing ordered graph algorithms with graphit. Proceedings of the 18th ACM/IEEF International Symposium on Code Generation and Optimization, pages 158 158-170, 2020.
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 lon Stoica. Judging lmm-as-a-judge with mt-bench and chatbot arena, 2023.
Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. Gemini: A {Computation- Centric} distributed graph processing system. In /2th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 301-316, 2016.
15

---

A Equivalence of Optimal Tree Search to Shortest Path Search
We can formulate this problem as follows:
Σ (riTc)(DilTT Paccepi (1t (T).
arg max TET
RIET
Here, Z; T refers to a token within the draft tree, T is a set of all trees of K tokens and reach (2x/7) is the probability that the Speculative Execution verification phase accepts the full prefix xo, ................................ - along the draft tree and considers sampling Y; next. Finally, Eaccupp<2,17 is the probability that the token I; will be accepted if it is reached during verification. Both Preach and Paceept depend on the target model probabilities P( (( flrgges), which cannot be accessed the drafting phase. Instead, we use the draft model to approximate the target model probabilities follows:
Preach (0:ch(22//)) (T)
II
P(21/T(Z) r), dran)
(xclT))( R ((x: (x;,)) r), Odmn)
where ((:;,7) r) is the path in from root to I;, excluding H; itself. From the LLM perspective, (2 r) is the prefix for token v, within the draft tree. If we multiply the two expressions as per Equation we get the cumulative probability of sequence π (22,, T) @ 24, where + is concatenation.
arg max TET
Σ 2CET
II (
P(zelT(I r), O
Since token probabilities cannot be greater than the cumulative probability of (r; r) m; cannot exceed the cumulative probability of all tokens in (x; r). Therefore, if a token z; is among the K most likely tokens, every token in <(x;, 7) is also part of the solution. Using this property, simplify Equation aas finding top-K most likely prefixes, since they are guaranteed to form a tree. Formally speaking, the optimal tree consists of K tokens with the highest cumulative probability:
can
arg top K
II 24 (.E,
(( T), Oaran)
This is similar (but not equivalent) to the standard beam search algorithm for neural sequence models Graves [2012). gowulanger-Lwwaddwwwy
et al. (2013). Sutskever et al. [2014]. The main difference that beam search looks for complete sequences, while we need a tree of partial drafts. However, using beam search instead of solving Equation 3 directly leads to suboptimal drafts (see Appendix F for details).
Instead, we solve Equation 4 by reformulating it as special case of the shortest path search problem. More specifically,
arg max z;
II
(T T), Aaratt)
arg max
Σ
log ((re|T((2,)) r), Oraa)) =
(5)
Te En (a Doa,
arg min
Σ
log P (Z (T), Oaran).
(Z
Note that every term in that sum is non-negative, (since log P(x (Z makes this equivalent to single-souree shortest path (SSSP) problem for finding paths to K nearest nodes in a graph with non-negative edge weights. Normally, this problem can be solved by running the Dijkstra algorithm for K steps. However, in practice, running the algorithm for K sequential steps inefficient on modern highly parallel hardware, especially in our setting with very large drafts. To alleviate this problem, we use modified parallel Dijkstra algorithm, which expands B > nodes on every iteration and keeps track of K nearest nodes in a priority queue. We describe this formally in Algorithm? 2
|( 7), Oaran) 2 0), which
16

---

In the worst case, this algorithm still makes up to K steps if the solution to Equation B a single "stem" tokens long. However, the actual number steps sigmificantly lower, often slightly above the lower bound [B/ B/ In the practical GPU implementation, we also limit the maximum depth with parameter D. The purpose of to limit the edge case where the draft model very confident about the next token, and thus the solution to Equation B single sequence of length K. For this edge case, Algorithm 2 will take long to generate a sequential draft, most of which will later be discarded if the draft model makes even one mistake.
B SpecExec Algorithm Diagram
Figure displays a block diagram that outlines the key steps of the SpecExec algorithm.
Start generation
Build tree with draft and target probabilities prefill cache
Try sampling token from cache
Yes
Token sampling
No
successful?
Save token in output sequence
No
Yes
Stop condition met?
Return output sequence
Figure 6: A high-level overview of the SpecExec algorithm.
C Parallel Graph Search
There dozens of works that study practical implementations of parallel shortest path search and SSSP in particular. One line of work proposes inexact search algorithms that use an approximate priority queue improve the performance of SSSP: Nguyen al. [2013) proposes a queue with an integer metric, and Zhang et al. [020)] adds bucket fusion to reduce the synchronization overhead..
A significant effort was dedicated to efficient shortest-path search GPUs, among others. Harish
and Narayanan (2007) proposes a GPU-efficient SSSP that outperforms sequential CPU computations. Davidson et al. [2014], |Wang et al. (2066) compare several SSSP variants for GPUs. Iacono et al. [2019] adapts priority queues to run efficiently on GPU and uses the resulting data structure to accelerate SSSP.
Many works on parallel graph search focus on the distributed setting Malewicz al. 2010 Zhu al. 2016), Besta et al. [2017), addressing communication and synchronization overheads. Finally,
17

---

a large body of work studies the theoretical properties of parallel SSSP, including Ullman and
Yannakakis 1990). Klein and Subramanian [197]] Cohen [993]. SSh and Spencer [999 Cohen
2000 [Spencer 1997]. Meyer (2001) Blelloch et al. 2016
D Additional Implementation Details
Our system design follows the following loop:
1. Load the draft model onto GPU memory and generate draft tree;
2. Load the main model (several layers time, if using offloading) compute probabilities for the draft tree tokens;
3. Choose the accepted tokens following the verification procedure.
When running the main model, we process all draft tokens in parallel by constructing merged attention mask, similar to Miao et al. (2023). We prefetch the first few layers the main model during speculation to speed up the procedure. We also load subsequent LLM layers in parallel, while the previous layers compute their activations, as described in (uudipeddi et al. 2020]. Aminabadi et al. 2022].
Finally, we keep the past key/value caches of both draft and main models in GPU memory at all times. We chose this because most modern language models use grouped-query attention (Ainsiee jet al. 2023], making caches relatively small for short prompts. When dealing with longer prompts or smaller GPU memory, one can reduce memory usage by offloading these KV caches into RAM. The draft model caches are only needed on GPU during the first stage when generating the draft tokens. In turn, the main model caches can be loaded alongside their transformer layers.
The optimal implementation of this algorithm is slightly different depending on the hardware configu- ration. Rumning SpecExec on system with GPU with RAM offloading works best with relatively fewer draft tokens, while longer offloading (to SSD or when using float16 precision weights) works best with larger token budgets.
As for the quantization scheme, while there are better quantization algorithms Lin et al. 20233 Dettmers et al.] (023), Chee et al. 2023), we chose GPTQ since it is popular among practitioners. Still, we believe that our experimental results will generalize other quantization algorithms. In addition to the main model, we also quantize the draft (7B) model using the same GPTQ algorithm. The optimal choices of the quantization methods will vary as new methods or faster implementations appear.
The experiments
mainly performed using A100 GPUs (unless specified otherwise), but may be easily reproduced using other GPUs Note that while A100 has 80GB VRAM, we did not keep any layers in VRAM in order to keep the VRAM use to minimum and emulate performance of GPUs like RTX4090 or L40. A S a result, the observed VRAM use requirements with offloading was in 12-22 GB range for experiments with draft trees up to 2048 tokens when using Llama-2-70B RAM offloading. Naturally, keeping some of the layers constantly in VRAM would increase both baseline and the model performance.
The offloading experiments require sufficient RAM to hold whole model. In case of -lama-2-70B in 16 bit, this is at least 140 GB, but in practice 192 GB would be recommended to fit the draft model, caches and memory of other processes. Our code is based on industry standard Py PyTochh Paszke et al. (2019) and Transformers Wolf et al. (2099 libraries.
E Ablation: Acceptance with Different Draft Models
we evaluate SpecExec and SpecInfer with 7B draft models based on the observations about their coverage probabilities. Here, we further compare these models in terms of the number of accepted tokens for different SpecExec batch sizes. We report the results of this comparison in F using the same OpenAssistant dataset as the main experiments using the recommended temperature (0.6) and nucleus size (0.9). Similarly to F the 7B model significantly outperforms both JackFram/llant htt./llaaaa-1i -10mm and TinyL.ama I.IB Chat. This is true both for the original 7B model and the one quantized to 4 bits with GPTQ Curiously, the full unquantized 13B model still obtains
In Section 5.2
18

---

slightly more accepted tokens, though at the cost of 26GB memory footprint that is inaccessible to modern consumer GPUs.
24
Llama 2 13b chat
# #cceptedd tokens tolens
20
Llama 7h
TinyLlama L.IB Chat
16
JackFram/llama-
12
16
32
64
128
256
512
1024
2048
4096
Draft model output size in tokens
Figure 7: Number of accepted tokens as function of the draft size B for the Llama 2-70B Chat target model and different draft models.
F
On The Suboptimality of Beam Search
In our preliminary experiments, we tried construct the optimal draft tree using top-k beam search decoding Graves 2012). However, we observed that the algorithm performed significantly worse than expected and often plateaued as we increased the maximum beam search length. Here, we describe the analysis of this problem that eventually led us to Algorithm
2.5
2.8
2.8
2.9
2.6
2.8
2.9
3.0
3.8
4.3
4.5
4.5
4.5
4.5
4.5
3.6
4.2
4.5
4.5
4.6
4.6
4.8
beam Jength
besm, Jangth
3.7
4.8
5.2
5.8
5.8
6.0
6.0
4.4
5.0
6.1
5.8
6.2
6.2
6.3
5.1
6.3
6.0
6.8
6.7
7.3
7.2
5.2
5.9
6.5
6.6
7.0
7.7
7.9
5.5
6.1
8.1
8.1
9.1
9.9
9.1
36
6.1
7.1
8.1
9.0
9.4
11.6
11.2
4.3
5.4
7.3
6.5
8.0
10.5
13.2
2
128
r_beams
Figure The average number of accepted tokens per speculation and verification phases as function of beam size and maximum length. The measurements are obtained Assnsssit conversations (Left and WikiText-2 articles (Right) for running with recommended generation parameters (temperature 0.6, top-p 0.9). (Left) standard beam search decoding, (Right) beam search without pruning out-of-beam tokens.
Figure g (left) reports grid where each cell is the number of accepted tokens for a version of SpecExec that uses beam search instead of parallel SSSP. The horizontal grid axis corresponds to beam size (also known as the number of beams), and the vertical axis depicts maximum length within a beam. The left grid shows standard beam search decoding that returns beam size most likely sequences. turn, right grid uses modified search algorithm that starts the same way as beam search but does not prune any partial hypotheses that did not make it into the final beam.
As can see, standard beam search decoding is suboptimal for SpecExec the sense that outperformed with trivial modifications. In turn, Algorithm is a generalization of the version on the right that does not need be manually tuned for length and width, but instead expands the graph optimally to maximize the coverage probability.
be
G Application to in-memory inference
While this was not the primary focus area of our research, the SpecExec method can also deliver measurable speedups in inference without offloading. While these speedups are less impressive than those for offload settings, they are still competitive when compared to recent works such as Chen al. 2224aa]
19

---

Table 4: SpecExec Inference speed without offloading, A100 GPU.
Draft Target models
Dataset
Method
Budget
Gen. rate
Speed, tok/s Speedup
OASST-1
0.6
SX
128
5.33
31.6
2.15x
OASST-1
0
SX
128
5,4
32.94
2.24x
C4
0.6
SX
128
5.1
33.3
2.26x
SL-1.3B/ Vicuna-33B
C4
0
SX
128
5.36
35.62
2.42x
WikiText-2
0.6
SX
128
4.87
30.19
1.90x
WikiText-2
0
SX
128
5.24
33.15
2.08x
H Drafting penalty effects
To verify the method's robustness, we ran series of experiments with penalties excluding the use of specific tokens. The same penalty scheme was applied to both draft and target models, and the expectation is that the models should be able to run SpecExec effectively. To verify this claim, we a series of experiments with penalties excluding use of fewer or more tokens. For these experiments, penalized all tokens that start from the letter "r" (left) all tokens that contain the letter "r" (right), Here we used the Llama 2-7B Chat target model with TinyLlama- Chat draft model, t=0.6, p=0.9, MT-Bench dataset.
The results these experiments can be found in Figure We found that our method's performance (measured in terms of accepted tokens per iteration) stays stable only with lightweight penalties, yet heavier penalties reduce the absolute speedups. Looking at the generated samples, we observed that while with lighter penalties, the model is able to work around the restrictions and generate reasonable text, with heavier penalties the quality deteriorated as the model skipped or replaced tokens seemingly at random. Stronger penalties affect the quality of the generated text and naturally make the task harder for the draft model. Thus, we attribute the lower performance with a heavy penalty to this perplexity increase rather than the penalty directly.
not not starting from "
not using letter
SpecExec
SpecExer
10
Specinfer
10
SpecInfer
tokens per step
6
tokens
2-
2-
128 tree size budget
1024 2048 4096
256 tree size budget
2048 4096
Figure 9: Acceptance rate in generation with token penalty: "don't 't start words with "R" (left) and "don't it the letter "R"" (right); Llama 2 7B Chat (+ IamaI.lma- Chat draft) model (t=0.6, p=0.9), MTT-Bench dataset. The rest the experimental configuration is the same as in Figure 1.
20

---

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: The abstract and introduction contain the summary of our results, specifically the achieved speedups.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The proposed algorithm performs best when the drafting model is of high quality and well aligned with the target model. This may become practical obstacle in obtaining high throughput in settings with comparatively low inference cycle time of the target model, namely without offloading. Additionally, the method is performing less impressively when used with quantized models since those start requiring significantly greater run time with moderate-to high batch sizes.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, 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 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 is low or images are taken in low lighting. Or speech-to-text 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged 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.
21

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In this paper's 's theoretical analysis, mostly refer to the results proven earlier, however for the equivalence optimal tree search to shortest path search, we provide a proof in the 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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our results are reproducible using the attached code. The necessary setup details are given in the manuscript of the paper and in the appendix named "Additional Implementation Details".
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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, 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 replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
22

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are 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., to 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
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The experiments for this paper only use openly available datasets and code libraries. The code with launch instructions is attached to the paper submission and we intend to keep it open.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm 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 (c.g., for 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
//iips.c//pple wttpccpppppppppeeeeeeeeeeeeeeeee
haaoll/ieggudeee/eeeeeuuuiisssss Coodeeoomdissiiieeccca sonoooooccss for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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?
Question:
Answer: [Yes]
Justification: The paper, together with the "Additional Implementation Details" appendix and instructions in the code, contain information on all substantial details necessary to understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
23

---

Justification:
Following the setting of the past papers in the speculative decoding area, we focus on providing the attained generation speed and acceptance rates.
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, statistical significance tests, 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, 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.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-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 range (e.g. negative error rates).
If error bars reported in tables 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification: the paper and in the "Additional Implementation Details" appendix, we list the GPU types used and indicative memory requirements.
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 as 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 failed experiments that didn't make into the paper).
9. Code Of Fthics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt///neurippp clts.cc/puuue hccppblllc/tthhcccuueeeeell.
Answer: [Yes]
Justification: Yes, we confirm adherence to the NeurlPS Code of Ethics.
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 (c.g., there a special consid- eration due to laws or regulations in 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: This paper studies the efficient inference of large language models accel- erators with limited memory. Importantly, using LLMs in these environments is already possible due to considerable number of previously proposed algorithmss, area is well-known within the machine learning community. The method we propose does not affect the task performance of the language model it is applied to, as it only improves the speed of generation with that model. Therefore, we feel that no potential consequences of LLM use (aside from those already discussed in past work) need to be specifically highlighted in our paper.
the research
Guidelines:
The answer NA means that there no societal impact of the work performed.
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 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.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it 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 is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe 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: This paper does not alter the capabilities of the available models or datasets, but rather provides a more efficient approach use them on hardware with limited capabilities. Thus, we believe that our paper has a neutral risk impact in this area.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
25

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We included references to the models, datasets, and other assets used in this paper. We believe that our use of these assets is consistent with their respective license terms.
Guidelines:
The answer NA means that the paper does use 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 (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We made an effort to document the proposed method and added its code implementation with appropriate instructions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember 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 sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The experiments in the paper did not require crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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.
26

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
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 equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The experiments in the paper did require crowdsourcing human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor 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 adhere the NeurIPS 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.
27


Reviews:
[{"review_id": "AwSKPrQJD1", "reviewer": "Reviewer_fKWn", "summary": "This work introduces SpecExec, an improved speculative decoding method.\n\nBy constructing a better draft token tree and refining the process of verifying tokens, SpecExec significantly increases the number of tokens accepted in a single verification while producing exactly the same outputs as sequential sampling from the target model.\n\nAdditionally, SpecExec leverages the capability of modern offloading engines to dispatch model parameters in parallel with computation, successfully achieving effective acceleration under offloading configurations.\n\nExperiments demonstrate that SpecExec can run a 70B model on consumer-grade GPUs and achieve up to 10.6 times acceleration.", "questions": "1. In Line 14 of Algorithm 1, \"next_probs := FORWARD(τ, θ_target)\", how is forward inference performed on the draft tree? Is it the same method used in SpecInfer?\n\n2. The paper lacks clear illustrations of the working process of SpecExec. Could additional diagrams be added to provide a more vivid explanation?\n\n3. The paper mentions several articles related to speculative decoding but lacks an introduction to these works and does not explain the differences between them. Adding this background could help readers better understand this paper and it's contribution.", "limitations": "The authors have not adequately discussed the limitations of this paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. SpecExec uses a modified version of Dijkstra’s algorithm to create better token trees, significantly increasing the number of tokens accepted in a single verification.\n\n2. SpecExec views the process of parallel verification of candidate tokens as looking them up in a speculative “cache”, ensuring that the output is identical to that of sequential sampling, while speculative decoding only guarantees correct overall sampling probabilities.\n\n3. SpecExec has demonstrated excellent acceleration in experiments, significantly outperforming SpecInfer and showcasing superior performance.", "weaknesses": "1. While SpecExec achieves significant performance acceleration in systems with offloading, it is unclear how this method performs in terms of acceleration in speculative inference systems that do not have offloading.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and appreciate that they share our views on the algorithm performance factors. Below, we do our best to address the reviewer’s concerns and answer questions.\n\n>  It is unclear how this method performs in terms of acceleration in speculative inference systems that do not have offloading.\n\nWe report experiments for the non-offloading setting in Appendix F (referenced in L287). The in-memory (no offloading) setting allows relatively less time for speculation compared to offloading. Nevertheless, our method demonstrates considerable speedups of up to 2.4x even in this setting.\n\n>  Line 14 of Algorithm 1, … how is forward inference performed on the draft tree?\n\nFirst, SpecExec uses the draft model to construct the draft tree in such a way that it covers the most probable text continuations. Next, in line 14 the algorithm runs the target model to get “true” probabilities in each of the tree nodes, which is done in a single forward pass, using a custom 4D “tree-attention” mask (L537-538).  This prefills a speculative “cache” of continuations to choose from  (See Alg.1 L6). Finally, we use these cached target model’s probabilities to generate final tokens.\n\n> Could additional diagrams be added to provide a more vivid explanation? (...)  Adding this background could help readers better understand this paper and its contribution.\n\nThank you for the suggestion. We offer a limited overview of speculative decoding works in Section 2.1, but we agree that the paper would benefit from a more detailed introduction to the topic.\nWe had ideas on more detailed background and extra illustrations, but chose instead to allocate more of our page limit to the algorithm and experiments. Should our paper be accepted, we intend to use the extra space to improve the intuitive diagram of the algorithm and extend the background section.", "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": "PLKtsYKsUU", "reviewer": "Reviewer_ph7U", "summary": "The authors present a method to improve the efficiency of speculative decoding on consumer-grade hardware. The technique addresses the inefficiencies of existing speculative decoding approaches when applied to devices with limited GPU memory, necessitating parameter offloading to RAM or SSD. SpecExec leverages a powerful draft model to create a speculative tree of potential token continuations, which the target model then verifies. This approach enables the processing of multiple tokens in parallel, significantly improving the inference speed on consumer GPUs.", "questions": "My questions are mainly regarding the experiment details discussed above in the weakness section.", "limitations": "Yes, the authors adequately addressed the limitations and, if applicable, potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a solid empirical analysis of key inefficiencies of speculative decoding and presents a well-founded solution. The paper is written clearly with solid motivation and method sections. \n\nThe empirical results that the authors provide are impressive, showing consistent speedup over SpecInfer on the number of generated tokens per step. \n\nIn addition to results on generated tokens per step, the authors also present an impressive speedup on tokens per second, showing that the improvement achieved at generated tokens per step can be translated to real wall-clock speedup.", "weaknesses": "1. Some experiment results are a bit confusing. For instance, the captions in Figure 3/4 say Generation rate vs draft size for Llama 2-7B/70B models, but it's not clear where the 7B model numbers are. The main text states the plots are for 70B models. \n\n2. The authors claim they have results on both base and chat models. But it's not clear from the tables and figures, which are chat models and which are base models. And further, whether this would lead to different results/conclusions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the well rounded review of the paper and address the questions below:\n\n> Some experiment results are a bit confusing. For instance, the captions in Figure 3/4 say Generation rate vs draft size for Llama 2-7B/70B models, but it's not clear where the 7B model numbers are. The main text states the plots are for 70B models.\n\nIn these figures, we use the 7B model **as a draft model**, whereas the 70B is the target model.\nSince the algorithm employs a separate draft model to speculatively develop a continuation tree, each experiment uses two models. Namely, we use a 7B draft model to develop a tree and a 70B target model for verification. We agree that the captions to the figures could be more detailed and will update them.\nTo further alleviate the reviewer’s concern, we have conducted an **additional set of experiments where the 7B model is the target model**, as suggested. For this experiment, we pair the 7B target model with TinyLlama 1.1B as the draft model. The rest of the experiment configuration is the same as in Section 5.2. The results can be found in **Figure 1 in the PDF attachment**.\n\n> The authors claim they have results on both base and chat models. But it's not clear from the tables and figures, which are chat models and which are base models. And further, whether this would lead to different results/conclusions.\n\nFollowing the examples of other speculative decoding papers, we report results separately for the two model classes. For most figures and tables, we use the word “chat” in the caption to indicate the results of the instruction-trained models, with a few omissions that we will rectify. Specifically, Figures 2, 4, 5, 6 and Tables 1, 3 and 4 are for chat models. Figures 1, 3, 7 and Table 2 provide results for non-chat models. We missed this caption in Figure 2, where we use chat models.\n\nOverall, we noticed that the algorithm demonstrates similarly high performance with both chat and base models. We thank the reviewer for bringing the missing captions to our attention. In the final version of the paper, we will add clearer labels to make the figures easier to follow.", "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": "DSFsuloK6v", "reviewer": "Reviewer_BH6v", "summary": "In this paper, the authors propose a speculative decoding technique, SPECEXEC (Speculative Execution), that can generate up to 20 tokens per iteration for the LLaMA-2 70B model. SPECEXEC enables the LLaMA-2 70B model to run on a consumer GPU by a parallel decoding strategy. The offloading scheme can process thousands of tokens using the same latency as that of one token. Therefore, the offloading scheme can be naturally used in supporting speculative decoding. However, prior speculative decoding techniques do not scale with a large batch of draft tokens. SPECEXEC uses a smaller draft model to built a tree of best tokens by single-source shortest path (SSSP) searches, and then processes best tokens with the target model by offloading. SPECEXEC also includes a new algorithm to determine which tokens are accepted.", "questions": "1. What type of applications are more suitable for SpecExec? The applications have not enough server-level GPUs?", "limitations": "no limitation.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. The paper works on an important topic.\n2. The paper includes enough supporting data.", "weaknesses": "1. The paper is not well-written. SPECEXEC is built on a important observation that the offloading of the target model can process thousands of tokens using the same latency as that of one token. SPECEXEC suffers from a lower acceptance rate for individual tokens. For a small number of draft tokens, SpecExec is less efficient than speculative decoding. However, for a large enough number of draft tokens, SpecExec obtains a better tree and increases the accept rate. SPECEXEC adopts the offloading technique to mitigate the processing of the  large enough number of draft tokens. Unfortunately, the authors did not justify the applications or user cases that must use the offloading schemes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback; we are glad that they appreciate our experimental results. Below, we do our best to address the concerns and answer questions.\n\n>The paper is not well-written.\n\nWe are eager to improve our writing and respectfully ask the reviewer to suggest specific improvement areas (e.g., in the updated review). While there are improvement areas, other reviewers found our presentation to be good (3), and we hope that the remaining issues can be fixed. We will pay significant attention to the writing and presentation style when developing the final version of the paper.\n\n> SPECEXEC suffers from a lower acceptance rate for individual tokens.\n\nThis is technically correct, but it is not a weakness of SpecExec. As we discuss in Lines 148-159, we deliberately use a simpler acceptance algorithm to lift the constraints on the draft tree structure. In turn, this allows us to dynamically build the best tree for a given budget, unlike SpecInfer which requires a specific sampling distribution.\n\nThe algorithm may occasionally exhibit a lower acceptance rate **for individual tokens**, when compared to SpecInfer. However, in practice, the average individual acceptance rate is not much different. This choice allows for superior global acceptance rate and speedup which are the key metrics important to the algorithm users.\n\n> For a small number of draft tokens, SpecExec is less efficient than speculative decoding. However, for a large enough number of draft tokens, SpecExec obtains a better tree and increases the accept rate.\n\nSpecExec is less effective than traditional speculative decoding only for cases with very small trees (1-4 tokens). In our main experiments, SpecExec is very close to SpecInfer for small budgets of up to 32 tokens draft tokens, but still slightly outperforms it. Please refer to Figures 3 and 4, where SpecExec attains better results for all considered token budgets. We attribute this to the fact that SpecExec picks the best tokens (most probable tree cumulatively), while SpecInfer and similar methods have to sample draft tokens randomly in order to maintain output distribution. However, the degree to which SpecExec outperforms SpecInfer is smaller because there is less potential to construct better draft trees.\n\n> the authors did not justify the applications or user cases that must use the offloading schemes - add details and examples. What type of applications are more suitable for SpecExec? The applications have not enough server-level GPUs?\n\nIn general, our approach can be helpful for LLM inference in any resource-constrained environment. One such environment is running modern LLMs with tens of billions of parameters on desktop hardware with consumer-grade GPUs.  Another important application is model inference on smartphones where even relatively small models need to be offloaded. Moreover, our approach can be applied to datacenter-grade GPUs running extremely large models (Nemotron-340B, Llama 3.1 405B).  Finally, there is a potential application to run extremely large models in a distributed environment, where the communication delays add latency to the base model, which is similar to the delays that stem from offloading.\n\nWe hope that our reply alleviates your concerns and welcome further suggestions in the updated review.", "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": "6cQKtZf4El", "reviewer": "Reviewer_PkkW", "summary": "This paper presents a novel speculation decoding method called SpecExec, designed to improve the performance of large language model (LLM) inference on consumer-level GPUs with offloading scenario. The main contribution is the application of speculative execution, a technique from CPU architecture, to the speculation decoding of LLMs. SpecExec leverages a draft model to construct a large draft tree of potential continuations, which are then verified in parallel by the target model. This approach aims to mitigate the inefficiencies of existing speculative decoding methods, particularly when dealing with a large number of draft tokens. The experiments result demonstrate that SpecExec achieves up to 18.7x speedup.", "questions": "- How much speedup does SpecExec gain without RAM offloading? For example, Llama2-70b chat GPTQ model on an A100 GPU. I am just curious\n- So, if I understood correctly, sampling parameters such as t = 0.6, p = 0.9 do not affect the draft tree, right? (deterministic tree)\n- In Figure 3 and 4, random sampling results are comparable with greedy sampling on the MTBench dataset while the C4 dataset shows lower hit ratio on random sampling. Does this difference come solely from the difference between datasets?\n- Can SpecExec achieve high performance gain on token penalty scenarios? For example, repetition penalty, presence penalty, and frequency penalty.", "limitations": "No additional limitations regarding societal impact.\nFor technical limitations, I stated in the weakness section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper tackles specific and clear setup. Since offloading  is the main bottleneck of LLM inference on consumer-level GPUs, using speculative decoding with many draft tokens is much more preferable. \n- SpecExec is robust for non-deterministic request (i.e., t = 0.6, top_p = 0.9)\n- As the SSSP problem is one of the well-studied problems in the CS domain, it may be easy to adopt other variants of SSSP to generate different draft trees (extendability).", "weaknesses": "- Although the paper targets consumer-level GPUs, the experiment results show that SpecExec achieves the highest speedup with the A100 GPU, one of the most popular datacenter-level GPUs.\n- Token throughput is still slow because of the offloading. For A100 GPU, using 4-bit quantized 70B model (AWQ, GPTQ, ...) and without speculative decoding will be more practical.\n- SpecExec seems plausible only for single request with single user.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and questions. We are glad that the reviewer appreciates the practical impact of our work for LLM inference on consumer GPUs. Below we address the questions to the best of our ability:\n\n> Although the paper targets consumer-level GPUs, the experiment results show that SpecExec achieves the highest speedup with the A100 GPU, one of the most popular datacenter-level GPUs.\n\nWe do indeed show high speed-ups on A100 GPUs, but we respectfully insist that this is not a weakness. Our main setup is still consumer GPUs — see Table 3 where we show significant speed-ups on consumer GPUs. Attaining speedup on a datacenter-grade A100 GPU is less challenging, but has a positive side-effect. We are glad that our approach can also accelerate datacenter applications. In light of recent LLM developments, this could allow datacenter users to run extremely large models (Nemotron-340B, Llama 3.1 405B) that do not fit on a single datacenter-grade GPU.\n\n> Token throughput is still slow because of the offloading. For the A100 GPU, using a 4-bit quantized 70B model (AWQ, GPTQ, ...) and without speculative decoding will be more practical.\n\nIn short, our method allows to use even less VRAM and fully preserve the original model quality.\n\nQuantization methods like GPTQ are indeed trying to solve a similar problem: to run LLMs with lower VRAM utilization. Quantized models can deliver decent compression at a slight cost in accuracy. Still, our method opens additional applications: (a) even lower vRAM requirements. Llama 70B GPTQ in 4 bit requires ~35 GB of VRAM, while our method allows it to fit into under 20GB (with Llama 7B draft model) or possibly even under 12GB if using a less capable draft model. (b) some users may insist on non-quantized models for applications requiring every last bit of performance or reproducing results of the original models.\n\nFurthermore, the quantized models may be offloaded and accelerated using our method, offering further speedups. We use GPTQ target models for some experiments reported in Tables 1 and 2, achieving an acceleration of up to 9x (against autoregressive inference) due to faster offloading.\nWhile there indeed are setups that SpecExec is not optimal for, our paper focuses on a narrow but practically important task of inferencing models with offloading, where we achieve significant speed-ups.\n\n> SpecExec seems plausible only for single request with single user\n\nYou are correct, and this is our target application setting. While our algorithm may be adopted for batch applications, it would require significantly more VRAM which is not what our typical user may have. Our objective is to give users of less capable GPUs the ability to run modern LLMs with decent quality and usable speed.\n\n> How much speedup does SpecExec gain without RAM offloading?\n\nThe in-memory (no offloading) setting allows relatively less time for speculation compared to offloading-scale timings. Nevertheless, our method demonstrates decent speedups of up to 2.4x with Vicuna-33b model: please refer to Appendix F for experiment results in this setup. \n\n> sampling parameters such as t = 0.6, p = 0.9 do not affect the draft tree, right? (deterministic tree)\n\nIn short, the SpecExec draft tree is not deterministic, but its shape in our implementation is not dependent on generation temperature.\nWe experimented with applying the same sampling temperature to the draft model when constructing the tree, however, we found that keeping the draft model always sampling at temperature 1.0 gives the most consistent results. Our algorithm builds the tree dynamically, selecting the best new nodes in order to maximize the expected length of the text continuations covered by the tree.\n\n> Figure 3 and 4, random sampling results vs greedy for MTBench and C4/ - Does this difference come solely from the difference between datasets?\n\nThe non-chat C4 dataset has a higher inherent text entropy, so when generation temperature grows, the model gets a wider choice of reasonably probable tokens, and matches between top choices of the draft and target models become relatively less frequent. Still, our algorithm outperforms SpecInfer in this scenario by a large margin.\n\n>Can SpecExec achieve high performance gain on token penalty scenarios? \n\nIn theory, the algorithm could work with any penalty that modifies the model probabilities. If the same penalty scheme is applied to both draft and target models, the models should be able to run SpecExec effectively.\nTo verify this claim, we ran a series of experiments with penalties excluding use of fewer or more tokens.  The results of these experiments can be found in **Figure 2 in the PDF attachment**. More specifically, we penalize all tokens that start from the letter “r” (Figure 2 left) or all tokens that contain the letter “r” (Figure 2 right). We use the same setup as in the previous experiments (Figure 1).\n\nWe found that our method’s performance (measured in terms of accepted tokens per iteration) stays stable only with lightweight penalties, while heavier penalties reduce the absolute speedups. Looking at the generated text, we observed that while with lighter penalties the model is able to work around the restrictions and generate reasonable text, with heavier penalties the quality deteriorated as the model skipped or replaced tokens seemingly at random. Stronger penalties affect the quality of the generated text and naturally make the task harder for the draft model. Thus, we attribute the lower performance with a heavy penalty to this perplexity increase rather than to the penalty directly. \n\nWe hope that the additional experiments and explanations help address your concerns and answer questions. If the reviewer has any further suggestions on improving the paper, we encourage them to include them in the OpenReview, e.g. by editing the review.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for taking the time to study our paper and providing valuable feedback. We are glad to notice that all four reviewers appreciate the practical speed-ups achieved by SpecExec and its positive impact on LLM accessibility. On the reviewers' suggestions, we implemented a few additional experiments described in our individual responses and in the attached PDF. The reviewers gave us a number of ideas on making the paper more polished and complete, which we intend to implement for the final version.  The individual reviewers' questions and concerns are addressed in the reviewer-specific rebuttal sections. 

Additionally, we'd like to highlight these common themes in several reviews:

- our method's somewhat lower acceptance rate on the individual token level is not a problem but a necessary trade-off, allowing us to build arbitrarily shaped trees, specifically ones that include the most probable tokens in each generation.

- our algorithm is focused on applications with relatively high target model latency, which makes multiple speculation iterations by a reasonably capable draft model affordable. Such a setup allows building quite large trees (up to thousands of tokens) and delivering speedups in 15x-20x range. Using our method with already fast models in an in-memory setting will also provide significant speedups, but those would not stand out among the ones from competitive methods.


In the attached PDF, we included several additional experiments to help us answer some of the reviewers questions:
* **(ph7U)** Additional evaluations where the 7B LLM is used as the target model, with a smaller draft model;
* **(PkkW)** Experiments on speculative decoding with a token penalty, comparing SpecExec and SpecInfer.

Meta-review: The paper has an Average Rating: 5.75 (Min: 5, Max: 7) and is slightly above the acceptance threshold. While there are various issues, all reviewers have given positive evaluations. Considering the following strengths, I recommend acceptance(poster).

1: SpecExec offers a method that enables large LLMs to operate efficiently on consumer-grade GPUs. Even on consumer hardware, it achieves more than a tenfold speed improvement when combined with offloading, making LLMs more accessible and practical by enhancing their accessibility and usability.

2: The proposed method consistently shows higher speed improvements compared to existing SpecInfer methods, especially when processing large numbers of tokens in parallel. Significant improvements in actual computation time have also been confirmed.

3: SpecExec extends existing inference methods by utilizing Dijkstra’s algorithm to construct more efficient token trees, allowing multiple tokens to be verified simultaneously. This significantly improves speed while maintaining the same output as sequential sampling.

4: The SpecExec algorithm leverages techniques adapted from CPU architecture, making it robust and applicable to a broader range of computing environments and models in the future. It is particularly well-regarded for its applicability to scenarios where inference speed is critical.
Decision: Accept (poster)