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

Authors: elias  jääsaari
ville  hyvönen
teemu  roos
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 08:22:10

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.

Main paper: 
 introduction: 
 In modern machine learning applications, data is often stored as embeddings, i.e., as vectors in a high-dimensional 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 as 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-augmented 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., 2021) . ANN search is also a key operation in vector databases that are used to store embeddings for industrial-scale applications (see, e.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 Bruch, 2024) . In the comprehensive ANN benchmark (Aumüller et al., 2020) , the leading graph algorithms HNSW (Malkov and Yashunin, 2018) and NGT (Iwasaki and Miyazaki, 2018) have faster query times than clustering-based algorithms. However, clusteringbased algorithms are often used in industrial-scale applications (see, e.g., Chen et al., 2021; Douze et al., 2024) due to their smaller memory footprints and faster index construction times. They are also suitable for distributed implementations and hybrid solutions that use persistent storage such as SSDs or blob storage (Chen et al., 2021; Gottesbüren et al., 2024) .The key components of clustering-based algorithms are clustering and score computation. In the indexing phase, the corpus, i.e., the data set from which the nearest neighbors are searched, is partitioned via clustering. In the query phase, w clusters are selected and the corpus points that belong to the selected clusters are scored. The points with the highest scores are selected into a candidate set that can be further re-ranked. The state-of-the-art clustering-based algorithms (Jegou et al., 2011; Guo et al., 2020; Sun et 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 a 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-output) regression problem. For the most common dissimilarity measures, it is 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-rank regression (RRR) is 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, we introduce LoRANN, a clustering-based 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 a 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-based 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-distribution (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-based libraries Faiss (Douze et al., 2024) and ScaNN (Guo et al., 2020) , and has faster query times than the leading graphbased library GLASS at recall levels under 90% on most data sets (Section 7.2.2). LoRANN outperforms the SOTA GPU methods on high-dimensional data (Section 7.2.3).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 1 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 in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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.Let x ∈ R d be a query point, and let {c j } m j=1 ⊂ R d be the corpus, i.e., the set of points from which the nearest neighbors are retrieved. The k nearest neighbors of x are defined as 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; Zhao et al., 2023) . In ANN search, the exact solution NN k (x; {c j } m j=1 , d) 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., Li et al., 2019; Aumüller et al., 2020) .Partitioning-based 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., 2011) , build an index by partitioning the corpus into L elements. In the query phase, they use a routing function τ : R d → [L] w to assign the query point into w partition elements.Clustering-based ANN algorithms (see, e.g., Bruch, 2024, Chapter 7) are partitioning-based ANN algorithms that partition the corpus via clustering. ANN indexes based on clustering are also often called inverted file (IVF) indexes (Jegou et al., 2011) . 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 d is the inner product or the cosine distance. While there exists recent exploratory work on alternative query routing methods (Gottesbüren et al., 2024; Vecchiato et al., 2024; Bruch et al., 2024) , the most common method is centroid-based routing where, for the set {µ l } L l=1 of cluster centroids, τ (x) = NN w (x; {µ l } L l=1 , d), i.e., the w clusters whose centroids are closest to the query point are selected. We follow this standard practice by using k-means clustering with centroid-based 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 a discussion of score computation methods), and the t 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 set points. Finally, the k most similar points are returned as the approximate k-nn.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss the limitations of the work in Section 8. 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
