mlsanityData to 14 Oct 2026

Representational Strengths and Limitations of Transformers

arXiv 2306.02896 ↗First posted 5 Jun 2023cs.LG stat.MLcited by 133

Not on the map. Why?

Abstract (arXiv)

Attention layers, as commonly used in transformers, form the backbone of modern deep learning, yet there is no mathematical description of their benefits and deficiencies as compared with other architectures. In this work we establish both positive and negative results on the representation power of attention layers, with a focus on intrinsic complexity parameters such as width, depth, and embedding dimension. On the positive side, we present a sparse averaging task, where recurrent networks and feedforward networks all have complexity scaling polynomially in the input size, whereas transformers scale merely logarithmically in the input size; furthermore, we use the same construction to show the necessity and role of a large embedding dimension in a transformer. On the negative side, we present a triple detection task, where attention layers in turn have complexity scaling linearly in the input size; as this scenario seems rare in practice, we also present natural variants that can be efficiently solved by attention layers. The proof techniques emphasize the value of communication complexity in the analysis of transformers and related models, and the role of sparse averaging as a prototypical attention task, which even finds use in the analysis of triple detection.

Key facts. Cited by 133 papers in the map (data through 14 Oct 2026). Builds on 30 of its 63 references that are in the map. First posted on arXiv 5 Jun 2023.

Builds on

30 of 63 references.

References · 30

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  4. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,248
  5. 2018How Powerful are Graph Neural Networks?cited by 4,393
  6. 2017Deep Setscited by 1,421
  7. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 1,003
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  9. 2020A Primer in BERTology: What we know about how BERT workscited by 815
  10. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  11. 2017A simple neural network module for relational reasoningcited by 346
  12. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
18 more
  1. 2022Transformers Learn Shortcuts to Automatacited by 268
  2. 2016Benefits of depth in neural networkscited by 250
  3. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  4. 2015The Power of Depth for Feedforward Neural Networkscited by 183
  5. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  6. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  7. 2019On the Universality of Invariant Networkscited by 152
  8. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  9. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  10. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  11. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  12. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  13. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 70
  14. 2021On the Expressive Power of Self-Attention Matricescited by 47
  15. 2017Depth Separation for Neural Networkscited by 46
  16. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 21
  17. 2022Exponential Separations in Symmetric Neural Networkscited by 10
  18. 2022CAT-probing: A Metric-based Approach to Interpret How Pre-trained Models for Programming Language Attend Code Structurecited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 14; 2024: 47; 2025: 43; 2026: 29.

133 papers.

Sort:

By area:

  1. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 832
  2. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 216
  3. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  4. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelscited by 191
  5. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  6. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  7. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  8. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 67
  9. 2024Position: Topological Deep Learning is the New Frontier for Relational Learningcited by 66
  10. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 64
  11. 2024Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challengescited by 64
  12. 2024On Limitations of the Transformer Architecturecited by 63
38 more
  1. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 46
  2. 2024Theoretical limitations of multi-layer Transformercited by 45
  3. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  4. 2024An Information-Theoretic Analysis of In-Context Learningcited by 40
  5. 2023On the Optimization and Generalization of Multi-head Attentioncited by 37
  6. 2024One-layer transformers fail to solve the induction heads taskcited by 32
  7. 2024Implicit Bias and Fast Convergence Rates for Self-attentioncited by 31
  8. 2024How Much Can RAG Help the Reasoning of LLM?cited by 31
  9. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 30
  10. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  11. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 30
  12. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  13. 2025Cramming 1568 Tokens into a Single Vector and Back Again: Exploring the Limits of Embedding Space Capacitycited by 28
  14. 2024Transformers on Markov Data: Constant Depth Sufficescited by 27
  15. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  16. 2024Prompting a Pretrained Transformer Can Be a Universal Approximatorcited by 25
  17. 2024BeHonest: Benchmarking Honesty in Large Language Modelscited by 24
  18. 2024When Can Transformers Count to n?cited by 24
  19. 2024In-Context Learning with Transformers: Softmax Attention Adapts to Function Lipschitznesscited by 22
  20. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 22
  21. 2024Sample, estimate, aggregate: A recipe for causal discovery foundation modelscited by 21
  22. 2024Provably learning a multi-head attention layercited by 21
  23. 2025Density Measures for Language Generationcited by 21
  24. 2024Do Efficient Transformers Really Save Computation?cited by 20
  25. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  26. 2024Evaluation of LLM Chatbots for OSINT-based Cyber Threat Awarenesscited by 14
  27. 2025Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizationscited by 13
  28. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 12
  29. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  30. 2025Strassen Attention, Split VC Dimension and Compositionality in Transformerscited by 12
  31. 2024Next-token prediction capacity: general upper bounds and a lower bound for transformerscited by 11
  32. 2025Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformerscited by 11
  33. 2024On the Optimal Memorization Capacity of Transformerscited by 10
  34. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 10
  35. 2026Sequential Group Composition: A Window into the Mechanics of Deep Learningcited by 10
  36. 2023Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regressioncited by 9
  37. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  38. 2024Training Dynamics of Transformers to Recognize Word Co-occurrence via Gradient Flow Analysiscited by 9

50 most cited of 133 All 133 (JSON)