K-Nearest Neighbours
Predict by looking at the most similar examples you've already seen — no training at all, and the ancestor of every vector search you use today.
When not to use it
- On high-dimensional raw features. Distances concentrate and "nearest" stops meaning anything. Embed first, or don't use it.
- When prediction latency matters and the dataset is large. Every query compares against everything. Approximate indexes exist, and then you're building a vector database.
- Without scaling. It is nothing but distance. Unscaled features mean one column decides everything.
- On imbalanced data, naively. The majority class dominates the neighbourhood by construction. Weight or resample.
Reach for something else instead
- Vector database with an ANN index — kNN at scale. This is what you actually want when the data is big.
- Random forest — usually better on tabular data and doesn't need scaling.
- Logistic regression — faster at prediction time, gives probabilities.
- Learned embeddings + kNN — the modern combination, and the one that works.
Unscaled, it is a working-looking model that uses one column.
Two features on their natural units: age in years, income in pounds. Euclidean distance squares the difference in each, so a £12,000 gap contributes 12,000² and a 30-year gap contributes 900 — the age term is not outweighed, it is annihilated. Watch the neighbourhood shape: unscaled it is a flat band, because the only way to be near is to have similar income. The model still runs, still returns neighbours, still reports an accuracy. It is simply not using age at all, and nothing in the output says so.
The full account
The oldest algorithm, and it still wins sometimes
Cover and Hart proved something remarkable about nearest neighbours in 1967, before almost any of modern machine learning existed. As the sample size grows without bound, the error rate of the 1-nearest-neighbour rule is bounded above by twice the Bayes error — twice the theoretical minimum achievable by any classifier that knows the true distribution perfectly.
An algorithm with no training, no parameters, and no assumptions gets within a factor of two of optimal, for free, given enough data. That result is why kNN never went away. It is the honest baseline: if your gradient-boosted ensemble cannot beat kNN on your problem, the problem is your features, not your model.
The failure the figure shows
kNN has no parameters, which means it has no way to learn that some of your columns matter more than others. It treats every dimension as equally important because you never told it otherwise, and you cannot tell it otherwise.
The figure above computes what that costs. Take a dataset with age in years (range ~50) and income in dollars (range ~100,000). Euclidean distance squares each difference and adds them. Income differences are measured in thousands, age differences in tens — so income contributes roughly a million times more to the squared distance. Age accounts for about 0.01% of the distance. It is not down-weighted; it is annihilated. The algorithm is now a very slow income-only classifier. Scale the features and accuracy goes from 67% to 84% — same data, same k, same everything, one line of preprocessing.
This is the most common kNN failure and it has nothing to do with dimensionality. It is a units bug.
What Beyer actually proved
The famous result is that kNN dies in high dimensions, and the citation is Beyer, Goldstein, Ramakrishnan and Shaft, 1999. What they showed is distance concentration: under certain conditions, as dimensionality rises, the distance to the nearest point and the distance to the farthest point converge. Everything is equidistant from everything. "Nearest" stops meaning anything, and the whole premise of the algorithm evaporates.
The conditions are the part everyone drops. Their analysis rests on assumptions closest to i.i.d. dimensions — the uniform-random case. And a field whose values are uniformly random is usually a field carrying no information at all, which is not what your data looks like.
Durrant and Kabán established the converse in 2009, and it reframes the whole thing: distances do not concentrate, in arbitrarily high dimensions, as long as the number of relevant dimensions grows no slower than the total. So the enemy was never dimensionality. It was irrelevance. A thousand informative dimensions are fine. Twenty informative dimensions buried in nine hundred and eighty of noise are fatal, and they would be fatal at any total count.
That is the same failure as the units bug, viewed from further away. Both are the algorithm being unable to distinguish signal columns from noise columns, because nothing in it can.
| The folk version | What the papers say |
|---|---|
| kNN breaks above ~10–20 dimensions | It breaks when irrelevant dimensions dominate the relevant ones |
| High dimension ⇒ distance concentration | Only under near-i.i.d. conditions (Beyer's assumption); the converse holds otherwise (Durrant & Kabán) |
| So don't use kNN on embeddings | Vector search runs kNN at 768–1536 dims and works — the dimensions are relevant and the intrinsic dimension is low |
Why vector databases exist at all
Follow the folk version and vector search is impossible. Every vector database on earth performs nearest-neighbour search over 768- or 1536-dimensional embeddings, which is far above where the curse supposedly kills you, and it works well enough to be a product category.
Two things resolve it. The dimensions are relevant — an embedding is trained so that its coordinates carry meaning about the input, which is precisely the condition Durrant and Kabán identified. And the intrinsic dimensionality is much lower than the ambient dimensionality: the points lie on or near a low-dimensional manifold inside that 768-dimensional box, and the geometry that matters is the manifold's, not the box's.
The curse is real for uninformative dimensions and largely absent for informative ones. Embeddings are the second case by construction — that is what training them is for.
What actually bites in high dimensions
Not concentration, usually. Hubness. Radovanović and colleagues documented it in 2010: as intrinsic dimensionality rises, the distribution of "how often is this point somebody's nearest neighbour" becomes badly skewed. A few points — hubs — turn up in an enormous number of neighbour lists, while others appear in none. Your kNN classifier now has a handful of points quietly voting on most predictions, and the effect is invisible in any accuracy number.
The other thing that bites is cost, and it is the reason approximate search exists. Exact kNN is O(n) per query, which is fine at ten thousand points and untenable at a hundred million. HNSW (Malkov & Yashunin) builds a navigable small-world graph and gets you near-exact results in logarithmic time — the algorithm underneath most vector databases, and the reason the 1967 method is running in production in 2026.
What to do
Scale your features. Always, first, before anything else. The figure is the argument and it is one line.
Then ask which of your columns are actually informative, because that — not their count — is what determines whether the algorithm has a chance. Feature selection helps kNN more than it helps almost any other method, for exactly the reason Durrant and Kabán identified.
Use approximate search past roughly a hundred thousand points; exact kNN's linear scan is the real scaling limit, not the geometry.
And keep it as a baseline even when you don't ship it. Cover and Hart's bound means kNN's score is a statement about your features. If a heavily-tuned ensemble barely beats it, that is information about your problem, and it is not the information you were hoping for.
Further reading
- Cover & Hart (1967), Nearest Neighbor Pattern Classification — the bound: 1-NN error is at most twice the Bayes error, asymptotically.
- Beyer et al. (1999), When Is "Nearest Neighbor" Meaningful? — the concentration result, and the i.i.d. condition it depends on.
- Malkov & Yashunin (2018), Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs — HNSW, the index under most vector databases.
- Durrant & Kabán (2009), When Is 'Nearest Neighbour' Meaningful: A Converse Theorem and Implications — the other half of Beyer: distances don't concentrate when relevant dimensions grow with the total.
- Radovanović, Nanopoulos & Ivanović (2010), Hubs in Space: Popular Nearest Neighbours in High-Dimensional Data — JMLR; a few points colonise everyone's neighbour list.
Primary sources, listed so you can check the claims on this page rather than take them on trust.
Where people go wrong
- Not scaling features. The most common failure, and it produces a working-looking model that uses one column.
- Using it on raw high-dimensional data and concluding the method is bad. It's the dimensionality, not the algorithm.
- Choosing k=1 because it fits the training data perfectly. It memorises, which is what k exists to prevent.
- Using Euclidean distance on text embeddings. Cosine is the convention for a reason — magnitude carries little meaning there.
- Not realising you're already using it. Your RAG pipeline is kNN with a good index.
At a glance
Often compared with
Where this sits
A destination. 2 concepts lead here, and nothing in the corpus depends on it.
Computed from the prerequisite graph, not assigned. How this works