The main question of this lecture: when the past gets a million tokens
long, do we really have to READ all of it every step?
Imagine you are chatting with a coding agent that has read your entire repository: a
million tokens of history. And you notice something odd: every new reply is slower than the last,
and the provider quietly charges you more per turn. Nothing changed in the model. What changed is
the length of the past it drags behind itself.
In Lecture 1, context length \(L\) was a background parameter that lived inside the KV-cache
term. That was fine at 4K tokens. But as production windows grew from 4K to 128K to 1M tokens,
\(L\) stopped being a parameter you set and became the dominant structural force in the whole cost
model. This lecture follows \(L\) as it takes over: first the formulas, then the parallel hardware,
and then, because brute force truly fails, the architecture of attention itself.
Main idea: long context attacks four costs at once: prefill compute
grows quadratically in \(L\), while decode bandwidth, memory, and transfer all grow
linearly. Compression (MLA) improves the constants; only reading less of the past
(sparse or recurrent attention) changes the growth order. Keep this
sentence in your pocket for
the rest of the lecture.
Prefill: The Attention Term Overtakes \(2P\)
Lecture 1's "\(2P\) FLOPs per token" rule quietly counted only the linear layers. The omission is
the attention operator, whose cost depends on how many keys each query attends to. And
that number is \(t\), the position itself. Let us add the term back, step by step.
The count. Take one query of one head: \(q \in \mathbb{R}^{d_h}\) dotted against \(t\) key
vectors, each dot product \(2 d_h\) FLOPs, so one head costs \(2 t d_h\). Summing over \(n_{heads}\)
heads with \(n_{heads} d_h = d_{model}\):
\[ \underbrace{2 t d_{model}}_{QK^\top\ \text{scores}} \;+\; \underbrace{2 t d_{model}}_{AV\ \text{aggregation}}
\;=\; \boxed{4 t\, d_{model}} \quad \text{FLOPs per layer per token.} \]
Multiplying by \(n_{layers}\) and summing over positions (causal average \(t = L/2\)):
\[ C_{attn}^{model} = \sum_{t=1}^{L} 4t\, d_{model} n_{layers}
\approx 2 L^2 d_{model} n_{layers} \ \text{(causal)}, \qquad 4 L^2 d_{model} n_{layers} \ \text{(full).} \]
The same prefill's linear layers cost \(2P \cdot L\). The ratio that matters is therefore
\[ \frac{C_{attn}}{C_{linear}} = \frac{4 L\, d_{model}\, n_{layers}}{2P} \;(\text{per token}),
\qquad\text{and the crossover is at}\qquad
L^* = \frac{2P}{4\, d_{model}\, n_{layers}}. \]
?Before I substitute numbers: which way does \(L^*\) move if the model gets deeper, or
wider? And why? Think for a minute; the formula is right above.
Possible answer
Down. Deeper or wider models cross over earlier, because depth and width spend their
parameter budget partly on attention, not only on linear layers: \(d_{model} n_{layers}\) grows
while \(P\) grows less than proportionally. The sanity checks behave: the ratio is dimensionless,
\(L^*\) has units of tokens, the ratio vanishes as \(L \to 0\) (short context is
linear-dominated ✓) and grows linearly in \(L\). That is exactly why prefill time is
quadratic in \(L\) once attention leads.
Worked example (do it with me):
Llama-3.3-70B: \(P = 70 \times 10^9\), \(d_{model} = 8192\), \(n_{layers} = 80\):
\[ L^* = \frac{2 \times 70 \times 10^9}{4 \times 8192 \times 80}
= \frac{1.4 \times 10^{11}}{2.621 \times 10^{6}} = 5.34 \times 10^{4} \approx \textbf{53K tokens.} \]
Below ~50K context, attention is the minority of prefill FLOPs and the \(2P\) approximation is
serviceable. Above it, attention dominates and prefill time grows quadratically. At \(L = 1\)M
(\(2^{20} = 1{,}048{,}576\)):
\[ \text{ratio} = \frac{4 \times 1{,}048{,}576 \times 8192 \times 80}{2 \times 70 \times 10^9} \approx 19.6 \approx 20\times, \]
Think about that: attention is ~90% of all prefill compute. On \(8 \times\)H100 at 50% MFU
this prefill takes \( \approx 1.45 \times 10^{18} / (8 \times 4.95 \times 10^{14}) \approx 366\) s.
That is over six minutes of time-to-first-token for a single request. That is the
quantitative reason a dense 1M prefill is not a serving product; it is the problem the rest of
this lecture attacks.
How to: walk right along the x-axis as your prompt grows. The green line (weights)
does not care how long the past is; the red line (attention) climbs steadily, and at L* ≈ 53K it
becomes the boss. Everything to the right of the dashed line is "long-context country".
Note on accounting: the headline "≈ 20× at 1M" uses full-attention
accounting; with the causal mask the attention term halves to \(2 L^2 d_{model} n_{layers}\), and
at \(L = 10^6\) the honest causal division gives \(1.31 \times 10^{18}\) vs \(1.40 \times 10^{17}\)
FLOPs, a ratio of ≈ 9.4×. Both readings agree on the conclusion (attention dominates long
prefill); the ≈ 20× headline's own causal average is ≈ 9.8×. I flag this because the printed text
mixes the two conventions on the same page. When you compare numbers, always ask which mask the
author assumed.
Decode: Every Step Re-reads the Whole Past
Prefill hurt because of a quadratic term. Decode hurts in a different way: a
linear one, and it hits bandwidth instead of FLOPs. Recall Lecture 1's intensity spine:
\[ I \approx \frac{2P\,B}{2P + B \cdot kv}. \]
The context length hides inside \(kv\): a request with context \(L\) holds \(L\) tokens of keys and
values, and every decode step reads all of it:
\[ kv_{request} = \underbrace{2 \times n_{layers} \times n_{kv} \times d_h \times b_{dtype}}_{\text{bytes per token}}\cdot L. \]
Worked example: Llama-3.3-70B (GQA): \(n_{layers}=80\), \(n_{kv}=8\),
\(d_h=128\), BF16 → 327,680 B = 320 KB per token. At \(L = 128\)K:
\[ kv_{request} = 320\ \text{KB} \times 131{,}072 = 42.9\ \text{GB} \;(=40\ \text{GiB}), \]
read once per step on an H100 (\(\beta = 3.35\) TB/s):
\[ t_{KV} = \frac{40\ \text{GB}}{3.35\ \text{TB/s}} \approx 12\ \text{ms}, \]
against a weight-read floor of \(140\ \text{GB} / 3.35\ \text{TB/s} \approx 42\) ms. One
request's KV read is already ~29% of the entire all-weights read; a second such request
adds another 12 ms, and nothing in the intensity formula amortizes it.
The \(B \cdot kv\) term grows linearly in both \(B\) and \(L\).
The capacity front. Bandwidth is only half the squeeze. The 40 GB must also physically
fit. BF16 weights of 70B occupy 140 GB, so on 80 GB H100s you need at least TP=2
(70 GB/GPU: a whole 128K cache no longer fits in the 10 GB left). With TP=4: weights 35 GB/GPU,
each GPU holds \(40/4 = 10\) GB of KV per request, and after activations and runtime overhead:
\[ B \le \left\lfloor \frac{80 - 35 - \text{overhead}}{10} \right\rfloor = 4\text{–}5 \text{ requests.} \]
TP=8 raises the cap to ~12 in idealized accounting. But real systems reserve memory for CUDA
graphs and fragmentation, and 256K contexts halve every figure again (TP=4 → \(B \le 2\)).
Long-context decode pushes the per-GPU batch limit to single digits. Small \(B\) and large
per-request \(B \cdot kv\) both drag intensity back into the bandwidth-bound region: decode is
squeezed on two fronts at once.
Engineering Takeaway: size long-context capacity planning with
two constraints, not one: per-step KV-read time (\(L \cdot kv / \beta\)) caps latency, and
the per-request footprint caps batch size. A 128K-context 70B service on H100s is bandwidth-bound
at any batch size and capacity-capped at single-digit batches. Quota and pricing must reflect
both, not just token counts.
So here is what long context does to each line item from Lecture 1:
Cost item
Growth in \(L\)
Mechanism
Prefill time
\(O(L^2)\)
attention term \(4 L d_{model} n_{layers}\) per token
Decode per-step bandwidth
\(O(L)\)
full KV cache re-read every step
Memory capacity
\(O(L)\)
KV bytes/token × \(L\)
Transfer (offload, PD)
\(O(L)\)
moving the cache between tiers/instances
Four rows, one villain. Note: MLA-style compression shrinks the per-token
constant (~320 → 34 KB/token, ≈ 9.3×) but not the growth order: every row still grows with
\(L\). Changing the growth order requires changing what attention reads.
Teamwork First: Ring Attention for the Giant Prefill
Here you will distribute the work of reading a long prompt. For generation after that prompt,
Lecture 6's decode context parallelism
section shows how to distribute its cached history and trade communication for KV capacity.
Why a single GPU cannot do it. A 1M-token prefill of a 70B-class model needs (a) ~400 s of
compute even spread across 8 GPUs, (b) KV memory for 1M tokens (\(320\ \text{KB} \times 10^6 = 320\)
GB for Llama-3.3-70B alone), and (c) a TTFT a user can tolerate. A single GPU fails on all three.
The easiest thing you can do is shard the sequence itself: context parallel (CP)
gives GPU \(i\) the Q/K/V of segment \(i\) (length \(L/N\)). Linear layers and layer norms are
embarrassingly parallel along the sequence; only attention needs cross-GPU data. And the naive
fix, gathering every K/V on every GPU, recreates the memory blow-up you were trying to escape. So
instead, let the K/V travel:
How to: pick GPU 0 and watch the green chips do one lap. Its own Q segment never
moves; the world's K/V flows to it. Partial results are merged on the fly with the online-softmax
trick (the same running-max rescaling as FlashAttention, Lecture 7), so nobody ever materializes
the full \(L \times L\) score matrix.
How much travels? Per layer, each GPU sends and receives \(N-1\) blocks of
\((L/N)\) tokens, so its per-layer traffic is
\[ V_{comm} = \frac{N-1}{N} \cdot L \cdot kv_{layer}, \qquad kv_{layer} = 2\, n_{kv}\, d_h\, b_{dtype}. \]
For Llama-3.3-70B (\(kv_{layer} = 4096\) B/token), \(L = 1\)M, \(N = 8\):
\(V_{comm} = \frac{7}{8} \times 10^6 \times 4096 \approx 3.6\) GB per layer, ≈ 287 GB per GPU for the
whole 80-layer prefill. That is ≈ 0.32 s on 900 GB/s NVLink, and ≈ 5.7 s even on 50 GB/s
inter-node InfiniBand.
Can we hide it? Ring step \(i\) transfers one block \((L/N)\, kv_{layer}\) bytes while
computing attention of \(L/N\) queries against \(\sim L/N\) keys, i.e. \(4 (L/N)^2 d_{model}\) FLOPs
per layer. Overlap succeeds when
\[ \underbrace{\frac{4 (L/N)^2 d_{model}}{\pi_{eff}}}_{\text{compute per step}} \;\ge\;
\underbrace{\frac{(L/N)\, kv_{layer}}{\beta_{link}}}_{\text{transfer per step}}. \]
Numerically (L = 1M, N = 8, H100): compute ≈ \(4 \times 125{,}000^2 \times 8192 = 512\) TFLOP ≈ 517 ms
at 990 TFLOPS (258 ms with the causal half); transfer = 512 MB ≈ 0.57 ms on NVLink (10 ms on IB).
Compute outweighs transfer by two to three orders of magnitude. Here is the
structural reason ring attention works: attention compute is \(O(L^2)\) per GPU while ring traffic
is \(O(L)\), so the longer the context, the easier communication is to hide. CP scales best
exactly where the problem is worst.
The flaw you should have noticed: sequential sharding interacts badly with the causal
mask. GPU 0's queries attend to 1 block of keys, GPU 1's to 2, ..., GPU \(N-1\)'s to all \(N\).
Work per GPU is proportional to \(i+1\), the tail GPU does \(2N/(N+1) = 1.78\times\) the average
(at \(N = 8\)) while the head GPU idles. The standard fix is zigzag (interleaved/striped)
partitioning: GPU \(i\) takes chunk \(i\) and chunk \(2N-1-i\), so each GPU's block
count is \((i+1) + (2N-i) = 2N+1\), identical for all \(i\) (every GPU holds exactly 17 block-units
at \(N = 8\)). Balance is restored without changing the math, at the cost of non-contiguous token
ownership.
Note: where CP fits. It solves feasibility and TTFT of one giant
prefill. It does not make that prefill cheaper (total FLOPs are unchanged!). That is the
deficiency that will push us to change attention itself in the next section. CP is orthogonal to
TP/PP (Lecture 6: CP shards the sequence, TP the hidden dims, PP the layers) and composes with
chunked prefill (Lecture 4: a different problem, scheduling interference). Typical deployment: CP
inside prefill instances of a PD-disaggregated system, and no CP in decode, because
decode has no quadratic term to shard, only a KV cache to place.
Engineering Takeaway: ring attention's overlap works because compute is
\(O(L^2)\) and traffic is \(O(L)\); even inter-node IB (50 GB/s) is hideable at 1M context. Spend
your effort on the load balancer (zigzag partitioning) and on online-softmax correctness
instead of interconnect upgrades: a sequentially sharded ring wastes ~45% of the fleet on idle
head GPUs.
The Architectural Answer: Read Less of the Past
Context parallel survived the quadratic prefill; it did not remove it. And decode still
re-reads the whole 40 GB every step. You can probably guess the next move. But let us build the
need for it from three empirical facts:
Attention weights are highly sparse. Each query's probability mass concentrates on a
few keys, so the full \(L\)-wide read is mostly wasted bandwidth.
Post-hoc bolt-on sparsity is unreliable. Heuristic KV dropping or eviction by
accumulated score has unstable accuracy, and dropped tokens are unrecoverable: the model was
never trained to live without them.
Therefore the modern direction is native sparsity: the sparse structure enters
training, so the model learns under the constraint from the start and the systems stack
can rely on the pattern.
NSA (Native Sparse Attention, DeepSeek 2025) was the proof of concept: each query reads
history through three parallel branches, merged by a learned gate: compression
(adjacent token blocks squashed into one coarse representation each: a cheap global gist),
selection (top-few original token blocks by importance: fine detail where it matters), and
a sliding window (most recent tokens, exact: local syntax and recency are always
full-fidelity). Crucially the pattern is hardware-aligned: selection happens at block
granularity, matching tensor-core tiles and paged memory. NSA established that sparsity can be
trainable and hardware-friendly at once.
DeepSeek-V3.2 DSA (DeepSeek Sparse Attention) took it to production in the flagship. The
design is two-stage: lightweight scoring over the entire history, then exact attention over a
selected few.
Stage 1, the lightning indexer. Every token carries one 128-dim FP8 indexer key;
64 indexer heads share that key (MQA-style), so the indexer cache costs only
132 B/token (128 B key + 4 B scale), about \( \frac{1}{4} \) of the 576 B MLA latent
entry. Each query scores against all history with a weighted-ReLU dot product:
\(O(L)\) work, but extraordinarily light per token. No value tensor, no full attention. The
only output is a ranking.
Stage 2, sparse main attention. The top \(k = 2048\) tokens by indexer score are
selected, and MLA attention is computed exactly, only over those \(k\). Main-attention
cost drops from \(O(L \cdot d_{latent})\) to \(O(k \cdot d_{latent})\): independent of
\(L\).
How to: follow the amber dashed arrow first. The indexer sweeps everything,
every step, but at only 132 B per token. Then notice that the expensive 576 B reads happen only on
the blue (top-k) and green (recent) ticks. The grey ticks are the money saved.
Let us put per-stage numbers on it (this is Derivation 4 of the module; worth redoing
yourself once). Per layer per decode step:
\[ \text{dense MLA: } L \cdot 576\ \text{B} \quad\Longrightarrow\quad
\text{DSA: } \underbrace{\color{#4a6fa5}{k \cdot 576\ \text{B}}}_{\text{main: constant in } L} + \underbrace{\color{#c95a4a}{L \cdot 132\ \text{B}}}_{\text{indexer: the residual } O(L)}. \]
At \(L = 128\)K: main attention reads \(2048 \times 576 = 1.18\) MB instead of
\(131{,}072 \times 576 = 75.5\) MB, a 64× reduction (\(= L/k\)); the indexer adds
\(131{,}072 \times 132 \approx 17.3\) MB per layer. Per-history-token compute: indexer =
\(64 \times 128 \times 2 = 16.4\) KFLOP (FP8) vs absorbed MLA main attention =
\(128 \times (576 + 512) \times 2 \approx 279\) KFLOP, a 17× ratio (and FP8 tensor cores roughly
double the gap in wall-clock). Whole model at 128K (61 layers):
\[ \text{dense MLA: } 61 \times 75.5 \approx 4.6\ \text{GB}\ (\approx 1.37\ \text{ms}), \qquad
\text{DSA: } 61 \times (1.18 + 17.3) \approx 1.13\ \text{GB}\ (\approx 0.34\ \text{ms}). \]
That is about 24% of dense. Sparse attention converts decode bandwidth from "grows with \(L\) at
576 B/token" to "grows with \(L\) at 132 B/token plus a constant".
Warning: the indexer's O(L) term is still there. DSA's main attention
is constant in \(L\), but the lightning indexer still scans all of history every step. At
128K the indexer read (1.06 GB across 61 layers) is 15× larger than the sparse main read
(0.072 GB); the crossover is at \(L = 576k/132 \approx 8.9\)K tokens. Beyond ~9K context, the
indexer scan costs more than the entire exact pass, and at 1M it is 8.05 GB/step. "Decode
bandwidth decoupled from \(L\)" is true only of the 576 B/token component. Also note the honest
accounting caveat: with MLA absorption the indexer/main gap is ~17× in FLOPs and ~4.4× in bytes
(132 vs 576 B); the "two orders of magnitude" version compares against materialized
per-head K/V (~80 KB vs 132 B: 620×). Either way, one to two orders lighter. But the growth
order survives in the indexer.
DeepSeek-V4: Compress the History, Then Sparsify It
The deficiency DSA leaves us is that stubborn 132 B/token scan. V4 (V4-Pro: 1.6T total /
49B activated; V4-Flash: 284B / 13B) attacks it by compressing the candidates themselves,
and ships 1M context as the official serving default:
CSA (Compressed Sparse Attention). A learned compression merges the KV of \(m = 4\)
adjacent tokens into one entry. DSA-style top-k selection then operates on the compressed
sequence: the candidate set shrinks to \(L/4\) entries, the cache shrinks 4× per unit history,
and sparse selection keeps query-relevant detail within the compressed stream.
HCA (Heavily Compressed Attention). A much higher rate \(m' = 128\) merges distant
history into \(L/128\) entries, attended densely: a low-cost global information pathway,
the evolved form of NSA's compression branch.
Recent tokens keep an exact sliding window, as in NSA/DSA.
The back-of-envelope (per history token, per layer) tells the whole arms race in four rows:
Scheme
Cache bytes / history token
Decode-step read
V3 dense MLA
576
\(576 L\)
V3.2 DSA
\(576 + 132 = 708\)
\(576 k + 132 L\)
V4 CSA tier
\((576 + 132)/4 = 177\)
\(576 k + 132\, L/4\)
V4 HCA tier
\(\approx 576/128 + 132/128 \approx 5.5\)
\(576 \cdot L/128\) dense
Worked example (does the back-of-envelope match the marketing?):
at \(L = 1\)M, 61 layers: DSA cache = \(61 \times 10^6 \times 708 \approx 43.2\) GB; per-step
read = \(61 \times (2048 \times 576 + 10^6 \times 132) \approx 8.1\) GB. A V4 layout with all
history in CSA + an HCA global tier reads
\(61 \times (2048 \times 576 + (10^6/4) \times 132 + (10^6/128) \times 576) \approx 2.4\) GB/step:
≈ 29% of DSA. For cache: all-CSA ≈ 11.1 GB (26% of DSA); with 50% of history promoted
to HCA ≈ 5.5 GB (12.8%); at 75% HCA ≈ 2.9 GB (6.8%). Public analyses report V4 long-context
compute ≈ 27% and KV cache ≈ 10% of V3.2's. Our envelope lands at 29% for the bandwidth proxy
and in the 7–26% band for cache: consistent with most deep history living in the HCA
tier. Notice what happened strategically: the per-token cost of long context changed from
growing linearly with \(L\) to nearly constant. That is the technical basis for the API's large
long-context price cut.
Engineering Takeaway: the design lineage is a constant-factor arms race
against the \(O(L)\) term: dense reads 576 B/token-step (MLA), DSA reads 132 B/token-step plus a
constant \(k\)-sized exact pass, V4 reads ~33 B/token-step over compressed entries plus an
\(L/128\) dense global trickle. When evaluating any future sparse scheme, skip the accuracy
marketing and ask two questions: what is the per-token-step byte cost of the residual
\(O(L)\) term, and is the selection pattern block-aligned?
The 2025–2026 Hybrid Turn: Linear Attention Returns
NSA, DSA, and V4 all kept softmax attention and shrank its read set. The parallel
2025–2026 line is more radical: replace most softmax layers with linear attention, whose
state is a fixed-size recurrent matrix, read in \(O(1)\) per decode step and updated in \(O(1)\)
per token, and keep a minority of full/sparse attention layers for exact global recall. Two 2026
flagships define the pattern:
Kimi K3 (Moonshot AI; 2.8T total / 104B activated; 93 layers; 1M context):
69 KDA layers (Kimi Delta Attention, a gated delta-rule linear attention) + 24
Gated-MLA layers at positions 4, 8, …, 92: a 3:1 hybrid, with NoPE everywhere (no RoPE;
KDA's content-dependent gating supplies the position signal). The motivating measurements from
Kimi Linear: 6.3× faster decode at 1M than full attention (TPOT 1.84 ms vs 11.48 ms).
GLM-5.3-Flash (Zhipu; 321B total / 18B active; 45 layers): 34 KDA layers + 11 NoPE
sparse-MLA/DSA layers, one every 4th layer. The sparse layers add IndexPool
(four indexer keys pooled into one, index_kpool = 4), quartering the indexer
cache: the residual \(O(L)\) term we flagged. Against GLM-5.3 (78 layers of MLA + DSA):
3.0× less attention compute and 4.4× smaller KV cache (a derived ≈ 1.15 KB → ≈ 0.26 KB per
token per layer on the BF16 per-layer basis).
The convergence is broad. DeepSeek's CSA/HCA and Qwen3-Next's gated delta networks (3:1
GDN : gated attention) are the same idea from different directions: a cheap recurrent or
compressed pathway carrying most layers, an exact pathway kept sparse and rare. The notable
dissenter is MiniMax: M2/M3 dropped linear-attention layers after failed ablations, a reminder
that the hybrid turn is empirical, not inevitable.
☺
TA says: do K3's asymptotics with me explicitly (Derivation 6). Per
decode step, per request:
\[ \text{bytes read/step} = \underbrace{69 \times 3.0\ \text{MiB}}_{\text{KDA state: } O(1) \text{ in } L}
\;+\; \underbrace{24 \times 1{,}152\ \text{B} \times L}_{\text{MLA cache: } O(L)\ [\text{or } O(k) \text{ if sparse}]} \]
where 3.0 MiB is one KDA layer's fixed BF16 state (\(128 \times 128\) per head × 96 heads) and
1,152 B/token/layer is the MLA latent (576 elements, BF16). At \(L = 1\)M:
\[ \approx 0.20\ \text{GiB} + 27.0\ \text{GiB} = \textbf{27.2 GiB} \quad\text{vs}\quad
\textbf{320 GiB} \text{ for GQA-70B-style} \ (\approx 12\times). \]
On H100 HBM that is ≈ 8.7 ms vs ≈ 103 ms of state/KV read per step. The \(O(1)\) floor dominates
only below \(L \approx 0.20\ \text{GiB} / 27.0\ \text{KiB} \approx 7.9\)K tokens. Beyond that, the
24 MLA layers' linear term rules again, with a slope 11.8× gentler than GQA; and DSA-style top-k
(GLM-5.3-Flash's design) can convert even that to \(O(k)\) plus an indexer scan.
How to: compare the bar lengths. They are proportional to time per step, not
to model quality. K3's bar has two parts: a constant floor that never grows (green) and a thin
growing term (blue). The lesson: the 12× gap widens as \(L\) grows, because part of K3's
state simply never grows at all.
Set the hybrid against the four-line cost table from earlier. It changes every row's
structure, not just its constant:
Cost item
Dense attention
K3 hybrid (69 KDA + 24 MLA)
Prefill time
\(O(L^2)\) all layers
KDA layers \(O(L)\) (chunkwise, chunk 64); the 24 MLA layers stay \(O(L^2)\) unless sparsified ⇒ quadratic coefficient ≈ 24/93 ≈ 26% of an equal-depth dense model
Decode bandwidth
\(O(L)\) at 320 KB/token
\(O(1)\) for 69 layers + \(O(L)\) at 27 KiB/token for 24
Memory capacity
\(O(L)\)
\(O(L)\) at 27 KiB/token + 0.20 GiB fixed
Prefix-cache reuse
per-block hits
MLA blocks hit at page granularity; KDA state only at sparse checkpoint boundaries (Lecture 2, §2.6)
Note: the honest caveat lives in row one. Linear attention removes the
quadratic term only for the layers that use it. K3's prefill still contains 24 quadratic
layers (chunked KDA prefill is \(O(L)\) via the chunk-parallel delta rule, not \(O(L^2)\)), so
its 1M prefill is far cheaper than a dense 93-layer model's but not yet linear
end-to-end. The pressure to make the remaining attention layers sparse is exactly
GLM-5.3-Flash's answer.
Engineering Takeaway: evaluate a hybrid model as two cost models
glued together: a constant floor (0.20 GiB/request of KDA state, present at any context
length) plus a thin linear term (27 KiB/token of MLA cache). Below ≈ 8K context the floor
dominates, so short-context capacity planning is about the fixed state, not the cache; above it,
the linear term rules and the same sparse-attention toolkit applies to the minority layers. And
budget for two cache systems with different reuse granularities in every engine you
deploy on.
Sparsity Is a Systems Feature: The Blast Radius
DSA is a model-architecture change, but its blast radius covers the whole serving stack. This
is where "just load the new weights" goes to die:
KV-cache management. One latent cache becomes two: the MLA latent KV cache
(576 B/token, FP8) and the indexer key cache (132 B/token, different dtype/shape/access
pattern). In SGLang the memory pool keeps separate buffers for indexer key and key-scale, and
two page sizes coexist in one backend: the indexer kernel requires page size 64 while the
token-level sparse-read operator requires page size 1. In vLLM, latent and indexer keys are
quantized on write and two independent prefill/decode execution paths are maintained. Prefix
caching extends accordingly: the two caches must hit together and be evicted together;
otherwise a prefix hit returns a latent cache whose ranking basis has been dropped.
Decode memory-access pattern. Per-step KV read changes from \(O(L)\) to a fixed
\(k = 2048\) tokens (0.072 GB at any context length); long-context decode bandwidth is decoupled
from \(L\) for the main attention, and throughput no longer degrades as context grows. The
residual \(O(L)\) is the indexer scan. But it touches a small 132 B/token cache, so the
degradation slope is ~4.4× gentler than dense MLA (and ~2400× gentler than Llama-style GQA).
Offload feasibility changes qualitatively. Under dense attention, swap-in is
all-or-nothing. After sparsity, each step needs only the top-\(k\) selected entries, so the full
latent cache can in principle sink to slower tiers (DRAM), fetched by index, with the GPU hosting
only the much smaller indexer cache (1.06 GB vs 4.61 GB at 128K). The difficulty shifts to
locality and prefetching: the top-\(k\) overlap between adjacent decode steps decides
whether the fetched set is nearly static (DRAM latency hidden) or 2048 scattered entries get
pulled over PCIe every step. An active engineering direction.
Kernel layer. The full DSA pipeline chains three specialized kernels: DeepGEMM for
indexer scoring (FP8 GEMM over the 128-dim keys), a fused top-\(k\) selection, and FlashMLA
sparse (MQA-shaped, FP8, paged gather by token indices). Sparsity did not remove the kernel
problem; it replaced one monolithic kernel with a pipeline whose stages must be jointly
tuned.
Common pitfalls (keep this list by your keyboard):
"Post-hoc KV dropping is free accuracy." Serving-side eviction after training shows
unstable accuracy and dropped tokens are unrecoverable. Treat any KV eviction scheme as an
accuracy experiment, not an optimization. Native sparsity works because the
constraint was present during training.
Sequential sharding in context parallel. The tail GPU gets
\(2N/(N+1) = 1.78\times\) the average work while the head idles. Always zigzag-partition;
verify balance by counting attended blocks per GPU, not equal token counts.
Forgetting the indexer's \(O(L)\) term. At 128K the indexer read is 15× the sparse
main read; at 1M it is 8 GB/step. Only the 576 B/token component is decoupled from \(L\).
Assuming MLA changes growth order. MLA compresses the constant (~9× vs GQA); every
row of the cost table stays \(O(L)\) or \(O(L^2)\). Compression buys time; only sparsity changes
asymptotics.
Splitting the two DSA caches in prefix caching. Evicting indexer keys while keeping
latent KV (or vice versa) silently corrupts the ranking basis for a cached prefix. The pair is
one logical object: co-hit, co-evict.
Research Thinking
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 a habit of thinking that counts: you have ideas, you try; if they don't work, you
think again.
?Card 1, "invent" sparse attention. Starting point: every decode step re-reads the whole
\(L \cdot kv\) cache; a 128K request costs 12 ms of KV reads per step, and attention weights are
empirically concentrated on a few keys. Question: what exactly do you have to change
(in the model, the training, and the system) before you may safely read only part of
the past? What breaks first if you skip one of these?
Some existing attempts
Three things must move together. Selection needs a scorer: something cheap must rank
all of history every step without paying the full attention cost (DSA's lightning indexer: one
shared 128-dim FP8 key per token → 132 B/token, 17× lighter than the exact pass).
Sparsity needs training: serving-side eviction of an untrained pattern has unstable
accuracy (pitfall 1); NSA put the constraint in training, on hardware-aligned block
granularity. The system needs two caches and coupled eviction: vLLM and SGLang both grew
dual-pool abstractions, dual page sizes (64 for the indexer, 1 for sparse token reads), and
co-hit/co-evict prefix caching to host it. Skip the scorer and selection is blind; skip training
and accuracy is unstable; skip the systems work and the speedup never materializes.
?Card 2, hunt the residual O(L) term. Starting point: DSA made the 576 B/token read
constant in \(L\), but the indexer still scans all history at 132 B/token per step; beyond
\(L \approx 576k/132 \approx 8.9\)K it is the dominant per-step read, reaching 8.05 GB/step at
1M. Question: what are your options for shrinking that scan? And what does each option
give up? Think about what the indexer actually needs to resolve.
Where production went with this (2026)
The 2026 answer was: compress the candidates, three ways. V4 CSA merges
\( m = 4 \) adjacent tokens' KV into one entry: the candidate set shrinks to \(L/4\) and the
scan to \(132 \cdot L/4\); you give up token-level resolution inside compressed blocks.
V4 HCA pushes \(m' = 128\) for distant history attended densely: you give up
sparsity there entirely and buy a cheap global pathway (≈ 5.5 B/history-token of cache).
GLM-5.3-Flash IndexPool pools four indexer keys into one: you give up nothing in the
exact pass and you quarter the indexer cache. The general rule from the Engineering Takeaway: ask
for the per-token-step byte cost of the residual term, and check the selection pattern
is block-aligned.
?Card 3, decide when to give up on softmax entirely. Starting point: K3's per-step read
is \(69 \times 3.0\) MiB (\(O(1)\)) + \(24 \times 1{,}152\) B \((\times L)\); the fixed floor
dominates below ≈ 7.9K tokens, the linear term above, and prefill still has 24 quadratic
layers. Question: if you were designing the next hybrid, how would you choose
the ratio of recurrent to attention layers? What workloads push you toward more of each, and
what systems property would you refuse to sacrifice?
Arguments from the field
More recurrent layers help long-decode workloads (per-step state read shrinks toward
the 0.20 GiB floor) and hurt nothing in prefill except... the remaining quadratic layers
dominate prefill asymptotics (K3: 24/93 ≈ 26% quadratic coefficient). So long-prefill
workloads push you toward more KDA or toward making the attention layers sparse (DSA/
IndexPool, as GLM-5.3-Flash did). More attention layers help exact global recall, which is
precisely what recurrent state compresses away. The property worth refusing to sacrifice is
prefix-cacheability: KDA state is overwritten in place and can only be reused at
checkpoint boundaries, while MLA pages hit at block granularity. A hybrid serving stack must
budget for both reuse granularities (Lecture 2) or lose the multi-turn economics of Lecture 1.
And a cautionary ablation: MiniMax M2/M3 dropped linear layers after failed ablations.
The ratio is an empirical question, and 3:1 is today's answer, not a law.
Have Fun! The Long-Context Cost-o-Meter
Enough reading. Now you drive the asymptotics. Pick an architecture and a context length and
watch the per-decode-step state read (and its time on an H100) change. Try: where does DSA stop
looking like a win? At which \(L\) does K3's fixed 0.20 GiB floor fall below its linear MLA term?
(We computed it together: ≈ 7.9K. Can your thumb find it?)
Physics: per-step bytes per request ÷ H100 HBM bandwidth. Watch the DSA line turn red
above ~8.9K tokens, exactly where \(132 L\) overtakes \(576 k\).
Seminar & Homework
Take Lab 3: Long Context from the course's hands-on pack and make the crossover appear
in your own measurements:
Setup: one GPU, an 8B dense model (\(d_{model} = 4096\), \(n_{layers} = 32\),
\(L^* \approx 30.5\)K), --max-model-len 65536, and prefix caching OFF,
since hits would corrupt the length sweep (pitfall #6).
Predict, then measure: sweep input length \(L \in \{1\text{K}, 4\text{K}, 16\text{K},
32\text{K}, 64\text{K}\}\); fit prefill time \(T_{prefill}(L) = aL + bL^2\) from 100 warmup-separated
requests at low rate; the two fitted terms should go equal near \(L^* \approx 31\)K. Expect a
factor ~2 from causal masking and be ready to explain it. Expected landmarks at 50% MFU: 34 ms
(1K) → 301 ms (8K) → 1.63 s (32K) → 4.40 s (64K).
Decode side: fit TPOT\((L) = c_0 + c_1 L\) and compare \(c_1\) to the prediction
\(kv/\beta \approx 39\) ns/token of context; the TPOT floor runs 4.79 ms (empty cache) →
6.08 ms (32K) → 7.36 ms (64K), and the 64K KV pool should read 8.0 GiB in the server log.
Optional MLA comparison: repeat the TPOT sweep on DeepSeek-V2-Lite-Chat
(≈ 30 KB/token vs the 8B's 128 KB/token) and watch the slope \(c_1\) shrink ≈ 4.2×.
Compression changes the constant, exactly the lecture's thesis.
Analysis questions worth a paragraph each: why does the empirical crossover differ from \(L^*\)
by a factor near 2 and which definition is the per-token one? At 64K, what fraction of TPOT is KV
vs weight reads, and why does that fraction grow with \(L\) but not with \(B\) in the same way?
What would TP=2 do to each term of TPOT?
Summary
Long context attacks four costs at once: prefill compute \(O(L^2)\), decode bandwidth
\(O(L)\), memory \(O(L)\), transfer \(O(L)\).
The attention term \(4 L d_{model} n_{layers}\) overtakes \(2P\) at
\(L^* = 2P/(4 d_{model} n_{layers}) \approx 53\)K for Llama-3.3-70B, and is ≈ 20× the linear
term at 1M (full-attention accounting; ≈ 9–10× causal). A 1M dense prefill costs ~366 s on
8×H100. Not a product.
Decode at 128K: a 40 GiB cache re-read every step (12 ms, ~29% of the all-weights read)
and a batch cap of 4–5 at TP=4. Capacity planning has two constraints.
Context parallel makes the giant prefill feasible: ring passing of K/V
(\(V_{comm} = \frac{N-1}{N} L\, kv_{layer}\)), online-softmax merging, zigzag partitioning
against the causal \(1.78\times\) imbalance. Compute \(O(L^2)\) vs traffic \(O(L)\) hides the
network exactly when context is long. But CP does not make the work cheaper.
Native sparsity evolved NSA → DSA → V4: trainable three-branch block sparsity; then a
lightning indexer (132 B/token) + exact top-\(k\) (\(k = 2048\)) making the main read constant
in \(L\) (the indexer scan is the new residual; watch pitfall #3); then CSA/HCA compress the
candidate stream itself (V4 ≈ 29% of DSA's per-step bytes and ≈ 10% of its cache by the public
numbers).
The hybrid turn: Kimi K3 (69 KDA \(O(1)\) + 24 Gated-MLA) reads ≈ 27.2 GiB/step at 1M vs
320 GiB for GQA. Evaluate it as a constant floor plus a thin linear term. Prefill keeps 24
quadratic layers; sparsifying them is exactly GLM-5.3-Flash's move.
Sparsity is a systems feature, not a model swap: two caches, two page sizes,
co-hit/co-evict prefix caching, a gather-based decode path, and offload whose viability hinges
on step-to-step top-\(k\) overlap.