🤖 machine learning

Efficiently Representing Algorithms With Chain-of-Thought Transformers

本文证明了思维链 Transformer 可以仅以多项对数级的开销高效地模拟 Word RAM 算法，其性能显著优于模拟图灵机所需的平方级开销。

原作者： Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

发布于 2026-06-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你有一个超级聪明的机器人（Transformer），它正在试图解决一个复杂的谜题。为了帮助自己，这个机器人被允许在给出最终答案之前，一步步地写下它的思考过程。这被称为思维链（Chain-of-Thought, CoT）。

长期以来，科学家们知道这个机器人从理论上讲可以解决任何问题，就像 1930 年代的经典计算机（图灵机）一样。但这里有一个限制：经典计算机就像一个正在阅读长卷轴的人。为了找到中间的一个特定词汇，他们必须从头开始，缓慢地向下滚动眼睛。这既慢又不高效。

现实世界的计算机（以及我们在教科书中学习的算法）则不同。它们就像一个拥有神奇文件柜的图书管理员，无论文件藏在书架多深的地方，他们都能瞬间取走。这被称为 Word RAM。

问题在于：
论文提出了一个问题：我们的超级智能机器人能否利用它的“思维标记”（thought tokens）来扮演那位神奇图书管理员的角色，还是只能被迫做一个缓慢的“卷轴阅读者”？

之前的研究认为，机器人确实可以做任何事，但前提是它必须付出巨大的额外时间代价（比如将步骤数进行平方）。如果图书管理员的任务需要 100 步，那么机器人可能需要 10,000 步才能搞清楚如何滚动到正确的位置。这对于实际应用来说太慢了。

解决方案：
这篇论文的作者说：“是的，机器人可以成为图书管理员，而且它可以做得几乎和教科书所说的那么快。”

他们证明了，通过一些巧妙的技巧，机器人可以模拟这些高效的“即时访问”算法，而产生的额外时间开销非常小（即“多项式对数级”开销，这是一种高级说法，意思是非常小且可控的额外步骤）。

以下是他们是如何实现的，我们通过给机器人换上三种不同的“装束”来理解：

1. “不断增长的背包”（多项式对数宽度）

想象机器人的背包会随着谜题规模的增大而略微变大。

工作原理： 机器人将它的思考过程写成一串二进制数字（0 和 1）的列表。因为背包足够大，可以一次性装下整个数字，所以它可以瞬间进行数字比较并找到正确的文件。
代价： 背包需要成长。如果谜题非常庞大，机器人就需要一个更大的背包。这不是一个“万能型”机器人；它需要为每一个新的谜题规模定制一个尺寸合适的背包。

2. “魔法隐形墨水”（连续思维链）

想象机器人不仅是在纸上写字，它还留下了只有它自己能看到的、发光的隐形笔记。

工作原理： 机器人不再只是写出数字的每一个位（比如 101101），而是写下一个代表整个数字的单一“发光向量”（一种数学形状）。它可以带着这个发光笔记在每一步之间传递。
技巧： 当机器人需要读取特定数字时，它会观察自己的发光笔记。它可以瞬间“放大”到正确的笔记上。如果它需要将一个数字拆解成位来进行数学运算，它可以将发光笔记逐位“展开”，完成计算，然后再将其“重新卷回”成发光笔记，供下一步使用。
优势： 机器人的体积保持不变（固定宽度），但它利用这种“魔法墨水”来追踪复杂的数据，而不会迷失方向。

3. “带有记忆循环的机器人”（混合模型）

想象机器人有一个标准的“大脑”（Transformer），但在其下方还有一个小型、连续的循环磁带（线性 RNN）在运行。

工作原理： 标准的大脑擅长回顾整个历史记录。而循环磁带则擅长记住“即时”的过去。
技巧： 机器人使用循环磁带来承载“发光笔记”（就像第二种方法那样），并在解谜过程中向前推进。它不需要魔法墨水；它只是利用磁带来传递状态。这使得它能够实现与“魔法墨水”法相同的、高效的“即时访问”模拟，而且使用的是一种更标准、更具物理感的架构。

