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

Joshua Engels, Benjamin Coleman, Vihan Lakshman, Anshumali Shrivastava

TL;DR

DESSERT is a novel randomized algorithm designed for "vector set search," where both queries and data points are collections of embeddings rather than single vectors. By leveraging locality-sensitive hashing (LSH) and a memory-optimized "TinyTable" structure, DESSERT achieves a 2-5x speedup over state-of-the-art models like ColBERT with minimal loss in retrieval accuracy.

What Problem Does This Paper Address?

Traditional similarity search focuses on finding the "nearest neighbor" to a single query vector in a massive collection of individual vectors. However, modern semantic search models—most notably ColBERT—have moved toward "late interaction" architectures. In these systems, a document isn't represented by one vector, but by a set of vectors (e.g., one for every token in the text).

Searching through these sets is computationally expensive. To rank a document, you must compute a complex set-to-set relevance score, often involving finding the maximum similarity for every query token against all document tokens. Existing solutions are either prohibitively slow brute-force methods or specialized heuristics that lack theoretical guarantees. DESSERT aims to fill this gap by providing a general-purpose, theoretically grounded, and highly efficient algorithm for set-to-set search.

Methods

DESSERT (DESSERT Efficiently Searches Sets of Embeddings via Retrieval Tables) treats the set-to-set search problem as an approximation task.

  1. Indexing (Sketching): Instead of storing raw vectors, DESSERT creates a "sketch" for each document set. Each vector in the set is passed through $L$ different Locality-Sensitive Hashing (LSH) functions. These hash values are stored in a specialized data structure.
  2. Querying: At query time, the query set is also hashed. The algorithm approximates the similarity between the query and document sets by counting "hash collisions"—how often the query hashes match the document hashes.
  3. Aggregation: The collision counts are used to estimate the "MaxSim" (maximum similarity) for each query vector, which are then summed to produce a final relevance score.
  4. TinyTable: To make this practical, the authors developed a custom, memory-efficient hash table called "TinyTable." It avoids the overhead of standard C++ containers, allowing the index to fit into RAM even when dealing with millions of documents.
  5. The Concatenation Trick: To handle vectors with low average similarity (like GloVe embeddings), the authors concatenate multiple hashes to sharpen the collision probability, ensuring that only truly similar vectors trigger a match.
Figure 1: The DESSERT indexing and querying algorithms. During indexing (left), we represent each target set as a 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.

Datasets

The authors evaluated DESSERT across three main types of data:

  • Synthetic Data: Random groups of GloVe vectors used to measure raw speedup against brute-force implementations.
  • MS MARCO: A massive real-world passage ranking dataset containing approximately 8.8 million documents.
  • LoTTE: A benchmark for "Long-Tail Topic Estimation," consisting of ten out-of-domain datasets designed to test how well retrieval models generalize.

Key Insights and Ideas

  • Set-to-Set is a Unique Challenge: The authors argue that simply treating set search as a billion-scale single-vector search is insufficient. Set similarity depends on the collective interaction of embeddings, and a single high-similarity match doesn't necessarily mean the whole set is relevant.
  • LSH as a Distribution Estimator: Rather than just using LSH to find the single nearest neighbor, DESSERT uses it to estimate the entire similarity distribution between two sets efficiently.
  • Theoretical Rigor: Unlike many approximate search heuristics, DESSERT comes with formal probabilistic guarantees. The authors prove bounds on the number of hash tables ($L$) required to ensure the top-ranked set is returned with high probability.
  • Hardware Efficiency: By focusing on CPU-friendly operations (hash lookups and additions), DESSERT makes advanced semantic search feasible on cost-effective hardware, rather than requiring expensive GPUs for real-time inference.

Key Results

DESSERT demonstrates a significant improvement over the previous state-of-the-art, PLAID (an optimized version of ColBERT):

  • Speed: On the MS MARCO benchmark, DESSERT achieved a 2-5x speedup over PLAID.
  • Accuracy: This speedup came with a negligible drop in recall. For instance, DESSERT achieved a 96.0% Recall@1000 at roughly 32ms latency, while PLAID required 100ms to reach 97.5%.
  • Scalability: In synthetic tests, DESSERT was 10-50x faster than optimized PyTorch brute-force methods, with the performance gap widening as the number of vectors per set increased.
Figure 2: Query time for DESSERT vs. brute force on 1000 random sets of m glove vectors with the y-axis as a log scale. Lower is better.

Limitations and Future Work

While DESSERT is highly effective, the authors note a few areas for further exploration:

  • Hardness Assumptions: The theoretical guarantees rely on "standard LSH assumptions," such as having sufficiently high relevance scores and clear gaps between the best and second-best results.
  • Scale of Evaluation: Due to compute constraints, the authors limited their evaluation to established benchmarks. Testing on even larger, billion-scale document sets remains a future goal.
  • Broader Applications: The current work focuses on text retrieval, but the authors suggest DESSERT could be applied to other domains where "set-of-vectors" representations are natural, such as image similarity search, market basket analysis, and graph neural networks.

Summary updated

Abstract

We study the problem of $\textit{vector set search}$ with $\textit{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 $\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 (${\bf D}$ESSERT ${\bf E}$ffeciently ${\bf S}$earches ${\bf S}$ets of ${\bf E}$mbeddings via ${\bf R}$etrieval ${\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.
BibTeX
@inproceedings{engels2023dessert,
  author = {Joshua Engels and Benjamin Coleman and Vihan Lakshman and Anshumali Shrivastava},
  title = {{DESSERT: An Efficient Algorithm for Vector Set Search with Vector Set Queries}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=kXfrlWXLwH},
}
Figure