Hierarchical Navigable Small World (HNSW)

HNSW constructs a hierarchical graph where each layer represents a proximity graph of the full dataset at varying densities. The bottom layer (layer 0) contains all data points and short-range connections, capturing local neighborhoods. Each subsequent upper layer contains an exponentially smaller subset of points with longer-range connections, acting as an expressway for search. This structure allows the algorithm to skip over large swaths of irrelevant space quickly.

• Layer assignment uses an exponentially decaying probability distribution, typically normalized by a level multiplier m_L.
• Search complexity scales as O(log N) due to the hierarchical skip-list-like navigation.
• The top layer often contains only a single entry point, serving as the universal starting node for all searches.

Search in HNSW proceeds layer-by-layer from the top down using a greedy best-first search. At each layer, the algorithm maintains a dynamic candidate list and an ef (exploration factor) parameter that controls the beam width. It evaluates neighbors of the current closest node and updates the candidate set, moving to the closest unvisited node until no closer candidates remain.

• The ef parameter at search time (often called ef_search) trades off speed against accuracy; higher values explore more candidates.
• Once a local minimum is found on a layer, the algorithm descends to the next layer using the best candidate as the new entry point.
• This greedy descent ensures the algorithm rapidly converges to the true nearest neighbors in the dense bottom layer.

Inserting a new element into an HNSW graph involves finding its nearest neighbors on each layer using the same greedy search, then establishing bidirectional connections. The algorithm enforces a maximum number of connections per node (M for the bottom layer, M_max0, and M for upper layers) to prevent memory blowout.

• A pruning heuristic removes redundant connections: if a new edge creates a detour path that is shorter than a direct connection, the direct connection is discarded.
• This heuristic ensures the graph maintains the small-world navigability property, where any node can be reached in a small number of hops.
• The insertion process is incremental and fully online, allowing the index to grow dynamically without full rebuilds.

HNSW explicitly constructs a graph that satisfies the navigable small-world criteria. In a small-world network, the average shortest path length between any two nodes scales logarithmically with the number of nodes, and the clustering coefficient is high. This is achieved by maintaining both short-range links (to immediate neighbors in the vector space) and long-range links (to distant points, especially in upper layers).

• Long-range links are naturally formed during insertion because new nodes connect to their approximate nearest neighbors, which may be far away in sparsely populated regions.
• The hierarchical structure amplifies this effect: upper layers function as a long-range shortcut network.
• This dual connectivity guarantees that greedy routing never gets trapped in local minima far from the query.

HNSW exposes several critical parameters that directly control the accuracy-speed trade-off. The construction-time parameter M (max outgoing connections) increases graph connectivity and recall at the cost of memory and build time. The search-time parameter ef_search increases the beam width of the greedy search, exploring more paths.

• Typical M values range from 16 to 64; higher values suit high-recall applications.
• ef_search is often set between 100 and 500; setting it equal to k (number of desired neighbors) yields fast but lower-recall results.
• ef_construction controls the search depth during insertion; a higher value builds a higher-quality graph at the expense of slower indexing.
• Memory usage is O(N * M) for the graph structure plus the raw vector storage.

HNSW consistently outperforms tree-based methods like Annoy and quantization-based methods like IVF-PQ on high-recall benchmarks, especially for high-dimensional data. Unlike FAISS IVF indexes, HNSW requires no separate training or clustering phase; it is purely incremental. Compared to NSG or DiskANN, HNSW typically achieves higher recall for a given queries-per-second (QPS) budget on in-memory datasets.

• Advantages: Fully incremental, no global retraining, excellent recall-latency Pareto frontier.
• Disadvantages: Higher memory footprint than compressed quantization methods; graph construction can be CPU-intensive.
• Common implementations: hnswlib (C++ with Python bindings), FAISS IndexHNSW, and Lucene's HNSW codec.

The practice of attaching structured attributes (date, author, category, security clearance) to vectors in an HNSW index and applying boolean or range filters before or during graph traversal. This ensures retrieved neighbors are not just semantically similar, but also contextually valid.

• Pre-filtering: Narrow the candidate set before HNSW search
• In-filtering: Apply constraints during graph navigation
• Critical for multi-tenant systems where data isolation is mandatory

A two-stage retrieval pipeline where HNSW serves as the fast, coarse retriever, fetching the top-k candidate documents, and a computationally intensive cross-encoder re-ranks those candidates with full query-document attention. HNSW provides breadth at speed; the cross-encoder provides depth and precision.

• Stage 1 (HNSW): Retrieve top 100-1000 candidates in milliseconds
• Stage 2 (Cross-Encoder): Score each candidate jointly with the query
• Improves MRR and NDCG significantly over single-stage retrieval

The segmentation of documents into semantically coherent units before embedding and indexing into an HNSW graph. Chunk size and overlap directly impact graph quality — too small loses context, too large dilutes semantic specificity.

• Semantic chunking splits on natural topic boundaries
• Propositional chunking decomposes text into atomic facts
• Chunk overlap (10-20%) prevents information loss at boundaries
• HNSW graph edges connect chunks that are both semantically and contextually related