PaperlayerView exact revision on arXiv

Source-linked AI summary

Locally-Adaptive Quantization for Streaming Vector Search

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

arXiv:2402.02044v1cs.LGcs.IR

TL;DR

Streaming similarity search matters as databases evolve, but LVQ’s usefulness in that setting had not been established. The paper evaluates LVQ and introduces Turbo LVQ and Multi-Means LVQ; SVS-LVQ outperforms its closest competitor in both IID and distribution-shift settings.

  • Problem

    LVQ offers strong static-search performance, but its usefulness for streaming similarity search—where databases change and data distributions may shift—had not been established.

    Source: §1 · p. 1, §2.3.1 · p. 3

  • Method

    The paper evaluates LVQ for streaming search and introduces Turbo LVQ’s SIMD-oriented layout and Multi-Means LVQ’s local means.

    Source: §1 · p. 1

  • Results

    Up to 9.4x in the IID case and 8.8x under data distribution shifts, SVS-LVQ outperforms its closest competitor.

    Source: §1 · p. 2

  • Takeaways & Limitations

    LVQ achieves state-of-the-art search and index-modification performance across different dataset characteristics, and the contributions are open-sourced as part of SVS.

    Source: §6 · p. 12

    The study leaves other distribution-shift patterns and online updates of multiple LVQ means under extreme shifts for future work.

    Source: §6 · p. 12

Abstract

from arXiv · show

Retrieving the most similar vector embeddings to a given query among a massive collection of vectors has long been a key component of countless real-world applications. The recently introduced Retrieval-Augmented Generation is one of the most prominent examples. For many of these applications, the database evolves over time by inserting new data and removing outdated data. In these cases, the retrieval problem is known as streaming similarity search. While Locally-Adaptive Vector Quantization (LVQ), a highly efficient vector compression method, yields state-of-the-art search performance for non-evolving databases, its usefulness in the streaming setting has not been yet established. In this work, we study LVQ in streaming similarity search. In support of our evaluation, we introduce two improvements of LVQ: Turbo LVQ and multi-means LVQ that boost its search performance by up to 28% and 27%, respectively. Our studies show that LVQ and its new variants enable blazing fast vector search, outperforming its closest competitor by up to 9.4x for identically distributed data and by up to 8.8x under the challenging scenario of data distribution shifts (i.e., where the statistical distribution of the data changes over time). We release our contributions as part of Scalable Vector Search, an open-source library for high-performance similarity search.

1 INTRODUCTION

The introduction frames streaming similarity search as an important but under-studied problem because databases change over time and maintaining fast, accurate data-driven indices remains difficult. It evaluates LVQ in this setting and presents two variants alongside strong reported benchmark results.

1 INTRODUCTION

  • Similarity search retrieves vectors most like a query and supports applications including recommender systems, ad matching, and Retrieval-Augmented Generation.The introduction notes that deep learning has expanded semantic search applications.Source: §1 · p. 1
  • Streaming indices must support changing databases, but updating data-driven index structures while preserving fast, accurate search remains an open problem.Streams may be IID or undergo distribution shifts over time.Source: §1 · p. 1
  • LVQ accelerates vector similarity computations and reduces memory use, but changing global data statistics in a stream could affect its representations and search quality.The evaluation examines small initial samples and distribution shifts, relating compression errors to search accuracy.Source: §1 · p. 1
  • Turbo LVQ streamlines SIMD use through a modified vector memory layout, while Multi-Means LVQ replaces LVQ’s global mean with local means and reduces compression error.The reduction in compression error may improve search accuracy.Source: §1 · p. 1
  • Up to 9.4x in the IID case and 8.8x under data distribution shifts: SVS-LVQ outperforms its closest competitor and is reported robust across both settings.Turbo LVQ improves search performance by 28%, while Multi-Means LVQ achieves dataset-dependent speedups of up to 27%.Source: §1 · pp. 1–2

2 BACKGROUND AND PROBLEM STATEMENT

Streaming similarity search maintains an approximate-nearest-neighbor index as vectors are added or removed, sometimes under changing data distributions. The section introduces graph-based search, LVQ compression, and the challenges a changing stream poses for LVQ’s global statistics.

2.1 Streaming similarity search

  • Streaming similarity search maintains a fast, accurate dynamic index as vectors are added or removed, seeking approximate top-k neighbors while trading some accuracy for performance.The text measures accuracy with k-recall@k and search performance in queries per second.Source: §2.1 · p. 2
  • Natural distribution shifts can arise when a fixed embedding model receives diverse inputs; this work excludes shifts caused by changing the model.Open-images-512-13M illustrates class-dependent vector distributions, including proximity between fountain and building vectors.Source: §2.1 · p. 2, Figure 1 · p. 2

