Approximate Nearest Neighbour
Approximate nearest neighbour search is the problem of finding the items in a collection closest to a given query point while permitting the answer to be slightly wrong, and by extension the family of methods that solve that problem.
The exact version of the task has an obvious solution: compare the query against every stored item and keep the closest. It is correct, trivial to implement, and linear in the size of the collection. Beyond some collection size, under some latency budget, it stops being affordable.
The approximate version drops the guarantee. A search organises the collection so that most of it can be skipped, examining only the regions likely to hold near neighbours. The consequence is that a true nearest neighbour may be missed, or returned in the wrong position, and how often that happens is a setting rather than a fixed property.
The concession is a deliberate one, and the reason it is tolerable is that the neighbours are being used as candidates rather than as answers. A retrieval system that occasionally receives the fourth-closest chunk instead of the third is affected less by that error than by its chunking or its embedding model.
The phrase is usually abbreviated ANN, and shortened further to approximate search or vector search in engineering writing.
In practice
The accuracy of an approximate search is measured as recall: of the k items the exact search would have returned, what fraction did the approximate search actually return. A recall of 0.95 means one neighbour in twenty was missed.
That figure is not a constant. It moves with three things at once.
Search effort. Every implementation exposes a parameter governing how much of its structure to examine per query — how many candidates to hold while walking a graph, how many partitions to scan. More effort buys more recall and costs more time, and the relationship flattens: the last few points of recall are the most expensive.
Build quality. How thoroughly the structure was constructed constrains what any amount of search effort can recover. A structure built cheaply has an accuracy ceiling.
The value of k. Recall at a large k and recall at a small k are different measurements, and a structure tuned for one is not necessarily good at the other. Returning more neighbours also costs more work inside the index. See top-k.
Metadata filtering complicates all of this, because a filter and an approximate structure interact. Restricting the candidate set before the search can invalidate the assumptions the structure was built on; applying the filter to the search’s output can leave fewer results than requested. The recall figure quoted for an unfiltered search does not carry over to a filtered one.
Commonly confused with
Vector index. The concrete artefact. Approximate nearest neighbour is the problem; a vector index is a built structure that answers it. “ANN index” and “vector index” are used interchangeably, and in a RAG context the substitution is harmless. See vector index.
HNSW and IVF. Specific algorithm families rather than the problem itself — one organising vectors as a navigable graph, the other partitioning them into cells around centroids. Both are approximate nearest neighbour methods; neither is what the term means.
Exact or brute-force search. The same task without the concession, comparing against everything. Commonly offered under the name flat, which is a source of confusion in its own right, since a flat index is the absence of an index structure.
k-nearest neighbours. The classification and regression method that labels a point by the labels of its closest neighbours. It uses nearest-neighbour search as a component, so the words overlap almost completely while the purposes do not: one retrieves, the other predicts.
Retrieval recall. A different measurement under the same word. Index recall asks whether the search found the true nearest vectors. Retrieval recall asks whether the returned chunks contain the answer. An index can score near-perfectly on the first while the second is poor, because the true nearest vectors were the wrong chunks.
Usage notes
The abbreviation is overloaded. ANN also stands for artificial neural network, and both expansions occur in machine-learning documentation. Context usually resolves it, but a sentence mentioning ANN alongside embeddings and models can be read either way.
A quoted recall figure needs three qualifiers to mean anything: which collection, which k, and at what search effort. Reported without them it describes one configuration on one dataset. Because the trade-off is a curve rather than a point, any single number on it can be improved by paying more.
“Approximate” describes the geometry, not the relevance. The approximation concerns whether the closest vectors were found. Whether closeness in the embedding space corresponds to usefulness is a separate question the method does not address. See cosine similarity.
Managed services often do not say which method they use, exposing a tuning surface instead. The search is still approximate, and the recall trade-off still exists; it has been made on the caller’s behalf.
Some collections need no approximation at all. A few thousand vectors can be searched exhaustively inside a request’s latency budget, which makes exact search the simpler correct answer at small scale and the term irrelevant there.