Compositional structure appears at every natural scale: atoms form molecules, molecules form cells, cells form organisms, and similar hierarchies exist within each level. Compositionality—the reuse and recombination of parts into novel configurations—is a primary source of interesting complexity in both natural and artificial systems. Although we readily recognize such structure, a precise mathematical account has been lacking. This work formalizes a simple idea using algorithmic information theory: when several parts are considered together they reveal shared structure that is invisible when each part is modeled separately. The definition leverages information compression, requiring no prior specification of the form of the structure and thus can detect compositional patterns in arbitrary data. With tractable approximations we invert the framework to generate compositional objects: we prescribe the desired shape of the compositional structure without fixing its concrete content, and directly optimise over strings or images. The resulting objects display clear hierarchical reuse and part‑whole organization, indicating that the definition captures compositionality rather than mere complexity, regularity, or shared information. Finally, we discuss implications for machine learning, offering a new perspective on depth in neural networks and principles for building compositional data curricula that support open‑ended learning.
Review