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_cc_2024_Conference
Published: 2024-05-15 20:24:46

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.

Main paper: 
 introduction: 
 Autoregressive language models (AR LMs) can reach both low training and test loss, but even minimal test loss is not predictive for out-of-distribution (OOD) model performance [Liu et al., 2023 , Reizinger et 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 Padó, 2024 , Ramesh et al., 2024 , Lake and Baroni, 2023 , Reizinger et al., 2024] . To systematically examine compositional generalization of AR LMs, we study a particular notion of OOD generalization, which we call rule extrapolation.Rule extrapolation is a form of compositional generalization: it studies OOD behavior of language models trained on formal languages defined by a logical conjunction of rules.For example, the a n b n 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 bbaab cannot be completed to obey the R2, but it is still possible to satisfy (R1) (e.g., bbaaba). When a language model trained on an intersection of rules remains consistent with one of the rules when another is broken, we say it successfully extrapolated the rule beyond its training data.A limited experiment by Reizinger et al. [2024] indicated that Transformers exhibit much-better-thanchance rule extrapolation performance on the formal grammar a n b n , despite lacking any explicit inductive biases encouraging this behaviour. However, it remains unclear whether the behaviour observed was specific to the Transformer or whether it holds more generally on a wider range of formal languages. Inspired by this work, we conduct a thorough empirical investigation of the role of architecture in rule extrapolation on a range of formal languages. As a non-rigorous baseline, we also conducted a 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 a 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 a 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 to Algorithmic Information Theory (AIT) to formalize a normative model. We propose a non-parametric prior for next-token prediction inspired by the Solomonoff prior [Solomonoff, 2001, Li and Vitányi, 1997] . This prior helps resolve how a 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 in 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 no single architecture that emerges as a 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, we propose a normative theory for OOD prompt completion, which posits that rule learning and extrapolation should be governed by the relative simplicities of rules ( § 5); • To demonstrate the presence of a similar simplicity bias in Transformers, We visualise the training dynamics enabling rule extrapolation on the a n b n language. We find that the model first learns a set obeying the easier rule, and then identifies the language as its subset ( § 5.3) .Figure 1 : Rule extrapolation summary for all models and languages (Tab. 1): 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) 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 
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 a possibly infinite alphabet. Chomsky [1956] has categorized formal languages into four types with increasing complexity: regular, context-free, context-sensitive, and recursively enumerable languages. Regular languages have rules that can be expressed via regular expressions, e.g., L 1 = {bα : α contains even number of a's} and L 2 = {b n a 2m : 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 demonstration purposes, we will use two simpler languages:L 3 = {a n b n : n > 0}, L 4 ={sequences of nested parentheses and brackets}. Context-sensitive grammars have rules that depend on the position in the sequence-we will use the standard example of L 5 = {a n b n c n : n > 0} and L 6 = {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.In modern deep learning theory, the test loss distinguishes the performance of models with low training loss by evaluating the model on unseen data sampled from the same distribution (i. e., i.i.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 on the generalization gap [Vapnik and Chervonenkis, 1971 , Dziugaite and Roy, 2017 , Pérez-Ortiz et al., 2021] . Along with the question of whether the test loss is sufficiently 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.i.d. 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., 2021 , Wiedemer et al., 2023b ,a, Brady et al., 2023 , Yang et al., 2023 , Lachapelle et al., 2023] ; however, such studies are only started emerging for natural language [Ahuja and Mansouri, 2024 , Han and Padó, 2024 , Ramesh et al., 2024 , Lake and Baroni, 2023 , Nogueira et al., 2021 , Dziri et al., 2023 , Saparov et al., 2023] . 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 or regularization, Transformers can exhibit much-better-than-chance extrapolation performance on some synthetic grammars. However, 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 a subset of rules is 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 n b n language is the intersection of two rules: (R1) the number of a'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 (e.g., bbaaba).Several deep learning architectures, such as CNNs or GNNs, were designed to capture specific structural data properties. Such inductive biases in sequence models remain to be understood [Reizinger et 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 et 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. Weiss et al. [2021] developed a formal programming language called RASP to model the inner workings of the Transformer, whereas Zhou et al. [2023] defined a 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 et al., 2020] , and also the structure of the training data [Chan et al., 2022] . LM inductive biases have also been studied from a mechanistic interpretability perspective. Most notably, Olsson 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., 2023] . These works constitute important progress; though we take a 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 as linear models or RNNs?3 Experimental setupQuestion: Does the paper discuss the limitations of the work performed by the authors?Justification: There can be found a Limitations paragraph in 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 a 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 on 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 on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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., 2023] caused a breakthrough in Natural Language Processing (NLP) by introducing the (self-)attention mechanism, allowing it to capture global dependencies efficiently in both directions, unlike the standard LSTM. Adapted from dynamical systems, SSMs have recently entered language modeling, and became increasingly popular, such as 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 matrix-valued memory cells, new gating and memory mixing mechanisms, and several computational improvements. Training details, data set sizes, and model parameters are in Appx. B.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 no connection between the language's complexity in the Chomsky hierarchy and what a neural network finds difficult to learn. Each language we study obeys two rules, and the OOD prompts violate the corresponding R2, but the prompt can still be completed to satisfy the other. Following (R1) and/or (R2) provide different information: following (R1) means the LM still adheres to a 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. 1. 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 L 3 and L 5 in Tabs. 4 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 1 = {bα : α contains even number of 'a's} and L 2 = {b n a 2m : n, m > 0}. The rules of the language L 1 are: (R1) there are even number of as in the sequence; and (R2) the sequence starts with a b. For L 1 , the OOD prompts consist of prompts that violate (R2) , i.e. start with an a, but all these prompts can be completed to satisfy (R1). For language L 2 , the rules are: (R1) there are even number of as in the sequence; and (R2) bs precede as. The OOD prompts for L 2 violate (R2). They start with a single a, then a block of bs and possibly a block of as.Context-free grammars. We implemented two context-free grammars L 3 and L 4 : L 3 = {a n b n : n > 0}, i.e., (R1) the number of as and bs match; and (R2) as precede bs. For L 3 , OOD prompts violate (R2) , i.e., the prompts include b tokens followed by a tokens.Our fourth formal language is a bracketing (Dyck-) language, i.e., L 4 = {sequences of nested and paired parentheses and brackets}, e.g. "( [ ]( ) )" The rules of the language are: (R1) brackets are nested and paired; and (R2) parentheses are nested and paired. Paired means that every opening bracket/parenthesis has a closing pair; nested means that between an opening and closing bracket/parenthesis, all other tokens must be paired-contrast this with L 6 . For L 4 , 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.We implemented two context-sensitive grammars L 5 and L 6 . L 5 = {a n b n c n : n > 0}. Though it seems very similar to L 3 , its grammar rules make it context-sensitive, i.e., the tokens generated depend on multiple tokens. The grammar rules can be summarized as: (R1) the number of as, bs, and cs 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). L 6 is a context-sensistve Dyck-language, i.e., L 6 = {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 L 4 , for L 6 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 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 L 3 OOD prompt abbb is as follows: the completion abbbaa is considered correct for (R2), but abbbabaa is not, as it has an a after a b in the completion. 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 a model that always predicts each token (excluding the start-of-sequence (SOS) token) as the next token with equal probability2 . We report means and standard deviations across 5 seeds. Similar to [Rajamanoharan et al., 2024] , we provide a non-representative human baseline based on a small pilot study, where participants have seen three examples for L 1 , L 3 then were asked to complete five OOD sequences for each (Appx. B.6). 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.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 of the checklist is still applicable, as § 5 proposes a novel prior inspired by the Solomonoff prior, and provides high-level intuition on why the prior is a suitable first-step for explaining OOD compositional generalization. § 5 and the corresponding Appx. C.2 provides all necessary background and definitions. For all results that are 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 crossreferenced. • All assumptions should be clearly stated or referenced in 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 to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
results: 
 Regular grammars. Perhaps surprisingly, modern architectures perform the worst on regular languages L 1 (Tab. 2) and L 2 (Tab. 3) : both Mamba and the Transformer are worse in-and out-ofdistribution than the LSTM-the xLSTM only matches the LSTM in OOD performance on (R1). Furthermore, the Transformer's accuracies are below chance level even for in-distribution, despite having approximately the same test loss as the LSTM and Mamba. The Linear model seemingly manages to obey perfectly (R2) in-distribution on L 2 , 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 1 (Tab. 14). 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 L 1 , L 2 require calculating the parity of a tokens. Context-free grammars. On the context-free grammars L 3 , L 4 , the conclusion is different. On L 3 (Tab. 4), although all four models achieve perfect accuracy on (R2) both in-and out-of-distribution, and all models except the Linear, (near) perfectly obey (R1) in-distribution, the Transformer extrapolates (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 L 4 (Tab. 5), the Transformer has the best extrapolation performance, and Mamba is better than the LSTM. On L 3 , the human participants in our small study had performed better on following (R2) on the completion than extrapolating (R1); however, the Transformer was better than humans in extrapolating both (R1) and (R2).Chance N/A 0.105 0.356 0.154 0.445 Linear 2.553±0.159 0.200±0.000 1.000±0.000 0.275±0.000 1.000±0.000 LSTM 0.019±0.000 1.000±0.000 1.000±0.000 0.376±0.209 1.000±0.000 Mamba 0.019±0.000 1.000±0.000 1.000±0.000 0.296±0.043 1.000±0.000 Transformer 0.022±0.002 1.000±0.000 1.000±0.000 0.657±0.162 1.000±0.000 xLSTM 0.019±0.000 1.000±0.000 1.000±0.000 0.438±0.252 1.000±0.000Table 4 : Test loss and rule-following accuracies for the context-free language L 3 = {a n b n }: the Transformer can extrapolate (R1) the best.Context-sensitive grammars. The grammar L 5 (Tab. 6) is similar to L 3 , i.e., the Transformer performs best. Intuitively, the sequences in the form of {a n b n } and {a n b n c n } are rather similar, despite the latter being context-sensitive in Chomsky's hierarchy. Rule extraplation accuracies for (R1) in L 5 are lower than for L 3 , 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 context-sensitive Dyck language L 6 (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. 1 ). Although the Transformer has a consistently good performance on the investigated contextfree 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 1 , L 3 , humans found the tasks difficult: they performed better than chance, though the LSTM performed better on L 1 , and the Transformer on L 3 (Tab. 14)-we emphasize that our human-machine comparison only provides intuition, rather than a rigorous evaluation of human performance, which is left for future work. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: All experimental details can be found in Section 3 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 as supplementary and make them publicly available upon acceptance.• 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 a 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 is a specific model and empirical evaluation, it may 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. Justification: 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.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or 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 or 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 not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the 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, it is not needed to point out that a 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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 a step back to ask what should happen: how an ideal model should learn and extrapolate rules. We propose a non-parametric prior and prediction scheme for OOD prompt completion, that can be seen as a generalization of Solomonoff induction [Solomonoff, 2001, Li and Vitányi, 1997] to settings relevant for AR LMs.Although our algorithm, just like Solomonoff induction, is uncomputable, we argue that it formalises a rational approach capable of OOD extrapolation in AR sequence models. Rather than a practical algorithm itself, it should be interpreted as a 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 [Theis, 2024 , Goldblum et al., 2023] , and have been applied in practical algorithms [Grau-Moya et al., 2024] .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 p data , that autoregressively generates M i.i.d. sequences of length m, {(x 1,j , x 2,j , . . . x m,j )} M j=1 := (x m 1j ) M i=1 . Since the sequences are generated autoregressively, we may call (x m-1 1j ) M j=1 the ID prompts, and each m th element (x m,j ) M j=1 its ID completions. Suppose that Charlie, Bob's enemy, generates a n-length sequence from the same LM, and intervenes (in the causal sense) on it, so that the resulting sequence (x 1 , x 2 , . . . x n-1 ) := x n-1 1 has zero probability under the LM. We call this the OOD prompt. Despite p data (x n-1 1 ) = 0, the LM still defines the conditional probability of completing the OOD prompt x n-1 1 . Charlie then asks an observer, Alice, to predict how Bob's LM will complete the OOD prompt x n-1 1 , i.e., what x n will be. Fig. 2 shows the probabilistic assumptions of Alice: the completions are generated independently, according to the same procedure (i.e., using the same LM). We use the conditional independence assumption x n ⊥ (x m 1 ) M j=1 | x n-1 1 in eq. ( 4) below.p data j ∈ (1, 2, . . . , M ) ID prompt (x m-1 1 ) j ID completion (x m ) j OOD prompt OOD completion (x n-1 1 )x nFigure 2 : Graphical model representing our approach for OOD prompt completion. Although Bob's LM p data assigns zero probability to the OOD prompt, it 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 are used for generating the completions). This is the same as assuming that the Markov factors marked in blue are the same, i.e. p(completion|prompt, p data ) = p(completion|OOD prompt, p data ), and the conditional independence OOD completion ⊥ ID prompt | OOD prompt.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.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 razor and Epicure's principle, as simple data points have a larger probability, and every possible explanation is 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 a monotone universal Turing machine (UTM). Solomonoff's universal prior [Solomonoff, 2001] is defined over arbitrary-length sequencesEQUATIONwhere we sum over all discrete lower semicomputable semimeasures p i (x N 1 ) implementable on the UTM [Li and Vitányi, 1997 ]. We will refer to the p i (x N 1 ) as mixture components or explanations of the data. The prior on weights α(p i ) is an arbitrary semimeasure, i.e., ∀i : α(p i ) > 0 and i α(p i ) ≤ 1. Frequently, α(p i ) is chosen as 2 -K(pi) , the prefix Kolmogorov complexity of p i 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 α(p i | x N -1 1) is updated via Bayesian inference:EQUATIONConvergence of predictions. Suppose that the true distribution of (x 1 , x 2 , . . . , x N ) is µ. The Solomonoff prior (with any valid sequence of weights) satisfies [Hutter, 2005] .p S (x N | x N -1 1 ) N →∞ ----→ µ(x N | x N -1 1) with µ-probability 1.(3)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 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 a mixture component p i . However, by definition, the Solomonoff prior can only take in a single sequence x n 1 . 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, it is 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: (i) We condition the prediction on a pre-training dataset D of M independent and identically distributed (i.i.d.) sequences of finite length m, i.e.D = {x m 1j } M j=1 . D is sampled from the distribution p M data (D) = M j=1 m k=2 p data (x k,j | x k-1 1,j ).For simplicity, we assume that each pre-training datapoint has equal length m. (ii) Instead of modelling semimeasures as joints over sequences {(x N 1 )} N ∈N , we model semimeasures as lists of conditionals, just as how AR LMs model probability distributions over{(x k | x k-1 1 )} Nk=2 , enumerating them with index i = 1, 2, . . . , denoting each semimeasure as p i| to emphasize the lists of conditionals representation. That is,p i| (x k | x k-1 1 ) and p i| (D) mean p i (x k | x k-1 1 ) and p i (D) = M j=1 m k=2 p i (x k,j | x k-11,j ), respectively. Note that the pre-training distribution p data also belongs to the set of p i| . We define a mixture over all lists of discrete lower semicomputable semimeasures p i| implementable on the UTM See Appx. C.1 for details.The motivation for modelling x N 1 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-probability sequences have multiple factorizations (see Appx. C.1 for justification and more details on this notation). If the prompt x n-1 1 comes from a distribution different from D ∼ p M data , that assigns zero probability mass to x n-1 1 , the probability p data (x n | x n-1 1) is left undefined if only the joint probability p data (x n 1 ) is specified. This is not a problem in the Solomonoff prior, as 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):EQUATIONInterpreting p R . Starting from a prior weight α over all possible explanationsp i| = {p i (x k | x k-1 1 )} n k=2, the posterior probability of p i| given D is computed (eq. ( 4), right). The n th step prediction by p i , conditioned on a possibly OOD test prompt, is then weighted by this posterior. It is important that the prediction p i| (x n | x n-1) is not conditioned on the pre-training data D, and the posterior α(p i| | D) is not conditioned on the test prompt x n-1 1 . This, as stated above, separates pre-training from testing, enabling us to define the completion of OOD test prompts. When D equals x n-1 1 , p R reduces to p S , and thus the posterior prediction converges according to eq. ( 3). Choice of the weight prior α(p i| ). For OOD test prompts, there are multiple explanations p i| consistent with D. Therefore, the behaviour of p R , even when |D| tends to infinity, depends on the prior weight α(p i| ). This differs from the Solomonoff prior, which converges to the true posterior regardless of the weights (eq. ( 3)) [Hutter, 2005] . Thus, α must be chosen to allow the extrapolation of simple explanations consistent with the data. We define α(p i| ) := 2 -K(p i| ) , penalising exponentially the length of the shortest program (implemented on the fixed UTM) K(p i| ) that can approximate p i| (each conditional probability) for every prompt x n 1 . This encodes Occam's razor into the prior, and is consistent with the optimal weights of the Solomonoff prior [Hutter, 2005] .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 a n b n 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 n b n 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 a formal language with rules (R1) and (R2), let p 1 , p 2 and p 1,2 be distributions defined by LMs that generate sequences that satisfy (R1), (R2) and (R1) ∩ (R2), respectively. If, e.g., K(p 2 ) ≪ K(p 1,2 ), our normative algorithm will first learn (R2), and then learn the (R1) ∩ (R2) as its subset. In the a n b n language, (R2) (a's before b's), is, on average, simpler to generate than (R1) (#a=#b) and (R1) ∩ (R2). Therefore, we expect our normative algorithm to first learn (R2), and then learn (R1) ∩ (R2) as its subset. Remarkably, our Transformer employs the same 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 to 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 our normative algorithm similarly to the approach of Grau-Moya et al. [2024] , will result in models with superior rule extrapolation properties. We leave this promising direction to future work. 
discussion: 
 Conclusion. We argue that focusing on rule extrapolation and formal languages gives us sound (theoretical) tools to analyze and better understand out-of-distribution behaviour in language models, such as the role of 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 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, we find that the model first identifies the whole set obeying one of the rules, then it 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 us to explain and contextualise some of our empirical observations. Impact. Rule extrapolation is a 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 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: from the composition/intersection, can the model identify the concepts/rules separately? Importantly, this direction is less straightforward. Rule extrapolation allows for easy study of compositional generalisation ability 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. 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, e. 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. We use PyTorch [Paszke et al., 2019] , PyTorch Lightning [Falcon, 2019] , and HuggingFace Transformers [Wolf et al., 2020] . Our training pipeline builds on [Reizinger et al.] and we use the PyTorch implementation of Mamba from [LeGuet] and the code released by the authors for the xLSTM [Beck et al., 2024] . Our code and experimental logs are publicly available at https://github.com/meszarosanna/rule_extrapolation.Training data. We generate data from the formal languages L 1 , L 2 , L 3 , L 4 and L 5 described in § 3.2 up to length 256-excluding the SOS and EOS tokens, i.e., those two tokens add two to the maximal length. The SOS (0), EOS (1), and padding (2) tokens are always represented by these numbers. When the grammar consists of 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), ′ [ ′ (5) and ′ ] ′ (6). We used different data set 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, L 1 , L 2 the training set consists of 15000 samples (as these languages have rules satisfied by many sequences), and for L 4 , 512 samples. For L 3 and L 5 , the corresponding data sets include all unique sequences up to length 256, which is 128 for L 3 and 85 for L 5 , respectively.Test prompts. We define our test prompts as all possible sequences of length 8 (prepended with SOS) for L 1 and L 3 , and all possible sequences of length 5 (prepended with SOS) for L 5 = {a n b n c n : n > 0}-we chose different lengths to have a comparable number of test samples, i.e., 2 8 and 5 3 , 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 L 2 , 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 OOD prompts by adding a single a to the beginning of the sequences. For L 4 , 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.We observed that the Linear model constantly predicts PAD tokens, unless we ignore those by setting the ignore_index=PAD in torch.nn.CrossEntropyLoss(). However, for comparison, when reporting the losses, we report the loss where we do not set the ignore_index parameter. 3 was plotted on the a n b n language with the Transformer on seed 63656. The left left was plotted at the Lightning module's "self.global_step=0", left middle at "self.current_epoch = 600" and left middle at nearly end of the training at "self.current_epoch=9700". On the right, the sum of the probabilities was computed at every epoch divisible by 100. Similarly, Figure 4 was plotted on a n b n with LSTM with seed 8556, and Figure 5 on a n b n with Mamba with seed 91686.Greedy decoding vs sampling. Our initial results use greedy decoding, but we conducted experiments 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. 6a ); the LSTM appears to excel when using sampling (Fig. 6b ).These results also open up new interesting future directions, e.g., investigating the influence of different temperature values in the softmax. Figure 6 : Rule extrapolation summary for all models but the xLSTM and languages L 1 -L 5 (Tab. 1) with greedy (Fig. 6a ) and sampling (Fig. 6b ) next-token decoding Figure 7 : Rule extrapolation performance for different optimizers and learning rates for all models except the xLSTM and languages L 1 -L 5 (Tab. 1): top row left is the same as Fig. 6a Hyperparameter sensitivity. We tested multiple hyperparameters, including three learning rates and two optimization algorithms, and plotted the results in Fig. 7 . Though our hyperparameter search 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 of layers and heads) for the Transformer architecture to determine whether increasing size can improve performance on regular languages. As shown in Fig. 8 , increasing the Transformer model size does not meaningfully improve performance on regular languages; the best values remain those originally used (num_layers = 7, num_heads = 5). For non-regular languages, the Transformer already outperformed the other architectures. 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.Instructions. 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:• first, we show some example sequences • then on, we start sequences and ask you to finish them as you see fit Then, on the three following pages of the questionnaire, they were presented the following: We generate sequences according to some patterns. You see below examples, which are 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 is to 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 see fit.• If you think the sequence is already completed, leave the space for the completion empty Case 1: regular grammar L 1 . The examples for the context-free grammar L 1 were:• baba • baa • babbaaaThe prompts the participants needed to complete were:• aba • abba • abaaba • abab • aabaCase 2: context-free grammar L 3 . The examples for the context-free grammar L 3 were:• aabb • aaabbb • aaaaaabbbbbbThe prompts the participants needed to complete were:• baa • abaa • bba • baabResults. We preprocessed the questionnaire results to remove invalid responses (e.g., those with invalid characters, where we assumed that we did not explain the task well to the study subjects). We report the OOD (R1) and (R2) accuracies, the latter only on the completion in Tab. 14.Language OOD R1 OOD R2 completion L 1 = {bα} 0.654 0.605 L 3 = {a n b n } 0.415 0.623Table 14 : Human pilot study OOD accuracies: humans in our study performed better than chance, though they could not beat the LSTM on L 1 and the Transformer on L 3Our models and data sets are small scale and were designed to fit into an NVIDIA GeForce RTX 2080 Ti with 11GB VRAM, this guided our 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 5 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. 1). 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 : 1,455 GPU hours for 107 runs • L 2 : 707 GPU hours for 59 runs • L 3 : 301 GPU hours for 334 runs • L 4 : 269 GPU hours for 208 runs • L 5 : 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 of an NVIDIA A100 (PCIe version), which is 250W 4 . This amounts to approximately 750kWh, which is equivalent to the emission of 0.313 metric ton CO 2 , i.e., approximately 1290 kilometres driven by an average gasoline-powered passenger vehicle5 .In this section, we 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 -length sequences, where the p i are drawn from some set S. For example, S = {p i : is computable w.r.t. a UTM}.EQUATIONand the set of conditional factorizations consistent i.e., such conditionals that the joint equals the product of the conditionals, with themEQUATIONWe claim thatD J,N ⊂ D C,N . To see that D J,N ⊆ D C,N , note that the list {p i| (x k | x k-1 1 )} N k=1uniquely determines p i (x 1 , x 2 , ..., x N ) as the product of its elements. To see that the sets are not equal, consider the following example.Let X 1 and X 2 be two binary random variables. Let us define a probability mass function (pmf) p such that p(X 1 = 0) = 0 and p(X 1 = 0, X 2 = 0) = p(X 1 = 0, X 2 = 1) = 0. Now consider two sets of conditional pmfs q 1 and q 2 , satisfyingq 1 (X 2 = x | X 1 = 1) = q 2 (X 2 = x | X 1 = 1) = p(X 2 = x | X 1 = 1) = p(X 2 = x), q 1 (X 1 = 1) = q 2 (X 1 = 1) = 1, but q 1 (X 2 = 0 | X 1 = 0) = 1 and q 2 (X 2 = 0 | X 1 = 0) = 0.Due to the first two equations, both q 1 and q 2 are consistent with p, but they can differ on the zero-probability prompt X 1 = 0.Hence the set corresponding to D C,N is larger, and the extra elements correspond to the zeroprobability sequences under each p i . These are precisely the prompts on which we assess rule extrapolation.The lists of conditionals notation. In § 5, we distinguish between the joint probability representation p k := {p k (x N 1 )} and the lists of conditionals representation p i| . Let ϕ denote the mapping from lists of conditionals to the joint probabilities. Consider the set of pre-images of p k under ϕ, i.e., ϕ -1 (p k ), which has cardinality |ϕ -1 (p k )|. If this set has multiple elements, we can enumerate them as {p k|,j }|ϕ -1 (p k )| j=1 , with p k|,j := {p k,j (x k | x k-1 1 )} N k=1 }, where p k,j is the j th element of ϕ -1 (p k ). In our predictive p R , we list the p i| , where the index i is understood to loop over all pre-images:{p i| } i ≡ {{p k|,j } |ϕ -1 (p k )| j=1} k , where the enumerations over (k, j) are combined into an enumeration over i in a dovetail fashion. Index k loops over the joint probability distributions, and j loops through each of their pre-images. Note that this is a different enumeration than the one in the Solomonoff prior p S , where only the joint probabilities are enumerated (here with index k).This section has been adapted from Li and Vitányi [1997] , Hutter [2005] 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 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. 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 in Section 5. 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 be 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 to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a 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. B.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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are 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 of 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 was obtained from people whose asset is used. • At submission time, remember to 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 as details about compensation (if any)? Answer: [Yes] Justification:We included the details for our small pilot human questionnaire in Appx. B. 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to 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 SubjectsQuestion: 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 a 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, or equivalent, was necessart.The code for calculating chance levels is in chance_level_accuracies.ipynbAdopted from https://github.com/NX-AI/xlstm?tab=readme-ov-file# xlstm-language-modelhttps://www.nvidia.com/content/dam/en-zz/Solutions/Data-Center/a100/pdf/ nvidia-a100-datasheet.pdfhttps://www.epa.gov/energy/greenhouse-gas-equivalencies-calculatorSome works introduce the Solomonoff prior using monotone Turing machines[Hutter, 2011, Grau-Moya et al., 2024], but for our purposes, using prefix Turing machines is equivalent[Li and Vitányi, 1997]. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The article also has weaknesses:

- 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.
EDIT : The author's response helps to address this question.

- This is a fine, technically sound article that doesn't strike me as particularly high impact.
questions: questions: - This statement is just asserted but wasn't obvious to me and could use justification:
"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. 
EDIT : The author's response helps to address this question, and should be included in an updated paper.

typos
- "an Bob's enemy" pg. 7
limitations: limitations: This section was fine
paper_summary: paper_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.
strength_weakness: strength_weakness: - Few theoretical insights to justify the experimental results (see comments below)
- One single architecture tested for each model, and one single language for each category
questions: 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
hyper-parameters for the transformer, to exclude that such worse performance depends on the choice of the model?

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

* 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: limitations: See questions above.
paper_summary: paper_summary: # Problem:

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

Natural languages (NLs) prompts, i.e. real-world data, are acknowledged as too complex to systematically study OOD behaviours.

# Contributions:

Formal languages have obvious practical relevance for programming languages and formal mathematics, despite their dissimilarities with NLs.

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

The paper also investigates whether the emergent capabilities found in Transformer-based LMs are also present in simpler models?

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

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

Finally, 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\}$).
strength_weakness: strength_weakness: # Weaknesses:

