Source-linked AI summary
Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
Yu. A. Malkov, D. A. Yashunin
TL;DR
Approximate nearest-neighbor search needs scalable methods that remain effective for high-dimensional and clustered data. HNSW addresses this with a fully graph-based hierarchy whose links are separated by scale and whose neighbors are selected heuristically. The paper reports strong performance across datasets and generalized metric spaces, with distributed-search and graph-approximation limitations discussed.
Problem
Approximate K-NNS is needed because exhaustive search scales linearly with dataset size and exact methods are limited by high-dimensionality.
Method
HNSW incrementally builds nested proximity-graph layers with exponentially distributed levels, searches greedily from upper to lower layers, and uses heuristic neighbor selection.
Results
HNSW strongly outperformed previous open-source state-of-the-art vector-only approaches and led across a large variety of datasets.
Takeaways & Limitations
HNSW provides a robust approximate search index for generalized metric spaces across the datasets tested.
Takeaways & Limitations
Distributed search is constrained by top-layer entry-point congestion, while approximate edge selection requires zero-layer backtracking to avoid local minima.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Similarity search needs scalable K-nearest neighbor methods because exhaustive search scales linearly with dataset size, while exact methods are limited by high dimensionality. The paper proposes HNSW, a fully graph-based approximate structure designed for logarithmic scaling and strong performance.
- Problem: K-NNS finds the K dataset elements minimizing distance to a query, but naïve exhaustive search scales linearly with the number of stored elements.The task supports applications including non-parametric machine learning, image-feature matching, and semantic document retrieval.
- Problem: Exact K-NNS is substantially limited on relatively high-dimensional data by the curse of dimensionality.Approximate nearest neighbor search relaxes exactness by allowing a small number of errors.
- Problem: Recall measures approximate-search quality as the ratio of found true nearest neighbors to K.The paper situates proximity graphs alongside tree algorithms, locality-sensitive hashing, and product quantization.
- Contribution: HNSW is a fully graph-based incremental K-ANNS structure intended to provide much better logarithmic complexity scaling.Its contributions include explicit entry-point selection, scale-separated links, and a neighbor-selection heuristic.
- Contribution: Performance evaluation reports that HNSW strongly outperforms previous open-source state-of-the-art approaches designed only for vector spaces.The proposed method is presented as applicable to general metric spaces.
2 RELATED WORKS
Related approaches use greedy routing over proximity graphs and navigable network structures to accelerate nearest-neighbor search. Their limitations include unfavorable scaling or connectivity failures on clustered and low-dimensional data, motivating HNSW.
- Proximity graph techniques: Proximity-graph search greedily moves from an entry point to the neighbor closest to the query while tracking the best discovered neighbors.The procedure repeatedly examines distances to a current node’s adjacent elements.
- Proximity graph techniques: k-NN graph methods suffer power-law routing growth and may lose global connectivity, producing poor search results on clustered data.Hybrid methods often add vector-only structures such as kd-trees or product quantization for coarse entry-point search.
- NSW: NSW constructs a navigable graph by consecutive random-order insertion and bidirectional connections to previously inserted neighbors.Early inserted nodes later act as bridges between network hubs, preserving connectivity and logarithmic hop scaling.
- NSW: NSW construction can be parallelized without global synchronization, but its polylogarithmic complexity still causes severe degradation on low-dimensional datasets.On such datasets, NSW could lose to tree-based algorithms by several orders of magnitude.
- Navigable small world models: Navigable small world networks are defined by logarithmic or polylogarithmic scaling of greedy graph-routing hops with network size.Kleinberg-style and scale-free models have additional requirements or unfavorable scaling for search applications.
- Navigable small world models: NSW uses a decentralized construction model suitable for data in arbitrary spaces, unlike models requiring global knowledge of the data distribution.This makes NSW relevant to scalable routing and distributed similarity search.
3 MOTIVATION
The paper motivates HNSW by separating graph links across distance scales and searching a hierarchy from its upper layers. A diverse-neighbor heuristic addresses connectivity problems that arise in clustered data.
- 3 MOTIVATION: NSW routing has “zoom-out” and “zoom-in” phases, and low-degree starts can leave the search in distant false local minima.Starting from high-degree hubs improves routing, especially on low-dimensional data, but retains at best polylogarithmic single-search scaling.
- 3 MOTIVATION: NSW distance computations grow with the product of greedy hops and the average degree along the path, both of which scale logarithmically.This motivates reducing the number of evaluated connections at each scale.
- 3 MOTIVATION: HNSW separates links by length scale into layers, searches from the upper layer downward, and evaluates a fixed portion of connections per element.The upper layer performs long-link greedy routing before lower layers refine the search with shorter links.
- 3 MOTIVATION: Exponentially decaying level assignment yields a logarithmic expected number of layers, with iterative greedy search from the top layer to layer zero.Merging all layers produces a structure similar to NSW, while random levels remove the need to shuffle insertion order.
- 3 MOTIVATION: The heuristic preserves cross-cluster connectivity when nearest candidates otherwise come exclusively from one isolated cluster.The illustrated insertion selects an element from Cluster 2 to maintain a bridge from a new element on Cluster 1’s boundary.
- 3 MOTIVATION: The neighbor-selection heuristic creates diverse connections rather than choosing only the closest neighbors.With enough candidates, it can contain the exact relative neighborhood graph as a subgraph and preserve connectivity across highly clustered data.
4 ALGORITHM DESCRIPTION
HNSW constructs a multilayer proximity graph with randomized layer assignments, searches from upper layers downward, and uses heuristic neighbor selection to improve scalability and recall. Its parameter choices govern layer overlap, zero-layer connectivity, search quality, memory, and construction complexity.
- Multilayer construction: Each inserted element receives a maximum layer sampled from an exponentially decaying probability distribution.This creates nested subsets of elements across the multilayer graph.
- Search procedure: Search traverses layers from the top downward, using greedy search and then a dynamic candidate list to return approximate nearest neighbors.The algorithm uses ef=1 during upper-layer search and expands ef at the ground layer for recall control.
- Neighbor selection: Neighbor selection can use either the M closest candidates or a heuristic that promotes connections in diverse directions.The heuristic is intended to improve connectivity, particularly for clustered data.
- Parameter effects: The optimal mL balances layer overlap against within-layer greedy hop count, with 1/ln(M) offered as a simple choice.Reducing mL lowers overlap but increases average hops within each layer.
- Parameter effects: Setting Mmax0 to 2∙M is suggested because Mmax0=M penalizes high-recall search, while larger values degrade performance and increase memory usage.Mmax0 controls the maximum number of zero-layer connections.
- Robustness and complexity: The heuristic improves or matches naïve neighbor selection, especially for low-dimensional, high-recall, and highly clustered data, where naïve search can stall at cluster boundaries.Backtracking addresses approximation errors in the zero-layer graph; empirical results indicate these errors do not alter scaling for low-dimensional data.
- Robustness and complexity: HNSW has O(log(N)) overall complexity, while insertion scales similarly and reaches O(N∙log(N)) construction time.The layer-search step count is bounded independently of dataset size, and the construction complexity follows the search complexity.
5 PERFORMANCE EVALUATION
The evaluation compares Hierarchical NSW with NSW, open-source Euclidean K-ANNS methods, general metric-space algorithms, and Faiss across synthetic, benchmark, and large-scale datasets. Hierarchical NSW reduces distance computations, shows at-least-logarithmic scaling in the tested setting, and achieves strong accuracy and speed results, with higher memory use than Faiss.
- Comparison with baseline NSW: Hierarchical NSW uses much less distance computations than NSW, especially at high recalls.This comparison uses d=4 random hypercube data for 10-NN search.
- Comparison with baseline NSW: Hierarchical NSW has complexity scaling not worse than logarithmic and outperforms NSW at every tested dataset size.The test uses d=8 random hypercube data, 10-NN search, and fixed recall of 0.95.
- Comparison in Euclid spaces: The benchmark evaluates one thousand queries per dataset and reports recall and average single-search time for each algorithm.The compared methods include NSW, FLANN, Annoy, VP-tree, and FALCONN.
- Comparison in Euclid spaces: Hierarchical NSW clearly outperforms competing methods on SIFT, GloVe, DEEP, and CoPhIR datasets.For low-dimensional data with d=4, it is reported as slightly faster at high recall than Annoy while strongly outperforming the other algorithms.
- Comparison with Faiss: On a 200M subset of the 1B SIFT dataset, Hierarchical NSW achieves higher accuracy, faster search, and faster index construction than Faiss, but requires significantly more RAM.The Faiss comparison uses state-of-the-art product-quantization implementations as the baseline.
- Comparison with Faiss: The Hierarchical NSW query-time scaling in the large-scale SIFT experiment deviates from a pure logarithm, possibly because of the dataset’s relatively high dimensionality.The scaling is shown in the inset of Fig. 15.
6 DISCUSSION
Hierarchical NSW improves robustness and practical utility across varied data structures while retaining incremental indexing and graph byproducts. Its main boundaries are distributed-search limitations and remaining construction and evaluation gaps.
- The approach supports continuous incremental indexing and produces approximations of k-NN and relative neighborhood graphs during construction.
- Hierarchical NSW performs well across datasets with complex structures and varying effective dimensionality across scales.The paper emphasizes robustness in generalized metric spaces, including data that is high dimensional at large scales and low dimensional at small scales.
- Index construction remains sensitive to the number of added connections per layer M, and full 1B SIFT and 1B DEEP evaluations remain future work.The paper also identifies element updates and removal as unsupported extensions of interest.
- Compared with basic NSW, Hierarchical NSW loses the possibility of distributed search because searches always begin at the top layer.Higher-layer congestion prevents using the same distributed-search techniques as basic NSW.
- Partitioning data across cluster nodes can distribute the structure, but total parallel throughput does not scale well with the number of nodes.
- Skip-list similarity suggests other distribution techniques may yield logarithmic scalability and ideally uniform node load.