Welcome back. In our last lesson, we delved into the critical process of benchmarking, establishing the fundamental trade-off between search speed (QPS) and accuracy (recall) that governs all approximate algorithms. You saw that while our Navigable Small World (NSW) graph is a significant leap in performance over a brute-force scan, it still has inherent limitations.
This lesson marks our transition to a truly state-of-the-art algorithm. Our objective is to explain how HNSW improves upon NSW by introducing a hierarchical, multi-layer graph structure. We will dissect the architectural weaknesses of a "flat" graph like NSW and understand how adding layers, inspired by a classic computer science data structure, leads to logarithmic search complexity and a superior performance curve. This conceptual understanding is the foundation upon which we'll build our implementation.
The Limits of a Flat World
The Navigable Small World graph was a major step forward, introducing the idea of combining short-range links for accuracy with long-range links for fast traversal. However, its single-layer, "flat" structure leads to a key problem. As we saw in the previous lesson, the search is a greedy traversal that starts at an entry point and hops to the closest neighbor at each step. This process has two phases:
- The "Zoom-Out" Phase: In the early stages, the search traverses nodes that may be far from the target, relying on long-range links to cross the vector space. If the local neighborhood is sparse, the search can easily get trapped in a local minimum far from the true destination.
- The "Zoom-In" Phase: As the search gets closer to the query, it navigates through a denser region of the graph with many short-range links, allowing it to converge on the nearest neighbors.
The problem with NSW is that you can't control these phases. A search might get stuck in the "zoom-out" phase, leading to poor recall. The only remedy is to increase the number of connections (M) for each node, but this makes the graph denser and slows down traversal for everyone. This leads to a search complexity that is polylogarithmic—better than linear, but not the O(log N) we are aiming for.
The Pinecone article "Hierarchical Navigable Small Worlds (HNSW)" provides an excellent summary of this issue.
Hierarchical Navigable Small Worlds (HNSW)
This article clearly explains the foundations of NSW and its limitations, setting the stage for HNSW.
Please read the subsection on NSW graphs. Pay close attention to the discussion of the "zoom-out" and "zoom-in" phases and the problem of getting stuck in local minima with low-degree vertices.
The Solution: A Hierarchy of Graphs
To overcome the limitations of NSW, its creators, Yury Malkov and Dmitry Yashunin, introduced a hierarchical structure. The core idea is simple but powerful: instead of one flat graph, what if we had multiple layers of graphs?
This concept is directly analogous to a classic data structure you may have encountered in your computer science studies: the skip list. A skip list enhances a standard linked list by adding multiple layers of "express lane" pointers that skip over several nodes at once. A search starts in the fastest, top-most layer, and drops down to more granular layers only when it has overshot its target. This allows it to achieve logarithmic search time.
HNSW applies this exact principle to proximity graphs.
In this structure:
- Higher layers contain very few nodes and only the longest-range links. They are the "expressways" of the vector space.
- Lower layers become progressively denser, with more nodes and shorter-range links, acting as the "local roads."
- Layer 0 is the bottom-most layer. It contains every single vector in the dataset and has the densest local connections, much like a complete NSW graph.
The following video provides a clear, concise walkthrough of the evolution from skip lists and NSW to the combined HNSW structure.
HNSW for Vector Search Explained and Implemented with Faiss (Python)
This video by James Briggs offers an excellent conceptual breakdown of the data structures that inspired HNSW and how they are combined.
Watch the segments that explain the foundational algorithms and their synthesis into HNSW: Probability Skip List: This section explains the core idea of using layers to speed up search in a 1D linked list. Navigable Small World Graphs: This covers the NSW concepts we've discussed, including the "zoom-out" and "zoom-in" phases. Creating HNSW: This part brings the two ideas together, showing how the hierarchy of the skip list solves the problems inherent in the flat NSW graph.
The HNSW Search Algorithm
With this layered structure, the search process becomes much more robust and efficient. It neatly decouples the long-range and short-range navigation that was entangled in NSW.
The search proceeds as follows:
- Enter at the Top Layer: The search begins at a single entry point in the highest, most sparse layer.
- Greedy Search Downwards:
- In the current layer, perform a greedy search to find the node closest to the query vector.
- Once a local minimum is found in this layer, use that node as the entry point into the layer below it.
- Repeat until the Bottom: This process is repeated—find the best entry point in the current layer, drop down, and refine the search—until the greedy search is completed in the dense Layer 0.
This top-down approach solves the primary weakness of NSW. By starting in the "zoom-in" phase on a sparse graph with long-range links, the algorithm quickly identifies the correct region of the vector space. It then progressively increases precision as it moves to denser layers, minimizing the risk of getting trapped in a poor local minimum. This is what enables HNSW to achieve O(log N) search complexity.
The video below gives another animated perspective on this search process.
Vector Database Search - Hierarchical Navigable Small Worlds (HNSW) Explained
This video from DataMListic provides a high-level animated walkthrough of the HNSW structure and search process.
Focus on these key sections: Combining Concepts: Briefly explains how skip lists and NSW are merged. The Search Process: An animated demonstration of the top-down search path. Performance Improvements: Explains why this hierarchical approach leads to logarithmic complexity.
Building the Hierarchy: Probabilistic Layer Assignment
The final piece of the puzzle is understanding how nodes are assigned to layers. HNSW again borrows from skip lists, using a simple and elegant probabilistic method.
When a new vector is inserted into the graph, it is assigned a maximum layer, l, using an exponentially decaying probability distribution. Specifically, every node is guaranteed to be in Layer 0. Then, it has a certain probability of also being in Layer 1, a smaller probability of being in Layer 2, and so on.
The original paper proposes the following formula to choose the maximum layer l for a new element:
Here, uniform(0,1) is a random number between 0 and 1, and mL is a normalization factor. This formula ensures that the number of nodes decreases exponentially with each layer. A node assigned to layer l will have connections on all layers from 0 up to l.
For a deeper dive into the theory, the following article provides a rigorous explanation.
Understanding HNSW — Hierarchical Navigable Small World
This article goes into the theoretical underpinnings of HNSW, connecting it to skip lists and small-world network theory.
Focus on these two sections under the "Core Algorithm Architecture" heading: First, read the section on Skip Lists for a formal description of the probabilistic level assignment that HNSW is based on. Then, read Hierarchical Layer Structure Design. This section describes exactly how HNSW uses a similar probabilistic model for its layer assignment and explains the role of the mL parameter, noting the optimal value is often near 1/ln(M).
Conclusion
In this lesson, we have uncovered the architectural brilliance of HNSW. By moving from a flat graph to a probabilistic, hierarchical structure, HNSW overcomes the core limitations of NSW, providing a more robust and scalable solution for approximate nearest neighbor search.
Key Takeaways:
- NSW Limitation: NSW's flat structure mixes long- and short-range navigation, leading to polylogarithmic complexity and a risk of getting trapped in poor local minima.
- HNSW's Solution: HNSW introduces a multi-layer graph hierarchy, inspired by skip lists, to separate links by distance scale.
- Hierarchical Structure: Top layers are sparse with long-range links for fast, coarse-grained traversal ("zoom-in" first). The bottom layer is dense with short-range links for fine-grained, accurate search.
- Top-Down Search: The search starts at the highest layer and progressively refines the result by moving down, drastically improving efficiency and recall. This achieves O(log N) complexity.
- Probabilistic Assignment: Nodes are assigned to layers using an exponentially decaying probability distribution, ensuring higher layers are exponentially sparser.
Now that you have a firm grasp of the "what" and "why" behind HNSW's structure, we are ready to move on to the "how." In our next lesson, we will begin the implementation by designing the in-memory data structures for an HNSW graph node, figuring out how to represent this complex, multi-layered connectivity efficiently in C.