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

Joshua Engels, Benjamin Coleman, Vihan Lakshman, Anshumali Shrivastava

Summary

DESSERT is a novel approximate search algorithm designed for "vector set search," where both queries and database items are represented as collections of embeddings. By leveraging memory-efficient Locality-Sensitive Hashing (LSH) sketches, DESSERT achieves a 2-5x speedup over state-of-the-art models like ColBERT with minimal loss in accuracy, making high-performance semantic search viable for real-time CPU deployment.

Traditional similarity search focuses on finding the nearest neighbor to a single query vector. However, modern "late interaction" models for semantic search, such as ColBERT, represent a single document or query as a set of vectors (e.g., one embedding per word or token).

To rank a document, these models must calculate the similarity between every vector in the query set and every vector in the document set. While this approach is highly accurate, it is computationally expensive. Existing solutions are often too slow for production environments (like e-commerce) that require latencies under 20-30 milliseconds. The authors identify a critical gap: we have excellent tools for single-vector search, but we lack efficient, theoretically grounded algorithms for searching over sets of vectors at scale.

Introducing DESSERT

The authors introduce DESSERT (DESSERT Efficiently Searches Sets of Embeddings via Retrieval Tables). The core idea is to replace expensive vector-to-vector calculations with fast hash-collision counting.

DESSERT Indexing and Querying Process
  • LSH Sketches: DESSERT converts each vector in a set into a series of $L$ hash values using Locality-Sensitive Hashing (LSH). Instead of storing high-dimensional vectors, the index stores these compact "sketches."
  • Collision Counting: To estimate the similarity between a query vector and a document set, DESSERT simply counts how many times their hashes collide across the $L$ tables. This count serves as a proxy for the maximum similarity.
  • TinyTable: A major contribution is a custom, space-optimized hash table structure. Standard C++ containers like std::unordered_map have too much memory overhead for million-scale datasets. TinyTable uses a bit-packed, offset-based design that fits the index into RAM while maintaining $O(1)$ lookup speeds.
  • The Concatenation Trick: To handle datasets where vectors are naturally very similar (like GloVe embeddings), the authors concatenate $C$ hashes per table. This "sharpens" the probability curve, ensuring that only very similar vectors result in a collision.
  • Two-Stage Filtering: For massive datasets, DESSERT uses an initial coarse filtering step (using k-means centroids) to narrow the search space before applying the full sketch-based ranking.

Experimental Setup

The researchers evaluated DESSERT using three primary sources:

  1. Synthetic Data: Random groupings of GloVe word vectors used to measure raw algorithmic speedup against optimized brute-force implementations.
  2. MS MARCO: A massive, industry-standard passage ranking dataset containing approximately 8.8 million passages.
  3. LoTTE: A benchmark for "Long-Tail Topic Estimation" consisting of out-of-domain datasets across five categories: Lifestyle, Technology, Recreation, Science, and Writing.

Key Insights

  • Approximation is Sufficient: You don't need to find the exact nearest neighbor for every token in a sentence to determine if two sentences are semantically similar. Approximating the aggregate "MaxSim" score is enough for high-quality retrieval.
  • CPU-First Design: While many vector databases rely on GPU acceleration, DESSERT is specifically optimized for CPU hardware. This makes it significantly more cost-effective for large-scale deployments.
  • Theoretical Rigor: Unlike many heuristic-based search algorithms, the authors provide formal probabilistic bounds. They prove that with a specific choice of $L$ (number of hashes), DESSERT will return the top-ranked set with high probability.
  • Memory Bottlenecks: The paper highlights that for set-based search, memory management is as important as algorithmic complexity. The transition from standard hash tables to the "TinyTable" was essential for making the algorithm practical.

Key Results

DESSERT demonstrates massive performance improvements across multiple benchmarks.

Query Time vs. Set Size
  • Speed vs. Brute Force: On synthetic data, DESSERT was 10-50x faster than highly optimized PyTorch brute-force implementations, scaling exceptionally well as set sizes increased.
  • Speed vs. State-of-the-Art: When integrated into the ColBERT framework, DESSERT provided a 2-5x speedup over PLAID (the previous leading optimized implementation).
  • Latency: DESSERT achieved sub-30ms latencies on the MS MARCO dataset, meeting the "gold standard" for real-time production search.
  • Accuracy: The speedups came with minimal impact on retrieval quality. For example, on MS MARCO, DESSERT achieved an MRR@10 (Mean Reciprocal Rank) of 37.2 compared to PLAID's 39.2, while being nearly three times faster.

Limitations and Future Work

  • Hardness Assumptions: The theoretical guarantees rely on "sufficiently high" relevance scores and clear gaps between the top result and the rest of the field. In extremely "noisy" datasets where many documents are nearly identical, performance might degrade.
  • Scale of Evaluation: While 8.8 million documents is substantial, the authors note that even larger-scale evaluations (billion-scale) would further strengthen the case for DESSERT's scalability.
  • Domain Expansion: The current work focuses heavily on text retrieval. The authors suggest that DESSERT could be applied to other domains where "set-of-vectors" representations are natural, such as image similarity search (sets of visual features) or graph neural networks.

Summary updated

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