How does the curse of dimensionality affect KNN?

How to think about it

K-nearest neighbours (KNN), a method that predicts from the labels of the k training examples closest to a query, usually degrades as the number of feature dimensions grows. The curse of dimensionality makes local neighborhoods sparse, makes distances less informative, and makes exact search harder; approximate indexes address only the last problem.

Why KNN needs low-dimensional neighborhoods

KNN does not learn a global decision boundary in the usual sense. It stores the training examples. For a new example, it calculates a distance to each candidate, selects the k smallest distances, and predicts by majority vote for classification or by averaging their values for regression.

That process relies on a local-similarity assumption: examples close to one another should have similar outcomes. A feature dimension is one coordinate used to describe an example, such as age, transaction amount, or a word count. As dimensions accumulate, “close” becomes harder to achieve and harder to interpret.

There are two related effects.

First, the data becomes sparse. A small neighborhood occupies an extremely tiny fraction of a high-dimensional space. To find even five useful neighbours, KNN must often expand the neighborhood. Those extra points may cross several class boundaries, so the vote becomes less local and more biased.

Second, distances concentrate. The nearest point is still technically nearest, but it may be only marginally closer than thousands of other points. Small amounts of irrelevant noise can then change the ranking.

The geometric reason

A neighborhood with radius r in d dimensions has volume proportional to r^d. The constant depends on the distance metric, but the exponent is the important part.

Halve the radius and the volume is multiplied by 1 / 2^d. At 20 dimensions, that is a factor of 1,048,576. Under roughly uniform data density, keeping the same number of neighbours in a neighborhood half as wide would require about a million times more training examples.

The usual nearest-neighbour scaling makes the same point: the typical nearest distance decreases roughly like n^(-1/d), where n is the number of training examples. This is a rough relationship, because the exact value depends on the distribution, boundaries, and metric. But its implication is reliable:

• In two dimensions, multiplying the data by 100 reduces the characteristic radius by about 10 times.
• In 100 dimensions, multiplying the data by 100 reduces it by only about 4.5 percent, because 100^(-1/100) is about 0.955.

So “just collect more data” is sometimes the answer, but in genuinely high dimension the required amount grows exponentially. The spreadsheet becomes optimistic long before the budget does.

Why distances start looking alike

Consider two unrelated points whose coordinates are independent standard normal values, meaning each coordinate has mean zero and standard deviation one. Their coordinate-wise difference has variance 2. The squared Euclidean distance is therefore distributed like two times a chi-squared variable with d degrees of freedom.

Its mean is 2d, and its relative standard deviation is sqrt(2/d). The Euclidean distance itself has roughly half that relative spread.

At 100 dimensions, the squared distance has a relative spread of about 14 percent, while the Euclidean distance has a relative spread of roughly 7 percent. A typical distance is near sqrt(200), or 14.1. The points are not literally all the same distance away, but their relative differences are small.

KNN cares about ordering, not just average distance. If the useful signal changes a distance by a small amount while irrelevant dimensions contribute larger random changes, the wrong point can become the “nearest” point. In many common distributions, this is described informally as the nearest and farthest distances becoming relatively similar. The exact result depends on the distribution; it is not a law that every high-dimensional dataset must obey.

A concrete example

Imagine a support-ticket router using KNN. Each ticket has 100 standardized numeric features. The first feature captures the useful similarity between two tickets. The other 99 features are weak or irrelevant measurements.

The query has all-zero feature values. Candidate A is close in the useful feature but differs by 0.10 in every noise feature. Candidate B is much farther in the useful feature but happens to line up with the noise features:

import numpy as np

q = np.zeros(100)
a = np.array([0.05] + [0.10] * 99)
b = np.array([0.30] + [0.01] * 99)

print(np.linalg.norm(a - q))
print(np.linalg.norm(b - q))

The code prints approximately 0.996 for A and 0.316 for B, in that order. Euclidean KNN chooses B, even though A is much closer in the feature that actually matters.

The arithmetic explains the failure. A’s squared distance is 0.05² + 99 × 0.10², which is about 0.9925. B’s is 0.30² + 99 × 0.01², about 0.0999. Ninety-nine harmless-looking dimensions overwhelm one useful dimension.

This is why adding features can lower KNN accuracy even when every added feature is syntactically valid and has no missing values. Standard software is faithfully calculating an unhelpful metric.

The computational cost also gets worse

With n training examples and d features, brute-force KNN calculates n distances, each involving d coordinates. A query therefore costs roughly O(nd) time and the stored dataset costs roughly O(nd) space.

Low-dimensional indexes such as k-d trees can prune large regions. They calculate a lower bound on the distance to a region and skip that region when it cannot contain a better neighbour. In high dimensions, those regions overlap heavily from the query’s point of view, so little can be pruned. The search approaches brute force.

Approximate nearest-neighbour systems such as HNSW-based indexes or FAISS can reduce latency by searching only promising parts of the index. That is valuable when the dataset is large. But they solve a retrieval problem, not a statistical one. If the exact nearest neighbours are not label-similar because the feature representation is poor, returning them faster does not improve the prediction.

What I would do in production

For the ticket router, I would first compare three representations: the useful feature subset, all 100 features, and a reduced representation. That ablation tells me whether the extra dimensions add signal or merely perturb the ranking.

I would make the metric part of the model design. Numeric features measured in different units should usually be standardized or otherwise scaled; otherwise a feature measured in dollars can dominate one measured in seconds. But scaling is not a cure for irrelevant dimensions.

Warning — common misconception. Standardizing 100 noise features gives them equal influence; it does not remove their influence. Fit the scaler using training data only, and perform it inside each cross-validation fold.

Next, I might use feature selection, supervised metric learning, or dimensionality reduction. PCA can help by projecting the data onto fewer directions, but PCA preserves directions of high input variance, not necessarily directions that predict the label. A rare fraud signal, for example, may have low variance and be discarded by an overly aggressive PCA projection. Choose the number of components using the downstream validation metric, not variance explained alone.

I would tune the preprocessing, metric, and k together. A small k preserves locality but has high variance: one noisy neighbour can change the result. A large k reduces variance but expands the neighborhood, increasing bias. There is no universally correct value such as 5 or 10.

Finally, if the representation is sound but the dataset is too large for brute-force search, I would add an approximate index and measure both recall of true neighbours and end-to-end prediction quality.

The senior nuance

The number of stored columns is not the whole story. Intrinsic dimensionality means the number of independent degrees of freedom that really govern how the data varies. A dataset with 100 columns may lie near a two-dimensional surface and remain friendly to KNN. Conversely, 20 independent, noisy dimensions can already be difficult.

The metric matters just as much. Euclidean distance may suit scaled numeric features. Cosine distance is often more sensible for text vectors when direction matters more than magnitude. A learned embedding may make semantic neighbours close, but its nominal size, such as 768 dimensions, does not guarantee a useful geometry. The embedding still needs validation.

I would favour KNN when the dataset is modest, the similarity metric is meaningful, the effective dimension is low, and the decision boundary is irregular. I would be cautious when features are numerous and uncurated, memory is limited, or prediction latency is strict. A linear model is often a stronger baseline for sparse TF-IDF text because it can combine many weak signals without requiring a dense local neighborhood.

A failure mode you can diagnose

A common symptom is perfect or near-perfect training accuracy followed by poor validation accuracy. With one-neighbour KNN, a training example is its own nearest neighbour, so a 100 percent training score is expected and mostly meaningless.

On held-out queries, inspect whether the nearest neighbours have stable labels. Also compare the k-th distance with the first distance using d_k / d_1. If that ratio is close to one across many queries and neighbour labels barely beat the class-prior baseline, the distance ranking is probably losing useful contrast. Compare the full feature set with a carefully selected subset. If removing features improves validation performance, the curse was not theoretical; it was in the feature table.

What they’ll ask next

Does PCA always fix the problem?
No. PCA helps when the discarded directions are mostly noise and the retained geometry preserves label-relevant similarity. It can hurt when predictive information has low variance. Fit and select it inside cross-validation.

Do HNSW or FAISS solve the curse of dimensionality?
They mainly solve the computational part by avoiding exhaustive search. They can make retrieval faster, but they cannot make irrelevant dimensions informative or create class separation that the representation does not contain.

How do you choose k?
Tune it with cross-validation alongside the metric and preprocessing. Small k gives a local, high-variance estimate; large k smooths noise but may cross decision boundaries. Distance weighting can help when closer points are genuinely more trustworthy, but concentrated distances make those weights nearly equal.

Say this in the interview

KNN suffers in high dimensions because neighborhoods become sparse and distances concentrate, so irrelevant features can determine which points appear nearest; I would fix the representation and metric first, then use dimensionality reduction or feature selection, and only afterward optimise the neighbour index.