What is the curse of dimensionality?

The curse of dimensionality is the umbrella term for a collection of related, often counterintuitive effects that emerge as the number of dimensions in a space grows large — effects that make many techniques and intuitions which work perfectly well in two or three dimensions behave strangely, or stop working at all, once applied to the hundreds or thousands of dimensions typical of a real embedding space. It isn’t a single phenomenon with one cause; it’s a name for the whole family of ways that high-dimensional geometry departs from human spatial intuition, and understanding it is essential background for understanding why nearest-neighbor search needed a structure as specialized as HNSW in the first place.

Where does the phrase actually come from, and what does it cover?

The term originated in the context of optimization and statistics, describing how the amount of data needed to reliably estimate something grows explosively as the number of variables involved increases. If covering a one-dimensional range with reasonable density takes ten sample points, covering the equivalent two-dimensional grid takes roughly a hundred, and a ten-dimensional version of the same grid would need ten billion — the amount of data needed to maintain the same coverage grows exponentially with the number of dimensions, not linearly. This specific effect, sometimes called the sampling problem, is one strand of the curse, but the phrase has since broadened to cover a wider family of related phenomena that all share the same root cause: intuitions built from living in a three-dimensional world simply don’t generalize to spaces with hundreds or thousands of dimensions.

For nearest-neighbor search specifically, the two strands of the curse that matter most are distance concentration and the strange behavior of volume in high-dimensional space, both covered in more depth on their own glossary pages. Distance concentration describes how the distances from a fixed query point to a set of random points stop varying much as dimensionality grows, so that “near” and “far” become harder to distinguish meaningfully. The volume effect describes how, in high dimensions, almost all of a space’s volume ends up concentrated in a thin shell near the boundary of any region rather than spread through its interior, upending assumptions about how densely points fill a space that hold naturally at lower dimensions.

Why do these high-dimensional effects actually break search structures that work fine at low dimensions?

Many classical exact search structures — the kind that recursively split space into smaller regions to narrow down where a nearest neighbor might be — rely implicitly on the idea that splitting a space into halves, or into a handful of well-separated regions, meaningfully reduces the area a search needs to consider. That idea holds up well in two or three dimensions, where a small number of splits really does shrink the remaining search area substantially. In high-dimensional space, though, distance concentration means that most points end up looking roughly equally far from a query regardless of which “half” of the space they technically sit in, so a structure that prunes based on spatial partitioning ends up unable to rule out large swaths of the data with any confidence, and its search cost degrades toward something close to checking every point anyway — the exact brute-force search these structures were built to avoid in the first place.

This is the direct, practical reason approximate methods like HNSW exist at all. Rather than trying to exploit spatial partitioning the way exact tree-based structures do — an approach that the curse of dimensionality actively undermines once dimensionality gets high enough — HNSW builds a proximity graph based purely on which points are actually close to which other points, and searches that graph with a greedy traversal rather than a recursive spatial split. This sidesteps the specific failure mode that dooms partition-based structures in high dimensions, though it comes with its own trade-off: HNSW gives up the guarantee of finding the exact nearest neighbor in exchange for search performance that stays practical even as dimensionality grows.

Does this mean the curse of dimensionality makes accurate search impossible at high dimensions?

Not impossible, but it does mean that exactness and speed trade off against each other more sharply as dimensionality rises, which is exactly why approximate nearest-neighbor search exists as its own field rather than being a minor variant of exact search. It’s also worth being precise that real embedding vectors, despite having hundreds or thousands of raw dimensions, often don’t actually use the full geometric freedom that number of dimensions would suggest — a phenomenon usually described in terms of a dataset’s intrinsic dimensionality being much lower than its ambient dimensionality, meaning the data effectively lies on or near a lower-dimensional structure embedded within the larger space. This is part of why HNSW and similar graph-based methods can perform far better in practice on real embedding data than the worst-case theoretical picture of the curse of dimensionality alone would predict — real data is rarely as adversarially high-dimensional in effective terms as its raw vector length might suggest.

Having covered the curse of dimensionality as the umbrella concept, the distance concentration and high-dimensional sparsity glossary pages are the natural next stop for the two specific geometric effects that matter most directly for search. From there, the intrinsic dimensionality and local intrinsic dimensionality pages explain why real datasets often behave much better than the curse’s worst case would suggest, which is a large part of why approximate methods like HNSW work as well as they do in practice.