PaperlayerView exact revision on arXiv

Source-linked AI summary

Compositional Generalization Requires Linear, Orthogonal Representations in Vision Embedding Models

Arnas Uselis, Andrea Dittadi, Seong Joon Oh

arXiv:2602.24264v2cs.CVcs.LG

TL;DR

The paper addresses what representation structure is needed for models trained on restricted combinations to generalize compositionally. It formalizes three desiderata and derives necessary geometric constraints, finding partial factorization and near-orthogonality correlated with generalization in modern vision encoders.

  • Problem

    Modern models observe only a tiny fraction of possible concept combinations, leaving what embedding structure supports generalization to unseen combinations as an open question.

  • Method

    The paper formalizes divisibility, transferability, and stability over valid training supports and analyzes their consequences for representations with linear readouts.

  • Results

    Across modern vision-language and self-supervised encoders, representations partially exhibit factorization and near-orthogonal geometry, whose degree correlates with compositional generalization on unseen combinations.

  • Takeaways & Limitations

    The theory reframes linear representation structure as a necessary consequence of compositional generalization and provides a geometric target for model analysis and design.

  • Takeaways & Limitations

    The theory emphasizes worst-case stability and assumes a fixed encoder retrained across different training supports, unlike practical training on one dataset.

Abstract

from arXiv · show

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.

1. Introduction

The paper asks what enables compositional generalization when vision models encounter unseen combinations of familiar concepts. It formalizes three desiderata and argues that they require linear factorization with near-orthogonal concept directions.

  • Motivation: Modern vision systems train on tiny, biased subsets of combinatorial concept spaces yet often struggle when test combinations differ from training combinations.This tension persists despite strong zero-shot transfer in large vision-language models.
  • Desiderata: The paper formalizes compositional generalization through divisibility, transferability, and stability.These require accessible parts, transfer from diverse restricted supports to unseen combinations, and robust behavior across valid supports.
  • Data-setting context: The introduction frames prior sampling designs as choices over training combinations and validity rules in a concept space.The figures depict training and held-out combinations within grid-based concept spaces.
  • Geometric necessity: The analysis shows that these desiderata necessitate linear factorization with near-orthogonal directions for different concepts.This gives a necessary geometric target under the paper’s standard linear-readout setting.
  • Implication: The resulting theory grounds the Linear Representation Hypothesis by treating observed linear structure in neural representations as necessary for compositional generalization.The claim concerns systems satisfying the stated desiderata under the paper’s assumptions.

2. Related work

Prior work studies sufficient conditions, learned representation geometry, and disentangled or object-centric representations. This paper instead asks what embeddings must satisfy for compositional transfer under its desiderata.

  • Compositional generalization: Prior studies establish sufficient conditions for compositional generalization under specific data-generating or representation assumptions.
  • This work: The paper asks the complementary necessary-condition question: what embeddings must satisfy if a model generalizes compositionally?
  • Representation geometry: Empirical work documents linear subspaces, linear representation hypotheses, and near-orthogonal feature encodings in learned representations.
  • Disentangled representations: Disentangled and object-centric research proposes representation desiderata and training schemes, with mixed evidence linking them to compositional generalization.

3. Setup: A framework for compositionality

The framework models inputs as combinations of concept values and defines compositional generalization through three desiderata: divisibility, transferability, and stability. It focuses on non-contextual embedding models with linear readouts trained from valid subsets of the concept space.

  • Concept spaces: The framework treats each input as a tuple of values from a Cartesian product of k concepts.With n values per concept, the concept space is C = [n]^k and contains n^k combinations.
  • Data collection: Training supports are valid subsets of the concept space defined by a validity class and rule.A training dataset contains the inputs and concept tuples associated with one valid support.
  • Model scope: The model class includes non-contextual embedding encoders such as CLIP, SigLIP, supervised models, and DINO with linear or affine readouts.Nonlinear layers before a final linear layer can be absorbed into the encoder.
  • Desiderata: Divisibility, transferability, and stability require distinguishing all combinations, transferring from restricted supports, and maintaining predictions across valid retrainings.The desiderata are intended to formalize ideal compositional generalization under standard training.
  • Formal definition: Compositional generalization is defined by satisfying divisibility and transferability on the full grid while keeping posteriors stable across valid retrainings.The linear version uses a linear readout hypothesis class.

