mlsanityData to 14 Oct 2026

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

arXiv 2502.02393 ↗First posted 4 Feb 2025cs.LG cs.CCcited by 28

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Chain-of-thought reasoning and scratchpads have emerged as critical tools for enhancing the computational capabilities of transformers. While theoretical results show that polynomial-length scratchpads can extend transformers' expressivity from TC0 to PTIME, their required length remains poorly understood. Empirical evidence even suggests that transformers need scratchpads even for many problems in TC0, such as Parity or Multiplication, challenging optimistic bounds derived from circuit complexity. In this work, we initiate the study of systematic lower bounds for the number of chain-of-thought steps across different algorithmic problems, in the hard-attention regime. We study a variety of algorithmic problems, and provide bounds that are tight up to logarithmic factors. Overall, these results contribute to emerging understanding of the power and limitations of chain-of-thought reasoning.

Key facts. Cited by 28 papers in the map (data through 14 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 33 of its 90 references that are in the map. First posted on arXiv 4 Feb 2025.

Builds on

33 of 90 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025Ehrenfeucht-Haussler Rank and Chain of Thought22 Jan
  2. 2024LLMs Faithfully and Iteratively Compute Answers During CoT: A Systematic Analysis With Multi-step Arithmetics2 Dec
  3. 2024From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step23 May
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 29

  1. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  2. 2016Layer Normalizationcited by 5,669
  3. 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,346
  4. 2024OpenAI o1 System Cardcited by 1,244
  5. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  6. 2024Token-Budget-Aware LLM Reasoningcited by 247
  7. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  8. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  9. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  10. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 101
  11. 2023A Theory of Emergent In-Context Learning as Implicit Structure Inductioncited by 86
  12. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
17 more
  1. 2024Transformers Can Do Arithmetic with the Right Embeddingscited by 78
  2. 2023GPT Can Solve Mathematical Problems Without a Calculatorcited by 68
  3. 2024On Limitations of the Transformer Architecturecited by 63
  4. 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
  5. 2024Theoretical limitations of multi-layer Transformercited by 45
  6. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  7. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  8. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  9. 2024Universal Length Generalization with Turing Programscited by 25
  10. 2024How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMscited by 24
  11. 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
  12. 2024Arithmetic Transformers Can Length-Generalize in Both Operand Length and Countcited by 18
  13. 2024Transformers Learn Low Sensitivity Functions: Investigations and Implicationscited by 14
  14. 2024Explicitly Encoding Structural Symmetry is Key to Length Generalization in Arithmetic Taskscited by 11
  15. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  16. 2024Learning High-Degree Parities: The Crucial Role of the Initializationcited by 7
  17. 2024Lower bounds on transformers with infinite precisioncited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 13; 2026: 15.

28 papers.

Sort:

By area:

  1. 2025Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Modelscited by 384
  2. 2025Measuring Chain of Thought Faithfulness by Unlearning Reasoning Stepscited by 47
  3. 2025A Formal Comparison Between Chain of Thought and Latent Thoughtcited by 15
  4. 2025Behavior Injection: Preparing Language Models for Reinforcement Learningcited by 8
  5. 2025Thoughts without Thinking: Reconsidering the Explanatory Value of Chain-of-Thought Reasoning in LLMs through Agentic Pipelinescited by 7
  6. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  7. 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
  8. 2026Do Language Models Track Entities Across State Changes?cited by 6
  9. 2026Parity, Sensitivity, and Transformerscited by 5
  10. 2025The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architecturescited by 4
  11. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
  12. 2025Efficient Turing Machine Simulation with Transformerscited by 4
16 more
  1. 2026On the Spatiotemporal Dynamics of Generalization in Neural Networkscited by 3
  2. 2026Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidthcited by 3
  3. 2026The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thoughtcited by 3
  4. 2025The Impossibility of Inverse Permutation Learning in Transformer Modelscited by 2
  5. 2025Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differentlycited by 2
  6. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  7. 2026Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separationcited by 2
  8. 2026A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attentioncited by 1
  9. 2026Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMscited by 1
  10. 2026The Library Theorem: How External Organization Governs Agentic Reasoning Capacitycited by 1
  11. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)cited by 1
  12. 2026The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessarycited by 1
  13. 2025BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoningcited by 0
  14. 2026On the Expressive Power of Transformerscited by 0
  15. 2026Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformerscited by 0
  16. 2026Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?cited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023The Expressive Power of Transformers with Chain of Thought
  2. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
  3. 2025Softmax Transformers are Turing-Complete
  4. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
  5. 2026The Geometry of Thought: Disclosing the Transformer as a Tropical Polynomial Circuit
  6. 2025To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers
  7. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought
  8. 2025Exact Expressive Power of Transformers with Padding