acceptodds
Under review as a conference paper at ICLR 2027

Decomposing Decomposition: When and How Do Models Learn Combinatorial Structure?

Abstract

There is now abundant evidence that neural networks learn to decompose solutions to large problems by learning smaller subroutines for subproblems, which can often be reused and recombined, sometimes even facilitating helpful forms of compositional generalization. Comparatively little is known, however, about what drives this decomposition, and where we should expect to find it. The present work confronts this question by studying the dynamics of learning various *combinators*, that is, higher-order functions that determine how simpler functions combine. We first study which combinators can be learned by Transformer-based language models across model sizes and data configurations. We then find that the model's generalization accuracy on novel combinations is strongly correlated with its successful realization of the task's intermediate causal variables. We explain how the model identifies and learns these intermediate variables by tracing the gradients of training examples that share the same intermediate value yet have different downstream functions. We find that these gradients drive the clustering of the intermediate variable representations, and such clustering leads to both the emergence of the causal variables identified by prior interpretability research and the model's compositional generalization capacity.

Primary area:
interpretability and explainable AI
Keywords:
compositional generalization, mechanistic interpretability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_4FxDOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors model reasoning as a method to decompose a complex problem into many simpler subroutines. They argue that, in order for an LLM to execute effective reasoning, it needs to have learned (i) how to solve the simpler subroutines and (ii) combinators, i.e., functions that tell the model how to combine subroutines towards a larger goal. The authors study how well a LLM can learn these combinator functions.

The authors train small 1-2 layer transformers which take as input (i) a set of values from the input alphabet and (ii) the functions being applied to these inputs, and it outputs the result of composing these functions on the inputs in a particular way. The composition being tested is the combinator, and each transformer is trained on one combinator. The models can successfully learn most combinators but not all. The authors do not test, as far as I could tell, how increasing training data or model depth affects which combinators the model can learn.

A natural follow-up question is whether or not the transformers are computing the combinators by composing the underlying functions and computing the intermediate results inside the composition. The authors use interchange interventions to show that the transformers are indeed representing intermediate variables in its internal activations. The authors ask how the transformers learn to represent the intermediate variables despite having never seen them in the training data. They study this question for two simple combinators and show that samples with the same intermediate value aggregate their learning signals.

Critical strengths

The authors show good command of some of the surrounding literature.

The authors use simple and well-motivated functions (combinators) to represent compositional structure in reasoning. I think it is interesting to study what kinds of combinators a transformer can implement for a toy model.

The authors produce many results. The result about how the LLM learns to represent intermediate variables because of how it aggregates learning signals is interesting. I would have liked to see this result explored in mode depth and centered in the paper.

Critical weaknesses

The paper organization makes it difficult to read, where the readers are shown one result after another. While it does have a central theme (studying combinators), it could benefit from a more structured narrative. The introduction should contain a comprehensive summary of the results.

The toy experiment with the combinators does not capture many aspects of compositional generalization. For example, how emitting intermediate reasoning tokens allow transformers to compose functions, or how Transformers execute a long sequence of compositions instead of simple combinators.

The authors do not explain why the transformer learns some combinators and not others. They only use shallow transformers and show that these small models cannot learn certain combinators. The authors could also study deeper models with more data and test to what extent their observations hold.

The authors use the term “recombination accuracy” repeatedly but never define it. Likewise, there are other terms that are not defined before usage in the text or left to the references.

It is not fully clear how much their analysis on different combinators can be used to better understand LLM performance on real-world tasks.

The authors claim the non-linear representation of an intermediate variable is a counter-example of the linear representation hypothesis. The linear representation hypothesis only applies to very high-dimensional models. The authors only study small models.

Questions for authors

What scientific insight do we gain from studying combinators that is relevant to real-world settings? It is generally accepted that LLMs combine sub-tasks to solve a larger task. They usually do this using their chain-of-thought. We also know that deep neural networks can compose functions, e.g., convolutional neural networks will extract the edges from an image before identifying its class. What additional insight do you hope to gain from studying these simple combinator examples and how will it help us build better models?

How much are each kind of combinator represented in realistic tasks? And do LLMs struggle to execute some combinators over others in practice?

Why is the model able to represent some combinators and not others? Is there a way to explain why using the theory about the learning signals?

5 comments

We thank the reviewer for the insightful comments and for highlighting the value of studying combinators and learning-signal aggregation. We were particularly motivated by your remark:

"The result about how the LLM learns to represent intermediate variables because of how it aggregates learning signals is interesting. I would have liked to see this result explored in more depth and centered in the paper."

Following your suggestion, we restructured the manuscript to center our theory (§3.2, §4, and a new §5), using it to explain both when models generalize across datasets and why some combinators are harder to learn than others, and we added new experiments scaling model size up to 1.1B parameters (16 layers; Appendix C.9).



Q1. Real-world relevance, Chain-of-Thought, and building better models

