LeanVec: Searching vectors faster by making them fit
Authors: Mariano Tepper
Ishwar Singh Bhati
Cecilia Aguerrebere
Mark Hildebrand
Theodore L. Willke
Venue: Accepted by TMLR ()

Abstract: Modern deep learning models have the ability to generate high-dimensional vectors whose similarity reflects semantic resemblance.
Thus, similarity search, i.e., the operation of retrieving those vectors in a large collection that are similar to a given query, has become a critical component of a wide range of applications that demand highly accurate and timely answers. In this setting, the high vector dimensionality puts similarity search systems under compute and memory pressure, leading to subpar performance.
Additionally, cross-modal retrieval tasks have become increasingly common, e.g., where a user inputs a text query to find the most relevant images for that query. However, these queries often have different distributions than the database embeddings, making it challenging to achieve high accuracy. In this work, we present LeanVec, a framework that combines linear dimensionality reduction with vector quantization to accelerate similarity search on high-dimensional vectors while maintaining accuracy. We present LeanVec variants for in-distribution (ID) and out-of-distribution (OOD) queries. LeanVec-ID yields accuracies on par with those from recently introduced deep learning alternatives whose computational overhead precludes their usage in practice. LeanVec-OOD uses a novel technique for dimensionality reduction that considers the query and database distributions to simultaneously boost the accuracy and the performance of the framework even further (even presenting competitive results when the query and database distributions match). All in all, our extensive and varied experimental results show that LeanVec produces state-of-the-art results, with up to 3.7x improvement in search throughput and up to 4.9x faster index build time over the state of the art.

Published in Transactions on Machine Learning Research (05/2024)
LeanVec: Searching vectors faster by making them fit
Mariano Tepper* Ishwar Singh Bhati'
mariano. Lepprstt.epprrree..e.e.. Gintel, ishwar. s. bhati@intel. com cecilio. oguerrebere @intel. com mork. hildehrand Gintel. com ted. willke @intel. com
Cecilia Aguerrebere
Mark Hildebrand
Ted Willke
Intel Labs
Reviewed on OpenReview: https: // openreview. net/ forum? id- wezgrpprIc
Abstract
Modern deep learning models have the ability to generate high-dimensional vectors whose similarity reflects semantic resemblance. Thus, similarity search, i.e., the operation of re- trieving those vectors in large collection that are similar to a given query, has become a critical component of a wide range of applications that demand highly accurate and timely answers. In this setting, the high vector dimensionality puts similarity search systems under compute and memory pressure, leading to subpar performance. Additionally, cross-modal retrieval tasks have become increasingly common, e.g., where user inputs a text query to find the most relevant images for that query. However, these queries often have different distributions than the database embeddings, making challenging to achieve high accu- racy. In this work, we present LeanVec, framework that combines linear dimensionality reduction with vector quantization lo accelerate similarity search on high-dinenniooal vec- tors while maintaining accuracy. We present LeanVec variants for in-distribution (ID) and out-of-distribution (OOD) queries. LeanVce-ID yields accuracics on par with those from re- cently introduced deep learning alternatives whose computational overhead precludes their usage in practice. LeanVec-OOn uses two novel techniques for dimensionality reduction that consider the query and database distributions to simultaneously boost the accuracy and the performance of the framework even further (even presenting competitive results when the query and database distributions match). All in all, our extensive and varied experimental results show that LeanVec produces state-of-the the-art results, with up to 3.7x improvement in search throughput and up to 4.9x faster index build time over the state of the art
1 INTRODUCTION
High-dinensional embedding vectors, stemming from deep learning models, have become the quintessential data representation for unstructured data, e.g., for images, audio, video, text, genomics, and computer code (e.g., Devlin et al., 2019; Radford et al., 2021; Shvetsova et al., 2022; Ji et al., 2021; Li et al., 2022). The power of these representations comes from translating semantic affinities into spatial similarities bet the corresponding vectors. Thus, searching over massive collections of vectors for the nearest neighbors to a given query vector yields semantically relevant results, enabling a wide range of applications (e.g., Blattmann et al., 2022; Borgeand et al., 2022; Karpukhin et al., 2020; Lian et al., 2020; Grbovic al., 2016).
Among other similarity scarch approaches, graph-based methods (c.g., Arya and Mount, 1993; Malkov and Yashunin, 2018; Jayaram Subramanya et al., 2019) stand out with their high accuracy and performance for nigh-dimensional data Wang et al. (2021). Here, the index consists of a directed graph, where each vertex corresponds to a dataset vector and edges represent neighbor-relationslii between vectors so that the graph can be efficiently traversed to find the nearest neighbors in sub-linear time (Fu et al., 2019).
* "Equal contribution

---

