HNSW Multi-Layer Skip Graph

Hierarchical Navigable Small World (HNSW) is an ANN graph index that combines the probabilistic multi-layer concept of Skip Lists with Navigable Small World (NSW) graph topology; during indexing, each inserted vector is assigned a maximum layer $l$ via exponential distribution $l = \lfloor -\ln(\text{uniform}(0, 1)) \cdot m_L \rfloor$; top layers contain sparse long-range highway edges for coarse navigation, while lower layers (Layer 0) host dense local connectivity containing all vectors, achieving logarithmic $O(\log N)$ search complexity.

Default in-memory ANN indexing engine in virtually all production vector databases (Milvus, Qdrant, Weaviate, Pgvector, Chroma) demanding 99%+ Recall.

Flat single-layer NSW graphs suffer search degradation and local minima traps as scale reaches tens of millions; HNSW multi-layer hierarchy isolates long-range highway links from dense local clusters, ensuring robust logarithmic convergence across high dimensions.

Derive the probability formula for assigning a node to layer $l$, and explain the normalization factor $m_L = 1/\ln(M)$?

Detail the two-stage greedy routing workflow from top Entry Point down to bottom Layer 0?

Why does HNSW possess both a high clustering coefficient and extremely short average path lengths?

Analyze the breakdown of HNSW memory consumption between neighbor pointer arrays and raw vector payloads?

Compare the architectural differences between HNSW and DiskANN (Vamana graph) in RAM footprint vs SSD random IO?