2.2 Graph-based streaming similarity search

  • Graph-based methods use proximity graphs and greedy traversal; increasing the search window allows more backtracking and improves accuracy at the cost of search time.The experiments use the FreshVamana dynamic index, with the authors stating that results apply to other graph-based methods.Source: §2.2 · p. 2

2.3 Locally-adaptive Vector Quantization

  • LVQ compresses vectors through per-vector scaling and scalar quantization; its first-level encodings support graph traversal, and optional residual encodings can support final reranking.The compressed vectors reduce effective memory bandwidth and footprint, while the text describes accuracy as hardly impacted.Source: §2.3 · pp. 2–3
  • LVQ uses a global sample mean to homogenize component distributions, and recovering accuracy through a larger search window or residual reranking can slow search.The LVQ model assumes component-wise distributions share the same span after mean subtraction.Source: §2.3.1 · p. 3, §2.3 · p. 3

2.3.1 The challenge of LVQ for streaming similarity search.

  • A small initial stream can yield an inaccurate mean, and distribution shifts can make it increasingly inaccurate, raising compression error when component-wise distributions diverge.Updating the mean over time could require re-encoding the entire dataset, which may be prohibitive for large databases.Source: §2.3.1 · p. 3

3 A DEEP DIVE ON LVQ

The section analyzes LVQ implementation and quantization-error regimes, presenting Turbo LVQ's SIMD-oriented layout and M-LVQ's localized means before examining search-window behavior and streaming robustness.

3.1 Turbo LVQ

  • Turbo LVQ permutes dimensions for SIMD decoding, reducing unpacking from seven assembly instructions to two for each group of sixteen dimensions.The illustrated layout groups 128 dimensions, encoded at 4 bits each, into 64 bytes.Source: §3.1 · p. 3, Figure 2 · p. 4

3.2 Multi-Means LVQ

  • M-LVQ replaces LVQ's global mean with assigned local centers, and stream additions require re-encoding only vectors assigned to the updated center.The method can reduce quantization error, but adds ⌈log2 M⌉ bits per vector, which may fit within LVQ's existing 32-byte padding.Source: §3.2 · p. 4

3.3 On the impact of LVQ in search performance

  • B1 chiefly determines required search windows: B2 matters little at B1 ≥ 7, while low B1 makes reranking critical and can prevent target recall.With B1=8 and B2=2, LVQ matches the float32 search window using 10 bits; some low-bit settings require more than 1500x the window or cannot reach target recall.Source: §3.3 · p. 5, Figure 3 · p. 5

3.3.1 M-LVQ versus LVQ.

  • 15%, 24%, and 26%: M-LVQ-4x8 reduces required search windows versus LVQ-4x8 at M=10, 100, and 256 on open-images-512-1M.At M=100, it approximates half an extra bit per dimension, an 11% reduction against a hypothetical 288 bytes; reductions vary across datasets, reaching 0% for rqa-768-1M-ID and 16% for laion-img-512-1M.Source: §3.3.1 · p. 5, Figure 4 · p. 6, Figure 5 · p. 6

3.3.2 LVQ for IID streaming data.

  • Using only 1% of vectors to estimate the mean caused no change in the search window needed for 0.9 10-recall@10 in IID streaming.The study compared mean estimates from random samples of 1%, 5%, 10%, and 100% of the database.Source: §3.3.2 · p. 6

4 EXPERIMENTAL EVALUATION

The evaluation tests LVQ-based streaming search across IID and distribution-shift streams, then examines recall stability and two LVQ variants. SVS-LVQ maintains strong search performance over time, while Turbo LVQ and Multi-Means LVQ offer gains in particular settings.

4.1 Datasets and experimental protocols.

  • The evaluation spans 10^6–10^8 vectors, multiple dimensions and modalities, and both IID streams and streams with distribution shifts.The shift protocol introduces classes sequentially; steady-state additions and deletions keep the database size constant.Source: §4.1 · p. 7

4.3.1 LVQ robustness under data distribution shifts.

  • LVQ retains its search advantage under distribution shifts, matching the impractical re-encoding baseline and outperforming full-precision SVS over time.The re-encoding baseline updates the mean and re-encodes the full database after each update round.Source: §4.3.1 · p. 8, Figure 8 · p. 10

