Why space-partitioning trees fail on embeddings

Before graphs and inverted files, the standard answer to nearest-neighbour search was a tree. It is a genuinely elegant answer, it is exact, and it collapses on embedding data in a specific and instructive way. Understanding how it collapses explains why the two index families that survived look the way they do.

The naive approach

Scan everything. For ten million vectors that’s ten million distance computations per query, linear in the collection size and hopeless as it grows. We want to eliminate most of the collection without looking at it.

The classical move is the same one that makes sorted arrays searchable: divide, and use the division to rule out half.

The idea: cut the space in half, repeatedly

Pick a dimension. Find the median value of your points along it. Split: everything below the median goes left, everything above goes right. Recurse on each half, cutting along a different dimension each time, until the leaves are small.

build(points, depth):
    if |points| ≤ leaf_size: return Leaf(points)
    axis  ← depth mod d
    m     ← median of points along axis
    return Node(axis, m,
                build(points below m, depth+1),
                build(points above m, depth+1))

This is a k-d tree. It has depth logarithmic in the number of points, and searching it looks like searching a binary search tree:

search(node, query, best):
    if node is a Leaf:
        return closest of (best, points in leaf)
    near, far ← children of node on the query's side, and the other side
    best ← search(near, query, best)
    if |query[node.axis] − node.m| < d(query, best):     # the crucial line
        best ← search(far, query, best)                   # backtrack
    return best

Descend to the leaf containing the query, find the best point there, then walk back up. That is logarithmic descent, and on two-dimensional data it is close to magic — you touch a handful of leaves out of thousands.

The crucial line

Look again at the condition before the backtrack. That line is the reason the tree is exact rather than approximate, and it is also the reason it dies.

You have a current best candidate at distance r. You are standing at a node that split space at value m along some axis. The question is whether the far side could contain anything better. The nearest possible point on the far side is at least |query[axis] − m] away — the perpendicular distance from the query to the splitting plane. If that distance already exceeds r, nothing over there can beat what you hold, and the entire subtree is discarded, unexamined. This is a triangle-inequality argument, the same one every pruning method uses.

If the distance is smaller than r, you must search the far side too. There might be a point just across the plane, closer than your current best. The exactness guarantee requires it.

So the tree’s efficiency is entirely a bet that the pruning test usually passes. In two dimensions it does: the query is typically well inside a cell, r is small relative to cell size, and most planes are comfortably farther away than r.

How it fails

Now put the geometry of high dimensions into that test, and watch it stop passing.

Every cell is nearly all boundary. A cell in d dimensions has 2d faces. In 768 dimensions that’s 1,536 walls, and a point in the cell is close to a great many of them — recall that shaving a thin shell off every face of a high-dimensional box removes essentially all of its volume. So for a typical query, the perpendicular distance to many splitting planes is small.

r is not small. Because distances concentrate, the distance to the nearest neighbour is not much less than the distance to a random point. So the radius you’re testing against is comparable to the scale of the whole dataset, not to the scale of a cell.

Put those together: |query[axis] − m| is often small, r is comparatively large, the test fails, and you backtrack. Then you backtrack again. The pruning that was supposed to eliminate half the tree eliminates almost nothing, and the search degenerates into visiting nearly every leaf — with tree overhead on top of the scan it was meant to replace. A k-d tree on high-intrinsic-dimensional data is reliably slower than brute force, which is a rare and impressive way for a data structure to fail.

The standard rule of thumb is that k-d trees stop beating a linear scan once the number of dimensions grows past roughly the logarithm of the number of points. Ten million points is about 23 in base two. There is no reading of that under which 768 dimensions is fine.

The variants, and why they only postpone it

Every obvious repair has been tried, and each helps a little.

Cut along a good direction instead of an axis. Axis-aligned splits are arbitrary when the data’s variation doesn’t run along the axes. Splitting on the principal direction of the local point cloud, or on a random direction, produces better-shaped cells. This is a real improvement and it does not change the asymptotics.

Use balls instead of boxes. A ball tree or vantage-point tree partitions by distance to a chosen pivot rather than by a coordinate: inside a radius, or outside it. Balls fit concentrated-on-a-manifold data far better than boxes do, and the pruning test becomes a cleaner triangle-inequality bound. Same fate, later: once distances concentrate, the inner and outer shells both intersect the query’s candidate radius and both must be searched.

Give up exactness — stop early. This is the important variant, because it’s the bridge to everything modern. Cap the number of leaves examined: descend, collect, and quit after a budget rather than after the pruning test says you may. You lose the guarantee and gain a bounded cost, and the budget becomes a recall knob.

Use many trees and vote. Build several trees with different random split directions, search each to a limited depth, union the candidates, and rescore them exactly. Different random cuts strand different points, so a point missed by one tree is often found by another. This works, and it is the design of the randomised-forest ANN implementations that were widely used before graph indexes became standard.

What survived, and why

Notice what the two successful repairs are. The first is abandon the exactness guarantee and impose a budget. The second is generate a candidate set cheaply, then rescore it exactly. Both are now universal.

And notice what the surviving index families kept from the tree idea, and what they threw away.

Cluster indexes kept the partition and threw away the hierarchy. One flat level of cells defined by centroids rather than by planes, cells shaped by the data rather than axis-aligned, and no backtracking at all — instead you deliberately probe several cells, with the count as an explicit knob. The pruning test that couldn’t be trusted is replaced by an adjustable budget, which is exactly the k-d tree’s “stop early” repair, made honest and put in the user’s hands.

Graph indexes threw away the partition entirely. A tree imposes a global hierarchy of regions on data that may not have one; a proximity graph stores only local relationships — for each point, who is near it — and lets the search assemble a route. There are no cells to be near the boundary of, so the dominant high-dimensional geometric problem simply doesn’t arise in that form. Graph indexes have their own failure, local minima, but it is not an exponential one.

The lesson worth keeping

The thing that broke was not the tree. It was the demand for a proof that nothing better exists elsewhere. That proof requires a distance bound tight enough to exclude a region, concentration takes tight bounds away, and without them the pruning test becomes a formality that always says “keep looking.”

Every practical index in this field responds the same way: it stops trying to prove anything. It budgets. It searches a bounded amount, returns what it found, and reports no guarantee at all — which raises the question of what the word “approximate” is entitled to mean once you’ve given up proofs.