Looped transformers reveal a linear budget law for algorithm emergence

A team led by Tong Zhang has tackled a fundamental question in neural network interpretability: when does a weight-tied looped transformer—the same block applied T times—actually execute a recognizable algorithm? Their experiments on group word problems yield four key insights. First, the 'budget law': free training installs a linear computation frontier that solves v positions per loop, where v scales almost exactly as n_train/T_train (exponent 0.98 ± 0.04, R²=0.99). This means the model naturally discovers the minimal number of loops needed for a given input length, providing a principled halting rule T* = ceil(n / v-hat). Training and test-time compute are interchangeable under this law: granting more loops during inference can rescue late positions even with shorter training.

Second, architecture prior, not expressive power, determines which algorithm the model learns. Standard-depth untied transformers converge to parallel scans on group problems, but weight tying forces a serial frontier—even when positional embeddings for a log-depth scan are provided. At matched depth and parameters, untied models fail to extrapolate and cannot learn the A5 group at all. Third, the computational hardness walls don't match circuit complexity: NC¹-completeness costs nothing (A5 generalizes perfectly), but group order matters—S5's 120×120 operator deadlocks joint learning. An operator-first curriculum dissolves this wall consistently. Finally, mechanisms are portable across training budgets: warm-starting transfers algorithms and re-prices their speed, while imposing seriality through input schedules fails. The authors introduce a new diagnostic, convergence-time scaling τ(n,i), validated via damage cones that recover the frontier slope.