Research map / Learning theory and algorithms / Kernels and regression theory
Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
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.
Studies how RNNs trained on the streaming parity task develop finite automata that generalize infinitely, using an interaction-based effective theory of representational merging in hidden states.
Problem
Explaining why neural networks sometimes learn algorithms that extrapolate infinitely in sequence length from finite training data, rather than merely interpolating, using the streaming parity task.
Approach
Models pairwise interactions between nearby hidden representations under gradient descent with an expressive smooth-map abstraction, showing representations that always agree on future outputs merge, which collapses the extracted automaton into a finite one and produces a sudden phase transition to full length generalization.
Key results
- RNNs trained on streaming parity up to length 10 generalize perfectly to sequences up to length 10000 once training succeeds, with a sharp phase transition in validation accuracy from 0.5 to 1.0 as data size grows and initial weight scale shrinks.
- Out of 103460 merged representation pairs, all agreed on all possible future outputs, supporting the merger condition.
- The learned automaton, after Hopcroft minimization, reduces to the two-state parity automaton.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a smaller initial weight scale and a larger training set | RNN on streaming parity · Streaming parity, validation sequences of length 100 | accuracy: 0.5 -> 1.0 | Helped |
| train on sequences up to length 10 | RNN on streaming parity · Streaming parity, sequences up to length 10000 | mean squared loss | Helped |
| replace ReLU activation with tanh (ablation) | RNN on streaming parity · Streaming parity | infinite generalization | No clear effect |
| add step-continuity to the output map (ablation) | RNN on streaming parity · Streaming parity | state-merger dynamics | No clear effect |
| use a transformer instead of an RNN | sequence models on parity computation · Parity computation, arbitrary-length sequences | infinite generalization | Hurt |
| use recurrent networks rather than transformers | sequence models · Parity computation, arbitrary-length sequences | infinite generalization | Helped |
| increase the training-set size or decrease the initial weight scale | RNN on streaming parity · Streaming parity | validation accuracy | Helped |
Surprising findings
- Transformers fail to fully generalize to arbitrary-length parity, while RNNs achieve infinite generalization in this setting.
- Redundant (equivalent) states are expected in the final learned automaton, and not all agreeing pairs merge.
Limitations
- Theory ignores global interactions, regularization, noise, and architectural inductive biases.
- Automaton interpretation may be incomplete for complex or continuous data settings.
- Discontinuous output maps give noisier dynamics; transformers are not explained by the same mechanism.
Experimental setup
Datasets: streaming parity task sequences up to length 10 random regular automata tasks modular subtraction
Benchmarks: streaming parity validation sequences up to length 10000
Metrics: validation accuracy validation loss number of automaton states fraction of merged pairs
Baselines: transformer
Builds on: deterministic finite automata extraction from RNNs Hopcroft's algorithm
Closest papers by meaning
- An exactly solvable model for emergence and scaling laws in the multitask sparse parity problem (NeurIPS 2024 · similarity 0.87)
- Learning High-Degree Parities: The Crucial Role of the Initialization (ICLR 2025 · similarity 0.87)
- Learning dynamics in linear recurrent neural networks (ICML 2025 · similarity 0.87)
- Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.86)
- Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.86)
- Deep Linear Network Training Dynamics from Random Initialization: Data, Width, Depth, and Hyperparameter Transfer (ICML 2025 · similarity 0.86)
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.