PaperlayerView exact revision on arXiv

Source-linked AI summary

The Automaton Underneath: The Additive Input Pathway Is a Parasitic Attractor for State Tracking in Householder Linear RNN

Gunner Levi Howe

arXiv:2609.18966v1cs.LGcs.NE

TL;DR

Linear RNNs can represent hard state-tracking automata, yet trained models often fail to generalize beyond training length, without a causal account of that gap. The paper tests a pre-registered deletion of the additive input pathway within one Householder architecture. Without that pathway, models generalize exactly at the widths admitted by a representation-relative law; with it, they fit training length and collapse.

  • Problem

    Linear RNNs can represent hard state-tracking automata, but trained models often collapse beyond training length, and prior work has not provided a causal account of this gap.

    Source: §1 · pp. 1–2

  • Method

    The paper pre-registers a within-architecture ablation of the additive input injection in a Householder linear RNN whose orthogonal transitions alone can represent the studied tasks.

    Source: §1 · p. 2, §2 · p. 2

  • Results

    At law-admitted widths, −b models reach exact accuracy at 16× training length, while +b models fit length 32 and collapse, including on non-solvable S5.

    Source: §1 · p. 2, §3 · p. 2

  • Takeaways & Limitations

    At law-minimal width, zeroing Wb at inference exposes the learned automaton and restores exact generalization in 18/20 seeds across the four group tasks.

    Source: §1 · p. 2, §6 · p. 5

    The evidence is limited to one architecture family, optimizer, budget, d=112, five two-generator tasks, point-tracking format, and five seeds per cell; scope beyond the family remains open.

    Source: §7 · p. 6

Abstract

from arXiv · show

Linear RNNs with input-dependent Householder-product transitions (DeltaNet/DeltaProduct-class) can provably represent hard state-tracking automata, yet trained models fail to length-generalize -- a gap recent work attributes to optimization, without a causal account. We give one, in a pre-registered, within-architecture causal ablation: the same model with one term deleted -- the additive input injection $b_t = W_b e_t$. With $b_t$, models fit length 32 and collapse out-of-distribution on parity, $S_4$, $A_5$, and non-solvable $S_5$ word problems (0.20 at position 512 on $S_5$). Without it -- input acting only through the orthogonal transitions -- the same architecture learns the exact automaton: median accuracy 1.00 at 16x the training length, at every width admitted by a representation law we state and test: the minimal number of Householder factors per token equals the maximal reflection length of the task's generators in the format-pinned representation (parity 1, $S_4$ 3, $A_5$ and $S_5$ 4); below it, nothing fits. The contrast with DeltaProduct's $S_4$/$A_5$ at $n_h{=}2$ (group-element classification, $SO(3)$ realization) shows the law is representation-relative: task format is a hidden variable in state-tracking benchmarks. Two pre-registered arms locate the mechanism. (i) Initialized at a verified-exact solution with $W_b{=}0$, Adam grows the additive path and pulls the model off the exact solution; $-b$ controls stay at 1.00. (ii) Our registered prediction that the fit routes through $b_t$ fired its kill criterion: all 49 fitting seeds retain in-domain fit under $W_b{:=}0$ -- and at law-minimal width, zeroing $W_b$ at inference restores exact generalization (parity 5/5, $S_5$ 5/5, $S_4$ 4/5, $A_5$ 4/5). The additive pathway is parasitic: it destabilizes, then conceals, a correctly learned automaton. All 202 runs pre-registered; all numbers regenerate from artifacts.

1 Introduction

The paper tests why Householder linear RNNs that can represent state-tracking automata fail to generalize when trained. In a pre-registered, within-architecture ablation, removing the additive input injection yields exact long-length tracking, while the injection is linked to destabilizing and concealing the learned automaton.

