# LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search

arXiv: https://arxiv.org/abs/2410.18926 · HTML: https://mlsanity.com/paper/2410.18926/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 54 references that are in the map.
- First posted on arXiv 24 Oct 2024.

## Builds on (most cited first, 25 of 25)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [REPLUG: Retrieval-Augmented Black-Box Language Models](https://mlsanity.com/paper/2301.12652/) (2023)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Fast Transformers with Clustered Attention](https://mlsanity.com/paper/2007.04825/) (2020)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [Manu: A Cloud Native Vector Database Management System](https://mlsanity.com/paper/2206.13843/) (2022)
- [OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries](https://mlsanity.com/paper/2211.12850/) (2022)
- [SOAR: Improved Indexing for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.00774/) (2024)
- [GGNN: Graph-based GPU Nearest Neighbor Search](https://mlsanity.com/paper/1912.01059/) (2019)
- [A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.11731/) (2024)
- [Efficient Autotuning of Hyperparameters in Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1812.07484/) (2018)
- [A Multilabel Classification Framework for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1910.08322/) (2019)
- [Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search](https://mlsanity.com/paper/2403.01797/) (2024)
- [Pyramid: A General Framework for Distributed Similarity Search](https://mlsanity.com/paper/1906.10602/) (2019)
- [Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search](https://mlsanity.com/paper/2405.12207/) (2024)

## Built on by (most cited first, 4 of 4)

- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces](https://mlsanity.com/paper/2506.06557/) (2025)
- [EGA: Adapting Frozen Encoders for Vector Search with Bounded Out-of-Distribution Degradation](https://mlsanity.com/paper/2605.05674/) (2026)
- [Nearest-Neighbor Radii under Dependent Sampling](https://mlsanity.com/paper/2605.14343/) (2026)

## Abstract (arXiv)

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.