midReportedcurated
Explain HNSW. What do M, ef_construction and ef_search each control, and which can you change in production?
30-second answer
- HNSW is a layered proximity graph: greedy descent through sparse upper layers, then a beam search of width ef at the bottom layer.
- M is links per node, typically 16-64, buying recall at roughly M times 2 times 4 bytes per vector of link storage plus a slower build.
- ef_construction sizes the candidate list during insertion and buys graph quality; it is fixed once the index is built.
- ef_search is the only runtime knob: raise it for recall, pay latency roughly linearly until recall saturates, and keep it at or above k.
- All three buy recall with memory or latency, and none of them makes the search exact.
Likely follow-ups
Open a question to rehearse the answer.
How do you prove recall against ground truth rather than trusting a vendor benchmark?
- Sample real queries, run exact brute-force search, keep the true top-k, and compute overlap with the ANN result at the same k and filters.
- Report a curve rather than a point, so every recall number carries the ef_search and latency that produced it.
- Re-run after bulk inserts, deletes or a rebuild, because graph quality changes with no code change.
What happens to recall at a fixed ef_search as the collection doubles, and what do you re-tune?
- Recall falls, because the same beam width covers proportionally less of a larger graph and the walk has more nodes to traverse.
- Re-tune ef_search upward first, then re-check p95 and p99, and reconsider M or ef_construction only if latency no longer fits.
- Measure on ground truth at the new size, since extrapolating the old curve overstates what the index now returns.
Which of M, ef_construction and ef_search can you change on a live index, and what does each rebuild cost?
- ef_search is query-time only, so it changes immediately with no rebuild and no data movement.
- M and ef_construction are baked into the graph, so changing either means a rebuild, planned as a deployment with an alias swap and a rollback window.
- Deletes are the expensive path in HNSW, so churn argues for periodic rebuilds rather than in-place repair.
Red flags
- confuses ef_construction/ef_search
- claims exact
Concepts this tests
Tags
Source: ishwarj.com
More in RAG & retrieval pipelines
- Explain parent-child (small-to-big) retrieval. What problem does it solve and what does it cost you?
- How would you tune HNSW for 10 million vectors when the product needs p95 retrieval under 100 ms?
- IVF, HNSW, product quantisation — pick an index for 500M vectors under a hard memory budget and defend it.