Research map / Label-efficient and robust learning / Recognition and long-tail
When does compositional structure yield compositional generalization? A kernel theory.
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.
Develops a kernel theory of compositional generalization showing compositionally structured kernel models are restricted to conjunction-wise additive functions, and identifies memorization leak and shortcut bias as failure modes validated in ConvNets, ResNets, and ViTs.
Problem
When and why compositionally structured (disentangled) representations yield compositional generalization to novel component combinations, given that empirical results on their benefit are inconsistent.
Approach
Shows that kernel models with compositionally structured representations can only implement conjunction-wise additive functions (summing values for each component combination seen in training), derives exact generalization constraints via representational salience, and identifies memorization leak and shortcut bias arising from training-data statistics.
Key results
- Kernel models with compositionally structured representations are restricted to conjunction-wise additive computations, so they cannot generalize transitive equivalence.
- On symbolic addition, the theory predicts a memorization leak where test predictions are scaled by m = p·S(1;2)/(1+(p-2)S(1;2)); ConvNets, ResNets and ViTs show this proportional compression.
- On context dependence CD-3, models with high context and full-conjunction salience fail (shortcut bias), with worse-than-chance accuracy in deep networks, while CD-1 and CD-2 generalize.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a compositionally structured kernel model on transitive equivalence | Kernel model · Transitive equivalence | generalization accuracy | Hurt |
| Use a compositionally structured kernel model on a conjunction-wise additive task | Kernel model · Symbolic addition | test prediction | Hurt |
| Increase single-component salience relative to two-component conjunction salience | Compositionally structured kernel model · Context dependence (CD-3) | accuracy: 100% or 0% accuracy | Hurt |
| Increase two-component conjunction salience relative to single-component salience | Compositionally structured kernel model · Context dependence (CD-3) | accuracy: 100% or 0% accuracy | Helped |
| Train deep networks on the largest held-out feature-combination split | ConvNets, ResNets, and Vision Transformers · Context dependence (CD-3) | accuracy | Hurt |
| Use a representation with higher salience for single components rather than two-component conjunctions | Randomly sampled representations · Context dependence (CD-3) | accuracy | Hurt |
| Use a representation with higher salience for two-component conjunctions rather than single components | Randomly sampled representations · Context dependence (CD-3) | accuracy | Helped |
| Increase the distance between the two image components | ConvNets, ResNets, and Vision Transformers · Symbolic addition (compositional generalization) | prediction slope | Helped |
| Increase the training set size | Deep networks · Symbolic addition (compositional generalization) | prediction slope | Helped |
| Change the split from interpolation to extrapolation | Deep networks · Symbolic addition (compositional generalization) | prediction slope | No clear effect |
| Use the extrapolation split rather than interpolation with p=4 | Deep networks · Symbolic addition (compositional generalization) | prediction slope | Hurt |
| Increase network depth in random ReLU networks | Random ReLU network · Representational salience | full-conjunction salience: S(C;C)\to 1 | Helped |
Surprising findings
- Compositionally structured kernel models cannot generalize transitive equivalence even though they can fit the training data, while transitive ordering can be solved.
- For ReLU networks, very deep random networks encode only the full conjunction, effectively acting as a look-up table.
Limitations
- Theory covers only kernel models (kernel regime) and does not give quantitative bounds for deep networks.
- Restricted to fixed compositionally structured representations and fixed-size categorical inputs; not tested on large language models.
- Deep network results only partially match theory (e.g., p=4 extrapolation exception).
Experimental setup
Datasets: MNIST CIFAR-10 DSprites
Benchmarks: symbolic addition context dependence (CD-1, CD-2, CD-3) transitive equivalence
Metrics: slope of test predictions vs ground truth accuracy MSE
Baselines: component-wise additive model ConvNet ResNet Vision Transformer
Builds on: neural tangent kernel random feature model disentangled representation learning
Closest papers by meaning
- Does Data Scaling Lead to Visual Compositional Generalization? (ICML 2025 · similarity 0.92)
- Scaling can lead to compositional generalization (NeurIPS 2025 · similarity 0.91)
- Scalable Evaluation and Neural Models for Compositional Generalization (NeurIPS 2025 · similarity 0.90)
- Compositional Generalization via Forced Rendering of Disentangled Latents (ICML 2025 · similarity 0.90)
- On the Statistical Mechanisms of Distributional Compositional Generalization (ICML 2025 · similarity 0.89)
- When and How Does CLIP Enable Domain and Compositional Generalization? (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.