Neural Networks and the Chomsky Hierarchy — part 5/6
Cleaned-text code points [61277, 76804). Bibliography omitted here; source.md includes it.
The NDStack-RNN is comparably slow to train. It is roughly four times slower than a classical Stack-RNN, due to the computation of the big tensor γ \gamma , denoting the transition weights between nodes. Furthermore, this tensor takes a lot of space in memory, i.e., the number of values it contains is, once unrolled on the whole trajectory, proportional to ( l + m ) 3 (l+m)^{3} , where l and m are the length of the input and output sequences, respectively. Thus, for our training range of 40 and a task where the output length is equal to the input length (e.g., Reverse String (DCF)), the required space is proportional to ( 40 + 40 ) 3 = 512000 (40+40)^{3}=512000 . Therefore, with a batch size of 128 and 16 possible actions (i.e., state-symbol pairs), the tensor is roughly of size 33.5Gb using float32 representation, which exceeds the memory size of our GPUs. Consequently, we reduced the batch size to 16 (i.e., 8 times smaller than normal) for this architecture.
## Appendix B Additional Experiments
### B.1 Main result
We visualize the performance curves for all tasks in Fig. B.6 and report the means and standard deviations of the test accuracies for all architectures on our tasks in Table B.1 . We observe that all the networks, except for Transformers, solve all regular tasks perfectly for all the seeds. However, only a few tasks above beyond regular can be solved (defined by a score larger or equal to 90 % 90\% ) on average, but the hierarchy still persists. For example, the Tape-RNN has much better scores overall, even on average, on the CS tasks compared to the other architectures. However, even though the Tape-RNN can solve more tasks, it still fails on some of them. We hypothesize that it is because the limited set of actions makes the right action trajectory long and difficult to find. Nevertheless, the Tape-RNN is the closest we have to an architecture capable of solving all tasks from regular to CS . Note that networks may be evaluated on unseen sequences even within the training range, as we are sampling from a training distribution and not a finite dataset (as discussed in Section 4 ). Thus, it is possible that some models do not achieve a perfect accuracy within the training range 𝒰 ( 1 , N ) \mathcal{U}(1,N) , such as in the Compute Sqrt ( CS ) task (cf. Fig. B.6 ).
### B.2 Phase transition under increasing training ranges
In this section, we investigate how much training data is needed to learn the data-generating grammars. For certain tasks and architectures we observe a substantial “phase transition” of the test accuracy for different training ranges. For example, Fig. B.1 shows the generalization performance of Stack-RNNs on the Reverse String ( DCF ) task for different training ranges. Clearly, the models fail to learn the data-generating algorithm when only exposed to sequences of length smaller than 10. We hypothesize that for small training ranges the networks overfit to the training data, essentially learning a lookup table to recognize the small finite language. In contrast, larger training ranges encourage the networks to learn the data-generating algorithm that generalizes to sequences of unseen length.
### B.3 Analysis of state- and memory-dynamics
#### B.3.1 Stack-RNN program analysis
Here, we check that the Stack-RNN, which is our simplest memory augmented network, performs as expected on some of our simple tasks. As mentioned in Section 5.2 , Fig. 2(a) shows that on the Parity Check ( R ) task the network ignores the stack by only applying no-op and pop actions (visualized on an unseen sequence of length 100). We recall that Fig. 3(a) also showed that the PCA of the states is identical to the one of a simple RNN as it only depends on the last result and the last input token. Moreover, Fig. 2(b) demonstrates that on the Reverse String task the network always uses the push action until the first empty token is reached, whereupon it starts performing pop actions until the end, which exactly matches the algorithms we would expected a PDA to implement. Note that in this task the number of empty tokens ∅ \varnothing we append to the input sequence is equal to the length of the input sequence, and thus the total sequence is of length 200. Finally, Fig. 2(c) shows that the Stack-RNN can leverage its probabilistic actions to implement multiple counters and consequently solve (counting) tasks that are beyond deterministic context-free . Concretely, the Stack-RNN uses a mixture of push and no-op actions to simultaneously push incremented counters while keeping the previous counter values unchanged. Once the Stack-RNN has consumed the entire input sequence, it switches to a mixture of pop and no-op to decrement the counters for the different tokens. Interestingly, once the final token is reached, the Stack-RNN relies mostly on no-op actions, since it has learned that the remainder of the output string will contain the token of highest value.
#### B.3.2 Transformer program analysis
##### Setup
The transformer achieves a non-trivial generalization score ( 61.9 % 61.9\% with baseline 20 % 20\% ) on the Cycle Navigation ( R ) task but it does not ‘solve’ the task (in terms of our definition of score ≥ 90 % \geq 90\% ). Therefore, we analyze the network’s internals, in particular the attention matrices, to understand which algorithm the network has learned and why it fails on very long sequences. We visualize the attention matrices in Fig. B.3 . The color scale is dark blue for 0.0 0.0 and yellow for 0.5 0.5 (not 1.0 1.0 to increase readability). Our transformer networks consist of 5 layers with 8 heads, and we show all of the attention matrices (i.e., 5 ⋅ 8 5\cdot 8 ) for a short input sequence of length 8. Note that the actual input to the network is of length 9 since we append an empty token to the input sequence, from which we retrieve the output (see Section 4 and Appendix A ).
##### Interpretation of the learned algorithm
On the first layer, the model uses only the last empty token and matches it with the tokens 0 and 2 (clearly seen on matrices (1, 1) and (1, 2)). Note that the task is to count the number of 0s, the number of 1s, and to do a subtraction modulo 5. This first layer is able to separate the different tokens; the output of the last token for each head is a weighted sum (softmax) of a single value (the token which is attended to), and the weights are all equal to a constant, which means the output of the last token is just the value of the token which is attended to. Then the other tokens have a constant weight over the whole sequence, which means that the output is a weighted sum of all the tokens’ values, with the weights also being constant and proportional to the number of occurrence of each token. This will then allow the network to compute the occurrence of each token individually in the linear layer to merge the heads. Fig. B.4 shows a scatter plot of the activations of the network after the first layer for sequences of length 20, which confirms this claim.
##### Failure mode for long sequences
The counting mechanism, which consists in having constant weights over the whole sequence, does not return true counts but frequencies, since they are multiplied by 1 / N 1/N where N N is the sequence length (since we are using a softmax). This explains why the network can reasonably generalize to longer lengths, but not perfectly. Looking at Fig. B.4 , it means that the structure we see is conserved for longer sequences, but the points become closer and closer, which makes further differentiation into classes more difficult. Fig. B.5 shows the evolution of the activations at the last layer for increasingly long sequences. The classification becomes more challenging because the input activations do not form 5 clear clusters anymore.
### B.4 Convolutional Neural Networks
Bansal et al. (2022) showed that fully convolutional networks achieve near-perfect length generalization on the prefix sum task in the length generalization setting. At the same time, Merrill (2019) theoretically showed that one-layer convolutional networks with maxpool activation functions are incapable of recognizing all regular languages. Therefore, we investigate the length generalization performance of a simple CNN on our benchmark and visualize the maximum and average accuracies over unseen test lengths in Tables B.2 and B.3 , respectively. We observe that our simple architecture with kernel sizes in { 3 , 5 , 7 , 11 } \{3,5,7,11\} (see Section A.2 ) generally fails to solve even regular tasks, achieving the random baseline accuracy in most cases. This confirms the theoretical derivations by Merrill (2019) but contrasts the results presented by Bansal et al. (2022) . However, the convolutional architecture that Bansal et al. (2022) consider relies on an adaptive number of layers depending on the sequence length (similar to adaptive computation time ( Graves, 2016 ) ) and thus crucially differs from a classical CNN (such as the one we study).
### B.5 Stack-LSTMs
We evaluate the experiment suite from Section 5.1 for the Stack-LSTMs and compare their performance with that of Stack-RNNs in Table B.2 . We observe that Stack-LSTMs and Stack-RNNs perform roughly equally well when considering the score (maximum accuracy over the 10 initialization seeds), which is not surprising given that both networks are theoretically located on the same level of the Chomsky hierarchy. However, when considering the average Stack-LSTMs perform worse, i.e., our training protocol (gradient descent) is less stable for this architecture, confirming the results of prior work ( Hao et al., 2018 ) . We hypothesize that this is due to the fact that LSTMs are more powerful than RNNs (as they can implement k-counter machines) and thus do not always simulate a finite-state automaton . This can be an advantage for more difficult tasks, e.g., counting tasks such as Bucket Sort ( CS ), but also a disadvantage for simpler tasks that only need a finite-state automaton controller to interact with the memory structure. Thus, if the controller is not a finite-state automaton , then its internal state does not interact well with the stack content as it is not part of a finite set, i.e., the interactions are potentially infinite and thus the network does not generalize well beyond the training range.
### B.6 NDStack-RNN
We also compared the Stack-RNN and the Stack-LSTM to their non-deterministic counterpart, the NDStack-RNN (which stands for Non Deterministic Stack-RNN) ( DuSell & Chiang, 2020 ; DuSell & Chiang, 2022 ) . We observe that this architecture performs well on regular tasks, as the other memory-augmented RNNs. However, it fails on most tasks beyond regular, potentially due to its large action space (24 actions) and the difficulty of training a tensor that tracks all possible stack values. We also don’t use unnormalized actions as it requires computing all the probabilities in log-space, and unfortunately JAX ( Bradbury et al., 2018 ) does not support complex tensor multiplications like e i n s u m einsum in log-space. Surprisingly, the architecture solves the Missing Duplicate ( CS ) task perfectly. We tried some ablations and reduced the stack size to only 1: the model still solves the task perfectly. Also, the actions taken by the model on the stack are not binary, leading to mixed computation. We conjecture that the network uses this mixed embedding of values on the stack (reduced to a single cell) efficiently as a memory, on top of the memory of the RNN controller.
### B.7 Autoregressive Models
In this paper, we chose to predict the output sequences from empty tokens, but we could also have chosen to predict the sequences autoregressively. Here, we conduct the same set of experiments but in the autoregressive setting to confirm that this aspect of our experimental setup does not impact the architectures’ positions in the Chomsky hierarchy. To that end, we use the true output sequence as the input to the model at train time and autoregressive sampling at test time, i.e., we use the predicted output token as the input for the next token until we reach the desired length (more details below for the different architectures). We show the results in Table B.2 with the corresponding means and standard deviations in Table B.3 .
#### B.7.1 Memory-augmented recurrent neural networks
For the (memory-augmented) RNNs, i.e., RNN, LSTM, Stack-RNN and Tape-RNN, we replace the empty tokens ∅ \varnothing with the true output sequence during training. However, to avoid predicting the input, we append an extra empty token between the input sequence (which could contain computation steps) and the true output sequence. We compute the loss with an offset of 1, so the network should predict the first token of the output sequence for the extra empty token, then the second token of the output sequence for the first token, passed now as input, etc. We observe in Table B.2 that these models trained with the auto-regressive system perform very similarly to the ones trained with the empty tokens system (see Table 2 for comparison). That is, this part of the training scheme does not affect the length generalization scores, and therefore does not change where the networks lie on the Chomsky hierarchy.
#### B.7.2 Transformer
In Section 5 , we compared the Transformer encoder (used in a non-autoregressive manner) to other sequence prediction models since this allowed for a fair comparison in terms of the experiment setup (all models had to predict the output from empty tokens ∅ \varnothing ). However, the original Transformer architecture ( Vaswani et al., 2017 ) also consists of a decoder and processes sequences autoregressively, which is what we evaluate in this section. Similar to memory-augmented RNNs, we observe that the autoregressive model performs roughly as well as the Transformer encoder, except that it fails to solve (or show strong performance) on the permutation-invariant task Bucket Sort ( CS ). This is likely due to the causal masking in the decoder attention, which eliminates permutation-invariance. However, the autoregressive model is capable of solving the Duplicate String ( CS ) perfectly. We hypothesize that this is due to the fact that the relevant input and output tokens are at a fixed length throughout the task and thus the model manages to align the input and output embeddings (using relative positional encodings).
### B.8 Scaling laws and the Chomsky hierarchy
Suppose a neural architecture, e.g., a transformer, is limited to a particular algorithmic complexity class (level on the Chomsky hierarchy). In that case, no amount of scaling of the training time, training data, or the number of model parameters can overcome this limitation, thus putting a hard limit on what is possible via scaling. Specific neural architectures might simply be unable to implement certain classes of algorithms in practice (i.e., when considering the training protocol). While we cannot rule out that excessive training, hyper-parameter tuning, or some very delayed grokking effect ( Power et al., 2022 ) would lead to the architecture eventually solving the task, we can show that at least under standard training conditions, we can surface some systematic limitations that are not overcome with more training data or larger models but can be overcome with architectural extensions in line with the theory of computation (i.e., adding a stack or a tape to an RNN).