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

We study the problem of $\mathit{\text{vector}}\mathit{\text{set}}\mathit{\text{search}}$ with $\mathit{\text{vector}}\mathit{\text{set}}\mathit{\text{queries}}$. This task is analogous to traditional near-neighbor search, with the exception that both the query and each element in the collection are $\mathit{\text{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 ($\mathbf{D}$ESSERT $\mathbf{E}$ffeciently $\mathbf{S}$earches $\mathbf{S}$ets of $\mathbf{E}$mbeddings via $\mathbf{R}$etrieval $\mathbf{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.