mlsanityData to 7 Oct 2026

Transformers, parallel computation, and logarithmic depth

arXiv 2402.09268 ↗First posted 14 Feb 2024cs.LGcited by 75

Not on the map. Why?

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

Abstract (arXiv)

We show that a constant number of self-attention layers can efficiently simulate, and be simulated by, a constant number of communication rounds of Massively Parallel Computation. As a consequence, we show that logarithmic depth is sufficient for transformers to solve basic computational tasks that cannot be efficiently solved by several other neural sequence models and sub-quadratic transformer approximations. We thus establish parallelism as a key distinguishing property of transformers.

Key facts. Cited by 75 papers in the map (data through 7 Oct 2026). Builds on 26 of its 63 references that are in the map. First posted on arXiv 14 Feb 2024.

Builds on

26 of 63 references.

References · 26

  1. 2017Attention Is All You Needcited by 59,932
  2. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  3. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  4. 2020Longformer: The Long-Document Transformercited by 3,362
  5. 2014Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modelingcited by 2,341
  6. 2020Rethinking Attention with Performerscited by 1,584
  7. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 994
  8. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  9. 2022Transformers Learn Shortcuts to Automatacited by 260
  10. 2016Benefits of depth in neural networkscited by 248
  11. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  12. 2022Pure Transformers are Powerful Graph Learnerscited by 188
14 more
  1. 2023Birth of a Transformer: A Memory Viewpointcited by 154
  2. 2023Representational Strengths and Limitations of Transformerscited by 132
  3. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  4. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  5. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  6. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  7. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  8. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 47
  9. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 47
  10. 2021On the Expressive Power of Self-Attention Matricescited by 44
  11. 2023PolySketchFormer: Fast Transformers via Sketching Polynomial Kernelscited by 33
  12. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  13. 2022Systematic Generalization and Emergent Structures in Transformers Trained on Structured Taskscited by 19
  14. 2020New lower bounds for Massively Parallel Computation from query complexitycited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 24; 2025: 27; 2026: 24.

75 papers.

Sort:

By area:

  1. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 223
  2. 2024The pitfalls of next-token predictioncited by 156
  3. 2025Scaling Latent Reasoning via Looped Language Modelscited by 145
  4. 2025Nested Learning: The Illusion of Deep Learning Architecturescited by 69
  5. 2024Transformers Provably Solve Parity Efficiently with Chain of Thoughtcited by 49
  6. 2024Theoretical limitations of multi-layer Transformercited by 43
  7. 2024One-layer transformers fail to solve the induction heads taskcited by 30
  8. 2024Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Datacited by 30
  9. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  10. 2024Counting Ability of Large Language Models and Impact of Tokenizationcited by 29
  11. 2025Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMscited by 29
  12. 2025How Do LLMs Perform Two-Hop Reasoning in Context?cited by 20
38 more
  1. 2024Transformers Struggle to Learn to Searchcited by 19
  2. 2025Foundation Models for Time Series: A Surveycited by 19
  3. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  4. 2025A Formal Comparison Between Chain of Thought and Latent Thoughtcited by 14
  5. 2024Distributional Associations vs In-Context Reasoning: A Study of Feed-forward and Attention Layerscited by 12
  6. 2024The Belief State Transformercited by 12
  7. 2025Is Random Attention Sufficient for Sequence Modeling? Disentangling Trainable Components in the Transformercited by 12
  8. 2025Knee-Deep in C-RASP: A Transformer Depth Hierarchycited by 12
  9. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Pathcited by 10
  10. 2025To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformerscited by 10
  11. 2025Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformerscited by 10
  12. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  13. 2025Lost in Transmission: When and Why LLMs Fail to Reason Globallycited by 9
  14. 2025Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limitscited by 9
  15. 2025An explainable transformer circuit for compositional generalizationcited by 8
  16. 2024How Transformers Get Rich: Approximation and Dynamics Analysiscited by 7
  17. 2024KV Shifting Attention Enhances Language Modelingcited by 7
  18. 2026Sequential Group Composition: A Window into the Mechanics of Deep Learningcited by 7
  19. 2024Contextual Counting: A Mechanistic Study of Transformers on a Quantitative Taskcited by 6
  20. 2024Best of Both Worlds: Advantages of Hybrid Graph Sequence Modelscited by 6
  21. 2025Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacitycited by 6
  22. 2024Supervised Chain of Thoughtcited by 5
  23. 2025Compression Barriers for Autoregressive Transformerscited by 5
  24. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 5
  25. 2026Billion-Scale Graph Foundation Modelscited by 5
  26. 2024Reasoning in Large Language Models: A Geometric Perspectivecited by 4
  27. 2024On the Benefits of Rank in Attention Layerscited by 4
  28. 2024Benchmarking and Understanding Compositional Relational Reasoning of LLMscited by 4
  29. 2025Subquadratic Algorithms and Hardness for Attention with Any Temperaturecited by 4
  30. 2025Transformers Meet In-Context Learning: A Universal Approximation Theorycited by 4
  31. 2025Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scalingcited by 4
  32. 2024A Theory for Compressibility of Graph Transformers for Transductive Learningcited by 2
  33. 2025When Do Transformers Outperform Feedforward and Recurrent Networks? A Statistical Perspectivecited by 2
  34. 2025Fast attention mechanisms: a tale of parallelismcited by 2
  35. 2026Energy-Entropy Regularization: The True Power of Minimal Looped Transformerscited by 2
  36. 2026Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformerscited by 2
  37. 2025Sample-Efficient Optimization over Generative Priors via Coarse Learnabilitycited by 1
  38. 2025Two Heads Are Better than One: Simulating Large Transformers with Small Onescited by 1

50 most cited of 75 All 75 (JSON)