o1方法性能无上限！姚班马腾宇等数学证明：推理token够多，就能解决任意问题

86 0 0

文章摘要

【关键词】 Transformer、思维链、图灵完备、模拟电路、华人学者

在最新的研究中，斯隆奖得主马腾宇和Google Brain推理团队创建者Denny Zhou联合证明了Transformer模型在引入思维链（Chain of Thought, CoT）后，理论上能够解决任何问题，这一发现为Transformer实现图灵完备性提供了可能性。他们的研究结果表明，只要思维链足够长，Transformer就可以模拟任意多项式大小的数字电路，这一论文已被ICLR 2024收录。

研究的核心是CoT对Transformer表达能力的提升。在不使用CoT的情况下，Transformer模型的表达能力受限于AC0问题类别，这类问题可以在并行计算中高效解决，但不包括需要复杂序列化计算的问题。然而，当引入CoT后，即使是固定深度、常数精度的Transformer模型也能解决任何由大小为T的布尔电路解决的问题，显著扩展了模型的表达能力。

为了验证这一理论，研究者在四个核心问题上进行了实验：模运算、置换群组合、迭代平方和电路值问题。实验结果显示，CoT在提高模型在这些任务上的准确性方面具有显著效果。特别是在置换群复合任务和迭代平方任务中，CoT使得即使是低深度的Transformer模型也能高效学习，而在电路值问题中，CoT使得模型即使在深度较低的情况下也能解决P完全问题。

此外，研究者还证明了对于任意一个可以用多项式大小的布尔电路计算的函数，都存在一个仅有常数层数的Transformer，可以通过足够多步数的思维链来模拟电路的计算过程。这一证明的关键是通过CoT逐步模拟电路中每个门的计算，从而实现对整个电路的模拟。

尽管这项研究在理论上展示了CoT的巨大潜力，但实际应用中仍存在一系列挑战。例如，有限的上下文窗口和计算资源限制了模型的实用性。此外，实验假设模型权重被正确设置，而实际模型训练很难达到这一理想状态。还有观点认为，这种模拟门电路运算并不是大模型实际学习和工作的方式，将实际问题用布尔电路表示是Transformer解决实际问题的关键。

尽管如此，这项研究至少揭示了CoT在提升Transformer模型能力方面的潜力，为未来的研究和应用提供了新的方向。论文的四位作者均为华人，包括清华姚班校友李志远、Hong Liu、Denny Zhou和马腾宇。论文的详细内容可以在arXiv上找到。