Chunked Prefill:
Ending the Great Stall

A single 4,096-token prompt can seize an A100 for two hundred milliseconds while every request mid-decode waits in silence. Chunked prefill fixes it by cutting prefills into chunks and packing them alongside decodes inside a fixed token budget — the stall disappears, but only if the scheduler gets the arithmetic right.

01 The interference problem

Why one long prompt ruins everyone's latency.

Prefill and decode are different workloads wearing the same model's clothes. Prefill processes the entire prompt in parallel: every token's query, key, value, and feed-forward pass happens at once, which makes it compute-bound — the GPU's tensor cores are the bottleneck. Decode generates one token per request per iteration: a single vector-matrix multiply against the full weight matrices, which makes it memory-bound — HBM bandwidth is the bottleneck, and the tensor cores sit mostly idle.

Put numbers on it. Prefill FLOPs are approximately 2 · P · L for P parameters and L prompt tokens. A 7B model with a 4,096-token prompt needs 2 × 7×10⁹ × 4,096 ≈ 5.7×10¹³ FLOPs. An A100 delivers about 280 TFLOP/s sustained in BF16 on large GEMMs, so that prefill takes roughly 205 milliseconds — about 50 microseconds per prompt token. Scale to 13B and the same prompt costs ~1.07×10¹⁴ FLOPs, roughly 380ms. The Sarathi-Serve paper measured worse in practice: serving Yi-34B on two A100s from an arXiv-summarization trace, vLLM exhibited generation stalls lasting over several seconds — one long prompt freezing every in-flight decode for longer than a typical API timeout.

Now the decode side. A 13B model in BF16 is 26 GB of weights. Streaming those weights from HBM at ~2 TB/s takes 13 milliseconds — and that is the entire decode iteration at batch size 1, because the one-token matvec is pure weight streaming. (At larger batches the KV cache joins in: 13B KV cache is 40 layers × 5,120 dim × 2 for K/V × 2 bytes ≈ 0.8 MB per token, so 32 requests at 2K tokens each add ~51 GB of KV reads — more than the weights themselves. Decode can become KV-bandwidth-bound, but the order of magnitude stays tens of milliseconds.)

Terminology check, because the field can't agree: the paper calls it TBT (time-between-tokens); vLLM's docs call it ITL (inter-token latency); SGLang calls it TPOT (time-per-output-token). Same metric. And the SLO is always on a high percentile, never the mean — a stream averaging 20ms TBT with one 2-second stall reads as broken, not fast. Sarathi-Serve's Figure 1 makes this visceral: Yi-34B on two A100s, 128 requests from an arXiv-summarization trace, and one visible stall stretching past several seconds while tokens-per-second (the throughput number) looks fine. Throughput metrics hide stalls; tail-latency metrics catch them. Every argument in this essay is about the tail.

So the interference arithmetic is brutal: one 4K prefill at ~200ms consumes the time of roughly fifteen decode iterations. Every request mid-decode experiences those 200ms as dead air between tokens. Time-between-tokens (TBT) — the metric that determines whether a chat stream feels alive — doesn't degrade gracefully; it spikes. A stream running at a healthy 15ms TBT suddenly shows a 215ms gap. Users notice gaps, not averages, which is why SLOs are written against p99 TBT and why p99 is exactly where whole-prefill admission detonates: a single 4K prompt in the queue poisons the tail for everyone behind it.

02 Orca and iteration-level scheduling

The batching revolution that wasn't enough.

Before Orca, serving engines used request-level batching: a batch of requests entered together and the batch completed only when the longest request finished. A 4K prompt batched with seven chat requests meant seven chat requests waited for the 4K prompt's full generation — head-of-line blocking in its purest form. FasterTransformer worked this way, and its decode-prioritizing schedule protected TBT only by refusing to admit new work until the batch drained, which cratered throughput.

