MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding

Authors: laxman  dhulipala
majid  hadian
google  deepmind
rajesh  jayaram
jason  lee
google  research
vahab  mirrokni
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 20:46:38

Abstract: Neural embedding models have become a fundamental component of modern information retrieval (IR) pipelines. These models produce a single embedding $x \in \mathbb{R}^d$ per data-point, allowing for fast retrieval via highly optimized maximum inner product search (MIPS) algorithms. Recently, beginning with the landmark ColBERT paper, multi-vector models, which produce a set of embedding per data point, have achieved markedly superior performance for IR tasks. Unfortunately, using these models for IR is computationally expensive due to the increased complexity of multi-vector retrieval and scoring. 

In this paper, we introduce MUVERA (MUlti-VEctor Retrieval Algorithm), a retrieval mechanism which reduces multi-vector similarity search to single-vector similarity search. This enables the usage of off-the-shelf MIPS solvers for multi-vector retrieval. 
MUVERA asymmetrically generates Fixed Dimensional Encodings (FDEs) of queries and documents, which are vectors whose inner product approximates multi-vector similarity. We prove that FDEs give high-quality $\epsilon$-approximations, thus providing the first single-vector proxy for multi-vector similarity with theoretical guarantees. Empirically, we find that FDEs achieve the same recall as prior state-of-the-art heuristics while retrieving 2-5$\times$ fewer candidates. Compared to prior state of the art implementations, MUVERA achieves consistently good end-to-end recall and latency across a diverse set of the BEIR retrieval datasets, achieving an average of 10% improved recall with 90% lower latency.

Main paper: 
 introduction: 
 Over the past decade, the use of neural embeddings for representing data has become a central tool for information retrieval (IR) [56] , among many other tasks such as clustering and classification [39] . Recently, multi-vector (MV) representations, introduced by the late-interaction framework in ColBERT [29] , have been shown to deliver significantly improved performance on popular IR benchmarks. ColBERT and its variants [17, 21, 32, 35, 42, 44, 49, 54] produce multiple embeddings per query or document by generating one embedding per token. The query-document similarity is then scored via the Chamfer Similarity ( §1.1), also known as the MaxSim operation, between the two sets of vectors. These multi-vector representations have many advantages over single-vector (SV) representations, such as better interpretability [15, 50] and generalization [16, 36, 51, 55] . Despite these advantages, multi-vector retrieval is inherently more expensive than single-vector retrieval. Firstly, producing one embedding per token increases the number of embeddings in a dataset by orders of magnitude. Moreover, due to the non-linear Chamfer similarity scoring, there is a lack of optimized systems for multi-vector retrieval. Specifically, single-vector retrieval is Figure 1 : MUVERA's two-step retrieval process, compared to PLAID's multi-stage retrieval process. Diagram on the right from Santhanam et. al. [43] with permission.generally accomplished via Maximum Inner Product Search (MIPS) algorithms, which have been highly-optimized over the past few decades [18] . However, SV MIPS alone cannot be used for MV retrieval. This is because the MV similarity is the sum of the SV similarities of each embedding in a query to the nearest embedding in a document. Thus, a document containing a token with high similarity to a single query token may not be very similar to the query overall. Thus, in an effort to close the gap between SV and MV retrieval, there has been considerable work in recent years to design custom MV retrieval algorithms with improved efficiency [12, 21, 42, 43] .The most prominent approach to MV retrieval is to employ a multi-stage pipeline beginning with single-vector MIPS. The basic version of this approach is as follows: in the initial stage, the most similar document tokens are found for each of the query tokens using SV MIPS. Then the corresponding documents containing these tokens are gathered together and rescored with the original Chamfer similarity. We refer to this method as the single-vector heuristic. ColBERTv2 [44] and its optimized retrieval engine PLAID [43] are based on this approach, with the addition of several intermediate stages of pruning. In particular, PLAID employs a complex four-stage retrieval and pruning process to gradually reduce the number of final candidates to be scored (Figure 1 ). Unfortunately, as described above, employing SV MIPS on individual query embeddings can fail to find the true MV nearest neighbors. Additionally, this process is expensive, since it requires querying a significantly larger MIPS index for every query embedding (larger because there are multiple embeddings per document). Finally, these multi-stage pipelines are complex and highly sensitive to parameter setting, as recently demonstrated in a reproducibility study [37] , making them difficult to tune. To address these challenges and bridge the gap between single and multi-vector retrieval, in this paper we seek to design faster and simplified MV retrieval algorithms.Contributions. We propose MUVERA: a multi-vector retrieval mechanism based on a light-weight and provably correct reduction to single-vector MIPS. MUVERA employs a fast, data-oblivious transformation from a set of vectors to a single vector, allowing for retrieval via highly-optimized MIPS solvers before a single stage of re-ranking. Specifically, MUVERA transforms query and document MV sets Q, P ⊂ R d into single fixed-dimensional vectors q, p, called Fixed Dimensional Encodings (FDEs), such that the the dot product q • p approximates the multi-vector similarity between Q, P ( §2). Empirically, we show that retrieving with respect to the FDE dot product significantly outperforms the single vector heuristic at recovering the Chamfer nearest neighbors ( §3.1). For instance, on MS MARCO, our FDEs Recall@N surpasses the Recall@2-5N achieved by the SV heuristic while scanning a similar total number of floats in the search.We prove in ( §2.1) that our FDEs have strong approximation guarantees; specifically, the FDE dot product gives an ε-approximation to the true MV similarity. This gives the first algorithm with provable guarantees for Chamfer similarity search with strictly faster than brute-force runtime (Theorem 2.2). Thus, MUVERA provides the first principled method for MV retrieval via a SV proxy.We compare the end-to-end retrieval performance of MUVERA to PLAID on several of the BEIR IR datasets, including the well-studied MS MARCO dataset. We find MUVERA to be a robust and efficient retrieval mechanism; across the datasets we evaluated, MUVERA obtains an average of 10% higher recall, while requiring 90% lower latency on average compared with PLAID. Additionally, MUVERA crucially incorporates a vector compression technique called product quantization that enables us to compress the FDEs by 32× (i.e., storing 10240 dimensional FDEs using 1280 bytes) while incurring negligible quality loss, resulting in a significantly smaller memory footprint.Given two sets of vectors Q, P ⊂ R d , the Chamfer Similarity is given by CHAMFER(Q, P ) = q∈Q max p∈P q, p where •, • is the standard vector inner product. Chamfer similarity is the default method of MV similarity used in the late-interaction architecture of ColBERT, which includes systems like ColBERTv2 [44] , Baleen [28] , Hindsight [41] , DrDecr [34] , and XTR [32] , among many others. These models encode queries and documents as sets Q, P ⊂ R d (respectively), where the query-document similarity is given by CHAMFER(Q, P ). We note that Chamfer Similarity (and its distance variant) itself has a long history of study in the computer vision (e.g., [4, 6, 14, 27, 45] ) and graphics [33] communities, and had been previously used in the ML literature to compare sets of embeddings [3, 5, 30, 48] . In these works, Chamfer is also referred to as MaxSim or the relaxed earth mover distance; we choose the terminology Chamfer due to its historical precedence [6] .In this paper, we study the problem of Nearest Neighbor Search (NNS) with respect to the Chamfer Similarity. Specifically, we are given a dataset D = {P 1 , . . . , P n } where each P i ⊂ R d is a set of vectors. Given a query subset Q ⊂ R d , the goal is to quickly recover the nearest neighbor P * ∈ D, namely:P * = arg max Pi∈D CHAMFER(Q, P i )For the retrieval system to be scalable, this must be achieved in time significantly faster than bruteforce scoring each of the n similarities CHAMFER(Q, P i ) within D.1.2 Our Approach: Reducing Multi-Vector Search to Single-Vector MIPS MUVERA is a streamlined procedure that directly reduces the Chamfer Similarity Search to MIPS. For a pre-specified target dimension d FDE , MUVERA produces randomized mappings F q : 2 R d → R dFDE (for queries) and F doc : 2 R d → R dFDE (for documents) such that, for all query and document multi-vector representations Q, P ⊂ R d , we have:F q (Q), F doc (P ) ≈ CHAMFER(Q, P )We refer to the vectors F q (Q), F doc (P ) as Fixed Dimensional Encodings (FDEs). MUVERA first applies F doc to each document representation P ∈ D, and indexes the set {F doc (P )} P ∈D into a MIPS solver. Given a query Q ⊂ R d , MUVERA quickly computes F q (Q) and feeds it to the MIPS solver to recover the top-k most similar document FDE's F doc (P ). Finally, we re-rank these candidates by the original Chamfer similarity. See Figure 1 for an overview. We remark that one important advantage of the FDEs is that the functions F q , F doc are data-oblivious, making them robust to distribution shifts, and easily usable in streaming settings.The early multi-vector retrieval systems, such as ColBERT [29] , all implement optimizations of the previously described SV heuristic, where the initial set of candidates is found by querying a MIPS index for every query token q ∈ Q. In ColBERTv2 [44] , the document token embeddings are first clustered via k-means, and the first round of scoring uses cluster centroids instead of the original token. This technique was further optimized in PLAID [43] by employing a four-stage pipeline to progressively prune candidates before a final re-ranking (Figure 1 ).An alternative approach with proposed in DESSERT [12] , whose authors also pointed out the limitations of the SV heuristic, and proposed an algorithm based on Locality Sensitive Hashing (LSH) [20] . They prove that their algorithm recovers ε-approximate nearest neighbors in time Õ(n|Q|T ), where T is roughly the maximum number of document tokens p ∈ P i that are similar to any query token q ∈ Q, which can be as large as max i |P i |. Thus, in the worst case, their algorithm runs no faster than brute-force. Conversely, our algorithm recovers ε-approximate nearest neighbors and always runs in time Õ(n|Q|). Experimentally, DESSERT is 2-5× faster than PLAID, but attains worse recall (e.g. 2-2.5% R@1000 on MS MARCO). Conversely, we match and sometimes strongly exceed PLAID's recall with up to 5.7× lower latency. Additionally, DESSERT still employs an initial filtering stage based on k-means clustering of individual query token embeddings (in the manner of ColBERTv2), thus they do not truly avoid the aforementioned limitations of the SV heuristic.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: All claims made in the abstract and introduction are thoroughly discussed and evaluated in the remaining sections of the paper. The theoretical claims are justified in Section 2.1, and the experimental claims are justified in Section 3.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
