HNSW vector search
How a stack of sparse-to-dense graphs finds the nearest vectors without checking them all.
Read first:Embeddings
Step 1 of 7· Illustrative 2-D points; the graph is built and searched live with the paper's algorithms, so hops, counts and recall are computed
Semantic search turns text into vectors, so answering a query means finding the stored vectors closest to it. Checking every one is exact but slow at millions. HNSW, short for Hierarchical Navigable Small World, builds a stack of linked maps instead. The top layer holds a few points with long links, like motorways; each layer down holds more points with shorter links, like local roads; the bottom layer holds them all. A search starts at the top, hops towards the query, drops a layer and repeats, then ends with a local search. It measures a small fraction of the points and usually finds nearly all the true nearest ones.
Why it matters for your product
HNSW gives high recall at low latency on collections that fit in memory, and the Faiss authors call it the most popular index for medium-sized datasets; in the ANN-Benchmarks study it was the fastest method at every recall level on GloVe word vectors. The costs are memory for its links, slower builds and approximate answers. Two settings govern the trade-off: M at build time and efSearch at query time. Measure recall against exact search on your own data before trusting defaults.
For engineersShow the maths
level = ⌊−ln(u) × mL⌋, u uniform in (0, 1)
Each point's top layer is drawn once, at insertion. The chance of reaching layer l or above is e^(−l ÷ mL); the paper's suggested mL = 1 ÷ ln M makes that 1 ÷ M^l, a skip list with p = 1 ÷ M.
Worked example: With M = 16, one point in 16 reaches layer 1 and one in 256 reaches layer 2, so of a million points about 3,900 reach layer 2 or higher.
memory for links per point ≈ (Mmax0 + mL × Mmax) × bytes per link, Mmax0 = 2M, Mmax = M
Every point stores up to 2M links on layer 0, plus on average mL × M on the layers above, before counting the vector itself.
Worked example: M = 16, mL = 1 ÷ ln 16 ≈ 0.36, 4-byte links: (32 + 0.36 × 16) × 4 ≈ 151 bytes per point. The paper puts M from 6 to 48 at about 60 to 450 bytes.
recall@k = (true k nearest found) ÷ k
The usual quality measure for approximate search: compare the returned k with the exact answer from brute force.
Worked example: The search returns 5 points and 4 of them are among the true 5 nearest: recall@5 = 4 ÷ 5 = 80%.
HNSW keeps its graph, and usually the full vectors, in memory, which becomes expensive at billions of vectors, where compressed indexes such as IVF with product quantisation are common. The paper left removing and updating points to future work, and results stay approximate: a query can settle in the wrong neighbourhood unless efSearch is large enough.
The words you will hear
Approximate nearest neighbour (ANN)
Primary sources
- 01Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphsMalkov, Yashunin · 2016
- 02Approximate nearest neighbor algorithm based on navigable small world graphsMalkov et al. · 2014
- 03ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor AlgorithmsAumüller et al. · 2018
- 04The Faiss libraryDouze et al. · 2024
- 05HNSW algorithm parameters (hnswlib documentation)hnswlib · 2022
Connected ideas
Retrieval and search
IVF and product quantisation
How vector search scales to billions: search only the nearest clusters, and shrink every vector to a few bytes.
ExploreRetrieval and search
Retrieval-augmented generation (RAG)
How a model answers from your documents, and shows you exactly where each claim came from.
ExploreRetrieval and search
Hybrid search and reranking
Search by exact words and by meaning at once, merge the two lists, then let a slower model reread the best few.
ExploreLanguage as numbers
Embeddings
How each token becomes a list of numbers, so that meaning turns into distance.
ExploreWant this working on your data?
We design and build the systems these ideas power: retrieval, agents, voice and the models behind them. Start with a free discovery call.