Compositional Generalization

Follow this topic Ask about this topic

Compositional generalization studies whether models can reuse learned concepts, skills, and rules in combinations they did not encounter during training. Approaches include modular and object-centric architectures, factorized or symbolic representations, and training methods such as curricula, structured reasoning traces, and reinforcement learning. Researchers test these abilities on controlled language, vision, arithmetic, planning, and robotics tasks, often holding out combinations, deeper structures, or longer sequences. Results remain uneven: models often recombine familiar parts more reliably than they discover new ones, and strong test accuracy can reflect shortcuts rather than reusable structure.

Latest papers

113 papers12 papers in the last four weeks, up 9% on the four weeks before. 0.1% of all new papers.

Mar 30, 2026

Known Intents, New Combinations: Clause-Factorized Decoding for Compositional Multi-Intent Detection

Multi-intent detection papers usually ask whether a model can recover multiple intents from one utterance. We ask a harder and, for deployment, more useful question: can it recover new combinations of familiar intents? Existing benchmarks only weakly test this, because train and test often share the same broad co-occurrence patterns. We introduce CoMIX-Shift, a controlled benchmark built to stress compositional generalization in multi-intent detection through held-out intent pairs, discourse-pattern shift, longer and noisier wrappers, held-out clause templates, and zero-shot triples. We also present ClauseCompose, a lightweight decoder trained only on singleton intents, and compare it to whole-utterance baselines including a fine-tuned tiny BERT model. Across three random seeds, ClauseCompose reaches 95.7 exact match on unseen intent pairs, 93.9 on discourse-shifted pairs, 62.5 on longer/noisier pairs, 49.8 on held-out templates, and 91.1 on unseen triples. WholeMultiLabel reaches 81.4, 55.7, 18.8, 15.5, and 0.0; the BERT baseline reaches 91.5, 77.6, 48.9, 11.0, and 0.0. We also add a 240-example manually authored SNIPS-style compositional set with five held-out pairs; there, ClauseCompose reaches 97.5 exact match on unseen pairs and 86.7 under connector shift, compared with 41.3 and 10.4 for WholeMultiLabel. The results suggest that multi-intent detection needs more compositional evaluation, and that simple factorization goes surprisingly far once evaluation asks for it.

Abhilash Nandy

Microsoft Research India

Intent Classification Compositional Generalization Multi-Label Classification

Mar 30, 2026

Stop Probing, Start Coding: Why Linear Probes and Sparse Autoencoders Fail at Compositional Generalisation

The linear representation hypothesis states that neural network activations encode high-level concepts as linear mixtures. However, under superposition, this encoding is a projection from a higher-dimensional concept space into a lower-dimensional activation space, and a linear decision boundary in the concept space need not remain linear after projection. In this setting, classical sparse coding methods with per-sample iterative inference leverage compressed sensing guarantees to recover latent factors. Sparse autoencoders (SAEs), on the other hand, amortise sparse inference into a fixed encoder, introducing a systematic gap. We show this amortisation gap persists across training set sizes, latent dimensions, and sparsity levels, causing SAEs to fail under out-of-distribution (OOD) compositional shifts. Through controlled experiments that decompose the failure, we identify dictionary learning as the limiting factor (not the inference procedure): SAE-learned dictionaries point in substantially wrong directions, and replacing the encoder with per-sample FISTA on the same dictionary does not close the gap. An oracle baseline proves the problem is solvable with a good dictionary at all scales tested. Our results, including experiments with real LLM activations (Pythia-70M, Gemma-2-2B) reframe the SAE failure as a dictionary learning challenge, not an inference problem, and point to scalable dictionary learning as the key open problem for sparse inference under superposition.

Vitória Barin-Pacela, Shruti Joshi, Isabela Camacho +2

Mila - Québec AI Institute & Université de Montréal · Santa Clara University · Cold Spring Harbor Laboratory

Sparse Autoencoders Sparse Coding Dictionary Learning Compositional Generalization

Mar 27, 2026

Arithmetic OOD Failure Unfolds in Stages in Minimal GPTs

