The Automaton Underneath: The Additive Input Pathway Is a Parasitic Attractor for State Tracking in Householder Linear RNN
Not on the map. Why?
Abstract (arXiv)
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 bt = Wb et. With bt, models fit length 32 and collapse out-of-distribution on parity, S4, A5, and non-solvable S5 word problems (0.20 at position 512 on S5). 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, S4 3, A5 and S5 4); below it, nothing fits. The contrast with DeltaProduct's S4/A5 at nh=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 Wb=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 bt fired its kill criterion: all 49 fitting seeds retain in-domain fit under Wb:=0 -- and at law-minimal width, zeroing Wb at inference restores exact generalization (parity 5/5, S5 5/5, S4 4/5, A5 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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 13 of its 13 references that are in the map. First posted on arXiv 16 Jul 2026.
Builds on
13 of 13 references.
References · 13
- 2022Neural Networks and the Chomsky Hierarchycited by 217
- 2024The Illusion of State in State-Space Modelscited by 187
- 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 101
- 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 75
- 2025Understanding and Improving Length Generalization in Recurrent Modelscited by 23
- 2024On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languagescited by 15
- 2026The Expressive Limits of Diagonal SSMs for State-Trackingcited by 9
- 2026M2RNN: Non-Linear RNNs with Matrix-Valued States for Scalable Language Modelingcited by 8
- 2026Learning State-Tracking from Code Using Linear RNNscited by 6
- 2025Revisiting Bi-Linear State Transitions in Recurrent Neural Networkscited by 4
- 2026Rethinking State Tracking in Recurrent Models Through Error Control Dynamicscited by 4
- 2026A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Trackingcited by 3
1 more
Built on by
Not cited yet.