Neural Networks and the Chomsky Hierarchy
Authors: Gregoire Deletang
Anian Ruoss
Jordi Grau-Moya
Tim Genewein
Li Kevin Wenliang
Elliot Catt
Chris Cundy
Marcus Hutter
Shane Legg
Joel Veness
Pedro A Ortega
Venue: ICLR 2023 notable top 25% (2023)
Keywords: length generalization
memory-augmented neural networks
recurrent neural networks

Abstract: Reliable generalization lies at the heart of safe ML and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in the field. In this work, we conduct an extensive empirical study (20'910 models, 15 tasks) to investigate whether insights from the theory of computation can predict the limits of neural network generalization in practice. We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.

Published as a conference paper at ICLR 2023
NEURAL NETWORKS AND THE CHOMSKY HIERARCHY
Grégoire Delétang") Anian Ruoss" Jordi Grau-Moya' Tim Genewein' Li Kevin Wenliang
Elliot Catt Chris Cundyla Marcus Hutter* Shane Legg* Joel Veness Pedro A. Ortega
ABSTRACT
Reliable generalization lies at the heart of safe ML. and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in the field. In this work, we conduct an extensive empirical study (20 910 models, 15 tasks) to investigate whether insights from the theory of computation can predict the limits of neural network generalization in practice. We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of- distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTTSs can solve regular and counter- language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.
INTRODUCTION
Statistical learning theory is the most widely used theory of generalization in practical machine learning, justifying empirical risk minimization and estimating the generalization error via a test set (Vapnik 1998). However, its central assumption that training and test data are independent and identically distributed (i.i.d.) is violated for many problems of interest (distribution shifts, continual learning, etc.). An example of such a non-i.i.d. setting is testing generalization on sequence prediction problems, where agent is trained with sequences of length E N and tested with arbitrarily longer sequences f >> N. This problem is of particular importance since it subsumes all computable problems (Dawid) 1984 Rich 2007 (Sisse 1997. [Solomonofi 2009 2010). Central sequence prediction is inductive inference, which consists of deriving a general rule from finite set of concrete instances and using this rule to make predictions. For example, in program induction (Goldberg
1989, Gomez et al. 2008 Holland| 1992, Liang et al. 2013; Nordin 1997; Solomonotf 1964a b
Wineberg & Oppacher] 1994), the goal is to obtain a model that correctly identifies the underlying data- geta-generating process given examples of input-output sequences. Then, if the model is correct, it can produce results in accordance with the generative process for previously unseen input sequences.
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, has infinitely many possible continuations. Thus, any principle that selects particular continuation requires additional assumptions that are independent of the data, i.c., 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 vast number of approaches for designing inductive biases via architectural and training protocol changes (see Battaglia lia et al. (2018) for an overview). However, the problem is that stronger inductive biases generally come at the cost of decreasing the universality of model, and thus finding good balance between the two is one of the biggest challenges in the contemporary literature.
Even if neural architecture is theoretically universal Turing complete, gradient-basee training, which cannot exhaustively search the parameter space, can impede finding the right solution and thus
"quual contribution. Correspondence to [gdelt, anianr) ) @ @deepmind.com. DeepMindd "ttanford University. Work performed while the author was DeepMind.

---

Published as a conference paper at ICLR 2023
infinite tape
recursively enumerable
context-eemidive
TapeoNNN
tape
deterministic context-free
regular
stack
INN
funite
finite-state
controller
counter
LSTM
Figure 1: Formal language classes and their correspondence with neural network architectures. Left: Our empirical evaluation locates the architectures on the hierarchy of formal language classes. Right: Each formal language class is associated with a minimal computational model (automaton) to recognize or generate the language (see Section B All automata have finite-state controller at their core, in addition increasingly restrictive memory access we descend the hierarchy.
practically render the model non-universal. Therefore, both architectural and training limitations impact which sequence prediction problems 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 the hierachy and can solve all computable problems. However, unlike for classical automata, unified placement of neural architectures on the Chomsky hierarchy has not yet been practically established, which is precisely the goal our work.
This work We conduct 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 practice (see Fig. for 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) 2erril]]2019]] Weiss et al. 2018) showed that RNNs lie much lower on the Chomsky hierarchy. To complement these theoretical analyses, we conduct large-scale empirical evaluation on sequence prediction problems. We make the following main contributions:
[020|Merril]]]
We conduct an extensive generalization study (20910 models, 15 tasks) of state-of-the- tfrttrr neural network architectures (RNN, LSTM, Transformer) and (Stack-RNN, Tape-RNN) on a battery of sequence requence-prediction tasks spanning the entire Chomsky hierarchy that can be practically tested with finite-time computation.
networks
We open-source a length generalization benchmark dhttps://gi newra rks chomsky hierarchy) that is out of reach for of-h--oft quence prediction models and allows us to pinpoint the failure modes of these architectures.
com deoomnde
We show how increasing amounts training data do not enable generalization on our tasks higher 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 the hierarchy.
2 RELATED WORK
Learning formal languages A long line work has empirically investigated whether common machine learning architectures, including RNNs (Elman 1990), GRUs (Cho al. 2014), SCNs (Giles et al. 1992 Pollack 1991), LSTMs (Hochreiter & Schmidhuber 1997). and Transformers (Vaswani al. 2017 capable of learning formal languages. The main insights are: These networks can
2

---

Published as a conference paper at ICLR 2023
learn simple counting languages (Hölldobler et al. 1997 Steijvers & Grünwald, 1996; Wiles &
Elman [1955] Rodriguez& & Wiles 1997) and the Dyck- language (Skachkova et al. 2018 Suzgun
et al.. (0019). 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"b" but in a very limited
way, i.c., they generalize only to lengths close to those seen during training (Bodén & Wiles 2000 2002 Gers & Schmidhuber, (200T). Similarly, Transformers cannot learn Dyck-n languages for > 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. (022). 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.
Neural networks and the Chomsky hierarchy It was theoretically shown that RNNs and Trans- formers are Turing complete (Chen al., 2018: Pérez et al., 2019, 202T 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 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 strietly more powerful since they can learn counting mechanism (i.e., are k-counter machines). Moreover, it was theoreti- cally 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) al. 202T). However, this approach only upper-bounds the capabilities of a model and does not provide any insight on whether madientt-bssed methods will find parameters that can solve 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.
popular approach for augmenting neural architectures with external memory is to equip recurrent network with read and write access to differentiable memory
Memory-augmented networks
structures, such as deterministic stacks (Das et al.. 1992a b
Grefenstette et al.
2015
Hao et al. 2018
Joulin & Mikolov 2015] Mali et al. | & Das 3922[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. (016)), and memory matrices (Graves) jet al. 2014 2016 Gülçehre et 20.180188 Yang Rush 2017). Such memory-augmenter networks capable of recognizing complex languages, including tasks like copying reversing strings, but they can only perform one computation step per input token. Thus, to solve superlinear tasks (c.g.. binary multiplication), memory memory-augmente -ugmeeted networks also need to be able perform 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 al. 2016). We also consider memory- augmentd networks and find that memory structures are necessary to generalize on sequence prediction problems higher up the Chomsky hierarchy.
3 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, generating arbitrarily long sequences that all exhibit the same structure. To that end, we will consider sequences elements of infinite formal languages, which are generated by a grammar.
need a way of
3

---