We appreciate you raising these foundational questions. We also appreciate the opportunity to clarify our motivation. We have expanded the opening of §2 to explicitly discuss how our combinator setup connects to Chain-of-Thought (CoT) and real-world language model capabilities. Below, we summarize the key points of this discussion:

Q1.1 Why study latent intermediate variables alongside Chain-of-Thought?

W2 / Q1: "The toy experiment with the combinators does not capture many aspects of compositional generalization. For example, how emitting intermediate reasoning tokens allow transformers to compose functions... What additional insight do you hope to gain from studying these simple combinator examples?"

We agree that in some instances—such as explicit CoT or multi-hop pretraining texts—models explicitly observe or emit the relevant intermediate values as tokens (e.g., a model will be exposed to texts explaining that Stonehenge is located in England, and that London is England’s capital). This can make the learning problem easier (cf., e.g., Yao et al. 2025), and in fact some methods in interpretability presuppose that relevant intermediate values can be identified with tokens (e.g., Gurnee et al. 2026).

However, many intermediate variables remain latent in the available data and are never verbalized as tokens. For example, to process natural language—even within a single forward pass or a single step of CoT—a model must somehow group strings into “constituents” and perhaps also label items with suitable grammatical categories (e.g., parts of speech), or performing implicit multi-hop reasoning (e.g., answering "What is the capital of the country where Stonehenge is located?" without emitting "England" first; Biran et al., 2024; Wang et al., 2024; Ye et al., 2026). Because these latent variables pose a formidable learning challenge compared to explicitly supervised steps, we focus our attention on this latent setting—our goal is to understand what properties of the training data push a model to induce an internal variable rather than, e.g., memorizing individual examples.

Q1.2 How do our combinators connect to realistic tasks and real neural circuits?

W5 / Q2: "It is not fully clear how much their analysis on different combinators can be used to better understand LLM performance on real-world tasks..."

As we highlight in §2, combinators are widely assumed to ground core linguistic capacities such as syntactic parsing (Steedman, 2000) and semantic evaluation (Donatelli & Koller, 2023), and many of the exact combinators we study are explicitly attested in reasoning patterns for even very simple neural models:

  • B=g(f(x))\mathsf{B} = g(f(x)) is the canonical structure of 2-hop implicit reasoning ((entity 1, relation 1, relation 2) -> entity 3) studied across the LLM literature (§1, Appendix A Related Work).
  • C7(1=,1=)=g(f(x,y),f(v,u))\mathsf{C}_7(\mathbf{1}_{=}, \mathbf{1}_{=}) = g(f(x,y), f(v,u)) is the exact "hierarchical equality" circuit analyzed in interpretability and cognitive science (Geiger et al., 2024).
  • C4(1≤,∧)=g(f(x,y),f(v,y))\mathsf{C}_4(\mathbf{1}_{\le}, \wedge) = g(f(x,y), f(v,y)) is the "price-tag" comparison algorithm localized in LLaMA/Alpaca by Wu et al. (2023), where two branches compare different items against a shared reference bound yy.

But we agree with the reviewer that more work needs to go into connecting these structures with even more real-world tasks. We have acknowledged this at several points in the revised version (e.g., end of the introduction and in future work in the conclusion).

Q1.3 Why use a synthetic setup, and how does this help us build better models?

Q1: "...What additional insight do you hope to gain from studying these simple combinator examples and how will it help us build better models?"

  • Why a controlled synthetic setup helps: In pre-trained LLMs, we often do not have access to the training data, and even when we do, it is difficult to identify and control all training sequences that share the same underlying task structure. Studying combinators in a controlled synthetic setting allows us to systematically vary the training distribution and isolate the exact learning pressures that drive decomposition, and these combinators represent fundamental compositional structures in real tasks.
  • How our findings potentially help build better models: Our study shows that the training data distribution is crucial for compositional generalization. By characterizing which data properties are needed—and which are often lacking under uniform sampling—our analysis can help guide the intentional design of data mixtures that allow models to generalize compositionally from fewer examples (e.g., collecting training data and defining training objectives that favor such compositional structures), as well as data curricula (see task transfer results in Appendix C.11).

Q2. Explaining why some combinators are harder to learn & scaling to larger models

Q2.1 Testing deeper models (up to 1.1B parameters) and more favorable data distribution on C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7

W3: "The authors do not explain why the transformer learns some combinators and not others. They only use shallow transformers and show that these small models cannot learn certain combinators. The authors could also study deeper models with more data and test to what extent their observations hold."

Thank you for this suggestion! In our original investigation, 2-layer models failed on C4\mathsf{C}_4 and C5\mathsf{C}_5 under our data grid, raising the natural question of whether learning these combinators requires (a) a more favorable data distribution or (b) deeper/larger models.

