Cruxly › AI engineering › Inference Serving

Continuous Batching and the Scheduler

iteration-level scheduling, and why prefill and decode are two different jobs

Prompt: your serving box shows 95% GPU utilization and still only manages 400 output tokens/second on a 7B model that benchmarks at 3,000+. Requests also show wildly variable latency — the same prompt sometimes returns in 600 ms and sometimes in 9 seconds. Diagnose it and fix the scheduler.

40 minutes first. Both symptoms have the same root cause, and "the GPU is already at 95%" is the red herring the question is built around.

Static batching: where the GPU time actually goes

Static batching groups N requests, runs them together, and returns when the last one finishes. It is the shape you get from a naive for batch in dataloader translation of training code into a server, and it wastes the GPU in a way that is easy to quantify.

Take a batch of 8 requests whose output lengths are 20, 30, 40, 60, 100, 150, 400, and 900 tokens. Static batching runs 900 decode iterations, because that is when the last sequence finishes. Total useful token-slots produced: 20+30+40+60+100+150+400+900 = 1,700. Total slots the GPU actually computed: 8 × 900 = 7,200. Efficiency: 23.6%. Over 76% of the decode compute went to padding for sequences that had already emitted their end-of-sequence token and were sitting in the batch doing nothing but holding memory.

And the variance symptom falls out of the same mechanism. The 20-token request in that batch waited for 900 iterations before its response was returned — so an identical short prompt is fast when it lands in a batch of short peers and 45× slower when it lands next to one long generation. That is the 600 ms / 9 s spread in the prompt, and no amount of hardware fixes it.

Dynamic batching — the intermediate answer — only fixes the queueing half. It waits a small window (say 10 ms) to accumulate arrivals into a batch before launching, which helps when traffic is bursty and requests would otherwise run one at a time. But once the batch launches it is still static: a finished sequence still cannot leave early, and a new arrival still cannot join. It is the right answer for fixed-output-length models like embedding or classification, and the wrong answer for autoregressive generation, where output length varies by an order of magnitude within a normal batch.

Continuous batching: scheduling at the iteration, not the request

The fix is to make the scheduling decision once per forward pass instead of once per batch. After every single decode iteration, the scheduler asks: which sequences finished (evict them, free their KV blocks, return their responses immediately), and which queued requests can now be admitted into the freed slots? A sequence joins a batch already in flight and leaves the instant it emits end-of-sequence. This is iteration-level scheduling, and "continuous batching" is the serving-world name for it.

