A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition

arXiv:2505.02627 · cs.LG, cs.AI · Submitted 2025-05-05 · Read on arXiv

cs.LG, cs.AI

Submitted: 2025-05-05

Updated: 2026-09-08

Code: https://github.com/yuanpeng16/tacg

License: http://creativecommons.org/licenses/by/4.0/

The gist: Compositional generalization the ability to systematically process novel combinations of known components is a hallmark of human intelligence; however, its theoretical foundation in neural networks

Terminology

Abstract

Compositional generalization the ability to systematically process novel combinations of known components 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.

Sources

Related papers