Hierarchical Navigable Small World (HNSW)

HNSW constructs a hierarchical graph where each layer represents a proximity graph with different connectivity radii. The bottom layer contains all data points, while higher layers contain exponentially fewer nodes, creating a skip-list-like structure that enables long-range jumps during search.

• Layer 0: Dense graph with all vectors and short-range connections
• Upper layers: Sparse graphs with long-range shortcuts
• Exponential decay: Node probability of appearing in higher layers decreases exponentially

The search algorithm performs a best-first greedy traversal from an entry point at the top layer, descending through layers until reaching the bottom. At each layer, it maintains a dynamic candidate list (beam width or ef_search parameter) of the closest neighbors found so far.

• Entry point: Fixed node at the topmost layer
• ef_search: Controls the trade-off between accuracy and speed
• Layer descent: Uses 1-greedy search on upper layers, beam search on bottom layer
• Typical ef_search values range from 16 to 512 depending on precision requirements

During construction, HNSW uses a pruning heuristic to select diverse neighbors rather than simply connecting to the closest candidates. This prevents hub formation and ensures the graph remains navigable in high-dimensional spaces.

• Pruning strategy: Discards candidates that are closer to existing neighbors than to the inserted node
• M parameter: Maximum number of outgoing connections per node (typically 16-64)
• M_max0: Double connections at the bottom layer for higher recall
• Prevents clustering collapse in dense regions of the vector space

HNSW supports online insertion of new vectors without requiring a full index rebuild. Each new element is inserted by finding its nearest neighbors at each layer and establishing bidirectional connections using the same heuristic neighbor selection.

• Insertion complexity: O(log N) on average
• No global rebalancing: Graph adapts locally to new data
• Deletion support: Mark-and-sweep or tombstone-based removal
• Enables streaming indexing for continuously updated corpora

HNSW achieves O(log N) average search complexity by leveraging the hierarchical skip-list analogy. The top-layer long-range connections rapidly narrow the search space, while the dense bottom layer provides precise nearest-neighbor resolution.

• Theoretical scaling: Sublinear with respect to dataset size
• Practical performance: Often 10-100x faster than brute-force for million-scale datasets
• Recall@1: Typically >95% with properly tuned parameters
• Outperforms tree-based methods like Annoy and clustering-based methods like IVF in high-recall regimes

HNSW stores the full graph structure in RAM, making it memory-intensive compared to compressed or disk-backed indexes. The M parameter directly controls the memory footprint: each connection stores a vector ID and distance.

• Memory formula: ~(M × N × bytes_per_id) + (N × dimension × bytes_per_float)
• M=16: ~2-4 GB for 1M 768-dimensional vectors
• M=64: Higher recall but ~4x memory increase
• Quantization: Product quantization (PQ) can compress vectors to reduce memory at the cost of some precision