Orca (OSDI '23) replaced the batch with the iteration as the scheduling unit. Each iteration, the scheduler looks at two queues — running requests (mid-decode) and waiting requests (need prefill) — and assembles a fresh batch. Requests enter and leave at iteration boundaries; a short request never waits for a long one to finish generating. Orca's second trick was selective batching: within one iteration, different requests can be in different phases. The engine batches the linear layers across all requests' tokens together while computing attention per request, so a prefill's tokens and decodes' single tokens can share one forward pass.

vLLM inherited iteration-level scheduling and added PagedAttention — KV cache in non-contiguous blocks, which made the memory side of dynamic batching practical. This combination was a genuine revolution: throughput up several-fold over request-level batching, and it became the default architecture of every serious engine, including SGLang and TensorRT-LLM's inflight batching.

The admission policy is what made it bite. vLLM's scheduler (V0 era) was prefill-prioritizing in a specific sense: whenever GPU memory became available — a request finished, KV blocks freed — the scheduler eagerly admitted waiting prefills before growing the decode batch. The paper quotes the mechanism directly: prefills are scheduled "whenever GPU memory becomes available," which under bursty arrivals means a 4K prompt jumps the queue into the next iteration the moment a few blocks free up. Throughput-wise this is defensible — admitted prefills become decodes, decode batch sizes grow, tokens/sec climbs. Latency-wise it is a trap, because the scheduler has no notion of how much compute it just admitted: a 128-token prompt and a 4,096-token prompt are both "one prefill" to the admission logic, but one costs 6ms and the other 200ms. Admitting the 4K one means the next iteration takes ~200ms instead of ~15ms, and every decode in the running set eats the full 200ms as a TBT spike. Iteration-level batching let requests join and leave freely, but it couldn't subdivide the one unit of work that mattered. The paper's own taxonomy (Figure 2 of Sarathi-Serve) puts Orca and vLLM in the same box — "iteration-level batching, prefill prioritizing" — and Figure 1 shows what that box costs: multi-second generation stalls.

Selective batching was the seed of the fix. If prefill tokens and decode tokens can already share a forward pass, the only remaining question is why the prefill must arrive all at once. It doesn't — attention is causal, so a prompt can be processed left to right in pieces, with each piece attending to the KV cache written by the pieces before it. That observation is chunked prefill.

03 Chunked prefill mechanics

Sarathi's token budget.

The core idea fits in one sentence: cap the number of prefill tokens admitted per iteration — the token budget — split long prefills into chunks that fit, and pack the remainder of each iteration with decode tokens. In the original Sarathi (2023) the chunk size was 512 tokens; Sarathi-Serve generalized this to a per-iteration token budget (evaluated at 512 and 2,048) and computes, for each waiting prefill, the maximum chunk that fits the leftover budget after decodes are placed. A 4,096-token prompt at a 2,048 budget becomes two chunks across two iterations; at a 512 budget, eight chunks across eight.

Causal correctness survives chunking because attention is already left-to-right. Chunk k of a prompt contains tokens [(k−1)·C, k·C); its queries attend to the keys and values of all tokens before them — the KV cache written by chunks 1 through k−1, which is already sitting in HBM, plus the tokens within chunk k itself. Each chunk writes its own KV slice progressively, so nothing is recomputed and nothing is read twice within a chunk. The prefill's total FLOPs are unchanged at 2·P·L; they are just spread across iterations. There is one real extra cost — each chunk re-reads the prefix KV of all earlier chunks, which section 05 prices exactly — but the compute is identical.

The reason this is nearly free is the piggyback insight, and it falls straight out of the roofline. A decode iteration on an A100 is memory-bound: ~13ms spent streaming 26 GB of weights while the tensor cores, capable of 312 TFLOP/s, do a few TFLOP of matvec work and idle. The compute headroom in a decode iteration is enormous — the SMs are waiting on HBM. A 512-token prefill chunk for a 7B model is 2 × 7×10⁹ × 512 ≈ 7.2×10¹² FLOPs, about 25ms of tensor-core time at sustained throughput. Dropped into a decode iteration, the chunk's GEMMs raise the iteration's arithmetic intensity: the weight read that was pure overhead for the decodes now amortizes across the chunk's tokens too, and the iteration stretches from ~15ms to ~30–40ms instead of the ~200ms a whole prefill would cost. The paper's own measurement backs the mechanism: prefill throughput saturates around a 512-token sequence length (their Figure 4) — a 512-token chunk is large enough to keep the tensor cores busy, which is exactly why chunks shouldn't be much smaller.

The roofline makes the piggyback quantitative rather than hand-wavy. An A100 offers 312 TFLOP/s of BF16 compute against 2 TB/s of HBM bandwidth, so the ridge point — the arithmetic intensity where the workload flips from memory-bound to compute-bound — sits at 312/2 = 156 FLOP per byte. A decode step is a matrix-vector multiply: roughly 2 FLOPs per weight byte, about 78× below the ridge, which is why the SMs idle near 1–2% compute utilization while HBM streams. Now drop in a 512-token chunk for a 7B model: 7.2×10¹² FLOPs against one 14 GB weight read gives ~514 FLOP/byte — well above the ridge, solidly compute-bound. The mixed iteration therefore raises arithmetic intensity: HBM still streams the weights once per iteration, but those bytes now serve both the decode matvecs and the chunk's GEMMs, lifting the iteration from ~2 FLOP/byte toward the compute-bound regime. The weight bytes, the most expensive thing in the iteration, get amortized across decode tokens and prefill tokens instead of just decodes. That amortization is the entire economic argument for hybrid batches, and it only works because the two phases sit on opposite sides of the ridge point.

Contrast the two schedules directly. Without chunking, admitting a 4K prefill inserts a ~200ms iteration into the stream: eight in-flight decodes each see one 215ms TBT sample, and p99 is wrecked by a single scheduling decision. With chunking at a 512 budget, the same prompt becomes eight ~35ms mixed iterations: decodes see a steady ~35ms cadence — slightly elevated, never spiked — while the prefill's own completion (TTFT) stretches from ~200ms to ~280ms because its chunks now share iterations with decodes. That stretch is the price, and section 04 argues it is the right price.

Two schedules for the same event: a 4,096-token prefill arriving while eight requests decode. Naive admission inserts one 200ms iteration — every decode sees its TBT jump from ~15ms to ~215ms. Chunked admission spreads the prefill over eight ~35ms mixed iterations; the prefill's own first token arrives ~80ms later, but no decode ever stalls. The tradeoff is visible on the axis: TTFT stretches, TBT is protected.

Zoom into a single mixed iteration and the packing becomes concrete. Take a token budget of 2,048 with 12 running decodes. The scheduler places the 12 decode tokens first — 12 tokens of budget — and the leftover 2,036 tokens go to prefill chunks: all of request A's first chunk, or A's remainder plus the head of request B. The next iteration repeats: decodes first, then whatever prefill fits. Across four iterations, two or three long prompts drain chunk by chunk while the decode set — which may itself be growing as chunks complete and their requests join the running set — never waits on an unbounded unit of work.

The scheduling loop itself is worth spelling out, because its simplicity is the point. Each iteration: first, place all running decode requests — every one, no selection, decode-maximal. Count their tokens against the budget (one per request). Then walk the waiting queue in order; for each prefill, compute the maximum chunk that fits the leftover budget and schedule exactly that many tokens, splitting the prompt at the chunk boundary. A prefill too large for the leftover simply contributes a smaller chunk this iteration and retries next iteration, when the decode set — and therefore the leftover — will have changed. There is no prediction, no cost model, no prompt-length oracle: the budget is the only control, and it is enforced by construction rather than by estimation. That is why the guarantee ("TBT nearly independent of prompt length") holds without the scheduler knowing anything about the prompts.

Four iterations at a 2,048-token budget draining three prompts (A: 3,072 tokens, B: 2,486, C: 2,580). Every iteration is decode-maximal — running decodes are placed first, prefill chunks take exactly the leftover — so per-iteration compute never exceeds the budget regardless of prompt length. As chunks complete, their requests graduate into the decode set (iterations 3–4), which is why the decode count grows. The scheduler's job is reduced to bin packing against a fixed budget.

Note what the budget does to variance. Without it, iteration time is a function of whatever prompt happened to arrive — 15ms, 200ms, 2 seconds, lottery. With it, every iteration costs at most the budget's worth of compute plus one decode pass, so iteration time is nearly independent of prompt length. The paper states this as the central guarantee: bounding compute per iteration makes TBT nearly independent of input length. Uniform iterations have a second payoff the paper exploits: with pipeline parallelism, wildly varying microbatch times create pipeline bubbles — one slow stage idles the rest. Uniform, budget-capped iterations balance the pipeline, which is a large part of why Sarathi-Serve's gains are biggest (up to 5.6× end-to-end serving capacity on Falcon-180B) in pipeline-parallel deployments.

04 Stall-free scheduling

Sarathi-Serve's decode-maximal rule.

Chunking is the mechanism; stall-free scheduling is the policy that makes it safe. The rule, per iteration: place every running decode first, then admit prefill chunks only into the leftover budget. A waiting prefill never displaces a decode, never extends an iteration beyond the budget, and therefore never stalls one. The paper's scheduler computes, for each waiting prefill, the maximum chunk size that fits the leftover tokens — a prefill that doesn't fit is simply split, and the split point moves every iteration as the decode set changes size.

The measured payoff is stark. The paper compares hybrid batches built two ways — decodes plus a full prefill (the Orca-style mix) versus decodes plus chunked prefills — and reports the naive mix inflating TBT by up to 28.3× over a decode-only batch, while the chunked mix holds a tight bound. End to end, under tail-latency SLOs, Sarathi-Serve raised serving capacity by up to 2.6× on Mistral-7B (single A100), 3.7× on Yi-34B (two A100s, tensor parallel), and 5.6× on Falcon-180B (8 A100s, pipeline parallel) versus vLLM. Note the shape of those numbers: the wins grow where iteration-time variance hurts most — pipeline-parallel deployments with bubbles, and larger models where a whole prefill is a longer stall.

The policy bakes in a deliberate tradeoff: TTFT gets worse so TBT can get better. A 4,096-token prompt that prefills in one ~200ms iteration now needs two iterations at a 2,048 budget, or eight at 512 — its first token arrives later because its chunks queue behind decodes' budget priority. The paper's ablation (their Table 4) isolates this: chunked-prefill-only increases TTFT, since chunks are slightly less efficient than a monolithic prefill, while hybrid-batching-only increases TBT, since long prefills still stall. Only the combination improves both capacity and tail latency. For chat and agents — workloads where the user watches tokens stream — this is the right trade: a first token delayed by 80ms is invisible next to a mid-stream 200ms freeze.

Put a number on the stretch, because "TTFT gets worse" is too vague to tune against. A 4,096-token prompt at a 2,048 budget needs 2 chunks; at mixed iterations of ~35ms, its first token lands at ~70ms plus queueing — actually faster than the monolithic 200ms, because the first chunk only waits for one budget-sized iteration rather than a whole prefill's worth of queue. At a 512 budget it needs 8 chunks × ~35ms ≈ 280ms, a 1.4× stretch over monolithic. The stretch factor is roughly (mixed-iteration time × number of chunks) / monolithic prefill time, and it is tunable: bigger budget, smaller stretch, weaker TBT protection. This is why the budget is the single knob — it slides the system along the TTFT–TBT frontier instead of picking a point blindly.

For bulk summarization where TTFT dominates the job's latency, it isn't, which section 05 takes up.

That leaves the tuning question: how big should the budget be? The paper evaluates 512 and 2,048 across models, and the choice falls out of four constraints pulling in different directions:

In practice the industry converged on the same knobs with different defaults. vLLM V1 enables chunked prefill by default, prioritizes decodes, and exposes the budget as max_num_batched_tokens — 2,048 in the V0 era, with V1 guidance of ~2,048 for good inter-token latency and >8,192 for throughput on smaller models. SGLang implements the same idea under its own chunk-size flag. The names differ; the scheduler is Sarathi's: decodes first, prefill chunks in the leftover.

One more honesty note on budgets, from the Etalon follow-up work on per-token deadlines (the "fluidity-index" metric): at a 25ms token deadline, the authors found almost all mixed batches — chunked included — violated the SLO. A budget is not a magic number; it has to be derived from the actual TBT target, the model, and the hardware. Set the budget from the SLO backwards: budget ≈ (TBT SLO − decode iteration time) worth of prefill compute, rounded down to a tile multiple. Static 512/2,048 covers the common cases; the frontier is picking it dynamically, which section 06 covers.

Schematic TBT p99 against request rate for the two policies. Whole-prefill admission is fine at low load and then detonates: each long prompt that arrives injects a multi-hundred-millisecond iteration into every in-flight decode, so the tail crosses a 100ms SLO at barely 2 queries/sec. The chunked scheduler's iterations are budget-bounded, so the tail rises gently with queueing instead of spiking with prompt length — the same hardware serves roughly 4–5× the load under the same SLO. Curves are illustrative; the shape (exploding vs flat) is what the paper's measurements show.

The table is the essay in miniature. Every row before Sarathi treats the prefill as atomic and pays for it in tail latency; every row after treats the token budget as the atomic unit and pays for it in TTFT. That is the entire design space of modern LLM scheduling in one column.

05 Costs and sharp edges

What chunking doesn't fix.

Chunking is not free; it converts one kind of cost into another, and the exchange rate matters. The real extra work is HBM traffic, not FLOPs. Within a chunk, attention is computed once — but chunk k must read the KV cache of all k−1 earlier chunks to attend over the prefix. Price it: a prompt of length L split into N chunks of C tokens forces the attention kernel to read roughly C·(1 + 2 + … + N) = C·N(N+1)/2 KV-token entries, versus L entries for a monolithic prefill. For L = 4,096 and C = 512 (N = 8): 512 × 36 = 18,432 KV-token reads against 4,096 — about 4.5× the HBM traffic for the attention portion. The FLOPs are unchanged; the bytes are not.

In practice the damage is bounded because attention is a fraction of prefill cost at moderate context lengths — the feed-forward layers, at 2·P·L with no re-reading, dominate. The paper measures it directly (their Figure 14, Yi-34B): at the smallest chunk size, 512, chunking adds at most ~25% to overall prefill runtime; at the larger 2,048 budget the overhead is almost negligible. That is the number to carry: chunking taxes prefill throughput by up to a quarter in the worst case, and the tax shrinks as chunks grow. It also grows with context length — at 128K tokens the quadratic attention term dominates and the re-read multiplier bites harder, which is one reason long-context serving pushes toward disaggregation instead.

The second sharp edge is CUDA graphs. Engines capture CUDA graphs to kill kernel-launch overhead, but a graph is a recording of fixed shapes: fixed batch size, fixed token counts. Chunked prefill makes every iteration's token count different — 2,048 here, 1,612 there, 2,036 after that. vLLM's answer is padding: bucket the observed batch sizes, capture a graph per bucket, and pad each iteration's token count up to the next bucket. The padding wastes a little compute (dummy tokens through the GEMMs) to buy back graph replay; the bucketing keeps the waste bounded. It works, but it means the "budget" the scheduler sees and the "budget" the hardware executes are related by a padding function, and naive budget math that ignores padding overestimates efficiency.

The attention kernel itself needs no changes, which is why chunking shipped fast. Each chunk is an ordinary causal attention call: queries from the chunk's C tokens against keys/values for all tokens up to the chunk's end. FlashAttention-2 handles that shape natively — it never materializes the attention matrix, so the only thing that grows with chunk index is the KV read volume, exactly the 4.5× re-read priced above. The KV cache layout is chunk-agnostic too: vLLM's paged blocks are filled token-sequentially regardless of which chunk wrote them, so a chunk boundary is invisible to the memory manager. Chunking lives entirely above the kernel — in the scheduler's token accounting — which is why vLLM and SGLang could adopt it without touching their attention backends.

Prefix caching interacts benignly but not invisibly. A cached prefix's KV is reused regardless of chunk boundaries, so chunking composes with it — but chunk boundaries rarely align with prefix boundaries, and the scheduler must track, per request, how much of the prompt is cached versus needs chunking. vLLM handles this by computing prefill only over the uncached suffix and chunking that. The bookkeeping is per-request state (cached length, chunk offset), small but real, and it lives in the scheduler's hottest path.

And then there is the workload where chunking is the wrong answer: prefill-heavy serving. Long-document summarization, bulk embedding-adjacent jobs, anything where TTFT dominates the request's latency and there are few concurrent decodes to protect. Chunking stretches TTFT — that is its explicit price — while its benefit (protecting decodes) has nobody to protect. In those regimes the paper itself concedes the alternative: disaggregated prefill/decode (Splitwise, DistServe, Mooncake) runs prefills at maximum efficiency on dedicated hardware with no chunking tax at all. Chunked colocation wins when phases share a GPU and decodes need shielding; it loses, mildly, when the prefill phase is the whole job.

06 Open questions

Where scheduling goes next.

Colocation vs. disaggregation is unsettled. Splitwise showed that prefill and decode want different hardware — prefill is compute-hungry, decode is bandwidth-hungry — and put them on different machines, even different GPU types, paying KV-cache transfer over the network to eliminate interference entirely. Mooncake took the same split and added a KV-cache-centric twist: disaggregated prefill with cache reuse across requests. Against that, chunked colocation says the transfer cost and the operational complexity of two fleets aren't worth it when a scheduler can bound the interference in software. The honest answer depends on scale: at modest QPS the colocation tax (~25% prefill overhead, stretched TTFT) is cheaper than a second fleet; at very long contexts, where the KV re-read multiplier grows quadratically, the physics starts favoring a wire over a scheduler. Nobody has published the crossover curve; it would be a genuinely useful measurement.

Static budgets leave money on the table. A fixed 512 or 2,048 budget is tuned for one SLO on one model on one GPU. When the decode batch is small, a fixed budget strands slack — iterations finish early with compute unused, and pending prefills wait for no reason. When a burst arrives, the same budget can push iteration time past the token deadline. SLOWeave (2026) made this the optimization target: choose the chunk size per iteration from live scheduler state — decode load, TPOT target, arrival pressure — with the optimum C* a function of all three. Fixed budgets capture one point in that space; the direction is clearly dynamic, deadline-aware chunking, where the scheduler reasons about per-request token deadlines (the fluidity-index view from the Etalon work) rather than a single global budget.

The KV math is about to change under chunking's feet. DeepSeek's MLA absorbs keys and values into a low-rank latent, shrinking per-token KV by an order of magnitude — which shrinks both the decode iteration's KV streaming and the chunked prefill's re-read multiplier. Chunking's cost model was derived for standard MHA/GQA; under MLA the 4.5× re-read arithmetic gets much cheaper, and the optimal chunk size moves. Similarly, MoE models route tokens to experts per chunk — chunk boundaries interact with expert load balancing in ways the dense-model analysis doesn't cover. The scheduler, the attention variant, and the chunk size are a three-body problem now.

Mooncake reframed the other side of the bet. Where Splitwise disaggregates by phase, Mooncake disaggregates around the KV cache itself: prefill nodes compute KV once, the cache becomes a distributed, reusable object, and decode nodes fetch it. Under that architecture chunking's central cost — the per-chunk prefix re-read — is replaced by a different cost, cross-node KV transfer, and the scheduler's problem becomes cache placement rather than iteration packing. For workloads with heavy prefix reuse (agents re-reading tool outputs, multi-turn chat), the KV-centric design attacks the same interference from the reuse angle. The open question is which cost curve bends harder at 100K+ contexts: HBM re-reads under chunking, or network transfers under disaggregation.

What to watch: whether vLLM/SGLang adopt dynamic chunk sizing (the SLOWeave idea is directly implementable in their schedulers); measured crossover points between chunked colocation and disaggregation at 100K+ contexts; and whether per-token-deadline metrics like fluidity-index replace p99 TBT as the scheduling objective — because a scheduler that reasons about deadlines can do strictly better than one reasoning about budgets.