FINDING NEEDLES · CHAPTER 07
A visitor types “ancient boat”. The label says “Bronze Age dugout canoe”. BM25 finds nothing. Two encoders and one dot product find the canoe.
A museum’s search box holds five exhibit labels. Curators write “dugout canoe”, “oil lamp of red clay”, “accession 1887.4.12”. Visitors type “ancient boat”. Not one word of that query is on the canoe’s label. Every lexical method from chapters 1 to 4 gives the canoe a score of 0.
This is vocabulary mismatch. Chapter 6 trained an encoder so that a question and its answer land close even when they share no words. Dense retrieval uses that encoder as the search engine.
Encode every document once and keep the vectors. When a query arrives, encode it with the query encoder and take a dot product with every stored vector. The highest scores are the results. Search by meaning becomes nearest-neighbour search in one shared space.
Dense Passage Retrieval (DPR) set the pattern. It uses two encoders: one for questions and one for passages. Questions are short and phrased as asks. Passages are long and phrased as statements. Separate weights let each side specialise. Many later models share one encoder and add a prefix such as “query:” instead. Either way, both sides must land in the same space.
vocab gap · bi-enc · contrast · recall
encode the query, encode the document, multiply them number by number, add it up. If both vectors have length 1, this is the cosine.
The expensive part, running a transformer over every document, happens before any visitor arrives. A query costs one encoder pass plus arithmetic.
Here the encoder is a table of hand-made 4-D vectors, standing in for a trained one. You can read the axes as water, home, war, and old. A real encoder’s axes have no names.
| # | Label | Vector | “ancient boat” (2, 0, 0, 2) |
|---|---|---|---|
| 1 | Bronze Age dugout canoe carved from a single oak trunk. | (3, 0, 0, 2) | 0.981 |
| 2 | Roman oil lamp of red clay, found near the river ford. | (1, 3, 0, 2) | 0.567 |
| 3 | Iron sword with a bronze hilt, from a warrior’s grave. | (0, 0, 3, 2) | 0.392 |
| 4 | Paddle replica made for the 1990 gallery opening. | (3, 0, 0, 0) | 0.707 |
| 5 | Accession 1887.4.12: carved bone comb. | (0, 1, 0, 1) | 0.500 |
Every vector is scaled to length 1 when it is stored, so each score is a cosine. The canoe wins at 0.981. The paddle replica comes second at 0.707: it is about boats, but it is not old. BM25 scores all five labels 0, because no label contains “ancient” or “boat”.
Interactive · The same query, two retrievers
Which labels come back first? Try a paraphrase, a plain match, and an accession number.
“clay lamp” is easy for both. BM25 scores the lamp 2.542 and nothing else. Dense ranks the lamp first at 0.930, with the comb close behind at 0.894. “1887.4.12” is the opposite of “ancient boat”: BM25 finds the comb at 1.694, and dense ranks it last.
Five labels need five dot products. DPR searched 21 million Wikipedia passages, each a 768-number vector. Stored as 4-byte floats, that is 21,000,000 × 768 × 4 = 64,512,000,000 bytes, about 64.5 GB, and every query would touch all of it.
The top-k step itself is cheap. A heap of size k keeps the best scores seen so far, just as the small engine in chapter 4 did with BM25. The cost is the scan. Chapter 8 replaces it with approximate nearest-neighbour search, which looks at a small fraction of the vectors and still finds most of the true top-k.
Dense encoders are trained with the contrastive loss from chapter 6. A query, its true document, and some negatives. Which negatives you pick matters as much as the loss.
Take “ancient boat”, with the canoe as the positive, at τ = 0.1. Compare two single negatives.
| Negative | Its score | Loss | Push on the query |
|---|---|---|---|
| Random: the sword | 0.392 | 0.003 | 0.003 |
| Hard: the paddle replica | 0.707 | 0.063 | 0.061 |
The sword is already far away, so the loss is almost 0 and the model learns almost nothing from it. The paddle is the one it might confuse with the canoe. It produces about twenty times the loss and twenty times the push. The push is the softmax probability on the negative, as in chapter 6.
A hard negative is a document that ranks high for the query but is not the answer. DPR mined them with BM25: the top BM25 passages that matched many question words but did not contain the answer. Later methods mine them with the dense model itself, so it keeps training on its own current mistakes. DPR reports beating BM25 by 9 to 19 points of top-20 passage accuracy on open-domain question answering.
"""Dense retrieval versus BM25 on five museum exhibit labels.
The "encoder" is a table of hand-made 4-D vectors, standing in for a
trained bi-encoder. Axes, for reading only: water, home, war, old.
"""
import heapq
import math
import re
LABELS = {
1: "Bronze Age dugout canoe carved from a single oak trunk.",
2: "Roman oil lamp of red clay, found near the river ford.",
3: "Iron sword with a bronze hilt, from a warrior's grave.",
4: "Paddle replica made for the 1990 gallery opening.",
5: "Accession 1887.4.12: carved bone comb.",
}
# What a trained encoder might return for each label (before normalising).
LABEL_VECS = {
1: [3, 0, 0, 2], # boat, very old
2: [1, 3, 0, 2], # household, old, near water
3: [0, 0, 3, 2], # weapon, old
4: [3, 0, 0, 0], # boat-shaped, but new
5: [0, 1, 0, 1], # small household object, old
}
# Query vectors from the same encoder. The id means nothing to it;
# it reads digits as "a date, so something old" and lands near the canoe.
QUERY_VECS = {
"ancient boat": [2, 0, 0, 2],
"clay lamp": [0, 3, 0, 1],
"1887.4.12": [2, 0, 1, 2],
}
# --- BM25, as in chapter 3 -------------------------------------------
def tokenize(text):
"""Lowercase words and numbers. "1887.4.12" stays one token."""
return re.findall(r"[a-z0-9]+(?:\.[a-z0-9]+)*", text.lower())
def bm25(query, docs=None, k1=1.2, b=0.75):
docs = LABELS if docs is None else docs
toks = {d: tokenize(t) for d, t in docs.items()}
avg_len = sum(len(t) for t in toks.values()) / len(toks)
n = len(docs)
scores = {d: 0.0 for d in docs}
for term in set(tokenize(query)):
df = sum(1 for t in toks.values() if term in t)
if df == 0:
continue
idf = math.log(1 + (n - df + 0.5) / (df + 0.5))
for d, t in toks.items():
tf = t.count(term)
if tf:
norm = 1 - b + b * len(t) / avg_len
scores[d] += idf * tf * (k1 + 1) / (tf + k1 * norm)
return scores
# --- Dense: normalise once, then one dot product per label -----------
def normalise(v):
size = math.sqrt(sum(x * x for x in v))
return [x / size for x in v]
def build_index(vecs=None):
"""Done once, offline. Unit length makes the dot product the cosine."""
vecs = LABEL_VECS if vecs is None else vecs
return {d: normalise(v) for d, v in vecs.items()}
def dense_scores(query, index):
q = normalise(QUERY_VECS[query])
return {d: sum(a * b for a, b in zip(q, v)) for d, v in index.items()}
def top_k(scores, k=3):
"""Highest scores first. A heap keeps this cheap when there are millions."""
return heapq.nlargest(k, scores.items(), key=lambda item: item[1])
# --- Training: why the negative you pick matters ---------------------
def contrastive_loss(pos, neg, tau=0.1):
"""-log softmax over [positive, negative], as in chapter 6."""
a, b = pos / tau, neg / tau
top = max(a, b)
return top + math.log(math.exp(a - top) + math.exp(b - top)) - a
def index_bytes(passages, dim, bytes_per_number=4):
"""Memory for a flat index of float32 vectors."""
return passages * dim * bytes_per_number
Expecting dense to find exact ids and rare names. “1887.4.12” means nothing to an encoder. Its vector lands near the canoe at 0.925, and the comb comes last at 0.471. BM25 finds the comb at once. Run both and fuse the lists: that is hybrid search, chapter 10.
Assuming a model trained on one domain works on yours. An encoder trained on web questions may rank museum labels, legal text, or part numbers worse than BM25. Test on your own queries before you switch.
Training only on random negatives. They are too easy. The loss goes to almost 0 and the model never learns to tell the canoe from the paddle.
Feeding in whole documents. An encoder reads a fixed number of tokens, often 512, and silently drops the rest. A long label becomes the vector of its first page. Split documents first; chunking is chapter 13.
In a bi-encoder the document encoder never sees the query. Its output depends only on the document.
BM25 only counts query words that appear in the label. Neither “ancient” nor “boat” does.
The model already scores the paddle close to the canoe (0.707). A negative the model already rejects, like the sword at 0.392, gives almost no loss and almost no gradient.
BM25. An exact token match is what lexical search does best. Dense vectors blur strings that carry no meaning.