mlsanityData to 7 Oct 2026

Sumformer: Universal Approximation for Efficient Transformers

arXiv 2307.02301 ↗First posted 5 Jul 2023cs.LG cs.CL stat.MLcited by 30

Not on the map. Why?

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.

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

Builds on

28 of 37 references.

References · 28

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  5. 2020Longformer: The Long-Document Transformercited by 3,362
  6. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  7. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  8. 2020Reformer: The Efficient Transformercited by 1,658
  9. 2020Rethinking Attention with Performerscited by 1,584
  10. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  11. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  12. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
16 more
  1. 2017Deep Setscited by 1,394
  2. 2020Efficient Transformers: A Surveycited by 784
  3. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
  4. 2016Error bounds for approximations with deep ReLU networkscited by 567
  5. 2022Transformers in Time Series: A Surveycited by 489
  6. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  7. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  8. 2017Optimal approximation of piecewise smooth functions using deep ReLU neural networkscited by 176
  9. 2018Universal approximations of invariant maps by neural networkscited by 127
  10. 2019Error bounds for approximations with deep ReLU neural networks in Ws,p normscited by 95
  11. 2017Optimal Approximation with Sparsely Connected Deep Neural Networkscited by 90
  12. 2019On the Limitations of Representing Functions on Setscited by 89
  13. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 82
  14. 2015Provable approximation properties for deep neural networkscited by 60
  15. 2021On the Expressive Power of Self-Attention Matricescited by 44
  16. 2020On Representing (Anti)Symmetric Functionscited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 12; 2025: 11; 2026: 5.

30 papers.

Sort:

By area:

  1. 2023Efficient Large Language Models: A Surveycited by 183
  2. 2023A mathematical perspective on Transformerscited by 160
  3. 2024DPOT: Auto-Regressive Denoising Operator Transformer for Large-Scale PDE Pre-Trainingcited by 137
  4. 2025CAKE: Cascading and Adaptive KV Cache Eviction with Layer Preferencescited by 59
  5. 2024Transformers are Universal In-context Learnerscited by 42
  6. 2024Measure-to-measure interpolation using Transformerscited by 28
  7. 2024Prompting a Pretrained Transformer Can Be a Universal Approximatorcited by 25
  8. 2024Do Efficient Transformers Really Save Computation?cited by 20
  9. 2024Clustering in pure-attention hardmax transformers and its role in sentiment analysiscited by 15
  10. 2024A Survey on Universal Approximation Theoremscited by 15
  11. 2025Sample Complexity and Representation Ability of Test-time Scaling Paradigmscited by 12
  12. 2026Attention Sinks Are Provably Necessary in Softmax Transformers: Evidence from Trigger-Conditional Taskscited by 10
18 more
  1. 2024On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformerscited by 8
  2. 2024Universal Approximation of Mean-Field Models via Transformerscited by 7
  3. 2025Transformers through the lens of support-preserving maps between measurescited by 5
  4. 2024On Expressive Power of Quantized Neural Networks under Fixed-Point Arithmeticcited by 3
  5. 2025End-to-End Multi-Modal Diffusion Mambacited by 3
  6. 2025Exact Sequence Interpolation with Transformerscited by 2
  7. 2025A unified framework for establishing the universal approximation of transformer-type architecturescited by 2
  8. 2026On the Expressive Power of Floating-Point Transformerscited by 2
  9. 2026Propagation of Chaos in Contextual Flow Mapscited by 2
  10. 2024How Out-of-Distribution Detection Learning Theory Enhances Transformer: Learnability and Reliabilitycited by 1
  11. 2025On the Existence of Universal Simulators of Attentioncited by 1
  12. 2026Quantitative Approximation Rates for Group Equivariant Learningcited by 1
  13. 2026Measure-to-measure Regression with Transformerscited by 1
  14. 2024Dynamic Universal Approximation Theory: The Basic Theory for Transformer-based Large Language Modelscited by 0
  15. 2025Transformers in Pseudo-Random Number Generation: A Dual Perspective on Theory and Practicecited by 0
  16. 2025An overview of neural architectures for self-supervised audio representation learning from masked spectrogramscited by 0
  17. 2025Vocabulary In-Context Learning in Transformers: Benefits of Positional Encodingcited by 0
  18. 2025On the Universality of Transformer Architectures; How Much Attention Is Enough?cited by 0