mlsanityData to 14 Oct 2026

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

arXiv 2507.09897 ↗First posted 14 Jul 2025cs.LG q-bio.NCcited by 0

Not on the map. Why?

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.

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

35 of 58 references.

References · 35

  1. 2022Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 smallcited by 1,165
  2. 2023Progress measures for grokking via mechanistic interpretabilitycited by 839
  3. 2018On Lazy Training in Differentiable Programmingcited by 675
  4. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  5. 2022Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasetscited by 629
  6. 2017Opening the Black Box of Deep Neural Networks via Informationcited by 503
  7. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 342
  8. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  9. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  10. 2022Towards Understanding Grokking: An Effective Theory of Representation Learningcited by 230
  11. 2022Exploring Length Generalization in Large Language Modelscited by 206
  12. 2023The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networkscited by 156
23 more
  1. 2023The emergence of clusters in self-attention dynamicscited by 140
  2. 2021Generalized Shape Metrics on Neural Representationscited by 112
  3. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 86
  4. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  5. 2017Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamplescited by 66
  6. 2019Universality and individuality in neural dynamics across large populations of recurrent networkscited by 61
  7. 2018Rearranging the Familiar: Testing Compositional Generalization in Recurrent Networkscited by 51
  8. 2024Deep Networks Always Grok and Here is Whycited by 51
  9. 2022Revisiting Transformer-based Models for Long Document Classificationcited by 49
  10. 2022The Onset of Variance-Limited Behavior for Networks in the Lazy and Rich Regimescited by 25
  11. 2024Opening the AI black box: program synthesis via mechanistic interpretabilitycited by 20
  12. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  13. 2023The Topology and Geometry of Neural Representationscited by 14
  14. 2023Eureka-Moments in Transformers: Multi-Step Tasks Reveal Softmax Induced Optimization Problemscited by 14
  15. 2016A recurrent neural network without chaoscited by 13
  16. 2023Aligned and oblique dynamics in recurrent neural networkscited by 10
  17. 2024When Representations Align: Universality in Representation Learning Dynamicscited by 10
  18. 2024Formation of Representations in Neural Networkscited by 10
  19. 2021Charting and navigating the space of solutions for recurrent neural networkscited by 8
  20. 2020Gating creates slow modes and controls phase-space complexity in GRUs and LSTMscited by 7
  21. 2022Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Netscited by 7
  22. 2019Visualizing Representational Dynamics with Multidimensional Scaling Alignmentcited by 3
  23. 2024Extracting Moore Machines from Transformers using Queries and Counterexamplescited by 2

Built on by

Not cited yet.