Complexity Induction: Compositional Generalization via Structured Training Distortion

Compositional generalization$\unicode{x2013}$the ability to systematically process novel combinations of known components$\unicode{x2013}$is a hallmark of human intelligence; however, its theoretical foundation in neural networks is not yet well understood. This paper establishes a necessary and sufficient condition for provable compositional generalization, precisely characterizing its boundary. Conceptually, the condition consists of two principles: (i) structural alignment, where a model's computational graph aligns with a task's true compositional hierarchy, and (ii) unambiguous minimized representations, where each component encodes adequate but not redundant information on the training data. The result is fully proved and machine-verified in Lean 4 and holds even in few-shot and one-shot regimes. The necessity direction establishes that provable compositional generalization cannot circumvent these requirements, while the sufficiency direction yields a unified inductive bias that jointly governs architectural design, training data properties, and regularization strategies. Building on this condition, we develop an example algorithmic approach, illustrate it through a controlled minimal example, and further demonstrate the condition on the SCAN jump task. All conclusions are derived mathematically without reliance on empirical validation. Our work provides a theoretical characterization of provable compositional generalization.

Generalized Category Discovery (GCD) assigns unlabeled instances, mixed with labeled data, to known or novel categories, requiring human-like compositional reasoning: reusing primitives learned from known classes and deciding when new combinations imply new categories. Existing GCD methods operate on unstructured token features and struggle to extrapolate to novel compositions. We propose CoGe-GCD, which rethinks GCD through compositional generalization with two coupled stages. (i) Compositional Perception structures patch tokens by mapping them to a small vocabulary of primitives and refining token embeddings via competitive token-primitive assignment and information passing, yielding coherent groups for discovery. (ii) Generalizing Induction exploits the induced geometric structure and applies a structure-preserving calibration over spatial relations, maintaining probabilistic semantics while improving extrapolation to unseen primitive combinations. CoGe-GCD is implemented as an inductive-bias module between backbone and projection head, without modifying heads or losses, and can be plugged into diverse GCD frameworks. On standard benchmarks, it consistently improves all-class accuracy, unknown-class number estimation, and geometric quality, with marginal computational overhead. Code is available at https://github.com/lytang63/CoGe-GCD.

Systematic generalization remains a significant challenge in deep learning. In particular, combinatorial generalization - generalizing to new configurations of known factors of variation - is effortless for humans but difficult for standard neural architectures that rely on statistical correlations rather than explicit structural representations. We introduce a new architectural component that embeds structured inductive bias into deep learning: an attention mechanism operating over tensor-product representations (TPRs). Through controlled experiments on compositional tasks, we show that this TPR-attention mechanism outperforms existing architectural components in combinatorial generalization. These results highlight the value of integrating explicit compositional structure into neural attention and point toward a promising path for models capable of systematic generalization.