Compositional Generalization

Ask about this topic

Overview

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

CardsList

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

May 28, 2026

Learning to Extrapolate to New Tasks: A Relational Approach to Task Extrapolation

Modern learning systems excel at interpolation but struggle to generalize to unseen tasks outside the training distribution's support. This failure occurs even in simple settings, such as handling task parameters beyond the training range, and persists despite advances in foundation models. To this end, we develop the Relational Task Extrapolator (RTE), an algorithm designed to enable systematic extrapolation to novel tasks. The key observation is that extrapolation is inherently relational: extrapolating to unseen tasks requires learning how tasks transform into one another. If a model learns the transformation between tasks A and B during training, it can apply that same transformation to relate known tasks to unseen ones at test time. RTE operationalizes this idea by decomposing each target task into a known anchor task and a transformation linking the anchor and target. It then learns a relational operator, mapping an anchor-transformation pair to predictions for the target task. We instantiate RTE across multiple task extrapolation regimes in function prediction, e.g. where target tasks use out-of-range parameters (parameter extrapolation), have greater compositional depth (length extrapolation), and/or recombine function primitives in unseen ways (compositional extrapolation). We further extend RTE to sequence prediction, integrating it into fine-tuning algorithms for foundation models. Across empirical studies, we find that RTE substantially outperforms existing approaches on extrapolation to novel, unseen tasks.

Adam Ousherovitch, Yixin Wang

Department of Statistics, University of Michigan, Ann Arbor.

OOD GeneralizationCompositional Generalization
AskPDF
May 27, 2026

On Compositional Learning Behaviours in Formal Mathematics

Self-evolving scientific agents capable of conquering the hard tail of formal mathematics require Compositional Learning Behaviours (CLBs) -- the capacity to ground and recombine novel symbolic structures in context, beyond mere recombination of prelearned atoms. We propose S2B-LM, an adaptation of the CLB-evaluating Symbolic Behaviour Benchmark that removes numerical processing as a confound and adds chain-of-thought scaffolding to elicit rather than merely probe latent CLB competency. Cross-evaluating ten Lean~4 theorem provers on CLB competency in S2B-LM and miniF2F whole-proof performance, we find correlational and causal evidence of our claim: First, a necessary-condition analysis via quadrant test yields p=0.004p=0.004, with model scale being ruled out as a confound. Second, extracting a CLB-encoding activation direction from DeepSeek-Prover-V2-7B using S2B-LM traces via Contrastive Activation Addition and applying it during miniF2F whole-proof generation on the AIME subset, CLB suppression collapses solve rate from 32.3%32.3\% to 2.9%2.9\%, without loss of coherence, while suppressing a random activation direction of equal magnitude leaves it at 31.9%31.9\%. Together, these results show that CLB competency is necessary but not sufficient for the hard tail of formal mathematical verification.

Kevin Yandoka Denamganaï

University of York

Mathematical Reasoning BenchmarksFormal VerificationLean Theorem ProvingLLM Mathematical ReasoningCompositional Generalization
AskPDF
May 27, 2026

Compositional Generalization in Autoregressive Models via Logit Composition

Composing autoregressive models remains a core challenge in understanding how large language models can combine behaviors or skills learned across tasks. We introduce a new and principled composition strategy for autoregressive systems, inspired by composition methods developed for diffusion models. Under a factorized-conditionals assumption, we show that the resulting composition is projective: each component model preserves control over its own designated subspace of the output distribution avoiding interference between models. This property is further preserved under smooth reparameterizations of the output space, yielding a feature-space theorem. Finally, we show that composition preserves length-generalizing behavior when the factorization assumptions and component guarantees hold uniformly at the target length. These results provide a principled understanding of when model composition and merging succeed in autoregressive systems and identify conditions under which their interactions remain stable.

Aakash Kumar, Maria Sofia Bucarelli, Emanuele Natale

COATI, CNRS, Inria, I3S, Université Coté d’Azur, France

Language Model MergingCompositional GeneralizationAutoregressive Modeling
AskPDF
May 27, 2026

Learning Compositional Latent Structure with Vector Networks

Deep networks are powerful function approximators, but they typically store many different computations in shared weight matrices, making it difficult to selectively reuse or adapt parts of them when a familiar structure appears in novel combinations. We introduce the Vector Network (VN), a hierarchical recurrent architecture in which each layer replaces a fixed weight matrix with a library of reusable rank-1 weight atoms. For each input, VN minimizes a layer-local energy to infer a sparse set of active weight atoms and their coefficients, jointly constrained by bottom-up input reconstruction and top-down feedback consistency. These weight atom coefficients then compose an input-specific low-rank weight matrix for that sample. After convergence, slow learning updates only the selected weight atoms through local residual signals scaled by the inferred coefficients. We evaluate VN on four compositional benchmarks spanning 1D signals, 2D spatial decoding, N-body dynamics, and compositional MNIST. VN matches strong baselines in distribution while often achieving out-of-distribution error about an order of magnitude lower when familiar factors must be recombined in novel ways. Vector networks thus make compositional generalization a structural property of the architecture and inference process rather than a brittle byproduct of fitting many behaviors into one shared dense parameter substrate.

Niclas Pokel, Benjamin F. Grewe

Institute of Neuroinformatics, UZH / ETH Zurich ETH AI Center Zurich, Switzerland

