# Similarity search in the blink of an eye with compressed indices

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 63 references that are in the map.
- First posted on arXiv 7 Apr 2023.

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

- [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)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [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)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Everything at Once -- Multi-modal Fusion Transformer for Video Retrieval](https://mlsanity.com/paper/2112.04446/) (2021)
- [VS-Quant: Per-vector Scaled Quantization for Accurate Low-Precision Neural Network Inference](https://mlsanity.com/paper/2102.04503/) (2021)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [A Survey on Locality Sensitive Hashing Algorithms and their Applications](https://mlsanity.com/paper/2102.08942/) (2021)
- [Semi-Parametric Neural Image Synthesis](https://mlsanity.com/paper/2204.11824/) (2022)
- [Optimal Clipping and Magnitude-aware Differentiation for Improved Quantization-aware Training](https://mlsanity.com/paper/2206.06501/) (2022)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD](https://mlsanity.com/paper/1812.09162/) (2018)
- [Scalable Semantic Matching of Queries to Ads in Sponsored Search Advertising](https://mlsanity.com/paper/1607.01869/) (2016)
- [Low-Precision Quantization for Efficient Nearest Neighbor Search](https://mlsanity.com/paper/2110.08919/) (2021)
- [Connecting Compression Spaces with Transformer for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.14415/) (2021)
- [Speed-ANN: Low-Latency and High-Accuracy Nearest Neighbor Search via Intra-Query Parallelism](https://mlsanity.com/paper/2201.13007/) (2022)

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

- [Arctic-Embed 2.0: Multilingual Retrieval Without Compromise](https://mlsanity.com/paper/2412.04506/) (2024)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [LeanVec: Searching vectors faster by making them fit](https://mlsanity.com/paper/2312.16335/) (2023)
- [RaanA: A Fast, Flexible, and Data-Efficient Post-Training Quantization Algorithm](https://mlsanity.com/paper/2504.03717/) (2025)
- [Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search](https://mlsanity.com/paper/2508.01405/) (2025)
- [Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs"](https://mlsanity.com/paper/2412.01940/) (2024)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [Advancing Multi-Agent RAG Systems with Minimalist Reinforcement Learning](https://mlsanity.com/paper/2505.17086/) (2025)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [An Entity Linking Agent for Question Answering](https://mlsanity.com/paper/2508.03865/) (2025)
- [ParisKV: Fast and Drift-Robust KV-Cache Retrieval for Long-Context LLMs](https://mlsanity.com/paper/2602.07721/) (2026)
- [Bang for the Buck: Vector Search on Cloud CPUs](https://mlsanity.com/paper/2505.07621/) (2025)
- [GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reduction](https://mlsanity.com/paper/2410.22347/) (2024)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)
- [Individualized non-uniform quantization for vector search](https://mlsanity.com/paper/2509.18471/) (2025)
- [Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach](https://mlsanity.com/paper/2603.06660/) (2026)
- [FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2603.21710/) (2026)
- [MERIT: Efficient In-Place Deletion for Dynamic Graph-Based Approximate Nearest Neighbor Indexes](https://mlsanity.com/paper/2607.29173/) (2026)
- [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026)
- [RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2608.30384/) (2026)

## Abstract (arXiv)

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.