What does rigorous HNSW benchmarking methodology actually require?

Rigorous HNSW benchmarking methodology requires treating measurement with the same care as the algorithm itself: establishing a trustworthy ground truth before comparing anything against it, reporting more than a single average number for speed, holding every variable but the one being tested constant, and repeating measurements enough times to know whether an observed difference is real or just noise.

What does a benchmark need to establish before measuring anything else?

Every recall number is only meaningful relative to a correct, exact answer to compare against, so the first requirement is computing genuine ground truth — the true nearest neighbors for a representative set of test queries, found through brute-force search using the exact same distance metric and data the approximate index will be evaluated against. Recall@k is then simply the fraction of those true top-k neighbors that the approximate search actually returned, averaged across the test queries. Skipping this step, or computing ground truth carelessly — using a different metric, a stale dataset snapshot, or too small a query sample to be representative — undermines every recall number reported afterward, no matter how carefully the rest of the benchmark is run.

Why isn’t average latency enough on its own?

An average hides exactly the kind of behavior that matters most for a production system: a handful of very slow outlier queries can pull an average up only modestly while representing a genuinely bad experience for whichever requests happen to hit them. Reporting latency as percentiles instead — the p50, or median, alongside the p95 and p99 — reveals this tail behavior directly, since a system with an excellent median but a poor p99 has a real problem an average alone would mask entirely. Throughput, usually measured in queries served per second, and the number of distance computations a typical query performs are worth reporting alongside latency percentiles, since they explain why a given latency figure came out the way it did rather than simply restating that it happened.

What separates a fair comparison from a misleading one?

Two results are only meaningfully comparable when everything except the variable actually being studied stays fixed — the same hardware, the same thread count, the same dataset, the same distance metric, and results measured at the same recall level rather than at arbitrary, mismatched operating points. A benchmark comparing one configuration’s peak throughput against another’s average latency, or one method’s recall@1 against another’s recall@10, isn’t really comparing them at all, even if the resulting numbers get placed side by side in a table. Memory reporting deserves particular care: peak memory used during index construction is often noticeably higher than the steady-state memory an index settles into afterward, due to temporary buffers and candidate structures needed only while building, and conflating the two — or reporting one while implying the other — produces a number that doesn’t actually describe either quantity honestly.

Why does a single benchmark run not settle the question?

Random level assignment during construction, and nondeterministic insertion ordering under multithreaded builds, both mean that two builds of the same dataset with identical settings can produce graphs that behave slightly differently from each other. A single build’s results can’t distinguish a genuine difference between two configurations from ordinary build-to-build variance, so a rigorous benchmark repeats key measurements across multiple builds — ideally with different random seeds — and reports the resulting spread rather than treating one run’s numbers as definitive. Recording exactly which seeds and insertion order were used, alongside the hardware, thread count, and software version, is what makes a benchmark result something another person can actually verify or reproduce later, rather than a number that quietly can’t be checked against.

Sound methodology answers how to measure correctly; the next page turns to what to actually measure against — which datasets and benchmark suites suit which kinds of research questions, since a methodologically perfect benchmark run against the wrong dataset still produces a misleading picture of real-world performance. For the underlying recall formula referenced here written out with explicit mathematical notation, this site’s appendix on notation covers it directly.