When Does Recurrence Become an Algorithm?

A weight-tied looped transformer applies one block T times. Everyone assumes loop t executes algorithm step t. We built the instruments to check — and found the answer is a law, not a yes or no.

Overview: looped transformer, computation frontier, tau scaling classes — Left: one shared block, applied T times. Middle: trained models solve tasks via a **linear computation frontier** — the solved prefix advances v positions per loop; standard instruments only see the converged tail, where they provably saturate. Right: the scaling class of the convergence time τ(n,i) identifies the mechanism.

Four findings

1 · The budget law

Frontier speed is priced by the training contract: v ≈ n_train/T_train with exponent 0.98 ± 0.04 (R² = 0.99, 23 models, 8× demand range). SGD meets the demanded minimum — never exceeds it when speed is costly.

2 · Architecture prior picks the algorithm

Standard transformers learn parallel scans on the same tasks; weight tying flips the selection to a serial frontier. At matched depth and parameters, fully untied models extrapolate worst and fail to learn A₅ at all.

3 · Walls track operator scale, not complexity class

NC¹-completeness costs nothing (A₅ generalizes fully); group order does — S₅'s 120×120 operator deadlocks joint learning. An operator-first curriculum dissolves the wall in 10/10 seeds.

4 · Mechanisms are portable, not mandatable

Warm-starting across budget contracts transfers the algorithm in every seed — re-pricing its speed to the new contract — while forcing seriality through the input schedule fails where free training succeeds.

The linear computation frontier

Per-(loop, position) accuracy heatmaps: each loop extends the solved prefix by a constant number of positions. The slope is a per-model fingerprint set by the training budget.

Frontier heatmaps at three training contracts — Tight log-T training yields v≈2.4 (left); a T=n contract yields exactly v=1.0 (middle); T=n/2 yields v≈2.1 (right).

v ≈ clip( n_train/T_train, v_free, v_max )

Budget law fit — The budget law across 23 models: measured speed tracks training demand (dashed: v = demand).

Causal validation & an actionable halting rule

Patching states at (position, loop) produces strictly-downstream damage cones whose slope independently reproduces each model's frontier speed — the frontier is a causal object, not a decoding artifact. And because v is estimable in distribution, T* = ⌈n/v̂⌉ recovers near-oracle accuracy at unseen lengths while avoiding overthinking.

Halting rule accuracy-compute — Stopping at T* (blue) nearly matches an oracle T-sweep (green) and far exceeds the training schedule's own fixed T (grey).

BibTeX

@article{zhang2026recurrence,
  title  = {When Does Recurrence Become an Algorithm?
            Convergence Selection in Weight-Tied Looped Transformers},
  author = {Zhang, Tong and Hu, Junhao and Peng, Yun and Xie, Tao},
  year   = {2026},
  note   = {Preprint}
}