# Transformers in Uniform TC0

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2024.

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

- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Exact Expressive Power of Transformers with Padding](https://mlsanity.com/paper/2505.18948/) (2025)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problems](https://mlsanity.com/paper/2412.05562/) (2024)
- [Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers](https://mlsanity.com/paper/2505.21024/) (2025)
- [Why Are Linear RNNs More Parallelizable?](https://mlsanity.com/paper/2603.03612/) (2026)
- [Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria](https://mlsanity.com/paper/2508.07102/) (2025)
- [Certifiable Boolean Reasoning Is Universal](https://mlsanity.com/paper/2602.05120/) (2026)
- [On the Existence of Universal Simulators of Attention](https://mlsanity.com/paper/2506.18739/) (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)
- [Rational Transductors](https://mlsanity.com/paper/2602.07599/) (2026)
- [Dynamical Systems Theory Behind a Hierarchical Reasoning Model](https://mlsanity.com/paper/2603.22871/) (2026)
- [Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't](https://mlsanity.com/paper/2605.30523/) (2026)
- [Comparing Transformers and Hybrid Models at the Token Level](https://mlsanity.com/paper/2606.20936/) (2026)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)
- [Semantic Content Determines Algorithmic Performance](https://mlsanity.com/paper/2601.21618/) (2026)
- [Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits](https://mlsanity.com/paper/2602.03970/) (2026)
- [How Many Different Outputs Can a Transformer Generate?](https://mlsanity.com/paper/2605.22223/) (2026)
- [Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization](https://mlsanity.com/paper/2605.22964/) (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)
- [Length Generalization for Transformers via Compression](https://mlsanity.com/paper/2609.08851/) (2026)

## Abstract (arXiv)

Previous work has shown that the languages recognized by average-hard attention transformers (AHATs) and softmax-attention transformers (SMATs) are within the circuit complexity class TC0. However, these results assume limited-precision arithmetic: using floating-point numbers with O(log n) bits (where n is the length of the input string), Strobl showed that AHATs can be approximated in L-uniform TC0, and Merrill and Sabharwal showed that SMATs can be approximated in DLOGTIME-uniform TC0. Here, we improve these results, showing that AHATs with no approximation, SMATs with O(poly(n)) bits of floating-point precision, and SMATs with at most 2-O(poly(n)) absolute error are all in DLOGTIME-uniform TC0.