LLM & VLM courseBlog
135Track 5: LLM inference and serving · session 58 of 65

Batching: continuous batching, chunked prefill, split-fuse

LLM requests start and end at different times, so a server that batches whole requests wastes the GPU and makes new users wait. Continuous batching (Orca) rebuilds the batch at every iteration; chunked prefill (Sarathi, Sarathi-Serve) and Dynamic SplitFuse (DeepSpeed-FastGen) cut long prompts into pieces that ride along with the decodes, so nobody’s next token is stalled by someone else’s prompt. This session builds the cost of one mixed iteration and measures the effect on TTFT, time between tokens and throughput in a small simulator.

Time: 3 to 4 hours (reading 2 hours, exercises and code 1 to 2 hours)Level: IntermediateBefore this: Session 84 (batching basics and the step-time model); sessions 78, 80 and 81 (prefill and decode, the KV cache, the metrics)

What you will learn

  • Why request-level batching fails for generation, and how iteration-level scheduling and selective batching (Orca) fix it
  • The cost of one mixed iteration: why about 300 tokens per step on an H100 are almost free and every token after that costs about 16 µs for an 8B model
  • What a generation stall is, and why prefill-first and whole-prefill hybrid schedulers both cause long gaps between tokens
  • How chunked prefill works (Sarathi’s decode-maximal batching, Sarathi-Serve’s stall-free batching), what it costs, and how to pick the token budget from a TBT target
  • Dynamic SplitFuse in DeepSpeed-FastGen, and why equal-sized forward passes are best (a convexity argument)
  • How each scheduler moves TTFT, TBT, TPOT and throughput, measured in a seeded simulator
  • How to run a mixed batch of prefill chunks and decodes in PyTorch and check that it gives exactly the same tokens as running each request alone

Why this matters

A chat server never sees a neat batch. Requests arrive one by one, their prompts have 50 or 5,000 tokens, and their answers end after 10 or 1,000 tokens. If the server batches whole requests, a finished answer leaves an empty row and a new user waits until the longest answer in the batch is done. In a small simulation in this session, that costs a mean time to first token of 4.6 seconds. Rebuilding the batch at every iteration brings it down to 65 ms, and cutting long prompts into chunks brings it to 49 ms, with the longest gap between two tokens of any user going from 113 ms to 9 ms.

In session 84 we built the cost of one batched decode step and saw that batching is the biggest lever on serving cost. We also saw its limit: static and dynamic batching treat a request as one unit, but an LLM request is hundreds of small steps. This session is about batching steps instead of requests. Three ideas, each fixing a problem the previous one left:

  • Continuous batching (also called iteration-level scheduling or in-flight batching; first in Orca, 2022): after every forward pass, finished requests leave and waiting requests join.
  • Chunked prefill (Sarathi, 2023, and Sarathi-Serve, 2024): a long prompt is split into chunks, and each chunk is processed in the same forward pass as the ongoing decodes. This removes the generation stall: the long pause that every running user sees when a new prompt is processed.
  • Dynamic SplitFuse (DeepSpeed-FastGen, 2024): the same split idea, plus packing short prompts so that every forward pass has about the same number of tokens.

All major open serving engines use these ideas: vLLM, SGLang, TensorRT-LLM (which calls it in-flight batching) and Hugging Face TGI implement continuous batching, and vLLM, SGLang and TensorRT-LLM support chunked prefill. [Likely: from their documentation; defaults change between versions.] The survey of efficient inference lists them under system-level serving optimization, in its section on batching. [Certain: Zhou et al., 2024, Section 6.2.] The memory side (PagedAttention) is in session 134, and the policies that decide who goes next (FCFS, preemption, fairness) are in session 136. This session is about the shape of each iteration.

From requests to iterations: continuous batching

The problem with request-level batching

Recall from session 78 that a request has two phases. In prefill, the model reads the whole prompt in one forward pass, writes its KV cache, and produces the first token. In decode, it produces one token per forward pass. A forward pass of the whole model over the current batch is called an iteration.

A request-level scheduler (static batching, or dynamic batching as in Triton) picks a set of requests and runs them together until all of them have finished. Orca’s paper describes the two costs: a request that finishes early cannot return or free its row until the whole batch ends, and a request that arrives after the batch has started must wait until the batch ends before even its prefill can begin. [Certain: Orca, OSDI 2022.] NVIDIA FasterTransformer, the baseline in the Orca paper, worked this way.

Iteration-level scheduling

Orca’s fix is simple to say. The scheduler does not hand the engine a batch of requests. It hands it one iteration at a time, and it picks the set of requests again before every iteration:

\[ \mathcal{B}_{s+1} \;=\; \big(\mathcal{B}_s \setminus \mathcal{F}_s\big) \,\cup\, \mathcal{A}_s, \qquad |\mathcal{B}_{s+1}| \le B_{\max} \tag{135.1} \]
Read the symbols
\(\mathcal{B}_s\)
the set of requests in iteration \(s\) (the running batch)
\(\mathcal{F}_s\)
the requests that finished in iteration \(s\): they produced an end-of-sequence token or reached their length limit. Their result is returned at once and their KV cache is freed
\(\mathcal{A}_s\)
the waiting requests admitted for the next iteration, usually first come, first served
\(B_{\max}\)
the largest batch the engine allows; in practice it is set by the KV-cache memory (formula 84.7) and by a maximum number of sequences

Nothing waits for a whole batch any more. A short answer leaves after its last token, and its row is reused at the next iteration. This is exactly the “refill” mode of Figure 3 in session 84, which removed most of the padding waste of static batching without knowing the answer lengths in advance.

Selective batching: how a ragged batch runs on a GPU

There is a technical problem. In one iteration, request R1 may bring a prompt of 900 tokens, R2 one decode token at position 40, and R3 one decode token at position 2,000. Their tensors have different shapes, and the old way (pad everything to one rectangle) would waste most of the work. Orca’s answer is selective batching: batch only the operations where batching is easy. [Certain: Orca abstract.]

  • For the matrix multiplies (QKV projection, output projection, the FFN), the position of a token does not matter. So all new tokens of all requests are stacked into one matrix of shape \((\sum_i n_i,\, d)\), with no padding, and each weight matrix is applied once. This is where batching saves weight reads.
  • For attention, each request needs its own keys and values. So the stacked matrix is split by request, each part attends to its own KV cache, and the outputs are merged back into one matrix.
new tokens of one iteration R1 t1 R1 t2 R1 t3 R1 t4 R2 t1 R3 t1 (6, d) stacked R1: 4-token prefill chunkR2, R3: one decode token each QKV GEMMone matmul(6, d)·(d, 3d) attention R14 new + 9 cached keys attention R21 new + 20 cached attention R31 new + 7 cached split: each request reads its own KV cache merge (6, d)output proj + FFNone matmul each Weights are read once per iteration for all 6 tokens. Only attention is per request. No padding: requests of any length and in any phase share the same step.
Figure 1. Selective batching in one iteration with a 4-token prefill chunk (R1) and two decodes (R2, R3). The six new tokens are stacked with no padding. The QKV projection, output projection and FFN each run as one matrix multiply over all six rows, so each weight is read once. Attention is done per request, because each request has its own KV cache of a different length. Modern engines do the per-request attention in one “varlen” or paged kernel rather than a loop, but the idea is the same.

Selective batching is what makes iteration-level scheduling work on a GPU, and it is what makes the next two ideas possible: once the batch is a flat list of tokens, a prefill chunk and a decode token are just rows of the same matrix. Today’s engines do the split attention with one kernel that reads each request’s cache through a block table (PagedAttention, FlashInfer, FlashAttention’s variable-length mode; see session 125).

Orca reported a 36.9 times throughput improvement over FasterTransformer on GPT-3 175B at the same latency. [Certain: Orca abstract, OSDI 2022.] Most of that gain comes from not waiting for whole batches, so the GPU always has a full batch of useful work.

Algorithm 1: iteration-level scheduling (continuous batching)
  1. state: waiting queue \(W\) (FCFS), running set \(\mathcal{B}\), KV-cache pool
  2. loop (one pass per model iteration):
  3.   move newly arrived requests into \(W\)
  4.   while \(W\) is not empty and \(|\mathcal{B}| \lt B_{\max}\) and the KV pool has room for the head of \(W\): move it into \(\mathcal{B}\) // admission
  5.   build the iteration: one token for each request in decode, the prompt (or a chunk of it) for each request in prefill
  6.   run one forward pass with selective batching; sample one token for each request whose prompt is complete
  7.   for each request that produced end-of-sequence or reached its limit: return it, free its KV blocks, remove it from \(\mathcal{B}\) // formula (135.1)

