Why can’t nearest-neighbor search just compare a query against every vector?

Nearest-neighbor search cannot simply compare a query vector against every stored vector once a dataset grows past a modest size, because that approach’s cost scales directly with how many vectors exist: doubling the dataset doubles the work of every single search, and at millions or billions of vectors the arithmetic alone — before even accounting for the time spent moving that data through memory — takes far longer than an interactive application can tolerate.

How expensive is comparing a query against every vector, exactly?

A linear scan measures the distance from the query to each of the n stored vectors, and each of those distance computations costs work proportional to the vector’s dimensionality d, since every dimension has to be read and included in the calculation. That gives a total cost proportional to n times d for a single query. For a small collection — a few thousand vectors — this is fast enough that nobody notices. For a collection of ten million 768-dimensional vectors, a single query already means several billion individual arithmetic operations, and that cost has to be paid again for every subsequent query, not just once. Real systems rarely serve a single query either; a search engine or recommendation system might need to answer thousands of queries per second, which multiplies an already large per-query cost by a demand that keeps growing as the product succeeds.

Why can’t exact data structures like k-d trees rescue this the way they do in low dimensions?

The natural next idea is to avoid comparing against every vector by organizing the data so that large portions of it can be skipped. Structures such as k-d trees and R-trees do exactly this in two or three dimensions: they recursively partition space, and a query only needs to explore the partitions that could plausibly contain a closer point than what’s already been found, discarding the rest without ever computing a distance to them. This works well for the kind of low-dimensional data these structures were originally designed for — geographic coordinates, for instance — but the technique degrades sharply as dimensionality increases. The underlying reason is a geometric effect usually called the curse of dimensionality: as the number of dimensions grows, the distances between a random query and the points in a dataset stop varying much relative to each other, so almost every point ends up looking roughly equally close. A partitioning scheme that depends on some regions being clearly closer than others loses its power once that assumption breaks down, and in high dimensions a tree built this way ends up having to examine nearly every partition anyway — at which point it’s slower than a plain linear scan, not faster, because it now pays the overhead of tree traversal on top of visiting almost everything.

What options are left once neither brute force nor exact trees scale?

Once exact methods stop working, the only way forward is to accept an answer that’s very likely correct rather than guaranteed correct, in exchange for a large reduction in search cost — this is the approximate nearest neighbor family of techniques, and it splits into a few distinct approaches. Hashing-based methods, most commonly locality-sensitive hashing, project vectors through functions designed so that nearby vectors are more likely to land in the same hash bucket than distant ones, turning a search into a lookup within a handful of buckets instead of a scan of everything; the drawback is that these hash functions are fixed in advance and don’t adapt to the actual shape of a specific dataset, which tends to limit how accurate they can be at a given speed compared to methods that do adapt. Quantization and partition-based methods take a different route, learning a compressed representation or a clustering of the actual data — an inverted file index groups vectors into clusters and only searches the clusters nearest the query, while product quantization compresses each vector into a short code to shrink both memory use and comparison cost — and because these methods are built from the real data distribution rather than a fixed formula, they generally reach a given accuracy level faster than hashing does. The third family is graph-based search, which connects vectors to their neighbors and answers a query by walking the graph toward better candidates rather than scanning or hashing at all; this is the family HNSW belongs to, and understanding why a graph structure in particular solves this problem well is the subject of the next few pages.

From here, the most useful next step is to see how “closest” gets defined in the first place, since every technique described above depends on a specific way of measuring distance or similarity between vectors — that’s covered in the next chapter. If the geometric argument above raised more questions than it answered, the dedicated page on why high-dimensional geometry breaks traditional search structures goes into that effect in more depth. And if you want to see where this all leads, the homepage’s walkthrough of HNSW’s layered graph shows the specific graph-based solution this site is built around.