Published as a conference paper at ICLR 2023
Table 1: Chomsky hierarchy grammar types, their corresponding minimal automata and memory structures required for language recognition or generation, their production rules, and the correspond- ing example languages from Section 3] The production rules symbols are defined as: a terminal; A, B non-terminal; 0, 3, y string of terminals and/or non-terminals (ax, 3 can be empty, but not 7)
Grammar by (low - high)
Automaton
Memory
Production rules
Example
Regular (R)
Finite-state autornatin (FSA)
Automaton state
+ a aB
Context-free (CF)
Push-down automaton (PDA)
+ infinitc stack toaly top entry accessibic)
A - c
B
Context-sensitvve (CS)
Lincar bounded automaton (LBA)
bounded tape (all entries accessible)
aA3 and
Recursively coumerable (RE)
Turing machine (TM)
infinite tape (all catries accessible)
7 - a
Formal language A formal language L is set of words, where each word is a finite string of symbols drawn from finite alphabet E. For example, with binary alphabet E = {0, 1} we can describe the following infinite languages: A = f00''" n. m > 0}. B = w w is a palindrome). C' = [ww] a word], and D [w] w describes terminating Turing machine).
Generative 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. distinctive start symbol. and finite set of production rules that map from non 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 e 0 | 1
OPO 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 D. For example, B is not regular, since the right-hand side contains variable enclosed by two terminal symbols, but context- context-free, since the left-hand side consists of a single nonterminal symbol.
Recognizing language An automaton recognizes a language if it accepts all strings in the language and no others. For example, (deterministic) finite-state automaton finite-state automaton (FSA) can be defined as a 5-tuple (Q, Σ, 6, qo, F), consisting of a finite set of states Q, the finite alphabet Σ, a transition function d Q x Σ + Q, an initial state qu E Q, and set of accept states F C Q. Thus, an FSA accepts a string w = 01 Tu, :.. Pn E Q such that re qu. Ti+1 6(r,, a.+1) for i O.....
On over the alphabet Σ if there exists a sequence of states
1, and rn 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 the automaton that can recognize it (see [a. All automata in the hierarchy have 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- (DCF) and nondeterministic context-free (NDCF) languages, since nondeterministic push- automata (PDAs) can recognize some CF languages that deterministic PDAs cannot. We also consider (real- time) counter languages, which are recognized by finite automata with one or more (infinite) counters (or, cquivalently, a PDA with one or more stacks and a single stack symbol). Counter languages are a proper superset of regular languages and proper subset of CS languages (see Fig,
Transduction vs. recognition In practice, learning to recognize a formal language by training a classifier on words and non-words is hard because there is, in general, 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 Iearn a deterministic function that maps a word from one language to the other. Concretely, a deterministic finite transducer, defindd as 6-tuple (Q, E,, Eo, 5, qo. F), differs from a finite-state automaton in that its transition function 5 Q x (E, (Ø)) + (Eo U (Ø]) x Q can output a symbol from the output alphabet Lo (or the dummy token Ø) at every step. Thus, a transducer maps wy = a102... ... On to wo = b biby...b. bn if there exists a sequence of states ro, Tl,...,, .n E Q such that Fo = qu. (be41, T(t1) = 8(r,, a;+1) for = 0, O..... n - 1, and Fn E F. The transducer outputs bi ... by 2 while reading input word w/ 01 ... ak Σ₁ and outputs wo by-1... b, E Eo while reading dummy tokens a++1 = = a, = Ø. Transducers therefore define deterministic function f EJ - Eg given by f(w() w/- between two formal languages, which
...b,
4

---

Published as a conference paper at ICLR 2023
is precisely what we want to learn. Thus, strictly speaking, we do not consider hierarchy over formal languages but over language transduction tasks. Importantly, the machines required are identical to those in the Chomsky hierarchy, i.e., FSAs, PDAs, LBAs, and TMs (see Table D 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, well as prior approaches, in Appendix A.1
4 METHODS
Problem setup For each task we define input and output languages L1 and Lo, with their corre- sponding alphabets Σn and Co. The goal of task is to learn the deterministic function f that maps words æ E I,, to words y E T.o, i.e., language transduction. To that end, we consider models po as conditional distributions over next possible sequence continuations (with parameters 0). We one-hot encode the tokens in both languages L and Lo as vectors of length |اكز| and [ool] respectively, denot- ing the corresponding jth entries of the ith one-hot tokens Zij and Yıj. We gradient-based training to minimize the average cross-entropy loss, where C(ær, y) =- Tyv Σ, of log (-12r) denotes the per-example loss (see Algorithm A. Note that do not auto-regressive models, but rather ap- pend yy empty dummy tokens to the input. Thus, the model will know when the input sequence æ has terminated by reading the first empty token. We compute the per-sequence accuracy as the percentage of correctly predicted tokens, i.e., A(x, y) == l Σ, Il (arg max, Miy) (arg max, (o(1(=);)] 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).
Tasks 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 state-of-the of-the-art models and thus provide an ideal benchmark to guide future research on architecture design. We list the tasks Table 2 and provide a full formalization in Table A. Although seemingly simple, these tasks are well-known examples in the theory of computation and concisely demonstrate the key propertics of the grammars in the Chomsky hierarchy, i... counting, repetition, long-distant tasks are independent of the levels of L, or Lo but correspond to the automata that can solve the corresponding transduction tasks. For example, for the Reverse String task, L1 = Lo fa, b)*, which are both regular. However, learning the function ʃ that maps w E L1 to reverse(w) E Lo requires deterministic push-down transducer, thus rendering the task deterministic context-free.
dependencies, and hierarchy. Note that the levels of our
Architectures We consider a wide range of neural network architectures, including both ot the-art and memory-augmenter model per level of the Chomsky hicrarchy. To that end, we use a standard RNN as a controller and augment it with two kinds of differentiable memory structures: a deterministic stack and a bounded tape. The stack and tape have elements in IRd with d = 8, and we ensure that the stack and tape sizes large enough to simulate infinite memory during training and testing. The Stack-RNN (Joulin & Mikolov| 2015) can perform any linear combination of PUSII, POP, and NO-OP operations on the stack. The RNN, which is inspired by the Baby- (Suzgun et al. 2019b), can perform any linear combination of WRITE-LEFT, WRITE-RIGHT, WRITE-STAY, HUMP-RIGHT JUMP-LEFT (details in Appendix AA.. In addition these ceanory-augmented models, we also evaluate LSTMs (Hochreiter & Schmidhuber 1997) and Transformers (Vaswani et al. 2017). We compute the Transformer output from the encoder only model that overlooks the whole input sequence. We consider five different positional encodings: none, classical sin/cos (Vaswani et al. (017). the rotary positional encodings (RoPE) (Su et al.) 2021). ALiBi (Press et al. (202I) and the relative positional encodings of Transformer-XL. (Dai et al. 2019). The latter two have been shown to allow extrapolation to longer sequences on some language modeling tasks. All models receive the tokens x as an input and are expected to produce the output y (i.e., we do not feed the output back to the input unlike sequence-to- sequence models (Sutskever et al. 2014)). We study CNNs, Stack-LSTMs, NDStack- RNNNs (DuSell & Chiang 2020 2022). and autoregressive versions of our models in Appendix B
models (full details in Appendix [.2]). Our goal is to have at least one
5

---

Published as a conference paper at ICLR 2023
Table 2: Score (in percentage, see Section 4). i... accuracy averaged over all lengths and maximized over 10 random seeds (and other hyperparameters, see Appendix A We consider model to generalize successfully (bold) if its score 2 90%. The random accuracy is 50% (except for Cycle Navigation (R), Bucket Sort (CS), and the two modular arithmetic tasks where it 20%). We observe that, general, RNNs with more permissive memory structures can solve more challenging tasks. We denote permutation-invariin tasks with i, counting tasks with tasks requiring a nondeterministic controller with o, and tasks requiring superlinear running time with x.
Level
Task
RNN
Stack-RNN
Tape-RNN
Transformer
LSTM
Even Pairs
100.0
100.0
100.0
96.4
100.0
Modular Arithmetic (Simple)
100.0
100.0
100.0
24.2
100.0
Parity Check!
100.0
100.0
100.0
52.0
100.0
Cycle Navigation
100.0
100.0
100.0
61.9
100.0
Stack Manipulation Reverse String Modular Arithmetic Solve Equation"
56.0
100.0
100.0
57.5
59.1
62.0
100.0
100.0
62.3
60.9
DCF
41.3
59.2
51.0
56.2
64.4
25.7
67.8
Duplicate String
50.3
52.8
100.0
52.8
57.6
Missing Duplicate
52.3
$5.2
100.0
56.4
54.3
Odds First Binary Addition
51.0
51.9
100.0
52.8
55.6
CS
50.3
52.7
100.0
55.5
Binary Multiplication"
50.0
52.7
58.5
52.2
53.1
Compute Sqrt Bucket Sorti*
54.3
56.5
57.8
52.4
57.5
27.9
78.1
70.7
91.9
99.3
Taanfoomer
0.9
RNN
Stace-Po RNN
Eon
Tase ANN
0..74
0.7
LSTM
0.8-
0.4-
8.6
1.0
200
300
400
500
100
200
300
400
0.5
100
200
300
400
500
(a) Parity Check (R)
(b) Modular Arithmetic (DCF)
(c) Duplicate String (CS)
Figure 2: Performance curves three tasks. The dashed vertical red line is the training range, mean- ing that sequences to the right have not been seen during training and thus measure generalization.
Data generation Instead of using fixed-size datasets, we define training and test distributions from which we continually sample sequences. We define the maximum training sequence length the training range N, with N = 40. Every mini-batch generated by first sampling a length from the uniform distribution 74 (V, and then sampling sequences length l from the task's generative grammar. For testing, we sample the sequence length from U(N + 1, M), with M = 500.
We provide an open-source implrntttionnnnnnnnneeetttooonno of models, tasks, and training and evaluation suite http:///httt...cceeeeee///r///rt
RESULTS
In this section, provide the results of our empirical evaluation. In Section 5.1 we relate the networks to the Chomsky hierarchy, in Section[.22we analyze the algorithms learned by the networks, and in Sections 5.3 and 5.4 we discuss the performance of LSTMS and Transformers more detail.

---

Published as a conference paper at ICLR 2023
contenes
Widead by shice artion ser Hour tikes
MORTHL
64
Stack osiiztan
13- c1 (61))
(a) Internal RNN states Parity Check (R), col- ored by the previous state and the current input.
(b) Stack-RNN action proba- bilities (above) and stack val- ues (below) on Modular Arithmetic (DCF) task.
(c) Tape-RNN action probabilities and memory values on Duplicate String (CS).
Figure 3: Analysis of the internal representations and memory dynamics of an RNN on regular task, a Stack-RNN on DCF task, and a Tape-RNN on CS task. The reverse-engineede network mechanisms are indicative of the correct algorithms that solve the corresponding tasks.
5.1
MAIN RESULT
We evaluate all architectures (defined in Section on all tasks (defined in Table A. and show the generalization accuracy averaged over the segment ((N + .)) (as described in Section 4 in Table Furthermore, Fig. displays the accuracy per sequence length for the best- best-performing model per architecture on three sample tasks (see Appendix B for the remaining tasks). As the test sequences have 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 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 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, So 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 and compare their results to the actual solution of the equation, which is only provided at the end of the input sequence. Similarly, Binary Multipl teitlipplition (CS) is a context-sensitive task but has quadratic complexity, which is infeasible for the architectures we investigate. Conversely, some architectures show non-trivial performance on tasks beyond their supposed level, such the Stack-RNN on Bucket Sort (CS) (more details in Appendix BB. 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.
5.2 ANALYSIS OF LEARNED PROGRAM STRUCTURE
To provide further evidence supporting the claim that some the networks are able to learn the right algorithm, now provide an analysis of solutions learned by some of our networks on tasks, by investigating internal state representations and memory-update dynamics.
Regular tasks 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 3a shohsws 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: the state 1 and the input token is 1, move to state O, 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
7

---

Published as a conference paper at ICLR 2023
stack for this task, which is unnecessary, in principle. Indeed, the Stack-RNNs only use NO-OP POP (which is equivalent to NO-OP in the absence of PUSH) actions, indicating that the RNN controller uses only a sinite-state automaton and does not rely on the stack (see Appendix B.3 for more details).
Deterministic context-free tasks On DCF tasks, we anticipate Stack-RNNs to use their stack. Indeed, on Reverss 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 Appendix [B.3] On Modular Ari writhmetic c (DCF), which requires stack to remember past results when entering new bracket, the networks use the stack exactly as expected. Figure Bboshows that the Stack-RNN learns to solve this task by: (i) pushing the last result when 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 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.
Context-sensitive tasks In contrast to the RNN and Stack-RNN, the reverse-engineere network mechanisms for the Tape-RNN are less interpretable. Neverthless, Fig. 3c shows that the Tape- RNN has learned an algorithm that is indicative of the data-generating grammar of the Duplic cate String (CS) task. The input to the network consists of the sequence a, a, b, of length followed by 2 a-symbols that the RNN can use to compute and manipulate the tape, followed by 28 3-symbols used output the result (i.e., the sequence a, a, b, a, a, a, b, a of length 26). The panels show the action probabilities and memory contents over time. We observe that up to time / = 5 the RNN writes the memory with WRITE-LEFT. Then, time-step 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-RIGIIT on time-step 7. After this, the RNN idles using WRITE-STAY until reaches the first 3-symbol, whereupon it starts outputting the result using WRITE-LEFT actions.
4.
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 strictly more powerful than RNNs because they can also solve counting tasks (Bodén & Wiles 2000 2002 Gers & Schmidhuber] 2001 Merrill 2019 Weiss 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-sensstive. 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 two-counter machine (Minsky (9677.. However, finding an architecture that solves non-regular tasks with counters via gradient descent is more difficult than when the controller has access to more permissive memory structure, such as a stack or 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 global attention mechanism. As 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 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-X XL) and report the best-performing variant.
Indeed, Table 2 shows that Transformers are most successful on permutation-invarian 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 germutation-ivvariantt 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. 4a for the
8

---

Published as a conference paper at ICLR 2023
1.
None ALB Tarabmennt
Longth 150
Refd
0.5
100
202
300
602
Sequince lengi
(a) Accuracy per length by positional encoding.
(b) First layer activations (PCA) by sequence length.
Figure 4: Transformers on Reverse String (DCF). Without positional encodings, Transformers
are permutation invariant, and with encodings, positions are out-of-distribution for longer sequences.
different positional encodings Reverse String (DCF) and Fig. B.7 for the remaining tasks). In particular, Transformers are unable to solve all permutation-invarian tasks (i.e., Parity Check (R), which is 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. 4b 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 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 sequence prediction viewpoint, using formal language theory to establish the computational complexity of each task. Naturally, we had to choose maximum test sequence length for evaluations, which theoretically renders all of our input and output languages finite. However, our sequences share the structure an infinite language, allowing us measure generalization by testing on input sequences that are significantly longer than those seen during training (and are thus nu--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 slight degradation of the accuracy as the test length increases. This a result of implementing finite state machines and memory updates with neural network trained via SGD: Even slight numerical inaccuracies in state- taate-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 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 al. (020): Even significantly increasing the amount of training data and the size of Transformer are insufficient for it to "climb the Chomsky hiearchy"'
7 CONCLUSION
We leveraged the theory of computation 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- architectures, such LSTMs and Transformers, cannot solve seemingly simple tasks, such as duplicating a string, when evaluated on sequences that significantly longer than those seen during training. Moreover, models interacting with an external memory structure, such as a stack or a finite tape, can climb the Chomsky hierarchy, indicating promising direction for improvements in architecture design.
showed that

---

Published as a conference paper at ICLR 2023
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. [T) that an architecture could solve. Similarly, we the same level of the hierarchy that architecture
cannot guarantee that tasks exist lower cannot solve. Moreover, without extracting and analyzing the automata implemented by the networks, cannot strictly claim that architectures generalize to arbitrary-length inputs, up to a maximum length. Finally, our results are w.r.t. our precise experimental setting, i.c., if an architecture fails generalize we cannot guarantee that no weight configuration would solve the task; we were simply unable to find such configuration with our training protocol.
only test
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.
REFERENCES
Joshua Ackerman and George Cybenko. survey of neural networks and formal languages. CoRR, 2020.
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay V. Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur, Exploring length generalization in large language models. CoRR, 2022.
Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Claudio Fantacei, Jonathan Godwin, Chris Jones, Tom Hennigan, Matteo Hessel, Steven Kapturowski, Thomas Keck, lurii Kemaev, Michael King, Lena Martens, Vladimir Mikulik, Tamara Norman, John Quan, George Papamakarios, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Wojciech Stokowiec, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL http://github. http:gghhhuu..oodeemm..... com/deepmnnd
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. 3rd International Conference on Learning Representations, 2015.
Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to End-to-end algorithm synthesis with recurrent networks: Logical extrapolation without overthinking. CoRR, 2022.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre. H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew M. Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, 2018
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020.
Mikael Bodén and Janet Wiles. Context-free and context-sensitive dynamics in recurrent neural networks. Connect. Sci., 2000.
Mikael Bodén and Janet Wiles. On learning context-frie frreett-eeeeeee and context-sensitive languages. 1EEE Trans. Neural Networks, 2002.
10

---

Published as a conference paper at ICLR 2023
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
httpp://githb..co htt.g/thhw..ccooogggg/////aaa/ae
Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. Recurrent neural networks weighted language recognizers. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2018.
David Chiang and Peter Cholak. Overcoming theoretical limitation of self-attention, 2022. URL https://arxiv wrgp http://aarxxi.oorra//2222..
12172
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, 2014.
Noam Chomsky. Three models for the description of language. IRE Trans. Inf. Theory, 1956.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G. Carbonell, Quoc Viet Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Conference of the Association for Compulational Linguistics, 2019.
Ivo Danihelka, Greg Wayne, Benigno Uria, Nal Kalchbrenner, and Alex Graves. Associative long short-term memory. In Proceedings of the 33nd International Conference on Machine Learning, 2016.
Sreerupa Das, Lee Giles, and Guo-Zheng Sun. Learning context-free grammars: Capabilities and limitations of a recurrent neural network with an external stack memory. In Fourteenth Annual Conference of the Cognitive Science Society, 1992a.
Sreerupa Das, Lee Giles, and Guo-Zheng Sun. Using prior knowledge in NNPDA learn context-free languages. In Advances in Neural Information Processing Systems 5, 1992b.
A. Philip Dawid. Present position and potential developments: Some personal views: Statistical theory: The prequential approach. Journal of the Royal Statistical Society. Series A (General), 1984.
Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack mns. In Proceedings of the 24th Conference on Computational Natural Language Learning, 2020.
Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nondeterministic stacks. In The Tenth International Conference on Learning Representations, 2022.
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize dyck-n languages? Findings of the Association for Computational Linguistics, 2020.
Jeffrey L. Elman. Finding structure in time. Cogn. Sci., 1990.
Karlis Freivalds and Renars Liepins. Improving the neural GPU architecture for algorithm learning. CORR, 2017.
Felix A. Gers and Jürgen Schmidhuber. LSTM recurrent networks learn simple context-free and context-sensitive languages. IEEE Trans. Neural Networks, 2001.
C. Lee Giles, Clifford B. Miller, Dong Chen, Hsing-Hen Chen, Guo-Zheng Sun, and Yee-Chun Lee. Learning and extracting finite state automata with recond-orde recurrent neural networks. Neural Comput., 1992.
David E. Goldberg. Genetic Algorithms in Search Optimization and Machine Learning. Addison- Wesley, 1989.
Faustino J. Gomez, Jürgen Schmidhuber, and Risto Müikkulaienn. Accelerated neural evolution through cooperatively coevolved synapses. J. Mach. Learn. Res., 2008
11

---

Published as a conference paper at ICLR 2023
Alex Graves. Adaptive computation time for recurrent neural networks. CoRR, 2016.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. CoRR, 2014.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gomez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John P. Agapiou, Adrià Puigdomènech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using neural network with dynamic external memory. Nat., 2016.
Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In Advances in Neural Information Processing Systems 28, 2015.
Çaglar Gülçehre, Sarath Chandar, Kyunghyun Cho, and Yoshua Bengio. Dynamic neural turing machine with continuous and discrete addressing schemes. Neural Comput., 2018.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 2020.
Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, and Simon Mendelsohn. Context-free transductions with neural stacks. In Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018.
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. CoRR, 2022.
Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. Haiku: Sonnet for JAX, 2020. URL httpp://github.....//// coom/deemiindddmm -aikuu
Matteo Hessel, David Budden, Fabio Viola, Mihaela Rosca, Eren Sezener, and Tom Hennigan. Optax: composable gradient transformation and optimisation, in jax!, 2020. URL UtL/htt::/giituubcoo com/ frepmind/optax
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 1997.
John H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, 1992.
Steffen Hölldobler, Yvonne Kalinke, and Helko Lehmann.
Designing a counter: Another case study of dynamics and activation landscapes in recurrent networks. In Advances in Artificial Intelligence, 21st Annual German Conference on Artificial Intelligence, 1997.
Armand Joulin and Tomás Mikolov. Inferring algorithmic patterns with atack-augmented recurrent nets. In Advances in Neural Information Processing Systems 28, 2015.
Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In 4th International Conference Learning Representations, 2016.
Nal Kalchbrenner, Ivo Danihelka, and Alex Graves. Grid long short-term memory. In 4th International Conference on Learning Representations, 2016.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, 2015.
Samuel A. Korsky and Robert C. Berwick. On the computational power rnns. CoRR, 2019.
Karol Kurach, Marcin Andrychowicz. and Ilya Sutskever. Neural random-access machines. In 4th International Conference Learning Representations, 2016.
12

---

Published as a conference paper at ICLR 2023
Percy Liang, Michael I. Jordan, and Dan Klein. Learning dependency-basee based compositional semantics. Comput. Linguistics, 2013.
Ankur Arjun Mali, Alexander Ororbia, Daniel Kifer, and C. Lee Giles, Recognizing long grammatical sequences using recurrent networks augmented with an external differentiable stack. In Proceedings of the 15th International Conference on Grammatical Inference, 2021.
William Merrill. Sequential neural networks as automata. CoRR, 2019.
William Merrill and Ashish Sabharwal. Log-precision transformers constant-depth uniform threshold circuits. CoRR, 2022.
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. A formal hierarchy of RNN architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
Marvin L. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, Inc., 1967.
Tom M. Mitchell. The need for biases in learning generalizations. Technical report, Rutgers University, 1980.
Michael Mozer and Sreerupa Das. A connectionist symbol manipulator that discovers the structure of context-free languages. Advances in Neural Information Processing Systems 5, 1992.
Peter Nordin. Evolutionary program induction of binary machine code and its applications. PhD thesis, Dortmund University of Technology, 1997.
Jorge Pérez, Javier Marinkovic, and Pablo Barceló. On the turing completeness of modern neural network architectures. In 7th International Conference on Learming Representations, 2019.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. J. Mach. Learn. Res., 2021.
Jordan B. Pollack. The induction of dynamical recognizers. Mach. Learn., 1991.
Alethea Power, Yuri Burda, Harrison Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. CoRR, 2022.
Ofrr Press, Noah A. Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. CoRR, 2021.
Eric Price, Wojeiech Zaremba, and Nya Sutskever. Extensions and limitations of the neural GPU. CoRR, 2016.
Elaine Rich. Automata, Computability and Complexity. Prentice-Hall, 2007.
Paul Rodriguez and Janet Wiles. Recurrent neural networks can learn to implement symbol-sensitive counting. In Advances in Neural Information Processing Systems 10, 1997.
John F. Savage. Models of computation exploring the power of computing. Addison-Wesley, 1998.
Luzi Sennhauser and Robert C. Berwick. Evaluating the ability of Istms to learn context-free grammars. Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018.
Hava T. Siegelmann and Eduardo D. Sontag. Analog computation via neural networks. Theor. Comput. Sci., 1994.
Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997.
Natalia Skachkova, Thomas Alexander Trost, and Dietrich Klakow. Closing brackets with recurrent neural networks. In Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018.
Ray J. Solomonoff. A formal theory of inductive inference. part Inf. Control., 1964a.
13

---

Published as a conference paper at ICLR 2023
Ray J. Solomonoff. A formal theory of inductive inference, part II. Inf. Control., 1964b.
Ray Solomonoff. Algorithmic probability: Theory and applications. In Information Theory and Statistical Learning. Springer US, 2009.
Ray J. Solomonoff. Algorithmic probability, heuristic programming and agi. In Proceedings of the 3d Conference on Artificial General Intelligence, 2010.
Mark Steijvers and Peter Grünwald. A recurrent network that performs a context- prediction task. In Eighteenth Annual Conference of the Cognitive Science Society, 1996.
John Stogin, Ankur Arjun Mali, and Lee Giles. Provably stable interpretable encodings of context free grammars in mns with differentiable stack. CoRR, 2020.
Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2021.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In Advances in Neural Information Processing Systems 28, 2015.
G. Z. Sun, C. L. Giles, H. H. Chen, and Y. C. Lee. The neural network pushdown automaton: model, stack and learning simulations. Technical report, University of Maryland, 1993.
Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence to sequence learning with neural networks. In Advances Neural Information Processing Systems 27, 2014.
Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieber. LSTM networks can perform dynamic counting. CoRR, 2019a.
Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieber. Memory-augmented recurrent neural networks can learn generalized dyck languages. CoRR, 2019b.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30, 2017.
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power finite precision mns for language recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, 2018.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks. In 3rd International Confer- ence on Learning Representations, 2015.
Janet Wiles and Jeff Elman. Learning to count without a counter: A case study of dynamics and activation landscapes in recurrent networks. In Seventeenth Annual Conference of the Cognitive Science Society, 1995.
Mark Wineberg and Franz Oppacher. A representation scheme to perform program induction in canonical genetic algorithm. In Parallel Problem Solving from Nature PPSN III, International Conference on Evolutionary Computation, 1994.
Greg Yang and Alexander M. Rush. Lie-access neural turing machines. In 5th International Conference on Learning Representations, 2017.
Dani Yogatama, Yishu Miao, Gábor Melis, Wang Ling, Adhiguna Kuncoro, Chris Dyer, and Phil Blunsom. Memory architectures in recurrent neural network language models. In 6th International Conference on Learning Representations, 2018.
Wojciech Zaremba and Ilya Sutskever. Reinforcement learning neural turing machines. CoRR, 2015.
14

---

Published as a conference paper at ICLR 2023
Wojeiech Zaremba, Tomás Mikolov, Armand Joulin, and Rob Fergus. Learnnng simple algorithms from examples. In Proceedings of the 33nd International Conference on Machine Learning, 2016.
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with LEGO: synthetic reasoning task. CoRR, 2022.
15

---

Published as a conference paper at ICLR 2023
A EXPERIMENTAL DETAILS
A. 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 commu- nity (Bahdanau et al., 2015 Vaswani et al. 2017)): Given a prefix p of a word w I., predict the probability of its next token E E. 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 palin- dromes of length 2, with alphabet Σ = {a, 6). the output probabilities are P'alprrfix = a) = 1 and P(b|prefix = b) = 1. However, for palindromes of length 3, the probabilities are very different, Le., P(a prefix a) 0.5 and P(b/pxxfix 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.
b) 0.5. Therefore, there is conflict between
The second approach is predict the set of possible next tokens and not their probabilities (Bhat- lamishra et al. 2020; Suzgun et al. 2019a). In this case, the distribution of possible next tokens does not change with the length, and incressing the length at test time is possible. However, for each prefix, the target will consists of set of tokens, which is incompatible with the (standard sequence) prediction setting and thus of lesser interest 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. 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 neemory-augmented finite-state automata that reside different levels of the Chomsky hierarchy depending on their type of external memory access (none, a stack, or 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 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 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 local view of the external memory (e.g., the top of the stack or the current memory cell).
the Transformer models), etc. For training of the
RNN A vanilla single-layer RNN EEman 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, 2013). The controller can perform any linear combination of PUSH, POP, and NO-OP on the stack, with action weights given by softmax over 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 differentiable nondeterministic stack. We consider the NDStack-RNN RNN proposed by (DuSell & Chiang, 2020 2022). which simulates nondeterministic stack via dynamic programming. Concretely, normalized
16

---

Published as a conference paper at ICLR 2023
actions and nondeterministic state reading with 2 states and sweep over 2, 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 architectrre (Suzgun et al. 2019b). The controller can perform any linear combination of WRITE-RIGIIT, WRITE-LEFT, WRITE-STAY, JUMP-LEFT, and JUMP-RIGIIT on the tape, with action weights given by softmax. The actions correspond to: writing at the current position and moving to the right (WRITE-RIGHT), writing at the current position and moving the left (WRITE-I.EFT), writing at the current position (WRITE-STAY), jumping & steps to the right without writing (JUMP-IIGHT) where & the length of the input, and jumping & steps to the left without writing (JUMP-LEFT). Finally, to allow the TNNe-RNNN to perform memory operations without having to produce the output, we append "computation" tokens (different from the empty tokens Ø used to produce the output, see Appendix A.4 below) to the input sequence. As in the Stack-RNN, each cell of the tape contains a real vector of dimension 8.
be.lbelow))
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 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-sequee tos-uueeeeeeeeeeeeeee model to produce the output but attend the whole input (including the empty tokens @). We use five blocks with dmode = 64, where each block is composed of attention layer, two dense layers, and 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 D RoPE (Su al. 202I), ALiBi (Press et al. 202I). and the relative positional encoding from Transformer-Xe XL (Dai et al. 2019).
Transformer (autoregressive) vanilla Transformer (Vaswani et al. 2017). We do not use empty tokens Ø 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 A vanilla CNN, consisting of convolutional layers with 32 channels each and 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, 113.
A.3 TASKS
Here, we describe our tasks (listed in Table A.I) in more detail. As mentioned in Section 4 all tasks consist of an input sequence æ E Ly from which the models have to predict the target sequence y E Lo. We append [y] empty tokens @ to the input sequence, such that the models can process the entire input sequence before having to produce the output (i.c., 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 one empty token 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.c., stack).
Even Pairs (R) Given a binary sequence, e.g., x = oabba, compute the number of abs and bas is even. For aabbo, we have one ab and ba, meaning that the total number is 2 and thus even, i.e., = (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 2tstate finite-state machine that looks at the first bit of the sequence and compares with the last one.
17

---

Published as a conference paper at ICLR 2023
Modular Arithmetic (Simple) (R) Given sequence of numbers in {,, 4) and opera- tions in (-.-,-1 compute the result modulo 5. For example, I = + 2 - evaluates to 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 can solve it with 5-state finite-state machine, which transitions for each new operation with the state being equal to the current result.
Parity Check (R) Given a binary string, e.g., aaobba, compute if the number of bs is even. The sequence z = aaabba contains 2 lis which is even, i.e., y = b (where we arbitrarily equate odd with a and even with b). This task regular since we can solve it with a 2-state finite-state machine, which transitions every time it sees token different from its current state.
Cycle Navigation (R) Given a sequence of movements on a cycle length 5, compute the end position. The movements STAY, INCREASE, DECREASE and are represented as {0. 1, 2). The agent always starts at position O. For example, 010211 means the agent stops at position 0 + 0+ it with a 5-state finite-state machine, similar to Modular Arithmetic (Simple) (R), as the task can be converted into sum modulo 5.
1 + 1 + = 2, and the output class is 2. This task is regular since
solve
Modular Arithmetic (DCF) Given sequence of numbers in (0, 1, 4), brackets, and opera- tions {+; -..), .). compute the result modulo 5. For example, the sequence x = -(1 (1-2)-(4 (4-3-(42) evaluates to y O. 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 (-2) with 2 E {0, 1, 3, 4}, which have length 4 and thus be used 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 closing bracket, and uses no-ops to let the finite-state machine work otherwise.
Reverse String (DCF) Given binary string, e.g., x aabba, compute its reverse, i.e., y abbua. The task is DCF since we can solve it by pushing the tokens of the input sequence stack until the first empty token Ø appears and then popping the tokens from the stack, outputting the values one by one. This task cannot be solved with finite-state machine since the number of possible outputs is infinite.
Solve Equation (DCF) Given an equation consisting of numbers in {0, 2, 3, 4). brackets, operations in {+,- - .) and an unknown variable z, compute the value of 2 such that the equation modulo holds for 2 i... = 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 nondeterministic finite-state machine can be simulated with deterministic one, implying that this task DCF and not NDCR.
holds modulo 5. For example, x -(2 2) (4 3 (-2))
Stack Manipulation (DCF) Given binary string representing stack's content (given bottom- to-top) and a sequence of PUSH a, PUSH 6, or POP actions, execute the actions on the stack and return the final stack content (in 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., x = abbua POP PUSH a POP, results in y = abba. If POP action is called on an empty stack, the action is ignored. This task requires stack manipulation by design and is therefore DCF.
Binary Addition (CS) Given two binary numbers, e.g., 10010 and 101, compute their sum in base 2, i.e., y = 10111 for & = 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 provided one after the other (and not bit-by-bit at the same time).
Binary Multiplication (CS) Given two binary numbers, e.g., 100 and 10110, compute their product in base 2, i.e., y 1011000 for 100 10110. The inputs and outputs are given in
18

---

Published as a conference paper at ICLR 2023
Table A.I: Our tasks with their level in the Chomsky hierarchy and example input/output pairs. The denotes cnrpuutaaioninvariinn tasks; the denotes counting tasks; the denotes tasks that require nondeterministic controller; and the x denotes tasks that require superlinear running time in terms of the input length.
Level
Name
Example Input
Example Output
Even Pairs
aabba
Truc
Modular Arithmetic (Simple)
1 + 2 aaabba
R
Parity Check
True
Cycle Navigation
011210
Stack Manipulation Reverse String Modular Arithmetic
abbaa POP PUSH POP aabba
abba
abbaa
DCF
-(1 2) 34 (-2))
Solve Equation
2) (4 (4-3-- (-2))
Duplicate String
abaab 10011021 aaabaa 10010 + 101
abaababaab
Missing Duplicate
Odds First
aaaaba
CS
Binary Addition
10111
Binary Multiplication*
10010 101 100010
1001000
Compute Sqrt Bucket Sorti*
110
421302214
011222344
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).
Compute Sqrt (CS) Given binary number, e.g., 101001, compute the floor of its square root, i.e., = L=11000011] = 101. The inputs and outputs are given little-endian representation, This task CS since the digit-by-digit algorithms compute the integer square root require many sequence manipulations, including binary multiplications, which is CS task.
Duplicate String (CS) Given binary string, e.g., abaab, output the string twice, i..., y/ abaababaab. This task is CS since it corresponds to the well-known language (ww w is word) (cf. Section which is CS.
Missing Duplicate (CS) The input is binary string of the form wew where is itself binary string. One token in this string has been hidden, and the network must find out which one it is, by looking at the value the same position but on the other side of the string. For instance, ab abo (i.e., w aba), then a. This task is CS since it requires on the recognition of the well-known language (ww w is word) (cf. Section which is CS.
Odds First (CS) Given binary string t,. output t tttats...atatt... For example, the output corresponding to æ = aaabaa is y aaaaba. The task is CS because it exhibits cross-serial dependencies (the output the interleaved input).
Bucket Sort (CS) Given string over alphabet of fixed size (5 in our case), return the sorted string. Since the alphabet has a fixed size, the task can solved via bucket sort, which only requires finite amount of counters (i.e., 5 counters in our case). For example, the output corresponding to x = 421302214 is y = 011222344. The task is CS because requires multiple counters that keep track of the number of occurrences for every token.
19

---

Published as a conference paper at ICLR 2023
A.4 PROBLEM SETUP
We now provide the full formalization of our problem setup (described in Section 4 Algorithm A.1 illustrates our training procedure. We train on sequences of length (11, N), with N 40 (using batches of size 128). For testing, we consider sequences of length sampled from ((N + 1, M), with M 500. In general, we report the score, which we define as the per-sequence accuracy A (see Section 4 averaged over all sequences of unseen length, i.e., score == M-N Ei=++1 A(x, y). We use the Adam optimizer (Kingma & Ba 2015) with default hyperparameters for 1 1000 000 steps, which we have found to be sufficient to achieve a near-optimal training performance for all tasks and architectures. As described in Algorithm [.I we augment our imput sequences a with m empty tokens Ø, where m is the length of the corresponding target sequence y, so that the networks only need to start outputting after they have consumed the entire input sequence. Moreover, we add computational tokens (which are different from the empty tokens Ø) the input sequence æ for the Tape-RNN to enable it to perform memory operations without having to output the result. In general, we run all experiments with 10 different random seeds (used for network parameter initialization) and three learning rates (1 x 10-4, 3 x 10 and 5 x 10 10= and we report the result obtained by the hyperparameters with the maximum score (means and standard deviations in Appendix [). However, for Transformers, NDStack-BR -NNs, and Tape-RNNs we sweep over additional hyperparameters: For Transformers we consider five different positional encodings, for the NDStack-RNN we optionally read from internal states of the nondeterministic stack (one of the improvements proposed by DuSeil & Chiang 2022)) and sweep over 2 and 4 symbols, and for the Tape-RNN we consider various numbers of computation tokens (0, l, 2f), and various numbers of tapes (1 and 4).
1
Algorithm A.1: Training pipeline for our sequence prediction tasks. The comments (in blue) show an example output for the Reverse String (DCF) task.
Input: model po (-1 (z) with parameters 8, learning rate a, number of training steps S Initialize parameters 0
for i 4- 1 to do
Sample length from (111 40)
/+ t=3 +/
Sample sequence x of length from the task's input grammar Compute the corresponding output sequence y of length m /- y 110 with = 3 +/ Pad æ with m empty tokens Ø such that the model only needs to start outputting after having consumed the entire input sequence, i.e., x t x 2... Set the output to empty sequence of length m, i.c., o + 2..2 for /. 4- 1 to m do | Compute the output probability distribution + po(-121:2++1)
/+ = 011 for f= 3 +/
/ x 011222 #/
/ o E R +/
10 end
11 Compute the cross-entropy loss (averaged over output tokens) C - 1 D
m 1=1 y/
log Oz
12
Update the parameters with gradient descent 0 +- 0 vCC
Compute the per-sequence accuracy A m Em= 1 [arg max, Vıj = arg max, 0tj]
13
14
end
A.5 COMPUTATIONAL RESOURCES
We implemented our evaluation suite in JAX (Bradbury et al., 2018)) using the DeepMind JAX ecosys- tem (Babuschkin et al. 2020 Hessel et al. 2020 Hennigan et al. 2020). We make all of our code pub- licly available at http:::p/// //ggtttuubbb com/ dreepmind/neural We ran each task- aurchteectur--yyerpaaaaa RNNs, Stack-RNNs, LSTMs and Stack-LSTMss, the hyperparameters we have used are learning rates and seeds, which gives 15 (tasks) 4 (models) 3 (learning rates). 10 (sceds) = 1800 TPU-units. For Tape-RNNs, the hyperparameters we have used are the learning rate, the num- ber of computation steps tokens, the number of tapes, and the random seeds, which yields 15 (tasks) 3 (learning rates)- 3 (computation steps) 2 (tapes) 10 (seeds) = 2700 TPU- units. For Transformers (encoder and autoregressive), the hyperparameters learning rate, the positional encodings, and the random seeds, which gives 15 (tasks) 2 (models). 5 (positional encodings). 3 (learning rates). 10 (seeds) 4500 TPU-units. For the NDStack-
triplet on single TPU on our internal cluster. For
have used are the
20

---

Published as a conference paper at ICLR 2023
Table A.2: Mean and standard deviation of the running times (in hours) for all the architectures and tasks. The denotes permutation-ing invarrinn tasks; the denotes counting tasks; the denotes tasks that require a nondeterministic controller; and the x denotes tasks that require superlinear running time in terms of the input length.
Stack-NNN
NDSSadd-BNN
Topo-RNN
Trandormerr
Stack-ISTM
Auturg,, Transfemur
0.56 0.01
8.50
297
Podular Arithmetic (Simple)
0.00
0.19
150 0.56
a
211 0.01
0:24
Parsty Check!
0.78
6.54
1:23
068::00.6
296 0.0)
Cycle Nevigation
247 0.01
Stack Masipulation
6.07 0.12
6:60+-0.. 0.85
17.80 1:45
5.97 3.00
5.05 0.05
6.27 1.77+-0.10
8 880 0.01
7:35- + 2.31
DCF
Beverse String
Modular Arithretic
2.702-2.115 2.15
0.50 + 0.02
3.112:002 0.90
0.35
0.11
10:40 0.90
0.082:0.75
5.64 2.36
1.58 2.58
3 0:000-0.00 0.00
1.02 0.78
0.70 0.00=0000
3:27::0..72
5:21 0.04
5:15 0.0)
3.99 0.90::047
4.32 + 2.05
Solve Equation"
252 6- 0.05
5:26 0.709
9.36:5.0.5 0.64
5.00
00000-2::5 2.30
5,50
0.04
2.96:::00 10
5.25 0.05
3.91 0.25
Duplicate String
UST 8 0.05
1.33-4-0113
20.25-4-3231
5.10 33.00
2445 0.76
01992 22
T:2 0.02
5,09 4 018
MLszing Duplicate
0.71 0.04
2:
1.24 0.55
2.05 0.01
First
2:
0.09 0.05
10.58
2:
1,07
5:45 0.01
Addition Binary # Sqrt Bucket Sorzfa
0.04
5.49
0.00
1.67 0.34
4.19 0.01
1.27
0.06 0.05
16.76
9.61
1.54
5.64 0.05
RNN, the hyperparameters we have used are the learning rate, the number of stack symbols, and the random seeds, which gives 15 (tasks) (numbeer of symbols) -3 (learning rates) 10 (seeds) = 900 TPU-units. Moreover, we used an additional 300 TPU-units for the phase transition ex- periment (Appendix [.2).. For the CNN experiment, we used 15 (tasks) 4 (kernel sizes) experimenn 3 (learning rates)) 10 (seeds) 1800 TPU-units. For the scaling laws experiment, we used 15 (tasks) 3 (training steps) 5 (num layers) 3 (learning rates). 10 (seods) = 6750 TPU- units. Finally, for the autoregresive experiments (excluding the autoregressive Transformer), we used 8 (Lasks) 3 (learning rates) 10 (seeds) = 240 TPU-units for the RNNs, Stack- and LSTMs, i.e., 720 TPU-units, and (Lasks) 3 (computation steps) 2 (tapes) -3 (learning rates). 10 (seeds) = 1440 TPU-units for the Tape-RNN: Thus, in total we used 20 910 TPU-units. We report all the running times, for each task and architecture, in Table A.2 Note that we aggregated the results over the hyperparameters, which explains the high standard deviation for Transformers (five different positional encodings) and Tape-RNN (three different numbers of computation steps tokens, two different numbers of tapes).
The NDStack-RNY RNN is comparably slow to train. Stack-RNN, due to the computation of the big tensor 7, denoting the transition weights between nodes. Furthermore, this tensor takes lot of space in memory, i.e., the number of values it contains is, once unrolled the whole trajectory, proportional to (1 + m)3 where I 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.
roughly four times slower than classical
B
ADDITIONAL EXPERIMENTS
B. 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 [a.l 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 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 training distribution and not finite dataset (as discussed in Section 4.. Thus, it is possible
21

---

Published as a conference paper at ICLR 2023
Table B.1: Means and standard deviations (computed over random seeds) of the score (average test accuracy, see Section 4 for the results of the main experiment (see Table 2 and Section 5.1). The denotes permutation invaarint tasks; the denotes counting tasks; the denotes tasks that require nondeterministic controller; and the x denotes tasks that require superlinear running time in terms of input length.
Level
Tasks
RNN
Stack-RNN
Tape-RNN
Transformer
LSTM
Even Pairs Modular Arithmetic (Simple)
100.0 = 0.0
100.0
0.0
100,0 = 0.0
67.7 + 15.2
100,0 = 0.0
100.0 0.0
100.0
0.0
100,0 1 0.0
23.1 1 0.8
100,0 0.0
Parity Check
95.5 + 14.2 14.2
100.0
0.0
100.0 + 0.0
50.4 0.7
100.0 0.0
Cycle Navigation!
100.0 + 0.0
96.8 6.6
100.0 + 0.0
33.9 + 10.5
90.0 + 10.8
Stack Manipulation Reverse String
54.3 + 1.1
93.8 = 15.1
66.9 = 22.6
51.1
58.1 0.7
60.4 2.3
96.2 + 12.1
90.7 15.6
56.1 2.7
59.5 1.0
DCF
Modular Arithmetic
34.6++00
75.8 + 11.3
60.9 20.7
28.2 3.4
53.1 4.3
Solve Equation
8.7
46.1
23.5
Duplicate String
0.0
51.6
90.0 16.3
52.8
56.5 1 0.9
Missing Duplicate
0.2
53.6 0.7
66.1 = 23.3
53.8
63.1
Odds First Binary Addition
1.2
51.5 0.1
76.2 16.6
1..7.00.0
54.6
1 0.8
CS
0.3
50.9 0.9
74.3 + 10.6
51.7
54.8 + 0.4
Binary Multiplication"
0.2
U.7
54.
30.4 3.6
52.9
0.2
Compute Sqrt Bucket Sort
13.9
56.1 0.3
55.6 1.4
51.5
57.3
0.2
22.5 1 3.6
56.6
16.2
33.6
12.8
35.7 1 23.1
79.4
21.9
1.0
0.8
Score
0.8
mean
0.7
std
100
200
300
500
Sequence length
Training range
(a) Maximum accuracy (over 10 different random (b) Score per training range (min, max, and mean taken seeds) per length for different training ranges (in color). over 10 random seeds).
Figure B.I: Phase transition effect for the Stack-RNN on Reverse String (DCF). For training ranges N < 10, the model fails to generalize longer sequences memorizes the training distribution. The score in Fig. B.lb is the accuracy shown in Fig. B.la averaged over sequence lengths (x-axis).
that models do not achieve perfect accuracy within the training range (11,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 lata-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. shows the generalization performance Stack-RNNs on the Reverse String (DCF) task for different training ranges. Clearly, the models fail to learn the data-generatee algorithm when only exposed to sequences of length smaller than 10. We hypothesize that for small training ranges the networks overfit the training data, essentially learning lookup table to recognize the small finite language. contrast, larger training ranges encourage the networks to learn the data-generating algorithm that generalizes to sequences of unseen length.
22

---

Published as a conference paper at ICLR 2023
brobebiity of stack action, timestep
Probabiity action,
PusH
339
PCA of the inte mai states
PCA of the interna states
PCA of the Incernal states
10
addeo
2
10
20
50
100
120
1900
(a) Stnck BNck-RNNooo on Parily Check (R).
(b) Stack-RNN Reverse String (DCF).
(c) Suck-RNN Bucket Sort (CS).
Figure B.2: Analysis of the Stack RNN on the Parity Check (R) and Reverse String (DCF)
tasks. Left: The network does not use the stack on Parity Check and has the same state structure as a classical RNN. Right: The network uses the stack on Reverse String and the PCA of the states shows that they are clustered according to the last input token only.
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. | 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. 3a also showed that the PCA of the states is identical to the one of simple RNN as it only depends on the last result and the last input token. Moreover, Fig. 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 implement. Note that in this task the number of empty tokens Ø 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. B.2c 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 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% with baseline 20%) on the Cycle Navigation (R) task but it does not 'solve' the task (in terms of our definition of score 2 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 increase readability). Our transformer networks consist of 5 layers with heads, and we show all of the attention matrices (i.e., 5 8) for a short input sequence of length 8. Note that the actual input to the network is of length since we append an empty token to the input sequence, from which we retrieve the output (see Section and Appendix A
Interpretation of the learned algorithm On the first layer, the model uses only the last empty token and matches 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 Os, the number of Is, 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 a weighted sum (softmax) of single value (the token which is attended to), and the weights are all equal to 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 constant weight over the whole sequence, which means that the output
23

---

Published as a conference paper at ICLR 2023
Head 1
Head
Head 3
Head 4
Head
Head
Head 7
Head
Layer
121021203
121021203
121021203
121021203
121621203
121021203
121021203
121021203
Layer
121021203
121021203
121021203
121021203
121021203
121021203
121021203
121021203
Layer
121021203
121021203
121021203
121021203
121021203
121021203
121021203
121021203
Layer
121021203
121021203
121021203
121021203
121021203
121021203
121021203
121021203
Layer
121021203
121021203
121021203
121021203
121021203
121021203
121021203
121021203
Figure B.3: Analysis of the Transformer attention matrices on the Cycle Navigation (R) task, for an input sequence of length 8, used as ticks the x-axis.
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 merge the heads. Fig. B.4 shows 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 I/N where N is the sequence length (since network can reasonably generalize to longer lengths, but not perfectly. Looking at Fig. B.4, means conserved for longer sequences, but the points become closer and closer, that the structure differentiation into classes more difficult. Fig. B.3] shows the evolution of which makes further the activations the last layer for increasingly long sequences. The classification becomes more challenging because the input activations do not form 5 clear clusters anymore.
using softmax). This explains why the
B.4 CONVOLUTIONAL NEURAL NETWORKS
Bansal al. (022) showed that fully convolutional networks achieve near-perfect length general- ization 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 simple CNN on our benchmark and visualize the maximum and average accuracies over unseen test lengths in Tables B.2 a.3 respectively. We observe that our simple architecture with kernel sizes {3,5, 7, 11} (see Appendix 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 adaptive number of layers depending the sequence length (similar to adaptive computation time (Grves 2016) and thus crucially differs study).
architecture that Bansal et al. (2022) consider relies
from classical CNN (such as the
24

---

Published as a conference paper at ICLR 2023
By number
By number of
By number of
By output classes
POZ
100 100 1.00
100
100
100
PCA1
PCA2
PCA1
PCAL
Figure B.4: Analysis of the Transformer activations after the first layer the Cycle Navigation (R) task, for an input sequence of length 8. We report only the first two principal components 512 sequences. We clearly see that the network learns count the number of Os, Is and 2s and already separates the output classes very well after this first layer.
Length 20
Length 100
Langth 200
Length 500
-3.0
-2.5
0.0
5.0
-5.0 -2.5
0.0
2.5
5.0
-5.0
-2.5
0.0
2,5
-3.2 -2.5
2.5
PCA)
PCAL
PCA)
PCAL
Figure B.5: Analysis of the Transformer activations after the last layer. before the final linear logit layer, on the Cycle Navigation (R) task, for an input sequence of length We report only the first two principal components of 512 sequences. We that the activations form clear clusters for short sequences (length 20), and slowly decay into the center, mixing the clusters together.
25

---

Published as a conference paper at ICLR 2023
B.5 STACK-LSTMS
We evaluate the experiment suite from Section 5.1 for the Stack-LSTMs and compare their per- formance 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 initializa- tion 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.., our training protocol (gradient descent) is less stable for this architecture, confirming the results of prior work (Hao al., 2018). We hypothesize that this is due the fact that LSTTSs 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 disadvantage for simpler tasks that only need finite-state automaton controller to interact with the memory structure. Thus, if the controller 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.c., 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 (which stands for Non Deterministic Stack-RNN) (DuSell & Chiang 2020 (022).
We observe that this architecture performs well on regular tasks, as the other memory-auggeent
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 Dup Duplicas licate (CS) task perfectly. We tried some ablations and reduced the stack size to only I: 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 memory, on top of the memory of the RNN controller.
B.7 AUTOREGRESSIVE MODELS
In this paper, we chose 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-AUGMENTT RECURRENT NEURAL NETWORKS
RNNs, i.c., RNN, LSTM, Stack-RNN and Tape-RNN, we replace the empty tokens Ø 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.
For the
26

---

Published as a conference paper at ICLR 2023
Table B.2: Score (in percentage, see Section i.c., accuracy averaged over all test lengths and maximized over 10 random seeds (and other hyperparameters, see Appendix A). for the CNN, Stack- LSTM, and NDStack-RNN. The results for the Stack-RNN) are identical to Table are included only for easier comparison with the Stack-LSTM. We consider model to generalize successfully (bold) its score 90%. The random accuracy 50% (except for Cycle Navigation (R), Bucket Sort (CS), and the two modular arithmetic tasks where it is 20%). We denote permutation- invariant tasks with f. counting tasks with *, tasks requiring a nondeterministic controller with o, and tasks requiring superlinear running time with x.
Level
Tasks
CNN
Stack-RNN
Stack-LSTM
NDStack-RNN
Even Pairs
50.1
100.0
100.0
100.0
Modular Arithmetic (Simple)
20.1
100.0
100.0
100.0
Parity Check!
50.0
100.0
100.0
100.0
Cycle Navigation
20.1
100.0
100.0
100.0
Stack Manipulation Reverse String Modular Arithmetic Solve Equation"
52.4
100.0
100.0
59.2
53.0
100.0
100.0
62.4
DCF
31.2
96.1
61.0
35,8
20.1
56.2
67.5
47.5
Duplicate String Missing Duplicate
50.0
52.8
59.0
51.0
51.0
55.2
55.1
100.0
Odds First Binary Addition
50.0
51.9
55.5
53.1
CS
49.8
52.7
56.0
53.5
Binary Multiplication
49.9
52.7
53.3
50.9
Compute Sqrt Bucket Sorti*
50.2
56.5
57.6
55.0
29.1
78.1
99.2
41.7
B.7.2 TRANSFORMER
In Section 5 we compared the Transformer encoder (used non-autoregressive manner) 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 Ø). However, the original Transformer architecture (Vaswani et al. (017)) also consists of a decoder and processes sequences autoregressively, which is what we evaluate in this section. Similar memory-augment autoregressive model performs roughly solve (or show strong performance) on the permutation-invariann task Bucket Sort (CS). This likely due to the causal masking in the decoder attention, which eliminates permutation cermutation-ivvarinnce 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 length throughout the task and thus the model manages to align the input and output embeddings (using relative positional encodings).
RNNs, we observe that the well as the Transformer encoder, except that it fails to
fixed
B.8 SCALING LAWS AND THE CHOMSKY HIERARCHY
Suppose a neural architecture, e.g., transformer, is limited 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 algorithms in practice (i.c., when considering the training protocol). While we cannot rule out that excessive training, hyper-parameter tuning, 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, more training data or larger models but can be overcome with architectural extensions in line with the theory of computation (i.e., adding stack or tape RNN).
surface some systematic limitations that not overcome with
27

---

Published as a conference paper at ICLR 2023
Table B.3: Means and standard deviations (computed over random seeds) of the score (average test accuracy, see Section for the results of Table B.2 The results for the Stack-RNN identical to Table B.I and are included only for easier comparison with the Stack-LSTM. The denotes permutation-Invarfe nondeterministic controller, and the x denotes tasks that require superlinear running time in terms of the input length.
tasks; the denotes counting tasks; the denotes tasks that require
Level
Tasks
CNN
Stack-RNN
Stack-LSTM
NDStack-RNI
Even Pairs Modular Arithmetic (Simple)
50.1 + 0.0
100.0 + 0.0
100.0 + 0.0
98.0 +.7
20.0 00 0.1
100.0 0.0
100.0 0.0
78.4 28.8
Parity Checkt
50.0 +.0+0.00 0.0
100.0 + 0.0
100.0 + 0.0
95.6 + 13.6
Cycle Navigation'
20.0 + 0.1
96.8 + 6.6
77.7 +.5
95.0 9.1.
Stack Manipulation Reverse String Modular Arithmetic
52.4 1.4++0.0 0.0
93.8 + 15.1
66.2 17.4
55.1 +
53.0
96.2 12.1
94.0 12.4
0.6
DCF
30.7
75.8 11.3
5.02
2.14
Solve Equation
19.9 0.1
46.1 7.3
42.7 16.0
9.74
Duplicate String
50.0
5..6
56.3 4 1.3
50.6
Missing Duplicate
0.1
53.6
53.3 0.7
82.0 23.3
Odds First Binary Addition
0.0
5.5
5.74
52.2
CS
0.2
5..9
+.6
50.4 + 1.3
Binary Multiplication"
4.0
51.4
5..9
50.0 + 0.4
Compute Sqrt Bucket Sorti*
0.0
5.3
57.3
54.3 0.4
2.6
56.6 16.2
81.7 19.9
25.9 1 7.2
Table B.4: Score (in percentage, see Section 4. i.e., accuracy averaged over all test lengths and maximized over 10 random seeds (and other hyperparameters, see Appendix A). for autoregressive setting. We only include the tasks with output length larger than 1, since the results are identical to those in Table otherwise. We consider model to generalize successfully (bold) if its score 2 90%. The random accuracy is 50% (except for Cycle Navigation (R), Bucket Sort (CS), and the two modular arithmetic tasks where it is 20%). We denote permutation-invariat tasks with t, counting tasks with x, tasks requiring a nondeterministic controller with o, and tasks requiring superlinear running time with X.
Level Tasks
RNN Stack-RNN
Transformer
LSTM
Stack Manipulation Reverse String
58.0
100.0
53.2
56.9
DCF
63.1
100.0
53.5
59.4
Duplicate String Odds First Binary Addition Binary Mul Multiplication
50.3
50.7
100.0
51.7
50.5
51.4
54.7
53.6
49.8
51.7
69.0
53.9
CS
49.5
52.0
52.2
53.3
Compute Sqrt Bucket S
54.1
57.8
52.4
58.0
28.9
52.8
40.4
28

---

Published as a conference paper at ICLR 2023
1.0
1.0
A
8.5
0.9
Jeneary
0.4
Sequence
Sequence lingth
Sequence langth
(a) Even Palrs
(b) Modulaar Arithnetic (Sirple)
Parilyy Check
3.0
1.0
Accupecy
0.8
Atourwyy
0.3
1.5
0.7
0.2
301
2000
330
420
500
0.5
100
200
310
409
590
0.5
350
2100
300
400
500
Soguonceleeggh
Sequince longoh
Scuuercc longth
(d) Cycle Nevigation (R)
(e) Stack Nanipulation (DCF)
(f) Reverse String (DCF)
Transforma
0.5
0.8
0.9
RNM
R
0.8
Tare RMN
0.7
LTM
0.4
644
0.6
0.2
160
200
500
0.5
100
200
400
(g) Nodular Arithretic (DCF)
(h) Equation
Duplicate String (CS)
1.0
1.0
1.0
0.8
0.7
0.7
0.5
0.5
0.5
230
Sequence mm
Seqquence lmngth
Sequerce length
(i) Missing Duplicate (CS)
(k) Odds First (CS)
(1 Dinary Addition (CS)
5.8
0.8
Neurtry
Acturrty
3.6
0.4
35
200
230
350
400
500
0.5
100
200
300
402
300
0.2
120
220
300
400
500
(m) Binary Pultiplication (CS)
(n) Compute Sqrt (CS)
(0) Bucket Sort (CS)
Figure B.6: Performance curves on all tasks, For the Transformer encoder, we pick the best positional encoding for each task (it is considered as a hyperparameter). The dashed vertical red line is the training range, meaning that sequences to the right have not been seen during training and thus measure generalization.
29

---

Published as a conference paper at ICLR 2023
1.0
1.0
1.0
MM/
0.7
0.5
Sequence linggh
Ging Seqquence lrnggh
Saquentne length
(a) Even Pallins (R)
(b) Modullar Arithnetic (Simple) (R)
(c) Parliy Check (R)
0.8-
0.8
22--
0.4
9.2
385
2.30
350
400
500
100
200
300
400
500
1.20
370
4.00
Sequerice longth
Se torgth
(d) Cyclo Novigattion (R)
(e) Stack Hanipulation (DCF)
(f) Reverse Striing (DCF)
1.0
1.0
0.9
Acouneyy
Acaurene
6.6-
0.4
Sequence length
Sequience kngtt
Sequence
(g) Nodular Arithretic (DCF)
(h)
(i) Duplicate Stringg
3.0
2.8-
0.00
0.8
0.7
0.7
8.5
300
2.30
330
420
500
0.5
200
300
409
500
0.5
100
2:0
300
400
500
Sequuence
Sequuence length
Sequerce length
(j) Missing Duplicate (CS)
(k) Odds First (CS)
(1 Binary Addition (CS)
3.5-
0.9
0.8
6.-
Accurery
0.7
3.5
0.6
0.4
8.5
300
2000
0.5
200
300
0.2
lengh
(m) Binary Poltiplication (CS)
Compute Sqrt (CS)
Sort
Figure B.7: Performance curves all tasks for the Transformer encoder architecture, for all the positional encodings we used. The dashed vertical red line is the training range, meaning that sequences the right have not been seen during training and thus measure generalization.
30

---

Published as a conference paper at ICLR 2023
Table B.5: Means and standard deviations (computed over random seeds) of the score (average test accuracy, see Section 4 for the results in the autoregressive setting (i.e., Table We only include the tasks with output length larger than 1, since the results are identical those Table otherwise. The i denotes permutation-invarte require a nondeterministic controller; and denotes tasks that require superlinear running time in terms of the input length.
tasks; the denotes counting tasks; the denotes tasks that
Level
Tasks
RNN
Stack-RNN
Transformer
LSTM
Stack Manipulation Reverse String
56.7 + 0.2
100.0 = 0.00
51.7 + 1.3
55.8 + 0.1 58.1 + 0.1
DCF
62.4 (2.4+01 011
99.3 + 0.2
52.3 + 1.6
Duplicate String Odds First Binary Addition
0.1
0.1
92.7 1 4.7
51.4 0.1
5.1
51.0
52.3
52.9
4.2
0.5
60.2 4.2
52.9
CS
Binary Multiplication"
4.5
1.3
50.8
52.5 0.5
Compute Sqrt Bucket Sort
53.7 0.3
0.3
54.5 0.5
57.7 + 0.5
2.
8.7
2..14.3
93.0 1 6.7
To provide more detailed empirical result, 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, ie., the accuracy averaged over all (unseen) test lengths and maximized over 10 seeds and learning rates, generally does not increase with more training data setup, the Chomsky hierarchy implies a hard limit on scaling laws (Kaplan et al. 2020).
parameters. Thus, in this empirical
31

---

Published as a conference paper at ICLR 2023
Table B.6: Score (see the caption of Table 2) for the Transformer with relative positional encodings and different numbers of layers and training steps (i.e., training data). We observe that the Chomsky hierarchy implies a hard limit on scaling laws (Kaplan et al., 2020p, i.e. more in-distribution data and/or more parameters do not lead to better length generalization performance.
Layers
Level
Task
Training Steps
5
10
15
20
25
100 000
90.2
84.7
74.8
50.1
50.1
Even Pairs
000 000
90.0
78.6
78.7
50.1
50.1
10000 000
97.5
89.7
89.5
50.1
50.1
100
21.7
21.6
21.5
20.5
19.9
Modular Arithmetic (Simple)
000 000
21.2
21.6
22.6
22.1
20.0
100000000
21.3
22.1
24.8
24.4
20.0
100 000
50.3
50.4
50.1
50.1
49.9
Parity Check
000 000
51.5
50.3
50.1
50.1
50.1
000
52.0
50.5
50.1
50.1
50.1
000
24.5
25.4
23.7
22.9
23.2
Cycle Navigation!
1 000 000
22.9
22.5
23.6
22.0
23.7
10000 000
22.8
22.9
25.9
23.2
23.3
100 000
54.9
55,4
55.3
54.5
54.9
Stack Manipulation
000 000
54.0
54.4
53.7
54.9
56.2
000 000
52.8
51.9
53.0
52.9
49.6
100 000
61.6
61.2
58.0
56.1
56.8
Reverse String
0.00 000
59.8
60.6
61.0
60.1
58.8
10000 000
56.5
58.7
57.2
52.1
50.0
DCF
100 000
31.4
31.7
31.9
31.5
31.6
Modular Arithmetic
000 000
28.9
27.9
31.0
31.0
31.0
10000000
27.5
30.8
31.0
31.0
31.0
100
22.4
21.3
21.5
22.2
19.9
Solve Equation
000 000
23.0
22.4
21.6
21.8
19.9
100000000
22.8
21.6
21.9
23.7
20.1
100 000
52.5
53.6
53.1
55.3
53.6
Duplicate String
1 000 000
51.9
51.5
53.1
53.7
54.2
10 000
51.9
51.1
51.7
51.3
50.0
100 000
53.9
52.7
52.6
52.1
50.0
Missing Duplicate
000 000
53.2
53.0
50.0
50.0
50.0
000 000
52.1
52.5
50.0
50.0
50.0
100 000
52.5
53.4
52.9
52.2
53.2
Odds First
000 000
52.5
53.4
52.9
52.7
53.5
10 000
51.8
52.8
52.0
50.0
50.0
100 000
52.3
54.7
51.7
51.2
50.8
cs
Binary Addition
000 000
53.3
55.9
54.8
54.8
53.8
10000 000
52.9
52.9
51.8
54.4
51.1
100 000
52.3
52.3
51.9
51.2
51.0
Binary Multiplication
000 000
52.5
53.1
53.4
53.4
54.0
000
51.8
53.0
52.0
52.8
50.6
100 000
52.8
52.7
52.6
52.0
52.7
Compute Sqrt
000 000
52.3
53.4
53.7
54.0
53.5
10000 000
51.6
52.7
53.4
53.3
53.0
100
90.9
93.9
93.0
91.4
87.5
Bucket Sorti*
000 000
93.1
91.6
92.1
93.7
93.0
10000000
84.3
81.9
80.4
89.5
65.1
32


Reviews:
[{"review_id": "z17RRvSkJo0", "reviewer": "Reviewer_unzx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "**High level motivation:** The authors are interested in understanding what it takes for machine learning systems to reliable generalize to novel circumstances, especially when those are out-of-distribution. \n\n**Research question:** Do insights from the theory of computation (specifically the Chomsky Hierarchy) inform us about the limits of neural network generalization in practice? \n\n**Operationalization:** The authors have:\n* **(tasks)** Designed 15 tasks that cover regular, context-free, context-sensitive and recursively enumerable languages (i.e. require automatons with computational requirements that are associated with the aforementioned grammar types to solve),\n* **(success definition)** Picked length generalization (ability to learn from short problem instances to generalize to longer ones ) as the target capability,\n* **(architecture)** Run extensive experiments on RNNs (augmented with a stack and a tape), LSTMs and transformers (in total 10250 models),\n* **(insights)** Demonstrated that the computational capabilities (i.e. access to stack or memory, a state etc.) of models roughly predict which tasks they display length generalization on. \n\n**Contributions:** \n* An extensive empirical study spanning multiple architectures and tasks,\n* The release of a dataset to evaluate length generalization on,\n* The depiction of serious failure modes regarding length generalization that can partially be explained by the (mis)match between a given model's computational capabilities and the language class the task at hand belongs to.\n* Evidence that some architectural modifications (like the addition of external memory modules) might mitigate length generalization deficiencies. \n\n", "summary_of_the_review": "The authors run an extensive empirical study checking whether theory of computation can be used to predict which architectures will generalize on different tasks. To a large extent, there's a match between a given architecture's computational limitations and the requirements (in the theory of computation sense) a task requires. \n\nThat this is a well-executed paper on an important and timely topic. I believe ICLR would be a better conference with this paper. ", "strength_and_weaknesses": "**STRENGTHS**\n* **Important and timely study:** Investigating the generalization patterns of sequence models is a very important research direction and comes at a time when we need more of this type of work that bridges theory and practice, and when safety concerns (that might be caused by lack of robustness under distribution shifts) are growing. \n* **Crisp problem description and task design:** The authors are very systematic in the way they pick the tasks and define length generalization as the locus of their analysis. There are many ways of framing this problem, and the way the authors have done it seems very sensible. \n* **Relatively comprehensive experiments:** While the experiments and ablations aren't exhaustive (some of the important components that are omitted will be described below), the experiments are still quite comprehensive and has a reasonable focus (i.e. on tools to augment sequence models with tools such as stacks and tapes).\n* **Nontrivial and interesting insights:** The reported limitations of existing architectures have important consequences on the forecasting of AI progress. For example, it looks like naive scaling (i.e. increase model size and in-distribution data size) alone won't solve length generalization unless we get clever with training details. \n* **Nice interpretability analysis:** The interpretability analyses of RNNs with tapes and stacks confirm the intuitions one might have about why these models are able to display length generalization. \n\n**WEAKNESSES**\n* **Missing components of ablation:** I'd like to highlight some components that seem to be missing in the experiments. (I'd like to note that no study is fully comprehensive -- I'm listing these in order to provide a balanced view of the weaknesses of the submission)\n  * Convolutional architectures missing: Bansal et al. [3] have shown that fully convolutional networks show near-perfect length generalization on the prefix sum task (akin to parity). It looks like convolutional networks are also relevant in a study that focuses on the effect of architecture on length generalization. \n  * Effect of pretraining: [4] shows that pretraining data could have an effect on the inductive bias displayed by transformer models. Likewise, [2] shows that large language models (when prompted properly) can display nontrivial length generalization, which is largely due to the pretraining procedure instead of scale. \n  * Effect of depth: While RNN-like architectures \"reason\" through timesteps, transformers \"reason\" along their depth. Hence, it makes sense that a 5 -transformer -block architecture won't have the capacity to handle large depths unless there's a shallow shortcut (like there is in Bucket sort). It'd be interesting to see either very deep transformers, or universal transformers [5] investigated in this work too. \n  * No focus on autoregressive models: Autoregressive generation is what enables scratchpad strategies in transformers, which could help them attain length generalization capabilities. \n* **Missing references:** I'd like to highlight two prior work that appear to be very relevant to the current submission:\n  * \"Unveiling Transformers with LEGO: a synthetic reasoning task\" This paper proposes a task that allows for testing encoder-only transformers' ability to display length generalization. The paper has interesting insights into what goes wrong when transformers fail at length generalization and which components (like pretraning) seem to help. \n  * \"Exploring length generalization in large language models\" This paper explores length generalization too, and finds that vanilla transformers lack this ability even at an extremely large scale. They show, however, that in-context learning and the use of a scratchpad significantly improves transformers' ability to posses length generalization. \n\n**QUESTIONS TO AUTHORS**\n* What exactly is the rightmost column in Table 1? \n* The square root computation doesn't appear to be marked as requiring superlinear time in Table 3. Could you explain what linear algorithm solves this task? \n\n\n\n\n[1] Zhang, Yi, et al. \"Unveiling Transformers with LEGO: a synthetic reasoning task.\" arXiv preprint arXiv:2206.04301 (2022).\n\n[2] Anil, Cem, et al. \"Exploring length generalization in large language models.\" arXiv preprint arXiv:2207.04901 (2022).\n\n[3] Bansal et al. End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking\n\n[4] Wu, Yuhuai, et al. \"Lime: Learning inductive bias for primitives of mathematical reasoning.\" International Conference on Machine Learning. PMLR, 2021.\n\n[5] Dehghani, Mostafa, et al. \"Universal transformers.\" arXiv preprint arXiv:1807.03819 (2018).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "T_s4UykYJ7", "reviewer": "Reviewer_6CTT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper empirically groups sequence to sequence neural architectures models according to the Chomsky Hierarchy. They achieve this by evaluating 10250 neural architectures models across 15 transduction tasks spanning the entire Chomsky Hierarchy.\n\nThey demonstrate that memory augmented architectures tend to fall higher in the Chomsky Hierarchy than those without structures memory (e.g. stack or tape). ", "summary_of_the_review": "I find this work to be an important contribution towards understanding the limits of our neural architectures and their corresponding training mechanisms for sequence prediction tasks. The results on memory-augmented neural architectures were similarly insightful. All in all, I am happy to accept this paper.\n\nI am willing to reconsider my recommendation to an oral presentation if:\n- Clarity around transduction and recognition is improved\n- The per sequence accuracy equation in page 5 is revised\n- The generative grammar section formally defines grammar and includes some dummy examples of Chomsky grammar rules.\n- The claim regarding the hard limits on scaling laws is well justified.", "strength_and_weaknesses": "Strengths\n-------------\n\nFormal languages are relatively under-explored in AI literature, so it is quite encouraging to see efforts in this direction. This work does a great job of identifying Chomsky’s hierarchy as a possible proxy for studying inductive biases in neural architectures and their corresponding training mechanisms for sequence prediction tasks.\n\nThis work also marries well with existing literature on the Turing completeness of neural architectures. The empirical evidence from this work, covers an important gap that was missing from the theoretical literature.\n\nAlthough the results are slightly underwhelming (some architectures cannot solve tasks at their supposed level), it nevertheless demonstrates the limits of these neural architectures for sequence prediction tasks.\n\nThe results from this work have also demonstrated some interesting insight on memory augmented neural architectures, which are often less favoured for sequence prediction tasks.\n\nWeaknesses\n-----------------\n\nThe main weaknesses of this work is the disambiguation of transduction and recognition. I can appreciate that the authors have made an effort to disambiguate between the two concepts which in itself is a non-trivial feat but I don’t think it’s evident from the introduction and abstract that sequence prediction would translate to Finite State Transduction (FST) Machines instead of Finite State Automata (FSA) Machines. \n\nI would suggest dedicating an entire section before the background describing transduction vs recognition and FST/FSA. This was partially addressed in the background section but it is tucked away at the end and requires a couple reads to finally get the greater picture. However this doesn’t take away from the paper, as the motivation to reduce the problem to a transduction problem is justified.\n\n- The generative grammar section could be better explained and would suggest discussing more about Chomsky’s rules as they are also vital in categorizing across Chomsky’s hierarchy. I also suggest placing the generative grammar section before the formal language section or combining the two, as this might read better.\n- The per sequence accuracy equation in page 5, doesn’t seem to make sense. I would suggest revising this. Same applies for the equation in Algorithm A.1.\n- The stack manipulation example in Table A.1 seems incorrect. Are you pushing an empty string? If so, would that be the result?\n- The claim regarding the hard limits on scaling laws is not well explored in this paper and is only mentioned in the introduction and conclusion. I would suggest elaborating on this in the results. I think this is sadly one of the shortfalls of this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "FtrVUohbBL", "reviewer": "Reviewer_vMMY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper conducts a large-scale extensive empirical study to practically investigate whether insights in the computation theory can predict the out-of-distribution generalization limits for neural networks.\n\nIt uses more than 10 thousand models and 15 tasks to evaluate the performance of program induction neural network models on sequence prediction tasks defined in the Chomsky hierarchy. The models include state-of-the-art architectures, such as RNN, LSTM, Transformer, and memory-augmented networks, such as Stack-RNN and Tape-RNN.\n\nIt finds the relation between models and hierarchy on out-of-distribution generalization. For example, memory-augmented networks can solve high-hierarchy tasks.\n\nIt also finds that using more training data does not enable the generalization higher up in the hierarchy for some architectures.\n\nIt opensources a novel benchmark for length generalization, designed to accurately pinpoint the architectures' problems.\n", "summary_of_the_review": "This paper has an extensive empirical study with high coverage of models in interest and tasks in the Chomsky hierarchy.\n\nIt has significant contributions and strengths, as mentioned above.", "strength_and_weaknesses": "***Strength:***\n\nThe best strength is the scale of the evaluation.\nIt includes a variety of models and representative tasks in the hierarchy.\n\nThe Chomsky hierarchy is essential in computation theory. So it is reasonable to find its relation to the neural network to help understand the out-of-distribution generalization for neural networks.\n\n***Weakness:***\n\nI have comments and questions.\n\n(1) This paper uses the \"limit\" of generalization to group neural network architectures.\nIt indicates that even if a model architecture works on a representative task for a Chomsky hierarchy level, it might not work on other tasks on the level.\nThough it is mentioned in the \"limitation,\" it might be worth attention because it differs from the classic automatons' case.\n\n(2) The introduction mentions that the length generalization problem \"subsumes all computable problems.\"\nIs it for classic models like automatons, or is it also correct for neural networks?\n\nFor example, suppose a neural network is trained with short inputs starting with 'a' and can generalize to long inputs beginning with 'a'. However, it is still unclear whether it can generalize to short inputs starting with 'b.'\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AkIu84wrwk", "reviewer": "Reviewer_U2az", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work conducts extensive experiments, showing that the ability of common neural network architectures to learn formal languages can roughly be characterized by the Chomsky hierarchy. \n\nAnother contribution of this paper is that, the results empirically confirmed that augmenting neural network architectures with auxiliary memory (e.g. stack or tape) is helpful for generalization in the formal language setting. (The paper under review is not the first paper that proposes this idea, but it is still good that the paper provides more evidence on this with extensive empirical results.)\n", "summary_of_the_review": "In summary, this work reports extensive empirical results. This work also includes a small number of case studies that shows the models did learn some groundtruth algorithms to solve the tasks in a limited number of settings. I think these strengths justify at least a weak accept. Satisfactorily resolving the above-mentioned weaknesses and questions may potentially justify a higher rating.\n\n\n\nEdit after reading authors' response: \n\nI think the authors sufficiently addressed my main concerns about correctness and clarity by updating their paper with some additional in-depth analyses. So I increased the overall rating from 6 to 8.", "strength_and_weaknesses": "Strengths:\n\n1. Some interpretation results (in Section 5.2) on some combinations of tasks and trained models are strong evidences that the models did learn some groundtruth algorithms to solve the tasks. \n\n2. The paper reports the empirical average accuracy of models trained and evaluated on a wide range of tasks.\n\n\nWeaknesses: \n\nThe set of interpreted/interpretable combinations of tasks and models are limited compared with the set of all claims made in this paper. In particular, when a model achieves higher-than-random but much-lower-than-perfect accuracy on some task, it remains unclear whether the model implemented a correct algorithm (up to small numerical errors), or it implemented a crude approximation. In particular, such approximation may reside in a lower level of the Chomsky hierarchy (e.g. approximating a context-sensitive task with some context-free level algorithm). The authors' claim is somewhat ambiguous on this point (see my 2nd question below).\n\n\nQuestions for the authors: \n\n1. In Figure 2(b), for the modular arithmetic task, why is there a slight increasing trend for transformers when the sequence length is between ~150 and ~300? Does this phenomenon robustly persist if you re-run it? (In comparison, all other curves in Figure 2 show a general decreasing trend.)\n\n2. In Section 5.4, 2nd paragraph, the author stated that “Table 3 shows that Transformers generally succeed on permutation-invariant tasks: They solve Bucket Sort (CS) and demonstrate non-trivial generalization on Cycle Navigation (R).” However, Table 3 shows that on Cycle Navigation, the average accuracy is just 61.9% (random baseline = 20%). This is indeed higher than the baseline, but still seems too low to convincingly justify that the model correctly solved the task. (See my comment in the Weaknesses section above.) Could the authors provide more evidence on whether transformers indeed learns some correct algorithm for Cycle Navigation, or propose a revision of the claim that \"Transformers generally succeed on permutation-invariant tasks\" to make the statement more precise?\n\n3. In Appendix A.1, the authors discusses the limitations of predicting the set of possible next tokens by mentioning that it is “incompatible with the (standard sequence) prediction setting and thus of lesser interest to the wider machine learning community.” Could you share your thoughts on whether we *should* pay more attention to the type of next token prediction tasks whose target is a set rather than a single token? In particular, I am curious to learn:\n- In principle, is it fundamentally different from current approaches? (i.e. is \"training with multiple labels for each sample\" a good approximation of \"training with a single label, different each time, for multiple steps\"?)\n- Practically, I can imagine some applications like auto-completing sentences in email apps or text editors. When it provides multiple candidates, it seems to me that this can be done with models trained either with single-target, or with multi-target?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6__70oi5ABb", "reviewer": "Reviewer_VcFp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides empirical evidences of generalizability of modern neural architectures over synthetic tasks following the Chomsky hierarchy. The results generally agree with theoretical results, highlighting (again) the need for external memory.", "summary_of_the_review": "An useful empirical study to highlight the need for memory to clime the Chomsky hierarchy. More in depth analysis of model behaviors and learning dynamics would be much more beneficial to the community, which is currently sticking around Transformer for empirical successes.", "strength_and_weaknesses": "Strength\n======\n- A nice empirical study with clear designs and messages sent across.\n- Results are useful, pointing to directions of memory, which has been somewhat neglected in the past 8 years.\n\nWeaknesses\n==========\n- As with any empirical study, there is never enough experiments to 100% confirm the points. The authors have clearly articulated that in the limitations section.\n- The authors pointed out that learning procedure (e.g., gradient-based) would have an important impact on the generalizability, but this was not analyzed further.\n- If the empirical nature is the main focus, some statistical analysis would be useful.\n- It would have been much more insightful if some in depth analysis of why models behave they way they do (e.g., LSTM after all is a RNN with state transition dynamic, Transformer is similar to feedforward net, but with clever design of attention, we can make it behave like it has some memory), and why some theoretical properties do not hold in the experiments (e.g., attention is Turing complete, but why Transformer doesn't seem to work well in designed tasks?).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%