Arithmetic benchmarks are often reduced to a single held-out score, but that score can conflate qualitatively different failures. We study a controlled minimal GPT trained on exhaustive 2-digit addition, where all local digit transitions are already present in training, and ask why 3-digit generalization still fails. The failure is staged. First, there is a layout barrier: a learned absolute-position model collapses under a pure 3-digit layout shift, and mixed-layout exposure is the only intervention that materially weakens this barrier. Second, after layout repair, the hundreds position behaves like a carry flag rather than a semantic hundreds digit; targeted carry probes reverse the relevant logit margin, whereas a matched extra-data control does not. Third, after carry repair, the main remaining bottleneck is conditional recomposition: high-conditioned tail data outperforms a matched control, high-only data, and tail-only data on all true-3-digit suites, and the same ordering reappears in a larger 2-layer bridge experiment. The residual errors after recomposition are then overwhelmingly tens-only, and a separate 10-seed late-stage study shows that a sign-aware tens repair raises exact match on the hardest thousands-carry suite from 0.664 to 0.822. We therefore provide an experimentally testable decomposition of arithmetic OOD failure into layout, carry-semantics, recomposition, and late tens-residual stages.

Seine A. Shintani

Department of Biomedical Sciences, College of Life and Health Sciences, Chubu University, Kasugai, Aichi 487-8501, Japan · Center for Mathematical Science and Artificial Intelligence, Chubu University, Kasugai, Aichi 487-8501, Japan · Institute for Advanced Research, Nagoya University, Nagoya, Aichi 464-8601, Japan

Numerical Reasoning in Language Models OOD Generalization Compositional Generalization Length Generalization

Mar 26, 2026

Towards Generalizable Robotic Data Flywheel: High-Dimensional Factorization and Composition

The lack of sufficiently diverse data, coupled with limited data efficiency, remains a major bottleneck for generalist robotic models, yet systematic strategies for collecting and curating such data are not fully explored. Task diversity arises from implicit factors that are sparsely distributed across multiple dimensions and are difficult to define explicitly. To address this challenge, we propose F-ACIL, a heuristic factor-aware compositional iterative learning framework that enables structured data factorization and promotes compositional generalization. F-ACIL decomposes the data distribution into structured factor spaces such as object, action, and environment. Based on the factorized formulation, we develop a factor-wise data collection and an iterative training paradigm that promotes compositional generalization over the high-dimensional factor space, leading to more effective utilization of real-world robotic demonstrations. With extensive real-world experiments, we show that F-ACIL can achieve more than 45% performance gains with 5-10

\times

fewer demonstrations comparing to that of which without the strategy. The results suggest that structured factorization offers a practical pathway toward efficient compositional generalization in real-world robotic learning. We believe F-ACIL can inspire more systematic research on building generalizable robotic data flywheel strategies. More demonstrations can be found at: https://f-acil.github.io/

Yuyang Xiao, Yifei Zhou, Haoran Wang +2

ByteDance Seed

Data-Efficient Robot Learning Robotic Data Collection Generalization in Robotic Manipulation Compositional Generalization Learning from Demonstration

Mar 23, 2026

Thinking Deeper, Not Longer: Memory-Efficient Test-Time Reasoning with Depth-Recurrent Transformers for Compositional Generalization

Standard Transformers have a fixed computational depth, limiting their ability to generalize to tasks that require variable-depth reasoning. The usual remedy, Chain-of-Thought (CoT), spends tokens to reason, inflating the key--value cache and making latency grow with the step count, so memory becomes the limiting cost when reasoning is served over large query batches. We study a depth-recurrent Transformer that decouples computational depth from parameter count by iterating a shared-weight block, so that each added reasoning step costs flat memory and linear latency, with no token generation. Three ingredients keep the recurrence stable for 20+ thinking steps: a silent thinking objective that supervises only the final output, LayerScale initialization, and an identity-biased gate that opens a gradient highway across steps. We characterize it on three compositional domains with decreasing structural bias: graph reachability (adjacency masking), nested boolean logic (relative positioning), and unstructured relational text (no positional cue). We find a computational frontier: accuracy climbs once the thinking-step count meets the task's complexity, reaching near-perfect performance on the two structured tasks and a lower plateau on unstructured text. How it climbs depends on the structural bias---abruptly from chance on the graph task, gradually on the other two. Depth recurrence extrapolates beyond the training range: it succeeds on the graph task where fixed-depth models barely extrapolate, and on the two sequence tasks comes within two points of fixed-depth Transformers that use

