Neural Networks and the Chomsky Hierarchy

Introduction

The key challenge of inductive inference (as opposed to deduction) is that it does not allow selecting one hypothesis with certainty among the ones that fit the data. For instance, the sequence $2,4,6,8$ has infinitely many possible continuations. Thus, any principle that selects a particular continuation requires additional assumptions that are independent of the data, i.e., inductive biases (Mitchell, 1980). In machine learning, the network architecture, training mechanisms (e.g., gradient descent), and initial distributions over parameters all generate their corresponding inductive biases. This has led to a vast number of approaches for designing inductive biases via architectural and training protocol changes (see Battaglia et al. (2018) for an overview). However, the problem is that stronger inductive biases generally come at the cost of decreasing the universality of a model, and thus finding a good balance between the two is one of the biggest challenges in the contemporary literature.

Even if a neural architecture is theoretically universal or Turing complete, gradient-based training, which cannot exhaustively search the parameter space, can impede finding the right solution and thus practically render the model non-universal. Therefore, both architectural and training limitations impact which sequence prediction problems a model can solve in practice. In formal language theory, the Chomsky hierarchy (Chomsky, 1956) classifies such (sequence prediction) problems by increasing complexity. This hierarchy is associated with an equivalent hierarchy of models (automata) that can solve different problem classes (Savage, 1998; Sipser, 1997). Lower-level automata have restrictive memory models and can only solve lower-level problems, while Turing machines with infinite memory and unrestricted memory access lie on top of the hierachy and can solve all computable problems. However, unlike for classical automata, a unified placement of neural architectures on the Chomsky hierarchy has not yet been practically established, which is precisely the goal of our work.

We conduct an extensive empirical study with the aim of discovering how neural network models used for program induction relate to the idealized computational models defined by the Chomsky hierarchy in practice (see Fig. 1 for a summary of our findings). We investigate whether the theoretical limitations of certain neural models hold in practice when trained with gradient-based methods. For example, previous work has theoretically argued that RNNs are Turing complete (Siegelmann & Sontag, 1994). However, more recent theoretical analyses (Ackerman & Cybenko, 2020; Merrill, 2019; Weiss et al., 2018) showed that RNNs lie much lower on the Chomsky hierarchy. To complement these theoretical analyses, we conduct a large-scale empirical evaluation on sequence prediction problems. We make the following main contributions:

We conduct an extensive generalization study ($20\,910$ models, 15 tasks) of state-of-the-art neural network architectures (RNN, LSTM, Transformer) and memory-augmented networks (Stack-RNN, Tape-RNN) on a battery of sequence-prediction tasks spanning the entire Chomsky hierarchy that can be practically tested with finite-time computation.

