Characterizing Pattern Matching and Its Limits on Compositional Task Structures
Authors: Hoyeon Chang
Jinho Park
Hanseul Cho
Sohee Yang
Miyoung Ko
Hyeonbin Hwang
Seungpil Won
Dohaeng Lee
Youbin Ahn
Minjoon Seo
Venue: ICLR 2026 Poster (2026)
Keywords: pattern matching
compositional generalization
functional equivalence
coverage
path ambiguity
mechanistic interpretability
Primary area: interpretability and explainable AI

Abstract: Despite impressive capabilities, LLMs' successes often rely on pattern-matching behaviors, yet these are also linked to OOD generalization failures in compositional tasks.
However, behavioral studies commonly employ task setups that allow multiple generalization sources (e.g., algebraic invariances, structural repetition), obscuring a precise and testable account of how well LLMs perform generalization through pattern matching and their limitations.
To address this ambiguity, we first formalize pattern matching as 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.
Then, we systematically study how decoder-only Transformer and Mamba behave in controlled tasks with compositional structures that isolate this mechanism.
Our formalism yields predictive and quantitative insights:
(1) Instance-wise success of pattern matching is well predicted by the number of contexts witnessing the relevant functional equivalence.
We prove a tight sample complexity bound of learning a two-hop structure by identifying the exponent of the data scaling law for perfect in-domain generalization.
Our empirical results align with the theoretical prediction, under 20× parameter scaling and across architectures.
(3) Path ambiguity is a structural barrier: when a variable influences the output via multiple paths, models fail to form unified intermediate state representations, impairing accuracy and interpretability.
(4) Chain-of-Thought reduces data requirements yet does not resolve path ambiguity.
Hence, we provide a predictive, falsifiable boundary for pattern matching and a foundational diagnostic for disentangling mixed generalization mechanisms.

Published as a conference paper at ICLR 2026
CHARACTERIZING PATTERN MATCHING AND ITS LIMITS ON COMPOSITIONAL TASK STRUCTURES
Hoyeon Chang'
Jinho Park
Hanseul Cho
Sohee Yang²
Miyoung Ko'
Hyeonbin Hwang!
Seungpil Won
Dohaeng Lee
Youbin Ahn?
Minjoon Seo
KAAIST AI
UCL
LG Al Research
(retapurayo, binlepain178, jhs4015, minjoon] Skaist
ABSTRACT
Despite impressive capabilities, LLMs' successes often rely on pattern matihing behaviors, yet these are also linked to OOD generalization failures in compositional tasks. However, behavioral studies commonly employ task setups that allow multiple generalization sources (e.g., algebraic invariances, structural repetition), obscuring a precise and testable account of how well LLMs perform generalization through pattern matching and their limitations. To address this ambiguity, we first formalize pattern matching as functional equivalence, i.e., identifying pairs of subsequences of imputs that consistently lead to identical results when the rest the input held constant. Then, we systematically study how decoder-only Transformer and Mamba behave in controlled tasks with compositional structures that isolate this mechanism. Our formalism yields predictive and quantitative insights: (1) Instance-wiz wise success of pattern matching is well predicted by the number of contexts witnessing the relevant functional equivalence. (2) We prove a tight sample complexity bound of learning two-hop structure by identifying the exponent of the data scaling law for perfect in-domain generalization. Our empirical results align with the theoretical prediction, under 20x parameter scaling and across architectures. (3) Path ambiguity is structural barrier: when variable influences the output via multiple paths, models fail form unified intermediate state representations, impairing accuracy and interpretability. (4) Chain-of Thought reduces data requirements yet does not resolve path ambiguity. Hence, we provide a predictive, falsifiable boundary for pattern matching and foundational diagnostic for disentangling mixed generalization mechanisms.
INTRODUCTION
Despite the remarkable performance of large language models (LLMs) (Brown et al., 2020; Touvron al., 2023), compositional generalization studies suggest that the core mechanism of generalization might be "pattern matching," i..., models learning local statistical regularities between input fragments and outputs in some cases (Loula al., 2018: Johnson et al., 2017: Berglund al., 2024: Wang et al., 2024a; Mirzadeh et al., 2025; Keysers et al., 2020; Csordás et al., 2022). However, behavioral studies commonly employ task setups that allow multiple generalization sources (e.g., algebraic invariances. structural repetition), discussing pattern matching without precise definition and diagnosing it post- hoc rather than characterizing predictively. As a consequence, remains unclear which behaviors should be counted as pattern matching and which should not, thereby obscuring constructive and testable account of its boundary.
To make this notion precise, we (1) introduce data-centered formalism for pattern matching and (2) systematically study how modern architectures like decoder-only Transformers (Vaswani et al., 2017; Radford et al., 2018; 2019) and Mamba (Gu & Dao, 2024) perform generalization through
"qqual contribution.

---

