Semantic and Hybrid Search: BM25, Dense Retrieval and Rank Fusion

Vector Search found the nearest vectors fast. Whether the nearest vectors are the right documents is a different question, and the oldest answer to it doesn’t use vectors at all: match the words. This post compares the two, keyword search and dense retrieval, and the simple trick that combines them, on a benchmark built from this blog’s own sections, in English and in Vietnamese.

Fusion adds only ranks, so the two scores never share a scale. It pays when the rankers are about as good as each other, as in English, and pulls the better one down when they are not, as in Vietnamese.

Data: the benchmark output in this post

At a glance

BM25 matches words: rare words count most, repeats saturate (a word’s weight goes from 1.51 at two occurrences to only 1.89 at four), long documents are discounted.
Dense retrieval matches meaning, but blurs exact tokens and silently truncates long text: the multilingual model cuts off 94% of the English sections at its 128 word pieces.
Reciprocal rank fusion combines rankings, not scores, so it needs no normalization; agreement wins: ranked 3rd by both rankers scores 0.0317, ahead of 1st and 8th at 0.0311.
On this blog’s English sections, fusion beat both rankers (MRR +0.051 over BM25). In Vietnamese, fusing BM25 with a much weaker dense model made it worse.
Diacritics matter: Vietnamese typed without them cut BM25’s first-place hits from 42% to 26%; a stripped index brought them back.

Open Table of contents

BM25: keyword search, derived
Dense retrieval
Fusing rankings
Measuring retrieval
A benchmark from this blog
Where this leads
Takeaways
References

BM25: keyword search, derived

A keyword score should reward a document for containing the query’s words, more for rare words than common ones, more for a word that appears several times, but not without limit, and less for a long document, which contains many words by chance. BM25, from the Okapi system (Robertson et al., 1994; surveyed by Robertson and Zaragoza, 2009), builds each of those in. For a query $q$ and document $d$ :

\text{BM25}(q, d) = \sum_{t \in q} \text{idf}(t) \cdot \frac{f(t, d)\,(k_1 + 1)}{f(t, d) + k_1 \big(1 - b + b \frac{|d|}{\text{avgdl}}\big)} .

Rarity: $\text{idf}(t) = \log\big(\frac{N - n_t + 0.5}{n_t + 0.5} + 1\big)$ , with $N$ documents and $n_t$ containing $t$ . A word in every document is worth almost nothing; a word in one is worth the most. (The $+1$ inside the logarithm is Lucene’s variant, which never goes negative; the classic form omits it.)
Repetition, saturated: as the count $f(t, d)$ grows, the fraction approaches $k_1 + 1$ and stops. The fifth “cache” adds much less than the first. $k_1$ between 1.2 (Lucene’s default) and 2 is typical; this post uses 1.5.
Length: the denominator grows with the document’s length relative to the average, by a fraction $b = 0.75$ , so a long document needs more matches for the same score.

Saturation and length together. Doubling a word’s count from 2 to 4 adds a quarter, not double; a shorter-than-average section gets a slightly higher weight for the same count.

The code in this post is four files: sections.py splits the blog’s posts into sections, bm25.py holds BM25, bm25_worked.py scores one query with it, and retrieval.py holds the two encoders and the benchmark. The run read a snapshot of the blog with 309 English sections; a rerun on the blog as committed finds 308, so its last digits can differ.

The BM25 class computes the formula above for every document at once:

class BM25:
    """Okapi BM25 (Robertson and Zaragoza, 2009), k1 = 1.5, b = 0.75."""
    def __init__(self, docs, k1=1.5, b=0.75):
        self.docs = [collections.Counter(tokens(d)) for d in docs]
        self.len = np.array([sum(d.values()) for d in self.docs]); self.avg = self.len.mean()
        df = collections.Counter(t for d in self.docs for t in d)
        n = len(docs)
        self.idf = {t: math.log((n - f + 0.5) / (f + 0.5) + 1) for t, f in df.items()}
        self.k1, self.b = k1, b
    def scores(self, query):
        s = np.zeros(len(self.docs))
        for t in set(tokens(query)):
            if t not in self.idf:
                continue
            tf = np.array([d[t] for d in self.docs])
            s += self.idf[t] * tf * (self.k1 + 1) / (tf + self.k1 * (1 - self.b + self.b * self.len / self.avg))
        return s

