PaperlayerView exact revision on arXiv

Source-linked AI summary

GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reduction

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

arXiv:2410.22347v1cs.IRcs.LG

TL;DR

High-dimensional vector search faces memory and compute pressure, and compression is challenging when query and database distributions differ. The paper introduces linear LeanVec-Sphering and nonlinear GleanVec for dimensionality reduction. It reports improved linear-method performance and further accuracy gains from GleanVec with little performance impact.

  • Problem

    High-dimensional vectors degrade index performance, while differing query and database distributions make compression harder in applications such as cross-modal search.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces LeanVec-Sphering and piecewise-linear GleanVec to reduce dimensionality and memory-bandwidth use while supporting ID and OOD queries.

    Source: §1 · p. 2, §7 · p. 15

  • Results

    LeanVec-Sphering outperforms other linear methods, while GleanVec further improves search accuracy over linear methods with little performance impact.

    Source: §1 · p. 2, §7 · p. 15

  • Takeaways & Limitations

    LeanVec-Sphering offers flexible target dimensionality and no hyperparameters, and its training requires only two singular value decompositions.

    Source: §1 · p. 2

    Modern neural-network architectures are computationally prohibitive in this setting because query preprocessing takes milliseconds while baseline search latency is measured in microseconds.

    Source: §2.2 · p. 5

Abstract

from arXiv · show

Embedding models can generate high-dimensional vectors whose similarity reflects semantic affinities. Thus, accurately and timely 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. In particular, cross-modal retrieval (e.g., where a text query is used to find images) is gaining momentum rapidly. Here, it is challenging to achieve high accuracy as the queries often have different statistical distributions than the database vectors. Moreover, the high vector dimensionality puts these search systems under compute and memory pressure, leading to subpar performance. In this work, we present new linear and nonlinear methods for dimensionality reduction to accelerate high-dimensional vector search while maintaining accuracy in settings with in-distribution (ID) and out-of-distribution (OOD) queries. The linear LeanVec-Sphering outperforms other linear methods, trains faster, comes with no hyperparameters, and allows to set the target dimensionality more flexibly. The nonlinear Generalized LeanVec (GleanVec) uses a piecewise linear scheme to further improve the search accuracy while remaining computationally nimble. Initial experimental results show that LeanVec-Sphering and GleanVec push the state of the art for vector search.

1 Introduction

High-dimensional vectors strain search indices through memory latency, while query and database distributions can differ in applications such as cross-modal retrieval. The paper introduces LeanVec-Sphering and GleanVec to reduce memory-bandwidth use while preserving accuracy for ID and OOD queries.

Motivation

  • Modern graph indices perform well at moderate dimensions but degrade at the higher dimensions common in deep-learning embeddings, and their construction also slows as dimensionality rises.The stated concern is especially relevant because vector-search deployments overwhelmingly use deep-learning vectors.Source: §1 · p. 1
  • Random-like database-vector access makes graph search memory-latency-bound, and parallel queries increase memory latency enough to hurt performance.Even carefully placed prefetch instructions cannot hide the increased latency.Source: §1 · p. 1
  • Vector compression is difficult when query and database distributions differ, as in cross-modal text-to-image and cross-model question-answering searches.Existing compression approaches either do not fit random-access patterns or provide insufficient compression.Source: §1 · p. 2

Contributions

  • LeanVec addresses random-access compression and ID/OOD search, but its linearity limits dimensionality reduction before accuracy suffers.The paper responds with two methods: linear LeanVec-Sphering and nonlinear GleanVec.Source: §1 · p. 2
  • LeanVec-Sphering outperforms existing ID and OOD linear reduction methods, has no hyperparameters, and permits target dimensionality to be set during search.Its training requires only two singular value decompositions.Source: §1 · p. 2
  • GleanVec's piecewise linear structure improves search accuracy over linear methods while barely affecting performance.It uses LeanVec-Sphering to perform similarity computations efficiently during graph search.Source: §1 · p. 2

2 Problem statement

The paper formulates high-dimensional maximum-inner-product search as preserving query–database inner products after dimensionality reduction. It describes a search-and-rerank pipeline and frames the reduction as query-aware, then reviews linear and neural-network approaches while noting the computational cost of deep networks.

