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

• High-dimensional embeddings support similarity search in machine-learning pipelines, including semantic search and recommendation systems, where large data sets motivate ANN search.The introduction also names RAG, approximate Transformer attention, and vector databases as ANN use cases.Source: §1 · p. 1
• Clustering-based ANN is used at industrial scale because it has smaller memory footprints and faster index construction than graph-based methods, despite slower query times.Clustering methods also suit distributed and persistent-storage implementations.Source: §1 · pp. 1–2
• RRR treats inner-product estimation as multivariate regression, approximates the OLS solution with a low-rank model, and uses 8-bit computations to improve latency and memory use.The authors report that RRR is faster than PQ at any given recall level and memory usage.Source: §1 · p. 2
• LoRANN packages the proposed score computation method in a clustering-based ANN library with CPU and GPU implementations.The GPU implementation is motivated by RRR’s low memory use and simple computational structure.Source: §1 · p. 2
• LoRANN outperforms leading clustering-based libraries and high-dimensional GPU ANN methods, and is faster than GLASS below 90% recall on most data sets.The authors also report that RRR outperforms PQ at optimal hyperparameters and fixed memory consumption.Source: §1 · p. 2

2.1 ANN search

• ANN approximates the k nearest corpus points to a query under a dissimilarity measure; recall measures effectiveness, while query latency or QPS measures efficiency.Common dissimilarities include Euclidean distance, negative inner product, and cosine distance.Source: §2.1 · pp. 2–3

2.2 Clustering-based ANN search

• Clustering-based ANN partitions the corpus, commonly with k-means, and centroid-based routing selects the clusters closest to the query.The standard practice described here uses k-means clustering and centroid-based routing.Source: §2.2 · p. 3
• After routing, points in the selected clusters are scored, the top-scoring points form a candidate set, and reranking can evaluate their true dissimilarities.Clustering-based ANN is one form of partitioning-based ANN.Source: §2.2 · p. 3

3 Reduced-rank regression

• The method approximates cluster-local query-to-point dissimilarities as a multivariate regression problem and derives an efficient reduced-rank solution with 8-bit integer vector-matrix products.The section proceeds from regression formulation to low-rank approximation and quantized implementation.Source: §3 · p. 3

3.1 Dissimilarity approximation as a multivariate regression problem

• For negative inner product, Euclidean distance, and cosine distance, estimating inner products suffices to rank points, with corpus norms precomputable for Euclidean distance and unit normalization used for cosine.The regression output contains the query’s dissimilarities to the points in a cluster.Source: §3.1 · p. 3

3.2 Reduced-rank regression solution

• The model fits query vectors routed to each cluster, constrains the parameter matrix to rank at most r, and predicts with factors A and B in Θ(r(d + ml)) operations instead of Θ(dml) exact inner-product operations.The reduced-rank solution projects the OLS fit using the first r right singular vectors of the training outputs; the experiments use r = 32 across data sets with dimensions 128 to 1536.Source: §3.2 · pp. 3–4

3.3 8-bit quantization

• 8-bit quantization of the query and model matrices computes predictions with two integer vector-matrix products and yields RRR index memory of order Ldr + rm bytes.Random rotations are used before quantization to spread variance and limit precision loss.Source: §3.3 · p. 4

4 LoRANN

• LoRANN combines the standard clustering-based ANN template with the paper’s reduced-rank score computation method.Its implementation includes dimensionality reduction, quantization optimizations, and a GPU implementation.Source: §4 · p. 5

4.1 Dimensionality reduction

• Projecting queries and centroids into a lower-dimensional space reduces model memory from Ldr + rm to Lsr + rm bytes, while the original query is retained for final reranking.Dimensionality reduction is most useful for high-dimensional data with moderate-sized corpora; it does not improve performance on data sets with d ≤ 300.Source: §4.1 · p. 5, §4.2 · p. 5

4.2 Quantization implementation

• The implementation combines mixed precision and random rotations with 8-bit quantization, and stores matrices as unsigned 8-bit values for efficient CPU dot products.The first projected component and first rows of A and B remain unquantized to reduce precision loss.Source: §4.2 · p. 5

4.3 GPU implementation

• The GPU implementation batches query-to-model products as matrix multiplication and balances cluster sizes to reduce padding inefficiency.It uses 16-bit floating-point computation because 8-bit integer multiplication is less efficient and less supported on GPUs; the quantized representation can still help fit larger data sets in accelerator memory.Source: §4.3 · pp. 5–6

