# Embeddings explained: why a search for car finds vehicle
URL: https://systemdesignsimple.com/why-search-for-car-finds-vehicle/
Published: 2026-11-05
Category: AI Systems
Publisher: System Design Simple (https://systemdesignsimple.com)
## Short answer
Without synonym expansion, BM25 scores a sentence that only says vehicle 0 for the query car. An embedding turns each word into numbers learned from the words it appears with. In our toy lab, BM25 found 2 of 14 relevant sentences and 0 of the 12 that never say car; a 304-number PPMI embedding put 8 relevant ones in its top 10, 6 without the word, but ranked a train car first.
## Key facts
- **Keyword search (lab):** Exact word car with BM25 returned 4 sentences: 2 of the 14 relevant (recall@10 14.3%, precision@10 20%) and 0 of the 12 car sentences that never say car
- **Substring search (lab):** Matching the letters c-a-r returned 10 sentences, 8 of them wrong: cardboard, caramel, cardigan, career, scar and others
- **Toy embedding (lab):** PPMI word vectors of 304 numbers from 124 training sentences we wrote. Top 10: 8 relevant, 6 of them never say car, 2 wrong
- **Word scores (lab):** cos(car, vehicle) 0.223 although the two words never share a training sentence; cos(car, cardboard) 0; cos(car, train) 0.424
- **The failure:** Rank 1 was 'The last train car was full of tired passengers' at cos 0.536: an averaged sentence vector cannot tell a train car from a road car
- **The catch:** 13 of 42 test sentences are exact copies of training sentences and 24 are near copies, so the lab shows the mechanism, not accuracy on new text
- **At scale:** 1 million vectors × 384 dimensions × 4 bytes = 1.536 GB for a flat index; approximate indexes like HNSW and IVF trade a little recall for far fewer comparisons
Embeddings explained: without synonym expansion, BM25 keyword search gives a sentence that says "vehicle" and never "car" exactly zero for the query car, and matching letters instead drags in cardboard and caramel. Embedding search compares vectors learned from the words each word appears with, which finds the vehicle sentences but brings its own mistakes, such as ranking a train car first. Interview version: "Users search your help center for car and miss every article that says vehicle. Design the search."
## Prerequisites {#prerequisites}
**An inverted index.** A keyword engine such as Lucene (inside Elasticsearch and OpenSearch) or PostgreSQL full-text search keeps, for every term, the list of documents that contain it. That makes keyword search fast and fixes its limit: a document without the query term is not in that term's list at all.
**Retrieval feeds AI answers.** In retrieval-augmented generation, a search step picks the chunks a model reads before it answers; miss the chunk that says "vehicle" and the model never sees it. The loop is covered in [how AI finds one line in 100 pages (AI 4)](/how-ai-finds-one-line-in-100-pages/); this article goes one level down, into how the retriever decides two texts are about the same thing.
**A dot product.** Multiply two equal-length lists of numbers position by position and add. If both vectors have length 1, that equals the cosine of the angle between them.
## Definitions {#definitions}
> Definition: **Token**: one unit of text after splitting, usually a lowercase word. The lab splits on every character that is not a letter a to z, so "car-pool" becomes the two tokens "car" and "pool".
> Definition: **BM25**: a keyword ranking function that scores a document by how often each query term appears in it, weighted by how rare the term is across the collection, with diminishing returns for repeats and a correction for document length.
> Definition: **Distributional hypothesis**: words that occur in similar contexts tend to have similar meanings. Every embedding method in this article is a way of measuring "similar contexts".
> Definition: **PPMI**: positive pointwise mutual information. For a word and a context word, the log of how much more often they occur together than independent chance predicts, with negative values set to 0.
> Definition: **Embedding**: a vector that represents a word, sentence or document so that texts with related meaning get vectors that point in similar directions.
> Definition: **Cosine similarity**: the dot product of two vectors divided by the product of their lengths; 0 to 1 when no value is negative, as in the lab.
> Definition: **ANN index**: an approximate nearest neighbour structure, such as HNSW or IVF, that finds most of the closest vectors without comparing the query with all of them.
> Definition: **Recall@k and precision@k**: relevant documents in the top k divided by all relevant documents, and divided by k (empty slots count as misses).
## Why does keyword search miss vehicle? {#how-it-works}
The lab (labs/ai-11/run.mjs) is a constructed toy demo on text we wrote, run on one Mac with Node 22, standard library only, deterministic. It has 42 test sentences labeled by hand before any search ran. 14 are about road cars: 2 say "car" and 12 never contain the letters c, a, r (vehicle, automobile, sedan, hatchback, "the engine would not start", "the gas station"). 8 are traps that contain the letters but are not about road cars: a train car, car-pool karaoke, cardboard, cardigan, career, caramel, a scar and one more. 20 are filler.
[Image: Comic panel: a search bar with car typed in, a thought bubble with a road car, sentence cards on a belt, and a counter showing 2 of 14 found | Exact keyword search for car: 2 of the 14 road-car sentences.]
### The BM25 formula
For a query with terms t and a document D, BM25 (Robertson and Zaragoza give the derivation) is:
```text
score(D) = Σ over query terms t of IDF(t) · tf(t,D) · (k1 + 1) / ( tf(t,D) + k1 · (1 - b + b · |D| / avgdl) )
IDF(t) = ln( 1 + (N - n(t) + 0.5) / (n(t) + 0.5) )
tf(t,D) = times t occurs in D |D| = tokens in D
N = documents in the collection avgdl = mean tokens per document
n(t) = documents that contain t k1 = 1.2, b = 0.75 (the lab's values)
```
IDF rewards rare terms. The tf fraction saturates: the first occurrence is worth far more than the fifth, and the fraction never exceeds k1 + 1. The b term penalizes long documents, which mention words by accident more often. The "1 +" inside the log keeps IDF positive; Lucene's BM25Similarity uses the same form.
### The lab's numbers
The lab counts a hit when a token equals "car" or "cars". 4 of the 42 test sentences contain one, so N = 42 and n = 4. The mean length, counting stop words, is 7.2857 tokens.
```text
IDF(car) = ln(1 + (42 - 4 + 0.5) / (4 + 0.5)) = ln(1 + 8.5556) = ln(9.5556) = 2.2571
"We washed the car on Sunday afternoon." |D| = 7, tf = 1
length factor = 1 - 0.75 + 0.75 · 7 / 7.2857 = 0.9706
score = 2.2571 · (1 · 2.2) / (1 + 1.2 · 0.9706) = 2.2571 · 2.2 / 2.1647 = 2.29
"The last train car was full of tired passengers." |D| = 9
length factor = 0.25 + 0.75 · 9 / 7.2857 = 1.1765
score = 2.2571 · 2.2 / (1 + 1.2 · 1.1765) = 2.2571 · 2.2 / 2.4118 = 2.06
"We sang car-pool karaoke songs at the office party." |D| = 10
score = 2.2571 · 2.2 / (1 + 1.2 · 1.2794) = 1.96
"The vehicle slid on the icy road." tf = 0
score = 2.2571 · 0 / (anything) = 0
```
Those match the lab's printed scores (2.29, 2.29, 2.06, 1.96). The road-car sentences rank first only because they are shorter; BM25 knows a token is there, not what it means. In the last line tf is 0, so no setting of k1 or b helps. Exact keyword search returned 4 sentences, 2 relevant: precision@10 20% (6 empty slots count as misses), recall@10 14.3% (2 of 14), and 0 of the 12 car sentences that never say car.
### Tokenization and the substring trap
A common patch is to drop the word boundary and match the letters. The lab's naive version is text.toLowerCase().includes('car'):
[Image: Panel: a stencil with the letters c, a, r catches cards for cardboard and caramel, with the counter 8 wrong | Matching letters instead of words: 10 results, 8 wrong.]
It returned 10 sentences, 8 wrong: the train car and karaoke again, plus cardboard, cardigan, career, caramel, scar and a name starting with the letters. Recall stayed at 2 of 14, because "vehicle" does not contain c-a-r either.
Real engines handle this in the analyzer chain. Stemming maps "cars" to "car" (the lab folds a trailing "s" when the singular is known). Edge n-gram analyzers match "car" inside "cardboard" on purpose, for autocomplete. Synonym filters expand "car" to "car OR vehicle OR automobile". A synonym list is the cheapest fix for a known vocabulary, but it never generalizes past the list, and embeddings cover the words nobody listed.
## Embeddings explained: how shared contexts become vectors {#ppmi}
The distributional hypothesis says "car" and "vehicle" are similar because they appear around the same words: engine, brakes, highway, insurance. The lab's buildModel() turns that into arithmetic in four steps, on 124 training sentences we wrote (separate from the test set, but overlapping it, see [evaluation](#evaluation)).
[Image: The word street: a vehicle word card on a roof with neighbours engine and brakes, and a strip of 304 shaded boxes, shapes only | A word's numbers come from its neighbours. The strip is a shape, not the real values.]
**Step 1: vocabulary.** Each sentence is lowercased, split on non-letters, stripped of stop words ("the", "on", "was" and about 120 more) and reduced to its distinct content words, with the plural fold. That leaves 304 distinct words, and that is where 304 comes from: one dimension per vocabulary word.
**Step 2: count co-occurrence.** A word's context is every other word in its sentence. For each ordered pair of different words (a, b) in a sentence, add 1 to C[a][b]; a sentence of k words adds k(k - 1), and the matrix is symmetric. The lab's totals:
```text
ordered pairs in all 124 sentences T = 1,960
"car" appears in 15 training sentences row(car) = 57 pairs
col(train) = 29, col(engine) = 36
C(car, train) = 4 (dining car, sleeper car, first car, train car)
C(car, engine) = 2
C(car, vehicle) = 0 (the two words never share a training sentence)
```
**Step 3: PPMI with context smoothing.** A raw count is misleading: frequent words co-occur with everything. PMI asks whether the pair co-occurs more than chance:
```text
PMI(w, c) = ln( P(w, c) / ( P(w) · Pα(c) ) )
P(w, c) = C(w, c) / T P(w) = row(w) / T
Pα(c) = col(c)^α / Σ col(x)^α with α = 0.75 (Σ col^0.75 = 1170.65 in the lab)
PPMI = max(0, PMI)
```
Worked with the lab's real counts:
```text
PPMI(car, train)
P(car, train) = 4 / 1960 = 0.002041
P(car) = 57 / 1960 = 0.02908
Pα(train) = 29^0.75 / 1170.65 = 12.497 / 1170.65 = 0.01068
ratio = 0.002041 / (0.02908 · 0.01068) = 6.57
PPMI = ln 6.57 = 1.883
PPMI(car, engine)
P(car, engine) = 2 / 1960 = 0.001020
Pα(engine) = 36^0.75 / 1170.65 = 14.697 / 1170.65 = 0.01255
ratio = 0.001020 / (0.02908 · 0.01255) = 2.79
PPMI = ln 2.79 = 1.028
same pair (car, train) without smoothing, α = 1:
ratio = (4 · 1960) / (57 · 29) = 7840 / 1653 = 4.74, PMI = 1.557
```
The 0.75 exponent is there because plain PMI overrates rare contexts: one coincidence gives a huge ratio. Raising context counts to 0.75 gives rare contexts more probability mass, shrinking their PMI, and frequent ones like "train" (29 pairs, against a mean of about 6.4) slightly less, raising its PMI from 1.557 to 1.883. Levy, Goldberg and Dagan showed this smoothing, borrowed from word2vec, is one of the choices that let count-based PPMI keep up with neural embeddings on word similarity.
**Step 4: normalize.** The car row has 52 positive entries of 304 (the whole matrix is about 98% zeros: 1,854 non-zeros in 92,416 cells). Dividing by its length, 11.322, turns the train entry into 1.883 / 11.322 = 0.166. Each word is now 304 numbers, most of them 0.
### Why car lands near vehicle without ever meeting it
C(car, vehicle) is 0, so each vector has a 0 in the other's position. They are still similar, because cosine compares whole rows: words are close when they share contexts (second-order similarity). The two rows overlap in 16 positions, and the dot product is the sum of 16 products:
```text
context car vehicle product
drove 0.148 0.197 0.0291
work 0.148 0.197 0.0291
electric ... ... 0.0201
charge, insurance, mechanic, new 0.0167 each
gas 0.0138 · night 0.0116 · highway 0.0106 · garage 0.0098 · road 0.0077
tire 0.0071 · engine 0.0065 · brake 0.0056 · needs 0.0052
sum 0.223
```
That is the lab's cos(car, vehicle) = 0.223. Cardboard's 16 contexts (box, tape, recycling...) share none with car's 52, so cos(car, cardboard) = 0. Other scores from the run: engine 0.205, garage 0.201, passengers 0.158, coffee 0.157, sedan 0.096, automobile 0.087, karaoke 0.020, caramel 0.009, and train 0.424, almost double vehicle. We put four train-car sentences in training on purpose, and a count-based model has one vector per spelling, so the rail and road senses of "car" blend into one row.
## How is a sentence scored, and why was a train car first? {#cosine}
The lab's embed() adds the vectors of a sentence's known words and normalizes the sum; the true average points the same way, so after normalizing they are the same vector. Unknown words are skipped (8 in the test set: burned, fall, pool, stayed, went, wish, working, year). The query vector is the car word vector. All vectors have length 1 and the dot product is linear, so a sentence S scores:
```text
cos(q, S) = Σ over words w in S of (q · w) / | Σ over words w in S of w |
```
[Image: Score panels: a sentence strip built as the average of word strips; vehicle scores 0.223 on a gauge, cardboard scores 0 | A sentence vector is the average of its word vectors; these example scores are below 1; identical nonzero vectors score 1.]
With that decomposition, the per-word dot products with the query (from the lab's vectors) explain the whole ranking:
```text
"The last train car was full of tired passengers." cos 0.536 (rank 1, wrong)
last 0.040 + train 0.424 + car 1.000 + full 0.135 + tired 0.135 + passengers 0.158 = 1.892
length of the summed vector = 1.892 / 0.536 = 3.53
"We washed the car on Sunday afternoon." cos 0.496 (rank 2, relevant)
washed 0.147 + car 1.000 + sunday 0.050 + afternoon 0.042 = 1.239, length 2.50
"The vehicle slid on the icy road." cos 0.172 (rank 10, relevant)
vehicle 0.223 + slid 0.032 + icy 0.035 + road 0.137 = 0.427, length 2.48
```
The train car sentence wins because it contains the query word (1.000) and its neighbours "train" and "passengers" also point toward car, since training put car in train contexts. The road-car sentence has the query word too, but washed, Sunday and afternoon (0.239 together) add norm with weaker query alignment. The model cannot read "train" as "rail sense": a sum has no word order and no interaction between words, so "train car", "car train" and any shuffle are the same vector.
[Image: Twist panel: the road car the user meant beside the number one result, a train car, with the lab line rank 1 cos=0.536 | The number one result was a train car: one vector per spelling, and an average with no word order.]
The top 10: train car (0.536), the two road-car sentences (0.496, 0.483), electric vehicle (0.330), car-pool karaoke (0.316, scored almost only on "car" because "pool" is unknown), then engine, mechanic, hatchback, automobile insurance and the icy road (0.224 down to 0.172). That is 8 relevant, 6 of them never say car, and 2 wrong: recall@10 57.1%, precision@10 80%. Rank 11 is a phone battery filler line (0.164), pulled up because "battery" and "charge" shared training sentences with car.
## What do real embedding models change? {#production}
Production embeddings keep the toy model's core idea and change almost everything else.
**Dense learned vectors.** word2vec (Mikolov et al., 2013) learns, say, 300 numbers per word by training a shallow network to predict words a few positions away, over billions of tokens. Levy and Goldberg later showed that skip-gram with negative sampling implicitly factorizes a shifted PMI matrix, so it measures the same statistic as the toy model, compressed to a dense fixed size. GloVe fits vectors to the log of co-occurrence counts, and truncated SVD of a PPMI matrix also gives dense vectors. Our 304 dimensions grow with the vocabulary; dense models do not.
**Context.** Sentence encoders such as Sentence-BERT (Reimers and Gurevych, 2019) run a transformer over the whole sentence, so "car" next to "train" gets a different token vector from "car" next to "washed". Many still finish with mean pooling, but over context-aware token vectors, so order and sense have already shaped what is averaged. 384 dimensions is a common small size.
**Training signal.** Sentence encoders are fine-tuned on matching pairs (questions and answers, paraphrases) with a contrastive loss that pulls matches together and pushes others apart. That training makes cosine useful for retrieval as well as word similarity.
**What does not change.** It is still one vector per text, compared by cosine. A term the model rarely saw (an internal product code) still gets a weak vector, so exact-match search stays. Scores are relative to the model, so thresholds must be tuned per model. And a new model changes every vector, so the whole index is re-embedded.
## How does vector search work at a million vectors? {#scale}
The lab compares the query with every sentence: 42 × 304 = 12,768 multiply-adds. That exact flat scan costs O(N · d) per query, gives perfect recall, and is right for small sets. Now assume 1 million chunks, 384 dimensions, float32:
```text
memory 1,000,000 × 384 × 4 bytes = 1,536,000,000 bytes = 1.536 GB (1.43 GiB)
pgvector each vector stores 4 · 384 + 8 = 1,544 bytes, about 1.544 GB of vectors
flat scan 1,000,000 × 384 = 384 million multiply-adds per query
time 1.536 GB read at an assumed 50 GB/s memory bandwidth = about 31 ms per query
100 queries/s would need 153.6 GB/s of reads -> exceeds the assumed machine's 50 GB/s
```
The scan is memory-bandwidth bound: every query reads every vector. Batching queries amortizes the reads (how GPU flat search in Faiss stays practical); past that, stop comparing against everything. It is the B-tree idea from SQL tuning and indexes (Part 30) in [the free course](/learn/): spend memory and build time so a query touches a small fraction of the data. The throughput arithmetic is the one in [latency vs throughput, measured](/ten-lanes-still-slow/).
### HNSW: a navigable graph
HNSW (Malkov and Yashunin) links every vector to about M near neighbours, in layers: sparse long-range links on top, every vector on layer 0. A query greedily walks toward the query vector on each layer, drops down, and at layer 0 keeps a candidate list of size efSearch, returning the best k.
```text
graph memory, M = 16 (pgvector's default m), 4-byte neighbour ids
layer 0 keeps 2M = 32 links per vector: 1,000,000 × 32 × 4 B = 128 MB
upper layers: about 1/16 of nodes, 16 links each ≈ 1,000,000 / 15 × 64 B ≈ 4.3 MB
total ≈ 132 MB on top of the 1.536 GB of vectors (assumed layout; real engines add overhead)
work per query, assumed 2,000 distance computations: 2,000 × 384 = 768,000 multiply-adds,
500 times fewer than the flat scan's 384 million
```
Higher M and efConstruction buy a better graph with memory and build time; higher efSearch buys recall with latency (pgvector defaults: m 16, ef_construction 64, hnsw.ef_search 40). Keeping the working set in RAM improves latency; disk reads can increase tail latency. Inserts are expensive. For pgvector, maintain dead tuples with VACUUM, measure recall and latency under update churn, and consider REINDEX when warranted ([pgvector vacuuming notes](https://github.com/pgvector/pgvector#vacuuming)).
### IVF: clusters, then a partial scan
IVF runs k-means to split the vectors into nlist lists by nearest centroid. A query compares itself with all centroids, then scans only the nprobe closest lists.
```text
nlist = 1,000, nprobe = 10, 1,000,000 vectors (assumed even clusters)
centroids 1,000 + vectors 10 × 1,000 = 11,000 comparisons
11,000 × 384 = 4.2 million multiply-adds, 1/91 of the flat scan
miss case: the true nearest neighbour sits just across a cluster boundary in list 11 -> not returned
```
IVF builds fast and adds little memory, but recall depends on nprobe and clusters drift as data changes, so it needs retraining. pgvector suggests lists = rows / 1000 up to 1 million rows, sqrt(rows) above, and probes starting at sqrt(lists) (the default of 1 is fast and low recall).
### Compression
Product quantization splits each vector into m sub-vectors and stores a 1-byte codebook index for each. With m = 48 sub-vectors of 8 dimensions, a vector shrinks from 1,536 bytes to 48: 1 million vectors from 1.536 GB to 48 MB of PQ code payload, 32 times smaller, with approximate distances. That is the payload only: Faiss IVFPQ also stores an 8-byte id per vector, so this example needs at least (48 + 8) × 1,000,000 = 56 MB, before centroids, codebooks and overhead ([Faiss index storage](https://github.com/facebookresearch/faiss/wiki/Faiss-indexes)). Keeping the original vectors for reranking is a separate 1.536 GB budget. int8 scalar quantization gives 384 MB. The usual pattern is to search the compressed index for a few hundred candidates, then re-score them with full vectors.
## Hybrid search: BM25 plus vectors {#hybrid}
Without synonym expansion, BM25 contributes zero for absent query terms. Keyword retrieval preserves exact-term signals when analysis retains those terms (a tokenizer that splits a product code, a stop-word filter or candidate truncation can still lose them), and [synonym expansion](https://www.elastic.co/docs/reference/text-analysis/analysis-synonym-graph-tokenfilter) can bridge a maintained vocabulary. Embeddings find synonyms and can rank related but wrong text first. Running both and fusing is the practical default. Reciprocal rank fusion (Cormack, Clarke and Buettcher, 2009) ignores raw scores, which live on different scales (2.29 versus 0.536), and uses only ranks:
```text
RRF(d) = Σ over rankings r of 1 / (k + rank_r(d)), k = 60, a document missing from a ranking adds 0
```
The constant k flattens the curve: rank 1 earns 1/61 = 0.0164 and rank 10 earns 1/70 = 0.0143, so agreement between rankings matters more than being first in one. With the lab's two rankings:
```text
id 13 washed the car: BM25 rank 1, cosine rank 2: 1/61 + 1/62 = 0.03252 -> fused 1
id 15 train car: BM25 rank 3, cosine rank 1: 1/63 + 1/61 = 0.03227 -> fused 2
id 14 car needs tires: BM25 rank 2, cosine rank 3: 1/62 + 1/63 = 0.03200 -> fused 3
id 16 car-pool: BM25 rank 4, cosine rank 5: 1/64 + 1/65 = 0.03101 -> fused 4
id 10 electric vehicle: cosine rank 4 only: 1/64 = 0.01563 -> fused 5
```
A road-car sentence moves to rank 1 and the vehicle sentences keep their places. The fused top 10 still holds 8 relevant and the same 2 wrong lines, because both retrievers like the train car. Fusion cannot remove an error both inputs share. A stage that reads the words together, such as a cross-encoder reranker over the top 50 candidates, a contextual encoder, or phrase handling ("train car" as one term), may reduce sense errors; validate it against domain-specific relevance labels. The query "car" carries no explicit road-vehicle intent, so no method can guarantee that reading: if intent remains ambiguous, use domain filters, additional query context or clarification.
## How do you measure search quality honestly? {#evaluation}
The lab reports the same cutoff for every method, which is the first rule: compare recall@10 with recall@10, not with a method's full result list.
| Method (lab) | Returned | Relevant in top 10 | Precision@10 | Recall@10 | Never-say-car found |
|---|---|---|---|---|---|
| Exact keyword, BM25 | 4 | 2 | 20% | 14.3% | 0 of 12 |
| Substring c-a-r | 10 | 2 | 20% | 14.3% | 0 of 12 |
| Toy PPMI embedding | 10 | 8 | 80% | 57.1% | 6 of 12 |
Keyword search's "precision of returned" is 50% only because it returned 4 results. As an extra metric, the embedding's recall in the top 14 is 78.6% (11 of 14). Rank-aware metrics differ again: the first relevant hit is rank 1 for BM25 and rank 2 for the embedding, a reciprocal rank of 1.0 versus 0.5.
[Image: The catch: 13 test sentences shown as exact copies of training sentences | 13 test sentences are exact copies of training sentences, so this shows how, not how well.]
The second rule is that test data must not leak into training. The lab measures its own leak: 13 of the 42 test sentences appear word for word in the training text, and 24 of 42 share at least 60% of their content words with one training sentence (Jaccard ≥ 0.6). We also wrote training contexts aimed at the exact synonyms and traps we test. So the lab demonstrates the mechanism, not accuracy on new text. In production the leak is quieter: a model tuned on support tickets and evaluated on tickets from the same week. Hold out by time or source, label relevance before looking at rankings, and use many queries; one query, like this lab's, is an anecdote.
## Worked example {#worked-example}
A help-center query for "car" misses articles containing only "vehicle". In the lab's terms:
```text
keyword (BM25): "vehicle" sentence tf = 0 -> score 0 found 0 of 12 never-say-car
substring "car": 10 results, 8 wrong recall unchanged, 2 of 14
toy embedding: cos(car, vehicle) = 0.223 via 16 shared contexts, C(car, vehicle) = 0
top 10: 8 relevant (6 never say car), 2 wrong (rank 1 train car 0.536,
rank 5 car-pool karaoke 0.316)
fused with RRF: road car moves to rank 1; same 8 relevant, same 2 wrong
production sizing: 1M chunks × 384 dims × 4 B = 1.536 GB flat; HNSW M=16 adds ≈ 132 MB (assumed layout)
```
## Code {#code}
First, the PPMI recipe from the lab on 8 sentences small enough to check by hand. It uses the same steps: distinct content words per sentence, ordered pair counts, α = 0.75, PPMI, length 1, cosine, and sentence vectors by summing.
```js
// ppmi-demo.mjs · node ppmi-demo.mjs (Node 18+, no packages)
// Same recipe as the lab, on 8 sentences: count shared sentences, PPMI, cosine.
const ALPHA = 0.75;
const STOP = new Set('a an the and of to in on at for with my was is it we our his her'.split(' '));
const TRAIN = [
'the car needs a new engine',
'the mechanic fixed the car brakes',
'the car slid on the icy road',
'the vehicle needs a new engine',
'the mechanic checked the vehicle brakes',
'the vehicle stopped on the road',
'pack the books in a cardboard box',
'put the cardboard box in recycling',
];
const docs = TRAIN.map((s) => [...new Set(s.split(' ').filter((w) => !STOP.has(w)))]);
const vocab = [...new Set(docs.flat())].sort();
const ix = new Map(vocab.map((w, i) => [w, i]));
const V = vocab.length;
// 1. Co-occurrence: +1 for every ordered pair of different words in one sentence.
const C = Array.from({ length: V }, () => new Array(V).fill(0));
for (const d of docs) for (const a of d) for (const b of d) if (a !== b) C[ix.get(a)][ix.get(b)]++;
// 2. PPMI with context smoothing: P_alpha(c) = count(c)^0.75 / sum of count^0.75.
const row = C.map((r) => r.reduce((s, x) => s + x, 0));
const total = row.reduce((s, x) => s + x, 0);
const colPow = vocab.map((_, j) => C.reduce((s, r) => s + r[j], 0) ** ALPHA);
const colPowSum = colPow.reduce((s, x) => s + x, 0);
const ppmi = (i, j) => {
if (C[i][j] === 0) return 0;
const pmi = Math.log((C[i][j] / total) / ((row[i] / total) * (colPow[j] / colPowSum)));
return Math.max(0, pmi);
};
const unit = (v) => { const n = Math.hypot(...v); return n ? v.map((x) => x / n) : v; };
const vec = Object.fromEntries(vocab.map((w, i) => [w, unit(vocab.map((_, j) => ppmi(i, j)))]));
const cos = (a, b) => a.reduce((s, x, k) => s + x * b[k], 0); // both have length 1
console.log('vocabulary', V, 'words, so each vector has', V, 'numbers; total pairs', total);
console.log('count(car, engine) =', C[ix.get('car')][ix.get('engine')],
' count(car, vehicle) =', C[ix.get('car')][ix.get('vehicle')]);
console.log('PPMI(car, engine) =', ppmi(ix.get('car'), ix.get('engine')).toFixed(3));
for (const w of ['vehicle', 'mechanic', 'cardboard', 'box'])
console.log(`cos(car, ${w}) = ${cos(vec.car, vec[w]).toFixed(3)}`);
// 3. Sentence vector = sum of word vectors, then length 1 (same direction as the average).
const embed = (s) => unit(vocab.map((_, j) => s.split(' ').filter((w) => ix.has(w))
.reduce((acc, w) => acc + vec[w][j], 0)));
for (const s of ['vehicle stuck on road', 'cardboard box for books', 'road vehicle stuck on'])
console.log(`cos("car", "${s}") = ${cos(vec.car, embed(s)).toFixed(3)}`);
```
What to observe: 19 vocabulary words, so 19 numbers per vector, and 90 ordered pairs. count(car, vehicle) is 0, yet cos(car, vehicle) prints 0.404, above mechanic at 0.376, because the two share needs, new, engine, mechanic, brakes and road. Cardboard and box print 0.000. The first and third sentence lines both print 0.527, because reordering the words leaves the vector unchanged. "stuck" is unknown and skipped. Scores run higher than the lab's because 8 tidy sentences share more context than 124 varied ones.
Second, reciprocal rank fusion over the lab's two real rankings (sentence ids from results.json):
```python
# rrf.py · python3 rrf.py (no packages)
# Reciprocal rank fusion of the lab's two rankings for "car" (sentence ids).
bm25 = [13, 14, 15, 16] # exact word, BM25 order
dense = [15, 13, 14, 10, 16, 5, 7, 6, 2, 1, 30, 3, 8, 9] # toy embedding, cosine order
relevant = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
def rrf(rankings, k=60):
score = {}
for ranking in rankings:
for rank, doc in enumerate(ranking, start=1):
score[doc] = score.get(doc, 0.0) + 1.0 / (k + rank)
return sorted(score.items(), key=lambda kv: (-kv[1], kv[0]))
fused = rrf([bm25, dense])
for pos, (doc, s) in enumerate(fused[:10], start=1):
print(f"{pos:2} id {doc:2} rrf {s:.5f} {'REL' if doc in relevant else 'wrong'}")
top10 = [d for d, _ in fused[:10]]
print("relevant in fused top 10:", sum(d in relevant for d in top10))
```
What to observe: id 13 (washed the car) is first at 0.03252 and id 15 (train car) second at 0.03227; the four sentences in both lists take the first four places, and "relevant in fused top 10: 8" shows fusion kept the embedding's recall without removing the shared error. Lower k to 1 and single-list rank differences start to dominate.
The full lab is labs/ai-11/run.mjs: node run.mjs prints every score and metric quoted here, deterministically; the intermediate counts (T, row sums, PPMI values) were read from the same model's internals. Its 2D PCA map keeps only 12% of the variance, so treat that picture as a sketch.
## Failure modes and edge cases {#failure-modes}
- **Shared spelling, different sense.** One vector per spelling blends senses, as the train car shows. Detect it by grouping bad results by query term; a contextual encoder, a reranker or phrase terms may reduce it, and ambiguous queries need filters, more context or clarification.
- **Topical but wrong.** Related text ranks high (the phone battery line at rank 11), and negations ("the car is not for sale") land near their positives. Detect with labeled hard negatives; fix with a reranker, not a raw cosine threshold.
- **Unknown words.** The toy model skipped 8 test words; "car-pool" scored almost only on "car". Subword tokenizers soften this, but rare domain terms still get weak vectors, so keep BM25 for codes and names.
- **Model mixing.** Vectors from two model versions are not comparable. Store the model id with each vector and build the re-embedded index beside the old one before switching reads.
- **Filtering after ANN.** Filters apply to a fixed candidate set: pgvector's README notes that with hnsw.ef_search 40 and a filter matching 10% of rows, about 4 rows survive. Use iterative scans or per-tenant partial indexes.
- **Silent recall loss.** An ANN index always returns something. Measure its recall against an exact scan on sample queries after every rebuild, and alert on drops.
- **Chunking.** Averaging dilutes every word: the road-car sentences scored only 0.496 with three unrelated words. Chunks of a few hundred tokens usually beat whole pages, and must fit the model's budget anyway ([the context window article](/my-chat-forgot-my-name/)).
## Trade-offs {#trade-offs}
| Option | Good for | Costs you | Use when |
|---|---|---|---|
| BM25 keyword | Exact terms, codes, names; explainable scores | No synonyms (0 of 12 in the lab) | Always, as one leg |
| Synonym lists | Known vocabulary gaps | Manual upkeep; never generalizes | Small fixed domains |
| Substring / n-grams | Autocomplete, typos | Precision (8 of 10 wrong in the lab) | Prefix search only |
| Count-based PPMI | Teaching, transparency | Dimension = vocabulary; one sense per spelling | Labs and tiny corpora |
| Dense sentence embeddings | Paraphrase and synonym recall | Model hosting, re-embedding, topical false hits | Natural-language queries |
| Flat vector scan | Perfect recall | O(N · d): 384 million multiply-adds at 1M × 384 | N × d × 4 B × QPS fits memory bandwidth (100,000 × 384 at 1,000 QPS = 153.6 GB/s); benchmark |
| HNSW | Low latency, high recall | Memory (≈ 132 MB of links at 1M, M = 16), slow inserts | Read-heavy, fits in RAM |
| IVF (+ PQ) | Large sets, low memory (48 MB PQ code payload; at least 56 MB with 8-byte ids) | Recall depends on nprobe; retraining | Hundreds of millions of vectors |
| Hybrid + RRF | Coverage of both failure types | Two indexes, two queries | Default for production search |
| Cross-encoder rerank | Word order and sense | A model call per candidate | Top 20 to 100 only |
## Common mistakes {#common-mistakes}
- **Mistake:** Replacing keyword search with vectors. **Instead:** Run both and fuse; embeddings miss exact identifiers and rank related but wrong text high.
- **Mistake:** Fixing synonyms with substring matching. **Instead:** It added 8 wrong results and no vehicle sentence; use synonyms or embeddings.
- **Mistake:** A fixed cosine threshold like 0.5 as "relevant". **Instead:** In the lab a relevant sentence scored 0.172 and a wrong one 0.536. Rank, fuse, rerank, and tune cut-offs on labeled data.
- **Mistake:** Comparing precision of what one method returned with another's precision@10. **Instead:** Same cutoff for all: keyword search's 50% becomes 20% at 10.
- **Mistake:** Evaluating on text the model was trained on. **Instead:** Measure overlap like the lab (13 exact, 24 near copies of 42) and hold out by time or source.
- **Mistake:** Trusting ANN results unmeasured. **Instead:** Compare with an exact scan on sample queries after every rebuild.
## In an interview {#in-an-interview}
**Clarify:** what is searched, how many documents, keyword or question queries, latency target, update rate. **Assumptions:** 1 million chunks, 384 dimensions, p95 under 100 ms. **Structure:** chunk, embed, index into BM25 and HNSW; query both; fuse with RRF; rerank the top 50. **Deep dive:** tf = 0 for synonyms; shared contexts; HNSW memory (1.536 GB plus about 132 MB of links) and efSearch versus recall. **Trade-offs:** HNSW versus IVF with PQ; reranker cost; re-embedding on model change. **Wrap up:** labeled queries with recall@10 and precision@10, ANN recall against exact scan, clicks online.
> **A 60-second answer**BM25 only scores terms that occur in the document, so an article that says vehicle scores exactly zero for car, and substring tricks add noise like cardboard. I would add embedding search: each chunk becomes a vector learned from the contexts words appear in, so car and vehicle land close and cosine similarity finds them. Embeddings make their own errors, such as a train car ranking first, so I keep BM25, query both in parallel, fuse with reciprocal rank fusion, and rerank the top 50 with a cross-encoder. A million 384-dimension chunks take 1.536 GB, so I use HNSW rather than a flat scan, tune efSearch, and check its recall against an exact scan. Quality is tracked on a held-out labeled query set with recall@10 and precision@10.
## Practice {#practice}
**Q (Beginner): Why does BM25 score "The vehicle slid on the icy road" 0 for car?**
The term never occurs, so tf = 0 and the numerator is 0, whatever k1, b or IDF are.
**Q (Beginner): Why did substring matching make results worse?**
"car" is inside cardboard, caramel, cardigan, career and scar: 10 results, 8 wrong, and still no vehicle sentence.
**Q (Intermediate): C(car, vehicle) is 0. How can cos(car, vehicle) be 0.223?**
Cosine compares whole PPMI rows. The words share 16 contexts (drove, work, insurance, mechanic, engine...), and those 16 products sum to 0.223: second-order similarity.
**Q (Intermediate): Compute PPMI(car, train) from T = 1,960, row(car) = 57, C = 4, Pα(train) = 0.01068.**
4/1960 = 0.002041; P(car) = 0.02908; ratio = 0.002041 / (0.02908 · 0.01068) = 6.57; ln 6.57 = 1.883.
**Q (Intermediate): What does α = 0.75 context smoothing do?**
It gives rare contexts more probability mass, lowering their inflated PMI. For the frequent context train, PMI rose from 1.557 to 1.883.
**Q (Advanced): Why does "The last train car..." outrank "We washed the car..."?**
Both contain car (1.0), but train (0.424) and passengers (0.158) also point toward car, while washed, Sunday and afternoon add norm with weaker query alignment. A sum has no word order.
**Q (Advanced): Memory for 1 million 384-dimension float32 vectors, and with 48-byte PQ codes?**
1,000,000 × 384 × 4 = 1.536 GB; PQ code payload 48 MB, 32 times smaller; at least 56 MB for Faiss IVFPQ with 8-byte ids, before centroids and codebooks.
**Q (Advanced): RRF kept the train car in the fused top 10. Why, and what fixes it?**
Both rankings place it high (ranks 3 and 1) and fusion rewards agreement. A cross-encoder reranker, a contextual encoder or a phrase term may reduce sense errors; validate on domain relevance labels. "car" alone does not state road-vehicle intent, so use domain filters, more context or clarification when it stays ambiguous.
## Cheat sheet {#cheat-sheet}
| Term or formula | Meaning |
|---|---|
| BM25 | Σ IDF · tf(k1+1) / (tf + k1(1 - b + b·\|D\|/avgdl)); k1 1.2, b 0.75 |
| IDF | ln(1 + (N - n + 0.5)/(n + 0.5)); 2.2571 for car in the lab |
| tf = 0 | Score 0: why keyword search cannot find synonyms |
| Distributional hypothesis | Words in similar contexts have similar meanings |
| PMI | ln(P(w,c) / (P(w)·Pα(c))) |
| PPMI | max(0, PMI); one row per word = a count-based embedding |
| Pα(c) | col(c)^0.75 / Σ col^0.75: context smoothing |
| Cosine | a·b / (\|a\|\|b\|); dot product for length-1 vectors |
| Sentence vector (lab) | Sum of word vectors, normalized; no word order |
| Flat scan | O(N·d); 1M × 384 = 384 million multiply-adds |
| Vector memory | N × d × 4 bytes; 1M × 384 = 1.536 GB |
| HNSW | Layered neighbour graph; M, efConstruction, efSearch |
| IVF | k-means lists; scan nprobe of nlist |
| PQ | m sub-vectors × 1 byte; 48 bytes per vector |
| RRF | Σ 1/(60 + rank) over rankings |
| Recall@k / precision@k | Relevant found / all relevant; relevant found / k |
## Further reading {#further-reading}
- **Robertson and Zaragoza (2009)**: the derivation of BM25 and what k1 and b control.
- **Levy, Goldberg and Dagan (2015)**: PPMI versus SVD versus neural embeddings, and why choices like α = 0.75 matter more than the model family.
- **Mikolov et al. (2013)**: the word2vec architectures.
- **Reimers and Gurevych (2019)**: sentence embeddings that cosine can compare directly.
- **Malkov and Yashunin**: the HNSW search and insertion algorithms, where M and ef come from.
- **Faiss**: flat, IVF, PQ and HNSW indexes and how to choose. For PostgreSQL, the [pgvector README](https://github.com/pgvector/pgvector).
- **Cormack, Clarke and Buettcher (2009)**: reciprocal rank fusion and k = 60.
Related in this series: once retrieval returns the right chunk, checking that a cited quote is really in the source (AI 10) covers the next failure, and [performance vs scalability, measured](/fast-alone-slow-crowded/) has the load arithmetic for sizing a search tier.
This article describes general patterns and our own toy lab on sentences we wrote. The numbers come from one small count-based model on constructed data and are not a benchmark of any embedding model, search engine or product.
## Frequently asked questions
**Why does a search for car find sentences that say vehicle?**
Because embedding search compares meaning vectors, not spellings. Car and vehicle appear with the same neighbouring words (engine, brakes, highway, insurance), so their vectors point in similar directions. In our toy lab they scored 0.223 cosine although they never shared a sentence.
**Why can't BM25 find synonyms?**
Without synonym expansion, BM25 contributes zero for query terms absent from the document: if it never contains car, tf is 0, so that term adds 0. A synonym filter can bridge a maintained vocabulary. In our lab, with no synonyms, BM25 found 0 of the 12 car sentences that use other words.
**What is PPMI?**
Positive pointwise mutual information: the log of how much more often two words appear together than chance predicts, with negative values set to 0. A word's row of PPMI values is a simple count-based embedding.
**Are embeddings better than keyword search?**
They catch different things. Embeddings find synonyms and paraphrases but can rank related but wrong text high; keyword retrieval preserves exact-term signals for codes, names and rare terms when analysis retains those terms. Most production systems run both and fuse the rankings.
**Do I need a vector database?**
Do the arithmetic first. 100,000 × 384 × 4 bytes is 153.6 MB: about 3.07 ms of reads per unbatched query at an assumed 50 GB/s, and 1,000 queries/s needs 153.6 GB/s. If that fits your hardware, a flat scan works; otherwise use an approximate index such as HNSW or IVF (pgvector, Faiss, search engines). Benchmark at your target concurrency, filters and recall.
**Are the lab's numbers a benchmark?**
No. It is a constructed toy demo on 42 sentences we wrote, with a model trained on 124 sentences we also wrote, and many test sentences overlap the training text. It shows how the mechanism works, not how any real model scores.
## Sources
- [Robertson and Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond (2009)](https://doi.org/10.1561/1500000019)
- [Levy, Goldberg and Dagan, Improving Distributional Similarity with Lessons Learned from Word Embeddings, TACL 2015](https://aclanthology.org/Q15-1016/)
- [Mikolov et al., Efficient Estimation of Word Representations in Vector Space (2013)](https://arxiv.org/abs/1301.3781)
- [Reimers and Gurevych, Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks (2019)](https://arxiv.org/abs/1908.10084)
- [Malkov and Yashunin, Efficient and robust approximate nearest neighbor search using HNSW graphs](https://arxiv.org/abs/1603.09320)
- [Faiss: a library for efficient similarity search and clustering of dense vectors](https://faiss.ai/)
- [Cormack, Clarke and Buettcher, Reciprocal Rank Fusion outperforms Condorcet and individual rank learning methods, SIGIR 2009](https://doi.org/10.1145/1571941.1572114)