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

arXiv: https://arxiv.org/abs/2006.04862 · HTML: https://mlsanity.com/paper/2006.04862/

## Key facts

- Cited by 83 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

## Built on by (most cited first, 30 of 83)

- [One Fits All:Power General Time Series Analysis by Pretrained LM](https://mlsanity.com/paper/2302.11939/) (2023)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2402.00789/) (2024)
- [SparQ Attention: Bandwidth-Efficient LLM Inference](https://mlsanity.com/paper/2312.04985/) (2023)
- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Beyond the Limits: A Survey of Techniques to Extend the Context Length in Large Language Models](https://mlsanity.com/paper/2402.02244/) (2024)
- [Revisiting Over-smoothing in BERT from the Perspective of Graph](https://mlsanity.com/paper/2202.08625/) (2022)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [Dynamic Context Pruning for Efficient and Interpretable Autoregressive Transformers](https://mlsanity.com/paper/2305.15805/) (2023)
- [Combiner: Full Attention Transformer with Sparse Computation Cost](https://mlsanity.com/paper/2107.05768/) (2021)
- [SCBench: A KV Cache-Centric Analysis of Long-Context Methods](https://mlsanity.com/paper/2412.10319/) (2024)
- [On the Emergence of Position Bias in Transformers](https://mlsanity.com/paper/2502.01951/) (2025)
- [Your Transformer May Not be as Powerful as You Expect](https://mlsanity.com/paper/2205.13401/) (2022)
- [MATE: Multi-view Attention for Table Transformer Efficiency](https://mlsanity.com/paper/2109.04312/) (2021)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [On the Role of Attention Masks and LayerNorm in Transformers](https://mlsanity.com/paper/2405.18781/) (2024)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?](https://mlsanity.com/paper/2307.14023/) (2023)
- [SparseBERT: Rethinking the Importance Analysis in Self-attention](https://mlsanity.com/paper/2102.12871/) (2021)
- [SepLLM: Accelerate Large Language Models by Compressing One Segment into One Separator](https://mlsanity.com/paper/2412.12094/) (2024)
- [Memorization Capacity of Multi-Head Attention in Transformers](https://mlsanity.com/paper/2306.02010/) (2023)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Mechanics of Next Token Prediction with Self-Attention](https://mlsanity.com/paper/2403.08081/) (2024)
- [Leveraging redundancy in attention with Reuse Transformers](https://mlsanity.com/paper/2110.06821/) (2021)
- [Universal Approximation Under Constraints is Possible with Transformers](https://mlsanity.com/paper/2110.03303/) (2021)
- [Implicit Bias and Fast Convergence Rates for Self-attention](https://mlsanity.com/paper/2402.05738/) (2024)
- [Unraveling Attention via Convex Duality: Analysis and Interpretations of Vision Transformers](https://mlsanity.com/paper/2205.08078/) (2022)

## Abstract (arXiv)

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 n2 connections. Lastly, we present experiments comparing different patterns/levels of sparsity on standard NLP tasks.