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

arXiv: https://arxiv.org/abs/2308.03212 · HTML: https://mlsanity.com/paper/2308.03212/

## Key facts

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

## Builds on (most cited first, 6 of 6)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Rational Recurrences](https://mlsanity.com/paper/1808.09357/) (2018)

## Built on by (most cited first, 26 of 26)

- [Hierarchical Reasoning Model](https://mlsanity.com/paper/2506.21734/) (2025)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [Position: An Inner Interpretability Framework for AI Inspired by Lessons from Cognitive Neuroscience](https://mlsanity.com/paper/2406.01352/) (2024)
- [Language models can learn implicit multi-hop reasoning, but only if they have lots of training data](https://mlsanity.com/paper/2505.17923/) (2025)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)
- [Lost in Transmission: When and Why LLMs Fail to Reason Globally](https://mlsanity.com/paper/2505.08140/) (2025)
- [Logicbreaks: A Framework for Understanding Subversion of Rule-based Inference](https://mlsanity.com/paper/2407.00075/) (2024)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [Is In-Context Learning Learning?](https://mlsanity.com/paper/2509.10414/) (2025)
- [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026)
- [Theoretical Analysis of Hierarchical Language Recognition and Generation by Transformers without Positional Encoding](https://mlsanity.com/paper/2410.12413/) (2024)
- [Three tiers of computation in transformers and in brain architectures](https://mlsanity.com/paper/2503.04848/) (2025)
- [Can Test-time Computation Mitigate Reproduction Bias in Neural Symbolic Regression?](https://mlsanity.com/paper/2505.22081/) (2025)
- [Realizable Circuit Complexity: Embedding Computation in Space-Time](https://mlsanity.com/paper/2509.19161/) (2025)
- [Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers](https://mlsanity.com/paper/2602.02707/) (2026)
- [BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoning](https://mlsanity.com/paper/2507.23170/) (2025)
- [Average Attention Transformers and Arithmetic Circuits](https://mlsanity.com/paper/2605.04683/) (2026)
- [A First-Principles Theory of Slow Thinking and Active Perception](https://mlsanity.com/paper/2607.08196/) (2026)
- [On the Expressive Power of Transformers](https://mlsanity.com/paper/2608.12671/) (2026)
- [Hidden Reasoning Must Leak, but Need Not Be Readable: Fundamental Opportunities and Limits for Chain-of-Thought Monitoring](https://mlsanity.com/paper/2609.37312/) (2026)

## 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.