What is kNN?

kNN, or the k-nearest neighbor algorithm, classifies or predicts by finding the k most similar labeled points to a query and aggregating their values — no trained model required, just stored data and distance. It is a supervised learning algorithm and the core retrieval mechanism behind modern vector search, where approximate kNN over dense embeddings powers semantic retrieval at scale.

kNN (k-nearest neighbors) is a non-parametric, instance-based learning algorithm: Unlike algorithms that fit an explicit model to training data, kNN stores labeled data points and classifies or predicts a new input by measuring its proximity to stored points at query time, not during a training phase. The core assumption is that similar points cluster near each other in feature space. Because kNN stores its training data and defers all computation to query time, researchers call this approach lazy learning — the algorithm does no modeling in the traditional sense, only retrieval and aggregation.

"k" denotes the number of nearest neighbors considered for each prediction. For classification, kNN assigns the label that appears most often among those k neighbors. For regression, it returns the mean of their values. kNN is a supervised learning algorithm: Labeled training data is required for it to produce predictions.

kNN works by measuring the distance from a query point to every stored training point and then assigning the mode of the k-nearest neighbors' labels for classification or their mean for regression. Consider a query point with two class-A neighbors and one class-B neighbor: At k=3, a majority vote assigns class A because two of three neighbors agree. Raise k to 5 and pull in two more class-B points, and the vote flips to class B — the same query point, a different k, a different prediction. This is why kNN has no separate training step. The algorithm stores the labeled dataset as-is and runs this distance-and-vote calculation only when a query arrives. In Python, scikit-learn's KNeighborsClassifier implements exactly this pattern. It stores the training data when you call fit() and performs the distance calculation and vote only when you call predict().

Metric learning answers a question fixed distance metrics can't: What if Euclidean, Manhattan, or any other preset formula isn't the best measure of "closeness" for your data, and a better distance function could be learned directly from labeled examples instead? kNN's predictions depend entirely on which points count as neighbors, so specialized algorithms such as large margin nearest neighbor and neighborhood components analysis learn a transformation of the feature space that pulls same-class points closer together and pushes different-class points apart — often outperforming a fixed metric on the same dataset. Before reaching for metric learning, though, most kNN implementations start from one of four fixed distance metrics, each defining closeness differently:

1. Euclidean distance measures the straight-line distance between two points — the hypotenuse connecting them in feature space. It extends naturally to many dimensions and weights all dimensions equally, regardless of their actual variance in the data. It is the most common choice for continuous, real-valued features.
2. Manhattan distance sums the absolute difference along each axis, as if navigating a city grid from one corner to another. Instead of cutting diagonally, it travels only horizontally and vertically. Manhattan distance is less sensitive to large differences on a single feature than Euclidean distance, making it more appropriate when individual features vary on very different scales.
3. Minkowski distance generalizes both Euclidean and Manhattan distance through a single parameter p. When p=1, Minkowski distance equals Manhattan distance. When p=2, it equals Euclidean distance. Values of p between those extremes produce geometrically distinct distance surfaces suited to different data distributions.
4. Hamming distance counts the number of positions where two equal-length strings or Boolean vectors differ, making it suitable for kNN problems with categorical and binary features where numerical closeness is not meaningful. Two binary strings that differ in three positions have a Hamming distance of three. It is particularly useful in kNN for error detection and error correction applications.

For high-dimensional embeddings in vector search, directional metrics such as cosine similarity and dot product often replace Euclidean distance because they measure angular similarity, not absolute magnitude. Metric learning techniques can refine any of these further for a specific dataset.

A low value of k overfits to noise in the local neighborhood, fitting noise rather than the underlying pattern, while a high value of k averages across too large a neighborhood and loses the local structure that makes proximity useful. Evaluate a kNN model by testing candidate k values with cross-validation on held-out folds and selecting the value with the lowest validation error.

With k=1, a single outlier neighbor can determine the prediction. If the nearest stored point happens to be mislabeled or an anomaly, that error propagates directly to the output. That is high variance: The model fits noise, not the pattern. With a very high k (say, k=20 in a training set of 25 points), the algorithm consults most of the dataset for every query and local variation disappears into the global distribution. That is high bias: The model is too coarse to capture real local structure.

Two guidelines help find a useful middle ground. In binary classification, choose an odd k to prevent ties. As a starting point, try the square root of N, where N is the number of training data points, and then refine with cross-validation.

As k and dataset size grow, comparing a query against every stored point becomes the real computational bottleneck — the problem that approximate nearest neighbor methods exist to solve.

Exact kNN guarantees the true k-nearest neighbors by scoring a query against every vector in the index. Approximate nearest neighbor (ANN) search preindexes vectors so a query visits only a promising subset of candidates, trading a small and configurable amount of recall for large gains in query speed. HNSW — hierarchical navigable small world — is the ANN algorithm that most production vector search systems, including Elasticsearch, default to, and Elasticsearch also supports DiskBBQ for efficient on-disk retrieval at massive scale. At thousands of vectors, exact search is fast enough; at millions or billions, latency requirements make an approximate approach necessary.

Each kNN use case applies the same proximity assumption — similar items sit close together in feature space — to a different kind of data.

1. Relevance ranking: kNN scores and ranks documents against a query by distance, surfacing the most similar results for natural language queries and powering the underlying retrieval in search applications.
2. Similarity search for images and video: Image similarity search maps images into a vector space and retrieves the closest visual or semantic matches to a query, whether the query is text-based or another image.
3. Pattern recognition: kNN classifies inputs by finding the labeled training examples closest to the new observation. Common applications include digit recognition, text categorization, and signal type identification.
4. Finance: In the financial sector, kNN supports fraud detection by flagging transactions that fall outside a user's normal behavioral neighborhood. It also supports forecasting by finding historical market patterns that closely resemble current conditions.
5. Product recommendations: Recommendation systems surface items similar to what a user has previously engaged with. Items a user would likely want sit close to items they have already chosen in the feature space the recommender operates in.
6. Healthcare and genetics: kNN estimates the probability of gene expressions by finding patients with similar genetic profiles, supporting research into hereditary conditions and treatment response prediction.
7. Data preprocessing: kNN estimates missing values in a dataset by substituting the mean of a data point's k-nearest non-missing neighbors. This technique, called kNN imputation, preserves local structure better than global mean substitution.

Modern vector search runs kNN, almost always in its approximate form, over dense vector embeddings. Embeddings (also called dense vectors) are numerical representations, typically arrays of hundreds to thousands of floating-point numbers, that machine learning models produce for text, images, and audio, positioning semantically similar items close together in high-dimensional space. Semantic search ranks results by conceptual similarity rather than literal keyword match, using vector proximity as its relevance signal. Running kNN over embeddings is what makes semantic search, retrieval augmented generation (RAG), and recommendation systems capable of retrieving by meaning instead of exact keyword match.

An embedding model converts both the indexed documents and the incoming query into vectors in the same space. A kNN search then finds the stored vectors closest to the query vector. Because the embedding model positions semantically similar content near each other in that space, proximity in vector space reflects conceptual relevance, not literal word overlap. A search for "broken authentication" can surface documents about session hijacking because the embedding space places them nearby, even though the terms differ.

In a retrieval augmented generation pipeline, kNN search retrieves the passages a large language model (LLM) uses to ground its response. A user's question is converted to a vector, and kNN finds the most relevant document chunks from a knowledge base. Those chunks are injected into the LLM's context window before it generates an answer. When retrieval is accurate, the model's answer reflects real facts. When retrieval misses the relevant passage, the model's answer reflects that gap, and retrieval quality is the dominant variable in most RAG deployments.

For developers evaluating retrieval at scale, the practical choice is almost always approximate versus exact. At thousands of vectors, exact search is fast enough and requires no additional index structure. At millions or billions of vectors (the scale of enterprise document collections, product catalogs, or knowledge bases), exact, linear-scan kNN exceeds any reasonable latency budget. Nearly all production systems default to approximate kNN backed by HNSW, with parameters like num_candidates controlling how many candidates the algorithm evaluates before returning results.

Elasticsearch, the search database for AI, supports both exact kNN and approximate kNN backed by HNSW. A vector database built on Elasticsearch stores and indexes the dense vectors your embedding model produces, enabling semantic search and hybrid retrieval, combining vector similarity with lexical scoring, at the scale production applications require.

kNN stores training data instead of fitting a model to it, and each advantage is a direct result of that choice.

1. Simple: kNN requires no training phase and no model architecture. It needs only two things at setup time: a k value and a distance metric. This makes it one of the easiest classifiers to implement correctly. Its predictions are also straightforward to explain; you can always inspect which neighbors drove a given output and why.
2. Adaptable: Adding new labeled samples does not require retraining or rebuilding a model. Because kNN stores data directly, a new labeled point is immediately available to influence future predictions as soon as it is added to the dataset.
3. Easily programmable: kNN has only two hyperparameters (k and the distance metric) compared to algorithms with dozens of configuration options. The tuning surface is small, and the effect of each parameter on behavior is predictable.

That same storage-based design, however, creates predictable scaling challenges as dataset size and query volume grow.

kNN's memory-and-distance design creates three scaling challenges: storage cost that grows with dataset size, loss of distance meaning in high dimensions, and sensitivity to the choice of k.

1. Difficult to scale: kNN holds all training data in memory, so storage costs grow directly with dataset size. At query time, exact kNN computes a distance from the query to every stored point, making latency grow linearly as the dataset grows. Both costs (memory and compute) make kNN expensive at production scale without approximate search techniques to reduce the per-query work.
2. Curse of dimensionality: As the number of feature dimensions increases, distances between points become less meaningful. In a 1,000-dimension space where points are distributed uniformly, the distance to the nearest neighbor and the distance to the farthest neighbor converge toward the same value — the contrast that makes “close” meaningful collapses. A query point that would clearly cluster with five nearby points in two dimensions may appear equidistant from hundreds of points in a thousand dimensions, making the neighborhood signal unreliable. Embedding models that produce hundreds or thousands of dimensions expose kNN to this phenomenon, which is one reason approximate methods that navigate high-dimensional space efficiently are necessary at scale.
3. Overfitting and underfitting: A low k value memorizes the training data too closely, fitting noise in the local neighborhood instead of the broader pattern (overfitting). A high k value averages across too large a neighborhood and loses the local structure that makes proximity useful (underfitting). Neither extreme generalizes reliably to new data, and finding the right value requires deliberate tuning on held-out validation data.

Production vector search sidesteps the scaling limitation by replacing exact kNN with approximate methods like HNSW, which visit only a structured subset of candidates, not the full index.

Elasticsearch, the search database for AI, supports both exact, brute-force kNN via script_score queries and approximate kNN backed by HNSW, so you can start with exact search on a small dataset and switch to approximate as your vector count grows. The dense_vector field type stores the embeddings your model produces, and parameters like num_candidates control how many candidates HNSW evaluates at query time while m and ef_construction shape the recall-latency trade-off at index build time.

• Elasticsearch's vector database
• kNN search in Elasticsearch docs
• Filtered HNSW & kNN search
• Vector quantization in Elasticsearch

1. Fix, E., & Hodges, J.L. (1951). Discriminatory Analysis—Nonparametric Discrimination: Consistency Properties. USAF School of Aviation Medicine, Randolph Field, TX, Report No. 4, Project 21-49-004. Reprinted with commentary by Silverman, B.W., & Jones, M.C. (1989), International Statistical Review, 57(3), 233–247. (1951). International Statistical Institute (ISI) / Revue Internationale de Statistique, 57(3), 233–238.
2. T. Cover and P. Hart, "Nearest neighbor pattern classification," in IEEE Transactions on Information Theory, vol. 13, no. 1, pp. 21–27, January 1967, doi: 10.1109/TIT.1967.1053964.
3. Keller, J.M., Gray, M.R., & Givens, J.A. (1985). "A Fuzzy K-Nearest Neighbor Algorithm," IEEE Transactions on Systems, Man, and Cybernetics, SMC-15(4), 580–585.
4. Terrell, G.R., & Scott, D.W. (1992). "Variable Kernel Density Estimation," The Annals of Statistics, 20(3), 1236–1265. Building on the k-th-nearest-neighbor density estimator first proposed by Loftsgaarden, D.O., & Quesenberry, C.P. (1965), "A Nonparametric Estimate of a Multivariate Density Function," Annals of Mathematical Statistics, 36(3), 1049–1051.