Which mathematical notation does this documentation use consistently?

This documentation uses a small, consistent set of mathematical notation throughout, borrowed from the conventions common across nearest-neighbor search literature: lowercase italic letters for dataset size, dimensionality, and result count, the algorithm’s own named parameters written exactly as introduced in earlier pages, and standard probability and complexity notation wherever randomness or scaling behavior needs to be stated precisely rather than only described in words.

How are dataset size, dimensionality, and result count written throughout this site?

The letter n denotes the number of vectors in a dataset, and d denotes each vector‘s dimensionality — the number of individual numbers making up one vector. The letter k denotes the number of nearest neighbors a query actually requests, distinct from any of HNSW‘s own internal parameters even though it plays a role in constraining one of them, as covered in this site’s page on what M, efConstruction, and efSearch actually change. These three letters appear together constantly in complexity statements — a linear scan‘s cost, for instance, is written as being proportional to n times d, capturing that its cost grows both with how many vectors exist and how large each one is.

How are HNSW’s own parameters and layer structure represented?

M, efConstruction, and efSearch are written exactly as introduced throughout this site’s tuning-and-optimization coverage, always referring to the same three quantities: the maximum connections per node, the construction-time candidate search width, and the query-time candidate search width, respectively. A specific layer within the graph‘s hierarchy is generally referred to as layer l, with layer 0 always denoting the base layer containing every vector, and higher values of l denoting progressively sparser layers above it. The level multiplier, written mL, is the parameter controlling how quickly the probability of reaching each successive layer decays, referenced in this site’s page on the core idea behind HNSW‘s layered graph.

How is randomness and probability written in the level-assignment formula?

A uniform random variable drawn from the open interval between 0 and 1 is written as U, sampled fresh for each new vector as it’s inserted. The maximum layer a given vector reaches is determined by taking the natural logarithm of this random draw, negating it, multiplying by the level multiplier mL, and rounding down to the nearest whole number — a formula that produces the exponentially decaying layer-population distribution described narratively in this site’s page on the core idea behind HNSW’s layered graph, where most vectors land only in the base layer and progressively fewer reach each layer above it.

How is complexity and recall written mathematically?

Asymptotic complexity throughout this site uses standard big-O notation, written as O of some expression, describing how a quantity like time or memory scales as the relevant input — usually n — grows large, always alongside the caveats covered in this site’s page on what can and can’t actually be proven about HNSW’s complexity rather than presented as an unconditional guarantee. Recall@k, the fraction of the true top-k nearest neighbors that a search actually returned, is written as the size of the overlap between the approximate result set and the true result set, divided by k — a precise formula behind the more conversational description given wherever recall is discussed narratively elsewhere on this site.

With this shared notation established, the next appendix builds on it directly, presenting HNSW’s search and construction procedures as complete, explicit pseudocode rather than the narrative descriptions used in the main chapters. Readers who encountered any of these symbols without this reference nearby should feel free to return to this page whenever a later page’s notation needs a refresher.