What is beam search width?

Beam search width is the general term, borrowed from a broader family of search algorithms, for the number of candidates a best-first search keeps actively under consideration at once rather than committing to a single path — in HNSW‘s specific case, this is exactly what efSearch controls at the base layer, so beam search width and efSearch describe the same underlying idea, with efSearch being HNSW‘s particular name and setting for that width. Understanding the term in its more general sense clarifies why HNSW’s search behaves the way it does, and situates HNSW’s specific approach within a much broader tradition of search algorithms that make the same fundamental trade-off between thoroughness and speed.

What does “beam” actually refer to, and why is that a useful way to picture this kind of search?

The name comes from imagining the search as a beam of light illuminating a set of promising paths simultaneously, rather than a single narrow ray following just one path at a time. A pure greedy search, as covered on its own glossary page, is effectively a beam of width one — it commits to a single current-best position and abandons every alternative the moment it moves on, with no way to reconsider a path it passed over. A beam search with a wider beam keeps multiple promising candidates active simultaneously, hedging against the risk that any single one of them turns out to be a dead end, at the cost of doing proportionally more work to maintain and evaluate that larger set of active possibilities.

This framing makes clear that beam width sits on a spectrum rather than being a binary choice — a width of one gives the cheapest, most greedy behavior, and progressively wider beams trade increasing computational cost for a progressively lower risk of missing a good answer because the search happened to abandon a productive path too early.

How does this general concept map onto HNSW’s specific base-layer search, mechanically?

HNSW’s base-layer search doesn’t use the term “beam” directly in its usual description, but the underlying mechanism is exactly a beam search: the result queue, sized to efSearch, is functionally the beam — it holds the set of currently active best candidates, and the search’s stopping criterion is tied directly to how wide the result queue is allowed to grow. A larger efSearch widens this beam, keeping more candidates under active consideration and requiring the closest remaining unexplored option to beat a correspondingly weaker threshold before the search concludes. A smaller efSearch narrows the beam, tightening that threshold and letting the search settle for a smaller, more quickly-assembled set of results.

This is precisely why efSearch functions as HNSW’s beam-width control even though it’s introduced elsewhere in this documentation primarily as a target result-set size — the two framings describe the identical mechanism from two complementary angles, one emphasizing what gets returned, the other emphasizing how many active candidates the search is willing to track along the way.

Why does the beam-search framing matter for understanding HNSW’s behavior beyond just its own specific terminology?

Recognizing HNSW’s base-layer search as an instance of the broader beam-search family clarifies that the fundamental trade-off it makes — wider exploration buys better odds of finding the true answer, at higher computational cost — isn’t something unique or specific to HNSW’s particular design. Beam search, and the same width-versus-thoroughness trade-off, shows up across a wide range of other search and optimization problems entirely unrelated to nearest-neighbor search, which means intuitions about how beam width generally behaves — diminishing returns past a certain point, increasing but bounded benefit from widening the beam, sensitivity to how good the underlying scoring function actually is — transfer directly to reasoning about efSearch’s effect on HNSW specifically, even for someone encountering HNSW’s own terminology for the first time.

Does HNSW’s upper-layer greedy descent count as a beam search too, or is it something categorically different?

The upper-layer greedy descent, as covered on its own glossary page, is specifically the width-one special case of beam search — it tracks exactly one active candidate at a time, with no wider beam to speak of. This is worth stating explicitly, since it shows that HNSW’s two search phases aren’t using two entirely unrelated strategies, but rather two different points along the same beam-width spectrum: the upper layers use the narrowest possible beam because their job only needs a single good handoff point, while the base layer uses a deliberately wider beam, controlled by efSearch, because its job of producing accurate final results benefits meaningfully from hedging against the risk any single greedy path might turn out to be a dead end.

Having covered beam search width as the general concept underlying HNSW’s specific efSearch parameter, the efSearch and base-layer-search glossary pages are worth revisiting together with this fuller framing in mind, since they describe the identical mechanism using HNSW’s own specific vocabulary. From there, the greedy-navigation and best-first-search glossary pages round out the picture, showing the narrow and wide ends of this same beam-width spectrum as they actually get used in HNSW’s two distinct search phases.