What is the difference between expected value and worst case?

Expected value describes what a random process’s outcome averages out to across many repeated runs, while worst case describes the single most unfavorable outcome that could possibly occur, even if it’s vanishingly rare — and understanding which of these two framings a claim about HNSW‘s performance is actually making matters enormously for interpreting it correctly.

Why can a random process have such different expected and worst-case outcomes at the same time?

Expectation, covered elsewhere in this glossary, is a weighted average across every possible outcome, so it naturally reflects what typically happens, dominated by whichever outcomes are actually likely. Worst case ignores likelihood entirely and asks only what the single most extreme possible outcome looks like, no matter how improbable it might be to actually encounter it. A process can have an excellent expected value while still having a terrible worst case, if that terrible outcome is rare enough to barely register in the average — this is exactly the kind of gap that shows up in randomized data structures, covered elsewhere in this glossary, where the typical run behaves very differently from the theoretical worst possible run.

How does this distinction play out concretely in claims about HNSW’s search performance?

HNSW‘s random level assignment, covered elsewhere in this glossary, produces graphs whose expected structure supports fast, efficient search in the overwhelming majority of cases, and most published performance claims about HNSW describe exactly this expected, typical behavior, covered in more detail in this site’s page on what can actually be proven about HNSW’s complexity. The worst case is a different story: it’s theoretically possible, though extraordinarily unlikely given the underlying probability distributions involved, for an unusually unlucky sequence of random level assignments to produce a graph with meaningfully worse search performance than the typical case would suggest. This is why performance claims about HNSW are almost always framed in terms of expected behavior, sometimes explicitly and sometimes only implicitly, rather than as guaranteed worst-case bounds.

Why does this distinction matter for how someone should actually read performance numbers and guarantees?

A benchmark report or a theoretical claim that doesn’t clearly specify whether it’s describing expected or worst-case behavior can be genuinely misleading, since the two framings answer fundamentally different questions: “what should I typically expect” versus “what’s the absolute worst that could happen.” For most practical purposes, especially with a large dataset where randomness averages out reliably across many independent insertions, expected behavior is the more relevant and more commonly reported framing, but any system with strict, non-negotiable latency or correctness requirements needs to reason explicitly about worst-case behavior rather than assuming the typical case will always hold, covered further in this site’s page on worst-case complexity.

Distinguishing expected value from worst case clarifies exactly what kind of guarantee, if any, a given claim about HNSW’s behavior is actually making. From here, the pages on expectation in probability and on worst-case complexity dig further into each side of this distinction individually.