4

--

6.4\times

more parameters. On the graph task, whose adjacency mask makes propagation depth verifiable, intermediate per-step supervision---a standard recipe for deep iterative models---consistently harms this extrapolation. We release the code for reproducibility.

Hung-Hsuan Chen

Computer Science and Information Engineering National Central University Taoyuan, Taiwan

Efficient Transformer Inference Recurrent Transformers Structured Reasoning Algorithmic Reasoning Compositional Generalization LLM Reasoning

Mar 18, 2026

How Psychological Learning Paradigms Shaped and Constrained Artificial Intelligence

Current artificial intelligence systems struggle with systematic compositional reasoning: the capacity to recombine known components in novel configurations. This paper argues that the failure is architectural, not merely a matter of scale or training data, and that its origins lie in the psychological learning theories from which AI paradigms were derived. The argument proceeds in three stages. First, drawing on the systematicity debate in cognitive science and on the demonstration of Aizawa that neither connectionism nor classicism can make systematicity a structural consequence of the architecture, the paper establishes that the corrective techniques proliferating in modern AI, from chain-of-thought prompting to alignment through human feedback, function as auxiliary hypotheses that address symptoms without resolving the underlying architectural indifference to systematicity. Second, it traces the genealogy from psychological learning theory to AI methodology, showing that behaviourism, cognitivism, and constructivism each bequeathed a specific structural limitation to the AI paradigm it inspired: the exclusion of internal structure, the opacity of representation, and the absence of formal construction operators. A cross-cultural reappraisal of rote learning reveals a further underexploited pathway. Third, the paper introduces ReSynth, a trimodular conceptual framework that proposes the principled separation of reasoning, identity, and memory as a path toward architectures in which systematic behaviour is a structural consequence of design rather than a correction applied after the fact.

Alex Anvi Eponon, Ildar Batyrshin, Christian E. Maldonado-Sifuentes +1

Centro de Investigación en Computación (CIC), Instituto Politécnico Nacional (IPN), Mexico City, Mexico.

Cognitive Architectures for AI Agents Compositional Generalization

Mar 17, 2026

Functorial Neural Architectures from Higher Inductive Types

Neural networks often learn the parts of a task but fail on novel combinations of those parts. We argue that this failure is architectural: a decoder generalizes compositionally only when it respects the algebraic laws of the task, i.e. when it descends from freely generated sequences to the quotient determined by those laws. We make this principle constructive by compiling Higher Inductive Type (HIT) specifications into neural architectures. Basepoints, path constructors, and 2-cells are mapped to base constraints, generator networks, structural concatenation, and learned homotopies. The resulting transport decoders are strict monoidal functors by construction: decoding a concatenated word is concatenation of independently generated loop segments. In contrast, we prove that softmax self-attention cannot simultaneously satisfy strict monoidal composition and descent to any non-trivial compositional quotient. Experiments on the torus, wedge of circles, and Klein bottle validate the predicted hierarchy: functorial decoders outperform non-functorial alternatives by

2

--

10\times

, and a learned 2-cell closes a

46\%

error gap precisely on words exercising the Klein-bottle relation. These results suggest that compositional generalization should be enforced as functorial structure in the architecture, rather than learned from examples alone.

Karen Sargsyan

Institute of Chemistry, Academia Sinica, Taipei, Taiwan

Compositional Generalization Compositional Representation Learning

Mar 15, 2026

Ternary Gamma Semirings: From Neural Implementation to Categorical Foundations

This paper establishes a theoretical framework connecting neural network learning with abstract algebraic structures. We first present a minimal counterexample demonstrating that standard neural networks completely fail on compositional generalization tasks (0% accuracy). By introducing a logical constraint -- the Ternary Gamma Semiring -- the same architecture learns a perfectly structured feature space, achieving 100% accuracy on novel combinations. We prove that this learned feature space constitutes a finite commutative ternary

Γ

