The Curse of Dimensionality: Why Distances Stop Meaning Anything, and Why Learning Works Anyway

Draw 1,000 points uniformly at random in the unit cube \([0,1]^{1000}\), add one more as a query, and measure Euclidean distances. The nearest point sits about 12.1 units away. The farthest sits about 13.6 away. Every candidate lies inside a band roughly 12% as wide as the distance to the nearest one. In 10,000 dimensions the band shrinks below 4%. The question "which point is closest?" has quietly stopped having an interesting answer.

This is distance concentration, a theorem since 1999 (Beyer et al., 1999, ICDT). Yet retrieval systems run nearest-neighbour search over 768- to 4,096-dimensional embeddings billions of times a day and mostly return the right documents. The work is in explaining why, and in knowing which parts of the curse still bite.

Why this matters: Every k-NN classifier, kernel method, clustering routine and embedding retriever assumes that small distances mean similar things. The curse of dimensionality says exactly when that assumption fails, and its escape clauses (low intrinsic dimension, smoothness, learned representations) say what your data must look like for it to hold.

TL;DR

• With independent coordinates, the spread of distances shrinks relative to their mean as \(1/\sqrt{d}\): for uniform data the coefficient of variation of Euclidean distance is about \(0.59/\sqrt{d}\).
• In a 1,000-point simulation, relative contrast \((D_{\max}-D_{\min})/D_{\min}\) falls from 82 at \(d=2\) to 2.7 at \(d=10\), 0.44 at \(d=100\) and 0.036 at \(d=10{,}000\).
• Fractional norms raise the constant (0.70 for \(\ell_{0.5}\) against 0.44 for \(\ell_2\) at \(d=100\)) but not the rate; across 25 databases, \(k\)-NN accuracy with \(\ell_{0.5}\), \(\ell_1\) and \(\ell_2\) was statistically indistinguishable (Mirkes et al., 2020).
• Hubness is the symptom retrieval feels: skewness of the 5-occurrence distribution for Gaussian data rises from 0.12 at \(d=3\) to 19.2 at \(d=100\) (Radovanović et al., 2010).
• The curse runs on intrinsic, not ambient, dimension: ImageNet has 150,528 values per image but an intrinsic dimension of 26 to 43 (Pope et al., 2021), and 10 latent dimensions written into 1,000 coordinates keep 25 times the contrast of i.i.d. data.
• Ambient dimension costs samples: at smoothness 2, halving root-mean-squared error at the minimax rate takes about 6x more data in one dimension and 128x more in ten (Stone, 1982).
• Single-vector retrieval has a separate dimensional ceiling: the extrapolated breaking point for returning every pair of documents is about 500k documents at \(d=512\) (Weller et al., 2025).

At a Glance

flowchart LR
    A["Ambient dimension d grows"] --> B["Volume moves to corners and shell"]
    B --> C["Distances concentrate"]
    C --> D["Relative contrast tends to 1"]
    C --> E["Hubs emerge near the centre"]
    D --> F["k-NN, kernels, indexes degrade"]
    E --> F
    G["Low intrinsic dimension"] --> H["Contrast set by m, not d"]
    I["Smoothness priors"] --> H
    J["Learned representations"] --> H
    H --> K["Neighbours stay meaningful"]

    classDef blue fill:#1e40af,stroke:#3b82f6,stroke-width:1px,color:#fff
    classDef purple fill:#6d28d9,stroke:#a78bfa,stroke-width:1px,color:#fff
    classDef teal fill:#0e7490,stroke:#22d3ee,stroke-width:1px,color:#fff
    classDef amber fill:#b45309,stroke:#fbbf24,stroke-width:1px,color:#fff
    classDef emerald fill:#047857,stroke:#34d399,stroke-width:1px,color:#fff
    classDef rose fill:#be123c,stroke:#fb7185,stroke-width:1px,color:#fff

    class A blue
    class B,C purple
    class D,E amber
    class F rose
    class G,I,J blue
    class H emerald
    class K teal

The left chain is the theorem. The right chain is the set of conditions under which the theorem does not describe your data.

From Bellman's Grid to Hubs in Embedding Space

The phrase is Richard Bellman's, from Dynamic Programming (Princeton University Press, 1957), and it was about counting, not distance: a value function tabulated with 10 grid points per state variable needs \(10^d\) cells, so ten state variables need ten billion before anything is computed.

Statisticians turned counting into sample complexity. Stone proved that no estimator of a \(p\)-times differentiable function of \(d\) variables can drive mean squared error down faster than \(n^{-2p/(2p+d)}\) (Stone, 1982, Annals of Statistics 10(4)). Dimension sits in the exponent, and because the bound is minimax over the function class, no algorithm recovers it.

The database community met the geometric version the hard way. Tree indexes prune regions provably far from the query. Weber, Schek and Blott showed that partitioning and clustering indexes degrade to linear complexity in high dimension, and that a plain sequential scan beat them on average above roughly 10 dimensions (Weber et al., 1998, VLDB). Nothing is provably far when everything is about equally far.

Beyer, Goldstein, Ramakrishnan and Shaft then asked whether nearest neighbour is even meaningful, and proved a sufficient condition under which the farthest-to-nearest ratio converges to 1. Aggarwal, Hinneburg and Keim studied the \(L_k\) family and recommended \(L_1\) and fractional norms as contrast-preserving (Aggarwal et al., 2001, ICDT). That advice became folklore, and the next two decades mostly dismantled it.

timeline
    title Curse of Dimensionality, from Counting to Retrieval
    1957 : Bellman coins the curse in Dynamic Programming
    1982 : Stone proves minimax rates for nonparametric regression
    1998 : Weber, Schek and Blott show indexes lose to linear scan near 10 dimensions
    1999 : Beyer et al. prove nearest neighbour can become meaningless
    2001 : Aggarwal, Hinneburg and Keim recommend L1 and fractional norms
    2007 : Francois, Wertz and Verleysen show fractional distances concentrate too
    2009 : Durrant and Kaban prove a converse for latent-variable data
    2010 : Radovanovic et al. identify hubness
    2012 : He, Kumar and Chang tie relative contrast to LSH cost
    2021 : Pope et al. estimate ImageNet intrinsic dimension at 26 to 43
    2025 : Weller et al. bound single-vector retrieval capacity by dimension

François, Wertz and Verleysen showed that concentration is intrinsic to the distances and that fractional distances concentrate too (François et al., 2007, IEEE TKDE 19(7)). Durrant and Kabán proved the converse practitioners wanted: for linear latent-variable data, distances do not concentrate while the number of relevant dimensions grows no slower than the total (Durrant and Kabán, 2009, Journal of Complexity 25(4)).

[IMAGE: Three-panel figure. Left: a 2D grid of 10 by 10 cells labelled "100 cells". Middle: a 3D cube of 1,000 cells. Right: a log-scale bar reaching 10^10 for d = 10. Caption: "Bellman's curse was about counting: a grid that is cheap in two dimensions costs ten billion cells in ten."]

How Distance Concentration Actually Works

Three mechanisms get filed under "the curse" and they fail differently: volume, concentration of measure, and hubness.

Volume runs to the corners and the skin

The volume of a \(d\)-dimensional ball of radius \(r\) is

Inscribe a ball of radius \(1/2\) in the unit cube. It fills 78.5% of the square at \(d=2\), 0.25% of the cube at \(d=10\), and about \(1.9\times10^{-70}\) at \(d=100\). The Gamma function in the denominator outgrows \(\pi^{d/2}\), so nearly all the cube's volume sits in its \(2^d\) corners. The fraction of a ball's volume in an outer shell of relative thickness \(\varepsilon\) is

so the outer 1% of the radius holds 2% of the volume at \(d=2\) and 63% at \(d=100\).

For local methods, the decisive form is neighbourhood size. A sub-cube holding a fraction \(f\) of uniform data has edge

Holding 1% of the data takes edge 0.10 at \(d=2\), 0.63 at \(d=10\), and 0.955 at \(d=100\). A "local" neighbourhood spans 95% of every coordinate's range, so local averaging stops being local and the bias of \(k\)-NN and kernel smoothers explodes.

[IMAGE: Line chart, d from 1 to 100. Three curves: inscribed-ball-to-cube volume ratio on a log axis collapsing toward zero; fraction of ball volume in the outer 1% shell rising toward 1; edge length needed to capture 1% of data rising from 0.01 to 0.955. Caption: "Three views of one geometry: the centre empties, the skin fills, neighbourhoods stop being local."]

Concentration is the law of large numbers applied to distance

Take \(x, y\) independent and uniform on \([0,1]^d\). The squared distance is a sum of \(d\) independent terms:

The difference \(u = x_j - y_j\) has triangular density \(1-|u|\) on \([-1,1]\), so

Each term has mean \(1/6\) and variance \(1/15 - 1/36 = 7/180\). The squared distance therefore has mean \(d/6\) and standard deviation \(\sqrt{7d/180}\): the mean grows like \(d\), the spread like \(\sqrt{d}\). By the delta method the coefficient of variation of the distance is half that of its square:

That \(1/\sqrt{d}\) is the whole phenomenon. Any distribution with independent coordinates and finite fourth moments gives the same rate with a different constant; for standard Gaussians, \(\|x-y\|^2\) is \(2\chi^2_d\) and the relative spread of distance is about \(1/\sqrt{2d}\).

Beyer et al. stated the general version without independence. With \(D_{\min}\) and \(D_{\max}\) the nearest and farthest of \(n\) distances from a query,

If a random point's norm, relative to its mean, stops fluctuating, every point ends up at essentially the same distance. The theorem fixes \(n\) as \(d\) grows, so larger databases partly compensate. And the condition is on the distribution, not the coordinate count: data whose relative norm keeps fluctuating escapes at any dimension.

Relative contrast, the quantity to measure

Two definitions circulate. Aggarwal et al. and Mirkes et al. use \((D_{\max}-D_{\min})/D_{\min}\), which tends to 0. He, Kumar and Chang use

the typical distance over the nearest-neighbour distance, which tends to 1 (He et al., 2012, ICML). Via the central limit theorem they approximate

where \(\phi\) is the standard normal CDF, \(n\) the database size, \(p\) the norm, and \(\sigma'\) the normalised standard deviation of the summed per-coordinate terms. Dimension enters only through \(\sigma'\), which falls as \(1/\sqrt{d}\) for independent coordinates. They then prove that the same quantity controls locality-sensitive hashing cost: lower contrast forces more hash tables for the same success probability.

Fractional norms: more contrast, same fate

Aggarwal et al. showed that for i.i.d. data the absolute contrast \(D_{\max}^{k} - D_{\min}^{k}\) of the \(L_k\) distance scales like \(d^{1/k - 1/2}\): growing for \(k=1\), bounded for \(k=2\), vanishing for \(k\ge3\). Hence the advice to prefer Manhattan or fractional distances.

The algebra holds, but relative contrast still vanishes for every \(k\), because \(D_{\min}\) grows like \(d^{1/k}\). Mirkes, Allohibi and Gorban tested the practical claim directly. Fractional quasinorms do have larger relative contrast than \(\ell_2\), yet "the distance concentration shows qualitatively the same behaviour for all tested norms", the differences decay with dimension, and on 25 databases with 37 binary classification problems \(k\)-NN with \(\ell_{0.5}\), \(\ell_1\) and \(\ell_2\) did not differ significantly (Mirkes et al., 2020, Entropy 22(10):1105). A better constant does not change the rate.

Hubness: concentration's second-order effect

Concentration says all distances are nearly equal. Hubness is what happens inside the "nearly". Let \(N_k(x)\) count the points whose \(k\) nearest neighbours include \(x\). In low dimensions \(N_k\) is roughly symmetric around \(k\). In high dimensions it becomes heavily right-skewed: a few hubs appear in very many neighbour lists and many anti-hubs appear in none.

The mechanism: points lie near a sphere around the data mean, but distance to the mean keeps non-negligible variance at finite \(d\). A point slightly closer to the centre is slightly closer to everyone, and because all distances are compressed together, that small edge wins thousands of neighbour lists. On 10,000 i.i.d. points, Radovanović et al. measured \(N_5\) skewness of 0.121, 1.541 and 5.445 for uniform data at \(d=\) 3, 20 and 100, and 0.118, 2.055 and 19.210 for Gaussian data. Across 50 real datasets, \(N_{10}\) skewness correlated with dimension and more strongly with maximum-likelihood intrinsic dimension, and hubs sat near cluster centres (Radovanović et al., 2010, JMLR 11). A hub whose label disagrees with its neighbours spreads that error across a classifier; a hub document gets retrieved for queries it has nothing to do with.

Seeing It in Motion

Why does learning survive? Each escape route breaks a different assumption of the concentration theorem.

flowchart TB
    T["Concentration theorem assumptions"]
    subgraph Break["Assumption broken"]
        A1["Coordinates independent"]
        A2["Target function arbitrary"]
        A3["Metric fixed in advance"]
    end
    subgraph Rescue["Escape route"]
        R1["Low intrinsic dimension"]
        R2["Smoothness and structure priors"]
        R3["Learned representations"]
    end
    O1["Contrast set by intrinsic dimension m"]
    O2["Sample cost set by function class"]
    O3["Distance aligned with the task"]
    T --> A1
    T --> A2
    T --> A3
    A1 --> R1 --> O1
    A2 --> R2 --> O2
    A3 --> R3 --> O3

    classDef blue fill:#1e40af,stroke:#3b82f6,stroke-width:1px,color:#fff
    classDef purple fill:#6d28d9,stroke:#a78bfa,stroke-width:1px,color:#fff
    classDef rose fill:#be123c,stroke:#fb7185,stroke-width:1px,color:#fff
    classDef emerald fill:#047857,stroke:#34d399,stroke-width:1px,color:#fff

    class T rose
    class A1,A2,A3 blue
    class R1,R2,R3 purple
    class O1,O2,O3 emerald

Low intrinsic dimension. Concentration needs many independent sources of variation; real data has few. With the Levina–Bickel maximum-likelihood estimator, Pope et al. put MNIST at 7 to 13 and ImageNet at 26 to 43, and found that intrinsic dimension tracked the samples needed to learn while extrinsic dimension "has little impact on generalization" (Pope et al., 2021, ICLR). Kpotufe proved \(k\)-NN regression converges at rates set by local intrinsic dimension (Kpotufe, 2011, NIPS).

Smoothness and structure priors. Stone's exponent has \(2p\) beside \(d\); assuming smoothness, additivity or sparsity changes the function class and so the rate. Linear models, convolution and weight sharing are all priors of this kind.

Learned representations. Ansuini et al. found the intrinsic dimension inside trained networks "orders of magnitude smaller than the number of units in each layer", with the final-layer value predicting test accuracy and the effect absent in untrained networks (Ansuini et al., 2019, NeurIPS). An embedding model builds a metric in which the theorem's hypotheses fail.

A production dense retriever meets every face of the curse on one query.

sequenceDiagram
    participant U as User query
    participant E as Embedding model
    participant I as ANN index
    participant N as Hubness correction
    participant R as Reranker
    U->>E: Raw text
    E->>E: Map onto learned low-dimensional manifold
    E->>I: Centred, normalised 768-d vector
    I->>I: Graph walk, effort grows as contrast falls
    I->>N: Top 200 candidates with cosine scores
    Note over N: Subtract each candidate's typical similarity to a query bank
    N->>R: Re-scored top 50
    R->>U: Final top 10

[IMAGE: Two side-by-side PCA scatter plots. Left: 5,000 i.i.d. points in 1,000 dimensions, a structureless blob, with an inset histogram of pairwise distances as a narrow spike. Right: 5,000 points from a 10-dimensional latent space mapped into 1,000 dimensions, visibly structured, with a wide distance histogram inset. Caption: "Same ambient dimension, different intrinsic dimension: the distance histogram tells you which world you are in."]

By the Numbers

Sources: Weber et al. (VLDB 1998), Radovanović et al. (JMLR 2010), He et al. (ICML 2012), Pope et al. (ICLR 2021), Mirkes et al. (Entropy 2020), Nielsen and Hansen (NLDL 2024), Weller et al. (ICLR 2026). LIMIT corpus sizes are the authors' extrapolation from free embeddings, not measurements on trained models.

GIST has three times SIFT's ambient dimension, a larger 85%-variance dimension (71 against 40) and under half its contrast: contrast tracked effective dimension.

[IMAGE: Scatter plot of the 50 real datasets from Radovanović et al., x-axis MLE intrinsic dimension, y-axis skewness of N_10, with a fitted trend line and a second faint series using ambient dimension on a log x-axis for contrast. Caption: "Hubness follows intrinsic dimension more closely than it follows the number of features."]

A Concrete Example

Setup: \(n = 1{,}000\) database points uniform in \([0,1]^d\), a random query, Euclidean distance. Predict nearest, mean and farthest distances by hand, then check against simulation.

Step 1: moments of squared distance. Mean \(\mu = d/6\), standard deviation \(s = \sqrt{7d/180}\). At \(d=100\): \(\mu = 16.67\), \(s = 1.972\). At \(d=1{,}000\): \(\mu = 166.67\), \(s = 6.236\).

Step 2: extremes of 1,000 draws. For a near-Gaussian sum, the minimum of \(n\) draws sits near the \(1/n\) quantile, about \(3.09\) standard deviations below the mean for \(n=1{,}000\), and the maximum symmetrically above.

• \(d=100\): nearest squared distance \(16.67 - 3.09\times1.972 = 10.57\); farthest \(22.76\).
• \(d=1{,}000\): nearest \(166.67 - 3.09\times6.236 = 147.40\); farthest \(185.94\).

Step 3: square roots. \(d=100\): \(D_{\min}=3.25\), \(D_{\text{mean}}\approx\sqrt{16.67}=4.08\), \(D_{\max}=4.77\). \(d=1{,}000\): \(D_{\min}=12.14\), \(D_{\text{mean}}=12.91\), \(D_{\max}=13.64\).

Step 4: contrast. \(d=100\): \((4.77-3.25)/3.25 = 0.47\) and \(C_r = 4.08/3.25 = 1.26\). \(d=1{,}000\): \((13.64-12.14)/12.14 = 0.124\) and \(C_r = 1.063\). The nearest neighbour is only 6% closer than a typical point; embedding noise of a few percent would reshuffle the top results.

Step 5: check against simulation. NumPy, seed 0, averaged over 100 queries:

The hand predictions (0.47 and 1.26; 0.124 and 1.063) land within 7% of the measured values. At \(d=10\) the Gaussian shortcut fails outright, predicting a negative squared distance (\(1.667 - 3.09\times0.624\)), because ten terms are too few for the central limit theorem, and contrast there is still healthy.

Step 6: fractional norms. \(\ell_{0.5}\) beats \(\ell_2\) by a factor of 1.59 at \(d=100\) and 1.47 at \(d=10{,}000\), while both collapse about thirteenfold between those dimensions.

Step 7: intrinsic dimension. Now sample a 10-dimensional uniform latent and map it into 1,000 dimensions with a fixed random Gaussian matrix. Ambient dimension is still 1,000. Measured contrast is 2.92 and \(C_r\) is 2.61, close to genuinely 10-dimensional data (2.73 and 2.48) and 25 times the i.i.d. 1,000-dimensional value. The linear map carries the latent geometry, so distances inherit its contrast.

Step 8: cosine space. Random unit vectors at \(d=768\) have cosine similarity with mean 0 and standard deviation \(1/\sqrt{768}\approx0.036\), so a relevant document at 0.45 would stand ten deviations clear. But contextual representations are not isotropic in any layer (Ethayarajh, 2019, EMNLP): unrelated pairs share a common direction and score well above zero, which shrinks contrast, manufactures hubs, and breaks fixed cosine thresholds across models.

Where It Breaks

Kernel methods lose their bandwidth

A Gaussian kernel \(\exp(-\|x-y\|^2/2h^2)\) is informative only when squared distances vary on the scale of \(h^2\). Under concentration they all sit near \(d/6\) with spread \(\sqrt{7d/180}\). Small \(h\) makes the Gram matrix nearly diagonal; large \(h\) makes it nearly constant. The usable band narrows as \(1/\sqrt{d}\), which is why SVMs and Gaussian processes on raw high-dimensional features usually need feature selection first.

k-NN fails through bias, then through hubs

At \(d=100\) a neighbourhood holding 1% of the data spans 95% of each axis, so bias dominates. Low intrinsic dimension repairs the bias but not necessarily the hubs: errors cluster around a handful of training points, which one \(k\)-NN graph pass measuring \(N_k\) skewness will reveal.

Indexes spend their budget on contrast

Graph indexes such as HNSW prune by distance, and He et al. tie LSH cost to relative contrast. Lower contrast means visiting more of the graph or more hash tables for the same recall. Swap to an embedding model with lower effective contrast and ANN recall can drop with no configuration change, so re-benchmark against exact search whenever the model changes.

Anisotropy and dimensionality reduction

Concentration arguments assume a centred distribution. Under cosine similarity a shared offset inflates every score and turns documents aligned with it into hubs. Reduction is subtler. Radovanović et al. found hubness under PCA stays roughly flat until the intrinsic dimension is reached and only changes once information is being lost. Random projections preserve pairwise distances within \(1\pm\varepsilon\) using \(O(\log n/\varepsilon^2)\) dimensions, and so preserve concentration faithfully. Neither adds contrast the data lacked.

Capacity limits no metric can fix

Weller et al. connect single-vector top-\(k\) retrieval to sign-rank and show that for a fixed dimension some document combinations cannot be the top-\(k\) for any query. On their LIMIT benchmark of deliberately simple queries, state-of-the-art embedders "struggle to reach even 20% recall@100" while BM25 does far better (Weller et al., 2025). Raising \(d\) therefore cuts both ways: more combinatorial capacity, but lower contrast if the added directions are noise.

[IMAGE: Log-scale histogram of k-occurrence counts N_10 for a 100,000-document embedding corpus, long right tail with three labelled hubs (a cookie-policy page, a table of contents, a generic FAQ) each in over 2,000 neighbour lists, and a spike at zero labelled "anti-hubs, never retrieved". Caption: "Hubness in a real retriever: a few generic documents answer everything and much of the corpus is unreachable."]

Alternative Designs

The first three rows fight the concentration rate and cannot beat it; the rest change what is measured. CSLS subtracts each candidate's mean similarity to its neighbours and "drastically increases" unsupervised word translation accuracy (Conneau et al., 2018). QB-Norm brings the idea to cross-modal retrieval "without requiring retraining" (Bogolin et al., 2022, CVPR).

How It Is Used in Practice

Diagnose before tuning. Sample queries, compute \(C_r = D_{\text{mean}}/D_{\min}\) per query and the skewness of \(N_{10}\) over a document sample. \(C_r\) near 1.05 means small noise reorders your top results; skewness in double digits means hubs, and the fix belongs in the similarity function, not the index.

Estimate intrinsic dimension. MLE and TwoNN (which needs only first- and second-neighbour distance ratios) run on a sample in minutes. Report a range: Pope et al.'s ImageNet estimate moves from 26 at \(k=3\) to 43 at \(k=10\).

Centre, then normalise. Subtracting the corpus mean before cosine search costs one vector subtraction per item and often recovers contrast lost to anisotropy.

Correct hubs where they appear. For sentence embeddings, Nielsen and Hansen report about 75% less hubness and about 9% error improvement on the pretrained Sentence-BERT models they tested (Nielsen and Hansen, 2024, NLDL).

Keep a lexical path. As of September 2026, fusing BM25 with dense scores is a common production default, and LIMIT gives it a theoretical justification: some relevant combinations are unreachable by one dense vector of a given size.

Treat embedding dimension as capacity, not quality. Benchmark truncated or projected variants on your own queries before assuming bigger is better.

[IMAGE: Retrieval-health dashboard with four panels: (1) histogram of query-to-corpus cosine scores with top-1 marked; (2) per-query C_r distribution with a red band below 1.1; (3) N_10 skewness across two embedding model versions; (4) ANN recall@10 against exact search. Caption: "Four numbers that tell you whether the curse is biting your retriever."]

Insights Worth Remembering

1. The curse is a theorem about independent coordinates, not vector length. Data driven by a few latent factors violates its hypothesis at any coordinate count: 10 latent dimensions in 1,000 coordinates kept 25 times the contrast.

2. Ambient dimension costs samples; intrinsic dimension costs meaning. Stone puts \(d\) in the exponent for arbitrary smooth functions, but \(k\)-NN adapts to intrinsic dimension. Estimate the intrinsic one.

3. Changing the norm changes the constant, never the rate. Across 25 databases the \(k\)-NN accuracy difference was not significant.

4. Hubness is the curse retrieval actually feels. Concentration makes everything equidistant; hubness decides who wins the ties. Generic documents in thousands of result lists are a geometric effect, not a relevance bug.

5. Relative contrast is a latency budget. It governs LSH and graph-search effort, so a new embedding model can slow an index or cut its recall with no index change.

6. Learned representations are metrics built to break the theorem. Trained networks compress into representations far narrower than their layers, and only when they generalise.