1 Introduction

  • Prior work reports optimization-related length-generalization failures, but the cited evidence does not causally isolate the additive pathway within one architecture.The introduction notes that cross-architecture comparisons can also remove capacity, and that PD-SSM’s S5 extrapolation with an additive term rules out an architecture-universal account.Source: §1 · pp. 1–2
  • The paper tests the optimization account in a fixed Householder linear RNN where orthogonal transitions alone are expressive enough for every studied task.Deleting the additive injection changes what SGD finds, not what the model can represent.Source: §1 · p. 2
  • At matched width, budget, and data, −b models learn the exact automaton to length 512 (16× training length), while +b models fit length 32 and collapse, including on non-solvable S5.The contrast is the paper’s central within-architecture result.Source: §1 · p. 2
  • The minimum Householder-factor count for generalization equals the maximum generator reflection length in the representation pinned by task format: parity 1, S4 3, and A5/S5 4.Every below-law −b cell is no-fit; the law is representation-relative, reconciling the S4/A5 group-element classification result at n_h=2.Source: §1 · p. 2
  • The additive pathway grows even from a verified-exact initialization and destroys length generalization, while −b controls remain stable.At law-minimal width, zeroing Wb at inference restores exact generalization in 18/20 seeds across parity, S4, S5, and A5.Source: §1 · p. 2

2 Setup

The setup uses one Householder-product recurrent layer and changes only whether the additive input injection is present. It evaluates per-step automaton-state tracking across specified generator-sequence tasks under a shared training protocol, with pre-registration and artifact regeneration documented.

2 Setup

  • Each recurrent step applies input-dependent Householder transitions to the previous state and adds b_t; a per-step linear readout predicts the automaton state.The −b ablation deletes b_t, so input acts only by selecting orthogonal transitions.Source: §2 · p. 2
  • Every cell uses the same 32-length sequences, 40 epochs, Adam, and training budget, with no cell-specific tuning.The model uses d=112.Source: §2 · p. 2
  • The task grid tracks a designated element under two-generator sequences for parity, mod-3, S4, A5, and S5; models train at L=32 and are evaluated per position through L=512.GEN is median position-512 accuracy above 0.9; shortcut means position-32 accuracy above 0.9 but below 0.6 at 512.Source: §2 · p. 2
  • The grid, predictions, kill criteria, and decision rules were committed before grid runs; the disclosed exploratory pilot was rerun from scratch under the harness.All reported numbers are regenerated from 202 run artifacts and byte-verified.Source: §2 · p. 2

3 One deleted term flips shortcut to exact automaton

The central comparison shows that the additive pathway yields training-length fit followed by collapse, whereas deleting it produces exact generalization at and above the representation-law width. Below that width, the core grid reports failure to fit.

3 One deleted term flips shortcut to exact automaton

  • At position 512, −b medians are 1.00 for parity, S4, A5, and S5; the +b pathway collapses beyond training length on every task that fits.The medians are over five seeds; S5 and parity have ranges [1.00, 1.00].Source: §3 · p. 2
  • At and above law width, +b cells shortcut while −b cells are exact; below it, S4@2, A5@3, and S5@3 both fail to fit.For S5, +b accuracy is 1.00 at position 32 and 0.20 at position 512; −b reaches 1.00 at position 512.Source: §3 · p. 2, Table 1 · p. 3
  • Figure 1 plots per-position median accuracy with seed min–max bands and marks training length 32; +b fits and collapses while −b remains exact through 16× training length, including S5.The comparison uses the same architecture at the same width.Source: §3 · p. 2, Figure 1 · p. 3

4 The law: minimal nh = generator reflection length, representation-relative

The minimum number of Householder factors needed for length generalization follows the generators’ reflection length in the representation pinned by the task format. The law is representation-relative, so task formats can support different widths for the same group.

4 The law: minimal nh = generator reflection length, representation-relative

  • A permutation generator’s reflection length in the defining representation is rank(I − P), and representability requires nh at least the maximum generator reflection length in the realized faithful representation.A transposition has length 1, a 4-cycle length 3, and a 5-cycle length 4.Source: §4 · p. 3
  • Siems et al. [10] generalize S4 and A5 at nh=2 using SO(3), while this task’s vector-state, per-step-readout format pins the defining permutation representation.The law that reconciles the results is representation-relative; task format is therefore a hidden variable in state-tracking benchmarks.Source: §4 · pp. 3–4
  • At the law width, −b models generalize; below it, cells do not fit, with minimal nh of 1 for parity, 3 for S4, and 4 for A5 and S5.Mod-3 is the labeled exception; S5 at nh=3 reaches only 0.27 at position 32.Source: §4 · p. 3, Figure 2 · p. 4

5 Mechanism: a parasitic attractor, discriminated by pre-registered arms

Training grows the additive pathway even from a verified-exact solution, pulling the model away from exact generalization. Yet zeroing that pathway can reveal an exact automaton underneath, making the pathway parasitic rather than necessary for the fit.

5 Mechanism: a parasitic attractor, discriminated by pre-registered arms

  • From exact initialization, the additive-path magnitude grows to 0.41 on parity and 0.77 on S5 as position-512 accuracy falls to 0.50 and 0.23; −b controls stay at 1.00.The exact-init experiments use five seeds per task; Figure 3 reports medians over five seeds.Source: §5 · p. 4, Figure 3 · p. 5
  • All 49 fitting +b seeds retain in-domain accuracy when Wb is zeroed, while at law-minimal width inference-time zeroing restores exact generalization in 18/20 seeds.Restoration is 5/5 on parity, 5/5 on S5, and 4/5 on both S4 and A5.Source: §5 · p. 4
  • The concealment effect is width- and task-scoped: above law width, zeroing Wb restores only 1–2/5 parity seeds, and mod-3 fails even without the additive path.At law width, S4 and A5 each restore in 4/5 seeds; mod-3 reaches 0.00 median position-512 accuracy at nh=4.Source: §5 · pp. 4–5
  • Exact-init experiments hold the initial solution and reachable-state distribution fixed, yet still observe the pull-off, so state coverage is not the operative variable in these experiments.The paper distinguishes this training-time account from prior accounts centered on inference-time error accumulation or data-distribution coverage.Source: §5 · p. 5

6 Discussion

In Householder linear RNNs, the additive pathway is a single-term source of the expressivity–learnability gap: it can destabilize a learned automaton and conceal it. Zeroing that pathway is a diagnostic and, at minimal width, can restore generalization; these claims are scoped to the studied setting.

6 Discussion

  • The additive input pathway is a single-term source of the gap in Householder linear RNNs: it destabilizes and then conceals an automaton the model has learned.The practical question shifts from how to make these models learn state tracking to how to stop this pathway from hijacking and hiding what they learn.Source: §6 · p. 5
  • Zeroing the additive path at inference is a one-line diagnostic for a concealed automaton and restores generalization in 18/20 seeds across four group tasks at minimal width.Per-seed exceptions occur, and the repair degrades off minimal width.Source: §6 · p. 5
  • The claims do not establish universality or a language-modeling prescription: they concern Householder-product linear RNNs under standard supervision, where transitions alone are expressive enough.In language modeling, the additive pathway carries content; deleting W_b is presented as a probe and mechanism demonstration, not a training recipe.Source: §6 · p. 5

7 Limitations

The evidence is bounded by one architecture family, optimizer, and budget, five two-generator tasks, and a point-tracking format. Whether the parasite account extends beyond this family and what separates locking from drifting tasks remain open.

7 Limitations

  • The evaluation uses one architecture family, optimizer, and budget, with d=112, five two-generator tasks, five seeds per cell, and point tracking with a per-step linear readout.Pre-registration is repository-native rather than third-party, and the disclosed June pilot preceded registration.Source: §7 · p. 6
  • Whether the parasite account extends beyond this family and what separates tasks that lock from those that drift remain open questions.Source: §7 · p. 6

A Reproducibility

The study pre-registered its grid and decision rules, generated results from run artifacts, and verified that the reported numbers regenerate. The runner checked task closures, reflection lengths, and exact-construction correctness before training.

A Reproducibility

  • The pre-registration preceded the grid artifacts, and every reported number is regenerated from 202 JSON run artifacts and byte-verified.Five seeds were used per primary cell and three for references.Source: A Reproducibility · p. 7
  • Before runs, the idempotent runner programmatically asserts group closures, generator reflection lengths, and exact-construction correctness.Source: A Reproducibility · p. 7
  • Training used d=112, 40 epochs, batches of 512, 4,000 length-32 sequences, Adam at 3×10^-3, and per-position cross-entropy; evaluation used 1,000 sequences at length 512.The full grid took approximately 53 minutes on one RTX 3080.Source: A Reproducibility · p. 7
Loading 2609.18966v1…