Line 5 hides the question that the rest of this session answers: how much prefill should one iteration carry? Orca puts whole prompts into the iteration. vLLM, in its original design, ran prefill-only iterations and decode-only iterations, and gave priority to new prefills. [Certain: Sarathi-Serve describes Orca as allowing hybrid prefill-and-decode batches, and vLLM batches as all-prefill or all-decode, both admitting new prefills eagerly.] Both choices cause a problem we can now measure.

What one iteration costs

We reuse the cost model of session 84 (formula 84.1) and extend it to an iteration that mixes decodes and prefill chunks. Let the iteration carry \(B\) decodes, decode \(i\) with \(T_i\) tokens in its cache, and some prefill chunks, chunk \(k\) with \(c_k\) new tokens after \(j_k\) tokens of the same prompt that are already cached (\(j_k = 0\) for a first or whole prefill). The number of tokens in the iteration is

\[ n \;=\; B + \sum_k c_k \tag{135.2} \]

The weights are read once for all \(n\) tokens. Every token needs about \(2N\) FLOPs for the matrix multiplies. Attention adds work that depends on how many keys each new token sees, and every request reads its own cache. The iteration takes at least the larger of the compute time and the memory time:

\[ t \;=\; \max\!\left( \frac{2Nn + 4 L d \Big[\sum_i T_i + \sum_k c_k \big(j_k + \tfrac{c_k}{2}\big)\Big]}{\pi},\;\; \frac{bN + s_{\text{kv}} \Big[\sum_i T_i + \sum_k (j_k + c_k)\Big]}{\beta} \right) \tag{135.3} \]
Read the symbols
\(N\), \(b\)
number of parameters and bytes per weight; \(bN\) is the weight bytes, 16.06 GB for Llama 3 8B in BF16
\(L\), \(d\)
number of layers and the attention width (32 and 4,096 for Llama 3 8B)
\(4Ld\,T_i\)
attention FLOPs of one decode token over \(T_i\) cached positions (\(QK^\top\) plus the weighted sum of values, in all layers)
\(4Ld\,c_k(j_k + c_k/2)\)
attention FLOPs of a chunk: each of its \(c_k\) tokens sees the \(j_k\) earlier tokens plus, on average, half of the chunk (causal mask)
\(s_{\text{kv}}\)
KV-cache bytes per token, \(2 L n_{kv} d_h b = 131{,}072\) for Llama 3 8B
\(\pi\), \(\beta\)
peak compute and memory bandwidth: 989 TFLOP/s (dense BF16) and 3.35 TB/s for an H100 SXM

This is a lower bound from the roofline; it assumes perfect overlap of compute and memory and peak speed. Real kernels are slower, and the gap is larger for small, odd-shaped batches. We use it because it shows the shape of the trade-off with numbers anyone can check.

The knee: about 300 tokens are almost free

Ignore attention and the KV reads for a moment. Then the memory time is the weight-read time \(t_w = bN/\beta\), which does not depend on \(n\), and the compute time is \(2Nn/\pi\), which grows with \(n\). They are equal at

\[ n^{*} \;=\; \frac{bN/\beta}{2N/\pi} \;=\; \frac{b\,\pi}{2\,\beta} \tag{135.4} \]

For BF16 on an H100, \(n^{*} = 2 \times 989 / (2 \times 3.35) = 295\) tokens. Note that \(N\) cancels: the knee depends only on the hardware and the number format. An iteration with fewer than about 295 tokens is memory-bound and takes about \(t_w = 4.79\) ms for Llama 3 8B, however many tokens it has. Above the knee, every extra token costs \(2N/\pi = 16.2\,\mu\)s. A decode batch of 32 users has only 32 tokens, so it uses about a tenth of the compute that the weight read pays for. That idle compute is the opportunity: prefill tokens can fill it. This is the main observation of the Sarathi paper. [Certain: Sarathi abstract: decodes “piggyback” on a prefill chunk at a much lower cost than a decode-only batch.]

Worked example: what a prefill costs inside a decode iteration

Llama 3 8B on one H100, 32 users in decode, each with 1,024 tokens in its cache. Formula (135.3):

Decode only. Memory: \(16.06 + 32 \times 1024 \times 131{,}072 / 10^9 = 20.36\) GB, so 6.08 ms. Compute: \(5.31 \times 10^{11}\) FLOPs, only 0.54 ms. The iteration is memory-bound by a factor of 11.

Plus a 256-token chunk: 6.09 ms. Plus up to 340 tokens: still below the memory time, so they are free (6.09 ms). The knee is higher than 295 here because the 32 caches add to the memory time.

Plus a 512-token chunk: 8.92 ms. Plus a whole 2,048-token prompt: 34.9 ms, 5.7 times longer than the decode-only iteration. Every one of the 32 users waits 34.9 ms for their next token instead of 6.1 ms.

Figure 2 lets you move the decode batch, the context length and a target for the time between tokens.

iteration time (the max)compute timememory timeTBT target
Figure 2. Formula (135.3) for Llama 3 8B in BF16 on one H100 SXM (989 TFLOP/s, 3.35 TB/s): one iteration with \(B\) decodes at context \(T\) plus one prefill chunk of \(c\) tokens with no earlier cached part (\(j = 0\)). The green dot marks the last “free” chunk size, where the compute time reaches the memory time. The open circle marks the largest chunk that keeps the iteration within the TBT target; \(K = B + c\) is then the token budget of formula (135.6). Roofline lower bounds; real kernels are slower.
How to read Figure 2

The thick curve is flat at first (memory-bound: the weight read dominates) and then rises in a straight line (compute-bound: every token costs about 16 µs). With the defaults (32 decodes, \(T = 1024\), target 10 ms), the decode-only iteration takes 6.08 ms, 340 prefill tokens are free, and the largest iteration under 10 ms carries 577 prefill tokens, so \(K = 609\). Set \(B = 0\): the knee moves to 294 tokens, close to formula (135.4). Set \(T = 4096\): the 32 caches make the memory time 9.9 ms and the free part grows to 570 tokens; a 10 ms target now allows 574 prefill tokens, almost exactly the free part, because the decode-only iteration already takes 9.92 ms. Set the target to 5 ms with 32 decodes: no iteration can meet it.

The problem left by continuous batching: generation stalls

Continuous batching admits a new request at the next iteration. But its prompt must be prefilled, and a long prefill is a long iteration. The two original designs handle this differently, and both hurt the users who are already decoding:

  • Prefill-first, separate iterations (original vLLM): when a request is waiting, the next iteration is a prefill-only iteration. The decodes are simply paused. Their next token comes after the prefill and the next decode iteration.
  • Hybrid iterations with whole prompts (Orca): the new prompt is added to the decode iteration. The decodes are not paused, but the iteration becomes as long as the prefill.

Sarathi-Serve calls this a generation stall, and notes that one stall can last several seconds for long prompts on large models. [Certain: Sarathi-Serve.] For the users who are decoding, the gap between two tokens is

\[ \text{TBT}_{\text{stall}} \;\approx\; \underbrace{t_{\text{pre}}(P)}_{\text{prefill-first}} + \; t_{\text{dec}}(B) \qquad\text{or}\qquad t\big(B \text{ decodes} + P\big) \;\approx\; \frac{2N(P + B) + 2LdP^2}{\pi} \;\;\text{(hybrid)} \tag{135.5} \]
Read the symbols
\(P\)
the number of prompt tokens of the new request
\(t_{\text{pre}}(P)\)
the time of a prefill-only iteration, which is compute-bound for \(P\) above a few hundred
\(2LdP^2\)
the causal attention FLOPs of the whole prompt, \(4Ld \cdot P \cdot P/2\)

With 32 decodes at \(T = 1024\) and a new 2,048-token prompt: prefill-first gives \(34.37 + 6.08 = 40.4\) ms; the hybrid iteration gives 34.9 ms. The normal gap is 6.08 ms. And this happens every time any user sends a prompt. With many users, some prompt arrives almost every few iterations, so the tail of the gap distribution (p99 TBT) is set by prefills, not by decodes.

Sarathi-Serve sorts schedulers into two groups. Decode-prioritizing schedulers (request-level batching, as in FasterTransformer) never stall a decode but admit new requests only when a batch is finished, so TTFT is long and throughput is low. Prefill-prioritizing schedulers (Orca, vLLM) admit new prompts at once, which gives high throughput and short TTFT, but causes stalls. [Certain: Sarathi-Serve.] Before chunked prefill, you had to choose between good TTFT and good TBT.