5 Out-of-distribution queries

• In cross-modal Yandex text-to-image search, image corpus points and text queries occupy the same vector space but have different distributions.Source: §5 · p. 6
• The Yandex OOD experiment compares query samples of 400K and 1.2M with corpus training, including local sets restricted to cluster points.The query-trained setups use query-distribution samples as global training sets; the corpus-local setup restricts each local training set to its cluster’s corpus points.Source: §5 · p. 6
• Query-trained LoRANN outperforms corpus-trained LoRANN, especially without reranking; larger training sets improve performance, and both outperform corpus-local.The authors suggest larger, more representative local training sets may explain the corpus-trained model’s advantage over corpus-local.Source: §5 · p. 6

6 Related work

• Supervised hashing and partition-learning methods optimize how corpus points are partitioned, while this work instead learns score computation.The passage names learning-to-hash methods (Weiss et al., 2008; Norouzi and Fleet, 2011; Liu et al., 2012) and partition-learning methods (Dong et al., 2020; Gottesbüren et al., 2024).Source: §6 · p. 6
• IVF-PQ and ScaNN use quantizers to approximate query-to-corpus dissimilarities, with product quantization decomposing features into subspaces and learned subquantizers.PQ code size, and thus memory consumption, is directly proportional to the number of subquantizers.Source: §6 · pp. 6–7
• On Yandex T2I OOD data, the caption reports benefits from query-distribution training and local training that includes points outside the cluster; reranking narrows the performance difference.The final reranking step requires retaining the original data set in memory.Source: Figure 1 · p. 7

7.1.1 Fixed clustering

• With the IVF clustering held constant, RRR outperforms PQ on seven of eight datasets.RRR uses r = 32, while PQ uses d/2 subquantizers for optimal performance.Source: Figure 2 · p. 8, §7.1.1 · p. 8

7.1.2 Memory usage

• At b ≈16 bytes per vector, RRR outperforms PQ at b ≈128, which uses eight times as much memory.The comparison varies RRR’s rank and PQ’s code size to match bytes per vector; the text also reports RRR at b ≈16 outperforming PQ at b ≈64 on all datasets.Source: Figure 3 · p. 8, §7.1.2 · p. 8

7.2.1 Ablation study

• Adding RRR score computation significantly improves performance on all datasets; the ablation figure reports that all components help at d = 768, while DR does not help at d = 200.The figure compares components against an IVF baseline.Source: §7.2.1 · p. 9, Figure 4 · p. 9
• Dimensionality reduction helps high-dimensional datasets with moderate-sized corpora, but does not improve datasets with d ≤300; 8-bit quantization improves memory use and query latency.DR is useful when the number of points in a cluster is below the dimension, making the first vector-matrix product more expensive.Source: §7.2.1 · p. 9
• Increasing r from 32 to 64 has little effect, while r = 16 performs worse on high-dimensional data but can further reduce memory use.The remaining experiments use r = 32.Source: §7.2.1 · p. 9

7.2.2 CPU evaluation

• LoRANN generally has faster index construction times than graph-based methods.Source: §7.2.2 · p. 9

7.2.2 CPU evaluation; 7.2.3 GPU evaluation

• CPU QPS-recall curves cross GLASS between 80% and 99% recall on most datasets; GPU LoRANN leads on 7 of 9 high-dimensional sets, while CAGRA leads at d ≤300.On the representative CPU comparison, the curves cross at 95% and 90% recall; on GPU, LoRANN is fastest at d = 768 and CAGRA at d = 200.Source: §7.2.2 · p. 9, §7.2.3 · p. 9, Figure 5 · p. 10

7.2.3 GPU evaluation

• On an Apple M2 Pro, LoRANN uses the M2 GPU and unified memory architecture to achieve faster queries.Source: §7.2.3 · p. 10

8 Discussion

• RRR is presented as an efficient score-computation method for clustering-based ANN, with small memory use and a simple computational structure.The authors recommend it in memory-limited regimes traditionally using PQ; experiments use the standard in-memory setting, while SSD-based hybrid and distributed settings are future research directions.Source: §8 · p. 10
• Graph methods are usually more efficient when recall exceeds 90% for k = 100, because reaching that level requires exploring many clusters.RRR is also inefficient on low-dimensional data when the required rank-to-dimension ratio r/d is too large; its score computation applies only to inner product-based dissimilarities, though the regression formulation can be extended.Source: §8 · p. 10

