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

Alireza Amiri, Xinting Huang, Mark Rofin +1

Chain-of-thought reasoning and scratchpads have emerged as critical tools for enhancing the computational capabilities of transformers. While theoretical results show that polynomi…