The curse of dimensionality, precisely

The curse of dimensionality is the most cited and least accurately stated idea in similarity search. The usual version — “high-dimensional space doesn’t work” — is false, and it’s obviously false, since 768- and 1536-dimensional retrieval works every day. But something real is going on, it does set a ceiling on what any index can do, and the precise statement is more interesting than the slogan.

The naive intuition, and why it’s reasonable

In two dimensions, spatial indexing is a solved problem. Cut the plane into a grid. To find points near a query, look in the query’s cell and the eight around it. You have eliminated the entire rest of the plane with nine cell lookups, and you can prove you haven’t missed anything within the cell radius.

The natural expectation is that this generalises: more dimensions, more cells, same idea. Cut each axis into a few intervals, look in the query’s cell and its neighbours, done.

How it fails, and the failure is arithmetic. In d dimensions, a cell has 3^d − 1 neighbours. At d = 20 that’s over three billion cells to examine to cover the immediate surroundings of one point. At d = 768 the number has no useful name. Meanwhile if you use only two intervals per axis, you have 2^768 cells and ten million points, so essentially every point sits alone in its own cell and the grid tells you nothing.

This is the first and simplest face of the curse: fixed-resolution partitioning of space costs exponentially in the number of dimensions, and there is no data volume that catches up. Any method whose cost has d in an exponent is finished before it starts.

Where the volume goes

The grid failure is a counting argument. The deeper phenomena are about where volume lives, and they’re worth building geometrically.

Take a cube of side 1 and shave a shell of thickness 0.05 off every face. The inner cube has side 0.9. In two dimensions the inner region keeps 0.9² = 0.81 of the volume — most of the square is interior. In ten dimensions it keeps 0.9^10 ≈ 0.35. In a hundred dimensions, 0.9^100 is about 0.000027: essentially all the volume is within 5% of a face.

In high dimensions, a region is nearly all boundary. Nothing is in the middle of anything. This is not an analogy; it’s the same exponential, and it has a direct operational consequence. Cluster indexes work by partitioning space and searching the partition your query lands in — and if almost every point of a cell is near that cell’s edge, then almost every query is a near-boundary query whose true nearest neighbour may sit just across the line in a cell you didn’t examine. The boundary problem in cluster indexes is not bad luck. It is the generic case, and it follows from where volume lives.

A second version of the same arithmetic: consider the fraction of a cube’s volume occupied by the largest ball inscribed in it. In two dimensions the circle covers about 79% of the square. As dimension rises, that fraction goes to zero — the ball vanishes and all the volume is in the corners. Any bounding-box argument therefore becomes an increasingly terrible approximation to a bounding sphere, which is one concrete reason tree indexes degrade.

Distance concentration, stated carefully

Now the phenomenon that actually sets the ceiling.

Draw points independently and uniformly from a d-dimensional cube, pick a query, and measure the distance from the query to every point. As d grows, those distances cluster together: the ratio between the farthest and the nearest approaches 1. The distribution of distances has a mean that grows with d and a spread that grows more slowly, so relative to the typical distance, everything is becoming the same distance away.

The consequence for search is severe. Every pruning argument works by showing that a candidate’s distance is provably worse than what you already hold. If the nearest point is at distance 10.0 and the thousandth is at 10.4, there is nothing to prune on. A lower bound of 10.1 excludes nothing. In the limit, “nearest neighbour” is a distinction so slight that no method can find it without checking essentially everything — and, worse, a distinction so slight that finding it may not be worth the trouble.

Now the careful part, because this is where the idea is usually overstated.

That result is a statement about a distribution: independent, identically distributed, spread across the full space. It is not a statement about the number of coordinates. Real embeddings are emphatically not uniformly distributed in their nominal space. They lie on a structured, curved, much lower-dimensional surface within it: correlated coordinates, dense clusters, large empty regions. The quantity that predicts whether concentration bites is the dimensionality of that surface — the intrinsic dimension — and it can be one or two orders of magnitude below the coordinate count.

So the honest statement is:

Similarity search becomes hard as the intrinsic dimensionality of the data rises, because distances concentrate and there is nothing left to prune on. The number of coordinates is at most a weak upper bound on that, and for learned embeddings it is a very loose one.

This is why a 1536-dimensional embedding index can perform beautifully and a synthetic 64-dimensional uniform dataset can be brutal. It also explains a common and confusing observation: reducing dimensionality often costs less recall than the numbers suggest, because you were never using that many effective dimensions.

What the ceiling looks like when you hit it

Concentration doesn’t announce itself. It shows up as an index that won’t tune. The signs:

Recall flattens well below what you want, and more search breadth or more probes barely moves it. You are on the flat part of the curve at an unhelpfully low height.
The distance to the 1st neighbour and the 100th are close together relative to their magnitude. This is directly measurable on a sample of queries with exact search, and it is the diagnostic worth running first.
Score distributions are narrow — unrelated items score well above zero and everything lands in a tight band, so no absolute threshold separates anything.
Exact search isn’t better. Run brute force on a sample of queries and compare the results by hand against the approximate ones. If exact results are no more useful, the index was never the problem.

That last one is the whole diagnostic, because it separates two failures with identical symptoms. An index that is losing recall to concentration and an embedding that doesn’t separate your data both present as “the results are mediocre and tuning doesn’t help.” Exact search tells them apart, since it has perfect recall by construction.

What can be done

Nothing on the index side, mostly — which is the point of naming it. If distances have concentrated, no traversal strategy recovers a margin that isn’t there. The levers are elsewhere:

Reduce the space to what’s actually used. If intrinsic dimension is far below nominal, a dimensionality reduction that keeps the structure loses little and improves the geometry the index has to work in. Some embedding families are explicitly trained so that a truncated prefix of the vector remains usable, which makes this cheap.

Add a signal that isn’t a distance. A rare token, an exact identifier, a date, a category. When every document is at the same distance, the discriminating information is not in the vector space, and combining a non-vector signal with the vector one is the only thing that recovers it.

Change the map. A different embedding model, or preprocessing that removes the boilerplate causing everything to look alike. If a corpus is four thousand instances of one template, the model is faithfully reporting that they are nearly identical.

Accept the approximation. If the 1st and 50th neighbours are genuinely near-equidistant, returning the 7th instead of the 1st is not an error worth spending latency on. Concentration cuts both ways: where it makes exact search hard, it also makes exact search less valuable.