§11.2Efficient Self-Attention: Sparse & Linearized

Self-attention self-attention Attention where the queries, keys, and values all come from the same sequence; each output embedding is a context-dependent weighted average of the sequence. defined in ch. 3 — open in glossary is the heart of the transformer — but it has a scaling problem. Because the weights come from comparing every token with every other token, the layer’s time and memory grow like $O(n^2)$ in the sequence length $n$. That quadratic cost is the bottleneck for long documents, speech, and vision. Two families of efficient attention efficient attention Techniques that reduce self-attention's O(n²) cost for long sequences, chiefly sparse and linearized attention. defined in ch. 11 — open in glossary attack it: introducing sparsity, or replacing the attention operation with a kernel.

Sparse attention

Sparse attention sparse attention Computing attention over only a chosen subset of query-key pairs (global, band, dilated, random, or block-local patterns) to cut cost. defined in ch. 11 — open in glossary simply computes fewer query-key pairs, chosen by a fixed pattern. Most schemes are built from a handful of atomic patterns — switch between them below and watch the sparsity (the fraction of skipped pairs) change:

• Global — a few special tokens attend to everything (and everything to them).
• Band — attend to a diagonal band of nearby tokens (a local window).
• Dilated — a band with gaps, widening reach without extra cost.
• Random — sample a few random keys per query.
• Block-local — attend only within fixed blocks.

Real models mix these: Longformer combines global + band, and BigBird adds random on top. The payoff is huge — both push the maximum sequence length to 4,096 tokens, 8× BERT’s 512. The pattern can even be learned rather than fixed (Reformer clusters similar tokens with a hash function).

Linearized attention

The other approach changes the order of operations. For a general similarity function, an attention output is:

Standard attention uses $\operatorname{sim}(Q_i, K_j) = \exp(Q_i^\top K_j)$, which couples every $i$ with every $j$ — the $O(n^2)$ cost. Linearized attention linearized attention Rewriting the attention similarity as a kernel φ(Q)ᵀφ(K) and reordering the sums so time and memory scale linearly in sequence length. defined in ch. 11 — open in glossary writes the similarity as a kernel that factorizes:

• $\varphi$ — a feature map applied to each query and key separately.
• Because $\varphi(Q_i)$ doesn’t depend on $j$ or $k$, we can pull it out of the sums:

Here’s the difference in cost as sequences grow — the whole reason these methods exist:

Both routes — sparse and linearized — let transformers handle far longer sequences. Next: transformers leaving text behind entirely, for vision and tables.