What are ties in nearest-neighbor results?

Ties in nearest-neighbor results occur when two or more points sit at exactly, or almost exactly, the same distance from a query, making it genuinely ambiguous which of them should count as the kth-closest point and which should fall just outside the requested top-k cutoff. Ties might seem like a minor edge case, but they show up more often than intuition suggests, and they have real, practical consequences for how recall gets measured and how consistently a search system behaves across repeated runs.

Why do ties happen more often than people tend to expect?

Exact ties — two points at precisely identical distance from a query — are genuinely rare in continuous, real-valued vector data, since the odds of two independently computed floating-point distances landing on exactly the same value are vanishingly small in most realistic datasets. Near-ties, however, are far more common, and they cause exactly the same practical problems as exact ties even though the underlying distances aren’t mathematically identical. Two points might sit at distances that differ by such a tiny amount that floating-point rounding during the distance computation itself can’t reliably distinguish which one is actually closer, or the difference might be so small that it falls well within the range of what any reasonable measurement or approximation error could flip in either direction. For practical purposes, a near-tie behaves exactly like a true tie: there’s no meaningful, stable basis for confidently ranking one point ahead of the other.

Ties and near-ties become especially common in datasets with certain structural characteristics — data with many duplicate or near-duplicate points, data where an embedding model produces very similar vectors for genuinely different but closely related inputs, or data sitting in a region of the embedding space with unusually high local density, where many points naturally cluster close enough together that their distances to any given query end up nearly indistinguishable from one another.

Why does this ambiguity actually matter for benchmarking and recall measurement?

Ground truth, as covered on its own glossary page, is supposed to represent the single, unambiguous, correct answer to a nearest-neighbor query — but when a tie sits right at the boundary between the kth and (k+1)th closest points, there may genuinely be more than one equally valid way to define what the “true” top-k set actually is. If the ground truth computation arbitrarily picks one of several tied points to include in its top-k set, while an approximate method like HNSW happens to return a different, equally close tied point instead, a naive recall calculation would penalize the approximate method for a “miss” that isn’t really a meaningful error at all — both points were genuinely, defensibly correct answers, and the discrepancy reflects an arbitrary tie-breaking choice rather than any real shortcoming in the approximate search.

This is a genuine source of measurement noise in benchmarking that’s easy to overlook if a benchmark’s methodology doesn’t account for it explicitly. A rigorous benchmark either needs some principled way of handling near-ties — treating any point within a small tolerance of the kth-place distance as an acceptable match rather than demanding an exact match against a single, arbitrarily chosen ground-truth set — or needs to accept that recall measurements very close to a tie carry some inherent uncertainty that shouldn’t be misread as evidence of a flaw in the algorithm being tested.

Does the presence of ties affect how HNSW’s search algorithm actually behaves, beyond just benchmarking?

Yes, in a more subtle way tied to how HNSW‘s construction process works. Because HNSW builds its graph incrementally, with node insertion order affecting exactly which connections form during construction, a dataset with many tied or near-tied distances can end up with a graph whose specific connectivity depends somewhat on the arbitrary order in which those tied points happened to be inserted — this connects directly to the insertion-order-sensitivity and insertion-order-recall-variance concepts covered elsewhere in this documentation. Two builds of the same HNSW index, differing only in the order tied points were inserted, could produce graphs that behave slightly differently on queries that land near those tied regions, even though the underlying dataset and all the configuration parameters were identical in both builds.

This is generally a minor effect on well-distributed, realistic datasets, since ties are usually a small fraction of the overall data, but it’s worth being aware of specifically when debugging small, seemingly inexplicable discrepancies between repeated benchmark runs or between different builds of what should be an identical index — a discrepancy traced back to tie-handling and insertion order is a genuinely different root cause than a discrepancy caused by a real bug or misconfiguration, and conflating the two can send debugging effort in the wrong direction.

Having covered why ties and near-ties matter for both correctness measurement and construction-time behavior, the ground-truth-in-a-search-benchmark glossary page is worth revisiting with this added nuance in mind, since it’s the concept most directly affected by unresolved tie-handling in a benchmark’s methodology. From there, the insertion-order-sensitivity and insertion-order-recall-variance glossary pages, under HNSW construction concepts, go deeper into the related, construction-time consequences of ties and near-ties introduced here.