Research map / Architectures and efficiency / RNNs and normalization
Revisiting Bi-Linear State Transitions in Recurrent Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
The paper revisits pure bilinear (multiplicative, non-affine) hidden-state transitions in RNNs, showing they can simulate arbitrary state machines and learn state-tracking tasks that linear RNNs such as Mamba fail on at length generalization.
Problem
Many linear recurrent models (e.g., Mamba) and Transformers fail to learn state tracking that generalizes to sequences much longer than training data; it is unclear what recurrence form provides the right inductive bias.
Approach
Model the hidden-to-hidden transition as a pure bilinear function of the previous hidden state and the current input (no additive bias or input terms), so the input-dependent transition matrix is linear in the input; this makes hidden states scale-invariant and allows simulating any finite state machine, with factored and block-diagonal variants for parameter control.
Key results
- Full bilinear and factored bilinear models reach 1.00 OOD accuracy at length 500 on modular addition for moduli 2-50 (factored bilinear 0.95 at m=50).
- Mamba with 1-4 layers largely fails length generalization on modular addition (OOD accuracy near 0 for most moduli), while bilinear models stay at 1.00.
- Real-diagonal bilinear (block size 1) learns parity only, and a frozen random bilinear network with trained readout learns parity from two training examples, as predicted by theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use bilinear hidden-state transitions instead of a standard RNN | Recurrent model · Modular addition, m=50, length 500 | normalized accuracy: 0.07 -> 1.00 | Helped |
| Use bilinear hidden-state transitions instead of Mamba | Recurrent model · Modular addition, m=50, length 500 | normalized accuracy: 0.00 -> 1.00 | Helped |
| Use bilinear hidden-state transitions instead of an LSTM | Recurrent model · Random state machine, m=50, length 500 | normalized accuracy: 0.09 -> 1.00 | Helped |
| Use bilinear hidden-state transitions instead of Mamba | Recurrent model · Random state machine, m=50, length 500 | normalized accuracy: 0.07 -> 1.00 | Helped |
| Use bilinear hidden-state transitions instead of an LSTM | Recurrent model · Modular arithmetic, m=50, length 500 | normalized accuracy: 0.64 -> 0.99 | Helped |
| Use bilinear hidden-state transitions instead of Mamba | Recurrent model · Modular arithmetic, m=50, length 500 | normalized accuracy: 0.08 -> 0.99 | Helped |
| Constrain bilinear transition matrix to block size 1 (ablation) | Bilinear model · Modular addition, m=50, length 500 | normalized accuracy: 1.00 -> 0.02 | Hurt |
| Use larger blocks in block-diagonal bilinear transitions (ablation) | Bilinear model · Random state machine, length 500 | normalized accuracy: block size 1: 0.00 at m=50; block size 64: 1.00 at m=50 | Helped |
| Constrain bilinear transitions to block size 64 (ablation) | Bilinear model · Modular arithmetic, m=50, length 500 | normalized accuracy: 0.99 -> 0.21 | Hurt |
| Remove additive terms from the hidden-state update (ablation) | Diagonal and 2D block-diagonal bilinear models · Modular addition, length 500 | OOD accuracy | Helped |
| Add additive terms to the hidden-state update (ablation) | Full bilinear model · Modular addition, length 500 | OOD accuracy | No clear effect |
| Remove additive terms from the recurrent update (ablation) | Random multiplicative RNN with frozen recurrence and trained readout · Parity, test length 400 | OOD performance | Helped |
Surprising findings
- Pure bilinear transitions without additive terms are sufficient and in some cases necessary; adding additive terms degrades block-diagonal and real-diagonal models but not the full bilinear model.
- A frozen random real-diagonal bilinear recurrence with only a trained linear readout can learn parity from just two training examples.
Limitations
- Full bilinear models have very large parameter counts (roughly cubic in hidden size).
- Evaluated only on small synthetic state-tracking tasks, not language modeling.
- Real-diagonal and 2x2 block-diagonal models have restricted expressivity (commutative tasks only).
Experimental setup
Datasets: synthetic modular addition synthetic random state machine synthetic modular arithmetic
Benchmarks: modular addition (synthetic) random state machine (synthetic) modular arithmetic (synthetic)
Metrics: accuracy normalized so 0 is chance
Baselines: LSTM Elman RNN Mamba Transformer (GPT-2) R2 block-diagonal bilinear
Builds on: Mamba Elman RNN LSTM GPT-2 Canonical Polyadic decomposition
Closest papers by meaning
- Rethinking State Tracking in Recurrent Models Through Error Control Dynamics (NeurIPS 2026 · similarity 0.90)
- Recurrent neural networks: vanishing and exploding gradients are not the end of the story (NeurIPS 2024 · similarity 0.86)
- Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues (ICLR 2025 · similarity 0.86)
- Learning dynamics in linear recurrent neural networks (ICML 2025 · similarity 0.86)
- The Illusion of State in State-Space Models (ICML 2024 · similarity 0.86)
- (How) Do Language Models Track State? (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.