Is Dimensionality a Barrier for Retrieval Models?

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.