IGP: Efficient Multi-Vector Retrieval via Proximity Graph Index

Neural embedding models are extensively employed in retrieval applications, including passage retrieval, question answering, and web search. In particular, multi-vector models (e.g., ColBERTv2), which represent a document as multiple embedding vectors, have been demonstrated to achieve superior retrieval quality. Nevertheless, these models incur significant overhead at the retrieval time due to the massive amount of embedding vectors. Several promising proposals (e.g., PLAID, DESSERT, EMVB, and MUVERA) have been made to optimize the query latency. To yield high recall, these methods need to generate a considerable amount (e.g., ten thousands) of document candidates, rendering both the candidate generation phase and the refinement phase inefficient. In this paper, we propose a high-quality candidate generation technique that produces only hundreds of candidates yet achieves high recall. Specifically, we develop an incremental next-similar retrieval technique for a proximity graph index in order to facilitate high-quality candidate generation. Our experiments on real datasets show that our proposed method IGP achieves 2x-3x query throughput compared to existing methods at the same accuracy level.