Why exact nearest-neighbor search breaks in high dimensions, and why approximation is the only way forward.
Part 1 of Approximate Nearest Neighbors
Nearest-neighbor search is one of the simplest problems you can state. You have a set of points. A query arrives. Return the closest point. The definition of "closest" is usually Euclidean distance, and in two dimensions you can check the whole thing visually.
Move your cursor over the figure below. A query point tracks your position, and the k nearest points light up in amber. Use the slider to change how many neighbors you want.
The naive algorithm is direct: compute the distance from the query to every point, sort, and return the k smallest. This is called exact search, and it costs O(N) per query. For a few thousand points, it runs in a blink. It is also the only way to be sure you have the true nearest neighbors.
With a little cleverness you can do much better than O(N). A kd-tree recursively splits the space along alternating axes, building a tree whose leaves are small regions containing a handful of points. To answer a query, you descend to the leaf containing the query, then only check other branches if they might contain a closer point than the ones you have already seen.
The pruning step is where the savings come from. Once the search has a candidate point at distance r, any branch whose bounding region is farther than r can be skipped entirely. In two dimensions, with a reasonable dataset, a kd-tree query runs in something close to O(log N). This is a strictly better deal than scanning everything, and until the late 1990s it was the standard answer.
Modern machine learning rarely lives in two dimensions. A sentence embedding from a current language model sits in a 768- or 1536-dimensional space. An image embedding might be 2048-dimensional. The "points" we actually want to search through are these long, opaque vectors of floats. So the question is: does kd-tree-style cleverness carry over?
The short answer is no, and the reason has to do with the geometry of high-dimensional space itself. Two related effects show up as the dimension grows: volume collapses into corners, and distances collapse onto each other. Both of them break the assumptions that make kd-trees work.
Start with a cube of side 2 in d dimensions, and inscribe a ball of radius 1 inside it. In two dimensions, the ball fills about 78% of the square. In three dimensions, a sphere fills about 52% of the cube. In ten dimensions, the ball fills about a quarter of one percent of the cube. Most of the volume is in the corners.
This is not a cute mathematical curiosity. It means that if you sample points uniformly inside a high-dimensional cube, almost none of them land near the center. They all pile up near the boundary. This is why high-dimensional data is often described as living on a thin shell.
Volume concentration has a direct consequence for nearest-neighbor search. If you generate N random points in d dimensions and look at the histogram of all pairwise distances, something surprising happens as d grows: the histogram narrows. Distances concentrate around a single value. The nearest point and the farthest point become almost the same distance away.
There is some nuance here worth flagging. Real embedding spaces are not uniformly random. Sentence embeddings cluster by topic, image embeddings cluster by content. That local structure is exactly what makes high-dimensional nearest-neighbor search possible at all. But the ambient geometry is still hostile, and any algorithm that tries to be fully exact in high dimensions pays a heavy price.
The kd-tree's speed came from pruning. A branch gets pruned when its bounding region is farther than the current best candidate. In high dimensions, two things conspire to kill this: the candidate distance is roughly the same everywhere (distance concentration), and the bounding regions along any one axis cover only a small slice of the geometry (volume concentration). The pruning test almost always says "could contain a closer point, please check." The tree degenerates into a linear scan, with extra overhead.
The choices at this point are narrow. You can accept linear scans, which become impractical past a few million vectors. You can give up on exact answers and start returning approximate nearest neighbors. Almost all modern vector search systems take the second path, and they do it well enough that the gap between exact and approximate is usually imperceptible to the application sitting on top.
Modern ANN is three ideas stacked on top of each other, each addressing a different aspect of the problem:
The next article introduces the first of these: partitioning. We will see that the same trick kd-trees tried to pull off can work in high dimensions, if you are willing to accept that the answer will be usually right instead of always right.