fixed dimensional encodings: 
 We now describe our process for generating FDEs. Our transformation is reminiscent of the technique of probabilistic tree embeddings [1, 7, 10, 13] , which can be used to transform a set of vectors into a single vector. For instance, they have been used to embed the Earth Mover's Distance into the 1 metric [1, 10, 22, 24] , and to embed the weight of a Euclidean MST of a set of vectors into the Hamming metric [9, 22, 23] . However, since we are working with inner products, which are not metrics, instead of p distances, an alternative approach for our transformation will be needed.The intuition behind our transformation is as follows. Hypothetically, for two MV representationsQ, P ⊂ R d , ifwe knew the optimal mapping π : Q → P in which to match them, then we could create vectors q, p by concatenating all the vectors in Q and their corresponding images in P together, so that q, p = q∈Q q, π(q) = CHAMFER(Q, P ). However, since we do not know π in advance, and since different query-document pairs have different optimal mappings, this simple concatenation clearly will not work. Instead, our goal is to find a randomized ordering over all the points in R d so that, after clustering close points together, the dot product of any query-document pair Q, P ⊂ R d concatenated into a single vector under this ordering will approximate the Chamfer similarity.The first step is to partition the latent space R d into B clusters so that vectors that are closer are more likely to land in the same cluster. Let ϕ : R d → [B] be such a partition (for an integer N 1 we use the notation [N ] = {1, 2, . . . , N }); ϕ can be implemented via Locality Sensitive Hashing (LSH) [20] , k-means, or other methods; we discuss choices for ϕ later in this section. After partitioning via ϕ, the hope is that for each q ∈ Q, the closest p ∈ P lands in the same cluster (i.e. ϕ(q) = ϕ(p)).Hypothetically, if this were to occur, then:EQUATIONIf p is the only point in P that collides with q, then (1) can be realized as a dot product between two vectors q, p by creating one block of d coordinates in q, p for each cluster k ∈ [B] (call these blocks q (k) , p (k) ∈ R d ), and setting q (k) , p (k) to be the sum of all q ∈ Q (resp. p ∈ P ) that land in the k-th cluster under ϕ. However, if multiple p ∈ P collide with q, then q, p will differ from (1), since every p with ϕ(p ) = ϕ(q) will contribute at least q, p to q, p . To resolve this, we set p (k) to be the centroid of the p ∈ P 's with ϕ(p) = ϕ(q). Formally, for k = 1, . . . , B, we defineEQUATIONSetting q = ( q (1) , . . . , q (B) ) and p = ( p (1) , . . . , p (B) ), then we haveEQUATIONNote that the resulting dimension of the vectors q, p is dB. To reduce the dependency on d, we can apply a random linear projection ψ : R d → R dproj to each block q (k) , p (k) , where d proj < d. Specifically, we define ψ(x) = (1/ d proj )Sx, where S ∈ R dproj×d is a random matrix with uniformly distributed ±1 entries. We can then define q (k),ψ = ψ( q (k) ) and p (k),ψ = ψ( p (k) ), and define the FDE's with inner projection as q ψ = ( q (1),ψ , . . . , q (B),ψ ) and p ψ = ( p (1),ψ , . . . , p (B),ψ ). When d = d proj , we simply define ψ to be the identity mapping, in which case q ψ , p ψ are identical to q, p. To increase accuracy of (3) in approximating (1), we repeat the above process R reps 1 times independently, using different randomized partitions ϕ 1 , . . . , ϕ Rreps and projections ψ 1 , . . . , ψ Rreps . We denote the vectors resulting from i-th repetition by q i,ψ , p i,ψ . Finally, we concatenate these R reps vectors together, so that our final FDEs are defined as F q (Q) = ( q 1,ψ , . . . , q Rreps,ψ ) and F doc (P ) = ( p 1,ψ , . . . , p Rreps,ψ ). Observe that a complete FDE mapping is specified by the three parameters (B, d proj , R reps ), resulting in a final dimension ofd FDE = B • d proj • R reps .Choice of Space Partition. When choosing the partition function ϕ, the desired property is that points are more likely to collide (i.e. ϕ(x) = ϕ(y)) the closer they are to each other. Such functions with this property exist, and are known as locality-sensitive hash functions (LSH) (see [20] ). When the vectors are normalized, as they are for those produced by ColBERT-style models, SimHash [8] is the standard choice of LSH. Specifically, for any k sim 1, we sample random Gaussian vectors g 1 , . . . , g ksim ∈ R d , and set ϕ(x) = (1( g 1 , x > 0), . . . , 1( g ksim , x > 0)), where 1(•) ∈ {0, 1} is the indicator function. Converting the bit-string to decimal, ϕ(x) gives a mapping from R d to [B] where B = 2 ksim . In other words, SimHash partitions R d by drawing k sim random half-spaces, and each of the 2 ksim clusters is formed by the k sim -wise intersection of each of these halfspaces or their complement. Another natural approach is to choose k CENTER 1 centers from the collection of all token embeddings ∪ n i=1 P i , either randomly or via k-means, and set ϕ(x) ∈ [k CENTER ] to be the index of the center nearest to x. We compare this method to SimHash in ( §3.1).A key source of error in the FDE's approximation is when the nearest vector p ∈ P to a given query embedding q ∈ Q maps to a different cluster, namely ϕ(p) = ϕ(q) = k. This can be made less likely by decreasing B, at the cost of making it more likely for other p ∈ P to also map to the same cluster, moving the centroid p (k) farther from p. If we increase B too much, it is possible that no p ∈ P collides with ϕ(q). To avoid this trade-off, we directly ensure that if no p ∈ P maps to a cluster k, then instead of setting p (k) = 0 we set p (k) to the point p that is closest to cluster k. As a result, increasing B will result in a more accurate estimator, as this results in smaller clusters. Formally, for any cluster k with P ∩ ϕ -1 (k) = ∅, if fill_empty_clusters is enabled, we set p (k) = p where p ∈ P is the point for which ϕ(p) has the fewest number of disagreeing bits with k (both thought of as binary strings), with ties broken arbitrarily. We do not enable this for query FDEs, as doing so would result in a given q ∈ Q contributing to the dot product multiple times.Final Projections. A natural approach to reducing the dimensionality is to apply a final projection ψ : R dFDE → R dfinal (also implemented via multiplication by a random ±1 matrix) to the FDE's, reducing the final dimensionality to any d final < d FDE . Experimentally, we find that final projections can provide small but non-trivial 1-2% recall boosts for a fixed dimension (see §C.2).We now state our theoretical guarantees for our FDE construction. For clarity, we state our results in terms of normalized Chamfer similarity NCHAMFER(Q, P ) = 1 |Q| CHAMFER(Q, P ). This ensures NCHAMFER(Q, P ) ∈ [-1, 1] whenever the vectors in Q, P are normalized. Note that this factor of 1/|Q| does not affect the relative scoring of documents for a fixed query. In what follows, we assume that all token embeddings are normalized (i.e. q 2 = p 2 = 1 for all q ∈ Q, p ∈ P ). Note that ColBERT-style late interaction MV models indeed produce normalized token embeddings. We will always use the fill_empty_clusters method for document FDEs, but never for queries.Our main result is that FDEs give ε-additive approximations of the Chamfer similarity. The proof uses the properties of LSH (SimHash) to show that for each query point q ∈ Q, the point q gets mapped to a cluster ϕ(q) that only contains points p ∈ P that are close to q (within ε of the closest point to q); the fact that at least one point collides with q uses the fill_empty_partitions method.Theorem 2.1 (FDE Approximation). Fix any ε, δ > 0, and sets Q, P ⊂ R d of unit vectors, and letm = |Q| + |P |. Then setting k sim = O log(mδ -1 ) ε , d proj = O 1 ε 2 log( m εδ ) , R reps = 1, so that d FDE = (m/δ) O(1/ε), then in expectation and with probability at least 1 -δ we have NCHAMFER(Q, P ) -ε 1 |Q| F q (Q),P i ⊂ R d is a set of unit vectors. Let m = |Q| + max i∈[n] |P i |. Let k sim = O( log m ε ), d proj = O( 1 ε 2 log(m/ε)) and R reps = O( 1 ε 2 log n) so that d FDE = m O(1/ε) • log n. Then if i * = arg max i∈[n] F q (Q), F doc (P i ) , with high probability (i.e. 1 -1/ poly(n)) we have:NCHAMFER(Q, P i * ) max i∈[n] NCHAMFER(Q, P i ) -εGiven the query Q, the document P * can be recovered in time O |Q| max{d, n} 1 ε 4 log( m ε ) log n .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: A limitations section is provided at the end of the paper in Section 4, along with the broader impacts. We discuss there the primary limitations of the paper. The computational efficiency of the algorithms are discussed in the latency experiments Section 3.2 of the paper, as well as how the MIPS index scales with dataset size.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