We open-source a length generalization benchmark (https://github.com/deepmind/neural_networks_chomsky_hierarchy) that is out of reach for state-of-the-art sequence prediction models and allows us to pinpoint the failure modes of these architectures.

We show how increasing amounts of training data do not enable generalization on our tasks higher up in the hierarchy for some architectures (under sufficient capacity to perfectly learn the training data) potentially implying hard limitations for scaling laws (Kaplan et al., 2020).

We demonstrate how augmenting architectures with differentiable structured memory (e.g., with a stack or a tape) can enable them to solve tasks higher up the hierarchy.

Related work

A long line of work has empirically investigated whether common machine learning architectures, including RNNs (Elman, 1990), GRUs (Cho et al., 2014), SCNs (Giles et al., 1992; Pollack, 1991), LSTMs (Hochreiter & Schmidhuber, 1997), and Transformers (Vaswani et al., 2017), are capable of learning formal languages. The main insights are: These networks can learn simple counting languages (Hölldobler et al., 1997; Steijvers & Grünwald, 1996; Wiles & Elman, 1995; Rodriguez & Wiles, 1997) and the Dyck-1 language (Skachkova et al., 2018; Suzgun et al., 2019a). To learn more advanced languages, RNNs and LSTMs require exponential memory in terms of the input length (Sennhauser & Berwick, 2018), as they lack an external memory structure. They are capable of learning simple context-sensitive languages, such as $a^{n}b^{n}c^{n}$, but in a very limited way, i.e., they generalize only to lengths close to those seen during training (Bodén & Wiles, 2000; 2002; Gers & Schmidhuber, 2001). Similarly, Transformers cannot learn Dyck-$n$ languages for $n>1$ and long sequences (Ebrahimi et al., 2020). Concurrent work also studies length generalization on synthetic reasoning tasks (akin to learning formal languages) but for pretrained large language models (Anil et al., 2022; Zhang et al., 2022). Thus, while prior work has investigated a single architecture on a restricted set of tasks under different experimental conditions, we provide a unified experimental protocol that spans all the levels of the Chomsky hierarchy for a wide range of models.

It was theoretically shown that RNNs and Transformers are Turing complete (Chen et al., 2018; Pérez et al., 2019; 2021; Siegelmann & Sontag, 1994). However, these results are impractical as they rely on an unbounded number of recurrent steps and on arbitrary numerical precision. Thus, more recent work (Ackerman & Cybenko, 2020; Bhattamishra et al., 2020; Hahn, 2020; Hao et al., 2022; Korsky & Berwick, 2019; Merrill, 2019; Merrill et al., 2020; Merrill & Sabharwal, 2022; Weiss et al., 2018) has refined these theoretical analyses by considering linear computation steps and logarithmic precision, showing that: (i) RNNs and GRUs can, in theory, recognize regular languages, and (ii) LSTMs are strictly more powerful since they can learn a counting mechanism (i.e., are k-counter machines). Moreover, it was theoretically shown that Transformers are not well-aligned with the Chomsky hierarchy since they cannot recognize certain regular languages (e.g., periodic finite-state languages), while being able to learn some counter languages (e.g., Shuffle-Dyck and $n$-ary Boolean expressions). A different approach proposed a computational model to capture the Transformer operations and used it to show which tasks could conceivably be learned by a Transformer (histograms, sorting, Dyck languages) (Weiss et al., 2021). However, this approach only upper-bounds the capabilities of a model and does not provide any insight on whether gradient-based methods will find parameters that can solve a task in practice, which is precisely the goal of our work. In that sense, our work complements the above studies by investigating how well gradient-based learning can exploit the inductive biases of common machine learning architectures to recognize languages on different levels of the Chomsky hierarchy.

A popular approach for augmenting neural architectures with external memory is to equip a recurrent network with read and write access to differentiable memory structures, such as deterministic stacks (Das et al., 1992a; b; Grefenstette et al., 2015; Hao et al., 2018; Joulin & Mikolov, 2015; Mali et al., 2021; Mozer & Das, 1992; Stogin et al., 2020; Sun et al., 1993; Suzgun et al., 2019b; Yogatama et al., 2018), nondeterministic stacks (DuSell & Chiang, 2020; 2022), random access memory (Danihelka et al., 2016; Kurach et al., 2016), and memory matrices (Graves et al., 2014; 2016; Gülçehre et al., 2018; Yang & Rush, 2017). Such memory-augmented networks are capable of recognizing complex languages, including tasks like copying or reversing strings, but they can only perform one computation step per input token. Thus, to solve superlinear tasks (e.g., binary multiplication), memory-augmented networks also need to be able to perform a linear number of steps per token (Freivalds & Liepins, 2017; Kaiser & Sutskever, 2016; Price et al., 2016). In a different effort, reinforcement learning has been applied to interact with discrete memory interfaces, making deterministic memory operations amenable to gradient-based training (Zaremba & Sutskever, 2015; Zaremba et al., 2016). Finally, prior work also proposed networks with read-only memory access (Sukhbaatar et al., 2015; Weston et al., 2015) or spatiotemporal connections (Kalchbrenner et al., 2016). We also consider memory-augmented networks and find that memory structures are necessary to generalize on sequence prediction problems higher up the Chomsky hierarchy.

Background

We now provide the necessary background on how to link sequence prediction and formal language theory, allowing us to associate neural architectures and the Chomsky hierarchy. As we want to evaluate the capability of networks to generalize to sequences of unseen length, we need a way of generating arbitrarily long sequences that all exhibit the same structure. To that end, we will consider sequences as elements of infinite formal languages, which are generated by a grammar.

Languages of infinite cardinality can be generated with a finite alphabet and a finite generative grammar. A formal grammar (Chomsky, 1956) is defined by a finite set of terminal symbols, a finite set of non-terminal symbols, a distinctive start symbol, and a finite set of production rules that map from non-terminal symbols to other symbols. The set of all words that can be formed by such a grammar is its corresponding formal language. For example, the binary palindrome language $B$ can be generated by the set of rules: $P\rightarrow\epsilon\mid 0\mid 1\mid 0P0\mid 1P1$, with start and nonterminal symbol $P$ and terminal symbols $\{0,1\}$. The Chomsky hierarchy arises from categorizing the allowed relationships between terminals and non-terminals in the grammar (see Table 1). For example, $B$ is not regular, since the right-hand side contains a variable enclosed by two terminal symbols, but context-free, since the left-hand side consists of a single nonterminal symbol.

An automaton recognizes a language if it accepts all strings in the language and no others. For example, a (deterministic) finite-state automaton finite-state automaton (FSA)can be defined as a 5-tuple $(Q,\Sigma,\delta,q_{0},F)$, consisting of a finite set of states $Q$, the finite alphabet $\Sigma$, a transition function $\delta:Q\times\Sigma\rightarrow Q$, an initial state $q_{0}\in Q$, and a set of accept states $F\subseteq Q$. Thus, an FSA accepts a string $w=a_{1}a_{2}\ldots a_{n}$ over the alphabet $\Sigma$ if there exists a sequence of states $r_{0},r_{1},\ldots,r_{n}\in Q$ such that $r_{0}=q_{0}$, $r_{i+1}=\delta(r_{i},a_{i+1})$ for $i=0,\ldots,n-1$, and $r_{n}\in F$. More complex automata, such as the push-down automaton (PDA), additionally have access to an external memory structure. The Chomsky hierarchy classifies languages based on the automaton that can recognize it (see Table 1). All automata in the hierarchy have a finite state controller at their core, with increasingly flexible memory structures. Language classes generated by higher grammar types subsume languages generated by those lower in the hierarchy, e.g., all regular languages are CF, all CF languages are CS, etc. For technical reasons, we differentiate deterministic context-free (DCF) and nondeterministic context-free (NDCF) languages, since nondeterministic push-down automata (PDAs) can recognize some CF languages that deterministic PDA s cannot. We also consider (real-time) counter languages, which are recognized by finite automata with one or more (infinite) counters (or, equivalently, a PDA with one or more stacks and a single stack symbol). Counter languages are a proper superset of regular languages and a proper subset of CS languages (see Fig. 1).

In practice, learning to recognize a formal language by training a classifier on words and non-words is hard because there is, in general, no formal construction for generating a sufficient but finite set of negative examples. For this reason, we consider language transduction tasks, where the inputs and outputs form two individual formal languages, and the goal is to learn a deterministic function that maps a word from one language to the other. Concretely, a deterministic finite transducer, defined as a 6-tuple $(Q,\Sigma_{I},\Sigma_{O},\delta,q_{0},F)$, differs from a finite-state automaton in that its transition function $\delta:Q\times(\Sigma_{I}\cup\{\varnothing\})\rightarrow(\Sigma_{O}\cup\{\varnothing\})\times Q$ can output a symbol from the output alphabet $\Sigma_{O}$ (or the dummy token $\varnothing$) at every step. Thus, a transducer maps $w_{I}=a_{1}a_{2}\ldots a_{n}$ to $w_{O}=b_{1}b_{2}\ldots b_{n}$ if there exists a sequence of states $r_{0},r_{1},\ldots,r_{n}\in Q$ such that $r_{0}=q_{0}$, $(b_{i+1},r_{i+1})=\delta(r_{i},a_{i+1})$ for $i=0,\ldots,n-1$, and $r_{n}\in F$. The transducer outputs $b_{1}=\ldots=b_{k}=\varnothing$ while reading input word $w^{\prime}_{I}=a_{1}\ldots a_{k}\in\Sigma_{I}$ and outputs $w^{\prime}_{O}=b_{k+1}\ldots b_{n}\in\Sigma_{O}$ while reading dummy tokens $a_{k+1}=\ldots=a_{n}=\varnothing$. Transducers therefore define a deterministic function $f:\Sigma_{I}^{\ast}\rightarrow\Sigma_{O}^{\ast}$, given by $f(w^{\prime}_{I})=w^{\prime}_{O}$, between two formal languages, which is precisely what we want to learn. Thus, strictly speaking, we do not consider a hierarchy over formal languages but over language transduction tasks. Importantly, the machines required are identical to those in the Chomsky hierarchy, i.e., FSA s, PDA s, LBA s, and TM s (see Table 1), except that they can now also output values at each transition (i.e., the memory augmentations stay the same). We further discuss the transition from recognition to transduction, as well as prior approaches, in Section A.1.

Methods

For each task we define input and output languages $L_{I}$ and $L_{O}$, with their corresponding alphabets $\Sigma_{I}$ and $\Sigma_{O}$. The goal of a task is to learn the deterministic function $f$ that maps words $\bm{x}\in L_{I}$ to words $\bm{y}\in L_{O}$, i.e., language transduction. To that end, we consider models $p_{\theta}(\cdot|\bm{x})$ as conditional distributions over next possible sequence continuations (with parameters $\theta$). We one-hot encode the tokens in both languages $L_{I}$ and $L_{O}$ as vectors of length $|\Sigma_{I}|$ and $|\Sigma_{O}|$, respectively, denoting the corresponding $j$th entries of the $i$th one-hot tokens $x_{ij}$ and $y_{ij}$. We use gradient-based training to minimize the average cross-entropy loss, where $C(\bm{x},\bm{y}):=-\frac{1}{|\bm{y}|}\sum_{i}y_{i}^{T}\log p_{\theta}(\cdot|\bm{x})$ denotes the per-example loss (see Algorithm 1). Note that we do not use auto-regressive models, but rather append $|\bm{y}|$ empty dummy tokens to the input. Thus, the model will know when the input sequence $\bm{x}$ has terminated by reading the first empty token. We compute the per-sequence accuracy as the percentage of correctly predicted tokens, i.e., $A(\bm{x},\bm{y}):=\frac{1}{|\bm{y}|}\sum_{i}\mathds{1}\left[(\operatorname*{arg\,max}_{j}y_{ij})=(\operatorname*{arg\,max}_{j}p_{\theta}(\cdot|\bm{x})_{j})\right]$. Moreover, we compute the overall performance score as the per-sequence accuracy averaged over all sequences of unseen length. We run our experiments over 10 different network parameter initialization seeds and report the maximum score instead of the average, as this better indicates if an architecture is capable of learning the right algorithm at all (we provide the means and variances in Appendix B).

For each level of the Chomsky hierarchy, we define various sequence prediction tasks ranging from modular arithmetic (R) to binary addition (CS). We place the most emphasis on CS tasks as they are currently out of reach for state-of-the-art models and thus provide an ideal benchmark to guide future research on architecture design. We list the tasks in Table 2 and provide a full formalization in Table A.1. Although seemingly simple, these tasks are well-known examples in the theory of computation and concisely demonstrate the key properties of the grammars in the Chomsky hierarchy, i.e., counting, repetition, long-distance dependencies, and hierarchy. Note that the levels of our tasks are independent of the levels of $L_{I}$ or $L_{O}$ but correspond to the automata that can solve the corresponding transduction tasks. For example, for the Reverse String task, $L_{I}=L_{O}=\{a,b\}^{*}$, which are both regular. However, learning the function $f$ that maps $w\in L_{I}$ to $reverse(w)\in L_{O}$ requires a deterministic push-down transducer, thus rendering the task deterministic context-free.

We provide an open-source implementation of our models, tasks, and training and evaluation suite at https://github.com/deepmind/neural_networks_chomsky_hierarchy.

Results

In this section, we provide the results of our empirical evaluation. In Section 5.1 we relate the networks to the Chomsky hierarchy, in Section 5.2 we analyze the algorithms learned by the networks, and in Sections 5.3 and 5.4 we discuss the performance of LSTMs and Transformers in more detail.

We evaluate all architectures (defined in Section 4) on all tasks (defined in Table A.1) and show the generalization accuracy averaged over the segment $\mathcal{U}(N+1,M)$ (as described in Section 4) in Table 2. Furthermore, Fig. 2 displays the accuracy per sequence length for the best-performing model per architecture on three sample tasks (see Appendix B for the remaining tasks). As the test sequences have not been seen during training, we can gauge whether the architectures can learn the “correct” algorithm. We observe that the networks generally match the computational models associated with the Chomsky hierarchy: RNNs can solve tasks up to the regular level, Stack-RNNs up to the DCF level, and Tape-RNNs up to the CS level. However, the match is not perfect, as some architectures cannot solve tasks at their supposed level, e.g., Stack-RNN cannot solve Solve Equation (DCF) and the Tape-RNN cannot solve the (challenging) Binary Multiplication (CS) and Compute Sqrt (CS) tasks. This may be due to shortcomings in the architecture, the training protocol, or the particular difficulty of the tasks. For example, Solve Equation (DCF) is context-free but requires a nondeterministic FSA controller because it has to compute multiple modular arithmetic expressions for the different values of the unknown variable $x$ and compare their results to the actual solution of the equation, which is only provided at the end of the input sequence. Similarly, Binary Multiplication (CS) is a context-sensitive task but has a quadratic complexity, which is infeasible for the architectures we investigate. Conversely, some architectures show non-trivial performance on tasks beyond their supposed level, such as the Stack-RNN on Bucket Sort (CS) (more details in Appendix B). Finally, we observe that Transformers and LSTMs are not well-aligned with the Chomsky hierarchy: Transformers fail on regular tasks, while LSTMs can solve (counting) tasks more difficult than regular. We discuss both cases in detail below (Sections 5.3 and 5.4).

2 Analysis of learned program structure

To provide further evidence supporting the claim that some of the networks are able to learn the right algorithm, we now provide an analysis of solutions learned by some of our networks on our tasks, by investigating internal state representations and memory-update dynamics.

According to the Chomsky hierarchy, we expect networks that solve regular tasks to simulate a finite-state automaton. We investigate this hypothesis by analyzing the internal states of the RNN controller and checking whether they are finite (or form a finite number of clusters). Figure 3(a) shows a scatter plot of a PCA projection of the internal RNN states when trained on Parity Check (R). We observe that the states form four clusters, each representing one of the four values of the tuple (subsequence result, last token seen). In principle, one can solve this task with only two states, corresponding to the subsequence result: If the state is 1 and the input token is 1, move to state 0, otherwise stay in state 1, and finally output the state itself. However, due to the problem symmetry, the network also learns to compute the parity of the number of zeros in the string, therefore adding another two states to the computation. We also investigate whether and how Stack-RNNs use their stack for this task, which is unnecessary, in principle. Indeed, the Stack-RNNs only use no-op or pop (which is equivalent to no-op in the absence of push) actions, indicating that the RNN controller uses only a finite-state automaton and does not rely on the stack (see Section B.3 for more details).

On DCF tasks, we anticipate Stack-RNNs to use their stack. Indeed, on Reverse String (DCF), the networks learn the expected algorithm: push until an empty token appears, and then pop until the stack is empty. Moreover, the internal state of the controller seems to be largely guided by the last input token and not the last state (details in Section B.3). On Modular Arithmetic (DCF), which requires a stack to remember past results when entering a new bracket, the networks use the stack exactly as expected. Figure 3(b) shows that the Stack-RNN learns to solve this task by: (i) pushing the last result when a bracket is opened, (ii) not operating on the stack and only using its internal controller when a number or an operator is seen, and (iii) popping the last result from the stack when a bracket is closed. The top plot reports the probability of each action given an input, and the bottom plot shows the stack evolution along the sequence. On the bottom plot, the x-axis is the timestep and the y-axis is the cell position in the stack (top of the stack on the bottom). Each cell is colored according to the first principal component of its actual content.

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

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$ at position 0 will no longer be considered the same as the same token $x$ at position 10. As described in Section 4, we evaluate five encodings (none, $\sin$/$\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).

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

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.

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.

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

References

Appendix A Experimental details

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 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$ and the stack size to $128$ and manually increase their sizes when testing on longer sequences. Thus, as these memory sizes are significantly larger than the training range $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).

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

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.

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; 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}$ symbols. We did not use the unnormalized actions as suggested in (DuSell & Chiang, 2022).

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

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.

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_{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).

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.