4.3.2 Comparison to other methods.

  • Under distribution shifts, SVS-LVQ outperforms its closest competitor in search performance by up to 8.8x at small scale and 4.8x at large scale, respectively.SVS-LVQ leads in additions and delete consolidations, except on open-images-512-1M and open-images-512-13M, where FreshVamana is 30% faster for additions.Source: §4.3.2 · p. 8

4.4 Recall stability

  • With a fixed search window, recall stays stable over time in most IID datasets and all evaluated distribution-shift datasets.For openimages-512-13M, recall degrades slightly before stabilizing after 60 iterations.Source: §4.4 · p. 8

4.5 Ablation study: Turbo LVQ

  • 28% and 26% are Turbo LVQ-4x8’s maximum static-index search gains over LVQ-4x8 for small and large datasets, respectively.For dynamic indices, Turbo LVQ-4x8’s gain reaches 34%; its implementation reduces unpacking instructions.Source: §4.5 · pp. 8–9, Figure 7 · p. 9

4.6 Ablation study: Multi-Means LVQ

  • 17% and 8% are M-LVQ’s reported static-index gains on open-images-512 at 13M and 1M scale, respectively.These results use M=10, 100, or 256 with B1=4 and B2=8; the 13M gain is reported at 0.9 10-recall@10.Source: §4.6 · pp. 9–10

4.2.2 Comparison to other methods.; 4.3.2 Comparison to other methods.

  • 9.4x in IID streams and 8.8x under distribution shifts are the maximum advantages of SVS-LVQ over its closest competitor.The advantage holds across small and large datasets and over time; LVQ accounts for much of the gain over SVS-float32.Source: §4.2.2 · pp. 7–8, §4.3.2 · p. 8, Table 2 · p. 10

4.6 Ablation study: Multi-Means LVQ

  • Under the streaming protocol (B1=4, B2=8, M=100), M-LVQ shows open-images-512 performance boosts of 8% at 1M and 25% at 13M; other datasets show no improvement.M-LVQ-ideal shows a 9% performance improvement on open-images-512-13M; its extreme computational cost makes it practically unfeasible, and online M-LVQ encoding is future work.Source: §4.6 · p. 10

5 RELATED WORK

Related work covers streaming similarity-search methods and online vector compression. It positions this study around graph-based search and LVQ’s robustness to distribution shifts.

LVQ variants

  • Turbo LVQ improves search speed over original LVQ, while M-LVQ’s benefit depends on dataset and scale and can diminish as the number of means grows.The cited comparisons report Turbo gains up to 28% and 34% in static and streaming settings; M-LVQ gains range up to 27% static and 25% streaming on the described Open Images comparisons.Source: Figure 10 · p. 11, Figure 11 · p. 11, Figure 12 · p. 11

Graph-based methods

  • Graph-based methods support online updates and are state-of-the-art for static and dynamic indexing, while LSH methods struggle to achieve high accuracy and performance simultaneously.FreshVamana supports additions and deletions while maintaining stable accuracy over long update streams.Source: §5 · pp. 10, 12

Vector compression

  • Online hashing and online quantization update their parameters as data arrives, but the cited quantization works do not address bookkeeping for re-encoding database vectors.Some approaches provide theoretical error bounds; reported accuracy gains over fixed parameters are not large [42].Source: §5 · p. 12
  • LVQ’s robustness to distribution shifts parallels reported mild effects of PQ degradation on search accuracy, while LVQ’s computational efficiency gives it an advantage for graph-based search.The passage argues that PQ’s accuracy gap largely disappears after full-precision reranking.Source: §5 · p. 12

6 CONCLUSIONS

The paper reports strong LVQ search and index-modification performance in streaming similarity search, including gains over the closest competitor for IID data and distribution shifts. It identifies more extreme shifts and possible online updates to multiple means as future work.

6 CONCLUSIONS

  • Up to 9.4x for IID data and 8.8x under distribution shifts: SVS with LVQ and its contributions outperforms its closest competitor.The comparison covers both identically distributed data and data distribution shifts.Source: §6 · p. 12
  • Up to 27% dataset-dependent search-performance boosts come from Multi-Means LVQ, while Turbo LVQ gives consistent speedups of up to 28% over traditional LVQ.The paper also analyzes when lower compression error translates into better search accuracy.Source: §6 · p. 12
  • Future work includes studying other distribution shifts and online updates to multiple LVQ means if extreme shifts make them necessary.The proposed shift scenarios include temporal patterns in additions and deletions and more extreme embedding dynamic ranges.Source: §6 · p. 12

