递归何时成为算法？权重共享循环Transformer中的收敛选择

# 递归何时成为一种算法？权重共享循环变压器中的收敛机制选择
来源：https://arxiv.org/html/2607.20594
张同 复旦大学 tongzhang25@m\.fudan\.edu\.cn & 胡俊豪 北京大学 junhaohu@stu\.pku\.edu\.cn & 彭云 复旦大学 yunpeng4@sigsoft\.org & 谢涛 北京大学 taoxie@pku\.edu\.cn

###### 摘要

当一个权重共享的循环变压器——一个模块重复应用 \(T\) 次——实现一个真正的算法时，会发生什么？我们通过群论词汇问题上的受控实验群体给出了四个发现。(1) **预算定律**：自由训练会安装一个*线性计算前沿*，这是一种每个循环解决 \(v\) 个位置的机制，并通过训练合同为其速度定价：\(v \approx n_{tr}/T_{tr}\)，在 \(T=n\) 训练时恰好为 1——SGD 一致地选择了一种前沿，其速度正好匹配合同要求的最低速度。速度是一个实验者可控制的旋钮，并且在固定输入长度下，给予比训练时更多的测试时循环可以挽救靠后的位置。(2) **架构先验，而非表达能力，决定了算法的选择**：标准深度的变压器在此任务家族中学习并行扫描；权重共享则翻转了选择，使其倾向于串行前沿（在全局注意力下），即使提供了用于 \(\log\) 深度扫描的位置寻址。(3) **障碍并非电路复杂性所指出**：\(\mathrm{NC}^1\)-完备性毫无代价（\(A_5\) 完全泛化），而群的阶却构成障碍（\(S_5\) 的 \(120 \times 120\) 操作矩阵导致联合学习死锁）——一种“算子优先”的课程表可以消除这个障碍，揭示了它是一个优化病理，而非不可能。(4) **机制是可迁移的对象**：在不同预算合同间进行热启动，可以在每一次尝试的随机种子中将算法迁移过去——为其速度重新定价以适应新合同——并绕过了那种会击败大多数从头开始运行的种子的“种子抽签（seed lottery）”，而通过输入调度施加串行性在自由训练成功的地方会失败——机制可以被迁移，但不能被强制指定。这些结果对于标准工具来说是不可见的：跳跃步和跨步相似性度量在被训练的循环收敛到的固定点处会饱和，它们测量的是轨迹的尾部，而算法却存在于轨迹的头部。我们引入了一个头部工具，即收敛时间标度 \(\tau(n,i)\)，通过激活修补（其损伤锥体的斜率重现了 \(v\)）对其进行因果验证，并展示了头部工具能够预测哪些种子能够泛化，而尾部指标和路径无关性得分却做不到。这些现象在公开的易到难基准测试中得到了复现，包括 \(4\times\) 精确匹配的长度外推。

## 1 引言

