# Sumformer: Universal Approximation for Efficient Transformers

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 37 references that are in the map.
- First posted on arXiv 5 Jul 2023.

## Builds on (most cited first, 28 of 28)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Transformers in Time Series: A Survey](https://mlsanity.com/paper/2202.07125/) (2022)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Universal approximations of invariant maps by neural networks](https://mlsanity.com/paper/1804.10306/) (2018)
- [Error bounds for approximations with deep ReLU neural networks in Ws,p norms](https://mlsanity.com/paper/1902.07896/) (2019)
- [Optimal Approximation with Sparsely Connected Deep Neural Networks](https://mlsanity.com/paper/1705.01714/) (2017)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [Provable approximation properties for deep neural networks](https://mlsanity.com/paper/1509.07385/) (2015)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [On Representing (Anti)Symmetric Functions](https://mlsanity.com/paper/2007.15298/) (2020)

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

- [Efficient Large Language Models: A Survey](https://mlsanity.com/paper/2312.03863/) (2023)
- [A mathematical perspective on Transformers](https://mlsanity.com/paper/2312.10794/) (2023)
- [DPOT: Auto-Regressive Denoising Operator Transformer for Large-Scale PDE Pre-Training](https://mlsanity.com/paper/2403.03542/) (2024)
- [CAKE: Cascading and Adaptive KV Cache Eviction with Layer Preferences](https://mlsanity.com/paper/2503.12491/) (2025)
- [Transformers are Universal In-context Learners](https://mlsanity.com/paper/2408.01367/) (2024)
- [Measure-to-measure interpolation using Transformers](https://mlsanity.com/paper/2411.04551/) (2024)
- [Prompting a Pretrained Transformer Can Be a Universal Approximator](https://mlsanity.com/paper/2402.14753/) (2024)
- [Do Efficient Transformers Really Save Computation?](https://mlsanity.com/paper/2402.13934/) (2024)
- [Clustering in pure-attention hardmax transformers and its role in sentiment analysis](https://mlsanity.com/paper/2407.01602/) (2024)
- [A Survey on Universal Approximation Theorems](https://mlsanity.com/paper/2407.12895/) (2024)
- [Sample Complexity and Representation Ability of Test-time Scaling Paradigms](https://mlsanity.com/paper/2506.05295/) (2025)
- [Attention Sinks Are Provably Necessary in Softmax Transformers: Evidence from Trigger-Conditional Tasks](https://mlsanity.com/paper/2603.11487/) (2026)
- [On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers](https://mlsanity.com/paper/2404.03380/) (2024)
- [Universal Approximation of Mean-Field Models via Transformers](https://mlsanity.com/paper/2410.16295/) (2024)
- [Transformers through the lens of support-preserving maps between measures](https://mlsanity.com/paper/2509.25611/) (2025)
- [On Expressive Power of Quantized Neural Networks under Fixed-Point Arithmetic](https://mlsanity.com/paper/2409.00297/) (2024)
- [End-to-End Multi-Modal Diffusion Mamba](https://mlsanity.com/paper/2510.13253/) (2025)
- [Propagation of Chaos in Contextual Flow Maps](https://mlsanity.com/paper/2605.16747/) (2026)
- [Exact Sequence Interpolation with Transformers](https://mlsanity.com/paper/2502.02270/) (2025)
- [A unified framework for establishing the universal approximation of transformer-type architectures](https://mlsanity.com/paper/2506.23551/) (2025)
- [On the Expressive Power of Floating-Point Transformers](https://mlsanity.com/paper/2601.16450/) (2026)
- [Measure-to-measure Regression with Transformers](https://mlsanity.com/paper/2605.28075/) (2026)
- [How Out-of-Distribution Detection Learning Theory Enhances Transformer: Learnability and Reliability](https://mlsanity.com/paper/2406.12915/) (2024)
- [On the Existence of Universal Simulators of Attention](https://mlsanity.com/paper/2506.18739/) (2025)
- [Quantitative Approximation Rates for Group Equivariant Learning](https://mlsanity.com/paper/2602.20370/) (2026)
- [Dynamic Universal Approximation Theory: The Basic Theory for Transformer-based Large Language Models](https://mlsanity.com/paper/2407.00958/) (2024)
- [Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practice](https://mlsanity.com/paper/2508.01134/) (2025)
- [An overview of neural architectures for self-supervised audio representation learning from masked spectrograms](https://mlsanity.com/paper/2509.18691/) (2025)
- [Vocabulary In-Context Learning in Transformers: Benefits of Positional Encoding](https://mlsanity.com/paper/2511.06376/) (2025)
- [On the Universality of Transformer Architectures; How Much Attention Is Enough?](https://mlsanity.com/paper/2512.18445/) (2025)

## Abstract (arXiv)

Natural language processing (NLP) made an impressive jump with the introduction of Transformers. ChatGPT is one of the most famous examples, changing the perception of the possibilities of AI even outside the research community. However, besides the impressive performance, the quadratic time and space complexity of Transformers with respect to sequence length pose significant limitations for handling long sequences. While efficient Transformer architectures like Linformer and Performer with linear complexity have emerged as promising solutions, their theoretical understanding remains limited. In this paper, we introduce Sumformer, a novel and simple architecture capable of universally approximating equivariant sequence-to-sequence functions. We use Sumformer to give the first universal approximation results for Linformer and Performer. Moreover, we derive a new proof for Transformers, showing that just one attention layer is sufficient for universal approximation.