HNSW turns vector search into graph navigation

Yury Malkov and Dmitry Yashunin introduced HNSW in their 2016 paper as a multilayer proximity graph. The design addressed a scaling problem in nearest-neighbor search: comparing a query with every vector gives exact results, but the work grows directly with the collection.

HNSW assigns some points to sparse upper layers and keeps progressively more points in lower layers. Search starts high, makes large moves toward the query, then descends and refines the candidate set in denser layers.

LAYERED SEARCHHNSW descends from sparse shortcuts into dense local neighborsEach layer narrows the region explored at the next one.
Enter at a sparse upper layerStart from the graph's entry point.
Follow links toward the queryUse long-range edges to cross the vector space.
Descend into a denser layerCarry the nearest current candidate downward.
closer neighbor found
Continue graph traversalExpand the candidate neighborhood.
local minimum reached
Finish the layerKeep the strongest candidates found so far.
more layers remain
Descend againRefine the search in a denser graph.
base layer reached
Return approximate neighborsRank the explored candidate set by distance.

The hierarchy reduces the region searched. It does not guarantee the exact nearest neighbors.

The index is not the embedding model

A bi-encoder creates vectors; HNSW searches them. Product quantization compresses vectors and may be combined with an index, while exact k-nearest-neighbor search compares the query against the full collection.

These components answer different questions and should not be presented as interchangeable vector databases.

Graph construction creates the routes search will later follow

When a vector enters the index, HNSW searches for nearby existing points and connects the new node according to construction settings and neighbor-selection rules. Those choices determine which shortcuts remain available at query time.

A weakly built graph cannot always be repaired by exploring more candidates during search. Construction quality, insertion order, deleted nodes, and later updates belong in the evaluation when the index changes over time.

Choosing HNSW means choosing a recall budget

HNSW exposes construction and search controls that change graph density, build work, memory use, and the number of candidates explored. Their names vary by implementation, but no setting can be interpreted without a recall target and a representative query set.

A filtered support search exposes the tradeoff

Imagine an index of support articles where the query must match both semantic meaning and a product-version filter. If filtering leaves few eligible graph nodes, an aggressive search setting can miss the best valid result.

Increasing search breadth may recover it, but the right setting must be measured on representative queries rather than copied from a vendor default.

The browser vector-search analysis discusses index choices without treating its earlier benchmark framing as proof. HNSW is unnecessary for a small collection that exact search handles comfortably, and its common misuse is quoting a latency number without the dataset, hardware, recall target, index parameters, and filter behavior that produced it.

Exact search supplies the baseline HNSW needs

Before tuning an approximate index, run exact search on the evaluation queries and record the true nearest neighbors. HNSW recall is the share of those neighbors recovered under a particular search setting.

Exact search can also be the production choice for a collection that fits the latency and cost budget. An approximate index adds build time, memory, and operational settings, so scale alone does not make it necessary.

Continue with these glossary entries: