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

Alireza Amiri Bavandpour; Xinting Huang; Mark Rofin; Michael Hahn

2025 ICML ICML 2025

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

Abstract

No abstract available. No abstract was captured for this paper when its proceedings were scraped - most often an older edition published without one online. How the corpus is built.

Authors

Alireza Amiri Bavandpour, Xinting Huang, Mark Rofin, Michael Hahn

Topics

Machine Learning > Optimization & Theory > Learning Theory Deep Learning > Architectures > Transformers Artificial Intelligence > Core AI > Large Language Models

Keywords

chain-of-thought reasoning expressivity lower bound hard-attention transformers scratchpad tc^0

Download PDF