Speculative Decoding & Continuous Batching

Executive Summary: Modern Large Language Model (LLM) inference is fundamentally bifurcated into two compute regimes: a compute-bound prefill phase and a memory-bandwidth-bound autoregressive decoding phase. During standard token-by-token generation, state-of-the-art accelerators (such as NVIDIA H100/B200) operate at less than $1\%$ compute utilization because every single generated token requires streaming tens of gigabytes of model weights from High Bandwidth Memory (HBM) into on-chip SRAM. Speculative Decoding and Continuous Batching are the two foundational paradigms that break this physical bottleneck—transforming memory-bound matrix-vector operations into compute-dense matrix-matrix multiplications without altering the target model's output probability distribution.

---

1. The Autoregressive Memory Bandwidth Wall & Arithmetic Intensity

Core Definition: The memory bandwidth wall in autoregressive decoding occurs because generating each token requires reading the entire parameter matrix $W\in {\mathbb{R}}^{d_{in}\times d_{out}}$ from High Bandwidth Memory (HBM3) to compute a single matrix-vector multiplication ($GEMV$). Because arithmetic intensity is near unity ($I\approx 1\text{ FLOP/byte}$), GPU Tensor Cores remain idle for over $99\%$ of the execution cycle waiting for memory transfers.

To understand why serving production LLMs is computationally inefficient at low batch sizes, one must analyze the hardware physics of modern tensor processors through the lens of the Roofline Model.

1.1 The Dual Phases of Transformer Inference: Prefill vs. Decode

Every transformer sequence generation task executes across two radically distinct computational workloads:

1. Prefill Phase (Prompt Processing / Time-To-First-Token - TTFT):

   • Input: A prompt context sequence $X\in {\mathbb{R}}^{B\times S\times d}$ of length $S$.
   • Computational Nature: Compute-Bound.
   • All $S$ prompt tokens are processed simultaneously in parallel. The self-attention projection layers execute high-dimensional General Matrix Multiplications ($GEMM$): $Q=X{W}_Q,K=X{W}_K,V=X{W}_V$
   • Because weight matrices $W$ are loaded once from HBM and reused across all $S$ tokens, the operational intensity scales linearly with sequence length $S$, pushing execution directly into the peak compute plateau of the Roofline model.

2. Decode Phase (Autoregressive Token Generation / Inter-Token Latency - ITL):

   • Input: Exactly one newly sampled token $x_t\in {\mathbb{R}}^{B\times 1\times d}$ concatenated with past Key-Value ($KV$) caches.
   • Computational Nature: Strictly Memory-Bandwidth Bound.
   • Because next-token prediction is strictly autoregressive—$P(x_{t+1}\mid x_1,x_2,\dots ,x_t)$ cannot be computed until $x_t$ is sampled—the model cannot parallelize across the time dimension.
   • The matrix multiplications collapse into General Matrix-Vector products ($GEMV$): $q_t=x_t{W}_Q,k_t=x_t{W}_K,v_t=x_t{W}_V$

---

1.2 The Arithmetic Intensity Proof: Why 70B Models Starve H100 GPUs

Let us mathematically quantify the hardware starvation of single-sequence ($B=1$) autoregressive decoding for a standard Llama-3-70B architecture executing on an NVIDIA H100 SXM5.

Hardware Specifications (NVIDIA H100 SXM5):

• Peak FP16/BF16 Tensor Core Compute ($C_{peak}$): $1,979\text{ TFLOPS}=1.979\times 10^{15}\text{ FLOPs/sec}$
• High Bandwidth Memory (HBM3) Capacity: $80\text{ GB}$ (or $96\text{ GB}$ on H200)
• Peak Memory Bandwidth ($B_{mem}$): $3.35\text{ TB/s}=3.35\times 10^{12}\text{ bytes/sec}$

Machine Balance (The Roofline Knee):

The machine balance represents the exact arithmetic intensity threshold required to saturate the GPU's compute units: $I_{knee}=\frac{C_{peak}}{B_{mem}}=\frac{1.979\times 10^{15}\text{ FLOPs/sec}}{3.35\times 10^{12}\text{ bytes/sec}}\approx 590.7\text{ FLOPs/byte}$

To operate in the compute-bound regime on an H100, an algorithm must execute at least 591 floating-point operations for every single byte transferred from HBM.

Llama-3-70B Decode Arithmetic Intensity:

For a transformer with $P=70\times 10^9$ parameters stored in 16-bit precision ($\text{FP16}=2\text{ bytes/param}$):

• Memory footprint to read weights: $M_{weights}=2\times P=140\times 10^9\text{ bytes}=140\text{ GB}$
• Floating point operations to multiply weights by 1 token vector: ${\text{FLOPs}}_{decode}=2\times P=140\times 10^9\text{ FLOPs}$ (Note: Each parameter requires 1 multiply and 1 accumulate = 2 FLOPs).

