mlsanityData to 7 Oct 2026

Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits

arXiv 2308.03212 ↗First posted 6 Aug 2023cs.CL cs.CC cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

Transformers have emerged as a widely used neural network model for various natural language processing tasks. Previous research explored their relationship with constant-depth threshold circuits, making two assumptions: average-hard attention and logarithmic precision for internal computations relative to input length. Merrill et al. (2022) prove that average-hard attention transformers recognize languages that fall within the complexity class TC0, denoting the set of languages that can be recognized by constant-depth polynomial-size threshold circuits. Likewise, Merrill and Sabharwal (2023) show that log-precision transformers recognize languages within the class of uniform TC0. This shows that both transformer models can be simulated by constant-depth threshold circuits, with the latter being more robust due to generating a uniform circuit family. Our paper shows that the first result can be extended to yield uniform circuits as well.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 6 of its 7 references that are in the map. First posted on arXiv 6 Aug 2023.

Builds on

6 of 7 references.

References · 6

  1. 2017Attention Is All You Needcited by 59,932
  2. 2022Transformers Learn Shortcuts to Automatacited by 260
  3. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  4. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  5. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  6. 2018Rational Recurrencescited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 7; 2025: 11; 2026: 7.

26 papers.

Sort:

By area:

  1. 2025Hierarchical Reasoning Modelcited by 167
  2. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  3. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  4. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  5. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  6. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  7. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  8. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  9. 2024Position: An Inner Interpretability Framework for AI Inspired by Lessons from Cognitive Neurosciencecited by 11
  10. 2025Language models can learn implicit multi-hop reasoning, but only if they have lots of training datacited by 11
  11. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  12. 2025Lost in Transmission: When and Why LLMs Fail to Reason Globallycited by 9
14 more
  1. 2024Logicbreaks: A Framework for Understanding Subversion of Rule-based Inferencecited by 3
  2. 2026Context-Free Recognition with Transformerscited by 3
  3. 2025Is In-Context Learning Learning?cited by 2
  4. 2024Theoretical Analysis of Hierarchical Language Recognition and Generation by Transformers without Positional Encodingcited by 1
  5. 2025Three tiers of computation in transformers and in brain architecturescited by 1
  6. 2025Can Test-time Computation Mitigate Reproduction Bias in Neural Symbolic Regression?cited by 1
  7. 2025Realizable Circuit Complexity: Embedding Computation in Space-Timecited by 1
  8. 2026On the Ability of Transformers to Verify Planscited by 1
  9. 2025BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoningcited by 0
  10. 2026Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformerscited by 0
  11. 2026Average Attention Transformers and Arithmetic Circuitscited by 0
  12. 2026A First-Principles Theory of Slow Thinking and Active Perceptioncited by 0
  13. 2026On the Expressive Power of Transformerscited by 0
  14. 2026Hidden Reasoning Must Leak, but Need Not Be Readable: Fundamental Opportunities and Limits for Chain-of-Thought Monitoringcited by 0