Supplementary material Locally-adaptive Quantization for Streaming Similarity Search

The supplementary material describes graph-based streaming search using a dynamic proximity graph, with search accuracy traded against time and updates maintaining the graph as data changes.

A GRAPH-BASED STREAMING SIMILARITY SEARCH

  • FreshVamana supports additions and deletions while maintaining search performance and accuracy over time; the paper uses it for its stable streaming performance and says results apply to other graph-based methods.FreshVamana is a variation of Vamana introduced by Singh et al. [36].Source: A GRAPH-BASED STREAMING SIMILARITY… · p. 14

A.1 Graph search

  • Increasing the graph-search window W explores more of the graph and improves neighbor accuracy, but increases search time.Graph search uses a modified best-first traversal to retrieve approximate nearest neighbors.Source: §A.1 · p. 14

A.2 Graph construction

  • Initial graph construction retrieves and prunes neighbors, then adds backward edges; insertions reuse the update routine, while deletions reconnect affected neighbors and prune when needed.The initial build runs twice with different pruning-relaxation settings.Source: §A.2 · p. 14
  • Deletions are lazy: deleted vectors remain available during traversal but are filtered from results, then removed in batches after enough deletions accumulate.This approach avoids excessive compute overhead from immediate deletion.Source: §A.2 · p. 14

B TURBO LVQ

Turbo LVQ permutes the encoded-vector layout to streamline SIMD unpacking. The resulting workflow reduces the assembly instructions needed to unpack dimensions compared with sequential LVQ.

B TURBO LVQ

  • 28% search-performance boost over the original LVQ [2]: Turbo LVQ permutes vector layout to streamline SIMD decompression.The original sequential layout is called Sequential LVQ.Source: B TURBO LVQ · p. 14, §B.1 · p. 15

B.1 Solution details

  • For 4-bit codes, Turbo LVQ packs 128 dimensions into 64 bytes and extracts groups of 16 using lane-wise masks and right shifts.The next 128-dimension block is loaded when all groups from the current block have been unpacked.Source: §B.1 · p. 15
  • Unpacking 16 dimensions takes 2 assembly instructions with Turbo LVQ, versus 7 with Sequential LVQ.Turbo LVQ uses a load and mask for the first group, then shift-plus-mask operations for following groups.Source: §B.1 · p. 16, Figure 16 · p. 16
  • Incomplete 128-dimension blocks are zero-padded and use masked SIMD for the final group; the permutation depends on lane width and bits per code.The illustrated lane configuration can change for other code widths or SIMD capabilities.Source: §B.1 · p. 16

C ON THE IMPACT OF LVQ IN SEARCH PERFORMANCE

The section describes an experimental procedure relating LVQ reconstruction error to recall across search-window sizes. It uses first-level quantization for graph search and two-level vectors to rerank candidates.

C ON THE IMPACT OF LVQ IN SEARCH PERFORMANCE

  • To relate reconstruction error to recall, the procedure varies LVQ bit levels and search-window sizes, runs graph search with first-level vectors, then reranks candidates using two-level vectors.The achieved recall is computed after reranking.Source: C ON THE IMPACT OF LVQ IN SEARCH… · p. 16
  • Continuous B1 and B2 values provide sub-bit granularity, with float32 versions of first-level and two-level vectors used for SVS search.The two-level encoding is Q2L(x) = Q(x) + Qres(x).Source: C ON THE IMPACT OF LVQ IN SEARCH… · p. 16

D EXPERIMENTAL SETUP

D.1 Datasets

The evaluation covers vector datasets spanning multiple scales, dimensions, and deep-learning model types. Dataset-specific learning and query sets support parameter tuning and recall evaluation.

D.1 Datasets

  • Datasets range from 1M to 100M vectors and span 96, 512, and 768 dimensions, with embeddings generated by multimodal, text-only, and image-only models.The collection includes laion-img-512-1M, rqa-768-1M-ID and rqa-768-10M-ID, and deep-96-1M and deep-96-100M.Source: §D.1 · p. 17
  • The newly introduced open-images-512-13M dataset provides a natural distribution-shift scenario for benchmarking.The authors state that its diverse deep-learning models provide empirical support for their contributions.Source: §D.1 · p. 17
  • For rqa-768-10M-ID, open-images-512-13M, and Deep1B, the first 5,000 learning vectors tune parameters and provided query sets measure final recall.For laion-img-512-1M, the first 10,000 embeddings form the query set and the following 5,000 form the learning set.Source: §D.1 · p. 17

