A Formal Framework for Defining and Generating Compositional Structure

Summary

The paper develops a mathematical account of compositional structure, the reuse and recombination of parts into novel structures across scales. It defines compositionality as a situation in which parts considered together reveal shared structure that is not captured when the parts are modeled separately. The authors express this idea through algorithmic information theory, using information and compression to identify structure in arbitrary data without specifying its form in advance. The framework can be applied across scales to determine where and how compositional structure emerges within an object. Using tractable approximations, the authors invert the analysis to generate objects with a desired form of compositional structure while leaving their particular content unspecified. They optimize directly over strings and images, producing examples with recognizable hierarchical reuse and part-whole organization. The authors argue that these results distinguish the framework from measures of complexity, regularity, or shared information alone. They also discuss implications for machine learning, including a possible new view of depth in neural architectures and principles for building compositional data curricula that could support open-ended learning.