A vanilla CNN, consisting of 5 convolutional layers with 32 channels each and a final MLP that produces the task output(s). We compute 2D convolutions over the time and (one-hot encoding) channel dimension. That is, the first kernel will consider the entire one-hot encoding at once for every time step. For all other kernel dimensions (time and filters), we sweep over the values $\{3,5,7,11\}$.

A.3 Tasks

Here, we describe our tasks (listed in Table A.1) in more detail. As mentioned in Section 4, all tasks consist of an input sequence $\bm{x}\in L_{I}$ from which the models have to predict the target sequence $\bm{y}\in L_{O}$. We append $|\bm{y}|$ empty tokens $\varnothing$ to the input sequence, such that the models can process the entire input sequence before having to produce the output (i.e., they know the input length before having to produce the output). Note that half of our tasks have an output length of 1 and are thus just standard classification tasks with the set of classes being the alphabet of the output language. The networks still see one empty token $\varnothing$ at the end of the input string to signify that the input phase has finished and that the output must be computed. We do not consider NDCF tasks since the distinction between DCF and NDCF is fairly technical and does not fundamentally change the type of memory structure required (i.e., a stack).

Given a binary sequence, e.g., $\bm{x}=aabba$, compute if the number of $ab$s and $ba$s is even. For $aabba$, we have one $ab$ and $ba$, meaning that the total number is 2 and thus even, i.e., $\bm{y}=b$ (where we arbitrarily equate odd with $a$ and even with $b$). This task is equivalent to computing whether the first and last character of the string are equal. Therefore, the task is regular since we can solve it with a 2-state finite-state machine that looks at the first bit of the sequence and compares it with the last one.

