Sparse Attention Patterns › Summary

Sparse attention patterns address the quadratic complexity bottleneck of standard attention by restricting each query to attend to a subset of keys. Rather than computing all $n^2$ pairwise interactions, sparse patterns select a carefully structured subset that preserves the most important interactions while discarding the redundant ones.

The key patterns covered in this chapter are:

• Local attention: Each position attends to a fixed window of nearby tokens, exploiting the locality of language. Complexity is $O(n \cdot w)$ where $n$ is the sequence length and $w$ is the window size. Best suited for tasks where most relevant information is nearby, like named entity recognition and part-of-speech tagging.

• Strided attention: Positions attend to regularly-spaced hub positions, enabling long-range information flow within two hops. Complexity is $O(n \cdot n/s)$ where $s$ is the stride, creating highways for information propagation across long sequences. Provides global connectivity guarantee regardless of sequence length.

• Block-sparse attention: Groups positions into blocks of size $b$ and defines attention at the block level. Complexity is $O(n \cdot k \cdot b)$ where $k$ is the number of blocks attended to. Hardware-friendly due to regular memory access patterns that align with GPU execution units.

• Combined patterns: Real systems combine multiple patterns, often using factorized multi-head attention where different heads use different patterns. The union of local and strided patterns covers both short-range density and long-range connectivity.

The effectiveness of sparse attention rests on a key observation: most attention weights are small, concentrated on a few important positions. By carefully selecting which positions to attend to, sparse patterns preserve most of the representational power of full attention while dramatically reducing computational cost. The empirical confirmation of this observation, that trained attention matrices are highly concentrated even without explicit sparsity constraints, is what gives the sparse attention approach its theoretical grounding.

Choosing a sparse pattern requires understanding your task's dependency structure, your sequence length distribution, and your hardware constraints. Local patterns are easy to implement and cache-friendly. Global patterns require more engineering effort but enable qualitatively different capabilities. Block structure improves hardware efficiency at the cost of pattern granularity.

These building blocks form the foundation for efficient attention mechanisms like Longformer and BigBird, along with Sparse Transformer. The next chapters explore specific architectures that combine sparse patterns with additional techniques like sliding windows and global tokens to achieve even better trade-offs between efficiency and expressiveness. As you move into those architectures, you will see the patterns from this chapter appear repeatedly as components in more sophisticated designs.