What is a search frontier?

A search frontier is the boundary of a graph traversal at any given moment — the set of nodes that have been discovered but not yet fully explored, sitting at the edge between the part of the graph the search has already processed and the part it hasn’t reached at all. In HNSW‘s base-layer search, the frontier corresponds directly to the contents of the candidate queue, and thinking about the search in terms of its expanding and contracting frontier offers a useful, visual way to understand how a best-first traversal actually moves through a graph over the course of a single query.

How does the frontier’s shape and composition actually change as a search progresses?

At the very start of a search, the frontier consists of just the single starting node handed off by upper-layer greedy descent, along with whatever neighbors that first expansion immediately reveals. As the search proceeds, each expansion pulls one node out of the frontier — removing it from the candidate queue and marking it visited — while simultaneously adding that node’s own unvisited neighbors into the frontier as fresh candidates. The frontier is therefore never static: it shrinks by one node every time an expansion happens, but it typically grows by however many new, previously undiscovered neighbors that expansion reveals, meaning the frontier’s overall size tends to fluctuate throughout the search rather than following any simple, predictable pattern.

This constant churn is exactly why the candidate queue needs an efficient way to always surface the closest remaining frontier node, as covered on its own glossary page — a frontier that’s continuously being added to and drawn from needs a structure that can keep up with that turnover without requiring a full re-sort every time its contents change.

Why is thinking in terms of a frontier a useful way to picture what a best-first search is actually doing, beyond just tracking a candidate queue?

The frontier framing emphasizes that a graph search, at any given instant, has a genuine boundary separating known territory from unknown territory — everything strictly inside the frontier has already been examined and won’t be revisited, everything strictly outside it hasn’t been discovered yet at all, and the frontier itself is where the search’s actual decision-making happens, since it’s only from among the frontier’s current members that the next expansion gets chosen. This is a useful mental picture specifically because it makes clear that a best-first search’s progress through the graph is really the frontier advancing outward from the starting point, always pushing into whichever direction currently looks most promising, rather than spreading out in every direction uniformly the way a strictly breadth-first traversal would.

Framed this way, HNSW‘s greedy preference for expanding the closest frontier node first is really a statement about which direction the frontier is allowed to advance in most eagerly — toward the query, rather than outward indiscriminately in whatever direction happens to reveal the most new nodes.

How does the frontier’s behavior connect to the stopping criterion that eventually ends the search?

The stopping criterion, covered on its own glossary page, is really a statement about the frontier’s remaining potential: once the closest node still sitting on the frontier is farther from the query than the worst entry already accepted into the results, nothing left on the frontier — and, by extension, nothing beyond it that the frontier hasn’t even reached yet — could possibly improve the final answer. In frontier terms, the search stops exactly when the frontier’s own closest edge has moved past the point where continuing to push it outward could do any more good, which is a slightly different but equivalent way of stating the same comparison already described in terms of the candidate and result queues directly.

Does the frontier ever include nodes that later turn out not to matter at all to the final result?

Yes, routinely — a node entering the frontier only means it’s been discovered as a neighbor of something already expanded, not that it will necessarily earn a place in the final result queue. Many nodes that pass through the frontier over the course of a search get examined, found to be farther from the query than the current worst accepted result, and discarded without ever influencing the final answer, even though they did briefly occupy a position on the search’s advancing boundary. This is entirely expected and not wasted effort in any problematic sense — examining these nodes is exactly how the search discovers their own neighbors, some of which might turn out to matter a great deal, even if the intermediate node itself ultimately doesn’t make the final cut.

Having covered the search frontier as a useful way to visualize how a best-first traversal’s boundary advances through the graph, the candidate-queue and stopping-criterion-in-HNSW-search glossary pages are worth revisiting together with this fuller framing, since the frontier is really just another lens on the exact same underlying mechanisms those pages describe more mechanically. From there, the local-minimum-in-graph-search glossary page, under recall and query difficulty, looks at what happens when the frontier’s advance stalls out in a way that hurts the final result.