HNSW (Hierarchical Navigable Small World)

HNSW constructs a multi-layered graph where each layer represents a subset of the data with exponentially decreasing density. The bottom layer (layer 0) contains all data points, while higher layers contain fewer points, acting as a skip list for the vector space.

• Layer assignment: A point's maximum layer is randomly assigned using an exponentially decaying probability distribution
• Skip-list analogy: Higher layers enable long-range jumps, quickly navigating to the local neighborhood of a query
• Logarithmic scaling: The hierarchy ensures the average path length scales logarithmically with the dataset size

Search in HNSW relies on a simple, memory-efficient greedy traversal. Starting from a fixed entry point at the top layer, the algorithm iteratively moves to the neighbor closest to the query vector until a local minimum is reached.

• 1-greedy routing: At each step, the algorithm evaluates all neighbors of the current node and moves to the one with the smallest distance to the query
• Local minimum stop: The search halts when no neighbor is closer to the query than the current node
• Ef parameter: The size of the dynamic candidate list (efSearch) controls the trade-off between search accuracy and speed, expanding the scope of the greedy exploration

HNSW supports fully dynamic indexing, allowing vectors to be inserted, deleted, or updated without requiring a costly global rebuild of the entire index structure.

• Insertion process: A new point is inserted by first finding its nearest neighbors using the search algorithm, then establishing bidirectional connections to them
• Local connectivity: The algorithm only modifies the graph neighborhood around the new point, leaving the rest of the structure intact
• Deletion support: Points can be marked as deleted and are skipped during search, with full graph repair handled by a background compaction process

To maintain efficient routing and prevent pathologically dense connections, HNSW applies a heuristic neighbor selection strategy that prunes redundant edges during construction.

• Diversity heuristic: When adding a connection, the algorithm prunes neighbors that are closer to the newly added neighbor than to the current node, ensuring diverse directional coverage
• Maximum connections: A parameter M limits the number of outgoing edges per node, keeping the graph sparse and memory usage bounded
• Small-world property: The pruned connections maintain the small-world navigability, ensuring any two nodes can be reached in a small number of hops

The defining performance characteristic of HNSW is its O(log N) scaling for both search and insertion operations, making it suitable for billion-scale vector datasets.

• Search complexity: The hierarchical skip-list structure reduces the average number of distance computations to logarithmic scale relative to the total number of elements
• Empirical performance: Benchmarks consistently show HNSW achieving the highest query-per-second throughput among graph-based ANN algorithms while maintaining high recall
• Memory trade-off: The graph structure requires storing all vectors and their connections in RAM, making it a memory-resident index optimized for speed