{"id":"arxiv/2605.23556","url":"https://arxiv.org/abs/2605.23556","tags":["cs.LG","cs.IR","math.CO"],"score":0,"title":"Is Dimensionality a Barrier for Retrieval Models?","domain":"cs.LG","source":"arxiv","authors":["Kiril Bangachev","Guy Bresler","Jonathan Kogan","Yury Polyanskiy"],"reviews":0,"subject":"cs.LG","summary":"Why does the low dimensionality of representations, typically $d\\approx 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\\in \\{0,1\\}^{N\\times 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-22","reactions":{}}