Neural Networks and the Chomsky Hierarchy — part 3/6

Cleaned-text code points [29740, 45622). Bibliography omitted here; source.md includes it.

In contrast to the RNN and Stack-RNN, the reverse-engineered network mechanisms for the Tape-RNN are less interpretable. Neverthless, Fig. 3(c) shows that the Tape-RNN has learned an algorithm that is indicative of the data-generating grammar of the Duplicate String ( CS ) task. The input to the network consists of the sequence a , a , b , a a,a,b,a of length ℓ = 4 \ell=4 , followed by 2 ​ ℓ 2\ell α \alpha -symbols that the RNN can use to compute and manipulate the tape, followed by 2 ​ ℓ 2\ell β \beta -symbols used to output the result (i.e., the sequence a , a , b , a , a , a , b , a a,a,b,a,a,a,b,a of length 2 ​ ℓ 2\ell ). The panels show the action probabilities and memory contents over time. We observe that up to time t = 5 t=5 the RNN writes on the memory with write-left . Then, on time-step 6 6 the RNN mixes jump-right and write-stay to duplicate the input string in the memory, before moving back to the initial position with jump-right on time-step 7 7 . After this, the RNN idles using write-stay until it reaches the first β \beta -symbol, whereupon it starts outputting the result using write-left actions.

### 5.3 LSTMs

LSTMs are similar to RNNs as they also carry a hidden state and are unrolled over a sequence of inputs. However, prior work showed that LSTMs are strictly more powerful than RNNs because they can also solve counting tasks ( Bodén & Wiles, 2000 ; Bodén & Wiles, 2002 ; Gers & Schmidhuber, 2001 ; Merrill, 2019 ; Weiss et al., 2018 ) . Indeed, Table 2 provides further evidence for this claim since LSTMs are capable of solving Bucket Sort ( CS ) almost perfectly, even though the task is context-sensitive . That is, counting tasks can reside on levels higher than regular in the Chomsky hierarchy, since every Turing machine can, in theory, be simulated by a two-counter machine ( Minsky, 1967 ) . However, finding an architecture that solves non-regular tasks with counters via gradient descent is more difficult than when the controller has access to a more permissive memory structure, such as a stack or a tape.

### 5.4 Transformers

Unlike the other architectures, Transformers are permutation invariant w.r.t. the position of a token in a sequence because they rely on a global attention mechanism. As a result, Transformers are more scalable since all tokens can be processed in parallel, however, at the cost of reduced expressivity (i.e., permutation invariance). Similar to real-world problems, most of our tasks are not permutation invariant, e.g., reversing a string depends on the tokens’ position. To overcome this problem, Transformers are generally augmented with positional encodings, which are added to the tokens to simulate some notion of position. Consequently, the augmented tokens intrinsically contain position information, i.e., the token x x at position 0 will no longer be considered the same as the same token x x at position 10. As described in Section 4 , we evaluate five encodings (none, sin \sin / cos \cos , RoPE, ALiBi, and the relative positional encoding from Transformer-XL) and report the best-performing variant.

Indeed, Table 2 shows that Transformers are most successful on permutation-invariant tasks: They solve Bucket Sort ( CS ) and demonstrate non-trivial generalization on Cycle Navigation ( R ). Moreover, they solve Even Pairs ( R ), which is not permutation-invariant but only requires checking whether the first and last tokens are equal (i.e., all other positions are irrelevant). However, for all other tasks, Transformers fail to generalize, regardless of their positional encodings (see Fig. 4(a) for the different positional encodings on Reverse String ( DCF ) and Fig. B.7 for the remaining tasks). In particular, Transformers are unable to solve all permutation-invariant tasks (i.e., Parity Check ( R ), which is a well-known failure mode ( Chiang & Cholak, 2022 ) ). We hypothesize that this poor performance is due to the positional encodings, which take on new values when the sequences grow longer (even for relative encodings), meaning that the network activations will be out-of-distribution. Indeed, Fig. 4(b) shows that the 2D PCA of the first layer activations is similar for sequences of length 40 (i.e., the training range, in blue) and 50 (in orange), but completely different for length 150 (in green). All our other models, which do not rely on global self-attention, do not suffer from this effect, as they only have access to a local view of the input token (and, potentially, a local memory reading).

## 6 Discussion

In this paper, we considered generalization from a sequence prediction viewpoint, using formal language theory to establish the computational complexity of each task. Naturally, we had to choose a maximum test sequence length for our evaluations, which theoretically renders all of our input and output languages finite. However, our sequences share the structure of an infinite language, allowing us to measure generalization by testing on input sequences that are significantly longer than those seen during training (and are thus out-of-distribution). Therefore, observing successful generalization in our setting is strong evidence that the network has learned the “correct” algorithm. However, for some tasks where we consider generalization to be successful we still see a slight degradation of the accuracy as the test length increases. This is a result of implementing finite state machines and memory updates with a neural network trained via SGD: Even slight numerical inaccuracies in state-transitions or memory dynamics might accumulate when increasing the test sequence length.