D.1.1 New dataset: open-images-512-13M.

The authors introduce open-images-512-13M, a CLIP-image-crop dataset intended to recreate natural distribution shifts, with query and learning sets for evaluation.

D.1.1 New dataset: open-images-512-13M.

  • The 13M-vector dataset uses 512-dimensional CLIP embeddings of image crops from the dense-annotations subset of Google Open Images.Bounding boxes from 1.9M images yield more than 13M crops labeled across 434 object classes.Source: §D.1.1 · p. 17
  • The dataset is split into 13M base vectors and query and learning sets of 10,000 vectors each.open-images-512-1M is the first million elements of the base vectors.Source: §D.1.1 · p. 17
  • The query and learning sets use 100 ground-truth nearest neighbors computed by maximum inner product; normalized embeddings also permit Euclidean distance.Source: §D.1.1 · p. 18
  • The code for generating open-images-512-13M is available in the VectorSearchDatasets repository.Source: §D.1.1 · p. 18

D.2 Methods

The appendix describes the comparison methods, parameter choices, tuning procedure, and system setup used in the evaluation. Tuning is performed once, while huge pages and static dimensionality are enabled for the stated methods.

D.2 Methods

  • SVS-LVQ is compared with FreshVamana [36] and HNSWlib; FAISS streaming methods do not reach 0.9 10-recall@10 without reranking, whose latest cited version does not support deletions.The cited streaming inverted-index method from Baranchuck et al. [5] had no publicly available code as of February 6, 2024.Source: §D.2 · p. 18

D.3 Parameters setting

  • Graph-building settings use R=64 for 1M datasets and R=128 above 10M, with search windows of 200 for SVS-LVQ and FreshVamana and 500 for HNSWlib.LVQ-compressed vectors are padded to half cache lines (p=32).Source: §D.3 · p. 18

D.4 Parameter tuning

  • SVS-LVQ’s search-buffer and prefetching parameters are tuned by grid search using learning-set vectors as queries, with final recall-versus-QPS results measured on query sets.Source: §D.4 · p. 18
  • Tuning occurs once—at the first iteration for IID data or after ramp-up under distribution shift—and parameters then remain fixed.Source: §D.4 · p. 18
  • Exact tuning ground truth requires a full-precision linear scan, but approximate graph-search ground truth costs less than 10% of delete consolidations on large datasets and about twice that time on smaller ones.Approximation uses a search window of 1000; the reported costs apply where tuning makes an important difference for large datasets and are described as a minor one-time cost for smaller ones.Source: §D.4 · p. 18

D.5 System Setup

  • SVS-LVQ uses huge pages natively, while other methods are run with huge-page system flags; static dimensionality is enabled for SVS datasets.Huge pages can hurt FreshVamana and HNSWlib performance in some cases.Source: §D.5 · p. 18

E COMPLEMENTARY EXPERIMENTAL RESULTS

Complementary experiments examine distribution shifts, sampling the LVQ mean, multi-means LVQ, streaming behavior, and huge pages. Their outcomes vary by method, dataset, and recall regime.

E COMPLEMENTARY EXPERIMENTAL RESULTS

  • Huge pages boost SVS-LVQ throughput, while FreshVamana and HNSWlib generally do not benefit and show degraded performance on deep-96-1M.Source: Figure 17 · p. 19, Figure 18 · p. 20, Figure 19 · p. 21
  • Computing the LVQ mean from as few as 1% of vectors preserves peak performance and leaves the search-window size for each target recall unchanged.The comparison covers three datasets and different recall values.Source: Figure 20 · p. 21
  • HNSWlib performs no delete consolidations and loses recall over time, whereas SVS maintains stable recall; FreshVamana shows sawtooth recall declines between consolidations on laion-img-512-1M.Source: Figure 21 · p. 22
  • A speedup of 1 over SVS-LVQ-ideal indicates no search-performance degradation under distribution shifts, while SVS-LVQ significantly speeds search over SVS-float32.SVS-LVQ-ideal impractically re-encodes the entire database at each time using LVQ with the sample mean from X_t.Source: Figure 22 · p. 23
  • With static indexing, M-LVQ does not help rqa-768-1M-ID, benefits deep-96-1M above 0.94 recall, and slightly benefits laion-img-512-1M at M=10.Source: Figure 23 · p. 23
  • During streaming, M-LVQ with M=100 shows neither speedup nor degradation over LVQ on rqa-768-1M-ID and rqa-768-10M-ID.Source: Figure 24 · p. 23

Related papers

Loading 2402.02044v1…