Continuous Batching and Speculative Decoding: How Modern LLM Serving Engines Actually Work

TL;DR: LLM decoding is memory-bandwidth bound, so the whole game is keeping the GPU busy with useful work per byte of weights read. Continuous batching (iteration-level scheduling) plus paged KV-cache management is what makes high throughput possible; speculative decoding is a latency optimisation that trades spare compute for fewer sequential steps. They interact: speculation shines at low batch sizes and can become a net loss at high batch sizes, so production engines tune or disable it dynamically.

If you deploy open-weight models on vLLM, SGLang, TensorRT-LLM, or TGI, you are configuring these mechanisms whether you know it or not — max_num_seqs, max_num_batched_tokens, gpu_memory_utilization, speculative config. Understanding what happens inside the scheduler turns those knobs from cargo-cult settings into engineering decisions. This article explains the mechanics from first principles and ends with a practical tuning framework.

Why LLM inference is a scheduling problem

Autoregressive generation has two phases with very different hardware profiles.

• Prefill processes the entire prompt in one forward pass. Every prompt token is computed in parallel, so prefill is dense matrix multiplication and is compute-bound. It produces the key/value (KV) tensors for every prompt token, which are cached.
• Decode generates one token per forward pass per sequence. Each step reads the entire model's weights from GPU memory (HBM) to produce a single token per sequence. The arithmetic per byte loaded is tiny, so decode is memory-bandwidth-bound.

That second point drives everything. If a single decode step for one sequence reads all the weights, then decoding 32 sequences in the same step reads the weights once and amortises that cost 32 ways. Batching is the primary lever for throughput. The constraint is memory: every active sequence needs its KV cache resident on the GPU, and the KV cache grows by one entry per layer per token generated.

So an LLM server is really a scheduler solving a bin-packing problem every few milliseconds: which sequences to run this step, given compute, memory bandwidth, and KV-cache capacity.

Static batching and why it wastes the GPU

The naive approach, borrowed from classic model serving, is request-level batching: gather N requests, run them together until all finish, return results, repeat.

For LLMs this is disastrous because output lengths vary wildly and are unknown in advance. If one request in a batch generates 1,000 tokens and the others generate 20, the batch holds its slots for 1,000 steps while most of them do nothing. New requests queue behind it — head-of-line blocking. GPU utilisation collapses and tail latency explodes.

Continuous batching: scheduling per iteration

