Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes theoretical limits on embedding dimensions for top-$k$ retrieval in quantized vector spaces, revealing that while $d = O(k)$ is sufficient for infinite precision, quantization imposes stricter requirements. Specifically, it proves that with $B$ bits per coordinate, the dimension must grow logarithmically with the corpus size $N$ to achieve perfect retrieval. The findings highlight critical thresholds for quantization precision, indicating that practical implementations must adapt embedding dimensions in tandem with corpus size to maintain retrieval efficacy.
Perfect top-$k$ retrieval in quantized systems demands that embedding dimensions scale logarithmically with corpus size, challenging existing assumptions about fixed dimensions.
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 = \Omega(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.