Published in Transactions on Machine Learning Research (05/2024)
140K
LVQ8
FP16
rqa-76B-1M
2708/s
95GB/s
Query
Dim. reduction
Construction Search
throughput (QPS)
120K
LVQ4x8
Input dalabase veciors
100K
LeanVec
stpdis
Primary vectors
Candidates
80K
11748/s
12268/5
124GB/s
reduction
40K
6G8/s
97c8
13GB//
20K
1400B5
247GB/
Nearest neighbors
0K
16308/s
149GB/s
149G8/s 1490B/s
Secondary vectors
10
20
30
40
50
60
re-ranking
Number of threads
(a)
(b)
Figure 1: We propose VeanVec, framework to accelerate similarity search for high-dimensional vectors, including those produced by deep learning models. LeanVec combines a novel linear dimensionality reduc- tion method for in-distribution and out-of-distribution use cases with Locally-adaptive Vector Quantization (LVQ, Aguerrebere et al. (2023)) to achieve state-of-the-art performance and accuracy in graph-basee based index construction and search. (a) For high dimensional vectors (c.g., D = 768), scarch performance scales with the level of memory compression. Compared to the FP16 encoding, LVQ8 and LVQ4x8 compress the vectors by 2x and -4x for search, respectively, while LeanVec reduces the vector size by 9.6x (4.8x from dimen- sionality reduction and 2x from LVQ8). At 72 throads (our system has 36 physical cores and 72 threads), LeanVec provides 8.5x performance gain over FP16 while consuming much less memory bandwidth (95 vs. 149GB/s). (b) The main search in LeanVec returns nearest neighbor candidates and is executed effi- ciently using primary vectors, i.e, compressed with dimensionality reduction and vector quantization. The candidates are then re-ranked using secondary vectors, i.c., quantized with LVQ.
Aguerrebere et al. (2023) have recently shown that, when properly implemented, graph search is bottlenecked by the memory bandwidth of the system, which is mainly consumed by fetching database vectors from memory in a random access pattern (due to the complexity in globally ordering high-dimensional vectors and to the way any graph traversal works, i.e, hoping from one node to the other). Mainstream state-of- the-art vector quantization techniques are either specifically designed for sequential access pattern (André et al. 2021; Guo et al., 2020), rendering them not suitable for graph search, incur more expensive similarity calculations by inereasing the number of memory accesses (Jégou et al., 2011) (more details in Section 4). To reduce these access limes, Aguerrebere el al. (2023) introduce a light method, Locally-adaptive Vector Quantization (LVQ), that greatly accelerates the search and leads to state-of- otate-of-the-art the-art performance. Although LVQ removes the memory bottleneck in vectors of moderate dimonsionality (D = 128), we observe increased memory bandwidth and computational pressure for higher dimensional (e-g., D = 512, 768) deep learning embedding vectors. Higher memory utilization drastically increases the memory latency (Srinivasan et al., 2009) to access each vector and results in suboptimal search performance. Even masterful placement of prefetching instructions in the software cannot hide the increased latency. These difficulties extend to the time-consuming procedure of constructing graph-based index construction speed is proportional to search speed. In a world where both academic and industrial deployments of similarity search overwhelmingly use deep learning embedding vectors, it is paramount to address this performance gap.
An additional difficulty with modern applications of similarity search is cross-modal querying, i.e., where a user uses a query from one modality to fetch similar clements from a different modality (Radford et al., 2021; Yu et al., 2022; Li et al., 2023). For instance, in (ext2image applications, text queries are used to retrieve semantically similar images. Alternatively, sometimes queries and database vectors are produced by different models, e.g., in question-answering applications (Karpukhin et al., 2020). In these cases, queries come from a statistical distribution differrnt from the one underlying the database vectors, which makes applying vector compression techniques learned from the data itself a more challenging problem (Jaiswal et al., 2022).
In this work, we introduce LeanVec, a framework that combines linear dimensionality reduction with Locally-adaptive Vector Quantization (LVQ) to accooerate similarity search for high-dimensional vectors, making it suitable for applications with deep learning embedding vectors. Lean is inscribed in the stan-
2

---

Published in Transactions on Machine Learning Research (05/2024)
dard search-and-rerank paradigm popular in similarity search. We present LeanVec variants for the two main cases: in-distribution (TD) and out-of-distribution (OOD) queries. LeanVec's compression lowers the required memory bandwidth and provides a proportional increase in search throughput. On the rqa-768-1J 1M dataset (refer to Table 1 for dctails), LeanVee compresses vectors by 9.6x (4.8x from the dimensionality reduction and 2x from IVQ) over the baseline of FP16 vectors and provides a 8.5x performance gain while consuming much less memory bandwidth (see Figure la). The performance gain increases even further as the dimensionality increases. For instance, in the standard gist-960-1M, 1M dataset, LeanVec shows -12x im- provement over the uncompressed FP16 vectors (see Figure 12 in the appendix). We present the following contributions:
We show that linear dimensionality reduction can be effectively used on-the-fly to increase the performance of graph- similarity search, with no degradation in quality, and leads to state of the art results for high-dimensional vectors, including those produced by deep learning models.
We show that LeanVec can be used to build high-quality graph indices in a fraction of the time required for the original vectors, yiclding up to 8.6x runtime improvement.
For the ID case, LeanVec-ID improves upon previous work using principal component analysis (PCA) (Jegou et al., 2010; Gong et al., 2012; Babenko and Lempitsky, 20146; Wei et al., 2014) by combining it with IVQ, bringing search speedups of up to 3.6x over the state of the art LeanVec-ID does not make any assumptions about the statistical distribution of the query vectors.
For the OOD case, we present new linear dimensionality reduction technique, LeanVec-OOD, that finds the optimal projection subspaces for the dataset and a representative query set to reduce the errors in the similarity computations. We present two lightweight and fast optimization algorithms for LeanVecOOOD, We present a detailed convergence analysis for one of these variants (based on a non-convex Frank- Wolfe algorithm). We show that LeanVec-OOD performs as good as LeanVec-ID in the ID case and is vastly superior in the OOD case.
For reproducibility, we will contribute the LeanVec implementation to Scalable Vector Search, an open source library for sigh-performance similarity search." We also introduce and will open-sourec two new datasets with different types of OOD characteristics.
The remainder of this work is organized follows. We introduce LeanVec in Section 2, covering the overall framework and the novel techniques for OOD dimensionality reduction. We then present in Section 3 extensive experimental results comparing LeanVec to its alternatives and showing its superiority across all relevant metrics. In Section 4 we review the existing literature and its relation to our work. We provide a few concluding remarks in Section 5.
2 LeanVec: a framework to accelerate similarity search for high-dimensional vectors
Notation. We denote rectors/maatices by lowercase/uppercar. bold letters, e.g. v E RR" and E Rmxn
We start from a set of database vectors X= {x, E " to be indexed and searched. We use maximum inner product as the similarity scarch metric, where one seeks to retrieve for query q the l databasc vectors with the highest inner product with the query, i.e., a set N such that A C X, W = k, and (VX;& E N, VX; E X' (W) (q) 2 xq,x.). Although maximum inner product is the most popular choice for deep learning vectors, this choice comes without loss of generality as the common cosine similarity and Euclidean distance we can be trivially mapped to this scenario by normalizing the vectors.
LeanVec accelerates similarity search for deep learning embedding vectors by using the approximation
(q. x) ~ (Aq, qua.tta((BB));
(1)
where B, B E RdxD are orthonormal projection matrices, d < D, and quant(v) is a method to quantize each dimension in v. The projection matrices reduce the number of entries of the database vectors and the quantization reduces the number of bits per entry. The reduced memory footprint decreases the time it takes
3

---

Published in Transactions on Machine Learning Research (05/2024)
to fetch each vector from memory. Furthermore, the lower dimensionality alleviates the algorithm's com- putational effort (i.e., requiring fewer fused multiply-add operations). This approximation enables efficient inner product calculations with individual database vectors (no batch-processing required), which makes it ideal for the random memory-access pattern encountered in graph search.
For the quantization step, we use Locally-adaptive Vector Quantization (I.VQ), recently introduced by Aguer- rebere et al. (2023), it is specifically designed to perform aucoding/decodiingg with great efficiency, while incurring negligible search accuracy penalties.
The LeanVec framework is schematically depicted in Figure 1b and its constituents are described next. The computation of the projection matrices will be presented in sections 2.1 to 2.4. In the following, we refer to the set (Bx.)) X; E } as primary veclors and to the set {quant((x)) x E } as secondary veclors.
Search. Here, the primary vectors are used for traversing the graph. We compensate for the errors in the inner- inner-product approximation by retrieving a number of candidates greater than k. Then, we use the set of secondary veclors, i.e,, (quant(x:)) x; E X); ; to re-compute the inner products for those candidates and to return the top-k. The dimensionality reduction for the query, ie,, the multiplication Aq, is done only once per scarch incurring a negligible overhead in the overall runtime.
Graph construction. Only the primary vectors are used for graph construction. The secondary vectors are not used at this stage. Aguerrebere et al. (2023) had already analyzed the robustness of the graph construction to quantization with LVQ. Notably, our experimental results show that the robustness extends to a dimensionality reduction as well. It is important to note that searches are an essential part of the graph construction process (Malkov and Yashunin, 2018; Fu et al., 2019). As such, our achieved search acceleration directly translates into graph construction acceleration, as shown in our experimental results. See Appendix A for discussion on graph construction and its acceleration.
LeanVec does not use dimensionality reduction to decrease the memory footprint of the similarity search index, but to accelerate its performance. LeanVec, in its current form, effectively increases the total footprint by keeping both primary and secondary vectors in memory. Without loss of generality and in pursuit of a reduced footprint, we could only store to D d dimensions for the secondary vectors (see the discussion in Scction 2.1) which would remove the current overhead. Alternatively, other encodings (e.g., Douze et al., 2018) can be used for the secondary vectors.
2.1 Dimensionality reduction for in-distribution similarity search
Let us begin with a few standard definitions. The Stiefel manifold is the set of row-orthonormal matrices, formally defined as St(D, d) = {U E Rd JU I}. Let |ellop denote the standard spectral norm, defined as ||A llop sup Al|A / [|v||,
E v + 0). The convex hull C of all row-orthonormal matrices in St(D, d) is the unit-norm ball of the spectral norm, ie.,
C= Allpp 1}.
(2)
In the in-distribution (ID) case, we compute the projection matrices from the set of database vectors X' fx, E RD)" iim Let d < D. We use matrix M gaxD to obtain the low-dimensional representation
x; = M Mx; + e;:
where e; = (I- M M)x; is the representation error. A desirable characteristic for M would be to define a d-dimensional orthogonal subspace of RR,, i.e., MM = I. Notice that e, can be represented losslessly using D - d dimensions. Commonly, one would seek to find the matrix M that minimizes the errors e, by solving
min Mc)
x - X-MMMX MX
(4)
F
where the matrix X E Rxx is obtained by horizontally stacking the database vectors. This is the traditional Principal Component Analysis (PCA) problem, whose solution is given by keeping the d left singular vectors of X that correspond to the singular values with larger magnitudes.
With representation, we approximate (q,x;) x;) (q.M 10,MMaan Mx,) = (Mq. Mx.) and thus A B = M.
4

---

