BM25: Why Keyword Search Still Matters

Anchored in rag_pipeline.py → class BM25Index · config.py · BM25Index.search

Last lesson you saw the "fold" trap: the same word in two sentences dragged a Neovim folding question and a laundry folding question to a 0.43 cosine score. The embedding model did its best — it raised the score because of the shared word — but it also dampened it because the contexts diverge. What we want in many cases is something else entirely: a hard, unapologetic match on the word "fold" and then a downstream re-ranker to figure out the meaning.

That's what BM25 does. It's the workhorse of search engines for a reason that's older than transformers: exact word matches are still the strongest signal we have for many queries, and you don't need a GPU to compute them.

1. The mental model

BM25 ranks documents by how well they match the words in a query. It is a scoring function, not a model. There are no learned weights, no GPU, no 80 MB download. It's just an equation.

Three ideas compose it:

1. Term frequency (TF) — the more often a query word appears in a document, the more relevant that document is. But with diminishing returns: the difference between 1 occurrence and 5 is huge; between 50 and 54 is basically nothing.
2. Inverse document frequency (IDF) — words like "the" and "is" appear in every document and tell you nothing. Words like "neovim" or "polysemy" appear in few documents and are highly discriminative. Weight them more.
3. Length normalization — a 5,000-word blog post is more likely to contain any given word by accident than a 200-word note. Don't reward it as much.

BM25 combines these three with two tunable knobs (k1 and b). It's the formula Elasticsearch uses by default, and the formula your BM25Index implements. The Elastic blog has the canonical deep dive →

2. The formula, line by line

For a single query q and a single document D, BM25 is:

score(q, D) = Σ_{t ∈ q} IDF(t) · ( tf(t, D) · (k1 + 1) / ( tf(t, D) + k1 · (1 - b + b · |D|/avgdl ) ) + δ )

That's a wall of symbols. Break it into the three pieces:

The big fraction in the middle is the saturating TF. As tf grows, the numerator grows linearly but the denominator grows linearly plus a constant, so the whole thing asymptotes to (k1 + 1). That's the "diminishing returns" — the 51st occurrence contributes much less than the 1st.

Our code has one extra symbol: δ (delta). With δ = 0 this is plain BM25. With δ > 0 this is BM25+ — an extension that gives a small baseline score to documents that contain a query term at least once, even when the TF saturating function would otherwise return 0. It's a small change that noticeably helps long-doc-vs-short-query behavior. Zilliz's BM25 walkthrough has the BM25+ derivation.

3. What k1 and b actually control

These are the two knobs. The defaults (k1=1.5, b=0.75) are not magic — they were empirically tuned on early TREC datasets and have stuck. But you can and should reason about them.

Mental shortcuts:

• b = 0: ignore length entirely. The "raw TF" view.
• b = 1: full length normalization. A document needs proportionally more TF to outscore a shorter one.
• k1 = 0: TF doesn't matter at all. Pure IDF, every match scores the same.
• k1 → ∞: linear TF. The 50th occurrence counts as much as the 1st.

4. Now read your own code

Open rag_pipeline.py and find class BM25Index. The whole class is ~80 lines. Here are the four pieces worth understanding:

rag_pipeline.py · BM25Index.__init__

self.k1 = 1.5       # TF saturation knob
self.b = 0.75       # Length normalization knob
self.delta = 1.0    # BM25+ lower bound (vs plain BM25's 0.0)

The constructor takes three hyperparameters. The defaults are the standard "BM25+ with mild lower bound" recipe.

rag_pipeline.py · BM25Index._tokenize

def _tokenize(self, text: str) -> list[str]:
    return re.findall(r"\b[a-zA-Z][a-zA-Z0-9#]{1,50}\b", text.lower())

One line. Three things it does:

