LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search
This work addresses the need for faster and more efficient ANN search in applications like retrieval-augmented generation and vector databases, though it is incremental as it builds on existing clustering-based methods.
The paper tackled the problem of slow query times in clustering-based approximate nearest neighbor (ANN) search by proposing a new supervised score computation method based on reduced-rank regression, which improved query latency and memory usage on high-dimensional datasets, making LoRANN competitive with leading graph-based algorithms.
Approximate nearest neighbor (ANN) search is a key component in many modern machine learning pipelines; recent use cases include retrieval-augmented generation (RAG) and vector databases. Clustering-based ANN algorithms, that use score computation methods based on product quantization (PQ), are often used in industrial-scale applications due to their scalability and suitability for distributed and disk-based implementations. However, they have slower query times than the leading graph-based ANN algorithms. In this work, we propose a new supervised score computation method based on the observation that inner product approximation is a multivariate (multi-output) regression problem that can be solved efficiently by reduced-rank regression. Our experiments show that on modern high-dimensional data sets, the proposed reduced-rank regression (RRR) method is superior to PQ in both query latency and memory usage. We also introduce LoRANN, a clustering-based ANN library that leverages the proposed score computation method. LoRANN is competitive with the leading graph-based algorithms and outperforms the state-of-the-art GPU ANN methods on high-dimensional data sets.