What is brute-force search?

Brute-force search finds the correct answer to a problem by exhaustively checking every possible option, guaranteeing correctness by never skipping anything, and in the context of nearest-neighbor search specifically it means computing the distance from a query to every single stored vector and simply keeping track of whichever ones turn out closest.

How does brute-force search actually apply to the specific problem of finding nearest neighbors?

Applied to nearest-neighbor search, brute-force search means computing a distance function, covered throughout this glossary, between the query vector and every single vector stored in the dataset, one at a time, and then simply keeping track of whichever vectors produced the smallest distances along the way. Once every vector has been checked, whatever’s left in that running tally is guaranteed to be the true, exact set of nearest neighbors, since nothing was skipped and every candidate got a fair, direct comparison. This is precisely why brute-force search is described as exact rather than approximate — there’s no risk of missing a genuinely closer vector, since every single one was checked directly.

How does brute-force search relate to the linear scan covered elsewhere in this glossary?

Brute-force search and a linear scan, covered elsewhere in this glossary, describe the same underlying idea from two slightly different angles: a linear scan describes the general strategy of checking every item in a collection one at a time, while brute-force search describes that exact same strategy specifically applied to the problem of finding the best-matching items according to some criterion, such as smallest distance to a query. Nearest-neighbor brute-force search is, in effect, a linear scan where the criterion being checked is distance rather than some other condition, which is why both concepts share the same fundamental cost: the amount of work required grows directly in proportion to how many vectors are stored, covered elsewhere in this glossary as a form of linear time complexity rather than the more favorable logarithmic scaling HNSW aims for.

Why does brute-force search remain genuinely useful even once a faster approximate method like HNSW is available?

Brute-force search’s guaranteed exactness makes it the standard tool for establishing ground truth, covered throughout this site’s coverage of evaluation and benchmarking, since measuring how well an approximate method like HNSW actually performs requires comparing its results against results that are known to be exactly correct. It also remains a perfectly reasonable choice on its own for genuinely small datasets, where the actual cost of checking every vector directly is negligible and doesn’t justify the added complexity of building and maintaining a more elaborate structure like HNSW’s graph.

Brute-force search’s guaranteed correctness makes it both the baseline HNSW is measured against and the tool used to verify HNSW’s own results are actually trustworthy. From here, the pages on linear scan and on recall as an evaluation metric cover the two places this exact, exhaustive approach gets put to direct use.