Research map / Learning theory and algorithms / Combinatorial and search optimization
MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MUVERA, which converts multi-vector sets into fixed-dimensional encodings (FDEs) so that single-vector MIPS can retrieve Chamfer-similarity nearest neighbors, followed by re-ranking.
Problem
Multi-vector (late-interaction) retrieval with Chamfer/MaxSim similarity is accurate but expensive, because existing systems rely on multi-stage single-vector heuristics that are complex and hard to tune.
Approach
Data-oblivious asymmetric fixed-dimensional encodings built from SimHash space partitioning, per-cluster sums (queries) or centroids with empty-cluster filling (documents), and random projections, so that the FDE inner product approximates Chamfer similarity; this lets off-the-shelf MIPS (DiskANN) do a single retrieval stage followed by Chamfer re-ranking.
Key results
- On MS MARCO, 10240-dim FDEs achieve 80% recall with 60 candidates versus 300 for the deduplicated single-vector heuristic.
- Averaged over 6 BEIR datasets and k in {100, 1000}, MUVERA achieves 10% higher Recall@k (up to 56%) and 90% lower latency (up to 5.7x lower) than PLAID.
- PQ-256-8 compresses FDEs by 32x with minimal recall loss and improves QPS by up to 20x at the same beamwidth.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace PLAID retrieval with MUVERA | ColBERTv2 retrieval · NQ, HotpotQA, MS MARCO, Quora, SCIDOCS, ArguAna | Recall@k: average of 10% higher recall; up to 56% higher | Mixed |
| replace PLAID retrieval with MUVERA | ColBERTv2 retrieval · BEIR datasets | latency: 90% lower latency; up to 5.7× lower | Helped |
| replace PLAID retrieval with MUVERA | ColBERTv2 retrieval · MS MARCO | Recall@k: within 0.4% | No clear effect |
| use FDE retrieval instead of the single-vector heuristic | ColBERTv2 multi-vector retrieval · MS MARCO | candidates retrieved at matched recall: 2.6-5× fewer | Helped |
| add final random projection (ablation) | FDE, MS MARCO, dimension 2460 · MS MARCO | Recall@100: 77.71 -> 78.82 | Helped |
| add final random projection (ablation) | FDE, MS MARCO, dimension 5120 · MS MARCO | Recall@100: 80.37 -> 83.35 | Helped |
| add final random projection (ablation) | FDE, MS MARCO, dimension 10240 · MS MARCO | Recall@100: 82.31 -> 85.15 | Helped |
| add final random projection (ablation) | FDE, MS MARCO, dimension 20480 · MS MARCO | Recall@100: 83.36 -> 86.00 | Helped |
| use k-means instead of SimHash for space partitioning (ablation) | FDE generation · MS MARCO | recall | Hurt |
| compress FDEs with PQ-256-8 (ablation) | MUVERA · BEIR datasets | QPS: up to 20× | Helped |
| compress FDEs with PQ-256-8 (ablation) | MUVERA · BEIR datasets | recall | No clear effect |
| enable ball carving at threshold τ = 0.7 (ablation) | MUVERA reranking · MS MARCO | QPS: 25% | Helped |
Surprising findings
- MUVERA did not outperform PLAID on MS MARCO in end-to-end recall (within 0.4%), possibly because PLAID is tuned for that dataset.
- k-means partitioning gave no quality gains over SimHash for FDEs and was often worse.
Limitations
- Did not outperform PLAID on MS MARCO end-to-end, possibly due to PLAID tuning for that dataset.
- Effect of average number of embeddings per document on FDE retrieval quality was not studied.
- Theoretical guarantees rely on normalized token embeddings (ColBERT-style models).
Experimental setup
Datasets: MS MARCO HotpotQA NQ Quora SciDocs ArguAna
Benchmarks: MS MARCO HotpotQA NQ Quora SciDocs ArguAna
Metrics: Recall@k latency QPS
Baselines: PLAID single-vector heuristic DESSERT
Builds on: ColBERTv2 PLAID DiskANN probabilistic tree embeddings SimHash
Closest papers by meaning
- MetaEmbed: Scaling Multimodal Retrieval at Test-Time with Flexible Late Interaction (ICLR 2026 · similarity 0.88)
- NUDGE: Lightweight Non-Parametric Fine-Tuning of Embeddings for Retrieval (ICLR 2025 · similarity 0.87)
- Your Embedding Model Is SMARTer Than You Think (NeurIPS 2026 · similarity 0.87)
- Hierarchical Retrieval: The Geometry and a Pretrain-Finetune Recipe (NeurIPS 2025 · similarity 0.86)
- POQD: Performance-Oriented Query Decomposer for Multi-vector retrieval (ICML 2025 · similarity 0.86)
- MM-EMBED: UNIVERSAL MULTIMODAL RETRIEVAL WITH MULTIMODAL LLMS (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.