mlsanityData to 14 Oct 2026

Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?

arXiv 2307.14023 ↗First posted 26 Jul 2023cs.LGcited by 47

Not on the map. Why?

Abstract (arXiv)

Existing analyses of the expressive capacity of Transformer models have required excessively deep layers for data memorization, leading to a discrepancy with the Transformers actually used in practice. This is primarily due to the interpretation of the softmax function as an approximation of the hardmax function. By clarifying the connection between the softmax function and the Boltzmann operator, we prove that a single layer of self-attention with low-rank weight matrices possesses the capability to perfectly capture the context of an entire input sequence. As a consequence, we show that one-layer and single-head Transformers have a memorization capacity for finite samples, and that Transformers consisting of one self-attention layer with two feed-forward neural networks are universal approximators for continuous permutation equivariant functions on a compact domain.

Key facts. Cited by 47 papers in the map (data through 14 Oct 2026). Builds on 37 of its 64 references that are in the map. First posted on arXiv 26 Jul 2023.

Builds on

37 of 64 references.

References · 37

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  5. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,372
  6. 2021Convex optimizationcited by 2,515
  7. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  8. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  9. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  10. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 672
  11. 2020Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuningcited by 671
  12. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
25 more
  1. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
  2. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
  3. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  4. 2019Visualizing and Measuring the Geometry of BERTcited by 216
  5. 2023ReLoRA: High-Rank Training Through Low-Rank Updatescited by 204
  6. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  7. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  8. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  9. 2016Identity Matters in Deep Learningcited by 109
  10. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  11. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  12. 2020Low-Rank Bottleneck in Multi-head Attention Modelscited by 89
  13. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 83
  14. 2018ResNet with one-neuron hidden layers is a Universal Approximatorcited by 79
  15. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 78
  16. 2022Your Transformer May Not be as Powerful as You Expectcited by 55
  17. 2021On the Expressive Power of Self-Attention Matricescited by 47
  18. 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
  19. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 40
  20. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  21. 2021Universal Approximation Under Constraints is Possible with Transformerscited by 32
  22. 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
  23. 2023Approximation Rate of the Transformer Architecture for Sequence Modelingcited by 28
  24. 2021On the rate of convergence of a classifier based on a Transformer encodercited by 16
  25. 2021An Exponential Improvement on the Memorization Capacity of Deep Threshold Networkscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 16; 2025: 17; 2026: 14.

47 papers.

Sort:

By area:

  1. 2024Understanding Factual Recall in Transformers via Associative Memoriescited by 51
  2. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 40
  3. 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 36
  4. 2024What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Taskscited by 19
  5. 2024Attention layers provably solve single-location regressioncited by 17
  6. 2024Implicit Optimization Bias of Next-Token Prediction in Linear Modelscited by 14
  7. 2024How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear Regressioncited by 14
  8. 2025A Theoretical Analysis of Discrete Flow Matching Generative Modelscited by 14
  9. 2024Next-token prediction capacity: general upper bounds and a lower bound for transformerscited by 11
  10. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  11. 2024On the Benefits of Rank in Attention Layerscited by 5
  12. 2024Global Convergence in Training Large-Scale Transformerscited by 5
35 more
  1. 2025Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspectivecited by 5
  2. 2025Recurrent Self-Attention Dynamics: An Energy-Agnostic Perspective from Jacobianscited by 5
  3. 2024Dynamical Mean-Field Theory of Self-Attention Neural Networkscited by 4
  4. 2024On Expressive Power of Quantized Neural Networks under Fixed-Point Arithmeticcited by 4
  5. 2024On Generalisation Error Bounds for Transformerscited by 4
  6. 2025Approximation Bounds for Transformer Networks with Application to Regressioncited by 4
  7. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  8. 2025Memory Limitations of Prompt Tuning in Transformerscited by 4
  9. 2025The Effect of Attention Head Count on Transformer Approximationcited by 4
  10. 2024Differentially Private Kernel Density Estimationcited by 3
  11. 2025Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Sizecited by 3
  12. 2025Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)cited by 3
  13. 2025Exact Sequence Interpolation with Transformerscited by 2
  14. 2025A unified framework for establishing the universal approximation of transformer-type architecturescited by 2
  15. 2026Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unitycited by 2
  16. 2024Multiplicative Logit Adjustment Approximates Neural-Collapse-Aware Decision Boundary Adjustmentcited by 1
  17. 2025Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regimecited by 1
  18. 2025Universal Approximation Theorem for a Single-Layer Transformercited by 1
  19. 2025Analyzing the Power of Chain of Thought through Memorization Capabilitiescited by 1
  20. 2026Nonparametric Teaching of Attention Learnerscited by 1
  21. 2026On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functionscited by 1
  22. 2026Geometric Factual Recall in Transformerscited by 1
  23. 2026Diffusion Models for Adaptive Sequential Data Generationcited by 1
  24. 2026Attention-based representations for multi-task computationcited by 1
  25. 2026Training-Free Universal Approximation by Prompting Random Transformerscited by 1
  26. 2025Dynamic Relational Priming Improves Transformer in Multivariate Time Seriescited by 0
  27. 2025Performance-Efficiency Tradeoffs in Transformers: An Approximation Theory Perspectivecited by 0
  28. 2025On the Universality of Transformer Architectures; How Much Attention Is Enough?cited by 0
  29. 2026A Boltzmann-machine-enhanced Transformer For DNA Sequence Classificationcited by 0
  30. 2026Transformer Approximations from ReLUscited by 0
  31. 2026Approximation Error Upper and Lower Bounds for H"older Class with Transformerscited by 0
  32. 2026Why Do Aligned LLMs Remain Jailbreakable: Refusal-Escape Directions, Operator-Level Sources, and Safety-Utility Trade-offcited by 0
  33. 2026InfoFlow: A Framework for Multi-Layer Transformer Analysiscited by 0
  34. 2026How Many Different Outputs Can a Transformer Generate?cited by 0
  35. 2026Universal interpolation for deep residual self-attention networkscited by 0