The quadratic cost of attention has attracted more attempts at circumvention than any other single fact in this field, and most of them have failed. The idea is a piece of algebra rather than an approximation heuristic: attention involves multiplying three matrices, matrix multiplication is associative, and doing the multiplications in the other order turns a quadratic cost into a linear one. That much is exactly true and costs nothing. What costs something is the softmax sitting in the middle, which blocks the reassociation and must be removed or replaced — and the entire history of this line of work is the history of discovering what the softmax was doing that nobody had noticed. This piece is about the family that has come closest, about what the softmax turned out to be doing, and about why “closest” has been such a moving target.
The reassociation
Set aside the softmax for a moment and write attention as three matrices multiplied together. Queries $Q$ and keys $K$ are $n \times d$, where $n$ is the sequence length and $d$ the head width, and values $V$ is $n \times d$. The computation is $(QK^\top)V$.
Do it in that order and the intermediate object $QK^\top$ is $n \times n$ — the score matrix, quadratic in sequence length, the source of all the trouble. The cost is $O(n^2 d)$.
But matrix multiplication is associative, so $(QK^\top)V = Q(K^\top V)$. Do it the second way and the intermediate object $K^\top V$ is $d \times d$ — a square matrix the size of the head width, with no dependence on sequence length at all. The cost is $O(n d^2)$.
For $n$ far larger than $d$, which is the case that matters, this is an enormous saving, and it is not an approximation. It is the same number computed in a different order.
The obstacle is that real attention is not $(QK^\top)V$. It is $\text{softmax}(QK^\top)V$, and the softmax applies a nonlinearity — exponentiate, then normalize across each row — to the intermediate matrix. You cannot reassociate around a function applied to the thing in the middle. To get the saving, the softmax must go.
Figure 1. Two orders of multiplication, two intermediate objects.
Replacing the softmax with a feature map
The standard move is to replace the exponentiated dot product with an inner product of transformed vectors. Where softmax attention weights position $j$ by $e^{q_i \cdot k_j}$, linear attention weights it by $\phi(q_i) \cdot \phi(k_j)$ for some function $\phi$ applied to each vector separately.
Because $\phi$ acts on the queries and keys individually rather than on their product, the reassociation is restored. Written out with the normalization included:
$$y_i = \frac{\phi(q_i)^\top \sum_{j \le i} \phi(k_j) v_j^\top}{\phi(q_i)^\top \sum_{j \le i} \phi(k_j)}$$The sums run over all previous positions and do not depend on $i$ except through the range, which means they can be maintained incrementally. Keep a running matrix $S = \sum \phi(k_j) v_j^\top$ of size $d \times d$ and a running vector $z = \sum \phi(k_j)$, update both with each new token, and read off the output by multiplying. Generation costs a constant amount per token, and there is no KV cache that grows.
Which reveals what this family really is. That running matrix is a fixed-size state, updated additively as tokens arrive. Linear attention is a recurrent model wearing attention’s notation — the same object the article on state space models describes, reached from the opposite direction. One line of work started from recurrence and made it parallelizable; the other started from attention and made it recurrent; they met.
The choice of $\phi$ has varied. A simple positive function such as an exponential-linear unit plus one, which guarantees the denominator stays positive. A random feature map chosen so the inner product approximates the exponential in expectation, which makes the method an unbiased estimator of true attention. A polynomial expansion. None has proved decisive, which is itself informative.
Figure 2. The running state that makes it a recurrent model.
What the softmax was doing
The early versions of this were substantially worse than attention, and the diagnosis took a while. Three things turned out to have been lost.
Sharpness. The exponential in a softmax is what lets attention concentrate almost all its weight on one position. An inner product of non-negative features produces a much flatter distribution — every position with any feature overlap gets some weight, and the winner cannot pull far ahead. Attention’s ability to retrieve one specific thing depends on that sharpness, and linear attention blurs it.
Capacity. The state is a $d \times d$ matrix, and every token writes into it additively, forever, with nothing removed. After a few thousand tokens the accumulated sum is a superposition of thousands of outer products in a space that cannot keep them separable. This is the superposition argument applied unfavourably: the state has a finite capacity and the writes never stop, so old content is progressively overwritten by interference rather than by any decision.
Selectivity. Nothing in the update can decide that a token is not worth remembering, or that an old memory should be released. Every token contributes equally and permanently.
The fixes that followed address these in order, and they are what made the family competitive. Adding a decay factor, so that the state is multiplied by something less than one at each step, gives forgetting — which frees capacity and matters more than its simplicity suggests. Making that decay depend on the input gives selectivity, the same ingredient that made state space models work. And treating the state as something to be written rather than accumulated — where each token performs a small corrective update that removes what was previously stored for a similar key before adding the new association — gives something closer to an actual memory with overwriting, which is the most recent and most promising direction.
Each of these makes the model less like a reassociated attention and more like a learned recurrent memory. The algebra was the entry point, not the destination.
Figure 3. What the softmax was doing, and what replaced it.
Why the field kept not adopting it
For several years these methods were reported as matching attention while being far cheaper, and were not adopted. Three reasons, all instructive.
The first is that they were being compared against a badly implemented baseline. FlashAttention made exact attention several times faster and linear in memory, which moved the crossover point where a linear method becomes worthwhile out to sequence lengths beyond what most people use. An approximation must beat the best implementation of the thing it approximates, and for a while it was not being asked to.
The second is that the losses were real but concentrated. Average language modelling loss looked fine; retrieval, copying, and in-context learning from many examples did not. A headline metric can be matched while a specific and important capability is not, which is the evaluation problem in miniature.
The third is that a $d \times d$ state per head sounds small and is not free — it must be held in fast memory during the scan, and naive implementations spent so much time moving it that the theoretical advantage evaporated. The gains only materialized once someone wrote the kernels with the same hardware-awareness that FlashAttention brought to exact attention.
Where it has landed is the same place the state space work landed, which is unsurprising given that the two turned out to be the same thing. Pure linear attention is not used for general-purpose models. Hybrid stacks — mostly linear or recurrent layers with a minority of exact attention layers — are used, increasingly in production, because they give constant-cost processing for most of the model while keeping a few places where the model can look something up exactly. The quadratic term was never the enemy; paying it at every one of eighty layers was.
What to carry forward
Linear attention begins from an exact observation: attention multiplies three matrices, matrix multiplication is associative, and computing $Q(K^\top V)$ instead of $(QK^\top)V$ replaces an $n \times n$ intermediate with a $d \times d$ one, turning quadratic cost into linear. The obstacle is the softmax applied to the middle term, which blocks the reassociation, so it is replaced by an inner product of separately-transformed queries and keys. The consequence is that the model maintains a fixed-size running state updated additively per token — which means linear attention is a recurrent model in attention’s notation, the same object state space models arrive at from the other direction. Removing the softmax loses three things: sharpness, since the exponential is what lets attention concentrate nearly all weight on a single position, and an inner product of non-negative features cannot; capacity, since a fixed state written to additively and never cleared accumulates interference until old content is unrecoverable; and selectivity, since no token can be judged not worth keeping. The repairs — a decay factor giving forgetting, input-dependent decay giving selectivity, and update rules that overwrite an existing association rather than accumulate on top of it — each move the method further from reassociated attention and closer to a learned memory. Adoption lagged because the comparison was against an unoptimized baseline until FlashAttention moved the crossover point, because the losses were concentrated in retrieval rather than visible in average loss, and because the state has to stay in fast memory to deliver its advantage. The outcome matches the state space story: not replacement, but hybrid stacks where most layers are constant-cost and a minority retain exact lookup.
The figures in this article follow the shared figure key , which explains what every shape, line style and colour means.