## Originality:

Nothing to report, I find this paper as original as it gets.

## Quality:

WQ1: 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.

## Clarity:

WC1: 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.

WC2: missing ‘that’ or ‘which’ on ln94, possibly --> ‘formal languages _that_ are’ …

WC3: typos on ln208: ‘largest extent(64%)’ --> ‘..(66%)’ ; on ln209 : ‘model again due’ --> ‘model _is_ again due’

WC4: Figure 2 left : it is unclear what is represented given the range of the legend (from 0 to -15), please clarify?

Similarly, in Figure 2 right, I do not understand why is it a _sum_ of probabilities and not just the probability or likelihood, please clarify?

## Significance:

WS1: 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.

WS2: 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.
questions: questions: # Questions:

Please see above, but mainly:

- WC4

# General advice:

I 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: ## Limitations:

The paper acknowledges limitations in terms of external validity with respect to different architectures and different attention or encoding mechanism.

# POST REBUTTAL UPDATE :

Most 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'.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: I have several concerns:
1. 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?
2. 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: limitations: See weakness and questions.

Comments: title: Reply
Rebuttal
xLSTM results for the new context-sensitive language
comment: I thank the authors for their thorough rebuttal and their careful address of my concerns and recommendations.
I am very satisfied with it, and thus increase my overall rating to 8, and contribution and presentation ratings to 'good'.
I thank the authors for the effort put in the rebuttal and above all for the additional experiments, which strengthen the message of the paper. I have increased my score.
We extend the results plotted in Figure 6 (b) in the uploaded pdf and provide the performance of the xLSTM on the new, context-sensitive Dyck language. We conclude that the xLSTM has similar performance to Mamba

