Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer

📄 arXiv: 2409.09239v3 📥 PDF

作者: Xiang Zhang, Muhammad Abdul-Mageed, Laks V. S. Lakshmanan

分类: cs.CL, cs.AI

发布日期: 2024-09-14 (更新: 2024-09-20)

💡 一句话要点

研究Transformer计算能力的局限性，并探讨CoT如何弥补循环计算的缺失。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Transformer 循环神经网络 思维链 计算能力 自回归模型 语言模型 循环完备性

📋 核心要点

  1. Transformer模型缺乏循环连接，导致其在计算能力上存在局限性，难以处理如计数、字符串反转等任务。
  2. 论文提出CoT方法可以模拟循环计算，弥补Transformer在处理复杂任务时的不足，提升模型性能和计算能力。
  3. 论文分析了现有循环Transformer模型的理论局限性，提出了“循环完备性”概念，旨在指导更好的模型设计。

📝 摘要（中文）

Transformer架构在各种语言建模任务中表现出色，超越了传统的RNN和LSTM等神经架构。这部分归功于它消除了循环连接，从而实现了并行训练和更平滑的梯度流动。然而，这种远离循环结构的举动将Transformer模型置于乔姆斯基计算层次结构的较低端，限制了其计算能力。因此，即使是基于Transformer的先进模型在计数、字符串反转和乘法等任务中也面临着相当大的困难。这些任务虽然看似简单，但需要的计算复杂度超出了Transformer架构的能力。与此同时，“思维链”（CoT）提示的出现使基于Transformer的语言模型能够处理以前不可能或执行不佳的任务。在这项工作中，我们彻底研究了神经模型中循环结构对其推理能力和可计算性的影响，对比了自回归在神经模型计算能力中所扮演的角色。然后，我们阐明了CoT方法如何模拟循环计算，并充当语言模型中自回归和循环之间的桥梁。正是这种近似的循环显著提高了模型的性能和计算能力。此外，我们重新审视了最近基于循环的Transformer模型设计，通过我们提出的“循环完备性”概念来关注它们的计算能力，并识别了线性Transformer和RWKV等模型中的关键理论局限性。通过这一点，我们旨在深入了解神经模型架构，并促进更好的模型设计。

🔬 方法详解

问题定义：Transformer模型虽然在很多NLP任务上表现出色，但由于其缺乏循环结构，导致其在处理需要循环计算的任务（如计数、字符串反转等）时表现不佳。现有的Transformer模型在计算能力上存在局限性，无法很好地处理这些任务。

核心思路：论文的核心思路是探讨循环结构在神经模型中的作用，并研究如何通过其他方式（如CoT）来模拟循环计算，从而提升Transformer模型的计算能力。CoT通过逐步推理的方式，将复杂问题分解为多个简单步骤，从而模拟了循环计算的过程。

技术框架：论文主要通过理论分析和实验验证来研究循环结构和CoT对模型计算能力的影响。首先，论文分析了Transformer模型的计算能力局限性，然后探讨了CoT如何模拟循环计算。最后，论文重新审视了现有的循环Transformer模型，并提出了“循环完备性”的概念。

关键创新：论文的关键创新在于提出了CoT可以模拟循环计算的观点，并将其视为连接自回归和循环的桥梁。此外，论文还提出了“循环完备性”的概念，用于评估循环Transformer模型的计算能力。

关键设计：论文主要关注理论分析，并没有提出新的模型结构或算法。但是，论文对CoT的使用方式和循环Transformer模型的设计提出了新的见解，可以指导未来的模型设计。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文通过理论分析和实验验证，证明了CoT可以有效提升Transformer模型在需要循环计算的任务上的表现。虽然论文没有给出具体的性能数据，但其提出的观点和分析框架对未来的模型设计具有重要的指导意义。

🎯 应用场景

该研究成果可应用于提升语言模型在需要复杂推理和计算的任务上的表现，例如数学问题求解、逻辑推理、代码生成等。通过模拟循环计算，可以使模型更好地处理序列依赖关系，从而提高模型的泛化能力和鲁棒性。

📄 摘要（原文）

The Transformer architecture excels in a variety of language modeling tasks, outperforming traditional neural architectures such as RNN and LSTM. This is partially due to its elimination of recurrent connections, which allows for parallel training and a smoother flow of gradients. However, this move away from recurrent structures places the Transformer model at the lower end of Chomsky's computational hierarchy, imposing limitations on its computational abilities. Consequently, even advanced Transformer-based models face considerable difficulties in tasks like counting, string reversal, and multiplication. These tasks, though seemingly elementary, require a level of computational complexity that exceeds the capabilities of the Transformer architecture. Concurrently, the emergence of Chain of Thought" (CoT) prompting has enabled Transformer-based language models to tackle tasks that were previously impossible or poorly executed. In this work, we thoroughly investigate the influence of recurrent structures in neural models on their reasoning abilities and computability, contrasting the role autoregression plays in the neural models' computational power. We then shed light on how the CoT approach can mimic recurrent computation and act as a bridge between autoregression and recurrence in the context of language models. It is this approximated recurrence that notably improves the model's performance and computational capacity. Moreover, we revisit recent recurrent-based Transformer model designs, focusing on their computational abilities through our proposed concept ofrecurrence-completeness" and identify key theoretical limitations in models like Linear Transformer and RWKV. Through this, we aim to provide insight into the neural model architectures and prompt better model design.