Rule Extrapolation in Language Models: A Study of Compositional Generalization on OOD Prompts

Title: Rule Extrapolation in Language Models: A Study of Compositional Generalization on OOD Prompts
Authors: Anna Mészáros, Szilvia Ujváry, Wieland Brendel, Patrik Reizinger, Ferenc Huszár
Published: 9th September 2024 (Monday) @ 22:36:35
Link: http://arxiv.org/abs/2409.13728v2

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 rule extrapolation. Rule extrapolation describes OOD scenarios, where the prompt violates at least one rule. We evaluate rule extrapolation in formal languages with varying complexity in linear and recurrent architectures, the Transformer, and state space models to understand the architectures’ influence on rule extrapolation. We also lay the first stones of a normative theory of rule extrapolation, inspired by the Solomonoff prior in algorithmic information theory.

---

Rule extrapolation is a form of compositional generalization: it studies OOD behavior of language models trained on formal languages defined by a logical conjunction of rules.

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.

1. Regular languages have rules that can be expressed via regular expressions, e.g., $L_1=\{b\alpha :\alpha$ contains even number of $a$ ‘s $\}$ and $L_2=\left\{b^n{a}^{2m}:n>0\right\}$.
2. 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=\left\{a^n{b}^n:n>0\right\},L_4=$ {sequences of nested parentheses and brackets}.
3. Context-sensitive grammars have rules that depend on the position in the sequence-we will use the standard example of $L_5=\left\{a^n{b}^n{c}^n:n>0\right\}$ and $L_6=$ {sequences of paired, but not necessarily nested parentheses and brackets }.
4. We omitted the recursively enumerable grammars similar to Deletang et al. [2022], as they require an infinite tape to simulate, which is impossible.