Hierarchical Navigable Small World (HNSW)

HNSW builds a hierarchical graph where each layer represents a proximity graph of the stored vectors. The bottom layer contains all data points, while higher layers contain exponentially fewer points, acting as a skip list over the vector space. Search begins at the top layer, making large leaps across the space using long-range edges, then descends to lower layers for finer-grained local exploration. This structure guarantees logarithmic scaling of search complexity relative to the dataset size.

The search algorithm uses a best-first greedy traversal controlled by a dynamic candidate list, often parameterized by ef_search. Starting from an entry point, the algorithm maintains a set of nearest neighbors found so far and iteratively explores their connections. A key mechanism is the beam width, which prevents the search from collapsing to a single path by keeping a pool of promising candidates. This balances exploration and exploitation, ensuring the algorithm does not get trapped in a local minimum and can navigate around 'hubs' in the graph.

New vectors are inserted incrementally without a global rebuild. The insertion algorithm first finds the nearest neighbors for the new element using the same greedy search. Connections are then established, and a pruning heuristic is applied: a new connection is only kept if it is closer to the new element than to any of its already-connected neighbors. This maintains the graph's small-world navigability and prevents nodes from having an excessive number of edges, controlling memory usage and search cost.

An element's maximum layer is assigned randomly using an exponentially decaying probability distribution, normalized by a level multiplier parameter m_L. This ensures that the number of elements at layer l is roughly proportional to n * (1/m_L)^l. This probabilistic approach creates the hierarchical skip-list structure without complex global coordination. Elements in higher layers act as long-range shortcuts, enabling the search to skip over large volumes of irrelevant data points in constant time.

HNSW offers direct, predictable control over the accuracy-performance trade-off through its construction and search parameters:

• M: The number of bi-directional links created per element during insertion. Higher M improves recall but increases memory and index build time.
• ef_construction: The beam width during index building. A larger value creates a higher-quality graph.
• ef_search: The beam width during query time. This is the primary knob for trading latency for recall without rebuilding the index.

Unlike clustering-based ANN methods like FAISS IVF, HNSW is a fully incremental algorithm. It does not require an initial training phase on a representative sample to define cluster centroids or a Voronoi tessellation. The index is built purely from the sequential insertion of data points. This makes it exceptionally well-suited for streaming data and dynamic corpora where vectors are continuously added, as the index maintains its navigability and query performance without periodic, computationally expensive global re-indexing.

The defining architectural feature of HNSW. The graph is built with multiple layers of decreasing density, where the top layers contain few nodes with long-range edges and the bottom layer contains all nodes with short-range edges.

• Search Mechanism: A 'zoom-in' process starting at the top layer for coarse navigation and refining locally at the bottom.
• Logarithmic Complexity: This hierarchy enables O(log N) search time.
• Parameter M: Controls the maximum number of connections per node per layer, directly impacting memory and recall.

The specific pruning strategy used during HNSW construction to maintain a navigable small-world property. When inserting a node, the algorithm evaluates candidate neighbors and discards redundant connections.

• Goal: Maximize graph connectivity while minimizing average path length.
• Parameter ef_construction: Controls the beam width during the neighbor search, trading build time for index quality.
• Impact: A high-quality heuristic prevents the formation of disconnected 'islands' in the graph.