DESSERT: An Efficient Algorithm for Vector Set Search with Vector Set Queries
Authors: Joshua Engels
Benjamin Coleman
Vihan Lakshman
Anshumali Shrivastava
Venue: NeurIPS 2023 poster (2023)
Keywords: Embedding Based Retrieval
Passage Ranking
Locality Sensitive Hashing
Randomized Algorithms
TL;DR: We extend the traditional near neighbor search problem to sets of vectors, and show both empirical and theoretical speed up over the best alternative methods.

Abstract: We study the problem of $\text{\emph{vector set search}}$ with $\text{\emph{vector set queries}}$. This task is analogous to traditional near-neighbor search, with the exception that both the query and each element in the collection are $\text{\textit{sets}}$ of vectors. We identify this problem as a core subroutine for semantic search applications and find that existing solutions are unacceptably slow. Towards this end, we present a new approximate search algorithm, DESSERT ($\text{\bf D}$ESSERT $\text{\bf E}$ffeciently $\text{\bf S}$earches $\text{\bf S}$ets of $\text{\bf E}$mbeddings via $\text{\bf R}$etrieval $\text{\bf T}$ables). DESSERT is a general tool with strong theoretical guarantees and excellent empirical performance. When we integrate DESSERT into ColBERT, a state-of-the-art semantic search model, we find a 2-5x speedup on the MS MARCO and LoTTE retrieval benchmarks with minimal loss in recall, underscoring the effectiveness and practical applicability of our proposal.

DESSERT: An Efficient Algorithm for Vector Set Search with Vector Set Queries
Joshua Engels
Benjamin Coleman ThirdAI benj amin. ray. co eman@gmail com
ThirdAI
josh adam. Engels@gmail.com
Vihan Lakshman
Anshumali Shrivastava
ThirdAI vihan@thirdai. com
ThirdAI, Rice University
anshu@thirdai, com, anshumali@rice edu
Abstract
We study the problem vector set search with vector sel queries. This task is analogous to traditional near-neighbor search, with the exception that both the query and each element in the collection are sets of vectors. We identify this problem core subroutine for semantic search applications and find that existing solutions are unacceptably slow. Towards this end, we present a new approximate search algorithm, DESSERT (DESSERT Effeciently Searches Sets Embeddings via Retrieval Tables). DESSERT is a general tool with strong theoretical guarantees and excellent empirical performance. When integrate DESSERT into ColBERT, a state-of-the-ard semantic search model, we find 2-5x speedup on the MS MARCO and LoTTE retrieval benchmarks with minimal loss in recall, underscoring the effectiveness and practical applicability of our proposal.
Introduction
Similarity search is fundamental driver of performance for many high-profile machine learning applications. Examples include web search [16], product recommendation [33], image search [21], de-duplication of web indexes [29] and friend recommendation for social media networks [39]. In this paper, study variation the traditional vector search problem where the dataset D consists of collection of vector sets D = S and the query Q is also a vector set. We call this problem vector set search with vector set queries because both the collection elements and the query are sets of vectors. Unlike traditional vector search, this problem currently lacks a satisfactory solution.
Furthermore, efficiently solving the vector set search problem has immediate practical implications. Most notably, the popular ColBERT model, a state-of-the-an neural architecture for semantic search over documents [23], achieves breakthrough performance retrieval tasks by representing each query and document as a set of BERT token embeddings. ColBERT's current implementation of vector set search over these document sets, while superior to brute force, is prohibitively slow for real-time inference applications like e-commerce that enforce strict search latencies under 20-30 milliseconds [34, 5]. Thus,
efficient algorithm for searching over sets of vectors would have significant implications making state-of-the-art semantic search methods feasible to deploy in large-scale production settings, particularly cost-effective CPU hardware.
Given ColBERT's success in using vector sets to represent documents more accurately, and the prevailing focus traditional single-vector near-neighbor search in the literature [1, 41, 19, 12, 14, 28, 18], we believe that the potential for searching over sets of representations remains largely untapped. An efficient algorithmic solution to this problem could enable new applications in domains
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where multi-vector representations are more suitable. To that end, we propose DESSERT, novel randomized algorithm for efficient set vector search with vector set queries. We also provide general theoretical framework for analyzing DESSERT and evaluate its performance on standard passage ranking benchmarks, achieving a 2-5x speedup over an optimized ColBERT implementation on several passage retrieval tasks.
1.1 Problem Statement
More formally, consider the following problem statement.
Definition 1.1. Given a collection of N vector sets D = .S.'...SNk query set Q, a failure probability 8 2 0, and set-to-set relevance score function F(Q, S), the Vector Set Search Problem is the task of returning S with probability at least 1 - 5:
S argmax 5:). iE()....N)
Here, each set S; = {I1,...mm, contains m, vectors with each 2, Rd, and similarly Q = {q1....mm. contains my vectors with each oj E R4.
We further restrict our consideration to structured forms of F(Q,S), where the relevance score consists of two "set aggregation" or "variadic" functions. The inner aggregation operates on the pairwise similarities between a single vector from the query set and each vector from the target set. Because there are |S| elements in S over which to perform the aggregation, takes |S] arguments. The outer aggregation A operates over the [Q] scores obtained by applying A to each query vector q E Q. Thus, we have that
F(Q, S) = A((Ineer, g. Q))
Innerg.s = o(fsim(9. x) S})
Here, sim is vector similarity function. Because the inner aggregation is often maximum other non-linearity, we use (()) to denote it, and similarly since the outer aggregation is often a linear function we denote with A(-). These structured forms for F A a are good measure of set
similarity when they are monotonically non-decreasing with respect to the similarity between any pair of vectors from Q and S.
1.2
Why is near-neighbor search insufficient?
may at first seem that we could solve the Vector Set Search Problem by placing all of the individual vectors into near-neighbor index, along with metadata indicating the set to which they belonged. One could then then identify high-scoring sets by finding near neighbors to each E Q and returning their corresponding sets.
There are two problems with this approach. The first problem that a single high-similarity interaction between g E Q and E S does not imply that F(Q, S) will be large. For concrete example, suppose that we are dealing with sets of word embeddings and that Q is phrase where one of the items is "keyword." With standard near-neighbor index, Q will match (with 100% similarity) any set S that also contains "keyword," regardless of whether the other words in S bear any relevance to the other words in Q. The second problem is that the search must be conducted over all individual vectors, leading to search problem that is potentially very large. For example, sets are documents consisting of roughly thousand words and we wish search over million documents, we now have to solve a billion-scale similarity search problem.
In this work, we formulate and carefully study the set of vector search problem with the goal of developing a more scalable algorithm capable of tackling large-scale semantic retrieval problems involving sets of embeddings. Specifically, research contributions can be summarized as follows:
Contributions:
1. We develop the first non-trivial algorithm, DESSERT, for the vector set search problem that scales to large collections (n > 10") of sets with m > 3 items.
2. We formalize the vector set search problem rigorous theoretical framework, and we provide strong guarantees for common (and difficult) instantiation of the problem.

---

3. We provide an open-source C++ implementation of our proposed algorithm that has been deployed a real-world production setting'. Our implementation scales to hundreds of millions of vectors and is 3-5x faster than existing approximate set of vector search techniques. We also describe the implementation details and tricks we discovered to achieve these speedups and provide empirical latency and recall results on passage retrieval tasks.
2 Related Work
Near-neighbor search has received heightened interest in recent years with the advent of vector-based representation learning. In particular, considerable research has gone into developing more efficient approximate near-neighbor (ANN) search methods that trade off an exact solution for sublinear query times. A number of ANN algorithms have been proposed, including those based on locality-sensitive hashing [1, 41], quantization and space partition methods [19, 12, 14), and graph-based methods [28, 18]. Among these classes of techniques, our proposed DESSERT framework aligns most closely with the sensitive hashing paradigm. However, nearly all of the well-known and effective ANN methods focus on searching over individual vectors; our work studies the search problem for sets of entities. This modification changes the nature of the problem considerably, particularly with regards to the choice of similarity metrics between entities.
Near-Neighbor Search:
The general problem of vector search has been relatively understudied in the literature. A recent work on database lineage tracking [25] addresses this precise problem, but with severe limitations. The proposed approximate algorithm designs concatenation scheme for the vectors in a given set, and then performs approximate search over these concatenated vectors. The biggest drawback to this method scalability, as the size of the concatenated vectors scales quadratically with the size of the vector set. This leads to increased query latency as well as substantial memory overhead: in fact, we are unable to apply the method to the datasets in this paper without terabytes of RAM. In this work, we demonstrate that DESSERT can scale to thousands of items per set with a linear increase (and a slight logarithmic overhead) in query time, which, to our knowledge, has not been previously demonstrated in the literature.
Vector Set Search:
Document Retrieval: In the problem of document retrieval, we receive queries and must return the relevant documents from preindexed corpus. Early document retrieval methods treated each documents as bags of words and had at their core an inverted index [30]. More recent methods embed each document into single representative vector, embed the query into the same space, and performed ANN search on those vectors. These semantic methods achieve far greater accuracies than their lexical predecessors, but require similarity search instead of inverted index lookups [15, 33, 26).
ColBERT and PLAID: COlBERT [23] is a recent state of the art algorithm for document retrieval that takes a subtly different approach. Instead of generating a single vector per document, ColBERT generates set of vectors for each document, approximately one vector per word. To rank a query, ColBERT also embeds the query into a set vectors, filters the indexed sets, and then performs brute force sum of max similarities operation between the query set and each of the document sets. CoIBERT's passage ranking system is an instantiation of our framework, where sim(q, 2)) the cosine similarity between vectors, a is the max operation, and A is the sum operation.
In a similar spirit to our work, PLAID [37] is a recently optimized form of ColBERT that includes more efficient filtering techniques and faster quantization based set similarity kernels. However, we note that these techniques are heuristics that do not come with theoretical guarantees and do not immediately generalize to other notions of vector similarity, which is a key property of the theoretical framework behind DESSERT.
3 Algorithm
At a high level, DESSERT index D compresses the collection of target sets into a form that makes set to set similarity operations efficient to calculate. This is done by replacing each set Sy with a sketch Dii] that contains the LSH values of each xj E St. At query time, we compare the corresponding
3

---

