Sparse Attention Patterns
What you'll learn: How sparse attention patterns reduce computation from quadratic to subquadratic complexity by attending to only a subset of tokens.
The Attention Bottleneck
Standard self-attention computes relationships between every pair of tokens in a sequence. For a sequence of length n, this creates n² comparisons — which becomes prohibitively expensive as sequences grow longer. Sparse attention patterns solve this by having each token attend to only a carefully chosen subset of other tokens.
Fixed vs Learned Sparsity
Fixed patterns use predetermined structures that don't require learning:
- Strided attention: Each token attends to every k-th position (e.g., positions 0, 4, 8, 12...)
- Local + global: Attend to nearby neighbors and a few global anchor positions
- Block-local: Divide the sequence into chunks; attend within chunks
These patterns scale subquadratically — meaning the computation grows slower than n². For example, strided patterns might scale as O(n√n) or O(n log n).
Learned patterns let the model discover which positions matter through training. The network learns attention masks or routing decisions, adapting sparsity to the data itself.
Why This Matters
Sparse patterns enable longer context windows without exhausting memory or compute budgets. They complement techniques like sliding window attention (which you've seen) and ALiBi, but go further by breaking the strict quadratic wall entirely.
The trade-off? Information flow becomes more constrained — distant tokens may only connect through multiple layers rather than directly. But for many tasks, this hierarchical information propagation works surprisingly well.
Key Takeaway: Sparse attention patterns strategically limit which tokens attend to each other using fixed or learned structures, achieving subquadratic scaling and enabling much longer sequence processing than full attention allows.