Necessary Conditions for Compositional Generalization of Embedding Models

Summary

This paper argues that compositional generalization — the ability of an embedding model to recognize familiar concepts in unseen combinations — is not merely helped by, but requires, representations that decompose linearly into per-concept components with cross-concept orthogonality. The conceptual move is to formalize three practically motivated desiderata on the learned readout (divisibility, transferability, stability) and derive geometric constraints from them, rather than assuming a particular data-generating process or imposing structure by construction. Under GD+CE with linear heads, and either a random support with $|T| = 2^{k-1}+1$ or a minimal cross-dataset with $|T| = 1+k$, the authors show that embeddings must factor as $z_c = \sum_i u_{i,c_i}$ with orthogonal cross-concept difference directions, and that at least $d \geq k$ dimensions are required. This is a genuinely useful reframing: it grounds the Linear Representation Hypothesis as a consequence of a stated notion of compositional generalization, and gives a testable geometric signature. Empirically, whitened Projected $R^2$ across CLIP, SigLIP, MetaCLIP, and DINO families is moderate (~0.4–0.6) but consistently above a random-init baseline, and correlates positively with held-out compositional accuracy on PUG-Animal, dSprites, and MPI3D; within-concept cosine similarity (~0.53–0.55) far exceeds cross-concept similarity (~0.09–0.12), and per-concept factors are low-rank. An executed partial replication on dSprites with four CLIP/OpenCLIP checkpoints monotonically reproduces the $R^2$–accuracy relationship (Spearman 1.0) and the within-vs-cross orthogonality gap (~5× separation), and matches the paper's exact dSprites per-concept dimensionality values (size 1/6, color 8/10). The main conceptual limitation is that "necessary" is contingent on choices — worst-case stability across all valid supports, a specific loss+geometry (GD+CE with linear probes), a binary base case with a multi-valued heuristic extension — that are strong enough to make the "necessity" narrower than the abstract implies, and several load-bearing proof steps are compressed in ways that obscure exactly where each assumption bites. The empirical evidence is broad and consistent across families, but the $R^2$–accuracy correlation is only sanity-checked against a single random-init baseline, and several "predicted-by-theory" patterns (high within-concept similarity, sub-$k$ empirical dimensions under CE) are actually not predicted by the theorem as stated.

Strengths

• Conceptual reframing. Deriving cross-concept orthogonality and linear factorization as necessary consequences of stated desiderata — rather than positing them as inductive biases — is a cleanly stated, useful contribution that connects LRH-style empirical observations to a concrete learning-theoretic argument.
• Well-scoped desiderata. The divisibility/transferability/stability triple is small, plainly motivated, and modular: it lets the reader see which parts of the theorem depend on which assumption (e.g., cross-concept orthogonality is driven by Stability + max-margin).
• Dimension bound with sharp geometry. The $d \geq k$ minimum-dimension result via hyperplane-arrangement counting is tight, easy to verify, and gives a clean quantitative prediction linking concept count to embedding capacity.
• Broad empirical coverage. Nine model families (CLIP, OpenCLIP, MetaCLIP, MetaCLIP2, SigLIP, SigLIP2, DINOv1–v3) on three compositional datasets plus ImageNet-AO, with consistent qualitative patterns (partial factorization, near-orthogonality, low-rank per-concept factors) and robustness checks over train fractions $|S|/N \in \{0.001, \dots, 0.999\}$ and the full $32 \times 32$ dSprites grid.
• Whitened Projected $R^2$ as diagnostic. The whitening step (Appendix G.2) is a genuinely useful methodological refinement: it prevents dominant-direction variance from inflating $R^2$, and the counter-examples in Fig. 17 make the danger concrete.
• Executed slice reproduces cleanly. On dSprites, the whitened $R^2$ values and per-concept effective ranks (size 1/6, color 8/10) reproduce essentially exactly on the models that ran, and the within/cross cosine ordering holds with ~5× separation.

Weaknesses

• "Necessity" is narrower than the abstract implies. The theorem is stated for GD+CE with linear readouts, binary concepts, worst-case Stability across all valid supports, and either $|T| = 2^{k-1}+1$ or a specific $|T| = 1+k$ cross-design. The multi-valued case in Section 5 uses an ansatz form of factorization rather than a proved extension of Proposition 1, and Appendix C.2 only shows a constructive-sufficiency statement. Phrasing this as "linear, orthogonal representations are required" for compositional generalization overstates a result that formally applies to a specific optimizer × loss × geometry × validity-rule cell.
• Stability stated stronger than it is used. Desideratum 3 requires per-concept posterior agreement across supports; the proof uses only prediction/argmax invariance. Under GD+CE on separable data, direction converges but scale does not, so exact posterior equality is generally unattainable — meaning Stability as printed may be unsatisfiable in the same regime where the theorem is proved. This matters because the whole orthogonality argument routes through Stability.
• Key proof steps compressed. Several load-bearing steps are asserted rather than shown: (i) "per-concept weights are proportional to the segment connecting positive and negative classes, from which orthogonality follows" in the main-text sketch; (ii) "Clearly ... $\lambda_j = \gamma_j = 0$" from non-negativity alone in Appendix B; and (iii) the final bridge from $w_i \perp (u_{j,1} - u_{j,0})$ to $(u_{i,1} - u_{i,0}) \perp (u_{j,1} - u_{j,0})$. Each is fixable, but as written a careful reader must reconstruct the crux of the argument.
• Empirical $R^2$–accuracy correlation has thin causal support. The claim that the correlation "is not a dimensionality or scale artifact" rests on a single random-init OpenCLIP ViT-L/14 point. The trained models on the scatter vary in $d$, training FLOPs, and architecture, and there is no partial-correlation or matched-$d$ control. The correlation itself is very likely real, but the framing overstates what one baseline can rule out.
• Empirical patterns misattributed to the theory. High within-concept similarity (~0.53–0.55) is presented as consistent with the theory, but Proposition 1 places no constraint on within-concept factor alignment. Similarly, several CE-Euclidean cells in Fig. 45 reach $\geq 0.99$ accuracy with $d < k$ (e.g., $k = 10, n = 2, d = 8$), which is a legitimate consequence of the $\geq 0.99$ tolerance but as printed looks like a violation of the $d \geq k$ bound.
• Overstated cross-cell generalizations of the synthetic study. The conclusion that "concept count is the primary dimensional driver" is defensible only for CE-Euclidean; the BCE grids show $n$-driven variation from $d \approx 8$ (n=2) to $d \approx 48$ (n=96) at fixed $k = 10$, at least comparable to the effect of $k$. Similarly, the "roughly one dimension" spherical/Euclidean offset holds for CE but is much larger under BCE.
• Section 5.2 evaluation protocol is under-specified. Training on 10% of concept combinations and evaluating on a "held-out 10%" (rather than the full 90% of unseen tuples) is inconsistent with Transferability's full-grid statement, and "best over learning rates $\{10^{-3}, 10^{-2}\}$" does not specify the selection set — if selection is on the test fraction, the reported compositional accuracies (the y-axis of the marquee scatter) are inflated by test-set model selection.
• Counterexample construction in Appendix F is asserted, not shown. The claim that additional near-parallel boundaries can subdivide regions "while maintaining perfect linear separability" is load-bearing for the argument that linear separability does not imply factorization, but no invariant is stated to certify that all grid points remain correctly classified under subdivision.
• Local presentation issues that hinder verification. Multiple in-proof typos (Case 1 vs Case 2 both labeled $i' = i$; two contradictory bullets both stating $r = j$ in Proposition 7; "flipping any other concept than $k$" where $i$ was meant; Orth$(i,j)$ described "for $i = j$"), the factor-recovery formula rendered without a fraction bar, and a duplicated Weller et al. 2025 reference. Individually minor, cumulatively a real friction for careful reading.

Reproducibility & code

An execution of the released repository at github.com/oshapio/necessary-compositionality confirms the paper's core mechanism on a partial slice but exposes substantive gaps between the release and the manuscript.

• What reproduced. On the one dataset that ran end-to-end (clean dSprites) and four checkpoints that could be embedded and probed (CLIP ViT-B/32, CLIP ViT-L/14, OpenCLIP ViT-B/16, OpenCLIP ViT-B/32), whitened projected $R^2 \in [0.406, 0.446]$ paired with mean held-out probe accuracy $\in [0.913, 0.965]$ is monotonically related (Spearman 1.0, Pearson 0.89), directionally reproducing Fig. 8 and matching Fig. 9's dSprites bars (~0.40–0.43). Within-concept cosine cosine $\in [0.488, 0.517]$ and cross-concept cosine $\in [0.087, 0.113]$ give a clean ~5× separation, matching the paper's cross-concept 0.09–0.12 band, though sitting slightly below the paper's 0.53–0.55 within-concept band (plausibly because the runner does not include the paper's exact ViT-L/14 SigLIP2-S/O and SigLIP-L/16 checkpoints). Per-concept effective ranks ($k_{95}$) reproduce the paper's example values exactly (size 1/6, color 8/10).
• Headline scatter has no shipped path. Section 5.2's marquee scatter uses a validity-rule split $|T| = 0.1\,n^k$ and mean per-concept accuracy on excluded tuples. The released train_probes.py splits by a random per-sample fraction (--val-split), not by held-out concept combinations, and no shipped code enumerates concept tuples or averages accuracy on the excluded set. Consequently the entire y-axis of Fig. 8 and the $|S|/N$ sweeps in Figs. 21 and 35–37 are not reproducible from the release as-is.
• Random-init baseline was not runnable end-to-end. The random-init hook exists but is not in the default runner; during execution the random-init embedding job stalled and never produced $R^2$/accuracy values, so the "low-R²/low-accuracy corner" argument could not be independently confirmed on the slice.
• Zero-shot text-encoder probing is absent. No code encodes prompts via the text encoder, uses them as probes $w_{i,j}$, or evaluates the resulting $R^2$/cosine matrices — blocking Section H.4 (PUG-Animal Figs. 28–30 and ImageNet-AO Figs. 32–34).
• ImageNet-AO is not loadable. No ImageNet-AO loader or the 3243-sample subset preprocessing is present, so the rank-$(2 \cdot 80 - 1)$ design-matrix analysis has no reproduction path.
• Synthetic (from-scratch) harness is not shipped. The CE/BCE × Euclidean/spherical training pipeline that produces Figs. 43–45 (including the empirical $d \geq k$ study and the CE-vs-BCE dimensionality comparison) is not in the release; a reproducer would have to reimplement it from the paper text.
• Residual-SVD utility is absent. The residual is computed inside the $R^2$ routine but is not persisted, and no code produces Fig. 39's $k_{95}$/$k_{99}$ counts or EVR curves.
• Pipeline fragility. get_embeddings.py imports a dsprites_dataset.py module that is not shipped (ImportError before any work), the default runner omits MetaCLIP, MetaCLIP2, DINOv1, DINOv2 and configures the wrong SigLIP2 checkpoint, and whitened projected $R^2$ — the paper's central metric — is only sent to W&B rather than written to a metrics file, so a reproducer without W&B must patch the analysis script. There are also no cross-model aggregation or plotting scripts producing Figs. 8, 9, 10, 22–24, 26, or 38.

