Linear Attention

Linear attention replaces the softmax with a kernel feature map, reordering the computation so cost grows linearly rather than quadratically with sequence length.

Reordering the matrix products

Standard attention computes softmax(Q K^T) V. The product Q K^T forms a matrix of size sequence-length squared, which is the source of quadratic cost. Linear attention removes the softmax and replaces it with a feature map phi applied to queries and keys, so attention becomes a normalized product of phi(Q), phi(K), and V. Without the softmax coupling the terms, the associative law lets the model compute phi(K)^T V first, a small matrix of size feature-dimension by value-dimension, and then multiply by phi(Q). This reordering makes the cost linear in sequence length.

The kernel feature map

The feature map phi must keep attention weights non-negative so the result stays a valid weighted average. A common choice is an elementwise function such as ELU plus one. The map approximates the exponential similarity that softmax provides; the closer the approximation, the nearer linear attention comes to the accuracy of full attention. Different feature maps trade fidelity against simplicity.

The recurrent form

For causal (autoregressive) generation, linear attention has a recurrent view: it maintains a running summary matrix S = sum of phi(k) outer v over past positions, updated one token at a time. Each new output is phi(q) times S, normalized. This gives constant memory and constant per-step cost during generation, unlike standard attention whose cost per step grows with the length of the history.

# causal linear attention, streaming update
phi_q, phi_k = feature_map(q), feature_map(k)
S = S + torch.outer(phi_k, v)        # running key-value summary
z = z + phi_k                        # running normalizer
out = (phi_q @ S) / (phi_q @ z + 1e-6)

Where it stands

Linear attention scales gracefully to very long sequences and gives streaming inference with fixed memory, which connects it conceptually to recurrent and state-space models such as Mamba. Its weakness is accuracy: the softmax's sharp, content-dependent focus is hard to reproduce with a fixed feature map, so linear attention can underperform full attention on tasks needing precise long-range recall. For exact attention at lower cost, see flash attention.