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 clusters multi-vector embeddings directly and searches an IVF tree over them, hitting up to 8.03x lower latency and 173.5x higher QPS than baselines at 90% Recall-10@10.
Multi-vector retrieval, the ColBERT line of late-interaction models, keeps every token embedding of a query and document as a point cloud and scores relevance with MaxSim: each query token picks its best-matching document token by inner product, and the scores are summed. Relevance beats single-vector encoders on BEIR and LoTTE, but search gets expensive fast. One query-document score already takes many inner products, and under ColBERTv2 each document averages 69 to 236 embeddings, so scanning the collection is off the table.
Practical systems sidestep the problem by dropping back to single-vector search for candidate generation. PLAID and WARP search over token centroids; MUVERA compresses each point cloud into one large vector whose inner product provably approximates MaxSim. The shared weakness: final top-k quality hinges on how well the surrogate preserves documents that rank high under MaxSim. This paper takes the complementary route, extending IVF (inverted file), the most widely deployed single-vector index paradigm, to operate directly on point clouds.\n
The foundation is MV-Lloyd, a Lloyd-style clustering algorithm for what the authors formalize as Chamfer (k, s)-median: partition point clouds into k clusters whose centers are themselves point clouds of at most s vectors, with Chamfer distance (each embedding's distance to its nearest center vector, averaged) as assignment cost. The parameter s budgets how expressive each representative is.
Each round does two things: assign every point cloud to its nearest center under Chamfer, then recompute centers. The key observation sits in the update step. Once assignments are fixed, finding the optimal center cloud for a cluster reduces exactly to weighted s-median over the flattened embeddings in that cluster, which is ordinary single-vector clustering. All the multi-vector difficulty stays in the assignment step; the update reuses highly optimized k-means machinery (an s-means update with cosine similarity in practice).
Recursing MV-Lloyd yields the index: each node clusters its point clouds into b groups, stores each group's center cloud on the child, and stops at a leaf size cap (500 by default). Queries run best-first beam search over the tree, navigating by MaxSim between the query cloud and the center clouds, pick nprobe leaves, and exactly score only the documents inside. An early-termination rule stops the search once the best unexpanded internal node scores no higher than the worst selected leaf; the authors state plainly that this is a heuristic with no bound guarantee.
Three engineering layers on top:
The paper also ships MV-Vamana, a native graph index extending Vamana to point clouds, and MVSIC (pronounced like music), a unified C++ library where SVH, MUVERA, MV-Vamana, and MV-IVF share the same scoring kernels and evaluation pipeline.
Nine datasets (eight from BEIR plus pooled LoTTE), all encoded with ColBERTv2, up to 8.84M documents on msmarco. Recall is measured against exact MaxSim rankings. Latency runs on a single core; throughput uses all cores.
At 90% Recall-10@10:
| Baseline | Metric | Result |
| MUVERA | single-query latency | 1.33x faster geomean, up to 4.76x |
| SVH (the PLAID pipeline) | single-query latency | 1.55x faster geomean, up to 8.03x |
| MV-Vamana | single-query latency | 1.22x faster geomean, up to 5.13x |
| MUVERA / SVH / MV-Vamana | batched throughput | 2.19x / 4.01x / 2.07x geomean, up to 8.40x / 173.5x / 4.99x |
The breakdown is more informative than the headline. SVH is strong on Recall-1@10, where a few high-signal token matches recover the top document, but falls behind once the full top-10 or top-100 neighborhood matters; nq and msmarco are exceptions, and msmarco sits in ColBERTv2's training data, which makes token matching unusually effective there. MV-Vamana often posts the best single-query latency at Recall-100@100 on larger datasets, since graph search minimizes expensive point-cloud comparisons, but it is the costliest to build and its irregular traversal hurts batched throughput at high recall. The ablation shows the engineering is load-bearing: full-precision scoring never reaches 90% Recall-10@10 within the 100ms budget; Rand-1bit leaf scoring alone gives at least 5.37x on fiqa, and the full stack at least 17.2x. Against FastPLAID and IGP the comparison covers only arguana and fiqa (those implementations would not run reliably elsewhere), with throughput higher by two orders and one order of magnitude respectively. Build time is often clearly faster than methods that use single-vector machinery as a black box; index size sits in the middle, with MV-Vamana smallest but most expensive to build.
For retrieval infrastructure teams, the claim that lands is narrower and more useful than a generic win: native multi-vector indexing is now practical, and the payoff concentrates in batched workloads. Single-query latency gains of 1.2-1.6x geomean are real but modest; throughput gains of 2-4x geomean, with near-domination across the recall range on smaller datasets, are what online serving and bulk reranking actually feel. IVF's regular leaf scans parallelize cleanly, an advantage neither graph indexes nor single-vector fallbacks exploit as well. MVSIC is a contribution in its own right: these lines of work compared for the first time in one codebase, on one set of embeddings and scoring kernels. Teams already running ColBERT-style retrieval and choking on serving cost are the natural audience.
The authors list open problems themselves: the Chamfer clustering objective is barely explored (initialization, approximation algorithms, other set-to-set similarities); the IVF design space is unfinished, with spilling, probe allocation, and reranking strategies left open, especially at larger scale; early termination carries no guarantee. Points that deserve scrutiny: the PLAID comparison rests on SVH as a stand-in, and while SVH does beat FastPLAID substantially, the direct external comparison covers only two small datasets; baselines in the batched setting just parallelize independent queries and get none of the leaf-grouped scheduling, so the 173.5x extreme likely reflects that gap on a small dataset and the 2-4x geometric mean is the honest number; latency and throughput are measured on one core and all cores respectively, so quoting them side by side needs care. All experiments use ColBERTv2 text embeddings, and the ColPali image retrieval mentioned as motivation never gets evaluated.