核心结论

论文证明了，思维链并不只是模拟旧式计算机的一种缓慢、笨拙的方式。 通过使用这些特定的架构技巧，Transformer 实际上可以运行现代的高效算法（例如对列表进行排序或在地图上寻找最短路径），其速度几乎可以达到这些算法设计的预期速度。

他们消除了由于将机器人视为“缓慢卷轴阅读者”而导致的“平方级惩罚”（巨大的减速）。现在，机器人可以表现得像一个现代图书管理员，能够瞬间抓取文件并高效地解决教科书级别的难题。

简而言之： 论文表明，只要拥有正确的工具，AI 模型就可以不再仅仅是缓慢的理论机器，而是可以成为高效、实用的问题解决者，就像我们每天使用的计算机一样。

技术摘要：利用思维链 Transformer 高效表示算法

问题陈述

虽然已有研究证实，思维链（Chain-of-Thought, CoT）Transformer 在原理上是图灵完备的，能够模拟任何算法（Pérez 等人，2021；Merrill 和 Sabharwal，2024），但现有的理论构建依赖于对图灵机（TM）的模拟。这种方法引入了一个根本性的低效问题：图灵机缺乏随机访问存储器（RAM），需要通过线性扫描来访问数据。因此，通过基于图灵机的 CoT 来模拟标准教科书算法（例如对 $n$ 个项目进行排序或运行 Dijkstra 算法）会产生相对于算法原生复杂度的二次方开销（ $O(t^2)$ ）。

本文旨在解决理论通用性与实际效率之间的差距。它探讨了 CoT Transformer 是否可以直接模拟以 Word RAM 模型编写的算法——这是现代算法的标准抽象，假设在 $O(\log n)$ 位字（word）上的操作具有单位成本，并支持随机内存访问——且不产生与模拟图灵机相关的二次方惩罚。

方法论

作者提出了在三种不同的架构设置下，使用 CoT Transformer 直接模拟 Word RAM 程序的方法。核心挑战在于如何在保持高效读写操作的同时，在 Transformer 的残差流（residual stream）中表示和操作 $w$ 位字（其中 $w = \Theta(\log(n+t))$ ）。

1. 多对数宽度 Transformer（有限精度）

架构： 具有固定精度但宽度随 $O(\log^2 n)$ 增长的 Transformer。它们利用 右侧唯一硬注意力（Rightmost-Unique Hard Attention, UHAT）。
表示： 整数以二进制向量的形式存储在残差流中。
机制： 模拟过程将每一次内存写入都记录在 CoT 转录中，表现为一系列地址-数值位对（address-value bit pairs）。读取操作涉及识别匹配查询地址的最右侧内存块。
复杂度：
- 通用 Word RAM 指令：每个 RAM 步骤需要 $O(w^2)$ 个 CoT token。
- 无乘法指令：每个 RAM 步骤需要 $O(w)$ 个 CoT token。
- 总开销： $O(t \log^2(n+t))$ 或 $O(t \log(n+t))$ 。

2. 具有连续 CoT 的定宽 Transformer

架构： 固定宽度、对数精度的 Transformer，其推理步骤发射的是 连续向量（软 token） 而非离散 token。
表示： 数值使用 层归一化哈希（Layer-Norm Hashes, $\phi(v)$ ） 进行编码，这是一种单位范数向量表示，允许通过内积进行相等性检查。
机制：
- 序列化： 将哈希 $\phi(v)$ 转换为二进制位流需要迭代除法（计算 $\lfloor v/2 \rfloor$ 和 $v \mod 2$ ）。这通过一种“受限”的 Word RAM 标准型实现，其中步骤 $s$ 处的数值 $v$ 满足 $v \le s$ 。
- 持久性： 软 token 作为持久寄存器，在解码步骤之间携带当前状态（ $\phi(v)$ ），而无需重新序列化数值。
- Oracle（神谕）： 复杂的算术运算由一个在序列化位流上运行的 TM-oracle 子程序处理，结果随后被反序列化回哈希表示。
复杂度： $O(t \cdot \kappa(w))$ 个解码步骤，其中 $\kappa(w)$ 是单条指令的 TM 代价。对于扁平指令集，这产生 $O(t \log^2(n+t))$ （全算术）或 $O(t \log(n+t))$ （简单算术）的复杂度。

