Sparse Attention Patterns
Why full attention gets expensive
Standard self-attention computes a score between every pair of tokens in a sequence, giving it $O(n^2)$ time and memory cost in sequence length $n$. For a 2K-token sequence that's 4 million pairwise scores per head per layer; at 128K tokens it's over 16 billion. Most of those scores end up tiny after softmax — a token at position 50,000 usually contributes almost nothing to the representation of a token at position 3. Sparse attention patterns are an attempt to skip computing scores that will be negligible anyway, restricting each query to attend to a structured subset of keys instead of all of them.
Common sparsity patterns
Several structured patterns recur across sparse-attention architectures. Local/sliding-window attention restricts each token to a fixed window of nearby tokens, capturing short-range dependencies cheaply. Strided attention has each token attend to every k-th token further back, cheaply covering long range at the cost of resolution. Global tokens (used in Longformer, BigBird) designate a small set of tokens — often the first few, or special [CLS]-like tokens — that attend to and are attended to by everything, acting as information-routing hubs. Block-sparse attention divides the sequence into fixed blocks and computes full attention only between a chosen subset of block pairs, which maps efficiently onto GPU tile-based matrix multiplication.
import numpy as np
def sliding_window_mask(seq_len: int, window: int) -> np.ndarray:
"""1 = allowed to attend, 0 = masked out."""
idx = np.arange(seq_len)
# distance between query i and key j
dist = np.abs(idx[:, None] - idx[None, :])
return (dist <= window).astype(np.int8)
def add_global_tokens(mask: np.ndarray, global_idx: list[int]) -> np.ndarray:
"""Global tokens attend to everything and are attended to by everything."""
mask = mask.copy()
mask[global_idx, :] = 1
mask[:, global_idx] = 1
return mask
m = sliding_window_mask(seq_len=10, window=2)
m = add_global_tokens(m, global_idx=[0])
print(m)Sparse attention patterns compared
| Pattern | Complexity | Captures | Weakness |
|---|---|---|---|
| Local window | O(n·w) | Short-range dependencies | Misses long-range links |
| Strided | O(n·n/s) | Coarse long-range coverage | Loses fine resolution at distance |
| Global tokens | O(n·g + g·n) | Hub-routed long-range info | Bottlenecks through few tokens |
| Block-sparse | O(n²/b) selected blocks | Flexible, GPU-efficient | Needs a good block-selection policy |
Sparsity is a bet about attention structure
Fixed patterns vs learned/dynamic sparsity
The patterns above are *fixed* — decided by architecture, not by the input. An alternative family learns which tokens to attend to dynamically, e.g. via clustering (Reformer's LSH attention groups similar queries/keys into buckets and only attends within a bucket) or via routing networks that predict which keys matter for a given query. Dynamic approaches can adapt to content but add their own overhead (clustering, routing) and training complexity. In practice, many production long-context systems favor fixed patterns — they're simpler to implement efficiently on hardware, and combine cleanly with other long-context tricks like attention sinks or windowed KV caches.
Where sparse attention is actually used
Longformer and BigBird combined local windows with global tokens for long-document NLP tasks. GPT-3 used alternating dense and locally-banded sparse attention layers in some configurations. More recent long-context LLMs often use sliding-window attention in most layers with occasional full-attention or global-token layers interleaved, trading some long-range precision for large reductions in memory and compute. The pattern choice is rarely academic — it directly determines what information can realistically flow between distant tokens in a single forward pass.
What's Next?
Sparse attention is one lever for taming the quadratic cost of self-attention; the next step is looking at how these ideas compose with other inference-time techniques — caching, windowing, and architectural alternatives that avoid quadratic attention altogether.
I build these systems professionally.
Whether it's a RAG pipeline, analytics migration, or AI workflow — let's talk.