Research map / Learning theory and algorithms / Matrix and tensor methods
LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes reduced-rank regression as a supervised score computation method for clustering-based ANN search, packaged in the LoRANN library with CPU and GPU implementations that beat PQ and several SOTA libraries on high-dimensional data.
Problem
Clustering-based approximate nearest neighbor search is scalable and memory-efficient but has slower query times than graph-based methods, mainly because its product-quantization score computation is slow.
Approach
Treat inner product approximation between a query and cluster points as a multi-output regression problem and solve it per cluster with a low-rank reduced-rank regression model trained on query samples, quantized to 8-bit integers, replacing PQ scoring.
Key results
- RRR with about 16 bytes per vector outperforms PQ even at about 64 bytes per vector on all data sets, and RRR@~16 bytes outperforms PQ@~128 bytes.
- LoRANN outperforms the product quantization methods on all data sets except glove-200-angular on the CPU benchmark.
- LoRANN outperforms the other GPU methods (IVF, IVF-PQ, CAGRA) on seven of the nine high-dimensional (d>300) data sets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace PQ scoring with reduced-rank regression | IVF ANN search · ANN data sets, fixed clustering | recall versus QPS | Helped |
| use RRR instead of PQ at similar bytes per vector | IVF ANN search · ANN data sets | recall versus QPS | Helped |
| add RRR score computation (ablation) | LoRANN · all tested data sets | performance | Helped |
| add dimensionality reduction (ablation) | LoRANN · high-dimensional data with moderate-sized corpora | performance | Helped |
| add dimensionality reduction (ablation) | LoRANN · lower-dimensional data sets (d ≤ 300) | performance | No clear effect |
| add 8-bit quantization (ablation) | LoRANN · ANN data sets | query latency | Helped |
| increase rank from 32 to 64 (ablation) | LoRANN · with final re-ranking | performance | No clear effect |
| decrease rank from 32 to 16 (ablation) | LoRANN · high-dimensional data | performance | Hurt |
| train using query-distribution samples instead of only corpus samples (ablation) | LoRANN · Yandex T2I OOD | recall versus QPS | Helped |
| increase query-distribution training set from 400K to 1.2M (ablation) | LoRANN · Yandex T2I OOD | recall versus QPS | Helped |
| select local regression training examples from routed nearby clusters rather than only the target cluster (ablation) | LoRANN · Yandex T2I OOD | regression accuracy | Helped |
| use LoRANN instead of product-quantization methods | ANN search libraries · CPU evaluation, all data sets except glove-200-angular | recall versus QPS | Helped |
Surprising findings
- The reduced-rank regression solution differs from a low-rank SVD factorization of the centroid/corpus matrix, and training on query samples gives more accurate models than training on the corpus alone for OOD queries.
- ScaNN does not outperform Faiss-IVFPQ in the end-to-end evaluation.
Limitations
- Graph methods remain more efficient at very high recall levels (above 90% for k=100).
- Reduced-rank regression is inefficient for low-dimensional data where r/d is large (e.g., d<100).
- Applicable only to inner-product-based dissimilarities; the regression formulation must be extended for other measures.
Experimental setup
Datasets: ag-news ann-arxiv ann-t2i arxiv (OpenAI Ada) arxiv (InstructXL) fashion-mnist fasttext-wiki gist glove mnist sift wiki (GTE-small)
Benchmarks: ANN-benchmarks ag-news ann-arxiv ann-t2i arxiv arxiv-instructxl fashion-mnist fasttext-wiki gist glove mnist sift
Metrics: recall@100 queries per second query latency memory usage (bytes per vector) index construction time
Baselines: Faiss-IVFPQ (fast scan) ScaNN HNSW GLASS QSG-NGT PyNNDescent MRPT CAGRA
Builds on: product quantization IVF-PQ ScaNN absmax quantization
Closest papers by meaning
- Efficient Large-Scale Approximate Nearest Neighbor Search on the GPU (CVPR 2016 · similarity 0.86)
- Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach (ICML 2026 · similarity 0.85)
- LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table (CVPR 2025 · similarity 0.84)
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.83)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.83)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.