Dense vs Sparse Retrieval (BM25 & DPR)

You run a docs search. Two users, two disasters.

User one types:

The perfect page exists. Its title:

Zero shared words except "azure". A word-matching engine returns nothing useful. It cannot paraphrase.

User two types:

A meaning-based engine returns a lovely essay about authentication in general. The one page that literally contains the code? Nowhere. It cannot match a rare exact string, because meaning-models smooth rare strings away.

So the question becomes

No — and this topic is about why: retrieval has two healthy philosophies with mirror-image blind spots, and the professional answer is to run both and merge.

• The word-matching philosophy: sparse retrieval, whose champion is BM25 (1994, still dominant).
• The meaning-matching philosophy: dense retrieval, whose modern ancestor is DPR (2020).

Every retriever answers the same question: "which document should this query get?" The two schools differ only in how they represent a document.

Sparse (BM25): a document becomes a giant list with one slot per vocabulary term (100k+ slots), and almost every slot is zero — hence "sparse."

code
Copy
vocab:    [azure, token, renew, key, cat, ...]
doc #77:  [  2,     5,    0,   3,   0, ...]   ← counts

Matching = overlapping nonzero slots. An inverted index — a lookup table from each term to the list of documents containing it (doc ids + frequencies) — makes this touch only documents that share query terms: microsecond lookups over billions of docs, with exact-match guarantees. Scoring is the BM25 formula (section 4).

Dense (DPR): a document becomes one short, fully filled-in vector — coordinates in meaning-space (topic 162: embeddings place similar meanings near each other).

doc #77 → [0.12, -0.44, 0.08, ..., 0.31]   (e.g. 768 numbers, none "special")

Matching = angle between query vector and document vector (cosine / dot product). No shared words required — but the coordinates come from a trained model, so training is mandatory and rare literal strings blur.

One contrast to memorize: in sparse, each slot means something fixed and human-checkable ("how many times does azure appear"). In dense, no single coordinate has a name — meaning is distributed across all of them. That is the whole trade: explicit and exact vs learned and generalizing.

Two librarians, one question.

code
Copy
SPARSE (book index)              DENSE (student who read the book)

term → pages                     "renew api key"   ⤷ points to
azure  → [77, 102, 9]                              "rotate token"
token  → [77, 41]                                 ← nearby ideas
renew  → [12]                                      on the map
key    → [77, 3, 55]

"only docs sharing WORDS"       "docs sharing MEANING, any words"

The index librarian is exact and literal: find every page containing the term, instantly, guaranteed — but two pages that say the same thing differently never connect.

The student librarian gets the gist — paraphrase, abbreviation, even another language — but draws a blank on the exact string "ERR_AUTH_8812": she remembers what things mean, and the code means nothing special.

Run both. Merge their lists. That is hybrid search, and the merging trick (RRF) is the punchline of this topic.

BM25 (Okapi BM25, Robertson & Zaragoza, 1994) scores a document per query term and sums. Each term's contribution bundles three intuitions:

• Term frequency with saturation. More occurrences of the word help — with diminishing returns. A knob k1 bends the curve: 1 occurrence → big gain, 2 → decent extra, 50 → barely more. A page repeating "azure" 50x is spam, not 50x better.
• Inverse document frequency (idf). Rare terms discriminate, common ones do not. "the" appears in nearly every doc → its weight ≈ 0. "FusionPro 3000" appears in three → it single-handedly identifies the right one.
• Length normalization. A knob b penalizes long docs so they cannot win merely by containing everything; a 2-for-200-word hit beats a 2-for-8000-word hit.

Tiny numeric feel for saturation (k1-style curve, roughly freq/(freq + 1) normalized): occurrences 1, 5, 50 give gains about 0.5, 0.83, 0.98 of the maximum. Five occurrences get you most of the way there; the next forty-five earn crumbs.

BM25's superpowers: exactness, speed, zero training, explainable scores (you can always say why: which terms, how often, in how rare a doc). Its weakness: vocabulary mismatch — "renew api key" never triggers the "rotate/access/token" postings, because there is no shared term to knock on the inverted index's door.

Dense Passage Retrieval (Karpukhin et al., 2020 — "DPR") swapped term matching for vector matching using a dual encoder: one BERT encodes the query to q, another (or the same) encodes each passage to p; relevance is simply dot(q, p).

Why "dual" is the design's whole genius: the two sides never interact until the dot product. That means every passage can be encoded offline, once, and indexed with ANN search (topic 163). At query time only one forward pass runs — the query encoder must keep up with live traffic; the corpus side is already done. That asymmetry is what makes dense retrieval deployable at scale.

