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.
The Challenge of Vector Set Search
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.
- 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_maphave 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:
- Synthetic Data: Random groupings of GloVe word vectors used to measure raw algorithmic speedup against optimized brute-force implementations.
- MS MARCO: A massive, industry-standard passage ranking dataset containing approximately 8.8 million passages.
- 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.
- 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