NoSQLAdvanced
How does approximate nearest neighbour trade off recall and speed?
“Explain HNSW and the knobs that trade recall for latency.”
What this tests
- ANN internals
- Recall/latency/memory tradeoff
Answers by level
Read the beginner answer first and notice what is missing.
Exact k-NN scores every vector — O(n) — fine to a few hundred thousand, hopeless at fifty million. HNSW builds a layered graph: a sparse top layer for coarse navigation, denser layers below; search enters at the top, greedily walks to the nearest node, drops a layer, repeats — O(log n) hops. It is approximate: it may miss the true nearest neighbour, with recall typically 95–99%.
Two knobs: M (edges per node — more memory, better recall) and ef_search (candidates kept during search — slower, better recall).
Green flags · Red flags
Strong green flag · Explains why approximate is acceptable for RAG.
Green flags
- Exact vs approximate
- M and ef_search knobs
- Recall is tunable and usually acceptable
Red flags
- Thinks ANN is exact
- Cannot name a single tuning knob
Follow-up questions
F1
Your recall is too low. Which knob do you turn and at what cost?
Scenario
A similarity search misses obviously relevant results ~10% of the time. What do you tune?