用思想链高效表示算法 Transformer

\emph{reasoning} 模型（在产生答案之前输出一系列推理或思想标记的语言模型）日益流行，部分原因是理论结果表明思想链 (CoT) Transformer 可以模拟图灵机，从而执行任意计算。然而，图灵机虽然适合复杂性理论分析，但对于讨论算法来说并不方便、直观或高效。算法通常在更高的抽象层次上进行设计和分析，由 \emph{Word RAM} 模型捕获，该模型具有随机存取存储器和对 $\bigO(\log n)$ 位字进行单位成本操作。因此，Word RAM 算法比图灵机算法要高效得多，这就提出了一个问题：\emph{CoT Transformer 能否有效地模拟 Word RAM 算法？} 例如，它们是否可以在 $\bigO(n \log n)$ 步中对 $n$ 项进行排序，或者在 $\bigO(E + V \log V)$ 步中运行 Dijkstra 算法？我们的回答是肯定的，最高可达多对数开销。我们首先为具有多对数宽度和最右边唯一硬注意力的有限精度 Transformer 建立此模型，然后将结果增强为具有有限宽度和对数精度的两个更实用的设置：\emph{连续} CoT，其中推理采用向量而不是标记的形式，以及 \emph{hybrid} 架构，其中 Transformer 层位于循环（线性 RNN）层之上。在所有这三种情况下，我们发现 CoT \emph{可以} 有效地​​模拟任何 Word RAM 算法，而只需 $n$ 的多对数开销。当 Word RAM 具有“平坦”指令集时，这种开销会减少到对数平方，并且对于无乘法平坦指令仅是对数 - 与已知的图灵机 CoT 模拟形成鲜明对比，后者需要的开销是 Word RAM 的二次方。