HNSW Explained
How Hierarchical Navigable Small World graphs find nearest neighbours in milliseconds, what the M, ef_construction and ef_search knobs do, and what HNSW costs in memory.
The idea: a navigable graph
Imagine each vector as a node, connected to a handful of its nearest neighbours. To find the vector closest to a query, start anywhere and repeatedly move to whichever neighbour is closer to the query. Stop when no neighbour is closer. That is greedy graph search, and on a well-built graph it reaches the right region in a few dozen hops.
Search a proximity graph
Click anywhere to place a query. The search starts at the entry node and hops to whichever neighbour is closest to the query.
| ef | recall@1 | distances |
|---|---|---|
| 1 | 61% | 18 |
| 2 | 79% | 22 |
| 4 | 86% | 25 |
| 8 | 98% | 33 |
| 16 | 100% | 43 |
Pure greedy search (ef = 1) is cheap but can stop at a node whose neighbours are all farther away. A wider beam explores more candidates: recall goes up, and so does cost. That is the ef_search knob in every HNSW-based vector database.
Try a few queries with a beam width of 1. Sometimes the search gets stuck at a node whose neighbours are all farther from the query, even though a closer node exists elsewhere. HNSW fixes this in two ways: a hierarchy of layers, and a wider beam.
The hierarchy
- Layer 0 contains every vector, each linked to up to 2 × M neighbours.
- Higher layers contain exponentially fewer vectors, chosen at random at insert time. Each layer up keeps about 1/M of the nodes below it.
- A search starts at the top from a fixed entry point, where a few long hops cross the whole space. At each layer it greedily moves as close to the query as it can, then drops down and continues from there.
- On layer 0 it runs a beam search, keeping the best
ef_searchcandidates found so far and exploring their neighbours, then returns the top k.
It works like a skip list for vectors. The top layers get you to the right neighbourhood in a few hops, and layer 0 does the fine-grained search. Search cost grows roughly logarithmically with N.
The three knobs
| Parameter | What it controls | Typical values | Raising it… |
|---|---|---|---|
| M | Max links per node (2M on layer 0) | 16–64 | Improves recall, costs more memory and slower inserts |
| ef_construction | Beam width while building | 100–500 | Builds a better graph, but slower |
| ef_search | Beam width at query time (≥ k) | 40–400 | Raises recall and latency. The main runtime knob |
ef_search can usually be set per query. That lets you offer a fast mode and an accurate mode on the same index, or raise it when a filter makes matches sparse.
Memory: the real cost
HNSW needs the full vectors plus the graph in RAM for fast search:
Bytes per vector ≈ d × bytes per dim + 2 × M × 4 bytes (links) × ~1.1 (upper layers)
For 1,536-dim float32 with M = 16: 6,144 + ≈ 141 bytes. The links are small next to the vectors. For 100M vectors that is ≈ 630 GB, which means sharding across machines, compressing the vectors (int8, PQ), or using a disk-based index.
Operational realities
- Inserts are incremental. New vectors are linked in without a rebuild, a big advantage over IVF for live data.
- Deletes are awkward. Removing a node can break paths through it. Most implementations tombstone deleted nodes and filter them out, then rebuild or compact periodically. Heavy delete workloads degrade recall and waste memory until compaction runs.
- Builds are CPU-heavy. Bulk-loading hundreds of millions of vectors takes hours. Plan index builds and re-embedding migrations as batch jobs, often building offline and swapping in.
- Memory is random-access. Graph traversal jumps around memory, which is why HNSW on SSD performs poorly without a design like DiskANN built for it.
Key takeaways
- HNSW is a layered proximity graph. Sparse upper layers give long hops, and the dense bottom layer holds every vector.
- Search descends greedily layer by layer, then runs a beam search of width ef_search on the bottom layer.
- M (links per node) and ef_construction set graph quality and memory. ef_search sets the per-query recall/latency trade-off.
- HNSW needs the vectors plus about 2 × M × 4 bytes of links per vector in RAM. Deletes and bulk rebuilds need care.