Thanks to this suggestion, we explicitly tested both hypotheses and report the results in the revised manuscript. We found that:

  • With a more favorable data distribution, even 2-layer models can learn C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7: In our original submission, we coupled the generation parameters (∣F∣=∣O∣|\mathcal{F}| = |\mathcal{O}| and ∣X∣=∣V∣=∣Y∣|\mathcal{X}| = |\mathcal{V}| = |\mathcal{Y}|), under which datasets with sufficiently rich signals for C4\mathsf{C}_4 and C5\mathsf{C}_5 were rarely sampled. In the revised manuscript, we use a more flexible data generation setup (§2.1, Appendix B.2) that varies ∣F∣,∣O∣,∣X∣,∣V∣,|\mathcal{F}|, |\mathcal{O}|, |\mathcal{X}|, |\mathcal{V}|, and ∣Y∣|\mathcal{Y}| independently. This allows us to explore a wider range of data distributions—in particular, datasets where calls share many more contexts and fewer intermediate values map to the same answer—under which 2-layer Transformers achieve near-100% recombination accuracy on C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7 (Appendix C.1, Figure 6).
  • Scaling model size alone does not overcome weak data signals: Conversely, to test whether deeper models can learn C4,C5\mathsf{C}_4, \mathsf{C}_5 (or B,C3\mathsf{B}, \mathsf{C}_3) on the datasets where 2-layer models fail, we trained an OLMo-2 1B model (16 layers, hidden width 2,048, 16 heads; 1.1B parameters) across 32 representative datasets (Appendix C.9, Figure 18). While the 1.1B model sometimes improves generalization on borderline datasets right at the transition boundary, it consistently fails (0.3%–5.2%0.3\%\text{--}5.2\% recombination accuracy) across all low-context or high-∣V∣/∣Y∣|\mathcal{V}|/|\mathcal{Y}| datasets where the 2-layer model fails.

Together, these results show that the bottleneck on C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7 is not model capacity, but rather the training data distribution.

Q2.2 Using our theory to explain why C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7 are harder to learn

W3 / Q3: "Why is the model able to represent some combinators and not others? Is there a way to explain why using the theory about the learning signals?"

Even under this expanded setup, C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7 require a more favorable data distribution (e.g., calls needs to share more contexts) to generalize, compared with C3\mathsf{C}_3. In the revised manuscript, we added §5.2 and Appendix D.2 to show how our learning-signal theory explains this difference. The core intuition is as follows:

  • Disjoint branches (B\mathsf{B} and C3\mathsf{C}_3): By Observation 1 (§3.2), two calls with the same intermediate value receive aligned gradients only when they appear in a shared context that gives them the same target answer. In B\mathsf{B} and C3\mathsf{C}_3, the branches use disjoint tokens, so any shared surrounding context (e.g., h g v u in C3\mathsf{C}_3) evaluates the second branch g(v,u)g(v,u) to the same value and guarantees the same answer.
  • (C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7) share arguments between constituents: In C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7, however, the two branches share function or argument tokens—such as yy in C6=h(f(x,y),g(v,y))\mathsf{C}_6 = h(f(x,y), g(v,y)) or (x,y)(x,y) in C5=h(f(x,y),g(x,y))\mathsf{C}_5 = h(f(x,y), g(x,y)). If two same-value calls differ in their shared arguments (e.g., y≠y′y \neq y'), pairing them with the exact same surrounding tokens (h g v) evaluates the second branch at two different inputs, g(v,y)g(v,y) vs. g(v,y′)g(v,y'), which usually produce different target answers and conflicting gradients.
  • Why a more favorable data distribution is needed for models to learn C4–C7\mathsf{C}_4\text{--}\mathsf{C}_7: Coherent gradient alignment comes primarily from same-value call pairs that also share arguments between constituents, which are rare under uniform sampling. Beyond this analytical argument, we also verify this empirically across 2,093 datasets in Appendix D.2 (Table 5 and Figure 21), showing that the average number of such pairs per training example cleanly separates datasets where the model generalizes from those where it fails (AUC-ROC 0.82–0.89).
Reviewer_NPk7OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The submission studies the mechanisms that allow small toy transformers to compositionally generalize on a family of function composition tasks (like h(f(x,y),g(v,u))h(f (x, y), g(v, u))). It finds that, given sufficient data diversity, transformers can generalize to unseen combinations of atomic functions. It proceeds to study how networks calculate intermediate values (like f(x,y)f(x,y)) and analyses what learning signals promote the representation of intermediate values.

Critical strengths
  • The submission is well written and structured. I found the experiments and analyses to be well-motivated and generally easy to follow (except for a few parts, see questions below).
  • The mechanistic analysis to identify the internal circuitry that implements the function composition is well executed
Critical weaknesses
  • Theorem 1, one of the central theoretical results, is missing a formal proof
  • The findings are not very well contextualized with respect to prior work
Questions for authors

Despite the abundance of evidence that neural learning models do decompose problems—often in predictable ways following the “true” decomposition of the generating process—comparatively less is known about precisely when, why, and how this emerges during training.

  1. There is plenty of prior work that at least attempts to adress this question that should be cited more carefully (like for example [1,2, ...])

