How does Approximate Nearest Neighbor (ANN) search work?

In this question, we will learn how Approximate Nearest Neighbor (ANN) search works at a systems level and how to explain its components to an interviewer. We will keep the math light but precise, and walk through a concrete example you can talk through in an interview.

We will cover the following:

• The high level idea
• The intuition
• How it actually works with a worked example
• Comparison of common ANN methods
• Tradeoffs and failure modes

Direct answer: ANN search speeds up similarity queries by organizing vectors into data structures that let the system inspect a tiny fraction of items while still finding near-neighbors with high probability. Graph indexes, partitioning plus quantization, and hashing are the main approaches; choose based on dataset size, dimensionality, latency targets, and memory constraints.

The intuition (an analogy that makes it click)

Imagine a library where books are not ordered by title but by themes. Exact search would read every book to find relevant pages. ANN is like grouping books into themed shelves, making a quick guess which shelves are likely to contain the answer, and then scanning only those shelves. You might miss a marginally relevant book, but you find most good matches much faster.

Graph based indexes like HNSW are like creating a neighborhood map between books: each book links to similar books so you can walk toward relevance. Inverted plus quantization is like coarse shelving followed by skimming condensed summaries.

How it actually works (the real mechanics)

We measure similarity with a distance or similarity function, for example Euclidean distance. The squared euclidean distance between vectors $x$ and $y$ in $d$ dimensions is

$\|x-y\|_2^2 = \sum_{i=1}^d (x_i - y_i)^2.$

Exact brute force checks all $n$ vectors with cost $O(nd)$ per query. ANN builds structures so query cost becomes roughly $O(\log n)$ to $O(\text{polylog } n)$ or depends on number of inspected candidates, not $n$ directly.

A small worked example. Suppose we have 10,000 vectors in 64 dimensions and we want top-5 nearest neighbors for a query. We compare three common choices:

Concrete steps for IVF+PQ with our 10k example:

1. Learn $k$ centroids for coarse quantizer, say $k=256$. Assign each vector to nearest centroid. This reduces candidate set to vectors in a few centroids.
2. Compress vectors in each partition using product quantization with $m$ subspaces and codebooks to shrink memory.
3. At query time, find nearest centroids, scan their compressed codes, compute approximate distances quickly, and optionally re-rank top candidates with full-precision vectors.

If we choose $k=256$ and probe $p=4$ centroids, expected candidate count is roughly $\frac{n}{k}p = \frac{10{,}000}{256}\cdot 4 \approx 156$ candidates, not 10,000.

Common methods and when they shine

HNSW (hierarchical navigable small world): build a multi-layer graph where long-range links at higher levels get you close fast and lower levels refine. Very high recall and low latency for many settings. Memory overhead is higher due to neighbor lists.

IVF+PQ (inverted file plus product quantization): great when memory is limited and you want to store vectors compressed on disk. It gives strong throughput at some recall loss and is standard for billion-scale systems.

LSH (locality sensitive hashing): uses random projections or hashing so similar items often collide. Good for theoretical guarantees and some specific distance metrics like cosine, but less competitive than HNSW in real retrieval tasks.

Practical considerations for deployment

• Build time versus query time. Graph methods take longer to build and tune but give excellent run-time latency. IVF+PQ builds faster and compresses storage.
• Dynamic updates. HNSW supports inserts reasonably well but deletes are more complex. IVF and PQ are simpler for batch updates.
• Re-ranking. Many systems do ANN to get candidates then compute exact distances on full vectors for the top-$k$ to improve precision.

Tradeoffs and failure modes

Other failure modes: very high dimensional noise, extremely skewed distributions, or using PQ with too few bits produce quantization error that harms nearest-neighbor quality.

Questions the interviewer might ask

Some follow-up questions you might get:

How does HNSW search work at query time? You start at a top-level entry point, greedily walk edges by moving to neighbors that reduce distance to the query, then descend levels to refine the search and inspect a limited candidate set at the bottom layer.

What does product quantization do? PQ splits vectors into $m$ sub-vectors and quantizes each subspace with a small codebook. Distances can be approximated by precomputed lookup tables, giving fast and compact storage.

How do you measure ANN quality? Common metrics are recall at $k$ and queries per second under a latency target. You can also use mean reciprocal rank or precision at $k$ depending on the application.

When would you choose IVF+PQ over HNSW? When memory footprint or disk storage is the limiting factor and you accept some accuracy loss for much lower storage and faster throughput at large scale.

How do you tune ANN for higher recall? Increase candidate pool size, probe more partitions for IVF, increase efSearch for HNSW, or allocate more bits to PQ. Each increases latency and memory.

What are the costs of maintaining an ANN index? Costs include build time, memory for index structures, and complexity for supporting inserts and deletes. Evaluate tradeoffs with expected update load.

Some things to note:

• Always measure recall on realistic queries, not only synthetic tests.
• Use re-ranking with exact distances when correctness matters for the top results.
• Monitor for dataset drift that can break index assumptions.

What the interviewer is really testing

They want to see that you understand the tradeoffs between accuracy, latency, memory, and build/update complexity. They also expect you to know typical ANN techniques, how to tune them, and how to reason about failure modes and monitoring strategies in a production vector-db system.