探究循环变压器何时真正成为算法，发现训练预算决定计算速度与收敛机制。
When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers
- 通过训练预算控制，发现每轮处理位置数与训练时长成正比，形成线性计算前沿。
- 权重共享使模型选择串行算法，即使提供并行地址也难以学习深层并行结构。
- 算法机制可迁移，但输入调度无法强制串行性，适合研究模型泛化与训练设计的人。
当一个权重共享的循环变压器（单个模块重复 T 次）真正实现算法？我们在群词汇问题的受控种群中得出四项发现：(1) 预算定律：自由训练建立线性计算前沿，每轮处理位置数为 v，其速度由训练合同决定：v ~ n_train/T_train（指数 0.98 ± 0.04，R²=0.99），在 T=n 训练时恰好为 1；SGD 选择满足最低合同要求的前沿；增加测试时循环次数可恢复固定输入长度下的后期位置，从而导出合理停止规则 T* = ceil(n / v-hat)。(2) 架构先验而非表达力决定算法：标准深度变压器在此类任务中学习并行扫描，而权重共享将其转向串行前沿，即使提供对数深度扫描的位置地址也无效；在匹配深度与参数下，未共享模型外推表现最差且完全无法学习 A5。(3) 壁垒不在电路复杂度：NC1 完备性不增成本（A5 可完全泛化），而群阶数却导致瓶颈（S5 的 120×120 算子阻碍联合学习）——以算子为主导的课程学习可解除所有种子的壁垒。(4) 机制具有可迁移性而非可强制性：跨预算合同热启动可转移算法并重定价速度，而通过输入调度施加串行性则在自由训练成功时失效。这些现象无法被标准工具捕捉，因其在训练循环固定的不动点上饱和。我们引入头仪器——收敛时间缩放 τ(n,i)，通过损伤锥因果验证，其斜率复现了速度 v；分布内头测量可预测分布外结果，而尾部指标无效。结果在公开的 easy-to-hard 基准上可复现。
原文摘要 · Abstract (English)
When does a weight-tied looped transformer -- one block applied T times -- implement an actual algorithm? We answer with four findings from controlled populations on group word problems. (1) The budget law: free training installs a linear computation frontier, a mechanism that solves v positions per loop, whose speed is priced by the training contract: v ~ n_train/T_train (exponent 0.98 +/- 0.04, R^2=0.99), exactly unity under T=n training. SGD selects a frontier matching the minimum the contract demands; granting more test-time loops than ever trained rescues late positions at fixed input length, yielding a principled halting rule T* = ceil(n / v-hat). (2) Architecture prior, not expressivity, picks the algorithm: standard-depth transformers learn parallel scans on this family; weight tying flips the selection to the serial frontier, even when positional addressing for a log-depth scan is supplied. At matched depth and parameters, untied models extrapolate worst and fail to learn A5 at all. (3) The walls are not where circuit complexity says: NC1-completeness costs nothing (A5 generalizes fully), while group order does (S5's 120x120 operator deadlocks joint learning) -- and an operator-first curriculum dissolves the wall in every seed. (4) Mechanisms are portable, not mandatable: warm-starting across budget contracts transfers the algorithm in every seed, re-pricing its speed, while imposing seriality through the input schedule fails where free training succeeds. These results are invisible to standard instruments, which provably saturate at the fixed points trained loops converge to. We introduce a head instrument, the convergence-time scaling tau(n,i), validate it causally via damage cones whose slope reproduces v, and show in-distribution head measurements predict out-of-distribution fate where tail metrics do not. Results replicate on the public easy-to-hard benchmark.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。