2 Problem statement

  • Reducing dimensionality lowers memory fetches and computation, with inner-product computation accelerated by a factor of D/d at the cost of approximation error.The method seeks functions f and g that map vectors from dimension D to d while preserving inner products.Source: §2 · p. 3
  • The proposed multi-step search reduces query and database dimensionality, retrieves κ candidates in the reduced space, then reranks them using original-space inner products.The reduction must make this pipeline faster than baseline search while retaining equal accuracy.Source: §2 · p. 3
  • Query-aware reduction targets preservation of query–database inner products because query and database distributions can differ in cross-modal and cross-model search.A query-agnostic projection or reconstruction-error objective can yield less accurate inner products.Source: §2 · p. 3, Figure 1 · p. 4

2.1 Preliminaries: The linear case

  • LeanVec is a linear method whose projection matrices A and B reduce vector entries, lowering memory footprint and the computation required in the main search.Applying A to the query takes approximately 1% of the main-search time.Source: §2.1 · p. 4
  • LeanVec learns projection matrices from database vectors and representative queries to preserve inner products, using an efficiently solvable optimization over row-orthonormal matrices.The stated solution options are block-coordinate descent or eigenvector search.Source: §2.1 · p. 4

2.2 Preliminaries: The nonlinear case

  • Neural networks can parameterize nonlinear reduction functions, but their millisecond query-preprocessing time is prohibitive against baseline search latency measured in microseconds.This computational mismatch rules out modern neural-network architectures in the described setting.Source: §2.2 · pp. 4–5

3 A closed-form solution for the linear case

LeanVec-Sphering gives a closed-form, query-aware linear reduction that uses query-derived sphering and an SVD, while supporting flexible target dimensions. It extends this approach to runtime dimension selection and streaming updates.

3 A closed-form solution for the linear case

  • The solution restricts A and B to transformations built from P and query-derived W, reducing the optimization to an SVD of WX.The resulting projection minimizes dimensionality under a Mahalanobis distance that uses query statistics rather than the classical database-derived whitening matrix.Source: §3 · p. 5
  • Applying W−1 flattens the query distribution’s spectrum, and LeanVec-Sphering requires no hyperparameters beyond target dimensionality d.The method can also apply scalar quantization to the reduced database vectors.Source: §3 · p. 5
  • As sample size grows, the SVD computations converge at a square-root rate, so using subsamples or small holdout sets has little effect on the result.The passage describes this as a small effect on the end result, not as an exact equivalence.Source: §3 · p. 6
  • LeanVec-Sphering achieves better minima of the training loss and prevails over LeanVec on validation maximum inner product search.The comparisons cover all training-set inner products and the more practically relevant validation query–database setting.Source: §3 · p. 6

3.1 Flexibly selecting the target dimensionality

  • Storing ordered projected coordinates lets LeanVec-Sphering select d at search time by using a prefix, rather than fixing d during index construction.The scheme can store D dimensions or αd dimensions for α > 1; it avoids storing a secondary database-vector set for postprocessing.Source: §3.1 · p. 6, Figure 2 · p. 7
  • The transformed inner product preserves undistorted similarities and can handle queries whose distribution differs from the data used to build the projection matrices.The paper gives image queries as a possible secondary query type in text-to-image retrieval.Source: §3.1 · p. 6
  • Storing all D dimensions can increase page misses, but preliminary experiments describe this performance penalty as second-order relative to usability gains.Runtime d selection trades accuracy against performance without changing the underlying index.Source: §3.1 · p. 6

3.2 Streaming vector search

  • For streaming updates, outer products update query and database summary statistics, whose eigendecompositions replace the batch SVDs; database vectors can be remapped periodically or on demand.The proposed update process avoids holding or rematerializing a full database copy when applying the updated transformation.Source: §3.2 · p. 7

4 GleanVec: Generalizing LeanVec with nonlinearities

GleanVec generalizes LeanVec through data partitioning followed by query-aware, locally linear dimensionality reduction. It replaces compute-heavy nonlinear reduction with selection among simple functions for inner-product approximation.

