Training Neural Networks as Recognizers of Formal Languages
Authors: Alexandra Butoi
Ghazal Khalighinejad
Anej Svete
Josef Valvoda
Ryan Cotterell
Brian DuSell
Venue: ICLR 2025 Poster (2025)
Keywords: neural network
formal language theory
transformer
rnn
lstm
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We train neural networks as recognizers (binary classifiers) on formal languages to fix a disconnect with formal results

Abstract: Characterizing the computational power of neural network architectures in terms of formal language theory remains a crucial line of research, as it describes lower and upper bounds on the reasoning capabilities of modern AI. However, when empirically testing these bounds, existing work often leaves a discrepancy between experiments and the formal claims they are meant to support. The problem is that formal language theory pertains specifically to recognizers: machines that receive a string as input and classify whether it belongs to a language. On the other hand, it is common instead to evaluate language models on proxy tasks, e.g., language modeling or sequence-to-sequence transduction, that are similar in only an informal sense to the underlying theory. We correct this mismatch by training and evaluating neural networks directly as binary classifiers of strings, using a general method that can be applied to a wide variety of languages. As part of this, we extend an algorithm recently proposed by Snæbjarnarson et al. (2025) for efficient length-controlled sampling of strings from regular languages. We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures: a simple RNN, an LSTM, and a causally-masked transformer. We find that the RNN and LSTM often outperform the transformer, and that auxiliary training objectives such as language modeling can help, although no single objective uniformly improves performance across languages and architectures. Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work. We have released our datasets as a benchmark called FLaRe (Formal Language Recognition), along with our code.

Published as a conference paper at ICLR 2025
TRAINING NEURAL NETWORKS AS RECOGNIZERS OF FORMAL LANGUAGES
Alexandra Butoi"
Ghazal Khalighinejad
Anej Svete
Josef Valvoda
Ryan Cotterell
Brian DuSell
'ETH Zürich Duke University
University of Copenhagen
falexandra butoi,
anej svete, ryan. catttoteeell, brian. coonndduelleeel @innf eee.eleeeen.f........
ghazal khal
edu
jval@di ku. dk
ABSTRACT
Characterizing the computational power of neural network architectures terms of formal language theory remains a crucial line of research, as it describes lower and upper bounds on the reasoning capabilities of modern AI. However, when em- pirically testing these bounds, existing work often leaves a discrepancy between experiments and the formal claims they are meant to support. The problem is that formal language theory pertains specifically recognizers: machines that receive a string as input and classify whether it belongs to a language. On the other hand, it is common instead evaluate language models proxy tasks, e-g-, language modeling or sequence-to- poannncettt-eqquee se-suuecce transduction, that are similar in only an infor- mal sense the underlying theory. We correct this mismatch by training and evaluating neural networks directly as binary classifiers of strings, using a general method that can be applied to wide variety of languages. As part of this, we extend an algorithm recently proposed by Snæebjarnarson et al. (2025) for efficient length-controlled sampling of strings from regular languages. We provide results variety of languages across the Chomsky hierarchy for three neural architec- tures: a simple RNN, an LSTM, and a guusally-maskee transformer. We find that the RNN and LSTM often outperform the transformer, and that auxiliary train- ing objectives such as language modeling can help, although no single objective uniformly improves performance across languages and architectures. Our contri- butions will facilitate theoretically sound empirical testing of language recogni- tion claims future work. We have released our datasets as benchmark called FLaRe (Formal Language Recognition), along with our code. 2
INTRODUCTION
Large language models (LLMs) based neural networks have been hailed for their impressive rea- soning abilities. However, the precise scope of what they can and cannot do is hard to pin down. For- tunately, formal language theory gives vocabulary for ascribing hard limits to the kinds of com- putations neural networks can perform. For example, results from formal language theory allow us to know with certainty that transformer LM (without extra whether two regular expressions with repetition operators are equivalent; a transformer LM runs in quadratic time, but the aforementioned problem provably requires exponential time (Sipser, 2013).
steps) cannot determine
A long line of research has attempted to precisely characterize the class of problems neural archi- tectures can solve in terms formal languages (Siegelmann & Sontag, 1995; Gers & Schmidhuber, 2001; Weiss et al., 20;8b; Merrill et al., 2020: Strobl et al., 2024b; Yang et al., 2024, inter alia). Research this line comes in two flavors: formal results that mathematically prove language class bounds, often under simplifying assumptions, and empirical results that, in complementary fashion, provide evidence of these bounds in practice. Simplifying assumptions for the transformer archi- tecture have included the absence of layer normalization, the of hard attention, and the use of special positional encodings; see Strobl et al. (2024b) for a survey. Formal expressivity results
hattpp///ggithbb..mm/yccoa//////

---

Published as a conference paper at ICLR 2025
CF
CF
CF
O
DCF
DCF
DCF O
R
(a) Transformer
(b) Simple RNN
(c) LSTM
Figure 1: Summary of our empirical expressivity results. Dots represent languages, which are listed in Table 1. A filled dot means that the architecture exhibits perfect length generalization (see Table under "Expressivity"). R regular, DCF deterministic context-free, CF context-free, CS context-sensitive. All architectures are limited to regular languages and the DCF language Majority. The transformer is strictly less expressive than the RNN/LSTM the languages we tested.
also typically do not comment on whether solutions are practically reachable through training, even though the bias imposed by the training algorithm may render the set of solvable problems much smaller than suggested by formal expressivity results (Hahn & Rofin, 2024). Empirical results are therefore important for validating the practical relevance of formal results.
This paper aims to reconcile subtle but important disconnect between empirical results and claims about computational power. Formal language theory deals in recognizers: machines that receive string as input and classify whether it is member of language. For instance, the Chomsky hierarchy and the classes P and NP are defined in terms of recognizers. However, some machine learning papers overlook the finer points of these definitions. For instance, the recent study by Delétang et al. (2023) purports to relate the expressivity of neural language models to the Chomsky hierarchy with experiments that use neural networks as string-to-string functions. However, the mismatch between the experimental setup and the actual definition of the Chomsky hierarchy means that the paper would provide evidence about an analogous hierarchy of functions, which is not as well understood formally. There are multiple ways to fix this mismatch: one could change the theoretical claims to those of hierarchy of ttring-to-string functions (Strobl et al., 2024a) without changing the experiments:" or, one could change the experiments to recognition to match the Chomsky hierarchy. In this paper, we explore the latter approach.
Specifically, we propose a method of training neural networks as recognizers that suits wide variety of languages, and we use to test simple RNNs, LSTMs, and transformers on 18 formal languages across the Chomsky hierarchy. Our method for generating data only requires two language-spedd algorithms: randomly sampling positive examples within a particular length range, and membership testing. We provide efficient instantiations for the class of regular languages based on work by Snæb- jarnarson et al. (2025). We generate adversarial negative examples by modifying positive examples, obviating the need for language-specific negative sampling (ef. Weiss et al., 2018b; Someya al., 2024: Bhattamishra et al., 2024). Like Delétang et al. (2023), our evaluation focuses on length gen- cralization, but we also include two sets of experiments that carefully distinguish between tests of inductive bias and expressivity. We also compare multiple training objectives in a multi-task learning setup. We find that the transformer generally underperforms the RNN and LSTM, and all architec- tures are limited to low levels of the Chomsky hierarchy (Figure 1). We have publicly released our datasets as a benchmark called FLaRe (Formal Language Recognition), along with our code.
2 BACKGROUND
An alphabet, denoted E throughout this paper, is a non-empty, finite set of elements called symbols. A string over Σ is finite sequence of symbols in Σ. We use denote the empty string. A language (or formal language) over Σ is a (possibly infinite) set of strings over E. Let E denote
Hierarchies of language models have also been studied (Icard, 2020; Borenstein et al., 2024).
2

---

