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

Yao Tian, Zhoujin Tian, Xi Zhao, Ruiyuan Zhang, Xiaofang Zhou · 2026

Read GEM: A Native Graph-based Index for Multi-Vector Retrieval by Yao Tian, Zhoujin Tian, Xi Zhao, Ruiyuan Zhang, Xiaofang Zhou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20336.txt.

Introduction

Tian and co-authors present GEM, a native index for multi-vector retrieval. Multi-vector search matches sets of vectors, giving finer semantic matches than single vectors. Reused single-vector indexes, though, often lose that meaning or run slowly. GEM builds a proximity graph directly over vector sets. Set-level clustering trims redundancy, and local graphs link into one navigable whole. At query time, beam search starts from several entry points with early pruning. GEM ran up to 16 times faster than leading methods at matched accuracy.

Catalog record

CREATORYao Tian, Zhoujin Tian, Xi Zhao, Ruiyuan Zhang, Xiaofang Zhou
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75555
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20336

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

GEM: A Native Graph-based Index for Multi-Vector Retrieval Yao Tian, Zhoujin Tian, Xi Zhao, Ruiyuan Zhang, Xiaofang Zhou Abstract . 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 16× speedup over state-of-the-art methods while matching or improving accuracy. 1. Introduction The advent of Large Language Models (LLMs) has profoundly reshaped the information retrieval landscape in recent years. By embedding diverse data—text, images, videos, and beyond—into high-dimensional vector spaces, LLMs have made vector representations a standard data format, as shown in Figure 1 (left). This shifts the retrieval paradigm from lexical matching to semantic similarity. At its core lies approximate nearest neighbor (ANN) search, which now underpins many modern applications, such as web search ( 21 ; 56 ) , recommendation systems ( 2 ; 20 ) , and retrieval-augmented generation (RAG) systems ( 27 ; 28 ; 12 ; 44 ) . However, compressing rich semantics into a single embedding vector—like summarizing an entire passage with a single word—inevitably leads to the loss of fine-grained details. This loss often results in irrelevant retrievals and propagates hallucinations in downstream LLMs, especially in long-context inference scenarios ( 62 ) . To overcome this limitation, modern information systems are increasingly representing complex objects as sets of vectors ( 24 ; 50 ; 15 ; 25 ; 31 ; 63 ; 40 ) . ColBERT ( 24 ) is a prominent example, which produces multiple embeddings per query or document by generating one embedding per token. The relevance score is then evaluated using the MaxSim operator (see Definition 1 ), which aggregates the maximum similarity of each query embedding to any document embedding. As illustrated in Figure 1 (right), both query and document are represented as sets of vectors, Q=\{q_{0},q_{1},q_{2}\} and P=\{p_{0},p_{1},p_{2},p_{3}\} , where q_{i},p_{j}\in\mathbb{R}^{d} . Then, each query vector q_{i} interacts with all vectors in the document P : for example, q_{0} achieves the highest similarity 0.94 with p_{0} , q_{1} best matches p_{0} with score 0.7 , and q_{2} aligns most with p_{4} at 0.22 . The final relevance score is computed by summing or averaging these individual scores, e.g., 0.94+0.7+0.22=1.86 . This new paradigm has demonstrated significant improvements in retrieval quality ( 59 ; 23 ; 51 ; 52 ) , interpretability ( 8 ; 60 ) , and generalization ability ( 36 ; 64 ) across various IR benchmarks, emerging as a core functionality in current industrial vector database systems, such as Weaviet ( 61 ) , Vespa ( 57 ) and Pinecone ( 46 ) . Figure 1 . Single-Vector v.s. Multi-Vector Retrieval However, these gains come at steep costs in storage, computation, and the complexity of indexing and retrieval. First, representing each item with multiple vectors inflates storage requirements by several orders of magnitude. Second, pairwise distance calculations across all vectors in the set-to-set comparison incur higher costs. These issues can be alleviated by low-bit quantization techniques ( 11 ; 10 ) or by strategically retaining only the most informative vectors ( 34 ; 15 ) ; however, accurate and efficient indexing and search algorithms for multi-vector representation remain an open challenge. To address this, one straightforward idea ( 24 ; 50 ; 49 ; 42 ; 4 ) is to pool all vectors from all vector sets into a single ANN index, e.g., IVFPQ ( 19 ) or diskANN ( 18 ) . At query time, each query vector retrieves its top- k NNs, generating the initial candidate pool for refinement. However, this approach leads to two issues: (1) vector-level similarity does not always imply set-level relevance, resulting in a large number of irrelevant candidates for refinement. For example, a document about "rocky beaches in Portugal" may be retrieved for the query "family-friendly beaches in Europe" due to the shared term "beaches" despite the clear mismatched intent; (2) indexing all individual vectors bloats the index. For example, 10k documents with 100 vectors each lead to a million-level ANN task. Another proposal ( 17 ) , from Google, attempted to map the vector set into a single vector using distance-preserving mappings, enabling the use of existing ANN indexes. However, a theoretically sound distance-preserving mapping requires prohibitively high dimensionality of the projection space that even well-optimized ANN indexes struggle to handle efficiently. Moreover, this approach contradicts the motivation for using multi-vector representations and begs the question of why not directly train a single-vector embedding model from the outset? DESSERT ( 7 ) is the first solution designed natively for multi-vector retrieval. It compresses the vector set into a sketch via locality-sensitive hashing (LSH) ( 5 ; 6 ) , and retrieves top- k candidates by comparing hash codes. However, without effective sketch-level pruning, the speedup is limited, and storage pressure increases due to the large number of hash values. Motivated by the aforementioned limitations, we propose GEM, a native G raph-based ind E x framework for M ulti-vector retrieval. The key idea of GEM is set-level indexing: constructing a proximity graph where each vertex represents a vector set, in the hope of preserving the semantic richness of multi-vector representations while leveraging the strong pruning capability of graph-based indexes. Specifically, GEM incorporates a series of co-designed architectural and algorithmic optimizations. First, GEM designs a clustering scheme for vector sets. It evaluates the informativeness of the vectors in each set using a TF-IDF–style score and adaptively assigns the set only to the clusters of r highest-scoring vectors. This design preserves semantic coverage while avoiding excessive redundancy in the subsequent graph construction. Next, GEM proposes a dual-graph structure consisting of intra-cluster graphs and a global graph. The intra-cluster graphs capture compact local structures, while sets shared across clusters naturally form bridges, yielding a globally connected graph that enables efficient cross-region traversal and pruning. To reconcile the non-metric nature of the MaxSim operator with the metric assumption underlying graph-based search, GEM decouples the similarity measures used for graph construction and search. Specifically, the graph is built using Earth Mover’s Distance (EMD) ( 48 ) . As EMD is a well-established metric that satisfies the triangle inequality

Read the complete text