Approximate Vector Search: Scaling Beyond Brute Force Cosine Similarity | Vedanshu
A Humanitarians AI fellow benchmarks brute-force cosine similarity from 1,000 to 100,000 vectors, then adds an inverted file index with cell centroids. The video measures what the shortcut costs in recall instead of assuming it is free.
After chunking documents and turning each chunk into an embedding, the next question is how to find the nearest few out of hundreds of thousands fast enough that nobody is left waiting. This video from a Humanitarians AI fellow covers that step, which is Chapter 5 of the series it belongs to. It benchmarks exact search, adds an approximate index, and measures what the shortcut costs.
The wall that exact search hits
Comparing a query against every stored vector is exactly correct. It never misses a true nearest neighbor. It is also the thing that does not scale, because every comparison still has to happen: double the collection and you double the work. A few hundred chunks is fine, but a whole company's documents is not.
Timing the naive version
The test uses synthetic embeddings at three collection sizes, 1,000, 10,000 and 100,000, with 20 queries each, returning the top 10 by comparing against every stored vector, with no index and no tricks. The search function is one dot product against every stored vector, keeping the top 10. The vectors are normalized, so the dot product is cosine similarity. The measured times were about a millisecond or less at 1,000 vectors, 1.16 milliseconds at 10,000, and 10.9 milliseconds at 100,000. Ten times the collection took very nearly ten times as long, a linear curve, and a real document store does not stop at 100,000 chunks.
How the inverted file index narrows the search
The revision groups the vectors into cells. A query is compared against the cell centroids first, and only the nearest few cells are scanned. The index uses two functions. Build puts every vector into a cell, with about the square root of the collection's size in cells, so each cell holds about the square root as well. Search ranks the centroids, takes the nearest few cells, and scans only what is inside them. Everything else is never examined.
The effect is large. With 100 times the data, exact search goes from 1,000 comparisons per query to 100,000, exactly 100 times the work. The index goes from 121 to 1,271 comparisons, about 10.5 times for 100 times the data.
The speed versus recall dial
The cost is recall, which the test reports against the exact answer so the shortcut is measured instead of assumed free. Comparing against a third of one percent of the collection returns a third of the true neighbors. About 1.3 percent gets 60 percent recall, 5 percent gets 88, and 10 percent gets 96. As the video puts it, approximate does not mean unpredictable: there is a dial, and you decide where to set it.
The video adds a caveat. The chapter itself covers HNSW, a graph index, while this demonstration builds an inverted file. The mechanism differs but the bargain is the same.
Key takeaways
- Exact search is always correct but its cost grows in step with the collection.
- Measured exact search time rose roughly tenfold when the collection grew tenfold, from 1,000 to 100,000 vectors.
- An index narrows the search space instead of scanning all of it.
- An inverted file index compares the query to cell centroids, then scans only the nearest cells.
- With 100 times the data, the index used about 10.5 times the comparisons, versus 100 times for exact search.
- Recall is the price: roughly 33 percent at a third of one percent compared, 96 percent at 10 percent compared.
- Always measure recall against the exact answer rather than assuming the shortcut is free.
Try it yourself
Ask Claude to take your brute-force search and add an approximate index. Then have it sweep the accuracy setting, plot recall against the share of the collection actually compared, and report the lowest setting that still answers your questions correctly. Also ask it to show the query where the approximate search first breaks, so the failure is shown instead of averaged away, and run it on your own data.
Chapters
Full transcript(auto-generated, with timestamps)
The exact search scalability wall
[0:00]Sawubona, I'm Vedanshi Dakshesh Patel. Chapter 4 left us with a pile of chunks and Chapter 3 turned each one into an embedding. Chapter 5 asks the question that makes them useful. A new question comes in, how do you find the nearest few out of hundreds of thousands fast enough that nobody is left waiting? Here is the problem before we write a line. Comparing a query against every
Benchmarking brute-force cosine similarity from 1k to 100k vectors
[0:20]Stored vector is exactly correct. It never misses a true nearest neighbor. It is also the thing that does not scale. Every comparison still has to happen, so double the collection and you double the work. A few hundred chunks is fine. A whole company's documents is not. The ask, build the naive version and time it honestly. Synthetic embeddings at three collection sizes, 1,000, 10,000, 100,000. 20 queries each top 10 comparing against every single stored
How cell centroids and inverted file indexes work
[0:46]Vector. No index, no tricks. I want to measure what exact search actually costs as the pile grows. Read the search function, one dot product against every stored vector, then keep the top 10. The vectors are normalized so that dot product is cosine similarity, the measure from Chapter 3. There's no cleverness in here and that is the point. This is the version that is exactly right and we are about to watch what being exactly right costs.
The speed vs. recall dial: Setting accuracy trade-offs
[1:10]Run it, 1,000 vectors, 800ths of a millisecond. 10,000, 1.16. 100,000, 10.9. 10 times the collection and very nearly 10 times the time. That is the linear curve measured on this machine and a real company's document store does not stop at 100,000 chunks. Now the revision and notice what I am asking for. Group the vectors into cells. Compare the query against the cell centroids first, then scan only the
Prompting Claude to find your approximate search breaking points
[1:35]Nearest few cells. And this is the part that matters, report recall against the exact answer. So we measure what the shortcut costs instead of assuming it is free. Two functions carry the whole idea. Build groups every vector into a cell about the square root of the collection so each cell holds about the square root, too. Search ranks the centroids, takes the nearest few cells, and scans only what is inside them. Everything else is never examined. That is the entire trick. Here's what that buys, 100 times the data. Exact search goes from 1,000 comparisons per query to 100,000, 100 times the work exactly as promised. The index goes from 121 to 1,271, 10 and 1/2 times for 100
Times the data. That is the chapter's figure measured. And here is the cost because it is not free. Compare against a third of 1% of the collection and you get a third of the true neighbors back. 1 and 1/3% gets you 60%. 5% gets you 88, 10% gets you 96. Approximate does not mean unpredictable. It means there is a dial and you decide where to set it. So, exact search is correct and does not scale because every comparison still has to happen. An index narrows the search space instead of scanning it and the cost stops tracking the collection. What you pay is recall and you pay exactly as much as you choose to. One honest caveat, the
Chapter walks through HNSW, a graph index. We built an inverted file. Different mechanism, same bargain. Your turn, paste this. Take my brute force search and add an approximate index, then sweep the accuracy setting and plot recall against the share of the collection actually compared. Tell me the lowest setting that still answers my questions correctly and show me the query where it first breaks. That last clause is the one that earns its keep. Anything will hand you a speed up. Asking for the query where it first breaks makes it show you the failure instead of averaging it away. Run it on your own data and find your own breaking point. Watch exact search hit a wall, Vidushi Daksh Patel.
More from Humanitarians AI Fellows
3:39RAG Chunking Strategies: Context vs Precision Trade-offs | Vedanshu
2:24Embeddings vs. Keyword Matching: Knowing When Closeness Trumps Exactness
2:26RAG Retrieval Architecture: 3 Default Settings That Will Fail | Vedanshu
2:50AI in Astronomy: Replacing Cosmological Simulations with Emulators
8:29The Cell Next Door: Reading Errors, Statistical Missteps, and Immunotherapy Links
2:39