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:
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:
A query's output is a normalized weighted average. Reassociate the numerator and denominator independently:
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:
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 / methods | Main intermediate | Attention work, excluding Q/K/V projections | What changes |
|---|---|---|---|
| Kernel: Linear Transformer, Performer, cosFormer | S: r × d_v, z: r | O(n·r·d_v), plus feature construction | Similarity kernel or its estimate |
| Low-rank sequence projection: Linformer | K′: k × d, V′: k × d_v, probabilities: n × k | O(n·k·(d + d_v)), including sequence projections | Sequence compressed to rank k |
| Sparse: Longformer, BigBird | Up to s permitted keys per ordinary query; fixed global-token count | O(n·s·(d + d_v)) with a kernel that exploits the pattern | Permitted query–key pairs |
| Exact tiling: FlashAttention | Score tiles and online softmax statistics | O(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
- Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, Katharopoulos et al., 2020 (Linear Transformer)
- Rethinking Attention with Performers, Choromanski et al., 2020 (FAVOR+)
- Linformer: Self-Attention with Linear Complexity, Wang et al., 2020
- cosFormer: Rethinking Softmax in Attention, Qin et al., 2022
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, Dao et al., 2022
- Longformer: The Long-Document Transformer, Beltagy et al., 2020
- Big Bird: Transformers for Longer Sequences, Zaheer et al., 2020
Related concepts
Compare head sharing with explicit projection dimensions and KV-cache bytes. Separate exact memory ratios from measured quality and latency, and see why FlashAttention is an independent choice.
Trace how grouped-query attention keeps independent query heads while sharing fewer key/value heads, projections, and compact KV-cache rows during LLM decoding.
Trace how multi-query attention keeps independent query heads while sharing one key/value head, with exact cache bytes and a shape-correct decoding example.
Explore causal and symmetric local attention with exact window counts, then distinguish direct keys, multi-layer input reach, and inference KV storage.
Compose sparse attention patterns, follow one query through masking and softmax, and separate fewer allowed pairs from actual sparse-kernel savings.
Follow a query-key distance through ALiBi head slopes, attention logits and normalized weights, then understand the evidence and limits of length extrapolation.
