Hierarchical Navigable Small World (HNSW)

Search in HNSW uses a greedy, best-first traversal algorithm. Starting from an entry point at the top layer, the algorithm moves to the neighbor closest to the query vector. It repeats this locally optimal step until it cannot find a closer neighbor, reaching a local minimum. To escape poor local minima, the search employs a dynamic candidate list (often managed via a priority queue) that explores multiple promising paths simultaneously, effectively providing soft restarts within the search process.

A core tunable parameter, M, defines the maximum number of bidirectional connections each node can have. A higher M value creates a denser, more interconnected graph, which can improve recall at the cost of higher memory usage and slower traversal. A lower M creates a sparser graph, speeding up search but potentially reducing accuracy. The optimal M is typically between 12 and 48, determined empirically based on the dataset's dimensionality and desired recall/throughput trade-off.

HNSW supports dynamic insertion of new vectors without requiring a full index rebuild. The insertion algorithm:

• Determines the maximum layer for the new node using a random decay probability.
• For each layer from the determined level down to zero, it finds the M nearest neighbors and creates bidirectional connections.
• Prunes connections if a node exceeds its M limit, typically by removing the longest edges. This allows the index to be updated incrementally, making it suitable for real-time applications where data is continuously added.

HNSW is renowned for achieving high recall (often over 95-99%) at very low latencies. Its time complexity is approximately O(log N) for search, where N is the number of indexed vectors. This sub-linear scaling makes it exceptionally efficient for billion-scale datasets. In benchmarks, HNSW frequently outperforms other ANN algorithms like Inverted File (IVF) and Product Quantization (PQ) in the recall-versus-speed trade-off, especially when high accuracy is critical, such as in retrieval-augmented generation (RAG) pipelines.

Product Quantization is a compression technique for high-dimensional vectors that enables billion-scale searches in memory-constrained environments. It works by splitting a vector into subvectors, quantizing each subspace independently into a codebook, and representing the original vector by a short code.

• Memory Efficiency: Can reduce vector storage by 10-50x (e.g., from 512 floats to 64 bytes).
• Asymmetric Computation: During search, the query vector is compared directly to the codebooks, avoiding reconstruction of the compressed database vectors. PQ is often used as a second-level compression within an IVF or HNSW index.

The Small World property describes a graph where most nodes can be reached from every other node in a small number of hops, despite low average edge density. This is the foundational network topology that HNSW exploits.

• Real-world analogy: The "six degrees of separation" concept in social networks.
• Algorithmic Impact: By constructing a navigable small world graph, HNSW ensures that a greedy search starting from a fixed entry point can find any node's neighborhood in approximately O(log n) steps. The hierarchical layers in HNSW create increasingly smaller "worlds" for faster long-range navigation.

A Malkov Chain is a stochastic model describing a sequence of possible events where the probability of each event depends only on the state attained in the previous event. The Navigable Small World (NSW) graph, the direct predecessor to HNSW, is constructed using a model inspired by Malkov chains.

• Relation to HNSW: The NSW insertion algorithm connects a new node to its nearest neighbors from a randomly walked search, inherently creating a graph with the small-world property. HNSW improves upon NSW by adding the hierarchical structure, which guarantees logarithmic search complexity.