The fix came from the Orca paper (OSDI 2022), which introduced iteration-level scheduling: instead of scheduling whole requests, the scheduler runs the model for a single iteration over the current batch, then re-decides the batch composition before the next iteration (Orca, USENIX OSDI '22). When a sequence emits its end-of-sequence token, its slot is freed immediately and a waiting request can join on the very next step. Orca reported up to 36.9× throughput over NVIDIA FasterTransformer at the same latency on GPT-3 175B.

This technique is now universally called continuous batching (or in-flight batching), and every serious serving engine implements it. Anyscale's benchmarks showed continuous batching delivering large throughput gains over naive static batching on realistic workloads, alongside lower median latency (Anyscale).

Conceptually the engine loop looks like this:

while True:
    # 1. Retire finished sequences, free their KV blocks
    for seq in running:
        if seq.finished():
            kv_cache.free(seq)
            respond(seq)
    running = [s for s in running if not s.finished()]

    # 2. Admit waiting requests while budgets allow
    while waiting and len(running) < MAX_NUM_SEQS \
          and token_budget_ok(running, waiting[0]) \
          and kv_cache.can_allocate(waiting[0]):
        running.append(waiting.pop(0))

    # 3. If KV cache is exhausted mid-decode, preempt lowest-priority sequences
    while not kv_cache.can_grow(running):
        victim = running.pop()          # newest / lowest priority
        kv_cache.free_or_swap(victim)   # recompute or swap to CPU later
        waiting.insert(0, victim)

    # 4. One forward pass over the mixed batch (prefill chunks + decode tokens)
    model.step(running)

The hard part is step 3. Because you do not know how long any sequence will run, you will sometimes admit more work than the KV cache can ultimately hold. The engine must then preempt: evict a sequence's KV cache and either swap it to CPU memory or recompute it later. Preemption is expensive, so seeing it frequently in your metrics means you are overcommitting.

PagedAttention: making the KV cache schedulable

Continuous batching only works well if KV memory can be allocated and freed at fine granularity. Early systems allocated a contiguous KV region per request sized for the maximum possible length, which wasted most of the memory through internal and external fragmentation and capped batch size.

vLLM's PagedAttention (SOSP 2023) borrowed virtual memory's solution: split the KV cache into fixed-size blocks (for example, 16 tokens), keep a per-sequence block table mapping logical token positions to physical blocks, and write attention kernels that read through that indirection (vLLM blog — Anatomy of vLLM). The effects:

• Near-zero fragmentation — waste is bounded by one partially filled block per sequence.
• Larger effective batch sizes for the same GPU memory, which directly means higher throughput.
• Copy-on-write sharing: sequences that share a prefix (a common system prompt, parallel samples of the same prompt, beam search) can point at the same physical blocks. This is the basis for automatic prefix caching.

When you set gpu_memory_utilization in vLLM, you are deciding how much memory is left for this block pool after weights and activations. More pool means more concurrent sequences.

Chunked prefill: stopping prompts from stalling decodes

Mixing phases creates a new problem. A long prompt arriving mid-stream triggers a large, compute-heavy prefill. If that prefill runs as one monolithic step, every in-flight decode waits for it, producing a visible stall in token streaming (inter-token latency spikes).

Chunked prefill, formalised in the Sarathi and Sarathi-Serve work, splits long prefills into fixed-size chunks and co-schedules them with ongoing decode tokens in the same forward pass (Sarathi-Serve). Each iteration gets a token budget (max_num_batched_tokens in vLLM); decodes take one token each, and remaining budget is filled with a prefill chunk. Decode steps are memory-bound and leave compute idle, so piggybacking prefill compute onto them improves utilisation while bounding how long any single step takes.

The budget is a direct latency/throughput dial: a larger budget finishes prefills faster (better time-to-first-token for new requests) but makes each step longer (worse inter-token latency for everyone else).

Speculative decoding: spending compute to save steps

Continuous batching maximises throughput. But for a single user watching tokens stream, the bottleneck is still one sequential forward pass per token. Speculative decoding attacks that sequential dependency.

The core idea

A cheap draft mechanism proposes k tokens ahead. The large target model then verifies all k proposals in one forward pass — which costs roughly the same as generating one token, because decode is memory-bound and the extra k positions add little. Tokens are accepted left to right until the first disagreement; the target's own prediction replaces the first rejected token. In the best case you get k+1 tokens for the price of one target step; in the worst case you get 1, same as normal decoding.

Critically, with the modified rejection sampling scheme from Leviathan et al. and Chen et al., the output distribution is provably identical to sampling from the target model alone (Leviathan et al., Chen et al.). Speculative decoding is lossless; it changes speed, never quality.

def speculative_step(target, draft, context, k):
    proposals, q_probs = draft.propose(context, k)          # k cheap sequential steps
    p_probs = target.forward(context + proposals)           # ONE target pass over k positions
    accepted = []
    for i, tok in enumerate(proposals):
        if random() < min(1, p_probs[i][tok] / q_probs[i][tok]):
            accepted.append(tok)
        else:
            # resample from the residual distribution max(0, p - q), normalised
            accepted.append(sample(normalize(relu(p_probs[i] - q_probs[i]))))
            return accepted
    accepted.append(sample(p_probs[k]))                     # bonus token if all accepted
    return accepted

Draft strategies

• Separate small draft model — a smaller model from the same family with the same tokenizer. Simple, but you now host two models and the draft's own sequential steps add latency.
• Medusa — extra decoding heads on the target model predict tokens at positions t+1, t+2, … in parallel. No second model, but the heads predict independently of each other, which limits acceptance.
• EAGLE family — a lightweight autoregressive head operating on the target model's hidden features, so each draft token conditions on the previous ones. The EAGLE paper reports roughly 3× speedups on LLaMA2-Chat 13B at temperature 0 and faster results than Medusa and Lookahead (EAGLE).
• N-gram / prompt lookup — propose tokens by matching n-grams from the prompt. Zero training, surprisingly effective for extraction, summarisation, and code editing, where outputs copy large spans of input.

The metric that matters is the acceptance rate (or mean accepted length per step). It depends on how predictable your workload is, the temperature, and how well the draft is aligned with the target. It is workload-specific — measure it on your own traffic rather than trusting published numbers.

Where the two techniques collide

This is the part most tuning guides skip. Speculative decoding works by using compute that decode leaves idle. Continuous batching works by filling that idle compute with more sequences. At high batch sizes, the verification passes for k speculative tokens across dozens of sequences are no longer free: the step becomes compute-bound, rejected tokens are wasted work, and the draft model competes for memory that could have held more KV cache.

Research consistently finds that speculation's speedup shrinks as batch size grows, and past a certain point it can be slower than plain decoding (TurboSpec, Baseten). That is why newer systems adapt speculation length to load, or switch it off under heavy traffic.

A tuning framework

1. Decide your objective per deployment. Throughput (tokens/sec/GPU, cost per million tokens) or latency (time-to-first-token and inter-token latency at a target percentile). You cannot maximise both with one configuration.
2. Size the KV pool first. Raise gpu_memory_utilization as high as is stable, and prefer quantised KV cache (FP8) if your quality evals allow. More blocks mean larger batches.
3. Set concurrency limits from measurement. Increase max_num_seqs until throughput plateaus or preemption events appear. Frequent preemption means you have overcommitted.
4. Tune the per-step token budget. Larger for TTFT-sensitive workloads with long prompts; smaller for smooth streaming.
5. Enable prefix caching if requests share long system prompts or retrieved context. It turns repeated prefill into cache hits.
6. Add speculative decoding only for latency-bound deployments. Start with n-gram lookup (free) or an EAGLE-style head if available for your model. Measure acceptance and end-to-end latency at your real concurrency, not batch size 1.
7. Load-test with realistic length distributions. Synthetic benchmarks with fixed input/output lengths hide exactly the variance continuous batching exists to handle. Replay production traces.
8. Re-run your eval pipeline after every change that touches numerics (quantisation, KV dtype). Speculative decoding itself is lossless, but many performance knobs are not.

Beyond a single engine: routing and disaggregation

Once one replica is tuned, the next bottleneck is usually the layer in front of it. Two patterns are increasingly common.

Cache-aware routing. Prefix caching only helps if requests sharing a prefix land on the replica that holds it. A round-robin load balancer scatters them and throws the benefit away. Routers that hash on a session ID, tenant, or system-prompt fingerprint — or that query replicas for cache contents — keep related requests together. The trade-off is load skew: a very popular prefix can overload one replica, so good routers combine affinity with a load threshold that spills to other replicas.

Prefill/decode disaggregation. Because prefill is compute-bound and decode is bandwidth-bound, some deployments run them on separate pools of GPUs and transfer the KV cache between them after prefill. Each pool can then be sized and configured for its own phase, and long prompts no longer interfere with streaming at all. The cost is operational complexity and the network bandwidth needed to move KV tensors, so it tends to pay off only at larger scale or with long-prompt workloads. Several open-source engines now offer experimental support; treat it as an optimisation to reach for after the single-replica fundamentals above are solid.

In both cases the principle is the same one that drives continuous batching: keep expensive hardware doing useful work, and avoid recomputing what you already computed.

Observability you need

At minimum, export: running and waiting queue depth, KV-cache block utilisation, preemption count, per-step batch size and token count, TTFT and inter-token latency percentiles, and — if speculating — acceptance rate and mean accepted length. These map directly onto the mechanisms above, so when latency degrades you can tell whether you are memory-bound (KV exhausted, preemptions), compute-bound (large token budgets, speculation at high batch), or queue-bound (not enough replicas).

Whether you are serving machine learning models for internal tooling or for customer-facing AI assistants, these mechanisms usually matter more to cost and latency than the choice of GPU. Getting them right is also a prerequisite for sensible capacity planning on your cloud infrastructure.

Syslabs' engineering team works on LLM serving and inference-cost problems like these.

Sources: Orca (OSDI '22) · Anyscale — Continuous batching · vLLM — Anatomy of vLLM · Sarathi-Serve · Leviathan et al. — Speculative decoding · Chen et al. — Speculative sampling · EAGLE · TurboSpec · Baseten — Speculative decoding