Our experiments indicate that RNNs, LSTMs, and Transformers, admittedly powerful architectures, are fairly limited in terms of their ability to generalize to longer inputs. However, this result must be contrasted with their ability to generalize and detect/extrapolate patterns for fixed size inputs or fixed size context windows. Transformers, for instance, are capable of learning complex and highly structured generalization patterns, but they cannot overcome the limitation of not having an extendable memory (which only becomes apparent when probed as in our experiments). This might imply hard limits for scaling laws ( Kaplan et al., 2020 ) : Even significantly increasing the amount of training data and the size of a Transformer are insufficient for it to “climb the Chomsky hiearchy”.

## 7 Conclusion

We leveraged the theory of computation to better understand how and why neural networks generalize on algorithmic sequence prediction tasks. Our extensive empirical evaluation demonstrates that there is a model hierarchy on the tasks we investigated, which are representative of the different levels of the Chomsky hierarchy. In particular, we showed that state-of-the-art architectures, such as LSTMs and Transformers, cannot solve seemingly simple tasks, such as duplicating a string, when evaluated on sequences that are significantly longer than those seen during training. Moreover, we showed that models interacting with an external memory structure, such as a stack or a finite tape, can climb the Chomsky hierarchy, indicating a promising direction for improvements in architecture design.

## 8 Ethics Statement & Limitations

Although our results are consistent with prior theoretical analyses ( Ackerman & Cybenko, 2020 ; Merrill, 2019 ; Weiss et al., 2018 ) , and suggest that we can group neural architectures according to the Chomsky hierarchy, our claims are limited to our empirical study. In particular, we cannot guarantee that no tasks exist higher in the hierarchy ( Fig. 1 ) that an architecture could solve. Similarly, we cannot guarantee that no tasks exist lower or on the same level of the hierarchy that an architecture cannot solve. Moreover, without extracting and analyzing the automata implemented by the networks, we cannot strictly claim that our architectures generalize to arbitrary-length inputs, as we only test up to a maximum length. Finally, our results are w.r.t. our precise experimental setting, i.e., if an architecture fails to generalize we cannot guarantee that no weight configuration would solve the task; we were simply unable to find such a configuration with our training protocol.

#### Acknowledgments

We thank Ann He, Chris Dyer, Markus Kunesch, Róbert Csordás, Tom McGrath, and Zhengdong Wang for their helpful feedback and insightful conversations.

## Appendix A Experimental details

### A.1 Language recognition vs. transduction

In practice, learning to recognize a formal language by training a classifier on words and non-words of a language is hard because there is, in general, no formal construction for generating a sufficient but finite set of negative examples. Thus, prior work has relied on other approaches to evaluate language recognition capabilities. These approaches are variants of language generation, which are as hard as their recognition counterpart (for a given language) and thus are good proxy tasks.

The first approach is autoregressive token prediction (standard in the machine learning community ( Bahdanau et al., 2015 ; Vaswani et al., 2017 ) ): Given a prefix p p of a word w ∈ L w\in L , predict the probability of its next token t ∈ Σ t\in\Sigma . The main problem with this approach is that the probabilities depend on the length distribution of the training strings. For instance, for the language of palindromes of length 2, with alphabet Σ = { a , b } \Sigma=\{a,b\} , the output probabilities are P ⁡ ( a | prefix = a ) = 1 P(a|\mathrm{prefix}=a)=1 and P ⁡ ( b | prefix = b ) = 1 P(b|\mathrm{prefix}=b)=1 . However, for palindromes of length 3, the probabilities are very different, i.e., P ⁡ ( a | prefix = a ) = 0.5 P(a|\mathrm{prefix}=a)=0.5 and P ⁡ ( b | prefix = b ) = 0.5 P(b|\mathrm{prefix}=b)=0.5 . Therefore, there is a conflict between the different distributions, and no model can solve the task without knowing the length beforehand. Accordingly, increasing the length at test time without informing the model makes it impossible to find the correct new probabilities and, therefore, to generalize to inputs of unseen lengths.

The second approach is to predict the set of possible next tokens and not their probabilities ( Bhattamishra et al., 2020 ; Suzgun et al., 2019a ) . In this case, the distribution of possible next tokens does not change with the length, and increasing the length at test time is possible. However, for each prefix, the target will consists of a set of tokens, which is incompatible with the (standard sequence) prediction setting and thus of lesser interest to the wider machine learning community.

