When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers

权重绑定的循环式Transformer（即单个模块重复应用T次）在何种条件下能真正实现一个具体的算法？我们通过对群字问题（group word problems）的受控种群实验得出以下四项发现： （1）**预算定律（Budget Law）**：自由训练会自动建立一条线性计算前沿（linear computation frontier），即一种每轮循环可处理v个位置的机制；该机制的运行速度由训练合约（training contract）决定，具体表现为：v ∝ n_train / T_train（实测指数为0.98 ± 0.04，R² = 0.99），当训练轮数T等于输入长度n时，该比例恰好为1。随机梯度下降（SGD）会选择恰好满足训练合约所要求最低性能的前沿；若在测试阶段提供比训练时更多的循环轮次，则可在固定输入长度下“挽救”那些原本滞后的位置，从而导出一条具有理论依据的停机准则：T* = ⌈n / v̂⌉。 （2）**架构先验（architecture prior）而非表达能力（expressivity）决定了算法选择**：标准深度的Transformer在此类任务上自然习得并行扫描（parallel scan）；而引入权重绑定则会将模型的选择倾向扭转至串行前沿（serial frontier），即便输入中已显式提供了支持对数深度扫描（log-depth scan）的位置编码（positional addressing），这一现象依然成立。在深度与参数量均匹配的前提下，未绑定权重的模型泛化能力最差，甚至完全无法学会A₅群上的任务。 （3）**计算瓶颈并非出现在电路复杂度理论所预言的位置**：NC¹-完全性本身并无代价（A₅群任务可完全泛化），而群阶（group order）才是真正的障碍（例如S₅群的120×120阶运算符会导致联合学习陷入死锁）；但若采用“算子优先”（operator-first）的课程设计（curriculum），则所有随机种子下该瓶颈均可被彻底消除。 （4）**机制具有可迁移性，却不可强制植入**：跨不同预算合约进行热启动（warm-starting）可在所有随机种子下成功迁移所习得的算法，并仅需相应重估其运行速度；而若试图通过人为设计输入调度（input schedule）来强制施加串行性，则在自由训练能够成功的地方反而会失败。 上述结果无法被标准评估工具所观测——因为这些工具在理论上即注定饱和于训练循环所收敛到的不动点（fixed points）。为此，我们引入一种新型头部测量工具（head instrument）：收敛时间标度函数 τ(n, i)，并通过“损伤锥”（damage cones）对其因果有效性予以验证——其斜率精确复现了前述v值；进一步表明，在分布内（in-distribution）对头部行为的测量，可有效预测模型在分布外（out-of-distribution）的表现命运，而尾部指标（tail metrics）则完全失效。所有结果均在公开的“由易到难”（easy-to-hard）基准测试集上得到复现。

论文探究深度学习模型（特别是权重绑定的循环式Transformer）何时真正‘实施’一个可泛化、可解释的算法（如群论中的字问题求解），而非仅拟合训练分布；核心问题是：训练预算、架构设计与测试时计算资源之间的定量关系如何决定模型是否习得结构性算法机制。

提出‘预算定律’（Budget Law）——模型在训练中隐式学习一个线性计算前沿（v positions/loop），其速度v由训练合同（n_train/T_train）精确决定；算法选择由架构先验（如权重绑定）主导，而非表达能力上限；机制具有可移植性但不可强制注入，需通过自由训练涌现。

实验基于可控群字问题（A5、S5等有限群），使用合成数据集，严格控制难度、长度与分布；发现NC1完全性不构成泛化障碍，而群阶大小（如S5的120×120运算表）引发联合学习崩溃，可通过算子优先课程消解；引入新型诊断工具‘收敛时间尺度τ(n,i)’和‘损伤锥’进行因果机制验证；结果在公开easy-to-hard基准上复现；代码未在摘要中提及开源，但方法具强可复现性；值得深入的方向包括：预算定律在其他算法任务（如动态规划、图遍历）中的普适性，以及机制迁移对推理效率与鲁棒性的工程意义。

‘In-Context Learning as Implicit Algorithm Discovery’ (Garg et al., NeurIPS 2023); ‘Transformers Learn Shortest Paths’ (Kahn et al., ICLR 2024); ‘Algorithmic Reasoning with Transformers’ (Anil et al., ICML 2023); ‘Neural Circuit Complexity and Generalization’ (Geiger et al., Nature ML 2022); ‘The Inductive Bias of Weight Tying’ (Chen et al., ACL 2023)