Skip to content
AI360XpertBeta

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.

Standard attention fills a 4096 by 4096 score grid costing 1.07 billion mults while linear attention folds pairs into one 64 by 64 state for 16.8 million
Standard attention fills a 4096 by 4096 score grid costing 1.07 billion mults while linear attention folds pairs into one 64 by 64 state for 16.8 million

Why Does This Exist?

Standard self-attention forces every query to score against every key, filling an N×NN \times N grid. At N=4096N = 4096 tokens and head size d=64d = 64, that grid costs N2d=1,073,741,824N^2 d = 1,073,741,824 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 d×dd \times d state as they stream past, and each query reads that state. The bill becomes Nd2=16,777,216N d^2 = 16,777,216, 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 N2N^2 scores, the report card is the kernel feature map, and the tally is the running d×dd \times d 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 QQ, keys KK, and values VV, each with NN rows of size dd. Standard attention outputs softmax(QK⊤/d)V\mathrm{softmax}(QK^\top / \sqrt{d})V, and the QK⊤QK^\top step is the N×NN \times N grid.

The kernel swap

Linear attention replaces the exponential similarity exp⁡(q⊤k/d)\exp(q^\top k / \sqrt{d}) with a kernel product ϕ(q)⊤ϕ(k)\phi(q)^\top \phi(k), where ϕ\phi is a feature map such as elu(x)+1\mathrm{elu}(x) + 1 that keeps every entry non-negative. The output for query ii becomes:

out(qi)=ϕ(qi)⊤∑jϕ(kj)vj⊤ϕ(qi)⊤∑jϕ(kj)\mathrm{out}(q_i) = \frac{\phi(q_i)^\top \sum_j \phi(k_j) v_j^\top}{\phi(q_i)^\top \sum_j \phi(k_j)}

The two sums are the whole trick. S=∑jϕ(kj)vj⊤S = \sum_j \phi(k_j) v_j^\top is a d×dd \times d matrix and z=∑jϕ(kj)z = \sum_j \phi(k_j) is a dd-vector, and both accumulate one pair at a time. No sum ever holds NN terms side by side, so memory stays flat in sequence length.

The 2 by 2 state, worked

Take two pairs with mapped keys [1.0,0.5][1.0, 0.5] and [0.5,1.0][0.5, 1.0] and values [1.0,0.0][1.0, 0.0] and [0.0,1.0][0.0, 1.0]. Adding each outer product ϕ(k)v⊤\phi(k) v^\top gives the state:

S=[1.00.50.51.0]S = \begin{bmatrix} 1.0 & 0.5 \\ 0.5 & 1.0 \end{bmatrix}

A query q=[1.0,0.5]q = [1.0, 0.5] reads it as S⊤q=[1.25,1.0]S^\top q = [1.25, 1.0] on top and q⊤z=2.25q^\top z = 2.25 below, with z=[1.5,1.5]z = [1.5, 1.5], giving [0.5556,0.4444][0.5556, 0.4444]. 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.4444

The 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 d×dd \times d state instead of an N×NN \times N 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.