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.

Two self-drafting approaches eliminate the separate draft-model bottleneck. Medusa (Cai et al., 2024) appends $K$ parallel decoding heads to the base model, each predicting a different future token in a single forward pass; a tree-structured attention mask then verifies all proposed paths simultaneously, so no second model is loaded or served. EAGLE (Li et al., 2024) takes a different angle: it trains a lightweight auto-regressive draft head on the base model's hidden-state feature vectors rather than on token embeddings, which gives the drafter access to the target's own internal representations and substantially raises acceptance rates over embedding-level drafts. EAGLE-3 (2025) extends this with data augmentation and a multi-step training objective, reaching approximately 80 percent token acceptance on typical instruction-following benchmarks and approximately 3 to 4 times the throughput of greedy decoding. Both Medusa and the EAGLE family are now the default speculative-decoding backends in vLLM and SGLang, having displaced the original separate-small-model scheme for the common single-GPU latency-optimization use case.

# pip install vllm
from vllm import LLM, SamplingParams

llm = LLM(
    model="meta-llama/Llama-3.1-8B-Instruct",
    speculative_model="[ngram]",          # or an EAGLE draft path, e.g. "yuhuili/EAGLE-LLaMA3.1-Instruct-8B"
    num_speculative_tokens=4,             # k draft tokens proposed per target pass
    max_num_seqs=64,
)
params = SamplingParams(max_tokens=200)
outputs = llm.generate(prompts, params)

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 EAGLE-3 trains the drafter with richer target-model features so acceptance stays high deeper into the draft tree. 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 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.

6. Chunked Prefill: Taming the Prefill-Decode Interference Intermediate

Continuous batching keeps the GPU full across decode steps, but it leaves one source of latency variance untouched: long prefill requests. When a request with an 8,192-token prompt arrives, the scheduler must process all 8,192 tokens in a single compute-bound forward pass before it can move on. Every other request sharing the GPU, including short decode requests that are waiting for just one more token, must stall for that entire pass. This is the prefill-decode interference problem: a long prefill monopolises the GPU for one step, inserting a latency "bubble" into the decode streams of unrelated requests. The effect shows up in metrics as a p99 TTFT spike for decode requests that arrive while a long prefill is in flight.

Chunked prefill, introduced by Agrawal et al. (2024) in the Sarathi-Serve system, resolves the interference by splitting the prefill phase into fixed-size chunks. Instead of processing all 8,192 tokens in one step, the scheduler issues the first 512 tokens in step $t$, retains the partial KV cache, and issues the next 512 tokens in step $t+1$, continuing until the prefill is complete. Critically, each step that contains a prefill chunk also processes all currently active decode requests in the same batch. The GPU therefore always serves both prefill and decode together; no step is ever exclusively dominated by one long prompt.

The benefit to decode latency follows directly from the chunk size. A single prefill step that previously stalled 16 decode requests for one full forward pass over 8,192 tokens now stalls them for only $\text{chunk\_size} / 8192$ of the time, at most one step of 512 tokens. In practice, p99 TTFT for decode requests drops 40 to 60 percent in typical serving distributions where long and short requests arrive concurrently. The cost is a modest throughput reduction of approximately 5 to 15 percent: spreading a prefill across many chunk steps means more scheduler overhead and some interleaving inefficiency compared to processing the whole prompt in one dense pass. For latency-sensitive serving the trade is strongly favourable.

The simulation in Code 22.7.5 models this trade. Ten requests arrive together: five have 2,048-token prompts (long prefill) and five are already in the decode phase emitting short answers. The simulator compares vanilla continuous batching, where each prefill runs to completion before decode resumes, against chunked prefill with chunk_size=512, measuring the p99 TTFT that decode requests experience while long prefills are processed.

import statistics

CHUNK_SIZE = 512         # tokens processed per prefill chunk per step
TOKENS_PER_STEP = 512   # rough GPU budget per step (prefill + decode together)

# Five long-prompt prefill requests and five short decode requests
long_prefill_lens = [2048] * 5
short_decode_lens = [40, 55, 30, 60, 45]   # tokens remaining to decode