Compared to previous work, the present analysis goes deeper into the mechanisms and training dynamics behind decomposition. But it also goes wider by putting the combinatorial structure itself into the spotlight.

  1. This is a strong claim but it is missing the necessary evidence/citations.

We observe a strong correlation between interchange intervention accuracy (IIA) and models’ recombination accuracy

  1. How does this finding relate to findings by prior work that linear decodability of task constituents correlates with successful composition (e.g. [3, ...])?

Given a Transformer with H attention heads, f(x) is encoded in an h-dimensional code, h ≤ H, with one af,x from each attention head.

  1. This type of mechanism has been identified before in [4], it might be nice to compare to it

  2. In Figure 1C, how do you explain that g(v,u) is only represented after the model has already achieved perfect recombination accuracy? The plot's x-axis is on a log-scale, so the gap might even be larger than it visually appears.

  3. Can you please provide a formal proof of Theorem 1? I know you provide the rough argument but for a theoretical result this is not enough. This is the main point preventing me from recommending this paper for acceptance.

[1] Compositional Generalization from First Principles, Wiedemer et al., NeurIPS, 2023.

[2] Discovering modular solutions that generalize compositionally, Schug et al., ICLR, 2024.

[3] Scaling can lead to compositional generalization, Redhardt et al., NeurIPS, 2025.

[4] Attention as a Hypernetwork, Schug et al., ICLR, 2025.

Minor remarks

  • The paper assumes familarity with distributed alignment search and interchange intervention accuracy in the main text, not providing any explanation what they are. I am not sure if these methods are sufficiently established to do that for a general machine learning audience. It might be worthwhile to briefly motivate/explain what they do.

  • Figure 1A shows only a small part of the results mentioned in Section 2.1. Figure 9 in the appendix contains the full results but is extremely dense and hard to parse. A plot to backs the main claims of the main text would be nice

  • Throughout section 3.1.1 I was wondering where the supporting evidence for the claims made therein is. Eventually this is clarified (it is in Appendix C) but I think this comes too late and some of it should be explained in the main text

We then move on to study the more complex C3 , which seems to require encoding two intermediate variables

  • I am confused by the "seems" in this statement, is there -- theoretically speaking -- an alternative of implementing C3?

For x ∈ X , the answer is g(f (x)) [...]

  • I couldn't parse this sentence, the answer to what?

Intuitively, aggregating over f, x “compresses” the input space into a small label space, with multiple examples explained by the same “compression.”

  • Even with the quotation marks I cannot parse this sentence. What does it mean for multiple examples to be explained by the same compression?
5 comments

We are grateful to the reviewer for the thoughtful feedback and for appreciating our experimental design and mechanistic analysis!

We also appreciate your pointers to related work on compositional generalization and mechanism—below, we clarify our theoretical argument, discuss how our findings connect to these works, and summarize the corresponding revisions in the manuscript.



Q1. Clarifying Theorem 1

W1 / Q6: "Theorem 1, one of the central theoretical results, is missing a formal proof... This is the main point preventing me from recommending this paper for acceptance."

We very much appreciate the reviewer pushing us on this. We agree that putting our original statement in a Theorem environment without a proof sets a different expectation. We have removed the Lemma and Theorem environments and put the relevant statement in an Observation environment (Observation 1 in §3.2).

Since we are really interested in earlier layers of the model anyway, and the math appears to be much more complicated there (given the further sequence of non-linear functions applied after them), we are relying here on a plausibility argument rather than a direct proof. So instead of proving that the learning signal works the way we hypothesize, we show consistency with the assumption empirically.

We also used this as an opportunity to refine and clarify the development of ideas in those sections. In particular, we expanded the probabilistic calculation into a dedicated section §4. We also added a new §5 showing how our mechanistic and probabilistic argument helps explain the empirical results we have observed at the beginning.

We hope that the main points are now readily apparent, and we thank the reviewer for prompting us in this direction!


Q2. Better contextualizing our findings

W2 / Q1–Q4: "The findings are not very well contextualized with respect to prior work... [1] Wiedemer et al., 2023; [2] Schug et al., 2024; [3] Redhardt et al., 2025; [4] Schug et al., 2025."

We are grateful for the pointers to these relevant papers! We have added citations in §1 and §3.1 of the revised PDF and discuss how our findings connect to each of your questions below.

Q1: "Comparatively less is known about precisely when, why, and how this emerges during training... There is plenty of prior work that at least attempts to address this question that should be cited more carefully ([1]; [2]...)"

Thank you for the suggestion! We have added citations to acknowledge prior work on compositional generalization and modular learning. While works like [1, 2] nicely study the architectural and theoretical conditions for composition (such as when architectures are structured to match the compositional form or use hypernetworks to discover modular primitives), our work complements this line of research by asking when standard, unconstrained Transformers induce latent intermediate variables from data symmetries during training.

