Introduction

K-Nearest Neighbors (KNN) is the foundational algorithmic concept underlying similarity search, covered in the previous topic: given a query vector, find the K stored vectors that are closest to it, where K is simply a chosen number specifying exactly how many results should be returned. Despite its genuinely simple, almost obvious-sounding definition, KNN is one of the most foundational ideas in this entire module, since it precisely defines what a vector database is actually trying to compute every single time a similarity search request comes in.

Notably, KNN isn't a technique unique to vector databases at all — it's also a classic, well-established supervised learning algorithm in its own right, used for classification and regression tasks, and understanding both of these related but distinct applications provides a genuinely fuller picture of why this particular concept comes up so often across machine learning and AI.

Why Does KNN Matter?

KNN helps to:

• Precisely define what a similarity search is actually computing: the K closest vectors to a query
• Provide the conceptual foundation that both exact and approximate similarity search, covered in the previous topic, are built around
• Connect vector database search back to a classic, well-established machine learning algorithm
• Clarify the direct relationship between choosing a value of K and the number of results a search returns
• Set up the Top-K Retrieval topic that follows, which focuses specifically on the practical mechanics of returning exactly K results
• Serve as essential conceptual grounding before the ANN Search topic, which covers how to compute KNN efficiently at scale

KNN as a Retrieval Concept

In the specific context of vector databases and similarity search, KNN simply means: given a query vector and a chosen value of K, return the K stored vectors with the smallest distance (or highest similarity score) to that query. If K is set to 5, the search returns the 5 closest matches; if K is set to 20, it returns the 20 closest matches. This is, in a genuine sense, the most literal, mathematically precise definition of what "similarity search" from the previous topic actually means in practice — KNN retrieval is the formal name for the exact operation being performed.

Whiteboard

Loading diagram...

Choosing an Appropriate Value of K

Selecting the right value of K is a genuinely practical decision that depends entirely on what a specific application actually needs. A RAG system feeding context to an LLM might use a relatively small K, like 3 to 5, since only a handful of the most relevant document chunks are typically needed, and providing too many could unnecessarily bloat the LLM's context window, as covered in the earlier Context Window topic. A recommendation system, by contrast, might use a much larger K, like 50 or 100, to generate a broader pool of candidate items before applying further ranking or filtering logic downstream.

KNN as a Classic Machine Learning Algorithm

Beyond its role in similarity search, KNN is also a well-established, classic supervised learning algorithm covered under the broader Supervised Learning topic earlier in this curriculum, used for both classification and regression tasks. In this context, given a new, unlabeled data point, KNN finds the K most similar labeled examples from a training dataset and uses them to make a prediction — for classification, typically by taking a majority vote among the K neighbors' labels, and for regression, typically by averaging their numeric values.

KNN for Classification: A Simple Example

Imagine trying to classify a new, unlabeled flower based on its petal measurements, using a labeled dataset of flowers whose species are already known. KNN classification would find the K most similar (nearest, by measurement) flowers from that labeled dataset, and assign the new flower whichever species appears most frequently among those K neighbors — if K is set to 5, and 4 out of the 5 nearest neighbors are labeled "rose," the new flower gets classified as a rose too, based purely on this majority vote among its closest matches.

KNN Retrieval (Vector Databases) vs KNN Classification (Machine Learning)

Why the Same Core Idea Shows Up in Two Different Places

It's genuinely worth pausing on why the exact same "find the K nearest neighbors" concept shows up in both contexts: at its core, both applications are built around the same underlying assumption — that things which are close together in some meaningful space (whether that's a flower's measurements or a document's embedding) tend to share something important in common, whether that's a species label or a semantic meaning. This is really just a specific application of the same distributional and similarity-based reasoning covered throughout the earlier Embeddings section, applied here either to predict a label or to directly retrieve similar content.

The Computational Challenge KNN Introduces at Scale

Computing exact KNN — literally finding the true, mathematically closest K vectors — requires comparing a query against every single vector in a collection, exactly as covered in the previous topic's discussion of exact, brute-force search. This becomes genuinely impractical as a collection grows into the millions or billions of vectors, which is precisely the motivation behind Approximate Nearest Neighbor (ANN) techniques, covered in the final topic of this module — approximating KNN's results efficiently, rather than computing them exactly, in order to remain fast at real-world production scale.

KNN's Relationship to This Module's Remaining Topics

Key Properties of KNN

• KNN, in the context of vector databases, means finding the K stored vectors closest to a given query vector.
• Choosing an appropriate value of K depends entirely on the specific application's needs, from small K for RAG to larger K for broader recommendation candidate pools.
• KNN is also a classic supervised machine learning algorithm, used for classification (majority vote) and regression (averaging) tasks.
• Both applications of KNN share the same underlying assumption: that items close together in a meaningful space tend to share something important in common.
• Computing exact KNN becomes impractical at large scale, directly motivating the approximate techniques covered in the ANN Search topic.

Where Does KNN Matter Most?

Advantages

• Provides a simple, intuitive, and mathematically precise definition of similarity-based retrieval
• Directly connects vector database search to a well-established, widely understood machine learning concept
• Flexible value of K allows tuning result quantity to fit a wide range of different application needs
• The same core idea generalizes cleanly across both retrieval and classification/regression use cases
• Forms essential conceptual groundwork for understanding both Top-K retrieval mechanics and ANN search techniques

Limitations

• Computing exact KNN scales poorly, becoming computationally impractical for very large collections
• Choosing an inappropriate value of K can return either too few or an unmanageably large number of results
• In its classification form, KNN's performance can be sensitive to how "distance" is defined and measured
• Doesn't inherently account for varying result quality within the K neighbors returned, treating all K results as the requested set
• Real-world production systems rarely use exact KNN directly, relying instead on the approximate techniques covered next

Real-World Examples

Best Practices

• Choose a value of K that matches the specific application's actual needs, rather than defaulting to an arbitrary number.
• Recognize KNN retrieval and KNN classification as related but distinct applications of the same core nearest-neighbor concept.
• Understand exact KNN's computational limitations as the direct motivation for approximate search techniques at scale.
• Consider how downstream processing (like an LLM's context window) should influence the choice of K in a RAG system.
• Use a larger K when broader candidate generation is needed, followed by additional ranking or filtering logic.

Interview Tip

A common interview question is:

"What is K-Nearest Neighbors, and how does its use in vector database retrieval relate to its use as a classification algorithm?"

A strong answer is:

K-Nearest Neighbors, at its core, means finding the K closest items to a given query point in some meaningful space. In vector database retrieval, this means finding the K stored vectors most similar to a query vector and returning them directly as search results. As a classification algorithm, KNN instead uses those K nearest neighbors — found among labeled training examples — to predict a label for a new, unlabeled data point, typically through a majority vote among the neighbors' labels. Both applications share the same underlying assumption: that items close together in a meaningful space tend to share something important in common, whether that's semantic meaning for retrieval or a shared category for classification.

Explicitly naming the shared underlying assumption connecting both applications makes your answer stronger.

Conclusion

K-Nearest Neighbors provides the precise, foundational definition of what similarity search is actually computing — finding the K closest vectors to a query — while also connecting directly back to a classic machine learning algorithm used for classification and regression. With this core concept now clearly established, the next topic explores Top-K Retrieval, covering the practical mechanics of how a vector database actually identifies, ranks, and returns exactly K results from a search.