mlsanityData to 14 Oct 2026

A General Theory for Compositional Generalization

arXiv 2405.11743 ↗First posted 20 May 2024cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Compositional Generalization (CG) embodies the ability to comprehend novel combinations of familiar concepts, representing a significant cognitive leap in human intellectual advancement. Despite its critical importance, the deep neural network (DNN) faces challenges in addressing the compositional generalization problem, prompting considerable research interest. However, existing theories often rely on task-specific assumptions, constraining the comprehensive understanding of CG. This study aims to explore compositional generalization from a task-agnostic perspective, offering a complementary viewpoint to task-specific analyses. The primary challenge is to define CG without overly restricting its scope, a feat achieved by identifying its fundamental characteristics and basing the definition on them. Using this definition, we seek to answer the question "what does the ultimate solution to CG look like?" through the following theoretical findings: 1) the first No Free Lunch theorem in CG, indicating the absence of general solutions; 2) a novel generalization bound applicable to any CG problem, specifying the conditions for an effective CG solution; and 3) the introduction of the generative effect to enhance understanding of CG problems and their solutions. This paper's significance lies in providing a general theory for CG problems, which, when combined with prior theorems under task-specific scenarios, can lead to a comprehensive understanding of CG.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 32 of its 63 references that are in the map. First posted on arXiv 20 May 2024.

Builds on

32 of 63 references.

References · 32

  1. 2020WILDS: A Benchmark of in-the-Wild Distribution Shiftscited by 1,375
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  3. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
  4. 2016The Option-Critic Architecturecited by 448
  5. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  6. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  7. 2017Neural Style Transfer: A Reviewcited by 199
  8. 2020Deep Learning for Text Style Transfer: A Surveycited by 162
  9. 2017Generalization in Deep Learningcited by 146
  10. 2017Implicit Regularization in Deep Learningcited by 90
  11. 2021Extending the WILDS Benchmark for Unsupervised Adaptationcited by 86
  12. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
20 more
  1. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 64
  2. 2023Compositional Generalization from First Principlescited by 64
  3. 2019Human few-shot learning of compositional instructionscited by 47
  4. 2021Improving Compositional Generalization with Latent Structure and Data Augmentationcited by 46
  5. 2023Provably Learning Object-Centric Representationscited by 45
  6. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  7. 2020Improving Compositional Generalization in Semantic Parsingcited by 42
  8. 2023Provable Compositional Generalization for Object-Centric Learningcited by 41
  9. 2022On the Compositional Generalization Gap of In-Context Learningcited by 24
  10. 2022First Steps Toward Understanding the Extrapolation of Nonlinear Models to Unseen Domainscited by 21
  11. 2021Solving Compositional Reinforcement Learning Problems via Task Reductioncited by 19
  12. 2023Learning to Extrapolate: A Transductive Approachcited by 19
  13. 2022The no-free-lunch theorems of supervised learningcited by 16
  14. 2023Improving Compositional Generalization Using Iterated Learning and Simplicial Embeddingscited by 15
  15. 2020What is important about the No Free Lunch theorems?cited by 9
  16. 2023Learning Trajectories are Generalization Indicatorscited by 5
  17. 2019Generativity and Interactional Effects: an Overviewcited by 3
  18. 2019On the Mathematical Structure of Cascade Effects and Emergent Phenomenacited by 1
  19. 2019On the Abstract Structure of the Behavioral Approach to Systems Theorycited by 1
  20. 2023Generalization error bounds for iterative learning algorithms with bounded updatescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Learning to Substitute Components for Compositional Generalizationcited by 1
  2. 2026Tool Use Reduces Depth-Induced Collapse in OOD Reasoningcited by 0
  3. 2026Generalization in LLM Problem Solving: The Case of the Shortest Pathcited by 0
  4. 2026Distributional Extrapolation for Interactionscited by 0