What is range-aware termination?
Range-aware termination is the specific stopping logic a range search needs, replacing HNSW‘s ordinary result-queue-based stopping criterion — built around a fixed number of results, k — with a rule based instead on a fixed distance threshold, since a range query has no target count of results to fill and therefore no natural “worst entry” for the ordinary criterion to compare against. It’s the piece of machinery that makes range search, covered on its own glossary page, actually work correctly on top of a search structure whose native stopping logic was designed with top-k queries specifically in mind.
Why doesn’t HNSW’s ordinary stopping criterion work as-is for a range query?
The ordinary stopping criterion compares the closest remaining candidate in the candidate queue against the worst entry currently held in a fixed-size result queue, and concludes the search once the former can no longer beat the latter — a rule that depends entirely on the result queue being capped at a specific target size, k. A range query has no such target size at all: it wants every point within a given distance of the query, however many that turns out to be, which means there’s no fixed-size result queue to compare against and no natural “worst entry” threshold the way a top-k search has. Applying the ordinary stopping criterion unmodified to a range query simply doesn’t make sense, since the entire comparison it relies on assumes a result set with a bounded, predetermined size.
What does range-aware termination actually use instead, to decide when a range search has done enough?
Rather than comparing against a result queue’s worst entry, range-aware termination compares the closest remaining candidate in the candidate queue directly against the query’s own fixed distance threshold. Once that closest remaining candidate is itself farther from the query than the threshold, every other candidate still waiting in the queue — all of which are, by the queue’s own distance ordering, at least as far away — must also fall outside the threshold, meaning none of them could possibly qualify as a valid range-search result. At that point the search can safely conclude, having already found and retained every candidate encountered so far that fell within the threshold, without needing to check any of the remaining candidates individually.
This is structurally very similar to the logic behind HNSW‘s ordinary stopping criterion — both rules exploit the candidate queue’s distance ordering to rule out an entire remaining set of candidates through a single comparison rather than checking each one — the only real change is what the closest remaining candidate actually gets compared against: a result queue’s worst entry for top-k search, or a fixed threshold for range search.
Does range-aware termination require any other changes to the search besides this different comparison?
Because a range search’s result set has no fixed size, the bookkeeping structure holding accepted results also has to change from a capped result queue to something that can grow to hold however many qualifying candidates actually get found — potentially very few, potentially quite a lot, depending on how the underlying data happens to be distributed around the query and how generous the distance threshold is. Every candidate found within the threshold gets retained in this open-ended collection rather than competing for a fixed number of slots the way top-k results do, which is exactly the structural difference described on the range-search glossary page between a fixed-count and a fixed-threshold query pattern.
Does range-aware termination guarantee the same kind of correctness that HNSW’s ordinary stopping criterion provides for top-k search?
The termination logic itself is sound in the same sense the ordinary criterion is — once the closest remaining candidate provably can’t qualify, nothing else remaining could qualify either, so stopping loses nothing relative to what the search’s own traversal was actually able to discover. What range-aware termination doesn’t change is the underlying approximate nature of HNSW’s greedy traversal itself: exactly as with top-k search, a range query run against HNSW has no guarantee that every point genuinely within the threshold actually gets found, since the search could still miss a qualifying point that happened to sit down a path the greedy traversal never explored, for all the same local-minimum and query-difficulty reasons that affect top-k search. Range-aware termination correctly stops the search once it’s confident nothing further would help, but it inherits, rather than resolves, the same approximate-search trade-off that runs through every other HNSW query pattern.
Having covered how range-aware termination adapts HNSW’s stopping logic to a fixed-threshold query rather than a fixed-count one, the range-search and stopping-criterion-in-HNSW-search glossary pages are worth revisiting together with this fuller picture of exactly what changes and what stays the same between the two query patterns. From there, the recall-based-approximation glossary page is worth rereading with range search specifically in mind, since the same fundamental measurement concerns apply whether the underlying query asked for a fixed count or a fixed distance threshold.