Quantization Forces Embedding Dimension to Scale with Corpus Size in Retrieval

A new theoretical paper by Koki Okajima and Tsukasa Yoshida, posted on arXiv, tackles a fundamental question in information retrieval: What limits does quantization impose on dense top-k retrieval? Prior work had shown that with infinite precision, embedding N documents into d-dimensional vectors such that any k-subset is retrievable requires only d=O(k) dimensions—independent of the corpus size N. This seemed to suggest that vector databases could scale to massive corpora without increasing embedding dimension.

The new study shatters that assumption by introducing quantization constraints. The authors prove that with B bits per coordinate, perfect top-k retrieval requires Bd = Ω(k ln N). In plain terms, at fixed precision, the embedding dimension must grow at least logarithmically with the number of documents. Furthermore, for a standard ℓ2-normalized B-bit uniform scalar quantization model, they identify a critical precision threshold B* = O(ln ln N) below which no embedding dimension can achieve perfect retrieval—meaning that quantization precision itself becomes a bottleneck. The paper maps out three regimes bounding feasible (B,d) pairs, giving practitioners a clear scaling rule: as corpus size grows, both dimension and precision must increase to maintain retrieval fidelity. This has direct implications for the design of vector databases, dense retrieval systems, and approximate nearest neighbor search used in production.