Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
This work addresses the theoretical limitations of chain-of-thought reasoning in transformers, which is crucial for understanding their computational capabilities in AI and machine learning.
The paper tackled the problem of determining lower bounds for the number of chain-of-thought steps required in hard-attention transformers across various algorithmic problems, providing bounds that are tight up to logarithmic factors.
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^0$ to $PTIME$, their required length remains poorly understood. Empirical evidence even suggests that transformers need scratchpads even for many problems in $TC^0$, 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.