Week 10 • Day 3Week 10
Day 3:Week 10, Day 3: Graph-Based ANN — Hierarchical Navigable Small World
Battle-tested daily lesson note • 100% runnable code, interview Q&A, test suite & interactive quiz
Week 10, Day 3: Graph-Based ANN — Hierarchical Navigable Small World (HNSW)
1. Why HNSW is the Industry Default for In-Memory Vector Search
Used as the primary index in Qdrant, Weaviate, Milvus, pgvector (hnsw), Lucene/Elasticsearch, and FAISS (IndexHNSWFlat) (Malkov & Yashunin, 2018).
Unlike IVF (which relies on fixed -Means centroids and suffers from boundary effects), HNSW combines two classic computer science ideas:
- Navigable Small World (
NSW) Proximity Graphs: Every vector is a node connected to its closest neighbors plus a few long-range highway edges. - Probabilistic Skip-Lists: Layers , where Layer $0P(l) = e^{-l / m_L}$:
code
Layer 2 (Express Highway — Sparse): [0] ────────────────────────► [42]
│ │
Layer 1 (Regional Roads — Medium): [0] ────────► [19] ─────────► [42] ────► [88]
│ │ │ │
Layer 0 (Local Streets — All Nodes): [0]─►[4]─►[9]─►[19]─►[27]─►[35]─►[42]─►[61]─►[88]─► ★ Query
2. The Three HNSW Hyperparameters Every Staff AI Engineer Tunes
| Parameter | Phase | Meaning & Tradeoff |
|---|---|---|
M (e.g., 16, 32, 64) | Build & RAM | Max bidirectional edges per node per layer. Higher M improves recall on high-intrinsic-dimensionality data, but linearly increases RAM overhead (~8–16 bytes x M x N) and slows graph traversal per hop. |
efConstruction (e.g., 128, 200) | Build Only | Dynamic candidate priority-queue size when inserting a new vector into the graph. Higher efConstruction builds a higher-quality graph (better recall at query time) with zero extra RAM—only slower index build time! |
efSearch (e.g., 32, 64, 128) | Query Only | Beam width (priority queue size) during Layer 0 greedy search (efSearch >= top_k). Tunable per request to trade query latency (ms) for Recall@K. |
In Simple English: How HNSW Works Like Flights + Local Trains
Think of traveling from New Delhi to a tiny bakery in Seattle:
- Layer 2 (International Express Planes): Big long-range hops jump rapidly across the globe (
Delhi -> London -> Seattle) in 2 steps! - Layer 1 (Regional Highways): Medium hops reach the right Seattle neighborhood.
- Layer 0 (Local Streets): Tiny short steps land on the exact bakery door!
HNSW builds this exact 3-layer highway map for vectors so finding the nearest match among 10 million documents takes — ~3 milliseconds! Tradeoff: storing highway links consumes ~1.5x–2x extra RAM.