Efficiently Representing Algorithms with Chain-of-Thought Transformers¶
会议: NeurIPS 2026
arXiv: 2606.19697
代码: https://github.com/allenai/cot-word-ram
领域: Reasoning
关键词: 思维链 (CoT), Word RAM, 计算复杂性, 算法模拟, 混合架构
一句话总结¶
证明了思维链 (CoT) Transformer 无需承受图灵机模拟带来的二次计算膨胀，能够以多对数级（Polylogarithmic）极低开销直接高效模拟 Word RAM 教科书级算法。
研究背景与动机¶
大语言模型的推理能力近期受到思维链机制的极大启发，而理论界通常依赖 Transformer 对图灵机（Turing Machine, TM）的计算通用性模拟（Turing Completeness）来解释 CoT 的有效性。然而，图灵机虽然适合传统计算复杂性理论的渐近划分，却与现代算法设计与实际运行模式存在根本性错配。真实世界的算法大多建立在随机存取机（Word RAM）抽象之上，支持以 \(O(1)\) 时间开销对宽为 \(w = \Theta(\log(n+t))\) 位的字进行任意内存单元随机寻址与字级算术操作；例如 \(n\) 个元素的排序在 Word RAM 上仅需 \(O(n \log n)\) 步，Dijkstra 最短路径仅需 \(O(E + V \log V)\) 步。
若直接将经典 Word RAM 算法经由图灵机中介转换为 Transformer 的 CoT 序列，由于图灵机缺乏真正的随机寻址能力，每一步内存访问都必须扫描长度达 \(O(n+t)\) 的磁带，导致原本 \(t\) 步的 Word RAM 程序在图灵机上退化至 \(O(t^2)\) 步，迫使离散 CoT 生成至少 \(O(t^2)\) 个推理 token。这就产生了一个基础性理论疑问：CoT Transformer 能否绕过低效的图灵机中间层，直接以接近教科书级算法复杂度的低开销模拟 Word RAM？
本文正是针对这一核心痛点展开攻关，指出 CoT 序列自身具备的自回归只追加（Append-only）与注意力寻址特性，天然契合构建随机访问内存日志。核心 idea：直接在 Transformer 的 CoT 生成步骤中实现基于注意力的 Word RAM 内存读写日志，通过多对数宽度、连续 CoT（Continuous CoT）或线性 RNN 混合架构三种路径，将算法模拟开销从二次爆炸 \(O(t^2)\) 压缩到仅需多对数级的 \(O(t \log^2(n+t))\) 甚至 \(O(t \log(n+t))\)。
方法详解¶
整体框架¶
本文构建了从 Word RAM 高层指令到 Transformer 解码生成的端到端直接映射。机器的全部全局状态（程序计数器 pc、通用寄存器 \(r_1, \dots, r_k\) 以及动态读写数组 mem）统一折叠并编码为单一地址空间 mem，通过向 CoT 记录形如 mem # bits(a) # bits(v) 的内存更新日志实现状态持久化。针对不同架构假设，论文提出了三种可行的模拟设定：其一是定点精度、\(\mathcal{O}(\log^2 n)\) 宽度的右侧唯一硬注意力 Transformer（Rightmost UHAT）；其二是固定宽度、对数精度的连续思维链（Continuous CoT）；其三是固定宽度底层堆叠线性 RNN 层的混合模型（Hybrid Transformer-RNN）。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Word RAM 指令与状态输入<br/>pc / 寄存器 / 内存数组折叠为 mem[a]"] --> B["受限 Word RAM 正规化<br/>字长缩减与数值界限保证 v ≤ t"]
B --> C["分块执行流水线<br/>读 pc 与操作数 → 执行运算 → 生成写入快照"]
C --> D["右侧注意力寻址与字级序列化<br/>UHAT / 连续软向量 / 线性RNN 动态读写"]
D --> E["极低开销 CoT 输出序列<br/>每步仅需 O(w) 或 O(w²) 步推理生成"]关键设计¶
1. 受限 Word RAM 等价正规化：消除数值越界以支持注意力除法
在定宽 Transformer 中利用 LayerNorm Hash 向量表示数值时，从哈希状态中解构并逐位提取二进制位的核心瓶颈在于：注意力机制只能在数值不超过当前序列位置（\(v \leq \tau\)）的前提下完成除以 2 与取模操作。本文证明了任意字长为 \(w = c \log(n+t)\) 的标准 1 维 Word RAM 均可等价转化为字长为 \(w' = \log(n+t)\) 的 \(c\) 维受限 Word RAM，且时间开销仅增加常数倍。进一步地，通过在前置阶段引入 \(v(n)\) 步空操作延迟，使得在任意时刻 \(i\) 寄存器与内存中的所有数值 \(v\) 严格满足 \(v \leq i\)。这一正规化转换保证了后续注意力机制能够可靠利用简化的除法引理（Simplified Division Lemma），通过查询键值匹配在常数深度内从 \(\phi(v)\) 迭代提取最低有效位 \(\phi(v \bmod 2)\) 与商 \(\phi(\lfloor v/2 \rfloor)\)。
2. 右侧唯一硬注意力（Rightmost UHAT）内存检索机制
在定点精度、多对数宽度的离散 CoT 设定下，恢复内存单元 mem[a] 的最新值等价于在整个历史 CoT 序列中找到最靠近右侧的地址匹配块。普通平均硬注意力或左侧注意力在定点精度下受限于严格单调性与有界性的矛盾，无法区分并选出最靠后的匹配项。本文采用右侧唯一硬注意力机制，先通过地址匹配头计算当前查询地址与历史所有 mem 块键字段的点积，唯一锁定最靠近右侧的最大匹配位置；紧接着第二层注意力基于已提取的位置编码施加固定偏移量 \(w+1\)，并行召回其后的值字段 \(w\) 个二进制 token。全流程在两层注意力与常数深度内精确完成，彻底实现了 \(O(1)\) 的 Word RAM 内存读取在 Transformer 架构内的等价投射。
3. 连续思维链与软标记传递（Continuous CoT）：固定宽度的状态保持
在保持固定模型宽度与对数精度的更具实用价值的设定中，模型无法在残差流中同时开辟多达 \(w\) 维的坐标向量来并发展平字的所有比特。论文引入连续思维链设定，允许 Transformer 每步不仅输出离散词表 token，还输出一个低维实数连续软标记（Soft Token）\(p_i \in \mathbb{R}^{d_s}\)。通过 LayerNorm Hash 编码 \(\phi(v) = \frac{(v, 1, -v, -1)}{\sqrt{2v^2 + 2}}\)，软标记能够无损暂存当前的地址-数值对 \((\phi(a), \phi(v))\)。在执行单步 RAM 指令时，模型拆分为 6 个微阶段：读取 pc、载入操作数、将哈希位逐位串行化至工作磁带、激活图灵机子网络执行运算、反序列化回哈希状态、写入新检查点软标记。这种方式彻底解耦了序列长度与模型宽度，且每步指令只需 \(\mathcal{O}(\kappa(w))\) 步解码，其中简单算术下 \(\kappa(w) = \mathcal{O}(w)\)。
4. 线性 RNN 混合架构：利用对角状态递推替代软标记
为了在标准离散输出下实现与连续 CoT 相同的定宽模拟，本文进一步提出了在 Transformer 底部叠加单层线性 RNN 的混合架构（Hybrid Model）。线性 RNN 隐状态更新公式满足 \(S_{t+1} = A_t S_t + b_t\)。针对序列化过程，当从 \(\phi(v_k)\) 提取出比特 \(b_k\) 后，更新到 \(\phi(\lfloor v_k / 2 \rfloor) = \phi(\frac{1}{2}(v_k - b_k))\) 本质上是一个仿射变换。论文设计了仅包含低秩与对角结构的转移矩阵 \(B_0, B_1 \in \mathbb{R}^{4 \times 4}\)，使得 RNN 隐状态能够在逐步吐出离散位 \(b_k\) 的同时，自动在内部更新并保留缩半后的哈希未归一化状态，再通过 LayerNorm 投影回残差流。而在反序列化时，RNN 同样利用 \(h_\ell = \frac{1}{2} h_{\ell-1} + b_{\ell-1}\) 的移位累加性质，以完全离散的 token 驱动完成字级构建，展现了状态空间模型（SSM / Linear RNN）与注意力协同模拟复杂控制流的独特优势。
复杂度分析与理论保证¶
根据指令集中运算原语的复杂度差异，模拟开销在不同设定下的理论边界保证如下： 1. 简单算术扁平指令集（包含加法、减法、位移、位运算等，不含乘除模）：单条指令在离散多对数宽度下需要 \(\mathcal{O}(w)\) 个 CoT token，连续 CoT 与混合模型同样仅需 \(\mathcal{O}(w) = \mathcal{O}(\log(n+t))\) 步解码，完美逼近离散 CoT 的信息论下界 \(\Omega(t \cdot w)\)。 2. 完全算术扁平指令集（包含乘法、整数除法、取模）：因乘除无法在常数深度纯 MLP 中单步求解，被编译为 \(w\) 个扁平微步（Micro-steps），总解码步数为 \(\mathcal{O}(t \cdot w^2) = \mathcal{O}(t \log^2(n+t))\)。
实验关键数据¶
主实验：理论渐进复杂度与模拟开销对比¶
本文主要为纯理论构造性工作，核心成果在于推导并证明了三种 Transformer 变体在模拟各类典型算法与计算模型时的渐进时空复杂度界限。下表系统对比了传统图灵机模拟路径与本文所提出的直接 Word RAM 模拟架构在关键指标上的理论差异。
| 模拟架构与设定 | 浮点精度要求 | 模型宽度 (Width) | 注意力类型 / 算子支持 | 每步 RAM 指令 CoT 开销 | \(t\) 步 RAM 算法总体 CoT 开销 |
|---|---|---|---|---|---|
| 传统 TM 模拟路径 (Pérez et al., 2021) | 定点精度 | \(\mathcal{O}(1)\) 常数 | 标配 Softmax / 严格因果 | \(\mathcal{O}(t)\) (磁带扫描爆炸) | \(\mathcal{O}(t^2)\) (二次膨胀) |
| 本文多对数宽度设定 (Theorem 1) | 定点精度 | \(\mathcal{O}(\log^2(n+t))\) | 右侧唯一硬注意力 (UHAT) | \(\mathcal{O}(w^2)\) (无乘除为 \(\mathcal{O}(w)\)) | \(\mathcal{O}(t \log^2(n+t))\) 或 \(\mathcal{O}(t \log(n+t))\) |
| 本文连续 CoT 设定 (Theorem 3) | \(\mathcal{O}(\log n)\) 对数精度 | \(\mathcal{O}(1)\) 常数固定 | 平均硬注意力 + 软标记 | \(\mathcal{O}(\kappa(w))\) | \(\mathcal{O}(t \cdot \kappa(w))\) |
| 本文混合模型设定 (Theorem 4) | \(\mathcal{O}(\log n)\) 对数精度 | \(\mathcal{O}(1)\) 常数固定 | 平均硬注意力 + 线性 RNN | \(\mathcal{O}(\kappa(w))\) | \(\mathcal{O}(t \cdot \kappa(w))\) |
消融实验：典型教科书算法实际 CoT 步数渐进对比¶
针对计算机科学中几类依赖非局域随机存取与字算术的经典基准算法，对比在 Word RAM 原始步数、传统图灵机 CoT 模拟与本文高效模拟方案下的 CoT 序列长度增长行为：
| 算法任务 | 原始 Word RAM 步数 \(t\) | 传统图灵机 CoT 模拟步数 | 本文直接模拟 (简单算术 / 连续 / 混合) | 渐进复杂度加速比 |
|---|---|---|---|---|
| \(n\) 元素数组排序 (Merge / Quick Sort) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n^2 \log^2 n)\) | \(\mathcal{O}(n \log^2 n)\) | 消除近乎 \(\mathcal{O}(n)\) 级磁带寻道开销 |
| 单源最短路径 (Dijkstra 算法) | \(\mathcal{O}(E + V \log V)\) | \(\mathcal{O}((E + V \log V)^2)\) | \(\mathcal{O}((E + V \log V) \log(V))\) | 保持近线性扩展，避免稠密图平方退化 |
| 动态规划 (0-1 背包问题) | \(\mathcal{O}(n \cdot W)\) | \(\mathcal{O}(n^2 \cdot W^2)\) | \(\mathcal{O}(n \cdot W \log(n+W))\) | 状态随机跳转无需线性扫描完整 DP 表格 |
| 散列表查找与插入 (Hash Table) | 期望 \(\mathcal{O}(1)\) | 悲观 \(\mathcal{O}(t)\) | \(\mathcal{O}(\log(n+t))\) | 保持对数级高效随机访问能力 |
关键发现¶
- 打破图灵机中介的二次计算惩罚：以往认为 CoT 表达能力来自图灵机完备性，导致分析算法时默认带有 \(\Omega(t^2)\) 开销；本文证明 Transformer 的注意力寻址机制本质上是只追加日志上的随机存取器，原生兼容 Word RAM。
- 信息论下界的紧致匹配：任何使用有限字符集的离散 CoT 在输出 \(w\) 位数值时都必然需要 \(\Omega(w)\) 个 token。本文在无乘法简单算术指令集下达到的 \(\mathcal{O}(t \log(n+t))\) 开销，严格在常数因子内达到了信息论最优下界。
- 宽度与递归的等价互换性：多对数宽度提供的空间并发展开能力，可以通过连续软向量或一阶线性递归层（如 RWKV / DeltaNet 形式的线性变换）进行完美替代，揭示了混合架构在复杂算法长程推理中的理论优越性。
亮点与洞察¶
- 将 Attention 视为动态 RAM 索引引擎：巧妙利用 Transformer 跨序列检索的注意力分数峰值特性，将 Key-Value 机制映射为“内存地址比对”与“值单元解引用”，把生成式只追加文本转化为一台具备自洽虚拟内存的计算机。
- LayerNorm Hash 结合受限 RAM 的纯代数解码：引入 \(v \leq i\) 的正规化约束，并结合 \(4 \times 4\) 极简状态转移矩阵，实现了在残差流中无需深层非线性即可完成二进制位解构的高雅构造。
- 为测试期计算缩放（Test-time Compute Scaling）提供坚实算法理论基础：解释了为什么让模型输出显式思考步骤能解决复杂长程算法问题——思考步骤不仅是在分解子目标，更是在外部生成内存寄存器以实现高效算法执行。
局限与展望¶
- 理论构造与实操训练的差距：本文给出的是存在性证明与显式权重构造，未研究如何通过梯度下降或强化学习（如 RL 探索）在真实训练中自发学出该套精密的 RAM 读写协议。
- 乘除法运算的微步展开代价：受限于纯前馈注意力网络的电路深度，乘除取模运算仍需展开为 \(\mathcal{O}(w)\) 个中间微步，导致全算术指令集带有多对数平方项 \(\mathcal{O}(\log^2 n)\) 开销。
- 定宽标准 Transformer 的离散 CoT 存在性悬而未决：在不借助软标记或 RNN 层的严苛条件下，固定宽度、纯离散的普通 Transformer 能否实现多对数开销模拟仍是开放问题。
相关工作与启发¶
- vs Pérez et al. (2021) / Merrill & Sabharwal (2024)：以往开创性工作证明了定深 CoT Transformer 可以模拟图灵机，从而确立了计算通用性，但该路径处理教科书算法时不可避免地引入 \(\mathcal{O}(t^2)\) 的二次时间惩罚；本文首次实现面向 Word RAM 的直接模拟，将开销压制至多对数级。
- vs Strobl et al. (2024) / Li et al. (2024)：形式语言与电路复杂性理论侧重于无思维链或单步 Transformer 识别语言的表达能力界限；本文则聚焦自回归解码动态利用 CoT 充当外置内存存储介质的计算威力。
- vs DeltaNet / RWKV-7 / Mamba 混合模型：经验性研究发现 Transformer 与线性 RNN 融合可加速推理并增强状态记忆；本文从复杂性理论层面证明了仅需单层线性 RNN 即可弥补定宽 Transformer 在位级序列化上的关键缺陷。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ (首次跨越图灵机直接建立 CoT 与 Word RAM 算法的高效映射)
- 实验充分度: ⭐⭐⭐⭐☆ (构造性数学证明极为完备扎实，但缺少神经网络经验性拟合实验)
- 写作质量: ⭐⭐⭐⭐⭐ (结构极为严密清晰，从直觉瓶颈到三种模型逐步推进，推导赏心悦目)
- 价值: ⭐⭐⭐⭐⭐ (为推理模型思维链复杂性提供了现代算法视角下的基石性理论支撑)