FINDING NEEDLES · CHAPTER 07

Dense retrieval

A visitor types “ancient boat”. The label says “Bronze Age dugout canoe”. BM25 finds nothing. Two encoders and one dot product find the canoe.

~14 min read5 exhibit labelsTested Python

What you'll learn

  • How a bi-encoder turns search into a dot product
  • Why every document vector is computed once, before any query
  • Where dense beats BM25, and where BM25 beats dense
  • Why the negatives you train on decide what the model learns

Before you start

  • Sentence embeddings — bi-encoders and the in-batch loss
  • BM25 — the lexical score this chapter is compared against

The visitor and the curator use different words

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.

The query side and the document side

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

MANIM Dense retrieval: bi-encoder + contrastive training.

encode the query, encode the document, multiply them number by number, add it up. If both vectors have length 1, this is the cosine.

Offline, once

Every label
Document encoder
Stored vectorsone per label

Online, per query

“ancient boat”
Query encoder
Dot products, top-kno document is re-read

The expensive part, running a transformer over every document, happens before any visitor arrives. A query costs one encoder pass plus arithmetic.

Five labels, four numbers each

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.

#LabelVector“ancient boat” (2, 0, 0, 2)
1Bronze Age dugout canoe carved from a single oak trunk.(3, 0, 0, 2)0.981
2Roman oil lamp of red clay, found near the river ford.(1, 3, 0, 2)0.567
3Iron sword with a bronze hilt, from a warrior’s grave.(0, 0, 3, 2)0.392
4Paddle replica made for the 1990 gallery opening.(3, 0, 0, 0)0.707
5Accession 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.

One dot product per document adds up

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.

Train on the mistakes the model would make

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.

NegativeIts scoreLossPush on the query
Random: the sword0.3920.0030.003
Hard: the paddle replica0.7070.0630.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.

The museum search you can re-run

dense_museum.py“ancient boat” → canoe 0.981
"""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

Mistakes learners make

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.

What to remember

  • Dense retrieval scores a document by the dot product of two encoder outputs. Document vectors are computed once, offline.
  • On “ancient boat”, BM25 scores every label 0. Dense ranks the canoe first at 0.981, then the paddle at 0.707.
  • On “1887.4.12”, BM25 finds the comb at 1.694. Dense ranks it last at 0.471.
  • A hard negative like the paddle gives a loss of 0.063, against 0.003 for a random one. Train on the near misses.
  • A flat scan of 21 million 768-number vectors is about 64.5 GB per query. Chapter 8 makes that approximate and fast.

Check yourself

1. Why can the document vectors be computed before any query arrives?

In a bi-encoder the document encoder never sees the query. Its output depends only on the document.

2. Why does BM25 score the canoe 0 for “ancient boat”?

BM25 only counts query words that appear in the label. Neither “ancient” nor “boat” does.

3. Why is the paddle replica a better training negative than the sword?

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.

4. A visitor types a catalogue number. Which retriever do you trust?

BM25. An exact token match is what lexical search does best. Dense vectors blur strings that carry no meaning.

Go to the source

Keep going