Probabilistic Layer Assignment & Skip Lists

The Skip List Principle Revisited

As we discussed, the inspiration for HNSW's hierarchy is the skip list. A skip list augments a simple sorted linked list with "express lanes" on higher levels. A search can traverse these express lanes to quickly skip over large sections of the list before dropping down to more granular levels for the final search.

The crucial question is: how are nodes chosen to be part of these express lanes? The answer is simple probability. When a new node is added, a virtual coin is tossed. If it's heads, the node is "promoted" to the next layer up. This process is repeated, so the probability of a node reaching a very high layer decreases exponentially. For a promotion probability p (e.g., 0.5), the chance of reaching level i is $p^i$. This naturally creates sparse upper layers and a dense base layer.

The article "Understanding HNSW" provides a formal description of this principle.

Adapting Probability for High-Dimensional Space

HNSW adopts this exact principle. However, unlike a 1D skip list where nodes have a clear order, our vectors exist in a high-dimensional space with no inherent "next" element. HNSW's insight was to apply the probabilistic layering not to an ordered list, but to the nodes of a proximity graph.

When a new vector is inserted into the graph, it is assigned a maximum layer, l, on which it will exist. (It will also exist on all layers below l, down to Layer 0). This assignment is made using a probabilistic formula defined in the original paper:

This formula might seem opaque at first, but it elegantly produces the same exponential decay we saw in skip lists. Let's break it down.

• uniform(0,1): This is simply a random floating-point number generated between 0.0 and 1.0. It's the source of randomness for our process.
• -ln(...): This is the core of the trick. Taking the negative natural logarithm of a uniformly distributed random variable transforms it into a variable that follows an exponential distribution. The key property here is that small output values are very likely, while large output values are very rare. This is exactly what we want: most nodes should be assigned to low layers, and only a few should reach the high layers.
• m_L: This is a normalization factor, or "level multiplier." It scales the output of the exponential distribution to control how many layers the graph is likely to have. A larger m_L "stretches" the distribution, making it more likely for nodes to reach higher layers.
• floor(...): Finally, we round the result down to the nearest integer to get our final layer index l.

The SDSLabs blog post on implementing HNSW gives a fantastic, code-oriented explanation of this process.

The Role of the m_L Parameter

The m_L parameter is not arbitrary. It's directly tied to M, the number of neighbors each node will connect to in a given layer. The original HNSW paper found that an optimal value for m_L is:

This establishes a clear relationship between the density of connections within a layer (M) and the distribution of nodes across layers (m_L). A graph with more connections per node (larger M) will have a smaller m_L, leading to a "flatter" hierarchy with fewer layers. Conversely, a sparser graph (smaller M) will have a larger m_L, creating more layers to ensure the graph remains navigable. This self-tuning property is part of what makes the algorithm so robust.

The video below from MongoDB provides an excellent visual demonstration of how changing m_L affects the distribution of nodes across the layers.

From Theory to Practice

Let's see what this looks like in a real system. The video by James Briggs not only explains the theory but also dives into the Faiss library's C++ source code to show the random_level function. He then replicates this logic in Python and shows that it produces an almost identical distribution of nodes per layer as the production Faiss library. This is a powerful confirmation that our understanding of the theory directly maps to how high-performance vector search libraries are built.

By assigning layers randomly with this exponentially decaying probability, HNSW achieves two critical goals:

1. It automatically creates the hierarchical structure needed for efficient O(log N) search.
2. It ensures the graph is well-balanced. Unlike in NSW where the first few nodes inserted could become over-centralized "hubs," in HNSW any node, regardless of when it was inserted, has the same random chance of reaching a high layer.

Conclusion

In this lesson, we have demystified the process of HNSW layer assignment. You have seen how a simple yet powerful probabilistic formula, directly inspired by skip lists, is used to construct the complex, multi-layered graph that gives HNSW its remarkable performance.

Key Takeaways:

• Probabilistic Foundation: HNSW borrows the probabilistic layer promotion mechanism from skip lists.
• The Formula: The assignment is governed by $l=\lfloor -\ln (\text{uniform}(0,1))\cdot m_L\rfloor$.
• Exponential Distribution: The -ln(uniform(0,1)) component is key, as it transforms a uniform random number into one following an exponential distribution, making low layers common and high layers rare.
• Normalization: The m_L parameter, typically set to 1/ln(M), scales the distribution, linking the graph's layer structure to its connection density (M).
• Balanced Graph: This random assignment at insertion time prevents the formation of overly-important "hub" nodes and leads to a more balanced and robust graph structure.

You now understand how a node decides which layers it belongs to. The next logical question is how we represent this information in memory. In the next lesson, we will design the in-memory data structures for an HNSW graph node, considering how to efficiently store a variable number of connections across multiple layers—a classic low-level systems design challenge.