深度递归（循环）变压器重复使用一个模块 \(T\) 次，承诺提供自适应的测试时计算：更困难或更长的输入获得更多循环 (Dehghani et al., 2019 (https://arxiv.org/html/2607.20594#bib.bib10); Geiping et al., 2025 (https://arxiv.org/html/2607.20594#bib.bib14); ByteDance Seed, 2025 (https://arxiv.org/html/2607.20594#bib.bib6))。其隐含的机制故事是：这个循环就是一个*算法*——即第 \(t\) 次循环执行了迭代计算的第 \(t\) 步，因此运行更多循环就执行了更多步骤。这个故事驱动着训练策略、停机规则和可解释性议程。这是真的吗？

这个问题分为两部分：(i) 一个训练好的循环变压器实际实现了什么机制？(ii) 我们的工具甚至能够区分吗？我们表明第二个问题制约着第一个问题。自然的测试——跳过一个循环会有害吗？连续的循环使用相同的电路吗？——是*尾部工具*：它们探测轨迹接近其终态的区域。但是，训练好的循环会收敛，收敛状态是循环映射的一个不动点；在接近幂等点处，跳跃是免费的，并且连续的局部电路在构造上是一致的（命题 1 (https://arxiv.org/html/2607.20594#Thmproposition1)）。一个在前几个循环就完成了实际工作然后闲置的模型，对于所有尾部工具来说，与一个从未有过离散步骤的模型是无法区分的。算法（如果存在的话）存在于轨迹的头部。

我们通过一项受控群体研究来具体化这一点：数十个权重共享的循环变压器，在具有已知单次（恒定深度）解的任务上运行，涵盖了各种配置（位置编码、输入注入、循环调度）和随机种子。该群体在长度泛化上表现出数量级的差异——包括同一配置下跨种子的几乎完全不同的泛化表现——但*每一个*尾部工具对此都视而不见：对于每个有足够多已解示例的模型，单步跳跃保持度是精确完全的，跨步的雅可比对齐度一致地高，并且没有任何跨步相似性度量与泛化相关（附录 C (https://arxiv.org/html/2607.20594#A3)）。

然后，我们引入了一个*头部*工具。收敛时间标度 \(\tau(n,i)\) 是解码输出在位置 \(i\) 达到其最终值并保持住的第一个循环，它作为输入长度 \(n\) 在已解输入上的函数进行测量。其标度类别是一个机制签名：常数 \(\tau\) 是捷径（或纯精炼）；\(\tau \propto \log n\) 是并行扫描；\(\tau \propto n\) 是串行的、步索引化的计算。与尾部指标不同，\(\tau\) 具有可证明的动态范围：我们通过一个流式阳性对照来验证它——标记 \(i\) 仅在循环 \(i\) 时才被揭示，因此串行计算被构造所强制——在那里它精确地读取为 \(\tau \propto n\)（斜率为 \(1.0\)），而捷径对照则读取为平坦的。

配备了一个校准过的工具，我们描述了自由训练实际安装了什么。群论词汇问题提供了一个具有已知理论的任务阶梯：可解群（\(\mathbb{Z}_{60}, S_4\)）允许恒定深度的捷径 (Liu et al., 2023 (https://arxiv.org/html/2607.20594#bib.bib19))，\(S_5\) 和 \(A_5\) 词汇问题是 \(\mathrm{NC}^1\)-完备的 (Barrington, 1989 (https://arxiv.org/html/2607.20594#bib.bib4))，并且原则上可以通过关联扫描实现 \(\Theta(\log n)\) 的循环深度 (Merrill & Sabharwal, 2025 (https://arxiv.org/html/2607.20594#bib.bib23))。面对这个理论菜单提供的每一个选项——单次捷径、\(\log\) 深度扫描、不动点精炼——训练好的模型选择了第四个：一个线性前沿，其速度是训练合同的函数，其障碍追踪的是算子的规模而非电路类，并且可以通过热启动在合同间移动，但不能通过输入调度来安装。

**贡献**。(1) **线性计算前沿及其预算定律**：自由训练安装了一个串行机制，其速度遵循 \(v \approx n_{tr}/T_{tr}\)（在 \(T=n\) 时恰好为 \(1.00\)），并在固定长度下具有按位置循环外推的挽救能力（§6 (https://arxiv.org/html/2607.20594#S6)）。(2) **算法选择由架构先验决定**：权重共享将 SGD 的选择从标准深度变压器的并行扫描翻转为串行前沿，并通过非共享和位置编码对照进行验证（§6 (https://arxiv.org/html/2607.20594#S6)）。(3) **学习障碍是优化对象，而非复杂性理论对象**：\(\mathrm{NC}^1\)-硬度是自由的（\(A_5\)），算子规模则不是（\(S_5\)），并且“算子优先”的课程表可以消除这个障碍；强制的串行调度在自由训练成功的地方会失败（§6 (https://arxiv.org/html/2607.20594#S6)）。(4) **机制的可移植性**：预算退火在 \(4/4\) 个随机种子中将算法跨循环合同迁移，绕过了从头开始的种子抽签（§7 (https://arxiv.org/html/2607.20594#S7)）。(5) **使 (1)-(4) 可见的测量理论**：一个饱和命题，展示了标准工具在不动点处是盲目的；\(\tau(n,i)\) 头部工具及其因果验证；以及三场 16 种子竞赛，其中头部工具能够预测种子级别的泛化，而尾部指标和路径无关性则不能（§4 (https://arxiv.org/html/2607.20594#S4)–5 (https://arxiv.org/html/2607.20594#S5), §8 (https://arxiv.org/html/2607.20594#S8)）。

参照图注图 1：概述。左：一个权重共享的循环变压器将一个共享模块应用 \(T\) 次。中：训练好的模型通过一个*计算前沿*来解决每个位置的任务，该前沿每个循环推进固定数量的位置；尾部工具只能看到收敛区域（它们在那里可证明地饱和），而算法存在于轨迹的头部。右：收敛时间 \(\tau(n,i)\) 的标度类别（平坦 / \(\log n\) / 线性）识别了机制。
## 2 相关工作

**循环和深度递归变压器**。通用变压器 (Universal Transformers, Dehghani et al., 2019 (https://arxiv.org/html/2607.20594#bib.bib10)) 引入了跨深度的权重共享；最近的开放模型扩展了这一思想 (Huginn-3.5B, Geiping et al., 2025 (https://arxiv.org/html/2607.20594#bib.bib14); Ouro, ByteDance Seed, 2025 (https://arxiv.org/html/2607.20594#bib.bib6))。循环变压器在 nn-RASP-L 任务上被证明可以长度泛化 (Fan et al., 2024 (https://arxiv.org/html/2607.20594#bib.bib12))，并且可以模拟迭代求解器 (Yang et al., 2023 (https://arxiv.org/html/2607.20594#bib.bib31); Gatmiry et al., 2024 (https://arxiv.org/html/2607.20594#bib.bib13))；Gatmiry 等人 (2024 (https://arxiv.org/html/2607.20594#bib.bib13)) 表明，上下文回归的全局最小值实现了预条件梯度下降——这是一种趋向于收敛精炼的归纳偏差，与我们的选择结果一致。

**循环的机制性解释**。Blayney (2026 (https://arxiv.org/html/2607.20594#bib.bib5)) 记录了 Ouro 和 Huginn 中的循环不动点和注意力模式稳定化；他们的命题 4.2（注意力相似性遵循状态收敛）预示了我们的尾部饱和分析，该分析将他们的观察转化为一个工具有效性约束。基于透镜对 Huginn 的研究发现了有限的潜在思维链结构 (Lu et al., 2025 (https://arxiv.org/html/2607.20594#bib.bib20))。Kohli (2026 (https://arxiv.org/html/2607.20594#bib.bib18)) 在受控递归深度模型中，以（位置，迭代）粒度修补隐藏状态；循环模型存在步骤解析的*数据*归因 (Kaissis, 2026 (https://arxiv.org/html/2607.20594#bib.bib17))。这些都没有测量循环何时携带步索引化计算；我们的 \(\tau\) 工具正是针对这一空白。特征级电路追踪 (Ameisen et al., 2025 (https://arxiv.org/html/2607.20594#bib.bib1)) 已扩展到具有时间步条件转码器的扩散变压器 (DifFRACT authors, 2026 (https://arxiv.org/html/2607.20594#bib.bib11))，但尚未扩展到权重共享循环；我们的结果表明，循环机制问题必须首先解决，因为归因图继承相同的尾部盲区。

**收敛动力学**。路径无关——收敛到输入决定的不动点——预测了深度均衡模型中的向上泛化 (Anil et al., 2022 (https://arxiv.org/html/2607.20594#bib.bib2))；循环式训练明确促进了这一点 (Bansal et al., 2022 (https://arxiv.org/html/2607.20594#bib.bib3))。我们采用渐近对齐分数作为基线，并表明收敛动力学的选择是训练压力的一个属性，而非递归本身。

**变压器的复杂性**。固定深度变压器位于 \(\mathrm{TC}^0\) 中 (Merrill & Sabharwal, 2023 (https://arxiv.org/html/2607.20594#bib.bib22))；对可解群自动机存在恒定深度捷径并且可以被学习，而不可解群（\(S_5, A_5\)）则没有，除非 \(\mathrm{TC}^0 = \mathrm{NC}^1\) (Liu et al., 2023 (https://arxiv.org/html/2607.20594#bib.bib19); Barrington, 1989 (https://arxiv.org/html/2607.20594#bib.bib4))。对数深度的循环变压器通过关联扫描弥合了这一差距 (Merrill & Sabharwal, 2025 (https://arxiv.org/html/2607.20594#bib.bib23))，而固定深度的 SSM 在 \(S_5\) 状态追踪上失败 (Merrill et al., 2024 (https://arxiv.org/html/2607.20594#bib.bib24))。我们使用这个阶梯作为选择网格的硬度轴。奇偶校验可以在恒定深度上表达 (Chiang & Cholak, 2022 (https://arxiv.org/html/2607.20594#bib.bib7))，但难以学习到长度泛化 (Hahn & Rofin, 2024 (https://arxiv.org/html/2607.20594#bib.bib15))——表达性和可学习性存在分歧，这就是为什么我们的主张是关于训练*选择*了什么，而不是架构*能做什么*。

**强制的步索引化**。按迭代的监督将循环与思维链步骤对齐 (Yu, 2026 (https://arxiv.org/html/2607.20594#bib.bib33))；CLRS 风格的提示将处理器迭代与算法步骤对齐 (Veličković et al., 2022 (https://arxiv.org/html/2607.20594#bib.bib29))，尽管无提示模型会漂移到并行策略 (Rodionov & Prokhorenkova, 2023 (https://arxiv.org/html/2607.20594#bib.bib25))。这些都是存在性证明，表明当监督施加时，循环*可以*被步索引化；我们的流式手臂从架构上施加了这一点，而自由手臂则测量了除了施加之外，是否有任何事物足以产生这样的效果。

## 3 设置

**架构**。一个权重共享的循环变压器将一个模块 \(F_\theta\)（2 或 4 层预归一化变压器层）应用 \(T\) 次于状态 \(h^t \in \mathbb{R}^{N \times d}\)：\(h^{t+1} = F_\theta(h^t, e)\)，其中 \(e\) 是词嵌入，可选地通过一个学习的适配器在每个循环中重新注入（输入注入，Bansal et al., 2022 (https://arxiv.org/html/2607.20594#bib.bib3))。读出是应用在 \(\mathrm{LN}(h^T)\) 上的一个线性头。规模分类：s（2 层，\(d=128\)），m（2 层，\(d=256\)），l（4 层，\(d=512\)）。主网格中无位置编码 (NoPE)；位置编码的效果在附录 D (https://arxiv.org/html/2607.20594#A4) 中进行了分析。

**任务**。所有任务都是逐位置的序列到序列任务，这阻止了仅回答的捷径，并为每个中间值提供了真实标签。*试点*：前缀奇偶校验，以及 LSB 优先的带进位增量（两者都是恒定深度可捷径化的）。*选择网格*：在 \(\mathbb{Z}_{60}\)（阿贝尔群）、\(S_4\)（非阿贝尔，可解群）和 \(S_5\)（不可解群；\(\mathrm{NC}^1\)-完备词汇问题）上的前缀乘积：输入 \(g_1 \dots g_n\)，目标是在每个位置 \(i\) 处得到 \(p_i = g_1 \circ \dots \circ g_i\)。\(S_4 / \mathbb{Z}_{60}\) 对照将非交换性与不可解性分离开来。

**训练模式**。*自由模式*：从第 0 次循环开始所有标记可见；循环调度为 \(T = \lceil \log_2 n \rceil + 3\)（抖动）或固定 \(T\)；长度课程表（\(S_5\) 必需，Merrill & Sabharwal, 2025 (https://arxiv.org/html/2607.20594#bib.bib23))。*流式模式*：标记 \(i\) 仅在从循环 \(i-1\) 开始才被揭示——嵌入并可被注意——因此串行计算被构造强制；\(T = n+2\)。流式单元是阳性对照和度量上限，而非新发现：它们用于校准工具并界定涌现可能的样子。

## 4 尾部工具在不动点处饱和

###### 命题 1 (尾部盲区，非正式陈述)

设 \(h^\star\) 是循环映射 \(G(h)=F_\theta(h,e)\) 的一个不动点，并且在循环 \(\tau^\star \leq T-k\) 处达到。那么 (i) 跳过 \(\tau^\star\) 之后的任意 \(k\) 次循环不会改变输出；(ii) 局部雅可比矩阵 \(J_t = \partial h^{t+1}/\partial h^t\) 对于所有 \(t \geq \tau^\star\) 是一致的；(iii) 任何基于特征词典 \(z=E(h)\) 和由它构建的任何归因图在循环 \(t \geq \tau^\star\) 上都是一致的。这些量都没有约束在循环 \(t < \tau^\star\) 时执行的任何计算。

证明直接从幂等性 \(G(h^\star)=h^\star\) 得出，并在附录 B (https://arxiv.org/html/2607.20594#A2) 中给出，连同针对近似不动点的定量版本（\(