Figure 3 makes this concrete. It runs eight requests through a small server with \(B_{\max}\) slots, one iteration at a time, and prices every iteration with formula (135.3) for Llama 3 8B on an H100. A (prompt 512 tokens, 9 output tokens), B (256, 3) and C (1,024, 6) arrive at 0 ms; D (2,048, 5) at 8 ms; E (128, 4) at 16 ms; F (768, 7) at 26 ms; G (384, 3) at 40 ms; H (1,536, 4) at 55 ms. The simulation runs in your browser; nothing is pre-recorded. Each iteration is shown in four steps that follow the four phases of Algorithm 1: admission, building the iteration, running it, and retiring finished requests.

prefill (whole prompt or chunk)decode (one token)padding (finished row still computed)paused or no room
  1. move arrived requests \((a_i \le t)\) into the queue \(W\)
  2. run one forward pass (selective batching): \(t \leftarrow t + t_{\text{iter}}\) // formula (135.3)
  3. emit one token per finished prompt or decode; finished requests leave and free their slot // (135.1)
Figure 3. Continuous batching, animated. Top: the waiting queue and the clock. Middle: the GPU slots; each slot shows its request’s prefill progress (orange bar) and its output tokens (blue squares), and, during the build and run steps, what it adds to this iteration. Right: the tokens of this iteration, decode (blue) plus prefill (orange), against the knee of about 295 tokens (formula 135.4). Bottom: the timeline; each column is one iteration and its width is its time. The live panel puts the current numbers into formulas (135.1) to (135.3); the table compares the final TTFT, longest gap and throughput of all four schedulers. Roofline cost; real kernels are slower.
How to read Figure 3

Start with Request-level and press Play. A, B and C are prefilled together (29.5 ms). B finishes after 3 tokens, but its row keeps running as padding until A’s ninth token, and D, E, F, G wait in the queue even though slots are idle. They join only at 68.4 ms, in one 55.4 ms prefill iteration; D’s first token comes 115.7 ms after it arrived. No gap between tokens is longer than 4.9 ms, but the mean TTFT is 77.1 ms and the run takes 193.4 ms. Switch to Orca hybrid: D joins in iteration 2, but its whole 2,048-token prompt makes that iteration 34.4 ms long, and A, B and C wait that long for their next token. Mean TTFT drops to 51.8 ms, throughput rises from 212 to 269 tokens/s. Prefill-first pauses the decodes (red) in every prefill iteration; the worst gap is 39.3 ms. Now choose Chunked prefill with \(K = 256\): every iteration carries about 256 tokens, below the knee, so each takes 4.8 to 4.9 ms. D’s prompt goes through in nine chunks next to the decodes, the worst gap is 4.9 ms, the mean TTFT is 50.5 ms and the throughput 281 tokens/s, the best of the four. Try \(K = 128\): the prompts starve and the mean TTFT rises to 115.6 ms. Try \(K = 1{,}024\): the gaps grow to 17.0 ms. With \(B_{\max} = 2\) the slots become the limit: chunked prefill and Orca end with almost the same mean TTFT (69.1 and 68.5 ms). With \(B_{\max} = 6\), Orca’s worst gap grows to 49.1 ms, because more whole prompts enter one iteration, while chunked prefill stays at 4.9 ms.

Chunked prefill: Sarathi and Sarathi-Serve

The idea

Split each prompt into chunks of \(c\) tokens and process one chunk per iteration, together with the decodes. The chunk writes its keys and values into the KV cache; the next chunk attends to everything cached so far plus itself, with a causal mask inside the chunk. After the last chunk, the logits of the last prompt token give the first output token. The result is exactly the same as a whole prefill (up to floating-point rounding), because causal attention for token \(t\) only ever needs the keys and values of tokens \(\le t\). The PyTorch code below checks this.

Sarathi (2023) builds each batch around one prefill chunk and fills the rest with decodes, which it calls decode-maximal batching. [Certain: Sarathi paper.] It reports up to 10 times higher decode throughput and up to 1.33 times higher end-to-end throughput for LLaMA-13B on an A6000, and 1.25 times end-to-end (up to 4.25 times decode) for LLaMA-33B on an A100. With pipeline parallelism on GPT-3, the uniform batches cut pipeline bubbles by 6.29 times, for 1.91 times end-to-end throughput. [Certain: Sarathi abstract.]

Sarathi-Serve (2024) turns this into a serving scheduler with latency targets. Its stall-free batching puts all ongoing decodes into the iteration first, then fills the remaining token budget \(K\) with prefill chunks: first the chunks of prompts that are already partly done, then new requests. A decode is never paused for a prefill, and no iteration has more than \(K\) tokens. [Certain: Sarathi-Serve.]

Choosing the token budget

Sarathi-Serve sets the budget to the largest number of tokens that can be packed into a batch without violating the TBT target, found by profiling. [Certain: Sarathi-Serve.] With our cost model:

\[ K(\tau) \;=\; \max\big\{\, n \;:\; t(n) \le \tau \,\big\}, \qquad \text{chunk room in an iteration} = K - B \tag{135.6} \]
Read the symbols
\(\tau\)
the TBT target (the service-level objective for the gap between tokens)
\(t(n)\)
formula (135.3) for an iteration of \(n\) tokens: the current decodes plus \(n - B\) prefill tokens
\(K - B\)
how many prefill tokens this iteration may carry; it shrinks as the decode batch grows

For 32 decodes at \(T = 1024\) on an H100: \(\tau = 8\) ms gives \(K = 488\), \(\tau = 10\) ms gives \(K = 609\), and \(\tau = 20\) ms gives \(K = 1{,}207\) (Figure 2). Sarathi-Serve used \(K = 512\) for its strict TBT targets and \(K = 2{,}048\) for relaxed ones (1,536 for LLaMA2-70B, to reduce pipeline bubbles). [Certain: Sarathi-Serve, evaluation setup.] Two more practical rules:

  • Align chunks with GPU tiles. Matrix-multiply kernels work on tiles of, for example, 128 or 256 rows. A chunk of 257 tokens needs a second, almost empty tile. Sarathi-Serve measured that a chunk size of 257 can increase prefill time by 32% compared with 256. [Certain: Sarathi-Serve.] This is the tile-quantization effect of session 126.
  • Small chunks have a cost. Each chunk must read the KV cache of all earlier chunks of its prompt. The next part computes how much.

The cost of chunking

Split a prompt of \(P = mc\) tokens into \(m\) chunks of \(c\). Chunk \(k\) (counting from 0) has \(j = kc\) earlier tokens. Sum the attention FLOPs of all chunks and the KV bytes they read:

\[ \sum_{k=0}^{m-1} 4Ld\, c\Big(kc + \frac{c}{2}\Big) = 4Ld\,\frac{P^2}{2}, \qquad \sum_{k=0}^{m-1} s_{\text{kv}}\,(kc + c) \;=\; s_{\text{kv}}\, c\,\frac{m(m+1)}{2} \;\approx\; s_{\text{kv}}\,\frac{P^2}{2c} \tag{135.7} \]

The attention FLOPs are exactly the same as for one whole prefill: chunking moves work, it does not add work. The memory traffic does grow: instead of writing \(P\) cache entries once, the chunks read the earlier cache again and again, about \(P^2/(2c)\) entries in total. (Sarathi-Serve notes that the KV cache of the first chunk is read \(m - 1\) more times. [Certain].) The weights are also read once per chunk instead of once, but those reads are shared with the decodes, which needed them anyway.

Figure 4 runs this on a toy prompt of 12 tokens and one attention head, with real numbers. Each chunk computes its rows of the causal mask: the green cells use keys that come from the cache, the orange cells use keys of the chunk itself. A real kernel computes the two parts separately and merges them with the online-softmax rule of session 124: for one row with cache part \((m_c, \ell_c, o_c)\) and chunk part \((m_n, \ell_n, o_n)\), it takes \(m = \max(m_c, m_n)\), \(\ell = e^{m_c - m}\ell_c + e^{m_n - m}\ell_n\) and \(o = (e^{m_c - m}\ell_c\,o_c + e^{m_n - m}\ell_n\,o_n)/\ell\). The figure does exactly this and compares every row with a whole prefill.

key read from the KV cachekey of the current chunk (causal)row already computedmasked (future key)
  1. \(j \leftarrow 0\) // tokens of this prompt already in the cache
  2. while \(j \lt P\): take the next chunk, positions \(j, \dots, j + c - 1\)
  3. project its tokens to \(q, k, v\) (with positions \(j, \dots, j + c - 1\))
  4. attend to the cache: keys \(0, \dots, j - 1\) // green
  5. attend inside the chunk with a causal mask; merge the two parts // orange
  6. append the chunk’s \(k, v\) to the cache; \(j \leftarrow j + c\)
  7. the last row of the last chunk gives the logits of the first output token
Figure 4. Chunked prefill of one 12-token prompt on a toy attention head (\(d = 2\), fixed seeded queries, keys and values). Left: the causal mask, one chunk at a time. Right: the prompt’s KV cache (thick cells are read, orange cells are written) and three running sums: the exact number of (query, key) pairs, the terms \(c(j + c/2)\) of formula (135.7), and the KV-cache entries touched, \(\sum (j + c)\). The live panel shows the cache part, the chunk part and the merged output of the chunk’s last row, next to the output of a whole prefill.
How to read Figure 4

With \(c = 4\) there are three chunks. Chunk 1 has no cache, so it is an ordinary causal prefill of rows 0 to 3 (10 pairs). Chunk 2 reads the 4 cached keys (green) and its own causal block (orange): \(4 \cdot 4 + 10 = 26\) pairs. Chunk 3 adds \(4 \cdot 8 + 10 = 42\). Total 78, the same as a whole prefill, and the formula (135.7) terms add up to 72 = \(P^2/2\) for every chunk size: chunking moves work, it does not add work. The KV-cache counter does grow: 4 + 8 + 12 = 24 entries instead of 12, and 78 with \(c = 1\) (that is plain decoding of the prompt, token by token). The merged outputs agree with the whole prefill to about \(10^{-16}\): the result is exact up to floating-point rounding.

Worked example: a 4,096-token prompt in chunks of 512

Cost of chunking. \(m = 8\). A whole prefill writes \(4096 \times 131{,}072 = 0.54\) GB of cache. The chunks touch \(131{,}072 \times 512 \times 36 = 2.42\) GB, so 1.88 GB extra, which is 0.56 ms at 3.35 TB/s. A whole prefill is compute-bound at 71.0 ms, so in the roofline model the extra reads hide under the compute completely: eight chunks alone also take 71.0 ms. On real hardware the overhead is larger, because attention kernels run less efficiently on short chunks: Sarathi-Serve measured at most about 25% extra prefill time with chunks of 512 on Yi-34B, and almost none with 2,048. [Certain: Sarathi-Serve.]

Effect on TTFT. With 32 decodes at \(T = 1024\) and \(K = 512\), each iteration has room for 480 prefill tokens, so the prompt needs \(\lceil 4096/480 \rceil = 9\) iterations of about 8.5 ms: 76.8 ms in total. In one hybrid iteration it would take 71.5 ms, but that iteration would stall the 32 other users for 71.5 ms. Chunking costs this request 5.3 ms of TTFT (7%) and saves every other user a 71.5 ms gap.

In general, for a request that arrives to a queue with waiting time \(W\), the TTFT under chunked prefill is about

\[ \text{TTFT} \;\approx\; W + \sum_{k=1}^{m} t_k, \qquad m = \left\lceil \frac{P}{K - B} \right\rceil \tag{135.8} \]

where \(t_k\) is the time of the \(k\)-th iteration that carries a chunk of this prompt. This is the trade-off in one line: a small budget keeps every \(t_k\) short (good TBT for everyone) but needs many iterations (long TTFT, and more KV re-reads); a large budget gives short TTFT for the new request but long gaps for the others. When \(B\) approaches \(K\), the prefill room \(K - B\) goes to zero and new requests starve. That is why the budget must be clearly larger than the decode batch.

Algorithm 2: stall-free batching with a token budget (Sarathi-Serve style)
  1. input: running decodes \(D\), partly prefilled requests \(Q\), waiting queue \(W\), token budget \(K\), \(B_{\max}\)
  2. batch \(\leftarrow\) one token for every request in \(D\); \(\;r \leftarrow K - |D|\) // decodes first: never stalled
  3. for each request \(q\) in \(Q\) (oldest first) while \(r \gt 0\):
  4.   \(c \leftarrow \min(r,\ \text{remaining prompt of } q)\); add the next \(c\) prompt tokens of \(q\); \(r \leftarrow r - c\)
  5. while \(r \gt 0\) and \(W\) not empty and \(|D| + |Q| \lt B_{\max}\) and the KV pool has room:
  6.   move the head of \(W\) into \(Q\); add its first \(\min(r, P)\) prompt tokens; reduce \(r\)
  7. run the iteration (selective batching, formula 135.3); a request whose last chunk was in it gets its first token and moves to \(D\)

Dynamic SplitFuse in DeepSpeed-FastGen

DeepSpeed-FastGen (2024) arrived at almost the same scheduler from a throughput point of view. Its paper makes three observations about a forward pass [Certain: DeepSpeed-FastGen paper]:

  • The time of a forward pass depends mainly on the number of tokens in it; how those tokens are split among sequences has a negligible effect.
  • Throughput rises with the number of tokens at first and then saturates: a memory-bound region and a compute-bound region, the knee of formula (135.4).
  • Because the throughput curve is concave, a fixed amount of work is processed fastest when it is divided into passes of equal size.

From this follows Dynamic SplitFuse: long prompts are split into smaller chunks spread over several forward passes, with only the final pass producing a token, and short prompts are composed (fused) to fill a target token budget exactly; a short prompt may also be split so the pass has exactly the target size. [Certain: DeepSpeed-FastGen.] The third observation has a short proof. Write the time of a pass as a function \(t(n)\) of its token count. With our cost model, \(t\) is the maximum of functions that are linear or convex in \(n\), so it is convex. For \(m\) passes that together process a fixed number of tokens, Jensen’s inequality gives

\[ \sum_{k=1}^{m} t(n_k) \;\ge\; m\; t\!\left(\bar n\right), \qquad \bar n = \frac{1}{m}\sum_{k=1}^{m} n_k \tag{135.9} \]

Equal passes are never slower than unequal ones. Intuition: a small pass wastes the compute that its weight read paid for (it sits on the flat part of Figure 2), and a large pass pays full price for every token above the knee. For Llama 3 8B on an H100, two passes with 580 and 20 tokens take 14.30 ms; two passes with 300 tokens each take 9.79 ms, for the same 600 tokens.

Figure 5 shows the split and the fuse at work. Eight prompts (1,800, 300, 120, 900, 60, 700, 2,400 and 220 tokens; 6,500 in total) wait while \(B\) users decode. Three policies prefill them, each pass priced with formula (135.3). Whole prompts puts one whole prompt into each pass, as Orca does. Split only cuts long prompts to fit the budget but puts at most one prompt into a pass, so a short prompt gets a short pass. Dynamic SplitFuse also fuses: after a piece of one prompt, the rest of the budget is filled with the next prompts.

decode tokens in the passprompt pieces (one color per prompt)current SplitFuse pass and the clock
  1. add one token for each of the \(B\) decodes; \(r \leftarrow K - B\)
  2. for each waiting prompt, oldest first, while \(r \gt 0\):
  3. \(c \leftarrow \min(r, \ell)\), where \(\ell\) = tokens left in the prompt // split a long one
  4. add its next \(c\) tokens; \(r \leftarrow r - c\) // then fuse the next one
  5. run the pass: \(n = K - r\) tokens, time \(t(n)\) // formula (135.3)
  6. a prompt whose last piece ran emits its first token // here \(B\) stays fixed
Figure 5. Dynamic SplitFuse, pass by pass, for Llama 3 8B on an H100 with \(B\) decodes at context 1,024 in every pass. Top: the prompt queue; the outlined part of a bar is already prefilled, the black frame marks the piece taken by the current pass. Bottom: three timelines on the same time axis; a column is one pass, its width is the pass time and its colors show what the pass contains. The dashed line is the clock of the SplitFuse pass being played; the other two rows show what they have done by that time. The table gives the totals and both sides of formula (135.9), using the simple pass time \(\tilde t(n) = \max(2Nn/\pi,\ (bN + s_{\text{kv}}BT)/\beta)\).
How to read Figure 5

