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…”
Background
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The Parallelism Tradeoff: Limitations of Log-Precision Transformers. https://app.cochat.ai/papers/10.1162/tacl_a_00562
- The paper
- Merrill, W., & Sabharwal, A. (2023). The Parallelism Tradeoff: Limitations of Log-Precision Transformers. Transactions of the Association for Computational Linguistics. https://doi.org/10.1162/tacl_a_00562
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.