The Price of Recurrence: Parameter Equivalence and Circuit Complexity in Token-Recurrent Models

Weight tying across depth has a measurable exchange rate: under scaling-law fits, an additional pass through a shared Transformer block contributes a fraction of the capacity of a fresh layer. We ask whether recurrence across tokens admits an analogous parameter-equivalence coefficient, ϕₜ, measuring the ordinary capacity contributed by each recurrent parameter. We find that it does, but only below a boundary set by circuit complexity. We study prefix products over three groups of order 60: the abelian ℤ₆₀, the solvable D₃₀, and the non-solvable A₅, a standard NC¹-complete benchmark. On ℤ₆₀ and shallow-depth D₃₀, recurrent and non-recurrent models obey a common capacity law with ϕₜ ≈ 0.3. On A₅, this finite exchange rate breaks down: non-recurrent Transformers require depth that grows with sequence length, while a single nonlinear recurrent state replaces an increasing number of feed-forward layers. At the measured crossover, recurrence is equivalent to 11 ± 2 additional layers, and the equivalence increases with sequence length. The effect persists from 0.5M to 340M parameters and when the group operation is embedded in natural-language text. The distinction is specifically tied to nonlinear recurrence. A diagonal state-space baseline fails on A₅ in all 72 runs, whereas nonlinear recurrence succeeds in 34/72; scratchpad decoding also succeeds, but uses roughly 60× more inference compute. Optimization introduces a separate phenomenon: recurrent training is less reliable on D₃₀ than on A₅ because models first discover a shallow solution on the rotation subgroup. A two-stage curriculum over the reflection coset raises D₃₀ success from 22% to 97%. Across all 216 base runs, held-out loss is bimodal and a width-dependent phase-transition model predicts success rates to within four percentage points. Finally, recurrent A₅ solvers generalize to sequences 64× longer than those seen in training in all 26/26 tested runs. These results suggest that token recurrence behaves as a conventional capacity multiplier on problems with shallow circuits, but becomes a capability switch once sequential computation is required.