What is an exponential distribution?

An exponential distribution describes a kind of randomness where small values are far more common than large ones, with the likelihood of a value dropping off sharply as that value grows, and it’s precisely this shape that HNSW relies on to decide how many layers of its graph any given vector should belong to.

What makes an exponential distribution’s shape different from a uniform random variable’s?

A uniform random variable, covered elsewhere in this glossary, treats every value in its range as equally likely, with no bias toward small or large outcomes. An exponential distribution is the opposite in spirit: the smallest possible values are the most likely outcomes by far, and the probability of drawing a larger value keeps shrinking the further out that value sits, producing a long tail where large values are technically possible but increasingly rare. This lopsided shape is exactly what’s needed whenever a system wants “most things small, a few things large” rather than “everything equally likely,” which turns out to describe HNSW‘s layer structure precisely.

How does drawing from an exponential distribution actually decide how many layers a vector gets added to?

When a new vector is inserted into HNSW’s graph, covered throughout this site’s coverage of building the algorithm from scratch, a value is drawn from an exponential distribution to determine the highest layer that vector will appear on, with the vector then also added to every layer below that one down through the bottom layer where all vectors ultimately reside. Because small values dominate an exponential distribution, most vectors are assigned a very low highest layer — often just the bottom one — while only a small, shrinking fraction get assigned to progressively higher layers, exactly matching the coarse-to-fine pyramid shape that gives the graph its efficient search behavior, covered in this site’s page on how the layered structure supports search.

How is a value actually drawn from an exponential distribution in practice?

The standard technique starts with a uniform random variable, drawing a value from a plain, unbiased range, and then applies a specific mathematical transformation — taking its logarithm and scaling the result by a chosen constant — to reshape that uniform value into one that follows an exponential distribution’s lopsided pattern instead. That scaling constant controls exactly how steeply the distribution favors small values, which in HNSW’s case directly controls how quickly the number of vectors thins out at each successive layer, tying this probability concept directly to a real, tunable parameter of the algorithm’s construction process.

The exponential distribution is the specific mathematical shape that makes HNSW’s pyramid-like layer structure emerge naturally from a simple random draw at insertion time. From here, the page on the uniform random variable it’s built from and the page on expectation in probability, which covers how to reason about its average behavior across many insertions, are the natural next steps.