Representation LearningRecurrent Neural NetworksSparse CodingCompositional Representation LearningCompositional GeneralizationModular Neural Networks
AskPDF
May 21, 2026

What Does the Caption Really Say? Counterfactual Phrase Intervention for Compositional Data Selection in Vision-Language Pretraining

CLIP-style contrastive pretraining typically curates web-scale image-text pairs using sample-level filtering signals, often based on pair-level alignment. We show that this signal saturates: once coarse mismatches are removed, stricter global filtering no longer tracks the compositional supervision provided by the retained captions. The reason is structural - a global score conflates whether a pair is broadly plausible with whether the individual object, attribute, and relation phrases inside the caption materially support the image-text match. The latter is what compositional generalization demands, yet pair-level filters are blind to it. We address this with Counterfactual Phrase Intervention (CPI), a phrase-level curation framework that converts controlled nonce-token substitutions into image-conditioned phrase-sensitivity scores. CPI uses global alignment only for coarse mismatch removal, then ranks the surviving pool by whether caption phrases measurably affect the image-text score under controlled substitution. We frame CPI as a first-order phrase-sensitivity signal rather than a grounding or identification result, and evaluate it at CC3M scale. Ranking by this signal yields a 50%-data subset that improves VL-CheckList-VG Relation by +1.91 over the full-data baseline and +1.00 over alignment-only filtering at matched budget, while improving SugarCrepe overall and preserving general transfer. CPI is loss-orthogonal: applied unchanged to NegCLIP, it further improves VL-CheckList-VG Relation by +3.84, with additional CE-CLIP gains in the main text.

Hyejin Go, Semi Lee, Hyesong Choi

Soongsil University Seoul, Republic of Korea

Training Data SelectionVision-Language PretrainingCompositional Generalization
AskPDF
May 21, 2026

Factored Diffusion Policies:Compositionally Generalized Robot Control with a Single Score Network

Robotic tasks are typically specified by a tuple of factors, such as the object to be grasped, the obstacles to be avoided, the color of the target, and so on. Collecting expert demonstrations for every combination of factor values grows combinatorially. We present factored diffusion policies: a single shared diffusion network trained with per-factor null-token dropout, whose score decomposes additively across factors at inference. Under approximate conditional independence between factors given the action-observation pair, this composition approximates the true joint score with a bounded uniform error, reducing the training-task budget from a product of factor cardinalities to a sum. A trajectory-tube certificate chains this score-level bound through the reverse-time sampling ODE and a contracting tracking controller into a closed-loop state-trajectory tube whose radius factors into an ODE-sensitivity constant and a per-factor score-error budget. Unlike compositional-diffusion methods for control that combine separately trained networks, we use one shared network. Drone racing experiments confirm both the generalization bound and the certificate. On state-based multi-gate racing, the factored policy passes 90% of held-out gates -- matching an oracle -- while a K-network composition baseline collapses to 3%; on vision-based single-gate traversal, it transfers zero-shot to an unseen venue with +11.7pp success-rate gain and 2.4X crash-rate reduction.

Sayan Mitra, Ege Yuceel, Noah Giles +1

University of Illinois Urbana-Champaign

Robotic ControlAutonomous Drone RacingDiffusion PolicyData-Efficient Robot LearningRobot Policy GeneralizationPolicy Learning+1
AskPDF
May 15, 2026

Decomposed Vision-Language Alignment for Fine-Grained Open-Vocabulary Segmentation

Open-vocabulary segmentation models often struggle to generalize to unseen combinations of object categories and attributes, because fine-grained descriptions are typically encoded as holistic sentences that entangle multiple semantic units. We propose a Decomposed Vision-Language Alignment framework that explicitly factorizes textual prompts into a concept token and multiple attribute tokens, enabling separate cross-modal interactions for each semantic unit. At the feature level, we introduce a Feature-Gated Cross-Attention module that generates attribute-specific gating maps to fuse information in a multiplicative manner, effectively enforcing compositional semantics. At the scoring level, per-token similarities are aggregated in log-space, producing a stable and interpretable compositional matching. The method can be seamlessly integrated into existing transformer-based segmentation architectures and significantly improves generalization to unseen attribute-category compositions in fine-grained open-vocabulary segmentation benchmarks.

Chenhao Wang, Yingrui Ji, Yu Meng +1

Aerospace Information Research Institute, Chinese Academy of Sciences · University of Chinese Academy of Sciences · Zhejiang University

Image SegmentationOpen-Vocabulary Semantic SegmentationVision-Language AlignmentSemantic SegmentationCompositional GeneralizationFine-Grained Semantic Segmentation
AskPDF
May 15, 2026

GiLT: Augmenting Transformer Language Models with Dependency Graphs

Augmenting Transformers with linguistic structures effectively enhances the syntactic generalization performance of language models. Previous work in this direction focuses on syntactic tree structures of languages, in particular constituency tree structures. We propose Graph-Infused Layers Transformer Language Model (GiLT) which leverages dependency graphs for augmenting Transformer language models. Unlike most previous work, GiLT does not insert extra structural tokens in language modeling; instead, it injects structural information into language modeling by modulating attention weights in the Transformer with features extracted from the dependency graph that is incrementally constructed along with token prediction. In our experiments, GiLT with semantic dependency graphs achieves better syntactic generalization while maintaining competitive perplexity in comparison with Transformer language model baselines. In addition, GiLT can be finetuned from a pretrained language model to achieve improved downstream task performance. Our code is released at https://github.com/cookie-pie-oops/GiLT-LM.

Tianyu Huang, Yida Zhao, Chuyan Zhou +1

School of Information Science and Technology, ShanghaiTech University · Shanghai Engineering Research Center of Intelligent Vision and Imaging

TransformerLanguage ModelingCompositional Generalization
AskPDF
May 14, 2026

XDomainBench: Diagnosing Reasoning Collapse in High-Dimensional Scientific Knowledge Composition

Large Language Models (LLMs) are increasingly deployed for knowledge synthesis, yet their capacity for compositional generalization in scientific knowledge remains under-characterized. Existing benchmarks primarily focus on single-turn restricted scenarios, failing to capture the capability boundaries exposed by real-world interactive scientific workflows. To address this, we introduce XDomainBench, a diagnostic benchmark for interactive interdisciplinary scientific reasoning. We formalize the composition order and mixture structure to enable systematic stress-testing from single-discipline to inter-disciplinary, comprising 8,598 interactive sessions across 20 domains and 4 task categories, with 8 realistic trajectory patterns covering difficulty and domain-mixture dynamics, simulating real AI4S scenarios. Large-scale evaluation of LLMs reveals a systematic reasoning collapse as composition order increases, stemming from two root causes: (i) direct difficulty increases induced by domain composition, and (ii) indirect interaction-amplified failures where trajectory patterns trigger error accumulation, reasoning breaks, and domain confusion, ultimately leading to session collapse.

Gong Zhiren, Tiantong Wu, Jiaming Zhang +9

College of Computing and Data Science, Nanyang Technological University, Singapore · Interdisciplinary Graduate Programme, Nanyang Technological University, Singapore · Department of Mathematics and Mathematical Statistics, Umeå University, Sweden +2

AI for ScienceLLM EvaluationScientific ReasoningAI Agent BenchmarksCompositional Generalization
AskPDF
May 13, 2026

KamonBench: A Grammar-Based Dataset for Evaluating Compositional Factor Recovery in Vision-Language Models

Kamon (family crests) are an important part of Japanese culture and a natural test case for compositional visual recognition: each crest combines a small number of symbolic choices, but the space of possible descriptions is sparse. We introduce KamonBench, a grammar-based image-to-structure benchmark with 20,000 synthetic composite crests and auxiliary component examples. Each composite crest is paired with a formal kamon description language - "kamon yōgo" - description, a segmented Japanese analysis, an English translation, and a non-linguistic program code. Because each synthetic crest is generated from known factors, namely container, modifier, and motif, KamonBench supports evaluation beyond caption-level accuracy: direct program-code factor metrics, controlled factor-pair recombination splits, counterfactual motif-sensitivity groups under fixed container-modifier contexts, and linear probes of factor accessibility. We include baseline results for a ViT encoder/Transformer decoder and two VGG n-gram decoders, with and without learned positional masks. KamonBench therefore provides a controlled testbed for sparse compositional visual recognition and factor recovery in vision-language models.

Richard Sproat, Stefano Peluchetti

VLM EvaluationCompositional Generalization
AskPDF
May 12, 2026

Unlocking Compositional Generalization in Continual Few-Shot Learning

Object-centric representations promise a key property for few-shot learning: Rather than treating a scene as a single unit, a model can decompose it into individual object-level parts that can be matched and compared across different concepts. In practice, this potential is rarely realized. Continual learners either collapse scenes into global embeddings, or train with part-level matching objectives that tie representations too closely to seen patterns, leaving them unable to generalize to truly novel concepts. In this paper, we identify this fundamental structural conflict and pioneer a new paradigm that strictly decouples representation learning from compositional inference. Leveraging the inherent patch-level semantic geometry of self-supervised Vision Transformers (ViTs), our framework employs a dual-phase strategy. During training, slot representations are optimized entirely toward holistic class identity, preserving highly generalizable, object-level geometries. At inference, preserved slots are dynamically composed to match novel scenes. We demonstrate that this paradigm offers dual structural benefits: The frozen backbone naturally prevents representation drift, while our lightweight, holistic optimization preserves the features' capacity for novel-concept transfer. Extensive experiments validate this approach, achieving state-of-the-art unseen-concept generalization and minimal forgetting across standard continual learning benchmarks.

Phu-Quy Nguyen-Lam, Phu-Hoa Pham, Dao Sy Duy Minh +3

Faculty of Information Technology, University of Science, Vietnam National University, Ho Chi Minh City, Vietnam. · Department of Computer Science, University of Warwick, Coventry, United Kingdom.

Object-Centric Representation LearningFew-Shot LearningCompositional Generalization
AskPDF
May 9, 2026

Benchmarking Compositional Generalisation for Machine Learning Interatomic Potentials

