mlsanityData to 14 Oct 2026

Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity

arXiv 2204.06618 ↗First posted 13 Apr 2022cs.CC cs.AI cs.CLcited by 93

Not on the map. Why?

Abstract (arXiv)

This paper analyzes three formal models of Transformer encoders that differ in the form of their self-attention mechanism: unique hard attention (UHAT); generalized unique hard attention (GUHAT), which generalizes UHAT; and averaging hard attention (AHAT). We show that UHAT and GUHAT Transformers, viewed as string acceptors, can only recognize formal languages in the complexity class AC0, the class of languages recognizable by families of Boolean circuits of constant depth and polynomial size. This upper bound subsumes Hahn's (2020) results that GUHAT cannot recognize the DYCK languages or the PARITY language, since those languages are outside AC0 (Furst et al., 1984). In contrast, the non-AC0 languages MAJORITY and DYCK-1 are recognizable by AHAT networks, implying that AHAT can recognize languages that UHAT and GUHAT cannot.

Key facts. Cited by 93 papers in the map (data through 14 Oct 2026). Builds on 7 of its 11 references that are in the map. First posted on arXiv 13 Apr 2022.

Builds on

7 of 11 references.

References · 7

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,026
  3. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  4. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  5. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  6. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  7. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 14; 2024: 27; 2025: 27; 2026: 19.

93 papers.

Sort:

By area:

  1. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  2. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  3. 2022Neural Networks and the Chomsky Hierarchycited by 217
  4. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  5. 2024The Illusion of State in State-Space Modelscited by 187
  6. 2023Representational Strengths and Limitations of Transformerscited by 133
  7. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  8. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 117
  9. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  10. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 70
  11. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  12. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 67
38 more
  1. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  2. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 64
  3. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 50
  4. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
  5. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
  6. 2022Autoregressive Structured Prediction with Language Modelscited by 43
  7. 2023Learning Transformer Programscited by 41
  8. 2024Memory3: Language Modeling with Explicit Memorycited by 40
  9. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
  10. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 37
  11. 2023Sparse Universal Transformercited by 32
  12. 2024Transformers Can Represent n-gram Language Modelscited by 32
  13. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  14. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  15. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  16. 2025Can Language Models Learn Typologically Implausible Languages?cited by 23
  17. 2024Provably learning a multi-head attention layercited by 21
  18. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  19. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  20. 2024Do Efficient Transformers Really Save Computation?cited by 20
  21. 2025Exact Expressive Power of Transformers with Paddingcited by 19
  22. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  23. 2025The Serial Scaling Hypothesiscited by 13
  24. 2025Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformerscited by 11
  25. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  26. 2025Circuit Complexity Bounds for Visual Autoregressive Modelcited by 10
  27. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  28. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  29. 2025The Counting Power of Transformerscited by 9
  30. 2024Transformers as Transducerscited by 8
  31. 2025Meta-Learning Neural Mechanisms rather than Bayesian Priorscited by 8
  32. 2025Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformerscited by 8
  33. 2026Why Are Linear RNNs More Parallelizable?cited by 8
  34. 2024Transformers are Expressive, But Are They Expressive Enough for Regression?cited by 6
  35. 2025Ehrenfeucht-Haussler Rank and Chain of Thoughtcited by 6
  36. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  37. 2025The Transformer Cookbookcited by 6
  38. 2025Diffusion Language Models are Provably Optimal Parallel Samplerscited by 6

50 most cited of 93 All 93 (JSON)