What is a geometric distribution?

A geometric distribution describes how many repeated attempts it takes before a random event with a fixed success probability finally happens, and it produces the same lopsided shape as the exponential distribution covered elsewhere in this glossary, but built from discrete, countable steps rather than a smooth continuous range.

How does a geometric distribution actually work, step by step?

Picture flipping a coin repeatedly, where each flip has some fixed chance of coming up heads, and asking how many flips it takes before the first heads appears. Most of the time the answer is small — heads shows up on the first or second flip far more often than it takes ten or twenty flips — but there’s always some chance, however small, of a long unlucky streak before the first success. A geometric distribution is exactly this pattern formalized: it counts the number of independent, repeated attempts needed before a fixed-probability event finally occurs, with small counts being the most likely outcomes and larger counts becoming steadily rarer.

How does a geometric distribution relate to the exponential distribution covered elsewhere in this glossary?

The exponential distribution describes the same basic idea of “small values common, large values rare” but for a smooth, continuous quantity like an amount of time rather than a count of discrete steps. A geometric distribution is often described as the discrete counterpart to the exponential distribution: where the exponential distribution asks how much continuous time passes before an event happens, the geometric distribution asks how many discrete, countable attempts pass before that same kind of event happens. Both share the identical lopsided shape, favoring small outcomes overwhelmingly over large ones, which is exactly why they show up in closely related situations throughout probability and why HNSW‘s own layer-assignment logic can be explained using either framing depending on whether the underlying process is treated as continuous or as a sequence of discrete steps.

Where does this discrete, step-counting framing actually show up in HNSW specifically?

HNSW‘s layer-assignment process, covered in this site’s page on the exponential distribution, is usually explained using a continuous draw, but it can equally be understood as a sequence of discrete coin flips: imagine repeatedly flipping a biased coin to decide whether a vector gets promoted to one more layer, continuing to flip and promote for as long as the coin keeps coming up in favor of promotion, and stopping the first time it doesn’t. The number of successful promotions before that first failure follows a geometric distribution, and this framing produces the exact same overall pattern — most vectors staying low, a shrinking few climbing higher — as the continuous exponential-distribution explanation covered elsewhere in this glossary, just expressed as a sequence of discrete steps instead of a single continuous draw.

Whether HNSW’s layer assignment is framed as a single continuous draw or as a sequence of discrete coin flips, both descriptions converge on the same underlying pattern of mostly-shallow, occasionally-deep vector placement. From here, the pages on the exponential distribution and on expectation in probability round out this glossary’s coverage of the randomness driving HNSW’s layered structure.