证明嵌入维度 $\mathbb{R}^{2k}$ 足以实现精确的 top-$k$ 检索。
$\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval
- 理论证明嵌入维度只需 $Θ(k)$，与向量数量无关。
- 在单位向量和 $ε$ 分离条件下，可行性上限为 $ε_\star(m,k)=m/\sqrt{k(m-1)(m-k)}$。
- 实验证明简单嵌入方法可超越 LLM 单向量基线，说明几何容量非瓶颈。
本文研究最小可嵌入维度（MED）：即存在 $m$ 个对象向量配置，使得任意大小不超过 $k$ 的子集可通过打分比较精确检索的最低维度。结果表明，对于内积、欧氏距离和余弦相似度，MED 为 $Θ(k)$，与 $m$ 无关。进一步考虑鲁棒性 MED（RMED），要求所有向量单位归一化且打分差距至少 $ε$，推导出 $m$ 相关的可行性阈值 $ε_\star(m,k) = m / \sqrt{k(m-1)(m-k)}$，当 $m \gg k$ 时趋近于 $1/\sqrt{k}$。高斯中心构造法在可行边际下给出鲁棒上界。合成数据上的 top-$2$ 检索实验，结合循环多面体与中心点查询优化，验证了理论结论。在 LIMIT 与 LIMIT-small 数据集上的实验显示，简单嵌入基线会过拟合并优于单向量 LLM 嵌入基线。理论与实证均表明，精确几何能力不足并非性能障碍。
原文摘要 · Abstract (English)
This paper studies the Minimal Embeddable Dimension (MED): the least dimension in which there exists a configuration of $m$ object vectors so that every subset of size at most $k$ is exactly retrieved by score comparison. Our result shows MED is $Θ(k)$, independent of $m$, for inner product, Euclidean distance, and cosine similarity. We then consider Robust MED (RMED), where all vectors are unit normed and an $ε$ gap of scores is required. We derive the $m$-dependent feasibility ceiling $ε_\star(m,k)=m/\sqrt{k(m-1)(m-k)}$, which approaches $1/\sqrt{k}$ when $m\gg k$, and a Gaussian centroid construction gives a robust witness upper bound in the feasible margin regime. Numerical simulation on synthetic top-$2$ retrieval with cyclic polytope and centroid query optimization confirmed our theoretical claims. Experiments on LIMIT and LIMIT-small datasets also show that simple embedding-based retrieval baselines can overfit and outperform the reported single-vector LLM embedding baseline. Both theoretical and empirical findings rule out the lack of exact geometric capacity as the obstruction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。