3. 混合 Transformer-RNN 模型

架构： 由单个 线性 RNN 层 增强的定宽 Transformer。
机制： 该设置使用 RNN 的隐藏状态取代了前一个模型中的连续软 token 以维持持久性。RNN 执行迭代式的位提取与重建（序列化/反序列化），这在之前是通过连续向量完成的。
复杂度： 与连续 CoT 的结果一致： $O(t \cdot \kappa(w))$ 步。

核心贡献

直接 Word RAM 模拟： 本文证明了 CoT Transformer 可以直接模拟 Word RAM 算法，绕过了中间的图灵机层。
紧凑的开销界限：
- 对于离散 CoT（多对数宽度）：每个指令的开销为 $O(w^2)$ ，这与 $\Omega(w)$ 的信息论下界仅差一个对数因子。
- 对于无乘法指令集：每个指令的开销恰好为 $O(w)$ ，这对于离散 CoT 而言是优化的。
- 这与基于 TM 的模拟形成了鲜明对比，后者需要 $O(t^2)$ 步。
提升效率的架构扩展： 作者证明，如果通过 连续 CoT 或 线性 RNN 层 进行增强，定宽 Transformer 可以实现这些高效模拟，这些扩展解决了定宽离散模型中位提取和状态持久性的瓶颈。
受限 Word RAM 等价性： 一个技术引理表明，任何 Word RAM 都可以由一个“受限”版本模拟，在该版本中，步骤 $s$ 处的数值受到 $s$ 的限制，从而便于在定宽设置下进行位提取证明。

结果

本文确立了 CoT Transformer 可以执行具有仅 多对数级（poly-logarithmic） $n$ 开销（具体为每个步骤 $O(\log^2 n)$ 或 $O(\log n)$ ）的教科书级算法。

排序： 可在 $O(n \log n \cdot \text{polylog}(n))$ 步内完成。
Dijkstra 算法： 可在 $O((E + V \log V) \cdot \text{polylog}(n))$ 步内完成。
指令集： 这些结果对于“扁平”指令集（无嵌套表达式）成立。对于全算术指令集（包括 $\times, \div, \mod$ ），开销为 $O(\log^2 n)$ ；对于简单算术指令集（排除 $\times, \div, \mod$ ），开销降至 $O(\log n)$ 。

意义与主张

本文声称填补了 Transformer 的理论能力（图灵完备性）与算法推理所需的实际效率之间的鸿沟。通过展示 CoT 可以以近乎最优的开销模拟 Word RAM，作者认为此前认为进行算法模拟必须存在“二次方膨胀”的假设，实际上是 TM 抽象带来的产物，而非 Transformer 本身的固有局限。

其意义在于：

理论证明： 为 CoT 推理模型为何能高效解决复杂算法任务提供了形式化基础，使理论表达能力与推理模型（如 Snell 等人，2024；DeepSeek-AI，2025）的经验观察相一致。
架构洞察： 确定了特定的、现实的扩展（连续 CoT 或 RNN 层）足以使定宽模型实现高效的算法模拟，这表明这些特性对于实际的算法推理至关重要。
最优性： 证明了所提出的模拟对于离散 CoT 而言基本上是紧致的，达到了信息论下界。

作者对于这些扩展是否为必要保持了审慎态度，指出在其他语境下，连续 CoT 或 RNN 层是否严格必要，以及这些扩展是否能惠及当前的实际算法推理，仍是一个开放性问题。