Bottom line: on the fragment that ran, the paper's core mechanism reproduces cleanly and matches the paper's specific numbers where they overlap; the release is best described as available-but-incomplete — it covers the whitened-$R^2$ / within-cross orthogonality / $k_{95}$ computations for Section 5, but the compositional-accuracy metric, the $|S|/N$ sweep, the zero-shot text-probe path, the ImageNet-AO experiment, and the synthetic and residual-SVD pipelines are missing.

Recommended Changes

Essential

• Reconcile Stability with what the proof uses. Restate Desideratum 3 in terms of prediction/argmax agreement, or explain how directional convergence of GD+CE yields the stated posterior equality; tie this to Fig. 5.
• Implement the concept-combination train/test split and compositional-accuracy evaluator. Ship a validity-rule-conforming sampler for $|T| = 0.1\,n^k$ and a mean-per-concept accuracy routine over the excluded tuples so the Fig. 8 scatter and the $|S|/N$ sweeps of Figs. 21 and 35–37 are reproducible from the release. This is the single largest reproducibility gap.
• Clarify the Section 5.2 evaluation protocol. State whether compositional accuracy averages over the full 90% unseen tuples or a 10% held-out subset, and on which set the learning-rate selection $\{10^{-3}, 10^{-2}\}$ is done; if selection is on the test fraction, replace it with a train/val protocol.
• Expand the load-bearing proof steps. In the main text, spell out the "$w_i$ proportional to the class-difference segment $\Rightarrow$ orthogonality" chain; in Appendix B, replace "Clearly ... $\lambda_j = \gamma_j = 0$" with the invariance-based argument that forces non-cancellation; state the $w_i \propto (u_{i,1} - u_{i,0})$ bridge explicitly at the end of the orthogonality section.
• Qualify empirical claims that outrun the theorem. State that (a) high within-concept similarity is not predicted by Proposition 1; (b) the sub-$k$ cells in the CE-Euclidean panel of Fig. 45 are consistent with the theorem because $d \geq k$ concerns exact classification while the experiment allows 1% error; (c) "concept count is the primary dimensional driver" holds under CE but is not supported by the BCE grids.
• Ship the missing dsprites_dataset.py module (or prune the import) and persist whitened projected $R^2$ to disk. This is what turns the release from a partial diagnostic library into a runnable Section-5 reproducer without user patching.
• Align the default runner with Table 2. Add MetaCLIP, MetaCLIP2, DINOv1, DINOv2 and the SigLIP2-SO400M checkpoint used in Fig. 8/9, and include the random-init baseline in the default invocation so the "not a scale artifact" control is reproducible without manual invocation.

