LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search
Elias Jääsaari, Ville Hyvönen, Teemu Roos
Abstract
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.
BibTeX
@inproceedings{
j{\"a}{\"a}saari2024lorann,
title={Lo{RANN}: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search},
author={Elias J{\"a}{\"a}saari and Ville Hyv{\"o}nen and Teemu Roos},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=wyYsCI3K7U}
}