The Expressive Power of Transformers with Chain of Thought
作者: William Merrill, Ashish Sabharwal
分类: cs.LG, cs.CC, cs.CL, cs.LO
发布日期: 2023-10-11 (更新: 2024-04-11)
备注: 9-page preprint. ICLR camera ready posted April 11
💡 一句话要点
提出链式思维提升变换器推理能力
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 变换器 链式思维 推理能力 复杂性理论 自然语言处理 正则语言 多项式时间
📋 核心要点
- 现有的标准变换器在处理某些推理问题时存在无法解决的局限性，影响其应用效果。
- 论文提出通过引入中间生成步骤，利用链式思维或草稿板来增强变换器的推理能力。
- 研究结果表明，增加解码步骤数量能显著提升变换器的能力，尤其是线性步骤能识别正则语言。
📝 摘要（中文）
近期的理论研究发现，标准变换器在处理某些简单推理问题时存在局限性，例如判断图中两个节点是否相连或模拟有限状态机。然而，通过允许变换器生成和依赖中间令牌序列，即使用“链式思维”或“草稿板”，可以显著提升其推理能力。本文探讨了中间生成是否从根本上扩展了仅解码器变换器的计算能力。研究表明，增加中间生成的步骤数量会显著提升变换器的能力，尤其是线性步骤能让变换器识别所有正则语言，并且在多项式步骤下，能够精确识别多项式时间可解问题，这是对变换器在标准复杂性类中的首次精确表征。
🔬 方法详解
问题定义：本文旨在解决标准变换器在处理某些推理问题时的局限性，尤其是无法有效解决的简单推理任务。现有方法在面对复杂输入时，推理能力不足，导致无法满足实际应用需求。
核心思路：论文的核心思路是通过引入中间生成步骤，允许变换器在回答之前生成和依赖一系列中间令牌，从而增强其推理能力。这种设计使得变换器能够在推理过程中进行更复杂的状态转换。
技术框架：整体架构包括输入处理、链式思维生成和最终输出三个主要模块。首先，输入被处理并传递到生成模块，生成中间令牌序列，最后根据这些中间结果生成最终答案。
关键创新：最重要的技术创新在于通过中间生成步骤的引入，显著扩展了变换器的计算能力，使其能够识别正则语言和多项式时间可解问题。这一创新与现有方法的本质区别在于，标准变换器通常只依赖一次性输入，而新方法允许多次状态更新。
关键设计：在设计中，论文采用了对数和线性数量的解码步骤，并引入了投影预归一化的概念，以优化变换器的性能。损失函数和网络结构经过精心调整，以确保在不同复杂性类中表现出色。
📊 实验亮点
实验结果显示，使用线性数量的解码步骤，变换器能够识别所有正则语言，并在多项式步骤下精确识别多项式时间可解问题。这一成果标志着对变换器能力的首次精确表征，显著提升了其在复杂推理任务中的应用潜力。
🎯 应用场景
该研究的潜在应用领域包括自然语言处理、图像理解和复杂系统模拟等。通过提升变换器的推理能力，可以在更复杂的任务中实现更高的准确性和效率，具有重要的实际价值和广泛的未来影响。
📄 摘要（原文）
Recent theoretical work has identified surprisingly simple reasoning problems, such as checking if two nodes in a graph are connected or simulating finite-state machines, that are provably unsolvable by standard transformers that answer immediately after reading their input. However, in practice, transformers' reasoning can be improved by allowing them to use a "chain of thought" or "scratchpad", i.e., generate and condition on a sequence of intermediate tokens before answering. Motivated by this, we ask: Does such intermediate generation fundamentally extend the computational power of a decoder-only transformer? We show that the answer is yes, but the amount of increase depends crucially on the amount of intermediate generation. For instance, we find that transformer decoders with a logarithmic number of decoding steps (w.r.t. the input length) push the limits of standard transformers only slightly, while a linear number of decoding steps, assuming projected pre-norm (a slight generalization of standard pre-norm), adds a clear new ability (under standard complexity conjectures): recognizing all regular languages. Our results also imply that linear steps keep transformer decoders within context-sensitive languages, and polynomial steps with generalized pre-norm make them recognize exactly the class of polynomial-time solvable problems -- the first exact characterization of a type of transformers in terms of standard complexity classes. Together, this provides a nuanced framework for understanding how the length of a transformer's chain of thought or scratchpad impacts its reasoning power.