Why vector search cannot just check everything

When a chatbot answers questions about your documents, one step does most of the work. It takes your question, finds the few paragraphs that are about the same thing, and hands those to the model. The rest is prompt formatting.

That step is called nearest neighbour search, and it has a scaling problem worth seeing rather than reading about. This post builds it up from two dimensions, where you can see everything, to the point where you can’t check everything, and then shows the algorithm that most vector databases use to skip the checking.

A sentence becomes a point

An embedding model takes text in and gives a list of numbers out. The list is fixed length. 1,536 numbers is a common size. The model is trained so that texts with similar meaning get similar lists.

That’s the whole idea. “Kitten” and “cat” get lists that are nearly the same. “Kitten” and “truck” get lists that are far apart.

A list of two numbers is a dot on a page. So here is a pretend embedding model that only produces two numbers, plotted. The axes don’t mean anything in a real model, but for this one, pretend the first number is roughly “how mechanical” and the second is “how edible”.

Figure 1. Fifteen words as points

Everything in this post is that picture with more dots and more numbers per dot. A paragraph of your document gets a list of 1,536 numbers instead of two, and your question gets one too. Finding “the paragraphs about the same thing” means finding the dots closest to the question dot.

Measuring “close”

Two ways are common. The figure above can show both.

Straight-line distance

The ruler measurement. For two points, subtract each coordinate, square the differences, add them up, and take the square root:

distance = sqrt((x1 - x2)² + (y1 - y2)²)

That’s Pythagoras. With 1,536 numbers per point the formula has 1,536 terms inside the square root instead of two, and nothing else changes. People call this Euclidean distance.

The angle between them

Treat each point as an arrow from the origin. Two arrows pointing the same way have a small angle between them, whatever their lengths. Cosine similarity is the cosine of that angle:

cos θ = (a · b) / (|a| × |b|)

a · b is the dot product: multiply the arrows coordinate by coordinate and add up the results. |a| is the arrow’s length. The result is 1 when the arrows point the same way, 0 when they are at right angles, and -1 when they point in opposite directions.

Switch Figure 1 to “Angle (cosine)” and you’ll see the arrows and the angle between the question and whichever word you hover. Notice that “sushi” is a long way from “kitten” with a ruler but only a couple of degrees away by angle. The angle only cares about direction from the origin, so anything along the same line counts as the same.

In a real embedding model that’s usually what you want. Length tends to track things like how long or how emphatic the text was rather than what it was about, so most vector search ignores it and uses the angle. In this made-up map it’s a reminder that the two measures can disagree, and the choice is part of the design.

Either way, the cost of one measurement is the same: about one multiply and one add per number in the list. Hold on to that, it’s what the rest of the post is about.

Where this sits in RAG

Retrieval-augmented generation is a pipeline with the search in the middle:

1. Cut your documents into chunks, a paragraph or so each.
2. Run every chunk through the embedding model and store the vectors. Do this once.
3. When a question arrives, embed it the same way.
4. Find the k stored vectors closest to the question vector.
5. Paste those chunks into the prompt and let the model answer.

Steps 1 to 3 are a fixed cost per chunk and per question. Step 4 is the one that depends on how many chunks you have, and it runs on every question.

The honest way: check everything

The obvious way to find the closest vectors is to measure the distance to every vector and keep the smallest. This is called brute force, and it’s exact: it never misses.

Here it is in three dimensions. The chunks are coloured by topic because real embeddings clump like this, and the question is the orange point.

Figure 2. Brute force, with a growing library

Read the readout as the slider moves. The number of distance computations is always the number of chunks, and each one costs a multiply-add per number in the vector. So the work per question is:

work = chunks × numbers per vector

Some real sizes, at 1,536 numbers per vector:

Chunks	Multiply-adds per question	Vector storage (4-byte floats)
10,000	15 million	61 MB
1,000,000	1.5 billion	6.1 GB
100,000,000	150 billion	614 GB

The bottom row is one question. A single fast CPU core does a few tens of billions of multiply-adds a second, so that’s several seconds of pure arithmetic, per question. Worse, the vectors don’t fit in memory on one machine, and even if they did, reading 614 GB once at typical memory speeds takes over ten seconds. Now serve a thousand questions a second.

