Linear Attention: Move the Parentheses

Part 2 of 4 on how a transformer remembers. KV cache · → Linear attention · Kernelization · Recurrent memory

Last post ended with a cache that is correct, necessary, and unboundedly large. This post is about the one algebra step that makes it finite — and it really is one step. Not a new architecture, not an approximation scheme. You move a pair of parentheses.

One step

Delete the softmax. Just for a moment — we’ll come back to what that costs. The output of a query is then three matrices multiplied together:

\[o \;=\; q\,K^{\top}V, \qquad q\in\mathbb{R}^{1\times d},\ \ K,V\in\mathbb{R}^{N\times d}\]

Matrix multiplication is associative, so you can evaluate that left-to-right or right-to-left and get the same answer. The answers are identical. The machines are not.

Left-to-right, $qK^{\top}$ is a $1\times N$ row of scores — one per token. That object grows every time you speak, and it’s exactly what the KV cache exists to feed. Right-to-left, $K^{\top}V$ is $d\times d$. It does not depend on $q$ at all, it can be built once and reused, and its size has nothing to do with $N$.

The reason this works is worth stating plainly, because it’s the hinge the whole field turns on. Path A’s $i$-th term is $(q\cdot k_i)\,v_i$. That scalar $(q \cdot k_i)$ is linear in $q$, so $q$ factors out of the sum:

\[\sum_i (q\cdot k_i)\,v_i \;=\; q\Big(\underbrace{\textstyle\sum_i k_i^{\top}v_i}_{S,\ d\times d}\Big)\]

Everything inside the bracket is free of $q$. It can be precomputed, stored, and reused — and it’s one fixed-size matrix no matter how many terms went into the sum. That is the constant-size cache.

Why softmax can’t play

Softmax attention’s score isn’t $q \cdot k_i$, it’s $\exp(q\cdot k_i)$. The exponential welds $q$ and $k$ together: there’s no way to write $\exp(q\cdot k)$ as something-with-only-q times something-with-only-k in finite dimensions. So $q$ won’t come out of the sum, no term can be evaluated before the query arrives, and every $k_i, v_i$ has to be kept.

That’s the trade in one sentence. Softmax buys you a sharp, content-addressable lookup and pays for it with an O(N) cache. Dropping it buys you an O(1) cache and pays for it with a weaker lookup. How much weaker, and whether you can get some of it back, is the next post.

Writing

Split $S=\sum_i k_i^{\top}v_i$ into steps and the famous recurrence falls out:

\[S_t \;=\; S_{t-1} + k_t^{\top}v_t\]

Every token contributes one outer product — a full $d\times d$ matrix — and they all land on the same board. Here is the same history stored both ways, side by side.

Reading, and what leaks in

Write two pairs and query with the first key:

\[k_1 S \;=\; k_1\big(k_1^{\top}v_1 + k_2^{\top}v_2\big) \;=\; \underbrace{\|k_1\|^2\,v_1}_{\text{what you wanted}} \;+\; \underbrace{(k_1\cdot k_2)\,v_2}_{\text{what leaked in}}\]

Two things to take from this. First, normalise the keys and $|k_1|^2 = 1$, so the first term is exactly right — that’s the entire justification for the F.normalize(k) you’ll find in every implementation. Second, the leak is exactly the inner product of the two keys. Orthogonal keys, no leak.

And now the fact you can’t negotiate with: in $d$ dimensions there are at most $d$ mutually orthogonal directions. Once you’ve written more than $d$ tokens, some new key must have a nonzero inner product with something already stored. Interference stops being a matter of luck or tuning and becomes arithmetic. That’s the wall the last post in this series is entirely about.

The bill

Per head, softmax stores $2Nd$ numbers; linear stores $d^2$. They break even at $N = d/2$ — 64 tokens for a head dimension of 128. Past that the flat line stays flat forever.

	Softmax attention	Linear attention
cache size	$2Nd$, grows with $N$	$d^2$, constant
per-token decode cost	$\approx 4Nd$, grows	$\approx 4d^2$, constant
memory traffic per token	the whole KV cache	one $d\times d$ state
the history itself	lossless, every token addressable	lossy, tokens interfere past capacity
training	parallel by construction	needs a chunkwise rewrite to parallelise

Read the last two rows together and you have the reason nobody ships a pure linear stack. The left column and the right column are complements, not competitors — which is why current hybrids interleave them, a few recurrent layers for every full-attention layer, cheap constant-cost memory for the near past and periodic exact retrieval for everything else.

What we broke

Everything above rests on one assumption we made in the first paragraph and never paid for: that the score is $q\cdot k$ rather than $\exp(q\cdot k)$. That assumption is what let $q$ leave the sum. It is also a real loss of expressiveness — a plain dot product is a much blunter retriever than a sharpened exponential one.

So the honest question is: how much of softmax can you recover while keeping $q$ and $k$ separable? That’s a question about kernels, and it’s the next post.

---

Same three matrices. Different order. Different machine.

References

• Linear attention — Katharopoulos et al., Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention (arXiv:2006.16236)
• The fast-weight reading of the same recurrence — Schlag, Irie, Schmidhuber, Linear Transformers Are Secretly Fast Weight Programmers (arXiv:2102.11174)
• Making it fast in practice (chunkwise parallel form) — Yang et al., Gated Linear Attention Transformers with Hardware-Efficient Training (arXiv:2312.06635)
• A hybrid that ships — Moonshot AI, Kimi Linear (arXiv:2510.26692)