Every retrieval system starts with the same primitive operation: given a query vector, find the most similar vectors in a database. Naive implementations compute distance between the query and every database vector, which is $O(n)$ per query. For a database of one million vectors that is one million distance computations per query, too slow for interactive applications. Approximate nearest neighbor (ANN) algorithms trade a small accuracy loss for massive speedups, making vector search practical at scale.

Exact kNN and When It Is Enough

Exact k-nearest-neighbor search computes distances to all $n$ vectors in the database, sorts them, and returns the top $k$. This is guaranteed to return the true nearest neighbors but takes $O(n \cdot d)$ time where $d$ is the vector dimension. For a database of 10,000 768-dimensional vectors, that is 7.7 million multiplications per query, fast enough for a non-interactive system but unusable at 100 queries per second.

Exact search is still useful for small databases (under 100K vectors), for applications where perfect recall is required, and as a ground truth baseline when evaluating approximate methods. Modern GPU-accelerated exact search libraries (like FAISS with brute force) can handle millions of vectors per second by parallelizing the distance computation across GPU cores, extending the practical range of exact search significantly.

The Approximate Tradeoff

Approximate algorithms do not compute distance to every vector. Instead, they use clever data structures to prune the search space, visiting only the most promising candidates. The result is a speedup of 100x to 10000x over exact search, at the cost of occasionally missing the true nearest neighbor.

The key metric for ANN algorithms is recall at k ($\mathrm{recall}@k$): given the top $k$ results returned by the approximate method, what fraction are among the true top $k$? Formally, $\mathrm{recall}@k = |\mathrm{true\_top}_k \cap \mathrm{approx\_top}_k| / k$. A good ANN algorithm achieves recall of 95-99 percent while running 100x faster than exact search. The remaining 1-5 percent of queries may return slightly less relevant results, but for most applications (RAG, recommendation, semantic search) this is an acceptable tradeoff.

The Three Families of ANN Algorithms

Modern ANN algorithms fall into three main families, each with different tradeoffs:

1. Tree-based methods (KD-trees, ball trees, annoy): Build a hierarchical partition of the vector space. Good for low-dimensional data (under 50 dimensions) but suffer from the curse of dimensionality, in high dimensions, trees become unbalanced and performance degrades.
2. Hashing methods (LSH, spectral hashing): Use locality-sensitive hash functions to map similar vectors to the same bucket. Simple to implement and analyze but usually produce worse recall-latency tradeoffs than graph or cluster methods for high-dimensional embeddings.
3. Graph-based methods (HNSW, NSG): Build a graph where nodes are vectors and edges connect similar vectors. Search navigates the graph from an entry point toward the query. Excellent performance on high-dimensional embeddings and the dominant choice for modern vector databases.
4. Inverted index methods (IVF, IVFPQ): Partition the vector space into clusters, search only the clusters nearest to the query. Often combined with product quantization for additional compression. Used by many large-scale systems alongside or instead of graph methods.

Graph-based methods (especially HNSW) and inverted index methods (especially IVF with quantization) dominate production vector search. Tree-based methods are mostly legacy, and pure hashing methods are rarely used except in specialized contexts.