Continuous Batching & Speculative Decoding

In cloud AI serving, static request batching introduces catastrophic latency overheads: fast 10-token queries sit stranded in memory waiting for slow 1,000-token queries to finish, creating massive "inference bubbles" where GPUs burn energy transferring weights for half-empty batches.

This chapter details the two core algorithmic breakthroughs that solve this bottleneck: Continuous Batching (iteration-level scheduling) and Speculative Decoding (draft-verify acceleration).

1. The Bubble Problem in Static Batching

In traditional deep learning serving (e.g. TorchServe, Triton dynamic batching), sequences are batched at the Request Level:

Static Batch (Request Level):
Req 1 (3 tokens):   [Tok 1][Tok 2][Tok 3][PAD  ][PAD  ][PAD  ] (Trapped idle!)
Req 2 (6 tokens):   [Tok 1][Tok 2][Tok 3][Tok 4][Tok 5][Tok 6] (Finishes batch)
                       ▲                     ▲
                       │                     │
                Tokens Generated      Wasted Padding Bubbles

Because sequence lengths follow a long-tailed Pareto distribution, padding tokens consume up to 70% of execution time.

Continuous Batching (Iteration-Level Scheduling)

Introduced in the Orca paper (OSDI 2022) and popularized by vLLM, Continuous Batching operates at the granularity of individual forward pass iterations:

Iteration-Level Continuous Batching:
Step 1:  [Req A (tok 1)] [Req B (tok 1)] [Req C (tok 4)]
Step 2:  [Req A (tok 2)] [Req B (tok 2)] [Req C (tok 5)] -> Req B completes!
Step 3:  [Req A (tok 3)] [Req D (prefill)] [Req C (tok 6)] -> Req D inserted!

Whenever a sequence emits an <EOS> (end of sentence) token, its physical memory is reclaimed, and a new waiting request's prefill or decode step is immediately scheduled in the very next iteration.

2. Speculative Decoding: Overcoming the Memory Bandwidth Bottleneck

During autoregressive decoding, generating each token requires streaming every single model parameter from high-bandwidth memory (HBM) into on-chip cache. For a 70B parameter model in FP16, this means loading 140 GB across the memory bus for every single token.

Speculative Decoding (Leviathan et al., Chen et al.) overcomes this by converting memory-bandwidth bound generation into compute-bound verification:

3. Mathematical Proof: Exact Distributional Match

A common misconception is that Speculative Decoding is an approximation technique that degrades model quality. It does not. The output probability distribution is mathematically identical to sampling directly from the target model.

The Modified Rejection Sampling Algorithm

Let $p(x)$ be the probability distribution of the large target model, and $q(x)$ be the probability distribution of the small draft model.

For each candidate token $x_i$ proposed by the draft model:

1. Sample $r \sim U(0, 1)$.
2. If $r \le \min\left(1, \frac{p(x_i)}{q(x_i)}\right)$, ACCEPT $x_i$.
3. If $r > \min\left(1, \frac{p(x_i)}{q(x_i)}\right)$, REJECT $x_i$ and halt verification.
4. Resample the replacement token from the normalized positive residual distribution: $p'(x) = \frac{\max(0, p(x) - q(x))}{\sum_y \max(0, p(y) - q(y))}$

4. Tree Attention & Medusa Heads

While standard Speculative Decoding drafts a linear sequence of $K$ tokens, modern production architectures expand the draft space into a tree structure:

Linear Draft:
[Token 1] ───► [Token 2] ───► [Token 3] ───► [Token 4]

Tree Attention (Medusa / EAGLE):
                 ┌───► [Branch A: token 2a] ───► [Token 3a]
[Token 1] ───────┤
                 └───► [Branch B: token 2b] ───► [Token 3b]

Using custom Tree Attention Masks, the target model verifies multiple candidate paths simultaneously in a single forward pass, raising the average accepted tokens per step from $2.1$ to over $3.6$.

5. Python Simulation: Speculative Decoding Speedup Calculator

Run this live in-browser Python implementation to compute the expected speedup for any draft model and acceptance rate: