mlsanityData to 7 Oct 2026

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

arXiv 2307.11353 ↗First posted 21 Jul 2023cs.LG math.ST stat.MLcited by 39

Not on the map. Why?

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.

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

Builds on

82 of 107 references.

References · 82

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,456
  4. 2020Language Models are Few-Shot Learnerscited by 32,199
  5. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  6. 2023GPT-4 Technical Reportcited by 18,132
  7. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  8. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  9. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  10. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  11. 2022In-context Learning and Induction Headscited by 930
  12. 2021An Explanation of In-context Learning as Implicit Bayesian Inferencecited by 915
38 more
  1. 2022A Generalist Agentcited by 802
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2022Transformers learn in-context by gradient descentcited by 714
  4. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  5. 2018On Lazy Training in Differentiable Programmingcited by 671
  6. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  8. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  9. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  10. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  11. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  12. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  13. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  14. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  15. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  16. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  17. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  18. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  19. 2022Transformers Learn Shortcuts to Automatacited by 260
  20. 2023Looped Transformers as Programmable Computerscited by 224
  21. 2020How Neural Networks Extrapolate: From Feedforward to Graph Neural Networkscited by 218
  22. 2016A Decomposable Attention Model for Natural Language Inferencecited by 214
  23. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  24. 2021Thinking Like Transformerscited by 182
  25. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  26. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  27. 2016Generalization Properties of Learning with Random Featurescited by 163
  28. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  29. 2019Linearized two-layers neural networks in high dimensioncited by 155
  30. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  31. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  32. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  33. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  34. 2020Tensor Programs II: Neural Tangent Kernel for Any Architecturecited by 139
  35. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  36. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  37. 2020Infinite attention: NNGP and NTK for deep attention networkscited by 117
  38. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110

50 most cited of 82 All 82 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 18; 2025: 10; 2026: 7.

39 papers.

Sort:

By area:

  1. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  2. 2023Transformers as Support Vector Machinescited by 67
  3. 2023Replacing softmax with ReLU in Vision Transformerscited by 43
  4. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 39
  5. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  6. 2024Mechanics of Next Token Prediction with Self-Attentioncited by 34
  7. 2024A phase transition between positional and semantic learning in a solvable model of dot-product attentioncited by 30
  8. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 28
  9. 2024Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamicscited by 27
  10. 2024In-Context Learning with Transformers: Softmax Attention Adapts to Function Lipschitznesscited by 22
  11. 2024Provably learning a multi-head attention layercited by 21
  12. 2024What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Taskscited by 19
27 more
  1. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  2. 2024Towards Understanding Inductive Bias in Transformers: A View From Infinitycited by 13
  3. 2024A Survey to Recent Progress Towards Understanding In-Context Learningcited by 12
  4. 2024Attention Meets Post-hoc Interpretability: A Mathematical Perspectivecited by 11
  5. 2025Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformerscited by 10
  6. 2024Dissecting the Interplay of Attention Paths in a Statistical Mechanics Theory of Transformerscited by 9
  7. 2024Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Featurescited by 5
  8. 2024Learning Linear Attention in Polynomial Timecited by 5
  9. 2024Global Convergence in Training Large-Scale Transformerscited by 5
  10. 2024On the Benefits of Rank in Attention Layerscited by 4
  11. 2025Tensor Sketch: Fast and Scalable Polynomial Kernel Approximationcited by 4
  12. 2026ZeroS: Zero-Sum Linear Attention for Efficient Transformerscited by 4
  13. 2025Bayes optimal learning of attention-indexed modelscited by 3
  14. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 2
  15. 2025How Can Mamba Learn In Context with Outliers and Generalize Provably?cited by 2
  16. 2026Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridgecited by 2
  17. 2024Learning Expressive Random Feature Models via Parametrized Activationscited by 1
  18. 2025On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functionscited by 1
  19. 2026Algebraic Invariants of Lightning Self-Attentioncited by 1
  20. 2026On the global convergence of gradient flow for wide shallow models beyond homogeneous nonlinearitiescited by 1
  21. 2026Transformers Provably Learn to Internalize Chain-of-Thoughtcited by 1
  22. 2025Softplus Attention with Re-weighting Boosts Length Extrapolation in Large Language Modelscited by 0
  23. 2025Theoretical Foundations of Representation Learning using Unlabeled Data: Statistics and Optimizationcited by 0
  24. 2025Minimax Rates for Learning Pairwise Interactions in Attention-Style Modelscited by 0
  25. 2025One-Bit Quantization for Random Features Modelscited by 0
  26. 2026A Decision-Theoretic View of Test-Time Training: When, How Far, and Which Directions to Adaptcited by 0
  27. 2026When Can Attention Heads Be Statically Defined?cited by 0