Published in Transactions on Machine Learning Research (05/2024)
2.2 Query- aware dimensionality reduction for -ustr--dist similarity search
From the ID approximation in Equation (3), we get
(g. xx) - [Mq.Mxx = (q. e.).
(5)
The smaller the magnitude of e4) is, the more accurate the approximation becomos. Observe, however, that Problem (4) can only produce guarantees about (q, e,) when the queries and the database vectors are identically distributed. To address this problem, given database vectors X' = fx: (R)) and query
vectors Q {x, E }
we propose to minimize the magnilude of (q, ei) directly.
Thus, given representative set of query vectors Q = = ER?J" "R]) propose the alternative model
x;
Bx; E
(6)
where E, = A the new representation error. We can now minimize (qj. Ei) E:). for all i. yielding the main optimization problem of this work,
- Q -
min A,
(7)
where X E Dxx and Q E RDxm are oblained by horizontally stacking the database and query vectors, respectively. We refer to this dimensionality reduction model as LeanVec-OOD, We use LeanVec-OOD for similarity search with the approximation (q.x.) x (Aq, Bx;), where the lower dimensionality alleviates the algorithm's 's computational burden (i.e., requiring fewer fuseed multiply-add operations) while simultaneously reducing memory bandwidth pressure and footprint.
LeanVec-OOD allows suitable matrices for dimensionality reduction be found and is specifically designed for the case where X' and Q are not drawn from the same distribution. However, if X' and Q are drawn from the same distribution, how does LeanVec compare to PCA? The following proposition addresses this question, showing that the LeanVec will perform similarly to PCA in the ID case (the proof is in Appendix B). Proposition 1. Problem (7) is upper bounded by the singular value decomposition of X.
Proposition 1 ensures that one can run LeanVec-OOD safely, without checking if the query and dataset sets are iso-distributed or not. Of course, LeanVec-OOD comes with the additional requirement of having a representative query set for training. Thankfully, this is not a ominous requirement as the standard calibration of the similarity search system (i.e., finding a suitable operating point in the accuracy-speed trade off for given application) already requires having a suitable query set..
Interestingly, for the searches performed as part of the graph construction process, database vectors are used as queries implying that, even for OOD use cases, the construction algorithm works with ID data. Proposition 1 ensures that graph construction can be executed with LeanVec-OOD.
Efficiency. Developing the squared Frobenius norm, we can equivalently write Problem (7) as
min Tr (AKQA T BKxB T + Kookx - AKQA T BKx), where Ko = QQ Kx = XXT A.BEC
(8)
Before solving this problem, we can precompute the D D matrices KQ and Kx. This removes the optimization's dependency in the number of database and query vectors and enables dealing with large data and query sets with great efficiency. Additionally, relying on the second-order statistics Kq and Kx prevents from overfitting the query training set. Moreover, the error between a sample covariance matrix and its expectation converges very quickly (Koltchinskii and Lounici, 2017) with a growing sample size. We can thus safely use uniform subsampling to compute Kq and Kx, as observed in figures 15 and 16 of the appendix. We need a minimum of D samples (D query and D database vectors) to ensure that these matrices are not artificially rank-deficient. Using m 10 queries and n 10x database vectors for training amounts to 13x (20x) query oversampling for D 512 (D) 768) over the minimum number of samples D.
5

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 1: Frank- Wolfe BCD optimization for
10
10011
Relative orthogonality error
Problem (9) with factor E (0,
10-1
Tet A (0) B E EC, e.g,, A (0) and B O;
||AAT 11B
100
[
11F./2
for i ...... I do
10
3
- 1/(t+ 1)";
10-30
X -- argmax
8 8A [ [(A (9, (B()))) D Eq. (13)
4
SEC
37
205
121
51
(1+1) f (1 - 7) A
Iterations
5
8/6 f- argmax - (A (t+1), B B); D.g. (13)
Figure 2: Algorithm 1 converges in 51 itera- tions for open- open- images-ma-e---eee 1- with D = 512 and d= 128. The total runtime is 4 seconds, respec- lively. Relaxing the orthogonality constraint in- curs relatively small error of 10-3
6
SEC
B(++)) 1--7)0 (1- +
7
2.3
Optimizing the LeanVec-OOD loss with Frank-Wolfe algorithm
Optimizing Problem (7) is not trivial as it is constrained optimization problem with non-convex loss function. Additionally, its constraints are non-convex the Stiefel manifold is non-convex set. Here, in order to make the optimization of Problem (7) more amenable, we define the relaxed problem
min f(A, A.BEC
(9)
where S(A, B) = 0 A
(10)
Here, we replace the non-convex constraints involving the Stiefel manifold by convex constraints involving its convex hull, Equation (2). Now, Problem (9) is convex and has a smooth loss function on A for fixed B and vice versa. Not only that, but, we will next, these convex problems be solved efficiently. We can thus recur to block coordinate descent (BCD) method, iteratively fixing one of the variables and updating the other one.
For these subproblems, we use the Frank- algorithm (a.k.a. conditional gradient), a classical optimizer for solving a problem with a convex and continuously diffcrentiable loss function f where the variable belongs a convex set (Frank et al., 1956). Given an initial solution y()) E DD the optimization procedure is given by the following iterations for O,...,T,
8 < t-argmax($ (V(()(())
(11)
sED
((+)) <- (1-7) 7
(12)
Equation (11) computes the direction in D that yields the steepest descent, ie., the more aligned with (f)) The update in Equation (12) guarantees that the iterates remain in D by using convex combination of elements in D.
The function f in Equation (10) has continuous partial derivatives given by (KQ, Kx defined in Problem (8))
A6 (A, 2BKxB
#
TOKKBBAKOK AKę 2BKxKQ. and a (A, = =2AKqA TBX 2AKaKx
(13)
We show that Equation (11) has an efficient solution for particular subproblems. We can write both updates as suppssi., C), where (.-)) is the standard matrix inner product and C Rdx D stands in oither for the d x D gradient matrices A (AA or aB f(A. B). This lincar problem has a solution
Recently, Ablin al. (2023) proposed efficient optimization methods the Stiefel manifold. We leave the study this option future work.

---

Published in Transactions on Machine Learning Research (05/2024)
wit-512-1M
Algorithm 2: Eigenvector search op-
128
160
timization for Problem (15).
=
192
LeanVec loss
224
Find B E [0, 1J that minimizes the
256
loss in Problem (14) with
10a
289
320
P + projection($);
Procodure projection(3)
return the matrix PE Su(D, d)
formed by the d eigenvectors of
0.0
0.2
0.4
0.6
0.8
1.0
1.2
K3 1- K= Kx with the largest cigenvalues, where Kq = QQ and Kx = Xx";
Figure 3: The loss in Problem (14) is smooth function of B when P eigsearch(3) and has unique minimizer (different for cach d). Algorithm 2 finds the minimum (marked with circle) of this loss. Additional results in Figure 17 of the appendix.
given by UVT, where UEVT C is the singular value decomposition of C (Jaggi, 2013). This update is very efficient for large datasets by working d x D matrices.
Equipped with these tools, we can pose the complete optimization procedure in Algorithm 1. There, we update A (resp. B) given a fixed B (resp. A) by rumning one Frank-Wolfe update. The factor a E (0, 1), proposed by Wai et al. (2017) for the step size Y 1/(t + 1)a, can replaced by a line search speed up the optimization. In our experiments we did not observe a need for such a perfor- mance tuning. In practice, we use early termination in Algorithm 1, i.., we stop the iterations whenever S A (++1), B((+1) / (A (A B /S (A() (()) < 10-3, yielding fast runtime, see Figure 2. In Ap- pendix C, we prove the convergence rate of Algorithm 1 to stationary point of Problem (9).
2.4 Optimizing the LeanVec-OOD loss with eigenvector search
In this section, we assume A = B. This assumption leads to new optimization technique for the LeanVec- OOD loss. Given = A = B and eliminating constant factors, Problem (8) can be rewritten as
Tr TP(KKpP PKxPT -2KqP 2KgPTPXx) PeS((D,)
min
(14)
Here, we can see that it would be desirable to align P with both the d leading eigenvectios of Ko and with those Kx. An intuitive idea would to set using the leading eigenvectors of KQ + kx.
However, the matrices KQ and Kx are summations over two different numbers of samples (i.c., n and m are not necessarily equal). This asymmetry would artificially give more weight, for example, to Kx if n m. We compensate this imbalance by scaling the loss Problem (14) by the constant 1 obtaining
min Tr ( KQ) P (D))
Kx ( P - ( PTP (tKx))
(15)
Now, we could set P to the d leading eigenvectors of 1g + Kx Although an improvement, this equal weighting is not empirically optimal. We thus add scalar factor 3 E 14, and examine the eigenvectors of
K B m 1-2 _Kx.
(16)
Empirically, we observe in Figure 3 that the loss in Problem (15) is a smooth function of B when P E dx is formed by the d leading eigenvectors of K3. Moreover, it has a unique minimizer. Our resulting optimization, summarized in Algorithm& 2, uses a derivative-free scalar minimization technique (Brent, 2013) to find the value 3 that provides the optimum balance.
In the ID case, we have 1 KQ 1 K in expectation. The cigenvectors of K3 are invariant to the value of m n 8. Hence, in this case, hm offers seamless fallback, becoming equivalent to Problem (4).
7

---

Published in Transactions on Machine Learning Research (05/2024)
Table 1: Evaluated datasets, where n is the number of database vectors and D their dimensionality. In all cases, we select the target dimensionality d that yields maximum performance at 90% accuracy (10- recall@10); The datasets are originally encoded using 32-bits floating point values. We use separate learning and test query sets, each with 10K entries. The datasets introduced in this work are marked with star.
Dataset
D
Similarity
d
Dataset
D
Similarity
d
In-distribution
Out-of-distributt
12i-200-1M
200
1M
Inner prod. 192
gist-960-1M
960
1M
Euclidean
160
t2i-220011M
200
10M
Inner prod. 192
deep-256-1M
256
1M
Fuclidean
96
'wit-512-10
512
1M
Inner prod. 256
Apen-images-512-IM
512
1M
Cosine
160
laion-512-IM
512
1M
Inner prod. 320
open-imagee-512-13MM
512
13M
Cosine
160
"rqa-768- IM
768
Inner prod.
160
'rqa-768-10M,
768
10M
Inner prod.
160
Algorithm/ 2 is highly efficient and achieves good local minima the LeanVec-OO1 OOD loss but, so far, lacks theoretical guarantees. However, we can use Algorithm to shed light on the quality of the solution P given by Algorithm If we set A < P and ( f- P in Algorithm 1, Algorithm converges in a handful of iterations, improving the loss by less than 2% as observed in Figure 18 of the appendix (we use line search for the gradient step y to ensure that stay within the same basin). We observe empirically that the theoretical guarantecs of Algorithm 1 translate to the solutions of Algorithm 2 and posit that further theoretical analysis may help clarify its empirical performance. Lastly, we point out that both algorithms perform similarly in the end-to-end similarity search evaluation (see Figure 18 of the appendix).
3 Experimental results
We integrated the proposed LeanVec into the state-of-the-art Scalable Vector Search (SVS) library (Aguer- rebere et al., 2023) and now present its performance improvements over the state-of-the-art techniques and open-source libraries for graph search and construction. Diverse ablation studies show the impact of the different hyperparameters such as, for example, the target dimensionality d and the quantization level.
Datasets. We evaluate the effectiveness of our method on wide range of datasets with varied sizes (n 1M to 13M) and medium to high dimensionalitics (D = 200 to D 960), containing in-distribution (ID) and oul-of-distribution (OOD) queries, see Table 1. For ID and OOD evaluations, we use standard and recently introduced datasets (Zhang et al., 2022; Babenko and Lempitsky, 2021; Schuhmann et al., 2021; Aguerrebere et al., 2024). We also introduce new datascts with different types of OOD characteristics: cross-modality with wit-512-1M and question-answering with rqa-768-1M and 10M. See Appendix E for more details.
Setup. Throughout the experiments, LeanVec uses LVQ8 for the primary vectors and FP16 for the secondary vectors. For cach dataset, we use the dimensionality d that yields the highest search performance at 90% accuracy (see Table 1). For LeanVec-OOD, we present the results using Algorithm (Algorithm 2 performs similarly as shown in Figure 13 of the appendix.) To prevent overfitting, we use two separate query sets (see Appendix E): one to learn the LeanVec-OOD projection matrices and to calibrate the runtime search parameters in SVS, and one to generate our results. As standard (Aumüller et al., 2020a), we report the best out of 10 runs for each method. Further experimental details can be found in Appendix D, including a discussion on hyperparameter selection in Appendix D.2.
Search performance. For this study, we use the graph built with uncompressed FP16 vectors to evalu- ate the search performance gains provided by LeanVec over the state-of- methods in SVS on high- dimensional embedding vectors. Figures 4 and 5 show the scarch performance on datascts with in-distribution (ID) and out-of-disttribution queries, respectively. In the ID datasets, both Vec-ID and LeanVec-OOD show similar performance, confirming Proposition 1 in practice. LeanVec-OOD provides up to 10.2x and 3.7x performance gains over FP16 and LVQ, respoctively, at a 10-rocall@10 of 0.90 on gist-960-1M as has the highest dimensionality amongst the evaluated datasets (recall is defined in Appendix D.3). LeanVec-Oon OOD shines on the OOD datasets, outperforming LeanVec-ID and IVQ by up to 1.5x and 2.8 2.8x, respectively, at
8

---

Published in Transactions on Machine Learning Research (05/2024)
throughput (QP5)
1,000K
deep-256-1M
400K
gist-960-1M
750K
open-Images-512--M
500K
500K
200K
250K
0K
0.80
0.85
0.90
0.95
0.80
0.85
0.90
0.95
0.80
0.85
0.90
0.95
10 recall@10
10
@ecal
10 recal @10
FP16
LVQ
LeanVec-ID
LeanVec-OOD
Figure 4: For in-distribution (ID) datasets, LeanVec-ID and LeanVec-OOD show similar performance and vast gains of up to 10.2x and 3.7x over FP16 and LVQ, respectively, for 10-recall@10 of 0.90.
throughout (OPS)
600K
12i-200-1M
400K
wit-512-1M
200K
laion-512-1M
300K
rqa-768-1M
200K
400K
200K
100K
100K
200K
06
OK
0K
OK
0.80
0.85
0.90
0.95
0.80
0.85
0.90 0.95
0.80
0.85
0.90 0.95
0.80
0.85
0.90 0.95
10 reca I@10
10 recall@10
10 recall@10
10 recall@10
FP16
LVQ
LeanVec-ID
Leanvec-OOD
Figure 5: Search performance of VeDnVec-OOD shines LeanVec-ID and IVQ by up to 1.5x and 2.8x, respectively, for 10-recall@10 of 0.90.
(OOD) datasets, outperforming
10-recall@10 of 0.90 IM..768-MM Note that the performance advantage of LeanVec diminishes when the dimensionality of the dataset is small, as in the case of t2i-200-1M. Lastly, LeanVec does not show significant gains in laion-512-1M. In this case, linear dimensionality reduction significantly impacts the accuracy of the search. We plan to address this issue in future work.
Index construction. LeanVee builds graphs up to 8.6x and 4.9x faster than FP16 and LVQ (Figure 6) without degrading their quality, i.e., their search accuracy and speed (see Figure 14 in the appendix). The accuracy preservation is surprising fact, as the graph, being related to the Delaunay graph, is heavily related to the local topology of the data. Further theoretical studies to understand this phenomenon are required. In LeanVec's construction timings, we include the time to learn the projection matrices. We point out that the LeanVec-OOD learning (Section 2.2) is implemented in Python, which can be casily optimizod.
Comparison with the state of the art. In addition to the stale-of-the-art SVS-IVQ (Aguerrebere et al., 2023), we compare LeanVec to three widely adopted methods: HNSWlib (Malkov and Yashunin, 2018), Vamana (Jayaram Subramanya et al., 2019), and FAISS-IVFPQfs (Johnson et al., 2021). See Appendix D for further experimental details and configurations. Here, use LeanVec-OOD as it achieves equal better performance than LeanVec-ID in all cases. As shown in Figure 7, the combination of LeanVec with the SVS library achieves a significant performance lead over the other prevalent similarity search methods on high-dimenssonal datasets. SVS-LeanVec provides 1.1x, 1.9x, 2.8x, and 3. 7x performance boost on t2i-200- 1M, deep-256-11 1M, rqa-768-110 and gist-960-1M, respectively, at a 10-recall@10 of 0.90 over the second-best method, SVS-LVQ, and 2.4x, 3.8x, 7.8x, and 8.5x, respectively, over the third-best method, FAISS-IVFPQIs. Note that the advantage gets higher as the dimensionality increases.
LeanVec scaling on larger datasets. We run LeanVec on three datasets of 13 and 10 million vectors; open-inaggs-512-13M. 1qa-768-10M, and 121-200-10M. As shown in Figure 8, LeanVec continues to show performance gains in larger datasets. LeanVec-OOD achieves 2x and 2.4x performance benefits over LVQ in -ww-iinages-11--111 and rqa-768-10M. respectively, at a 10-recall@10 of 0.90. Leaving SVS-LVQ aside, LeanVec-OOD provides much higher benefits when compared the next best performing methods: 7.9x and 13.7x over HNSWIib in open- aaa---aagss-11111.. and benchmark dataset for the OOD track of the NeurIPS'23 Big-ANN competition (Simhadri et al., 2024), we
respectively. On t2i-200- 10M, the
9

---

Published in Transactions on Machine Learning Research (05/2024)
FP16
LVQ
LeanVec ID
LeanVec OOD
Index build time (Sec)
500
400
300
225
200
100
46 d6
38
65 45
46
D07
40
85
66
deep-256-1M
gist-960-1M
open-images-12-1M 121-200-1M
wit-512-IM
lalon-512-1M
rqa-768-1M
Figure 6: LeanVec accelerates graph construction compared to the state-of-the-art SVS runtimes (by up to 8.6x and 4.9x over FP16 and LVQ. respectively). For OOD datasets, the increase in construction time with LeanVec-OOD over LeanVec-IT) brings faster search performance.
throughput (QPS)
1,000K
400K
gist-960-1M
121-200-1M
300K
rqa-768-1M
600K
200K
400K
500K
200K
200K
100K
0K
OK
OK
0K
0.80
0.85 0.90 0.95
0.80
0.85
0.90 0.95
0.80
0.85
9.
0.95
0.80
0.85
0.90
0.95
10
recall@10
10 recall@10
10
recail@10
10
recall@10 10
SVS LeanVec OOD
SVS LVQ
HNSWibb
Vamana
FAISS IVFPQfs
Figure 7: The combination of the statc-of-the-art SVS library with LeanVee outperforms other mainstream similarity search methods by large margin. Compared to FAISS-IVFPQSs, the second-bes method outside SVS, SVS-LeanVee provides up to 8.5x performance gain at 10-recall@10 of 0.90.
consider the track winner RoarANN (Chen et al., 2024). SVS-LeanVec-OOD and SVS-LVQ perform similarly due the original low-dimensionality (D 200) and outperform RoarANN by 2x at 10-rocall@10 of 0.90.
A Ablation study: The target dimensionality. The target dimensionality d required to provide optimal scarch performance a given accuracy depends multiple factors like the system and datasct character- istics. As expected, lower dimensionality yields higher search throughput at the cost. of some accuracy loss. As shown in Figure 9, the performance using values of d that are either too low (d= 128) or too high (d = 320) for LeanVec-OOD depart from the sweot spot, which is dataset-dependent. With low d, this is due to a loss accuracy, which we compensate by retrieving more neighbor candidates for the re-ranking step. For high d, the memory and computation costs outweigh the diminishing accuracy improvements. For instance, in gist-960-IM and rqa-768-1M the best performance is reached at d 160, while in wit-512-1M the best performance is attained with d 256.
Ablation study: The level of vector quantization. LeanVec uses dimenssionaliy--edeeed primary vectors to fetch nearest neighbor candidates and secondary vectors to re-rank these candidates (see Section 2). Both vectors can be quantized using LVQ. In Figure 10, we study the effect of using different levels of quantization. For the primary vectors, using IVQ outperforms not using compression (FP16) and comes with lower memory footprint. However, sometimes LVQ4 (using 4 bits per value) not sufficient, requiring longer search windows reach the same as LVQ8 (using 8 bits per value). For the secondary vectors, LVQ8 and FP16 provide similar performances except for t2i-200-1M. where FP16 does slightly better. If memory footprint is important, we recommend using LVQ8 for the sccondary vectors at minimal cost.
A Ablation study: Re-ranking. Figure 11 compares the recall of LeanVec variants with two recent neural network based dimensionality reduction techniques: NN-MDS (Canzar et al., 2021) and CCST (Zhang et al., 2022). To remove confounding factors, we perform exhaustive scarch for this experiment. NN-MDS and CCST only support the Euclidean distance, thus, for inner-produce datasets, we used the transformation Bachrach et al. (2014) to convert the vectors. Dimensionality is reduced by 4x for each dataset except
10

---

Published in Transactions on Machine Learning Research (05/2024)
open-images-512-13
rqa-768-10M
t2i-200-10M
throughput (QPS)
400K
Ehfolgghpt (QPS)
150K
300K
SVS-LeanVec-OOD
SVS-LeanVec-ID
300K
100K
200K
SVS-LVQ
200K
HNSWIbb
50K
100K
Vamana
100K
FAISS-IVPPQTs
0K
0K
0K
RoarANN
0.80
0.85
0
90
0.95
0.80
0.85
0 90
0
95
0.80
0.85
0.90
0.95
10
recall@10
10
1@
10
recall@10
Figure 8: LeanVec exhibits superior performance on large-scale datasets. SVS-LeanVec-OOOD achieves perfor- mance gains of up to 2.4x over SVS-LVQ and 13.7x over HNSWlib at 10-recall@10 of 0.90. On t2i-200- compared to RoarANN (Chen et al., 2024), the OOD track winner of the NeurIPS'23 Big-ANN competition (Simhadri et al., 2024), SVS-LcanVec and SVS-LVQ provide 2x performance gain at a 10-recalI@10 of 0.90.
throughout (OPS)
400K
gist-960-1M M
400K
wit-512-1M
300K
rq8-768-1M
d=128
200K
d=160
200K
200K
de 1º1
100K
d=256
d=320
06. .0
0.85
0.90
0.95
OK
0.80
0.85 0.90 0.95
0K
0.80
0.85 0.90 0.95
SVS-LVQ
10 recall
recall 10
10 recall@11
Figure 9: The level of dimensionality reduction at which LeanVec provides the best performance varies for each dataset. However, in all cases, LeanVec brings clear performance improvements over SVS-LVQ, state- of-the-art solution that does not involve dimensionality reduction. There is a tradeoff between the accuracy and search performance at different target dimensionalities d. In most cases, setting 256 is a reasonable compromise with 2-3x bandwidth reduction.
1 where we reduce by 2x.* For all three methods, the recall at 10 unacceptably low (e.g., below 0.90). However, the recall at 50 improves drastically. This observation supports the use of re-ranking, as we can obtain 50 candidates, recompute their distance using secondary vectors yield recall at 10 on par with the recall at 50. LeanVec-OOD shows higher recalls than LeanVec-ID datasets with OOD queries (12i-200-1M) MM and rya-768-1M), Note that NN-MDS and CCST use complex neural networks to transform the vectors in low dimensionality, precluding their use for search as the query transformation time is exorbitant
4 Related Work
The application of linear dimensionality reduction for approximate nearest neighbor search is not new (Deer- wester et al., 1990; Ailon and Chazelle, 2009). A few studies (Jegou et al., 2010; Gong et al., 2012; Babenko and Lempitsky, 20146; Wei et al., 2014) used it for ID queries while the OOD) case has been largely ignored.
Hashing (Indyk and Motwani, 1998; Jafari et al., 2021) and learning-to-hash (Wang et al., 2018; Luo et al., 2023) techniques often struggle to simultaneously achieve high accuracy and high speeds.
Product Quantization (PQ) (Jégou et al., 2011) and other related methods (Ge et al., 2013; Babenko and Lempitsky, 2014a; Zhang et al., 2014; André et al., 2015; Matsui et al., 2018; Guo et al., 2020; Wang and Deng, 2020; Johnson et al., 2021; André et al., 2021; Ko et al., 2021) were introduced handle large datasets in settings with limited memory capacity (e.g., Jayaram Subramanya With these techniques, the similarity between (partitions of) the query and each corresponding centroid is precomputed to create a look-up table of partial similarities. The complete similarity computation can then be posed as a set of indexed gather and accumulate operations on this table, which are generally quite slow (Pase and Agelastos, 2019). This is exacerbated with an increased dimensionality D: the lookup table does not fit in L1 cache, which slows down the gather operation even further. Quicker ADC (André et al., 2021)
al., 2019; Jaiswal et al., 2022).
412-200-1M requires > 100 reach acceptable recalls, but CCST only allows the reduction factors of
11

---

Published in Transactions on Machine Learning Research (05/2024)
1,000K
deep-256-1M
400K
gist:960-1M
10--200-MM-
300K
rqa-768-1M
throughput (QPS)
600K
750K
300K
200K
400K
500K
200K
200K
100K
250K
10K
OK
0K
0.80
0.85 0.90 0.95
0.80
0.85 0.90 0.95
0.80
0.85
0.90
0.95
0.80
0.85 0.90 0.95
10 reca 1@10
10 recall@ 10
10 recall@ 10
10 recal @10
Primary Secondary
FP16 FP16
LVQ4 FP16
LVQ4 LVQB
LVQ8 FP16
LVQ8 LVQ8
Figure 10: LeanVec-OOD performance scnsitivity to different compression schemes used for the primary and secondary vectors. Primary vectors show higher performance when compressed with LVQ8. For the secondary vectors, LVQ8 and FP16 yield similar performance except (2i-200-1M where FP16 does better.
deep-256-1M
gist-960-1M
t2l-200-1M
rqa-768-1M
Recall
1.0
0.69
0.99
0.69
0.99
0.70
0.99
0.73
1.00
1.0
0.75
1.00
0.74
1,00
0.80
3.00
0.80
1:00
0.6
0.60
0.51
0.64
1.0
0.94
0.75
0.99
0.64
0.4
0.5
0.5
0.2
0.21
0.23
0.36
0.16
0.0
Leanver
Lean
NN-MDS
CEST
0.0
0.0
0.0
ID
000
10 recall@10
10 recall@50 (re-ranking)
Figure 11: The recall at 10 of all dimensionality reduction techniques suffer (blue bars). However, recall 50 remains strong. Thus, after selecting 50 candidates and re-ranking them, recall at 10 reaches optimal levels. Like other otate-of-the-art techniques, both LeanVec variants show perfect recall on ID datasets, while LeanVec-OOD proves superior in OOD datasets. NN-MDS and CCST employ neural networks for non-linear dimensionality reduction, whose computational complexity precludes their use for search.
offers a clever fix by optimizing these table lookup operations using AVX shuffle and blend instructions to compute the similarity between a query and multiple database elements in parallel. This parallelism can only be achieved if the database elements are stored contiguously in a transposed fashion. This transposition, and Quicker ADC by extension, are ideally suited for inverted indices (Johnson et al., 2021) but are not compatible with the random memory access pattern in graph-based similarity search.
Dimensionality reduction is deeply related to metric learning (Bellet et al., 2013). In the ID case, any metric learned for the main dataset will be equally suitable for similarity search. However, this metric may be unsuitable for similarity scarch in the OOD case. As an instance of deep metric learning (Kaya and Bilge, 2019), CCST (Zhang et al., 2022) uses transformers to reduce the dimensionality of deep learning embedding vectors. However, the computational complexity of transformers precludes their usage for search and circumscribes their application to index construction, where they lead to significant performance gains. LeanVec outperforms CCST for index construction (Figure 11) and can be equally used for scarch.
Lastly, He et al. (2021) and Izacard al. (2020) used PCA in the context of retrieval-augmenned language models, showing that their perplexity score is maintained and their overall speed is boosted. However, they treat the similarity search system as black box and do not address out-of- distribution aspects.
5 CONCLUSIONS
In this work, we presented LeanVec, a framework that combines lincar dimensionality reduction with vector quantization to accelerate similarity search on high-dimensional vectors, including those produced by deep learning models. Additionally, LeanVec speeds up the time-consuming construction of the index used to conduct the search. We presented LeanVee variants for in-distribution (ID) and out-of-distribution (OOD) queries, both leading state-of-the-art results. Leanvec-OOD uses two novel techniques for dimensionality reduction that consider the query and database distributions to simultaneously boost the accuracy and the
12

---

Published in Transactions on Machine Learning Research (05/2024)
performance of the framework even further (even matching the performance of LeanVec-ID in the ID setting). Overall, our extensive and varied experiments show that LeanVec yields state-of-the-art results, with an up to 3.7x improvement in search throughput and up to 4.9x faster index build time over the best alternatives.
As future work, we will investigate why laion-512-1M 1M is resistant to higher levels of linear dimensionality reduction (and whether this behavior extends other datasets) and propose solution. We also plan optimize the LeanVec-OO1) learning algorithm, implementing it in C++ using lutel OneMKL (2023).
References
Ablin, P., Vary, S., Gao, B. and Absil, P.-.. (2023), 'Infcasible deterministic, stochastic, and variance- reduction algorithms for optimization under ort orthogonality constraints', preprint 2303: 16510
Aguerrebere, C., Bhati, I., Hildebrand, M., Tepper, M. and Willke, T. (2023), 'Similarity search in the blink of an eye with compressod indices', Proceedings of the VLDB Endowment 16(11), 3433-3446.
Aguerrebere, C., Hildebrand, M., Bhati, I., Willke, T. and Tepper, M. (2024), "Locally-adaptive quantization for streaming vector search', Unpublished manuscript.
Ailon, N. and Chazelle, B. (2009), 'The fast Johnson Lindenstrauss transform and approxinate nearest neighbors', SIAM Journal on Computing (1), 302-322.
André, F., Kermarree, A.-.. and Scouarnee, N. L. (2021), 'Quicker ADC: Unlocking the hidden potential of product quantization with SIMD', IEEE Transactions on Puttern Analysis and Machine Intelligence 43(5), 1666-1677
André, F., Kermarree, A.M and Le Scouarnec, N. (2015), 'Cache locality is not enough: High-performanee nearest neighbor search with product quantization fast scan', Proceedings of the VLDB Endowment 94), 288 299.
Arya, S. and Mount, D.M. M. (1993), Approximate nearest neighbor queries in fixed dimensions, in ACC-SIAM Symposium on Discrete algorithms', Vol. 93, pp. 271-2801
Aumüller, M., Bernhardsson, and Faithfull, A. (2020a), NNN-BBenchmrrs: benchmarking tool for approximate ncarest neighbor algorithms', Information Systems 87, 101374.
Aumüller, M., Bernhardsson, E. and Faithfull, A. (20206), 'Benchmarking nearest neighbors', http: baannbbenchmarks com/index, html. GitHub code: Accessed: 20 Oct. 2023.
Babenko, A. and Lempitsky, V. (2014a), Additíve quantization for extreme vector compression, in 'EEE Conference on Computer Vision and Pattern Recognition', pp. 931 938.
Babenko, A. and Lempitsky, V. (2014b), 'The inverted multi-index', IEEE transactions on pottern analysis and machine intelligence (6))), 1247-1260.
Babenko, A. and Lempitsky, V. (2021), 'Benchmarks for billion-scale similarity search', simi similarity search. Accessod: 15 Feb. 2023.
yandex. http//lloobbehhhhhe
Bachrach, Y., Finkelstein, Y., Gilad-Bachrach, R., Katzir, L., Koenigstein, N., Nice, N. and Paquet, U. (2014), Speeding up the Xbox recommender system using a euclidean transformation for inner-product spaces, in 'ACM Conference on Recommender systems'.
Bellet, A., Habrard, A. and Sebban, M. (2013), 'A survey on metric learning for feature vectors and structurod data', preprint 1Yi6:3006667
Blattmann, A., Rombach, R., Oktay, K., Müller, J. and Ommer, B. (2022), 'Retrieval-angmennt diffusion models', Advances in Neural Information Processing Systems 35,
13

---

Published in Transactions on Machine Learning Research (05/2024)
Borgeaud, S., Mensch, A., Hoffmann, J., Cai, T., Rutherford, E., Millican, K., Van Den Driessche, G. B., Lespiau, J.-B., Damoc, B., Clark, A. et al. (2022), Improving language models by retrieving from trillions of tokens, in "International Conference on Machine Learning', pp. 2206 2240.
Brent, R. P. (2013), Algorithms for minimization without derivatices, Courier Corporation.
Canzar, S., Do, V. H., Jelić, S., Laue, S., Matijevié, D. and Prusina, T. (2021); 'Metrie multidimensional scaling for large single-cell data sets using neural networks', preprint bioRrii:2021.006 06. 24..4.44.2499..
Chen, M., Chen, Y., Ma, R.,, Zhang, K., Cai, Y., Shi, J., Chen, Y. and Zheng, W. (2024), 'RoarANN: Projected bipartite graph for efficient cross-modal approximate nearest neighbor scarch', https: / giub... htt///maccc/////sryryee
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K. and Harshman, R. (1990), 'Indexing by latent semantic analysis', Journal of the American Sociely for Information Science 41 (6), 391-407,
Devlin, J., Chang, M.-W., Lee, K. and Toutanova, (2019), BERT: pre-training of deep bidirectiona transformers for language understanding, in 'Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies', pp. 4171-4186.
Douze, M., Sablayrolles, A. and Jégou, H. (2018), Link and code: Fast indexing with graphs and compact regression codes, in 'Proceedings of the IEEE conference on computer vision and pattern recognition', pp. 3646-3654.
Frank, M., Wolfe, P. et al. (1956), 'An algorithm for quadratic programming', Naval Research Logistics Quarterly 3(1-2), 95-110.
Fu, C., Xiang, C., Wang, C. and Cai, D. (2019), 'Fast approximate nearest neighbor search with the navi- gating spreading-out graph', Proceedings of the VLDB Endoument 12(5), 461-474.
Ge, T., He, K., Ke, Q. and Sun, J. (2013), 'Optimized product quantization', IEEE transactions on Pattern Analysis and Machine Intelligence 36(4), 744 755.
Gidel, G., Pedregosa, F. and Lacoste-Julien, S. (2018), Frank-Wolfe splitting via angmented lagrangian method, in 'International Conference on Artificial Intelligence and Statistics', pp. 1456-1465.
Gong, Y., Lazebnik, S., Gordo, A. and Perronnin, F. (2012), 'Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval', JEEE transactions on pattern analysis and machine intelligence 35 (12),, 2916-2922
Grbovic, M., Djuric, N., Radosavljevic, V., Silvestri, F.,, Baeza-Yates, R., Feng, A., Ordentlich, E., Yang, L. and Owens, G. (2016), Scalable semantic matching of queries to ads in sponsored search advertising, in "International ACM SIGIR conference on Rescarch and Development in Information Retrieval', pp. 375- 384.
Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F. and Kumar, S. (2020), Accelerating large- scale inference with anisotropic vector quantization, in 'International Conference Machine Learning', pp. 3887-3896.
He, J., Neubig, G. and Berg-Kirkpatrice T. (2021), 'Efficient nearest neighbor language models', preprint arXiv:2109.0422
Indyk, and Motwani, R. (1998), Approximate nearest noighbors: towards removing the curse of dimen- sionality, in 'ACM Symposium on Theory of Computing', pp. 604-613.
Intel OneMKL (2023), 'Developer reference for intel oneAPI Math Kernel Library C', https://www. c/2023- 2/ 2/overview html.
intel. www.co/ccooooococcc wtt.://teccctetcc//meeem wttc/ooonttttteeeeeeeeeeeeeeeeet www/ws/wateeetwwwwwwwwwww en/ docs/ /nt////emkk/////e http://eeeeloeeeeererreeeeeeeeee
Izacard, G., Petroni, F., Hosseini, L., De Cao, N., Riedel, S. and Grave, E. (2020), 'A memory efficient
baseline for open domain question answering', preprint 1511:2012.1116.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Jafari, O., Maurya, P., Nagarkar, P.,, Islam, K. M. and Crushev, C. (2021), 'A survey on locality sensitive hashing algorithms and their applications', preprint or Xxix:21020089422
Jaggi, M. (2013), Revisiting Frank-Wolfe: Projection-free sparse convex optimization, in 'International Con- ference Machine Learning', pp. 427-435.
Jaiswal, S., Krishnaswamy, R., Garg, A., Simhadri, H. V. and Agrawal, (2022), 'ODD-DikANNN Efficient and scalable graph amns for out-of-distribution queries', preprint arXiv:2211.19550
Jayaram Subramanya, S., Devvrit, F., Simhadri, H. V., Krishnawamy, R. and Kadekodi, R. (2019), 'DiskANN: Fast accurate billion-point nearest neighbor search on a single node', Advances in Neural Information Processing Systems 32.
Jegou, H., Douze, M., Schmid, C. and Perez, P. (2010), Aggregating local descriptors into a compact image representation, in 'EEE Conference on Computer Vision and Pattern Recoguition', IEEE, pp. 3304 3311.
Ji, Y., Zhou, Z., Liu, H. and Davuluri, R. V. (2021), 'DNABERT: pre-trained bidirectional encoder repre- sentations from transformers model for DNA-language in genome', Bioinformatics 37(15), 2112-2120.
Johnson, J., Douze, M. and Jégou, H. (2021), 'Billion-Scale similarity scarch with GPUs', IEEE Transactions on Big Data 7(3), 535 547.
Jégou, H., Douze, M. and Schmid, C. (2011), 'Product quantization for nearest neighbor search', IEEE Transactions on Pallern Analysis and Machine Intelligence 33(1), 117-128.
Karpukhin, V., Oguz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D. and Yih, W.-. (2020), Dense passage retrieval for open-domain question answering, in 'Conference on Empirical Methods in Natural Language Processing', pp. 6769-6781.
Kaya, M. and Bilge, H. S. (2019), 'Deep metric learning: A survey', Symmetry 11(9), 1066.
Ko, A., Keivanloo, L., Lakshman, V. and Schkufza, E. (2021), LLow-precision quantization for efficient nearest neighbor search', preprint or Xiv:::1 10.08919.
Koltchinskii, V. and Lounici, K. (2017), 'Concentration inequalities and moment bounds for sample covari- ance operators', Bernoulli pp. 110 110-133.
Kuznetsova, A., Rom, H., Alldrin, N., Uijlings, J., Krasin, I., Pont-Tuset, J., Kamali, S., Popov, S., Malloci, M., Kolesnikov, A., Duerig, T. and Ferrari, V. (2020), 'The Open Images Dataset V4: Unified image clas- sification, object detection, and visual relationship detection at scale', International Journal of Computer Vision 128(7), 1956 1981.
Lacoste-Julien, S. (2016), *Convergence rate of Frank- Wolfe for non-convex objectives', preprint arXiv:1607.00345
Li, J., Li, D., Savarese, S. and Hoi, S. (2023), BBipp2: Bootstrapping language-inage pre-training with frozen image encoders and large language models', preprint arXiv:2301.12997
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago, A. et al. (2022), 'Competition-level code generation with AlphaCode', Science 378(6624), 1092- 1097.
Lian, D., Wang, H., Liu, 7., Lian, J., Chen, F. and Xie, X. (2020), LightRec: A memory and search-efficient recommender system, in 'The Web Conference', pp. 695 705.
Luo, X., Wang, H., Wu, D., Chen, C., Deng, M., Huang, J. and Hua, X.-S. (2023), 'A survey on deep hashing methods', ACM Transactions Knowledge Discovery from Data 17(1), 1-50.
Malkov, Y. A. and Yashunin, D. (2018), 'Efficient and robust approximate nearest neighbor scarch using hicrarchical navigable small world graphs', IEEE Transactions on Pattern Analysis and Machine Intelligence 42((4, 824 836.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Matsui, Y., Uchida, Y., Jegou, H. and Satoh, S. (2018), 'A survey of product quantization', ITE Transactions On Media Technology and Applications 6(1), 2-10.
Pase, D. M. and Agelastos, A. M. (2019), 'Performance of gather/scatter operations.
URL: https://www..ost
http//bbbioo///// 1761952
Peng, L. and Vidal, R. (2023), 'Block coordinate descent on smooth manifolds', preprint orXiv:2305. 14744
Qu, Y., Ding, Y., Liu, J., Liu, K., Ren, R.,, Zhao, W. X., Dong, D., Wu, H. and Wang. H. (2021), Rock- etQA: An optimized training approach to dense passage retrieval for open-domain question answering, in "Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies' pp. 5835 5847.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J. et al. (2021), Learning transferable visual models from natural language supervision, in 'International Conference on Machine Learning', pp. 8748-877 8763.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W. and Liu, P. J. (2020), 'Exploring the limits of transfer learning with unified text-to-text transformer', The Journal of Machine Learning Research 21, 140:1-140:60
Reimers, N. and Gurevych, 1. (2020), Making monolingual sentence embeddings multilingual using knowledge distillation, in *Conference on Empirical Methods in Natural Language Processing.
Schuhmann, C., Vencu, R., Beaumont, R., Kacamarczyk, R., Mullis, C., Katta, A., Coombes, T., Jitsev,
J. and Komatsuzaki, A. (2021), 'LAION-400M: open dataset of clip-filtered 400 million image-text pairs', Data Centric Al NearIPS Workshop.
Shvetsova, N., Chen, B., Rouditchenko, A., Thomas, S., Kingsbury, B., Foris, R. S., Harwath, D., Glass,
J. and Kuehne, H. (2022), Everything once-multi-modal fusion transformer for video retrieval, in 'IEEE/ FIEE//VF Conference Computer Vision and Pattern Recognition', pp.
Simbadri, H. V., Aumüller, M., Baranchuk, D., Douze, M., Liberty, E., Ingber, A., Liu, F. and Williams, G. (2024), 'NeurIPS 2023 BigANN challenge practical vector search', attps://big ann ann- benchmarks. com/ neurips23.5 html.
Srinivasan, S., Zhao, L., Ganesh, B., Jacob, B., Espig, M. and Iyer, R. (2009), CMP memory modeling: How much does accuracy matter?, in 'Workshop on Modeling, Benchmarking and Simulation'.
Wai, H.-T., Lafond, J., Scaglione, A. and Moulines, E. (2017), 'Decentralized Frank-Wolfe algorithm for convex and nonconvex problems', IEFF Transactions on Aulomatic Control 62(11), 5522 -5337
Wang, J., Zhang, T., Song, J., Sebe, N. and Shen, H. T. (2018), 'A survey learning to hash', IEEE Transactions on Pattern Analysis and Machine Intelligence 40(4), 769-790.
Wang, M., Xu, X., Yue, Q. and Wang, Y. (2021), 'A comprehensive survey and experimental com- parison of graph-based approximate nearest neighbor scarch', Proceedings of the VLDB Endoument 14(11), 1964 1978.
Wang, R. and Deng. D. (2020), 'DeltaPQ: Lossless product quantization code compression for high dimen- sional similarity search', Proceedings of the VLDB Endowment 13(13), 3603 3616.
Wei, B., Guan, T. and Yu, J. (2014), 'Projected residual vector quantization for ANN search', IEEE Multi- Media 21(3), 41 51.
Yu, J., Wang, Z., Vasudevan, V., Yeung, L., Seyedhosseini, M. and Wu, Y. (2022), 'CoCa: Contrastive captioners are imago-text foundation models', preprint arXiv:2205.0190
Zhang, H., Tang, B., Hu, W. and Wang. X. (2022), Connecting compression spaces with transformer for approximate nearest neighbor search, in 'European Conference on Computer Vision', pp. 515-530.
Zhang, T., Du, C. and Wang, (2014), Composite quantization for approximate nearest neighbor search, in 'International Conference Machine Learning', pp. 838 846.
16


Reviews:
[{"review_id": "r8gT83y6bH", "reviewer": "Reviewer_zLyP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n1. **Effective framework**: The combination of linear dimensionality reduction and vector quantization is a novel approach that effectively addresses the challenges of high-dimensional vector similarity searches.\n\n2. **Interesting Idea for OOD Queries**: For the hard OOD queries, the authors introduce a novel asymmetric query-aware dimensionality reduction idea to use different orthonormal matrices for dimension reduction. They also provide the details on optimizing the objective function and the convergence analysis. \n\n3. **Extensive Experimental Results**: This submission includes a comprehensive set of experiments, showcasing the efficacy of LeanVec across various scenarios and datasets.\n\n4. **Clear Presentation**: The paper is well-structured and clearly written, making the complex concepts and methodologies accessible to the reader. This clarity enhances the overall impact and comprehensibility of the research.\n\n**Weaknesses**:\n1. **Limited Discussion on Scalability**: While the paper shows improvements in search performance, it lacks a detailed discussion on the scalability of the approach for very large datasets, particularly for the index build time.\n\n2. **Potential Overfitting for Specific Query Distribution**: For the OOD queries, as LeanVec-OOD requires a representative query set as input, there may be concerns about overfitting to specific types of query distributions (and datasets).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission introduces LeanVec, a framework designed to accelerate similarity search for high-dimensional vectors, particularly those generated by deep learning models. LeanVec combines linear dimensionality reduction with vector quantization and graph search to maintain accuracy while improving the search (and index construction) efficiency.\nIt offers two variants: LeanVec-ID for in-distribution queries and LeanVec-OOD for out-of-distribution queries. For OOD queries, the authors introduce a query-aware dimensionality reduction technique that considers both the query and database distributions to enhance accuracy and performance.\nExtensive experiments demonstrate that LeanVec can significantly improve search throughput and index build time while maintaining accuracy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please remedy the issues raised in the weaknesses.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sGDqrYTQQP", "reviewer": "Reviewer_N8m6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Generally, I like the contribution of the paper. Key points are:\n\nS1. Simple, convincing idea\n\nS2. Efficient algorithm to learn linear projections\n\nS3. Convergence analysis of that algorithm\n\nS3. Extensive experimental study with good results\n\nI do have some concerns, however. Some of these concerns (W2,W3) can be addressed by expanding the experimental study appropriately.\n\nW1. Key technical contribution of this paper is for out-of-distribution queries.\n\nW2. Simpler baselines not explored\n\nW3. Unclear how much tuning and query data is required\n\nW4. No deeper analysis\n\nW5. Performance on recent NeurIPS competition unclear\n\nIn more details:\n\nOn W1. The key ideas for in-distribution queries (perform PCA, retrieve-and-rerank) are not new and used in prior methods as well; the paper essentially applies them in front of a recent MIPS method (Aguerrebere et al., 2023). For out-of-distribution queries, this is different because different projections are learned for queries and examples. That's where the contribution of the paper lies. (The writing sometimes does not make this clear.)\n\nOn W2. For out-of-distribution queries, baseline alternative to Alg. 1 are: (1) use the PCA of the queries only or (2) use the PCA of queries and examples concatenated. Although these techniques should be inferior to the proposed method in theory, I feel that they should be included in the study.\n\nOn W3. (1) The experimental study essentially tuned the dimensionality of the proposed method so that best performance is achieved. This involves learning projections, building indexes, and determining the candidate threshold. The tuning cost is unclear. (2) The study does not consider the amount of available out-of-distribution data (but fixed to 10k), which play an important role. How much data is needed really and how much benefits does it bring? (I consider the remark behind Prop. 1 not valid, as it's assuming that the number of available queries is large.)\n\nOn W4. The papers neither empirically nor theoretically analyzes how much information is lost by the proposed approach and how it interplays with the subsequent quantization. Essentially, it's a try-and-see-if-it-works method.\n\nOn W5. The recent NeurIPS competition on similarity search (https://big-ann-benchmarks.com/neurips23.html) also included out-of-distribution tasks. This dataset is a natural candidate to be included in the experimental study, fostering comparability to prior work. (The best-performing methods for this task are although worth including, but those have been published in parallel to this work so that wouldn't be a fair request).\n\nMinor remarks:\n\nD1. The matrices in the Stiefel manifold are not orthogonal, but row-orthogonal.\n\nD2. Why not just write spectral norm?\n\nD3. Why is the contraint needed in (8)? Is it to obtain convexity (of (9) later on)?\n\nD4. The solution of (11) does not seem to be \"closed-form\", as it requires the computation of the SVD of the gradient matrices.\n\nD5. The metrics 10-recall@K should be defined.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Proposes an approach for maximum inner product search (MIPS), one for in-distribution queries and one for out-of-distribution queries. The key idea is to (1) perform linear dimensionality reduction of queries/examples, (2) use prior MIPS methods to retrieve candidates, (3) re-rank the candidates. For in-distribution queries, PCA is used. For out-of-distribution queries, a different projection for queries and examples is learned; here the paper proposes an efficient algorithm and analyzes its convergence. An experimental on multiple datasets indicates that the approach outperforms its baseline methods and state-of-the-art methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "W2, W3, W5, clarify W1 (tone down langauge at parts). Optional: W4, which would be great.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6IopkTASQg", "reviewer": "Reviewer_xCWw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Summary of Strengths:\n* Empirical advantages - Figure 3, 4 demonstrate strong empirical gains for search and similarly for Vamana graph construction Figure 5, 12. Results include some datasets newly introduced by this paper.\n* Depth of empirical analysis - Figures 9,10 demonstrate depth in empirical study, for instance comparing OOD compression schemes\n\nSummary of Weaknesses:\n* Presentation of method - My main concern about the presentation of the paper is that I think LeanVec's differences from other quantization techniques could be much more clearly presented. For instance, I would have expected more discussion, more focus, and more assistance fto the reader about all the ways modern \"mainstream state-of-the-art vector quantization techniques are incompatible with the random[-like access] pattern\". As a reader who is not deeply familiar with the results of Aguerrebere et al. (2023), I would have appreciated much more discussion of this. \n* Similarly, I would have expected more discussion about when & why the proposed approach is better than other quantization / dimensionality reduction alternatives. E.g., why should we expect improvements with the method over other choices of quantization. \n* I think the presentation would be greatly improved by a comparison between the proposed approach & alternatives delineating design choices in terms of objective optimized, algorithm for optimizing the objective, and memory access patterns. I understand that some of this burden should be on the reader, but I think readers would find more detailed discussion and relationship to these so-called \"mainstream\" VQ methods (e.g., [OPQ](https://www.microsoft.com/en-us/research/wp-content/uploads/2013/11/pami13opq.pdf), [Anisotropic Vector Quantization](https://arxiv.org/pdf/1908.10396.pdf), [Pairwise quantization](https://arxiv.org/pdf/1606.01550.pdf), etc)\n* If I have misinterpreted the important points of emphasis or misunderstood, please let me know.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents, LeanVec, for efficient nearest neighbor search through linear dimensionality reduction + quantization. The authors present empirical analysis on in-domain/out-of-domain datasets of up to 13M points, which shows significant throughput / recall improvements upon past related work.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Changes:\n* Further discussion on the ways in which LeanVec improves the \"random-like access pattern\" issues of past work. \n* Further comparison (from methodological perspective, not empirical) of the approach to other quantization methods. Empirical comparison ok, but secondary on this point in my opinion.\n\nMinor:\n* \"However, there are no systematic studies of its effects when applied to deep learning embedding vectors in modern graph-based indices.\" Seems a bit strong to me. Perhaps say way previous studies that readers may think of as in this space are insufficient?\n* Other related work on graph/quantization relationships:\n  * https://openaccess.thecvf.com/content_cvpr_2018/papers/Douze_Link_and_Code_CVPR_2018_paper.pdf\n* \"related to metric learning Bellet et al. (2013).\" -> \"related to metric learning (Bellet et al., 2013).\"", "broader_impact_concerns": "Not required. If the authors wish to add discussion that is ok.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers recommended accepting the paper.  In their recommendations, they noted that the method is "highly relevant, simple, solid," "substantial improvements over (the huge number of) state-of-the-art methods," "the revisions made by the author greatly improve the paper and address my concerns," and that the paper is "a good fit to be published at TMLR".  The rebuttal did help clear up issues that the reviewers had, so at this point there are no serious issues that need to be addressed.  I'm happy to recommend acceptance.  Given the high quality of the paper, I am furthermore recommending a Featured Certification for the paper.
Decision: Accept (poster)