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

arXiv: https://arxiv.org/abs/2502.02393 · HTML: https://mlsanity.com/paper/2502.02393/

## 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.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 30 of 33)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step](https://mlsanity.com/paper/2405.14838/) (2024)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [A Theory of Emergent In-Context Learning as Implicit Structure Induction](https://mlsanity.com/paper/2303.07971/) (2023)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [GPT Can Solve Mathematical Problems Without a Calculator](https://mlsanity.com/paper/2309.03241/) (2023)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Universal Length Generalization with Turing Programs](https://mlsanity.com/paper/2407.03310/) (2024)
- [How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs](https://mlsanity.com/paper/2410.13857/) (2024)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count](https://mlsanity.com/paper/2410.15787/) (2024)
- [Transformers Learn Low Sensitivity Functions: Investigations and Implications](https://mlsanity.com/paper/2403.06925/) (2024)
- [Explicitly Encoding Structural Symmetry is Key to Length Generalization in Arithmetic Tasks](https://mlsanity.com/paper/2406.01895/) (2024)
- [LLMs Faithfully and Iteratively Compute Answers During CoT: A Systematic Analysis With Multi-step Arithmetics](https://mlsanity.com/paper/2412.01113/) (2024)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)

## Built on by (most cited first, 28 of 28)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Measuring Chain of Thought Faithfulness by Unlearning Reasoning Steps](https://mlsanity.com/paper/2502.14829/) (2025)
- [A Formal Comparison Between Chain of Thought and Latent Thought](https://mlsanity.com/paper/2509.25239/) (2025)
- [Behavior Injection: Preparing Language Models for Reinforcement Learning](https://mlsanity.com/paper/2505.18917/) (2025)
- [Thoughts without Thinking: Reconsidering the Explanatory Value of Chain-of-Thought Reasoning in LLMs through Agentic Pipelines](https://mlsanity.com/paper/2505.00875/) (2025)
- [Compositional Reasoning with Transformers, RNNs, and Chain of Thought](https://mlsanity.com/paper/2503.01544/) (2025)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [Do Language Models Track Entities Across State Changes?](https://mlsanity.com/paper/2605.30233/) (2026)
- [Parity, Sensitivity, and Transformers](https://mlsanity.com/paper/2602.05896/) (2026)
- [The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures](https://mlsanity.com/paper/2510.05364/) (2025)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [Efficient Turing Machine Simulation with Transformers](https://mlsanity.com/paper/2512.00003/) (2025)
- [On the Spatiotemporal Dynamics of Generalization in Neural Networks](https://mlsanity.com/paper/2602.01651/) (2026)
- [Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth](https://mlsanity.com/paper/2602.11175/) (2026)
- [The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought](https://mlsanity.com/paper/2605.18079/) (2026)
- [The Impossibility of Inverse Permutation Learning in Transformer Models](https://mlsanity.com/paper/2509.24125/) (2025)
- [Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently](https://mlsanity.com/paper/2511.17852/) (2025)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)
- [Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation](https://mlsanity.com/paper/2605.30757/) (2026)
- [A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention](https://mlsanity.com/paper/2602.01763/) (2026)
- [Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs](https://mlsanity.com/paper/2602.02909/) (2026)
- [The Library Theorem: How External Organization Governs Agentic Reasoning Capacity](https://mlsanity.com/paper/2603.21272/) (2026)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [The Deterministic Horizon: When Extended Reasoning Fails and Tool Delegation Becomes Necessary](https://mlsanity.com/paper/2606.00376/) (2026)
- [BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoning](https://mlsanity.com/paper/2507.23170/) (2025)
- [On the Expressive Power of Transformers](https://mlsanity.com/paper/2608.12671/) (2026)
- [Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers](https://mlsanity.com/paper/2608.31067/) (2026)
- [Ceiling of a Task: When Can a Transformer Succeed Without Its Chain of Thought?](https://mlsanity.com/paper/2609.33134/) (2026)

## 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.