Q2: "Compared to previous work, the present analysis goes deeper... it also goes wider... This is a strong claim but it is missing the necessary evidence/citations."

We appreciate the feedback and have softened the phrasing of this sentence in §1.

Our intention here is to highlight how our setup complements prior work on implicit reasoning (e.g., Biran et al., 2024; Wang et al., 2024; Yao et al., 2025; Ye et al., 2026): whereas prior studies typically focus on standard 2-hop composition (corresponding to combinator B\mathsf{B}), we systematically compare a broader family of combinators to explain why some compositional structures are much harder to learn than others (§5.2) and how atomic functions transfer across combinators (Appendix C.11).

Q3: "We observe a strong correlation between interchange intervention accuracy (IIA) and models' recombination accuracy. How does this finding relate to findings by prior work that linear decodability of task constituents correlates with successful composition (e.g. [3] Redhardt et al., 2025, ...)?"

We thank the reviewer for noting this interesting connection. Our observation is in some sense a more general phenomenon, as the metric we choose, i.e., Interchange Intervention Accuracy, tests causal mediation directly and does not assume any particular feature geometry. In cases where a feature is linearly represented, which is common in LLMs, linear decodability often correlates well with higher IIA.

Q4: "Given a Transformer with H attention heads, f(x) is encoded in an h-dimensional code, h ≤ H, with one a_{f,x} from each attention head. This type of mechanism has been identified before in [4] (Schug et al., 2025), it might be nice to compare to it."

Thank you for pointing out this parallel—we have added a note in §3.1 that the hh-dimensional attention-weight code we found mirrors the across-head latent code unearthed in Schug et al. (2025) [4].

Q3. Presentation and specific clarifications

Q5: "In Figure 1C, how do you explain that g(v,u) is only represented after the model has already achieved perfect recombination accuracy? The plot's x-axis is on a log-scale, so the gap might even be larger than it visually appears."

Looking across the full set of models and data configurations in Appendix E.4.2 (Figures 27–28), we find that the model actually learns to represent the two intermediate variables at roughly the same time; the slight lag in the single run shown in Figure 1C may reflect run-to-run variation rather than a systematic pattern.

Following your observation about the x-axis, we have also updated Figure 1C (and all trajectory plots in Appendix E.4.2) to use a linear epoch scale.

Minor remark 1: "The paper assumes familiarity with distributed alignment search and interchange intervention accuracy in the main text, not providing any explanation what they are... It might be worthwhile to briefly motivate/explain what they do."

We agree and have added a dedicated paragraph in §2.2 ("Causally localizing intermediate variables") that motivates and explains causal abstraction, interchange interventions (also known as activation patching), DAS, and IIA in the main text, with full mathematical and training details in Appendix B.4.

Minor remark 2: "Figure 1A shows only a small part of the results mentioned in Section 2.1. Figure 9 in the appendix contains the full results but is extremely dense and hard to parse. A plot to back the main claims of the main text would be nice."

Following your suggestion, we added Figure 4 in the main text (§5.1) to directly back our main claims on how shared contexts and ∣V∣/∣Y∣|\mathcal{V}|/|\mathcal{Y}| govern generalization on B\mathsf{B} and C3\mathsf{C}_3 (and many more combinators, as shown in Appendix C.3-C.4).

We also replaced the dense table/heatmap in the appendix with a much cleaner all combinator summary heatmap (Figure 6 in Appendix C.1), supplemented by stratified threshold plots (Figures 7–8) and regression analyses (Figures 9–11).

Minor remark 3: "Throughout section 3.1.1 I was wondering where the supporting evidence for the claims made therein is. Eventually this is clarified (it is in Appendix C) but I think this comes too late and some of it should be explained in the main text."

To make the supporting evidence clearer in the main text, we expanded the caption of Figure 2(c)–(d), which serves as the primary empirical evidence for the representational claims in §3.1, to more clearly explain the feature geometry and quantitative linear separation results. We also added upfront pointers to the detailed localization results in Appendix E in the relevant paragraphs.

Minor remark 4: "We then move on to study the more complex C3, which seems to require encoding two intermediate variables. I am confused by the 'seems' in this statement, is there -- theoretically speaking -- an alternative of implementing C3?"

We removed this phrasing in §3. Full recombination across novel function pairs indeed requires computing both intermediate variables f(x,y)f(x,y) and g(v,u)g(v,u).

Minor remark 5: "For x ∈ X, the answer is g(f(x)) [...] I couldn't parse this sentence, the answer to what?"

Thanks for catching this. We rewrote this in §2.1 to explicitly describe the prompt and target.

Minor remark 6: "Intuitively, aggregating over f, x 'compresses' the input space into a small label space, with multiple examples explained by the same 'compression.' Even with the quotation marks I cannot parse this sentence."

