Topic 3.4
HNSW by Hand
In one line
HNSW links every vector to a few near neighbours and finds the nearest vectors by walking that graph: greedy hops, a small beam (efSearch) and sparse upper layers that act as express lanes. M, efConstruction and efSearch set memory, build quality and recall.
Think of it like this
You arrive in an unfamiliar town and must find one address. You ask the first person you meet: "Of the people you know, who lives closest to this address?" You walk to that person and ask the same thing. Each hop gets you nearer. At the start you can take a long-distance coach that only stops at a few big places, then a local bus, then walk. That is the whole idea of HNSW.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Graph
- Points (vectors) joined by links to a few neighbours.
- Greedy search
- Always step to the neighbour closest to the question, and stop when none is closer.
- Local minimum
- A point closer to the question than all its neighbours, though a better point exists elsewhere.
- Layer
- One of several graphs. Higher layers hold fewer vectors and have longer jumps.
- M
- How many neighbours a new vector is linked to when inserted. More means better recall and more memory.
- efConstruction
- The beam size used while building: how many candidates the builder looks at for each new vector.
- efSearch (ef)
- The beam size used when searching: how many candidates the search keeps. The main recall-versus-speed knob.
- Entry point
- The vector where every search starts, in the top layer.
Step by step
01Step 1: link each point to its nearest neighbours
For every point, find its 3 nearest points and link them both ways. 40 points become a web of 3 to 5 links each. This is the single-layer graph that everything else improves.
02Step 2: walk greedily
Start at point 0. Compare the question with 0's neighbours and hop to the nearest one if it beats 0. Repeat. The first example prints the paths: question 1 goes 0 > 21 > 15 > 28 and finds the true nearest (28) after 19 distances. Question 2 stops at point 3 although point 8 is the true nearest.
03Step 3: keep a beam of candidates
search_layer keeps the best ef points seen and a queue of points still to explore. Always explore the closest unexplored point, and stop when it is worse than everything kept. With ef = 1 it is the greedy walk.
while candidates:
d, current = pop_closest(candidates)
if len(found) >= ef and d > worst_distance(found):
break # nothing left that could improve the result
for nb in graph[current]:
if nb in visited:
continue
visited.add(nb)
nd = dist2(query, points[nb])
if len(found) < ef or nd < worst_distance(found):
candidates.append((nd, nb))
keep_best(found, (nd, nb), ef)04Step 4: add an express lane
The second example gives 600 points a sparse upper layer (every 15th point, 40 in all). A search first walks the upper layer with ef = 1 to land near the question, then runs the beam on the bottom layer from there. The table compares it with starting from the bottom at point 0.
05Step 5: build by inserting one at a time
build inserts points in order. For each, search_layer on the graph so far (beam efConstruction) finds candidates, the closest M become its links, and any neighbour that now has more than 2 * M links drops its farthest. This keeps the degree bounded, as real implementations do.
06Step 6: turn efConstruction
The third example builds the same data four times with efConstruction 1, 3, 10 and 40 and searches each with efSearch = 10. Recall@3 rises from 0.62 to 0.79, 0.86 and 0.97 while the build computes 4,699, 7,320, 10,086 and 17,353 distances. A better-connected graph is a better road map, and it is paid for once at build time.
07Step 7: the three names to remember
M and efConstruction shape the graph and are fixed when you build. efSearch is chosen per query. In a database you will see them as m, ef_construction and ef_search, or M, efConstruction and ef. If recall is too low, raise efSearch first, because it costs nothing to try.
Try it yourself
- 1
Make greedy fail less
In the first example change
build_graph(points, 3)tobuild_graph(points, 6). How many of the 20 queries now find the true nearest, and how many distances does a query take? Which is the better buy for 40 points: more links or an exact scan? - 2
Raise efSearch
In the second example add
40to the list ofefvalues. Does recall reach 1.00 for the bottom-only column, and how many distances does that take compared with the express lane atef = 10? - 3
Remove the lane's help
In the second example change the express lane to every 60th point (10 points). Does the benefit survive? What does that suggest about how many points the upper layer should have?
- 4
Predict before building
In the third example predict whether
efConstruction = 100will beat 40 atefSearch = 10, then try. Then raiseMto 5. Which change helps recall more, and what does each cost?
Code & diagrams
40 random points in 2 dimensions keep every walk readable. Question 0 never leaves the entry point: a local minimum.
Expected output
links per point: min 3, max 5
query 0: path 0 true nearest 14 distances 4
query 1: path 0 > 21 > 15 > 28 true nearest 28 distances 19
query 2: path 0 > 29 > 30 > 24 > 25 > 3 true nearest 8 distances 23
query 3: path 0 > 21 > 15 > 28 > 17 > 13 > 38 true nearest 38 distances 30
query 4: path 0 true nearest 0 distances 4
query 5: path 0 > 21 > 15 > 28 > 17 true nearest 7 distances 23
found the true nearest for 12 of 20 queries, 17 distances per query (exact: 40)The upper layer here is every 15th point, chosen by a rule so the output is repeatable. Real HNSW assigns layers at random.
Expected output
efSearch with the express lane bottom layer only
3 recall 0.911, 28 distances recall 0.544, 35 distances
5 recall 0.933, 31 distances recall 0.556, 38 distances
10 recall 1.000, 37 distances recall 0.767, 52 distances
20 recall 1.000, 48 distances recall 0.900, 68 distancesA single layer (the bottom one) is enough to see the effect of efConstruction. Real HNSW chooses neighbours with a smarter heuristic than simply the closest.
Expected output
efConstruction= 1: 589 links, 4699 distances to build, search recall@3 0.622
efConstruction= 3: 1408 links, 7320 distances to build, search recall@3 0.794
efConstruction=10: 1432 links, 10086 distances to build, search recall@3 0.861
efConstruction=40: 1427 links, 17353 distances to build, search recall@3 0.967Not run here: it needs a PostgreSQL server with the pgvector extension. The option names and defaults (m 16, ef_construction 64, ef_search 40) are from the pgvector documentation. Topic 5.2 covers pgvector fully.
-- Build-time: m and ef_construction. Query-time: hnsw.ef_search (default 40).
CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);
SET hnsw.ef_search = 100; -- higher: better recall, slower queriesNot run here: it needs the hnswlib package. The meaning of M, ef_construction and ef follows the library's ALGO_PARAMS documentation.
import hnswlib
index = hnswlib.Index(space="cosine", dim=384)
index.init_index(max_elements=100000, M=16, ef_construction=200)
index.add_items(vectors, ids)
index.set_ef(50) # efSearch: must not be lower than k
labels, distances = index.knn_query(query_vector, k=5)Break it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Throw away what the express lane found
In the Python tab of the second example, change entry = [found[0][1]] to entry = [0].
Break #2
Link new points only one way
In the Python tab of the third example, in build, replace the line graph[nb].append(i) with pass, so a new point links to its neighbours but they do not link back.
Myth vs fact
Myth
HNSW always finds the exact nearest neighbour if the data is small.
Fact
It is still a walk that can stop early. Small data just makes the gap small. If you need exact results for a small collection, use exact search.
Myth
Raising efConstruction speeds up queries.
Fact
It makes the graph better, so a given efSearch gives higher recall, but queries are not faster by themselves. Build time and recall go up.
Myth
The upper layers store different vectors.
Fact
They store the same vectors as the bottom layer, just fewer of them. Only the bottom layer holds every vector, and each vector's data is stored once.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Memory is the HNSW bill. Besides the vectors, each element stores its links (hnswlib's guideline is about 8 to 10 bytes per element for each unit of M, on top of the vector itself). For a million 384-number vectors that is a small extra over 1.5 GB; at 1,536 numbers and tens of millions of vectors the vectors dominate and quantisation (Topic 3.5) matters more than M.
- ▸
Because the graph is built by sequential insertion, the order of insertion changes the graph, and parallel builds are non-deterministic. Two builds of the same data can differ slightly in recall, which is why you measure each build rather than trusting parameters.
- ▸
Filters and graphs do not mix well (Topic 3.7): skipping vectors that fail a filter removes the very nodes the walk needs to hop through. Modern implementations add filter-aware traversal, and some vector databases fall back to exact scans for very selective filters.
- ▸
Deletion is usually a mark (a tombstone) until a rebuild or a repair pass, because physically removing a node can disconnect others. A heavily updated collection needs a periodic rebuild (Topic 5.6).
Remember this
- 1
Why this exists. IVF (Topic 3.3) draws hard borders and loses neighbours that sit across one. A graph has no borders: from any vector you can keep moving toward the question through its neighbours. HNSW (Hierarchical Navigable Small World graphs, by Malkov and Yashunin) became the most used index for embeddings because it reaches high recall with few distance computations. The price is memory for the links and a slower build.
- 2
The graph. Link every vector to a few of its nearest vectors, in both directions. The first example does this for 40 points with 3 links each, so every point ends up with 3 to 5 links. A greedy walk starts at a fixed entry point, looks at the neighbours of the current point, moves to the one closest to the question, and stops when no neighbour is closer. For 20 questions it finds the true nearest neighbour for 12 of them with about 17 distance computations instead of 40.
- 3
Why greedy fails sometimes. The other 8 walks stopped at a local minimum: a point whose neighbours are all farther from the question than itself, although a better point exists elsewhere. Question 0 never moves from the start (4 distances), and the true nearest is point 14. One path is a very narrow search, so one unlucky turn ends it.
- 4
**Fix one: a beam,
efSearch. Instead of following one path, keep a shortlist (the beam**) of the bestefpoints seen so far. Repeatedly take the closest point not yet explored, look at its neighbours, add the good ones to the list, and stop when the closest unexplored point is already worse than everything in the list. Withef = 1this is the greedy walk. A largerefexplores more of the neighbourhood, so it escapes more dead ends, at the cost of more distance computations. This is the query-time knob:efSearchin this course,hnsw.ef_searchin pgvector (default 40) andefin hnswlib, where it must be at least k. You can change it without rebuilding the index. - 5
Fix two: layers, the "H" in HNSW. Keep several graphs. The bottom layer holds every vector. Each layer above holds a smaller random subset, so the top layers are sparse with long links, like express lanes. A search starts at the top, walks greedily, and when it can get no closer drops to the next layer from where it stopped, finally running the beam search (with
efSearch) on the bottom layer. In the second example the "express lane" is every 15th of 600 points. Withef = 10the lane gives recall 1.00 using 37 distances, against 0.77 and 52 distances starting from the bottom alone. In real HNSW each vector draws its top layer at random with exponentially fewer vectors on each higher layer, so the number of layers grows like the logarithm of the collection. - 6
Building: M and efConstruction. The graph is built by inserting vectors one at a time. For each new vector the builder searches the graph so far, with a beam of size **
efConstruction, to find its nearest candidates, links it to theM** best of them (both ways), and trims any neighbour that now has too many links, keeping the closest. In the third example, withM = 3, a beam of 1 builds a thin, poorly connected graph (589 links, recall@3 0.62 at search time), while a beam of 40 builds a much better one (recall 0.97) for about four times the build work (17,353 distances against 4,699). BiggerMmeans more links per vector, more memory and usually better recall. The hnswlib documentation recommendsMof 12 to 48 for most uses and about 8 to 10 bytes per element for each unit ofM; pgvector usesm = 16andef_construction = 64by default. TheM, the graph andefConstructionare fixed at build time: changing them means rebuilding. - 7
What it costs. The graph lives in memory next to the vectors, so memory is vectors plus links (the practice below counts about 128 MB of links for a million vectors with
M = 16). Builds are slow because every insertion is a search. Deleting a vector from a graph is awkward, because other vectors may only be reachable through it (Topic 5.6). In return, queries are fast and recall stays high, which is why HNSW is the default index of most vector databases. The paper's real algorithm is richer than the examples here: it picks neighbours with a heuristic that favours spread-out directions, not simply the closest ones, but the mechanism you built is the one that matters.
Explain it without notes
Explain greedy search on a neighbour graph and why it sometimes returns the wrong point.
What is efSearch, and what happens to recall and latency as you raise it? Why is it the first knob to try?
Why does HNSW have layers? Describe how a search uses them.
What do M and efConstruction control? Which can you change without rebuilding?
Compare IVF and HNSW: where do each lose neighbours and what does each cost?
Practice
Write greedy_walk(graph, points, query, start) for 1-D points: from start, move to the neighbour whose value is closest to query, if it is strictly closer than the current point, and return the path. Use points [0, 10, 20, 30, 40], query 33, start 0, once with a chain graph 0-1-2-3-4 and once with the link between 2 and 3 missing. Print both paths.
A graph index holds 1,000,000 vectors of 384 numbers with M = 16. As a rough estimate, count 2 x M links per vector on the bottom layer, 4 bytes per link, and 4 bytes per vector number. Print the memory of the vectors, of the links, and the total in megabytes (1 MB = 1,000,000 bytes).
Trade-offs
- ↔
Higher M: better recall, more memory and a slower build.
- ↔
Higher efConstruction: a better graph, built more slowly. It does not change memory.
- ↔
Higher efSearch: better recall and slower queries; the knob you can change at any time.
- ↔
HNSW versus IVF: HNSW usually wins on recall per distance computed; IVF wins on build time, memory and simple updates.
Done when you can
Done when you can trace a greedy walk on a small graph by hand.
Done when you can explain a local minimum and how a beam of size ef reduces it.
Done when you can explain what the layers add.
Done when you can say what M, efConstruction and efSearch each control and which need a rebuild.
Done when you can estimate an HNSW index's memory from n, dimensions and M.