Vibe Engines Learn
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
  1. Precompute N, avglen, and df per query term (how many docs contain it) before scoring.
  2. idf uses document frequency, not term counts: a term appearing 10 times in one doc still has df = 1.
  3. 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.
  4. Sum contributions per query term; a term with tf = 0 contributes 0 automatically.
CPython · WebAssembly

Explore the topic

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

RAG & Retrieval