Linear Attention
By replacing the softmax with a kernel function, attention can be rewritten so keys and values fold into a fixed-size running state, making cost linear in sequence length.
Why Does This Exist?
Standard self-attention forces every query to score against every key, filling an grid. At tokens and head size , that grid costs multiplications, over a billion, and the grid itself must be stored. Longer contexts square the bill, which is why plain attention hits a wall on books and genomes.
Cheaper exact variants only soften the blow. FlashAttention tiles the same grid through fast memory without changing the operation count. Sparse patterns skip cells but keep quadratic growth. Linear attention takes the third path: change the operation so the grid never exists. Keys and values fold into one fixed state as they stream past, and each query reads that state. The bill becomes , about 16.8 million, a 64-fold saving that grows with every added token. The price is softer focus, explained below.
Think of It Like This
A running tally instead of every pairwise vote
Ranking 1000 students by comparing every pair takes nearly 500,000 comparisons. Or score each student once on a fixed report card, keep one running tally of report cards weighted by their results, and answer each new query by matching it against the tally. The tally never grows with the headcount.
Pairwise votes are the scores, the report card is the kernel feature map, and the tally is the running state. Where it stops: a tally cannot replay any single matchup on demand. Softmax attention can point at the one decisive token, while the tally only remembers the blend, which is why sharp retrieval is the first casualty.
How It Actually Works
Call the queries , keys , and values , each with rows of size . Standard attention outputs , and the step is the grid.
The kernel swap
Linear attention replaces the exponential similarity with a kernel product , where is a feature map such as that keeps every entry non-negative. The output for query becomes:
The two sums are the whole trick. is a matrix and is a -vector, and both accumulate one pair at a time. No sum ever holds terms side by side, so memory stays flat in sequence length.
The 2 by 2 state, worked
Take two pairs with mapped keys and and values and . Adding each outer product gives the state:
A query reads it as on top and below, with , giving . Two pairs in, one fixed state, one query out, and the state never widens no matter how many pairs came before.
The quality gap
Softmax is peaky: it concentrates weight on a few top keys, which is exactly what needle-in-a-haystack retrieval needs. Kernel maps spread weight more evenly, so the sharp focus dulls and long-document lookup suffers first. State space models and Mamba chase the same recurrent efficiency from a different direction, adding selectivity to recover what the plain kernel loses.
Code
The cost gap and the 2 by 2 running state from the worked example, in plain standard-library Python.
N, d = 4096, 64print(f"{N * N * d} vs {N * d * d}")# -> 1073741824 vs 16777216
Kf = [[1.0, 0.5], [0.5, 1.0]]V = [[1.0, 0.0], [0.0, 1.0]]S = [[Kf[0][i] * V[0][j] + Kf[1][i] * V[1][j] for j in range(2)] for i in range(2)]q = [1.0, 0.5]num = [S[0][0] * q[0] + S[1][0] * q[1], S[0][1] * q[0] + S[1][1] * q[1]]den = q[0] * 1.5 + q[1] * 1.5print(f"{num[0] / den:.4f} {num[1] / den:.4f}")# -> 0.5556 0.4444The counts 1073741824 against 16777216 confirm the 64-fold gap, and 0.5556 with 0.4444 matches the hand-read state exactly.
Watch Out For
Expecting softmax quality at linear cost
Linear attention is a different algorithm with a blurrier focus profile, not a faster implementation of the same one.
Symptom: retrieval benchmarks drop while language modeling looks fine, and the gap widens with context length. Fix: reserve kernel attention for throughput-bound workloads, and keep exact attention where pointing at one decisive token decides the answer.
Trusting parallel training and recurrent inference to agree
Causal linear attention trains in parallel form and serves as a recurrence, mathematically equal but numerically different paths.
Symptom: served outputs drift from training-time reconstructions on long generations. Fix: compare both code paths token by token on a short example before trusting production output, and pin down which path is canonical when they differ.
The Quick Version
- Linear attention swaps the softmax similarity for a kernel product, so keys and values fold into one fixed state instead of an grid.
- At 4096 tokens with head size 64, exact attention costs 1,073,741,824 multiplications against 16,777,216 for the linear form, a 64-fold saving.
- The 2 by 2 worked state reads query 1.0, 0.5 as outputs 0.5556 and 0.4444 through a denominator of 2.25.
- The recurrent form serves each new token in constant time, which is why long-generation workloads want it.
- Kernel maps spread focus more evenly than softmax, so sharp retrieval over long contexts pays the visible price.