# GEM: A Native Graph-based Index for Multi-Vector Retrieval

arXiv: https://arxiv.org/abs/2603.20336 · HTML: https://mlsanity.com/paper/2603.20336/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 73 references that are in the map.
- First posted on arXiv 20 Mar 2026.

## Builds on (most cited first, 30 of 33)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [BLIP-2: Bootstrapping Language-Image Pre-training with Frozen Image Encoders and Large Language Models](https://mlsanity.com/paper/2301.12597/) (2023)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [FILIP: Fine-grained Interactive Language-Image Pre-Training](https://mlsanity.com/paper/2111.07783/) (2021)
- [ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction](https://mlsanity.com/paper/2112.01488/) (2021)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [PLAID: An Efficient Engine for Late Interaction Retrieval](https://mlsanity.com/paper/2205.09707/) (2022)
- [Relevance-guided Supervision for OpenQA with ColBERT](https://mlsanity.com/paper/2007.00814/) (2020)
- [Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval](https://mlsanity.com/paper/2101.00436/) (2021)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [PreFLMR: Scaling Up Fine-Grained Late-Interaction Multi-modal Retrievers](https://mlsanity.com/paper/2402.08327/) (2024)
- [Hindsight: Posterior-guided training of retrievers for improved open-ended generation](https://mlsanity.com/paper/2110.07752/) (2021)
- [Pseudo-Relevance Feedback for Multiple Representation Dense Retrieval](https://mlsanity.com/paper/2106.11251/) (2021)
- [Rethinking the Role of Token Retrieval in Multi-Vector Retrieval](https://mlsanity.com/paper/2304.01982/) (2023)
- [Introducing Neural Bag of Whole-Words with ColBERTer: Contextualized Late Interactions using Enhanced Reduction](https://mlsanity.com/paper/2203.13088/) (2022)
- [Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2409.09913/) (2024)
- [Video-ColBERT: Contextualized Late Interaction for Text-to-Video Retrieval](https://mlsanity.com/paper/2503.19009/) (2025)
- [CITADEL: Conditional Token Interaction via Dynamic Lexical Routing for Efficient and Effective Multi-Vector Retrieval](https://mlsanity.com/paper/2211.10411/) (2022)
- [RELIC: Retrieving Evidence for Literary Claims](https://mlsanity.com/paper/2203.10053/) (2022)
- [Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment](https://mlsanity.com/paper/2401.02116/) (2024)
- [Learning Cross-Lingual IR from an English Retriever](https://mlsanity.com/paper/2112.08185/) (2021)
- [A White Box Analysis of ColBERT](https://mlsanity.com/paper/2012.09650/) (2020)
- [Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring](https://mlsanity.com/paper/2004.05345/) (2020)
- [MS-Shift: An Analysis of MS MARCO Distribution Shifts on Neural Retrieval](https://mlsanity.com/paper/2205.02870/) (2022)
- [DESSERT: An Efficient Algorithm for Vector Set Search with Vector Set Queries](https://mlsanity.com/paper/2210.15748/) (2022)
- [Evaluating Interpolation and Extrapolation Performance of Neural Retrieval Models](https://mlsanity.com/paper/2204.11447/) (2022)

## Built on by (most cited first, 1 of 1)

- [TileMaxSim: IO-Aware GPU MaxSim Scoring with Dimension Tiling and Fused Product Quantization](https://mlsanity.com/paper/2606.26439/) (2026)

## Abstract (arXiv)

In multi-vector retrieval, both queries and data are represented as sets of high-dimensional vectors, enabling finer-grained semantic matching and improving retrieval quality over single-vector approaches. However, its practical adoption is held back by the lack of effective indexing algorithms. Existing work, attempting to reuse standard single-vector indexes, often fails to preserve multi-vector semantics or remains slow. In this work, we present GEM, a native indexing framework for multi-vector representations. The core idea is to construct a proximity graph directly over vector sets, preserving their fine-grained semantics while enabling efficient navigation. First, GEM designs a set-level clustering scheme. It associates each vector set with only its most informative clusters, effectively reducing redundancy without hurting semantic coverage. Then, it builds local proximity graphs within clusters and bridges them into a globally navigable structure. To handle the non-metric nature of multi-vector similarity, GEM decouples the graph construction metric from the final relevance score and injects semantic shortcuts to guide efficient navigation toward relevant regions. At query time, GEM launches beam search from multiple entry points and prunes paths early using cluster cues. To further enhance efficiency, a quantized distance estimation technique is used for both indexing and search. Across in-domain, out-of-domain, and multi-modal benchmarks, GEM achieves up to 16x speedup over state-of-the-art methods while matching or improving accuracy.