Machine Learning Interatomic Potentials play a fundamental role in computational chemistry and materials science, enabling applications from molecular dynamics simulations to drug design and materials discovery. While recent approaches can estimate inter-atomic forces with high precision, it remains unclear to what extent they can generalise to previously unseen molecules. Do they learn the compositional structure of chemistry, capturing how molecular fragments and their combinations determine properties, or do they primarily learn to interpolate patterns that are specific to the training examples? To address this question, we propose a benchmark consisting of four tasks that require some form of compositional generalisation. In each task, models are tested on molecules that were unseen during training, but the training data is chosen such that generalisation to the test examples should be feasible for models that learn the underlying physical principles. Our empirical analysis shows that the considered tasks are highly challenging for state-of-the-art models, with errors on out-of-distribution examples often an order of magnitude higher than on in-distribution examples, even when using foundation models that have been pre-trained on millions of molecules.

Amir Masoud Nourollah, Irtaza Khalid, Stefano Leoni +1

Cardiff University, Cardiff, CF10 3AT, UK

Machine Learning Interatomic PotentialsOOD GeneralizationMolecular Property PredictionCompositional Generalization
AskPDF
May 8, 2026

When Symbol Names Should Not Matter: A Logistic Theory of Fresh-Symbol Classification

Template tasks have emerged as a clean testbed for asking whether transformers reason with abstract symbols rather than concrete token names. We study the fixed-label classification version of this problem, where train and test examples share latent templates but may use disjoint vocabularies. Unlike next-token prediction, the model need not emit unseen symbols; it must learn a decision rule invariant to symbol renaming. We analyze regularized kernel logistic classification in the transformer-kernel regime. Our main result decomposes the learned predictor into an ideal template-level classifier and a finite-sample perturbation caused by accidental token overlaps in the training data. We encode these overlaps by a colored collision graph and prove high-probability margin-transfer guarantees for fresh-symbol classification. This perspective extends template-based analyses to logistic classification and refines scalar diversity conditions: vocabulary size controls the average rate of collisions, but collision geometry controls whether the ideal classification margin is preserved. More broadly, the same perturbation framework applies to abstraction-augmented inputs, yielding a general margin-versus-collision criterion for identifying when prompting strategies improve fresh-symbol generalization. Synthetic template experiments illustrate the predicted roles of regularization, sample size, and transformer-kernel structure.

Wenjie Guan, Jelena Bradic

Department of Statistics and Data Science, Cornell University

TransformerClassificationKernel MethodsInvariant Representation LearningCompositional Generalization
AskPDF
May 8, 2026

Test-Time Compositional Generalization in Diffusion Models via Concept Discovery

Compositional generalization requires models to produce novel configurations from familiar parts. In diffusion models, prior compositional generation methods typically assume that the relevant concepts or conditioning signals are already available. We instead ask whether a pretrained diffusion model can discover query-specific concepts from the time-indexed scores it learns for the noisy marginals pt(xt)p_t(x_t) and compose them at test time. Given a single out-of-distribution query, our method performs gradient ascent on sθ(xt,t)≈∇xtlog⁡pt(xt)s_θ(x_t,t) \approx \nabla_{x_t}\log p_t(x_t) at multiple noising timesteps to recover local density modes, maps these modes into clean-space Gaussians, greedily selects relevant prototypes with a submodular likelihood objective, and combines them into a product-of-experts (PoE) teacher model with an analytic score. This teacher model can be sampled directly through classifier-free guidance or used to generate a sample pool for training a new class embedding and low-rank adapter. On held-out composition benchmarks built from ColorMNIST and CelebA, both the analytic PoE sampler and the low-rank adapted model outperform query-only and nearest trained-class baselines. These results suggest that the time-indexed score geometry of the diffusion model contains reusable density-mode concepts that support test-time compositional generation without a predefined concept library.

Zekun Wang, Anant Gupta, Tianyi Zhu +1

Georgia Institute of Technology · University of Virginia

Test-Time AdaptationCompositional Image GenerationCompositional GeneralizationDiffusion Models
AskPDF
May 6, 2026

Reinforcement Learning for Compositional Generalization with Outcome-Level Optimization

Compositional generalization refers to correctly interpret novel combinations of known primitives, which remains a major challenge. Existing approaches often rely on supervised fine-tuning, which encourages models to imitate target outputs. This token-level training paradigm fails to capture the global compositional structure required for generalizing to unseen combinations. In this work, we investigate whether compositional generalization can instead be improved through outcome-level reinforcement learning. We adopt Group Relative Policy Optimization to optimize models based on feedback on their final outputs. Within this framework, we explore both a simple binary outcome reward and a composite reward that provides additional composition feedback. Experiments on multiple compositional benchmarks show that reinforcement learning improves compositional generalization compared to supervised fine-tuning. Further analysis reveals that supervised models tend to overfit frequent training compositions, whereas reinforcement learning improves compositional generalization by reshaping the output distribution, particularly for more complex composition types.

Xiyan Fu, Wei Liu

Nanyang Technological University · Independent Researcher

Reinforcement LearningRL for Generative ModelsRL Fine-TuningCompositional Generalization
AskPDF
May 6, 2026

Critical Windows of Complexity Control: When Transformers Decide to Reason or Memorize

