O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers

Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, Sanjiv Kumar

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:

  1. 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).
  2. 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).

Copying Task Results

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

Abstract

Recently, Transformer networks have redefined the state of the art in many NLP tasks. However, these models suffer from quadratic computational cost in the input sequence length $n$ to compute pairwise attention in each layer. This has prompted recent research into sparse Transformers that sparsify the connections in the attention layers. While empirically promising for long sequences, fundamental questions remain unanswered: Can sparse Transformers approximate any arbitrary sequence-to-sequence function, similar to their dense counterparts? How does the sparsity pattern and the sparsity level affect their performance? In this paper, we address these questions and provide a unifying framework that captures existing sparse attention models. We propose sufficient conditions under which we prove that a sparse attention model can universally approximate any sequence-to-sequence function. Surprisingly, our results show that sparse Transformers with only $O(n)$ connections per attention layer can approximate the same function class as the dense model with $n^2$ connections. Lastly, we present experiments comparing different patterns/levels of sparsity on standard NLP tasks.
BibTeX
@inproceedings{yun2020o,
  author = {Chulhee Yun and Yin-Wen Chang and Srinadh Bhojanapalli and Ankit Singh Rawat and Sashank J. Reddi and Sanjiv Kumar},
  title = {{O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=S1wnlRQublZ},
}
Figure