Thus, the operational intensity $I_{decode}$ is: $I_{decode}=\frac{{\text{FLOPs}}_{decode}}{M_{weights}}=\frac{2P}{2P}=1.0\text{ FLOP/byte}$

Attainable Performance & Hardware Efficiency:

Since $I_{decode}=1.0\ll I_{knee}=590.7$, decoding is severely memory-bandwidth bound. The maximum attainable compute performance ($R_{attainable}$) is constrained entirely by memory throughput: $R_{attainable}=I_{decode}\times B_{mem}=1.0\text{ FLOP/byte}\times 3.35\text{ TB/s}=3.35\text{ TFLOPS}$

The resulting Tensor Core computational efficiency ($\eta$) is: $\eta =\frac{R_{attainable}}{C_{peak}}=\frac{3.35\text{ TFLOPS}}{1979\text{ TFLOPS}}\approx 0.169\%$

Key Takeaway: During single-stream autoregressive token generation on an H100, over $99.8\%$ of the GPU's computational tensor cores are completely idle, stalled waiting for parameter bytes to travel across the memory bus.

---

1.3 Minimum Theoretical Latency per Token

The minimum physical time (${\tau }_{min}$) required to generate a single token across a cluster of GPUs with aggregate bandwidth $B_{aggregate}$ is strictly bounded by the memory transfer time:

${\tau }_{min}=\frac{2P}{B_{aggregate}}+{\tau }_{KV}$

Where ${\tau }_{KV}$ is the additional time required to read the active Key-Value cache for previous context tokens: $M_{KV}=2\times n_{layers}\times 2\times d_{head}\times n_{kv\_heads}\times S\times \text{sizeof(FP16)}$

For a tensor-parallel configuration of 2x H100 GPUs ($B_{aggregate}=6.70\text{ TB/s}$) hosting a 70B model: ${\tau }_{min}\approx \frac{140\text{ GB}}{6.70\text{ TB/s}}\approx 20.89\text{ milliseconds/token}$ ${\text{Max Throughput}}_{B=1}=\frac{1}{{\tau }_{min}}\approx 47.8\text{ tokens/second}$

Regardless of algorithmic optimizations or tensor core clocks, no single-stream transformer decoding can surpass this physical barrier without altering how memory transfers occur.

---

1.4 The Paradigm Shift: Why Not Evaluate $K$ Tokens in a Single Memory Sweep?

This fundamental physical limitation establishes the core architectural thesis of Speculative Decoding:

If loading the 140 GB weight matrix from HBM into SRAM takes $\approx 20\text{ ms}$, then:

1. Evaluating 1 token against that weight matrix takes $\approx 20\text{ ms}$ (Operational Intensity $\approx 1$).
2. Evaluating $K=5$ tokens against that exact same weight matrix in a single $GEMM$ operation also takes $\approx 20\text{ ms}$ (Operational Intensity $\approx 5$).

If an auxiliary, lightweight mechanism can accurately propose $K$ candidate tokens at negligible cost, the large target model can verify all $K$ candidates in a single forward pass, unlocking multiple generated tokens per memory sweep and shattering the classical memory bandwidth barrier.

---

2. The Core Mechanics of Speculative Decoding (Draft & Verify Loop)

Core Definition: Speculative Decoding decomposes generation into a fast proposal phase and a parallel verification phase. A compact draft model ($M_{draft}$) autoregressively generates $K$ speculative tokens at low latency ($\sim 1\text{ ms/token}$). The large target model ($M_{target}$) then executes a single parallel forward pass across all $K$ tokens simultaneously, using causal masking to compute next-token probabilities for all positions in one memory sweep.

---

2.1 The Two-Model Architecture: Roles & Constraints

Speculative decoding leverages two distinct transformer instances operating in symbiosis:

Critical Constraint: The Draft Model and Target Model must share the exact same tokenizer and vocabulary space $\mathcal{V}$ (e.g., Llama-3's 128,256 Tiktoken BPE tokenizer). If token IDs do not map 1:1, logits cannot be mathematically aligned for rejection sampling without expensive re-tokenization.

---

2.2 Causal Masking in Parallel Verification

The key insight that allows the target model to verify $K$ tokens in a single forward pass without autoregressive serialization is Causal Attention Masking.

When verifying a speculative prefix $[{\tilde{x}}_1,{\tilde{x}}_2,\dots ,{\tilde{x}}_K]$ conditioned on prompt history $X=[x_1,\dots ,x_t]$:

1. The target model concatenates all $K$ candidate tokens into a single sequence input: ${\tilde{X}}_{verify}=[x_1,\dots ,x_t,{\tilde{x}}_1,{\tilde{x}}_2,\dots ,{\tilde{x}}_K]$

2. The attention mask $\mathcal{M}\in {\mathbb{R}}^{(t+K)\times (t+K)}$ is structured such that:

   • Every prompt token $x_i$ attends to all preceding prompt tokens $x_{\le i}$.
   • Candidate token ${\tilde{x}}_1$ attends to all prompt tokens $X$.
   • Candidate token ${\tilde{x}}_2$ attends to $X$ and ${\tilde{x}}_1$.
   • Candidate token ${\tilde{x}}_j$ attends to $X$ and ${\tilde{x}}_1,\dots ,{\tilde{x}}_{j-1}$.

In a single matrix multiplication pass through the target transformer's layers, the output hidden states at positions $t,t+1,\dots ,t+K-1$ produce the exact target probability distributions:

$P_{target}(x_{t+1}\mid X)$ $P_{target}(x_{t+2}\mid X,{\tilde{x}}_1)$ $P_{target}(x_{t+3}\mid X,{\tilde{x}}_1,{\tilde{x}}_2)$ $P_{target}(x_{t+4}\mid X,{\tilde{x}}_1,{\tilde{x}}_2,{\tilde{x}}_3)$

---

2.3 Mathematical Speedup Ratio & Optimal Speculative Depth ($K^{\ast }$)

Let us mathematically model the speedup ratio ($S$) of speculative decoding to determine the optimal number of speculative draft tokens ($K^{\ast }$).

Latency Variables:

• $T_{draft}$: Wall-clock time for the draft model to generate 1 token.
• $T_{target}$: Wall-clock time for the target model to execute 1 forward pass.
• $c=\frac{T_{draft}}{T_{target}}$: Relative draft latency cost ratio ($0<c\ll 1$).
• $K$: Number of speculative tokens drafted per cycle.
• $\alpha \in [0,1]$: Empirical acceptance rate per token ($\alpha =\mathbb{E}[\text{accepted tokens}]/K$).

Total Wall-Clock Time per Speculative Cycle ($T_{iter}$):

$T_{iter}=K\cdot T_{draft}+T_{target}=T_{target}\cdot (1+c\cdot K)$

Expected Number of Accepted Tokens ($E[N]$):

Assuming an independent token acceptance probability $\alpha$:

• The probability that exactly $j$ draft tokens are accepted before the first rejection is ${\alpha }^j(1-\alpha )$.
• When the first rejection occurs at index $j+1$, the verification engine samples a replacement token from the residual distribution $P_{target}^{\prime }$ at zero additional compute cost. Thus, $j+1$ tokens are emitted.
• If all $K$ tokens are accepted (probability ${\alpha }^K$), the target model still emits an additional bonus token from its $(K+1)$-th output distribution. Thus, $K+1$ tokens are emitted.

Summing the expectations yields the geometric series: $E[N]={\sum }_{j=0}^{K-1}(j+1){\alpha }^j(1-\alpha )+(K+1){\alpha }^K=\frac{1-{\alpha }^{K+1}}{1-\alpha }$

The Theoretical Speedup Ratio ($S$):

Standard autoregressive decoding would take $E[N]\times T_{target}$ to generate $E[N]$ tokens. The speculative speedup ratio $S$ is:

$S(\alpha ,c,K)=\frac{E[N]\cdot T_{target}}{T_{iter}}=\frac{1-{\alpha }^{K+1}}{(1-\alpha )(1+c\cdot K)}$

Architectural Rule of Thumb: For production LLM engines serving general code and chat (Llama-3-70B with Llama-3-8B draft, $c\approx 0.08$), setting $K\in [4,6]$ provides the maximum real-world throughput gain while avoiding speculative overhead on hard reasoning tasks.

---

3. The Mathematics of Modified Rejection Sampling

Core Definition: Modified Rejection Sampling is the mathematical core of speculative decoding that guarantees zero quality degradation. It provably ensures that the probability distribution of every emitted token strictly equals the target model's output distribution $P_{target}(x)$ by accepting draft tokens with probability $\alpha =\min \left(1,\frac{P_{target}(x)}{P_{draft}(x)}\right)$ and resampling rejected positions from a normalized residual probability distribution $P_{target}^{\prime }(x)\propto \max (0,P_{target}(x)-P_{draft}(x))$.

A critical question engineers ask when adopting speculative decoding is: Does using a smaller 8B model to draft tokens degrade the reasoning capability, factual accuracy, or stylistic nuances of the 70B target model?

The answer is an unequivocal no. Speculative decoding is not an approximation algorithm—it is mathematically exact.

---

3.1 The Distribution Invariance Theorem

Let $\mathcal{V}$ be the shared vocabulary space. For a given context prefix $X$:

• Let $q(x)=P_{draft}(x\mid X)$ denote the probability vector predicted by the draft model.
• Let $p(x)=P_{target}(x\mid X)$ denote the probability vector predicted by the target model.

Theorem (Distributional Equivalence):
Let a candidate token $\tilde{x}\sim q(x)$ be drawn from the draft model. If $\tilde{x}$ is accepted with probability: $\beta (\tilde{x})=\min \left(1,\frac{p(\tilde{x})}{q(\tilde{x})}\right)$ and upon rejection, a replacement token $x^{\prime }$ is drawn from the normalized residual distribution: $p^{\prime }(x)=\frac{\max (0,p(x)-q(x))}{{\sum }_{y\in \mathcal{V}}\max (0,p(y)-q(y))}$

Then the marginal distribution of the emitted token $x_{emitted}$ satisfies: $P(x_{emitted}=x)=p(x)=P_{target}(x\mid X)\forall x\in \mathcal{V}$

---

3.2 Formal Step-by-Step Proof of Equivalence

To prove this theorem, we evaluate the law of total probability across both mutually exclusive outcomes: acceptance and rejection.

$P(x_{emitted}=x)=P(\text{Accepted}\wedge \tilde{x}=x)+P(\text{Rejected}\wedge x^{\prime }=x)$

Step 1: Probability of Token $x$ Being Drafted and Accepted

The probability that token $x$ is initially proposed by the draft model is $q(x)$. Given that $\tilde{x}=x$ was proposed, the probability of acceptance is $\beta (x)=\min \left(1,\frac{p(x)}{q(x)}\right)$.

Therefore, the joint probability is: $P(\text{Accepted}\wedge \tilde{x}=x)=q(x)\cdot \min \left(1,\frac{p(x)}{q(x)}\right)=\min (p(x),q(x))$

Step 2: Total Acceptance Rate Across All Vocabulary ($\alpha$)

The total probability that any proposed token is accepted ($\alpha$) is the sum over all vocabulary elements: $\alpha ={\sum }_{x\in \mathcal{V}}P(\text{Accepted}\wedge \tilde{x}=x)={\sum }_{x\in \mathcal{V}}\min (p(x),q(x))$

Step 3: Total Rejection Probability and Normalization Constant

The probability of rejection is simply the complement of acceptance: $P(\text{Rejected})=1-\alpha =1-{\sum }_{x\in \mathcal{V}}\min (p(x),q(x))$

Using the identity $p(x)-\min (p(x),q(x))=\max (0,p(x)-q(x))$ and the fact that ${\sum }_{x\in \mathcal{V}}p(x)=1$: $1-\alpha ={\sum }_{x\in \mathcal{V}}p(x)-{\sum }_{x\in \mathcal{V}}\min (p(x),q(x))={\sum }_{x\in \mathcal{V}}\max (0,p(x)-q(x))$

This confirms that the denominator of the residual distribution $p^{\prime }(x)$ is exactly equal to the total rejection probability $(1-\alpha )$: $p^{\prime }(x)=\frac{\max (0,p(x)-q(x))}{1-\alpha }$

Step 4: Probability of Token $x$ Being Sampled via the Residual Distribution

If the proposed token is rejected (which occurs with probability $1-\alpha$), the verifier samples a new token $x^{\prime }$ from $p^{\prime }(x)$: $P(\text{Rejected}\wedge x^{\prime }=x)=P(\text{Rejected})\cdot p^{\prime }(x)=(1-\alpha )\cdot \left[\frac{\max (0,p(x)-q(x))}{1-\alpha }\right]=\max (0,p(x)-q(x))$

Step 5: Combining Accepted and Resampled Probabilities

Summing the two probabilities: $P(x_{emitted}=x)=\min (p(x),q(x))+\max (0,p(x)-q(x))$

For any real numbers $a,b$: $\min (a,b)+\max (0,a-b)=a$

Substituting $a=p(x)$ and $b=q(x)$: $P(x_{emitted}=x)=p(x)\equiv P_{target}(x\mid X)\forall x\in \mathcal{V}$

$■\text{Q.E.D.}$

---

3.3 Concrete Numerical Walkthrough

Consider a simplified vocabulary of 4 tokens $\mathcal{V}=\{A,B,C,D\}$ with the following probability distributions from $M_{draft}$ and $M_{target}$:

Execution Scenarios:

1. If Draft proposes Token A ($\tilde{x}=A$):
   • Acceptance ratio: $\frac{p(A)}{q(A)}=\frac{0.20}{0.60}=\frac{1}{3}\approx 33.3\%$.
   • Roll random number $r\in [0,1)$. If $r\le 0.333$, emit A.
   • If $r>0.333$, reject A and sample from $p^{\prime }(x)$: $75\%$ chance of emitting B, $25\%$ chance of emitting C.
2. If Draft proposes Token B ($\tilde{x}=B$):
   • Acceptance ratio: $\frac{p(B)}{q(B)}=\frac{0.50}{0.20}=2.5\ge 1.0$.
   • Token B is accepted with $100\%$ certainty ($\beta (B)=1.0$).

---

3.4 Temperature, Top-$p$ (Nucleus), and Top-$k$ Invariance

In production LLM serving, temperature scaling ($\tau$) and nucleus truncation ($\text{Top-}p$) are applied dynamically:

1. Temperature Scaling ($\tau >0$):

   • Logits are scaled prior to Softmax: $p(x)=\text{softmax}(z_{target}/\tau )$ and $q(x)=\text{softmax}(z_{draft}/\tau )$.
   • Because temperature scaling is applied before computing probabilities, the rejection sampling theorem holds identically for any arbitrary temperature $\tau$.
   • When $\tau \to 0$ (Greedy Decoding), the sampling collapses into deterministic equality: accept if $\text{argmax}(p)=\text{argmax}(q)$, otherwise emit $\text{argmax}(p)$.

2. Top-$p$ (Nucleus) Truncation:

   • Truncate both $p(x)$ and $q(x)$ to their respective nucleus subsets ${\mathcal{V}}_p$ and ${\mathcal{V}}_q$.
   • Normalize probabilities within the active subsets before passing vectors into the rejection sampler. This guarantees exact distributional matching under truncated probability spaces.

---

4. Advanced Architectures: Medusa Heads & EAGLE Tree-Attention

Core Definition: Advanced speculative decoding architectures eliminate the memory overhead and communication bottlenecks of auxiliary draft models by using single-model multi-head extensions (Medusa) or feature-level recurrence (EAGLE). By replacing linear token sequences with non-linear Tree Attention, these systems evaluate multiple branching token hypotheses in parallel during a single target forward pass—achieving up to $3.5\times$ speedups without hosting a secondary model in VRAM.

While classical two-model speculative decoding (Leviathan et al.) delivers substantial speedups, it introduces several severe production challenges in enterprise serving environments:

1. VRAM Footprint & Memory Fragmentation: Hosting an auxiliary 8B draft model alongside a 70B target model consumes an additional $16\text{ GB}$ of GPU memory in FP16, directly cannibalizing memory that could otherwise serve KV cache for hundreds of concurrent user sessions.
2. Inter-Model KV Cache Synchronization: Operating two separate models requires maintaining two independent KV caches and synchronizing their context states across GPUs over PCIe or NVLink buses, introducing non-trivial scheduling jitter.
3. Linear Chain Fragility: If the draft model errs on token index $1$, the remaining $K-1$ candidate tokens are completely discarded, wasting draft computation.

To solve these bottlenecks, modern LLM engines deploy single-model draft heads and Tree Attention verification.

---

4.1 Medusa: Draft-Model-Free Speculative Decoding

Introduced by Cai et al. (2024), Medusa eliminates the auxiliary draft model entirely. Instead of running a secondary transformer, Medusa attaches $M$ lightweight feed-forward neural network heads (termed Medusa Heads) directly to the final hidden state of the frozen base transformer.

Mathematical Formulation:

Let $h_t\in {\mathbb{R}}^d$ be the output hidden state of the base model's final transformer block at position $t$.

• The standard language model head predicts the next token distribution: $P(x_{t+1}\mid x_{\le t})=\text{softmax}(W_{LM}\cdot h_t)$
• Medusa head $k\in \{1,2,\dots ,M\}$ predicts the token distribution at offset $t+k+1$: $P(x_{t+k+1}\mid x_{\le t})=\text{softmax}(W_k\cdot \text{SiLU}(W_{proj}\cdot h_t+h_t))$

Each Medusa head consists of a single residual block: a linear projection down-scaled with a $\text{SiLU}$ activation function and a skip connection, followed by the language model projection matrix $W_k$.

Training Objective:

During training, the base model weights $W_{base}$ are kept completely frozen. Only the parameters of the $M$ Medusa heads are optimized using standard cross-entropy loss across next-token ground-truth targets from a generic instruction dataset (e.g. ShareGPT):

${\mathcal{L}}_{Medusa}={\sum }_{k=1}^M-\log P\left(x_{t+k+1}\mid x_{\le t};W_k\right)$

Because the base model is frozen and heads are non-recurrent, training takes just a few hours on a single GPU node and consumes zero additional inference memory for auxiliary transformer layers.

---

4.2 Non-Linear Tree Attention: Verifying Branching Hypotheses

In linear speculative decoding, the draft engine proposes a single sequence $[{\tilde{x}}_1,{\tilde{x}}_2,{\tilde{x}}_3]$. If the target model rejects ${\tilde{x}}_1$, tokens ${\tilde{x}}_2$ and ${\tilde{x}}_3$ are completely invalidated, resulting in an effective acceptance length of $1$.

Medusa and modern speculative engines solve this through Tree-Structured Speculative Decoding. Instead of a single chain, the heads generate top-$k$ predictions that branch into a tree of $N$ candidate paths.

Constructing the 2D Tree Attention Mask:

To verify this entire branching tree in a single forward pass without cross-branch contamination, the attention mask is structured according to the tree's ancestral hierarchy:

${\mathcal{M}}_{tree}(i,j)=\{\begin{array}{ll}1& \text{if candidate }j\text{ is an ancestor of candidate }i\text{ or }j=i\\ 0& \text{otherwise}\end{array}$

Shared Positional Embeddings:

A critical innovation in Tree Attention is the handling of positional encodings. Sibling nodes in the tree share the exact same positional index corresponding to their depth in the tree:

$\text{pos}(B_1)=\text{pos}(B_2)=\text{pos}(Root)+1$ $\text{pos}(B_{1,1})=\text{pos}(B_{1,2})=\text{pos}(B_{2,1})=\text{pos}(B_{2,2})=\text{pos}(Root)+2$

Because attention masking strictly prevents cross-talk between sibling branches, the target model computes the exact next-token logits for all independent candidate paths concurrently in a single GPU kernel execution!

---

4.3 EAGLE: Feature-Level Speculative Sampling

While Medusa uses simple independent MLP heads, EAGLE (Extrapolation Algorithm for Greater Language-model Efficiency, Li et al., 2024) addresses the fundamental limitation of multi-head drafting: loss of contextual dependencies.

Medusa heads predict tokens independently from the base hidden state $h_t$, meaning Head 3 has no awareness of what Head 1 and Head 2 chose. In complex logical reasoning, this causes speculative accuracy to degrade rapidly beyond offset 2.

The EAGLE Innovation:

Instead of drafting in discrete token space, EAGLE drafts in continuous feature space:

1. It passes the top-layer hidden state $h_t$ from the target model along with the embedding vector $e(x_t)$ of the current token into a single lightweight transformer decoder layer.
2. The decoder layer predicts the next top-layer hidden state ${\tilde{h}}_{t+1}$.
3. The base model's original language model head $W_{LM}$ projects ${\tilde{h}}_{t+1}$ into token logits, sampling candidate token ${\tilde{x}}_{t+1}$.
4. The predicted feature ${\tilde{h}}_{t+1}$ and embedding $e({\tilde{x}}_{t+1})$ are fed recurrently back into the single decoder layer to generate ${\tilde{h}}_{t+2},{\tilde{h}}_{t+3}$, and so on.

Because EAGLE operates with full autoregressive feature recurrence in its lightweight single-layer decoder, it achieves an acceptance rate of $\alpha \approx 0.80-0.90$, delivering $2.8\times -3.5\times$ wall-clock speedup across challenging code and reasoning benchmarks (GSM8K, HumanEval).

---

4.4 Speculative Architecture Comparison Matrix

---

5. Continuous Batching, PagedAttention & Memory Management

Core Definition: Continuous Batching (iteration-level scheduling) and PagedAttention (virtual memory KV-cache allocation) are the dual systems innovations in modern serving engines (e.g. vLLM, TensorRT-LLM) that maximize GPU throughput. Continuous batching evicts completed sequences and schedules new requests at every individual token step, while PagedAttention stores non-contiguous KV-cache tensors in fixed-size memory blocks—eliminating over $96\%$ of GPU memory fragmentation and increasing concurrency by $4\times -8\times$.

While Speculative Decoding optimizes latency for a single sequence ($B=1$), high-scale inference systems must simultaneously maximize throughput across hundreds of concurrent user requests ($B\gg 1$).

At scale, the primary bottleneck transitions from weight bandwidth to Key-Value ($KV$) Cache Memory Capacity.

---

5.1 The Failure of Static Request-Level Batching

In classical deep learning serving (e.g. vision or BERT models), inference engines utilize Static Batching: a fixed batch of $B$ requests is grouped together, padded to the longest sequence length $L_{max}$, and executed synchronously across all forward passes until the entire batch finishes.

In Large Language Models, static batching causes catastrophic inefficiencies due to high variance in generation lengths:

The Inefficiencies of Static Batching:

1. Padding Waste: Sequences must be padded with <pad> tokens to match the longest sequence in the batch. The GPU executes full attention and feed-forward computations on meaningless padding tokens.
2. Early Completion Stalls: When a short request emits <|endoftext|> after 15 tokens, its allocated memory and GPU compute slot remain locked until the longest request (e.g. 1,000 tokens) finishes.
3. Queue Head-of-Line Blocking: New requests arriving at time $t=10$ must wait in an external HTTP queue until the entire current static batch completes at $t=1000$.

---

5.2 Continuous Batching: Iteration-Level Scheduling (Orca)

Pioneered by Yu et al. (Orca, OSDI 2022), Continuous Batching (also called cellular or iteration-level scheduling) completely decouples batch management from individual request lifecycles.

Instead of managing batches at the coarse granularity of entire requests, the inference engine operates an iteration-level scheduler that executes at every single token step:

Execution Mechanics:

• Immediate Eviction: As soon as a request emits an end-of-sequence token, its slot in the batch is immediately freed, and its KV cache memory is returned to the memory pool.
• Dynamic Admission: New requests are admitted into the running batch on the very next token iteration without waiting for existing requests to complete.
• Chunked Prefills (Sarathi-Serve / vLLM): Long prompt prefill requests are chunked (e.g. 512 tokens per chunk) and piggybacked alongside active decoding steps in a single unified GEMM forward pass, eliminating Time-To-First-Token (TTFT) latency spikes while maintaining high decode throughput.

---

5.3 The KV Cache Memory Crisis: Exact Arithmetic

During autoregressive decoding, every token generated across every active request must store its Key ($K$) and Value ($V$) activation vectors across all transformer layers to avoid recomputing attention history.

Let us quantify the KV cache memory footprint for Llama-3-70B with Grouped-Query Attention (GQA):

Model Architecture Parameters:

• Number of Layers ($n_{layers}$): $80$
• Hidden Dimension ($d_{model}$): $8,192$
• Number of Query Heads ($n_q$): $64$ ($d_{head}=128$)
• Number of Key/Value Heads ($n_{kv}$): $8$ (Grouped-Query Attention with 8 groups)
• Data Precision: $\text{FP16}$ ($2\text{ bytes/element}$)

KV Cache Size per Single Token:

For each token at each layer, the model stores one Key vector ($d_{head}\times n_{kv}$) and one Value vector ($d_{head}\times n_{kv}$):

$\text{KV Bytes per Token}=2\times n_{layers}\times (n_{kv}\times d_{head})\times \text{sizeof(FP16)}$ $\text{KV Bytes per Token}=2\times 80\times (8\times 128)\times 2\text{ bytes}=327,680\text{ bytes}=327.68\text{ KB/token}$

Total Memory Impact Across Batch Sizes and Context Lengths:

On an 8x H100 GPU cluster ($640\text{ GB}$ total HBM3), model weights consume $140\text{ GB}$, leaving $\approx 500\text{ GB}$ for KV cache. Memory allocation strategy dictates whether the cluster serves 30 users or 300 users simultaneously.

---

5.4 PagedAttention: OS Virtual Paging for Tensors

In traditional serving frameworks (e.g. HuggingFace Accelerate, FasterTransformer), KV caches were allocated as contiguous tensor buffers sized for the maximum potential request length $L_{max}$ (e.g. 4,096 tokens).

This caused severe memory waste through two forms of fragmentation:

1. Internal Fragmentation: Reserving 4,096 tokens of contiguous VRAM for a request that terminates after 150 tokens wastes $96.3\%$ of the allocated buffer.
2. External Fragmentation: Over time, as requests of arbitrary lengths allocate and free contiguous chunks, the GPU memory space becomes fragmented into non-contiguous gaps, causing Out-Of-Memory (OOM) errors even when $40\%$ of total VRAM is free.

PagedAttention (Kwon et al., SOSP 2023 / vLLM) solves this by adapting the classical Operating System Virtual Memory Page Table architecture directly to GPU tensors:

Architectural Components:

1. Fixed-Size Physical Blocks: Physical GPU VRAM is partitioned into fixed-size memory blocks (typically holding $B_{size}=16$ or $32$ tokens of KV data).
2. Logical Blocks: A request's context sequence is dynamically chunked into logical blocks of size $B_{size}$.
3. Block Table (Page Table): A metadata table on the host CPU/GPU maps each logical block index to an arbitrary, non-contiguous physical block address in GPU HBM.
4. On-Demand Allocation: As a request generates new tokens:
   • Tokens are written into the current physical block.
   • Only when the block is completely full (e.g. token 16 arrives) does the engine allocate a single new physical block from the free pool.

Memory Efficiency Gains:

• Near-Zero Internal Fragmentation: Internal memory waste is strictly bounded to the unused slots in the final block of a sequence ($<B_{size}$ tokens, or $<5\text{ MB}$ per request).
• Zero External Fragmentation: All physical blocks are identical in size ($16$ tokens). Any freed block can instantly satisfy any allocation request from any user session.
• Overall VRAM Waste: Reduced from $60\%-80\%$ under static contiguous allocation down to $<4\%$ under PagedAttention, allowing vLLM to achieve $4\times -8\times$ higher concurrent batch capacity.

---

5.5 Copy-on-Write (CoW) for Parallel Sampling & Multi-Turn Chat

Beyond basic allocation, PagedAttention unlocks Copy-on-Write (CoW) memory sharing for advanced LLM generation patterns:

2. Multi-Turn System Prompts & Prefix Caching:
   • Static system instructions (e.g. a 2,000-token enterprise system prompt or PDF context) are computed once, stored in physical blocks, and shared across thousands of incoming user requests via prefix hashing.

---

6. Production Reference Implementation & Serving Benchmarks

Core Definition: A production-grade speculative inference engine orchestrates three synchronized subroutines: fast autoregressive proposal via the draft model, single-pass tensor-parallel verification via the target model, and vector-accelerated rejection sampling. By integrating these components into high-throughput serving engines like vLLM and TensorRT-LLM, production deployments achieve $2.5\times -3.2\times$ lower inter-token latency across standard enterprise workloads.

---

6.1 Complete Python / PyTorch Speculative Sampling Engine

Below is a complete, standalone Python/PyTorch reference implementation demonstrating the exact draft-propose, target-verify, and modified rejection sampling loop:

---

6.2 Production Deployment: vLLM & TensorRT-LLM CLI Parameters

In production environments, Speculative Decoding and Continuous Batching are enabled with optimized memory and tensor parallel settings:

vLLM Speculative Serving Command:

Key Production Configuration Flags:

• --num-speculative-tokens 5: Sets speculative depth $K=5$, providing optimal latency across code and conversational workloads.
• --enable-chunked-prefill: Splits prompt prefill into chunks of $2,048$ tokens to prevent Time-To-First-Token (TTFT) spikes from stalling active decoding streams.
• --gpu-memory-utilization 0.95: Allocates $95\%$ of remaining VRAM directly to PagedAttention KV-cache pools.

---

6.3 Comprehensive Benchmark Results Across Workloads

The following empirical benchmarks were recorded on an NVIDIA 4x H100 SXM5 (80GB) cluster comparing standard autoregressive decoding against Speculative Decoding ($K=5$) and EAGLE-2:

---

7. People Also Ask (PAA) & Enterprise FAQ

Why is speculative decoding faster if it runs two models instead of one?

Direct Answer: Speculative decoding is faster because LLM inference is strictly memory-bandwidth bound rather than compute bound. The small draft model generates candidate tokens rapidly at tiny memory transfer cost ($\sim 1\text{ ms}$), and the large target model verifies all $K$ candidate tokens simultaneously in a single parallel matrix-matrix forward pass ($GEMM$). Because evaluating $K$ tokens in parallel takes nearly the same time as evaluating 1 token ($\sim 20\text{ ms}$), the engine emits $2\times -3\times$ more tokens per memory sweep.

Does speculative decoding alter or degrade model quality?

Direct Answer: No. Modified Rejection Sampling provides a formal mathematical guarantee that the output probability distribution of every emitted token strictly equals the target model's output distribution ($P_{target}(x)$). Factual accuracy, perplexity, and reasoning benchmarks remain $100\%$ identical.

What is the difference between Speculative Decoding and Medusa?

Direct Answer: Classical speculative decoding requires running a separate, smaller language model (e.g. Llama-3-8B) as an auxiliary draft model in VRAM. Medusa eliminates the auxiliary model by training multiple lightweight residual MLP heads directly on the target model's final hidden state, verifying branching candidate token trees via 2D Tree Attention without consuming extra VRAM for a secondary transformer.

How does PagedAttention prevent GPU Out-Of-Memory (OOM) errors?

Direct Answer: PagedAttention adapts OS virtual memory page tables to GPU memory allocation. Instead of reserving large, contiguous memory buffers for maximum sequence lengths, PagedAttention dynamically allocates non-contiguous physical blocks of 16 tokens as needed. This eliminates internal and external memory fragmentation, reducing VRAM waste from $80\%$ to under $4\%$.

When does speculative decoding slow down inference?

Direct Answer: Speculative decoding can cause a throughput regression under two conditions: (1) When the system is operating at maximum batch saturation (compute-bound regime with hundreds of concurrent users), where GPU compute is fully saturated and cannot spare FLOPs for parallel verification; and (2) When the draft model acceptance rate falls below $\alpha <40\%$ (e.g. highly chaotic or cryptographic outputs), where rejection overhead outweighs verification gains.

---

8. Summary & Systems Engineering Takeaways

Key Engineering Takeaways:

1. Arithmetic Intensity Dictates Serving Strategy: Single-sequence latency is optimized via Speculative Decoding (converting $GEMV\to GEMM$). Multi-user throughput is optimized via Continuous Batching and PagedAttention.
2. Deterministic Quality Preservation: Speculative decoding is not a distillation or quantization compromise—it is a mathematically lossless algorithmic acceleration technique.
3. Hardware-Co-Designed Serving: Modern inference engines (vLLM, TensorRT-LLM, SGLang) achieve state-of-the-art throughput by co-designing GPU memory hierarchies with virtual page tables and chunked prefill schedulers.

---