Recent work has shown that Transformers' compositional generalization is governed by complexity control, initialization scale and weight decay, which steers training toward low-complexity reasoning solutions rather than high-complexity memorization. Existing analyses, however, treat complexity control as a single static hyperparameter choice, leaving open when during training this control is actually decisive. We show that the memorization-versus-reasoning fate of a Transformer is determined within a sharp, identifiable window of training. On a controlled compositional task we find that (i)~weight decay applied for a single 25%-of-training window matches full-training weight decay in out-of-distribution (OOD) accuracy (0.930.93 vs 0.910.91); (ii)~holding total regularization budget constant, placing it in the middle of training yields 5−9×5{-}9\times higher OOD accuracy than placing it early; (iii)~the boundary of the critical window is remarkably sharp, window onset shifted by as little as 100100 optimization steps causes mean OOD to jump from chance (0.150.15) to reasoning-regime (0.610.61); (iv)~the window's position depends systematically on initialization scale, but the basin of attraction for reasoning solutions shrinks at small initialization, contradicting the prevailing recommendation that smaller initialization is uniformly better. We further show that the critical-window phenomenon is task-specific: it does not appear on grokking with modular arithmetic, where properly tuned constant weight decay matches scheduled weight decay.

Sarwan Ali

Columbia University, Irving Medical Center, NY, USA

Deep Learning OptimizationWeight DecayTransformer Training DynamicsOOD GeneralizationNeural Network Training DynamicsCompositional Generalization
AskPDF
May 3, 2026

Towards Systematic Generalization for Power Grid Optimization Problems

AC Optimal Power Flow (ACOPF) and Security-Constrained Unit Commitment (SCUC) are fundamental optimization problems in power system operations. ACOPF serves as the physical backbone of grid simulation and real-time operation, enforcing nonlinear power flow feasibility and network limits, while SCUC represents a core market-level decision process that schedules generation under operational and security constraints. Although these problems share the same underlying transmission network and physical laws, they differ in decision variables and temporal coupling, and prior learning-based approaches address them in isolation, resulting in disjoint models and representations.We propose a learning framework that jointly models ACOPF and SCUC through a shared graph-based backbone that captures grid topology and physical interactions, coupled with task-specific decoders for static and temporal decision-making. Training includes solver supervision with physics-informed objectives to enforce AC feasibility and inter-temporal operational constraints. To evaluate generalization, we assess cross-case transfer on unseen grid topologies for ACOPF and SCUC without retraining, and systematic generalization on the UC-ACOPF problem using unsupervised, physics-based objectives and a power-dispatch consensus mechanism. Experiments across multiple grid scales demonstrate improved performance and transferability relative to existing learning-based baselines, indicating that the model can support learning across heterogeneous power system optimization problems.

Zeeshan Memon, Yijiang Li, Hongwei Jin +2

Emory University Atlanta, GA, USA · Argonne National Laboratory Lemont, IL, USA

Optimal Power FlowConstrained OptimizationCompositional GeneralizationPower Systems
AskPDF
May 1, 2026

Reconstructing conformal field theoretical compositions with Transformers

We study the use of transformers to reconstruct the compositions of tensor products of two-dimensional rational conformal field theories (RCFTs) based on their low-energy spectra. The task is challenging due to its combinatorial nature. The constituent theories are characterized by their central charges and affine Lie algebra labels. We achieve 98% accuracy in recovering the constituents of tensor products theories constructed from Wess-Zumino-Witten models. We further demonstrate that our method generalizes to CFTs with larger central charge and unseen classes of RCFTs by adding a small number of out-of-domain examples. Our results show that transformers are effective at this task and point towards a new tool for bulk reconstruction in AdS/CFT.

Haotian Cao, Garrett Merz, Kyle Cranmer +1

a Department of Physics, University of Wisconsin-Madison · b Data Science Institute, University of Wisconsin-Madison

Compositional Generalization
AskPDF
Apr 30, 2026

When Do Diffusion Models learn to Generate Multiple Objects?

Text-to-image diffusion models achieve impressive visual fidelity, yet they remain unreliable in multi-object generation. Despite extensive empirical evidence of these failures, the underlying causes remain unclear. We begin by asking how much of this limitation arises from the data itself. To disentangle data effects, we consider two regimes across different dataset sizes: (1) concept generalization, where each individual concept is observed during training under potentially imbalanced data distributions, and (2) compositional generalization, where specific combinations of concepts are systematically held out. To study these regimes, we introduce mosaic (Multi-Object Spatial relations, AttrIbution, Counting), a controlled framework for dataset generation. By training diffusion models on mosaic, we find that scene complexity plays a dominant role rather than concept imbalance, and that counting is uniquely difficult to learn in low-data regimes. Moreover, compositional generalization collapses as more concept combinations are held out during training. These findings highlight fundamental limitations of diffusion models and motivate stronger inductive biases and data design for robust multi-object compositional generation.

Yujin Jeong, Arnas Uselis, Iro Laina +2

TU Darmstadt & hessian.AI · University of Tübingen · Visual Geometry Group, University of Oxford +1

T2I GenerationCompositional Image GenerationGenerative ModelingT2I Diffusion ModelsCompositional Generalization
AskPDF
Apr 30, 2026

Investigating More Explainable and Partition-Free Compositionality Estimation for LLMs: A Rule-Generation Perspective

Compositional generalization tests are often used to estimate the compositionality of LLMs. However, such tests have the following limitations: (1) they only focus on the output results without considering LLMs' understanding of sample compositionality, resulting in explainability defects; (2) they rely on dataset partition to form the test set with combinations unseen in the training set, suffering from combination leakage issues. In this work, we propose a novel rule-generation perspective for compositionality estimation for LLMs. It requires LLMs to generate a program as rules for dataset mapping and provides estimates of the compositionality of LLMs using complexity-based theory. The perspective addresses the limitations of compositional generalization tests and provides a new way to analyze the compositionality characterization of LLMs. We conduct experiments and analysis of existing advanced LLMs based on this perspective on a string-to-grid task, and find various compositionality characterizations and compositionality deficiencies exhibited by LLMs.