With the defaults (\(K = 512\), \(B = 16\)) every SplitFuse pass has exactly 512 tokens, except the last one: 14 passes, 116.41 ms in total, and no pass longer than 8.80 ms. Whole prompts need only 8 passes but they are very unequal (76 to 2,416 tokens): 119.76 ms in total, and the pass with the 2,400-token prompt holds every decoding user for 40.77 ms. Split only keeps the gaps short (8.78 ms) but wastes passes on the short prompts: 17 passes and 123.99 ms. The last column of the table is formula (135.9) for each policy: for the whole-prompt passes, \(\sum \tilde t(n_k) = 116.96\) ms against \(m\,\tilde t(\bar n) = 107.63\) ms, so their unequal sizes cost about 9 ms. Try \(K = 256\): all passes are below the knee, each one pays a full weight read for few tokens, and SplitFuse needs 153.31 ms. Try \(B = 0\): SplitFuse at \(K = 512\) then meets the Jensen bound exactly (105.55 ms on both sides), because all its passes, even the shorter last one, are above the knee, where \(\tilde t\) is a straight line.

So Sarathi-Serve and Dynamic SplitFuse are two routes to the same iteration shape: decodes plus a fixed-size share of prefill chunks. Sarathi-Serve derives the size from a latency target; DeepSpeed-FastGen derives it from the throughput curve. [Likely: this is our reading of the two papers; the implementations differ in details such as how many prompts may share one pass.] DeepSpeed-FastGen reports up to 2.3 times higher effective throughput, about 2 times lower average latency and up to 3.7 times lower token-level tail latency than vLLM, on Llama 2 models (for example, Llama 2 70B with tensor parallelism on four A100-80GB GPUs). [Certain: DeepSpeed-FastGen abstract and evaluation; the vLLM version compared was the one of late 2023, before vLLM added chunked prefill.] Sarathi-Serve reports, under tail-latency targets and also against vLLM, 2.6 times higher serving capacity for Mistral-7B on one A100, up to 3.7 times for Yi-34B on two A100s, and up to 5.6 times for Falcon-180B with pipeline parallelism. [Certain: Sarathi-Serve abstract.]

Effect on TTFT, TPOT and throughput

The metrics

session 81 defined the latency metrics. Here we need them per request. Request \(i\) arrives at \(a_i\) and its tokens appear at times \(\tau_{i,1} \lt \tau_{i,2} \lt \dots \lt \tau_{i,n_i}\):

\[ \text{TTFT}_i = \tau_{i,1} - a_i, \qquad \text{TBT}_{i,k} = \tau_{i,k} - \tau_{i,k-1}, \qquad \text{TPOT}_i = \frac{\tau_{i,n_i} - \tau_{i,1}}{n_i - 1}, \qquad X = \frac{\sum_i n_i}{\text{time span}} \tag{135.10} \]
Read the symbols
TTFT
time to first token: queueing plus the whole prefill (all chunks)
TBT
time between tokens: one gap; its tail (p99, max) shows stalls
TPOT
time per output token: the average gap of one request; a mean can hide a few long stalls, which is why Sarathi-Serve targets the p99 of TBT
\(X\)
throughput: output tokens per second over the whole run

Each scheduler moves these numbers in a different direction:

SchedulerTTFTTBT tailThroughput
Request-level batching (FasterTransformer)Very long: new requests wait for the whole batchLow: decodes are never interruptedLow: rows idle while the batch drains
Continuous, prefill-first (vLLM before chunking)Short at low loadLong: decodes pause for every prefillHigh
Continuous, hybrid with whole prompts (Orca)ShortLong: the iteration is as long as the prefillHigh
Chunked prefill, stall-free (Sarathi-Serve, SplitFuse)Short if \(K\) is not too small; slightly longer for one long promptBounded by \(K\): about \(t(K)\)High; compute and memory overlap in every iteration

A small serving simulator

Figure 6 runs all four schedulers on the same seeded trace of 200 requests with formula (135.3) as the cost of each iteration. Prompt lengths are log-uniform between 64 and 4,096 tokens (mean 830), output lengths are exponential with mean 128 (cut to 8 to 512; mean 108), arrivals are Poisson, at most 64 requests run at once, and the whole-prompt schedulers put at most 8,192 prompt tokens into one iteration.

decode tokensprefill tokensiteration length
Figure 6. A seeded event simulation of one Llama 3 8B server on an H100 (roofline cost of formula 135.3; real engines are slower, so read the numbers as a comparison, not as a prediction). Top: the tokens in each iteration between 1.0 and 1.5 s, split into decode and prefill tokens (square-root scale). Bottom: the length of each iteration, which is the gap every running user sees before their next token. Metrics are over all 200 requests.
How to read Figure 6

Start with Orca at 45 requests/s: tall orange bars are whole prompts, and the iteration length jumps each time one is processed; mean TTFT is 64.6 ms, p99 TBT 68.0 ms, the longest gap 112.9 ms, throughput 3,326 tokens/s. Switch to prefill-first: the decodes now pause during prefill-only iterations, and the p99 TBT rises to 138.5 ms (max 315.7 ms), with TTFT 132.4 ms. Switch to request-level: no stalls at all (p99 TBT 7.4 ms), but the mean TTFT is 4,650 ms and throughput drops to 1,444 tokens/s. Now choose chunked prefill with \(K = 512\): every iteration has about 512 tokens, the gaps stay near 9 ms (p99 9.06 ms), TTFT is 49.1 ms and throughput 3,511 tokens/s. Move \(K\) to 128: the decodes use almost the whole budget, prompts starve, and TTFT explodes to about 1.8 s. Lower the rate to 12/s: all continuous schedulers reach the same throughput (about 1,290 tokens/s, the offered load), but their TBT tails still differ.

Three results from the simulator are worth remembering. First, at moderate and high load, chunked prefill with a sensible budget improves the TBT tail by almost an order of magnitude and does not hurt TTFT or throughput. In this model it even helps both, because every iteration overlaps the memory-bound decodes with compute-bound prefill tokens, instead of alternating memory-bound and compute-bound iterations. Second, the budget has a sweet spot: too small and prompts starve; too large and the stalls return. Third, at low load all continuous schedulers give the same throughput (they all keep up with the traffic), and the differences are only in latency. Figure 7 sweeps the budget.

mean TTFT (chunked)p99 TBT (chunked)TBT target
Figure 7. The simulator of Figure 6 with chunked prefill for nine token budgets from 128 to 4,096 (log scales; values above 10 s are cut). Dashed lines: Orca with whole prompts at the same load. The green circle is the budget with the lowest mean TTFT among those that meet the p99 TBT target, which is how Sarathi-Serve frames the choice.
How to read Figure 7

At 45 requests/s the blue curve (p99 TBT) rises steadily with \(K\): 5.7 ms at 128, 9.1 ms at 512, 35.5 ms at 2,048, and at 4,096 it meets Orca’s 68 ms, because almost no prompt is longer than 4,096 tokens and chunking stops. The orange curve (TTFT) is U-shaped: 1.76 s at 128 (starvation), about 49 ms between 384 and 1,024, then slowly up towards Orca’s 64.6 ms. With a 10 ms target the best budget is 512 (TTFT 49.1 ms). Tighten the target to 6 ms: only 128 qualifies, at a TTFT of 1.76 s; a 7 ms target allows 384 (49.6 ms). At 60 requests/s the starvation part widens: 256 now gives a mean TTFT of 448 ms.

The code

The first program is a tiny serving engine in PyTorch. One function, step, runs one iteration over any mix of prefill chunks and decode tokens, with selective batching: all new tokens are stacked for the linear layers, attention is done per request with its own KV cache and a causal mask that is offset by the number of cached tokens. A stall-free scheduler with a token budget of 6 serves three requests that arrive at different iterations. At the end, the program checks that every request got exactly the tokens and logits it gets when run alone with a whole prefill. It runs on a CPU in about a second.

import torch, torch.nn.functional as F
torch.manual_seed(0)
torch.set_default_dtype(torch.float64)            # float64: batched and single runs agree to ~1e-15
V, d, H, L = 64, 32, 4, 2                         # vocab, width, heads, layers
dh = d // H

class Block(torch.nn.Module):
    def __init__(s):
        super().__init__()
        s.n1, s.n2 = torch.nn.LayerNorm(d), torch.nn.LayerNorm(d)
        s.qkv, s.o = torch.nn.Linear(d, 3 * d), torch.nn.Linear(d, d)
        s.ff = torch.nn.Sequential(torch.nn.Linear(d, 4 * d), torch.nn.GELU(), torch.nn.Linear(4 * d, d))

