How Vector Search Finds the Closest Matches
See how vector databases find the closest matches among millions in milliseconds, and what they trade for it.
Finding the closest vectors sounds easy: compare the question with every stored vector, keep the best few. That’s exact search, and for a few thousand documents it’s perfectly fine. Now try it with 100 million vectors of 1,536 numbers each. Every single question means 100 million comparisons, hundreds of billions of multiplications. Too slow, too expensive.
The way out is approximate search. Think of finding the nearest café in a city. You don’t walk to every café; you go to the right neighbourhood and look around there. Vector indexes do the same, organising vectors ahead of time so a search can skip almost all of them.
- Clusters (IVF): group the vectors into neighbourhoods, each with a centre. At search time, find the few nearest centres and only check the vectors in those groups.
- Graphs (HNSW): link every vector to a few near neighbours, in layers from coarse to fine. A search hops from neighbour to closer neighbour, like asking for directions, until it can’t get any closer.
The price is in the name: approximate. Now and then the true nearest vector sits just over the border of a neighbourhood you didn’t visit, and it’s missed. The share of true best matches that are actually found is called recall. Every index has a dial: search more neighbourhoods, or hop more carefully, and recall rises, but so does the work.
In practice the trade is excellent: checking a small fraction of the vectors typically finds well over 90% of the true best matches, in milliseconds. And for RAG, the very closest vector isn’t sacred anyway: the second closest is usually just as good an answer.
Key takeaways
- Exact search compares the question with every vector: fine for thousands, too slow for millions.
- Approximate nearest-neighbour indexes skip most vectors, using clusters (IVF) or neighbour graphs (HNSW).
- Recall measures how many of the true best matches are found.
- A dial trades recall for speed; small sacrifices in recall buy huge speed-ups.
Check your understanding
Go deeper (more technical)
IVF (inverted file index) clusters vectors with k-means (Track 1’s unsupervised learning). HNSW (hierarchical navigable small world graphs, Malkov and Yashunin, 2016) is the most widely used graph index. Indexes are often combined with vector compression (product quantization) so billions of vectors fit in memory.
Search speed also depends on the hardware: similarity is matrix maths, so large deployments run on GPUs (Track 3), and libraries such as FAISS include GPU indexes.
The simulation’s comparison counts and timings are illustrative.