Unified and Efficient Approach for Multi-Vector Similarity Search Binhan Yang, Yuxiang Zeng, Hengxin Zhang, Zhuanglin Zheng, Yunzhen Chi, Yongxin Tong, Ke Xu State Key Laboratory of Complex & Critical Software Environment, Beihang University, Beijing, China {yangbh, yxzeng, zhanghengxin, zzlin, chiyz, yxtong, kexu}@buaa.edu.cn
arXiv:2604.02815v1 [cs.DB] 3 Apr 2026
ABSTRACT Multi-Vector Similarity Search is essential for fine-grained semantic retrieval in many real-world applications, offering richer representations than traditional single-vector paradigms. Due to the lack of native multi-vector index, existing methods rely on a filter-andrefine framework built upon single-vector indexes. By treating token vectors within each multi-vector object in isolation and ignoring their correlations, these methods face an inherent dilemma: aggressive filtering sacrifices recall, while conservative filtering incurs prohibitive computational cost during refinement. To address this limitation, we propose MV-HNSW, the first native hierarchical graph index designed for multi-vector data. MV-HNSW introduces a novel edge-weight function that satisfies essential properties (symmetry, cardinality robustness, and query consistency) for graph-based indexing, an accelerated multi-vector similarity computation algorithm, and an augmented search strategy that dynamically discovers topologically disconnected yet relevant candidates. Extensive experiments on seven real-world datasets show that MV-HNSW achieves state-of-the-art search performance, maintaining over 90% recall while reducing search latency by up to 14.0× compared to existing methods. PVLDB Reference Format: Binhan Yang, Yuxiang Zeng, Hengxin Zhang, Zhuanglin Zheng, Yunzhen Chi, Yongxin Tong, Ke Xu. Unified and Efficient Approach for Multi-Vector Similarity Search. PVLDB, 17(12): 4441 - 4444, 2026. doi:10.14778/3685800.3685895
1
INTRODUCTION
With the rapid advancement of Retrieval-Augmented Generation (RAG) [8], vector similarity search has become essential for enabling Large Language Models (LLMs) to access external knowledge. Given a query vector, vector similarity search aims to identify the top-𝑘 most similar vectors from a large-scale collection, where similarity is typically measured by distance metrics such as inner product or Euclidean distance. This core operation underpins a wide range of applications, such as image retrieval, recommendation systems, and entity linking. However, modern applications increasingly demand finer-grained semantic understanding. Conventional single-vector representation, where each object is encoded as a single fixed-dimensional vector, often struggles to capture the rich details of complex unstructured This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 17, No. 12 ISSN 2150-8097. doi:10.14778/3685800.3685895
data. For example, encoding an entire document as a single vector inevitably compresses local information, leading to semantic dilution [15, 27]. To address this limitation, recent retrieval systems have shifted toward multi-vector representations, where each object is decomposed into smaller units (e.g., tokens or passages), each represented as a distinct vector (referred to as a “token vector” throughout this paper). This paradigm, known as Multi-Vector Similarity Search (MVSS) [15, 16], preserves fine-grained semantics and enables more precise relevance matching through functions like MaxSim [15]. A typical example is as follows. Example 1 (Document Retrieval). Consider an academic document retrieval system. A user submits a query: “climate change impacts on biodiversity”. In this system, both queries and documents are represented as multi-vectors: the query is encoded into token-level vectors, while each document (e.g., a research paper) is chunked into passages (e.g., abstract, methodology, experiments), each encoded as a separate vector. To measure relevance, the MaxSim function [15] is commonly used. For a given document, we examine each query token (e.g., “climate change”, “biodiversity”) and identify its most similar passage within that document based on semantic relevance. These maximum similarities are then summed across all query tokens. A document is considered relevant if its passages collectively cover the query’s semantics, with each query token finding a strong semantic match somewhere in the document. Prior Work on Multi-Vector Similarity Search. Most existing approaches follow a filter-and-refine paradigm. In the filtering phase, heuristic strategies prune irrelevant objects based on similarities among token vectors. In the refinement phase, exact multi-vector similarity is computed on the remaining candidates. For filtering, existing methods [7, 15, 16, 18] leverage single-vector indexes (e.g., HNSW [20] and IVF [30]) or product quantization [13] to prune dissimilar objects. During refinement, they enumerate all token vector pairs between each candidate and the query to compute multi-vector similarity according to functions like MaxSim. Limitations of Existing Work. Current solutions suffer from critical limitations in either efficiency or recall. First, their filtering strategies treat the token vectors within a multi-vector in isolation, building separate single-vector indexes. This ignores intra-object correlations and leads to avoidable recall loss. Second, refinement phases typically compute expensive multi-vector similarity functions in a brute-force manner, creating an inherent dilemma: aggressive filtering to reduce computational cost risks severe recall degradation, while conservative filtering to preserve recall incurs prohibitive overhead during refinement. These two fundamental limitations arise from a single structural gap: the absence of native multi-vector indexing support in existing vector databases and search engines, such as Faiss [5], Milvus [32] and Weaviate [3]. This situation forces most methods to adapt single-vector indexes
for multi-vector data. Thus, balancing recall and efficiency remains an open challenge for multi-vector similarity search. Technical Challenges and Our Solution. Inspired by the success of the HNSW index [20] in single-vector similarity search, this paper introduces MV-HNSW, a native hierarchical graph index for multivector data. Adapting graph-based indexing to the multi-vector setting presents three technical challenges: (1) Unsuitable Multi-Vector Similarity Metric: Multi-vector similarity functions like MaxSim lack essential properties required for graph edge weights, such as symmetry. (2) Computational Inefficiency: Expensive multi-vector similarity computations hinder both index construction and similarity search. (3) Topological Disconnect: Due to multi-vector structural complexity, true nearest neighbors may be topologically distant or disconnected from traversed nodes within the graph index. To address these challenges, MV-HNSW proposes an end-toend framework integrating three synergistic components. First, we introduce a novel edge-weight function that averages the bidirectional similarity between two multi-vector objects and prove that it satisfies three essential properties (i.e., symmetry, cardinality robustness, and query consistency) required for graph-based vector indexes. Second, we design an accelerated algorithm that leverages clustering to efficiently approximate common multi-vector similarity functions, significantly reducing computational overhead. Third, we develop an augmented search strategy that adaptively expands the candidate list during graph traversal, boosting recall while incurring minimal efficiency loss. Contribution. This paper makes the following contributions: • Unified Problem Formalization: We formalize the Unified Multi-Vector Similarity Search problem, which unifies representative multi-vector similarity metrics (e.g., MaxSim [15] and Aggregate 𝛾 NN [16]) as its special instantiations. • Essential Property Definition: We formally define three core properties, symmetry, cardinality robustness, and query consistency, that a valid edge-weight function must satisfy for multi-vector graph indexes. We show that directly adopting existing multi-vector similarity functions (e.g., MaxSim) as edge weights in HNSW violates all three. • Native Multi-Vector Graph Index: We propose MV-HNSW, the first hierarchical graph index natively designed for multi-vector data. We design a novel edge-weight function that satisfies all three essential properties. • Efficiency & Recall Optimizations: We present optimization methods to accelerate index construction and similarity search while improving recall. • Experiment Evaluation: We conduct extensive experiments on 7 real-world datasets. Results demonstrate that our MV-HNSW significantly outperforms the state-of-theart solutions [15, 16, 27, 28] in search latency and recall. Road Map. The rest of this paper is organized as follows. Sec. 2 formalizes the problem. Sec. 3 and Sec. 4 introduce our MV-HNSW index and search algorithm. Sec. 5, Sec. 6, and Sec. 7 present the experimental study, related work, and conclusion, respectively.
Table 1: Summary of major notations Notation 𝑣 = (𝑤 1, · · · , 𝑤𝑑 ) 𝑉 = (𝑣 1, · · · , 𝑣𝑐 ) D = {𝑉1, · · · , 𝑉𝑛 } VD 𝑄 𝑘 𝛾 NN(𝑞, 𝑉 ) dis(𝑣 1, 𝑣 2 ) USim(𝑄, 𝑉 )
2
Description A 𝑑-dimensional vector data 𝑣 A multi-vector 𝑉 with 𝑐 token vectors A dataset D of 𝑛 multi-vector data A set of all token vectors in the dataset D The query multi-vector data Number of neighbors needed for the query 𝛾 nearest neighbors of 𝑞 in 𝑉 Vector data distance between 𝑣 1 and 𝑣 2 Unified multi-vector similarity from 𝑄 to 𝑉
PROBLEM STATEMENT
This section formally defines the studied problem. The key notations used throughout the paper are summarized in Table 1.
2.1
Basic Concepts
Definition 1 (Vector Data). A vector data object (“vector” as short) is represented as a point 𝑣 = (𝑤 1, 𝑤 2, · · · , 𝑤𝑑 ) in the 𝑑-dimensional real coordinate space R𝑑 , where each 𝑤𝑖 ∈ R denotes the 𝑖-th coordinate of 𝑣. Given two such objects, their similarity can be quantified by a distance function dis : R𝑑 × R𝑑 → R. Common choices for the distance function dis(·, ·) include Euclidean distance, inner product, and cosine similarity. In this work, we adopt the inner product ⟨·, ·⟩ as the default distance function, following the convention that a larger distance indicates greater similarity. Our solution also supports other distance metrics. Definition 2 (Single-Vector Similarity Search). Given a (single) vector dataset 𝑉 , a query vector 𝑞 ∈ R𝑑 , and a positive integer 𝑘, the single-vector similarity search returns a subset A of exactly 𝑘 vectors from the dataset 𝑉 that are nearest to 𝑞, i.e., satisfying ∀𝑢 ∈ A, ∀𝑣 ∈ (𝑉 \ A), dis(𝑢, 𝑞) ≥ dis(𝑣, 𝑞)
(1)
We use 𝛾 NN(𝑞, 𝑉 ) to denote these 𝛾-nearest neighbors of 𝑞 in 𝑉 . Definition 3 (Multi-vector Data). A multi-vector data object is denoted as a finite sequence of vectors, formally 𝑉 = (𝑣 1, 𝑣 2, · · · , 𝑣𝑐 ) with 𝑐 > 1, and each vector 𝑣𝑖 shares the same dimension 𝑑. We refer to each 𝑣𝑖 as a token vector, adapting the terminology of token embeddings from LLMs. A multi-vector data provides a more fine-grained representation of unstructured data. In practice, such a representation is typically created in two steps: (1) applying a segmentation strategy to divide the raw data into multiple segments, and then (2) encoding each segment independently using an embedding model. The cardinality 𝑐 corresponds to the number of segments, which in turn depends on the granularity of the segmentation strategy. To illustrate this process, we use text data as an example and introduce two segmentation strategies used in passage retrieval: • Token-Level Segmentation: Methods like ColBERT [15] generate a contextualized embedding for each token in the text, so each vector encodes token-level semantics within its surrounding context. • Passage-Level Segmentation: Methods like DPR [14] first split a document into fixed-size text windows (referred to as “passages”), then embed each passage into a single vector.
Definition 4 (Unified Multi-Vector Similarity Function). For multivector data 𝑄 and 𝑉 , the unified multi-vector similarity function USim(𝑄, 𝑉 ) is defined as the weighted average distance from each token vector 𝑞 ∈ 𝑄 to its 𝛾-nearest neighbors in 𝑉 :
Example 3. Consider a multi-vector dataset D = {𝑉1, 𝑉2, 𝑉3 } and a query multi-vector 𝑄 = {𝑞 1, 𝑞 2 }. Their token vectors are as follows: √
• 𝑉1 = {𝑣 1, 𝑣 2 }: 𝑣 1 = ( 23 , 12 , 0), 𝑣 2 = (0, 45 , 35 ). • 𝑉2 = {𝑣 3, 𝑣 4 }: 𝑣 3 = ( √1 , √1 , 0), 𝑣 4 = (0, 35 , 45 ). 2
∑︁ © ∑︁ 1 ª dis(𝑞, 𝑣) ® (2) 𝑤𝑞 · 𝛾 𝑞 ∈𝑄 « 𝑣 ∈𝛾 NN(𝑞,𝑉 ) ¬ where 𝑤𝑞 ∈ [0, 1] is the input weight assigned to token vector 𝑞. Compared to single-vector similarity evaluation, the unified function USim for multi-vectors is more complex and computationally intensive. Moreover, several multi-vector similarity metrics proposed in prior work can be expressed as special cases of USim. Below we introduce three representative examples: • MaxSim is the most prevalent multi-vector similarity metric. It corresponds to the case where 𝛾 = 𝑤𝑞 = 1 in Eq. (2). It was first introduced in ColBERT [15] and has since been used in many subsequent studies [6, 17, 19, 22, 25–27, 29]. • Weighted Chamfer was proposed to explicitly account for importance of different token vectors in multi-vector similarity search [9]. It corresponds to the instantiation of Eq. (2) with 𝛾 = 1, where 𝑤𝑞 are learnable weights. • Aggregate 𝛾 NN was originally introduced in Google’s framework (called XTR [16]) for multi-vector similarity search. It corresponds to the instantiation of Eq. (2) with 𝛾 > 1, 𝑤𝑞 = 1, and dis defined as the inner product. This metric has also been adopted in follow-up work [28]. Example 2. To illustrate the computation of USim with 𝛾 = 1, consider a multi-vector 𝑉 = {𝑣 1, 𝑣 2, 𝑣 3 } and a query 𝑄 = {𝑞 1, 𝑞 2, 𝑞 3 }. Their token vectors and associated weights are given as follows: • 𝑄: 𝑞 1 = (1, 0), 𝑞 2 = (0, 1), and 𝑞 3 = ( √1 , √1 ). 2
2
• 𝑉 : 𝑣 1 = (0.8, 0.6), 𝑣 2 = (0.6, 0.8), and 𝑣 3 = ( √1 , √1 ). 2 2 • Weight: 𝑤𝑞1 = 1, 𝑤𝑞2 = 0 and 𝑤𝑞3 = 1. Based on Eq. (2) the similarity from 𝑄 to 𝑉 is computed by taking, for each token vector 𝑞 ∈ 𝑄, the maximum inner product with any token vector in 𝑉 , and then aggregating the weighted results: ∑︁ USim(𝑄, 𝑉 ) = 𝑤𝑞𝑖 · max ⟨𝑞𝑖 , 𝑣 𝑗 ⟩ 𝑣 𝑗 ∈𝑉
𝑞𝑖 ∈𝑄
o n o = 1 · max 0.8, 0.6, √1 + 0 · max 0.6, 0.8, √1 + 2 2 n o √ √ 1 · max 0.8+0.6 , 0.6+0.8 , 1 = 0.8 + 0 + 1 = 1.8 n
2
2.2
2
Problem Definition
We formally define the studied problem as follows. Definition 5 (Unified Multi-Vector Similarity Search). Given a multi-vector dataset D, a query multi-vector 𝑄 with associated token weights 𝑤𝑞 , and a target integer 𝑘, the unified multi-vector similarity search aims to retrieve a subset A ⊆ D consisting of the 𝑘 multi-vectors most similar to 𝑄 according to the unified multivector similarity function USim. Formally, the search result A must satisfy the following conditions: (1) |A| = 𝑘 and A ⊆ D; (2) ∀𝑈 ∈ A and 𝑉 ∈ (D \ A), USim(𝑄, 𝑈 ) ≥ USim(𝑄, 𝑉 ). Example 3 illustrates a concrete instance of the problem.
2
• 𝑉3 = {𝑣 5, 𝑣 6 }: 𝑣 5 = ( 35 , 45 , 0), 𝑣 6 = (0, 1, 0). • 𝑄 = {𝑞 1, 𝑞 2 }: 𝑞 1 = (1, 0, 0), 𝑞 2 = (0, √1 , √1 ).
USim(𝑄, 𝑉 ) =
2
2
Assume 𝛾 = 1, 𝑤𝑞1 = 𝑤𝑞2 = 1, and 𝑘 = 2. Computing USim from the query multi-vector 𝑄 to each multi-vector 𝑉𝑖 ∈ D yields: √
√
USim(𝑄, 𝑉1 ) = ⟨𝑞 1, 𝑣 1 ⟩ + ⟨𝑞 2, 𝑣 2 ⟩ = 23 + 7102 ≈ 1.856, √
USim(𝑄, 𝑉2 ) = ⟨𝑞 1, 𝑣 3 ⟩ + ⟨𝑞 2, 𝑣 4 ⟩ = √1 + 7102 ≈ 1.697, 2
USim(𝑄, 𝑉3 ) = ⟨𝑞 1, 𝑣 5 ⟩ + ⟨𝑞 2, 𝑣 6 ⟩ = 35 + √1 ≈ 1.307. 2
With 𝑘 = 2, the unified multi-vector similarity search returns {𝑉1, 𝑉2 } as the top-2 results with the highest similarity scores. Remark. Due to the curse of dimensionality [12] and the expensive computational cost of evaluating multi-vector similarity, exact solutions to the above problem do not scale to large-scale datasets. Consequently, existing research has focused on approximate algorithms that trade some accuracy for efficiency, aiming to maximize the recall as defined in Eq. (3): |A ∩ A ∗ | (3) 𝑘 ∗ where A denotes to the exact answer. Following this research direction, our work also focuses on the approximate algorithm for unified multi-vector similarity search. Recall =
3
MULTI-VECTOR INDEX MV-HNSW
This section elaborates on our index MV-HNSW, the first native hierarchical graph index for multi-vectors. We start with its main idea (Sec. 3.1), then introduce its structure and novel edge-weight function (Sec. 3.2), present the index construction algorithm (Sec. 3.3), and finally propose an optimized USim computation method for accelerating offline construction and online search (Sec. 3.4).
3.1
Main Idea
The Hierarchical Navigable Small World (HNSW) graph [20] has become a dominant index for single-vector similarity search. Its success stems from a multi-layered graph design that enables approximate 𝑘NN search in sublinear time, achieving state-of-the-art recall and latency trade-offs [33], making it one of the most popular index choices in modern vector databases. However, HNSW is designed to index individual token vectors, not multi-vectors. Consequently, existing filter-and-refine based methods for multivector similarity search lack native multi-vector indexing support, suffering from either low recall or high search latency. To address these limitations, we propose a multi-vector index (MV-HNSW) and an efficient solution for unified multi-vector similarity search. Our framework consists of two synergistic components: (1) Multi-Vector Graph Index. We design a hierarchical graph index, where each node represents a multi-vector. An edge connects two nodes if their corresponding multi-vectors are similar enough according to a similarity fusion function. To accelerate index construction, we introduce an approximate method for efficiently computing the USim score.
(2) Augmented Search via Hierarchical Graphs. Using MVHNSW, we can progressively find the 𝑘 NNs to the query multivector, but navigating this graph alone still misses relevant answers. To mitigate this, we expand the candidate set for every explored node during traversal by incorporating globally relevant multivectors into its connected neighbors (see Sec. 4 for detail).
3.2
Multi-Vector Index Structure
We introduce our MV-HNSW index in two parts: the core design principle (Sec. 3.2.1) followed by its detailed structure (Sec. 3.2.2). 3.2.1 Core Design Principle. To extend HNSW’s success to multivector similarity search, we propose MV-HNSW, a novel HNSWbased index. In this index, each node represents a multi-vector, and edges connect similar multi-vectors. The core technical challenge lies in defining a suitable edge-weight function 𝑓 (𝑢, 𝑣) between nodes 𝑢 and 𝑣. We first identify and formalize three essential properties that such a function 𝑓 (·, ·) must possess: symmetry, cardinality robustness, and query consistency. We then demonstrate that the unified multi-vector similarity function USim violates these criteria, justifying the need for our subsequent solution in Sec. 3.2.2. Essential Property for Edge Weight Function. We now formally define the three essential properties for the edge weight function. Definition 6 (Symmetry). An edge weight function 𝑓 is symmetric if 𝑓 (𝑢, 𝑣) = 𝑓 (𝑣, 𝑢) for any two multi-vectors 𝑢 and 𝑣. This weight symmetry property ensures that traversing graph is consistent: if you can go from nodes from 𝑢 to 𝑣, then 𝑣 is equally reachable from 𝑢. This ensures consistent navigation. Definition 7 (Cardinality Robustness). An edge weight function 𝑓 is cardinality-robust if it does not exhibit systematic bias towards larger cardinalities of multi-vectors. That is, 𝑓 (𝑢, 𝑣) should not systematically increase or decrease with |𝑢| or |𝑣 |. Without this property, some multi-vectors would attract an excessive number of edges due to their high cardinality rather than genuine similarity. This isolates closely relevant nodes and creates hub nodes that monopolize connections, thereby harming recall.
Proof. (1) Violation of Symmetry. The definition in Eq. (2) is inherently asymmetric. For 𝛾 = 1, USim(𝑢, 𝑣) computes the weighted sum of distance from each token vector 𝑢𝑖 ∈ 𝑢 to its nearest neighbor in 𝑣, whereas USim(𝑣, 𝑢) computes that from each 𝑣 𝑗 ∈ 𝑣 to its nearest neighbor in 𝑢. Since the nearest-neighbor relation is not symmetric, USim is asymmetric. (2) Violation of Cardinality Robustness. From Eq. (2), USim(𝑢, 𝑣) sums over all 𝑢𝑖 ∈ 𝑢. Thus, for fixed 𝑣 and 𝛾 = 1, USim(u, v) = Θ(|𝑢 |) when the nearest neighbor distances are bounded. This linear dependence on |𝑢| directly violates cardinality robustness. (3) Violation of Query Consistency. Query consistency does not hold in general. Consider the following counterexample. Let 𝐷 1 = (𝑣 1, 𝑣 2 ) and 𝐷 2 = (𝑣 1, 𝑣 2, 𝑣 3, 𝑣 4 ) be multi-vector datasets, and let 𝑄 = (𝑣 3, 𝑣 4 ) be a query multi-vector with weight 𝑤 𝑣3 = 𝑤 𝑣4 = 1, where each 𝑣𝑖 denotes a token vector. We assume both token vectors 𝑣 3, 𝑣 4 are orthogonal to every token vector in 𝐷 1 , which can be trivially instantiated in high-dimensional space. Then, when 𝛾 = 1, 1 ,𝐷 2 ) we have USim(𝑄, 𝐷 1 ) = 0 and USim(𝑄, 𝐷 2 ) = 2. Then USim(𝐷 = |𝐷 1 | 1, giving 𝜏 = 0, but | USim(𝑄, 𝐷 1 ) − USim(𝑄, 𝐷 2 )| = |𝑄 | ≠ 0. Hence, the query consistency is violated. □ 3.2.2 Index Structure. As shown in Fig. 1, MV-HNSW is a hierarchical graph with multiple layers, where each node represents a unique multi-vector, Within a layer, nodes are connected by undirected edges that indicate the similarity between the corresponding multi-vectors, and each node maintains at most 𝑀 such connections to its (approximate) nearest neighbors. When constructing this index, each multi-vector 𝐷𝑖 from the dataset D is first assigned a random layer 𝑙𝑖 sampled from an exponentially decaying distribution. A node representing 𝐷𝑖 is then inserted into all layers from 𝑙𝑖 down to the base layer. Accordingly, the highest layer contains the fewest nodes and provides the global entry point 𝑒𝑝 for similarity search. This design ensures two key properties: (1) higher layers contain progressively sparser subsets of the dataset, which enables rapid coarse-grained navigation, and (2) similarity search can proceed top-down, starting from the coarsest layer and refining results through finer layers.
(4)
Edge Weight Function. The key adaptation that enables effective multi-vector search lies in the design of edge weight function 𝑓 . As aforementioned, a suitable 𝑓 must satisfy three properties: symmetry, cardinality robustness, and query consistency. To meet these requirements, we introduce a novel similarity fusion function (defined in Definition 9) to quantify edge weights between multi-vectors, and provide a formal proof in Theorem 1.
This property guarantees that when the search moves from a node 𝑢 to its connected neighbor 𝑣 with high weights, their similarity to the query remains comparable. Without this property, following a local edge could lead to a node with a drastically different USim score, making the traversal unstable and inefficient.
Definition 9 (Edge Weight Function). The edge weight function 𝑓 (𝑢, 𝑣) is defined as the average of bidirectional normalized similarity between two multi-vectors 𝑢 and 𝑣: 1 USim(𝑢, 𝑣) USim(𝑣, 𝑢) + (5) 𝑓 (𝑢, 𝑣) = 2 |𝑢| |𝑣 |
Definition 8 (Query Consistency). An edge weight function 𝑓 is said to be query-consistent if, whenever two nodes are similar under 𝑓 , their USim scores remain similar for any query. Formally, for any small 𝜏 ≥ 0, if 𝑓 (𝑢, 𝑣) ≥ 1 − 𝜏, then |USim(𝑄, 𝑢) − USim(𝑄, 𝑣)| = 𝑂 (𝜏 · |𝑄 |).
Why USim Fails as an Edge Weight Function. We now demonstrate that the unified multi-vector similarity function USim, while a natural candidate for 𝑓 , fails to satisfy the essential properties defined above. Lemma 1. USim is asymmetric, not cardinality-robust, and not query-consistent.
where token weights used in USim follow the same pre-processing method as query token weights, defaulting to 1 if unspecified. Theorem 1. The edge weight function 𝑓 defined in Eq. (5) is symmetric, cardinality-robust, and query-consistent. Proof. The theorem follows directly from Lemmas 2–4.
□
Token Vector
Global Entry Point
Multi-Vector
Unified Multi-Vector Edge Weight Function in HNSW Similarity Function 𝐔𝐔𝐔𝐔𝐔𝐔𝐔𝐔 𝒖𝒖, 𝒗𝒗 + 𝐔𝐔𝐔𝐔𝐔𝐔𝐔𝐔(𝒗𝒗, 𝒖𝒖) Cover 3 Metrics
MaxSim
Aggregated 𝛾𝛾NN
Weighted Chamfer
𝒖𝒖
Dynamic Candidate Expansion
+ Three Properties
𝟐𝟐 𝐔𝐔𝐔𝐔𝐔𝐔𝐔𝐔 𝒖𝒖, 𝒗𝒗
Symmetry
Query Consistency
𝐔𝐔𝐔𝐔𝐔𝐔𝐔𝐔(𝒗𝒗, 𝒖𝒖)
𝒗𝒗
Cardinality Robustness
Fast Selection by Heap
Parallelizable
Efficient USim Computation MV-HNSW: HNSW, but each node is a Multi-Vector
𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖 𝒅𝒅𝒗𝒗𝟏𝟏 , 𝑸𝑸 ⋅
𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖(𝒅𝒅𝒗𝒗𝟐𝟐 , 𝑸𝑸) ⋅
𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖𝐖(𝒅𝒅𝒗𝒗𝟑𝟑 , 𝑸𝑸) ⋅
Index Construction Algorithm
> > >
> > >
c
>
Expand Connected Neighbors by Priority
>
Monotonous Aggregated Distances
Q
D
Augmented Search Algorithm
𝑽𝑽𝟏𝟏
𝑽𝑽𝟐𝟐
𝑽𝑽𝟑𝟑
Figure 1: Overview of our solution MV-HNSW Lemma 2. The edge weight function 𝑓 is symmetric. Proof. Based on the definition of 𝑓 in Eq. (5), we have 1 USim(𝑣, 𝑢) USim(𝑢, 𝑣) + = 𝑓 (𝑣, 𝑢) 𝑓 (𝑢, 𝑣) = 2 |𝑣 | |𝑢 |
(6) □
Lemma 3. The edge weight function 𝑓 is cardinality-robust.
Algorithm 1: Insert Multi-Vector 𝐷𝑖 into MV-HNSW Input: Node degree 𝑀, size 𝑒 𝑓 𝐶 of construction candidate list, normalization factor 𝑚𝐿 for layer sampling Output: MV-HNSW after inserting the new multi-vector 𝐷𝑖 1 𝑙𝑖 ← ⌊− ln(uniform(0, 1)) · 𝑚 𝐿 ⌋; 2 𝑒𝑝 ← the global entry point at layer 𝑙𝑒𝑝 ; 3 foreach layer 𝑙𝑐 ← 𝑙𝑒𝑝 to 𝑙𝑖 + 1 do 4 𝑒𝑝 ← SEARCH-LAYER(𝐷𝑖 , 𝑙𝑐 , 𝑒𝑝) with 𝑒 𝑓 = 1;
Proof. For any multi-vectors 𝑢 and 𝑣, the term USim(𝑢,𝑣) repre|𝑢 | sents the average similarity from token vectors of 𝑢 to 𝑣, which lies ) in [−1, 1]. Similarly, USim(𝑣,𝑢 ∈ [−1, 1]. Since 𝑓 (𝑢, 𝑣) is the average |𝑣 | of these two values in [−1, 1], we have 𝑓 (𝑢, 𝑣) ∈ [−1, 1]. Moreover, each term is normalized by the cardinality of its first argument, ensuring that 𝑓 (𝑢, 𝑣) does not systematically increase with |𝑢| or |𝑣 |. This satisfies the definition of cardinality robustness. □
for 𝑙𝑐 ← min(𝑙𝑖 , 𝑙𝑒𝑝 ) to 0 do 𝐶𝑎𝑛𝑑 ← SEARCH-LAYER(𝐷𝑖 , 𝑙𝑐 , 𝑒𝑝) with 𝑒 𝑓 = 𝑒 𝑓 𝐶; 7 𝑆 ← 𝑀 nearest candidates to 𝐷𝑖 from 𝐶𝑎𝑛𝑑; 8 Connect 𝐷𝑖 with each 𝐷 𝑗 ∈ 𝑆 at layer 𝑙𝑐 ; 9 foreach multi-vector 𝐷 𝑗 ∈ 𝑆 do 10 if degree(𝐷 𝑗 ) > 𝑀 then 11 Trim number of connected neighbor of 𝐷 𝑗 to 𝑀;
Lemma 4. The edge weight function 𝑓 is query-consistent.
12
Proof Sketch. Due to page limitations, we provide a proof sketch here, and more detailed proof can be found in our online full paper [35]. We first prove that when the edge weight 𝑓 (𝑉1, 𝑉2 ) is sufficiently high, the expected number of token vectors in 𝑉1 that are highly similar to token vectors in 𝑉2 is bounded. Applying Markov’s inequality [21] then yields a constraint on the distance discrepancy for any query 𝑄. By algebraically bounding the minimum distance gap, we deduce that | USim(𝑄, 𝑉1 ) − USim(𝑄, 𝑉2 )| ≤ 𝑂 (𝜏 𝑧 |𝑄 |) with 𝑧 ≤ 1 holds strictly, which satisfies the definition of query consistency. □
3.3
Index Construction Algorithm
3.3.1 Main Idea. The MV-HNSW index is constructed by sequentially inserting each multi-vector into a hierarchical graph. For each insertion, the algorithm first randomly assigns a layer 𝑙𝑖 to the new node, navigates from the topmost layer down to 𝑙𝑖 to obtain an entry point 𝑒𝑝, and then inserts the node from layer 𝑙𝑖 down to the base layer. At each layer in this downward traversal, the insertion consists of two steps: Navigation: Starting from the global entry point, the algorithm invokes the SEARCH-LAYER routine of HNSW [20] to perform a greedy search at the current layer and locate the nearest neighbor(s) of the new multi-vector. This neighbor serves as the entry point(s) for the next (lower) layer.
5
6
13 14
𝑒𝑝 ← 𝐶𝑎𝑛𝑑; if 𝑙𝑖 is higher than current global entry point then Change global entry point to 𝐷𝑖 ;
Connection: During the traversal in current layer, the algorithm also retrieves 𝑒 𝑓 𝐶 candidate neighbors, selects up to 𝑀 closest ones, and establishes bidirectional edges. The degree of each node is maintained below 𝑀 through pruning when necessary. 3.3.2 Algorithm Details. Algo. 1 illustrates the detailed steps: Localization (Lines 1-4). We first randomly assign a layer 𝑙𝑖 to the new multi-vector 𝐷𝑖 . Unlike standard HNSW, our SEARCH-LAYER uses the edge weight function as the multi-vector similarity metric. The resulting node 𝑒𝑝 serves as the entry point for the next layer, and this process repeats until the target layer 𝑙𝑖 is reached. Insertion (Lines 5-12). Starting from the assigned layer 𝑙𝑖 down to the base layer, the algorithm inserts the new multi-vector 𝐷𝑖 iteratively. At each layer, the SEARCH-LAYER routine retrieves a set 𝐶𝑎𝑛𝑑 of candidates, from which the top-𝑀 nearest neighbors are selected to establish bidirectional connections with 𝐷𝑖 . If a neighbor 𝐷 𝑗 ’s degree exceeds 𝑀 after connection, its neighbor list is pruned to retain only the top-𝑀 closest neighbors. The nearest neighbor in 𝐶𝑎𝑛𝑑 also serves as the entry point for the next lower layer. If the assigned layer 𝑙𝑖 of 𝐷𝑖 exceeds that of the current global entry point, 𝐷𝑖 becomes the new global entry point (Lines 13-14). This ensures that the entry point always resides at the highest layer.
Algorithm 2: Accelerate USim Computation Input: Two multi-vectors 𝐷 and 𝑄 associated with weighted 𝑤𝑞 , parameter 𝛽 Output: Approximate result 𝑎𝑛𝑠 1 Clusters 𝐶 1 , · · · , 𝐶 √ ← 𝑘-means over {𝑞𝑣𝑖 ∈ 𝑄 }; |𝑄 | foreach 𝑖-th cluster with centroid 𝐶𝑖 do Initialize an empty 𝛽-sized heap 𝑆𝑖 keyed by distance; 4 foreach token vector 𝑑 𝑗 ∈ 𝐷 do 5 𝑑𝑖𝑠𝑡 ← dis(𝐶𝑖 , 𝑑 𝑗 ); 6 if |𝑆𝑖 | < 𝛽 or key of top tuple in 𝑆𝑖 < 𝑑𝑖𝑠𝑡 then 7 Remove top tuple if |𝑆𝑖 | = 𝛽; 8 Insert (𝑑𝑖𝑠𝑡, 𝑑 𝑗 ) into 𝑆𝑖 ;
2
3.4.2 Algorithm Details. Algo. 2 presents the detailed algorithm. √︁ Line 1 clusters the token vectors 𝑞𝑣𝑖 ∈ 𝑄 into |𝑄 | centroids via k-means clusering [11]. For filtering (Lines 2–8), we perform a 𝛽NN search for each centroid 𝐶𝑖 over all token vectors in 𝐷. Finally, in the refinement step (Lines 9–12), we identify the 𝛾NN for each query token vector 𝑞𝑣𝑖 ∈ 𝑄 by scanning the pruned candidate sets of its cluster and compute the approximate USim value.
3
for cluster 𝑖 ← 1 to 𝛼 do foreach token vector 𝑞𝑣 𝑗 ∈ cluster 𝐶𝑖 do 11 𝑡𝑑𝑖𝑠 ← sum of distance of 𝛾 NN to 𝑞𝑣 𝑗 from 𝑆𝑖 ; 9
10
𝑎𝑛𝑠 ← 𝑎𝑛𝑠 + 12
𝑤𝑞𝑣 𝑗 𝛾
· 𝑡𝑑𝑖𝑠;
return ans;
3.3.3 Complexity Analysis. The complexity of Algo. 1 is derived from the complexity analysis of standard HNSW [20]. Time Complexity. HNSW constructs an index for 𝑛 token vectors in 𝑂 (𝑛 log 𝑛) time. By contrast, our construction algorithm introduces one additional cost per layer: computing USim for multivector pairs during traversal. Each (exact) USim computation takes 𝑂 (𝑑𝑐 2 log 𝛾) time. As 𝑑, 𝑐 and 𝛾 are constants, the overall construction time remains 𝑂 (𝑛 log 𝑛), but with a larger constant factor. Space Complexity. HNSW stores 𝑛 token vectors using 𝑂 (𝑛) space. Our MV-HNSW stores multi-vectors instead, where each node contains 𝑐 token vectors of dimension 𝑑, increasing per-node storage by a factor of 𝑐. Since 𝑑 and 𝑐 are constants, the overall space complexity remains 𝑂 (𝑛).
3.4
Accelerating USim Computation
The computational cost of USim, as revealed by our complexity analysis, is the main bottleneck for building MV-HNSW. Consequently, we target its acceleration to reduce total construction time. 3.4.1 Main Idea: Filter-and-Refine with Clustering. We accelerate the computation of USim(𝑄, 𝐷) using a filter-and-refine strategy coupled with clustering to balance efficiency and accuracy. This method operates at two complementary granularities: (1) Cluster Level √︁ Filtering: The token vectors in the query √︁ 𝑄 are partitioned into |𝑄 | clusters via k-means clustering. This |𝑄 | choice balances the trade-off between granularity and efficiency, as it grows sublinearly with query sizes and is empirically effective. For each cluster centroid, we perform 𝛽NN search over √︁ token vectors in 𝐷 to collect a candidate set of size 𝛽 = max{𝛾, |𝐷 |}. (2) Token-Vector Level Refinement: Each token vector 𝑞𝑣𝑖 ∈ 𝑄 then searches only within its cluster’s candidate set to find its 𝛾NN. Since this step operates only on the pruned candidate set of size 𝛽 (rather than all |𝐷 | token vectors), it retains high efficiency while preserving accuracy with negligible degradation.
Complexity Analysis. Since the number of clusters √︁ for high√ dimensional vectors is typically set to 𝑛, we obtain |𝑄 | clusters √︁ in Line 1 in 𝑂 (|𝑄 | |𝑄 |) time. To balance the time cost between the √︁ filtering and refinement steps, 𝛽 is set to |𝐷 |. Let 𝑐 = max(|𝑄 |, |𝐷 |) be the maximum number of token vectors in a multi-vector. The √ overall time cost of Algo. 2 is then 𝑂 (𝑐 𝑐). Parallelization. The filter-and-refine framework of this optimization algorithm lends itself naturally to√︁ parallel execution. In the filtering phase, the 𝛽NN search for all |𝑄 | centroids are independent and can thus be executed in parallel. Similarly, in the refinement phase, token vectors from different clusters can be processed √︁ concurrently. Overall, the pipeline enables |𝑄 |-way parallelism.
4
AUGMENTED SEARCH ALGORITHM FOR MULTI-VECTOR SIMILARITY SEARCH
This section introduces our augmented search algorithm using MVHNSW. We begin with the main idea in Sec. 4.1, then detail the algorithm in Sec. 4.2, and finally analyze its complexity in Sec. 4.3.
4.1
Main Idea
4.1.1 Motivation. Using MV-HNSW, a straightforward solution to unified multi-vector similarity search is to traverse this index from top to bottom while progressively collecting 𝑘 nearest candidates to the query 𝑄, following the search method of HNSW [20]. However, due to the dynamic nature of queries and the finite degree constraints in MV-HNSW, a critical issue arises: multi-vectors in the exact result may be topologically distant from, or even disconnected from, the traversed nodes. This is because the index is constructed based on multi-vector similarity among data objects, but the search procedure relies on similarity between data objects and the query. This mismatch can prevent the search from reaching relevant candidates, leading to impaired recall and causing the algorithm to become trapped in local optima. 4.1.2 Key Idea. To address this issue, we enhance the graph traversal by dynamically expanding the candidate list. While exhaustively scanning all multi-vectors would achieve this goal in principle, it is computationally intractable for large-scale datasets. Thus, we propose a local-to-global inference strategy to infer promising global candidates using locally identified candidates. This strategy starts from local neighborhoods in the graph index and leverages the precomputed correlations to reach distant but relevant multi-vectors that might otherwise remain undiscovered. The core idea is twofold: (1) Offline Pre-Processing: We pre-compute for each token vector a list of multi-vectors containing token vectors correlated with it in the dataset, stored in an Auxiliary Navigation Table (ANT). (2) Online Search: When exploring a multi-vector 𝑉 from the dynamic candidate list, we expand the search scope by leveraging
ANT for multi-vectors containing high correlated token vectors of 𝑉 ’s token vectors (and thus similar to those in 𝑄), bridging structural gaps in the graph index.
4.2
Augmented Search Algorithm
4.2.1 Core Components. To realize the above idea, we introduce two technical components: auxiliary navigation table and dynamic candidate expansion strategy. (1) Auxiliary Navigation Table (ANT). For each token vector 𝑣 in every multi-vector 𝑉 in the dataset D, we pre-compute an 𝑀-sized list of relevant multi-vectors to 𝑣, denoted by AN T (𝑣), where 𝑀 is the node degree in MV-HNSW. To construct this list, we first use the standard HNSW index [20] to retrieve a set 𝐴 of 𝑀 ′ nearest token vectors to 𝑣 from all token vectors, excluding those within 𝑉 . Here, 𝑀 ′ is set to a constant multiple of 𝑀 (e.g., 5𝑀 in our implementation) to ensure sufficient candidates after removal. We then consider the multi-vectors that contain at least one token vector in 𝐴, and for each such multi-vector, we compute the sum of distances between 𝑣 and its top-𝛾 nearest token vectors in 𝐴. Finally, we retain the top-𝑀 multi-vectors based on this sum. (2) Dynamic Candidate Expansion Strategy. During online search, after exploring the connected neighbors of a candidate multi-vector 𝑉 , we invoke dynamic candidate expansions as follows. For each token vector 𝑣 ∈ 𝑉 , we collect all the multi-vectors in AN T (𝑣) via ANT and form the expansion candidate set E = Ð 𝑣 ∈𝑉 AN T (𝑣). This set has up to |𝑉 | · 𝑀 distinct multi-vectors, so computing the USim scores between these multi-vectors and the query 𝑄 is costly. Instead, we quantify the priority of each multivector 𝑉 ∈ E based on Eq. (7)–Eq. (9) and only select the top-𝑀 multi-vectors to be expanded from E. ∑︁ Contrib(𝑣, 𝑄) = I 𝑣 ∈ 𝛾 NN(𝑞, 𝑉 ) · 𝑤𝑞 · dis(𝑞, 𝑣) (7) 𝑞 ∈𝑄
exp (Contrib(𝑣, 𝑄)) Weight(𝑣, 𝑄) = Í ′ 𝑣 ′ ∈𝑉 exp (Contrib(𝑣 , 𝑄)) ( ∑︁ Priority(𝑉 ′, 𝑄) = max Weight(𝑣, 𝑄) 𝑣 ∈𝑉
(8) ) dis(𝑣, 𝑣 ′ )
(9)
𝑣 ′ ∈𝛾 NN(𝑣,𝑉 ′ )
Specifically, Contrib(𝑣, 𝑄) defined in Eq. (7) measures the contribution of a token vector 𝑣 ∈ 𝑉 to the unified multi-vector similarity USim(𝑄, 𝑉 ), where I(·) is an indicator function. Weight(𝑣, 𝑄) in Eq. (8) is derived using softmax normalization to amplify highcontribution token vectors and suppress low-impact ones. Based on this, Priority(𝑉 ′, 𝑄) quantifies the priority score between the candidate multi-vector 𝑉 ′ and the query 𝑄. To avoid the expensive computation of USim(𝑄, 𝑉 ′ ), Priority(𝑉 ′, 𝑄) estimates the similarity between 𝑉 ′ and 𝑄 by considering, among all token vectors 𝑣 ∈ 𝑉 , the one that best matches 𝑉 ′ (via its 𝛾 NN in 𝑉 ′ ), weighted by 𝑣’s relevance to 𝑄. We adopt this max-based aggregation for two reasons: (1) to accelerate priority computation, and (2) to avoid confining the online search to graph-connected neighbors of 𝑉 and uncover topologically distant yet closely relevant candidates. 4.2.2 Algorithm Details. Algo. 3 optimizes the SEARCH-LAYER algorithm in the HNSW index [20] by incorporating our dynamic expansion strategy. The search procedure initializes 𝐶𝑎𝑛𝑑 as the
Algorithm 3: Augmented SEARCH-LAYER Input: A query multi-vector 𝑄, MV-HNSW index, ANT, entry points 𝑒𝑝 at current layer 𝑙𝑐 , search candidate list with size 𝑒 𝑓 𝑆 Output: 𝑒 𝑓 𝑆 most similar multi-vectors to 𝑄 at layer 𝑙𝑐 1 𝐶𝑎𝑛𝑑 ← 𝑒𝑝, 𝑄𝑢𝑒𝑢𝑒 ← 𝑒𝑝; 2 while 𝑄𝑢𝑒𝑢𝑒 is not empty do 3 (𝑉𝑐 , dis𝑐 ) ← most dissimilar node to 𝑄 in 𝐶𝑎𝑛𝑑; 4 (𝑉𝑞 , dis𝑞 ) ← most similar node to 𝑄 in 𝑄𝑢𝑒𝑢𝑒, pop it; 5 if dis𝑐 > dis𝑞 then break; 6 𝐸𝑥𝑁 ← direct neighbors of 𝑉𝑞 in layer 𝑙𝑐 ; // Dynamic Expansion Strategy 7 Max-heap ℎ𝑒𝑎𝑝 ← ∅ ; // Key: Priority(·, 𝑄) 8 foreach token vector 𝑣 ∈ 𝑉𝑞 do 9 𝑉 ′ ← the first multi-vector in AN T (𝑣); 10 ℎ𝑒𝑎𝑝 ← ℎ𝑒𝑎𝑝 ∪ {(Priority(𝑉 ′, 𝑄), 𝑉 ′, 𝑣)}; 11 12 13 14 15 16 17 18 19 20 21
22
foreach iteration 𝑖 ← 1 to 𝑀 do (𝑉 , 𝑣) ← pop the top tuple from ℎ𝑒𝑎𝑝; 𝐸𝑥𝑁 ← 𝐸𝑥𝑁 ∪ {𝑉 }; 𝑉 ′ ← the next multi-vector in AN T (𝑣); ℎ𝑒𝑎𝑝 ← ℎ𝑒𝑎𝑝 ∪ {(Priority(𝑉 ′, 𝑄), 𝑉 ′, 𝑣)}; foreach unvisited multi-vector 𝑉 ∈ 𝐸𝑥𝑁 do Mark 𝑉 as visited, dis ← USim(𝑄, 𝑉 ); (𝑉𝑐 , dis𝑐 ) ← most dissimilar node to 𝑄 in 𝐶𝑎𝑛𝑑; if |𝐶𝑎𝑛𝑑 | < 𝑒 𝑓 𝑆 or dis > dis𝑐 then Insert (𝑉 , dis) into 𝐶𝑎𝑛𝑑, keep |𝐶𝑎𝑛𝑑 | ≤ 𝑒 𝑓 𝑆; Push (𝑉 , dis) into 𝑄𝑢𝑒𝑢𝑒; return 𝐶𝑎𝑛𝑑;
candidate answer set and 𝑄𝑢𝑒𝑢𝑒 as the priority queue during traversal, both with the entry points 𝑒𝑝 (Line 1). 𝐶𝑎𝑛𝑑 maintains the top-𝑒 𝑓 𝑆 most similar results found so far, while 𝑄𝑢𝑒𝑢𝑒 stores nodes pending expansion, ordered by their similarity to the query 𝑄. At each iteration, let 𝑉𝑐 ∈ 𝐶𝑎𝑛𝑑 be the candidate most dissimilar to 𝑄 and 𝑉𝑞 ∈ 𝑄𝑢𝑒𝑢𝑒 the multi-vector most similar to 𝑄 so far. If the worst candidate 𝑉𝑐 is more similar to 𝑄 than the best node 𝑉𝑞 awaiting for expansion, the search loop terminates (Line 5); otherwise, the algorithm proceeds to expand from 𝑉𝑞 . The set of neighbors 𝐸𝑥𝑁 expanded from 𝑉𝑞 consists of two subsets: (1) the direct neighbors of 𝑉𝑞 in MV-HNSW (Line 6), and (2) those generated by the dynamic expansion strategy (Lines 7–15). For the latter, each token vector 𝑣 ∈ 𝑉𝑞 contributes the first multi-vector in its associated list AN T (𝑣) as an initial candidate. This candidate 𝑉 ′ is inserted into a max-heap keyed by Priority(𝑉 ′, 𝑄). Lines 11– 14 then repeatedly extract the top tuple from this heap and append it to 𝐸𝑥𝑁 , the set of nodes awaiting expansion. This extraction repeats 𝑀 times, so 𝐸𝑥𝑁 contains at most 2𝑀 multi-vectors, where 𝑀 is the node degree. Finally, Lines 16–21 process each unvisited node 𝑉 ∈ 𝐸𝑥𝑁 . If this node 𝑉 is more similar to 𝑄 than any node in 𝐶𝑎𝑛𝑑 (or if |𝐶𝑎𝑛𝑑 | < 𝑒 𝑓 𝑆), then 𝑉 is inserted into both 𝐶𝑎𝑛𝑑 and 𝑄𝑢𝑒𝑢𝑒, and 𝐶𝑎𝑛𝑑 is trimmed to maintain a size of at most 𝑒 𝑓 𝑆.
Table 2: Statistics of datasets (M: Million, B: Billion) Dataset Recreation Lifestyle Writing Science Technology Pooled Macro
Dim. 128–768 128–768 128–768 128–768 128–768 128–768 128–768
#(Token Vector) 263.0 M 268.9 M 277.1 M 343.6 M 127.6 M 2.429 B 8.842 B
#(Query) 563 417 497 538 916 2.931 K 101.1 K
Compared Algorithms. We select four representative methods for multi-vector similarity search as the major competitors, including ColBERT[15], ColBERTv2[27], XTR[16], and WARP[28]. The parameter configurations for each algorithm follow their implementation recommendations. • ColBERT [15]: This work introduce the multi-vector similarity search problem and the MaxSim operator. This algorithm retrieves 𝛼 · 𝑘 candidate token vector for each query token vector using HNSW [20], then re-ranks the corresponding multi-vectors by computing the exact USim value. Following the original paper, we set 𝛼 = 0.5. The HNSW parameters are set to 𝑀 = 32 (node degree) and 𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 = 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ = 40 (candidate list sizes). • ColBERTv2 [27]: This work introduces residual compression that clusters embeddings to reduce storage, along with a centroid-based index to improve efficiency. We adopt the open-source implementation [31] with default parameters. • XTR [16]: This solution was developed by Google DeepMind and inspired recent state-of-the-art (e.g., WARP [28] and ColXTR [4]). Like ColBERT, XTR retrieves candidate multi-vectors by collecting token vectors similar to each query token vector. However, unlike the re-rank procedure of ColBERT, XTR computes an approximate USim value using only the token vectors already retrieved. • WARP [28]: WARPis a state-of-the-art solution designed for large-scale datasets using the IVF index. We set 𝑛𝑝𝑟𝑜𝑏𝑒 = 32 (clusters probed), 𝑡 ′ = 40000 (cumulative cluster size threshold), and 𝑏 = 4 (residual compression rate).
Remark. The dynamic expansion strategy is designed to select 𝑀 Ð multi-vectors from the union set E = 𝑣 ∈𝑉𝑞 AN T (𝑣) according to their Priority(·, 𝑄) defined in Eq. (9). Rather than exhaustively scanning the entire set E, the algorithm adaptively retrieves one multi-vector from each AN T (𝑣) list at a time in Lines 11–15. This optimization is effective for two reasons. First, Weight(𝑣, 𝑄) in Eq. (9) remains constant for a given token vector 𝑣 across all candidate multi-vectors in AN T (𝑣). Second, each list AN T (𝑣) Í is pre-ordered by the remaining term 𝑣 ′ ∈𝛾 NN(𝑣,𝑉 ′ ) dis(𝑣, 𝑣 ′ ). Consequently, for any list AN T (𝑣), the front multi-vector always has a higher priority than any subsequent multi-vector in the same list. This monotonic property ensures that Lines 8–15 yield the top-𝑀 multi-vectors from E without requiring a full scanning of E.
4.3
Complexity Analysis
We mainly analyze the time complexity of our search algorithm, as the ANT requires only 𝑂 (𝑛𝑐 ·𝑀) ∼ 𝑂 (𝑛) space. The time complexity is examined in two phases: offline pre-processing and online search. Offline Pre-Processing. The time overhead for constructing the ANT consists of two main steps: (1) building a single-vector HNSW index over all the token vectors VD , and (2) executing a 𝑘NN search on this index for every token vector. This leads to an overall offline pre-processing complexity of O (|VD | log |VD |). Online Search. Algo. 3 optimizes the standard SEARCH-LAYER procedure by adapting the dynamic candidate expansion strategy. This algorithm additionally performs 𝑂 (𝑀 + |𝑉𝑞 |) heap operations for each explored node 𝑉𝑞 . As 𝑀 and |𝑉𝑞 | are constants in practice, each online search requires 𝑂 (log 𝑛) time.
5
EXPERIMENTAL STUDY
5.1
Experimental Setup
Datasets. We evaluate our method on seven multi-vector datasets derived from two real-world benchmark corpora: LoTTE [27] and MS MARCO [23]. As summarized in Table 2, these datasets cover a broad range of scales, from 263 million to nearly 9 billion token vectors. Each dataset provides token-level embeddings generated by the representation model of ColBERTv2[27] in four dimensionalities (128, 256, 512, and 768). Each dataset also includes a set of queries of varying scales, which are similarly processed into token-level embeddings (i.e., multi-vectors). To establish the ground truth, we perform a brute-force linear scan to compute the exact USim and rank the results to identify the exact answer. Notice that the above data preparation pipeline is commonly adopted by existing research on multi-vector similarity search [7, 15, 16, 18, 26–28]. All datasets use the MaxSim multi-vector similarity function.
Beyond these algorithms, we also compare our solution with Qdrant [1], a vector database that provides a ColBERT-based solution for multi-vector similarity search. Although Qdrant incorporates system-level optimizations, experimental results show that our MV-HNSW achieves superior search performance (see our full paper [35] for details). Metrics. We assess the performance of all methods based on two criteria: search performance and index construction cost. For search performance, we use recall (defined in Eq. (3)) to measure the accuracy of the retrieved results, and search time (average time per query) to measure time efficiency. For index construction cost, we measure construction time and index size. Implementation and Environment. All methods, including our proposed approach and baselines, are implemented in C++ and Python, with C++ components compiled using g++. Experiments are conducted on a server equipped with 32 AMD Ryzen 9 5950X 3.40GHz Processor with 128 GB RAM, running Ubuntu 24.04.2. For index construction, our algorithm leverages multi-threading, while all other methods and all search experiments are conducted in a single-threaded environment. Our source code and datasets are publicly available on GitHub [2].
5.2
Overall Search Performance
We evaluate search performance by measuring recall and search time and illustrating the results using recall-time curves. A timerecall curve visualizes the trade-off between accuracy and efficiency, with recall on the x-axis and search time (in milliseconds) on the y-axis. This representation highlights how much time an algorithm
3
10
2
20
40
60
Recall (%)
80
4
10
3
10
2
100
20
10
3
10
2
20
40
60
Recall (%)
80
10
3
10
2
100
20
80
10
4
10
3
10
2
100
20
(e) Technology
40
60
Recall (%)
40
60
80
Recall (%)
10
4
10
3
10
2
100
20
(c) Writing
Search Time (ms)
10
60
Recall (%)
4
(b) Lifestyle
Search Time (ms)
Search Time (ms)
(a) Recreation 4
40
10
Search Time (ms)
10
10
Search Time (ms)
4
Search Time (ms)
Search Time (ms)
10
80
10
4
10
3
10
2
100
20
(f) Pooled
40
60
Recall (%)
40
60
Recall (%)
80
100
(d) Lifestyle
80
100
(g) Macro
10 50 100 200 Dataset Cardinality n (k multi-vectors) (a) Recall (Pooled)
80 60 10 50 100 200 Dataset Cardinality n (k multi-vectors)
10
6
10
5
10
4
Search Time (ms)
60
Search Time (ms)
80
Recall (%)
Recall (%)
Figure 2: Search performance on all seven real-world datasets (with default query parameter 𝑘 = 128)
10 50 100 200 Dataset Cardinality n (k multi-vectors)
(b) Recall (Macro)
(c) Time (Pooled)
10
5
10
4
10 50 100 200 Dataset Cardinality n (k multi-vectors) (d) Time (Macro)
Figure 3: Scalability test with varying dataset cardinality 𝑛 requires to achieve a given recall level. Consequently, a curve that is shifted towards the bottom-right corner indicates superior performance, as it achieves higher recall with lower latency. Fig. 2 shows the recall-time curves on all the datasets under the default parameter settings: the number of required nearest neighbors 𝑘 = 128, the dimensionality of each token vector 𝑑 = 128, and the number of token vectors in each multi-vector 𝑐 = 32. As the results show, our method MV-HNSW consistently outperforms the baselines across all datasets. Recall. Our MV-HNSW achieves substantially higher recall than the compared baselines. On all seven datasets, it attains over 90% recall with minimal latency. In contrast, the baselines generally fall into two categories: high-latency and ultra-fast methods. Highlatency baselines, such as ColBERTv2, prioritize recall but incur significant computational overhead. When fixing search latency at 1.2 to 3.9 seconds, their recall saturates at around 80%, and even at this level, their latency remains 2.4–25.2× higher than that of our method at 90% recall. Ultra-fast baselines (represented by XTR) sacrifice recall (hovering around 50%) for extremely low latency (10 to 100 ms) but fail to scale to higher recall tiers. Search Latency. Our method demonstrates superior efficiency when targeting high recall. While baseline methods exhibit explosive latency growth as recall increases, our approach maintains consistently low latency. For example, to reach a target recall of 90% across all datasets, our method achieves a speedup of 5.6–14.0× over the fastest competing baseline.
5.3
Scalability Test
We evaluate scalability on on Pooled and Macro datasets by varying three key parameters: the total number 𝑛 of multi-vectors, the number 𝑐 of token vectors per query multi-vector, and the dimensionality 𝑑 of each token vector. Due to page limitations, please refer to our full paper [35] for results on the other datasets. 5.3.1 Varying Dataset Cardinality. The total number of vectors in the dataset (i.e., cardinality) is the primary metric for evaluating data scalability. To assess this, we conduct scalability tests on dataset subsets of varying sizes, with 𝑛 ∈ {1 × 104, 5 × 104, 1 × 105, 5 × 105 }, and compare our method against the baselines. Latency Scaling. Across all datasets, our method exhibits slow and stable growth in search latency as the dataset size increases. Specifically, the latency growth trend remains logarithmic in logscale coordinates, which closely aligns with the time complexity analysis presented in Sec. 4.3. Overall, our method achieves a significant latency advantage over all baselines, with the sole exception of XTR. However, the low recall of XTR undermines its practicality, underscoring the importance of the recall-latency balance achieved by our approach. Recall Stability. Our method maintains robust recall performance as the dataset scale expands. The overall recall trend of our MV-HNSW remains consistently high, staying at approximately 90% across all dataset sizes and vastly outperforming all compared algorithms. This demonstrates the superior scalability of our MVHNSW in preserving search accuracy over large-scale datasets.
Warp
70 60 50 16 32
64
Search Time (ms)
90
80
Recall (%)
Recall (%)
90
ColBERTv2
80 70 60 16 32
128
64
128
10
4
10
3
10
2
16 32
Query Multi-Vector Scale c
Query Multi-Vector Scale c
(a) Recall (Pooled)
XTR
MV-HNSW Search Time (ms)
ColBERT
64
10
4
10
3
10
2
128
16 32
Query Multi-Vector Scale c
(b) Recall (Macro)
64
128
Query Multi-Vector Scale c
(c) Time (Pooled)
(d) Time (Macro)
60 40 128 256
512
Dimensionality d
Search Time (ms)
80
Recall (%)
Recall (%)
100 80 60 40
768
128 256
512
Dimensionality d
(a) Recall (Pooled)
768
10
4
10
3
10
2
Search Time (ms)
Figure 4: Scalability test with varying the number 𝑐 of token vectors per query multi-vector
128 256
512
Dimensionality d
(b) Recall (Macro)
768
10
3
10
2
128 256
512
Dimensionality d
(c) Time (Pooled)
768
(d) Time (Macro)
Figure 5: Scalability test with varying the dimensionality 𝑑 of token vectors
60
80 70 60
32 64
128
Query Parameter k
(a) Recall (Pooled)
256
50
32 64
128
Query Parameter k
256
8000
Search Time (ms)
Recall
Recall
80
Search Time (ms)
90
6000 4000 2000 0
32 64
128
Query Parameter k
(b) Recall (Macro)
256
(c) Time (Pooled)
6000 4000 2000 0
32 64
128
Query Parameter k
256
(d) Time (Macro)
Figure 6: Impact of the number 𝑘 of nearest neighbors 5.3.2 Varying the Number of Token Vectors Per Query Multi-Vector. In practice, the number 𝑐 of token vectors per query multi-vector directly impacts search latency. Accordingly, we evaluate search performance by varying 𝑐 ∈ {16, 32, 64, 128} on the datasets. Fig. 4 illustrates the search time and recall results, respectively. Search Latency. Our method exhibits efficient sub-linear time complexity as the number of token vectors per query increases. It consistently outperforms all compared algorithms except XTR. As the parameter 𝑐 doubles, the growth rate of our search time remains significantly lower than that of the baselines, demonstrating a sublinear trend that aligns with our time complexity analysis. When 𝑐 reaches the maximum 128, our method achieves a speedup up to 2.3× over ColBERT and a speedup of 11.9–31.6× over WARP and ColBERTv2. However, as discussed below, XTR’s extreme speed comes at the cost of severely limited recall. Recall Stability. Our method maintains exceptional recall stability regardless of the number 𝑐 of token vectors per query, consistently achieving approximately 90% recall across all 𝑐 values. In contrast, the maximum recall of other algorithms does not exceed 80%. Notably, while XTR exhibits high efficiency, its recall remains below 60% across the tests and drops below 50% at certain 𝑐 values. 5.3.3 Search Performance on Varied Dimensionality. Dimensionality 𝑑 is another natural metric for scalability evaluation, and we
evaluate the search performance by varying 𝑑 ∈ {128, 256, 512, 768} over a sample of each dataset. Fig. 5 presents the corresponding recall and search time. Recall. As 𝑑 varies, our algorithm consistently maintains recall around 95% and never drops below 90%, demonstrating its advantage on search accuracy. In contrast, the recall of the baselines fluctuates significantly between 20% and 80%, showing high sensitivity to dimensionality changes. Search Time. Across all tested dimensions, our algorithm outperforms all baselines in terms of search time, with the sole exception of XTR. Although XTR achieves the optimal efficiency, its recall fluctuates drastically with varying 𝑑 and remains below 60% on most datasets.
5.4
Impact of Query Configuration
This experiment evaluates the impact of the query parameter 𝑘 and a different similarity metric on the Pooled and Macro datasets. Due to page limitations, please refer to [35] for other results. 5.4.1 Impact of Query Parameter 𝑘. 𝑘 controls the number of nearest neighbors returned. To evaluate sensitivity under varying 𝑘, we conduct experiments with 𝑘 ∈ {32, 64, 128, 256} in Fig. 6.
Macro Compared Algorithms
Pooled
𝛾 =2
𝛾 =8
𝛾 =2
𝛾 =8
Recall
Time
Recall
Time
Recall
Time
Recall
Time
Linear Scan
-
862.6
-
1104.1
-
1589.0
-
1912.6
XTR MV-HNSW
58.9 96.0
51.9 173.7
54.3 96.0
51.7 216.1
50.7 94.9
54.5 228.8
54.3 95.3
51.7 260.3
Table 4: Index construction (time: h, size: GB) Compared Writing Science Pooled Macro Algorithms Time Size Time Size Time Size Time Size ColBERT 1.85 ColBERTv2 0.37 XTR 6.62 WARP 0.69 MV-HNSW 21.29
3.58 2.18 0.50 0.41 3.60 6.09 1.06 0.81 7.65 21.06
4.11 2.04 0.22 1.29 4.13 6.58 1.21 0.78 6.22 18.09
3.93 0.92 1.76 0.55 0.58 0.25 3.95 7.74 1.76 0.95 0.33 0.52 6.90 13.81 10.73
Search Time. The search time of our method is stable across different values of 𝑘. Unlike ColBERTv2, which exhibits (nearly) linear search time growth as 𝑘 increases, our search time remains nearly flat and constant even as 𝑘 doubles. Moreover, our method is significantly faster than all high-recall baselines, such as ColBERTv2 and WARP. For example, it achieves an 6.9–19.7× speedup over ColBERTv2. While XTR achieves lower latency, it sacrifices too much accuracy to be practically viable, particularly as its recall degrades further with larger 𝑘. Recall. Our method strictly dominates all baselines in recall as 𝑘 scales. It consistently maintains a recall of approximately 90%, surpassing the 80% ceiling observed across all compared algorithms. Furthermore, our method exhibits strong stability: as 𝑘 grows exponentially, the recall curve remains smooth and shows minimal degradation. This robustness is attributed to the effectiveness of our underlying graph-based index structure and optimized search algorithm, which ensure that the candidate set captures the majority of ground truth objects efficiently. 5.4.2 Beyond MaxSim Multi-vector Similarity. We conducted experiments on another multi-vector similarity function, aggregate 𝛾NN [16]. Since other algorithms do not natively support aggregated 𝛾NN, we only compare against XTR. As shown in Table 3, our algorithm achieves a recall of over 94.9% across both datasets, substantially outperforming XTR, which attains only 50.7%–58.9%. This represents a relative improvement of 60%–87% in recall. In terms of query latency, our algorithm is approximately 3–5× slower than XTR. However, this latency remains well within an acceptable range for practical applications, especially given the significant recall gains.
5.5
Experiment on Index Construction
This experiment evaluates the index construction time and index size on on Writing, Science, Pooled, and Macro datasets. Please refer to [35] for the complete results. Overall, while our method incurs higher costs, the overhead remains manageable and acceptable for real-world datasets. Index Size. As shown in Table 4, ColBERTv2 and WARP, exhibit the most compact index sizes. In contrast, algorithms based
on token-vector HNSW (ColBERT and XTR) incur an index size roughly 3.4× larger than that of WARP. Our MV-HNSW yields a slightly larger index size than ColBERT and XTR, but remains well within an acceptable range. Construction Time. Among the baselines, ColBERT, ColBERTv2, and WARP demonstrate exceptionally high efficiency in index construction. The average construction time for XTR is approximately 9.5× that of WARP and 3.8× that of ColBERT. To achieve better online search performance, our proposed algorithm incurs a longer index construction time than these baselines. Notably, our ablation study shows that this overhead can be significantly reduced by using more threads during construction.
5.6
Ablation Study
We conduct ablation studies to evaluate the effectiveness of the proposed optimization methods: efficient USim computation (Sec. 3.4) and augmented search layer (Sec. 4). 5.6.1 Optimization #1: Accelerated USim Computation. This optimization accelerates the computation of the USim operator, thereby improving both index construction time and search latency. In this ablation study, we focus on evaluating its impact on index construction, as the acceleration effect is identical for both phases: the optimized USim computation is invoked in the same manner during indexing and searching. Fig. 7 illustrates the index construction performance on the Pooled, Science, and Writing datasets, comparing results with and without optimization #1. To isolate the overhead introduced by multi-vectors, we include an extra baseline (named “token-only HNSW”) that builds a standard HNSW index over all token vectors in each dataset. This baseline serves as a reference point for understanding the computational cost of our multi-vector index. Applying optimization #1 yields a substantial reduction in index construction time. For constructing a 128-dimensional multi-vector indexs with 10,000 data objects on these datasets, the construction time of our MV-HNSW is reduced to 3.1–3.3× that of token-only HNSW. Without optimization #1, this overhead increases to 10.9– 13.6×. These results confirm that optimization #1 effectively mitigates the computational complexity introduced by the multi-vector structure in the graph index.
Construction Time (min)
Table 3: Experiment on Aggregate 𝛾NN (recall: %, time: ms)
Token-Only HNSW
With Optimization #1
Without Optimization #1
Writing
Pooled
200 100 0
Science
Figure 7: Ablation study on Optimization #1 5.6.2 Optimization #2: Augmented Search Layer. This optimization enhances search accuracy by introducing an auxiliary index and a dynamic candidate expansion strategy. We compare the standard HNSW search algorithm [20] with our augmented search strategy on the same MV-HNSW structure constructed over the Lifestyle, Writing, Technology, and Macro datasets.
Fig. 8 presents the recall results with and without optimization #2 across all datasets. The results demonstrate that our augmented search algorithm consistently improves recall compared to the standard search method. This is because our algorithm explores candidates that are topologically distant or disconnected from the traversed nodes, whereas the baseline, strictly following connected edges, inevitably becomes trapped in local optima. Without Optimization #2
With Optimization #2
Recall
94 92 90 88
Writing Technology Macro Lifestyle Figure 8: Ablation study on Optimization #2
5.7
Summary of Major Findings
Our experimental study yields the following key findings: • Balanced Search Performance. Our MV-HNSW achieves the best trade-off between recall and efficiency. It usually maintains over 90% recall with competitive search time and can be 5.6–14.0× faster than the baselines at the same recall level. As dataset scale and query parameters vary, our method maintains stable recall with only modest growth in the search latency. • Acceptable Offline Trade-offs. The superior online search performance comes at the increased cost of offline indexing. Although our index construction time and size exceed those of some baselines, they remain practical for real-world deployments, thanks to our accelerated USim computation optimization, which achieves up to 10.9–13.6× speedup. • Baseline Comparison. Among the baselines, ColBERT strikes the most balanced trade-off between recall and search time. XTR prioritizes efficiency at the expense of recall, while ColBERTv2 and WARP sacrifice efficiency to achieve moderate recall levels. Overall, none of these baselines achieves consistently satisfactory search performance.
6
RELATED WORK
We review related work in the following two categories: multi-vector similarity search and approximate nearest neighbor search. Multi-Vector Similarity Search. Prior studies on this problem adopt a filter-and-refine framework. The filter phase is used to prune the entire dataset to a small set of candidate multi-vectors, avoiding the expensive USim computation over all multi-vectors. In the refine phase, the exact USim score is computed between the query and all candidates generated to determine the final results. Based on the filtering strategy, existing work can be broadly classified into three categories: bound estimation, clustering-based, and lexical-based methods. Bound estimation methods [15–17] estimate lower bounds of USim using single-vector distances between query and data objects. Clustering-based methods [7, 18] focus on token-vector-level matching, pruning objects based on single-vector
distances when their original tokens exactly match or are semantically similar. Lexical-based methods [26–28] rely on clustering and quantization techniques. These methods exploit semantic locality by clustering token vectors within each multi-vector and quantizing their residuals to reduce storage cost. During search, multi-vectors are pruned if they contain no token vectors belonging to centroids close to the query’s token vectors. We select the state-of-the-art method from each category as our primary competitors: ColBERT [15], ColBERTv2 [27], XTR [16], and WARP [28]. Existing methods prune multi-vectors by leveraging token vectors but often overlook the rich inter-multi-vector information, leading to the inadvertent pruning of relevant candidates and thus limiting search performance. By contrast, our solution organizes data objects at the multi-vector level and navigates the search process accordingly, thereby enhancing both recall and efficiency. Approximate Nearest Neighbor Search. Approximate nearest neighbor search (ANNS) indexes are extensively leveraged in existing multi-vector similarity search algorithms. Josef et al. [30] pioneered the use of k-means clustering for high-dimensional ANN search and introduced the Inverted File (IVF) index to record vector IDs belonging to each cluster centroid. Jegou et al. [13] advanced this solution by representing vectors as residuals to their cluster centroids and applying Product Quantization (PQ) to compress these residuals. Wang et al. [34] later observed that residuals are more concentrated within the IVF framework, enabling further compression for improved efficiency. In multi-vector similarity search, clustering-based methods [15–17] adopt a similar filtering paradigm. Additionally, some lexical-based methods, such as COIL [7], employ IVF to manage vector IDs associated with each token type. Graph-based indexes offer a superior accuracy-efficiency tradeoff among ANN methods [33], with representative solutions like HNSW [20], LSH-APG [36], and SHG [10]. Among these, HNSW is widely regarded as the state-of-the-art [24] and is widely used in bound estimation methods for multi-vector similarity search to manage token vectors and derive heuristic information. However, despite the success of graph-based indexes in the ANN setting, no existing work applies graph indexing directly to multi-vector data.
7
CONCLUSION
Fine-grained semantic retrieval in RAG and LLM systems increasingly demands accurate and scalable multi-vector similarity search. Existing approaches predominantly follow a filter-and-refine framework: they first apply heuristics based on single-vector similarity to filter candidates, then refine the results. However, this heuristic filter stage ignores the rich information embedded in multi-vector data, leading to solutions that are either inaccurate or inefficient. To address these limitations, we formalize the Unified Multi-Vector Similarity Search problem. We propose MV-HNSW, a hierarchical graph index tailored for multi-vector data using a novel edge-weight function that rigorously satisfies three core properties: symmetry, cardinality robustness, and query consistency. We further develop optimized algorithms for index construction and query processing, and provide a thorough complexity analysis. Experimental results on seven real-world datasets demonstrate that our solution achieves a superior balance between accuracy and efficiency compared to state-of-the-art methods. MV-HNSW accelerates search latency by up to 5.6–14.0× while stably maintaining over 90% recall.
References [1] [2] [3] [4]
2026. Qdrant. https://qdrant.tech/ Accessed: 2026-03-01. 2026. Source Code and Dataset. https://github.com/oldherd/MV-HNSW. 2026. Weaviate. http://weaviate.io Accessed: 2026-03-01. Riyaz Ahmad Bhat and Jaydeep Sen. 2025. XTR meets ColBERTv2: Adding ColBERTv2 Optimizations to XTR. In Proceedings of the 31st International Conference on Computational Linguistics: Industry Track. 358–365. [5] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2025. The faiss library. IEEE Transactions on Big Data (2025). [6] Manuel Faysse, Hugues Sibille, Tony Wu, Bilel Omrani, Gautier Viaud, Céline Hudelot, and Pierre Colombo. 2025. ColPali: Efficient Document Retrieval with Vision Language Models. In ICLR. [7] Luyu Gao, Zhuyun Dai, and Jamie Callan. 2021. COIL: Revisit exact lexical match in information retrieval with contextualized inverted list. arXiv preprint arXiv:2104.07186 (2021). [8] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Qianyu Guo, Meng Wang, and Haofen Wang. 2023. Retrieval-Augmented Generation for Large Language Models: A Survey. CoRR abs/2312.10997 (2023). [9] Ankit Garg, Kirankumar Shiragur, Neeraj Kayal, et al. 2025. Incorporating Token Importance in Multi-Vector Retrieval. arXiv preprint arXiv:2511.16106 (2025). [10] Zengyang Gong, Yuxiang Zeng, and Lei Chen. 2025. Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts. PVLDB 18, 10 (2025), 3518–3530. [11] Jiawei Han, Micheline Kamber, and Jian Pei. 2011. Data Mining: Concepts and Techniques, 3rd edition. Morgan Kaufmann. [12] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC). 604–613. [13] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128. [14] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick SH Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense Passage Retrieval for Open-Domain Question Answering.. In EMNLP (1). 6769–6781. [15] Omar Khattab and Matei Zaharia. 2020. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval. 39–48. [16] Jinhyuk Lee, Zhuyun Dai, Sai Meher Karthik Duddu, Tao Lei, Iftekhar Naim, Ming-Wei Chang, and Vincent Zhao. 2023. Rethinking the role of token retrieval in multi-vector retrieval. Advances in Neural Information Processing Systems 36 (2023), 15384–15405. [17] Minghan Li, Sheng-Chieh Lin, Xueguang Ma, and Jimmy Lin. 2023. Slim: Sparsified late interaction for multi-vector retrieval with inverted indexes. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 1954–1959. [18] Minghan Li, Sheng-Chieh Lin, Barlas Oguz, Asish Ghoshal, Jimmy Lin, Yashar Mehdad, Wen-tau Yih, and Xilun Chen. 2023. CITADEL: Conditional token interaction via dynamic lexical routing for efficient and effective multi-vector retrieval. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 11891–11907. [19] Antoine Louis, Vageesh Kumar Saxena, Gijs van Dijck, and Gerasimos Spanakis. 2025. ColBERT-XM: A Modular Multi-Vector Representation Model for ZeroShot Multilingual Information Retrieval. In Proceedings of the 31st International
Conference on Computational Linguistics. 4370–4383. [20] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836. [21] Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. [22] Franco Maria Nardini, Cosimo Rulli, and Rossano Venturini. 2024. Efficient multivector dense retrieval with bit vectors. In European Conference on Information Retrieval. Springer, 3–17. [23] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016. Ms marco: A human-generated machine reading comprehension dataset. (2016). [24] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. The VLDB Journal 33, 5 (2024), 1591–1615. [25] Cheoneum Park, Seohyeong Jeong, Minsang Kim, KyungTae Lim, and YongHun Lee. 2025. SCV: Light and Effective Multi-Vector Retrieval with Sequence Compressive Vectors. In Proceedings of the 31st International Conference on Computational Linguistics: Industry Track. 760–770. [26] Keshav Santhanam, Omar Khattab, Christopher Potts, and Matei Zaharia. 2022. PLAID: an efficient engine for late interaction retrieval. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 1747–1756. [27] Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. 2022. ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 3715–3734. [28] Jan Luca Scheerer, Matei Zaharia, Christopher Potts, Gustavo Alonso, and Omar Khattab. 2025. WARP: An efficient engine for multi-vector retrieval. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2504–2512. [29] Susav Shrestha, Narasimha Reddy, and Zongwang Li. 2024. Espn: Memoryefficient multi-vector information retrieval. In Proceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management. 95–107. [30] Sivic and Zisserman. 2003. Video Google: A text retrieval approach to object matching in videos. In Proceedings ninth IEEE international conference on computer vision. IEEE, 1470–1477. [31] Stanford Future Data. 2020. ColBERT: Official GitHub Repository. https://github. com/stanford-futuredata/ColBERT. Accessed: 2026-03-01. [32] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 international conference on management of data. 2614–2627. [33] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. PVLDB 14, 11 (2021), 1964–1978. [34] Runhui Wang and Dong Deng. 2020. DeltaPQ: lossless product quantization code compression for high dimensional similarity search. PVLDB 13, 13 (2020), 3603–3616. [35] Binhan Yang, Yuxiang Zeng, Hengxin Zhang, Zhuanglin Zheng, Yunzhen Chi, Yongxin Tong, and Ke Xu. 2026. Unified and Efficient Approach for Multi-Vector Similarity Search (Full Paper). https://github.com/oldherd/MV-HNSW. [36] Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in HighDimensional Spaces. PVLDB 16, 8 (2023), 1979–1991.