MagicDec: Breaking the Latency-Throughput Tradeoff for Long Context Generation with Speculative Decoding

## Abstract

Abstract Large Language Models (LLMs) have become more prevalent in long-context applications such as interactive chatbots, document analysis, and agent workflows, but it is challenging to serve long-context requests with low latency and high throughput. Speculative decoding (SD) is a widely used technique to reduce latency without sacrificing performance but the conventional wisdom suggests that its efficacy is limited to small batch sizes. In MagicDec , we show that surprisingly SD can achieve speedup even for a high throughput inference regime for moderate to long sequences . More interestingly, an intelligent drafting strategy can achieve better speedup with increasing batch size based on our rigorous analysis. MagicDec first identifies the bottleneck shifts with increasing batch size and sequence length, and uses these insights to deploy speculative decoding more effectively for high throughput inference. Then, it leverages draft models with sparse KV cache to address the KV bottleneck that scales with both sequence length and batch size.
This finding underscores the broad applicability of speculative decoding in long-context serving, as it can enhance throughput and reduce latency without compromising accuracy .
For moderate to long sequences, we demonstrate up to 2x speedup for \seqsplit LLaMA-2-7B-32K and 1.84x speedup for \seqsplit LLaMA-3.1-8B when serving batch sizes ranging from 32 to 256 on 8 NVIDIA A100 GPUs.
The code is available at https://github.com/Infini-AI-Lab/MagicDec/ .

## 1 Introduction

The landscape of language models has changed dramatically, with models capable of processing extremely long context lengths becoming increasingly prevalent [, , , ]. Interactive use cases such as chatbots [] demand low latency, whereas background data-processing workloads prioritize high throughput [, ]. However, simultaneously achieving high throughput and low latency is challenging [].

Figure: (a) Throughput of Autoregressive decoding and SD for prefill 8000.
Refer to caption: x1.png

Speculative decoding (SD)[, , ] has emerged as a latency improvement technique which is guaranteed to maintain the generation quality.
A fast draft model is used to generate multiple tokens and then the LLM verifies the speculated tokens in parallel, which is only marginally more expensive than decoding one token.
However, SD has been believed to be less effective in improving throughput with larger batch sizes [, , , ].
On the other hand, methods like vLLM [] and ORCA [] can achieve high throughput by serving more requests, but cannot reduce latency. Lossy methods like quantization [, , ] and pruning [, ] have been proposed to improve both throughput and latency, but they can suffer from performance degradation.
Given these trade-offs, we pose the following question:

> Can we simultaneously improve throughput and latency without sacrificing accuracy, particularly for long sequences?

In this work, we challenge the conventional belief that speculative decoding is inefficient for increasing throughput. We demonstrate that for moderate to large sequence lengths, *speculative decoding can achieve all three objectives: increased throughput, reduced latency, and lossless accuracy*. Furthermore, by addressing the KV bottleneck using draft models with sparse KV cache, we can achieve even better speedup for larger batches of requests.

This conclusion is derived from a comprehensive analysis of LLM decoding performance, which reveals that as batch size grows, LLM decoding remains memory-bound for medium-to-long sequences[, ]. In this regime, KV cache becomes the dominant bottleneck. Unlike model parameter loading, this new bottleneck scales with batch size, making speculative decoding even more effective for large batches. As Figure 1 illustrates, for a given latency budget, SD has higher throughput than autoregressive decoding, and the efficacy of SD is evidently greater for longer sequences. Moreover, if we can allow a higher latency budget, we can improve throughput even more with MagicDec.

The main contributions of our work are:

- 1.
We performed a theoretical analysis of LLM inference performance with speculative decoding. Our findings indicate that with medium-to-long sequence lengths and large batch sizes, LLM remains memory-bound and can be effectively accelerated through speculative decoding.
- 2.
We found KV cache size of draft models, rather than model weights, is the most important factor in large batch and long sequence regime from our analysis. Therefore, we propose draft models with constant KV cache by StreamingLLM [], making improving speedup with increasing batch size possible.
- 3.
To verify our analysis, we conducted empirical evaluations across various GPUs and LLMs by sweeping batch sizes and sequence lengths. Our SD based system improves both throughput and latency, achieving a 2x speedup over autoregressive decoding for \seqsplitLLaMA-2-7B-32K and a 1.84x speedup for \seqsplitLLaMA-3.1-8B on 8 A100 GPUs .

## 2 Related Work

Numerous efforts have been made to improve the latency and throughput of LLMs. While methods like Flash-decoding [], Flash-decoding++[], FasterTransformers[] have performed system optimizations to improve latency, Speculative Decoding[, , ] has emerged as a novel sampling algorithm to speed up inference. On the other hand, batching has been a natural technique to improve GPU utilization and throughput. To make batching more effective, continuous batching [, , ] and chunked prefill [] techniques have proposed intelligent batch scheduling techniques. Although these techniques can address the problems arising from heterogeneous batches with unequal context and generation lengths, they cannot solve the memory-bound problem of autoregressive decoding. In our work, we have considered the orthogonal direction of homogeneous batches, and therefore the aforementioned methods are complementary to our observation.

In our work, we have used speculative decoding as a method to balance the throughput-latency trade-off. We have particularly focused on draft models with StreamingLLM KV cache. This approach is motivated by the recent finding in Triforce [] that self-speculation with sparse KV is an effective draft choice when KV loading is the main bottleneck. While Triforce is designed for small batches of extremely long sequences, we have focused on large batches of moderate to long sequences in our work.

Although promising for single batch requests, Speculative Decoding poses new challenges when implemented with batch support. Because the number of accepted tokens in SD follows a truncated geometric distribution [], the average accepted length can vary throughout the batch, leading to misalignment of the sequence lengths. Qian et al.[] have optimized the attention kernels to take care of this unequal number of accepted tokens across the batch. However, as previously reported, the excess computation for SD could be restrictive in a large batch size regime [, , , ]. Hence, [, ] suggest a reduction in speculation length with increasing batch size.

These findings imply that SD is not as effective in improving throughput; however, we notice that these observations are limited to a very small sequence-length regime. In our work, we focus on the relatively longer sequences that have been ubiquitous in practice.

## 3 Theoretical Analysis

In this section, we first outline the theoretical model to estimate the speed-up using SD and discuss various factors that affect it. In addition, we conduct several theoretical analysis on how the effect of these factors varies in different sequence length and batch size regimes. This forms the basis of our empirical studies discussed in section §5.

As introduced in §1, SD uses the LLM (target model) to verify the tokens speculated by a small draft model. This parallel verification amortizes the cost of loading the model parameters. The final output tokens are sampled using rejection sampling, ensuring the same output as the target distribution [, ].

### 3.1 Mathematical Formulation of Speedup

Given a speculation length $\gamma$ for a sequence of length $S$ and batch size $B$, let $\bf{T_{T}(B,S,1)}$ and $\bf{T_{D}(B,S,1)}$ denote the times taken by the target and draft models to decode one token, respectively. The verification time, $\bf{T_{V}(B,S,\gamma)}$, is the time it takes the target model to verify the $\gamma$ tokens speculated by the draft model in a single forward pass. Given an acceptance rate $\alpha\in[0,1]$ and speculation length $\gamma$, $\bf{\Omega(\gamma,\alpha)}$ represents the expected number of tokens generated in one verification step, as described in [].

