A graph and a greedy walk
40 random points in 2 dimensions keep every walk readable. Question 0 never leaves the entry point: a local minimum.
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.
Change the code and press Run (Ctrl+Enter). Predict what will happen first, then break it on purpose and read what changes. Your edits are saved and match the lesson page.
Ready for more? This phase has 6 hands-on exercises with automatic checks.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
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).
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?
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)