The main question of this lecture: why is generating text slow? And who do we blame: the compute or the memory?
You know the feeling. You type "write me a haiku about GPUs" into a chatbot, and the answer starts appearing... one... word... at... a... time. But notice: the first word took a noticeable pause, and everything after it pours out at a steady drip. That pause and that drip come from two different machines hiding inside one model. By the end of this lecture you will be able to put numbers on both of them, on real hardware, with real models.
When your request arrives at a serving engine, it passes through four stages:
The single most consequential structural fact in all of LLM serving is the asymmetry between stages 2 and 3:
You can probably guess that one of these two is a much weaker use of a GPU than the other. Hold that thought. In a moment we will make it precise, and the number is going to surprise you. This one asymmetry returns as the batching problem (Lecture 4), the disaggregation problem (Lecture 5), and the kernel-split problem (Lecture 7).
Here is a puzzle. During decode, step \(t\) needs attention over tokens \(1..t\). Surely we don't re-run the whole prefix every step... or do we? What are we even allowed to reuse?
Possible answer
No. And this is provable, not folklore. In a causal decoder, attention at position \(s\) reads only positions \(1..s\). So once token \(s\) has been processed, none of its intermediate activations can ever change again. A tidy induction over layers makes it rigorous:
Setup. Let \(h_t^{(l)}\) be the hidden state at position \(t\) after layer \(l\). A causal layer computes \(h_t^{(l)} = \mathrm{MLP}^{(l)}\!\left(\mathrm{Attn}^{(l)}(q_t, \{K_s, V_s\}_{s\le t}) + h_t^{(l-1)}\right) + \dots\) The crucial detail is the index set \(\{s \le t\}\).
Base (\(l=0\)): \(h_t^{(0)} = \mathrm{Embed}(x_t) + \mathrm{pos}(t)\) depends only on \(x_{1..t}\). ✓
Step: if \(h_s^{(l-1)}\) depends only on \(x_{1..s}\) for all \(s\), then \(K_s^{(l)}, V_s^{(l)}\)
depend only on \(x_{1..s} \subseteq x_{1..t}\), the query \(q_t\) depends on \(x_{1..t}\), and the MLP is
position-wise. So \(h_t^{(l)}\) depends only on \(x_{1..t}\). ∎
Corollary (cache legality). Appending tokens cannot change \(h_s, K_s, V_s\) for any \(s \le t\). Storing prefix K/V and reusing them is exact, not approximate. The KV cache is licensed by causality. It is a structural property of the decoder, not an engineering trick.
Contrast: a bidirectional encoder replaces \(\{s\le t\}\) with all positions. There, one appended token changes every attention output in every layer, and any cache is instantly invalid. BERT could never have this for free.
And what happens if we lose a KV entry? Its replacement cost is one full prefix re-prefill: deep-layer K/V are deep nonlinear functions of the whole prefix, so there is no shortcut from token ids back to \(K_s^{(l)}\). In other words, discarding is recomputing. This identity is the basis of the recompute-vs-swap trade-off we will keep meeting (Lectures 2, 4, 5).
Without caching, generating \(N\) tokens costs \[ \sum_{t=1}^{N} t = \frac{N(N+1)}{2} = O(N^2) \quad \text{token-forwards,} \] versus exactly \(N\) with a cache. For \(N = 2048\) that is 2,098,176 versus 2,048, about a \(1024\times\) difference. The cache is not an optimization; it is the difference between feasible and absurd. The price we pay is memory, and the state grows linearly with context length. How different architectures pay that price defines a whole spectrum:
| Scheme | State size | Fidelity |
|---|---|---|
| RNN / linear attention | fixed, \(O(1)\) in \(L\) | lossy compression of the prefix |
| MLA (DeepSeek-V3) | low-rank latent, ~576 elem/token/layer | nearly lossless |
| GQA / MHA | full (grouped) K and V | lossless |
| DSA (V3.2) | state not reduced; a subset is read per step | lossless state, sparse reads |
Four generations of attack on the same term. Remember this table in Lecture 2!
Per token, per request, the cache stores K and V at every layer: \[ kv = \underbrace{2}_{K \text{ and } V} \times n_{layers} \times n_{kv} \times d_h \times b_{dtype} \quad \text{bytes/token.} \] Note that \(n_{kv}\) is the number of KV heads (after GQA/MQA grouping), not query heads.
TA says: the 2026 update split this formula in two. Kimi K3 is a hybrid of 69 KDA layers (a gated delta-rule linear attention: fixed recurrent state, \(S_t \in \mathbb{R}^{128\times 128}\) per head, never grows with \(L\), ≈ 0.20 GiB per request total) and 24 Gated-MLA layers (the usual linear-in-\(L\) cache, 27 KiB/token). At \(L = 1{,}048{,}576\), K3's state is ≈ 27.2 GiB vs ≈ 320 GiB for a GQA-70B-style model. That is about 12×, and the gap widens with \(L\), because part of K3's state simply never grows. The "RNN row" of our table became production reality. Two consequences for later: you can't prefix-cache a state that's overwritten in place (engines checkpoint it at block boundaries instead), and rolling it back for speculative decoding is its own adventure (Lecture 8).
Now for the numerator of our ratio. How much compute does one token cost? Let's just count.
Derivation
Each output entry \(Y_{ij}\) is a dot product of length \(d_{in}\): \(d_{in}\) multiplications and \(d_{in}-1\) additions ≈ \(2d_{in}\) FLOPs. With \(M \cdot d_{out}\) entries: \[ \mathrm{FLOPs}(Y = XW) = 2 M d_{in} d_{out}. \] The layer's parameter count is \(d_{in} d_{out}\), so per token (\(M=1\)) the cost is \(2 \times\) its parameters. Summing over every linear layer (the Q/K/V/O projections and the MLP) gives \(2\sum_i p_i = 2P\), since transformer parameters live almost entirely in these matrices. ∎
What did we ignore, and when does it bite?
Every GPU kernel obeys two speed limits: peak compute \(\pi\) (FLOP/s) and peak memory bandwidth \(\beta\) (bytes/s). If your computation has arithmetic intensity \(I\) (FLOPs per byte of memory traffic), then \[ T \ge \max\!\left(\frac{\text{FLOPs}}{\pi},\, \frac{\text{bytes}}{\beta}\right) \quad\Longrightarrow\quad \text{attainable FLOP/s} = \min(\pi,\; \beta \cdot I). \]
The two limits meet at the ridge point \(I_{ridge} = \pi/\beta\). For the canonical GPU of this course, the H100 SXM (\(\pi \approx 990\) TFLOPS BF16, \(\beta \approx 3.35\) TB/s HBM3, 80 GB): \(I_{ridge} \approx 295\) FLOP/byte.
Now the punchline. Decode at \(B=1\), FP16: each token costs \(2P\) FLOPs; each step must read all \(P\) parameters (\(2P\) bytes) plus a (then small) KV cache: \[ I_{decode}(B=1) \approx \frac{2P\ \text{FLOPs}}{2P\ \text{bytes}} = 1\ \text{FLOP/byte}. \] One FLOP per byte sits a factor of 295 to the left of the ridge, deep in memory-bound territory. Attainable compute: \(\beta \cdot I = 3.35\) TFLOPS. That is about 0.3% of what the tensor cores can do.
TA says: this is my favorite sentence in the whole course: during decode, the GPU is an extremely fast memory system with an incidental compute unit attached. When someone proposes to "optimize your decode kernels", your first question should be: which bytes do they eliminate? A kernel that makes a bandwidth-saturated GEMV 2× faster at math does exactly nothing.
Every decode step must read all the weights once, and no kernel, however clever, moves bytes faster than the memory hands them over. So nothing can beat \[ T_{step} \ge \frac{\text{weight bytes}}{\beta} = \frac{2P}{\beta}. \] For 70B FP16: \(T_{step} \ge 140\ \text{GB} / 3.35\ \text{TB/s} \approx 41.8\) ms, a single-request ceiling of \(1/T_{step} \lesssim 24\) tok/s. Only three levers move this bound: (i) shrink the bytes (FP8 halves it, INT4 quarters it); (ii) produce several tokens per weight read (speculative decoding, Lecture 8); (iii) buy more bandwidth.
Possible answer
The bound reads weight bytes, not \(2P\). K3 activates only 104B of 2.8T parameters (16 of 896 routed experts + 2 shared), and stores routed experts in MXFP4, about 17.5 MB per expert. Routed-only traffic: \(17.5 \text{ MB} \times 16 \times 92 \approx 26\) GB per step, so \(T_{step} \ge 26\text{ GB}/3.35\text{ TB/s} \approx 7.8\) ms, i.e. ≲ 129 tok/s. (The full always-on BF16 parts push real traffic to ≈ 55–60 GB.) Observed on GB300: 111–118 tok/s. That is bandwidth theory predicting production reality within about 15%. Two morals: the bound transfers across hardware only through \(\beta\); and at ~90% MBU there is little kernel headroom left, so further gains must come from the three levers.
Fine, one request is memory-bound. But we don't serve one request. We serve many at once. Let \(B\) requests decode together, each with mean resident context \(L\). Count the two quantities for one batched decode step:
Numerator (FLOPs): each of the \(B\) tokens needs \(2P\) weight FLOPs, so \[ \text{FLOPs} \approx 2P\,B. \] Denominator (bytes): three contributions:
Therefore \[ I \approx \frac{2P\,B}{2P + B\, \cdot kv} \] (the short form absorbs the mean context \(L\) into the per-request KV footprint read each step). Divide top and bottom by \(B\) to see the two regimes: \[ I = \frac{2P}{\underbrace{2P/B}_{\text{weights} \to 0} + \underbrace{L \cdot kv}_{\text{KV: invariant}}} \qquad\Longrightarrow\qquad I \xrightarrow[B \to \infty]{} I_{sat} = \frac{2P}{L \cdot kv}. \] Batching can lift you off the floor. But there is a ceiling, set by KV, and it sinks as context grows. KV reads start to dominate once \(B \cdot L \cdot kv = 2P\), i.e. at \(B_{cross} = 2P/(L\,kv)\).
| \(L\) | \(I\) @ B=1 | \(I\) @ B=32 | \(I\) @ B=256 | \(I_{sat}\) |
|---|---|---|---|---|
| 512 | 1.0 | 30.8 | 195.9 | 834.5 |
| 2,048 | 1.0 | 27.7 | 115.0 | 208.6 |
| 8,192 | 1.0 | 19.8 | 43.3 | 52.2 |
| 32,768 | 0.9 | 9.3 | 12.4 | 13.0 |
| 131,072 | 0.8 | 3.0 | 3.2 | 3.3 |
Put the two phases side by side:
| Prefill | Decode | |
|---|---|---|
| Linear-layer shape | GEMM, \(M = L\) | GEMV / small GEMM, \(M = B\) |
| Attention | \(L \times L\) lower-triangular | 1 query vs all history |
| Intensity | \(\approx L\) (hundreds–thousands) | \(\approx \frac{2PB}{2P + B \cdot kv}\) (1–50) |
| Bound by | tensor-core FLOPS (\(\pi\)) | HBM bandwidth (\(\beta\)): weights + KV |
| Right metric | MFU | MBU |
Prefill needs \(I > 295\), i.e. \(L\) of a few hundred tokens. That is a short paragraph of text. So nearly all real prompts are compute-bound in prefill; prefilling 4,096 tokens of 70B costs \(2PL \approx 573\) TFLOP ≈ 1.2 s of pure compute at a realistic 50% MFU. Different bottlenecks mean a mixed batch forces one kernel to serve two regimes at once. This is the direct motivation for prefill/decode disaggregation (Lecture 5) and chunked prefill (Lecture 4).
To talk about any of this honestly we need scorecards. Two utilization metrics; match each to its regime: \[ \mathrm{MFU} = \frac{\text{useful FLOPs/s achieved}}{\pi}, \qquad \mathrm{MBU} = \frac{\text{weight+KV bytes/s actually moved}}{\beta}. \] MFU is for compute-bound work (prefill, training); MBU is for decode, where good engines hold 60–80%. Reporting decode MFU (0.3%!) measures the wrong resource; reporting prefill MBU is equally meaningless.
Four latency metrics. Take a request issued at \(t_0\), first token at \(t_1\), tokens at \(t_1 < t_2 < \dots < t_{N_{out}}\), finish at \(t_e\): \[ \mathrm{TTFT} = t_1 - t_0, \qquad \mathrm{TPOT} = \frac{\mathrm{E2E} - \mathrm{TTFT}}{N_{out}-1}, \qquad \mathrm{ITL}_i = t_{i+1} - t_i, \qquad \mathrm{E2E} = t_e - t_0 = \mathrm{TTFT} + \sum_{i=1}^{N_{out}-1} \mathrm{ITL}_i. \]
Throughput determines cost: serving cost per token ≈ GPU-hours ÷ tokens produced, so doubling throughput halves per-token cost. (An H100 at $2/hour sustaining 3,000 output tok/s costs \(\frac{\$2}{3{,}000 \times 3{,}600} \times 10^6 \approx \$0.19\) per 1M output tokens; the intensity formula is literally a cost model.) But batching raises per-step time and queuing delay, so a throughput number without a latency constraint is meaningless. The honest form is goodput: \[ \text{goodput} = \frac{\text{requests (or tokens) completed per unit time that meet the SLO}}{\text{unit time}}. \] Timed-out requests don't count. A system can show high throughput while violating P99 TTFT for half its requests. Then goodput < throughput, and you're over usable capacity.
Multi-turn and agent workloads resend the entire conversation history with each turn; the genuinely new content is a small suffix. With prefix caching, a hit means prefill computes only the uncached suffix. With hit rate \(h\) (fraction of input tokens whose KV is already resident): \[ \text{effective prefill FLOPs} \approx (1 - h) \cdot 2P \cdot L. \] DeepSeek reported a production input hit rate ≈ 56%. Agentic coding is higher still: Moonshot reports >90% on coding workloads whose typical prefix is ≈ 400K tokens and grows by ≈ 4K per turn.
Possible answer
No. TTFT stops being a FLOPs question and becomes a placement/scheduling question: which replica holds the matching prefix, and can the request be routed to it? This motivates cache-aware routing and multi-level KV storage (Lecture 2): KV turns from per-request scratch space into a long-lived, cross-request asset. Route by cache affinity, not round-robin. A 10-point drop of \(h\) at \(L\) = 32K on a 70B model adds ≈ 460 TFLOP ≈ 0.9 s of prefill per request. Kimi K3's API even prices it directly: $0.30/MTok cache-hit vs $3.00/MTok cache-miss, which is exactly the 1/10 rule of thumb.
A benchmark has three defining elements. Get any one of them wrong and no number is comparable:
ignore_eos + fixed
max_tokens.Possible answers (any five)
ignore_eos + fixed
max_tokens.Tooling: vllm bench serve and SGLang's bench_serving
drive an OpenAI-compatible endpoint end-to-end. Benchmark the full online path, not engine
internals.
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 that counts.
Some existing attempts
Attack \(n_{kv}\): query heads can share KV heads. MQA (all share one) → GQA (8 groups for 64 query heads: 8× compression, minimal quality loss) → MLA (don't store K/V at all: store a low-rank 576-element latent and re-derive K/V, about 9.3× under Llama-70B-GQA). Each step raises \(I_{sat} = 2P/(L \cdot kv)\) proportionally and pushes the ridge-crossing context out by the same factor. The DSA generation then keeps the state but stops reading all of it. Lecture 2 takes this thread and runs with it.
Where this leads (Lecture 8)
Let a cheap "draft" propose several tokens, then check them all in one parallel forward pass: \(k\) tokens at GEMM cost \(2Pk\), which at small \(k\) still reads the weights once. Accept the longest agreeing prefix, roll the KV back, repeat. That's speculative decoding: exact (lossless), and it multiplies tokens per weight-read. K3's DSpark reaches 331–370 tok/s at batch 1, well over the 129 tok/s "impossible" ceiling we derived. The ceiling is only impossible for sequential one-token-per-read decode; keep the three levers honest.
Existing designs (Lectures 4–5)
(i) Chunked prefill (Sarathi): slice the prefill into chunks small enough to piggyback on decode iterations without blowing TPOT: one pool, carefully interleaved. (ii) PD disaggregation (Splitwise, Mooncake): run prefill and decode on different GPU pools sized to their own SLOs and ship the KV across the network. You pay a transfer cost and buy independent scaling. Which one wins depends on the workload; how much, and when, is Lecture 5's obsession.
Enough reading. Now you drive the formula. Set a model, a batch size, and a context, and watch where you land on the roofline. Can you find a setting where decode is compute-bound? (And if not... why not?)
Take Lab 1: Roofline and Metrics from the course's hands-on pack: run a real decode sweep
with vllm bench serve, compute \(I\) at several \((B, L)\) points, compare against the
theoretical table above, and report TTFT/TPOT/ITL percentiles plus a goodput curve under an SLO you
choose. Bonus: find the goodput knee by sweeping the open-loop arrival rate.