# How Do Language Models Compose Functions?

arXiv: https://arxiv.org/abs/2510.01685 · HTML: https://mlsanity.com/paper/2510.01685/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 57 references that are in the map.
- First posted on arXiv 2 Oct 2025.

## Builds on (most cited first, 30 of 34)

- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [BERT Rediscovers the Classical NLP Pipeline](https://mlsanity.com/paper/1905.05950/) (2019)
- [Transformer Feed-Forward Layers Build Predictions by Promoting Concepts in the Vocabulary Space](https://mlsanity.com/paper/2203.14680/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [Function Vectors in Large Language Models](https://mlsanity.com/paper/2310.15213/) (2023)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Patchscopes: A Unifying Framework for Inspecting Hidden Representations of Language Models](https://mlsanity.com/paper/2401.06102/) (2024)
- [Linearity of Relation Decoding in Transformer Language Models](https://mlsanity.com/paper/2308.09124/) (2023)
- [CREPE: Can Vision-Language Foundation Models Reason Compositionally?](https://mlsanity.com/paper/2212.07796/) (2022)
- [Do Large Language Models Latently Perform Multi-Hop Reasoning?](https://mlsanity.com/paper/2402.16837/) (2024)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [Language Models Implement Simple Word2Vec-style Vector Arithmetic](https://mlsanity.com/paper/2305.16130/) (2023)
- [Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures](https://mlsanity.com/paper/2007.08970/) (2020)
- [Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization](https://mlsanity.com/paper/2405.15071/) (2024)
- [Hopping Too Late: Exploring the Limitations of Large Language Models on Multi-Hop Queries](https://mlsanity.com/paper/2406.12775/) (2024)
- [Understanding and Patching Compositional Reasoning in LLMs](https://mlsanity.com/paper/2402.14328/) (2024)
- [Break It Down: Evidence for Structural Compositionality in Neural Networks](https://mlsanity.com/paper/2301.10884/) (2023)
- [Do Large Language Models Perform Latent Multi-Hop Reasoning without Exploiting Shortcuts?](https://mlsanity.com/paper/2411.16679/) (2024)
- [Relational Composition in Neural Networks: A Survey and Call to Action](https://mlsanity.com/paper/2407.14662/) (2024)
- [Back Attention: Understanding and Enhancing Multi-Hop Reasoning in Large Language Models](https://mlsanity.com/paper/2502.10835/) (2025)
- [On Linear Representations and Pretraining Data Frequency in Language Models](https://mlsanity.com/paper/2504.12459/) (2025)
- [Distributional reasoning in LLMs: Parallel reasoning processes in multi-hop reasoning](https://mlsanity.com/paper/2406.13858/) (2024)
- [Paths Not Taken: Understanding and Mending the Multilingual Factual Recall Pipeline](https://mlsanity.com/paper/2505.20546/) (2025)
- [Distinguishing Antonyms and Synonyms in a Pattern-based Neural Network](https://mlsanity.com/paper/1701.02962/) (2017)
- [Racing Thoughts: Explaining Contextualization Errors in Large Language Models](https://mlsanity.com/paper/2410.02102/) (2024)
- [Internal Chain-of-Thought: Empirical Evidence for Layer-wise Subtask Scheduling in LLMs](https://mlsanity.com/paper/2505.14530/) (2025)

## Built on by (most cited first, 8 of 8)

- [What do Language Models Learn and When? The Implicit Curriculum Hypothesis](https://mlsanity.com/paper/2604.08510/) (2026)
- [Shared Lexical Task Representations Explain Behavioral Variability In LLMs](https://mlsanity.com/paper/2604.22027/) (2026)
- [Reasoning as Pattern Matching: Shared Mechanisms in Human and LLM Everyday Reasoning](https://mlsanity.com/paper/2606.13607/) (2026)
- [Adversarial Concept Search: Predicting Compositional Errors From Feature Geometry](https://mlsanity.com/paper/2606.13934/) (2026)
- [Why Knowing Both Hops Is Not Enough: Understanding Two-Hop Generalization in Language Models](https://mlsanity.com/paper/2608.07261/) (2026)
- [Hierarchical Compositionality for An Assistive AI Agent](https://mlsanity.com/paper/2608.10330/) (2026)
- [A Calibrated Test of Internal Action Maps: State Signals Without Global Affine Closure](https://mlsanity.com/paper/2608.13626/) (2026)
- [Layer-Informed Fine-Tuning via Three-Stage Functional Segmentation of LLMs](https://mlsanity.com/paper/2609.38027/) (2026)

## Abstract (arXiv)

While large language models (LLMs) appear to be increasingly capable of solving compositional tasks, it is an open question whether they do so using compositional mechanisms. In this work, we investigate how feedforward LLMs solve two-hop factual recall tasks, which can be expressed compositionally as g(f(x)). We first confirm that modern LLMs continue to suffer from the "compositionality gap", i.e. their ability to compute both z = f(x) and y = g(z) does not entail their ability to compute the composition y = g(f(x)). We then decode residual stream representations and identify two processing mechanisms: one which solves tasks textitcompositionally, computing f(x) along the way to g(f(x)), and one which solves them textitdirectly, without any detectable signature of the intermediate variable f(x). Finally, we find that embedding space geometry is strongly related to which mechanism is employed, where the idiomatic mechanism is dominant when tasks are represented by translations from x to g(f(x)) in the embedding spaces. We fully release our data and code at: https://github.com/apoorvkh/composing-functions.