evaluation: 
 In this section, we evaluate our FDEs as a method for MV retrieval. First, we evaluate the FDEs themselves (offline) as a proxy for Chamfer similarity ( §3.1). In ( §3.2), we discuss the implementation of MUVERA, as well as several optimizations made in the search. Then we evaluate the latency of MUVERA compared to PLAID, and study the effects of the aforementioned optimizations.Datasets. Our evaluation includes results from six of the well-studied BEIR [46] information retrieval datasets: MS MARCO [40] (CC BY-SA 4.0), HotpotQA (CC BY-SA 4.0) [53] , NQ (Apache-2.0) [31] , Quora (Apache-2.0) [46] , SciDocs (CC BY 4.0) [11] , and ArguAna (Apache-2.0) [47] . These datasets were selected for varying corpus size (8K-8.8M) and average number of document tokens (18-165); see ( §B) for further dataset statistics. Following [43] , we use the development set for our experiments on MS MARCO, and use the test set on the other datasets.MV Model, MV Embedding Sizes, and FDE Dimensionality. We compute our FDEs on the MV embeddings produced by the ColBERTv2 model [44] (MIT License), which have a dimension of d = 128 and a fixed number |Q| = 32 of embeddings per query. The number of document embeddings is variable, ranging from an average of 18.3 on Quora to 165 on Scidocs. This results in 2,300-21,000 floats per document on average (e.g. 10,087 for MS MARCO). Thus, when constructing our FDEs we consider a comparable range of dimensions d FDE between 1,000-20,000. Furthermore, using product quantization, we show in ( §3.2) that the FDEs can be significantly compressed by 32× with minimal quality loss, further increasing the practicality of FDEs.We evaluate the quality of our FDEs as a proxy for the Chamfer similarity, without any re-ranking and using exact (offline) search. We first demonstrate that FDE recall quality improves dependably as the dimension d FDE increases, making our method relatively easy to tune. We then show that FDEs are a more effective method of retrieval than the SV heuristic. Specifically, the FDE method achieves Recall@N exceeding the Recall@2-4N of the SV heuristic, while in principle scanning a similar number of floats in the search. This suggests that the success of the SV heuristic is largely due to the significant effort put towards optimizing it (as supported by [37] ), and similar effort for FDEs may result in even bigger efficiency gains. Additional plots can be found in ( §C). All recall curves use a single FDE instantiation, since in ( §C.1) we show the variance of FDE recall is negligible.FDE Quality vs. Dimensionality. We study how the retrieval quality of FDE's improves as a function of the dimension d FDE . We perform a grid search over FDE parameters R reps ∈ {1, 5, 10, 15, 20}, k sim ∈ {2, 3, 4, 5, 6}, d proj ∈ {8, 16, 32, 64}, and compute recall on MS MARCO (Figure 3 ). We find that Pareto optimal parameters are generally achieved by larger R reps , with k sim , d proj playing a lesser role in improving quality. Specifically, (R reps , k sim , d proj ) ∈ { (20, 3, 8) , (20, 4, 8) (20, 5, 8) , (20, 5, 16 )} were all Pareto optimal for their respective dimensions (namely R reps • 2 ksim • d proj ). While there are small variations depending on the parameter choice, the FDE quality is tightly linked to dimensionality; increase in dimensionality will generally result in quality gains. We also evaluate using k-means as a method of partitioning instead of SimHash. Specifically, we cluster the document embeddings with k-means and set ϕ(x) to be the index of the nearest centroid to x. We perform a grid search over the same parameters (but with k ∈ {4, 8, 16, 32, 64} to match B = 2 ksim ). We find that k-means partitioning offers no quality gains on the Pareto Frontier over SimHash, and is often worse. Moreover, FDE construction with k-means is no longer data oblivious. Thus, SimHash is chosen as the preferred method for partitioning for the remainder of our experiments.In Figure 4 , we evaluate the FDE retrieval quality with respect to the Chamfer similarity (instead of labelled ground truth data). We compute 1Recall@N , which is the fraction of queries for which the Chamfer 1-nearest neighbor is among the top-N most similar in FDE dot product. We choose FDE parameters which are Pareto optimal for the dimension from the above grid search. We find that FDE's with fewer dimensions that the original MV representations achieve significantly good recall across multiple BEIR retrieval datasets. For instance, on MS MARCO (where d • m avg ≈ 10K) we achieve 95% recall while retrieving only 75 candidates using d FDE = 5120.Single Vector Heuristic vs. FDE retrieval. We compare the quality of FDEs as a proxy for retrieval against the previously described SV heuristic, which is the method underpinning PLAID. Recall that in this method, for each of the i = 1, . . . , 32 query vectors q i we compute the k nearest neighbors p 1,i , . . . , p k,i from the set ∪ i P i of all document token embeddings. To compute Recall@N , we create an ordered list 1,1 , . . . , 1,32 , 2,1 , . . . , where i,j is the document ID containing p i,j , consisting of the 1-nearest neighbors of the queries, then the 2-nearest neighbors, and so on. When reranking, one first removes duplicate document IDs from this list. Since duplicates cannot be detected while performing the initial 32 SV MIPS queries, the SV heuristic needs to over-retrieve to reach a desired number of unique candidates. Thus, we note that the true recall curve of implementations of the SV heuristic (e.g. PLAID) is somewhere between the case of no deduplication and full deduplication; we compare to both in Figure 5 .To compare the cost of the SV heuristic to running MIPS over the FDEs, we consider the total number of floats scanned by both using a brute force search. over n vectors can be accomplished in sublinear n ε time, for some ε ∈ (0, 1). Then even in the unrealistic case of ε = 0, we can still afford an FDE dimension of d FDE = 32 • 128 = 4096.The results can be found in Figure 5 . We build FDEs once for each dimension, using R reps = 40, k sim = 6, d proj = d = 128, and then applying a final projection to reduce to the target dimension (see C.2 for experiments on the impact of final projections). On MS MARCO, even the 4096dimensional FDEs match the recall of the (deduplicated) SV heuristic while retrieving 1.75-3.75× fewer candidates (our Recall@N matches the Recall@1.75-3.75N of the SV heuristic), and 10.5-15× fewer than to the non-deduplicated SV heuristic. For our 10240-dimension FDEs, these numbers are 2.6-5× and 20-22.5× fewer, respectively. For instance, we achieve 80% recall with 60 candidates when d FDE = 10240 and 80 candidates when d FDE = 4096, but the SV heuristic requires 300 and 1200 candidates (for dedup and non-dedup respectively). See Table 1 for further comparisons.Variance. Note that although the FDE generation is a randomized process, we show in ( §C.1) that the variance of the FDE Recall is essentially negligible; for instance, the standard deviation Recall@1000 is at most 0.08-0.16% for FDEs with 2-10k dimensions.We implemented MUVERA, an FDE generation and end-to-end retrieval engine in C++. We discussed FDE generation and various optimizations and their tradeoffs in ( §3.1). Next, we discuss how we perform retrieval over the FDEs, and additional optimizations.Single-Vector MIPS Retrieval using DiskANN. Our single-vector retrieval engine uses a scalable implementation [38] of DiskANN [25] (MIT License), a state-of-the-art graph-based ANNS algorithm. We build DiskANN indices by using the uncompressed document FDEs with a maximum degree of 200 and a build beam-width of 600. Our retrieval works by querying the DiskANN index using beam search with beam-width W , and subsequently reranking the retrieved candidates with Chamfer similarity. The only tuning knob in our system is W ; increasing W increases the number of candidates retrieved by MUVERA, which improves the recall.Product Quantization (PQ). To further improve the memory usage of MUVERA, we use a textbook vector compression technique called product quantization (PQ) with asymmetric querying [19, 26] on the FDEs. We refer to product quantization with C centers per group of G dimensions as PQ-C-G.For example, PQ-256-8, which we find to provide the best tradeoff between quality and compression in our experiments, compresses every consecutive set of 8 dimensions to one of 256 centers. Thus PQ-256-8 provides 32× compression over storing each dimension using a single float, since each block of 8 floats is represented by a single byte. See ( §C.4) for further experiments and details on PQ.Experimental Setup. We run our online experiments on an Intel Sapphire Rapids machine on Google Cloud (c3-standard-176). The machine supports up to 176 hyper-threads. We run latency experiments using a single thread, and run our QPS experiments on all 176 threads.Ball Carving. To improve re-ranking speed, we reduce the number of query embeddings by clustering them via a ball carving method and replacing the embeddings in each cluster with their sum. This speeds up reranking without decreasing recall. Specifically, we group the queries Q into clusters C 1 , . . . , C k , setting c i = q∈Ci q and Q C = {c 1 , . . . , c k }. Then, after retrieving a set of candidate documents with the FDEs, instead of rescoring via CHAMFER(Q, P ) for each candidate P , we rescore via CHAMFER(Q C , P ), which runs in time O(|Q C | • |P |), offering speed-ups when the number of clusters is small. Instead of fixing k, we perform greedy ball-carving to allow k to adapt to Q. Specifically, given a threshold τ , we select an arbitrary point q ∈ Q, cluster it with all other points q ∈ Q with q, q τ , remove the clustered points and repeat until all points are clustered. In Figure 6 , we show the the trade-off between end-to-end Recall@k of MUVERA and the ball carving threshold used. Notice that for both k = 100 and k = 1000, the recall curves flatten after a threshold of τ = 0.6, and for all datasets they are essentially flat after τ 0.7. Thus, for such thresholds we incur essentially no quality loss by performing ball carving. Based on these empirical results, we choose the value of τ = 0.7 in our end-to-end experiments.In ( §C.3), we show the impact on end-to-end QPS of ball carving on the MS MARCO dataset.For sequential re-ranking, we find that ball carving at a τ = 0.7 threshold provides a 25% QPS improvement, and when re-ranking is being done in parallel (over all cores simultaneously) it yields a 20% QPS improvement. Moreover, with a threshold of τ = 0.7, there were an average of 5.9 clusters created per query on MS MARCO. This reduces the number of query embeddings by 5.4×, down from the initial fixed setting of |Q| = 32. This finding shows that pre-clustering the queries before re-ranking gives non-trivial runtime improvements with negligible quality loss. It also suggests that a fixed setting of |Q| = 32 query embeddings used by existing approaches is likely excessive for MV similarity quality, and that fewer queries could achieve a similar performance.QPS vs. Recall. A useful metric for retrieval is the number of queries per second (QPS) a system can serve at a given recall; evaluating the QPS of a system tries to fully utilize the system resources (e.g., the bandwidth of multiple memory channels and caches), and deployments where machines serve many queries simultaneously. Figure 7 shows the QPS vs. Recall@100 for MUVERA on a subset of the BEIR datasets, using different PQ schemes over the FDEs. We show results for additional datasets, as well as Recall@1000, in the Appendix. Using PQ-256-8 not only reduces the space usage of the FDEs by 32×, but also improves the QPS at the same query beamwidth by up to 20×, while incurring a minimal loss in end-to-end recall. Our method has a relatively small dependence on the dataset size, which is consistent with prior studies on graph-based ANNS data structures, since the number of distance comparisons made during beam search grows roughly logarithmically with increasing dataset size [25, 38] . We tried to include QPS numbers for PLAID [43] , but unfortunately their implementation does not support running multiple queries in parallel, and is optimized for measuring latency.Latency and Recall Results vs. PLAID [43] We evaluated MUVERA and PLAID [43] on the 6 datasets from the BEIR benchmark described earlier in ( §3); Figure 8 shows that MUVERA achieves essentially equivalent Recall@k as PLAID (within 0.4%) on MS MARCO, while obtaining up to 1.56× higher recall on other datasets (e.g. HotpotQA). We ran PLAID using the recommended settings for their system, which reproduced their recall results for MS MARCO. Compared with PLAID, on The value on top of each bar is the latency in seconds (lower is better). The value on top of each bar is the Recall@k (higher is better).N Q -1 0 0 N Q -1 0 0 0 H o t p o t Q A -1 0 0 H o t p o t Q A -1 0 0 0 M S M A R C O -1 0 0 M S M A R C O -1 0 0 0 Q u o ra -1 0 0 Q u o ra -1 0 0 0 S C ID O C S -1 0 0 S C ID O C S -1 0 0 0 A rg u A n a -1 0 0 A rg u A n a -Muvera PLAID N Q -1 0 0 N Q -1 0 0 0 H o t p o t Q A -1 0 0 H o t p o t Q A -1 0 0 0 M S M A R C O -1 0 0 M S M A R C O -1 0 0 0 Q u o ra -1 0 0 Q u o ra -1 0 0 0 S C ID O C S -1 0 0 S C ID O C S -1 0 0 0 A rg u A n a -1 0 0 A rg u A n a -1 0 0 0 0.0 0.Muvera PLAID The x-tick labels are formatted as dataset-k, i.e., optimizing for Recall@k on the given dataset.average over all 6 datasets and k ∈ {100, 1000}, MUVERA achieves 10% higher Recall@k (up to 56% higher), and 90% lower latency (up to 5.7× lower).Importantly, MUVERA has consistently high recall and low latency across all of the datasets that we measure, and our method does not require costly parameter tuning to achieve this-all of our results use the same 10240-dimensional FDEs that are compressed using PQ with PQ-256-8; the only tuning in our system was to pick the first query beam-width over the k that we rerank to that obtained recall matching that of PLAID. As Figure 8 shows, in cases like NQ and HotpotQA, MUVERA obtains much higher recall while obtaining lower latency. Given these results, we believe a distinguishing feature of MUVERA compared to prior multi-vector retrieval systems is that it achieves consistently high recall and low latency across a wide variety of datasets with minimal tuning effort.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: All theoretical results are formally stated in the main paper, along with all relevant assumptions in Section 2.1. All definitions are formally given in the main paper, with full proofs deferred to the appendix in Section A, with ideas of the proof given in the main paper in Section 2.1.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.• Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.• Theorems and Lemmas that the proof relies upon should be properly referenced. 
