# Is Dimensionality a Barrier for Retrieval Models?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 72 references that are in the map.
- First posted on arXiv 22 May 2026.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [DINOv2: Learning Robust Visual Features without Supervision](https://mlsanity.com/paper/2304.07193/) (2023)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Sigmoid Loss for Language Image Pre-Training](https://mlsanity.com/paper/2303.15343/) (2023)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [DINOv3](https://mlsanity.com/paper/2508.10104/) (2025)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation](https://mlsanity.com/paper/2402.03216/) (2024)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Contrastive Learning with Hard Negative Samples](https://mlsanity.com/paper/2010.04592/) (2020)
- [With a Little Help from My Friends: Nearest-Neighbor Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2104.14548/) (2021)
- [Perception Encoder: The best visual embeddings are not at the output of the network](https://mlsanity.com/paper/2504.13181/) (2025)
- [EmbeddingGemma: Powerful and Lightweight Text Representations](https://mlsanity.com/paper/2509.20354/) (2025)
- [Robust Large Margin Deep Neural Networks](https://mlsanity.com/paper/1605.08254/) (2016)
- [Large Margin Deep Networks for Classification](https://mlsanity.com/paper/1803.05598/) (2018)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)
- [Global Minimizers of Sigmoid Contrastive Loss](https://mlsanity.com/paper/2509.18552/) (2025)
- [Local and global expansion in random geometric graphs](https://mlsanity.com/paper/2210.00158/) (2022)

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

- [Non-negative Elastic Net Decoding for Information Retrieval](https://mlsanity.com/paper/2606.17910/) (2026)
- [The Limits of Binding in Dual Encoders](https://mlsanity.com/paper/2608.15971/) (2026)
- [Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy](https://mlsanity.com/paper/2610.02749/) (2026)

## Abstract (arXiv)

Why does the low dimensionality of representations, typically d≈ 1000, not prevent modern embedding-based retrieval models from scaling to billions, or even trillions, of data points? To answer this question, we study maximal-margin embeddings in the following retrieval model, classically studied in communication complexity [PS86] and more recently in embedding-based retrieval [WBNL26]. Let A∈ 0,1N× n be a matrix indicating whether each of N queries is relevant to each of n documents. We are interested in the largest margin m>0, denoted by mathsfm^mathsfrd(d, A), for which there exist unit norm embeddings of the queries and documents Ujj = 1N, Vii = 1n with the following property. langle Uj, Virangle ≥ m whenever Aji = 1 and langle Uj, Virangle ≤ -m otherwise. A large margin is a key proxy for representation quality: it controls both robustness to perturbations and compositional generalization across queries. Our main theorem establishes that the best possible margin without a restriction on the dimension, mathsfm^mathsfrd(+∞, A), can be nearly achieved in dimension d = O(mathsfm^mathsfrd(+∞, A)-2log n) which improves a theorem of [BDES02]. Together with a matching lower bound in Theorem 1.5, we conclude that when A∈ 0,1^binomnk× n is the matrix containing all possible k-sparse rows once, dimension d = O(klog (n/k)) is necessary and sufficient for the maximal possible margin mathsfm^mathsfrd(+∞, A) = Theta(k-1/2) in this setting. This fully resolves the setup of [WBNL26]. We also give several constructions for large margins when d = o(klog (n/k)). Finally, we empirically test the InfoNCE and sigmoid losses for producing large margin embeddings and demonstrate a clear advantage of the sigmoid loss.