Core ML

Sparse Attention

Instead of scoring every token against every other token, sparse attention computes only a structured subset of those scores — nearby tokens for local context, a few strided positions for long-range reach, and a handful of global tokens that everything can see.

Why Does This Exist?

Standard self-attention fills every cell of the $N \times N$ score matrix. That's $N^2$ scores per layer, which for a document of 4,096 tokens costs 16 million cells — and for 16,384 tokens, 268 million. Sliding window attention cuts this by restricting each query to its local neighbourhood, but pure local attention misses long-range dependencies that can't propagate through enough layers.

The goal of sparse attention is to be more surgical: compute some long-range scores (enough to cover patterns that matter) while skipping the bulk that don't contribute. The resulting attention pattern is no longer dense — it's a sparse subset of the full matrix, chosen by a rule rather than filled naively.

Sparse Transformer (Child et al., 2019) formalised this idea. Longformer (2020) and BigBird (2021) refined the pattern for practical long-document tasks. The approach has three ingredients, which most sparse patterns combine: local windows, strided attention, and global tokens.

Think of It Like This

City roads vs. every road

A city's road network doesn't connect every house directly to every other house — that would be $N^2$ roads. Instead it uses local streets (everyone connects to their neighbours), arterials (periodic long roads that cross many blocks), and hubs (downtown intersections that everyone can reach). You can get from anywhere to anywhere else by combining those route types, and the total road count is far less than $N^2$ .

Sparse attention is the same plan for a token's context graph. Local streets are the sliding window. Arterials are strided positions. Hubs are global tokens. Together they cover the cases that matter without filling every cell.

How It Actually Works

Local windows

Each query attends to the $W$ nearest tokens on either side. This covers all the linguistic structure that relies on proximity: syntactic agreement, coreference within a clause, local code context. Cost: $O(N \cdot W)$ .

Strided attention

Every $s$ -th position is a "stride head" that attends to every $s$ -th key position. A query at position 300 can reach positions 0, 50, 100, 150, 200, 250, 300 in one hop, giving indirect access to all content every $s$ tokens away. This is how information from far-away positions propagates to the current query without every intermediate position having to relay it. Cost: $O(N \cdot N/s)$ .

Global tokens

A small set of designated tokens (CLS, question tokens, special markers) attend to every position and every position attends to them. The cost is $O(N \cdot g)$ for $g$ global tokens, and they act as hubs: any two tokens that would never reach each other through local or strided paths can communicate by going through a global token. Longformer uses global tokens on all whitespace-delimited sentence boundaries for document QA; BigBird uses them on random positions sampled each layer.

Combined complexity

A realistic pattern (local window $W=512$ , stride $s=16$ , global $g=128$ ) on a sequence of $N=16384$ tokens:

Local: $N \cdot W = 8.4 \text{M}$ cells
Strided: $N \cdot N/s = 16.8 \text{M}$ cells
Global: $N \cdot g = 2.1 \text{M}$ cells
Total: ~27M cells, vs. $N^2 = 268 \text{M}$ for full attention — about 10× less.

Show Me the Code

Building a binary attention mask for a combined local+global sparse pattern and verifying the active cell count.

1import numpy as np2
3n, W, g = 64, 8, 4   # scaled-down illustration4
5mask = np.zeros((n, n), dtype=bool)6
7# Local window: each query attends to its W nearest keys8for i in range(n):9    lo, hi = max(0, i - W // 2), min(n, i + W // 2 + 1)10    mask[i, lo:hi] = True11
12# Global tokens: first g positions attend to all; all attend to first g13mask[:g, :] = True14mask[:, :g] = True15
16active = mask.sum()17full = n * n18
19print(f"N={n}, W={W}, g={g}")20print(f"Active cells:  {active:,}")21print(f"Full attention: {full:,}")22print(f"Reduction: {full / active:.1f}×")23# N=64, W=8, g=424# Active cells:  74325# Full attention: 409626# Reduction: 5.5×

At the toy scale the reduction is modest; at $N=16384$ the reduction grows toward 10× or more because the local-window cost grows as $O(N)$ while full attention grows as $O(N^2)$ .

Watch Out For

Assuming sparse patterns transfer across tasks

The right pattern depends on the task's information flow. A sliding window is excellent for language modelling where local syntax dominates. A global-token pattern works for document QA where the question needs to reach every paragraph. Using a language-modelling pattern on a QA task means the question tokens can't directly see the relevant passage unless the global set is defined accordingly. Don't import a sparse pattern from a different task without checking whether its information flow matches yours.

Confusing sparse attention with linear attention

Both handle long sequences more cheaply than full dense attention. Sparse attention is still exact within its chosen pattern — it computes the true softmax over a subset of keys. Linear attention approximates the full softmax using a kernel trick, making it cheaper but introducing approximation error. They solve different versions of the cost problem.

The Quick Version

Sparse attention skips most cells of the $N \times N$ score matrix, computing only a structured subset.
Three common ingredients: local windows (nearby context, $O(N \cdot W)$ ), strided attention (periodic long-range reach, $O(N^2/s)$ ), and global tokens (hubs that every position can access, $O(N \cdot g)$ ).
Combined patterns reduce score cells by 5–10× at practical document lengths, enabling tasks that full attention can't afford.
The scores within the chosen pattern are exact — no approximation, unlike linear attention.
The right pattern is task-dependent; a pattern optimised for language modelling may not work for document QA.