mlsanityData to 14 Oct 2026

Tighter Bounds on the Expressivity of Transformer Encoders

arXiv 2301.10743 ↗First posted 25 Jan 2023cs.LG cs.FL cs.LOcited by 66

Not on the map. Why?

Abstract (arXiv)

Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform TC0. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.

Key facts. Cited by 66 papers in the map (data through 14 Oct 2026). Builds on 16 of its 32 references that are in the map. First posted on arXiv 25 Jan 2023.

Builds on

16 of 32 references.

References · 16

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Layer Normalizationcited by 5,669
  3. 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
  4. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  5. 2019Learning Deep Transformer Models for Machine Translationcited by 309
  6. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  7. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  8. 2021Thinking Like Transformerscited by 184
  9. 2019Transformers without Tears: Improving the Normalization of Self-Attentioncited by 153
  10. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  11. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  12. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 104
4 more
  1. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  2. 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
  3. 2020On the Linguistic Capacity of Real-Time Counter Automatacited by 17
  4. 2018SoPa: Bridging CNNs, RNNs, and Weighted Finite-State Machinescited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 10; 2024: 24; 2025: 14; 2026: 18.

66 papers.

Sort:

By area:

  1. 2023Large Language Modelscited by 780
  2. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
  3. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  4. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 216
  5. 2024The Illusion of State in State-Space Modelscited by 187
  6. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  7. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  8. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 53
  9. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 50
  10. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
  11. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 46
  12. 2024Transformers are Universal In-context Learnerscited by 43
38 more
  1. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  2. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
  3. 2024Transformers Can Represent n-gram Language Modelscited by 32
  4. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  5. 2024Measure-to-measure interpolation using Transformerscited by 29
  6. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  7. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  8. 2023Do pretrained Transformers Learn In-Context by Gradient Descent?cited by 18
  9. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  10. 2024An Examination on the Effectiveness of Divide-and-Conquer Prompting in Large Language Modelscited by 12
  11. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  12. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  13. 2024ALTA: Compiler-Based Analysis of Transformerscited by 7
  14. 2024Strong hallucinations from negation and how to fix themcited by 6
  15. 2024Transformers are Expressive, But Are They Expressive Enough for Regression?cited by 6
  16. 2025Ehrenfeucht-Haussler Rank and Chain of Thoughtcited by 6
  17. 2025Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformerscited by 6
  18. 2025Transformers through the lens of support-preserving maps between measurescited by 6
  19. 2025The Transformer Cookbookcited by 6
  20. 2024Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoningcited by 5
  21. 2024GUNDAM: Aligning Large Language Models with Graph Understandingcited by 5
  22. 2024Learning Linear Attention in Polynomial Timecited by 5
  23. 2026Parity, Sensitivity, and Transformerscited by 5
  24. 2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
  25. 2025Efficient Turing Machine Simulation with Transformerscited by 4
  26. 2025Rectifying LLM Thought from Lens of Optimizationcited by 4
  27. 2026Length Generalization Bounds for Transformerscited by 4
  28. 2023State space models can express n-gram languagescited by 3
  29. 2026Characterizing the Expressivity of Local Attention in Transformerscited by 3
  30. 2026Continuous Latent Contexts Enable Efficient Online Learning in Transformerscited by 3
  31. 2023Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languagescited by 2
  32. 2024A Transformer with Stack Attentioncited by 2
  33. 2025Deciphering Trajectory-Aided LLM Reasoning: An Optimization Perspectivecited by 2
  34. 2025Expressive Power of Graph Transformers via Logiccited by 2
  35. 2025Topos Theory for Generative AI and LLMscited by 2
  36. 2026SymTorch: Symbolic Distillation of Neural Networkscited by 2
  37. 2026Measure-to-measure Regression with Transformerscited by 2
  38. 2026Indexing: the Beginning and the Endcited by 2

50 most cited of 66 All 66 (JSON)