class TinyLM(torch.nn.Module):
    def __init__(s):
        super().__init__()
        s.emb, s.pos = torch.nn.Embedding(V, d), torch.nn.Embedding(128, d)
        s.blocks = torch.nn.ModuleList([Block() for _ in range(L)])
        s.head = torch.nn.Linear(d, V)

model = TinyLM().eval()

@torch.no_grad()
def step(work, cache):
    """One engine iteration. work: list of (rid, new_token_ids); any mix of prefill chunks and decodes.
    cache[rid] = list of L (K, V) pairs, each (H, T_cached, dh). Returns the last logits of each item."""
    sizes = [len(t) for _, t in work]
    starts = [cache[r][0][0].shape[1] if r in cache else 0 for r, _ in work]
    ids = torch.tensor([x for _, t in work for x in t])                       # flat: (n_tok,)
    pos = torch.cat([torch.arange(j, j + n) for j, n in zip(starts, sizes)])
    x = model.emb(ids) + model.pos(pos)                                       # (n_tok, d)
    for l, blk in enumerate(model.blocks):
        qkv = blk.qkv(blk.n1(x))                     # ONE matmul for all tokens of all requests
        outs = []
        for (r, _), part, j in zip(work, qkv.split(sizes), starts):          # attention: per request
            q, k, v = [t.view(-1, H, dh).transpose(0, 1) for t in part.split(d, -1)]
            if r in cache and l < len(cache[r]):
                k = torch.cat([cache[r][l][0], k], 1); v = torch.cat([cache[r][l][1], v], 1)
            cache.setdefault(r, [])
            if l < len(cache[r]): cache[r][l] = (k, v)
            else: cache[r].append((k, v))
            n = q.shape[1]
            mask = torch.arange(j + n)[None, :] <= (j + torch.arange(n))[:, None]   # causal with offset j
            outs.append(F.scaled_dot_product_attention(q, k, v, attn_mask=mask).transpose(0, 1).reshape(n, d))
        x = x + blk.o(torch.cat(outs))               # merge back, ONE matmul again
        x = x + blk.ff(blk.n2(x))
    last = torch.tensor(sizes).cumsum(0) - 1
    return model.head(x[last])                       # (n_items, V)

def alone(prompt, n_new):
    """Reference: one request, whole prompt in one step, then plain decode."""
    cache, toks, logs = {}, [], []
    lg = step([(0, prompt)], cache)[0]
    for _ in range(n_new):
        t = int(lg.argmax()); toks.append(t); logs.append(lg)
        lg = step([(0, [t])], cache)[0]
    return toks, torch.stack(logs)

# requests: (arrival iteration, prompt, number of new tokens)
g = torch.Generator().manual_seed(1)
reqs = {"A": (0, torch.randint(1, V, (11,), generator=g).tolist(), 5),
        "B": (1, torch.randint(1, V, (7,), generator=g).tolist(), 5),
        "C": (3, torch.randint(1, V, (13,), generator=g).tolist(), 5)}

K = 6                                                # token budget per iteration
cache, done_p, out, logs, it = {}, {}, {r: [] for r in reqs}, {r: [] for r in reqs}, 0
while any(len(out[r]) < reqs[r][2] for r in reqs):
    work = [(r, [out[r][-1]]) for r in reqs if 0 < len(out[r]) < reqs[r][2]]    # 1) all decodes first
    left = K - len(work)
    for r, (a, p, _) in reqs.items():                                          # 2) prefill chunks, FCFS
        if a <= it and done_p.get(r, 0) < len(p) and left > 0:
            c = min(left, len(p) - done_p.get(r, 0))
            work.append((r, p[done_p.get(r, 0):done_p.get(r, 0) + c])); left -= c
    lg = step(work, cache)
    for (r, t), row in zip(work, lg):
        if len(out[r]) == 0:                          # a prefill chunk
            done_p[r] = done_p.get(r, 0) + len(t)
            if done_p[r] < len(reqs[r][1]): continue  # not the last chunk: logits unused
        out[r].append(int(row.argmax())); logs[r].append(row)
    print(f"iter {it}: " + " ".join(f"{r}{'+1' if len(t) == 1 and len(out[r]) > 1 else ':' + str(len(t))}" for r, t in work))
    it += 1

for r, (a, p, n) in reqs.items():
    ref, ref_logs = alone(p, n)
    diff = (torch.stack(logs[r]) - ref_logs).abs().max().item()
    print(r, out[r], "same as alone:", out[r] == ref, f"max logit diff {diff:.1e}")

With PyTorch 2.8 on a CPU it prints the schedule, where A:6 means six prompt tokens of A and A+1 one decode token of A:

iter 0: A:6
iter 1: A:5 B:1
iter 2: A+1 B:5
iter 3: A+1 B:1 C:4
iter 4: A+1 B+1 C:4
iter 5: A+1 B+1 C:4
iter 6: B+1 C:1
iter 7: B+1 C+1
iter 8: C+1
iter 9: C+1
iter 10: C+1
A [11, 53, 21, 14, 42] same as alone: True max logit diff 6.7e-16
B [8, 6, 55, 58, 41] same as alone: True max logit diff 6.7e-16
C [53, 55, 11, 62, 19] same as alone: True max logit diff 4.4e-16

Read the schedule. A’s 11-token prompt is split 6 + 5; B’s 7-token prompt 1 + 5 + 1, filling whatever the decodes leave; C’s 13 tokens go 4 + 4 + 4 + 1 next to three decodes. No iteration has more than 6 tokens, and no decode is ever skipped. The token IDs may change with the PyTorch version; the equality checks should not. In float32 the logits differ by about \(10^{-7}\), and in rare cases this can flip a greedy argmax between two almost equal tokens. Real engines see the same effect: batched and unbatched runs are equal in exact arithmetic, not always bit for bit.

The second program, in plain Python, is the simulator behind Figures 4 and 5 (the same seeded generator, so it prints the same numbers):

import math
N, L, DA, SKV, BW, PI = 8.03e9, 32, 4096, 131072, 3.35e12, 989e12   # Llama 3 8B, one H100 SXM
BMAX, PMAX = 64, 8192                         # max running requests, max prompt tokens per step

def step_time(dec, pre):
    """Roofline time of one iteration. dec: contexts of decodes; pre: (c, j) prefill chunks."""
    F = 2 * N * (len(dec) + sum(c for c, _ in pre)) + 4 * L * DA * (
        sum(dec) + sum(c * (j + c / 2) for c, j in pre))
    by = 2 * N + SKV * (sum(dec) + sum(j + c for c, j in pre))
    return max(F / PI, by / BW)

