trendingzones
← Back to the Introduction level

AI & ML — INTERMEDIATE

BM25 Explained: The Formula Behind Keyword Search

“Keyword search matches literal words” undersells how much engineering goes into scoring which document actually matches best. BM25 — the algorithm behind most production keyword search — has real, well-defined math behind it.

The Quick Answer

BM25 scores a document against a query by combining two ideas for each query term: how rare that term is across the whole collection (inverse document frequency — rarer terms matter more), and how often it appears in this specific document, with two important adjustments — a saturation curve so a word repeated 20 times doesn’t score 20x higher than appearing once, and a length penalty so a term isn’t artificially boosted just because it sits inside a very short document. Semantic search has its own, different weak spots: it can genuinely struggle with rare technical terms and, more surprisingly, with negation — “hotels with pools” and “hotels without pools” can end up nearly indistinguishable in embedding space.

The BM25 Formula, Piece by Piece

For each query term, BM25 combines an inverse-document-frequency weight with a term-frequency component adjusted for document length:

import math

def bm25_score(query_terms, document, corpus, k1=1.5, b=0.75):
    doc_terms = document.lower().split()
    doc_len = len(doc_terms)
    avg_doc_len = sum(len(d.lower().split()) for d in corpus) / len(corpus)
    N = len(corpus)

    score = 0.0
    for term in query_terms:
        term = term.lower()
        n_t = sum(1 for d in corpus if term in d.lower().split())
        if n_t == 0:
            continue
        idf = math.log((N - n_t + 0.5) / (n_t + 0.5) + 1)
        f_t_d = doc_terms.count(term)
        numerator = f_t_d * (k1 + 1)
        denominator = f_t_d + k1 * (1 - b + b * (doc_len / avg_doc_len))
        score += idf * (numerator / denominator)
    return score

corpus = [
    "affordable travel deals for students on a budget",
    "luxury vacation packages with premium service",
    "budget backpacking tips for solo travelers on a budget",
    "business class flights and airport lounge access",
]
for i, doc in enumerate(corpus):
    print(f"Doc {i+1}: {bm25_score(['budget', 'travel'], doc, corpus):.4f}")

# Doc 1: 1.8419   <- has both "budget" and "travel"
# Doc 2: 0.0000   <- has neither
# Doc 3: 0.9304   <- has "budget" twice, but not "travel"
# Doc 4: 0.0000   <- has neither

Two design choices matter most here. k1controls term-frequency saturation — the score contribution from a repeated term grows quickly at first, then flattens out, which is why doubling how many times a word appears doesn’t double the score. bcontrols length normalization: the same single occurrence of a term is worth more in a short document than a long one, since it makes up a bigger share of that document’s content. A quick check confirms this directly — two documents each containing exactly one occurrence of “budget,” one short and one nine times longer:

corpus = [
    "budget travel",  # 2 words
    "budget travel means finding the best deals on flights "
    "hotels and food while exploring new places around the world",  # 19 words
]
for i, doc in enumerate(corpus):
    print(f"Doc {i+1} ({len(doc.split())} words): "
          f"{bm25_score(['budget'], doc, corpus):.4f}")

# Doc 1 (2 words): 0.2868
# Doc 2 (19 words): 0.1336

Same term, same single occurrence, nearly half the score once the document is nine times longer — length normalization doing exactly what it’s meant to do. Try the live calculator below against the original 4-document corpus:

Source: Robertson & Zaragoza, “The Probabilistic Relevance Framework: BM25 and Beyond”

Where Semantic Search Genuinely Struggles

Rare, technical terms — a specific part number, an uncommon acronym, a proper noun that barely appeared in an embedding model’s training data — often get poorly-calibrated embeddings, since the model has little signal to learn a precise representation for something it saw rarely. The result is exactly what showed up in the Introduction level’s activity: a specific identifier can get matched to a generically similar document instead of the one exact match that actually mattered.

More surprising is negation. “Hotels with pools” and “hotels without pools” describe opposite things, but share almost every word and the same overall topic — which is precisely the kind of similarity embeddings are trained to detect. The “not” relationship isn’t reliably encoded as its own clear direction in embedding space, so a semantic search for one can genuinely surface documents about the other. Research built specifically to test this found that even a strong model reached only 42% on a negation-consistency benchmark, against 81% human performance on the same questions.

Source: Ravichander et al., “CONDAQA: A Contrastive Reading Comprehension Dataset for Reasoning about Negation,” arXiv:2211.00295

Fun Fact

BM25’s two tunable parameters — k1 and b— are usually left at their standard defaults (1.5 and 0.75) in production systems, not because they’re mathematically special, but because decades of practical use have shown they work well across a very wide range of document collections without needing per-collection tuning.

Test Yourself

In BM25, what does term-frequency saturation mean?

In the worked BM25 example, why did a short document score higher than a longer one containing the same single occurrence of the query term?

What did the CONDAQA research find about negation and language understanding systems?

Ready to see how production systems combine both approaches — and the actual code that merges their rankings into one? Continue to the Advanced level →