Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 14 Pith papers
-
TheoremGraph: Bridging Formal and Informal Mathematics
TheoremGraph builds a unified statement-level dependency graph across informal arXiv math and formal Lean code via parsing, embeddings, and LLM validation, releasing the data and APIs for search and retrieval.
-
Query-aware Routing for Filtered Approximate Nearest Neighbors Search
A machine-learned router predicts per-query recall for filtered ANN methods and selects the recall-QPS optimal one, outperforming fixed baselines on five unseen datasets.
-
Mycelium-Index: A Streaming Approximate Nearest Neighbor Index with Myelial Edge Decay, Traffic-Driven Reinforcement, and Adaptive Living Hierarchy
Mycelium-index matches state-of-the-art recall on streaming and static ANN benchmarks while using 5x less RAM and delivering higher query throughput on SIFT-1M.
-
Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
RAG models set new state-of-the-art results on open-domain QA by retrieving Wikipedia passages and conditioning a generative model on them, while also producing more factual text than parametric baselines.
-
CodeTeam: An LLM-Powered Multi-Agent Framework for Repository-Level Code Generation
CodeTeam is an LLM multi-agent system that improves SketchBLEU by 4.1/2.9 points and achieves top test pass rates (34.6% PE, 42.3% SFT) on repository-level code generation benchmarks via role-specialized planning and ...
-
Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases
Soft-deleted HNSW embeddings are reconstructible from raw storage via Vec2Text inversion (up to 100% on structured data), addressed by epoch key rotation that reduces PII recovery to 0%.
-
TSseek: Regular Expression-Based Similarity Search for Distributed Time Series Datasets
TSseek approximates time series as line segments and regex queries as bounding rectangles, then uses a distributed spatial index (TSseek-X) to support efficient exact whole-matching and subsequence-matching queries.
-
When More Cores Hurts: The Vector Database Scaling Paradox in HPC
Large-scale HPC evaluation of Qdrant, Milvus, and Weaviate reveals that workload patterns limit scaling and extra cores can reduce throughput, exposing a cloud-to-HPC design mismatch.
-
Storage Is Not Memory: A Retrieval-Centered Architecture for Agent Recall
True Memory is a verbatim-event retrieval pipeline running on a single SQLite file that reaches 93% accuracy on LoCoMo multi-session questions, outperforming Mem0, Supermemory, Zep, and matching or exceeding EverMemOS...
-
PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors
PUFFINN is a parameterless probabilistic LSH index for k-NN search that combines heuristics into a rigorous method with guarantees and outperforms prior approaches on a new hard synthetic dataset.
-
RACORN-1: Adaptive Recall-Preserving Speedup for Low-Selectivity Filtered Vector Search
RACORN-1 adds adaptive search fallback to ACORN-1 to fix recall collapse at low selectivity in filtered vector search, achieving 9-26x speedups over HNSW with recovered recall on 1M-40M datasets.
-
Using predefined vector systems to speed up neural network multimillion class classification
Predefined vector systems structure neural network latent spaces to allow O(1) label prediction via index searches on embedding vectors, delivering up to 11.6x speedup on multimillion-class tasks while preserving accu...
-
MLT-Dedup: Efficient Large-Scale Online Video Deduplication via Multi-Level Representations and Spatial-Temporal Matching
MLT-Dedup achieves 91% reduction in online video repetition rates at 90% precision and 5x indexing capacity using multi-level representations and differential feature-enhanced similarity on a real-world platform.
-
KadiAssistant: A conversational AI Agent for information retrieval in Kadi4Mat
KadiAssistant is a privacy-by-design conversational AI that pairs a self-hosted LLM with semantic search to retrieve and structure information from the Kadi4Mat research data platform while respecting fine-grained per...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.