MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding
Authors: Rajesh Jayaram
Laxman Dhulipala
Majid Hadian
Jason Lee
Vahab Mirrokni
Venue: NeurIPS 2024 poster (2024)
Keywords: Retrieval
Late Interaction
ColBERT
Multi-Vector
Primary area: optimization
TL;DR: We give a new and highly-efficient algorithm for multi-vector retrieval via a provable reduction to single-vector retrieval.

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.

MUVERA: Multi-Vecton Retrieval via Fixed Dimensional Encodings
Laxman Dhulipala Google Research and UMD
Majid Hadian Google DeepMind
Rajesh Jayaram' Google Research
Jason Lee Google Research
Vahab Mirrokni
Google Research
Abstract
Neural embedding models have become fundamental component of modern information retrieval (IR) pipelines. These models produce a single embedding I R 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 set of embedding per data- point, have achieved markedly superior performance for IR tasks. Unfortunately, using these models for IR is computationally expensive due the increased complexity of multi-vector retrieval and scoring.
In this paper, introduce MUVERA (Multi-Vector Retrieval Algorithm), trieval 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 Encod- ings (FDEs) of queries and documents, which are vectors whose inner product approximates multi-vector similarity. We prove that FDEs give high-quality e- approximations, thus providing the first single-vector proxy for multi-vector simi- larity with theoretical guarantees. Empirically, we find that FDEs achieve the same recall prior state-of-the-ar heuristics while retrieving 2-5x x fewer candidates. Compared to prior state of the art implementations, MUVERA achieves consis- tently good end-to-end recall and latency across diverse set of the BEIR retrieval datasets, achieving an average of 10% improved recall with 90% lower latency.
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 classifica- tion [39]. Recently, multi-vector (MV) representations, introduced by the late-interaction framework in ColBERT [29]. have been shown to deliver significantly improved performance 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 dataset by orders of magnitude. Moreover, due the non-linear Chamfer similarity scoring, there is lack of optimized systems for multi-vector retrieval. Specifically, single-vector vector retrieval is
Cooresponding Author: ekjayaraa@@google.com
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

MUVERA
PLAID
T, FDEs
Exnbecdings
Chander Reraskin
Querry
Toadl
MIPS Iodox EXSLANNI
Topik)
Decuments
Stage 1, Diesmee EDES
Sige 2. Chassia Ranaking
E: larkl Coecnda
Sagp Coavid Inarrnan with
Sugp Gotoral fraetsiie
Stge Randing
Quary
Figure I: MUVERA'S two-step retrieval process, compared 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 query to the nearest embedding in 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 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 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 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 find the true MV nearest neighbors. Additionally, this process is expensive, since it requires querying 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, 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- retrieval mechanism based on light-weight and provably correct reduction to single-vector MIPS. MUVERA employs a fast, data-oblivious transformation from set of vectors to 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 C Rd into single fixed-dimensional vectors 7. p. called Fixed Dimensional Encodings (FDEs), such that the the dot product q approximates the multi-vector similarity between (S2). 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@NN surpasses the RecalI@2-5N achieved by the SV heuristic while scanning 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 s-approximation 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 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 be robust and efficient retrieval mechanism; across the datasets we evaluated, MUVERA obtains average of 10% higher recall, while requiring 90% lower latency on average compared with PLAID. Additionally, MUVERA crucially incorporates vector compression technique called product quantization that enables us to compress the FDEs by 32x (i.e., storing 10240 dimensional FDEs using 1280 bytes) while incurring negligible quality loss, resulting in a significantly smaller memory footprint.

---

