Attention Variants: Sparse, Linear, and Sliding Window
Full attention compares every token to every other, and the cost grows with the square of length. The variants that break that quadratic, and what each gives up.
On this page
Standard self-attention has one uncomfortable property: every token attends to every other token, so doubling the sequence length quadruples the work. That quadratic cost is the wall long-context models hit. The attention variants are the ways around it, and they share a single strategy — compute less than all-pairs attention while losing as little as possible. What each one gives up is the whole story.
Where the quadratic comes from
Full attention builds an N×N matrix: for N tokens, every token scores its relevance to every other. That matrix is the source of both attention’s power and its cost. It captures any dependency regardless of distance — the reason attention beat recurrent approaches — but it means N² comparisons and N² memory.
Every variant below attacks that matrix. The question is always the same: which of those N² scores can you skip without breaking the model?
Sparse attention: skip most pairs
The observation behind sparse attention: most of those all-pairs scores are near zero anyway. A token rarely depends strongly on most other tokens. So predefine a pattern of which pairs to compute and ignore the rest.
Common patterns combine a few simple structures:
- Local windows — each token attends to its near neighbors, capturing the fact that nearby context usually matters most.
- Strided or dilated — attend to every k-th token, reaching far with few connections.
- Global tokens — a handful of designated tokens that attend to everything and are attended by everything, acting as information hubs so distant tokens can still communicate through them.
The cost drops because the pattern is fixed and sparse rather than dense. The gamble is that the pattern covers the dependencies that actually matter. When a real long-range dependency falls outside the pattern, the model simply cannot see it — the failure mode of any fixed sparsity.
Sliding window: only local, but stacked
Sliding-window attention is sparse attention taken to its simplest form: each token attends only to a fixed number of recent tokens, a window that slides along the sequence. Cost becomes linear in length — each token does constant work regardless of how long the sequence is.
The obvious objection is that a token cannot see beyond its window. The answer is depth. Stack many layers and the effective receptive field grows: a token sees its window directly, but each of those neighbors saw their windows in the layer below, so information propagates outward layer by layer — the same way stacked small convolutions cover a large area. Information travels far, just indirectly and more slowly.
The trade is directness. A dependency two windows away is reachable but weaker and later than one full attention would capture in a single step. For text where most dependencies are local, the trade is often excellent.
Linear attention: change the math
Sparse and sliding-window attention keep the same operation and compute fewer entries. Linear attention does something more fundamental: it rewrites the computation so the N² matrix is never formed at all.
Standard attention applies a softmax over the raw scores, and the softmax is exactly what forces you to compute all pairs before normalizing. Linear attention replaces that softmax with a different similarity function that can be reassociated — reordering the operations so cost grows linearly with length instead of quadratically. The N×N matrix disappears from the arithmetic entirely.
The catch is that softmax was not doing nothing. Its sharp, selective weighting — the ability to focus hard on a few tokens — is part of why attention is expressive. Approximating it with a linearizable function generally costs some of that sharpness, and linear-attention models have historically traded a little quality for their speed. The engineering question is whether the approximation is close enough for the task.
Reading the trade-offs
The variants line up on a single axis: how much of full attention’s expressiveness you sacrifice for how much speed.
- Full attention — maximum expressiveness, quadratic cost. Still the default when sequences are short enough to afford it.
- Sparse / sliding window — same operation, fewer pairs. Excellent when dependencies are mostly local or fit a known pattern; blind to dependencies outside the pattern.
- Linear — cheapest asymptotically, but approximates the softmax and can lose selectivity.
There is no free lunch, and this is the point worth internalizing: the quadratic cost buys the ability to model any dependency at any distance in one step. Every variant that beats the cost gives up some slice of that ability. The right choice is not the cheapest — it is the cheapest one whose sacrifice does not matter for your data.
A related, orthogonal line of work drops attention altogether for state-space models, which reach linear cost by a different route entirely.
What to remember
- Full attention’s cost is quadratic because it scores every pair of tokens; every variant reduces which pairs get computed.
- Sparse attention uses a fixed pattern (local windows, strided, global tokens) and is blind to dependencies outside it.
- Sliding-window attention is local only, but stacked layers grow the effective range indirectly.
- Linear attention rewrites the math to avoid the N×N matrix entirely, at the cost of the softmax’s selective sharpness.
- The trade is universal: cheaper attention sacrifices some ability to model arbitrary long-range dependencies — pick the cheapest sacrifice your task can absorb.