What Limits Does Quantization Place on Dense Top-$k$ Retrieval? A Theoretical Study

Koki Okajima, Tsukasa Yoshida

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$ retriev…