Subscribe
AI
7 min read

What Is the Curse of Dimensionality? The Geometry Problem Behind Every Vector Database

The curse of dimensionality causes distance concentration, making nearest-neighbor search degenerate into random scanning. This post explains how modern vector databases use approximate algorithms and correlated embeddings to overcome these geometric challenges.

Visualization of high-dimensional vector space showing distance concentration and the concept of the curse of dimensionality in machine learning
Visualization of high-dimensional vector space showing distance concentration and the concept of the curse of dimensionality in machine learning

The curse of dimensionality refers to phenomena that arise in high-dimensional spaces, such as distance concentration, which causes the nearest neighbor of a query point to become as useful as a randomly chosen point. Modern vector search systems bypass this by utilizing embeddings with low intrinsic dimensionality and approximate nearest neighbor indexes like HNSW.

Every retrieval-augmented system on the market makes the same bet: take a chunk of text, compress it into a list of 1,536 or 3,072 numbers, and find the "nearest" list to a query. A body of theoretical work from the late 1990s says that bet should not pay off. In spaces that high-dimensional, distance stops meaning much of anything. The nearest neighbor of a query point converges in usefulness toward a randomly chosen point.

Vector search works anyway, most of the time. Understanding why is the clearest window into what embeddings actually are, and where the technology quietly stops working.

An old complaint from dynamic programming

The phrase "curse of dimensionality" was coined by Richard Bellman, who introduced it in his 1961 book Adaptive Control Processes while studying dynamic programming problems (Wikipedia). Bellman's complaint was arithmetic. Many algorithms divide a space into a grid of cells. If each dimension requires 100 cells to resolve the problem to a given precision, a two-dimensional problem needs 10,000 cells and a ten-dimensional one needs 10 to the twentieth power, an impossible number to store.

The same multiplication applies to data. A corpus that feels dense in three dimensions is nearly empty in 1,536. Volume grows exponentially with dimension, so the average distance between points explodes, and any fixed-radius neighborhood contains either everything or nothing.

When every neighbor is equally far

The version of the curse that should worry anyone shipping embeddings is distance concentration. In 1999, Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan and Uri Shaft formalized what makes nearest-neighbor search useful: not the absolute distance to the closest point, but the gap between the closest and the farthest. Their measure, relative contrast, is (distance to farthest - distance to nearest) / distance to nearest. They proved that under broad, general conditions on the data distribution, that ratio converges to zero as dimensionality grows (ICDT 1999, Springer). Once all distances are nearly the same, ranking by distance is ranking by noise, and nearest-neighbor lookup degenerates into scanning the database in effectively random order. The corollary they drew is that standard multi-dimensional index structures degrade to sequential scan in high dimensions.

Charu Aggarwal, Alexander Hinneburg and Daniel Keim sharpened the result in 2001, showing that relative contrast degrades roughly in proportion to 1/sqrt(d) as dimension d increases, for the usual distance norms, and that even the choice of metric only delays the collapse (On the Surprising Behavior of Distance Metrics in High Dimensional Space).

A related fact makes the geometry feel alien even when distances stay distinct: two random vectors in a high-dimensional space are almost always nearly perpendicular. The expected cosine similarity of random unit vectors is zero, and the spread around zero shrinks like 1/sqrt(d). In 1,536 dimensions, the typical random pair sits within a few hundredths of cosine similarity from zero, nearly all of them the same way (intuitive walkthrough at Towards Data Science). Practitioners have reproduced this directly; Erik Bernhardsson's simulation of sampled Gaussian points showed the distance to the farthest point converging onto the distance to the nearest as dimensions climbed (2015 blog post).

A point in high-dimensional space, nearly equidistant from every other point

What the theory forced into practice

Computer scientists responded by giving up on exact answers. Piotr Indyk and Rajeev Motwani's 1998 paper on locality-sensitive hashing, Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality, showed that if a query may return a neighbor within some factor of the true nearest, indexes with near-linear storage become possible. Every vector database today still lives inside that trade. The hierarchical graph indexes that dominate production retrieval, including HNSW (Malkov and Yashunin), and the libraries around them exist because exact search in thousands of dimensions is a brute-force affair, and because classical spatial trees are built for a world the scikit-learn documentation sums up plainly: KD-trees become inefficient as dimension grows (scikit-learn user guide).

Why embedding search works anyway