1.1 Chamfer Similarity and the Multi-Vector Retrieval Problem
Given two sets of vectors Q, P C. R2, the Chamfer Similarity is given by
CHAMFER(Q,P))
Σ SEQ
max p) PEP
where (.--) is the standard vector inner product. Chamfer similarity is the default method of MV sim- ilarity used in the late-interaction architecture of ColBERT, which includes systems like C [44], Baleen [28], Hindsight ], DrDecr [34], and XTR [32], among many others. These models en- code queries and documents sets Q, P C R (respectively), where the query-document similarity is given by CHAMFER 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, 45J) 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 as MaxSim 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 dataset = [P',..... P',} where each P. C I is a set of vectors. Given a query subset Q C R the goal is quickly recover the nearest neighbor P E D, namely:
p arg max CHAMPER P3) PID
For the retrieval system to be scalable, this must be achieved in time significantly faster than brute- force scoring each of the n similarities CHAMFER (Q, P.) within D.
1.2 Our Approach: Reducing Multi- Search to Single-Vector MIPS
MUVERA is streamlined procedure that directly reduces the Chamfer Similarity Search to MIPS. For pre-specified target dimension dFDE, MUVERA produces randomized mappings Fq 2 - Rdree
(for queries) and Feoc/ 24t R dons (for documents) such that, for all query and document multi-vector representations Q, P C Rd we have:
Foc vo CHAMFER(Q, P)
We refer to the vectors (Q).). F decc( as Fixed Dimensional Encodings (FDEs). MUVERA first applies F doc to each document representation P E D, and indexes the set (o (P) into MIPS solver. Given query Q R MUVERA quickly computes F (Q) and feeds it to the MIPS solver to recover the top-k most similar document FDE's (P)) Finally, we re-rank these candidates by the original Chamfer similarity. See Figure I for overview. We remark that one important advantage of the FDEs is that the functions Fg. Fase are data-oblivious, making them robust to distribution shifts, and easily usable in streaming settings.
1.3 Related Work Multi-Vector Retrieval
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 E Q. In ColBERT v2 [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 e-approximate nearest neighbors time Ó( Q(T). where T' is roughly the maximum number of document tokens p E P: that are similar to any query token g E Q. which can as large as max; PPl. Thus, the worst case, their algorithm runs no faster than brute-force. Conversely, our algorithm recovers e-approximate nearest neighbors and always runs in time (m22)) Experimentally. DESSERT is 2-5x faster than PLAID, but attains worse recall (e.g. 2-2.5% 100000 on MS MARCO). Conversely, we match and sometimes strongly exceed PLAID's recall with up to 5.7x lower latency. Additionally, DESSERT still employs an initial filtering stage hased on k-means clustering of individual query token embeddings (in the manner of C2) thus they do not truly avoid the aforementioned limitations of the SV heuristic.
3

---

2 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 set of vectors into a single vector. For instance, they have been used to embed the Earth Mover's Distance into the l metric [1, 10, 22, 24], and embed the weight of a Euclidean MST of set of vectors into the Hamming metric 19, 22, 23]. However, since we are working with inner products, which are not metries, instead of Ep distances, alternative approach for transformation will be needed.
The intuition behind our transformation is as follows. Hypothetically, for two MV representations P C RR, if we knew the optimal mapping л Q -> P in which to match them, then we could create vectors T. p by concatenating all the vectors in Q and their corresponding images P together, so that (7. p) = En (g. (g)) CHAMFER(Q2 (Q P). However, since we do not know in advance, and since different query- -oeymddo 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 I2 so that, after clustering close points together, the dot product of any query-document pair Q, P C IR concatenated into a single vector under this ordering will approximate the Chamfer similarity.
The first step is to partition the latent space Id into B clusters so that vectors that are closer are more likely to land in the same cluster. Let o R + [B] be such a partition (for an integer N > 1 we use the notation [M] = {1, (........ N }); can be implemented via Locality Sensitive Hashing (LSH) [20], k-means, or other methods; we discuss choices for yp later in this section. After partitioning via sp the hope is that for each g Q, the closest p E P lands in the same cluster (i.e. (p(g) = (())). Hypothetically, if this were occur, then:
CHAMFER (Q,P)
Σ
Σ
max (g.p)
PEP
(p())=k p(p)=k
GEQ
If p is the only point in P that collides with g, then (1) can be realized as a dot product between two vectors q. by creating one block of d coordinates in 7. p for each cluster k E [B] (call these blocks Ka))P(N) P(x) E Rd), and setting (()): P(xe to be the sum of all q E Q (resp. p P) that land in the k-th cluster under sp. However, if multiple p' P collide with q, then (7. P) will differ from (1), since every p' with (p')) pp(4) will contribute at least (q, P') to (q. p). To resolve this, we set P(R) to be the centroid of the E P's with (pp) = p(4). Formally, for k- = 1,..., B, we define
Σ 9.
P(k) IP (k))
Σ PEP 4p(p==
(2)
REQ =ka)=k
Setting q= ((B))
and 7 (f .(B))) then we have
B
(
Σ (1.P)
(3)
Pn
(k)
h=1 <(())k k
EEQ
PEP
p(p)=k
Note that the resulting dimension of the vectors 7.7's is d.. To reduce the dependency d, can apply a random linear projection &b : Rd -> df to each block ((s),P() where dpros < d. Specifically, we define (x)) = /draa Sax, where S E R is random matrix with uniformly distributed 1 entries. We can then define T()) (Q(()) and P(R) (b(()) and define the FDE's with inner projection as 7+ (T(1)........ {(B),.) and Pip = ( ..) When d d we simply define v to be the identity mapping, which case go. Pw are identical to q. P. To increase accuracy of (3) in approximating (1), we repeat the above process Reeps > 1 times independently, using different randomized partitions PI..... Reps and projections $1..... &RR.e We denote the vectors resulting from i-th repetition by T. Pr. Finally, we concatenate these Reoge vectors together, so that our final FDEs are defined as F (Q(Q) = (Øi,,,.... .., ....g
and Fa (P) (PI.w,... ....,.... ........) Observe that complete FDE mapping is specified by the three parameters dproo, Peepa), resulting in a final dimension of dede B ddpros Rrepa.
Choice of Space Partition. When choosing the partition function y, the desired property that points are more likely to collide (i.e. sp(x)= sp(y)) the closer they are to each other. Such functions

---

F
F2(()
(P)
A
X
C
B
0
0
A
Doc Embeddings
C
y+z
W
Query Embeddings
D
0
(t+u)/3
F
0
Figure 2: FDE Generation Process. Three SimlHshes (kum = 3) split space into six regions labelled A-F (in high-dimensions B 2 but 6 here since d' = 2). (Q). Fac(P) are shown as B x matrices, where the k-th row is ((k).Pa). The actual FDEs are flattened versions of these matrices. Not shown: inner projections, repetitions, and fill _ clusters.
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- models, SimHash [8] is the standard choice of LSH. Specifically, for any Knim 2 1, we sample random Gaussian vectors
91....,. -hhim E R and set (xx)) = (1 (1()) x) > O)...., . 1 x) > 0)), where 1(-) {0. 13 is
the indicator function. Converting the bit-string decimal, (o(x) gives mapping from I2 to [B] where B 2 In other words, SimHash partitions R by drawing Keim random half-spaces, and each of the 2 clusters is formed by the hum -wise intersection of each of these halfspaces or their complement. Another natural approach is choose iEENTER 3/ I centers from the collection of all token embeddings U P., either randomly or via k-means, and set (p(x) E [RCENteR] to be the index of the center nearest We compare this method to SimHash in ($3.1).
Filling Empty Clusters. A key source of error in the FDE's approximation is when the nearest vector p E P to a given query embedding q Q maps to a different cluster, namely <p() * (p(g) This can be made less likely by decreasing B, at the cost of making it more likely for other p' E P to also map to the same cluster, moving the centroid P(a) farther from p. If increase B too much, is possible that no p E P collides with (q)). To avoid this trade-off,
directly ensure that if no E P maps to a cluster k, then instead of setting P(a) = 0 we set P(a) to the point that is closest to cluster k. As result, increasing B will result in more accurate estimator, as this results in smaller clusters. Formally, for any cluster k with Pn (k) = 0, if fill empty_ clusters is enabled, we set P(k = p where p E 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 given E Q contributing to the dot product multiple times.
Final Projections. A natural approach to reducing the dimensionality is to apply final projection vb' IR deon + Rd (also implemented via multiplication by a random +1 matrix) to the FDE's, reducing the final dimensionality to any danal < dFDE. Experimentally, we find that final projections can provide small but non-trivial 1-2% recall boosts for a fixed dimension (see SC.2).
2.1 Theoretical Guarantees for FDEs
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) श CHAMFER P). This ensures
NCHAMFER ( P) E [-1, whenever the vectors in Q, P are normalized. Note that this factor of 1/1Q| does not affect the relative scoring of documents for a fixed query. what follows, we assume that all token embeddings are normalized (i.e. ||d/|2 lllll
for all q Q, 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 E-additive approximations of the Chamfer similarity. The proof uses the propertics of LSH (SimHash) show that for each query point q E Q, the point gets mapped to cluster (p()) that only contains points p E P that are close to g (within e 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 E, > O, and sets Q, C Rdd of unit vectors, and let m = [QI + |P|. Then setting kism 0 loogmm 1) dprož = O ( log( ( m )) Brepe = 1, so that
5

---

dFDE = (m/8)001/)) then in expectation and with probability at least ô we have
NCHAMFER(Q.P))-E
Fdx (P)) & NCCAAFEE(Q.-. P)
Finally, we show that our FDE's give an e-approximate solution Chamfer similarity search, using FDE dimension that depends only logarithmically on the size of the dataset n. Using the fact that our query FDEs are sparse (Lemma A. one can run exact MIPS over the FDEs in time Õ(1Q) n). improving on the brute-force runtime of 0(1Q) max, P((n) for Chamfer similarity search.
Theorem 2.2. Fix any E > O. query Q. and dataset P = {PI..... Pu). where Q C RR and
each P. C R$ is set of unit vectors. Let = IQ1 + maXie[[] PPl. Let Kiss = O logm )
dproj = O log(m) log(m/E)) and Rreps = =0 3a logn) so that dEDE m0(1/5) llog n. Then if
= arg e| (Fg(Q), Fdoc (P.)), with high probability (i.e. 1- - 1/ poly(n)) we have:
NCHAMFER (Q, P:-) E max NCHAMPER(QQ P.) -
sE(n]
Given the query Q. the document P can be recovered in time O (IQ max (d, n) f log( log n)...
Evaluation
In this section, we evaluate our FDEs as 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 (A (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 the MV embeddings produced by the ColBERTv2 model [44] (MIT' License). which have a dimension of d 128 and fixed number [QI 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 dFDE between 1,000-20,000, Furthermore, using product quantization, we show in ($3.2) that the FDBs can be significantly compressed by 32x with minimal quality loss, further increasing the practicality of FDEs.
3.1 Offline Evaluation of FDE Quality
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 dEDE increases, making our method relatively easy to tune. We then show that FDEs more effective method of retrieval than the SV heuristic. Specifically, the FDE method achieves Recall@ 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 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 be found in (SC). All recall curves use single FDE instantiation, since in (SC.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 dFDE- We perform a grid search over FDE parameters Reypa E 5, 10, 15, 20}, Katm E (2, 4, 4,5, 6), dproj E (8, 16, 32, 64), and compute recall on MS MARCO (Figure 3). We find that Pareto optimal parameters are generally achieved by larger Rrops with Keim, dgroj playing a lesser role in improving quality. Specifically, (Rrage, Keim: dpeoj) {(20, 3, 8). (20. 4, (20,
(2, 5, 8). (20, 5, 16)) were all Pareto optimal for their respective dimensions (namely Rrape 28.m d. 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

---

100
077
10.0
30.7
0.3
Sansioe Parttinning Rggi0
0.0
FDE Sinviush Partttaiing Rg1000
FDC Sinllsth Pertteeing Rigodc0
leverdd Center Fartitooing Ri11000
lemment Center Parttorinng Ro038003
Exact ChamteeRigtn
Eaact Chamter Cradt ChamtterRgp000
0.5
Exact Charder Ro220
06
baxt Unorver Aigisd
Exact Charder Rg1000
Beac Charctr RB/0000
10008
15000
20000
15000
Oimaniion
Figure 3: FDE recall vs dimension for varying FDE parameters MS MARCO. Plots show FDE Recall 100, Ik, 10k left right. Recalls@&N for exact Chamfer scoring is shown by dotted lines.
VSMorco
HirponQA
2.00
Dustr
NQ
0.45
cimension
0.90
2350
5120
35240
100
300
200
000
520
300
200
300
400
500
100
200
305
400
500
100
200
300
-00
500
Deculigh
Rocalige
RecallgN
(ocalligh
Figure 4: Comparison of FDE recall versus brute-force search over Chamfer similarity.
quality gains. We also evaluate using k-means method of partitioning instead of SimHash. Specif- ically, we cluster the document embeddings with k-means and set (rx)) to be the index of the nearest centroid to x. We perform grid search over the same parameters (but with k {4, 8, 16, 32, 64) to match B = 2h.).. We find that k-means partitioning offers no quality gains the Pareto Frontier over SimHash, and is often worse. Moreover, FDE construction with k-means is no longer data oblivious. Thus, SimHash is chosen 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 @Recall N, which the fraction of queries for which the Chamfer L-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 mavg 10K) we achieve 95% recall while retrieving only 75 candidates using dFDE 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 this method, for each of the i = I...., 32 query vectors 9i we compute the nearest neighbors Pi. & from the set U.P. of all document token embeddings. To compute & we create an ordered list fi.1..... L1,32, .,.,. where 4, is the document ID containing Pi.i consisting of the 1-nearest neighbors of the queries, then the 2-nearest neighbors, and so on. When re- ranking, 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 over-retrieve to reach 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 brute force search. The FDE method must scan n dFDE floats to compute the k-nearest neighbors. For the SV heuristic, one runs 32 brute force scans over n Mavg vectors in 128 dimensions, where Mang is the average number of embeddings per document (see BB for values of marg). For MS MARCO, where marg 78.8, the SV heuristic searches through 32. 128- 78.8 n floats. This allows for an FDE dimension of dEDE = 322,766 to have comparable cost! We can extend this comparison to fast approximate search suppose that approximate MIPS
7

---

3.0
McHorco
HE4p0004
3.00
0,9r
1.0
00
0.7
5.00
FDC 20465
1-2 cA04
2.5
Rocal
Recal 1gm
Pac
Recial 1gi
Figure 5: FDE retrieval vs SV Heuristic, both with and without document id deduplication.
over n vectors can be accomplished sublinear no time, for some E E (0, 1). Then even in the unrealistic case of e 0, we can still afford an FDE dimension of dYDE 32 128 4096.
The results can be found in Figure We build FDEs once for each dimension, using Ryaps 40, Keim 6, dproj = 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 4096- dimensional FDEs match the recall of the (deduplicated) SV heuristic while retrieving 1.75-3.75x fewer candidates (our Recall@N matches the Recall@ 1. 1.75-3.75.N of the SV heuristic), and 10.5-15x fewer than to the non-deduplicated SV heuristic. For 10240-dimension FDEs, these numbers 2.6-5 x and 20-22.5x x fewer, respectively. For instance. we achieve 80% recall with 60 candidates when dFDE 10240 and 80 candidates when dYDE 4096, but the SV heuristic requires 300 and 1200 candidates (for dedup and non-dedup respectively). See Table 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 at most 0.08-0. 16% for FDEs with 2-10k dimensions.
3.2 Online Implementation and End-to-End Evaluation
We implemented MUVERA, an FDE generation and end-to-end retrieval engine in C++. We discussed FDE generation and various optimizations and their tradeoff's in ($3.1). Next, we discuss how we perform retrieval over the FDEs, and additional optimizations.
Single-Vector MIPS Retrieval using DiskANN. Our dingle-vector retrieval engine uses a scalable implementation [38] of DiN [25] (MIT License), a state-of-the-ar graph-based ANNS algorithm. We build DiN 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 dimensions to one of 256 centers. Thus PQ-256-8 provides 32x compression over storing each dimension using a single float, since each block of 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 1atandard-176)) The machine supports up to 176 hyper- We run latency experiments using 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 Ci...., Ck. setting = Σ5eo, q and Qc = (ci,..., }. Then, after retrieving set of candidate documents with the FDEs, instead of rescoring via CHAMFER Q, P) for each candidate P. we rescore via CHAMFER Qc, P), which runs in time 0(Qcl - IP)), 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 T, we select an arbitrary point E Q. cluster it with all other points g' Q with (q.g)) > r, remove the clustered points and repeat until all points are clustered.
8

---

NQ
MSMarco
Quera
0.38
1.10
0.55
0.30
Racafe
RoufOe
0:55
Raulee
9.56
0.50
0.94
0.50
100
0.7
022
100
1000.0
1000.0
1000.0
0.6
Ball Canving Threshold
Ball Carving Threshold
Ball Corving Threshald
Figure 6: Plots showing the trade-off between the threshold used for ball carving and the end-to-end recall.
Quara
NQ
MARCO
Uncorprosed
PC 295.5
Uscorppessed
PQ 255
PQ 256-2
FQ 10-255-
PQ 2Q-299-2
PQ
PC 330-6
PC 395 16
PQ 296-
PQ 296-2922
PQ--30-0 0
901
PQ-200-
PQ 796.5
PQ-236
0.02
0:98
0.00 0.965
Plots showing the QPS Recall@ 100 for MUVERA subset of the BEIR datasets. The different curves are obtained by using different PQ methods on -imenniimeli FDEs.
Figure 7:
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 r = 0.6, and for all datasets they essentially flat after > 0.7. Thus, for such thresholds incur essentially no quality loss by performing ball carving. Based on these empirical results, we choose the value of r = 0.7 in end-to-end experiments.
In (SC.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 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 average of 5.9 clusters created per query on MS MARCO. This reduces the number of query embeddings by 5.4x, 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.
0.7 threshold provides 25% QPS
QPS vs. Recall. A useful metric for retrieval is the number of queries per second (QPS) a system serve 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 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 32x, but also improves the QPS at the same query beamwidth by up to 20x, while incurring 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 shows that MUVERA achieves essentially equivalent Recall @ k as PLAID (within 0.4%) on MS MARCO, while obtaining up to 1.56x higher recall on other datasets (e.g. HotporQA). We ran PLAID using the recommended settings for their system, which reproduced their recall results for MS MARCO. Compared with PLAID, on

---

Latency in seconds
top each bar latency in (lower better).
Muvera PLAID
0.60-
0.644
0.20-
0.40
0.152
0.187
0.14
0.273
0.31
0.221
0.318
0.0457
0.008
0.0014
0.32
0.34
0.205
0.205
00035
0.0822
0.25
0.00
NO.100
NQ-1000
HorpenGA 100
Hemerr 1000
MS MARCO-100 100
MS MARCO-1080
Querg 100
Quaak Qusa--100 1o0p
SCID0cs-10 100
Sa000s-1100
ArguAne-110 100
Argura 1020
Muvera
The
Recallik (higher better).
PLAID
Recallok
0.904
0.33
0.851
0,902
0,903
0.971
0.955
0.997
0.964
0.998
0.998
0.89
0:966
0.95)
1.0
0.008
0.462
0.481
0.572
0.571
a. 0.347
0.344
0.5
0.0
NG 100100
BiQ 1880
HolporO 100
Hosper 1805
MS MARCO 1800
Quap. 108
Quere 1850
SCDGCS 100
SQDOCS 1000
ArguAra 160
ArguAna- 1009
MS MARCO-
Figure 8: Bar plots showing the latency and Recall @ of MUVERA PLAID on subset of the BEIR datasets.
The x-tick labels formatted as dataset-k; i.e., optimizing for Recall l the given dataset.
average over all 6 datasets and k E {100, 1000}, MUVERA achieves 10% higher Recall k (up to 56% higher), and 90% lower latency (up 5.7 lower).
Importantly, MUVERA has consistently high recall and low latency across all of the datasets that we measure, and method does not require costly parameter tuming to achieve this all of our results use the same -2a40-iimesiioall FDEs that are compressed using PQ with PQ-256-8; the only tuning in our system was pick the first query beam-width over the l that rerank to that obtained recall matching that of PLAID.. AS Figure shows, in cases like NQ and HotpotQA, MUVERA A obtains much higher recall while obtaining lower latency. Given these results, believe distinguishing feature of MUVERA compared to prior multi-vector retrieval systems is that it achieves consistently high recall and low latency across wide variety of datasets with minimal tuning effort.
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 MV representation. We prove that FDE dot products give high-quality approximations to Chamfer similarity ($2.1). Experimentally, we show that FDEs are much more effective proxy for MV similarity, since they require retrieving 2-4x 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.
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, 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, did not study the effect that the average number of embeddings Mavg per document has on retrieval quality of FDEs; this is an interesting direction for future work.
Broader Impacts and Limitations:
10

---

References
[1] Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high- dimensional spaces. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA '2008), pages 343-352, 2008
[2] Rosa I Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine learning, 63:161-182, 2006.
[3] Kubilay Atasu and Thomas Mittelholzer. Linear- complxxy data-paralled earth mover's distance approximations. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 364-373, PMLR, 09-15 Jun 2019.
[4] Vassilis Athitsos and Stan Sclaroff. Estimating 3d hand pose from a cluttered image. In 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. volume 2, pages 11-432. IEEE, 2003.
[5] Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, and Erik Waingarten. Near-linear time algorithm for the chamfer distance. Advances in Neural Information Processing Systems, 36, 2024.
[6] Harry G Barrow, Jay M Tenenbaum, Robert C Bolles, and Helen C Wolf. Parametric correspon- dence and chamfer matching: Two new techniques for image matching. In Proceedings: Image Understanding Workshop, pages 21-27 Science Applications, Inc, 1977.
[7] Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium Foundations of Computer Science (FOCS '1996), 1996.
[8] Moses Charikar. Similarity estimation techniques from rounding algorithms. Proceedings of the thiry-fourth annual ACM symposium Theory of computing, pages 380-388, 2002.
[9] Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, and Erik Waingarten. Streaming euclidean mst to a constant factor. In Proceedings of the 55th Annual ACM Symposium on Theory Computing, STOC 2023, page 156-169, New York. NY, USA, 2023, Association for Computing Machinery.
[10] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional emd and mst. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 222-233, 2022.
[11] Arman Cohan, Sergey Feldman, Beltagy, Doug Downey, and Daniel S Weld. Specter: Document-level representation learning using citation-informed transformers. arXiv preprint arXiv:2004.077 07 180, 2020.
[12] Joshua Engels. Benjamin Coleman, Vihan Lakshman, and Anshumali Shrivastava. Dessert: An efficient algorithm for vector set search with vector set queries. Advances in Neural Information Processing Systems, 36, 2024.
[13] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-49,, 2004.
[14] Haoqiang Fan, Hao Su, and Leonidas Guibas. A point set generation network for 3d object reconstruction from single image. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 605-613, 2017.
[15] Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. white box analysis of colbert. In Advances in Information Retrieval: 43rd European Conference IR Research, ECIR 2021, Virtual Event, March 28 28-April 1, 2021, Proceedings, Part 43, pages 257-263. Springer, 2021.
[16] Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. Match your words! a study of lexical matching in neural information retrieval. In European Conference on Information Retrieval, pages 120-127 Springer, 2022.

---

[17] Luyu Gao. Zhuyun Dai, and Jamie Callan. Coil: Revisit exact lexical match in information retrieval with contextualized inverted list. arXiv preprint arXiv:2104.07186, 2021.
[18] Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, and David Simcha. Quantization based fast inner product search. In Artificial intelligence and statistics, pages 482-490. PMLR, 2016.
[19] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiy Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887-3896. PMLR, 2020.
[20] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing, 8(1):321-350, 2012.
[21] Sebastian Hofstätter, Omar Khattab, Sophia Althammer, Mete Sertkan, and Allan Hanbury. Introducing neural bag of whole-words with colberter: Contextualized late interactions using enhanced reduction. In Proceedings of the s1 ACM International Conference on Information Knowledge Management, pages 737-747, 2022.
[22] Piotr Indyk. Algorithms for dynamic geometrie problems data streams. In Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC '2004), pages 373-380, 2004.
[23] Rajesh Jayaram. Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Massively parallel algorithms for high-dimensional euclidean minimum spanning tree. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 3960-3996. SIAM, 2024.
[24] Rajesh Jayaram, Erik Waingarten, and Tian Zhang. Data-dependent Ish for the earth mover's s distance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
[25] Suhas Jayaram Subramanya. Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-poin -pont nearest neighbor search on single node. Advances in Neural Information Processing Systems, 32, 2019.
[26] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117-128, 2010.
[27] Li Jiang, Shaoshuai Shi, Xiaojuan Qi, and Jiaya Jia, Gal: Geometric adversarial loss for single-view 3d-object reconstruction. In Proceedings of the European conference on computer vision (ECCV), pages 802-816, 2018
[28] Omar Khattab, Christopher Potts, and Matei Zaharia. Baleen: Robust multi-hop reasoning at scale via condensed retrieval. Advances in Neural Information Processing Systems, 34:27670- 27682, 2021.
[29] Omar Khattab and Matei Zaharia. Colbert: Efficient and effective passage search via contextual- ized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pages 39 2020.
[30] Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. From word embeddings to document distances. In International conference on machine learning, pages 957-966. PMLR, 2015.
[31] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, et al. Natural questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics, 2019.
[32] Jinhyuk Lee, Zhuyun Dai, Sai Meher Karthik Duddu, Tao Lei, Iftekhar Naim, Ming-Wer Chang, and Vincent Zhao. Rethinking the role of token retrieval in multi-vector retrieval. Advances in Neural Information Processing Systems, 36, 2024.
[33] Chun-Liang Li, Tomas Simon, Jason Saragih, Barnabás Póezos, and Yaser Sheikh. Lbs autoencoder: Self-supervised fitting of articulated meshes to point clouds. In Proceedingy of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 11967-11976. 2019.
12

---

[34] Yulong Li, Martin Franz, Md Arafat Sultan, Bhavani Iyer, Young-Sur Suk Lee, and Avirup Sil. Learning cross- monssll ir from an english retriever. arXiv preprint arXiv:21 2021.
[35] Weizhe Lin, Jinghong Chen, Jingbiao Mei, Alexandru Coca, and Bill Byme. Fine-grained late- interaction multi-modal retrieval for retrieval augmented visual question answering. Advances in Neural Information Processing Systems, 36, 2024.
[36] Simon Lupart. Thibault Formal, and Stéphane Clinchant. Ms-shift: An analysis of ms marco distribution shifts on neural retrieval. In European Conference on Information Retrieval, pages 636-652, Springer, 2023.
[37] Sean MacAvaney and Nicola Tonellotto. A reproducibility study of plaid. arXiv preprint arXiv:2404. 14989, 2024.
[38] Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Har- sha Vardhan Simhadri, and Yihan Sun. Parlayann: Scalable and deterministic parallel graph- based approximate nearest neighbor search algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, pages 270-285, 2024.
[39] Niklas Muennighoff, Nouamane Tazi, Loic Magne, and Nils Reimers. Mteb: Massive text embedding benchmark. arXiv preprint arXiv:2210.073:1 2022.
[40] Tri Nguyen, Mir Rosenberg, Xia Song. Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. Ms marco: A human-generated machine reading comprehension dataset. 2016.
[41] Ashwin Paranjape, Omar Khattab, Christopher Potts, Matei Zaharia, and Christopher D Manning. Hindsight: Posterior-guider training of retrievers for improved open-ended generation. arXiv preprint arXiv:21 2021.
[42] Yujie Qian, Jinhyuk Lee, Sai Meher Karthik Duddu, Zhuyun Dai, Siddhartha Brahma, Iftekhar Naim, Tao Lei, and Vincent Y Zhao. Multi-vector retrieval sparse alignment. arXiv preprint arXiv:2211.01267, 2022.
[43] Keshav Santhanam, Omar Khattab, Christopher Potts, and Matei Zaharia. Plaid: an efficient engine for late interaction retrieval. In Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pages 1747-1756, 2022.
[44] Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. Colbertv2: Effective and efficient retrieval via lightweight late interaction. arXiv preprint arXiv:2112.01488, 2021.
[45] Erik B Sudderth, Michael I Mandel, William T Freeman, and Alan S Willsky. Visual hand tracking using nonparametric belief propagation. 2004 Conference on Computer Vision and Pattern Recognition Workshop, pages 189-189. IEEE, 2004.
[46] Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. Beir: A heterogenous benchmark for zero-shot evaluation of information retrieval models. arXiv preprint arXiv:2 2021.
[47] Henning Wachsmuth, Shahbaz Syed, and Benno Stein. Retrieval the best counterargument without prior topic knowledge. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 241-251, 2018
[48] Ziyu Wan, Dongdong Chen, Yan Li, Xingguang Yan, Junge Zhang, Yizhou Yu, and Jing Liao. Transductive zero-shot learning with visual structure constraint. Advances in neural information processing systems, 32, 2019.
[49] Xiao Wang, Craig Macdonald, Nicola Tonellotto, and ladh Ounis. Pseudo-relevance feedback for multiple representation dense retrieval. In Proceedings of the 2021 ACM SIGIR International Conference Theory of Information Retrieval, pages 297-306, 2021.
13

---

[50] Xiao Wang, Craig Macdonald, Nicola Tonellotto, and Iadh Ounis. Reproducibility, replicability. and insights into dense rellestepresnnttioonn retrieval models: from colbert to col. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2552-2561, 2023.
[51] Orion Weller, Dawn Lawrie, and Benjamin Van Durme. Nevir: Negation in neural information retrieval. arXiv preprint arXiv:2305.076./ 2023.
[52] David P Woodruff et al. Sketching tool for numerical linear algebra. Foundations and Trends() in Theoretical Computer Science, 10(1-2)11-157, 2014.
[53] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhut- dinov, and Christopher Manning. Hotpotqa: dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv:/809.0900 2018.
[54] Lewei Yao, Runhui Huang, Lu Hou, Guansong Lu, Minzhe Niu, Hang Xu, Xiaodan Liang, Zhenguo Li, Xin Jiang, and Chunjing Xu. Filip: Fine-grained interactive language-image pre-training, arXiv preprint arXiv:2111.0778: 2021.
[55] Jingtao Zhan, Xiaohui Xie, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, and Shaoping Ma. Evaluating interpolation and extrapolation performance neural retrieval models. In Pro- ceedings of the st ACM International Conference on Information Knowledge Management, pages 2486-2496, 2022.
[56] Ye Zhang, Md Mustafizur Rahman, Alex Braylan, Brandon Dang, Heng-Lu Chang, Henna Kim, Quinten McNamara, Aaron Angert, Edward Banner, Vivek Khetan, et Neural information retrieval: A literature review. arXiv preprint arXiv:1611.0679, 2016
14

---

A Missing Proofs from Section 2.1
In 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 kaim aproj. Reeps and sets Q. R., compute F (Q) in time Ty == O (reeps Q[d( + kesm)), and F (P) in time O Rrepe P1 K kgrm). Moreover, (Q) has at most O d doro Rreps) 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 th; R² R4 which requires O[I dddrra Reaps) time to perform the matrix-query products for all repetitions. Next, must compute yi (4) for each [Reeee] Each such value can be compute in d kiam time to multiply the
E Q and repetition
E Rd by the kamm Gaussian vectors. Thus the total running time for this step is (Rraa ( dkkam)) Finally, summing the relevant values into the FDE once (p)()), ()())))))))))))))))))))))))))())
(g) are computed can be done in time. For sparsity, note that only the coordinate blocks in the FDE corresponding to clusters k a repetition with least one q E [Q] with (g) are non-zero, and there can be at most O Recpal)) of these blocks, each of which has ((dpras) coordinates.
The document runtime is similar, except with the additional complexity required carry the fill clusters option. For each repetition, the runtime required to find the closest / to give cluster & O(PI kam), since need to run over all [pl values of (p(p) and check how many bits disagree with k. Thus, the total runtime is O (Rrepal P Blkmm)) O D(Rzeg 2 keim).
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.
Fact A.2 ([2)). Fix e, 8 O. For any > 1 and x, y E Rd let S E Rexd by a matrix of independent entries distributed uniformly over (1,-1}, where I = O(1/e² -log 8-1. Then we have [Sx, Sy)] = (I. y). and moreover with probability at least 1 we have
((SxSS)) (x. < ||||a||2l111
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 the following Lemma.
Lemma A.3 (One-Sided Error Estimator). Fix any sets Q, C Rd un vectors with |Q|+|P| = m.
Then if d dprog. we always have
F (q()). (P)) & NCHAMFEE P)
IQI
Furthermore, for any 8 O. if derog logmmm))) then we have Q (F,(Q),F Fane) (P)) NCHAMPER(Q, P) + e in expectation and with probability at least 1 8.
15

