低维嵌入也能高效检索百亿数据，关键在于边际最大化机制。
Is Dimensionality a Barrier for Retrieval Models?
- 通过最大间隔嵌入理论分析检索模型在低维空间的可行性。
- 证明维度仅需 O(k log(n/k)) 即可实现最优间隔 Θ(k^{-1/2})。
- 实验证明Sigmoid损失比InfoNCE更易生成大间隔嵌入，适合工程优化。
为何现代基于嵌入的检索模型在仅有约1000维的低维表示下仍能处理百亿甚至万亿级数据？本文研究经典通信复杂度与近期嵌入检索中的最大间隔嵌入模型。给定查询-文档相关性矩阵 $A\in \{0,1\}^{N\times n}$，定义 $\mathsf{m}^{\mathsf{rd}}(d, A)$ 为在维度 $d$ 下可实现的最大间隔 $m>0$：当 $A_{ji}=1$ 时，查询与文档嵌入内积 ≥ m；否则 ≤ -m。大间隔是表示质量的核心指标，影响抗扰动性和组合泛化能力。主定理表明，无需维度限制时的最优间隔 $\mathsf{m}^{\mathsf{rd}}(+\infty, A)$ 可在 $d = O(\mathsf{m}^{\mathsf{rd}}(+\infty, A)^{-2}\log n)$ 维下近似达成，优于 [BDES02] 的结果。结合定理1.5的匹配下界，当 $A\in \{0,1\}^{\binom{n}{k}\times n}$ 包含所有 $k$-稀疏行一次时，维度 $d = O(k\log (n/k))$ 是达到最优间隔 $\mathsf{m}^{\mathsf{rd}}(+\infty, A) = \Theta(k^{-1/2})$ 的充要条件，完全解决了 [WBNL26] 的设定。此外，本文还给出 $d = o(k\log (n/k))$ 时构造大间隔嵌入的方法。最后，实验对比 InfoNCE 与 Sigmoid 损失，证实 Sigmoid 损失在生成大间隔嵌入上具有明显优势。
原文摘要 · Abstract (English)
Why does the low dimensionality of representations, typically $d\approx 1000$, not prevent modern embedding-based retrieval models from scaling to billions, or even trillions, of data points? To answer this question, we study maximal-margin embeddings in the following retrieval model, classically studied in communication complexity [PS86] and more recently in embedding-based retrieval [WBNL26]. Let $A\in \{0,1\}^{N\times n}$ be a matrix indicating whether each of $N$ queries is relevant to each of $n$ documents. We are interested in the largest margin $m>0,$ denoted by $\mathsf{m}^{\mathsf{rd}}(d, A),$ for which there exist unit norm embeddings of the queries and documents $\{U_j\}_{j = 1}^N, \{V_i\}_{i = 1}^n$ with the following property. $\langle U_j, V_i\rangle \ge m$ whenever $A_{ji} = 1$ and $\langle U_j, V_i\rangle \le -m$ otherwise. A large margin is a key proxy for representation quality: it controls both robustness to perturbations and compositional generalization across queries. Our main theorem establishes that the best possible margin without a restriction on the dimension, $\mathsf{m}^{\mathsf{rd}}(+\infty, A),$ can be nearly achieved in dimension $d = O(\mathsf{m}^{\mathsf{rd}}(+\infty, A)^{-2}\log n)$ which improves a theorem of [BDES02]. Together with a matching lower bound in Theorem 1.5, we conclude that when $A\in \{0,1\}^{\binom{n}{k}\times n}$ is the matrix containing all possible $k$-sparse rows once, dimension $d = O(k\log (n/k))$ is necessary and sufficient for the maximal possible margin $\mathsf{m}^{\mathsf{rd}}(+\infty, A) = Θ(k^{-1/2})$ in this setting. This fully resolves the setup of [WBNL26]. We also give several constructions for large margins when $d = o(k\log (n/k)).$ Finally, we empirically test the InfoNCE and sigmoid losses for producing large margin embeddings and demonstrate a clear advantage of the sigmoid loss.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。