Rule Extrapolation in Language Modeling: A Study of Compositional Generalization on OOD Prompts
Authors: Anna Mészáros
Szilvia Ujváry
Wieland Brendel
Patrik Reizinger
Ferenc Huszár
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Language models
autoregressive models
out-of-distribution generalization
compositional generalization
rule extrapolation
formal languages
Primary area: deep_learning_architectures

Abstract: LLMs show remarkable emergent abilities, such as inferring concepts from presumably out-of-distribution prompts, known as in-context learning. Though this success is often attributed to the Transformer architecture, our systematic understanding is limited. In complex real-world data sets, even defining what is out-of-distribution is not obvious. To better understand the OOD behaviour of autoregressive LLMs, we focus on formal languages, which are defined by the intersection of rules. We define a new scenario of OOD compositional generalization, termed \textit{rule extrapolation}. Rule extrapolation describes OOD scenarios, where the prompt violates at least one rule. We evaluate rule extrapolation in formal languages with varying complexity in linear and recurrent architectures, the Transformer, and state space models to understand the architectures' influence on rule extrapolation. We also lay the first stones of a normative theory of rule extrapolation, inspired by the Solomonoff prior in algorithmic information theory.

Rule Extrapolation in Language Models: A Study of Compositional Generalization on OOD Prompts
Anna Mészáros', Szilvia Ujváry!.5 Wieland Brendel2.44 Patrik Reizinger" and Ferenc Huszár"
University of Cambridge, Cambridge, United Kingdom
Max Planck Institute for Intelligent Systems, Tübingen, Germany 'ELLIS Institute Tübingen, Tübingen, Germany
*Tübingen AI Center, Tübingen, Germany 5 AI Center, UCL,, London, United Kingdom
Abstract
LLMs show remarkable emergent abilities, such inferring concepts from presum- ably out-of-distriuutin prompts, known as in-context learning. Though this success is often attributed the Transformer architecture, our systematic understanding is limited. In complex real-world data sets, even defining what is not obvious. To better understand OOD behaviour autoregressive LLMs, we focus on formal languages, which are defined by the intersection of rules. We define a new scenario of OOD compositional generalization, termed rule extrapolation. Rule extrapolation describes OOD scenarios, where the prompt violates at least rule. We evaluate rule extrapolation in formal languages with varying complexity in linear and recurrent architectures, the Transformer, and state space models understand the architectures' influence on rule extrapolation. We also lay the first stones of normative theory of rule extrapolation, inspired by the Solomonoff prior in algorithmic information theory.
is
Introduction
Autoregressive language models (AR LMs) can reach both low training and loss. but even minimal test loss is not predictive for out-of-distribttion (OOD) model performance (Liu et al. 2023 Reizinger al., 2024]. i.e. when the test data has vanishing probability under the training distribution. Despite the success of deploying modern language models in OOD situations, OOD generalization is not well understood theoretically. Recently, studies started to focus on a specific form of OOD generalization: compositional generalization in language models [Ahuja and Mansouri 2024 Han and Pado 20244 Ramesh al. 2024 Lake and Baroni [023] Reizinger et al., 2024). To systematically examine compositional generalization of AR LMs we study particular notion of OOD generalization, which we call rule extrapolation.
Rule extrapolation a form of compositional generalization: studies OOD behavior of language modely trained on formal languages defined by logical conjunction of rules.
For example, the "b language is the intersection of two rules: (R1) the number of a's is equal to the number of b's and (R2) a's precede b's. The prompt bhaab cannot completed to obey the R2, but it is still possible to satisfy (R1) (c.g., bbaaba). When language model trained on an intersection of rules remains consistent with one of the rules when another is broken, we say successfully extrapolated the rule beyond its training data.
Joint senior authors. Correspondence to am30498cam.ac ac. uk
Code available at:
github.comm wwt../////eerrrnnaaaaaaaaaaae rule,, httprpaaraaaammmeeeeeeeettrraort
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

A limited experiment by Reizinger et al. (2024) indicated that Transformers exhibit much-better than chance rule extrapolation performance on the formal grammar a²b", despite lacking any explicit inductive biases encouraging this behaviour. However, it remains unclear whether the behaviour observed was specífic to the Transformer or whether it holds more generally on wider range of formal languages. Inspired by this work, we conduct thorough empirical investigation of the role of architecture in rule extrapolation on a range of formal languages. As non-rigorous baseline, we also conducted small pilot human study to understand how people would generalize the rules.
We chose to study rule extrapolation because it appears to be a rational, or at least desirable, behaviour. However, we lack normative reason why this behaviour should be considered rational. It is unclear whether any OOD behaviours could be considered rational. This question led us to investigate how general rational algorithm for OOD prompt completion might be formalized. That is, instead of asking what models do, we ask what they should do if they were to be consistent with some principles of rational inference. We turn Algorithmic Information Theory (AIT) formalize normative model. We propose a paraamamttiic prior for next-token prediction inspired by the Solomonoff prior [Solomonoff] 20001] Li and Vitányil 1997). This prior helps resolve how rational model should behave in situations that are mathematically underspecified by their training: to extrapolate the simplest theories consistent with training data. Although, like Solomonoff's induction, our rational algorithm is uncomputable, it helps explain some of our empirical observations about rule extrapolation practical language models. Our contributions are:
We use formal languages to define scenarios for evaluating sequence models' OOD compositional
generalization, which we call rule extrapolation ($ 2.2);
We empirically evaluate different models' rule extrapolation in formal languages with varying complexity, we study linear, recurrent, Transformer and State Space models. We show that there is single architecture that emerges clear winner of rule extrapolation. Though Transformers fare very well in most scenarios we investigated, they struggle on regular languages ($ 4
Inspired by algorithmic information theory, propose normative theory for OOD prompt completion, which posits that rule learning and extrapolation should be governed by the relative
simplicities of rules (8 5):
To demonstrate the presence a similar simplicity bias in Transformers, We visualise the training dynamics enabling rule extrapolation the a²²² language. We find that the model first learns set obeying the easier rule, and then identifies the language as its subset ($ 5.3
100
B2 compledee
LSTM
Lincer
Manbe
XC.T7M
Dyck
C5 byct
56
87 4V
Dysk
<5 C5
Figure 1: Rule extrapolation summary for all models and languages (Tab. []: The Transformer is
the best on context-free and context-sensitive languages, whereas the LSTM and Mamba excel on regular languages. We also plot chance-level performance as gray rectangles. Mean accuracies and standard deviations (averaged over 5 seeds)
Language
Category
Rule 1
Rule 2
L1 {ba)
regular
#a even
starts with b I's before a's a's before b's paired and nested ()
L2 2m2
regular
#a even
L3 {a"b"}
context-free context-free
#a #b
L4 Dyck
paired and nested []
L3 (a"
context-sensitive
#a #b- #c paired
a's before 6's before c's paired
L6 CS Dyck
context-sensitive
Table 1: Formal languages used in our paper: The languages are categorized according to the
Chomsky hierarchy, and they can be considered as the intersection of two rules: (R1) and (R2)

---

2 Background and related work
2.1 Formal languages
Formal languages are linguistic constructions that simplify the study of natural languages. Their advantage is their well-defined set of symbols and rules. Although they fall short of capturing the nuances and irregularities of human languages, they are very powerful with immense practical relevance-e.g., programming languages are formal languages.
Formal languages consist of words with symbols coming from possibly infinite alphabet. Chom- sky [956]] has categorized formal languages into four types with increasing complexity: regular, context-free, sontixt-eensitive, and recursively enumerable languages. Regular languages have rules that can be expressed via regular expressions, c.g., L1 = {ba a contains even number of a a's} and L2 = 2 n > 0}. Context-free grammars have rules that do not depend on the context- programming languages such as C or Python belong to this category, e.g., an if-else block in the programming language C always has the same structure. For demon- stration purposes, we will use two simpler languages: L3 {a"D" (sequences of nested parentheses and brackets]. Context-sensilive grammars have rules that de- pend on the position in the sequence-we we will use the standard example of Lş = {a"b"c":n > 0} and Lg = (sequences of paired, but not necessarily nested parentheses and brackets). We omitted the recursively enumerable grammars similar to Deletang et al. [2022]. as they require an infinite tape to simulate, which is impossible.
> 0}, L4 =
2.2 Out-of-distribution (OOD) (oo))generllizationn
In modern deep learning theory, the test loss distinguishes the performance of models with low training loss by evaluating the model unseen data sampled from the same distribution ei. Li.d.) as the data it was trained on. When the test loss is (near- )minimal, the model has statistical generalization ability. Therefore several studies focused on establishing bounds the generalization gap [Vapnik and Chervonenkis 1971 Dziugaite and Roy, 2017 Pérez-Ortie et al., 2021]. Along with the question of whether the test loss is sufficienlly low, another one arose: does the test loss have a unique minimum? Identifiability is a property of a family of statistical models, concerning the uniqueness of the data generator model recovered from the observed data. In machine learning, identifiability implies the uniqueness of the test loss' minimum, and the model it corresponds to, which is desirable since it enables us to interpret the model and reason about its properties.
Theoretical tools such as statistical generalization or identifiability are mostly concerned about the i..dd scenario, i.e., when the training and test data come from the same distribution. However, this is an unrealistic assumption for language models (LMs), especially when pretrained models are used for various downstream tasks. Despite the clear OOD nature of these tasks, OOD generalization of these models is not understood theoretically. Recently, several works addressed a special type of OOD generalization called compositional generalization in vision models (Schott et al.] 1021
Wiedemer et al.) 2023b]ur Brady et al.) 2023 Yang et al.] 2023 Lachapelle et al. [023]] however. such studies are only started emerging for natural language [Ahuja and Mansouri 2024, Han and
Pado 2024 Ramesh et al. 2024| Lake and Baroni 2023 Nogueira et al. 2021 Dziri et al. 2023
Saparov et al. [023]] Deletang et al. [2022] and Ruoss et al. [2023] conducted a similar experimental investigation to ours, the tasks they evaluate on are also derived from formal language recognition
and thus grouped according to the Chomsky hierarchy, but they focus on length generalization.
Reizinger et al. [2024] show that despite any explicit inductive bias regularization, Transformers can exhibit muuch-better-than-chame
extrapolation performance on some synthetic grammars. How- ever, it is unclear whether this behavior is specific to the Transformer and/or the formal language. Furthermore, there are some tasks such as addition and parity that are known to be very hard (or even impossible) to solve by Transformers, at least without tricks [Zhou et al. 2023). Inspired by these works, our paper investigates the role of architecture in different formal languages.
Rule extrapolation. To understand the OOD behavior in |AR LMs] we study a particular notion of OOD generalization, which we term rule extrapolation. Rule extrapolation is a subclass of compositional generalization, for formal languages are defined by composing multiple rules. When assessing rule extrapolation, the model is pre-trained on formal language data, i.e., the support is the intersection of all language rules. Then, OOD data is presented, where subset of rules violated, thus having zero probability over the training distribution. If the completed OOD prompts satisfy the not violated rules, we say the model extrapolates the rules. For example, the a language is the intersection of two rules: (R1) the number of e's equals the number of b's and (R2) a's precede b's. The prompt bbaab cannot be completed to obey the second rule. In this case, rule extrapolation means that the completed prompt satisfies the first rule (c.g.. bbaaba).
3

---