Brute force is fine up to a hundred thousand vectors or so, and it’s the right choice there because it’s exact. Past that, the per-question cost grows in lockstep with the library, and no amount of hardware makes “read everything for every question” a good plan.

Why the pictures stop at three dimensions

Three numbers per point is the most a screen can show. The formulas don’t care: a 1,536-number vector uses the same distance and the same angle, with a longer sum. The figures use three so you can watch the search, and the readouts scale the arithmetic to the real size.

Skipping most of the work: HNSW

The fix is the same one you use to find a house in a new city. You don’t check every house. You take a highway to roughly the right area, a main road to the right neighbourhood, then side streets to the door.

Hierarchical Navigable Small World graphs, HNSW, build that road system over the vectors. It’s the index inside most vector databases, and it’s made of two ideas: layers and links.

Layers from coin flips

Every chunk goes on the bottom layer, layer 0. Then flip a weighted coin. With probability about 1 in M (M is a setting, usually 8 to 16), the chunk also goes on layer 1. Flip again for layer 2, and so on until the coin says stop.

The exact rule is level = floor(-ln(u) / ln(M)) for a random u between 0 and 1. That works out to each chunk having a 1 in M chance of reaching each next layer up. With a million chunks and M = 8, layer 1 has about 125,000, layer 2 about 16,000, layer 3 about 2,000, and the top few layers hold a handful. The top layers are the highways: sparse, so a hop covers a lot of ground.

Links to neighbours

On every layer a chunk lives on, it gets linked to about M of its nearest neighbours on that layer. Layer 0 allows 2M links, since it holds everything and needs the extra routes.

There’s one refinement that matters. Picking the M closest neighbours would link every chunk only to its own clump, and a search could get stuck in a clump. So a candidate is skipped if it’s closer to an already-chosen neighbour than to the chunk itself. That spreads the links out in different directions, which is what makes the graph navigable.

Building the index uses the search below to find each new chunk’s neighbours, so the graph grows one chunk at a time. Figure 3 does exactly that when you move the size slider.

The search

Start at the single entry chunk on the top layer. Look at its links, measure their distance to the question, and move to whichever neighbour is closest. Repeat until no linked neighbour is closer than where you are. That’s as close as this layer gets you, so drop down a layer at the same chunk and keep walking.

On layer 0 the walk widens a little: instead of one current position it keeps the best ef candidates found so far and explores from each of them. ef is the search width. Bigger means more distance checks and a better answer.

Figure 3. HNSW searching the same kind of library

Watch the “Distance checks” number. For a thousand chunks the search typically measures a few dozen. Brute force measures a thousand.

What it costs

Each layer is a short greedy walk, and each step of the walk costs about M distance checks. The number of layers grows with the logarithm of the library size, because each layer is M times smaller than the one below. So the total is roughly:

checks ≈ (layers × hops per layer × M) + (ef × 2M on layer 0)

Going from a thousand chunks to a hundred million adds a few layers, so a few more short walks. A search that costs a hundred checks at a thousand chunks costs maybe a thousand at a hundred million. Brute force went from a thousand to a hundred million. That gap is the whole reason vector databases exist.

What it gets wrong

HNSW is approximate. The greedy walk can settle in a spot where no neighbour is closer even though a better chunk exists two hops away. Figure 3’s readout says whether the true nearest chunk was found and how many of the top five match brute force. Push ef down to 1 and ask a few random questions and you’ll see it miss. Push it up and it stops missing and costs more.

That’s the trade. Recall against speed, and ef is the dial. In practice indexes run at 95 to 99 percent recall for a tiny fraction of the brute force cost, and for “find me relevant paragraphs” that’s more than good enough.

Putting it back together

One question through a RAG system with an HNSW index:

1. The question becomes a 1,536-number vector. One model call.
2. The index walks down its layers: a few hundred distance checks out of millions of chunks.
3. The top k chunks come back in a few milliseconds.
4. They go into the prompt.

The embedding model decides what “about the same thing” means. The index decides whether finding it is affordable. Everything you saw in the three figures is that second decision.