$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

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 sparsemax or entmax.

Requirements for Expressivity

For a sparse pattern to be "expressive enough," it must satisfy three intuitive conditions:

  1. Self-attention: Every token must attend to itself.
  2. Connectivity: There must be a "chain" of direct connections covering all tokens (a Hamiltonian path).
  3. 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.

Table 1: Accuracy of various sparse attention patterns on the synthetic copying task across different model depths. Structured patterns like Strided and Fixed reach 100% accuracy with sufficient depth, while random patterns lag behind.

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

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