Ziyao Xu, Cong Wang, Houfeng Wang

National Key Laboratory for Multimedia Information Processing, School of Computer Science, Peking University · OPPO AI Center

Compositional Generalization
AskPDF
Apr 29, 2026

AGEL-Comp: A Neuro-Symbolic Framework for Compositional Generalization in Interactive Agents

Large Language Model (LLM)-based agents exhibit systemic failures in compositional generalization, limiting their robustness in interactive environments. This work introduces AGEL-Comp, a neuro-symbolic AI agent architecture designed to address this challenge by grounding actions of the agent. AGEL-Comp integrates three core innovations: (1) a dynamic Causal Program Graph (CPG) as a world model, representing procedural and causal knowledge as a directed hypergraph; (2) an Inductive Logic Programming (ILP) engine that synthesizes new Horn clauses from experiential feedback, grounding symbolic knowledge through interaction; and (3) a hybrid reasoning core where an LLM proposes a set of candidate sub-goals that are verified for logical consistency by a Neural Theorem Prover (NTP). Together, these components operationalize a deduction--abduction learning cycle: enabling the agent to deduce plans and abductively expand its symbolic world model, while a neural adaptation phase keeps its reasoning engine aligned with new knowledge. We propose an evaluation protocol within the Retro Quest simulation environment to probe for compositional generalization scenarios to evaluate our AGEL agent. Our findings clearly indicate the better performance of our AGEL model over pure LLM-based models. Our framework presents a principled path toward agents that build an explicit, interpretable, and compositionally structured understanding of their world.

Mahnoor Shahid, Hannes Rothe

Universität Duisburg-Essen, Essen, Germany

Neuro-Symbolic AIInductive Logic ProgrammingLLM Agent PlanningCompositional Generalization
AskPDF
Apr 29, 2026

Grounding vs. Compositionality: On the Non-Complementarity of Reasoning in Neuro-Symbolic Systems

Compositional generalization remains a foundational weakness of modern neural networks, limiting their robustness and applicability in domains requiring out-of-distribution reasoning. A central, yet unverified, assumption in neuro-symbolic AI is that compositional reasoning will emerge as a byproduct of successful symbol grounding. This work presents the first systematic empirical analysis to challenge this assumption by disentangling the contributions of grounding and reasoning. To operationalize this investigation, we introduce the Iterative Logic Tensor Network (iiLTN), a fully differentiable architecture designed for multi-step deduction. Using a formal taxonomy of generalization -- probing for novel entities, unseen relations, and complex rule compositions -- we demonstrate that a model trained solely on a grounding objective fails to generalize. In contrast, our full iiLTN, trained jointly on perceptual grounding and multi-step reasoning, achieves high zero-shot accuracy across all tasks. Our findings provide conclusive evidence that symbol grounding, while necessary, is insufficient for generalization, establishing that reasoning is not an emergent property but a distinct capability that requires an explicit learning objective.

Mahnoor Shahid, Hannes Rothe

Universität Duisburg Essen, Germany

Tensor NetworksLogical ReasoningLogic Tensor NetworksNeuro-Symbolic ReasoningCompositional Generalization
AskPDF
Apr 28, 2026

Structural Generalization on SLOG without Hand-Written Rules

Structural generalization in semantic parsing requires systems to apply learned compositional rules to novel structural combinations. Existing approaches either rely on hand-written algebraic rules (AM-Parser) or fail to generalize structurally (Transformer-based models). We present an alternative requiring no hand-written compositional rules, based on a neural cellular automaton (NCA) with a discrete bottleneck: all compositional rules are learned from data through local iteration. On the SLOG benchmark, the system achieves an overall accuracy of 67.3±0.2%67.3 \pm 0.2\% across 10 seeds (AM-Parser: 70.8±4.3%70.8 \pm 4.3\%), with 11 of 17 structural generalization categories at 100%100\% type-exact match, including three where AM-Parser scores 00--74%74\%. Analysis reveals that all 5,539 failure instances reduce to exactly two mechanisms: novel combinations of wh-extraction context with reduced verb types, and modifiers appearing on the subject side of verbs. When we decompose results by CCG structural features, each sub-pattern either succeeds on all instances or fails on all. Intermediate scores (e.g., 41.4%41.4\%) are mixtures of structurally distinct CCG patterns, not partial generalization. These results suggest that CCG directed types provide higher resolution than SLOG's phenomenon-level categories for characterizing structural generalization, and that the success/failure boundary is determined by the coverage of directed operations in the training data.

Zichao Wei

Saarland University

Neural Cellular AutomataSemantic ParsingCompositional Generalization
AskPDF
Apr 23, 2026

To See the Unseen: on the Generalization Ability of Transformers in Symbolic Reasoning

