Hierarchical Navigable Small World (HNSW)
HNSW stacks your vectors into layers of graphs: almost empty on top for long jumps, crowded at the bottom for close inspection, so each query skips far before it looks closely.
Why Does This Exist?
Checking every vector against your query is the honest approach, and it has a name: exact search. Say you hold vectors ( is your collection size) with numbers each ( is the embedding dimension). One query then costs on the order of operations. You will not feel that at ten thousand vectors. You will feel it at ten million, inside a chat answer that must arrive now, which is exactly where retrieval usually sits.
So production systems accept a bargain with a name too: approximate nearest neighbor (ANN) search. Skip most of the collection, still land on the right answer almost every time. The parent page spells out that bargain in approximate nearest neighbor search. What you compare still matters, so if distance feels fuzzy, read similarity metrics first. And if you have never turned text into vectors, start with embeddings.
This page covers the layered graph behind many fast searches: how a query walks it, and the two knobs that set its recall. The system around the index, with its filters, tenants, and restarts, lives in vector databases. The compression-first rival lives in IVF and product quantization.
Think of It Like This
Express highways, then local streets
You are driving to one house in a faraway city. You do not crawl street by street from your driveway. You join the interstate, skip hundreds of exits at speed, leave it near your destination, and only then crawl the local grid.
HNSW keeps the same rhythm. The top layer is the interstate: few nodes, long links, big skips. The base layer is the local grid: every vector, short links, close inspection. You enter at the top, hop toward your query, and drop down to finish on foot.
Where it stops: highways are fixed pavement, but HNSW links are rebuilt on every insert, upper layers are drawn at random, and distance means vector distance, not miles. Nothing about the drive explains the two knobs, and , and those knobs are where the real tuning happens.
How It Actually Works
Each stored item is a vector ( is the -th embedding in the collection) and your request is a query vector . Closeness is some distance , Euclidean or cosine, fixed when you build the index.
Layers, links, and the two knobs
Layer holds all vectors. Each layer above holds fewer, thinning out fast because every insert draws a random top level and most draws stay low. A node that reaches a high layer is rare, so high layers form a sparse net of long jumps over the same points.
Each node keeps up to links per layer ( is the most neighbors one node may hold on one layer). A larger connects the graph better and eats more RAM. Two more knobs finish the picture: (the candidate list size used while inserting) decides how hard the build tries to wire each newcomer well, and (the candidate list size used while querying) decides how many runners-up a query keeps. You can raise at query time without rebuilding anything. is baked in the day you build.
How a query walks down
The walk has two gears. Up high it is pure greed: stand on a node, look at its neighbors, step to the one closest to , repeat until nobody nearby beats you. Then drop to the next layer using that winner as the entry and do it again.
At the base layer the query widens into a shortlist. Keep the closest points seen so far, always expand the closest one you have not visited, and admit a newcomer only if it beats the worst name on the list. Stop when the list stops changing and return the top ( is how many neighbors you asked for). A bigger checks more runners-up, so recall climbs and latency climbs with it. That is the whole trade: recall for RAM at build time through and , recall for latency at query time through .
The method assumes your distance tracks meaning and the graph stays connected. It fails when is too small and greed gets stuck in a dead end, when the metric at query time differs from build time, or when a filter rejects most candidates so the walk starves. Skip HNSW when RAM is capped at huge scale, when answers must be exact, or when the collection churns constantly. A compressed index fits the first case and an exact scan fits the second.
Worked example: six points, one query
Take six 2D points and a query :
- , , , , ,
Rank them with squared distance, which orders the same as distance and keeps every number an integer:
- :
- :
- :
- :
- :
- :
True order: , then , then and tied, then , then . As distances that is , , , , .
Now give it HNSW layers. The top layer holds with one link between them. The base layer holds all six, chained to to to to to . Enter at up top (). Its only neighbor () wins, nothing up there beats , so descend with as entry.
At the base with , the board opens at , expands to admit () and (), expands to check () and () without changing the board, then expands and stops. Ask for and you get and . The diagram draws exactly this walk: the mint path runs to to , with and printed under the two winners.
Code
The point of this snippet is the check you should run before trusting any index: rank the fixture by hand, then confirm the order in code.
import math
def sq_dist(a: tuple[float, float], b: tuple[float, float]) -> float: return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
pts: dict[str, tuple[float, float]] = { "A": (1.0, 1.0), "B": (2.0, 3.0), "C": (4.0, 2.0), "D": (5.0, 5.0), "E": (3.0, 6.0), "F": (6.0, 1.0),}q: tuple[float, float] = (4.0, 4.0)
ranked = sorted(pts.items(), key=lambda kv: sq_dist(kv[1], q))print([(k, sq_dist(v, q)) for k, v in ranked]) # -> [('D', 2.0), ('C', 4.0), ('B', 5.0), ('E', 5.0), ('F', 13.0), ('A', 18.0)]print(round(math.sqrt(2), 2)) # -> 1.41The ranking matches the hand computation point for point: at squared distance , at , and the winner at true distance . Compare any index against this exact order on a sample before you believe its recall number.
Watch Out For
efSearch left low while recall quietly drops
Easy queries look perfect and latency looks great, so nobody touches the settings. Then harder queries and larger start missing: measured against an exact brute force check on a sample, recall sags while every dashboard stays green. It reads as a model problem, but it is an index setting.
Sweep upward at query time and plot recall against latency until the curve bends. Never lower it to fix latency without remeasuring recall. And remember the split: changes take effect at once, but a too small needs a full rebuild to fix.
Deletes pile up while RAM runs the show
HNSW lives in memory: every vector plus every link list stays resident, so the index is far bigger than the raw data. Deletes make it worse. Most engines mark deleted vectors as tombstones instead of rewiring the graph, so after heavy churn the walk keeps visiting dead nodes. Symptom: latency climbs and recall sags weeks after launch, with no config change in between.
Batch deletes, rebuild on a schedule, and spot check recall against brute force after each rebuild. If RAM is the binding constraint from day one, reach for IVF and product quantization instead of squeezing until the graph falls apart.
The Quick Version
- HNSW files every vector into stacked graph layers: sparse long links above, dense short links at the base.
- A query hops greedily to its closest neighbor up top, descends with that winner, then runs a shortlist of size efSearch at the base.
- M and efConstruction are set at build time and cost RAM; efSearch is set per query and buys recall for latency.
- The method assumes distance means relevance and the graph stays connected; tiny M, a mismatched metric, or heavy deletes break it.
- Skip HNSW when RAM is capped, answers must be exact, or churn is constant; a compressed index or an exact scan fits better there.