What Is HNSW? – Definition and How It Works

Informational P2 what is hnsw

Learn how HNSW builds a navigable graph for approximate nearest-neighbour search, and what M and ef actually control.

HNSW — Hierarchical Navigable Small World — is the index structure most vector databases use for approximate nearest-neighbour search. It trades exactness for speed, and the trade is tunable.

1. Why Approximate at All

Exact nearest-neighbour search compares the query against every vector. At a million vectors that is a million distance computations per query, which is fine offline and far too slow for interactive search.

HNSW answers in logarithmic-ish time by searching a graph instead of a list, at the cost of occasionally missing a true nearest neighbour.

2. The Structure

A multi-layer graph, where each layer is a navigable network of vectors:

The top layer is sparse — few nodes, long-range links.
Lower layers get progressively denser.
The bottom layer contains every vector.

A search enters at the top, greedily walks toward the query, then descends a layer and repeats. Long hops at the top cover distance quickly; short hops at the bottom refine.

The analogy that makes it click: skimming a country-level map to find the right region, then a city map, then a street map — each layer narrowing the search cheaply.

3. The Parameters That Matter

Parameter	Controls	Effect of raising it
`M`	Links per node	Better recall, more memory, slower build
`ef_construction`	Candidate list size while building	Better graph quality, slower build
`ef_search`	Candidate list size at query time	Better recall, slower queries

The critical distinction: M and ef_construction are build-time and fixed once the index exists. ef_search is query-time and can be changed per request.

So ef_search is the dial to reach for when recall is too low — it needs no reindexing. If raising it to a large value still gives poor recall, the graph itself was built too cheaply and needs rebuilding with higher M.

4. Recall Is Measurable — Measure It

"Approximate" is not an excuse for unknown quality. Recall against exact search is directly testable:

def recall_at_k(index, exact, queries, k=10):
    hits = 0
    for q in queries:
        approx = set(index.search(q, k))
        truth  = set(exact.search(q, k))       # brute force on a sample
        hits += len(approx & truth)
    return hits / (len(queries) * k)

Run it on a sample against brute force. A pipeline shipping ANN search without ever measuring recall does not know what it is returning — and the failure is silent, because approximate results always look plausible.

5. Memory Is the Real Constraint

HNSW keeps the graph in memory. Cost scales with vector count, dimensions, and M.

Rough shape: the vectors themselves are count × dims × 4 bytes for float32, and the graph adds links proportional to count × M. A million 1536-dimension vectors is around 6 GB for the raw vectors alone, before the graph.

Practical levers: reduce dimensions (many models offer shortened variants), quantise to int8 or binary, or shard across nodes.

6. HNSW Versus Other Indexes

Index	Character
Flat (brute force)	Exact, slow, no memory overhead beyond vectors
HNSW	Fast, high recall, memory-hungry, slow to build
IVF	Cheaper memory, needs training, recall depends on probes
Product quantisation	Very compact, lossy
DiskANN	Disk-resident, for datasets exceeding RAM

For collections up to a few hundred thousand vectors, flat brute force is often the right answer — it is exact, trivially simple, and fast enough. HNSW earns its complexity at scale, not before.

7. Deletions Are the Weak Spot

HNSW handles insertions well and deletions poorly. Most implementations mark deleted nodes as tombstones rather than removing them from the graph, so a heavily churned index accumulates dead nodes that degrade both memory use and recall.

For a corpus that changes constantly — recrawled pages, expiring listings — plan on periodic full rebuilds rather than assuming incremental updates hold quality indefinitely.

8. Summary

HNSW is a hierarchical navigable graph giving fast approximate nearest-neighbour search, tuned by M and ef_construction at build time and ef_search at query time.

Raise ef_search first when recall is low since it needs no rebuild, measure recall against brute force rather than trusting "approximate", expect memory to be the binding constraint, and plan periodic rebuilds because deletions only tombstone — and for a few hundred thousand vectors, exact search is often simpler and fast enough.