Full script: bm25.py

Worked for the query “paged KV cache” on the blog’s 309 English sections, term by term, against the section d that scores highest for it:

total = 0
for t in tokens(q):
    n = sum(1 for doc in bm.docs if t in doc)
    tf = d[t]
    norm = bm.k1 * (1 - bm.b + bm.b * bm.len[best] / bm.avg)
    part = bm.idf[t] * tf * (bm.k1 + 1) / (tf + norm)
    total += part
    print(f"  {t:6s} in {n:3d} of {len(docs)} sections: idf {bm.idf[t]:.2f}; appears {tf:2d} times here; "
          f"saturated tf {tf * (bm.k1 + 1) / (tf + norm):.2f}; contributes {part:.2f}")
print(f"  score {total:.2f}")

Full script: bm25_worked.py

query "paged KV cache"; best section: "Borrowing an idea from operating systems" (paged-attention-explained), 231 words, average 280
  paged  in  16 of 309 sections: idf 2.93; appears  2 times here; saturated tf 1.51; contributes 4.44
  kv     in  46 of 309 sections: idf 1.90; appears  4 times here; saturated tf 1.89; contributes 3.58
  cache  in  73 of 309 sections: idf 1.44; appears  2 times here; saturated tf 1.51; contributes 2.18
  score 10.20

“paged” is in 16 sections and “cache” in 73, so one occurrence of “paged” is worth twice one of “cache”. Doubling a count from 2 to 4 raises the saturated term only from 1.51 to 1.89: without saturation, “kv“‘s four occurrences would outweigh “paged“‘s two, and with it they don’t. And the section is shorter than average, which raises every term’s contribution slightly.

The rarest word contributes the most, though “kv” appears twice as often in the section.

Data: the output above

Dense retrieval

Dense retrieval embeds the query and every document (Embeddings and Contrastive Learning) and ranks by similarity (Vector Search). It matches meaning, not words: “speed up generation” can find a section about speculative decoding that never uses either word. Its weaknesses are the mirror image of BM25’s:

Exact tokens: identifiers, error codes, model names and numbers carry meaning the embedding blurs. BM25 matches them exactly.
Truncation: an encoder reads a limited number of tokens, 256 word pieces for the English MiniLM used here and 128 for the multilingual one, and silently drops the rest. On this blog, 72% of English sections are longer than the English model reads, and 94% than the multilingual one. A long document has to be split into passages, which is Building RAG’s chunking.
Language: a model trained on English embeds other languages poorly.

Fusing rankings

BM25 scores and cosine similarities live on unrelated scales, so adding them needs normalization that is fragile. Reciprocal rank fusion (RRF; Cormack et al., 2009) ignores the scores and uses only ranks: each document gets $\sum_i \frac{1}{k + \text{rank}_i}$ over the rankers, with $k = 60$ . Worked: a document ranked 1st by BM25 and 8th by the dense model scores $\frac{1}{61} + \frac{1}{68} = 0.0311$ ; one ranked 3rd by both scores $\frac{2}{63} = 0.0317$ , and wins. Agreement between rankers counts for more than one ranker’s enthusiasm.

Reciprocal rank fusion, worked. Only ranks enter the score, so BM25’s unbounded scores and cosine similarities never have to be put on one scale.

Measuring retrieval

With one relevant document per query, at rank $r$ (Measuring a Classifier Honestly measured classifiers; these measure rankings):

recall@k: the fraction of queries whose document is in the top $k$ ;
MRR, mean reciprocal rank: the average of $1/r$ , 1 for first place, 0.5 for second;
nDCG@10: $1 / \log_2(r + 1)$ if $r \le 10$ , else 0, averaged. With several relevant documents of different grades, it rewards putting the best ones first.

A benchmark from this blog

Each section heading of each post is a query, and the section under it is the one relevant document: a task with labels for free. Headings that occur in several posts are left out as ambiguous, and link targets are removed from the text, so a post’s own URL can’t give it away. The Vietnamese twins give the same task in Vietnamese, and, by pairing each Vietnamese heading with the English section of the same post whose heading it translates (mutual best matches by the multilingual model, 245 pairs), a cross-lingual one. Because that model chose the pairs, headings it couldn’t match are left out, which may flatter it on this task. Ties are counted against the right section, which slightly understates rank fusion, whose scores tie more often.

