Plain-English Summary
The original Transformer’s attention mechanism has each word look at every other word in the sequence. For a 1,000-word document, that means a million attention comparisons. For 10,000 words, it is 100 million. This quadratic scaling makes long documents prohibitively expensive. Sparse Transformers solved this by having each word attend to only a carefully chosen subset of other words, reducing computation dramatically while preserving most of the model’s quality.
The paper introduced two sparse attention patterns: “strided” attention (where each word looks at nearby words plus evenly spaced distant words) and “fixed” attention (where specific positions serve as summary points that all words attend to). By combining these patterns across layers, the model maintains long-range connectivity while doing far less computation.
Think of it like reading a long book. Instead of re-reading every page before understanding the current one, you remember recent pages clearly and have bookmarks for key earlier passages. You skip most pages but still grasp the overall story.
Key Innovation
The core innovation was factoring the full attention matrix into sparse patterns that cover all positions across multiple layers. The strided pattern ensures local context is captured, while the fixed pattern provides global connectivity. Together, they reduce the attention cost from O(N^2) to O(N*sqrt(N)), enabling sequences up to 16x longer for the same compute budget.
The paper also introduced efficient GPU kernels for sparse attention and demonstrated the approach on text, images, and audio — showing that sparse attention patterns are broadly applicable across modalities.
Impact on the Field
Sparse Transformers opened the “efficient Transformer” research direction that produced dozens of follow-up papers. The core insight — that full attention is wasteful because most attention weights are near zero — motivated a wave of architectures that use structured or learned sparsity to reduce attention cost.
The practical impact was enabling models to process longer sequences. This was an early step toward the long-context models (128K+ tokens) that are now common, though modern approaches (like FlashAttention) took different paths to achieve similar goals.
Models That Built on This
GPT-3 incorporated ideas from sparse attention in its architecture. Longformer (Allen AI) extended sparse attention with a combination of local and global attention tokens. BigBird (Google) proved theoretical properties of sparse attention patterns. LED (Longformer Encoder-Decoder) applied sparse attention to sequence-to-sequence tasks. While FlashAttention ultimately became the dominant efficiency technique (by making full attention fast rather than sparse), the sparse attention paradigm continues to influence architecture design, especially for extremely long sequences.