conclusion: 
 In this paper, we presented MUVERA: a principled and practical MV retrieval algorithm which reduces MV similarity to SV similarity by constructing Fixed Dimensional Encoding (FDEs) of a MV representation. We prove that FDE dot products give high-quality approximations to Chamfer similarity ( §2.1). Experimentally, we show that FDEs are a much more effective proxy for MV similarity, since they require retrieving 2-4× fewer candidates to achieve the same recall as the SV Heuristic ( §3.1). We complement these results with an end-to-end evaluation of MUVERA, showing that it achieves an average of 10% improved recall with 90% lower latency compared with PLAID. Moreover, despite the extensive optimizations made by PLAID to the SV Heuristic, we still achieve significantly better latency on 5 out of 6 BEIR datasets we consider ( §3). Given their retrieval efficiency compared to the SV heuristic, we believe that there are still significant gains to be obtained by optimizing the FDE method, and leave further exploration of this to future work.Broader Impacts and Limitations: While retrieval is an important component of LLMs, which themselves have broader societal impacts, these impacts are unlikely to result from our retrieval algorithm. Our contribution simply improves the efficiency of retrieval, without enabling any fundamentally new capabilities. As for limitations, while we outperformed PLAID, sometimes significantly, on 5 out of the 6 datasets we studied, we did not outperform PLAID on MS MARCO, possibly due to their system having been carefully tuned for MS MARCO given its prevalence. Additionally, we did not study the effect that the average number of embeddings m avg per document has on retrieval quality of FDEs; this is an interesting direction for future work.A Missing Proofs from Section 2.1In this section, we provide the missing proofs in Section 2.1. For convenience, we also reproduce theorem statements as they appear in the main text before the proofs. We begin by analyzing the runtime to compute query and document FDEs, as well as the sparsity of the queries.Lemma A.1. For any FDE parameters k sim , d proj , R reps and sets Q, P ⊂ R d , we can computeEQUATIONF q (P ) in time O(T q + R reps |P |2 ksim k sim ).Moreover, F q (Q) has at most O(|Q|d proj R reps ) non-zero entries.Proof. We first consider the queries. To generate the queries, we must first project each of the |Q| queries via the inner random linear productions ψ i : R d → R dproj , which requires O(|Q|dd proj R reps )time to perform the matrix-query products for all repetitions. Next, we must compute ϕ i (q) for each q ∈ Q and repetition i ∈ [R reps ], Each such value can be compute in d • k sim time to multiply the q ∈ R d by the k sim Gaussian vectors. Thus the total running time for this step is O(R reps |Q|dk sim ).Finally, summing the relevant values into the FDE once ϕ i (q), ψ i (q) are computed can be done in O(|Q|d proj ) time. For sparsity, note that only the coordinate blocks in the FDE corresponding to clusters k in a repetition i with at least one q ∈ |Q| with ϕ i (q) = k are non-zero, and there can be at most O(R reps |Q|) of these blocks, each of which has O(d proj ) coordinates.The document runtime is similar, except with the additional complexity required to carry out the fill_empty_clusters option. For each repetition, the runtime required to find the closest p ∈ P to a give cluster k is O(|P | • k sim ), since we need to run over all |p| values of ϕ(p) and check how many bits disagree with k. Thus, the total runtime isO(R reps |P |Bk sim ) = O(R reps |P |2 ksim k sim ).In what follows, we will need the following standard fact that random projections approximately preserve dot products. The proof is relatively standard, and can be found in [2] , or see results on approximate matrix product [52] for more general bounds. To anaylze the approximations of our FDEs, we begin by proving an upper bound on the value of the FDE dot product. In fact, we prove a stronger result: we show that our FDEs have the desirable property of being one-sided estimators -namely, they never overestimate the true Chamfer similarity. This is summarized in the following Lemma. Then if d = d proj , we always have1 |Q| F q (Q), F doc (P ) NCHAMFER(Q, P )Furthermore, for any δ > 0, if we set d proj = O( 1 ε 2 log(m/δ)), then we have1 |Q| F q (Q), F doc (P )NCHAMFER(Q, P ) + ε in expectation and with probability at least 1 -δ.Proof. First claim simply follows from fact that the average of a subset of a set of numbers can't be bigger than the maximum number in that set. More formally, we have:EQUATIONWhich completes the first part of the lemma. For the second part, to analyze the case of d proj < d, when inner random projections are used, by applying Fact A.2, firstly we have E [ ψ(p), ψ(q)] = q, p for any q ∈ Q, p ∈ P,, and secondly, after a union bound we over |P | • |Q| m 2 pairs, we have q, p = ψ(p), ψ(q) ± ε simultaneously for all q ∈ Q, p ∈ P, with probability 1 -δ, for any constant C > 1. The second part of the Lemma then follows similarly as above.We are now ready to give the proof of our main FDE approximation theorem.Theorem 2.1 (FDE Approximation). Fix any ε, δ > 0, and sets Q, P ⊂ R d of unit vectors, and letm = |Q| + |P |. Then setting k sim = O log(mδ -1 ) ε , d proj = O 1 ε 2 log( m εδ ) , R reps = 1, so that d FDE = (m/δ) O(1/ε) , we have NCHAMFER(Q, P ) -ε 1 |Q| F q (Q), F doc (P ) NCHAMFER(Q, P ) + εin expectation, and with probability at least 1 -δ.Proof of Theorem 2.1. The upper bound follows from Lemma A.3, so it will suffice to prove the lower bound. We first prove the result in the case when there are no random projections ψ, and remove this assumption at the end of the proof. Note that, by construction, F q is a linear mapping so that F q (Q) = q∈Q F(q), thusF q (Q), F doc (P ) = q∈Q F q (q), F doc (P )So it will suffice to prove that Pr F q (q), F doc (P ) maxEQUATIONfor all q ∈ Q, since then, by a union bound 5 will hold for all over all q ∈ Q with probability at least 1 -εδ, in which case we will haveEQUATIONwhich will complete the theorem.In what follows, for any x, y ∈ R d let θ(x, y) ∈ [0, π] be the angle between x, y. Now fix any q ∈ Q, and let p * = arg max p∈P q, p , and let θ * = θ(q, p * ). By construction, there always exists some set of points S ⊂ P such that F q (q), F doc (P ) = q, 1 |S| p∈S p the RHS of the above equation is always bounded by 1 in magnitude, since it is an average of dot products of normalized vectors q, p ∈ S d-1 . In particular, there are two cases. In case (A) S is the set of points p with ϕ(p) = ϕ(q), and in case (B) S is the single point arg min p∈P ϕ(p) -ϕ(q) 0 , where x -y 0 denotes the hamming distance between any two bitstrings x, y ∈ {0, 1} ksim , and we are interpreting ϕ(p), ϕ(q) ∈ {0, 1} ksim as such bit-strings. Also let g 1 , . . . , g ksim ∈ R d be the random Gaussian vectors that were drawn to define the partition function ϕ. To analyze S, we first prove the following: Claim A.4. For any q ∈ Q and p ∈ P , we havePr ϕ(p) -ϕ(q) 0 -k sim • θ(q, p) π > √ εk sim εδ m 2Proof. Fix any such p, and for i ∈ [k sim ] let Z i be an indicator random variable that indicates the event that 1( g i , p > 0) = 1( g i , q > 0). First then note that ϕ(p) -ϕ(q) 0 = ksim i=1 Z i . Now by rotational invariance of Gaussians, for a Gaussian vector g ∈ R d we havePr [1( g, x > 0) = 1( g, y > 0)] = θ(x,y) π for any two vectors x, y ∈ R d . It follows that Z i is a Bernoulli random variable with E [Z i ] = θ(x,y) π .By a simple application of Hoeffding's inequality, we haveEQUATIONwhere we took k sim 1/2 • log( m 2 εδ )/ε, which completes the proof.We now condition on the event in Claim A. 4 Now first suppose that we are in case (B), and the set S of points which map to the cluster ϕ(q) is given by S = {p } where p = arg min p∈P ϕ(p) -ϕ(q) 0 . Firstly, if p = p * , then we are done as F q (q), F doc (P ) = q, p * , and 5 follows. Otherwise, by Claim A.4 we must have had |θ(q, p )-θ(q, p * )| π• √ ε. Using that the Taylor expansion of cosine is cos(x) = 1-x 2 /2+O(x 4 ), we have | cos(θ(q, p )) -cos(θ(q, p * ))| O(ε)Thus F q (q), F doc (P ) = q, p = cos(θ(q, p )) cos(θ(q, p * )) -O(ε) = max p∈P q, p -O(ε) (8)which proves the desired statement 5 after a constant factor rescaling of ε.Next, suppose we are in case (A) where S = {p ∈ P | ϕ(p) = ϕ(q)} is non-empty. In this case, S consists of the set of points p with ϕ(p) -ϕ(q) 0 = 0. From this, it follows again by Claim A.4 that θ(q, p) √ επ for p ∈ S. Thus, by the same reasoning as above, we haveEQUATIONwhich again proves the desired statement 5 in case (A), thereby completing the full proof in the case where there are no random projections.To analyze the expectation, note that using the fact that | F q (q), F doc (P ) | 1 deterministically, the small O(εδ) probability of failure (i.e. the event that E does not hold) above can introduce at most a O(εδ) ε additive error into the expectation, which is acceptable after a constant factor rescaling of ε.Finally, to incorporate projections, by standard consequences of the Johnson Lindenstrauss Lemma (Fact A.2) setting d proj = O( 1 ε 2 log m ε ) and projecting via a random Gaussian or ±1 matrix from ψ :R d → R dproj , for any set S ⊂ P we have that E ψ(q), ψ( 1|S| p∈S p) = q, 1|S| p∈S p , and moreover that q, 1 |S| p∈S p = ψ(q), ψ( 1 |S| p∈S p) q 2 1 |S| p∈S p 2 ± ε for all q ∈ Q, p ∈ P with probability at least 1 -εδ. Note that q 2 = 1, and by triangle inequality1 |S| p∈S p 2 1 |S|p∈S p 2 = 1. Thus, letting F q (Q), F doc (P ) be the FDE values without the inner projection ψ and F ψ q (Q), F ψ doc (P ) be the FDE values with the inner projection ψ, conditioned on the above it follows thatEQUATIONFinally, to analyze the expectation, note that since1 |Q| F q (Q), F doc (P ) 1 |Q| q∈Q | F q (q), F doc (P ) | 1as before conditioning on this small probability event changes the expectation of 5 by at most a ε additive factor, which completes the proof of the Theorem after a constant factor rescaling of ε.Equipped with Theorem 2.1, as well as the sparsity bounds from Lemma A.1, we are now prepared to prove our main theorem on approximate nearest neighbor search under the Chamfer Similarity.Theorem 2.2. Fix any ε > 0, query Q, and dataset P = {P 1 , . . . , P n }, where Q ⊂ R d and eachP i ⊂ R d is a set of unit vectors. Let m = |Q| + max i∈[n] |P i |. Then setting k sim = O( log m ε ), d proj = O( 1 ε 2 log(m/ε)) and R reps = O( 1 ε 2 log n) so that d FDE = m O(1/ε) • log n.Then setting i * = arg max i∈[n] F q (Q), F doc (P i ) , with high probability (i.e. 1 -1/ poly(n)) we have:NCHAMFER(Q, P i * ) max i∈[n] NCHAMFER(Q, P i ) -ε Given the query Q, the document P * can be recovered in time O |Q| max{d, n} 1 ε 4 log( m ε ) log n .of Theorem 2.2. First note, for a single repetition, for any subset P j ∈ D, by Theorem 2.1 we have E [ F q (Q), F doc (P j ) ] = NCHAMFER(Q, P ) ± ε Moreover, as demonsrated in the proof of Theorem 2.1, setting δ = 1/10, we have1 |Q| F q (Q), F doc (P j ) 1 |Q| q∈Q | F q (q), F doc (P j ) | 1It follows that for each repetition i ∈ [R reps ], letting F q (Q) i , F doc (P j ) i be the coordinates in the final FDE vectors corresponding to that repetition, the random variableEQUATIONwith probability 1 -1/n C for any arbitrarily large constant C > 1. Note also thatQuestion: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: The algorithm for generating FDEs is thoroughly and exactly described in Section 2, and is easy to reproduce from the description. As mentioned in Section 3.2, we will publish a standalone open-source shared-memory implementation of the FDE generation step upon publication. Further note that the DiskANN library used for retrieving via MIPS is publicly available, and we explicitly state the parameters we ran it with.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
