What is exhaustive search?

Exhaustive search checks every candidate in a search space to guarantee correctness, the general strategy that brute-force nearest-neighbor search applies specifically to vector search.
Created: Updated: 3 min read

Exhaustive search is the general strategy of systematically checking every possible candidate in a problem’s search space to guarantee the correct answer, and it’s essentially the same idea as brute-force search covered elsewhere in this glossary, just framed as a broader concept that applies well beyond the specific case of nearest-neighbor search.

Exhaustive search describes the underlying strategy of examining every single candidate solution to a problem without skipping any, which guarantees correctness precisely because nothing gets overlooked. Brute-force search, covered elsewhere in this glossary, is exhaustive search applied specifically to the nearest-neighbor problem: checking the distance from a query to every stored vector is exhaustive in exactly this sense, examining every candidate rather than narrowing the search down ahead of time. The two terms are frequently used interchangeably in the context of vector search, though “exhaustive search” is the broader term that applies to many kinds of problems beyond just finding nearest neighbors.

Why does the guarantee exhaustive search provides come at such a predictable, steep cost?

Because exhaustive search checks every candidate without exception, its cost scales directly with how many candidates exist to check, which is exactly the linear time complexity, covered elsewhere in this glossary, that makes it impractical for very large search spaces even though it’s conceptually simple and always correct. This trade-off, exact correctness purchased at a cost that grows directly with problem size, is precisely what motivates approximation algorithms, covered elsewhere in this glossary, like HNSW: they deliberately give up the guarantee that exhaustive search provides in exchange for a search cost that scales far more favorably as the search space grows.

Where does exhaustive search remain the right choice despite this steep scaling cost?

Exhaustive search remains entirely reasonable whenever the search space is small enough that its direct cost stays negligible, or whenever the specific task genuinely requires a guaranteed, exact answer rather than a fast approximate one, covered in this site’s page on brute-force search’s continued role in establishing ground truth for evaluation. The decision to move away from exhaustive search toward an approximate structure like HNSW is fundamentally a judgment call about scale: as a search space grows large enough that exhaustively checking every candidate becomes impractically slow, the case for accepting some approximation in exchange for tractable performance becomes correspondingly stronger.

Exhaustive search represents the conceptual starting point that approximation algorithms like HNSW are built specifically to improve upon, once a search space grows too large for exhaustively checking every candidate to remain practical. From here, the pages on brute-force search and on approximation algorithms work through exactly how and why that improvement gets made.