HNSW (Hierarchical Navigable Small World) — AI Glossary

Reference details

Related terms

• Vector Database
• Embedding

How it works

1. Vectors are inserted into a multi-layer proximity graph, with each node linked to a bounded number of near neighbours set by M.
2. Upper layers are sparse and act as express lanes; lower layers are dense, with every vector present at the bottom.
3. Search enters at the top, greedily walks toward the query, then descends a layer and repeats — so the hop count grows logarithmically with corpus size rather than linearly.
4. ef_construction controls how hard the index works to find good neighbours at build time, trading build duration for later recall.
5. ef at query time controls how many candidates are kept during the walk, which is the knob that trades latency against recall without rebuilding.

Example: Why the graph costs memory, not just time

At M = 16, each node keeps up to 16 neighbour links at the base layer and about half that in upper layers, so roughly 24 links per node in total. At 4 bytes per identifier that is about 96 bytes of graph per vector. For 10 million 768-dimensional float32 vectors the data itself is 10e6 x 768 x 4 ≈ 30.7GB, and the graph adds about 0.96GB — a few percent. Raise M to 64 and the graph approaches 4GB, which buys recall and is the memory cost the parameter actually controls.

Commonly confused with

One approximate-nearest-neighbour index family among several. Against IVF, the difference is the failure mode as much as the speed: IVF partitions and can miss a neighbour in an unprobed cell, whereas a graph walk can end in a local minimum. HNSW generally gives better recall at a given latency and costs more memory for the graph, which is the trade to measure on your own data.

When to use it

Reach for it when:

• Approximate nearest-neighbour search is needed with high recall at low latency.
• Memory is available for the graph structure on top of the vectors.
• Query-time recall must be tunable without rebuilding the index.

Reach for something else when:

• Memory is the binding constraint, where a partitioning or compressed index fits more vectors.
• The corpus is small enough for exact search, which avoids approximation entirely.
• Writes are heavy and constant, where graph maintenance costs more than a rebuildable index.

Continue your research

Use these connected ModelRefs sections to compare alternatives, inspect implementation paths, and review the evidence and governance boundaries relevant to HNSW (Hierarchical Navigable Small World) — AI Glossary.

• Browse models
• Review providers
• Inspect benchmarks
• Explore workflows
• Learn AI concepts
• Read decision guides
• Review trust and methodology
• Start a decision path