mlsanityData to 7 Oct 2026

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

arXiv 1603.09320 ↗First posted 30 Mar 2016cs.DS cs.CV cs.IRcited by 853

Not on the map. Why?

Cited by 158 in Retrieval-augmented generation, but placed by its own abstract, which didn’t fit.

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.

Key facts. Cited by 853 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Mar 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 56; 2022: 77; 2023: 93; 2024: 146; 2025: 219; 2026: 261.

853 papers.

Sort:

By area:

  1. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  2. 2024The Faiss librarycited by 370
  3. 2024Retrieval-Augmented Generation for AI-Generated Content: A Surveycited by 352
  4. 2022Matryoshka Representation Learningcited by 268
  5. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  6. 2021PAQ: 65 Million Probably-Asked Questions and What You Can Do With Themcited by 198
  7. 2023Almanac: Retrieval-Augmented Language Models for Clinical Medicinecited by 122
  8. 2022RetroMAE: Pre-Training Retrieval-oriented Language Models Via Masked Auto-Encodercited by 118
  9. 2024RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrievalcited by 114
  10. 2022Retrieval Augmented Classification for Long-Tail Visual Recognitioncited by 106
  11. 2022Re2G: Retrieve, Rerank, Generatecited by 102
  12. 2024RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generationcited by 97
38 more
  1. 2022PLAID: An Efficient Engine for Late Interaction Retrievalcited by 95
  2. 2024PQCache: Product Quantization-based KVCache for Long Context LLM Inferencecited by 93
  3. 2024From Matching to Generation: A Survey on Generative Information Retrievalcited by 89
  4. 2022Deep Visual Geo-localization Benchmarkcited by 83
  5. 2024A Survey on Retrieval-Augmented Text Generation for Large Language Modelscited by 77
  6. 2024Retrieval-Augmented Generation for Natural Language Processing: A Surveycited by 70
  7. 2021Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classificationcited by 66
  8. 2023Shall We Pretrain Autoregressive Language Models with Retrieval? A Comprehensive Studycited by 63
  9. 2021Neural Machine Translation with Monolingual Translation Memorycited by 61
  10. 2023Learning Customized Visual Models with Retrieval-Augmented Knowledgecited by 58
  11. 2021Personalized Federated Learning through Local Memorizationcited by 57
  12. 2022PinnerFormer: Sequence Modeling for User Representation at Pinterestcited by 57
  13. 2023A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challengecited by 55
  14. 2021Efficient Passage Retrieval with Hashing for Open-domain Question Answeringcited by 53
  15. 2023InstructRetro: Instruction Tuning post Retrieval-Augmented Pretrainingcited by 53
  16. 2025OpenSearch-SQL: Enhancing Text-to-SQL with Dynamic Few-shot and Consistency Alignmentcited by 51
  17. 2022Tevatron: An Efficient and Flexible Toolkit for Dense Retrievalcited by 47
  18. 2023On the De-duplication of LAION-2Bcited by 47
  19. 2024Financial Report Chunking for Effective Retrieval Augmented Generationcited by 46
  20. 2022Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Searchcited by 45
  21. 2025In-depth Analysis of Graph-based RAG in a Unified Frameworkcited by 45
  22. 2024Training-Free Open-Vocabulary Segmentation with Offline Diffusion-Augmented Prototype Generationcited by 43
  23. 2024When Large Language Models Meet Vector Databases: A Surveycited by 39
  24. 2024M-RAG: Reinforcing Large Language Model Performance through Retrieval-Augmented Generation with Multiple Partitionscited by 38
  25. 2021DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documentscited by 37
  26. 2022Nonparametric Uncertainty Quantification for Single Deterministic Neural Networkcited by 36
  27. 2022An Efficient Memory-Augmented Transformer for Knowledge-Intensive NLP Taskscited by 36
  28. 2021SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Searchcited by 35
  29. 2024MemLLM: Finetuning LLMs to Use An Explicit Read-Write Memorycited by 35
  30. 2025A Survey on Knowledge-Oriented Retrieval-Augmented Generationcited by 34
  31. 2022NGAME: Negative Mining-aware Mini-batching for Extreme Classificationcited by 32
  32. 2024Beyond Text: Optimizing RAG with Multimodal Inputs for Industrial Applicationscited by 31
  33. 2024A Semantic Search Engine for Mathlib4cited by 30
  34. 2025A Systematic Review of Key Retrieval-Augmented Generation (RAG) Systems: Progress, Gaps, and Future Directionscited by 30
  35. 2023Online Continual Learning Without the Storage Constraintcited by 29
  36. 2021Extreme Multi-label Learning for Semantic Matching in Product Searchcited by 28
  37. 2023Rethinking the Role of Token Retrieval in Multi-Vector Retrievalcited by 28
  38. 2024PipeRAG: Fast Retrieval-Augmented Generation via Algorithm-System Co-designcited by 28

50 most cited of 853 All 853 (JSON)