PaperlayerView exact revision on arXiv

Source-linked AI summary

LeanVec: Searching vectors faster by making them fit

Mariano Tepper, Ishwar Singh Bhati, Cecilia Aguerrebere, Mark Hildebrand, Ted Willke

arXiv:2312.16335v2cs.LGcs.DB

TL;DR

High-dimensional embeddings pressure similarity search systems, and cross-modal queries may differ in distribution from database vectors. LeanVec combines linear dimensionality reduction with vector quantization in ID and OOD variants; experiments report state-of-the-art search throughput and index-build time.

  • Problem

    High-dimensional embeddings create memory and compute pressure for similarity search, while cross-modal queries may follow a different distribution than database vectors.

    Source: §1 · p. 2

  • Method

    LeanVec combines linear dimensionality reduction with vector quantization and provides ID and OOD variants, with OOD projections using dataset vectors and queries.

    Source: §1 · p. 2, §2.2 · p. 5

  • Results

    Up to 3.7x improvement in search throughput and up to 4.9x faster index build time over the best alternatives are reported across varied experiments.

    Source: §5 · p. 13

  • Takeaways & Limitations

    LeanVec is reported to accelerate graph-based search and index construction while maintaining quality on high-dimensional vectors.

    Source: §1 · p. 3, §5 · p. 12

    In its current form, LeanVec keeps both primary and secondary vectors in memory, increasing the total footprint.

    Source: §2 · p. 4

Abstract

from arXiv · show

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

LeanVec targets the memory and compute pressure of high-dimensional vector search and the distribution mismatch in cross-modal queries. It combines dimensionality reduction with vector quantization in ID and OOD variants to accelerate search and index construction.

1 INTRODUCTION

  • 9.6x vector compression and an 8.5x performance gain over FP16 are reported for LeanVec at 72 threads on rqa-768-1M.The compression combines 4.8x dimensionality reduction with 2x LVQ8; memory bandwidth is 95 vs. 149GB/s.Source: Figure 1 · p. 2, §1 · p. 3
  • High-dimensional vectors increase memory latency and compute pressure in graph search, while cross-modal queries can come from a different distribution than database vectors.These conditions make search performance and compression accuracy more challenging.Source: §1 · p. 2
  • LeanVec combines linear dimensionality reduction with LVQ in a search-and-rerank framework, with variants for in-distribution and out-of-distribution queries.The main search uses compressed primary vectors; candidates are reranked using secondary vectors quantized with LVQ.Source: §1 · p. 2, Figure 1 · p. 2
  • Up to 8.6x runtime improvement is reported for building high-quality graph indices compared with using the original vectors.Source: §1 · p. 3
  • LeanVec-ID combines PCA with LVQ for up to 3.6x search speedups over prior work, without assumptions about query-vector distributions.Source: §1 · p. 3
  • LeanVec-OOD optimizes projection subspaces using dataset vectors and a representative query set to reduce similarity-computation errors.It includes two lightweight, fast optimization algorithms and is reported to match LeanVec-ID in ID settings while outperforming it in OOD settings.Source: §1 · p. 3

2 LeanVec: a framework to accelerate similarity search for high-dimensional vectors

LeanVec combines dimensionality reduction and vector quantization to speed high-dimensional similarity search through compressed vectors and search-and-rerank. It provides an in-distribution PCA-based approach and query-aware out-of-distribution methods, including two ways to optimize their projections.

2 LeanVec: a framework to accelerate similarity search for high-dimensional vectors

  • LeanVec uses projected, quantized primary vectors for graph traversal and secondary vectors to rerank candidates; dimensionality reduction targets speed, while current storage increases total footprint.Locally-adaptive Vector Quantization (LVQ) is used for efficient encoding and decoding; the query projection is computed once per search.Source: §2 · pp. 3–4

2.1 Dimensionality reduction for in-distribution similarity search

  • For in-distribution search, LeanVec uses PCA’s leading singular vectors to minimize database-vector representation error and approximates inner products in the reduced space.The residual can be represented losslessly using D − d dimensions.Source: §2.1 · p. 4

2.2 Query-aware dimensionality reduction for out-of-distribution similarity search

  • LeanVec-OOD learns separate projections from query and database statistics to minimize inner-product approximation error, and its objective is upper bounded by SVD in the in-distribution case.It requires a representative query set for training, which the authors note is also used to calibrate search settings.Source: §2.2 · p. 5

2.3 Optimizing the LeanVec-OOD loss with a Frank-Wolfe algorithm

  • Frank-Wolfe block-coordinate descent alternates updates to A and B over convexified constraints, making the relaxed OOD optimization amenable to efficient subproblems.For open-images-512-1M with D = 512 and d = 128, Algorithm 1 converges in 51 iterations and takes 4 seconds; relaxing orthogonality incurs 10−3 error.Source: §2.3 · pp. 6–7, Figure 2 · p. 6

