Skip to main content

Linear Attention Approximations

Understand normalized kernel attention, low-rank sequence projections and their trade-offs, and compare them with sparse attention and exact tiled softmax.

The O(n²) bottleneck

Dense self-attention compares every query with every key. For one head, let Q and K have shape n × d and V have shape n × d_v:

O = \operatorname{softmax}\!\left(\frac{QK^\top}{\sqrt{d}}\right)V

There are n² query–key pairs, so computing all scores and weighted values costs O(n²(d + d_v)). A straightforward implementation also stores an n × n score or probability matrix. Softmax does not require that full matrix to be stored. FlashAttention evaluates the same dense attention in tiles with online softmax, retaining exact attention while avoiding the quadratic intermediate. Its arithmetic still grows quadratically with n.

Linear attention changes the attention operator to reduce that arithmetic. Low-rank projections and sparse patterns take different routes to cheaper attention. We will derive the kernel route first, then separate the families.

The core trick: kernelize and reassociate

Choose a nonnegative similarity that factorizes into r-dimensional features:

\kappa(q_i,k_j) = \phi(q_i)^\top\phi(k_j),\qquad \phi(q_i),\phi(k_j)\in\mathbb{R}^{r}

A query's output is a normalized weighted average. Reassociate the numerator and denominator independently:

o_i = \frac{\sum_{j=1}^{n} \kappa(q_i,k_j)\,v_j}{\sum_{j=1}^{n}\kappa(q_i,k_j)} = \frac{\phi(q_i)^\top S}{\phi(q_i)^\top z},\qquad S=\sum_{j=1}^{n}\phi(k_j)v_j^\top,\quad z=\sum_{j=1}^{n}\phi(k_j)

Here S has shape r × d_v, and z has r entries. They summarize the keys and values once, and every query reuses them. The denominator \phi(q_i)^\top z makes the weights sum to one; multiplying by S alone does not.

The matrix form makes the changed multiplication order visible:

\bigl(\phi(Q)\phi(K)^\top\bigr)V = \phi(Q)\bigl(\phi(K)^\top V\bigr)

This identity is exact for the chosen kernel. The approximation or change of behavior comes from replacing the softmax kernel, not from associativity. Aggregating S and evaluating all queries costs O(n·r·d_v), plus the cost of constructing the features. For a dense random-feature projection, feature construction adds O(n·d·r).

The reusable state takes O(r·d_v + r) space. This is not the total memory for a full sequence: Q, K, V, features and outputs can still grow with n. Compute grows linearly in n only when feature width r and head widths stay fixed.

Interactive explorer

Change n, select a query and compare two feature maps. The denominator, normalized output and exact-softmax reference use the same deterministic toy Q, K and V. Both feature maps receive q/d¹ᐟ⁴ and k/d¹ᐟ⁴ so their input dot product matches q·k/√d.

The displayed error is \lVert o_i^{\text{kernel}}-o_i^{\text{softmax}}\rVert_2, the Euclidean distance between two output vectors for one query. It is not a model accuracy percentage. ELU + 1 defines a different kernel; the positive random features estimate the exponential softmax kernel. Increasing r trades a larger summary and more work for a better estimate in expectation, but a fixed sample need not improve monotonically on every query.

The families

Kernel methods choose the similarity. Sequence projections compress K and V before softmax. Sparse methods restrict which pairs are visible. Exact tiling changes how dense softmax is evaluated. These distinctions matter even when several methods have linear growth under fixed settings.

  • Linear Transformer uses \phi(x)=\operatorname{ELU}(x)+1. Its feature width equals the query/key width. For causal attention, prefix summaries S_i=\sum_{j\le i}\phi(k_j)v_j^\top and z_i=\sum_{j\le i}\phi(k_j) prevent access to future tokens. Updating and reading them takes O(r·d_v) work per new token at fixed widths, independent of prefix length.
  • Performer (FAVOR+) uses positive orthogonal random features to approximate the unnormalized exponential kernel. The estimate must still be normalized by the key-feature sum. An unbiased kernel estimate does not make its numerator/denominator ratio exactly unbiased. The explorer uses fixed-seed IID Gaussian features to teach the identity, rather than implementing the full FAVOR+ algorithm.
  • Linformer uses learned sequence projections E and F with shape k × n. It forms K′ = EK (k × d) and V′ = FV (k × d_v), then computes an n × k softmax matrix. Here k is a sequence projection rank, distinct from kernel feature width r. The projections depend on the supported sequence length; rank and length choices are part of the model design.
  • cosFormer combines nonnegative features with cosine-based distance reweighting, which can also be factorized. It changes the similarity and adds positional locality; it does not preserve exact dense softmax.
  • Longformer and BigBird use sparse connectivity. Longformer combines local windows with designated global tokens; BigBird adds random connections. Their global tokens participate in sparse softmax attention, rather than providing a kernelized global summary.
  • FlashAttention tiles exact dense softmax. It avoids storing the full attention grid without replacing the kernel, compressing the sequence or dropping pairs.
Family / methodsMain intermediateAttention work, excluding Q/K/V projectionsWhat changes
Kernel: Linear Transformer, Performer, cosFormerS: r × d_v, z: rO(n·r·d_v), plus feature constructionSimilarity kernel or its estimate
Low-rank sequence projection: LinformerK′: k × d, V′: k × d_v, probabilities: n × kO(n·k·(d + d_v)), including sequence projectionsSequence compressed to rank k
Sparse: Longformer, BigBirdUp to s permitted keys per ordinary query; fixed global-token countO(n·s·(d + d_v)) with a kernel that exploits the patternPermitted query–key pairs
Exact tiling: FlashAttentionScore tiles and online softmax statisticsO(n²·(d + d_v))Evaluation order and memory traffic

In the kernel row, the feature map determines the extra cost: ELU + 1 has r = d and O(n·d) feature construction, while dense positive random projections cost O(n·d·r). In the sparse row, s includes the local/random budget and access to global keys; global-query rows add O(n·g·(d + d_v)) for g global tokens. Linear growth therefore assumes fixed r, fixed k, or fixed sparse budgets including g. If those settings grow with n, the complexity grows with them.

What you give up

A smaller state, lower rank or restricted pattern can change how attention retrieves information. Quality depends on the feature map, rank or connectivity, training setup and task. There is no universal ordering in which one family retains a fixed percentage of accuracy or is always the weakest approximation. A toy output error also cannot predict the quality of a trained model that adapts to its attention operator.

Exact tiled attention preserves dense softmax mathematically, subject to normal floating-point differences. Sparse attention computes normalized softmax over its allowed keys exactly, but generally differs from full dense attention. Linformer and kernel methods make other changes to the operator. Hybrid architectures can combine local attention and a kernel summary, but Longformer and BigBird themselves belong to the sparse family.

Use the constraint to frame the comparison: tiling addresses the stored attention grid and memory traffic; kernel summaries, sequence projections and sparse execution can reduce attention arithmetic. Actual latency also depends on shapes, hardware and kernels, so asymptotic counts are not measured speedups. The sparse-attention and sliding-window pages explore the connectivity route in more detail.

Further reading

If you found this explanation helpful, consider sharing it with others.

Mastodon