2.3 Inductive biases in sequence models
Several deep learning architectures, such CNNs or GNNs, were designed to capture specific structural data properties. Such inductive biases in sequence models remain to be understood (Reizinger al. 2024]. McCoy et al.. 2020 and Murty et al. 2023 studied whether different architectures on language processing tasks have an inductive bias towards hierarchical structure. [Murty et al.) 2023) showed that with sufficient training. the transformer architecture can represent
hierarchical sentence structure and use this structure to generalize correctly, Several works establish
forms of simplicity bias [Valle-Pérez al.) 2019 Dingle et al.) 2018 Mingard et al. 2020). Goldblum et al. 2023] demonstrate that (even randomly initialized) language models are biased towards low
algorithmic complexity. WWiis al. [202 developed a formal programming language called RASP
to model the inner workings of the Transformer, whereas Zhou et al. (2023) defined subset, called
RASP-L, and proved length generalization in Transformer, emphasizing a simplicity bias in terms of
RASP-L code length. Chen et al. (2024) attribute the development of grammatical capabilities to Syntactic Attention Structure (SAS), wherein specific Transformer heads tend to focus on specific syntactic relations. These approaches leverage the tools of theoretical computer science to reason about the success of Transformers, hinting at the role of a structural inductive bias. For example, in-context learning (ICL) performance depends on the ordering of layers in the Transformer (Press) ctt al. 2020], and also the structure of the training data [Chan et al., 2022]. LM inductive biases have also been studied from mechanistic interpretability perspective. Most notably, OOsson et al. [2022] propose that ICL is due to induction heads (a type of specialised attention heads). Mechanistic interpretability approaches can also identify and disable the computational circuits responsible for bad behaviors [Li et al.. 2024] and locate ones that capture factual knowledge [Meng et al.) [023]. These works constitute important progress; though take step back to ask: is the good performance attributable to the Transformer? Are (at least some of) these emergent capabilities present in simpler models such linear models RNNs?
3
Experimental setup
3.1 Architectures
To study when rule extrapolation emerges, we compare five architectures: linear models, LSTMs [Hochreiter and Schmidhuber 1997]. Transformers (Vaswani et al. 2023), and State Space Models (SSMs) (focusing on Mamba Gu and Dao 2023]), and the recently introduced xLSTM [Beck] et al. 2024). The Transformer (Vaswani et al. [202]] caused a breakthrough in Natural Language mechanism, allowing capture global depen- dencies efficiently in both directions, unlike the standard LSTM. Adapted from dynamical systems, SSMs have recently entered language modeling, and became increasingly popular, such this work's focus, Mamba [Gu and Dao 2023]. In this architecture, the attention mechanism (where every token must "attend" to every other token) is replaced by a single SSM block, allowing the model to selectively focus on relevant information. The on-par performance of the Transformer and the SSM along with the removal of the attention block raises the question of whether the SSM also show rule extrapolation abilities. Recently, Beck et al. (2024) proposed an extension of the LSTM, which includes -aluux memory cells, new gating and memory mixing mechanisms, and several computational improvements. Training details, data set sizes, and model parameters are in Appx. B
Processing (NLP) by introducing the (self-)attente
3.2 Datasets
Our data sets follow the hierarchy of [Chomsky 1956]. The advantage of the classification is that the categories exhibit fundamental differences. However, this hierarchy is based on computational linguistics concepts. Therefore, there might be connection between the language's complexity in the Chomsky hierarchy and what a neural network finds difficult to learn. Each language we study obeys rules, and the OOD prompts violate the corresponding R2, but the prompt can still be completed to satisfy the other. Following (RI) and/or (R2) provide different information: following (R1) means the LM still adheres to rule even when the other is violated (in the whole sequence), whereas adhering to (R2) on the completion shows that the LM still tries to satisfy that.
The used formal languages and their categorization and rules are included in Tab. [ We define two rules for each language to keep the results comparable; however, we acknowledge that these can lead to rules of different complexity (cf. the chance levels for L3 and L5 in Tabs. [4...]]a and (6), and also that the rules can potentially be defined in multiple equivalent ways.
Regular grammars. Regarding the hierarchy, the two simplest data sets are regular languages
L = {ba contains even number of aass} and L2 = (b*a2m language Ln are: (R1) there are even number of as the sequence; and (R2) the sequence starts with a b. For L1, the OOD prompts consist of prompts that violate (R2). i.c. start with an a, but all these
m > 0}. The rules of the
4

---

prompts can be completed to satisfy (RI). For language L2, the rules are: (RI) there are even number of as in the sequence; and (R2) bs precede as. The OOD prompts for L2 violate (R2). They start with a single then block of bs and possibly block of as.
Context-free grammars. We W implemented two context-free grammars La and La: L3 = {a"t" 03, i.e., (R1) the number of as and bs match; and (R2) as precede bs. For La, OOD prompts violate (R2), i... the prompts include 6 tokens followed by a tokens.
Our fourth formal language is
bracketing (Dyck-) language, i.c., L1
(sequences of nested and paired parentheses and brackets), e.g. "( "IK (I)" The rules of the language are: (R1) brackets are nested and paired; and (R2) parentheses are nested and paired. Paired means that every opening
has a closing pair; nested means that between an opening and closing bracket/parennthess,, all other tokens must be paired contrast this with Lg. For Lg, ID prompts begin with "((" and OOD prompts start with ")[" both are followed by a sequence where the parentheses and the square brackets are matched.
We implemented two context-sensitive grammars Ls and Le- Ls (a" n > 03. Though it seems very similar to L3, its grammar rules make it context- i.e., the tokens generated depend on multiple tokens. The grammar rules can be summarized as: (R1) the number of as, bs, and es are the same; (R2) as precede bs and bs precede cs; and The OOD prompts are sequences which violate (R2) All these prompts can still be completed to obey (R1). T.g is context-sensistve Dyck-language, i.e., La = [sequences of paired, but not necessarily nested parentheses and brackets), e.g. "( "(()) The rules of the language are: (R1) brackets are paired; and (R2) parentheses are paired. Akin to I.,, for Lg ID prompts begin with "((" and OOD prompts start with ")(": both are followed by a sequence where the parentheses and the square brackets are matched.
Context-sensitive grammars.
3.3 Metrics.
We monitor training and test loss. We evaluate the accuracy of both rules (R1/R2) separately and simultaneously both for in-distribution samples, and also for OOD prompts. As OOD prompts are designed that (R2) cannot be satisfied, we evaluate its accuracy in the most lenient way. That is, we either calculate it on the completion or, for the Dyck languages, on the part after the closing parenthesis ")". An example for the L3 OOD prompt abbb is as follows: the completion abbbaa considered correct for (R2), but abbbabaa is not, as has an after b in the completionn Our evaluation is restricted to prompt completions with an EOS token. We also monitor the accuracy of the next token prediction via greedy decoding (i.e., using the token with the largest probability).
Our results report the minimum of the test loss to measure whether the models are in the saturation regime [Reizinger et al. 2024). We select the largest values for the rule accuracies. We choose this evaluation as small variations in the test loss could lead to large deviations (as predicted by Liu et al. (2023). We also report chance level accuracies as a baseline, quantifying how complex a given rule is. Chance level accuracy in each case refers to the performance of model that always predicts each token (exeluding the Sttart-f--squeece (oken) as the next token with equal probability We report means and standard deviations across 5 seeds. Similar to (Rajamanoharan et al., [024]] we provide a represeeeeeeeeev human baseline based on a small pilot study, where participants have seen three examples for L,, Lag then were asked to complete five OOD sequences for each (Appx. [B6)). We corrected for invalid answers and emphasize that we only aim to provide a sense of how humans measure against neural networks, without reaching any statistical conclusions.
4 Results
Regular grammars. Perhaps surprisingly, modern architectures perform the worst on regular languages L1 (Tab. (2) and L2 (Tab. 3 both Mamba and the Transformer are worse in- and out-of- distribution than the LSTM the xLSTM only matches the LSTM in OOD performance on (RI). Furthermore, the Transformer's 's accuracies are below chance level even for in-distribution, despite having approximately the same test loss as the LSTT and Mamba. The Linear model seemingly manages to obey perfectly (R2) in-distribution on Lz, which happens because this model only predicts EOS on test prompts, and the ID test prompt already satisfies (R2). In the other categories, Linear is at or below chance-level. In our small pilot study, humans performed akin to Mamba on Lı (Tab. [4). Zhou et al. (2023) observed that Transformers struggle with addition or parity calculation, which might explain the Transformer's low performance on regular languages, as both L1, L2 require calculating the parity of tokens.
"The code for calculating chance levels is in Laannce_Leve___cccuue ipynb
5

---

Model
Test loss
ID R1
OOD R1
OOD R2 completion
Chance
N/A
0,500
0.500
0.333
Linear
4.
0,500 000
0,500 000
0,000
LSTM
0.276=00.007
0.926 4.110
0.862
0.947 =0mm
Mamba
0.274=0.000
0.634 130
0.591 o 063
0.597 248
Transformer
0.277 00000
0.393 40.400
0.445 t:o 461
0.468
xLSTM
0.284=o.oom
0.740
0.679 o.o. 183
0.701+0.300
Table 2: Test loss and rule-following accuracies for the regular language I, {box): the LSTM can extrapolate (RI) the best. The column R2 is left out as it is satisfied by design.
Model
Test loss
ID R1
ID R2
OOD R1
OOD R2 completion
Chance
N/A
0,473
0.250
0.500
0.750
Linear
1.927+2.637
0,422 +0.034
1.000
+o. +0.000
0.513+o.mm
0.000+o.com
LSTM
0,037+0.00 +0.000
1.000
9.000
1.000
1.000
-0.000
0,.00++..om .000
Mamba
0,038
0,90 +0.00
1.000
-8000
0.959 +000%
0.073 +..22
Transformer
0.039
273920.omm
18158 20.357
o.o 405
0.067
2.0223
0.000 2:0 .000
xLSTM
0.037
0.833 23.3:004000
0.833 408
1.000 200000
0.000 .000
Table 3:
Test loss and rule-following accuracies for the regular language L2 2m, the LSTM and the XLSTM can extrapolate (R1) the best, closely followed by Mamba
Context-free grammars. On the context- free grammars L3, Lg, the conclusion is different. On La (Tab. 4), although all four models achieve perfect accuracy on (R2) both in- and and all models except the Linear, (near) perfectly obey (R1) in-distribution, the Transformer ex- trapolates (R1) to the largest extent (66%), followed by the LSTM (38%) and Mamba (30%). The seemingly perfect (R2) ID and OOD extrapolation for the Linear model is, again, due to EOS token generation. On the Dyck language L4 (Tab. 5). the Transformer has the best extrapolation performance, and Mamba is better than the LSTM. On L3. the human participants in our small study had performed better on following (R2) on the completion than extrapolating (RI); however, the Transformer was better than humans in extrapolating both (R1) and (R2).
Model
Test loss
ID R1
ID R2
OOD R1
OOD R2 completion
Chance
N/A
0.105
0.356
0.154
0.445
Linear
2.553
0.200220.00
1 1.000
1.0 o.0
0.275 oo0
1 1.0002..com 0o00
LSTM
0.019 2019220.om
1.000 auns
1.000
evato
0.376 20a
1.000
Mamba
0.019 2019=0..om .000
1.000
9.000
1.000
0.296 .44
1.000:0.0
Transformer
0.022 .002
1.000
200000
1.000 E-800
0.657 #0362
1.000=0..0
XLSTM
0.019=0.000
1.000 =
1.000
0.438 2522
1.000 000
Table 4: Test loss and rule-following accuracies for the context-free language L3 = {aa 6tthb b":: the Transformer can extrapolate (R1) the best.
Context-sensitive grammars. The grammar Ls (Tab. 6 is similar to L3. i.e., the Transformer performs best. Intuitively, the sequences in the form of [a"b") } and (a"b"<" cn) are rather similar, despite the latter being context-sensitive in Chomsky's 's hierarchy. Rule extraplation accuracies for (R1) in Lg are lower than for Ly, which can be attributed to the higher complexity of (R1) in the context-sensitive grammar (cf. chance levels in Tabs. 4 and (6) For the cntext-sensitive Dyck language LG (Tab. 7. the Transformer and LSTM perform similarly on both OOD (R1) and (R2).
Results summary. We conclude that on different grammars, different architectures perform best (Fig. D Although the Transformer has a consistently good performance on the investigated context- free and -sensitive grammars, LSTM and Mamba are better choices for the studied regular grammars. We hypothesize that it happens because these languages require calculating parity, in which the Transformer struggles [Zhou et al.) [2023). The xLSTM generally lies somewhere between the LSTM and the Transformer. The Linear model has very limited capabilities for modeling formal grammars as it cannot even minimize the test loss. In our small pilot study on L,, La, humans found the tasks difficult: they performed better than chance, though the LSTM performed better on L1, and the Transformer on L3 (Tab. 14) we emphasize that our human-machine comparison only provides intuition, rather than rigorous evaluation of human performance, which is left for future work.

---

Model
Test loss
ID R1
ID R2
OOD R1
OOD R2 completion
Chance
N/A
0.127
0.127
0.127
0.382
Linear
6,145+0.647
0.000
0,000 aco
0.000
1.000=
LSTM
0.266
+0.075
0.969 +0. a6o
0.543 28.282
1.000
Mamba
0.277
0.697 20.172..12
0.607 20. 140
0.64
0.886 1::00:22
Transformer
0.273=0.011
0.974
0.973 =
0.980 00000
1.000 10000:..00> :00000
xLSTM
0.273=0.013
0.706
0.663
0.689 1-6114
0.991 +.0015
Table 5: Test loss and rule-following accuracies for the context-free Dyck language Typ the Transformer can extrapolate (R1) the best.
Model
Test loss
ID R1
ID R2
OOD R1
OOD R2 completion
Chance
N/A
0.022
0.454
0.003
0.593
Linear
2.657 20..000 383
10.0020.000
0.000
1. 0.0
0.0001.o 000
0.000 .000
LSTM
0.01 720.000
1.000
1.000
0.068 g. 038
1.000.amm
Mamba
0,01 =0,000
1.000 9.000
1.000
8-800
0.099 .1.0
1.000
Transformer
0,024 .0o8
1.000 0.000
1.000
0-000
0.187 +000ss
1.000
XLSTM
0.017=0.00m 0.000
1.000 9.000
1.000
8,800
0.116+0.00 oos
1.000=a.00
Table 6: Test loss and rule-following accuracies for the context-sensitive language
Ls = (a"; the Transformer can extrapolate (R1) the best
Model
Test loss
ID R1 ID R2
OOD R1
OOD R2 completion
Chance
N/A
0.127
0.127
0.127
0.382
Linear
4.013
0.000
0.000 000
0.000 boa
1.000 .000
LSTM
0.645
0,981 +
0,956-ead
tast
1.000
0.894
Mamba
0.675++0.0
0.745 +0.070
0.807
+o. 185
0.684+a 119
0.810 0 212
Transformer
0.640go.a
1.000
1.000
0.980
Livees
0.973 Laos
XLSTM
0.671 20.021
0.791 179
0.765 185
0.767 110.15
0.715 520.121
Table 7: Test loss and rule-following accuracies for the context-sensitive Dyck language Lo: the Transformer and the LSTM can extrapolate the best
5 Normative theory of OOD prompt completion
The previous sections empirically assessed an example of rational OOD prompt completion: rule extrapolation. In this section, instead of asking what happens, we take step back to ask what should happen: how ideal model should learn and extrapolate rules. We propose non non-parametric prior and prediction scheme for OOD prompt completion, that can be seen as a generalization of Solomonoff induction [Solomonoti] 2001 Li and Vitányi 1997 to settings relevant for AR LMs. Although our algorithm, just like Solomonotf induction, is uncomputable, we argue that formalises rational approach capable of OOD extrapolation in AR sequence models. Rather than practical algorithm itself, it should be interpreted as guide towards building and assessing future practical models. Our conceptual approach is not without precedent: ideas from AIT have recently been popularized as "North Stars" for guiding practical implementations (Thiis 2024 Goldblum et al. 2023). and have been applied in practical algorithms [Grau-Moya al. 2002
We first introduce our approach on the high-level, via the following story.
A story of OOD prompt completion. Suppose that Bob has a Language Model Paata that autore- gressively generates M i.i.d. sequences of length m, {(11,j K2.j. ...2jj....ee ...j) 1M == (xT)) M Since the sequences are generated autoregressively. we may call (x=))
the ID prompts, and each m
element (Im.)) ) its ID completions. Suppose that Charlie, Bob's enemy, generates n nenehh sequence from the same LM, and intervenes (in the causal sense) on it, so that the resulting sequence (I1, 22, Fr 1) == x n-1 has zero probability under the LMM We call this the O0D prompt. Despite Pdata (I" (-1 = 0, the LM still defines the conditional probability of completing the OOD prompt J Charlie then asks an observer, Alice, to predict how Bob's LM will complete the OOD prompt J i.e., what v, will be. Fig. 2 shows the probabilistic assumptions of Alice: the completions generated independently, according to the same procedure (i.e., using the same LM). We use the conditional independence assumption In 1 M x n-1 in eq. (4 below.
7

---

Pdatn
ID
ID
OOD
OOD completion Za
prompt
completion (Xmm)
prompt (x
(ef )
1 M
Figure 2: Graphical model representing our approach for OOD prompt completion. Although Bob's LM Paama assigns zero probability to the OOD prompt, defines a conditional probability distribution for its completions. Our probabilistic model assumes that Bob's LM completes the ID and OOD prompt independently. according to the same procedure (e.g. the same LM architecture and parameters used for generating the completions). This is the same as assuming that the Markov factors marked in blue are the same, i.e. and the conditional independence OOD completion T ID prompt OOD prompt.
prrompt, Pdata) p pcooplletion (OOD prompt, Pdan),
In the rest of this section, we construct an algorithmic prior that formalizes these assumptions, and argue why it is a promising approach to study OOD compositional generalization theoretically.
5.1 The Solomonoff prior
The Solomonoff prior assigns a prior probability to individual data points based on some algorithmic notion of how difficult it is to generate that data point. It embodies Occam's 's razor and Epicure's principle, as simple data points have a larger probability, and every possible explanation included in the prior (see also Appx. C.2). For simplicity, we define the Solomonoff prior for discrete sample spaces, though similar arguments hold for the continuous case. To encourage readability, we define technical terms in Appx. C.2 and highlight them in blue here. Let us fix monotone universal Turing machine (UTM) Solomonoff's universal prior [Solomonofi] 2001 is defined over arbitrary-length sequences x1 (21,22......2 .NN
Ps (= Σ [p(p)p(<=)))
(1)
where we sum over all discrete lower semicomputable semimeasures pi (x4²) implementable on the UTM [Li and Vitányi 1997]. We will refer to the (x] as mixture components explanations of the data. The prior on weights (<p;) an arbitrary semimeasure i..., Vi : a(p,) > 0 and
Σ, ap.) < 1. Frequently, a(p;) is chosen as 2 k(e),, the prefix Kolmogorov complexity of pt in the UTM (see Defn. C.5 in Appx. C.2).
Predictive form. The above formulation of the Solomonoff prior has the predictive form Hutter 2005 Chapter 3.2.3], where a(p; 1NN N-1 is updated via Bayesian inference:
where ap, | 1 (p:))p:zz) N-11
Ps(EN| - Σ a(p: xx N..-11 (NN |x (=N~")),(EN
(2)
(x) (2 N -11
Convergence of predictions. Suppose that the true distribution of (II, J22 ...,,..,,,................. IN) ) is n. The Solomonoff prior (with any valid sequence of weights) satisfies [Hutter] 2005).
ps(xN -1) Not00, u(IN 1
with p-probability 1.
5.2 A predictive model for OOD prompt completion
Our goal is to define a similar prior, and predictive scheme that fits our scenario of AR next-token prediction, and where we can express the notion of completing an out-of-distribution prompt x; n-1 even when our prior assigns zero probability to the prompt.
The Solomonoff prior assigns nonzero prior mass to every possible prompt, i.e. there exist no OOD problems for the Solomonoff prior, as each possible test distribution is included in the prior as mixture component P:- However, by definition, the Solomonoff prior can only take in single sequence x². This means that it can only model pre-training and (OOD) testing together, since the pre-training and testing data need to be concatenated into the same sequence (Hutter] 2011]. Intuitively, more natural to separate those processes. To achieve this, we propose an adapted version of the Solomonoff prior, modifying it two ways, and justifying our approach below:
8

---

(i) We condition the prediction on pre-training dataset D of M independent and identically distributed (i.i.d)) sequences of finite length m. i... [m [=1 D is sampled from the
distribution Pasla (D) I1 M - Pain =ffg)) For simplicity, we assume that each
pre-training datapoint has equal length m.
(ii) Instead of modelling semimeasures as joints over sequences {(x1 )) we model semimea- sures as lists of conditionals, just as how AR LMS model probability distributions over {(T | #1 ") k= enumerating them with index = 1.,,..., denoting each semimea- sure as Pa to emphasize the lists of conditionals representation. That is, Pay -f and Ps] (D) mean (r = and Pa(D) I1,-1 2
æt.j "), respectively. Note that the pre-training distribution Pdata also belongs to the set of Paj- We define mixture over all lists of discrete lower semicomputable semimeasures P4] implementable on the UTM See Appx. [.I for details.
The motivation for modelling zi as a list of conditionals is because the mapping from lists of conditional factorizations to joint semimeasures consistent with them is a many-to-one mapping. because zero- zero-probaan prro-prbabbiltyy sequences have multiple factorizations (see Appx. C.1 for justification and more details on this notation). If the prompt x n-1 comes from distribution different from D ~ MM that assigns zero probability mass to zi n- the probability Pdataa ( | 2 1) is left undefined if only the joint probability Pasa (xf) is specified. This is not problem in the Solomonoff prior, it assigns nonzero probability mass to every (computable) sequence. But once we introduce the conditioning on D. this step becomes necessary. The above two modifications generalize the predictive form of the Solomonoff prior as follows (we color-code the equation denoting modification (i) in red and modification (ii) in green):
)) with [<p (D) = a(pp))Ps((2)
pR( x 10---_ :D:= a(pi) D)pp (xn,
(4)
Pana (D)
Interpreting PR- Starting from a prior weight a over all possible explanations Pa = {pr(
of ") the posterior probability of Pi given D is computed (eq. (4). right). The th step prediction by pt, conditioned on a possibly OOD test prompt, is then weighted by this posterior. It is not conditioned on the pre-training data D, and the posterior (p:) D) not conditioned on the test prompt xn-1_ This, as stated above, separates pre-training from testing, enabling us to define the completion of OOD test prompts. When 'D equals
is important that the prediction Pal (4r, ==)-))
"i "f-1.PR PR reduces to ps. and thus the posterior prediction converges according to eq. (3)
Choice of the weight prior a(p.).. For OOD test prompts, there are multiple explanations Pal consistent with D. Therefore, the behaviour of Pa, even when (D) tends to infinity, depends on the prior weight a (P.). This differs from the Solomonoff prior, which converges to the true posterior regardless of the weights (eq. 33) (Hutter 2005). Thus, must be chosen to allow the extrapolation of simple explanations consistent with the data. We define ap;; ) ;= 2 (P(),, penalising exponentially the length of the shortest program (implemented on the fixed UTM) K ((pi)) that can approximate P:l (each conditional probability) for every prompt xT. This encodes Occam's 's razor into the prior, and is consistent with the optimal weights of the Solomonoff prior (Hutter] 2005
5.3 Towards explaining training dynamics and rule extrapolation
Here, we argue informally that our normative algorithm provides a notion of a rational pre-training process, and thus helps explain the training dynamics of practical LMs, and is also capable of rule extrapolation. We support our arguments by showing the role of simplicity bias (towards low Kolmogorov complexity) in the dynamics of learning the b² language with Transformers.
Explaining training dynamics. We analize the dynamics of learning rule extrapolation. We report results on the Transformer (training dynamics of Mamba and the LSTM are in Appx.[A. trained on the a=6" language- where high rule extrapolation ability is achieved. Fig. 3 shows that first, the model learns the sequences obeying (R2), then it learns the language (R1) (R2) as its subset.
We argue that the order in which rules are learnt is governed by the relative simplicity of the rules, quantified by Kolmogorov complexity. Given formal language with rules (R1) and (R2), let pI, P2 and P1.2 be distributions defined by LMs that generate sequences that satisfy (R1), (R2) and (R1) n (R2), respectively. If, e.g., K(p2) & K (p),2), our normative algorithm will first learn (R2), and then learn the (R1) n (R2) as its subset. In the a" language, (R2) (a's before b's), is, on average, simpler to generate than (R1) (#a=tth) and (R1) n (R2). Therefore, we expect our normative algorithm to first learn (R2), and then leam (R1) ( (R2) its subset. Remarkably, our Transformer employs the same

---

Intianzatioo
During Trairing
After Training
(92)
2od 6o1
Banabuuinn of 1ow.oooo
Onl Rt
and
ND 1221
y R2
(92)
Not RL. not
NO
2000
4000
8000
10600
Epochs
Figure 3: Training dynamics of rule learning for Transformer trained the a"b" language: we color-code the log probability of all sequences of length 8 consisting of a's and b's and ending with EOS initialization (left leff), during (left middle) and after training (left right). The sequences separated according to which rule they obey. While at initialization, the probabilities are distributed roughly evenly, during training the model starts to assign higher probabilities (R2). After training the most likely sequences are the ones in (RI) n (R2), the others are negligible. The same trend can be seen on the right, where the normalized sum of the probabilities of the four categories (satisfying (R1) 1) and (R2), only (R1), only (R2) and neither) is plotted during training.
sequences satisfying
strategy ( Fig. 3)
verifying the presence of simplicity bias. This result is matches past observations that Transformers are biased towards low Kolmogorov complexity (Goldblum et al., 2023).
Towards explaining rule extrapolation. Our normative algorithm has been designed complete OOD prompt based on the simplest explanations consistent with the pre-training data. On the high level, this approach is consistent with rule extrapolation. We conjecture that approximating normative algorithm similarly to the approach of of[[ruMoyya et al. (2024), will result in models with superior rule extrapolation properties. We leave this promising direction future work.
Discussion
Conclusion. We argue that focusing on rule extrapolation and formal languages gives us sound (theoretical) tools to analyze and better understand ouittf-diitribuution behaviour in language models, such as the role different architectures. Our empirical findings emphasize that no single universal architecture exists for autoregressive sequence modeling. Though Transformers fare very well in most scenarios we investigated, they struggled on regular languages. Therefore, we argue that the architecture's 's inductive bias should be considered when selecting models since the architecture that performs the best depends on the nature of the task. Furthermore, we analyse the training process enabling rule extrapolation, rules, then learns the language (intersection of all rules) as its subset. Beyond advancing our empirical understanding, we also proposed a normative theory of OOD prompt completion. Our normative algorithm predicts the next token based on simple explanations consistent with the data, and allows to explain and contextualise some of our empirical observations.
find that the model first identifies the whole obeying of the
Impact. Rule extrapolation is special case of compositional generalization in language models. While other OOD generalisation types were examined previously, this is the first work studying rule extrapolation. This novel concept has the potential impact LLM research both conceptual and practical levels. General compositional generalization notions examine whether from learning multi- ple concepts/rules separately, the model can understand the composition of the concepts/intersection of the rules. However, in rule extrapolation, we measure the reverse direction: from the composi- tion/intersection, can the model identify the concepts/rules separately? Importantly, this direction less straightforward. Rule extrapolation allows for easy study of compositional generalisation ability on variety of datasets, such as formal or programming languages. Therefore rule extrapolation has the potential to become an established benchmark task for evaluating current and future LM architectures.
Limitations. We defined and empirically evaluated rule extrapolation in simple formal languages, where analysis is tractable and demonstrates that models can "go beyond" their training data. We acknowledge that our data sets are far from natural language where rule extrapolation may be difficult to demonstrate. Studying formal languages may still have practical relevance, g. for programming languages or formal mathematics. Even though we considered different hyperparameter setups presented in the appendix, we have not performed exhaustive ablations over the hyperparameters or analysis of architectures. Furthermore, model variants, like different attention or positional encoding, may impact our findings.
10

---

Acknowledgements
The authors would like to thank Gergely Flamich for several inspiring discussions on Solomonoff induction, Bence Nyéki for insights on practical aspects of natural language processing and Gail Weiss for her insights on PCFGs. This work was supported by a Turing AI World-Leading Researcher Fellowship G G111021. Patrik Reizinger acknowledges his membership in the European Laboratory for Learning and Intelligent Systems (ELLIS) PhD program and thanks the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for its support. This work was supported by the German Federal Ministry of Education and Research (BMBF): Tübingen AI Center, FKZ: 011S18039A, Wieland Brendel acknowledges financial support via an Emmy Noether Grant funded by the German Research Foundation (DFG) under grant no. BR 6382/1-1 and via the Open Philantropy Foundation funded by the Good Ventures Foundation. Wieland Brendel is member of the Machine Learning Cluster of Excellence, EXC number 2064/1 - Project number 390727645. This research utilized compute resources at the Tübingen Machine Learning Cloud, DFG FKZ INST 37/1057-1 FUGG.
References
K. Ahuja and A. Mansouri. On Provable Length and Compositional Generalization, Feb. 2024. URL www.:org/aago htrg/abs/4422..o 04875 arXiv:2402.04875 [cs, stat].
0487
M. Beck, K. Pöppel, M. Spanring, A. Auer, O. Prudnikova, M. Kopp. G. Klambauer, Brandstetter, and S. Hochreiter. xLSTM: Extended Long Short-Term Memory, May 2024. URL http://
arxiv. arxiv.org/aie
04517 MtXiv:2405.04511 [cs, stat]. 16
Brady, R. Zimmermmnn, Y. Sharma, B. Schölkopf, von Küggelgen, and W. Brendel. Provably Learning Object-Centric Representations, May 2023. URL httt:://axxx: org/ 2235 14229 arXiv:2305. 12223055..2222 14229 [cs]. 3
S. Chan, A. Santoro. A. Lampinen, J. Wang. A. Singh. P. Richemond, J. McClelland, and F. Hill. Data distributional properties drive emergent in-context learning in transformers. Advances in Neural Information Processing Systems, 1888-1 2022.
A. Chen, R. Shwartz-Ziv, K. Cho, M. L. Leavitt, and N. Saphra. Sudden drops in the loss: Syntax acquisition, phase transitions, and simplicity bias in mims, 2024. 4
N. Chomsky, Three models for the description of language. IRE Transactions on Information Theory, 2-3):1,3-12,, 1956. doi: 10.1109/TIT. 195.. 1056813.
G. Deletang, A. Ruoss, J. Grau-Moya, T. Genewein, L. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg, Veness, and A. Ortega. Neural Networks and the Chomsky Hierarchy, Sept. 2022. net mett//orrum//d--Debikeeeee.
URL httpp::/
K. Dingle, C. Q. Camargo, and A. A. Louis. Input-output maps are strongly biased towards sim- ple outputs. Nature Communications, 9(1):761, Feb. 2018. ISSN 2041 doi: 10. 1038/ 941467-018-031011-
URL https:: //www natura. wttteeetcco.ce...//ee/eeettaeeee Number: 1 Publisher: Nature Publishing Group.
N. Dziri, X. Lu, M. Sclar, X. L. Li, L. Jiang, B. Y. Lin, P. West, C. Bhagavatula, R. L. Bras, J. D. Hwang, S. Sanyal, S. Welleck, X. Ren, A. Ettinger, Z. Harchaoui, and Y. Choi. Faith and fate: Limits of transformers on compositionality, 2023.
G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, 2017. 3
L. Falcon. Pytorch lightning: Accelerated research from prototypes to production. https
//ithub. com/ Py haapattiiinnpttrtoccmooo wttpg//ooooooooootoiinnnn 2019. T6
M. Goldblum, M. Finzi, K. Rowan, and A. G. Wilson. The no free lunch theorem, kolmogorov complexity, and the role of inductive biases in machine learning, 2023. 4 10
J. Grau-Moya, T. Genewein, M. Hutter, L. Orseau, G. Delétang, E. Catt, A. Ruoss, L. K. Wenliang,
C. Mattern, M. Aitchison, and J. Veness. Learning Universal Predictors, Jan. 2024. http
// //arxiv.. org/ abs abs//401.. 14953 arXiv:2401.14953 [cs]. 7 10 22
11

---

A. Gu and T. Dao. Mamba: Linear- Sequence Modeling with Selective State Spaces, Dec. 2023. URL http:://aarati wttpo///g/....//////// arXiv:2312.00752 [cs].
S. Han and S. Padó. Towards Understanding the Relationship between In-context Learning and Compositional Generalization, Mar. 2024. URL htttp://aaxxi..org/aaa////////// arXiv:2403. 1834 [cs]. 13
S. Hochreiter and J. Schmidhuber. Long short-term memory, Neural computation, 98):17355-170,, 1997.
M. Hutter. Universal Artificial Intelligence. Texts in Theoretical Computer Science, An EATCS Series. Springer, Berlin and Heidelberg. 2005. ISBN 578-3-540--221395. doi: 10.1007/b138233.
21
M. Hutter. Universal learning theory. 02 2011. doi: 10.1007/978---387--00111 8_6666666886.66
21
Lachapelle, D. Mahajan, Mitliagkas, and Lacoste-Julien. Additive Decoders for Latent Variables Identification and Cartesian-Product Extrapolation, July 2023. URLphtpp: //arxiv
org/abs/2307 02598, arXiv:2307.02599 [cs, stat].
B. M. Lake and M. Baroni. Human-like systematic generalization through a meta-learning neural network. Nature, 623(7985):115-121 Nov. 2023, ISSN 1476-4687. doi: 10310
15188-023-06668-3 URL hhttps://wwt http:////wwwwanuuutee.cr///rrtta http://wwwww.ooooccccc...///////
Publisher: Nature Publishing Group.
A. LeGuet. Mamba repository. URL httpp////ggthuub..mmmmaa/aiaaai
py
M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, 1997. Utth:tp::///att
google. www.coooooocceecccc 711-111001111 21 22
M. Li, X. Davies, and M. Nadeau. Circuit breaking: Removing model behaviors with targeted ablation, 2024. 4
H. Liu, M. Xie, Li, and Ma. Same pre-training loss, better downstream: Implicit bias matters for language models. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages htttps://proceedingg. mlr ppress/v22//ini
PMLR, 23-29 Jul 2023. URL
html
5
R. T. McCoy, R. Frank, and T. Linzen. Does syntax need to grow on trees? sources of hierarchical inductive bias in sequence-to-sequeeee networks. Transactions of the Associ- ation for Computational Linguistics, 8: 8:125-140, 2020. doi: 10.1162/tacl_a a a_00304. URL
wwwp://oooooo./000...... tacl
K. Meng, D. Bau, A. Andonian, and Y. Belinkov. Locating and editing factual associations in gpt, 2023. 4
C. Mingard, Valle-Pérez, Skalse, and A. Louis. SGD Bayesian sampler? Well, almost, Oct. 2020. http:://a/// wwwp:iivwwrgggb//////eoosbb abspg//bb/200055 15191 arXiv:2006. 15191 [cs, stat].
S. Murty, P. Sharma, J. Andreas, and C. Manning. Grokking of hierarchical structure in vanilla transformers. In A. Rogers, Boyd-Graber, and N. Okazaki, editors, Proceedings of the 61s Annual Meeting of the Association for Computational Linguisties (Volume 2: Short Papers). pages 439-448, Toronto, Canada, July 2023, Association for Computational Linguistics. doi: 10. 10.18653/v1/2033. acl:223..cl330. acl-short.38.
acl short 38
R. Nogueira, Z. Jiang, and Lin. Investigating the limitations of transformers with simple arithmetic tasks, 2021. 3
C. Olsson, N. Elhage, Nanda, Joseph, N. DasSarma, T. Henighan, B. Mann, A. Askell, Bai, A. Chen, T. Conerly, D. Drain, D. Ganguli, Z. Hatfield-Dodds, D. Hernandez, S. Johnston, A. Jones, Kernion, I.. Lovitt, K. Ndousse, D. Amodei, T. Brown, Clark, J. Kaplan, S. McCandlish, and
C. Olah. In-context learning and induction heads, 2022.
12

---

A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin. N. Gimelshein, L. Antiga, A. Desmaison,
Köpf, E. Yang. Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, I.. Fang. J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library, 2019. T6
O. Press, N. A. Smith, and O. Levy. Improving Transformer Models by Reordering their Sublayers. In D. Jurafsky, J. Chai, N. Schluter, and J. Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2996-3005, Online, July 2020. Association for Computational Linguistics. doi: 10. 10.18655/w1/2002.callmmmii 270. URRLhttppe
//aclanthology.org www.oor...........oo 2020 acl-main. attp:/222...ccmmiaaaa...
270
M. Pérez-Ortiz, O. Rivasplata, J. Shawe-Taylor, and C. Szepesvári. Tighter risk certificates for neural networks, 2021. 3
Rajamanoharan, A. Conmy, L. Smith, Lieberum, V. Varma, Kramár, R. Shah, and N. Nanda. Improving dictionary learning with gated sparse autoencoders, 2024. 5
R. Ramesh, E. S. Lubana, M. Khona, R. P. Dick, and H. Tanaka. Compositional Capabilities of Autoregressive Transformers: A Study on Synthetic, Interpretable Tasks, Feb. 2024. URL
2tt arXiv:2311.12997 [es].
P. Reizinger, S. Ujváry, A. Mészáros, A. Kerekes, W. Brendel, and F. Huszár. Llm non-identifiabiiity repository. URL
16
P. Reizinger, S. Ujváry, A. Mészáros, A. Kerekes, W. Brendel, and F. Huszár. Understanding 1ims requires more than statistical generalization, 2024.
A. Ruoss, G. Delétang, T. Genewein, J. Grau-Moya, R. Csordás, M. Bennani, S. Legg, and Veness. Randomized Positional Encodings Boost Length Generalization of Transformers, May 2023. URL
Sttt://arxivy org/ wwt.ooo//////aeeeeeoeee has//bbbb3305.../ 16843 arXiv:2305.1688 [cs, stat]. 3
A. Saparov, R. Y. Pang, V. Padmakumar, N. Joshi, S. M. Kazemi, N. Kim, and H. He. Testing the general deductive reasoning capacity of large language models using ood examples, 2023.
L. Schott, J. von Kügelgen, Träuble, P. Gehler, C. Russell, M. Bethge, Schölkopf, F. Locatello, and W. Brendel. Visual Representation Learning Does Not Generalize Strongly Within the Same Domain. arXiv:2107.08221 [cs], July 2021. /tttt:ttt///riiii www.awwwww.w.eeaeee.......o httggaab//110... 08221 2107.08221. 3
arXiv:
R. J. Solomonoff. A preliminary report on general theory of inductive inference. 2001. URL https://api. www.ssemmmammool..e.......
L. Theis. What makes an image realistic?, 2024.
A. M. Turing. On computable numbers, with an application to the Entscheidungsproblen. Pro- ceedings of the London Mathematical Society, 2(42):230-263 1936. URI. httt:://ww.....
helsinki. fi/u/ ht////ggonis///e http:/cc5///////// wwtpi/iiicc//OOO/o//nnoae http/////noooputaaaeembbrrrrrrre pd
22
G. Valle-Pérez, C. Q. Camargo, and A. A. Louis. Deep learning generalizes because the parameter- function map is biased towards simple functions, Apr. 2019. URL http:://axiiv www.axiii.rr.rreeooo abs/
1805. 08522
arXiv:1800 005522 [es, stat].
V. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264, 1971.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need, 2023. 4
G. Weiss, Y. Goldberg, and E. Yahav. Thinking Like Transformers, July 2021. URL http://arxx ht////bb/210000 06981 arXiv:2106.0998 [cs].
T. Wiedemer, J. Brady, A. Panfilov, A. Juhos, M. Bethge, and W. Brendel. Provable Compositional Generalization for Object-Centric Learning, Oct. 2023a. URL, http::t://aax...rr//p///
05327, arXiv:2310.05327 [cs]. g
13

---

T. Wiedemer, P. Mayilvahanan, M. Bethge, and W. Brendel. Compositional Generalization from First Principles. July 2023b. URL http:://rxii org/abs/2300/ 05596 arXiv:2307.05596
[es, stat]. 3
T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao,
S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush. Huggingface's 's transformers: State-of-the-ar
natural language processing, 2020. 16
T. Yang. Y. Wang, C. Lan, Y. Lu, and N. Zheng. Vector-based Representation is the Key: A Study on Disentanglement and Compositional Generalization, May 2023. URL http:://aaxii..rrrte wrw. /bag/ 2305. 18063 arXiv:2305. 18063 [es]. 3
H. Zhou, A. Bradley, E. Littwin N. Razin, O. Saremi, J. Susskind, S. Bengio, and P. Nakkiran. What Algorithms can Transformers Lear?? A Study in Length Generalization, Oct. 2023. URL http://aree org/ 2010 2310. 16028 arXiv:23 11122300.10088 [cs, stat].
14

---

A Further experimental results on training dynamics
Training dynamiss of the probabilities of the sequences
R1 and R2
Only R1
Only R2
280 400 603 0.0 5009
Figure 4: Training dynamics of the LSTM Training LSTM the a² language, the normalized probability of all sequences, grouped into the four categories (satisfying (R1) and (R2), only (R1), only (R2) and neither) of length 8 consisting of a's and b's and ending with EOS is plotted during training. The sequences are separated according to which rule they obey. At initialization, sequences obeying any of the rules have low probability. During training, the model first starts assigning higher probabilities to sequences satisfying (R2), but soon after, sequences in (R I) n (R2) dominate. After training the most likely sequences are the ones in (RI) (R2), the others are negligible.
Training dynamics of the probsbilitie of the sequences
VM
Sum of pmbobiiitee
R2 Net 13, not
0.-
Esochs
Figure 5: Training dynamies of Mamba Training a Mamba architecture on the a² language, the normalized probability of all sequences, grouped into the four categories (satisfying (R1) and (R2), only (RI), only (R2) and neither) length 8 consisting a's and b's and ending with EOS is plotted during training. The sequences
separated according which rule they obey. Intriguingly, at initialization, sequences obeying (R2) are assigned largest probability. During training, the model learns (RD) n (R2) consistently after 3000 epochs. After training the most likely sequences are the ones in (R1) O (R2), the others are negligible.
15

---

B Experimental details
B.1 Reproducibility and codebase.
We use PyTorch Paszke et al.
2019]. Py PyTorh Lightning Falcon 2019]. and HuggingFace
Transformers Wolf al. 2020 Our training pipeline builds |Reizinger et al.] and
use the Py implementation of Mamba from [LeGuet) and the code released by the authors
for the xLSTM (Beck al. 2024). Our code and experimental logs publicly available at
https://gtt wwwpehhww.....aaaeeeeeememm
B.2 Formal grammars
Training data. We generate data from the formal languages L1. L2, L3. L4 and Ls described in $3.2 up to length excluding the SOS and LOS] tokens, i.e., those two tokens add two to the maximal length. The SOS (0), EOS (I), and padding (2) tokens always represented by these numbers. When the grammaa consists letters, their representations are a (3). b (4) and c (5), and when the language is the nested brackets and parentheses the tokens are the "(" (3), ' (4), II (5) and
I (6).
We used different data sizes for the different languages. This is explained by the highly different size of all possible sequences that obey all rules of any language. For the languages, I,, L2 the training set consists of 15000 samples (as these languages have rules satisfied by many sequences), and for L4. 512 samples. For L3 and La. the corresponding data sets include all unique sequences up length 256, which is 128 for L3 and 85 for Ls, respectively.
Test prompts. We define our test prompts as all possible sequences length (prepended with SOS for L1 and L3. and all possible sequences of length 5 (prepended Sith[SOOS for Lş = {a" 0}- we chose different lengths to have a comparable number of test samples, i.e., 2 and 53. respectively. We split these sets into in-distribution and OOD test prompts, based on whether they can be completed to obey the rules of the specific grammar.
For L2, first, we generate in-distribution test prompts of length 8-these can be completed according to the grammar rules by definition. From these, we create the (OD prompts by adding single a to the beginning of the sequences, For L4, we sample length-6 sequences obeying both rules, then the ID prompts are prepended with '( and the OOD prompts with ') Then the prompts are prepended with [SOS]
B.3 Model and training parameters
We observed that the Linear model constantly predicts PAD tokens, unless we ignore those by setting the ignore_ -nnoe__index-PAD in torch. mn. CrossEntropyLoss (). However, for comparison, when reporting the losses, we report the loss where we not set the ignore_inde parameter.
Table 8: General parameters
PARAMETER
VALUES
TRAINING MAXIMUM LENGTH
256
PROMPT PREDICTION CUTOFF LENGTH
300
BATCH SIZE
128
OPTIMIZER
ADAMW
LEARNING RATE SCHEDULER
INVERSE SQUARE ROOT
BATCH SIZE
128
LEARNING RATE
2e-3
NUMBER OF EPOCHS
50, 000
Table Linear model parameters
PARAMETER
VALUE
MODEL
LINEAR
DIMENSION OF THE MODEL
256
BIAS
TRUE
16

---

Table 10: LSTM parameters
PARAMETER
VALUE
MODEL
STANDARD LSTM
NUMBER OF LAYERS
EMBEDDING DIMENSION
16
HIDDEN DIMENSION
64
DROPOUT PROBABILITY
0.4
Table 11: Transformer parameters
PARAMETER
VALUE
MODEL
TRANSFORMER DECODER
NUMBER OF LAYERS
MODEL DIMENSION
10
NUMBER OF ATTENTION HEADS
FEEDFORWARD DIMENSION
1024
DROPOUT PROBABILITY
0.1
LAYER NORM
6e-3
ACTIVATION
RELU
Table 12: Mamba parameters
PARAMETER
VALUE
MODEL
MAMBA
NUMBER
10
MODEL DIMENSION
DIM OF CONV LAYER
DIM OF STATE SPACE
16
Table 13: xLSTM parameter
PARAMETER
VALUE
MODEL
XLSTM
NUMBER OF BLOCKS
6
EMBEDDING DIMENSIONS
64
MLSTM CONY ID KERNEL SIZE
4
MLSTM qkv PROJECTION BLOCK SIZE
MLSTM NUMBER OF HEADS
4
SLSTMM POSITION
1
SLSTM NUMBER OF HEADS
4
SLSTM CONVID KERNEL SIZE
SLSTM BIAS INITIALIZATION
DLOCN-DEPENDENT POWER LAW
SLSTM FEEDFORWARD PROJECTION FACTOR
1.3
SLSTM FEEDFORWARD ACTIVATION
GELU
B.4 Training dynamics plot generation details
Figure 3 was plotted on the a language with the Transformer on seed 63656. The left left was plotted the Lightning module's "self -llobalstte==",, left middle cosrenttrrretteeee 600" and left middle at nearly end of the training at "self wcurrent On the right,
Adopted
from
xlstm model
17

---

the sum of the probabilities was computed at every epoch divisible by 100. Similarly, Figure 4 was plotted on an with LSTM with seed 8556, and Figure ( a"b" with Mamba with seed 9 91686.
B.5 Additional experimental results
Greedy decoding vs sampling. Our initial results greedy decoding, but we conducted experi- ments to evaluate the sampling method for next token prediction. As shown in Fig. 6 we conclude that while the the Transformer is the best choice with greedy decoding, except for regular languages where the LSTM performs better (Fig. 6ab: the LSTM appears to excel when using sampling (Fig. (ob). These results also open up new interesting future directions, e.g., investigating the influence of different temperature values in the softmax.
Transformer
RI (8)
completion
50
50
<'i'c
Dyck
2m
676
Dyck
(a) Greedy decoding
100
completion (%)
75-
75
RI (3)
50
50
Mamba
25
Chance
3ox
2m
Dyck
Dyck
(b) Sampling decoding
Figure 6: Rule extrapolation summary for all models but the xLSTM and languages L1 - Li (Tab. with greedy (Fig, 6a) and sampling (Fig, 6bb next-token decoding
Fig. optimizer: adamw, 0.002
optimizer: sgd, 0.002
75
75-
(8)
(8))
25
25
a'IP'
a't"c"
optimizer: adamw, Ir: 0.02
optimizer: sgd. Ir: 0.02
1000
75
75-
(8)
(9S)
50-
50
25-
25-
6"
d'
6c
optimizer: adamw, Ir: 0. 0.0002
optimizer: sgd, Ir: 0.0002
75
75-
RI (9)
RI (8)
50
50-
Figure 7: Rule extrapolation performance for different optimizers and learning rates for all models except the xLSTM and languages L, Ls (Tab. I top row left is the same as Fig. 6a
Hyperparameter sensitivity. tested multiple hyperparameters, including three learning rates and two optimization algorithms, and plotted the results in Fig. 7 Though our hyperparameter search
18

---

is not exhaustive, we can state that when considering the best settings for each architecture, the LSTM consistently performs best on regular languages, while the Transformer excels on everything else.
Model size ablation. We tested varying size settings (different numbers layers and heads) for the Transformer architecture to determine whether increasing size can improve performance on regular languages. As shown in Fig. increasing the Transformer model size does not meaningfully improve performance on regular languages; the best values remain those originally used _almmlayerrss_ num num_heads = 5). For non-regular languages, the Transformer already outperformed the other architectures.
Heads: 10, #t Decoder layers:
Heads: 5, # Decoder layers: 13
100
100
75-
75-
(S)
(SS)
50-
50-
25-
25-
bx
<7
Dyek
<70'e*
Dyek
Heads: 10, # Decoder layers: 10
# Heads: 5, Decoder layers: 10
Transformer
Chanos-tevel
75-
75-
R1 (16)
60-
50-
bx
2m
Dyek
Dyck
Heads:
10, Decoder layers:
Heads:
# Decoder layers:
75
75-
(15)
(95)
25-
25-
5m
0710"
<76he*
Dyck
<"the*
Dyck
Figure 8: Rule extrapolation performance for differrnt number of attention heads and decoder layers in the Transformer for languages L1 L5 (Tab. 1
B.6 Human pilot study details
We conducted a small pilot study with humans using an online questionnaire (the study size was 14). We did not collect any personal information, only task-relevant responses.
The participants received the following instruction: This questionnaire asks you to perform a task of completing sequences based on examples for 2 cases. Each case follows the same layout:
Instructions.
first, show some example sequences
then on, we start sequences and ask you to finish them as you see fi
Then, on the three following pages of the questionnaire, they were presented the following: We generate sequences according some patterns. You see below examples, which considered completed (whitespace is only for visibility reasons):
(Examples came here in the questionnaire; detailed below]
Now you will see 5 incomplete messages. What you see are the first characters of sequences of unknown length. Your task finish them.
When writing down your answer:
DO NOT include the beginning of the sequence already provided, only your completion of it. The length of your answer is up to you, choose what you fit.
you think the sequence is already completed, leave the space for the completion empty
Case 1: regular grammar L1- The examples for the context-free grammar L1 were:
baba
baa
19

---

babbooa
The prompts the participants needed complete
aba
abba
abaaba
abab
aaba
Case 2: context-free grammar L3.
The examples for the context-free grammar La were:
aabb
anabbb
aaaaaabbbbbó
The prompts the participants needed to complete were:
baa
abaa
bba
baab
Results. We preprocessed the questionnaire results remove invalid responses (e.g., those with invalid characters, where assumed that did not explain the task well to the study subjects). We report the OOD (R1) and (R2) accuracies, the latter only on the completion Tab. 14
Language
OOD R1
OOD R2 completion
L [ba} 0.654
0.605
L3 a b"
0.415
0.623
Table 14: Human pilot study OOD accuracies: humans in our study performed better than chance, though they could not beat the LSTM on L1 and the Transformer L3
B.7 Computational requirements
Our models and data sets are small scale and were designed to fit into an NVIDIA GeForce RTX 2080 Ti with 11GB VRAM, this guided parameter choices (Appx. B.3). As we used SLURM and Condor managed clusters, our experiments were, due to GPU availability. in some cases, allocated on NVIDIA A100 GPUs Although in the paper we report statistics over seeds, in some cases, we ran more experiments during the lifetime of the project. For transparency, we report overall numbers, given in GPU hours for each synthetic grammar (Tab. [ The runtimes differed based on model architecture, data set size, and the stochasticity of the training (i.e., the use of early stopping)
L 1,455 GPU hours for 107 runs
L2 707 GPU hours for 59 runs
L3 301 GPU hours for 334 runs
L4 269 GPU hours for 208 runs
Ls 264.5 GPU hours for 65 runs,
which amounts to approximately 3,000 GPU hours and also includes the GPU hours required for creating the figures (Fig. 3)
To estimate the energy consumption, we take the maximum power consumption an NVIDIA A100 (PCle version), which is 250W This amounts approximately 750kWh, which is equivalent to the emission of 0.313 metric ton CO2, i.c., approximately 1290 kilometres driven by an average gasoline-powered passenger vehicle
https://www http:://www..viiia.am nvidia- a00---aaa-dddaaeee..... pdf
20

---

Details on the normative theory of OOD extrapolation
C.1 The set of joints and conditional factorizations
In this section, denote sets of probability distributions as D and use subscripts J and C to refer to joint and conditional distributions, respectively. Consider the set of joint probabilities on N -eegth sequences, where the p; are drawn from some set S. For example, S {p: is computable w.r.t. a UTM).
DJ,
Pt E S}
(5)
and the set of conditional factorizations consistent i.e., such conditionals that the joint equals the product the conditionals, with them
DC.N = (a of 1 consistent with elements of S}.
We claim that DJ,N C Dc,N. To see that Da.N S Dc.v, note that the list (pa )) uniquely determines P; 22. NN) as the product of its elements. To see that the sets are not equal, consider the following example.
Example.
Let X1 and X₂ be two binary random variables. Let us define probability mass
function (pmf) such that p(X, = 0) and p(X1 = 0, X₂ = 0) = p(X1 = X2 =
Now consider two sets of conditional pmfs 9ı and Q2. satisfying
ạ1 (X2 = x X1 = 1) = 92(X² = x X1 = 1) = p(X; = x X1 = 1) = p(X² = x),
(x = 1) = 42 42 (1 = 1) 11
but
@ (X2 0 0) 0) = and ga(X2 X1 = = 0.
Due the first equations, both qi and 92 are consistent with p, but they can differ the zero-probability prompt X, = 0.
Hence the set corresponding to Dc.N is larger, and the extra elements correspond the zero- probability sequences under each pt. These are precisely the prompts on which we assess rule extrapolation.
The lists of conditionals notation. In 5 we distinguish between the joint probability represen- tation Ps = {p (x+*)) and the lists of conditionals representation Pij- Let denote the mapping from lists of conditionals to the joint probabilities. Consider the set of pre-images of ps: under é. iee. o (ps). which has cardinality 1 (ps)). If this set has multiple elements, we can enumerate them as ( 1i=1
( with Paj.i = (x 1 )) where Pt.j is the j element of o- (px)))
In our predictive PR. we list the Pij. where the index i is understood to loop over all pre-images:
{pa)s {P 1/5 10- (o=]" kk. where the enumerations over (k.j) are combined into enumeration over in dovetail fashion. Index & loops over the joint probability distributions, and loops through each of their pre-images. Note that this is a different enumeration than the one in the Solomonoff prior ps. where only the joint probabilities are enumerated (here with index k).
C.2 Solomonoff Induction
This section has been adapted from Li and Vitányi [997]] Hutter (0055 and Hutter 2011
Epicure's principle states that if more than one theory is consistent with the observations, one should keep all the theories. The Solomonoff prior follows this principle in including all (lower semicomputable) semimeasures in the prior.
Occam's 's razor states to keep the simplest theory consistent with the observations. The Solomonoff prior follows this in assigning larger probabilities to algorithmically more complex strings.
Definition C.1 (Prefix code). A prefix code P is set of binary strings such that element is proper
prefix of another. It satisfies Kraft's inequality Σpep 2 2~1(p) < 1.
21

---

Turing machines. A Turing machine can be thought of as an idealised form of a computer. Informally, it consists of tapes, read/write heads, table of rules and an internal state. There are multiple technical variants of Turing machines. Here, we define prefix Turing machines
Definition C.2 (Prefix Turing Machine). A prefix Turing machine T is a Turing machine with one unidirectional (i.e. the head only move from left to right) input tape, one unidirectional output tape, and some bidirectional work tapes. Input tapes are read only, output tapes are write only. All tapes are are binary (no blank), work tapes are initially filled with zeros.
We say that T halts on imput with output æ, and write T(p) and x is to the left of the output head after T halts. The set of on which 7 halts forms a prefix code. We call such codes self-delimiting programs. The Turing machine may take another input y on its input tape. Since T is prefix Turing machine, y needs to be prefix encoded, denoted as y'. and then concatenated the program p. In this case, we say T(y'p)
if p to the left of the input head
The table of rules of a Turing machine 7 can be encoded as a binary string, which we denote by (T). Hence the of Turing machines {Ti, (/i,7,,... ..,...> can be enumerated (computably). We will use this property when we sum over Turing machines.
Universal Turing Machines. There are so-called universal Turing machines, which can "simulate" all Turing machines. We define particular one which simulates prefix Turing machine T (q) if fed with input gT)) ie. U((T)g) = T(g) VT, q. If p is not of the form (T)q, U (p) does not output anything. We call this particular U the reference universal Turing machine.
Semimeasures. Let X be the set of finite strings and x be the set of infinite sequences over some alphabet X' of size |.). Recall our sequence notation from $ length n we write use the shorthand æi with I; E X Vi E [1,2..... ..).
$55 for a string (I1, (2,,,22,... ................................ In. E X of
Definition C.3 (Semimeasure), Let e denote the empty string. A function μ X - R is semimeasure if for all x X²,, μu(e) < 1, and μux:) 2 EbEx j(xb), where xb denotes the concatenation of x and b, also an element of X" If equalities hold, is called a probability measure.
Remark C.1. Ps and Pæ ($ 5) are semimeasures, because Ex; ( T2, Fn) < The fact that the integral is less than 1 is due to the halting problem of UTMss [Tring 1936). which means that there are some programs in the sum that never stop running.
Definition C.4 (Lower semicomputability). A function f: - R is lower semicomputable iff there exists computable function (1x, k): Q x N - Q, such that
lim o(x, f() * 4k E N: o(x, k + + kz,
ie, if it can be approximated from below to arbitrary precision.
Kolmogorov complexity. Kolmogorov complexity measures the complexity of object as the length of the shortest program that generates the object. There is also a conditional version, based on the length of programs that input some other objects.
Definition C.5 (CConditional) prefix Kolmogorov complexity). The (conditional) prefix Kol- mogorov complexity of string x is the length / of the shortest halting program for which U outputs (given y):
K (x) = min(((p) (p) = x halts}
K(xly) == min(((p) : (U''p) = halts).
(8)
The Kolmogorov complexity of a semimeasure, pa (xf), is understood to be the length of the shortest self-delimiting program on U, computing (i("T) given xT, for every xT.
'Some works introduce the Solomonoff prior using monotone Turing machines (Hutter 2011
Grau-Moya
al. 2024 but for purposes, using prefix Turing machines is equivalent [Li and Vitányi 1997
22

---

D Acronyms
AR LM autoregressive language model
NLP Natural Language Processing
CS context-sensitive
OOD out-of-distribution
EOS end-of-sequence
RASP Restricted-Acces Sequence Processing Language
i..d. independent and identically distributed
ICL in-context learning
SOS start-of-sequence SSM State Space Model
LM language model
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We define the formal languages we use and the term rule extrapolation in Section 2 the detailed empirical findings can be found in Section 4 and the proposed normative theory is Section Furthermore, we clearly state the scope/ main limitation of the paper when we write "We empirically evaluate different models' rule extrapolation in formal languages with varying complexity, we study linear, recurrent, Transformer and State Space models" in the Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. It fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: There can be found a Limitations paragraph Section [6] which clearly states the limitations of our datasets and the architectures analysed. As we did not propose new algorithms, concerns regarding their computational efficiency are not applicabble
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The paper does not contain novel theorems and proofs. However, this section the checklist still applicable, as $ $ proposes a novel prior inspired by the Solomonoff prior, and provides high-level intuition on why the prior is suitable first-step for explaining OOD compositional generalization. $ | and the corresponding Appx. [C22 provides all necessary background and definitions. For all results that recalled from other sources, we provide references containing the proof (e.g. eq. (3)).
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All experimental details can be found in Section and Appendix B including how the metrics were evaluated, how the datasets were generated, and the parameters of the architectures and algorithm we use. The experimental results can be found in Section 4 Furthermore, we upload our code and experimental logs supplementary and make them publicly available upon acceptance.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
25

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We upload our code and experimental logs as supplementary and make them publicly available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. httppssccppullccgguuuieeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details can be found in Section 3 and Appendix B e.g. data generation, metrics, hyperparameters, type of architectures, type of the optimizer.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We report standard deviations in our tables and figures.
26

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the eπror bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report the experimental details, including our estimated energy consump- tion in Appx. B).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:///wwrrrps.cccccubbb////aaa itccciiieeeiciieeeeeeeee
Answer: [Yes]
Justification: Our paper aims to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which, we feel, must be specifically highlighted here.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
27

---

The answer NA means that the paper poses no such risks. This paper presents work that aims to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications,
authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks since our data sets are artificial and are far from real-world data sets. Moreover, the paper aims for deeper understanding, not for improvement.
Guidelines:
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We only use open source assets, i.e., code, which we properly cite in Appx.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
28

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: we release our codebase and experimental logs as supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [Yes]
Justification: We included the details for our small pilot human questionnaire in Appx. Participant were not compensated.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu-
tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Although our work includes a small human study, as it involved only questionnaire participants could fill out whenever and wherever they wished, and their participation was fully voluntary, no potential risks were involved. Thus, no IRB approval, equivalent, was necessart.
29

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "bH7Yj0G8bB", "reviewer": "Reviewer_Nwv7", "summary": "The article examines systematic generalization in neural networks using artificial grammar learning tasks. Distinctive to this work, the authors operationalize systematic generalization through studying how models extrapolate learned rules to ungrammatical (and thus OOD) seqeunces. Their examination considers a range of models as well as grammars of varying complexity. The article ends with a discussion of algorithmic information theorry and how it relates to OOD generalization.", "questions": "- This statement is just asserted but wasn't obvious to me and could use justification:\n\"In the a^n b^nn language, R2 (a-s before b-s), is, on average, simpler to generate than R1 (#a=#b) and R1 ∩ R2. \nEDIT : The author's response helps to address this question, and should be included in an updated paper.\n\ntypos\n- \"an Bob's enemy\" pg. 7", "limitations": "This section was fine", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The article has a number of strengths:\n- Distinctive operationalization of compositional generalization\n- Solid technical methodology\n- Evaluated a number of different model architectures and grammars\n- The writing and presentation are clear", "weaknesses": "The article also has weaknesses:\n\n- In my view the section on \"Normative theory of OOD prompt completion\" didn't contribute much to the article. It's right that this can serve as a normative account of how models should generalize OOD. However the relationship to the current article seemed thin. Instead, the authors could have established normative baselines for their tasks using probabilistic grammar induction and actually run a model to demonstrate a type of normative generalization.\nEDIT : The author's response helps to address this question.\n\n- This is a fine, technically sound article that doesn't strike me as particularly high impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation of our experiments and presentation. Please find below our replies to your concerns.\n\n## RE normative theory\nWe thank the reviewer for their feedback on our normative theory in Section 5. We agree that our theory relates loosely to the rule extrapolation phenomenon discussed primarily in this article. However, we think that even general (normative) theories of OOD prompt completion are limited in the literature, let alone specialised versions that the reviewer is suggesting. As a first step, we wanted to offer a general perspective on how an idealised model should complete OOD prompts, as we felt that general intuition was missing. Therefore, rather than fully explaining the special case of rule extrapolation, our work offers deeper intuition to the nature of OOD prompt completion as choosing the simplest hypotheses consistent with the training data. Our theory builds on Solomonoff induction, the foundation of Bayesian inference, and offers a new, novel way of relating OOD extrapolation into this general framework.\n\nApart from providing foundational understanding, we also relate our normative theory to the dynamics of rule learning in our experiments. We argue that the order in which the rules are learned is governed by the simplicity of the rules. This is in line with existing observations on the simplicity bias of language models (towards low Kolmogorov complexity [Goldblum et al., 2023], and further motivates our approach of building on the general theory of Solomonoff induction. In order to strengthen this connection in our narrative, we swapped Section 4.1 (training dynamics experiment) and Section 5 (normative theory), which makes it explicit that the training dynamics experiment is a verification of the high-level ideas in our normative theory section.\n\n\n## RE simplicity of rules\n\nThis high-level statement refers to the Kolmogorov complexities of generating R1 (#a=#b) and R2 (a-s before b-s). The shortest program generating instances following R2 is likely shorter than the shortest program generating instances from R1, since the R2 program can default to outputting only b-s once it generates a b, while the R1 program needs to keep track of the number of a-s and b-s it generates. Furthermore, R1 in itself is a regular language which is accepted by a pushdown automaton, while R2 defines a context-free language which is recognisable by a simpler automata, a finite-state machine.\n\n\n## RE impact of paper\nThank you for your feedback. We realise that we have not fully clarified the significance of our work in our original manuscript. We have expanded on this in our discussion, which we summarise here. \n\nWhile other OOD generalisation types were examined in the literature (Ruoss et al, 2022; Deletang et al. 2022; Ahuja and Mansouri, 2024), this is the first work studying/evaluating rule extrapolation. This novel concept has the potential to impact LLM research both on conceptual and practical levels:\n - General compositional generalization notions examine whether from learning multiple concepts/rules separately, the model can understand the composition of the concepts/intersection of the rules. However, in rule extrapolation we measure the reverse direction: from the composition/intersection, can the model identify the concepts/rules separately. Importantly, this notion of compositionality is less straightforward than the generally considered direction.\n- Natural languages are compositional, thus, we expect this property in LLMs if they ought to model these languages well. Therefore, studying rule extrapolation can help us better understand LLMs’ inner workings.\n- Rule extrapolation allows for studying compositional generalisation ability easily on a variety of datasets, such as formal or programming languages. Therefore rule extrapolation has the potential to become an established benchmark task for evaluating current and future LM architectures. \n\nIn order to further strengthen the significance of our contribution, we added multiple new experiments (xLSTM, size, hyperparameter, sampling technique ablations, and a new context-sensitive language). Please find the details in [our joint response](https://openreview.net/forum?id=Li2rpRZWjy&noteId=1xbJMvUYnC), and in the uploaded document.\n\n## References\nM. Goldblum, M. Finzi, K. Rowan, and A. G. Wilson. (2023). The no free lunch theorem, Kolmogorov complexity, and the role of inductive biases in machine learning,  URL https://arxiv.org/pdf/2304.05366\n\nK. Ahuja and A. Mansouri. (Feb. 2024) On Provable Length and Compositional Generalization, URL http://arxiv.org/abs/2402.04875\n\nDeletang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wenliang, L. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Veness, J., & Ortega, P. A. (2022, September 29). Neural Networks and the Chomsky Hierarchy. The Eleventh International Conference on Learning Representations. https://openreview.net/forum?id=WbxHAzkeQcn\n\nRuoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., & Veness, J. (2023). Randomized Positional Encodings Boost Length Generalization of Transformers (arXiv:2305.16843). arXiv. https://doi.org/10.48550/arXiv.2305.16843", "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": "HtM5shCyvd", "reviewer": "Reviewer_57oB", "summary": "This paper studies the compositional generalization of auto-regressive large language models with respect to rule extrapolation in formal languages. Both linear and recurrent architectures, including transformers, are compared on the task of inferring the rules that define regular grammars, context-free grammars, and context-sensitive grammars. The paper also presents the theoretical contribution of a normative theory of rule extrapolation, grounded on the idea of the Solomonoff prior, taken from algorithmic information theory.", "questions": "* The paper makes the conjecture that LSTMs perform better than LLMs on regular languages, because such grammars require comuting parity, which is a notoriously difficul task for LLMs. Did the experimental evaluation consider also different architectures and/or\nhyper-parameters for the transformer, to exclude that such worse performance depends on the choice of the model?\n\n* Similarly, the experimental evaluation is conducted on a single language for each category, and for a single architecture for each model: I wonder whether different architectural choices were tried for different models.\n\n* At the end of page 4, in the definition of \"Context-sensitive grammar\" there is R2 twice, while the first one should be R1.", "limitations": "See questions above.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ Understanding the compositional generalization capability of large language models is a challenging important task\n+ Interesting theoretical framework insipired by the Solomonoff prior and information theory\n+ Experimental evaluation with different baselines and languages/grammars", "weaknesses": "- Few theoretical insights to justify the experimental results (see comments below)\n- One single architecture tested for each model, and one single language for each category", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation of our chosen topic, proposed theory and experiments. We address your questions below:\n\n>One single architecture tested for each model, and one single language for each category\n\nOur architectures have been selected through initial manual hyperparameter optimisation. However, we have added further new experiments: size, hyperparameter, sampling technique ablations, a new architecture (xLSTM) and a new context-sensitive grammar (non-nested Dyck). Originally, we had 2 languages in each category except in the context-sensitive, but now there are 2 languages in that category, too. Please find the details in the joint response to reviewers, and on the uploaded document. Altogether (including all seeds), we have evaluated 1170 models. \n \n>Did the experimental evaluation consider also different architectures and/or hyper-parameters for the transformer, to exclude that such worse performance depends on the choice of the model?\n\n- From the additional experiments, it can be seen that increasing the **model size** does not meaningfully improve performance on regular languages; the best values remain those originally used (num_layers = 7, num_heads = 5) (Figure 7 (b)).\n- Regarding **hyperparameters** such as the optimisation algorithm and the learning rate, when considering the best settings for each architecture, LSTM consistently performs better than the Transformer on regular languages (Figure 7 (a)).\n- When using **sampling** instead of greedy decoding for next token prediction, LSTM is consistently better than the Transformer in OOD R1 extrapolation (Figure 6 (a)).\n\n>Similarly, the experimental evaluation is conducted on a single language for each category, and for a single architecture for each model: I wonder whether different architectural choices were tried for different models.\n\nBesides the size, optimisation algorithm, learning rate, and sampling technique ablations, we added a **new context-sensitive language** to ensure there is more than one grammar in each category. The new language is the non-nested Dyck language, where brackets and parentheses do not need to be nested; for example, the sequence ([)] is grammatical here. For the results, please see the joint response. We conclude that this language fits our narrative, specifically that the Transformer architecture is usually the best choice for non-regular languages. Figure X shows (cf. the uploaded pdf) the results: the Transformer and LSTM perform similarly on both OOD R1 and R2 completion. We note that although the Linear model appears to be the best, it is not representative since it predicts only the EOS token, resulting in an empty sequence that obeys both rules.\n\n>At the end of page 4, in the definition of \"Context-sensitive grammar\" there is R2 twice, while the first one should be R1.\n\nThank you for pointing out the typo; we have corrected it.\n\nWe would like to thank the reviewer for their valuable feedback, we hope that the extra experiments and reframed insights address the reviewer’s concerns.", "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": "k9RapKqWV8", "reviewer": "Reviewer_3gdK", "summary": "# Problem:\n\nWe lack systematic understanding about the Out-Of-Distribution (OOD) behaviours of autoregressive language models (LMs), such as in-context learning with natural languages prompts, despite successful deployment of LMs in such OOD situations.\n\nNatural languages (NLs) prompts, i.e. real-world data, are acknowledged as too complex to systematically study OOD behaviours.\n\n# Contributions:\n\nFormal languages have obvious practical relevance for programming languages and formal mathematics, despite their dissimilarities with NLs.\n\nIn contrast to NLs, formal languages enable studying in a systematic fashion rule extrapolation (as a special case of compositional generalization (systematicity)/OOD behaviours) and therefore provides a systematic framework to analyze and better understand LMs. Thus, the paper defines and empirically evaluate rule extrapolation for simple formal languages, with linear, recurrent (LSTM), transformers and state space models.\n\nThe paper also investigates whether the emergent capabilities found in Transformer-based LMs are also present in simpler models?\n\nTransformers models are found to surprisingly struggle with regular languages while they outperform other models with other categories, i.e. context-free and context-sensitive languages.\n\nLSTM and SSM models are found to indeed have some emergent capabilities for OOD behaviours, albeit to a lesser extent than Transformers, and the LSTM struggles less with regular languages.\n\nFinally, the paper proposes a non-parametric prior and prediction scheme for OOD prompt completion using Solomonoff induction, and discusses it in comparison to recent Algorithmic Information Theory frameworks, towards ‘building and assessing future practical models’. Their proposed prior is found to match the training dynamics of the Transformers on rule extrapolation for a context-free language ($L_3=\\{a^n b^n\\}$).", "questions": "# Questions:\n\nPlease see above, but mainly:\n\n- WC4\n\n# General advice:\n\nI would like to propose the authors to present section 4.1 after section 5 (theory before experimental validation) for increased impact. Indeed, when reading the paper the first time, I was surprised to find section 4.1 and could not understand what did it brought to the discussion. After having read section 5 it became clear that section 4.1 is an experimental validation to the theoretical concerns of section 5, thus my recommendation to change the ordering.", "limitations": "## Limitations:\n\nThe paper acknowledges limitations in terms of external validity with respect to different architectures and different attention or encoding mechanism.\n\n# POST REBUTTAL UPDATE :\n\nMost of my concerns have been addressed through the rebuttal in a satisfiable way, thus I am increasing my overall rating to 8, as well as contribution and presentation ratings to 'good'.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "# Strengths:\n\n## Originality:\n\nSO1: The paper is as original as it gets, as far as I am concerned, and I appreciate how it tries to still build bridges with previous work, mainly as it discusses how their normative approach relates to previous Algorithmic Information Theory methods.\n\n## Quality:\n\nSQ1: I appreciate section 2.2.’s discussion between Reizinger et al.[2024] and Zhou et al., [2023], and would encourage the authors to expand further on the impact on this work, possibly in the Discussion section.\n\n## Clarity:\n\nSC1: I appreciate the clarity externalisation approach used in Section 5.1.\n\n## Significance:\n\nSS1: Section 4 - Regular grammars, the paper proposes insights about the Transformer’s surprisingly low performance by relating it to previous work on parity ( but please see WS1 below).", "weaknesses": "# Weaknesses:\n\n## Originality:\n\nNothing to report, I find this paper as original as it gets.\n\n## Quality:\n\nWQ1: section 2.1 does not describe recursively enumerable languages nor explain why they are not considered in this paper. Adding those considerations could be one way to paint a more complete bigger picture about the current work and therefore enhance its quality.\n\n## Clarity:\n\nWC1: section 2.2. starts directly with ‘statistical generalization’ and ‘identifiability’ without having defined them, which might possibly hinders the readability of the paper for readers that are unfamiliar with this (relatively-)recent literature.\n\nWC2: missing ‘that’ or ‘which’ on ln94, possibly --> ‘formal languages _that_ are’ …\n\nWC3: typos on ln208: ‘largest extent(64%)’ --> ‘..(66%)’ ; on ln209 : ‘model again due’ --> ‘model _is_ again due’\n\nWC4: Figure 2 left : it is unclear what is represented given the range of the legend (from 0 to -15), please clarify?\n\nSimilarly, in Figure 2 right, I do not understand why is it a _sum_ of probabilities and not just the probability or likelihood, please clarify?\n\n## Significance:\n\nWS1: Following SS1 above, I think the paper could have a greater impact by possibly reproducing the parity experiment with the current architectures and propose correlation measures between the scores on OOD (R1/R2) and the parity accuracy, for instance.\n\nWS2: Providing results for the recently proposed xLSTM would increase the impact of the paper. Thus I would like to encourage the authors to consider adding it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We warmly thank the reviewer for their positive evaluation of our work, in particular highlighting its originality, clarity and interesting nature. Please find our replies to your comments and suggestions below.\n\n## WQ1 (section 2.1 does not describe recursively enumerable languages)\n\nWe added a discussion of recursivey enumerable languages. We omitted these similar to Deletang et al, 2022, as they require an infinite tape to simulate, which is impossible.\n\n## SQ1 (Expand discussion about further impact)\n\nThank you for your feedback, we have expanded on this in our discussion, which we summarise here.\nWhile other OOD generalisation types were examined in the literature (Ruoss et al, 2022; Deletang et al. 2022; Ahuja and Mansouri, 2024), this is the first work studying/evaluating rule extrapolation. This novel concept has the potential to impact LLM research both on conceptual and practical levels:\n- General compositional generalization notions examine whether from learning multiple concepts/rules separately, the model can understand the composition of the concepts/intersection of the rules. However, in rule extrapolation we measure the reverse direction: from the composition/intersection, can the model identify the concepts/rules separately. Importantly, this notion of compositionality is less straightforward than the generally considered direction.\n- Natural languages are compositional, thus, we expect this property in LLMs if they ought to model these languages well. Therefore, studying rule extrapolation can help us better understand LLMs’ inner workings.\n- Rule extrapolation allows for studying compositional generalisation ability easily on a variety of datasets, such as formal or programming languages. Therefore rule extrapolation has the potential to become an established benchmark task for evaluating current and future LM architectures. \n\n## WC1 (New paragraph in the background)\n\nWe have included a new paragraph in the background section about statistical generalisation and identifiability to improve the readability of the paper.\n\n\n## WC2-3 (typos)\nThank you for pointing out the typos, we have corrected them.\n\n## WC4 (Figure 2)\nOn the left, we plotted the log probability, resulting in the rage 0 - (-15). We updated the plot with a label and the caption to clarify this issue. On the right, we intended to show that R2 is learnt first and the language is identified as its subset, which is why we *summed* the probabilities of all sequences obeying only R1, only R2, both R1 and R2, and not R1 nor R2.\n\n## WS2 (xLSTM)\nWe have carried out the suggested experiments with the xLSTM architecture. \nDue to the limitations of our computational resources, not all languages could be tested with a significant number of seeds, and there was no time for extensive hyperparameter ablations. We aim to update our results in the discussion period. Our results are in Figure 6 (b) in the uploaded document. We see that xLSTM indeed outperforms LSTM, but cannot reach the Transformer on the non-regular languages. \n\n\n### Hyperparameters for xLSTM:\nWe used the following hyperparameters for xLSTM. Most of these were suggested by the xLSTM github repository, except for num_blocks and xlstm_embedding_dim, which were lowered to match the size of the other models we trained. This model has 185K parameters.\n ```model: xlstm\n  mlstm_block:\n    mlstm:\n      conv1d_kernel_size: 4\n      qkv_proj_blocksize: 4\n      num_heads: 4\n  slstm_block:\n    slstm:\n      backend: cuda\n      num_heads: 4\n      conv1d_kernel_size: 4\n      bias_init: powerlaw_blockdependent\n    feedforward:\n      proj_factor: 1.3\n      act_fn: gelu\n  num_blocks: 5\n  xlstm_embedding_dim: 64\n  slstm_at: [ 1 ]\n```\n\n## WS1 (Parity Experiment)\nThank you for this suggestion. We thought about how to best incorporate parity into our framework, and we carried out the following experiment.\n\n**Parity extrapolation.** In the anbn language, Rule 1 (#a=#b) is a subset of the rule “even number of tokens in the sequence”. Thus, in order to extrapolate R1 on OOD prompts where R2 is broken, it’s necessary for the model to also understand and extrapolate parity (since #a=#b means the sequence has even length). To understand the relationship between parity and R1 extrapolation, we tested whether failure on R1 extrapolation also means failure in parity extrapolation.\n\n\nOur results **(see the below table)** show that models learnt to extrapolate parity, despite their imperfect R1 extrapolation accuracies. This supports our intuition  that parity is an easier task, and R1 extrapolation requires other concepts as well (such as equality). \n\n\n| Model                 | Test loss                 | ID R1                     | ID parity                 | OOD R1                    | OOD parity                |\n|--------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|\n| Linear | $2.796\\scriptscriptstyle\\pm 0.171$ | $0.200\\scriptscriptstyle\\pm 0.000$ | $1.000\\scriptscriptstyle\\pm 0.000$ | $0.275\\scriptscriptstyle\\pm 0.000$ | $1.000\\scriptscriptstyle\\pm 0.000$ |\n| LSTM           | $0.019\\scriptscriptstyle\\pm 0.000$ | $1.000\\scriptscriptstyle\\pm 0.000$ | $1.000\\scriptscriptstyle\\pm 0.000$ | $0.351\\scriptscriptstyle\\pm 0.056$ | $1.000\\scriptscriptstyle\\pm 0.000$ |\n| Transformer   | $0.022\\scriptscriptstyle\\pm 0.002$ | $1.000\\scriptscriptstyle\\pm 0.000$ | $1.000\\scriptscriptstyle\\pm 0.000$ | $0.628\\scriptscriptstyle\\pm 0.103$ | $1.000\\scriptscriptstyle\\pm 0.000$ |\n\n\n## General advice\nThank you for pointing out this unclarity in our narrative. We have changed the structure as suggested: section 5 now precedes section 4.1. \n\nWe would like to thank the reviewer again for their constructive questions and suggestions, which we hope we successfully addressed.", "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": "PmiZUbbhYl", "reviewer": "Reviewer_AxjF", "summary": "This paper studies rule extrapolation, one OOD behavior, of autoregressive LLMs on different models to understand the effect of model's architecture on this specific ability. The paper also introduces a normative theory for OOD prompt completion, which well explains the empirical observation about the training dynamics enabling the rule extrapolation.", "questions": "I have several concerns:\n1. Does the model size significantly impact performance? For instance, if the size of the Transformer model is increased, is there a potential for a substantial improvement in its performance on regular grammars?\n2. Contemporary language models typically use sampling rather than greedy decoding to generate sequences. If the sampling technique is altered, would the results remain consistent?", "limitations": "See weakness and questions.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper studies an interesting and important question for language models: how different models do extrapolation and how well they are. It is well-structured and clearly presented. The authors conduct extensive and well-designed simulations, yielding valuable insights into the rule extrapolation capabilities of various models. Additionally, the paper introduces a normative theory to elucidate the training dynamics associated with rule extrapolation observed in practice. This is a very good starting point for the community to investigate the OOD problem for the language models.", "weaknesses": "The paper only investigates four models with fixed sizes. It is commonly acknowledged that the model capacity rely on the model size, which is not adequately addressed in the paper. While the study provides a general impression of the models' capabilities on different tasks, it remains unclear whether the observed differences are due to variations in model size, specific structural characteristics of each model, or a combination of both.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their positive evaluation of our work, in particular highlighting its relevance, good structure, clarity and deeming our experiments extensive and well-designed.\n\nWe agree with the reviewer that beyond the present experiments, there are various other options and ablations to evaluate. We have carried out additional experiments on:\n- Transformer model size\n- Sampling instead of greedy decoding\n- Hyperparameter ablation\n- A new context-sensitive language\n- The xLSTM architecture\n\nPlease find the results of your suggested experiments under ‘Transformer size ablation’ and ‘Sampling’ below. The results of the rest of the experiments are in [our general response](https://openreview.net/forum?id=Li2rpRZWjy&noteId=1xbJMvUYnC).\n\n## **Transformer size ablation**:\n As suggested, we tested varying size settings (different numbers of layers and heads) for the Transformer architecture to determine whether increasing size can improve performance on regular languages. As shown in Figure 7(b) (cf. the uploaded pdf), increasing the model size does not meaningfully improve performance on regular languages; the best values remain those originally used (`num_decoder_layers = 7, num_heads = 5`). For non-regular languages, the Transformer already outperformed the other architectures.\n\n## **Sampling**:\n Our initial results use greedy decoding, but we conducted experiments to evaluate the sampling method for next token prediction. As shown in Figure 6(a), we conclude that while the Transformer is the best choice with greedy decoding (except for regular languages where LSTM performs better), LSTM appears to excel when using sampling. These results also open up new interesting future directions, e.g., investigating the influence of different temperature values in the softmax.\n\nWe hope that our additional experiments have addressed the reviewer’s concerns.", "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:
We would like to thank the reviewers for their constructive feedback and suggestions. We were happy to see that **the reviewers found our topic important, our methodology solid, and our presentation clear**. We supply separate replies to all reviewers, but summarize the common points in our joint response. 

The main suggestion of the reviewers was to add more experiments. We would like to summarise these here in the joint response. We implemented all the suggested experiments, including a new language, a new architecture, and an extensive hyperparameter search covering model size, optimization algorithm, learning rate, a parity check and next token prediction method. Overall, these experiments confirm our results and narrative. However, due to time and computational constraints, the results are based on a limited number of seeds, and some settings are missing. We will continue these experiments and update the results during the discussion period. If our paper is accepted, we will include all the necessary experiments in the camera-ready version. Currently, altogether (including all seeds), we have evaluated 1170 models. Please find our current conclusions below.


### New context-sensitive language:
 We added a new context-sensitive language to ensure there is more than one grammar in each category. The new language is the non-nested Dyck language, where brackets and parentheses do not need to be nested; for example, the sequence ([)] is grammatical here. We conclude that this language fits our narrative, specifically that the Transformer architecture is usually the best choice for non-regular languages. **The table below** shows the results: the Transformer and LSTM perform similarly on both OOD R1 and R2 completion. We note that although the Linear model appears to be the best, it is not representative since it predicts only the EOS token, resulting in an empty sequence that obeys both rules.

| Model| Test loss | ID R1 | ID R2| OOD R1| OOD R2  completion |
|--|--|----|-|-|---|
| Linear | $4.013\pm 0.254$ | $0.000\pm 0.000$ | $0.000\pm 0.000$ | $0.000\pm 0.000$ | $1.000\pm 0.000$ |
| LSTM           | $0.645\pm 0.019$ | $0.981\pm 0.042$ | $0.956\pm 0.061$ | $1.000\pm 0.000$ | $0.894\pm 0.165$ |
| Mamba          | $0.675\pm 0.018$ | $0.745\pm 0.070$ | $0.807\pm 0.185$ | $0.684\pm 0.159$ | $0.810\pm 0.212$ |
| Transformer   | $0.640\pm 0.016$ | $1.000\pm 0.000$ | $1.000\pm 0.000$ | $0.980\pm 0.045$ | $0.973\pm 0.044$ |





### xLSTM: 
As suggested by one of the reviewers, we implemented the latest extension of the LSTM architecture, the xLSTM model. Due to time constraints, we did not conduct a hyperparameter search, however, using a model with approximately the same number of parameters as our other architectures performs in alignment with our narrative. Furthermore, we see that xLSTM indeed outperforms LSTM, but cannot reach the Transformer on the non-regular languages. The results are plotted in Figure 6 (b)  (cf. the uploaded pdf), and we will include the outcomes of additional runs with different hyperparameters in our paper.

### Sampling the next token: 
Our initial results use greedy decoding, but we conducted experiments to evaluate the sampling method for next token prediction. As shown in Figure 6 (a), we conclude that while the Transformer is the best choice with greedy decoding (except for regular languages where LSTM performs better), LSTM appears to excel when using sampling. These results also open up new interesting future directions, e.g., investigating the influence of different temperature values in the softmax.

### Hyperparameters: 
We tested multiple hyperparameters, including three learning rates and two optimization algorithms, and plotted the results in Figure 7 (a)  (cf. the uploaded pdf).  Due to time constraints, we could not produce results for all languages, but we will include them in the paper as soon as possible; we plan to do so during the discussion period. Despite this, our claims remain valid: when considering the best settings for each architecture, LSTM consistently performs best on regular languages, while the Transformer excels on everything else.

### Size ablation:
As suggested, we tested varying size settings (different numbers of layers and heads) for the Transformer architecture to determine whether increasing size can improve performance on regular languages. As shown in Figure 7 (b)  (cf. the uploaded pdf), increasing the Transformer model size does not meaningfully improve performance on regular languages; the best values remain those originally used (`num_decoder_layers = 7, num_heads = 5`). For non-regular languages, the Transformer already outperformed the other architectures.

### **Expanding the discussion:**
While reviewers appreciated our discussion on the impact of our work, they suggested expanding it in the Discussion section. We summarise it here.

While other OOD generalisation types were examined in the literature, this is the first work studying rule extrapolation. This novel concept has the potential to impact LLM research both on conceptual and practical levels:
- General compositional generalization notions examine whether from learning multiple concepts/rules separately, the model can understand the composition of the concepts/intersection of the rules. However, in rule extrapolation we measure the reverse direction. Importantly, this notion of compositionality is less straightforward than the generally considered direction.
- Natural languages are compositional, thus, we expect this property in LLMs if they ought to model these languages well. Therefore, studying rule extrapolation can help us better understand LLMs’ inner workings.
- Rule extrapolation allows for studying compositional generalisation ability easily on a variety of datasets, such as formal or programming languages. Therefore rule extrapolation has the potential to become an established benchmark task for evaluating current and future LM architectures.

Meta-review: This paper proposes training models on data generated according to multiple rules, and evaluating models on generalization problems that involve extrapolating some of those rules to situations where others are violated. This is an interesting approach to generalization which differs somewhat from most prior OOD evaluations (even others on formal languages). The authors then systematically test different classes of models for extrapolation under several sets of rules, and find an interesting pattern of results. The reviewers generally agree that the paper is a useful contribution, especially after revision, and I concur.

I do think, however, that the work could situate itself better within the prior literature —  some prior papers have considered pitting structural rules against superficial ones in a way that resembles the rule extrapolation setting, e.g. https://aclanthology.org/2023.acl-short.38/ even if it does not explain it particularly clearly (see Fig. 1 caption).  Likewise, the prior Chomsky Hierarchy work (https://arxiv.org/abs/2207.02098) that came up in the discussion period seems worth discussing as well, even though it does not use the same extrapolation approach it is clearly a related space of issues. These are simply examples; I’d encourage the authors to do a more thorough literature review of related topics for the camera ready verison. These works do not impinge on the novelty of the current work, but discussing their relation would help to situate the reader and allow them to understand the current contribution better.
Decision: Accept (spotlight)