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
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 200
“Furthermore, Merrill and Sabharwal (2023a) show that softmax attention, O ( log n ) -precision transformers are in L -uniform TC 0 , and then tighten this bound to DLOGTIME -uniform TC 0 (Merrill and Sabharwal, 2023b).”
BackgroundSelf-citationTowards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective
Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., & Wang, L. (2023) · arXiv · doi:10.48550/arxiv.2305.15408 · Cited by 69
“[36] William Merrill and Ashish Sabharwal.”
BackgroundResultInfluentialLarge Language ModelsPreprint
Douglas, M. R. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2307.05782 · Cited by 55
Training Strategies for Efficient Embodied ReasoningPreprint
Chen, W., Belkhale, S., Mirchandani, S., Mees, O., Driess, D., Pertsch, K., & Levine, S. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.08243 · Cited by 71
“Critically though, this does not improve the complexity class of the Transformer, which is known to be TC 0 ; it only increases the expressivity of the fixed-size network within that class [64, 83].”
GeoNav: Empowering MLLMs with dual-scale geospatial reasoning for language-goal aerial navigation
Xu, H., Hu, Y., Gao, C., Zhu, Z., Zhao, Y., & Yin, Q. (2026) · Pattern Recognition · doi:10.1016/j.patcog.2026.113365 · Cited by 54
Lessons from Studying Two-Hop Latent ReasoningPreprint
Balesni, M., Korbak, T., & Evans, O. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2411.16353 · Cited by 37
Next-Latent Prediction Transformers Learn Compact World ModelsPreprint
Teoh, J., Tomar, M., Ahn, K., Hu, E. S., Pearce, T., Sharma, P., Krishnamurthy, A., Islam, R., Lamb, A., & Langford, J. C. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2511.05963 · Cited by 39
“After all, it primarily serves as a complementary alignment objective.”
Olmo Hybrid: From Theory to Practice and BackPreprint
Merrill, W., Li, Y., Romero, T., Svete, A., Costello, C., Dasigi, P., Groeneveld, D., Heineman, D., Kuehl, B., Lambert, N., et al. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.03444 · Cited by 38
Self-citationState-space modeling in long sequence processing: a survey on recurrence in the transformer era
Tiezzi, M., Casoni, M., Betti, A., Gori, M., & Melacci, S. (2025) · Neural Networks · doi:10.1016/j.neunet.2025.108039 · Cited by 39
Evaluating the World Model Implicit in a Generative Model
Vafa, K., Chen, J., Rambachan, A., Kleinberg, J., & Mullainathan, S. (2024) · Advances in Neural Information Processing Systems 37 · doi:10.52202/079017-0846 · Cited by 22
CoTFormer: A Chain-of-Thought Driven Architecture with Budget-Adaptive Computation Cost at Inference
Mohtashami, A., Pagliardini, M., & Jaggi, M. (2023) · International Conference on Learning Representations · doi:10.48550/arxiv.2310.10845 · Cited by 23
“Furthermore, while Transformers with fixed depth are not Turing complete on their own [22], combining them with the auto-regressive decoding used for generating the chain of thought can make them Turing complete [21, 23].”
BackgroundTransformers in Uniform TC$^0$Preprint
Chiang, D. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2409.13629 · Cited by 20
A Survey on Compositional Learning of AI Models: Theoretical and Experimental Practices
Sinha, S., Premsri, T., & Kordjamshidi, P. (2024) · Transactions on machine learning research · doi:10.48550/arxiv.2406.08787 · Cited by 34
“This result remains limited to the scope of a single neuron and has not yet been extended to large models.”
InfluentialLimits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory
Zubić, N., Soldá, F., Sulser, A., & Scaramuzza, D. (2024) · International Conference on Learning Representations · doi:10.48550/arxiv.2405.16674 · Cited by 21
“One approach at explaining this failure case of the transformer models is by their limitation to express simple kinds of state tracking problems [24].”
Self-Guiding Exploration for Combinatorial Problems
Iklassov, Z., Du, Y., Akimov, F., & Takáč, M. (2024) · neural information processing systems · doi:10.52202/079017-4150 · Cited by 31
Characterizing the Expressivity of Fixed-Precision Transformer Language Models
Li, J., & Cotterell, R. (2025) · neural information processing systems · doi:10.52202/085713-5329 · Cited by 26
“For instance, while practical implementations of transformers operate under fixed precision, e.g., single (32-bit) or half (16-bit) precision, many authors assume arbitrary [38, 18, 34] or length-dependent precision [32, 7].”
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
“Overall, we hope our results help demystify certain observations of the surprising “reasoning-like” abilities of Transformers, by showing that some of these behaviors can actually emerge for simple, unsurprising reasons.”
ResultICL Characterization of Geo-Foundation Models
Hawarey, M. (2026) · AIR Journal of Mathematics & Computational Sciences · doi:10.65737/airmcs2026360 · Cited by 9
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 13
“Meanwhile, TC 0 , the standard for modeling discretized neural networks 20,78 , can simulate LLMs with realistic constraints on variable precision and autoregression 25,79,80 , in the absence of more complicated elements such as feedback loops.”
Transformers are Expressive, But Are They Expressive Enough for Regression?Preprint
Nath, S., Khadilkar, H., & Bhattacharyya, P. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2402.15478 · Cited by 11
“In light of the success of Transformers, several works (De-hghani et al., 2018; Yun et al., 2020a; Perez et al., 2021; Merrill & Sabharwal, 2023) have studied the expressivity 1 of Transformers.”
BackgroundICL Characterization of Climate Foundation Models: When Can Transformers Learn Weather and Climate?
Hawarey, M. (2026) · AIR Journal of Mathematics & Computational Sciences · doi:10.65737/airmcs2026405 · Cited by 7
Fixed-Point RNNs: Interpolating from Diagonal to Dense
Movahedi, S., Sarnthein, F., Cirone, N. M., & Orvieto, A. (2025) · neural information processing systems · doi:10.52202/085713-1495 · Cited by 14
“With similar motivations, Merrill & Sabharwal (2023) introduce a set of word-problems for assessing state-tracking capabilities, among which the A 5 and S 5 tasks remain unsolved by Transformers and SSMs. Motivated by Transformers outperforming RNNs in memory capabilities, Jelassi et al. (2024)…”
Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right DataPreprint
Ran-Milo, Y., Alexander, Y., Mendel, S., & Cohen, N. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2601.15158 · Cited by 8
Hawarey, M. (2026) · AIR Journal of Mathematics & Computational Sciences · doi:10.65737/airmcs2026446 · Cited by 6
Chain-of-Thought ICL for GeoAI: Breaking the Hardness Barrier
Hawarey, M. (2026) · doi:10.65737/airmcs2026482 · Cited by 7
Scalable and accurate online multivariate anomaly detection
Salles, R. P., Lange, B., Akbarinia, R., Masséglia, F., Ogasawara, E., & Pacitti, E. (2025) · Information Systems · doi:10.1016/j.is.2025.102524 · Cited by 6
“Furthermore, the latest advances in parallel and distributed computing for multivariate anomaly detection are discussed, including the adoption of: federated learning [Abreha et al., 2022], GPU acceleration [Zhu et al., 2021], and transformer architectures [Merrill and Sabharwal, 2023].”
Investigating Recurrent Transformers with Dynamic HaltPreprint
Chowdhury, J. R., & Caragea, C. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2402.00976 · Cited by 8
“Recurrence can, in principle, allow the model to assign an unbounded amount of layers depending on the task complexity (Dehghani et al., 2019; Tan et al., 2023; Banino et al., 2021).”
BackgroundDepth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with TransformersPreprint
Yehudai, G., Sanford, C., Bechler-Speicher, M., Fischer, O., Gilad-Bachrach, R., & Globerson, A. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2503.01805 · Cited by 9
“This is a common assumption in many previous works Sanford et al. [2024c,b], Merrill and Sabharwal [2023b, 2024], and is relatively mild.”
Yang, A., Watson, C., Xue, A., Bhattamishra, S., Llarena, J. R. L., Merrill, W., Ferreira, E. D. S., Svete, A., & Chiang, D. (2025) · Transactions on machine learning research · doi:10.3929/ethz-c-000796068 · Cited by 5
Self-citationThe expressive power of transformers with chain of thought
Merrill, W., & Sabharwal, A. (2023) · arXiv · doi:10.48550/arxiv.2310.07923 · Cited by 4
Self-citationTighter Bounds on the Expressivity of Transformer Encoders
Chiang, D., Cholak, P., & Pillay, A. (2023) · arXiv · doi:10.48550/arxiv.2301.10743 · Cited by 4
“In subsequent work (Merrill & Sabharwal, 2023), they show that transformers using full (softmax) attention and numbers with 𝑂 ( log 𝑛 ) bits recognize languages in logspace-uniform TC 0 .”
BackgroundMethodFormal 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 8
“[19] then extend [21]’s result to show that arbitrary soft-attention trans-formers with precision logarithmic in the input length can be simulated in the tighter class log-space-uniform TC 0 .”
Self-citationFlashRNN: I/O-Aware Optimization of Traditional RNNs on modern hardwarePreprint
Pöppel, K., Beck, M., & Hochreiter, S. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2412.07752 · Cited by 7
“…[Vaswani et al., 2017], Mamba [Gu & Dao, 2023] or mLSTM [Beck et al., 2024], these lack the state-tracking capabilities [Mer-rill et al., 2024, Merrill & Sabharwal, 2023, Delétang et al., 2023] of traditional RNNs like LSTM [Hochreiter & Schmidhuber, 1997], GRU [Cho et al., 2014] and sLSTM…”
The Seriality Gap in Video Diffusion ModelsPreprint
Chao, J. D., Preechakul, K., Liu, Y., & Bai, Y. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.13031 · Cited by 6
“Our explanation connects these empirical failures to prior work on transformer parallelism, depth– width tradeoffs, and serial scaling, which argues that model depth, width, and denoising steps are not interchangeable computational resources [20, 37, 38, 22].”
The Capability Convergence Hypothesis: Capability from Access Structure, Not ScalePreprint
Chen, W., Chen, J., Lin, Z., & Vong, C. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.14144 · Cited by 4
“A fixed-depth, log-precision, softmax-attention stack (in the model of the cited bound) lies in TC 0 [38]; chain-of-thought is exactly what escapes this class for serial problems [34].”
Wang, G., Li, J., Sun, Y., Chen, X., Liu, C., Wu, Y., Lu, M., Song, S., & Yadkori, Y. A. (2025) · arXiv · doi:10.48550/arxiv.2506.21734 · Cited by 3
“For example, our results on the Sudoku task show that increasing Transformer model depth can improve performance, 1 but performance remains far from optimal even with very deep models (see Figure 2), which supports the conjectured limitations of the LLM scaling paradigm 9 .”
RELIC: Evaluating Complex Reasoning via the Recognition of Languages In-Context
Petty, J., Hu, M. Y., Wang, W., Ravfogel, S., Merrill, W., & Linzen, T. (2026) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl.a.735 · Cited by 4
Self-citationMemory makes computation universal, remember?Preprint
Garrison, E. P. (2024) · arXiv (Cornell University) · doi:10.48550/arxiv.2412.17794 · Cited by 3
Data Shifts Hurt CoT: A Theoretical StudyPreprint
Yin, L., Banerjee, D., & Singh, G. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2506.10647 · Cited by 3
On the Spatiotemporal Dynamics of Generalization in Neural NetworksPreprint
Wei, Z. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2602.01651 · Cited by 5
“…that make it so successful in language modeling—such as global attention allowing it to see the entire sequence at once, and different layers learning different representations—are precisely what cause its systematic failure in tasks requiring precise logic and long-range causality [13, 22].”
Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget SeparationPreprint
Zhang, H. (2026) · arXiv.org · doi:10.48550/arxiv.2605.30757 · Cited by 4
“Merrill and Sabharwal (2023) place log-precision Trans-formers in logspace-uniform TC 0 , providing the circuit-complexity background for the comparisons above.”
Attention-based representations for multi-task computationPreprint
Hsu, D., & Xu, M. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.04243 · Cited by 3
“In transformers, layers of several attention heads are composed together to form these representations, and the use of multiple layers seems to be necessary for several natural computational tasks related to multi-step reasoning [4, 5, 15, 16, 17, 24].”
The Head Complexity of Boolean Functions in Single-Layer AttentionPreprint
Rajaraman, R., Sundaram, R., & Tesfaye, A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.04046 · Cited by 3
Zhang, J., Yuan, B., & Zhang, Q. (2026) · Entropy · doi:10.3390/e28090951 · Cited by 2
“The standard Transformer, however, is fundamentally feedforward, so a single forward pass of a log-precision Transformer is bounded by uniform TC 0 [45] and cannot execute fixed-point iterations.”
Transformers, parallel computation, and logarithmic depth
Sanford, C., Hsu, D., & Telgarsky, M. (2024) · arXiv · doi:10.48550/arxiv.2402.09268 · Cited by 2
Turbo Connection: Reasoning as Information Flow from Higher to Lower LayersPreprint
Tang, M., & Lu, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2602.17993 · Cited by 2
“Aligning with this perspective, Merrill & Sabharwal (2023) demonstrated that finite-depth Transformers are confined to the uniform TC 0 complexity class, a class of problems solvable by constant-depth circuits, suggesting they may lack the expressive power required for inherently sequential…”
Preisach Attention: A Hysteretic Model of Sequential MemoryPreprint
Frydrych, P. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.23603 · Cited by 2
“Merrill and Sabharwal (2023) established circuit complexity bounds separating transformer classes.”
An Examination on the Effectiveness of Divide-and-Conquer Prompting in Large Language Models
Zhang, Y., Du, L., Cao, D., Fu, Q., & Liu, Y. (2024) · arXiv · doi:10.48550/arxiv.2402.05359 · Cited by 2
Kimi Linear: An Expressive, Efficient Attention Architecture
Kimi Team, Zhang, Y., Lin, Z., Yao, X., Hu, J., Meng, F., Liu, C., Men, X., Yang, S., Li, Z., et al. (2025) · arXiv · doi:10.48550/arxiv.2510.26692 · Cited by 1
“This design achieves expressive power comparable to softmax attention [65, 125, 64] while maintaining constant time and memory complexity during inference time.”
RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval
Wen, K., Dang, X., & Lyu, K. (2024) · arXiv · doi:10.48550/arxiv.2402.18510 · Cited by 1
“This is a common assumption when studying the finite precision neural networks (Feng et al., 2023; Merrill & Sabharwal, 2023).”
BackgroundWu, T., & Han, Z. (2025) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2025.131077 · Cited by 2
Graph Neural Networks and Arithmetic Circuits
Barlag, T., Holzapfel, V., Strieker, L., Virtema, J., & Vollmer, H. (2024) · neural information processing systems · doi:10.52202/079017-0175 · Cited by 1
Basu, S., Sheth, P., Muralidharan, B., Morgan, J., & Batniji, R. (2026) · AI · doi:10.3390/ai7070267 · Cited by 1
“…fixed-depth log-precision transformers are contained in the circuit class TC0 and cannot express certain compositional problems regardless of scale [12], a chain of thought relaxes but does not remove this for a bounded number of steps [13], and compositional accuracy decays empirically with…”
Beyond Parallel Blindness: Information Floors and Model Gaps in Block DraftingPreprint
Qiang, X., Fang, X., Chen, C., Pan, Z., Guan, Y., & Ding, Y. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.27339 · Cited by 1
“Log-precision transformers in the model of Merrill & Sabharwal (2023) are contained in logspace-uniform TC 0 , which contains parity.”
Certification 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
“Theorem C.1 (Merrill and Sabharwal [22]) .”
InfluentialImplicit 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
“These shortcomings appear to stem from a fundamental trade-off between parallelizability at training time and the ability to track state (Merrill & Sabharwal, 2023).”
InfluentialExact Expressive Power of Transformers with Padding
Merrill, W., & Sabharwal, A. (2025) · Advances in Neural Information Processing Systems 38 · doi:10.52202/085713-3758
Self-citationSchmidt, D. M., Schubert, R., & Cimiano, P. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-09527-5_1 · Cited by 2
“The question of whether LLMs can work in a compositional way has been investigated from different perspectives already, e.g., from a more (complexity) theoretical point of view [8, 14, 29, 44, 55], or with focus on arithmetics [12, 28] or logic puzzles [12].”
Expert Survey: AI Reliability & Security Research PrioritiesPreprint
O'Brien, J., Dolan, J., Kim, J., Dykhuizen, J., Sania, J., Becker, S., Kraprayoon, J., & Labrador, C. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.21664
xLSRec: xLSTM for Sequential Recommendation
Liu, H., Zhao, M., & Liu, J. (2025) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn64981.2025.11227198
“Furthermore, the memory fusion mechanism of sLSTM effectively resolves state-tracking[33, 34] issues, Authorized licensed use limited to the terms of the applicable license agreement with IEEE.”
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 · Cited by 2
“…language perspective (predominantly via automata or circuit complexity analyses), [1, 119, 181] has examined what models are able to do [1, 22, 23, 31, 118, 119, 153, 154, 172, 182, 200, 208] and what models are not able to do [75, 77, 121, 122, 180], i.e., computational lower and upper bounds.”
Enhanced Architectures and Optimization Methods for Efficient Language Modeling
Mohtashami, A. (2025) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-10940
Ανάπτυξη συστήματος συνομιλίας μεταξύ chatbots
Μαντούβαλου, Δ. (2024) · Dione (University of Piraeus) · doi:10.26267/unipi_dione/4175
Towards Learning High-Precision Least Squares Algorithms with Sequence ModelsPreprint
Liu, J., Grogan, J., Dugan, O., Rao, A., Arora, S., Rudra, A., & Ré, C. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2503.12295
Shortcut Transformers and the Learnability of Automata
Martens, W. (2023) · KTH Publication Database DiVA (KTH Royal Institute of Technology)
On the Mirage of Long-Range Dependency, with an Application to Integer MultiplicationPreprint
Wei, Z. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2603.29069 · Cited by 1
“A Transformer has global connectivity but fixed depth 𝑂(1) [7], [8]; a cellular automaton has only local connectivity but can iterate for 𝑂(𝑛) steps.”
The UNDO Flip-Flop: A Controlled Probe for Reversible Semantic State Management in State Space ModelPreprint
Zhou, H. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2604.05923
“Theoretical analyses show that log-precision Transformers are confined to the TC 0 complexity class and cannot reliably compute inherently sequential problems [Merrill and Sabharwal, 2023].”
Closing the Theory-Practice Gap in Spiking Transformers via Effective Dimension
Guo, D., Wu, J., & Yiu, S. M. (2026) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn69854.2026.11728473
“Merrill and Sabharwal proved log-precision transformers lie in TC 0 [17].”
Zhang, Y., Zhang, Y., Zhou, X., & Chen, X. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.19944
“Bounded-precision Transformers are restricted to TC 0 , inherently struggling with sequential NC 1 tasks like Dyck languages [Hahn, 2020, Merrill and Sabharwal, 2023].”
Emergence of Frontier Superposition: Möbius attractor and Cascade SupervisionPreprint
Gu, H., & Fu, J. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.18820
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 · Cited by 1
“Lower bounds against transformers typically rely on communication complexity [SHT23, PNP24, SHT24b] for depth one lower bounds, or reductions to other computational models [MS23, PNP24, SHT24b].”
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
On the Computational Complexity of Structural GeneralizationPreprint
Wei, Z. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.19573
“But once a reliable proof is demanded, an asymmetry emerges: Transformers have a precise definition, and their computational power is characterized exactly in terms of circuit complexity(Merrill and Sabharwal, 2023), while structural generalization remains unclear.”
On the Expressive Power of TransformersPreprint
Kolaitis, P., & Sengupta, R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2608.12671
“• SMAT and AHAT encoders with 𝑂 ( log 𝑛 ) -precision only recognize languages in TC 0 [6, 18, 24].”
LLM-Augmented Program Analysis: Towards Practical and Scalable Bug Detection
Li, H. (2026) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/3774748.3787640
“Certain classes of static analysis tasks (e.g., path-sensitive data-flow analysis, alias resolution) have intrinsic computational complexity, raising questions about whether any transformer-based architecture can feasibly solve such tasks [10, 11].”
Structure-Guided Approaches for Robust Language Model Reasoning
Sclar, M. (2026) · ResearchWorks at the University of Washington (University of Washington)
Beyond Hallucination: Cultural Entropy in Multi-Turn Conversation with Large Language Models
Ciccia, A. (n.d.) · PhilPapers (PhilPapers Foundation)
Modern Language Models on Permutation State Tracking
Surya, R. Z. J., Christian, S., Budianto, V., & Hidayaturrahman (2026) · International Conference on Information Management and Technology (ICIMTech) · doi:10.1109/icimtech202671078.2026.11699041
“Consequently, an LM can exploit this and learn to solve S 3 state tracking problems with constant depth number of layers (TC 0 word problem class) [22].”
Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?Preprint
He, J., Fan, J., Xiao, X., Mărculescu, R., & Ribeiro, A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.33134
“Existing results of this type, based on the circuit perspective on transformers (Merrill & Sabharwal, 2023; 2025; Amiri et al., 2025), establish that for a given class of problems there exists a transformer with some chain length that solves it.”
InfluentialImproving the Expressive Power of Hybrid Sequence Models via Multi-Hop RetrievalPreprint
Eitan, Y., Yehudai, G., & Maron, H. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.25250
“Circuit-complexity analyses establish limitations of log-precision Transformers [27] and study how padding tokens[26], recurrent application of layers [10] and chain of thought tokens [28] expand their capabilities.”
Copying Under Repetition: From Prefix Matching to Position HashingPreprint
Guo, A., Huang, T., Yang, C., & Li, Z. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.26722 · Cited by 1
“This captures a natural requirement for a model designed for a finite context window, and lies between length-specific circuit expressivity (Li et al., 2024; Merrill & Sabharwal, 2023) and fixed-resource expressivity over unbounded lengths (Yang et al., 2025; 2026).”
Putting Transformer Theories to the TestPreprint
Altabaa, A., Schnabel, T., & Tomlinson, K. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2610.32104
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.