mlsanityData to 14 Oct 2026

What Formal Languages Can Transformers Express? A Survey

arXiv 2311.00208 ↗First posted 1 Nov 2023cs.LG cs.CL cs.FLcited by 124

Not on the map. Why?

Abstract (arXiv)

As transformers have gained prominence in natural language processing, some researchers have investigated theoretically what problems they can and cannot solve, by treating problems as formal languages. Exploring such questions can help clarify the power of transformers relative to other models of computation, their fundamental capabilities and limits, and the impact of architectural choices. Work in this subarea has made considerable progress in recent years. Here, we undertake a comprehensive survey of this work, documenting the diverse assumptions that underlie different results and providing a unified framework for harmonizing seemingly contradictory findings.

Key facts. Cited by 124 papers in the map (data through 14 Oct 2026). Builds on 47 of its 99 references that are in the map. First posted on arXiv 1 Nov 2023.

Builds on

47 of 99 references.

References · 47

  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. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  5. 2016Layer Normalizationcited by 5,669
  6. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  7. 2016Gaussian Error Linear Units (GELUs)cited by 3,502
  8. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  9. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  10. 2021A Survey of Transformerscited by 401
  11. 2019Learning Deep Transformer Models for Machine Translationcited by 309
  12. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
35 more
  1. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  2. 2022Transformers Learn Shortcuts to Automatacited by 268
  3. 2022Neural Networks and the Chomsky Hierarchycited by 217
  4. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  5. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  6. 2021Thinking Like Transformerscited by 184
  7. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  8. 2023Representational Strengths and Limitations of Transformerscited by 133
  9. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  10. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  11. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  12. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  13. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 104
  14. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  15. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  16. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  17. 2022Formal Algorithms for Transformerscited by 72
  18. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 70
  19. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  20. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  21. 2020A Formal Hierarchy of RNN Architecturescited by 62
  22. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  23. 2020Limitations of Autoregressive Models and Their Alternativescited by 55
  24. 2019Sequential Neural Networks as Automatacited by 54
  25. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  26. 2019LSTM Networks Can Perform Dynamic Countingcited by 45
  27. 2023Entity Tracking in Language Modelscited by 44
  28. 2023Learning Transformer Programscited by 41
  29. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
  30. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
  31. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  32. 2020On the Linguistic Capacity of Real-Time Counter Automatacited by 17
  33. 2020A Survey of Neural Networks and Formal Languagescited by 17
  34. 2021Formal Language Theory Meets Modern NLPcited by 9
  35. 2018On learning an interpreted language with recurrent modelscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 24; 2025: 55; 2026: 45.

124 papers.

Sort:

By area:

  1. 2025CODI: Compressing Chain-of-Thought into Continuous Space via Self-Distillationcited by 225
  2. 2024The Illusion of State in State-Space Modelscited by 187
  3. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 101
  4. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  5. 2024A Mechanistic Analysis of a Transformer Trained on a Symbolic Multi-Step Reasoning Taskcited by 49
  6. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 46
  7. 2024Transformers are Universal In-context Learnerscited by 43
  8. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  9. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 37
  10. 2025(How) Do Language Models Track State?cited by 34
  11. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  12. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
38 more
  1. 2025Cramming 1568 Tokens into a Single Vector and Back Again: Exploring the Limits of Embedding Space Capacitycited by 28
  2. 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
  3. 2025Can Language Models Learn Typologically Implausible Languages?cited by 23
  4. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 23
  5. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 22
  6. 2024Mixture of Parrots: Experts improve memorization more than reasoningcited by 21
  7. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  8. 2025Constant Bit-size Transformers Are Turing Completecited by 19
  9. 2025Structured Sparse Transition Matrices to Enable State Tracking in State-Space Modelscited by 16
  10. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  11. 2025Constrained Decoding of Diffusion LLMs with Context-Free Grammarscited by 14
  12. 2025The Serial Scaling Hypothesiscited by 13
  13. 2025Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformerscited by 12
  14. 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 11
  15. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  16. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  17. 2024Relations, Negations, and Numbers: Looking for Logic in Generative Text-to-Image Modelscited by 9
  18. 2025Lost in Transmission: When and Why LLMs Fail to Reason Globallycited by 9
  19. 2025The Counting Power of Transformerscited by 9
  20. 2025Mechanistic evaluation of Transformers and state space modelscited by 9
  21. 2025Comprehension Without Competence: Architectural Limits of LLMs in Symbolic Computation and Reasoningcited by 9
  22. 2025Softmax Transformers are Turing-Completecited by 9
  23. 2024Transformers as Transducerscited by 8
  24. 2025Meta-Learning Neural Mechanisms rather than Bayesian Priorscited by 8
  25. 2025Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformerscited by 8
  26. 2025Sequential-Parallel Duality in Prefix Scannable Modelscited by 8
  27. 2025Fast weight programming and linear transformers: from machine learning to neurobiologycited by 8
  28. 2026Why Are Linear RNNs More Parallelizable?cited by 8
  29. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  30. 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
  31. 2025Transformers through the lens of support-preserving maps between measurescited by 6
  32. 2025The Transformer Cookbookcited by 6
  33. 2026Learning State-Tracking from Code Using Linear RNNscited by 6
  34. 2026Do Language Models Track Entities Across State Changes?cited by 6
  35. 2024Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoningcited by 5
  36. 2024Learning Linear Attention in Polynomial Timecited by 5
  37. 2024Quantifying artificial intelligence through algorithmic generalizationcited by 5
  38. 2025Can Large Language Models Learn Formal Logic? A Data-Driven Training and Evaluation Frameworkcited by 5

50 most cited of 124 All 124 (JSON)