Retrieval Needs Multivectors: An Exponential Separation
Mihir Agarwal, Viraj Agrawal, Sabyasachi Basu, Ankit Garg, Kirankumar Shiragur
cs.IR, cs.DB, cs.LG
2026-08-21
微软亚洲研究院给出排序意义上的指数分离:单向量要 2^Ω(m) 维,多向量 O(m^6) 就够。新基准 ANDOR 上,微调后 ColBERT 相对单向量 Recall@2 仍高约 99%。
ColBERT 这类晚交互模型用一组 token 向量和 Chamfer 分数(每个查询向量找最像的文档向量再求和)做检索,工业上已经进了 Vespa、Qdrant。LIMIT 等基准也显示单向量更弱,但后续工作发现 LIMIT 的差距能被任务微调补回,于是「多向量是不是真的更有表达力」还没钉死。
Jayaram 等人证明过:若目标是点对点逼近 Chamfer 分数,单向量可能要指数维。检索真正要的是排序,相关文档排在无关文档上面就行。分数逼近更难,不自动推出排序也难。这篇把问题收成检索排序,并给出一族明确的 query/document 相关性矩阵。
相关性矩阵来自通信复杂度里的 pattern matrix,布尔函数换成 Minsky-Papert 函数:m 个子句的合取,每个子句是 L=4m² 个文字的析取。文档相关,当且仅当每个子句至少被满足一次,即 AND-of-OR。
单向量用内积打分。若它能把每行的相关文档都排在无关文档之上,嵌入维数至少是该矩阵的 sign-rank。已有结论给出 sign-rank = 2^Ω(m),所以单向量维数指数级。多向量这边显式构造:查询每个子句一个向量,文档每个坐标一个向量,Chamfer 分数在「全满足」和「缺一句」之间留出 Θ(m⁻²) 的间隔,表示规模 O(m⁶),多项式级。
对照实验也堵了一条退路:Jayaram 用的 NAND pattern matrix 虽然分数逼近很难,但存在 Θ(N) 维的单向量就能保住排序。分数硬,不代表排序硬。
基准 ANDOR 把同一套 AND-of-OR 换成电商筛选:20 个品类、每类 20 个属性,语料 50,000 件商品。查询要求每个指定品类至少命中一个可接受属性。测试查询恰好 2 条正例,并配只差 1–3 个品类的 hard negative。用 query width(每类可接受属性的均值)控制难度。
零样本下多向量已经大幅领先。GTE ModernColBERT 相对最强单向量 Cohere Embed v4,Recall@2 / @10 / @100 相对增益 80.6%、93.8%、87.0%;相对 OpenAI text-embedding-3-large 的 Recall@2 增益到 1662%。零样本相对增益均值约 6.3×(Recall@2)。
微调补不回这条缝。相对 Qwen3 Embedding 0.6B 和 Arctic Embed L v2,ColBERT 在整张 train–test 网格上 Recall@2 仍高约 99%,Recall@100 高约 58%。最容易的 test width 3.5 上,ColBERT 的 Recall@100 大约 89%–93%,单向量仍明显落后。
更干净的对照是 Jina Embeddings v4:同一骨干同时出单向量头和多向量头,联合微调后多向量相对单向量 Recall@2 / @10 / @100 仍高 105%、84%、62%。训练数据、参数量、优化器都对齐,差距还在。
| 对照 | Recall@2 相对增益 | Recall@100 相对增益 |
| ColBERT vs 零样本单向量均值 | 631.8% | 414.4% |
| ColBERT vs 微调单向量均值 | 99.4% | 57.8% |
| Jina 多向量 vs 同模型单向量(联合微调) | 104.8% | 61.5% |
LIMIT 留下的借口是「没训好」。ANDOR 把这条借口收窄了:同一套 Jina 模型、联合微调,多向量头仍然大约强一倍。做 faceted search、复杂布尔过滤、agent 检索时,单向量稠密检索可能有表达力上限,不是调参能翻过去的。
理论结果说的是最坏实例的维数,ANDOR 不是证明里的那张 pattern matrix,只是同一逻辑的语义版。它已经够难,让现成单向量模型学不会那条简单规则。
每条测试查询只有 2 条正例。按已有存在性结果,完整相关性矩阵已知时,5 维单向量就足以实现排序;那是非构造性的,也不教你从文本里学出嵌入。实验走的是常规语义学习,不矛盾,但也不能直接说「现实任务需要指数维」。
query width 变大时所有方法都掉点,论文没有把机制讲透。开放问题还包括:只要求每行 (1−ε) 比例排对,指数缝是否还在;若目标是保住指定名次而不是相关/无关二分,多向量还有没有指数优势。