Vectors, Distance and Similarity
The Cost of Asking What Is Nearby
Last timeWhere Intuition Stops Working
Comparing a query against every stored vector is exact and grows with the size of the collection. Every fast alternative gives up the guarantee of exactness in exchange, and the trade is measurable.
Everything up to here has been about comparing two vectors. Retrieval is about
comparing one against millions, which is a different problem, and the difference
is entirely about cost.
What the honest answer costs
Compare the query against every stored vector, keep the best few. This is exact,
simple, easy to get right, and the cost is linear in the size of the collection.
| vectors stored | multiplications per quer | cost relative to the fir | |
|---|---|---|---|
| ten thousand vectors | 10000 | 3000000 | 1 |
| a million | 1000000 | 300000000 | 100 |
| a hundred million | 100000000 | 30000000000 | 10000 |
Two things are worth saying before moving on. First, exhaustive search is
underrated: at ten thousand or a hundred thousand vectors it is fast, exactly
correct, trivial to maintain and has no parameters to tune. Second, it
parallelises perfectly, so a large machine moves the threshold further out than
people expect.
The lesson stops here
5 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents