Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Authors: Loek van Rossem
Andrew M Saxe
Venue: ICML 2025 oral (2025)
Keywords: Out-of-distribution generalization
Algorithm discovery
Deep learning theory
Mechanistic Interpretability
Primary area: theory->deep_learning
TL;DR: We explain in a simple setting how out-of-distribution generalization can occur.

Abstract: 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 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.

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Loek van Rossem
Andrew M. Saxe 12
Abstract
Training data
Even when massively overparameterized, deep neural networks show a remarkable ability to gen- eralize. Research on this phenomenon has fo- cused on generalization within distribution, via smooth interpolation. Yet some settings neural networks also learn extrapolate to data far be- yond the bounds of the original training some- times even allowing for infinite generalization, implying that an algorithm capable of solving the task has been learned. Here we undertake case study of the learning dynamics of recurrent neural networks (RNNs) trained on the streaming parity task in order develop an effective theory of algo- rithm development. The streaming parity task is simple but nonlinear task defined on sequences up to arbitrary length. We show that, with sufficient finite training experience, RNNs exhibit phase transition to perfect infinite generalization. Using an effective theory for the representational dynam- ies, find an implicit representational merger effect which be interpreted the construc- tion of finite automaton that reproduces the task. Overall, our results disclose one mechanism by which neural networks can generalize infinitely from finite training experience.
0.50
11
+ 0
001
+
0101
+ 0
Loss
0.25
Validation
0001001100
0.00
1000
1010111001101
Epochs
Figure I. Sequence length generalization of a recurrent network a simple task. Left: Example sequenees of the streaming parity task, from the training dataset (short sequences) and the validation dataset (long sequences). Right: The mean squared loss of recurrent neural network during training on the streaming parity task. Note that the loss also goes for sequences much longer than found in the training data. This was tested for sequences up to length 10000.
2020) in particular to sequences with lengths not seen in the training data (Dai et al., 2022; Abbe et al., 2023; Cohen- Karlik et al., 2023). These results surprising as gradient descent provides clear incentive to generalize beyond the training domain. Why do deep learning systems sometimes develop proper computational algorithms, instead of simply interpolating the data? Understanding this crucial for the safe application of machine learning models, as for instance, models can appear to generalize initially, but break after moving too far away from the training domain (Anil et al., 2022; Zhou al., 2024). Similarly, in neuroscience, important goal is to try to figure out the types of algorithms the brain employs. This is particularly difficult since the brain is so complex, interconnected, and poorly understood (Thompson & Best, 1989; Olshausen Field, 2006) that is unclear how to even recognize an algorithm when we see it. Instead, studying the dynamics of algorithm development in the brain might be more tractable (Richards et al., 2019). as learning rules may not be complex the learned algo- rithm itself. Despite attempts to understand these dynamics (Zhou et al., 2021; El-Gaby et al., 2024), it is still a highly challenging problem by itself. Here we hope to provide a better sense what to look for in the brain, by answering analogous questions in simpler setting.
1. Introduction
Examples of computational algorithms appearing deep networks are numerous (Olah et al., 2020; Goh al., 2021; Wang et al., 2022; Power et al., 2022: Nanda et al., 2023: Zhong al., 2023). Furthermore, recurrent neural networks and transformers have shown noteworthy ability to gener- alize (Loula et al.. 2018; Lake & Baroni, 2018; Brown et al.,
'Gatsby Computational Neuroscience Unit, University Col- lege London "Sainsbury Wellcome Centre, University Col- lege London. Correspondence to: Lock van Rossem clock.rossem.22ee. 22w....c.....................
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Let us consider a relatively simple computational problem for which algorithm development can still be studied: the streaming parity task (Figure 1). Given a sequence of zeros and ones with varying length, the aim of the task is to output a zero when the number of ones is even and output a one when the number of ones is odd. A recurrent neural network trained only on sequences up to some short finite length will sometimes generalize infinitely. It is able to solve the task accurately for any sequence length no matter how large, even for sequences thousands of times longer than shown in the training data.
the network may be helpful, it does not directly say much about the nature of the computations being performed on that representational space. Moreover, the representational geometry can vary greatly across RNN architectures trained on the same task (Maheswaranathan et al., 2019).
One common approach to interpret RNNs is with dynamical systems (Sussillo & Barak, 2013; Laurent & Brecht, 2016; Can al., 2020; Driscoll et al., 2024). Here, due to our focus computational algorithms, we will instead be in- terpreting the recurrent neural network using deterministic finite automata (DFA), an approach also well known in the RNN literature 1992; Omlin & Giles, 1996; Tino et al., 1999; Weiss et al., 2020; Merrill & Tsilivis, 2022; Michaud al., 2024), which has also seen some applications in neuroscience context (Turner et al., 2021; Brennan et al., 2023).
As longer sequences are not within the same domain as shorter sequences, the generalization cannot simply be ex- plained by interpolation. One can continue feeding in sym- bols and the network will continue predicting correctly, sug- gesting it has somehow learned computational algorithm. It is unclear how such an algorithm can develop during training from gradient descent optimization. The network is trained to reduce its loss only on the shorter sequence dataset; it is not penalized for breaking after a certain length.
Servan-Schrriier et al., 1989; Giles et al.,
A DFA consists of set of states including an initial state, transitions between the states given input symbols, and an output symbol for each state. An example of such a DFA solving the streaming parity task can be seen in Figure 2.
The main goal of this paper is to find simple mathematical models able explain this seemingly surprising behavior. Our main contributions are follows:
output 0 initial
output 1
In Section 3, we provide a local interaction theory for representational learning dynamics in recurrent neural networks.
Figure 2. Example of two state DFA solving the streaming parity task. Every time it receives 1 an input it alternates between the state that will output 0 and the state that will output 1. When it receives 0 it remains in its current state.
In Section 4, we explain how these interactions can result in the development of an algorithm capable of out-of-distribution generalization.
In Section 5, we find algorithm development occurs in two phases: an initial tree fitting phase, and a secondary generalization phase.
2.2. Automaton Extraction
We will use a relatively simple method for constructing an automaton from the representational space of an RNN, as this will be enough for our purposes. Consider an abstract recurrent neural network:
2. Automata and Recurrent Neural Networks
2.1. Interpreting Recurrent Neural Networks
h4 = f (1))
(1)
The first step to understanding the development of computa- tional algorithms in recurrent neural networks, is to choose the right way of representing the information that defines the network. The model's parameters are a complete but poor representation. They also contain a large amount of redundant information, e.g. swapping the order of neurons does not affect the encoded algorithm in any way.
y/ (
where the exact forms of the recurrent map fn. and out- put map fy will depend on the architectural details of the network.
From the hidden representations of this network we can extract a deterministic finite automaton. States are defined to be the hidden representations after receiving each sequence. transitions are determined by following where states go after the network received an input symbol, and outputs are simply the network's 's output map evaluated at each state. This procedure is illustrated in Figure 3.
For analyzing the inner structure of neural networks better approach is to consider the geometry of the representational structure, i.e. how are the hidden activations correspond- ing to the data structured in the network (Lin et al., 2019; Williams et al., 2022; Lin & Kriegeskorte, 2023). This is however, still not ideal in the context of computational algo- rithms. Although understanding how data is represented in
When two different sequences of input symbols are assigned the same internal activation vector, an additional application
2

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
3. Implicit State Merger
h
3.1. Intuition
1
fy
Why would states merge during training? The represen- tational space typically high-dimensional, so seems statistically unlikely that many different representations end up at the same vector by chance. The key insight here is that, due to continuity, sometimes the fastest way for gradient descent to minimize the loss is to merge nearby representa- tions.
y
initial
0
output
1
0
10
As an example for illustration, suppose that at some point during training, two sequences in the dataset agree on target outputs, and one already has the correct predicted output. Then, if the recurrent map fa. adjusts to move the other rep- resentation closer, its target output will also move towards the correct prediction, as the output map fy is continuous. Continuity thus gives rise to an interaction effect between nearby representations, potentially resulting in merging.
fn
Figure 3. Example of the automaton extraction procedure. Before the network has seen any input symbols the internal vector of hidden activations has some initial value ha. which will call the initial state of the automaton. After seeing a symbol, say e.g. 1, the hidden activations change to different vector fi, 1). We will call this vector the state corresponding to input sequence 1, and say that the initial state has transition to the state after receiving the input symbol 1. We can repeat this procedure for all possible sequences, to define a state for each one and transitions on cach state for every possible input symbol. We can assign an output cach state by evaluating the output map on its corresponding representation.
Implicit bias from gradient descent is well-studied topic in the deep learning literature (Neyshabur et al., 2015; Gu- nasekar et al., 2018; Chizat & Bach, 2020; Soudry et al., 2022). However, the relatively simple effect we are consid- ering here will turn out to be particularly interesting in the context of algorithm development in RNNs.
of the recurrent map will send them to the same internal activation vector for any possible input symbol received. Their activations will remain the same in the future, and the output map will always assign them the same output from that point on. They can no longer be distinguished, so we will consider them to be the same state in the automaton.
3.2. Interaction Model
Let us attempt to formalize this intuition by modeling the interaction between two nearby states, using the modeling approach from (van Rossem & Saxe, 2024), adapted for recurrent networks. Suppose that we have two input sequences x1 ... ....(-m) and x/2 ....22 ..f").....f in our dataset, with corresponding hidden representations h((=;)) (,())),, h((z)") ...... ((m=))). We would like to un- derstand the behavior of these representations when they get near each other during training, in an arbitrary neural network.
(ma) ...)((m))
If enough representations overlap, it may be the case that all transitions go to already existing states. At this point, we have a finite set of states capable of representing all possible internal states of the network. These states, together with the transitions between them and their outputs, form discrete computational algorithm capable of producing outputs on input sequences, which match the outputs of the RNN. For more details on automaton extraction, see Appendix A.
Arbitrary architecture with high expressivity. Instead of analyzing this interaction for a specific recurrent architec- ture, we model it for an arbitrary network with high expres- sivity, meaning any network large and complex enough to have the freedom to behave like a smooth map. Under this assumption, we replace the effect of the assignment of hid- den states by the network's 's parameters with two arbitrarily optimizable vectors h2 h2. and replace the effect of the net- work assigning output prediction those hidden states with arbitrarily optimizable smooth maps V1...., Uu (schema- tized in Figure 5). Note that because we are dealing with a re- current architecture, there may be multiple data points which have h( ... 2 (m1)) or h(xx
2.3. Automata During Training
In order to visualize the development of an algorithm, we extract automata at each epoch from an RNN during training on the streaming parity task (Figure 4). We can see that, due random small weights, the automaton initially has few states and random outputs. As the model trains, the automaton expands into a complete tree fitting the training data. Then, right when the training loss becomes zero, states in the automaton appear to merge until it becomes finite, and we see generalization on all data. To understand this better, we will first try to model the representational dynamics, and then study the induced dynamics on the automaton.
...... ..22 ((22) as intermediate hidden states. Thus, we have N output maps, one for each possible sequence after x1 ... #1 (m1) and (1) 22
(1) .......
(m2)
3

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
0.30
Training loss
0.25
Validation loes
Number of states
0.20
Loss
0.15
0.10
Initial state
0.05
State with all outgoing edgas shown
0.00
Epochs
State with unshown outgoing edgee
250
500
750
1000
Figure 4. Automata extracted from the hidden layer of an RNN during training on the streaming parity task. First the model fits the training data with complete tree. After that states merge until the automaton becomes finite, which is when generalization occurs. The RNN consisted of single fully connected recurrent layer with 100 units and ReLU activation. It was trained on all examples of the streaming parity task, up to length 10.
To simplify the theoretical analysis, we assume here that any sequence ø1 (1) (m1) ([1). ... ((m=) in the dataset has a matching sequence 222
We will take gradients with respect to these arbitrary smooth maps. While neural network may not optimize with smooth map dynamics and the gradient will depend on the architectural details, universal approximation theorems (Hornik et al., 1989; Csáji, 2001) tell us that expressive one is at least able to freely model smooth maps. Therefore, we are modeling simple behavior that, at least in princi- ple, any expressive network can exhibit. The exact details of the architecture are not required to understand the key mechanisms by which the network learns solve the task. Abstracting them away may help to find simpler and more intuitive explanations.
(1) ...22 (11)). (mm)) and vice
versa, we do not expect pairs for which this is not the case to contribute to the interaction.
h
y
h
(1)
21
hg
(1 a
Note also that the maps h1 h2, Vi... may share param- eters. They are not independent smooth maps. However, the network is expressive enough, it can still have enough freedom to effectively optimize each map independently at specific points, so we will choose to ignore potential interaction effects arising from parameter sharing.
dh
v(x50)
(ma))
v(rg
Figure 5. Schematic illustration of the interaction model be- tween two nearby representations corresponding sequenees a1 ......... _().)).(mm) (mm] and 2 ... x12 (m02) The effect of the model as- signing their representations is abstracted away with arbitrarily optimizable vectors hy and h2, and the effect of the model assign- ing outputs for every of the N subsequent sequences the training data is abstracted away with arbitrarily optimizablc smooth maps W) UN-
Local linear approximation. As trying model the interaction between two representations, we will con- sider the case where the distance dh == ho h1 between them is small. We can thus take linear approximations of the maps y1.... UN around the representational mean i (h2 h1):

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
3.3. State Merger Condition
The final representational distance is exactly solved in Ap- pendix B.2 to find:
y( ... x.. x(1) ... ... {(m))) ~ Di + Dv. (ha - h-a),
(2)
where a E 1, and i E ,,
|ddllp
Anigh + V
A
high
+ A
A
(5)
In general, the dynamics are undefined without speci- fying the parameterization. However, for the local lin- earized system, there is unique choice of parameter- independent dynamics, namely by optimizing with re- spect to the effective linear parameters of the network h1, h2, .1..... : MN, Dy....., Dyx For the mean squared loss
where
Anigh |lch NTy [|dyy(()]
Th |Ich(0) 12
(6)
NT V V(lls,, --,,,ll)))
Alow
Th
Note that these results not dependent the details of the neural network architecture used here. They the results of an interaction effect locally present in any smooth, expressive machine learning system with hidden representations.
1 L 1-1(1b 2
<1l0: + Dy. (ha - h aa - )
(3) after taking the continuous-time limit and considering so- lutions where representations either move closer or further away form each other, we find the self-contained 3-scalar system
A merger occurs when the final representational distance zero, which is when
Alaw = 0 and Anigh < 0.
Suppose the network's parameters are initialized at some scale G < 1, where G the average decrease of represen- tational distances when applying the recurrent map. We roughly have
1 1
|chlll
(wi)s
di
2 Th
c di (1]dysl1))s
1
<lldyall 11 1|)
||ch||2 2
(ws))
2 Nr,
Th
|ddill2
[d)(1) & G" dy. (0) 12 [d(
d
(w))s
1
(3 (11)
(8)
dt
4 N Ty
)/ x G
+ (11v2.
vi. lddh|1
where m min (m1, m2) and n min (n1...., ........,, nN are the minimal sequence lengths of the sequences correspond- ing to the representations and their potential subsequences respectively. Equation (7) then reduces to the condition
1 (w:)+
((Idd; (w))..
4 Th
v, vi. v2,4 and C N Gm-
where ||dh||2 the squared representational distance, (lldy.ll 112) the average squared prediction distance, and (wi)s 12 dy, (V2. vi.))): the average of output alignment metric. The constants 1/TT and 1/T, are the effective learning rates of the representational map and
where C is an unknown constant depending on the network architecture.
We can make three observations from this:
output map respectively, as we are now optimizing with respect to these smooth maps as opposed to the model's parameters. The derivation and more details can be found Appendix B.I.
The only states that can merge are those which al- ways agree on outputs after receiving both the same sequence.
States only merge if the sequences they correspond to are long enough.
Note that because are considering the continuous-time limit, noise has been introduced, and also did not include any form of regularization. Any results in terms of generalization are from inductive biases in gradient descent alone, e.g. the intuition discussed in Section 1.1. Regulariza- tion and noise may also play a crucial role in generalization some settings (Zhou et al., 2019; Ziyin al., 2025).
3. Mergers only start to occur given enough data and small enough initial weights.
We will study these observations and their implications in more detail the next section.
5

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
4. Automaton Development
Train
0.50
4.1. System of Interacting Particles
100
The interaction model requires the states to be close to each other. It does not model the global behavior of the dataset during training, only the local interaction between any two states. Many other things may oceur during training, which potentially more complex and exist on a global scale. We will ignore these effects here and treat the representational learning dynamics as a system of locally interacting particles (Liu et al., 2022; Geshkovski et al., 2023). The aim is to investigate how much of algorithm learning in recurrent neural networks can already be explained from this simple interaction alone.
250
0.25
1000
2500
10000
0.00
500
1000
Epochs
Figure 6. Validation loss for sequences of varying lengths during training on the streaming parity task. The validation loss initially does not change while the training loss goes down, but some point it suddenly drops for all sequence lengths at the same time.
4.2. Developing an Algorithm
We can see from Equation (9) that two states will only merge if they agree target outputs for any possible subsequence in the data, i.e. they need not be distinguished in order to solve the task'. Indeed, out of all 103460 pairs of repre- sentations that ended up merging, all agreed on all possible future outputs.
0.15
Sequencee length
0.10
Once enough of such pairs merge, the automaton will be- come finite. Because the merging of agreeing pairs does not affect the output of the automaton, it will still predict correctly the training data. If, such as for the streaming parity task, the task can be expressed with a finite automa- ton, and the training dataset is large enough, the learned automaton and task automaton must agree on all possible sequences. particular, as long as the training dataset con- tains all sequences up the length of the task automaton's 's size, it is guaranteed that the automata are equivalent, as all its reachable states can be reached with the training data, which the two automata agree.
10
0.00
Soquence length
Figure 7. Fraction of pairs agreeing on all future outputs that ended up merging after training on the streaming parity task. We can see that mergers only start to occur once m min(m1,, mz) reaches certain threshold.
Because not all pairs agreeing on all future outputs merge, redundant states will be present in the learned automaton. In fact, from Figure 7 it can be seen that not even all of the agreeing pairs that reached the minimum length threshold ended up merging. A possible explanation for this is that some pairs that never end up getting close during training, and therefore the effects from the interaction model do not apply.
When the learned automaton becomes finite, the behavior of the RNN becomes fixed for any sequence length, and we should see instant generalization on all lengths. This sudden complete generalization can be observed in Figure 6.
4.3. Redundant States
It is not necessary for all agreeing pairs merge to fully generalize, only enough for the final automaton to become finite. Redundant states are consequently expected to be learned. The final automaton in Figure 4 has far more states than the minimal two required to solve the task. However, it is still equivalent computational function to the two-state automaton shown in Figure 2, which can be seen by merging all its redundant states (Figure 8).
Since weights are initialized small, i.e. G < follows from Equation (9) that the first pairs to merge when decreas- the ones for which
ing the weight initialization is minimal. Therefore, representations corresponding to shorter sequence pairs may not merge, even when enough longer sequences do. For the training data used here, the smallest possible n is O, so we should start to see mergers once m reaches a certain threshold, which can be observed in Figure 7.
Redundant states in the brain There is some evidence of redundant states in the brain (Morcos & Harvey, 2016; Marmor et al., 2023). From a functional perspective, is not so clear why these states may exist. However, as can
In language of automata theory, this is equivalent to ab- sence of a distinguishing extension on the pair of input sequences.
6

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
5. Merger Dynamies
5.1. Two Development Phases
Something that remains unclear about the dynamics in Fig- ure 4 is the presence of an initial phase where the automaton expands into a complete tree of all possible sequences, be- fore phase of mergers resulting in finite algorithm. Why would the RNN learn to memorize individual outputs per imput sequence in the first place, only to collapse into finite automaton later?
Figure 8. Learned automaton in the RNN from Figure 4 after redun- dant state reduction using Hopcroft's 's Algorithm (Appendix A.3). It is equivalent to the automaton representing the streaming parity task Figure 2.
be seen from the above argument, purely from learning dynamics perspective, they expected in the final learned automaton. Similar representations containing scemingly identical information have also been observed in other ma- chine learning settings such as wide feed-forward networks (Doimo et al., 2021).
5.2. Fixed Expansion Point Interaction Model
A relatively simple dynamical explanation for this behavior can be found in the representational drift of each interaction pair. the two representations during an interaction start to drift, and their effective learning rates 1/7ha 1/The differ, they will drift at different speeds. In this case, their distance may initially start increase one outpaces the other.
4.4. Full Generalization Phase Transition
Finally, we can see from Equation (9) that the merger condi- tion only holds given a small enough initial weight scale G and a large enough number of datapoints N. As either the weight initialization is decreased the training set size is in- creased, agreeing states will start to merge. This can be seen on the left side of Figure 9, At some point, enough states will have merged such that the automaton becomes finite, and the RNN will generalize to all sequences. Since no state mergers can occur before the merger condition reached, we see sharp boundary in number of states and in particu- lar in the validation accuracy on the right side of Figure 9, splitting the training setting landscape into two regimes; one where it fits the training data with complete tree, and where it learns finite, generalizing representation of the task. Such separation resembles the phenomenon of rich
The local interaction model we have considered does not exhibit this behavior, as the linear expansion point is cho- sen to be at the moving representational mean, enforcing a representational movement symmetry. In Appendix B.3 the analytical learning trajectory for an agreeing pair is solved for in this model, and their representational distance can be to decay exponentially.
To allow for enough freedom in the interaction model for both representations to drift freely, we can instead keep the expansion point fixed:
y( ... (0.)...(()))))).).. x()) ... I.. {m))) Ur Dy.ha- (10)
Number of states
Validation accuracy
The downside of this choice is that the pair drifts far away from the expansion point, the interaction model may lose accuracy. In Appendix B.4 we use a similar approach as before to reduce these dynamics to a self-contained system of 9 variables.
2000
1.0
0.2
0.2
Initial weight
Inittal weight
0.4
0.8
0.8
0.6
Au6
0.8
500
0.8
1.0
0.4
5.3. Diverging Mergers
Training data fraction
Training data fraction
We can see from numerical solutions to this system (Fig- ure 10) that agreeing pairs initially diverge before they end up merging. This divergence is only present when the effec- tive learning rates 1/Th, 1/Th, differ. Experimentally. we find qualitatively similar divergence behavior the RNN during training. We also see that the divergence occurs more often in pairs with higher effective learning rate difference (Appendix D.3). Such an initial divergence of many agree- ing pairs, may explain the tree fitting phase. A division in two phases with some similarities has been studied in feed-forward networks in (Shwartz-Ziv Tishby, 2017).
Figure 9. Left: Number of states at convergence function of training dataset size and initial weight scale used. Right: Validation accuracy of 30 sequences of length 100. All trials converged on training set. Note the sudden jump from chance (0.5) to complete generalization (1.0) at enough data and small enough initial weights.
and lazy learning found in RNNs (Schuessler et al., 2024) and other settings (Chizat et al., 2020; Flesch et al., 2021; Atanasov al., 2022).
7

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Theory
Experiment
100
0.50
Loss
0.5
0.25
2-
Training loss
Distance agrosing pair
Distance disagreeing pair
0.0
0.00
0-
0
500
1000
0
500
1000
500
350
600
Epochs
Epochs
Epochs
Figure 10. Left: Numerical solutions of the fixed expansion point interaction model. The representational distance of pair agrecing on all possible future outputs first diverges before finally merging, whereas pair which disagrees on some outputs only diverges. Right: Normalized experimentally observed representational distances from a randomly selected pair with agreeing outputs that ended up merging, and randomly selected pair with disagreeing outputs.
6. Other Settings
ing dynamics. To investigate this, we compute the number of states in transformer during training on the modular subtraction task from (Power et al., 2022). As can be seen from Figure 11, we do not find a clear state merger pattern in the hidden representations of the transformer. However, we do see a state merger pattern in the attention matrix that is reminiscent the two phases found in recurrent networks. A similar pattern was found for local complexity measure in (Humayun et al., 2024).
6.1. Random Regular Tasks
The ideas considered in this paper should be applicable to any task that can be described by an automaton. Therefore, all experiments were also performed on a set of tasks defined by randomly generated automata. Similar results were found as with the streaming parity task (Appendix D.5).
6.2. Architecture Independence
The merging of attention patterns may possibly play an im- portant role in representation merger recurrent neural networks. Other phenomena observed here in RNNs also resemble behaviors in transformers, such as sudden transition to full gener- alization (Hoffmann al., 2024). The exact way which a transformer can learn algorithm from mergers is not as clear and requires further study.
generalization, similar to
The local interaction models discussed here are universal with respect the neural network architecture. They rep- resent intuitions that apply to any model with a smooth, expressive recurrent map on some hidden space and simi- larly smooth and expressive output map on this space. To illustrate this, we replaced the ReLU activation function with a hyperbolic tangent and found similar qualitative re- sults (Appendix D.6).
6.3. Transformers
Training loss
10.0
Transformers have been shown exhibit a similar ability to learn computational algorithms. One may wonder what extent the ideas considered here for recurrent networks still apply to the transformer architecture.
Validation loss
Number of states (attention)
7.5
Number of states (hidden)
Loss
5.0
The interpretation of the internal structure via an automaton not as clearly applicable to a transformer. The recurrent map was an essential ingredient in the understanding of the formation of a finite automaton, as it allows for mergers result in automaton transitions going previous states. Interestingly enough, despite some generalization larger sequence lengths, transformers fail to fully generalize to sequences of arbitrary length on parity computation (Anil et al., 2022).
2.54
0.0
25000
50000
75000
Epochs
Figure 11. The training loss, validation loss, number of states in the attention matrix, and number of states in the hidden layer of single layer transformer trained on modular subtraction. Note that the pattern of state mergers after initially state splitting is only present in the attention matrix, but is absent in the hidden space.
However, the intuition behind the local interactions from continuity still applies, and so we may still find similar merg-
8

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
6.4. Discontinuity
must be specifically highlighted here.
One of the assumptions in the interaction model is continuity of the recurrent and output maps. This may not necessarily be a reasonable assumption in the context of neuroscience, as the spiking coupling between neurons is not typically viewed as continuous. For the intuitions to work, however, we only really need predictions of nearby representations to move closer when the representations do on average. Conti- nuity gives us this, but may not be a necessary condition. To explore this, we add a step-continuity in the output map of the recurrent network. We find qualitatively similar results, albeit with noisier dynamics Appendix D.9.
A Acknowledgements
We thank Stefano Sarao Mannelli and Chenxiao Ma for useful feedback. This work was supported by a Sir Henry Dale Fellowship from the Wellcome Trust and Royal Soci- cty (216386/2/19/Z) to A.S., and the Sainsbury Wellcome Centre Core Grant from Wellcome (219627/2/19/2)) and the Gatsby Charitable Foundation (GAT3755).
References
Abbe, E., Bengio, S., Lotfi, A., and Rizk, K. Generaliza- tion on the Unseen, Logic Reasoning and Degree Cur- riculum. In Proceedings of the 40th International Con- ference on Machine Learning, pp. 31-60. PMLR, July 2023. URL htt.https//ppoceeeeeeeee 1202/abbez2 html. ISSN: 2640-3498.
7. Conclusion
Despite the surprising nature of infinite generalization from finite data, there exists a setting in which it can be under- stood through relatively simple intuitions about inductive bias in gradient descent. In this setting, we found that al- gorithm development occurs in two phases, an initial tree fitting phase and secondary merging phase that results in generalization. The merging phase occurs via a phase transi- tion, when the right training conditions are met. Therefore, algorithm learning and infinite generalization can occur in deep networks, but not consistently. We also saw that from dynamical perspective, redundant states are expected in the final learned algorithm. This is of particular interest to neuroscience, as it suggests that different animals may learn different but equivalent versions of an algorithm, which is something that should be taken into account when compar- ing representations. Finally, we found that intuitions about automaton formation do not apply as well to transformers, and that at least for some specific tasks, recurrent networks have an advantage in terms of infinite generalization.
mlr. press/
Adriaensen, R. and Maene, J. Extracting Fi- nite State Machines from Transformers, October 2024. URL http:// / aarxivivivv.//aaia/aaaaaaaaaavva org/abs/2410 06045. arXiv:2410.06045 [cs].
Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. Exploring Length Generalization in Large Language Models, November 2022. URL http:// abs/abs/////eeeeooeee.//////a.er abs 2207 04901. urXiv:2207.04901 [cs].
arxiv.org//aao
Ashby, W. R. Automata Studies: Annals of Mathematics Studies. Number 34. Princeton University Press, April 1956. ISBN 978-0-691-00916-5. Google-Books-ID OL571ECEEEWC.
Atanasov, A., Bordelon, B., Sainathan, S., and Pehlevan, C.
The theoretical approach used here is rela- tively simple and not necessarily a realistic model of the complete learning dynamics. Higher-order local interac- tions, global interactions, inductive biases from architectural choices, regularization, and noise were ignored, but may have additional effects algorithm development worth studying. Additionally, the interpretation of an RNN as an automaton may provide incomplete information in more complex or continuous data settings. Other mathematical objects may be necessary to properly represent the internal structure of an RNN in such settings.
Limitations
The Onset of Variance-Limitte Behavior for Networks in the Lazy and Rich Regimes, December 2022. URL https: /alss///axvvv.. org
www./org//aaaaaaooooooooooes http:/bb//22111 2212. 12147v11.
Brennan, C., Aggarwal, A., Pei, R., Sussillo, D., and Prockt, A. One dimensional approximations of neuronal dynamics reveal computational strategy. PLOS Compu- national Biology, 19(1)=e000088) January 2023. ISSN
1553-7358. doi: 10. 10.1377ijommal.ppb..0000777
URL p.oscomptiol//rrticceleeee
https: / http://ooonanas...ss.. org/
journal Nournal.pcbi.111 pcb..111108...... Library of Science.
Publisher:
Public
Impact Statement
This paper presents work whose goal is to increase under- standing of deep learning, which may lead to advancements in the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M.,

