When you search a database of a million vector embeddings for the ones closest to your query, checking every single one is often too slow to be practical at scale. Approximate Nearest Neighbor (ANN) search is the technique that makes vector search fast enough for real applications — trading a small amount of accuracy for a massive gain in speed. Here's how it works.
The Problem ANN Solves
Vector search — used in recommendation systems, semantic search, and retrieval-augmented generation (RAG) — works by embedding items (text, images, products) as high-dimensional vectors and finding the vectors closest to a query vector, usually by cosine similarity or Euclidean distance.
The exact way to do this, brute-force nearest neighbor search, compares the query against every single vector in the dataset. For a small dataset, that's fine. For millions or billions of vectors, each with hundreds of dimensions, it becomes computationally expensive — and does so at exactly the scale where fast retrieval matters most.
What "Approximate" Actually Means
ANN algorithms don't guarantee finding the exact closest vectors — they find vectors that are very likely to be among the closest, in a fraction of the time. This trade-off is usually described in terms of recall: what percentage of the true nearest neighbors does the approximate search actually return? A well-tuned ANN index might achieve 95–99% recall while running orders of magnitude faster than brute force — a trade most applications happily accept, since the difference between the 1st and 5th closest match is rarely meaningful to the end user.
Common ANN Techniques
Hierarchical Navigable Small World (HNSW) graphs. One of the most widely used approaches today. HNSW builds a multi-layered graph where each vector is a node connected to its approximate neighbors. Search starts at a sparse top layer and works down through progressively denser layers, quickly narrowing in on a promising region of the vector space rather than scanning everything.
Inverted File Index (IVF). Vectors are first clustered into groups (using something like k-means), and a query only searches within the most relevant clusters rather than the whole dataset — dramatically cutting the number of comparisons needed.
Product Quantization (PQ). Compresses vectors into smaller, approximate representations, making both storage and distance calculations cheaper — often combined with IVF (as "IVF-PQ") to shrink memory footprint further at large scale.
Locality-Sensitive Hashing (LSH). Hashes similar vectors into the same buckets with high probability, letting a search restrict comparisons to items in matching buckets rather than the full dataset.
Key Trade-Offs
ANN indexes generally let you tune three interacting factors:
- Speed — how fast a query returns
- Recall — how close the approximate results are to the true nearest neighbors
- Memory/index size — how much space the index structure itself takes up
Pushing for higher recall generally costs more time and/or memory; pushing for speed generally costs some recall. Most vector databases expose tunable parameters (like the number of graph connections in HNSW, or the number of clusters searched in IVF) letting you land wherever your application's tolerance for imprecision actually sits.
Why This Matters for RAG and Semantic Search
In retrieval-augmented generation, ANN search is what finds the handful of relevant document chunks to feed into an LLM's context before it answers a question. Search latency directly affects user-facing response time, and at production scale — millions of documents, many concurrent users — brute-force search simply isn't viable. ANN is the mechanism that makes semantic search over large knowledge bases fast enough to feel instantaneous.
The Bottom Line
ANN search trades a small, usually imperceptible amount of accuracy for a dramatic improvement in speed and scalability, using techniques like HNSW graphs, clustering-based indexes, and vector compression to avoid comparing a query against every item in a dataset. It's the foundational technique behind virtually every production vector search system today, and understanding its speed-recall-memory trade-off is essential for tuning any system that depends on fast similarity search at scale.