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.
Sources & 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 curse of dimensionality made precise; why distances concentrate.
- Malkov & Yashunin (2018), Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs — HNSW, the index under most vector databases.
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
FieldMachine Learning
Training costnone
Prediction costeverything
The dialk, a pure bias-variance knob
Breaks onhigh dimensions, where distances concentrate
Modern namevector search
DifficultyBeginner
Flashcards for this concept
Question
—
Answer
—
1 / 4
Often compared with
kNN vs. vector search — the same algorithm, sixty years apart. What changed is the index (approximate, fast) and the space (learned, meaningful).