PaperlayerView exact revision on arXiv

Source-linked AI summary

Similarity search in the blink of an eye with compressed indices

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

arXiv:2304.04759v2cs.LGcs.IR

TL;DR

At billion-vector scale, exact similarity search is impractical, and graph indices face random-access memory challenges. The paper introduces LVQ and an optimized graph-search system to reduce memory pressure and speed search. Together, they establish a reported state of the art in performance and memory footprint.

  • Problem

    At billion-vector scale, exact nearest-neighbor retrieval is impractical, while graph search faces random-access memory-bandwidth constraints and lossy compression can compromise accuracy or require costly similarity computations.

    Source: §1 · pp. 1–2

  • Method

    LVQ centers and individually scales vectors before scalar quantization, and the authors combine it with an optimized graph-search implementation.

    Source: §1 · p. 2

  • Results

    LVQ reduces bandwidth by up to ~8x versus float32 with negligible accuracy degradation, and the combined approach establishes the state of the art in performance and memory footprint.

    Source: §1 · p. 2, §8 · p. 12

  • Takeaways & Limitations

    The authors show that accurate graphs can be built directly from LVQ-compressed vectors, reducing the memory pressure of index construction.

    Source: §1 · p. 2, §4 · p. 4

    The authors note that large variance differences across dimensions are not observed in the standard datasets or deep-learning embeddings they studied, though they report empirical robustness in an appendix.

    Source: §3 · p. 4

Abstract

from arXiv · show

Nowadays, data is represented by vectors. Retrieving those vectors, among millions and billions, that are similar to a given query is a ubiquitous problem, known as similarity search, of relevance for a wide range of applications. Graph-based indices are currently the best performing techniques for billion-scale similarity search. However, their random-access memory pattern presents challenges to realize their full potential. In this work, we present new techniques and systems for creating faster and smaller graph-based indices. To this end, we introduce a novel vector compression method, Locally-adaptive Vector Quantization (LVQ), that uses per-vector scaling and scalar quantization to improve search performance with fast similarity computations and a reduced effective bandwidth, while decreasing memory footprint and barely impacting accuracy. LVQ, when combined with a new high-performance computing system for graph-based similarity search, establishes the new state of the art in terms of performance and memory footprint. For billions of vectors, LVQ outcompetes the second-best alternatives: (1) in the low-memory regime, by up to 20.7x in throughput with up to a 3x memory footprint reduction, and (2) in the high-throughput regime by 5.8x with 1.4x less memory.

1 INTRODUCTION

At billion-vector scale, exact search is impractical and graph-based methods face memory-footprint and random-access bandwidth constraints. The paper pairs LVQ compression with an optimized graph-search system to improve throughput and memory use while preserving accuracy.

1 INTRODUCTION

  • At 0.9 10-recall@10 on deep-96-1B, LVQ-8 with R=32 beats Vamana, HNSWlib, FAISS-IVFPQfs, and ScaNN by 2.3x, 2.2x, 20.7x, and 43.6x throughput, using 3.0x, 3.3x, 1.7x, and 1.8x less memory, respectively.With R=126, the highest-throughput configuration outperforms the second-highest by 5.8x while using 1.4x less memory.Source: Figure 1 · p. 1
  • Graph search is limited by random vector accesses and memory bandwidth, while reducing graph work by visiting fewer points trades recall for throughput and barely reduces memory use.The paper also identifies compression trade-offs: some methods make similarity computations more expensive or require auxiliary uncompressed vectors, while others can distort distances enough to harm accuracy.Source: §1 · pp. 1–2
  • LVQ centers the data, scales each vector individually, and applies uniform scalar quantization to reduce bandwidth by up to ~8x versus float32 with negligible accuracy degradation.A second-level quantization remainder can support final reranking, and graphs can be built directly from LVQ-compressed vectors.Source: §1 · p. 2
  • The authors combine LVQ with a graph-search library that flattens memory layout, avoids indirections, uses a custom prefetcher, and accelerates similarity computations with AVX.For LVQ, the AVX implementation is reported as up to 2.12x faster than with float16-valued vectors.Source: §1 · p. 2
  • The paper introduces a 768-dimensional dataset generated with large language models and releases code to generate it from a standard corpus.The experiments use an instance containing 10 million vectors.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries define approximate nearest-neighbor search and its evaluation, then describe graph-based search and construction. They also illustrate how LVQ normalization uses quantization range more fully than global or per-dimension normalization.

2 PRELIMINARIES

  • Similarity search seeks the k vectors with maximum similarity to a query; approximate retrieval permits errors to avoid an exact full scan.Accuracy is measured by k-recall@k (using k=10 and 0.9 by default), while performance is measured in queries per second.Source: §2 · p. 2

2.1 Graph-based similarity search

  • Graph search uses modified greedy traversal to retrieve approximate nearest neighbors, with priority-queue capacity W trading accuracy against performance.The search repeatedly explores the closest unexplored candidate and updates the candidate set.Source: §2.1 · pp. 2–3
  • Graph construction searches for candidate neighbors, prunes the candidates to an out-degree bound R, updates outward adjacency, then adds and prunes backward edges.The approach follows Subramanya et al. and performs two dataset passes.Source: §2.1 · p. 3
  • For 95% of deep-96-1M vectors, global and per-dimension normalization use about 60% and 75% of the available range, while LVQ normalization uses the whole range more uniformly.The figure reports the mean across vectors ±2σ.Source: Figure 2 · p. 3

3 LOCALLY-ADAPTIVE VECTOR QUANTIZATION

LVQ centers vectors, sets quantization bounds per vector, and applies scalar quantization to use the available range efficiently. A two-level residual code supports re-ranking, while graph integration and simpler model updates address search and index-maintenance costs.

3 LOCALLY-ADAPTIVE VECTOR QUANTIZATION

  • Per-vector bounds let LVQ use scalar quantization’s available range efficiently; with 8-bit codes and no padding, compression ratios are 3.84 on deep-96-1B and 3.98 on DPR-768-10M.LVQ centers vectors before computing bounds, and individual bounds adapt the quantization range to each vector.Source: §3 · pp. 3–4

3.1 Two-level quantization

  • Two-level LVQ quantizes the first-level residual with B2 bits, enabling a final re-ranking step without additional constants for the residual code.The residual is modeled as uniformly distributed in [−Δ/2, Δ/2), and re-ranking recovers part of the accuracy lost at the first level.Source: §3.1 · p. 4, §3.2 · p. 4

3.2 Integrating LVQ into graph-based indices

  • For dynamic indices, LVQ adapts to distribution shifts by recomputing the dataset mean and re-encoding vectors in linear time without loading the full dataset into memory.The integration uses first-level LVQ for graph search and compressed residuals for final re-ranking.Source: §3.2 · p. 4

4 THEORETICAL RESULTS ON GRAPH CONSTRUCTION

LVQ-compressed vectors can reduce graph-construction memory while preserving search accuracy at low bit widths. The section explains why pruning remains compatible with LVQ and evaluates how compression affects candidate selection and ordering.

4 THEORETICAL RESULTS ON GRAPH CONSTRUCTION

  • LVQ-4 reduces graph-building memory requirements by up to 6.2x, while search accuracy remains almost unchanged with 4 or 8 bits.The memory comparison covers graph plus vectors; the search-performance comparison uses deep-96-100M.Source: §4 · p. 4, Table 1 · p. 5, Figure 4 · p. 5

4.1 Graph pruning with LVQ

  • For Euclidean similarity and α=1, LVQ and full-precision graph-pruning rules are equivalent when the error-dependent condition holds.The error depends on quantization error and vectors x, x*, and x′.Source: §4.1 · p. 5
  • Assuming uniformly distributed quantization error, the pruning error E is normally distributed and |E| follows a folded normal distribution.These theoretical results characterize the errors introduced during pruning with LVQ-compressed vectors.Source: §4.1 · p. 5
  • At 4 bits, LVQ can reduce the pruning precision without affecting the pruning rule; at 2 bits, overlapping error bars leave guarantees unavailable.The empirical analysis uses triplets sampled from deep-96-100M and agrees with the search-accuracy results in Figure 4.Source: §4.1 · p. 5

4.2 Candidates selection and sorting with LVQ

  • For deep-96-100M, candidate-list recall is 0.82 with LVQ-4 versus 0.6 with global quantization at 4 bits.LVQ recall is almost one at 8 and 16 bits; these candidate-list results align with Figure 4's throughput comparison.Source: §4.2 · p. 6
  • LVQ maintains high-quality candidate ordering at 4, 8, and 16 bits, while 4-bit global quantization affects sorting.The comparison uses Ranked Bias Overlap between candidate lists sorted by compressed-vector and full-precision similarity.Source: §4.2 · p. 6

5 IMPLEMENTATION CHALLENGES

The implementation targets graph search’s memory bottlenecks with memory-layout, prefetching, and vector-computation optimizations. Its evaluation reports high bandwidth use, scaling gains, and faster similarity computation under several configurations.

Efficient similarity calculations using LVQ with AVX

  • LVQ similarity kernels fuse decompression with distance computation, using AVX instructions, loop unrolling, and masked operations to accumulate partial results in registers.Compressed vectors are densely packed with scaling constants inline; the 4-bit LVQ-B1xB2 case also uses vectorized shifts and masking.Source: §5 · p. 6
  • Up to 32% speedup from static rather than dynamic dimensionality contributes to an implementation with ~2x faster computation.The dimensionality is fixed for each dataset, allowing the compiler to unroll similarity-kernel loops more extensively; Figure 8 compares mean similarity times by encoding and dimensionality.Source: §5 · p. 6, Figure 8 · p. 7

Advanced prefetching

  • Up to 2x performance gain over no-prefetch comes from the advanced prefetch scheme; prefetch-step=1 shows no gain over baseline.The tunable prefetch-offset and prefetch-step control lookahead and the number of vectors prefetched per iteration.Source: §5 · p. 7, Figure 7 · p. 7

Optimizing graph search

  • Disabling the visited set improves deep-96-100M throughput by 15–20% on Cascade Lake but only 2–3% on Ice Lake, with no difference on DPR-768-10M.For common small W values, a sorted linear queue buffer is faster than a heap-like structure; searches are parallelized across queries, while per-query parallelization remains future work.Source: §5 · p. 7

Memory layout and allocation

  • 20% in deep-96-100M and 90% in deep-96-1B are the performance gains from huge pages at 0.90 recall.The implementation uses contiguous block allocations and explicit huge-page allocators, while avoiding graph layouts with memory indirections.Source: §5 · pp. 7–8, Figure 7 · p. 7

System utilization

  • 160 GB/s for float16 and 135 GB/s for LVQ-8 use more than 90% and 78% of the 174 GB/s-per-socket peak read-only bandwidth, respectively.LVQ-8 scales to 80 threads and gains 33x over single-thread, while float16 saturates at 40 threads with a 23.5x gain.Source: Figure 7 · p. 7, §5 · p. 8

6 EXPERIMENTAL RESULTS

Across datasets from 10^6 to 10^9 vectors, the experiments evaluate OG-LVQ’s search performance, memory footprint, and compression against established alternatives. OG-LVQ combines graph-based search with LVQ and achieves strong throughput and memory results, while the best LVQ configuration depends on dataset dimensionality.

6.1 Datasets

  • The benchmark spans datasets with 10^6 to 10^9 vectors and dimensionalities from 25 to 768, including a new 10-million-vector, 768-dimensional DPR embedding dataset.The DPR dataset uses C4 text snippets for its context and question embeddings.Source: §6.1 · p. 8, Table 2 · p. 8

6.2 System setup

  • Experiments ran on two-socket Intel Xeon systems, but each experiment used a single socket to avoid remote NUMA memory-access regressions.Huge pages were enabled natively where available; small-scale ANN-benchmarks runs did not allocate them to keep conditions equal.Source: §6.2 · p. 8, §6.3 · p. 9

6.4 Performance on large scale search

  • For 10-recall@10 of 0.9, OG-LVQ delivers 6.5x higher throughput on deep-96-1B and 2.0x and 1.8x on t2i-200-100M and DPR-768-10M, respectively.On the inner-product datasets, its advantage is present below recall 0.97 and 0.95, respectively; at very high recall its performance is on par with alternatives.Source: §6.4 · p. 9, Figure 10 · p. 10

6.5 LVQ: Fast graph search with small footprint

  • For deep-96-1B at R=32, OG-LVQ achieves 20.7x the throughput with 1.7x less memory than FAISS-IVFPQfs.Against Vamana, the same setting reaches 2.3x throughput with 3x less memory.Source: §6.5 · p. 9

6.3 Performance on small scale search

  • At 0.90 10-recall@10, OG-LVQ wins 8 of 10 small-scale cases; in full-batch mode, it beats its closest competitor by 1.15x to 5.49x.In single-query mode, it wins 3 of 5 cases, with NGT-qg taking the other two.Source: §6.3 · p. 9, Table 3 · p. 10

6.6 LVQ versus PQ for exhaustive search

  • LVQ achieves higher accuracy than PQ and OPQ below 6x compression on deep-96-1M, while providing faster similarity calculations.At higher compression ratios, re-ranking with full-precision vectors is needed for reasonable accuracy, undermining compression’s purpose.Source: §6.6 · p. 10, Figure 11 · p. 11

6.7 An ablation study comparing quantizers

  • LVQ’s maximum recall exceeds 0.98 versus 0.96 for global quantization on deep-96-100M; one-level LVQ leads at smaller dimensions and two-level LVQ at larger dimensions.For deep-96-100M, LVQ-4x4 performs slightly worse than LVQ-8; LVQ-4x8 reaches higher accuracy with a larger footprint on deep-96-1B.Source: §6.7 · p. 11
  • In Figure 12, LVQ-8 outperforms PQ at every recall value, delivering 5.2x more QPS at 0.9 recall while maintaining similar compression ratios (4x for PQ versus 3.84 for LVQ-8).Source: §6.7 · p. 11

7 RELATED WORK

Related work spans similarity-search algorithms, compression techniques, and optimizations for particular index designs. The paper positions LVQ in relation to graph search’s random-access workload and notes dimensionality reduction as a complementary technique.

Algorithms for similarity search

  • Graph-based methods offer a better latency-accuracy trade-off than trees, hashing, and learning-to-hash, which face dimensionality or accuracy-speed challenges.The literature continues to respond to increasing dataset sizes, dimensionalities, speed requirements, and recall demands.Source: §7 · p. 12

Compression for similarity search

  • PQ and related quantizers address limited-memory settings but do not enable extremely fast similarity computations for high-throughput graph search’s random accesses.PQ’s lookup-table and gather operations can slow as dimensionality rises, and its transposed layout and Quicker ADC are incompatible with graph search’s random-access pattern.Source: §7 · p. 12

Quantization approaches

  • Scalar quantization methods for neural-network inference quantize SIMD-sized vectors and compress quantization parameters, but had not been used for similarity search.The cited two-level approaches use SSD-resident graphs or PQ at both levels; joint PQ optimization is described as prohibitive at billion scale.Source: §7 · p. 12

Complementary compression

  • Dimensionality reduction is presented as orthogonal to LVQ, so the two techniques can be combined for stacked gains.Source: §7 · p. 12

8 CONCLUSIONS

The paper concludes that LVQ and optimizations for graph-based indices produce faster, smaller similarity-search indices. For billion-scale datasets, the reported gains extend across both low-memory and high-throughput regimes.

Conclusions

  • LVQ reduces memory footprint and improves search performance with minimal impact on accuracy, while reducing effective bandwidth and supporting fast random-access similarity computations.Source: §8 · p. 12
  • For billion-scale datasets, the approach achieves up to 20.7x throughput with up to 3x less memory in the low-memory regime, and 5.8x throughput with 1.4x less memory in the high-throughput regime.Source: §8 · p. 12

Future work

  • Future work will study LVQ for dynamic similarity search, dimensionality reduction as preprocessing, and intra-query parallelism.Source: §8 · p. 12

A LOCALLY-ADAPTIVE VECTOR QUANTIZATION

The passage compares empirical vector-value distributions for two datasets and describes their suitability for quantization after de-meaning.

Vector-value distributions

  • The gist-960-1M and glove-25-1.2M vector-value distributions are almost identical across individual dimensions.Source: Figure 14 · p. 15
  • The distributions mainly differ in their mean, with a slight difference in variance.Source: Figure 14 · p. 15
  • After de-meaning, the values are highly amenable to quantization because their dynamic range lacks regions of very high or very small density.Source: Figure 14 · p. 15

A.1 Experimental results with large variance differences

OG-LVQ remains competitive on datasets with large dimension-wise variance differences. The appendix also examines LVQ quantization error and its aggregate behavior.

A.1 Experimental results with large variance differences

  • The pathological tests scale 20% of dimensions by factors of 10–100; deep-image-96-angular uses Euclidean distance after scaling breaks unit normalization.Standard datasets generally have similar dimension distributions after mean removal, while pathological differences may affect reconstruction accuracy.Source: §A.1 · p. 15
  • OG-LVQ outperforms or matches other methods across datasets and query modes with dimension variances differing by orders of magnitude.The evaluation includes modified standard datasets and a generated Gaussian dataset with 20% of dimensions assigned much larger standard deviations.Source: §A.1 · p. 15, Figure 15 · p. 16

B INDEXING WITH COMPRESSED VECTORS

  • The empirical LVQ quantization-error distribution is approximated by a uniform distribution, except for zero-error endpoint values that are perfectly reconstructable.The derivation treats error terms as sample means of d independent identically distributed random variables, yielding a Gaussian aggregate by the central limit theorem.Source: Figure 16 · p. 17, B INDEXING WITH COMPRESSED VECTORS · p. 17

C DPR DATASET GENERATION DETAILS

The DPR-768-10M dataset is generated from C4 text embeddings, with training documents used as base vectors and validation documents as queries.

C DPR DATASET GENERATION DETAILS

D ADDITIONAL EXPERIMENTAL RESULTS

The additional results report strong throughput and memory results for LVQ configurations, alongside performance across datasets and recall regimes. On DPR-768-10M, ScaNN leads at higher recall.

D ADDITIONAL EXPERIMENTAL RESULTS

D.1 Fast search and a small footprint with LVQ

  • Figure 17 reports that OG-LVQ establishes a new state of the art across the small-scale datasets and query modes.Source: Figure 17 · p. 20
  • 4.7x: LVQ-8 with R=128 outperforms the second-highest-throughput configuration with 1.3x less memory on deep-96-100M.For LVQ-8 with R=32, OG-LVQ has higher throughput across recall up to 0.97; at higher recall, LVQ-4x8 is on par with the competition with a 2.5x smaller footprint.Source: Figure 21 · p. 22

Related papers

Loading 2304.04759v2…