Is Dimensionality a Barrier for Retrieval Models?

arXiv:2605.23556v1 Announce Type: new Abstract: Why does the low dimensionality of representations, typically dapprox 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 Ain {0,1}^{Nimes 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 mathsf{m}^{mathsf{rd}}(d, A), for which there exist unit norm embeddings of the queries and documents {U_j}{j = 1}^N, {V_i}{i = 1}^n with the following property. langle U_j, V_irangle ge m whenever A_{ji} = 1 and langle U_j, V_irangle le -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, mathsf{m}^{mathsf{rd}}(+infty, A), can be nearly achieved in dimension d = O(mathsf{m}^{mathsf{rd}}(+infty, A)^{-2}log n) which improves a theorem of [BDES02]. Together with a matching lower bound in Theorem 1.5, we conclude that when Ain {0,1}^{inom{n}{k}imes 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 mathsf{m}^{mathsf{rd}}(+infty, 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.

Source: arXiv cs.LG | 2026-05-25