LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search
Authors: Elias Jääsaari
Ville Hyvönen
Teemu Roos
Venue: NeurIPS 2024 poster (2024)
Keywords: Approximate nearest neighbor search
vector search
k-nn search
multivariate regression
vector databases
Primary area: infrastructure

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.

LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search
Elias Jääsaari Ville Hyvönen Teemu Roos f Department of Computer Science, University of Helsinki *Dpaarmeent of Computer Science, Aalto University {elias. jaasaari, teemu. ttwteeeoos @hessihelsinkiii.. ffi; ville. 2.hyvonen@aalto.fr
Abstract
Approximate nearest neighbor (ANN) search is a key component in many modern machine learning pipelines; recent use cases include retrieval -aggevelee gener- ation (RAG) and vector databases. Clustering-basee -baind 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 new supervised score computation method based on the observation that inner product approx- imation is multivariate (multi-output) regression problem that can be solved efficiently by reduced-rank regression. Our experiments show that on modern nigh-dimensional data sets, the proposed reduced-rank regression (RRR) method is superior to PQ in both query latency and memory usage. We also introduce LORANI" clustering-basee based ANN library that leverages the proposed score compu- tation method. LORANN is competitive with the leading graph- based algorithms and outperforms the state-of-the-art GPU ANN methods high-dimensional data sets.
Introduction
In modern machine learning applications, data is often stored as embeddings, i.c., as vectors in high-ddmensiionl vector space where representations of semantically similar items are close to each other. Consequently, similarity search in high-dimensional vector spaces is a key algorithmic primitive used in many pipelines, such semantic search engines and recommendation systems. Since the data sets are usually both large and high-dimensional, approximate nearest neighbor (ANN) search is deployed to speed up similarity search in many applications (Li et al. 2019).
Recent use cases of ANN search include retrieval- -aggmente generation (RAG) (Lewis et al. 2020 Guu et al. 2020 Borgeaud et al. 2022; (Shi et al. 2024) and approximate attention computation in Transformer- based architectures Kitaev et al. [2020] Vyas et al. 2020 Roy et al., (202I). ANN search is also key operation in vector databases that used to store embeddings for industrial-scale applications (see, c.g.. Wang et al. 2021 Guo et al. 2022 Pan et al. 2024).
The state-of-the-art methods for ANN search can be classified into clustering based and graph-based algorithms (for a recent survey, see see Brruh] (024). In the comprehensive ANN benchmark (Aumüller et al.] (2020), the leading graph algorithms HNSW (Malkov and Yashunin (018)) and NGT (Iwasaki and Miyazaki (218)) have faster query times than clustering-based algorithms. However, clustering- based algorithms are often used in industrial-scale applications (see, e.g., Chen et al. 2021 Douze
al. 2024) due to their smaller memory footprints and faster index construction times. They are
httpp:///gthabb..cm//jaaaaaaarrt
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

also suitable for distributed implementations and hybrid solutions that use persistent storage such as SSDs or blob storage (Chen al. 2021 Gottesbüren et al.) 2024).
The key components of clustering- algorithms are clustering and score computation. In the indexing phase, the corpus, i.e., the data set from which the nearest neighbors searched, is partitioned via clustering. In the query phase, w clusters are selected and the corpus points that belong the selected clusters are scored. The points with the highest scores are selected into candidate set
that can be further re-ranked. The state-of-the-at clustering- algorithms (Jegou et al. 201T
Guo et al., 2020; Sun al. 2023) use variants of product quantization (PQ) (Jegou et al., 2011 with highly optimized implementations (see, e.g., André et al., 2015) for score computation.
In this article, we propose supervised score computation method that improves the query latency of clustering- -based ANN methods, making them competitive with the leading graph algorithms. Our key observation is that estimating the dissimilarities between the query point and the cluster points is a multivariate (multi-outputt) regression problem. For the most common dissimilarity measures, sufficient to estimate the inner products between the query point and the cluster points, and the ordinary least squares (OLS) estimate is the exact solution for this regression problem. The proposed method approximates the OLS solution by reduced-rank regression (Izenman 1975). We further approximate the reduced-rank regression estimates using 8-bit integer computations, improving query latency and memory consumption. Reduced-ran regression (RRR) a simpler method than PQ. and our experimental results show that it is faster at any given recall level and memory usage.
To make our work available for practical applications of ANN search, introduce LORANN, clustering- ANN library that leverages the proposed score computation method. Since the low memory usage and the simple computational structure of reduced-rank regression make it well-suited for GPUs, LORANN also includes GPU implementation of the proposed method.
In summary, our contributions are:
We propose reduced-rank regression (RRR) as a new supervised score computation method for clustering-basee ANN search (see Section 3)
We verify experimentally that RRR outperforms PQ both at the optimal hyperparameters (Section 7.1.1) and at fixed memory consumption (Section 7.1.2). and that it naturally adapts
to the query distribution in the out-of-distriuttion (OOD) setting (Section 5).
We introduce LORANN, a clustering-based ANN library that contains efficient CPU and GPU implementations of the proposed score computation method (Section 4
We show that LoRANN outperforms the leading clustering- libraries Faiss (Douze et al. 2024) and ScaNN (Guo et al./ (200)), and has faster query times than the leading graph- based library GLASS at recall levels under 90% on most data sets (Section 7.2.2) LORANN outperforms the SOTA GPU methods on high- nigh-dimensional data (Section 7.2.3).
2
Background
In this section, we first review the notation of approximate nearest neighbor (ANN) search and then describe the standard structure of clustering- based ANN algorithms.
2.1 ANN search
Let x E Rd be a query point, and let (c, 1 C Rdd be the corpus, i.e., the set of points from which the nearest neighbors retrieved. The k nearest neighbors of defined as
(x; {c,) d) = (i E [m] d(x, c,) S d(x, c())),,
(I)
where d: Rdd + R is a dissimilarity measure, C(1), ... ((m) denote the corpus points that are ordered in ascending order w.r.t. their dissimilarity to the query point x, and [m]] = m..
Commonly used dissimilarity measures are the Euclidean distance d(a, b) = | bl 2, the (negative) inner product a, b) = - (a,, b), and the cosine (angular) distance d(a, b) = 1 (a/||a |2, bll The special case where the dissimilarity measure is the negative inner product is often called maximum inner product search (MIPS) (see, e.g., Guo et al. 2020 Lu et al. 2023. Zhha et al., (023). In ANN search, the exact solution NN₃ (x: (c, is approximated.

---

The effectiveness of ANN algorithms is typically measured by recall, i.e., the fraction of the true k nearest neighbors returned by the algorithm. The efficiency is measured by query latency or, equivalently, by queries per second (QPS) (see, e.g., .s.,Lies al. 2019 Aumüller et al. 2020).
2.2
Clustering-based ANN search
Partitioning- ANN algorithms, such as tree-based (e.g., Muja and Lowe 2014 Dasgupta and
Sinha 2015 Jääsaari et al. 2019) and hashing-based algorithms (e.g.. Charikar 2002 Weiss et al. 2008
Liu et al.120111 l). build an index by partitioning the corpus into L. elements. In the query phase,
they use routing function F [L] to assign the query point into partition elements.
Clustering- -bsend ANN algorithms (see, e.g., Bruch 2024, Chapter 7) are partitioning- -baed ANN algorithms that partition the corpus via clustering. ANN indexes based on clustering are also often called inverted file (IVF) indexes (Jegou et al. 201T). The most commonly used clustering method is k-means clustering, specifically standard k-means when the dissimilarity measure d is the Euclidean distance, and spherical k-means (Dhillon and Modha 2001) when is the inner product or the cosine distance. While there exists recent exploratory work on alternative query routing methods (Gottesbüren al. 2024 Vecchiato al.) 2024 Bruch et al., 2024), the most common method centroid-based routing where, for the set (14 [= of cluster centroids,
7 7x) = (x; (1))
i.e. the w clusters whose centroids are closest the query point are selected. We follow this standard practice by using k-means clustering with centroid- routing. However, the proposed score computation method can be combined with any partitioning and routing method.
After routing, the corpus points that belong to the selected w clusters are scored (see Section 6 for discussion of score computation methods), and the / highest scoring points are selected into the candidate set. This candidate set can be re-ranked by evaluating the true dissimilarities between x and the candidate points. Finally, the k most similar points returned the approximate k-nn.
3 Reduced-rank regression
In this section, derive the proposed supervised score computation method. First, we formulate dissimilarity approximation as a multivariate regression problem. We then show how the exact OLS solution to this problem be approximated by reduced-rank regression (RRR). Finally, we show how RRR can be implemented efficiently using 8-bit integer vector-matrix multiplications.
3.1 Dissimilarity approximation as a multivariate regression problem
We consider the task of approximating the dissimilarities d(x, cj) between the query point and the corpus points Cj that belong to the Ith cluster. Denote the set of the indices these corpus points by I, their number by m, := [t], and the matrix containing them as rows by C, E mi In what follows, avoid cluttering the notation, matrices, e.g., we denote C₁ by C. We also assume, w.l.o.g.. that the corpus is indexed so that multivariate regression problem where the
drop the subscript / denoting the cluster from be formulated
1, = (1, (1,.... .., output is defined as a 1 x my matrix = [y1 y,,, where y = d(x, c₁) for each l,..., my,
.......,.... m. This task
We consider the cases where d is the (negative) inner product, the Euclidean distance, the cosine (angular) distance. In all three cases, it is sufficient to estimate the inner products. For Euclidean distance, arg minjer, ||x cyll2 arg min (-2x"c, c, + ||c,112), where the norms ||cy|la can be precomputed. For cosine distance, arg minjer, (1 cos(x, c,)) arg minjer, (-x"c,, the corpus points are normalized to have unit norm.
3.2 Reduced-rank regression solution
We approximate the exact solution y CT of the regression problem defined in the previous section by low-rank approximation. We assume the standard supervised learning setting, i.e., that we have sample [x,]__ from the query distribution Q (the corpus can also be used as the training set if no separate training set is available). To train the lth model, use all the training set points that
3

---

are routed into the /th cluster. When the standard centroid- routing is used, these are the training set points that have μr, i... the centroid of the Ith cluster, among their closest centroids. Denote the set of indices of these training set points by JI == {i [n] I E =xx))), and their number by ny = -Jl. The output values of the training set of the Ith model are given by Y == XCT E [R where we denote by X E Ruex the matrix containing the training set points {x. as rows.
To approximate the dissimilarities between the query point x and the cluster points {c, hee. we consider the linear model x" x"3, where 3 E Rdxm: is a matrix containing the parameters of the model, and minimize the mean squared error Ex~ dolly-x"x 11 E r(x)] (the indicator function selects the query points that routed into the Ith cluster). The unconstrained least squares solution foos = CT reproduces the exact inner products y = x" CT. In order to reduce the computational complexity of evaluating the model predictions, we constrain the rank of the parameter matrix: (3) < r < min(d, my). Under this constraint, the parameter matrix can be written using a low-rank matrix factorization 3 = AB, where A E Rdd and B E R"X", and, consequently, the model predictions ý (x" A B can be computed with (rr(d + m²) operations. When the rank is sufficiently low, this is significantly faster than computing the exact inner products which requires O ((dm)) operations. Our experiments (Section 7 indicate that fixing this hyperparameter works well with a wide range of data sets encompassing dimensionalities between 128 and 1536.
= 32
The optimal low-rank solution can be found by minimizing the training loss
BRRR=
arg min
|| 1x33
B (ink(3))r
where || || is the Frobenius norm, This is the well-known reduced-rank regression problem (Izenman 1975). Denote the singular value decomposition (SVD) of Y as Y = -UEV", where Σ is non-negative diagonal matrix and U and V orthonormal matrices. The standard reduced-rank regression solution is ARRR V, VT V.
AB, where V, E TR denotes the matrix that contains the first r columns of V (i.e., the first r right singular vectors of the least squares fit Y = XCT). A = CTV,,, r. and B == V In practice, we fast randomized algorithm (Halko et al. 2011) to compute only V, instead of the full SVD. Observe that the reduced- rank regression solution is different from the most obvious low-rank matrix factorization of the OLS solution computed via an SVD of the matrix C (see Appendix A
3.3
8-bit quantization
The simple computational structure of the reduced-rank regression solution enables us to further improve its query latency and memory consumption by using integer quantization. For each cluster, we quantize the matrices A and B to 8-bit integer precision. By also quantizing the query vector (x" A)B can be computed efficiently in two 8-bit integer Dettmerss et al.) (022). where the elements of vector are scaled to the range 127, 127] by multiplying with constant Cx such that X/32| = (5xxx332] where [-] denotes rounding to the nearest integer.
x, the model prediction ý = xx" x vector- matrix products. We use absmax quantization
X;s = [127/||xxazl]
We quantize the matrices A and B by applying absmax quantization to each column of the given matrix, resulting in vectors Ca and cn of scaling constants, We can then recover a 32-bit floating point approximation to the vector-matrix product
x²' A with
r:32 2 CA =: =: C r: = s о x T A - s Q(x) ((A)32))
r r33
Cx
where Q(-) denotes absmax quantization, and Ø and denote element-wise division and multiplica- tion, respectively. To compute y = r' B in the same fashion, we can first re-quantize r.
To ensure minimal loss of precision from the quantization, we rotate x before quantization by multiplying x with a random rotation matrix; this spreads the variance among the dimensions of x. Similarly, we rotate the vector r resulting from the first product r = x" " before re-quantization. Since A = C V, and B V we can rotate r by rotating V, beforehand at no extra cost.
Memory usage Storing each matrix Ais E [Z] takes dr bytes and each matrix B E [ F
256
takes rm; bytes. Thus in a clustering- total memory consumption of RRR is of order Ldr + rm bytes. In our experiments (Section we use = 32 for all data sets, while L is typically of order vm.
ANN index with L clusters and m corpus points, the
4

---

4 LoRANN
In this section, we describe the additional implementation details of LORANN, an open-source library that combines the standard template of clustering- based ANN search described in Section 2.2 with the score computation method described in Section 3 Using dimensionality reduction is particularly efficient for RRR (Section 4..1 and works well with 8-bit integer quantization (Section Finally, we describe the GPU implementation of LORANN (Section 4.3
4.1 Dimensionality reduction
With a moderate corpus and high-dimensionll data, computing the first vector matrixx product of the model prediction ý = (x" A B can be more expensive than the second. In LORANN, we further approximate the product by first projecting the query into a lower- liwee-dimesiionll space. We use the projection matrix W. E Rdx* whose columns are the first s eigenvectors of X X
global X glohal where Xglobul E nnd is the matrix containing the training set points {x; 1 To estimate the reduced-rank regression models, we use the s-dimensional approximations x; W x; as inputs, but the true inner products x!" Cj as outputs. In this case, the reduced-rank regression estimate of the /th model is 3RRuR= BOlS V, V. solution, and V, E R is the matrix whose columns are the first r right singular vectors of Y. Thus, now A
VYV,
R*xm, where BOLS == (XW,) 'Y is the full-rank
YVV, Rexr and B = V Rrxxm
We observe that computing performance improvement. In the indexing phase, we perform k-means clustering using č2 W cj. In the query phase, the s-dimensional approximation of the query point, X = -W x, is used to compute the distances to the cluster centroids and the predictions ý x BRRR. The original d-dimensional query point x is used for the dissimilarity evaluations in the final re-ranking step.
distances in the s-dimensional space yields a minor
4.2 Quantization implementation
The dimensionality reduction works particularly well with the 8-bit integer quantization described in Section 3.3 After dimensionality reduction, the first component of x corresponds to the principal axis. Thus, to further reduce the precision lost by quantization, we employ by not quantizing the first component of X and the first row of both A and B. Moreover, by pre- multiplying the projection matrix W, with a random rotation matrix, we rotate the query point x at extra cost before quantization. For re-quantizing B V we can again randomly rotate V, beforehand at no extra cost.
sixxedprecisson decomposition
x A, since A (XW.) YV, and
We compute the 8-bit vector-matrix products r,32 X A and f:32 = =r.B Bis efficiently modern CPUs using VPDPBUSD instructions in the AVX-512 VNNI instruction set Since a VPDPBUSID instruction computes dot products of signed 8-bit integer vectors and unsigned 8-bit integer vectors,
store As and B&s unsigned 8-bit integer matrices A A 128 1 [Z]dxr and
B' B + 128- 1,xm 2 Zrrxm and compute r;32 A A 128 x 1xx- The
dimensionality reduction lowers the memory usage of LoRANN from Ldr + rm to Lsr + rm bytes.
4.3 GPU implementation
Hardware accelerators such as GPUs and TPUs can be used to speed up ANN search for queries that
arrive in batches (Johnson et al.) 2019: Zhao et al., 2020; Groh et al., 2022: Ootomo et al. 2023). The computational structure of RRR, consisting of vector-matrix multiplications, makes easy to implement LORANN for accelerators, and the low memory usage of RRR (see Section 7.1.2) makes it ideal for accelerators that typically have a limited amount of memory.
Given a query matrix Q R with IQ) queries, need compute the products q. A, Ba for all i == 1, 1,..,, Q) and 1 1, 1,..., w. Here we denote by Aa and B, the matrices A and B of the Ith cluster in the set of w clusters the ith query point is routed into. We compute the required products efficiently using one batched matrix multiplication QT AT by representing Q as a r tensor Ar. and the matrices
[Q] 1 x d tensor Qr. the matrices Au as one Q w X
https://en.. htw.tchpp.oorg/ii/////e/////////
5

---

By as one [Q] x w x r x M tensor Br, where M is the maximum number of points in a single cluster. To avoid inefficiencies due to padding clusters with fewer than M points, we use an efficient balanced k-means algorithm (de Maeyer et al. 2023) to ensure that the clusters are balanced such that the maximum difference in cluster sizes
16.
On GPUs, 8-bit integer multiplication is presently both less efficient and less supported than 16- bit floating-point multiplication. Therefore, we use 16-bit floating-point numbers to perform all computations on GPU. However, the 8-bit quantization scheme can still be useful on accelerators by allowing bigger data sets be indexed with limited memory.
The simple structure of our method allows it to be easily implemented using frameworks such as PyTorch, TensorFlow, and JAX. This enables LORANN to support different hardware platforms with minimal differences between implementations. We write our GPU implementation in Python using JAX which uses XIA compile and the algorithm on GPU or TPU (Frostig et al. 2018).
5 Out-of-distribution queries
In the standard benchmark set-up (Li et al. 2019 Aumüller et al.) 2020). a data set is randomly split into the corpus and a test set, i.e., the corpus and the queries are drawn from the same distribution. However, this assumption often does not hold in practice, for example in cross-modal search. Thus, there is recent interest (Simhadri al., 2022; Jaiswal al.) 2022 Hyvönen al.) (022) in the out-of- oit-o---iitriuttionn (OOD) setting. For instance, in the -undex-text-to- -o-iimaee data set, the corpus consists of images, and the queries are text; even though both the corpus and the queries are embedded in the same vector space, their distributions differ (see Figure 2 in Jaiswal et al. (022).
Due to the regression formulation, the proposed method handles OOD queries by design. To verify this, we construct an index for sample of 400K points of the Yandex OOD data set in four different scenarios: (1) the default version MOORANN-quera query distribution, as a global training set and selects the local training set (xe, as the global training set points that are routed into the /th cluster; (2) LoRANN-query-bil
uses {x, )x)]== i.e.,
400K sample from the
like LORANN- -uuery, uses the corpus {c,} as a global training set, and selects the local training sets as {c, hee,,,, like the default version; (4) MoRANNN-corpus-locee
but with n = 1.2M; (3) LORANN-Corpen
uses { as global training set, but selects the local training sets as {c, he i.e., uses only the corpus points of the /th cluster train the Ith model. We can thus disentangle the effect of the choice of the global training set from the effect of using the points in the nearby clusters to train the RRR models.
The results are shown in Figure T The version trained queries outperforms the version trained only on the corpus, especially in the case of no re-ranking. Furthermore, we can use larger training sets to increase the performance of LORANN. Both LoRANN-query and LoRANN-corpus outperform CCRAANN-orpps-locaa
indicating that selecting the local training sets as described in Section (3.2 improves the accuracy of the regression models. We assume that this is because of the larger and more representative training sets, even though they are not from the actual query distribution.
6 Related work
Supervised A ANN algorithms Learning-to-har methods (Weiss al. 2008 Norouzi and Fleet
2011 Liu et al. 2012) optimize partitions in a supervised fashion using data data-dependent hash functions. Other supervised methods include learning optimal partitions by approximating a balanced graph partitioning (Dong et al. 2020 Gupta et al. 2022 Gottesbüren et al. 2024) and interpreting partitions as multilabel classifiers (Hyvönen al.) 2022). These supervised methods are orthogonal to our approach since they define the learning problem as selecting a subset of corpus points via partitioning. In contrast, we propose a supervised score computation method for clustering- based or, more generally, for partition-based ANN algorithms.
Product quantization The saute-of-the-are clustering based algorithms IVF-PQ (Jegou et al. 2011 and ScaNN (Guo et al. 2020) use quantization for data compression and score computation. They use a quantizer g R A to map a point of the feature space to value in a codebook A. Given A, they approximate the dissimilarity between the query point x and the corpus point ej by d(x, q(c,)), ie., the dissimilarity between the query point and the codebook value corresponding

---

yandex 200-an0a
yandex 2andexx400K2200aanguuarr
Queries per second (US)
Queries secoidd (1IS)
204
101
prann-corpus
lorann crann--orpus--ee socal
forantt-comm corpus
lorenn-corpus
errann-uuery
lorani-querry lorann-querr-biig
lorann-query-biig
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
0.5
0.6
0.7
0.8
0.9 1.0
Rocall
Recall
Figure Recall vs. QPS on the Yandex T2I OOD data set (400K sampled corpus points) without (left) and with (right) the final re-ranking step. LoRANN-Query is trained using a sample of 400K points from the query distribution as a training set, while LoRANN-query- -big uses a sample of 1.2M points. JORANN-Corpul is trained using the corpus as training set. LORANN-Corpus -oocal is trained using the corpus as training set with only the cluster points as the local training sets of the reduced-rank regression models. It is beneficial to (1) use sample from the actual query distribution as a training set and to (2) select the local training set by using also the points outside of the cluster as described in Section 3.22 The performance difference decreases when the final re-ranking step is introduced (requiring the original data set to be kept in memory).
to Cj. Further, IVF-PQ and ScaNN quantize the residuals, i.e., the distances between corpus points and the cluster centroids, and use product quantization that decomposes the feature space into lower- dimensional subspaces and learns subquantizers in these subspaces. The code size, and thus the memory consumption, of PQ is directly proportional to the number of subquantizers.
7 Experiments
We use the ANN-benchmarks project (Aumüller al. 2020) to run our experiments and replicate its experimental set-up as closely as possible (see Appendix for the description of the experimental set- up). We use A = 100 for all experiments and measure recall (the proportion of true k-nn found) versus queries per second (QPS). Additionally, due to the lack of modern high-dimensional embedding data sets ANN- benchmnaasr,s we include multiple new high-dimensional embedding data sets in our experiments; for a description of all the data sets, Appendix
Note that, even though we demonstrated Section that LORANN can adapt to the query distribution, there are no samples from the actual query distribution available for the benchmark data sets of this section. Thus, we follow the standard approach by using only the corpus {c, ) train LORANN.
7.1 Reduced-rank regression
We first compare the proposed score computation method, reduced-rank regression (RRR), against product quantization (PQ) for clustering- based ANN search We use RRR and PQ as scoring methods for an IVF index that partitions the corpus using k-means (see Section 2.2 We implement RRR using b-bit integer quantization as described in Section 3.3 and compare against product quantization implemented in Faiss (Douze et al., (024) with 4-bit integer quantization and fast scan (André et al.) 2015). First, we compare the score computation methods at the optimal hyperparameters while keeping the clustering fixed, and then compare them at fixed memory budget.
"Since ScaNN does not outperform Faiss-IVFPQ our end- end-to-end-oee tod-too-nd-evlluatio (Section 7.2.2) and both methods employ k-means for partitioning, the anisotropic quantization (Guo et al. 2020) used by ScaNN is unlikely outperform the original PQ [Jegou al. 201I).

---

7.1.1 Fixed clustering
To directly compare the score computation methods, in Figure we present results where the IVF index (the partition defined by f--means clustering) is the same for both methods. For RRR,
r = 32, while for PQ each vector is encoded with d/2 subquantizers for optimal performance. RRR outperforms PQ seven out of the eight data sets; for complete results, see Appendix D.1
awil-inssrruttd--E8-aaqquuu
onxiv-openai-Bn 1wt.ppnnnn--13-annngguur
Querles per second (1,8)
IVF RAR Tours. 2048)
IVF RRR jouns, 2048:
PO jours. 1024)
1024)
2048)
PO (tilss, 2048)
1024)
10a
0.60
0.65
0.70
0.75
0.80
0.85
1.00
0.60
0.65
0.75
0.50
0.90
1.00
Figure 2: Performance comparison between RRR and PQ. The k-means clustering (IVF index) is kept constant to directly compare the effect of the score computation method (here denotes the number of clusters). The proposed score computation method outperforms the baseline method (PQ).
7.1.2 Memory usage
In Figure we compare the performance of RRR (IVF+RRR) and PQ (IVF+PQ) by varying the rank parameter r for RRR and the code size for PQ such that b. bytes per vector, is similar for both. For all values of 6, RRR outperforms PQ which is a typical choice in memory-limited use cases. Note that RRR with 16 outperforms PQ even with 64 on all data sets; for the full results, see Appendix D.2
The results are similar when no final re-ranking step is used (Appendix D.3
anriviinstructt--66--nqqu.
amkiv-openall1533--nnull
Querres per second (35))
Quertes second
100
10"
PO (fiis. 64)
IVF PO (hiss. 58
IMF PQ (faiss. 22)
IVF
PO ftais. 32)
IVF PQ (falss
16)
IVF PO (tals. 15)
10a
0.60
0.65
0.70
0.75
0.80
0.85
0.30
0.95
1.00
0.60
0.65
0.70
0.75
0.30
0.85
0.90
0.95
1.00
Recall
Recall
Figure 3: Performance comparison of RRR and PQ different levels of memory usage. We vary the rank parameter for RRR and the code size for PQ such that b, bytes per vector, is similar for both. @ 16) outperforms even PQ@ (b 128) which uses eight times as much memory.
7.2 LoRANN
In this section, we measure the end-to-end performance LORANN (see Section 4 first perform an ablation study on the components of LoRANN (Section 7.2.1), and then perform end-to-end evaluation LoRANN against the state-of-the-art ANN libraries both the CPU setting (Section 7.2.2) and the GPU setting (Section 7.2.3)

---

ag news distilbert- 768 angular
ann 12: 1012-2000-a- angular
10a
Queries per second (11))
100
10
Queries
107
IVF RAR + DR B.DE
IVP a HRR e DR
IVT BRR IVF
0.60
0.65
0.70
0.75
0.80 Recall
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.50
0.85
0.90
0.95
1.00
Recall
Figure 4: LoRANN ablation study. On the high-dimensional (d - (68) data (left), all the compo- nents improve the performance of LoRANN. On the ower-dimenniioal (d = 200) data set (right), all the components except dimensionality reduction (DR) improve performance.
7.2.1 Ablation study
In Figure 4 study the effect the different components of LoRANN on its performance (for the full results, see Appendix E.T. As the baseline, we use an IVF index. Adding the score computation step via RRR significantly improves performance on all the data sets.
Dimensionality reduction (DR) beneficial on dieberrdi data sets with moderate-sizze corpora: if the number of points in cluster is lower than the dimension, then the first octtor-atrix product in the computation (x" A)B of the local reduced-rank regression models will be more expen- sive. For large data sets with high-dimensional data, this effect decreases. Dimensionality reduction also does not improve performance on the lower-dimensional data sets (d S 300). Incorporating 8-bit quantization improves not only the memory usage but also the query latency.
In Appendix E.2 we study the effect of varying the rank r of the parameter matrices. We find that increasing from 32 to 64 has little effect, while r 16 performs worse for high-dimensional data (but can be used to further decrease memory usage). For all of our other experiments, we use r = 32.
7.2.2 CPU evaluation
As the baseline methods, we choose four leading graph implementations. HNSW, GLASS QSG- NGT, and PyNNDescent (Dong et al., 201T), two leading product quantization implementations. Faiss-IVFPQ (fast scan) and ScaNN, and the leading tree implementation MRPT (Hyvönen et al. 2016). See Figure 5 for the results and Appendix E.3 for the results on 16 data sets. Three trends emerge: (1) LORANN outperforms the product quantization methods all data sets except glove-200-angular. (2) LORANN performs better in the high-dimensionall regime: outperforms all the other methods except GLASS and QSG-NGT all but the power-dimensiones (d S 200) data sets. (3) Compared to graph methods, LORANN performs better at the lower recall levels: QPS-recall curves of LORANN and GLASS cross between 80% and 99% most of the data sets. On 8 of the 16 data sets, LORANN has better or similar performance as QSG-NGT at all recall levels.
Furthermore, in Appendix we demonstrate that in general LoRANN has faster index construction times than the graph- based methods.
7.2.3 GPU evaluation
We compare LoRANN against GPU implementations of IVF and IVF-PQ in both Faiss (Douze et al. 2024) and the NVIDIA RAFT library 6 In addition, we compare against state-of-the-art GPU graph algorithm CAGRA (Ootomo et al. 2023) implemented in RAFT. All algorithms receive all test queries as one batch of size 1000. See Figure 6 for representative results, and Appendix EE.5 for the complete results. LORANN outperforms the other methods on seven out of the nine high-dimensiinall (d > 300) data sets. For d < 300, CAGRA has the best performance.
5 An efficient HNSW implementation with quantization: http::://gsthub..mm/illlll

---

news distibbert- 768--errt--6----ee 0ale--678---n--- angular
onn 121- 200---220000 200-alglor
Querles per second (118)
101
10
Queriess
asgngt
10
syrndescent
tnswlbb
10a
scann
Miiss-Miggh
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.50
0.85
0.90
0.95
1.00
Recall
Recall
Figure 5: CPU comparison. The QPS-recal curves of LORANN and the leading graph library GLASS cross at the 95% (left) and at the 90% recall level (right), indicating that LoRANN is the fastest method the lower recall levels, and GLASS at the higher recall levels.
ag.news-dittilbett-8----ngg
ann- ann-tzl-200-angular
10
(390
Queries per second (1s5)
103
lonon
raft-cagra rethvrisq roft vv
tales-ivtngggg
10a
0.60
0.65
0.70
0.75
0.00
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.90
0.85
0.90
0.95
1.00
Recall
Recall
Figure 6: GPU comparison. On the high-dimensional (d = 768) data set (left), LORANN is the fastest, and the lower-dimensional (d 200) data set (right), the graph method CAGRA is the fastest.
To demonstrate the ease of implementation of our algorithm for new hardware platforms, in Ap- pendix E.5 implement our method for Apple silicon. We show using the M2 Pro SoC that LORANN can take advantage of the M2 GPU and its unified memory architecture to achieve faster queries.
8 Discussion
In this article, we show that an elementary statistical method, reduced-rank regression (RRR), is surprisingly efficient for score computation in clustering-based ANN search. Since RRR outperforms product quantization (PQ) at fixed memory consumption while being simpler to implement efficiently, recommend using it in regimes where PQ is traditionally used, e.g., when the memory usage the article are performed in the
a limiting factor (Douze et al. 2024). While the experiments standard in-memory setting, the simple strueture and the small memory footprint of the proposed method suggest scalability for larger data sets that do not fit into the main memory. In particular, hybrid solutions that the corpus on SSD (Jayaram Subramanya et al. 2019 Ren al., 2020 Chen et al.) 202T) and the distributed setting where the corpus and the index are distributed over multiple machines (Deng et al. 2019 Gottesbüren al. 2024 are promising research directions.
Limitations Since reaching the highest recall levels (> 90% for k: = 100) requires exploring many clusters, graph methods are usually more efficient than clustering- based methods in this regime. Furthermore, low-dimensional data sets (e.g., 100) also require that the rank of the parameter matrix is reasonably high. Thus, reduced-rank regression is not efficient for low-dimensional data sets for which the proportion r/d is too large. The proposed score computation method is also only applicable to inner product-based dissimilarity measures. However, the multivariate regression formulation of Section 3.1 can be extended for other dissimilarity measures.
10

---

Acknowledgments
This work has been supported by the Research Council of Finland (grant #345635 and the Flagship programme:
Finnish Center for Artificial Intelligence FCAI) and the Jane and Aatos Erkko Foundation (BioDesign project, grant #7001702). We acknowledge the computational resources provided by the Aalto Science-I1 IT Project from Computer Science IT. We thank the anonymous reviewers for their valuable feedback.
References
Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. Cache locality is not enough: high-performance nearest neighbor search with product quantization fast sean, Proceedings of the VLDB Endowment, 9()):288-29)) 2015.
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020.
Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George Bm Van Den Driessche, jean-Baptiss Lespiau, Bogdan Damoc, Aidan Clark, et al. Im- proving language models by retrieving from trillions of tokens. In Proceedings of the International Conference on Machine Learning, pages 2206-2240. PMLR, 2022.
Sebastian Bruch. Foundations Vector Retrieval. Springer, 2024.
Sebastian Bruch, Aditya Krishnan, and Franco Maria Nardini. Optimistic query routing in clustering- based upproximate maximum inner product search. arXiv preprint orXiv:2405.12207 2024.
Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 380-388, 2002.
Qi Chen, Bing Zhao, Haidong Wang. Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. SPANN: Highly-efficient billion-scale approximate nearest neighborhood search. Advances in Neural Information Processing Systems, 34:5199-5211 2021.
Sanjoy Dasgupta and Kaushik Sinha. Randomized partition trees for nearest neighbor search. Algorithmica, (2(1):277-263 2015.
Rieke de Maeyer, Sami Sieranoja, and Pasi Fränti. Balanced k-means revisited. Applied Computing and Intelligence, 3(2): 1411-15999 2023.
Shiyuan Deng, Xiao Yan, KW Ng Kelvin, Chenyu Jiang, and James Cheng. Pyramid: A general framework for distributed similarity search large-scale datasets. 2019 IEEE International
Conference on Big Data (Big Data), pages 1066-1071, IEEE, 2019.
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. LLM.int80) 8-bit matrix multiplication for transformers scale. Advances in Neural Information Processing Systems, 35: 30318-30332, 2022.
Inderjit S. Dhillon and Dharmendra S. Modha. Concept decompositions for large sparse text data using clustering. Machine learning, 42:143-175, 2001.
Wei Dong. Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference World Wide Web.
pages 577-586, 2011.
Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In Proceedings of the International Conference Learning Representations, 2020.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The Faiss library. arXiv preprint arXiv:2401.0828/ 2024.
Roy Frostig, Matthew James Johnson, and Chris Leary. Compiling machine learning programs via high-level tracing. Machine Learning and Systems (MI.Sys), 2018.
Lars Gotteshüren, Laxman Dhulipala, Rajesh Jayaram, and Jakub Lacki. Unleashing graph partition- ing for large-scale nearest neighbor search. arXiv preprint 273.v7240.001797, 2024.
11

---

Fabian Groh, Lukas Ruppert, Patrick Wieschollek, and Hendrik P. A. Lensch. GGNN: Graph-based epu nearest neighbor search. IEEE Transactions on Big Data, (1):2677-27, 2022.
Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi
Xu, Jiarui Luo, Frank Liu, et al. Manu: cloud native vector database management system. Proceedings of the VLDB Endowment, 15(12)3354833) -3068,355,,2220 2022.
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng. David Simcha, Felix Chern, and Sanjiy Kumar. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the International Conference on Machine Learning, pages 3887-3896. PMLR, 2020.
Gaurav Gupta, Tharun Medini, Anshumali Shrivastava, and Alexander Smola. BLISS: A billion scale index using iterative re-partitioning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 486-495, 2022.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training In Proceedings of the International Conference Machine Learning, pages 3929-3938. PMLR, 2020.
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):
217-288, 2011.
Ville Hyvönen, Teemu Pitkänen, Sotiris Tasoulis, Elias Jääsaari, Risto Tuomainen, Liang Wang. Jukka Corander, and Teemu Roos. Fast nearest neighbor search through sparse random projections and voting. In Proceedings of the 2016 IEEE International Conference on Big Data, pages 881 881-888.
IEEE, 2016.
Ville Hyvönen, Elias Jääsaari, and Teemu Roos. A multilabel classification framework for ap- proximate nearest neighbor search. Advances in Neural Information Processing Systems, 35: 35741-35754, 2022.
Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355, 2018.
Alan Julian Izenman. Reduced-rant regression for the multivariate linear model. Journal of multivariate analysis, 5(2):248-264, 1975.
Elias Jääsaari, Ville Hyvönen, and Teemu Roos. Efficient autotuning of hyperparameters in approxi- mate nearest neighbor search. In Proceedings of the 23rd Pacific-Asia Conference on Knowledge Discovery and Data Mining, volume 2, pages 590-602. Springer, 2019.
Shikhar Jaiswal, Ravishankar Krishnaswamy, Ankit Garg, Harsha Vardhan Simhadri, and Sheshansh queries.
Agrawal. BOD-DiskANN; Efficient and scalable graph ANNS for
arXiv preprint arXiv:2211.12823 2022.
Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and
Rohan Kadekodi. DiskANN: Fast accurate billion-poii point nearest neighbor search on a single node. Advances in Neural Information Processing Systems, 32, 2019.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 117-1288 2011.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):335-544 547, 2019.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer:
The efficient transformer. In Proceedings of the International Conference on Learning Representations, 2020.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmenter generation for knowledge-intenee inteesive NLP tasks. Advances in Neural Information Processing Systems, 33:9459-9474, 2020.
Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approxi- mate nearest neighbor search on high dimensional data exprrimets,m analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering, 32(8): 1488-1488 2019.
Wei Liu, Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. Hashing with graphs. Proceedings of the International Conference Machine Learning, pages 1-8. PMLR, 2011.
12

---

Wei Liu, Jun Wang, Rongrong Ji, Yu-Gang Jiang, and Shih-Fu Chang. Supervised hashing with kernels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pages 2074-20010 2081. IEEF, 2012.
Zepu Lu, Jin Chen, Defu Lian, Zaixi Zhang, Yong Ge, and Enhong Chen. Knowledge distillation for high dimensional search index. In Advances in Neural Information Processing Systems, volume 36,
pages 33403-33419, 2023.
Yu A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824-836, 2018.
Marius Muja and David G. Lowe. Scalable nearest neighbor algorithms for high dimensional data.
IEEF Transactions on Pattern Analysis and Machine Intelligence, 36(1 1):2227-2240,, 2014.
Mohammad Norouzi and David J. Fleet. Minimal loss hashing for compact binary codes. In Proceedings of the International Conference on Machine Learning, pages 353-360. PMLR, 2011.
Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. CAGRA: Highly parallel graph construction and approximate nearest neighbor search for GPUs. arXiv preprint ar arXiv:2308. /5166, 2023.
James Jie Pan, Jianguo Wang, and Guoliang Li. Vector database management techniques and systems. In Companion of the 2024 International Conference on Management of Data, pages 597-604, 2024.
Jie Ren, Minjia Zhang, and Dong Li. HM-ANN: Efficient billion-point nearest neighbor search on heterogeneous memory. Advances Neural Information Processing Systems, 13:40672-10684 2020.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68, 2021.
Weijia Shi, Sewon Min, Michihiro Yasunaga, Minjoon Seo, Richard James, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih. REPLUG: Retreeval--ugmmeneed black-box language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics, pages 8371-8384 Association for Computational Linguisties, 2024.
Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa, et al. Results of the NeurlPS' 21 challenge on billion-scale approximate nearest neighbor search. In NeurIPS 2021 Competitions and Demonstrations Track, pages 177-189. PMLR, 2022.
Philip Sun, David Simcha, Dave Dopson, Ruiqi Guo, and Sanjiv Kumar. SOAR: Improved indexing for approximate nearest neighbor search. In Advances in Neural Information Processing Systems, volume 36, 2023.
Thomas Vecchiato, Claudio Lucchese, Franco Maria Nardini, and Sebastian Bruch. A learning-to- rank formulation of clustering- based approximate nearest neighbor search. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2261-2265, 2024.
Apoorv Vyas, Angelos Katharopoulos, and François Fleuret. Fast transformers with clustered attention. Advances in Neural Information Processing Systems, 33:21665-21674 2020.
Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xi- angzhou Guo, Chengming Li, Xiaohai Xu, et al. Milvus: A purpose-built vector data management system. In Proceedings of the 202/ International Conference on Management of Data, pages 2614-2627, 2021.
Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. Advances in Neural Information Processing Systems, 21:1753- 7600, 2008.
Weijie Zhao, Shulong Tan, and Ping Li. SONG: Approximate nearest neighbor search on GPU. In
IEEE 36th International Conference on Data Engineering (ICDE), pages 0033-1044, IEEE, 2020.
Xi Zhao, Bolong Zheng, Xiaomeng Yi, Xiaofan Luan, Charles Xie, Xiaofang Zhou, and Christian S. Jensen. FARGO: Fast maximum inner product search via global multi-probing. Proceedings of the VLDB Endowment, 16(5):1 100-1112, 2023.
13

---

A Geometric intuition
Observe that the reduced-rank regression solution is different from the most obvious low-rank approximation of the OLS solution computed via an SVD of the matrix C. In Section we verify experimentally using a real-world data set that more accurate model can indeed be trained by factorizing XC instead of C. These two solutions are equivalent only in the special case where X C. this special case, computing the predictions of the reduced-rank regression model, denoted by RrrR= == x" BRRR. equivalent to projecting both the query point x and the cluster points {cyhjeı onto the subspace spanned by the first cigenvectors of K == C²C, and computing the inner products in this r-dimensional subspace. If the cluster points are centered, the eigenvectors of K are the principal axes of the cluster points, and mi m,-T K can be interpreted the sample covariance matrix. However, unlike in principal component analysis (PCA), data should not be centered when estimating the inner products, since the inner products are not invariant with respect to translation.
Let W, E Raxr be matrix containing the first cigenvectors of K as columns, and denote by X = WTx the r-dimensional projection of the query point, by C == CW, my X r-matrix containing the projected cluster points, and by ý == xTČ an 1 x mn-matrix containing the inner products between the projected query and the projected cluster points. Using this notation, we have the following result:
Theorem 1. If = C, then y = FRAR-
Proof. Denote 3 = W, W.C. Now ý can be written as ý = x To prove the result, it suffices to show that B BRRR. Denote the singular value decomposition of C by C' UEV". Since X= C, Y CCT and, consequently, the right singular vectors of CT are the eigenvectors of Y. Thus, the reduced-rank regression solution is
3RRR CVV,
where V, is r-matrix containing the first columns of V.
The columns of the matrix U-i.e., the left singular vectors of CT- the eigenvectors of C C. Thus, W, = U, and 3 can be written as
= U,UCC
where we denote by U, a r-matrix containing the first columns of the matrix U. Since UTCT= EV", also U.C these identities, we have
E, V and since C.
UE, also C²V, U,E,- Using
3 = U.U.C U.E.V. CVV, ,RRR,
which completes the proof.
However, in the general case where X A C, i.e. the training set of the ith model selected as the training queries that routed into the /th cluster (for which E 7xx))) the matrix X also affects the right singular vectors of the output matrix Y = XC". Hence, there is no simple geometric interpretation for the reduced-rant regression solution 3RRR in the d-dimensional feature space.
14

---

B Experimental set-up
We the ANN-benchmarks project" Aumüller al. 2020) its set-up as close as possible: our experiments are performed on AWS r6i.4x440x .xlaage instances with Intel Xeon 8375C (Ice Lake) processors and hyperthreading disabled, and all algorithms are run using single core. For our GPU experiments, we use AWS g5. 2xlarge instance with an NVIDIA A A10G GPU (24 GB VRAM) and mac2-m2pro. metal instance with an Apple M2 Pro SoC.
run our experiments and replicate
We use k 100 for all experiments and measure the recall (the proportion of true k-nn found) separate test set of 1000 queries, and
queries per second (QPS). For all data sets, each hyperparameter combination is benchmarked 5 times, from which the lowest achieved query latency recorded. Additionally, due to the lack of modern high-dimensional embedding data sets in LNN-benchmarks, we include multiple new high-dimensional data sets in our experiments, for a list of all the data sets, see Appendix C To account for the new data sets, increase the sizes of the considered hyperparameter grids in applicable cases.
For LORANN experiments (Section 7.2 use the following hyperparameter grid:
Number of clusters L: 1024, 2048, 4096
Reduced dimension 8: 64, 128, 192
Rank r: 32 (for GPU, r: 24)
Clusters search 8, 16, 24, 32, 48, 64, 128, 256
Points to re-rank t: 100, 200, 400, 800, 1200, 1600, 2400, 3200
For experiments on just sduuced-rnkk regression (Section 7.1,, we use the same hyperparameter grid for L, w, and above and do not dimensionality reduction.
For all hyperparameters, see https: thub. http://hhhh....coapaaaaaaaaaaaap
httpe://ggthhbbbooo/rrrrbb////b benchaarrs
15

---

C Data sets
In addition to data from ANN-benchmarks (fashion-mnis gist, glove, mnist, sift), we include high-dimensional neural network embedding data sets that are more representative of those encoun- tered in modern machine learning applications and encompass dimensionalities ranging from 200 to 1536. The full list of data sets along with their sizes and the distance metrics used is given in Table
Table I: Data sets used in the experiments.
Data set (model)
type
corpus size
dim
distance
license
ag-news (DistilBERT)
text embedding
120 000
768
angular
CC BY 4.0
ag-news (Mi
text embedding
120 000
384
angular
CC BY 4.0
ann-arxiv (E5-base)*
embedding
288 300
768
angular
Apache 2.0
ann-t2i (ResNext)
image embedding
1000 000
200
angular
Apache 2.0
arxiv (OpenAI Ada)* arxiv (InstructXI.)"
text embedding text embedding
319 224
1536
angular
CCO 1.0
254 000
768
angular
N/A
fashion-mnist fasttext-wiki
image
60 000
784
euclidean
MIT
word embedding
000 000
300
euclidean
CC BY-SA 3.0
gist
image descriptor
000 000
960
euclidean
CCO 1.0
glove mo sift
word embedding
193 514
200
angular
Apache 2.0
raw image
60 000
784
euclidean
CC BY-SA 3.0
image descriptor
000 000
128
euclidean
CCO 1.0
wiki (GTE-small)"
text embedding
224 482
384
angular
MIT
wiki (OpenAl Ada)" wolt (
text embedding
224 482
1536
angular
MIT
image embedding
720 611
512
angular
N/A
yandex T2I 53
text/image
5 000 000
200
angular
CC BY 4.0
News neere__cboccane/2222333338111110
https://huggiin
11
https:
12
16

---

D Reduced-rank regression experiments
D.1 Fixed clustering
In this section, we present the complete evaluation of reduced-rank regression in comparison to product quantization when the k-means clustering kept fixed. For discussion, refer Section 7.1.1
ag nennee-wsssiieee distiibert-iteeee Beatlberrt-6--angglle angg-ag
neg-news-ine Beows-minimm-3B- 384-38444-00 384-angular
100
Querles second
Queries per second
1.7
RMR founs 1024)
1V + RMH (ours, 1024)
IVE BAR jouns 512)
IVT RBR (ours. c 512)
(feis, 1004]
(feins, 1009]
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Recall
Recall
1wx.vinstruttx--78--aquuue
second
Querles per second (115)
103
1024:
20481
(faiss, 2048)
1004]
(feins, 1024]
sift 12- 28-elcidee
wiki-gte 384 angulrr
10a
100
Querles per second 13.81
second
10P
IVF RAR lours, 2048)
IVF + RAR (ours. c 2048)
M/ RAR jours. 1024)
IV + RIB (ours, 1024)
IVF PQ ifhies. 2048]
IVT PO Ihils, c 2040)
PQ (faiss. 1024]
IVF PQ (faiss. 1024)
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.30
0.85
0.90
0.95
1.00
Recall
Recall
wiki-openai- www.pppanai-156-aguuuu annular
(18)
Qutriies per second (1:5)
107
2048)
7048:
1024)
17

---

D.2 Memory usage
In this section, we present the complete evaluation of reduced-rank regression in comparison to product quantization for different memory consumptions. For discussion, refer to Section 7.1.2
ag ng-news-dittilber--t 768-aaa
ag-news-minnine ag-news-minnim-384-angg 384-nnuiaar
Quaries per second C1S))
second
1.0
0/T BRR fours. 321
Jours.
10"
RRR jours,
321
PO
16)
15)
(Taiss 15)
0.60
0.65
0.70
0.75
0.80 Recall
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.00 Recall
0.05
0.90
0.95
1.00
Poxiv-instructx-766-aaaa
anxiv-openal- annulan
Querles per second (18))
per
(faiss.
IVF PQ (faiss. 64)
IVF PO (tais. 64)
1/T PQ (leiss 32)
IV7 PQ (fais, 523
PQ (fais. 26)
(faiss. 16)
10a
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.50
0.85
0.90
0.95
1.00
Recall
Recall
sift-12-euuliddaan
wiki-gte-384-angular
10*
Quarles per second (1/S)
M/T BRR Jouns 321
203
17T + BBR jouns
Jouns
1b)
PO
P0 (hiss, 64)
(hiss.
wiki opw.aieepaa...mm 1536 angular
wolt-vit Solt-vit-S12-ane 512--lulaa
Querres per second (1,8)
Quertes second
64)
(fais. 64)
IMF
PQ (fais.
22)
IVF ftais. 32)
IVT Pd (faiss 160
PVT P0 (biss, 15)
0.60
0.65
0.70
0.75
0.80
0.85
0.30
0.95
1.00
0.60
0.65
0.70
0.75
0.30
0.85
0.90
0.95
1.00
Recall
Recall
18

---

D.3 Memory usage (no re-ranking)
In this section, we present the evaluation of reduced-rank regression in comparison to product quantization for different memory consumptions when no final re-ranking step is used. In this scenario, the original data does not have be kept in memory.
distiiee-isttbbrttt 768-angular
ag ng-news-mmiimm 384uang
Queries per second (115)
10
(ours, 321
(curs,
N7 è 883 (ours. 161
NF APA (our, 32)
177 + (ravs 120)
N7 2038 (ours, b 18)
Cates. 640
No (lais.
107
107
arxiv-instructall-G0 760p:nstrruubl------a--- 766-anullar
arxiv-openai 1536 36-nlllr
second
Overles per second (328)
(cur,
107
N6
NV Carvs 64)
P0
(33cs 1281
NF +0 raiss b 1281
No PQ (ates 6 64)
P0 (laiss 32)
NF P0 (lass 32)
0.2
0.3
0.4
0.5
0.6
wiki-gte-384-ance
Querles per second (315)
2
per second
NF NF raass. 64)
(ous,
P0 (tass. 64)
102
NV (laiss 22)
NF PO (lais. 6
22)
NF PD (faiss 16)
NF P0 (1852. 16)
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
1.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Recall
Recall
wolt-vit-512-ance
10a
Querles per second (1/5)
N? + (UU (ours,
NV 4JUU (ours, b 64)
NV RBR (ours, 32)
NF 8R8 (ours,
32)
Querles
10a
NF 883 (ours
18)
PO
32)
NF (lles
10a
IF
16)
IF P0 (aiss
16)
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Recall
Recall
19

---

E LoRANN experiments
E.1
Ablation study
In this section, we study the effect the components (reduced-rank regression, dimensionality reduction, 8-bit quantization) of LoRANN on its performance. For discussion, refer to Section 7.2.T
10%
Queries per second
10*
10
8-51
IF RAR + DR
M RAR
I/F
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.50
0.85
0.90
0.95
1.00
Recall
Recall
1ii--22200-anuglla angular
arxiv-instructxi-ee angular
10"
Queries per second (18)
102
10
10P
10'
1.00
0.75
0.90
andli-gpenal-133--annllar
fashlon-mmiiee764-sullleee
10a
Querles per second (1/5) (1/5)
10a
10º
10*
IVF RAR
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.30
0.85
0.30
0.95
1.00
Recall
Recall
100--66-eeu euclidean
10
Querles per second (1/8)
102
Quertes
10a
10'
0.75
0.85
1.00
0.60
0.75
0.90
1.00
20

---

sif-128 euclidean
wiki gte 384 angular
Querless per second (UNN)
10*
10a
A3R.
AAR
10
0.80
0.55
0.70
0.75
0.80
0.90
1.00
0.70
0.80
0.90
1.00
Recall
Recall
wikk-openall-1566 153--anuuar
Sotb-vit-512annguee
10a
Queriess seccord 1129)
por second (124)
20a
10*
10'
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Recall
Recall
E.2
Effect of the rank
In Figure we study the impact of the rank of the parameter matrices PRRR- We find that LORANN is robust with respect to the choice of r: increasing from 32 to 64 has little effect (when the final re-ranking step is used), while our experiments, we use 32, but 16 can be used to decrease the memory consumption, and r 64 be used achieve higher recall if the final re-ranking step not used.
16 performs only slightly worse for high-dimensional data. In
arxiv-openai- www.oppenii-136-angiie
gist-960-nuclidean
10*
10"
Queries per second (16s)
(3.5)
20*
W0rnn-166
Iecan--16 16
Wrant-17
Ineann-3 30
Brann-61
0.00
0.83
0.70
0.75
0.80
0.05
0.90
0.95
1.00
0.00
0.05
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Recall
Recall
sift-12--uclidean
wolt:wit-512-angular
Quariess per second 11153
por 11/2)
30
Wrnnn-18
Incare-16
loron 32
lorom 32
lorznn-G4
loram 64
1.00
Figure 7: Effect of the rank r of the parameter matrices GRRR in LORANN.
21

---

E.3 CPU Evaluation
In this section, we present the complete evaluation LORANN in the CPU setting comparison to other ANN algorithms. For discussion, refer to Section 7.2.2
ag ag-news-distibbert balagargr--
ag www.wwwiiiimmm---aaaa.....
Quarfes per second (US))
10"
Querles
10*
Siss--/bohh
mrst
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Recall
Recall
ann-arxiv- 768 768-angularr
mmn-12i-200-anguul
10a
Querles per second C188
10a
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.75
0.80
0.85
0.90
1,00
Recall
Recall
arklloppena--556-annggaaa
Querlee per second (119)
10a
glacs
lorann
10a
syrndescent
10
10":
Recall
Recall
Isshion-mnis-784eecdddee
basteextwwk--30-eeldddeee
Querles per second (3/8)
Querles secord
2.0"
10a
10'
0.60
0.65
0.70
0.75
0.80
0.85
0.30
0.95
1.00
0.60
0.65
0.70
0.75
0.30
0.85
0.90
0.35
1.00
Recall
Becall
22

---

gist-960-euclidann
glove-200-anguiar
10
10a
Querles per second (1,8)
102
glass
gegngt
syrndescent
100
bnselib
scann
hiss-r/bof
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.60
0.85
0.90
0.95
1.00
Recall
Recall
molst-784eeuulldea
sift-28-euccldeann
Querles per second (1())
10*
1.04
20*
wiki-gte 384 angular
wiki-openai 1a3-eenni------nnuula
Queeries per second (18))
10*
per second
2.0H
10a
asgngt
syendescent tnswlbb
10
scam
Miss-
mist
10a
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Recall
Recall
5oll-vil-512-angular
yandex 5M-200-angularr
10a
10*
Querlies per second (1:5)
1.0
10a
107
0.75
23

---

E.4 Index construction time
For all libraries, we measure the index construction time on single CPU core (for LoRANN, the index construction parallelizes easily as all local cluster models can be computed independently). Table 2 shows index construction times for all data sets and compared methods at 90% recall for 100 at the optimal hyperparameters (a dash means that the algorithm either did not reach the necessary recall or ran out of memory on the data set).
LORANN has slower index construction times than IVFPQfs, and similar index construction times as ScaNN. In general, LORANN has faster index construction times than the graph methods: QSG-NGT has extremely slow index construction times, HNSW has slower index construction times than LORANN on all data sets except ann-12i, and GLASS is slower on all data sets except two lower-dimensional data sets (ann-t2i and faskt.
We note that our implementation of LORANN has not been optimized with respect to index construction time, and could be improved with further sampling and more approximate SVD computations.
Table 2: Index construction times (seconds) at 90% recall for optimal hyperparameters.
data set
IVFPQIs
LoRANN
ScaNN
NNDesc.
QSGNGT
Glass
HNSW
ag ag-distilbert
29
26
66
56
1687
73
104
ag-minilm
15
18
34
47
1763
46
203
ann-arxiv
269
1442
1160
3988
16521
4241
7421
ann-t2i
34
916
125
238
3366
304
842
arxiv-instructxl
79
1189
1259
1041
18781
2956
6779
arxiv-openai
77
112
425
208
16369
405
926
fashion-mnist
15
30
32
1254
22
42
fasttext-wiki
60
1012
1241
3025
752
1414
gist
979
305
686
1203
8610
2258
6631
glove
49
155
1958
14259
1728
4412
mnist
15
31
32
1249
22
43
sift
91
32
361
2785
405
851
wiki-gte
24
34
39
59
2060
61
138
wiki-openai
362
67
296
137
5085
239
506
wolt-vit
286
464
563
1103
8327
874
1982
yandex-5M
589
2444
612
5218
2884
6599
24

---

E,5
GPU evaluation
NVIDIA GPU In this section, we present the full evaluation of LORANN in the GPU setting in comparison to other GPU ANN methods. For discussion, refer to Section 7.2.3
ag ng-nnww--istilber- 768-anull
ag agg-news- meto:ssmnilmm384-aaam
10a
Queries per second (18)
100
100
Quarrees
100
10*
laiss-r/gpa
bals--Mbp gm0
0.60
0.65
0.70
0.75
0.00
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.00
0.05
0.90
0.95
1.00
Recall
Recall
ann-t2i-200 aoraalla
anxiv-openai 1530mmai-l33-
100
Querles per second (18)
10a
Quertes second
10"
10*
10a
10a
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.30
0.85
0.90
0.95
1.00
Recall
Recall
fashion-mmist-7BBeeullleee
fasttextwwlk:300eeedlddee
109
Quanies F1/S)
Querles second (1/5)
10
100
10*
100
Siss Mfgpa
10"
fatow-irlpe gpu
gist: 960 not-960-euulidees euclidean
mnist- 784 -84-ecccd
103
Querles per second (18))
Querles second
10%
10
0.60
0.65
0.70
0.75
0.80
0.85
0.30
0.95
1.00
0.60
0.65
0.70
0.75
0.30
0.85
0.90
0.95
1.00
Recall
Becall
25

---

sif-128 101-128-eucche euclidean
wiki-gte 384 angular
Queries per second (11))
second
100
roft-oogra roft-viog
ratt-vl
latesoolgpa
Si2 Mibo
0.60
0.65
0.70
0.75
0.80
0.65
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.50
0.85
0.90
0.95
1.00
Recall
Recall
wolt-wit-512-angujar
Querles per second (375)
second
20a
10a
10"
10a
1.00
Apple silicon this section, we use MIXX to implement LoRANN for Apple silicon. We compare MLX versions (both CPU and GPU versions) of LORANN against MLX versions of IVF and the C++ version of LORANN (without quantization) on the Apple M2 Pro SoC. The MLX version of LORANN can take advantage of the M2 Pro GPU and its unified memory architecture achieve 2-5 times faster query latencies compared to C++ implementation of LORANN.
ag agrressddiilllbett---anngggg
ag-news arngglll
10a
10a-
second (1N)
Querles per second (18)
10a
20*
borann-ni--gu
1.00
0.75
0.90
1.00
sift- sitt-28--ucllddenn
wild-appenal-153--nnqule
Querles per second (115)
Querles
103
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Recall
Recall
26

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We explicitly list the main contributions of the article at the end of Section and refer to the relevant sections of the article justifying the claims being made.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in Section g
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

Justification:
The proof of Theorem is provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide code implementing our method as well as code for running the benchmarks, including code to prepare all the data sets and algorithms.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

Answer: [Yes]
Justification: We provide code implementing our method as well as code for running the benchmarks, including code prepare all the data sets and algorithms. The provided repository has instructions for running the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https http///ooeuuuissioooooooo
/ ctiips.cc/public/uuii
ssiolloliiii//oooccccccccoc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental set-up is descrihed in Appendix Baand the details for all data sets are given in Appendix C The experimental code including data set preparation and used hyperparameters for all methods is available hhttpss//ggthhhi com/ e /asaarii/
Iorann wwweeeeeperrmmmeet
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: It is not customary to report error bars or test the statistical significance in the field of ANN search because it would be computationally expensive. We perform the experiments using the ANN--bencharrk framework (Aumtiller et al. 2020) which is a de facto standard in the field.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
29

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We mention the exact AWS instances used in the experiments Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We checked that our work presented in the article conforms with the NeurIPS code Ethics. In particular, we checked that the data sets used were not deprecated and had permissive license (see answer to Question 12), and we disclose the elements of reproducibility (see our answer to Question 4).
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The article is foundational research as ANN search is primitive that is used as a component machine learning pipelines. Thus, our contribution of making ANN search more efficient has direct socictal impact.
30

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., dep.oymmly of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The article is foundational research, so there are no elements that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use data sets with open licenses and our benchmarking code downloads the used data sets from their original sources; we also list all used data sets in Appendix C along with their licenses and links. Our benchmarking code is a fork of the ANN-benchmarks project which licensed under the MIT license.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
31

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide documentation for both LORANN and our experiments in their respective repositories.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The article does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The article does not involve crowdsourcing or research with human subjects.
Guidelines:
32

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "wJ3ZNB3B3q", "reviewer": "Reviewer_wBA6", "summary": "The paper presents LoRANN, a novel algorithm for Approximate Nearest Neighbor (ANN) search that leverages low-rank matrix factorization and k-means clustering. The core idea is to approximate the ordinary least squares solution of the inner product computation via reduced-rank regression. The authors also introduce a quantized 8-bit version of LoRANN, which is memory efficient and performs well on high-dimensional data. The experiments demonstrate that LoRANN outperforms existing methods on both CPU and GPU.", "questions": "Does LoRANN provide any theoretical guarantees on approximation quality or search time?", "limitations": "The limitations of this work have been discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors provide extensive experimental results, reporting that their method outperforms leading product quantization-based algorithms and has faster query times than graph-based methods at certain recall levels.", "weaknesses": "There exists room for improvement in the visual presentation in this paper. Additionally, it is best to keep the starting or ending points consistent to better compare all methods.\n\n At different recall levels, LoRANN is sometimes faster, and sometimes slower compared to other methods (GLASS, CAGRA). The authors should analyze the reasons that lead to this phenomenon", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestion on improving the presentation of our graphs and will incorporate this change. We would also be happy to hear any additional suggestions regarding the visual presentation.\n\nAs mentioned in Section 8 (Limitations), the reason for the lower relative performance of LoRANN compared to graph algorithms (Glass, CAGRA) at the highest recall levels ($>0.9$) is that our method is clustering-based: too many clusters have to be explored to reach the highest recall levels. This performance degradation at the highest recall levels applies also to other SOTA clustering-based methods such as SCANN and IVF-PQ. Our method improves the performance of cluster-specific score computation, but it cannot overcome this limitation. Naturally, addressing this drawback is subject to further research.\n\nWe do not currently provide theoretical guarantees on approximation quality, but this is an interesting direction for future research. The search time of our algorithm can easily be expressed in terms of given hyperparameters, and we will include this detail in a further revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1BMtdAST72", "reviewer": "Reviewer_rz2s", "summary": "The paper describes a method for computing approximate nearest neighbors in\nhigh dimensions. Computing nearest neighbors is a classical problem in\ncomputational geometry, with applications in many areas of computer science.\nThe classical solutions in low dimensions do not generalize to high dimensions.\nThe approach in the paper has two main ideas: the first is performing k-means\nclustering, computing nearest neighbors on the means, and then computing \nmore accurate nearest neighbors inside the cluster.\nThe second is reducing the computation in each cluster to multivariate\nregression which can be solved approximately by low rank matrix factorization.", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The result appears to be very useful in many applications.", "weaknesses": "Unfortunately I am not an expert in this field and cannot comment on how this\nresult compares to the current state of the art.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We acknowledge that it is not easy  to review an article without field-specific knowledge and appreciate the effort. The ANN-benchmarks project (the link is provided on page 14 in Appendix B of the original manuscript) is the de facto standard for performance evaluation in the field of ANN search. We perform the experiments in the ANN-benchmarks framework, and use their leaderboard to pick the baseline methods. Thus, it should be possible to verify that the comparisons presented in the article are to the actual state-of-the-art even without being an expert in the field.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7hkuCLAse0", "reviewer": "Reviewer_bJwE", "summary": "This paper introduces a new method for the nearest neighbor search problem. Leveraging the low-rank assumption, the authors combine low-rank matrix factorization, clustering, and quantization to enhance the speed of nearest neighbor search. The authors conducted extensive experiments to demonstrate the advantages of their method over numerous baselines.", "questions": "1. Regarding the low-rank approximation, I don't understand why this method is fundamentally different from first performing dimension reduction on the dataset and then applying any standard nearest neighbor search algorithm.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The authors conducted extensive experiments to compare their methods with other baselines.\n2. The method proposed by the authors is easy to follow and implement.", "weaknesses": "1. It seems that all the techniques mentioned in this paper have already known to be useful for nearest neighbor search.\n2. As shown in Figure 2, all the components contribute to the final results. I don't see any reason why any component applied there is unique to the new algorithm. For example, the clustering and 8-bit quantization techniques appear to be applicable to any existing nearest neighbor search algorithm or library. Thus, I question whether it is fair to employ too many techniques when comparing with other standard nearest neighbor search libraries.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their feedback. However, we want to clarify that our method does not reduce to techniques that have already been used in the earlier ANN literature. As nicely summarized by Reviewer udkL, the main novel contribution of the manuscript is a new supervised method (reduced-rank regression) for cluster-specific score computation in clustering-based ANN search. To the best of our knowledge, this score computation method has not been considered in the earlier ANN literature. \n\nWe also want to clarify that the proposed method is fundamentally different from first performing a dimensionality reduction and then applying any ANN algorithm. Our cluster-specific supervised method does not reduce to global dimensionality reduction, since it is neither global nor unsupervised. The key differences are: (1) we compute the scores locally at the clusters by cluster-specific reduced-rank regression models, not by one global model, allowing much greater compression; (2) the proposed score computation method is supervised, i.e., we predict the inner products via reduced-rank regression, and not by an unsupervised dimensionality reduction method.\n\nIn addition to the novel score computation method, we propose a concrete ANN algorithm (LoRANN), that combines this score computation method with $k$-means clustering, global dimensionality reduction, and 8-bit quantization. As the Reviewer correctly points out, these techniques have been used earlier in ANN algorithms. However, we combine them in a novel fashion: for example, LoRANN performs the entire score computation using 8-bit integer vector-matrix multiplications. We also do not think that using these techniques makes the comparison to the standard nearest neighbor libraries unfair. We use them to design a practically useful ANN algorithm and to ensure a fair end-to-end comparison with the state-of-the-art ANN libraries that also utilize these techniques.\n\nHowever, we acknowledge that, as also pointed out by Reviewer udkL, our experimental validation was unclear, since we did not directly compare the novel component of our algorithm (supervised score computation) against the product quantization that is used for score computation by the state-of-the-art clustering-based libraries. In Figure 1 of the attached pdf file, we present the results of an experiment that demonstrates the performance improvement provided by our novel score computation method. In particular, when the clustering is constant across methods, the proposed score computation method outperforms product quantization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hYN2ViwRzs", "reviewer": "Reviewer_udkL", "summary": "This paper investigates approximate nearest neighbor (ANN) search, where, given a collection $\\mathcal{X}$ of points in $\\mathbb{R}^d$, the task is to find the top $k$ data points that are closest to a query point $q$ according to some similarity or dissimilarity measure (denoted by $\\delta(\\cdot, \\cdot)$), such as inner product. There are many classes of algorithms in existence[1], with this particular work falling into the clustering-based paradigm.\n\nIn clustering-based (aka Inverted File or IVF) ANN search, $\\mathcal{X}$ is partitioned into a set number of clusters, often using a geometric clustering algorithm such as (spherical) KMeans, with every cluster represented using some sketch of the cluster such as its mean. When presented with $q$, the algorithm first identifies $\\texttt{nprobe}$ clusters to search by ranking the clusters according to the distance between $q$ and their representative points. It then computes $\\delta(q, \\cdot)$ with points within the $\\texttt{nprobe}$ clusters, and returns the top $k$ points from that set.\n\nThis work concerns the second step. Typically the computation of $\\delta(q, \\cdot)$ uses Product Quantization (PQ) to reduce memory consumption and to perform the distance computation efficiently. Instead, this work reduces the dimensionality of the data matrix within each cluster using its low-rank approximation. The key insight is that, the low-rank approximation is constrained to the space of rank $r$ matrices that predict the inner products well on a specific query distribution.\n\n\n[1] \"Foundations of Vector Retrieval\" by S. Bruch. Springer.", "questions": "My questions mainly concern your experimental evaluation:\n* Setup: What's the training set used to train LoRANN? You have kindly given statistics about each dataset, but sadly did not include any information about the size of the query sets.\n* Figure 1: What is the size of the initial candidate set in the right figure, where reranking is enabled? It is important to know this because the size of the initial set can explain the small difference between the different curves (e.g., if you retrieve a very large set followed by re-ranking, the accuracy of each method pre-reranking becomes less and less important)\n* PQ is obviously sensitive to the bitrate, a hyper-parameter. Can you elaborate how LoRANN holds up against PQ as you sweep the rank parameter and PQ's code size, in terms of speed and memory usage?", "limitations": "I really like this work and the simplicity of the idea. I'd love to see this work in print, but I think it can be so much more complete with a proper set of experiments. As it stands, the incomplete experiments limit the reach of this work. A stronger formulation (using ranking, e.g.) can even enhance the results too. I hope my feedback proves helpful in strengthening the arguments of this work.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The proposed method relies on a very simple yet effective method for supervised dimensionality reduction in the context of ANN search\n* The paper is easy to read and arguments straightforward to follow\n* Results are encouraging", "weaknesses": "Post-discussion Update: The authors have addressed my concerns around the experimental setup, and have expressed interest in adopting a more clear narrative and framing of their contributions.\n\n-----------------\n\n* Presentation:\n  - I think the authors can shed quite a bit of fluff by positioning the work as I did in my summary. This work's contribution is very much in the speeding up and improving the accuracy of the score computation phase in clustering-based/IVF ANN search. Presented that way, the authors can immediately focus on the regression problem instead, and not introduce distractions such as the details of clustering, the importance of MIPS (section 2.1), and more. It'd make for a cleaner presentation of your idea, and lets your readers understand the scope of your contributions more clearly.\n  - As a minor point, Theorem 1 is a vacuous statement. It's neither necessary to explain the findings of the paper, nor is it insightful enough to birth new research directions. Perhaps you can move it entirely to the appendix if you insist on including it in the work.\n  - It must be noted that the method presented in this work is supervised. That is a critical differentiating factor between LoRANN and existing methods such as PQ and Scann.\n\n* Methodology: One of the interesting insights that led to Scann is that not all inner products are equally important. For a quantization method to be successful, it needs to preserve the inner product between $q$ and high-ranking data points better than inner product between $q$ and low-ranking points. In your work, you model the problem as regression, and attempt to minimize the error of inner production approximation equally for all data points. What motivates this uniform weighting? Have you considered a ranking formulation of the problem rather than regression? There is a vast literature on learning-to-rank which, in fact, is very relevant to your idea, but where Scann's insight is baked into its machinery/objective.\n\n* Experiments: Because the methodology is very straightforward and the novelty is minimal, I expect a much stronger experimental evaluation of the proposed method. Here are a few points to consider:\n  - Your main experiments conflate two orthogonal axes of evaluation: effect of clustering vs effect of score computation; this I believe stems from the way you present your work. Your contribution, as I noted above, is to the score computation phase of IVF-based ANN search. To evaluate your contributions fairly against SOTA IVF methods, you must partition the data once. Given this fixed set of partitions, you can directly compare the efficacy of LoRANN against PQ and Scann's quantization protocol. By running each method independently as you do now, such that each produces its own partitioning of the data separately, you run the risk of conflating the effect of clustering on IVF's accuracy with the effect of the specific choice of dimensionality reduction/quantization. As it stands, I cannot deduce the exact reason why your method should work better.\n  - You are also comparing a supervised method that adapts to a query distribution, with unsupervised baselines. Not only is it not a fair comparison, your results are also not informative. It is not surprising that your method does well: you give it an unfair advantage (as confirmed by Figure 1 - left) by finding a matrix that can predict inner products on *a specific query distribution*. A more reasonable experiment would be to (a) compare a variant of LoRANN that's trained on the data points only (i.e., without training queries) with other IVF methods, and (b) incorporating the query distribution into Scann (its objective can use information about the query distribution). There are other methods that can use a query set to improve quantization ([2,3] are a couple of examples).\n  - As a very simple baseline, consider partitioning the data using centroids obtained from a partitioning of queries!\n  - Frankly, a comparison with graph methods is nice, but is rather tangential. I encourage you to contrast your method with other IVF methods first, focus your discussion to justifying your proposal against SOTA IVF methods, and then conclude your work with a comparison with graph methods for completeness.\n\n\n[2] \"Query-Aware Quantization for Maximum Inner Product Search\" by Zhang et al. AAAI 2023.\n   \n[3] \"A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search\" by Vecchiato et al. SIGIR 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for constructive feedback and good suggestions for improving the manuscript. In particular, clarifying the main contribution of our article as improving the accuracy of score computation in clustering-based ANN search would indeed make the presentation cleaner and our argument stronger; we will revise the manuscript accordingly.\n\nWe address the remarks and questions about our experimental methodology by clarifying the details of our experimental setup and providing additional experimental results. Most importantly, we want to clarify that our method does not get an unfair advantage by using any training data the other methods do not have access to. In all the experiments (except the experiments of Section 5 that specifically verify that our method can adapt to the query distribution in the OOD setting), our method uses only the corpus itself as a global training set and draws local training sets as detailed in Section 3. All the data sets, except Yandex used in Section 5, are benchmark data sets for which no specific training set drawn from the query distribution is available. We follow Aumüller et al. [1] by dividing the original data set randomly into a corpus and a set of 1000 test queries. Thus the corpus and the test queries are drawn from the same distribution, and LoRANN exhibits superior performance compared to PQ even in this standard in-distribution setting. This critical detail was missing in the original manuscript, and we thank the Reviewer for pointing this out. \n\nAs the Reviewer suggests, it would be natural to also consider non-uniform weightings. The anisotropic quantization used in SCANN works well for GloVE which has a specific data distribution, but does not seems to improve the performance of standard PQ for most data sets as evidenced by both our experiments and experiments by the Faiss authors [2]. We also performed preliminary experiments with optimizing weighted MSE and ranking losses, but they did not improve accuracy while making the models much slower to train. Meanwhile, the simple MSE already results in superior performance compared to earlier methods. However, as the Reviewer suggests, exploring different supervised formulations and loss functions is still an interesting direction for future work.\n\nTo address the remark about conflating the effects of clustering and score computation, in Figure 1 of the attached pdf, we perform an additional experiment where the clustering is kept constant to directly compare the proposed score computation method to the score computation method (product quantization) employed by IVF-PQ. The proposed score computation method outperforms product quantization on all of the data sets. Unfortunately, due to the limited time for author response, we were unable to include anisotropic quantization of SCANN in this experiment, but since SCANN did not outperform IVF-PQ in our end-to-end experiments (see Figure 3 and Appendix E of the original manuscript), we do not expect that the performance of anisotropic quantization would be better than the performance of PQ.\n\nTo compare the proposed method to PQ for fixed memory consumption, in Figure 2 of the attached pdf, we vary the code size of PQ, and compare LoRANN to IVF-PQ with hyperparameters resulting in similar memory usage. The results of this experiment verify that for fixed memory consumption, LoRANN has superior performance compared to PQ that is a typical choice in memory-limited use cases.\n\n[1] M. Aumüller et al. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020): 101374.\n\n[2] Indexing 1M vectors. Faiss Wiki on GitHub.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their constructive feedback. Here we address the most important concerns about novelty (Reviewer bJwE) and experimental methodology (Reviewer udkL) by clarifying our contribution and experimental setup, and performing new experiments:

- We clarify that our method does not get an unfair advantage by using training data that the baseline methods do not have access to. In all of the experiments (except those in Section 5: Out-of-distribution queries) our algorithm draws its training sets from the corpus itself. 
- We clarify that the main methodological contribution of the manuscript is a novel supervised score computation method for clustering-based ANN search.
- We empirically verify that the proposed score computation method outperforms the score computation method (product quantization) used by the SOTA clustering-based algorithm IVF-PQ.

Detailed comments are provided in our reviewer-specific responses.

Additionally, the attached pdf includes two new experiments: (1) In Figure 1, we keep the clustering constant to directly compare the proposed score computation method to product quantization (PQ); (2) In Figure 2, we vary the code size of PQ to compare LoRANN to IVF-PQ with different hyperparameters resulting in similar memory usage.

Meta-review: The authors present LoRANN, an innovative method for approximate nearest neighbor (ANN) search that ingeniously combines low-rank matrix factorization, clustering, and quantization techniques. The method is straightforward to understand and implement, and the experimental results are highly promising.

In response to the reviewers' concerns, the authors provide clarifications and additional experiments in their rebuttal, convincingly demonstrating LoRANN's superior performance.

This work offers a simple yet powerful perspective to the field, significantly contributing to its overall value. To further enhance the paper, the authors should focus on refining the presentation in the camera-ready version by more clearly articulating their ideas and the scope of their contributions.

By incorporating these improvements, this paper will make a substantial and valuable contribution to the field of approximate nearest neighbor search.
Decision: Accept (poster)