Hierarchical Navigable Small World (HNSW)

HNSW constructs a hierarchical graph where each layer is a proximity graph. The bottom layer (layer 0) contains all data points, while higher layers contain exponentially fewer points, acting as a skip list over the graph. This structure enables logarithmic search complexity by allowing the algorithm to make long-range jumps at higher layers before descending for fine-grained local search.

The search algorithm uses a best-first greedy traversal parameterized by ef_search (beam width). At each step, the algorithm maintains a dynamic candidate list of the closest neighbors found so far and explores their connections. A larger ef_search value increases recall at the cost of latency. The search starts from a fixed entry point at the top layer and descends layer by layer, using the nearest neighbor from the previous layer as the entry point for the next.

During construction, HNSW uses a pruning heuristic to select a diverse set of M neighbors for each inserted element. Rather than simply connecting to the nearest candidates, the heuristic evaluates whether a candidate is closer to the new element than to any already-selected neighbor. This prevents hub formation and ensures the graph maintains small-world navigability by prioritizing connections that reduce path lengths across the space.

Each inserted element is assigned a maximum layer l using an exponentially decaying probability distribution controlled by the mult parameter. The probability of an element reaching layer l is proportional to 1 / mult^l. This creates a natural hierarchy where higher layers contain fewer, more distant nodes that serve as highway intersections for rapid traversal, while the dense bottom layer preserves recall accuracy.

HNSW supports online insertion of new vectors without requiring a full index rebuild. Each new element is inserted by first finding its ef_construction nearest neighbors at its assigned layer, then applying the neighbor selection heuristic to establish bidirectional connections. This makes HNSW suitable for dynamic datasets where vectors are continuously added, though deletions require additional tombstoning logic.

The M parameter controls the maximum out-degree of each node, directly governing memory consumption and search quality. A higher M (typically 16-64) creates a denser graph with more connections, improving recall at the cost of increased RAM usage. Each connection stores both the neighbor ID and the vector, making HNSW memory-intensive compared to quantization-based ANN methods like IVF-PQ.

HNSW builds a hierarchical graph where each layer is a navigable small world network. The bottom layer (layer 0) contains all data points, while higher layers contain exponentially fewer points, acting as a skip list for the search.

• Top layers: Enable long-range jumps across the vector space, quickly narrowing the search region.
• Bottom layer: Performs a final, exhaustive greedy walk to refine the exact nearest neighbors.
• Layer assignment: Each inserted vector is assigned a maximum layer using an exponentially decaying probability distribution, creating the hierarchical structure automatically.

Search begins at the entry point in the topmost layer and performs a 1-greedy search: at each step, move to the neighbor closest to the query until no closer neighbor exists. This becomes the entry point for the next layer down.

• EfSearch parameter: Controls the size of the dynamic candidate queue during the final layer search. Higher values increase recall at the cost of latency.
• Typical production values: EfSearch between 64 and 512 balances sub-millisecond latency with >95% recall@10.
• Beam search behavior: The algorithm maintains a sorted list of the ef closest candidates found so far, expanding the most promising ones first.

Inserting a new vector into an HNSW index involves finding its approximate nearest neighbors at its assigned layer and connecting it to the M closest ones. The algorithm then descends, inserting the vector into each lower layer.

• M parameter: Defines the maximum out-degree of each node. Higher M improves recall but increases memory footprint and build time.
• M_max0: Often set to 2 * M for the dense bottom layer to ensure high connectivity where it matters most.
• Heuristic neighbor selection: Instead of simply connecting to the M closest neighbors, a pruning heuristic favors neighbors that are diverse in direction, preventing cluster over-connection and improving graph navigability.

HNSW is a memory-intensive index because it stores the full graph structure alongside raw vectors. For a dataset of N vectors of dimension d:

• Vector storage: N * d * 4 bytes (for float32).
• Graph storage: Approximately N * M * (4 + 8) bytes per edge, storing neighbor IDs and distances.
• Total overhead: Typically 1.5x to 3x the raw vector data size.
• Mitigation: Use product quantization (PQ) or scalar quantization (SQ) to compress vectors, trading a small recall loss for significant memory savings. Disk-backed implementations like DiskANN offer alternatives for terabyte-scale indexes.

For production recommender systems, the choice often comes down to HNSW versus Inverted File with Product Quantization (IVF-PQ).

• HNSW strengths: Superior recall at low latency, no training phase, incremental insertions are natural, and graph structure adapts to data distribution.
• IVF-PQ strengths: Dramatically lower memory footprint (10x–30x compression), faster build times for billion-scale datasets, and more predictable resource usage.
• Hybrid approaches: Libraries like FAISS and ScaNN combine techniques. ScaNN uses anisotropic vector quantization with a two-pass re-ranking step to achieve state-of-the-art recall-memory tradeoffs.

HNSW powers candidate retrieval in two-tower recommender systems, where user and item embeddings are generated independently and matched via ANN search.

• Sharding: Partition the index across multiple nodes by item ID ranges, with a router merging top-K results from each shard.
• Freshness: New items are inserted incrementally without full index rebuilds. Stale items are periodically pruned via a background compaction process.
• Libraries: FAISS (Meta), HNSWlib (standalone C++), Annoy (Spotify, tree-based alternative), and ScaNN (Google) are the dominant open-source implementations.
• Managed services: Pinecone, Weaviate, and Milvus provide HNSW-backed vector databases with horizontal scaling and real-time updates.