The main question of this lecture: batching fixes decode's arithmetic intensity. But requests arrive and finish whenever they like, so who keeps the batch full, step after step?
Lecture 1 ended with a quantitative promise: decode throughput scales with batch size \(B\), because the one-per-step weight read of \(2P\) bytes gets amortized over more tokens: \(I \approx 2PB/(2P + B \cdot kv)\). Slide the batch up, and you climb the roofline slope toward the ridge.
But that formula takes \(B\) as given, as if someone politely handed the engine a full batch, forever. Nobody does. Users arrive at random moments, ask for a haiku or a 10-page analysis, and stop after wildly different numbers of tokens. So between the physics of Lecture 1 and a real serving stack there sits a component that decides, every single forward step, which requests run and which wait. That component is the scheduler. And it turns out to be worth several-fold of throughput, before any kernel even executes.
The easiest thing you can do is what any deep-learning tutorial does: collect \(B\) requests, run the model forward until all \(B\) have finished, then admit the next batch. Nobody enters, nobody leaves: a closed world. This is static batching, and it is the natural design if you think of inference as "apply a function to a fixed-shape batch of inputs."
You can probably guess why that breaks: autoregressive decode is not a fixed-shape function. The number of iterations is itself a random variable that differs per request. From this one fact drop two misalignments. Let us take them one at a time, with numbers.
Suppose your batch of \(B\) requests has output lengths \(N_1, \dots, N_B\) with mean \(\mu\). Real traces are long-tailed: one user wants a one-word classification, the next wants a chain-of-thought essay. The batch must run until the longest request finishes: \[ M_B = \max_{i = 1..B} N_i \quad \text{steps.} \] During step \(t\), only requests with \(N_i \ge t\) still produce useful tokens. The finished ones still occupy their batch slot and their KV-cache blocks, because nothing is released until the whole batch retires. The effective batch size decays over time from \(B\) toward 1.
Make it quantitative. Useful work over the batch's life is \(\sum_i N_i\) decode tokens, but the engine spends \(B \cdot M_B\) slot-steps (finished or not, every step runs \(B\) sequence positions). Define batch efficiency: \[ \eta(B) = \frac{E[\sum_i N_i]}{B \cdot E[M_B]} = \frac{\mu}{E[M_B]}. \] For geometric lengths, \(\Pr(N=k) = (1-p)^{k-1}p\), \(\mu = 1/p\) (the standard first model of "the request could stop at any token"), the tail-sum formula plus the classical extreme-value approximation give \[ E[M_B] \approx \mu\big(\ln B + \gamma\big), \qquad \eta(B) \approx \frac{1}{\ln B + \gamma}, \qquad \gamma \approx 0.577. \]
The second flaw is temporal. A request that arrives one millisecond after a batch starts waits for the entire batch to finish: queueing delay is quantized to the completion time of a whole batch, not to a step. If batch durations \(T_b\) are i.i.d., a Poisson arrival lands in an interval drawn with probability proportional to its length (length-biased sampling, the inspection paradox), so its mean wait is the mean residual life: \[ E[W] = \frac{E[T_b^2]}{2\,E[T_b]} \;\ge\; \frac{E[T_b]}{2}, \] with equality only if batch duration is deterministic. The inequality matters: static batching inflates \(E[T_b^2]\) twice, because batches are long and variable (the max of \(B\) random variables).
Possible answer
Make the unit of scheduling one forward step. If membership is recomputed after every step, a finished request's slot is recycled within ~50 ms (not after the longest of 32 sequences), and a queued arrival can join at the next step instead of the next batch. Both misalignments die of the same cause. That is exactly what the next section does, and it is all it does.
Continuous batching, introduced by Orca (OSDI '22), makes the call we just anticipated. The rule is disarmingly simple:
Why is that worth so much? Decode throughput is \(B_{\text{eff}} / t_{step}\). Static batching operates at the time-average \(\bar B = \eta B \approx 0.25 B\); continuous batching operates at \(B_{\text{eff}} \approx B_{cap}\) all the time. The gain is the ratio of throughputs at these two operating points, measured on the Module-1 intensity spine:
TA says: this is why textbooks call continuous batching the largest single source of gap between modern engines and naive implementations: a 3–4× difference from when you schedule, before any difference in how fast you execute. It is the default in vLLM, SGLang, and TensorRT-LLM. So when someone shows you a 4× serving speedup from a clever kernel, your first question should be: "what scheduler was the baseline running?" If the answer is request-level batching, you have just been shown Lecture 4 in a trench coat.
Step-level membership creates an execution problem: at any step, the batch holds requests with different context lengths at different positions (one decoding, another mid-prefill). No single monolithic tensor exists anymore. The resolution is selective batching, Orca's other contribution, now universal: concatenate for linear layers, divide-and-conquer for attention.
So: slots recycle, \(B\) stays pinned, and Lecture 1's intensity formula finally gets the \(B\) it was promised. Deficiency fixed? Not quite. Look at what else we just allowed into a step.
Continuous batching made it possible for two very different kinds of token to share every step:
A step's duration is set by the total work in it, so the scheduler's mixing policy directly shapes the latency distributions we defined in Lecture 1. The two obvious policies both fail, symmetrically:
On a single resource pool the conflict is intrinsic: the same HBM bandwidth and the same FLOPs are demanded by two token kinds with opposite appetites. How bad is it, numerically? We need a time model for a mixed step. For a step with \(B\) decode tokens (mean context \(\bar L\)) plus a prefill segment of \(L_c\) tokens: \[ T_{step}(B, L_c) \approx \max\!\Big( \underbrace{\tfrac{2P + B\bar L\,kv + L_c\,kv}{\beta \cdot \mathrm{MBU}}}_{\text{bytes}},\; \underbrace{\tfrac{2P(B + L_c) + 4\bar L\,d_{model}\,n_{lay}\,B + \mathrm{attn}_{pf}(L_c)}{\pi \cdot \mathrm{MFU}}}_{\text{FLOPs}} \Big). \] The bytes term (one weight read plus all KV reads/writes) dominates at small token counts; that is the decode-only regime. The FLOPs term (\(2P\) per token for linear layers, \(4\bar L d_{model}\) per layer per decode token, \(\approx 2L_c^2 d_{model}\) per layer of causal attention for prefill) takes over once enough prefill tokens are mixed in. The crossover is Lecture 1's roofline ridge, applied per step.
Worked Example 4.2: one 8K prefill detonates a decode batch
Decode-only step: bytes \(= 161\) GB → 56.5 ms; FLOPs
\(= 32 \times 140\ \text{GFLOP} + 32 \times 4 \times 2048 \times 8192 \times 80 = 4.5 + 0.17 \approx 4.6\) TFLOP
→ \(4.6/495 = 9.4\) ms. Max: 56.5 ms, bandwidth-bound.
Now watch what happens when we mix in the full \(L = 8192\) prefill. Linear FLOPs:
\(8192 \times 140\) GFLOP =
1.147 PFLOP; causal attention: \(2L^2 d_{model} n_{lay} = 2 \times 8192^2 \times 8192 \times 80 = 88\) TFLOP
(just 7.1% of the total, below the \(L^* \approx 53\)K attention crossover from Lecture 1,
exactly as expected at 8K). Total ≈ 1.239 PFLOP, so
\[ T_{step} = \max(56.5,\ 1.239\ \text{PFLOP} / 495\ \text{TFLOP/s}) = \max(56.5,\ 2504)\ \text{ms} = 2.50\ \text{s}. \]
Every one of the 32 decoding requests freezes for 2.5 seconds, a 44× ITL spike.
And here is the cruel part: the TPOT mean barely moves (one bad step among hundreds).
This is the exact spike Lecture 1 warned the mean would hide; only P99 ITL and inter-token
histograms reveal it.
Chunked prefill (Sarathi-Serve) restores control by changing what may enter a step.
Split every prefill along the sequence into chunks, and assemble each step under a token
budget \(T\) (vLLM: max_num_batched_tokens):
Three effects follow:
Effect 1: capped step compute, smooth ITL. Per-step FLOPs \(\le 2P \cdot T\) (plus attention): the step duration is bounded regardless of how long any single prefill is. The 2.5 s explosion of Worked Example 4.2 is sliced into \(\lceil L / (T - B) \rceil\) bounded steps.
Effect 2: utilization complementarity. A decode-only step is bandwidth-bound: HBM runs at ~85% MBU while the tensor cores idle at ~20% MFU. Prefill chunks demand compute and almost no extra bandwidth, because the weights are already being read and a chunk's KV writes are tiny. Filling decode steps with prefill chunks uses exactly the idle compute: the mixed step does strictly more work per wall-clock second than running the two kinds separately.
Effect 3, the cost: TTFT inflation. One prefill now spreads over \(\lceil L / c \rceil\) steps, and each of those steps also carries the co-scheduled decodes: \[ \mathrm{TTFT} \approx \Big\lceil \frac{L}{T - B} \Big\rceil \cdot T_{step}(B,\, T - B) \quad \text{(queuing aside).} \] The budget \(T\) is a direct TTFT–ITL dial: larger \(T\) → fewer, longer steps → better TTFT, worse ITL; smaller \(T\) → the reverse. You cannot satisfy both on one pool. Stay tuned: that sentence is Lecture 5's entire premise.
We have been saying "the scheduler admits" and "the scheduler evicts" casually. Let us look inside. The scheduler keeps two sets of requests: waiting (not yet started, or preempted: their KV was reclaimed) and running (holding KV blocks, participating in steps). It manages exactly two resources, the two currencies of this whole lecture: the token budget \(T\) (compute per step) and the KV-block pool (memory, Lecture 2). Every admission spends both; every preemption buys memory back at a compute or transfer price.
Decode appends KV blocks every step. When the pool is exhausted, some running request must yield memory. To evict a request of context length \(L\) there are two ways:
Recompute. Discard the KV entirely (Lecture 1: losing KV costs one re-prefill); the request returns to waiting and is later re-prefilled in chunks. The cost is prefill FLOPs, linear in \(L\) from projections/FFN plus quadratic from attention: \[ T_{recompute}(L) \approx \frac{2PL + 2L^2 d_{model} n_{lay}}{\pi \cdot \mathrm{MFU}} = aL + cL^2. \]
Swap. Copy the request's KV out to CPU memory over PCIe, copy it back on resumption. Two transfers, strictly linear in \(L\): \[ T_{swap}(L) = \frac{2L \cdot kv}{\beta_{PCIe}} = sL. \]
Equating the two, recompute wins iff \(aL + cL^2 < sL\), i.e. iff \[ L < L^* = \frac{s - a}{c}, \qquad a = \frac{2P}{\pi\,\mathrm{MFU}}, \quad c = \frac{2 d_{model} n_{lay}}{\pi\,\mathrm{MFU}}, \quad s = \frac{2\,kv}{\beta_{PCIe}}. \]
| \(L\) | \(T_{recompute}\) | \(T_{swap}\) (320 KB) | \(T_{swap}\) (34 KB) |
|---|---|---|---|
| 512 | 145 ms | 5.1 ms | 0.5 ms |
| 4,096 | 1,203 ms | 41.0 ms | 4.4 ms |
| 32,768 | 12,111 ms | 327.7 ms | 34.8 ms |
| 131,072 | 82.6 s (L² term dominates) | 1.31 s | 139 ms |
Interpreting the model honestly. On H100 + PCIe 5.0, the pure time model favors swap at essentially all lengths. So why did vLLM v1 choose recompute? Because the model omits three systems facts: (1) recompute rides the chunked-prefill machinery: it can be absorbed into spare token budget of steps that are bandwidth-bound anyway, so its marginal cost is near zero, while swap occupies a PCIe link also needed for weight loading, KV transfer, and sampling outputs; (2) recompute needs no pinned CPU buffers, no swap bookkeeping, no extra code path, which buys operational simplicity and memory certainty; (3) preemptions are rare and typically victimize short requests, where the absolute cost (145 ms at \(L = 512\)) is tolerable. The engineering rule that survives: recompute for short contexts and simplicity; swap for long contexts (its \(O(L)\) scaling wins decisively once \(L\) is large and a swap channel exists), with MLA layouts tilting the field further toward swap. Note this is the same inequality as the swap-in vs recompute decision for prefix-cache blocks in Lecture 2, with a different victim.
Victim selection. Preemption order is generally last-arrived-first-preempted: the youngest running request holds the least invested compute and the shortest prefix to rebuild, and the policy protects longer-waiting requests from unbounded delay. Priority-aware systems instead pick victims by priority class (low-priority batch traffic yields to latency-critical traffic).
Scheduling decisions are only as good as their execution. Two mechanisms at the boundary with Lecture 7's kernel layer decide whether the GPU actually stays busy.
A decode step launches hundreds of small kernels, one per layer per operation. Launched one by one from the CPU, launch overhead is a significant share of a ~50 ms step. The fix: pre-capture CUDA graphs for several fixed batch shapes (buckets \(\{b_1 < b_2 < \dots < b_m\}\)); at runtime, pad the assembled batch up to the nearest captured bucket \(b(B) = \min\{b_i \ge B\}\) and replay the whole graph in one launch. The scheduler's freely chosen batch shapes must now align with the captured buckets.
Padding \(\Delta(B) = b(B) - B\) phantom tokens are executed and discarded each step. In the bandwidth-bound regime each padded token costs the marginal per-token step time, i.e. the KV read it adds: \[ t_{tok} \approx \frac{\bar L \cdot kv}{\beta \cdot \mathrm{MBU}}, \qquad E[\text{waste}] = E[\Delta(B)] \cdot t_{tok}. \] With buckets spaced at stride \(g\) and \(B\) uniform within a bucket interval, \(E[\Delta] = (g-1)/2\). The trade is against memory: each captured graph pins buffers and workspace, so graph memory grows linearly with the bucket count. Finer buckets → less padding, more graphs.
| Buckets | # graphs | \(E[\Delta]\) | waste/step | % of a 167 ms step |
|---|---|---|---|---|
| stride 1 (every \(B\)) | 256 | 0 | 0 | 0% |
| stride 8 | 32 | 3.5 tok | 1.6 ms | 1.0% |
| stride 16 | 16 | 7.5 tok | 3.5 ms | 2.1% |
| powers of 2 | 9 | 42.2 tok (worst 127) | 19.4 ms | 12% |
Even with perfect batches, a naive engine serializes: between steps the CPU does scheduling, sampling, detokenization, Python bookkeeping (tens of milliseconds in the worst case), and the GPU idles through all of it. Async scheduling restructures the loop so the CPU schedules step \(i + 1\) while the GPU is still executing step \(i\) (vLLM v1's architecture; SGLang's overlap scheduler runs in a separate process with one-step lookahead). The decision for step \(i+1\) is made without knowing step \(i\)'s sampled tokens: the engine speculates batch membership (a request leaves only when its stop condition is confirmed) and corrects the rare misprediction. The measurable acceptance test: look at the GPU timeline (Nsight or torch profiler) and check that the holes between consecutive forward passes approach zero. Any persistent inter-step gap is CPU overhead leaking onto the critical path.
Everything so far assumed one homogeneous state: per-token KV growing with \(L\). The canonical 2026 model breaks that assumption. Kimi K3 (Moonshot AI) has 93 layers of which 69 are KDA (a gated delta-rule linear attention whose state is a fixed matrix \(S \in \mathbb{R}^{128 \times 128}\) per head, updated in place) and only 24 are Gated-MLA full-attention layers, a 3:1 hybrid. Four scheduling consequences follow:
(a) Two memory pools, two kinds of pressure. The MLA side costs the familiar \(kv = 24 \times 1{,}152\ \text{B} = 27.0\) KiB per token (grows with \(L\)); the KDA side costs a constant per request: \[ V_{KDA} = 69 \times 96 \times 128^2 \times 2\ \text{B} = 0.20\ \text{GiB (BF16)}. \] So the scheduler admits against two pools: the MLA KV pool (per-token blocks) and a KDA state pool (one fixed block per running request). Because every resident request must hold its whole rolling state, the KDA pool imposes a hard concurrency ceiling: the hybrid analog of the block-pool capacity from Lecture 2, but charged per request, not per token.
(b) Chunked prefill survives, lighter. A KDA layer's prefill is \(O(L)\) (chunkwise form, chunk size 64), not \(O(L^2)\); the quadratic term of the mixed-step model lives on only in the 24 MLA layers. But chunk boundaries are now stateful: each chunk consumes the incoming \(S\) and must checkpoint the boundary state.
(c) CUDA-graph interaction. A KDA decode step reads and writes a fixed 0.2 GiB state regardless of \(L\), so its graph is fully static, with no block-table indirection, unlike paged-attention decode graphs, whose KV gather traverses per-request block tables that grow with \(L\).
(d) Preemption flips: swap wins. Paged KV can be dropped and recomputed chunk by chunk; a KDA state cannot. It is a single rolling state overwritten in place, so "recompute" means replaying the entire prefix through the recurrence: at SGLang's measured 4,550 tok/s/GPU prefill rate, a 128K replay ≈ 29 s. But the swap side becomes length-independent: moving the 0.20 GiB state both ways over 64 GB/s PCIe costs ≈ 6.8 ms at any \(L\) (the 27 KiB/token MLA part still follows the break-even math above). Hybrid preemption is therefore swap/checkpoint by default, the reverse of vLLM v1's recompute default. The same in-place overwrite kills conventional prefix caching: engines instead checkpoint states at block boundaries with copy-on-write restore.
TA says: running K3 in production (2026) mixes the new and the
painfully familiar. SGLang serves it as a unified pool: a 54 MB FP32-per-TP8-rank KDA state
block plus 27 KB MLA KV blocks, sized by --mamba-full-memory-ratio; for prefix
caching you get copy-on-write/snapshot/donate on state blocks instead of hash-only pages. And a
real cautionary tale: SGLang's day-0 K3 support crashed under CUDA graphs on SM103
(B300-class silicon), a hybrid-graph bug, since fixed. Moral, straight from §4.5:
re-validate graph capture on your exact GPU SKU before trusting any of these dials.
How to: read the starting point; read the question and think, for a minute, a day, a week... and only then open the answers. You are not supposed to reinvent several months of someone's research; it's the habit of thinking about these things that counts.
Some existing attempts
The change is to schedule at the granularity of one forward step: Orca (OSDI '22) introduced continuous batching. Finished requests retire their slot at the next step, waiting requests join it, and \(B\) stays pinned at the cap. The new execution problem it creates is the ragged batch: requests of different lengths and phases share a step, so no monolithic tensor exists. Orca's own solution, selective batching (concatenate for linear layers, per-request attention), is precisely what pairs with Lecture 2's paged KV: attention already runs against per-request block tables. Today this is the default in vLLM, SGLang, and TensorRT-LLM, and it was worth ~3.65× in our worked example, from scheduling alone.
Existing solutions and attempts
On one pool, no: the budget \(T\) times every step, and decode tokens and prefill chunks compete for the same FLOPs and bandwidth. What production systems do instead: (i) bounds and floors, i.e. decode-first within a token budget, with a guaranteed prefill share or age-based escalation so prefills never starve (Sarathi-Serve's policy family); this softens both tails but cannot remove the coupling. (ii) Take the coupling away: put prefill and decode on different GPU pools, each tuned to its own regime, and ship KV across the network. That is Splitwise and Mooncake's prefill–decode disaggregation, the subject of Lecture 5. You pay a transfer and buy an independent dial. Which wins depends on the workload's input:output mix.
Existing solutions and attempts
For the rolling state, recompute means replaying the whole prefix through the recurrence (≈ 29 s at 128K tokens and 4,550 tok/s/GPU), while swap moves a fixed-size block: ≈ 6.8 ms at any \(L\) over 64 GB/s PCIe. The linear-in-\(L\) advantage that swap already had for MLA becomes flat-out length-independence for KDA, so hybrid engines preempt by swap/checkpoint, inverting vLLM v1's recompute default. The same in-place overwrite that forces this also breaks hash-based prefix caching, so engines checkpoint state at block boundaries with copy-on-write restore (vLLM 6,144-token state blocks vs 512-token hash blocks; SGLang's snapshot/donate API). One scheduler inequality, two model families, opposite defaults. Worth remembering every time someone quotes you a "rule".
Turn the dial yourself. Below is Worked Example 4.3 as a lab bench: the token budget \(T\) and the decode batch \(B\) are yours; an 8,192-token prompt is always waiting to be chunked. Watch ITL, TTFT, and which resource binds. Three challenges: (i) find the budget where the step stays within a 250 ms ITL SLO but TTFT is minimal; (ii) push \(B\) to 512 and explain what broke; (iii) find where the step flips from bandwidth- to compute-bound. Can you make the two exactly equal?
Take Lab 4: Continuous Batching and Chunked Prefill from the course's hands-on pack. One GPU; a mixed workload: 70% short prompts (\(L = 512\)) and 30% long (\(L = 8192\)) from a prepared prompt file, output lengths 64–512, open-loop arrival rate at ~70% of the knee you found in Lab 1, 30-minute sustained runs with per-request ITL traces saved.
--max-num-batched-tokens 8192 (large chunks). Measure
P50/P99 of TTFT, TPOT, ITL.--max-num-seqs 8 (a
static-ish schedule) and measure what head-of-line blocking costs.What to expect: one step with a full chunk costs ≈ \(2P \cdot \text{chunk}/\pi_{eff}\): 266 ms at budget 8192, 66 ms at 2048, 17 ms at 512. Against a 4.8 ms decode-step floor, that is the ITL spike a decode tenant feels when sharing a step. Large budget → best TTFT (long prompts prefill in few steps) but worst ITL P99; small budget → TTFT inflates (an 8K prompt needs 4–16 chunk steps) but ITL P99 flattens toward TPOT P50. Then answer the analysis questions honestly: which point on the curve satisfies "TTFT < 2 s, TPOT < 50 ms"? Why does TPOT P50 stay flat while ITL P99 moves? And where does prefill–decode interference still leak through despite chunking? (The pitfalls from Lecture 1 apply with teeth: report ITL P99, run 30 minutes, fix the arrival process across budgets.)