How vector search works
RAG, recommendations and "find similar" all need the closest points among millions, fast. Here's how, and what it costs.
An embedding turns text into a point in space, with similar meanings close together. Checking the distance to every point works, but not at a billion vectors. So nearly every vector database builds a navigable graph ahead of time and walks it. HNSW is the default in Pinecone, Qdrant, Weaviate, pgvector and FAISS.
Greedy search on a graph
Click to drop a query. Search starts at a fixed node and hops to the neighbor closest to your query until none is closer. It touches very few nodes.
Set "links / node" to 2 and try again. With fewer links, it gets stuck and misses the true nearest point more often.
Why brute force loses
In high dimensions, the only way to be sure you have the closest point is to check them all. Vector search gives up that guarantee. It returns approximate neighbors, almost always the right ones, in a handful of hops.
Small worlds
Most links go to nearby points, and a few reach far, like "six degrees of separation."
Short links help you home in, and long ones mean you're never far from anywhere. HNSW
(Hierarchical Navigable Small World) stacks these graphs in layers, sparse on top for big
jumps and dense below for the finish. Cost grows like log(n), where a full
scan grows like n.
Where it breaks
Search can get stuck at a node with no closer neighbor while a closer point sits out
of reach. Production systems add links, start from several points and keep a short list of
candidates (the ef setting). Raise it for accuracy, lower it for speed. For
feeding passages to a language model, "almost always right" is good enough.
About the toy. It's 2D with one layer, so you can see it. Production embeddings have hundreds or thousands of dimensions, and HNSW uses several layers. The mechanism is the same.