mlsanityData to 7 Oct 2026

The Parallelism Tradeoff: Limitations of Log-Precision Transformers

arXiv 2207.00729 ↗First posted 2 Jul 2022cs.CC cs.CLcited by 191

Not on the map. Why?

Cited by 44 in LLM reasoning, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

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 mathsf L neq mathsf 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.

Key facts. Cited by 191 papers in the map (data through 7 Oct 2026). Builds on 12 of its 30 references that are in the map. First posted on arXiv 2 Jul 2022.

Builds on

12 of 30 references.

References · 12

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  5. 2018Universal Transformerscited by 613
  6. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  7. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  8. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  9. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  10. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
  11. 2020On the Linguistic Capacity of Real-Time Counter Automatacited by 16
  12. 2022What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environmentcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 12; 2024: 46; 2025: 61; 2026: 70.

191 papers.

Sort:

By area:

  1. 2023Large Language Modelscited by 774
  2. 2025Self Forcing: Bridging the Train-Test Gap in Autoregressive Video Diffusioncited by 569
  3. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  4. 2023How Language Model Hallucinations Can Snowballcited by 310
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  6. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  7. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 223
  8. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  9. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelscited by 186
  10. 2024The Illusion of State in State-Space Modelscited by 181
  11. 2025Kimi Linear: An Expressive, Efficient Attention Architecturecited by 169
  12. 2025Hierarchical Reasoning Modelcited by 167
38 more
  1. 2024The pitfalls of next-token predictioncited by 156
  2. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  3. 2024Evaluating the World Model Implicit in a Generative Modelcited by 107
  4. 2025TiRex: Zero-Shot Forecasting Across Long and Short Horizons with Enhanced In-Context Learningcited by 107
  5. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  6. 2024In-Context Language Learning: Architectures and Algorithmscited by 86
  7. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  8. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 73
  9. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 69
  10. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  11. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  12. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  13. 2024On Limitations of the Transformer Architecturecited by 63
  14. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 62
  15. 2025On the Emergence of Position Bias in Transformerscited by 57
  16. 2025Training Strategies for Efficient Embodied Reasoningcited by 53
  17. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  18. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 47
  19. 2025What Has a Foundation Model Found? Using Inductive Bias to Probe for World Modelscited by 46
  20. 2024Theoretical limitations of multi-layer Transformercited by 43
  21. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  22. 2024Transformers Can Represent n-gram Language Modelscited by 31
  23. 2024How Much Can RAG Help the Reasoning of LLM?cited by 31
  24. 2025(How) Do Language Models Track State?cited by 31
  25. 2025Understanding Transformer from the Perspective of Associative Memorycited by 31
  26. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  27. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  28. 2025Next-Latent Prediction Transformers Learn Compact World Modelscited by 29
  29. 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 28
  30. 2023CoTFormer: A Chain-of-Thought Driven Architecture with Budget-Adaptive Computation Cost at Inferencecited by 27
  31. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  32. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  33. 2025LLM Probability Concentration: How Alignment Shrinks the Generative Horizoncited by 26
  34. 2024DeCoRe: Decoding by Contrasting Retrieval Heads to Mitigate Hallucinationscited by 23
  35. 2024When Can Transformers Count to n?cited by 22
  36. 2024Self-Guiding Exploration for Combinatorial Problemscited by 21
  37. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  38. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21

50 most cited of 191 All 191 (JSON)