Hierarchical Navigable Small World (HNSW)

HNSW constructs a hierarchy of proximity graphs, where each layer represents a different scale of the vector space. The bottom layer (layer 0) contains all data points and captures local neighborhood relationships. Higher layers contain exponentially fewer nodes, serving as express lanes for long-range jumps. A search begins at the topmost layer, performs a greedy traversal to find the nearest entry point, then descends to the next layer. This skip-list-inspired design reduces the average path length from O(N) to O(log N).

At each layer, HNSW performs a best-first greedy search governed by a parameter called ef (exploration factor). The algorithm maintains a dynamic candidate list and a result set, iteratively evaluating unvisited neighbors of the closest candidate. A larger ef value increases search accuracy (recall) at the cost of more distance computations. This tunable parameter directly controls the ANN recall trade-off, allowing operators to dial precision up or down based on latency budgets.

New vectors are inserted by assigning them a random maximum layer using an exponentially decaying probability distribution. The level is determined by floor(-ln(uniform(0,1)) * mL), where mL is a normalization factor. This probabilistic assignment ensures that higher layers remain sparse, naturally creating the small-world navigability property. The node is then inserted into every layer from its assigned maximum down to layer 0, connecting to its M nearest neighbors at each level.

During insertion, HNSW applies a neighborhood pruning heuristic to maintain graph quality. For each candidate neighbor, the algorithm checks whether the new connection would create a redundant path. Specifically, it evaluates if the candidate is closer to an already-connected neighbor than to the inserted node. If so, the connection is skipped. This heuristic prevents hub formation and ensures the graph maintains diverse, non-redundant edges, improving both search speed and recall.

Unlike tree-based ANN methods that require periodic rebuilding, HNSW supports fully incremental insertion and deletion. New vectors can be added to a live index without degrading search performance, making it suitable for streaming data pipelines and continuously updated knowledge bases. Deletions are handled through tombstoning, where nodes are marked as removed but retained in the graph structure to preserve connectivity for existing neighbors.

HNSW's primary cost is memory overhead. Each node maintains M outgoing edges per layer, and the graph stores the full-precision vectors alongside the adjacency lists. For a dataset of size N with parameter M=16, the index can consume 2-3x the raw vector storage. This contrasts with compressed methods like Product Quantization (PQ), which reduce memory at the cost of recall. HNSW is optimal when RAM is abundant and query latency is the binding constraint.