The fusion and the benchmark loop of retrieval.py. Around them, dense embeds whole sections, dense_passages scores a section by its best 80-word passage, evaluate prints the four measures, and paired the bootstrap interval of an MRR difference:

def rrf(*score_fns, k=60, weights=None):
    """Reciprocal rank fusion (Cormack et al., 2009): sum of 1 / (k + rank),
    optionally weighted per ranker."""
    weights = weights or [1] * len(score_fns)
    def f(q):
        total = 0
        for fn, wt in zip(score_fns, weights):
            order = np.argsort(-fn(q)); rank = np.empty_like(order); rank[order] = np.arange(1, len(order) + 1)
            total = total + wt / (k + rank)
        return total
    return f

for title, corpus, queries in (
        ("English headings -> English sections", en, [(s["heading"], i) for i, s in enumerate(en) if s in unique(en)]),
        ("Vietnamese headings -> Vietnamese sections", vi, [(s["heading"], i) for i, s in enumerate(vi) if s in unique(vi)]),
        ("Vietnamese headings typed without diacritics -> Vietnamese sections", vi,
         [(strip_marks(s["heading"]), i) for i, s in enumerate(vi) if s in unique(vi)]),
        ("Vietnamese headings -> English sections (cross-lingual, headings matched)", en, cross)):
    docs = [s["body"] for s in corpus]
    print(f"\n{title}: {len(queries)} queries, {len(docs)} sections")
    bm25 = BM25(docs).scores
    d_en, d_multi = dense("MiniLM (English)", docs), dense("MiniLM (multilingual)", docs)
    p_en, p_multi = dense_passages("MiniLM (English)", docs), dense_passages("MiniLM (multilingual)", docs)
    rr_bm25 = evaluate("BM25", bm25, queries)
    evaluate("dense, English, whole section", d_en, queries)
    evaluate("dense, English, best passage", p_en, queries)
    evaluate("dense, multilingual, whole section", d_multi, queries)
    evaluate("dense, multilingual, best passage", p_multi, queries)
    rr_en = evaluate("hybrid: BM25 + English passages", rrf(bm25, p_en), queries)
    rr_multi = evaluate("hybrid: BM25 + multilingual passages", rrf(bm25, p_multi), queries)
    paired("hybrid (English) minus BM25", rr_en, rr_bm25)
    paired("hybrid (multilingual) minus BM25", rr_multi, rr_bm25)
    evaluate("hybrid, multilingual weighted 0.25", rrf(bm25, p_multi, weights=[1, 0.25]), queries)

Full script: retrieval.py

English text, MiniLM (English): 72% of sections and 0% of passages cut off
English text, MiniLM (multilingual): 94% of sections and 48% of passages cut off
Vietnamese text, MiniLM (English): 89% of sections and 0% of passages cut off
Vietnamese text, MiniLM (multilingual): 96% of sections and 14% of passages cut off

English headings -> English sections: 297 queries, 309 sections
  BM25                                   recall@1   35%  recall@10   73%  MRR 0.480  nDCG@10 0.535
  dense, English, whole section          recall@1   31%  recall@10   72%  MRR 0.440  nDCG@10 0.499
  dense, English, best passage           recall@1   32%  recall@10   71%  MRR 0.458  nDCG@10 0.511
  dense, multilingual, whole section     recall@1   27%  recall@10   60%  MRR 0.374  nDCG@10 0.419
  dense, multilingual, best passage      recall@1   26%  recall@10   64%  MRR 0.380  nDCG@10 0.432
  hybrid: BM25 + English passages        recall@1   40%  recall@10   77%  MRR 0.530  nDCG@10 0.582
  hybrid: BM25 + multilingual passages   recall@1   35%  recall@10   75%  MRR 0.494  nDCG@10 0.550
  hybrid (English) minus BM25: MRR difference +0.051 [+0.016, +0.086]
  hybrid (multilingual) minus BM25: MRR difference +0.015 [-0.024, +0.052]
  hybrid, multilingual weighted 0.25     recall@1   38%  recall@10   74%  MRR 0.516  nDCG@10 0.566

