ANN & HNSW

Three parameters govern behavior. M is the maximum neighbors per node: higher M improves recall and connectivity but costs memory and slows build and search. efConstruction is the candidate-list size during insertion: larger values build a higher-quality graph (a higher recall ceiling) but take longer. efSearch is the candidate-list size at query time: larger values explore more of the graph, raising recall while adding latency. efSearch must be at least $k$.

IVF and product quantization

IVF (inverted file) takes the opposite approach: partition instead of connect. A k-means pass over a training sample produces nlist centroids that carve the space into Voronoi cells, and every vector is filed under its nearest centroid. At query time you measure the query against the centroids and scan only the nprobe closest cells. Small nprobe is fast but risks missing a true neighbor that fell just across a cell boundary; large nprobe approaches an exhaustive scan.

IVF is frequently paired with product quantization (PQ) to shrink memory. PQ splits each vector into $m$ subvectors and replaces each with the nearest entry from a small learned codebook (commonly 256 entries, one byte each). A vector that was thousands of bytes becomes $m$ bytes, and distances are approximated from precomputed lookup tables. IVF-PQ is the classic recipe for billion-scale search on limited RAM, at the cost of accuracy lost to compression.

The tradeoff triangle

Every ANN index balances three quantities that pull against one another: recall, latency, and memory. You can usually improve any two by sacrificing the third. Turning up efSearch or nprobe buys recall with latency. Quantization buys memory with recall. Raising M or efConstruction buys recall with memory and build time. No single setting maximizes all three, which is why tuning is workload-specific.

Crucially, recall is measured against exact k-NN. Recall@k is the fraction of the true top-k neighbors, as returned by a brute-force exact search, that your index actually retrieves. Without that exact baseline you cannot tell whether an index returns good results or quietly drops half of them.

Tracing an HNSW query

The core loop at each layer is simple:

1. 1Enter at the topSearch begins at a fixed entry node in the sparsest layer, where long-range links let it jump across the space cheaply.
2. 2Greedy hopFrom the current node, evaluate its neighbors and move to whichever is closest to the query. Repeat until no neighbor is closer than where you stand.
3. 3Descend a layerUse that local best as the entry point for the next, denser layer, and greedily hop again to refine the position.
4. 4Finish at layer 0At the bottom layer, run a wider search of breadth efSearch and return the best k candidates found.

Picture a tiny bottom-layer graph where lower numbers mean closer to the query $q$. You enter at node A (distance 0.9). A links to B (0.6) and C (0.7), so you hop to B. B links to D (0.3) and C (0.7), so you hop to D. D's neighbors are F (0.35) and B (0.6), neither beats 0.3, so greedy search stops and returns D. But the true nearest is G (0.2), reachable only through F, which looked slightly worse than D. D is a local optimum.

This is exactly what efSearch fixes. With efSearch = 1 the search keeps only its single best candidate and commits to D. Raising it keeps a priority queue of the best efSearch candidates, so F (0.35) stays on the frontier, its neighbor G (0.2) gets evaluated, and recall improves, paid for by the extra distance computations that widen latency.

The numbers are illustrative, not a benchmark, but the trend is universal: recall rises with diminishing returns while latency keeps climbing. You tune efSearch to hit a recall target, then stop.

HNSW vs IVF at a glance

Further reading

• Malkov & Yashunin, Efficient and robust ANN search using Hierarchical Navigable Small World graphs
• FAISS wiki, index types, IVF, and product quantization
• Qdrant, indexing concepts and HNSW tuning
• pgvector, HNSW and IVFFlat index options