We investigate the ability of decoder-only transformer models to perform abstract symbolic reasoning; specifically solving propositional logic reasoning problems given in-context. Previous work demonstrated that models fail to generalize to problems involving variable names that were not observed during training, and it was shown that one reason behind this is the difficulty of copying (or generating) unseen tokens. We show both theoretically and empirically that a particular representational collapse also has a crucial role: the unembeddings (last-layer weights) of unseen tokens collapse to nearly the same vector during training. The collapse makes distinguishing multiple unseen variables difficult for the model (especially when the embedding and unembedding parameters are shared), and provides a mechanistic explanation for the effectiveness of existing heuristic interventions like "active forgetting", which periodically reset the token (un)embeddings. Based on these observations, we devise a combination of techniques, involving a small architecture change facilitating copying, data diversity, and freezing or resetting (un)embeddings, that achieves generalization to unseen tokens. We support our claims with extensive controlled experiments on propositional logic reasoning problems. Beyond synthetic experiments, we also observe evidence of (un)embedding collapse in the open-weight models in the Gemma 3 family, which includes 99 unused tokens reserved for downstream use. Empirically we find that the correlated embeddings of these tokens are a poor initialization for finetuning applications.

Nevena Lazić, Liam Fowl, András György +1

Logical ReasoningDecoder-Only Language ModelsSymbolic ReasoningCompositional GeneralizationLLM Reasoning
AskPDF
Apr 22, 2026

Diagnosing CFG Interpretation in LLMs

As LLMs are increasingly integrated into agentic systems, they must adhere to dynamically defined, machine-interpretable interfaces. We evaluate LLMs as in-context interpreters: given a novel context-free grammar, can LLMs generate syntactically valid, behaviorally functional, and semantically faithful outputs? We introduce RoboGrid, a framework that disentangles syntax, behavior, and semantics through controlled stress-tests of recursion depth, expression complexity, and surface styles. Our experiments reveal a consistent hierarchical degradation: LLMs often maintain surface syntax but fail to preserve structural semantics. Despite the partial mitigation provided by CoT reasoning, performance collapses under structural density, specifically deep recursion and high branching, with semantic alignment vanishing at extreme depths. Furthermore, "Alien" lexicons reveal that LLMs rely on semantic bootstrapping from keywords rather than pure symbolic induction. These findings pinpoint critical gaps in hierarchical state-tracking required for reliable, grammar-agnostic agents.

Hanqi Li, Lu Chen, Kai Yu

1X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · 3Shanghai Innovation Institution, Shanghai, China · 4Jiangsu Key Lab of Language Computing, Suzhou, China +2

LLM EvaluationIn-Context LearningLLM Agent ReliabilityCompositional Generalization
AskPDF
Apr 20, 2026

Gradient-Based Program Synthesis with Neurally Interpreted Languages

A central challenge in program induction has long been the trade-off between symbolic and neural approaches. Symbolic methods offer compositional generalisation and data efficiency, yet their scalability is constrained by formalisms such as domain-specific languages (DSLs), which are labour-intensive to create and may not transfer to new domains. In contrast, neural networks flexibly learn from data but tend to generalise poorly in compositional and out-of-distribution settings. We bridge this divide with an instance of a Latent Adaptation Network architecture named Neural Language Interpreter (NLI), which learns its own discrete, symbolic-like programming language end-to-end. NLI autonomously discovers a vocabulary of primitive operations and uses a novel differentiable neural executor to interpret variable-length sequences of these primitives. This allows NLI to represent programs that are not bound to a constant number of computation steps, enabling it to solve more complex problems than those seen during training. To make these discrete, compositional program structures amenable to gradient-based optimisation, we employ the Gumbel-Softmax relaxation, enabling the entire model to be trained end-to-end. Crucially, this same differentiability enables powerful test-time adaptation. At inference, NLI's program inductor provides an initial program guess. This guess is then refined via gradient descent through the neural executor, enabling efficient search for the neural program that best explains the given data. We demonstrate that NLI outperforms in-context learning, test-time training, and continuous latent program networks on tasks that require combinatorial generalisation and rapid adaptation to unseen tasks. Our results establish a new path toward models that combine the compositionality of discrete languages with the gradient-based search and end-to-end learning of neural networks.

Matthew V. Macfarlane, Clément Bonnet, Herke van Hoof +1

AMLab, University of Amsterdam · Work completed while a visiting student at the University of Alberta. · Ndea +2

Program SynthesisDifferentiable ProgrammingCompositional Generalization
AskPDF
Apr 16, 2026

Generalization in LLM Problem Solving: The Case of the Shortest Path

Whether language models can systematically generalize remains actively debated. Yet empirical performance is jointly shaped by multiple factors such as training data, training paradigms, and inference-time strategies, making failures difficult to interpret. We introduce a controlled synthetic environment based on shortest-path planning, a canonical composable sequential optimization problem. The setup enables clean separation of these factors and supports two orthogonal axes of generalization: spatial transfer to unseen maps and length scaling to longer-horizon problems. We find that models exhibit strong spatial transfer but consistently fail under length scaling due to recursive instability. We further analyze how distinct stages of the learning pipeline influence systematic problem-solving: for example, data coverage sets capability limits; reinforcement learning improves training stability but does not expand those limits; and inference-time scaling enhances performance but cannot rescue length-scaling failures.

Yao Tong, Jiayuan Ye, Anastasia Borovykh +1

National University of Singapore · Capital Fund Management · Google Research

