The main question of this lecture: the KV cache lives in GPU memory like a tenant who never cleans. How do we house it, share it, and evict it without wasting half the building?
Imagine you run a hotel. A guest checks in and says "I might stay one night, I might stay sixty. Reserve me the whole floor, just in case." You comply, because checkout time is unknowable in advance. Now do this for every guest, forever, and never let two guests share a floor. That is how pre-2023 serving stacks treated the KV cache. This lecture is the story of how the industry fixed it, one concrete flaw at a time.
Recall the protagonist from Lecture 1. Per token, per request, the cache stores K and V at every layer: \[ kv = 2 \times n_{layers} \times n_{kv} \times d_h \times b_{dtype} \quad \text{bytes/token,} \] and for Llama-3.3-70B (80 layers, GQA with \(n_{kv} = 8\) KV heads, \(d_h = 128\), BF16): \[ kv = 2 \times 80 \times 8 \times 128 \times 2\,\text{B} = 327{,}680\ \text{B} = \textbf{320 KB/token}. \] Two facts from Lecture 1 motivate everything today:
From these two facts, four engineering questions follow, and they are the spine of this lecture: how do we place growing KV in HBM without wasting it (paging), how do we reuse identical prefixes across requests (prefix caching), what do we do when the working set exceeds one machine (tiered storage), and can the model itself be designed so that \(kv\) is smaller (MLA)? Plus a 2026 postscript: what if most of the state is not per-token at all (Kimi K3's dual cache)?
The easiest thing you can do (and what HuggingFace Transformers and FasterTransformer actually did) is this: when a request arrives, hand it one contiguous KV region sized at max_seq_len. Contiguous, because the attention kernels of that era indexed KV with a base pointer plus dense strides. Sized at the maximum, because the output length is unknowable at admission.
You probably can guess why this is not the best way to run a hotel. Two failure modes, and they have exactly the names an OS textbook would give them:
Derivation
\(\mathrm{E}[D] = \frac{1}{R}\sum_{d=1}^{R} d = \frac{R+1}{2}\), so the utilization \[ u \equiv \frac{\mathrm{E}[D]}{R} = \frac{R+1}{2R} \xrightarrow[R \to \infty]{} \tfrac{1}{2}. \] Half the reservation is empty, on average, in the best case. At \(R = 4096\): \(\mathrm{E}[D] = 2048.5\), \(\mathrm{E}[\text{waste}] = 2047.5\) tokens, \(u = 0.5001\). Real workloads are worse. Output lengths are heavy-tailed well below the limit, so \(\mathrm{E}[D] = 2\)K against \(R = 8\)K gives \(u = 0.25\), squarely inside the 20–40% utilization band the vLLM paper measured on production-like workloads. At any moment, 60–80% of the memory reserved for KV holds no live data.
Why should you care about an accounting statistic? Because utilization is a throughput multiplier, in three steps.
Step 1 (waste). \(\mathrm{E}[\text{waste}] = R - \mathrm{E}[D]\); define \(u = \mathrm{E}[D]/R\).
Step 2 (batch cap). With contiguous reservations of \(R\) tokens and \(M_{free}\) bytes of HBM available for KV, the number of concurrent requests obeys \[ B \le \frac{M_{free}}{kv \cdot R} = \frac{M_{free}}{kv \cdot \mathrm{E}[D]} \cdot u. \] The utilization enters multiplicatively: waste translates one-for-one into lost batch slots.
Step 3 (throughput). Decode is memory-bound; in the weight-dominated regime (\(B \cdot L \cdot kv \ll 2P\)) the intensity reduces to \(I \approx B\) and per-step time is \(2P/\beta\), so \[ \text{decode throughput} \approx \frac{B\,\beta}{2P} \propto B \propto u. \] A measured utilization of 20–40% means the system runs \(u^{-1} \in [2.5, 5]\times\) below the batch (and hence the throughput) it could sustain with perfect packing.
So contiguous, max-sized reservations waste 60–80% of HBM, and the waste multiplies straight through to throughput. How did operating systems solve exactly this problem for process memory? Think for a second before reading on. You already know the answer: fixed-size pages, a page table per process, on-demand allocation, and a shared free pool. PagedAttention (vLLM) imports the whole design into KV management:
What does the last block cost us? A request of length \(D\) holds \(\lceil D/b \rceil\) blocks, of which only the last can be partially filled. If the final position is uniform within the last block (reasonable when \(D \gg b\)), the waste is \(b\lceil D/b \rceil - D \in \{0, \dots, b-1\}\), so \[ \mathrm{E}[\text{waste}] \le \frac{b-1}{2} \quad \text{tokens per request.} \] For \(b = 16\): \(\le 7.5\) tokens. Against an 8K-token reservation that is \(7.5/8192 \approx 0.092\%\) wasted, versus 75% under the contiguous policy of the worked example. Utilization ≈ 100%, and the batch cap becomes the ideal \(B \le M_{free}/(kv \cdot \mathrm{E}[D])\).
The price is metadata and indirection. The block table costs \(\lceil L/b \rceil\) entries per request: at \(L = 8\)K, 512 entries (2 KB with 4-byte ids) at \(b = 16\), versus 128 entries (512 B) at \(b = 64\). That is negligible next to the KV itself, but its read sits on the kernel's critical path. A contiguous kernel computes addresses as \(\text{base} + \text{stride} \cdot t\); a paged kernel must, per block, read the table entry and then gather. Attention kernels must explicitly support this: FlashAttention, FlashInfer, and FlashMLA all expose paged-KV interfaces. Sanity check of the trade: as \(b \to 1\), waste → 0 but the table grows to \(L\) entries with a per-token gather, and coalescing is destroyed. So \(b\) is negotiated, not minimized:
| smaller pages | larger pages |
|---|---|
| less internal waste | fewer block-table reads → less indirection |
| finer prefix-reuse granularity (next section) | better coalescing / TMA efficiency |
| more table entries per token | coarser reuse, more last-block waste |
page_size as a
tunable you can sweep at deployment time.
Block-table indirection has a second payoff: two logical blocks can point to the same physical block. With a reference count per physical block, \(n\) parallel samples (or a beam fork) of one prompt share all prompt blocks read-only; the first request to write a shared block triggers a copy-on-write, so only the divergent suffix ever consumes new memory. This is exactly OS copy-on-write for forked address spaces, and it is the mechanical foundation of what comes next: a "cache hit" is nothing more than inserting shared physical block ids into a new request's block table and bumping refcounts.
We stopped wasting HBM. Next flaw: we are still recomputing enormous prefixes that somebody (often the same agent, one turn ago) has computed already. What are we allowed to reuse, and how do we find it fast?
The key observation: KV content is a pure function of the prefix token sequence. Layer by layer, the K and V at position \(t\) are computed from the hidden state at \(t\), which is computed from positions \(1..t\) and nothing else. Sampling parameters decide which tokens get sampled next, but once the tokens are fixed, the KV is fixed. Therefore: \[ \text{prefix tokens identical} \;\Longrightarrow\; \text{corresponding KV blocks bitwise reusable.} \]
A hit is defined at block granularity and is prefix-only: a block of \(b\) tokens is reusable iff all \(b\) tokens match and all preceding blocks matched (KV at position \(t\) depends on the whole prefix, so matching can never skip a mismatch). Worked example: with \(b = 16\), a request whose first 8,000 tokens match a cached prefix but whose token 8,001 differs reuses exactly \(\lfloor 8000/16 \rfloor = 500\) blocks, and not one token more.
How do we find the longest cached prefix? Two index structures dominate:
Eviction has two constraints that naive LRU violates: blocks pinned by in-flight requests (refcount > 0) must never be evicted from under an active request; and in the radix tree a node may be evicted only if it has no descendants (a child's KV is meaningless without its ancestors), so eviction proceeds leaf-first.
Routing becomes cache-aware. In a multi-instance deployment a hit exists only in one instance's memory, so routing stops being pure load balancing. Simplest policy: session stickiness. General policy (SGLang router, Dynamo KV-aware routing): keep a per-instance prefix index, and pick \[ \arg\max_i\; w_1 \cdot overlap_i - w_2 \cdot load_i, \] a weighted combination of cache overlap and current load. The payoff is exactly Lecture 1's discount: effective prefill FLOPs become \((1-h)\cdot 2P \cdot L\). But now \(h\) is an engineered quantity, not just a property of the workload.
TA says: how much does this pay in production? Kimi K3's serving stack reports >90% prefix-cache hit rates on coding workloads, whose typical agent prefix is ≈ 400K tokens growing by ≈ 4K per turn (Moonshot, 2026). And the API prices it directly: $0.30/MTok cache-hit input vs $3.00/MTok cache-miss, a hit priced at exactly 1/10 of a miss, just like Lecture 1's rule of thumb. One caveat that foreshadows the end of this lecture: for hybrid linear-attention models the recurrent-state part of the cache can only be reused at sparse state-checkpoint boundaries (every 6,144 tokens in vLLM's K3 support, against 512-token hash blocks), so the effective \(h\) on the state side is rounded down to the last checkpoint. Keep that in the back of your mind.
Next flaw: even perfectly packed, HBM is finite, and there are two pressures pushing idle KV out of it. First, hit rate is monotone in retained KV: every evicted byte is a future hit converted into a full recompute. Second, idle KV competes with the running batch: HBM held by a paused agent session cannot host concurrent requests, and by the batch-cap formula it subtracts directly from throughput. And agents are bursty: inter-turn gaps of minutes (human reading time, tool execution) keep megabytes-to-gigabytes of state in the scarcest memory in the data center doing nothing.
The resolution is the classical one: sink idle KV down a memory hierarchy and buy it back when needed. Here is the ladder:
| tier | capacity | bandwidth | vs. HBM |
|---|---|---|---|
| HBM3 (H100) | 80 GB | 3.35 TB/s | 1× |
| CPU DRAM (PCIe 5.0 x16) | TB-scale | 64 GB/s | ≈ 2% |
| remote pool (RDMA) | cluster-scale | 25–50 GB/s per link | ≈ 1% |
| local NVMe | several TB | 7–14 GB/s | ≈ 0.3% |
Bandwidth drops ~50× from HBM to host DRAM, and another ~2–9× into the NVMe/remote tiers. So offloading is rational only if fetching back beats recomputing. That is a quantitative question. Let's just count both sides.
Two caveats keep the decision honest. (i) Recompute consumes GPU compute that could serve other requests, an opportunity cost not in \(T_{re}\), which only strengthens the case for transfer when the GPU is busy. (ii) Latency-bound small prefixes on slow tiers can make the transfer term visible in TTFT: NVMe at 7 GB/s needs 384 ms for 8K GQA tokens. And two corollaries do real work:
The industrial substrate already exists. Mooncake (Moonshot AI, open-sourced) organizes DRAM and SSDs across the cluster as a distributed KV cache pool, with prefill and decode disaggregated and KV flowing through an RDMA transfer engine; its public production trace is a commonly used workload dataset for exactly these policies, and in 2026 deployments Mooncake Store serves as the L3 tier behind both major engines (vLLM via its MooncakeStoreConnector, SGLang via HiCache L3). NIXL (NVIDIA) unifies asynchronous movement among VRAM, DRAM, NVMe, and remote memory, auto-selecting NVLink or RDMA/UCX backends.
Sections so far housed, shared, and evicted the tenant. But what if the tenant simply carried less luggage? Multi-head Latent Attention (MLA, introduced in DeepSeek-V2, carried into V3/R1/V3.2) redesigns the attention layer so that what must be cached is small: instead of caching K and V of all heads, project the hidden state down to a low-rank latent and cache that: \[ c_t = W^{DKV} h_t \in \mathbb{R}^{512}, \qquad k_t = W^{UK} c_t, \quad v_t = W^{UV} c_t, \] with K and V recovered on demand through up-projection weights, resident like any other parameters. One latent serves both K and V of all heads: a joint compression.
There is one catch, and it is worth a minute of your thought: what about RoPE?
Possible answer
Folding needs a single merged matrix \(W_Q^{\top} R_j W^{UK}\). But \(R_j\) changes with position \(j\), so no such fixed matrix exists: the rotation sits exactly between the two matrices we wish to merge. RoPE would block the absorption trick that makes MLA cheap at decode. MLA's fix is decoupled RoPE: positional information takes a separate, narrow path, a 64-dimensional key \(k^R_t\) that carries RoPE, is shared by all heads (MQA-style), and is concatenated with the cached latent:
\[ \text{cached per token per layer} = \big[\, c_t\ (512),\; k^R_t\ (64) \,\big] \Rightarrow 576\ \text{elements.} \] At FP8 that is 576 B per token per layer; over DeepSeek-V3's 61 layers: \[ kv_{MLA} = 576 \times 61 \times 1\ \text{B} = 35{,}136\ \text{B} \approx \textbf{34 KB/token}, \] i.e. ≈ 4.4 GB at 128K context, versus ≈ 40 GiB for GQA-70B.
Two equivalent computation modes. (a) MHA mode: recover full per-head K and V from the latent and run ordinary attention. This costs an extra GEMM and transient full-size K/V; fine for prefill, which is compute-bound anyway and well served by mature dense kernels. (b) MQA mode (absorption). This is where the elegance lives. Now watch what happens to the score between query at \(t\) and key at \(j\), head \(h\) (ignoring the RoPE path for one line): \[ s_{tj} = q_{t,h}^{\top} k_{j,h} = \big(W_{Q,h} h_t\big)^{\top} W^{UK}_h c_j = \underbrace{\big(W^{UK}_h W_{Q,h} h_t\big)^{\top}}_{\text{absorbed query } \hat{u}_{t,h} \in \mathbb{R}^{512}} c_j. \] The product \(W^{UK}_h W_{Q,h}\) is a single fused matrix computed once at load time; each head's absorbed query is 512-dimensional and scores directly against the cached latent. K is never materialized. The RoPE path re-enters additively: the full score is \(\hat{u}_{t,h}^{\top} c_j + q^R_{t,h}{}^{\top} k^R_j\), which is exactly why \(k^R\) had to be decoupled: that second term cannot fold into the first. On the value side the same magic works in reverse: \[ out_{t,h} = \sum_j \alpha_{tj}\, W^{UV}_h c_j = W^{UV}_h \underbrace{\sum_j \alpha_{tj}\, c_j}_{\in\, \mathbb{R}^{512}}, \] so the attention-weighted sum accumulates in the 512-dim latent space and is up-projected once. And \(W^{UV}\) merges with the output projection just as \(W^{UK}\) merged with \(W_Q\).
Possible answer
It is multi-query attention with head dim 576: all 128 heads attend to one shared 576-dimensional "KV" per token, so a decode step reads one latent cache, not one KV copy per head. Bytes per cached token per step: exactly \(kv_{MLA} = 576\ \text{B} \times 61 \approx 34\) KB, versus 320 KB for GQA-70B: \[ \frac{kv_{GQA}}{kv_{MLA}} = \frac{327{,}680}{35{,}136} \approx 9.3. \] In the intensity formula the \(kv\) term divides by 9.3: bandwidth traffic per step and HBM capacity per cached token drop by the same factor. That means larger \(B\) at fixed memory and higher throughput at fixed bandwidth.
The costs, because there is no free lunch. (i) Effective head dim grows to 576: attention FLOPs per token per layer per cached token scale as \(4\, n_h\, d_{eff}\), so absorbed MLA costs \(4 \times 128 \times 576 = 294{,}912\) versus \(4 \times 64 \times 128 = 32{,}768\) for GQA-70B: 9× the attention FLOPs. The trade is deliberate: exchange surplus compute for scarce bandwidth. That is the right direction, because decode is memory-bound. (For contrast: had MLA materialized full K/V instead, the ratio would be only 2×.) (ii) Non-standard kernel shape: "high-compute-intensity MQA" (128 query heads, one shared 576-dim KV) matches no standard kernel's tiling, so MLA needs a dedicated implementation: FlashMLA (Lecture 7), which supports FP8 KV with the latent quantized on write, and (as you now expect) dictates page size 64.
Everything so far assumed all model state is per-token KV. The 2026 generation of flagship hybrids breaks that assumption. Kimi K3 (Moonshot AI; 2.8T total / 104B activated, 93 layers, 1M context) interleaves two attention mechanisms in a 3:1 ratio: 69 KDA layers (Kimi Delta Attention, a gated delta-rule linear attention) plus 24 Gated-MLA layers at positions 4, 8, …, 92, with NoPE throughout. Each mechanism carries a different kind of serving state:
Step 1: the MLA side is per-token and paged. Each Gated-MLA layer caches exactly the MLA object from the previous section: a 512-dim latent plus a 64-dim positional key (under NoPE the key is never rotated, but it is still cached), 576 elements per token per layer: \[ kv^{K3}_{MLA} = 576 \times 2\,\text{B} \times 24\ \text{layers} = 27{,}648\ \text{B} = 27.0\ \text{KiB/token} \quad (\text{FP8 halves it to} \ 13.5), \] growing linearly in \(L\), paged and prefix-cacheable exactly as above.
Step 2: the KDA side is a fixed-size recurrent state. A KDA layer keeps, per head, a state matrix \(S_t \in \mathbb{R}^{128 \times 128}\), updated by a gated delta-rule recurrence \[ S_t = \big(I - \eta_t k_t k_t^{\top}\big)\, \mathrm{Diag}(\alpha_t)\, S_{t-1} + \eta_t\, k_t v_t^{\top}, \] with per-channel decay gate \(\alpha_t\) and delta-rule step size \(\eta_t\) (not to be confused with bandwidth \(\beta\)!): \[ \text{KDA state per layer} = 128 \times 128 \times 96\ \text{heads} \times 2\,\text{B} = 3.0\ \text{MiB}, \] fixed regardless of context length. Over 69 layers: \(\approx 0.20\) GiB per request. A constant, not a function of \(L\).
Step 3: the whole-request footprint. At \(L = 2^{20}\) (1M tokens): MLA cache \(= 27.0\ \text{KiB} \times 2^{20} = 27.0\) GiB; KDA state = 0.20 GiB; total ≈ 27.2 GiB, versus 320 GiB for a GQA-70B-style model. ≈ 12×. Sanity checks worth doing yourself: the crossover where KDA state exceeds the MLA cache sits at \(0.20\ \text{GiB} / 27.0\ \text{KiB} \approx 7{,}900\) tokens. Past ≈ 8K context the per-token cache dominates again, but with an 11.8× gentler slope than GQA. And one KDA layer's whole state equals \(3.0\ \text{MiB} / 1152\ \text{B} \approx 2{,}731\) tokens of one MLA layer's per-token cache: the constant price paid so that most of the model's state never grows.
Why does the KDA side break prefix caching? The hit condition rests on attention KV being a pure per-token function of the prefix: a block of \(b\) tokens is reusable iff its tokens match. A KDA state has no such granularity: it is a single running matrix, overwritten in place at every token, a function of all tokens \(1..t\). There is no "state of token \(t\)" to share independently, and the state cannot be reconstructed from any suffix. Classic block-granular caching is impossible; the fix, in both production engines, is to checkpoint the recurrent state at sparse boundaries and treat checkpoints as cache entries: vLLM decouples state blocks from hash blocks (6,144-token state blocks against 512-token hash blocks, copy-on-write restore, off by default); SGLang runs one unified pool (54 MB FP32 TP8 KDA state block + 27 KB MLA KV block) with copy-on-write / snapshot / donate primitives, so forking, rollback (speculative decoding, Lecture 8), and cache handoff operate uniformly across both cache types. In Mooncake, NIXL exposes each physical page through dual page views (the same bytes addressable as MLA KV pages and as KDA state checkpoints), so the pool is typed per state but the transport is unified.
TA says: a hybrid model is two KV-cache systems in one process. Size capacity from the sum (27 KiB/token growing + 0.20 GiB fixed per request for K3), but design reuse from the intersection: the effective prefix-cache hit is limited by the coarser of the two granularities (512-token MLA blocks vs. 6,144-token KDA checkpoints). When prompting agents, place mutable content so turn boundaries land near state checkpoints, or accept replaying up to one state block per turn (cheap: linear attention costs \(O(1)\) state-size work per replayed token). And remember this when Lecture 5 disaggregates prefill from decode: both state types must cross the network together.
page_size=16 and
then enabling FlashMLA fails at integration time, not at design time.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 engineering; it's the habit of thinking about these things that counts: you have ideas, you try; if they don't work, you think again.
What happened
Your OS textbook says: fixed-size pages, per-process page tables, allocate on demand, free into a shared pool. The two workload properties: (i) the reservation-blindness matters precisely because output lengths are unknowable at admission (so demand-paging beats pre-sizing); (ii) all requests' KV have the same per-token byte cost, so one block size fits every request and external fragmentation dies by construction. This is exactly PagedAttention (vLLM, 2023): expected waste drops to \((b-1)/2 = 7.5\) tokens at \(b = 16\), and the block abstraction became the substrate for everything in this module: sharing, prefix caching, offload. vLLM, SGLang, and TensorRT-LLM all now use it. The one cost the textbook also predicts: indirection on the critical path, and a page-size war settled not by operators but by kernels (FlashMLA → 64; V3.2 → 64 + 1).
Possible answer (Module 2, Exercise 2.5)
A: \(0.2 \times 2.896\ \text{s} + 0.8 \times 8192 \times 327{,}680 / 64\times 10^{9}\ \text{s} + 0.1\ \text{s} = 0.579 + 0.034 + 0.1 = 0.71\) s. B: the full 2.90 s of prefill. Choose A: the 100 ms queue is repaid many times over. For indifference versus halved TTFT, solve \((1-h)\,T_{re} + h\,T_{xfer} = T_{re}/2\) with \(T_{xfer} = 8192 \times 327{,}680 / 64\times10^9 = 41.9\) ms: \[ h = \frac{T_{re} - T_{re}/2}{T_{re} - T_{xfer}} = \frac{2.896 - 1.448}{2.896 - 0.042} \approx 0.51. \] Any overlap above ≈ 51% halves TTFT even when the hit arrives over PCIe. This is why cache-aware routing pays, and why session stickiness is such a strong baseline.
Existing attempts (2026)
What you give up: hit granularity degrades to the coarser of the two granularities, so effective \(h\) on the state side is rounded down to the last checkpoint. The general lesson: once the model carries two state types, the pool must be typed per state but the transport and the CoW machinery can be unified.
You are the router. A request with a cached prefix arrives, but the cache lives on some storage tier. Is fetching the hit worth it, or should you just recompute (or route cold)? Set the hit rate, the context, and the tier, and watch the TTFT decomposition. Can you find a corner where a hit hurts? (Hint frames: slowest tier, long context, GQA model... then explain it still rarely loses to recompute (the break-even derivation tells you why).)
Take Lab 2: KV Cache and Prefix Caching from the course's hands-on pack (vLLM, one GPU):
--enable-prefix-caching) and read the startup lines: block size
(block_size=16), KV cache size in blocks; track
vllm:gpu_cache_usage_perc and the hit counters on /metrics.Pitfalls to dodge in your own benchmark: duplicated prompts silently inflate \(h\); comparing engines with caching toggled inconsistently; forgetting that hit counters reset per engine restart.