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

תקציר מקורי באנגליתarXiv:2505.02627v2 Announce Type: replace Abstract: 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-ve