Research map / Learning theory and algorithms / Kernels and regression theory

On the Statistical Mechanisms of Distributional Compositional Generalization

ICML 2025 · Learning theory and algorithms › Kernels and regression theory · approach: Statistical perspectives on generalization

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Statistically formulates distributional compositional generalization (DCG), proposing an invariant µ-measure for trade-off vs non-trade-off improvements and a generalization bound decoupling insufficient-data error from knowledge-composition error, with small GPT-2 toy experiments on synthetic sequence composition rules.

Problem

Understanding the statistical mechanisms behind distributional compositional generalization, i.e., whether methods transfer across DCG problems and which statistical properties govern a learning algorithm's ability to compose knowledge from support distributions to unseen target distributions.

Approach

Models the learning algorithm's inherent bias and adaptivity via mutual information between the predicted composition rule and the support distribution, defines an invariant µ-measure over all methods, and bounds CG error by a term combining mutual information I(f^S; T | P_S) with an incompatibility measure τ(T, A) between composition rule and learning algorithm.

Key results

• Across 10 learning-algorithm instances, GACC rises with adaptivity IA,β(T̃=T; P_S), e.g., from 0.605 at 0.073 to 0.776 at 0.564 (Table 1).
• Generalization-bound CG error (ours) is 0.271-0.372 for rule complexity 6-12, versus 0.622-0.701 for the Ben-David et al. (2010) bound (Table 2).
• Theory shows non-trade-off improvement requires adaptivity of the learning algorithm to data, and the bound is tractable across composition rules.

Measured effects reported in the paper

Surprising findings

• Under the Ben-David et al. bound comparison, the authors find neither bound is uniformly tighter; theirs is better only when the support set is large.

Limitations

• Analysis does not directly address specific real-world DCG problems; experiments are small synthetic toy settings.
• Bound relies on assumptions such as L-bounded error and solvability, and the Ben-David comparison is mixed.
• Mutual-information adaptivity measure is hard to estimate directly in practice.

Experimental setup

Datasets: synthetic composition-rule sequences (|A|=|B|=1000 words, 64 composition rules)

Benchmarks: synthetic DCG composition tasks

Metrics: average accuracy GACC CG error mutual information I(rule; support)

Baselines: Ben-David et al. (2010) bound

Builds on: PAC learning No Free Lunch theorem Ben-David et al. 2010 domain adaptation bound

Closest papers by meaning

• When does compositional structure yield compositional generalization? A kernel theory. (ICLR 2025 · similarity 0.89)
• Does Data Scaling Lead to Visual Compositional Generalization? (ICML 2025 · similarity 0.88)
• Compositional Risk Minimization (ICML 2025 · similarity 0.86)
• Scaling can lead to compositional generalization (NeurIPS 2025 · similarity 0.86)
• Swing-by Dynamics in Concept Learning and Compositional Generalization (ICLR 2025 · similarity 0.85)
• Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoning (ICLR 2026 · similarity 0.85)