Beam search and an express lane
The upper layer here is every 15th point, chosen by a rule so the output is repeatable. Real HNSW assigns layers at random.
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
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 distances