---

Doimo, D., Glielmo, A., Goldt, S., and Laio, A. Rep- resentation mitosis in wide neural networks. October net/forum? Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Wu, J. Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M. Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language Models are Few-Shot Learners, July 2020. URL http://ttt... arxi vixiv..oo 14165. arXiv:2005.14166 [es].
mapping behavioural structure. Nature, 636(8043): 671-680, 2024. ISSN 0028-0836. doi: 10.1038/ $411886002-088145-x URL http:://wwwwccc. nim. http:///wwo...aaaaaaaaes////A1//
Flesch, T. Juechems, K., Dumbalska, T., Saxe, A.. and Summerfield, C. Rich and lazy learning of task representations in brains and neural networks, April 2021. URL https: /www: www.xii.orggg............o...... content/ /10 101111112222111 2...2...411882
Can, T. Krishnamurthy, K,, and Schwab, D. J. Gat- ing creates slow modes and controls phase-space complexity in GRUs and LSTMs. In Proceedings of The First Mathematical and Scientific Machine Learning Conference, pp. 476-511. PMLR, August 2020. URL https:::: /ttp:s/:///occeeeeeeemmmoe nag.oceddinn.... mlr. ..press//// v107 v107/can20a, html. ISSN: 2640-3498.
Pages: 2021.04.23.441 128 Section: New Results.
Geshkovski, B., Letrouit, C., Polyanskiy, Y., and Rigol- let, P. The emergence of clusters in self-attention dynamics. Advances in Neural Information Pro- cessing Systems, 36:57026-57037, December 2023. URL
Chizat, I.. and Bach, F. Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss. In Proceedings of Thirty Thirl Confer- ence on Learning Theory, pp. 1305-1338, PMLR, July 2020. URL /ttp//eeeceeeegeeeeeeeeeepoc...e wmw.iinnnsmm.......mmmmmm.mmmm.m mlr. press// v125 1125/chizat22a html. ISSN: 2640-3498.
selida.iie mit www.miiittttii.ee edu//p/ .pdf.
Giles, C. L., Miller, C. B., Chen, D., Chen, H. H., Sun, G. Z., and Lee, Y. C. Learning and Extracting Finite State Automata with Second-Order Recurrent Neural Networks. Neural Computation, 4(3):393-405, May 1992. ISSN 0899-7667. doi: 10. 10.1162/neco.1992..4
Chizat, L., Oyallon, E., and Bach, F. On Lazy Training in Differentiable Programming, January 2020. URL pttt:///rxizn www.iiiiorra/aaeee 07956. arXiv:1812.07955 [cs, math].
3.393. URL https: / /t/////ee //eeeexpplpp ore. wwweeeee.ggg. document/ 67963444. Conference Name: Neural Computation.
Cohen-Karlik, E., Menuhin-Gruman, I., Giryes, R., Co- hen, N., and Globerson, A. Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Nets, March 2023. URL http: rxiv. org/ abs/ 2210. 14064. arXiv:2210. 14064 [es].
Goh, G., t. N. C., f. C. V., Carter, S., Petrov, M., Schubert, L., Radford, A., and Olah, C. Multimodal Neurons in Artificial Neural Networks. Distill, 6(3): e30, March 2021. ISSN 2476-0757. doi: 10.23915/ distill.00330. URL https: http:::ss///isiil..... http//isstill.... 20221 / multimodal -eurons.
Csáji, B. Approximation with Artificial Neural Networks. PhD thesis, June 2001.
Gunasekar, S., Lee, D., Soudry, D., and Srebro, N. Im- plicit Bias Gradient Descent on Linear Convolutional Networks. Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: / arwiv. .ww.vvorg//oooo wwt.sa/sssssee 88066880..0 00468.
Dai, X., Chalkidis, I., Darkner, S., and Elliott, D. Revisiting Transformer-basee Models for Long Document Classi- fication, October 2022. URL http: aaaaaaiiivv.oo org/ abss/204 06683, arXiv:2204.06683 [es] version: 2.
Hoffmann, D. T., Schrodi, S., Bratulić, J., Behrmann, N., Fischer, V., and Brox, T. Eureka-Moments in Trans- formers:
Multi-Step Tasks Reveal Softmax Induced Opti- mization Problems, June 2024. URL http: /tte://rxxxie /arxiv. org/abs/ 22100 12956. arXiv:2310.1299
2021. URL htttps:://ppereeee id=pVu7Gp7NNck.
Driscoll, L. N., Shenoy, K., and Sussillo, D. Flexible mul- titask computation in recurrent networks utilizes shared dynamical motifs. Nature Neuroscience, 27(7):1349
Hopcroft, J. An n log n algorithm for minimizing states in a finite automaton. Kohavi, and Paz, (eds.), Theory
Machines and Computations, pp. 189-196 Academic Press, January 1971. ISBN 978-0- 12--11750-77 doi:
1363, July 2024. ISSN 1546-1726.
doi: 10.1038/
-41593-024-01668-6 URL htLp::::
1111666997780-222447773555533023 URL https:
com/articlln 0etee/e//111131-011111111 0168866.
Pub-
/ w/wp://cceenncerrretcccoooo//ice
lisher: Nature Publishing Group.
El-Gaby, M., Harris, A. L., Whittington, J. C. R., Dorrell, W. Bhomick, A., Walton, M. E., Akam, T., and Behrens, E. J. cellular basis for
Horik, K., Stinchcombe, M., and White, H. Mul- tilayer feedforward networks are universal approxi- mators. Newral Networks, 2(5):39-3666 January
10

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
1989. ISSN 08936080. doi: 10.1016/0993-6080099) 90020-8. h sevier. htmp:/eeeteeeee1////339009990000
Merrill, W. and Tsilivis, N. Extracting Finite Automata from RNNs Using State Merging, April 2022. URL http://////.. arxiv. org/abs 2201 112.0...141.11 12451. arXiv:220112251 [cs].
Humayun, A. I., Balestriero, R., and Baraniuk, R. Deep Networks Always Grok and Here Why. In Proceedings of the 41st International Conference on Machine Learning, pp. 20722-20745. PMLR, July 2024. https: http://ptooeee....eeeee//o .mwr.mmrr.... ..ress/ v2.35 7.35//hmayun2244 html. ISSN: 2640-3498.
Michaud, E. J., Liao, I., Lad, V., Liu, Z., Mudide, A., Loughridge, C., Guo, Z. C.,, Kheirkhah, T. R., Vukelić, M., and Tegmark, M. Opening the Al black box: pro- gram synthesis via mechamistic interpretability, Febru- ary 2024. URL http:/ arxiv. org/ abs/2402. 05110. arXiv:2402.05110 [es].
Lake, and Baroni, M. Generalization with- out Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks. In Pro- ceedings of the 35th International Conference Ma- chine Learning, pp. 2873-2882. PMLR, July 2018.
Morcos, A. S. and Harvey, C. D. History-dependent vari- ability in population dynamics during evidence accu- mulation in cortex. Nature Neuroscience, 19(1)):1672 1681, December 2016. ISSN 1546-1726. 1038/nn.4403. URL https: / www. nature com/ articles nn 4403. Publisher: Nature Publishing Group.
doi: 10.
URL http:t httt:s://prrceeedngge mml..ng..........mmmmmm........m htt.:eeeedirr.......e.eeee/eeeee press/v80// lakel8a Ba html. ISSN: 2640-3498.
Laurent, T. and Brecht, v. A recurrent neural network without chaos, December 2016. URL http: /arxivv. htee/bb//15t 111.. 06212. arXiv:1612.06212 [es].
Nanda, N., Chan, L.,, Lieberum, T., Smith, J., and Stein- hardt, J. Progress measures for grokking via mechanistic interpretabilityy October 2023. URL http: : /arxiv. org bcg/abs//an abd//a/ss1111 05217. arXiv:2301 .05217 [cs].
Lin, B. and Kriegeskorte, N. The Topology and Geometry of Neural Representations, September 2023. URL http: /atxxvixvvvvv///////////////aav. wrggabs/23039 11028. arXiv:2309.11022 [cs, q-bio, stat].
Neyshabur, B., Tomioka, R., and Srebro, N. In Search of the Real Inductive Bias: On the Role Implicit Regu- larization in Deep Learning, April 2015. URL http: / arxiv.orgiioo......a abs 111//111.1..0 6614. arXiv:1412.6614 [cs, stat].
Lin, B., Mur, M., Kietzmann, T., and Kriegeskorte, N. Vi- sualizing Representational Dynamics with Multidimen- sional Scaling Alignment, July 2019. URL http:// arxiv. orgg aassss900 09264. arXiv:1906.09264 [es, q-bio, stat].
Olah, C.,, Cammarata, N., Schubert, L., Goh, G., Petrov, M., and Carter, S. Zoom In: An Introduction to Circuits, 2020. URL /ttt::::/disttii (idistilllpub//20...... pttpp//00//rrrrittttt.. circuits/ zoom- in/
Liu, Z., Kitouni, O., Nolte, N., Michaud, E. J., Tegmark, M., and Williams, M. Towards Understanding Grokking: An Effective Theory of Representation Learning. Oc- tober 2022. URL http::/tpt/......... / arxiv. www. wasg/bb/////ooo.ooeo/o///eeebebe abs/a2b5. 10343. arXiv:2205.103: 10343 [es].
Olshausen, B. A. and Field, D. J. What Is the Other 85 Per- cent V1 Doing? In van Hemmen, J. L. and Sejnowski, T. (eds.). 23 Problems Systems Neuroscience, pp. 0. Oxford University Press, January 2006. ISBN 978-0- 19-514822-4 doi: 10. 10.100334amm0000s/07778095444440
Loula, J., Baroni, M., and Lake, B. M. Rearranging the Familiar: Testing Compositional Generalization in Re- current Networks, July 2018. URL http:// //p::///ara /arxiv. org/abs//ln 1870 07545. arXiv:1807.0754. [cs].
003.0010. URL /ttttps:/dooiooog//111 1093/ 003.001
Maheswaranathan, N., Williams, A. H., Golub, M. D., Gan- guli, S., and Sussillo, D. Universality and individuality in neural dynamics across large populations of recurrent net- works, December 2019. URL http: /wtwivaxvvvv/vvv////v//.aaeaaaav wttpai.ovggg////////////../..o/r abs/1907. 08949 1907.08897088499 [cs, b-bi.].
Omlin, C. W. and Giles, C. L. Constructing deter- ministic finite-state automata in recurrent neural net- works. Journal of the ACM, 43(6):937-972, Novem- ber 1996. ISSN 0004-5411, 1557-735X. doi: 10.1145/ 235809.235811 ht / http/dlaaa.// wtt.ddl.....gg//mmm..... ocm.org//ol/ 10. 10.1145/235888 235811.
Marmor, O., Pollak, Y., Doron, C., Helmchen, F., and Gi- lad, A. History information emerges in the cortex dur- ing learning. eLife, 12:c83702, November 2023. ISSN URL https:
Power, A., Burda, Y., Edwards, H., Babuschkin, I., and Misra, V. Grokking: Generalization Be- yond Overfitting on Small Algorithmic Datasets, Jan- uary 2022. URL http: aariiv. org/ /bs//bbs/225 2201. 02177. 22t0:2220200227777 [es].
2050-084X. doi: 10.7554/eLife.837000 // //doi. //doi.oog/10. 7554 1554/e2200 /Lwife....e.ee 83702. Publisher: eLife Sciences Publications, Ltd.

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Richards, B. A., Lillicrap, T. P., Beaudoin, P. Bengio, Y., Bogacz, R., Christensen, A., Clopath, C., Costa, R. P., de Berker, A., Ganguli, S., Gillon, C. J., Hafner, D., Kepecs, A., Kriegeskorte, N., Latham, P., Lind- say, G. W. Miller, K. D., Naud, R., Pack, C. C., Poirazi, P., Roelfsema, P., Sacramento, J., Saxe, A., Scellier, B., Schapiro, A. C., Senn, W., Wayne, G., Yamins, D., Zenke, F.. Zylberberg, J., Therien, D., and Kording, K. P. A deep learning framework for neu- roscience. Nature Neuroscience, 22(11):1761-177) November 2019. ISSN 1546-1726 doi: 10.1038/ 941553-019-0520-2. URL https: / http///www......e/.//////at nature. com/artic sete///41111111---11 012-000-22 Number: 11 Publisher: Nature Publishing Group.
van Rossem, L. and Saxe, A. M. When Representations Align: Universality in Representation Learning Dynam- ics. In Proceedings of the s1 International Conference on Machine Learming, pp- 49098-491211 PMLR, July 2024.
ngs w...g.......rr....... press/ v235 v235/vary ht///vann-oosssse 4a. html. ISSN: 2640-3498.
Wang. K., Variengien, A., Commy, A., Shlegeris, B., and Steinhardt, J. Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small, Novem- ber 2022. URL http:// /tte:p//axxiii arxiv. wwtp/bsg////ooooo.../t...t...ttt 2211. 00593. arXiv:2211.005 [cs].
Weiss, G., Goldberg, Y., and Yahav, E. Extracting Au- tomata from Recurrent Neural Networks Using Queries and Counterexamples, February 2020. URL http:// arxiv www.avs.rgaa////ooee/oooo.oo 1711. 09576. arXiv:1711.09576 [es].
Schuessler, F., Mastrogiuseppe, F., Ostojie, S., and Barak, O. Aligned and oblique dynamics in recurrent neural networks, August 2024. URL http: arxiv.org/ abs/2307. 07654. arXiv:2307.07654 [q-bio].
Williams, A. H., Kunz, E., Kornblith, S., and Linderman, S. W. Generalized Shape Metrics on Neural Represen- tations, Jamuary 2022. URL http: / aarii.ivvvo.o.. org/ abs/ abs/21100 2ats/2110.44 14739.
Servan-Schreiber, D., Cleeremans, A., and Mcclelland, J. Encoding Sequential Structure in Simple Recurrent Net- works. pp. 40, July 1989.
arXiv:21 [cs, stat].
Zhong, Z., Liu, Z., Tegmark, M., and Andreas, J. The Clock and the Pizza: Two Stories Mechanistic Explanation Neural Networks, November 2023, URL http:// // a arxiv, wwxiv.org/aai........o wwt.oorg//b///oo/ 17844. arXiv:2306.1 17844 [cs].
Shwartz-Zivg Ziv, R. and Tishby, N. Opening the Black Box of Deep Neural Networks via Information, April 2017. URL http: arxiv. wwtpiv..org/bb//11/ 00810. 0. arXiv:1703.0081 [es].
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The Implicit Bias of Gradient Descent Sep- arable Data, July 2022. URL http: warxiv.vvvv////a///aaaaaaaaaavva org/ abs/ 10345. arXiv: 1710. 10345 [cs, stat].
Zhou, J., Jia, C., Montesinos-Cartagee M., Gardner, M. H., Zong, W., and Schoenbaum, G. Evolv- ing schema representations bles during learning. Nature, 590(7847):606--11
orbitofrontal ensem-
February 2021. ISSN 1476-4687.
doi: 10.1038/
Sussillo, D. and Barak, O. Opening the black box: low-dimensional dynamics in high-dimensional recur- rent neural networks. Neural Computation, 25(3):626- 649, March 2013. ISSN 1530-888X. NECO 00409.
541588-020-03061- URL https: http:/wwttturtttt// com com/articlest 4 08155860022 020-63061-2
Pub-
lisher: Nature Publishing Group.
doi: 10.1162/
Zhou, M., Liu, T., Li, Y., Lin, D., Zhou, E.,, and Zhao, T. To- ward Understanding the Importance of Noise in Training Neural Networks. In Proceedings of the 36th Interna- tional Conference on Machine Learming, pp. 7594-7602. PMLR, May 2019. URL https: http:::/pprcceeinng. m sr.r. A.r.press/vv1 zhou 9d.html..... ISSN: 2640- 3498.
Thompson, L. T. and Best, P. Place cells and silent cells in the hippocampus of freely-behaving rats. The Journal of Neuroscience: The Official Journal of the Society for Neuroscience, 9(7):3382 2390, July 1989 ISSN 0270- 6474. doi: 10. N0.1523/JEUROSCCO WLL553/NEERROSCC.0000000222000..
Tino, P., Horne, W., Giles, C.,, and Collingwood, P. Finite State Machines and Recurrent Neural Networks Au- tomata and Dynamical Systems Approaches. March 1999. ISSN 9780125264204 doi: 10. 0011016/9978--022554224444 50007-0.
Zhou, Y., Alon, U., Chen, X., Wang, X., Agarwal, R., and Zhou, D. Transformers Can Achieve Length Generaliza- tion But Not Robustly, February 2024. URL http:// www.v.org//aooooee........oooovr abs /20//222222222 09371. arXiv:2402.09371 [cs].
Turner, E., Dabholkar, K., and Barak, O. Charting and navigating the space of solutions for recurrent neural net- works, November 2021. URL http: / araii.vvv.. org/ abs 21ss.111.1 69356. 211x:2111.09356 (q-bio).
Ziyin, L., Chuang, I., Galanti, T., and Poggio, T. For- mation of Representations in Neural Networks, Febru- ary 2025. URL http: /ttt:://arivv. /axxiv.ivvv org/ abs/2410. 03006. arXiv:2410.03006 [cs].
12

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
A. Automaton Extraction
A.1. Definition Deterministic Finite Automaton
Formally a deterministic finite automaton (Ashby, 1956) is a tuple (Q, 2, 6, go. F), consisting of
1. A finite set of states Q
2. A finite set of possible input symbols Σ, called the alphahet
3. A transition function 5: x +
4. An initial state Qo
5. A subset of accepting states F
Given some string of input symbols x = (2) x(1) the automation is said to accept the string æ when there exists a
sequence states 7()) ,...,, (()) E Q such that
1. r())= =
2. (1r(+1) 8(r(1), 8(1((),x((111) x(1-1))
3. p(n) E F
In the context of the streaming parity task we can take the subset of accepting states to be precisely those for which the model predicts an output 1.
A.2. Extraction Algorithm
In order to extract one from recurrent neural network, we define the state corresponding to an input string x as the hidden representation in the network after received that string, i.e.
Q0 ho
(1I)
qu.....; (9
When two states are on top of each other, i.e. the representations are within some small distance c, we will consider them as the same state. Given evaluation dataset X of input sequences, the of states be defined as
Q = (g-l= X)/gax q = 11a--110 --1--- < c).
(12)
The alphabet E is the set of all possible input symbols in the data. The transition function 8(g, o)) is given by the state corresponding to fr(g. o). The set of accepting states F are all states for which fy(2) is closest to the output 1. If we are considering a task with more than two possible output symbols, we can generalize this definition using a Moore machine, which replaces the set of accepting states with an output function.
A.3. State Reduction Algorithm
To help interpret the final learning automaton within the recurrent neural network, we can reduce it to a minimal state automaton with equivalent outputs. For this we use Hopcroft's Algorithm (Hopcroft, 1971) (see Algorithm 1), which returns the unique smallest DFA, equivalent to the provided DFA. Essentially what this algorithm does is it merges all pairs of states which are indistinguishable for any possible input string.
13

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Algorithm 1 Hopcroft's is Algorithm
Input: set of states Q with output O, set of states with output
Output: minimal state partition P
P = QF F}
W = (F.Q)
while W is not empty do
choose and remove set A from W for e in do
let be the set of states for which a transition on leads to state in A for set in P for which X Y nonempty and Y X is nonempty do
replace in by the sets X n Y and Y \
if Y is in W then
replace Y in W by the same two sets else
|XNY & Y X|
then
add X n Yn to to
else
add X to W
end if
end if
end for
end for
end while
return P
B. Details Theoretical Analysis
B.1. Reduction to 3-dimensional System
To model the two-point interaction we consider two sequences xi ... x1
with nearby representations h h(= (.(.))).((m))) (ma))) respectively he h(=2)) ... x2 (mm))) Let D { vi.)), (I2, 15.) be the set of all
(m))
and x22
(m²) 22
datapoints contained within the training dataset which have xz(1) 21 2!
... (m²) subsequence. Assuming high expressivity, we model hy and ht2 freely optimizable vectors and the output predictions of the network for each subsequent sequence in D as given by smooth, freely optimizable maps H + Y.
(m²1) 2 (1)
In contrast to (van Rossem Saxe, 2024), we cannot use an optimizable linearized hidden map as here we cannot smoothly vary the inputs for the hidden map. Since our input symbols are discrete, we can instead consider arbitrarily optimizable hidden vectors, as no two differing input symbols can ever get arbitrarily close each other in the input space.
As h and h2 close, take linear approximation of each output prediction map around the representational mean:
v(aa.)) Ø: + _ Der (ha h .a)-
(13)
The mean squared loss in this approximation takes the form:
L = 2 (1u +
2 Du. (ha - h-a) vi.
(14)
14

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
We apply gradient decent optimization directly with respect Dyo la and ys, resulting in the dynamics:
d
1 aL
dt 1/
Tÿ. dy:
1
Ty. N (ie +
Dy. (ha - h-a) - va.a)=1.22
2
1
V2.i + Vi.5
(3h
Typ N
2
[ h(aa)
d
aL
di
The aha
1
(D.. (ūt +
2 Du. (ha (ha 11-0)= - Va,i)
DTT. (Ti + 2 Dv. (h-a ha) - y -'a..)) (15)
Tha
The (D (Do. (ha ha)) - (Va,t v)a,i)))==
d
1 OL
Dv:
dl
Tys yDy,
Ty. N 2 (1 Dy. (ha - 1ha - ha)) + (g) - Va,)ha - (aaa))aa>
1
1
Ty (De, (h2 -h1) (W2,5 vi,))) - h1)
where we used the matrix differentiation identities da Xb 2A (Ar + b).
ab
TTCe 8X
(C + CT) Xaa and
AA
8x
d2
The y dynamics are decoupled and can be solved directly:
V2.1 + VÎ.
32. +
)e Fo. X
(t)
(v:(0)
(16)
the solution of which takes the form of exponential decay towards each pairs target output mean.
Define dh h2 hi, dy; Dy. (h2 h1), w, ||dys 12 dyf (vě. vi.:). We take an Anzats representational movement of the two points towards away from each other, i.e.
d de
26 ch
dh
11 dh
dh x dh -
dh
dh
(17)
dhll
||
||hh||
Applying this twice allows us to write
D dh = |1
dt
||dh||
Dv, dh =
11 diill
||ch|12
|2h]|12
Dy, dh =
dh.
||dh|
11 dh)
|Mii
Dy, dh
dh dh
|/dh||2
dt
Dy, dh
=
2 ||hh||
1 d _|ldh 1|2
D dh
(18)
15

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
which we can use find self-contained scalar system:
|dil2 = 2dh' d dt
d
dt
1
dh' [ (
(D (Dg. dh (V2,, Vi,..))=
Th
2 (I|dysl 1|2 - dyp (12,i vi,)))==......
2 (20²) i.....N
d di
dys dyill 2dy, al
dh T dh
=2dy, (Dys dh +
||dhil2 Dy, dh)
2t
1 at. lcbb|12
(19)
=2y, (D,, dh +
2 |[dhi]2 yh,
=2dy, (- 1 1
1 (wii)=l,..., dys)
(dy; (y5, vi,)) vi.h))/hhl
Ty. N 4
4 Th
||dh||
1
||dy;|1 11 ||ch 1
dy: dy, (v5. - V d1,)l/
(w:))=1,....
Tys N 2
2 Th
dt w/ = (2dy; - (V²,: - vi,))) d
d
dys
dt
1
(w;)==1.... dy:)
(2dy; - (V2,s - vi,)))( (-
(dys (U5,; - -i,h)/hhh
Ty. N 4
4 Th
||dh|
N 4 (3w; ||dy;l| 12 + 11v2, yi, (3)] (wi)i=l.....
(l|dyil12 + wx)
||dh|
Tys
where 1
The
Th2
In the case that the output effective learning rates all equal, i.c. V.Ty, Ty. this system can be reduced to a 3-dimensional scalar system:
d
1 (wi)
di |dhl12
Th
di (1ldw:l)))
(
1
|dbl|12 + Th. ||ch||2
1 (1ld)//13)
(wx))
(20)
1
11 (wx) 4 Th [ahli
dt (wi)
4 Nr, (3(w))) - (11dyi 12)² + (lbb. -v..1
((lldyel))) + (wx))).
B.2. Final Representational Structure
In order to study the final representational structure learned by the network, we solve the final representational distance for the pair. Using the relationship
d (1 dy. 1P)
|dil2 de []dyyil)) <lldy: 12);; d |dh]|2
2N (w,)) = To
||dhl12
(21)
di |
||
Nr,
we can solve (1) as a function of (1))
16

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
(I]d);(0))1)) [0)l
(Ildy/1P)((t)
Th
(t) +
Th
[Idh(0)))))) |]dh||(tt. (tt),
(22)
NT
NTy
reducing the dynamics to 2-dimensional system:
d
1 1
|dhll2
(we)s
2 Th
d
1
1
4 [(dhl)
+ 1 {wi)
di (wa)s
-
ddill +
l122 vill 1 |d1l/ +
(23)
N2
NTy
Nry
7h |dhi|p?
Th
[aab(011))
( (mee)s
1
1
|dbh|())-
[d)(1)
NTy
Th
NTg
This system has three fixed points
|dhh||
Anigh
Ahigh + A (2r))s 0
(24)
||d]]|2
Anigh
Anigh
Alimar (wi)s O'
|dhh||2 = O, (wi) 0
where
Anigh = |Ich(0)]12 NTy (0)1)) |[ch(0)]2²
(25)
NNy. (1lu,, v2,,112)..
Alow
The first fixed point has negative representational distance and thus valid solution. The second fixed point has Jacobian
J =
(26)
NZ7g (2A2 + (Anigh + V Aligh + 4.42
( (2 Anigh + VAugh + 4.2
with negative trace
Tr(J) NTw Anigh + / //high + 4A
(27)
and positive determinant
1 det(J) N2 (2A + (Anigh + Aliggh + 4.A )2),
(28)
and is therefore always stable.
The final fixed point has Jacobian
0
( 1 (m d
1 vl.)
11 Auigh
Anihh
1
(wr [ahl
(29)
Nr,
which cannot be directly evaluated at (w,), 0, ||ah||2 0 because of the undetermined tenm with the direction of approach h we can solve for eigenvectors
(wis [ah
By replacing
(wi)s
1
6 8 Th. a2 NF,
1 E1vv vi,11%))
(1
Anggh
Th 1
b))
>
(30)
NTy
Th.
17

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
find
1 Ang + / A 1m
(31)
Nrv
2
with one positive and one negative eigenvalue
Anigh +
V Aligh + 4.A
(32)
NTy
2
There is always direction along which perturbations increase, so this fixed point is not stable.
Only the second fixed point is valid and stable, hence we expect the final representational distance to reach it.
B.3. Agreeing Pair Dynamics
When the pair agrees on all possible future outputs, i.e. Vi vē., vi, we have that (we)): <I1dy; allowing to reduce the system Equation (20) to
d
1 <I|dy:ll?):
di ||dhl|?
2 Th
(33)
d (Ildy:113)s
1 - (1lddss1 (
1
<[]dyill?);
||hb112 +
dt
Nr
Th ||dh||
Using Equation (22) we can write self-contained equation for [[dh]
d di
1
1
dhl]
||db||* 4 +
Anigh |ch
(34)
NN Try
2 NT
which is Bernoulli and has solution
Anigh
[d)(1)]2=
(35)
Augh [F
1)e Niy Auga!
which, as Anigh < [|dh(0)]l2 exponentially decays towards the final representational distance [|dh(co)][² = Anigh-
B.4. Fixed Expansion Point Interaction Model
We take the same approach before but instead keep the linear expansion point fixed during training:
y(I.,) = b; + Dy, ha-
(36)
The mean squared loss in this approximation has the form:
L 2 (1bb, + ha - va.
(37)
Motivated by the assumption of high model expressivity, we apply gradient decent optimization directly with respect to Dy,
18

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
ha and b,, resulting in the dynamics:
d
al
b
dt
Tbe ab;
Tb. (b, + Dy, ha Va,ia==1,2
(b; + Du. (hala - (Wa,)a)
T5. N
d dt
1 Ø0.
ha
The tha
(38)
1 1
The 2 (D (b, Dy,ha - Va.i.i
ØL
Doa
dt
Tys
aDy,
(Dy ha + (b; Va Va.ilaaa-
N
Tys
1 (D,, (hal be bb (a
We again try the Ansatz where the representations only move towards or away from each other, which, since we take the expansion point to be the representational mean at = 0, can be written by shifting coordinates without loss of generality as
ha haV,
(39)
for some vector with |/|| 1. We define d; = v vT Do, v, b, v TDD b; allowing write using the derivatives
lma
((D,, v) (b; + hi Dy. va,))s
dt
The 2
1
1
(b: (ha)a Dy, (a)))a)
(40)
dt
To, N
d
1 1
D
v
( + (ha)abi (hataadaa)
dt
Ty.
N
a scalar system which takes the form
d
1 1
dt hr
(b. D hallDy.ul1 212 DD.
The
2
b,
Dg.
(b: Dy, + (ha)all Dy, r/12 W. (v. N (12)aab, Dy. v + (ha)allb.ll (hab, Va.)))
dt
N
d
D. 1/.1
(b, U3.5 + (ha)) Do. - yT (V
dt
Top
d
1 1
|bb1122
-2
(11b,112 + bb Dy, 18,7 varila)
dt
Tb. N
d dt
u112 = -2
(l
v112 (, Dy. v - (haVo. Daa Dy Dy) a)
Ty. N
J. 3,4 Dy.
TT
1
8. Dyy v+ + (ha)ay -T b,bb (has Da) ((1))
Typ N
(41)
19

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
If the output effective learning rates are again all equal, i.e. V Tb Tb. V Tye Tyx this system be reduced to scalars:
d
1
hi
(1) Dy, o)s + ho 2 2113)= - Wa,DDay b),
di
Th.
d
1
(b) Uy,
(bb) Py (ha) (1l 1/ 11)); Wa, Dy U)
Tb N
1 1
(12)) (b: Dyce)s + (Ma)a (110:11)) - (ne (br (as)s)a)
Ty N 1
d
1b) 13.1)
(1b) 1b (Mada Wp pe u) (D..aa
(42)
dt
7b N
- 1
dt (1]b:11))
((11;112)s + (ha)a Du u)2 - (DT vas)as)
N
d
1
di (1) ul12)/
2 ((ha) (
(ba)a (b, Dy. (ho (Va. Dy, o)))a)
Ty N
dt (. D.. u)
Ty N (th (v' 8, Dy u) + (ha)aly" T b, (haly" B.Naa.)saa)
1
Training loss
The loss can be written expressed using the variables from this system
L -= (116,11++ (h2) ,, d + (I1b,,11 2(ha) (6, Dy,u); u); 2(h Du u)d) - -2( 2, a,)i)))))) (43)
Equal hidden effective learning rates
When the pairs agree on all outputs,s we have
W T a), (v" da.
(44)
Assuming no correlation at initialization due to random weights
(b. Dy, (0) 0
(b. (0)
(45)
w B, v).(
we find the relations
dt (b vī
(b, v2.1)
dt
(46)
di w I Dy, o)
(v 2. D v)
di
such that
(67 vo. (b, v2,);
(47)
( Ty 0) (v I. Dy, v)
From this it follows that
d
(T2h2 -1/1)= = मi
- (122 (1)2--11)(1100 (1) 1)))))-
(48)
In the case of equal effective hidden learning rates The Thu the representational distance can only increase
_ 1// h 1| (11
d
(49)
di
so no initial divergence occurs for agreeing pairs in this case.
20

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
C. Experimental Details
For all experiments, the PyTorch library was used to train the models. The code we used can be found at https: / //gitttin giihhu.... com/loekvanrossem, /nn ren_snns_tuuurt structure. git.
C.1. Streaming Parity Task
Model The neural network architecture consists of a single fully connected recurrent layer with 100 hidden units, ReLU activation function, along with fully connected linear output layer, both with bias:
he ReLU + bin + h4- Whth + bux)
(50)
Y/ W hg h4 bby
The initial hidden vector hg was all ones, to reduce time being stuck at the zero fixed point early in training.
Training procedure The model trained all sequences up length 10. We used 100 randomly selected sequences of length 50 to compute the validation loss during training. Both the inputs and outputs were embedded in 2-dimensional space using a one-hot encoding.
Optimization was performed using stochastic gradient descent on the mean squared training loss. The model was trained over 1000 epochs a learning rate 0.02 and a batch size of 128. No momentum or regularization was used. Weights were initialized small using Xavier initialization a gain of 0.1. Bias was initialized zero.
Automata Automata were extracted using the complete training set. The merger cutoff was set factor of 0.01 of the representational standard deviation.
C.2. Grokking
For the re-implementation of the grokking experiment, made use of the following publicly available repository: https:
git
The data used is subtraction modulo 96, with a fraction of 0.6 of possible examples set aside for validation.
Every 250 epochs we evaluated the training loss, validation loss, number of states in the attention, and number of states in hidden layer.
To compute the number of states in the hidden activations, we considered the activations after the normalization layer, as suggested in (Adriaensen & Maene, 2024). Next, applied principal component analysis reduce the space 512 dimensions and merged pairs with distance below threshold to count the number of states. The number of states in the attention matrix was computed in a similar manner.
The threshold was chosen to be 1.25 times the initial maximum distance, as states are expected to be close at initialization. Any significantly larger or smaller choice for the threshold resulted in the counting of a single or all possible states at every epoch.
D. Supplemental Figures
D.1. No Representational Contraction
One may wonder if the reduction in the number of automaton states during the second phase of learning is merely the result of the whole representational space contracting, as the merger threshold is fixed constant. To make sure this is not the case, we computed the representational mean distance over time and found it always increases (Figure 12).
D.2. Validity Linear Approximation
The theoretical interaction model assumes close enough representations such that the first order term in the Taylor expansion dominates higher order terms. One may wonder whether or not representations practice are ever close enough for this to be a reasonable assumption, especially since even pairs that end up merging still initially move apart from each other as can be seen in Figure 10. To test this we compute the average ratio of the norm of the second-order Taylor term with respect to
21

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
1.25
Mean distance
1.00
0.75
0.50
0.25
0.00
0
250
500
750
1000
Epochs
Figure 12. The mean pairwise representational distance of training set during training on the streaming parity task. It never decreases during training, hence state mergers cannot entirely explained by representational contraction.
the first-order term (Figure 13). We find that although the linear approximation does get worse when representations start to move apart, the first-order term still remains dominant, and in the case of merging pairs by at least factor of 10.
Ratio second to first order term
1.00
Mean converging pairs
Mean diverging pairs
0.75
0.50
0.25
0.00
250
500
750
1000
Epochs
Figure 13. The norms of the fecond-order term divided by the first-order term in the Taylor expansion of the output map during training. averaged all pairs that ended up below the merging threshold and all pairs that ended up above the merging threshold out of 100 randomly selected pairs. Note that this ratio increases around the point where pairs start to diverge, however, the first order term remains dominant average throughout the entire training procedure.
D.3. Diverging Mergers Occurrence Rates
As gradient descent scales with the number of parameters, the effective learning rates of representations should be proportional to the sequence lengths.
1
α The
(51)
This is because for hidden state corresponding sequence of length n, the map assigning that hidden state consists of the recurrent map applied times. Therefore, this map has nP parameters, where P is the number of parameters on the recurrent map, and parameters that appear multiple times are double counted. Applying gradient descent will thus result in sum of n terms, and this increases linearly with n.
From Equation (51) we would expect such mergers that initially diverge to be more prevalent among pairs with a large difference sequence lengths. Such a pattern was indeed observed in the experiment (Figure 14).
22

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
0.8
Sequence length
3
0.6
0.4
7-
8
0.2
10
0.0
9
Sequence length
Figure Fraction of mergers that first move apart by least factor 10 of the merging threshold, some point during training, before merging in the end. Displayed a function of the sequence lengths of the points in cach pair. We can see that pairs with larger difference sequence length appear diverge initially more oflen during merging.
D.4. State Change Patterns Due to Diverging Merger
According to the theory, the reason the number of states initially increases before decreasing is that pairs of datapoints agreeing on outputs will first move apart before they end up merging, As we can see Figure 15, the decrease of the number of states after the initial increase can indeed be entirely explained by merging pairs that initially diverged.
Experiment
1.00
0.75
Loss
0.50
Training loss
0.25
Total number splits
Number of agreeing splits
0.00
Number disagreeing splits
250
500
750
1000
Epochs
Figure 15. The number of pairs of datapoints whose representational distance apart than the merging threshold during training on the streaming parity task, divided by whether or not they agree on all possible future outputs. We see that the drop in number of automaton states be explained by pairs agreeing all outputs initially diverging before they end up merging.
D.5. Random Regular Tasks
We ran multiple experiments on randomly generated regular tasks with number of states between 1 and Tasks were defined using random automata, which were generated by starting with initial state and adding transitions for each input symbol to either new state with some probability which we set to 0.75, or a uniformly selected already existing state. This procedure was iterated for each state until all transitions were assigned, or states exist at which point all remaining transitions would be assigned to already existing states. Results were found to be consistently qualitatively similar to the streaming parity task. Initial weight gain was set to 0.025, the learning rate to 0.05, An example is shown in Figure 16. Other samples of regular tasks provided qualitatively similar results.
D.6. Hyperbolic Tangent Activation Function
We reran the experiments on the same recurrent neural network architecture except with hyperbolic tangent non- linearitt. Initial weight gain was set to 0.01 and learning rate 0.05. All other settings remained the same. Similar qualitative results
23

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
found as with the ReLU network (Figure 17).
D.7. Modular Addition
The single-layer transformer trained on modular subtraction has a much smoother transition to generalization than the RNN trained on parity. Modular addition tends to have sharper transition. To see if this changes any of the results the experiment again. We still find similar merging patterns (Figure 18).
D.8. State Merging in the Value Matrix
Although less clear, we found something resembling a state merging effect in the value matrix of the transformer (Figure 19). The key matrix did not show such effect.
D.9. Discontinuity
We can break the assumption of continuity by adding step discontinuity in the output map of the RNN.
i < 0 x x+1 i > 0
f(x)
(52)
We still find similar results albeit with nosier dynamics (Figure 20).
24

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Number of automaton states during training
Learned automaton
0.30
Training loes
0.25
Validation loes
0.20
Number
Loss
0.15
0.10
0.05
250
500
750
1000
Epochs
Initial
Stase with outgoing shown
Long sequence validation loss
with outgoing edges
0.50
Train
Task automaton
Learned automaton reduced
25
100
Loss
250
0.25
1000
2500
10000
intal
intell
0.00
500
1000
Epochs
01
Number of states
Validation accuracy
Fraction of agreeing pairs that merge
Initial weight scale
2000
Initial weight scale
0.2
0.2
1500
0.9
Sequence length
0.10
0.4
3
0.8
0.6
1000
0.6
4
0.8
0.8
0.7
6-
0.06
500
0.6
7
1.0
8
9
6.02
Training data fraction
Training data fraction
10
8
9
Sequence length
Representational distances
Fraction of mergers that diverges
Sequence length
0.9
Loss
0.5
5-
0.8
Training loss
Distance agreeing pair
Distance disagreeing pair
0.0
250
500
750
Epochs
Sequence length
Figure 16. Experimental results of a recurrent neural network trained randomly generated regular task. Note that the task automaton and learned automaton are equal, but states are displayed in different locations.
25

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Number of automaton states during training
Learned automaton
Training
0.75
Validation
Number
0.50
Loss
0.25
inital
0.00
250
500
750
1000
Epochs
Initial state
Long sequence validation loss
State with outgoing edges shown
0.50
25
State with unshown outgoing
100
Loss
250
0.25
1000
Learned automaton reduced
2500
10000
0.00
500
1000
Epochs
Fraction of agreeing pairs that merge
Number of states
Validation accuracy
Initial weight scale
0.1
Initial weight scale
0.14
1.0
Sequence length
0.04
0.2
1500
0.03
0.3
1000
0.3
0.6
0.02
0.4
0.4
7
0.5
0.5
0.4
9-
0.01
10
0.00
Training data fraction
Training data fraction
00
Sequence length
Representational distances
Fraction mergers that diverges
10
1.0
0.9
Sequence length
44
Loss
5
088
64
Training loss
0.7
7
Distance agrecing pair
8-
Distance disagreeing pair
0.0
9-
0.6
475
500
525
550
10
Epochs
0.5
6
9
0
Sequence length
Figure 17. Experimental results of recurrent neural network with hyperbolic tangent non-lincarity trained on the streaming parity task.
26

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Training loss
Validation loss
Number of states (attention)
Number of states (hidden)
4
Loss
2+
2500
5000
7500
10000
12500
Epochs
Figure The training loss, validation loss, number of states in the attention matrix, and number of states in the hidden layer of single layer transformer trained on modular addition. Note that as with subtraction we see pattern of initial attention pattern divergence followed by mergers, while hidden states continue increase.
Training loss
15
Validation loss
Number of states (keys)
Number of states (values)
10
Loss
5
0
25000
50000
75000
Epochs
Figure 19. The training loss, validation loss, number of states in the key matrix, and number of states in the value matrix of a single layer transformer trained modular subtraction. Note that some amount of state merging appears to happen in the value matrix, but not for the key matrix. Losses have been scaled down for visualization purposes.
27