---

Proof. First claim simply follows from the fact that the average of subset of a set of numbers can't be bigger than the maximum number in that set. More formally, we have:
B
[Q] (Q) Faoe (P)) = |Q1
Σ
Σ (g.p)
Pr 8 (k)l
qEQ (p())=
DEP sp()=
1
Σ
max
Pn 4 (k:)
VEEP
(4)
QEQ (p())=
PEP
(p(p)=
Σ 9EQ
max NCHAMFER(Q,
Q
PeEP
pp()==
Which completes the first part of the lemma. For the second part, to analyze the of dprrot d, when inner random projections are used, by applying Fact A.2, firstly we have (<b(p), 1b(4)) = (1, p) for any Q.P E P., and secondly, after union bound over [P| |Q| & m² pairs, have (q. p) (p), (b()) = simultancously for all E Q.p E P. with probability - 6, 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 E, O, and sets Q, P C R of unit vectors, and let m = |Q] + PPl Then setting kaim = log(mó 1) dproj O ( log ())) Rrepe = 1, so that
dFDE (m/8)0(/d) we have
NCHAMMER (Q,
(F,(Q), & NCHIAMFER(,,.. P) +
Q
in expectation, and with probability at least 1 6.
Proof of Theorem 2.1. The upper bound follows from Lemma A.3, it will suffice to prove the lower bound. We first prove the result in the case when there are no random projections sh. and remove this assumption the end of the proof. Note that, by construction, Fş linear mapping so that F, (Q)))= = Eneq F4)), thus
Fd), = E(Fg()) -(F
((x)))) Face(P))
gEQ
So will suffice to prove that
Pr (Fg(g), doc (P))
> max (g. p)
c
(5)
PEP
for q Q. since then, by union bound will hold for all over all q E Q with probability least 1 - =õ, in which case we will have
1
Fale)
>
max
(g. p) -E)
Q
1Q
PEP
(6)
4EQ
NCHAAMFERQ,
which will complete the theorem.
In what follows, for any x. Rd let (x. y) [0, π be the angle between x; y. Now fix any q Q. and let p" = arg max p), and let 0 0(g.p") By construction, there always exists some set of points S c P such that
F (gg(g), F (o))
q:
Σ PES
16

