# What can a Single Attention Layer Learn? A Study Through the Random Features Lens

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 82 of its 107 references that are in the map.
- First posted on arXiv 21 Jul 2023.

## Builds on (most cited first, 30 of 82)

- [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)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [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)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [An Explanation of In-context Learning as Implicit Bayesian Inference](https://mlsanity.com/paper/2111.02080/) (2021)
- [A Generalist Agent](https://mlsanity.com/paper/2205.06175/) (2022)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)

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

- [Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretraining](https://mlsanity.com/paper/2310.08566/) (2023)
- [Transformers as Support Vector Machines](https://mlsanity.com/paper/2308.16898/) (2023)
- [Replacing softmax with ReLU in Vision Transformers](https://mlsanity.com/paper/2309.08586/) (2023)
- [Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains](https://mlsanity.com/paper/2402.04161/) (2024)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Mechanics of Next Token Prediction with Self-Attention](https://mlsanity.com/paper/2403.08081/) (2024)
- [A phase transition between positional and semantic learning in a solvable model of dot-product attention](https://mlsanity.com/paper/2402.03902/) (2024)
- [Sequence Length Independent Norm-Based Generalization Bounds for Transformers](https://mlsanity.com/paper/2310.13088/) (2023)
- [Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics](https://mlsanity.com/paper/2405.04669/) (2024)
- [In-Context Learning with Transformers: Softmax Attention Adapts to Function Lipschitzness](https://mlsanity.com/paper/2402.11639/) (2024)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Tasks](https://mlsanity.com/paper/2404.01601/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [A Survey to Recent Progress Towards Understanding In-Context Learning](https://mlsanity.com/paper/2402.02212/) (2024)
- [Towards Understanding Inductive Bias in Transformers: A View From Infinity](https://mlsanity.com/paper/2402.05173/) (2024)
- [Attention Meets Post-hoc Interpretability: A Mathematical Perspective](https://mlsanity.com/paper/2402.03485/) (2024)
- [Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformers](https://mlsanity.com/paper/2506.10887/) (2025)
- [Dissecting the Interplay of Attention Paths in a Statistical Mechanics Theory of Transformers](https://mlsanity.com/paper/2405.15926/) (2024)
- [Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Features](https://mlsanity.com/paper/2402.02969/) (2024)
- [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024)
- [Learning Linear Attention in Polynomial Time](https://mlsanity.com/paper/2410.10101/) (2024)
- [Global Convergence in Training Large-Scale Transformers](https://mlsanity.com/paper/2410.23610/) (2024)
- [ZeroS: Zero-Sum Linear Attention for Efficient Transformers](https://mlsanity.com/paper/2602.05230/) (2026)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspective](https://mlsanity.com/paper/2503.11272/) (2025)
- [Bayes optimal learning of attention-indexed models](https://mlsanity.com/paper/2506.01582/) (2025)
- [How Can Mamba Learn In Context with Outliers and Generalize Provably?](https://mlsanity.com/paper/2510.00399/) (2025)
- [Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridge](https://mlsanity.com/paper/2602.02470/) (2026)
- [Transformers Provably Learn to Internalize Chain-of-Thought](https://mlsanity.com/paper/2605.28600/) (2026)
- [Learning Expressive Random Feature Models via Parametrized Activations](https://mlsanity.com/paper/2411.19468/) (2024)

## Abstract (arXiv)

Attention layers -- which map a sequence of inputs to a sequence of outputs -- are core building blocks of the Transformer architecture which has achieved significant breakthroughs in modern artificial intelligence. This paper presents a rigorous theoretical study on the learning and generalization of a single multi-head attention layer, with a sequence of key vectors and a separate query vector as input. We consider the random feature setting where the attention layer has a large number of heads, with randomly sampled frozen query and key matrices, and trainable value matrices. We show that such a random-feature attention layer can express a broad class of target functions that are permutation invariant to the key vectors. We further provide quantitative excess risk bounds for learning these target functions from finite samples, using random feature attention with finitely many heads. Our results feature several implications unique to the attention structure compared with existing random features theory for neural networks, such as (1) Advantages in the sample complexity over standard two-layer random-feature networks; (2) Concrete and natural classes of functions that can be learned efficiently by a random-feature attention layer; and (3) The effect of the sampling distribution of the query-key weight matrix (the product of the query and key matrix), where Gaussian random weights with a non-zero mean result in better sample complexities over the zero-mean counterpart for learning certain natural target functions. Experiments on simulated data corroborate our theoretical findings and further illustrate the interplay between the sample size and the complexity of the target function.