reduced-rank regression: 
 In this section, we 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 can be approximated by reduced-rank regression (RRR). Finally, we show how RRR can be implemented efficiently using 8-bit integer vector-matrix multiplications.We consider the task of approximating the dissimilarities d(x, c j ) between the query point x and the corpus points c j that belong to the lth cluster. Denote the set of the indices of these corpus points by I l , their number by m l := |I l |, and the matrix containing them as rows byC l ∈ R m l ×d .In what follows, to avoid cluttering the notation, we drop the subscript l denoting the cluster from matrices, e.g., we denote C l by C. We also assume, w.l.o.g., that the corpus is indexed so that I l = {1, . . . , m l }. This task can now be formulated as a multivariate regression problem where the output is defined as a 1 × m l matrix y = [y 1 . . . y m l ], where y j = d(x, c j ) for each j = 1, . . . , m l .We consider the cases where d is the (negative) inner product, the Euclidean distance, or the cosine (angular) distance. In all three cases, it is sufficient to estimate the inner products. For Euclidean distance, arg min j∈I l ∥x -c j ∥ 2 = arg min j∈I l (-2x T c j + ∥c j ∥ 2 2 ), where the norms ∥c j ∥ 2 can be precomputed. For cosine distance, arg min j∈I l (1 -cos(x, c j )) = arg min j∈I l (-x T c j ) if the corpus points are normalized to have unit norm.We approximate the exact solution y = x T C T of the regression problem defined in the previous section by a low-rank approximation. We assume the standard supervised learning setting, i.e., that we have a sample {x i } n i=1 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, we use all the training set points that are routed into the lth cluster. When the standard centroid-based routing is used, these are the training set points that have µ l , i.e., the centroid of the lth cluster, among their w closest centroids. Denote the set of indices of these training set points by J l := {i ∈ [n] : l ∈ τ (x i )}, and their number by n l := |J l |. The output values of the training set of the lth model are given by Y := XC T ∈ R n l ×m l , where we denote by X ∈ R n l ×d the matrix containing the training set points {x i } i∈J l as rows.To approximate the dissimilarities between the query point x and the cluster points {c j } j∈I l , we consider the linear model x T β, where β ∈ R d×m l is a matrix containing the parameters of the model, and minimize the mean squared error E x∼Q [∥y -x T β∥ 2 2 I{l ∈ τ (x)}] (the indicator function selects the query points that routed into the lth cluster). The unconstrained least squares solution βOLS = C T reproduces the exact inner products y = x T C T . In order to reduce the computational complexity of evaluating the model predictions, we constrain the rank of the parameter matrix: rank(β) ≤ r < min(d, m l ). Under this constraint, the parameter matrix can be written using a low-rank matrix factorization β = AB, where A ∈ R d×r and B ∈ R r×m l , and, consequently, the model predictions ŷ = (x T A)B can be computed with Θ(r(d + m l )) operations. When the rank r is sufficiently low, this is significantly faster than computing the exact inner products which requires Θ(dm l ) operations. Our experiments (Section 7) indicate that fixing this hyperparameter to r = 32 works well with a wide range of data sets encompassing dimensionalities between 128 and 1536.The optimal low-rank solution can be found by minimizing the training loss βRRR = arg minβ : rank(β)≤r ∥Y -Xβ∥ 2 F ,where ∥ • ∥ F 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 = UΣV T , where Σ is a non-negative diagonal matrix and U and V are orthonormal matrices. The standard reduced-rank regression solution is βRRR = βOLS V r V T r = C T V r V T r = AB, where V r ∈ R m l ×r 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 = XC T ) , A := C T V r , and B := V T r . In practice, we use a fast randomized algorithm (Halko et al., 2011) to compute only V r instead of the full SVD. Observe that the reducedrank 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).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, the model prediction ŷ = x T βRRR = (x T A)B can be computed efficiently in two 8-bit integer vector-matrix products. We use absmax quantization (e.g., Dettmers et al., 2022) , where the elements of a vector x are scaled to the range [-127, 127] by multiplying with a constant c x such that x i8 = ⌊(127/∥x f 32 ∥ ∞ ) • x f 32 ⌉ = ⌊c x x f 32 ⌉, where ⌊•⌉ denotes rounding to the nearest integer.We quantize the matrices A and B by applying absmax quantization to each column of the given matrix, resulting in vectors c A and c B of scaling constants. We can then recover a 32-bit floating-point approximation to the vector-matrix product r = x T A withr f 32 ≈ 1 c x r i32 ⊘ c A =: s ⊙ r i32 = s ⊙ x T i8 A i8 = s ⊙ Q(x) T Q(A f 32 ),where Q(•) denotes absmax quantization, and ⊘ and ⊙ denote element-wise division and multiplication, respectively. To compute ŷ = r T 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 T A before re-quantization. Since A = C T V r and B = V T r , we can rotate r by rotating V r beforehand at no extra cost. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] 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. The provided repository has instructions for running the experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 4.2). Finally, we describe the GPU implementation of LoRANN (Section 4.3).With a moderate-sized corpus and high-dimensional data, computing the first vector-matrix product of the model prediction ŷ = (x T A)B can be more expensive than the second. In LoRANN, we further approximate the product by first projecting the query into a lower-dimensional space. We use the projection matrix W s ∈ R d×s whose columns are the first s eigenvectors of X T global X global , where X global ∈ R n×d is the matrix containing the training set points {x i } n i=1 . To estimate the reduced-rank regression models, we use the s-dimensional approximations xi = W T s x i as inputs, but the true inner products x T i c j as outputs. In this case, the reduced-rank regression estimate of the lth modelis βRRR = βOLS V r V T r = (XW s ) † YV r V T r ∈ R s×m l, where βOLS := (XW s ) † Y is the full-rank solution, and V r ∈ R m l ×r is the matrix whose columns are the first r right singular vectors of Y. Thus, now A := (XW s ) † YV r ∈ R s×r and B := V T r ∈ R r×m l . We observe that computing query-to-centroid distances in the s-dimensional space yields a minor performance improvement. In the indexing phase, we perform k-means clustering using cj = W T s c j . In the query phase, the s-dimensional approximation of the query point, x = W T s x, is used to compute the distances to the cluster centroids and the predictions ŷ = xT βRRR . The original d-dimensional query point x is used for the dissimilarity evaluations in the final re-ranking step.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 a mixed-precision decomposition by not quantizing the first component of x and the first row of both A and B. Moreover, by premultiplying the projection matrix W s with a random rotation matrix, we rotate the query point x at no extra cost before quantization. For re-quantizing r = xT A, since A = (XW s ) † YV r and B = V T r , we can again randomly rotate V r beforehand at no extra cost. We compute the 8-bit vector-matrix products r i32 = xT i8 A i8 and ŷi32 = r T i8 B i8 efficiently on modern CPUs using VPDPBUSD instructions in the AVX-512 VNNI instruction set.2 Since a VPDPBUSD instruction computes dot products of signed 8-bit integer vectors and unsigned 8-bit integer vectors, we store A i8 and B i8 as unsigned 8-bit integer matricesA ′ i8 = A i8 + 128 • 1 s×r ∈ [Z] d×r 256 and B ′ i8 = B i8 + 128 • 1 r×m ∈ [Z] r×m 256 , and compute r i32 = xT i8 A i8 = xT i8 A ′ i8 -128 • xT i8 1 s×r .The dimensionality reduction lowers the memory usage of LoRANN from Ldr + rm to Lsr + rm bytes.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 it 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 |Q|×d with |Q| queries, we need to compute the products q T i A il B il for all i = 1, . . . , |Q| and l = 1, . . . , w. Here we denote by A il and B il the matrices A and B of the lth cluster in the set of w clusters the ith query point is routed into. We compute the required products efficiently using one batched matrix multiplicationQ T A T B T by representing Q as a |Q| × 1 × 1 × d tensor Q T , the matrices A il as one |Q| × w × s × r tensor A T ,B il as one |Q| × w × r × M tensor B T ,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 is ∆ = 16.On GPUs, 8-bit integer multiplication is presently both less efficient and less supported than 16bit floating-point multiplication. Therefore, we use 16-bit floating-point numbers to perform all computations on a GPU. However, the 8-bit quantization scheme can still be useful on accelerators by allowing bigger data sets to 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 XLA to compile and run the algorithm on a GPU or a TPU (Frostig et al., 2018) . 
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 et al., 2022; Jaiswal et al., 2022; Hyvönen et al., 2022) in the out-of-distribution (OOD) setting. For instance, in the Yandex-text-to-image 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., 2022) .Due to the regression formulation, the proposed method handles OOD queries by design. To verify this, we construct an index for a sample of 400K points of the Yandex OOD data set in four different scenarios: ( 1 The results are shown in Figure 1 . The version trained on 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 LoRANN-corpus-local, 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. 
related work: 
 Supervised ANN algorithms Learning-to-hash methods (Weiss et al., 2008; Norouzi and Fleet, 2011; Liu et al., 2012) optimize partitions in a supervised fashion using 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 et 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.The state-of-the-art 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 q : R d → A to map a point of the feature space to a value in a codebook A. Given A, they approximate the dissimilarity between the query point x and the corpus point c j by d(x, q(c j )), i.e., the dissimilarity between the query point and the codebook value corresponding Figure 1 : 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. LoRANN-corpus is trained using the corpus as a training set. LoRANN-corpus-local is trained using the corpus as a training set with only the cluster points as the local training sets of the reduced-rank regression models. It is beneficial to (1) use a 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.2. The performance difference decreases when the final re-ranking step is introduced (requiring the original data set to be kept in memory). to c j . 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 lowerdimensional 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The experimental set-up is described in Appendix B and 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 at https://github.com/ejaasaari/ lorann-experiments. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
experiments: 
 We use the ANN-benchmarks project (Aumüller et al., 2020) to run our experiments3 and replicate its experimental set-up as closely as possible (see Appendix B for the description of the experimental setup). We use k = 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 in ANN-benchmarks, we include multiple new high-dimensional embedding data sets in our experiments; for a description of all the data sets, see Appendix C.Note that, even though we demonstrated in Section 5 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 j } m j=1 to train LoRANN.We first compare the proposed score computation method, reduced-rank regression (RRR), against product quantization (PQ) for clustering-based ANN search. 4 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 8-bit integer quantization as described in Section 3.3 and compare against product quantization implemented in Faiss (Douze et al., 2024) 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 a fixed memory budget.To directly compare the score computation methods, in Figure 2 we present results where the IVF index (the partition defined by k-means clustering) is the same for both methods. For RRR, we use r = 32, while for PQ each vector is encoded with d/2 subquantizers for optimal performance. RRR outperforms PQ on seven out of the eight data sets; for complete results, see Appendix D.1. In Figure 3 , 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 b, RRR outperforms PQ which is a typical choice in memory-limited use cases. Note that RRR with b ≈ 16 outperforms PQ even with b ≈ 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). Figure 3 : Performance comparison of RRR and PQ at different levels of memory usage. We vary the rank parameter r for RRR and the code size for PQ such that b, bytes per vector, is similar for both. RRR@(b ≈ 16) outperforms even PQ@(b ≈ 128) which uses eight times as much memory.In this section, we measure the end-to-end performance of LoRANN (see Section 4). We first perform an ablation study on the components of LoRANN (Section 7.2.1), and then perform an end-to-end evaluation of LoRANN against the state-of-the-art ANN libraries in both the CPU setting (Section 7.2.2) and the GPU setting (Section 7.2.3). In Figure 4 , we study the effect of the different components of LoRANN on its performance (for the full results, see Appendix E.1). 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) is beneficial on higher-dimensional data sets with moderate-sized corpora: if the number of points in a cluster is lower than the dimension, then the first vector-matrix product in the computation (x T A)B of the local reduced-rank regression models will be more expensive. 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 ≤ 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 r 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.As the baseline methods, we choose four leading graph implementations, HNSW, GLASS5 , QSG-NGT, and PyNNDescent (Dong et al., 2011) , 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 all 16 data sets. Three trends emerge: (1) LoRANN outperforms the product quantization methods on all data sets except glove-200-angular. (2) LoRANN performs better in the high-dimensional regime: it outperforms all the other methods except GLASS and QSG-NGT on all but the lower-dimensional (d ≤ 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% on 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 E.4, we demonstrate that in general LoRANN has faster index construction times than the graph-based methods.We compare LoRANN against GPU implementations of IVF and IVF-PQ in both Faiss (Douze et al., 2024) and the NVIDIA RAFT library6 . In addition, we compare against a 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 E.5 for the complete results. LoRANN outperforms the other methods on seven out of the nine high-dimensional (d > 300) data sets. For d ≤ 300, CAGRA has the best performance.Figure 5 : CPU comparison. The QPS-recall 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 at the lower recall levels, and GLASS at the higher recall levels. To demonstrate the ease of implementation of our algorithm for new hardware platforms, in Appendix E.5 we 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.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-benchmarks framework (Aumüller 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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. 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), fairness considerations (e.g., deployment 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 not tied to particular applications, let alone deployments. However, if there is a 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, it 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 as 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 or 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). 
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, we recommend using it in regimes where PQ is traditionally used, e.g., when the memory usage is a limiting factor (Douze et al., 2024) . While the experiments of the article are performed in the standard in-memory setting, the simple structure 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 store the corpus on an SSD (Jayaram Subramanya et al., 2019; Ren et al., 2020; Chen et al., 2021) and the distributed setting where the corpus and the index are distributed over multiple machines (Deng et al., 2019; Gottesbüren et 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., d < 100) also require that the rank r 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.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 5, we verify experimentally using a real-world data set that a more accurate model can indeed be trained by factorizing XC T instead of C. These two solutions are equivalent only in the special case where X = C. In this special case, computing the predictions of the reduced-rank regression model, denoted by ŷRRR := x T βRRR , is equivalent to projecting both the query point x and the cluster points {c j } j∈Ij onto the subspace spanned by the first r eigenvectors of K := C T 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 1 m l -1 K can be interpreted as 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 r ∈ R d×r be a matrix containing the first r eigenvectors of K as columns, and denote by x := W T r x the r-dimensional projection of the query point, by C := CW r an m l × r-matrix containing the projected cluster points, and by ỹ := xT CT an 1 × m l -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 X = C, then ỹ = ŷRRR . Proof. Denote β := W r W T r C. Now ỹ can be written as ỹ = x T β. To prove the result, it suffices to show that β = βRRR . Denote the singular value decomposition of C T by C T = UΣV T . Since X = C, Y = CC T , and, consequently, the right singular vectors of C T are the eigenvectors of Y. Thus, the reduced-rank regression solution isβRRR = C T V r V T r , where V r is m × r-matrix containing the first r columns of V.The columns of the matrix U-i.e., the left singular vectors of C T -are the eigenvectors of K = C T C. Thus, W r = U r , and β can be written asβ = U r U T r C, where we denote by U r a d × r-matrix containing the first r columns of the matrix U. Since U T C T = ΣV T , also U T r C T = Σ r V T r , and since C T V = UΣ, also C T V r = U r Σ r . Using these identities, we haveβ = U r U T r C T = U r Σ r V T r = C T V r V T r = βRRR , which completes the proof.However, in the general case where X ̸ = C, i.e., the training set of the lth model is selected as the training queries that are routed into the lth cluster (for which l ∈ τ (x i )), the matrix X also affects the right singular vectors of the output matrix Y = XC T . Hence, there is no simple geometric interpretation for the reduced-rank regression solution βRRR in the d-dimensional feature space.We use the ANN-benchmarks project7 (Aumüller et al., 2020) to run our experiments and replicate its set-up as close as possible: our experiments are performed on AWS r6i.4xlarge instances with Intel Xeon 8375C (Ice Lake) processors and hyperthreading disabled, and all algorithms are run using a single core. For our GPU experiments, we use an AWS g5.2xlarge instance with an NVIDIA A10G GPU (24 GB VRAM) and a mac2-m2pro.metal instance with an Apple M2 Pro SoC.We use k = 100 for all experiments and measure the recall (the proportion of true k-nn found) versus queries per second (QPS). For all data sets, we use a separate test set of 1000 queries, and each hyperparameter combination is benchmarked 5 times, from which the lowest achieved query latency is recorded. Additionally, due to the lack of modern high-dimensional embedding data sets in ANN-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, we increase the sizes of the considered hyperparameter grids in applicable cases.For LoRANN experiments (Section 7.2), we use the following hyperparameter grid: , 200, 400, 800, 1200, 1600, 2400, 3200 For experiments on just reduced-rank regression (Section 7.1), we use the same hyperparameter grid for L, w, and t as above and do not use dimensionality reduction.For all hyperparameters, see https://github.com/ejaasaari/lorann-experiments.In addition to data sets from ANN-benchmarks (fashion-mnist, gist, glove, mnist, sift), we include high-dimensional neural network embedding data sets that are more representative of those encountered 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 1 . 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. 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 set does not have to be kept in memory. In this section, we study the effect of the components (reduced-rank regression, dimensionality reduction, 8-bit quantization) of LoRANN on its performance. For discussion, refer to Section 7.2.1. In Figure 7 , we study the impact of the rank r of the parameter matrices βRRR . We find that LoRANN is robust with respect to the choice of r: increasing r from 32 to 64 has little effect (when the final re-ranking step is used), while r = 16 performs only slightly worse for high-dimensional data. In our experiments, we use r = 32, but r = 16 can be used to decrease the memory consumption, and r = 64 can be used to achieve higher recall if the final re-ranking step is not used. In this section, we present the complete evaluation of LoRANN in the CPU setting in comparison to other ANN algorithms. For discussion, refer to Section 7.2.2.For all libraries, we measure the index construction time on a 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 k = 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-t2i, and GLASS is slower on all data sets except two lower-dimensional data sets (ann-t2i and fasttext-wiki).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.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 a 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 is 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is 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 of the dataset/code/model 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 is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.https://github.com/ejaasaari/lorann 38th Conference on Neural Information Processing Systems (NeurIPS2024).takes rm l bytes. Thus in a clustering-based ANN index with L clusters and m corpus points, the total memory consumption of RRR is of order Ldr + rm bytes. In our experiments (Section 7), we use r = 32 for all data sets, while L is typically of order √ m.https://en.wikichip.org/wiki/x86/avx512_vnnihttps://github.com/ejaasaari/lorann-experimentsSince ScaNN does not outperform Faiss-IVFPQ in our end-to-end-evaluation (Section 7.2.2) and both methods employ k-means for partitioning, the anisotropic quantization(Guo et al., 2020) used by ScaNN is unlikely to outperform the original PQ(Jegou et al., 2011).An efficient HNSW implementation with quantization: https://github.com/zilliztech/pyglasshttps://github.com/rapidsai/rafthttps://github.com/erikbern/ann-benchmarkshttps://github.com/ml-explore/mlx 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

 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
questions: questions: Does LoRANN provide any theoretical guarantees on approximation quality or search time?
limitations: limitations: The limitations of this work have been discussed in the paper.
paper_summary: paper_summary: The paper describes a method for computing approximate nearest neighbors in
high dimensions. Computing nearest neighbors is a classical problem in
computational geometry, with applications in many areas of computer science.
The classical solutions in low dimensions do not generalize to high dimensions.
The approach in the paper has two main ideas: the first is performing k-means
clustering, computing nearest neighbors on the means, and then computing 
more accurate nearest neighbors inside the cluster.
The second is reducing the computation in each cluster to multivariate
regression which can be solved approximately by low rank matrix factorization.
strength_weakness: strength_weakness: Unfortunately I am not an expert in this field and cannot comment on how this
result compares to the current state of the art.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. It seems that all the techniques mentioned in this paper have already known to be useful for nearest neighbor search.
2. 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.
questions: 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: limitations: yes
paper_summary: paper_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.

In 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.

This 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.


[1] "Foundations of Vector Retrieval" by S. Bruch. Springer.
strength_weakness: strength_weakness: 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.

-----------------

* Presentation:
  - 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.
  - 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.
  - 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.

* 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.

* 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:
  - 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.
  - 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).
  - As a very simple baseline, consider partitioning the data using centroids obtained from a partitioning of queries!
  - 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.


[2] "Query-Aware Quantization for Maximum Inner Product Search" by Zhang et al. AAAI 2023.
   
[3] "A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search" by Vecchiato et al. SIGIR 2024.
questions: questions: My questions mainly concern your experimental evaluation:
* 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.
* 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)
* 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: 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.

Comments: title: Response to Author Rebuttal
comment: Thanks for your rebuttal and I will remain my rating.
Thank you for your reply. I have increased my score to 5.
Thank you so much for carefully answering all my questions and clarifying your experimental setup! I also appreciate the empirical data you collected for the experiments I requested in my review, in such a short amount of time. This apples-to-apples comparison highlights the strengths of your method even more.

I have no further questions or concerns. You have adequately addressed the issues I raised. It is delightful to see such a simple algorithm perform so well in practice.

I hope you incorporate my suggestions regarding the structure of the presentation, the reframing of your contributions, and the experiments you've additionally run into a revision of your work.