Sparse Attention: Longformer and BigBird

Full self-attention forces every token to score itself against every other token, which is why its cost grows with the square of sequence length (see The Quadratic Cost of Attention). But does every token actually need to see every other token directly? Longformer and BigBird both answer no: most useful information is local — a word's meaning is shaped mostly by nearby words — and the few genuinely long-range dependencies can be handled by a small number of designated "hub" positions everyone can reach, rather than a full all-pairs matrix. Restricting attention to a fixed, sparse pattern instead of the complete graph turns cost from quadratic back to linear in sequence length.

The analogy: a highway system, not a fully connected map

Imagine wanting every town in a country reachable from every other by a direct road — a huge network, growing as the square of the number of towns. Real transportation systems don't do this. Each town has local roads to its near neighbours, and a small number of hub cities have highways connecting them to everywhere. You can still reach any town from any other, usually in one or two hops via a hub, but no direct road was built for every pair. Sparse attention patterns are exactly this: local roads (a sliding window) plus a few global hubs (special tokens attending to, and attended to by, everything).

The two patterns

Longformer combines a sliding-window pattern — each token attends only to $w$ neighbours on either side, cost $O(nw)$ instead of $O(n^2)$ — with a small set of global tokens (like the classification token, or task-specific markers) that attend to all $n$ positions and are attended to by all $n$ positions, giving the model a way to route long-range information through those hubs.

BigBird adds a third ingredient on top of window and global attention: a handful of random connections per token, so that even non-hub, non-neighbouring tokens have some low-probability direct paths, which the BigBird paper shows is enough to preserve the theoretical expressive power (it can still approximate any function a full-attention transformer can, under the same conditions) while every token still only attends to $O(1)$ other tokens on average, not $O(n)$.

$$\text{cost}(n) = O(n \cdot k), \qquad k = w + g + r \ll n$$

In words: total attention cost scales with sequence length $n$ times a small constant $k$ — the window size $w$ plus number of global tokens $g$ plus number of random links $r$ — and $k$ does not grow with $n$, so cost grows linearly instead of quadratically.

Worked example 1: counting connections at two sequence lengths

Take window $w=256$ (128 either side), $g=4$ global tokens, $r=8$ random links, so $k = 256+4+8=268$ connections per token, roughly constant regardless of $n$.

At $n=4{,}096$: total attention pairs $\approx n \times k = 4{,}096 \times 268 \approx 1.1$ million, versus full attention's $n^2 = 16.8$ million — about 15× fewer.

At $n=32{,}768$ (8× longer): sparse cost $\approx 32{,}768 \times 268 \approx 8.8$ million (grew 8×, matching the 8× growth in $n$). Full attention cost: $32{,}768^2 \approx 1.07$ billion (grew 64×, matching $n^2$). The gap widens from 15× to over 120× as the sequence gets longer — the entire point of a linear-cost pattern.

Worked example 2: a token's reachable set

Consider token 5,000 in a 10,000-token document, window $w=100$, 4 global tokens at positions 1–4. Directly, token 5,000 attends to tokens 4,950–5,050 (its window) and 1–4 (global) — not to token 9,500. But token 9,500 also attends to those same 4 global tokens, so information from it reaches a global token in one hop, and from there reaches token 5,000 in a second hop. Two hops through a hub substitute for the one direct connection full attention would have used — the model loses single-hop directness for a distant pair, but not reachability.

Set the exponent above near 1 to see roughly linear growth — that's how sparse-attention cost scales with sequence length, in contrast to the exponent-2 curve full attention traces.

What this means in practice

Sparse attention patterns were the dominant way to reach tens of thousands of tokens of context before hardware-level tricks like FlashAttention and IO-Aware Attention made full attention itself cheap enough at moderate lengths, leading many production models back to dense attention. Sparse patterns remain relevant for extremely long sequences (genomic data, very long documents) where even efficient dense attention is too costly, and where the sparsity pattern can be chosen to match known structure in the data.

Practice

1. With window $w=64$, $g=2$ global tokens, and $n=16{,}384$, roughly how many attention pairs does the sparse pattern compute, and how does that compare to full attention's $n^2$?
2. Why does adding random links (BigBird's contribution beyond Longformer) help preserve the model's theoretical expressive power compared to window-plus-global alone?