4. Implications of compositionality on representations

The paper derives geometric implications of compositional generalization under gradient descent with cross-entropy and linear readouts, then analyzes capacity requirements. The resulting representation must factor linearly across concepts with orthogonal cross-concept directions, while the minimum dimension scales with the number of concepts.

  • Geometric interpretation: Linear factorization represents n^k combinations using n · k per-concept factors, while orthogonality applies across concepts rather than within a concept.For example, factors for “red” and “square” must be orthogonal, whereas “red” and “blue” need not be.
  • Empirical analysis: Synthetic experiments show that linearity and orthogonality emerge under standard classification losses, especially as the number of concepts increases.The empirical analyses concern models that already support compositional generalization.
  • Geometric necessity: Under binary gradient descent with cross-entropy, stable compositional generalization requires linear factorization and cross-concept orthogonality.The result is established for validity regimes including supports covering more than half the grid and anchor-based supports.
  • Sufficiency: Linear factorization with cross-concept orthogonality is also sufficient for compositional generalization in the same binary gradient-descent and cross-entropy regime.This establishes a converse to the necessity result.
  • Minimum dimension: The minimum embedding dimension satisfies d ≥ k for k concepts, independently of the number of values per concept.The bound only requires two distinguishable values per factor and therefore applies to discrete and continuous factors.
  • Capacity effects: As k grows at fixed d, per-concept subspaces become increasingly low-rank and approach near-collinearity.Empirically, cross-entropy in Euclidean space approaches the lower bound most closely, whereas BCE and spherical geometry require more dimensions.

5. Surveying necessary conditions in pretrained models

Modern pretrained vision models partially exhibit the linear factorization and cross-concept orthogonality predicted as necessary for compositional generalization. Greater linear structure correlates with better performance on unseen combinations, while current models remain short of perfect factorization.

  • Qualitative geometry: DINOv3 embeddings on dSprites show near-constant direction shifts when shape or position changes, with the two directions nearly orthogonal.The same approximate structure appears when other concepts are fixed and varied.
  • Qualitative geometry: Each embedding is approximately a sum of per-concept factors, which are often low-rank and organize pairwise projections into aligned grids.Recovered factors are typically at most 3D in the illustrated examples.
  • Linearity: Projected R2 scores are consistently above random baselines, at 0.4-0.6 versus 0.12-0.42, indicating partial but incomplete linear factorization.The same linearity trend holds when text encoders act as zero-shot probes.
  • Generalization: Higher Projected R2 coincides with higher compositional accuracy across datasets, train fractions, the full 32×32 dSprites grid, and zero-shot probe experiments.A randomly initialized OpenCLIP baseline occupies the low-R2/low-accuracy corner.
  • Orthogonality: Pretrained encoders show within-concept direction similarity around 0.53-0.55 versus cross-concept similarity around 0.09-0.12, indicating partial orthogonality.Randomly initialized encoders show higher across-concept similarity, averaging 0.32.
  • Factor dimensionality: Ordinal and continuous concepts are typically captured by ≤4 principal components, often ≤2, while discrete concepts have higher effective rank.Factor geometry is similar across CLIP, OpenCLIP, SigLIP, and SigLIP2.

6. Discussion and conclusion

The paper concludes that compositional generalization imposes linear, cross-concept-orthogonal embedding geometry, with a minimum dimension bound. Empirical evidence shows current models only partially meet this structure, motivating extensions beyond worst-case stability and further study of training support and geometry.

  • Conclusion: The three desiderata force linear factorization with cross-concept orthogonality and require a minimum embedding dimension d ≥ k.This reframes the Linear Representation Hypothesis as a necessary consequence of compositional generalization.
  • Conclusion: Across modern VLMs and compositional datasets, factorization degree correlates with compositional generalization in both vision-language and self-supervised DINO encoders.The R2–accuracy relationship provides a representation-space diagnostic for compositional capability.
  • Limitations and future work: The theory emphasizes worst-case stability over valid training supports, while average-case or approximate stability may better match some practical settings.Characterizing how training supports alter the implied geometry is identified as future work.
  • Relation to prior work: The work differs from prior sufficient-condition studies by characterizing what embeddings must satisfy for transfer from restricted subsets to the full combinatorial space.Related approaches analyze objectives, architectures, data-generating assumptions, or specific representation classes instead.
  • Relation to prior work: Prior representation studies report linear subspaces, multidimensional features, task-dependent concept families, and geometry shaped by data distributions and training objectives.These findings provide context for the paper’s necessary-geometry perspective.
  • Relation to prior work: Disentanglement and object-centric work commonly specifies internal-code desiderata or training schemes, whereas this paper derives necessary structure under compositional-generalization desiderata.The distinction is complementary to empirical correlations between disentanglement and compositional accuracy.

B. Necessary conditions (proof of Proposition 1)

Under the stated valid-support regimes and Desiderata 1–3, GD with cross-entropy forces binary-grid embeddings to factor linearly by concept, with orthogonal cross-concept differences. The same geometry supports transferability and stability from sufficiently small valid supports.

  • Setup: The proof studies full datasets with |T| = 2^(k−1) + 1 and cross-datasets containing an anchor plus k one-concept flips.Cross-datasets vary one concept at a time around a center, making the geometric argument transparent.
  • Proof mechanism: GD+CE is analyzed through its max-margin SVM limit, whose support vectors are counterfactual pairs differing in one concept.For each concept, paired cross-datasets provide tight support vectors that exchange the minority and majority points.
  • Linearity: Linearity: every binary-grid embedding decomposes as z_c = Σ_i u_i,c_i.Concept-wise differences are independent of the values of other concepts, so datapoints can be written as sums of concept-specific components.
  • Orthogonality: Cross-concept orthogonality: (u_i,1 − u_i,0) ⊥ (u_j,1 − u_j,0) for i ≠ j.The proof first establishes invariance to changes in other concepts, then shows orthogonality against their difference span.
  • Consequence: A valid support of size 2^(k−1) + 1 or a cross-dataset of size 1 + k recovers every concept value on the full grid and yields stability across valid supports.The recovered readouts have the same weight and bias vectors across the considered valid datasets.

C.2. General case: linearly factored embeddings and sufficiency of recovering the factors

The general case characterizes how linearly factored embeddings can be recovered and when that recovery supports compositional readouts. Factorizations are identifiable only up to concept-wise shifts, while centered factors are unique; full-rank recovery then enables linear probes.

  • Approach: The section analyzes sufficiency by recovering factors from representations that already possess linear factorization.The approach covers general concept values and does not require concept directions to be linearly independent.
  • Identifiability: Any two valid factorizations differ by one shift vector s_i per concept, so factors are identifiable only up to concept-wise shifts.The shifts preserve all reconstructed embeddings when their sum is zero.
  • Identifiability: Centered factors are uniquely determined because subtracting each concept’s mean removes its shift ambiguity.Once centered per concept, any recovered factorization matches the true centered factors.
  • Sufficiency: In the multi-valued case, recoverable linear factors are sufficient in principle to construct concept classifiers, although GD+CE does not necessarily satisfy the desiderata without orthogonality.The constructive sufficiency result is distinct from the binary GD+CE necessity–sufficiency case.
  • Recovery: When the one-hot design matrix has rank 1 + k(n − 1), the linear system determines centered factors uniquely and permits readouts that recover all combinations under linear separability.The rank equals the maximum possible rank established for the design matrix.

D. Packing and minimum dimension (proof of Proposition 2)

The dimension analysis bounds the embedding space needed for linear probes to realize every combination of k concepts with n values. At least k dimensions are necessary, and a k-dimensional construction is sufficient.

  • Question: The geometric-capacity question asks how large d must be for linear probes to realize all concept combinations.The argument uses affine hyperplane arrangements induced by concept-value classifiers.
  • Lower bound: Each concept contributes an affine decision hyperplane in the binary restriction, and all 2^k combinations require at least 2^k regions.For n > 2, restricting every concept to two values preserves this binary requirement.
  • Lower bound: d ≥ k is necessary for k concepts, each with n values, to be correctly classified across all n^k combinations by linear probes.When d < k, the maximum region count of k affine hyperplanes is less than 2^k.
  • Tightness: The bound is tight: with d = k, assigning one coordinate to each concept yields correct classification of all n^k combinations.The construction uses standard-basis directions and suitable probe vectors and biases.
  • Geometric intuition: In the LRH toy geometry, orthogonal concept directions form a regular grid whose axes correspond to concepts.The figure compares mildly non-orthogonal and closer-to-orthogonal directions through their decision regions and joint-space cells.

