Sparse Attention

Definition

Sparse attention breaks the $O(s^2)$ wall by changing which query–key pairs may interact — masking most entries of the score matrix before softmax — while keeping the attention math itself unchanged. The motivation is empirical: in trained models most attention mass is local, so the dense $s\times s$ matrix pays in full for a nearly-sparse object. Structured patterns (window + global + random) recover $O(s)$ cost, provably without losing expressive power in the limit.

Key math / How it works

One masked op with binary mask $M\in \{0,1{\}}^{s\times s}$:

$A=\mathrm{softmax}(\frac{Q{K}^{\top }}{\sqrt{d_k}}+\log M)V,\log M_{ij}=\{\begin{array}{ll}0& \text{allowed}\\ -\infty & \text{masked}\end{array}$

Core cost $\propto \Vert M{\Vert }_0$, not $s^2$. Pattern families:

• Sliding window — local band, $\Vert M{\Vert }_0\approx sw$, $O(swd)$.
• Longformer (Beltagy et al., 2020; arXiv:2004.05150): window + dilation (gaps of $d_{\text{dil}}$ widen reach per layer, like dilated convs) + global tokens (a few positions, e.g. [CLS], attend to and are attended by all — one-hop hubs). Cost $O(sw+sg)$, $g\ll s$. Scaled bidirectional BERT-style attention to thousands of tokens.
• BigBird (Zaheer et al., 2020; arXiv:2007.14062): window + global + random ($r$ random keys per query). Viewing $M$ as a graph, random edges make it an expander with small diameter, so any two tokens connect via a short path. Proven to be a universal approximator and Turing-complete at $O(s)$ cost.

Entries and FLOPs:

Pattern	Allowed entries	Scaling
Dense	$s^2$	quadratic
Window ($w$)	$sw$	linear
Window + global ($g$)	$sw+2gs$	linear
BigBird ($+r$ random)	$s(w+2g+r)$	linear

Why it matters

Sparse patterns pay off precisely in the long-context regime ($s\gtrsim d$) where the $s^2$ term dominates the $O(s{d}^2)$ projections. Practically, window + global does most of the work: BigBird’s universality is an existence result, and random access is hardware-unfriendly (gather-scatter, poor coalescing), so deployed stacks lean on window + global + a few dense layers rather than random edges.

Taught in

• 06-sparse-and-sliding-window — §3 the pattern taxonomy and universality argument.

See also

• sliding-window-attention — the local base pattern
• attention-sinks — the streaming/eviction cousin
• linear-attention — dissolving the matrix vs. thinning it
• attention-glossary · attention-mechanisms