2.4 Optimizing the LeanVec-OOD loss with eigenvector search

  • With A = B, eigenvector search tunes β to balance query and database statistics; Algorithm 2 finds a smooth loss minimum but lacks theoretical guarantees.Algorithm 1 initialized from its solution improves the loss by less than 2%, and both algorithms perform similarly in end-to-end search.Source: §2.4 · pp. 7–8

3 Experimental results

LeanVec improves graph-search performance on both in-distribution and out-of-distribution datasets, with the OOD variant providing the strongest gains for OOD queries. It also accelerates graph construction, while the best target dimensionality depends on the dataset and re-ranking helps recover recall.

Search performance

  • Up to 10.2x and 3.7x performance gains over FP16 and LVQ, respectively, at 10-recall@10 of 0.90, with LeanVec-ID and LeanVec-OOD performing similarly on ID datasets.On OOD datasets, LeanVec-OOD outperforms LeanVec-ID and LVQ by up to 1.5x and 2.8x, respectively, at 10-recall@10 of 0.90.Source: §3 · pp. 8–9, Figure 4 · p. 9, Figure 5 · p. 9
  • LeanVec's search advantage diminishes on lower-dimensional t2i-200-1M, and it shows no significant gains on laion-512-1M, where dimensionality reduction significantly impacts search accuracy.The authors plan to address the laion-512-1M issue in future work.Source: §3 · p. 9

Index construction

  • Up to 8.6x and 4.9x faster graph construction than FP16 and LVQ, respectively, without degrading search accuracy or speed.LeanVec construction timings include learning the projection matrices.Source: §3 · p. 9, Figure 6 · p. 10

Comparison with the state of the art

  • At 10-recall@10 of 0.90, SVS-LeanVec provides 1.1x, 1.9x, 2.8x, and 3.7x performance boosts over SVS-LVQ across t2i-200-1M, deep-256-1M, rqa-768-1M, and gist-960-1M, respectively.On the same datasets, its gains over FAISS-IVFPQfs are 2.4x, 3.8x, 7.8x, and 8.5x, respectively.Source: §3 · p. 9, Figure 7 · p. 10

LeanVec scaling on larger datasets

  • On larger datasets, LeanVec-OOD provides 2x and 2.4x performance benefits over LVQ on open-images-512-13M and rqa-768-10M, respectively, at 10-recall@10 of 0.90.On t2i-200-10M, SVS-LeanVec-OOD and SVS-LVQ perform similarly and outperform RoarANN by 2x at the same recall target.Source: §3 · pp. 9–10, Figure 8 · p. 11

Ablation study: The level of vector quantization

  • LVQ compression improves primary-vector performance over FP16; LVQ8 and FP16 perform similarly for secondary vectors except on t2i-200-1M, where FP16 does better.LVQ8 is recommended for secondary vectors when memory footprint matters, at minimal cost.Source: §3 · p. 10

Ablation study: The target dimensionality

  • The best target dimensionality varies by dataset; d = 256 is a reasonable compromise in most cases, with 2-3x bandwidth reduction.Too-low dimensionality can reduce accuracy and require retrieving more candidates for re-ranking, while higher dimensionality increases memory and computation costs.Source: §3 · p. 10, Figure 9 · p. 11

Ablation study: Re-ranking

  • Re-ranking 50 retrieved candidates using secondary vectors can raise recall at 10 to levels on par with recall at 50, while LeanVec-OOD has higher recall than LeanVec-ID on OOD datasets.The comparison uses exhaustive search; NN-MDS and CCST have exorbitant query transformation time that precludes their use for search.Source: §3 · pp. 10–11

4 Related Work

Prior dimensionality-reduction work addressed in-distribution search more than out-of-distribution search, while other approaches face accuracy-speed trade-offs or access-pattern constraints. LeanVec is positioned as a linear-reduction approach usable for search across ID and OOD settings.

Related work

  • Earlier linear dimensionality reduction work addressed ID queries, while the OOD case had been largely ignored.The cited examples are Deerwester et al. (1990), Ailon and Chazelle (2009), Jegou et al. (2010), Gong et al. (2012), Babenko and Lempitsky (2014b), and Wei et al. (2014).Source: §4 · p. 11
  • Hashing and learning-to-hash techniques often struggle to achieve high accuracy and high speed simultaneously.The passage cites Indyk and Motwani (1998), Jafari et al. (2021), Wang et al. (2018), and Luo et al. (2023).Source: §4 · p. 11
  • PQ-style lookup-table methods can become slower at higher dimensionality when the table no longer fits in L1 cache.Quicker ADC's contiguous transposed storage suits inverted indices but not graph search's random memory-access pattern.Source: §4 · pp. 11–12
  • CCST uses transformers for dimensionality reduction, but their computational complexity precludes search use; LeanVec outperforms CCST for index construction and can also be used for search.The passage relates OOD metric-learning concerns to the possibility that a metric learned on the main dataset may be unsuitable for OOD search.Source: §4 · p. 12
  • PCA-based retrieval-augmented language-model work maintains perplexity and boosts overall speed, but treats similarity search as a black box and does not address OOD aspects.The passage cites He et al. (2021) and Izacard et al. (2020).Source: §4 · p. 12

5 CONCLUSIONS

LeanVec combines linear dimensionality reduction with vector quantization to accelerate high-dimensional similarity search and index construction. Its ID and OOD variants yield state-of-the-art results, while the authors identify further work on dataset resistance to dimensionality reduction and OOD training speed.

5 CONCLUSIONS

  • LeanVec combines linear dimensionality reduction with vector quantization to accelerate high-dimensional similarity search and speed index construction.The paper presents variants for in-distribution and out-of-distribution queries; both lead to state-of-the-art results.Source: §5 · p. 12
  • Up to 3.7x improvement in search throughput and up to 4.9x faster index build time over the best alternatives are reported for LeanVec.The authors characterize the results as state of the art.Source: §5 · p. 13
  • The authors plan to investigate why laion-512-1M resists higher levels of linear dimensionality reduction and whether the behavior extends to other datasets.They also plan to optimize the LeanVec-OOD learning algorithm by implementing it in C++ using Intel OneMKL.Source: §5 · p. 13

A Speeding up graph construction with dimensionality reduction

LeanVec is applied to graph construction, where high-dimensional vector fetches and distance computations slow search and pruning. Reducing dimensionality alleviates memory pressure while remaining computationally lean, with acceleration scaling linearly with graph size.

A Speeding up graph construction with dimensionality reduction

  • Graph construction iteratively searches from each node for more than R approximate nearest neighbors, then prunes candidates to fewer than R outgoing edges.The pruning step computes distances between candidate vectors.Source: A Speeding up graph construction with… · p. 17
  • LeanVec accelerates graph construction by alleviating memory pressure while remaining computationally lean.The construction process involves search and pruning, and both are dominated by fetching high-dimensional vectors and computing distances.Source: A Speeding up graph construction with… · p. 17
  • Because construction runs at least once per node and scales linearly with nodes and edges, LeanVec acceleration has a linear impact on construction runtime.The number of edges is bounded above by nR.Source: A Speeding up graph construction with… · p. 17

B Proof of Proposition 1

The proof passage identifies the matrix constraints and states that the linear autoencoder solution is obtained by truncating singular vectors of X. It also re-normalizes each query.

B Proof of Proposition 1

C Convergence analysis of the Frank-Wolfe algorithm for LeanVec-OOD

The appendix analyzes convergence for the Frank-Wolfe BCD procedure used in LeanVec-OOD. It states a convergence result for approximate stationarity and identifies extension beyond two blocks as future work.

C Convergence analysis of the Frank-Wolfe algorithm for LeanVec-OOD

  • The authors note that convergence for inexact BCD has not been studied in the cited literature.They contrast this with prior convergence results for Frank-Wolfe algorithms on convex problems and stationary-point convergence for non-convex objectives.Source: C Convergence analysis of the… · p. 18
  • The analysis considers a non-convex continuously differentiable objective over a convex set and defines stationarity through a zero Frank-Wolfe gap.For the LeanVec-OOD setting, the objective is non-convex over the intersection of the constraints on A and B; the partial derivatives are Lipschitz and the curvature is finite.Source: C Convergence analysis of the… · p. 18
  • With step size γ(t) = 1/(t + 1)^α for α in (0,1) and T at least 6, Theorem 1 gives a convergence result for Algorithm 1.The result concerns finding an approximate stationary point with gap below ε.Source: C Convergence analysis of the… · p. 18
  • Extending Theorem 1 and its proof to settings with more than two blocks is left for future work.The authors relate their setting to Peng and Vidal (2023), who study exact subproblem minimization or cases with retractions.Source: C Convergence analysis of the… · p. 19

D Experimental setup.

The experiments use shared graph and hardware settings, compare LeanVec against established search methods, and tune target dimensionality for each dataset. Search is evaluated by throughput at a default accuracy target.

D Experimental setup.

  • The graph uses R = 128, L = 200, and α = 1.2 for L2 distance or α = 0.95 for inner product.Experiments run with 72 threads on one socket of a 2-socket Intel Xeon 8360Y system with 36 cores and 256GB DDR4 memory per socket.Source: D Experimental setup · p. 20, §D.4 · p. 21

D.1 Baseline approaches

  • LeanVec is compared with SVS-LVQ and HNSWlib, Vamana, and FAISS-IVFPQfs; OOD-DiskANN showed no performance benefit over Vamana on evaluated datasets with disjoint learning and test queries.RoarANN segfaulted while building indices for open-images-512-13M and rqa-768-10M.Source: §D.1 · p. 20

