Sparse Attention Patterns › Sparse Attention Patterns

Standard attention computes pairwise scores between all tokens, creating an $n \times n$ attention matrix where $n$ is the sequence length. This quadratic scaling becomes prohibitively expensive for long sequences. A sequence of 1024 tokens requires about one million attention score computations. Scale that to 8192 tokens, and the count jumps to 67 million. For 32768 tokens, you need over a billion. Even on the most powerful GPUs available today, full attention at these lengths is slow enough to make training impractical and inference unusable in real-time applications.

Sparse attention offers a principled solution: instead of attending to every position, each token attends only to a carefully chosen subset. The key insight is that most attention weights in practice are small, meaning many token pairs contribute little to the final representation. By restricting attention to positions that matter most, sparse patterns achieve near-linear complexity while preserving the model's ability to capture important relationships.

To appreciate why this works, think about how you read a paragraph. When processing the word "they" in the middle of a sentence, you scan back a few words to find the referent, not the entire document. When you encounter a technical term, you look at the surrounding clause for context, not at paragraphs from pages ago. The same intuition applies to transformer attention: the information that matters most is usually nearby, with occasional long-range dependencies that require targeted access rather than exhaustive search.

This chapter explores the fundamental sparse attention patterns that form the building blocks of efficient transformers. We will implement local windowed attention, strided patterns, and block-sparse attention, then combine them into hybrid approaches used by models like Sparse Transformer and Longformer, along with BigBird. Along the way we will analyze the complexity guarantees each pattern provides, examine how information flows through sparse attention layers, and understand the hardware realities that make some patterns more practical than others.

The efficiency gains from sparse attention are not merely academic. They directly determine what problems language models can solve. A model that can only process 512 tokens cannot read a research paper in one pass. A model capped at 2048 tokens struggles with long-form code files. Sparse attention, when designed carefully, lifts these limits by orders of magnitude while maintaining most of the expressive power of full attention.