Our approach is similar to the second one, but we only consider prefixes for which there is only one possible (deterministic) continuation. Thus, instead of language generation, we consider language transduction: The inputs and outputs form two individual languages, and the goal is to learn the deterministic function that maps a word from one to the other. The automata solving these tasks are the classical automata from Fig. 1 but with outputs attached to each transition and are denoted transducers. Therefore, the hierarchy that we consider is a hierarchy over transducers and not over acceptors as detailed in Section 3 . However, the two types of machines (acceptor automata and transducer automata) are interchangeable for the purposes of our investigation as they are both memory-augmented finite-state automata that reside on different levels of the Chomsky hierarchy depending on their type of external memory access (none, a stack, or a tape).

### A.2 Models

Here we describe our neural architectures in more detail. All models have a final linear readout layer to produce the output logits. We do not use any regularization, e.g., weight decay, dropout (except for the Transformer models), etc. For training of the memory-augmented models, we set the tape size to 256 256 and the stack size to 128 128 and manually increase their sizes when testing on longer sequences. Thus, as these memory sizes are significantly larger than the training range N N (see Section 4 ), the finite memory models appear infinite for our neural architectures in the context of our experimental evaluation. Moreover, increasing the memory size does not affect how the RNN controller takes actions, since it only has access to a local view of the external memory (e.g., the top of the stack or the current memory cell).

##### RNN

A vanilla single-layer RNN ( Elman, 1990 ) with hidden size of 256.

##### Stack-RNN

A single-layer RNN controller of hidden size 256 with access to a differentiable stack ( Joulin & Mikolov, 2015 ) . The controller can perform any linear combination of push , pop , and no-op on the stack, with action weights given by a softmax over a linear readout of the RNN output. Each cell of the stack contains a real vector of dimension 8.

##### NDStack-RNN

A single-layer RNN controller of hidden size 256 with access to a differentiable nondeterministic stack. We consider the NDStack-RNN proposed by ( DuSell & Chiang, 2020 ; DuSell & Chiang, 2022 ) , which simulates a nondeterministic stack via dynamic programming. Concretely, we use normalized actions and nondeterministic state reading with 2 states and sweep over 2 , 4 {2,4} symbols. We did not use the unnormalized actions as suggested in ( DuSell & Chiang, 2022 ) .

##### Tape-RNN

A single-layer RNN controller of hidden size 256 with access to a differentiable tape, inspired by the Baby-NTM architecture ( Suzgun et al., 2019b ) . The controller can perform any linear combination of write-right , write-left , write-stay , jump-left , and jump-right on the tape, with action weights given by a softmax. The actions correspond to: writing at the current position and moving to the right ( write-right ), writing at the current position and moving to the left ( write-left ), writing at the current position ( write-stay ), jumping ℓ \ell steps to the right without writing ( jump-right ), where ℓ \ell is the length of the input, and jumping ℓ \ell steps to the left without writing ( jump-left ). Finally, to allow the Tape-RNN to perform memory operations without having to produce the output, we append “computation” tokens (different from the empty tokens ∅ \varnothing used to produce the output, see Section A.4 below) to the input sequence. As in the Stack-RNN, each cell of the tape contains a real vector of dimension 8.

##### LSTM

A vanilla single-layer LSTM Hochreiter & Schmidhuber (1997) of hidden size 256.

##### Stack-LSTM

A single-layer LSTM controller of hidden size 256 with access to a differentiable stack Joulin & Mikolov (2015) . The only difference to the Stack-RNN is that this model uses an LSTM as the controller.

##### Transformer encoder

A vanilla Transformer encoder ( Vaswani et al., 2017 ) . We do not use the autoregressive sequence-to-sequence model to produce the output but attend the whole input (including the empty tokens ∅ \varnothing ). We use five blocks with d m ​ o ​ d ​ e ​ l = 64 d_{model}=64 , where each block is composed of an attention layer, two dense layers, and a layer normalization. We add a residual connections as in the original architecture ( Vaswani et al., 2017 ) . We consider five different positional encodings: none, classical sin/cos ( Vaswani et al., 2017 ) , RoPE ( Su et al., 2021 ) , ALiBi ( Press et al., 2021 ) , and the relative positional encoding from Transformer-XL ( Dai et al., 2019 ) .

##### Transformer (autoregressive)

A vanilla Transformer ( Vaswani et al., 2017 ) . We do not use empty tokens ∅ \varnothing anymore, and the output is produced via the decoder (using causal masking). We use the same hyperparameters and positional encodings as for the Transformer encoder above.

##### Convolutional Neural Network