---

Moreover, the RHS of the above equation is always bounded by in magnitude, since it is an average of dot products of normalized vectors q.P gd-1 In particular, there are two cases. In case (A) S is the set of points p with (p()) ((g), and in case (B) S is the single point arg minper (|sp - ((g)llo. where || - yllo denotes the hamming distance between any two bit- strings 2; E {0, 1)Am, and we are interpreting (p)), sp(g) E {0. 1] Sium as such bit-strings. Also let :1:-..: R be the random Gaussian vectors that were drawn define the partition function s. To analyze S, we first prove the following:
Claim A.4. For any q E Q and E P. we have
((g.p)
EB m
Pr [|p(p) s0())ll - heim
Vehiai
<
Proof. Fix any such and for E [Kaml] let Z, be an indicator random variable that indicates the event that 1((g,p) 0) * 1((9).9) > 0). First then note that 1|9(p) pp())ll
kai Zi Now by rotational invariance of Gaussians, for Gaussian vector E R we have Pr (1(1((g,2) 2) 0) + 1( v\ 0)] 0(r.v] for any two vectors x, R It follows that Z; is Bernoulli random variable with E [Z,] ((nw) By a simple application of Hoeffding's inequality, we have
O(g.p)
Kaim
Pr |}p(() -p(())lo Aaim
Veliaim
Pr
Zi
E
Z
Vekaii
1=1
< exp Eδ
(-2e2 (-2ekiat))
m2
where we took Kaim > 1/2 log( m² 28 )/5, which completes the proof.
We now condition on the event Claim A.4 occurring all p E P. which holds with probability at (zd) by a union bound. Call this event and condition on it in what
least [P| [
follows.
Now first suppose that are in (B), and the set S of points which map the cluster (g given by S = {p'} where p' = arg minger (|<(p) - (g()) Firstly, p' = p", then we are done as (Fa Fave P)) r") and 5 follows. Otherwise, by Claim A.4 must have had 10(q.p)) p')-0((,,,2) p²) < VE. Using that the Taylor expansion of cosine is cos(x) = 1- 1==2/2+0((1))
we have
coo((((q, - (oo(0ll.)))ccc(((a''"" & ((e)
Thus
Fsco()) = (q.p')
= cos(0((,)1))
cos(O(g.p")) 0(e)
(8)
max((..)) - 0(e)
pep
which proves the desired statement 5 after a constant factor rescaling ef
Next, suppose we are in case (A) where {p E P (p(p) = <(()) non-empty. this case,
consists of the set of points p with []{((p) sp(g)llo 0. From this, it follows again by Claim A.4
17

---

that (lg.p) VET for any S. Thus, by the same reasoning above, we have
(g) Fooc (P))
cos cos(O(g,pp))
= |
PES
E (1- (1- 0(s))
PES
(9)
((..p') -
PES
max (q, ( pEp
which again proves the desired statement 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 (Fa(1) Fanc (P) < 1 deterministically, the small ((z)) probability of failure (i.e. event that does not hold) above can introduce at most (ss)) & additíve error into the expectation, which is acceptable after constant factor rescaling of E.
Finally, to incorporate projections, by standard consequences of the Johnson Lindenstrauss Lemma (Fact A.2) setting dproj = ( log ") and projecting via random Gaussian or =1 matrix from sb IR + Rxd, for any set S C we have that E (w)()) 2/ [S] Epes p)) = (q, [S| Epes p). and moreover that (q: [ST Epes p) (x)( 20 |ST Epe 1lllll EpEs pll2 + e for all g E Q,PE E P with probability at least 26. Note that ||q/12 1, and by triangle inequality | Epes Plla < [ST Epes llpl|2 1. Thus, letting (Q),,, Fao (P)
be the FDE values without the inner projection
db and F (Q), F& doo (P) be the FDE values with the inner projection sb conditioned on the above follows that
1
F (Q), F (P))
F (F
(4), F (P))
Q
Q
1
(F (g) F Foc (P) =
(10)
Q
1
F
Face (P)) te
Q
Finally, to analyze the expectation, note that since
1 Q
Fg (q. (P))
<
Σ QEQ
(o.()) <
Q
as 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 constant factor rescaling of s.
Equipped with Theorem 2. well the sparsity bounds from Lemma A.I, are now prepared to prove our main theorem on approximate nearest neighbor search under the Chamfer Similarity.
Theorem 2.2. Fix any > O, query Q. and dataset P (Pı,..,, Pa), where C RRd and each P. C Rd is a set of unit vectors. Let m [Q] + max
P.). Then setting ksim = O log doros = O log(m/e) e)) and Rreps = 0 1 log n) so that d = m. 0(1/s) .log n. Then setting Faoc((.)). (P:)), with high probability (i.e. 1/ poly(n)) we have:
arg ma (F (Q), Faoc
NCHAMFER (Q, P:-) > max NCHAMFER Q, P:) - iE(n]
Given the query Q, the document P can be recovered in time O (IQ) max d, n 1 log( m log n).
18

---

Proof of Theorem 2.2. First note, for single repetition, for any subset Pj E D, by Theorem 2.1 we have
E 4 (Q), doc Fe = NCHAMFER(Q..) +
Moreover, as demonsrated in the proof of Theorem 2.1, setting ō = 1/10, we have
1 [2 (F((2). Facc Facc)))Fac(P))))
<
(g)
Foo (Pj))) <
@
QQ
REQ
follows that for each repetition E [Rzepe], letting Fq(Q)', dao ( be the coordinates in the final FDE vectors corresponding to that repetition, the random variable X; Teा (Q) (P)) is bounded in [-1, 1] and has expectation NCHAMFER(44 (Q, (3, = By Chernoff bounds, averaging over Reeps = ( log(n)) repetitions, have
Rases
(Q)(Q), F (Pz)) NCHAMFER(Q, Py) & 2s
(11)
Propa Q
with probability 1/n for any arbitrarily large constant C 1. Note also that Li
Q (Q). (P)) Re Iq (Qq()), (P))) where Fq(Q), Fuce)) are the final
FDEs. We then condition (11) holding for all documents j E [ni], which holds with probability with probability 1/nC-1 by union bound. Conditioned on this, we have
NCHAMFER( Q, P.) >
(Fg(Q),Fal daxc(P:)) 2E
Rzepe QQ)
max sEīn
Rzepa 12) (Fq(Q), F Fove (P;))
(12)
max NCHAMFER 65 Je(n
which completes the proof of the approximation after constant factor scaling e. The runtime bound follows from the runtime required to compute (Q))), which is Rropo + hmm)) 2- d( iz log(m/s) + log m). plus the runtime required to brute force search for the nearest. dot product. Specifically, note that each of the FDE dot products can be computed time pro- portional to the sparsity of (Q))), which is at most ((QQ) Reopa) = 0( log(m/s) log n). Adding these two bounds together yields the desired runtime.
O(Q log
B Additional Dataset Information
In Table we provide further dataset-specific information 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 corpus) will have a total of #Corpus x (Avg # Embeddings per Doc) token embeddings. For even
further details, see the BEIR paper [46].
MS MARCO
HotpotQA
NQ
Quora
SciDocs
ÁrguAna
# Queeries #Corpus Avg Embeddings 78.8
6,980
7,405
3,452
10,000
1,000
1,406
8.84M
5.23M
2,68M
523K
25.6K
8.6K
68.65
100.3
18.28
165.05
154.72
per Doc
Figure 9: Dataset Specific Statistics for the BEIR datasets considered in this paper.
19

