- 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
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:
- 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). - is the exact "hierarchical equality" circuit analyzed in interpretability and cognitive science (Geiger et al., 2024).
- 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 .
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
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 and 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 : In our original submission, we coupled the generation parameters ( and ), under which datasets with sufficiently rich signals for and were rarely sampled. In the revised manuscript, we use a more flexible data generation setup (§2.1, Appendix B.2) that varies and 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 (Appendix C.1, Figure 6).
- Scaling model size alone does not overcome weak data signals: Conversely, to test whether deeper models can learn (or ) 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 ( recombination accuracy) across all low-context or high- datasets where the 2-layer model fails.
Together, these results show that the bottleneck on is not model capacity, but rather the training data distribution.
Q2.2 Using our theory to explain why 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, require a more favorable data distribution (e.g., calls needs to share more contexts) to generalize, compared with . 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 ( and ): 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 and , the branches use disjoint tokens, so any shared surrounding context (e.g.,
h g v uin ) evaluates the second branch to the same value and guarantees the same answer. - () share arguments between constituents: In , however, the two branches share function or argument tokens—such as in or in . If two same-value calls differ in their shared arguments (e.g., ), pairing them with the exact same surrounding tokens (
h g v) evaluates the second branch at two different inputs, vs. , which usually produce different target answers and conflicting gradients. - Why a more favorable data distribution is needed for models to learn : 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).
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:
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).