What is ground truth in a search benchmark?
Ground truth, in the context of a search benchmark, is the exact, correct answer to a nearest-neighbor query — the true k closest points to a given query, computed by exhaustive search rather than by whatever approximate method is actually being evaluated. It’s the fixed reference point every measurement of recall depends on: without knowing what the genuinely correct answer to a query actually is, there’s no way to say how close an approximate search’s results came to getting it right, which makes ground truth the foundation underneath essentially every benchmark number reported anywhere in the HNSW literature or in practical tuning work.
How does ground truth actually get computed for a benchmark dataset?
Ground truth is produced by running exact nearest-neighbor search — a full, brute-force linear scan comparing a query against every single point in the dataset — for each query in a benchmark’s test set, and recording exactly which points come out as the true k closest matches. This is precisely the exhaustive search approach that HNSW and every other approximate method exist to avoid at production scale, but for the purposes of establishing ground truth, that same slowness is a feature rather than a drawback: an exhaustive scan is, by construction, guaranteed to find the genuinely correct answer, since it checks every single candidate with no shortcuts or approximations involved anywhere in the process.
Because computing exact results this way is expensive, ground truth is typically computed once, ahead of time, for a fixed set of benchmark queries against a fixed dataset, and then reused across many different evaluation runs — testing different HNSW parameter settings, different implementations, or entirely different algorithms — without needing to be recomputed each time. This is a sensible division of labor: ground truth only needs to be correct, and only needs to be computed once per dataset and query set, while the actual benchmarking work of comparing various approximate methods against that fixed reference can happen repeatedly and cheaply by comparison.
Why does recall depend so completely on having reliable ground truth to compare against?
Recall, as covered on its own glossary page, measures what fraction of the true k nearest neighbors an approximate search actually managed to find, out of the k it was asked to retrieve. That definition is only as meaningful as the ground truth it’s measured against — if the “true” answer used for comparison is itself wrong, computed with a flawed distance function, an incorrect k, or a buggy exhaustive-search implementation, then every recall number calculated against it inherits that same error, regardless of how carefully the approximate method being tested was actually implemented or tuned. This is why establishing correct, trustworthy ground truth is treated as a foundational, non-negotiable step in rigorous benchmarking methodology, worth getting right before any comparison of approximate methods is attempted at all.
A specific, easy-to-make mistake worth calling out explicitly: ground truth has to be computed using the exact same distance function that the approximate search being evaluated is configured to use. Computing ground truth with Euclidean distance and then evaluating an HNSW index configured to search using cosine distance produces a comparison that looks like a recall measurement but is actually comparing answers to two different questions, since “nearest” means something different under each distance function. Any meaningful recall measurement requires that the ground truth and the system under test agree completely on what “nearest” is actually supposed to mean.
Does ground truth ever need to account for ties or near-ties among candidates?
Yes, and this is a subtlety that a careless benchmarking setup can easily get wrong. When multiple points sit at exactly the same distance from a query, or close enough to it that floating-point precision makes their exact ordering ambiguous, there may be more than one equally valid set of “true k nearest neighbors” — the exact boundary between the kth and (k+1)th closest point isn’t always as clean and unambiguous as the concept of ground truth might suggest at first glance. This connects directly to the ties-in-nearest-neighbor-results glossary page, and rigorous benchmark methodology generally needs some explicit convention for handling this ambiguity, whether that means treating any point within some small tolerance of the kth-place distance as an acceptable match, or accepting that recall measurements near a genuine tie carry some inherent, unavoidable uncertainty that shouldn’t be mistaken for noise in the approximate algorithm being tested.
Having established what ground truth is and why every recall measurement depends entirely on it being computed correctly, the recall-based approximation glossary page is the natural next stop, since it defines precisely how ground truth gets turned into the actual recall metric used throughout benchmarking work. From there, the ties-in-nearest-neighbor-results and reproducibility-manifest glossary pages, along with the fuller treatment in the evaluation-and-benchmarking chapter, go deeper into the practical care required to make sure a ground-truth comparison actually measures what it claims to measure.