Abstract
We study the problem of vector set search with 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 sets of vectors. We identify this problem as a core subroutine for many web applications and find that existing solutions are unacceptably slow. Towards this end, we present a new approximate search algorithm, DESSERT (DESSERT Efficiently Searches Sets of Embeddings via Retrieval Tables). DESSERT is a general tool with strong theoretical guarantees and excellent empirical performance. When we integrate DESSERT into ColBERT, a highly optimized state-of-the-art semantic search method, we find a 2-5x speedup on the MSMarco passage ranking task with minimal loss in recall, underscoring the effectiveness and practical applicability of our proposal.
Introduction
Traditional vector search, or Approximate Nearest Neighbor (ANN) search, typically focuses on finding the closest single point in a high-dimensional space. However, modern "late interaction" models like ColBERT represent documents and queries as sets of vectors (e.g., one embedding per word or token). Comparing these sets is computationally expensive; to rank a document, one must compute a "sum of max similarities" between the query set and the document set.
Doing this via brute force across millions of documents is prohibitively slow for real-time applications like e-commerce, which often require latencies under 30 milliseconds. Existing optimizations are either heuristic-heavy or struggle to scale without massive hardware costs. DESSERT addresses this bottleneck by treating set-to-set comparison as a probabilistic counting problem.
The DESSERT Algorithm
DESSERT (DESSERT Efficiently Searches Sets of Embeddings via Retrieval Tables) leverages Locality-Sensitive Hashing (LSH) and a custom memory-efficient data structure to enable scalable vector set search.
LSH Indexing and Collision Counting
During indexing, every vector in a document set is passed through $L$ different LSH functions. Instead of storing raw vectors, DESSERT stores these hash values in a retrieval table. At query time, the algorithm hashes the query vectors and counts how many times they "collide" (share the same hash) with vectors in the document sets. The number of collisions serves as a proxy for the similarity between vectors, approximating the "MaxSim" operator used in models like ColBERT with high statistical confidence.
Hardware-Aware Design: TinyTable
To make this feasible on standard CPU hardware, the authors developed "TinyTable," a highly optimized C++ data structure. It uses offset lists and concatenated IDs to minimize memory overhead. This allows a million-document index that might normally require 196GB to fit into just 14.7GB. Additionally, a "Concatenation Trick" is used, where $C$ hashes are concatenated per table to narrow the collision window, ensuring only very similar vectors share a hash and reducing noise in similarity estimation.
Experimental Evaluation
The researchers evaluated DESSERT using three primary sources:
- Synthetic Data: Random groupings of GloVe word vectors used to measure raw algorithmic speedup against optimized PyTorch brute-force implementations.
- MS MARCO: A massive real-world passage ranking dataset (~8.8 million passages) used to evaluate performance in a standard web-search context.
- LoTTE: A benchmark consisting of 10 out-of-domain datasets (covering topics like Lifestyle, Technology, and Science) to test generalization across subjects.
Key Results and Insights
DESSERT demonstrates a superior position on the latency-vs-recall curve, offering a "sweet spot" for production systems that cannot afford the latency of exact search.
Performance Gains
- Significant Speedups: DESSERT achieved a 2–5x speedup over PLAID, the previous state-of-the-art optimized implementation for ColBERT.
- Brute Force Comparison: On synthetic data, DESSERT was 10–50x faster than highly optimized PyTorch brute-force matrix multiplication, especially as the number of vectors per set increased.
- Minimal Accuracy Trade-off: On the MS MARCO benchmark, DESSERT achieved a 96.0% Recall@1000 compared to PLAID’s 97.5%, but did so at a fraction of the latency (32.3ms vs 100ms).
Theoretical Rigor
Unlike many ANN heuristics, DESSERT comes with formal proofs. The authors provide probabilistic bounds on the number of hashes ($L$) required to ensure the top-ranked result is returned with high probability, assuming a sufficient relevance "gap" exists between the top document and the rest of the corpus.
Conclusion and Future Work
DESSERT provides a scalable, theoretically grounded solution for the emerging frontier of vector set search. While currently optimized for static search indexes (due to the TinyTable architecture), future work may explore dynamic updates. Furthermore, while tested on text retrieval, the vector set approach could potentially be extended to image similarity or graph neural networks.
Summary updated