ANN indexing: HNSW and IVF
Two ideas. IVF clusters the vectors and searches only the nearest few clusters. HNSW builds a layered graph — sparse at the top for long hops, dense at the bottom for precision — and walks greedily downwards. Both skip most of the corpus; they differ in how they choose what to skip.
Overview
HNSW: skip lists, in vector space
Take a proximity graph — each vector linked to its nearest neighbours — and stack several, each a random sample of the one below. Search enters at the sparse top layer and greedily moves to whichever neighbour is closer to the query, until no neighbour improves. Then it drops a layer and repeats.
The top layers have long edges, so a few hops cross most of the space; the bottom layer has short edges, so the final steps are precise. It is the skip-list idea applied to geometry, and it is the reason HNSW dominates: excellent recall at low latency.
Parameters
Visualisation
—Readout
What to watch
- The top layer covers distance; the bottom layer covers precision.
- Search is greedy — it can settle in a local minimum and miss.
efSearchwidens the beam: better recall, more time.
ANN indexing: HNSW and IVF: A Practical Guide
How does approximate nearest neighbour search actually work? Explain HNSW.
The parameters worth naming
M — edges per node, fixed at build time. Higher means a better-connected graph, better recall, more memory. The graph itself is a real memory cost on top of the vectors, which is HNSW's main drawback.
efConstruction — how hard the builder works to find good neighbours. Build-time only: slower indexing, better graph forever.
efSearch — the size of the candidate list during a query. The runtime knob: raise it for recall, lower it for latency, per query if you like. This is the one to mention, because it is the one you actually tune in production.
How each one fails
HNSW's search is greedy, so it can settle in a local minimum and return a neighbourhood that is good but not the best. A wider efSearch makes that less likely without eliminating it. Deletion is also awkward — removing a node can disconnect the graph — so most implementations tombstone and rebuild periodically.
IVF's failure is cleaner: a true neighbour sitting just across a cluster boundary is missed unless that cluster is probed. More probes fixes it and costs latency. IVF is cheaper to build and to update, which is why it survives alongside HNSW — and combined with product quantization it is what runs when memory, not latency, is the binding constraint.
Things to try
- Sweep efSearch from 8 to 512. Recall and latency both climb — this is the knob you tune in production, and it can differ per query.
- Drop M to 4. Recall is capped no matter how large efSearch gets: build-time damage cannot be repaired at query time.
- Raise M to 48 and watch the index memory. The graph is stored alongside the vectors, which is HNSW's main cost.
What to remember
HNSW stacks proximity graphs: sparse upper layers with long edges to cross the space, a dense bottom layer to refine. Search is greedy with a candidate list of width efSearch, which is the runtime recall/latency knob. M and efConstruction are fixed at build time. IVF is the simpler alternative — cluster then probe — cheaper to build and update, and it misses neighbours across cluster boundaries.