Continuous Batching and Speculative Decoding

"They told me to wait for the slowest request in my batch. I waited. The sun set. The slowest request was generating a sonnet."

A GPU Slot Held Hostage by the Longest Sequence

The previous sections of this chapter made each token cheaper: Section 22.5 paged the KV cache so more sequences fit in memory, and Section 22.6 made the attention kernel itself read fewer bytes. Those wins are real, but they assume the GPU is actually busy. For large-language-model serving that assumption is usually false, because generation is sequential and requests are uneven. This section attacks the two largest sources of idle silicon directly. The first is scheduling waste: a batch that must wait for its slowest member. The second is the sequential nature of decoding itself: a forward pass that produces only one token while the hardware could have produced several. Neither technique changes what the model outputs; both change how fast it gets there.

1. Prefill and Decode Are Two Different Workloads Beginner

Serving one request to a transformer splits into two phases with opposite hardware characters. The prefill phase processes the entire prompt at once: every prompt token attends to every earlier token in a single large matrix multiplication, so prefill is compute-bound, the kind of dense arithmetic a GPU loves. The decode phase then generates the answer one token at a time; each new token requires a forward pass that reads the whole model's weights and the growing KV cache just to produce a single vector. That per-token pass moves a great deal of memory for very little arithmetic, so decode is memory-bandwidth-bound and leaves the compute units mostly idle. A request is therefore a short compute-heavy burst followed by a long memory-heavy trickle, and the trickle is where serving systems spend most of their time.

This asymmetry is the root cause of both techniques in this section. Continuous batching exists because the memory-bound decode phase has spare compute to absorb other requests, so you should keep as many sequences decoding together as memory allows. Speculative decoding exists because a single decode pass is so memory-bound that verifying several proposed tokens costs almost the same as generating one, so you should make each expensive pass do more work. A third optimization, chunked prefill, follows from the same observation: a long prompt's compute-bound prefill can starve the latency-sensitive decode steps of other requests, so serving engines split a large prefill into smaller chunks and interleave them with ongoing decode, smoothing the latency of every request sharing the GPU.

2. Static Batching Wastes the GPU on the Longest Sequence Beginner

Generic model servers batch requests to amortize the cost of a forward pass, a practice Chapter 23 treats as dynamic batching: the server waits a few milliseconds, collects whatever requests arrive, runs them as one batch, and returns all the results together. That works beautifully when every request does the same amount of work, as in image classification, where each input takes exactly one forward pass. It fails for text generation, because the requests in a batch finish at wildly different times. One user asks for a yes-or-no answer (eight tokens) while another asks for an essay (two hundred tokens), yet a static batch cannot return the short answer until the whole batch is done. Until then the short request's slot sits occupied but idle, a bubble of wasted GPU, and no new request can take its place.

Continuous batching, also called in-flight batching, removes the bubble by operating at the token level rather than the request level. After every decode step the scheduler checks which sequences have emitted their end-of-sequence token, evicts them from the running batch, frees their KV-cache pages, and admits waiting requests into the freed slots, all before the next step. The batch is thus never the same from one step to the next; it is a continuously refreshed set of whatever sequences are currently live. The short request leaves the instant it finishes and a new one begins immediately, so the GPU stays full instead of waiting for the essay. Figure 22.7.1 contrasts the two schedules, and the simulation that follows measures the difference.

The simulation in Code 22.7.1 models both schedules in pure Python. It draws two hundred requests with decode lengths between eight and two hundred tokens, runs them through eight GPU slots under each policy, and reports utilization (the fraction of slot-time that did real work) and throughput (inverse of the total ticks taken). The static scheme pads each batch to its longest member; the continuous scheme refills a slot the moment its request finishes.

import random
random.seed(7)

B = 8                  # number of parallel slots on the GPU
N_REQUESTS = 200       # total requests to serve
out_lens = [random.randint(8, 200) for _ in range(N_REQUESTS)]  # decode lengths