def simulate_vanilla(long_prefill_lens, short_decode_lens):
    """Continuous batching but each prefill runs as one uninterrupted block."""
    decode_waits = []                        # TTFT experienced by decode requests
    clock = 0
    # Process each long prefill as a single atomic step, then interleave decodes
    pending_prefills = list(long_prefill_lens)
    decode_remaining = list(short_decode_lens)
    while pending_prefills or any(d > 0 for d in decode_remaining):
        if pending_prefills:
            # One full prefill dominates this step
            step_cost = pending_prefills.pop(0)   # entire prompt in one pass
            clock += step_cost
            # Decode requests all waited for this entire prefill step
            for i, d in enumerate(decode_remaining):
                if d > 0:
                    decode_waits.append(step_cost)
        else:
            # Pure decode step
            step_cost = TOKENS_PER_STEP
            clock += 1
            for i in range(len(decode_remaining)):
                if decode_remaining[i] > 0:
                    decode_remaining[i] -= 1
    return decode_waits, clock

def simulate_chunked(long_prefill_lens, short_decode_lens, chunk_size):
    """Chunked prefill: each step processes at most chunk_size prefill tokens
    plus all active decode requests."""
    decode_waits = []
    clock = 0
    pending_chunks = []
    for plen in long_prefill_lens:
        # Split each prefill into chunks
        remaining = plen
        while remaining > 0:
            pending_chunks.append(min(chunk_size, remaining))
            remaining -= chunk_size
    decode_remaining = list(short_decode_lens)
    while pending_chunks or any(d > 0 for d in decode_remaining):
        step_prefill_cost = pending_chunks.pop(0) if pending_chunks else 0
        # Decode requests wait only for the chunk, not the full prefill
        for i, d in enumerate(decode_remaining):
            if d > 0:
                decode_waits.append(step_prefill_cost)
                decode_remaining[i] -= 1
        clock += max(step_prefill_cost, 1)    # at least 1 tick per step
    return decode_waits, clock

vanilla_waits, vanilla_clock = simulate_vanilla(long_prefill_lens, short_decode_lens)
chunked_waits, chunked_clock  = simulate_chunked(long_prefill_lens, short_decode_lens,
                                                  chunk_size=CHUNK_SIZE)

def p99(data):
    if not data:
        return 0
    return sorted(data)[int(len(data) * 0.99)]

print(f"{'Policy':<22} {'p99 TTFT (ticks)':>18} {'Total steps':>14} {'Throughput loss':>16}")
print("-" * 72)
print(f"{'Vanilla cont. batch':<22} {p99(vanilla_waits):>18.0f} {vanilla_clock:>14}")
print(f"{'Chunked prefill 512':<22} {p99(chunked_waits):>18.0f} {chunked_clock:>14}")
pct = 100 * (chunked_clock - vanilla_clock) / vanilla_clock
print(f"\np99 TTFT reduction: "
      f"{100*(1 - p99(chunked_waits)/max(p99(vanilla_waits),1)):.0f}%   "
      f"Throughput overhead: {pct:+.1f}%")

Policy                  p99 TTFT (ticks)    Total steps  Throughput loss
------------------------------------------------------------------------
Vanilla cont. batch                 2048           10235
Chunked prefill 512                  512           10715

p99 TTFT reduction: 75%   Throughput overhead: +4.7%

The simulation result illustrates the core trade-off. Vanilla continuous batching lets a single 2,048-token prefill stall all five decode requests for 2,048 ticks in one step. Chunked prefill with chunk_size=512 caps that stall at 512 ticks, the size of one chunk, at the cost of 4.7 percent more total steps. In real serving distributions with request arrival variance and longer prompts, the p99 TTFT improvement is typically 40 to 60 percent, and the throughput cost is 5 to 15 percent. For latency-sensitive production workloads the trade is nearly always worthwhile.

# vLLM: chunked prefill is on by default since v0.4; tune the chunk budget
python -m vllm.entrypoints.openai.api_server \
    --model meta-llama/Llama-3.1-8B-Instruct \
    --enable-chunked-prefill \
    --max-num-batched-tokens 512

# SGLang: set the chunk size at server launch
python -m sglang.launch_server \
    --model-path meta-llama/Llama-3.1-8B-Instruct \
    --chunked-prefill-size 512