HNSW Explained: The Index Behind Most Vector Search

Hierarchical Navigable Small World graphs — Malkov and Yashunin, 2016, later in IEEE TPAMI — are the default index in pgvector, Qdrant, Weaviate, Milvus, Lucene and Faiss. The structure is easier than its name: it is a skip list where “next” means “nearer in vector space”.

It is a skip list in many dimensions

A skip list over sorted numbers has several linked lists stacked on top of each other. The bottom contains every element; each level up contains a random sample of the level below. You search by walking the sparse top list until you overshoot, dropping a level, walking again, and so on — logarithmic instead of linear, from a structure with no global ordering requirement beyond “less than”.

HNSW is that idea with “nearer” substituted for “less than”. Each vector is a node. Each node is assigned a maximum layer by an exponentially decaying random draw — the paper uses l = floor(-ln(U) * mL) with mL = 1 / ln(M) — so the probability of appearing at level l or above is M^-l. With M = 16, one node in 16 reaches layer 1, one in 256 reaches layer 2, and the top layer of a ten-million-vector index sits at about log16(10^7) ≈ 5.8, so six layers. Within a layer, each node keeps links to a bounded number of its near neighbours; the top layers are sparse and their links span long distances, the bottom layer is dense and its links are short.

Tracing one search

A query arrives. The search has a fixed entry point — the node in the highest layer — and proceeds:

layer 5..1   greedy descent, beam width 1:
               repeat:
                 look at the current node's neighbours in this layer
                 if one is closer to q than the current node, move to it
                 else drop to the next layer down, same node

layer 0      beam search, beam width ef_search:
               candidates = {entry}, results = {entry}
               while candidates not empty:
                 c = closest unvisited candidate
                 if dist(c, q) > worst in results and |results| == ef: break
                 for each neighbour n of c:
                   if n unvisited: add to candidates and to results
                 keep only the ef best in results

return       the k best of the ef results

The upper layers are a coarse teleport: they move the search into roughly the right region of the space in a handful of hops. All the accuracy comes from the beam search at layer 0, and ef_search is the beam width. It must be at least k, and raising it makes the search both slower and more accurate — that single knob is the entire recall/latency trade-off at query time.

You can count the work. Each expansion evaluates up to M neighbours, so a layer-0 search that expands on the order of ef_search nodes performs roughly ef_search × M distance computations. At ef_search = 40 and M = 16 that is around 640 — against ten million vectors. That ratio, four or five orders of magnitude fewer comparisons than a full scan, is the whole product.

The three parameters

The practical order is: leave M at the default, set ef_construction as high as your build window tolerates because it is free afterwards, and tune ef_search against measured recall. Only raise M if a high ef_search still cannot reach your recall target — that is the signal the graph itself is too sparse for your data.

What the graph costs

layer 0 links:  2M * 4 bytes         = 128 B  (M = 16, 4-byte ids)
upper layers:   expected node count per node is M/(M-1) = 1.067,
                so the extra 0.067 layers * M * 4 bytes  =   4 B
                                                         -------
graph overhead per vector                                 ~132 B

vs the vector itself at 1536 dims:                        6144 B

  overhead = 2.1%          at M = 16, d = 1536
  overhead = 4.3%          at M = 32, d = 1536
  overhead = 8.4%          at M = 32, d =  384

The lesson is in the third line. Against wide float32 vectors the graph is a rounding error and there is no point economising on M. Against narrow or quantised vectors it is a substantial fraction of the index — binary-quantised 1536-dim vectors are 192 bytes each, so a graph at M = 32 costs more than the vectors do. Quantisation shifts where the memory goes, and the graph parameter you had ignored becomes the one that matters.

Why the build is the expensive part

Inserting one node runs the same search with beam width ef_construction, then selects neighbours and repairs their link lists. So the build is roughly N × ef_construction × M distance computations: at 10 million vectors with ef_construction = 64 and M = 16, on the order of 10 billion. That is why HNSW builds take hours and why they parallelise well but never become cheap.

It also explains the memory requirement. The graph must be in memory while it is being built, because each insertion navigates the existing graph. In pgvector this is maintenance_work_mem; when it is exceeded the build spills and emits a notice saying the graph no longer fits after so many tuples, with a hint that building will take significantly longer. Treat that notice as an error: raise the setting and start again rather than waiting out a build that is now an order of magnitude slower.

Where it goes wrong

• Deletes. Removing a node would strand the nodes whose only route passed through it, so engines mark it deleted and keep it in the graph. Recall and memory both degrade with the tombstone fraction, and only a rebuild or compaction recovers them.
• Filtered search. The greedy walk is over the whole graph. If most neighbours fail your predicate the walk stalls, and you get too few results rather than an error. Engines address this with extra links, adaptive strategies or iterative scans; none of it is free.
• ef_search below k. Asking for 50 results with a beam of 40 cannot work. Some engines clamp silently, so recall quietly drops instead of anything failing.
• Clustered or duplicated data. Thousands of near-identical vectors fill a node’s neighbour list with copies of the same thing, wasting the graph’s connectivity. Deduplicating before indexing improves recall and shrinks the index at the same time.
• Insertion order. The graph depends on the order nodes were inserted, so two indexes over the same data are not identical and recall can vary by a little between rebuilds. Measure recall after every rebuild rather than assuming it carried over.