$$ $\Omega(\gamma,\alpha):=\mathbb{E}(\#\>generated\>tokens)=\frac{1-\alpha^{ \gamma+1}}{1-\alpha}$ (1) $$

The total time taken for speculative decoding, $T_{Total}^{SD}$, is given by:

$$ $T_{Total}^{SD}=\gamma\cdot T_{D}(B,S,1)+T_{V}(B,S,\gamma)$ $$

The per-token latency for speculative decoding is simply $T_{Avg}^{SD}=\frac{T_{Total}^{SD}}{\Omega(\gamma,\alpha)}$.

For simplicity, we will refer to these times as $T_{T}$, $T_{D}$, and $T_{V}$ going forward, with the dependence on $B$ and $S$ implied unless otherwise specified. The total speedup from speculative decoding is then expressed as:

$$ $\frac{T_{T}}{T_{Avg}^{SD}}=\Omega(\gamma,\alpha)\cdot\frac{T_{T}}{\gamma\cdot T _{D}+T_{V}(\gamma)}$ (2) $$

This equation can be further rewritten as:

$$ $\frac{T_{Avg}^{SD}}{T_{T}}=\frac{1}{\Omega(\gamma,\alpha)}\left(\frac{\gamma \cdot T_{D}}{T_{T}}+\frac{T_{V}(\gamma)}{T_{T}}\right)$ (3) $$

Figure: (a)
Refer to caption: x3.png

### 3.2 Factors Affecting Speculative Decoding Speedup

Using Eq 3, we can see that speed-up depends on three primary factors: (a) draft to target cost ratio $\frac{T_{D}}{T_{T}}$ (b)
verification to target decoding cost ratio $\frac{T_{V}(\gamma)}{T_{T}}$ and (c) expected
generation length $\Omega(\gamma,\alpha)$.

#### 1. Draft to Target Cost Ratio ( T D / T T ) subscript 𝑇 𝐷 subscript 𝑇 𝑇 ({T_{D}}/{T_{T}}) ( italic_T start_POSTSUBSCRIPT italic_D end_POSTSUBSCRIPT / italic_T start_POSTSUBSCRIPT italic_T end_POSTSUBSCRIPT ) :

Figure: (g) \seqsplitLLaMA-2-7B
Refer to caption: x9.png

A lightweight draft model is generally preferred for a shorter model loading time and fewer computations, leading to ${T_{D}}/{T_{T}}\approx 0$. However, with increasing sequence length, the bottleneck is shifted to KV cache loading. Furthermore, this bottleneck scales linearly with batch size, making KV loading an even bigger bottleneck for large batches as shown in Figure 3. In the cases of \seqsplitLLaMA-3.1-8B for \seqsplitLLaMA-3.1-70B and \seqsplitLLaMA-2-7B for \seqsplitLLaMA-2-70B , the draft models can occupy up to $38\sim 140\%$ memory footprint of target models (Figures 3 and 3)due to the fact that $\mathrm{dim}_{kv}/\mathrm{dim}_{model}$ is higher. Hence, for long sequences, draft models with sparse KV is quite beneficial[]. This can be seen in Figure 4, which illustrates how ${T_{D}}/{T_{T}}$ for self-speculation approaches 0 with increasing sequence length for batch size 256.

In addition, Figure 2(a) and Figure 2(d) show how this ratio diminishes with increasing batch size for sufficiently long sequences. While the draft cost increases with larger batch sizes mainly due to increased computation time, the target cost rises even more due to the greater KV loading time. This makes the draft-to-target cost ratio decrease with increasing batch size, making speculative decoding more effective.

#### 2. Verification to Target Decoding Cost Ratio ( T V ⁢ ( γ ) / T T ) subscript 𝑇 𝑉 𝛾 subscript 𝑇 𝑇 \left(T_{V}(\gamma)/T_{T}\right) ( italic_T start_POSTSUBSCRIPT italic_V end_POSTSUBSCRIPT ( italic_γ ) / italic_T start_POSTSUBSCRIPT italic_T end_POSTSUBSCRIPT ) :

As evident from Eq 3, this ratio is desired to be close to 1. In low batch size setting, the verification process makes use of the underutilized compute and amortizes the cost of model loading. However, previous work [] observed that with large batch sizes, $T_{V}(\gamma)/T_{T}$ becomes significantly greater than 1 as the model becomes more compute-bound [, ].

Our theoretical analysis challenges this argument. Figure 2(b) and Figure 2(e) illustrate how the ratio changes for \seqsplitLLaMA-2-7B-32K and \seqsplitLLaMA-3.1-8B with increasing batch size for different sequence lengths and a fixed speculation length of 3. As can be seen from the two figures, the $\left(T_{V}(\gamma)/T_{T}\right)$ ratio is expected to remain reasonably close to 1 for long sequences even when the batch size is quite large.

#### 3. The expected generation length ( Ω ⁢ ( γ , α ) ) Ω 𝛾 𝛼 (\Omega(\gamma,\alpha)) ( roman_Ω ( italic_γ , italic_α ) ) :

$\Omega$ is a function of the acceptance rate $\alpha$ and the speculation length $\gamma$. Here we look at how $\alpha$ and $\gamma$ affect $\Omega$ and hence the speedup.

- (a)
$\alpha$:
For a fixed draft cost, as $\alpha$ increases, $\Omega(\gamma,\alpha)$ increases, leading to a higher speed-up. In the regimes where $T_{V}(\gamma)\gg T_{T}$, $\alpha$ becomes pivotal as a lower $\alpha$ leads to considerable time spent on verifying tokens that are eventually discarded [].
On the other hand, achieving a higher $\alpha$ usually comes at the cost of a higher $T_{D}$.
- (b)
$\gamma$:
A longer speculation length increases $\Omega(\gamma,\alpha)$, but it also raises the verification and draft decode costs. In addition, the proportion of accepted tokens reduces with increasing $\gamma$ []. This is because $\Omega$ follows a truncated geometric distribution [], as seen in eq. 1. Thus, finding the optimal $\gamma$ is crucial for achieving the best speedup under different batch sizes and sequence lengths.

### 3.3 Speculative Decoding Speedup Analysis

In this section, we examine the impact of increasing batch size on speculative decoding performance and discuss how our theoretical analysis provides insights into overcoming this challenge.

> Our analysis identifies a critical sequence length $\bf{S_{inflection}}$ for a given model pair and hardware. When $S\geq S_{\text{inflection}}$, the speculative decoding speedup tends to increase with batch size. However, this is not the case for $S<S_{\text{inflection}}$.

$\mathbf{S<S_{\text{inflection}}}$:
As noted in Subsection §3.2, a shorter verification time allows SD to achieve a greater speedup. While serving smaller batches, SD can efficiently use underutilized compute resources for its verification phase. However, large batches can saturate the available compute, making verification more expensive. If the draft token acceptance rate is low, the target model spends considerable time verifying incorrect speculations, reducing SD efficiency.

In this regime, our theoretical estimate aligns with Liu et al.[]. As illustrated in Figure 2(c), the speedup with SD decreases with batch size for prefill lengths below the critical sequence length.

$\bf{S\geq S_{inflection}}:$
In this regime, we note that both $\frac{T_{D}}{T_{T}}$ and $\frac{T_{V}(\gamma)}{T_{T}}$ are low, favoring speculative decoding as per equation 3. For sufficiently long sequences, the ratio $\frac{T_{D}}{T_{T}}$ decreases with increasing batch size, as discussed in Section §3.2. Furthermore, the rate of increase in $\frac{T_{V}(\gamma)}{T_{T}}$ with the batch size is significantly slowed for longer sequences, while the acceptance rate remains unaffected. As a combined effect, there is an increase in speedup with batch size.

The key observation behind our analysis is that, for large sequences, KV becomes the main bottleneck instead of compute [, ]. This shift in bottleneck from compute to KV memory forces the target model to be memory bound even for a large batch size. Figure 4 shows for batch size 256 how the bottleneck changes from compute to memory with increasing sequence length (for different models and hardware pairs). As a result of this shift, the estimated ratios of verification and decoding time $\left(\frac{T_{V}(\gamma)}{T_{T}}\right)$ remain consistently close to 1 for $S>S_{\text{inflection}}$ (see Figure 2(b)). In addition, Figure 3 shows how KV loading becomes even more dominant with increasing batch size. If we use sparse KV cache for the draft model, the draft to target cost ratio will go down with increasing batch size. Consequently, we expect a greater speedup for larger batches.
Thus, as Figure 2(c) illustrates in the case of \seqsplitLLaMA-2-7B-32K , the speedup with SD is expected to improve with increasing batch size for longer sequence lengths. It can be seen that the theoretical speedup decreases with batch size for $S<1024$, but for $S\geq 1024$, the speedup increases with batch size.

Figure: (a)
Refer to caption: x12.png

#### Factors Affecting S inflection subscript 𝑆 inflection S_{\text{inflection}} italic_S start_POSTSUBSCRIPT inflection end_POSTSUBSCRIPT :

The critical sequence length, $S_{\text{inflection}}$, depends on both the model and the hardware. Figure 4 shows the FLOPS-to-memory ratio for \seqsplitLLaMA-2-7B and \seqsplitLLaMA-3.1-8B . For a device with a higher FLOPS-to-memory bandwidth ratio, we expect a lower $S_{\text{inflection}}$, as illustrated in Figure 4. Additionally, the model itself influences $S_{\text{inflection}}$. For instance, \seqsplitLLaMA-3.1-8B  has a higher $S_{\text{inflection}}$ due to its Grouped Query Attention (GQA), which requires a larger sequence length to achieve the same KV memory footprint (see Figure 4).

## 4 Draft Model Design

As discussed in §3, with the increasing batch size and the growing sequence length, the KV cache becomes the bottleneck. Accurate draft models with constant KV cache are ideal. Similar to [], we use StreamingLLM [] for draft models due to its simplicity and effectiveness. It employs attention sinks (KV of initial tokens) with a sliding window KV for attention computation, enabling a stable, training-free method to handle infinitely long contexts. Specifically,

#### Self-Speculation.

We leverage target models with StreamingLLM cache for accurate drafting since KV cache, rather than model weights, becomes major bottleneck. As we see in our theoretical analysis in Figure 4 for batch size 256, the relative cost of the self-speculation draft (with fixed budget 512) approaches 0 for large sequence lengths.

#### Standalone GQA Draft Models.

Since the KV size is several times smaller than that of regular (MHA) models, GQA draft models can further reduce draft cost on the basis of StreamingLLM cache, when the batch size and sequence length are large.

## 5 Experiments

In this section, we demonstrate how speculative decoding increases speedup with batch size for sufficiently large sequence lengths, which matches our theoretical analysis. We conducted most experiments on 8 Nvidia A100 GPUs with 8-way Tensor Parallelism. We also tested on higher-end GPUs like Nvidia H100 and lower-cost alternatives like Nvidia L40, these results are shown in Table 2 and Table 2. Across all these devices, we show that speculative decoding achieves significantly better throughput and lower latency than autoregressive decoding with long sequence lengths.

Figure: Algorithm 1 GQA Custom

### 5.1 Experimental Setup

In our experiments, we focused on two types of draft models as we discussed in Section 4. We tested various StreamingLLM cache budgets to balance draft cost and acceptance rate. These experiments were performed on the PG-19 dataset []. Each run was evaluated on 50 samples, generating 64 tokens per sentence in the batch using greedy decoding. The specifics of our draft selection are as follows:

- 1.
Self-Speculation: We experimented with \seqsplitLLaMA-2-7B-32K [, ] and \seqsplitLLaMA-3.1-8B-128K [] models with various StreamingLLM budgets for drafting.
- 2.
Standalone GQA Model: We used the long context variant of \seqsplitLLaMA-2-7B, \seqsplitLLaMA-2-7B-32K [], as the target model and \seqsplitTinyLLaMA-1.1B [] for drafting.

### 5.2 System Implementation

We built our speculative decoding system on top of GPT-Fast []. FlashAttention-2 [] was used to accelerate attention computation. During implementation, we observed that Grouped-Query Attention (GQA) [] lacks adequate support from FlashAttention when verifying multiple tokens simultaneously. To address this, we modified the GQA implementation to achieve the desired speed improvements detailed below (see Algorithm 1). Additionally, we used Pytorch CUDA graphs to reduce CPU-side kernel launching overhead. For self-speculation and draft models with limited context length, we used StreamingLLM [] with fixed KV cache budgets. This predetermined cache budget helps save CPU overhead through CUDA graphs.

#### Optimized Group Query Attention:

The implementation of Group Query Attention (GQA) by FlashAttention[] is found to be poorly optimized for the verification of multiple tokens. However, there is no such problem with regular Multi-Head Attention (MHA). Thus, to circumvent the problem of slow verification, we utilized FlashAttention’s MHA to implement GQA. The implementation details can be found in Algorithm 1.

Figure: (a) Draft: \seqsplitTinyLLama-1.1B , Target: \seqsplitLLaMA-2-7B-32K
Refer to caption: x15.png

**(a) \seqsplitLLaMA-2-7B-32K , \seqsplitTinyLLama-1.1B**
| S | B | $\bf{\gamma T_{D}}$ | $\bf{T_{V}}$ | $\bf{\Omega}$ | $\bf{T^{AR}}$ | $\bf{T^{SD}}$ | $\bf{x}$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 1024 | 32 | 8.21 | 9.55 | 2.19 | 8.27 | 8.70 | 0.95 |
| 1024 | 48 | 8.46 | 10.66 | 2.19 | 9.41 | 9.33 | 1.01 |
| 1024 | 64 | 9.26 | 13.05 | 2.19 | 10.83 | 10.80 | 1.00 |
| 1024 | 128 | 12.04 | 18.87 | 2.19 | 14.02 | 14.83 | 0.94 |
| 4000 | 32 | 8.46 | 13.21 | 2.19 | 11.89 | 10.52 | 1.13 |
| 4000 | 48 | 8.71 | 16.19 | 2.19 | 14.39 | 12.02 | 1.20 |
| 4000 | 64 | 9.35 | 21.83 | 2.19 | 19.28 | 14.88 | 1.30 |
| 4000 | 128 | 12.31 | 33.82 | 2.19 | 28.77 | 21.78 | 1.32 |
| 8000 | 32 | 8.61 | 18.40 | 2.18 | 16.53 | 13.02 | 1.27 |
| 8000 | 48 | 8.91 | 23.67 | 2.18 | 21.45 | 15.58 | 1.38 |
| 8000 | 64 | 9.58 | 34.32 | 2.18 | 31.49 | 20.80 | 1.51 |
| 8000 | 128 | 12.54 | 53.78 | 2.18 | 49.89 | 31.25 | 1.60 |
| 16000 | 32 | 8.78 | 27.79 | 2.17 | 26.28 | 17.46 | 1.50 |
| 16000 | 48 | 9.33 | 38.29 | 2.18 | 35.83 | 22.52 | 1.59 |
| 16000 | 64 | 9.92 | 58.14 | 2.17 | 55.08 | 31.99 | 1.72 |
| 24000 | 32 | 8.68 | 37.57 | 2.16 | 35.70 | 22.05 | 1.62 |
| 24000 | 48 | 9.31 | 52.89 | 2.16 | 50.28 | 29.48 | 1.71 |
| 32000 | 32 | 8.83 | 47.35 | 2.17 | 44.94 | 26.55 | 1.69 |

**(a) Results on 8 $\times$ L40, StreamingLLM budget for the draft model is 512, each with the optimal $\gamma$**
| Target | Draft | Prefill | Bsz | $\bf{\gamma}$ | $\bf{\gamma T_{D}(1)}$ | $\bf{T_{V}(\gamma)}$ | $\bf{\Omega(\gamma,\alpha)}$ | $\bf{T^{AR}}$ | $\bf{T^{SD}}$ | $\bf{x}$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Llama3.1-8B | Selfspec | 32000 | 32 | 3 | 44.11 | 45.12 | 3.00 | 36.62 | 30.32 | 1.21 |
| Llama2-7B | Selfspec | 8000 | 32 | 2 | 29.06 | 42.02 | 2.53 | 35.13 | 28.70 | 1.22 |
| Llama2-7B | Tinyllama1.1B | 8000 | 32 | 3 | 12.01 | 42.96 | 2.53 | 22.32 | 56.48 | 1.57 |
| Llama2-7B | Selfspec | 8000 | 64 | 3 | 58.33 | 74.85 | 3.14 | 62.92 | 42.96 | 1.46 |
| Llama2-7B | Tinyllama1.1B | 8000 | 64 | 3 | 19.66 | 74.91 | 2.51 | 62.92 | 38.33 | 1.64 |

### 5.3 Results

The main results of the experiment are summarized in Figures 5. These figures show the speedup achieved by speculative decoding at the optimal speculation length ($\gamma_{\text{optimal}}$) across various batch sizes and sequence lengths.

We can find that speculative decoding consistently outperforms autoregressive decoding except when the batch size is large and the sequence length is short. Moreover, as the sequence length increases, the speedup grows with batch size, achieving both higher throughput and lower latency. With optimal speculation lengths, SD achieves a $\bf{2}$x speedup over autoregressive decoding for \seqsplitLLaMA-2-7B-32K self-speculation at a sequence length of 32k and batch size 32, and a $\bf{1.84}$x speedup for \seqsplitLLaMA-3.1-8B at a sequence length of 100k and batch size 32.
These combinations of sequence length and batch size correspond to the maximum KV size that fits within our experimental setup as detailed in Section §5.1.

The raw values for the verification, draft, and target latencies for specific StreamingLLM budgets and $\gamma$ are reported to support our discussion (Table 1).
The results on 8 L40 and 4 H100 GPUs are also shown in Tables 2 and 2, demonstrating that speculative decoding performs well when the batch size and sequence length are large on different types of GPUs. These tables also illustrate the influence of FLOPS-to-memory bandwidth ratios of different devices on speedup.

For most cases in our experiment, the relative gain in acceptance rate for budget 1024 over budgets 256 and 512 is not a good tradeoff. However, for longer sequences, as the relative size of the target KV is the main bottleneck, a higher $\alpha$ of a higher budget can be an important factor in providing speedup, as $\Omega(\gamma,\alpha)$ is higher. Notably, our 2x speedup comes for batch size 32 and sequence length 32k for the \seqsplitLLaMA-2-7B-32K self-speculation setting for the highest StreamingLLM budget size of 1024 (Figure 6).

Based on these results, we infer the following:

- 1.
As hypothesized in §3.3, this inflection is evident in Figure 5. SD does not provide speedup with increased batch size for \seqsplitLLaMA-2-7B-32K  and \seqsplitLLaMA-3.1-8B  when $S<2000$ and $S<8000$, respectively. However, for sequences longer than these inflection points, we observe consistent improvements in speedups with higher batch sizes. These empirical values align well with the expectations on Figure 4. The factors affecting $S_{\text{inflection}}$ are discussed in detail in §3. We present the raw numbers in Tables 1 for 8 A100 GPUs.
- 2.
Conventionally, $\gamma_{\text{optimal}}$ is expected to decrease with batch size []. However, this is not universal. As shown in Figures 5 and 5, for $S>S_{\text{inflection}}$, $\gamma_{\text{optimal}}$ can increase with larger batch sizes. Similarly, an improved speedup is observed with batch size increasing in this regime.
- 3.
Based on Figure 5 for A100 and Table 2 for H100, we observe a higher speedup on the H100 device. This is because the H100 has a higher FLOPS-to-memory bandwidth ratio than the A100, leading to $T_{V}\approx T_{T}$. Additionally, the higher compute bandwidth of the H100 reduces $T_{D}$, resulting in better speedup.

## 6 Conclusion

This work reassesses the trade-off between throughput and latency in long-context scenarios. We show that *speculative decoding can enhance throughput, reduce latency, and maintain accuracy*. Our theoretical and empirical analysis reveals that as the sequence length and batch size increase, bottlenecks shift from being compute-bound to memory-bound. This shift enables effective use of speculative decoding for longer sequences, even with large batch sizes, achieving up to 2x speedup for \seqsplitLLaMA-2-7B-32K and 1.84x for \seqsplitLLaMA-3.1-8B on 8 A100 GPUs. More surprisingly, larger batches can achieve even better speedup from speculative decoding if draft models with sparse KV cache are used. These results highlight the need to integrate speculative decoding into throughput optimization systems as long-context workloads become more common.

## Appendix A Appendix

### A.1 Additional Results

Figure: (a) \seqsplitTinyLLama-1.1B
Refer to caption: x18.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 4
questions: See weakness part.
soundness: 2
strengths: 1. The writing is pretty good and easy to follow.

2. Sufficient experiments conducted on high-performance GPUs (e.g., A100, H100) show up to a 2x speedup compared to autoregressive decoding, demonstrating speculative decoding’s efficiency for long sequences.

3. The authors provide a detailed mathematical analysis showing how speculative decoding can be effective even for large batch sizes in memory-bound regimes, particularly by addressing the KV cache bottleneck.
summary: This paper introduces a speculative decoding technique designed to enhance throughput and reduce latency in long-context Large Language Models (LLMs), addressing a common bottleneck in high-batch, memory-bound inference tasks. By optimizing the Key-Value (KV) cache through sparse KV configurations and employing self-speculation, the method improves memory efficiency, making speculative decoding effective for large batch sizes and moderate-to-long sequence lengths. Empirical results on high-performance GPUs, such as A100s and H100s, show up to a 2.51x speedup compared to traditional autoregressive decoding, especially in scenarios with long sequences benchmarking. While promising, the approach lacks comparisons of some baselines, evaluating a limited spectrum of model sets, lack of case study or worse case analysis, and lacks a discussion of the scope/limitation section. If the authors could address the concerns in revision, I would be willing to raise the score.
weaknesses: 1. Missing discussion and comparisons of reasonable baselines. Although the authors briefly discuss TriForce, which demonstrates the effectiveness of self-speculation with compressed KV, they did not compare it with TriForce in experimentation for some reasons. Besides, there exists some self-speculation work aiming to accelerate LLM inference, e.g.,  Xia et al. [1] and Zhang et al. [2]. Could such existing works be applicable to / integrated with the proposed solution? Please either provide satisfactory reasons why forgiving such baselines or add comparisons in experiments and clear this work's novelty. While the paper references approaches like vLLM, it lacks a side-by-side comparison, especially regarding memory efficiency versus other batch-processing strategies. Including metrics from existing solutions in similar conditions would solidify the paper’s contributions.

[1] SWIFT: ON-THE-FLY SELF-SPECULATIVE DECODING FOR LLM INFERENCE ACCELERATION

[2] Draft & Verify: Lossless Large Language Model Acceleration via Self-Speculative Decoding

2. Evaluation of a limited spectrum of models. The experimental settings focus on LLaMA series models, yet the performance of proposed methods on other models remains unknown.

3. Lack of Case study or worse case analysis. The paper describes handling variability in token acceptance rates during speculation, but it could provide more details on failure cases or worst-case scenarios where rejection rates could impair throughput significantly. This is especially important for practical deployments in heterogeneous batches where sequence lengths vary widely.

3. Lack of discussion and limitation. Providing a brief discussion of limitations would help clear the scope of this work and make broader impacts. For instance, this work focuses on high-end modern GPUs, so the proposed solution may not perform that well on desktop/low-end GPUs, or even worse at resource-constrained embedded systems. Including tests on more widely accessible hardware (e.g., T4 or V100 GPUs) would demonstrate the method’s practical viability across a broader range of settings. The authors could elaborate more directions in the revisions.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: See above.
soundness: 3
strengths: - Interesting insights on the significant sequence length and how the nature of memory bound translates to speedups in batched speculative decoding setting.

- Insights that changing the KV drafting instead of the smaller draft models can potentially have better acceptance rate and thus better speedups.
summary: The paper discusses the batched speculative decoding in the long context scenario. It finds a critical sequence length that is the threshold for batched speculative above which it can show speedups compared to the original autoregressive decoding. The paper further examines the compressed kv cache and tries to find the best compressed KV-based drafting with the best strategy.
weaknesses: - Perhaps on the incremental side since the main new ideas are not all that large. The idea of compression KV is already in the literature.

- Perhaps the paper jump to some conclusions too fast without enough explanations, which makes it a little hard to follow.
  
  - What does Figure 1(b) try to show?

  - Maybe consider adding more details about the effects of increasing batch size with the original speculative decoding.


- Some terms are vague in the texts. Authors may consider more clearly define them.

   - What does Figure 1(b) try to show?

  - What does ``self-speculation" in the texts mean?

  -  What does KV budget mean?

- Some important design details can be more explicitly clarified.

  - Where does the time breakdown such as Figure 1(a) come from? GPU kernels can hide latency among threads so the end-to-end time does not necessarily equals to the combination of the memory loading and computing time. Nevertheless, the intuition of memory bound of KV cache when batch size is large makes sense.

  - Is KV compression used for both the draft and target model?

  - What is the baseline for results in Figure 4?

  - As for this lossy KV compression selection method, perhaps consider adding the evaluation that shows the selection in KV compression strategy has advantage (e.g., speedups) over the original speculative decoding.

  - How the framework guide the selection of KV compression method remains unclear to me.

- The applications for the very long contexts prompts in large batch size still need further justification.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: ## Questions
1. Can you clarify the potential trade-offs in performance if MagicDec were applied to significantly smaller LLM models?
2. Is the performance gain from MagicDec sustained across varying types of long-context tasks, particularly those that require variable batch sizes or non-standard hardware configurations?
3. Have you considered additional draft model selection criteria that might further alleviate the KV bottleneck?

## Comments
### Comment on Lines 52-74 and Figure 1a
In the section describing how the "KV Cache Bottleneck Enables SD Speedup Even For Large Batches," the authors assert that KV cache loading time increases significantly in long-context, large-batch scenarios, leading to a more memory-bound process. This serves as evidence for the memory bottleneck supporting speculative decoding at scale. However, Figure 1a appears to represent the combined "KV load and store" time rather than isolating the KV load time alone. Could you clarify what portion of this time is allocated to "KV store"? Understanding the distinction between load and store times would help validate the impact of the bottleneck more precisely.

### Comment on Lines 203-211 ("Expected Generation Length Per Step")
The preprint by Timor, Nadav, et al., titled *"Distributed Speculative Inference of Large Language Models"* (arXiv preprint arXiv:2405.14105, 2024), appears to be highly relevant to your study, particularly in examining the regime where SD leads to either speedups or slowdowns based on the drafting latency budget. Consider discussing this work to strengthen the related literature section.
soundness: 3
strengths: + The work introduces novel improvements in speculative decoding for large-batch, long-sequence LLMs, challenging existing assumptions and offering a fresh perspective.
+ Theoretical insights are well-validated through high-quality experimental results, with robust data supporting the effectiveness of MagicDec across diverse scenarios.
+ While some sections could benefit from increased clarity, the paper's main findings are well-articulated, with sufficient depth to support the claims.
+ MagicDec offers notable improvements in both latency and throughput for LLMs, with potential impacts across a range of long-context applications.
summary: The paper addresses the challenge of improving latency and throughput in LLM inference for long-context tasks. Traditional speculative decoding (SD) literature tends to focus on smaller batch sizes, but MagicDec demonstrates how SD can also benefit high-throughput scenarios involving long sequences. By combining theoretical and empirical approaches, MagicDec identifies and mitigates bottlenecks in memory access using a draft model with sparse Key-Value (KV) caching. It introduces a theoretical model for selecting optimal draft strategies, achieving speedups of up to 2.51x in large batch settings for the LLaMA-3.1-8B model across diverse hardware configurations.
weaknesses: - Complexity in Explanation: Sections discussing KV caching and speculative decoding speedup factors could be streamlined to improve readability, especially for a broader audience.

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: Please answer the following question.

1. **Potential limitations in real-world application**: The theoretical analysis is thorough and effectively clarifies when the conventional view—that speculative decoding (SD) enhances performance primarily with small batch sizes—applies, as well as when the new discovery on SD’s performance benefits with larger batch sizes and extended prompt lengths holds true. However, in real-world cloud environments, request configurations are often limited to smaller batch sizes and shorter prompt lengths (see https://www.microsoft.com/en-us/research/publication/splitwise-efficient-generative-llm-inference-using-phase-splitting/). Could the authors kindly discuss how this theoretical analysis might be applied within the constraints of typical LLM request configurations?
soundness: 3
strengths: 1.The paper is well-written.
2. The paper presents a clear and logical progression of ideas.
3. The paper provides rigorous theoretical analysis supported by extensive experimental results.
summary: Conventional understanding suggests that **speculative decoding (SD)** enhances performance primarily in scenarios with small batch sizes. This paper presents a novel theoretical analysis demonstrating that SD can also yield performance improvements in settings with large batch sizes and extended prompt lengths. The analysis in this paper identifies how performance bottlenecks shift with increasing batch size and prompt length. To address these bottlenecks, this paper proposes using a draft model with a compressed key-value (KV) cache, effectively alleviating the new constraints. The theoretical framework provided by this paper enables an optimal drafting strategy tailored to specific draft-target model pairs, making this approach particularly valuable for SD applications in long-context scenarios.
weaknesses: I appreciate the quality of this paper, and I have only one minor suggestion.

1. **Potential limitations in real-world application**: The theoretical analysis is thorough and effectively clarifies when the conventional view—that speculative decoding (SD) enhances performance primarily with small batch sizes—applies, as well as when the new discovery on SD’s performance benefits with larger batch sizes and extended prompt lengths holds true. However, in real-world cloud environments, request configurations are often limited to smaller batch sizes and shorter prompt lengths (see https://www.microsoft.com/en-us/research/publication/splitwise-efficient-generative-llm-inference-using-phase-splitting/). Could the authors kindly discuss how this theoretical analysis might be applied within the constraints of typical LLM request configurations?

Meta-review: (a) Summary of Scientific Claims and Findings

The paper presents MagicDec, a speculative decoding technique aimed at improving throughput and reducing latency for long-context Large Language Models (LLMs). It challenges the conventional understanding by demonstrating that speculative decoding can be effective even in high-throughput scenarios with large batch sizes and extended sequences, achieved through an optimized drafting strategy and sparse Key-Value (KV) caching.

(b) Strengths of the Paper

1. The paper challenges the traditional view that speculative decoding is only viable for small batch sizes.

2. MagicDec demonstrates compatibility with a wide range of LLMs and hardware setups.

3. It achieves notable speedup without compromising accuracy.

4. The framework is versatile, supporting multiple drafting strategies and KV compression techniques.

(c) Weaknesses of the Paper and Missing Elements

1. Initial reviews noted a lack of comparisons with related works and speculative decoding baselines (e.g., TriForce, SWIFT), along with limited evaluations on diverse LLM families and datasets (e.g., InfiniteBench). Most of these issues were addressed during the discussion phase.

2. Some sections, such as the theoretical explanation of KV caching, are overly dense and could benefit from improved clarity.

3. The paper focuses exclusively on decoding performance, leaving prefill optimization unexplored.

(d) Decision and Rationale

The paper’s strengths outweigh its weaknesses. It offers novel insights that question established beliefs about speculative decoding, provides solid experimental evidence with practical implications for LLM serving systems, and effectively addresses most reviewer concerns through constructive revisions.

Decision: Accept (Poster)