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

2025/02/04 by Alireza Amiri, Xinting Huang, Amiri, Alireza +5 · 2 voices · 12 citations
Computer Science · Engineering · Neuroscience · #Advanced Memory and Neural Computing #Computer science #EEG and Brain-Computer Interfaces #Electrical engineering #Engineering #Transformer #Visual Attention and Saliency Detection #cs.CC #cs.LG

paper · pdf · doi:10.48550/arxiv.2502.02393

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/02/04 · arxiv published 2025/02/04 · arxiv updated 2025/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 TC⁰ to PTIME, their required length remains poorly understood. Empirical evidence even suggests that transformers need scratchpads even for many problems in TC⁰, 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.

Cited by

• Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently
• Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training
• Benefits and Limitations of Communication in Multi-Agent Reasoning
• The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures
• Efficient Turing Machine Simulation with Transformers
• A Formal Comparison Between Chain-of-Thought and Latent Thought
• BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoning
• Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities
• Behavior Injection: Preparing Language Models for Reinforcement Learning
• Diffusion LLMs can think EoS-by-EoS
• Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
• Do Language Models Track Entities Across State Changes?

Discussions

• This new draft claims to give lower bounds on chain-of-though iterations, with hard attention, needed to solve PARITY and some other tasks (which is pretty cool!) arxiv.org/abs/2502.02393 [bsky, 1 points, 0 comments]
• 8/8 Big thanks to my co-authors Alireza, Xinting, and Mark! 🔗 Read the paper: arXiv.org/abs/2502.02393 [bsky, 0 points, 0 comments]

Related

• The Expressive Power of Transformers with Chain of Thought
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
• Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
• Analyzing the Power of Chain of Thought through Memorization Capabilities
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective