# Algorithm Development in Neural Networks: Insights from the Streaming Parity Task

arXiv: https://arxiv.org/abs/2507.09897 · HTML: https://mlsanity.com/paper/2507.09897/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 58 references that are in the map.
- First posted on arXiv 14 Jul 2025.

## Builds on (most cited first, 30 of 35)

- [Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small](https://mlsanity.com/paper/2211.00593/) (2022)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Towards Understanding Grokking: An Effective Theory of Representation Learning](https://mlsanity.com/paper/2205.10343/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks](https://mlsanity.com/paper/2306.17844/) (2023)
- [The emergence of clusters in self-attention dynamics](https://mlsanity.com/paper/2305.05465/) (2023)
- [Generalized Shape Metrics on Neural Representations](https://mlsanity.com/paper/2110.14739/) (2021)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Universality and individuality in neural dynamics across large populations of recurrent networks](https://mlsanity.com/paper/1907.08549/) (2019)
- [Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networks](https://mlsanity.com/paper/1807.07545/) (2018)
- [Deep Networks Always Grok and Here is Why](https://mlsanity.com/paper/2402.15555/) (2024)
- [Revisiting Transformer-based Models for Long Document Classification](https://mlsanity.com/paper/2204.06683/) (2022)
- [The Onset of Variance-Limited Behavior for Networks in the Lazy and Rich Regimes](https://mlsanity.com/paper/2212.12147/) (2022)
- [Opening the AI black box: program synthesis via mechanistic interpretability](https://mlsanity.com/paper/2402.05110/) (2024)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [The Topology and Geometry of Neural Representations](https://mlsanity.com/paper/2309.11028/) (2023)
- [Eureka-Moments in Transformers: Multi-Step Tasks Reveal Softmax Induced Optimization Problems](https://mlsanity.com/paper/2310.12956/) (2023)
- [A recurrent neural network without chaos](https://mlsanity.com/paper/1612.06212/) (2016)
- [Aligned and oblique dynamics in recurrent neural networks](https://mlsanity.com/paper/2307.07654/) (2023)
- [When Representations Align: Universality in Representation Learning Dynamics](https://mlsanity.com/paper/2402.09142/) (2024)
- [Formation of Representations in Neural Networks](https://mlsanity.com/paper/2410.03006/) (2024)

## Abstract (arXiv)

Even when massively overparameterized, deep neural networks show a remarkable ability to generalize. Research on this phenomenon has focused on generalization within distribution, via smooth interpolation. Yet in some settings neural networks also learn to extrapolate to data far beyond the bounds of the original training set, sometimes even allowing for infinite generalization, implying that an algorithm capable of solving the task has been learned. Here we undertake a case study of the learning dynamics of recurrent neural networks (RNNs) trained on the streaming parity task in order to develop an effective theory of algorithm development. The streaming parity task is a simple but nonlinear task defined on sequences up to arbitrary length. We show that, with sufficient finite training experience, RNNs exhibit a phase transition to perfect infinite generalization. Using an effective theory for the representational dynamics, we find an implicit representational merger effect which can be interpreted as the construction of a finite automaton that reproduces the task. Overall, our results disclose one mechanism by which neural networks can generalize infinitely from finite training experience.