---

Algorithm Development in Neural Networks: Insights from the Streaming Parity Task
Number of automaton states during training
Learned automaton
0.30
Training
0.25
Validation
0.20
Number
Loss
0.15
0.10
Intal
0.05
0.00
500
1000
1500
0
Epochs
Initial state
Long sequence validation loss
State with outgoing edges shown
0.50
25
State with unshown outgoing
100
Loss
250
0.25
1000
Learned automaton reduced
2500
10000
0.00
500
1000
Epochs
Fraction of agreeing pairs that merge
Number of states
Validation accuracy
Initial weight scale
2000
1.0
2
0.10
0.2
0.2
Sequence length
0.4
1500
0.4
4-
0.08
5
1000
0.06
0.6
6-
0.8
0.8
74
0.4
8
1.0
1.0
9
2.
10
0.00
Training data fraction
Training data fraction
9
Sequence length
Representational distances
Fraction mergers that diverges
1.0
1.0
2
Sequence length
4
Loss
64
Training loss
0.6
Distance agrecing pair
8-
Distance disagreeing pair
0.0
0.4
500
1000
1500
10
Epochs
2
9
Sequence length
Figure 20. Experimental results of a recurrent neural network with a discontinuity the output map trained on the streaming parity task.
28


Reviews:
[{"review_id": "ORlRz9vIuY", "reviewer": "Reviewer_5QF7", "summary": "This paper studies the learning dynamics in RNNs trained on a toy-task to understand what conditions influence generalization in RNNs. The authors first study RNNs trained on the streaming parity task, and group together RNN hidden states to construct Discrete Finite Automaton (DFA) proxy-models of the RNN. They study how the number of states in the constructed DFAs evolve during training and find that training starts with few states, then over-fitting each data-point with a tree of states. Finally, states merge until the DFA truly becomes finite, at which point generalization occurs. The authors attempt to explain the decrease, leading to generalization, by suggesting that for continuous models the continuity of the model will lead to nearby states merging because continuity will result in the same solution being found. The authors attempt to explain the increase of states, earlier in training, by suggesting that differing effective learning rates lead to states drifting apart. These explanations are justified by analyzing two simplified mathematical models for sequence learning via gradient descent. By way of experiments and simplified model analysis, the authors connect the generalization phenomenon with parameter initialization strength and dataset size.\n\n## Update After Rebuttal\nThank you to the authors for the many clarifications! I am mostly satisfied by their responses and have thus increased my score to a 4. I have chosen not to give the paper a 5 on account of the disconnect between the studied toy model (continuous functions of sequences) and the system of interest (RNNs), and some minor clarity issues (e.g. greater intuition for equations 3, 7).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and spending your time reviewing our paper. Please find below responses to your comments and the changes we will make to the paper.\n\n***Weaknesses***\n- We are unsure if this is related to the question about equation (16), but for clarity we would like to note that in equation (16) we mean to assume that $\\frac{d}{dt}dh$ and $dh$ are proportional during training only as vectors. They still differ by a time-dependent proportionality coefficient. Complex behavior can happen within this coefficient and $dh$ does not have linear dynamics. We can see this as some of the results, such as a transition between a rich and lazy regime in equation (4) are not present for linear dynamics. We will change the text to make this point clearer.\\\nWe will also add a mention of this assumption in the main body. In our view, however, it is does not change the bigger picture. We are only restricting to a set of solutions that we can easily solve, which are still valid solutions to the system in equation (14). Solutions that move towards or away from each other, are, due to the importance of mergers in this paper, precisely the ones we would like to study. Additional solutions may exist, where representations spin around each other, but this is less relevant to the formation of finite automata.\n- There are a few steps between line 6 and 7 and the appendix will be changed to explain these in more detail. We use the Ansatz $\\frac{\\mathrm{d}}{\\mathrm{d}t} dh \\propto dh \\implies \\frac{\\frac{d}{dt}dh}{||\\frac{d}{dt}dh||}=\\frac{dh}{||dh||}\\implies \\frac{d}{dt}dh=\\frac{||\\frac{d}{dt}dh||}{||dh||}dh$. This allows us to rewrite the second term in line 6 from equation (17): $D_{y_i}\\frac{d}{dt}dh=\\frac{||\\frac{d}{dt}dh||}{||dh||}D_{y_i}dh=\\frac{\\frac{||\\frac{d}{dt}dh||}{||dh||}||dh||^2}{||dh||^2}D_{y_i}dh=\\frac{dh^\\top (\\frac{||\\frac{d}{dt}dh||}{||dh||}dh)}{||dh||^2}D_{y_i}dh=\\frac{dh^\\top\\frac{d}{dt}dh}{||dh||^2}D_{y_i}dh$, where we used the previous relation twice.\n\n***Questions For Authors***\n1. One can write exact equations of the pair's dynamics by replacing the effective learning rates with time-varying tangent kernels. These depend on the parameterization and thus the architecture. The rest of the equation's structure still is the same. By replacing the kernels with constants, the architecture-independent part of the dynamics could be examined on its own. In a more detailed model we would still see this part of the equation and therefore expect similar merging results, but the kernels may add highly complex behavior.\n2. The representational distance in the plots 10, 15, 16 are normalized in order to compare the patterns, as distances for the merging pair are much smaller than the diverging pair. The merging pair was reduced by about a factor 100. This is not clear from the figure's description and we will change this.\\\nWe believe the observation that additional freedom in the model can result in initial divergence patterns is interesting on its own, as it offers an explanation to the tree fitting phase. However, the paper could do better discussing the accuracy of the approximation in the experiment. Even though the representational distance is small this does not guarantee the approximation holds. We ran the experiment and tracked the values of the first and second order term in the Taylor expansion for 100 randomly selected pairs of hidden states. We found that on average for pairs that merge the first order term always dominates by at least a factor of 10. We will add this to the paper.\\\nFrom what we have seen all merging pairs move apart before merging with a similar pattern.\n3. For the state merger intuitions to hold, nearby hidden states moving closer must result in their respective predictions also moving closer. Continuity provides this, but a weaker condition may be enough. If, for instance, the model is discontinuous but still on average predictions move closer when their hidden states do, the intuitions still make sense. In a neuroscience context this may be an interesting point to mention, so we will add a discussion in the paper. When adding a discontinuous jump in the output map we find a similar automaton development pattern, albeit with noisier dynamics.\n4. The scale $G$ increases with the initial weight scale, but the rate at which it does will depend on the architectural details. Since a hyperbolic tangent non-linearity saturates and a ReLU does not, how $G$ and thus the occurrence of mergers depends as a function on the initial weight scale may be qualitatively different. In particular for a tanh model near the saturating regime one may expect less dependence on $G$ compared to $N$ which is not affected by architectural choices.\n5. As mentioned in question 3, discontinuity is still okay as long as on average there is a local relationship between the representations and their predicted outputs. In the case of spiking networks the intuitions may still apply to the firing rates.", "claims_and_evidence": "The claims seem reasonable, except the reviewer would like to see greater discussion of the assertion that continuity is the key property that enables mergers. The reviewer wonders if it might be some other regularity or smoothness property that is crucial (see Question 2 of “Questions for Authors” section).", "methods_and_evaluation_criteria": "Evaluation seems sound, but the reviewer did not review the full supplementary section.", "theoretical_claims": "I am concerned about the assumption made in Equation 16 and a potential error in Equation 17 (see bullet points 2 and 3 in “Other Strengths and Weaknesses” section).", "experimental_designs_or_analyses": "Experimental design and analysis appear sound", "relation_to_broader_scientific_literature": "The reviewer is less familiar with the Discrete Finite Automata (DFA) literature so is ill positioned to discuss this. Conversely, the reviewer is familiar with literature on analysing learning in RNNs. To the reviewer's understanding, much of the recent work on how RNNs learn has focused on computational analysis of internal dynamics (Ostrow et al., 2024, NeurIPS), analysis of linear RNNs (Zucchett & Orvieto, NeurIPS, 2024; Li et al. JMLR, 2022), or analysis of very simple, non-optimal, learning rules (Clark & Abbott, Phys Rev X, 2024). From the reviewer’s point of view, this work is novel because it uses DFA coarse-graining to study the RNN representations algorithmically (although, again, the reviewer is less familiar with DFA literature so such analysis may have appeared there), and because the analytical results deal with a hyper-simplified model–casting aside RNN architecture altogether–and seem to provide some insights that still apply to learning in RNNs.", "essential_references_not_discussed": "The reviewer cannot immediately think of any missed references.", "other_strengths_and_weaknesses": "## Strengths\nThe paper is nicely written and the approach of coarse-graining with DFAs is very cool and provides great insight into RNN learning dynamics on the streaming parity task. The authors did a great job with study design, to have selected a mathematical model that is so highly simplified but still appears to yield relevant insight. Lastly, the plots are visually appealing and insightful.\n\n## Weaknesses\nThe reviewer is primarily worried about some of the mathematical assumptions made in the paper (first two bullets below), and also about a potential mistake in Equation 17 (last bullet below):\n- The reviewer is concerned about the closeness of hidden states assumptions (see Q1 of “Questions for Authors” section).\n- In equation (16) the authors make the assumption that the difference in hidden state representations follows simple linear dynamics (specifically, that the time derivative is proportional to the state value). Given the coupling with the $D_{y_i}$ variable derived in equation (14), this appears to be a not-insignificant approximation. As such, it would be nice to see some justification for this, along with a mention of this in the main body of the manuscript.\n- The reviewer was unable to get from line 6 to line 7 in equation (17). It seems that the above linear assumption is being used here but, unless the reviewer is missing something, there appears to be an error where the second term in equation 7 is different from what it should be by a constant factor.\n\nOn the whole the reviewer likes the paper, but cannot recommend it for acceptance until their concerns are addressed. If these and the below comments + questions are satisfactorily addressed the reviewer would likely increase their score.", "other_comments_or_suggestions": "- It would be nice if the authors could discuss their choice of gradient flow as learning dynamics versus something closer to stochastic gradient descent–perhaps a discussion of pros and cons of this choice.\n- Many of the figures, in the main body and the supplementary section, are missing a Y-axis label. Please add!\n- Line 138 LHS: “them same” => “them the same”\n- Line 119 RHS: “As an example for illustration, suppose that two sequences in the dataset agree on target outputs, and one already has the correct predicted output.” The reviewer found this a little confusing. How is it that they can agree on targets but not predicted output? Is the target not what is being predicted? Perhaps this is a problem with the reviewer’s comprehension but some clarity here could be useful.\n- It would be really helpful to have some intuitive description, if possible, of the dynamics in Equation 3.\n- Some insight into the derivation of Equation 7 would be great.\n- Line 305 LHS: “that the first pairs to merge are the ones for which $n - m$ is minimal.” Isn’t Equation 8 a statement about the system at a fixed point? If this is true, why would it explain which pairs merge earlier or later?\n- Line 350 RHS: could be good to give a quick definition of what “Regular Random” means.\n- Line 436: suggest: “mathematical structures” => mathematical objects\n- Line 671: a definition of “accepting state” could be good\n- Line 693: reference for Hopcroft’s algo is missing\n- Equation 14 lines 8-9: it seems the $2$ in the denominator should be a $4$.\n- Notation in section B.1: it could be nice to use something to distinguish the target $y$ values from the predicted ones.\n- Line 814: not sure there is supposed to be a 2 in the denominator for $\\frac{1}{\\tau_h}$\n- Could be nice to elaborate on how Equation 19 was derived\n- Equation 25 and 26: might suggest different notation for determinant and trace, given similarity with previously used symbols.", "questions_for_authors": "1. Do the authors have insight about how the learning dynamics in a more detailed model would be different from their parameterizing the output maps directly with the parameters of the Taylor expansion?\n2. Much of the theory rests on the assumption that the RNN states observed in practice are close enough together for the Taylor expansion of Equation 2 to hold. In Fig.10 (Right), and similarly in Figs 15, 16, it seems that–before merging–the merging states actually get rather far apart from each other (looking at the blue trace). Does this not invalidate the closeness assumption? Relatedly, do all states usually get far apart like this before merging, or do some stay close together during the training dynamics?\n3. The studied toy dynamical system model seems to provide an argument for the sufficiency of continuity, but perhaps not for the necessity of continuity for this phenomenon. Can the authors think of ways that they could test a discontinuous map (or at least an approximation of such), to determine the necessity of continuity? The reviewer wonders if it might be some form of regularity, rather than the continuity per se, that is the important quality here.\n4. In supplementary figure 16 it doesn’t seem like the initial weight scale has much of an effect on “Number of States” or “Merging” with a Tanh, in comparison to the ReLUs used in the paper. How do the authors explain this?\n5. Part of the authors’ motivation for the work is from a neuroscience perspective. However, the spike coupling between neurons is often viewed as discontinuous. Do the authors believe that the intuition provided in this paper would not apply to spiking networks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L90tUxzhto", "reviewer": "Reviewer_kzvD", "summary": "This paper explores how neural nets learn automata through training, focusing on a parity task in RNNs, with a short foray into a modular arithmetic task in transformers at the end. They are able to (in a very satisfying way!) theoretically derive equations governing the merging of states in the RNN under some assumptions, which provides a number of useful intuitions for when and why such merging occurs, which explains their experimental results. This analysis shows that the learning occurs in phases, with an initial phase where many states effectively \"memorize\" distinct sequences of training data. This is followed by a second phase where states which constrain all future outputs similarly merge, corresponding the network internally instantiating a finite-state machine (though non minimal) that generalizes to infinite-length sequences. I feel compelled to also say that aside from the actual content - which I found interesting and thought provoking - this paper is extremely well-written and was a pleasure to read!", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and spending your time reviewing our paper. Please find below responses to your comments and the changes we will make to the paper.\n\n***Questions For Authors***\n\n- The intuitions and theoretical model surrounding state mergers are independent of the task and not affected by averages, so these we would expect to see these in general. For a probabilistic regular task we expect everything to still work via a very similar argument as in the deterministic case. However, for a non-regular task a different mathematical object is needed to represent the learned internal structure of the network, and how representational mergers can result in the development of one is unclear. E.g. it is not possible for representational mergers alone to explain parenthesis balancing, as after all the possible mergers have occurred the automaton is still not finite and so there is no reason to expect generalization to longer sequences. We do wonder if perhaps other types of merging occur due to similar continuity arguments, perhaps in the patterns of maps within architectures more advanced than the RNN explored here. This is why we found the merging of attention patterns in transformers interesting, as it may be related to the development of some kind of mathematical object more advanced than a DFA, but this would require significant further study.\n\n- Note that Nanda et al. used weight decay, which we avoided to focus on induced bias in gradient descent. When we run the experiment on modular addition data without weight decay the transition is not as sharp as in Nanda et al., although it is still sharper than the subtraction task. We find qualitatively similar results as for subtraction, where the number of hidden states ends up increasing overall, and the number of attention patterns first increases and then decreases. We will add this plot to the paper. When using weight decay we get a sharper transition and find significant merging in both the attention patterns and hidden states, although studying regularization is beyond the scope of this work.", "claims_and_evidence": "The main claims are that \n\n- State merging is what underlies generalization, which they show by interpreting/analyzing the internal states of the RNN and their transitions upon seeing another token of input as an automata. Through training they observe that particular distinct sequences of inputs increasingly cause internal RNN states that are close to eachother (ie. the states merge), and ultimately the number of visited internal states becomes finite, corresponding to infinite-lengthscale generalization. This is a convincing example of their claim, though it is of course a single relatively simple example. To be more specific about this limitation, the tasks explored in this work were all regular, and it's not obvious to me what would happen in the case of e.g. parenthesis balancing or Dyck-languages or other irregular things. Similarly, what occurs in the more general case of probabalistic automata? Still, it's very illustrative and coupled with the local interaction theory is convincing. \n\n- A local interaction theory explains why and when states merge over training. The setup of the theory explores how the distance between  two hidden states associated with two distinct sequences of input changes over gradient descent. The theory shows a number of deep intutions - that states merge when they are associated with the same constraints over all future outputs, that states associated with short inputs won't merge, and that there's a dependence on initialization - all of which is born out in experiment. They perform analysis on their experimental RNN on these points (fig. 6 and 7 and 9). Though there are some assumptions made to make the theory, they discuss them and say them explicitly, so that all seems kosher.", "methods_and_evaluation_criteria": "Yes, I find the methods good, and appreciate that they tested on random automata in the appendix.\n\nRegarding the transformer experiments towards the end of the paper - I am unsure why they didn't study the modular addition task which has been shown to have the type of sudden phase-transitiony/grokking behavior that their parity RNN has. Instead they studied a modular subtraction task in a network which showed a smoother transition to generalization. I wonder if the results would bear out in a more clean way in the setting of more sudden grokking as their main example had in their RNN. In general I believe there is a lot more work that could have been done on the transformer - but that is reasonably beyond the scope of the current work (and I look forward to seeing it at some later date).", "theoretical_claims": "Yes, I found the theoretical work elegant and also was explained clearly.", "experimental_designs_or_analyses": "I thought their main RNN experiments, and the experiments on random automata were designed and carried out well.", "relation_to_broader_scientific_literature": "This is a strong contribution to the field of interpretability in neural networks. Arguably, the entire issue of interpretability can be framed as figuring out the fundamental link between the continuous (up to floating point precision) dynamics of neural networks and the algorithmic and symbolic nature of what we often think of as performing computation (a similar idea applies to neuroscience). This paper does a good job of pretty directly attacking this fundamental issue. There is a long history on this topic, goign back at least to", "essential_references_not_discussed": "I thought the references were reasonably complete, and I appreciated the connection to the neuroscience literature - but just to name some other refs that came to mind the authors might be interested in (I don't necessarily think these need to be included):\n\n- Cleeremans, Axel, David Servan-Schreiber, and James L. McClelland. \"Finite state automata and simple recurrent networks.\" Neural computation 1.3 (1989): 372-381.\nClassic work on a similar topic. McClelland has other similar work that more directly looks at fixed point structures in RNNs and interprets them as states of an automata but I can't find that work right now.\n\n- Shai, Adam, et al. \"Transformers represent belief state geometry in their residual stream.\" Advances in Neural Information Processing Systems 37 (2024): 75012-75034.\nIn that paper they show that the internal states of transformers represent the states of the probabalistic automata (they call it a mixed state presentation) that describes the prediction algorithm over some stochastic process. Similar to the inutition in the paper being reviewed, these states are also those that merge sequences of inputs that constrain the future in the same way.", "other_strengths_and_weaknesses": "I've answered this in responses to other questions.", "other_comments_or_suggestions": "I think the plots in figure 9 would look cleaner if you showed fewer x and y marker labels - e.g. you could show 0.2, 0.4, 0.6, 0.8, 1 instead of every .1 interval. or even 0.25 interval", "questions_for_authors": "How do you think the analysis, theory, and intuitions of this work apply to non-regular and probabilistic algorithmic tasks?\n\nWould the results of your transformer analysis look different if you analyzed a setting where obvious and sharp phase-transition grokking phenomenon occurs, like in the original Nanda et al work studying modular arithmetic?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qVSe7I6LDa", "reviewer": "Reviewer_opdC", "summary": "The authors provide an in-depth analysis for an RNN solving the Streaming Parity Task. Specifically, they extract a computational graph from the network at different training phases. Once this graph becomes cyclic, the network can generalize to longer times. An analytical treatment of how learning dynamics affects nearby representations explains some of the observed properties\n\n## After rebuttal\n\nAfter reading all the rebuttals and discussion with all reviewers, I am keeping my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and spending your time reviewing our paper. Please find below responses to your comments and the changes we will make to the paper.\n\n***Claims And Evidence***\n\nThe phrasing of the sentence in line 155 is not clear enough, so we will amend it to avoid confusion. What is meant by this is that initially only the training loss decreases, even though the generalization loss remains fixed. We can see in Figure 6 that the generalization loss is completely fixed until around 550 epochs, whereas training loss already can be seen in the plot to be decreasing at around 250 epochs, albeit very slowly initially. By the time the training loss gets close to zero the generalization loss starts to drop, although this happens almost immediately, with no delay in between.\n\n***Relation To Broader Scientific Literature***\n\nCorrect, the only difference between the interaction model discussed here in 3.2 and that in van Rossem & Saxe 2024 is replacing the linearized representation map with two optimizable vectors. This difference is due to the consideration of an RNN as opposed to a feedforward network. In a feedforward network we can smoothly vary the inputs for the map that assigns representations, and can thus take a local approximation. For an RNN we cannot do this as easily as the hidden map will depend on multiple input symbols. But since these are discrete we can instead consider representations for different input sequences as each separately optimizable vectors, as different sequences cannot get arbitrarily close in the input space. We will mention this contrast explicitly in the text.\n\n***Other Strengths And Weaknesses***\n\nNote that the network used here is quite overparameterized compared to the task. The RNN has 100 hidden units, which is very high dimensional considering a representation solving the task can in theory be constructed in one dimension. We did not see any issues related to network size limitations in the setting we studied. We found that we got consistent results for finiteness of the automata, using a large enough test set, with long enough sequences.\n\nThe timescales $\\tau_h$, $\\tau_y$ are depend on the architectural details of the map assigning representations and the map assigning outputs to those representations respectively, which have been abstracted away in the theoretical model. They cannot be determined from theory, only empirically by studying trajectories.\n\nWe will change the notation to more clearly distinguish between predicted outputs and target outputs.\n\nIn Figure 14 we see that for both theory and experiment the drop in number of states in the second phase is solely due to agreeing pairs. This is the main point of the figure. Besides that there is indeed not much of a match, and it the figure does not explain much else. We will state this more clearly in the paper.\n\nThe assumption in line 194 indeed does not hold in the training data for sequence pairs with different lengths and where only one subsequence will result in a sequence longer than 10. It still holds for most pairs of two input sequences and subsequence, but we should not say it holds for all. The better motivation for the assumption is that when there isn't a matching sequence that pair will not contribute to the interaction. We will change this in the text.\n\nThe motivation for equation (49) is as follows: if we consider the map assigning a representation to a sequence of length $n$, this map consists of the recurrent map applied $n$ times. Suppose this recurrent map has $P$ parameters. The total map assigning the representation will then have $nP$ parameters, if we double count the same parameters when they show up multiple times. Applying gradient descent to this will result in a sum of $nP$ terms, thus we expect the effective learning rate to scale linearly with $n$. We will add this explanation to the paper, since the current one is too limited.\n\nThere is no comparison of the two point dynamics because the simpler model from van Rossem & Saxe 2024 was not enough to capture the behavior here, see e.g. the initial divergence in Figure 10. The fixed expansion point interaction model can capture this behavior, but some of its parameters are hard to measure, as some of the quantities in equation (41) cannot be directly computed from the representation and prediction vectors. Additionally, it has far more freedom considering it has 4 instead of 2 effective parameters. Fitting it to the data would not be very demonstrative, as we would have enough freedom to fit any relatively simple curve such as seen here in the representational distance.", "claims_and_evidence": "Overall yes. There is one point which seems at odds with the results. In line 155, the authors write “As the model trains, the automaton expands into a complete tree that correctly fits the training data, reducing the loss only on the training data. After that, states in the automaton appear to merge until it becomes finite, at which point it generalizes on all data.” \nFrom reading this, one would expect the training loss to be close to zero – while the states keep on merging and then there is a large drop in generalization without a big change in training loss. In contrast, Figure 6 shows that the training loss hardly changes until dropping almost together with the generalization loss.", "methods_and_evaluation_criteria": "Yes. The tasks chosen are all described by automatons, allowing to check whether state mergers can lead to finite automatons and thereby generalization.", "theoretical_claims": "I read all the proofs. Did not check every math step in detail. The methods are very similar to van Rossem & Saxe 2024.", "experimental_designs_or_analyses": "Yes. The task is well suited to the problem at hand, and the training and automaton extraction seem valid.", "relation_to_broader_scientific_literature": "The mathematical part is very similar to van Rossem & Saxe 2024. If I understand correctly, the main difference is defining h_1 and h_2 as individual functions, instead of optimizing Dh. This choice should be explicitly stated and motivated in the text. \nThe application of the theory to algorithm development is novel to the best of my knowledge.", "essential_references_not_discussed": "Two papers that come to mind in the context of automaton extraction are:\nTurner, Elia, Kabir V Dabholkar, and Omri Barak. “Charting and Navigating the Space of Solutions for Recurrent Neural Networks.” In Advances in Neural Information Processing Systems, 34:25320–33. Curran Associates, Inc., 2021. \nBrennan, Connor, Adeeti Aggarwal, Rui Pei, David Sussillo, and Alex Proekt. “One Dimensional Approximations of Neuronal Dynamics Reveal Computational Strategy.” PLOS Computational Biology 19, no. 1 (January 6, 2023): e1010784. https://doi.org/10.1371/journal.pcbi.1010784.", "other_strengths_and_weaknesses": "Finite automaton (line 160) – because the network is finite, there is a finite number of states by definition. To show that the automaton is infinite before the transition, one would need to see how the number of states scales with the size of the network and the duration of the training sequences.\nWhat determines the timescales (tau_h, tau_y)? \nDefinition of w is a bit confusing because it seems like dy should equal y2-y1. Perhaps it’s worth emphasizing that dy is the network’s output and y2-y1 is the difference in labels.\nLine 1175 wether – whether\nFigure 14 – The match between theory and experiment is not very convincing.\nRelation to neural collapse, Farrell. NTK and others. Tunnel \n\nLine 194 – “this assumption is true for the training data”. What happens when x1,x2 are of different length? Because the training set is length 10, there isn’t a match between any residual sequences.\nThe definition of subsequence vs. initial sequence is not entirely clear.\nEquation 49 – what is the intuition / justification for this?\nThere is no direct comparison of dynamics (dh,w…dy) to data. (Similar to figure 4 in van Rossem & Saxe).\nFigure 4 :loss type and secondary y axis missing", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YQTeFFQdkC", "reviewer": "Reviewer_axEp", "summary": "This is an interesting work that studies the development of algorithms in RNN. It combines theory and experiments, which I think is a great plus. The theory and experiments are novel, showing how representations become merged in a linearized dynamical theory", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and spending your time reviewing our paper. Please find below responses to your comments and the changes we will make to the paper.\n\n***Experimental Designs Or Analyses***\n\n- The RNN was initialized at small weights, which is why we see few states at initialization in Figure 4. Due to the small weights, the hidden states are initially all close. We will make this clearer in the figure's description. When we rerun the experiment at a higher initialization scale (but still in the generalizing regime), we see more states at initialization. These quickly disappear during training, and the rest of the behavior is the same in this case as seen in Figure 4.\n\n- We used approximate identity, since due to numerics two representations never end up overlapping exactly. We merge two states when their representational distance is below a threshold. The threshold was set at 0.01 of the representational standard deviation during the entire training procedure. Varying the threshold around this scale did not significantly affect results.\n\n***Essential References Not Discussed***\n\nWe agree the paper should make it more clear that noise and regularization can still play important part in representation learning for many settings. We will add this to the paper and cite relevant literature.", "claims_and_evidence": "The claims are validated, and I find that the experiments are sufficient", "methods_and_evaluation_criteria": "Good", "theoretical_claims": "Nothing too problematic, even though the theory may be too simple -- it is a simple quadratic loss function!", "experimental_designs_or_analyses": "I am a little confused with the result in Figure 4. \na) at initialization, why are there so few states? Here, all the weights are random and so all the states should be different, right? I would expect a lot of states here\n\nb) how do you count the number of states? Does it require both representations to be **exactly** identical? Or some approximate identicality is sufficient?", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "I think the references are fine -- maybe the work should acknowledge and discuss its limitation more. For example, noise and/or regularization are known to be a key factor of representation learning, but the proposed theory ignores both factors: https://arxiv.org/abs/2410.03006", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "See my answers above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers appreciated this paper’s clear exposition, rigorous analysis, and compelling experiments on how recurrent neural networks solve the streaming parity task by effectively learning and consolidating a finite automaton. Multiple reviewers highlighted the insightful theoretical framework illustrating how pairs of hidden states diverge or converge (merge) under gradient flow, and how this merging drives out-of-distribution generalization. The experiments were found to be well-designed and strongly supportive of the authors’ claims.

Reviewers noted areas that could use clarification. The authors’ rebuttal and plan to revise the paper satisfied most concerns. Overall, the reviewers concur that the work represents a strong contribution to our understanding of how neural networks can learn algorithmic behaviors with finite-state-like structures.
Decision: Accept (oral)