揭示硬注意力Transformer中思维链步骤的理论下界
Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
- 从算法问题出发，系统推导思维链步骤的理论下界
- 对多种问题给出紧致至对数因子的下界估计
- 为思维链能力与局限提供理论依据，适合模型研究者
思维链推理与草稿区已成为提升Transformer计算能力的关键工具。尽管理论表明，多项式长度的草稿区可使Transformer的表达能力从TC⁰扩展至PTIME，但其所需长度仍不明确。实证发现，即使在TC⁰中的问题（如奇偶性、乘法）也需草稿区，挑战了电路复杂性推导的乐观估计。本文首次系统研究硬注意力情形下不同算法问题的思维链步骤下界，对多种问题给出紧致至对数因子的边界。结果有助于深化对思维链推理能力与局限的理解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。