Semantic search sounds simple: embed the query, find the closest stored vectors. But "find the closest among a billion vectors" is a genuinely hard computational problem, and the answer that makes it practical is approximation.
Why exact search doesn't scale
To find the exact nearest vectors, you'd compare the query against every stored vector — fine for a thousand, hopeless for a billion. Every query would take too long. So production systems give up a tiny bit of accuracy for an enormous speedup, using approximate nearest-neighbor (ANN) search: find vectors that are almost certainly among the closest, very fast.
Perfect nearest-neighbor search is too slow to use. Approximate search that's 99% as accurate and 1000x faster is what actually ships.
HNSW: the workhorse
The most popular ANN method is HNSW (Hierarchical Navigable Small World). The intuition: build a layered graph connecting similar vectors, with sparse "highway" connections at the top and dense local ones at the bottom. To search, you start at the top, jump quickly toward the right region, then refine downward — like zooming in on a map. You reach the neighborhood of the answer in a few hops instead of scanning everything.
The tradeoffs
ANN methods have knobs that trade accuracy for speed and memory: search more of the graph for higher recall but slower queries, or less for the reverse. HNSW is fast and accurate but memory-hungry; other methods (IVF, quantization-based) trade differently. Choosing and tuning depends on your scale and latency needs.
Why it matters
Every large-scale semantic search, RAG system, and recommendation engine relies on ANN under the hood — usually you never see it, because your vector database handles it. But understanding that "vector search" is really "approximate vector search" explains its behavior: it's fast because it's willing to occasionally miss the true nearest neighbor, a trade that's almost always worth it.
