Hierarchical Navigable Small World (HNSW) graphs are the default approximate nearest neighbour index in most vector databases and in libraries such as hnswlib, FAISS and pgvector. Most explanations stop at the picture of layered graphs. This article is the practitioner's version: a compact implementation you can read in one sitting, the neighbour-selection heuristic that makes it work on clustered data, a recall harness for tuning, the memory arithmetic for a real collection, and the two problems that bite in production: deletes and filtered search.
If you want the derivation of why search scales logarithmically, read the HNSW math article; for the component overview, see HNSW architecture. Here we build and operate one.
The structure in one picture
An HNSW index stores, for each vector, a level and an adjacency list per layer from 0 up to that level. Levels are drawn from an exponentially decaying distribution, level = floor(-ln(U) * mL) with mL = 1 / ln(M), so roughly a fraction 1/M of nodes reach layer 1, 1/M squared reach layer 2, and so on. Upper layers are sparse and their edges are long; layer 0 contains everything.
Three parameters control the structure. M is the number of links a node keeps on upper layers; layer 0 conventionally keeps 2M because it carries the fine-grained search. efConstruction is the beam width used while inserting, which decides how good the chosen neighbours are. ef (or efSearch) is the beam width at query time and is the main recall-versus-latency knob.
An implementation you can read
The whole algorithm is two routines: a beam search within one layer, and an insert that uses it at every layer. This version uses squared Euclidean distance and numpy; swap the distance function for cosine or inner product.
import heapq, math, random
import numpy as np
class HNSW:
def __init__(self, dim, M=16, ef_construction=200):
self.M, self.M0, self.efc = M, 2 * M, ef_construction
self.mL = 1.0 / math.log(M)
self.vecs = np.empty((0, dim), dtype=np.float32)
self.links = [] # links[node][layer] -> list of neighbour ids
self.entry, self.top = None, -1
def dist(self, q, ids):
d = self.vecs[ids] - q
return np.einsum("ij,ij->i", d, d)
def search_layer(self, q, entries, ef, layer):
visited = set(entries)
d0 = self.dist(q, entries)
cand = [(d, e) for d, e in zip(d0, entries)] # min-heap: closest first
best = [(-d, e) for d, e in zip(d0, entries)] # max-heap: worst on top
heapq.heapify(cand); heapq.heapify(best)
while cand:
d, e = heapq.heappop(cand)
if d > -best[0][0]:
break # nothing closer left
nbrs = [n for n in self.links[e][layer] if n not in visited]
visited.update(nbrs)
if not nbrs:
continue
for dn, n in zip(self.dist(q, nbrs), nbrs):
if len(best) < ef or dn < -best[0][0]:
heapq.heappush(cand, (dn, n))
heapq.heappush(best, (-dn, n))
if len(best) > ef:
heapq.heappop(best)
return sorted((-d, e) for d, e in best) # (dist, id) ascending
def select(self, q, cands, m):
"""Heuristic: keep a candidate only if it is closer to q than to any kept one."""
kept = []
for d, e in cands:
if len(kept) == m:
break
if all(d < self.dist(self.vecs[e], [k])[0] for _, k in kept):
kept.append((d, e))
return [e for _, e in kept]
def insert(self, v):
nid = len(self.links)
self.vecs = np.vstack([self.vecs, v.astype(np.float32)])
lvl = int(-math.log(1.0 - random.random()) * self.mL)
self.links.append([[] for _ in range(lvl + 1)])
if self.entry is None:
self.entry, self.top = nid, lvl
return
ep = [self.entry]
for layer in range(self.top, lvl, -1): # greedy phase, ef = 1
ep = [self.search_layer(v, ep, 1, layer)[0][1]]
for layer in range(min(lvl, self.top), -1, -1):
found = self.search_layer(v, ep, self.efc, layer)
cap = self.M0 if layer == 0 else self.M
for n in self.select(v, found, self.M):
self.links[nid][layer].append(n)
self.links[n][layer].append(nid)
if len(self.links[n][layer]) > cap: # shrink the neighbour's list
nb = self.links[n][layer]
ranked = sorted(zip(self.dist(self.vecs[n], nb), nb))
self.links[n][layer] = self.select(self.vecs[n], ranked, cap)
ep = [e for _, e in found]
if lvl > self.top:
self.entry, self.top = nid, lvl
def query(self, q, k=10, ef=64):
ep = [self.entry]
for layer in range(self.top, 0, -1):
ep = [self.search_layer(q, ep, 1, layer)[0][1]]
return self.search_layer(q, ep, max(ef, k), 0)[:k]The termination test in search_layer is the key line: once the closest unexpanded candidate is farther than the worst member of the result set, no path through it can improve the result, so the search stops. The vstack per insert makes this toy quadratic in copying; real libraries preallocate a fixed-capacity array, store links in flat per-node blocks and use fine-grained locks for parallel inserts.
Why the neighbour heuristic matters
The naive choice is to connect each new node to its M nearest neighbours. On clustered data that fails: all M links point into the node's own cluster, and the graph splits into islands that greedy search cannot cross. The heuristic in select keeps a candidate only if it is closer to the new node than to any neighbour already kept. A candidate that is shadowed by an existing neighbour adds little, because search can reach it through that neighbour; a candidate in a different direction adds a bridge.
The original paper also describes two optional variants: extending the candidate set with neighbours of candidates, and keeping pruned candidates to fill unused slots. Libraries differ on whether they enable these, which is one reason the same M and ef give slightly different recall in different engines.
Measuring recall before tuning
Never tune ef by intuition. Compute exact neighbours for a sample of real queries with brute force, then sweep ef and record recall@k and latency. The query sample should come from production traffic, not from the indexed vectors themselves, because self-queries are unrealistically easy.
import time
import numpy as np
def exact_knn(base, queries, k):
d = ((queries[:, None, :] - base[None, :, :]) ** 2).sum(-1) # fine for a 1k-query sample
return np.argsort(d, axis=1)[:, :k]
def sweep(index, base, queries, k=10, efs=(16, 32, 64, 128, 256)):
truth = exact_knn(base, queries, k)
for ef in efs:
t0 = time.perf_counter()
got = [[i for _, i in index.query(q, k, ef)] for q in queries]
ms = (time.perf_counter() - t0) * 1000 / len(queries)
per_q = [len(set(g) & set(t)) / k for g, t in zip(got, truth)]
p5 = np.percentile(per_q, 5) # recall that 95% of queries beat
print(f"ef={ef:4d} mean={np.mean(per_q):.3f} p5={p5:.3f} {ms:.2f} ms/query")The curve almost always has a knee: recall climbs fast until ef is a few times k, then flattens while latency keeps growing roughly linearly. Pick the smallest ef whose recall target holds for 95 percent of queries (the p5 column), not the mean, because a few hard queries in sparse regions dominate the user-visible misses.
Memory arithmetic
Take 10 million 768-dimensional float32 embeddings with M = 16. The vectors alone need 10M x 768 x 4 bytes, about 30.7 GB. Layer 0 links need up to 2M = 32 neighbour ids of 4 bytes each per node: 10M x 32 x 4, about 1.3 GB. Upper layers hold about 1/M of the nodes with M links each, which adds well under 0.1 GB. So the graph is roughly 4 percent of the footprint and the vectors are the rest.
That is why memory work on HNSW focuses on the vectors. Options, in order of invasiveness: store float16 (halves it, small recall cost), use scalar 8-bit quantisation (quarters it), or store product-quantised codes in the graph and re-rank the top candidates with full vectors kept on SSD. Raising M from 16 to 32 doubles the link memory and build time and usually helps recall only on high-dimensional or hard-to-separate data. If the collection does not fit in RAM even quantised, compare with DiskANN and IVF-PQ.
Deletes and updates
HNSW has no cheap true delete. Removing a node strands paths that ran through it, and repairing every neighbour is expensive. Libraries therefore use tombstones. In hnswlib, mark_deleted(label) hides an element from results while it still participates in routing, and an index created with allow_replace_deleted=True can reuse those slots via add_items(..., replace_deleted=True).
Tombstones have two costs. Search still visits deleted nodes, so with heavy churn you do more work to return k live results. And a replaced slot gets new links while old in-links from unrelated nodes now point at a vector that has moved, which slowly degrades graph quality. Operationally: track the deleted fraction, rerun the recall sweep weekly on churning indexes, and rebuild (or compact segments, in databases that segment the index) when recall drops below target. Updates are delete plus insert; do not overwrite a vector in place and expect its links to stay sensible.
Filtered search
Real queries carry predicates: tenant, language, date range, access control. Post-filtering runs the ANN search and drops non-matching results. If only 1 percent of vectors match, a search with ef = 100 may return zero matches. The pgvector documentation describes exactly this: filtering is applied after the index scan, so a query can return fewer rows than its LIMIT. Since version 0.8.0 pgvector offers iterative index scans (SET hnsw.iterative_scan = relaxed_order or strict_order), which keep scanning until enough rows pass, bounded by hnsw.max_scan_tuples.
In-search filtering keeps non-matching nodes for routing but excludes them from results, which is what hnswlib's filter argument does. It works for moderate selectivity but degrades as matches get rare, because the beam fills with useless nodes. A robust engine picks a strategy per query from an estimate of selectivity:
def filtered_search(index, q, k, predicate, est_selectivity, matching_ids):
if est_selectivity < 0.01: # few matches: exact scan is cheaper
return brute_force(q, matching_ids, k)
ef = min(4096, int(64 / max(est_selectivity, 0.05))) # widen beam as filter tightens
return index.query_filtered(q, k, ef, predicate)For hard multi-tenant isolation, a separate index or partition per large tenant is both faster and safer than a filter, because a filter bug becomes a data leak. See pgvector at 100M scale for how this plays out in a relational engine.
Worked example: sizing and tuning
Worked example: a support search over 2 million 384-dimensional embeddings, target recall@10 of 0.95 at p95, latency budget 10 ms. Memory is 2M x 384 x 4 = 3.1 GB of vectors plus about 0.26 GB of layer-0 links at M = 16, so one 8 GB node is enough. Build with efConstruction = 200. Suppose the sweep on 1,000 logged queries shows p5 recall of 0.80 at ef = 32, 0.90 at ef = 64, 0.95 at ef = 128 and 0.97 at ef = 192. Choose 128, the smallest value whose p5 meets the target, confirm its latency fits the budget, and set it explicitly at query time: in hnswlib, set_ef is not saved with the index, so a reloaded index silently falls back to the default. Finally, schedule the sweep to rerun after each bulk load and each 10 percent of deletes.
Failure modes
- Recall cliff after reload: ef not persisted, defaults apply. Set it in code on every load.
- Empty filtered results: post-filtering with selective predicates. Use iterative scans, wider ef, or brute force for rare matches.
- Slow decay: tombstones accumulate. Monitor deleted fraction and rebuild.
- Wrong metric: index built with L2 on unnormalised vectors meant for cosine. Normalise or build with inner product.
- Benchmark on self-queries: recall looks perfect, production does not.
- Build stalls: high efConstruction on tens of millions of vectors with one thread. Parallelise inserts and size build time before launch.
Trade-offs
| Knob | Raise it to get | Pay with |
|---|---|---|
| M | Higher recall on hard data | Link memory, build time, slower search per hop |
| efConstruction | Better graph quality | Build time, almost no query cost |
| ef | Higher recall | Linear growth in query latency |
| Quantisation | Less memory | Recall loss unless you re-rank |
What to do next
- Run the implementation above on 100,000 of your own vectors to build intuition.
- Log 1,000 real queries and compute exact neighbours as ground truth.
- Sweep ef and pick the smallest value whose p5 recall meets target; set it explicitly in code.
- Do the memory arithmetic for your size and decide on float16 or 8-bit storage.
- Measure filtered queries separately and choose post, in-search or brute force by selectivity.
- Track deleted fraction and schedule recall sweeps and rebuilds.