Given a sequence of numbers in $\{0,1,2,3,4\}$ and operations in $\{+,-,\cdot\}$, compute the result modulo 5. For example, $\bm{x}=1+2-4$ evaluates to $\bm{y}=4$. Note that the length of the input sequences must be of odd. Therefore, if we sample an even length during the training/evaluation process, we return an input sequence of this length plus 1. This task is regular since we can solve it with a 5-state finite-state machine, which transitions for each new operation with the state being equal to the current result.

Given a binary string, e.g., $aaabba$, compute if the number of $b$s is even. The sequence $\bm{x}=aaabba$ contains 2 $b$s, which is even, i.e., $\bm{y}=b$ (where we arbitrarily equate odd with $a$ and even with $b$). This task is regular since we can solve it with a 2-state finite-state machine, which transitions every time it sees a token different from its current state.

Given a sequence of movements on a cycle of length 5, compute the end position. The movements are STAY, INCREASE, DECREASE and are represented as $\{0,1,2\}$. The agent always starts at position 0. For example, $010211$ means the agent stops at position $0+0+1+0-1+1+1$ = $2$, and the output class is $2$. This task is regular since we can solve it with a 5-state finite-state machine, similar to Modular Arithmetic (Simple) (R), as the task can be converted into a sum modulo 5.