4 GleanVec: Generalizing LeanVec with nonlinearities

  • The design connects generalized PCA’s union-of-subspaces setting with k-means partitioning and piecewise-linear representations.The paper says Generalized LeanVec inherits its name from generalized PCA; k-means divides input space into Voronoi cells, while neural-network layers use Voronoi-like partitions with linear mappings.Source: §4 · pp. 7–8
  • GleanVec decouples nonlinear reduction into data partitioning and locally linear, query-aware dimensionality reduction, replacing compute-bound neural reduction with selection.The paper contrasts this with CCST [70], whose transformers it says preclude its use for search.Source: §4 · p. 8
  • For each database vector, GleanVec uses its cluster tag to select a simple function instead of computing a complex nonlinear query mapping.The tag lookup can be made efficient by storing the tag and low-dimensional vector contiguously in memory.Source: §4 · p. 8
  • GleanVec approximates inner products with linear functions fc and gc learned from data in a query-aware fashion.The method assumes a set of dimensionality-reducing functions and landmarks for its construction.Source: §4 · p. 8
  • GleanVec offers lazy query transformations during inner-product computation or eager precomputation of each cluster’s query view.Lazy execution may repeat transformations for vectors in the same cluster; eager execution may compute unused views and depends on cache retention.Source: §4 · p. 8

4 Procedure inner-product(xi, q)

The procedure assigns database vectors to clusters, and GleanVec learns cluster-specific linear projections. Its alternative perspective highlights how its cluster-center bottleneck differs from VQ-VAE and standard neural networks.

4 Procedure inner-product(xi, q)

  • The inner-product procedure first recovers the cluster assignment c_i for database vector x_i.Source: §4 · p. 9

4.1 Learning

  • Learning partitions Xlearn into clusters, learns linear query and database mappings for each, and applies LeanVec-Sphering to reduce dimensionality.Source: §4.1 · p. 9

4.2 An alternative perspective on GleanVec

  • GleanVec uses cluster centers for dimensionality reduction rather than VQ-VAE’s vector quantization; its query output directly depends on x_i, increasing locality and representational power.The learning procedure is stage-wise; end-to-end learning is left for future work.Source: §4.2 · pp. 9–10

5 Experimental results

Across the evaluated settings, GleanVec improves search accuracy over LeanVec-Sphering, while LeanVec-Sphering performs similarly to alternatives on ID data and better on OOD data. The experiments also examine cluster-wise projections and inner-product computation strategies.

5 Experimental results

  • Evaluation spans 1M–13M vectors and dimensions 200–960, measuring accuracy with K-recall@k (usually K=10) and search performance with QPS.Source: §5 · p. 10

5.1 Linear dimensionality reduction

  • On ID datasets, analyzed methods perform similarly in loss and search accuracy, even where LeanVec-FW has worse GIST-1M-ID loss.Source: Figure 4 · p. 11, §5.1 · p. 11
  • For OOD datasets, LeanVec-Sphering outperforms alternatives in LeanVec loss and brute-force search accuracy.Source: §5.1 · p. 11, Figure 5 · p. 12

5.2 Nonlinear dimensionality reduction

  • Partitioning vectors into spherical k-means clusters before projection captures more database-vector information than projecting the full set; most variance lies in the first ∼150 principal directions.Source: §5.2 · p. 12
  • Searches often visit fewer than all 48 clusters, and visited tags quickly stabilize at a small fraction, favoring eager inner products with trivially parallelizable preprocessing.Source: §5.2 · p. 12
  • Across tested target dimensions and retrieved-neighbor counts, GleanVec outperforms LeanVec-Sphering; its accuracy advantage is wider at lower target dimensionalities.Source: §5.2 · p. 12

6 Related work

Prior work spans dimensionality reduction, learned metrics, transformers, hashing, and product quantization, with limitations for OOD queries and graph-search compatibility. The section also reports cluster-level structure and locality in accessed cluster tags.

6 Related work

  • Dimensionality reduction has long supported approximate nearest-neighbor search, but OOD queries remain largely unexplored.The passage notes that ID-query settings have been covered extensively.Source: §6 · p. 12
  • Transformer-based dimensionality reduction can accelerate vector search, but its computational complexity precludes its use during search [70].The passage circumscribes its application to index construction.Source: §6 · pp. 12, 15
  • Cluster correlation matrices show checkerboard structure, and roughly 150 dimensions capture 80% of each cluster’s variance.Each cluster’s intrinsic dimensionality is lower than the full dataset’s.Source: §6 · p. 13
  • Across graph searches, the sliding-window count of accessed tags quickly settles at a small fraction of 48 clusters, and some searches never visit all clusters.The reported curves average 1,000 queries and show plus or minus one standard deviation.Source: §6 · p. 13
  • Hashing and learning-to-hash techniques often struggle to achieve high accuracy and high speed simultaneously [34].Source: §6 · p. 15
  • Product quantization and related methods use prototype-based look-up tables, but gather operations slow as dimensionality grows [30] [44].Quicker ADC optimizes lookups for contiguous, transposed storage, which is incompatible with graph search’s random memory access.Source: §6 · p. 15