---

C Additional Experiments and Plots
In this 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 z-axis for our experiments in Section ($3.1), as well as additional experimental results, such as an evaluation 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 handle duplicates) on most datasets, especially in lower recall regimes. In Table I, we compare how many candidates must be retrieved by SV heuristic, both with and without the deduplication step, as well as by our FDE methods, in order to exceed given recall threshold.
Recall Threshold
SV non-dedup
SV dedup
20k FDE
10k FDE
4k FDE
2k FDE
80%
1200
300
60
60
80
200
85%
2100
400
90
100
200
300
90%
4500
800
200
200
300
800
95%
>10000
2100
700
800
1200
5600
Table 1: FDE retrieval vs SV Heuristic: number of candidates that must be retrieved by each method to exceed given recall on MS MARCO. The first two columns are for the SV non-deduplicated and deduplicated heuristics, respectively, and the remaining four columns are for the FDE retrieved candidates with FDE dimensions (20480, 10240, 4096, 2048), respectively. 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, 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, SeiDoes and ArguAna).
C.1 Variance of FDEs.
Since the FDE generation is randomized process, one natural concern whether there is large variance in the recall quality across different random seeds. Fortunately, 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 (Reepe Kaim dpecs) 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 @ 1 00 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 recall point, compared to the 80-95% range of recall values. Note that Recall 1000 had roughly twice as small standard deviation Recall 100.
FDE params (Ryeps Katnay dproj)
(20, 5, 32)
(20, 5, 16)
(20, 4, 16)
(20, 4, 8)
FDE Dimension
20480
10240
5120
2560
Recall @ 100
83,68
82.82
80.46
77.75
Standard Deviation
0.19
0.27
0.29
0.17
Recall @ 1000
95.37
94.88
93.67
91.85
Standard Deviation
0.08
0.11
0.16
0.12
Table 2: Variance FDE Recall Quality on MS MARCO.
20

---

MSMarco
HotpotQA
1.0
0.9
1.00
0.8
0.95
Recall
0.8
0.7
0.90
0.7
0.6
0.85
0.5
0.5
0.80
w/ Dedup
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
FDE 20480
NQ
SciDocs
ArguAna
1.0
0.8
1.0
FDE 4096
FDE 2048
0.7
0.9
0.9
Recall
0.8
0.7
0.4
0.6
0.6
1000
2000
3000
5000
1000
2000
3000
4000
5000
1000
4000
5000
Recall@N
Recali@N
Figure 10: FDE retrieval SV Heuristic, Recall @ 100-5000
MSMarco
HotpotQA
Quora
0.8
0.95
0.90
Recail
0.7
0.6
0.5
0.4
0.5
0.75
SV
0.3
w/ Dedup
FDE
NO
SciDocs
ArguAna
FDE 10240
1.0
FDE
0.9
FDE 2048
0.9
0.8
Recall
0.8
0.3
0.7
0.6
0.5
0.6
0.4
0.5
0.0
0.3
100
200
300
500
100
200
300
400
500
100
200
300
400
500
Recall@N
Recall@N
Recall@N
Figure 1 11: FDE retrieval vs SV Heuristic, Recall @55-50
Experiment
w/o projection
w/ projection
w/o projection
w/ projection
Dimension
2460
2460
5120
5120
Recall @ T00
77.71
78.82
80.37
83.35
Recall@ @ 1000
91.91
91.62
93.55
94.83
Recall 10000
97.52
96.64
98.07
98.33
Table 3: Recall Quality of Final Projection based FDEs with deDe E {2460, 5120)
21

---

MSMarco
HotpotQA
SciDocs
1.0
1.0
1.0
0.9
0.9
0.9
Recall
0.8
0.8
0.7
0.7
0.7
0.5
0.5
0.5
FDE dimension
100
200
300
400
500
100
200
300
400
500
5
100
200
300
500
1280
ArguAna
1.00
1.0
1.00
5120
10240
0.99
0.95
Recall
0.0
0.90
0.6
0.96
500
Recall@N
Recall@N
Recall@N
Figure 12: Comparison of FDE recall with respect to the most similar point under Chamfer.
Experiment
w/o projection
w/ projection
w/o projection
w/ projection
Dimension
I0240
I0240
20480
20480
Recall @ 100
82.31
85.15
83.36
86.00
Recall@ 1000
94.91
95.68
95.58
95.95
Recall @ 10000
98.76
98.93
98.95
99.17
Table 4: Recall Quality of Final Projection based FDEs with dFDE E {10240, 20480}
(10240,00480)
C.2 Comparison to Final Projections.
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 in- ner projections are: namely, via multiplication by a random +1 matrix. We choose four tar- get dimensions, dEDE E {2460, 5120, 10240, 20480), and choose the Pareto optimal parame- ters (Rrope, hiim dpros) from the grid search without final projections in Section 3.1, which are (20, 4, 8). (20, 8), (20, 5, 16), (20. 32). We then build large dimensional FDE with the parame- ters (Rrepa, kimm dpraj) = (40, 6, 128). Here, since d = dpraj, we do not use any inner projections a single random final projection to reduce the dimensionality when constructing the FDE. We then 3277600 down to each of the above target dimensions dFDE- The of this FDE from Prege 2 ddproj
results are show in Tables 3 and 4. Notice that incorporating final projections can have 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 dimessima FDE, where the Recall @ 100 only improved by 1.1%, and the Recall 1000 was actually lower bound 0.3%.
C.3 Ball Carving
Continuing our discussion from Section 3.2, we show that ball- 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 Qc, 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 simple "textbook" k-means based quantizer. Recall that AH-C-G means that each consecutive group of G dimensions represented by C centers. We train the quantizer by: (1) taking for each group of dimensions the coordinates
22

---

