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:
- a query vector, such as the embedding of a user’s question
- a distance measure, such as cosine similarity or Euclidean distance (see vector distance metrics)
- a number k, how many results to return
The result is the k stored vectors closest to the query.
How kNN works
kNN is the brute-force approach. It has no shortcuts:
- Compare the query to every stored vector using the distance measure.
- Sort the distances.
- 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.
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:
- Build an index (ahead of time). The vectors are organized into a structure that groups nearby points together.
- 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.
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
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.