Vector DB & ANN · advanced
HNSW
Hierarchical Navigable Small World graphs — the dominant ANN index.
Mental model
HNSW builds a layered proximity graph: sparse upper layers for long hops, dense lower layers for fine search. A query greedily walks toward the nearest neighbour, descending layers, so it touches a small neighbourhood instead of the whole set. Malkov & Yashunin report polylogarithmic search cost empirically — it is a measured scaling, not a proven bound.
How to study HNSW
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Efficient and robust ANN using HNSW graphs (Malkov & Yashunin) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare HNSW with IVF (Inverted File), Recall / Latency Tradeoffs. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Explain HNSW search on paper and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Default index in Qdrant, Weaviate, pgvector, Lucene/Elasticsearch kNN.
Common mistakes
- Tuning efSearch/efConstruction blindly without a recall curve
- Ignoring that HNSW is memory-hungry and hard to update/delete
- Expecting exact results — it is approximate by design
Learn from primary sources
Practice and explain it back
Explain HNSW search on paper
Draw a 3-layer HNSW graph and trace a query: which layer it enters, how it greedily hops, when it descends, and where efSearch widens the search.
Expected evidence: A diagram + walkthrough showing O(log n) traversal instead of O(n) scan.
Open the interactive drill →Review prompts
- What do the layers in an HNSW graph do?
- What does the efSearch parameter trade off in HNSW?
Build evidence
Recall / latency benchmark dashboard
Plot recall vs latency for ANN parameter sweeps against the brute-force baseline.
- Brute force used as the recall=1.0 ground truth
- Sweep at least one ANN parameter
- Produce a recall-vs-latency curve