Paper deep dive

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

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

Year: 2026Venue: arXiv preprintArea: cs.IRType: PreprintEmbeddings: 92

Intelligence

Status: succeeded | Model: anthropic/claude-sonnet-4.6 | Prompt: intel-v1 | Confidence: 96%

Last extracted: 3/24/2026, 2:36:27 AM

Summary

GEM is a native graph-based indexing framework for multi-vector retrieval that constructs a proximity graph directly over vector sets. It introduces set-level clustering with TF-IDF-style weighting, a dual-graph structure (intra-cluster and global), metric decoupling using Earth Mover's Distance for graph construction while retaining Chamfer similarity for search, semantic shortcuts, quantized distance estimation, and a cluster-guided multi-entry beam search. GEM achieves up to 16x speedup over state-of-the-art methods on in-domain, out-of-domain, and multi-modal benchmarks while matching or improving accuracy.

Entities (40)

ColBERT · modelsystem · 99%GEM · algorithmframework · 99%Multi-vector retrieval · research-problemparadigm · 99%Ruiyuan Zhang · personauthor · 99%The Hong Kong University of Science and Technology · organization · 99%Xiaofang Zhou · personauthor · 99%Xi Zhao · personauthor · 99%Yao Tian · personauthor · 99%Zhoujin Tian · personauthor · 99%Approximate Nearest Neighbor Search · research-problemparadigm · 98%Chamfer similarity · conceptmetric · 98%ColBERTv2 · modelsystem · 98%Earth Mover's Distance · conceptmetric · 98%Hong Kong Generative AI Research & Development Center · organization · 98%MaxSim operator · conceptoperator · 98%PLAID · algorithmsystem · 98%Proximity Graph · data-structureconcept · 98%Beam Search · algorithmtechnique · 97%DESSERT · algorithmsystem · 97%Dual Graph Structure · conceptarchitecture · 97%EMVB · algorithmsystem · 97%IGP · algorithmsystem · 97%Large Language Models · technologyconcept · 97%MUVERA · algorithmsystem · 97%Quantized Distance Estimation · technique · 97%DiskANN · algorithmindex · 96%IVFPQ · algorithmindex · 96%k-means clustering · algorithmtechnique · 96%Semantic Shortcuts · concepttechnique · 96%TF-IDF · techniqueconcept · 96%CITADEL · algorithmsystem · 95%Locality-Sensitive Hashing · technique · 95%Pinecone · systemproduct · 95%POQD · algorithmsystem · 95%Retrieval-Augmented Generation · applicationparadigm · 95%Vespa · systemproduct · 95%Weaviate · systemproduct · 95%XTR · algorithmsystem · 95%HNSW · algorithmindex · 93%MVG · algorithmbaseline · 93%

Relation Signals (32)

GEM → addresses → Multi-vector retrieval

confidence 99% · GEM, a native indexing framework for multi-vector representations

Zhoujin Tian → affiliatedwith → The Hong Kong University of Science and Technology

confidence 99% · Zhoujin Tian The Hong Kong University of Science and Technology Hong Kong China

Yao Tian → affiliatedwith → The Hong Kong University of Science and Technology

confidence 99% · Yao Tian The Hong Kong University of Science and Technology Hong Kong China

Xi Zhao → affiliatedwith → The Hong Kong University of Science and Technology

confidence 99% · Xi Zhao The Hong Kong University of Science and Technology Hong Kong China

Xiaofang Zhou → affiliatedwith → The Hong Kong University of Science and Technology

confidence 99% · Xiaofang Zhou The Hong Kong University of Science and Technology Hong Kong China

Ruiyuan Zhang → affiliatedwith → Hong Kong Generative AI Research & Development Center

confidence 99% · Ruiyuan Zhang Hong Kong Generative AI Research & Development Center Hong Kong China

GEM → proposedby → Yao Tian

confidence 99% · we propose GEM — a native Graph-based indExing framework for efficient Multi-vector retrieval

ColBERT → uses →

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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 16x speedup over state-of-the-art methods while matching or improving accuracy.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

92,150 characters extracted from source content.

Expand or collapse full text

GEM: A Native Graph-based Index for Multi-Vector Retrieval Yao Tian The Hong Kong University of Science and TechnologyHong KongChina ytianbc@cse.ust.hk 0000-0001-6876-5059 , Zhoujin Tian The Hong Kong University of Science and TechnologyHong KongChina ztianaf@cse.ust.hk 0009-0001-7673-7311 , Xi Zhao The Hong Kong University of Science and TechnologyHong KongChina xzhaoca@cse.ust.hk 0000-0002-3240-8225 , Ruiyuan Zhang Hong Kong Generative AI Research & Development CenterHong KongChina zry@hkgai.org 0000-0003-2022-7387 and Xiaofang Zhou The Hong Kong University of Science and TechnologyHong KongChina zxf@cse.ust.hk 0000-0001-6343-1455 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. Multi-Vector Retrieval, Approximate Nearest Neighbor Search †copyright: none 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 (Karpukhin et al., 2020; Tian et al., 2023b), recommendation systems (Aouali et al., 2022; Jiang et al., 2020), and retrieval-augmented generation (RAG) systems (Lewis et al., 2020; Li et al., 2023a; Gao et al., 2023; Patil et al., 2023). 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 (Yang et al., 2024). To overcome this limitation, modern information systems are increasingly representing complex objects as sets of vectors (Khattab and Zaharia, 2020; Santhanam et al., 2022b; Hofstätter et al., 2022; Lee et al., 2023; Lin et al., 2023; Yao et al., 2022; Moll et al., 2023). ColBERT (Khattab and Zaharia, 2020) 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=q0,q1,q2Q=\q_0,q_1,q_2\ and P=p0,p1,p2,p3P=\p_0,p_1,p_2,p_3\, where qi,pj∈ℝdq_i,p_j ^d. Then, each query vector qiq_i interacts with all vectors in the document P: for example, q0q_0 achieves the highest similarity 0.940.94 with p0p_0, q1q_1 best matches p0p_0 with score 0.70.7, and q2q_2 aligns most with p4p_4 at 0.220.22. The final relevance score is computed by summing or averaging these individual scores, e.g., 0.94+0.7+0.22=1.860.94+0.7+0.22=1.86. This new paradigm has demonstrated significant improvements in retrieval quality (Wang et al., 2021; Khattab et al., 2021b; Thai et al., 2022; Thakur et al., 2021), interpretability (Formal et al., 2021; Wang et al., 2023), and generalization ability (Lupart et al., 2023; Zhan et al., 2022) across various IR benchmarks, emerging as a core functionality in current industrial vector database systems, such as Weaviet (Weaviate, 2025), Vespa (Vespa, 2024) and Pinecone (Pinecone, 2025). 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 (Gao and Long, 2024; Gao et al., 2025) or by strategically retaining only the most informative vectors (Liu et al., 2025; Hofstätter et al., 2022); however, accurate and efficient indexing and search algorithms for multi-vector representation remain an open challenge. To address this, one straightforward idea (Khattab and Zaharia, 2020; Santhanam et al., 2022b, a; Nardini et al., 2024; Bian et al., 2025) is to pool all vectors from all vector sets into a single ANN index, e.g., IVFPQ (Jégou et al., 2011) or diskANN (Jayaram Subramanya et al., 2019). 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, 10k10k documents with 100100 vectors each lead to a million-level ANN task. Another proposal (Jayaram et al., 2024), 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 (Engels et al., 2023) is the first solution designed natively for multi-vector retrieval. It compresses the vector set into a sketch via locality-sensitive hashing (LSH) (Charikar, 2002; Datar et al., 2004), 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 Graph-based indEx framework for Multi-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) (Rubner et al., 2000). As EMD is a well-established metric that satisfies the triangle inequality and upper-bounds the MaxSim, the EMD-based graph could provide a stable and reliable basis for navigating toward high-quality results. In addition, GEM introduces semantic shortcuts to bridge the gap between the two similarity measures. These shortcuts directly connect vertices that are semantically similar but distant in the graph, accelerating search and helping escape local optima. Furthermore, GEM employs quantized versions of EMD and MaxSim. This replaces expensive set-to-set distance calculations with efficient lookups over a centroid codebook, significantly enhancing both indexing and querying efficiency. Finally, a cluster-guided multi-entry search algorithm is developed on top of the proposed index. The search begins from multiple entry points within multiple promising clusters and expands over the graph in parallel. Meanwhile, a cluster-guided pruning mechanism prevents the search from drifting into irrelevant regions, effectively balancing speed and accuracy. In summary, we make the following contributions: • We propose GEM, the first native graph index for multi-vector retrieval. It successfully unifies the semantic richness of multi-vector representations with the pruning efficiency of graph-based indexing, delivering both high accuracy and efficiency. • GEM introduces a series of architectural and algorithmic innovations tailored to the unique challenges of multi-vector search. The architecture adopts a dual graph design with metric decoupling and semantic shortcuts, ensuring a navigable graph topology for accurate search. These are integrated with a novel semantic clustering algorithm, a cluster-aware multi-entry search algorithm, and quantized distance estimation, achieving full end-to-end efficiency across large-scale vector-set collections. • Extensive experiments on in-domain, out-of-domain, and multi-modal benchmarks show that GEM significantly outperforms the state-of-the-art methods in both retrieval quality and latency, with a comparable or even smaller index size and indexing time. The rest of the paper is organized as follows. Section 3 defines the problem and introduces a straightforward graph-based solution. Our GEM framework is detailed in Section 4, followed by experimental results in Section 5. Section 2 reviews related work, and we conclude in Section 6. 2. Related Work 2.1. Single-Vector ANN Search The ANN search problem has been extensively studied in the database community for decades (Tian et al., 2023a). However, nearly all well-known methods make the single-vector representation assumption, i.e., both queries and data are encoded as single high-dimensional vectors in the same Euclidean space. Prominent approaches include LSH-based methods (Lei et al., 2020; Tian et al., 2022, 2024; Huang et al., 2015; Lu et al., 2020; Zheng et al., 2020; Liu et al., 2021), quantization-based methods (Jégou et al., 2011; Ge et al., 2014; Gao and Long, 2024; Gao et al., 2025), and graph-based methods (Malkov and Yashunin, 2020; Fu et al., 2019; Muñoz et al., 2019; Jayaram Subramanya et al., 2019; Zhao et al., 2023; Wang et al., 2024). LSH-based methods are well-known for the strong theoretical guarantees on recall. Quantization-based methods significantly reduce memory usage and accelerate distance calculations. Graph-based methods, which construct a proximity graph among vectors and find neighbors via greedy traversal, have become the de facto state-of-the-art, demonstrating superior performance in both secch accuracy and efficiency. 2.2. Multi-Vector ANN Search Multi-vector search is a relatively new paradigm that has seen rapid adoption across various domains due to its high effectiveness (Khattab and Zaharia, 2020; Khattab et al., 2021a; Paranjape et al., 2022; Li et al., 2022). Unlike single-vector approaches, which alleviate information loss by increasing dimensionality but exacerbate the curse of dimensionality, multi-vector models capture complex semantics from a different angle: they represent an object with multiple simpler (e.g., not very high-dimensional) vectors. It is first introduced for document retrieval by ColBERT (Khattab and Zaharia, 2020), which represents queries and documents as sets of token-level embeddings and employs a late interaction architecture to achieve strong performance. Subsequent work further improved the effectiveness of this paradigm, for instance, by learning different weights for vectors of varying importance (Hofstätter et al., 2022), or expanding it to other domains such as visual-language retrieval tasks (Lin et al., 2024; Yao et al., 2022). However, early research relies on simple inverted lists to index all individual embeddings, which hinders large-scale deployment. To improve scalability, ColBERTv2 (Santhanam et al., 2022b) introduces a centroid-based compression scheme, where each token embedding is stored using the ID of its closest centroid and a low-bit residual (1–2 bits per component), significantly reducing storage overhead. However, the search process remains costly. PLAID (Santhanam et al., 2022a) builds on this by further exploiting the centroids to aggressively prune irrelevant documents via a centroid interaction mechanism, substantially accelerating retrieval. EMVB (Nardini et al., 2024) enhanced PLAID with system-level optimizations, including bit-vector filtering and SIMD-accelerated scoring. More recently, IGP (Bian et al., 2025) proposes to replace the inverted list with a proximity graph index over centroid vectors and develops an incremental next-similar retrieval technique to efficiently filter low-relevance candidates. Alternative indexing strategies have also been explored. MUVERA (Jayaram et al., 2024) introduces fixed-dimensional encodings (FDEs) that approximate multi-vector similarity, enabling the use of optimized single-vector ANN indexes. While efficient, this method inevitably loses token-level alignment, risking reduced recall. DESSERT (Engels et al., 2023) proposes compressing vector sets into compact sketches, but its speedup is often limited by a lack of effective set-level pruning. Orthogonal to the research on indexing and search algorithms, XTR (Lee et al., 2023) improves retrieval efficiency by simplifying the scoring mechanism during training. CITADEL (Li et al., 2023b) reduces computation cost by selectively considering only a subset of tokens. POQD (Liu et al., 2025) enhances accuracy by optimizing query decomposition with the assistance of LLMs. Since these approaches optimize the set-level representation itself, they can complement the above indexing methods for higher search accuracy and efficiency. 3. Preliminary In this section, we formulate the multi-vector retrieval problem and introduce a baseline solution. 3.1. Problem Definition We first clarify the similarity measurement used throughout this paper. Following ColBERT (Khattab and Zaharia, 2020) and other state-of-the-art multi-vector methods (Khattab and Zaharia, 2020; Lin et al., 2024; Santhanam et al., 2022a; Engels et al., 2023; Jayaram et al., 2024; Bian et al., 2025), we adopt the MaxSim operator, a.k.a. Chamfer similarity, to compute the similarity score between two multi-vector sets. In the following, we choose the terminology Chamfer (CH) due to its historical precedence (Bakshi et al., 2023; Jayaram et al., 2024). Definition 0 (Similarity score). Given two sets of vectors A,B⊆ℝdA,B ^d, the similarity score is defined as the sum of the maximum similarity between each vector in A and all vectors in B. Formally, (1) CH(A,B)=∑a∈Amaxb∈B⁡Sim(a,b), CH(A,B)= _a∈ A _b∈ BSim(a,b), where cosine similarity or L2L_2 distance are typically used as the default choices for Sim(⋅,⋅)Sim(·,·) in prior work. Problem Statement 0 (multi-vector retrieval problem). Given a database =P1,P2,…,PND=\P_1,P_2,…,P_N\, where each Pi=p1,p2,…,P_i=\p_1,p_2,…, pmip_m_i\ is a set of vectors with each pj∈ℝdp_j ^d, and a query Q=q1,q2,…,Q=\q_1,q_2,…, qmqq_m_q\ with each qj∈ℝdq_j ^d, the multi-vector retrieval problem, a.k.a. the vector set search problem, aims to return the top-k sets in D that are most similar to Q, namely: (2) ℛ=k-arg⁡max⁡CH(Q,P)|P∈.R=k- \ CH(Q,P)|P \. Remark 1. Multi-vector retrieval has been widely adopted in various domains and systems (Reddy et al., 2025; Khattab and Zaharia, 2020; Khattab et al., 2021a; Paranjape et al., 2022; Li et al., 2022). A prominent example is ColBERT (Khattab and Zaharia, 2020) for document retrieval, where queries and documents are encoded into sets of token-level vectors. Throughout this work, we use the terms ”document” and ”vector set” interchangeably, as well as ”token” and ”vector” interchangeably. However, it is worth noting that multi-vector retrieval itself is a general problem, agnostic to the data’s origin. A ”vector” could represent an image patch, a chunk of text, or other forms of data. 3.2. A Baseline Solution Recall the ANN search problem in the traditional single-vector setting: both data and queries are represented as high-dimensional vectors, and the goal is to find the top-k most similar (i.e., closest) data points to a given query based on certain distance functions (e.g., L2L_2 distance). Formally, given a dataset =o1,…,oND=\o_1,...,o_N\ with each data object oi∈ℝdo_i ^d and a query q∈ℝdq ^d, it aims to return (3) ℛ=k-argmin∥q,oi∥2|oi∈.R=k- \\|q,o_i\|_2|o_i \. Among ANN solutions, graph-based methods have demonstrated the best trade-off between search accuracy and efficiency on real-world datasets. These methods organize the base vectors into an approximate proximity graph (APG), where each vertex corresponds to a data vector, and edges connect vertices that are sufficiently similar. During query time, a greedy (beam) search is performed on the graph: it starts from an arbitrary vertex and iteratively traverses edges toward neighbors that are closer to the query, until convergence to a local optimum. Inspired by the success of graph-based indexes in the single-vector setting, we pose a question: Can we build a set-level APG? In such a graph, each vertex represents a vector set, and an edge connects two sufficiently similar vertices based on the Chamfer distance. The graph construction and search processes are the same as those in single-vector methods, so we omit them here for brevity. Unfortunately, this direct extension does not work due to two critical issues: (1) Fragmented neighbors and local optima. Chamfer distance is not a metric and lacks triangle inequality, which undermines core assumptions behind graph-based search. For example, even if Q is close to P1P_1 and P1P_1 is close to P2P_2, Q may still be far from P2P_2. As a result, the nearest neighbors of Q are scattered across the graph, making them difficult to reach via local hops and slowing down convergence. Without strong connectivity among these neighbors, greedy search paths become oscillatory and unstable, often getting trapped in local optima—terminating early even when better candidates exist several hops away, ultimately degrading recall. (2) Lack of cheap distance approximation and pruning. While graph structures provide a powerful pruning framework, the exorbitant cost of computing the Chamfer distance remains a critical bottleneck. It is impractical to perform set-to-set comparisons between the query and all candidate neighbors at each step of the search traversal. A practical solution, therefore, necessitates a cheaper distance approximation, effective pruning strategies, and more informed entry points. We will empirically validate these analyses in Section 5, where this naive approach, named MVG, is included as a baseline. 4. GEM To address the limitations of existing approaches and the challenges exposed by the naive graph-based solution, we propose GEM — a native Graph-based indExing framework for efficient Multi-vector retrieval. The key innovations are as follows: (1) We propose a set-level clustering scheme, where each document is assigned to only a small number of semantically relevant clusters, guided by adaptive TF-IDF–style weighting over centroids. This reduces index redundancy while preserving semantic coverage (Section 4.1 and Section 4.4.2). (2) We design a novel dual graph structure, featuring both intra-cluster graphs and a unified global graph naturally bridged by sets shared between clusters. This design guarantees global connectivity while preserving local structure (Section 4.3). (3) We decouple the similarity measures used for graph construction and search: Earth Mover’s Distance (EMD) (Rubner et al., 2000) is used for graph construction due to its metric properties, while Chamfer distance is retained for search. Since EMD upper bounds Chamfer, vertices that are close under EMD are also close under Chamfer, ensuring reasonable navigation. We further augment the graph with shortcuts, directly linking semantically close pairs under Chamfer, but may require several hops under EMD, which improves search efficiency and helps escape local optima (Section 4.3.1 and Section 4.4.1). (4) We introduce quantized versions of EMD and Chamfer to alleviate the high cost of set-to-set similarity computation. By leveraging centroid-level codebooks and quantized representations derived from cluster centroids, we improve the efficiency of both the indexing and search phases (Sections 4.2.2 and Section 4.5). (5) We devise a new cluster-guided, multi-entry search strategy. The search is initialized from multiple semantically relevant clusters, enabling parallel, layer-wise expansion over the global graph. A cluster-guided early pruning mechanism aggressively culls unpromising paths, preventing the search from drifting into irrelevant regions (Section 4.5). Figure 2. Two-Stage Clustering Figure 3. Cluster Assignment with TF-IDF 4.1. Set-Level Clustering 4.1.1. Two-Stage Clustering To facilitate efficient filtering and quantization, we begin with a two-stage clustering step. In the first stage, we perform k-means clustering on a sample of vectors across all sets in D to obtain a set of centroids quant=C1,C2,…,Ck1C_quant=\C_1,C_2,…,C_k_1\. These centroids serve as a vocabulary for our subsequent quantized distance approximations, i.e., qEMD during graph construction to be introduced in Section 4.2.2 and qCH during search in Section 4.5.3. In the second stage, we cluster quantC_quant into a smaller set of coarser centroids index=C1′,C2′,…,Ck2′C_index=\C _1,C _2,…,C _k_2\, which defines a cluster space for set-level indexing. As illustrated in Figure 2, all vectors are first grouped into 8 fine-grained clusters, which are then organized into 3 coarse clusters that serve as higher-level semantic bins. Then, we assign each vector p∈Pp∈ P to its nearest cluster centroid in indexC_index, denoted as N(p)N(p). As a result, a set P=p1,p2,…,pmP=\p_1,p_2,…,p_m\ is approximately represented as a set of centroids: (4) (P)=N(p1),N(p2),…,N(pm). (P)=\N(p_1),N(p_2),…,N(p_m)\. To obtain a set-level clustering, a naive way is to associate a set with every cluster if one or more of its tokens are assigned to that centroid. For example, P3P_3 is linked to all three clusters C1′,C2′,C3′C _1,C _2,C _3. However, this can cause a vector set to appear in an excessive number of clusters, especially when it contains uninformative tokens, such as ”is”, ”the”, and ”of”. This leads to index redundancy and increased query-time overhead. Motivated by the unequal semantic contribution of tokens, we introduce a TF-IDF-guided pruning strategy in the following. 4.1.2. TF-IDF Guided Cluster Pruning The key idea is that: retain only clusters associated with important tokens, while ignoring uninformative ones. This way, a set is expected to be assigned to only a few salient clusters, which help reduce index redundancy while preserving the semantic richness of multi-vector representations. To achieve this, we design a TF-IDF–style importance score over the centroid vocabulary indexC_index to reflect how salient the cluster is to the set P. Specifically, we define ”term frequency” (TF) as: (5) TF(Cj′,P)=|p∈P:N(p)=Cj′,Cj′∈index|, (C _j,P)=|\p∈ P:N(p)=C _j,C _j _index\|, which counts how many token vectors in P are associated with a cluster CjC_j. Then, we apply an ”inverse document frequency” (IDF) to downweight clusters shared across many sets: (6) IDF(Cj′)=log⁡N1+|P′∈:TF(Cj′,P′)>0|, (C _j)= N1+|\P :TF(C _j,P )>0\|, where N is the number of vector sets in the database. The overall TF-IDF score is: (7) Score(Cj′,P)=TF(Cj′,P)⋅IDF(Cj′). (C _j,P)=TF(C _j,P)·IDF(C _j). We then construct a weighted centroid profile for each document: (8) (P)=[(Cj1′,sj1),(Cj2′,sj2),…,(Cjm′,sjm)], (P)= [(C _j_1,s_j_1),\,(C _j_2,s_j_2),\,…,\,(C _j_m,s_j_m) ], where sjt=Score(Cjt′,P)s_j_t=Score(C _j_t,P) indicates how strongly cluster Cjt′C _j_t represents the semantics of P. Based on this profile, we assign P to the top-r clusters with the highest TF-IDF scores: (9) top(P)=Top-rCj′∈C(P)Score(Cj′,P). _top(P)=Top-r_C _j∈ C(P)\,Score(C _j,P). Figure 3 provides a concrete example of this pruning. For P3P_3, our TF-IDF guided mechanism identifies that its connection to cluster C3′C _3 is weak (score of 1.61.6). Therefore, only the two clusters with high semantic relevance (scores 18.418.4 and 12.612.6) are selected as its indexing targets. This pruning step ensures that each document is linked only to its most representative clusters, improving both graph construction efficiency and candidate generation efficiency. Figure 4. Average # of Clusters Each Set is Assigned to Remark 2. Clearly, there is no single r value that works best for all: some sets are well represented by a few clusters, while others may require broader cluster coverage. We defer the details of how to determine r adaptively to Section 4.4.2. Discussion 1. PLAID adopts a similar clustering idea, but differs from our approach in two aspects. It performs only fine-grained token-level clustering and directly assigns each document to every cluster that any of its tokens maps to. However, we found this strategy less suitable for our graph-based indexing framework. In particular, PLAID’s large number of fine-grained clusters results in very few documents per cluster (e.g., often only dozens), making it unnecessary and inefficient to build a graph index per cluster. Moreover, the high redundancy in cluster memberships results in costly graph construction and many redundant edges during query processing. Therefore, to better support our graph-based design, we adopt the fine-grained clustering in the first stage for accurate distance approximation, while second-stage coarser clusters, combined with TF-IDF pruning, significantly reduce per-document cluster memberships, striking a better balance between granularity and efficiency. Figure 4 compares the average number of clusters each document is assigned to under different strategies across four datasets. The PLAID bars correspond to PLAID’s default configuration with 260K260K fine-grained clusters, resulting in high redundancy. The Ours (40K, w/o TF-IDF) bars represent a coarser 40K-cluster setup without applying TF-IDF guided cluster filtering, while the Ours (40K, w/ TF-IDF) bars show the results after pruning. As shown, our approach dramatically reduces the number of cluster memberships, e.g., from 43.8 to 2.9 on MSMARCO (a 93.4% reduction), from 94 to 5.8 on LOTTE (93.8%), from 76 to 3 on OKVQA (96%), and from 120.8 to 1.7 on EVQA (98.6%), alleviating index redundancy while preserving semantic coverage. 4.2. Metric Decoupling and Quantization 4.2.1. Metric Decoupling Figure 5. Overview of Global Graph Construction As discussed in Section 3.2, multi-vector similarity lacks the metric properties required to serve as a reliable foundation for building a stable and navigable APG. To address this issue, we propose using EMD (Rubner et al., 2000) as the edge weight metric, while performing search based on the original Chamfer distance. EMD is a well-established distance function that satisfies the triangle inequality, ensuring a well-structured graph topology with guaranteed monotonicity. A key insight supporting this metric decoupling is the bounding relationship between EMD and Chamfer distance. It can be proven that for any two vector sets Q and P: (10) CH(Q,P)≤EMD(Q,P). (Q,P) (Q,P). This inequality implies that if two sets are close under EMD, they are at least as close–if not closer–under Chamfer distance. Consider a search path that is currently at vertex P1P_1, then the distance from P1P_1 to its neighbor P2P_2 has a predictable upper bound: CH(Q,P2)≤EMD(Q,P2)≤EMD(Q,P1)+EMD(P1,P2)CH(Q,P_2)≤ EMD(Q,P_2)≤ EMD(Q,P_1)+EMD(P_1,P_2). Consequently, navigating toward the nearest neighbor under EMD is a reliable heuristic for finding a reasonable candidate in the Chamfer space. This mitigates oscillatory search behavior and the local optima trap. EMD is formally defined as follows: given two vector sets P1=p1,…,pm1P_1=\p_1,…,p_m_1\ and P2=p1′,…,pm2′P_2=\p _1,…,p _m_2\, and a transport plan T=tijT=\t_ij\, then (11) EMD(P1,P2)=minT∑i=1m1∑j=1m2tij⋅dX(pi,pj′) (P_1,P_2)= _T _i=1^m_1 _j=1^m_2t_ij· d_X(p_i,p _j) subject to the following constraints: (12) ∑j=1m2tij=1m1,∑i=1m1tij=1m2,tij≥0 _j=1^m_2t_ij= 1m_1, _i=1^m_1t_ij= 1m_2, t_ij≥ 0 where dX(pi,pj′)=1−⟨pi,pj′⟩d_X(p_i,p _j)=1- p_i,p_j when cosine similarity is used, and dX(pi,pj′)=∥pi,pj′∥2d_X(p_i,p _j)=\|p_i,p_j \|_2 when the L2L_2 distance is adopted. 4.2.2. Quantization While EMD offers desirable properties for graph construction, its exact computation is prohibitively expensive (Andoni et al., 2008; Charikar, 2002; Lv et al., 2004, 2006; Grauman and Darrell, 2006). To make EMD practical at scale, we introduce an efficient quantized approximation. The key idea is to replace expensive token-level distance computations in EMD with efficient centroid-level approximations by leveraging the shared centroid vocabulary quantC_quant derived from k-means clustering (Section 4.1.1). Specifically, each token vector is first mapped to its nearest centroid in quantC_quant, and the distance between raw vectors is then approximated by the distance between their corresponding assigned centroids, formalized as: (13) dX(pi,pj′)≈dX(N(pi),N(pj′)), d_X(p_i,p _j)≈ d_X(N(p_i),N(p _j)), where N(pi)N(p_i) and N(pj′)N(p _j) ∈quant _quant. This quantization brings two key computational benefits. First, all centroid-to-centroid distances can be precomputed and stored in a k1×k1k_1× k_1 codebook, enabling constant-time distance lookups instead of costly high-dimensional distance calculations. Second, the reduced centroid space generates significantly sparser transport plans, which further accelerate EMD computation. Formally, the quantized EMD (qEMD) is as follows: (14) qEMD(P1,P2)=minT∑i=1n1∑j=1n2tij⋅dX(N(pi),N(pj′)). (P_1,P_2)= _T _i=1^n_1 _j=1^n_2t_ij· d_X(N(p_i),N(p _j)). Input: Database D, two-stage cluster counts k1,k2k_1,k_2, degree limit M, parameter f, training pairs T, Output: GEM proximity graph G 1 Initialize G with V=V=D and E=∅E= ; 2 quant,index,top←C_quant,C_index,C_top\;← ClusterAndAssign(,k1,k2D,k_1,k_2) ; 3 foreach Ci∈indexC_i _index do 4 G←G← LocalGraphandBridges(Ci,quant,top,f,MC_i,C_quant,C_top,f,M); ⊳ Alg. 2 5 6G←G← InjectShortcuts(G,,MG,T,M); ⊳ Alg. 4 return G Algorithm 1 Index Construction Pipeline 4.3. Graph Construction Building upon the set clustering and distance function introduced earlier, this section details the construction of GEM’s dual-graph structure. Algorithm 1 outlines the indexing pipeline. 4.3.1. Cluster-Level APG with qEMD For each cluster CiC_i, we invoke LocalGraphandBridges (Line 1 in Algorithm 1) to build a cluster-level graph while handling cross-cluster bridges. Specifically, for each vector set P∈CiP∈ C_i, we find its top-f ANNs by performing the search algorithm (Algorithm 5) over the current cluster graph, starting from an arbitrary entry point in CiC_i and using qEMD as the distance metric (Line 2 in Algorithm 2). If P is new to the current graph G (Line 2), we directly connect it to its neighbors (Line 2) and ensure that each neighbor P′P does not exceed the degree limit M by removing the least similar edges if necessary (Line 2). Otherwise, P has already been inserted in previous clusters Ci∣i<j,Ci∈top(P)\C_i i<j,\,C_i _top(P)\, which means P can serve as a cross-cluster bridge. In this case, we invoke UpdateBridges (Algotihrm 3) to merge the old and new neighbor candidates (Line 2), as detailed in the next section. Input: Cluster CiC_i, current global graph G=(V,E)G=(V,E), top(⋅)C_top(·), f, M Output: Updated global graph G 1 2foreach P∈CiP∈ C_i do 3 C←C← f ANNs of P in the current graph of CiC_i by qEMD; ⊳ Alg. 5 4 5 if E[P]=∅E[P]= then 6 foreach P′∈CP ∈ C do 7 Add a bidirectional edge (P,P′)(P,P ) to E; 8 if degree of P′>MP >M then 9 Remove the least similar edge from E[P′]E[P ]; 10 11 12 13 else 14 G←G← UpdateBridges(P,C,G,top(P),MP,C,G,C_top(P),M); ⊳ Alg. 3 15 return G Algorithm 2 Build Cluster Graph with Cross Bridges 4.3.2. Global Graph via Cross-Cluster Bridges Cluster-level graphs offer good local navigability, but cluster-by-cluster traversal is inefficient and duplicating sets across clusters introduces redundancy. This motivates weaving cluster-level graphs into a single, globally connected graph via bridge sets. As shown in Algorithm 3, for a bridge set P, we gather both the neighbors already connected to P from earlier clusters and the new neighbors identified in the current cluster (Line 3-3). If the total number of neighbors is within the degree limit M, we retain them all (Line 3). Otherwise, only top-M closest neighbors are retained (Line 3). To ensure P preserves its role as bridges, we enforce that at least one neighbor from each cluster in top(P)C_top(P) is included in the final neighbor set (Line 3-3). For example, if P belongs to clusters C2′C _2 and C4′C _4, this step ensures its final neighbor list will contain at least one neighbor from C2′C _2 and one from C4′C _4. This prevents newly added connections from overwriting prior inter-cluster links and preserves global connectivity. Finally, the neighborhood of P is updated to reflect the new connection set (Line 3). Note that each P corresponds to a unique vertex in the global graph: logically assigned to multiple clusters, but physically stored as a single shared node. This design maintains intra-cluster structural coherence, supports efficient cross-cluster traversal via inter-cluster bridges, and eliminates redundant vertex duplication. Example 0. Figure 5 further illustrates the graph construction process. In Figure 5(a), P3P_3 is assigned to cluster C1′C _1 based on its informative vectors (solid-edge circles). Within the cluster, a local graph is constructed using qEMD-based similarity. Since P3P_3 also belongs to another cluster C2′C _2, it becomes a natural bridge between clusters, as shown in Figure 5(b). Figure 5(c) presents a complete toy example of the resulting dual-graph structure. Input: Set P, new neighbors CnewC_new, G=(V,E)G=(V,E), top(P)C_top(P), M Output: Updated global graph G 1 2Cold←C_old← existing neighbors of P in E; 3 Call←Cnew∪ColdC_all← C_new∪ C_old; 4 5if |Call|≤M|C_all|≤ M then 6 Cfinal←CallC_final← C_all; 7 8else 9 Cfinal←C_final← M closest vertices of P in CallC_all by qEMD; 10 11 foreach Ci∈top(P)C_i _top(P) do 12 if Cfinal∩Ci=∅C_final∩ C_i= then 13 Si←P∈Call∣P∈CiS_i←\P∈ C_all P∈ C_i\; 14 Replace farthest in CfinalC_final with closest node from SiS_i; 15 16 17 18 19Replace E[P]E[P] with edges (P,P′)(P,P ) for all P′∈CfinalP ∈ C_final; 20 return G Algorithm 3 Update Bridges Input: Graph G=(V,E)G=(V,E), training pairs T, M Output: Augmented GEM graph G 1 2foreach (Q,P)∈(Q,P) do 3 C←C← f′f ANN results for Q in G; 4 5 if PID∉CPID∉ C and both Ptop,P_top,P have degree ≤M≤ M then 6 Ptop←P_top← 1-ANN in C; 7 Add a undirected edge (Ptop,P)(P_top,P) to E; 8 9 return G Algorithm 4 Inject Shortcuts 4.4. Graph Enhancement 4.4.1. Inject Shortcuts We observed that some queries may require many short hops to reach a relevant result. This issue arises because, while EMD upper-bounds the Chamfer distance, the reverse does not hold. As a result, two vector sets may be close under Chamfer but remain distant in EMD space, preventing direct connections during graph construction and leading to longer traversal paths at query time. To mitigate this, we propose a lightweight supervised graph augmentation technique that injects semantic shortcuts into the graph index. A shortcut is a direct edge connecting two vertices that are labeled as semantically close but might be distant in the graph. As detailed in Algorithm 4, we leverage training pairs (Q,P)(Q,P), where P is the human-annotated ground-truth to answer the query Q, to augment the graph. Note that generating the training pairs does not require additional labeling effort or exhaustive search. In this work, we simply re-use training sets that are widely used to train LLMs for generating vector representations of data. For example, on MSMARCO dataset, to be introduced in Section 5.1.1, provides “forms of training data, usually with one positive passage per training query,” where a positive passage means “there is a direct human label that says the passage can be used to answer the query.” Here, we randomly sample from these existing training pairs to construct the shortcuts. For each pair, we run the search algorithm (Algorithm 5) over the current graph to find the query’s top-f′f ANNs (Line 4). If P is not among them and both PtopP_top and P have remaining degree capacity, we add an edge between them (Line 4-4). Since test queries are generally assumed to follow a similar distribution as the training data, such edges act as a shortcut, allowing future queries to reach the correct region more directly. As illustrated in Figure 6, the shortcut helps the search bypass long paths and suboptimal results. By adding EMD-based structural connectivity with Chamfer-based semantic alignment, we enhance graph reachability, search efficiency, and accuracy. Figure 6. Graph Enhancement via Shortcuts 4.4.2. Adaptive Cluster Cutoff As discussed in Section 4.1.2, a fixed cut-off threshold r is suboptimal. To address this, we introduce an adaptive technique that employs a lightweight decision tree classifier (Pedregosa et al., 2011) to predict an optimal per-set r. Our key idea is to retain the minimum cluster representation required for search-time discoverability. Specifically, we first generate rlabelr_label for each training pair (Q,P)(Q,P). The label is defined as the rank of the first cluster in the TF-IDF-sorted profile (P)S(P) that intersects with Q’s relevant cluster set query(Q)C_query(Q). If no intersection occurs within the top-rmaxr_max (default 10), the label is set to rmaxr_max. Then, the decision tree is trained with the top-rmaxr_max TF-IDF scores (padded if necessary) and the number of vectors in P as input, and learn to predict the number of clusters r to retain. During the indexing pipeline, the trained model infers per-set r, which is then used for final cluster assignments. This strategy effectively reduces the number of redundant assignments while preserving the necessary semantic coverage for effective retrieval. 4.5. Query Processing Input: Query Q, G, quantC_quant, indexC_index, parameters t,ef,kt,ef,k Output: k ANNs to Q 1 2Compute relevance scores Sc,q=C⋅Q⊤S_c,q=C· Q ; 3 4query←C_query← union of top-t centroids for each qi∈Qq_i∈ Q; 5 6E←E← one random node from each Cj∈queryC_j _query; 7 8Initialize a shared result heap ℛ←ER← E, a shared visited set ←EV← E; 9 Initialize a local queue epW_ep for each ep∈Eep∈ E; 10 while any epW_ep is not empty do 11 foreach non-empty epW_ep in parallel do 12 P←P← pop the element in epiW_epi cloest to Q by qCH; 13 τ←τ← current furthest distance in ℛR; 14 if qCH(Q,P)>τ(Q,P)>τ then 15 mark epW_ep as empty; 16 continue; 17 18 19 foreach P′∈Neighbors(P)P (P) do 20 if P′∉P and top(P′)∩query≠∅C_top(P ) _query≠ then 21 compute qCH(Q,P′)qCH(Q,P ); 22 insert P′P into epW_ep, V, and ℛR; 23 if |ℛ|>ef|R|>ef then 24 Remove the furthest from R; 25 26 27 update τ; 28 29 30 31ℛ←R← rerank top-k results in ℛR by CH; return ℛR Algorithm 5 Cluster-Guided Beam Search Building on our index structure, we propose a cluster-guided beam search algorithm tailored for efficient multi-vector retrieval. The complete search procedure is detailed in Algorithm 5. At a high level, the algorithm improves upon traditional single-vector greedy search from three complementary perspectives: (1) coarse-grained cluster filtering, (2) informative multi-entry point initialization, and (3) cluster-aware early pruning during graph traversal. 4.5.1. Cluster Filtering In multi-vector retrieval, distance computations are significantly more expensive than in the single-vector setting. To reduce this cost, it is crucial to eliminate highly unlikely vector sets as early as possible—ideally before any graph traversal begins. For this purpose, we draw inspiration from the initial filtering phase of ColBERTv2, which is extremely fast for coarse candidate selection. While this strategy alone may yield a large number of false positives, our downstream graph traversal module can refine these results with high precision. This rationale leads us to retain ColBERTv2’s initial filtering strategy to generate coarse-grained cluster candidates. Specifically, we compute a query–centroid relevance matrix: (15) Sc,q=C⋅Q⊤, S_c,q=C· Q , where C∈ℝk2×dC ^k_2× d is the centroid matrix and Q∈ℝmq×dQ ^m_q× d is the query token matrix. For each query token qiq_i, we select its top-t nearest centroids and take the union across all tokens to form a relevant cluster set query⊆C_query . This early pruning step is shown in Line 5-5 in Algorithm 5 and visually illustrated in Figure 7, where irrelevant clusters (in gray) are filtered out before the graph traversal. 4.5.2. Multi-Entry Point Initialization Since relevant sets under the Chamfer distance may be distributed across multiple clusters, relying on a single entry point can lead to biased initialization and longer traversal paths. Therefore, after identifying the relevant clusters, we initialize the search from multiple entry points, one from each cluster in queryC_query (Line 5). As shown in Figure 7, two yellow vertices (ep1 and ep2) from two different clusters are randomly selected as the initial entry points. This multi-entry strategy, combined with the semantic shortcuts on the index side, effectively mitigates the fragmentation of Chamfer nearest neighbors and enhances overall retrieval effectiveness. 4.5.3. Cluster-Guided Parallel Beam Search Given the selected entry points, we perform a cluster-guided, multi-path parallel search over the graph G using quantized Chamfer distance (qCH). Similar to qEMD, qCH serves as a lightweight yet effective proxy for the expensive pairwise computation between vector sets, formalized as follows: (16) qCH(Q,P)=∑q∈Qminp∈P⁡dX(N(q),N(p)), (Q,P)= _q∈ Q _p∈ Pd_X(N(q),N(p)), where N(⋅)N(·) is the nearest centroids in quantC_quant. As elaborated before, although Chamfer is not used during index construction, it is upper-bounded by the EMD metric, leading that EMD-near neighbors are also reasonable candidates under Chamfer. Line 5- 5 in Algorithm 5 details the query process. First, we initialize a global result heap ℛR, a global visited set V, and a local priority queue epW_ep for each entry point ep∈Eep∈ E (Line 5-5). The search then proceeds in parallel from these entry points. Within each thread, we repeatedly pop the element P with the lowest qCH to the query (Line 5) until epW_ep is empty (Line 5). We denote τ as the current furthest distance to Q in ℛR. If qCH(Q,P)qCH(Q,P) is already worse than τ, the current path is deemed unpromising and terminated (Line 5-5). Otherwise, we continue expanding P’s neighbors. To boost query efficiency, we apply a cluster-aware pruning condition (Line 5). That is, if P′P would pull the search into an irrelevant cluster (one not in queryC_query), it is directly filtered out. If the P′P passes this filter, the qCH score is computed, and the local queue epW_ep, result heap ℛR, and visited set V are updated accordingly (Line 5-5). ℛR maintains a maximum of efef candidates, evicting the farthest node when necessary (Line 5-5). Note that both ℛR and V are globally shared across threads, enabling implicit communication. If one path discovers a closer node, it updates the τ (Line 5), which allows other paths to prune their search space earlier. Similarly, once a vertex is visited by any thread, it is skipped by all others, preventing redundant computation. The search terminates when all epW_ep queues are exhausted. In the final step, the top-k candidates in ℛR are re-ranked using exact Chamfer distance before being returned. Figure 7. Search in GEM Example 0. Figure 7 gives an example of the GEM search process for 1-ANN with ef=2ef=2. P1P_1 is the ground-truth nearest neighbor. Assume that the cluster filtering stage identifies two relevant clusters, query=C1′,C2′C_query=\C _1,C _2\, while pruning C3′C _3 and C4′C _4. The search then begins in parallel from two entry points: ep1 and ep2 (yellow squares). In the first iteration (labeled with 1), the path of ep1 expands to P2P_2, while ep2 discovers P3P_3. These two candidates are inserted into the shared result heap ℛR. In the second iteration (labeled with 2), the path from ep1 continues by expanding from P2P_2. When considering its neighbors, P4P_4 is immediately pruned without a distance calculation because it resides in a pruned cluster. Concurrently, the other path expanding from P3P_3 jumps directly to P1P_1 via a semantic shortcut (highlighted in red), bypassing what would otherwise have been a multi-hop traversal. 4.6. Index Maintenance As a graph-based method, GEM naturally supports dynamic index maintenance, including both insertion and deletion of data points. To insert a new vector set into the current index, GEM first maps its vectors to the fine-to-coarse centroid hierarchy and prunes uninformative clusters using the TF-IDF–guided strategy, as described in Section 4.1. Then, the set is incorporated into the graph by linking it to its nearest neighbors under the qEMD metric, followed by updating the cross-cluster bridges to maintain both local proximity and global connectivity, as detailed in Section 4.3. For deletions, we follow the lazy deletion strategy (Malkov and Yashunin, 2020), which is commonly used in graph-based indexes: a vertex to be removed is simply marked as inactive, so it is skipped during search and can be physically pruned in later maintenance passes. 5. Experiments In this section, we conduct extensive experiments on real-world datasets to evaluate our GEM. We implement GEM111https://github.com/sigmod26gem/sigmod26gem in C++ compiled with g++ using -Ofast optimization and openMP for parallelism. All experiments are run on a Ubuntu server with 4 Intel(R) Xeon(R) Gold 6218 CPUs (160 threads) and 1.5 TB RAM. 5.1. Experimental Settings 5.1.1. Datasets. Table 1. Summary of Datasets Datasets # Corpus # Vectors # Queries Modality MS MARCO v1 333MSMARCO weblink, LoTTE webLink, OK-VQA weblink, EVQA weblink 8.8M 597M 6980 Text-only LoTTe pooled 333MSMARCO weblink, LoTTE webLink, OK-VQA weblink, EVQA weblink 2.4M 339M 2931 Text-only OK-VQA 333MSMARCO weblink, LoTTE webLink, OK-VQA weblink, EVQA weblink 114K 14M 5046 Text + Image EVQA 333MSMARCO weblink, LoTTE webLink, OK-VQA weblink, EVQA weblink 50K 9.7M 3750 Text + Image We evaluate GEM’s performance on four widely-used multi-vector retrieval benchmarks, which are detailed in Table 1. MS MARCO v1 is widely used for in-domain evaluation with a retriever trained specifically for this task, while LoTTE serves as an out-of-domain benchmark. To further evaluate performance in complex multi-modal settings, we include two vision-language retrieval datasets, OK-VQA and EVQA, both involving queries with textual and visual content. All four datasets provide training and test splits, in which each query is paired with one or more human-annotated relevant document IDs. The training instances are used to enhance the graph, while queries from the test split are used to evaluate retrieval performance, with the corresponding relevance annotations treated as ground truth. For MS MARCO and LoTTE, we employ ColBERTv2 (Santhanam et al., 2022b) to encode queries and documents into sets of vectors. Following prior work (Santhanam et al., 2022a; Engels et al., 2023; Jayaram et al., 2024; Bian et al., 2025), the dimensionality of each individual vector is set to d=128d=128 by default. For multi-modal datasets, we adopt preFLMR (Lin et al., 2024), a fine-grained late-interaction retriever that jointly encodes text and image content into multi-vector representations (d=128d=128). Both ColBERTv2 and preFLMR adopt the late interaction paradigm with set-to-set similarity computed via Chamfer distance, and have shown strong performance in text-only and multi-modal retrieval, respectively. 5.1.2. Competitors. We compare GEM with four representative methods in multi-vector retrieval, as mentioned in Section 2: PLAID (Santhanam et al., 2022a), DESSERT (Engels et al., 2023), MUVERA (Jayaram et al., 2024) and IGP (Bian et al., 2025). We also include a graph-based baseline as discussed in Section 3.2, denoted as the multi-vector graph (MVG). To ensure basic competitiveness, here we use qCH for both indexing and search in our experiments. 5.1.3. Parameter Settings. Parameter settings of competitors follow the original papers or their source codes. For PLAID, we set the number of centroids to 262K262K for MSMARCO and LoTTE, 32K32K for OKVQA and EVQA. All vectors are quantized to 2 bits per dimension for MS MARCO and LoTTE, and to 8 bits for OKVQA and EVQA. For DESSERT, we set C=7C=7, L=64L=64 for MSMARCO, LoTTE, and set C=4C=4, L=768L=768 for OKVQA, EVQA. For MUVERA, we adopt Rreps=20R_reps=20, Ksim=5K_sim=5, and Dproj=32D_proj=32 to generate single-vector representations, which are then compressed using PQ-256x8 and indexed with HNSW (M=24M=24, ef_construct=80 ef\_construct=80). For IGP, we use 262K262K centroids for MSMARCO and LoTTE, 32K32K for OKVQA and EVQA, with graph construction parameters set to M=24M=24, ef_construct=200 ef\_construct=200. For our GEM, the number of codebooks |quant||C_quant| follows the same empirical formula from prior studies (Santhanam et al., 2022a, b), i.e., the nearest power of two to 16×#vectors16× \#vectors. This yields |quant|=2⌊log2⁡(16597M)⌋≈262k|C_quant|=2 _2\! (16 597M ) ≈ 262k for MASMARCO. Similarly, |quant|=262K|C_quant|=262K for LoTTE, and 32K32K for OK-VQA and EVQA. The number of clusters |index||C_index| is scaled with dataset size to balance granularity and indexing cost. Specifically, |index||C_index| is set to 40K40K for MSMARCO, 10K10K for LoTTE, and 1K1K for OK-VQA and EVQA, so that each cluster contains about 103−10410^3\!-\!10^4 objects. The graph construction parameters M=24M=24 and ef_construction=80=80 and 20% of the training instances are randomly sampled to construct the shortcuts. At query time, we set t=4t=4 and vary ef_search, #rerank\#rerank to trade off efficiency and accuracy. For MVG, we adopt the same indexing parameters as GEM. All competitors are also tuned to their best query performance. 5.1.4. Evaluation Metrics. Following previous works (Santhanam et al., 2022a; Engels et al., 2023; Lin et al., 2024), we adopt four metrics to evaluate query performance: Recall, Mean Reciprocal Rank (MRR), Success, and query latency; and two metrics to evaluate indexing performance: indexing time and index size. Given a query set Q, with ground-truth set QG_Q for each query Q∈Q , and top-k retrieved results ℛQ(k)R_Q^(k), Recall@k measures the proportion of relevant items retrieved: (17) R@k=1||∑Q∈|Q∩ℛQ(k)||Q|. @k= 1|Q| _Q |G_Q _Q^(k)||G_Q|. MRR@k captures the reciprocal rank of the first relevant item: (18) MRR@k=1|Q|∑Q∈1rankQ, @k= 1|Q| _Q 1rank_Q, Success@k indicates whether any relevant item is present in the top-k, defined as follows: (19) S@k=1|Q|∑Q∈[Q∩ℛQ(k)≠∅]. @k= 1|Q| _Q I[G_Q _Q^(k)≠ ]. Query latency is reported as the average runtime over 1010 repeated runs for each dataset. Remark 3. Note that the ground-truth set QG_Q in the above definitions refers to results with ”a direct human label that says the passage can be used to answer the query”, as stated in MSMARCO. Other datasets follow the same principle. Unlike ANN benchmarks, where the ground truth is typically defined as the exact kkNN obtained by brute-force search in the embedding space, our results below directly reflect end-to-end semantic similarity retrieval performance. 5.2. Performance Analysis Table 2. End-to-end Retrieval Performance Overview Method MSMARCO LOTTE OKVQA EVQA R@100 S@100 MRR@10 T (ms) R@100 S@100 MRR@10 T (ms) R@100 S@100 MRR@10 T (ms) R@100 S@100 MRR@10 T (ms) PLAID 0.913 0.919 0.395 352 0.745 0.910 0.558 462 0.400 0.735 0.225 570 0.895 0.895 0.476 211 DESSERT 0.890 0.905 0.372 344 0.748 0.893 0.541 362 0.371 0.723 0.163 642 0.837 0.837 0.370 552 MUVERA 0.902 0.915 0.385 310 0.736 0.901 0.547 441 0.369 0.723 0.219 605 0.878 0.878 0.471 446 IGP 0.895 0.901 0.389 340 0.731 0.899 0.553 338 0.402 0.732 0.215 549 0.892 0.892 0.440 458 MVG 0.895 0.905 0.421 360 0.701 0.879 0.555 231 0.381 0.719 0.230 427 0.880 0.880 0.468 450 GEM (Ours) 0.915 0.920 0.447 140 0.749 0.910 0.592 210 0.410 0.754 0.236 165 0.895 0.895 0.477 197 5.2.1. Query Performance In this section, we study the end-to-end retrieval performance of all methods under default settings, as summarized in Table 2, Table 3, and Figure 8. Table 2 provides an overview of recall, success, MRR, and end-to-end latency for all methods across all datasets. Clearly, GEM offers the best overall query performance on all datasets. It adapts well to in-domain, out-of-domain, and more complex multi-modal datasets, outperforming all competitors on every query quality metric while maintaining the lowest latency. In particular, GEM achieves speedups of up to 2.5× on MSMARCO, 2.2× on LoTTE, 3.9× on OKVQA, and 2.8× on EVQA, all with better query quality. For EVQA, each query has exactly one annotated relevant document, thus Q∩ℛQ(k)G_Q _Q^(k) can only be size 0 or 11. If the ground truth is in the retrieved top-k: recall=1/1=1,success=1recall=1/1=1,success=1; otherwise: recall=success=0recall=success=0. Hence, its averaged recall and success reported in Table 2 and Figure 8 are always identical. These experimental results validate our design goal: preserving the semantic richness of multi-vector representations to achieve high accuracy, while leveraging an efficient graph index for speed. The reason GEM achieves the best performance can be concluded as follows: 1) Compared with PLAID, GEM indexes at a set-level granularity, treating the entire vector set as the basic unit. This is fundamentally different from PLAID, which indexes all vectors individually. By doing so, GEM significantly reduces the number of false positive candidates returned due to token-level matches, avoiding the need for expensive refinement and boosting efficiency. 2) Compared with DESSERT, which is often bottlenecked by an exhaustive scan of all set sketches, GEM’s graph structure provides a powerful pruning mechanism, enabling significantly faster navigation to the most promising candidates. 3) Compared with MUVERA, which suffers significant accuracy degradation by compressing a vector set into a single vector, GEM preserves set-level semantic nuances, thereby easily achieving superior query quality that MUVERA struggles to match even when its FDEs are tuned to an impractically high 2048020480 dimensions. 4) Compared with IGP, which extends token-level indexing into a graph structure over quantized centroids for incremental candidate filtering, GEM constructs a set-level graph where each node represents a complete vector set. This design captures inter-set relations that centroid-level graphs overlook, enabling faster and more accurate retrieval. 5) Compared with the naive MVG, while it preserves multi-vector inputs, its naive graph suffers from fragmented neighbors, local optima, and lacks effective distance approximation and pruning strategies. Figure 8. Accuracy–Latency Trade-off Overview Table 3. End-to-End Retrieval Perfomance Varying k Method MSMARCO LoTTE R@10/T R@100/T R@1k/T S@10/T S@100/T S@1k/T PLAID 68.8/222 91.3/352 97.5/352 76.8/288 91.0/462 94.5/462 DESSERT 66.2/298 89.0/344 97.2/336 74.7/362 89.3/362 94.3/477 MUVERA 67.7/286 90.2/310 97.1/444 74.1/397 90.1/441 94.4/461 IGP 66.9/279 89.5/340 96.9 /399 75.5/311 89.9/338 94.0/412 MVG 69.2/293 89.5/360 94.2/436 74.7/303 87.9/331 94.2/442 GEM 71.1/88 91.5/140 97.5/212 77.3/133 91.0/210 94.5/251 Table 3 reports how query quality and latency change as the number of returned results k increases. Due to space limitations, we only present results on two datasets. Following our competitors (Santhanam et al., 2022a; Engels et al., 2023), we report recall on MSMARCO and success on LoTTE. On MSMARCO, GEM uses ef_search = 800, 2000, 8000 for k = 10, 100, 1k, respectively. On LoTTE, GEM uses ef_search = 1000, 5000, 8000 for k = 10, 100, 1k, respectively. We make the following observations: (1) GEM consistently achieves the best query performance across all k values, offering higher Recall@k and Success@k while maintaining significantly shorter query times. For example, on MSMARCO, GEM requires only 8888 ms, 140140 ms, and 212212 ms for k=10,100,k=10,100, and 10001000 respectively, whereas the best baselines require 222222 ms (PLAID), 310310 ms (MUVERA), and 336336 ms (DESSERT) to reach comparable recall. On LoTTE, GEM completes in 133133 ms, 210210 ms, and 251251 ms, while the fastest baselines still require 288288 ms (PLAID), 338338 ms (IGP), and 412412 ms (IGP) to achieve similar quality. (2) Our naive solution, MVG, can compete with several well-tuned baselines for small k. Though non-metric distance induces fragmented neighbors and local optima, this issue is not overly severe when the target k is small. By slightly increasing ef_search, greedy graph traversal can escape local minima and reach to the ground truth eventually. As a result, MVG retains the key advantage of graph-based indexes, i.e., it accesses fewer candidates than LSH-based (DESSERT) and IVF-style (PLAID, IGP) methods to achieve the same recall. When further combined with our qCH quantization, which reduces the cost of per-candidate distance computation, MVG exhibits a favorable accuracy–latency trade-off. However, MVG does not consistently outperform other methods. For instance, on MSMARCO, other methods reach around 97% recall when k=1000k=1000, while MVG saturates at 94.2%94.2\%. Even with larger ef_search and longer query time, further improvement is limited by the suboptimal graph structure resulting from the non-metric nature of Chamfer distance. This underscores the necessity of metric decoupling and other optimizations, such as shortcuts and multi-entry search, in GEM for achieving stable performance gains. (3) As expected, in the out-of-domain setting (LoTTE), retrieval is more challenging than in-domain setting (MSMARCO), and all methods require more time to achieve good quality. GEM remains consistently more accurate and faster, often requiring only 1/21/2 or even 1/31/3 of the time of other methods. Figure 8 provides a more comprehensive view of the trade-off between query accuracy and efficiency of all methods. From the figures, we have the following observations: (1) GEM consistently achieves the best trade-off. Among all methods, GEM requires the least time to reach the same MRR, success, or recall, indicating the most favorable balance between accuracy and efficiency. For the same MRR@10, GEM is up to 16x faster than DESSERT (on OKVQA), up to 10x faster than MUVERA (on OKVQA), up to 8x faster than IGP (on OKVQA), and up to 5x faster than PLAID (on MSMARCO). (2) Visual-language retrieval is inherently more challenging. On OKVQA and EVQA, even with increased search time, Success@100 reaches only about 75–89%, while in text-only QA tasks, our algorithm can easily exceed 90%. Notably, this bottleneck is not on the retrieval side: even brute-force search on OKVQA and EVQA achieves only around 77–90% Success@100. This points to the need for stronger embedding models and improved multimodal feature alignment mechanisms. (3) MVG can outperform some competitors on certain datasets, such as complex multi-modal OKVQA and EVQA datasets. This advantage can be attributed to its tailored set-level indexing structure, which preserves fine-grained semantics. In contrast, methods like MUVERA maps a multi-vector set to a single vector, inevitably causing non-trivial information loss. This loss worsens with data complexity, leading to degraded query performance. (4) GEM and PLAID are highly robust, maintaining stable performance across all datasets. PLAID is often the second-best method. In contrast, IGP, DESSERT, and MUVERA exhibit substantial performance variation across datasets. Figure 9. Indexing Performance on All Datasets 5.2.2. Indexing Performance The indexing time and index size of all methods under default settings are summarized in Figure 9. Here, the index size includes only the index files, excluding raw data, to clearly highlight the differences among indexing methods. We make two key observations: (1) GEM’s index size is small (e.g., 2 GB on MSMARCO, 27MB on OKVQA), significantly smaller than MUVERA (10.5 GB on MSMARCO, 139 MB on OKVQA) and DESSERT (107 GB on MSMARCO, 1.8GB on OKVQA). This compactness is attributed to the graph structure of GEM, which primarily stores edge information. This storage overhead is independent of whether the setting is under single- or multi-vector, and is negligible compared to the dataset size. In contrast, DESSERT requires storing a large number of hash values generated by LSH, while MUVERA needs to store Fixed Dimensional Encodings (FDEs) for all vector sets, which scale directly with the dataset size and make it less suited to large-scale scenarios. GEM’s index size is comparable to that of IGP (2.3 GB on MS MARCO, 59 MB on OKVQA) and PLAID (1.5 GB on MS MARCO, 34 MB on OKVQA), but GEM delivers a substantial advantage in both efficiency and accuracy. (2) On MSMARCO and LoTTE, all methods have comparable indexing time. This is because PLAID, DESSERT, IGP, and GEM all rely on a clustering step, which dominates the construction cost. MUVERA does not involve clustering but has to convert every vector set into a single vector, which is also time-consuming. Both clustering and vector conversion can be accelerated on GPUs, making this step less of a practical concern. On smaller datasets, OKVQA and EVQA, the clustering cost becomes less significant, and GEM’s graph construction is slower than PLAID’s IVF, IGP’s single vector graph, and DESSERT’s LSH indexing. MUVERA, which requires both vector conversion and graph construction, remains the slowest. Overall, GEM achieves competitive indexing time and compact index size while providing superior retrieval performance. Figure 10. Ablation Study on the GEM’s Components 5.3. Ablation Study In this section, we evaluate how much each component of GEM contributes to the overall performance. We disable key modules individually and compare the query latency required to reach comparable retrieval accuracy. Due to space constraints, we only present two representative scenarios, i.e., MRR@10 = 0.42 on MSMARCO, and MRR@10 = 0.30 on OKVQA. As shown in Figure 10, removing different components results in varying degrees of latency increase. 5.3.1. w/o EMD distance. We replace the qEMD with qCH for graph construction, which doubles the latency on both datasets. The absence of metric properties degrades the graph quality, confirming the importance of the decoupling strategy in GEM. 5.3.2. w/o multi-path strategy. We disable multi-path search from multiple entry points, instead enqueuing all entry points into a single search queue W and expanding greedily. This change increases latency by 70–80%. Without synchronized paths sharing the visited and best-found result sets, pruning is less aggressive and the search space contracts more slowly. To reach the correct results, a larger ef_search is needed, which increases latency. These results confirm that multi-entry search accelerates convergence. 5.3.3. w/o adaptive TF-IDF cluster pruning. We disable the adaptive adjustment of clusters per document and fix |top|=3|C_top|=3 for all documents–a value nearly identical to the average |top||C_top| on MSMARCO and OKVQA when TF-IDF is enabled (Section 4.1.2). This setup isolates the effect of cluster granularity and allows a direct, fair comparison of adaptive v.s. fixed topC_top values. As observed, performance degrades because a fixed threshold hurts recall for long, topically diverse documents, while short documents suffer efficiency loss from retaining unnecessary clusters. This result highlights the importance of dynamic TF-IDF–guided pruning in balancing accuracy and efficiency. 5.3.4. w/o bridge constraint. In this variant, when the degree of a bridge P exceeds the limit, we retain only its M closest neighbors, rather than enforcing it to keep at least one neighbor from each cluster in top(P)C_top(P). This change greatly degrades performance, with the drop on MSMARCO more pronounced than on OKVQA due to the larger corpus size. This result shows the importance of bridges in maintaining graph connectivity, especially on large datasets. 5.3.5. w/o shortcuts enhancement. We remove shortcuts that directly connect sets that may be close under Chamfer but require many hops to reach over the EMD graph. This leads to a modest degradation in query latency. While the co-designed architecture of GEM is already robust for most queries, the shortcut mechanism is a useful addition for handling a few hard-to-find cases. It is worth noting that these components are co-designed to work synergistically. The optimal performance of GEM relies on their combined effect. Removing all of them (w/o all) leads to a severe degradation, with latency increasing by 5–6x. 5.4. Further Analysis Figure 11. Impact of t on Retrieval Performance Figure 12. Impact of #rerank on Retrieval Performance 5.4.1. Effect of t. In this experiment, we study the impact of parameter t, which controls the number of nearest clusters each qi∈Qq_i∈ Q identifies in the early pruning step. We vary t∈1,2,4,8t∈\1,2,4,8\ and report results on MSMARCO and OKVQA for brevity. Larger t makes the pruning more conservative: pruning fewer clusters to potentially increase recall, but at the cost of higher latency. As shown in Figure 11, both datasets exhibit similar trends. When t=1t=1, pruning is too aggressive, leading to insufficient accuracy. Performance improves substantially at t=2t=2, while the gains begin to saturate as t increases further to 88. Therefore, we set t=4t=4 by default as it provides a favorable balance between accuracy and efficiency. 5.4.2. Effect of #rerank. In this experiment, we evaluate the impact of rerank_k. This parameter determines the size of the candidate pool retrieved from the graph search, which is then re-ranked using the exact Chamfer distance to obtain the final top-k results. Figure 12 reports results for k=10k=10 and 100100. For k=10k=10, the choice of rerank_k has a clear effect on accuracy: a larger rerank_k increases the likelihood that the true best results are included and ranked near the top. For k=100k=100, increasing rerank_k has a more modest impact. This is because our algorithm is already highly effective, with a strong probability of placing the true results within its top-100 candidates, leaving limited room for further improvement. 5.4.3. Effect of Index Parameters. In this experiment, we investigate the impact of two key indexing parameters: the maximum number of neighbors per vertex (M) and the size of the candidate list during construction (ef_construction). As shown in Figure 13 on MSMARCO, with M=8M=8 and ef_construction = 24, the index is small and fast to build, but the graph quality is insufficient, resulting in lower query accuracy. Increasing to M=48M=48 and ef_construction = 200 significantly enlarges the index size and construction time, but query performance improves only marginally. This is because each vertex connects to too many neighbors, increasing the number of candidates to verify at each hop and thereby hurting latency. Our default configuration of M=24M=24 and ef_construction = 80 achieves the best overall trade-off, offering competitive indexing performance and superior query efficiency and accuracy. Figure 13. Impact of M and ef_construction 5.4.4. Effect of N and m. Figure 14. Impact of corpus size N and vector set size m In this experiment, we evaluate scalability with respect to the corpus size (N) and the average number of vectors per set (m). We randomly sample 18N 18N, 14N 14N, 12N 12N, and N vector sets from the original corpus, and randomly sample 18m 18m, 14m 14m, 12m 12m, and m vectors from each set to form new subsets. We vary one factor at a time. Figure 14 reports the effects of these variations on both query latency and index construction time. Increasing N causes a slight rise in latency, e.g., from 6767 ms (18N 18N) to 8585 ms (N), consequently increasing indexing time (0.13 h to 1.79 h) due to the search-based construction procedure. This trend aligns with the logarithmic query cost of graph-based indexes, demonstrating GEM’s strong scalability across different corpus scales. Increasing m exerts a much stronger impact on efficiency, e.g., query latency rises from 4444 ms (18m 18m) to 8585 ms (m) and indexing time from 0.06h0.06~h to 1.791.79 h. The higher sensitivity to m arises from the set-to-set distance calculations. This also explains why many studies focus on optimizing the embedding training itself to preserve semantics more effectively with fewer vectors. As discussed in Section 2, our method can be seamlessly integrated with such advances. Figure 15. Impact of Shortcuts Figure 16. Impact of |quant||C_quant| 5.4.5. Effect of Shortcut Coverage. In this experiment, we study how the amount of training data used for shortcut construction affects query performance. We randomly sample 5%, 10%, 20%, and 40% of the training instances, resulting in approximately 10k, 20k, 40k, and 80k shortcut edges, respectively. As shown in Figure 16, increasing the sampling ratio from 5% to 20% yields a better MRR–latency trade-off, whereas further increasing it to 40% degrades performance. The recall–latency and success–latency curves are omitted as they follow almost the same trend. Such results indicate that sparse shortcuts provide insufficient long-range connectivity, limiting search performance for some hard-to-find cases. In contrast, excessive shortcuts densify the graph, forcing the search to perform more distance computations per step during traversal, thereby offsetting the gains from improved connectivity. Therefore, we set the sampling ratio to 20% by default, which provides a favorable balance between accuracy and efficiency. 5.4.6. Effect of |quant||C_quant|. In this experiment, we evaluate the effect of the number of quantization centroids |Cquant||C_quant| on retrieval performance by varying |Cquant|∈131k,262k,524k|C_quant|∈\131k,262k,524k\. Recall that 262k262k is the default value for MSMARCO derived from the empirical formula in Section 5.1.3. As shown in Figure 16, the retrieval performance of GEM is robust to the choices of |Cquant||C_quant|. Although increasing |Cquant||C_quant| leads to higher distance computation overhead, it yields more accurate approximations and thus requires fewer candidates for reranking. In contrast, reducing |Cquant||C_quant| lowers the computational cost but necessitates probing more candidates to achieve a comparable accuracy level. Therefore, we simply adopt the empirical formula suggested by prior work to set the default value of |Cquant||C_quant|. 6. Conclusion We introduced GEM, a native graph-based framework designed for multi-vector retrieval. GEM constructs a set-level dual-graph with metric decoupling to represent complex inter-set relationships, and further refines it through adaptive TF-IDF–guided clustering and semantic shortcuts. By incorporating quantized distance estimation and cluster-guided multi-path search, GEM jointly enhances efficiency and accuracy, effectively bridging the gap between semantic expressiveness and retrieval efficiency. Extensive experiments showed that GEM consistently surpasses state-of-the-art methods in retrieval quality and latency, while maintaining comparable or smaller index size and construction cost. These results confirmed GEM as a practical solution for large-scale multi-vector retrieval. For future work, integrating ultra-low-bit quantization could further reduce computational and memory costs, paving the way for broader industrial adoption. Acknowledgements. The research work described in this paper was supported by Hong Kong Research Grants Council (grant #16210625, T43-513/23-N), HKUST-WeBank Joint Laboratory (grant #WEB24EG01), HKUST-MetaX Joint Laboratory for Advanced AI Computing (grant #META X24EG01). It was partially conducted in JC STEM Lab of Data Science Foundations funded by The Hong Kong Jockey Club Charities Trust. References A. Andoni, P. Indyk, and R. Krauthgamer (2008) Earth mover distance over high-dimensional spaces. In SODA, p. 343–352. Cited by: §4.2.2. I. Aouali, A. Benhalloum, M. Bompaire, A. A. S. Hammou, S. Ivanov, B. Heymann, D. Rohde, O. Sakhi, F. Vasile, and M. Vono (2022) Reward optimizing recommendation using deep learning and fast maximum inner product search. In KDD, p. 4772–4773. Cited by: §1. A. Bakshi, P. Indyk, R. Jayaram, S. Silwal, and E. Waingarten (2023) Near-linear time algorithm for the chamfer distance. In NeurIPS, Cited by: §3.1. Z. Bian, M. L. Yiu, and B. Tang (2025) IGP: efficient multi-vector retrieval via proximity graph index. SIGIR ’25, New York, NY, USA, p. 2524–2533. Cited by: §1, §2.2, §3.1, §5.1.1, §5.1.2. M. Charikar (2002) Similarity estimation techniques from rounding algorithms. In STOC, p. 380–388. Cited by: §1, §4.2.2. M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni (2004) Locality-sensitive hashing scheme based on p-stable distributions. In SCG, p. 253–262. Cited by: §1. J. Engels, B. Coleman, V. Lakshman, and A. Shrivastava (2023) DESSERT: an efficient algorithm for vector set search with vector set queries. In NeurIPS, Cited by: §1, §2.2, §3.1, §5.1.1, §5.1.2, §5.1.4, §5.2.1. T. Formal, B. Piwowarski, and S. Clinchant (2021) A white box analysis of colbert. In ECIR (2), Lecture Notes in Computer Science, Vol. 12657, p. 257–263. Cited by: §1. C. Fu, C. Xiang, C. Wang, and D. Cai (2019) Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow. 12 (5), p. 461–474. Cited by: §2.1. J. Gao, Y. Gou, Y. Xu, Y. Yang, C. Long, and R. C. Wong (2025) Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search. Proc. ACM Manag. Data 3 (3), p. 202:1–202:26. Cited by: §1, §2.1. J. Gao and C. Long (2024) RaBitQ: quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proc. ACM Manag. Data 2 (3), p. 167. Cited by: §1, §2.1. Y. Gao, Y. Xiong, X. Gao, K. Jia, J. Pan, Y. Bi, Y. Dai, J. Sun, Q. Guo, M. Wang, and H. Wang (2023) Retrieval-augmented generation for large language models: A survey. CoRR abs/2312.10997. Cited by: §1. T. Ge, K. He, Q. Ke, and J. Sun (2014) Optimized product quantization. IEEE Trans. Pattern Anal. Mach. Intell. 36 (4), p. 744–755. Cited by: §2.1. K. Grauman and T. Darrell (2006) Approximate correspondences in high dimensions. In NIPS, p. 505–512. Cited by: §4.2.2. S. Hofstätter, O. Khattab, S. Althammer, M. Sertkan, and A. Hanbury (2022) Introducing neural bag of whole-words with colberter: contextualized late interactions using enhanced reduction. In CIKM, p. 737–747. Cited by: §1, §1, §2.2. Q. Huang, J. Feng, Y. Zhang, Q. Fang, and W. Ng (2015) Query-aware locality-sensitive hashing for approximate nearest neighbor search. PVLDB 9 (1), p. 1–12. Cited by: §2.1. R. Jayaram, L. Dhulipala, M. Hadian, J. Lee, and V. Mirrokni (2024) MUVERA: multi-vector retrieval via fixed dimensional encoding. In NeurIPS, Cited by: §1, §2.2, §3.1, §5.1.1, §5.1.2. S. Jayaram Subramanya, F. Devvrit, H. V. Simhadri, R. Krishnawamy, and R. Kadekodi (2019) Diskann: fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing Systems 32. Cited by: §1, §2.1. H. Jégou, M. Douze, and C. Schmid (2011) Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33 (1), p. 117–128. Cited by: §1, §2.1. J. Jiang, P. H. Chen, C. Hsieh, and W. Wang (2020) Clustering and constructing user coresets to accelerate large-scale top-k recommender systems. In W, p. 2177–2187. Cited by: §1. V. Karpukhin, B. Oguz, S. Min, P. Lewis, L. Wu, S. Edunov, D. Chen, and W. Yih (2020) Dense passage retrieval for open-domain question answering. In EMNLP (1), p. 6769–6781. Cited by: §1. O. Khattab, C. Potts, and M. A. Zaharia (2021a) Baleen: robust multi-hop reasoning at scale via condensed retrieval. In NeurIPS, p. 27670–27682. Cited by: §2.2, Remark 1. O. Khattab, C. Potts, and M. Zaharia (2021b) Relevance-guided supervision for openqa with colbert. Trans. Assoc. Comput. Linguistics 9, p. 929–944. Cited by: §1. O. Khattab and M. Zaharia (2020) ColBERT: efficient and effective passage search via contextualized late interaction over BERT. In SIGIR, p. 39–48. Cited by: §1, §1, §2.2, §3.1, Remark 1. J. Lee, Z. Dai, S. M. K. Duddu, T. Lei, I. Naim, M. Chang, and V. Zhao (2023) Rethinking the role of token retrieval in multi-vector retrieval. In NeurIPS, Cited by: §1, §2.2. Y. Lei, Q. Huang, M. S. Kankanhalli, and A. K. H. Tung (2020) Locality-sensitive hashing scheme based on longest circular co-substring. In SIGMOD Conference, p. 2589–2599. Cited by: §2.1. P. S. H. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W. Yih, T. Rocktäschel, S. Riedel, and D. Kiela (2020) Retrieval-augmented generation for knowledge-intensive NLP tasks. In NeurIPS, Cited by: §1. J. Li, D. Li, S. Savarese, and S. C. H. Hoi (2023a) BLIP-2: bootstrapping language-image pre-training with frozen image encoders and large language models. In ICML, Proceedings of Machine Learning Research, Vol. 202, p. 19730–19742. Cited by: §1. M. Li, S. Lin, B. Oguz, A. Ghoshal, J. Lin, Y. Mehdad, W. Yih, and X. Chen (2023b) CITADEL: conditional token interaction via dynamic lexical routing for efficient and effective multi-vector retrieval. In ACL (1), p. 11891–11907. Cited by: §2.2. Y. Li, M. Franz, Md. A. Sultan, B. Iyer, Y. Lee, and A. Sil (2022) Learning cross-lingual IR from an english retriever. In NAACL-HLT, p. 4428–4436. Cited by: §2.2, Remark 1. W. Lin, J. Chen, J. Mei, A. Coca, and B. Byrne (2023) Fine-grained late-interaction multi-modal retrieval for retrieval augmented visual question answering. In NeurIPS, Cited by: §1. W. Lin, J. Mei, J. Chen, and B. Byrne (2024) PreFLMR: scaling up fine-grained late-interaction multi-modal retrievers. In ACL (1), p. 5294–5316. Cited by: §2.2, §3.1, §5.1.1, §5.1.4. W. Liu, H. Wang, Y. Zhang, W. Wang, L. Qin, and X. Lin (2021) EI-LSH: an early-termination driven I/O efficient incremental c-approximate nearest neighbor search. VLDB J. 30 (2), p. 215–235. Cited by: §2.1. Y. Liu, J. Li, Y. Wu, and Z. Chen (2025) POQD: performance-oriented query decomposer for multi-vector retrieval. CoRR abs/2505.19189. Cited by: §1, §2.2. K. Lu, H. Wang, W. Wang, and M. Kudo (2020) VHP: approximate nearest neighbor search via virtual hypersphere partitioning. Proc. VLDB Endow. 13 (9), p. 1443–1455. Cited by: §2.1. S. Lupart, T. Formal, and S. Clinchant (2023) MS-shift: an analysis of MS MARCO distribution shifts on neural retrieval. In ECIR (1), Lecture Notes in Computer Science, Vol. 13980, p. 636–652. Cited by: §1. Q. Lv, M. Charikar, and K. Li (2004) Image similarity search with compact data structures. In CIKM, p. 208–217. Cited by: §4.2.2. Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li (2006) Ferret: a toolkit for content-based similarity search of feature-rich data. In EuroSys, p. 317–330. Cited by: §4.2.2. Y. A. Malkov and D. A. Yashunin (2020) Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42 (4), p. 824–836. Cited by: §2.1, §4.6. O. R. Moll, M. Favela, S. Madden, V. Gadepally, and M. J. Cafarella (2023) SeeSaw: interactive ad-hoc search over image databases. Proc. ACM Manag. Data 1 (4), p. 260:1–260:26. Cited by: §1. J. A. V. Muñoz, M. A. Gonçalves, Z. Dias, and R. da Silva Torres (2019) Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognit. 96. Cited by: §2.1. F. M. Nardini, C. Rulli, and R. Venturini (2024) Efficient multi-vector dense retrieval with bit vectors. In ECIR (2), Lecture Notes in Computer Science, Vol. 14609, p. 3–17. Cited by: §1, §2.2. A. Paranjape, O. Khattab, C. Potts, M. Zaharia, and C. D. Manning (2022) Hindsight: posterior-guided training of retrievers for improved open-ended generation. In ICLR, Cited by: §2.2, Remark 1. S. G. Patil, T. Zhang, X. Wang, and J. E. Gonzalez (2023) Gorilla: large language model connected with massive apis. CoRR abs/2305.15334. Cited by: §1. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay (2011) Scikit-learn: machine learning in Python. Journal of Machine Learning Research 12, p. 2825–2830. Cited by: §4.4.2. Pinecone (2025) External Links: Link Cited by: §1. A. Reddy, A. Martin, E. Yang, A. Yates, K. Sanders, K. Murray, R. Kriz, C. M. de Melo, B. V. Durme, and R. Chellappa (2025) Video-colbert: contextualized late interaction for text-to-video retrieval. In CVPR, p. 19691–19701. Cited by: Remark 1. Y. Rubner, C. Tomasi, and L. J. Guibas (2000) The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vis. 40 (2), p. 99–121. Cited by: §1, item (3), §4.2.1. K. Santhanam, O. Khattab, C. Potts, and M. Zaharia (2022a) PLAID: an efficient engine for late interaction retrieval. In CIKM, p. 1747–1756. Cited by: §1, §2.2, §3.1, §5.1.1, §5.1.2, §5.1.3, §5.1.4, §5.2.1. K. Santhanam, O. Khattab, J. Saad-Falcon, C. Potts, and M. Zaharia (2022b) ColBERTv2: effective and efficient retrieval via lightweight late interaction. In NAACL-HLT, p. 3715–3734. Cited by: §1, §1, §2.2, §5.1.1, §5.1.3. K. Thai, Y. Chang, K. Krishna, and M. Iyyer (2022) RELiC: retrieving evidence for literary claims. In ACL (1), p. 7500–7518. Cited by: §1. N. Thakur, N. Reimers, A. Rücklé, A. Srivastava, and I. Gurevych (2021) BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In NeurIPS Datasets and Benchmarks, Cited by: §1. Y. Tian, Z. Yue, R. Zhang, X. Zhao, B. Zheng, and X. Zhou (2023a) Approximate nearest neighbor search in high dimensional vector databases: current research and future directions. IEEE Data Eng. Bull. 47 (3), p. 39–54. Cited by: §2.1. Y. Tian, X. Zhao, and X. Zhou (2022) DB-LSH: locality-sensitive hashing with query-based dynamic bucketing. In ICDE, p. 2250–2262. Cited by: §2.1. Y. Tian, X. Zhao, and X. Zhou (2024) DB-LSH 2.0: locality-sensitive hashing with query-based dynamic bucketing. IEEE Trans. Knowl. Data Eng. 36 (3), p. 1000–1015. Cited by: §2.1. Z. Tian, C. Li, Z. Zuo, Z. Wen, L. Sun, X. Hu, W. Zhang, H. Huang, S. Wang, W. Deng, X. Xie, and Q. Zhang (2023b) PASS: personalized advertiser-aware sponsored search. In KDD, p. 4924–4936. Cited by: §1. Vespa (2024) External Links: Link Cited by: §1. M. Wang, W. Xu, X. Yi, S. Wu, Z. Peng, X. Ke, Y. Gao, X. Xu, R. Guo, and C. Xie (2024) Starling: an i/o-efficient disk-resident graph index framework for high-dimensional vector similarity search on data segment. Proc. ACM Manag. Data 2 (1), p. V2mod014:1–V2mod014:27. Cited by: §2.1. X. Wang, C. Macdonald, N. Tonellotto, and I. Ounis (2021) Pseudo-relevance feedback for multiple representation dense retrieval. In ICTIR, p. 297–306. Cited by: §1. X. Wang, C. Macdonald, N. Tonellotto, and I. Ounis (2023) Reproducibility, replicability, and insights into dense multi-representation retrieval models: from colbert to col. In SIGIR, p. 2552–2561. Cited by: §1. Weaviate (2025) External Links: Link Cited by: §1. X. Yang, K. Sun, H. Xin, Y. Sun, N. Bhalla, X. Chen, S. Choudhary, R. D. Gui, Z. W. Jiang, Z. Jiang, L. Kong, B. Moran, J. Wang, Y. E. Xu, A. Yan, C. Yang, E. Yuan, H. Zha, N. Tang, L. Chen, N. Scheffer, Y. Liu, N. Shah, R. Wanga, A. Kumar, W. Yih, and X. L. Dong (2024) CRAG - comprehensive RAG benchmark. CoRR abs/2406.04744. Cited by: §1. L. Yao, R. Huang, L. Hou, G. Lu, M. Niu, H. Xu, X. Liang, Z. Li, X. Jiang, and C. Xu (2022) FILIP: fine-grained interactive language-image pre-training. In ICLR, Cited by: §1, §2.2. J. Zhan, X. Xie, J. Mao, Y. Liu, J. Guo, M. Zhang, and S. Ma (2022) Evaluating interpolation and extrapolation performance of neural retrieval models. In CIKM, p. 2486–2496. Cited by: §1. X. Zhao, Y. Tian, K. Huang, B. Zheng, and X. Zhou (2023) Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces. Proc. VLDB Endow. 16 (8), p. 1979–1991. Cited by: §2.1. B. Zheng, X. Zhao, L. Weng, N. Q. V. Hung, H. Liu, and C. S. Jensen (2020) PM-LSH: A fast and accurate LSH framework for high-dimensional approximate N search. Proc. VLDB Endow. 13 (5), p. 643–655. Cited by: §2.1.

Instant research discovery