Chapter 3: Exact Search

Time: 30 minutes. Cost: $0. This lab uses random vectors, so it needs no embedding model and no API key.

The short version

• Exact search compares the query against everything you stored. It is always right, and on a laptop it stays fast up to roughly a hundred thousand vectors.
• Past that it gets slow, and the classic shortcut, a tree index, stops helping on embeddings.
• Exact search is also your measuring stick. Its answers, plus a list of the answers people actually needed, are the two kinds of ground truth you check every faster system against.

Every search in Chapters 1 and 2 did the same thing: compare the query against every article, then sort. That is called brute force, and it has one property nothing else in this track will match. It is always right. The 10 results it returns are the 10 closest, every time, by definition.

So why does the rest of this track exist? Because "compare against everything" has a cost that grows with everything. At 16 articles you cannot even measure it. At a hundred million, it decides whether your search takes a few milliseconds or a few seconds. This chapter measures exactly where that line falls on a laptop, looks at the classic attempt to avoid brute force, the tree index, and why it fails on embeddings. Then it shows how to use exact search as a measuring stick.

An old idea: look at the neighbors

If you want to guess what a house will sell for, you look at what the most similar nearby houses sold for. Nobody needs a formula for house prices to do that. You only need the closest examples.

That is the nearest-neighbor rule: to label something new, find the known examples closest to it and borrow their label. Statisticians wrote it down in 1951, and in 1967 proved it is surprisingly good for something so simple. The rule made the hard part obvious. Once you know who the neighbors are, the rest is easy. Finding them, quickly, among millions of points, became its own field of research. That field is what vector databases are built on.

Where this came from: Fix and Hodges, Cover and Hart

In 1951, Evelyn Fix and Joseph Hodges wrote a technical report for the US Air Force School of Aviation Medicine on "nonparametric discrimination": how to sort a new observation into a category without assuming anything about how the data is distributed. The nearest-neighbor rule is one of the methods they described.

In 1967, Thomas Cover and Peter Hart proved why the rule is good. As the number of labeled examples grows without limit, the error rate of the nearest-neighbor rule is at most twice the error rate of the best possible rule. A method with no training and no model, just "look at your neighbors," is provably within a factor of two of the best anyone could do.

Words you will see for the rest of the track

• k nearest neighbors (KNN): the k stored vectors closest to a query. Ask for the top 10 and k = 10.
• Exact search: returns the true k nearest neighbors, guaranteed. Brute force is exact.
• Approximate search (ANN): returns k vectors that are probably the nearest, much faster. Chapter 4 starts there.
• Ground truth: the right answers you measure a search against. The last section of this chapter covers the two kinds you will use.

The real cost of brute force

Scoring one query against one stored vector of 768 numbers takes 768 multiplications and 768 additions. Do that for N stored vectors and the work grows in a straight line with N. Doubling the collection doubles the time. Memory grows the same way: each number is a 4-byte float, so one 768-dimension vector is about 3 KB, and N of them take N × 3 KB.

How fast is that in practice? It depends heavily on how you run it. The lab scores 2,000 vectors two ways, with identical results:

plain Python loop     92.52 ms
numpy                  0.53 ms

Same algorithm, about 175 times faster on that run (your ratio will differ). The plain loop is a cashier typing in every price by hand. numpy is the scanner: it hands the whole job to optimized code that uses your processor's vector instructions, which process several numbers in a single step. Vector search libraries do the same. So brute force is a lot faster than people assume, and the lab measures how far it goes:

     vectors  ms/query    memory
      10,000      0.21      31 MB
      30,000      0.74      92 MB
     100,000      2.07     307 MB

  Projected from the 100,000 measurement (same machine, same 768 dimensions):
     1,000,000 vectors  ~      21 ms/query  ~     3 GB
    10,000,000 vectors  ~     207 ms/query  ~    31 GB
   100,000,000 vectors  ~   2,072 ms/query  ~   307 GB

Those numbers came from an Apple silicon laptop. Yours will differ, but the shape will not: a straight line in both time and memory.

That table shapes a practical decision. Up to roughly a hundred thousand vectors, brute force is a perfectly good production choice. It is exact, has no index to build or tune, and answers in a couple of milliseconds. pgvector, which you will use in Chapter 7, does exact search by default until you create an index. Measure on your own hardware, and do not add an approximate index you do not need.

Brute force runs out at the bottom of the table, and it hits two walls at once. Two seconds per query is too slow for a search box, and that is one query: ten users searching at once need ten times the processor time. And 307 GB of vectors is more memory than most servers you would rent for this, so you cannot even keep it all in memory to scan.

The classic shortcut: trees

You already know the trick for avoiding a full scan in one dimension. To find a word in a sorted dictionary, you do not read every page. You open the middle, see you are too far, and throw away half the book. Repeat, and a million entries take about 20 steps.

