Navigable Small World Graphs and HNSW Construction

Build a graph where every vector links to its 16 nearest neighbours, drop a query in, and walk greedily downhill. It works on uniform synthetic data and fails on real embeddings, because nearest-only links form tight cliques with no edges leaving them. The walk descends into whichever cluster it started near and stops, having never been offered a step toward the cluster that actually contains the answer. Everything interesting about HNSW is a response to that failure.

Two fixes, usually confused for one

HNSW contributes a layer hierarchy and a neighbour-selection heuristic, and they solve different problems (Malkov & Yashunin, IEEE TPAMI 42(4):824–836, preprint arXiv:1603.09320).

The hierarchy addresses distance travelled. Each inserted point is assigned a maximum level drawn from an exponentially decaying distribution, so layer 0 holds every point, layer 1 holds a fraction, and the top layer holds a handful. Search enters at the top, greedily descends to the locally closest node, drops a layer, and repeats. The sparse upper layers act as long-range links: a few hops cover most of the space before the dense layers do fine positioning. This is what gives roughly logarithmic navigation from a fixed entry point rather than a walk proportional to corpus diameter.

The neighbour-selection heuristic addresses connectivity, and it is the part with no knob. When a point has more candidate links than M slots, the heuristic does not simply keep the M closest. It prefers candidates that are not already well-connected to each other, which approximates a relative neighbourhood graph and preserves edges that bridge between clusters. The authors single this out as what lifts performance specifically at high recall and on highly clustered data, which is the regime real embedding corpora occupy. NSG makes the same move explicitly, constructing a monotonic relative neighbourhood graph so that a greedy walk has a monotone path to its target (Fu, Xiang, Wang & Cai, PVLDB 12(5):461–474). Vamana, the graph inside DiskANN, generalises it with an alpha parameter controlling how aggressively near-duplicate edges are discarded in favour of distant ones.

The three parameters are not peers

M is the maximum out-degree per layer, with layer 0 allowed roughly 2M because it is the only layer holding every point. It is a build-time commitment and it is where graph memory comes from. FAISS documents HNSW32 as adding about 256 bytes per vector at the densest level, which is exactly 32 × 2 × 4 bytes of 32-bit neighbour ids (FAISS wiki, The index factory). Both hnswlib and pgvector default to M = 16, giving 128 bytes per vector.

efConstruction is the candidate-queue width used while inserting a point. It buys graph quality with build time and costs nothing at query time, which makes it the one parameter worth being generous with: hnswlib defaults to 200, pgvector to 64.

efSearch is the candidate-queue width at query time and the only genuinely elastic dial. Search keeps a priority queue of the ef closest candidates seen, expands the nearest unexpanded one, scores its out-neighbours, and stops when the nearest unexpanded candidate is further than the worst member of the result set. Distance computations run at roughly ef times average out-degree, independent of corpus size. Because it is a per-session setting in most implementations, recall can be traded for latency per tenant or per query class without rebuilding anything (pgvector README).

When it breaks

Deletion is the sharpest limit: graph indexes do not really support it. hnswlib's mark_deleted omits an element from results but leaves it in the graph, and reusing its slot requires opting in at construction with allow_replace_deleted (hnswlib README). A high-churn corpus therefore accumulates nodes that cost traversal time and return nothing, while links that once routed through live nodes now route through dead ones. Recall decays slowly and monotonically; the fix is a rebuild.

Memory is the second limit, and it is the full float vectors plus the graph, all of which wants to be resident. A graph index also fails differently from a cell index: its failure mode is connectivity, meaning the answer is indexed but unreachable within the traversal budget. Raising efSearch helps because it widens the frontier; it cannot help if the bridging edge was never built, which is why efConstruction and M matter more on clustered data than their benchmark effect on uniform data suggests.

Finally, the graph is a router, not a scorer. If the vectors it traverses are compressed, graph quality cannot recover what the codes lost; see two-stage search.