Published as a conference paper at ICLR 2026
Functional Equivalence Observation
Substitution Graph
Coverage
Za
(
fi
fa
(211 T2g ma)
(01, 22, 2/s)
(#1, (21,32223) 23)
(1
(21 22 wa)
(e) 22 x5)
(eL. 25) (ff
Figure Illustration of functional equivalence. Left: In two-hop task (21, T2, 22s) + with t fa(fi (21, 23), two fragments (2) and (zí, x2) satisfying fi(z1, = f (2 x25 b consistently yield the same final output when combined with the same context 23, supporting their functional equivalence. Right: Among all possible inputs (few shown), draw edge between any two inputs that differ only by functionally equivalent fragments form substitution graph. Then, coverage is of observed inputs (highlighted as blue) and all inputs connected to them. We define pattern matching as type of generalization that occurs inside the coverage, harnessing functional equivalence.
pattern matching. Specifically, we first propose a model-agnostic and data-centric definition of pattern matching by formalizing the substitution of input patterns observed to result in identical outputs (Def. 3.1; henceforth, we use pattern matching as equivalent to functional-equivee wewp:raaeleeuuivleeeeeeeeeee -based generalization). This induces coverage boundary (Def. 3.2): learning relies only on such evidence, there is no hope to expect any reliable predictions for the test inputs unreachable by these substitutions.
in shared contexts as rnncciionl-eqiivllennn
Moreover, to isolate and study nattern-machhing behaviors, we use controlled setups that deliberately remove other sources of generalization and make functional equivalence the primary available mechanism. With these setups, our formalism offers predictive and quantitative insights about the limitations of pattern matching. To the best of knowledge, these have not been well characterized yet in prior works:
The success in generalization is well predicted by the number of supporting contexts that witness the relevant functional equivalence. Mechanistically, Transformers seem to implement the functional equivalence by clustering intermediate representations at specific layers/positions. The strength of the clustering aligns with the evidence strength (Sec. 5).
We prove a tight sample complexity bound of pattern matching on a two-hop structure by identifying the exponent of the data scaling law (in terms of the token set size) which is necessary and sufficient to achieve perfect in-domain generalization (Theorem 6.1). We find that the measured power-law exponent agrees with theoretical bounds, remains stable under roughly 20x parameter increase (from 68M to 1 1.5B) for GPT-2 (Radford et al., 2019), and also holds for Mamba (Gu& & Dao, 2024) architecture (Sec. 6).
When the els fail to form unified intermediate state representations. Our analysis reveals that they instead develop context-dependent state representations, impairing both generalization and interpretability (Sec. 7).
variable influences the output along multiple computational paths, mod-
Mhain-of-Thoughee (CoT) supervision (Wei et al., 2022) does not completely resolve the path ambiguity without observing nearly exhaustive in-domain combinations, although reduces the data requirements to some extent (Sec. 8).
Finally, we situate this characterization of pattern matching within a mechanism- taxonomy of generalization mechanisms, proposing two additional distinguishable mechanisms of generalization in compositional tasks: property-based and shared-operator generalization (Sec. 9.2 and App. I).
Our formalism opens several research directions with practical implications (e.g.. targeted data augmentation to maximize coverage) and motivates expansion to broader tasks and architectures, as well as systematic studies of how pattern matching interacts with other generalization mechanisms. Overall, study provides a predictive, falsifiable boundary for what can be achieved through pattern matching alone and a foundational diagnostic for disentangling mixed mechanisms in modern neural networks.
2

---

regimes grounded in our Published as a conference paper at ICLR 2026
2
RELATED WORK
Pattern matching behaviors of LLMs on compositional tasks. It is well perceived that pattern matching alone is inadequate for systematic generalization (Fodor & Pylyshyn, 1988), and modern LLMs display generalization abilities that seem to be far beyond what pattern matching alone can do, as measured by their remarkable performance on complex benchmarks (OpenAI, 2023). However, growing body of work has consistently reported that LLMs still fall short on benchmarks designed to test compositionality (Hupkes et al., 2020), including mathematical reasoning (Mirzadeh et al., 2025), multi-hop reasoning (Yang et al., 2024; Wang et al., 2024a), and more (Lake & Baroni, 2018; Kim & Linzen, 2020; Csordás et al., 2022; Dziri et al., 2023). This gap between their capabilities and pattern- matching behaviors on compositional tasks calls for principled framework to define what pattern matching is and to what extent a model's behavior can be attributed to pattern matching, but is mostly discussed with behavioral studies under the context of a specifically designed benchmark. Our work addresses this gap by formally defining pattern matching, and we systematically analyze models' behaviors with controlled tasks that are designed to isolate framework.
Mechanistic interpretability. Mechanistic interpretability studies aim to understand how sub- mechanisms implement models' behaviors (Elhage et al., 2021; Olsson et al., 2022; Nanda et al., 2023; Elhage al., 2022). Recent work analyzes how Transformer components lated to certain behaviors (Meng et al., 2022; Hanna et al., 2023; Goldowsky-Dill et al., 2023), In particular, it is reported that in-domain compositional generalization can emerge through grokking, with identifiable intermediate state representations inside Transformers (Wang et al., 2024a). Our framework complements these works by providing mechanistic insights about pattern matching, Our findings also explain why standard interpretability techniques like logit lens (nostalgebrais 2020; Belrose et al., 2023) may fail to identify state representations models trained on tasks with path ambiguities.
causally re-
3 FORMALIZING PATTERN MATCHING WITH FUNCTIONAL EQUIVALENCE
We now develop formal framework for pattern matching. We first provide an intuitive illustration with a two-hop structure, then generalize to arbitrary fixed-length sequeeee-equeece tasks.
Imagine learner observing data determined by f 223 + X. The input sequence of three discrete tokens and the output a single token, where each token chosen from a finite set X Suppose (unknown to the learner) that factorizes as the composition of two primitive functions, ((x) = f2(J((r) 22), 23), where /i : X²2 + X' and /2 X + X, as illustrated in Fig. 2a. How can the learner generalize by only seeing the input-output patterns?
(æ1, 22, Z3) E X is
Our key intuition is that a learner exploits the underlying patterns only when two frag- ments of inputs are observed to behave identically. For instance, assume that two fragments (x1, x2), (x', x.)) E X²2 give the same implicit intermediate state upon the application of /1, i.e., fi x2) f1(1 x/)) = b. These fragments behave identically regardless of context, i.e., they functionally equivalent: for all Ø3 E X. f 23) = f(r 224 22). If observations consistently support their equivalence, i.e., f (2, va) [a +22 233) for observed 2y values, this equivalence can be supported (Fig. Left). Intuitively, the learner would harness this equivalence pattern to predict [z 242, ,²),, provided the training set contains
Equivalently, the learner can utilize the observed functional equivalence to correctly infer the output of unseen input, if can reach an observed input by 'safe substitutions' (edges in the substitution graph) supported by observations (Fig. 1 Right), which we define as a pattern matching. Coverage set of such inputs that are reachable from an observed input through chains of functionally equivalent substitutions. Then, coverage sets boundary for what can be achieved by solely relying on substituting observed, equivalently behaving patterns. In other words, a learner can only generalize inside the coverage when it relies on functional equivalence, which we will define as pattern matching.
We now formalize these concepts for an arbitrary fixed-length task with an arbitrary set of discrete sequence observations. We restrict our attention to single-token prediction tasks defined as a de-
Forr brevity, use shared token set X' in most parts of this paper. A more general notion using position- specific domains (e.g.. 'X,") can be used; e.g., see App. F.1.
3

---

Published as a conference paper at ICLR 2026
terministic mapping f : X + X, where X' is finite set of tokens. We also consider fixed observation set D C X² a collection of inputs that are allowed to be observed by the learnrr Write = (Zi,...., [x) E X and, for subset C [e] == {l...., E). let æ, == (zi)ies be subsequence of a. 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 in [4]. Consider any set S C X2 of input sequences. 2 Given pair of subsequences a, a' E x211,, we say a pair of inputs {z, x²} to be an I-co-occurrence of a and a' in S if it satisfies fæ, x²} C S and
a. "(q/-- Also, the subsequences a and a' are said to be functionally k- 2 = a', and x TM
equivalent at 7 in S and denoted by a =] (D.k) a', if satisfies:
(Sufficiency of co-occurrences.) There are or more distinct T-co-occurrences of a and a' in S: 2. (Consistency.) Every /-co-occurrence {æ, } of a and a' in S satisfies f(x) - f(x').
In other words, two subsequences are functionally k-equivalent if they behave identically in the same contexts at least & times. The hyperparameter lo represents the strength of evidence required to establish functional equivalence between two subsequences. The minimum value corresponds to the weakest form of evidence, meaning 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 substitution graph: Let (DD,) (V, E) be an undirected graph with vertex set V = x' of all possible inputs. Two vertices æ, x² E V are connected with an edge in and only if there exists an index set / C [4] such that 27 = (D.k) {x, x') } is an I-co-occurrence (in V) of pair of functionally k-equivalent sequences of Fig. 1, special case where k 1. With this substitution graph G(D,k), formally define the k-coverage as set of inputs which are connected to at least one observed input as follows:
in D. This process is illustrated on the right side
Definition 3.2 (h-coverage). The k-coverage of D X denoted by Covery (D), is the set of all inputs in X2 connected an æ D with a path in the substitution graph (D..).
Note that the notion of coverage is stricter condition of the canonical definition of in-domain (ID), which is obtained by random train/test split (Wang et al., 2024a) or taking combinations of observed internal computations (Dziri et al., 2023). In Sec. 5, we demonstrate that learners may not necessarily generalize on data that are classified as ID in a canonical sense, but coverage can precisely explain when and why this occurs. We also emphasize that coverage is property of dataset and is independent of model architectures and learning algorithms, and we demonstrate that the predictions made by our framework are invariant across model architecture and scale in Sec. 6 and 7. Finally, k-coverage can be algorithmically determined for any fixed-length discrete sequence tasks (Alg. 1), which we use for the analyses in the following sections.
Now, we formally define pattern matching as a kind of generalization that is done by substituting functionally k-equivalent fragments of inputs, whose boundary is precisely the k-coverage defined above. This formalization enables us to predict, before testing, which inputs will be reliably handled through pattern matching and which require additional mechanisms. other words, we view pattern matching as possible only within k-coverage, and generalization outside the coverage requires generalization mechanisms other than pattern matching, which we discuss in Sec. 10 and App. I. In the following sections, we draw systematic picture of how task structure, dataset, and model size interact to determine the success and failure of pattern matching through controlled setups, leading us to important and nontrivial insights.
4 EXPERIMENTAL SETUP
Dataset construction. We construct four synthetic tasks with different structures: 2- HOP, PARAL- LEL 2-HOP, 3-HOP, and NON- TTRE (Fig. 2). To isolate functional ciwloonalllvvvlleeeeeeoooo based generalizations, we randomly create ground-trui -ruth mappings from product space of token sets to control the generaliza- tion sources not attributable to compositional structures (i.e., commutativity). We explain the dataset
"The set S can be any subset of the whole domain, c.g., x itself, the train dataset D, or whatever clse.
For undirected graph G, two vertices u. v are connected if & contains path hetween u and
4

---

Published as a conference paper at ICLR 2026
f2
b1
b2
f2
2a
22
F3
21
(a) 2-HoP
(b) PARALLEL 2-HOP
(c) H-
(d) NON-TREE
Figure 2: Four synthetic task structures we study.
construction process using 2-Hor task (Fig. 2a), (I1, rz) + with t t= f2(f((11,, (11, ..)) as an example. We construct training datasets by defining token set with size |.X and randomly defining two mappings for the primitive functions fi X² > X' and f2 222 - X. We mark fraction Pseen = 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 training dataset. See App. B.1 for more details the dataset construction process.
Training& & evaluation. Following Wang et al. (2023), train randomly initialized GPT-2 (Radford et al., 2019) models with 8 layers, 12 heads, and 768 dimensions as a base model (see App. B.2 for details). We construct two evaluation sets, each with 2,000 instances: (1) ID Test Set all primitive function applications (e.g.. fi (11, x22) and (2 23) in 2-HOP task) are observed during training, but their specific combination was unseen. (2) Out-of-coverage (canonical OOD) Test Set: least one primitive function application is never observed during training, which is used as a control group.
5
QUANTITATIVE ANALYSIS OF PATTERN MATCHING IN TRANSFORMERS
5.1
EVIDENCE STRENGTH IS TIGHTLY ALIGNED TO PATTERN MATCHING SUCCESS
PATTERN-MATCHING
Dataset
80
50k
Accuracy
0.8
% Covered
25k
60
25k
SK
40
5k
0.2
20
2.5k
k-cutoff
Figure 3: Left: Percentage of covered ID data depending on & values and dataset size (N). for 2-Hop task
(IA') 50). Right: Test accuracy depending on k-cutoff values for 2- HOP task (|X' = 50, =110k). Each line represents different training checkpoint. Note that out-of-coverage (l 0) accuracy remains chance level (== 1/50) regardless of training time. The below show the number test data each k-cutoff value.
We first analyze the correlation between k-coverage and ID generalization performance of the GPT-2 model. To this end, we implement and release task-agnostic coverage determination algorithm (see App. C) that can be applied to diverse compositional structures. Then, we analyze what fraction of ID test data of 2-HOP task with | 50 lies inside k-coverage, depending l and dataset size N. Fig. 3 (Left) shows that, at N = 5k, every ID test example is already covered with minimal evidence
1). Hence, an ideal scenario where single witness of functional equivalence suffices, training with the dataset as small as N 5k will lead to perfect ID generalization.
However, we demonstrate our experiments that minimal coverage (i.e., k = 1) alone is practically insufficient for ID generalization. To demonstrate this, let us fix training dataset D and define the k-cuutof of each input sequence as the lowest value of & for which an input lies in k-coverage, measuring the strength of evidence for functional equivalence. For example, k-cutoff of means that an example inside coverage with = 3 but not with = For -ft-of-coverage data, we define k-cutoff as O. Then, for the 2-HOP dataset with N 10k, classify each ID test instance

---

Published as a conference paper at ICLR 2026
according its k-cutoff, and track the aceuracy development of the GPT-2 model for each group across 50k training epochs. As shown in Fig. 3 (Right), ID test accuracy shows a strongly positive correlation 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.
These results yield two important insights. First, successful ID generalization in practice requires a robust coverage so the model can confidently identify and utilize functional equivalence relationships. The parameter effectively quantifies this evidence strength, directly impacting generalization speed and reliability. Second, while our experiments use uniformly sampled datasets, the results can explain why models struggle with generalizing long-tail distributions in imbalanced real-world data (Mallen et al., 2023; Kandpal et al., 2023; Chang et al., 2024). Despite technically being in-distribution, rare combinations naturally receive limited evidence of functional equivalence (low k), effectively and practically placing them outside the coverage. We believe that our insights will motivate future research on targeted data augmentation strategies to maximize k-coverage.
5.2
LATENT REPRESENTATION CLUSTERS DRIVE PATTERN MATCHING ON COVERAGE
Layer
Layer
Layer
Layer
0.3
IICG
Layer
0.2
Layer
Layer
-5.0
-2.5
0.0
-2.5
255
-2.5 0.0
0<k<3
k-3
k>3
k=0
0<k<3
k>3
k-0 0
Figure 4: Left: Heatmap of Intra-Inter Cosine Gap (ICG) across layers and positions, sliced by k-cutoff. Higher IIGG 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 position za and layer 3. Datapoints are classified by their intermediate states fi 22).
Next, we investigate how the model internally represents functional equivalence for k-covered inputs. Specifically, we inspect GPT-2 trained on H-H task ((X') 50, N 10k) for 50k epochs (corresponding to the yellow line in Fig. 3 (Right)).* 4 We observe that when a model successfully generalizes 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 metric that captures how distinetly 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 = fi (1 .2) (coS)mma,, and those that do not (cOSiner)) for each position and layer of the model. We term this difference the intra-inter cosine gap IICG cO8 ioS where higher values indicate stronger within- group clustering relative to between-groue separation. Fig. 4 (Left) reveals a positive correlation: higher k-cutoff values yield higher IICG scores at certain positions. indicating that stronger functional equivalence evidence leads to more coherent internal representations. In contrast, out-of-coverage (k: = 0) examples exhibit no clustering pattern, as they lack evidence of functional equivalence in the training data. The PCA visualization at position I2 and layer (Right) shows this trend visually. We verify that the representation clusters play causal role in pattern matching with causal tracing (Goldowsky-Dii et al., 2023; Hanna et al., 2023), a widely used technique to identify Transformer circuits (Fig. 8).
Our findings extend the previous insights from mechanistic interpretability literature (Wang et al., 2024a) in several ways. First, we demonstrate that unified circuit formation is driven by functional equivalence evidence in the training data, not by explicit exposure intermediate computation steps. Moreover, we find that these clustered representations are not necessarily aligned with vocabulary embeddings, implying that standard interpretability methods like logit lens (nostalgebraist, 2020) may fail to detect these functional equivalence representations despite their presence (see App. E).
'The analyses for varying factors including task structures, entity set size (l/t),, dataset size (N), and training steps give consistent results; see App. D.

---

Published as a conference paper at ICLR 2026
5.75
5.50
5.5
logiN
5,00
2-Hap 1.58 (c-2.28)
3-Hlop Ic = 2.58)
4.75
HoH S6M (c-2.26)
4.5
Farallel-22 2 Hop (c- 2.43)
4.50
2-Hopp 6BM (:12.1))
1.7
1.8
1.9
2.0 log(
2.1
2.2
2.3
1.7
1.0
1.9
2.0
211
2.2
2.3
logila))
Figure 5: Left:: Log-log plot of measured Nog vs. token set size ((27) across three compositional tasks. The slope corresponds to the empirical power-law scaling exponent. Omitted points for 3-HOP are due prohibitively large dataset requirements. Right: Power-law scaling behavior on 2-HOP task across varying GPT-2 model sizes (68M to 1.5B parameters) and Mamba model (For Mamba, we used 4 layers, a hidden dimension 256, and a learning rate of 0.008, and Newq is measured for only |.8| < 100, since a larger token set size led to training instability). It? > 0.99 for all linear fitting.
DATA SCALING LAW OF PATTERN MATCHING BEHAVIORS
Our analysis in the previous section demonstrates that stronger functional equivalence evidence leads to better generalization. natural follow-up question arises: How large should the training set be to enable full generalization all ID test data? Intuitively, this requires the training set to support (strongly enough) the functional equivalence of every pair of inputs that shares the same
intermediate state b. Formally, for 2-HoP task we need (2). [112] (x),,²) whenever
(D.k)
f1 22) fi xz), Assuming that generalization is constrained by the k-coverage, how should the train data size scale in the token set size | to achieve it completely? In practical terms, this question seeks to determine the amount of data necessary and/or sufficient to cover all ID combinations with k-coverage, which is crucial for understanding the data cost for pattern- matthingg generalization. To quantify the data cost, we establish and prove the following upper bound for learning a H-HOP task (the complete statement and proof are provided in App. F);
Theorem 6.1 (Informal: Corollaries F.9 and F.17), Consider 2-HOP task with token set of size For uniformly randomly sampled train dataset D of size N, consider a learner that generalizes within the k-coverage of D. Then, for sufficiently large n, the learner can achieve perfect ID generalization with high probubility if N ス ne with 2.5 T.
In contrast, the learner (with & 2) cannot achieve perfect ID generalization with high probability for some 2-HOP task n S Sn.. Here, we ignore the polylogarithmic factors in n.
Theorem 6.1 presents a tight sample complexity bound (nn") for mattern-matching based generaliza- tion, showing that the training dataset required to ensure full ID generalization grows polynomially in the token set size with exponent E [2, 2.5). To empirically confirm this, we define practical threshold Noog estimate Nre. k).
minimal amount of training data required to exceed ID accuracy of 0.99 within 100 epochs after reaching the same level on training data (see App. G for the measurement details). Fig. 5 (Left) shows the measured power-law exponents for Neg vs. | across different task structures. The measured exponent for 2-HOP well with our theoretical predictions. Although we derive the theoretical bound only for 2-HOP, we observe clear plwer-law relationships for more complex structures as well. The higher exponents for PARALLEEI --P (c = 2.43) and H-H (c 2.58) tasks suggest that extra computational steps essentially add another dimension of relationships that require robust coverage, driving the steeper pawer-law scaling.
2.26) aligns
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 Right and Tab. 2 in App. G). We also show that the exponent measured with a Mamba model (4 layers and a hidden dimension 256) falls inside the boundary predicted by the theory (same figure). Interestingly, the result in Fig. 6 (Middle) demonstrates that with increasing training dataset size N, there a sharp phase transition from ID generalization failure to complete success near N 20k.
7

---

Published as a conference paper at ICLR 2026
Identical Intermediate States
Functional Equivalence
240p
Layer
Layer?
0.4
(01.22)
(x1, 2
(21,
accuraa
0.6
0.8
Layer
Layer4
6.38
02
0.4
Layer 3
(#11, 22)
(21: x
(x1
Layer
Layer1
5k
10k 156
20k 25t Dataset Size(N)
30x 35k 4GK 45K
50k
X2 x5
X1 X2 X3
-000
(b, x2)
Figure 6: Left: In NON-TREE task, the representations of input subsequences with the same intermediate state 6 = (x1, 22) are split into multiple context-dependent state representations, conditioned on 22 value. Middle: ID test accuracy after standard training with varying training dataset size (Ix 50, evaluated 100 epochs after training accuracy reaches 0.99). Observe sharp transition from generalization failure complete success near = 20k for 2-HOP, which does not occur in NON-TREE task. Right: IIGG heatmap from model that achieved near-perfect ID accuracy (0.96) after extended training (36k epochs, | = 50, N = 50k).
Overall, the results support that the data scaling law is primarily determined by data properties rather than model capacity or architectures, and additional generalization mechanisms will be required to achieve milder scaling laws on such compositional tasks.² We note that our result aligns with the practical observation that parameter scaling does not significantly improve the multi-hop reasoning capability of L.Ms (Yang et al., 2024) and the data-hungry nature of compositional tasks (Lake & Baroni, 2018) 8), suggesting that these could be partly attributed to pattern-matchin behaviors. We leave further analysis of the connection between scaling behavior and pattern matching as an exciting future research direction.
PATH AMBIGUITY PROBLEM AS A FAILURE CASE OF PATTERN MATCHING
We identify path ambiguity problem with our framework, previously uncharacterized failure mode that pattern matching struggles with task structures where a single variable affects the output through multiple paths. In this section, we analyze NON-TREE task (Fig. 2d) as a case study, where x2 affects the output through two paths, as input to Si and directly to /2- Unlike in the 2-HOP case, one cannot establish the functional equivalence of two subsequences (22) x2) and (1', .r)) that produce
the same intermediate state b. unless they also share the same 22 value (02 2²2). It is because 22
(x1, x2) and (x1 x/2) are not guaranteed to behave identically (i.c., fZ1, 22, 23) is not necessarily
equal to f(1 2/2, 233) when In * Zz. Consequently, we can predict that Transformers trained on the NON-TREE will create context-dependent state representations that are conditioned on 22 values, failing to unify them to represent the true intermediate state b (Fig. 6 Left).
Experiments show that the path ambiguity indeed hinders both generalization on the ID test set and the interpretability of intermediate state representations, as the model now establishes functional equivalence for each X2 rr-coonitioned equivalent pair. Fig. 6 (Middle) shows that GPT-2 can fully generalize on the ID test set of 2-HOP task within reasonable time with increasing data size, but fails with NON-TREE task, even provided with near-exhaustive amount of possible ID combinations as training data. Notably, scaling to 1.5B parameters does not show significant improvement in the performance (Fig. 18), and the Mamba model used in Sec. 6 shows the same trend of generalization failure (Fig. 19). In addition, 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 Right). In contrast, grouping by 22 cy-conditio intermediate state (b, x2) leads to high IICG scores, showing the formation of context-dependent state representations. This context-dependence due to path ambiguity raises an interpretability concern, standard linear probing- techniques like logit lens (nostalgebraist, 2020; Belrose et al., 2023) would not reliably identify intermediate states when model relies on pattern matching.
Hence, generalization mechanism other than pattern matching will be required for a robust ID generalization complex task structures that require the access and update of intermediate states
'The observed scaling relationships are robust across different hyperparameters (weight decay and learning rate) and empirical decision criteria for Nrea (see App. G). For [X] = 50 and Preen = 0.7, our largest run (N 50k) includes virtually the entire domain (++
0.72 x s Rs 61k distinct ID triples).
8

---

Published as a conference paper at ICLR 2026
through multiple paths (e.g., planning tasks (Ruis et al., 2020; Kambhampati et al., 2024; Valmeekam et al., 2023)), where further characterization this problem remains as an exciting future direction.
8 COT IMPROVES DATA EFFICIENCY BUT PATH AMBIGUITY PERSISTS
5.5
1.0
0.35
Mam--ree (hi
2-Hip Ch x2)
2-Hop Ohl
5.0
2-Hpp
0:25
Non tre tee (22
Ron-2000-0 CoT
0.20
2-i Ic- 2.581
2i0 ic 2.261
0.4
0.5
25
022
0.05
3.0
l0g
5K
10K
154.
204 25k
Dataset StzelW)
36k
35A
416 454
50k
Layar
Figure 7: Left: Pawer-law scaling of required dataset size token set size for tasks with CoT supervision. R > 0.98 for linear fits. Middle: Comparison ID test Accuracy of NON-TREB task (12t) = 50) with and without CoT supervision. Right: IICG score comparison for NON-TREE and 2-HOP task with CoT supervision ([X = 50, N = 10k). The scores are measured at each layer of intermediate state position b, based on two grouping strategies: b and (2). Models are trained for 100 epochs after reaching training accuracy 0.99.
The CoT supervision (Wei et al., 2022: Kojima et al., 2022) dramatically improves performance on multi-step reasoning tasks. We investigate how it interacts with our framework and whether it can address the challenges observed in Sec. and 7. Specifically, intermediate states before final outputs, making 2-HOP a two-token prediction task: (I1, T2, 43) + (b, f). for example. This substantially improves data efficiency (Fig. 7 (Left)), with the power-law exponent dropping from 2.58 to 1.76 in the 3-HOP task, aligning with previous studies on the sample efficiency of CoT (Srivastava al., 2023; Kim & Suzuki. 2025: Wen al.. 2025). The scaling exponents measured for 2-HOP, 3 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.
train models to sequentially generate
However, we find the path ambiguity problem persists even with CoT supervision. Despite showing improvements, the models fail to achieve perfect ID generalization under the same training conditions that yield perfect performance in 2-HOP task (Fig. 7 (Middle). IICG analysis (Right) reveals that the model's 's representations remain partially context-dependent. For the 2- 2-HOP task, the representations cluster purely by intermediate states b, as indicated by the result that IICG measurement with Z2- 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 (æ1, 22) pairs sharing the same b should yield identical second-step outputs, as functional equivalence holds only when x2 xzy. 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. 7. Our analysis may explain why LLMs struggle with complex planning tasks even when using CoT techniques and massive training data (Stechly et al., 2024), where we leave further analysis as future work.
DISCUSSION
9.1 PRACTICAL IMPLICATIONS
Although the experiments in this work have focused on synthetic setups to dissect purely pattern- matching behaviors, our results provide valuable practical implications for understanding and im- proving LLMs on natural language tasks.
First, it accounts for the data-hungry nature of compositional tasks by demonstrating that robust coverage is required for reliable generalization (Lake et al., 2017). For instance, our scaling-law analysis (Theorem 6. provides a quantitative explanation for the observed behavior that the data demand for generalization on multi-hop natural language data dramatically increases with the number of hops (Yao et al., 2025). Such a dlat--hungry nature of compositional tasks is also well observed in semantic parsing (Dong & Lapata, 2016), where has been shown that the diversity of

---

Published as a conference paper at ICLR 2026
data (i.e., the same component is shown in diverse contexts) is more important than the sheer size of the dataset for better generalization (Keysers et al., 2020). Based on these insights, we believe results will motivate strategic data augmentation methods that seek to maximize coverage by ensuring diverse shared contexts for functionally equivalent components (Andreas, 2020).
Second, framework helps interpret various real-world failure cases observed in LLMs as stemming from their reliance on pattern matching. For example, our framework aligns with the reversal curse phenomenon, which is the failure to automatically infer that 'A is a child of B' by observing that 'B is parent of A' (Berglund et al., 2024). This occurs because pattern matching inherently cannot generalize to the reversing relation without clear evidence of functional equivalence in the training dataset. Similarly, our framework can explain the notoriously hard problem of logical negation in I.LMs (Truong al., 2023). A purely pattern-matching learner cannot deduce that the negation rule (i.e., if a statement "p" is true, then 'not p" is false and vice versa) should apply to any well-formed statement, including the ones that aren't 't observed, through finite observations. Finally, difficulties in solving complex planning tasks with LLMs (Valmeekam al., 2023; Stechly et al., 2024; Kambhampati et al., 2024; Wang et al., 2024b) may partly result from path ambiguities, since such tasks likely require the correct tracking of intermediate states, which can be affected by multiple computational paths.
Hence, we believe framework and analyses can provide important practical insights, which future work can extend to investigate I.LMs' pattern-matching behaviors under more realistic setups.
9.2 TOWARDS A TAXONOMY OF GENERALIZATION MECHANISMS
Natural language tasks exhibit algebraic and structural properties that distinguish them from the randomly generated mappings we studied. For example, the same knowledge can be used in any hop of the multi-hop reasoning in practice, unlike our 2-HOP task that used fi * fz. In practice, learner may reasonably harness such properties of given task to generalize beyond the boundary of pattern-matching defined by coverage. Therefore, mechanisms enable generalization beyond the coverage boundary? While complete answer requires future work, we outline mechanism- based taxonomy as a starting point for constructive categorization of distinct generalization mechanisms beyond pattern matching:
natural to ask: What generalization
Functional equivalence- based generalization, the main focus of this work.
Function property-basee generalization leverages algebraic invariances of individual primitive functions, e.g., commutativity or input irrelevance, where certain arguments never affect the output. This distinguishes it from pattern matching, as it leverages a primitive function's 's global property that holds across all inputs, not only those observed.
Shared-operator generalization leverages the reuse of the same computation across positions (e.g., when fi f2 in two-hop task), which may be important in compositional generalization. For example, it is known that Transformers with inductive biases towards computation reuse can improve generalization
compositional tasks (Csordás et al., 2021).
We envision this taxonomy as a foundational diagnostic that quantifies when pattern matching suffices and when other mechanisms are required. See App. for complete discussion the categorization of generalization mechanisms.
10 CONCLUSION
In this work, we formalized framework for characterizing pattern matching. Our theoretical and experimental analyses provided quantitative and predictive insights into modern neural networks' pattern-mate matching behaviors, moving beyond post-hoc accounts of model's s behavior on composi- tional tasks: (i) the alignment of instance-we sestacce-wise success with the strength of dunetional-equivalenee evidence (Sec. 5), (ii) the theoretical identification and empirical verification a sharp sample com- plexity bound for complete ID generalization on the 2- task through pattern matching (Sec. 6), and (iii) the identification of the path ambiguity problem that impairs accuracy and interpretability under high coverage and COT supervision (Sec. 7 and 8). We anticipate that future work will build on this foundation, towards a more complete and constructive understanding of compositional generalization and its failures.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
All codes for dataset generation, training, and analysis can be found at: https://github com/ KolsstA//ooveragg--princ.pppp..
THE USE OF LARGE LANGUAGE MODELS (LLMs)
This work deployed LLMs to proofread for grammatical errors and improve the quality of writing.
ACKNOWLEDGEMENTS
We thank Jaewon Oh, Jihoon Ha, Hyowon Cho, Yunjae Won, Seongyun Lee, and Boshi Wang for their invaluable feedback.
This work was supported by Institute for Information & communications Technology Planning Artificial
(IT))) grant funded by the Korea government (MSIT) (RS- Intelligence Graduate School Program(KAIST), Hoyeon Chang, Jinho Park, Miyoung Ko, Hyeonbin Hwang, & Minjoon Seo acknowledge support by Institute of Information & communications Tech- nology Planning & Evaluation (ITTP) grant funded by the Korea government (MSIT) (No.RS-2019) I1190075 Artificial Intelligence Graduate School Program (KAIST), 10%;
Artificial Intelligence Innovation Hub, 10%; RS RS-2024-00398111 15, Research on the reliability and co- herence of outcomes produced by Generative AI, 20%; No. 2022020000 13, Developing a Sustainable Collaborative Multi-modal Lifelong Learning Framework, 20%; No. No.RSS2000 00222-1220024, Compre- hensive Video Understanding and Generation with Knowledge-based Deep Logic Neural Network, 20%; -032094- Development a Cybersecurity Specialized RAG-based sLLM Model for Suppressing Gen-AI Malfunctions and Construction of Publicly Demonstration Platform) and the InnoCORE program of the Ministry of Science and ICT(N10250156) Hanseul Cho acknowledges support by IITP grant funded by the Korean govemmment (MSIT) (No. RS RS-2024-00457882 National Al Research Lab Project).
REFERENCES
David Aldous. Probability Approximations via the Poisson Clumping Heuristic. New York, NY Springer New York Imprint: Springer, 1989. URL http: http://xxxxoodooooo//oooo owt.ooo//o...100./7777
978-1-4757-6283-1 44
Jacob Andreas. Good-enough compositional data augmentation. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 7556-7566, Online, 2020. Association for Computational Linguistics. doi: 10. 10.18653/v1/23 10133//1/220..am 1/2an20.aa-mmii..677776 URL https: / //cc///aa//cco/////// anthology.....o.. org/
2020..ac-ma i n.. 676. 10
Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ra- masesh, Ambrose Slone. Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Ex- ploring length generalization in large language models. In S. Koyejo, S. Mohamed. A. Agarwal, D. Belgrave. K. Cho, and A. Oh (eds.). Advances in Neural Informa- tion Processing Systems (NeurIPS), volume 35, pp. 38546-38556. Curran Associates, Inc., 2022. URL https://proceeinng: neurips cc/paper hacp/ppprr_fieeeeee fww.fflll/ppppl tttee//paee//222.. file/ File/fbli foefff4455552 htll://///Sseeefffoss333orrtaaaa
Paper Conference .pw..
Nora Belrose, Zach Furman, Logan Smith, Danny Halawi, Igor Ostrovsky, Lev McKinney, Stella Biderman, and Jacob Steinhardt. Eliciting latent predictions from transformers with tuned lens. ArXiv preprint, abs/2303.08 0113000...11....... 2023. URL https:///////....c / httpaaaxvv.rg.a.aaaa.a.a httgg/abs/33000 22003. 08.12.1
Lukas Berglund, Meg Tong, Maximilian Kaufmann, Mikita Balesni, Asa Stickland, Tomek Ko- rbak, and Owain Evans. The reversal curse: Lims trained "a is b" fail to learn "b is a". In B. Kim, Y. Yue, Chaudhuri. K. Fragkiadaki, M. Khan, and Y. Sun (eds.), Proc. the International Conference on Learning Representations (ICLR), pp. 18623-18642,
11

---

Published as a conference paper at ICLR 2026
2024. URL
517
påf. 1, 10, 55
Alexei Borodin, Andrei Okounkov, and Grigori Olshanski. Asymptotics of plancherel measures for symmetric groups. Journal of the American Mathematical Sociery, 13(3):481-513 2000. 44
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris 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 H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems (NeurIPS), volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. URL 2020/ Fi e (11445500d6fccbbb4377 http://4466671110011114212211
iggs rewrips...... wtwriiis.ccppeeee wwtppppr_eeaeeeeeeeeeeeeee fellsspappr/
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 pre- training? In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems (NeurIPS), vol- ume 37, pp. 60626-60668. Curran Associates, Inc., 2024. doi: 10.52202/079017-19399 URL https: https:://prrceeddngg.ooo neuuiii 0B0557777hcc11eee221148833333333
halppppppfflll wttpe///ppppe//2///442/ ffile/ Paper-appp----- aaper-Conferene..pco 6
Hanseul Cho, Jaeyoung Cha, Pranjal Awasthi, Srinadh Bhojanapalli, Anupam Gupta, and Chulhee Yun. Position coupling: Improving length generalization of arithmetic transformers using task structure. In A. Globerson, Mackey, D. Belgrave, A. Fan, U. Paquet, Tom- czak, and C. Zhang (eds.), Advances in Neural Information Processing Systems (NeurIPS), volume 37, pp. 22233 22315. Curran Associates, Inc., 2024. doi: 10.52202/079017-0700 URL https: http//ppreeeennsseeeeeee//e newriieersppp... cc/paper 77aa300e6d63db 6997 (16999992266677755502 Papeeeaapp-r--ae Cow--oooneeeeeeee....ee 55
//tp///// file/
Hanseul Cho, Jaeyoung Cha, Srinadh Bhojanapalli,, and Chulhee Yun. Arithmetic transformers can length-generalize in both operand length and count. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), Proc. the International Conference on Learning Representations (ICLR), pp. 79987-80029, htw.lleeeppape//////
2025. URL https: http///pcceeee...eooe///o iclr oc Satpeee--appe----eeeeeeeeeee pdf. 55
c6c2 (eteeeeeeee22eee7e1eeeeeeeeeeeee
Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber. The devil is in the detail: Simple tricks improve systematic generalization of transformers. In Marie-Francin Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 619-634, Online and Punta Cana, Dominican Republic, 2021. Association for Computational Linguistics. doi: 10. 11111611122221111.. 1ttp//2.m.mmmmmmii...... URL https: /aa/aaaaaatttta aalaattooooooy .rg. 2021 emnlp-main 49. 10, 55
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 (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. Emirates, 2022. Association for Computational Linguisties. doi: 10.1 1663/v1/2022.mmllp main. 662. URL. https::tp////oc... / aac antho Mitoolooyy. logy .rgg 2022..222.22..2 ee222.emn111.mmm 1 ma i In. 662. 1,3
Abu Dhabi, United Arab
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. Proc. the International Conference on Learning Representations (ICLR), 2019.
URL http::/:///pppevvieeeee .net/ wwwpeenneeeetteiiieeeeeeee www.uoriuddioor.ooo dotoummii-ttyyddRRRRRY 55
Li Dong and Mirella Lapata. Language logical form with neural attention. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 33-43, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10. (0.18853/v1/P 1/133//111111.11 1004. URL https: aaclanthology. org/p166-104/..
12

---

Published as a conference paper at ICLR 2026
Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang (Lorraine) Li, Liwei Jiang, Bill Yuchen Lin. Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers on compositionality. In A. Oh, T. Naumann, A. Glober- son, K. Saenko, M. Hardt, and S. Levine (eds.). Advances in Neural Information Processing Systems (NeurIPS), volume 36, pp. 70293-70332. Curran Associates, Inc., neurips wwtppperppiiiaaeeeeee waallls/paper//ee pdf. 3,
2023. URL
file/ /aleeddee
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021. URL https: /tt/tttannsss aatransforrree wormer-oooorooeooo www.mmerrririittt..eee pub /tt///////////////////////// Eramework/ index html. 3
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.1063 2022. URL httph:ttt//.ooo. http://axvvvv.///// org/ abs 2209 10652.
Pál Erdōs and Alfréd Rényi. On a classical problem of probability theory. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 6(1-2):215-25) 220, 1961. 43
Jerry A. Fodor and Zenon W. Pylyshyn. Connectionism and cognitive architecture: A crit-
ical analysis. Cognition, 28(1):3-71, 1988. ISSN 0010-0277. doi: https://oi.orr//10
101670000002778839003355 URL http:::/www.cceeeddeeeet.
aaticlee/11/000122778888888
E. Godehardt and J. Jaworski. Two models of random intersection graphs for classification. In Manfred Schwaiger and Otto Opitz (eds.), Exploratory Data Analysis in Empirical Research, pp. 67-81, Berlin, Heidelberg, 2003. Springer Berlin Heidelherg. ISBN 978-3-642-55721-7, 49
Nicholas Goldowsky-DD 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/ 23004 05969. 3, 6, 26
Alex Graves, Greg Wayne, and Ivo Danihelka. arXiv:1410.5401, 2014. 55
Neural turing machines.
arXiv preprint
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In First Conference on Language Modeling, 2024. URL httpt:htt///ppttt htttt:ss///ppeeevviiw net forum?id= tEYskw1vY2. 1,2
Michael Hanna, Ollie Liu, and Alexandre Variengien. How does gpt-2 compute greater-than?: Interpreting mathematical abilities in pre-trained language model. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Informa- tion Processing Systems (NeurIPS), volume 36. pp. 76033-76060. Curran Associates, Inc., 2023. URL https: https: http:://////cceeeeneeoeo neurips wwtppppppeeeiieeeeeee wtt.ffileeseeeeeeeeeeeee file/efbba 77 htt.aaacccc.cc1a2222222222222200
pdd.. 3, 6, 26
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98):
1735-1780, 1997. 55
Lars Holst. On birthday, collectors', occupancy and other classical urn problems. International Statistical Review/Revue Internationale de Statistique, pp. 15-27, 1986. 44
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. 3, 55
Philippe Jacquet and Wojeiech Szpankowski. Analytical depoissonization and its applications. Theoretical Computer Science, 201 1998. 44
13

---

Published as a conference paper at ICLR 2026
Kurt Johansson. The longest increasing subsequence in random permutation and unitary random matrix model. Mathematical Research Letters, 5(1):68 82, 1998. 44
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In Proc. of the IEEE conference on computer vision and pattern recognition (CVPR), pp. 1988-19977 July 2017. doi: 10.11099CVP..2017.255. URL https: / /tti//oi...////// ort./0.11100000 CVPR. 2017. 2017.215.
Mare Kac. On deviations between theoretical and empirical distributions. Proceedings of the National Academy of Sciences, 35(5):252-257, 1949. 44
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma. Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil Murthy. Position: L.MSs can't plan, but can help planning in LLM-modulo frameworks. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proc. the International Conference Machine Learning (ICML), volume 235 of Proceedings of Machine Learning PMLR, 21-27 Jul 2024. URL https: http:///roeeeeeeeeeeeeee//e/ooee mmlr. Research, pp. http///aaaaaaaatataaaa 14a html. 9, 10 Sress/v233
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 (eds.), Proc. the International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pp.
PMLR, 23-29 Jul 2023. URL https: cattps://proceedinne http://pccceee....c.e// .mll....s.m........mm.m......... mlr. press/v200 kandpald ....mmmll.......mm..mmmmmmm 6
Michal Karoński, Edward R Scheinerman, and Karen B Singer-Cohen. On random intersection graphs: The subgraph problem. Combinatorics, Probability and Computing, 8(1-2)1311-55, 1999. 49
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, Mare van Zec, and Olivier Bousquet. Measuring compositional generalization: A comprehensive method realistic data. In Proc. the International Conference Learning Representations (ICLR), 2020. URL https:/ /tt:://pppeee /oppnreviee net/ ffo.mmridddgss idrrummid=SSyyenNKkvr 1, 10
Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought. In Proc. the International Conference Learning Representations (ICLR), 2025. URL https: / //oppereviiie ew net/ d 9
Najoung Kim and Tal Linzen. COGS: compositional generalization challenge based on semantic interpretation. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9087-9105, Online, 2020. Association for Computational Linguistics. doi: 10.18653/v 1ttp:///122222mmmmm http2200.cmmmpmmmii..3.33... m3in.731. URL https: /aclaacaaaa wawaaaannallooyooaooo org/ 2020 emnlp-mail in.innnn. 731.
Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwa- sawa. Large language models zero-shot reasoners. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave. K. Cho, and A. Oh (eds.), Advances in Neural Informa- fion Processing Systems (NeurIPS), volume 35, pp- 22199-22211 Curran Associates, Inc., 2022. URL https:: http://///ooceeennnsseeee neurips wewpips.cc/ppperrrrrr.o...... filerrffll//pppeee httpp/pppprr///////// file/Bbb0d29
file/ 8bb0dbbbbo (awddd29acc4acfffeefeo
pdf.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequeeee recurrent networks. In Jennifer Dy and Andreas Krause (eds.), Proc. the International Conference Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 2873-2882, PMIR, 10-15 Jul 2018. URL https: http:////ocoeedeeee ings. mlr. w.x..pess/vvee vv0 aaaaeelaa.... html. 3, 8, 55
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. doi: 10.1017/S0110522 16001837.
14

---

Published as a conference paper at ICLR 2026
João Loula, Marco Baroni, and Brenden Lake. Rearranging the familiar: Testing compositional generalization in recurrent networks. In Tal Linzen, Grzegorz Chrupata, and Afra Alishahi (eds.), Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 108-1 108-114, Brussels, Belgium, 2018. Association for Computational Linguistics. doi: N0.18653/11W118-544 URL a httpc/cccnnttooooooooooooooooooe org. 54143.
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 Proc. the Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 9603-13615, 2024. 55
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 (eds.), Proceedings of the st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9802-9822, Toronto, Canada, 2023. Association for Computational Linguistics. doi: 10. 1865// v1/2023.acl-oong.55 URL https: htt///aaaaantttt wnt.lolgy org 2203 aall 546. 6
Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov. Locating and editing factual associations in gpt. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho. and A. Oh (eds.), Advances in Neural Information Pro- cessing Systems (NeurIPS), volume 35, pp. 17359-17372. Curran Associates, Inc., neurips cwtpaper_ffiiieeeeceeee filefffillss.. wwwile/papper.. /ttplesspaper//2/22.
2022. URL https::/ file/6f1d4 htll:/ff.c4cc5222227999666666663
82 www-eee---PPP--ee Pwwperaaaaeeeeeeeeeaeeee .aw.nnnc..................... pdd. 3
Iman Mirzadeh, Keivan Alizadeh-Vahie Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. GSM-Symbolic: Understanding the limitations of mathematical rea- soning in large language models. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), Proc. the International Conference on Learning Representations (ICLR), pp. 94743 94765, 2025. URL / http://poceeeengeeeeeeppoe iclr cc/ wwcpppape_fiiiieeeeeee files pttpp/pppppp////////////// 222///222///////////// ec2e (o2e7789661222066330008
-appeeeee------eee-------- Conereec-cofree........ 1,3
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. In Proc. the International Conference on Learning Rep- resentations (ICLR), 2023. URL https: /opprreeevvvieeeeeeeeeeeeeeeeeee ew,
d= SbDPmdW.
Donald Newman. The double dixie cup problem. The American Mathematical Monthly, 67(1): 58 1960. 43
nostalgebraist.
Interpreting GPT: the logit lens. https://www lesswrong. www./o/////ooooooo com/posts httm//ssss/AcceeeeDeeeeeee AAckRB6DppaaGGG6rrr
LessWrong, 2020.
URL interpreting gpt-the- logit -emeitt-eee....e lens. 3, 6, 8
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, 7ac HaffieldDDodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Ka- plan, Sam McCandlish, and Chris Olah. In-context learning and induction heads. Trans- former Circuits Thread, 2022. URL in- co-context-aie Learning and sodd-inductionn heads/index. html. 3
cicittss rcuuist.... pub/2022/
OpenAI. Gpt-4 technical report. ArXiv preprint, abs/2303.08774, 2023. URL org/abs 2303. 08774.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, al. Improving language understanding by generative pre-training. 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 188):9 2019. 1,
15

---

Published as a conference paper at ICLR 2026
Laura Ruis, Jacob Andreas, Marco Baroni, Diane Bouchacourt, and Brenden M Lake. A bench- mark for systematic generalization in grounded language understanding. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Informa- fion Processing Systems (NeurlPS), volume 33, pp- 19861-19872. Curran Associates, Inc., 2020. URL https: http::://oocceedee ngs. neurips httppppeeeeepppeeeeeeeeeeeesssse Paw.eeeepppperppp.. 9
Katarzyna Rybarezyk. Sharp threshold functions for random intersection graphs via a coupling method. The Electronic Journal of Combinatorics, 18, 2011. doi: 10.37236/523. 50
Katarzyna Rybarezyk. The coupling method for inhomogeneous random intersection graphs. The Electronic Journal of Combinatorics, 24:P2. 10, 2017. 50
Arnab Sen Sharma, David Atkinson, and David Bau. Locating and editing factual associations in mamba. In First Conference on Language Modeling, 2024. URL /tttps:///peereview.
wow.oorrunnddooyyyyrii.i....... 26
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, 55
Karen B. Singer. Random intersection graphs. PhD thesis, The Johns Hopkins University, 1995. 37, 49, 50
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 Tazary, 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 Karakay, B. Ryan Roberts, Bao Sheng Loe, Barret Zoph, Bartlomiej 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-Burche Christopher Waites, Christian Voigt, Christo- pher 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, Ekaaeeinaa Shutova, Ekin Dogus Cubuk, Flad Segal, Eleanor Hagerman, Elizabeth Barnes, Elizabeth Donoway, Ellie Pavlick, Emanuele Rodolà, Emma Lam, Eric Chu, Eric Tang. Erkut Erdem, Ernic Chang. Ethan A Chi, Ethan Dyer, Ethan Jerzak, Ethan Kim, Eunice Engefu Manyasi, Evgenii Zheltonozhskii,, Fanyue Xia, Fatemeh Siar, Fernando Martinez-Plumed, Francesca Happé, Francois Chollet, Frieda Rong, Gaurav Mishra, Genta Indra Winata, Gerard de Melo, Germàn Kruszewski, Giambatiist Parascandolo, Giorgio Mariani, Gloria Xinyue Wang, Gonzalo Jaimovitch-Loppez 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, Jachoon 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,
16

---

Published as a conference paper at ICLR 2026
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-Ochandoo, Louis- 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-Quintange Marie Tolkiehn, Mario Giulianelli, Martha Lewis, Martin Potthast, Matthew 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, Michat Swedrowski, 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 Milkowski, Piyush Patil, Pouya Pezeshkpour, Priti Oli, Qiaozhu Mei, Qing Lyu, Qinlang Chen, Rabin Banjade, Rachel Etta Rudolph, Raefer Gabriel, Rahel Habacker, Ra- mon 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 Ham- dan, Sharon Zhou, Shashank Srivastava, Sherry Shi, Shikhar Singh, Shima Asaadi, Shixiang Shane Gu, Shubh Pachchigar, Shubham Toshniwal, Shyam Upadhyay, Shyamolima Shammic 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, Stephanic Lin, Stephen Prasad, Steven Piantadosi, Stuart Shieber, Summer Misherghi, Svetlana Kiritchenko, Swaroop Mishra, Tal Linzen, Tal Schuster, Tao Li, Tao Yu, Tariq Ali, Tat- sunori 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 Pad- makumar, 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 (TMLR), 2023. ISSN 2835-8856. URL https:://// /ttes:///ppenae //tpppppeeeiieeeeeeeeeeeeeeeeeee net/ wee/tforumee forum? iiriidddyyyyossss Featured Certification. 9
Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. Chain of thoughtlessness?? an analysis of cot in planning. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural Information Processing Systems (NeurIPS), volume 37, pp. 29106.29141, Curran Associates, Inc., 2024. doi: 10.52200/079017-0091, URL https: http://ptcceeee.eeeeeeeeeee neurips oc paperpppr_aae wwwles/papee///// wwwpeee--pappe-e-eeeeeeeeeee pdf. 9, 10
file/
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.13997 2023. URL https:
/ //arxiv.org/abs/ /2.p//332222222 13971.
Thinh Hung Truong, Timothy Baldwin, Karin Verspoor, and Trevor Cohn. Language models are not naysayers: an analysis of language models on negation benchmarks. In Alexis Palmer and Jose Camacho-collades (eds.), Proceedings of the 12th Joint Conference on Lexical and Computational Semantics (*EMM 2023). pp. 101-114, Toronto, Canada, July 2023. Association for Computational
17

---

Published as a conference paper at ICLR 2026
Linguistics. doi: 10.18653//112023.sttrrre 1.10. URL httpss//aaacaaaatooooo.ooo/// 3023.starsemm111 10
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Planbench: An extensible benchmark for evaluating large language mod- els on planning and reasoning about change. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Process- ing Systems (NeurIPS), volume 36, pp. 38975-38987. Curran Associates, Inc., 2023. wttpiiiss.ccppppeeeeeeeeeeeeee ec wwcpppapr_fiiiiieeee
URL https://pree http::///proceeeiiiss.nueeu neurips 7a (e92cceeee8c7aaaal007722aaaass32 Paper-aatasetsssssseeeeea and BicasettssnddBBeccharsssss Benchmarks pdf. 9, 10
Paper- Datasets
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need. I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems (NeurIPS), volume 30. Curran Asso- ciates, Inc., 2017. URL htttp:::pppoceeeeieieeeeeoo 2017/file 2017/Eile/ Sat.2/455477e1111000aacccaaa111.
reurips...... httppps.ccpppaee wwtpcppppppapeeeeeeeeee filef/ile//eeee files/paper/
Boshi Wang, Xiang Yue, Yu Su, and Huan Sun. Grokking of implicit reasoning in transformers: A mechanistic journey to the edge of generalization. In A. Glober- son, L. Mackey, D. Belgrave, A. Fan, U. Paquet, Tomezak, and C. Zhang (eds.), Advances in Neural Information Processing Systems (NeurIPS). volume 37, pp. 15238-95263 Curran Associates, Inc., 2024a. doi: 10.52202/099017-301,,
URL.
https: pettss:/prrceedeeee http///ceeeenng..eeeepppe
mewpeeddddnnnnn.iipp..ee.. neurips cc/ wwwppppeerillleeepeeeeeeeeeeeeee www.f///ppeee/ee////////e 20t////////f//////////////////// file/
1, 3, 4,
23,55 55
Kevin Wang, Junbo Li, Neel P. Bhatt, Yihan Xi, qiang liu, ufuk topeu, and Zhangyang Wang. Ontheplanning abilities of openAl's ol models: Feasibility, optimality, and Language Gamificatiio NeurIPS 2024 Workshop, 2024b. URL generalizability. In net/
10
Kevin Wang. Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt. Interpretability in the wild: circuit for indirect object identification in GPT-2 small. In Proc. the International Conference on Learning Representations (ICLR), 2023. URL https:// openreview.r net/ www.nnee////rr.eoe forum? Sooruum?id-NSSVSNNo44
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichtier, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In S. Koyejo, S. Mohamed, Agarwal, D. Belgrave, K. Cho, and A. (eds.), Advances Neural Information Processing Systems (NeurIPS), volume 35, pp. 24824-24837. Curran Associates, Inc., 2022. URL https: / www.diiinnnnnuuuuueeee nwwrips.rr.... cc/ cc/pper files/ file filee//eecco113322eeef11000100a2 Paper-Cofeeereeeeeeeeeeeeoeeeeee pdf. 2,9
Conference
Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, and Jingzhao Zhang. From sparse dependence to Unveiling how thain-of-thought enhances transformer sample efficiency. In Proc. the International Conference on Learning Representations (ICLR), 2025. URL https: //openeeview.... net wtt.//oormddiaeeee 2-rrumm2d-AAmm 9, 55
sparse attention:
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 (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 10210-10229, Bangkok, Thailand, 2024. Association for Computational Linguistics. doi: 10. http://ww1/222....ooog..... URL https: //tc//aacaaaaa antho centhooooy... logy. org/ 2024 acl- 550/.3..... 3,8
Yuekun Yao, Yupei Du, Dawei Zhu, Michael Hahn, and Alexander Koller. Language models can learn implicit multi-hor hop reasoning, but only if they have lots of training data. In Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng (eds.), Proc. of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9695-9713,
18

---

Published as a conference paper at ICLR 2026
Suzhou, China, November 2025. Association for Computational Linguistics. ISBN 979-8-89176- 332-6. doi: 10. 1/23//1120222.....//// www.:p-eemlpm--me. main.490. URL lta.ttss//aclaanhoooogg.o orw.:///cccoo..0225.... munlp-main. 4 490/.
Jun Zhao, Osman Yagan, and Virgil Gligor. On k-connectivity and minimum vertex degree in random s-intersection graphs. In 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatories (ANALCO), pp. 1-15. SIAM, 2014. 36, 50
Jun Zhao, Osman Yagan, and Virgil Gligor. On connectivity and robustness in random intersection
graphs. IEEE Transactions on Automatic Control, 62(5):2121-2136, 2017. doi: 10.1 109/TAC 2016.2601564. 36,
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms transformers learn? study in length gen- eralization. In B. Kim, Y. Yue, S. Chaudhuri, K. Fragkiadaki, M. Khan, and Y. Sun (eds.), Proc. the International Conference on Learning Representations (ICLR), pp. 15898-15926, 2024a. URL https: htttts:://prcceedaiiitt 4Bccc11722799101115EE8c0022222
iclz cc/paper cc/paper_files httpp/pppppp////// 2024/file/ p.. 55
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.co fortfoormaa www..rrmmmm-.--.... 55
19

---

Published as a conference paper at ICLR 2026
Contents of the Appendix
A Limitations
21
Detailed Experimental Setup
22
B.1 Dataset Construction
22
B.2 Training Details
23
C Implementation Details for the Coverage Determination Algorithm
24
D Detailed Analysis for Representation Unification Experiments
26
D.I Causal Tracing Methodology
26
D.2
Causal Tracing Results for Each k--Cttff Value in 2-HOP Task
26
D.3 Token Set Size Ablation
26
D.4
Task Ablation
28
E Partial Computation Observation Drives the Alignment of Functional Equivalence Representation and Vocabulary Space
30
Proofs: Asymptotically Perfect Coverage in 2-HOP Task
31
F.l Preliminaries: Definitions, Assumptions, and Facts
F22 Main Theorem: Sample Complexity Bound for Perfect Coverage With High Probability
33
F3
Backgrounds, Useful Facts, and Lemmas
42
F.3.1
(De-)Poissonizatie of Monotone Multinomial Events
43
F.3.2
Binomial Random Intersection Graphs
49
Additional Results for Power-Law Scaling Analysis
51
G.1
Measurement Protocol for Nreq ..ng............................
G.2 Measured Power-Law Scaling Exponents Across Task Structures and Model Sizes
51
G.3 Robustness to Hyperparameter Variations
51
H Detailed Analysis for NON-TREE Task
53
H.1
Coverage Analysis
53
H.2 Effect of Model Scaling
53
H.3 Comparison between Mamba and GPT-2 on NON-TREF Task
53
H.4 Representation Analysis in Successful Generalization
54
I Detailed Discussion the Taxonomy for Understanding Generalization Mechanisms
55
20

---

Published as a conference paper at ICLR 2026
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 discrete sequence tasks with variable lengths and more natural data future work. Additionally, our experiments focus autoregressive architectures, and the applicability of the coverage principle to broader architectures remains to be validated.
21

---

Published as a conference paper at ICLR 2026
B DETAILED EXPERIMENTAL SETUP
B.I DATASET CONSTRUCTION
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 task with token set size [2',, create X special
tokens of the form <t <t_ 0>, <t <t__>,.... <t_ <t_[[X' - 1)>, which we append to the standard GPT-2 vocabulary. We also add special tokens </a> to mark the end of sequences. For Shain-of-Thoughe (CoT) experiments, intermediate computations represented in the target sequence the actual intermediate token.
Function Construction For the 2-HOP task, construct two primitive functions fi X2 - X and /2 X² + X' by randomly mapping from their respective domains to the codomain X. We create the domain by taking the Cartesian product of the token set with itself. For each function, we randomly designate fraction Preen 0.7 of its domain as the "seen" portion, resulting in sets Sy, and f22-
Dataset Generation Algorithm To generate the training dataset, we first identify all possible com- binations where both primitive operations come from their respective "seen" domains. Specifically, we find all valid tuples (#1, 22 33, 1) such that:
(2) E domain (S₁, (fi(21, r3) E domain (Sy,)
(2)
f2(J1 (x1,
From this of all possible in-domain combinations, 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 possible in-domain combinations.
Test Set Construction We carefully construct test sets to evaluate the model's generalization capabilities across coverage conditions. Our test sets contain:
In-Domain (ID) Test Set: Combinations unseen during training but where both primitive
operations were observed in other contexts. These examples may lie within the coverage as defined by framework.
Out-of-coverage (canonical OOD) Test Set: Examples where at least one primitive opera- tion was never observed in training. These fall outside the coverage.
Input-Output Format The dataset is formatted for rego-segressive token prediction. For the standard H-H task, inputs comprise three tokens representing I1, Ø2, and Is, while the target includes these input tokens followed by the prediction and an end marker. Below are the examples of the dataset format for different settings.
Standard Format:
Input: <t <t__<<____________ (c__5<t___ f____<t__1><____________________
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
Target Completion: <t <t_ [t__9><t_____ 9>><t_1><</a>>>>>
The model must first predict the intermediate computation result <t_9> (where <t_9>
=fi(<t_5>, <t <t_12>)), followed by the final output.
Partial Computation Format (fı):
Input: <t_ st_5><t_122
Target Completion: >><>>><>>>>>>
-These examples represent the primitive function applications used to construct the full compositional task.
22

---

Published as a conference paper at ICLR 2026
For the other compositional tasks, 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 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-XI
Number of Attention Heads
6
12
25
Number of Layers
48
Hidden Dimension
768
768
1600
Total Parameters
68M
96M
1.5B
For experiments, employ three GPT-2 model variants of increasing size: GPT-2-Small (68M parameters), GPT-2 (96M parameters). and GPT-2-XL XL (1.5B parameters). As shown in Tab. GPT-2- Small consists of layers with 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-XLL, significantly scales up the architecture with 48 layers. 25 attention heads, and an increased hidden dimension of 1600. The implementation follows the codebase from (Wang al., 2024a).
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 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 constant learning rate schedule with linear warmup period of 2,000 steps. This standardized training configuration maintained across all experiments ensure fair comparisons between different task structures and dataset sizes, unless explicitly varied in specific ablation studies.
23

---

Published as a conference paper at ICLR 2026
C IMPLEMENTATION DETAILS FOR THE COVERAGE DETERMINATION ALGORITHM
In this section, explain algorithm of computing the k-coverage Coverg( (see Def. 3.2), given a train dataset D S X and threshold & to check functional equivalences (see Def. 3.1). The algorithm works in three main stages, as described with pseudo-code in Alg. 1.
Algorithm I: k-Coverage Determination Algorithm
Training examples: D S X each with known output (f(x)) E X for each E D)
Input:
Minimum evidence threshold: 2
Output:
Coverage set: Covers(D)
/* STEP Build behavior maps for each subsequence pattern */
Behav empty hash table
foreach (1)19) 0 # I [4], = [4] do
Behav[7] < an empty hash table
foreach x D do
if o: E Behav [7] keys then
Behav | t an empty hash table
end
Behav 7] a1 [r r + f(x)
end
10 end
/* STEP 2: Build substitution graph using behavior maps
+ a graph (vertex X"; edge set 2)
foreach (1, Ø # C [4] === do
foreach (a, a') a. a' Behav(T].keys and + a' do (aaav
CoDce Belav(/jjaa
// I-co-occurrences Behav(7][a']b) then
15
if [Coocl|2 & and vb E CoDce: Behav| [a]
/+ Statisfies the functional k-equivalence (Def. 3.1) +/
16
foreach b E CoDcc do
17
Let æ. x' E X such that æ, = a, a = a', and x. = x =
18
Add an edge x'} to
19
end
20
end
end
end
/* STEP 3: Build k-coverage
23
Covers( + USED Connected (Q0pone(ee return Cover:(
In the first stage (Alg. 1, Lines 1-10), we first create a mapping of behaviors for all subsequences of every training data. To elaborate on the behaviors, for each subset of indices I, we record how each subsequence æ, (æ:)ses at I of x E D behave when being paired with another subsequence 2t at the complement of indices / == [ \ I. This ends up creating a thrice-nested mapping Behav, as showcased in Line 8. It is particularly useful in the next stage, where we should collect the co-occurrences of each pair of input sequences and verify their consistencies.
The second stage (Alg. 1, Lines 11 11-22) is for establishing the substitution graph g ((D,)) which is essential in the definition of k-coverage. To recall, g is an undirected graph with vertex set & having edges {ar, a²)) when and only when there exists index set such that æ; = (D.k) at/ To verify the presence of an edge via functional k-equivalence, we need to figure out at least k distinct T-co-occurrences (CoDcc in the pseudocode) for some index set 7 (Def. 3.1(1)) and check whether all T-co-occurrences satisfy the consistency (Def. 32)). It is done for every nonempty index set
24

---

Published as a conference paper at ICLR 2026
I S [4] and every distinct pair of subsequences (a. a') E X 211, where take advantage of the mapping Behav defined in stage 1; see Line 15 in particular.
In the last stage, we generate the k-coverage (Alg. 1, Line 23). Here we utilize subroutine ConnectedComponeen
æ) which returns the set of all vertices of 9 sitting the same connected component as the given vertex æ. Hence, Line 23 generates the of all imput sequences that are connected with a train datapoint by a path the substitution graph G, which is precisely the definition of k-coverage. In other words, this set comprises all inputs that are reachable from the training data through a chain of functionally equivalent subsequence substitutions.
25

---

This metric quantifies how much corruption in a particular state affects the overall outcome. An IE value close 1 indicates that the corruption of the state n,(") h h=(() alone almost completely changes the prediction to that of the corrupted run, suggesting that this state causally important for Published as a conference paper at ICLR 2026
D DETAILED ANALYSIS FOR REPRESENTATION UNIFICATION EXPERIMENTS
D.I 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 (Goldowsky-Dill et al., 2023; Hanna et al., 2023). Specifically, we measure the causal effect using the indirect effect metric defined in (Sharma et al., 2024). This methodology enables us identify which components and positions in the model most strongly contribute to compositional generalization. We illustrate the measurement with the 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 (I1, (2; vz)) where the corresponding output is t f2(fi(z1 22), T3)).
2. Corrupted run (G*): We replace the original input with a corrupted version by changing the first two tokens (#1, model produces different final output t* + t. During this run, we cache all hidden states (=(() for each token position i and layer
(21,22) 22),, where fi f1(2(xz)) * f1 22). This ensures that the
3. Patched run (G|+ (0(") We run the model on the input from the clean run, but at a specific token position i and layer l, we replace the hidden state with the corresponding state from the corrupted run.
To quantify the causal effect of specific hidden state hg the model's 's prediction, measure the Indirect Effect (IE):
pl+ 1(1) p(()) IE AEO (*(t)) ptt))
where:
p(t*) is the probability assigned to the corrupted output t" in the clean run G;
p p*(t") is the probability assigned to the corrupted output 1" in the corrupted run G*:
pf- (=(")(t)) is the probability assigned to the corrupted output t* in the patched run c
the computation. Conversely, an IE value close to indicates that the state has minimal causal impact on the prediction.
In our experiments, apply causal tracing analyze different subsets of test data categorized by their k--cutoff values, where represents the minimum evidence threshold required for functional equivalence (as defined in Sec. 3 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-CUTOFF VALUE IN 2-HOP TASK
Fig. displays the causal tracing results for the H-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 example falls within coverage (even with minimal evidence, k = 1), the model forms internal representations that play similar causal roles in prediction.
D.3 TOKEN SET SIZE ABLATION
We show that the observed patterns of cosine similarity analysis and causal tracing in the 2-HOP task consistent across different token set sizes (x). For | 70, 100, 150, 200, analyze model
checkpoints with training dataset size N Nreq (122)) that achieve training accuracy 0.99. Figure
26

---

Published as a conference paper at ICLR 2026
IE
1.0
Layer
0.00
00.77
0.95
0.00
0.00
0.94
0.00
0.01
0.99
Layer
0.98
0.8
Layer 5
0.00
-0.10
0.91
0.00
0.01
0.90
0.00
-0.04
0.97
0.6
Layer
0.4
Layer 3
0.00
-0.08
0.86
0.00
0.03
0.83
0.00
-0.09
0.91
Layer
0.00
0.75
0.05
0.00
0.87
0.03
0.00
0.91
-0.00
Layer
0.00
0.00
x1
X2
X3
x1
X2
X3
X1
X2
X3
0 O<k<3
3=3
k> 3
Figure 8: Causal tracing results for the 2-HoP task across different ke-cutoff values, showing Indirect Effect (IE) scores at each layer and position.
Fig. 9 shows the results, indicating strong representation clustering at the lower layers of position T2 for all cases. The causal tracing results in Fig. 10 show that the clustered functional equivalence representations at the lower layers of position ø2 play a causal role determining the model's 's final prediction.
0.5
Layer
Layer
Layer
0,50
|ICG
Layer
0.2
Layer 3 6.66
6.56
Layer
0.1
Layer
k>
k= 0
k> 0
k=
k> 0
k=0
k> 0
k=0
|x|
70
|xT 100
= 150
| =M=200
Figure 9: IICG heatmap across different token set sizes, showing consistent representation clustering patterns.
1.0
Layer
0.00
0.00
1.00
0.00
0.000
1.00
0.00
-0.00
1.00
0.00
0.00
0.99
Layer
0.00
-.00
0.99
0.00
0.00
1.00
0.00
0.000
0.99
0.00
0.00
0.99
0.8
Layer
0.00
0.00
0.98
0.00
0.00
0.99
0.00
0.00
0.99
0.00
0.00
0.98
Layer
0.00
0.00
0.96
0.00
0.00
0.99
0.00
0.01
0.97
0.00
0.02
0.92
Layer
0.00
0.01
0.92
0.00
0.01
0.06
0.00
0.39
0.40
0.00
0.57
0.16
Layer
0.00
6.4
0.31
0.00
0.84
0.06
0.00
0.98
0.00
0.00
0.96
0.00
Layer
0.00
0.99
0.00
0.00
1.00
0.00
0.00
0.99
0..00
0.00
0.98
0.00
x1
X2
X3
x1
X2
X3
x1
X2
X3
x1
X2
x3
|X|
70
|
100
|X] = 150
|x]
200
Figure 10: Causal tracing results showing indirect effect heatmaps for different token set sizes |
27

---

Published as a conference paper at ICLR 2026
D.4 TASK ABLATION
We show that GPT-2 models trained on PARALLEL-2-HE 2-H 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 | 50 and examine model checkpoints with training dataset size N = Neee () that achieve training accuracy 0.99.
Figs. 11 and 12 show the results for the PARALLEL-2-HOP task. The IICG patterns reveal strong representation clustering at mid-layers: at positions 22 and Iy when grouped by bj = fi (m1 x2). and at position 24 when grouped by b2 f2 24). Causal tracing confirms the causal role of these clustered representations the model's predictions.
0.5
Layer 8
0.5
Layer 7
Layer 6
Layer 5
0.00
IICG
Layer
00.
Layer 3
Layer 2
00.1
Layer
x1 x3
X2
x4
k>
k=
k> 0
k=0
k> 0
k=
b1
b2
Figure IIGG heatmap for 22RALLEI---HHPP task with grouping strategies based on (1 22) (Left), b2 f2 24) (Middle), and = fa(bi, (2) (Right).
Ap
1.0
Layer 7
0.00
00.00
0.00
0.98
0.00
0.00
0.00
1.00
6
0.00
0.8
Layer
0.6
Layer 4 0.00
0.00
0.01
0.60
0.00
0.00
0.00
1.00
0.4
Layer 3 0.00
0.10
0.07
0.00
0.00
0.00
0.00
1.00
Layer
0.2
Layer
0.71
x1
x2
x3
x4
x1
x2
x3
x4
b1'
62'
Figure 12: Causal tracing results showing indirect effect heatmap for PARAILEI--2-HOP task. Left: perturbation with different (æ1, x2) pair leading different by value. Right: perturbation with different x4) pair leading to different by value.
Similarly, Figs. 13 and show results for the 3-HOP task. The IICG patterns exhibit strong representation clustering at mid-layers: at position 23 when grouped by b fi 22), and at position is when grouped by b2 = 22 w2). Causal tracing again confirms the causal importance of these representations.
These results demonstrate that the formation of clustered intermediate state representations and their causal role in compositional generalization is consistent phenomenon across different task structures, supporting the generality of our findings beyond the 2-HOP task.
28

---

Published as a conference paper at ICLR 2026
Layer 8
2.40
Layer 7
0.4
Layer 6
3333
Layer 5
IICG
Layer 4
Layer
Layer 2
0.36
0.1
Layer
p.01
p.05
p.04
x1 x2 x3 x4
x1 X2 x3
X2
X4
X1 x2
x3 x4
x1 X2 x3
X2
x4
0.0
k> 0
k=0
k>
0
k=
k>0 0
k=0
b1
b2
Figure 13: IICG heatmap for 3-HoP task with grouping strategies based on b1 = =f(211 (Left), b2 fbb, ø3) (Middle), and 24) (Right).
Ap
1.0
Layer 7
0.00
0.00
0.00
0.99
0.00
0.00
0.00
0.99
Layer
0.00
0.00
0.00
0.98
0.00
0.00
0.00
0.98
0.8
Layer
0.6
Layer 4
0.00 0.00
0.35
0.29
0.00
0.00
0.32
0.28
0.4
Layer 3
0.00
0.00
0.93
0.00
0.00
0.00
0.91
0.00
Layer
0.00
0.2
Layer
0.00
0.98
0.00
-0.00
0.00
0.00
0.99
0.00
0.0
x1
X2
x3
x4
x1
X2
x3
x4
bl'
b2'
Figure 14: Causal tracing results showing indirect effect heatmap for 3-HOP task. Left: perturbation with different (2) pair leading different b value. Right: perturbation leading to different by = (b1, 23) value.
29

---

Published as a conference paper at ICLR 2026
E 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 modified 2-HOP task with | 50 and N 10k, after 40k epochs of training:
1. Standard Training: fi f2. model only sees complete two-hop examples (21, 22; 22, 233 t.
2. With Partial Computation: Si f2, model additionally sees all possible partial computations (2) >> b where b fi (x1, T2) (2,500 partial examples, not counted toward the N 10k 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. The low MRR indicates that the model's internal representation of intermediate state aligns with the corresponding vocabulary token.
Fig. 15 shows 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.
1000
Layer 8
3301.7
2709.5
13963.5
404.1
12324.7
Layer 7
912.2
746.4
7865.1
279.5
0.0
215314
800
Layer
1188.3
1466.5
7832.9
476.0
0.0
48696.2
600
Layer
MRR
Layer 4
5181.4
6416.6
9259.0
1886.7
4090.1
400
Layer 3
8839.2
8723.1
11519.3
3384.8
0.0
1678.1
Layer 2
14823.914750.5733...
10164.3
46. 1
2051.9
200
Layer
20829.924188.221982)
16836.9
4269.2
x1
x2
x3
x1
x2
x3
Non-Atomic
With Atomic
Figure 15: MRR scores for intermediate state representations projected to vocabulary space. Left: Standard training (/1 * f2. no partial computation) shows very high MRR regardless of position and layer. Right: Training with partial computation (f1 = f2, with partial examples) shows MRR in layers 3 to at position ø2, indicating strong vocabulary alignment.
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 the 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.
30

---

Published as a conference paper at ICLR 2026
F PROOFS: ASYMPTOTICALLY PERFECT COVERAGE IN 2-HOP TASK
We establish a scaling-law analysis for the 2-HOP task (as illustrated in Fig. 2a) within our formal framework for understanding pattern matching (Sec. 3). While a simplified statement (Theorem 6.1) already presented in the main text, we provide the complete results of our analyses here in great detail, along with their rigorous and self-contained proofs. This appendix long, we have organized into the following structure.
In App. F.I. we first review and (re)define the problem setting for 2-HOP task. Since the functional (k- je-iiviqvveeeee at indices 1 and 2 matters for the 2-HOP task, argue that it is enough for us to focus on / {1, 2), thereby simplifying some key definitions (e.g., substitution graph, k-coverage) accordingly.
In App. F.2, we state and prove our main theorems that characterize the number of training data sufficient for learner to achieve a perfect in-domain generalization with high probability. There are two main theorems: one is for A 2 2 (Theorem F.7) and another is for k = (Theorem F.8). As consequence, we further assume a specific regime of set cardinalities- namely, where all token sets have (n) elements-ann provide Corollary E9, combining both cases for 2 2 and
k = 1.
- We also claim that our results are nearly light, especially for h: 2 2. It is done by constructing a worst-case subclass of 2-HOP problems in which, given dataset slightly smaller than upper bound, the learner fails in achieving perfect ID generalization with high probability (Theorem F.16 and Corollary F.17).
Theorem 6. in the main text is indeed a simplified combination of Corollaries F.9 and F.17.
In App. F.3. we provide (almost) all postponed proofs of lemmas used in App. F.2. We first prove that the connectivity of all b-evidence graphs (Def. F.5), the induced subgraphs of the substitution graph, is a sufficient condition for the perfect in-domain generalization we want to show: see Lemma F.10.
App.
F.3.1 1 is dedicated explaining the renowned Poissonization technique, rigorously proving one of our main lemmas, Lemma F. 12. Under usual fixed-sized dataset sampling scheme, the edge connections of the substitution graph are not guaranteed to be independent. Nevertheless, the Poissonization technique enables us to disentangle these dependencies, thereby simplifying our analysis.
App. F.3.2 reviews the binomial random k-intersection graphs, topic in the random graph theory literature. We bring some results on the threshold functions for their connectivity (without bringing their involved proofs). It is crucial because we show that the b-evidence graphs can be regarded as binomial random k-intersection graphs under the Poissonization.
F.1 PRELIMINARIES: DEFINITIONS, ASSUMPTIONS, AND FACTS
definee as Ground-truth mapping. Consider ground-truth mapping f X X + defined f(11, 22, v2aa= = f2 (2), 23), ), two-hop composition of primitive functions fi Xi X22 B
and f2 : B X3 Y. Here, the set B == Ji (X, x X2) collection intermediate states, implicitly assuming surjectivity of without loss of generality.
Train dataset. We take train dataset D by independently sampling input sequences N times from the uniform distribution over X Xi X, X3. For the sake of simplicity, we allow duplicates/replacceents of train samples in D, thereby considering / as a multiset.
We find it helpful in analysis to define a random vector dence with a dataset constructed by sampling with replacement as described below.
that has one-to-one correspon-
Proposition F.1. Given train dataset D and for each x E X. define Z as the sampled count of x (i.e., the number of identicul duplicutes equal to x) in D. In particular, if D is uniformly randomly generated by with aedh-replacement sampling N times from X. the random vector (Za)xex follows mudtinomial distribution with parameters
N and Pa
[ (Var X).. That is, for all collections
of integers Ze 2 0 (Yz E X)) such that EBEx Zz ====0 =N N.
N X N.
P(Z.. Zz Vx E X)
IeExx(E!)
The one-to-one correspondence between D and (Zn)eex is straightforward: their realizations uniquely determine each other (up the order of sampling).
31

---

Published as a conference paper at ICLR 2026
A learner making predictions using functional k-equivalence. Let consider an artificial learner that perfectly trained on D (i.e., always predicts correctly on D). We suppose that the learner confidently predicts the output for the elements in k-coverage of (defined with functional t-equivalence), while producing a random (or unconfident) prediction outside of it. However, the confident prediction is not necessarily correct in general. Luckily, since we suppose clear two-hop compositional structure of the task, the confident predictions based functional equivalences at indices / = {1,2 2} are guaranteed to be correct. Hence, to study the scope of mattern-macchin- based in-domain (ID) generalization as confident and correct predictions on unseen inputs, we restrict the scope of our analysis to the index set {1, 2) for our analysis in this appendix.
To formalize how far the learner can generalize (Def. F.4) and how far we hope the learner to generalize (Def. F.2), let us (re)define the key terms for our analysis of the two-hop task, based on the restriction
with respect to the index set / (1. For brevity, let us write 12 (2), X12 == X X2-
Definition F2 (In-domain closure, in terms of (1,2}). For train dataset D, its in-domain closure D is defined as
D = 12 z3) E 3(1/2, X such that fi = fi (1122) (1/2, E D, and (212, E)
Also, its element (I12, x2) E D is said to be an in-domain data.
According to the definition above, the in-domain closure D contains all input sequences (I12, Ix) such that (i) its subsequences (=2(= æ1) and ra(= x.)) has already been observed in the train dataset D. and (ii) its output can be inferred using functional equivalence at indices I {1, 2). namely, fZ122 23) = f (21z2 2z) for a training data (1/2, xz3) D. Hence, the set D is the largest set of input sequences whose output can be correctly predicted using the exact task structure (e.g., the functional equivalence at {1. (.) We also remark that it is obvious to see that D C D. We wish the learner would acquire such prediction capabilities from training dataset. Nevertheless, the task structure is not directly accessible to our learner since it can only identify the necessary functional relationships through functional k-equivalences (Def. 3.1).
On the other hand, the k-coverage quantifies how far the assumed learner can actually make correct predictions using the observed functional k-equivalences from the training dataset D. The definition (Def. F.4) resembles that of the connectivity of a graph with a vertex set 1
Recall that in our main text, we defined substitution graph with the entire input space X as its vertex set since we aim to check all functional equivalences across all index sets. However, since we are particularly interested in the functional equivalences at I = {1,2], we can simplify its definition as below.
Definition E.3 (Substitution graph, in terms of 1 {1, For train dataset D and positive integer k we define a substitution graph (in terms of = (1, as (DD.)) (V,, Fx D.D))) Here, the vertex set is V. == X12 and the edge set is
k( = {{ x12) C Vo I12 + 212 and [Sy 112 D) 2 k}:
where the set (112, 2112 D) is defined
Sy D)= = (5g E X'3: : 1(112, = 10-0-(aa f(1/2 (2) 33) E D, (2 Tz) E D).
In other words, in the substitution graph g. two vertices 1 and x'p are adjacent if they have at least & distinct co-occerences in D. With this definition, we define the k-coverage as follows.
Definition F.4 (k-coverage,, in terms of I = (1,2)). For train dataset D and a positive integer k. the k-coverage of D (in terms of / = (1,2}) is a subset of X defined as
Cover (D)
(I12, 13)) EX: Briy E 222 connected to T12 with a path in ((D.)) and (2/22 v3) E D} del
(un, nz) EX: 38 2 0, Buy U1," uy E 2i such that (uş-1. u, E (D.)) (Vie (e] & (3),
where [[] (1, ,.., e).
Also, an element 23) E Cover, (D) is said to be covered.
Again, we can easily verify that D C Covera (D) by choosing & = 0 in the definition above. However, the inclusion relation between the in-domain coverage (D) and the k-coverage (Cover,, (D)) cannot be explicitly determined in general. From the next sub-section, aim to analyze when (or, with how
32

---

Published as a conference paper at ICLR 2026
large D) do have a relation "D C Cover& (D)", which we call perfect coverage of in-domain data, with high probability (with respect to the randomness of D).
We additionally introduce some useful symbols for our later proofs. We denote by BD the set of all intermediate states observed in D: i.e..
BD == {b E B 3(112 E D such that f1 = b}.
Moreover, we introduce the bevidence graph 9 (D..), defined as a subgraph of ( induced by the set V,, / (212 E X12 (1 b) C V. of vertices sharing the same intermediate state b B.
Definition F,5 (Evidence graphs). For train dataset D, positive integer k; and an intermediate
state b B, we define b-evidence graph (in terms of {1, 2)) as (. (Vo, (Vo (.D.)) Here, the vertex set V/ == ST ((b)((()))))))) ({b)) and the edge set
E == 11 112 C Vb: 412 & 1'22 and 15 D) kJ,
(4)
where the set S(x12 122 D) is defined as
S(z12, 112 D) == {āz E N' (x12, E D, (z/2. E D}.
(5)
Lastly, we introduce an assumption that will be assumed only when we claim the tightness of our sample complexity upper bound results.
Assumption F.6. The learner uses the parameter & 2 k. + 1, where k. 2 0 is defined as
k, max (b, 60)l subject b b b',
(b.b))
and Hb, = fag E X. f2(0, = f2))
According to the assumption above, xb) f2() can hold for more than k. elements in X3 only when b- = V' It is quite a natural assumption for general 2-HOP tasks since it naturally climinates pathological examples that can barely be regarded as 2-HOP tasks (e.g., a constant function f on X).
The assumption above additionally assumes that learner pessimistically recognizes the functional equivalences between {1, 2) -usubeequesssss by using 2 k. + 1. If k = k, + 1, the learner is using the precise value of i to recognize functionally equivalent subsequences sharing the same intermediate state; a higher value of k indicates more pessimistic learner. Because of this pessimism,
once the learner recognizes that 222 and 212 are functionally k-equivalent (i.c., {I12, 2/2 E P.PM), it is guaranteed that 212 and 212 share the same intermediate state (i.e., fi (Z12) fi f1(11)), More importantly, it implies that there must be no edges (in (D())) connecting two graphs ((D.M) and 9 c(D.k) for distinct 6, // B; otherwise, there must be pair of subsequences 212 V, and x/22 Vy that are functionally k-equivalent, contradicting the assumption.
Even though Assumption F.6 appears to pertain to the learning rule of the learner, it can also be interpreted as assumption about the ground-truth -trnt mapping, which necessitates k. I k 1 for given i >
F.2
MAIN THEOREM: SAMPLE COMPLEXITY BOUND FOR PERFECT COVERAGE WITH HIGH PROBABILITY
The ultimate goal of this appendix is to characterize a sufficient number of training data |D] (i.e., sam- ple complexity upper bound) so that the c-cooerage includes all in-domain data, i.e., D C Cover, (D). with high probability. Here, we will state and prove our main theorems, Theorem F.7 (for k 2 2) and Theorem F.8 (for A = 1), which are followed by simplified combination of them (Corollary 1.9).
Soon after, will also claim the near near-tightness of these theorems by showing that, for k 2 2, the training datasets slightly smaller than the obtained sample complexity are sufficient to guarantee D Coverg (D) with high probability (Theorem F.16 and Corollary F.17). Although we present the proofs of the theorems here, the complete proofs of most lemmas used in the main proofs are postponed to the later part of this appendix (App. F.3).
Here are the statements of our main theorems for the sample complexity upper bounds, which will be proved soon after.
33

---

Published as a conference paper at ICLR 2026
Theorem F.7 (Sample Complexity Upper Bound, 2, J) Under the two-hop task setup described in App. F.I, suppose that 2 2 is universal constant. Let ñ. = minge Bo [V6] and ñ = maxte Bp [Vo), and assume that [xaa = ((()). Fix any O. Then, there exists No satisfying
(())(
No 5 max
12 22 [3) In
such that, for any large enough and any integer > Ng, we have
Px (D c Covery (D)) 2 1
Here, Py is the probability measure for the train dataset D constructed by uniformly randomly sampling elements N times, allowing duplicates, independently from X = X1 X2 Xz.
Theorem F.8 (Sample Complexity Upper Bound, 1, -). Under the two-hop task setup described in App. F.I, suppose that = 1. Let ñ == mingeBo [Vo] and == maxte (Vol. and assume that [2 ( Fix any 5 O. Then, there exists Ng 0 satisfying
55) ))
N₂ S max (In (1n))-122 x X21, In
such that, for any large enough ñ and any N >> No. we have
PN (D C Covery (D)) 2 8.
We use the same definition of P as in Theorem E.7.
In particular, these two theorems can be easily combined (hence the detailed proof is skipped) in the regime of almost balanced cardinalities as (n)), which described in the following corollary.
Corollary F.9 (Power-Law Sample Complexity Upper Bound, Simple). Under the two-hop task setup described in App. F.l, Assume that Xr. X2, X', and Vo (vb B) are all the sets of size (n). Fix any k 2 1 and any >> Then, there exists Na(n) > 0 satisfying
(1 2k
for k 1;
22 ( max n 2.5 25---
(kl (mm), In 2)))
No(n) S S0
with y
for k 2 2,
such that, for any large enough n and any N (n). the learner with a uniformly randomly sampled training dataset D (with replacements) achieves a perfect coverage of in-domain data, i.e., D C Covery(D) with probability at least 5.
Now, we prove our main theorem for k > 2 (Theorem F.7). After that, we will present the proof of the other case (k 1, Theorem F.8), which follows a similar plot except for few steps at the end.
Proof of Theorem F77. We begin the proof with the following observation: sufficient condition for a perfect coverage is that every b-evidence graph (Def. F.5) a connected graph.
Lemma F.10 (L). If all (.P))) are connected graphs (Vb E Bp), then we have D Covery (D))
Refer to App. F.3 for the proof. Thanks to the lemma above, it suffices to show the following with sufficiently large N D|:
Py D & Cover,(D)) Lemma F.10
PN (3b E BD such that (DM)) disconnected) s
To this end, consider the multinomial random vector (Z=)xxx corresponding to randomly sampled training dataset D, as defined in Proposition F.1. Define a property C as
(Za) CC >> (!D,A)
()) is connected vb Bp.
(6)
34

---

Published as a conference paper at ICLR 2026
Then, want to compute upper bound of probability PN ((Zz) C). Observe that the property
a non-decten decceaeean property (Def. F.11): a vector (Z satisfies C, then still satisfies C after increasing in its entries by non-negative amounts. In other words, the negation of C ("not satisfying C") is a non-increasing property. This is because adding data point the training dataset does not remove any edge from all evidence graphs, thereby preserving the connectivity, In general, we define the monotone property of vectors as below.
Definition F.11 (Monotone property). We refer to a property A of m-dimensional vectors as non-decreasing property when, for any vector (Ai,... (AI,..,,Am) Am) with non-negative entries A; (vi = , m),
(2 2m) E A = (21 + A + Am) E A.
(Non-Decreasing Property)
On the other hand, we define non-increasing property A as what satisfies
(Z 2m) EA
(21 , Am) E A.
(Non-Increasing Property)
Taking advantage of the monotonicity, we can apply the Poissonization technique (App. F.3.1) to obtain an upper bound on the probability PN ((Z))=e & C). The Poissonization technique we use is summarized as the lemma below, which will be proved in App. F33.1:
Lemma F.12 IDe-Posssonization of Monotone Multinomial Events, J). Fix any 2 1. Define
Pn == P ((2 (121.--Z.m.--- --m--mmtttnnmmaaaaa pt.)"Ppm) ((Z), ... ,mn A).
Let be nen-decreasing property (Def. F.11) of m-dimensionall vector. Then, we have an upper bound and a lower bound for Pn, as follows:
P. Pr((nte) ((Z), Zm) A) + exp
(3-c)c²
(Ve E (0,3), Vs E (n)c
P. Pro(u-e) ((Z,, ... Zm,) A) exp
(Ve (0,
2m
If A a non-increasing property (Def. F. 11, then we have similar upper and lower bounds for P.:
Pn < Pro(n-e) ((Z1, ,,, ,,m) E A) + exp (-
(Ve E n0)
2n
Pn 2 Pro(nte) ((Z1, .., Zm) ) E A) - exp (- (3-c)e²
(Ve E (0,3), Ve E (0, cn))
6n
indep. Poisson (Vi = 1, m)
Here, we denote by Pro()) the probability measure under Z;
In particular, considering the disconnectedness (Ab E Bp) as non-increasing property, we have
PN (3b E Bn such that (P is disconnected)
(Po((N-c) (36 BD such that (. is disconnected) exp
E²
2N
Σ PP)(N-S) (.. is disconnected) + exp (-
E²
(: union bound)
2.V
BEBD
for any positive number < N, where (PO(N--) is the probability measure under i..d. Poisson random variables Ze Poisson N
(vz E X). Let us take e v 2N in (2). which is smaller
[X]
than N by our choice of N₂ and ensures that
8
exp
exp
In
2N
Now, we claim that each b-evidence graph gf is binomial random k-intersection graph (App. F3.2) for every b E Bp, under the Poissonization governed by PPo((N-))
Lemma F.13 (Evidence Graphs are Binomial k-Intersection Graphs under Poissonization, }). Let any E Bp. Consider a vector tz)wex associated with a dataset D (i.e., an input sequence æ is sampled Z. times in D). Let PPO(A) be probability measure for 7 ltd. Poisson (2/171). Then,
35

---

Published as a conference paper at ICLR 2026
under Po(()) the beevidence graph 9b graph ((k) (no, m, m, p) with parameters
(D.)) (Def. F.5) instance binomial random k-intersection
A X
m& [V], 1 p= 1 exp
Based on such observation, can the following seminal result about the connectivity of binomial random k-intersection graphs with p = 1 exp(-(NV - In particular, we will use only the "k 2 2" part (which tightly matches our assumption (2(ss)) (vb E Bp)) below:
Lemma F.14 (Zhao al., 2014, Theorem 2; Zhao al., 2017, Theorem 1 & Remark 1). Fix any k 2 1. Suppose that
{ (Iun) nee)), if 2 2,
Ω min (n).
if = 1, for any > 1;
m
and
p k! (Inn + an)
#
(7)
m
for any sequence }an} which attains limit Oloo E { +00| cc. Then,
lim IP (g(h) m, p) is connected) = lim miin (()) (n, m, m) 1) = =exp (-e n-+00
n-000
where we compute exp (-e-(-o0)) = and cxp (-c-(too)) =1.
Now, we aim to find a sufficient condition for N to have
Σ
PPO(N--) -e)
( (D,k) is disconnected
8 2
(8)
DEBp
Let us choose the sequence an Inn Lemma F.14, which guarantees that (Kg( (n, m, is connected) 1 as n 30.
From the definition of the limit of a sequence, for any choice of 0, us define no(o) > > such that
((g (n, m. p) is disconnected) S
Vn > no(
Then, choosing all n, |V, be greater than nu 2 we yield the bound (8). Note that choice
of p larger than the threshold in Eq. (7) will never change that ((G(()) (n), m. p) is connected) - 1 as
+ co. Thus, since we choose On.. Inn, it suffices to have
N
k! (2 (m
1
p exp
7b
V
for each nu, (vb E Bp). Since - - 2 (1 for large enough e, suffices to have
) ju for 0 < u < 1 and In is decreasing function
11
N
k! (2
1
X
à
for â minsen Bp ny. Plugging in 8
v 2N In (3)
and X
12 x X22 |2aa,,
we have
2
k! (2 (2
1
N
2N In
>
|2 X5l //1
e 2-
36

---

Published as a conference paper at ICLR 2026
which is satisfied by
de he (2In (
2
N 4. max
12g x x
In
In conclusion, for large enough max {no B satisfies the inequality above, we finally have
E
provided that the training dataset size N
(36 BD such that k( is disconnected)
N
8²
Σ PPo(N-e)
(g% is disconnected) + exp
2N
BEBp
6
$ + = d.
2
2
This concludes the proof of the theorem.
Proof of Theorem F88. Even for k = 1, we follow almost the same proof as that of Theorem F.7, except for the last few steps. Namely, we again observe that every ( is a binomial random 1-intersection graph (n,, m, p) with parameters пı, |V/,, m = |/Kg) and p = exp(-(NV E)/ ()) (see the definition of binomial random intersection graph in App. F.3.2). To guarantee the union bound in Eq. (8), however, we use different lemma: Lemma F.15 (instead of Lemma F.14). In particular, we will use only the "p S 1" part (which tightly matches our assumption m = O(m,) (b E Bp)) of the lemma below:
Lemma F.15 (Singer, 1995, Propositions 3.1-2, Theorem 3.3). Let ks = 1. Suppose that m = nº for > 0 and
Inn + On
for S 1;
p
Inn + On
for prrp" > 1,
mn
for any sequence {an} which attains a limit Ono E (-00, +oo} as n - xc. Then,
[0 i -X;;
lim ((g()) m, p) is connected) lim IP (inn deg ( (n, (m, 21) [1, if +00. n=000
1,
n=00
Again, let us choose the sequence on Inn in Lemma F.15, which guarantees that P(g()) (n, m.p) p) is connected) + 1 as + cc. From the definition of the limit of a sequence, for any choice of 8 0, let us define no(8) > 1 such that
(P( (n, m. p) is disconnected) S
Vn no()).
5 ) we yield Then, choosing all nı = |V/ (and thus ñ mingeB, n4) to be greater than no 2|Boo| the same bound (8). Now, by our choice an = In n, suffices to have
2 nb
1 exp
2
124s
for each n2, (4b E BD). Since 1 - e 2 (1 for u > it suffices have
f)u for < u < and In is an increasing function
1 (1-
N
2 á
X
for ń == maNteB Bp Thp Plugging e =
2N In (3) and
| = | x X2| Kxs,, we have
N 2N
2
(2)
8
>
(2lmn) |2 x
e
37

---

Published as a conference paper at ICLR 2026
which is satisfied by
N 2 4 max )
(7))
x,2,, In
In conclusion, for large enough à 2 â > max mo
2T 3.. provided that the training dataset
size N satisfies the inequality above, we finally have
PN 3b Bn such that (. is disconnected)
(g. is disconnected) + exp (-
8²
2NV
DEBp
8
+ = 6.
2
2
This concludes the proof.
Subsequently, we argue that the sample complexity upper bound obtained in Theorem F.7 (for k: 2 2) nearly tight.? To this end, we show that the learner (we assumed in App. F.1) cannot avoid an incomplete coverage (i.e., 7) g Coverg( (D) with high probability, with dataset slightly smaller than our upper bound for certain instances of the H-HOP task. In particular, it is enough to consider a subclass of the 2-HOP task satisfying a mild condition (Assumption F.6) that any two distinct intermediate states in B never share the same output for more than (, k) tokens in &g. The formal statement of the tightness result is shown below:
Theorem F.66 Teear-Tigttness.. of the Sample Complexity Upper Bound for k 2 2, 1). Under the two-hop task setup described in App. F.I, suppose that k 2 2 is universal constant. Let == minseB B Vol and ñ := max B [Vol. Assume that [Xa] = Q(n and [X x xX22 2 6. Let us further assume that the ground-truth mapping satisfies Assumption F.6. Fix any 8 > 0.
Then, there exists N8 > O satisfying
(k 1)! (k-1)! (In
N& 2
12 x
X21
v
such that, for any large enough á and any integer N satisfying the range
{ | x In
4 4|2 X2
[ In 4 x
max
S N << Ño
8
we have
PN D Cover (D)) S 8.
We use the same definition PN as in Theorem E.7
caveat of Theorem F.16 is that makes sense only when the range of N is nonempty. Luckily, is easy to verify its validity in the regime of balanced cardinalities, similar to what we assumed in Corollary F.9. As result, we establish the rightness (for k 2 2. up to constant factor) of our sample complexity upper bound in Corollary F.9, among the data sizes N X ne² In n (Corollary F.17). Note that, shown in the middle of the proof of Theorem F. 1. O( In n) is indeed the data size which is sufficient to guarantee that the learner observes all possible pairs X; x X2 and B x Xs, ensuring that all possible input sequences in X are in-domain, with high probability.
Corollary F.17 (Tightness of Sample Complexity Upper Bound for k 2 Simple). Under the two-hop task setup described in App. F.1, suppose that |xa| = [2 = [2gl = |B] [Vol = (Vb E B). Also, assume that the ground-truth mapping f satisfies Assumption F.6. Fix any 2 and any 5 > O. Then, there exists Na(n) > O satisfying
Ño(n) 2 2.5- 2 ((k - 1)! I)
We often say complexity upper bound is tight if we can find a worst-case example whose complexity lower bound is almost identical the upper bound.
38

---

Published as a conference paper at ICLR 2026
such that, for any large enough nt (e.g., such that kn > 256e(lan)) and vī((nn) >
4(In })²) and any integer N satisfying that
n² (n SN No(n).
the learner with a uniformly randomly sampled training dataset D (with replacements) cannot achieve a perfect coverage of in-domain data, ie., D &f Covery (D), with probability at least - 5.
From now on, we prove Theorem F.16, the tightness result of the sample complexity upper bound obtained in Theorem F.7.
Proof of Theorem F.16. We aim to prove that, even when the dataset D is large enough to ensure that D) = X. the incomplete coverage may happen with high probability for certain range of data size N. To this end, let us first define two sets D12 and DB3 as follows:
D12 == {x12 E X12 3zz E A' such that (112, E D): DB3 {(b,03) E B Xx 1212 Vi such that (212, 23) D}.
Also, we denote by min deg := min degg (v) the minimum degree among all vertices of a graph G (V, E). With these definitions in place, we now apply the following lemma, which describes a necessary condition for perfect coverage.
Lemma F.18 (L). Assume that D12 = = and DBa = B x X3 hold. Then, these imply that D X. Furthermore, suppose that Assumption F.6 holds for given 1 S k S Rsl. Then, D Cover (D) implies that min deg g (DD.) 2 for all b E B.
Refer to App. F.3 for its proof. Now, it suffices to show the inequality below:
FN D C Cover,(D))
PN D Covera( or D12 F X12 Da3 # B Xs)
Fv min deg (..)))
(vb B) or D12 + X12 or DBA + B xxxxs
(: Lemma F.18)
(D.A) S FN min deg g ( (4b B)) + PN (D12 + X12) + PN (DB3 + x Xz) S 8.
(9)
To this end, consider the multinomial random vector (Ze )xxx ~ Multinomial (px) xxx) corre- sponding to a randomly sampled training dataset D, as defined in Proposition F.l. Define property M1 as
(Zx) Mi min deg (. (vb B).
(10)
Also, observe that
Tap
Σ
(Ten)apEXX ~ Multinomial(N;; 2mpEx)))
if
xsEX,
Σ P(Z12
O212
23EXa
U(b.es)
= Σ
7
(Uw)eEBxXs ~ Multinomial(N; (xx)))
#11EV/
Σ
T(baas))
P(r1
312EV
where we can actually put P(Z12,a)) notation, we know that
1 G812
Xal
Pial and T(b,zs)
[6]
above, Using this X
D12 = X12 +
Te 2 (Vr1 E X12);
DB3 = X's
- Um 2 1
(Yw E Xz).
39

---

Published as a conference paper at ICLR 2026
Hence, show Eq. (9), it suffices to prove the following three inequalities:
8
P(zz) MecaeeeeeMMtttoooaaii/.ee.ee
((-m) E &Mi)
(11)
2'
8
P "unggggghhn-MiibbmmmaaaMelaMaaaa (3x12 &12 such that T212 0)
(12)
4'
8
(Jw E B X3 such that Uw 0)
(13)
4'
size N of training dataset that sufficient to ensure Eqs. (12) and (13) can characterized with the following lemma.
Lemma E.19 (A Tail Bound for Coupon Collector's Problem, U) Consider a multinomial random vector (Z,,"", Zm) Multinomial(;; Pl, Pmm) Then,
P(3i such that Z, 0) - Σ p.)
In particular, if = minigigm Pt, then for any 8 > 0.
In m 7 P(li such that Z; = 0) S 5.
n
5
See App. F.3 for the proof. Applying the lemma and minjeB 8 [Vll, we can figure out that the
data size
( 4
[4]
X ft
4 B x Xss
N max |2121
In
(14)
enough to ensure both Eqs. (12) and (13). The remaining task now is to determine a condition for N that guarantees Eq. (11).
Observe that M1 (defined as Eq. (10)) is non-decreasing property (Def. F.11)) because of a similar reason for the monotonicity of the property C (defined as Eq. (6); the proof of Theorem F.7). Thanks to the monotonicity of M₁, we can apply the Poissonization technique (Lemma F. F.12) once again. That is, taking any fixed c (0, we have
Pv mmi deg (..)) 2 (tbEB))
< PPo(N+)) (min deg g (D.)) 2 (vb E B)) + +exp
(- (3 (3-c)="
6N
c)e²
$ PPo(N++))
min
deg dog 9 (D,)) 21) + cxp
(vb E B),
6N
for any cN), where Po) is the probability measure under i.i.d. Poisson random variables
7mm Poisson
Ntc [
(Var X). Let us take & = 3-c In (f). which is smaller than N by Eq. (14)
(since
K212 2 J-c and ensures that
exp (- (3 (3-c))² = exp
In )
8
(- 6.V
4
Moreover, again use the fact that () is an instance of binomial random k-intersection graph ((k) (ng. m. p) with parameters n4, [V).. m [. and p 1 1-expp (-(N + +)/ under the Poissonization governed by FPo[N+e)- Since we assume k 2 2, we can use the "k 2 2" part
of Lemma 14 In particular, we are to apply Lemma F. for an evidence graph g (D.)) with
b E arg minyen [Vo (thus, n, ûi), which is possible since assume | = 2(n). We aim
to find sufficient condition for to have
PPo(N++) (min deg
g. (D.A) > 1)
(15)
40

---

Published as a conference paper at ICLR 2026
Let us choose the sequence on - - })) In in Lemma F.14, which guarantees that P(min ((k) (n, m. p) 2 1)
cc.
From the definition of the limit of sequence, for any choice of 8 > 0, consider no(6) satisfying that
P (min deg ((h) (n, m. 1 S 6,
no(
Then, choosing á greater than no (2), we yield the bound (15). Observe that choice of p smaller than the threshold in Eq. (7) will never change the limit (mmmnn deg ((k) (n, m, 2 1) - 0. Thus, by our choice an -(1 1)) In n, it enough to have
N +
(k
(k-1) 1)! (In
1
p 1 exp
X
f
Kg
Applying 1 e 14 < for R. it suffices have
N +
(k:
1)! (In
1
X
V
Plugging cN and X
| x 82) Ks) in, we eventually have a sufficient condition
(k (k- 1)! (m 1 +
N
x Asl.
ft
To summarize, for large enough á no (1), provided that the data size N satisfies
(In))) de
max { | In
4 K12l
X
4|
1
In
8 SNS
1+c
and take
6NN 3-c
In (+), we finally have
PN (D Covera (D))
(min deg deg (D.)) 2 21) exp
[3-c))²²
c)e²)
+P)
PN (D12 # M2) +N (Dnz + BxX2)
GN
8 5
8 = 8.
4
Since the choice of e E (0, 2) is arbitrary, we obtain the same result (I (Px(....) - 6) by letting e Y and choosing N which satisfies that
max {
| In 4 K1
X n
4|
(k (k- n
NN
Before moving on to the postponed proofs of lemmas, we lastly remark that the same proof (of Theorem F.16) can hardly apply to the case of k 1 in general. This is because, for the sake of simplicity in applying the necessary condition for perfect coverage (Lemma F.18), we first characterize minimal data size to guarantee D X with high probability as Eq. (14), using the tail bound of the coupon collector's 's problem (Lemma F.19). Unfortunately, it already exceeds the sample complexity upper bound to ensure D C Cover, (D) D) (obtained Theorem F.8) for k with high probability, especially in the regime of balanced cardinalities assumed in Corollary F.17.
41

---

Published as a conference paper at ICLR 2026
F.3 BACKGROUNDS, USEFUL FACTS, AND LEMMAS
Now, we delve into the detailed backgrounds to provide comprehensive understanding of the main theorems' proof, along with the deferred proofs of the lemmas used carlier.
We begin with the proof of sufficient condition for a perfect coverage (Lemma F.10). For readability, we restate the lemma here.
Lemma E.10 (L)- If all g.D.A) are connected graphs (vb E BD), then we have D C Cover;
Proof of Lemma F.10. Take any (I12, ra) E D. By definition (Def. F2), there exists 212 E X222 such that fi (111) (1(22) and (12,, Tz) E D. Let b = f1(112 E Bp. By assumption, there exists a path in Gb ((..)) connecting 312 and 2/2- which we write uo(= x12), u...... up(= z1z) for some integer & 2 1. Then, for each i [8]. we have set S(u=1:: 14 D) (defined in Def. F.5) of size at least For each Øy E S(,,,1, 04 D). both (u;-1, Z2) and (u,, Tg) are both in D. Also,
f(u--1, - f2(b,
(u,,T3).
meaning that the set Sy (y4-11, D) (defined in Def. F.3) is the same S( D), set of size at least k. for each E [e] Hence, (f12, satisfies the definition of k-coverage with a path Wo..... tgg i.e., (212, ma) E Cover,(
u4
Next, we show necessary condition for perfect coverage (Lemma F.18). Before proving the lemma, we recall that we have defined two sets:
12 == 1212 E 122 323 E X' such that (I12, 23) E D};
D (() B X3 Ar Vi such that (212, 2x3) D}
Also, for a graph G (V, F.), we define min deg == mingev degg(v) as the minimum degree among all vertices of G.
Lemma F.18 ()). Assume that D12= 212 and DBa B x X3 hold. Then, these imply that D X. Furthermore, suppose that Assumption E66 holds for given 1 < k S (2g). Then, D C Cover, implies that min deg L (D.R) z ffoor all E B.
Proof of Lemma F.18. We first show that D12 X12 and DB3 = B x X's imply that D = X. Since already have D) c X by definition, it suffices to prove X C D. Let any 312 X22 and mg Xs. and take b- fi (x11) E B. Let us define:
Wz12 =ta's E X' (212, 2'3) D}:
((b) {112 Vo: (4 x')) E D}.
The conditions D12 = X12 and D33 = B x X's imply that W # Ø and W!th) + Ø, respectively. If we take any 2/3 Wayn and 412 E Wil) they hold that (z12, x//) E D. (1)2 D, and (1 = 6 = (x This set of conditions is equivalent (I12, D; hence, we have just shown that
D12 = X12 and DB3 = B x X3 = D X.
Now, we prove the contrapositive of the lemma. Suppose that min deg g. (P = 0 for some e B; we aim to show that Cover, (D) f X = D, or, X \ Covera (D) + Ø.
Take a b E B such that min deg g (D.)) 0, which implies that such graph (D has an isolated vertex F12 Vo (i.e., degg.o..) (212) = 0). Let us fix such an ø12. Since we assume Assumption F.6,
((Pb)) for distinct b, 6' E B. Thus, T12 must be isolated vertex in the whole substitution graph g! The isolation implies that, for any IC E X3, the input sequence (I12, cannot be in the k-coverage of D unless it is already in D.
there must not be any edge connection between Gf (D.E) and G
Observe that Waip A Ø for any 2'2 X12: otherwise, it inevitably holds that (4/2, + D for every 33 X3. which contradicts to the fact T> = X (under the assumption of the lemma). Thus, we can think of the following two cases:
42

---

Published as a conference paper at ICLR 2026
Case 1 (0 * 211 Kz). Take any 23 W which implies (#12, 22)) D. Thus, we have an element (I12, Fz) X Cover, (D) because 112 is an isolated vertex.
Case (W212 = Rz). Since ø is an isolated vertex, it is not adjacent to any other vertex 2'12- Fix any such an z12 E X12 \ {I12}. By definition of the edges in E k.(D.)
know that [W,,, m1 n n < k. Since W = X3, we also know that |Wa;p] < h - [xa]- This implies that 2/2 cannot be adjacent to any other vertices in &12. meaning that 2 is an isolated vertex. Moreover, since W ç 23 (:' [Wai, #12 < (Ks)), we take any 23 & Wafp- Then, since (3) & D and 412 is isolated, we have an element (#12, 23) E X Covera (D).
In both cases above, obtain the same result that X \ Covera (D) # Ø. It concludes the proof of the lemma.
We also prove the tail probability bound for the coupon collector's problem (Newman, 1960; Erdös Rényi, 1961) here. We again restate the lemma here for the sake of readability.
Lemma F.19 (A Tail Bound for Coupon Collector's 's Problem, 4). Consider a multinomial random vector (Zz, 11 Z ~ Multinomiall(;; P1, ... Pmm). Then,
P(Ji such that Z, - 0) s Σ (1 -P))".
1=1
In particular, if minjsigm Ps, thenfor any 8 0,
n In
P(3i such that Z, = 0) 5.
Proof of Lemma F.19. Observe that Z, ~ Bin(n, pı) for each E [m]. It implies that P(Z, 0) (1 - p=) One can yield the same result by directly summing up the multinomial probability masses and applying the multinomial theorem: for instance,
n!
P 11
Σ
P2
P
(p2 + + Pmm) = =11-1"".
22!
2m
Thus, by applying a union bound,
P(3i such that Z, = 0) -
Σ P(Z, - 0) i=1
p.)" S mm1 6)" S m
1=1
where we apply P minisism Ps and 1 + u S (Vu R) in the last two inequalities above.
Solving me -mp mp 5, conclude that In m implies PP3i such that Z, = 0) < 6.
O
F.3.1 JOISSONNNNNNN OF MONOTONE MULTINOMIAL EVENTS
Randomization probabilistic technique that provides convenient way to analyze a sequence by treating the sequence index as a random variable/process. When the sequence (a, Jn20 is monotone and bounded, in particular, it provides an and the expectation [[[ax] in terms of a non-negative integral random variable N. The following lemma provides a simple conversion between a deterministic monotone bounded sequence and the expectation of the randomized sequence, which we will prove later.
upper/lower bounds of the difference between
Lemma F.20 (De- Rondommmininnnnn Lemma, General, 4). Consider a non-decreasing real-valued sequence {ag 322 which lies in a closed interval (m, M), i.e., m S ag S 01 S 02 ... < M. Let N be a non-negative integer-valued random variable with probability mass P(N = j) = Pj
0, 1, -). Then, for any 2 0, it holds that
E[an] (M-m) mm) IPPNNNN S an & ElaN]] + (M m)) P(N <n). (Non-Decreasing Case)
On the other hand, if {az}iz0 is non-increasing, i.e., M 2 an 2 01 2 02 2 m, a similar result holds that
Blax] (M- mm) IPNN < n) < an <[[aN] (M m) P(N n). INon-Increasing Case)
Here, all expectations are taken with respect N.
43

---

Published as a conference paper at ICLR 2026
Remark F.21 (On the choice of random index N). When obtaining an estimate of sequence value using the lemma above, is unnecessary to utilize the same random variable N for both upper and lower bounds. Namely, when the sequence is non-decreasing. choice of N with E[N] > n [E[N]
gives a small lower tail P(N < n) for the upper bound; whereas N with a small upper tail P(N > n) for the lower bound. We can think of the opposite relationship for non-increasing sequence well. Moreover, to guarantee the tail bounds to be small, often choose N having a lot of mass concentrated around its mean (e.g,, sub- Gaussian); then, we can take advantage of concentration inequalities associated with N to have a better estimate of On R Elax].
gives
Poissonization (Kac, 1949; Holst, 1986; Aldous, 1989; Jacquet & Szpankowski, 1998; Johansson, 1998; Borodin et al., 2000) can be thought of as special case of randomization using Poisson random variables. A Poisson random variable N Poisson(A) with parameter À > 0 equipped with probability mass function
^ n!
P(N n)
0,
(Poisson)
In this section, our primary goal is to complete the proof of Lemma F.12, asserting that the Pois- sonization technique is particularly advantageous for analyzing a monotone property (Def. F. of multinomial random vectors (e.g., the connectivity of random graph whose edge connections are sampled with replacements). To see why, let us first review elementary property of Poisson random variables: the sum of independent Poisson random variables again Poisson random variable, whose parameter is the sum of the parameters of individual Poisson variables. We defer the proof for brevity.
Lemma F.22 (L), Consider mutually independent Poisson random variables Z₃ Poisson (X:) 11 1....,mm) m)) Then, Σ Zí Poisson (E== Xi).
Next, we explore the relationship between multinomial and Poisson distributions by establishing an equivalence between the probability associated with multinomial random vectors and the conditional probability of mutually independent Poisson random variables whose sum is fixed, As result, we can construct Poissonization of a sequence probabilities by regarding the multinomial random vector's 's parameter n as a Poisson random variable. The detailed formal statement is below, although we again defer its proof.
Lemma F.23 (L). Let A be any property of a (random) m-dimensional vector: we write (Z1, "5,, , E
AZ1( "",,"""","," Fm) satisfies the property A. Then, for any X > 0, and p1, " > 0
that sums to (i.e., Ei=1 Ps =1},
MMulti(a) (Z,,..., Z,,) A) = Pro(()) (Z,,..,,Z,u -m) A
Σ
Zi
1=1
Here, Muuliitnn is the probability measure under (Zi,..., Zm) ~ Multinomial (mz; P1..... ....)...))) ).n) whereas P PP((A) is the probability measure under Zi ~ Poisson(Ap:)) (i = 1,...,m, which are mutually independent. As a result, it holds that
Ex-Poissu(() [PAsuLEEN)) (1Z)..... ..,, Zm) E
A)] =|] (Poocs(((1:) ((,,,..,, 2m) E A)
We now move our attention to a monotone property of (finit-diieensional) vectors, of which we recall the definition again.
Definition F.11 (Monotone property). We refer to a property A of m-dimensional vectors as a non-decreasing property when, for any vector (A,, "3,,,.., Am) with non-negative entries A; 2 0 (Vi L,........ m),
(Z 2m) E
(21 + Ai, 2m + Am) E A.
(Non-Decrcasing Property)
On the other hand, we define non-increasing property A as what satisfies
(21, (2,, =m) E EA-
(21 A,...., Am) E A.
(Non-Increasing Property)
monotone property of multinomial random vectors has an interesting feature: the probability of sat- isfying the property is also monotone in the parameter n of the multinomial distribution (Lemma F.25). This is roughly because the multinomial distribution is inspired by multiple independent trials of with-reellaeemen sampling: an additional trial corresponds to the increase of the parameter by 1. This intuitive explanation can be formalized into the following lemma.
44

---

Published as a conference paper at ICLR 2026
Lemma E.24 (4). Consider random vector (Z1..... Zm) Mmn) "1,"""" p. (Pm)fov for 2 1 and Pi,''",Pr > 0 such that Ei=1 1. That is. for any non-negative integers 21,-11 2m whose sum is
n2!
P( 21,
7m
2m)
Pm
(Multinomial)
Also, consider categorical (so-called multinoulli) random variable Categorical(pt .... Pm.) which can have a value among the integers {1, 2, ... m.) i.e, for each = 1, ,
P(j i) Pi-
(Categorical)
Then, if we let Z, = Zi + (j=i)) for 1 < S m, we have new multinomial random vector as follows:
(Z.,..., Zm) Multinomial(n- + ".P,,".,PPii
Using the above a key lemma, we can prove the following lemma about the monotone property of multinomial random vector.
Lemma F.25 (L), Recall the definition of of Multi((j) Lemma F223. Fix any integers 1 S n S n'.
a property A is non-decreasing, then
Mullt((n) ((Z1,-.., ,2,) A) S Mulls(ny) ((Z),... Zm) E A).
The direction of the inequality should be opposite ("2") if the property is non-increasing.
Most importantly, thanks Lemmas F.23 and F.25, we can apply the de-randomization lemma (Lemma F.20) for the sequence { of probabilities defined with a monotone property A as
Un Mulltin)) (1 2m) E A).
The only things left to obtain a complete Poissonossoni lemma for upper/lower-boundeee bounding the sequence an are the tail probability bounds for Poisson distribution. The concentration inequalities for the Poisson distribution them for our own purpose.
already well-known, 8 although derive slightly different forms of
Lemma E226 (L). If Poisson(n for any and n, it holds that
P(N 2 n) S exp
(Upper Tail Bound)
2n
On the other hand, Poisson (n + E) for any and en for some E (0,3).
P(N 5) S exp (3 (3-c)=²
(Lower Tail Bound)
Gn
As result, we finally summarize the arguments in this section the following de- Poissonizzation lemma for monotone property of multinomial random vectors:
Lemma F.12 (De-Poissonizationn of Monotone Multinomial Events, J). Fix any 2 1. Define
P, = P (Z (m.nn-77)-MMnniiiiiii PL."" ((Z,, Zmm A).
Let A be non-eecrggiing property (Def. F.11) of m-dimensiional vector. Then, we have an upper bound and a lower bound for P, as follows:
P. Pro(ute) ((Z1, Zm) A) + exp
(3-c)=²)
(Ve (0,3), Ve (n))
P. PPo(n-e) ((Z,,... Zm) A) cxp
c²
(Ve (0,
2n
If a non-increasing property (Def. F.11), then we have similar upper and lower bounds for P.:
Pn < Pro(n-e) (11,.... .m,..)) E A) + exp (-
(Ve E n0,
P. 2 Pro(n+e) ((z,, ... 2m) A) - cxp (- (3-c)=² 6n
(Ve E (0,3), Ve E (0, cn))
indep. Poisson (p:) (Vi = 1,...,m),
Here, we denote by Pro(X) the probability measure under Z;
For example, document online: "A short note Poisson tail hounds."
45

---

Published as a conference paper at ICLR 2026
Proof of Lemma F.12. This is the combination of Lemmas F.20, E.23, F.25 and E.26.
We use this de-Poissonization lemma in the proof of our main theorem (Theorems F.7 and F.8).
Lastly, we conclude this section by presenting all the deferred proofs.
Proof of Lemma F.20. In the first part of the proof, we deal with the non-decreasing case. Observe that, since an has finite expectation (m I [R[ax] S M), the infinite sum Σj20 Pyny converges.
Now, let us first obtain the upper bound. Since Σ,20 = 1,
Og
E Pjan +
Epran
$2n
Σ Pjan + ' pzaj
(: 2 an if 2 n)
03j<h
J2R
Σ Pj(an -a1)
Σ
Pjoj
0Sj<n
j20
S (M -m)
Σ Pj Σ
Pjaj
(:' an 0, S M m)
0šj<n
1>0
= (M - -m) PPN < n) + E[aN].
Likewise, we obtain the lower bound.
an Σ Pjan + Σpjan
05i5n
j2n
2
Σ Pjaj +
Σ
Pjan
(: S a, if S n)
03i5n
j>n
Σ Pjuj
Σ
Pj(aj - an)
120
j>n
Pjaj
(M -m) Σ
Pj
(: an aj 2 m M)
120
j>n
= =[aa]] (M- - m) IP(N n).
These imply the inequality
Case) and prove the first part of the lemma.
The second part for the non-increasing sequence }a,} directly follows by applying the first part to the non-decreasing sequence {b..) defined as bn == M + m dg Indeed, we have
E[M + m ax) (M - m) PPNN > n) S + m an S E[M + m an] (M m) P(N < n),
which implies the inequality -oo-esnceg Case) and concludes the proof of the lemma.
Proof of Lemma F.22. Denote the sum of random variables by Zm : Σm Ze Likewise, let us write Xm = E Xi. To prove the lemma, proceed with the induction on 1.
Since the base case is obvious (Z1 ~ Poisson(A1)) )), let us assume m 2 2 and compute the probability mass. The inductive assumption says Zm-1 Poisson (Am-1). which is independent of Zm due to the mutual independence of .., Zm. Then, for any non-negative integer ž,
PP (2 = 2)
Σ Fm 00
P(2m-1 = --- Em, 2m = 2m
PP (/2mm = - -=Zm)
) IP(2m 2m)
(:: (-2m-1 1 Zm)
Z!
exp (-Am-1) (mm-1)5-2m
expl Am) (Nm
(2 2m
Zm
46

---

Published as a conference paper at ICLR 2026
exp
_i=1
Xx)
E!
(mm- 3--20 am 202
2!
(3
Zm .2m
-mm
Zim =0
exp (- -is Ae)
2! (Am-1 + 2m)
(:: binomial theorem)
exp Σ Di=t Xn) (Xm)²
Since the choice of is arbitrary, by induction, this ends up proving that Zm Poisson (Am).
Lastly, we remark that one may prove the same result without induction, by directly applying the multinomial theorem (which is essentially a recurrent application of the binomial theorem). [
Proof of Lemma F.23, By the law of total probability, for any probability measure P under any distribution a random vector (Z1. Zm
P((ZI,.... .. 2m) E A)
Σ
P(Z = -1, Zm = 2m).
Thus, it suffices to compare the multinomial distribution and the conditional distribution of a Poisson random vector given fixed sum: namely, we aim to show here that
(Mults()) = 21, ".. Zm 2m) = PPO()) (Z) = -,,-.. ... Zm
Σ Zi = n. (16)
am
Moreover, it is sufficient for proving the first equation to study the case with non-negative integers 21: ....,, 4m such that Σ 2, n; otherwise, both sides of Eq. (16) are zero. In this case, observe an inclusion between events
121 = 21 Zm = 2m3 S
[ t=1 Z =
(17)
Because of this, we can compute a conditional probability mass as:
PPO(A) (21 -,, Zm 2m Σn
Zi = m1)
Pro(A) (21 21, 21. Zm 3ml)
(:: Eq. (17))
PPP(A)) (21=1 Zi = 11)
Api (Apr)**
c A--2" -1
(: Σ Z: ~ Poisson(A), due to Lemma F.22)
zz!
n!
21 --. 2m ........
Pi
p
(: Em 2; =n)
= -PMulti(n) (Z1 .., Zm 2m).
Therefore, we have just proved Eq. (16).
Lastly, we conclude the proof by computing the expectation in terms of N ~ Poisson(A): since P(N = 5) = PPO(A) (E Z, j) (:. Lemma R22),, by law of total probability,
E (N [FMutuica) (14),..,,Zm) ..))) AA]
PMulti(i) (Zz,,..,, (mm) EA) -P(N= =
120
Σ PPO(A)
(Z,,..., 7m) E A ETH
m
Z: =) P(N- 5)
-i===
J20
Σ PPO()) (Z,, Zm) E A and
Σm Zi Zi=1)
1
J20
FPo()) ((Z,,..,, Zm) E A).
47

---

Published as a conference paper at ICLR 2026
Proof of Lemma F.24. Take any integers 21.-.., 2m such that + ............ 2m n 1. Let us calculate the probability mass. Applying the law of total probability,
P
71 = 21, Zm km
m
Σ
P (Zz + 1 (j=1) 21. .. + (j=m) 2m 1j= P(i i)
PIZ 2 1, 2r (vr xi) P(j = i) (::j 1 (Z1, 2m))
n!! 22
PJ
Pin
Pi
Am
Pi
1=1
n!
m
Pi
Pm
2/
21 ... 2m
(n + 1)!
Pin-
21! ... Zm!
Since the choice of 21, .1. 2m arbitrary (given their fixed sum), proves that (Ż,,... Zm) follows the distribution Multinomial(n + " PPm), as desired.
Proof of Lemma F.25. We only consider the non-decreasing property since the proof of the non- increasing case can be done symmetrically. Then, by induction, it suffices to prove
[Mulii(()) ((2),-.,,44 2m) E A) S (xtult((+1) ((2), Zm) E A).
(18)
Fix any n 2 and consider (Z1, ,Zm) Multinomial(n; ... Pm)) Then, by a property of multinomial random variables (Lemma F.24), we have another multinomial vector (Z1. Zm) ~ Multinomial(n + 1;P1,".', ".P.,..',PP .Pm)) by 2, = Zi + [j==j. where j ~ pategorical(pp.......... Ob- serve that
P ( _m)) E A (Z,,..., Zm) E A) =
since Z, S 7 (Vi) and A is a non-decreasing property.
Hence, we can derive the following by applying the law of total probability:
P (Z ..., Zmm) A)
= P (IZ,.... ... 2m) A
(Z.,...,, $ A) IP (((( Zm) $ A)
+ P ( ... 7m) A (.,, Zmm E A) TP ((Z,, . Zm) E A)
2 0 + 1. P ((Z), 2m) E
P ) ((Z), Zm) E A).
This proves Eq. (18), concluding the proof.
Proof of Lemma F226. Let us recall the moment generating function (MGF) of Poisson random variable N ~ Poisson() A) is E[e(N] exp (D(e* - 1)) (Vl E R):
(Xet)²
5.. 120
j! exp exp (Xe") exp (A(e* 1))
j!
120
For the upper tail (Chernoff) bound, we use = n - and apply Markov inequality on NN; for any n > & > 0 and f. > 0,
P(N 2 n) IP (e ) < E N e- tn exp ((n - =)(E" -1) 33-tm tt).
48

---

Published as a conference paper at ICLR 2026
Since t is arbitrary, take the infimum of both sides over t > 0, obtaining
P(N n) S inf exp ((n e)(e - -1) tm)
120
nn In 1 - = ))
exp
E2
v² if 0)
S exp
(: In(1- S
2n
2
This proves Eq. (Upper Tail Bound). On the other hand, for the lower tail (Chernoff) bound, we use e-tN;
and apply Markov inequality e -NN; for any 0, 0, and / 0,
P(N S n) IP (e IN 2 m) <
E |e ] e I exp ((n + s)(e 1) + tm)
Similarly before, taking the infimum over t 0, P(N < n) Σ inf exp ((n + E)(e 1) + tm)
t>0
E
- m
exp
n
In
1
8²
u² u
S
exp
(: In + u)
if 0)
2n
6n
Observe that, 0 < E < en for some E (0,3),
22
8²
(3 c) c)-c)
c
2n
6n
2n
6n
6n
This proves Eq. (Lower Tail Bound).
F.3.2 BINOMIAL. RANDOM INTERSECTION GRAPHS
Let us explain the random k-intersection graph (Singer, 1995; Karoński al., 1999; Godehardt Jaworski, 2003). Consider a set V of vertices and another set W items. Each vertex E V is randomly assigned a subset of items W, C W. Then, a pair of vertices u and are adjacent (i.e., connected with edge) in random k-intersection graph if and only if at least k items are shared between and v, i.e. W. a n W.W 2 k. We remark that is a universal constant throughout our paper.
One of the most well-studied models of random intersection graphs is binomial random k-intersection V and m [W|. In the (()) (n, m. m. model, for every vertex v E V. each item w E W is assigned to v independently with the same probability p E (0, 1). That is, the indicator variables 1 w ussigned to w) are i.i.d. Bernoulli random variables with the same parameter p, for all vertices v E V and items w E W. The word binomial is attached to the name because the number of items assigned to each vertex is random variable following Bin(m,,) p).
graphs (kk) (n, m. p). with
We are particularly interested in the (k) (n, m. p) model because of the following observation.
Lemma F.13 (Evidence Graphs are Binomial k-Intersection Graphs under Poissonization, 4). Let any b E Bp. Consider a vector (wxx associated with a dataset D (i.e., an input sequence x is sampled 7oo times in D). Let PPo()) be probability measure for 7 itd Poisson (A/1%)). Then, under Fro(x), the b-evidence graph G. (D,R) (Def. F.5) is an instance binomial random k- k-intersection
graph (R) (n6, m, p) with parameters
A X
nh = [V6, = =|,,,, p= exp
Proof of Lemma F.13. Recall that the vertex set of c (Dk)) is V. {x12 X12 (112) = c
X12- Also, consider := X3 as the set of all 'items.' Define a set items assigned to each vertex
I12 E Vi as
W {x3 E W (I12, x2) E D} {xa E W (m1a.za) > 1}
49

---

Published as a conference paper at ICLR 2026
Observe that all vertex-item assignments are i..d. Bernoulli random variables with the same probabil- ity parameter p. for any 12 Vo and I3 E X3,
= Po(A) (2 (m12wes) 2 1) = PO(A)) (112 = 0) exp
X
In addition, observe that the set S(1 D) defined in Eq. (5) is identical to the intersection Wa1 n Wais- Hence, by the definition of the edge set Fbg (Dk)) in Eq. (4), two distinct vertices 212 and 22 are adjacent and only if [We12 O Waip 2 k. In summary, every b-evidence graph 9/ (P.A) is a binomial random k-intersection graph G(k) m. with parameters ni [V6,, m [2a], and p = exp(-A/
Note that n, m. and p not necessarily independent of each other; the parameters m2 and p Pn.m often regarded as functions of Indeed, it is often studied the literature on random graphs that a sufficient condition for the parameters (in terms of n + oc) to guarantee certain graph properties, at least asymptotically.
Here, review few of the seminal results on the connectivity (as well as the disappearance of isolated vertices) of binomial random k-intersection graphs (Singer, 1995; Zhao al., 2014; 2017; Rybarczyk, 2011; 2017)." The proof's are involved; thus, we omit them.
Lemma E.14 (Zhao et al., 2014, Theorem 2; Zhao et al., 2017, Theorem I & Remark 1). Fix any 2 1. Suppose that
min n (Inn) .ne))
if 1, for any p > if 2 2,
Ω (n).
and
hd p ( aa)) a
V m
for any sequence }an} which attains a limit Okgo E [-000 +00| as n + cc. Then,
lim IP (g( m. p) is connected) lim P [min (()) (n, m. 2 21) exp exp(-ee (-e-ax).
where compute cxp (-00)- 0 and exp (-c-(+20) =1 1.
Lemma F.15 (Singer, 1995, Propositions 3.1-2, Theorem 3.3). Let k: 1. Suppose that nP for
p 0 and
In On m
for p S 1;
p
In On
for p 1,
mn
for any sequence {an} which attains limit Oioo E (000, +00) as x.. Then,
[, if a -0;;
lim P(g())(n, m. p) is connected) = lim IP (min dog (1)) (n, m, p) 21) = - a = +00.
40000
n=000
CCveat: in the literature of (random) graph theory, the letter '/' is often used for k-connectivity (i.e., being connected after removing less than & vertices/edges). On the other hand, they study 'random s-intersection graphs, using s-instead of this paper-as the intersection constraint parameter.
50

---

Published as a conference paper at ICLR 2026
G ADDITIONAL RESULTS FOR POWER-LAW SCALING ANALYSIS
G.1 MEASUREMENT PROTOCOL FOR Nreq
To empirically determine the minimum dataset size required for reliable compositional generalization (Nreq), we develop measurement protocol that accounts for practical computational constraints while ensuring robustness. For each token set size | 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 the "reliable generalization" on ID is defined 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. Baaining-to-genraliiee 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.
delay: Larger datasets naturally require more iterations to fit
2. Epoch-based measurement: Using epochs rather than raw training steps ensures that the model 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 reasonable upper bound (100 epochs post-training convergence) to reflect practical limitations.
4. Measurement precision:
For each identified Nreq. we verified that 75% of this dataset size consistently failed to meet our generalization criterion. This establishes that our measurement error is most 10g(0.75) = 0.125 in log scale, providing confidence the derived power-law exponents.
G.2 MEASURED POWER-LAW SCALING EXPONENTS ACROSS TASK STRUCTURES AND MODEL SIZES
Using our measurement protocol, we measure the required dataset size Neeq across three different compositional structures (2-HOP, PARALLEL-2- 2--LL,,--HH, and 3-HOP) and three model scales (68M, 96M, and 1.5B parameters). For each task structure, we vary the token set size |X' from 50 to 200, allowing us to observe the scaling relationship.
Tab. 2 presents the power-law exponents obtained by linear fitting log(I vs. Dog(Nre)) plots, all with R² > 0.99. The consistency of exponents across model sizes suggests that the observed power-law scaling relates 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:
The power-law exponents for different tasks and GPT-2 sizes, obtained by linear fitting lo'( vs. log( (eeg) plots. R² > 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
G.3 ROBUSTNESS TO HYPERPARAMETER VARIATIONS
To verify that the paw scaling relationship we observed is not an artifact of specific hyperparam- eter choices, we conduct ablation studies with modified training configurations. Fig. 16 demonstrates that for the H-HOP task with | = 50. the following changes did not significantly affect the measured Nreq or the derived pawer-law exponent:
1. Learning rate reduction: Halving the learning rate from 8e-4 4e-4;
2. Weight decay reduction: Decreasing weight decay by factor of 10 (from 0.1 0.01);
3. Generalization criteria modification: Requiring test accuracy > 0.95 within 10 epochs after training accuracy 0.95.
51

---

Published as a conference paper at ICLR 2026
5.75
5.50
log(Nwgg
5.25
5.00
2.Hop (c= 2.26)
4.75
2-Hop-lr (c21)21)
2-Hop-wd (c- 2.20)
4.50
Hop criteria (c 2.06)
2.1
log()a()
Figure 16: Robustness of power-law scaling relationship to hyperparameter variations in the 2-HOP task with 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² 0.99 for all linear fitting.
This robustness to hyperparameter variations suggests that the power-law relationship between token size and required dataset size is primarily property of the compositional generalization process, rather than an artifact of specific optimization settings.
52

---

Published as a conference paper at ICLR 2026
H DETAILED ANALYSIS FOR NON-TREE TASK
This section provides additional analyses that support our findings in Sec. 7 regarding the challenges of path ambiguity in the NON-TREE task.
H.1
COVERAGE ANALYSIS
100
Dataset size (N)
Covered
50k
60
25k
15k
10k
20
5k
Figure 17: Coverage analysis for NON-TREE task with |. = 50. The graph shows the percentage of ID test data covered at different & values across various dataset sizes (N). Compared to the 2- H-HOP task (Fig. 3, left), NON-TREE has significantly lower coverage at equivalent dataset sizes, indicating that path ambiguity impedes the formation of functional equívalence relationships.
Fig. 17 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 (Left). This aligns with theoretical analysis in Sec. 7, which predicts that path ambiguity limits the establishment of functional equivalence relationships between input subsequences, cannot generalize across different 22 values the NON-TREE structure even when they produce the same intermediate state b = f1 (x1,
the model
H.2 EFFECT OF MODEL SCALING
1.0
Non-tree
Non-tree-XL
ID accuracy
0.8
0.6
0.4
0.2
0.0
5k
10k
15k
20k 25k 30k 35k 40k 45k 50k Dataset Size(N)
Figure 18: ID test accuracy comparison between GPT-2 (96M parameters) and GPT-2-XL (1.5B parameters) the NON-TREE task with | = 50, measured 100 epochs after training accuracy exceeds 0.99. Despite the 15x increase in parameter count, the accuracy does not increase.
Fig. 18 shows that scaling up the model size GPT-2-XL (1.5B parameters) does 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.
H.3 COMPARISON BETWEEN MAMBA AND GPT-2 ON NON-TREE TASK
Fig. 19 shows that the Mamba model (4 layers, hidden dimension of 256, trained with learning rate of 0,008) shows a similar trend of ID test accuracy on NON-TREE task compared to GPT-2, suggesting that the generalization failure is more likely due to the task structure itself, rather than specific model architecture.
53

---

Published as a conference paper at ICLR 2026
1.0
Mamba
GPT-2
0.8
0.6
ID
0.2
0.0
10k
20k
30k
40k
50k
Dataset Size(N)
Figure 19: ID test accuracy comparison between GPT-2 and Mamba on the NON-TREE task with | 50, measured 100 epochs after training accuracy exceeds 0.99.
H.4 REPRESENTATION ANALYSIS IN SUCCESSFUL GENERALIZATION
For model that eventually achieved near-perfect ID accuracy (0.96) after extended training (36k epochs. | 50, N 50k), we conduct causal tracing analysis to understand how it achieves generalization despite path ambiguity.
IE
1.0
Layer 0.00
-0.03
1.00
0.00
0.00
1.00
-0.00
0.00
1.00
Layer
0.00
-0.03
1.00
0.00
0.00
1.00
-0.00
0.00
1.00
0.8
Layer
40.00
-0.04
1.00
0.00
0.00
1.00
0.00
0.00
1.00
0.6
Layer
0.02
-0.09
0.98
0.00
0.01
0.98
0.00
0.01
0.98
Layer
0.46
.0.44
0.28
0.46
0.05
0.27
0.46
0.05
0.27
Layer 2
0.74
0.24
-0.00
0.74
0.21
0.00
0.74
0.21
0.00
0.2
Layer
0.76
0.25
0..00
0.75
0.21
..00
0.75
0.21
-0.00
0.0
x1
x2
x3
x1
X2
x3
x1
X2
x3
b'
(b, x2')
(b', x2')
Figure 20: 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 fi (2). Middle: same b but different 22. Right: different b and J2.
The causal tracing results in Fig. 20 reveal how the model achieves generalization in the presence of path ambiguity. Across all perturbation strategies, the model's predictions show strong causal both the Fı and I2 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.
dependence on 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 22 value, rather than learning single unified representation of the intermediate state b fi (2). This represents fundamentally different solution strategy compared to the 2-HOP task, with implications for both generalization capability and interpretability.
54

---

Published as a conference paper at ICLR 2026
I DETAILED DISCUSSION ON THE TAXONOMY FOR UNDERSTANDING GENERALIZATION MECHANISMS
In this section, we initiate discussion disambiguate the mixed mechanisms of generalization into isolated testable parts by sketching a preliminary laxonomy that distinguishes three complementary mechanisms of generalization. We note that we do not view our categorization as a complete one.
Type-I: Functional equivalence-ban basedd generalization (pattern matching). This is precisely what we formalized through this work: 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. In other words, it describes the ceiling of pattern matching.
Type-II: Function property-based generalization. This mechanism exploits intrinsic properties of individual primitive functions, e.g., algebraic invariances such as commutativity or input irrelevance, where certain arguments never affect the output (e.g.. f x²2 = f f(11 even when distractor z2 is present (Wen et al., 2025)). Unlike the previous type, this mechanism explains the generalization beyond the coverage by leveraging 'global' properties that hold across all possible inputs of primitive, beyond what is actually observed. We interpret the Reversal Curse phenomenon (Berglund al., 2024) as an example of the layered nature of challenges across multiple generalization lypes. Our framework predicts the failure of pattern matching on this problem, since training on "A is B" provides no functional equivalence evidence for B is A". An architectural modification to learn inverse mappings from the same training data to handle this problem (I.v et al., 2024) can be interpreted utilization of Type-Il generalization to enable generalization beyond coverage.
Type-III: Shared-operator generalization. This mechanism emerges through the reuse of identical primitive functions across computational positions (c.g.. when fi = f2). Recurrent architectures (Hochreiter & Schmidhuber, 1997) exemplify the utilization of this through weight sharing across time steps, enabling processing of variable-length sequences (Graves et al., 2014). Likewise, it has been reported in Transformers with inductive biases towards reuse of the same computation through parameter sharing (Dehghani et al., 2019: Csordás al., 2021; Wang et al., 2024a) can improve generalization on complex compositional tasks where the same primitive function can be reused in various contexts. With a similar insight, the generalization capability of Transformers in terms of sequence length (i.e., length generalization) and its limitation has recently been studied a lot, especially in terms of arithmetic/algorihmii tasks (Anil al., 2022; Zhou et al., 2024a; Shen et al., 2023; Zhou et al., 2024b; Cho et al., 2024; 2025). We interpret this mechanism as exploiting structural repetition.
Distinguishing mechanisms from phenomena. Compared to prior categorizations of generaliza- tion, which focus observed phenomena (Lake & Baroni, 2018; Hupkes et al., 2020), we categorize the underlying mechanisms. As noted in Sec. many behavioral 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 (and possibly more). While preliminary, we believe this taxonomy guides future research design on constructive characterization of neural networks' generalization behaviors on discrete sequence tasks. In this broader context, this work can be understood formalization of pattern-matching generalization clarify its specific boundaries. When models suc- ceed beyond our coverage predictions, we view these as exploiting other generalization mechanisms, ie., beyond pattern matching. Our focused study suggests that challenges to reliable generalization remain as long as models rely primarily on pattern matching, requiring methodological innovations that harness taxonomy serves as research program towards our better understanding of generalization, and confirming or refuting its utility an empirical matter that we invite the community to explore.
characterization and
pattern-matchin mechanisms, e.g., variable binding. We hope this preliminary
55


Reviews:
[{"review_id": "z3Q66OWhLd", "reviewer": "Reviewer_5m5w", "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.", "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?\n\n2. Is there any equivalent empirical observation where compositional generalization requires robust observation of functional equivalence in a real-world NLP dataset?\n\n3. Would the formulation in the paper generalize to stochastic functions and approximate functional equivalence?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper studies an important problem of the compositional generalization of language models.\n\n2. The experiments include various settings of practical relevance.", "weaknesses": "1. The results are limited to small synthetic task structures.\n\n2. The settings require a deterministic function and strict functional equivalence, which may be too restrictive in a real-world NLP dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cuZ1aKSoCE", "reviewer": "Reviewer_ntJX", "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. \n\nThey 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:\n\n- 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).\n- 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.\n- 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.\n- 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.\n- 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.", "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)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "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.\n- 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).", "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.\n- 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.\n- 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.\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZD5WRQYcc1", "reviewer": "Reviewer_cspU", "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.", "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.\n\nWhat 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 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.\n\nThe large sweep over a variety of dataset sizes is also helpful for determining the role of data access.", "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.\n\n\"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.”\n\n“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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NzWMw6BHHv", "reviewer": "Reviewer_ZpTF", "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.", "questions": "- For clarification, how is k computed if there is functional equivalence between more than two subsequences?\n- 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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This work makes a significant contribution in providing a formalization to the boundary of pattern matching and compositional generalization.\n- 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.\n- The results make several interesting implications for the capabilities of larger models.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)