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.

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

• Transformer model size
• Sampling instead of greedy decoding
• Hyperparameter ablation
• A new context-sensitive language
• The xLSTM architecture

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

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

Sampling:

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.

We hope that our additional experiments have addressed the reviewer’s concerns.

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.

WQ1 (section 2.1 does not describe recursively enumerable languages)

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

SQ1 (Expand discussion about further impact)

Thank you for your feedback, we have expanded on this in our discussion, which we summarise here. While 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:

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

WC1 (New paragraph in the background)

We have included a new paragraph in the background section about statistical generalisation and identifiability to improve the readability of the paper.

WC2-3 (typos)

Thank you for pointing out the typos, we have corrected them.

WC4 (Figure 2)

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

WS2 (xLSTM)

We have carried out the suggested experiments with the xLSTM architecture. Due 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.

Hyperparameters for xLSTM:

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

 mlstm_block:
   mlstm:
     conv1d_kernel_size: 4
     qkv_proj_blocksize: 4
     num_heads: 4
 slstm_block:
   slstm:
     backend: cuda
     num_heads: 4
     conv1d_kernel_size: 4
     bias_init: powerlaw_blockdependent
   feedforward:
     proj_factor: 1.3
     act_fn: gelu
 num_blocks: 5
 xlstm_embedding_dim: 64
 slstm_at: [ 1 ]

WS1 (Parity Experiment)

Thank you for this suggestion. We thought about how to best incorporate parity into our framework, and we carried out the following experiment.

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.

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

General advice

Thank you for pointing out this unclarity in our narrative. We have changed the structure as suggested: section 5 now precedes section 4.1.

We would like to thank the reviewer again for their constructive questions and suggestions, which we hope we successfully addressed.

We thank the reviewer for their positive evaluation of our chosen topic, proposed theory and experiments. We address your questions below:

One single architecture tested for each model, and one single language for each category

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

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?

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

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.

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

At the end of page 4, in the definition of "Context-sensitive grammar" there is R2 twice, while the first one should be R1.

Thank you for pointing out the typo; we have corrected it.

We would like to thank the reviewer for their valuable feedback, we hope that the extra experiments and reframed insights address the reviewer’s concerns.

We thank the reviewer for their positive evaluation of our experiments and presentation. Please find below our replies to your concerns.

RE normative theory

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

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

RE simplicity of rules

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

RE impact of paper

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

While 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:

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

In 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, and in the uploaded document.

References

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

K. Ahuja and A. Mansouri. (Feb. 2024) On Provable Length and Compositional Generalization, URL http://arxiv.org/abs/2402.04875

Deletang, 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

Ruoss, 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

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