II · THE IDEA · ARTIFICIAL INTELLIGENCE
Sparse Transformer with Local Attention
▶ Listen · narrated
A model that attends to every token pair hits a wall long before a novel or a high-resolution image fits. Sparse patterns keep useful connections and drop the rest.
At a glance
- Problem
- Dense self-attention is quadratic in sequence length
- Approach
- Replace the full matrix with factorised sparse patterns
- Patterns
- Local windows plus strided or fixed sparse factors
- Complexity
- O(n√n) for the Sparse Transformer factorisations
- Related
- Linformer reaches linear cost via low-rank projections
Think of a crowded room where everyone tries to listen to everyone else at once. The noise and the effort both explode as more people arrive. Dense attention is that room: every token looks at every other token, and the bill grows with the square of the crowd.
A Sparse Transformer changes the seating plan. Each person is allowed to listen only to their immediate neighbours, plus a few people sitting at regular intervals down the row. Because the allowed conversations are limited and regular, the work grows much more slowly, and rooms of tens of thousands of seats become thinkable. Stack several such layers and a whisper can still cross the whole room — it just takes a few hops.
Linformer uses a different trick. Instead of thinning the conversations, it first summarises the whole crowd into a small panel of representatives, then lets everyone listen only to that panel. The cost stays linear in the size of the crowd. Both ideas keep the useful mixing and discard the all-to-all tax.
Dense scaled dot-product attention computes QK^T for Q, K in R^{n×d}, materialising an n×n matrix before the softmax and the multiply by V. Time and memory are Θ(n²).
Sparse Transformers (Child et al., 2019) replace that matrix with a factorised sparsity pattern. Two canonical patterns appear in the paper: strided and fixed. In the strided form, a head at position i attends to a local neighbourhood and to positions congruent to i modulo a stride s ≈ √n, yielding roughly O(√n) keys per query and O(n√n) overall cost for the two-dimensional factorisation. Fixed patterns assign static subsets of keys to each head. Residual connections and stacked layers ensure that the union of paths still yields a broad receptive field. The sparsity pattern is an architectural constant, not a learned mask.
Linformer (Wang et al., 2020) keeps the full set of queries but inserts learned projections E, F that map the n-length key and value sequences to length k ≪ n. Attention becomes softmax(Q (E K)^T) (F V), which is n×k and therefore linear in n for fixed k. The justification is an empirical and theoretical claim that the attention matrix is low-rank.
Limitations follow directly. Sparse patterns must match data geometry; a stride tuned for images is not automatically correct for text. Linformer’s rank k is a hyperparameter that trades fidelity for speed, and the projection is shared across positions. Neither method preserves the exact dense attention output; both are structured approximations whose quality is task-dependent.
Look closer
The full matrix is never materialised
In dense attention every query position compares itself with every key. Sparse Transformers never build that n-by-n grid. Each position is allowed only a small, predetermined set of connections — nearby tokens in a local window, plus a thinner set of longer-range links laid down by a stride or a fixed pattern. The saved work is not a side effect; it is the design.
Two factorisations, different geometries
The 2019 Sparse Transformer paper describes strided and fixed patterns. Strided attention steps across the sequence at regular intervals, so information can still travel far in a few layers. Fixed patterns assign each head a static subset of positions. Both keep the number of attended keys per query far below n, which is what drops the asymptotic cost.
Linformer takes a different cut
Where Sparse Transformers thin the attention graph, Linformer keeps every query but projects the key and value sequences down from length n to a much smaller constant dimension. The resulting attention is low-rank by construction and costs linear time and memory in n. The two lines of work attack the same quadratic bottleneck from opposite ends.
The story
Self-attention lets every position in a sequence gather information from every other position. That global view is powerful, and expensive. Memory and compute both scale with the square of the sequence length, so a context of a few thousand tokens already strains ordinary hardware, and tens of thousands become impractical.
The Sparse Transformer work of 2019 starts from a simple observation: most of those pairwise comparisons are not equally useful. A token usually needs its immediate neighbours, plus a sparser sampling of the distant past or of other regions of an image. If the allowed connections can be written as a product of sparse patterns — local windows combined with strided or fixed long-range links — the attention matrix never has to be dense. Each query attends to only a handful of keys, and the cost falls from quadratic to roughly O(n√n) for the factorisations they study.
The patterns are not learned connectivity masks in the usual sense; they are architectural choices about which offsets are legal. Local attention covers a contiguous neighbourhood. Strided attention jumps by a fixed step so that, across several layers, information can still propagate across the whole sequence. Fixed patterns hand different heads different static subsets of positions. Stacked together, the network recovers a usable global receptive field without paying for a full all-to-all matrix at every layer.
The same motivation appears, with different machinery, in Linformer the following year. Instead of deleting edges, Linformer assumes that the attention matrix is low-rank and projects the key and value sequences from length n down to a small projected length. Every query still produces a distribution over that reduced set, so the dominant terms become linear in n. Sparse patterns and low-rank projections are therefore complementary answers to one question: which structure can we impose on attention so that long contexts remain feasible?
Neither approach is free. Sparse patterns must be chosen to match the data geometry — what works for a rasterised image is not automatically right for raw audio or for prose. Low-rank projections introduce their own approximation error and a hyperparameter for the projected dimension. The papers treat these as engineering trade-offs rather than universal solutions. The lasting contribution is the demonstration that the quadratic barrier is not fundamental to the Transformer block; it is a consequence of insisting on dense global attention at every layer.
Why it mattered then
By 2019 the Transformer had become the default architecture for sequence modelling, yet practical context lengths were still modest because memory scaled with n squared. Tasks that genuinely need long range — high-resolution images generated pixel by pixel, long audio waveforms, documents that do not fit in a few thousand tokens — were awkward or impossible. Sparse Transformers showed that carefully chosen factorised patterns could push sequence length into the tens of thousands without a proportional explosion in memory. Linformer’s linear-complexity variant, published the next year, reinforced the point that the quadratic term could be removed entirely under a low-rank assumption. Together they shifted the research question from “how do we afford dense attention?” to “which structure should attention have?”
Why it matters now
Context windows continue to grow, and the cost of dense attention remains the binding constraint on many open-weight deployments. Modern long-context models still rely on the same family of ideas: sliding windows, strided or dilated patterns, and various low-rank or kernel approximations. Reading the 2019 and 2020 papers makes those later designs legible. They also clarify what is being traded away — full all-to-all mixing at every layer — so that when a model fails to bind distant facts, one can ask whether the sparse pattern or the rank bottleneck is part of the cause. The techniques remain directly useful for anyone training or fine-tuning on long documents, images, or audio with limited hardware.
The surprising detail
The Sparse Transformer does not learn which connections to keep in the way a pruning method might. The sparsity pattern is an architectural prior, fixed before training. Expressivity is recovered by stacking layers and by giving different heads different patterns, so that a path between distant positions still exists even though no single layer connects them directly. The network learns how to use the allowed wires, not which wires should exist.
What is disputed
Reported sequence lengths and exact complexity expressions depend on the chosen factorisation and on implementation details. The original Sparse Transformer work emphasises O(n√n) for its two-dimensional factorisations; Linformer claims linear complexity under a fixed projection rank. Neither paper settles which pattern is best for every modality, and later systems often hybridise several ideas.
Remember this
Sparse and low-rank attention keep long contexts feasible by refusing to build the full n-by-n matrix — the quadratic cost was a design choice, not a necessity.
Test yourself
A Sparse Transformer layer gives each query a local window and a strided set of longer-range keys. Why can information still travel from the first token to the last across a deep stack, even though no single layer connects them directly?
Because the strided pattern creates overlapping hops. A token reaches positions one stride away in one layer; those positions reach a further stride in the next layer; after enough layers the receptive field covers the whole sequence. Depth turns a sparse graph into a connected one, which is why the architectural prior can remain sparse without isolating distant tokens permanently.
Go deeper
- [1904.10509] Generating Long Sequences with Sparse Transformers · arxiv.org
- [2006.04768] Linformer: Self-Attention with Linear Complexity · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.