Open Questions

What is intrinsic dimension for corpora that are only locally low-dimensional? MLE and TwoNN assume locally uniform density on a manifold, and estimates shift with neighbourhood size (26 to 43 on ImageNet). Whether a single number, a local field, or a multiscale profile is the right description for a text embedding corpus is unsettled.

Where does hubness in contrastive embedders come from? The link to intrinsic dimension is measured on 50 classical datasets, and anisotropy in transformer representations is measured, but how much modern hubness comes from geometry versus training-data frequency structure has not been cleanly separated.

Do single-vector capacity limits bind on natural corpora? Weller et al. prove the limit and build a benchmark where it binds; their critical corpus sizes are extrapolated from free embeddings. Whether production query distributions hit those limits at the predicted scale is an open empirical question.

Sources and Further Reading

1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.
2. Stone, C. J. (1982). "Optimal Global Rates of Convergence for Nonparametric Regression." The Annals of Statistics, 10(4), 1040-1053. Project Euclid
3. Weber, R., Schek, H.-J., & Blott, S. (1998). "A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces." VLDB 1998, 194-205. dblp
4. Beyer, K. S., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999). "When Is 'Nearest Neighbor' Meaningful?" ICDT 1999, LNCS 1540, 217-235. Technical report TR1377
5. Aggarwal, C. C., Hinneburg, A., & Keim, D. A. (2001). "On the Surprising Behavior of Distance Metrics in High Dimensional Space." ICDT 2001, LNCS 1973, 420-434. dblp
6. François, D., Wertz, V., & Verleysen, M. (2007). "The Concentration of Fractional Distances." IEEE TKDE, 19(7), 873-886. PDF
7. Durrant, R. J., & Kabán, A. (2009). "When Is 'Nearest Neighbour' Meaningful: A Converse Theorem and Implications." Journal of Complexity, 25(4), 385-397. doi:10.1016/j.jco.2009.02.011
8. Radovanović, M., Nanopoulos, A., & Ivanović, M. (2010). "Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data." JMLR, 11, 2487-2531. JMLR
9. Kpotufe, S. (2011). "k-NN Regression Adapts to Local Intrinsic Dimension." NIPS 2011. Proceedings
10. He, J., Kumar, S., & Chang, S.-F. (2012). "On the Difficulty of Nearest Neighbor Search." ICML 2012. arXiv:1206.6411
11. Ansuini, A., Laio, A., Macke, J. H., & Zoccolan, D. (2019). "Intrinsic Dimension of Data Representations in Deep Neural Networks." NeurIPS 2019. arXiv:1905.12784
12. Ethayarajh, K. (2019). "How Contextual are Contextualized Word Representations?" EMNLP 2019. arXiv:1909.00512
13. Mirkes, E. M., Allohibi, J., & Gorban, A. (2020). "Fractional Norms and Quasinorms Do Not Help to Overcome the Curse of Dimensionality." Entropy, 22(10), 1105. doi:10.3390/e22101105
14. Pope, P., Zhu, C., Abdelkader, A., Goldblum, M., & Goldstein, T. (2021). "The Intrinsic Dimension of Images and Its Impact on Learning." ICLR 2021. arXiv:2104.08894
15. Conneau, A., Lample, G., Ranzato, M., Denoyer, L., & Jégou, H. (2018). "Word Translation Without Parallel Data." arXiv:1710.04087
16. Feldbauer, R., & Flexer, A. (2019). "A Comprehensive Empirical Comparison of Hubness Reduction in High-Dimensional Spaces." Knowledge and Information Systems, 59(1), 137-166. Springer
17. Bogolin, S.-V., Croitoru, I., Jin, H., Liu, Y., & Albanie, S. (2022). "Cross Modal Retrieval with Querybank Normalisation." CVPR 2022. arXiv:2112.12777; with Nielsen, B. M. G., & Hansen, L. K. (2024). "Hubness Reduction Improves Sentence-BERT Semantic Spaces." NLDL 2024. arXiv:2311.18364
18. Weller, O., Boratko, M., Naim, I., & Lee, J. (2025). "On the Theoretical Limitations of Embedding-Based Retrieval." ICLR 2026. arXiv:2508.21038

Free to read, no ads, no sign-up. If it was useful you can buy me a coffee.