量化限制了稠密top-k检索的性能，维度需随语料库大小对数增长。
What Limits Does Quantization Place on Dense Top-$k$ Retrieval? A Theoretical Study
- 理论证明：固定精度下，维度必须随语料库大小对数增长才能实现完美检索。
- 在每维B比特量化下，需满足Bd = Ω(k ln N)，否则无法保证检索正确性。
- 发现精度阈值B* = O(ln ln N)，低于此值任何维度均不可行，适合系统设计参考。
我们建立了将包含N个文档的语料库嵌入为d维向量的条件，使得任意k个文档的子集S ⊆ [N]都能通过某个查询向量实现top-k检索。近期研究显示，在无限精度下，d = O(k)的维度即可实现，且与N无关。本文理论证明，这一与语料库无关的界限仅在无限精度时成立。当每坐标使用B比特量化时，实现完美top-k检索要求Bd = Ω(k ln N)；因此在固定精度下，维度至少需随N对数增长。针对ℓ₂-归一化的B比特均匀标量量化模型，我们还识别出一个精度阈值B* = O(ln ln N)，低于该阈值时，无论维度多高都无法实现检索。此外，还确定了两个进一步约束可行(B, d)组合的区间。结果表明，在实际向量数据库和密集检索系统中，量化是常态，因此嵌入维度和可能精度都需随语料库规模增加。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。