A billion vectors, and you need the closest few in milliseconds. You can't compare them all. HNSW builds express lanes over a proximity graph — sparse layers to cover distance fast, dense layers to home in — and a greedy hop rides them to the answer. Drop a query and watch it navigate.
Act 1 · The greedy hop
Navigate the layers
Click anywhere to drop a query. Search enters at the top layer (sparse express lanes), greedily hops to the nearest node it can see, then descends a layer and refines — until it lands on the nearest neighbors at the bottom.
click (or focus + Enter) to drop a query · then Search
The top layer holds only a few nodes, so one hop covers huge distance. Each descent adds detail. That's the skip-list idea, in space: cross the continent on the highway, find the house on the side street.
Act 2 · Approximate vs exact
Race it against brute force
Brute force compares the query to every vector — perfect, but it scans all of them. HNSW visits only a handful. Drop a query and run both: watch brute force sweep the whole field while HNSW darts to the answer.
click (or focus + Enter) to drop a query · then Race
0
Brute force · comparisons
0
HNSW · comparisons
—
Speedup
Same answer (almost always), a fraction of the work. Scale this from 200 points to a billion and the gap becomes the difference between milliseconds and minutes.
Act 3 · The dials
Recall vs speed vs memory
HNSW is approximate — it can miss the true nearest. Two dials tune it: efSearch widens how many candidates it explores (recall ↑, latency ↑), and M sets connections per node (richer graph, more memory). Move them and watch the trade — the numbers below are a teaching model of that shape, not a benchmark off a real index.
efSearch (search width)32
M (connections / node)16
—
Recall @10
—
Relative latency
—
Relative memory
Production tuning is a target game: pick a recall floor (say 95%), then find the smallest efSearch and M that clear it — because every extra point of recall past "good enough" is paid in latency and RAM.
Why a graph, and why layers
Embeddings turn meaning into geometry: similar things sit close in a high-dimensional space, so "find similar" becomes "find nearest." The exact answer means measuring distance to every vector — fine for thousands, hopeless for billions. Approximate nearest-neighbor search buys enormous speed by accepting the occasional miss.
HNSW's insight borrows from the skip list. A skip list adds express lanes over a sorted list so search skips ahead instead of stepping one-by-one. HNSW does the same in space: build a proximity graph (each node linked to its near neighbors), then stack sparse upper layers over it. Search starts at the top — few nodes, huge jumps — and greedily walks toward the query, descending a layer each time it can't get closer, refining as the graph gets denser.
The payoff
Search cost drops from O(N) to roughly O(log N). That logarithm is why the same query is milliseconds whether your index holds a million vectors or a billion — the number of nodes you visit grows only like log N, so it is an ever-smaller fraction of the index.
The knobs that matter
M — connections per node — sets graph richness: higher M means more paths to the right neighborhood (better recall) but more memory and slower builds. efConstruction controls build-time quality; efSearch controls query-time width — how many candidates the greedy search keeps in play. Bigger efSearch explores more, recovers more true neighbors, and costs more time. Tuning HNSW is choosing where on the recall-latency-memory surface you want to live.
Why it's everywhere
Nearly every vector database and library — FAISS, hnswlib, Qdrant, Weaviate, Milvus, pgvector — ships HNSW, and many make it the default, because that balance is hard to beat. When your RAG pipeline retrieves in single-digit milliseconds over millions of chunks, this graph is doing the walking.
HNSW, step by step
One graph, two procedures: insert builds it, search walks it. Here is each as numbered steps, the formula that decides how tall the graph grows, and the arithmetic for a million-vector index.
Insert and search, in order
Draw a level. A new vector gets a top layer l = floor(−ln(U) · mL), with U uniform on (0, 1] and mL = 1/ln(M). It lives on every layer from 0 to l.
Descend to it. From the entry point on the top layer, hop to whichever neighbor is closer to the new vector, and drop a layer whenever none is. Stop at layer l.
Link on each of its layers. From layer l down to 0, run a beam search that keeps efConstruction candidates, then connect the vector to M of them, picked by a heuristic that prefers neighbors in different directions over a tight clump. Layer 0 allows 2M links per node; a neighbor whose list overflows is pruned back to the limit.
Search the same way. A query descends greedily through the upper layers with one candidate. At layer 0 it keeps a list of efSearch candidates, expands the closest unexpanded one until nothing improves the list, and returns the best k.
Worked example: one million vectors, M = 16
The level formula. mL = 1/ln 16 = 0.361. A draw of U = 0.5 gives 0.25, so level 0; U = 0.01 gives 1.66, level 1; U = 0.0001 gives 3.32, level 3.
Layer sizes. Because P(l ≥ k) = M^−k, about 62,500 of the 1,000,000 vectors reach layer 1, 3,906 reach layer 2, 244 layer 3 and 15 layer 4. The chance that at least one reaches layer 5 is 61%, and layer 6 just 6%: the graph is about log16 N ≈ 5 layers tall.
Link memory. Layer 0 stores up to 2M = 32 neighbor ids of 4 bytes, 128 bytes per vector. A vector has 1/15 of an upper layer on average, each holding 16 ids, which adds about 4.3 bytes: 0.13 GB of links in total.
Against the vectors. At 768 float32 dimensions a vector is 3,072 bytes, so the vectors take 3.07 GB and the graph adds about 4%. Brute force spends 768 million multiply-adds on every query; HNSW computes distances only to the neighbors of the nodes it expands.
Tuning it in production
M = 16 is a common default (hnswlib, pgvector, Qdrant); raise it for high-dimensional data or hard recall targets, and pay in RAM and build time. Raise efSearch first, since it costs no memory, and keep it at least k. Set both by measuring recall@k against exact search on a sample of real queries, not by feel.
Watch three traps. A metadata filter applied after the graph search can leave fewer than k results, so use an engine with filtered search when filters are selective. Deletes usually just mark nodes, and heavy churn degrades the graph until you rebuild. And the graph and vectors must fit in RAM: past that, compressed indexes such as IVF-PQ or disk-based graphs take over.
Check yourself
Four questions. Navigate them like the graph.
See every answer, with the reasoning
What idea does HNSW borrow from the skip list?
Answer: Sparse upper layers as express lanes over a dense base graph — Few nodes up top for big jumps, dense nodes at the bottom for precision — skip-list logic in space.
Roughly how does HNSW search cost scale with N vectors?
Answer: O(log N) — a tiny near-constant fraction visited — The logarithm is why a million and a billion vectors both return in milliseconds.
What does raising efSearch do?
Answer: Explores more candidates → higher recall, higher latency — efSearch is the recall dial you reach for first — cheap recall before spending memory on M.
Why is HNSW called "approximate"?
Answer: It can occasionally miss the true nearest neighbor — It trades a little recall for a massive speedup — tuned to hit a recall floor like 95%.