Sarathi-Serve: Chunked Prefills for Stall-Free LLM Inference

Online LLM serving wants two things at once: high throughput (keep GPUs packed) and smooth token streams (low time-between-tokens, or TBT). Prefill and decode fight those goals. Prefill is compute-heavy — it can saturate an A100 on a long prompt in one shot. Decode is memory-bound — you want fat batches of one-token steps. Prefill-eager systems in the Orca / vLLM lineage admit whole prompts as soon as KV memory allows. That raises throughput, but a multi-thousand-token prefill can stall every ongoing decode for seconds.

Sarathi-Serve’s move is scheduling, not model math. Chunked-prefills split a long prompt into near-equal pieces that fit a configured token budget. Stall-free batching then builds each iteration so leftover budget is filled with decodes — new requests join without pausing the stream. Same GPUs, same phases colocated; finer prefill grain.

What this paper explains

Every request has two phases:

1. Prefill — process the full prompt in parallel; emit the first output token; materialize the KV cache for the prefix.
2. Decode — emit further tokens one at a time; each step is a full forward over a tiny activation footprint.

Applications feel both clocks. Chat cares about TBT smoothness once tokens start flowing. Capacity planning cares about how many concurrent requests you can sustain under a P99 TBT SLO.

The authors sort prior online schedulers into:

• Prefill-prioritizing (Orca, vLLM-style) — eagerly run prefills when memory allows; great for throughput; risk of generation stalls.
• Decode-prioritizing (classic request-level batching / FasterTransformer-style) — finish ongoing decodes before new prefills; protects TBT; wastes throughput when the batch shrinks.
• Disaggregated (DistServe and kin) — put prefill and decode on different replicas. Related problem, different mechanism — Sarathi-Serve stays colocated.

Prior limits

Iteration-level continuous batching (Orca) already lets requests enter/leave every token step. PagedAttention (vLLM) already fixed fragmented KV memory. Those are necessary — and Sarathi-Serve builds on that world — but they do not by themselves bound how large a prefill you schedule into a live decode batch.

On long-prompt traces (the paper cites openchat / arXiv summarization medians in the thousands of tokens), a hybrid batch that co-schedules a full prefill with decodes still stretches iteration time. Figure 1 in the paper shows Yi-34B on two A100s with multi-second stalls under vLLM on an arXiv-summarisation load. Raising offered load then blows P99 TBT.

Decode-first systems avoid that stall by refusing to admit prefills mid-batch — and then leave decode slots empty when requests finish early. Throughput collapses.

The mechanism

Chunked-prefills. Split prompt $P$ of length $L$ into chunks of size roughly $C$ (near-equal pieces). Each chunk is a smaller compute unit that can share an iteration with decodes.

Token budget. Configure a per-iteration budget $B$ (tokens of work). Schedule:

1. Ongoing decode requests (one token each), and
2. One or more prefill chunks that fill remaining budget up to $B$.

So an iteration’s work is bounded near $B$, almost independent of the original prompt length $L$. Prefill still completes — just across several iterations — while decodes keep streaming.

Stall-free batching. Because chunks are small, admitting a new request does not require pausing the decode cohort for a mega-prefill. Uniform-sized iterations also reduce pipeline bubbles when you run pipeline parallel replicas.

Contrast DistServe: there the fix is move prefill off the decode GPUs. Sarathi-Serve’s fix is shrink what you schedule onto the shared GPUs.

A useful mental model for iteration cost under a hybrid batch is that decode latency grows gently with batch size, while a full prefill of length $L$ can dominate. With chunking, the prefill contribution per iteration is closer to the chunk size $C \approx B - n_{\mathrm{decode}}$ than to $L$:

(The paper’s Figure 9 plots the empirical incremental cost of full vs chunked coalescing — treat those curves as hardware-specific evidence, not universal constants.)

Algorithm / figure walkthrough

1. Pick a token budget $B$ from TBT SLO, model, and hardware (the paper uses Vidur to help choose; examples include $B=256$ on Mistral-7B / one A100 and $B=512$ on LLaMA2-70B / four A100s in Figure 9).
2. When a new prompt arrives and KV memory allows, chunk it instead of scheduling all $L$ tokens in one iteration.
3. Each iteration: pack decodes first (or as policy requires), then add prefill chunks until the budget is spent.
4. Continue until every chunk of the prompt is done; the request then joins the pure-decode cohort.
5. Under pipeline parallelism, more uniform iteration times shrink bubbles between micro-batches / stages.

The opening visual is the same story in three beats: a full prefill stalls the decode lane; chunking splits the prompt; leftover budget piggybacks decodes so tokens keep leaving.

What to notice when reading

• Stall-free is about generation continuity (TBT), not about eliminating prefill compute — you still pay for all prompt tokens, just spread out.
• Chunk size / token budget is a real knob: too large → stalls return; too small → arithmetic intensity and fixed overheads hurt (the paper notes a chunk of 257 vs 256 can already matter on their stack).
• Pipeline-parallel gains come from uniform batches, not from a new parallel algorithm.
• DistServe appears in their taxonomy as a third category — read that section if you are comparing colocated vs disaggregated designs.

Results and evidence

From the abstract / intro (authors’ reported serving-capacity gains vs vLLM under their tail-latency SLO settings — not timeless absolutes):

Evaluation spans Mistral-7B, Yi-34B, LLaMA2-70B, and Falcon-180B with GQA / sliding-window variants as listed in their Table 1, on A100 / A40 configurations. SLOs are defined on P99 TBT relative to an interference-free decode baseline (strict ≈ $5\times$ that decode time; relaxed ≈ $25\times$ — see their Table 3). Figure 9 shows decode+full-prefill hybrid batches costing much more incremental latency than decode+chunked-prefill at the same token budget.

Limitations

Compressed from the paper’s own caveats and operating-point discussion:

• Token budget selection is hardware- and SLO-specific — not a single magic $B$. Pipeline bubbles, arithmetic intensity, and even off-by-one chunk sizes matter.
• Gains are under TBT-oriented SLOs with their trace mix; different product SLOs (strict TTFT-first chat, offline batch) may prefer other schedulers or disaggregation.
• Colocation still shares GPU memory bandwidth between phases; DistServe-style separation remains a competing design when fabric handoff is cheap and dual SLOs are tight.
• Results are for the authors’ vLLM / Orca baselines and listed models — treat multipliers as evidence from that bake-off.

How to read the paper

1. Abstract + §1 — stalls, taxonomy, headline capacity numbers.
2. Background on prefill vs decode and iteration-level batching (Orca).
3. Mechanism sections on chunked-prefills and stall-free schedules (figures comparing vLLM / Orca / FasterTransformer-style behaviors).
4. §5 evaluation — Tables 1–3, capacity under SLO, Figure 9 incremental cost.
5. Related work — where DistServe / FlexGen / vLLM sit relative to this scheduler.
6. Conclusion — two techniques, one tradeoff.

Knowledge check

Keep reading / Sources

• Paper: arXiv:2403.02310 — Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve (MLSys 2024)
• Code: microsoft/sarathi-serve
• Related Fanout Daily: Orca continuous batching, PagedAttention, DistServe
• Precursor technical report: SARATHI chunked prefills (arXiv:2308.16369)