Six Degrees of Separation
Think about how you'd find a specific person in a city of ten million people. You wouldn't knock on every door. Instead, you'd ask someone you know, who knows someone closer to your target, who knows someone even closer — and within a handful of hops, you'd arrive. This is the intuition behind HNSW (Hierarchical Navigable Small World), the most widely used ANN algorithm in production today.
HNSW is built on the mathematical observation that certain graph structures — called "small world" graphs — allow you to reach any node from any other node in a logarithmically small number of hops, even in graphs with millions of nodes. The algorithm constructs exactly this kind of graph over your vector dataset, then navigates it at query time.
The Multi-Layer Graph Structure
HNSW builds a layered skip-list graph. Think of it like a city's transportation network: at the top, you have express highways connecting distant hubs; at the bottom, you have local streets connecting every building.
Construction works as follows:
- Layer 0 (Ground Level): Every single vector in the database lives here. Each node is connected to its nearest neighbors via bidirectional edges. This layer is dense — a typical node might have 16 to 64 neighbors.
- Layer 1: A randomly selected subset of vectors (roughly 1/e ≈ 37% of Layer 0). Connections here span longer distances.
- Layer 2 and above: Progressively sparser subsets. The top layer might contain only a handful of nodes with very long-range connections.
When a new vector is inserted, it is assigned a random maximum layer (with exponentially decreasing probability of reaching higher layers). The algorithm then finds its nearest neighbors at each layer from the top down and wires it into the graph.
Key parameters:
- M: The number of bidirectional edges per node (typically 16–64). Higher M = better recall, more memory.
- ef_construction: The size of the dynamic candidate list during index build. Higher = better quality graph, slower build.
- ef_search (or ef): The candidate list size during query time. Higher = better recall, slower queries. This is the primary runtime tuning knob.
The Search: Greedy Descent
When a query vector arrives:
- Enter at the top layer. Start at a fixed entry point node.
- Greedy traversal. At each layer, move to whichever neighbor is closest to the query vector. Keep moving until no neighbor is closer than your current position (local minimum).
- Drop down. Descend to the next layer at your current position.
- Repeat. Each layer provides a better starting point for the next, denser layer.
- Ground-level refinement. At Layer 0, perform a beam search (keeping the top
efcandidates) to find the final K nearest neighbors.
Pros and Cons:
| Dimension | Detail |
|---|---|
| Query Speed | Sub-millisecond for datasets up to ~100M vectors |
| Recall | Highest of any ANN algorithm (tunable via ef) |
| Build Time | Moderate; fully incremental (no retraining needed) |
| Memory | High — raw float32 vectors + graph edges. A 10M vector index at M=16 can consume 20–40 GB RAM |
| Deletions | Soft-delete only; graph must be periodically rebuilt to reclaim space |
Interviewers frequently ask: "Why does HNSW use multiple layers instead of just one dense graph?" The answer is search complexity. A single-layer graph requires O(N) traversal in the worst case. The hierarchical structure reduces search complexity to O(log N) by using upper layers as a coarse navigation mechanism — similar to how a skip list improves on a linked list. Follow-up: "What happens if ef_search is set too low?" Answer: recall degrades because the beam search terminates before finding true nearest neighbors, returning approximate results that are further from the query than necessary.
Senior depth — failure modes: HNSW's Achilles' heel is memory. At one billion vectors with 1,536 float32 dimensions, raw storage alone is ~6 TB. The graph edges add another 20–40% overhead. This is why pure HNSW is rarely used beyond ~100M vectors without compression. Additionally, HNSW does not support efficient updates — deleted vectors leave "ghost" nodes in the graph that degrade recall over time. Production systems must schedule periodic index rebuilds or use a hybrid approach with a separate deletion bitmap.