Chapter 04 · Fixed-size state

Linear attention: memory on a budget

The KV cache grows with every token. Linear attention stores information from earlier tokens in one fixed-size matrix instead. Each new token reads and updates a matrix of the same size, even at a million-token context. Because many associations share that limited space, they can interfere with one another. This chapter explains both the saving and the loss.

4.1How the calculation changes

Softmax attention computes softmax(QK^⊤)V. Softmax couples each query to all keyscontext Its denominator sums over every key for a query, so each weight depends on all scores in that row. You cannot simply rearrange softmax(QK⊤)V into Q(K⊤V).. The direct calculation forms all T×T scores before combining the values.

In their 2020 paper Transformers are RNNs, Katharopoulos, Vyas, Pappas, and Fleuret show how to avoid that growing calculation. They replace the softmax score with a feature map φcontext Applying φ separately to queries and keys lets the model compute a reusable sum over past keys and values. The tradeoff is weaker selectivity than softmax. Later variants use different feature maps and sometimes drop the positivity requirement. applied to queries and keys separately. The resulting score factors into a query part and a key part, so past key-value contributions can be added together before the query arrives. The paper uses φ(x) = elu(x) + 1, a fixed elementwise function chosen to keep scores positive:

The sum inside the parentheses does not depend on the query. The model can update that sum as tokens arrive and store it as its running state:

A normalizer z_t = z_t−1 + φ(k_t) divides the readout; many modern variants drop itcontextThe denominator is extra state to carry, and a division whose value can get small for some queries, awkward numerically and in kernels. Most modern descendants (the DeltaNet family included) skip it and stabilize the readout with an ordinary normalization layer instead: one more case of replacing bespoke math with a standard, kernel-friendly part. for a normalization layer instead. Shapes, for the record: S_t is d×d, z_t is a d-vector, and the denominator φ(q)^⊤z is one number.

φ(k)v^⊤ is an outer product, a d×d updatecontextA rank-1 matrix: every row is v scaled by one coordinate of k. It has d² cells but only one "direction" of content, one reason capacity for clean recall scales on the order of d stamps (the exact number depends on key geometry and tolerated noise). Each write changes the shared matrix. that associates a key direction with a value.

Two writes and a read, with actual numbers

Take d = 2 so every cell is visible (φ taken as the identity and the normalizer skipped, purely to keep the arithmetic bare). Write two associations with perpendicular keys:

write  k₁=(1,0) → v₁=(3,1)      stamp k₁v₁⊤ = | 3  1 |     running S = | 3  1 |
                                              | 0  0 |                 | 0  0 |

write  k₂=(0,1) → v₂=(-2,4)     stamp k₂v₂⊤ = | 0  0 |     running S = | 3  1 |
                                              |-2  4 |                 |-2  4 |

read   k₁⊤S = (3, 1)   ✓ exactly v₁          read   k₂⊤S = (-2, 4)   ✓ exactly v₂

Because the first two keys are perpendicular, each read returns its own value exactly. In two dimensions there are only two perpendicular directions. A third key must overlap the others (only two perpendicular directions exist in 2D):

write  k₃=(0.8, 0.6) → v₃=(0,-5)    stamp k₃v₃⊤ = | 0  -4 |    S becomes | 3  -3 |
                                                  | 0  -3 |              |-2   1 |

read   k₁⊤S = (3, -3)      ✗ was (3, 1), k₃ overlapped k₁, so v₃'s stamp inked k₁'s row
read   k₃⊤S = (1.2, -1.8)  ✗ was (0, -5), and k₃'s own read picks up v₁ and v₂ bleed

No earlier value was explicitly deleted, but the third write changed what the first key retrieves. The equations and demo below show how this interference grows.

S is the sum of every stamp so far. Attention has become an RNN with a matrix-valued hidden statecontext Traditional RNNs and LSTMs carry a hidden vector with d numbers. This state is a d×d matrix, or 4,096 numbers when d=64. It updates through an outer product and supports matrix reads..

An accountant with a running ledger

Imagine an accountant answering questions about a client's finances. With softmax attention, she keeps every receipt. Each time the client asks a question, she goes back through the receipts, decides how relevant each one is to that question, and combines them. She can examine any receipt, but the pile grows and every question requires another pass through it. That is like the growing cache in chapter 03.

With linear attention, she updates a fixed-size ledger whenever a receipt arrives. She answers new questions from the ledger instead of rereading the receipts. This works because the score separates into a query part and a key part: φ(q)·φ(k). The key-value contributions can be added to the ledger before the query is known, and the query is applied to the stored sum afterward. Softmax does not allow the same rearrangement: each receipt's weight depends on the current query and on the other scores through normalization.

The ledger saves storage and repeated reads, but it does not keep an individual slot for every receipt. The rest of this chapter shows what happens when many associations share that limited space.

4.2What fixed-size state saves

• Constant decode state. The ch. 03 calculator's runaway bar becomes a flat linecontextThe serving economics hiding in that flat line: per-conversation memory no longer grows, so a GPU can hold as many million-token sessions as thousand-token ones. This, not FLOP counts, is the raw material of headline numbers like "6× decoding throughput at 1M context" (ch. 06).: one d×d matrix per head, whatever the context length.
• Constant per-token work. Each step is a fixed-size write and read, with no growing scan over the past.
• Linear total time. Generating T tokens costs O(T), not O(T²).

4.3Where retrieval breaks down

Write associations k_i → v_i into S = Σ_i k_iv_i^⊤, then read back with key k_j:

Assuming unit-norm keyscontextNormalizing keys makes the self-term coefficient exactly 1 and bounds each cross-term by a cosine similarity. In the delta-rule family (ch. 05), it also keeps the erase step from overshooting., so k_j^⊤k_j = 1.

If all keys were perpendicular, the cross terms would vanish and each value could be retrieved exactly. There are only so many perpendicular directions. Songlin Yang states the limit this way:

Store more than ~d associations on a d-dimensional whiteboard and their representations overlapcontextThis crowding has a name inside ordinary dense networks too: superposition. Anthropic's "Toy Models of Superposition" (Elhage et al., 2022) showed plain MLPs storing more features than they have dimensions by accepting exactly this kind of interference. The whiteboard problem is what finite vector spaces do when asked to hold too much, not a linear-attention quirk.. This is interference, the overcapacity problem. The demo below lets you test it:

Spotlight and floodlight

Softmax attention can act like a spotlight. Its exponential weights can concentrate almost all attention on one earlier token, as the sharpness slider in chapter 02 shows. Additive linear attention is closer to a floodlight: its simpler scores tend to mix information from several earlier tokens in the same fixed-size state. A more expressive feature map can make the readout more selective, but it cannot give every token its own stored slot.

A broad readout may be enough to summarize the tone of a paragraph. Copying the exact token that followed a distant phrase, as in chapter 02's induction-head example, needs a more focused lookup. If several stored associations contribute to the answer, the target can be mixed with its neighbors. Chapters 05 and 06 improve how the fixed state is written and cleared. Chapter 07 also keeps some exact-attention layers, where individual earlier tokens remain addressable.

Contents · Glossary · Derivations follow Katharopoulos et al. and the source article; quotes credited inline.