What is variance in a randomized algorithm?

Variance in a randomized algorithm measures how much an outcome, run after run, tends to spread out around its average value, and it’s the key idea for understanding whether a randomized process like HNSW’s construction behaves consistently across repeated builds or fluctuates widely from one build to the next.

How does variance actually capture the idea of “spread” around an average?

Expectation, covered elsewhere in this glossary, describes the average outcome a random process tends to produce, but two very different processes can share the exact same average while behaving completely differently in practice: one might land close to that average almost every single time, while another might swing wildly above and below it, only averaging out to the same value once enough runs accumulate. Variance is what distinguishes these two situations, measuring how far individual outcomes typically stray from the average — a low variance means outcomes cluster tightly around the average, while a high variance means outcomes are scattered much more loosely around it, even if the average itself is identical in both cases.

Where does variance actually show up as a meaningful concern in HNSW’s construction process?

Random level assignment, covered elsewhere in this glossary, determines how many layers each vector belongs to through an independent random draw for every single insertion, and while the overall expected proportion of vectors on each layer is well understood, the variance around that expectation describes how much an individual index’s actual layer proportions might deviate from that expected pattern purely by chance. For a very large dataset, with many independent insertions averaging out any individual randomness, this variance tends to matter relatively little in practice; for a smaller dataset, with fewer insertions to average across, the same underlying variance can produce a noticeably lopsided graph purely as a result of chance, which is worth being aware of when interpreting the structure or performance of a small index.

How does variance connect to the reliability of benchmark results built from repeated queries?

Evaluation and benchmarking, covered throughout this site, generally rely on running many test queries and averaging metrics like recall across them, drawing directly on the same Monte Carlo estimation logic covered elsewhere in this glossary. The variance of the underlying per-query results directly determines how many test queries are actually needed before that average can be trusted: a metric with low variance across queries settles into a reliable average relatively quickly, while a metric with high variance requires substantially more test queries before the averaged result becomes trustworthy, which is a key reason rigorous benchmarking methodology, covered elsewhere on this site, emphasizes running enough queries rather than treating any arbitrary sample size as automatically sufficient.

Variance rounds out expectation’s picture of average behavior by describing how much any single outcome can be expected to deviate from that average, a distinction that matters throughout both HNSW’s construction and its evaluation. From here, the pages on expectation in probability and on Monte Carlo estimation dig further into the two concepts variance directly builds on.