def mulberry32(a):                            # the same seeded generator as the figures
    s = [a]
    def r():
        s[0] = (s[0] + 0x6D2B79F5) & 0xFFFFFFFF; a = s[0]
        t = ((a ^ (a >> 15)) * (1 | a)) & 0xFFFFFFFF
        t = ((t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF) ^ t
        return (t ^ (t >> 14)) / 4294967296
    return r

def trace(lam, n=200, seed=11):
    r, t, out = mulberry32(seed), 0.0, []
    for _ in range(n):
        t += -math.log(1 - r()) / lam                                  # Poisson arrivals
        P = round(64 * 64 ** r())                                      # prompt 64..4096, log-uniform
        G = min(512, max(8, round(-128 * math.log(1 - r()))))          # output: exponential, mean 128
        out.append(dict(a=t, P=P, G=G, done=0, times=[]))
    return out

def simulate(mode, lam, K=512):
    R = trace(lam); n = len(R)
    t, nxt, wait, run, pref, static, fin = 0.0, 0, [], [], [], None, 0
    def emit(q):
        nonlocal fin
        q["times"].append(t); fin += len(q["times"]) == q["G"]
    while fin < n:
        while nxt < n and R[nxt]["a"] <= t: wait.append(R[nxt]); nxt += 1
        if not (wait or run or pref or static): t = R[nxt]["a"]; continue
        if mode == "static":                                           # request-level batching
            if static is None:
                static, wait = wait[:BMAX], wait[BMAX:]
                t += step_time([], [(q["P"], 0) for q in static])
                for q in static: emit(q)
            else:                                                      # finished rows still run
                t += step_time([q["P"] + len(q["times"]) for q in static], [])
                for q in static:
                    if len(q["times"]) < q["G"]: emit(q)
            if all(len(q["times"]) >= q["G"] for q in static): static = None
            continue
        chunks = []
        if mode in ("prefill", "orca"):                                # whole prompts, FCFS
            tok = 0
            while wait and len(run) + len(chunks) < BMAX and (not chunks or tok + wait[0]["P"] <= PMAX):
                q = wait.pop(0); chunks.append((q, q["P"])); tok += q["P"]
            dec = [] if (mode == "prefill" and chunks) else list(run)  # prefill-first: decodes wait
        else:                                                          # stall-free chunked prefill
            dec, left = list(run), K - len(run)
            for q in pref:
                if left > 0: c = min(q["P"] - q["done"], left); chunks.append((q, c)); left -= c
            while left > 0 and wait and len(run) + len(pref) < BMAX:
                q = wait.pop(0); pref.append(q); c = min(q["P"], left); chunks.append((q, c)); left -= c
        t += step_time([q["P"] + len(q["times"]) for q in dec], [(c, q["done"]) for q, c in chunks])
        for q in dec:
            emit(q)
            if len(q["times"]) == q["G"]: run.remove(q)
        for q, c in chunks:
            q["done"] += c
            if q["done"] == q["P"]:
                if q in pref: pref.remove(q)
                emit(q)
                if len(q["times"]) < q["G"]: run.append(q)
    ttft = sum(q["times"][0] - q["a"] for q in R) / n
    tbt = sorted(b - a for q in R for a, b in zip(q["times"], q["times"][1:]))
    thr = sum(q["G"] for q in R) / (max(q["times"][-1] for q in R) - R[0]["a"])
    return ttft, tbt[int(0.99 * len(tbt))], tbt[-1], thr

for mode, K in [("static", 0), ("prefill", 0), ("orca", 0), ("chunked", 256), ("chunked", 512), ("chunked", 2048)]:
    ttft, p99, mx, thr = simulate(mode, 45, K)
    print(f"{mode:8s} K={K:4d}  mean TTFT {ttft*1e3:7.1f} ms  p99 TBT {p99*1e3:6.1f} ms"
          f"  max TBT {mx*1e3:6.1f} ms  {thr:5.0f} tokens/s")

With Python 3.9 it prints, at 45 requests per second:

static   K=   0  mean TTFT  4649.9 ms  p99 TBT    7.4 ms  max TBT    7.4 ms   1444 tokens/s
prefill  K=   0  mean TTFT   132.4 ms  p99 TBT  138.5 ms  max TBT  315.7 ms   3157 tokens/s
orca     K=   0  mean TTFT    64.6 ms  p99 TBT   68.0 ms  max TBT  112.9 ms   3326 tokens/s
chunked  K= 256  mean TTFT   126.5 ms  p99 TBT    6.3 ms  max TBT    6.3 ms   3540 tokens/s
chunked  K= 512  mean TTFT    49.1 ms  p99 TBT    9.1 ms  max TBT    9.2 ms   3511 tokens/s
chunked  K=2048  mean TTFT    56.3 ms  p99 TBT   35.5 ms  max TBT   36.1 ms   3345 tokens/s

The simulator leaves out many things a real engine has: kernel efficiency below the roofline, the CPU time of the scheduler itself, sampling, preemption when the KV cache is full, and prefix caching. It is a tool for intuition about the shape of the trade-off, not a benchmark.

Where this is used

SettingWhat mattersTypical choice
Chat assistants and coding assistants (streaming)TTFT and a smooth stream (p99 TBT)Continuous batching with chunked prefill; a budget from the TBT target
RAG and long-document question answeringPrompts of thousands of tokens arrive while others streamChunked prefill is essential: without it, every retrieval-heavy prompt stalls all users
Offline batch jobs: synthetic data, evaluation, RL rolloutsThroughput onlyContinuous batching with a large budget (less chunking overhead), large \(B_{\max}\)
Agents and multi-turn tool useMany short follow-up prompts on long shared contextsChunked prefill plus prefix caching (session 134), so only the new part is prefilled
Video question answering and Video-RAG with a VLMA clip can become thousands of visual tokens in one promptChunk the visual-token prefill so that a long video does not stall text users on the same GPU
Live video: key-moment detection and captioning on many streamsEach stream sends new frames all the time; a per-stream deadlineEach new segment is a prefill chunk on that stream’s cache; the budget keeps every stream’s output on time
Video retrieval and fingerprinting (embedding models)One forward pass per clip, no decodePlain dynamic batching (session 84); continuous batching gives nothing without a decode phase

Common mistakes

  • Thinking continuous batching alone solves latency. It fixes TTFT and idle rows, but whole-prompt prefills still stall every running user. You need chunked prefill (or disaggregation) for a good TBT tail.
  • Looking only at mean TPOT. A few 300 ms stalls hardly change the mean of a 1,000-token answer, but users see the stream freeze. Track p99 and max TBT.
  • Choosing the token budget without the decode batch. The prefill room is \(K - B\). A budget of 128 with 64 running decodes leaves 64 prefill tokens per iteration, and prompts starve (TTFT 1.76 s in Figure 7).
  • Odd chunk sizes. A chunk of 257 tokens wastes most of a second tile; Sarathi-Serve measured up to 32% slower prefill than with 256. Use multiples of the kernel tile size.
  • Forgetting the offset in the causal mask or the positions of a chunk. Chunk \(k\) must use positions \(j, \dots, j + c - 1\) and attend to all \(j\) cached tokens; otherwise the output changes silently. Test against a whole prefill, as the code does.
  • Sampling a token after every chunk. Only the last chunk of a prompt produces a token; the logits of earlier chunks must be discarded.
  • Expecting chunking to save compute. The attention FLOPs are exactly the same (formula 135.7); chunking only moves work to where the GPU has idle compute, and it adds KV-cache reads.

Interview questions

What is continuous batching, and why does it beat request-level batching for LLMs?basic
The scheduler rebuilds the batch at every iteration (one forward pass): finished requests leave at once, freeing their KV cache, and waiting requests join at the next iteration. Request-level batching keeps a batch until its longest request ends, so finished rows idle (padding) and new requests wait for the whole batch. Orca introduced it and reported 36.9 times the throughput of FasterTransformer on GPT-3 175B at the same latency. In the simulator of this session, mean TTFT drops from 4.6 s to 65 ms and throughput more than doubles.
What is selective batching and why is it needed?core
In one iteration the requests have different numbers of new tokens (a prompt or a chunk, or one decode token) and different cache lengths, so their tensors do not form a rectangle. Selective batching stacks all new tokens into one \((\sum n_i, d)\) matrix for the operations where position does not matter (QKV, output projection, FFN), so each weight is read once, and splits by request only for attention, where each request uses its own KV cache. No padding is needed. Modern engines do the split attention in one variable-length or paged kernel.
What is a generation stall, and which schedulers cause it?core
A long pause between two tokens of a running request because a prefill was processed. Prefill-first schedulers (original vLLM) pause decodes during a prefill-only iteration; hybrid schedulers with whole prompts (Orca) make the decode iteration as long as the prefill. For Llama 3 8B on an H100 with 32 decodes at 1,024 tokens, a 2,048-token prompt turns a 6.1 ms gap into 40.4 ms (prefill-first) or 34.9 ms (hybrid). Request-level batching never stalls decodes, but has very long TTFT.
Why can a prefill chunk ride along with decodes almost for free?core
A decode iteration is memory-bound: it reads all weights to process only \(B\) tokens. The compute is idle until the iteration has about \(n^{*} = b\pi/(2\beta)\) tokens, 295 for BF16 on an H100, independent of model size. Up to that point extra tokens cost almost nothing (only their KV traffic). With 32 decodes at \(T = 1024\), up to 340 prefill tokens add nothing to the 6.08 ms iteration in the roofline model. Above the knee each token costs \(2N/\pi\), about 16 µs for an 8B model.
Is chunked prefill exact? What does it cost?core
Yes, up to floating-point rounding: causal attention for each token only needs earlier keys and values, which are already in the cache, provided the chunk uses the right positions and a causal mask offset by the cached length. The attention FLOPs are unchanged (\(\sum 4Ldc(kc + c/2) = 2LdP^2\)). The costs are extra KV reads (about \(s_{\text{kv}} P^2/(2c)\) in total), weights read once per chunk (shared with decodes), lower kernel efficiency for small chunks (Sarathi-Serve: up to about 25% prefill overhead at chunk 512 on Yi-34B), and a slightly longer TTFT for the chunked request.
How would you choose the token budget (chunk size)?advanced
From the TBT target: \(K(\tau) = \max\{n : t(n) \le \tau\}\), measured by profiling the real iteration time for a typical decode batch (Sarathi-Serve uses a profiler for this). Then check three things: \(K\) must be clearly larger than the expected decode batch, or prompts starve; it should be a multiple of the matmul tile size; and it should not be so small that the KV re-reads and kernel inefficiency dominate. Sarathi-Serve used 512 for strict and 2,048 for relaxed targets. In the simulator at 45 requests/s with a 10 ms p99 TBT target, the best budget is 512 (mean TTFT 49.1 ms).
What is Dynamic SplitFuse and how does it relate to Sarathi-Serve?core
DeepSpeed-FastGen’s scheduler: long prompts are split into chunks over several forward passes (only the last one produces a token), and short prompts are packed together to fill a fixed token budget exactly. It is motivated by throughput: pass time depends mainly on the token count, and equal-size passes are best because pass time is convex in the token count (Jensen). Sarathi-Serve reaches almost the same iteration shape from a latency target. Both keep each forward pass near a fixed size with all decodes included.
Prove that equal-sized forward passes are best.advanced
Let \(t(n)\) be the time of a pass with \(n\) tokens. In the roofline model \(t(n) = \max(\text{compute}(n), \text{memory}(n))\), with compute linear plus a convex attention term and memory linear in \(n\); a maximum of convex functions is convex. For passes \(n_1, \dots, n_m\) with a fixed sum, Jensen gives \(\sum t(n_k) \ge m\,t(\bar n)\). Example: 600 tokens as 580 + 20 take 14.30 ms on an H100 for Llama 3 8B; as 300 + 300 they take 9.79 ms. The small pass wastes the compute its weight read paid for.
How do TTFT, TBT and throughput change when you increase the token budget?core
TBT grows roughly like the iteration time \(t(K)\) once \(K\) is above the knee. TTFT first falls fast (a tiny budget starves prefills, because the room is \(K - B\)), then flattens, and at very large budgets rises again towards the whole-prompt behaviour, because long prompts block the queue. Throughput is highest near the point where compute and memory are balanced in each iteration and changes little at low load, where all schedulers just keep up with the traffic. In the simulator at 45 requests/s: \(K = 128\) gives TTFT 1.76 s, \(K = 512\) gives 49.1 ms with p99 TBT 9.1 ms, \(K = 2048\) gives 56.3 ms with 35.5 ms.
When would you use prefill–decode disaggregation instead of chunked prefill?advanced
Chunked prefill shares each GPU between the phases; interference is reduced but not removed (a budget that is good for TBT can make TTFT worse, and the KV re-reads grow with prompt length). Disaggregation (Splitwise, DistServe) runs prefill and decode on different GPUs and sends the KV cache over the network, so each pool can be sized and tuned for its own SLO (TTFT for prefill, TBT for decode). It pays for KV transfer and needs enough traffic to keep both pools busy. Very long prompts and strict separate SLOs favour disaggregation; a single GPU or small deployment favours chunked prefill.
Why does chunked prefill also help pipeline parallelism?advanced
With pipeline parallelism, micro-batches flow through stages one after another. If one micro-batch is a long prefill and the next a short decode, the stages wait for each other and the pipeline has bubbles. Chunked prefill with a fixed budget makes every micro-batch about the same size and time, so the stages stay busy. Sarathi reported 6.29 times fewer bubbles and 1.91 times end-to-end throughput for GPT-3 with pipeline parallelism, and Sarathi-Serve up to 5.6 times higher serving capacity for Falcon-180B.

Exercises

  1. Compute the knee \(n^{*}\) of formula (135.4) for an H100 in FP8 (1,979 TFLOP/s dense, 3.35 TB/s, \(b = 1\)) and for an A100 in BF16 (312 TFLOP/s, 2.039 TB/s). What do you notice about the H100 numbers?
  2. Llama 3 8B on an H100 with 32 decodes at \(T = 1024\). A 4,096-token prompt arrives. What gap between tokens do the 32 users see with a prefill-first scheduler? With a hybrid whole-prompt iteration?
  3. For the same 32 decodes, use Figure 2 to find the token budget for a TBT target of 20 ms. How many iterations does a 4,096-token prompt then need?
  4. An 8,192-token prompt is prefilled in chunks of 512. How many bytes of KV cache do the chunks read and write in total (use formula 135.7 with \(s_{\text{kv}} = 131{,}072\))? How much more than a whole prefill, and how long does the extra take at 3.35 TB/s?
  5. Three passes process 900 tokens as 800 + 50 + 50. Using the simple model \(t(n) = \max(4.794 \text{ ms},\ 16.24\,\mu\text{s} \cdot n)\), compare with 300 + 300 + 300.
  6. In Figure 7 at 45 requests/s, which budget would you choose for a p99 TBT target of 20 ms, and why is it not the largest budget that meets the target?
Answerscheck
1. H100 FP8: \(1 \times 1979 / (2 \times 3.35) = 295\) tokens; A100 BF16: \(2 \times 312 / (2 \times 2.039) = 153\) tokens. The H100 knee is the same in FP8 and BF16: halving the bytes and doubling the FLOP rate cancel. 2. Prefill-first: the prefill-only iteration takes 70.96 ms, then the decode iteration 6.08 ms, so a gap of 77.0 ms. Hybrid: 71.5 ms. 3. \(K = 1{,}207\), so 1,175 prefill tokens per iteration and \(\lceil 4096/1175 \rceil = 4\) iterations. 4. \(m = 16\); \(131{,}072 \times 512 \times 16 \times 17/2 = 9.13\) GB, against \(8192 \times 131{,}072 = 1.07\) GB for a whole prefill; 8.05 GB extra, about 2.4 ms at 3.35 TB/s (hidden under about 151 ms of compute in the roofline model, but not on a real GPU). 5. \(12.99 + 4.79 + 4.79 = 22.58\) ms against \(3 \times 4.87 = 14.61\) ms: the two small passes each pay a full weight read for little work. 6. Budgets 128 to 1,024 meet 20 ms (p99 TBT from 5.7 ms at 128 to 17.9 ms at 1,024); 1,536 gives 26.7 ms and fails. Among them, the mean TTFT is lowest at 768 (48.9 ms, p99 TBT 13.6 ms), with 384 and 512 almost the same. The largest qualifying budget, 1,024, has a slightly worse TTFT (49.8 ms) and a longer TBT tail (17.9 ms), for no gain. The largest qualifying budget is not the best because, beyond the knee, a bigger budget only lengthens every iteration.

Key takeaways

  • Continuous batching (Orca) rebuilds the batch at every iteration (135.1): finished requests leave, new ones join. Selective batching stacks all new tokens for the linear layers and splits only attention, so a ragged mix of prefills and decodes runs with no padding.
  • An iteration costs \(\max(\text{compute}, \text{memory})\) (135.3). Up to about \(n^{*} = b\pi/(2\beta)\) tokens (295 on an H100) it costs one weight read; a decode batch leaves most of that compute idle (135.4).
  • Whole-prompt prefills stall every running user: a 6 ms gap becomes 35 to 40 ms for a 2,048-token prompt on Llama 3 8B (135.5).
  • Chunked prefill (Sarathi, Sarathi-Serve) splits prompts into chunks that ride along with the decodes under a token budget \(K(\tau)\) (135.6). It is exact, keeps attention FLOPs the same, and adds KV re-reads of about \(s_{\text{kv}}P^2/(2c)\) (135.7) and a slightly longer TTFT for the chunked request (135.8).
  • Dynamic SplitFuse (DeepSpeed-FastGen) reaches the same shape from throughput: equal-size passes are optimal because pass time is convex in the token count (135.9).
  • Measure per request (135.10): TTFT, the p99 and max of TBT, TPOT and throughput. In the simulator, chunked prefill with a good budget cuts the p99 TBT by 7 to 15 times without losing throughput; a budget that is too small starves prompts.

Key formulas

\[ t = \max\!\left(\frac{2Nn + 4Ld\,[\cdot]}{\pi}, \frac{bN + s_{\text{kv}}[\cdot]}{\beta}\right), \quad n^{*} = \frac{b\pi}{2\beta}, \quad K(\tau) = \max\{n : t(n) \le \tau\}, \quad \sum_k t(n_k) \ge m\,t(\bar n) \]

References for this session

  1. Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
  2. Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
  3. Agrawal et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
  4. Holmes et al. (2024). DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inference
  5. Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
  6. Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
  7. Agrawal et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
  8. Holmes et al. (2024). DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inference
  9. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  10. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  11. Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
  12. Zhong et al. (2024). DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
  13. Patel et al. (2023). Splitwise: Efficient Generative LLM Inference Using Phase Splitting