Compositional Generalization Requires Linear, Orthogonal Representations in Vision Embedding Models

Compositional generalization, the ability to recognize familiar parts in novel contexts, is a defining property of intelligent systems, yet modern models, despite massive training sets, see only a tiny fraction of the combinatorial input space. We ask what structure representations {must} have to support generalization to unseen combinations. We formalize three desiderata (divisibility, transferability, stability) and show they impose necessary geometric constraints under standard training: representations must decompose linearly into per-concept components, orthogonal across concepts. This grounds the Linear Representation Hypothesis as a necessary consequence of compositional generalization, and yields dimension bounds linking the number of composable concepts to embedding geometry. Empirically, across CLIP, SigLIP, and DINO, we find partial linear factorization with low-rank near-orthogonal per-concept factors, and the degree of this structure correlates with compositional generalization on unseen combinations. As models continue to scale, these conditions predict the geometry they may converge to. Code: https://github.com/oshapio/necessary-compositionality

Modern AI systems learn from millions of examples, but the world contains far more combinations of things (a red sports car, a striped cat, a blue mug) than any training set can hold. A trustworthy AI should still recognize "red" and "cat" together even if it only ever saw red cars and black cats, a skill called compositional generalization that current models often fail at. We ask a different question: if an AI does generalize correctly to new combinations, what must its internal representations look like? We show, mathematically, that there is essentially no choice. It must encode each concept (color, shape, object) as an independent direction in its internal map, with these directions perpendicular to one another. Examining modern foundation models, we find they partially achieve this structure, and the closer they get, the better they generalize.