# Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch

arXiv: https://arxiv.org/abs/2605.03346 · HTML: https://mlsanity.com/paper/2605.03346/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 46 references that are in the map.
- First posted on arXiv 5 May 2026.

## Builds on (most cited first, 19 of 19)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [Understanding Contrastive Learning Requires Incorporating Inductive Biases](https://mlsanity.com/paper/2202.14037/) (2022)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Optimal Sample Complexity of Contrastive Learning](https://mlsanity.com/paper/2312.00379/) (2023)
- [Redundancy, Isotropy, and Intrinsic Dimensionality of Prompt-based Text Embeddings](https://mlsanity.com/paper/2506.01435/) (2025)
- [Insights into Ordinal Embedding Algorithms: A Systematic Evaluation](https://mlsanity.com/paper/1912.01666/) (2019)
- [Randomly Removing 50% of Dimensions in Text Embeddings has Minimal Impact on Retrieval and Classification Tasks](https://mlsanity.com/paper/2508.17744/) (2025)
- [Learning Lines with Ordinal Constraints](https://mlsanity.com/paper/2004.13202/) (2020)
- [Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors](https://mlsanity.com/paper/2312.13490/) (2023)
- [Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant](https://mlsanity.com/paper/2212.12765/) (2022)

## Built on by (most cited first, 1 of 1)

- [Optimal VC Dimension of Contrastive Learning with Margin](https://mlsanity.com/paper/2609.38834/) (2026)

## Abstract (arXiv)

Embedding-based representations in Euclidean space ℝd are a cornerstone of modern machine learning, where a major goal is to use the 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 dist(i,j) < 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 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 -- textitregardless of its dimension -- can achieve accuracy above the trivial 50% baseline.