Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
For practitioners using contrastive learning or embedding methods, this work reveals a fundamental limitation that dimensionality mismatch can cause catastrophic performance drops, highlighting the need for careful dimension selection.
This paper proves that embedding-based representations suffer a sudden accuracy collapse when the embedding dimension is below a critical threshold relative to the ground-truth dimension, even in standard contrastive learning settings. The authors show that every embedding of dimension at most cD violates half of the triplets, and under the Unique Games Conjecture, no polynomial-time algorithm can exceed 50% accuracy.
Embedding-based representations in Euclidean space $\mathbb{R}^d$ are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that faithfully captures data relations. In this work, we prove sharp dimension--accuracy tradeoffs and identify a fundamental information-theoretic limitation: unless the embedding dimension $d$ is chosen close to the ground-truth dimension $D$, accuracy undergoes a sudden collapse. Our main result shows that this phenomenon arises even in standard contrastive learning settings, where supervision is limited to a set of $m$ anchor--positive--negative triplets $(i,j,k)$ encoding distance comparisons $\mathrm{dist}(i,j) < \mathrm{dist}(i,k)$. Specifically, given triplets realizable by an unknown ground-truth embedding in $D$ dimensions, we prove that there exists constant $c < 1$, such that \emph{every embedding of dimension at most $cD$ violates half of the triplets}, yielding accuracy as low as a trivial one-dimensional solution that ignores the input. We complement our information-theoretic bounds with strong computational hardness results: under the Unique Games Conjecture, even if the given triplets are nearly realizable in $D=1$ dimension, no polynomial-time algorithm -- \textit{regardless of its dimension} -- can achieve accuracy above the trivial $50\%$ baseline.