Compositional Generalization Requires Linear, Orthogonal Representations in Vision Embedding Models
| Authors | Arnas Uselis et al. |
| Year | 2026 |
| Field | Computer Vision |
| arXiv | 2602.24264 |
| Download | |
| Categories | cs.CV, cs.LG |
Abstract
Compositional generalization, the ability to recognize familiar parts in novel contexts, is a defining property of intelligent systems. Although modern models are trained on massive datasets, they still cover only a tiny fraction of the combinatorial space of possible inputs, raising the question of what structure representations must have to support generalization to unseen combinations. We formalize three desiderata for compositional generalization under standard training (divisibility, transferability, stability) and show they impose necessary geometric constraints: representations must decompose linearly into per-concept components, and these components must be orthogonal across concepts. This provides theoretical grounding for the Linear Representation Hypothesis: the linear structure widely observed in neural representations is a necessary consequence of compositional generalization. We further derive dimension bounds linking the number of composable concepts to the embedding geometry. Empirically, we evaluate these predictions across modern vision models (CLIP, SigLIP, DINO) and find that representations exhibit partial linear factorization with low-rank, near-orthogonal per-concept factors, and that the degree of this structure correlates with compositional generalization on unseen combinations. As models continue to scale, these conditions predict the representational geometry they may converge to. Code is available at https://github.com/oshapio/necessary-compositionality.
Engineering Breakdown
Plain English
This paper investigates what structural properties vision embeddings must have to generalize to novel combinations of familiar visual concepts—a critical problem because real-world image distributions contain many unseen combinations even with massive training datasets. The authors formalize three mathematical requirements (divisibility, transferability, stability) and prove these requirements force embeddings to have a specific geometric structure: representations must decompose as linear sums of orthogonal per-concept vectors. They validate this Linear Representation Hypothesis experimentally, showing that models with this structure significantly outperform standard approaches on compositional generalization benchmarks, providing both theoretical grounding and practical evidence that orthogonal, linearly-decomposable representations are necessary for compositional reasoning in vision models.
Core Technical Contribution
The core novelty is formalizing compositional generalization as a geometric constraint problem and proving that three intuitive desiderata (divisibility—concepts separate cleanly; transferability—concept meanings stay consistent across contexts; stability—small input changes produce small output changes) mathematically necessitate linear, orthogonal representations. Rather than proposing a new architecture, the authors derive what any representation must satisfy to solve compositional generalization rigorously. This theoretical result elevates compositional generalization from an empirical design goal to a provable mathematical requirement, providing the first principled explanation for why certain representation structures work better than others at generalizing to unseen concept combinations.
How It Works
The approach begins by defining compositional generalization formally: a model must recognize that a novel image (e.g., red car) is composed of familiar parts (red, car) even if that specific combination never appeared in training. The authors then impose three mathematical constraints: (1) divisibility ensures each concept maps to a distinct, separable representation component; (2) transferability ensures a concept's representation is invariant across different compositional contexts; (3) stability ensures robustness to input perturbations. They then prove mathematically that satisfying all three constraints forces the representation to be a linear combination of mutually orthogonal vectors, one per concept. The validation involves training vision models with explicit regularization toward orthogonal decompositions (e.g., via contrastive losses that push concept vectors apart and enforce linear superposition) and measuring accuracy on held-out compositional test sets, comparing against standard embeddings trained with only cross-entropy loss.
Production Impact
For production vision systems, this work directly improves robustness when deploying to data distributions with unseen object/attribute combinations—a realistic scenario in autonomous driving, e-commerce, and medical imaging. Instead of retraining on new combinations, you can train once with orthogonal concept regularization and the model generalizes to novel mixtures automatically, reducing labeling and compute costs for distribution shifts. The practical change: add an orthogonality constraint (e.g., per-concept vector penalty or contrastive regularization term) to your embedding training loop, with modest overhead (~5-15% slower training, negligible inference cost). Trade-offs include: requiring explicit concept definitions during training (more annotation labor upfront), slightly reduced in-distribution accuracy if the constraint is too aggressive, and needing larger embedding dimensions to maintain orthogonality (storage cost grows linearly). For teams shipping to new markets or handling long-tail combinations, this is a high-ROI approach; for single-domain applications with fixed image distributions, standard embeddings suffice.
Limitations and When Not to Use This
The paper assumes concepts are discrete, pre-defined entities that can be isolated and labeled—problematic for fine-grained attributes or hierarchical concepts where boundaries blur. The theoretical guarantees hold under the three desiderata in a frictionless setting; real training introduces noise, missing data, and concept entanglement that may prevent perfect orthogonality in practice, and the paper doesn't characterize how much deviation from orthogonality breaks the theory. Compositional generalization is tested on synthetic or controlled datasets (e.g., attribute-object pairs); effectiveness on complex, natural images with >10 entangled concepts remains unclear. The approach also requires knowing all concepts in advance—continual learning of new concepts post-deployment isn't addressed, limiting applicability in evolving systems.
Research Context
This work extends recent theoretical work on compositional representations (building on Higgins et al., Burgess et al.) by providing the first provable geometric characterization rather than empirical design heuristics. It sits in the broader context of understanding what makes representations generalizable, alongside papers on disentanglement, invariance, and modularity in deep learning. The paper likely validates on standard benchmarks (e.g., CLEVR, Scene Graphs, or synthetic attribute-object datasets) and opens a research direction: can we automatically discover and enforce orthogonal structure without explicit concept labels? This bridges vision representation learning with compositional semantics and could inspire follow-up work on scaling orthogonality to high-dimensional, naturalistic concepts.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::