We agree that the "compression" metaphor obscured the argument, and we replaced it in §3.2 with an explicit contrast between ways of grouping the training examples: grouping by the inner call (f,x)(f,x) and aggregating over gg collapses the ∣F∣∣X∣|\mathcal{F}||\mathcal{X}| distinct calls into at most ∣V∣|\mathcal{V}| distinct label histograms (one per intermediate value v∈Vv \in \mathcal{V}), whereas grouping by (g,x)(g,x) or (f,g)(f,g) lacks this structural sharing and produces nearly as many distinct label histograms as there are pairs.



Thank you again for your detailed feedback and encouragement, and we would be happy to respond to any further questions or suggestions!

Thank you for your clear and comprehensive response. I appreciate the effort you put into improving the manuscript.

We agree that putting our original statement in a Theorem environment without a proof sets a different expectation. We have removed the Lemma and Theorem environments and put the relevant statement in an Observation environment

As I stated in my original review, the lack of a formal proof of Theorem 1 was the main point preventing me from recommending this paper for acceptance. My positive impression of the paper was in large part supported by the (seeming) existence of a provable identifiability result in this toy setting.

While I still believe the findings are promising, in the absence of a theoretical proof (or, e.g., replication of the discovered mechanisms in a realistic setting) the generality of the results are not clear to me. Before giving my recommendation, I would appreciate your response to this point.

we find that the model actually learns to represent the two intermediate variables at roughly the same time; the slight lag in the single run shown in Figure 1C may reflect run-to-run variation rather than a systematic pattern.

Do you have an explantion of how, within a specific run, it is possible for a model to achieve perfect recombination accuracy without representing g(v,u)?

Reviewer_zmH3OpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates how models learn to compute over functional compositions and whether they end up representing intermediate variables in their hidden representations. The authors find that high interchange intervention accuracy (operationalizing whether intermediate variables are represented) is strongly correlated with high generalization performance, and provide a sketch of an argument for how the models could pick up on such intermediate variables (despite the fact that they are neither contained in the input nor output).

Critical strengths
  • The authors do a great job motivating the problem studied in this paper (I particularly liked the framing in the introduction) and I think the synthetic datasets considered here are a really good perspective on implicit reasoning tasks.
  • I really liked the theoretical basis provided by the authors for how the model could possibly pick up on intermediate variables. I think this is a really useful concept, I thought the evidence provided was convincing, and it is a really good example of why this synthetic dataset is useful.
Critical weaknesses
  • My primary issue is with clarity. The paper, especially in the main text, is extremely vague on some of the details, e.g., it provides very little information about how the task data is actually presented to the model and how DAS is implemented. The appendix contains most of the important information, but the fact that the reader needs to look up even fairly basic information like "what is the input-output structure on which the model is trained?" (especially given that the authors do not consistently reference the relevant parts of the appendix) disrupts reading flow significantly. I am highlighting other parts of the paper that I found unclear, hopefully this will be helpful for illustrating the difficulties I had in following the presentation:
    • What is shown in Fig. 2c? The caption is not very helpful and I had a hard time understanding the relevant paragraph (last paragraph of section 3.1.1): what does it mean for f(x)f(x) to be encoded in an hh-dimensional code? What is ll? How does the bilinear interaction implement this functional mapping?
    • How do you vary the number of intermediate values in Fig. 1a? Note that you are also labeling the x axis of this plot as "contexts" in the panel, but then refer to it as "outer functions" in the figure captions (which is also more consistent with how you refer to it in the text).
    • How many random seeds do you consider? Fig. 1b seems to use three seeds but then a lot of other figures seem to rely on a single seed?
    • It may be useful more broadly to have a dedicated methods section where you describe your setup (and where to find more details on it) in detail.
  • The authors' stated theorem is not a theorem. It is lacking precise language (e.g., what is "sufficiently large" or "high probability" or "uniquely identify") or a proof.
Questions for authors
  • See questions under the lack of clarity point above.
  • To the extent that some of your primary analysis appears to have been conducted on only a single seed, do you expect that there might be significant variation between multiple seeds?
  • Can you please either formalize your theorem or remove the label theorem from it? Either way, it would be useful to get a better sense of what it means to "uniquely identify the intermediate variable" and how that is related to actually being able to represent it.
3 comments

We sincerely thank the reviewer for the constructive feedback and for appreciating the framing of our introduction! We are particularly encouraged by your comment:

I really liked the theoretical basis provided by the authors for how the model could possibly pick up on intermediate variables.

I think this is a really useful concept, I thought the evidence provided was convincing, and it is a really good example of why this synthetic dataset is useful.

Your specific pointers on where missing definitions and technical details disrupted the reading flow were especially helpful as we revised the manuscript.



Q1. Clarify our theory

W5 / Q2:"The authors' stated theorem is not a theorem. It is lacking precise language... Can you please either formalize your theorem or remove the label theorem from it? Either way, it would be useful to get a better sense of what it means to 'uniquely identify the intermediate variable' and how that is related to actually being able to represent it."

We very much appreciate the reviewer pushing us on this. We agree that putting the statement in a theorem environment was not quite apt. We have two derivations in the main body of the paper, but both are quite elementary. The first pertains to the gradient signal on the logits, the second is a simple probabilistic calculation.

For the first, we removed the Lemma and Theorem environments and put the relevant statement in an Observation environment (Observation 1 in §3.2). Since we are really interested in earlier layers of the model anyway, and the math appears to be much more complicated there (given the further sequence of functions applied after them), we are relying here on a plausibility argument rather than a direct proof. So instead of proving that the learning signal works the way we hypothesize, we show consistency with the assumption empirically.

We also used this as an opportunity to refine and clarify the development of ideas in those sections. In particular, we expanded the probabilistic calculation into a dedicated section §4.

We hope that the main points are now readily apparent, and we thank the reviewer for prompting us in this direction!


Q2. Multiple random seeds and analysis of seed variance

W3 / Q1: "How many random seeds do you consider? Fig. 1b seems to use three seeds but then a lot of other figures seem to rely on a single seed? To the extent that some of your primary analysis appears to have been conducted on only a single seed, do you expect that there might be significant variation between multiple seeds?"

Q2.1 Updating our results across 3 initialization seeds

We updated all primary behavioral and regression results in the paper (including Figure 1A–B, Figure 4, and our full analysis across all combinators in Appendix C) to report means over at least 3 random initialization seeds per dataset.

Q2.2 When does seed variance arise, and what causes it?

Across our multi-seed runs, we find that variance across seeds is very small when the learning signal in the data is either strong or weak (where runs consistently converge to near 100% or near 0% accuracy), and rises primarily on borderline datasets right along the transition boundary (such as the anti-diagonal entries of Figure 1A).

We also studied this boundary variance across 32 random initializations on a fixed dataset and batch order in Appendix C.5 (Figure 12): while all 32 runs reach near-zero training loss, their test accuracies span from 30% to 99%, and we can predict a run's final generalization accuracy within the first few epochs from whether its initial attention value weights suppress raw ff-token identity in favor of an ff-invariant direction.


Q3. Presentation, experimental setup, and Section 3.1 clarifications

Q3.1 Explaining the task setup and DAS in the main text

W1 / W4: "My primary issue is with clarity... it provides very little information about how the task data is actually presented to the model and how DAS is implemented... It may be useful more broadly to have a dedicated methods section..."

Thank you for the suggestion! To improve the reading flow, we expanded §2.1 and §2.2:

  • Task structure and evaluation (§2.1): We added a clear description of how prompts and targets are formatted as token sequences (e.g., B f g x with single-token target g(f(x))∈Yg(f(x)) \in \mathcal{Y}, and intermediate values never appearing in the prompt) and how compositional generalization is evaluated using the metric of recombination accuracy. We also update the full date generation and training details in Appendices B.2–B.3.
  • Causal localization and DAS (§2.2): We added a dedicated paragraph in §2.2 explaining how each combinator defines a high-level causal model and how we use interchange interventions (also known as activation patching), DAS, and IIA to localize intermediate variables. We also put more relevant details in Appendix B.4.

Q3.2 Clarifying how ∣V∣|\mathcal{V}| is varied and unifying "outer functions" vs. "contexts"

W2: "How do you vary the number of intermediate values in Fig. 1a? Note that you are also labeling the x axis of this plot as 'contexts' in the panel, but then refer to it as 'outer functions' in the figure captions..."

  • How we vary ∣V∣|\mathcal{V}|: We explicitly control the number of intermediate values ∣V∣|\mathcal{V}| as an input parameter to our data generation algorithm, which sets the codomain size of the balanced inner mappings. We clarified this in the dataset construction paragraph in §2.1 and added our data generation algorithm in Appendix B.2. Regarding the specific values, we sample ∣V∣∈{32,48,64,128}|\mathcal{V}| \in \{32, 48, 64, 128\} for B\mathsf{B} in Figure 1A. Note that we also updated the y-axis label of Figure 1A to the ratio ∣V∣/∣Y∣|\mathcal{V}|/|\mathcal{Y}| for consistency with the rest of the paper; in Figure 1A, this is directly equivalent to varying ∣V∣|\mathcal{V}| since we hold ∣Y∣=16|\mathcal{Y}| = 16 fixed.
  • Unifying "outer functions" and "contexts": Sorry for the confusion! We updated the x-axis label of Figure 1A to "Avg. # of outer functions per (f,x)(f,x)" to match the caption and §2.1, and we explain in §4 (and in more detailed in Appendix D) how "outer functions" in B\mathsf{B} corresponds to the more general notion of "literal contexts" across combinators.

Q3.3 Clarifying the hh-dimensional code, ll, and Figure 2(c)