Vietnamese headings -> Vietnamese sections: 257 queries, 270 sections
  BM25                                   recall@1   42%  recall@10   78%  MRR 0.539  nDCG@10 0.591
  dense, English, whole section          recall@1   17%  recall@10   44%  MRR 0.262  nDCG@10 0.294
  dense, English, best passage           recall@1   16%  recall@10   48%  MRR 0.256  nDCG@10 0.297
  dense, multilingual, whole section     recall@1   25%  recall@10   54%  MRR 0.352  nDCG@10 0.386
  dense, multilingual, best passage      recall@1   18%  recall@10   56%  MRR 0.308  nDCG@10 0.358
  hybrid: BM25 + English passages        recall@1   28%  recall@10   67%  MRR 0.414  nDCG@10 0.465
  hybrid: BM25 + multilingual passages   recall@1   35%  recall@10   75%  MRR 0.481  nDCG@10 0.540
  hybrid (English) minus BM25: MRR difference -0.125 [-0.168, -0.085]
  hybrid (multilingual) minus BM25: MRR difference -0.058 [-0.102, -0.015]
  hybrid, multilingual weighted 0.25     recall@1   40%  recall@10   77%  MRR 0.537  nDCG@10 0.588

Vietnamese headings typed without diacritics -> Vietnamese sections: 257 queries, 270 sections
  BM25                                   recall@1   26%  recall@10   58%  MRR 0.366  nDCG@10 0.411
  dense, English, whole section          recall@1   18%  recall@10   44%  MRR 0.260  nDCG@10 0.290
  dense, English, best passage           recall@1   16%  recall@10   49%  MRR 0.255  nDCG@10 0.299
  dense, multilingual, whole section     recall@1   14%  recall@10   34%  MRR 0.209  nDCG@10 0.230
  dense, multilingual, best passage      recall@1    9%  recall@10   30%  MRR 0.165  nDCG@10 0.184
  hybrid: BM25 + English passages        recall@1   20%  recall@10   59%  MRR 0.336  nDCG@10 0.388
  hybrid: BM25 + multilingual passages   recall@1   20%  recall@10   54%  MRR 0.314  nDCG@10 0.357
  hybrid (English) minus BM25: MRR difference -0.030 [-0.066, +0.007]
  hybrid (multilingual) minus BM25: MRR difference -0.053 [-0.089, -0.016]
  hybrid, multilingual weighted 0.25     recall@1   26%  recall@10   59%  MRR 0.368  nDCG@10 0.414

Vietnamese headings -> English sections (cross-lingual, headings matched): 245 queries, 309 sections
  BM25                                   recall@1   27%  recall@10   60%  MRR 0.376  nDCG@10 0.426
  dense, English, whole section          recall@1   13%  recall@10   40%  MRR 0.205  nDCG@10 0.238
  dense, English, best passage           recall@1   13%  recall@10   38%  MRR 0.217  nDCG@10 0.243
  dense, multilingual, whole section     recall@1   27%  recall@10   55%  MRR 0.363  nDCG@10 0.396
  dense, multilingual, best passage      recall@1   21%  recall@10   58%  MRR 0.331  nDCG@10 0.382
  hybrid: BM25 + English passages        recall@1   22%  recall@10   58%  MRR 0.339  nDCG@10 0.389
  hybrid: BM25 + multilingual passages   recall@1   26%  recall@10   62%  MRR 0.385  nDCG@10 0.434
  hybrid (English) minus BM25: MRR difference -0.037 [-0.077, +0.002]
  hybrid (multilingual) minus BM25: MRR difference +0.009 [-0.031, +0.049]
  hybrid, multilingual weighted 0.25     recall@1   31%  recall@10   62%  MRR 0.423  nDCG@10 0.465

Vietnamese headings typed without diacritics, against a diacritic-stripped index:
  BM25, stripped index                   recall@1   40%  recall@10   76%  MRR 0.524  nDCG@10 0.576

Four findings, each with its counterfactual in the table:

