Saturated Transformers are Constant-Depth Threshold Circuits
Open accessAbstract
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., 2022). 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 TC0 as an upper bound on the formal languages they recognize.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Standard transformers, even with ideal parameters, cannot perfectly solve many sequential reasoning problems at scale, such as simulating finite-state machines, deciding whether nodes in a graph are connected, or solving matrix equalities.
“They have shown that standard transformers, even with ideal parameters, cannot perfectly solve many sequential reasoning problems at scale, such as simulating finite-state machines, deciding whether nodes in a graph are connected, or solving matrix equalities.”
From The expressive power of transformers with chain of thought (2023) · cites this paper as Merrill et al., 2022
Section 2 (Roadmap) says that saturated transformers with floating-point values can recognize only languages in TC0, supporting a qualified limit on their computational power. But §4 (Circuit Complexity) says it is unknown whether TC0 contains all regular languages, and the paper does not establish that transformers cannot solve the listed finite-state, graph-connectivity, or matrix-equality tasks. The claim turns a model-specific upper bound into categorical impossibility claims about standard transformers. (LLM, conf=0.88)
Experimental — accuracy not yet measuredMerrill et al. (2022) studied a binary-only version of the mode task and demonstrated strong length generalization.
“Merrill et al. (2022) studied a binary-only version of this task and demonstrated strong length generalization.”
From What Algorithms can Transformers Learn? A Study in Length Generalization (2023) · cites this paper as Merrill et al. (2022)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017) · arXiv · doi:10.48550/arxiv.1706.03762 · Cited by 120,404 · see citing works
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019) · Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) · doi:10.18653/v1/n19-1423 · Cited by 48,293 · see citing works
Advances in Neural Information Processing Systems 29
Teymur, O., Zygalakis, K., & Calderhead, B. (2016) · Cited by 13,881 · see citing works
Layer NormalizationPreprint
Ba, J., Kiros, J., & Hinton, G. E. (2016) · arXiv.org · doi:10.48550/arxiv.1607.06450 · Cited by 13,745 · see citing works
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690 · see citing works
A Catalog of Complexity Classes
Johnson, D. S. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50007-2 · Cited by 578 · see citing works
Machine Models and Simulations
Boas, P. V. E. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50006-0 · Cited by 248 · see citing works
On the Practical Computational Power of Finite Precision RNNs for Language Recognition
Weiss, G., Goldberg, Y., & Yahav, E. (2018) · Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) · doi:10.18653/v1/p18-2117 · Cited by 226 · see citing works
Parity, circuits, and the polynomial-time hierarchy
Furst, M. L., Saxe, J. B., & Sipser, M. (1981) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1981.35 · Cited by 212 · see citing works
On the Turing Completeness of Modern Neural Network ArchitecturesPreprint
Pérez, J., Marinkovic, J., & Barceló, P. (2019) · International Conference on Learning Representations · doi:10.48550/arxiv.1901.03429 · Cited by 187 · see citing works
Theoretical Limitations of Self-Attention in Neural Sequence Models
Hahn, M. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00306 · Cited by 165 · see citing works
Are Transformers universal approximators of sequence-to-sequence functions?Preprint
Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., & Kumar, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.10077 · Cited by 149 · see citing works
Sequential Neural Networks as Automata
Merrill, W. (2019) · Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges · doi:10.18653/v1/w19-3901 · Cited by 54 · see citing works
Self-citationOn the Ability and Limitations of Transformers to Recognize Formal Languages
Bhattamishra, S., Ahuja, K., & Goyal, N. (2020) · Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.576 · Cited by 48 · see citing works
A History of the Prime Number Theorem
Goldstein, L. J. (1973) · American Mathematical Monthly · doi:10.1080/00029890.1973.11993338 · Cited by 45 · see citing works
Peng, H., Schwartz, R., Thomson, S., & Smith, N. A. (2018) · Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/d18-1152 · Cited by 41 · see citing works
Self-citationProceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP
Alishahi, A., Belinkov, Y., Chrupała, G., Hupkes, D., Pinter, Y., & Sajjad, H. (2020) · doi:10.18653/v1/2020.blackboxnlp-1 · Cited by 35 · see citing works
RNNs can generate bounded hierarchical languages with optimal memory
Hewitt, J., Hahn, M., Ganguli, S., Liang, P., & Manning, C. D. (2020) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2020.emnlp-main.156 · Cited by 30 · see citing works
Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity
Hao, Y., Angluin, D., & Frank, R. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00490 · Cited by 27 · see citing works
Self-Attention Networks Can Process Bounded Hierarchical Languages
Yao, S., Peng, B., Papadimitriou, C. H., & Narasimhan, K. (2021) · Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/2021.acl-long.292 · Cited by 24 · see citing works
Weiss, G., Goldberg, Y., & Yahav, E. (2021) · arXiv · doi:10.48550/arxiv.2106.06981 · Cited by 18 · see citing works
Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent
Merrill, W., Ramanujan, V., Goldberg, Y., Schwartz, R., & Smith, N. A. (2021) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2021.emnlp-main.133 · Cited by 17 · see citing works
Self-citationPolynomial Size Log Depth Circuits: Between NC 1 and AC 1 .
Mahajan, M. (2007) · Cited by 9 · see citing works
Formal Language Theory Meets Modern NLPPreprint
Merrill, W. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.10094 · Cited by 8 · see citing works
Self-citation
Flagged first, then by citations
2 of the 28 references couldn’t be matched to a known paper.
Research works printed but not linked: 1
- Liliana Cojocaru. 2016. Advanced Studies on the Complexity of Formal Languages. Ph.D. thesis, University of Tampere.
Cited by
Sorted by citations
What Formal Languages Can Transformers Express? A Survey
Strobl, L., Merrill, W., Weiss, G., Chiang, D., & Angluin, D. (2024) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00663 · Cited by 31 · see citing works
Self-citationFormal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity
Hao, Y., Angluin, D., & Frank, R. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00490 · Cited by 27 · see citing works
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
Merrill, W., & Sabharwal, A. (2023) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00562 · Cited by 22 · see citing works
Self-citation(2023) · doi:10.18653/v1/2023.acl-short.38 · Cited by 12 · see citing works
Characterizing In-Context Learning: When Can Transformers Match Standard Learning Algorithms?
Hawarey, M. (2026) · doi:10.65737/airmcs2026277 · Cited by 11 · see citing works
Tan, S., Shen, Y., Chen, Z., Courville, A. C., & Gan, C. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.12 · Cited by 11 · see citing works
What Algorithms can Transformers Learn? A Study in Length Generalization
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., & Nakkiran, P. (2023) · arXiv · doi:10.48550/arxiv.2310.16028 · Cited by 10 · see citing works
“…which functions are possible to represent by a Transformer 10 , but this representation is not always “simple” enough to be learnable, and not always uniform (Hahn, 2020; Merrill et al., 2022; Chiang & Cholak, 2022; Pérez et al., 2021; Bhattamishra et al., 2020; Ebrahimi et al., 2020).”
BackgroundSimplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions
Bhattamishra, S., Patel, A., Kanade, V., & Blunsom, P. (2023) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2023.acl-long.317 · Cited by 10 · see citing works
Provably Learning a Multi-head Attention Layer
Chen, S., & Li, Y. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718174 · Cited by 6 · see citing works
Do Transformers Parse while Predicting the Masked Word?
Zhao, H., Panigrahi, A., Ge, R., & Arora, S. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.1029 · Cited by 6 · see citing works
The expressive power of transformers with chain of thought
Merrill, W., & Sabharwal, A. (2023) · arXiv · doi:10.48550/arxiv.2310.07923 · Cited by 4 · see citing works
Self-citationZoology: Measuring and Improving Recall in Efficient Language Models
Arora, S., Eyuboglu, S., Timalsina, A., Johnson, I., Poli, M., Zou, J., Rudra, A., & Ré, C. (2023) · arXiv · doi:10.48550/arxiv.2312.04927 · Cited by 4 · see citing works
Strobl, L., Angluin, D., Chiang, D., Rawski, J., & Sabharwal, A. (2025) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00736 · Cited by 4 · see citing works
Self-citationRepeat After Me: Transformers are Better than State Space Models at Copying
Jelassi, S., Brandfonbrener, D., Kakade, S. M., & Malach, E. (2024) · arXiv · doi:10.48550/arxiv.2402.01032 · Cited by 3 · see citing works
Irie, K., Csordás, R., & Schmidhuber, J. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.588 · Cited by 3 · see citing works
de Oliveira, M., Subramanian, S., Mendes, L. R. D. S., & Hsieh, M.-H. (2025) · Nature Communications · doi:10.1038/s41467-025-58545-4 · Cited by 3 · see citing works
Improved Linear Decomposition of Majority and Threshold Boolean Functions
Chattopadhyay, A., Bhattacharjee, D., & Maitra, S. (2023) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2023.3257082 · Cited by 3 · see citing works
Evaluating Transformer’s Ability to Learn Mildly Context-Sensitive Languages
Wang, S., & Steinert‐Threlkeld, S. (2023) · BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP (BlackboxNLP) · doi:10.18653/v1/2023.blackboxnlp-1.21 · Cited by 3 · see citing works
Recurrent Neural Language Models as Probabilistic Finite-state Automata
Svete, A., & Cotterell, R. (2023) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2023.emnlp-main.502 · Cited by 3 · see citing works
Transformers, parallel computation, and logarithmic depth
Sanford, C., Hsu, D., & Telgarsky, M. (2024) · arXiv · doi:10.48550/arxiv.2402.09268 · Cited by 2
Nested Learning: The Illusion of Deep Learning Architectures
Behrouz, A., Razaviyayn, M., Zhong, P., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2512.24695 · Cited by 1 · see citing works
“…the expressive power of the models in multiple aspects, for example: (i) The computational depth of deep models might not change with more layers [21, 22], leaving their ability to implement complex algorithms untouched compared to traditional shallow approaches [23]; (ii) The capacity of some…”
Circuit Complexity Bounds for RoPE-based Transformer Architecture
Chen, B., Li, X., Liang, Y., Long, J., Shi, Z., Song, Z., & Zhang, J. (2025) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2025.emnlp-main.561 · Cited by 1 · see citing works
Formal Languages and the NLP Black Box
Merrill, W. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-33264-7_1 · Cited by 1 · see citing works
Self-citationEvaluating and Improving the Reasoning Abilities of Language Models
Helwe, C. (2024) · theses.fr (ABES) · doi:10.70675/7fc70e59zdd27z4b0fza38dz03a2c67cda50 · Cited by 1 · see citing works
Language models need inductive biases to count inductively
Chang, Y., & Bisk, Y. (2024) · arXiv · doi:10.48550/arxiv.2405.20131
“…of functional libraries (Weiss et al., 2021; Lindner et al., 2023; Zhou et al., 2023), boolean circuits (Cong et al., 1996; Yang & Chiang, 2024; Strobl et al., 2024; Merrill et al., 2022), or Automata Theory (Del’etang et al., 2022; Yao et al., 2021; Liu et al., 2022; Ebrahimi et al., 2020).”
BackgroundCertification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
de Luca, A. B., & Fountoulakis, K. (2026) · arXiv · doi:10.48550/arxiv.2605.22964
“Beyond this task connection, there is a stronger relationship between Transformers and circuits: existing expressivity results show that log-precision Transformer computations can be simulated by threshold circuits [24, 21, 23, 9].”
Implicit Language Models are RNNs: Balancing Parallelization and Expressivity
Schöne, M., Rahmani, B., Kremer, H., Falck, F., Ballani, H., & Gladrow, J. (2025) · arXiv · doi:10.48550/arxiv.2502.07827
“Such non-solvable transitions are critical for state tracking but remain intractable for the class of circuits representable by transformers and SSMs (Merrill et al., 2022; 2024).”
InfluentialCritical thinking: Which kinds of complexity govern optimal reasoning length?
Lee, C., Rush, A. M., & Vafa, K. (2025) · Proceedings of the 14th International Joint Conference on Natural Language Processing and the 4th Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics · doi:10.18653/v1/2025.ijcnlp-long.57
A Pragmatic Approach to Syntax Repair
Considine, B. (2023) · ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity (SPLASH) · doi:10.1145/3618305.3623591
Linear Decomposition of the Majority Boolean Function using the Ones on Smaller VariablesPreprint
Chattopadhyay, A., Bhattacharjee, D., & Maitra, S. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5508051
Three Tiers of Computation in Transformers and in Brain Architectures
Graham, E., & Granger, R. (2026) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3844612
Improving Representations for Language Modeling
Godey, N. (2024) · theses.fr (ABES) · doi:10.70675/b6a15d0ez15bez43e5za967z16a069e0a8bb
On the Computational Hardness of Transformers
Saha, B., Xu, Y., Ye, C., & Yu, H. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800819
Circuit Complexity of Hierarchical Knowledge Tracing
Liu, N.-S., Baraniuk, R. G., & Sonkar, S. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-29760-0_8
Characterizing the role of reasoning tokens in large language models as state over tokens
Levy, M., Elyoseph, Z., Ravfogel, S., & Goldberg, Y. (2026) · Nature Machine Intelligence · doi:10.1038/s42256-026-01303-y
- Authors
- Merrill, W., Sabharwal, A., & Smith, N. A.
- Affiliations
- Allen Institute for Artificial Intelligence (US)
- University of Washington (US)
- Corresponding author
- Merrill, William
- Sabharwal, Ashish
- Smith, Noah A.
- ORCID
- Smith, Noah A.
- Venue
- Transactions of the Association for Computational Linguistics
- Publisher
- MIT Press
- Published
- 2022
- Volume
- 10
- Pages
- 843-856
- ISSN
- 2307-387X (ISSN-L)
- OpenAlex
- W4290994975
- Cited by
- 25
- References
- 28
- Citations by year
- 2026: 5 · 2025: 5 · 2024: 3 · 2023: 11 · 2022: 1
- FWCI
- 2.61
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Locations
- Transactions of the Association for Computational Linguistics (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- transformer models, threshold circuits, TC0, circuit complexity, formal languages, hard attention, floating-point arithmetic
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
