mlsanityData to 7 Oct 2026

Saturated Transformers are Constant-Depth Threshold Circuits

arXiv 2106.16213 ↗First posted 30 Jun 2021cs.CL cs.CC cs.LGcited by 137

Not on the map. Why?

Cited by 23 in LLM reasoning, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Transformers have become a standard neural network architecture for many NLP problems, motivating theoretical analysis of their power in terms of formal languages. Recent work has shown that transformers with hard attention are quite limited in power (Hahn, 2020), as they can be simulated by constant-depth AND/OR circuits (Hao et al. 2021). However, hard attention is a strong assumption, which may complicate the relevance of these results in practice. In this work, we analyze the circuit complexity of transformers with saturated attention: a generalization of hard attention that more closely captures the attention patterns learnable in practical transformers. We first show that saturated transformers transcend the known limitations of hard-attention transformers. We then prove saturated transformers with floating-point values can be simulated by constant-depth threshold circuits, giving the class mathsfTC0 as an upper bound on the formal languages they recognize.

Key facts. Cited by 137 papers in the map (data through 7 Oct 2026). Builds on 14 of its 32 references that are in the map. First posted on arXiv 30 Jun 2021.

Builds on

14 of 32 references.

References · 14

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2016Layer Normalizationcited by 5,579
  4. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  5. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  6. 2021Thinking Like Transformerscited by 182
  7. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  8. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  9. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  10. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  11. 2019Sequential Neural Networks as Automatacited by 54
  12. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
2 more
  1. 2018Rational Recurrencescited by 18
  2. 2021Formal Language Theory Meets Modern NLPcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 23; 2024: 37; 2025: 38; 2026: 34.

137 papers.

Sort:

By area:

  1. 2023Large Language Modelscited by 774
  2. 2022Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thoughtcited by 334
  3. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  4. 2023Looped Transformers as Programmable Computerscited by 224
  5. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 208
  6. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  7. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  8. 2023Birth of a Transformer: A Memory Viewpointcited by 154
  9. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  10. 2024Secret Collusion among AI Agents: Multi-Agent Deception via Steganographycited by 107
  11. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 99
  12. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
38 more
  1. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  2. 2025Nested Learning: The Illusion of Deep Learning Architecturescited by 69
  3. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  4. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  5. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  6. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  7. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
  8. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 62
  9. 2023Grokking of Hierarchical Structure in Vanilla Transformerscited by 53
  10. 2024A Mechanistic Analysis of a Transformer Trained on a Symbolic Multi-Step Reasoning Taskcited by 49
  11. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  12. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  13. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 47
  14. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 46
  15. 2023An Over-parameterized Exponential Regressioncited by 45
  16. 2023Learning Transformer Programscited by 40
  17. 2023The Impact of Depth on Compositional Generalization in Transformer Language Modelscited by 37
  18. 2024Transformers Can Represent n-gram Language Modelscited by 31
  19. 2025(How) Do Language Models Track State?cited by 31
  20. 2025Next-Latent Prediction Transformers Learn Compact World Modelscited by 29
  21. 2023Sparse Universal Transformercited by 28
  22. 2025MUDDFormer: Breaking Residual Bottlenecks in Transformers via Multiway Dynamic Dense Connectionscited by 27
  23. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  24. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  25. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  26. 2024Mechanistic?cited by 25
  27. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  28. 2024Provably learning a multi-head attention layercited by 21
  29. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  30. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21
  31. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  32. 2024Do Efficient Transformers Really Save Computation?cited by 20
  33. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  34. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 20
  35. 2024Why do small language models underperform? Studying Language Model Saturation via the Softmax Bottleneckcited by 19
  36. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  37. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  38. 2023Do pretrained Transformers Learn In-Context by Gradient Descent?cited by 18

50 most cited of 137 All 137 (JSON)