DESSERT: An Efficient Algorithm For Vector Set Search With Vector Set Queries

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.

Stats

• citations1
• S2 citations—
• github stars0
• HF likes0
• heat score2.26
• arxiv keyengels2022dessert

Related papers

• Approximate Vector Set Search Inspired By Fly Olfactory Neural System (2024)0.00
• Vectorsearch: Enhancing Document Retrieval With Semantic Embeddings And Optimized Search (2024)0.00
• DEG: Efficient Hybrid Vector Search Using The Dynamic Edge Navigation Graph (2025)6.34
• Gleanvec: Accelerating Vector Search With Minimalist Nonlinear Dimensionality Reduction (2024)0.00
• Exqutor: Extended Query Optimizer For Vector-augmented Analytical Queries (2025)0.00
• Semantic Vector Encoding And Similarity Search Using Fulltext Search Engines (2017)6.77
• Leanvec: Searching Vectors Faster By Making Them Fit (2023)0.00
• Passing The Baton: High Throughput Distributed Disk-based Vector Search With Batann (2025)0.00