Hierarchical Navigable Small World builds layered proximity graphs: sparse top layers for coarse navigation, dense bottom layers for precision. A query greedily descends toward its neighborhood, finding near-nearest neighbors in logarithmic hops instead of scanning every vector. The trade: excellent speed/recall, at the cost of memory and slower inserts — the default index in most vector stores.
Worked example: HNSW builds a multi-layer graph linking near neighbors; a search greedily hops toward the query and drops down layers to refine, finding approximate neighbors in ~log time instead of scanning millions of vectors. Gotcha: it trades a little recall for huge speed, and build time plus memory are significant; the ‘ef’ and ‘M’ knobs set the recall-vs-latency curve, so defaults rarely fit every workload.