Abstract
Standard Transformers are computationally expensive due to their $O(n^2)$ complexity, where every token attends to every other token. This paper provides the first formal proof that Sparse Transformers—even those with only $O(n)$ connections—are universal approximators. We demonstrate that they can represent any continuous sequence-to-sequence function as effectively as dense models, provided they meet basic connectivity requirements. Our empirical results show that structured sparsity patterns, when paired with sufficient depth, achieve performance parity with full attention on both synthetic and standard NLP benchmarks.
Introduction
The "quadratic bottleneck" is the primary obstacle to scaling Transformer architectures to long documents or high-resolution data. While various "Sparse Transformers" have been proposed to limit attention to local neighbors or specific global tokens, a fundamental theoretical question remained: do we lose expressive power by cutting these connections? This work addresses this gap by establishing a unifying framework for sparse attention and proving a Universal Approximation Theorem for these models.
Methodology
The Unifying Framework
We define a Sparse Transformer Block (STB) that generalizes existing models through:
- Cycling Blocks: Layers that alternate between different sparsity patterns (e.g., local vs. strided).
- Sparsity Patterns: Specific indices defining query-key interactions.
- General Probability Maps: Support for functions beyond standard Softmax, such as
sparsemaxorentmax.
Requirements for Expressivity
For a sparse pattern to be "expressive enough," it must satisfy three intuitive conditions:
- Self-attention: Every token must attend to itself.
- Connectivity: There must be a "chain" of direct connections covering all tokens (a Hamiltonian path).
- Full Reachability: Every token must be able to "see" every other token through multiple "hops" across a finite number of layers.
Experimental Validation
We validated our theory using a mix of synthetic and standard NLP benchmarks, including the One Billion Word Benchmark, WMT18 (English-Czech/German), and GLUE. A key test was the Synthetic Copying Task, a stress test requiring the model to move information from the first half of a sequence to the second half.
Key Results
Our findings confirm that connectivity is more critical than density. As long as information can flow between tokens via multiple layers, the model retains its fundamental power. Notably, we found that depth compensates for sparsity: while a dense model might see everything in one step, a sparse model requires a few additional layers to propagate information across the sequence.
As shown in the table above, structured patterns (Strided and Fixed) achieved 100% accuracy on the copying task within 2-4 layers. Conversely, purely random sparsity patterns consistently underperformed, suggesting that structured communication is superior for learning.
Conclusion and Limitations
This research provides a theoretical green light for highly efficient $O(n)$ models like BigBird or Longformer. However, some limitations remain. Our proof treats sequence length as a fixed constant and does not address generalization when lengths change between training and inference. Furthermore, while we prove a solution exists, it does not guarantee that standard optimization algorithms like Adam will easily find the optimal weights in a sparse landscape. Future work is needed to bridge the gap between theoretical capacity and practical learnability.
Summary updated