-semiring, whose ternary operation implements the majority vote rule. Comparing with the recently established classification of Gokavarapu et al., we show that this structure corresponds precisely to the Boolean-type ternary

Γ

-semiring with

|T|=4

,

|Γ|=1

}, which is unique up to isomorphism in their enumeration. Our findings reveal three profound conclusions: (i) the success of neural networks can be understood as an approximation of mathematically ``natural'' structures; (ii) learned representations generalize because they internalize algebraic axioms (symmetry, idempotence, majority property); (iii) logical constraints guide networks to converge to these canonical forms. This work provides a rigorous mathematical framework for understanding neural network generalization and inaugurates the new interdisciplinary direction of Computational

Γ

-Algebra.

Ruoqi Sun

Intelligent Game and Decision Lab(IGDL), No.1 Xianghongqi Road, Haidian District, Beijing, 100091,China.

Neural Network Generalization Compositional Representation Learning Compositional Generalization

Mar 9, 2026

The ARC of Progress towards AGI: A Living Survey of Abstraction and Reasoning

The Abstraction and Reasoning Corpus (ARC-AGI) has become a key benchmark for fluid intelligence in AI. This survey presents the first cross-generation analysis of 82 approaches across three benchmark versions and the ARC Prize 2024-2025 competitions. Our central finding is that performance degradation across versions is consistent across all paradigms: program synthesis, neuro-symbolic, and neural approaches all exhibit 2-3x drops from ARC-AGI-1 to ARC-AGI-2, indicating fundamental limitations in compositional generalization. While systems now reach 93.0% on ARC-AGI-1 (Opus 4.6), performance falls to 68.8% on ARC-AGI-2 and 13% on ARC-AGI-3, as humans maintain near-perfect accuracy across all versions. Cost fell 390x in one year (o3's

4,500/task to GPT-5.2's

12/task), although this largely reflects reduced test-time parallelism. Trillion-scale models vary widely in score and cost, while Kaggle-constrained entries (660M-8B) achieve competitive results, aligning with Chollet's thesis that intelligence is skill-acquisition efficiency. Test-time adaptation and refinement loops emerge as critical success factors, while compositional reasoning and interactive learning remain unsolved. ARC Prize 2025 winners needed hundreds of thousands of synthetic examples to reach 24% on ARC-AGI-2, confirming that reasoning remains knowledge-bound. This first release of the ARC-AGI Living Survey captures the field as of February 2026, with updates at https://nimi-ai.com/arc-survey/

Sahar Vahdati, Andrei Aioanei, Haridhra Suresh +1

TIB - Leibniz Information Centre for Science and Technology · L3S Research Center, Leibniz University of Hannover · Dresden University of Technology +1

Abstract Reasoning ARC-AGI Compositional Generalization Program Synthesis

Feb 27, 2026

Compositional Generalization Requires Linear, Orthogonal Representations in Vision Embedding Models

Compositional generalization, the ability to recognize familiar parts in novel contexts, is a defining property of intelligent systems. Although modern models are trained on massive datasets, they still cover only a tiny fraction of the combinatorial space of possible inputs, raising the question of what structure representations must have to support generalization to unseen combinations. We formalize three desiderata for compositional generalization under standard training (divisibility, transferability, stability) and show they impose necessary geometric constraints: representations must decompose linearly into per-concept components, and these components must be orthogonal across concepts. This provides theoretical grounding for the Linear Representation Hypothesis: the linear structure widely observed in neural representations is a necessary consequence of compositional generalization. We further derive dimension bounds linking the number of composable concepts to the embedding geometry. Empirically, we evaluate these predictions across modern vision models (CLIP, SigLIP, DINO) and find that representations exhibit partial linear factorization with low-rank, near-orthogonal per-concept factors, and that the degree of this structure correlates with compositional generalization on unseen combinations. As models continue to scale, these conditions predict the representational geometry they may converge to. Code is available at https://github.com/oshapio/necessary-compositionality.

Arnas Uselis, Andrea Dittadi, Seong Joon Oh

Tübingen AI Center, University of Tübingen · Helmholtz · Technical University of Munich

Neural Representation Geometry Visual Representation Learning Linear Representation Hypothesis Orthogonal Representation Learning Geometric Representation Learning Compositional Representation Learning+1

Feb 24, 2026

COMiT: Learning Structured Visual Tokens through Sequential Communication

Discrete image tokenizers provide a sequential interface for vision and multimodal models, but are typically optimized for reconstruction or compression and therefore tend to encode local appearance rather than object-level structure. We introduce COMiT, a communication-inspired framework for learning structured discrete visual representations. COMiT constructs a fixed-length latent message through sequential visual observations: at each step, a transformer processes a localized image crop and updates, refines, and reorganizes the existing token sequence. After several iterations, the resulting message conditions a flow-matching decoder that reconstructs the complete image. The encoder and decoder are implemented within a single transformer and trained end-to-end using flow-matching reconstruction and semantic representation-alignment objectives. COMiT substantially improves compositional generalization and relational reasoning over prior methods. Our experiments show that, while semantic alignment helps ground the representation, attentive sequential tokenization is critical for inducing more interpretable, object-centric token structures.

Aram Davtyan, Yusuf Sahin, Yasaman Haghighi +4

Computer Vision Group, University of Bern, Switzerland · VITA Lab, EPFL, Switzerland

Image Tokenization Visual Tokenization Object-Centric Representation Learning Compositional Generalization

Feb 22, 2026

Neuro-Symbolic Decoding of Neural Activity

We propose NEURONA, a neuro-symbolic framework for fMRI decoding and concept grounding in neural activity. Leveraging image- and video-based fMRI question-answering datasets, NEURONA learns to decode interacting concepts from visual stimuli based on patterns of fMRI responses, integrating symbolic reasoning and compositional execution with fMRI grounding across brain regions. We demonstrate that incorporating structural priors (e.g., compositional predicate-argument dependencies between concepts) into the decoding process significantly improves both decoding accuracy over precise queries, and notably, generalization to unseen queries at test time. With NEURONA, we highlight neuro-symbolic frameworks as promising tools for understanding neural activity.

Yanchen Wang, Joy Hsu, Ehsan Adeli +1

Columbia University · Stanford University

Neural Decoding fMRI-Based Visual Decoding Neuro-Symbolic Reasoning Multimodal Grounding Compositional Generalization

Feb 18, 2026

Are Object-Centric Representations Better At Compositional Generalization?

Compositional generalization, the ability to reason about novel combinations of familiar concepts, is fundamental to human cognition and a critical challenge for machine learning. Object-centric (OC) representations, which encode a scene as a set of objects, are often argued to support such generalization, but systematic evidence in visually rich settings is limited. We introduce a Visual Question Answering benchmark across three controlled visual worlds (CLEVRTex, Super-CLEVR, and MOVi-C) to measure how well vision encoders, with and without object-centric biases, generalize to unseen combinations of object properties. To ensure a fair and comprehensive comparison, we carefully account for training data diversity, sample size, representation size, downstream model capacity, and compute. We use DINOv2 and SigLIP2, two widely used vision encoders, as the foundation models and their OC counterparts. Our key findings reveal that (1) OC approaches are superior in harder compositional generalization settings; (2) original dense representations surpass OC only on easier settings and typically require substantially more downstream compute; and (3) OC models are more sample efficient, achieving stronger generalization with fewer images, whereas dense encoders catch up or surpass them only with sufficient data and diversity. Overall, object-centric representations offer stronger compositional generalization when any one of dataset size, training data diversity, or downstream compute is constrained.

Ferdinand Kapl, Amir Mohammad Karimi Mamaghan, Maximilian Seitzer +4

Technical University of Munich · Helmholtz AI, Munich · KTH Royal Institute of Technology +2

Compositional Generalization Object-Centric Representation Learning Visual Representation Learning

Jan 22, 2026

Why Can't I Open My Drawer? Mitigating Object-Driven Shortcuts in Zero-Shot Compositional Action Recognition

