kNN and the Curse of Dimensionality

TL;DR: kNN stores the training set and, at query time, labels a point by the majority vote (or average) of its k closest neighbors under a distance metric. It works well in low dimensions but degrades as dimensionality grows because distances concentrate: every point looks roughly equidistant, so "nearest" stops meaning anything. The same problem is why high-dimensional retrieval uses approximate nearest-neighbor indexes rather than exact brute-force search.

Lazy, instance-based learning

kNN does no training. There is no model to fit, no weights, no loss. You keep the labeled examples, and all the work happens at inference: for a query point, find the k closest training points and vote. That is why it is called lazy or instance-based. The decision boundary is implicit in the data and the metric.

The tradeoff is stark. Fitting is free and the method is non-parametric, so it can represent irregular boundaries with enough data. But every prediction searches the whole training set, so inference is O(n*d) per query with brute force, and you carry the entire dataset in memory forever. A model that costs nothing to train and everything to serve is the inverse of most ML, and that inversion is what interviewers like to poke at.

The metric is a modeling choice, not a default

People reach for Euclidean distance reflexively, but the metric is where most of the modeling lives. Euclidean assumes features share a scale, so an unscaled large-range feature (income in dollars) dominates a small one (age in years) and silently becomes the only thing kNN looks at. Standardize before you compute distances, every time.

Cosine distance ignores magnitude and compares direction, the default for text and embedding vectors where length encodes document size rather than meaning. Manhattan (L1) is less sensitive to outliers along any single axis. Picking k matters too: small k is low bias and high variance (jagged boundaries), large k smooths and can wash out minority classes. Cross-validate it, and prefer odd k for binary votes to avoid ties.

Why it falls apart in high dimensions

Here is the result that earns the name. In high dimensions, the distances from a query to its nearest and farthest training points converge: the ratio (max minus min) over min tends toward zero as d grows for many distributions. Everything becomes nearly equidistant, so a meaningful "nearest" neighbor evaporates.

A quick intuition: sample points uniformly in a unit hypercube. In 2D, neighbors are genuinely close. In 1000D, almost all the volume sits near the surface and corners, points sprawl into a thin shell, and pairwise distances cluster tightly around one value. kNN votes then come from points that are not actually similar, and accuracy collapses. You also need exponentially more data to keep any fixed density, the data-hunger side of the same coin.

The fix on the modeling side is to cut dimensions before measuring distance: PCA, UMAP, or a learned embedding that places semantically similar items close together. Embeddings work because they are dense and the dimensions carry signal, unlike a sparse one-hot blowup where most coordinates are noise.

From kNN to ANN at scale

Even with a good embedding space, exact kNN over millions of vectors is too slow: scanning every vector per query does not scale. Production retrieval uses approximate nearest-neighbor (ANN) indexes that trade a little recall for large speedups. HNSW builds a navigable small-world graph you greedily traverse; IVF partitions vectors into clusters and probes only a few; product quantization compresses vectors so more fit in memory. FAISS, hnswlib, and vector databases (Qdrant, Milvus, pgvector) implement these. Every RAG system you build is kNN with the brute force swapped for an ANN index, tuned to a recall-versus-latency target.

Why interviewers probe this

The interviewer is screening for whether you understand that distance is not free and not universal. The weak answer recites "find the k closest points and vote." The strong move names the two things that decide whether kNN works: feature scaling plus metric choice, and dimensionality. Then connect the curse of dimensionality to why we embed-then-index rather than run exact search, showing you see the line from a textbook algorithm to a production vector store. The held-back follow-up is "so how does a vector database find neighbors fast?", your cue to explain HNSW or IVF and the recall tradeoff.

Common misconceptions

• "kNN has no assumptions." It assumes your metric reflects similarity and features are comparably scaled. Skip standardization and the largest-range feature quietly takes over.
• "More features can only help." Past a point, extra dimensions dilute the signal through distance concentration and hurt kNN directly.
• "kNN is slow to train." It is instant to train and slow to predict, the opposite of parametric models.
• "ANN is a sloppy shortcut." It is a deliberate recall-for-latency trade; exact search is infeasible at scale, and tuned ANN keeps recall in the high 90s.

Key takeaways

• kNN is lazy and non-parametric: zero training cost, full-dataset search at inference, O(n*d) per query brute force.
• Scale features and choose the metric deliberately (Euclidean for scaled numerics, cosine for embeddings).
• The curse of dimensionality concentrates distances so "nearest" loses meaning; reduce dimensions or use learned embeddings first.
• At scale, exact kNN gives way to ANN indexes (HNSW, IVF, PQ) that trade a little recall for large speedups, the core of vector search.