def simulate_static(out_lens, B):
    useful, total, i = 0, 0, 0
    while i < len(out_lens):
        batch = out_lens[i:i + B]
        longest = max(batch)        # every slot is held until the longest finishes
        total += B * longest        # all B slots occupied for `longest` ticks
        useful += sum(batch)        # but each slot only worked for its own length
        i += B
    return useful, total

def simulate_continuous(out_lens, B):
    useful, total = 0, 0
    queue = list(out_lens)
    slots = [queue.pop(0) if queue else 0 for _ in range(B)]
    while any(s > 0 for s in slots) or queue:
        active = sum(1 for s in slots if s > 0)
        total += B                  # all B slots are available this tick
        useful += active            # only the active ones did work this tick
        for k in range(B):
            if slots[k] > 0:
                slots[k] -= 1
            if slots[k] == 0 and queue:     # finished -> refill immediately
                slots[k] = queue.pop(0)
    return useful, total

us_u, us_t = simulate_static(out_lens, B)
co_u, co_t = simulate_continuous(out_lens, B)
print(f"static   util : {100*us_u/us_t:5.1f}%   makespan ticks: {us_t//B}")
print(f"continuous util: {100*co_u/co_t:5.1f}%   makespan ticks: {co_t//B}")
print(f"throughput gain: {us_t/co_t:4.2f}x  (continuous vs static)")

static   util :  60.0%   makespan ticks: 4334
continuous util:  96.6%   makespan ticks: 2691
throughput gain: 1.61x  (continuous vs static)

The numbers in Output 22.7.1 are the whole argument for continuous batching. Identical work, identical model, identical outputs, yet the in-flight scheduler delivers about 1.6 times the throughput on this length distribution simply by never letting a slot idle behind a longer sequence. Real engines see larger gains when the length spread is wider, which is the common case for chat and code workloads. Continuous batching is the default in every modern serving engine for exactly this reason.

# pip install vllm
from vllm import LLM, SamplingParams

llm = LLM(model="meta-llama/Llama-3.1-8B-Instruct",
          max_num_seqs=256)        # up to 256 sequences batched in flight at once
params = SamplingParams(max_tokens=200)

# Hand the engine a whole queue; it admits, evicts, and refills slots per token,
# overlapping short and long requests automatically. No manual scheduling.
outputs = llm.generate(prompts, params)

3. Speculative Decoding Turns Sequential Work Into Parallel Work Intermediate

Continuous batching fills the GPU across requests; speculative decoding attacks the sequential cost within a single request. Decoding is slow because it is inherently serial: token $t+1$ cannot be computed until token $t$ exists, so a length-$L$ answer needs $L$ memory-bound forward passes of the large model. Speculative decoding breaks that chain with a division of labor. A small, cheap draft model generates a guess of the next $k$ tokens quickly. The large target model then runs a single forward pass over the prompt plus all $k$ proposed tokens at once, which a transformer can do in parallel because it scores every position simultaneously. Comparing the target's own distribution at each position to the draft's proposal, the system accepts the longest prefix the target agrees with and resamples the first disagreement from a corrected distribution.

The decisive property is that this procedure is exact: with the standard rejection-sampling acceptance rule, the accepted tokens are distributed exactly as if they had been sampled from the target model alone. Speculative decoding changes the speed of generation and nothing about its output distribution. The win comes from arithmetic intensity. One target forward pass is so memory-bound that processing $k+1$ positions costs almost the same wall-clock time as processing one, so every accepted draft token is a target pass avoided. If the draft and target agree on a fraction $a$ of tokens, a single verification pass yields, in expectation,

the mean of a truncated geometric run of agreements plus one bonus token that the target supplies for free at the end of the accepted prefix. Writing $T$ for the latency of one target forward pass and $D \ll T$ for one draft pass, the expected speedup over plain decoding is

The numerator rewards a high acceptance rate; the denominator charges for the $k$ draft passes that may be wasted if the target rejects early. Code 22.7.3 evaluates this expression across acceptance rates for a draft that is about seven times cheaper than the target.

