Sparse Attention: Windows, Global Tokens, and Information Paths

Updated September 2026 · 5 min read

Define a window without an off-by-one ambiguity

For causal window size $w$, count the current position as one of the $w$ allowed keys. Query $i$ may attend to $\max(0,i-w+1)\le j\le i$. At $w=1$, each token reads only itself. At $w\ge n$, the pattern becomes ordinary causal attention.

For $n=8$ and $w=3$, there are $1+2+3+3+3+3+3+3=21$ allowed query/key pairs. Full causal attention has $8\cdot9/2=36$. At fixed $w$, the edge count grows linearly with sequence length. A two-sided encoder window has a different definition and count; do not reuse a causal formula without adjusting it.

Receptive fields grow through layers

A local layer lets position $i$ directly read the previous $w-1$ positions. After $L$ such layers, information can travel backward at most $L(w-1)$ positions under this simple stride-one pattern. The receptive field contains at most $1+L(w-1)$ positions, bounded by the available prefix.

This is reachability, not a promise of perfect retrieval. Information moving across many layers can be transformed or lost. Conversely, a model might infer a useful answer without directly accessing the relevant original token if enough information has been propagated through intermediate states.

Global tokens create shortcuts

In a bidirectional encoder, selected global positions can attend to all valid positions, and ordinary positions can attend to those globals. A global token can collect information in one layer and distribute it in the next, connecting distant local regions in a small number of hops.

With $g$ global tokens and local width $w$, the edge count is of order $n(w+g)$ plus terms for the global rows. If $g$ grows with $n$, the benefit changes. A “global token” means a special attention connectivity pattern, not a magical token that automatically summarizes the sequence.

In a causal model, global connectivity must still obey time: a global position cannot gather future text and send it back to earlier queries. Intersecting a global pattern with the causal mask avoids this leakage, but it can also limit which shortcut paths are possible. Longformer provides a primary example of combining local and global attention.

Dilated and block patterns make different tradeoffs

Dilation samples keys at a fixed spacing, reaching farther with the same number of edges but skipping intervening positions. Strided or block patterns can create additional long-range paths. Random edges can improve graph connectivity without making every pair directly available; Big Bird studies a local/global/random construction.

A connectivity guarantee depends on the exact graph and number of layers. A model's ability to perform a task also depends on the learned representations and training. A graph-theoretic argument is not a benchmark result.

The mathematical mask and the hardware schedule

The pedagogical implementation computes an allowed Boolean matrix and feeds it to dense attention. This verifies the pattern but does not demonstrate sparse complexity. A sparse implementation needs blocks or index lists that allow the kernel to skip excluded interactions.

Arbitrary irregular sparsity can create indexing overhead and poor memory access. Block sparsity may compute some extra entries inside retained blocks while mapping more efficiently onto matrix hardware. The useful operating point balances model quality, edge count, kernel efficiency, and memory access.

A local decoder can bound its history cache

For strictly local layers, a streaming implementation only needs the most recent $w$ keys and values for that layer. A ring buffer can overwrite older entries after they leave the receptive window. Position IDs still represent their actual sequence locations; wrapping a physical buffer index is not the same as resetting logical position.

If some layers retain full attention, their caches still grow with context. If certain global tokens are retained indefinitely, account for their additional storage. Hybrid models need a layer-by-layer memory total.

Sparse and FlashAttention address different costs

Sparsity changes the attention function by removing edges. FlashAttention reorganizes how retained softmax attention is computed and stored. They can be combined. A claim of linear complexity from a fixed window is about the chosen sparse pattern, not the online-softmax algorithm alone.

Compress the history instead of selecting edges

Linear attention takes a different route: it summarizes previous key/value contributions in a fixed-size state.