D.2 Finding the optimal target dimensionality d

  • For most modern-model-dimensional datasets, target dimensionality d in [160, 256] provides significant gains, and performance degrades gracefully away from the best-fit setting.The best d depends on the dataset; the experiments select it using the highest throughput at 90% accuracy, testing increments of 32 from 64.Source: §D.2 · p. 20

D.3 Metrics

  • Accuracy is measured by k-recall@k, with k = 10 by default, and search performance by queries per second (QPS).The default accuracy target is 0.9.Source: §D.3 · p. 21

D.4 System setup

  • Experiments use 72 threads on a single socket to avoid performance regressions from remote NUMA memory accesses.The system has two 3rd-generation Intel Xeon 8360Y sockets, each with 36 cores and 256GB DDR4 memory.Source: §D.4 · p. 21

E Datasets

The evaluation covers high-dimensional in-distribution datasets and cross-modal out-of-distribution text-to-image datasets, including collections with up to 13 million database vectors.

E Datasets

  • The evaluation spans in-distribution and out-of-distribution datasets, including standard high-dimensional ID collections and cross-modal text-to-image collections.The ID set includes gist-960-1M and deep-256-1M, with test and validation queries drawn from supplied learn sets.Source: E Datasets · p. 21
  • The Open Images ID datasets contain 1 million and 13 million CLIP image vectors, and use normalized vectors with Euclidean distance as the equivalent of cosine similarity.Provided queries form the test set, while the first 10K learn queries form validation.Source: E Datasets · p. 21
  • The OOD t2i-200-1M and laion-512-1M datasets each use one million image vectors and text embeddings as queries.Each dataset's queries are divided into test and learning sets.Source: E Datasets · p. 21

E.1 New text-to-image dataset with OOD queries

wit-512-1M adds an OOD text-to-image dataset built from Wikipedia image-text examples. The associated compression result shows substantially higher search performance than FP16.

E.1 New text-to-image dataset with OOD queries

  • wit-512-1M uses the first million WIT image-text examples, encoding images with CLIP and text descriptions with a multilingual CLIP model.The text descriptions combine the Reference and Attribution fields; each query's 100 ground-truth neighbors are computed by maximum inner product.Source: §E.1 · pp. 21–22
  • ~12x performance gain over FP16 at 72 threads accompanies LeanVec's 12x vector-size reduction for search.The reduction combines 6x dimensionality reduction and 2x LVQ8 compression; LVQ8 and LVQ4x8 alone compress by 2x and ~4x.Source: Figure 12 · p. 22

E.2 New question-answering dataset with ID and OOD queries

The paper introduces OOD question-answering datasets using distinct question and answer encoders, and reports supplementary analyses of LeanVec-OOD learning and search behavior.

E.2 New question-answering dataset with ID and OOD queries

  • The new OOD question-answering datasets rqa-512-1M and rqa-512-10M contain 1 million and 10 million vectors encoded with RocketQA.Questions and answers use different neural networks, and the experiments use the OOD variant.Source: §E.2 · p. 22
  • The OOD questions come from C4 validation snippets encoded with the question model, while database vectors come from C4 training snippets encoded with the answer model.The reported ground-truth neighbors are computed by maximum inner product.Source: §E.2 · p. 22
  • Figure 13 compares search throughput and accuracy for LeanVec-FW and LeanVec-ES.The caption identifies the variants as Algorithms 1 and 2, respectively.Source: Figure 13 · p. 23
  • Figure 14 reports no noticeable graph-performance differences with versus without dimensionality reduction across the tested LeanVec combinations.The figure compares search throughput and accuracy.Source: Figure 14 · p. 23
  • Figure 15 shows that relative errors in LeanVec-OOD learned parameters drop quickly as the random subsample size grows.The analysis estimates covariance matrices from subsamples and compares resulting parameters with those learned using the full sets.Source: Figure 15 · p. 23
  • Figure 16 shows that LeanVec-ES brute-force accuracy degrades at ns = D or 2D but the degradation vanishes at ns = 4D or more.Here ns is the number of query vectors used for learning.Source: Figure 16 · p. 24
  • Figure 17 describes a smooth loss over β with an empirical unique minimizer, which Algorithm 2 finds using derivative-free scalar minimization.β = 0 and β = 1 correspond to the query-vector and database-vector SVDs, respectively.Source: Figure 17 · p. 24
  • Figure 18 reports comparable brute-force search performance for LeanVec-ES and LeanVec-FW, while LeanVec-ES and its FW-initialized variant are almost indistinguishable.LeanVec-ES often has lower loss than LeanVec-FW.Source: Figure 18 · p. 25

Related papers

Loading 2312.16335v2…