A vector search round often opens with a question that sounds easy and isn’t. Your retrieval returns the wrong neighbors about 8% of the time, latency is well within budget, so what do you change? If the first answer that comes to mind is “switch embedding models” or “add more dimensions,” you’ve walked past what the interviewer is probing. They want to see that you know an approximate nearest neighbor index gives up some recall for speed by design, and that you can point at the specific parameter that moves the line.
That one idea, recall traded against latency, sits underneath most of the questions you’ll get in this round. Everything else is detail about how a particular index structure makes that trade and where it falls apart.
The recall-latency curve is the whole conversation
Recall here means the fraction of the true nearest neighbors your search actually returns. An exact flat search scans every vector and gets recall 1.0, but it pays a full linear scan per query. That’s fine for a few hundred thousand vectors and hopeless at a hundred million. Every approximate index exists to skip most of that scan, and the price is that it sometimes misses a real neighbor. Recall is always measured at a k, so recall@10 is the fraction of the true ten closest that came back in your ten. Quote a recall number without the k and it means nothing, and interviewers notice when you pin it down.
The shape of the curve matters more than the headline number. Pushing recall from 0.80 to 0.95 usually costs a modest latency bump. Going from 0.95 to 0.99 is where it turns cruel: the search has to explore far more of the structure to catch the last few stragglers, and latency can climb three to five times over that short stretch. When an interviewer asks why you wouldn’t just run at 0.99 everywhere, that’s the answer. You pay dearly for the top slice, and most retrieval-augmented generation pipelines don’t need it because a reranker downstream fixes the ordering anyway.
How HNSW actually searches
HNSW (Hierarchical Navigable Small World) is a layered graph. Every vector is a node wired to roughly M neighbors. The bottom layer holds every node densely connected, and each layer above is sparser, acting like an express lane for long jumps across the space. A query enters at the top, greedily hops toward closer nodes, then drops a layer and does it again, finishing with a careful search of the bottom layer’s neighborhood.
Three parameters run the show. M sets how many neighbors each node keeps, so a bigger M means a denser graph, better recall, and more memory. efConstruction is the size of the candidate list during the build, which controls graph quality and build time. efSearch is the candidate list at query time, and it’s the knob you turn in production: raise it and the search keeps more candidates in flight, finds more true neighbors, and takes longer. A common question is which of these you can change without rebuilding. Only efSearch. M and efConstruction are fixed once the index is built.
What HNSW is bad at is memory. It keeps every vector at full precision in RAM alongside the graph edges, so a hundred million 768-dimension float32 vectors run into the low terabytes before you count links. Bulk updates are awkward too, though single inserts are cheap, which is why HNSW wins for steady small writes when you have RAM to spare.
How IVF and product quantization change the math
IVF (inverted file) takes a different route. It runs k-means over a sample of your vectors to carve the space into nlist cells, each with a centroid. At query time it finds the nearest centroids and only searches inside nprobe of those cells. nprobe is the recall knob: probe one cell and you’re fast but likely to miss neighbors sitting just past a cell boundary; probe thirty-two and recall climbs while latency grows. That boundary problem is a favorite gotcha, and a sharp candidate raises it unprompted, because the true nearest neighbor can live in an adjacent cell you never scanned.
Product quantization is the compression layer usually bolted onto IVF. Split each vector into several subvectors and replace each one with the id of its closest entry in a small learned codebook (256 entries fits in a single byte). A 768-dimension float32 vector is 3,072 bytes raw; stored as 96 one-byte PQ codes it’s 96 bytes. That is the memory arithmetic interviewers want you to do out loud: IVF-PQ can hold a billion vectors in a few hundred gigabytes where full-precision HNSW would need several terabytes. The cost is recall, since you’re now comparing approximate distances against compressed codes, which is why teams often rerank the top candidates with exact distances at the end.
Picking an index out loud
The strong answer to “which index would you use” is never a single name. It’s a short decision that starts from corpus size, memory budget, update pattern, and whether the queries carry filters. This table is the version I’d sketch on a whiteboard.
| Index type | Relative memory for the same vectors | Recall per unit of latency | Query-time recall knob | Frequent-update cost | Best fit |
|---|---|---|---|---|---|
| Flat (exact) | Baseline: full vectors, no index overhead | Perfect recall at full linear-scan cost | None; always exact | Trivial, just append | Under ~1M vectors, or as a ground-truth baseline |
| HNSW | Highest: full vectors plus graph edges | Best of the approximate indexes in RAM | efSearch | Cheap single inserts, awkward bulk rebuilds | Low-latency search with memory to spare |
| IVF-Flat | Full vectors, cell lists instead of a graph | Good, below HNSW at the same recall | nprobe | Retrain centroids as the data drifts | Tens of millions of vectors, filtered queries |
| IVF-PQ | Lowest: 4 to 8x smaller, often far more | Lower, recovered by reranking top hits | nprobe, plus PQ code size chosen at build | Retrain centroids and the codebook | Hundreds of millions to billions on a memory budget |
In code the knobs are small and worth knowing by name, because interviewers sometimes hand you a snippet and ask what to change:
import faiss
d = 768
# HNSW: 32 neighbors per node; efSearch trades latency for recall at query time
index = faiss.IndexHNSWFlat(d, 32)
index.hnsw.efConstruction = 200
index.hnsw.efSearch = 64 # raise for higher recall and higher latency
# IVF-PQ: 4096 cells, 96-byte codes; nprobe sets how many cells get scanned
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(quantizer, d, 4096, 96, 8)
index.train(sample_vectors) # centroids and codebook learned from a sample
index.nprobe = 16 # raise for higher recall and higher latency
The filtering follow-up that separates people
Then comes the metadata filter. “Only return documents from the last thirty days for this tenant.” Now the interviewer is watching for pre-filter versus post-filter. Post-filtering runs the ANN search first and drops results that don’t match, which breaks when the filter is selective: you retrieve the top hundred, three match, and the user asked for ten. Pre-filtering restricts the candidate set before the search, but a plain HNSW graph has no idea about your filter, so its traversal loses pruning power when only a sparse subset qualifies. It wanders, and you either blow the latency budget or come back with too few results.
IVF tends to handle this more gracefully, since you can apply the predicate inside the cells you scan and widen nprobe to make up the difference. Modern engines paper over some of this with filtered-search modes that keep the graph or cell scan filter-aware, but the failure modes are what the question is really testing. If you can name why HNSW tail latency spikes under a strict filter, you’re ahead of most candidates.
Real questions from this round, phrased close to how they land:
- “You’re at 0.90 recall and need 0.97 without touching the embedding model. What do you change, and what does it cost?”
- “What’s the difference between efSearch and efConstruction, and which one can you tune on a live index?”
- “Eight hundred million vectors, a 200 GB RAM budget. Which index, and how do you win recall back?”
- “A query with a strict metadata filter returns two results when the user wanted ten. Why, and how do you fix it?”
Measuring recall when you have no ground truth
This is the question that catches people, because production traffic doesn’t arrive with labeled answers. The move is to sample real queries, run them against a flat exact index offline to get the true top-k, and compare your approximate index’s results against that set. Do it on a schedule, because recall drifts as the data distribution shifts and your centroids or graph go stale. A candidate who reaches for “we’d track it against an offline flat index on a sampled slice” has clearly shipped one of these, and that tends to be the exact signal the round was built to find.
