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.
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:
- 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.
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.
- state: waiting queue \(W\) (FCFS), running set \(\mathcal{B}\), KV-cache pool
- loop (one pass per model iteration):
- move newly arrived requests into \(W\)
- 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
- build the iteration: one token for each request in decode, the prompt (or a chunk of it) for each request in prefill
- run one forward pass with selective batching; sample one token for each request whose prompt is complete
- 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
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:
- 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
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.]
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.
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
- 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.
- move arrived requests \((a_i \le t)\) into the queue \(W\)
- run one forward pass (selective batching): \(t \leftarrow t + t_{\text{iter}}\) // formula (135.3)
- emit one token per finished prompt or decode; finished requests leave and free their slot // (135.1)
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:
- 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:
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.
- \(j \leftarrow 0\) // tokens of this prompt already in the cache
- while \(j \lt P\): take the next chunk, positions \(j, \dots, j + c - 1\)
- project its tokens to \(q, k, v\) (with positions \(j, \dots, j + c - 1\))
- attend to the cache: keys \(0, \dots, j - 1\) // green
- attend inside the chunk with a causal mask; merge the two parts // orange
- append the chunk’s \(k, v\) to the cache; \(j \leftarrow j + c\)
- the last row of the last chunk gives the logits of the first output token
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.
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
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.
- input: running decodes \(D\), partly prefilled requests \(Q\), waiting queue \(W\), token budget \(K\), \(B_{\max}\)
- batch \(\leftarrow\) one token for every request in \(D\); \(\;r \leftarrow K - |D|\) // decodes first: never stalled
- for each request \(q\) in \(Q\) (oldest first) while \(r \gt 0\):
- \(c \leftarrow \min(r,\ \text{remaining prompt of } q)\); add the next \(c\) prompt tokens of \(q\); \(r \leftarrow r - c\)
- while \(r \gt 0\) and \(W\) not empty and \(|D| + |Q| \lt B_{\max}\) and the KV pool has room:
- move the head of \(W\) into \(Q\); add its first \(\min(r, P)\) prompt tokens; reduce \(r\)
- 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
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.
- add one token for each of the \(B\) decodes; \(r \leftarrow K - B\)
- for each waiting prompt, oldest first, while \(r \gt 0\):
- \(c \leftarrow \min(r, \ell)\), where \(\ell\) = tokens left in the prompt // split a long one
- add its next \(c\) tokens; \(r \leftarrow r - c\) // then fuse the next one
- run the pass: \(n = K - r\) tokens, time \(t(n)\) // formula (135.3)
- a prompt whose last piece ran emits its first token // here \(B\) stays fixed
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}\):
- 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:
| Scheduler | TTFT | TBT tail | Throughput |
|---|---|---|---|
| Request-level batching (FasterTransformer) | Very long: new requests wait for the whole batch | Low: decodes are never interrupted | Low: rows idle while the batch drains |
| Continuous, prefill-first (vLLM before chunking) | Short at low load | Long: decodes pause for every prefill | High |
| Continuous, hybrid with whole prompts (Orca) | Short | Long: the iteration is as long as the prefill | High |
| Chunked prefill, stall-free (Sarathi-Serve, SplitFuse) | Short if \(K\) is not too small; slightly longer for one long prompt | Bounded 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.
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.
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
| Setting | What matters | Typical 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 answering | Prompts of thousands of tokens arrive while others stream | Chunked prefill is essential: without it, every retrieval-heavy prompt stalls all users |
| Offline batch jobs: synthetic data, evaluation, RL rollouts | Throughput only | Continuous batching with a large budget (less chunking overhead), large \(B_{\max}\) |
| Agents and multi-turn tool use | Many short follow-up prompts on long shared contexts | Chunked prefill plus prefix caching (session 134), so only the new part is prefilled |
| Video question answering and Video-RAG with a VLM | A clip can become thousands of visual tokens in one prompt | Chunk 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 streams | Each stream sends new frames all the time; a per-stream deadline | Each 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 decode | Plain 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
What is selective batching and why is it needed?core
What is a generation stall, and which schedulers cause it?core
Why can a prefill chunk ride along with decodes almost for free?core
Is chunked prefill exact? What does it cost?core
How would you choose the token budget (chunk size)?advanced
What is Dynamic SplitFuse and how does it relate to Sarathi-Serve?core
Prove that equal-sized forward passes are best.advanced
How do TTFT, TBT and throughput change when you increase the token budget?core
When would you use prefill–decode disaggregation instead of chunked prefill?advanced
Why does chunked prefill also help pipeline parallelism?advanced
Exercises
- 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?
- 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?
- 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?
- 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?
- 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.
- 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
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
References for this session
- Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
- Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
- Agrawal et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
- Holmes et al. (2024). DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inference
- Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
- Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
- Agrawal et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
- Holmes et al. (2024). DeepSpeed-FastGen: High-throughput Text Generation for LLMs via MII and DeepSpeed-Inference
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Zheng et al. (2023). SGLang: Efficient Execution of Structured Language Model Programs
- Zhong et al. (2024). DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
- Patel et al. (2023). Splitwise: Efficient Generative LLM Inference Using Phase Splitting