open access to data and code: 
 Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [No] Justification: Our end-to-end retrieval engine is implemented in C++ in a proprietary codebase, preventing us from directly releasing it. As described in Section 3.2, we plan to publish a standalone open-source implementation of the FDE generation step upon publication, along with the product quantization code (which is a textbook method) and the ball-carving code. The only other component of the algorithm is DiskANN, which is publicly available and properly cited.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: No models were trained for this paper, however details about all datasets and how we evaluated our algorithms on them were precisely defined. All parameters used in our algorithms were explicitly stated for every experiment in their corresponding section.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We run detailed variance experiments in the supplementary in Appendix C.1, and describe the main conclusions of these results in Section 3.1, demonstrating that our FDE recall is extremely stable and varies very little depending on the random seed.Guidelines:• The answer NA means that the paper does not include experiments. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: For all our online (latency) experiments, we the exact hardware and compute resources we used in Section 3.2. The results of offline experiments (Section 3.1) do not depend on hardware implementation, as they are measuring fixed recall properties of an algorithm (without any runtime benchmarking), and therefore can be reproduced on any hardware and infastructure.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss the broader impacts in a standalone section at the end of the paper in Section 4. In essence, since our work is solely about improving the efficiency of multi-vector retrieval, it is unlikely to have any direct path to negative applications, and we discuss this fact in the Broader Impacts section.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper proposes a new algorithm that purely improves the efficiency of multi-vector retrieval; we do not release any data or new models. Therefore our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The authors and sources of all six BEIR datasets that were used in this paper are cited, as well as the ColBERTv2 model that was used to generate the multi-vector embeddings, and the DiskANN algorithm we used for single vector retrieval. For each of these aforementioned assets, the license of the asset was explicitly stated in the text: we stated the license for the BEIR datasets in Section 3, and the license for DiskANN in Section 3.2. The terms of use of all these licenses were properly respected in this paper.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: No new assets were introduced in this paper.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] .Justification: No crowdsourcing nor research with human subjects with used in this paper.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] .Justification: No crowdsourcing nor research with human subjects with used in this paper.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: 1EQUATIONRreps|Q| F q (Q), F doc (P j ) , where F q (Q), F doc (P j ) are the final FDEs. We can then condition on (11) holding for all documents j ∈ [n], which holds with probability with probability 1 -1/n C-1 by a union bound. Conditioned on this, we haveEQUATIONwhich completes the proof of the approximation after a constant factor scaling of ε. The runtime bound follows from the runtime required to computeF q (Q), which is O(|Q|R reps d(d proj + k sim )) = O(|Q| log n ε 2 d( 1 ε 2 log(m/ε) + 1 ε log m), plus the runtime required to brute force search for the nearest dot product. Specifically, note that each of the n FDE dot products can be computed in time proportional to the sparsity of F q (Q), which is at most O(|Q|d proj R reps ) = O(|Q| 1 ε 4 log(m/ε) log n). Adding these two bounds together yields the desired runtime.In Table 9 we provide further dataset-specific information on the BEIR retrieval datasets used in this paper. Specifically, we state the sizes of the query and corpuses used, as well as the average number of embeddings produced by the ColBERTv2 model per document. Specifically, we consider the six BEIR retrieval datasets MS MARCO [40] , NQ [31] , HotpotQA [53] , ArguAna [47] , SciDocs [11] , and Quora [46] , Note that the MV corpus (after generating MV embeddings on all documents in a corpus) will have a total of #Corpus × (Avg # Embeddings per Doc) token embeddings. For even further details, see the BEIR paper [46] . In Section, we provide additional plots to support the experimental results from Section 3. We provide plots for all six of the datasets and additional ranges of the x-axis for our experiments in Section ( §3.1), as well as additional experimental results, such as an evaluation of variance, and of the quality of final projections in the FDEs.FDE vs. SV Heuristic Experiments. In Figures 10 and 11 , we show further datasets and an expanded recall range for the comparison of the SV Heuristic to retrieval via FDEs. We find that our 4k+ dimensional FDE methods outperform even the deduplciated SV heuristic (whose cost is somewhat unrealistic, since the SV heuristic must over-retrieve to handle duplicates) on most datasets, especially in lower recall regimes. In Table 1 , we compare how many candidates must be retrieved by the SV heuristic, both with and without the deduplication step, as well as by our FDE methods, in order to exceed a given recall threshold. Recall@N values were computed in increments of 10 between 10-100, and in increments of 100 between 100-10000, and were not computed above N > 10000.Retrieval quality with respect to exact Chamfer. In Figure 12 , we display the full plots for FDE Recall with respects to recovering the 1-nearest neighbor under Chamfer Similarity for all six BEIR datasets that we consider, including the two omitted from the main text (namely, SciDocs and ArguAna).Since the FDE generation is a randomized process, one natural concern is whether there is large variance in the recall quality across different random seeds. Fortunately, we show that this is not the case, and the variance of the recall of FDE is essentially negligible, and can be easily accounted for via minor extra retrieval. To evaluate this, we chose four sets of FDE parameters (R reps , k sim , d proj ) which were Pareto optimal for their respective dimensionalities, generated 10 independent copies of the query and document FDEs for the entire MS MARCO dataset, and computed the average recall@100 and 1000 and standard deviation of these recalls. The results are shown in Table 2 , where for all of the experiments the standard deviation was between 0.08-0.3% of a recall point, compared to the 80-95% range of recall values. Note that Recall@1000 had roughly twice as small standard deviation as Recall@100. We now show the effect of employing final projections to reduce the target dimensionality of the FDE's. For all experiments, the final projection ψ is implemented in the same way as inner projections are: namely, via multiplication by a random ±1 matrix. We choose four target dimensions, d FDE ∈ {2460, 5120, 10240, 20480}, and choose the Pareto optimal parameters (R reps , k sim , d proj ) from the grid search without final projections in Section 3.1, which are (20, 4, 8) , (20, 5, 8) , (20, 5, 16) , (20, 5, 32) . We then build a large dimensional FDE with the parameters (R reps , k sim , d proj ) = (40, 6, 128) . Here, since d = d proj , we do not use any inner projections when constructing the FDE. We then use a single random final projection to reduce the dimensionality of this FDE from R reps •2 ksim •d proj = 327680 down to each of the above target dimensions d FDE . The results are show in Tables 3 and 4 . Notice that incorporating final projections can have a non-trivial impact on recall, especially for Recall@100, where it can increase by around 3%. In particular, FDEs with the final projections are often better than FDEs with twice the dimensionality without final projections. The one exception is the 2460-dimensional FDE, where the Recall@100 only improved by 1.1%, and the Recall@1000 was actually lower bound 0.3%.Continuing our discussion from Section 3.2, we show that ball-carving at this threshold of 0.7 gives non-trivial efficiency gains. Specifically, in Figure 13 , we plot the per-core queries-per-second of re-ranking (i.e. computing CHAMFER(Q C , P )) against varying ball carving thresholds for the MS MARCO dataset. Please see the discussion in Section 3.2 for analysis of the figure.C.4 Product Quantization PQ Details We implemented our product quantizers using a simple "textbook" k-means based quantizer. Recall that AH-C-G means that each consecutive group of G dimensions is represented by C centers. We train the quantizer by: (1) taking for each group of dimensions the coordinates of a sample of at most 100,000 vectors from the dataset, and (2) running k-means on this sampleusing k = C = 256 centers until convergence. Given a vector x ∈ R d , we can split x into d/G blocks of coordinates x (1) , . . . , x (d/G) ∈ R G each of size G.The block x (i) can be compressed by representing x (i) by the index of the centroid from the i-th group that is nearest to x (i) . Since there are 256 centroids per group, each block x (i) can then be represented by a single byte.In Figures 14 and 15 we show the full set of results for our QPS experiments from Section 3.2 on all of the BEIR datasets that we evaluated in this paper. We include results for both Recall@100 (Figure 14 ) and Recall@1000 (Figure 15 ).We find that PQ-256-8 is consistently the best performing PQ codec across all of the datasets that we tested. Not using PQ at all results in significantly worse results (worse by at least 5× compared to using PQ) at the same beam width for the beam; however, the recall loss due to using PQ-256-8 is minimal, and usually only a fraction of a percent. Since our retrieval engine works by over-retrieving with respect to the FDEs and then reranking using Chamfer similarity, the loss due to approximating the FDEs using PQ can be handled by simply over-retrieving slightly more candidates.We also observe that the difference between different PQ codecs is much more pronounced in the lower-recall regime when searching for the top 1000 candidates for a query. For example, most of the plots in Figure 15 show significant stratification in the QPS achieved in lower recall regimes, with PQ-256-16 (the most compressed and memory-efficient format) usually outperforming all others; however, for achieving higher recall, PQ-256-16 actually does much worse than slightly less compressed formats like PQ-256-8 and PQ-256-4.The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: We have read the code of ethics and verified that research conducted in the paper fully conforms to the code.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: This work addresses the problem of improving the efficiency of multi-vector similarity search in the context of multi-vector models like ColBERT that represent queries as well as documents using multiple embedding vectors. Previous work addressed the efficiency problem of multi-vector similarity search taking a heuristic approach without any theoretical guarantees. In contrast, the current work proposes an approach that is theoretically grounded, simple to implement and use, relatively less sensitive to parameter setting and gives competitive retrieval performance and latency compared to the heuristic approach. 

The main idea here is to transform the multi-vector similarity search problem into a single-vector similarity search problem using Fixed Dimensional Encodings (FDEs) of queries and documents. FDEs are designed so that their inner product closely approximates multi-vector similarity as measured using Chamfer similarity and thereby enabling fast multi-vector retrieval using off-the-shelf MIPS solvers. Further, data oblivious transformations are used to compute FDEs thereby eliminating the need for additional datasets and/or training for the transformations. As FDEs are high-dimensional and therefore can have a large memory footprint, the work employs a vector compression technique called product quantization and thereby compressing the FDEs significantly without incurring substantial loss in recall. 

The work provides theoretical guarantees for the proposed approach. It shows that the inner product of FDEs of two multi-vector sets is an ε-approximation to the Chamfer similarity of the two sets.

The work compares the end-to-end retrieval performance of the proposed approach, as measured using Recall@N, with the heuristic search algorithm PLAID on MS-MARCO and several other datasets. While it achieves 10% higher recall an and  90% lower latency on average compared with PLAID, it has significantly higher latency (0.31 s vs 0.221 s) and nearly the same recall (0.971 vs 0.975) on MS-MARCO.

The problem and the proposed approach are well-motivated. The solution proposed is principled and backed by theoretical guarantees. Memory footprint is reduced significantly by a quantization trick. Results are very promising and competitive. The paper is well written and has sufficient detail to reproduce the experimental results. Authors have promised to release the code. Overall, the work makes significant contribution to multi-vector similarity search.

The experimental study can be strengthened further by addressing the following issues:

	1. Latency comparison is made only for 1 CPU thread. Speedup on GPU should also be reported. 
	2. End-to-end evaluation reports only Recall@N. MRR should also be reported as done by PLAID [35].
	3. End-to-end evaluation is not done on LoTTE benchmark. 
	4. Investigation of the reasons for higher latency for MS-MARCO is missing. A study of latency as a function of dataset size could be useful in this regard.

Reviews: review: paper_summary: paper_summary: This paper aims to improve the search efficiency of multi-vector retrieval models, such as ColBERT. Specifically, the authors propose MUVERA framework, which reduces the multi-vector (MV) similarity of a query/document pair to the single-vector (SV) similarity by constructing Fixed Dimensional Encoding (FDE) of MV representation. Such reduction allows re-using many highly-optimized MIPS solvers for multi-vector retrieval. The authors also provide theoretical guarantee on the approximation error of FDEs. Empirically, compared to previous SOTA heuristic for multi-vector retrieval, MUBERA can achieve a similar Recall while significantly reduce the latency.
strength_weakness: strength_weakness: Here are the summarized version. See detailed comments/questions in the next Section.
- The index size of MUVERA framework can be quite large
- MUVERA has sub-optimal performance on the MS-Marco dataset
- no released code
questions: questions: ### Q1: The index size of MUVERA
As illustrated in Figure 1, MUVERA consider a two-stage search procedure: (1) first using MIPS to obtain a candidate set of documents; and (2) re-rank the candidates with exact Chamfer similarity.
- (a) For the first step, using PQ codes on the FDE of documents and build ANN index indeed save the memory. For the second step, however, computing the exact Chamfer similarity still require storing all the original token embeddings per document?
- (b) What's the memory usage and index size for stage 1 and stage 2, respectively?

### Q2: Why do MUVERA has sub-optimal performance, compared to PLAID, on the MS-Marco dataset? 
- (a) Is it because of using data-agnostic partitioning functions (SimHash), making the approximation error of FDE larger?
- (b) If the token embedding distributions are skew and concentrating on certain sub-space (maybe this is the case in MS-Marco?) , is it still a good idea to use SimHash in FDEs? Or k-means would do a better work?

### Other minor comments
- (a) In Figure 1 caption, there is a typo: "comapred" => "compared"
- (b) At Line 133: "vectors that are closer are more are more likely to..." => there seems to be some repeatedly wording
- (c) In Figure 2, the legend on the left-hand-side seems wrong? The orange square should be Doc Embeddings and the blue circle should be Query Embedding, according to the right-hand-side plot?
limitations: limitations: To my knowledge, there's no potential negative societal impact.
paper_summary: paper_summary: The paper presents a method of converting multi-vector query-document retrieval problem to a single query-document vector-based retrieval problem. The basic idea is to project the multi-vector queries and documents into fixed-dimensional embedding through random projections. Further efficiency in storage of the random projections is achieved through vector quantization (product quantization) methods. The method is shown to result in improved recall as well as improvements in time performance. The projection into the fixed-dimensional space is obtained by latent semantic hashing (LSH). This concept could have been explained in a much simpler manner than presented in the paper.
strength_weakness: strength_weakness: It seems to me in the current age of LLMs, this technique appears to be a bit dated. There wasn't any mention of SpladeV2 and its variants either that are actively being used in commercial vector databases along with vector quantization in billion-vector size databases. Addressing this would be good for related work.  A 0.6 sec time performance for a single search is too slow for commercial uses, since typically multiple searches are rolled into an overall one. 

It is difficult to reproduce this work from the level of detail provided. A block diagram illustrating the overall steps would be useful.

There are typos in the draft so a good spell check is needed.
questions: questions: The fact that LSH preserves nearness is known. How does adding product quantization alter this ability? Does this technique allow for vector search using the compressed representation or the vectors need to be decompressed back before similarity search?
limitations: limitations: The limitations of the algorithm have not been adequately addressed. For example, for what sized datasets is this technique suitable or will be an overkill?
paper_summary: paper_summary: Multi-vector representation can greatly help retrieval systems work efficiently and accurately, transforming these sets of multiple vectors into a single vector representation that can still encapsulate the information from the multiple vectors, allowing efficient search using traditional single-vector search techniques while preserving the benefits of multi-vector search for rich document representation.
strength_weakness: strength_weakness: Computational overhead: as introduced by the FDE creation and query processing, the computational overhead may be high as the dataset grows. The MUVERA may have problems in preprocessing and dynamic updates.

The robustness of MUVERA across different types of retrieval tasks and its effectiveness in different domains (e.g., legal documents versus scientific articles) have not been extensively validated, for those domain-specific tasks, it could be beneficial to run experiments on different datasets from diverse domains.
questions: questions: What are the main trade-offs in this work? Maybe dimension reduction and accuracy are one of them: it is advantageous for processing speed and memory usage, but it can also lead to information loss.

What are the specific challenges encountered when implementing FDEs in real-world systems, particularly concerning maintaining the balance between efficiency and retrieval accuracy?

Tuning parameter W in this work: "The only tuning knob in our system is W; increasing W increases the number of candidates
298 retrieved by MUVERA, which improves the recall" Can this be pre-determined or you can use a specific algorithm to decide it?
limitations: limitations: If the computation overhead is a barrier problem for MUVERA running on a very large dataset, it may face limitations on scalability of the FDE approach, especially in terms of how well it can be adapted to very large datasets or highly dynamic environments.
paper_summary: paper_summary: The paper proposes a method of speeding up text retrieval approximating ColBERT multi-vector ranker with very high dimensional single vector using projections. 

Authors demonstrate that the proposed approach is better compared to a colbert-based single vector heuristic and is comparable to PLAID in terms of accuracy and speed, but is easier to tune.
strength_weakness: strength_weakness: 1) The heuristic approach is reminiscent of [Morozov, Stanislav, and Artem Babenko https://arxiv.org/pdf/1908.06887 ] where a more general problem is stated with a more general solution (using the ranker as the metric during the graph search). This approach seems extremely relevant, but not discussed/compared in the paper. 

2) Using a single vector embedding search to approximate a more complex interaction sounds like distillation of a ranker to a retrieval, which is a well-known baseline (e.g. googling gives https://arxiv.org/pdf/2210.11708 or https://arxiv.org/pdf/2403.20327 ). As both ranker and retrieval are trained, it is not clear why not directly train the retrieval model to directly optimize the ranking objective. There might scenarios where distilling is not feasible for some reason, but for a research paper I think it is important to show how much of the performance is lost.
questions: questions: I'd like the authors to address both points of weaknesses.
limitations: limitations: The approach is limited to multi-vector ranking as the function.
paper_summary: paper_summary: Efficient vector retrieval to maximise inner product similarity is well studied, and this paper explores the issue of multi-vector retrieval to support late interaction models like Colbert. The core idea is to use SimHash to generate clusters of multiple representation of documents, represent each document's vectors in a cluster using a centroid, and use that with the centroid of query vectors that land in the same cluster. Authors rely on the SimHash's approximation theory to show that this approach approximates the maxSim measure used by Colbert. Experimental results indicate Muvera outperforms PLAID in some of the datasets from BEIR in terms of query latency and Recall@k.
strength_weakness: strength_weakness: w1. the theoretical analysis of the presented approach is rather limited. SimHash theory focuses on EMD minimisation while the focus here is on Chamfer similarity maximisation. So, it would be good detail the theory further. 

w2. despite multiple stages listed for PLAID, the performance of MUVERA is not particularly strong -- in terms of latency, PLAID outperforms MUVERA on largest dataset (MS-MARCO). It leads one to question if the observed latency gains are primarily due to small(er) dataset sizes? Similarly in terms of recall@k, MUVERA outperforms PLAID only in a couple of datasets. 

w3. there is no mention of how far from ideal (i.e, ColbertV2 performance) is the proposed model?
questions: questions: q1. I would have liked to see the connection with the EMD approximation theory of SimHash with the Chamfer distance approximation presented here. In general, it seems to me --authors can clarify if I am mistaken-- the key innovation is the use of centroids in each bucket, instead of the standard O(n^2) similarity computation done even with SimHash in applications such as shingling. It would also be useful to show the sensitivity to the value of B = number of partitions. 

q2. Improvements over PLAID are not significant in my opinion -- in terms of both latency and recall @ k. There are only few datasets (NQ-{100,1000}, HotPotQA-{100, 1000} the recall is better, and latency is worse in ms-marco (a commonly used Colbert benchmark). Further, it would be also worthwhile comparing with the baseline of ColbertV2 (without using any of these efficient indexing techniques).
limitations: limitations: Given that the work is aimed at improving the performance of an existing retrieval framework, I do not expect to see any specific negative societal impact from the work. Authors also have given similar remarks.
paper_summary: paper_summary: The paper studies how to optimize multi-vector retrieval under the MaxSim similarity function (commonly used in NLP literatures like ColBERT). This is done by mapping queries and item embeddings asymmetrically to fixed dimensional embeddings (FDEs), such that in the mapped embedding space, the inner product similarity is a good approximation of the original MaxSim similarity. This approach then enables classical MIPS techniques to be applied to optimize for MaxSim similarity search. The authors compare FDEs with PLAID / SV heuristics, and found it to outperform those optimized similarity search baselines.
strength_weakness: strength_weakness: **W1**: With FDE, the MaxSim approach (used in ColBERT and other work)'s effectiveness is degraded dramatically, to the point that it underperforms dense retrieval baselines.  E.g., Figure 3 (LHS) suggest that Recall@100 of FDE is quite bad vs Exact MaxSim in ColBERT (up to ~.84, vs ~.92). The main issue here is that, gains of non-MIPS similarity approaches (like MaxSim and more recently DSI/NCI etc.) are primarily on smaller @Ks (e.g., ColBERT v2's quality gains are primarily demonstrated on Metric@10 in their original paper). The current paper only reported Recall@K={100, 1K, 10K}, which are not aligned with intended use cases for ColBERT (as it didn't provide that much gains over dense baselines for these Ks).
- Even at 100, the 1-.84/.92 = 0.087 degradation in recall will likely make MaxSim+FDE underperform classical dense retrieval baselines. E.g., on MS MACRO, DPR achieves 82.2 R@50 whereas ColBERT achieves 82.9 R@50 per [1] (and gap @100 will be smaller). So adjusting for FDE's quality degradation, we get 82.2 for dual encoder baselines but just 82.9 * .84/.92 = 75.69 for MaxSim, and people will ask - why not use classical dense encoders like DPRs to begin with?
- Additionally, to achieve the ~.84 recall, FDE encodings already used 20K floats vs 10,087 in MS MACRO multi-vector baselines per Fig. 3...

**W2**: Random projection techniques (incl. their multi-hash variants, or $R_{reps}$ in this paper), and production quantization techniques used in FDEs are commonly used in MIPS systems, and generally universally reduce memory access costs and improve throughput/latency, etc. of nearest neighbor methods (after hparam tuning). Have we evaluated applying random projection and PQ techniques directly to baselines like ColBERTv2, PLAID, etc.? How much of the throughput gains presented in the paper are due to RPs/PQs?

**W3**: Writing could be improved.
- It would be good to add a table of notations, at least to appendix to help with references. Even though I work on vector search (incl multi-vector search and variants), I ended up spending quite some time figuring out what the authors meant by various notations in Section 2. 
- Line 141-142: "To resolve this, we set ~p(k) to be the centroid of the p ∈ P’s with ϕ(p) = ϕ(q)". - This sentence is confusing as the FDE mapping for query (p) should not be item (q) aware. Please consider rewriting it to reflect the actual mapping done in Equation (3). 
- Section 3: consider removing codebase/dataset licenses (CC BY-SA MIT etc.) as most readers may not find them useful.
- Line 311 - "We run latency experiments using a single thread, and run our QPS experiments on all 176 threads."  Could you explain why latency experiments are run with a single thread? As using additional threads should further improve latency.
- Typos: Line 132-133 are more are more likely to land in -> are more likely to land in
	

**References**:
- [1] Ren et al. PAIR: Leveraging Passage-Centric Similarity Relation for Improving Dense Passage Retrieval. ACL 2021
questions: questions: **Q1**: Would it be possible to report effectiveness of FDE + MaxSim vs corresponding baselines (incl dense retrieval and ColBERTv2 etc.), esp. for common Ks (10, 50, 100)?

**Q2**: Can we equally apply techniques like PQ and random projection to baselines (again ideally dense retrieval with a comparable embedding dimensionality to normalize I/O costs), and evaluate how much throughput gains are due to PQs/RPs vs the particular construction of FDEs proposed in this paper? 

**Q3**: FDE's approximation quality seems to heavily rely on how the B clusters are defined. If B is large: a) the overall dimensionality is large, requiring significantly more memory accesses, and b) Max(P, Q) may not map to anything.  OTOH if B is small, many false positives collisions may occur, resulting in (potentially significant) overestimation of the MaxSim similarity function. Is there a reliable way of grid searching B (other than in 2^k as done in Sec 3.1)? Could we discuss this somewhere in the paper?
limitations: limitations: NA

Comments: title: Response to rebuttal
Re: Rebuttal by authors
re: rebuttal
Some additional questions
Reviewer-Author Discussions
some additional questions
comment: We thank the reviewer for their comment, but disagree with the assessment on limited interest on this domain from a broader community! Importantly, we emphasize the following

(1) The demand for neural information retrieval is stronger than ever. If the number of startups that are forming to offer this service, or the number of cloud service providers that are offering a variety of services that use information retrieval is not convincing enough, one can look at the sheer number of research papers that are being written in this domain. Here is a list of some of the papers that are posted to arxiv since the beginning of 2024 specifically on multi-vector: https://arxiv.org/abs/2407.20750 https://arxiv.org/abs/2405.15028 https://arxiv.org/abs/2404.02805 https://arxiv.org/abs/2404.00684 https://arxiv.org/abs/2402.15059 https://arxiv.org/abs/2403.13291 https://arxiv.org/abs/2402.03216

(2) While a lot of headroom remains on the table in neural information retrieval, there hasn't been a lot of progress in the single vector modeling recently and it is believed that single vector models can’t address the remaining major challenges and multi-vector approaches can potentially move the needle here. These challenges include: information retrieval for ambiguous, multi-intent, and not-a-right-answer queries; information retrieval for complex and nuanced queries that require multiple different pieces of information to be answered.

(3) In GenAI, which is undoubtedly the hottest field of AI at the moment, neural information retrieval is critical and is going to remain important in the foreseeable future in the RAG type systems. In this context, similar to (2) above, single vectors fall short in terms of quality for complex and critical problems such as multiple needles in a haystack problem that is in the center of many generative tasks.

(4) While multi-vector models have already shown to outperform single-vector models for information retrieval, the main reason their use-case has not become standard in all the above mentioned domains is their lack of efficiency compared to single vector models and retrieval systems.

We believe the above provides substantial evidence for the broad appeal of algorithms for multi-vector models
Thanks for those clarifications. So could you comment on how your method compares to Splade V2?
Also, what would be the time performance in realistic settings? What is the largest vector database you have tested this against?
Finally, it would be good to compare the results of retrieval with and without PQ and LSH components to see how much loss in accuracy.

So although the response addressed my questions somewhat, the answers I am looking for are still not there as indicated above.
We thank the reviewer again for this discussion and valuable comments. 

>”In (Charikar, STOC'02) EMD approximation using LSH is given in Section 4. I disagree that the paper dealt only with cosine similarity between single vectors. If you believe that your analysis is significant improvement or different over the analysis given there, please clarify.”

Note that we did not claim that the (Charikar, STOC'02) only considered cosine similarity between single vectors. Instead, we stated that *SimHash*, which is a particular LSH function, was only used in that paper to estimate cosine similarity. For completeness: SimHash is a random hash function h:R^d → {0,1} which maps a d-dimensional vector to a single bit {-1,1} by (1) drawing a random gaussian vector g ~ R^d and (2) outputting the sign bit of the dot product <x,g>, so SimHash(x) = Sign(<g,x>). The reviewer is correct that the Charikar paper gives algorithms for sketching EMD, but they are *not* based on SimHash.

Let us attempt to clarify the differences in the historical approaches to sketching EMD vs. the approach in our paper. In the Charikar paper, as well as all other papers on sketching EMD, the main technique is called probabilistic tree embeddings (e.g. Bartal trees or FRT embedding, see e.g. Bartal, Yair. "Probabilistic approximation of metric spaces and its algorithmic applications."). This technique creates a randomized embedding F from the original metric ( R^d for us, but also works for any metric) into a tree metric T, such that the shortest path distances in the tree T approximates the original metric distances. For two sets A,B, if we want to estimate EMD(A,B), we first apply F to each point in A and B, to get two sets of vertices F(A),F(B) in a tree. One then tries to compute the EMD in the tree; the key point is that EMD in a tree can be embedded isometrically into the L1 metric (over single vectors) via a simple folklore embedding. This is all fundamentally different from our approach, which does not use tree embeddings at all. 

The above is the general recipe used for all algorithms for sketching EMD. The Charikar paper obtained a log(n) log log(n) approximation for any general metric. Indyk (STOC ‘04) improved this to O(log n) for the 2-dimensional grid (R^2), and (Andoni, Alexandr, Piotr Indyk, and Robert Krauthgamer. "Earth mover distance over high-dimensional spaces." SODA 2008) extended this to a log^2(n) for high-dimensional spaces R^d. These last two algorithms used an L1 distance LSH based on random Quadtree decompositions (which splits the space into random nested hypergrids), which is fundamentally different from SimHash.

For a more detailed overview of the history and techniques used in sketching EMD, see the overview Section 1.1, of (Rajesh Jayaram, Erik Waingarten, and Tian Zhang. "Data-Dependent LSH for the Earth Mover’s Distance." STOC 2024, https://arxiv.org/pdf/2403.05041). 

Now for our results, note that we surprisingly are able to prove strong sketching results without the usage of probabilistic tree embeddings at all. Further, the reviewer is correct that we get a much better approximation: specifically, we get a (1+eps) approximation instead of a O(log n) or O(log^2(n)) approximation. This is possible due to our different techniques and the many differences between EMD and Chamfer (e.g. Chamfer is asymmetric, and does not satisfy triangle inequality). Some of the key differences are (1) we use an *asymmetric* LSH (encoding documents different from queries) based on SimHash (2) we do not use a tree embedding approach, but instead partition the space on a *single* granularity (unlike the nested partitions in tree embeddings) (3) we embed Chamfer into single vectors with the *dot product similarity* instead of the “L1 distance” – these two spaces behave very differently. The combination of these three different techniques, as well as the difference in the function we are trying to approximation (Chamfer vs. EMD) is how we get the improved approximation.

> “ The computational cost for over-retrieving... is not given ... how does this over-retrieval compare with the performance of ColbertV2?”

We emphasize that the experiments the reviewer is discussing in Figure 3 are part of our *offline experiments* that are meant to compare how over-retrieval with FDE’s compares to brute force (using the ColBERTv2 Model). Since this paper introduces a new sketching method (FDEs) we used this experiment to show how well FDEs approximate brute force max-sim (chamfer).

We note that we do spend substantial time in the paper discussing online retrieval experiments which show the tradeoff between recall and QPS (Figures 6 and 7, and more in the supplementary materials). These experiments compare our online retrieval solution to PLAID, which is the fastest retrieval mechanism for the ColBERTv2 model to date. Note that PLAID is orders of magnitude faster than brute-forcing ColBERTv2.
Thanks for your further comments and questions.

> “first, in terms of FDE generation, due to the fact that I don't have your code access, I'm curious how long it takes to finish FDE generation on your datasets provided.”

FDE generation is extremely fast—the average running time to generate an FDE is roughly 0.001s, and is embarrassingly parallelizable.

> “skewed data distribution, can this framework somehow overcome this problem theoretically?”

With regards to skewed data distributions, we would like to emphasize that our theoretical results hold for any input, even worst case inputs, as is standard in theoretical computer science. Thus skewed data would not affect the performance of our algorithm theoretically. 
 
> “how big is the index in terms of the disk usage on some specific dataset? Do you need to load the index into memory like HNSW indexes? Your index disk usage and memory footprint may be a crucial point of your work.”

We provided some details about the index size in our discussion with reviewer Z5yi. The index size for MUVERA is dominated by the space used for the multivector embeddings. As we discussed with reviewer Z5yi, future optimizations for our system could reduce the space usage by applying quantization techniques to the multivector embeddings. We note that the space used for our graph index and FDEs is about 10% of the space of the original multi-vector representations. We would be happy to add exact space usage numbers for the index to the final version of the paper.

Yes, we do load the index into memory as in an HNSW index. We are using the DiskANN algorithm fully in-memory, which we will emphasize in the paper. The DiskANN algorithm is extremely competitive and many vector search companies (e.g., Pinecone) have migrated from HNSW to DiskANN due to its strong performance.

> “building an index on a multi-vector is somehow a fixed solution for specific multi-vector queries, e.g., we have vector columns vc1, vc2, vc3, vc4, and we somehow build them together via FDE, your framework is focused on the combinational query on vc1, vc2, vc3, vc4, right? Can it be used to serve queries on vc1 + vc3?”

We are not fully sure what the reviewer means by this question—if we understand the reviewer’s question correctly, the reviewer is describing a vector database use case where an object has multiple vector columns (v1, .., v4), where the vectors are produced using potentially different single-vector models, which is fundamentally different from the setting that we consider.

Our paper is focused on the multivector setting where we have a single multivector *model* which transforms an object into a set of vectors, which all live in the same latent space. When a query arrives, we run the same model on it to transform it into a set of vectors. The goal is to find the most similar document, where similarity is given by a specific set-set function—the chamfer similarity. 

> “Does the W parameter have a relatively monotonic effect on the results? For example, in IVF indexes, the larger the search partition parameter is set (n_probe), the higher the recall rate will be, and the longer the latency will also be expected.

Yes, increasing W monotonically improves the quality of the results—it will result in higher recall at the expense of higher latency as the reviewer correctly pointed out.
I thank the authors for providing detailed responses to my questions. 

> SimHash as a Locality Sensitive Hash (LSH) function dates back to the paper “Similarity Estimation Techniques from Rounding Algorithms” (Charikar, STOC ‘02), where it is used to estimate the cosine similarity between single vectors. 

In (Charikar, STOC'02) EMD approximation using LSH is given in Section 4. I disagree that the paper dealt only with cosine similarity between single vectors. If you believe that your analysis is significant improvement or different over the analysis given there, please clarify. 

Since some of my other queries are dependent on this aspect, I would like to hear from the authors before I update my rating. 

> We actually do compare to the ideal ColbertV2 Performance (i.e., the performance obtained by a brute-force search using Chamfer similarity) in the paper. Specifically, in Figure 3 we show the baselines for “Exact Chamfer@N” for various N, which is precisely the brute-force ColbertV2 performance. 

Thanks for pointing this out. The computational cost for over-retrieving (upto 10k for reaching ColbertV2) and reranking is not given. latency and QPS plots seem to be for retrieving 1000 (please clarify if I am incorrect), and how does this over-retrieval compare with the performance of ColbertV2?
I would like to that the authors for the response and for scope clarification. I'll increase the soundness score

I think the paper scope on adapting the existing multi-vector solutions limits its interest from a broader community, so I am going to keep my rating.
Thanks for the clarification. 

I have some additional questions for this work:

- first, in terms of FDE generation, due to the fact that I don't have your code access, I'm curious how long it takes to finish FDE generation on your datasets provided.

- Second, the data diversity I mentioned may have another concern, which is skewed data distribution, can this framework somehow overcome this problem theoretically?

- how big is the index in terms of the disk usage on some specific dataset? Do you need to load the index into memory like HNSW indexes? Your index disk usage and memory footprint may be a crucial point of your work.

- On the other hand, building an index on a multi-vector is somehow a fixed solution for specific multi-vector queries, e.g., we have vector columns vc1, vc2, vc3, vc4, and we somehow build them together via FDE, your framework is focused on the combinational query on vc1, vc2, vc3, vc4, right? Can it be used to serve queries on vc1 + vc3?

- Does the W parameter have a relatively monotonic effect on the results? For example, in IVF indexes, the larger the search partition parameter is set (n_probe), the higher the recall rate will be, and the longer the latency will also be expected.
We are glad that our explanation helped clarify some matters about our retrieval setup, and we will be sure to help clarify the exact setup further in the paper. We note that our main figure 1 (on page 2) shows the retrieval and reranking process, where the Chamfer reranking is a key step – we will add a further discussion on the importance of reranking in 1.2 where it is currently described. 

“multi-vector SV baselines”
What does it mean to be a multi-vector SV baseline? We were slightly confused by this description and would like to understand better. 

“It might be useful to compare learned SVs which seem to work for small ds” 
We agree that training a SV model to approximate the Chamfer similarity is an interesting and important direction for future work. However, as discussed in the global response, the focus of our paper is to design an improved standalone retrieval algorithm for multi-vector databases. Like PLAID, we assume we are already given as input a multi-vector database (without necessarily having a training set needed for distillation), and we need to find the approximate nearest neighbors under the Chamfer Similarity for the MV embeddings in that dataset. Thus, comparing with other SV models, such as those distilled from a re-ranker, is somewhat out of the scope of the current paper. 

We also agree that pre-filtering with SV before a more complex or learned similarity is an popular and important method in the IR literature, and we will be sure to add references and discuss this alternative further in the paper.

“multi-vector heuristics” 
We used the term “SV heuristic” to emphasize that the retrieval stage was only taking into account interactions between single vectors, and not aggregate interactions between sets of vectors (i.e. MV), which is what makes MV models unique. Moreover, we wanted to describe a *specific* heuristic which was to retrieve the top-k for each single vector and then aggregate them. We agree with the reviewer, though, that there may be a better term to describe this method, and will attempt to change it in the final version to something more descriptive.

“it might be useful to report the K' and FDE dimensionalities “
In the sentence on lines 332-336, we report that we used 10k-dimensional FDE’s with PQ-256-8 (32x compression) for all the latency experiments, and that we set K’ (=(# reranked)) to be equal to the beam width W (which is variable, since we tune so that our recall matches the recall of PLAID for each dataset). We will be happy to add the specific value of the beam-width K’ = W used for each of the six datasets in Figure 7 to give a more complete picture of the parameters. 

“quantization scheme across ColBERTv2/PLAID vs this work”
We note that the standard PQ technique we use in this paper is different than the 1-2 bit compression scheme used in PLAID/ColBERTv2. Standard PQ-256-8 compresses chunks of size 8 into one of 256 centroids, whereas ColBERT/PLAID used many more centroids (2^32 or 2^16) plus a residual with 1 or 2 bits per dim. One advantage of PQ-256-8 is that using fewer centroids allows us to pre-compute a codebook that will fit in cache, allowing for very fast scoring (whereas 2^16 centroids would be too large of a codebook to fit in cache).

“It would be helpful to control for related factors somehow”
We note that we do conduct QPS experiments in C.4 considering different compression schemes, including PQ-256-4 which would compress blocks for 4 coordinates into one byte (so 2 bits per float). We found PQ-256-8 to offer a better QPS vs Recall tradeoff, since scoring is faster with a more compressed vector (and not much recall is lost). Since there are several differences between our approach and PLAID — (1) we are using a graph-based index for retrieval instead of IVF, which have different memory access patterns (IVF enjoys more sequential accesses) and (2) we are doing PQ mainly on the FDE’s and they are doing the PQ on the original 128-d vectors — it would be difficult to compare the two methods in precisely the same setting. However, our PQ-256-8 and PQ 256-4 with a similar number of retrieved candidates per query vector (and using 10k-dim vectors) would give the same number of bits retrieved from memory on MS Marco as PLAID (although note that our FDE vs. SV Heuristic section shows that FDE’s need to retrieve fewer candidates to get the same recall). 

“won't fill_empty_clusters break the FDE construction in Sec 2?”
We would like to emphasize that fill_empty_clusters is part of Section 2. Thus, it is used in the theorems that we prove and in all of our experimental results. Thus, far from breaking the FDE construction in Sec 2, fill_empty_clusters is actually a core part of the FDE construction in Sec 2. 

We thank the reviewer again for this valuable discussion. If the reviewer agrees with the above points of clarification, we encourage them to reevaluate their score.
Dear reviewers: as you are aware, reviewer-author discussions phase is ending on Aug 13. We request you to kindly make use of the remaining time to contribute productively to these discussions. If you have not read and/or responded to author rebuttal, please do it asap so that the authors get a chance to respond to you. If you have more questions to ask or want further clarification from the authors, please feel free to do it. 

Dear authors: please read the responses of the reviewers and if there are any pending questions/request-for-clarification, please attend to them.
Thanks for the clarification about the index size. I will encourage the author also supplement the index size of MUVERA (stage1 and 2 respectively) together with the Recall and latency results, in the main experiment sections. The index size is also a crucial factor to be considered when deploying the ANN search system for online retrieval. Thus, I will like to keep my score as is.
Thanks for providing the clarifications. I have some additional questions based on the authors' responses: 

* inference setups used w/ FDE + MaxSim: thanks for your response to W1 as I was confused about the exact inference setup earlier. polishing writing further with a paragraph highlighting FDE's inference setup somewhere would be useful. Some comments:
  * ColBERTv2 and PLAID are more *multi-vector* SV baselines, whereas the inference setup in this paper differs by doing lightweight prefiltering w/ FDE SV to a larger set. This reminds me of retrieve-then-rerank in IR which is a reasonably common setup and may need discussions/comparisons. Some related work in this area might include Learning Query-dependent Prefilters for Scalable Image Retrieval. CVPR'09 [1], Revisiting Neural Retrieval on Accelerators. KDD'23 [2] etc. In particular [2] also proposed to retrieve with learned single-vector SV followed by re-scoring with learned similarities. It might be useful to compare learned SVs which seem to work for small ds (64d in [2]) vs FDE constructed SVs (2k-20k dimension here, albeit different datasets etc)?
   * writing: would using "multi-vector heuristics" to characterize the method in ColBERTv2/PLAID make more sense, given prior work have explored two-stage SV for learned distance functions, and learned SV seems like a reasonable/competitive baseline here?
   * it might be useful to report the K'  and FDE dimensionalities $d$s used for prefiltering the candidate sets (per your comment *"... we wanted to achieve end-to-end 0.84 recall, we would not use the raw output of the 20k dimensional FDE’s. Instead, we could use the (e.g.) 960 dimensional FDE"*), and how this affects final end-to-end recalls to help with understanding.

* efficiency experiments: double checked the papers, it seems that we didn't use the same quantization scheme across ColBERTv2/PLAID vs this work. eg this work uses PQ-256-8 which compresses each float to 1 bit (line 307-308) whereas PLAID compresses each float to 2 bits ("For both vanilla ColBERTv2 and PLAID ColBERTv2, we compress all datasets to 2 bits per dimension, with the exception of MS MARCO v2 where we compress to 1 bit."). It would be helpful to control for related factors somehow, given retrieval efficiency is frequently memory-bandwidth bound. 

* Re Q5: thanks for pointing out fill_empty_clusters. But won't fill_empty_clusters break the FDE construction in Sec 2?