How does approximate nearest-neighbor search work, and how do you choose a vector index (HNSW vs IVF)?

TL;DR: Exact nearest-neighbor search is O(N) per query and dies at millions of vectors, so production uses Approximate Nearest Neighbor (ANN) indexes that trade a little recall for large speedups. HNSW (a navigable small-world graph) gives excellent recall at low latency but costs RAM and slow builds; IVF (clustering) is memory-light and fast to build but needs tuning (nprobe) and misses neighbors near cluster boundaries. Choose by recall target, latency SLO, memory budget, and update pattern, then add quantization (PQ) when memory forces it.

How to approach it. Establish why ANN exists (exact search is linear and too slow at scale), define recall as the quality knob you are trading, then contrast the two dominant index families by their tradeoffs, and end on how you tune and measure. Skip "just use Pinecone/FAISS"; show you understand what is underneath.

A strong answer. Why approximate. Exact search compares the query against all N vectors: O(N·d) per query, fine for thousands, hopeless for tens of millions at any real QPS. ANN indexes accept a small loss in recall (the fraction of true nearest neighbors returned) for orders-of-magnitude faster search. Recall is the dial: higher recall costs more time and memory.

HNSW (Hierarchical Navigable Small World). A multi-layer graph where each node links to nearby nodes; search greedily hops toward the query, starting coarse (top layer) and refining downward. Excellent recall at low latency, the strong default for most workloads, and it supports incremental inserts. The cost is memory (it stores the graph plus the vectors) and slow, RAM-heavy builds. Tune with M (links per node) and efSearch (search breadth: higher means better recall, slower).

IVF (Inverted File). Cluster the vectors with k-means into buckets; at query time search only the nprobe nearest clusters instead of everything. Memory-efficient, fast to build, scales well. Recall depends on nprobe (probe too few clusters and you miss neighbors sitting near boundaries), and it needs a representative training step to form clusters. Often paired with Product Quantization (PQ) to compress vectors (IVF-PQ), trading some recall for large memory savings, which is how billion-scale indexes fit in RAM.

The defensible framing: pick the index by your recall target, latency SLO, memory budget, and update pattern, then quantize if memory forces it, and validate recall empirically against an exact baseline on a sample.

Key takeaways.

• ANN buys speed by trading recall; recall is the dial you tune, not a given.
• HNSW wins on recall-per-latency when RAM is available; IVF-PQ wins when you are memory-bound at scale.
• Heavy insert workloads favor HNSW; IVF clusters drift and want periodic retraining.
• Always measure recall@k against brute force on a sample, then tune efSearch/nprobe to the target.

What interviewers probe next.

• "What is recall here and how do you measure it?" Fraction of the true top-k (from exact search) that the ANN returns; measure on a sample against a brute-force baseline.
• "HNSW memory problem?" It keeps the full graph plus vectors in RAM; for huge corpora use IVF-PQ or disk-based indexes (DiskANN) instead.
• "What does Product Quantization do?" Splits vectors into subvectors and quantizes each to a codebook, shrinking memory many-fold at some recall cost.
• "Filtered search (metadata) with ANN?" Pre-filter (restrict candidates by metadata before or within the search) or post-filter with over-fetch; pre-filtering is needed for multi-tenant scoping.

Common mistakes.

• "Just use a vector DB" with no grasp of the recall/latency/memory tradeoff underneath.
• Assuming ANN returns exact results; it is approximate by design and recall must be measured.
• Picking HNSW for a memory-constrained billion-vector corpus where IVF-PQ fits.
• Not tuning efSearch/nprobe to a recall target, so the index silently under- or over-serves.