$\alpha$-Reachable Graphs for Multivector Nearest Neighbor Search

Authors: Siddharth Gollapudi, Ravishankar Krishnaswamy, Sandeep Silwal, Kirankumar Shiragur, Harsh Wardhan, Ben Landrum, Nikhil Rao
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: Nearest neighbor Search, Graph-based Search, Multivector Retrieval

Abstract:
It is common in machine learning pipelines to embed every data point as an embedding in order to geometrically represent semantic relationships. However, the standard practice of using a single vector per data point may not be powerful enough to capture nuanced information in modalities such as text. Indeed, recent empirical evidence, such as the seminal ColBERT paper \citep{khattab2020colbert}, demonstrates the advantage of representing every data point as a collection of embeddings, and comparing data points via a \emph{multi-vector} similarity measure between collections of embeddings.

To accelerate the adoption of the multi-filter approach in large scale search and retrieval applications, efficient algorithms for nearest neighbor search for multi-vector similarities are needed. While many recent practical solutions have been proposed towards this problem, they are either limited to specific multi-vector similarities (such as the Chamfer distance used in ColBERT) or come with limited theoretical understanding. Our work aims to address this gap.

- On the theoretical side, we provide a provably efficient algorithm for approximate nearest neighbor search for a wide range of multi-vector similarities, including the Chamfer distance. 
-  Practically, we demonstrate that our approach can provide improved results for the common case of Chamfer similarity studied in prior empirical works. Our algorithm outperforms prior SOTA by up to **20\%** increase in QPS for comparable 1@100 recall, while achieving up to **2x** improvement for the challenging 100@100 recall setting.

The core of our approach lies in extending the well-known single-vector DiskANN algorithm, both in theory and practice, to the multi-vector setting in a black-box manner.

Decision: reject

Reviews and discussion:

Metareview: