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

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.

Experimental Designs Or Analyses

• 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.

• 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.

Essential References Not Discussed

We 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.

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.

Claims And Evidence

The 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.

Relation To Broader Scientific Literature

Correct, 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.

Other Strengths And Weaknesses

Note 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.

The 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.

We will change the notation to more clearly distinguish between predicted outputs and target outputs.

In 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.

The 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.

The 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.

There 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.

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.

Weaknesses

• 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.
  We 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.
• 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.

Questions For Authors

1. 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.
2. 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.
   We 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.
   From what we have seen all merging pairs move apart before merging with a similar pattern.
3. 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.
4. 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.
5. 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.

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.

Questions For Authors

• 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.

• 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.