| Model                 | Test loss                 | ID R1                     | ID R2                     | OOD R1                    | OOD R2 $\tiny completion$ |
|--------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|------------------------------------|
| Linear | $4.013\scriptscriptstyle\pm 0.254$ | $0.000\scriptscriptstyle\pm 0.000$ | $0.000\scriptscriptstyle\pm 0.000$ | $0.000\scriptscriptstyle\pm 0.000$ | $1.000\scriptscriptstyle\pm 0.000$ |
| LSTM           | $0.645\scriptscriptstyle\pm 0.019$ | $0.981\scriptscriptstyle\pm 0.042$ | $0.956\scriptscriptstyle\pm 0.061$ | $1.000\scriptscriptstyle\pm 0.000$ | $0.894\scriptscriptstyle\pm 0.165$ |
| Mamba          | $0.675\scriptscriptstyle\pm 0.018$ | $0.745\scriptscriptstyle\pm 0.070$ | $0.807\scriptscriptstyle\pm 0.185$ | $0.684\scriptscriptstyle\pm 0.159$ | $0.810\scriptscriptstyle\pm 0.212$ |
| Transformer   | $0.640\scriptscriptstyle\pm 0.016$ | $1.000\scriptscriptstyle\pm 0.000$ | $1.000\scriptscriptstyle\pm 0.000$ | $0.980\scriptscriptstyle\pm 0.045$ | $0.973\scriptscriptstyle\pm 0.044$ |
| xLSTM          | $0.671\scriptscriptstyle\pm 0.021$ | $0.791\scriptscriptstyle\pm 0.179$ | $0.765\scriptscriptstyle\pm 0.155$ | $0.767\scriptscriptstyle\pm 0.158$ | $0.715\scriptscriptstyle\pm 0.121$ |
We are delighted that our answers addressed your concerns. We also appreciate your positive ratings of "excellent" for soundness, presentation and contribution. If possible, we would be grateful if you could consider raising the overall rating. If there are any further improvements we could make to achieve a higher score, we would be more than happy to address them.
Thanks for your reply! I am satisfied with the answers and I don't have any additional concerns or questions.
Thank you for the detailed reply and additional experiments, which I found helpful. I raised my score.