Indexing
Hash Tables
Querying
Query Set
Count Callisions
Index
Set Relevance Scores
Target Sets
0.3
Figure I: The DESSERT indexing and querying algorithms. During indexing (left), we represent each target set as set of hash values (L hashes for each element). To query the index (right), we approximate the similarity between each target and query element by averaging the number of hash collisions. These similarities are used to approximate the set relevance score for each target set.
LSH values of the query set Q with the hashes in each D[:] to approximate the pairwise similarity matrix between Q and S (Figure I). This matrix is used as the input for the aggregation functions A and to rank the target sets and return estimate of S*.
We assume the existence of locality-sensitive hashing (LSH) family C (R Z) such that for all LSH functions h E H. p(h(z) = h(y)) sim (z, 3). LSH functions with this property exist for cosine similarity (signed random projections) [8]. Euclidean similarity (p-stable projections) [11],
and Jaccard similarity (minhash or simhash) [6]. LSH is well-developed theoretical framework with
a wide variety of results and extensions [4, 3, 20, 40J. See Appendix for deeper overview.
Algorithm describes how to construct a DESSERT index D. We first take LSH functions fc for / [L, L). ft E H. We next loop over each S; construct D(i). For given St, arbitrarily assign an identifier j to each vector x E S. E [1, [S]]]. We next partition the set [1, m. using each hash function h4, such that for a partition Pt, indices J1 and j2 are in the same set in the partition iff h(S,,) h(S)2). We represent the results of these partitions in universal hash table indexed by hash function id and hash function value, such that D(i]r, {i x, E A = h].
Algorithm 2 describes how to query a DESSERT index D. At a high level, we query each sketch D, to get estimate of F(Q, St), score,, and then take the argmax of argmax (I.... (I....N) F(Q. S²). To get these estimates, we first compute the hashes ht,g for each N) query and LSH function ft- Then, to get an estimate score; for set S₁, we loop over the hashes he.g for each query vector and count how often each index j appears in Dii After this step, we have a count for each that represents how many times (g) = he (1rz). Equivalently,
the estimates get estimate
finish
since p(h(x) = h(y)) = sim (z. y), if we divide by apply to these estimates and save the result in a variable aggy build up the inputs to A, and then apply A to get our final estimate for S,), which we store in score,.
have an estimate for sim j 9). We then
4 Theory
In this section, we analyze DESSERT's query runtime and provide probabilistic bounds on the correctness of its search results. We begin by finding the hyperparameter values and conditions that are necessary for DESSERT to return the top-ranked set with high probability. Then, we use these results to prove bounds the query time. In the interest of space, defer proofs the Appendix.
Notation:
For the sake of simplicity of presentation, we suppose that all target sets have the same If this is not the case, one may replace m. with mmax in our
number of elements m, i.e. |SS] analysis. We will use the boldface vector s(g, S)) R SSll to refer to the set of pairwise similarity calculations {sim(g,x1),.... ..),..., sim(g, xm,)) between query vector and the elements of S,, and we will drop the subscript (g. St) when the context is clear. See Table I for complete notation reference.

---

Table 1: Notation table with examples from the document search application.
Notation
Definition
Intuition (Document Search)
D
Set of target vector sets Cardinality [D]
Collection of documents
Number of documents
D
DESSERT index of D Target vector set Query vector set See Definition 1.1
Search index data structure ith document
S
Q
Multi word query (e.g., question)
The most relevant document to Q Embedding from document
Ij S;
jth vector in target set S; jth vector in query set Q Sj.2, E Rd
Oj E EQ
Embedding from a query Embedding dimension
mis
Cardinality J.S]), m, Q and S; relevance score Estimate of F(Q, S.)
Number of embeddings in ith document
F(Q, S.)
Measures query-document similarity
score;
Approximation of relevance score Estimates relevance score for S; and any Q Embedding similarity
D
Sketch of ith target set and b vector similarity See Section 1.1 Number of hashes ith LSH function
sim a. b)
A.
Components of relevance score
L
Larger I. increases accuracy and latency Often maps nearby points to the same value
f
s(q, St),
sim(g, 22)
for 2 S
Query embedding similarities with S;
Algorithm Building a DESSERT
Algorithm Querying a DESSERT Index
Index
1: Input: DESSERT index D, query set Q, 1Q mg.
1: Input: N sets S;, |S
2: Output: Estimate of argmax (E....N A o (Q, S.)
2: Output: A DESSERT index D
3: for q Q do
3: D = an array of N hash tables,
4: h1,g. ......... hL.9 fi Sn((1)
each indexed by æ E g?
5: for = 1 to do
4: for i = 1 to N do
6: for q in Q do
5: for x in St do
7: 3=0
to L do 6: for = f(
8:
for f = 1 to L do
7:
9:
for j in Di do
8:
Diile, 1
10:
8; = 8;
9: Return ID
11:
$=$/L.
12:
agga = (s))
13:
score; = Allagg, E Q})
14:
Return argmax score;
4.1 Inner Aggregation
We begin by introducing condition the component of the relevance that allows to prove useful statements about the retrieval process.
Definition 4.1. A function oxx) R + IR is (a, -maxiaall on U C Rmm if for 0 < B 3 S a,
VI E U:
3 maxx X S (x) < a max
The function (x) maxx is trivial example of an (a, 33-mmximall function on R", with = a = 1. However, we can show that other functions also satisfy this definition:
Lemma 4.1.1. If (x()):) R IR is (a, 3)-mxiimal (2)) TM + IR is a,
interval 1, then the following function
f maximal on U = m
1 m
x(x)
p(xx)
m
5

---

Note that in R. the (a, (...3-mmainn maximal condition is equivalent to lower and upper bounds by linear functions Sr and oz respectively, so many natural functions satisfy Lemma 4.1.1. We are particularly interested in the case / = [0. J. and note that possible such include ((xx) x with , the exponential function (p(x) e. with 1. a = e - 1, and the debiased sigmoid function with B ~ 0.23, = 0.25. Our analysis of DESSERT holds when the o component of the relevance score is (a, B) maximal function.
1,
(((x) 1
Ite-z
vector of normalized counts S. In Lemma 4.1.2, we bound the probability that a low-similarity set (one for which a (s) is low) scores well enough to outrank high-similarity set. In Lemma 4.1. 1.3,, we bound the probability that high-similarity set scores poorly enough to be outranked by other sets. Note that the failure rate in both lemmas decays exponentially with the number of hash tables L.
In line 12 Algorithm we estimate (s)) by applying
Lemma 4.1.2. Assume is (a, B) maximal. Let 0 Smax < 1 be the maximum similarity between query vector and the vectors in the target set and let & be the set of estimated similarity scores. Given threshold mas
a, we write A
m+8maax and we have
Pr(o(s) Z a- +A] mz!
for =
ool o(l--mmx)) E (8max: 1). Furthermore, this expression for 7 is increasing in Smax and decreasing in T, and y has one sided limits lim, y " 1 and lim, Smax-
Semas))
Lemma 4.1.3. With the same assumptions as Lemma 1.1 and given A > 0, we have:
Pr(a(s) I 38max A < 2c 22
4.2 Outer Aggregation
Our goal in this section is to use the bounds established previously to prove that our algorithm correctly ranks sets according to FQ), To this, we must find conditions under which the algorithm successfully identifies S* based on the approximate F(Q.S) scores.
Recall that FQQ, S) consists of two aggregations: the inner aggregation (analyzed in Section 4.1) and the outer aggregation A. We consider normalized linear functions for A, where we are given set of weights S w < and we rank the target set according weighted linear combination of scores.
1 m F(Q = m
W. (
Ø=1
With this instantiation of the vector set search problem, we will proceed Theorem 4.2 to identify choice of the number of hash tables L that allows to provide probabilistic guarantee that the algorithm's 's query operation succeeds. We will then use this parameter selection to bound the runtime of the query operation in Theorem 4.3.
Theorem 4.2. Let S* be the set with the maximum F(Q.S) and let S; be any other set. Let B* and B. be the following sums (which are lower and upper bounds for F*Q,S*) and F(Q, respectively)
3 my
B
wy smx (gj: S*)
B
W m m S.)
my
Here, Siase (9, S) is the maximum similarity between query vector 9 and any element of the target set S. Let B' be the maximum value of B; over any set S; + S. Let a be the following value (proportional to the difference between the lower and upper bounds)
= (B" BB)/3
If A a DESSERT structure with the following value? of solves the search problem from Defiiition 1.1 with probability 1 8.
Nmm
T=
log
2L additionally depends on the data-depence dependentn parameter A, which we elide in the asymptotic bound; see the proof in the appendix for the full expression for L.

---

4.3 Runtime Analysis
Theorem 4.3, Suppose that each hash function call runs time O(d) and that |Did]a.ll Vi,t, for some positive threshold T, which we treat as data deta-dependent constant in our analysis. Then, using the assumptions and value of L from Theorem 4.2, Algorithm 2 solves the Vector Set Search Problem in query time
O (m, log(Nm,,m/0)dd + m,, m,
This bound is improvement over a brute force search of (m, when m d is large. The above theorem relies upon the choice of L that we derived in Theorem 4.2.
5 Implementation Details
Filtering: We find that for large N it useful to have an initial lossy filtering step that can cheaply reduce the total number of sets we consider with a low false-negative rate. We use an inverted index on the documents for this filtering step.
To build the inverted index, we first perform k-means clustering on a representative sample of individual item vectors at the start of indexing. The inverted index we will build is a map from centroid ids to document ids. As we add each set S; to D in Algorithm 1, we also add it into the inverted index: we find the closest centroid to each vector x E S and then we add the document id i to all of the buckets in the inverted index corresponding to those centroids.
This method is similar to PLAID, the recent optimized COlBERT implementation [37], but our query process is much simpler. During querying, we query the inverted index buckets corresponding to the closest filter filter_probe centroids each query vector. We aggregate the buckets to get count for each document id, and then only rank the filter_k documents with DESSERT that have the highest count.
Space Optimized Sketches: DESSERT has two features that constrain the underlying hash table implementation: (1) every document is represented by a hash table, so the tables must be low memory, and (2) each query performs many table lookups, so the lookup operation must be fast. If (1) is not met, then we cannot fit the index into memory. If (2) is not met, then the similarity approximation for the inner aggregation step will be far too slow. Initially, we tried a naive implementation of the table, backed by a vedt:vector, std:map. or std:unordered, mapp In each case, the resulting structure did not meet our criteria, so we developed TinyTable, a compact hash table that optimizes memory usage while preserving fast access times. Tiny Tables sacrifice ((1) update-accees access (which DESSERT does not require) for a considerable improvement to (1) and (2).
A TinyTable replaces the universal hash table in Algorithm 1, so it must provide a way to map pairs of (hash value, hash table id) to lists of vector ids. At a high level, Tiny is composed of L inverted indices from LSH values to vector ids. Bucket b of table consists of vectors xy such that h2())) b. During query, we simply need to go to the L buckets that correspond to the query vector's L Ish values to find the ids of S, 's colliding vectors. This design solves (I), the fast lookup requirement, because we can immediately go to the relevant bucket once we have a query's 's hash value. However, there is large overhead in storing resizable vector in every bucket. Even an empty bucket will use 3 8 24 bytes. This adds up: let r be the hash range of the LSH functions (the number of buckets in the inverted index for each of the L tables). If N = 1M, L = 64, and r = 128, we will use L. r 24- 196 gigabytes even when all of the buckets are empty.
Thus, a TanyTable has more optimizations that make it space efficient. Each of the L. hash table repetitions in a Table are conceptually split into two parts: list of offsets and list of vector ids. The vector ids are the concatenated contents of the buckets of the table with no space in between (thus, they are always some permutation of 0 through m - 1). The offset list describes where one bucket ends and the next begins: the ith entry in the offset list is the (inclusive) index of the start of the ith hash bucket within the vector id list, and the i + 1th entry the (exclusive) end of the ith hash bucket (if a bucket is empty, indices = indicesli + 1). To save more bytes, we can further concatenate the L offset lists together and the L vector lists together, since their lengths are always r and my respectively. Finally, we note that if m < 256 we can store all of the the offsets and ids can be safely be stored as single byte integers. Using the same hypothetical numbers as before, a filled Tabye
Table with = 100 will take up just N + ((m + +r- + 1)) 14.7GB.
7

---

The Concatenation Trick:
In our theory, we assumed LSH functions such that p(h(a) h(v))
sim(x. y). However, for practical problems such functions lead overfull buckets; for example, GLOVE has an average vector cosine similarity of around 0.3, which would mean each bucket in the LSH table would contain a third of the set. The standard trick to get around this problem is to concatenate C hashes for each of the I. tables together such that p(h(ar) = h(v)) = sim(x,y)
Rewriting, we have that
(1, v) exp In (p(h(x) = h(y))
(I)
During query, we count the number of collisions across the L tables and divide by L to get p(h(z) = h(y)) on line 11 of Algorithm 2. We now additionally pass count/ into Equation I to get accurate similarity estimate to pass into on line 12. Furthermore, evaluating Equation I for every collision probability estimate slow in practice. There are only L + 1 possible values for the count/ L, so precompute the mapping in lookup table.
6 Experiments
Datasets: We tested DESSERT on both synthetic data and real-world problems. We first examined a series of synthetic datasets to measure DESSERT's speedup over a reasonable CPU brute force algorithm (using the Py PyTorch library [35] for matrix multiplications). For this experiment, we leave out the prefiltering optimization described Section better show how DESSERT performs on its own Following the authors of [25], our synthetic dataset consists of random groups of Glove [36] vectors; we vary the set size m and keep the total number of sets N 1000.
We next experimented with the MS MARCO passage ranking dataset (Creative Commons Li- cense) [32], N 8.8.M. The task for MS MARCO is to retrieve passages from the corpus relevant to query. We used ColBERT to map the words from each passage and query to sets of embedding vectors suitable for DESSERT [37]. Following [37], we use the development set for our experiments, which contains 6980 queries.
Finally, we computed the full resource-accuracy tradeoff for ten of the LoTTE out-of-domain benchmark datasets, introduced by ColBERTv2 [38]. We excluded the pooled dataset, which is simply the individual datasets merged.
We ran our experiments on an Intel(R) Xcon(R) CPU E5-2680 v3 machine with 252 GB of RAM. We restricted all experiments to 4 cores (8 threads). We ran each experiment with the chosen hyperparameters and reported overall average recall and average query latency. For all experiments used the average of max similarities scoring function.
Experiment Setup:
6.1 Synthetic Data
The goal of our synthetic data experiment was to examine DESSERT's speedup over brute force vector set scoring. Thus, we generated synthetic data where both DESSERT and the brute force implementation achieved perfect recall so we could compare the two methods solely query time.
ery Synchedt:
tyto en Brite heve incivieul
The two optimized brute force implementations we tried both used PyTorch, and differed only in whether they computed the score between the query set and each document set individ- ually (" ("Individual") or between the query set and all document sets at once using PyTorch's highly performant reduce and reshape opera- tions ("Combined").
30
307
207
Figure 2: Query time for DESSERT vs. brute force on 1000 random sets of m glove vectors with the y-axis as log scale. Lower is better.
In each synthetic experiment, we inserted 1000 documents of size m for m E [2, 4, 8, 16, .... 1024] into DESSERT and the
8

---

brute force index. The queries in each experiment were simply the documents with added noise. The DESSERT hyperparameters we chose were L 8 and C' = (og)(m) + 1. The results of our experi- ment, which show the relative speedup of using DESSERT at different values of m, are in Figure 2. We observe that DESSERT achieves a consistent 10-50x speedup over the optimized Pytorch brute force method and that the speedup increases with larger m (we could not run experiments with even larger mn because the PyTorch runs did not finish within the time allotted).
6.2 Passage Retrieval
Passage retrieval refers to the task of identifying and returning the most relevant passages from a large corpus of documents in response to a search query. In these experiments, we compared DESSERT to PLAID, ColBERT's heavily-optimzed MARCO and LoTTE passage retrieval tasks.
sate-of-the-aa late interaction search algorithm, on the MS
We found that the best ColBERT hyperparameters were the same as reported in the PLAID paper, and we successfully replicated their results. Although PLAID offers way to trade off time for accuracy, this tradeoff only increases accuracy at the sake of time, and even then only by fraction of percent. Thus, our results represent points on the recall vs time Pareto frontier that PLAID cannot reach.
MS MARCO Results For MS MARCO, we performed a grid search over DESSERT pa-
rameters = (4,5, 6, 7). L = (16,32, 64). filter_ fiiter_probe {1. 2, 4, 8), and filter k {1000, 2048, 4096, 8192, 16384). We reran the best configurations to obtain the results in Table 2. We report two types of results: methods tuned to return 10 results and methods tuned return k = 1000 results. For each, we report DESSERT results from a low latency and high latency part of the Pareto frontier. For k = 1000 we use the standard R@1000 metric, the average recall of the top 1 passage in the first 1000 returned passages. This metric is meaningful because retrieval pipelines frequently rerank candidates after an initial retrieval stage. For k = 10 we use the standard MRR010 metric, the average mean reciprocal rank of the top 1 passage in the first 10 returned passages, Overall, DESSERT is 2-5x faster than PLAID with only a few percent loss in recall.
Method Latency (ms)
MRR@10
Method
Latency (ms)
R@1000
DESSERT
9.5
35.7 = 1.14
DESSERT DESSERT PLAID
22.7
95.1 + 0.49
DESSERT 15.5
37.2 + 1.14
32.3
96.0 + 0.45
PLAID 45.1
39.2 + 1.15
100
97.5 + 0.36
Table 2: MS MARCO passage retrieval, with methods optimized for k=10 (left) and k=1000 (right). Intervals denote 95% confidence intervals for average latency and recall.
LoTTE Results
For LOTTE, we performed grid search over C = {4, 6, 8), L= (32, 64, 128). = {1, 2. 4). and filler_k {1000, 2048, 4096, 8192]. In Figure 3, we plot the full Pareto tradeoff for DESSERT on the 10 LoTTE datasets (each of the 5 categories has a "forum" and "search" split) over these hyperparameters, as well as the single lowest-latency point achievable by PLAID. For all test datasets, DESSERT provides a Pareto frontier that allows tradeoff between recall and latency. For both Lifestyle test splits, both Technology test splits, and the Recreation and Science test-search splits, DESSERT achieves a 2-5x speedup with minimal loss in accuracy. On Technology, DESSERT even exceeds the accuracy of PLAID at half of PLAID's latency.
7 Discussion
We observe a substantial speedup when we integrate DESSERT into COlBERT, even when compared against the highly-optimized PLAID implementation. While the use of our algorithm incurs a slight recall penalty as is the case with most algorithms that use randomization to achieve acceleration Table 2 and Figure 3 shows that we are Pareto-optimal when compared with baseline approaches.
We are not aware of any algorithm other than DESSERT that is capable of latencies in this range for set-to-set similarity search. While systems such as PLAID are tunable, we were unable to get them to operate in this range. For this reason, DESSERT is likely the only set-to-set similarity search algorithm that can be run in real-time production environments with strict latency constraints.

---

lifestyle
writing
recreation
60
02
Succeess@11
78
643
76
74
70
70
technology
50
10.0
science
Mean Latency (ms)
75
70
Succeess@10
PLAID
DESSERT
60
15
dev-search
DESSERT dev-search
10-
10
15
10 15
Mean Latency (ms)
Mean Latency (ms)
Figure 3: Full Pareto frontier of DESSERT on the LoTTE datasets. The PLAID baseline shows the lowest-latency result attainable by PLAID (with FAISS-IVE base index and centroid pre-filtering)
We also ran a single-vecte vector search baseline using ScaNN, the leading approximate kNN index [14]. ScaNN yielded 0.77 Recall 1000, substantially below the state of the art. This result reinforces our discussion in Section 1.2 on why single-vector search is insufficient.
Broader Impacts and Limitations: Ranking and retrieval are important steps in language modeling applications, some of which have recently come under increased scrutiny. However, our algorithm is unlikely to have negative broader effects, as it mainly enables faster, more cost-effective search over larger vector collections and does not contribute to the problematic capabilities of the aforementioned language models. Due to computational limitations, set of benchmarks; a larger-scale evaluation would strengthen our argument. Finally, we assume sufficiently high relevance scores and large gaps in theoretical analysis to identify the correct results. These hardness assumptions are standard for LSH.
conduct our experiments
relatively small
8 Conclusion
In this paper, we consider the problem of vector set search with vector set queries, a task understudied in the existing literature. We present formal definition of the problem and provide motivating application in semantic search, where more efficient algorithm would provide considerable immedi- ate impact in accelerating late interaction search methods. To address the large latencies inherent in existing vector search methods, we propose novel randomized algorithm called DESSERT that achieves significant speedups over baseline techniques. We also analyze DESSERT theoretically and, under natural assumptions, prove rigorous guarantees on the algorithm's 's failure probability and runtime. Finally, we provide an open-source and highly performant C++ implementation of our pro- posed DESSERT algorithm that achieves 2-5x speedup over ColBERT-PLAID on the MS MARCO and LoTTE retrieval benchmarks. We also note that a general- purposs algorithmic framework for vector set search with vector set queries could have impact in number of other applications, such as image similarity search [42], market basket analysis [22], and graph neural networks [43], where might be more natural to model entities via sets of vectors as opposed to restricting representations to single embedding. We believe that DESSERT could provide viable algorithmic engine for enabling such applications and we hope to study these potential use cases in the future.
10

---

9 Acknowledgments
This work was completed while the authors were working ThirdAL. We do not have any external funding sources to acknowledge.
References
[1] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 51(1):117-122, 2008.
[2] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt, Practical and optimal Ish for angular distance. Advances in neural information processing systems, 28, 2015.
[3] Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the twenty-fifth anmual ACM-SIAM symposium Discrete algo- rithms, pages 1018-1028. SIAM, 2014.
[4] Alexandr Andoni and Ily Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the sertt- annual ACM symposium Theory of computing, pages 793-801, 2015.
[5] loannis Arapakis, Souneil Park, and Martin Pielot. Impact of response latency on user behaviour in mobile web search. In Proceedings of the 2021 Conference Human Information Interaction and Retrieval, pages 279-283, 2021.
[6] A. Broder. On the resemblance and containment of documents. In Proceedings of the Com- pression and Complexity of Sequences 1997, SEQUENCES '97, page 21, USA, 1997. IEEE Computer Society.
[7] J Lawrence Carter and Mark N Wegman. Universal classes of hash functions. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 106-112, 1977.
[8] Moses S. Charikar. Similarity estimation techniques from rounding algorithms. Proceedings of the Thiry-Fourth Annual ACM Symposium Theory of Computing, STOC '02, page 380-388, New York, NY, USA, 2002. Association for Computing Machinery.
[9] Benjamin Coleman, Richard Baraniuk, and Anshumali Shrivastava. Sub-linear memory sketches for near neighbor search on streaming data. In International Conference on Machine Learning, pages 2089-2099. PMLR, 2020.
[10] Benjamin Coleman and Anshumali Shrivastava. Sub-linear race sketches for approximate kernel density estimation streaming data. In Proceedings of The Web Conference 2020, pages 1739-1749, 2020.
[11] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG '04, page 253-262, New York, NY, USA, 2004. Association for Computing Machinery.
[12] Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. arXiv preprint arXiv:190I.08544 2019.
[13] Joshua Engels, Benjamin Coleman, and Anshumali Shrivastava. Practical near neighbor search via group testing. Advances in Neural Information Processing Systems, 34:9950-9999 19000996222220 2021.
[14] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887-3896. PMLR, 2020.
[15] Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padmanabhan, Giuseppe Ottaviano, and Linjun Yang. cimbedding-basee retrieval in facebook search. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2553-2561, 2020.

---

[16] Po-Sen Huang, Xiaodong He, Jianfeng Gao. Li Deng, Alex Acero, and Larry Heck. Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 1333-2336 2013.
[17] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '9, page 604-613, New York, NY, USA, 1998. Association for Computing Machinery.
[18] Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint (tf0::881000700 2018.
[19] 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.
[20] Jianqiu Ji, Jianmin Li, Shuicheng Yan, Bo Zhang, and Qi Tian. Super-bit locality-sensitive hashing. Advances in neural information processing systems, 25, 2012.
[21] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535-547, 2019.
[22] Manpreet Kaur and Shivani Kang. Market basket analysis: Identify the changing trends of market data using association rule mining. Procedia computer science, 85:78-85, 2016.
[23] 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 48, 2020.
[24] Runze Lei, Pinghui Wang, Rundong Li, Peng Jia, Junzhou Zhao, Xiaohong Guan, and Chao Deng. Fast rotation kernel density estimation over data streams. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 892-902, 2021.
[25] Michael Leybovich and Oded Shmueli. Efficient approximate search for sets of vectors. arXiv preprint arXiv:2107.06817 2021.
[26] Sen Li, Fuyu Lv, Taiwei Jin, Guli Lin, Keping Yang, Xiaoyi Zeng, Xiao-Ming Wu, and Qianli Ma. Eimbedding-base product retrieval in taobao search. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 3181-3189, 2021.
[27] Chen Luo and Anshumali Shrivastava. Arrays of (locality-sensitive) count estimators (ace) anomaly detection on the edge. In Proceedings of the 2018 World Wide Web Conference, pages 2018.
[28] Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824 836, 2018.
[29] Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma. Detecting near-duplicates for web crawling. In Proceedings of the 16th international conference on World Wide Web, pages 141-150, 2007.
[30] Christopher D Manning. Prabhakar Raghavan, and Hinrich Schütze, Introduction information retrieval. Cambridge university press, 2008
[31] Nicholas Meisburger and Anshumali Shrivastava. Distributed tera-scale similarity search with mpi: Provably efficient similarity search over billions without a single distance computation. arXiv preprint arXiv:2008. 03360, 2020.
[32] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. Ms marco: human generated machine reading comprehension dataset. In Workshop on Cognitive Computing at NIPS, 2016.
12

---

[33] Priyanka Nigam. Yiwei Song, Vijai Mohan, Vihan Lakshman, Weitian Ding, Ankit Shingavi, Choon Hui Teo, Hao Gu, and Bing Yin. Semantic product search. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2876-2885, 2019.
[34] Steve Olenski. Why brands are fighting over milliseconds, Nov 2016.
[35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[36] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP), pages 1532-1543, 2014.
[37] Keshav Santhanam, Omar Khattab, Christopher Potts, and Matei Zaharia. Plaid: An efficient engine for late interaction retrieval. arXiv preprint arXiv:2205.0970) 2022.
[38] Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. Colbertv2: Effective and efficient retrieval via lightweight late interaction. arXiv preprint 12X1::2112001488 2021.
[39] Aneesh Sharma, C Seshadhri, and Ashish Goel. When hashes met wedges: A distributed algo- rithm for finding high similarity vectors. In Proceedings of the 26th International Conference on World Wide Web, pages 431-440, 2017.
[40] Anshumali Shrivastava and Ping Li. Improved asymmetric locality sensitive hashing (alsh) for maximum inner product search (mips). In Proceedings of the Thirty-First Conference Uncertainty Artificial Intelligence, pages 81 812-821, 2015.
[41] Yiqiu Wang, Anshumali Shrivastava, Jonathan Wang, and Junghee Ryu. Flash: Randomized algorithms accelerated over cpu-gpu for ultra-high dimensional similarity search. arXiv preprint arXiv:1709.011 190, 2017.
[42] Jun Yang, Yu-Gang Jiang, Alexander Hauptmann, and Chong- Waong-WWhhha Ngo. Evaluating bag- ofodss representations in scene classification. In Proceedings of the international workshop on Workshop on multimedia information retrieval, pages 197-206, 2007.
[43] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. CoRR, abs/1806.01997, 2018.
13

---

A Proofs of Main Results
Lemma 4.1.1. If (((x)) R + R is (a, m-mmximal on an interval then the following function (x)) 1 + R is a, m
f
-maximal U :
xxx) Σ ((x))
Proof. Take some x E (so each Dy E 1). Since I, max(x) = æ, we have from the definition of (a, maxximal that
Bx S x S az
For the upper bound, we have
1 m78
(x) (x,)
S
Ot
(m max(x)) max(x)
m
where the second inequality follows by the properties the max function. For the lower bound, we have that
8
(x) =
3r.
max x
1=1
where the the second inequality again follows by the properties of the function.
Lemma 4.1.2. Assume is (ax, 3m-mximmal. Let O < Smax < 1 be the maximum similarity between query vector and the vectors the target set and let & be the set of estimated similarity scores. Given threshold ma8 < a, we write A m.8 and we have
Pr(a(s) 2 asmax + A mo!
yor
(fl-Smmxx) E (Smax. 1). Furthermore, this expression for is increasing Smax and decreasing т, and y has one sided limits lim,>aasuux 7 = and lim, / 7 = 8max-
Smag
Proof. We first apply a generic Chernoff bound to (s). which gives us the following bounds for any t t> 0:
B[e etr
Pr(a(S) 2 7] Pr(e > eTT
We now proceed by continuing to bound the numerator. Because a is (a, mmxxmall,,, we can bound (S) with max S. We can further bound max by bounding the maximum with the sum and the sum with m times the maximal element. We are now left with the formula for the moment generating function for 8max. Smax scaled binomial L B(mmam L), so we directly substitute the binomial moment generating function into the expression:
(8)) < EEle ta max,
max, 8y
<
Bletas tasj] < mllle ta
m2( 8max + Smaxe )z
Combining these equations yields the following bound:
Pr(a(() 2 7 & me -tr (1 Smax + Smaxe 4
We wish to select a value of to minimize the upper bound. By setting the derivative of the upper bound to zero, and imposing 0 < < > 1, and Smax 1, we find that
14

---

L In a
T(1 - Smax)
Smax (ar T)
This greater than zero when the numerator inside the In is greater than the denominator, or equivalently when T > SmaxQ. Thus the valid range for T is (Smax a) (and similarly the valid range for Smax (0, 7 /o))). These bounds have a natural interpretation:
be meaningful, the threshold
must be between the expected value and the maximum value for times p Smax binomial.
Substituting into our upper bound, we obtain:
Pr(a(s) 2 m ((+() ((+(1- 8max)
- a((1 8max) )
L
Smmax( -T)
Thus we have that
8max (K
T) r(1 Smax)
1. [x(1 8max)
We will now prove our claims about y viewed as a function of Smax E (0, T/a) and (smax a). We will first examine the limits of with respect to J at the ends of its range. Since is continuous, we can find one of the limits by direct substitution:
(//aaa-)) =u
a aa11 a - )
lim
lim 7=
=1=
Smax /7/a 7(1 - TT/a)
Smaze
The second limit is harder; we merge y into one exponent and then simplify:
Smax
-) (
lim y lim a/a
Ta
T(1 8max] 1-007
Smax (a la 0/T
lim T/a
T(1 Smaxx) 1-//T
lim Smax T/a
7) 1a/aT
lim (smax(a 55mxx(a770077) -1/r T/aa
-1/a
lim ((ar ((a- a--
8max
(1)-1/a
Smax
Smax
where the fact that lim, vo ln(x) 1 (we that lim x In(x) lim (n(x)/(1/xx) = 0 with L'Hopital's rule). We next find the partial derivatives of y:
87
maax)
Okmmmn Suaaa t - Smaxt
87 (Smax 1)
(8Suas Sman T- -mmaxx
In
asmmax - Smax?
T-S
8s 0amax
Smax ma
öT
a T
We are interested in the signs of these partial derivatives. First examining 8y
Jamax as max
T 088max > 0. Similarly, a > T - a - T 0 and 8max - 7) = Smax( 8max7 > Finally, 8max < - r(1 8max) =
T8max > O. Thus every term is positive and the entire fraction is positive. Next examining d2 37 by similar logic a > 0 and
8max T > 0 and $max > Q $max7, so the numerator greater than the denominator and the In is positive. Finally, since Smax 1. Smax 1 < and thus the entire fraction has a single negative term the product, so is negative.
0'8max $max 7 > For the In, since 5 > a
This completes our lemma: is strictly decreasing function of T and strictly increasing function of 8max- Since T decreasing and has leftward limit of and rightward limit of smax, all values for y are in (smax: 1).
15

---

First, we will make a substitution. We note that is a strictly decreasing function on this interval of T with range (Smax: 1). To see this, we will first make the following change of variabls:
a(k +
T
k ++1
for & E (0, oo). This parameterizes 7 E (smax a) weighted sum of max and a. Plugging in and simplifying, we have that
kiramax R+1
max
(k+ + 1)
+ Smax
This is continous function over E (0, oo) and 8max ()
Lemma 4.1.3. With the same assumptions as Lemma 4.1.2 and given A > 0, we have:
Pr(a(s) < max A] < 2e 2TA2//88
2
Proof. We will prove this lemma with a chain of inequalities, starting with Pr[o($) < 38max - A]:
Pr(a(()= S 8amax
A]
Pr max $ < =amax
A]
Pr Pr[Bsmax I m8x A
Pr mrs8 Bsuiax
A
< Pri| Bsmaxl 2 AJ = Prr[[ssmax -B8maxl 2 A]
S 182
The explanations for each step are follows:
1. Because (s) 2 8 maxs, we can replace (s) with 3 max and the probability will be strictly larger.
2. By the definition of the max operator, each individual & < max and in particular this is true for smax (the estimated similarity for the ground-truth maximum similarity vector). Thus, we have Bamax S 33 max so we can again apply replacement to get further upper bound.
3. Rearranging.
4. Because Pr[la bl = Pr(a b + c
5. 6max is the sum of L Bernoulli trials with success probability 5max and scaled 3 L. Thus, we can directly apply the Hoeffding ineuqliaty with trials with success probability 8a L
Theorem 4.2. Let S* be the set with the maximum F(Q,S) and let S; be any other set. Let B* and B, be the following sums (which are lower and upper bounds for F(Q,S*) and F.), respectively)
3
my
my
B
Σ my
wy Smax (q.. S*)
B
wy Smax (gj. St)
my j=l
Here, Smax (g, S) is the maximum similarity between query vector g and any element of the target set S. Let B' be the maximum value of B; over any set S, + S. Let A be the following value (proportional the difference between the lower and upper bounds)
A =BB -B'//3
16

---

A O, DESSERT structure with the following value' of L solves the search problem from Definition 1.1 with probability 1 5.
L 0=0 Nmg
Proof. For set S* to have the highest estimated score F(Q, S*), ), we need all other sets to have lower scores. Our overall proof strategy will find minimum L that upper bounds the probability that each inner aggregation of a set S & S* is greater than A + ass ? the probability that the inner aggregation of S less 88 muxx A. Finally, we will show that an that is maximum of these two values solves the search problem.
and minimum that lower bounds
Upper Bound: We start with the upper bound on S; * S*: we have from Lemma 4.1.2 that
Pr(o(si: 2 max + + S my!!
with
A Attroj,mas
(A + OLS 068i, )1 8i,max)
a(1 8i.max
Si,max (A + (.8i,max))
(A 0'8i,max
and N/ (0, 1). To make our analysis simpler, as function A, since then all of these bounds will hold with the same 7, making easy to solve for L. Since limemms N.0 7 and /i
interested in the maximum 7max of all these Y
- A /a, there must be some Ymax E (1 - A/a, 1) that maximizes this expression over any 8max. This exact maximum is hard to find analytically, but are guaranteed that it is less than 1 by Lemma 4.1.2. We will use the term Tmax in analysis, since it is data dependent and guaranteed to be in the range (0, 1). We also numerically plot some 1 to give some intuition for what the function looks like over different A; we note that it is decreasing in A and approximates a linear function for >>> 0.
values of Mmax here with
Numerical Solutions Ymax with
1.0
0.8
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0
To hold with the union bound over all N target sets and all my query vectors with probability we want the probability that our bound holds on single set and query vector to be less than
N Dim We find that this true with L > log 2(N 2(N-1)m,m
log( "maax for any qj and S;:
Pr[p(Si, (3) 2 aax S mm! S mix S m (7maxx
log
11mmm log(
Tiaxx
2(N )m
'L additionally depends on the data data-dependen parameter A, which we elide in the asymptotic bound: see the proof in the appendix for the full expression for L.
17

---

Lower Bound We next examine the lower bound on S we have from Lemma 4.1.3 that
Pr(a((",00) (b) S max
2 254
To hold with the union bound over all my query vectors with probability that our bound holds on single set and query vector to be less than
j. we want the probability
5 We find that this is true
2m,"
with L 2 log( 6 )0² for any 9z-
4mm 22
Pr(a($".0)) S B8.
A] < 2e 11
2e
221B2
2m
Putting Together
Let
log
2(N 1)m
log( B ),3²
L max
log
2
7mmax
Then the upper and lower bounds we derived in the last two sections both apply. Let be the random variable that is when the m, (N -)) upper bounds and the m. lower bounds hold and that is otherwise. Consider sets S; * S* Then the probability we solve the Vector Search Problem from Definition 1. equal to the probability that all v, (F(Q,5*) F(Q. > 0). We now lower bound this probability:
F(Q, Pr - > 0))
m,
mg
u 93) > >0 0)
= Pr
44
Σ
"s ($*,3))
,4:)
Σ
Definition of F
mg j=1
mg j=1
my
Pr
44
Σ wy(a(s" o >0
my
of 11=1]] 1) Pr(1 =
Pr
11
Σ uy(o 91) ($), 0
Pr(A) 2 Pr(AAB)
mg
Pr
V1
Σ Wi( (3s s.,max
A (asi + +)) >
Pr(1 1)
Bounds hold 1
Pr
14
Σ
wi( (3s m mxx) > 24 Σ
Wj
Pr(1
1=1
Pr
V:
my (B* (B* - B,) 24 Wij
Pr(1 1)
Definition of B", B,
j=1
2 Pr
41
(B"
(B* - B¹) > 2A
Wij
Pr(1 1)
Definition of B'
j=l
my
2 Pr
V1
3m, A > 2A
w/
Pr(1 =
Definition of A
1=1
2 Pr (V, (3mH A 2m, A)) Pr(1 1)
Wi S
= 1 (1=1) 1)
A 0
18

---

= 1 (1 0)
8
2 1 (m mg (N - 1) 2(N 1)
* m4) = 1
Union bound
2m4
and thus DESSERT solves the Vector Set Search Problem with this choice Finally, we can now examine the expression for L to determine its asymptotic behavior. Dropping the positive data dependent constants
22 and S², the left term in the max for L. is O(Tgg( Nm, and the
Timax
right term in the max is (log ""))), )), and thus L = O (log( Nay
Theorem 4.3, Suppose that each hash function call runs in time O(d) and that [Didlenl < TV,,t, h for some positive threshold T, which we treat as data-dependent constant our analysis. Then, using the assumptions and value of T. from Theorem 4.2, Algorithm 2 solves the Vector Set Search Problem query time
O (mg log( NoggNNmmm/84e + log Mog(Nmmm//ol
Proof. If we suppose that each call to the hash function ft is (dd), the runtime the algorithm is N-1-1
nLd +
ΣΣΣ
To bound this quantity, we use the sparsity assumption we made in the theorem: no set S; contains too many elements that are very similar a single query vector qj- Formally, we require that
Diilanl < T Vi,t,
for some positive threshold T. With this assumption, the runtime of Algorithm 2 is
O Ld + NLT)
Plugging in the L we found in previous theorem, and treating T as data dependent constant, have that the runtime of Algorithm 2 is
0 (mg log log( mm/d + N log( m//m))
which completes the proof.
B Hyperparameter Settings
Settings for DESSERT corresponding to the first row in the left part of Table 2, where DESSERT was optimized for returning 10 documents in low latency part of the Pareto frontier:
hashes_peas table (C)
num_tables
num tables (L.) 32
filter_k 4096
filter_probe
Settings for DESSERT corresponding to the second row in the left part of Table 2, where DESSERT optimized for returning 10 documents in high latency part of the Pareto frontier:
hashes_pezs kashes_per_table (C) =
num_tables (L)
64
filter_k 4096
filter_probe 2
Settings for DESSERT corresponding to the first row the right part Table 2, where DESSERT was optimized for returning 1000 documents in a low latency part of the Pareto frontier:
19

---

pasheesper_table (C)=
num_tables (L) 32
filter_k 8192
filter_probe
Settings for DESSERT corresponding to the second row in the right part of Table where DESSERT was optimized for returning 1000 documents in a high latency part of the Pareto frontier:
hashes_per_table (C) =
num_ num_tables (L) 32
filter_k 16384
filter_probe
Intuitively, these parameter settings make sense: increase the initial filtering size and the number of total hashes for higher accuracy, and increase the initial filtering size for returning more documents (1000 vs. 10).
C Background on Locality-Sensitive Hashing and Inverted Indices for Similarity Search
Here, we offer a refresher on using locality hashing for similarity search with a basic inverted index structure.
Consider set of distinct vectors = (.1,..., INN) where each ot E TRd A hash function h with a range m maps each v; to an integer in the range [1, m]. Two vectors I; and I are said to "collide" when h(:;) h(z)).
As warmup, we will first consider the case of a hash function drawn from a set of universal hash functions H. Under such function, if + j. p(h(x) h(w)) : such families exist in practice [7]. We can build an inverted index using this hash function by mapping each hash value in [1, m] to the set of vectors X, that have this hash value. Then, given a new vector y, we can query the inverted index with h(y). We can see that X iff y X. Such an index is in a sense solving search problem, we only care about finding exact duplicates of search query. Additionally, we can solve the nearest neighbor problem with this index in time O(N), ), by going to every bucket and checking the distance of query against every vector in the bucket.
Now, in a similar way as the universal case, let h to be drawn from a family of locality-sensitivy hash functions H. At a high level, instead of mapping vectors uniformly to [1, m], maps vectors that are close together to the same hash value more often. Formally, if we define a "close" threshold rı. "far" threshold r2, "close" probability pl, and "far" probability p2, with pi p2 and rı < r2.
then we say H is (r1, 72, Pl, P2) -enssiiie if
d(x, v) < r1 = Pr(h(z) = h(y)) > Pr d(x, y) > 12
Pr(h(z) h(y)) < <
where d is a distance metric. See [17] for the origin of locality-sensiinn sensitive hashing and this definition. Intuitively, if we build an inverted index using the same way as before, it now seems we have strategy to solve the (approximate) nearest neighbor problem more efficiently: given a query q, only search for nearest neighbors the bucket h(g), since each of these points æ likely has d(g, a) < ri- However, this strategy has problem: with our definition, even a close neighbor might not be collision with probability (1 P1). Thus, we can repeat our inverted index L times with different h; drawn independently from H, such that our probability of not finding close neighbor in any bucket (1 - =. FALCONN [2] is an LSH inverted index algorithm that uses this basic idea, along with concatenation and probing tricks, to achieve an asymptotically optimal (and data-dependent sub-linear) runtime; see the paper and associated code repository for more details.
One final note is that in practice, most LSH families satisfy much stronger condition than the above. Consider a similarity function sim E [0, 1]. where s(x, v) = = I = yy. As æ and y get more dissimilar (e.g. their distance increases according to some distance metric), s sxx, v) decreases. For most I.SH families, there exists an explicit similarity function that their collision probability satisfies, such that p(h(x) h(y)) sim(x, y). Such LSH families exist for most common similarity
20

---

functions, including cosine similarity (signed random projections) [8], Euclidean similarity (p-stable
projections) [11], and Jaceard similarity (minhash or simhash) [6]. Following [13, 9, 10. 27, 24, 31], in our work, we use LSH families with this explicit similarity description to provide tight analyses and strong guarantees for similarity-search algorithms.
21


Reviews:
[{"review_id": "etEZLDP5K1", "reviewer": "Reviewer_yuRv", "summary": "This paper considers a nearest neighbor search problem where each point is a set of vectors, and the distance function is drawn from a general class of aggregation functions over the vectors. \n\nThe approach presented here is based on the LSH algorithms, but since we're dealing with multiple vectors, the bounds behind LSH need to be re-derived. Assumptions used in order to allow or speed up the search include that the distance function obeys a certain Lipschitz smoothness property, and tools include inverted indices, sampling, and compressed tables. These are all fairly standard in the field.", "questions": "None.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The query model introduced is interesting, and the authors make a good argument as to its utility. The techniques utilized are non-trivial, and constitute a contribution to the field of nearest neighbor search. The fact that the distance function is very general is also a plus.", "weaknesses": "The presentation can be somewhat improved. The authors actually put in significant work into this direction, but the presentation can be improved by adding a high-level overview of the approach before introducing the pseudo-code. This is a more effective approach than referring to code to explain an approach.\n\nThe authors should also add background on LSH and inverted indices, so that the paper can be more accessible to non-experts.\n\nThe explanation of the motivation behind TinyTable is garbled, and a clearer exposition is necessary. \n\n---------------------------------\n\nIn response to the author rebuttal, and in particular the improvement in presentation, I raised my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for pointing out the presentation issues. \n\nRegarding high-level overview: Good suggestion. We’ve added the following description to Section 3: “At a high level, DESSERT compresses the collection of target sets into a form that makes similarity operations efficient to calculate. This is done by replacing each element of the set with its LSH codes, transforming the set into an integer array of hash values. At query time, these hash values are compared with the corresponding hashes of the query set elements to approximate the pairwise similarity matrix (Figure 1). This matrix is used as the input for aggregations $A_2$ and $A_1$ to rank the target sets.”\n\nRegarding background: We began with a longer text that contained a thorough exposition on LSH and inverted indices, which we had to cut down due to the NeurIPS page limit. In the revision, we have put this background back into the appendix and provided references in the main text for the interested reader.\n\nRegarding TinyTable: After a second read-through, we agree. We’ve drafted a revised description of TinyTables, which we hope will be clearer:\n“DESSERT has two features that constrain the underlying hash table implementation: (1) every document is represented by a hash table, so the tables must be low memory, and (2) each query performs many table lookups, so the lookup operation must be fast. If (1) is not met, then we cannot fit the index into memory. If (2) is not met, then the similarity approximation for the inner aggregation step will be far too slow. Initially, we tried a naive implementation of the table, backed by an std::vector, std::map, or std::unordered_map. In each case, the resulting structure did not meet our criteria, so we developed TinyTable, a compact hash table that optimizes memory usage while preserving fast access times. TinyTables sacrifice O(1) update-access (which DESSERT does not require) for a considerable improvement to (1) and (2).”\n\nIf this rebuttal has addressed your concerns, we hope you may consider raising the score.\n\n"}, {"review_id": "vtjmGNGxff", "reviewer": "Reviewer_hUSH", "summary": "The paper presents a study focused on the problem of vector set search with vector set queries, which is a crucial subroutine for various web applications. The authors highlight the insufficiency of existing solutions in terms of speed. To address this, they propose a new approximate search algorithm called DESSERT. DESSERT is a versatile tool that offers robust theoretical guarantees and demonstrates excellent empirical performance. The authors integrate DESSERT into ColBERT, a highly optimized state-of-the-art semantic search method, and report a notable 2-5x speed improvement on the MSMarco passage ranking task.", "questions": "1. How can DESSERT be applied to different similarity measures?\n\n2. How to intuitively explain the running time and memory? How do the terms $L$  and $T$ relate to the search quality?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The problem formulation is truly innovative. Vector set search is undeniably an essential and challenging task, with practical applicability in serving LLMs. \n\n2. The proposed methodologies are lucid and firmly grounded, ensuring the reproducibility of the research.  DESSERT uses hash tables for element-wise similarity search to build a data structure for vector set similarity search. Moreover, DESSERT taking advantage of hash tables in terms of query speed and performs an efficient query for similar sets.\n\n3. DESSERT has a detailed theoretical analysis in terms of inner and outer aggregation, which justify its choices of aggregation functions in the algorithm.\n", "weaknesses": "It would be better to have a section that unifies the notation for algorithms and theory. Maybe a table would be better. \n\nOverall, I have a positive impression on the paper. If authors are willing to further polish the theory part of the paper, I'm willing to raise the score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and suggestions. We agree that the theory is a little hard to read, so we’ve added a table to disambiguate. We’ve reproduced (part of) the table below and have added this to the appendix. We have also updated the notation in the algorithm listings, since there were some mistakes (e.g., $k$ instead of $L$ as the hash subscript in line 4 of Algorithm 2). We also plan to standardize the notation between the practical and theoretical sections (e.g., we can rewrite Algorithm 2 to replace the “count” variable with $\\hat{\\mathbf{s}}(q, S_i)$). We thank you for pointing out these discrepancies and we plan to carefully consolidate the notation as much as we can.\n\n| Notation                     | Definition                                                | Explanation                                                                              |\n| ---------------------------- | --------------------------------------------------------- | ---------------------------------------------------------------------------------------- |\n| $D$                          | Set of target sets                                        | Collection of documents                                                                  |\n| $N$                          | Cardinality $\\\\vert D \\\\vert$                                         | Number of documents                                                                      |\n| $\\\\mathcal{D}$               | DESSERT index of $D$                                      | Search index data structure                                                              |\n| S                            | Target set                                                | Document (text passage)                                                                  |\n| Q                            | Query set                                                 | Search phrase (text passage)                                                             |\n| $x \\\\in S_i$                 | Vector in target set $S_i$                                | Embedding                                                                           |\n| $q \\\\in Q$                   | Vector in query set $Q$                                   | Embedding                                                                           |\n| $m_i$                        | Cardinality $\\\\vert S_i \\\\vert$                                       | Length of $i$th document                                                                 |                                                                   |                                      |\n| $\\\\mathrm{score}_i$          | Estimate of $F(Q,S_i)$                                    | Approximate relevance /  search ranking score                                            |\n| $L$                          | Number of hashes                                          | Larger $L$ increases the accuracy of $\\\\mathrm{score}$ at the cost of space and latency. |\n                                             \n\n__Questions:__\n\n*Q1: How can DESSERT be applied to different similarity measures?*\n\nTo use DESSERT with a similarity measure other than cosine similarity, we can use a different LSH function. There are well-known LSH functions for similarities based on Euclidean, Manhattan, and Lp-norm distances [1] as well as measures defined over sets and Hamming codes (such as Jaccard similarity [2-4], edit distance, etc). There is also a developing research area using asymmetric hashing techniques [6] to design more flexible, asymmetric similarity measures.\n[1]: “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,” Datar et. al. in SCG 2004.\n[2]: “One Permutation Hashing,” Li et. al. in NIPS 2012\n[3]: “Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search,” Shrivastava and Li, ICML 2014\n[4]: “Re-randomized Densification for One Permutation Hashing and Bin-wise Consistent Weighted Sampling\n[5]: “Locality-sensitive hashing for the edit distance,” Marcais et. al., Bioinformatics, Volume 35, Issue 14, July 2019\n[6]: “Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS),” Shrivastava and Li, NIPS 2014\n\n*Q2: How to intuitively explain the running time and memory? How do the terms L and T relate to the search quality?*\n\nT is the maximum number of elements in a single set that share the same hash code. This bound can be loosely interpreted as saying, “No set $S_i$ contains too many elements that are very similar to a single query vector $q \\\\in Q$.” In the text-search setting, T can be thought of as the number of duplicate words (or very close synonyms) in the document.\n\nTo develop intuition for why we need this bound, look at lines 9-10 of Algorithm 2. If an element of the query set $Q$ collides with every element in a target set $S_i$, the loop in lines 9-10 takes time $|S_i|$. If this happens for every target set, the resulting algorithm is asymptotically no better than brute force (albeit with expensive distance calculations replaced by cheap integer operations). However, this also does not happen except for in highly degenerate, unrealistic cases where the document consists entirely of duplicate / near-duplicate terms (e.g., the document “cat cat cat kitten cat” and the query “cat kitten”). In practical search datasets, we’ve found that T is fairly small (usually under 20).\n\nL is the number of hash functions used to approximate the similarity. L is a design parameter - higher values of L require a larger index size and query time but result in a smaller error when estimating the similarity scores. This can be seen from Lemma 4.2.3: for a fixed failure probability $\\delta$, the estimation error decays with $\\frac{1}{\\sqrt{L}}$. \nWe will add this discussion to Section 4.3. \n\n\nIf this rebuttal has addressed your concerns, we hope you may consider raising the score.\n"}, {"review_id": "5QnDkonyOj", "reviewer": "Reviewer_Uhsc", "summary": "The paper addresses the problem of set-to-set similarity calculation and retrieval, which is a problem with any downstream applications. While previous approaches inevitably perform a brute force similarity calculation over |Q| query vectors and |S| target vectors for each set comparison F(Q, S), this paper leverages random hashing functions to estimate similarity between query and target vectors to avoid this brute force search. Combined with highly space-optimized hash tables, and building on top of previous centroid-based candidate set filtering mechanisms, the proposed algorithm achieves notable speed improvements over existing methods at only a small cost to recall. Theoretical support is provided for the algorithm, along with experiments on synthetic, solvable data and the standard MS MARCO benchmark dataset. ", "questions": "- The paper argues that vector-level NN retrieval is clearly limited, but I think this assumes that one is really looking for a comparison using something like A2=weighted sum and A1=max. I think there are settings where one would be interested in A2=max and A1=max, as well as other variants. Are there problems besides passage retrieval that are better evaluated in terms of other combinations of A2 and A1 besides those considered in this paper?\n- The set-to-set comparison problem might also be viewed more generally as comparison of two distributions over R^d. When |Q| and |S| are large relative to d, these distributions might be accurately estimated and then distributional divergence measures deployed. What do you think the trade-offs are with a vector similarity-based approach? (And could the perspectives be unified based on specifying A2/A1 and sim?)\n- I think I never saw which specific LSH functions you used, besides using 16/32/64 of them. Are they all signed random projection to approximate cos-sim?\n- What does perfect recall mean on synthetic data? That you already know what the correct top-1 avg-max-sim “passage” is?\n- Can you increase the latency of your approach to reach the performance of PLAID?\n- In the next version of the appendix, could you include the results of your hyperparameter grid search?\n- Since you make a claim about Pareto improvement, it would be nice to include graphs visualizing the Pareto curves of the methods.\n- More of a comment, really: You might add “passage retrieval” for language modeling pretraining and finetuning to the list of potentially valuable applications for this kind of approach. Current methods use simple heuristics like embedding averaging across tokens to reduce the problem to vector-level NN search: https://arxiv.org/pdf/2112.04426.pdf.", "limitations": "Yes, the limitation section was satisfactory. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Very important: The proposed method cleverly utilizes randomness via an LSH based approach to estimate similarity and avoid brute force similarity calculation between sets of vectors, leading to notable improvements in speed over previous methods, at reasonable memory requirements for large scale settings, and with very limited negative impact on recall.\n- Important: The experiments are simple and clear.\n- Important: The choice of baselines seems appropriate. As the authors note, their method reaches points on the Pareto curve, w.r.t. latency, that are not reachable by baselines even though the baselines are nominally customizable for trading off latency vs. recall. \n- Important: The paper is clearly written.\n- Of some importance: Theoretical analysis is provided for the proposed method, although, as the authors note, they “assume sufficiently high relevance scores and large gaps in our theoretical analysis to identify the correct results.”", "weaknesses": "- Important: As noted by the authors, this work draws heavily upon LSH-based NN vector search methods that already use LSH methods to approximate exact similarity calculation. In my opinion, the extension to the set-to-set comparison setting is fairly straightforward. This is a drawback of the methodological contribution of the paper, in terms of novelty, though it may be entirely outweighed by the positive empirical performance of the approach over strong baselines.\n- Of some importance: The intro of the paper is written as if the paper proposes a generic framework for cross-query-vector aggregation (A2) and cross-target-vector aggregation steps (A1), but to my understanding, the only setting experimentally considered in the paper is that of A2 = weighted sum and A1 = max. This seems to be the main practical setting of interest in settings like passage retrieval, but I would not say this paper really broadens how people have been thinking about set-to-set comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding novelty: While LSH methods have been widely used for the last 20 years, our set search departs from the standard approach in some subtle but important ways. The vast majority of LSH search algorithms group points into hash tables, then explicitly compute similarities between points that fall into the same buckets. A naive adaptation of this method would actually require more memory than PLAID. Instead, we use collision statistics to rank sets based only on the distribution of hash codes, meaning that we do not store the d-dimensional embeddings. While similar ideas have recently been used for vector similarity search [1] and density estimation [2], this is still an emerging area and a new interpretation of LSH.\nWhile it is true that the NLP community currently only uses A2 = (unweighted) sum and A1 = max, our theory shows that the set-search problem is tractable for a larger family of functions. We hope that this might lead to better modeling techniques (e.g., learned weights in the sum, or soft nonlinearities in place of the maximum), though this is beyond the scope of our present study. Our general analysis provides some insight about which kinds of functions might be good candidates (e.g., Lemma 4.2.1 identifies smooth, monotone functions as compatible with fast search).\n\n__Questions:__\n\n1. While it is true that the NLP community currently only uses A2 = (unweighted) sum and A1 = max, our theory shows that the set-search problem is tractable for a larger family of functions. We hope that this might lead to better modeling techniques (e.g., learned weights in the sum, or soft nonlinearities in place of the maximum), though this is beyond the scope of our present study. \nProblems such as database lineage tracking [1] use a linear combination of average and max similarity (and [1] references papers that use different A1 / A2). Image instance retrieval can be formulated as A1=max and A2=max (e.g., over SIFT vectors), but again other compositions are possible [2]. We think that the design of A1 and A2 represents an exciting opportunity for future work, since our results show that a large class of similarity aggregation functions can be solved tractably. \n\n\t[1] https://arxiv.org/pdf/2107.06817.pdf\n\n\t[2] https://arxiv.org/pdf/2101.11282.pdf\n\n\n2. This idea is very interesting. For divergence-based ranking to be feasible, we would need a fast, low-memory way to model high-dimensional distributions and compute divergences. Most methods scale poorly with input size and dimensionality (in both runtime and error), but some recent LSH-based algorithms [2, 3] can construct a kernel density estimate of the distribution in near-linear time. If a divergence measure can be constructed from these methods, it would lead to a tradeoff where DESSERT requires $O(m m_q)$ time to materialize the pairwise similarity matrix, but the divergence calculation runs in time $\\tilde{O}(m + m_q + C)$ where $C$ is the cost to compute the divergence.\n\nFor example, consider the kernel density estimate of the total variation distance.\n$$\\int_z \\left|\\sum_{q \\in Q}k(q, z) - \\sum_{x \\in S}k(x, z)\\right|dz$$\nIf we approximate this integral by sampling point estimates at a set $Z$ of sampling locations (e.g. Monte Carlo estimation), we have an estimate of the form:\n$$\\frac{c}{|Z|}\\sum_{z \\in Z} \\left|\\sum_{q \\in Q}k(q, z) - \\sum_{x \\in S}k(x, z)\\right|dz$$\nwhere $c$ is a scalar. If the quantity $k(x, z)$ is chosen from the family of LSH similarity kernels [2], it can be approximated via DESSERT if we choose $z$ from the set $Q$. This gives the decomposition:\n$$A_1(A_2(q, S)) = c\\sum_{z \\in Q}\\left| \\sum_{z \\in Q} k(q,z) - A_2(z, S) \\right|$$\n$$A_2(q,S) = \\sum_{x \\in S} \\sigma(q, x)$$\n$$\\sigma(x,z) = k(x,z)$$\nUnfortunately, it is not clear whether the restriction $z \\in Q$ ruins the Monte Carlo estimator. It is also not clear whether other divergences (such as the KL divergence or Hellinger distance) can be similarly decomposed. Another problem is that nonparametric density estimation suffers from the curse of dimensionality: $|S|$ must grow much faster than $d$ to have constant estimation error (so this may only work for very large sets). This is a fascinating direction for future work.\n\nReferences:\n\n[1]: “FLASH: Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search,” Wang et. al., SIGMOD 2018\n\n[2]: “Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data,” Coleman and Shrivastava, WWW 2020\n\n[3]: “Rehashing Kernel Evaluation in High Dimensions,” Siminelakis et. al., ICML 2019\n\n3. Yes, the LSH functions are all signed random projections.\n\n4. Yes, we computed the top-1 avg-max-sim “passage” to use as ground truth for the synthetic experiments.\n\n5. Regarding whether DESSERT can match PLAID: We’ve conducted new experiments on LoTTE that show the full latency-performance tradeoff. Our experiments show that it is sometimes (but not always) possible to match the PLAID performance. This is probably due to the estimation error of our similarity approximation. Lemma 4.2.3 shows that in principle, this error can be driven arbitrarily small (as $L \\to \\infty$, the error between the DESSERT and PLAID ranking scores goes to zero with high probability). However, the error scales with $\\frac{1}{\\sqrt{L}}$, so zero error requires large values of $L$ that may not be feasible in practice.\n\n6. We plan to include these results, as well as the Pareto-optimal hyperparameter configurations for LoTTE.\n\n7. See our evaluation on LoTTE (pdf attached in the author rebuttal), where we show the full Pareto curves. On the plots, the PLAID result shows the lowest-latency result attainable by PLAID. We did not do the full curves for MS-MARCO due to computational constraints.\n\n8. Thank you for the reference! We will mention this in the revision.\n\n\nIf our response has addressed the concerns raised in your review, we hope you will consider raising the score.\n\n"}, {"review_id": "PFKptxezYQ", "reviewer": "Reviewer_FWNJ", "summary": "The paper studies the vector set search problem, which is an extension of the canonical near-neighbor search problem and finds an application in the semantic search task. The paper claims that existing methods for vector set search are unacceptably slow, and thus, proposes an approximate search algorithm called DESSERT. The paper presents both theoretical analysis and empirical evaluation to demonstrate the effectiveness of the DESSERT algorithm.", "questions": "Please refer to the Weaknesses given above, and provide further explanations, particularly for W1 and W2.", "limitations": "I do not see any potential negative societal impact in this paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The paper proposes a new algorithm, DESSERT, to solve the vector set search problem efficiently. \n\nS2. The paper presents both theoretical analysis and empirical evaluation to testify the effectiveness of the DESSERT algorithm. \n\nS3. The DESSERT algorithm can be applied to the semantic search task.", "weaknesses": "W1. [Motivations & Contributions] The paper is the first to formally formulate the vector set search problem (if not, then citations are required to be provided to the first work), yet only providing one concrete application of the vector set search problem (i.e., semnatic search). The reasons why we need to study the vector set search problem require further clarified. It seems to me that the DESSERT algorithm is actually an incremental work, with a specific focus for improving the running time of the ColBERT model. This severely limits the paper's contributions.\n\nW2. [Experiments] According to the paper, the proposed algorithm, DESSERT, is implemented in C++. However, the baseline method, the brute force algorithm, is implemented in Python using the PyTorch library. The reasonability and fairness of implementing two methods in different programming languages need further explanations. \n\nW3. [Presentations] The paper's presentation needs improvement. There exist several typos and undefined notations in the paper. Some concrete examples are given as follows. \n\n- Line 139: I believe the notation H refers to the hash set, which requires further clarification. \n\n- Line 30: citations are required to the literature on traditional single-vector near-neighbor search. \n\n- Algorithm 2: the output given in the pseudo code doesn't concur with the desciptions given in the main text (though they may refer to the same variable).  \n\n\n\n---\nAfter the rebuttal process, most of my concerns mentioned above have been sufficiently addressed. Thus, I raise my rating from 4 to 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1: Yes, we believe that we are the first to formalize the vector set search problem. While semantic search is the clear “killer application” today, we provide references to other potential applications such as database lineage tracking (line 96), image instance retrieval, market basket analysis, and graph neural networks (line 342). We focus on semantic search in our empirical evaluations because it is a core routine for various tasks (web search, product search, recommendation ranking, and question-answering). We hope that our general formulation of the problem will encourage future work in this area, especially since we have shown that search is tractable for a large class of similarity functions.  \n\nSecondly, we respectfully disagree with the claim that accelerating ColBERT is an incremental contribution. ColBERT has had a tremendous impact on both research and practice. The “late interaction” modeling approach introduced by ColBERT represents the state of the art in numerous IR benchmarks such as passage retrieval [1], multi-hop reasoning [2], open question answering [3], and even broader retrieval problems such as table QA [4]. Given the widespread interest and adoption of ColBERT and the importance of achieving low latency inference on cost-effective hardware in industry settings [5] , we believe that our work has the potential for substantial real-world impact. \n\n[1] https://arxiv.org/abs/2205.09707\n\n[2] https://arxiv.org/abs/2101.00436\n\n[3] https://arxiv.org/abs/2007.00814\n\n[4] https://aclanthology.org/2023.acl-short.133/\n\n[5] https://arxiv.org/abs/2101.09086\n\n\nW2: PyTorch is not a pure python library and heavily calls out to optimized C++ and CUDA kernels for tensor operations. Similarly, we implement DESSERT with a C++ backend and invoke the algorithm via a python interface (please see our code provided in the supplementary materials for further details). Thus, this is an apples-to-apples comparison because both PyTorch and our codebase are Python binding-based C++ libraries. \n\nW3:\n\n- Line 139: This is the set of functions from which we draw the LSH function. It is defined in line 126.\n\n- We discuss this literature in lines 83-94. We will also add the citations in line 30\n\n- We have cleaned up the algorithm pseudocode description by including a table for notation as suggested by Reviewer hUSH. We also fixed multiple typos in the algorithm presentation. \n\nIf this has addressed the issues in your review, we hope that you will consider raising the score.\n\n"}, {"review_id": "tQ6pDE6EZ3", "reviewer": "Reviewer_iVRP", "summary": "In this paper, the authors studied a new problem of vector set search with vector set queries. They have formalized this problem and proposed a novel, provable hashing scheme, DESSERT, to efficiently deal with this problem. Moreover, they have provided theoretical analysis for DESSERT and conducted experiments to validate its efficiency and accuracy.", "questions": "***Experiments***\n\nQ1: For the passage retrieval experiments, it is less convincing to me to use a single dataset for validation. Can they conduct and report results on at least one more dataset (for example, TREC Complex Answer Retrieval dataset [1] used in ColBERT)? \n\nQ2: The metric R@1000 is too weak as an accuracy measure. Can they report recall together with R@1000? \n\nQ3: What are the best hyperparameter settings of C, L, probe, and k for the results they show in Table 1? Moreover, can they conduct the parameter study for some vital parameters (e.g., L and C) of DESSERT?\n\nQ4: In Section 5, the authors developed some implementation tricks for DESSERT. Can they conduct an ablation study to validate the effectiveness of the three tricks they proposed (i.e., filtering by k-means clustering, space optimized sketches, and the concatenation trick)?\n\n***Presentations***\n\nQ5: There exist some typos in Algorithm 2:\n- In line 2: $G\\circ H(G,S_i)$ -> $A_1 \\circ A_2(Q,S_i)$;\n- In line 4: $f_k(q)$ -> $f_L(q)$;\n- In line 11: $count_{m_q}/L$ -> ${count}_{m_i}/L$;\n- In line 13: $0,\\cdots,N-1$ -> $1,\\cdots,N$.\n\n***Reference***\n\n[1] Laura Dietz, Manisha Verma, Filip Radlinski, and Nick Craswell. 2017. TREC\nComplex Answer Retrieval Overview. In TREC.", "limitations": "This work does not appear to have any negative social impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The motivation to study this new problem is clear, which is a vital sub-problem in semantic search, and the authors formalize a general definition of this problem.\n\n- They design an efficient hashing to solve this challenging problem and provide a theoretical bound and query time complexity.\n\n- The presentation is clear and easy to follow.", "weaknesses": "***Novelty and Contributions***\n\n- I appreciate the authors have provided the theoretical bound and query time complexity for their proposed hashing scheme. One of my concerns is that the improvement of the query time complexity is only marginal compared to the brute force method, which is still O(N) in general. Moreover, the impact of L is less discussed either in the theory part or in the experiments, making the efficiency improvement less promising.\n\n***Experiments***\n\n- Another primary concern is the experiments. The experimental results are too few. They only validate the performance of DESSERT on a single real-world dataset, making their conclusion of DESSERT compared to PLAID less convincing. Moreover, no ablation study and parameter study is performed, making users hard to know the effectiveness of implementation tricks and how to set the hyperparameters of DESSERT. Please see Q1-Q4.\n\n***Presentation***\n\n- The paper still needs some careful proofreading. There are some minor issues in Algorithm 2. Please refer to Q5 for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*>I appreciate the authors have provided the theoretical bound and query time complexity for their proposed hashing scheme. One of my concerns is that the improvement of the query time complexity is only marginal compared to the brute force method, which is still O(N) in general. Moreover, the impact of L is less discussed either in the theory part or in the experiments, making the efficiency improvement less promising.*\n\nThank you for pointing this out. In the revision, we plan to include better descriptions of these parameters (see also our response to Reviewer hUSH). In short:\nL is the number of hash functions used to approximate the similarity. L is a design parameter - higher values of L require a larger index size and query time but result in a smaller error when estimating the similarity scores. This can be seen from Lemma 4.2.3: for a fixed failure probability $\\delta$, the estimation error decays with $\\frac{1}{\\sqrt{L}}$. \n\nRegarding the asymptotic complexity: This is true, but we want to emphasize that the asymptotic comparison does not fully capture the advantages of our method. The brute force method requires O(N) distance calculations, which typically require many floating-point multiplications. The most expensive asymptotic term in our method comes from integer comparisons and increments, which are substantially faster on hardware. \n\n__Experiments__\n\nWe conducted a hyperparameter study, which we described on Line 301. We have added a more complete description of this study to the appendix. We have also added an evaluation on ten more datasets from the LoTTE benchmark.\n\n__Questions__\n\n__Q1: For the passage retrieval experiments, it is less convincing to me to use a single dataset for validation. Can they conduct and report results on at least one more dataset (for example, TREC Complex Answer Retrieval dataset [1] used in ColBERT)?__\n\nWe have added an evaluation on ten of the LoTTE datasets, used in ColBERTv2. Our method shows extremely competitive Pareto-frontier performance. See the rebuttal PDF for full pareto tradeoffs on ten of the LoTTE datasets.\n\n__Q2: The metric R@1000 is too weak as an accuracy measure. Can they report recall together with R@1000?__\n\nR@1000 is the standard evaluation metric for the MS-MARCO evaluation task. However, we also report MRR@10 (see Table 1), which is a much harder metric to improve. \nIn our LoTTE experiments, we report a variety of metrics (from R1@10 to R1@1000) using the evaluation code from the original paper.\n\n__Q3: What are the best hyperparameter settings of C, L, probe, and k for the results they show in Table 1? Moreover, can they conduct the parameter study for some vital parameters (e.g., L and C) of DESSERT?__\n\nWe conducted this study, via grid search over the values described in the paper (see Line 301). The results of this study are listed below. We have added this to the appendix.\n\nHyperparameter settings: \n\nSettings for DESSERT corresponding to the first row in table optimized for returning 10 docs:\n- Hashes_per_table (C) = 7\n\n- Num_tables (L) = 32\n\n- initial_filter_k = 4096\n\n- nprobe_query = 1\n\nSecond row:\n- hashes_per_table  = 7\n\n- num_tables = 64\n\n- initial_filter_k = 4096\n\n- nprobe_query = 2\n\nSettings for DESSERT corresponding to the first row in table optimized for returning 1000 docs\n- hashes_per_table = 6\n\n- num_tables = 32\n\n- initial_filter_k = 8192\n\n- nprobe_query = 4\n\nSecond row:\n- hashes_per_table = 7\n\n- num_tables = 32\n\n- initial_filter_k = 16384\n\n- nprobe_query = 4\n\nIntuitively, these parameter settings make sense: increase k and the number of total hashes for higher accuracy, and increase k for returning more documents (1000 vs. 10).\n\n__Q4: In Section 5, the authors developed some implementation tricks for DESSERT. Can they conduct an ablation study to validate the effectiveness of the three tricks they proposed (i.e., filtering by k-means clustering, space optimized sketches, and the concatenation trick)?__\n\nUnfortunately, all of these tricks are strictly required to have a practical index. Without the pre-filtering, the indexing process requires > 1 day to run. The concatenation trick provides a similar speedup. Finally, the process runs out of memory if we do not use space-optimized sketches, so this evaluation is not possible. We will make a note of this in the paper. \n\nIf our response has addressed the issues raised in your review, we hope that you will consider raising the score.\n"}, {"review_id": "yU4y4lzOed", "reviewer": "Reviewer_PFCR", "summary": "The authors study the general case of multi-vector retrieval, i.e., ColBERT and beyond. They propose and analyze a new algorithm for this \"vector set\" search task, with theoretical guarantees. When integrated into ColBERT, the proposed DESSERT method is 2-5x faster at some, relatively small loss in quality.", "questions": "- How much space does the full method consume? I see 15GB are consumed by the hash table. Is that all?\n- How long does preparing the search data structures (indexing) take?", "limitations": "See weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors discuss a general class of \"vector set\" retrieval scoring functions (Sec 1.1), generalizing ColBERT.\n\n2. The authors formalize the \"vector set\" search problem, perhaps for the first time (although I'd be interested in a comparison with Luan et al. 2021 \"Sparse, Dense, and Attentional Representations for Text Retrieval\" for completeness). They propose a new algorithm, unlike ColBERT's. The algorithm provides theoretical guarantees.\n\n3. The proposed method is shown to be ~2pt worse than a recent state-of-the-art ColBERT method (PLAID) on MRR quality, while being 3x faster, applying search in just 15.5 milliseconds per query on CPU. This is on the Pareto frontier with respect to the ColBERT retrieval quality/latency curve.", "weaknesses": "DESSERT is primarily tested on the MS MARCO query set (besides a small synthetic experiment). The authors justify much of this by citing PLAID [35], but that other paper like many IR papers in the last 1.5-2 years tests on several datasets, including especially out-of-domain and larger datasets. It's not inherently clear how much quality loss DESSERT would incur out-of-domain, say, on the LoTTE or BEIR (or even a subset of one of them, if computational resources do not permit more tests). This is the main weakness in my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*>DESSERT is primarily tested on the MS MARCO query set (besides a small synthetic experiment). The authors justify much of this by citing PLAID [35], but that other paper like many IR papers in the last 1.5-2 years tests on several datasets, including especially out-of-domain and larger datasets. It's not inherently clear how much quality loss DESSERT would incur out-of-domain, say, on the LoTTE or BEIR (or even a subset of one of them, if computational resources do not permit more tests). This is the main weakness in my opinion.*\n\nThank you for the suggestion. We have run additional experiments on the LoTTE dataset. We find that DESSERT performs well in the out-of-domain setting. See the rebuttal PDF for full pareto tradeoffs on ten of the LoTTE datasets.\nThank you for the reference to the work of Luan et al. We will take a deeper look and add this to our discussion of related work.\n\n__Questions:__\n\n__Q1: How much space does the full method consume? I see 15GB are consumed by the hash table. Is that all?__\n\nYes, 15 GB is the space required by the full method. In general, DESSERT tables are an order of magnitude smaller than the (non-quantized) full embedding collection. For example, in our LoTTE experiments, the vast majority of configurations were under 4 GB.\n\n__Q2: How long does preparing the search data structures (indexing) take?__\n\nThis is highly hardware-dependent. If a GPU (or accelerator) is available to cluster the centroids (same process used by PLAID), then DESSERT runs in a fraction of the embedding time. For example, MS-MARCO took several hours to embed on GPU, and then 2.5 additional hours to build the DESSERT index. We conducted a new set of experiments on LoTTE (using different CPU hardware), and here DESSERT took about 15 minutes to index 1.5M sets. The key takeaway is that DESSERT indexing adds only a small overhead to the existing embedding costs.\n\nIf our response has addressed the issues raised in your review, we hope that you will consider raising the score.\n\n\n\n"}]

Author rebuttal:
We thank all of the reviewers for their thoughtful feedback! 

It seems the most common theme expressed in the reviews was a desire for evaluation on more datasets. To that end, we have run 10 additional evaluations on the LoTTE dataset for out-of-domain retrieval. Interestingly, we found that DESSERT performed very well compared to PLAID in this setting. We hope that this sufficiently addresses the concerns of those reviewers who desired to see an evaluation on more datasets.  We have attached a pdf plotting the pareto curves for DESSERT and PLAID on these datasets. 

Meta-review: The paper introduces DESSERT, a novel algorithm for efficient vector set search, supported by theoretical analysis and empirical validation. Moreover, DESSERT finds application in the realm of semantic search tasks. It employs hash tables for element-wise similarity search, enhancing query speed and overall efficiency. The reviewers are in favor of accepting the submission, but please incorporate all the reviewers' suggestions in the final version of the paper.
Decision: Accept (poster)