What is an approximation algorithm?

An approximation algorithm deliberately trades away the guarantee of finding an exactly correct answer in exchange for finding a good-enough answer much faster than an exact method could, and HNSW is a textbook example of this trade-off applied to nearest-neighbor search specifically.

Why would deliberately giving up exactness ever be a reasonable design choice for an algorithm?

For plenty of computational problems, finding the exact, provably correct answer requires an amount of work that grows too quickly as the problem gets larger to remain practical, covered directly in this site’s early coverage of why nearest-neighbor search can’t just compare a query against every vector. An approximation algorithm accepts a small, usually well-controlled chance of returning a slightly suboptimal answer in exchange for a dramatic reduction in the work required to get there, which is a favorable trade whenever a near-perfect answer delivered quickly serves the actual task better than a perfect answer delivered too slowly to be useful.

How does HNSW specifically fit this description of an approximation algorithm?

HNSW searches its layered graph structure, covered throughout this site’s coverage of building the algorithm from scratch, by following promising-looking paths toward a query rather than exhaustively checking every single vector in the index, which means it can occasionally miss a stored vector that would technically have been a slightly better match than what it actually returns. This is precisely why HNSW is described as an approximate nearest-neighbor algorithm rather than an exact one — it deliberately accepts this small risk of missing the true best match in exchange for search times that scale far more favorably with dataset size than an exact brute-force comparison ever could, covered in this site’s page on what can actually be proven about the algorithm’s complexity.

How is the quality of an approximation algorithm like HNSW actually measured, given that it doesn’t guarantee exact correctness?

Since an approximation algorithm’s whole value proposition depends on how close its answers actually land to the exact, correct answer, measuring that closeness becomes essential, and for HNSW this is done through recall, covered throughout this site’s coverage of evaluation and benchmarking, which measures what fraction of the true nearest neighbors a search actually manages to find. A well-tuned HNSW index typically achieves recall in the very high nineties percent range, meaning it recovers the true best matches the overwhelming majority of the time, which is exactly the kind of favorable trade-off, near-perfect accuracy purchased at a small but real cost, that makes approximation algorithms broadly useful across computing rather than being a compromise reserved only for cases with no better option.

Recognizing HNSW as an approximation algorithm clarifies exactly what trade-off it’s making and why that trade-off is worthwhile for the vast majority of real-world search use cases. From here, the pages on recall as an evaluation metric and on average-case complexity dig further into how that trade-off gets measured and reasoned about in practice.