CODING CHALLENGE · N°18

BM25 Scoring

Medium AI EngineeringRetrievalSearch

The keyword-ranking function every fancy retriever still has to beat. Score documents for a query with BM25 — term frequency that saturates, rare terms weighted up, long documents normalized down. The lexical half of every hybrid search pipeline.

The problem

Given a query (list of tokens) and docs (list of documents, each a list of tokens), return a list of BM25 scores, one per document. Use k1 = 1.5, b = 0.75. For each query term: idf = ln(1 + (N - df + 0.5) / (df + 0.5)) where N is the number of documents and df the number containing the term; the term contribution to a document is idf · tf·(k1+1) / (tf + k1·(1 - b + b·len/avglen)) where tf is the term count in the document, len its length, and avglen the mean document length. A document score is the sum over query terms.

EXAMPLE 1

Input query = ['cat'], docs = [['the','cat','sat'], ['the','dog','ran']]

Output [0.49…, 0.0]

only the cat document scores

EXAMPLE 2

Input query = ['cat'], docs with tf=2 vs tf=1

Output higher score for tf=2 — but not 2× (saturation)

k1 caps repeat rewards

EXAMPLE 3

Input same tf, shorter vs longer doc

Output shorter doc scores higher

b normalizes length

CONSTRAINTS

k1 = 1.5, b = 0.75 exactly.
A query term absent from every document contributes 0 to every score (its idf still computes, tf = 0 zeroes it).
avglen = total tokens across docs ÷ number of docs.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement bm25_scores(query, docs) → one score per document, using the standard BM25 formula with k1 = 1.5, b = 0.75 and the +1-smoothed idf.

HINTS — 4 IDEAS

Precompute N, avglen, and df per query term (how many docs contain it) before scoring.
idf uses document frequency, not term counts: a term appearing 10 times in one doc still has df = 1.
The tf part is tf·(k1+1) / (tf + k1·(1 − b + b·len/avglen)) — note tf appears in numerator AND denominator: that is the saturation.
Sum contributions per query term; a term with tf = 0 contributes 0 automatically.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Score a document by summing, over each query term, three factors: IDF (rarer terms weigh more), a saturating term-frequency (more occurrences help with diminishing returns, controlled by k1), and a length normalization (longer documents are discounted, controlled by b against the average document length). Precompute IDF and document lengths, then each query is a cheap sum.

Complexity

Time O(q × matching docs) per query after an O(1) IDF/length lookup; index build is O(total tokens).

Common mistakes

Using raw term frequency without saturation, so a term repeated many times in a long document dominates unfairly.
Dropping the document-length normalization — long documents then score artificially high.
Mishandling IDF edge cases (a term in every document, or in none).

Where this shows up

BM25 is the default lexical ranking function in production search (Lucene, Elasticsearch, OpenSearch) and the lexical half of hybrid retrieval. It nails the exact identifiers, names, SKUs, and error codes that embeddings blur, which is why serious RAG systems run BM25 and vector search together and fuse the results.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

RAG & Retrieval