HNSW graph search

Exact nearest-neighbour search compares the query with every vector: O(n·d). At millions of vectors that is too slow, so we use approximate nearest-neighbour (ANN) indexes.

HNSW (Hierarchical Navigable Small World) builds a multi-layer graph. Upper layers are sparse 'express lanes' with long links; the bottom layer contains every vector with short links. A search enters at the top, greedily hops to whichever neighbour is closest to the query, then drops a layer and repeats, refining as it descends. Parameters M (links per node) and ef (search breadth) trade speed, memory and recall.

IVF (inverted file) clusters vectors with k-means, then searches only the few clusters whose centroids are nearest the query (nprobe). PQ (product quantisation) compresses vectors so more fit in memory. IVF-PQ is the memory-frugal choice at very large scale.