Zero-Shot Compositional Action Recognition (ZS-CAR) requires recognizing novel verb-object combinations composed of previously observed primitives. In this work, we tackle a key failure mode: models predict verbs via object-driven shortcuts (i.e., relying on the labeled object class) rather than temporal evidence. We argue that sparse compositional supervision and verb-object learning asymmetry can promote object-driven shortcut learning. Our analysis with proposed diagnostic metrics shows that existing methods overfit to training co-occurrence patterns and underuse temporal verb cues, resulting in weak generalization to unseen compositions. To address object-driven shortcuts, we propose Robust COmpositional REpresentations (RCORE) with two components. Co-occurrence Prior Regularization (CPR) adds explicit supervision for unseen compositions and regularizes the model against frequent co-occurrence priors by treating them as hard negatives. Temporal Order Regularization for Composition (TORC) enforces temporal-order sensitivity to learn temporally grounded verb representations. Across Sth-com and EK100-com, RCORE reduces shortcut diagnostics and consequently improves compositional generalization.

Geo Ahn, Inwoong Lee, Taeoh Kim +3

1Kyung Hee University · ∗This work was done during an internship at NAVER Cloud. · 2NAVER Cloud

Zero-Shot Learning Video Action Recognition Shortcut Learning Compositional Representation Learning Compositional Generalization Zero-Shot Action Recognition

Dec 9, 2025

Is Generation Required for Data-Efficient Perception?

It has been hypothesized that achieving the data efficiency of human visual perception requires a generative approach in which internal representations result from inverting a decoder. Yet today's most successful vision models are non-generative, relying on an encoder that maps images to representations without decoder inversion. This raises the question of whether generation is necessary for data-efficient machine perception. To address this, we study to what extent generative and non-generative methods can achieve compositional generalization, a hallmark of human data efficiency. Under a compositional generative process, we formally characterize the inductive biases required for compositional generalization in decoder-based (generative) and encoder-based (non-generative) methods. We show theoretically that the inductive biases required for an encoder are substantially more complex and generally infeasible to impose explicitly through architectural constraints or regularization. By contrast, the decoder biases take a simple form that can be enforced directly. These results suggest that compositional generalization may be substantially easier to achieve through a generative paradigm of learning and inverting a decoder rather than learning an encoder directly. We examine our theoretical findings empirically by training a range of generative and non-generative methods on synthetic image data. We find that non-generative methods often fail to generalize compositionally and require large-scale pretraining to improve generalization. By comparison, generative methods yield gains in generalization without requiring additional data.

Jack Brady, Bernhard Schölkopf, Thomas Kipf +2

Max Planck Institute for Intelligent Systems, Tübingen, Germany · Tübingen AI Center · ELLIS Institute, Tübingen +1

Visual Representation Learning Generative Modeling Inductive Bias Compositional Generalization Data-Efficient Learning

Dec 1, 2025

How Does RL Post-training Induce Skill Composition? A Case Study on Countdown

While reinforcement learning (RL) successfully enhances reasoning in large language models, its role in fostering compositional generalization (the ability to synthesize novel skills from known components) is often conflated with mere length generalization. To this end, we study what RL post-training teaches about skill composition and how the composition structure affects the skill transfer. We focus on the Countdown task (given n numbers and a target, form an expression that evaluates to the target) and analyze model solutions as expression trees, where each subtree corresponds to a reusable subtask and thus can be viewed as a "skill." Tracking tree shapes and their success rates over training, we find: (i) out-of-distribution (OOD) generalization to larger n and to unseen tree shapes, indicating compositional reuse of subtasks; (ii) the order of skill acquisition depends upon the composition structure---models master shallow balanced trees (workload is balanced between subtasks) before deep unbalanced ones, with persistent fragility on right-heavy structures for a fixed composition depth. Our diagnostic reveals what is learned, in what order, and where generalization fails, clarifying how RL-only post-training induces OOD generalization beyond what standard metrics such as pass@k reveal. To study the implications of our findings for real-world tasks, we present a preliminary study on formal theorem proving.

Simon Park, Simran Kaur, Sanjeev Arora

Princeton Language and Intelligence (PLI), Princeton University

Compositional Generalization RL Post-Training Emergent Abilities in Language Models

Nov 24, 2025

Understanding the Staged Dynamics of Transformers in Learning Latent Structure

