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

Tong Zhang; Junhao Hu; Yun Peng; Tao Xie

cs.LGJul 22, 2026

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

Authors: Tong Zhang, Junhao Hu, Yun Peng, Tao Xie

Organizations: Fudan University · Peking University

Abstract

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.

Explore similar work

Apr 22, 2026cs.LG

How Much Is One Recurrence Worth? Iso-Depth Scaling Laws for Looped Language Models

We measure how much one recurrence is worth to a looped (depth-recurrent) transformer, in equivalent unique parameters. From an iso-depth pretraining sweep across recurrence counts

r \in \{1, 2, 4, 8\}

spanning

{\sim}50\times

in training compute, we fit a joint scaling law

L = E + A\,(N_\text{once} + r^{\varphi} N_\text{rec})^{-α} + B\,D^{-β}

and measure a recurrence-equivalence exponent

\varphi = 0.46

. Intuitively,

\varphi

tells us whether looping a block

r

times is equivalent in validation loss to

r

unique blocks of a non-looped model (full equivalence,

\varphi{=}1

) or to a single block run repeatedly with no capacity gain (

\varphi{=}0

). Our

\varphi = 0.46

sits in between, so replacing unique blocks with shared recurrences increases validation loss at matched training compute. For example, at

r{=}4

a 410M looped model performs on par with a 580M non-looped model, but incurs the training cost of a 1B non-looped one. We demonstrate the utility of

\varphi

as a diagnostic tool on two case studies: commonly used truncated backpropagation lowers

\varphi

0.38

, indicating that the loop mechanism is poorly trained under truncation, even though validation loss decreases. Conversely, hyperconnections raise

\varphi

0.65

, a genuine capacity gain. Our method separates true loop improvements from training-side gains, a distinction raw validation loss cannot make.

Kristian Schwethelm, Daniel Rueckert, Georgios Kaissis

Recurrence Large Models Scaling Laws Loss Function Model Pretraining

Ask PDF

Date pendingcs.LG

On the Residual Scaling of Looped Transformers: Stability and Transferability

Looped (weight-tied) Transformers apply a shared residual block

N

times (

h \leftarrow h + \varepsilon\,f(h)

, same

f

at each step), increasing effective depth without adding parameters. Prior depth-scaling analyses prescribe

\varepsilon = 1/\!\sqrt{L}

for depth-

L

residual networks. We show that this is insufficient for looped architectures: weight sharing makes residual updates correlated across iterations, requiring the stronger scaling

\varepsilon = 1/N

. For multi-layer blocks (

L

unique layers looped

N

times), we derive a factored parameterization

\varepsilon = \lambda/(N\!\sqrt{L})

that separates the two sources of growth:

1/N

controls the within-layer loop correlation, and

1/\!\sqrt{L}

controls the across-layer variance. A key consequence is that the optimal learning rate depends only on the number of unique layers

L

, not on the loop count

N

, enabling direct hyperparameter transfer from small to large

N

without retuning. Experiments on looped Transformers confirm that

1/N

scaling improves trainability and yields better loss than

1/\!\sqrt{N}

scaling across loop counts.

Shaowen Wang, Bingrui Li, Ge Zhang +3

Residual Connections Learning Rates Transformer Architectures

Ask PDF

Jul 15, 2026cs.LG

DeepLoop: Depth Scaling for Looped Transformers

Looped Transformers scale sequential computation by applying a compact stack of physical blocks for multiple rounds, increasing unrolled depth without increasing stored parameters. This reuse changes the residual-scaling problem: in an untied Transformer, each residual branch receives and applies its own parameter update, whereas in a looped Transformer one shared update aggregates gradients from repeated visits and is read back by those same visits in the next linearized forward pass. We formalize this tied-depth effect through a first-order perturbation bound controlled by a visit-alignment coefficient

κ_R

. The bound recovers the DeepNorm exponent when visits decorrelate, but in the conservative aligned regime it requires the exponent to increase from

1/4

1/2

as loop count grows at fixed physical depth. The resulting method, \textbf{DeepLoop}, keeps the Post-LN DeepNorm architecture and sets

α=(2N)^{1/2}

and

β=(8N)^{-1/2}

for unrolled depth

N

. On GPT-style looped language models at GPT-2 small and GPT-2 medium scale, DeepLoop is neutral when no physical block is revisited and improves validation loss and downstream accuracy once recurrent depth is activated. These results show that stable recurrent depth requires residual scaling rules that account for parameter visits, not only nominal layer count.

Shuzhen Li, Yifan Zhang, Jiacheng Guo +2

Transformer Architectures Search Depth

Ask PDF