Efficiently Representing Algorithms With Chain-of-Thought Transformers

📄 arXiv: 2606.19697v1 📥 PDF

作者: Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

分类: cs.LG, cs.AI, cs.CL

发布日期: 2026-06-18

💡 一句话要点

提出链式思维变换器以高效模拟Word RAM算法

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

关键词: 链式思维变换器 Word RAM 算法模拟 图灵机 高效计算 推理模型 多对数开销

📋 核心要点

  1. 现有的推理模型虽然能够模拟图灵机，但在算法效率和直观性上存在不足，尤其在复杂度分析时不够便捷。
  2. 本文提出了一种链式思维变换器，能够高效模拟Word RAM算法，解决了传统图灵机模拟的效率问题。
  3. 实验结果表明，CoT变换器在多对数开销下能够高效执行排序和Dijkstra算法，性能显著优于现有方法。

📝 摘要（中文）

随着推理模型的日益普及，链式思维（CoT）变换器被证明可以模拟图灵机，从而执行任意计算。然而，图灵机在算法讨论中并不方便。本文探讨CoT变换器是否能高效模拟Word RAM算法，结果表明，CoT变换器在多对数开销的情况下，能够高效地模拟任何Word RAM算法。我们首先在有限精度的变换器上建立这一结果，随后扩展到更实用的设置，包括连续CoT和混合架构。在这三种情况下，CoT均能以多对数开销高效模拟Word RAM算法，且在特定条件下开销可降至对数平方或仅对数级别，显著优于已知的CoT对图灵机的模拟。

🔬 方法详解

问题定义：本文旨在解决链式思维变换器能否高效模拟Word RAM算法的问题。现有方法在算法效率上存在较大局限，尤其是图灵机的模拟开销过高。

核心思路：论文提出CoT变换器可以在多对数开销下高效模拟Word RAM算法，设计上考虑了变换器的精度和宽度，以提高计算效率。

技术框架：整体架构包括三个主要模块：有限精度变换器、连续CoT和混合架构。每个模块针对不同的精度和宽度设置进行优化，以实现高效计算。

关键创新：最重要的创新在于提出了CoT变换器能够在多对数开销下模拟Word RAM算法，且在特定条件下开销可降至对数平方或对数级别，这与传统图灵机的模拟方法有本质区别。

关键设计：关键参数包括变换器的宽度和精度设置，采用了右侧唯一硬注意力机制，确保在计算过程中保持高效性和准确性。

📊 实验亮点

实验结果显示，CoT变换器能够在多对数开销下高效模拟Word RAM算法，排序操作的时间复杂度为O(n log n)，Dijkstra算法的时间复杂度为O(E + V log V)，相较于传统方法有显著提升。

🎯 应用场景

该研究的潜在应用领域包括高效算法设计、计算机科学教育以及人工智能推理系统。通过高效模拟Word RAM算法，CoT变换器能够在实际应用中提升计算效率，推动智能系统的发展。

📄 摘要（原文）

The increasing popularity of \emph{reasoning} models -- language models that output a series of reasoning or thought tokens before producing an answer -- is justified, in part, by theoretical results showing that chain-of-thought (CoT) transformers can simulate Turing machines, and thus perform arbitrary computation. However, the Turing machine, while suitable for complexity-theoretic analysis, is not convenient, intuitive, or efficient for discussing algorithms. Algorithms are typically designed and analyzed at a higher level of abstraction, captured by the \emph{Word RAM} model with random-access memory and unit-cost operations on $\bigO(\log n)$-bit words. As a result, Word RAM algorithms can be substantially more efficient than their Turing machine counterparts, raising the question: \emph{Can CoT transformers efficiently simulate Word RAM algorithms?} For instance, can they sort $n$ items in $\bigO(n \log n)$ steps or run Dijkstra's algorithm in $\bigO(E + V \log V)$ steps? We answer affirmatively, up to poly-logarithmic overhead. We first establish this for finite-precision transformers with poly-logarithmic width and rightmost unique hard attention, then strengthen the result to two more practical settings with finite width and log-precision: \emph{continuous} CoT, where reasoning takes the form of vectors rather than tokens, and a \emph{hybrid} architecture in which transformer layers sit atop a recurrent (linear RNN) layer. In all three cases, we find that CoT \emph{can} efficiently simulate any Word RAM algorithm with only a poly-logarithmic overhead in $n$. This overhead reduces to log-square when the Word RAM has a ``flat'' instruction set, and only logarithmic for multiplication-free flat instructions -- in stark contrast to known CoT simulations of Turing machines, which require quadratic overhead over Word RAM.