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

> Trained weight-tied looped transformers implement serial linear-frontier algorithms whose speed obeys a budget law, and standard interpretability instruments are provably blind to this mechanism.

- **Source:** [arXiv](https://arxiv.org/abs/2607.20594)
- **Published:** 2026-10-17
- **Permalink:** https://picx.dev/p/BtiPo0
- **Whiteboard:** https://picx.dev/p/BtiPo0/image

## Summary

## Summary (Overview)

- **Core question**: When does a weight-tied looped transformer—one block applied T times—actually implement a serial algorithm, and can existing interpretability instruments even detect it?
- **Key finding 1 (Budget Law)**: Free training installs a *linear computation frontier*—a serial mechanism solving v positions per loop, where v ≈ n_tr/T_tr (exactly 1.00 under T = n training). Speed is an experimenter-controllable knob priced by the training contract.
- **Key finding 2 (Architecture prior, not expressivity)**: Weight tying flips SGD's algorithm selection from the parallel scan learned by standard-depth transformers to a serial frontier, even when positional addressing for a log-depth scan is supplied.
- **Key finding 3 (Walls are optimization, not complexity)**: NC¹-completeness costs nothing (A₅ generalizes fully), while group order does (S₅'s 120×120 operator deadlocks joint learning)—an operator-first curriculum dissolves the wall.
- **Key finding 4 (Mechanism portability)**: Warm-starting across budget contracts transfers the algorithm in every seed attempted (4/4), re-pricing its speed to the new contract and bypassing a seed lottery that defeats most from-scratch runs.
- **Key finding 5 (Measurement theory)**: Standard tail instruments provably saturate at fixed points; the authors introduce a *head instrument*—convergence-time scaling τ(n,i)—with causal validation via activation patching.

---

## Introduction and Theoretical Foundation

### Background

Looped (depth-recurrent) transformers reuse a single block T times, promising adaptive test-time compute: harder or longer inputs get more loops. The implicit mechanistic story is that loop t performs the t-th step of an iterative computation. The paper asks: **Is this story true?**

The question splits into two parts:
1. What mechanism does a trained looped transformer actually implement?
2. Can our instruments even tell?

The authors show the second question gates the first. Natural tests—skip tolerance, cross-step similarity—are **tail instruments**: they probe the trajectory near its end state. But trained loops converge, and a converged state is a fixed point of the loop map. Near an idempotent point, skipping is free and successive local circuits agree by construction.

### Theoretical Foundation

The paper leverages a task ladder from complexity theory:

- **Solvable groups** (Z₆₀, S₄) admit constant-depth shortcuts (Liu et al., 2023)
- **S₅ and A₅ word problems** are NC¹-complete (Barrington, 1989)
- **Θ(log n) looped depth** suffices in principle via associative scan (Merrill & Sabharwal, 2025)
- Fixed-depth transformers sit in TC⁰ (Merrill & Sabharwal, 2023)

Against this theory menu—one-shot shortcut, log-depth scan, fixed-point refinement—trained models choose a **fourth option**: a linear frontier whose speed is a function of the training contract.

### Key Theoretical Result: Tail Blindness

**Proposition 1 (Tail blindness, informal)**: Let $h^\star$ be a fixed point of the loop map $G(h) = F_\theta(h, e)$ reached at loop $\tau^\star \leq T - k$. Then:
- (i) skipping any k loops after $\tau^\star$ leaves the output unchanged;
- (ii) the local Jacobians $J_t = \partial h_{t+1}/\partial h_t$ agree for all $t \geq \tau^\star$;
- (iii) any feature dictionary $z = E(h)$ and any attribution graph built from it agree across loops $t \geq \tau^\star$.

None of these quantities constrain the computation performed at loops $t < \tau^\star$.

The approximate form (Proposition 3) states that if $\|G(h_t) - h_t\| \leq \epsilon$ for $t \geq \tau^\star$ and G is L-Lipschitz, then skipping k tail loops perturbs the final state by at most $\epsilon \sum_{i=0}^{k-1} L^{T-\tau^\star-i}$, making near-converged trajectories indistinguishable from converged ones at instrument precision.

---

## Methodology

### Architecture

- **Weight-tied looped transformer**: applies block $F_\theta$ (2 or 4 pre-norm transformer layers) T times to state $h_t \in \mathbb{R}^{N \times d}$:
  $$h_{t+1} = F_\theta(h_t, e)$$
  where e is the token embedding, optionally re-injected each loop via a learned adapter (input injection).
- Readout: linear head on $\text{LN}(h_T)$
- Scales: S (2L, d=128), M (2L, d=256), L (4L, d=512)
- No positional encoding (NoPE) in the main grid

### Tasks

All tasks are **per-position sequence-to-sequence** (blocks answer-only shortcuts, gives every intermediate value a ground truth):

| Task Type | Examples | Property |
|-----------|----------|----------|
| Pilot | Prefix parity, LSB-first increment-with-carry | Constant-depth shortcuttable |
| Selection grid | Prefix products over Z₆₀, S₄, S₅ | Solvable/non-solvable groups |

Task formulation: input $g_1 \ldots g_n$, target $p_i = g_1 \circ \cdots \circ g_i$ at every i.

### Regimes

- **Free**: all tokens visible from loop 0; loop schedules T = ⌈log₂n⌉+3 (jittered) or fixed T; length curriculum
- **Streaming**: token i revealed only from loop i−1 on (seriality forced by construction); T = n+2

### The Head Instrument: Convergence-Time Scaling

**Definition 1**: For a solved input of length n, let $\hat{y}^t_i$ be the label decoded from $h_t$ at position i. Define:
$$\tau(n, i) = \min\{k : \hat{y}^t_i = \hat{y}^T_i \ \forall t \geq k\}$$
$$\tau_{\max}(n) = \text{median}_{inputs} \max_i \tau(n, i)$$

The scaling class is the growth of $\tau_{\max}(n)$:
- **Flat**: shortcut/refinement
- **Θ(log n)**: parallel scan
- **Θ(n)**: serial

### Calibration

- Streaming parity (seriality forced by construction): slope $d\tau_{\max}/dn = 1.00$
- Fixed-T parity (bounded budget): slopes 0.39–0.41, bounded by T
- Learned-PE models (positional wall): reported as out of instrument range

---

## Empirical Validation / Results

### The Linear Computation Frontier

Free training discovers frontier algorithms on S₄ and A₅ prefix products: the contiguous solved prefix advances v positions per loop, with v essentially constant across input lengths within a model.

**Table 1: Frontier speed and uniformity by training contract**

| Group | Contract (demand n/T) | runs | v | unif.@64 |
|-------|----------------------|------|-----|----------|
| S₄ | S T=2n (0.5) | 4 | 0.51 [.51,.52] | .55 |
| S₄ | S T=n (1) | 2 | 1.00 [1.00,1.00] | .98 |
| S₄ | S T=n/2 (2) | 4 | 2.00 [1.93,2.13] | .19 |
| S₄ | S T=n/4 (4) | 2 | 4.00 [3.60,4.00] | .00 |
| S₄ | S log-T (mixed) | 16 | 2.00 [1.86,2.42] | .33 |
| S₄ | M log-T (mixed) | 4 | 1.88 [1.86,1.88] | .41 |
| S₄ | L log-T (mixed) | 4 | 2.73 [2.09,3.33] | .09 |
| A₅ | S T=n, horizon (1) | 16 | 0.96 [0.08,1.03] | — |
| S₅ | M op.-first, T=n (1) | 2 | 1.00 | .56 |
| Z₆₀ | S log-T (mixed) | 8 | 2.15 [1.82,5.17] | — |
| ETH parity | T=n (1) | 4 | ≈1.5 | — |

### The Budget Law

Across contracts spanning an 8× range of demand, measured v tracks $n_{tr}/T_{tr}$ with a power-law exponent of $0.98 \pm 0.04$ (95% CI; R² = 0.99 over 23 models at 8 demand levels). The complete form:

$$v \approx \text{clip}(n_{tr}/T_{tr}, v_{free}, v_{max})$$

Three regimes:
- **Law-bound** (A₅, S₄): v tracks demand exactly
- **Floored** (parity): v never drops below ≈1–1.5 (attention composes cheap XOR operators over multiple positions)
- **Escaped** (Z₆₀): tight contracts push the model off the frontier class entirely (abelian task has a parallel shortcut)

### Causal Validation

Resampling the state at (position i, loop t) yields damage that is strictly downstream-in-position (zero upstream damage in all 72 grid cells), structured by the frontier. The cone slope reproduces each model's measured v independently.

### Storage Phenotypes

**Table 3: Repair phenotype** (mean self-damage when stored value at a position already passed by the frontier is resampled)

| | A₅ T=n | S₄ log | S₄ T=n/2 | S₅ op-first |
|---|---|---|---|---|
| self-damage behind frontier | .02 | .95 | .96 | .99 |

- **Self-healing** (A₅ star solution): repairs corrupted stored values within a loop
- **Store-once** (most models): near-total, permanent self-damage

### Learning Walls: Operator Scale, Not Circuit Class

**Table 4: Optimization cost of the group operator** (training steps to per-token accuracy ≥ .98 on pair composition, n=2)

| | S₄ (|G|=24) | Z₆₀ | A₅ (|G|=60) | S₅ (|G|=120) |
|---|---|---|---|---|
| scale S | ∼0.5k | 2.5k | ∼4k | >40k (never) |
| scale M | — | 2.0k | — | 6.5k |

- A₅ is exactly as NC¹-hard as S₅, yet trains to full length generalization
- Operator-first curriculum cracks S₅ in 10/10 seeds (exact match ≥ 0.92 at 2× training length)
- Joint learning of operator and chain deadlocks; sequenced learning does not

### Imposed Seriality Fails

**Table 5: Mechanism cannot be mandated through the input schedule**

| | free | streaming | streaming + per-loop sup. |
|---|---|---|---|
| parity | ✓ | ✓ | — |
| A₅ | ✓ (lottery) | × | × |
| S₅ | × (op. wall) | × | × |
| S₅, operator-first | ✓ | — | — |

### Tying-Degree Control

**Table 6: Tying-degree control at fixed effective depth 12** (mean per-token accuracy at n=64, 3 seeds per cell)

| | G=1 (tied) | G=2 | G=3 | G=4 | G=6 | G=12 (untied) |
|---|---|---|---|---|---|---|
| S₄ const. width | .21 | .27 | .30 | .30 | .32 | .26 |
| S₄ param-matched | .21 | .28 | .27 | .25 | .25 | .15 |
| A₅ const. width | .10 | .23 | .17 | .25 | .23 | .15 |
| A₅ param-matched | .10 | .15 | .05 | .05 | .05 | .05 |

With parameters matched, untying hurts extrapolation (S₄) and destroys learnability (A₅, G≥3 at chance). Weight reuse is a load-bearing inductive bias.

### Budget Annealing: Mechanism Portability

**Table 7: Budget annealing results**

| Arm | contract | cracked | v before | v after |
|---|---|---|---|---|
| A₅ from scratch | T=n | 8/22 seeds | — | ≈1.0 |
| A₅ from scratch | log-T | bimodal, weaker | — | ≈2 |
| A₅ anneal | T=n → log | 4/4 | 1.0 | 2.0 |
| S₄ anneal | T=n → log | 4/4 | 1.0 | 2.4 |
| S₄ anneal | log → T=n | 4/4 | 2.4 | 1.2 |
| S₅ operator-first | T=n | 10/10 | — | 1.0 |

The transferred mechanism is **re-priced** by the new contract, but without re-running the seed lottery.

### Halting Rule

Stopping at $T^\star = \lceil n/\hat{v} \rceil$ (with $\hat{v}$ estimated in distribution) recovers near-oracle accuracy at test lengths and avoids overthinking.

### Head Instruments Predict Generalization

**Table 8: Predicting OOD generalization (n ∈ {64, 128}) from strictly in-distribution measurements (n ≤ 32), 16 seeds per cell**

| Metric [ID, n ≤ 32] | S₄ log-T | A₅ prop-T | parity prop-T |
|---|---|---|---|
| frontier speed v₃₂ [head] | +.87 (.95) | — | +.38 (.62) |
| frontier completion@32 [head] | +.83 (.94) | +.90 (1.00) | +.58 (.84) |
| cosine (adjacent) [tail] | −.02 (.44) | −.77 (.03) | +.01 (.37) |
| Jacobian align. [tail] | −.61 (.10) | −.79 | +.11 (.44) |
| AA / path indep. | +.31 (.60) | −.66 (.14) | +.21 (.65) |

Entries: Spearman ρ (median-split AUROC). Head instruments dominate in every cell; the path-independence score never wins a cell.

### Open-Benchmark Validation

**Table 9: Easy-to-hard prefix sums** (train 32-bit official split)

| Arm | n=32 | n=64 | n=128 | n=256 | official 512 |
|---|---|---|---|---|---|
| T=n, seed 2 | 1.00 | 1.00 | 1.00 | 0 | 0 |
| T=n, seed 3 | 1.00 | 1.00 | 0.96 | 0 | 0 |
| T=n, seeds 0/1 (lottery) | 1.00 | 0 | 0 | 0 | 0 |
| log-T, all seeds | 1.00 | 0 | 0 | 0 | 0 |
| DT conv-RNN | solves 512 (locality-forced frontier) | | | | |

The frontier breaks between 128 and 256 bits—convolutional locality forces a linear frontier and shields it from long-range interference, whereas the frontier learned inside global attention inherits attention's length fragility.

---

## Theoretical and Practical Implications

### Theoretical Implications

1. **Instrument validity constraint**: Any loop-mechanism claim based on skip tolerance, cross-step similarity, or shared-dictionary attribution is uninformative unless localized to the head of the trajectory ($t < \tau^\star$). This is a general theorem (Proposition 1), not an empirical observation.

2. **Selection, not expressivity**: Which algorithm SGD finds is set by the architecture prior and the budget contract—not by what the architecture can express. Weight tying flips selection from parallel scans to serial frontiers.

3. **Learning walls are optimization objects**: Non-solvability blocks nothing at these scales; the order of the group sets the optimization cost of its operator. NC¹-hardness is free (A₅), operator scale is not (S₅).

4. **Localization–editing dissociation is architectural under weight tying**: Any weight edit hits every loop, so activation-space localization cannot inform weight-space editing even in principle.

### Practical Implications

1. **Halting rules**: The useful stopping signal is frontier completion ($T \geq n/v$), predictable per input length, rather than state convergence.

2. **Test-time compute**: The safe operating range of test-time compute is a contract property—pushing T far beyond frontier completion degrades tight-budget models (overthinking).

3. **Training design**: Budget annealing transfers mechanisms across contracts, bypassing seed lotteries. Operator-first curricula dissolve optimization walls.

4. **Interpretability for depth-recurrent LMs**: Instruments that probe converged states inherit Proposition 1's blindness; they should be replaced or augmented by head-of-trajectory measurements.

---

## Conclusion

The paper's central contributions are:

1. **The linear computation frontier and its budget law**: Free training installs a serial mechanism whose speed obeys $v \approx n_{tr}/T_{tr}$ (exactly 1.00 under T = n), with per-position loop-extrapolation rescue at fixed length.

2. **Algorithm selection is set by architecture prior**: Weight tying flips SGD's choice from parallel scan to serial frontier.

3. **Learning walls are optimization objects, not complexity-theoretic ones**: NC¹-hardness is free (A₅), operator scale is not (S₅), and an operator-first curriculum dissolves the wall.

4. **Mechanism portability**: Budget annealing transfers algorithms across loop contracts in 4/4 seeds, bypassing the from-scratch seed lottery.

5. **The measurement theory**: A saturation proposition showing standard instruments are blind at fixed points, the τ(n,i) head instrument with causal validation, and three 16-seed races in which head instruments predict seed-level generalization while tail metrics and path independence do not.

### Scope and Future Directions

- Claims concern what end-to-end training selects in weight-tied loops on per-position algorithmic sequence tasks at ≤25M parameters
- The S₅ result is a statement about optimization cost at |G|=120, not an NC¹ impossibility claim
- Pretrained depth-recurrent LMs (Huginn, Ouro) are out of scope; extending τ to them requires resolving tokenization and format confounds
- Future work: demonstrating that faster-but-equally-trainable solutions exist at the same contract (and are avoided) would require constructive search over solutions not yet performed

---

_Markdown view of https://picx.dev/p/BtiPo0, served by PicX — AI-generated visual whiteboard summaries of research papers._