MV-IVF: Multi-Vector Retrieval via Multi-Vector Clustering
Kishen N Gowda, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram
cs.IR, cs.DB
2026-11-06
MV-IVF 直接对多向量嵌入聚类建倒排索引,把候选生成留在原生多向量空间;90% Recall@10 下单查询延迟最高降 8.03 倍,QPS 最高提升 173.5 倍。
多向量检索是 ColBERT 一系 late interaction 模型的做法:查询和文档各自保留全部 token 级 embedding(一个点云),打分用 MaxSim,查询的每个 token 在文档 token 里取最大内积再求和。检索质量比单向量编码器高,但代价直线上来:算一次查询-文档分数就要几十上百次内积,ColBERTv2 编码下每个文档平均带 69 到 236 个 embedding,暴力扫库不可行。
现有实用系统全走绕道单向量的路线:PLAID 和后继 WARP 用 token 质心做单向量候选生成,MUVERA 把点云压成一个固定维大向量,内积可证近似 MaxSim,再交给普通 MIPS 索引。这条路线的共同软肋是,最终 top-k 的质量取决于代理表示能多好地保住 MaxSim 意义下的高分文档。这篇走互补方向:直接在点云上建 IVF(inverted file,倒排文件)索引。IVF 是单向量检索里部署最广的范式,构建简单、开销低、天然适合并行和批量搜索,把它扩展到多向量数据正是这篇要做的事。
地基是 MV-Lloyd,一个 Lloyd 式点云聚类算法,对应形式化的 Chamfer (k, s)-median 问题:点云分 k 簇,每簇中心本身是一个最多 s 个向量的点云,分配代价用 Chamfer 距离(点云内每个向量到中心点云取最近邻距离再平均)。s 控制中心的表达能力。
每轮两步:分配步把每个点云划给 Chamfer 距离最近的中心;更新步重算中心。关键观察在更新步:分配固定后,求一个簇的最优中心点云,精确等价于把簇内点云摊平后在这些单个向量上解带权 s-median,也就是普通单向量聚类。多向量的复杂性只留在分配步,更新步直接吃现成的高度优化 k-means 代码,实现里用 cosine 的 s-means 做近似。
递归跑 MV-Lloyd 就得到索引:每个节点把分到的点云聚成 b 簇,中心点云存进子节点,递归到叶子上限(默认 500)。查询时在树上做 best-first beam search,用查询点云与中心点云的 MaxSim 分数导航,选出 nprobe 个叶子,只对叶子内文档精算 MaxSim。提前终止的规则是凑够叶子后,若剩余最好的内部节点分数不超过已选叶子中最差的就停;论文自己承认这是启发式,中心分数不是子树内文档分数的上界。
工程上再叠三层:
论文还附带 MV-Vamana(把图索引 Vamana 直接搬到点云)和 MVSIC(读作 music),后者是统一评测的 C++ 库,SVH、MUVERA、MV-Vamana、MV-IVF 共享同一套打分内核。
9 组数据(8 个 BEIR 数据集加 pooled LoTTE),全部用 ColBERTv2 编码,最大到 msmarco 的 880 万文档;召回相对精确 MaxSim 排名计算,单查询延迟用单核、吞吐用满核。90% Recall-10@10 工作点:
| 对照 | 指标 | 结果 |
| MUVERA | 单查询延迟 | 几何平均快 1.33×,最高 4.76× |
| SVH(PLAID 路线) | 单查询延迟 | 几何平均快 1.55×,最高 8.03× |
| MV-Vamana | 单查询延迟 | 几何平均快 1.22×,最高 5.13× |
| MUVERA / SVH / MV-Vamana | 批量吞吐 | 几何平均 2.19× / 4.01× / 2.07×,最高 8.40× / 173.5× / 4.99× |
细分比总数字更有信息量。SVH 在 Recall-1@10(只需找回第一名)上很强,token 级候选生成擅长抓少数强匹配;但要恢复完整 top-10、top-100 邻域就普遍掉队,nq 和 msmarco 是例外,后者本就在 ColBERTv2 训练集里。MV-Vamana 在大数据集的 Recall-100@100 单查询延迟经常最好,图搜索省得下昂贵的点云比较,代价是建库最贵、批量访问不规则,高召回段吞吐下滑。消融说明工程优化是承重墙:全精度版在 100ms 预算内到不了 90% Recall-10@10,仅 Rand-1bit 叶子打分就在 fiqa 提速至少 5.37×,四层全开至少 17.2×。与 FastPLAID、IGP 的直接对比只在 arguana 和 fiqa(两个外部实现在其余数据集跑不稳),吞吐分别高出两个数量级、一个数量级以上。建库时间常明显快于把单向量检索当黑盒的方法;索引大小居中,MV-Vamana 最小但建库最贵。
对做检索基础设施的人,结论是「原生多向量索引在系统层面成立」。单查询延迟的几何平均改进 1.2 到 1.6 倍,实在但不惊人;批量吞吐几何平均 2 到 4 倍、小数据集上几乎全召回区间领先,对在线服务和批量重排序是真金白银。IVF 的叶子扫描规整、可并行,天然对齐高吞吐负载,图索引和单向量降级路线在这一点上都没占到便宜。MVSIC 把几条主要路线放进同一套代码对比,本身也是社区资产。已经在跑 ColBERT 系检索、卡在 serving 成本上的团队是天然受众。
论文自己列的:Chamfer 聚类远没研究透,初始化、近似算法、其他 set-to-set 相似度都没碰;IVF 设计空间没穷尽,溢出、probe 分配、重排策略在大数据集上可能还有空间;提前终止无理论保证。可疑处:与 PLAID 的对比靠自研 SVH 做替身,SVH 确实大幅快于 FastPLAID,但 PLAID 本尊只在两个小数据集被直接比过;基线的批处理只是把独立查询并行化,没有享受按叶子分组的调度,173.5× 这种极值大概率出自小数据集上的这一差距,几何平均的 2 到 4 倍更能代表真实差距;延迟单核、吞吐满核测量,引用数字时口径要对齐。实验全部基于 ColBERTv2 文本 embedding,动机里点名的 ColPali 图像检索没有实验。