What is a greedy algorithm?

A greedy algorithm makes the choice that looks best right now, at each individual step, without looking ahead or reconsidering earlier decisions, and HNSW‘s search process is a direct application of this strategy: at each point in a search, it simply moves toward whichever neighboring vector currently looks closest to the query.

What exactly makes a strategy “greedy” rather than some more careful, forward-looking approach?

A greedy algorithm commits fully to whatever option looks most promising at the current step, using only the information immediately available, and never revisits that decision later even if a different choice might have turned out better in hindsight. This is a deliberate simplification compared to strategies that consider multiple possible paths forward before committing to one, since a greedy algorithm trades away that broader consideration in exchange for making each individual decision quickly and cheaply. The trade-off only pays off when the problem’s structure tends to reward locally good decisions with globally reasonable outcomes, which isn’t true for every problem but turns out to be true often enough, and specifically true for the kind of graph HNSW searches, to make greedy strategies genuinely useful.

How does HNSW’s search process actually apply this greedy strategy in practice?

Searching an HNSW graph, covered throughout this site’s coverage of how the algorithm searches step by step, means starting at some entry point and then repeatedly checking the current position’s neighboring vectors, moving to whichever neighbor is closest to the query, and continuing this process until no neighbor looks any closer than the current position already is. At no point does this process look several steps ahead to plan out a longer route, or reconsider a move it already made — it simply follows the locally best option at each individual step, which is precisely what makes it a greedy algorithm rather than a more exhaustive search strategy.

Why does this greedy approach work well enough for HNSW despite being a deliberate simplification?

Greedy search works well specifically because of the properties of the navigable small-world graphs HNSW builds, covered elsewhere on this site, where locally moving toward whatever looks closest tends to make genuine, steady progress toward the true nearest neighbors rather than getting stuck or wandering unproductively. The layered structure, covered throughout this site’s coverage of building the algorithm from scratch, reinforces this further by letting greedy search make large jumps across the graph in its upper, sparser layers before switching to smaller, more careful greedy steps in the denser bottom layer — this combination is what lets a fundamentally simple, locally-focused strategy produce results that are close to what a much more exhaustive search would find, without paying the cost of that more exhaustive search.

Recognizing HNSW’s search as a greedy algorithm clarifies why it’s fast — it never wastes effort planning ahead — while also explaining exactly why it’s approximate rather than exact, since a purely local, step-by-step strategy can occasionally miss a better path a more exhaustive search would have found. From here, the pages on how HNSW searches a graph step by step and on approximation algorithms fill in the two ideas this greedy strategy sits directly between.