Hierarchical Navigable Small Worlds (HNSW) Internals

As highlighted in the chapter introduction, performing an exact nearest neighbor search across millions or billions of high-dimensional vectors is often too slow for practical applications like real-time semantic search or Retrieval-Augmented Generation (RAG). Hierarchical Navigable Small Worlds (HNSW) emerges as a highly effective and widely adopted Approximate Nearest Neighbor (ANN) algorithm, offering an excellent balance between search speed, recall (accuracy), and memory usage. It's a graph-based algorithm inspired by the principles of Navigable Small Worlds (NSW), but with a significant enhancement: a hierarchical structure.

The Multi-Layer Architecture

Imagine trying to find a specific address in a large country. You wouldn't drive down every single local street. Instead, you'd likely use highways to get close quickly, then regional roads, and finally local streets for the last part of the trip. HNSW employs a similar strategy using a multi-layer graph.

1. Layered Structure: HNSW builds multiple layers of graphs. The bottom layer (Layer 0) contains all the data points (vectors) added to the index. Each subsequent layer above it contains a subset of the points from the layer below. The very top layer typically has only a few points, acting as the main entry points into the graph.
2. Fast Lanes and Local Roads: Higher layers act like "expressways," allowing for long jumps across the vector space during a search. Lower layers represent the "local roads," enabling fine-grained exploration closer to the target query.
3. Inter-layer Connections: Each point exists on its assigned layers and all layers below it. Connections exist not only between points within the same layer but also implicitly connect layers, as the search transitions downwards.

Simplified visualization of an HNSW graph structure with three layers. Connections exist within layers (solid lines) and points also exist on lower layers (dashed lines indicating presence, not direct inter-layer edges). Searches typically start at the top layer entry point(s) (E) and navigate down.

Graph Construction Algorithm

Building an HNSW graph is an incremental process where points are inserted one by one. When a new vector $p$ is added:

1. Select Max Layer ($L_{max}$): A maximum layer $L_{max}$ for the new point $p$ is chosen randomly using an exponentially decaying probability distribution. This means most points will only exist in the lower layers, while a few will reach the higher "expressway" layers. The probability is controlled by a normalization factor mL. A higher mL leads to sparser upper layers. $P(\text{layer}) \propto e^{-\text{layer} / \text{mL}}$
2. Find Entry Points: The insertion process starts at the highest layer of the existing graph. The designated entry point(s) for that layer are used as starting points.
3. Search for Nearest Neighbors (Top Down): Starting from the top layer the new point $p$ will be inserted into (i.e., layer $L_{max}$), the algorithm performs a greedy search within each layer down to Layer 0.
   • Within a Layer: Starting from the entry point(s) found in the layer above (or the global entry point for the top layer), it navigates the graph greedily, always moving towards neighbors that are closer to the new point $p$.
   • Candidate List (efConstruction): During this search-for-neighbors phase at construction time, a dynamic list (priority queue) of the closest candidates found so far is maintained. The size of this list is controlled by the parameter efConstruction. A larger efConstruction means exploring more potential neighbors at each step, leading to a potentially higher-quality graph structure (better recall later) but increasing the index build time.
4. Establish Connections ($M$): Once the search within a layer identifies the nearest neighbors to $p$ (according to efConstruction), connections are established between $p$ and a subset of these neighbors.
   • Maximum Connections ($M$): The parameter $M$ defines the maximum number of outgoing connections a node can have within a single layer.
   • Heuristics: Connections are typically selected based on proximity. Sometimes heuristics are used to ensure good spatial coverage and avoid connecting only to tightly clustered neighbors. If adding a connection to $p$ would exceed $M$ for a neighbor, the neighbor might drop its furthest connection to accommodate the new, closer one. A separate parameter Mmax0 might be used for Layer 0, often set higher (e.g., $2M$) to improve connectivity at the base layer.
5. Repeat for Lower Layers: The algorithm uses the closest neighbors found in layer $l$ as the entry points for the search in layer $l-1$. This process repeats, performing the greedy search and connection steps at each layer from $L_{max}$ down to Layer 0.

This layered construction with controlled connectivity ($M$) and guided search (efConstruction) aims to create a graph that allows efficient navigation from coarse to fine-grained detail.

