Click anywhere to drop a query. See exact nearest-neighbor search compare against an approximate (IVF) index that only probes a few clusters — trading a little recall for a big speedup.
Once you've turned text (or images, or users) into embeddings — vectors where similar things sit close together — almost every interesting task becomes the same question: given a query vector, which stored vectors are nearest? That's nearest-neighbor search, and it powers semantic search, RAG retrieval, recommendations, and de-duplication.
The obvious approach is brute force: measure the distance from the query to every stored
vector, sort, and take the closest k. It's beautifully simple and always exact. The catch is
cost: it's O(n) per query. With a few thousand vectors that's instant. With a few billion
(web scale), checking every one for every query is hopeless — you'd burn a data center per search.
Approximate Nearest Neighbor (ANN) search trades a tiny bit of accuracy for a huge speedup. The
classic IVF (inverted file) recipe is intuitive: once, ahead of time, cluster all the
vectors into buckets (using k-means — the ◆ centroids below). At query time, you don't search every
bucket — you find the few centroids nearest the query and search only those buckets
(n_probe of them). If the points are clustered well, the true neighbors are almost always in
the nearest bucket, so you get the same answer while comparing against a fraction of the data.
"Almost always" is the catch — and the lesson. A true neighbor sitting just across a bucket boundary
can be missed if you don't probe its bucket. That's why ANN reports recall (what fraction
of the exact top-k it found). Raising n_probe searches more buckets → higher recall, less
speedup. This recall ↔ speed dial is the entire game. Drop a query below and watch it.
★ query · ◆ cluster centroid · green ring = exact top-k · blue ring = ANN result · shaded = probed clusters
Each colored dot is a stored vector; its color is the cluster it was assigned. The ★ is your query.
The green rings mark the exact top-k (brute force checked
every dot). The dashed blue rings mark what ANN returned after
searching only the shaded (probed) clusters. When the two agree, recall is 100% — ANN found the truth
with far fewer comparisons. Move the query near a cluster boundary, or set n_probe = 1, to
watch ANN miss a true neighbor and recall drop — then raise n_probe to recover it.
IVF is the easiest ANN method to picture, but production systems often use HNSW (a navigable small-world graph) which hops through a graph of vectors to reach the neighborhood fast, usually beating IVF on the recall/speed curve. Libraries like FAISS, and vector databases like Chroma, Qdrant, and pgvector, implement these so you don't have to — but the tradeoff you just felt (probe more → higher recall, lower speed) is universal. Tuning it is the job.