Given a sequence of numbers in $\{0,1,2,3,4\}$, brackets, and operations in $\{+,-,\cdot\}$, compute the result modulo 5. For example, the sequence $\bm{x}=-(1-2)\cdot(4-3\cdot(-2))$ evaluates to $\bm{y}=0$. Note that we do not have the same problem of odd lengths as in Modular Arithmetic (Simple) (R), since we can use substrings of the form $(-z)$ with $z\in\{0,1,2,3,4\}$, which have length 4 and thus can be used to produce input strings of even length. The task is DCF since we can solve it with a 5-state finite-state machine and an external stack. That is, similar to the Modular Arithmetic (Simple) (R) task, the finite-state machine transitions for each new operation, with the state being equal to the current result. Moreover, the stack is used to handle brackets: The machine pushes if the current input token is an opening bracket, pops if it is a closing bracket, and uses no-ops to let the finite-state machine work otherwise.

Given a binary string, e.g., $\bm{x}=aabba$, compute its reverse, i.e., $\bm{y}=abbaa$. The task is DCF since we can solve it by pushing the tokens of the input sequence on a stack until the first empty token $\varnothing$ appears and then popping the tokens from the stack, outputting the values one by one. This task cannot be solved with a finite-state machine since the number of possible outputs is infinite.