E.2. Case 2: Ideal “on-off” concept classifier

The ideal on-off classifier assigns one score to matching concept values and another to mismatches, yielding an additive representation structure that preserves probe responses. This structure has rank and dimensionality constraints tied to the number of concepts and values.

  • On-off scoring: An on-off classifier gives each probe score α for a match and β for a mismatch, with α > β.The same two-score pattern is imposed across concepts, values, and representation tuples.
  • Rank structure: The resulting logit matrix has rank 1 + k(n −1), because each concept block contains one redundancy while contributing n−1 independent directions.Summing rows within every block produces the same vector, creating k−1 redundancies.
  • Dimensionality: Any model realizing the fixed on-off dot-product pattern requires at least 1 + k(n −1) embedding dimensions, and this bound is tight.Explicit probe and representation families achieve the bound using orthogonal directions.
  • Example: For two concepts with three values each and (α, β) = (1, 0.2), the logit matrix has rank 5 = 1 + k(n −1).Each of the two concept blocks sums to the same vector and contains two independent directions.
  • Additive factorization: Under the on-off pattern, representations can be linearly reconstructed as a global mean plus concept-specific factors.The reconstructed representations are indistinguishable from the originals to all probes.
  • Additive factorization: The construction obtains concept factors by averaging representations and centering the resulting per-concept components.This averaging-based factorization preserves the on-off probe condition.

F. Discussion on stability

Stability is necessary because perfect linear classification alone permits brittle, non-factorized geometries. Requiring predictions to remain consistent across valid training supports constrains decision boundaries and supports the factorized structure.

  • Without Stability, decision regions can vary arbitrarily across training supports, allowing boundaries near data points and infinitesimally thin concept-value regions.These degenerate configurations can persist even as n →∞.
  • Stability requires per-concept posteriors to agree across valid supports, which fixes linear-softmax probe weights up to a shift in the non-binary case.This pins down decision boundaries and forces the representational structure established by the main results.
  • Perfect linear classification does not imply additive structure, even for d = 2, k = 2, and n →∞.Constructed point clouds can be perfectly linearly separable while lacking a linear factorization.
  • For n = 8 and n = 14, boundary arrangements yield 64 and 196 regions while preserving perfect separability, yet no linear factorization is possible.Additional nearly parallel boundaries can split regions into arbitrarily thin pieces.
  • The framework avoids degenerate configurations through Stability rather than imposing technically difficult minimum-area constraints on decision regions.Minimum-area constraints are possible in principle but become technical.

G.2. Whitening in measuring linear factorization

Whitening prevents dominant variance directions from making non-factorized representations appear highly linear. The analyses also show that perfect separability can coexist with low factorization scores, while higher projected R2 consistently aligns with better held-out compositional accuracy.

  • Whitening removes dominant directions that can inflate R2, revealing whether representations are genuinely decomposable into per-concept components.In one example, R2 falls from 0.813 to 0.509 after whitening; in another, it falls from 0.991 to 0.564.
  • R2 = 1 indicates perfect decomposition into per-concept components, whereas R2 = 0.53 leaves reconstruction incomplete.The perfect case reconstructs 576 combinations using 48 factor vectors.
  • Perfect linear classification can coexist with factorization scores from R2 = 0.32 to R2 = 0.83 when k < d.The extra degrees of freedom allow embeddings to be perturbed without sacrificing classification.
  • Across held-out split regimes, higher projected R2 is consistently associated with higher compositional accuracy on unseen combinations.This pattern holds across different held-out test fractions and model checkpoints.
  • Across datasets and models, at least 95% of factor variance is typically captured by one or two principal components.Semantic factors are low-rank and geometrically similar across models, while discrete concepts are not strictly low-rank.

H.4.1. EXPERIMENTS ON PUG-ANIMAL

