The Parallelism Tradeoff: Limitations of Log-Precision Transformers
Open accessThe DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Abstract
Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens (and whose feedforward nets are computable using space linear in their input) can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory. For example, if L≠P (i.e., not all poly-time problems can be solved using logarithmic space), then transformers cannot even accurately solve linear equalities or check membership in an arbitrary context-free grammar with empty productions. Our result intuitively emerges from the transformer architecture’s high parallelizability. We thus speculatively introduce the idea of a fundamental parallelism tradeoff: any model architecture as parallelizable as the transformer will obey limitations similar to it. Since parallelism is key to training models at massive scale, this suggests a potential inherent weakness of the scaling paradigm.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“This result is in agreement with findings that Transformers and State Space models are fundamentally less powerful than RNNs (Merrill et al., 2024;Merrill & Sabharwal, 2023;Delétang et al., 2023).”
From xLSTM: Extended Long Short-Term Memory (2024) · cites this paper as Merrill & Sabharwal, 2023
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“This result is in agreement with findings that Transformers and State Space models are fundamentally less powerful than RNNs (Merrill et al., 2024;Merrill & Sabharwal, 2023;Delétang et al., 2023).”
From xLSTM: Extended Long Short-Term Memory (2024) · cites this paper as Merrill & Sabharwal, 2023
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“Independently, Merrill and Sabharwal [45] established a formal complexity bound for log-precision Transformers: they are contained in uniform TC0.”
From Self-Referential Introspection in Large Language Models: The Critical Threshold for Recursive Self-Improvement (2026) · cites this paper as [45]
The cited source says what the claim attributes to it.
In the citing paper
“a single forward pass of a log-precision Transformer is bounded by uniform TC0 [45] and cannot execute fixed-point iterations.”
From Self-Referential Introspection in Large Language Models: The Critical Threshold for Recursive Self-Improvement (2026) · cites this paper as [45]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
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 · cited 3×
“A transformer (Vaswani et al., 2017) is a neural network architecture made up of a constant number of transformer layers.”
BackgroundInfluentialBERT: 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 54,325 · cited 1×
“This work aims to characterize the computational model implicit in transformer neural networks (Vaswani et al., 2017), which form the basis of recent breakthroughs in large language models such as BERT (Devlin et al., 2019), T5 (Raffel et al., 2020), and GPT-3 (Brown et al., 2020).”
BackgroundLanguage Models are Few-Shot Learners
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020) · arXiv · doi:10.48550/arxiv.2005.14165 · Cited by 23,372
Advances in neural information processing systems 7
(1996) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(96)90463-0 · Cited by 14,281
Advances in Neural Information Processing Systems 29
Teymur, O., Zygalakis, K., & Calderhead, B. (2016) · Cited by 13,887
Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., & Liu, P. J. (2019) · arXiv · doi:10.48550/arxiv.1910.10683 · Cited by 10,929 · cited 1×
“This work aims to characterize the computational model implicit in transformer neural networks (Vaswani et al., 2017), which form the basis of recent breakthroughs in large language models such as BERT (Devlin et al., 2019), T5 (Raffel et al., 2020), and GPT-3 (Brown et al., 2020).”
BackgroundThe complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Undirected connectivity in log-space
Reingold, O. (2008) · Journal of the ACM · doi:10.1145/1391289.1391291 · Cited by 505 · cited 2×
“This implies that—despite their massive size—the computation performed by such transformers is, for instance, no harder than solving basic L-complete problems like graph connectivity: the problem of checking whether there is a path between two nodes in an undirected graph (Lewis and Papadimitriou, 1982; Reingold, 2008…”
BackgroundDehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., & Kaiser, Ł. (2018) · arXiv · doi:10.48550/arxiv.1807.03819 · Cited by 467
The circuit value problem is log space complete for P
Ladner, R. E. (1975) · ACM SIGACT News · doi:10.1145/990518.990519 · Cited by 306 · cited 1×
“…their massive size—the computation performed by such trans-formers is, for instance, no harder than solving basic L -complete problems like graph connectivity : the problem of checking whether there is a path between two nodes in an undirected graph (Lewis and Papadimitriou, 1982; Reingold, 2008).”
BackgroundComplete problems for deterministic polynomial time
Jones, N. D., & Laaser, W. T. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90068-2 · Cited by 279
Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications
Biere, A., Heule, M. J. H., van Maaren, H., & Walsh, T. (2009) · Cited by 251
Symmetric space-bounded computation
Lewis, H. R., & Papadimitriou, C. H. (1982) · Theoretical Computer Science · doi:10.1016/0304-3975(82)90058-5 · Cited by 171 · cited 1×
“This implies that—despite their massive size—the computation performed by such transformers is, for instance, no harder than solving basic L-complete problems like graph connectivity: the problem of checking whether there is a path between two nodes in an undirected graph (Lewis and Papadimitriou, 1982; Reingold, 2008…”
BackgroundTheoretical 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 · cited 3×
“, 2019) or place unrealistic restrictions (Hahn, 2020; Hao et al., 2022; Merrill et al., 2022).”
Background(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)90035-4 · Cited by 96
Division in logspace-uniformNC1
Chiu, A., Davida, G. I., & Litow, B. E. (2001) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita:2001119 · Cited by 92
On the Turing Completeness of Modern Neural Network Architectures
Pérez, J. E. P., Marinković, J., & Barceló, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.03429 · Cited by 78 · cited 2×
“Prior formal characterizations of transformers either make unrealistically strong assumptions (Pérez et al., 2019; Dehghani et al., 2019) or place unrealistic restrictions (Hahn, 2020; Hao et al., 2022; Mer-rill et al., 2022).”
BackgroundMasakhaNER: Named entity recognition for African languages
(2021) · HAL · doi:10.1162/tacl · Cited by 61
Hesse, W. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_9 · Cited by 52 · cited 1×
“4, it is standard and well-defined to extend the same term to refer to circuit families computing functions as well (Hesse, 2001).”
BackgroundThe Permanent Requires Large Uniform Threshold Circuits.
Allender, E. (1999) · Chicago Journal of Theoretical Computer Science · doi:10.4086/cjtcs.1999.007 · Cited by 52
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 · cited 4×
“Prior formal characterizations of transformers either make unrealistically strong assumptions (Pérez et al., 2019; Dehghani et al., 2019) or place unrealistic restrictions (Hahn, 2020; Hao et al., 2022; Mer-rill et al., 2022).”
BackgroundMethodInfluentialComplexity Results for Extended Planning
Bylander, T. (1992) · Elsevier eBooks · doi:10.1016/b978-0-08-049944-4.50008-2 · Cited by 25 · cited 2×
“• Universal context-free recognition1,2 • Propositional satisfiability (SAT)3 • Horn-clause satisfiability (HORN-SAT)1 • AI planning (Bylander, 1991) • Permanent computation4”
BackgroundSaturated Transformers are Constant-Depth Threshold Circuits
Merrill, W., Sabharwal, A., & Smith, N. A. (2022) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00493 · Cited by 25 · cited 3×
“The initial non-uniform result extends the findings of Merrill et al. (2022), who showed that saturated attention transformers 12 can be simulated in TC 0 .”
BackgroundInfluentialSelf-citationEffects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent
Merrill, W., Ramanujan, V., Goldberg, Y., Schwartz, R., & Smith, N. A. (2021) · Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2021.emnlp-main.133 · Cited by 13 · cited 1×
“We imagine f ( h , h ) is computed via saturated attention (cf. Merrill et al., 2022), which provides a simple model of the types of attention we can expect to be learned in trans-formers (Merrill et al., 2021).”
MethodSelf-citationFinlayson, M., Richardson, K., Sabharwal, A., & Clark, P. A. (2022) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/2022.emnlp-main.27 · Cited by 13
Self-citationOn the Linguistic Capacity of Real-Time Counter Automata
Merrill, W. (2020) · arXiv · doi:10.48550/arxiv.2004.06866 · Cited by 12 · cited 1×
“It is known that LSTMs cannot evaluate boolean formulae (Merrill, 2020), a special case of the CVP.”
BackgroundSelf-citation
Research works printed but not linked: 2
- Dettmers, 2022, GPT3.int8(): 8-bit matrix multiplication for transformers at scale
- Elhage, 2021, A mathematical framework for transformer circuits, Transformer Circuits Thread
Cited by
xLSTM: Extended Long Short-Term Memory
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., & Hochreiter, S. (2024) · Advances in Neural Information Processing Systems 37 · doi:10.52202/079017-3417 · Cited by 286
Faith and Fate: Limits of Transformers on Compositionality
Dziri, N., Lu, X., Sclar, M., Li, X. (., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Bras, R. L., et al. (2023) · Advances in Neural Information Processing Systems 36 · doi:10.52202/075280-3081 · Cited by 335
“Transformer-specific work has focused on quantifying the class of problems that (not necessarily autoregressive) transformers can express assuming perfect parameters [51, 50, 14, 49, inter alia].”
BackgroundFaith and Fate: Limits of Transformers on Compositionality
Dziri, N., Lu, X., Sclar, M., Li, X. L., Jiang, L., Lin, B. Y., West, P., Bhagavatula, C., Bras, R. L., Hwang, J. D., et al. (2023) · arXiv · Cited by 124
“Transformer-specific work has focused on quantifying the class of problems that (not necessarily autoregressive) transformers can express assuming perfect parameters [51, 50, 14, 49, inter alia].”
BackgroundxLSTM: Extended Long Short-Term Memory
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., & Hochreiter, S. (2024) · arXiv · doi:10.48550/arxiv.2405.04517 · Cited by 299
Randomized Positional Encodings Boost Length Generalization of Transformers
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., & Veness, J. (2023) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.18653/v1/2023.acl-short.161 · Cited by 153
Metadata
- Authors
- Merrill, W., & Sabharwal, A.
- Affiliations
- New York University (US)
- Allen Institute for Artificial Intelligence (US)
- Corresponding author
- Merrill, William
- Sabharwal, Ashish
- Venue
- Transactions of the Association for Computational Linguistics
- Publisher
- MIT Press
- Published
- 2023
- Volume
- 11
- Pages
- 531-545
- ISSN
- 2307-387X (ISSN-L)
- OpenAlex
- W4380996571
- Cited by
- 22
- References
- 27
- Citations by year
- 2026: 13 · 2025: 6 · 2024: 1 · 2023: 2
- FWCI
- 3.15
- 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, cc-by-sa)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1922658)
- 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, numerical precision
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.