Given an equation consisting of numbers in $\{0,1,2,3,4\}$, brackets, operations in $\{+,-,\cdot\}$, and an unknown variable $z$, compute the value of $z$ such that the equation holds modulo 5. For example, $\bm{x}=-(z-2)\cdot(4-3\cdot(-2))=0$ modulo 5 holds for $z=1$, i.e., $\bm{y}=1$. This task is DCF since we can solve it by simulating all possible values of $x$ in a nondeterministic finite-state machine and producing each result using the same algorithm as in Modular Arithmetic (DCF). Note that a nondeterministic finite-state machine can be simulated with a deterministic one, implying that this task is DCF and not NDCF.

Given a binary string representing a stack’s content (given bottom-to-top) and a sequence of push $a$, push $b$, or pop actions, execute the actions on the stack and return the final stack content (in a top-to-bottom manner, i.e., as if popping the resulting stack). For example, executing the sequence pop push $a$ pop on the stack $abbaa$, i.e., \bm{x}=abbaa~{}\textsc{pop}{}~{}\textsc{pusha}{}~{}\textsc{pop}{}, results in $\bm{y}=abba$. If a pop action is called on an empty stack, the action is ignored. This task requires stack manipulation by design and is therefore DCF.

Given two binary numbers, e.g., $10010$ and $101$, compute their sum in base 2, i.e., $\bm{y}=10111$ for $\bm{x}=10010+101$. The inputs and outputs are given in little-endian representation. The task is CS since it exhibits cross-serial dependencies because the two numbers are provided one after the other (and not bit-by-bit at the same time).

