Hierarchical Navigable Small World (HNSW)

HNSW builds a hierarchical graph where each layer represents a proximity graph of the stored vectors. The bottom layer (layer 0) contains all data points, while higher layers contain progressively fewer points, acting as an express lane for navigation.

• Skip list analogy: The hierarchy functions like a skip list, allowing the search to make large jumps across the vector space in upper layers before descending for fine-grained local search.
• Logarithmic scaling: This structure enables search complexity of O(log N), making it highly efficient for billion-scale datasets.

The search process uses a best-first greedy algorithm that traverses the graph from an entry point, always moving to the neighbor closest to the query vector until a local minimum is found.

• Heuristic neighbor selection: During construction, HNSW uses a heuristic that prunes candidate connections to avoid clustering and ensure a diverse set of long-range edges, which is critical for maintaining the small world property.
• Ef construction parameter: This parameter controls the beam width during the neighbor selection heuristic, directly trading off index build time for search quality.

HNSW supports incremental insertion without requiring a full index rebuild, making it suitable for dynamic datasets. New vectors are inserted by finding their nearest neighbors and establishing connections.

• Layer assignment: The maximum layer for a new element is randomly assigned using an exponentially decaying probability distribution, ensuring the hierarchy remains balanced.
• No global retraining: Unlike clustering-based indices like IVF, HNSW does not require a computationally expensive global training phase, allowing for true online updates.

HNSW delivers state-of-the-art recall-speed performance but has a higher memory footprint than compressed indices.

• Memory overhead: The graph structure requires storing neighbor lists for every element across multiple layers, consuming significantly more RAM than Product Quantization (PQ) based indices.
• Ef search parameter: At query time, the ef_search parameter controls the dynamic candidate list size. A higher value increases recall but proportionally increases latency, allowing fine-grained control over the accuracy-speed trade-off.