7 Conclusions

The paper presents LeanVec-Sphering and GleanVec for dimensionality reduction in high-dimensional vector search with ID and OOD queries. It reports state-of-the-art results, while end-to-end library integration and performance assessment remain planned.

7 Conclusions

  • LeanVec-Sphering and GleanVec are reported to push the state of the art for vector search.Source: §7 · p. 15
  • LeanVec-Sphering outperforms other linear methods, trains faster, uses no hyperparameters, and permits more flexible target dimensionalities.Source: §7 · p. 15
  • GleanVec uses a piecewise linear scheme to further improve search accuracy while remaining computationally nimble.Source: §7 · p. 15
  • Integration into a state-of-the-art vector-search library and assessment of end-to-end performance benefits are planned for a manuscript revision.Source: §7 · p. 15

A Spherical k-means

The appendix describes spherical k-means for clustering normalized data, including its iterative optimization and initialization. In practice, it uses a uniform sample to compute cluster centers.

A Spherical k-means

  • Spherical k-means operates on normalized dataset vectors and finds cluster centers on the unit sphere.Source: A Spherical k-means · p. 19
  • The clustering objective is non-convex, and iterative EM-like optimizations can reach a local minimum.Source: A Spherical k-means · p. 19
  • The authors initialize centers with k-means++ on the normalized data, while noting Pyramid Vector Quantization as an alternative depending on the distribution.Source: A Spherical k-means · p. 19
  • For fewer than 100 clusters, centers are computed from a uniform random sample of 10^5 points; the authors report no catastrophic effects and note coresets as an alternative.Source: A Spherical k-means · p. 19

A.1 Adapting other similarities

For datasets with Euclidean ground truth, the appendix adapts vectors to the inner-product setting. Nearly normalized vectors need no substantial change, while unnormalized vectors use a transformation that adds one dimension.

A.1 Adapting other similarities

  • For nearly normalized vectors, minimizing Euclidean distance is almost equivalent to maximizing inner products.Source: §A.1 · p. 19
  • For unnormalized vectors, the authors apply a transformation so inner-product search remains compatible with Euclidean ground truth.Source: §A.1 · p. 19
  • The transformed query and database vectors have one additional dimension.Source: §A.1 · p. 19

B Datasets

The evaluation spans standard and application-specific ID datasets, cross-modal text-to-image retrieval, and OOD query settings. Table 2 describes the similarities and vector normalization used to compute ground truth.

B Datasets

  • The methods are evaluated across a range of ID and OOD datasets, with Table 1 presenting the evaluation suite.Source: B Datasets · p. 19
  • Table 2 lists the datasets alongside the similarities and vector normalization used for ground-truth computation; Euclidean distance is a dissimilarity.Source: Table 2 · p. 20
  • The ID suite includes GIST-1M and DEEP-1M, using the first 10K learn-set entries for test queries and the next 10K for validation.Source: B Datasets · p. 20
  • OI-1M and OI-13M are ID datasets derived from Google Open Images and encoded with OpenAI CLIP-ViT-B32.Source: B Datasets · p. 20
  • A further 1M-vector ID dataset uses RocketQA text embeddings, with query and database vectors drawn from a common pool of text answers.Source: B Datasets · p. 20
  • The evaluation includes three cross-modal text-to-image datasets—T2I-1M, T2I-10M, and LAION-1M—with text queries and image database embeddings.The passage says their queries are divided into learning and test sets.Source: B Datasets · p. 20
  • OOD evaluation includes WIT-1M, where text-description queries are encoded with CLIP-ViT-B32-multilingual-v1 and image database vectors with CLIP-ViT-B32.Source: B Datasets · p. 20
  • RQA-1M and RQA-10M test OOD question-answering queries against RocketQA-encoded text vectors; query and answer encoders differ, yielding the stated OOD setting.Source: B Datasets · p. 20

Related papers

Loading 2410.22347v1…