On the same 8-request example, the batch stays full. The 20-token request returns after 20 iterations instead of 900. As each short sequence leaves, a queued request takes its slot, so the GPU keeps computing useful tokens rather than padding. Reported end-to-end throughput improvements (Anyscale's 2023 benchmark reported up to 23× for vLLM over naive Hugging Face serving, and the Orca paper reported over 30× against FasterTransformer at matched latency; those baselines and workloads are not yours, so treat the size as indicative) are not marketing — they come from that 23.6% efficiency figure going to near-100%, multiplied by the higher average batch size you can now sustain.

The prerequisite is the paged KV cache from GPU Memory Math: Weights, KV Cache, and What Actually Fits. Iteration-level scheduling only works if a sequence's memory can be allocated and released in small increments at arbitrary times — which is exactly what PagedAttention provides and what contiguous reservation forbids. Continuous batching and paged KV are usually described as two features; they are better understood as one mechanism and its memory manager.

Prefill and decode are two different workloads

This is the distinction that separates a candidate who has operated an inference server from one who has read about one.

Prefill processes the entire prompt in one forward pass. Every token attends in parallel, so the GPU does a large matrix-matrix multiplication with high arithmetic intensity: it is compute-bound, and a single 4,000-token prompt can saturate an A100 by itself. Cost scales with prompt length.

Decode generates one token per forward pass per sequence. The matrices are matrix-vector products — the whole weight matrix must be read from HBM to produce a handful of numbers — so arithmetic intensity is terrible and the step is memory-bandwidth-bound. A batch of 1 in decode uses a few percent of an A100's FLOPs while pinning 100% of its bandwidth, which is precisely why GPU utilization is a lying metric here.

	Prefill	Decode
Parallelism	whole prompt at once	one token per sequence
Bottleneck	compute (FLOPs)	memory bandwidth
Batching helps?	barely — already saturated	enormously — amortizes weight reads
Scales with	prompt length	output length × batch size
Owns which metric	TTFT	TPOT

The scheduler consequence: batching a long prefill together with ongoing decodes stalls every streaming response. A 30,000-token prefill can take several hundred milliseconds to a couple of seconds, and if it runs as one iteration of the shared batch, every other user's token stream freezes for that entire duration. Users describe this as "it randomly pauses mid-sentence." It is one long prompt entering the batch.

Chunked prefill is the fix. Split a long prefill into fixed-size token chunks — 512 or 2,048 tokens — and schedule one chunk per iteration alongside the ongoing decodes. The long prompt takes several iterations to finish prefilling instead of one, which slightly raises its TTFT, and in exchange nobody else's stream stalls. It also raises overall GPU efficiency, because a chunk of compute-bound prefill mixed with bandwidth-bound decodes uses more of the hardware than either alone — the two workloads' bottlenecks are complementary.

The bigger-hammer version is disaggregated serving: run prefill on one pool of GPUs and decode on another, transferring the KV cache between them. It lets each pool be sized, batched and even hardware-matched for its own bottleneck, and it costs you a KV-cache transfer over the interconnect on every request. This is no longer "the direction the field is moving" — it runs in production today (NVIDIA Dynamo, llm-d, Mooncake, SGLang's prefill/decode mode). Name it as a real option for large fleets, and name the KV transfer as its price: it only pays off when the interconnect is fast and the fleet is big enough to keep both pools busy.

Prefix caching: the free win everyone leaves on the table

If every request in your product begins with the same 2,000-token system prompt, you are re-prefilling those 2,000 tokens on every single request for no reason. The KV vectors for a given prefix are deterministic given the model — identical input tokens produce identical keys and values — so they can be computed once and reused.

Do the arithmetic on a realistic RAG-style request. System prompt 1,800 tokens, few-shot examples 1,200 tokens, retrieved context 3,000 tokens, user question 100 tokens. The first 3,000 tokens are byte-identical across every request from that endpoint. Prefix caching drops prefill work for that request from 6,100 tokens to 3,100 — roughly half the prefill compute and half the TTFT contribution from prefill, for a feature that requires no model change and no quality trade-off whatsoever.

The mechanism is chained hashing and reference counting on paged blocks. A block's keys and values depend on every token before it, not just its own 16 tokens — so the same 16 tokens after a different prefix produce different KV. The hash therefore has to cover the whole prefix:

Each block's hash = hash(parent block's hash + this block's token IDs + extra keys), where extra keys cover anything else that changes the KV — the LoRA adapter ID, multimodal inputs, a per-tenant cache salt.
Walk the prompt block by block, reusing any block whose chained hash already exists in the table, and compute only from the first mismatch onward.
Hashing a block's contents plus its position alone would be a bug: two prompts with identical tokens at block 5 but different text in blocks 1–4 would collide and serve the wrong KV.

SGLang's RadixAttention generalizes this to a radix tree over all active and recent prefixes, which handles branching conversation trees and multi-turn history rather than just a single shared head.

Three things to say about where it does and does not pay. It is enormous for shared system prompts, multi-turn chat (turn N re-prefills all of turns 1..N-1 without it), and agent loops that replay a growing scratchpad. It does nothing for a workload of unique, short, unrelated prompts. And it is exactly prefix-sensitive: putting a per-request timestamp, request ID or user name at the start of your prompt template invalidates the shared prefix for every request and silently reduces the cache hit rate to zero. Order your prompt template static-first, variable-last, and say that out loud — it is a one-line change that is worth more than most tuning.

The security caveat worth raising unprompted. Cross-request block sharing means blocks from one tenant's prompt can, if the cache is not partitioned, be reused for another tenant's request whose prefix happens to match — and cache hit timing is observable, which makes it a side channel for confirming whether a particular prefix has been seen. Partition the prefix cache by tenant. Raising this before being asked connects this topic to the multi-tenant isolation discipline from the retrieval module.

The throughput/latency knob, and how to set it

The scheduler has one fundamental dial — how many sequences to run in a batch — and it trades the two things users care about against each other. Larger batches amortize the weight read across more sequences, so total tokens per second goes up; but every sequence in a batch shares one forward pass, so each individual sequence's time per output token goes up too. High throughput and low per-user latency are the same resource spent two ways.

Concretely, on a 7B model on one A100: batch size 1 might give ~90 tokens/sec for that one user and ~90 tokens/sec of total system throughput. Batch size 64 might give each user ~35 tokens/sec while producing ~2,200 tokens/sec system-wide. The single user is 2.5× slower; the box serves 24× more work. Neither is correct in the abstract — it depends entirely on whether you are serving an interactive chat UI or a batch document pipeline.

So set the batch cap from the SLO, not from the benchmark. Users don't read every streamed token — they skim, and adult reading speed is only about 5–7 tokens/sec anyway — but output noticeably slower than ~20–25 tokens/sec looks sluggish, and for code or agent outputs that feed another step, total completion time matters more than reading pace. So a chat product should keep each user above roughly 20–25 tokens/sec and cap the batch wherever the p95 TPOT crosses that; a nightly summarization job has no such floor and should run the largest batch that fits in KV memory. Running one engine configuration for both workloads is the mistake — separate pools with separate batch caps, routed by request class, is the answer, and it is the same "two different workloads" reasoning as prefill/decode one level up.

Also give the scheduler a queueing policy, and know what it costs. First-come-first-served is fair and lets one 30K-token prefill delay everything behind it. Shortest-job-first minimizes average wait and starves long requests. A priority lane for interactive traffic over batch traffic is usually the pragmatic production answer, with a cap on how long a batch request can be starved so it does not wait forever.

How to say it in the interview

"High GPU utilization during decode means almost nothing, because decode is memory-bandwidth-bound — the GPU looks busy while it re-reads the entire weight matrix to produce one token for one request. The fix is not a bigger GPU, it is putting more requests in the same forward pass, and doing that at iteration granularity rather than at request granularity so a finished sequence releases its slot immediately instead of at the end of the batch."

Checklist

Quantified static batching's waste with an actual output-length spread
Explained the latency variance and the low throughput as one root cause
Distinguished dynamic batching from continuous batching rather than conflating them
Described continuous batching as a per-iteration evict/admit decision
Named prefill as compute-bound and decode as memory-bandwidth-bound
Explained the mid-stream stall from a long prefill and fixed it with chunked prefill
Computed the prefix-cache saving on a realistic shared system prompt
Put static content first and variable content last in the prompt template
Set the batch cap from the latency SLO, with separate pools per request class

Practice this interactively