What Limits Does Quantization Place on Dense Top-$k$ Retrieval? A Theoretical Study
This work provides fundamental limits for practitioners building vector databases and dense retrieval systems, showing that quantization imposes unavoidable scaling requirements with corpus size.
This paper theoretically shows that for dense top-k retrieval with quantized embeddings, the dimension must grow logarithmically with corpus size, unlike the corpus-independent bound for infinite precision. Specifically, with B bits per coordinate, perfect retrieval requires Bd = Ω(k ln N), and below a precision threshold B* = O(ln ln N), no dimension suffices.
We establish conditions for embedding a corpus of $N$ documents as $d$-dimensional vectors such that every $k$-subset $S \subseteq [N]$ is realizable as a result of top-$k$ retrieval by some query vector. Recent work shows that $d = O(k)$ suffices for such embeddings to exist in $\mathbb{R}^d$, independently of $N$. We theoretically prove that this corpus-independent bound is specific to infinite precision. With $B$ bits per coordinate, perfect top-$k$ retrieval requires $Bd = Ω(k \ln N)$; thus, at any fixed precision, the dimension must grow at least logarithmically with $N$. Specializing to a $\ell_2$-normalized $B$-bit uniform scalar quantization model, we also identify a threshold on the precision $B^{*} = O(\ln \ln N)$ below which no dimension suffices, together with two further regimes that bound the feasible $(B, d)$ pairs. Our result implies that in practical vector databases and dense retrieval systems where quantization is standard, the embedding dimension and possibly the precision must grow with the corpus size.