If the curse is so general, why does semantic search return relevant chunks? Because the theorems assume statistical independence between dimensions, and trained embeddings are the opposite of independent.

Aggarwal, Hinneburg and Keim's own follow-up work pointed at the escape hatch: when attributes are correlated, distance contrast is preserved, and the concentration result fails to bite. Text embeddings are correlations made numerical. The 1,536 axes of OpenAI's ada-002 embedding do not each carry a degree of freedom; they carry a small number of meanings smeared across many coordinates. Recent measurements put it precisely: a 2025 study of token embeddings found that while models nominally span hundreds or thousands of dimensions, their intrinsic dimension, the number of directions in which the data actually varies, is remarkably low and stabilizes early in training, while redundancy grows with model scale (Measuring Intrinsic Dimension of Token Embeddings, arXiv:2503.02142).

The industry has been exploiting the redundancy for years, mostly quietly. OpenAI's 2022 workhorse embedding model, ada-002, was already a cut to 1,536 dimensions, one-eighth the size of its davinci-era predecessor (OpenAI community thread citing the launch post). In January 2024, OpenAI shipped text-embedding-3-large at 3,072 dimensions with a dimensions API parameter that lets users truncate the vector to anything down to 256, reporting that even the 256-dimensional version outperforms a full-size ada-002 on retrieval benchmarks (OpenAI announcement). The trick traces to Matryoshka Representation Learning, a 2022 training method that packs information into a nested prefix of the vector so early dimensions carry the most signal (Kusupati et al., arXiv:2205.13147; Pinecone's analysis). Truncating from 3,072 to 256 is a tacit admission that the model never used most of its own dimensions.

A long vector compressed to a short one that returns the same results

The newest thread is formal theory catching up with the practice. A December 2025 paper, Breaking the Curse of Dimensionality: On the Stability of Modern Vector Retrieval, reframes the question from "do distances separate?" to "is retrieval stable," meaning: does nudging a query slightly change its result set? The authors prove conditions under which modern retrieval escapes the curse, and where it falls back in. Chamfer distance, the multi-vector aggregation used by late-interaction models, preserves stability; naive average pooling of vectors can destroy it. Filtered search gains stability when mismatched-filter penalties are large enough. Sparse retrieval needs overlap in where each document puts its mass. The paper's tone is not triumph; it is a map of where the curse still bites.

What a practitioner should take from this

Four concrete conclusions follow from the literature.

Distance values are not comparable across models or dimensionalities. Cosine 0.81 in one embedding space and 0.81 in another mean different things, because what matters is contrast against the rest of the distribution, a point the concentration results make unavoidable.

Dropping dimensions is cheap until it is not. Truncation works because intrinsic dimensionality is low; OpenAI's published benchmark of 256-dim beating full 1,536-dim is the strongest available evidence. The same literature says the degradation is gradual, not cliff-edged, until the truncated budget falls below the intrinsic dimension of the query workload.

Indexes are an apology for the curse. Any ANN system, including every major vector database, answers "approximately" precisely because exact high-dimensional search collapses toward brute force. Recall targets are a direct measurement of how much curse a given configuration swallowed.

Bigger vectors are not more capable. If scale keeps shrinking the useful dimensionality, as the intrinsic-dimension measurements suggest, the industry's vector inflation is redundancy, not knowledge. A 3,072-number list that behaves like a 200-number list is mostly a storage decision.

The curse of dimensionality was never disproven. It was engineered around, by correlating the dimensions on purpose and then pruning what the correlation made redundant. Whether the next generation of learned sparse and multi-vector retrievals keeps outrunning the 1999 theorems is an open research question, and one of the better places to watch theory and practice argue.

Sources

Frequently asked questions

Who coined the term "curse of dimensionality"?

Richard Bellman coined the phrase in his 1961 book Adaptive Control Processes while studying dynamic programming problems.

How does the curse of dimensionality affect nearest-neighbor search?

It leads to distance concentration, where the gap between the closest and farthest points converges to zero, causing ranking by distance to effectively become ranking by noise.

Why does embedding search work despite the curse of dimensionality?

Embedding search works because the data dimensions are correlated rather than statistically independent, preserving distance contrast and preventing the concentration result from taking effect.

What is Matryoshka Representation Learning?

It is a training method that packs information into a nested prefix of the vector, allowing users to truncate vectors (e.g., from 3,072 down to 256 dimensions) with minimal performance loss.

AILLMEducation