A Geometric intuition

• When X = C, RRR predictions equal inner products after projecting the query and cluster points onto the first r eigenvectors of K = C^T C.In this special case, centered cluster points make those eigenvectors the principal axes, but inner-product estimation should not center the data because inner products are not translation-invariant.Source: A Geometric intuition · p. 14
• For general X ≠ C, the training-query matrix also affects the right singular vectors of Y = XC^T, so RRR has no simple geometric interpretation in the original feature space.The discussion notes that factorizing XC^T can yield a more accurate model than truncating an SVD of C; the solutions are equivalent only when X = C.Source: A Geometric intuition · p. 14

B Experimental set-up

• Experiments use AWS r6i.4xlarge instances with hyperthreading disabled, and each algorithm runs on a single core.GPU experiments use an AWS g5.2xlarge with an NVIDIA A10G GPU and a mac2-m2pro.metal instance with an Apple M2 Pro SoC.Source: B Experimental set-up · p. 15
• The evaluation measures recall, the proportion of true k-nn found, against queries per second, using k = 100 throughout.Each dataset has a separate 1,000-query test set; every hyperparameter combination is benchmarked five times, and the lowest query latency is recorded.Source: B Experimental set-up · p. 15
• The experiments use the same hyperparameter grid for L, w, and t as the LoRANN experiments when evaluating RRR alone, but omit dimensionality reduction.The passage refers to the LoRANN grid described earlier.Source: B Experimental set-up · p. 15
• The paper reports that full hyperparameter settings are available in the lorann-experiments repository.The provided passage gives the repository address.Source: B Experimental set-up · p. 15

C Data sets

• The experiments add neural-network embedding datasets with dimensionalities from 200 to 1536 alongside fashion-mnist, gist, glove, mnist, and sift.Table 1 lists the datasets, their sizes, and the distance metrics used.Source: C Data sets · p. 16, Table 1 · p. 16

D.1 Fixed clustering

• The fixed-clustering evaluation compares RRR with PQ while keeping the k-means clustering fixed.The passage directs readers to Section 7.1.1 for discussion; the supplied text gives no outcome values.Source: §D.1 · p. 17

D.2 Memory usage

• A separate evaluation compares RRR and PQ across different memory consumptions.The supplied passage provides the evaluation scope but no result values.Source: §D.2 · p. 18

D.3 Memory usage (no re-ranking)

• The no-re-ranking evaluation compares RRR and PQ across memory consumptions without a final re-ranking step.In this scenario, the original dataset does not need to be kept in memory; no outcome values are supplied.Source: §D.3 · p. 19

E.1 Ablation study

• The ablation study examines reduced-rank regression, dimensionality reduction, and 8-bit quantization as LoRANN components.Source: §E.1 · p. 20

E.2 Effect of the rank

• With final re-ranking, increasing r from 32 to 64 has little effect; r = 16 performs only slightly worse on high-dimensional data.The experiments use r = 32; r = 16 can reduce memory, while r = 64 can increase recall without final re-ranking.Source: Figure 7 · p. 21, §E.2 · p. 21

E.3 CPU Evaluation

• The CPU evaluation section presents a complete evaluation of LoRANN against other ANN algorithms in the CPU setting.Source: §E.3 · p. 22

E.4 Index construction time

• Table 2 reports index-construction times in seconds at 90% recall for k = 100 and optimal hyperparameters; dashes indicate missed recall or memory exhaustion.The LoRANN index-construction implementation was not optimized; further sampling and more approximate SVD computations could improve it.Source: Table 2 · p. 24, §E.4 · p. 24

E.5 GPU evaluation

• 2–5 times faster query latencies: MLX LoRANN using the M2 Pro GPU and unified memory versus the C++ LoRANN implementation without quantization.The comparison includes MLX CPU and GPU LoRANN and MLX IVF on the M2 Pro.Source: §E.5 · p. 26

NeurIPS Paper Checklist

• The authors report code for LoRANN and the benchmarks, including data preparation, with repository instructions for running experiments.Source: NeurIPS Paper Checklist · pp. 28–29
• The paper reports no error bars or statistical significance tests, citing computational expense and ANN-search field practice.Source: NeurIPS Paper Checklist · p. 29
• The authors characterize the work as foundational ANN-search research with no direct societal impact.Source: NeurIPS Paper Checklist · p. 30