1. text.lower() — case folding. "Neovim" and "neovim" are the same token.
2. \b[a-zA-Z][a-zA-Z0-9#]{1,50}\b — word boundaries, must start with a letter, can include letters/digits/#, length 2–51. This drops punctuation, single-character tokens (so "I" and "a" don't pollute the index), and supports things like C# and .NET variants.
3. Returns a list, not a set. BM25 needs the actual TF count, not a unique set.

rag_pipeline.py · BM25Index.add_documents

def add_documents(self, doc_ids: list[str], texts: list[str]):
    self.doc_ids = doc_ids
    self.doc_texts = texts
    self._doc_tokens = [self._tokenize(t) for t in texts]
    self.doc_lengths = [len(toks) for toks in self._doc_tokens]
    self.total_docs = len(texts)
    self.avg_doc_length = sum(self.doc_lengths) / max(self.total_docs, 1)

    term_to_df: dict = {}
    for toks in self._doc_tokens:
        for token in set(toks):         # ← set, not list
            term_to_df[token] = term_to_df.get(token, 0) + 1
    self.doc_freqs = term_to_df
    self._built = True

This is the index build. It's just three pieces of state:

• self._doc_tokens — the tokenized documents (kept around for repeated TF lookups at query time).
• self.doc_lengths and self.avg_doc_length — for the length normalization in the formula.
• self.doc_freqs — the per-term document frequency (how many documents contain each term), not the per-term term frequency (how many times the term appears in each document). DF is used for IDF; TF is computed at query time.

Note set(toks) — we count each term once per document for DF purposes, even if it appears 100 times. The TF is what we count for the per-document term frequency.

rag_pipeline.py · BM25Index.search

for token in query_tokens:
    df = self.doc_freqs.get(token, 0)
    if df == 0:
        continue                        # ← term not in corpus, skip
    idf = np.log((n - df + 0.5) / (df + 0.5) + 1.0)
    for i in range(n):
        toks = self._doc_tokens[i]
        tf = toks.count(token)         # ← O(|doc|) per query
        if tf == 0:
            continue
        dl = self.doc_lengths[i]
        denom = tf + self.k1 * (1 - self.b + self.b * dl / self.avg_doc_length)
        if denom > 0:
            scores[i] += idf * (tf * (self.k1 + 1) / denom + self.delta)

This is the full formula. Notice:

• df == 0 → continue. If the term isn't in the corpus, it can't help. This is why BM25 silently returns empty for unknown terms.
• idf = log((N - df + 0.5) / (df + 0.5) + 1.0). The + 1.0 inside the log clamps IDF ≥ 0 — a term that appears in every document still gets a score of exactly 0, not negative.
• toks.count(token) is O(|doc|) per query token per doc — this is the algorithmic hot path. For 83 chunks × 100 tokens × 5 query tokens it's nothing. For 100k chunks, it starts to matter (more in the next lesson).
• The + self.delta at the end is BM25+ — the small floor that ensures any matching document gets a non-zero contribution from each query term.

5. Embeddings vs BM25 — when to use which

We've now seen both. Here's the working rubric from production RAG systems:

Production RAG systems don't pick one — they run both and fuse the rankings. That's the next lesson (RRF). OpenSearch's hybrid retrieval post explains why this is the consensus →

6. Hands-on exercise

"""Lesson 0003 — compare BM25 vs vector search on the real index."""
import json
from rag_pipeline import BM25Index, Embedder, VectorStore

# Load existing BM25 index (built during ingest)
print("Loading BM25 index...")
with open("data/lancedb/bm25_data.json", encoding="utf-8") as f:
    bm25 = BM25Index.from_json_dict(json.load(f))

print("Loading vector store + embedder...")
embedder = Embedder()
vstore = VectorStore("data/lancedb", embedder.dimension)

# Four queries that should differentiate the two methods
queries = [
    "how to configure neovim folding",       # paraphrase + technical term
    "polysemy",                              # single rare term
    "neovim",                                # exact brand match
    "How do I do a barrel roll in Neovim?",  # sentence-shaped, no overlap likely
]

print(f"\nBM25 corpus: {bm25.total_docs} docs, {len(bm25.doc_freqs)} unique terms")
print(f"Avg doc length: {bm25.avg_doc_length:.1f} tokens\n")

for q in queries:
    print(f"=== Query: {q!r} ===")
    bm25_results = bm25.search(q, top_k=3)
    print(f"  BM25 top 3:")
    for r in bm25_results:
        title = r["content"].split("\n")[0].lstrip("#").strip()[:60]
        print(f"    {r['score']:6.2f}  {r['doc_id']:25s}  {title}")

    qvec = embedder.embed_one(q)
    vec_results = vstore.vector_search(qvec, top_k=3)
    print(f"  Vector top 3 (cosine):")
    for r in vec_results:
        title = r["content"].split("\n")[0].lstrip("#").strip()[:60]
        cos = 1 - r["score"]
        print(f"    {cos:6.3f}  {r['doc_id']:25s}  {title}")
    print()

7. The threshold filter — when "below floor" means "no real match"

(Added in a later session, after we built the cosine-threshold feature in Lesson 0002 and applied the same pattern here. Read it as the production-noise-control coda to the BM25 chapter.)

The BM25_THRESHOLD in config.py (default 1.0) is a raw-score floor: a BM25 hit with score < 1.0 is dropped from the BM25 rank list before it reaches the RRF fusion. This is defense against two real failure modes:

• Single-token incidental matches. A chunk containing the word "set" in a JS method call .set({...}) gets a non-zero BM25 score for the query "how to set up neovim folding" — but the chunk isn't actually about Neovim. We saw this in the Lesson 0003 forensic exercise: the html2pdf chunk scored 7.49 almost entirely on the word "set" with idf=2.73 (df=5 in an 83-chunk corpus). A floor around 1.0 filters most of these.
• Stopword piles. A chunk that mentions 20 common words but none of the actual rare query terms can still score above 0. The floor cuts them off.

The rule

if score >= BM25_THRESHOLD:
    keep
else:
    drop   # can still surface via vector search if ranked there

BM25_THRESHOLD = 0.0 disables the filter (the backward-compat default if you don't tune the floor).

The adaptive override — "no good match" means "let vector do the work"

The hard floor has two failure modes worth distinguishing:

1. Truly zero lexical overlap. A nonsense token like "aardvark" or "xyzzy123" has df=0 in the corpus. BM25Index.search filters via if scores[idx] > 0 at the end of the search loop, so the BM25 list comes back as [] and the filter block in HybridSearch.search short-circuits on the if bm25_results guard. That's already a graceful degradation — RRF falls back to pure vector search, and the LLM gets vector hits with no BM25 contribution.

2. Weak but non-zero overlap. A query like "best pizza in naples italy" against our Neovim-folding corpus has weak overlap: common words like "in" and "best" appear in many chunks (high df, low IDF), and tokens like "pizza"/"naples"/"italy" have df=0 and don't contribute. The BM25 list comes back with ~8–10 weak hits, with the top hit scoring somewhere in the [1.0, 3.0] range at our default floor of 1.0. This is the case the override is built for:

rag_pipeline.py · HybridSearch.search (BM25 block)

if self.bm25_threshold > 0 and bm25_results:
    top_bm25 = float(bm25_results[0].get("score", 0))
    if top_bm25 < self.bm25_threshold:
        # No good lexical match anywhere — let vector carry the load.
        bm25_threshold_suppressed = True
    else:
        # apply the normal `>=` filter
        ...

When the top BM25 hit itself is below the floor, the filter is suppressed and every hit is kept. The bm25_threshold_suppressed flag in the timing dict records that the override fired, so operators can see "this query had no lexical match in the corpus" — and the LLM gets a richer context than it would from a silently wiped BM25 list.

For the full timing-dict schema and the keep/drop rule, see the BM25 cheat sheet's Threshold filter section.

Symmetric with the cosine threshold

See Lesson 0003 §7 for the production-noise-control coda — two failure modes (zero overlap vs weak overlap), the live sweep data behind the numbers, and tuning advice.

This is the exact same pattern as the cosine-threshold feature in HybridSearch.search (covered in Lesson 0002). The two thresholds are now symmetric:

Both rank lists are now noise-filtered symmetrically, and both fail gracefully when the corpus has no good match for the query. The two suppression flags tell operators exactly which side had nothing. Production RAG systems often log both and alert when both fire on the same query — that's the "this query is off-topic for the corpus" signal.

Tuning the floor

For this corpus (83 chunks of TILs and guides, all about Neovim/editor workflows), BM25_THRESHOLD = 1.0 is the right default. You can sweep the floor empirically using the playground_bm25_threshold_sweep.py pattern: run the same 4 canary queries at floor ∈ {0.0, 1.0, 3.0, 5.0, 10.0} and watch the dropped count + top-5 shift. The sweet spot is the lowest floor that filters single-token noise without dropping any chunk that contributes to the RRF top-5.

For a 100k+ chunk corpus where the number of noise hits matters more, 5.0 is a reasonable next step. Above that, you're trading recall for marginal noise reduction.

8. What you now know

• ✅ BM25 is a hand-rolled scoring function, not a model. No GPU, no training, no model file.
• ✅ It combines term frequency (with saturation), inverse document frequency, and length normalization.
• ✅ k1 controls how much term frequency matters. b controls how much document length matters.
• ✅ Our implementation is BM25+ (the delta term), which gives a small floor to any document containing a query term.
• ✅ The tokenization is case-folding + regex word boundary; no stemming, no stop-word list, no n-grams.
• ✅ The BM25Index build phase computes doc_freqs (the per-term document count). The query phase computes TF on the fly per doc.
• ✅ BM25 wins on exact technical terms, code identifiers, brand names. Embeddings win on paraphrases and semantic queries. That's why we run both.
• ✅ The BM25_THRESHOLD floor filters single-token incidental matches (like the .set({...}) false positive) and stopword piles. = 0.0 disables it.
• ✅ The adaptive override fires when the top BM25 hit is below the floor — keeps every hit, sets bm25_threshold_suppressed=True. Symmetric with the cosine-threshold suppression (Lesson 0002): both rank lists are noise-filtered the same way, and both fail gracefully when the corpus has no good match for the query.

9. What you don't know yet (next lessons)

• How to fuse two rankings (BM25 + vector) into a single result list (Lesson 0004: RRF).
• How to evaluate which is winning on real queries (Lesson on evaluation).
• How to swap our hand-rolled BM25 for a real inverted index (e.g. tantivy, Lucene) when we hit scale.

Citations & further reading

1. Elastic, Practical BM25 (Part 2): The BM25 Algorithm and Its Variables — the definitive explanation of k1 and b.
2. Zilliz, Mastering BM25 — implementation-level walkthrough with BM25+ derivation.
3. OpenSearch, Improving Document Retrieval with Sparse Semantic Encoders — why hybrid search is the production default.
4. Robertson & Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond — the academic foundation; dense but authoritative.