Chapter 4: Approximate Search
Time: 40 minutes, plus about 3 minutes to build the shared dataset once on a fast laptop, or 20 minutes or more on one without a GPU. Cost: $0 with Ollama, about 6 cents with OpenAI.
- Approximate search skips most of the collection and accepts that it will sometimes miss one of the true closest results. Recall measures how often it misses.
- Two classic ways to skip: sort vectors into buckets at random (LSH), or group them by what they are about and search only the nearest groups (IVF). Grouping by content wins clearly.
- Defaults matter. IVF's out-of-the-box setting found fewer than half of the true top 10 in this chapter's lab. One setting fixes it.
Suppose your search returns 9 of the 10 closest paragraphs instead of all 10. Would your user notice?
Most of the time, I do not think they would. In Chapter 2 you saw that similarity scores bunch together. The paragraph in 10th place and the one in 11th place often score within a hair of each other. Swapping one for the other rarely changes the answer a person, or a language model, gets out of the results.
Chapter 3 ended with a hard rule: in high dimensions, if you insist on the exact answer, you pay for brute force. This chapter takes the other road. Give up a little accuracy, skip most of the work, and measure exactly how much accuracy you gave up. Nearly every vector index you will configure is built on that bargain. Exact search still exists, and pgvector, for one, searches exactly until you add an index. It just gets slow as the collection grows.
A bigger collection​
Sixteen help-desk articles were perfect for seeing every score. They are useless for this chapter, because brute force on 16 vectors takes no time at all. From here through Chapter 6, the labs share a bigger collection.
It comes from SQuAD, the Stanford Question Answering Dataset, published in 2016. Crowdworkers read Wikipedia paragraphs and wrote more than 100,000 questions about them. The lab uses the training set: 18,896 paragraphs from 442 Wikipedia articles, and 1,000 of the questions as search queries. Every question was written about one specific paragraph, which turns out to be useful.
You embed all of it once, in about 3 minutes, and the next three labs reuse the result.
Recall: what approximate costs​
Before building anything fast, you need a way to score it. The standard one is recall@k.
Run the question through brute force and keep the exact top 10. That is the first kind of ground truth from Chapter 3, the kitchen check. Then run the same question through the fast index and count how many of those 10 it returned. Nine of ten is a recall@10 of 0.9. Average that over a thousand questions and you have one number that says how much the index loses.
There is a catch here that confuses a lot of people, and the lab shows it right away. Recall measures agreement with brute force. It does not measure whether the answer is right. Because every SQuAD question was written about one known paragraph, the lab can also run the customer check, the second kind of ground truth:
The paragraph each question came from is in the exact top 10: 59% of the time
Brute force, the perfect search, finds the paragraph each question was written about only 59% of the time. That is the embedding model's limit, not the index's. An index is built to agree with brute force, so tuning it moves you toward that 59%, not reliably past it. An approximate index can occasionally stumble onto the right paragraph when exact search ranked it 11th, but that is luck, not something you can tune for. So when a retrieval system disappoints you, measure both numbers separately: how good is exact search with this model, and how much does the index lose on top of that? They have different fixes.
Idea one: hash similar vectors into the same bucket​
The first serious attack on the problem came straight out of Chapter 3's wall, in 1998. It is called locality-sensitive hashing (LSH).
A normal hash function, the kind behind a Python dictionary, tries hard to send similar inputs to completely different places. LSH does the opposite on purpose. It wants similar vectors to collide in the same bucket, so that at search time you only look inside the query's bucket.
The version for cosine similarity is a game of yes-or-no questions. Draw a random line through the space, and ask each vector: are you on this side of it, or that side? That is one bit, a 1 or a 0. Ask 8 such questions and every vector gets an 8-bit code. Vectors with the same 8 answers share a bucket.
Why would that keep neighbors together? A random line separates two vectors with probability equal to the angle between them divided by 180 degrees. Close vectors have a small angle, so a random line rarely falls between them. Here is that math for 8 bits, for intuition:
| Pair of vectors | Angle | Same bit | Same 8-bit bucket |
|---|---|---|---|
| Cosine 0.9 (close) | 26° | 86% | 29% |
| Cosine 0.6 (typical) | 53° | 70% | 6% |
The good news: a close pair is five times as likely to share a bucket as a typical pair. The bad news: a close pair still lands in different buckets 71% of the time. So you build several tables, each with its own random lines, and check the query's bucket in all of them. More tables catch more true neighbors, and also pull in more of everything else.
Notice the second row. The lab measures how alike two random paragraphs are:
Length of the average paragraph vector: 0.78 (0 would mean no common direction)
Typical similarity between two random paragraphs: 0.60
These embeddings all lean in one shared direction, which is also why Chapter 2's scores bunched around 0.6. For LSH that is bad news. Random lines through zero would put almost every paragraph on the same side. The lab fixes that by drawing the lines through the middle of the data instead, a practical tweak rather than part of the classic method. It also means the table above shows the idea, not the lab's numbers, because the angles that matter are now measured from that middle point. Here is what LSH really delivers:
bits tables scanned recall@10
6 1 1.6% 0.06
6 16 23.0% 0.66
6 64 63.0% 0.98
8 1 0.4% 0.03
8 16 6.5% 0.37
8 64 23.2% 0.80
10 1 0.1% 0.01
10 16 1.8% 0.18
10 64 7.0% 0.52
"Scanned" is the share of all paragraphs the search had to score. Getting to a recall of 0.8 took 64 tables and scanning almost a quarter of the collection. Sixty-four tables also means storing every paragraph's ID 64 times.
LSH still has real jobs. Its first big one was finding near-duplicate pages on the web, and it comes with math you can reason about on paper. But for searching embeddings, my read is that it lost, and the next idea shows why.
Where this came from: Indyk, Motwani, Charikar, and the web
Piotr Indyk and Rajeev Motwani introduced LSH in 1998, in a paper whose title says what they were after: "Approximate nearest neighbors: towards removing the curse of dimensionality." The random-line version for cosine similarity, and the angle-over-180-degrees result, came from Moses Charikar in 2002.
On the web, Andrei Broder developed MinHash at AltaVista in 1997 to detect duplicate pages. In 2007, Google researchers showed that 64-bit fingerprints built with Charikar's method worked for near-duplicate detection across 8 billion pages.
Idea two: cluster first, then search a few clusters​
Think of a grocery store. To find pasta, you do not walk every aisle. You read the signs, go to the aisle that matches, and maybe glance at the one next to it in case the store put the pasta somewhere odd. A big store becomes a small search.
Text search engines have worked this way for decades. They keep an inverted index: for every word, the list of documents that contain it, like the index at the back of a book. To answer a query, you only open the lists for the query's words.
Vectors do not have words, so researchers made some. Group the vectors into clusters of similar ones, treat each cluster like a word or an aisle, and keep a list of which vectors sit in each. The grouping method underneath is k-means, short enough to say in one breath: pick k starting centers, assign every vector to its closest center, move each center to the middle of its group, and repeat.
An inverted file (IVF) index for vectors works like this:
The setting that matters is nprobe, the number of clusters you open per query, the number of aisles you check. Why open more than one? Because cluster borders are arbitrary. A question can land near the edge of one cluster while its best match sits just across the line in the next. Opening a few neighboring clusters catches it.
The lab builds k-means and the inverted file by hand, in about 20 lines, with 128 clusters:
Cluster sizes: smallest 36, median 141, largest 387
nprobe scanned recall@10
1 0.9% 0.48
2 1.8% 0.63
4 3.6% 0.76
8 7.2% 0.86
16 14.4% 0.93
32 28.6% 0.97
Compare the two tables at about 7% scanned. LSH found about half of the true top 10. IVF found 86%. Same budget, much better answer.
The reason is simple. LSH draws its lines at random. k-means draws them where the data actually is, so each cluster holds paragraphs that really belong together, the way a store shelves pasta with pasta. When an index can learn the shape of your data, it usually beats one that ignores it.
Two practical notes before you rely on IVF. First, the cluster sizes are uneven: the biggest cluster here is ten times the size of the smallest, and a query that lands in a big cluster costs more. Second, how many clusters to use is a judgment call, and the rules of thumb disagree. pgvector suggests starting at rows divided by 1,000, which is about 19 here. The FAISS guidelines, for collections under a million vectors, suggest 4 to 16 times the square root of the collection size, which is over 500 here. I used 128. Pick a starting point, then measure recall at a few nprobe values on your own data.
Where this came from: from Bell Labs to "Video Google"
k-means is older than all of this. Stuart Lloyd worked it out at Bell Labs in 1957, though it was not published until 1982, and James MacQueen gave it the name in 1967.
In 2003, Josef Sivic and Andrew Zisserman's "Video Google" system grouped image features into clusters, called each cluster a "visual word," and then used an inverted file and TF-IDF straight out of text retrieval. In 2011, Hervé Jégou, Matthijs Douze, and Cordelia Schmid combined an inverted file with vector compression, the design FAISS's IVF indexes are built on. You will meet the compression half in Chapter 6.
The library everyone uses: FAISS​
In 2017, Facebook AI Research open-sourced FAISS, its library for vector search. FAISS is not one algorithm. It is a toolbox that holds brute force, IVF, the compression methods in Chapter 6, and the graph index in Chapter 5, all behind one interface.
The lab builds the same 128-cluster index in FAISS, then times one question at a time on one processor core, the way a server handles a single user's search:
index ms/query recall@10
brute force (Flat) 0.746 1.00
IVF, nprobe=1 0.018 0.46
IVF, nprobe=4 0.036 0.75
IVF, nprobe=8 0.063 0.85
IVF, nprobe=16 0.117 0.93
At nprobe 8, IVF answers about 12 times faster than brute force and keeps 85% recall. At 18,896 paragraphs, both are fast enough that nobody would notice. The point is the ratio. IVF's work grows with the share it scans. On a collection of 100 million vectors, scanning 7% instead of 100% is roughly the difference between Chapter 3's two seconds and a small fraction of one.
Now look at the first IVF row. FAISS's default nprobe is 1, and so is pgvector's default number of probes. Build an IVF index, leave the default, and in this lab you get fewer than half of the true top 10. It is easy to conclude that "vector search does not work for our data" when the real problem is one setting nobody changed.
When you read a vector database benchmark, it will usually show exactly this trade as a curve: recall on one axis, queries per second on the other. The open-source ANN-Benchmarks project made that chart the standard way to compare indexes. A single speed number without a recall number next to it tells you nothing.
Who built FAISS and ANN-Benchmarks
Jeff Johnson, Matthijs Douze, and Hervé Jégou at Facebook AI Research published "Billion-scale similarity search with GPUs" in February 2017, and the company open-sourced FAISS in March. ANN-Benchmarks is by Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull.
Hands-on lab: LSH and IVF, measured​
You will build the shared dataset, compute the ground truth by brute force, then build LSH and an IVF index by hand and measure both against it. The last part repeats IVF in FAISS with real timings.
Full instructions: download the
Vector Databases labs ZIP. First build the
shared dataset by following labs/vector-databases/dataset/README.md, then open
labs/vector-databases/04-approximate-search and follow its README.
The output is the tables in this chapter. Recall numbers will be close to these with Ollama. With OpenAI's model, they will differ, because the vectors are different. The timings depend on your machine.
Checkpoint​
Brute force finds the paragraph each question was written about only 59% of the time. Why does a better index not fix that?
An index is tuned to agree with brute force, because recall is measured against brute force. It may occasionally land on the right paragraph by luck, but tuning only moves it toward 59%. The 59% comes from the embedding model: it does not always place a question closest to its own paragraph. To raise that number you need a better model, better chunking, or another retrieval method such as the keyword search in Chapter 8. A faster index will not help.
In the 8-bit LSH math, a close pair shares a bucket only 29% of the time. How does LSH still find most close pairs?
It builds many tables, each with its own random lines, and collects the query's bucket from every table. A pair that misses in one table often collides in another. The price is that typical pairs also collide more often, so the share scanned grows, and every extra table stores every ID again.
Why did IVF beat LSH at the same share of paragraphs scanned?
k-means places the cluster centers where the paragraphs actually are, so each cluster holds paragraphs that belong together. LSH's random lines ignore the data, so its buckets mix related and unrelated paragraphs. At about 7% scanned, IVF reached 0.86 recall and LSH 0.52.
Check Your Knowledge​
Click to start the quiz
What's next​
IVF jumps to a neighborhood and searches it. Chapter 5 tries a different strategy: start anywhere, and walk toward the answer one hop at a time across a graph of near neighbors. That idea, HNSW, grew out of social network research from the 1960s, and today it is the default index in most vector databases. You will build a small one by hand before tuning the real thing.