Overcoming the Compositional Generalization Gap

13 concepts12 papers1 proposal

Human intelligence possesses a remarkable ability: once we learn the meaning of "red cube" and "blue sphere," we instantly understand what a "blue cube" looks like, even if we have never seen one. This ability to combine familiar, discrete components into entirely novel configurations is known as compositional generalization.

Despite their massive scale, modern deep learning models routinely fail at this task. When a neural network encounters a novel combination of known attributes, actions, or objects, its performance drops precipitously. Instead of learning systematic rules, models tend to memorize statistical shortcuts present in their training data.

To solve this problem, researchers are shifting away from purely empirical benchmarks toward rigorous mathematical definitions of compositionality, while designing new architectures that move beyond standard feedforward processing.


The Diagnostic Problem: Exposing the Failure

For years, the machine learning community recognized compositional failure primarily as an intuitive, "know it when you see it" phenomenon. Early diagnostics in Visual Question Answering (VQA) revealed that models were fundamentally myopic. For instance, Agrawal et al. demonstrated that VQA models frequently "jump to conclusions" by relying heavily on language priors—such as answering "yes" to any question starting with "Is there a..."—rather than actually grounding their answers in the visual scene. When concepts were decoupled from their typical training contexts, the models collapsed.

To systematically expose these vulnerabilities, researchers developed increasingly complex benchmarks:

  • Spatio-Temporal Recombination: In video understanding, Ranjay Krishna introduced the AGQA benchmark (AGQA: A Benchmark for Compositional Spatio-Temporal Reasoning), which tests whether models can handle novel compositions of objects, actions, and relationships over time. The results showed a massive gap between machine performance and human-level understanding, proving that models overfit to specific temporal sequences.
  • Mathematical Reasoning: Lindström and Dan evaluated neuro-symbolic and pure neural architectures on CLEVR-Math, discovering that both paradigms struggle with attribute and length generalization. Instead of learning the underlying mathematical operations, the models simply memorized training patterns.
  • Massive-Scale Evaluation: To scale up these diagnostic insights, Taoudi-Benchekroun et al. developed COGITAO, a framework capable of generating millions of distinct visual reasoning tasks specifically designed to test systematic generalization.

The Theoretical Shift: Defining Compositionality Mathematically

While empirical benchmarks can identify when a model fails, they do not explain why certain architectures struggle while others succeed. To bridge this gap, recent work has focused on establishing a formal, mathematical foundation for compositionality.

In a pair of foundational papers, Ram et al. (and its extended abstract What makes Models Compositional? A Neuro-Symbolic Theoretical View (Extended Abstract)) addressed the lack of precise definitions by introducing a formal neuro-symbolic framework. The authors mapped out how a model's internal computation graph influences its generalization capacity. Crucially, Ram et al. introduced a metric called the Locus of Influence (LoI), which theoretically quantifies why standard sequence models, like Transformers and RNNs, struggle to generalize to complex, unseen structures. Their theory proves that a model's ability to generalize compositionally is strictly bounded by the structural complexity of its internal routing.

Standard Feedforward (Entangled)       Compositional Representation (Compressible)
     [Input: Blue Cube]                       [Input: Blue Cube]
            │                                        │
     ┌──────┴──────┐                          ┌──────┴──────┐
     ▼             ▼                          ▼             ▼
[Feature A]   [Feature B]                [Concept: Blue] [Concept: Cube]
     └──────┬──────┘                          └──────┬──────┘
            ▼                                        ▼
  [Prediction: Unknown]                    [Prediction: Blue Cube]

Taking an information-theoretic perspective, Elmoznino et al. proposed the concept of representational compositionality. The authors argue that a representation is truly compositional if it satisfies two conditions: it must be highly expressive, yet efficiently compressible via simple functions of its discrete parts. Without these explicit mathematical constraints, standard neural networks optimize for the training distribution by entangling features, making out-of-distribution generalization impossible. As Kim and Kim frame it, current architectures lack the deliberate, logical "System 2" reasoning required to dynamically adapt learned concepts to unfamiliar patterns.


Architectural Remedies: Moving Beyond Feedforward Processing

To achieve true compositional generalization, researchers are designing architectures that enforce structural decomposition, top-down feedback, or symbolic abstraction.

1. Inverting the Problem via Generative Decomposition

Standard classification models operate in a bottom-up fashion, mapping high-dimensional pixels directly to labels. This unconstrained mapping allows the network to rely on spurious correlations.

To counter this, Yao et al. proposed treating classification as an inverse problem using a customized Conditional Variational Autoencoder (c-VAE). Instead of guessing a label directly, the model decomposes an image into its constituent parts and attempts to reconstruct the input. By evaluating which combination of learned, independent components best reconstructs the image, the model naturally recognizes novel symbol combinations that baffle traditional networks.

2. Guided Counterstream Processing

Human vision does not rely solely on a single forward pass; it utilizes a continuous dialogue between low-level sensory inputs and high-level conceptual expectations.

Assif et al. replicated this mechanism using a counterstream processing architecture. The model iteratively refines its understanding of a scene by reconciling bottom-up visual data with top-down instructions. This recurrent feedback loop prevents the model from overfitting to static combinations, allowing it to dynamically isolate and compose objects, properties, and relations in novel contexts.

3. Symbolic Abstraction and Graph Reasoning

Another powerful approach is to explicitly separate the learning of parts from the learning of relations.

  • Bayesian Program Induction: Zhou and Lake demonstrated that human-like few-shot learning of visual concepts can be captured by modeling concepts as executable programs. By combining discrete primitives through probabilistic rules, their model generalizes seamlessly across novel compositional structures.
  • Cross-Graph Reasoning: In the domain of video and language grounding, Li et al. developed VISA (Variational Cross-Graph Reasoning) and ASSL (Adaptive Structured Semantics Learning). Their framework decomposes videos and text queries into hierarchical graphs. By performing reasoning over these structured graphs, the model mitigates the "semantic shift" that occurs when familiar words appear in entirely new visual configurations, ensuring robust combinatorial generalization.

Key Foundational Work

Analyzing the Behavior of Visual Question Answering Models (2016) — contributed 1 concept elements to this direction.
Image Decomposition and Classification through a Generative Model (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compositional_generalization_failure_7210f246,
  title = {compositional generalization failure},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-generalization-failure/rdr_7210f246cac147a4ac32f0fd3c35dd68},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_compositional_generalization_failure_7210f246_v1,
  title = {compositional generalization failure},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-generalization-failure/rdr_7210f246cac147a4ac32f0fd3c35dd68/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake