# Locally-Adaptive Quantization for Streaming Vector Search

arXiv: https://arxiv.org/abs/2402.02044 · HTML: https://mlsanity.com/paper/2402.02044/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 3 Feb 2024.

## Builds on (most cited first, 21 of 21)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Open Images Dataset V4: Unified image classification, object detection, and visual relationship detection at scale](https://mlsanity.com/paper/1811.00982/) (2018)
- [Measuring Robustness to Natural Distribution Shifts in Image Classification](https://mlsanity.com/paper/2007.00644/) (2020)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (2016)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [The Effect of Natural Distribution Shift on Question Answering Models](https://mlsanity.com/paper/2004.14444/) (2020)
- [Retrieval-Augmented Generation for Code Summarization via Hybrid GNN](https://mlsanity.com/paper/2006.05405/) (2020)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [Online Product Quantization](https://mlsanity.com/paper/1711.10775/) (2017)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [MIHash: Online Hashing with Mutual Information](https://mlsanity.com/paper/1703.08919/) (2017)
- [LeanVec: Searching vectors faster by making them fit](https://mlsanity.com/paper/2312.16335/) (2023)
- [Online Hashing](https://mlsanity.com/paper/1704.01897/) (2017)
- [K-means for Evolving Data Streams](https://mlsanity.com/paper/2012.03628/) (2020)

## Built on by (most cited first, 11 of 11)

- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion](https://mlsanity.com/paper/2406.19651/) (2024)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [Bang for the Buck: Vector Search on Cloud CPUs](https://mlsanity.com/paper/2505.07621/) (2025)
- [How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?](https://mlsanity.com/paper/2512.06200/) (2025)
- [GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reduction](https://mlsanity.com/paper/2410.22347/) (2024)
- [Individualized non-uniform quantization for vector search](https://mlsanity.com/paper/2509.18471/) (2025)
- [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026)

## Abstract (arXiv)

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.