PUG-Animal experiments use text-encoder probes to assess factorization, orthogonality, and accuracy across four exposed concepts. Higher projected R2 aligns with higher accuracy, while factors are more orthogonal across concepts than within them.

  • The experiments expose four concepts: character, background, scale, and texture, using concept-specific prompt templates.Scale values are mapped to descriptive prompts before generating text embeddings.
  • Text-encoder probe vectors are generated by passing each concept-value prompt through the encoder and applying ℓ2 normalization.These vectors serve as probes for the factor analysis.
  • Higher projected R2 generally coincides with higher accuracy on the full PUG-Animal dataset, while the random baseline has low projected R2 and accuracy.The probes are extracted from the text encoder rather than trained linear probes.
  • For all evaluated models, factor cosine similarity is lower across concepts than within concepts, unlike the random baseline.The off-diagonal versus diagonal contrast indicates partial cross-concept orthogonality.
  • High-R2 samples generally depict clean scenes where character, size, and texture are easier to discern than in low-R2 samples.The qualitative comparison is shown for SigLIP2.

H.4.2. EXPERIMENTS ON IMAGENET-AO

ImageNet-AO evaluates adjective–noun compositions in a sparse dataset using text-encoder probes and recovered factors. Across models, higher projected R2 coincides with accuracy, cross-concept factors are more orthogonal, and the factorization metric remains robust across training regimes.

  • ImageNet-AO contains adjective–noun descriptions with around 80 adjectives, over 600 nouns, and only 0 to 6 images per potential combination.The balanced analysis uses the most common 80 adjectives and nouns and contains 3243 datapoints.
  • Because linear probes cannot be trained, the experiments use text-encoder probes and recover factors by solving a linear system for the sparse, imbalanced data.The design matrix has 3243 rows and full rank 2 · 80 −1.
  • Higher projected R2 coincides with higher accuracy across models, while the random baseline has projected R2 below 0.1.The comparison is computed using the text encoder.
  • For CLIP ViT-L/14, within-concept cosine similarity averages 0.10 for nouns and 0.14 for adjectives, compared with 0.07 across concepts.The random baseline averages 0.49 both across and within concepts.
  • Non-random models show nearly identical within- and across-concept cosine similarities, supporting cross-model similarity in factor geometry.CLIP ViT-L/14 and OpenCLIP ViT-L/14 differ mainly in noun–noun similarity, 0.10 versus 0.11.
  • Projected R2 generally exceeds 0.75 for top-scoring samples and falls below 0.10 for lowest-scoring samples, but some high-scoring samples remain incorrectly predicted.The authors attribute some discrepancies to possible image–text encoder misalignment.
  • Across train fractions, projected R2 increases and then plateaus, while model rankings remain preserved; the major increase occurs only as training coverage approaches N.This indicates the reported values are not simply artifacts of the chosen split.
  • The within-versus-cross-concept orthogonality gap persists across models and datasets, including the complete dSprites grid, while residual variance lacks dominant singular values.The unexplained variance is spread across many components rather than concentrated in a low-dimensional structured subspace.

H.7.1. RESULTS: LINEARITY.

From-scratch experiments show substantial linear factorization across representation spaces and loss types, with most cases achieving R2 ≥0.7.

  • Most from-scratch settings exhibit linear-factorization R2 ≥0.7.The result holds across varied representation spaces and loss types.

H.7.2. RESULTS: ORTHOGONALITY.

From-scratch experiments consistently show cross-concept orthogonality, while dimensional requirements depend on the loss and representation geometry. CE in Euclidean space is typically closest to the theoretical minimum, whereas BCE and spherical variants require more dimensions.

  • Cross-concept factor differences are consistently more orthogonal as the number of concepts increases.Cross-concept cosine similarity decreases with more concepts, while within-concept orthogonality is not theoretically required.
  • CE in Euclidean space typically needs d≈k dimensions, while BCE often needs roughly 2k.These empirical trends are consistent with the theoretical capacity bound d ≥k, though the bound does not guarantee that a training objective reaches it.
  • Spherical representation variants generally require about one additional dimension compared with Euclidean geometry.The dimensionality estimate targets ≥0.99 per-concept classification accuracy across concept spaces varying in k and n.
Loading 2602.24264v2…