W1: "What is shown in Fig. 2c? The caption is not very helpful and I had a hard time understanding the relevant paragraph (last paragraph of section 3.1.1): what does it mean for f(x) to be encoded in an h-dimensional code? What is l? How does the bilinear interaction implement this functional mapping?"

We have expanded the caption of Figure 2(c)–(d) and clarified §3.1 (with more details in Appendix E.2):

  • Bilinear interaction: In single-token B=g(f(x))\mathsf{B}=g(f(x)), the attention weight from query xx to key ff, af,x=σ(WKEf⋅WQEx)a_{f,x} = \sigma(W_K E_f \cdot W_Q E_x), directly captures a bilinear interaction between the embeddings of ff and xx.
  • hh-dimensional code: The hh-dimensional code describes the feature geometry of f(x)f(x) across attention heads. Consider a simple case with 4 binary variables, which can encode 24=162^4 = 16 values via a 4-dimensional code. In the case of f(x)f(x), each attention head serves as a variable that takes at most ll discrete values (explained below), yielding an hh-dimensional code (h≤Hh \le H) that can encode at most lhl^h values. This feature geometry explains how the model packs a relatively large number of intermediate values (e.g., ∣V∣=128|\mathcal{V}| = 128) into a small number of attention heads.
  • What ll is: ll is the maximum number of discrete values (buckets) an attention head represents. This comes from our empirical observation that attention weights af,xa_{f,x} are encoded in discrete clusters rather than spread evenly between 0 and 1 (the lower and upper bounds of an attention weight). For example, in Figure 2(c), there are roughly 2 clusters for the attention head on the x-axis and 5 clusters for the attention head on the y-axis.
  • What Figure 2(c) shows: Putting this together, Figure 2(c) illustrates the feature geometry of f(x)f(x). Since the full code in this 4-head model is 4-dimensional, we randomly picked two attention heads to visualize how the representations of (f,x)(f,x) pairs with the same intermediate value v=f(x)v = f(x) cluster together.


We hope these revisions and explanations address your concerns, and we very much welcome any further questions or suggestions!

Thank you again for your careful reading and constructive suggestions! They were very helpful in improving the clarity of the paper and refining how we present our theoretical argument.

As the discussion period closes today, we wanted to check in briefly to see if anything in the updated draft or our responses remains unclear, or if there are any remaining questions we could help clarify. We would very much welcome any further discussion or suggestions!

Comments on the paper

1 comment

We thank all three reviewers for their thoughtful engagement with our work! We are glad that the reviewers found our problem framing “well-motivated” (zmH3, NPk7, 4FxD), our synthetic combinator tasks “a really good perspective on implicit reasoning” (zmH3, 4FxD), our mechanistic circuit analysis “well executed” (NPk7), and our theoretical account of how models induce intermediate variables via gradient aggregation “convincing” and “interesting” (zmH3, 4FxD).

Prompted by the reviewers' feedback, we have revised the manuscript and conducted new analysis with two primary goals in mind:

  1. Clarifying and expanding our theoretical argument on the learning signal, and
  2. Restructuring the paper so that this account sits at the center of the narrative and directly explains our empirical findings across datasets and combinators


1. Clarified and expanded our theoretical account (§3-5)

We separated and expanded the two sides of our argument, and added a dedicated section connecting the theory to our empirical results: 

  • 1.1 Low-level mechanistic argument (§3.2): We refined our analysis of how shared contexts align logit gradients to pull same-value representations together (Observation 1), supported by empirical gradient and representation tracking in the residual stream (Figure 3, Appendix E.4.1).
  • 1.2 Higher-level probabilistic argument (§4): We moved our probabilistic analysis into its own section (§4), expanding it to more clearly explain how a learner can infer whether two calls evaluate to the same intermediate value across shared contexts, and showing how the introduced concepts apply to each individual combinator in Appendix D.
  • 1.3 Explaining empirical patterns across datasets and combinators (§5, Appendices C & D): Following the reviewers' suggestion to give our theory a more central role, we added a dedicated §5 to show how our account explains the empirical patterns observed earlier in the paper: Two quantities derived from our account—the average number of contexts shared by two calls and the collision ratio ∣V∣/∣Y∣|\mathcal{V}|/|\mathcal{Y}|—together with a third factor related to outer-function learning (the average number of training examples per outer-function entry), quantitatively predict the transition from memorization to compositional generalization across 3,741 datasets (Figure 4, Appendices C.1–C.4).

2. Restructured the presentation to improve the reading flow

To make the paper easier to navigate, we:

  • Rewrote the second half of §1 as a roadmap of our findings and integrated more relevant literature across the main text;
  • Introduced explicit definitions of the task format, evaluation metrics (recombination accuracy), and causal localization methods (interchange interventions, DAS, IIA) upfront in §2 (with full details in Appendix B); and
  • Expanded the caption of Figure 2 in §3.1 to help clarify the empirical evidence for how the model represents f(x)f(x) in B\mathsf{B}.


We have uploaded the revised PDF with major changes highlighted in blue.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.