def expected_speedup(a, k, T, D):
    accepted = (1 - a ** (k + 1)) / (1 - a)   # mean tokens per verification pass
    cost = T + k * D                          # 1 target pass + k draft passes
    return accepted * T / cost                # baseline cost per token is T

T, D, k = 1.0, 0.15, 4                         # target=1.0, draft=0.15, propose 4
for a in (0.5, 0.7, 0.8, 0.9):
    acc = (1 - a ** (k + 1)) / (1 - a)
    print(f"accept rate a={a:.1f} : mean accepted/pass = {acc:4.2f}"
          f"  ->  {expected_speedup(a, k, T, D):4.2f}x speedup")

accept rate a=0.5 : mean accepted/pass = 1.94  ->  1.21x speedup
accept rate a=0.7 : mean accepted/pass = 2.77  ->  1.73x speedup
accept rate a=0.8 : mean accepted/pass = 3.36  ->  2.10x speedup
accept rate a=0.9 : mean accepted/pass = 4.10  ->  2.56x speedup

Output 22.7.3 explains why speculative decoding lives or dies on the acceptance rate. A draft model that mirrors the target closely turns four memory-bound target passes into one and yields better than a 2.5x speedup; a weak draft spends its budget on guesses the target throws away and the verification overhead eats most of the gain. The engineering problem is therefore to make the draft both cheap and well-aligned, which is exactly where the recent variants compete.

4. The Variants: Better Drafts, Fewer Passes Advanced

The original formulation uses a separate small model as the draft, which works but requires shipping and serving a second model whose distribution must track the target. A family of variants removes that cost by drawing the draft from the target model itself. Medusa attaches a handful of extra prediction heads to the target so it proposes several future tokens in one pass with no separate model. EAGLE drafts at the feature level rather than the token level, predicting the target's own hidden states to raise the acceptance rate, and its successors push that idea further. Self-speculation uses a subset of the target's own layers as the draft, so a single set of weights both proposes and verifies. The simplest variant of all, n-gram or prompt-lookup decoding, skips a neural draft entirely and proposes tokens by copying repeated spans from the prompt, which is remarkably effective for summarization and code editing where the output echoes the input.

All of these are single-GPU mechanisms: the draft, the verification, and the acceptance test happen inside one accelerator's forward passes. They compose cleanly with continuous batching, since a verified multi-token step is just a different kind of step in the in-flight schedule, and with the paged KV cache of Section 22.5, since accepted tokens extend the cache while rejected ones are simply not committed. What none of them do by themselves is coordinate across machines. Deciding which replica drafts, how a speculative step interacts with cross-node scheduling, and when to disaggregate prefill from decode are fleet-level questions answered by the distributed serving scheduler of Chapter 24, which treats the per-node throughput this section creates as the unit it replicates and load-balances.

5. When These Techniques Earn Their Keep Intermediate

Neither technique is universally free. Continuous batching needs a length spread to exploit; a workload where every request emits the same number of tokens (fixed-length classification or scoring) gets little from it, because there are no early finishers to evict. It also raises memory pressure, since more sequences decode concurrently and each holds a KV cache, which is precisely why it is built on top of the paged cache of Section 22.5 rather than alongside it. Speculative decoding helps most when decoding is the bottleneck and the batch is small, the latency-sensitive regime; at very large batch sizes the GPU is already compute-saturated by the batch itself, the spare compute that speculation feeds on is gone, and the extra draft passes can even slow things down. A negative acceptance rate scenario, a draft that disagrees with the target often, can leave you worse off than plain decoding once verification overhead is counted, as the $a = 0.5$ row of Output 22.7.3 hints.

The practical rule is to layer them in the order this section presents them. First make each token cheap (Section 22.5 and Section 22.6), then keep the GPU full across requests (continuous batching), then make each expensive pass produce more tokens (speculative decoding), and finally compile the whole stack for the target hardware, which Section 22.8 takes up next. Each layer assumes the one below it is in place, and together they set the per-node throughput that the distributed serving chapters multiply across a fleet.