k-Nearest Neighbours
No training, all the cost at inference, and a distance that is only meaningful in a scaled space. The mental model behind every embedding retrieval system.
The problem, the obvious approach, and why it breaks
Every lesson starts where the work starts: someone has a problem, and the first model that comes to mind looks fine offline.
A model with no training step at all beat the tuned one offline — what is it assuming about distance, and what will it cost to serve?
A marketplace team wants to suggest a price for a new listing. "Find the ten most similar listings that sold recently and show the seller the median price. That is what a good human agent does."
Store every sold listing as a vector. For a new listing, compute the Euclidean distance to all of them, take the k closest, and return the median of their prices. No training, no hyperparameters except k, and it is exactly the story the product team told.
Euclidean distance on the raw columns is dominated by item age, because its range is fifty times the others. The "ten most similar listings" are the ten with the closest age in months, whatever their category — and the suggested price for a phone comes from ten sofas of the same age.
- Euclidean distance on the raw columns is dominated by item age, because its range is fifty times the others. The "ten most similar listings" are the ten with the closest age in months, whatever their category — and the suggested price for a phone comes from ten sofas of the same age.
- Offline the number looked fine because the validation set was a random sample of the same pool, so the neighbours were near-duplicates of the held-out listings. In production the reference pool is yesterday's sales, and the new listing has no near-duplicate.
- Every prediction scans a few hundred thousand vectors. At a few requests per second that is fine; when the listing form starts calling it on every keystroke it is a CPU bill and a latency budget nobody planned for, because the cost of k-NN is entirely at inference (Latency Breakdown).
- After one-hot encoding forty categories, every listing is a point in a ~50-dimensional space, and in high dimensions nearest and farthest neighbours are almost the same distance apart. "Similar" stops meaning anything.
What is being predicted, and from what data
This domain leads with these two. A target nobody defined precisely is a label nobody can trust, and a dataset nobody can describe is a model nobody can debug.
- Predict the sale price of a listing that has just been created, from listings that sold in the last ninety days. The label is the realised sale price, which is known only after the sale closes.
- The prediction is shown as a suggestion, so the cost of a wrong number is a listing priced far from the market — too high and it sits unsold, too low and the seller loses money and trust.
- One example is one sold listing: category, condition, brand, item age in months, photo count, seller rating, and the price it sold for. A few hundred thousand rows.
- Numeric columns live on wildly different scales: item age is 0–240 months, seller rating is 1–5, photo count is 0–20. Categorical columns were one-hot encoded.
- New listings arrive continuously and the "recent sales" pool is meant to slide forward daily, so the reference set changes every day even though nothing is trained.
How it actually works
Precisely enough to predict its behaviour — not a framework API.
- k-NN has no parameters to fit. The "model" is the reference set plus a distance function plus k. Prediction is a lookup: find the k reference points with the smallest distance, aggregate their labels — majority vote for classification, mean or median for regression.
- Because the distance is computed on the raw feature vector, the distance function *is* the model's inductive bias. Scaling each column to comparable range (standardising, or min–max) is not preprocessing; it is choosing what "similar" means. Weighting a column is choosing how much it matters (Bucketing & Normalisation).
- k is a bias/variance knob. k = 1 memorises the reference set and every noisy label becomes a decision boundary; a large k averages over a wide neighbourhood and cannot represent fine structure. The right k is found on validation data, like any other hyperparameter (Bias and Variance).
- In high dimensions the volume of space grows so fast that every point is far from every other, and the ratio of nearest to farthest distance tends to one. The remedy is a lower-dimensional representation in which distance is meaningful — which is exactly what a learned embedding is (Embeddings, Cosine Similarity).
The distance is the model
A neural network encodes what "similar" means in its weights. k-NN encodes it in the distance function and the scaling of the columns, and nothing else. Two listings that differ by one month of age and one point of seller rating are at Euclidean distance √2 if both columns are standardised, and at distance ≈ 1 if they are raw — where the rating difference has become invisible.
This makes scaling a modelling decision rather than a cleaning step. Standardising every column says "one standard deviation of any feature counts the same". Weighting a column by two says "this matters twice as much". Dropping a column says "irrelevant". A tree learns these choices from the labels; k-NN takes them from you.
Listings that are close under the chosen distance in the scaled space sell for close prices.
holds when The columns in the distance are the ones that drive price, they are scaled so none dominates by range, and the dimensionality is low enough that nearest neighbours are meaningfully nearer than random points.
breaks when A high-range column is added without rescaling, one-hot encoding pushes the dimensionality up, or a category launches with no reference points so its neighbours come from unrelated categories.
respond Fix the representation — rescale, drop or weight columns, or move to an embedding — before touching k. A larger k only averages over more wrong neighbours.
1import numpy as np2 3def scale_fit(X_train):4 mu, sd = X_train.mean(axis=0), X_train.std(axis=0) + 1e-95 return lambda X: (X - mu) / sd # fitted on the training fold only6 7def knn_predict(X_ref, y_ref, x, k=10):8 d = np.sqrt(((X_ref - x) ** 2).sum(axis=1)) # Euclidean, in *scaled* space9 idx = np.argsort(d)[:k]10 return np.median(y_ref[idx]), idx, d[idx] # keep the neighbours for tracing11 12# raw: age_months in [0, 240], rating in [1, 5] -> age dominates every distance13# scaled: both ~N(0, 1) -> "similar" means similar in bothThe function returns the neighbour indices and distances alongside the prediction. That is not debugging convenience — it is the explanation the product will show, and the trace that lets a bad suggestion be diagnosed.
All the cost at inference
A linear model spends its compute once, in training, and a prediction is a dot product. k-NN spends nothing in training and pays for the entire reference set on every prediction. That inversion is why the offline story and the serving story diverge: the notebook evaluated a few thousand held-out points against a static pool and never noticed the cost.
At scale the fix is an approximate nearest-neighbour index, which is a database problem — the same structures that serve embedding retrieval for RAG. The index turns a linear scan into a sub-linear lookup at the price of sometimes missing the true nearest neighbours, so recall of the index becomes a quantity that must be measured and can drift as the pool changes.
Median absolute error on a random held-out sample of the reference pool comfortably under the per-category median baseline; p50 latency of a single query under a millisecond on the notebook's exact scan.
Suggestions for new listings noticeably worse than the baseline in two categories; the listing form's p99 latency doubled once the endpoint was called on every field change.
- 1The random split shared near-duplicate listings between reference and held-out sets, so offline k-NN was largely looking itself up; new listings have no such twin.
- 2Both categories with poor suggestions had fewer than k recent sales, so their neighbours were drawn from adjacent categories in encoded space.
- 3The notebook measured one query against an in-memory array; production runs a scan per keystroke against a pool served over the network.
Why this is also the mental model for embedding retrieval
Vector search — retrieving the documents whose embeddings are closest to a query embedding — is k-NN with a learned representation and a cosine distance. Everything in this lesson transfers: the distance is the model, the index trades recall for latency, the reference set must be refreshed, and the curse of dimensionality is why the embedding model exists at all. Agentic Engineering owns how retrieval is used inside a RAG system; this is the model-level view of what it is computing.
The transfer works in the other direction too. A team that has built retrieval already understands k-NN's failure modes, they have just met them under different names: stale index, embedding drift (Embedding Drift), a query far from every document, and an approximate index returning neighbours that are not the nearest.
Distance dominated by whichever column has the widest range; a scan over the whole pool per query; no representation that makes fifty one-hot dimensions comparable.
An embedding trained so that distance tracks the quantity that matters; cosine so magnitude is ignored; an approximate index with measured recall serving the query within budget.
The learned representation solves the scaling and dimensionality problems at once by making the coordinates mean "similar for this task", and the index moves the cost from every query to an offline build — which is the only way k-NN survives at scale.
How to build it
Most important first.
- Scale every feature on the training fold and apply the same scaler at prediction time, or the distance means something different in production (Preprocessing Leakage, Preprocessing Lives in the Artifact).
- Choose the distance deliberately: Euclidean for dense scaled numerics, cosine for embeddings where magnitude is nuisance, a learned metric or an embedding when raw columns are not comparable.
- Choose k on a validation set that mirrors serving — held-out listings from *after* the reference window, not a random sample of the same pool (Time-Based Split).
- Treat the reference set as data infrastructure: an approximate nearest-neighbour index rebuilt or updated on a schedule, with the same freshness questions as any feature (Feature Freshness). Agentic Engineering and the database domain own the index internals.
- Prefer a model that trains when the reference set is large and the latency budget is tight; k-NN wins when the "similar cases" story is itself the product, or when the representation is an embedding and retrieval is the point.
What to measure
Which number actually maps to the decision — and which numbers look relevant and are not.
- Error on listings created after the reference window, against a mean-price-per-category baseline (Majority Class and Mean Predictor). If k-NN does not beat "median price in this category", the neighbours are not adding information.
- Serving latency at the p99 as a function of reference-set size — this is the number that decides whether k-NN can be served online at all.
- The distribution of nearest-neighbour distances over time. When the typical distance to the nearest reference point grows, new listings are drifting away from the pool and the predictions are being made from far-away neighbours (Data Drift).
- Do not measure accuracy on a random split of the reference pool. Near-duplicate listings on both sides of the split turn k-NN into a lookup of itself (Entity Leakage).
What must stay true after deployment
The field this whole domain exists for. A model is a set of assumptions with weights attached; these are the ones a monitor or a test should be checking.
- Distance in the scaled feature space corresponds to similarity in the quantity being predicted — close listings really do sell for close prices.
- The reference set is representative of what is being queried, and it is refreshed at the cadence the product assumes.
- The scaler applied at prediction time is the one the validation k was chosen under, and no feature's range has moved far enough to dominate the distance again.
- The reference set is small enough, or the index good enough, that a query returns within the latency budget under peak load.
- Offline: evaluate on listings dated after the reference window with the scaler fitted only on the window; compare against the per-category median baseline.
- Online: log the k neighbour ids and distances with every prediction, so a bad suggestion can be traced to the neighbours that produced it (Tracing a Prediction).
- Over time: alert when the median nearest-neighbour distance rises, when the reference pool's newest timestamp is stale, and when a category appears with fewer than k reference points.
What can go wrong
- The scaler was fitted on the whole pool including future sales; in production it is applied to listings from a slightly different distribution and the scaled distances no longer match validation.
- The reference pool is refreshed nightly by a job that silently fails; k-NN keeps serving from a pool that ages one day at a time, and the price suggestions drift with the market without any model changing.
- A new category launches. It has no sold listings, so its neighbours are whatever category happens to be closest in encoded space — usually a meaningless one.
- The approximate index trades recall for speed and the "nearest" neighbours it returns are not the nearest; the tuned k on the exact index is now wrong for the approximate one.
- No training step means no training pipeline, no artifact and no retraining decision — and also no compression: the whole reference set ships to serving and every query pays for its size.
- Explanations are excellent — "these ten listings" — and the product may value that more than a point of accuracy; the price is inference cost and index infrastructure.
- An approximate index makes serving feasible at scale and introduces a recall/latency knob that must be tuned and monitored alongside k.
- "k-NN has no training, so there is nothing to version." The scaler, the distance, k and the reference-set snapshot are the model. Change any of them and the predictions change.
- "More features means better neighbours." Every added column dilutes the distance. Past a few dozen dimensions the nearest neighbour is barely nearer than a random point unless the columns were chosen or learned to be comparable.
- "It beat the boosted model on validation, ship it." Check the split. On a random split of a pool with near-duplicates, k-NN is looking up the answer.
Where this applies
ML advice is stated as universal far more often than it is. These labels say what each claim is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- MODEL-SPECIFICDistance-based methods — k-NN, k-means, kernel SVMs, embedding retrieval — all depend on feature scaling; tree models are invariant to monotone rescaling and do not have this failure at all.
- DATA-SPECIFICOn a few dense, comparable numeric columns k-NN is a strong, honest baseline; on hundreds of sparse one-hot columns distance degrades and a learned embedding or a tree ensemble is needed before neighbours mean anything.
- SCALE-SPECIFICAt thousands of reference points a brute-force scan is faster than any index; at millions an approximate index is mandatory and its recall becomes a monitored quantity of its own.
Where the depth lives
This domain teaches the model and hands the rest off by name.
- — Testing & Reliability Engineering — the recall of an approximate index against exact search is a regression test that should run whenever the pool or the index parameters change; this domain names the quantity and leaves the test discipline to a domain that does not yet exist.