TracksStudyAbout
Sign in
Start studying
Module 8 · Embeddings & Search Module contents
Module 8  ·  Card 14 / 17intermediate

HNSW

HNSW stands for Hierarchical Navigable Small World.

It builds a layered graph where each vector links to nearby vectors.

Upper layers are sparse and used for long jumps across the space.

Lower layers are dense and used to refine down to the true neighbours.

It is the default index in most vector databases because of its speed and recall.

Back Next
Learn in depth ↓
Module 08 · Embeddings & Search · 17 concepts
In depth  /  15 lines

HNSW, in more detail

HNSW stands for hierarchical navigable small world, and the name describes the structure.

It is the default index in most vector databases because it is fast and accurate.

It builds a graph where each vector is linked to some of its near neighbours.

Searching means walking the graph towards the query, greedily.

You move to whichever neighbour is closer, and stop when none are.

That would be slow from a bad starting point, so the graph is built in layers.

The top layer holds few nodes with long links across the whole space.

Each layer down is denser with shorter links.

A search starts at the top, crosses the space in a few hops, and descends to refine.

It is the same idea as a skip list, applied to geometry.

The small world name comes from graphs where any node reaches any other in few steps.

Two knobs matter: how many links each node keeps, and how wide the search beam is.

More links means better recall and more memory.

A wider beam means better recall and slower queries.

Its weakness is memory, since the graph itself is large, and deletion is awkward and usually handled by marking rather than removing.

Want the full technical article? Wikipedia ↗
Deep dive

What is underneath HNSW

A graph you can walk towards the answer

Every vector becomes a node connected to some of its near neighbours. A search starts anywhere and repeatedly steps to whichever neighbour is closer to the query.

greedy:v←arg⁡min⁡u∈N(v)d(q,u) while it improves\text{greedy} : v \leftarrow \arg\min_{u \in N(v)} d(q, u) \text{ while it improves}

That walk converges quickly and gets stuck in local minima, because a node's neighbours may all be further away while a much better region sits elsewhere.

layers 0…L\text{layers } 0 \dots L

The fix is hierarchy. Upper layers hold a sparse sample of the nodes with long-range links, and each layer below is denser and more local.

P(node in layer l)=e−l/mLP(\text{node in layer } l) = e^{-l / m_L}

A node's top layer is drawn from an exponential distribution, so most nodes exist only at the bottom and a few reach the top.

The search

  1. Enter at the single node in the top layer.
  2. Walk greedily in that layer until no neighbour is closer.
  3. Drop to the layer below, starting from where you stopped.
  4. Repeat, so each layer refines the previous one's answer.
  5. In the bottom layer, keep a candidate list of size ef\mathrm{ef} rather than a single best node.
O(log⁡n)O(\log n)

The upper layers cover distance in few steps and the lower layers cover detail, which gives a logarithmic expected number of hops.

efsearch\mathrm{ef}_{\mathrm{search}}

The bottom-layer beam is the one knob that matters at query time. Larger means more nodes visited, higher recall and proportionally more latency.

The build parameters

MM

Each node keeps up to MM neighbours per layer, typically 16 to 64. It is fixed at build time and it sets both the memory and the connectivity.

memory≈n(d⋅4+M⋅2⋅4) bytes\text{memory} \approx n \big( d \cdot 4 + M \cdot 2 \cdot 4 \big) \text{ bytes}

A million 768-dimensional float vectors with M=32M = 32 is about 3 GB of vectors and 250 MB of graph, and all of it has to be in RAM.

efconstruction\mathrm{ef}_{\mathrm{construction}}

During insertion the same beam search finds each new node's neighbours. A larger value builds a better graph slowly and does not affect query speed at all.

Why the neighbour selection is not simply the nearest

Linking each node to its MM closest neighbours produces clusters that are densely connected inside and barely connected to each other.

The heuristic instead keeps a neighbour only if it is closer to the node than to any already-selected neighbour, which deliberately preserves some long links.

Those links are what let the walk cross between clusters, and without them recall collapses on clustered data even though the graph looks well built.

What it costs to operate

Deletes are soft.

Removing a node would break the paths that run through it, so deletions are marked rather than applied, and the graph is periodically rebuilt.

Building is expensive, roughly O(nlog⁡n)O(n \log n) distance computations with a large constant, and it cannot be meaningfully parallelised across machines.

That is the summary of HNSW: the fastest recall per millisecond available, in exchange for holding everything in memory and rebuilding when the corpus changes shape.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1
What does HNSW build to make search fast?
Concepts these five lines lean on
Vectors · Data ScienceRecall
Embeddings & Search

17 concepts in this module, then a graded test with every answer explained.

Study this module →
↑↓ move↵ openesc close