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

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

## 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 (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [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)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning](https://mlsanity.com/paper/2012.13255/) (2020)
- [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)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Visualizing and Measuring the Geometry of BERT](https://mlsanity.com/paper/1906.02715/) (2019)
- [ReLoRA: High-Rank Training Through Low-Rank Updates](https://mlsanity.com/paper/2307.05695/) (2023)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Low-Rank Bottleneck in Multi-head Attention Models](https://mlsanity.com/paper/2002.07028/) (2020)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [ResNet with one-neuron hidden layers is a Universal Approximator](https://mlsanity.com/paper/1806.10909/) (2018)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Your Transformer May Not be as Powerful as You Expect](https://mlsanity.com/paper/2205.13401/) (2022)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)

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

- [Understanding Factual Recall in Transformers via Associative Memories](https://mlsanity.com/paper/2412.06538/) (2024)
- [On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)](https://mlsanity.com/paper/2407.01079/) (2024)
- [On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding](https://mlsanity.com/paper/2410.01405/) (2024)
- [What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Tasks](https://mlsanity.com/paper/2404.01601/) (2024)
- [Attention layers provably solve single-location regression](https://mlsanity.com/paper/2410.01537/) (2024)
- [Implicit Optimization Bias of Next-Token Prediction in Linear Models](https://mlsanity.com/paper/2402.18551/) (2024)
- [How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear Regression](https://mlsanity.com/paper/2408.04532/) (2024)
- [A Theoretical Analysis of Discrete Flow Matching Generative Models](https://mlsanity.com/paper/2509.22623/) (2025)
- [Next-token prediction capacity: general upper bounds and a lower bound for transformers](https://mlsanity.com/paper/2405.13718/) (2024)
- [On the Optimal Memorization Capacity of Transformers](https://mlsanity.com/paper/2409.17677/) (2024)
- [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024)
- [Global Convergence in Training Large-Scale Transformers](https://mlsanity.com/paper/2410.23610/) (2024)
- [Transformers Can Overcome the Curse of Dimensionality: A Theoretical Study from an Approximation Perspective](https://mlsanity.com/paper/2504.13558/) (2025)
- [Recurrent Self-Attention Dynamics: An Energy-Agnostic Perspective from Jacobians](https://mlsanity.com/paper/2505.19458/) (2025)
- [Dynamical Mean-Field Theory of Self-Attention Neural Networks](https://mlsanity.com/paper/2406.07247/) (2024)
- [On Expressive Power of Quantized Neural Networks under Fixed-Point Arithmetic](https://mlsanity.com/paper/2409.00297/) (2024)
- [On Generalisation Error Bounds for Transformers](https://mlsanity.com/paper/2410.11500/) (2024)
- [Approximation Bounds for Transformer Networks with Application to Regression](https://mlsanity.com/paper/2504.12175/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Memory Limitations of Prompt Tuning in Transformers](https://mlsanity.com/paper/2509.00421/) (2025)
- [The Effect of Attention Head Count on Transformer Approximation](https://mlsanity.com/paper/2510.06662/) (2025)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size](https://mlsanity.com/paper/2502.11467/) (2025)
- [Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)](https://mlsanity.com/paper/2503.22076/) (2025)
- [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)
- [Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity](https://mlsanity.com/paper/2605.08811/) (2026)
- [Multiplicative Logit Adjustment Approximates Neural-Collapse-Aware Decision Boundary Adjustment](https://mlsanity.com/paper/2409.17582/) (2024)
- [Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regime](https://mlsanity.com/paper/2506.24120/) (2025)
- [Universal Approximation Theorem for a Single-Layer Transformer](https://mlsanity.com/paper/2507.10581/) (2025)

## 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.