BM25 Cheat Sheet

Quick reference. Pair with lessons/0003-bm25-keyword-search-still-matters.html.

The formula

For a single query q and document D:

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

Three pieces:

• tf(t, D) — how many times term t appears in D
• IDF(t) = log((N - df(t) + 0.5) / (df(t) + 0.5) + 1) — how rare t is in the corpus
• |D|/avgdl — length penalty

Our implementation: BM25+

The four key code blocks

Constructor

self.k1 = 1.5
self.b = 0.75
self.delta = 1.0
self._built = False

Tokenizer

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

Case-folded, word-boundary, letter-prefixed, length 2–51, includes #.

Index build

self._doc_tokens = [self._tokenize(t) for t in texts]
self.doc_lengths = [len(toks) for toks in self._doc_tokens]
self.avg_doc_length = sum(self.doc_lengths) / max(self.total_docs, 1)

# Per-document frequency: each term counted ONCE per doc, even if repeated
for toks in self._doc_tokens:
    for token in set(toks):
        term_to_df[token] = term_to_df.get(token, 0) + 1
self.doc_freqs = term_to_df

Search

idf = np.log((n - df + 0.5) / (df + 0.5) + 1.0)   # ≥ 0 always
denom = tf + self.k1 * (1 - self.b + self.b * dl / self.avg_doc_length)
score = idf * (tf * (self.k1 + 1) / denom + self.delta)

TF saturation intuition

For k1=1.5, the per-term score contribution as TF grows:

Notice BM25+ has no true asymptote — the +δ adds a constant. That's the floor.

Embeddings vs BM25

Threshold filter (production noise control)

BM25_THRESHOLD = 1.0 (in config.py) — the floor on BM25 raw score below which a hit is dropped from the BM25 rank list before it reaches RRF. Defense against two real failure modes:

• Single-token incidental matches. A chunk containing the word "set" (e.g. .set({...}) in a JS code block) gets a non-zero BM25 score for the query "how to set up neovim folding" — but the chunk isn't actually about Neovim. 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 (backward-compat default).

Adaptive override — the "no good match" case

The hard floor has its own failure mode: an adversarial query with zero corpus overlap would have its BM25 list silently wiped clean. The adaptive override detects this and keeps every hit so vector search + RRF can still do useful work. Mirrors the cosine-threshold logic in HybridSearch.search exactly:

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   # every BM25 hit kept as-is
    else:
        # apply the normal `>=` filter
        ...

When the top BM25 hit itself is below the floor, the filter is suppressed and every hit is kept. bm25_threshold_suppressed in the timing dict records that the override fired.

Timing dict fields

Symmetric with the cosine threshold

The cosine and BM25 thresholds are now symmetric: both peek at the top hit, suppress the filter if it's below the floor, otherwise apply the filter normally. Both rank lists are noise-filtered symmetrically, and both fail gracefully when the corpus has no good match for the query. The two suppression flags (vec_threshold_suppressed / bm25_threshold_suppressed) tell operators exactly which side had nothing.

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.

Production decisions

Complexity

For 100k docs × 200 tokens: ~20M ints in memory. Fine. For 10M docs, switch to a real inverted index (tantivy, Lucene) where cost is O(|q| · matches), not O(|q| · N · L).

Where to look in the codebase

Glossary