Given two binary numbers, e.g., $100$ and $10110$, compute their product in base 2, i.e., $\bm{y}=1011000$ for $\bm{x}=100*10110$. The inputs and outputs are given in little-endian representation. The task is CS since it exhibits cross-serial dependencies because the two numbers are provided one after the other (and not bit-by-bit at the same time).

Given a binary number, e.g., $101001$, compute the floor of its square root, i.e., $\bm{y}=\lfloor\sqrt{101001}\rfloor=101$. The inputs and outputs are given in little-endian representation. This task is CS since the digit-by-digit algorithms to compute the integer square root require many sequence manipulations, including binary multiplications, which is a CS task.

Given a binary string $t_{1}...t_{n}$, output $t_{1}t_{3}t_{5}...t_{2}t_{4}t_{6}...$. For example, the output corresponding to $\bm{x}=aaabaa$ is $\bm{y}=aaaaba$. The task is CS because it exhibits cross-serial dependencies (the output is the interleaved input).

Given a string over an alphabet of fixed size (5 in our case), return the sorted string. Since the alphabet has a fixed size, the task can be solved via bucket sort, which only requires a finite amount of counters (i.e., 5 counters in our case). For example, the output corresponding to $\bm{x}=421302214$ is $\bm{y}=011222344$. The task is CS because it requires multiple counters that keep track of the number of occurrences for every token.

A.4 Problem setup

A.5 Computational resources

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}$, 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$. 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

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\%$) 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 $\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

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

The transformer achieves a non-trivial generalization score ($61.9\%$ with baseline $20\%$) on the Cycle Navigation (R) task but it does not ‘solve’ the task (in terms of our definition of score $\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$ and yellow for $0.5$ (not $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\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).

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.

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$ where $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\}$ (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; 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 $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.

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

To provide a more detailed empirical result, we train the transformer encoder with relative positional encodings for increasing numbers of in-distribution data points ($100\,000$, $1\,000\,000$, and $10\,000\,000$ training steps) and increasing numbers of layers (5, 10, 15, 20, 25). Table B.6 shows that the score, i.e., the accuracy averaged over all (unseen) test lengths and maximized over 10 seeds and 3 learning rates, generally does not increase with more training data or more parameters. Thus, in this empirical setup, the Chomsky hierarchy implies a hard limit on scaling laws (Kaplan et al., 2020).