Language modeling has shown us that transformers can discover latent structure from context, but the dynamics of how they acquire different components of that structure remain poorly understood, leading to assertions that models just remix training data. In this work, we use the Alchemy benchmark in a controlled setting (Wang et al.,2021) to investigate latent structure learning. We train a small decoder-only transformer on three task variants: 1) inferring missing transitions from partial contextual information, 2) composing simple rules to solve multi-transition sequences, and 3) decomposing complex multi-step examples to infer intermediate transitions. By factorizing each task into interpretable components, we show that the model learns the different latent structure components in discrete stages. We also observe an asymmetry: the model composes fundamental transitions robustly, but struggles to decompose complex examples to discover the atomic transitions. Finally, using causal interventions, we identify layer-specific plasticity windows during which freezing substantially delays or prevents stage completion. These findings provide insight into how a transformer model acquires latent structure, offering a detailed view of how capabilities evolve during training.

Rohan Saha, Farzane Aminmansour, Alona Fyshe

Department of Computing Science University of Alberta Edmonton, Canada · Department of Computing Science and Psychology University of Alberta Edmonton, Canada

Transformer Training Dynamics Decoder-Only Language Models Neural Network Training Dynamics Compositional Generalization

Oct 18, 2025

Memorizing Long-tail Data Can Help Generalization Through Composition

Deep learning has led researchers to rethink the relationship between memorization and generalization. In many settings, memorization does not hurt generalization due to implicit regularization and may help by memorizing long-tailed examples. In this paper, we consider the synergy between memorization and simple composition -- the ability to make correct prediction on a combination of long-tailed features. Theoretically, we show that for a linear setting, memorization together with composition can help the model make correct predictions on rare test examples that require a combination of long-tailed features, even if such combinations were never observed in the training data. Experiments on neural network architecture on simple data show that the theoretical insight extends beyond the linear setting, and we further observe that the composition capability of the model depends on its architecture.

Mo Zhou, Haoyang Ma, Rong Ge

University of Washington · Duke University

Neural Network Generalization Neural Network Memorization Long-Tail Learning Compositional Generalization

Oct 3, 2025

What Drives Compositional Generalization in Visual Generative Models? The Importance of Continuous Training Objectives

Compositional generalization, the ability to generate novel combinations of known concepts, is a key ingredient for visual generative models. Yet, not all mechanisms that enable or inhibit it are fully understood. In this work, we conduct a systematic study of which design choices critically determine compositional generalization in image and video generation. By isolating independent design axes, we identify two key factors strongly associated with compositional success: (i) whether the training objective operates on a discrete or continuous distribution, and (ii) the completeness of conditioning information about constituent factors during training. We also show that relaxing the discrete loss with an auxiliary continuous latent objective can partially recover compositional performance in discrete models like MaskGIT. Our findings, corroborated by diverse compositional tasks and preliminary evidence in world models and LLMs, motivate a shift toward continuous objectives for compositional generalization.

Karim Farid, Rajat Sahay, Yumna Ali Alnaggar +4

University of Freiburg · Bosch Center for Artificial Intelligence · Inria, École Normale Supérieure, CNRS, PSL Research University

Compositional Image Generation Generative Modeling Video Generation Conditional Generative Modeling Compositional Generalization Compositional Video Generation

Sep 29, 2025

Unveiling the Mechanisms of Multi-Hop Reasoning in Transformers via Identity Bridge

Large Language Models (LLMs) excel at multi-hop reasoning in distribution, yet fail on unseen compositions, a phenomenon known as the curse of two-hop reasoning. In this work, we argue that this phenomenon can be attributed to a missing supervision on the bridge entity. We formalize this gap by introducing identity bridge, a minimal supervision that enforces a identity mapping on bridge tokens. Under this supervision, even a one-layer transformer with uniform attention (Emb-MLP) can achieve out-of-distribution (OOD) two-hop generalization. We provide a theoretical analysis demonstrating that identity bridge induces an implicit regularization effect, leading the model to establish a direct subject-to-answer association. From an empirical perspective, the performance of standard GPT-2 models aligns closely with simple Emb--MLP models across varying levels of problem complexity. Finally, analyses of fine-tuned mainstream LLMs indicate that correct two-hop predictions consistently coincide with the establishment of a subject-to-answer relationship, extending our findings to realistic settings.

