ANN Indexes: HNSW, IVF, DiskANN & Recall vs Latency

Approximate Nearest Neighbor Indexes

A vector database answers one core question: given a query vector, which stored vectors are nearest to it? For semantic search, RAG, recommendations, and deduplication, "nearest" means most similar embedding. Comparing the query against every vector (exact k-nearest-neighbor search) is simple, but its cost grows linearly: fine for thousands of vectors, far too slow for hundreds of millions at interactive latency.

Approximate nearest neighbor (ANN) indexes trade a little accuracy for enormous speedups: they find almost always the true nearest neighbors while examining a tiny fraction of the data. HNSW, IVF, and disk-based DiskANN are the dominant families. Understanding their parameters, especially the recall vs latency trade-off, is essential for tuning any vector search system.

TL;DR

Exact kNN scans everything, which is accurate but O(n) per query. ANN examines a small candidate set, making it fast and slightly approximate.
Choose the distance metric matching your embedding model: cosine, dot product (inner product), or Euclidean (L2).
HNSW: a multi-layer proximity graph with excellent recall and speed, and high memory use. Tune M, ef_construction, and ef_search.
IVF: cluster vectors into lists and search only the nearest nprobe lists. It's memory-efficient, needs training, and pairs with quantization.
DiskANN / SSD-based graphs serve billion-scale indexes from disk with modest RAM.
Measure recall@k against exact search on your data, and tune for the recall your application needs.

Quick Example

HNSW in PostgreSQL with pgvector:

Measuring recall against exact search (Python, FAISS):

Core Concepts

Distance Metrics

Use the metric the embedding model was trained with (check its documentation). Normalizing vectors to unit length makes cosine, dot product, and L2 rankings equivalent, and lets you use the fastest one.

Why Approximate?

Exact search over N vectors of dimension d costs O(N·d) per query. At 100M vectors × 1,024 dimensions, that's about 10¹¹ multiply-adds per query. ANN indexes organize vectors so a query visits a tiny fraction of them, and accept that occasionally a true neighbor is missed. Recall@k (the fraction of true top-k neighbors returned) quantifies the accuracy, and 95–99% is typical.

HNSW (Hierarchical Navigable Small World)

HNSW builds a multi-layer graph: the top layers contain few nodes with long-range links, and lower layers contain more nodes with local links. A search enters at the top, greedily moves toward the query, and descends layers, refining with a candidate list at the bottom layer.

Strengths: excellent recall and speed, and incremental inserts without retraining. Weaknesses: high memory (vectors plus graph must be in RAM for speed), slow builds at scale, and deletes that degrade the graph until it's rebuilt.

IVF (Inverted File Index)

IVF runs k-means to partition vectors into nlist clusters (Voronoi cells). Each vector is stored in its nearest cluster's list. At query time, only the nprobe closest clusters are searched.

nlist: the number of clusters (often around √N to 4√N).
nprobe: clusters searched per query, the recall-latency knob.

IVF needs a training step on representative data, and it's usually combined with product quantization (IVF-PQ) for compact memory. See vector quantization. Recall drops if the data distribution shifts away from the training data, so retrain periodically.

Disk-Based Indexes

DiskANN (Vamana graph) and similar designs keep a compressed representation in RAM, and full vectors plus the graph on SSD, serving billion-scale indexes from a single machine with good recall and low latency. Many managed vector databases and pgvectorscale (StreamingDiskANN) use these ideas to cut memory costs.

Other Approaches

Flat (brute force): exact, and perfectly fine up to roughly 100k–1M vectors, especially on GPUs.
ScaNN (Google): anisotropic quantization plus reordering, very fast.
GPU indexes (FAISS GPU, cuVS CAGRA): massive throughput for batch and high-QPS workloads.
Tree methods (Annoy): simple and memory-mappable, but largely superseded.

Choosing and Tuning an Index

Tuning loop: build the index, compute ground truth with exact search on a sample of real queries, sweep ef_search or nprobe, and pick the lowest-latency setting that meets your recall target at your expected QPS.

Best Practices

Measure Recall on Your Own Data

Public benchmarks (ANN-Benchmarks, VectorDBBench) are useful, but your embeddings, dimensionality, and query distribution determine real recall. Keep a ground-truth evaluation set.

Tie Recall Targets to End Quality

For RAG, a few points of ANN recall often matter less than chunking, hybrid search, and reranking. Retrieve more candidates (a larger k) and rerank, rather than pushing ANN recall to 99.9% at high cost.

Plan for Updates and Deletes

Graph indexes degrade with heavy deletes. Schedule rebuilds or compaction, and understand your engine's segment or merge behavior.

Budget Memory

HNSW memory is roughly vectors (N × d × 4 bytes for float32) plus graph links (N × M × 2 × 4–8 bytes). Estimate before choosing hardware, and consider quantization for large corpora. See vector search scaling.

Common Mistakes

Using the Wrong Distance Metric

Indexing with L2 when the model expects cosine or dot product (and vectors aren't normalized) silently degrades relevance. Match the model's metric, or normalize vectors.

Tuning Only on Default Parameters

Default ef_search values can yield mediocre recall on some datasets. Always sweep the query-time knob, and measure.

ANN Where Exact Search Suffices

For 50k vectors, a flat index returns exact results in milliseconds. ANN adds complexity and approximation for no benefit.

FAQ

What is approximate nearest neighbor search?

A family of algorithms that find vectors most similar to a query without comparing against every stored vector. They use graphs, clustering, or trees, plus compression, to examine a small candidate set, and they return results that are almost always the true nearest neighbors, much faster than exact search.

What is HNSW?

Hierarchical Navigable Small World: a graph-based ANN index with multiple layers of proximity graphs. Searches navigate from sparse upper layers to dense lower layers. It offers some of the best recall-speed trade-offs and supports incremental inserts, at the cost of significant memory.

HNSW or IVF?

HNSW generally offers better recall and latency, and easy incremental updates, when the index fits in RAM. IVF (especially IVF-PQ) uses far less memory and scales to very large datasets, but requires training and usually has lower recall at the same speed. Many systems use HNSW up to tens of millions of vectors, and IVF-PQ or DiskANN beyond that.

What recall should I aim for?

Commonly 90–99% recall@k, depending on the application. Search and RAG with reranking tolerate lower ANN recall, since you can retrieve extra candidates, while deduplication or exact-match-sensitive tasks need higher recall. Tie the target to end-task metrics.