Characterizing Pattern Matching and Its Limits on Compositional Task Structures

## Abstract

Abstract Large language models excel at pattern matching, yet often fall short in systematic compositional generalization.
We propose the coverage principle: a data-centric framework showing that models relying primarily on pattern matching for compositional tasks cannot reliably generalize beyond substituting fragments that yield identical results when used in the same contexts.
We demonstrate that this framework has a strong predictive power for the generalization capabilities of Transformers.
First, we derive and empirically confirm that the training data required for two-hop generalization grows at least quadratically with the token set size, and the training data efficiency does not improve with 20x parameter scaling.
Second, for compositional tasks with path ambiguity where one variable affects the output through multiple computational paths, we show that Transformers learn context-dependent state representations that undermine both performance and interpretability.
Third, Chain-of-Thought supervision improves training data efficiency for multi-hop tasks but still struggles with path ambiguity.
Finally, we outline a mechanism-based taxonomy that distinguishes three ways neural networks can generalize: structure-based (bounded by coverage), property-based (leveraging algebraic invariances), and shared-operator (through function reuse). This conceptual lens contextualizes our results and highlights where new architectural ideas are needed to achieve systematic compositionally.
Overall, the coverage principle provides a unified lens for understanding compositional reasoning, and underscores the need for fundamental architectural or training innovations to achieve truly systematic compositionality. 1 1 1 All code and resources are available at: https://github.com/kaistAI/coverage-principle

### 1 Introduction

Figure: Figure 1: Left: In a two-hop task $(x_{1},x_{2},x_{3})\mapsto t$ with $t=f_{2}(f_{1}(x_{1},x_{2}),x_{3})$, two fragments $(x_{1},x_{2})$ and $(x_{1}^{\prime},x_{2}^{\prime})$ satisfying $f_{1}(x_{1},x_{2})=f_{1}(x_{1}^{\prime},x_{2}^{\prime})=b$ consistently yield the same final output when combined with the same context $x_{3}$, supporting their functional equivalence. Right: Among all possible inputs (few shown), we draw an edge between any two inputs that differ only by functionally equivalent fragments to form a substitution graph. Then, coverage is the set of observed inputs (highlighted as blue) and all inputs connected to them. The coverage principle states that a learner relying on pattern matching can reliably generalize only to inputs that are reachable from the observations by substituting functionally equivalent fragments.

Human generalization capability is often attributed to our ability to manipulate symbols *compositionally* [1, 2].
Despite the remarkable performance of Large Language Models (LLMs) [3, 4, 5, 6, 7, 8], our understanding of *how* they represent and manipulate compositional structures is still limited.
Meanwhile, a growing body of work points to the brittleness of LLMs in performing *systematic*(^2^22We refer to *systematicity* as an ability to generalize to unseen outcomes by exploiting their structural relations. For a more thorough discussion, see Fodor and Pylyshyn [9], Marcus [10], and Szabó [11].) compositional reasoning [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25].
These observations suggest that LLMs succeed primarily through pattern matching, i.e., by exploiting surface-level statistical correlations between input fragments and outputs, rather than systematic compositional reasoning.
However, prior analyses of the pattern-matching behavior remain largely observational and task-specific, leaving us without a unified framework to predict when they will succeed or fail.

We show that Transformers’ [26] generalization on synthetic compositional tasks is predictable through a unified framework grounded in one observation: Transformers generalize by utilizing functionally equivalent fragments supported by input-output relations.
This insight allows us to move beyond observing success or failure cases to systematically predicting generalization boundaries.
To this end, we first formalize the concept of functional equivalence, where two fragments (i.e., components of input sequences) are regarded as equivalent when they yield identical results in all shared contexts observed in the training data. Then, we introduce coverage, the set of inputs reachable from training data by substituting functionally equivalent fragments.
Finally, we propose the coverage principle, which states that coverage is a necessary condition for compositional generalization, i.e., model predictions become unreliable beyond this fundamental boundary, as long as the only generalization mechanism is pattern matching.

From this conceptual formulation, we derive specific predictions about generalization in Transformers. First, we derive and empirically confirm that reliable generalization on a two-hop reasoning task requires training data to scale at least quadratically with the token set size. Remarkably, our experiments suggest that this scaling relationship remains invariant even for 20x larger model, underscoring that the limitation is inherent to data properties rather than model capacity.

Second, our framework also predicts specific complications in tasks with path ambiguities, where the same variable influences outputs through multiple computational paths.
We show that Transformers cannot form unified representations of identical intermediate states in such cases, instead developing context-dependent state representations that fragment across different paths.
This degrades both performance and interpretability, explaining why seemingly simple compositional tasks can remain challenging even for large models.

Third, while Chain-of-Thought (CoT) supervision [27, 28] improves data efficiency by ‘flattening’ tasks into sequences of single-hop problems, our analysis reveals a fundamental limitation: CoT-trained models still cannot resolve path ambiguities without showing nearly all possible in-domain combinations. This finding provides insights into understanding the Transformers’ failure modes in complex reasoning tasks with path ambiguities (e.g., planning [29, 30, 31]).

We place these findings within a broader, mechanism-based taxonomy that distinguishes three routes to generalization:
(i) structure-based generalization via functional equivalence (the focus of this paper),
(ii) property-based generalization that exploits algebraic invariances of individual primitive functions, and
(iii) shared-operator generalization that reuses the same computation across positions.
This taxonomy clarifies how certain model behaviours that occur *outside* the coverage region can arise from Type-II or Type-III mechanisms, providing a conceptual framework for analysing diverse sources of generalization.

Overall, the coverage principle offers a unified conceptual framework providing valuable insights into compositional generalization, highlighting how compositional reasoning and its mechanistic interpretation remain inherently bounded by coverage limitations. This underscores the need for architectural or training innovations to achieve truly systematic generalization in neural networks.

### 2 Related work

##### Compositional generalization and systematicity

Since Fodor and Pylyshyn [9] posed the systematicity challenge, arguing connectionist systems inherently lack symbolic structural capabilities, understanding how neural networks might achieve compositional reasoning has remained a persistent research question [32, 33, 34, 35, 36, 37, 38, 39, 10].
Central to this debate is the variable binding problem, how neural networks can flexibly associate variables with values across contexts [40, 41, 42], which Marcus [37] argues as the fundamental limitation of modern connectionist approaches.
Despite AI advances, a growing body of work reveals limitations in neural networks’ compositional capabilities [14, 43, 18, 44, 45, 20, 46, 15, 21, 22, 23, 24, 47, 42].
Dziri et al. [17] observe that Transformers perform linearized subgraph matching to solve compositional tasks, but leave open when and why it occurs.
Our coverage principle addresses this gap by formally demarcating what pattern matching models can achieve without true variable binding, showing both the possibilities and fundamental limitations of pattern matching-based approaches through data-based preconditions.
This aligns with empirical findings of Andreas [48] and Auersperger and Pecina [49], where compositional data augmentation that implicitly expands coverage significantly improves generalization.
Our derived power-law scaling relationship between token set size and required dataset size contributes to scaling laws literature [50, 51], but differs by characterizing a data requirement invariant to model size for compositional tasks.
Unlike prior disentanglement work [52, 53, 54, 55] which focuss on latent factors, our data-centric view identifies fundamental boundary conditions for pattern-based generalization.
The coverage principle thus complements recent architectural or training innovations [56, 57, 58, 59, 60] by showing what any pattern matching approach must overcome to achieve true systematicity.

##### Mechanistic interpretability

Mechanistic interpretability studies aim to understand how submechanisms implement models’ behaviors [61, 62, 63, 64].
Recent work traces how Transformer components coordinate on compositional tasks [65, 66, 67, 68, 69].
Wang et al. [19] demonstrate that in-domain compositional generalization emerges through grokking, but do not identify necessary data conditions for such emergence.
Our data-centric framework complements this optimization-centric view by pinpointing when generalizing circuits can exist: only when training data provides sufficient evidence of functional equivalence, essentially formalizing when the pattern matching mechanisms that Fodor and Pylyshyn [9] critique can succeed or must fail.
Our findings also explain why standard interpretability techniques like logit lens [70, 71] may fail to identify compositional structure in models trained on tasks with path ambiguities.

### 3 A formulation of the coverage principle

We now develop a formal framework of the coverage principle. We first provide an intuitive illustration with a two-hop compositional task, then generalize the intuitions to formalize the coverage principle for more general compositional tasks.

