Sparse Attention
Sparse attention restricts each token to attend to a chosen subset of positions, cutting the quadratic cost of full attention while preserving important connections.
Not every pair needs a score
Full self-attention lets every token attend to every other token, which costs time and memory proportional to the square of the sequence length. For long sequences this becomes the dominant expense. Sparse attention observes that most of those pairwise interactions carry little weight, so it computes attention only over a structured subset of positions for each query, reducing the cost while keeping the connections that matter most.
Common sparsity patterns
- Sliding window: each token attends to a fixed number of nearby tokens, capturing local context
- Dilated or strided: attend to positions at regular gaps to reach farther with the same budget
- Global tokens: a few designated tokens attend to and are attended by everything, carrying summary information
- Block-local: partition the sequence into blocks and attend within and between selected blocks
Practical long-sequence models combine patterns, for example a sliding window for local detail plus a handful of global tokens for long-range routing. This mixture keeps cost near linear in sequence length while still allowing information to travel across the whole sequence through the global tokens.
Learned versus fixed sparsity
Fixed patterns are chosen in advance and are simple and hardware-friendly. Learned sparsity instead selects which positions to attend to based on content, for example by clustering or hashing similar queries and keys together so that likely-relevant pairs share a bucket. Learned schemes can be more accurate per unit of compute but add complexity and can be harder to implement efficiently on accelerators.
Trade-offs
Sparse attention is an approximation: if two tokens that genuinely interact are never allowed to attend to each other, the model cannot capture that relationship, so the pattern must be chosen to match the task's dependency structure. Where exactness is required, flash attention reduces the cost of full attention without approximating. Where a different mathematical reformulation is acceptable, linear attention achieves linear scaling by another route.