Suggested

• Add a matched-$d$ or partial-correlation control to strengthen the "not a dimensionality or scale artifact" claim beyond a single random-init point.
• Fix in-proof typos (Case 2 label $i' \neq i$; the second Proposition 7 bullet $r \neq j$; "other than $i$" in the linearity step; Orth$(i,j)$ qualifier "for $i \neq j$") and the "$n \cdot k$ factors" intuition ($1 + k(n-1)$).
• Retypeset the factor-recovery mean with an explicit fraction bar and state whether centering is applied before recovery; state where and why the $\alpha \neq -\beta(n-1)$ side condition is used.
• Fix the Fig. 33 caption ("SigLIP2 model" → "across models") and deduplicate the Weller et al. 2025a/2025b reference.
• State explicitly that ImageNet-AO's design-matrix rank $2 \cdot 80 - 1$ was numerically verified on the 3243-sample subset, and specify how the shift ambiguity in the linear-system solve is resolved (per-concept centering, minimum-norm, etc.).
• Ship the zero-shot text-encoder-probe path and an ImageNet-AO loader, or scope the reproduction package explicitly to the learned-probe / PUG-Animal / dSprites / MPI3D experiments.
• Release the synthetic (from-scratch) harness for Figs. 43–45 so the empirical $d \geq k$, $R^2 \geq 0.7$, and CE-vs-BCE-vs-geometry claims are reproducible.
• Persist the residual matrix inside the factorization routine and add a small SVD-of-residual utility so Fig. 39's $k_{95}$/$k_{99}$ counts are reproducible.
• Add cross-model aggregation and plotting scripts (or a summary CSV/JSON schema and reference notebook) so per-run outputs can be assembled into Figs. 8, 9, 10, 22–24, 26, and 38 without ad-hoc glue.
• Soften "consistently above the random baseline" to per-dataset language, since the reported model and random ranges touch at the boundary, and state the actual random spread (rather than "around 0.5") in the ImageNet-AO / PUG-Animal orthogonality discussion.
• State a subdivision invariant in Appendix F that certifies grid points remain correctly classified after adding boundaries, and exhibit one explicit point cloud for the counterexample.