What is expected hierarchy height?
Expected hierarchy height is the theoretical prediction, derived directly from the level-assignment probability distribution, for how tall an HNSW index‘s hierarchy should typically grow as a function of how many vectors it contains — a quantity that grows only logarithmically with dataset size, meaning even a dataset a thousand times larger only needs a modestly taller hierarchy to accommodate it. It’s one of the more concrete, mathematically grounded predictions in HNSW‘s theoretical foundations, and it directly explains an observation covered informally elsewhere in this documentation: real HNSW indexes, even ones holding hundreds of millions of vectors, tend to end up with only a handful of layers rather than dozens or hundreds.
Where does this logarithmic prediction actually come from, mathematically?
Recall from the level-assignment-probability glossary page that each node’s maximum layer is drawn from a distribution that decays exponentially with height, controlled by the level-multiplier parameter mL — the probability of any single node reaching a given layer shrinks by a consistent multiplicative factor for every additional level up the hierarchy. Because this decay is exponential, the expected height of the tallest layer any node actually reaches, across an entire dataset of N vectors, grows only as the logarithm of N. This inverse relationship — an exponentially decaying per-node probability paired with a logarithmically growing expected maximum across many independent draws — is a standard pattern in probability theory that shows up whenever many independent trials are drawn from a distribution with exponential tails, and it’s exactly the mathematical mechanism responsible for HNSW’s hierarchy staying so compact even as the underlying dataset grows extremely large.
Intuitively, this happens because doubling the dataset size doubles the number of chances for at least one node to draw an unusually high layer by chance, but since reaching an even higher layer requires an exponentially rarer draw, that doubled number of chances only pushes the expected maximum height up by a small, roughly constant increment rather than doubling it in turn.
Why does this theoretical prediction actually matter in practice, rather than being purely a mathematical curiosity?
This logarithmic relationship is the direct theoretical justification behind HNSW’s favorable overall search-cost scaling, discussed throughout the complexity-and-theory-specific-to-HNSW glossary category. The hierarchy’s height determines how many layers a query has to descend through during its upper-layer greedy phase before reaching the base layer, and since that height grows only logarithmically with dataset size, the number of these comparatively cheap upper-layer steps stays small even for enormous datasets. This is a meaningful part of the overall argument for why HNSW’s search cost scales so favorably overall — a hierarchy that instead grew linearly or worse with dataset size would undermine much of the benefit the layered structure is supposed to provide, since the upper-layer descent phase would itself become an increasingly expensive part of every query rather than staying a cheap, bounded preliminary step.
Does the expected hierarchy height actually match what gets observed in real, practical HNSW indexes?
Empirical measurements of real HNSW indexes generally confirm this theoretical prediction closely — indexes holding datasets ranging from thousands to billions of vectors typically end up with hierarchies only a handful of layers tall, consistent with what the logarithmic relationship predicts given typical mL settings. This close match between theory and practice is one of the more reassuring pieces of evidence that HNSW’s underlying probabilistic design actually behaves the way its mathematical foundations predict, rather than the theory being a rough approximation that real implementations diverge from significantly once actual data and real-world construction quirks get involved.
It’s worth being precise, though, that “expected” here means exactly what it says statistically — the actual height of any single, specific index build can vary somewhat around this expected value, since it ultimately depends on the specific random draws that happened to occur during that particular build’s construction, exactly as covered on the insertion-order-sensitivity and random-level-assignment glossary pages. Two indexes built from identical data with identical parameters can end up with hierarchies of slightly different heights purely due to this randomness, even though both heights should cluster reasonably close to the same theoretically predicted expected value.
How does mL specifically influence this expected height, beyond the general logarithmic relationship?
mL directly scales the logarithmic relationship — a larger mL flattens the level-assignment distribution’s decay, which both increases the expected height for any given dataset size and shifts the whole logarithmic curve upward, while a smaller mL steepens that decay and correspondingly compresses the expected height downward. This connects directly back to the practical discussion on the mL glossary page about why a specific relationship between mL and M tends to be chosen in practice — that relationship is specifically calibrated to produce an expected hierarchy height, and a corresponding degree of upper-layer sparsity, that balances useful long-range navigability against the overhead of maintaining more layers than actually necessary.
Having covered the mathematical basis for why HNSW’s hierarchy stays logarithmically compact as datasets scale, the mL and level-assignment-probability glossary pages are worth revisiting together with this fuller theoretical grounding for why they’re set the way they typically are. From there, the logarithmic-search-claim glossary page picks up the closely related, broader claim about HNSW’s overall query cost, which this page’s result about hierarchy height feeds directly into as one of its key supporting pieces.