Published as a conference paper at ICLR 2025
the language of all possible strings over Σ. A recognizer is any computational device that receives string as input and produces a decision to accept or reject it as output, and we say that recognizes the language of strings that it accepts. A language class is (possibly infinite) set of languages. Throughout the rest of this paper, let us assume we are dealing with a specific language over alphahet Y. For any string E", call the proposition T. the label of
2.1 FINITE AUTOMATA AND REGULAR LANGUAGES
Definition 1. A partial deterministic finite automaton (partial DFA) is a tuple A (Q, 5, 9o, F)
QU {8) is the transition function, where 0 indicates the absence of a transition, (4) 90 E Q is the start state, and (5) F _ Q the set of accepting states. If 8(q,a)
where (1) Q is a finite of states, (2) E is alphabet, (3) 6: Q x
+ 0, we say that A has transition from q to that
scans and we write q - 8. We define jo [(q.a) E Q x E 8(q.a) # 00]-
Our definition of DFA is partial in the sense that do not require an outgoing transition to exist for all (g, a) E Q x Σ. For simplicity, from now on, we will simply refer to partial DFAs as DFAs. We call sequence æ of connecting states and transitions path. If i'' transitions scan di..... On. we say that π scans the string t a1.-.. ... ag- For any string w E Σ", if there is path that starts in qu, scans w, and ends in an accepting state, we say that A accepts w and rejects it otherwise. We say that A recognizes the language {w E Σ" A accepts w). A language is regular if there is a DFA that recognizes If all states a DEA are reachable from the start state and can lead to an accepting state, we call it trim.
Because we will present algorithms that use semirings and weighted DFAs, we introduce them here.
Definition 2. A monoid is a tuple (K, O.1), where IK is set, @ is an associative binary operation, and I K. called the identity element, satisfies I @ a I a for all K. If a b b for all b E K, we say that the monoid is commutative.
Definition 3. A semiring is tuple (K, B &, 0, where (I,, + 0) is a commutative monoid and (K, @, 1) is monoid. Additionally, & distributes over @: a @ (b t c) = (a @ b) + (a @
c) and (a b) c = (a (c&c c) @ (b @ c): furthermore, is absorbing with respect to @: 0 & a a
O.
Definition 4. A weighted deterministic finite automaton (WDFA) over a semiring (K, @ 8 0,0, 1) tuple A
(Q, E, o, qo: p) such that (1) Q, E. and qo are defined as in Def. I. (2) 8: Q Σ + (Q x K) U {0} is the transition function, and (3) p: Q + K is the accept weight function. If ō(q.a) (r, w). we say that A has a transition from q to r that seans a with
a/w
weight w, and we write q
r E 6.
Rather than accepting or rejecting a string, WDFA assigns it weight. The weight of a path is the product of the weights of its transitions and the accept weight of its last state. The weight of string is the weight of the path that scans it, or O if one does not exist. We can assign probabilities to strings with the real semiring (R22. +, x, 0, 1) or, for numerical stability, the log semiring (R { {-oo}, log( log(exp(-) (xp(())= + exp(-)), + 000 0). A WDFA must constitute probability distribution in der to allow sampling from it. One way to achieve this is by locally normalizing the WFDA per state.
Definition 5. A WDFA A = (Q. 40. () over the real semiring is called probabilistic DFA
(PDFA) for all E Q ( ain "))))ee) p) + p(g) = 1, and A induces probability distribution
over E
3 METHOD
We now give a method for generating datasets of formal languages and training neural networks as recognizers. We address a number of challenges cited in past work, namely length-constrained sampling, negative sampling, and the paucity of the training signal when training on binary labels.
*This second condition, known tightness, is easily checkable in the case of WDFAs (Du al., 2023).
3

---

Published as a conference paper at ICLR 2025
3.1 DATASET GENERATION
Here, we describe how to generate a set of N string-label pairs for language L, where the length of every string falls in the range [Mmin, mmmx]] To do this, we will require two language-specific algorithms: (1) an algorithm for sampling a string w from L such that |w] E [Mmina Pmax (using a distribution to be described in $3.1.1), and (2) an algorithm for determining whether a string w > is a member of L. To generate N strings, we uniformly sample a label from {0, 1) N times, ensur- ing a balanced dataset, and we generate a positive 1$3.1.1) or negative ($3.1.3) string accordingly.
3.1.1 POSITIVE SAMPLING
The choice of probability distribution we sample from is important, as affects the quality of train- ing and evaluation; at a minimum, it should assign non-zero probability to all strings in L with lengths in [T'inu m We detail our choices below.
When L is regular, we assume we have a trim DFA A= (Q, 6, qo: F) that recognizes it. The set of actions that may occur at each state consists of its outgoing transitions and, if is an accepting state, acceptance. We convert A to a PDFA A' by assigning uniform probabilities to these actions at each state (details in Algorithm 1). p. denote the probability distribution defined by A'' and W P.A'
distributed string-valued random variable. Let NA {n E [Mmin Rmax]] Ew E Σ", (w)) > 0}. First, we sample a length n uniformly from NA'. Then, we sample string from the conditional distribution P. (W| [W| = n.) This amounts to sampling from the distribution
1
p(w) = 1[ [wo] E Nar]
| PA
(W (W- = w [ = |w])-
We will show how to sample from NA and p.v' (W) [W| n) efficiently in $3.1.2. For non-regular languages, we use language-specing distributions detailed in App. E.
3.1.2 EFFICIENT LENGTH HENGGTH--ONSTRAINNEE SAMPLING FOR REGULAR LANGUAGES
How do we compute NA and sample from P. (W [W] = n) efficiently? One approach would be to construct PDFA for (W | n). We could do this by intersecting A' with DFA that recognizes Σ", which would take O(( + [()m)) time. This would result in a WDFA that not necessarily probabilistic, so as a prerequisite for sampling from it, we would need re- distribute its weights to locally sum to I (Def. 5). using a procedure known as weight pushing (Mohri, 2009) that would run in ((([Q))² 3 + (8|n) time. Supposing Amin 0, it would thus take Q(QQ) in " + _m)) time to do this for all lengths. This would not be scalable for our experi- ments, in which we sample strings up to length 7mma 500. Fortunately, we can improve this by a factor of O( using an object proposed by Snæejarnnasonn et al. (2025) called the binning semiring. The key idea is to share computation among the different lengths by running version of the weight pushing algorithm-onj once-that computes the normalized weights for all lengths. Instead of weighting the DFA with probabilities, we use vectors that bin probabilities by each length in [0, )
Definition 6. Let W = (K, t 8, 0. be a semiring, and let D E Zzo- For u E KK D+1, we write The tth order binning semiring with respect to the base semiring W is the semiring WD [K"
v = (vo, Vi...., Up)
O. D), where:
1
+
(u. E K
DD:10 0iis D)
(2a)
uu
Uy
2 Di-j
(u. K 05is D)
(2b)
1=0
def
0)
del (1,0..... 0)
(2c)
The indices of the vectors in the order binning semiring represent the values of an integer counter from 0 to D; the meaning of the counter depends on how the semiring is used. We will use
"This is directly comparable to the classical learning theory of Gold (1967), which assumes the availability of "text" of positive examples and an "informant" that provides labels.
4

---

Published as a conference paper at ICLR 2025
the counter to keep track of the number of symbols scanned by DFA, i.e., the length of a sampled string. To do
sampling from the PDFA A', we lift it to a Amax th -oder binning a/p, semiring-weighted DFA An as follows. For every transition y _ r in A', we set the weight of q S in AD to (O, p. 0, 0), indicating that the transition scans exactly one symbol with probability p. For every state with accept weight p. we set its accept weight in Ap to (p. .,....0) 0), indicating that it accepts (and scans symbols) with probability p. A similar interpretation applies to anything with a weight, including transitions, accepting states, paths, and strings.
Running a semiring generalization of weight pushing on An allows us to compute exactly the quan- tities we need for efficient sampling from ( [W] = rz). The key idea is that for every state and 0 S < D, it computes probability distribution over actions (transitioning
accepting) con- ditioned on scanning exactly i symbols in the future. Then Na is the set of all n for which we can perform any action at qu with nonzero probability, conditioned on scanning symbols in the future. The preprocessing step now takes ((Q) 2 n2 maxx |0) mxx) time, and sampling a string of length takes O( log oot time, where (0uut is the maximum out-degree of A. See App. B for details.
3.1.3 NEGATIVE SAMPLING AND MEMBERSHIP TESTING
To generate a negative example, we repeatedly propose a random string w until we achieve that w & L using a membership testing algorithm for L. We propose w in one of two ways, with uniform probability. Half the time, we uniformly sample a length n from [Mmin 7max]] then uniformly sam- ple from Σ". For many languages, this is very likely to produce a negative example, but one that is so superficially dissimilar to positive examples that the classification problem becomes too easy and fails to demonstrate the underlying algorithm. Prior work, therefore, typically uses language- specific rules to generate adversarial negative samples (Weiss et al., 201 8b; Bhattamishra et al., 2024; Someya et al., 2024). To keep our methodology more general, the other half of the time, we propose by sampling positive example and perturbing it with random edits (ef. Weiss et al., 2018a). More precisely, we (I) sample the number of edits K from a geometric distribution that heavily favors small K, and (2) iteratively apply K uniformly-sampled edits (single-symbol insertion, replace- ment, or deletion). See App. A for details. Typically, this is much more likely to produce negative examples that are difficult to distinguish from positive ones (see also our analysis in Figure 2).
Membership testing is necessary because it is possible that a random string w is inadvertently a member of L. DFAS have a straightforward (nn)-imme membership testing algorithm: start in the initial state, follow the unique w-scanning path (if it exists), and accept if it ends in an accepting state. For non-regular languages, we use language-specific membership testing algorithms detailed in App. E. A limitation of this rejection sampling approach is that it is impractical when the com- plement of L is small, i.e., when the expected probability of successfully sampling a negative string is small. For many languages of interest, including all those we test in this paper, this probability is reasonably large regardless of n, in which case is not an issue.
3.2 NEURAL NETWORK ARCHITECTURES
We compare three neural network architectures: (1) a multi-layer simple RNN (Elman, 1990) with a tanh activation function and learned initial hidden states, (2) a multi-layer LSTM (Gers & Schmid- huber, 2001) with decoupled input and forget gates and learned initial hidden states, and (3) a causally masked transformer encoder (Vaswani et al., 2017) with pre-norm (Wang et al., 2019; Nguyen & Salazar, 2019) and sinusoidal positional encodings. In all cases, the model, M, receives a string of symbols hg, hi...., h2 E R4, which are used to compute logits for the loss terms. For the simple RNN and LSTM, the hidden vectors are the hidden states of the last layer. For the transformer, the hidden vectors are the outputs of the last layer, and we always prepend a reserved BOS symbol to the input to compute hg. See App. C for details.
wi ...,, w,, Σ" as input and produces sequence of hidden vectors
We apply a learned affine transformation, called the recognition head, to the last hidden vector to classify whether the string is a member of the language. Let o(:) be the pointwise logistic function. Then, we model the probability of acceptance as
PM (w E L.) del awn hn + br):
(3)
5

---

Published as a conference paper at ICLR 2025
where wR E R and bR IR are learnable parameters. We say that the model accepts if Pas (w E L) 2 and rejects it otherwise.
3.3 TRAINING OBJECTIVES
In all experiments, we train neural network to classify whether an input string is in L by minimizing the binary cross-entropy of the recognition head (cf. Weiss et al., 2018b; Bhattamishra et al., 2023; van der Poel et al., 2024; Hahn & Rofin, 2024; Bhattamishra et al., 2024). For any probability p and proposition o, define the binary cross-entropy Ho (p) follows:
log(p) log(1 - p) otherwise.
i
(p)
(4)
We minimize the following loss function:
CR(M, w) des (WEL E L)).
(5)
However, using (M, w) as the only term in the training objective might not be enough. For one, it might be difficult to learn orchestrate large number of internal computational steps given only a single bit of information per example. Moreover, the gradient originates only from the last timestep, which is problematic for the RNN and LSTM, which are susceptible to the exploding and vanishing gradient problems. It is presumably for these reasons, in addition to the need for negative sampling, that most prior work has shied away from a pure language recognition training objective. One way to alleviate these issues is to provide the model with hints about intermediate computational steps. Indeed, a common setup in past work is to have the model predict, for each timestep f, the set of symbols that may appear at position & given the prefix Wet (Cleeremans et al., 1989; Gers & Schmidhuber, 2001; Schmidhuber et al., 2002: Rodriguez & Wiles, 1997; Suzgun et al., 2019a;b;c; Bhattamishra et al., 2020a;b:c; Ebrahimi et al., 2020). Other work uses language modeling, eschewing negative sampling entirely (Merrill, 2019; Hewitt et al., 2020: DuSell & Chiang, 2020: 2022; 2023; 2024; Liu et al., 2023; Akyürek al., 2024; Someya et al., 2024; Borenstein et al., 2024).
def wh W1-1
To this end, include experiments that add one or both of the following auxiliary loss terms to the training objective for positive examples: (1) a language modeling loss term, LLM(M, w)), which requires the model learn a distribution next-symbol prediction loss term, LNs w), which requires the model to predict whether each symbol may appear next at each position, given the prefix of w seen so far.
the next symbol at each position, and (2)
When we include the language modeling loss term, we add a language modeling head to the model that computes conditional probabilities Par(a) w<1) for each timestep and symbol a. We average cross-entropy over timesteps to get the loss term. We now define this formally. Let Egos def Σ U { and E E IR |EsosXX xd be matrix of output embeddings, which is tied to the input embeddings of the model. Then we define the loss term as follows:
(ar(a | wee)
def
softmax( Eh,
(1 1 EEOS)
(6a)
CLM(M,W) w) del
log Per (we wee)
(Wn+1 EOS).
def
(6b)
12
Likewise, when we include the next-symbol prediction loss term, we add next-symbol prediction head. For any string u E E", we define the set of valid next symbols NEXT as follows:
NEXT {a E Σ Ee E Σ', wav E U
E L}.
We use binary cross-entropy to train the model to discern whether each symbol a E Egos is in NeXTy(W<r)) by computing the probability Ps(a E N We average cross-entropy over symbol types and timesteps to get the loss term, which we denote formally as
Pad (a E NEXTy(W<d) df o(Wsshi-1 bys)a
(1 n 1:00 Egos)
(8)
Thii is often called next character prediction in prior work.

---

Published as a conference paper at ICLR 2025
LNS [M, (Ns(M, w)
def
(we E (EXT)(
(9)
n2
EEOS
where WNS E IR Exod xd and bNS E IR Eneil are learned parameters, We say that at each timestep I, the model predicts the set {a Egos Par(a NEXTz("<<)) 2 2). Unlike language modeling, next-symbol prediction adds additional information to the training data, as NEXTz(w<e) can include information about unobserved strings. For trim partial DFAs, we can easily precompute the set of valid next symbols for each state based on the outgoing transitions (Algorithm 6). We use language- specific rules for non-regular languages (App. E). The full loss function with all terms is
[(M, w) def CR(M, w) + ALM w) ANs
(10)
where ALM; ANS E R20 are coefficients that determine the importance of each auxiliary loss term. Whenever an auxiliary loss term is not included, this is equivalent to setting ALM or ANs to O. Note that we never include them for negative examples. When computing the loss for whole minibatch of examples, we average the loss [(M, w) of the individual examples.
3.4 COMPARISON TO PRIOR WORK
Many past papers have used neural networks for language recognition, but each uses a slightly dif- ferent methodology. Our work is attempt to unify this methodology. to extend it to the broadest possible class of languages, to compare different training objectives, and to spur theoretically sound empirical work in the future. MLRegTest (van der Poel et al., 2024) proposes recognition setup that is specific to regular languages, whereas our method generalizes to any language that has tractable algorithms for length-constraie constrained positive sampling and membership testing, and whose comple- ment is not small. MLReg Test samples efficiently from regular languages with small complements by constructing a PDFA for the complement directly, but this technique is not available for many higher language classes. As for positive sampling from DFAs, they sample uniformly from the set of strings of length n, using an intersection-based approach similar to that described in $3.1.2. Their preprocessing step runs in [[)=)]lQ)mmmme (Trmaa mmmi (m time (App. F), whereas ours <[[
runs in Q(1Q) n + 18] ( time. Weiss al. (2018a) also employ a perturbation-based neg- ative sampling method that edits positive samples up to 9 times; we allow an unlimited number of edits and provide a way of analyzing the ground touund-truthha edit distance distribution in $5, Figure 2.
4 EXPERIMENTS
We test the performance of the three architectures in $3.2 on a variety of formal languages (Ta- ble 1) that have proven to be of particular interest in prior work, and that come from various lev- els of the Chomsky hierarchy. These include analogs of the transduction tasks used by Delétang et al. (2023). For each regular language, algorithms described in 13.1.2. For the other languages, we use language-specifie algorithms for length-constrained sampling and membership testing. We describe all languages in more detail in App. E. We call this collection of datasets FLaRe (Formal Language Recognition).
generate datasets using hand-crafted DFA and the
For each language, we sample a single, fixed training set of 10k examples with lengths in [0, 40). We run separate experiments with two different validation sets that are designed to address different scientific questions, each with 1k examples: a short validation set with string lengths in [0, 40), and a long validation set with string lengths in [0. 80). For any finite training set of strings, there are infinitely many valid ways of extrapolating to longer strings; we refer to the way that a neural net- work architecture disambiguates these possible solutions as its inductive bias. The short validation set reveals an architecture's 's inductive bias in the absence of any disambiguating information about how it should generalize to longer lengths, as in the experiments of Delétang et al. (2023). The long validation set, on the other hand, does include longer strings, and so the model's performance on strings that are longer than those in the training set modulates the learning rate schedule, early stop- ping schedule, and model selection. In this way, it is more in line with expressivity work that seeks to understand whether an architecture admits certain solution at all, regardless of its inductive bias.
We use 5 layers for all models in all experiments. We automatically adjust the hidden vector size d so that the number of parameters is close as possible to 64k, excluding extra parameters for language
7

---

Published as a conference paper at ICLR 2025
Table 1: Formal languages tested in this paper and included in FLaRe. For each language. we show the language class that it belongs to: regular (R), deterministic context-free (DCF), context-free (CF), or context-sensitive (CS). Each language does not belong the previous language classes. Let (w) be the number of times substring u occurs in let w;-va be w with its 1th symbol replaced with a, and let (x) be the little-endian binary encoding of x E 220- See App. E for details.
Class Language
Description
Example String
Even Pairs
{w E {o. 1} can (w) + (1o(w) is even]
010110
{aua a {0, 1), {0, 1)" J (e,
Repeat 01
{(01) 2 0}
010101
Parity Cycle Navigation
{w [0.1]* ci (w) is odd}
11011001
A sequence left (4), right (>), stay (=) moves on a
>>><>2
position cycle, then the final position (0-indexed).
Modular Arithmetic
Expression involving {+. x} and {0, 4), then the result mod 5. No operator precedence. Strings of balanced brackets with 2 bracket types and maximum depth of
1-3x2=1
D2ck-(2,3)
(())]
First
{1w (0, 1}
100010
DCF
Majority Stack Manipulation
{w E 10. c (u(w)) > cu(w)]
101101
A stack from bottom top, sequence of push and pop operations, and the resulting stack from top to bottom.
011 P
Marked Reversal
{wth" R w E {0, 1}
001 #11#100
CF
Unmarked Reversal
[ww"
(0, 13"}
081100
CS
Marked Copy
{w#w w E (0, 1)"}
001#001
Missing Duplicate
(ww) i E 10,
2/wl. (ww); = 1}
1_011101
Odds First
{aib) ... a..aa...aaaaa...........
...b. bn
01010=00011
0;0;, E [e,1):a (0,1,
Binary Addition
(()) (1) 2. Zgo3
110+01=10100
Binary Multiplication
(1)) U.j.i,kke Zzo)
110=0100=011
Compute Sqrt
(=))==[[LVz])) x, j.je Z2o]
01010=1 100
Bucket Sort
Sequence of integers in {1, then and the sorted sequence.
45134#13445
modeling and next-symbol prediction heads. This ensures that all models are of comparable size across architectures and languages. For the simple RNN and LSTM, d is the size of the hidden state vectors. For the transformer, d is the model size dmodel- Every time we train model, randomly sample certain hyperparameters (Bergstra & Bengio, 2012), namely initial learning rate, minibatch size, and (when required) ALM and ANS- For every combination of architecture, loss function variant, and type of validation set, we train 10 models. We use four loss function variants: recognition with(out) language modeling and with(out) next-symbol prediction. Therefore, for every architecture and validation set, we train 40 models. See App. D for details.
5 RESULTS
To test whether model has learned the underlying recognition algorithm, our evaluation focuses on the ability to generalize to inputs that are longer than those seen in training (cf. Delétang et al., 2023). In Table 2, we show recognition accuracy on test with string lengths in [O, 500). It has 5,010 examples, an average of 10 examples per length. Under "Inductive Bias," we select the loss function with the highest mean accuracy on the test set from among the models trained on the short validation set, and report this mean accuracy. Although performance on the validation set, this would result in noise due to the vagaries of model selection; find that the mean accuracy that each architecture converges to when aggregated across multiple runs is more informative. Under "Expressivity." we show the maximum test accuracy across all 40 models trained on the long validation set. See unabridged results and additional metrics in App. G.
could select single model based on
We find that the RNN and LSTM outperform the transformer in most cases. In the inductive bias experiments, the transformer outperforms the RNN and LSS only on Even Pairs, First, and Major-
8

---

Published as a conference paper at ICLR 2025
Table 2: Accuracy on test set with strings in the length range [0, 500]. The training data in the length range [0, 40). "Inductive Bias" uses validation data in the length range [0, [0,40). We show mean accuracy and standard deviation across 10 runs for the loss function with the highest mean accuracy the test set. "Expressivity" uses validation data in the length range [0, 80). We show maximum aceuracy across all runs of all 4 loss functions. "Tf" = transformer, "RNN" = simple RNN, "LSTM" LSTM. Best scores among all three architectures are in bold.
Inductive Bias
Expressivity
Language
Tf
RNN
LSTM
Tf
RNN
LSTM
Even Pairs
1.001
0.60
0.83
1.00
1.00
1.00
Repeat 01
0.72+
0.97
0.97
0.86
1.00
1.00
Parity
0.56
0.71
0.90=2.20
0.60
1.00
1.00
Cycle Navigation
0,84
0.93
0.90
0.93
0.93
0.93
Modular Arithmetic
0.69
1.00
0,98+0003
0.88
1.00
1.00
Dyck-(2,3)
0.70
0.95
0.82
1.00
0.98
First
0.98 4:004
0.80
0.94
1.00
1.00
1.00
Majority
:.004
0.90
0.95
1.00
0.95
1.00
Stack Manipulation
0.66
0.84
0.75
0.87
0.93
0.91
Marked Reversal
0.64-10.12
0.70
0.74 0.74
0.87
0.95
0.95
Unmarked Reversal
0.58
0.72
0.76 0.76
0.63
0.81
0.88
Marked Copy
0.
0.76
0.69 00.15
0.86
0.95
0.95
Missing Duplicate
0.66
0.82
0.85
0.86
0.95
0.94
Odds First
0.59
0.79
0.67
0.86
0,95
0.96
Binary Addition
0.64-10.13
0.74
0.74
0.88
0.92
0.92
Binary Multiplication
0.70
0.74
0.78
0.92
0.92
0.92
Compute Sqrt
0.67 10.10
0.78
0.84
0.86
0.89
0.89
Bucket Sort
0.63
0.84
0.69
0.88
0.96
0.83
ity. In the expressivity experiments, is never the best (except by a hair on Binary Multiplication), and it only outperforms the LSTM on Bucket Sort. In terms of languages that the architectures can solve perfectly in the expressivity experiments, all architectures are limited to regular languages and Majority (Figure 1). The transformer almost reaches, but does not quite reach, 100% accuracy on Majority. We do see differences based on language's ' sensitivity, i.e., the tendency that changing a bit in string changes its label. Transformers struggle on high-sensitivity languages (Parity) and do well on low-sensitivity languages (Even Pairs, First), in accordance with prior work (Hahn, 2020; Bhattamishra et al., 2023; Hahn & Rofin, 2024). The LSTM outperforms the RNN some lan- guages that involve long-range dependencies (Even Pairs, First), likely thanks to its memory cell. The LSTM can use its memory cell set of counters, which is useful for certain languages (Weiss et al., 2018b); accordingly, we see that it outperforms the RNN on Majority, but surprisingly not on Bucket Sort. Although Yao et al. (2021) gave construction showing that the transformer can recognize bounded Dyck languages, we see that it struggles on Dyck-(2,3).
Although it is possible, in principle, for model's inductive bias to differ substantially from its pressivity, we see a remarkable consistency between inductive bias and expressivity. As expected, all expressivity scores are higher than the corresponding inductive bias score. However, the ranking of the architectures remains the same between inductive bias and expressivity for almost all languages; it only changes slightly for Missing Duplicate and Odds First, and more noticeably for Bucket Sort.
Certain auxiliary loss terms do help in isolated cases: for example, next-symbol prediction is crucial for the RNN to learn Even Pairs (Table 4). On the other hand, they are sometimes detrimental; for example, language modeling results in lower accuracy for the LSTM on Parity (Table 6). However, no term has a consistently positive or negative impact across languages and architectures (Table 3). In fact, recognition alone is the most frequent best loss function, followed by next-symbol prediction; loss functions that include language modeling help the least often. Remarkably, the RNN gets a mean accuracy of 100% in the inductive bias experiments for Modular Arithmetic, using only recognition training objective.
We accuracy ceilings in the expressivity results for Cycle Navigation, Binary Addition, Binary Multiplication, and Compute Sqrt. To investigate this, we looked at the examples with the highest cross-entropy. For Cycle Navigation, all architectures struggle negative examples that have the

---

Published as a conference paper at ICLR 2025
Repeat 01
Dyck-(2, (2,
Cross: Entropy
2
2-
1
Incorrect
1 Incorrect
50
100
150
50
100
Edit Distance
Edit Distance
Figure 2: Recognition cross-entropy (lower is better) as a function of edit distance for the trans- former model shown under "Expressivity" in Table 2, on a separate dataset of 50 negative examples the length range [0, 500]. The dashed lines show log 2, the threshold for incorrect predictions. Despite being trained on a large proportion of negative examples with low edit distance, the trans- former still struggles on examples that resemble positive examples.
right format but the wrong digit at the end;? in contrast, the RNN and LSTM got perfect accuracy on related task in Delétang et al. (2023). On Binary Addition, the transformer and RNN/LSTM fail for different reasons. The RNN/LSTM only misclassify negative examples that have the right format but incorrect arithmetic, but the transformer also misclassifies positive examples and negative examples that have extra +, x, or = symbols. The RNN and LSTM fail on Compute Sqrt for dissimilar reasons; the RNN sometimes accepts invalid formats. Using larger models does not solve the problem; in most cases, accuracy does not improve with model size (App. H).
How does using recognizers instead of string-to-string functions affect our findings? The most com- parable sets of experiments are those of Delétang et al. (2023, Tables B. and B.5) and our inductive bias experiments. Whereas they found that transformers struggle on Even Pairs and the RNN/LSTM excel, we see the opposite. We both show that transformers struggle on Parity. Whereas they showed that the RNN/LSTM perfectly solve Cycle Navigation, our results show otherwise, perhaps because in our version, the model must additionally validate the format of the string rather than predict single digit. We see the same model ranking on Stack Manipulation, but not on Marked Reversal, Odds First, Binary Addition, Binary Multiplication, Compute Sqrt, and Bucket Sort. Notably, the RNN overperforms in our experiments, possibly due to our use of dropout, multiple layers, and a different activation function. Whereas Delétang al. (2023) found that accuracy often decreases sharply with length, we find that recognition cross-entropy is usually stable (App. l).
In order to examine how the similarity of negative examples to positive examples affects classifica- tion difficulty, for Repeat 01 and (2, 3), we plot the transformer's recognition cross-entropy vs. the minimum edit distance between a string and any string in the language in Figure 2 (we do not plot the RNN and LSTM because they get almost 100% accuracy). Note that the number of edits K performed in $3.1 is an upper bound for, but not necessarily equal to, the true edit distance. We give formal defimitions and algorithms for computing edit distance in App. J. We do see that for both languages, the lower the edit distance is, the more the transformer struggles, particularly near I and 2 edits. This confirms that strings with few perturbations are indeed adversarial (cf. van der Poel al., 2024), even when the training distribution is highly skewed toward few edits.
CONCLUSION
We have proposed general method for training neural networks recognizers of formal languages, filling a crucial gap between formal results and experiments meant to support them. We also gave a new, efficient algorithm for length-consstn consth-conttrained sampling of strings from regular languages. We pro- vided results for RNNs, LSTMs, and transformers on a wide range of formal languages commonly used in prior work, showing that RNNs and LSTMs often outperform transformers. An interesting question to address in future work is why transformers perform so much better on natural language than formal languages. We tested auxiliary training objectives that have been previously used as a proxy for recognition and found that these do not improve model performance reliably. We have publicly released our datasets benchmark called FLaRe (Formal Language Recognition). Using larger models, more adversarial examples, and more training data did not alleviate this issue.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Leonardo Nevali, Vésteinn Snæebamarsoon, and Paul Soulos for helpful discussions, and we thank Dakotah Lambert for answering questions about MeRegTest's ungth-consttraiee sam- pling algorithm. Anej Svete is supported by the ETH AI Center Doctoral Fellowship. Josef Valvoda is funded by the Nordic Programme for Interdisciplinary Research Grant 105178 and the Danish National Research Foundation Grant no. DNRF169.
REFERENCES
Ekin Akyürek, Bailin Wang, Yoon Kim, and Jacob Andreas. In-context language learning: Archi- tectures and algorithms. In Forty-first International Conference on Machine Learning, Vienna, Austria, July 2024. URL https: httpss///penrreveew wwt..e/ooroommd322Crrrrr
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13(10))281-305 2012. URL /ttttp::/jmmr..oe http:ps://mlrrrrr//eee/ee prtpp//s////p//////////// bergstral html.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing (EMNLP), pp. 7096-7116. Association for Computational Linguistics, November 2020a. doi: 10. 11533//1122220.mmllmmmaaaaa
URL https: pattps://aclanthooloog org.oo2g///22/ emnlp-main. 576.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the practical ability of recurrent neural networks recognize hierarchical languages. In Donia Scott, Nuria Bel, and Chengqing Zong (eds.), Proceedings of the 28th International Conference on Computational Linguistics, pp. 1481 1 1494, Barcelona, Spain (Online), December 2020b. International Committee on Computational Linguistics. doi: 18.18 10.18855//1/2020.cooo 1tt0://colin00mmaaai...a... main. 129. URL httpss//aae hwwooooloooooogyyyyooooooooooooe org/2020. coling-main. 129.
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling- In Raquel Fernández and Tal Linzen (eds.), Pro- ceedings of the 24th Conference on Computational Natural Language Learning, pp. 475. Association for Computational Linguistics, November 2020c. doi: 00.18653/1/2022.comlll URL htttps://aclaan ootts:://allanthoologyy org/2020 www.:/.oooo.....111111
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in trans- formers and their ability to learn sparse Boolean functions. In Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Associa- tion for Computational Linguistics (Volume 1: Long Papers), 5767-5791. Association for Computational Linguistics, July 2023. doi: 10.18653/w1/2023.cee aon.oon...ll- URL https: //aclanthology. 2023. acl long. 317.
Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 36002-36045. Curran Associates, Inc., December 2024. URL https://papers: nips. cc/ cttpcc/ppppppeeeeeeeeeeeeeeee.ee pappr_ffpllll /ptps/appr/////eee /2024/aash/ 1f639b22b77b3cc6ddaaa00 6f ortraaaoooooeeeeeea-oooaaaettooo
html..
Nadav Borenstein, Anej Svete, Robin Chan, Josef Valvoda, Franz Nowak, Isabelle Augenstein, Eleanor Chodroff, and Ryan Cotterell. What languages are easy to language-model? A perspec- tive from learning probabilistic regular languages. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 15115-15134 Association for Computational Linguis- tics, August 2024. doi: 1/2.65//l//224..a// long..00...
URL https: /attt:://aclaatholloggo .org//ggg org/
2024.acl- aol.long..80 807.
David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting
11

---

Published as a conference paper at ICLR 2025
of the Association for Computational Linguistics (Volume I: Long Papers), pp. 1664-7664. As- sociation for Computational Linguistics, May 2022. doi: 10.18655/w1/2022..lllmoo.gg URL https://aclanthhology http:://elaattooooy...g////22222 acl-oon
Axel Cleeremans, David Servan-Schreiher, and James L.. McClelland. Finite state automata and simple recurrent networks. Neural Computation, 1(3):372-311, April 1989. doi:
00.11622nccco1199...3.3777 URL https: /ditrct//irrett..... mi edt//neco/articleeeeeeeeeeeeeeee http://rtccle-abstrat/1133 372/5483/Finite- http://eearinnetttttattttttaaaaa and-tta-ddd-mmmmllm-
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the Chomsky hierarchy. In The Eleventh International Conference on Learning Representations, May 2023. URL
Li Du, Lucas Torroba Hennigen, Tiago Pimentel, Clara Meister, Jason Fisner, and Ryan Cotterell. A measure-theoretic characterization of tight language models. Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Proceedings the 61st Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 9744-9770, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 1..18663/112033.allloong hwwphhhoolgy.ooooo..oooooo /ttg/ acl acl-long.54d 553/.
URL
Brian DuSell and David Chiang. Learning context-free languages with nondeterministic stack RNNs. In Proc. CoNLL, pp. 507-519. Association for Computational Linguistics, November 2020. doi: 10.18653/1120220.oomll/ 1.411 URL https: httpp:://alaanthollgg. wtrg/2020.comm 41/.
Brian DuSell and David Chiang. Learning hierarchical structures with differentiable nondetermin- istic stacks. In International Conference on Learning Representations, Online, April 2022. URL https://openrree
Brian DuSell and David Chiang. The surprising computational power of nondeterministic stack RNNs. In The Eleventh International Conference on Learning Representations, Kigali, Rwanda, May 2023. URL https: http:/iwwwwwweeeeeeeeeeeeeeeeeee wttp://wwwweeeoommmddddd////---0
Brian DuSell and David Chiang. Stack attention: Improving the ability of transformers to model hierarchical patterns. In The Twelfth International Conference on Learning Representations, May 2024. URL /ttps://openreviit www.reeeewweeweereeeeeee.
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize Dyck- languages? In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Associa- tion for Computational Linguistics: EMNLP 2020, pp. 4301-4306. Association for Computa- tional Linguistics, November 2020. doi: 10. 18653/v1/2020 1/223//1/0 findings-emmlp.3884 URL https: // //aclanthology. htwpchhoolgg.ooggg/egoooo
org/2020 indings-emnln 384.
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 5793- 5831. PMLR, July 2022. URL htwph:tts///ppp http:ps///ppoceeeiggss...... wtt.....rree////22/eeeemmmaaa3
html.
Jeffrey L. Elman. Finding structure in time. Cognitive Science, 14(2):179-211, April-May 1990. doi: 10.10160036-022110000000022 articlee/p11/3344219999000
URL https://www.scienced/ wttp:/ett.ccccc.ceeeeeeeeeeee
Robert W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, June 1962.
doi: 10.1145/367766.36666 168. URL https::///// //dl acm
http://ll.acc.oo//oooo/o//////// org/m////////..oo 1145/367768 3681 68.
Felix A. Gers and Jürgen Schmidhuber. LSTM recurrent networks learn simple context-free and context-sensitive languages. IEEE Transactions on Neural Networks, 1333) Novem- ber 2001. doi: 10. 1 19997799.66,,66 URL httpst::/ieeeeppprrrrre ieee. htt.://re......oeeeeoooooe/n///e
12

---

Published as a conference paper at ICLR 2025
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth Interna- tional Conference Learning Research, pp. 249-256. PMLR, May 2010. URL hat.https//ppooeeee //roceedg///...sdngg.... mlr .press/ v9/glorot10 0a html. hammml..
Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine
E. Mark Gold. Language identification in the limit. Information and Control, 10(5):44-474, May 1967. doi: 0211016/80011--95566677 165-55. URL https:/www.scienccdrree. com/ scieence/articcle//i////////////
1655.
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020. doi: 10.1 1.01 URL https://aclanthonn
wrw.:org///ea/ tacl-1.11.
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the
Association for Computational Linguistics (Volume 1: Long Papers), pp. 14973-15008, Associ- ation for Computational Linguistics, August 2024. doi: 10.18653/v1/2024 acl-long.800 URL
https://aclanttien www.e/44...22222... a1144..cllaa0 acl-oog............... 800.
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. RNNs can generate bounded hierarchical languages with optimal memory. Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference Methods in Natural Language Processing (EMNLP), pp. 1978-2010. Association for Compu- tational Linguistics, November 2020. doi: 10.18653/v1/2020.ccmm eenll- main, 156. URL https:
Empirical
// wwwpanttooooooooooooooooe emnlp-main. 156.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Lan- guages, and Computation. Addison-Wesley Longman Publishing Co., 3rd edition, July 2006.
URL https::////. /dll acm. wwtg/////////eeeoeeeeeee httgg/////boo///.////// 1195416
Thomas F. Icard. Calibrating generative models: The probabilistic Chomsky-Schützzenlee Schützenberger hier- archy. Journal of Mathematical Psychology, 95, Jamuary 2020. doi: 10. 2mp.0099..... URL https: /wwww wwwenceiiiieeeeeeeeeeeceeeeeeeee com/ httpe//ccccccceeeeeeeeeeeeeeee/e /ttp://rraa.aeee/////00022211110
Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. Repeat after me: Trans- formers are better than state space models at copying, June 2024. URL. https://arxiv.. abs/2402. 0 01032. arXiv:2402.01032.
Aravind Joshi. Tree adjoining grammars: How much context-sensitivity is required provide reasonable structural descriptions?, pp. 206-250. Studies in Natural Language Processing, Cam- bridge University Press, 1985.
Diederik Kingma and Jimmy Lei Ba. Adam: method for stochastic optimization. In The Third International Conference for Learning Representations, San Diego, California, USA, May 2015. URL https://arxis: httpr/iv.org/bb////1//./ https/1112.99900 6980.
Daniel J. Lehmann. Algebraic structures for transitive closure. Theoretical Computer Science, 4(1): 59-76, 1977. doi: 10.1001603304439557777956655 URI. https: / //wwww s sci eec.eiieeeettt......mm com/
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. The Eleventh International Conference on Learning Representa- tions, May 2023. URL https::/openrevieee www.:e/eeoooummiideeeeeooooooFF
William Merrill. Sequential neural networks as automata. In Jason Eisner, Matthiss Gallé, Jeffrey Heinz, Ariadna Quattoni, and Guillaume Rabusseau (eds.), Proceedings of the Work- shop Deep Learning and Formal Languages: Building Bridges. pp. 1-13, Florence, Au- gust 2019. Association for Computational Linguistics. doi: 10.18653/v1/W19-3000 https://acllnthhlogy..rrrg org/w19 3901.
URL
13

---

Published as a conference paper at ICLR 2025
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. A formal hierarchy of RNN architectures. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, pp. 443-459, Online, July 2020. Association for Computational Linguistics. doi: 11116///1/2022.aclmmii URL https: http::::///claathoooggyy org/ acl -main.43..4
William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843-856, August 2022. doi: 16. a 00493. URL https:: //direct wtt.etttttttttteeeeeeeeeeee 10. 10.1162/tacl.2 http://tccla..9999.... 00493/1 2604//12260555 2ttp//////////ttttatteeeeeeeeeee Testturated-Trnsffrmmom
are Sarre-Costaant-eeee
Mehryar Mohri. Weighted Automata Algorithms, pp- 213-254. Springer Berlin Heidelberg, 2009. doi: 10. 978-3-640 602-01121111 492--5.66
URL https::/link..pringerr
springer. com/chapterr110110000
Toan Q. Nguyen and Julian Salazar. Transformers without tears: Improving the normalization of self-attention. In Jan Niehues, Rolando Cattoni, Sebastian Stüker, Matteo Negri, Marco Turchi, Thanh-Le Ha, Elizabeth Salesky, Ramon Sanabria, Loic Barrault, Lucia Specia, and Marcello Federico (eds.), Proceedings of the 16th International Conference Spoken Lan- guage Translation. Association for Computational Linguistics, November 2-3 2019. URL https://aclannthologg org/2019 iwslt-1.11 17.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy. Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, perforreform deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., December 2019. URL https: / Abstrratttt.
nips. cc/ cttpccpppppppppeeeeeeceeeeeeeeee seaper_filsss fiwes/llleppeee paalee//papr//2119
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is Turing-complete. Journal of Ma- chine Learning Research, 12(75):1-35, March 2021. URL httpp://jjnr..oggppprrr prppp////////2/////// 20- 302.
Paul Rodriguez and Janet Wiles. Recurrent neural networks can learn to implement sensol--enssitive counting. In M. Jordan, M. Kearns, and S. Solla (eds.), Advances in Neural Information Pro- cessing Systems, volume 10. MIT Press, 1997. URL https: httppe/d/ppoccediingg neun iirrrips.co cc/ paper Files/paper/1990 http:///999//hhh1000220007745330
(tt000455111f2222f2 7ffd281
html..
Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Ben- nani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generaliza- tion of transformers. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Pro- ceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 1889-1900 Association for Computational Linguistics, July 2023. doi: 10. 1/22533///003..acllses 161. URL https://aclanttott
org org/o0g3/ aww.sar.clssoo......m 161.
Jürgen Schmidhuber, Felix Gers. and Doug Eck. A comparison of simple recurrent networks and LSTM.
Learning nonregular languages: Neural Computa- lion, (49):2039-2041 September 2002. doi: 10. 101116220899766602322299999 https://direct. mit. wtwp//eetteiiiteeeeeeeeeeooooe/e httpee//rrrtiieeeeaarrrrr///////
URL
Hava T. Siegelmann and Eduardo D. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50(1):132-150, 1995. doi: 10.1006/jcss.1995 1995. 1013. URL
Michael Sipser. Introduction the Theory of Computation. Cengage Learning, 3rd edition, 2013.
Vésteinn Snæejarnarson, Josef Valvoda, Anej Svete, Brian DuSell, and Ryan Cotterell. Separating data scarcity from task complexity in language model evaluation, 2025.
14

---

Published as a conference paper at ICLR 2025
Taiga Someya, Ryo Yoshida, and Yohei Oseki. Targeted syntactic evaluation on the Chomsky hierar- chy. In Nicoletta Calzolari. Min-You Kan, Veronique Hoste. Alessandro Lenci, Sakriani Sakti, and Nianwen Xue (eds.), Proceedings of the 2024 Joint International Conference Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pp- 15595-15605. ELRA and ICCI., May 2024. URL www.hhtsss/aaaaantoll.oooo/ wwwp://twwoooooooo/22ee.... 1rec-main. 1356.
Lena Strobl. Average-hard attention transformers are constant-depth uniform threshold circuits, August 2023. URL htwps: //arxvv.a/iivva//aa httpr/ivvoorg/b///000000 03212. arXiv:2308.0321
Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, and Ashish Sabharwal. Transformers 02040. MxXiv:2404.02044
as transducers, April 2024a. URL DBLLttss///axxl.orr////////
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? A survey. Transactions of the Association for Computational Linguis- tics, 12:543-561, 2024b. doi: 10. 111162ttacla.00666 URL httpt:://aclaeeae hattooloyy org/2024. tac1-1.30.
Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. LSTM networks can perform dynamic counting. In Jason Eisner, Matthias Gallé, Jeffrey Heinz, Ariadna Quattoni, and Guillaume Rabusseau (eds.), Proceedings of the Workshop Deep Learning and Formal Languages: Building Bridges, pp. 44-54, Association for Computational Linguistics, August URL https://aclanthoooggy wrg.://..org//.. wttp 3905.
2019a. doi: 10.18653/v1/W19-3000
Mirac Suzgun, Yonatan Belinkov, and Stuart M. Shieber. On evaluating the generalization of LSTM models in formal languages. In Gaja Jarosz, Max Nelson, Brendan O' Connor, and Joe Pater (eds.), Proceedings of the Society for Computation in Linguistics (SCiL) 2019, pp. 277-286, 2019b. doi: 10.7275/6020-4411. URL
or org/w19-g0 28.
Mirac Suzgun, Sehastian Gehrmann, Yonatan Belinkov, and Stuart M. Shieher. Memory-augmented recurrent neural networks can learn generalized Dyck languages, November 2019c. URL https:
//aaxiv..rg/abs///// 1ttps///9911..31111111 03329, arXiv: 1911:1321.3399
Sam van der Poel, Dakotah Lambert, Kalina Kostyszyn, Tiantian Gao, Rahul Verma, Derek An- dersen, Joanne Chau, Emily Peterson, Cody St. Clair, Paul Fodor, Chihiro Shibata, and Jeffrey Heinz. MLRegTest: benchmark for the machine learning of regular languages. Journal of Machine Learning Research, 25(283):1--5, 2024. URL https: //jmrr orggpappes//22 23-0518. 15mml1...tml.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Gareet (eds.), Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., December 2017. URL https:/ nips. cc/ cc/paper apappr_fille files/paperr/00 /217/hash//// 3f5ee243547dee9)
c4a0533acc2a845aaaaaaa wabbtract.htm
Qiang Wang, Bei Li. Tong Xiao, Jingbo Zhu, Changliang Li. Derek F. Wong, and Lidia Chao. Learning deep transformer models for machine translation. In Anna Korhonen, David Traum, and Lluís Mårquez (eds.). Proceedings of the 57th Annual Meeting of the Association for Compu- tational Linguistics, pp. 1810-1822. Association for Computational Linguistics, July 2019. doi: 11186553v1/P191111 URL https: http://aacaannnolgy.ooo org/
Stephen Warshall. A theorem on Boolean matrices. Journal of the ACM, 91):111-2, January 1962. doi:
URL https:: //dl. //dl.acmm. acm. wwtp/oi//////oooooo/ 1111/111111111 105. 327
Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting automata from recurrent neural networks using queries and counterexamples. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Ma- chine Learning Research, pp. 5247-5256. PMLR, July 2018a. URL https://proceeding wttppppss////wwiissssse hatm.ll1.....m....
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision RNNs for language recognition. In Iryna Gurevych and Yusuke Miyao (eds.), Pro- ceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume
15

---

Published as a conference paper at ICLR 2025
2: Short Papers), pp. 740-745. Association for Computational Linguistics, July 2018b. doi: 10. 10.188633/11/11--225 21177 URL https://acllanthol.gg org/P18-2117
Kaiyue Wen, Yuchen Li, Bingbin Liu, and Andrej Risteski. Transformers are uninterpretable with myopic methods: case study with bounded Dyck grammars. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural In- formation Processing Systems, volume 36, pp. 38723-38766. Curran Associates, Inc., De- cember 2023, URL https: https://proceeedings..o neurips cc/ paper wtpppafilleseeeeeaeeeaaaaaaaaaep /iLee//paper/222//aasss 79balb827d3fc58e ciat ConfeeenceCoeeeeeeeeeeeeoeo html.
Andy Yang. David Chiang, and Dana Angluin. Masked hard-attention transformers recognize ex- actly the star-free languages. The Thirty-eigtth Annual Conference on Neural Information Pro- cessing Systems, Vancouver, Canada, December 2024. URL /ttttps://openeeeeeee www.rrreeee..eeeorumm.. id=FBMsBdHOyz.
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention net- works can process bounded hierarchical languages. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.). Proceedings of the 59th Annual Meeting of the Association for Com- putational Linguistics and the 11th International Joint Conference on Natural Language Pro- cessing (Volume I: Long Papers), pp. 3770-377 3785. Association for Computational Linguistics, August 2021. doi: 10.18653/v1/2021..2m www.0221..cllllo aacllllllonng longlllon..... 292. URL https://aclanthhooogy 200.ol//g...../211....
acl-long.29 292
Wojeiech Zaremba, Ilya Sutskever, and Oriol Vinyals. Recurrent neural network regularization, February 2015. URL
2329.
A DETAILS OF PERTURBATION SAMPLING
We perform perturbation sampling as follows. Given a positive string w E L with |w] e [mmina Remax], we first sample a number of edits K from geometric distribution with success probability of = J. Note that this highly skewed toward small K, ensuring that strings with few edits (i.e., similar positive examples) randomly apply an edit as follows. Let w' be the current edited version of w. We uniformly sample type of edit: insertion, replacement, beyond max and deletion if it would decrease it below Amin- We disallow replacement if [>] 1. For each insertion, we uniformly sample an insertion position from {1...., |w/| 1} and sym- bol to insert from Σ. For each replacement, we uniformly sample a replacement position from (1...., [w'l) and new symbol from Σ {w(]. For each deletion, we uniformly sample deletion position from
well-represented in the dataset. Then, K times,
deletion. We disallow insertion if it would increase [w']
[w'].
B DETAILS OF LENGTH-CONSTRAINEE SAMPLING FOR REGULAR LANGUAGES
Here, we discuss our contt-ccnntt sampling algorithm for regular languages, and the binning semiring, in more detail.
B. FURTHER EXPOSITION OF THE BINNING SEMIRING
Notice that if u is vector whose only non-zero element is u, and is vector whose only non-zero element By, then u @ vector with the value u, 6 By at index + j and 0 elsewhere. More generally, Eq. (2b) convolves the two vectors, in effect marginalizing over all ways of reaching count of for each 0 <i< D.
In the case of Ap ($3.1.2), in which all transition and accept weights are vectors with at most one non zon-zero element, the weight of any path is also a vector with at most one non-zero element, whose index is equal to the number of symbols the path scans, and whose value is the product of the original transition probabilities. We combine the weights of multiple paths by adding them elementwise (Eq. (2a)).
16

---

Published as a conference paper at ICLR 2025
When the base semiring is the log semiring, as in Ap. the @ operation be computed in O time, and the 2 operation (Fq. (2b)) in O(D2) time. When the base semiring is the real semiring, the operation can be computed only O(D log D) using the fast Fourier transform, but since this results in underflow when multiplying many probabilities, we do not use it in this paper.
B.2 CLOSED SEMIRINGS
key component of our method is the semiring generalization of weight pushing (Mohri, 2009). Weight pushing sums over an infinite number of paths in a WDFA, which requires the ability to perform infinite summations in its semiring.
Definition 7. Let (IK, B 8, 0, 1) be a semiring. Let a 8 a, and a" + i- oi Ifa" is defined and in for all K. we say the semiring is closed.
In the real semiring, a² I-o In the log semiring, a* log T-exp = - log(1 exp(a))
a semiring W = (IK, + 60, 0, 1) is closed, so is any -rder binning semiring with respect to W, has the following closed-form
i.e. WD PK+++ solution.
①). We write v def
(0 (o0); ; = = 2
1
U
Rijj
(0 S S D)
(11)
A derivation is given by Snæbjarnarson et al. (2025). The elements (x0), can be computed in order of increasing i. Assuming @ 80, and run 0(1) time, the total time complexity is (D2)), since it involves (DD) iterations, each of which takes O(D) time.
B.3 ALGRITHTS
Here, we describe our algorithms for sampling strings from regular languages more detail. Given DFA A and length range [mimn Rrmaa). we run the following steps and for all for each language:
1. convert A to PDFA A', then convert A'' to a WDFA Ad over the 1mmax th thoorder binning semiring with respect to the log semiring in (([Q) + [o])) time (Algorithm 1);
2. push the weights of AD get new WDFA A'D over the R'mxx" "oodder binning semiring with respect to the real semiring in O + |6l)n? time (Algorithm 2), using the backward algorithm (Algorithm 3) and Lehmann's algorithm (Algorithm 4);
3. compute the subset of valid lengths NA C [Pminn Rmax] in 0 Rminn) time (Algo- rithm 5);
4. precompute the next-symbol sets for each state in O(IQ) + [8]) time (Algorithm 6).
The total runtime of these preprocessing steps is " + |6] n m being dominated by the weight pushing step.
Afterwards, we can sample strings as many times as desired as follows:
1. uniformly sample a length n from NA in (()) time;
2. sample a string of length with next-symbol sets in O(n log (lout) time, where |8] out is the maximum out-ee of the automaton (Algorithm 7).
17

---

Published as a conference paper at ICLR 2025
Algorithm Convert partial DFA a WDFA AD over the Tmmax th -order binning semiring with respect to the log semiring. This implicitly creates an intermediate PDFA A' over the real semiring with uniform probabilities. Time complexity: (([QQ) + (6 [m)))
def LIFT LIGHWFIGHTS (Q, E,, 6,,,, fo, F), 1mmax):
2. let AD = (Q, x2, 8", 2o. p) be new WDFA over the Tmmx -order binning semiring with respect to the log semiring
3. for q E Q:
k 0
for q 9 : 5.
t- k +1 q E :
8.
+ k+1
9.
p log
DSt the probability &/ (in log space)
10.
for
add 00.............0---
11.
r to
i E F
13.
p(g) t (p. -0,,... -20)
else
15.
p(q) f (-00.... -00)
return Ap
Algorithm 2 Weight pushing Ap. where Ap is WDFA over the 1ih -id-rrder binning semiring with respect to the log semiring. Given Ap, produce WDFA A', over the Dth-order binning semiring with respect to the real semiring that is suitable for length-constrained sampling (Algo- rithm 7). Also return the allsum weight z, which can be used to compute the set valid lengths (Algorithm 5). Time complexity: O(((Q) + (3)
def PUSHWEIGHTS(
(Q, E, 4o, p)):
2. + B-CCKWARD(AA)
3. let A', (Q, E, 8', qo. p¹) be a new WDFA over the tth -od-erder binning semiring with
respect to the real semiring
for q Q:
5. let be an empty mapping from Σ to (HU
6 for 4 a/v
E 8: 7. Taa + rr T - softmax :a.
DCnnvert log probabilities to normalized probabilities. This may safety return NaN for columns with all -co.
for 9
add 9 a/Tial 8:
8'
11. 2 Biqu] return (Ab:2)
18

---

Published as a conference paper at ICLR 2025
WDFA A over the closed semiring (IK, 3 8, 0, complexity: O |2) Tel +TIQQ + Ta (ö]), where Ta. To. and T. are the runtimes of @, 8, and respectively.
Algorithm Backward algorithm
0, 1). Time
def BACKWARD(A= &. qo.
let A be a matrix indexed by Q x Q full of
for a/10 à
4. Alg,r] + Alg, r| @ w
A <- LEHMANN (A)
6. let /3 be a table indexed by Q
for Q:
8. B + + Alg,r] @ p(r)
rE
return ,
Algorithm 4 Lehmann's algorithm for inverting matrix A KNNN in the closed semiring
(K, db, @, 0, 1). Time complexity: O + TT + N,,), where Ta, Tg, and T, are the run- times @ @, and ", respectively.
def LEHMANN(A):
for k = I..... N
let A' be N N matrix full of 0
a 6 Ak: k]"
5.
for I,...,
6.
for j = 1,...,, N
A Ali @ (Ai, A(k,))
7.
8.
- A'
9.
for k I,... N
10.
A[k; k]] t A(k: k) @
return A
minimum length Thmin and max- imum length Remax, where D 2 Tmmax. compute the set of valid lengths NA. The allsum weight must be the second output of Algorithm 2. Time complexity: O Rmin).
Algorithm Given allsum weight E (- (-o)))
def COMPUTEVALILLENTTIO 2 return {n {Tmin ...; Mmmax) Zn > 0G
Amin Temax) )
Algorithm 6 Given trim partial DFA A. precompute the next-symbol set for each state. Time
complexity: Q(QQ + ()).
def COMPUTENEXT(AL (Q, Σ, 8, qo. F));
2. let NEXT table indexed by Q
for q Q:
4. NEXT 4 +
for q Sre 8
6
add a to NEXT(g]
if q E F: add NEXT[g]
return NEXT
19

---

Published as a conference paper at ICLR 2025
Algorithm Sample a string of length n from WDFA A'D over the Dth binning semiring with respect to the real semiring, where D 2 Also output a sequence of + next-symbol sets. The DFA A'D must be the first output Algorithm 2, and NEXT must the output of Algorithm 6. Time complexity: (n log (6) lou)). where but is the maximum out-degree of A'D
def SAMPLE(AD = (Q, E, 4o p), n, NEXT):
2. 9 x 40
w <
4. 8 + [NEXT[a]}
for .,,..,,:
sample (a, ps where r)) vz for a/v r r bLog. time due to binary search.
7.
9 x+r
wa 9. append NEXT [g] to 8
return (w,s)
B.4 EXPLANATION AND DETAILS
The log semiring is used in Algorithm instead of the real semiring in order to avoid underflow.
Running semiring generalization of weight pushing on Ap allows us to compute exactly the quantities we need for efficient sampling from P. (W ||] =)). At every state, and for every $ i S D. it computes a probability distribution over (1) outgoing transitions and (2) whether to accept, conditioned A'. It does this by computing (1) for every transition, the sum of the weights all paths in Ap that start with that transition, and (2) for every state, the sum of the weights of all paths in AD that start and end at that state. Once we have these weights, which are vectors, if we locally normal- ize them elementwise Onn)-time sampling algorithm for sampling a string of exactly length n becomes straightforward (Algorithm 7). We start in qo and initialize counter to n. Repeatedly, we sample transitions from the normalized distributions for index i from the current state and decrement i for every symbol scanned. We stop when we sample an accept action (this happens implicitly in Algorithm after i == 1. the automaton is guaranteed by construction to accept that point). The set of valid string lengths NA is the set of all n for which we can take any transition or accept at qo, conditioned on scanning symbols in the future, with nonzero probability (Algorithm 5).
scanning exactly symbols in the future, according to the probabilities of
each state, get the aforementioned probability distributions. Now,
We now discuss details of the weight pushing algorithm. Let us define a path in a WDFA as follows (cf. Def. 12).
Definition 8. For any WDFA A (Q, 6, go, p). path is sequence of states and transitions
a1/w1, Y1 ... Fm-1
am //mm
To
T'm
(12)
ai-1/wet1
such that for all i = O..... m 1, ri and that the inner path weight of π is
r+t E 8. We say that π scans the string ...
m
WI(
def
Wi-
(13)
The path weight of π is
iT
def WI(T) & p(rm).
(14)
Lehmann's 's algorithm (Lehmann, 1977) computes the total inner weight of all paths between all pairs of states. When a WDFA A contains cycles, this set of paths can be infinite, so closed semiring with a defined operation is required. We give Lehmann's 's algorithm a table A indexed by Q x Q such that
Alg, r|
w
(g,r E Q).
(15)
a/
20

---

Published as a conference paper at ICLR 2025
Let [I, q r)) denote the (infinite) set of all paths starting at q and ending at in A. Lehmann's
algorithm computes a table A' indexed by Q x Q where
(T)
(g,r E Q).
(16)
TEl((A
This allows compute the backward weight of each state q, or the total weight of accepting if starting in 4- Definition 9. For a WDFA A, the backward weight [lg]] is the sum of the weights of all paths from to any other state.
Blq
w(T).
(17)
(ETT(A)))))
The quantity = B[qu] is the total weight assigned by A to strings in E" We call it the allsum.
We use the backward weights for weight pushing, Weight pushing redistributes the weights of Ap so that the weight of each transition in A', is the normalized (infinite) sum of the weights of all paths in Ap that start with that transition (Algorithm 2, line 7). Note that unlike the standard weight pushing algorithm (Mohri, 2009), we do not "normalize" the weights by left-multiplying them by (/q]-1, where, general, a=1 E K is the solution to the equation a- @ 1. The reason for this not because computing a= is hard; it is possible to do by solving system of linear equations. The issue is that this would result in weights that add up elementwise to I = (1, .,.0,...1 0), which would not be useful for purposes. Instead, normalize them by dividing them elementwise, which we do implicitly when we apply softmax (Algorithm 2, line 8).
In our implementation, precompute the elementwise cumulative sum of the transition weights. In our Python implementation of Algorithm 7, line 6, we pass the cumulative sum to the python. choices function the argument cun_weights in order to avoid recomputing it every time. Note that python. choices runs in logarithmic time in the length of cum_ sum_weightt weights due to its of binary search.
An important implementation detail that all of the operations in Def. 6 and weight pushing are amenable to vectorization, and we take advantage of this by accelerating it with PyTorch (Paszke et al., 2019). This significantly improves the runtime of the preprocessing step.
C DETAILS OF NEURAL NETWORK ARCHITECTURES
In this section, we describe each of the neural network architectures referenced in $3.2 in more detail. Our implementations for all three architectures are based on those provided by PyTorch (Paszke et al., 2019). Each architecture consists uses input embedding matrix E' to map each symbol wy of the input string 2e = E The size the embeddings is always d, the size the hidden vectors. In the following, DROPOUT(-) indicates the application of dropout.
configurable number of layers Each architecture embedding
C.1 SIMPLE RNN
Let h denote the hidden state of the 9th layer at timestep t. We apply dropout to the input embed- dings, the hidden states between layers, and the hidden states output from the last layer (Zaremba et al., 2015). Our simple RNN architecture is defined as follows.
h (0) Dt
E (6) def tanh(w (w (6))
(1stsn)
(18a)
h
(15
(18b)
( def
DROPOUT(H (5))
(18c)
((t-1) h h
(f) def (
(0))
h
(18d)
h (.)
(0stsm)
(18e)
21

---

Published as a conference paper at ICLR 2025
(8) IRd is learned parameter, making the initial hidden state hg of each layer learned. Here, wi Note that PyTorchh's RNN implementation includes redundant bias parameters byn and baa we have modified it single bias parameter b per layer instead.
C.2 LSTM
As with the simple RNN, we apply dropout following Zaremba et al. (2015). Our LSTM architecture defined as follows. Let @ denote elementwise multiplication.
h Dt a0
(0) def
(1$t5n)
(19a)
ho ( def l )
(1< L)
(19b)
del DROPOUT(H! (1)
(19c)
def (WW(
+ (
(19d)
h
5( det (W,( (8)
+ b (1)
(SISS11SISM)
(19e)
h
(-11
( tanh(W((1)
(
(1S141111SM)
(19f)
[--
of de (W(())
((())
(19g)
(8)
(S(544111S
(19h)
h
tanh(c)
(1564115SSM)
(19i)
def
(15$SL)
(19j)
def E
(0$t5m)
(19k)
Here, w E d is learned parameter, making the initial hidden state h of each layer learned. Note that PyTorch's LSTM implementation includes pairs of redundant bias parameters: by and bas b, and bas, big and bag. and bio and bho- We have modified it that each pair is replaced with single bias parameter per layer.
C.3 TRANSFORMER
We Torch'''s transformer implementation. Following Vaswani al. (2017), we map input symbols to vectors size d with a scaled embedding layer and add sinusoidal positional encodings. Note that Delétang et (2023) found that the type of positional encoding does not seem to have large impact on the transformer's performance, whereas Ruoss et al. (2023) found that transformers with randomized positional encodings perform better on the same set of tasks. We use attention heads in each layer, and we set the number of hidden units in each feedforward layer to 4d. We use pre-norm instead post-norm and apply layer norm to the output of the last layer. We use the same dropout rate throughout the transformer. We apply it in the same places Vaswani et al. (2017), and, as implemented by PyTorch, we also apply it to the hidden units of feedforward sublayers and to the attention probabilities of scaled dot-product attention operations. We always BOS the first input symbol to the transformer, which has been shown to improve performance on formal languages (Ebrahimi et al., 2020).
D DETAILS OF EXPERIMENTS
Here, provide additional details about the models and training procedures used in $4.
22

---

Published as a conference paper at ICLR 2025
Wherever dropout is applicable, use dropout rate of 0.1. For the transformer, when adjusting d to accommodate the parameter budget, we round it to the nearest multiple of 8, as Py PyTorhh requires it to be a multiple of the number of attention heads. We use Xavier uniform initialization (Glorot & Bengio, 2010) to initialize the fully-connected layers in the recognition and next-symbol prediction heads. For layer norm, we initialize weights to and biases to O. We initialize all other parameters by sampling uniformly from --0.1,011.
For each epoch, we randomly shufile the training set and group strings of similar lengths into the same minibatch, enforcing an upper limit of B symbols per batch, including padding, BOS, and EOS symbols. We train each model by minimizing the loss function defined in $3.3 using Adam (Kingma & Ba, 2015). We clip gradients with a threshold of 5 using L norm rescaling. We take a checkpoint every 10k examples (i.e., the end of each epoch), at which point we evaluate the model on the validation set and update the learning rate and early stopping schedules. We multiply the learning rate by 0.5 after checkpoints of no decrease in recognition cross-entropy on the validation set, and we stop early after 10 checkpoints of no decrease. We select the checkpoint with the lowest recognition cross-entropy on the validation set when reporting results. We train for a maximum of 1k epochs.
Every time we train a model, we randomly sample a number of hyperparameters. We randomly sample the batch size B from uniform distribution over [128, 4096]. We randomly sample the initial learning rate from a log-uniform distribution over [0.0001, 0.01]. We randomly sample the loss term coefficients ÄLM and ANS, when they are needed, from log-uniform distribution [0.01, 10].
Our experiments are small enough that we are able run them in CPU mode, without GPU accel- eration.
E DETAILS OF LANGUAGES
Here, we give more detailed descriptions of the languages listed Table 1, For each language, we indicate whether it is regular (R), deterministic context-free (DCF), context-free (CF), context- sensitive (CS); this also indicates that the language does not belong to previous classes.
Even Pairs (R). Binary strings where the total number of 01 and 10 substrings is even. Equiva- lently, this is the language of binary strings that have the same first and last symbol, or strings with fewer than two symbols. This is a low-sensitivity language, since only changing the first or last bit changes membership. This language corresponds to the Even Pairs task of Delétang et al. (2023). This language is given as an example in Sipser (2013, Chapter 1.4); see also Example 1.11.
Positive Examples
Negative Examples
01
10100
11
100110
010100
11101101
Repeat 01 (R). The string 01 repeated any number of times. As a star-free language, it is a low- sensitivity language under the uniform distribution over {0, 13" for a given string length n, since most strings are not in the language. However, under distribution in which exactly half of the strings are in the language, Repeat 01 can be considered a high-sensitivity language.
Positive Examples
Negative Examples
0
01
10101
0101
011001
Parity (R). Binary strings with an odd number of 1s. This is siggh-ensitivity language, since changing any bit changes membership. It appears commonly in the theoretical literature on the rep- resentational capacity of transformers, since its high sensitivity makes it difficult for transformers to represent the language (Hahn, 2020; Chiang & Cholak, 2022; Bhattamishra al., 2023; 2020a;
23

---

Published as a conference paper at ICLR 2025
Hahn & Rofin, 2024). However, it easily be learned by RNNs and scratchpad-augmennee trans- formers (Liu et al., 2023; Hahn Rofin, 2024). This language corresponds to the Parity Check task of Delétang al. (2023).
Positive Examples
Negative Examples
01011
181110
Cycle Navigation (R). Suppose an agent is on a 5-state cycle, numbered from 0 to 4, starting at state Strings in this language consist of a sequence of movess-mvv right (2), move left (<), or stay (=)-followed by the integer corresponding to the state reached after executing the sequence of moves. This language corresponds to the Cycle Navigation task of Delétang et al. (2023).
Positive Examples
Negative Examples
3
>=>><
>=>><<
<=O=<3
<=O>
>=>=><
4=31<
Modular Arithmetic (R). An expression involving the digits (0.....4) and the operators {t:-, then the result of evaluating that expression in modulo 5 arithmetic. All operators left-associative infix operators with equal precedence. Note that this is different from the Modular Arithmetic (Simple) task of Delétang et al. (2023), which gives higher precedence x, which would result in more complex DFA.
Positive Examples 3=3
Negative Examples
2+4+0-3=3
1=4
1-3x2=1
2+4+0-3=2
1-3x2=0
-1=4
=x3+-0+
Dyck-(2,3) (R). In general, the language Dyck-(k; m) contains strings of balanced brackets of A types with maximum nesting depth of m. We specifically test & 2 and m 3. Bounded Dyck languages have been studied for RNNs (Hewitt et al., 2020; Bhattamishra et al., 2020b) and transformers (Ebrahimi al., 2020; Bhattamishra et al., 2020a;b; Yao et al., 2021; Wen et al., 2023) both in terms of (empirical) representational capacity as well as interprerability. These languages star-free (Strobl et al., 2024b), and the language Dyck-(k, m) has a dot-depth of m. In this sense, bounded Dyck languages span the (infinite) hierarchy of star-free languages, which have been closely linked to transformers (Yang et al., 2024). Bhattamishra et al. (2020a) argue that transformers struggle to learn languages beyond dot-depth 1.
Positive Examples
Negative Examples ]())
(())
([]
[O]
[(])
([O]O)ΕO)
(I(O)]O)[O)
First (R). Binary strings that start with 1. This is a low-sensitivity language, since only changing the first bit changes membership. More concretely, it is special case of 1-Parity language, i.e., the Parity language restricted to a single position (Hahn & Rofin, 2024). Bhattamishra et al. (2023) refer to such functions as 1-Sparse functions. Transformers have been shown to learn such sparse functions well (Edelman et al., 2022; Bhattamishra et al., 2023; Hahn & Rofin, 2024).
Positive Examples
Negative Examples
E
101110
0
0111010
24

---

Published as a conference paper at ICLR 2025
Majority (DCF), Binary strings with more 1s than 0s. It is between low- and high-sensitivity, since string membership flips only when half of the bits in the string are 1. This language has been studied by Pérez et al. (2021); Merrill et al. (2022); Bhattamishra et al. (2023); Strobl (2023). Although it lies higher on the Chomsky hierarchy than the high-sensitivity languages Parity and Even Pairs, its lower sensitivity makes it easier for transformers to learn (Bhattamishra al., 2023; Hahn & Rofin, 2024).
Positive Examples
Negative Examples
E
110
001
011811010
1100
We generate a positive example by first sampling length n uniformly from [maxx(mmin: 1), mmmax) then number of 1s e uniformly from [[m/2] + +1,n] n... We compute the number of 0s as ca = n C1- We return a random permutation of the string 101
To test whether string is in the language, we simply return whether the number of 1s is greater than the number of Øs.
To compute (. we always include (0, 1), and we add EOS if wee E L.
Stack Manipulation (DCF). Each string starts with a binary string representing the contents of stack, written bottom to top. Then, there is a sequence of operations be performed on the stack, where popping is indicated with [POP, pushing 0 is indicated with the string 0, and pushing indicated with the string 1 Popping from an empty stack is not allowed. Finally, there is a =, and the contents of the resulting stack are written top to bottom (if the stack were not reversed, this language would not be context-free). This language corresponds to the Stack Manipulation task of Delétang et al. (2023); note that their version treats popping from an empty stack as a no-op.
Positive Examples
Negative Examples
01011 POP p PUSH| 1=101010
01011
|POP PUSH 0 |PUSS] 1001101
11 POP
PUSH 0=01
11= POP PUSH =01
01
POP
POP
PUSH
0 PUSH
1=10
01 POP
POP
POP
PUSH
PUSH
1=10
To generate positive example, we first sample the number of original stack symbols Nstack and then the number of push operations rpuuhh Let Πpop be the number of pop operations. Note that the length of the resulting stack Nstack + 7push - Npopp and the total length of the string is n = Nstaak + push + Mpop + -Push - -pppp
+-31 +. The minimum value of Mpush is O.
So, following simple algebra, we sample Nsstack uniformly from [max((, Rexin
1), Rmay -1] and
then we sample Npush uniformly from [max(0, [Rmmn -2n.ttcie- 1), Remay -Marack
We sample
3
an initial stack uniformly from {0, 1) J'Beraok, We then sample sequence of operations while counting the number of pushes generated so far and simulating the stack actions. At each step, we sample an action uniformly from ([PUSH], |POP]}. We disallow |POP] if the stack is empty. If we sample PUSH, we uniformly sample a pushed symbol from {0. 1}. We stop when we sample a [PUSH] and Ppush pushes have already been generated (this allows POP to occur after the last push). We then add and the resulting stack.
To test whether a string is in the language, we scan it from left to right while checking that it has the right format and simulating the stack actions. We push all 0s and 1s at the beginning scan PUSH and [POP commands and perform them on the stack, until we scan =. We reject if (PUSH] is not followed by 0 1, or if we attempt to pop from empty stack. We then check that the rest of the string is equal to the resulting stack.
stack. We
To compute NEXT (w we scan w in order of increasing t while simulating the stack actions, as above. If wes ends within the initial stack part, we set it to (0, 1, [PO]. |PUSH] =}. If wee ends with after PUSII we include =, and we include PUSII if fewer than pppuhh pushes have been seen, and we include [POP| if the stack is not empty. If wee ends with [PUSH] we set it to (0, 1 }. There is only one correct string for the final stack; if Wez ends within the final stack part, we set it to (0), (1), or (FOS) depending on what the correct string is.
POP,,
25

---

Published as a conference paper at ICLR 2025
Marked Reversal (DCF). Strings of the form utu where is binary string. This is classic example of a deterministic context-free language (Hopcroft et al., 2006). This corresponds to the Reverse String task of Delétang et al. (2023), which explicitly marks the point when model should stop reading w and start generating w. DuSell & Chiang (2020; 2022; 2023; 2024) showed that LSTTM and transformer language models struggle weighted version of this language compared to stack-augmented neural networks.
Positive Examples
Negative Examples
E
011#110
011#101101
0#0
011#11
01001#10010
0#11#110#
011110
generate a positive example, we first sample m uniformly from [], then we sample u uniformly from (0, 1)m". We then return the string w Notice that the string guaranteed to be in the desired length range.
Let m lu/. [[maxx(), 2min- [1. -
To test whether string is in the language, check whether there is single #, and whether the substring after the marker the reverse the substring before the marker.
To compute (w we scan w in order of increasing l. If wer ends within the first half (before the # symbol), then the set of next valid symbols set to {0, 1, #). The rest of the string is deterministic based on w, and we one of {0). {1}. {EOS} needed.
Unmarked Reversal (CF), Strings of the form wu R where u is a binary string. This a classic example of nondeterministic context-free language (Hoperoft et al., 2006, p. 254). DuSell & Chiang (2020; 2022; 2024) showed that LSTM and transformer language models struggle on this language compared tagk-augmented neural networks.
Positive Examples
Negative Examples
1
011110
01110
00
011100
0100110010
11110
Let m = lu]. To generate positive example, we first sample m uniformly from [[ [""mia 1, then we sample u uniformly from (0, 1 We then return the string uu?.
Ximax
2
To test whether string in the language, we check whether the length of the string even and whether the second half is the reverse of the first half.
To compute NEXT L (Wee), we always include (0, 1), and we include EOS wes L.
Marked Copy (CS). Strings of the form wHu, where is binary string. This is classic exam- ple of mildly context-sensitive language (Joshi, 1985). This language somewhat similar to the Duplicate String task of Delétang et al. (2023), which requires a model to read u and output wu, which is more like the language (u#uu u E {0, 1}* Jelassi et al. (2024) showed both theoret- ically and empirically that transformers are better copying than modern recurrent architectures, since the latter are constrained by their hidden state bottleneck. This language is also analogous to the String Equality task in Bhattamishra et al. (2024), who also found that transformers outperform both modern and classic recurrent architectures. DuSell & Chiang (2023) showed that LSTM lan- guage models struggle weighted version of this language compared to certain stack-augmented LSTMs.
Positive Examples
Negative Examples
011#011
011#91
040
011011
01001001001
0##1 1#11#1
We generate positive examples, test membership. and compute (WEz) similarly to Marked Reversal.
26

---

Published as a conference paper at ICLR 2025
Missing Duplicate (CS). This language contains strings of the form uu, where u is a binary string, but where one of the symbols in uu has been replaced with and where the replaced symbol was 1. This language corresponds to the Missing Duplicate task of Delétang al. (2023), which does not explicitly mark the boundary between the two us.
Positive Examples
Negative Examples
1
8 00100_10 10
001 _00_0 0 11_8100111011
11101001110100
_01_1_00
To generate a positive example, we sample = |u| uniformly from [max(11 Paaii 1), Amuax ]]. To 2 (0. 1) then we
ensure that contains least one 1, we first sample a string u' uniformly from
uniformly at random replace one of its symbols with to get u. We uniformly at random pick one of the 1 un and replace with to get the final string w.
To test whether string is in the language, we check if its length is even and if it contains exactly one We replace the with 1 and check if the first half the same as the second half.
To compute NEXT (wex:) if wer does not contain we set it to {0, 1, If wier does contain we include {0, 1}, and we add EOS wee L.
Odds First (CS). A binary string u, then #, then string the symbols in u at odd positions, and Ueeen is all the symbols in u at even positions. In other words, strings in this language are of the form u' eeenn where u' is the perfect shuffle of Wadd: Ueven E {0, 1)" and a E {0, 1, This corresponds to the Odds First task of Delétang et al. (2023).
Modd Mevens where Modd is all
Positive Examples
Negative Examples
E
1#1
010101#800110
010101 #000111
010101880111
010101 00000100000111
0#14#
16011011#10110100
To generate positive example, we first sample string in Marked Reversal. We then return Wof Meven-
To test whether a string is in the language, first check whether it contains exactly one #. We let the string to the left of # be u, and we check if the string to the right is equal to Uodd
To compute x if wee ends before #, we set it to {0, 1, #). The rest of the string is deterministic based on the value of u, and we use either {0), {1) or (FOS} to match Undd Meven-
Binary Addition (CS). Strings of the form U2 Uuy where Ugs My. u, are little-endian binary encodings (possibly with trailing 0s) of integers x, y, Zzo. and I + = z. The number 0 is encoded as 0, but not e. This language corresponds to the Binary Addition task of Delétang et al. (2023).
Positive Examples
Negative Examples
0+0=0
001+1=101
0111800100-0100000 101+01011:1111
001+1=011
100+1=101
1+11=001
0011101
=0+10=1+
We generate positive example follows. Note that, in general, binary encodings must have least one bit, and a binary string of length m can only encode integers in [0, 2m - 1]. Let nu = | We first sample ng, Ny. n2z, then we sample x. y, 2 that satisfy S 2n= 1,y52 - 1, = x + < 2n 1. We sample total string length n uniformly from [max(5, (5,xx(5,mmmi Rmin), Rmax]] Let nt = n2 + 1, nl nt, + 1, n', + 1. We sample n/ nl.. n'z using Dirichlet distribution with parameters (1, 1) that fl.,, ny: n2 equally distributed and always
|uz] my My n2 1,
27

---

Published as a conference paper at ICLR 2025
sum to n nt-2. 2. If ny > fz. we swap them, so that R2 ny this will make the distribution over x: less restrictive on y. because it reduces cases where x: is so large that few y can be chosen that satisfy the constraint
1)] and y uniformly from [0, min(2"y - 2 1 - =)}- We encode I, U, 2 x + y as Mar; My, M2, padding them with Os as needed to reach lengths of exactly Rzz; Ry, f2.- In order avoid bias in the distribution of vs. y, with probability 1.2 swap Uy and My. We return U2 =Ug
z. We sample r uniformly from [0, min(2" - 2,
To test whether a string is in the language, we simply check that it has the expected format, parse 3r, y, 2, and check that y =
To compute N (mre)) we scan we in order of increasing t. Before Ma. we set it to {0, 13. After any symbol in ug. we set it {e, 1, +). Similarly, before "y, we set it {0. 1), and after any symbol in Ny. we set it to {0, 1.= After =, we must deterministically generate (z), so we set it to {0) or {1} as needed. After (z), and after any trailing 0s, we set it to {0, EOS].
Binary Multiplication (CS). Strings of the form Up uzz where, like Binary Addition,
Ue By U2 are binary encodings of integers z, y, 2 E Z>o, and xy This language corresponds to the Binary Multiplication task of Delétang et al. (2023).
Positive Examples
Negative Examples
0x0=0
8 x= 001x11=1011
001x11=0011
001800x1000-001100
1001x0111=0111111
100x1010=010100
0011101
=0x10=1x
We generate a positive example similarly to Binary Addition. We first sample R2 Bly f22 then we sample x. y, z that satisfy x S 2n y S 2%v - 11, ay S 2n - 1. We sample n, Rly Rly 02 in the same way as Binary Addition, except the Dirichlet distribution has parameters 1,2, This means ng tends to be twice as big as n2 or ny; we do this because the number of bits required for ry is approximately the sum of the bits required for x and y. Note that guaranteeing n2 S ny is particularly important here for a good distribution of y. We sample x uniformly from [0, 2 - ..
& > O, we sample y uniformly from [0, min((" - 1, 1 11
- D]. Otherwise, we sample y uniformly
from [0, 2d 1]. The rest is like Binary Addition, except we return UyZ
We test whether a string is in the language and compute N like Binary Addition, except use zy instead of y 2, and x instead of +.
Compute Sqrt (CS). Strings of the form u,=u,, where, similarly to Binary Addition and Binary Multiplication, uay M2 are binary encodings of integers x, E Z20, and [vz]= = z. This language corresponds to the Compute Sqrt task of Delétang et al. (2023).
Positive Examples
Negative Examples
0=0
8
011=11
00181=001
011=01
00101000=00100
0=11=1
We generate a positive example similarly to Binary Addition and Binary Multiplication. Let ng |unl 11 |uz]. We first sample nz,, R2,, then we sample that satisfy x < 2 1, = [V S 2 -1 We sample a total string length n uniformly from [max(3, 7min)) Rmma Let The n/, + 1, n', + 1. We sample nig, n'g using Dirichlet distribution with parameters (2, 1), so that n, and n, sum to n 2, and ng tends to be twice as big as ng. We do this because the number of bits required for |T is about half of that required for z. We sample uniformly from [0. min - 1, 2 1)]. We encode x, 2 = |V as Ug Uz padding them with Os as needed to reach lengths of exactly ng, n2.. We return u. =ug.
To test whether a string is in the language, we simply check that it has the expected format, parse Jr 2, and check that [vr]
28

---

Published as a conference paper at ICLR 2025
To compute N (w<e), we in order of increasing t. Before Ugg set it to {0, 1}. After any symbol in ugs we set it to {0, 1,=). After =, we must deterministically generate (2). so we set to {0) or {1} as needed. After (2), and after any trailing 0s, we set it to BOS).
Bucket Sort (CS), A string u E (1,...,55) 53", then #, then the digits of in sorted order. Note that it is only necessary to keep track of the counts of each type of digit recognize this language. This language corresponds to the Bucket Sort task of Delétang et al. (2023).
Positive Examples
Negative Examples
E
451234541234455 51284124#0112233
4512345#1434255
31204124H0112
41#14
1#2##12
Let m -u]. To generate positive example, we first sample as in Marked Reversal, then we sample uniformly from (1....,5)mm We then compute the sorted string u' and return the string wthl..
To test whether string is in the language, we check whether there is single #, and whether the substring after the marker the bucket sort the substring before the marker.
To compute (w we scan w in order of increasing l.. If weer ends within the first half (before the # symbol), then the set of next valid symbols is set (1,.... ... 5, #). The rest of the string is deterministic based on the value of and we use one of [1),... {5), (FOS) needed.
F LENGTH-CONSTRAINED SAMPLING FOR REGULAR LANGUAGES IN MLREGTEST
MLRegTest (van der Poel al., 2024) assumes the availability of complete DFA A (Q, 8, F)) F) that recogmizes L. In order to sample strings within a given length range [miin mmma)) performs the following steps for each length n in [Amin mmax].
1. Construct a DFA that recognizes nn and intersect it with A in O([2][Q)m) time, resulting in an acyclic DFA with O(QQmn) states.
2. Minimize the DFA in Q( log(IQ)n) time, resulting in O([Q)n) m) states.
3. Topologically sort the states, then run dynamic programming algorithm that counts the number of accepting paths leading out of each state, all in 0 [Q[n) time. This is equiv-
alent to running the backward algorithm in the counting semiring (Zzo, +, 0,
4. Use the path counts make the DFA PDFA encoding the uniform distribution LN
The total runtime of this approach is ([ max Aminn) (( being dominated by the minimization step. If minimization is removed, it is only O(EE Mmax (Amax 7 )-
G FULL RESULTS
We show the best loss functions for each architecture, language, and validation set in Table 3.
We show unabridged versions of the results from $5 for all languages in Tables 4 to 21. Every row is aggregated across 10 runs. The scores shown in each row are of the model with the lowest recognition cross-entropy on the validation set (this value shown under "Val. CE"; lower better). All columns accuracy scores except for "Val. CE." We show the best score in each column in bold.
Here, we refer to the test set used in $5, which has lengths in [0, 500], as the long test set. We also report accuracy on a short test set of 1k held-out examples with lengths in 40). The short test set only includes examples that do not occur in the training set, short validation set, long validation set; it tests how well model generalizes to unseen strings within the same length distribution. For languages where the training and validation data already includes all possible strings, leave this
29

---

Published as a conference paper at ICLR 2025
Table 3: The best loss functions, corresponding to the accuracy scores reported in Table 2. "R"= recognition; "LM" = language modeling; "NS" = next-symbol prediction. No single loss function consistently results in the best performance; the most frequent winner is just R.
Inductive Bias
Expressivity
Language
Tf RNN
LSTM
Tf
RNN
LSTM
Even Pairs
R+LM+NS
R+NS
R
Repeat 01
R
R+NS
R
R
R
Parity
R+NS
R+NS
R+NS
R+NS
R+LM
R
Cyclc Navigation
R+LM+NS
R
R
R
R
R
Modular Arithmetic
R
R
R+NS
R
R
Dyck-(2,3)
R+LM
R+LM4NS
R+NS
R+NS
R+NS
First
R+NS
R+LM
R+LM
R
R
R
Majority
R+LM
R+NS
R+NS
R+LM
R+LM+NS
R+LM+NS
Stack Manipulation
R
R+NS
R+LM+NS
R R+LM
R+LM
Marked Reversal
R+NS
R+NS
R+LM
R+LM
Unmarked Reversal
R+NS
R+NS
R+NS
R+NS
Marked Copy
R+NS
R+LM
R+NS
R
R
Missing Duplicate
R+LM+NS
R
R
R+LM+NS
R+LM+NS
R+LM
Odds First
R
R
R
R+LM+NS
R
R+LM+NS
Binary Addition
R+NS
R+LM
R+NS
R+NS
Binary Multiplication
R+NS
R
R+NS
R+NS
R+LM
R+NS
Compute Sqrt
R
R
R
R R+NS
R
R R+LM+NS
Bucket Sort
R
R+LM+NS
R+NS
column blank. We also report accuracy the training and validation sets to show how well the model fits the training data.
In order to the effects of model selection, also report the mean and maximum accuracy scores on the long test set across all runs, as it is often the case that the model that generalizes best longer strings is not the one with the lowest recognition cross-entropy. Although this kind of test-set-based model selection impossible in the wild, for our purposes it is useful for revealing when architecture is capable of chancing upon solution that generalizes, even if it cannot be reliably found with model selection.
In all rows, "+LM" means a language modeling loss term is added, "+NS" means next-symbol prediction loss term is added, "S" means short validation set is used, and "L" means a long val- idation set is used. "Train" is accuracy on the training set, "Val. CE" is recognition cross-entropy on the validation set (which is used as the model selection criterion), "Val." is accuracy on the val- idation set, Test" is accuracy on the short test set, "I.. Test" is accuracy on the long test set, "L. Test (Mean)" is "L. Test" averaged across runs with standard deviations, and "I.. Test (Max)" is the maximum.
30

---

Published as a conference paper at ICLR 2025
Table 4: Full results on the Even Pairs language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
1.000
0.000
1.000
1.000
1.000
0.994 0.01
1.000
TY (L)
1.000
0.000
1.000
1.000
1.000
0,999 1 0.00
1,000
TT (+LM, S)
1.000
0.000
1.000
1.000
0,997
0.978 1: 0.04
1.000
TT (+LM,, L)
1.000
0.000
1.000
1.000
0.923
0.956 +: 0.06
1.000
Tf (+NS,
1.000
0.000
1.000
1.000
0.998
0.994 0.01
1.000
Tf (+NS, L)
1.000
0.000
1.000
1.000
1,000
0.996 + 0.01
1.000
TI (+LM+NS, S)
1.000
0.000
1.000
1.000
0.992
0,959 = 0.06
1.000
Tf (4LM+NS,
1.000
0.000
1.000
1.000
1,000
0.992 + 0.01
1,000
RNN (S)
0.549
0.673
0.565
0.513
0.512
0.504 0.01
0.517
RNN (L)
0.542
0.680
0.527
0.480
0.509
0.508 + 0.01
0.518
RNN (+LM. S)
0.541
0.674
0.559
0,520
0.505
0.506
0.517
RNN (+LM. L)
0,576
0.658
0.607
0.575
0,640
0,640
RNN (+NS,
1.000
0.000
1.000
1.000
1.000
0.556 0.15
1.000
RNN (+NS, L)
1.000
0.000
1.000
1.000
1.000
0.621 0.19
1.000
RNN (+LM+NS, S)
1.000
0.000
1.000
1.000
1.000
0.601 0.20
1.000
RNN (+LM+NS, L)
1.000
0.000
1.000
1.000
1.000
0.614 0.20
1.000
LSTM (S)
1.000
0.000
1.000
1.000
1.000
1.000
LSTM (L)
1.000
0.000
1.000
1.000
0.761
0.900 0.15
1.000
LSTM (4LM, S)
1.000
0.000
1.000
1.000
1.000
0.554
1.000
LSTM (+LM,
0.538
0.680
0.520
0.518
0.509
0.503 1003:000 0.01
0.515
LSTM (+NS, S)
1.000
0.000
1.000
1.000
1.000
0.611 0.20
1.000
LSTM (+NS, L)
1,000
0.000
1.000
L.000
1.000
0.697
1.000
LSTM (+LM+NS, S)
0.539
0.671
0.551
0,508
0,511
0.504 0.01
0,516
LSTM (+LM+NS, L.)
0.537
0.681
0.513
0.518
0.497
0.503
0.517
Table 5: Full results on the Repeat 01 language.
Model
Train
Val. CE
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0.999
0.000
1.000
0,707
0.717 + 0.09
0.844
Tf (L)
0.994
0.134
0.969
0.593
0,693 + 0.10
0.857
Tf (+LM, S)
0.998
0.001
1.000
0.833
0.675 0.12
0.847
(+LM, L.
0.997
0.087
0.979
0.617
0.687
0.838
Tf (+NS. S)
1.000
0.000
1,000
0,546
0.710 + 0.10
0,842
(+NS. L)
0.971
0.126
0.962
0.845
0.734 #.10
0.845
TF (+LM+NS.
0.999
0.003
L.000
0.681
0.659 0.09
0.842
(+LM-NS.. L)
0.997
0.105
0,970
0,592
0.706
0.850
RNN (S)
1.000
0.000
1.000
1.000
0.935
1.000
RNN (L)
1.000
0.000
1.000
1.000
0.880 + 0.10
1,000
RNN (+LM, S)
1.000
0.000
1.000
1.000
0.956 0.09
1,000
RNN (+LM, L)
1.000
0.000
1.000
1.000
0.948 + 0.08
1.000
RNN (+NS, S)
1.000
0.000
1.000
1.000
0.969
1.000
RNN (+NS, L)
1.000
0.000
1.000
1.000
0.978 1 0.07
1.000
RNN (+LM+NS, S)
1.000
0.000
1.000
1.000
0.911 191110.1 0.11
1.000
RNN (+LM+NS, L)
1.000
0.000
1.000
1.000
0.914
1.000
LSTM (S)
1.000
0.000
1,000
1.000
0.972 + 0.07
1.000
LSTM (L)
1.000
0.000
1.000
L.000
0.905 2 0.13
1.000
LSTM (+LM,
1.000
0.000
1.000
0.864
0.928 + 0.14
1,000
LSTM L.)
1.000
0.000
1.000
0.939
0.975000
1.000
LSTM (+NS, S)
1.000
0.000
1.000
1.000
0.921 +
1.000
LSTM (+NS. L)
1.000
0.000
1.000
1.000
0,982 0.05
1.000
LSTM (+LM+NS, S)
L.000
0.000
1.000
1.000
0.953 1 0.13
1.000
LSTM (+LM+NS, L)
1.000
0.000
1.000
0.964
0.881 + 0.20
1.000
31

---

Published as a conference paper at ICLR 2025
Table 6: Full results on the Parity language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
0.713
0.503
0.688
0.601
0.538
0.528 0.01
0.544
TY (L)
0.664
0.620
0.595
0.569
0.521
0.529 1 0.01
0.543
TT (+LM, S)
0.764
0,452
0.722
0.680
0.558
0.530 1 0.01
0.558
TT (+LM, L)
0.756
0.552
0.658
0.686
0.561
0.532 1 0.01
0.561
Tf (+NS,
0,969
0.060
0.973
0.953
0.559
0.557 0.03
0.630
Tf (+NS, L)
0,903
0.424
0.766
0.882
0,550
0.599
TI (+LM+NS, S)
0,909
0.198
0.895
0.874
0.579
0.552 0.03
0,604
Tf (4LM+NS, I))
0.865
0.444
0.751
0.820
0.587
0.553
0.591
RNN (S)
0.546
0.677
0.531
0.534
0.521
0.507 + 0.01
0.525
RNN (L)
0.554
0.687
0.540
0.540
0.522
0.512
0.541
RNN (+LM. S)
1.000
0.000
1.000
1.000
1.000
0.605 0.20
1.000
RNN (+LM. L)
1.000
0.000
1.000
1.000
1.000
0.572
1,000
RNN (+NS,
1.000
0.000
1.000
1.000
1.000
0.712 0.24
1.000
RNN (+NS, L)
1.000
0.000
1.000
1.000
1.000
0.671 0.19
1.000
RNN (+LM+NS, S)
1.000
0.000
1.000
1.000
1.000
0.706 - 0.24
1.000
RNN (+LM+NS, L)
1.000
0.000
1.000
1.000
1.000
0.682 + 0.21
1.000
LSTM (S)
1.000
0.000
1.000
1.000
1.000
0.664
1.000
LSTM (L)
1.000
0.000
1.000
1.000
1.000
0.705 0.24
1.000
LSTM (4LM, S)
1.000
0.000
1.000
1.000
1.000
0.599
1.000
LSTM (+LM,
0.544
0.686
0.542
0.542
0.497
0.494 0.00
0,497
LSTM (+NS, S)
1.000
0.000
1.000
1.000
1.000
0.902 0.20
1.000
LSTM (+NS, L)
1.000
0,000
1.000
1.000
1.000
0.752 0.25
1.000
LSTM (+LM+NS, S)
1.000
0.000
1.000
1.000
1.000
0.613 0.20
1.000
LSTM (+LM+NS, L.
1.000
0.000
1.000
1.000
1.000
0.547 + 0.15
1,000
Table Full results on the Cycle Navigation language.
Model
Train
Val. CE
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0.931
0.250
0.911
0.946
0.811
0,836 + 0.05
0.934
Tf (L)
0.923
0.192
0.938
0.946
0.901
0.844 = 0.05
0.934
Tf (+LM, S)
0.931
0.249
0.911
0.946
0.805
0.804 0.10
0,933
(+LM, L.
0,926
0.191
0.938
0.946
0.923
0.866 0.05
0.933
Tf (+NS. S)
0.984
0.074
0.973
0.987
0.767
0,812 + 0.04
0,884
(+NS. L)
0.950
0.169
0.943
0.957
0.776
+ 0.04
0.927
TF (+LM+NS.5
0.931
0,251
0.911
0.946
0.810
0.838 - 0.05
0,932
(+LM-NS.. L)
0.924
0.192
0.938
0.946
0.932
0.838
0,932
RNN (S)
0.930
0,255
0.910
0.946
0,934
0.930 - 0.01
0.934
RNN (L)
0,928
0.192
0.939
0.946
0.934
0.917 + 0.05
0.934
RNN (+LM, S)
0.929
0.254
0.910
0.946
0.934
0.915 0.05
0.934
RNN (+LM, L)
0.931
0.189
0.941
0.946
0.934
0.904 + 0.09
0.934
RNN (+NS, S)
0,930
0.256
0.910
0.946
0.934
0.900
0.934
RNN (+NS, L)
0,929
0.190
0.940
0.946
0.934
0.877 1 0.13
0.934
RNN (+LM+NS, S)
0,928
0.264
0.907
0.946
0.934
0,888 1: 0.11
0.934
RNN (+LM+NS, L)
0.929
0.192
0.940
0.946
0.934
0.839 + 0.17
0.934
LSTM (S)
0.929
0.257
0.910
0.946
0,934
0.900 0.04
0.934
LSTM (L)
0,929
0.190
0.940
0.946
0.927
0.914
0.934
LSTM (+LM,
0.930
0.252
0.910
0.946
0.934
0.878 0.13
0.934
LSTM L.)
0,929
0.191
0.940
0.946
0.934
0.828 0.17
0.934
LSTM (+NS, S)
0.931
0.255
0.911
0.946
0.934
0.822 0.16
0.934
LSTM (+NS. L)
0,929
0.193
0,940
0.946
0,923
0.880
0,933
LSTM (+LM+NS, S)
0.935
0.237
0.912
0.947
0.884
0.17
0.934
LSTM (+LM+NS, L)
0.929
0.189
0.940
0.946
0.933
0.798 + 0.20
0.934
32

---

Published as a conference paper at ICLR 2025
Table 8: Full results on the Modular Arithmetic language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
0.977
0.093
0.976
0.979
0.643
0.686 0.11
0.812
TY (L)
0,978
0.117
0.963
0.981
0.829
0.698 1 0.09
0,830
TT (+LM, S)
0,983
0.085
0.980
0.980
0.531
0.659 1 0.11
0.796
TT (+LM,, L)
0.929
0.270
0.889
0.919
0.559
0.676 +: 0.08
0.790
Tf (+NS,
0,984
0.085
0.981
0.981
0.740
0.654 0.12
0.869
Tf (+NS, L)
0,975
0.100
0.969
0.976
0.884
0.706 0.09
0,884
TI (+LM+NS, S)
0,979
0.089
0.976
0.981
0,826
0,671 = 0.12
0.852
Tf (4LM+NS, L.)
0,972
0.122
0.965
0.973
0.582
0.612 + 0.08
0.793
RNN (S)
0.986
0.080
0.982
0.978
0.997
0.996 + 0.00
0.997
RNN (L)
0.988
0.062
0.987
0.984
0.997
0.989 0.02
0.997
RNN (+LM. S)
0.987
0.081
0.982
0.980
0.997
0.882 + 0.10
0.997
RNN (+LM. L)
0.988
0.062
0.987
0.984
0.997
0.964 + 0.07
0.997
RNN (+NS,
0.987
0.079
0.982
0.980
0.997
0,950 + 0.08
0.997
RNN (+NS, L)
0.988
0.062
0.987
0.984
0.996
0.965
0.997
RNN (+LM+NS, S)
0,986
0.079
0,982
0.978
0.997
0.966 - 0.07
0.997
RNN (+LM+NS,) L)
0.988
0.062
0.987
0.984
0.997
0.955 + 0.07
0,997
LSTM (S)
0,986
0.078
0.982
0.978
0.997
0.982 =
0.997
LSTM (L)
0.985
0.063
0.987
0.978
0.997
0.955 + 0.08
0.997
LSTM (4LM, S)
0.986
0.081
0,982
0,978
0.997
0.981 +
0.997
LSTM (+LM,
0.988
0.061
0.987
0.984
0.997
0.995 + 0.00
0.997
LSTM (+NS, S)
0,986
0.078
0.982
0.978
0.997
0.952 + 0.09
0.997
LSTM (+NS, L)
0.988
0.061
0.987
0.984
0.997
0.957 0.07
0.997
LSTM (+LM+NS, S)
0.986
0.081
0.982
0.978
0.964
0.918 1 0.14
0.997
LSTM (+LM+NS, L.
0.988
0.062
0.987
0.984
0.996
0.950 + 0.08
0.997
Table Full results on the Dyck-(2,3) 3) language.
Model
Train
Val. CE
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0.968
0.119
0.969
0.968
0.585
0.630 + 0.05
0.711
Tf (L)
0.965
0.146
0.953
0.967
0.804
0.690 + 0.08
0.804
Tf (+LM, S)
0.998
0.010
0.998
0.994
0.604
0.702 0.09
0.811
(+LM, L.
0,979
0.157
0.950
0.975
0.599
0.652 0.06
0.778
Tf (+NS. S)
0,998
0.002
1.000
0.995
0.596
0.622 + 0.07
0.765
Tf (+NS. L)
0.964
0.163
0.941
0.969
0.756
0.687 + 0.09
0.819
TF (+LM+NS.5
0.996
0,008
0.996
0.991
0.693
0.627 = 0.05
0.734
(+LM+NS.. L)
0,994
0.123
0.959
0.989
0.788
0.693
0.791
RNN (S)
0.972
0.093
0.976
0.977
0,980
0.907 + 0.08
0,982
RNN (L)
0,972
0.092
0.979
0.976
0.972
0.929 + 0.10
0,982
RNN (+LM, S)
0.999
0.005
1.000
0.998
0.991
0.941 + 0.07
0.991
RNN (+LM, L)
0.999
0.014
0.998
0.998
0.826
0.945 0.05
0.982
RNN (+NS, S)
0,999
0.005
0.999
0.999
0.957
0.952 0.07
0.998
RNN (+NS, L)
0.998
0.014
0.998
0.997
0.988
0.923 1 0.07
0,996
RNN (+LM+NS, S)
1.000
0.000
1.000
1.000
0.999
0.953 1133-0000 0.05
0,999
RNN (+LM+NS, L)
1.000
0.001
1.000
1.000
0.991
0.922 0.09
0,996
LSTM (S)
0.971
0.097
0.975
0.978
0,982
0.907 0.10
0,982
LSTM (L)
0,971
0.094
0,979
0,978
0.977
0.883 + 0,10
0,977
LSTM (+LM,
0.971
0.100
0.975
0.978
0.982
0.835 + 0.14
0,982
LSTM (+LM,
0,972
0.089
0.979
0.976
0.701
0.868 + 0.10
0,980
LSTM (+NS, S)
0.972
0.097
0.975
0.977
0.982
0.16
0.982
LSTM (+NS. L)
0.972
0.091
0.979
0.975
0,976
0.942 4
0,983
LSTM (+LM+NS, S)
0.971
0.098
0.974
0.977
0.962
0.838 0.19
0,983
LSTM (+LM+NS, L)
0.972
0.089
0.979
0.977
0.975
0.922 + 0.10
0,982
33

---

Published as a conference paper at ICLR 2025
Table 10: Full results on the First language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
1.000
0.000
1.000
1.000
1.000
0.926 0.12
1.000
TY (L)
1.000
0.000
1.000
1.000
0,987
0.936 1 0.10
1,000
TT (+LM, S)
1.000
0.000
1.000
1.000
1.000
0.934 1 0.08
1.000
TT (+LM,, L)
1.000
0.000
1.000
1.000
1.000
0.974 1: 0.04
1.000
Tf (+NS,
1.000
0.000
1.000
1.000
0.952
0.982 0.04
1.000
Tf (+NS, L)
1.000
0.000
1.000
1.000
1.000
0,969 + 0.08
1.000
TI (+LM+NS, S)
1.000
0.000
1.000
1.000
0.999
0,935 = 0.14
1.000
Tf (4LM+NS,
1.000
0.000
1.000
1.000
1,000
0.928 + 0.12
1.000
RNN (S)
1.000
0.000
1.000
1.000
1.000
0.629 0.20
1.000
RNN (L)
1.000
0.000
1.000
1.000
1.000
0.701 0.24
1.000
RNN (+LM. S)
1.000
0.000
1.000
1.000
1.000
0.800 + 0.24
1.000
RNN (+LM. L)
1.000
0.000
1.000
1.000
1.000
0,800 +: 0.24
1.000
RNN (+NS,
1.000
0.000
1.000
1.000
1.000
0.703 1: 0.24
1.000
RNN (+NS, L)
1.000
0.000
1.000
1.000
1.000
0.799
1.000
RNN (+LM+NS, S)
1.000
0.000
1.000
1.000
1.000
0.750 - 0.25
1.000
RNN (+LM+NS, L)
1.000
0.000
1.000
1.000
1.000
0,704 + 0.24
1.000
LSTM (S)
1.000
0.000
1.000
1.000
1,000
0,932 - 0.15
1.000
LSTM (L)
1.000
0.000
1.000
1.000
1.000
1.000 + 0.00
1.000
LSTM (4LM, S)
1.000
0.000
1.000
1.000
1.000
0.938 0.14
1.000
LSTM (+LM,
1.000
0.000
1.000
1.000
1.000
0.896 + 0.15
1.000
LSTM (+NS, S)
1.000
0.000
1.000
1.000
1.000
0,850 =
1.000
LSTM (+NS, L)
1.000
0.000
1.000
1.000
1.000
0.944
1.000
LSTM (+LM+NS, S)
1.000
0.000
1.000
1.000
1.000
0.850
1.000
LSTM (+LM+NS, L.
1.000
0.000
1.000
1.000
0.779
0.912 0.15
1.000
Table 11: Full results on the Majority language.
Model
Train
Val. CE +
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
1.000
0.001
1.000
1.000
0.970
0.946 + 0.07
0.990
Tf (L)
1.000
0.004
1.000
1.000
0.985
0,943 = 0.07
0.995
Tf (+LM, S)
1.000
0.001
1.000
1.000
0.992
0.969 0.04
0.992
(+LM, L.
1.000
0.005
1.000
1.000
0.991
0.959 0.05
0.996
Tf (+NS. S)
1.000
0.000
1.000
1.000
0,992
0.961 + 0.05
0,992
Tf (+NS. L)
1.000
0.005
0.998
1.000
0.985
0.966 + 0.04
0.993
TF (+LM+NS.
1.000
0.001
1.000
1.000
0.989
0.969 0.02
0,989
(+LM+NS..
1.000
0.007
0.998
1.000
0.991
0.975 0.04
0,993
RNN (S)
L.000
0.003
1.000
L.000
0.913
0.868 = 0.12
0,928
RNN (L)
1.000
0.025
0.997
1.000
0.926
0.834 + 0.14
0,931
RNN (+LM, S)
1.000
0.000
1.000
1.000
0.918
0.875 0.12
0.924
RNN (+LM, L)
1.000
0.021
0.996
1,000
0.916
0.880 + 0.13
0.945
RNN (+NS, S)
0,999
0.005
0.999
0.998
0.899
0.896
0,927
RNN (+NS, L)
0.999
0.030
0.994
0.998
0.934
0.916 0.01
0,934
RNN (+LM+NS, S)
1.000
0.006
0.999
1.000
0.919
0.887 1 0.07
0,927
RNN (+LM+NS, L)
1.000
0.021
0.997
1.000
0.927
0,949
LSTM (S)
1.000
0.000
1.000
1.000
0.979
0.939 0.04
0,997
LSTM (L)
1.000
0.000
1.000
L.000
0.973
0.943
0,989
LSTM (+LM,
1.000
0.000
1.000
1.000
0.980
0.942 0.04
0,998
LSTM L.)
1.000
0.000
1.000
1.000
0.990
0.946 0.04
0.995
LSTM (+NS, S)
1.000
0.000
1.000
1.000
0.999
0.952 0.04
0.999
LSTM (+NS. L)
1.000
0.000
1.000
1.000
0,989
0.862 - 0.18
0,997
LSTM (+LM+NS, S)
L.000
0.000
1.000
L.000
1.000
0.91
1.000
LSTM (+LM+NS, L)
1.000
0.000
1.000
1.000
0.991
0.963 1 0.04
1.000
34

---

Published as a conference paper at ICLR 2025
Table 12: Full results the Stack Manipulation language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
0.929
0.190
0.917
0.912
0.610
0.664
0.14
0.869
TY (L)
0,920
0.294
0.885
0.897
0.573
0.640 1 0.13
0,868
TT (+LM, S)
0,981
0.072
0.983
0.980
0.515
0.595 1 0.13
0.854
TT (+LM, L)
0.935
0.238
0.909
0.922
0.869
0.701 + 0.14
0.869
Tf (+NS,
0,976
0.101
0.973
0.976
0.857
0.591 0.14
0.868
Tf (+NS, L)
0,928
0.255
0,906
0.914
0,545
0.684 0.14
0,869
TI (+LM+NS, S)
0,981
0,059
0.985
0.979
0.515
0.571
0,868
Tf (4LM+NS, L.
0,950
0.246
0.914
0.939
0.870
0.608 + 0.13
0,870
RNN (S)
0.926
0.229
0.923
0.919
0.928
4834+00.11
0.929
RNN (L)
0.943
0.187
0.940
0.944
0.933
0.783 0.17
0.933
RNN (+LM. S)
0.985
0.070
0.986
0.983
0.520
0.691 =
0,930
RNN (+LM. L)
0,925
0.211
0.927
0.919
0.930
0.817 0.12
0,930
RNN (+NS,
0.986
0.073
0.986
0.989
0.520
0.838 +: 0.16
0.930
RNN (+NS, L)
0.930
0.208
0.931
0.919
0.927
0.854
0,930
RNN (+LM+NS, S)
0,988
0.050
0.991
0.990
0.523
0.762 0.20
0,930
RNN (+LM+NS, L)
0,935
0.206
0.934
0.937
0.932
0.852 + 0.11
0,932
LSTM (S)
0,989
0.047
0.991
0.993
0.987
0.746
0.987
LSTM (L)
0.956
0.189
0.936
0.951
0.876
0.784 0.07
0.885
LSTM (4LM, S)
0.987
0.045
0.991
0.992
0.551
0.568 0.09
0.818
LSTM (+LM,
0.989
0.069
0.986
0.990
0.540
0.674 0.14
0,906
LSTM (+NS, S)
0.987
0.051
0.988
0.992
0.664
0.669 : 0.14
0.922
LSTM (+NS, L)
0.989
0.063
0.986
0.993
0.750
0.67
0.799
LSTM (+LM+NS, S)
0.989
0.043
0.991
0.993
0.602
0.528
0,602
LSTM (+LM+NS, L.
0.988
0.066
0.985
0.993
0.541
0.620 + 0.13
0.896
Table 13: Full results on the Marked Reversal language.
Model
Train
Val. CE
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0.969
0.116
0.969
0.967
0.552
0.604 + 0.11
0.847
Tf (L)
0.876
0.316
0.879
0.877
0.616
0.693 + 0.08
0.758
Tf (+LM, S)
0.969
0.117
0.969
0.967
0.534
0.577 0.08
0.740
(+LM, L.
0,960
0.197
0.943
0.953
0.870
0.689 0.13
0.870
Tf (+NS. S)
0.995
0.032
0.992
0.991
0,541
0.641 + 0.12
0,827
(+NS. L)
0.969
0.176
0.944
0.967
0.868
0.647 0.12
0.868
TF (+LM+NS.
0.993
0.027
0.995
0.994
0.539
0.580
0.859
(+LMMNS.. L)
0,966
0.170
0.941
0.962
0.853
0.665 0.09
0.853
RNN (S)
0,968
0.119
0.969
0.965
0.603
0.17
0,947
RNN (L)
0,960
0.131
0.965
0.961
0.594
0.761 + 0.15
0,947
RNN (+LM, S)
0.969
0.119
0.969
0.967
0.535
0.662
0.911
RNN (+LM, L)
0.959
0.130
0.965
0.960
0.948
0.793
0.948
RNN (+NS, S)
0,967
0.124
0.969
0.965
0.544
0.699 0.18
0.948
RNN (+NS, L)
0,968
0.102
0.975
0.966
0.643
0.612 661210.11 0.12
0,947
RNN (+LM+NS, S)
0,968
0.119
0.969
0.967
0.538
0.651 + 0.17
0,947
RNN (+LM+NS, L)
0.955
0.136
0.963
0.958
0.947
0.660
0,947
LSTM (S)
0.969
0.116
0.969
0.967
0.954
0.744
0.963
LSTM (L)
0.952
0.163
0.950
0,946
0.574
4.755
0.859
LSTM (+LM,
0.999
0.001
1,000
0.992
0,584
0.552 0.05
0.679
LSTM (+LM,
0.969
0.103
0.975
0.967
0.596
0.681 + 0.16
0,947
LSTM (+NS, S)
0.969
0.117
0.969
0.967
0.561
0.653
0.845
LSTM (+NS. L)
0.969
0.107
0.975
0.967
0,578
0.623
0,852
LSTM (+LM+NS, S)
0,969
0.116
0.969
0.967
0.617
0.624
0,946
LSTM (+LM+NS, L)
0.981
0.073
0.981
0.980
0.593
0.674
35

---

Published as a conference paper at ICLR 2025
Table 14: Full results on the Unmarked Reversal language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
0,970
0.099
0.971
0.969
0.552
0.584 0.03
0.632
TY (L)
0.818
0.454
0.774
0.839
0,583
0.600 1 0.04
0,631
TT (+LM, S)
0,955
0.147
0.952
0.958
0.563
0.552 1 0.04
0.617
TT (+LM,, L)
0.695
0.558
0.674
0.677
0.559
0.544 1: 0.04
0.623
Tf (+NS,
0.963
0.112
0.965
0.949
0.541
0.557 0.02
0.612
Tf (+NS, L)
0.868
0.456
0.779
0.846
0.547
0.578 1 0.04
0.630
TI (+LM+NS, S)
0.959
0.127
0.957
0.940
0.540
0.539 0.03
0.578
Tf (4LM+NS, L.
0.752
0.529
0.726
0.748
0.607
0.589 + 0.04
0,630
RNN (S)
0.975
0.094
0.974
0.977
0.670
0.708 + 0.09
0.763
RNN (L)
0.970
0.139
0.965
0.962
0.726
0.736
0.763
RNN (+LM. S)
0.973
0.020
0.982
0.998
0.622
0.715 0.05
0.763
RNN (+LM. L)
0,981
0.097
0.982
0.984
0.748
0.721 + 0.05
0.763
RNN (+NS,
0.976
0.097
0.971
0.968
0.682
0.716 1: 0.08
0.766
RNN (+NS, L)
0.974
0.158
0.957
0.963
0.665
0.744 0.05
0.813
RNN (+LM+NS, S)
0,961
0.061
0.973
0.984
0.636
0.712
0.763
RNN (+LM+NS,) L)
0,971
0.150
0.954
0.961
0.765
0.744 0.04
0.765
LSTM (S)
0.963
0.150
0.954
0.944
0.610
0.09
0.763
LSTM (L)
0.989
0.056
0.988
0.987
0.746
0.717 0.08
0.763
LSTM (4LM, S)
0.786
0.440
0.774
0.751
0.763
0.711 0.10
0.763
LSTM (+LM,
0.786
0.444
0.782
0.751
0.763
0.711 + 0.10
0.763
LSTM (+NS, S)
0.966
0.145
0.953
0.934
0.743
0.761 0.01
0,763
LSTM (+NS, L)
0.987
0.068
0.982
0.985
0.838
0.731 0.12
0.884
LSTM (+LM+NS, S)
0.786
0.441
0.774
0.751
0.763
0.711 0.10
0.763
LSTM (+LM+NS, L.)
0.786
0.444
0.782
0.751
0.763
0.711 0.10
0.763
Table 15: Full results on the Marked Copy language.
Model
Train
Val. CE
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0,970
0.113
0.970
0.977
0.548
0.565 + 0.04
0.639
Tf (L)
0.859
0.327
0.866
0.872
0.795
0.698 + 0.07
0.795
Tf (+LM, S)
0.970
0.114
0.970
0.977
0.542
0.614 0.10
0.846
(+LM, L.
0,949
0.206
0.937
0.955
0.625
0.646
0.785
Tf (+NS. S)
0,991
0.035
0.992
0.991
0,588
0.627 + 0.11
0,872
(+NS. L)
0.950
0.213
0.922
0.950
0.843
2.693
0,856
TF (+LM+NS.5
0.990
0,025
0.991
0.992
0.550
0.573
0.827
(+LM+NS.. L)
0.963
0.226
0.944
0.970
0.573
0.612 0.08
0.775
RNN (S)
0.970
0.118
0,970
0.977
0.602
0.12
0,920
RNN (L)
0.958
0.134
0.964
0.965
0.946
0.710
0,946
RNN (+LM, S)
0.970
0.115
0.970
0.977
0.545
0.756
0.945
RNN (+LM, L)
0.959
0.135
0.965
0.969
0.595
0.945
RNN (+NS, S)
0.970
0.115
0.970
0.977
0.677
0.755 0.14
0,908
RNN (+NS, L)
0.960
0.133
0.965
0.967
0.946
0.757 0.13
0,946
RNN (+LM+NS, S)
0,970
0.117
0.970
0.976
0.598
0.730 0.15
0,946
RNN (+LM+NS, L)
0.961
0.127
0.966
0.968
0.591
0.728 1728+0.11 0.14
0.945
LSTM (S)
0.970
0.113
0.970
0.977
0.564
0.691 0.15
0,946
LSTM (L)
0.970
0.099
0.976
0.977
0.649
0.717
0,946
LSTM (+LM,
0.970
0.113
0.970
0.977
0,568
0.582 0.07
0.781
LSTM (+LM,
0.970
0.098
0.976
0.977
0.596
0.656
0.807
LSTM (+NS, S)
0.995
0.041
0.990
0.994
0.568
0.609 0.12
0.962
LSTM (+NS. L)
0.970
0.098
0.976
0.977
0.721
0.664 0.11
0,923
LSTM (+LM+NS, S)
0.970
0.113
0.970
0.977
0.631
0.604 1044000 0.09
0.849
LSTM (+LM+NS, L)
0.970
0.098
0.976
0.977
0.657
0.600 + 0.07
0.760
36

---

Published as a conference paper at ICLR 2025
Table 16: Full results on the Missing Duplicate language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
0.938
0.200
0.933
0.949
0.614
0.650 0.09
0.781
TY (L)
0,856
0.316
0.876
0.874
0.857
0.709 1 0.10
0.857
TT (+LM, S)
0,880
0.311
0.871
0.890
0,638
0.608 1: 0.05
0.687
TT (+LM,, L)
0.856
0.315
0.876
0.874
0.782
0.699 1: 0.09
0.796
Tf (+NS,
0.953
0.169
0.943
0.952
0.720
0.637 0.10
0.857
Tf (+NS, L)
0.860
0.317
0.875
0.874
0.777
0.651 + 0.07
0.777
TI (+LM+NS, S)
0.955
0.166
0.948
0.956
0,696
0.661 = 0.08
0,760
Tf (4LM+NS, L.)
0.864
0.315
0.880
0.874
0.858
0.728 + 0.11
0,858
RNN (S)
0.946
0.176
0.944
0.949
0.919
0.824 0.10
0.944
RNN (L)
0.951
0.163
0.953
0.957
0.783
0.815 0.07
0.937
RNN (+LM. S)
0,951
0.178
0.946
0.957
0.945
0.789 0.10
0.945
RNN (+LM. L)
0,951
0.163
0.953
0.957
0.945
0.860 +: 0.07
0,945
RNN (+NS,
0.959
0.162
0.952
0.959
0.946
0.804 0.14
0.946
RNN (+NS, L)
0.982
0.116
0.967
0.970
0.942
0.879 0.10
0.945
RNN (+LM+NS, S)
0.950
0.179
0.946
0.957
0.945
0.790
0.945
RNN (+LM+NS, L)
0,951
0.162
0.954
0.957
0.696
0.946
LSTM (S)
0.951
0.178
0.946
0.957
0.926
0.852
0.945
LSTM (L)
0.951
0.162
0.953
0.957
0.922
0.794 0.07
0.922
LSTM (4LM, S)
0.951
0.179
0.946
0.957
0.945
0.795 0.15
0.945
LSTM (+LM,
0,951
0.161
0.953
0.957
0.771
0.769 + 0.12
0,945
LSTM (+NS, S)
0.958
0.163
0.951
0.957
0.946
0,821 - 0.15
0.946
LSTM (+NS, L)
0.951
0.162
0.953
0.957
0.913
0.784
0.945
LSTM (+LM+NS, S)
0.954
0.174
0.947
0.957
0,940
0.770
0,945
LSTM (+LM+NS, L.
0.951
0.162
0.953
0.957
0.904
0.749
0.904
Table 17: Full results on the Odds First language.
Model
Train
Val. CE
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0.966
0.122
0.968
0.966
0.537
0.592 + 0.11
0,851
Tf (L)
0.835
0.345
0.853
0.849
0.850
0.730 + 0.09
0.850
Tf (+LM, S)
0.969
0.116
0.969
0.968
0.536
0.559 0.07
0.754
(+LM, L.
0,958
0.207
0.924
0.959
0.561
0.613 0.09
0.763
Tf (+NS. S)
0.993
0.048
0.991
0.993
0,545
0.537 + 0.00
0,545
(+NS. L)
0.941
0.236
0.919
0.944
0.861
0.724
0.861
TF (+LM+NS.5
0.995
0,043
0.991
0.998
0.538
0.579
0.799
(+LM-NS.. L)
0.955
0.182
0.937
0.952
0.864
0.693
0.864
RNN (S)
0.966
0.119
0.968
0.966
0.544
0.15
0,948
RNN (L)
0.957
0.137
0.962
0.959
0.948
0.795
0,948
RNN (+LM, S)
0.968
0.119
0.969
0.968
0.542
0.708 0.14
0.948
RNN (+LM, L)
0.959
0.137
0.963
0.959
0.948
0.766 + 0.15
0.948
RNN (+NS, S)
0,959
0.138
0.963
0.959
0.948
0.789
0.948
RNN (+NS, L)
0.967
0.116
0.972
0.967
0.594
0.712
0,948
RNN (+LM+NS, S)
0,969
0.117
0.969
0.968
0.536
0.575 1 0.08
0.777
RNN (+LM+NS, L)
0.957
0.138
0.961
0.959
0.669
0.758
0,947
LSTM (S)
0.969
0.116
0.969
0.968
0.572
0.668 1668+0.14
0,921
LSTM (L)
0,969
0.102
0.974
0.968
0.838
0.718 0.15
0,914
LSTM (+LM,
0,969
0.115
0.969
0.968
0.617
0.612 0.10
0.857
LSTM (+LM,
0.969
0.103
0.974
0.968
0.701
0.687 + 0.10
0.853
LSTM (+NS, S)
0.997
0.014
0.997
0.997
0.575
4.595
0.936
LSTM (+NS. L)
0,969
0.104
0.974
0.968
0.611
0.673 6613
0,906
LSTM (+LM+NS, S)
0.997
0.027
0.995
0.993
0.565
0.597 0.09
0.848
LSTM (+LM+NS, L)
0.969
0.103
0.974
0.968
0.964
0.696 + 0.13
0.964
37

---

Published as a conference paper at ICLR 2025
Table 18: Full results on the Binary Addition language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
0.925
0.235
0.919
0.922
0.673
0.643 0.13
0.913
TY (L)
0,915
0.262
0.902
0.915
0.645
0.654 1 0.09
0.778
TT (+LM, S)
0,974
0.107
0.963
0.962
0.562
0.602 1 0.10
0,913
TT (+LM,, L)
0.933
0.228
0.917
0.925
0.744
0.713 1 0.09
0.876
Tf (+NS,
0.976
0.084
0.977
0.968
0.632
0.629 0.13
0.914
Tf (+NS, L)
0,924
0.248
0.910
0.924
0.831
0.692 + 0.10
0,831
TI (+LM+NS, S)
0,975
0.094
0.968
0.966
0.577
0.615
0,896
Tf (4LM+NS, L)
0.967
0.154
0.944
0.960
0.850
0.684 + 0.11
0,854
RNN (S)
0.924
0.227
0.922
0.921
0.549
0 0.10
0.879
RNN (L)
0.927
0,236
0.915
0.924
0.598
0.813
0.878
RNN (+LM. S)
0.943
0.194
0.931
0.940
0,566
0.718
0.893
RNN (+LM. L)
0,929
0.235
0.916
0.925
0.822
0.703:0.1
0,914
RNN (+NS,
0.988
0.085
0.979
0.981
0.604
0.743 0.12
0.915
RNN (+NS, L)
0.930
0.226
0.914
0.928
0.731
0.790
0.915
RNN (+LM+NS, S)
0.978
0.094
0.974
0.968
0.604
0.10
0.898
RNN (+LM+NS, L)
0,939
0.214
0.923
0.934
0.903
0.762
0.914
LSTM (S)
0.929
0.220
0.925
0.925
0.595
0.74
0.916
LSTM (L)
0.929
0.233
0.916
0.925
0.651
0.783 0.09
0.915
LSTM (4LM, S)
0.989
0.081
0,979
0.969
0.685
0.702 + 0.12
0.914
LSTM (+LM, L.)
0,951
0.210
0.923
0.952
0.692
0.780 + 0.09
0,915
LSTM (+NS, S)
0.988
0.083
0.981
0.976
0,648
0.709 0.13
0.902
LSTM (+NS, L)
0.929
0.233
0.916
0.925
0.916
0.750
0.916
LSTM (+LM+NS, S)
0.992
0.074
0.981
0.982
0,581
0.715 1
0.866
LSTM (+LM+NS, L.
0.986
0.115
0.966
0.978
0.820
0.786 +
0.916
Table 19: Full results on the Binary Multiplication language.
Model
Train
Val. CE +
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0.959
0.118
0.958
0.952
0.563
0.616 + 0.12
0,889
Tf (L)
0.933
0.216
0.916
0.928
0.720
0.705 = 0.09
0.821
Tf (+LM, S)
0.973
0.082
0.974
0.968
0.627
0.573 0.03
0.627
(+LM, L.
0,932
0.255
0.899
0.931
0.582
0.688 0.10
0.807
Tf (+NS. S)
0.975
0.071
0.977
0.958
0.760
0.700 + 0.11
0,922
(+NS. L)
0.952
0.165
0.941
0.949
0.723
4.703:0.1
0.923
TF (+LM+NS.
0.983
0,054
0.979
0.970
0.617
0.642
0.884
(+LM+NS.. L)
0.972
0.169
0.933
0.961
0.615
0.637 1637:0077 0.07
0.787
RNN (S)
0.937
0.168
0,944
0.930
0.606
0.11
0,919
RNN (L)
0,936
0.194
0.934
0.931
0.889
0.801 0.07
0.893
RNN (+LM, S)
0.980
0.063
0.980
0.969
0.604
0.672
0.897
RNN (+LM, L)
0.936
0.192
0.934
0.931
0.597
0.12
0.919
RNN (+NS, S)
0.963
0.122
0.958
0.955
0.559
0.684 0.14
0.919
RNN (+NS, L)
0.935
0.195
0.934
0.931
0.645
0.750
0,919
RNN (+LM+NS, S)
0,982
0.060
0.978
0.973
0.610
0.11
0,919
RNN (+LM+NS, L)
0.956
0.190
0.937
0.945
0.910
0.784
0,916
LSTM (S)
0.946
0.145
0.951
0.939
0.616
0.73
0,902
LSTM (L)
0.937
0.189
0.933
0.933
0.774
0.00
0.792
LSTM (+LM,
0.995
0.019
0.994
0.983
0.610
0.664 0.10
0.898
LSTM L.)
0.961
0.155
0.943
0.952
0.876
0.759 +
0.897
LSTM (+NS, S)
0.992
0.046
0.987
0.980
0.652
0.779
0.919
LSTM (+NS. L)
0.961
0.165
0.942
0.966
0.890
0.784
0,915
LSTM (+LM+NS, S)
0.997
0.031
0.994
0.986
0.639
0.638 0.07
0.756
LSTM (+LM+NS, L)
0.971
0.123
0.953
0.966
0.771
0.688 - 0.10
0.915
38

---

Published as a conference paper at ICLR 2025
Table 20; Full results on the Compute Sqrt language.
Model
Train
Val. CE
Val.
Test
L. Test
L. Test (Mean)
L. Test (Max)
Tf (S)
0.956
0.130
0.954
0.948
0.718
0.673 0.10
0.828
TY (L)
0,937
0.254
0.898
0.926
0.629
0.705 1 0.10
0,860
TT (+LM, S)
0,971
0.100
0.964
0.960
0,629
0.623 1: 0.10
0.885
TT (+LM,, L)
0,911
0.264
0.887
0.906
0.629
0.648 1: 0.09
0.782
Tf (+NS,
0.973
0.101
0.967
0.967
0.578
0.631 0.11
0.852
Tf (+NS, L)
0,953
0.205
0.919
0.947
0.645
0.639 + 0.06
0.739
TI (+LM+NS, S)
0,970
0.094
0.968
0.963
0.592
0,648 = 0.11
0,856
Tf (4LM+NS, L.
0.960
0.177
0.932
0.952
0.811
0.695 + 0.11
0,846
RNN (S)
0.892
0.280
0.897
0.884
0.887
0.784 0.12
0.887
RNN (L)
0.892
0.306
0.878
0.884
0.773
0.699 0.13
0.887
RNN (+LM. S)
0.976
0.110
0.965
0.975
0.647
0.681
0,882
RNN (+LM. L)
0,911
0.281
0.893
0.898
0,806
4.776:0.09
0,878
RNN (+NS,
0.982
0.099
0.976
0.982
0.636
0.720 1:00:00 0.15
0.887
RNN (+NS, L)
0.894
0.301
0.874
0.884
0.709
0.767 1.07
0.887
RNN (+LM+NS, S)
0.987
0.080
0.979
0.983
0.644
0.638 0.10
0.887
RNN (+LM+NS, L)
0,917
0.283
0.888
0.910
0.816
0.715
0.887
LSTM (S)
0.892
0.278
0.897
0.884
0.853
0.836
0.887
LSTM (L)
0.892
0.307
0.878
0.883
0.887
0.799 0.07
0.887
LSTM (4LM, S)
0.995
0.043
0.989
0.989
0.658
0.653 + 0.15
0.887
LSTM (+LM,
0.985
0.123
0.959
0.982
0.610
0.697 + 0.13
0.887
LSTM (+NS, S)
0.986
0,076
0.976
0.978
0.576
0.795 = 0.10
0.887
LSTM (+NS, L)
0.915
0.293
0.869
0.914
0.729
0.830
0.887
LSTM (+LM+NS, S)
0.995
0.036
0.991
0.994
0.659
0.614
0.831
LSTM (+LM+NS, L.
0.984
0.140
0.944
0.981
0.613
0.679
0.887
Table 21: Full results on the Bucket Sort language.
Model
Train
Val. CE +
Val.
S. Test
L. Test
L. Test (Mean)
L. Test (Max)
T (S)
0.974
0.107
0.973
0.963
0.569
0.629 + 0.08
0.764
Tf (L)
0.821
0.417
0.806
0.824
0.670
0.727 = 0.03
0.756
Tf (+LM, S)
0.986
0.029
0.989
0.977
0.556
0.590 0.10
0.858
(+LM, L.
0,988
0.094
0.973
0.975
0.837
0.706 0.11
0,880
Tf (+NS. S)
0.976
0.077
0.978
0.977
0.891
0.616 + 0.12
0.891
(+NS. L)
0.945
0.200
0.920
0.936
0.878
0.709 0.13
0.884
TF (+LM+NS.5
0.997
0.008
0.999
0.992
0.553
0,603
0.874
(+LM-NS.. L)
0.960
0.168
0.947
0.948
0.579
0.572
0.629
RNN (S)
0.967
0.132
0.966
0.953
0.911
0.709
0,911
RNN (L)
0.945
0.181
0.942
0.929
0.757
0.769 0.14
0.897
RNN (+LM, S)
0.990
0.063
0.984
0.977
0.575
0.647 0.12
0.880
RNN (+LM, L)
0.960
0.128
0.965
0.953
0.630
0.706 0.10
0.908
RNN (+NS, S)
0.965
0.138
0.964
0.957
0.924
0.778 0.13
0.924
RNN (+NS, L)
0.962
0.126
0.966
0.954
0.957
0.771 1 0.15
0.957
RNN (+LM+NS, S)
0,962
0.142
0.962
0.950
0.930
0.836 1 0.09
0,951
RNN (+LM+NS, L)
0.960
0.129
0.965
0.953
0.613
0.690 + 0.09
0.869
LSTM (S)
0.969
0.095
0.966
0.966
0.546
0.688 0.13
0.967
LSTM (L)
0,971
0.109
0.970
0.956
0.813
0.700
0.813
LSTM (+LM,
0.998
0.013
0.997
0.991
0.592
0.645 144500.0 0.10
0.774
LSTM (+LM,
0,999
0.003
1.000
0.998
0.605
0.621 + 0.10
0.769
LSTM (+NS, S)
0.996
0.015
0.998
0.992
0.576
0.572 0.04
0.664
LSTM (+NS. L)
0,979
0.087
0,980
0.968
0,592
0.588 0.04
0.671
LSTM (+LM+NS, S)
0,992
0.039
0.991
0.984
0.569
0.554 4.03
0.597
LSTM (+LM+NS, L)
0.989
0.075
0.982
0.981
0.594
0.640 + 0.09
0.835
39

---

Published as a conference paper at ICLR 2025
Table 22: Results for different model sizes.
Tf
RNN
LSTM
Language
32k
64k
128k
32k
64k
128k
32k
64k
128k
Repeat
0.85
0.86
0.85
1.00
1.00
1.00
1.00
1.00
1.00
Parity
0.54
0.54
0.54
0.53
0.52
1.00
1.00
Cycle Navigation
0.93
0.93
0,93
0.93
0.93
0.93
0.93
0.93
0,93
Modular Arithmetic
0.86
0.83
0.92
1.00
1.00
1.00
1.00
1.00
1.00
Dyck-(2,
0.73
0.80
0.79
0.98
0.98
0.98
0.98
0.98
0.98
Majority
1.00
0.99
0.93
0.94
1.00
0.99
Stack Manipulation
0.82
0.87
0.87
0.93
0.93
0.93
0.84
0.89
0,92
Marked Reversal
0.75
0.76
0.79
0.95
0.95
0.94
0.91
0.86
0.96
Unmarked Reversal
0.63
0.63
0.63
0.76
0.76
0.76
0.76
0.76
0.78
Marked Copy
0.76
0.80
0.85
0.95
0.95
0.95
0.94
0.95
0.92
Missing Duplicate
0.83
0.86
0.77
0.95
0.95
0.95
0.92
0.95
Odds First
0.77
0.85
0.85
0.95
0.95
0.92
0.95
0.91
0,95
Binary Addition
0.79
0.78
0.83
0.92
0.88
0.88
0.92
0.92
0,92
Binary Multiplication
0.80
0.82
0.92
0.92
0.89
0.78
0.89
0.79
0.92
Compute Sqrt
0.82
0.86
0.80
0.89
0.89
0.89
0.89
0.89
0.89
Bucket Sort
0.76
0.76
0.87
0.92
0.90
0.91
0.80
0.81
0.93
H RESULTS WITH SMALLER AND LARGER MODELS
Is the reason that models do not get perfect accuracy in $5 simply because they are not big enough? In this section, we find that the answer is generally no. To test this, we show results with larger and smaller models Table 22. The experiments $5 use models with approximately 64k parameters. Here, we train models with approximately 32k, 64k, and 128k parameters, using the same rounding technique described in $4. We omit the languages Even Pairs and First, as all architectures already get perfect accuracy on them in Table 2. We run experiments according to the expressivity setup described in $4, but using only a recognition head, without auxiliary loss terms. We report the best test accuracy of 10 runs. There are only two cases where larger model results in an improvement over Table more than 0.01, which we show in bold. We see strict positive correlation between accuracy and model size in only few cases: transformer Marked Reversal, Marked Copy, and Binary Multiplication; and LSTM on Stack Manipulation and Bucket Sort. Interestingly, we Otherwise, we do not see clear trends, suggesting that the limitations are due to model architecture rather than size.
negative correlation in the case of RNN Binary Multiplication.
I PERFORMANCE VS. INPUT LENGTH
We show recognition cross-entropy (lower is better) input length for the models shown under "Expressivity" in Table 2. At every length n on the x-axis that is a multiple of 10, we show the average cross-entropy of the model all strings in the long test with lengths in the range [n - 10, + 10] (this smooths the curves for the sake of readability). The shaded regions indi- cate one standard deviation. The vertical dashed lines indicate the maximum lengths the training and validation sets. The horizontal dashed lines mark log 2, which is the threshold for incorrect predictions. In general, we find that cross-entropy usually does not increase significantly on longer strings. Notable exceptions include Repeat 01, Parity, Modular Arithmetic, and Dyck-(2,3) for the transformer and Majority for the RNN. This is contrast to Delétang et al. (2023), who found that models often fail catastrophically on longer input strings in their string-to-string transduction setup.
40

---

Published as a conference paper at ICLR 2025
Transformer
LSTM
RNN
Even Pains
Repeat 01
Parity
Cross- Entroy
Incorrect
Incorret
Incornect
200
Cycle Navigation
Modular Arithmettcc
(2c
Cross- Entropy
Incorrect
Incorrect
0.6
Incderoct
300
400
First
Majority
Stack Manipulation
Cross Cross-Entropy Entro-trrpyy
Incurrect
Incorrect
0.5
Incorrect
0.5
100
300
300
400
500
1.00
200
300
400
500
100
200
300
4.00
500
1.5
Marked Reversal
Unmarked Reversal
1.5
Marked Copy
Cross- Cross-Entropp Entropy
Incorrest
Incomoct
Incorrect
100
300
300
400
500
1000
200
300
603
500
1.00
200
300
400
503
Missing Duplicate
Odds First
Binary Addition
Cross- Cross-Entropp Entropy
Incorrest
Incorrect
Incerrect
300
2000
300
200
100
2010
Binary Multiplication Incorrect
Compute Sqrt
Bucket Sort
Cross- Cross-Entropy Entrop
200
300
400
100
200
Input Length
Input Length
Input Length
Figure 3: Recognition cross-entropy (lower is better) vs. input length for the models shown under "Expressivity" in Table 2.
41

---

Published as a conference paper at ICLR 2025
J EDIT DISTANCE FROM LANGUAGES
In this section, give formal definition of string-language edit distance and provide algorithm for computing for regular languages. Definition 10. For any string w and language L, the edit distance D(w, L) is defined as
D(w, L) min D(w, u), wET.
(20)
where D(w, u.) is the Levenshtein distance between w and u, or the minimal number of single-symbo edits (insertions, deletions, and replacements) required transform w into u.
Suppose is regular language over alphabet Σ recognized by DFA A. Then for any E", D(w, L) can be computed as follows:
1. Construct a nondeterministic weighted finite automaton (WFA) AD(w.,) over the tropical semiring (Rzo U (oo), min, +, 00,00, that assigns weight D(w, u) to every string u (Fig- ure 4);
2. Lift A to the tropical semiring by assigning weight 0 to all transitions and accepting states, resulting in a WDFA A.gr.;
3. Intersect A.ez and Ap(w..) using the standard WFA intersection algorithm (Mohri, 2009), resulting in automaton AD(.L) that encodes D(w, u) for every E L; and
4. Compute the shortest path in AD(,E) using the Floyd-Waad Warshall algorithm (Floyd, 1962; Warshall, 1962).
The rest of this section describes these steps in more detail and argues their correctness.
J.1 WEIGHTED FINITE AUTOMATA
We start by defining WFAs, which used in multiple steps. This is more general, nondetermin- istic version of Def. 4.
Definition 11. A weighted finite automaton (WFA) over semiring (K, 4. 8, 0,10) is a tu-
ple A (Q, E, 2.0.go.PP. such that (1) Q is finite set of states, (2) Σ an alphabet,
Q + K is the transition function, and (4) qo E Q is the start state;* and (5) p: Q + K. is the accept weight function. If 8(g, a, r) w, we say that A has a transition a/w E
(3) 8: Q x (2' (e))
from q to that scans a with weight w, and we write
This definition nondeterministic in the sense that it permits multiple outgoing transitions on the same symbol from the same state. We define paths and path weights in a similar way to $3.1.2.
Definition 12. A path æ in WFA A sequence of states and transitions
01/w0
6m /wmm
P1 ... Pm-
T'm
(21)
such that
1. To 40. and
0041//004
2. for all i O,..,, 1, ri
Ti+1
E 8.
We say that ı scans the string Ome and that the path weight of n is
def
X me
p(rm)
(22)
SSome definitions initial weight function A: Q - K. to indicate start states. For simplicity, start state with weight of 1.
42

---

Published as a conference paper at ICLR 2025
Note that in nondeterministic WFA, multiple paths may the same string. We denote the set of all paths A as II),,, and the set paths that scan w as II(AA, w).
The weight that a WFA assigns string is the sum of the weights of all paths that scan that string. Definition 13. The stringsum of string w E E" under WFA A is
A(w)
w(T).
(23)
=EII(A,.)
We also make use of the sum of the weights of all paths in a WFA. Definition 14. The allsum of WFA is
((A) del
w(T)
(24a)
+EII(A))
A(w).
(24b)
WEΣ
J.2 ALGORITHM DETAILS
First, we encode the input string w wi W2 .......0 Wn into chain-like WFA AD(w,) in the tropical semiring, as shown in Figure 4.
/ E/1 a/l (a E {wi))
W2/2
Wn/P 0n E/1 a/1 (a E E {wn})
E/1 a/1 (a E (w2))
q1
Qn
a/1 (AE
a/1 E)
a/1 (a
Figure 4: Diagram of AD(w,). The double-cireled state has accept weight O; the others have accept weight xx.
Given an input string u E Σ', every path AD(w.) that scans u encodes a way of transforming into u. Every time transition deviates from scanning w by inserting, replacing, or deleting symbol, it incurs cost of 1. Taking the minimum weight of any path that seans u gives D(w, u). Lemma 1. For all u E Σ", AD(W.)(u) = D(w, u).
Proof. For every w; in w, AD(w.) either matches symbol in with AD(w.) with cost 0, simulates the deletion of Wi with cost so that can continue scanning u some other way, or simulates the replacement of wi with a symbol in with cost 1. Before and after symbols in AD(W.) can also simulate the insertion of any number of symbols, each with cost 1. So, path is in II [[A(( u) iff it corresponds a way of changing w into u, and its weight is the number of edits it performs to turn into u. The stringsum gives the minimum number of edits.
AD(w.)(u)
W(T)
(25a)
*EI(AA(w.)...)
min =ETI(AD
W W(T)
(25b)
D(w, u)
(25c)
Next, lift the weights of A into the tropical semiring, resulting in WDFA AEL. The weights of all transitions and the accept weights all accepting states in A are set to in A. All other weights are set So, A.et. z. assigns weight 0 to all strings in L,, and weight co to all others.
43

---

Published as a conference paper at ICLR 2025
Lemma 2. For all E Σ"
0 ifu E AEc(u)=
100 otherwise.
(26)
Proof. By definition, A has path that scans iff L. By construction, A. has path that scans u with weight 0 iff A has a path that seans u. Therefore, if L, the stringsum A is the minimum of one over an empty set of path weights, which is defined to be co in the tropical semiring.
path weights of O, so it is O. Otherwise, the stringsum is summation
Next, we intersect AD(w.) and A using the standard intersection algorithm for WFAs, resulting WFA AD(.L) that assigns weight Dww, u) if u E L and oo otherwise. Lemma 3. For all E E",
(D(w,u) u) if
AD(,L)(u)
00
(27)
otherwise.
Proof. By definition of intersection, the stringsum the intersected automaton
AD(,L)(u) def AD( @ Aez(uu)
(28)
Using Lemmas and and Eq. (28), we have
[D(w, u) +0 u L otherwise
(D)
(29a)
(D(w, u) +
(D(w,u) u) if
(29b)
0o
otherwise.
Finally, we compute the allsum of AD(.L.), which gives us the minimum edit distance from w to any string u E L. Let AD(.L) = (Q, E, 40- p). To compute the allsum, we first use the Floyd- Warshall all-pairs shortest path algorithm. 9 to compute the shortest path weight from go ro denoted 4go r), for every r E Q. We then compute the allsum as
7(AD(.L)
A Algo. p(r)
(30a)
rEQ
min Algo. r] + p(r). rE
(30b)
This gives us the edit distance D(w, L). Theorem 1. Z(AD(.L)) D(w, L).
Proof. By definition, the allsum is
Z(AD(,)) ADC,L;(u.
(31)
wEE*
Using Lemma and Def. 10, we have
Z(A Z(AD(.L)) = min AD(,L)(U)
(32a)
weXt
=min D(w, u)
(32b)
ael.
=D(w, D).
(32c)
9This is special case of L.chmann's 's algorithm (Algorithm 4) The only difference is that do not need to compute the operation in Algorithm 4, line which is always in the tropical semiring.
44


Reviews:
[{"review_id": "UhrsQAdm9M", "reviewer": "Reviewer_v4NN", "summary": "The paper explores formal language recognition tasks with different architectures. The authors argue that the primary motivation underlying formal language theory is language recognition and not next token prediction as used by existing literature. As such, they propose a novel data generation algorithm that can generate positive and hard negative examples from a diverse set of formal languages. Finally, through extensive experiments, they show that RNNs and LSTMs generally outperform transformer architectures.", "questions": "Please check my questions in the above section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength of the paper lies in its motivation to quantify gaps between different architectures by formal language recognition tasks. The authors start with a discussion on the basis of formal language theory, and how existing works differ from this basis in their experimental settings. Then, they propose a novel data generation algorithm that can sample positive and hard negative samples from each formal language. The algorithm has been discussed in great detail, and the running time has been contrasted with naive data generation algorithms.\n\nThe authors then conduct extensive comparisons of RNNs, LSTMs, and transformers across a wide suite of formal languages. Interestingly, RNNs and LSTMs generally perform better. Other interesting observations include (a) transformers can't learn Dyck-(2,3), as opposed to the results of Yao et al. (2021), and (b) the order of ranking between the different architectures is different from Deletang et al. (2023). The work emphasizes the need for empirical validations that align with theoretical results for a clearer understanding of neural network capabilities.", "weaknesses": "As such, the work doesn't have many weaknesses. I have a couple of questions regarding the setup.\n\na) **Behavior with input length**\n- The authors report aggregated scores over strings of all lengths. It would be interesting to include a discussion on input length v/s performance for different models. Are there tasks where the transformer's performance shows a more exponential/drastic drop with input length? \n\nb) **Tasks where additional loss terms hurt:** \n- Are there tasks where the additional language model loss and the next symbol loss hurt performance? For example, for parity, language model loss can intuitively hurt performance as the token at each step could be randomly selected for each string. \n- Furthermore, how do the optimal $\\lambda$ hyper-parameters behave for different tasks for different models? Are there cases, where the additional losses help one architecture more than others?\n\nc) **How is 64k parameters and 5 layers decided for the experiments?** What happens for smaller and wider models?", "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": "", "extra_scores": {}}, {"review_id": "JJWTOKpY0K", "reviewer": "Reviewer_t9kn", "summary": "This paper takes a formal language theory approach to string classification and asks how well various types of neural networks recognize languages. The authors evaluate the network types on eighteen formal languages from three of the four languages classes of the Chomsky hierarchy (excluding recursively enumerable languages). Length generalization is tested systematically by using a short and a long validation set, and a test set that comprises much longer strings than in either validation set. They find that recurrent types of networks tend to be more accurate than transformers. The paper contains some analysis of certain languages on which one or more network types exhibits poor performance. The authors additionally describe an algorithm for efficiently sampling strings from a regular language that they describe as concurrent work.\n\n--------\n\nI will refer to the following papers in this review. [1] is relevant because the paper being reviewed here appears to be, at least in part, a response to [1]. [2] is relevant as an example of prior work with substantial overlap in experimental setting and possibly different results. [3] provides theoretical insights into the results reported in Section 4 of the paper reviewed here.\n\n* [1] Neural networks and the chomsky hierarchy, Del{\\'e}tang et al, 2023\n* [2] MLRegTest: A Benchmark for the Machine Learning of Regular Languages, van der Poel et al, 2024\n* [3] Why are Sensitive Functions Hard for Transformers?, Hahn & Rofin, 2024", "questions": "1. Can you clarify the contribution of this work in light of previous work on language recognition with neural networks? For instance, the authors of [2] have evaluated with larger datasets and have trained many more models. How does your contribution differ in terms of language classes tested and insights derived therefrom? Are there other aspects of your work that can be highlighted?\n2. Have you considered investigating the scaling properties of the neural networks on the language recognition task? [1] demonstrated that none of the networks in your study are able to perform transduction on recursively enumerable languages without the support of an external memory module (e.g. Stack-RNN or Tape-RNN), but -- with respect to scaling -- only showed that increasing the amount of training data when the network is large enough to memorize the training data did not help generalization for some neural network types. Related: do you have any reason to believe that results you report here that differ in order from e.g. [1] -- such as recognition on cycle navigation -- are not due to the capacity of the network? Would larger networks recognize cycle navigation better?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This is a well-performed study of the ability of neural networks to recognize formal languages. The writing is of good quality, the methodology is clearly communicated, and it introduces an efficient algorithm for sampling strings from regular languages. Models are trained with validation sets of length [0, 40] (short) or [0, 80] (long) and tested on a set with strings of length [0, 500]. The authors of this study introduce several additional languages -- Dyck-(2, 3), binary strings that start with 1, and a distinction between marked and unmarked reversed strings -- that do not appear in [1]. The appendix contains copious information about the models trained.", "weaknesses": "* The general method for training neural networks as language recognizers is straightforward and is difficult to see as a substantial contribution (see similarities with e.g. [2]).\n* The algorithm for efficiently sampling from a regular language is described, and the authors state that they use it for sampling training and evaluation instances from the regular languages (class `R` in Table 1). Since the algorithm is only used to generate data for 25% of the types of languages in this study, the amount of page real estate devoted to it seems disproportionate, particularly since algorithms for sampling from a formal language are not typically showcased in this venue.\n* The insights about which languages are best-suited to which network types could be much deeper. With the literature on language recognition having advanced somewhat, reports that explain *the why* (e.g. [3]) are more compelling than those that describe *the what*. The results reported here are similar to [1] on the modular arithmetic language and marked string reversal and differ from [1] on cycle navigation. Some analysis is done here to characterize the kinds of errors transformers make on the task of recognizing strings from the cycle navigation language. The authors describe how with cycle navigation the recognition error of the instances with the highest cross entropy loss is always due to the model recognizing an instance with an incorrect final character (the position in the cycle). Since [1] reports 100% transduction accuracy for cycle navigation for RNN and LSTM, and 62% for a transformer, what explains the ceiling on recognition accuracy for all networks here? The analysis of Dyck-(2, 3) and Repeat 01 seems to primarily indicate that, with transformers,  some negative instances are near the decision boundary to positive instances. More insights about *why* this occurs with transformers and not the other networks would improve the paper.\n\nNit\n* The standard deviation of recognition is a figure of merit for distinguishing neural network types, particularly in cases when no network achieves perfect recognition accuracy. This is included in the appendix. It would be helpful to report in Table 2 mean and stdev of recognition accuracy across multiple runs using the model from the appropriate table in the appendix.", "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": "", "extra_scores": {}}, {"review_id": "mt8yIQJLak", "reviewer": "Reviewer_gn5o", "summary": "This paper argue that there exists a methodological disconnect between the complexity theory of the formal language and the empirical evaluation of neural networks' computational capabilities. The existing work related the capabilities of neural networks with Chomsky hierarchy, which is framed in terms of language recognition (classifying whether strings belong to a language). However their empirical studies evaluate models on string-to-string transformation tasks instead. This paper propose an experimental setup for training neural networks as recognizers, and a more efficient algorithm for length-controlled sampling from finite automata. The empirical results show that RNNs and LSTMs often perform better than transformers on the formal language recognition task.", "questions": "Please refer to the weaknesses part.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. It is an important direction to study neural networks' computational ability through formal language theory.\n2. This paper introduces an efficient algorithm for length-controlled sampling from finite automata, which may have practical value for future research in formal language processing.\n3. Experiments are conducted on a variety of formal languages with 3 neural models with different architectures (RNN, LSTM, transformer). The methodology appears to be well-documented and reproducible.", "weaknesses": "1. The paper overlooks significant existing work on training neural networks for formal language recognition tasks (e.g. [1, 2, 3]). This oversight diminishes the claimed novelty of the proposed experimental setup. The authors should acknowledge and position their work in relation to previous studies.\n2. The claimed technical improvement in sampling from finite automata appears to be the main novel contribution, but its significance needs better contextualization.\n\nReferences       \n[1] Bhattamishra, Satwik, Kabir Ahuja, and Navin Goyal. \"On the ability and limitations of transformers to recognize formal languages.\" EMNLP 2020.          \n[2] William Merrill. 2019. Sequential Neural Networks as Automata.           \n[3] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages.", "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": "", "extra_scores": {}}, {"review_id": "JTlVYzHy7N", "reviewer": "Reviewer_eTo5", "summary": "This paper builds on Deletang et. al. 2023, and rigorously tests standard sequence neural architectures for their ability to _recognise_ formal languages that span the Chomsky Hierarchy. It also proposes a way to sample sequences from automata with a length constraint in order to generate training data for the experiment.", "questions": "Can the length constrained algorithm for DFAs be modified for other automata? I suspect not due to the combinatorial way the paths compose for these other automata, and the infinite nature of the stack, etc.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper references important work on the theoretical expressibility of Transformers, and other neural architectures, and, along with Deletang et. al. 2023, is useful information for understanding the learnability of these architectures in an empirical way.\n\nIt follows a similar set of experiments as the Deletang et. al. 2023 paper, while focusing on the recognition aspect of formal languages, rather than mixing recognition and transduction tasks. This of course comes with some drawbacks (e.g. uninformative training signal), but the authors spend some time addressing that issue with other reasonable auxiliary losses.\n\nThe length-constrained sampling from DFAs is an interesting aspect, even if it takes a bit of a detour from the original point of the paper\n\nUnderstanding the limitations of the neural architectures we use is important, and can only be explored and understood in smaller scale experiments lik", "weaknesses": "I have only minor comments here as I find the paper well-executed:\n- Table 2: decide on a threshold and make results above it visually dissimilar, this will give a better idea of where a model sits on these benchmarks and the hierarchy they’re measured to be in\n- Missing a more conclusive figure regarding placement of models wrt to their level in the chomsky hierarchy. I know this is a tough ask, since the mapping of these models don’t fit as neatly into the Chomsky hierarchy as Deletang, et. al. 2023 suggest. Perhaps a better visual representation could be figured out.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)