HQAI Engineering HQ
Search
Checking sign-in...

kNN and ANN nearest neighbor search

Concept8 min readintermediate

What you’ll understand

  • Explain how exact k-nearest neighbors (kNN) search works and why it gets slow on large collections
  • Describe how approximate nearest neighbors (ANN) search uses an index to trade a little accuracy for speed
  • Choose between kNN and ANN using dataset size, latency, and recall needs

Helpful first: Vector representations for AI systems · Vector distance and similarity metrics

Nearest neighbor search answers one question: given a query vector, which stored vectors are closest to it? It is the core step behind semantic search, recommendations, and retrieval-augmented generation (RAG).

There are two main ways to answer it. kNN (k-nearest neighbors) is exact but checks everything. ANN (approximate nearest neighbors) is fast but may miss a true neighbor. In this article, ANN does not mean “artificial neural network”.

The problem: finding close vectors

Text, images, and other data can be turned into embeddings, which are lists of numbers where similar items sit close together. See vector representations for how that works.

A nearest neighbor search needs three things:

The result is the k stored vectors closest to the query.

How kNN works

kNN is the brute-force approach. It has no shortcuts:

  1. Compare the query to every stored vector using the distance measure.
  2. Sort the distances.
  3. Return the k smallest.

Because it looks at every vector, the answer is always exactly right. The cost is that the work grows with the collection. With N vectors, every query does N distance calculations, and each one touches hundreds or thousands of numbers.

kNN compares the query to every stored vector A scatter of stored points with one query point in the middle. Thin lines connect the query to every point, showing that all distances are calculated. The three closest points are connected with thick lines and filled green, labeled as the top k results with k equal to 3. Query Thin lines: every distance is calculated. Thick lines and green points: the k = 3 closest. Positions are illustrative.
kNN measures the distance to every point, then keeps the k smallest, so the result is exact but the work grows with the collection.

Choosing k

The value of k controls how many neighbors you keep. In search, k is simply how many results you want, such as the top 5 passages. kNN is also a classic machine learning method, and there k matters more:

  • Classification: the query takes the most common label among its k neighbors, a majority vote.
  • Regression: the prediction is the average, or a weighted average, of the neighbors’ values.
  • A small k reacts to noise, because one odd neighbor can change the answer. A large k smooths away real detail.

How ANN works

ANN gives up the guarantee of the perfect answer to avoid checking everything. It works in two phases:

  1. Build an index (ahead of time). The vectors are organized into a structure that groups nearby points together.
  2. Search the index (at query time). The query jumps straight to the region where its neighbors probably are, and compares itself only to the vectors there.

Common index families include:

  • Tree-based (for example KD-trees): split the space into regions, then search only the matching branch. Works best with few dimensions.
  • Hashing-based (locality-sensitive hashing, LSH): hash vectors so similar ones tend to land in the same bucket.
  • Clustering-based (for example IVF, inverted file): group vectors around centers and search only the nearest few groups.
  • Graph-based (for example HNSW, and DiskANN): link each vector to near neighbors, then walk the graph toward the query. These are popular for high-dimensional embeddings.

The result is a set of vectors that are very likely, but not guaranteed, to be the true nearest ones.

ANN searches only the region where the query falls The space is split into four regions by an index. The query sits in the top-left region, which is outlined with a dashed green border and is the only region searched. Three results are returned from that region. One true neighbor sits just across the region boundary in the top-right region, so it is missed and shown with an orange outline. Points in the other regions are never compared. SEARCHED REGION SKIPPED REGIONS Query True neighbor, missed Green: returned results. Orange: a true top-3 neighbor just over a region boundary. Positions are illustrative.
ANN compares the query only to one nearby region, so it is much faster, but a neighbor just across a boundary can be missed.

Measuring accuracy with recall

Since ANN can miss, we measure how often it does. Recall is the share of the true nearest neighbors that ANN actually returned. If the exact top 10 contains 10 items and ANN returns 9 of them, recall@10 is 0.9, or 90%.

Most ANN indexes have settings that let you raise recall by searching more candidates, at the price of more time. You tune the balance.

kNN vs ANN

kNN and ANN compared side by side Two columns. The kNN column, in green, lists: setup none, work per query all N vectors, results exact with 100 percent recall, best for small collections. The ANN column, in purple, lists: setup build and store an index, work per query a small region of the data, results approximate with recall below 100 percent that you tune, best for large collections. kNN (exact) Setup: none Per query: compares all N vectors Results: exact, 100% recall Cost: grows with N Best for small collections ANN (approximate) Setup: build and store an index Per query: a small region only Results: close, recall below 100% Cost: grows slowly with N Best for large collections
kNN buys exactness with per-query work, while ANN buys speed with an index and a tunable amount of missed neighbors.

A rule of thumb for picking one:

  • Use kNN when the collection is small (thousands of vectors), when every result must be exact, or when a filter first narrows the search to a small subset.
  • Use ANN when the collection is large (millions of vectors or more) and you need low latency. Check recall on real queries to confirm it is high enough.
  • Many production systems use ANN for the main search and exact kNN to re-rank the final few candidates.

A worked example

These numbers are illustrative.

A support site stores 1,000,000 document embeddings and wants the top 10 matches for each question.

  • kNN: 1,000,000 distance calculations per query. The 10 results are exactly right.
  • ANN: the index sends the query to a few promising regions, and maybe 5,000 distance calculations are needed. That is about 200 times less work. Say 9 of the 10 results match the exact top 10, so recall@10 is 0.9.

For a chatbot that feeds a few passages to an LLM, one slightly different passage in the top 10 usually costs little, and the faster answer is worth it. If you want better accuracy, you can raise the search effort and accept some extra time. For exact keyword matches that vector search blurs, see hybrid search.

Common pitfalls

  • Confusing the acronym: ANN here means approximate nearest neighbors, not artificial neural network.
  • Never measuring recall: compare ANN results to an exact kNN run on a sample of queries before trusting the index.
  • Using a different metric than the model expects: the index must use the same distance measure the embedding model was trained for.
  • Using ANN too early: for small collections, exact kNN is simpler and just as fast.
  • Forgetting the cost of the index: ANN indexes take time to build and extra memory or storage, and heavy updates can lower quality until they are refreshed.

Saved in this browser only. Not synced to your account.