In English, fusion wins. BM25 and the English dense model are about even on their own (MRR 0.480 and 0.458 with passages); fused with RRF they find the right section first 40% of the time against 35%, and the MRR gain, $+0.051$ , has a 95% interval of $[+0.016, +0.086]$ over queries. The two make different mistakes, which is what fusion needs.
In Vietnamese, fusion with a weak ranker hurts. BM25 alone is far ahead (MRR 0.539); the dense models, scoring passages as they are fused, reach 0.308 (multilingual) and 0.256 (English). Fusing BM25 with either makes it worse: $-0.058$ $[-0.102, -0.015]$ with the multilingual model, $-0.125$ with the English one. RRF weighs every ranker equally, so a much weaker one drags the good one down. Weighting the multilingual ranker at a quarter removes the loss (0.537) but doesn’t turn it into a gain. (The weight was picked after seeing these results, on the same queries, so read the weighted rows as an illustration, not a tuned method.)
Diacritics matter, and the fix is cheap. Typed without diacritics, as Vietnamese often is, the same queries drop BM25 from 42% first-place hits to 26%: “điểm” and “diem” are different tokens. The multilingual model drops too, from 25% to 14%. The English model barely changes, because its tokenizer already strips accents: it reads both forms as the same unaccented text, which is also why it does better than chance on Vietnamese at all. Indexing a diacritic-stripped copy, and stripping the query, brings BM25 back to 40%.
Technical Vietnamese can be searched with English keywords. Vietnamese headings against English sections, a cross-lingual search, BM25 still puts the right section first 27% of the time, because Vietnamese technical writing keeps the English terms: “In-flight batching và paged KV cache” shares six words with its English section. The multilingual model also reaches 27%, by meaning rather than shared words, on pairs its own heading similarity chose, so that figure may be generous. Here the two are comparably good, and fusing them with the multilingual ranker weighted at a quarter is the best of all: 31% first-place hits, MRR 0.423 against BM25’s 0.376.

A one-line normalization on both sides recovers almost all of the loss.

Data: the output above

Only in English does fusion (filled dots) land right of BM25 (the square) by more than noise. In Vietnamese-to-Vietnamese search, BM25 is far ahead and fusing with a weaker ranker pulls it back. Dense scores here are best-passage.

Data: the output above

Scoring a section by its best 80-word passage instead of embedding the whole section changes little here, and not always for the better (Vietnamese, multilingual: MRR 0.352 whole, 0.308 by passage). For the multilingual model even an 80-word passage is often too long: 48% of the English passages are cut off at its 128 word pieces. The benchmark has its own bias: a heading’s words usually appear in its section, which favors keyword matching. Real users’ questions, phrased their own way, may favor dense retrieval more; that is a measurement to make on each system’s own queries, not a number to borrow from this one.

Where this leads

Reranking and Late Interaction re-ranks the top results with a model that reads query and document together.
Building RAG builds retrieval-augmented generation: chunking, and what each choice above does to the final answer.

Takeaways

BM25 scores rare words high, saturates repeated ones and corrects for length; dense retrieval matches meaning but blurs exact tokens, truncates long documents, and depends on the languages it was trained on.
Reciprocal rank fusion combines rankings without comparing scores. On this blog’s English sections it beat both rankers, MRR $+0.051$ over BM25 $[+0.016, +0.086]$ .
Fusing with a much weaker ranker hurts: on the Vietnamese sections, BM25 alone beat every equal-weight fusion, by up to 0.125 MRR; weighting the weak ranker down removed the loss.
Vietnamese typed without diacritics cut BM25’s first-place hits from 42% to 26%; a stripped copy of the index brought them back to 40%. Technical Vietnamese keeps English terms, which keyword search can use across languages.
Measure on the system’s own queries: which method wins depended here on the language, the typing and the ranker paired with it.

References

Start with Robertson and Zaragoza for BM25 and where each of its terms comes from, then Karpukhin et al. for dense retrieval and Cormack et al. for reciprocal rank fusion.

Robertson, Walker, Jones, Hancock-Beaulieu and Gatford, Okapi at TREC-3 (TREC, 1994): BM25 as first defined, in the Okapi system.
Robertson and Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond (Foundations and Trends in Information Retrieval, 2009): the survey that explains where each BM25 term comes from.
Karpukhin et al., Dense Passage Retrieval for Open-Domain Question Answering (EMNLP, 2020): dense retrieval with a trained bi-encoder.
Cormack, Clarke and Büttcher, Reciprocal Rank Fusion outperforms Condorcet and individual Rank Learning Methods (SIGIR, 2009): reciprocal rank fusion, the hybrid method measured here.
Reimers and Gurevych, Making Monolingual Sentence Embeddings Multilingual using Knowledge Distillation (EMNLP, 2020): the multilingual MiniLM used here.