Recently, Transformer networks have redefined the state of the art in many NLP tasks. However, their "Achilles' heel" is the self-attention mechanism. To compute attention, every token in a sequence looks at every other token, requiring $O(n^2)$ operations for a sequence of length $n$. This quadratic scaling makes processing very long sequences computationally prohibitive.
To address this, researchers have proposed various "sparse" Transformers (e.g., Longformer, BigBird, Reformer) that limit which tokens can interact. While empirically successful, a fundamental theoretical gap remained: do we lose expressive power by cutting these connections? Can a sparse model still represent the same complex functions as a dense one?
This paper, presented at NeurIPS 2020, provides a theoretical foundation proving that sparse Transformers with only $O(n)$ connections per layer are "universal approximators"—meaning they are theoretically just as expressive as standard Transformers with $O(n^2)$ connections.
A Unifying Framework for Sparse Attention
The authors establish a unifying framework by defining a Sparse Transformer Block (STB) that generalizes existing sparse models. This framework accounts for "cycling" patterns (where different layers use different sparsity masks) and various "probability maps" (generalizations of the standard softmax).
They identify two intuitive conditions required for universal approximation:
- Assumption 1 (Sparsity Pattern): The graph of connections must be sufficiently "connected." Specifically, there must be a path for information to flow from any token to any other token within a finite number of layers (e.g., a Hamiltonian path).
- Assumption 2 (Probability Map): The function used to turn attention scores into weights must be able to behave like a "hardmax" (picking the single most important token) when scaled.
If these conditions are met, stacking enough sparse layers allows the model to simulate the behavior of a dense Transformer.
Key Insights: Why Sparse Models Work
- $O(n)$ is Sufficient: The most striking finding is that a linear number of connections ($O(n)$) per layer is enough to maintain universal approximation. The $O(n^2)$ "all-to-all" connectivity is not strictly necessary for expressivity.
- Connectivity is King: The engineering rule of thumb—that tokens should reach each other in a few "hops"—is formally justified. If the sparsity pattern allows information to propagate across the sequence, the model remains powerful.
- Depth-Sparsity Trade-off: While sparse models are as expressive as dense ones, they may require more layers (by a factor of $p$, where $p$ is the number of distinct sparsity patterns used) to achieve the same representational power.
- Design Over Randomness: How you sparsify matters as much as how much you sparsify. Designed patterns significantly outperform random ones.
Empirical Validation
The authors validated their theory using several standard benchmarks, including a Synthetic Copying Task, the One Billion Word Benchmark, WMT18 English-Czech, and GLUE (MNLI and XNLI).
In the Synthetic Copying Task, models utilizing STRIDED and FIXED patterns achieved 100% accuracy within 2 to 4 layers. Conversely, the STAR pattern struggled, likely due to its heavy reliance on a single "relay" token. Furthermore, random sparsity patterns performed significantly worse than designed patterns, even with similar connection counts.
For Language Modeling and Translation, the STRIDED and STAR patterns performed nearly as well as full attention, even at high sparsity levels (e.g., over 90% of connections removed). On GLUE Tasks, the "UNION" configuration (combining multiple sparsity patterns) proved the most robust, often matching the performance of the dense BERT-base model.
Limitations and Future Directions
While this paper provides strong theoretical backing for sparse Transformers, it has a few limitations:
- Fixed Sequence Length: The proof treats the sequence length $n$ as a fixed constant and does not strictly address asymptotic behavior as $n \to \infty$.
- Expressivity vs. Learnability: The theorem proves a sparse Transformer can represent any function, but it does not guarantee that standard training algorithms (like SGD) will easily find those optimal parameters.
- Encoder Focus: The analysis primarily focuses on the encoder portion of the Transformer architecture.
Ultimately, this framework paves the way for designing even more efficient sparsity patterns optimized for specific hardware or tasks, secure in the knowledge that foundational expressive power is not being sacrificed.
Summary updated