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 KK-Means centroids and suffers from boundary effects), HNSW combines two classic computer science ideas:

  1. Navigable Small World (NSW) Proximity Graphs: Every vector is a node connected to its closest neighbors plus a few long-range highway edges.
  2. Probabilistic Skip-Lists: Layers Lmax⁡…0L_{\max} \dots 0, where Layer $0contains∗∗100contains **100% of nodes**, and each node is promoted to higher layers with exponentially decaying probabilityP(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

ParameterPhaseMeaning & Tradeoff
M (e.g., 16, 32, 64)Build & RAMMax 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 OnlyDynamic 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 OnlyBeam 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 O(log⁡N)O(\log N) — ~3 milliseconds! Tradeoff: storing highway links consumes ~1.5x–2x extra RAM.