DESSERT: An Efficient Algorithm for Vector Set Search with Vector Set Queries

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.

Strengths

1. The authors discuss a general class of "vector set" retrieval scoring functions (Sec 1.1), generalizing ColBERT. 2. 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. 3. 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.

Questions

- How much space does the full method consume? I see 15GB are consumed by the hash table. Is that all? - How long does preparing the search data structures (indexing) take?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See weaknesses.

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.

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. - They design an efficient hashing to solve this challenging problem and provide a theoretical bound and query time complexity. - The presentation is clear and easy to follow.

Weaknesses

***Novelty and Contributions*** - 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. ***Experiments*** - 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. ***Presentation*** - The paper still needs some careful proofreading. There are some minor issues in Algorithm 2. Please refer to Q5 for more details.

Questions

***Experiments*** 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)? Q2: The metric R@1000 is too weak as an accuracy measure. Can they report recall together with R@1000? 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? 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)? ***Presentations*** Q5: There exist some typos in Algorithm 2: - In line 2: $G\circ H(G,S_i)$ -> $A_1 \circ A_2(Q,S_i)$; - In line 4: $f_k(q)$ -> $f_L(q)$; - In line 11: $count_{m_q}/L$ -> ${count}_{m_i}/L$; - In line 13: $0,\cdots,N-1$ -> $1,\cdots,N$. ***Reference*** [1] Laura Dietz, Manisha Verma, Filip Radlinski, and Nick Craswell. 2017. TREC Complex Answer Retrieval Overview. In TREC.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This work does not appear to have any negative social impact.

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.

Strengths

S1. The paper proposes a new algorithm, DESSERT, to solve the vector set search problem efficiently. S2. The paper presents both theoretical analysis and empirical evaluation to testify the effectiveness of the DESSERT algorithm. S3. 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. W2. [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. W3. [Presentations] The paper's presentation needs improvement. There exist several typos and undefined notations in the paper. Some concrete examples are given as follows. - Line 139: I believe the notation H refers to the hash set, which requires further clarification. - Line 30: citations are required to the literature on traditional single-vector near-neighbor search. - 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). --- After the rebuttal process, most of my concerns mentioned above have been sufficiently addressed. Thus, I raise my rating from 4 to 5.

Questions

Please refer to the Weaknesses given above, and provide further explanations, particularly for W1 and W2.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

I do not see any potential negative societal impact in this paper.

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.

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. - Important: The experiments are simple and clear. - 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. - Important: The paper is clearly written. - 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. - 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.

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? - 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?) - 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? - What does perfect recall mean on synthetic data? That you already know what the correct top-1 avg-max-sim “passage” is? - Can you increase the latency of your approach to reach the performance of PLAID? - In the next version of the appendix, could you include the results of your hyperparameter grid search? - Since you make a claim about Pareto improvement, it would be nice to include graphs visualizing the Pareto curves of the methods. - 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.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes, the limitation section was satisfactory.

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.

Strengths

1. The problem formulation is truly innovative. Vector set search is undeniably an essential and challenging task, with practical applicability in serving LLMs. 2. 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. 3. DESSERT has a detailed theoretical analysis in terms of inner and outer aggregation, which justify its choices of aggregation functions in the algorithm.

Weaknesses

It would be better to have a section that unifies the notation for algorithms and theory. Maybe a table would be better. Overall, 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.

Questions

1. How can DESSERT be applied to different similarity measures? 2. How to intuitively explain the running time and memory? How do the terms $L$ and $T$ relate to the search quality?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors adequately addressed the limitations.

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. The 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.

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. The authors should also add background on LSH and inverted indices, so that the paper can be more accessible to non-experts. The explanation of the motivation behind TinyTable is garbled, and a clearer exposition is necessary. --------------------------------- In response to the author rebuttal, and in particular the improvement in presentation, I raised my score.

Questions

None.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Reply to rebuttal

Thanks for the thorough reply. The response addresses all of my questions. Where my main concern was novelty, I appreciate that a naive extension of existing methods to the set-to-set setting would be extremely memory intensive, and the proposed algorithm makes some advances on that front. Other parts of the response point out ways that the paper theory and method are relatively general across possible applications, although the experiments in the paper remain somewhat narrow in their focus. I raise my score from 6 to 7 as a result, though I am keeping my confidence at 2 because I am not intimately familiar with the area for the paper.

Reply to Rebuttal

Thank you for the rebuttal. The authors have addressed all of my concerns. I am happy to see that much more datasets have been included in this manuscript, and the results make this work more convincing. I will raise my score to 6. Thanks!