nucleation

LIT-1098: Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the authors' arXiv preprint, version 4 of 14 August 2018 (arxiv.org/pdf/1603.09320v4, 13 pp., the last arXiv version, whose abstract matches the published one apart from copy-editing; the TPAMI body was not seen). Version 1 (2016) was compared: it claimed deletion, which v4 drops and lists as future work. Unpaywall and OpenAlex list no open-access copy of the TPAMI version. Worth reading as the source of the hierarchical graph index: nested proximity graphs on geometrically sampled layers, with a neighbour rule that keeps links between clusters. Its logarithmic search cost is derived only for exact Delaunay graphs of bounded degree, which it does not build, and is measured only on uniform random data in 4 and 8 dimensions; on 200M SIFT the scaling "deviates from the pure logarithm". It gives no worst-case or recall guarantee and no deletion. For CLAIM-310 it shows, with bins replaced by graphs, that the arrangement of fixed data under a fixed distance decides cost and, on clustered data, whether items can be found at all; it narrows part 2, since the index is built without any query mix and every test drew its queries from the data. For QUESTION-114 it supplies a measured build-time against query-time curve and O(N log N) construction argued at low dimension, with insertion upkeep only.
Tagsinformation-retrieval, network-science, anthology-candidate
Cited as “paper” byNOTE-916 — Malkov & Yashunin — Hierarchical navigable small world graphs for approximate nearest neighbour search
Cited as “source” byTHEORY-365 — In one study of a stack of proximity graphs on nested random subsets of the data, each element's top layer drawn geometrically, greedy search on uniform random data in 8 dimensions needed a number of distance computations that grew no worse than logarithmically with the number of items and stayed below a single-layer navigable graph's at every size tested, and in 4 dimensions the beam width needed for a fixed recall saturated; the logarithmic bound is derived only for exact Delaunay graphs of bounded degree, which the index does not build, and on 200 million SIFT vectors the measured growth departs from it, THEORY-385 — In HNSW over 10-dimensional data in 100 isolated clusters, linking each new item to its nearest neighbours leaves part of the bottom layer unreachable from the entry point and caps recall well short of 1 however wide the query search, while linking a candidate only when it is nearer the new item than to any neighbour already kept keeps that layer connected and reaches recall near 1 with about half the links; on uniform data at 10 and 64 dimensions the two rules differ little; shown in Malkov and Yashunin's own tests on 10 million points and in an independent re-run on 30,000, which found the nearest-neighbour rule capped at a recall@10 of 0.72 to 0.83 against 0.999, at matched build cost too, THEORY-815 — Layering a navigable small-world graph on nested random subsets of the data, with links separated by length scale and each layer's degree capped, makes greedy nearest-neighbour search cost grow logarithmically with the number of items on data of low intrinsic dimension, where the single-layer graph's cost grows polylogarithmically

Graph View

Malkov, Y. A. and Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4), 824–836. DOI 10.1109/TPAMI.2018.2889473

Key takeaways

Read in full (NOTE-916). HNSW is a stack of proximity graphs on nested random subsets of the data. Each element’s top layer is drawn from a geometric distribution, and new neighbours are chosen by a pruning rule that favours diverse directions. Searching from the sparse top layer down makes per-query cost grow about logarithmically with N on uniform random data in 4 and 8 dimensions, which flat NSW graphs did not. The logarithmic bound is derived only for exact Delaunay graphs of bounded mean degree, which HNSW does not build. For the graphs it does build, logarithmic scaling is measured, at low dimension only, and on 200M SIFT vectors the paper reports the scaling “deviates from the pure logarithm”. The neighbour-selection rule is what keeps clustered data searchable: in the paper’s synthetic test with 100 isolated clusters, linking each element to its nearest neighbours fails to reach high recall. There is no worst-case or recall guarantee, no deletion, and no analysis of query distributions unlike the data.

Why this is here

CLAIM-310, with LIT-1103 and LIT-1112: the graph index in widest use. Its logarithmic search time is proved only for idealized graphs it does not build and measured only at low dimension; its clearest result is that the neighbour-selection rule decides whether clustered items are findable. The final version supports insertion only.

Backlinks