The Coverage Principle: A Framework for Understanding Compositional Generalization

• URL: http://arxiv.org/abs/2505.20278v1
• Date: Mon, 26 May 2025 17:55:15 GMT
• Title: The Coverage Principle: A Framework for Understanding Compositional Generalization
• Authors: Hoyeon Chang, Jinho Park, Hanseul Cho, Sohee Yang, Miyoung Ko, Hyeonbin Hwang, Seungpil Won, Dohaeng Lee, Youbin Ahn, Minjoon Seo,
• Abstract summary: We show that models relying primarily on pattern matching for compositional tasks cannot reliably generalize beyond substituting fragments that yield identical results when used in the same contexts.<n>We demonstrate that this framework has a strong predictive power for the generalization capabilities of Transformers.
• Score: 31.762330857169914
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language models excel at pattern matching, yet often fall short in systematic compositional generalization. We propose the coverage principle: a data-centric framework showing that models relying primarily on pattern matching for compositional tasks cannot reliably generalize beyond substituting fragments that yield identical results when used in the same contexts. We demonstrate that this framework has a strong predictive power for the generalization capabilities of Transformers. First, we derive and empirically confirm that the training data required for two-hop generalization grows at least quadratically with the token set size, and the training data efficiency does not improve with 20x parameter scaling. Second, for compositional tasks with path ambiguity where one variable affects the output through multiple computational paths, we show that Transformers learn context-dependent state representations that undermine both performance and interoperability. Third, Chain-of-Thought supervision improves training data efficiency for multi-hop tasks but still struggles with path ambiguity. Finally, we outline a \emph{mechanism-based} taxonomy that distinguishes three ways neural networks can generalize: structure-based (bounded by coverage), property-based (leveraging algebraic invariances), and shared-operator (through function reuse). This conceptual lens contextualizes our results and highlights where new architectural ideas are needed to achieve systematic compositionally. Overall, the coverage principle provides a unified lens for understanding compositional reasoning, and underscores the need for fundamental architectural or training innovations to achieve truly systematic compositionality.

Related papers

• Does Data Scaling Lead to Visual Compositional Generalization? [21.242714408660508]
  We find that compositional generalization is driven by data diversity, not mere data scale.<n>We prove this structure is key to efficiency, enabling perfect generalization from few observed combinations.
  arXiv  Detail & Related papers  (2025-07-09T17:59:03Z)
• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  We propose a novel structural entropy-guided probabilistic coding model, named SEPC.<n>We incorporate the relationship between latent variables into the optimization by proposing a structural entropy regularization loss.<n> Experimental results across 12 natural language understanding tasks, including both classification and regression tasks, demonstrate the superior performance of SEPC.
  arXiv  Detail & Related papers  (2024-12-12T00:37:53Z)
• When does compositional structure yield compositional generalization? A kernel theory [0.0]
  We present a theory of compositional generalization in kernel models with fixed, compositionally structured representations.<n>We identify novel failure modes in compositional generalization that arise from biases in the training data.<n>This work examines how statistical structure in the training data can affect compositional generalization.
  arXiv  Detail & Related papers  (2024-05-26T00:50:11Z)
• Hierarchical Invariance for Robust and Interpretable Vision Tasks at Larger Scales [54.78115855552886]
  We show how to construct over-complete invariants with a Convolutional Neural Networks (CNN)-like hierarchical architecture. With the over-completeness, discriminative features w.r.t. the task can be adaptively formed in a Neural Architecture Search (NAS)-like manner. For robust and interpretable vision tasks at larger scales, hierarchical invariant representation can be considered as an effective alternative to traditional CNN and invariants.
  arXiv  Detail & Related papers  (2024-02-23T16:50:07Z)
• Understanding and Constructing Latent Modality Structures in Multi-modal Representation Learning [53.68371566336254]
  We argue that the key to better performance lies in meaningful latent modality structures instead of perfect modality alignment. Specifically, we design 1) a deep feature separation loss for intra-modality regularization; 2) a Brownian-bridge loss for inter-modality regularization; and 3) a geometric consistency loss for both intra- and inter-modality regularization.
  arXiv  Detail & Related papers  (2023-03-10T14:38:49Z)
• Variational Cross-Graph Reasoning and Adaptive Structured Semantics Learning for Compositional Temporal Grounding [143.5927158318524]
  Temporal grounding is the task of locating a specific segment from an untrimmed video according to a query sentence. We introduce a new Compositional Temporal Grounding task and construct two new dataset splits. We argue that the inherent structured semantics inside the videos and language is the crucial factor to achieve compositional generalization.
  arXiv  Detail & Related papers  (2023-01-22T08:02:23Z)
• Learning to Generalize Compositionally by Transferring Across Semantic Parsing Tasks [37.66114618645146]
  We investigate learning representations that facilitate transfer learning from one compositional task to another. We apply this method to semantic parsing, using three very different datasets. Our method significantly improves compositional generalization over baselines on the test set of the target task.
  arXiv  Detail & Related papers  (2021-11-09T09:10:21Z)
• Dynamic Inference with Neural Interpreters [72.90231306252007]
  We present Neural Interpreters, an architecture that factorizes inference in a self-attention network as a system of modules. inputs to the model are routed through a sequence of functions in a way that is end-to-end learned. We show that Neural Interpreters perform on par with the vision transformer using fewer parameters, while being transferrable to a new task in a sample efficient manner.
  arXiv  Detail & Related papers  (2021-10-12T23:22:45Z)
• Meta-Learning to Compositionally Generalize [34.656819307701156]
  We implement a meta-learning augmented version of supervised learning. We construct pairs of tasks for meta-learning by sub-sampling existing training data. Experimental results on the COGS and SCAN datasets show that our similarity-driven meta-learning can improve generalization performance.
  arXiv  Detail & Related papers  (2021-06-08T11:21:48Z)
• Dual-constrained Deep Semi-Supervised Coupled Factorization Network with Enriched Prior [80.5637175255349]
  We propose a new enriched prior based Dual-constrained Deep Semi-Supervised Coupled Factorization Network, called DS2CF-Net. To ex-tract hidden deep features, DS2CF-Net is modeled as a deep-structure and geometrical structure-constrained neural network. Our network can obtain state-of-the-art performance for representation learning and clustering.
  arXiv  Detail & Related papers  (2020-09-08T13:10:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.