Exact vs Approximate Nearest-Neighbour Search
Why brute-force vector search stops scaling, what approximate search trades away, how recall@k is measured, and the main index families.
Brute force and when it is enough
The simplest vector search computes the similarity between the query and every stored vector, then keeps the top k. This is called a flat or exact index.
Cost per query ≈ N × d multiply-adds. For 1M vectors of 768 dims that is ≈ 768M operations, a few milliseconds on a modern CPU with SIMD, or far less on a GPU. For 100M vectors it is 100× more: hundreds of milliseconds per query on one CPU, before you reach any real QPS.
Exact search is the right answer more often than people think:
- Up to about 1M vectors, or more with GPU brute force.
- With highly selective filters. If a filter leaves only 5,000 candidates (one user's documents), just score those 5,000.
- For ground truth when measuring an ANN index's recall.
Approximate nearest neighbour (ANN)
ANN indexes organise vectors so a query examines only a small fraction of them. The trade: results are probably the true nearest neighbours, not certainly.
Measuring quality: recall@k
Recall@k = |ANN top-k ∩ exact top-k| ÷ k
Measure it by running a sample of real queries through both the ANN index and exact search, then comparing. Every index has knobs, such as ef_search for HNSW or nprobe for IVF, that trade recall against latency. The right setting comes from this curve on your data, not from a blog post.
Remember that retrieval recall is not answer quality. An ANN index at 95% recall is rarely the weak point in a RAG system. Chunking, the embedding model, and missing hybrid search usually cost far more.
The index families
| Family | Idea | Strengths | Weaknesses |
|---|---|---|---|
| Graph (HNSW) | Link each vector to its neighbours. Search by hopping greedily toward the query | Best recall/latency trade-off in memory. Incremental inserts | Memory-hungry (vectors + links). Deletes are awkward |
| Clustering (IVF) | Partition vectors into clusters. Search only the nearest few | Compact, fast to build, works well with compression | Needs training. Recall drops at cluster edges |
| Compression (PQ, scalar, binary) | Store small codes instead of full floats | 4–64× less memory | Approximate distances, so it needs rescoring |
| Disk-based graph (DiskANN-style) | Graph on SSD, compressed vectors in RAM | Billions of vectors per node at low cost | SSD latency; more complex |
These combine: IVF-PQ (clusters plus compressed codes) is the classic billion-scale index, and HNSW + PQ or HNSW + int8 shrinks the memory footprint of graph indexes. The next two lessons cover HNSW and IVF and PQ in depth.
Filtering: the hard part
Real queries rarely ask only for the nearest vectors. They ask for the nearest vectors where tenant = 42 and language = en and date > last month. The strategies are:
- Post-filtering: ANN top-k, then drop non-matching results. This is fast, but if the filter is selective you may end up with zero results.
- Pre-filtering: filter first, then search only the matches. This is exact, but it breaks graph navigation when matches are sparse, so the engine falls back to brute force over the matches.
- Filtered or in-index search: modern engines apply the filter during graph traversal and switch strategy based on the filter's selectivity. Ask how a vector database handles this before choosing it.
Key takeaways
- Exact (flat) search compares the query with every vector. It is perfect recall at O(N × d) cost, fine up to around a million vectors.
- Approximate nearest-neighbour (ANN) indexes skip most vectors and trade a little recall for 100–1,000× less work.
- Recall@k is the share of the true top-k neighbours returned. Tune index parameters against it on your own data.
- There are three families: graphs (HNSW), clustering (IVF) and compression (PQ), often combined.