Por Core Charritr Camputations Per Second
Chamfer Throughput MS MARCO
65000
Setting
50000
10000
23000
30000
25000
20000
15000
0.4
0.8
Ball Carving Threshold
Figure 13: Per-Core Re-ranking QPS versus Ball Carving Threshold, on MS MARCO dataset.
Argufwa
SCHO0CS
Quaa
100
PG 395.5
Bacongressed
30T
Usconpessed
PQ 796
PG 795
790
7.55
700
PQ 2964
PQ-255-11 255-1 16
PQ 2904
PQ-255-15
PG 256-4
PQ-256-15
Roc
Recal
Recal
Himpor@A
30'
Lecompraaed
PG-23555
Uncompanaeed
PS 230-5
PQ-220--2
12-235-- PQ 795 16
PQ 795 2
P1) 3954
PC 705.0
PC 205-39 16
P4 2904
Pq 796
PG 320 12
PG 755
301
PQ 200
PQ 700-
Recaltitin
Rocal 111
Recalt1100
Figure 14: Plots showing the QPS vs. Recall@100 for MUVERA on the BEIR datasets we evaluate in this paper. The different curves are obtained by using different PQ methods on 10240-dimensional FDEs.
of a sample of most 100,000 vectors from the dataset, and (2) running k-means on this sample using k = C = 256 centers until convergence. Given a vector x E R2, we can split a into d/G blocks of coordinates T())..... ((d/G) E RC each of size G. The block ((() can be compressed by representing Z(,) by the index of the centroid from the i-th group that is nearest to ((t)- Since there are 256 centroids per group, each block (()) can then be represented by a single byte.
Results 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 5x 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 percent. Since our retrieval engine works by over-vetgi 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,
23

---

ArguAra
SCIDOCS
Quen
327
Uncorpoord
FGC 395.5
Uacompreood
2962
14P
256-2622
296-
256-
1.90
6.00
0.50
0.45
0.56
NO
HerporQA
MS MARCO
307
80
JP
5.50
85
0.00
16
0.5 66
07
0.5 0.53
0.55
5:00
3.16
Recal
Figure 15: Plots showing the QPS vs. Recall @ 1000 for MUVERA on the BEIR datasets we evaluate in this paper. The different curves are obtained by using different PQ methods on 10240-dimensional FDEs.
with PQ-256-16 16 (the most compressed and memory-effiiiet 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.
24

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
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 separate "Limitations" section in their paper.
The paper should point out any strong ussumptions 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 faimess.
25

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
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 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 Section A, with ideas 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 cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Ye]]
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-memont 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.
the paper includes experiments, a No answer to this question will not 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 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 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 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 replicate the results, access to a hosted model (c.g., g., in the case
26

---

of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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 proprictary codebase, preventing us from directly releasing it. As described in Section 3.2, we plan publish 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 NeurlPS code and data submission guidelines (https://nips.co/ for more details.
http:/guide///odduuumiiite
While we encourage the release of code and data, we understand that this might 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 new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //mppa.cc/pbblleee http:////w.ccggeeeee/o/eetbbbaaa
hotaes//oooSabbbmioooooiiig for more details.
The authors should provide instructions 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. only 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) recommended, but including URLs to data and code permitted.
27

---

6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e-g., data splits, hyper- parameters, 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 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We run detailed variance experiments in the supplementary in Appendix C.I, 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 include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, 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.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 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 range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
28

---

Justification: For all our online (latency) experiments, we state the exact hardware and compute resources we used 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 henchmarking), and therefore can 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 well 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 failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:://wwarriisspppppppeceeeaae
Answer: [Yes]
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. 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 standalone section at the end of the paper in Section 4. In essence, since work is solely multi-vector retrieval, unlikely to have any direct path to negative applications, and we diseuss this fact in the Broader Impacts section.
about improving the efficiency of
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.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 that 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Our paper proposes 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.
Justification:
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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The authors and sources of all six BEIR datasets that were used in this paper are cited, as well the ColBERTv2 model that used 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: 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.
Justification:
Guidelines:
The answer NA means that the paper does not 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 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.
30

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode. como/oo/////o/// comdsttasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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 the datasct/code/moodll 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 used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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 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 contribu- tion 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.
15. 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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: crowdsoureing nor research with human subjects with used this paper.
Guidelines:
31

---

The answer NA means that the paper does not involve crowdsoureing nor research with 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.
32


Reviews:
[{"review_id": "gYRtBTzwDL", "reviewer": "Reviewer_4i1U", "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.", "questions": "### Q1: The index size of MUVERA\nAs 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.\n- (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?\n- (b) What's the memory usage and index size for stage 1 and stage 2, respectively?\n\n### Q2: Why do MUVERA has sub-optimal performance, compared to PLAID, on the MS-Marco dataset? \n- (a) Is it because of using data-agnostic partitioning functions (SimHash), making the approximation error of FDE larger?\n- (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?\n\n### Other minor comments\n- (a) In Figure 1 caption, there is a typo: \"comapred\" => \"compared\"\n- (b) At Line 133: \"vectors that are closer are more are more likely to...\" => there seems to be some repeatedly wording\n- (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": "To my knowledge, there's no potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposal of Fixed Dimensional Encodings (FDEs) such that its inner product approximate the multi-vector (MV) similarity is novel and interesting\n- The authors also provide strong theoretical guarantee under $\\epsilon$-approximation to the true MV similarity\n- Promising empirical results that significantly reduce the latency on most BEIR datasets compared to PLAID", "weaknesses": "Here are the summarized version. See detailed comments/questions in the next Section.\n- The index size of MUVERA framework can be quite large\n- MUVERA has sub-optimal performance on the MS-Marco dataset\n- no released code", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer. \n\n> Q1(a): \n\nWe first clarify questions about the index size of MUVERA. The reviewer is correct that we need to store both (some representation of) the FDE’s and original multi-vector (MV) representations, however we do not need to fully store either of them. Specifically, we can use the same product quantization for the original MV representations that we use for the FDE’s. Since the focus of the paper was on latency (and not necessarily space) and the new FDE method, we did not run our end-to-end evaluations with the compressed MV representations when rescoring. However, doing so would (1) speed up rescoring (since asymmetric PQ scoring is up to an order of magnitude faster than scoring the uncompressed vectors) and (2) result in negligible quality loss. For concrete numbers on (2), we found that using PQ256-2 (i.e. 8x compression) on the original 128-d vectors resulting in *no downstream quality loss* in the recall for Chamfer scoring (i.e. uncompressed R@100 = 91.49 vs compressed = 91.63, or 98.44 uncompressed vs 98.47 compressed for R@1k). If we compress using PQ256-4 (16x compression), we see very negligible quality loss (the recall@N is 91.1 and 98.38 for N=100,1000 respectively). Also note that PLAID and ColBERTv2 also store compressed versions of the original MV embeddings (via centroids + small residual), which could easily be used for rescoring in our case as well.\n\n> Q1(b): \n\nfor concrete numbers, when using 10k dimensional FDE’s on MS MARCO (which originally has an average of 78.8*128 = 10086 floats per MV representation), we used PQ256-8 (as reported in the paper) to compress the vectors by 32x, and the full index size is 11 GB (instead of 340GB to store the uncompressed FDE’s). For the original multi-vector representations, the uncompressed index size is about 340 GB on disk. Using PQ256-4 we reduce it to 42GB, and using PQ256-8 it goes down to 21 GB (with negligible quality loss as described above). Thus the total index size for stages (1)+(2) would be 11 + 21 = 32 GB for MS Marco, which is more than a 10x compression from the original vectors, and comparable to PLAID’s index (21.6GB). \n\n> Q2: \n\nWe first want to emphasize (1) that we outperform (sometimes significantly) PLAID on all 5 other datasets we studied, in terms of both latency (and sometimes recall too), and (2) PLAID only marginally outperforms our method on MS MARCO. As discussed in the paper, PLAID was highly optimized for MS MARCO due to the prevalence of that dataset, and its parameters were likely overfit. Quoting from a recent reproducibility study of PLAID (https://arxiv.org/pdf/2404.14989): “PLAID’s Pareto frontier is a patchwork of parameter settings; changing one parameter without corresponding changes to the others can result in slower retrieval with no change to effectiveness.” In contrast, using one single set of parameters for all datasets, we get strong results across the board with MUVERA. We also want to emphasize that PLAID was the third in a series of papers (ColBERT, ColBERTv2, PLAID) which attempted to highly optimize the SV Heuristic. MUVERA, on the other hand, is the first paper on the FDE-based approach for MV retrieval, and thus has not seen the same level of optimization. We believe the fact that we match (and often exceed) PLAID on many datasets with this new approach without heavy systems optimization is a strong benefit of our work.\n\n> Q2(a) + (b): \n\nWith regards to Simhash vs. K-means: As shown in Figure 3 (the grid-search), SimHash outperforms k-means on MS MARCO for every parameter range on the pareto frontier. The reason for this is as follows: because we need the FDE’s to be small dimensional, we cannot set the number of partitions B to be too large, so we often use B = {16,32,64}. For such small values of B, you cannot hope to capture the global behavior of a dataset of 8.8M * 77.8 ~ 684M vectors in MS MARCO. Thus, using only <100 centers from k-means on nearly a billion vectors will give very little information about any individual datapoint’s MV representation (note we cannot run a different k-means on each document’s MV representation, since the partition needs to be the same for all points!). Thus, data dependent techniques will not help much here. Instead, SimHash likely performs better because it provably is an LSH and gives good approximate partitions (unlike k-means, which has no theoretical guarantees) for *all* points in the dataset. With regards to the question about skew in the dataset – the data would have to be incredibly skewed (i.e. tightly concentrated around 100 clusters) for k-means to work well. Additionally, each MV representation would have to be spread out over the different clusters (otherwise the partition would not split it into smaller parts). \n\n> “(c) In Figure 2, the legend…’ \n\nThis is a very good catch! We thank the reviewer for finding this mistake in the diagram, as well as the other typos mentioned. We will fix them right away.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pJ5EG8NhjE", "reviewer": "Reviewer_Egyf", "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.", "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": "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?", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The formulation of the problem and the theoretical proofs are the strength of the work. The experimentation has been done on the obligatory BEIR benchmark datasets. Comparison has been made to one other approach (PLAID).", "weaknesses": "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. \n\nIt is difficult to reproduce this work from the level of detail provided. A block diagram illustrating the overall steps would be useful.\n\nThere are typos in the draft so a good spell check is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer. \n\n> “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.”\n\nWe would first like to emphasize that multi-vector models are a fairly new technique which have attracted considerable attention in the last few years, especially in the last 2 years, with many papers being published on the topic at each major conference (see the large list of references in the paper for a subset of these works).  Thus, it does not seem to be the case that multi-vector models are outdated in the current LLM era.\n \nFurthermore, while LLMs have shown amazing results in generative tasks, they are not really strong for information retrieval tasks out of the box and, for example, using standard techniques such as special token pooling or average pooling on top of LLMs for information retrieval from large corpora of text doesn’t match up with even older and simpler semantic encoder approaches. As a result, a contrastive loss based tuning is applied to embeddings pooled from LLMs to make them useful for information retrieval (e.g. Sentence T5, Gecko). Multi-Vector training over LLMs is an even more recent and active field of research that has been challenging researchers in academia and industry both on the modeling and on the efficiency worlds (e.g. XTR, ALIGNER, ColBERT, ColBERTer, ColBERTv2). \n\nFinally, we emphasize that the goal of our work (like PLAID) is to design a more practically- and theoretically-efficient method for multi-vector retrieval. We do not focus on modeling aspects, or comparing multi-vector with other retrieval methods such as SPLADE or other single-vector methods. Such comparisons have already been considered extensively in the literature. \n\n> “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.”\n\nWe would like to emphasize that these latency experiments were run on a single core, as is standard practice in the line of IR papers our work contributes to (ColBERT, ColBERTv2, PLAID). In commercial settings, queries are typically run using more cores, and the queries are distributed across multiple machines resulting in significantly faster searches. We focused on single core evaluation as this is the standard methodology for measuring latency in the information retrieval literature (e.g., PLAID and other IR papers all use single core measurements when reporting latency).\n\n> “A block diagram illustrating the overall steps would be useful.”\n\nWe include block diagrams of the overall steps of our algorithm in Figure 1; if the reviewer has additional suggestions on how to improve our figure we would be happy to incorporate them.\n\n\n> “The fact that LSH preserves nearness is known. How does adding product quantization alter this ability?”\n\nFirstly, we would like to point out that the product quantization is being done on top of the FDEs, not on the original vectors before they are added to the FDEs. Since LSH is only used to decide how to add initial vectors to the FDEs, product quantization does not interact with the LSH at all in this way. Nevertheless, for completeness we remark that even if we did do PQ first before applying LSH, the theoretical and practical guarantees of LSH would still hold. This is because PQ approximates the original vector by a very nearby vector (which is represented in compressed form), therefore preserving nearness to the original vector. So even if PQ was applied before LSH, the guarantees of LSH would still apply. \n\n\n> “Does this technique allow for vector search using the compressed representation or the vectors need to be decompressed back before similarity search?”\n\nYes, the vector search and scoring is done using the compressed representations. This is one of the main benefits of product quantization – you can score similarity even faster than a fixed dot product using asymmetric scoring – this is a standard technique in similarity search.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wz3KYIpL3M", "reviewer": "Reviewer_7tYU", "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.", "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.\n\nWhat are the specific challenges encountered when implementing FDEs in real-world systems, particularly concerning maintaining the balance between efficiency and retrieval accuracy?\n\nTuning parameter W in this work: \"The only tuning knob in our system is W; increasing W increases the number of candidates\n298 retrieved by MUVERA, which improves the recall\" Can this be pre-determined or you can use a specific algorithm to decide it?", "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Novelty and generalizability: by introducing Fixed Dimensional Encodings (FDEs) in MUVERA, which compress multi-vector data into a single vector. This concept is innovative as it allows for applications of single-vector retrieval techniques, such as MIPS, to multi-vector problems. And I can foresee how this work is generalizable to other tasks and other datasets.\n\nComprehensive experiment: this experiment fully compared the state-of-the-art techniques with careful experiment settings, as well as good methodology.", "weaknesses": "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We respond now to the specific questions of the reviewer. \n\n> “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.”\n\nWe note that the cost of FDE generation is only incurred at index time, which can be done offline. Furthermore, the cost of generating an FDE from the multivector representation is linear in the size of the multivector representation, where the complexity scales linearly with the number of repetitions performed. We note that our latency measurements also include the cost of generating the FDE from the query’s multivector representation, and that the time spent on this step is less than 1% of the overall query time. Also note, with regards to dynamic updates, that the construction of FDE’s are data-oblivious, and therefore are easy to generate and maintain in a dynamic setting.\n\n\n> “Robustness of MUVERA across different types of retrieval tasks and its effectiveness in different domains (e.g., legal documents versus scientific articles)”\n\nWe note that the BEIR retrieval benchmarks that we evaluate on, which are standard in the IR literature, are diverse, and include a mix of scientific documents, web queries, quora QA, and other types of domains. In this paper, we chose to focus on the same (diverse) set of datasets used in prior work on multivector representations.\n\n> “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.”\n\nWe agree with the reviewer that the relationship between FDE dimension and accuracy is the main trade-off that we optimize in this work. We further leverage compression techniques like product quantization to enable using higher-dimensional FDEs while keeping the index size for the FDEs moderately sized. Another trade-off that we explored is the relationship between the number of query embeddings and the search latency (via ball-carving) —to the best of our knowledge our work is the first to identify this relationship and we believe it may be of independent interest and importance in future work on multivector systems.\n\n> “What are the specific challenges encountered when implementing FDEs in real-world systems, particularly concerning maintaining the balance between efficiency and retrieval accuracy?”\n\nThe main challenge is to tune the dimensionality of the FDEs to achieve a desired level of accuracy while bounding the space usage of the index. Thanks to the strong theoretical properties of FDEs, our implementation of FDEs is robust to specific choices in the FDE design space such as the type of partitioning used (as illustrated in Figure 3). After fixing a dimension that provides suitable accuracy, the next major challenge is to tune the quantization level to keep the index size manageable—as we show in the paper FDEs are remarkably robust to quite aggressive quantization, which enables the index size of MUVERA to be comparable to highly-engineered systems such as PLAID.\n\n> “Tuning W”\n\nW is a parameter that the user needs to tune to achieve a suitable level of recall—we note that this is standard practice in IR systems that are based on graph-based approximate nearest neighbor search. Understanding how to automatically set W to achieve a given level of recall seems to be equivalent to obtaining provable guarantees for these ANNS methods which is a major open question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QkWrL9cQXn", "reviewer": "Reviewer_uq8U", "summary": "The paper proposes a method of speeding up text retrieval approximating ColBERT multi-vector ranker with very high dimensional single vector using projections. \n\nAuthors 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.", "questions": "I'd like the authors to address both points of weaknesses.", "limitations": "The approach is limited to multi-vector ranking as the function.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper is relatively easy to follow (though using  many acronyms like SV, MV, FDE makes it harder)\n\n* The approach is more efficient at retrieval compared to the SV heuristic baseline\n\n* Authors show that the method does not require much parameter tuning to achieve results comparable to PLAID.", "weaknesses": "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. \n\n2) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions about the paper. Below, we address both points of weakness mentioned by the reviewer. \n\n> W1: \n\nWe thank the reviewer for the reference to this paper. Using a re-ranker or general similarity metric in the graph Beam Search is an interesting approach, which has not been considered by any of the prior extensive literature on multi-vector models and retrieval that we know of. One important point to note is that scoring in the graph search becomes significantly more expensive when the re-ranking similarity is used (Chamfer for us). In contrast, our method uses heavily quantized vectors in the search (compressed by 32x), so that scoring the dot product between two 5k-dimensional FDE’s can be done in roughly the same time as the dot product between two 5000/32 ~ 150-dimensional vectors of floats, which is significantly faster than computing Chamfer similarity (which requires a (32 x 128) x (128 x ~78) matrix product). Furthermore, our approach is based on provable theoretical bounds, whereas it is not clear that searching directly with Chamfer similarity would work in graph based approaches (due to the non-metric aspects of the similarity). \n\n> W2: \n\nAs discussed in the global author response, we would like to emphasize that the focus of our paper is to design an improved standalone retrieval algorithm for multi-vector databases. This is exactly the same goal as the PLAID paper. Thus the reviewer’s concern would apply equally to the (highly-successful) PLAID paper, whose retrieval approach is purely based on the multi-vector representations. \n\nTherefore, like PLAID, we assume we are already given as input a multi-vector database, and we need to find the approximate nearest neighbors under the Chamfer Similarity for the MV embeddings in that dataset. Thus, training different MV models, or comparing with other SV models, such as those distilled from a re-ranker, are both out of the scope of the current paper. We remark that the comparison of MV models versus other methods of retrieval have been extensively evaluated in the prior literature on multi-vector retrieval, and the continued extensive research on multi-vector models and retrieval is testament to the power of multi-vector models.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DgVOYkkK7l", "reviewer": "Reviewer_b2ZE", "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.", "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. \n\nq2. 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": "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.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "s1. Simple yet effective idea that seems to work on a variety of datasets. \ns2. Well written, and experiments are well conducted.", "weaknesses": "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. \n\nw2. 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. \n\nw3. there is no mention of how far from ideal (i.e, ColbertV2 performance) is the proposed model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments and suggestions. We reply to the main questions and concerns below, and attempt to clarify several points.\n\n> W1: “SimHash theory focuses on EMD minimisation while the focus here is on Chamfer similarity maximisation”.\n\nWe would like to point out that this is not accurate. SimHash as a Locality Sensitive Hash (LSH) function dates back to the paper “Similarity Estimation Techniques from Rounding\nAlgorithms” (Charikar, STOC ‘02), where it is used to estimate the cosine similarity between single vectors. In fact, to our knowledge SimHash has not been previously used for theoretical guarantees for EMD in any work. Instead, theoretical results for sketching EMD, such as the seminal “Algorithms for Dynamic Geometric Problems over Data Streams” (Indyk STOC ‘04) or “Earth Mover Distance over High-Dimensional Spaces” (Andoni, Indyk, Krauthgamer SODA ‘08) use L1 distance LSH’s, which are based on random hypergrid shifts, instead of SimHash. However, if the vectors are normalized (as they are for us) then dot product similarity and cosine similarity are the same. This is why we use SimHash for our theoretical (and practical) algorithm, because Chamfer similarity is an aggregate over the max dot product / cosine similarity of each individual vector. \n\n> “So, it would be good detail the theory further.”\n\nCould you please clarify what part of the theory you would like to see be explained further so that we can do so? Note that our theorem proves an eps-approximation of the Chamfer similarity with the FDE dot product, which is essentially the best result one could hope for in a reduction from Chamfer similarity to dot-product similarity. Our method for embedding a set of vectors into a single vector is novel, and has not been used in prior work. \n\n> Q1: \n\nFirstly, we emphasize that the theoretical bound in our paper (Theorem 2.1) applies to the Chamfer Similarity, which is exactly the similarity considered in the rest of the paper. We reiterate that SimHash itself is a Locality Sensitive Hash function for cosine similarity as described above, not for EMD. Thus, there is no direct connection between our theoretical results and known sketching techniques for EMD. The only similarity to sketching techniques for EMD, which is mentioned in the paper, is that sketches for EMD also take the approach of embedding a set of vectors into a single vector using LSH, but the approach for doing so is dramatically different due to the significant differences between EMD and Chamfer (e.g., Chamfer is asymmetric and has no matching constraint). \n\n> “-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. “\n\nWhile the usage of centroids for the construction of the document-side FDE’s is important, it is not the key innovation in our paper. Specifically, the goal of our paper is not to avoid a O(n^2) similarity computation (where n is the size of the query set), but rather to provably embed Chamfer Similarity into dot-product similarity. SimHash is used as a method to turn a multi-vector similarity (where different vectors can match with each other) to a single vector similarity, which fixes the ordering in which the coordinates align. The key idea is to use SimHash to partition the space so that close points always end up in the same bucket, and therefore the same block of coordinates and can be matched. For the theory, the centroid used in the document FDE could have been equivalently replaced with any point from the document that landed in that partition and the theoretical bounds would still apply. Another key insight novel to this work is the “fill_empty_partition” method, which assigns the nearest document point to any empty cluster to ensure that increasing the number of buckets does not decrease quality. \n\n\n> W2\n\nThe dataset size alone does not explain the performance of PLAID vs MUVERA on MS-MARCO, because note that MUVERA significantly outperforms PLAID on HotpotQA (5.2M documents) and NQ (2.7M documents) which are both on the same order of magnitude as MS-Marco (8.8M Documents). Instead, as discussed in the paper, note that PLAID was highly optimized for MS Marco, and was the culmination of multiple papers (ColBERT, ColBERTv2, PLAID), that successively optimized retrieval on the MS MARCO dataset. Our method, on the other hand, is not fine-tuned in any way for MS MARCO, and the same parameters achieve good results on all of our datasets without re-tuning.  With regards to recall@k, in our latency experiments we set our beam width so that our recall matches the recall of PLAID, so that we can primarily compare the latency at a given recall. The goal in these experiments was not to outperform PLAID’s recall, but rather to outperform it in latency at a fixed recall.\n\n\n> W3: “there is no mention of how far from ideal (i.e, ColbertV2 performance) is the proposed model?”\n\nWe 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. The main insight from this figure is that one can over-retrieve with FDE’s and then re-rank to obtain near-ideal or ideal performance (i.e. matching ColbertV2) by using an FDE with recall value (given by the dots) above the corresponding line in the plot. We do this in our end-to-end experiments, where we achieve, for instance, where we obtain 90.2 R@100 and 97.1 R@1k for MS MARCO (Figure 7), which can be compared to 91.4 and 98.3 for ColBERTv2 (as reported in Figure 3 and also in the PLAID paper). Interpretation of Figure 3 is further discussed in our response to reviewer Z5yi.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7qBcIYzaZU", "reviewer": "Reviewer_Z5yi", "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.", "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)?\n\n**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? \n\n**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": "NA", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**S1**: I really like the MIPS approximation construction for MaxSim in Section 2. While the techniques used are not that novel (e.g., Section 2 heavily reminds me of the classical AND- and OR- constructions on top of LSH etc.), being able to reduce MaxSim to MIPS is likely of significant interest to many researchers in NLP and vector search community.\n\n**S2**: Reducing MaxSim to MIPS enables many classical optimizations for MIPS to be applied incl PQ, RP (line 177-180) etc, likely significantly improving the usability and applicability of ColBERT-style approaches. \n\n**S3**: MaxSim similarity (and related setting under late-interaction settings) is an important topic in NLP, as inner products have been proven to be suboptimal for similarity search, especially when we are interested in Recall@K for small Ks (e.g., 10s-50s).", "weaknesses": "**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).\n- 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?\n- Additionally, to achieve the ~.84 recall, FDE encodings already used 20K floats vs 10,087 in MS MACRO multi-vector baselines per Fig. 3...\n\n**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?\n\n**W3**: Writing could be improved.\n- 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. \n- 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). \n- Section 3: consider removing codebase/dataset licenses (CC BY-SA MIT etc.) as most readers may not find them useful.\n- 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.\n- Typos: Line 132-133 are more are more likely to land in -> are more likely to land in\n\t\n\n**References**:\n- [1] Ren et al. PAIR: Leveraging Passage-Centric Similarity Relation for Improving Dense Passage Retrieval. ACL 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed comments and suggestions. We reply to the main questions and concerns below.\n\n> W1: \n\nWe first note that the FDE technique, like the SV Heuristic, is an approach for multi-vector retrieval that must be followed by a re-ranking step with the exact Chamfer similarity. Therefore, the raw recall of the FDE method should not be compared to the brute-force ColbertV2 recall (or to other dense retrieval baselines), but rather to other alternative methods for MV over-retrieval. The primary such alternative (used in PLAID and others) is the SV Heuristic, and we show that FDE’s are significantly more efficient than this method by a factor of 2.6-5x. The message of Figure 3 is that by using a (e.g.) 2.5k dimensional FDE, retrieving 1000 candidates and reranking, one can obtain near-optimal recall@100 with respect to the brute force Chamfer (see Figure 3, middle, at the point where the FDE pareto curve passes the red “Exact Chamfer R@100” line). In contrast, the SV heuristic needs to retrieve many more (2k-5k) candidates to achieve the same recall after reranking.\n\n> “MaxSim+FDE underperform dense retrieval baselines.”\n\nWe emphasize again that our model is *not* returning the 100 candidates retrieved by the FDE. Instead, it would retrieve more candidates, say 500 or 1000, rerank them with Chamfer, and output the top-100 after reranking. This gives us significantly better R@100 than 0.84, for instance, in Figure 7, in our end-to-end evaluation, we achieve .902 R@100 and 0.971 R@1000 on MS Marco, both of which are much closer to the brute-force ColBERTv2 recall (within 1-2%). Also note that this matches the recall obtained by PLAID in those experiments. Also note that PLAID (which uses the SV heuristic for initial retrieval) must also perform the same over-retrieval and reranking steps. \n\n> “Additionally, to achieve the ~.84 recall, FDE encodings already used 20K floats vs 10,087 in MS MACRO multi-vector baselines…”\n\nThe same above point about reranking applies to this comment as well. Specifically, if 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, which attains .855 R@1000 (shown in Figure 3), retrieve 1000 candidates, and rerank to output the top 100. This FDE would then be 10x smaller than the 10k floats used in the MV baseline. Alternatively, we could use our 4k dimensional FDE’s, which achieve 0.88 Recall@500, and retrieve 500 and re-rank to get roughly the same result (if not better). \n\nWith regards to the choice of k used in our Recall@k experiments, we point out that the ColBERT paper also studied similar values of k, namely (50,200,1000), as well as the PLAID paper (100,1k). Since 100,1k were the metrics considered by PLAID, our primary baseline, our end-to-end recall results focused on the same values, although we would be happy to add additional points of comparison at low recall ranges.  \n\n> W2 + Q2: \n\nWith regards to using product quantization in baselines like PLAID or ColBERTv2, we point out that those papers *extensively* utilize quantization methods in their algorithm already. Specifically, the ColBERTv2 retriever compresses points by representing each point by a nearby centroid plus a compressed residual (1-2 bits per coordinate), where the centroids are sampled from the dataset in pre-processing. PLAID, which is built on top of ColBERTv2, also uses the same compression scheme with additional optimizations. Thus, these methods crucially use complex and highly tailored quantization methods. One of our main contributions is to show that an out-of-the-box textbook product quantization method can be used to achieve similar results when applied to FDE’s. \n\n> “how much throughput gains are due to PQs/RPs vs the particular construction of FDEs proposed in this paper?”\n\nIn Figures 14 and 15 we address exactly this question, by plotting Recall vs QPS curves for different datasets and different PQ methods, including uncompressed methods. The figure shows that using PQ gives significant throughput gains, which are needed to be competitive with PLAID (which, as discussed above, also extensively uses quantization techniques).\n\n> W3: \n\nWe greatly appreciate the suggestions for improving the writing, and will be sure to incorporate them.\n\n> Q1:  \n\nAs discussed above, we compare FDE’s without any reranking brute force ColBERTv2 in Figure 3, for k=100 and 1000, as these were the Recall@K metrics considered in the PLAID paper. We will add additional experiments for smaller k to the paper as well. Since our work focuses on designing a standalone retrieval algorithm for MV models, we do not compare to IR methods (such as SV dense retrievers).\n\n> Q3: \n\nThis is a fantastic question, and addressing it is a key contribution of our work. Specifically, we introduce the method “fill_empty_clusters” on Page 5 (see 166-180) to solve this problem, which ensures that at least one document vector maps to every cluster. As a result, there are no empty clusters on the document side, so there can be no “misses”. This makes tuning B easy – increasing B will always improve performance, so increase it as large as possible within your dimension constraints. This is also illustrated in the grid search experiments, where increasing B improves performance. We will emphasize this further by referring back to the paragraph on Page 5 in the section on grid searching. \n\n> “... (potentially significant) overestimation of the MaxSim similarity function.”\n\nIt is certainly true that setting B too small could result in collisions, but we note that this could actually only result in an underestimation. In fact, we prove that our method never over-estimates (Lemma A.3), since every query vector will get matched to some document vector (or none, if fill_empty_clusters is not enabled) which can only result in an underestimate of the best similarity.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their thoughtful comments and suggestions. We reply to the questions and comments of each reviewer individually in the corresponding rebuttal fields. First, we would like to emphasize here several global points which will address common concerns of the reviewers.

Firstly, we stress that the goal of our work is to design a more practically- and theoretically-efficient method for multi-vector retrieval. We do not focus on modeling aspects, or comparing multi-vector with other retrieval methods such as SPLADE or other single-vector methods. Such comparisons have already been considered extensively in the literature. Like PLAID, our method is a standalone multi-vector retriever, is independent of the underlying multi-vector model, and works given any database of multi-vector embeddings. Therefore, while there may be other approaches to IR not based solely on the multi-vector representations, they are out of the scope of this paper.

Secondly, we would like to make clarifying points with respect to the comparison of MUVERA and PLAID. While our goal is to design a state of the art retrieval system for multi-vector search, we see the main contribution of our work as contributing a new approach to multi-vector search which is based on principled theoretical guarantees, as an alternative to the prior heuristic approaches used by other work on multi-vector retrieval. PLAID itself is a highly-engineered system which is built on a sequence of successive optimizations (ColBERT, ColBERTv2, PLAID), and has been carefully hyper-optimized, especially for MS MARCO. In fact, quoting from a recent reproducibility study of PLAID (https://arxiv.org/pdf/2404.14989): “PLAID’s Pareto frontier is a patchwork of parameter settings; changing one parameter without corresponding changes to the others can result in slower retrieval with no change to effectiveness.”

In contrast, our paper is the very first of its kind using the new FDE method, and is significantly simpler to tune and, as a result, is more straightforward to generalize to arbitrary models and data sets without significant quality regression. We used the *same parameter settings* for all six of the datasets tested, and on five out of the six we outperformed PLAID. On MS MARCO, which PLAID was highly tuned for, we nearly matched its performance, which we find to be a strong contribution given that our technique has not benefited from the same extensive engineering as PLAID. 

Finally, we emphasize that in our offline experiments, we show that as a method for retrieval FDE’s are 2x-5x more efficient than the SV heuristic (Figure 5), meaning that they need to retrieve many fewer candidates to achieve the same recall. Since PLAID uses (an optimized version of) the SV heuristic, we believe that this signals that there is significant headroom for optimizing the approach of using FDE’s for multi-vector retrieval.

Meta-review: 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.
Decision: Accept (poster)