# Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

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

## Key facts

- Cited by 861 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2016.

## Built on by (most cited first, 30 of 861)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Retrieval-Augmented Generation for AI-Generated Content: A Survey](https://mlsanity.com/paper/2402.19473/) (2024)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [PAQ: 65 Million Probably-Asked Questions and What You Can Do With Them](https://mlsanity.com/paper/2102.07033/) (2021)
- [Almanac: Retrieval-Augmented Language Models for Clinical Medicine](https://mlsanity.com/paper/2303.01229/) (2023)
- [RetroMAE: Pre-Training Retrieval-oriented Language Models Via Masked Auto-Encoder](https://mlsanity.com/paper/2205.12035/) (2022)
- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [Retrieval Augmented Classification for Long-Tail Visual Recognition](https://mlsanity.com/paper/2202.11233/) (2022)
- [Re2G: Retrieve, Rerank, Generate](https://mlsanity.com/paper/2207.06300/) (2022)
- [PLAID: An Efficient Engine for Late Interaction Retrieval](https://mlsanity.com/paper/2205.09707/) (2022)
- [RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generation](https://mlsanity.com/paper/2404.12457/) (2024)
- [PQCache: Product Quantization-based KVCache for Long Context LLM Inference](https://mlsanity.com/paper/2407.12820/) (2024)
- [From Matching to Generation: A Survey on Generative Information Retrieval](https://mlsanity.com/paper/2404.14851/) (2024)
- [Deep Visual Geo-localization Benchmark](https://mlsanity.com/paper/2204.03444/) (2022)
- [A Survey on Retrieval-Augmented Text Generation for Large Language Models](https://mlsanity.com/paper/2404.10981/) (2024)
- [Retrieval-Augmented Generation for Natural Language Processing: A Survey](https://mlsanity.com/paper/2407.13193/) (2024)
- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [Shall We Pretrain Autoregressive Language Models with Retrieval? A Comprehensive Study](https://mlsanity.com/paper/2304.06762/) (2023)
- [Neural Machine Translation with Monolingual Translation Memory](https://mlsanity.com/paper/2105.11269/) (2021)
- [Learning Customized Visual Models with Retrieval-Augmented Knowledge](https://mlsanity.com/paper/2301.07094/) (2023)
- [Personalized Federated Learning through Local Memorization](https://mlsanity.com/paper/2111.09360/) (2021)
- [PinnerFormer: Sequence Modeling for User Representation at Pinterest](https://mlsanity.com/paper/2205.04507/) (2022)
- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [Efficient Passage Retrieval with Hashing for Open-domain Question Answering](https://mlsanity.com/paper/2106.00882/) (2021)
- [InstructRetro: Instruction Tuning post Retrieval-Augmented Pretraining](https://mlsanity.com/paper/2310.07713/) (2023)
- [OpenSearch-SQL: Enhancing Text-to-SQL with Dynamic Few-shot and Consistency Alignment](https://mlsanity.com/paper/2502.14913/) (2025)
- [Tevatron: An Efficient and Flexible Toolkit for Dense Retrieval](https://mlsanity.com/paper/2203.05765/) (2022)
- [On the De-duplication of LAION-2B](https://mlsanity.com/paper/2303.12733/) (2023)

## Abstract (arXiv)

We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed solution is fully graph-based, without any need for additional search structures, which are typically used at the coarse search stage of the most proximity graph techniques. Hierarchical NSW incrementally builds a multi-layer structure consisting from hierarchical set of proximity graphs (layers) for nested subsets of the stored elements. The maximum layer in which an element is present is selected randomly with an exponentially decaying probability distribution. This allows producing graphs similar to the previously studied Navigable Small World (NSW) structures while additionally having the links separated by their characteristic distance scales. Starting search from the upper layer together with utilizing the scale separation boosts the performance compared to NSW and allows a logarithmic complexity scaling. Additional employment of a heuristic for selecting proximity graph neighbors significantly increases performance at high recall and in case of highly clustered data. Performance evaluation has demonstrated that the proposed general metric space search index is able to strongly outperform previous opensource state-of-the-art vector-only approaches. Similarity of the algorithm to the skip list structure allows straightforward balanced distributed implementation.