Embeddings and vector search
Compute what a brute-force vector search costs at 100k and 10M vectors, and decide when an approximate index earns the recall it gives up.
On this page
An embedding model turns a piece of text into a list of numbers — a vector of, say, 1,024 floats — arranged so that texts with similar meaning land close together. "How do I get my money back?" and "refund policy" share almost no words, and a keyword index misses the pair; their embeddings sit near each other, and a nearest-neighbour search finds them. Vector search is the mechanism that made retrieval work on paraphrase, and the arithmetic of it is simpler than the vendors around it suggest.
What an embedding is
The model is trained on pairs: a question and the passage that answers it, two sentences that say the same thing, a title and its body. It learns to place each text at a point in a space of 1,024 dimensions so that the pairs end up close and unrelated texts end up far apart. The dimension is a property of the model, not of your data: 384, 768, 1,024 and 1,536 are all common, and a larger vector costs proportionally more to store and compare without being proportionally better.
Two rules follow from how the space is made. Index and query must use the same embedding model — a vector from one model is meaningless in another's space, so changing the model means re-embedding the whole corpus. And the model embeds what it is shown: a chunk that is only "within 14 days of delivery" lands near other durations, which is why the heading path is prepended before embedding, not after.
Cosine similarity, and why normalising once makes it a dot product
Closeness is measured by the angle between two vectors: cosine similarity is 1 for the same direction, 0 for unrelated, and in practice the useful range for text is a narrow band near the top. Cosine is the dot product divided by the two lengths. Divide every stored vector by its own length at index time, and the query vector by its length once per query, and the similarity is just the dot product: 1,024 multiplications and 1,024 additions per comparison — 1,024 multiply-adds. That is the unit the rest of the lesson is counted in.
Brute force over 100k vectors
The naive search compares the query with every vector and keeps the best k. For 100,000 chunks of 1,024 dimensions that is 100,000 × 1,024 ≈ 100M multiply-adds per query. A single core with vector instructions does on the order of a few billion of those a second, so the arithmetic is around 30 ms. The memory tells the same story: 100,000 × 1,024 × 4 bytes is 400 MB of float32, which streams through one core at on the order of 10 GB/s — about 40 ms. Halve it with float16. Either way: tens of milliseconds, in a numerical library, on one machine, with no index at all. Keeping the best five of 100,000 scores is a bounded heap, O(n log k), not a sort.
The mistake is common enough to name. A team with 8,000 chunks — 8,000 × 1,024 ≈ 8M multiply-adds and 33 MB, about 3 ms by the same arithmetic — deploys a managed vector database cluster. Each query now pays a network round trip inside the datacenter (0.5 ms on the latency ladder) to save at most those 3 ms, beside a model call measured in seconds, and the team owns a service, its upgrades and its failure modes. A matrix multiply in the process that already holds the chunks would have done it. Put the retriever behind an interface — search(query, k) returning chunk ids and scores — so the brute-force version can be replaced by an index later without touching the prompt code.
When an approximate index earns its recall loss
Scale the same arithmetic. One million vectors: 1G multiply-adds and 4 GB per query — about 0.4 s, still one machine, but now a visible slice of a latency budget. Ten million: 10G multiply-adds and 40 GB — seconds per query, and the vectors no longer fit comfortably in one process's memory. Brute force is linear in both dimensions, and past about a million vectors it stops being the answer.
An approximate nearest-neighbour index — a graph of neighbours walked greedily, or vectors clustered so only a few clusters are scanned — answers a query over 10M vectors in a few milliseconds by looking at a fraction of them. The price is in the name: it returns the true top k most of the time, not always. Measured recall at 10 against brute force is typically 95–99%, tunable towards 99% by scanning more at the cost of latency. That loss is only acceptable if you measure it: run 1,000 queries through both brute force and the index, count how many of the exact top 10 the index returned, and treat the number as the index's own eval, re-run whenever its parameters change.
Two more costs arrive with the index. Metadata filters interact badly with it: filtering after the approximate search can leave fewer than k results when the filter is selective, and filtering before it can force a scan. And the index is built, not written — adding 10,000 vectors a day means either a rebuild or an index that supports inserts, with the recall measured again afterwards. Quantising vectors to 8-bit integers cuts memory by 4× at a small recall cost and is often the cheaper first step: a 10M-vector corpus at 10 GB fits one machine again, and the index can wait.
The rule: under a million vectors, brute force on the machine that holds the chunks; measure the query latency and move on. Over a million, or over a few hundred queries a second, build an index and measure its recall before trusting it.
In an interview
What is being tested is whether you can count the work. Say the multiply-adds: "100k vectors of 1,024 dimensions is about 100M multiply-adds, tens of milliseconds on one core, so no index". Say what an index trades: "milliseconds for a recall loss I would measure at 95–99%". Say when the answer changes: "past a million vectors, or past a few hundred queries a second". Then say the two rules of the space: same model for index and query; re-embed everything when the model changes.
The mistake that loses points is proposing an approximate index without stating the corpus size — and, on the other side, forgetting that an index returns approximate results and never measuring the recall it costs.
Check yourself
1. 250,000 chunks, 768 dimensions, 20 queries a second. Index or brute force?
250,000 × 768 ≈ 192M multiply-adds a query, roughly 60 ms on one core, and 250,000 × 768 × 4 bytes ≈ 770 MB. At 20 queries a second that is 20 × 60 ms = 1.2 core-seconds per second — more than one core, so either two cores or an index. Brute force on a small pool of workers holds, with float16 halving the memory; an index becomes the cheaper option if queries pass about 50 a second.
2. You switch embedding models for a 3-point gain on the retrieval eval. What does the switch cost?
Every chunk is re-embedded — the old vectors are in a different space — so the whole corpus goes through the new model once, and the index is rebuilt. For 170 chunks that is a minute; for 10M chunks it is 10M × 400 tokens = 4G tokens through the embedding endpoint and a rebuild measured in hours, scheduled with the old index serving until the new one's recall is checked.
3. The approximate index reports recall at 10 of 0.93 against brute force. Ship it?
Only with the retrieval eval beside it. A 7% loss of true neighbours matters if the missing neighbour was the one chunk with the answer, and the labelled 100-question set says how often that happens: if end-to-end recall at 5 drops from 0.90 to 0.88 the index is within noise; if it drops to 0.80, raise the scan parameter until recall at 10 is 0.98 and pay the milliseconds.