In 1975, Jon Bentley published the k-d tree, which extends that idea to many dimensions. Split the points in half on the first coordinate. Split each half on the second coordinate. Keep going, cycling through the coordinates, until each group is small. To search, walk down to the query's own group and find the closest point there. Then back up, and only check a neighboring group if the dividing line is closer than the best match you have found so far. If it is not, nothing on the far side can win, and the whole group is skipped without looking.

In this picture the query's best match in Group A is closer than the line x = 0.5, so nothing on the right side of that line can beat it. Groups C and D are never opened.

In two dimensions this is spectacular. The lab builds a k-d tree over 20,000 random points and counts how many points the search actually has to compare:

  dimensions  points checked  same answer as brute force
           2           0.1%                    20 of 20
           4           0.3%                    20 of 20
           8           7.5%                    20 of 20
          16          92.9%                    20 of 20
          32         100.0%                    20 of 20
         128         100.0%                    20 of 20

At 2 dimensions it checks one point in a thousand. At 16, it checks 93% of them. From 32 up, it checks every single one and does extra work walking the tree, so it can only be slower than plain brute force.

Why the tree gives up

Two things go wrong at once, and you have already met the second one.

The tree runs out of splits. Each level of the tree halves the points, so 20,000 points with up to 16 per group make a tree about 11 levels deep. That is about 11 splits, one coordinate each. In 2 dimensions, that is five or six cuts on x and on y, plenty. In 128 dimensions, the tree splits on about 11 coordinates and never looks at the other 117. Imagine sorting people into groups by height, then shoe size, and never asking anything else: your group matches you on two things and can differ on everything that matters. So the first "best match" is a poor one, and its distance is too large to rule anything out.

The skipping test stops passing. The tree skips a group only when the dividing line is farther away than the best match found so far. In Chapter 2 you measured that in high dimensions the nearest point is barely closer than the farthest. So the best match is always far away, almost every dividing line is closer than that, and almost nothing gets skipped.

This is not a flaw in this particular tree. Researchers who analyzed tree indexes in 1998 found that, on average, a plain scan of everything beat them once data went beyond about 10 dimensions.

The details: who worked this out, and under what assumptions

The search procedure for k-d trees, including the skipping test, was worked out in a 1977 follow-up by Friedman, Bentley, and Finkel.

The 1998 analysis is by Weber, Schek, and Blott, and it covers tree and partitioning indexes in general. Its result is for uniformly distributed data under their cost model, but the pattern matches what you just measured.

Notice the last column of the table, though: 20 of 20, every time. The tree never gave a wrong answer. It lost all of its speed and none of its accuracy, because it is an exact method. That is the real lesson of this chapter. In high dimensions, if you insist on the exact answer, you pay for brute force. Every fast method from here on gets its speed by accepting that it will sometimes miss a true neighbor, and then measuring how often.

Two kinds of ground truth

"Measuring how often" needs something to measure against. That is ground truth, and in practice you need two kinds, because a search can fail in two different ways.

Think of a restaurant. The kitchen can cook something other than what is on the order ticket. Or the kitchen can cook exactly what is on the ticket, and it is still not what you wanted, because the ticket itself was wrong. Checking one tells you nothing about the other.

1. Did the fast search return what exact search would? This is the kitchen check. Exact search is the order ticket: its top 10 is, by definition, the right answer for the index. Comparing the two tells you how much the index loses. It needs no people, only computer time.

2. Did search return what the person needed? This is the customer check. Exact search can be perfectly exact and still wrong. You already saw it happen: in Chapter 1, TF-IDF compared the query against all 16 articles, no shortcuts, and the article that answered the question came fourth. To catch that, you need a list of questions together with the documents that actually answer them. That list takes human judgment to build.

The two numbers point to different fixes:

	Fast search matches exact search	Fast search misses some of it
Exact search finds the right document	Working as intended	Tune the index (Chapters 4 to 6)
Exact search misses it	Fix the vectors or the method: the model, how you cut documents into chunks, or adding keyword search (Chapters 8 and 9)	Fix the method first, then tune the index

Building each one in production

The index check is mechanical:

1. Save a few hundred real questions from your search logs.
2. Run each one with exact search and keep its top 10. That is slow on a big collection, but this is a check you run occasionally, not something users wait for. Chapter 7 does it inside PostgreSQL.
3. Run the same questions through the index and count how many of each top 10 it returned. Chapter 4 names that number recall.
4. Repeat after anything changes: an index setting, a large batch of new documents, a new embedding model.

The labeled set takes judgment. Here are four ways to get one, from most trustworthy to cheapest:

• Ask people who know the content. Take 50 to 100 real questions and have someone who knows the documents mark the ones that answer each. It is slow, and it is the set you can trust most.
• Reuse work people already did. A support ticket that an agent closed by linking a help article is a question with a labeled answer. Clicks on search results are a weaker signal, because people tend to click whatever is on top.
• Use a public dataset. From Chapter 4, this track uses SQuAD, where every question was written about one known paragraph. Chapter 10 uses HotpotQA, where each question comes with the two paragraphs needed to answer it.
• Generate questions from your documents. Give a language model a paragraph and ask it to write a question the paragraph answers. The paragraph is the label. It is cheap and fast, but the questions tend to reuse the paragraph's own words, which makes keyword search look better than it will on real users' questions. Chapter 8 sees that effect on SQuAD, whose questions were written by people looking at the paragraph.

Why go to this trouble? Because the second kind is where many wrong answers start. If search never hands the language model the paragraph that holds the answer, the model can only say it does not know, or answer from memory and possibly make something up. A labeled set tells you how often the right paragraph made it into the prompt, and that caps how often the answer can be right. Grading the written answer itself is the other half of the job. If you did the Intermediate track, Chapter 8: Evaluating What You Built does that with a second model as the judge.

Hands-on lab: brute force and a k-d tree

You will compare a plain Python loop with numpy, time brute force at three collection sizes, and build a small k-d tree you can read from top to bottom, about 40 lines, then watch it lose its advantage as the dimensions climb. The lab covers the speed half of this chapter. Chapter 4's lab builds the first kind of ground truth and measures an index against it.

Full instructions: download the Vector Databases labs ZIP, then open labs/vector-databases/03-exact-search and follow its README.

The output is the three tables shown in this chapter. The timings depend on your machine. The k-d tree percentages use a fixed random seed and should match closely.

Checkpoint

Your company has 5,000 closed support tickets, each with the help article the agent linked to close it. How can you use them to measure your search, and what is one weakness?

Treat each ticket's text as a question and the linked article as its labeled answer. Run every ticket through your search and count how often the linked article appears in the top 10. That is the second kind of ground truth, built from work people already did. One weakness: an agent links the article they found, not necessarily the best one, and only one even when several would help, so a search can return a good answer and still be counted as a miss.

From the lab's timing table, how would brute-force query time and memory change if you went from 100,000 to 400,000 vectors?

Both roughly quadruple, because brute force does the same work for every vector and stores every vector in full. About 8 ms per query instead of 2, and about 1.2 GB instead of 307 MB, on the machine that produced the table.

In 128 dimensions, the k-d tree checked 100% of the points but still found the right answer every time. Why both?

It is an exact method. It only skips a group when it can prove nothing there is closer, so it never misses. In 128 dimensions it can almost never prove that, so it ends up checking everything, which is brute force with extra overhead.

Check Your Knowledge

Click to start the quiz

1. Your team has 50,000 product descriptions as 768-dimension embeddings and plans to stand up a cluster with an approximate index "to be safe." Based on the lab, what would you recommend first?

An approximate index is required, because brute force cannot handle more than 16 vectorsTry brute force first: at this size it is exact, needs no index, and answered in about a millisecond in the lab; add an approximate index only when measurements show you need itA k-d tree, because it is exact and faster than brute force at 768 dimensionsReduce the embeddings to 2 dimensions so a k-d tree can search them

2. In Part 1, numpy scored 2,000 vectors hundreds of times faster than the plain Python loop. The exact ratio depends on your machine. Why is it so much faster?

numpy skipped vectors that were clearly too far awaynumpy used an approximate method that rounds the scoresnumpy cached the answer from an earlier runIt runs the same multiply-and-add in optimized compiled code that uses the processor's vector instructions; the algorithm and results are identical

3. For which of these tasks is a k-d tree a strong choice?

Finding the nearest coffee shop to a phone's latitude and longitudeFinding the most similar support article using 768-dimension text embeddingsFinding the most similar product image using 512-dimension image embeddingsAny task, as long as the collection has more than a million items

4. After adding a fast index, you check it against exact search: it returns 99 of every 100 results exact search would. Users still say the right document is often missing. What should you do next?

Tune the index until it matches exact search 100% of the time, because the missing 1% explains the complaintsRemove the index and switch to exact search, because exact search always returns the right documentBuild a labeled set of real questions and the documents that answer them, and test exact search against itRaise the similarity threshold, so that fewer unrelated documents reach the user

What's next

To go faster in high dimensions, you have to let go of "guaranteed exact." Chapter 4 does that the way the field first did it: hashing similar vectors into the same bucket, and clustering the collection so you only search the nearest clusters. It also introduces recall, the number that tells you how much accuracy you gave up, and switches to a collection of 18,896 Wikipedia paragraphs, big enough for speed to matter.