Inference-Time ScalingLanguage Model GeneralizationLength GeneralizationCompositional Generalization
AskPDF
Apr 13, 2026

THEIA: Learning Complete Kleene Three-Valued Logic in a Pure-Neural Modular Architecture

We present THEIA, a 2.75M-parameter modular neural architecture that learns the complete Kleene three-valued logic (K3) truth table from task data without external symbolic inference or hand-encoded K3 gate primitives. Across 5 seeds it passes all 39 K3 rules at >99% per-rule accuracy. K3 learnability is not the central finding: Transformer baselines also pass all 39 rules, and flat MLPs match THEIA on Phase-1 accuracy within 0.04pp. The contributions are two properties of the learned system. (1) Uncertainty-verdict asymmetric propagation. THEIA preserves Has-Unknown at every upstream boundary (80.0/91.1/90.8/99.7% across Arith/Order/Set/Logic vs. ~52% majority) while final-verdict decodability stays at or below a 73.4% U-vs-non-U oracle reference under linear and nonlinear probes. Activation patching on non-absorbent T->U cases flips 4,898/4,898 OR and 4,719/4,719 AND pairs across 5 seeds, ruling out residual shortcuts. (2) Reliability spectrum under discretized end-to-end training, on tasks decomposable along the engine boundaries. A mod-3 sequential composition task generalizes from 5- to 500-step evaluation at 99.96+-0.04% (5 seeds). Under identical Gumbel-softmax training, flat MLPs collapse to chance by 50 steps; a 2x2 ResMLP grid reaches >=99% on only 3/20 (config, seed) trials; a pre-LN Transformer reaches 99.24+-0.34%. Straight-through discretization prevents 0.999^500 compounding; the architectural separator is sustaining Phase-1 accuracy under Phase-3 training, where flat MLPs fail. Auxiliary: under per-architecture development defaults (not optimizer-controlled), THEIA reaches 12/12 Kleene coverage 6.5x faster than a parameter-comparable 8L Transformer; this narrows to ~3.6x with Transformer-standard tuning and 4.93x with the same recipe on both. Ratios are config-specific, not asymptotic.

Augustus Haoyang Li

Irvine Valley College Irvine, CA, USA

Neural Network InterpretabilityCompositional GeneralizationModular Neural Networks
AskPDF
Apr 9, 2026

Loop, Think, & Generalize: Implicit Reasoning in Recurrent-Depth Transformers

We study implicit reasoning, i.e. the ability to combine knowledge or rules within a single forward pass. While transformer-based large language models store substantial factual knowledge and rules, they often fail to compose this knowledge for implicit multi-hop reasoning, suggesting a lack of compositional generalization over their parametric knowledge. To address this limitation, we study recurrent-depth transformers, which enables iterative computation over the same transformer layers. We investigate two compositional generalization challenges under the implicit reasoning scenario: systematic generalization, i.e. combining knowledge that is never used for compositions during training, and depth extrapolation, i.e. generalizing from limited reasoning depth (e.g. training on up to 5-hop) to deeper compositions (e.g. 10-hop). Through controlled studies with models trained from scratch, we show that while vanilla transformers struggle with both generalization challenges, recurrent-depth transformers can effectively make such generalization. For systematic generalization, we find that this ability emerges through a three-stage grokking process, transitioning from memorization to in-distribution generalization and finally to systematic generalization, supported by mechanistic analysis. For depth extrapolation, we show that generalization beyond training depth can be unlocked by scaling inference-time recurrence, with more iterations enabling deeper reasoning. We further study how training strategies affect extrapolation, providing guidance on training recurrent-depth transformers, and identify a key limitation, overthinking, where excessive recurrence degrades predictions and limits generalization to very deep compositions.

Harsh Kohli, Srinivasan Parthasarathy, Huan Sun +1

The Ohio State University

Position ExtrapolationImplicit Reasoning in Language ModelsCompositional GeneralizationRecurrent Transformers
AskPDF
Apr 7, 2026

Transformer See, Transformer Do: Copying as an Intermediate Step in Learning Analogical Reasoning

Analogical reasoning is a hallmark of human intelligence, enabling us to solve new problems by transferring knowledge from one situation to another. Yet, developing artificial intelligence systems capable of robust human-like analogical reasoning has proven difficult. In this work, we train transformers using Meta-Learning for Compositionality (MLC) on an analogical reasoning task (letter-string analogies) and assess their generalization capabilities. We find that letter-string analogies become learnable when guiding the models to attend to the most informative problem elements, induced by including copy tasks in the training data. Furthermore, generalization to new alphabets improves when models are trained with more heterogeneous datasets. For the best training run, our 3-layer encoder-decoder model performs on par with frontier models on our letter-string analogy datasets. The MLC approach also enables some generalization to compositions of trained transformations, but not to completely novel transformations. To understand how the model solves the analogies, we identify an algorithm for one analogy task that approximates the model's computations. We verify this using interpretability analyses and show that head-level attention weights causally affect model output, allowing steering between different analogy tasks. We discuss the implications of our findings for generalization capabilities of larger models and the parallels to human analogical reasoning.

Philipp Hellwig, Willem Zuidema, Claire E. Stevenson +1

Psychological Methods, University of Amsterdam · Institute for Logic, Language and Computation, University of Amsterdam

Analogical Reasoning for Language ModelsCompositional Generalization
AskPDF