arXiv:2502.02393cs.LG
Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
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^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.
Subbarao Kambhampati and his team has several papers strongly suggesting that the intermediate tokens are of no symantic import.[0] My hunch is that training explicitly for human acceptance of the intermediate/scratch tokens will end up being expensive. What you need is to…
nyrikkiView on HNParent context