Pengxiao Lin, Zheng-An Chen, Zhi-Qin John Xu

School of Mathematical Sciences, Shanghai Jiao Tong University · Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University · Shanghai Seres Information Technology Co., Ltd, Shanghai 200040, China.

Transformer Interpretability OOD Generalization Multi-Hop Reasoning Compositional Generalization

May 28, 2025

Learning Composable Chains-of-Thought

A common approach for teaching large language models (LLMs) to reason is to train on chain-of-thought (CoT) traces of in-distribution reasoning problems, but such annotated data is costly to obtain for every problem of interest. We want reasoning models to generalize beyond their training distribution, and ideally to generalize compositionally: combine atomic reasoning skills to solve harder, unseen reasoning tasks. We take a step towards compositional generalization of reasoning skills when addressing a target compositional task that has no labeled CoT data. We find that simply training models on CoT data of atomic tasks leads to limited generalization, but minimally modifying CoT formats of constituent atomic tasks to be composable can lead to improvements. We can train "atomic CoT" models on the atomic tasks with Composable CoT data and combine them with multitask learning or model merging for better zero-shot performance on the target compositional task. Such a combined model can be further bootstrapped on a small amount of compositional data using rejection sampling fine-tuning (RFT). Results on string operations and natural language skill compositions show that training LLMs on Composable CoT outperforms multitask learning and continued fine-tuning baselines within a given training data budget.

Fangcong Yin, Zeyu Leo Liu, Liu Leqi +2

The University of Texas at Austin · Princeton University

LLM Fine-Tuning CoT Reasoning LLM Training Compositional Generalization LLM Reasoning

May 14, 2025

Disassociating performance from compositional feature learning

Out-of-distribution (OOD) generalisation through composition requires a system to discover invariant properties from input-output associations and transfer them to novel inputs and unseen tasks. We argue that confirming compositional learning requires more than OOD evaluation alone: one must also verify that the learned features are genuinely compositional and that the system encodes their compositional rules. We demonstrate this through two tasks with clearly defined OOD metrics, generated via composable high-level abstractions, on which three standard architectures (MLP, CNN, Transformer) and an object-centric, slot-based architecture fail to generalise OOD. We pair these tasks with two novel attention-based architectures featuring an interpretable final hidden layer designed to expose whether compositional representations emerge. One architecture carries an engineered inductive bias that enables near-perfect OOD performance on one task. Our results show that even with appropriate biases and near-perfect OOD accuracy, a model can fail to learn the compositional feature structures necessary for systematic generalisation. The interpretable layer reveals that successful OOD performance is driven by task-specific biases rather than the discovery of reusable compositional primitives. These findings indicate that OOD benchmarks alone are insufficient for evaluating compositionality in neural networks.

George Dimitriadis, Spyridon Samothrakis

Computer Science and Electronic Engineering Department of the University of Essex

Representation Learning OOD Generalization Compositional Representation Learning Compositional Generalization

May 5, 2025

A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition

Compositional generalization

\unicode{x2013}

the ability to systematically process novel combinations of known components

\unicode{x2013}

is a hallmark of human intelligence; however, its theoretical foundation in neural networks is not yet well understood. This paper establishes a necessary and sufficient condition for provable compositional generalization, precisely characterizing its boundary. Conceptually, the condition consists of two principles: (i) structural alignment, where a model's computational graph aligns with a task's true compositional hierarchy, and (ii) unambiguous minimized representations, where each component encodes adequate but not redundant information on the training data. The result is fully proved and machine-verified in Lean 4 and holds even in few-shot and one-shot regimes. The necessity direction establishes that provable compositional generalization cannot circumvent these requirements, while the sufficiency direction yields a unified inductive bias that jointly governs architectural design, training data properties, and regularization strategies. Building on this condition, we develop an example algorithmic approach, illustrate it through a controlled minimal example, and further demonstrate the condition on the SCAN jump task. All conclusions are derived mathematically without reliance on empirical validation. Our work provides a theoretical characterization of provable compositional generalization.

Yuanpeng Li

Compositional Generalization