K-Nearest Neighbors (KNN)

K-nearest neighbours (KNN) is the idea at the heart of vector search: given a query, find the k closest points. It's a classic machine-learning algorithm, and in a vector database it's the mechanism that retrieves the most similar vectors. Understanding KNN makes the whole retrieval side of vector databases click.

💡 In one line: KNN finds the k closest vectors to a query — the core operation behind vector search.

What is KNN?

Given a query point and a set of stored points, KNN finds the k nearest — the k points with the smallest distance to the query. The letter k is simply how many neighbours you want. KNN needs no training: it just compares the query to what's stored (a so-called "lazy" algorithm).

KNN in Two Roles

KNN shows up in two related ways:

  • Classic ML — classify or predict a point from its k nearest neighbours (majority vote for classification, average for regression). No model is trained; it decides by looking at neighbours.
  • Vector databases — retrieve the k nearest vectors to a query. This is the retrieval step behind semantic search and RAG.

Same idea, different use: label a point, or fetch the closest ones.

How It Works (Brute-Force)

The simplest version compares the query to everything. 

Whiteboard
Whiteboard diagram


The "k" Parameter

k controls how many neighbours you consider:

  • Small k → a tight, specific neighbourhood.
  • Large k → a broader, smoother one.

In retrieval, k is simply how many results to return — the top-k (the next subtopic).

Exact vs. Approximate KNN

  • Exact (brute-force) — check every stored vector. Perfectly accurate, but the cost grows with the number of vectors — slow at millions.
  • Approximate (ANN) — use an index to find near-neighbours fast, with a tiny accuracy trade-off. This is what makes KNN practical at scale (see ANN Search).

Distance Metrics

KNN ranks by a distance/similarity metric — cosine, Euclidean, or dot product — the same choices as similarity search. The metric must match how the vectors were stored.

Choosing k

  • Too small → noisy and sensitive to outliers.
  • Too large → sweeps in less-relevant items.
  • For RAG retrieval, a top 3–10 is common — enough context without noise.

Code Example


 
KNN vs. Top-K vs. ANN
 
     
  • KNN — the concept: the k nearest points.
    •  
  • Top-K — returning the k best matches (the retrieval operation).
    •  
  • ANN — the fast, approximate way to do KNN at scale.
    •  
 
Summary
 
     
  • KNN finds the k closest vectors to a query by distance.
    •  
  • It works in two roles: classifying in ML, and retrieving in vector databases.
    •  
  • Brute-force KNN compares to every vector — accurate but slow at scale.
    •  
  • k sets the neighbourhood size; 3–10 is typical for RAG.
    •  
  • ANN makes KNN fast; top-k is how you request it — both covered next. EOF echo created