Search Algorithm

Searching for the $k$ nearest neighbors of a query vector $q$ mirrors the insertion process but focuses solely on finding the closest points without modifying the graph:

1. Find Entry Point: Start the search at the entry point(s) of the topmost layer of the graph.
2. Greedy Search (Top Down): Navigate greedily from the entry point(s) in the top layer towards nodes closer to the query vector $q$. Keep track of the closest node found in this layer.
3. Iterative Refinement (Layer by Layer): Use the closest node found in layer $l$ as the entry point (or one of the entry points) to start the greedy search in layer $l-1$.
4. Candidate List (efSearch): Similar to construction, maintain a dynamic priority queue of candidate nearest neighbors found so far during the search across layers. The size of this candidate list during search is controlled by the parameter efSearch. This is a critical parameter for tuning the trade-off between search speed and accuracy (recall).
   • efSearch must be at least $k$ (the number of neighbors requested).
   • A larger efSearch explores more paths in the graph, increasing the probability of finding the true nearest neighbors (higher recall) but taking more time (higher latency).
   • A smaller efSearch results in a faster search but might miss some true neighbors (lower recall), settling for "good enough" approximate neighbors.
5. Termination: The search continues downwards layer by layer. The process typically involves exploring neighbors primarily in Layer 0, guided by the entry points found from the layers above. Once the search exploration according to efSearch criteria is complete (e.g., the priority queue cannot be improved further), the algorithm returns the $k$ closest vectors found from the final candidate list.

Core Parameters and Tuning Considerations

Effectively using HNSW often involves tuning a few important parameters:

• M (Max Connections per Layer): Controls the density of the graph within each layer (except potentially Layer 0).
  • Impact: Higher M increases graph connectivity, potentially improving recall and robustness. However, it also significantly increases the memory footprint of the index and the graph construction time.
  • Typical Values: 5 - 48.
• efConstruction (Construction Candidate List Size): Controls the depth of the search performed during index building when finding neighbors for a new point.
  • Impact: Higher efConstruction leads to a better-quality graph structure (better recall during actual searches) but substantially increases index build time. It has less impact on index size compared to M.
  • Typical Values: 64 - 512 (or even higher, depending on desired quality vs. build time).
• efSearch (Search Candidate List Size): Controls the depth of the search performed at query time.
  • Impact: Directly influences the trade-off between search speed (latency) and recall. Higher efSearch increases recall but slows down queries. Must be $\ge k$.
  • Typical Values: $k$ to 512 (or higher, depending on the required recall/latency). Often tuned based on application requirements via offline evaluation or A/B testing.
• mL (Level Normalization Factor): Influences the probability distribution for assigning layers during construction.
  • Impact: Affects the distribution of nodes across layers. Smaller values lead to denser upper layers. Often left at default values (e.g., $1 / \ln(M)$).

Tuning these parameters is essential for optimizing HNSW for specific dataset characteristics and application requirements (e.g., prioritizing low latency vs. maximizing recall).

Advantages and Disadvantages of HNSW

Advantages:

• State-of-the-Art Performance: Often achieves high recall at very high query speeds compared to many other ANN methods.
• Memory Efficiency: While graph-based, its memory usage is generally more manageable than brute-force or some other complex structures, especially when combined with quantization (discussed later).
• Handles Updates: The incremental build process makes it relatively straightforward to add new points to an existing index without a full rebuild (though deletions can be more complex).
• Good Generality: Performs well across various data distributions and dimensionalities.

Disadvantages:

• Build Time: Constructing the HNSW graph, especially with high efConstruction, can be time-consuming for very large datasets.
• Parameter Tuning: Finding the optimal combination of M, efConstruction, and efSearch can require careful experimentation and evaluation.
• Complexity: The underlying algorithm is more intricate than simpler methods like IVF, potentially making implementation or modification more challenging.

HNSW stands as a cornerstone algorithm for modern vector search due to its impressive performance characteristics. Understanding its layered structure, construction process, and search mechanism is fundamental to building efficient and effective semantic search and RAG systems. In the following sections, we will explore other important ANN techniques like IVF and PQ, and later discuss how they can sometimes be combined with HNSW for further optimization.