Imagine a learner(^3^33By “learner”, we mean any system that learns from data (e.g., neural networks).) observing input-output pairs determined by a function $f:{\mathcal{X}}^{3}\to{\mathcal{X}}$.
The input ${\bm{x}}=(x_{1},x_{2},x_{3})\in{\mathcal{X}}^{3}$ is a sequence of three discrete tokens and the output is a single token, where each token is sampled from a finite set ${\mathcal{X}}$.(^4^44For brevity, we use a shared token set ${\mathcal{X}}$. Position-specific domains ${\mathcal{X}}_{i}$ can be embedded as subsets of an enlarged token set $\tilde{{\mathcal{X}}}={\mathcal{X}}_{1}\cup{\mathcal{X}}_{2}\cup{\mathcal{X}}_ {3}$ without loss of generality.)
Being unknown to the learner, let $f$ be a function that can be factorized as the composition of two primitive functions as $f({\bm{x}})=f_{2}(f_{1}(x_{1},x_{2}),x_{3})$, where $f_{1}:{\mathcal{X}}^{2}\to{\mathcal{X}}$ and $f_{2}:{\mathcal{X}}^{2}\to{\mathcal{X}}$, as illustrated in [Fig. 2(a)](https://arxiv.org/html/2505.20278v1#S4.F2.sf1).
How can the learner generalize by only seeing the input-output pairs?

Our key intuition is that a learner exploits the compositional structure only when observations show that two fragments behave identically. For instance, assume that $f_{1}(x_{1},x_{2})=f_{1}(x_{1}^{\prime},x_{2}^{\prime})=b$ for $(x_{1},x_{2}),(x_{1}^{\prime},x_{2}^{\prime})\in{\mathcal{X}}^{2}$.
From the underlying structure, these fragments are functionally equivalent, i.e., substituting one for the other never changes the output.
If observations consistently support their equivalence, i.e., $f(x_{1},x_{2},x_{3})=f(x_{1}^{\prime},x_{2}^{\prime},x_{3})$ for observed $x_{3}$ values, this equivalence can be *supported* ([Fig. 1](https://arxiv.org/html/2505.20278v1#S1.F1) (Left)).
Intuitively, the learner would be able to harness this equivalence to generalize to an unseen input $(x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime\prime})$, provided the learner has seen $f(x_{1},x_{2},x_{3}^{\prime\prime})$.

In short, the learner can utilize the observed functional equivalence to correctly infer the output of an unseen input, if it can reach an observed input by *safe substitutions* supported by observations ([Fig. 1](https://arxiv.org/html/2505.20278v1#S1.F1) (Right)).
Coverage is a set of such inputs that are reachable from an observed input through chains of functionally equivalent substitutions.
The essence of our framework, the coverage principle, is that a learner can only generalize inside the coverage when the only source of compositional generalization is the observation and utilization of functional equivalence.

We now formalize these concepts for an arbitrary fixed-length task with an arbitrary set of observations.
We restrict our attention to single-token prediction tasks defined as a deterministic mapping $f:{\mathcal{X}}^{n}\to{\mathcal{X}}$, where ${\mathcal{X}}$ is a finite set of tokens.
We also consider a fixed observation set $D\subset{\mathcal{X}}^{n}$, a collection of inputs that are allowed to be observed by the learner.
Write ${\bm{x}}=(x_{1},\dots,x_{n})\in{\mathcal{X}}^{n}$ and, for a subset
$I\subset[n]:=\{1,\dots,n\}$, let ${\bm{x}}_{I}:=(x_{i})_{i\in I}$ be a subsequence of ${\bm{x}}$.
The first step is to formalize what it means for two subsequences to be functionally equivalent.

###### Definition 3.1 (Functional $k$ -equivalence) .

Fix a nonempty proper subset of indices $I\subsetneq[n]$.
Given a pair of subsequences ${\bm{a}},{\bm{a}}^{\prime}\in{\mathcal{X}}^{|I|}$, we say a pair of inputs $\left\{{\bm{x}},{\bm{x}}^{\prime}\right\}\subset D$ to be an *$I$-co-occurrence* of ${\bm{a}}$ and ${\bm{a}}^{\prime}$ in $D$ if it satisfies ${\bm{x}}_{I}={\bm{a}}$, ${\bm{x}}^{\prime}_{I}={\bm{a}}^{\prime}$, and ${\bm{x}}_{[n]\setminus I}={\bm{x}}^{\prime}_{[n]\setminus I}$.
Also, we say ${\bm{a}}$ and ${\bm{a}}^{\prime}$ are *functionally $k$-equivalent* at $I$ in $D$, denoted by ${\bm{a}}\equiv^{I}_{D}{\bm{a}}^{\prime}$, if it satisfies:

- 1.
(Sufficiency of co-occurrences.) There are $k$ or more distinct $I$-co-occurrences of ${\bm{a}}$ and ${\bm{a}}^{\prime}$ in $D$;
- 2.
(Consistency.) Every $I$-co-occurrence $\left\{{\bm{x}},{\bm{x}}^{\prime}\right\}$ of ${\bm{a}}$ and ${\bm{a}}^{\prime}$ in $D$ satisfies $f({\bm{x}})=f({\bm{x}}^{\prime})$.

In other words, two subsequences are functionally $k$-equivalent if they behave identically in the same contexts at least $k$ times.
The hyperparameter $k$ represents the strength of evidence required to establish functional equivalence between two subsequences.
The minimum value $k=1$ corresponds to the weakest form of evidence, meaning a single shared context is sufficient to establish equivalence, whereas higher values of $k$ demand more robust evidence.

Next, we ask: which inputs are
reachable from observed data utilizing functional equivalence?
To formalize this, we define the substitution graph:
Let ${\mathcal{G}}_{D,k}=(V,E)$ be an undirected graph with a vertex set $V={\mathcal{X}}^{n}$ of all possible inputs.
Two vertices ${\bm{x}},{\bm{x}}^{\prime}\in V$ are connected with an edge in $E$ if and only if there exists an index set $I\subset[n]$ such that $\left\{{\bm{x}},{\bm{x}}^{\prime}\right\}$ is an $I$-co-occurrence (in $V$) of a pair of functionally $k$-equivalent sequences at $I$ in $D$.
With this substitution graph ${\mathcal{G}}_{D,k}$, we formally define the $k$-coverage as a set of inputs which are connected(^5^55For an undirected graph ${\mathcal{G}}$, two vertices $u,v$ are connected if ${\mathcal{G}}$ contains a path between $u$ and $v$.) to at least one observed input as follows:

###### Definition 3.2 ( $k$ -coverage) .

The *$k$-coverage* of $D$, denoted by $\mathrm{Cover}_{k}(D)$, is the set of all inputs in ${\mathcal{X}}^{n}$ that is connected to an input in $D$ on the substitution graph ${\mathcal{G}}_{D,k}$.

Note that the notion of coverage is a stricter condition of the conventional definition of in-domain, which is obtained by random train/test split [19] or taking combinations of observed internal computations [17].
We also emphasize that coverage is a property of a dataset and is independent of model architectures and learning algorithms.
Now, we formally phrase the coverage principle:

###### Claim 3.3 (Coverage principle) .

Let a learner output $\hat{f}$ that is *consistent* with the training
set $D$. If generalization is derived solely from observed functional $k$-equivalences and ${\bm{x}}\notin\mathrm{Cover}_{k}(D)$, the value
$\hat{f}({\bm{x}})$ is unconstrained by $D$.

This establishes a fundamental boundary: no learner can reliably generalize beyond the coverage as long as the only source of the generalization is functional equivalence. In [Sec. 5.1](https://arxiv.org/html/2505.20278v1#S5.SS1), we show that Transformers indeed fail to generalize beyond coverage when our random mapping dataset construction isolates functional equivalence as the sole generalization source.
However, deeper insights come from asking when generalization success occurs in practice.
While theory suggests that deep learning methods implicitly favor simpler solutions [72, 73, 74], which may involve leveraging functional equivalence, we still lack a systematic picture of how task structure, dataset, and model size interact to determine when such solutions emerge.
We study this through experiments in [Sec. 5](https://arxiv.org/html/2505.20278v1#S5).

###### Definition 3.1 (Functional k 𝑘 k italic_k -equivalence) .

###### Definition 3.2 ( k 𝑘 k italic_k -coverage) .

###### Claim 3.3 (Coverage principle) .

### 4 Experimental setup

Figure: (a) 2-Hop

##### Dataset construction

We construct four synthetic compositional tasks: 2-Hop, Parallel 2-Hop, 3-Hop, and Non-tree ([Fig. 2](https://arxiv.org/html/2505.20278v1#S4.F2)).
We create random mappings from the product space of a token set to control generalization sources not attributable to compositional structures (i.e., commutativity).(^6^66Such *external* generalization sources will be discussed in [Sec. 7](https://arxiv.org/html/2505.20278v1#S7) and [App. H](https://arxiv.org/html/2505.20278v1#A8).)
We explain the dataset construction process using 2-Hop task ([Fig. 2(a)](https://arxiv.org/html/2505.20278v1#S4.F2.sf1)), $(x_{1},x_{2},x_{3})\mapsto t$ with $t=f_{2}(f_{1}(x_{1},x_{2}),x_{3})$, as an example.
We construct training datasets by defining a token set with size $|{\mathcal{X}}|$, and creating two random maps for the primitive functions $f_{1}:{\mathcal{X}}^{2}\to{\mathcal{X}}$ and $f_{2}:{\mathcal{X}}^{2}\to{\mathcal{X}}$. We mark a fraction $p_{\mathrm{seen}}=0.7$ of each function’s domain as ‘seen’, gather all possible combinations where both functions are applied to inputs from their seen domains, and uniformly sample $N$ examples to form a training dataset. See [Sec. B.1](https://arxiv.org/html/2505.20278v1#A2.SS1) for more details of the dataset construction process.

##### Training & evaluation

Following Wang et al. [19], we train randomly initialized GPT-2 [75] models with 8 layers, 12 heads, and 768 dimensions (see [Sec. B.2](https://arxiv.org/html/2505.20278v1#A2.SS2) for details).
We construct two evaluation sets, each with 2,000 instances: (1) In-Domain (ID) Test Set : all primitive function applications (e.g., $f_{1}(x_{1},x_{2})$ and $f_{2}(b,x_{2})$ in 2-Hop task) are observed during training, but the specific combination was unseen.
(2) Out-of-Domain (OOD) Test Set: at least one primitive function application is never observed during training.

### 5 Results

#### 5.1 Predictive power of k 𝑘 k italic_k -coverage on Transformer’s compositional generalization

Figure: Figure 3: Left: Percentage of covered ID data depending on $k$ values and dataset size ($N$), for 2-Hop task ($|{\mathcal{X}}|=50$). Right: Test accuracy depending on $k$-cutoff values for 2-Hop task ($|{\mathcal{X}}|$=50, $N$=10k). Each line represents a different training checkpoint. Note that OOD accuracy remains at chance level (=1/50) regardless of training time. The bars below show the number of test data for each $k$-cutoff value.
Refer to caption: x1.png

We now empirically validate the predictive power of the coverage principle by quantifying the correlation between $k$-coverage and model generalization performance.
To this end, we implement and release a task-agnostic coverage determination algorithm (see [App. C](https://arxiv.org/html/2505.20278v1#A3) for implementation details) that can be applied to diverse compositional structures. Then, we analyze what fraction of ID test data of 2-Hop task with $|{\mathcal{X}}|=50$ lies inside $k$-coverage, depending on $k$ and dataset size $N$.
[Fig. 3](https://arxiv.org/html/2505.20278v1#S5.F3) (Left) shows that at $N=5$k, every ID test example is already covered with minimal evidence ($k=1$).

Ideally, a single witness of functional equivalence could suffice.
However, experiments show that such minimal coverage alone is insufficient for efficient generalization in practice.
To demonstrate this, we define a sample’s $k$-cutoff as the lowest $k$ for which an input lies in $k$-coverage, measuring the strength of evidence for functional equivalence. For example, a $k$-cutoff of 3 means that an example is inside coverage with $k=3$ but not with $k=4$. For 2-Hop dataset with $N=10$k, we classify each ID test instance according to its $k$-cutoff, and track accuracy development for each group across 50k training epochs.
As shown in [Fig. 3](https://arxiv.org/html/2505.20278v1#S5.F3) (Right), generalization success shows a strong relationship with $k$-cutoff values. Test data with low $k$-cutoff values show delayed improvement even after extensive training, while examples with stronger evidence generalize much faster. Notably, OOD test examples (outside coverage) remain at chance-level ($1/50=0.02$) throughout training, empirically validating our coverage principle.

These results yield two important insights. First, successful generalization in practice requires *robust* coverage so the model can confidently identify and utilize functional equivalence relationships. The $k$ parameter effectively quantifies this evidence strength, directly impacting generalization speed and reliability.
Second, while our experiments use uniformly distributed data, the coverage principle explains why models struggle with generalizing long-tail distribution in imbalanced real-world data [76, 77, 78]. Rare combinations naturally receive limited functional equivalence evidence (low $k$), placing them effectively outside practical coverage, despite technically being in-distribution.

#### 5.2 The clustering of latent representation drives generalization on coverage

Figure: Figure 4: Left: Heatmap of Intra-Inter Cosine Gap (IICG) across layers and positions, sliced by $k$-cutoff. Higher IICG values indicate stronger clustering of representations that share the same intermediate state. The positions with the highest IICG values are marked with squares. Right: PCA visualization of latent representations at position $x_{2}$ and layer 3. Datapoints are classified by their intermediate states $b=f_{1}(x_{1},x_{2})$.
Refer to caption: x3.png

Next, we investigate how the model internally represents functional equivalence for $k$-covered inputs. Specifically, we inspect a GPT-2 trained on 2-Hop task ($|{\mathcal{X}}|=50$, $N=10\text{k}$) for 50k epochs (corresponding to the yellow line in [Fig. 3](https://arxiv.org/html/2505.20278v1#S5.F3) (Right)).(^7^77Analyses for varying factors including task structures, entity set size ($|{\mathcal{X}}|$), dataset size ($N$), and training steps give consistent results; see [App. D](https://arxiv.org/html/2505.20278v1#A4).)
We observe that when a model successfully generalizes to ID test data, it maps functionally equivalent components into tight latent clusters, thereby encoding the equivalence relationships needed for compositional generalization.

To quantify this representation clustering phenomenon, we develop a metric that captures how distinctly the model separates functionally equivalent fragments from others. Specifically, we measure the difference between the average pairwise cosine similarity of latent vectors that share the same intermediate state $b=f_{1}(x_{1},x_{2})$ ($\overline{\cos}_{\text{intra}}$), and those that do not ($\overline{\cos}_{\text{inter}}$), for each position and layer of the model. We term this difference the Intra–Inter Cosine Gap
$\text{IICG}=\overline{\cos}_{\text{intra}}-\overline{\cos}_{\text{inter}}$,
where higher values indicate stronger within-group clustering relative to between-group separation.
[Fig. 4](https://arxiv.org/html/2505.20278v1#S5.F4) (Left) reveals a clear relationship: higher $k$-cutoff values yield higher IICG scores at certain positions, indicating that stronger functional equivalence evidence leads to more coherent internal representations.
Critically, OOD examples show no clustering pattern at all, since they lack any functional equivalence evidence in the training data, as predicted by the coverage principle.
The PCA visualization at position $x_{2}$ and layer 3 (Right) shows this trend visually.
We verify that the representation clusters play a causal role in ID generalization with causal tracing [67, 66], a widely used mechanistic interpretability technique to identify Transformer circuits (see [Fig. 8](https://arxiv.org/html/2505.20278v1#A4.F8) in [App. D](https://arxiv.org/html/2505.20278v1#A4)).

Our findings extend the insights of Wang et al. [19] in several ways. First, we demonstrate that unified circuit formation is driven by functional equivalence evidence in the training data, not by explicit exposure to intermediate computation steps. Consequently, out-of-coverage inputs lack these unified circuits by construction, explaining their systematic failure on OOD examples.
Moreover, we find that these clustered representations are not necessarily aligned with vocabulary embeddings, implying that standard interpretability methods like logit lens [70] may fail to detect these functional equivalence representations despite their presence. See [App. I](https://arxiv.org/html/2505.20278v1#A9) for a detailed analysis.

#### 5.3 When does coverage lead to full ID generalization? A power-law lower bound

Figure: Figure 5: Left: Log-log plot of measured $\hat{N}_{\mathrm{req}}$ vs. token set size ($|{\mathcal{X}}|$) across three compositional tasks. The slope $c$ corresponds to the empirical power-law scaling exponent. Omitted points for 3-Hop are due to prohibitively large dataset requirements. Right: Power-law scaling remains invariant across GPT-2 model sizes (68M to 1.5B parameters) for 2-Hop task. $R^{2}>0.99$ for all linear fitting.
Refer to caption: x5.png

Our analysis of $k$-coverage and representation clustering demonstrates that stronger functional equivalence evidence leads to better generalization. A natural follow-up question arises: How large should the training set be to enable full generalization on all ID test data?
Intuitively, this requires the training set to support the functional equivalence of *every* pair of inputs that shares the same intermediate state $b$.
Formally, for a 2-Hop task we need
$(x_{1},x_{2})\equiv^{\{1,2\}}_{D}(x^{\prime}_{1},x^{\prime}_{2})$
whenever
$f_{1}(x_{1},x_{2})=f_{1}(x^{\prime}_{1},x^{\prime}_{2})$.
Assuming a learner requires at least $k$ distinct pairs of evidence to establish functional equivalence of two fragments, how does the required dataset size scale with the token set size $|{\mathcal{X}}|$?
In practical terms, this question addresses how much data is fundamentally needed for compositional generalization, which is central to understanding data scaling requirements for compositional tasks. For 2-Hop task, we derive the following result (full derivation in [App. E](https://arxiv.org/html/2505.20278v1#A5)):

###### Result 5.1 (Power-law lower bound) .

Let $f:{\mathcal{X}}^{3}\!\to\!{\mathcal{X}}$ be a 2-Hop composition.
Assume a learner recognizes functional equivalence of two subsequences only after observing them in at least $k$ distinct pairs of evidence (i.e., functionally $k$-equivalent).(^8^88Note that this assumption is equivalent to modeling [Fig. 3](https://arxiv.org/html/2505.20278v1#S5.F3) (Right) as a step function.)
Let $N_{\text{req}}(|{\mathcal{X}}|,k)$ be the smallest training dataset size that enables complete generalization to ID examples under this evidence threshold.
Then, up to poly-logarithmic factors in $|{\mathcal{X}}|$,
$N_{\text{req}}(|{\mathcal{X}}|,k)=\tilde{\Omega}\bigl{(}|{\mathcal{X}}|^{\,
\alpha(k)}\bigr{)},\text{where}\;\alpha(k)=2.5-\frac{0.5}{k}.$

[Res. 5.1](https://arxiv.org/html/2505.20278v1#S5.Thmtheorem1) predicts that a learner relying on pattern matching requires training dataset size scaling at least quadratically with respect to the token set size, to fully generalize on ID test data.
To empirically confirm this, we define a practical threshold $\hat{N}_{\mathrm{req}}$ to estimate $N_{\mathrm{req}}(|{\mathcal{X}}|,k)$, as a minimal amount of training data required to exceed ID accuracy of 0.99 within 100 epochs after reaching the same level on training data.(^9^99See [App. F](https://arxiv.org/html/2505.20278v1#A6) measurement details.)
[Fig. 5](https://arxiv.org/html/2505.20278v1#S5.F5) (Left) shows the measured power-law exponents for $\hat{N}_{\text{req}}$ vs. $|{\mathcal{X}}|$ across different task structures. The measured exponent for 2-Hop ($c=2.26$) aligns well with our theoretical predictions of at least quadratic scaling. Although we derive the theoretical bound only for 2-Hop, we observe clear power-law relationships for more complex structures as well. The higher exponents for Parallel-2-Hop ($c=2.43$) and 3-Hop ($c=2.58$) tasks suggest that extra computational steps essentially add another dimension of relationships that require robust coverage, driving the steeper power-law scaling.

Strikingly, these exponents remain invariant across three different GPT-2 model sizes spanning a 20x range in parameters (from 68M to 1.5B) for all three tasks ([Fig. 5](https://arxiv.org/html/2505.20278v1#S5.F5) (Right) and [Tab. 2](https://arxiv.org/html/2505.20278v1#A6.T2) in [App. F](https://arxiv.org/html/2505.20278v1#A6)). This supports that the scaling relationship is primarily determined by data properties rather than model capacity, reinforcing our framework’s data-centric perspective.
The observed scaling relationships are robust across different hyperparameters (weight decay and learning rate) and empirical decision criteria for $\hat{N}_{\mathrm{req}}$ (see [App. F](https://arxiv.org/html/2505.20278v1#A6)).
Overall, these results suggest that compositional generalization in Transformers requires dataset sizes scaling as a power-law with token set size. This has significant implications for how we approach complex reasoning tasks, suggesting that data curation strategies informed by coverage considerations may be more effective than raw parameter scaling.

###### Result 5.1 (Power-law lower bound) .

#### 5.4 Path ambiguity hinders generalization and interpretability in Transformers

Figure: Figure 6: Left: In Non-tree task, the coverage principle predicts that representations of input subsequences with the same intermediate state $b=f_{1}(x_{1},x_{2})$ split into multiple context-dependent state representations, conditioned on $x_{2}$ value. Middle: ID test accuracy after standard training (100 epochs post training accuracy$>$0.99), showing Non-tree task significantly underperforms 2-Hop task ($|{\mathcal{X}}|=50$). Right: IICG heatmap from a model that achieved near-perfect ID accuracy (0.96) after extended training (36k epochs, $|{\mathcal{X}}|=50$, $N=50\text{k}$).
Refer to caption: x7.png

Many real-world reasoning tasks involve computational structures where a single variable affects the output through multiple paths, creating what we call *path ambiguity*.
Our framework predicts that in such cases, Transformers struggle with forming unified representations of intermediate states that are theoretically equivalent, instead developing *context-dependent state representations* that vary based on the input context. In this section, we analyze Non-tree task ([Fig. 2(d)](https://arxiv.org/html/2505.20278v1#S4.F2.sf4)) as a case study, where $x_{2}$ affects the output through two paths: as input to $f_{1}$ and directly to $f_{2}$.
Following the definition of functional equivalence ([Def. 3.1](https://arxiv.org/html/2505.20278v1#S3.Thmtheorem1)), this path ambiguity prevents the model from establishing the functional equivalence of two subsequences $(x_{1},x_{2})$ and $(x_{1}^{\prime},x_{2}^{\prime})$ that produce the same intermediate state $b$, unless they also share the same $x_{2}$ value ($x_{2}=x_{2}^{\prime}$).
Consequently, the model creates context-dependent state representations rather than unifying them to represent true intermediate state $b$, as illustrated in [Fig. 6](https://arxiv.org/html/2505.20278v1#S5.F6) (Left).

In consequence, the path ambiguity hinders both generalization performance and efficiency, as the model must establish functional equivalence for each $x_{2}$-conditioned equivalent pair.
[Fig. 6](https://arxiv.org/html/2505.20278v1#S5.F6) (Middle) shows that GPT-2 can fully generalize on ID test set of 2-Hop task within a reasonable time with increasing data size, but fails with Non-tree task, even provided with a near-exhaustive amount of possible ID combinations as training data.(^10^1010For $|\mathcal{X}|=50$ and $p_{\text{seen}}=0.7$, our largest run ($N=50\text{k}$) includes virtually the entire domain ($\approx 0.7^{2}\!\times|\mathcal{X}|^{3}\;\approx\;61\text{k}$ distinct ID triples).)
Notably, scaling to 1.5B parameters does not show significant improvement in the performance ([Fig. 17](https://arxiv.org/html/2505.20278v1#A7.F17) in [App. G](https://arxiv.org/html/2505.20278v1#A7)).
Extremely prolonged training (36k epochs) with near-exhaustive ID combinations eventually achieves ID accuracy of 0.96. However, IICG analysis reveals no evidence of a unified intermediate state representation formation, with near-zero IICG scores when grouping by the intermediate state value $b$ ([Fig. 6](https://arxiv.org/html/2505.20278v1#S5.F6) (Right)).
In contrast, grouping by $x_{2}$-conditioned intermediate state ($(b,x_{2})$) leads to high IICG scores, suggesting the formation of context-dependent state representations.

This context-dependence raises an interpretability concern, as standard linear probing-based techniques like logit lens [70, 71] would not reliably identify intermediate states. Moreover, our analysis provides insights into why LLMs fall short in planning tasks [29, 31, 30], as planning often requires correct tracking of intermediate states, which can influence outcomes through multiple paths.

#### 5.5 CoT supervision improves data efficiency but still struggles with path ambiguity

Figure: Figure 7: Left: Power-law scaling of required dataset size vs. token set size for tasks with CoT supervision. $R^{2}>0.98$ for all linear fits. Middle: Comparison of ID test Accuracy of Non-tree task ($|{\mathcal{X}}|=50$) with and without CoT supervision (100 epochs post training accuracy$>$0.99). Right: IICG score comparison for Non-tree and 2-Hop task with CoT supervision ($|\mathcal{X}|=50$, $N=10\text{k}$). The scores are measured at each layer of intermediate state position $b$, based on two grouping strategies: $b$ and $(b,x_{2})$. Models are trained for 100 epochs after reaching training accuracy$>$0.99.
Refer to caption: x9.png

CoT supervision [27, 28] dramatically improves performance on multi-step reasoning tasks.
We investigate how CoT interacts with the coverage principle and whether it can address the challenges observed in Sections [5.3](https://arxiv.org/html/2505.20278v1#S5.SS3) and [5.4](https://arxiv.org/html/2505.20278v1#S5.SS4).
Specifically, we train models to sequentially generate intermediate states before final outputs, making 2-Hop a two-token prediction task: $(x_{1},x_{2},x_{3})\mapsto(b,t)$, for example.
This explicit supervision substantially improves data efficiency ([Fig. 7](https://arxiv.org/html/2505.20278v1#S5.F7) (Left)), with the power-law exponent dropping from 2.58 to 1.76 in 3-Hop task, aligning with previous studies on the sample efficiency of CoT [79, 80, 81].
Remarkably, the scaling exponents measured for 2-Hop, 3-Hop, and even 5-Hop tasks become nearly identical with CoT supervision.
We interpret this as CoT effectively ‘flattening’ multi-hop structures into sequences of single-hop tasks, reducing the compounding data requirements of deeper compositional structures.

However, we find models trained with CoT supervision still struggle with the path ambiguity in Non-tree task.
Despite showing improvements with CoT supervision, the models fail to achieve perfect ID generalization under the same training conditions that yield perfect performance in 2-Hop task ([Fig. 7](https://arxiv.org/html/2505.20278v1#S5.F7) (Middle).
IICG analysis (Right) reveals that the model’s representations remain partially context-dependent.
For 2-Hop task, the representations cluster purely by intermediate states $b$, as indicated by the result that IICG measurement with $x_{2}$-conditioned states does not significantly shift the curve. In contrast, the IICG score for Non-tree task is significantly elevated at every layer with the same conditioning, suggesting the absence of disentangled state representation inside the model.
We hypothesize this arises since CoT supervision does not give enough evidence that different $(x_{1},x_{2})$ pairs sharing the same $b$ should yield identical second-step outputs, as functional equivalence holds only when $x_{2}=x_{2}^{\prime}$.
Hence, while CoT supervision helps with sequential computation by breaking down multi-hop structures, it may partially inherit the limitations on handling tasks with path ambiguities we describe in [Sec. 5.4](https://arxiv.org/html/2505.20278v1#S5.SS4).
Our analysis likely explains why LLMs struggle with complex planning tasks even when using CoT techniques and massive training data [82].

### 6 A taxonomy for understanding generalization mechanisms

Our coverage analysis reveals fundamental limits of pattern matching for compositional generalization.
This raises a broader question: What other mechanisms allow neural networks to go beyond coverage boundaries?
We sketch a preliminary taxonomy that distinguishes three complementary mechanisms and offers hypotheses about why models sometimes succeed beyond coverage(^11^1111The taxonomy is not exhaustive; Appendix [H](https://arxiv.org/html/2505.20278v1#A8) details limitations and open questions.).

Type-I: Structure-based generalization
occurs when models identify and utilize functionally equivalent components based on how primitive functions are composed. This is precisely what we formalize through the coverage principle: models learn that different input fragments yield identical results in shared contexts, enabling generalization to new fragment combinations. Crucially, this generalization remains bounded by coverage, and reliable generalization fails without sufficient functional equivalence evidence. Type-I describes the ceiling of pattern matching without explicit variable binding.

Type-II: Function property-based generalization exploits intrinsic properties of individual primitive functions (e.g.,
algebraic invariances such as commutativity),
group-theoretic structure in modular arithmetic [63],
or *input irrelevance*, where certain arguments never affect the output (e.g., $f(x_{1},x_{2})=f(x_{1})$ even when distractor $x_{2}$ is present [81]). Unlike Type-I, this can transcend coverage limitations by leveraging properties that hold across all inputs of a primitive.
The Reversal Curse exemplifies the layered nature of compositional challenges across multiple generalization types. The coverage principle (Type-I) explains the fundamental failure: training on “$A$ is $B$” provides no functional equivalence evidence for “$B$ is $A^{-1}$”. Property-based approaches like bidirectional training partially succeed [83] by exploiting relationship invertibility (Type-II), using architectural modifications to learn inverse mappings from the same training data. However, recent evidence [42] shows that models still struggle once entities switch syntactic roles, indicating a remaining challenge in variable binding.(^12^1212See [42] for controlled concept–surface dissociation experiments.)

Type-III: Shared-operator generalization emerges through reuse of identical primitive functions across computational positions (e.g., when $f_{1}=f_{2}$). Recurrent architectures [84] exemplify this through weight sharing across time steps, enabling processing of variable-length sequences [85]. In Transformers, inductive biases towards reuse of the same computation through parameter sharing [86, 87, 19] can improve generalization on compositional tasks beyond coverage. We interpret this mechanism as exploiting structural repetition without requiring Type-II’s algebraic property understanding.

##### Distinguishing mechanisms from phenomena

Prior categorizations focus on observed phenomena, for example, “systematic” versus “mix-and-match” [12]. We instead categorize the underlying mechanisms, as our coverage principle offers quantitative predictions for Type-I boundaries while identifying when Type-II or Type-III mechanisms become necessary. Many influential studies have examined tasks mixing functional equivalence, primitives’ intrinsic properties, and operator reuse within the same benchmark, making it difficult to pinpoint the true source of success or failure. We therefore advocate clearer experimental control and community discussion around this mechanistic distinction to sharpen future analyses of neural generalization.

##### Implications and future directions

Real compositional tasks typically involve combinations of all three types, making it difficult to isolate why models succeed or fail. We suggest diagnostic approaches based on the proposed taxonomy: coverage ablation tests for Type-I, algebraic identity probes for Type-II, and parameter-sharing ablations for Type-III. While preliminary, this taxonomy provides a conceptual scaffold for understanding the fundamental capabilities and limitations of neural networks on compositional reasoning.
This work isolates and formalizes structure-based generalization (Type-I) to clarify its specific boundaries. When models succeed beyond our coverage predictions, e.g., through ignoring distractors without seeing all combinations or leveraging parameter sharing, we view these as exploiting Type-II or Type-III mechanisms rather than contradicting our framework. Our focus on Type-I suggests that fundamental systematicity challenges remain as long as models rely primarily on pattern matching, requiring architectural innovations that harness all three mechanisms and, crucially, incorporate explicit variable binding. We hope this preliminary taxonomy serves as a conversation starter, and confirming or refuting its utility is an empirical matter that we invite the community to explore.

### 7 Discussion

##### Systematicity without variable binding

The coverage principle pinpoints a fundamental question in the systematicity debate:
*How far can a neural network generalize compositionally when it relies only on pattern matching and has no mechanism for explicit variable binding?*
By formalizing the exact conditions under which pattern matching succeeds, we draw a principled boundary around what can be learned from input–output pairs alone.
This boundary clarifies the limitations that Fodor and Pylyshyn [9] and Marcus [37] highlighted decades ago.
Our results therefore complement approaches that encode compositional structure directly, whether through symbolic interfaces, slot-based representations, or neural modules [56, 57, 58, 59, 60, 88], and delineate what must still be overcome to reach truly systematic generalization.

##### Practical implications

Our framework provides valuable insights into various observed LLM behaviors.
First, it accounts for the data-hungry nature of compositional tasks by demonstrating that robust coverage is required for reliable generalization [43].
Next, our framework explains why models struggle with generalizing long-tail knowledge [76, 77, 78], as low-frequency combinations naturally receive limited functional equivalence evidence.
Similarly, failures in complex planning tasks [30, 82, 31, 89], even with CoT techniques, might be attributed to path ambiguities.
Moreover, our coverage principle predicts the reversal curse phenomenon [16, 42, 83], as pattern-matching models fundamentally cannot generalize to reversed relationships without explicit functional equivalence evidence in training data.

Beyond explaining failures, our framework helps understand when and why standard interpretability techniques like linear probing or logit lens can fail.
In addition, our analysis suggests targeted data augmentation strategies that maximize coverage by ensuring diverse shared contexts for functionally equivalent components.
This can explain the success of strategic data augmentation methods [90, 91, 49, 48] and offers principled guidance.
Finally, although our empirical study focuses on GPT-2–style Transformers, the coverage principle itself makes no architectural assumptions, and it applies to any learning system whose generalization mechanism is primarily pattern matching. Extending the analysis to recurrent (e.g., LSTM [84]), state-space [92], or convolutional [93] architectures, and more realistic data where multiple computational structures coexist within the same dataset [12, 15, 94] remains promising future work.

### 8 Conclusion

We introduce the *coverage principle*, a data-centric framework that specifies when pattern-matching learners can and cannot generalize compositionally. Our theoretical analysis and controlled experiments show that a Transformer’s success is tightly predicted by coverage: two-hop tasks obey a superquadratic data scaling law that does not improve with 20x parameter scaling, path ambiguity fragments internal representations, and CoT supervision helps only inside the coverage boundary.

These results isolate Type I structure-based generalization and reveal its limits. Our taxonomy then situates two additional mechanisms, Type II property exploitation and Type III shared-operator reuse, that help explain coverage “violations” reported in the literature. Yet all three mechanisms may still rely on sophisticated pattern matching rather than explicit variable binding, leaving the fundamental systematicity challenge unresolved.

Hence, the systematicity challenge posed by Fodor and Pylyshyn [9] and by Marcus [37] remains open. Matching human-like compositionality will likely require architectures that can *bind* and manipulate symbols independently of surface form, not merely scale up or refine current pattern-matching strategies. We hope the coverage principle and the accompanying taxonomy provide a clear target and a roadmap for the next stage of innovation.

### Acknowledgments and Disclosure of Funding

We would like to thank Jaewon Oh, Jihoon Ha, Hyowon Cho, Yunjae Won, Seongyun Lee, and Boshi Wang for their valuable feedback on our work.

### References

- Fodor [1975]
Jerry Fodor.
The language of thought, 1975.
- Newell and Simon [1976]
Allen Newell and Herbert A. Simon.
Computer science as empirical inquiry: symbols and search.
*Commun. ACM*, 19(3):113–126, 1976.
ISSN 0001-0782.
doi: 10.1145/360018.360022.
URL [https://doi.org/10.1145/360018.360022](https://doi.org/10.1145/360018.360022).
- Brown et al. [2020]
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.
Language models are few-shot learners.
In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual*, 2020.
URL [https://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html](https://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html).
- Achiam et al. [2023]
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al.
Gpt-4 technical report.
*ArXiv preprint*, abs/2303.08774, 2023.
URL [https://arxiv.org/abs/2303.08774](https://arxiv.org/abs/2303.08774).
- Grattafiori et al. [2024]
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al.
The llama 3 herd of models.
*ArXiv preprint*, abs/2407.21783, 2024.
URL [https://arxiv.org/abs/2407.21783](https://arxiv.org/abs/2407.21783).
- Touvron et al. [2023]
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.
Llama: Open and efficient foundation language models.
*ArXiv preprint*, abs/2302.13971, 2023.
URL [https://arxiv.org/abs/2302.13971](https://arxiv.org/abs/2302.13971).
- Team et al. [2023]
Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al.
Gemini: a family of highly capable multimodal models.
*ArXiv preprint*, abs/2312.11805, 2023.
URL [https://arxiv.org/abs/2312.11805](https://arxiv.org/abs/2312.11805).
- Guo et al. [2025]
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al.
Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.
*ArXiv preprint*, abs/2501.12948, 2025.
URL [https://arxiv.org/abs/2501.12948](https://arxiv.org/abs/2501.12948).
- Fodor and Pylyshyn [1988]
Jerry A Fodor and Zenon W Pylyshyn.
Connectionism and cognitive architecture: A critical analysis.
*Cognition*, 28(1-2):3–71, 1988.
- Marcus [1998]
Gary F Marcus.
Rethinking eliminative connectionism.
*Cognitive psychology*, 37(3):243–282, 1998.
- Szabó [2024]
Zoltán Gendler Szabó.
Compositionality.
In Edward N. Zalta and Uri Nodelman, editors, *The Stanford Encyclopedia of Philosophy*. Metaphysics Research Lab, Stanford University, Fall 2024 edition, 2024.
- Lake and Baroni [2018]
Brenden M. Lake and Marco Baroni.
Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.
In Jennifer G. Dy and Andreas Krause, editors, *Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018*, volume 80 of *Proceedings of Machine Learning Research*, pages 2879–2888. PMLR, 2018.
URL [http://proceedings.mlr.press/v80/lake18a.html](http://proceedings.mlr.press/v80/lake18a.html).
- Loula et al. [2018]
João Loula, Marco Baroni, and Brenden Lake.
Rearranging the familiar: Testing compositional generalization in recurrent networks.
In Tal Linzen, Grzegorz Chrupała, and Afra Alishahi, editors, *Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP*, pages 108–114, Brussels, Belgium, 2018. Association for Computational Linguistics.
doi: 10.18653/v1/W18-5413.
URL [https://aclanthology.org/W18-5413](https://aclanthology.org/W18-5413).
- Finegan-Dollak et al. [2018]
Catherine Finegan-Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev.
Improving text-to-SQL evaluation methodology.
In Iryna Gurevych and Yusuke Miyao, editors, *Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, pages 351–360, Melbourne, Australia, 2018. Association for Computational Linguistics.
doi: 10.18653/v1/P18-1033.
URL [https://aclanthology.org/P18-1033](https://aclanthology.org/P18-1033).
- Johnson et al. [2017]
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross B. Girshick.
CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning.
In *2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017*, pages 1988–1997. IEEE Computer Society, 2017.
doi: 10.1109/CVPR.2017.215.
URL [https://doi.org/10.1109/CVPR.2017.215](https://doi.org/10.1109/CVPR.2017.215).
- Berglund et al. [2024]
Lukas Berglund, Meg Tong, Maximilian Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans.
The reversal curse: LLMs trained on “a is b” fail to learn “b is a”.
In *The Twelfth International Conference on Learning Representations*, 2024.
URL [https://openreview.net/forum?id=GPKTIktA0k](https://openreview.net/forum?id=GPKTIktA0k).
- Dziri et al. [2023]
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaïd Harchaoui, and Yejin Choi.
Faith and fate: Limits of transformers on compositionality.
In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, *Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023*, 2023.
URL [http://papers.nips.cc/paper_files/paper/2023/hash/deb3c28192f979302c157cb653c15e90-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2023/hash/deb3c28192f979302c157cb653c15e90-Abstract-Conference.html).
- Yang et al. [2024a]
Sohee Yang, Elena Gribovskaya, Nora Kassner, Mor Geva, and Sebastian Riedel.
Do large language models latently perform multi-hop reasoning?
In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, *Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, pages 10210–10229, Bangkok, Thailand, 2024a. Association for Computational Linguistics.
doi: 10.18653/v1/2024.acl-long.550.
URL [https://aclanthology.org/2024.acl-long.550/](https://aclanthology.org/2024.acl-long.550/).
- Wang et al. [2024a]
Boshi Wang, Xiang Yue, Yu Su, and Huan Sun.
Grokking of implicit reasoning in transformers: A mechanistic journey to the edge of generalization.
In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024*, 2024a.
URL [http://papers.nips.cc/paper_files/paper/2024/hash/ad217e0c7fecc71bdf48660ad6714b07-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2024/hash/ad217e0c7fecc71bdf48660ad6714b07-Abstract-Conference.html).
- Mirzadeh et al. [2025]
Seyed Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar.
GSM-symbolic: Understanding the limitations of mathematical reasoning in large language models.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=AjXkRZIvjB](https://openreview.net/forum?id=AjXkRZIvjB).
- Keysers et al. [2020]
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet.
Measuring compositional generalization: A comprehensive method on realistic data.
In *8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020*. OpenReview.net, 2020.
URL [https://openreview.net/forum?id=SygcCnNKwr](https://openreview.net/forum?id=SygcCnNKwr).
- Csordás et al. [2022]
Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber.
CTL++: Evaluating generalization on never-seen compositional patterns of known functions, and compatibility of neural representations.
In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, *Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing*, pages 9758–9767, Abu Dhabi, United Arab Emirates, 2022. Association for Computational Linguistics.
doi: 10.18653/v1/2022.emnlp-main.662.
URL [https://aclanthology.org/2022.emnlp-main.662](https://aclanthology.org/2022.emnlp-main.662).
- Kim and Linzen [2020]
Najoung Kim and Tal Linzen.
COGS: A compositional generalization challenge based on semantic interpretation.
In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, *Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)*, pages 9087–9105, Online, 2020. Association for Computational Linguistics.
doi: 10.18653/v1/2020.emnlp-main.731.
URL [https://aclanthology.org/2020.emnlp-main.731](https://aclanthology.org/2020.emnlp-main.731).
- Press et al. [2023]
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah Smith, and Mike Lewis.
Measuring and narrowing the compositionality gap in language models.
In Houda Bouamor, Juan Pino, and Kalika Bali, editors, *Findings of the Association for Computational Linguistics: EMNLP 2023*, pages 5687–5711, Singapore, 2023. Association for Computational Linguistics.
doi: 10.18653/v1/2023.findings-emnlp.378.
URL [https://aclanthology.org/2023.findings-emnlp.378](https://aclanthology.org/2023.findings-emnlp.378).
- Xu et al. [2024]
Zhuoyan Xu, Zhenmei Shi, and Yingyu Liang.
Do large language models have compositional ability? an investigation into limitations and scalability.
In *ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models*, 2024.
URL [https://openreview.net/forum?id=4XPeF0SbJs](https://openreview.net/forum?id=4XPeF0SbJs).
- Vaswani et al. [2017]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.
Attention is all you need.
In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, *Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA*, pages 5998–6008, 2017.
URL [https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html](https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html).
- Wei et al. [2022]
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou.
Chain-of-thought prompting elicits reasoning in large language models.
In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022*, 2022.
URL [http://papers.nips.cc/paper_files/paper/2022/hash/9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2022/hash/9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html).
- Kojima et al. [2022]
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa.
Large language models are zero-shot reasoners.
In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022*, 2022.
URL [http://papers.nips.cc/paper_files/paper/2022/hash/8bb0d291acd4acf06ef112099c16f326-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2022/hash/8bb0d291acd4acf06ef112099c16f326-Abstract-Conference.html).
- Ruis et al. [2020]
Laura Ruis, Jacob Andreas, Marco Baroni, Diane Bouchacourt, and Brenden M. Lake.
A benchmark for systematic generalization in grounded language understanding.
In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual*, 2020.
URL [https://proceedings.neurips.cc/paper/2020/hash/e5a90182cc81e12ab5e72d66e0b46fe3-Abstract.html](https://proceedings.neurips.cc/paper/2020/hash/e5a90182cc81e12ab5e72d66e0b46fe3-Abstract.html).
- Valmeekam et al. [2023]
Karthik Valmeekam, Matthew Marquez, Alberto Olmo Hernandez, Sarath Sreedharan, and Subbarao Kambhampati.
Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change.
In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, *Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023*, 2023.
URL [http://papers.nips.cc/paper_files/paper/2023/hash/7a92bcdede88c7afd108072faf5485c8-Abstract-Datasets_and_Benchmarks.html](http://papers.nips.cc/paper_files/paper/2023/hash/7a92bcdede88c7afd108072faf5485c8-Abstract-Datasets_and_Benchmarks.html).
- Kambhampati et al. [2024]
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy.
Position: Llms can’t plan, but can help planning in llm-modulo frameworks.
In *Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024*. OpenReview.net, 2024.
URL [https://openreview.net/forum?id=Th8JPEmH4z](https://openreview.net/forum?id=Th8JPEmH4z).
- Frankland and Greene [2020]
Steven M Frankland and Joshua D Greene.
Concepts and compositionality: in search of the brain’s language of thought.
*Annual review of psychology*, 71(1):273–303, 2020.
- Ito et al. [2022]
Takuya Ito, Tim Klinger, Douglas Schultz, John Murray, Michael W. Cole, and Mattia Rigotti.
Compositional generalization through abstract representations in human and artificial neural networks.
In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022*, 2022.
URL [http://papers.nips.cc/paper_files/paper/2022/hash/d0241a0fb1fc9be477bdfde5e0da276a-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2022/hash/d0241a0fb1fc9be477bdfde5e0da276a-Abstract-Conference.html).
- Piantadosi [2021]
Steven T Piantadosi.
The computational origin of representation.
*Minds and machines*, 31(1):1–58, 2021.
- Martin and Baggio [2019]
Andrea E. Martin and Giosuè Baggio.
Modelling meaning composition from formalism to mechanism.
*Philosophical Transactions of the Royal Society B*, 375, 2019.
URL [https://api.semanticscholar.org/CorpusID:209370877](https://api.semanticscholar.org/CorpusID:209370877).
- Smolensky [1990]
Paul Smolensky.
Tensor product variable binding and the representation of symbolic structures in connectionist systems.
*Artificial intelligence*, 46(1-2):159–216, 1990.
- Marcus [2003]
Gary F Marcus.
*The algebraic mind: Integrating connectionism and cognitive science*.
MIT press, 2003.
- Hupkes et al. [2020]
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni.
Compositionality decomposed: How do neural networks generalise?
*Journal of Artificial Intelligence Research*, 67:757–795, 2020.
- Elmoznino et al. [2024]
Eric Elmoznino, Thomas Jiralerspong, Yoshua Bengio, and Guillaume Lajoie.
A complexity-based theory of compositionality.
*ArXiv preprint*, abs/2410.14817, 2024.
URL [https://arxiv.org/abs/2410.14817](https://arxiv.org/abs/2410.14817).
- Feldman [2013]
Jerome Feldman.
The neural binding problem(s).
*Cognitive Neurodynamics*, 7, 2013.
doi: 10.1007/s11571-012-9219-8.
- Greff et al. [2020]
Klaus Greff, Sjoerd Van Steenkiste, and Jürgen Schmidhuber.
On the binding problem in artificial neural networks.
*ArXiv preprint*, abs/2012.05208, 2020.
URL [https://arxiv.org/abs/2012.05208](https://arxiv.org/abs/2012.05208).
- Wang and Sun [2025]
Boshi Wang and Huan Sun.
Is the reversal curse a binding problem? uncovering limitations of transformers from a basic generalization failure.
*ArXiv preprint*, abs/2504.01928, 2025.
URL [https://arxiv.org/abs/2504.01928](https://arxiv.org/abs/2504.01928).
- Lake et al. [2017]
Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman.
Building machines that learn and think like people.
*Behavioral and brain sciences*, 40:e253, 2017.
- Thomm et al. [2024]
Jonathan Thomm, Giacomo Camposampiero, Aleksandar Terzic, Michael Hersche, Bernhard Schölkopf, and Abbas Rahimi.
Limits of transformer language models on learning to compose algorithms.
In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024*, 2024.
URL [http://papers.nips.cc/paper_files/paper/2024/hash/0e797d5139ad94fc2dc2080c09119f29-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2024/hash/0e797d5139ad94fc2dc2080c09119f29-Abstract-Conference.html).
- Schott et al. [2022]
Lukas Schott, Julius von Kügelgen, Frederik Träuble, Peter Vincent Gehler, Chris Russell, Matthias Bethge, Bernhard Schölkopf, Francesco Locatello, and Wieland Brendel.
Visual representation learning does not generalize strongly within the same domain.
In *The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022*. OpenReview.net, 2022.
URL [https://openreview.net/forum?id=9RUHPlladgh](https://openreview.net/forum?id=9RUHPlladgh).
- Yang et al. [2024b]
Haoran Yang, Hongyuan Lu, Wai Lam, and Deng Cai.
Exploring compositional generalization of large language models.
In Yang (Trista) Cao, Isabel Papadimitriou, and Anaelia Ovalle, editors, *Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 4: Student Research Workshop)*, pages 16–24, Mexico City, Mexico, 2024b. Association for Computational Linguistics.
URL [https://aclanthology.org/2024.naacl-srw.3](https://aclanthology.org/2024.naacl-srw.3).
- Yao et al. [2025]
Xinhao Yao, Ruifeng Ren, Yun Liao, and Yong Liu.
Unveiling the mechanisms of explicit cot training: How chain-of-thought enhances reasoning generalization.
*ArXiv preprint*, abs/2502.04667, 2025.
URL [https://arxiv.org/abs/2502.04667](https://arxiv.org/abs/2502.04667).
- Andreas [2020]
Jacob Andreas.
Good-enough compositional data augmentation.
In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault, editors, *Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics*, pages 7556–7566, Online, 2020. Association for Computational Linguistics.
doi: 10.18653/v1/2020.acl-main.676.
URL [https://aclanthology.org/2020.acl-main.676](https://aclanthology.org/2020.acl-main.676).
- Auersperger and Pecina [2021]
Michal Auersperger and Pavel Pecina.
Solving SCAN tasks with data augmentation and input embeddings.
In Ruslan Mitkov and Galia Angelova, editors, *Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2021)*, pages 86–91, Held Online, 2021. INCOMA Ltd.
URL [https://aclanthology.org/2021.ranlp-1.11](https://aclanthology.org/2021.ranlp-1.11).
- Kaplan et al. [2020]
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.
Scaling laws for neural language models.
*ArXiv preprint*, abs/2001.08361, 2020.
URL [https://arxiv.org/abs/2001.08361](https://arxiv.org/abs/2001.08361).
- Hoffmann et al. [2022]
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack W. Rae, and Laurent Sifre.
Training compute-optimal large language models.
In *Proceedings of the 36th International Conference on Neural Information Processing Systems*, NIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc.
ISBN 9781713871088.
- Locatello et al. [2019]
Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Rätsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem.
Challenging common assumptions in the unsupervised learning of disentangled representations.
In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, *Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA*, volume 97 of *Proceedings of Machine Learning Research*, pages 4114–4124. PMLR, 2019.
URL [http://proceedings.mlr.press/v97/locatello19a.html](http://proceedings.mlr.press/v97/locatello19a.html).
- Lippl and Stachenfeld [2025]
Samuel Lippl and Kim Stachenfeld.
When does compositional structure yield compositional generalization? a kernel theory.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=FPBce2P1er](https://openreview.net/forum?id=FPBce2P1er).
- Besserve et al. [2021]
Michel Besserve, Rémy Sun, Dominik Janzing, and Bernhard Schölkopf.
A theory of independent mechanisms for extrapolation in generative models.
In *Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021*, pages 6741–6749. AAAI Press, 2021.
URL [https://ojs.aaai.org/index.php/AAAI/article/view/16833](https://ojs.aaai.org/index.php/AAAI/article/view/16833).
- Montero et al. [2021]
Milton Llera Montero, Casimir J. H. Ludwig, Rui Ponte Costa, Gaurav Malhotra, and Jeffrey Bowers.
The role of disentanglement in generalisation.
In *9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021*. OpenReview.net, 2021.
URL [https://openreview.net/forum?id=qbH974jKUVy](https://openreview.net/forum?id=qbH974jKUVy).
- Lake and Baroni [2023]
Brenden M Lake and Marco Baroni.
Human-like systematic generalization through a meta-learning neural network.
*Nature*, 623(7985):115–121, 2023.
- Hinton [2023]
Geoffrey Hinton.
How to represent part-whole hierarchies in a neural network.
*Neural Computation*, 35(3):413–452, 2023.
- Andreas et al. [2016]
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein.
Neural module networks.
In *2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016*, pages 39–48. IEEE Computer Society, 2016.
doi: 10.1109/CVPR.2016.12.
URL [https://doi.org/10.1109/CVPR.2016.12](https://doi.org/10.1109/CVPR.2016.12).
- LeCun [2022]
Yann LeCun.
A path towards autonomous machine intelligence version 0.9. 2, 2022-06-27.
*Open Review*, 62(1):1–62, 2022.
- Goyal and Bengio [2022]
Anirudh Goyal and Yoshua Bengio.
Inductive biases for deep learning of higher-level cognition.
*Proceedings of the Royal Society A*, 478(2266):20210068, 2022.
- Elhage et al. [2021]
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al.
A mathematical framework for transformer circuits.
*Transformer Circuits Thread*, 1(1):12, 2021.
- Olsson et al. [2022]
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al.
In-context learning and induction heads.
*ArXiv preprint*, abs/2209.11895, 2022.
URL [https://arxiv.org/abs/2209.11895](https://arxiv.org/abs/2209.11895).
- Nanda et al. [2023]
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt.
Progress measures for grokking via mechanistic interpretability.
In *The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023*. OpenReview.net, 2023.
URL [https://openreview.net/pdf?id=9XFSbDPmdW](https://openreview.net/pdf?id=9XFSbDPmdW).
- Elhage et al. [2022]
Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al.
Toy models of superposition.
*ArXiv preprint*, abs/2209.10652, 2022.
URL [https://arxiv.org/abs/2209.10652](https://arxiv.org/abs/2209.10652).
- Meng et al. [2022]
Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov.
Locating and editing factual associations in GPT.
In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022*, 2022.
URL [http://papers.nips.cc/paper_files/paper/2022/hash/6f1d43d5a82a37e89b0665b33bf3a182-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2022/hash/6f1d43d5a82a37e89b0665b33bf3a182-Abstract-Conference.html).
- Hanna et al. [2023]
Michael Hanna, Ollie Liu, and Alexandre Variengien.
How does GPT-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model.
In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, *Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023*, 2023.
URL [http://papers.nips.cc/paper_files/paper/2023/hash/efbba7719cc5172d175240f24be11280-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2023/hash/efbba7719cc5172d175240f24be11280-Abstract-Conference.html).
- Goldowsky-Dill et al. [2023]
Nicholas Goldowsky-Dill, Chris MacLeod, Lucas Sato, and Aryaman Arora.
Localizing model behavior with path patching.
*ArXiv preprint*, abs/2304.05969, 2023.
URL [https://arxiv.org/abs/2304.05969](https://arxiv.org/abs/2304.05969).
- Tang et al. [2025]
Cheng Tang, Brenden Lake, and Mehrdad Jazayeri.
An explainable transformer circuit for compositional generalization.
*ArXiv preprint*, abs/2502.15801, 2025.
URL [https://arxiv.org/abs/2502.15801](https://arxiv.org/abs/2502.15801).
- Song et al. [2024]
Jiajun Song, Zhuoyan Xu, and Yiqiao Zhong.
Out-of-distribution generalization via composition: a lens through induction heads in transformers.
*Proceedings of the National Academy of Sciences of the United States of America*, 122 6:e2417182122, 2024.
URL [https://api.semanticscholar.org/CorpusID:271904016](https://api.semanticscholar.org/CorpusID:271904016).
- nostalgebraist [2020]
nostalgebraist.
interpreting gpt: the logit lens.
*LessWrong*, 2020.
URL [https://www.lesswrong.com/posts/AcKRB8wDpdaN6v6ru/interpreting-gpt-the-logit-lens](https://www.lesswrong.com/posts/AcKRB8wDpdaN6v6ru/interpreting-gpt-the-logit-lens).
- Belrose et al. [2023]
Nora Belrose, Zach Furman, Logan Smith, Danny Halawi, Igor Ostrovsky, Lev McKinney, Stella Biderman, and Jacob Steinhardt.
Eliciting latent predictions from transformers with the tuned lens.
*ArXiv preprint*, abs/2303.08112, 2023.
URL [https://arxiv.org/abs/2303.08112](https://arxiv.org/abs/2303.08112).
- Mingard et al. [2019]
Chris Mingard, Joar Skalse, Guillermo Valle-Pérez, David Martínez-Rubio, Vladimir Mikulik, and Ard A Louis.
Neural networks are a priori biased towards boolean functions with low entropy.
*ArXiv preprint*, abs/1909.11522, 2019.
URL [https://arxiv.org/abs/1909.11522](https://arxiv.org/abs/1909.11522).
- Dwivedi et al. [2023]
Raaz Dwivedi, Chandan Singh, Bin Yu, and Martin Wainwright.
Revisiting minimum description length complexity in overparameterized models.
*Journal of Machine Learning Research*, 24(268):1–59, 2023.
- Vardi [2023]
Gal Vardi.
On the implicit bias in deep-learning algorithms.
*Communications of the ACM*, 66(6):86–93, 2023.
- Radford et al. [2019]
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.
Language models are unsupervised multitask learners.
*OpenAI blog*, 1(8):9, 2019.
- Mallen et al. [2023]
Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, and Hannaneh Hajishirzi.
When not to trust language models: Investigating effectiveness of parametric and non-parametric memories.
In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, *Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, pages 9802–9822, Toronto, Canada, 2023. Association for Computational Linguistics.
doi: 10.18653/v1/2023.acl-long.546.
URL [https://aclanthology.org/2023.acl-long.546](https://aclanthology.org/2023.acl-long.546).
- Kandpal et al. [2023]
Nikhil Kandpal, Haikang Deng, Adam Roberts, Eric Wallace, and Colin Raffel.
Large language models struggle to learn long-tail knowledge.
In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, *International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA*, volume 202 of *Proceedings of Machine Learning Research*, pages 15696–15707. PMLR, 2023.
URL [https://proceedings.mlr.press/v202/kandpal23a.html](https://proceedings.mlr.press/v202/kandpal23a.html).
- Chang et al. [2024]
Hoyeon Chang, Jinho Park, Seonghyeon Ye, Sohee Yang, Youngkyung Seo, Du-Seong Chang, and Minjoon Seo.
How do large language models acquire factual knowledge during pretraining?
In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024*, 2024.
URL [http://papers.nips.cc/paper_files/paper/2024/hash/6fdf57c71bc1f1ee29014b8dc52e723f-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2024/hash/6fdf57c71bc1f1ee29014b8dc52e723f-Abstract-Conference.html).
- Srivastava et al. [2023]
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, Agnieszka Kluska, Aitor Lewkowycz, Akshat Agarwal, Alethea Power, Alex Ray, Alex Warstadt, Alexander W. Kocurek, Ali Safaya, Ali Tazarv, Alice Xiang, Alicia Parrish, Allen Nie, Aman Hussain, Amanda Askell, Amanda Dsouza, Ambrose Slone, Ameet Rahane, Anantharaman S. Iyer, Anders Johan Andreassen, Andrea Madotto, Andrea Santilli, Andreas Stuhlmüller, Andrew M. Dai, Andrew La, Andrew Kyle Lampinen, Andy Zou, Angela Jiang, Angelica Chen, Anh Vuong, Animesh Gupta, Anna Gottardi, Antonio Norelli, Anu Venkatesh, Arash Gholamidavoodi, Arfa Tabassum, Arul Menezes, Arun Kirubarajan, Asher Mullokandov, Ashish Sabharwal, Austin Herrick, Avia Efrat, Aykut Erdem, Ayla Karakaş, B. Ryan Roberts, Bao Sheng Loe, Barret Zoph, Bartłomiej Bojanowski, Batuhan Özyurt, Behnam Hedayatnia, Behnam Neyshabur, Benjamin Inden, Benno Stein, Berk Ekmekci,
Bill Yuchen Lin, Blake Howald, Bryan Orinion, Cameron Diao, Cameron Dour, Catherine Stinson, Cedrick Argueta, Cesar Ferri, Chandan Singh, Charles Rathkopf, Chenlin Meng, Chitta Baral, Chiyu Wu, Chris Callison-Burch, Christopher Waites, Christian Voigt, Christopher D Manning, Christopher Potts, Cindy Ramirez, Clara E. Rivera, Clemencia Siro, Colin Raffel, Courtney Ashcraft, Cristina Garbacea, Damien Sileo, Dan Garrette, Dan Hendrycks, Dan Kilman, Dan Roth, C. Daniel Freeman, Daniel Khashabi, Daniel Levy, Daniel Moseguí González, Danielle Perszyk, Danny Hernandez, Danqi Chen, Daphne Ippolito, Dar Gilboa, David Dohan, David Drakard, David Jurgens, Debajyoti Datta, Deep Ganguli, Denis Emelin, Denis Kleyko, Deniz Yuret, Derek Chen, Derek Tam, Dieuwke Hupkes, Diganta Misra, Dilyar Buzan, Dimitri Coelho Mollo, Diyi Yang, Dong-Ho Lee, Dylan Schrader, Ekaterina Shutova, Ekin Dogus Cubuk, Elad Segal, Eleanor Hagerman, Elizabeth Barnes, Elizabeth Donoway, Ellie Pavlick, Emanuele Rodolà, Emma Lam, Eric
Chu, Eric Tang, Erkut Erdem, Ernie Chang, Ethan A Chi, Ethan Dyer, Ethan Jerzak, Ethan Kim, Eunice Engefu Manyasi, Evgenii Zheltonozhskii, Fanyue Xia, Fatemeh Siar, Fernando Martínez-Plumed, Francesca Happé, Francois Chollet, Frieda Rong, Gaurav Mishra, Genta Indra Winata, Gerard de Melo, Germàn Kruszewski, Giambattista Parascandolo, Giorgio Mariani, Gloria Xinyue Wang, Gonzalo Jaimovitch-Lopez, Gregor Betz, Guy Gur-Ari, Hana Galijasevic, Hannah Kim, Hannah Rashkin, Hannaneh Hajishirzi, Harsh Mehta, Hayden Bogar, Henry Francis Anthony Shevlin, Hinrich Schuetze, Hiromu Yakura, Hongming Zhang, Hugh Mee Wong, Ian Ng, Isaac Noble, Jaap Jumelet, Jack Geissinger, Jackson Kernion, Jacob Hilton, Jaehoon Lee, Jaime Fernández Fisac, James B Simon, James Koppel, James Zheng, James Zou, Jan Kocon, Jana Thompson, Janelle Wingfield, Jared Kaplan, Jarema Radom, Jascha Sohl-Dickstein, Jason Phang, Jason Wei, Jason Yosinski, Jekaterina Novikova, Jelle Bosscher, Jennifer Marsh, Jeremy Kim, Jeroen Taal, Jesse
Engel, Jesujoba Alabi, Jiacheng Xu, Jiaming Song, Jillian Tang, Joan Waweru, John Burden, John Miller, John U. Balis, Jonathan Batchelder, Jonathan Berant, Jörg Frohberg, Jos Rozen, Jose Hernandez-Orallo, Joseph Boudeman, Joseph Guerr, Joseph Jones, Joshua B. Tenenbaum, Joshua S. Rule, Joyce Chua, Kamil Kanclerz, Karen Livescu, Karl Krauth, Karthik Gopalakrishnan, Katerina Ignatyeva, Katja Markert, Kaustubh Dhole, Kevin Gimpel, Kevin Omondi, Kory Wallace Mathewson, Kristen Chiafullo, Ksenia Shkaruta, Kumar Shridhar, Kyle McDonell, Kyle Richardson, Laria Reynolds, Leo Gao, Li Zhang, Liam Dugan, Lianhui Qin, Lidia Contreras-Ochando, Louis-Philippe Morency, Luca Moschella, Lucas Lam, Lucy Noble, Ludwig Schmidt, Luheng He, Luis Oliveros-Colón, Luke Metz, Lütfi Kerem Senel, Maarten Bosma, Maarten Sap, Maartje Ter Hoeve, Maheen Farooqi, Manaal Faruqui, Mantas Mazeika, Marco Baturan, Marco Marelli, Marco Maru, Maria Jose Ramirez-Quintana, Marie Tolkiehn, Mario Giulianelli, Martha Lewis, Martin
Potthast, Matthew L Leavitt, Matthias Hagen, Mátyás Schubert, Medina Orduna Baitemirova, Melody Arnaud, Melvin McElrath, Michael Andrew Yee, Michael Cohen, Michael Gu, Michael Ivanitskiy, Michael Starritt, Michael Strube, Michał Swędrowski, Michele Bevilacqua, Michihiro Yasunaga, Mihir Kale, Mike Cain, Mimee Xu, Mirac Suzgun, Mitch Walker, Mo Tiwari, Mohit Bansal, Moin Aminnaseri, Mor Geva, Mozhdeh Gheini, Mukund Varma T, Nanyun Peng, Nathan Andrew Chi, Nayeon Lee, Neta Gur-Ari Krakover, Nicholas Cameron, Nicholas Roberts, Nick Doiron, Nicole Martinez, Nikita Nangia, Niklas Deckers, Niklas Muennighoff, Nitish Shirish Keskar, Niveditha S. Iyer, Noah Constant, Noah Fiedel, Nuan Wen, Oliver Zhang, Omar Agha, Omar Elbaghdadi, Omer Levy, Owain Evans, Pablo Antonio Moreno Casares, Parth Doshi, Pascale Fung, Paul Pu Liang, Paul Vicol, Pegah Alipoormolabashi, Peiyuan Liao, Percy Liang, Peter W Chang, Peter Eckersley, Phu Mon Htut, Pinyu Hwang, Piotr Miłkowski, Piyush Patil, Pouya Pezeshkpour,
Priti Oli, Qiaozhu Mei, Qing Lyu, Qinlang Chen, Rabin Banjade, Rachel Etta Rudolph, Raefer Gabriel, Rahel Habacker, Ramon Risco, Raphaël Millière, Rhythm Garg, Richard Barnes, Rif A. Saurous, Riku Arakawa, Robbe Raymaekers, Robert Frank, Rohan Sikand, Roman Novak, Roman Sitelew, Ronan Le Bras, Rosanne Liu, Rowan Jacobs, Rui Zhang, Russ Salakhutdinov, Ryan Andrew Chi, Seungjae Ryan Lee, Ryan Stovall, Ryan Teehan, Rylan Yang, Sahib Singh, Saif M. Mohammad, Sajant Anand, Sam Dillavou, Sam Shleifer, Sam Wiseman, Samuel Gruetter, Samuel R. Bowman, Samuel Stern Schoenholz, Sanghyun Han, Sanjeev Kwatra, Sarah A. Rous, Sarik Ghazarian, Sayan Ghosh, Sean Casey, Sebastian Bischoff, Sebastian Gehrmann, Sebastian Schuster, Sepideh Sadeghi, Shadi Hamdan, Sharon Zhou, Shashank Srivastava, Sherry Shi, Shikhar Singh, Shima Asaadi, Shixiang Shane Gu, Shubh Pachchigar, Shubham Toshniwal, Shyam Upadhyay, Shyamolima Shammie Debnath, Siamak Shakeri, Simon Thormeyer, Simone Melzi, Siva Reddy, Sneha Priscilla Makini,
Soo-Hwan Lee, Spencer Torene, Sriharsha Hatwar, Stanislas Dehaene, Stefan Divic, Stefano Ermon, Stella Biderman, Stephanie Lin, Stephen Prasad, Steven Piantadosi, Stuart Shieber, Summer Misherghi, Svetlana Kiritchenko, Swaroop Mishra, Tal Linzen, Tal Schuster, Tao Li, Tao Yu, Tariq Ali, Tatsunori Hashimoto, Te-Lin Wu, Théo Desbordes, Theodore Rothschild, Thomas Phan, Tianle Wang, Tiberius Nkinyili, Timo Schick, Timofei Kornev, Titus Tunduny, Tobias Gerstenberg, Trenton Chang, Trishala Neeraj, Tushar Khot, Tyler Shultz, Uri Shaham, Vedant Misra, Vera Demberg, Victoria Nyamai, Vikas Raunak, Vinay Venkatesh Ramasesh, vinay uday prabhu, Vishakh Padmakumar, Vivek Srikumar, William Fedus, William Saunders, William Zhang, Wout Vossen, Xiang Ren, Xiaoyu Tong, Xinran Zhao, Xinyi Wu, Xudong Shen, Yadollah Yaghoobzadeh, Yair Lakretz, Yangqiu Song, Yasaman Bahri, Yejin Choi, Yichi Yang, Sophie Hao, Yifu Chen, Yonatan Belinkov, Yu Hou, Yufang Hou, Yuntao Bai, Zachary Seid, Zhuoye Zhao, Zijian Wang, Zijie J. Wang,
Zirui Wang, and Ziyi Wu.
Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.
*Transactions on Machine Learning Research*, 2023.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=uyTL5Bvosj](https://openreview.net/forum?id=uyTL5Bvosj).
Featured Certification.
- Kim and Suzuki [2025]
Juno Kim and Taiji Suzuki.
Transformers provably solve parity efficiently with chain of thought.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=n2NidsYDop](https://openreview.net/forum?id=n2NidsYDop).
- Wen et al. [2025]
Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, and Jingzhao Zhang.
From sparse dependence to sparse attention: Unveiling how chain-of-thought enhances transformer sample efficiency.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=AmEgWDhmTr](https://openreview.net/forum?id=AmEgWDhmTr).
- Stechly et al. [2024]
Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati.
Chain of thoughtlessness? an analysis of cot in planning.
In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, *Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024*, 2024.
URL [http://papers.nips.cc/paper_files/paper/2024/hash/3365d974ce309623bd8151082d78206c-Abstract-Conference.html](http://papers.nips.cc/paper_files/paper/2024/hash/3365d974ce309623bd8151082d78206c-Abstract-Conference.html).
- Lv et al. [2024]
Ang Lv, Kaiyi Zhang, Shufang Xie, Quan Tu, Yuhan Chen, Ji-Rong Wen, and Rui Yan.
An analysis and mitigation of the reversal curse.
In *Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing*, pages 13603–13615, 2024.
- Hochreiter and Schmidhuber [1997]
Sepp Hochreiter and Jürgen Schmidhuber.
Long short-term memory.
*Neural computation*, 9(8):1735–1780, 1997.
- Graves et al. [2014]
Alex Graves, Greg Wayne, and Ivo Danihelka.
Neural turing machines.
*arXiv preprint arXiv:1410.5401*, 2014.
- Dehghani et al. [2019]
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser.
Universal transformers.
In *7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019*. OpenReview.net, 2019.
URL [https://openreview.net/forum?id=HyzdRiR9Y7](https://openreview.net/forum?id=HyzdRiR9Y7).
- Csordás et al. [2021]
Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber.
The devil is in the detail: Simple tricks improve systematic generalization of transformers.
In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, *Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing*, pages 619–634, Online and Punta Cana, Dominican Republic, 2021. Association for Computational Linguistics.
doi: 10.18653/v1/2021.emnlp-main.49.
URL [https://aclanthology.org/2021.emnlp-main.49](https://aclanthology.org/2021.emnlp-main.49).
- Locatello et al. [2020]
Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf.
Object-centric learning with slot attention.
In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, *Advances in Neural Information Processing Systems*, volume 33, pages 11525–11538. Curran Associates, Inc., 2020.
URL [https://proceedings.neurips.cc/paper_files/paper/2020/file/8511df98c02ab60aea1b2356c013bc0f-Paper.pdf](https://proceedings.neurips.cc/paper_files/paper/2020/file/8511df98c02ab60aea1b2356c013bc0f-Paper.pdf).
- Wang et al. [2024b]
Kevin Wang, Junbo Li, Neel P. Bhatt, Yihan Xi, qiang liu, ufuk topcu, and Zhangyang Wang.
Ontheplanning abilities of openAI’s o1 models: Feasibility, optimality, and generalizability.
In *Language Gamification - NeurIPS 2024 Workshop*, 2024b.
URL [https://openreview.net/forum?id=qgvQx30Z0R](https://openreview.net/forum?id=qgvQx30Z0R).
- Golovneva et al. [2024]
Olga Golovneva, Zeyuan Allen-Zhu, Jason E Weston, and Sainbayar Sukhbaatar.
Reverse training to nurse the reversal curse.
In *First Conference on Language Modeling*, 2024.
URL [https://openreview.net/forum?id=HDkNbfLQgu](https://openreview.net/forum?id=HDkNbfLQgu).
- Allen-Zhu and Li [2024]
Zeyuan Allen-Zhu and Yuanzhi Li.
Physics of language models: Part 3.1, knowledge storage and extraction.
In *Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024*. OpenReview.net, 2024.
URL [https://openreview.net/forum?id=5x788rqbcj](https://openreview.net/forum?id=5x788rqbcj).
- Gu and Dao [2024]
Albert Gu and Tri Dao.
Mamba: Linear-time sequence modeling with selective state spaces.
In *First Conference on Language Modeling*, 2024.
URL [https://openreview.net/forum?id=tEYskw1VY2](https://openreview.net/forum?id=tEYskw1VY2).
- LeCun et al. [1998]
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.
Gradient-based learning applied to document recognition.
*Proceedings of the IEEE*, 86(11):2278–2324, 1998.
- Yu et al. [2018]
Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev.
Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQL task.
In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun’ichi Tsujii, editors, *Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing*, pages 3911–3921, Brussels, Belgium, 2018. Association for Computational Linguistics.
doi: 10.18653/v1/D18-1425.
URL [https://aclanthology.org/D18-1425](https://aclanthology.org/D18-1425).
- Sharma et al. [2024]
Arnab Sen Sharma, David Atkinson, and David Bau.
Locating and editing factual associations in mamba.
In *First Conference on Language Modeling*, 2024.
URL [https://openreview.net/forum?id=yoVRyrEgix](https://openreview.net/forum?id=yoVRyrEgix).
- Erdős and Rényi [1959]
Paul Erdős and Alfréd Rényi.
On random graphs i.
*Publ. math. debrecen*, 6(290-297):18, 1959.
- Erdős and Rényi [1960]
Paul Erdős and Alfréd Rényi.
On the evolution of random graphs.
*Publ. Math. Inst. Hungar. Acad. Sci*, 5:17–61, 1960.
- Le Cam [1960]
Lucien Le Cam.
An approximation theorem for the poisson binomial distribution.
*Pacific Journal of Mathematics*, 10(4):1181–1197, 1960.
doi: 10.2140/pjm.1960.10.1181.
- Abbe et al. [2024]
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk.
Generalization on the unseen, logic reasoning and degree curriculum.
*Journal of Machine Learning Research*, 25(331):1–58, 2024.
- Cho et al. [2025]
Hanseul Cho, Jaeyoung Cha, Srinadh Bhojanapalli, and Chulhee Yun.
Arithmetic transformers can length-generalize in both operand length and count.
In *The Thirteenth International Conference on Learning Representations*, 2025.
URL [https://openreview.net/forum?id=eIgGesYKLG](https://openreview.net/forum?id=eIgGesYKLG).
- Zhou et al. [2024a]
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran.
What algorithms can transformers learn? A study in length generalization.
In *The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024*. OpenReview.net, 2024a.
URL [https://openreview.net/forum?id=AssIuHnmHX](https://openreview.net/forum?id=AssIuHnmHX).
- Shen et al. [2023]
Ruoqi Shen, Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, Yuanzhi Li, and Yi Zhang.
Positional description matters for transformers arithmetic.
*arXiv preprint arXiv:2311.14737*, 2023.
- Zhou et al. [2024b]
Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou.
Transformers can achieve length generalization but not robustly.
In *ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models*, 2024b.
URL [https://openreview.net/forum?id=DWkWIh3vFJ](https://openreview.net/forum?id=DWkWIh3vFJ).
- Deletang et al. [2023]
Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega.
Neural networks and the chomsky hierarchy.
In *The Eleventh International Conference on Learning Representations*, 2023.
URL [https://openreview.net/forum?id=WbxHAzkeQcn](https://openreview.net/forum?id=WbxHAzkeQcn).
- Liu et al. [2023]
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang.
Transformers learn shortcuts to automata.
In *The Eleventh International Conference on Learning Representations*, 2023.
URL [https://openreview.net/forum?id=De4FYqjFueZ](https://openreview.net/forum?id=De4FYqjFueZ).
- Dekker et al. [2022]
Ronald B Dekker, Fabian Otto, and Christopher Summerfield.
Curriculum learning for human compositional generalization.
*Proceedings of the National Academy of Sciences*, 119(41):e2205582119, 2022.

## Contents of the Appendix

subsubsection \localtableofcontents

### Appendix A Limitations

We deliberately restrict to synthetic tasks to isolate structure-based limits without confounds from lexical or domain priors. We leave extending the coverage analysis to natural data as a future work. Additionally, our experiments focus on autoregressive Transformer architectures, and the applicability of the coverage principle to other architectures (e.g., state-space models) remains to be validated.

### Appendix B Detailed experimental setup

#### B.1 Dataset construction details

We now provide detailed information about our dataset construction process. While we primarily explain this process for the 2-Hop task, we follow similar procedures for the other compositional structures.

##### Vocabulary and Token Representation

For a task with token set size $|\mathcal{X}|$, we create $|\mathcal{X}|$ special tokens of the form <t_0>, <t_1>, $\ldots$, <t_$(|\mathcal{X}|-1)$>, which we append to the standard GPT-2 vocabulary. We also add special tokens </a> to mark the end of sequences. For Chain-of-Thought (CoT) experiments, intermediate computations are represented in the target sequence as the actual intermediate token.

##### Function Construction

For the 2-Hop task, we construct two primitive functions $f_{1}:\mathcal{X}^{2}\rightarrow\mathcal{X}$ and $f_{2}:\mathcal{X}^{2}\rightarrow\mathcal{X}$ by randomly mapping from their respective domains to the codomain $\mathcal{X}$. We create the domain by taking the Cartesian product of the token set with itself. For each function, we randomly designate a fraction $p_{\text{seen}}=0.7$ of its domain as the "seen" portion, resulting in sets $S_{f_{1}}$ and $S_{f_{2}}$.

##### Dataset Generation Algorithm

To generate the training dataset, we first identify all possible combinations where both primitive operations come from their respective "seen" domains. Specifically, we find all valid tuples $(x_{1},x_{2},x_{3},t)$ such that:

$$ $\displaystyle(x_{1},x_{2})$ $\displaystyle\in\text{domain}(S_{f_{1}})$ (1) $\displaystyle(f_{1}(x_{1},x_{2}),x_{3})$ $\displaystyle\in\text{domain}(S_{f_{2}})$ (2) $\displaystyle t$ $\displaystyle=f_{2}(f_{1}(x_{1},x_{2}),x_{3})$ (3) $$

From this set of all possible in-domain combinations, we uniformly sample $N$ examples to form our training dataset. When the number of possible combinations exceeds $N$, this sampling ensures the model sees only a subset of possible in-domain combinations.

##### Test Set Construction

We carefully construct test sets to evaluate the model’s generalization capabilities across different coverage conditions. Our test sets contain:

- •
In-Domain (ID) Test Set: Combinations not seen during training but where both primitive operations were observed in other contexts. These examples may lie within the coverage as defined by our framework.
- •
Out-of-Domain (OOD) Test Set: Examples where at least one primitive operation was never observed in training. These fall outside the coverage boundary.

##### Input-Output Format

The dataset is formatted for auto-regressive token prediction. For the standard 2-Hop task, inputs comprise three tokens representing $x_{1}$, $x_{2}$, and $x_{3}$, while the target includes these input tokens followed by the prediction $t$ and an end marker. Below are the examples of the dataset format for different settings.

- •
Standard Format:
–
Input: <t_5><t_12><t_3>
–
Target Completion: <t_17></a>
–
The model must predict the final output token followed by the end marker.
- •
Chain-of-Thought Format:
–
Input: <t_5><t_12><t_3>
–
Target Completion: <t_9><t_17></a>
–
The model must first predict the intermediate computation result <t_9> (where <t_9> = $f_{1}$(<t_5>, <t_12>)), followed by the final output.
- •
Partial Computation Format ($f_{1}$):
–
Input: <t_5><t_12>
–
Target Completion: <t_9></a>
–
These examples represent the primitive function applications used to construct the full compositional task.

For the other compositional tasks, we follow analogous construction procedures, adjusting the number of input tokens and the composition structure based on the specific task’s requirements. For example, Parallel 2-Hop requires four input tokens, while 3-Hop follows a three-step composition chain requiring appropriate modifications to the function construction and sampling procedures.

#### B.2 Training details

**Table 1: Model configurations for different GPT-2 variants used in our experiments**
| Configuration | GPT-2-Small | GPT-2 | GPT-2-XL |
| --- | --- | --- | --- |
| Number of Attention Heads | 6 | 12 | 25 |
| Number of Layers | 4 | 8 | 48 |
| Hidden Dimension | 768 | 768 | 1600 |
| Total Parameters | 68M | 96M | 1.5B |

For our experiments, we employ three GPT-2 model variants of increasing size: GPT-2-Small (68M parameters), GPT-2 (96M parameters), and GPT-2-XL (1.5B parameters). As shown in [Tab. 1](https://arxiv.org/html/2505.20278v1#A2.T1), GPT-2-Small consists of 4 layers with 6 attention heads and a hidden dimension of 768. The standard GPT-2 configuration used in most experiments features 8 layers with 12 attention heads while maintaining the same hidden dimension of 768. Our largest model, GPT-2-XL, significantly scales up the architecture with 48 layers, 25 attention heads, and an increased hidden dimension of 1600. The implementation follows the codebase from [19].

We train all models using the AdamW optimizer with beta values of (0.9, 0.999) and epsilon of 1e-8. We set the learning rate to 8e-4 with a weight decay of 0.1. A batch size of 16,384 is used, with full gradient descent applied for datasets smaller than the batch size. All training is conducted with mixed precision (fp16) on 4 NVIDIA A100 GPUs with 80GB memory each. We employ a constant learning rate schedule with a linear warmup period of 2,000 steps. This standardized training configuration is maintained across all experiments to ensure fair comparisons between different task structures and dataset sizes, unless explicitly varied in specific ablation studies.

### Appendix C Implementation details for the coverage determination algorithm

Figure: Algorithm 1 $k$-Coverage Determination Algorithm

Algorithm [1](https://arxiv.org/html/2505.20278v1#algorithm1) presents our approach to computing the coverage set with a minimum evidence threshold $k$. The algorithm works in four main stages:

##### Stage 1: Behavior mapping

We first analyze the training data to create a mapping of behaviors for each possible subsequence of the input. For each subset of indices $I$, we record how different subsequences $x_{I}$ behave when paired with their complements $x_{[n]\setminus I}$, essentially mapping each subsequence to a function from complements to outputs.

##### Stage 2: Equivalence class construction

For each subset of indices $I$, we build equivalence classes of subsequences that exhibit functionally identical behavior. Two subsequences are considered equivalent only if: (1) they share at least $k$ distinct complements where they produce the same output, and (2) they never produce different outputs when given the same complement (no contradictions). We use a Union-Find data structure to efficiently track and merge these equivalence classes. The Union-Find (or Disjoint-Set) data structure efficiently maintains a collection of disjoint sets, supporting two key operations: (1) Find - determine which set an element belongs to, and (2) Union - merge two sets.

##### Stage 3: Substitution Graph Construction

We construct a graph where nodes represent input sequences from our training and test sets, rather than the entire domain space (which would be computationally prohibitive for large token sets). We add an edge between two inputs $x$ and $y$ if and only if: (1) they produce the same output, (2) they differ only in one subsequence position set $I$, and (3) their differing subsequences belong to the same equivalence class. This graph represents the space of *safe substitutions* where one can replace a subsequence with a functionally equivalent alternative without changing the expected output. Our implementation uses parallel processing to efficiently construct this graph even for large datasets.

##### Stage 4: Coverage computation

Finally, we compute the coverage set by taking the union of all connected components in the substitution graph that contain at least one training example. This set comprises all inputs that are reachable from the training data through chains of equivalent subsequence substitutions.

### Appendix D Detailed analysis for representation unification experiments

#### D.1 Causal Tracing Methodology

To analyze the causal role of specific hidden representations in our Transformer model, we employ causal tracing, a technique that measures the effect of intervening on intermediate activations during inference [67, 66]. Specifically, we measure the causal effect using the *indirect effect* metric defined in [95]. This methodology allows us to identify which components and positions in the model most strongly contribute to compositional generalization. We illustrate the measurement with 2-Hop task.

Our analysis begins by collecting three types of computational traces:

- 1.
Clean run ($G$): We run the model on a compositional task with input $(x_{1},x_{2},x_{3})$ where the corresponding output is $t=f_{2}(f_{1}(x_{1},x_{2}),x_{3})$.
- 2.
Corrupted run ($G^{*}$): We replace the original input with a corrupted version by changing the first two tokens $(x_{1},x_{2})$ to $(x_{1}^{\prime},x_{2}^{\prime})$, where $f_{1}(x_{1}^{\prime},x_{2}^{\prime})\neq f_{1}(x_{1},x_{2})$. This ensures that the model produces a different final output $t^{*}\neq t$. During this run, we cache all hidden states ${h^{*}}_{i}^{(\ell)}$ for each token position $i$ and layer $\ell$.
- 3.
Patched run ($G[\leftarrow{h^{*}}_{i}^{(\ell)}]$): We run the model on the input from the clean run, but at a specific token position $i$ and layer $\ell$, we replace the hidden state with the corresponding state from the corrupted run.

To quantify the causal effect of a specific hidden state $h_{i}^{(\ell)}$ on the model’s prediction, we measure the Indirect Effect (IE):

$$ $\text{IE}_{h_{i}^{(\ell)}}=\frac{p[\leftarrow{h^{*}}_{i}^{(\ell)}](t^{*})-p(t^ {*})}{p^{*}(t^{*})-p(t^{*})}$ (4) $$

where:

- •
$p(t^{*})$ is the probability assigned to the corrupted output $t^{*}$ in the clean run $G$
- •
$p^{*}(t^{*})$ is the probability assigned to the corrupted output $t^{*}$ in the corrupted run $G^{*}$
- •
$p[\leftarrow{h^{*}}_{i}^{(\ell)}](t^{*})$ is the probability assigned to the corrupted output $t^{*}$ in the patched run $G[\leftarrow{h^{*}}_{i}^{(\ell)}]$

This metric quantifies how much corruption in a particular state affects the overall outcome. An IE value close to 1 indicates that the corruption of the state $h_{i}^{(\ell)}$ to ${h^{*}}_{i}^{(\ell)}$ alone almost completely changes the prediction to that of the corrupted run, suggesting that this state is causally important for the computation. Conversely, an IE value close to 0 indicates that the state has minimal causal impact on the prediction.

In our experiments, we apply causal tracing to analyze different subsets of test data categorized by their $k$-cutoff values, where $k$ represents the minimum evidence threshold required for functional equivalence (as defined in [Sec. 3](https://arxiv.org/html/2505.20278v1#S3) of the main text). This allows us to correlate the strength of functional equivalence evidence with the formation of unified internal representations.

#### D.2 Causal tracing results for each k 𝑘 k italic_k -cutoff value in 2-Hop task

Figure [8](https://arxiv.org/html/2505.20278v1#A4.F8) displays the causal tracing results for the 2-Hop task, broken down by different $k$-cutoff values. We observe that the causal patterns are similar across different $k$-cutoff values, with slight differences in where and how strongly the causal effects manifest in the model.
This suggests that once an example falls within coverage (even with minimal evidence, $k=1$), the model forms internal representations that play similar causal roles in prediction.

Figure: Figure 8: Causal tracing results for the 2-Hop task across different $k$-cutoff values, showing Indirect Effect (IE) scores at each layer and position.
Refer to caption: x12.png

#### D.3 Token set size ablation

We show that the observed patterns of cosine similarity analysis and causal tracing in the 2-Hop task are consistent across different token set sizes $|{\mathcal{X}}|$. For $|{\mathcal{X}}|=70,100,150,200$, we analyze model checkpoints with training dataset size $N=\hat{N}_{\text{req}}(|{\mathcal{X}}|)$ that achieve training accuracy > 0.99. Figure [Fig. 9](https://arxiv.org/html/2505.20278v1#A4.F9) shows the results, indicating strong representation clustering at the lower layers of position $x_{2}$ for all cases. The causal tracing results in [Fig. 10](https://arxiv.org/html/2505.20278v1#A4.F10) show that the clustered functional equivalence representations at the lower layers of position $x_{2}$ play a causal role in determining the model’s final prediction.

Figure: Figure 9: IICG heatmap across different token set sizes, showing consistent representation clustering patterns.
Refer to caption: x13.png

Figure: Figure 10: Causal tracing results showing indirect effect heatmaps for different token set sizes $|{\mathcal{X}}|$.
Refer to caption: x14.png

#### D.4 Task ablation

We show that GPT-2 models trained on Parallel-2-Hop and 3-Hop tasks exhibit the same patterns: clustered functional equivalence representations of intermediate states at specific layers and positions, confirmed through cosine similarity analysis, with causal tracing analysis verifying their role in model predictions. For both tasks, we analyze with $|{\mathcal{X}}|=50$ and examine model checkpoints with training dataset size $N=\hat{N}_{\text{req}}(|{\mathcal{X}}|)$ that achieve training accuracy > 0.99.

Figures [11](https://arxiv.org/html/2505.20278v1#A4.F11) and [12](https://arxiv.org/html/2505.20278v1#A4.F12) show the results for the Parallel-2-Hop task. The IICG patterns reveal strong representation clustering at mid-layers: at positions $x_{2}$ and $x_{3}$ when grouped by $b_{1}=f_{1}(x_{1},x_{2})$, and at position $x_{4}$ when grouped by $b_{2}=f_{2}(x_{3},x_{4})$. Causal tracing confirms the causal role of these clustered representations in the model’s predictions.

Figure: Figure 11: IICG heatmap for Parallel-2-Hop task with grouping strategies based on $b_{1}=f_{1}(x_{1},x_{2})$ (Left), $b_{2}=f_{2}(x_{3},x_{4})$ (Middle), and $t=f_{3}(b_{1},b_{2})$ (Right).
Refer to caption: x15.png

Figure: Figure 12: Causal tracing results showing indirect effect heatmap for Parallel-2-Hop task. Left: perturbation with different $(x_{1},x_{2})$ pair leading to a different $b_{1}$ value. Right: perturbation with different $(x_{3},x_{4})$ pair leading to a different $b_{2}$ value.
Refer to caption: x16.png

Similarly, Figures [13](https://arxiv.org/html/2505.20278v1#A4.F13) and [14](https://arxiv.org/html/2505.20278v1#A4.F14) show results for the 3-Hop task. The IICG patterns exhibit strong representation clustering at mid-layers: at position $x_{3}$ when grouped by $b_{1}=f_{1}(x_{1},x_{2})$, and at position $x_{3}$ when grouped by $b_{2}=f_{2}(b_{1},x_{3})$. Causal tracing again confirms the causal importance of these representations.

Figure: Figure 13: IICG heatmap for 3-Hop task with grouping strategies based on $b_{1}=f_{1}(x_{1},x_{2})$ (Left), $b_{2}=f_{2}(b_{1},x_{3})$ (Middle), and $t=f_{3}(b_{2},x_{4})$ (Right).
Refer to caption: x17.png

Figure: Figure 14: Causal tracing results showing indirect effect heatmap for 3-Hop task. Left: perturbation with different $(x_{1},x_{2})$ pair leading to different $b_{1}$ value. Right: perturbation leading to different $b_{2}=f_{2}(b_{1},x_{3})$ value.
Refer to caption: x18.png

These results demonstrate that the formation of clustered intermediate state representations and their causal role in compositional generalization is a consistent phenomenon across different task structures, supporting the generality of our findings beyond the 2-Hop task.

### Appendix E Derivation of Result 5.1 (power–law lower bound)

##### Problem setting

Let ${\mathcal{X}}$ be a finite token set with cardinality $|{\mathcal{X}}|$.
The target mapping

$$ $f:{\mathcal{X}}^{3}\longrightarrow{\mathcal{X}},\qquad f(x_{1},x_{2},x_{3})=f_ {2}\bigl{(}f_{1}(x_{1},x_{2}),\,x_{3}\bigr{)}$ $$

is a *two-hop* composition of unknown primitives
$f_{1}:{\mathcal{X}}^{2}\to{\mathcal{X}}$ and $f_{2}:{\mathcal{X}}^{2}\to{\mathcal{X}}$.
Write
$b=f_{1}(x_{1},x_{2})\in{\mathcal{X}}$
for the *intermediate state*.
Throughout the proof we impose two assumptions.

- (A1)
Balanced classes:
Each intermediate value $b\in{\mathcal{X}}$ is realized by exactly $|{\mathcal{X}}|$ first-hop
pairs, i.e., the sets
$E_{b}:=\{(x_{1},x_{2})\in{\mathcal{X}}^{2}:f_{1}(x_{1},x_{2})=b\}$
all have size $|{\mathcal{X}}|$ and form a partition of ${\mathcal{X}}^{2}$.
- (A2)
Uniform training sampler:
The training set $D$ contains $N$ triples drawn *uniformly with replacement* from the domain ${\mathcal{X}}^{3}$.

##### Functional k 𝑘 k italic_k -equivalence and learner model

For two first-hop fragments $a,a^{\prime}\in{\mathcal{X}}^{2}$ define

$$ $a\sim a^{\prime}\quad:\Longleftrightarrow\quad f_{1}(a)=f_{1}(a^{\prime}).$ $$

They are functionally $k$-equivalent w.r.t. $D$
(denoted $a\equiv^{k}_{D}a^{\prime}$)
when there exist *$k$ distinct contexts*
$c_{1},\dots,c_{k}\in{\mathcal{X}}$ such that for every $r\leq k$
both $(a,c_{r})$ and $(a^{\prime},c_{r})$ appear in $D$ and
$f(a,c_{r})=f(a^{\prime},c_{r})$. We call each $(a,c_{r}),(a^{\prime},c_{r})$ an *evidence pair*.

The coverage principle by itself is *only a necessity* statement:
outside the $k$-coverage region a purely pattern matching learner’s
predictions are unconstrained.
To convert this into a *sufficient* data condition we adopt an
explicit inductive bias, matching the premise of
Result [5.1](https://arxiv.org/html/2505.20278v1#S5.Thmtheorem1):

Learner assumption:
*Whenever two fragments become linked by *$k$* independent (i.e., pairwise from distinct contexts)
evidence pairs, the learner treats them as functionally equivalent; the
learner also propagates equivalence *transitively* along chains of
such links.*

With this rule in place the relevant structure inside each class $E_{b}$
is the *$k$-evidence graph*: vertices are the $|{\mathcal{X}}|$ first-hop pairs
in the class and an edge connects two vertices whenever the pair is
observed at least $k$ times in shared contexts.
If that graph is *connected* (every vertex reachable from every
other), then every fragment in $E_{b}$ is linked by a
chain of $k$-evidence steps and is therefore recognized as equivalent by
the learner. Hence

> Data sufficiency criterion: If the $k$-evidence graph of *each* class $E_{b}$ is connected, the learner generalizes perfectly to all in-domain (ID) inputs.

This criterion requires *connectivity*, and we aim to derive the condition to yield the connectivity with high probability using Erdős–Rényi model [96, 97].
The minimal dataset size achieving this with high probability is denoted
$N_{\mathrm{req}}(|{\mathcal{X}}|,k)$.

Note that the $k$-evidence graph on $E_{b}$ is the restriction of the substitution graph $\mathcal{G}_{D,k}$ (Def. 3.2) to the vertex set $E_{b}\times\{x_{3}\}$ for any fixed $x_{3}$. Connectivity of every class therefore implies that *every* first-hop fragment lies in the same connected component as some training input, i.e., the entire in-domain set is contained in $k$-coverage. Under the learner assumption, this is both necessary and sufficient for perfect ID generalization, yielding [Res. 5.1](https://arxiv.org/html/2505.20278v1#S5.Thmtheorem1).

#### E.1 Step 1: probability of a single evidence pair

##### Evidence pair probability

Fix two distinct first–hop fragments $i,j\in E_{b}$ and a context $c\in{\mathcal{X}}$. We want to find $p_{1}$, the probability that context $c$ provides an evidence pair for the functional equivalence of fragments $i$ and $j$:

$$ $p_{1}:=\Pr[(i,c)\in D\text{ and }(j,c)\in D]$ $$

Let $q:=1/|{\mathcal{X}}|^{3}$ denote the probability of drawing any specific triple in a single draw. Using the inclusion–exclusion principle:

$$ $\displaystyle p_{1}$ $\displaystyle=\Pr[(i,c)\in D\text{ and }(j,c)\in D]$ $\displaystyle=1-\Pr[(i,c)\not\in D]-\Pr[(j,c)\not\in D]+\Pr[(i,c)\not\in D \text{ and }(j,c)\not\in D]$ $\displaystyle=1-(1-q)^{N}-(1-q)^{N}+(1-2q)^{N}$ (S1.1) $$

For $q\ll 1$ (which holds when $|{\mathcal{X}}|$ is large), we can use Taylor expansion:

$$ $\displaystyle(1-q)^{N}$ $\displaystyle=1-Nq+\frac{N(N-1)}{2}q^{2}+O(q^{3})$ $\displaystyle(1-2q)^{N}$ $\displaystyle=1-2Nq+\frac{N(N-1)}{2}(2q)^{2}+O(q^{3})$ (S1.2) $$

Substituting these approximations:

$$ $\displaystyle p_{1}$ $\displaystyle=1-2\left(1-Nq+\frac{N(N-1)}{2}q^{2}\right)+\left(1-2Nq+2N(N-1)q^ {2}\right)+O(q^{3})$ $\displaystyle=1-2+2Nq-N(N-1)q^{2}+1-2Nq+2N(N-1)q^{2}+O(q^{3})$ $\displaystyle=N(N-1)q^{2}+O(q^{3})$ $\displaystyle=\frac{N(N-1)}{|{\mathcal{X}}|^{6}}+O\left(\frac{1}{|{\mathcal{X} }|^{9}}\right)$ $\displaystyle=\frac{N^{2}}{|{\mathcal{X}}|^{6}}(1+o(1))$ (S1.3) $$

Therefore, in the regime of interest ($N\gg|{\mathcal{X}}|$ but $N\ll|{\mathcal{X}}|^{3}$):

$$ $\boxed{p_{1}=\frac{N^{2}}{|{\mathcal{X}}|^{6}}(1+o(1))}$ $$

Equation ([E.1](https://arxiv.org/html/2505.20278v1#A5.Ex14)) gives an exact expression for the probability (up to lower-order terms) that the *single* context $c$ provides an *evidence pair* for the functional equivalence of fragments $i$ and $j$.

##### Remark on “lucky coincidences”

Because functional $k$-equivalence demands *consistency* across all $k$ evidences, a single coincidental equality $f(i,c)=f(j,c)$ with $i\not\sim j$ can only masquerade as evidence when $k=1$ *and* the dataset lacks any contradicting context $c^{\prime}$. For $k\geq 2$ the joint probability that two *independent* contexts simultaneously produce such coincidences is $|{\mathcal{X}}|^{-k}$ per fragment pair and hence negligible relative to the isolate probability once $N=\Omega(|{\mathcal{X}}|^{2})$. Consequently, the effects of such “lucky coincidences” on the lower bound in [Res. 5.1](https://arxiv.org/html/2505.20278v1#S5.Thmtheorem1) can be neglected.

#### E.2 Step 2: probability of observing k 𝑘 k italic_k evidences for one fixed pair

Having established the probability $p_{1}$ for a single evidence pair in Step 1, we now derive $p_{k}$, the probability that a dataset provides at least $k$ distinct contexts as evidence for the functional equivalence of two fragments $i$ and $j$. This probability will determine the edge probability in the random graph model analyzed in Step 3.

##### Indicators for one fragment pair

Fix two distinct first-hop fragments $i,j\in E_{b}$ and, for each context
(third token) $c\in{\mathcal{X}}$, set

$$ $Z_{ij}(c):=\mathbf{1}\bigl{[}(i,c)\in D\bigr{]}\,\mathbf{1}\bigl{[}(j,c)\in D \bigr{]}.$ $$

Thus $Z_{ij}(c)=1$ exactly when the single context $c$ supplies an
*evidence pair* for the functional equivalence of $i$ and $j$.

##### Single-context success probability

From ([E.1](https://arxiv.org/html/2505.20278v1#A5.Ex14)),

$$ $p_{1}:=\Pr[Z_{ij}(c)=1]=\frac{N^{2}}{|{\mathcal{X}}|^{6}}\bigl{(}1+o(1)\bigr{) },\qquad(|{\mathcal{X}}|\to\infty).$ $$

##### Negatively correlated counts and an i.i.d. surrogate

Because all $N$ draws come from a single multinomial
$\bigl{(}N,1/|{\mathcal{X}}|^{3}\bigr{)}$, the indicators
$\{Z_{ij}(c)\}_{c\in{\mathcal{X}}}$ are *negatively correlated*:
drawing many triples with one context leaves fewer draws for the others.
Negative correlation *decreases* the probability that several
$Z_{ij}(c)$ equal 1 simultaneously. Hence the tail probability for the
true count

$$ $Y_{ij}:=\sum_{c\in{\mathcal{X}}}Z_{ij}(c)$ $$

is *upper-bounded* by the tail of an i.i.d. binomial variable with
the same single-trial success probability $p_{1}$. Concretely, define

$$ $Y_{ij}^{\star}\sim\mathrm{Binom}\bigl{(}|{\mathcal{X}}|,p_{1}\bigr{)},\qquad p _{1}=\frac{N^{2}}{|{\mathcal{X}}|^{6}}\bigl{(}1+o(1)\bigr{)}.$ $$

Then for every real $t$

$$ $\Pr\bigl{[}Y_{ij}\geq t\bigr{]}\leq\Pr\bigl{[}Y_{ij}^{\star}\geq t\bigr{]}.$ $$

Using $Y_{ij}^{\star}$ therefore *overestimates* the chance of
obtaining $k$ or more distinct evidence contexts, which is conservative
for our goal of deriving a lower bound on the required dataset size $N$.

Since $Y_{ij}^{\star}$ is binomial with mean

$$ $\mu:=\mathbb{E}[Y_{ij}^{\star}]=|{\mathcal{X}}|\,p_{1}=\frac{N^{2}}{|{\mathcal {X}}|^{5}}\bigl{(}1+o(1)\bigr{)},$ $$

we may work henceforth with $Y_{ij}^{\star}$ alone; the resulting bounds
apply verbatim to the original $Y_{ij}$.

##### Poisson tail via Le Cam

Le Cam’s theorem [98] states that the total-variation
distance between $\mathrm{Binom}(n,p)$ and $\mathrm{Poisson}(\mu=np)$ is
at most $2np^{2}$. At the scaling that will emerge in Step 3
($N=|{\mathcal{X}}|^{\,2.5-\frac{0.5}{k}}$), one has
$2|{\mathcal{X}}|p_{1}^{2}=2|{\mathcal{X}}|^{-1-\frac{2}{k}}\to 0$ and
$\mu=|{\mathcal{X}}|^{-\frac{1}{k}}\to 0$. Thus

$$ $\Pr[Y_{ij}\geq k]\leq\Pr[Y_{ij}^{\star}\geq k]=\sum_{r=k}^{\infty}\frac{e^{- \mu}\mu^{r}}{r!}\leq\frac{\mu^{k}}{k!}\bigl{(}1+o(1)\bigr{)}.$ $$

This upper bound $p_{k}:=\mu^{k}/k!(1+o(1))$ will be the edge
probability used in the connectivity threshold of Step 3.

#### E.3 Step 3: connectivity inside each equivalence class

With the edge probability $p_{k}$ from Step 2, we now analyze when the $k$-evidence graphs become connected. Recall that under our learner assumption, perfect generalization requires every equivalence class to form a connected component in the $k$-evidence graph. We model this as a random graph connectivity problem.

##### Random graph construction

Fix one balanced class $E_{b}$ of size $n:=|{\mathcal{X}}|$
(Assumption [(A1)](https://arxiv.org/html/2505.20278v1#A5.I1.i1)).
Create a graph $G_{b}$ whose vertices are the first-hop pairs in $E_{b}$, and place an undirected edge $\{i,j\}$ exactly when the pair $(i,j)$ has
been observed in *at least $k$ distinct shared contexts*.
By Step [E.2](https://arxiv.org/html/2505.20278v1#A5.SS2), each potential edge appears with
probability

$$ $p_{k}=\Pr\bigl{[}Y_{ij}\geq k\bigr{]}=\frac{\mu^{k}}{k!}\,,\qquad\mu=\frac{N^{ 2}}{|{\mathcal{X}}|^{5}}.$ $$

##### Why G b subscript 𝐺 𝑏 G_{b} italic_G start_POSTSUBSCRIPT italic_b end_POSTSUBSCRIPT can be approximated as Erdős–Rényi

As mentioned earlier, the dependence among distinct edges in $G_{b}$ arises from the constraint that the total sample size is $N$, which induces a *negative correlation*.
Such negative dependence *reduces* the likelihood of simultaneously
creating many edges.
Consequently, viewing $G_{b}$ as an independent Erdős–Rényi graph
$G(n,p_{k})$ provides a conservative model, and any threshold we
derive for connectivity under independence remains valid (or becomes
easier to satisfy).

##### Classwise connectivity threshold

For Erdős–Rényi graphs, the classical result of
Erdős–Rényi [97] states

$$ $\Pr\bigl{[}G(n,p)\text{ is connected}\bigr{]}\xrightarrow[n\to\infty]{}1\quad \Longleftrightarrow\quad p\geq\frac{\log n+\omega(1)}{n}.$ $$

Setting $n=|{\mathcal{X}}|$ and $p=p_{k}$
yields the requirement

$$ $p_{k}=\frac{\mu^{k}}{k!}\geq\frac{\log|{\mathcal{X}}|}{|{\mathcal{X}}|}(1+o(1)).$ $$

Substituting $\mu=N^{2}/|{\mathcal{X}}|^{5}$ and rearranging gives

$$ $\frac{N^{2k}}{|{\mathcal{X}}|^{5k}\,k!}\gtrsim\frac{\log|{\mathcal{X}}|}{|{ \mathcal{X}}|},\qquad\Longrightarrow\qquad N\gtrsim|{\mathcal{X}}|^{\frac{5k-1 }{2k}}\,\bigl{(}k!\log|{\mathcal{X}}|\bigr{)}^{1/(2k)}.$ $$

Because $(k!\log|{\mathcal{X}}|)^{1/(2k)}=(\log|{\mathcal{X}}|)^{O(1/k)}$
grows only poly-logarithmically, we hide it inside a
$\tilde{\Omega}(\,\cdot\,)$:

$$ $N=\tilde{\Omega}\bigl{(}|{\mathcal{X}}|^{\,2.5-\frac{0.5}{k}}\bigr{)}.$ $$

Since every class must be connected to achieve the data–sufficiency
criterion in the problem setting, we conclude

$$ $\boxed{N_{\mathrm{req}}(|{\mathcal{X}}|,k)=\tilde{\Omega}\bigl{(}|{\mathcal{X} }|^{\,2.5-\frac{0.5}{k}}\bigr{)}}\quad\text{(with high probability).}$ $$

As a remark, we note that Erdős–Rényi theory also shows that if
$N\leq|{\mathcal{X}}|^{\,2.5-\frac{0.5}{k}}/(\log|{\mathcal{X}}|)^{1/(2k)}$
then each $G_{b}$ is *disconnected* with high probability,
so the exponent $2.5-\frac{0.5}{k}$ is in fact *sharp*
(up to poly-logarithmic factors).

### Appendix F Additional results for power-law scaling analysis

#### F.1 Measurement protocol for N req subscript 𝑁 req N_{\mathrm{req}} italic_N start_POSTSUBSCRIPT roman_req end_POSTSUBSCRIPT

To empirically determine the minimum dataset size required for reliable compositional generalization ($N_{\mathrm{req}}$), we develop a measurement protocol that accounts for practical computational constraints while ensuring robustness. For each token set size $|\mathcal{X}|$ and task structure, we test multiple dataset sizes until we identify the threshold point where the model successfully generalizes to the ID test set.

Specifically, our criterion for “reliable generalization” on ID is defined as:

- •
The model must reach ID test accuracy of 0.99 within 100 epochs after achieving training accuracy > 0.99.

This protocol balances several considerations:

- 1.
Training-to-generalization delay: Larger datasets naturally require more iterations to fit training data. By measuring epochs after reaching training accuracy > 0.99, we focus on the generalization gap rather than conflating it with initial training difficulty.
- 2.
Epoch-based measurement: Using epochs rather than raw training steps ensures that the model sees each functional equivalence evidence approximately the same number of times, regardless of dataset size. This provides a fairer comparison across different dataset sizes.
- 3.
Practical time constraints: While indefinite training might eventually yield generalization with smaller datasets, we established a reasonable upper bound (100 epochs post-training convergence) to reflect practical limitations.
- 4.
Measurement precision: For each identified $N_{\mathrm{req}}$, we verified that 75% of this dataset size consistently failed to meet our generalization criterion. This establishes that our measurement error is at most $-\log(0.75)=0.125$ in log scale, providing confidence in the derived power-law exponents.

#### F.2 Measured power-law scaling constants across task structures and model sizes

Using our measurement protocol, we measure the required dataset size $N_{\mathrm{req}}$ across three different compositional structures (2-Hop, Parallel-2-Hop, and 3-Hop) and three model scales (68M, 96M, and 1.5B parameters). For each task structure, we vary the token set size $|\mathcal{X}|$ from 50 to 200, allowing us to observe the scaling relationship.

Table [2](https://arxiv.org/html/2505.20278v1#A6.T2) presents the power-law exponents obtained by linear fitting $\log(|\mathcal{X}|)$ vs. $\log(N_{\mathrm{req}})$ plots, all with $R^{2}>0.99$. The consistency of exponents across model sizes suggests that the observed power-law scaling relates to properties of the compositional tasks themselves, rather than model capacity. This observation aligns with our theoretical derivation in Section 5.1, which predicts that the required dataset size scales at least quadratically with token set size.

**Table 2: Power law exponents for different tasks and GPT-2 sizes, obtained by linear fitting $\log(|\mathcal{X}|)$ vs. $\log(N_{\mathrm{req}})$ plots. $R^{2}>0.99$ for all linear fitting.**
| Model Size | 2-hop | Parallel-2-hop | 3-hop |
| --- | --- | --- | --- |
| 68M | 2.13 | 2.47 | 2.61 |
| 96M | 2.26 | 2.35 | 2.50 |
| 1.5B | 2.28 | 2.17 | 2.60 |

#### F.3 Robustness to hyperparameter variations

Figure: Figure 15: Robustness of power-law scaling relationship to hyperparameter variations in the 2-Hop task with $|\mathcal{X}|=50$. Each line shows the training and test accuracy curves for a different configuration: (1) baseline, (2) reduced learning rate (4e-4, half of baseline), (3) reduced weight decay (0.01, one-tenth of baseline), and (4) changed generalization criteria (test accuracy > 0.95 within 10 epochs after training accuracy > 0.95). $R^{2}>0.99$ for all linear fitting.
Refer to caption: x19.png

To verify that our observed power-law scaling relationship is not an artifact of specific hyperparameter choices, we conduct ablation studies with modified training configurations. Figure [15](https://arxiv.org/html/2505.20278v1#A6.F15) demonstrates that for the 2-Hop task with $|\mathcal{X}|=50$, the following changes did not significantly affect the measured $N_{\mathrm{req}}$ or the derived power-law exponent:

- 1.
Learning rate reduction: Halving the learning rate from 8e-4 to 4e-4
- 2.
Weight decay reduction: Decreasing weight decay by a factor of 10 (from 0.1 to 0.01)
- 3.
Generalization criteria modification: Requiring test accuracy > 0.95 within 10 epochs after training accuracy > 0.95

This robustness to hyperparameter variations suggests that the power-law relationship between token set size and required dataset size is primarily a property of the compositional generalization process, rather than an artifact of specific optimization settings.

### Appendix G Detailed analysis for Non-tree task

This section provides additional analyses that support our findings in [Sec. 5.4](https://arxiv.org/html/2505.20278v1#S5.SS4) regarding the challenges of path ambiguity in the Non-tree task.

#### G.1 Coverage analysis

Figure: Figure 16: Coverage analysis for Non-tree task with $|\mathcal{X}|=50$. The graph shows the percentage of ID test data covered at different $k$ values across various dataset sizes ($N$). Compared to the 2-Hop task ([Fig. 3](https://arxiv.org/html/2505.20278v1#S5.F3), left), Non-tree has significantly lower coverage at equivalent dataset sizes, indicating that path ambiguity impedes the formation of functional equivalence relationships.
Refer to caption: x20.png

[Fig. 16](https://arxiv.org/html/2505.20278v1#A7.F16) demonstrates that with equivalent training dataset sizes, a smaller percentage of ID test examples fall inside $k$-coverage for the Non-tree task compared to the 2-Hop task shown in [Fig. 3](https://arxiv.org/html/2505.20278v1#S5.F3) (Left). This aligns with our theoretical analysis in [Sec. 5.4](https://arxiv.org/html/2505.20278v1#S5.SS4), which predicts that path ambiguity limits the establishment of functional equivalence relationships between input subsequences, as the model cannot generalize across different $x_{2}$ values in the Non-tree structure even when they produce the same intermediate state $b=f_{1}(x_{1},x_{2})$.

#### G.2 Effect of model scaling

Figure: Figure 17: ID test accuracy comparison between GPT-2 (96M parameters) and GPT-2-XL (1.5B parameters) on the Non-tree task with $|\mathcal{X}|=50$, measured 100 epochs after training accuracy exceeds 0.99. Despite the 15x increase in parameter count, the accuracy does not increase.
Refer to caption: x21.png

[Fig. 17](https://arxiv.org/html/2505.20278v1#A7.F17) shows that scaling up the model size to GPT-2-XL (1.5B parameters) does not significantly improve generalization performance on the Non-tree task, even when measured 100 epochs after reaching training accuracy > 0.99. This suggests that the challenges posed by path ambiguity cannot be overcome simply by increasing model capacity, supporting our claim that the limitation is structural rather than related to model capacity.

#### G.3 Representation analysis in successful generalization

For a model that eventually achieved near-perfect ID accuracy (0.96) after extended training (36k epochs, $|\mathcal{X}|=50$, $N=50\text{k}$), we conduct causal tracing analysis to understand how it achieves generalization despite path ambiguity.

Figure: Figure 18: Causal tracing analysis for the Non-tree model after extended training. The heatmap shows indirect effect values across different layer-token positions. Left: perturbation leading to different intermediate state $b=f_{1}(x_{1},x_{2})$. Middle: same $b$ but different $x_{2}$. Right: different $b$ and $x_{2}$.
Refer to caption: x22.png

The causal tracing results in [Fig. 18](https://arxiv.org/html/2505.20278v1#A7.F18) reveal how the model achieves generalization in the presence of path ambiguity. Across all perturbation strategies, the model’s predictions show strong causal dependence on representations at both the $x_{1}$ and $x_{2}$ positions, indicating reliance on direct access to both input tokens rather than an abstracted intermediate computation. This pattern contrasts sharply with the 2-Hop task, where causal effects concentrate primarily at positions corresponding to clustered functional equivalence representations.

This analysis demonstrates that even models achieving high accuracy on Non-tree tasks do so by developing context-dependent representations rather than unified abstractions of intermediate states. The model forms separate computational pathways conditioned on the $x_{2}$ value, rather than learning a single unified representation of the intermediate state $b=f_{1}(x_{1},x_{2})$. This represents a fundamentally different solution strategy compared to the 2-Hop task, with implications for both generalization capability and interpretability.

### Appendix H Detailed discussion on the taxonomy of generalization

In Section [7](https://arxiv.org/html/2505.20278v1#S7), we introduce a taxonomy of generalization that extends beyond the coverage principle. We propose this taxonomy as an initial conceptual framework to disentangle different mechanisms of generalization that are often conflated in the literature. This categorization offers hypotheses for why neural networks succeed or fail at compositional tasks, connecting empirical observations to theoretical principles. We emphasize that the taxonomy is preliminary and that [Sec. H.5](https://arxiv.org/html/2505.20278v1#A8.SS5) outlines its current limits, open questions, and future directions.

#### H.1 Type-I: Structure-based generalization

Type-I generalization occurs when a model succeeds by identifying and utilizing functionally equivalent components based on *how primitive functions are composed*. This form of generalization is precisely what we have formalized and studied via the coverage principle. Crucially, this kind of generalization remains strictly bounded by coverage as defined in Section [3](https://arxiv.org/html/2505.20278v1#S3).

In Type-I generalization, a model learns to recognize when different input fragments yield identical results in shared contexts, allowing it to generalize to new combinations of these fragments. However, without exposure to sufficient functional equivalence evidence during training, the model cannot reliably generalize to novel compositions.

Type-I generalization effectively describes what a pattern matching learner can achieve through the functional equivalence observed by input-output relationships, without requiring abstract variable binding mechanisms. This limitation aligns with the classic argument by Fodor and Pylyshyn [9] and Marcus [37] that connectionist networks lacking explicit variable binding capabilities(^13^1313We expand on the variable binding concept defined in [Sec. 2](https://arxiv.org/html/2505.20278v1#S2) beyond flexibly associating variables with values, and we distinguish between self-replicative expansion (e.g., 2-hop $\to$ 3-hop via Type-III) and complex compositional binding (e.g., substituting noun phrases for nouns), where the latter may require explicit variable binding mechanisms beyond parameter sharing.) cannot exhibit fully systematic generalization.
We introduce this perspective as a conceptual framing of the coverage principle: it describes the ceiling of pattern-based generalization in neural networks that rely on pattern matching rather than symbolic variable binding.

#### H.2 Type-II: Function property-based generalization

Type-II generalization occurs when a model exploits specific properties *intrinsic to individual primitive functions*, enabling generalization beyond patterns observed during training. Unlike Type-I generalization which requires explicit evidence of functional equivalence, Type-II generalization leverages invariant properties that hold for all inputs of the primitive, making the function’s output fully determined by those invariances even in unobserved contexts.

We identify several sub-families of property-based generalization:

- •
Algebraic invariances: commutativity, associativity, and similar properties
- •
Group-theoretic structure: as in Fourier basis representations for modular arithmetic [63]
- •
Input irrelevance: attention sparsity that ignores distractors [81]

The reversal curse [16] exemplifies the layered nature of compositional challenges across multiple generalization types. The coverage principle (Type-I) explains the fundamental failure: training on “$A$ is $B$” provides no functional equivalence evidence for “$B$ is $A^{-1}$”. Property-based approaches like bidirectional training [83] partially succeed by exploiting relationship invertibility (Type-II), using architectural modifications to learn inverse mappings from the same training data. However, recent work [42] reveals deeper representational binding constraints: even though models can exploit inverse mapping properties in idealized conditions (abstract concept-level tasks), they struggle to maintain consistent concept representations when moving to realistic surface-level predictions, where entities switch roles between subject and object positions. This demonstrates how real compositional tasks involve multiple mechanism layers, where achieving one capability may be insufficient due to representational binding limitations.

Type-II generalization fundamentally differs from Type-I in that it can, in principle, transcend the limitations imposed by the coverage principle, allowing models to generalize correctly to inputs that lie outside the coverage of their training data by leveraging invariant properties of the underlying functions. Systematic characterization of pure Type-II extrapolation remains limited and is an important direction for future work.

#### H.3 Type-III: Shared-operator generalization

Type-III generalization emerges through *reuse of identical primitive functions* across different computational positions, e.g., when $f_{1}=f_{2}$ in a multi-hop reasoning task. Unlike Type-I (bounded by coverage) and Type-II (exploiting algebraic properties), Type-III generalization leverages the structural repetition of identical operations.

This mechanism is not unique to Transformers. Recurrent architectures [84] exemplify Type-III generalization through their recurrent weight sharing: the same transformation is applied at each time step, enabling the network to process sequences of varying lengths despite training on fixed-length examples. This architectural inductive bias directly encodes the assumption that the same operation should apply across temporal positions, allowing recurrent architectures to extrapolate to longer sequences [85].

In the Transformer context, Wang et al. [19] demonstrate that Universal Transformer layers [86] enable generalization beyond in-domain data in two-hop tasks, while [87] show improved compositional reasoning with weight-shared layers. These findings suggest parameter sharing as a key enabling mechanism, where a single learned implementation of a function can be applied across multiple contexts.

A prominent manifestation of Type-III generalization appears in depth extrapolation and length generalization tasks, where models generalize to deeper or longer compositional structures than seen during training [99, 100, 101, 102]. While length generalization tasks fundamentally involve applying the same computation to longer inputs (Type-III), successful generalization often requires additional mechanisms like specialized positional encodings that facilitate computation reuse across positions. The observed brittleness of current approaches [103] suggests that such inductive biases are necessary but may not be sufficient for robust systematicity.

In summary, Type-III generalization extends beyond the coverage-bound limitations of Type-I by exploiting identical operations, without requiring the algebraic property understanding characteristic of Type-II. Type-III therefore complements Types I and II, but may still operate without explicit variable binding.

#### H.4 Relationship to prior taxonomies of generalization

Prior taxonomies of generalization in neural networks have primarily categorized the phenomena of compositional generalization rather than the underlying mechanisms. Lake and Baroni [12] distinguish between “mix-and-match” generalization (for small training-test differences) and systematic compositional generalization (requiring abstract rule application). Other frameworks focus on empirical evaluations through benchmarks [23] or decomposing compositional abilities into constituent skills [38].

Our taxonomy differs by categorizing the mechanisms that enable generalization rather than categorizing based on the phenomena. By distinguishing between structure-based pattern matching (Type-I), algebraic property exploitation (Type-II), and shared-operator transfer (Type-III), our framework provides a lens for interpreting why models succeed or fail at certain compositional tasks. This mechanistic approach not only explains observed behaviors but also offers hypotheses about when Types II or III become necessary for certain generalization challenges.

#### H.5 Open questions and future directions

To operationalize this taxonomy, future work could develop diagnostics: coverage ablation tests for Type-I (systematically removing training examples to test coverage boundaries), algebraic identity probes for Type-II (testing whether models recognize properties like commutativity without explicit training), and parameter-sharing ablations for Type-III (comparing shared vs. independent weights across positions). Current examples in this paper are illustrative rather than definitive classifications; real tasks often involve combinations of mechanisms, and our taxonomy provides a scaffold for disentangling them rather than enforcing mutually exclusive categories.

Several fundamental questions remain. First, practical computations often involve mixed ingredients of generalization, spanning multiple types. When classification is ambiguous, we suggest identifying the dominant mix of types that contribute, as most realistic tasks involve combinations rather than pure instances of any single type. Second, identifying the true compositional structure underlying a task can be ambiguous, as Locatello et al. [52] demonstrate regarding multiple valid decompositions. Third, real-world datasets contain heterogeneous computational structures, and it remains unclear how neural networks accommodate this diversity. Fourth, none of the three mechanisms solves the variable binding problem, and devising diagnostics and architectures for binding remains crucial.

Future work could explore connections to complementary frameworks:

- •
Minimum Description Length [73]: Type-II may compress regularities that lower description length. Similarly, Type-III can be viewed as compression through parameter reuse.
- •
Formal language learning [104, 105]: Connections to grammatical inference and automata learning
- •
Cognitive science [106]: Human compositional learning strategies that may inspire architectural innovations

This taxonomy is not intended as a complete classification but rather as a conceptual framework to organize our understanding of generalization mechanisms and stimulate further research into the fundamental capabilities and limitations of neural networks on compositional tasks. Ultimately, developing architectural and optimization strategies that enable neural networks to leverage all three types more robustly and ultimately addressing the variable binding problem represents an important frontier for addressing the longstanding challenge of systematicity in connectionist systems.

### Appendix I Partial computation observation drives the alignment of functional equivalence representation and vocabulary space

In this section, we investigate how exposure to partial computations affects the interpretability of intermediate state representations through vocabulary space alignment. We compare two training conditions on a modified 2-Hop task with $|\mathcal{X}|=50$ and $N=10\text{k}$, after 40k epochs of training:

- 1.
Standard Training: $f_{1}\neq f_{2}$, model only sees complete two-hop examples $(x_{1},x_{2},x_{3})\mapsto t$.
- 2.
With Partial Computation: $f_{1}=f_{2}$, model additionally sees all possible partial computations $(x_{1},x_{2})\mapsto b$ where $b=f_{1}(x_{1},x_{2})$ (2,500 partial examples, not counted toward the $N=10\text{k}$ two-hop training data).

To assess interpretability, we measure the Mean Reciprocal Rank (MRR) of intermediate state representations when projected to vocabulary space using the unembedding matrix. Low MRR indicates that the model’s internal representation of intermediate state $b$ aligns with the corresponding vocabulary token.

[Fig. 19](https://arxiv.org/html/2505.20278v1#A9.F19) shows a striking contrast between the two conditions. Under standard training, the MRR score remains very high throughout training, indicating that intermediate representations are not aligned with vocabulary space despite the model successfully learning the compositional task. However, when partial computations are included, the MRR score becomes very high, demonstrating clear vocabulary alignment.

Figure: Figure 19: MRR scores for intermediate state representations projected to vocabulary space. Left: Standard training ($f_{1}\neq f_{2}$, no partial computation) shows very high MRR regardless of position and layer. Right: Training with partial computation ($f_{1}=f_{2}$, with partial examples) shows MRR of 0 in layers 3 to 8 at position $x_{2}$, indicating strong vocabulary alignment.
Refer to caption: x23.png

This experiment suggests that logit lens interpretability is orthogonal to functional equivalence representation formation. A model can develop functionally correct intermediate representations that enable compositional generalization while remaining completely uninterpretable through standard vocabulary projection techniques. Interpretability via logit lens requires explicit vocabulary anchoring through exposure to partial computations that map intermediate states to vocabulary tokens.

This finding has important implications for mechanistic interpretability research: the absence of interpretable representations through logit lens does not indicate the absence of structured internal computation. Furthermore, it suggests that interpretability techniques may need to account for how training data shapes the alignment between internal representations and vocabulary space, rather than assuming such alignment emerges naturally from task performance.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: 1. If the task structure is more complicated, would observing robust functional equivalence still be enough for compositional generalization? Wouldn't task complexity challenge the model's understanding of the task, resulting in training failure?

2. Is there any equivalent empirical observation where compositional generalization requires robust observation of functional equivalence in a real-world NLP dataset?

3. Would the formulation in the paper generalize to stochastic functions and approximate functional equivalence?
soundness: 3
strengths: 1. This paper studies an important problem of the compositional generalization of language models.

2. The experiments include various settings of practical relevance.
summary: This paper formulates functional equivalence as the condition where two sets of tokens produce the same output in the same context. The experimental results demonstrate that the model's performance and internal representation of these equivalences get stronger as more of these functional equivalences occur in the training data. The paper also analyzes the scaling law (required training data size depends on the vocabulary size), the effect of ambiguous composition, and the same phenomenon in CoT training.
weaknesses: 1. The results are limited to small synthetic task structures.

2. The settings require a deterministic function and strict functional equivalence, which may be too restrictive in a real-world NLP dataset.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 2
questions: What are the class of real-world problems or tasks that being good at pattern matching helps solve? Is it supposed to capture logical reasoning? Why this particular logical reasoning task versus another (like syllogisms or SAT problems)?
soundness: 4
strengths: - At a high level, thinking about generalization in terms of many-to-one functions seems like it clearly captures a kind of task-level generalization. Completing the task correctly requires non-trivial logical reasoning. The task has the nice properties that (1) it is possible to get 100% accuracy when correctly applying logical reasoning / a graph algorithm and (2) the LLM never sees the exact problem instance it is evaluated on.
- The empirical results in the paper strongly support the narrative presented. The setups of the experiments are thoughtful, and the analysis is suitable for the questions addressed in the paper. I would say the first results (that more examples of an invariance are helpful) is not very surprising, but I learned a lot from the second through fourth analyses (scaling laws, non-tree tasks, and CoT).
summary: This paper is about when LLMs can learn many-to-one (or, equivalently, non-injective) maps. A many-to-one map is a function such that two different inputs yield the same output. All maps are deterministic. In their experiments, an LLM is trained on many examples of such functions (sometimes composed with each other) and is asked to produce outputs on unseen inputs. For example, if we see $f_1(a) = f_1(b) = c$ and $f_2(f_1(b), d) = e$, we can infer that $f_2(f_1(a), d) = e$ as well, without having seen this particular example before. 

They use many-to-one maps as a formalization of what pattern matching means in LLMs. They then create quantifiable tests for when pattern matching is or is not happening. They also explore how data requirements scale with the complexity of the task, and how the amount of computation necessary to learn pattern matching scales with the size of the input vocabulary. Each section of the paper is summarized as follows:

- Their first experiments show how the number of times an invariance is observed affects the test accuracy on the many-to-one maps. Despite the fact that just two observations of an invariance is sufficient to implement an algorithm that solves the task perfectly, the LLM only begins to generalize well until after more examples of the invariance are seen (3+, depending on the amount of training).
- They next develop a metric for measuring how well internal representations capture shared states. In particular, one might hope that if two function inputs lead to the same output, the internal representations would be similar after a few layers. Similarly, if two function inputs lead to different outputs, they internal representations should be different at all points. They capture this by measuring cosine similarity between inputs that induce the same output and cosine between inputs that induce different outputs and then taking the difference between these two quantities. They then show that the models trained on their many-to-one task exhibit high values on the metric.
- They next consider how much data should be needed to learn the task, for a given input vocabulary. They show that, depending on how many examples are needed to confirm an invariance, the number of examples needed scales as polynomial in the size of the domain, with exponent between 2 and 2.5. By scaling the input size, they verify empirically that these scaling laws hold.
- When the function composition structure is more complex (the computation graph is not a tree, and is instead some general directed graph), they show the LLMs do not perform well. This is because it is harder to generalize when the same token is used for multiple different arguments to a function.
- They also train the models to output intermediate computations and find that it leads to more data-efficient generalization. However, when learning with general graphs rather than trees there is still no generalization.
weaknesses: - I found the exposition introducing the problem to be a bit confusing. It wasn’t clear to me whether pattern matching is a desirable or undesirable property of transformers (is it capturing overfitting or generalizing?) The abstract suggests that surface-level pattern matching is bad, but perhaps that deeper pattern matching (which survives multiple logical steps) is a good thing.
- I am also confused about why it is interesting to understand pattern matching in LLMs. I’m not sure how the toy problem is supposed to generalize to other tasks, or shed insight into broad phenomena around LLM reasoning. The introduction did not really have examples of pattern matching in real-world LLM uses, so this added to the confusion. There were many citations supposedly about pattern matching, but not any explanation of how we are supposed to imagine pattern matching works beyond the toy problems in this paper itself. I believe there could be a good motivation for studying this problem, but I don’t get it from this paper, and I’d like the authors to explain.
- I think there could be more discussion of what makes the non-tree case hard. Is there not a way to reduce the non-tree task to the tree task? Or is generalization impossible because of the same token is used for multiple arguments.
- Another minor critique I have is about terminology: “functional equivalence” to me suggests that two functions are the same. I think “functional invariance” is a clearer term?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Pattern matching is generally defined in terms of substitution rules (i.e., $a * (b + c) \to a * b + a * c$. Is the notion of pattern matching you define equivalent to unbounded substitution rules (with an unlimited number of variables on each side of the $\to$)? Is it a generalization? Is it a subset? A discussion of this would help ground your definition in the context of existing notions of pattern matching.

What is the purpose of holding out 30% of inputs and having a test condition where you add a new one in? In my understanding, this task is impossible to perform above chance on, as the primitives are defined as random tables.
soundness: 3
strengths: The domain setup seems to eliminate other potential sources of information cleanly. The definition of functional equivalence and specifically k-equivalence are simple and naturalistic definitions.

The large sweep over a variety of dataset sizes is also helpful for determining the role of data access.
summary: This paper characterizes “pattern matching” in sequence-to-sequence tasks as the identification of particular equivalences between pairs of certain input variables in sequences (subsequences of the input sequence), when all else is held equal. They investigate the ability of models to learn this kind of information by creating a synthetic domain where no other information exists, specifically by framing the problem as the composition of binary functions of the input, each of which is a random lookup table. In general, they find that transformers appear to be using this kind of pattern recognition when trained on this kind of data; but only when these equivalences appear several times. In general, in situations where such an equivalence is found, evidence can be found in intermediate layers for clustering. They develop a scaling law for the data needed to perform this kind of pattern matching. Additionally, they discover that having a non-tree-structured computation graph (where the same input variable can affect the output via multiple paths), causes pattern recognition to become much harder.
weaknesses: The abstract and first paragraph of the introduction do not make it clear enough that “pattern matching" is undesirable. The first sentence could be read as “pattern matching" performed by LLMs as being too surface level. This reading recontextualizes later uses of the term to be neutral rather than negative, confusing such a reader. It should be made more clear that “pattern matching" specifically is being used to exclusively refer to undesirably syntactic/surface level heuristics.

"Functional equivalence, i.e., substituting input fragments observed to result in identical outputs in shared contexts” (used in the abstract and introduction lede) should be rephrased as, by itself, this is too vague to communicate what it means to someone who has not read the paper.. Perhaps something like “functional equivalence, i.e., identifying pairs of subsequences of inputs that consistently lead to identical results when the rest of the input is held constant.”

“Tightly ordered by” is used several times, but as far as I can tell is not a standard term. I think a term like “well predicted by” would be more standard and thus easier to read.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: - For clarification, how is k computed if there is functional equivalence between more than two subsequences?
- I'm curious what might happen if the models are trained on a mixture of different compositional tasks, or a mixture of compositional/non-compositional tasks? IMO this potentially captures the nuanced structures in natural languages, in which certain aspects are strongly compositional and others less so. Without explicit task cues, how would this change the learned strategy? Would functional equivalence be learned earlier or later? Would models still develop some form of context/task-dependent functional equivalence?
soundness: 4
strengths: - This work makes a significant contribution in providing a formalization to the boundary of pattern matching and compositional generalization.
- The paper is dense but I find it a good read. I appreciate that the authors studied a range of important issues beyond the base setting within the task suite, including testing two architectures, data/model scaling, interpretability, tasks with different compositional structures, and CoT.
- The results make several interesting implications for the capabilities of larger models.
summary: This work presents a formalization of pattern matching by quantifying evidence for functional equivalence. The authors systematically study how strength of functional equivalence in the data leads to different kinds of success and failures in compositional generalization tasks. The formalization is accompanied by empirical evidence with both Transformers and mamba architectures on data scaling, learned internal representation of functional equivalence, and the role of CoT on a set of synthetic compositional generalization tasks. The results yield important insights on the limitations of compositional generalization supported by pattern-matching behavior, including generalizing to in-frequent data and multi-hop problems.
weaknesses: - I think it would be good if the implications for specific LLM failures are discussed in more detail, as well as more discussions of whether certain aspects of the formalization would/would not apply given how natural language data may differ in properties studied in the synthetic settings. Though I understand this could be in part due to the space limit.


Decision: Accept (Poster)