Training is end-to-end with in-batch negatives: inside one batch of (question, gold-passage) pairs, each question treats the other questions' gold passages as negatives — free negatives, no labeling cost. Add hard negatives mined from BM25 results (the plausible-but-wrong pages), and DPR beat lexical baselines on open-domain QA by roughly 9–19 points of top-20 recall — and spawned the modern retriever lineage: ANCE, Contriever, E5/BGE/GTE, instruction-tuned retrievers.

Dense strengths: synonymy, paraphrase, cross-lingual matching. Weaknesses: needs labeled pairs to train, struggles on out-of-domain vocabulary (biomedical, legal, internal product names) unless adapted, and — critically for 2024–2026 RAG — misses rare exact identifiers that appear once in the corpus, because the model generalizes them away.

The two lists exist. Merge time. But BM25 scores (unbounded: 0 to ~25+) and cosine similarities (−1 to 1) live on different scales — averaging them numerically is nonsense, like adding a "7/10" gymnastics score to an Olympic diving score.

Reciprocal Rank Fusion (RRF) sidesteps calibration entirely: use only ranks. Each list contributes

score(doc) = Σ over lists 1/(k + rank)

with k ≈ 60 dampening the head so a first-place finish doesn't drown everything else. Worked numbers, one document appearing at BM25 rank 1 and dense rank 3 (counting from 1):

1/61 + 1/63 = 0.0164 + 0.0159 = 0.0323

versus a doc at dense rank 1, BM25 rank 6:

1/61 + 1/66 = 0.0164 + 0.0152 = 0.0316

The "good on both lists" doc edges ahead — consensus is rewarded, and no score ever mixes. RRF is unsupervised, robust, and the default fusion in Weaviate/Elastic/Microsoft Search for years.

Alternatives and extensions, in plain words:

• Convex combination: alpha·BM25 + (1−alpha)·cos after per-corpus score normalization; needs labeled data to tune alpha but can squeeze extra nDCG.
• Learned sparse (SPLADE): a trained network expands each token into weighted vocabulary terms ("renew" also adds "rotate" with weight 0.8) — keeps the inverted-index infrastructure with near-dense quality; the hybrid's third pillar in modern Elasticsearch/OpenSearch.
• Late interaction (ColBERT): sits between the extremes — full BERT per token, one vector per token stored per document, MaxSim scoring at query time ("best-match each of my words against yours"). Top dense-quality with exactness, at a storage premium.

def rrf(rank_lists: dict[str, list[str]], k: int = 60):
    """rank_lists: {source: [doc_id at rank 0, doc_id at rank 1, ...]}"""
    fused: dict[str, float] = {}
    for docs in rank_lists.values():
        for rank, doc in enumerate(docs):
            fused[doc] = fused.get(doc, 0.0) + 1.0 / (k + rank + 1)
    return sorted(fused, key=fused.get, reverse=True)

top = rrf({"bm25": lex_ids, "dense": vec_ids})[:50]

Carry it through: hybrid retrieval is a talent show with two judging panels.

• Judge BM25 scores with a ruler: "did the contestant literally hit the notes (the query terms)?" Mechanical, exact, fast, explainable — and tone-deaf to a jazz paraphrase of the same melody.
• Judge DPR listens to the feeling: "is this the same song in spirit?" Brilliant at covers and translations — but when the brief said "must hum the exact 7-note code ERR_AUTH_8812", the vibe-based judge fumbles it.
• Both submit a ranking, not a dollar amount. The showrunner (RRF) refuses to add scores across panels — different rulers, different units. Instead: "you were #1 on one sheet and #3 on the other; you win on agreement." The k ≈ 60 is the humility constant: nobody is unbeatable at rank 1.
• SPLADE is a judge who rewrites the brief first ("renew" → also check "rotate"), then scores literally. ColBERT is a judge who compares note by note instead of summarizing the whole performance into one impression — late interaction — richer, but she needs a bigger notebook (per-token vectors).

The lesson is the architecture: parallel panels, rank-only fusion, then send the shortlist to the meticulous final judge (the reranker, topic 167).

Decision shortcuts from production reality:

• Hybrid by default for RAG and enterprise search: +5–15 nDCG over either leg alone on typical benchmarks, and robust when one path degrades (bad embedder update, unexpected vocabulary).
• Pure BM25 for logs, catalogs, and compliance search — anywhere a literal-term guarantee is the product ("find every occurrence of this clause").
• Pure dense when the latency budget forbids two paths, or the corpus is conversational/short-text where paraphrase coverage matters more than literals.
• Never fuse by naive numeric averaging of raw scores, and never ship dense-only over a corpus dense in SKUs, part numbers, error codes, or coined names — those workloads are BM25's home turf and your recall will silently collapse there.

And instrument the two legs separately (recall@k per path): the most common "hybrid is broken" bug is one leg rotting while the fused average looks healthy.