K-Nearest Neighbors (KNN): How It Works and How to Choose k

LLM foundationsRetrieval and dataPublished By Simon Budziak

K-nearest neighbors (KNN) is an algorithm that predicts from the k most similar stored examples. To classify a new point it takes a majority vote among those neighbors, and for regression it averages their values. Training only stores the data, so the whole cost moves to search time, at every prediction.

How does the k-nearest neighbors algorithm work?

KNN measures the distance from a new point to every stored example and keeps the k closest. For classification the neighbors vote; for regression their target values are averaged. KNN has no real training step: fitting stores the data, and every prediction pays for the search.

A worked example: a new support ticket is turned into an embedding, and its five nearest past tickets are:

Neighbor Distance Label
1 0.12 Billing
2 0.18 Billing
3 0.21 Shipping
4 0.30 Billing
5 0.33 Shipping

With k = 5 and equal weights, billing wins three votes to two, a 0.6 probability. Weighted by inverse distance, billing scores 1/0.12 + 1/0.18 + 1/0.30 ≈ 17.2 against shipping’s 1/0.21 + 1/0.33 ≈ 7.8, so the closest neighbors count for more.

How do you choose k and the distance metric?

Start from the library defaults and tune k on held-out data. scikit-learn 1.9.1’s KNeighborsClassifier defaults to n_neighbors=5, equal weights and the Minkowski metric with p=2, which is Euclidean distance (scikit-learn docs, read 16 November 2026). Its user guide puts the trade-off plainly: “a larger k suppresses the effects of noise, but makes the classification boundaries less distinct” (Nearest Neighbors guide, read 16 November 2026). A k of 1 memorizes the training set, and a k near the dataset size predicts the majority class everywhere: the first overfits, the second underfits.

Scale features before measuring distance, or the feature with the largest units decides every vote: income in euros swamps age in years. For text embeddings, cosine distance is the usual choice.

Why does KNN slow down on large or high-dimensional data?

Brute-force search compares the query with every stored point. scikit-learn’s guide gives that cost as O[DN²] for N samples in D dimensions across a whole dataset. Tree indexes help in low dimensions: a KD tree “is very fast for low-dimensional (D < 20) neighbors searches”, and scikit-learn’s algorithm='auto' falls back to brute force above 15 dimensions (same guide). In high dimensions distances bunch together, the curse of dimensionality, and exact search stops scaling.

Exact KNN returns the true k closest points; approximate nearest neighbor (ANN) search returns almost the closest, much faster.

Exact KNN Approximate (ANN)
Recall Perfect Below 100%, tunable
Query cost Grows with every stored vector Roughly logarithmic for HNSW
Typical index None, or KD and ball trees HNSW, IVFFlat
Where you meet it Small tabular models Vector databases

pgvector “performs exact nearest neighbor search, which provides perfect recall” by default, and an HNSW or IVFFlat index “trades some recall for speed” (pgvector README, v0.8.7, read 16 November 2026). HNSW comes from Malkov and Yashunin, whose layered graph search “allows a logarithmic complexity scaling” (arXiv:1603.09320, 30 March 2016, read 16 November 2026). Every semantic search query in a RAG system is a nearest-neighbor query, so when retrieval misses a passage, check the index’s recall before blaming the model.

This entry was drafted with AI assistance.

Frequently asked questions

Why is k odd in KNN?

With two classes an odd k cannot split the vote evenly, so every prediction has a winner. With three or more classes ties can still happen, which is one reason to weight neighbors by distance.

Is KNN supervised or unsupervised?

A KNN classifier or regressor is supervised, because it predicts from labeled neighbors. Finding the nearest neighbors on its own needs no labels, which is how vector databases use it for retrieval.

Summarize this page with

Train your team to build this