Nearly every vector database you can name — pgvector, Qdrant, Weaviate, and plenty more — ships the same index under the hood: Hierarchical Navigable Small World graphs, from a 2016 paper by Yu. A. Malkov and D. A. Yashunin. HNSW won because it delivers high recall at low latency without any coarse quantization stage. But it also has sharp edges that only show up in production: it lives in RAM, it handles deletes badly, and metadata filters can quietly wreck either its speed or its accuracy. Understanding the data structure explains all three.
A greedy walk through a graph
Start with the flat version, the Navigable Small World (NSW) graph. Every vector is a node, connected to a handful of near neighbors. To answer a query, you pick an entry node, look at its neighbors, hop to whichever one is closest to the query, and repeat until no neighbor improves on where you stand. That greedy walk is fast because each hop discards huge regions of the space — but it has two problems. Hops early in the walk are wasteful little steps if you enter far from the target, and a purely greedy walk can get stuck in a local minimum: a node none of whose neighbors are closer to the query, even though better nodes exist elsewhere in the graph.
HNSW fixes the first problem with hierarchy, borrowing the trick that makes skip lists work. Instead of one graph, you build a stack of them. Layer 0 contains every vector. Each layer above it contains an exponentially shrinking random sample of the layer below, so upper layers are sparse graphs whose edges span long distances. When a new element is inserted, its top layer is drawn from an exponentially decaying distribution:
l = floor(-ln(uniform(0,1)) * mL)with the paper recommending mL = 1/ln(M), where M is the connectivity parameter. Most elements land only in layer 0; a lucky few become long-range waypoints several layers up.
Search enters at the top layer and greedily descends: on every layer above 0 it runs the greedy walk keeping just a single candidate (ef = 1), finds the local best, and drops down a layer using that node as the new entry point. The upper layers do coarse routing — crossing the space in a few long hops — and only on layer 0 does the search widen out, keeping a dynamic candidate list of size ef to fight the local-minimum problem. Bigger ef means more candidates explored, higher recall, slower queries. The paper's headline claim is that this structure gives search complexity that scales logarithmically with collection size, and — unlike earlier proximity-graph methods — it needs no separate coarse search structure like a quantizer or tree bolted on front.
Picking neighbors is not "pick the closest"
The subtler contribution of the paper is how edges get chosen at insert time. The obvious rule — connect each new node to its M nearest neighbors — fails on clustered data: all M edges point into the node's own cluster, and the greedy walk has no way to escape a cluster it entered by mistake. HNSW instead uses a selection heuristic that favors diverse edges: a candidate is kept when it is closer to the new node than to any already-selected neighbor. The effect is that some edges deliberately go to farther nodes in other directions, preserving routes between clusters. The paper notes this heuristic matters most precisely on clustered data at high recall targets.
Layer 0 gets extra connectivity: the maximum degree there is M_max0 = 2 * M, since that's the layer where the fine-grained search actually happens.
The three knobs, with real defaults
Every HNSW implementation exposes the same three parameters. The hnswlib reference implementation documents the practical ranges:
| Parameter | What it controls | Guidance (hnswlib) |
|---|---|---|
M | Edges per node per layer | 12–48 fits most use cases; high-dimensional embeddings may want 48–64 |
ef_construction | Candidate list size at build time | Bigger = slower build, better graph; quality plateaus |
ef | Candidate list size at query time | From k up; higher = more recall, more latency |
The link structure alone costs roughly M * 8–10 bytes per element on top of the vectors themselves, which is why M is a memory knob as much as a recall knob. hnswlib also documents a useful sanity check for ef_construction: query the index for M nearest neighbors with ef set equal to ef_construction — if recall is below 0.9, there's room to improve the build.
In pgvector, the same knobs surface as index options with conservative defaults — m = 16, ef_construction = 64, and a query-time hnsw.ef_search defaulting to 40:
CREATE INDEX ON items USING hnsw (embedding vector_l2_ops)
WITH (m = 16, ef_construction = 64);
SET hnsw.ef_search = 100; -- per-session recall/latency knobpgvector's docs are candid about the tradeoff versus its other index type: HNSW beats IVFFlat on the speed–recall curve but builds slower and uses more memory — they suggest raising maintenance_work_mem (e.g. to 8GB) so the graph fits in memory during the build. And the index is only used at all when the query has an ORDER BY on a distance operator plus a LIMIT; on small tables the planner will rightly prefer a sequential scan.
Where the design bites back: deletes
HNSW was built for static datasets, and it shows. There is no clean delete operation: the hierarchy is sparse by construction, and a node that happens to be one of the few members of an upper layer is load-bearing — remove it naively and everything that routed through it can become unreachable. Pinecone's engineering write-up on running HNSW in production is blunt about the consequence: real systems don't remove nodes, they tombstone them — flag them as deleted, filter them out of results, and keep them in the graph (and in memory) until a periodic rebuild reclaims the space. Updates inherit the problem, because an update is a delete plus an insert. Under heavy churn, memory grows well past what the live data needs, and you're paying RAM for ghosts.
Where the design bites back: filters
The second production headache is the query every application eventually needs: nearest neighbors where category = 'shoes'. HNSW has no native answer, and the two obvious strategies both fail in a characteristic way, as Qdrant's article on filtering lays out:
- Post-filtering runs the vector search first, then applies the filter. With a low-cardinality filter, most of your top-k gets discarded — and if the matching items weren't in the candidate set at all, no amount of filtering recovers them.
- Pre-filtering restricts the graph walk to nodes that pass the filter. But the graph's connectivity was built over all nodes; over large datasets a selective filter breaks too many links, and the greedy walk strands in disconnected fragments, tanking accuracy.
Qdrant's fix is a filterable HNSW: at build time it adds extra links so that commonly-filtered subsets stay navigable on their own, using category-aware connection strategies. Its query planner also refuses to use the graph when the filter is selective enough that brute force wins — below a full-scan threshold (10 kilobytes by default) it skips HNSW and scans the filtered set directly. That planner behavior is worth internalizing even if you use a different database: for highly selective filters, the honest answer is usually exact search over the survivors, not a graph walk.
The shape of the tradeoff
HNSW buys you logarithmic-ish search and excellent recall by spending memory and by assuming the world holds still. If your corpus is mostly append-only, fits in RAM with the M * 8–10 bytes per element of graph overhead, and your filters are mild, it is close to a free lunch. If you churn vectors constantly or slice the data with selective filters on every query, the index degrades in ways the benchmark curves never showed — and the fixes (tombstones plus rebuilds, filterable graph variants, planner cutoffs to brute force) are all workarounds layered on a structure that fundamentally wants to be immutable.