What is BM25? Keyword search explained from scratch
You search your company’s docs for error 4042 refund. Semantic search — the fancy
AI kind — returns pages that are vaguely about refunds. But the one page that literally
contains error 4042 sits at rank seven. A 30-year-old algorithm called BM25 would
have put it first, instantly, without a GPU.
That algorithm powered web search for decades and still ships inside Elasticsearch, Lucene, and every serious vector database today. By the end of this post you will understand every term in the BM25 formula — because we build it up one idea at a time, and after each idea you’ll run a few lines of code and read the real numbers it produces.
We’ll cover it in four parts:
- Setup — what “search” means, turning text into tokens, our tiny example corpus
- The four ideas — term frequency, rarity, saturation, length normalization
- BM25 assembled — compose the ideas into the formula, run it, read real rankings
- BM25 in the real world — sparse vectors, production libraries, when it wins and fails
The one metaphor to hold onto: BM25 is a detective
Everything below is a detective scoring evidence against a case file. Four rules:
- Count the clues. More mentions of the suspect’s name → stronger file.
- Rare clues matter more. “Owns a car” — half the city does, worthless. “Owns a 1967 Corvette” — now you have something.
- The tenth repetition of the same clue adds little. Once you get the point, you get the point.
- A clue in a one-page note counts more than the same clue buried in a 300-page report. Focus beats bulk.
Those four rules are BM25. Keep them in mind — each one becomes a piece of math below.
What does “search” actually mean?
You have a pile of text — call each piece a document. A user types a query like
dog park. Search has one job:
Rank the documents so the ones most relevant to the query come first.
Here’s the whole pipeline we’re about to build:
query: "dog park"
│ tokenize
▼
['dog', 'park']
│ score against every document (this is BM25's job)
▼
doc 0: 0.000 doc 1: 1.486 doc 2: 0.813 doc 3: 0.851 doc 4: 0.000
│ sort by score
▼
1. (1.486) "A dog chased the cat around the yard"
2. (0.851) "The park has a pond where ducks swim every morning"
3. (0.813) "Dogs are loyal and love to play fetch in the park"
The only mystery is the middle step: how do we score “relevant”? BM25 is one very good, very durable answer. We’ll reach it in four small steps — each step fixes a flaw in the one before it.
First, turn text into tokens
A computer only understands numbers — it has no concept of a word. So the first move in any search system is to chop text into tokens: units that can be counted and compared.
BM25 works at the level of whole words, so our tokenizer is the simplest possible one — lowercase and split on spaces:
def tokenize(text):
return text.lower().split()
tokenize("A dog chased the cat")
# -> ['a', 'dog', 'chased', 'the', 'cat']
From here on, a “document” is just a list of these word-tokens.
Aside — LLMs tokenize differently. Modern LLMs and embedding models split text into subword pieces (
"unbelievable"→un / belie / vable), each mapped to an integer id. You can watch it live at OpenAI’s interactive tokenizer: https://platform.openai.com/tokenizer. None of that machinery is needed for BM25 — whole words are enough — but the word “token” means the same thing in both worlds: the unit of text a system counts.
Already a subtle lesson:
"Dogs"and"dog"are different tokens to this simple tokenizer — different strings, no match. Keyword search matches literal tokens. Real systems soften this with stemming (dogs→dog) and stop-word removal (droppinga,the). Keep this limitation in mind — it’s exactly the gap the next blog (semantic search) fills.
Our example corpus
Everything below runs against these five everyday sentences. Small enough to check by hand, big enough to be interesting:
import math
from collections import Counter
corpus = [
"The cat sat on the warm windowsill in the sun", # doc 0
"A dog chased the cat around the yard", # doc 1
"Dogs are loyal and love to play fetch in the park", # doc 2
"The park has a pond where ducks swim every morning", # doc 3
"She planted tomatoes and basil in her garden", # doc 4
]
docs = [tokenize(d) for d in corpus]
N = len(docs) # 5 documents
avgdl = sum(len(d) for d in docs) / N # average document length ≈ 9.4
# document frequency: in how many documents does each word appear?
df = Counter()
for d in docs:
for term in set(d):
df[term] += 1
Two numbers from that setup deserve a closer look, because they show up in every formula later:
avgdl — the average document length. Count the words in each document, then take
the plain average:
doc 0: "The cat sat on the warm windowsill in the sun" → 10 words
doc 1: "A dog chased the cat around the yard" → 8 words
doc 2: "Dogs are loyal and love to play fetch in the park" → 11 words
doc 3: "The park has a pond where ducks swim every morning" → 10 words
doc 4: "She planted tomatoes and basil in her garden" → 8 words
avgdl = (10 + 8 + 11 + 10 + 8) / 5 = 47 / 5 = 9.4
Think of avgdl as the yardstick for “a normal-sized document in this corpus.” Later
(Idea 4), each document’s length gets compared against it: longer than 9.4 words =
“long-ish here”, shorter = “short-ish here.”
df — the document frequency table. For each word, in how many documents does it
appear (not how many times total)? E.g. cat is in doc 0 and doc 1 → df["cat"] = 2;
the is in docs 0, 1, 2, 3 → df["the"] = 4. This table feeds Idea 2.
Now we build the score one idea at a time.
Idea 1 — Term Frequency (TF): count the clues
Detective rule 1: count the clues.
The most obvious signal: how many times does a query word appear in a document? More
mentions of cat → probably more about cats. This count is the term frequency, f.
doc1 = docs[1] # "A dog chased the cat around the yard"
freqs = Counter(doc1)
print(freqs)
Real output:
{'a': 1, 'dog': 1, 'chased': 1, 'the': 2, 'cat': 1, 'around': 1, 'yard': 1}
Notice the already appears twice — and that’s the problem with raw counting: the is
everywhere and means nothing. Idea 2 fixes exactly that.
Idea 2 — Inverse Document Frequency (IDF): rare clues matter more
Detective rule 2: “owns a 1967 Corvette” beats “owns a car”.
IDF measures how rare a term is across the entire corpus. Terms that appear in many
documents (like the or a) are less informative than terms in only a few documents
(like cat or garden). So we weight each term by its rarity.
The IDF formula used in this BM25 implementation:
IDF(term) = log( 1 + (N − n + 0.5) / (n + 0.5) )
Where:
- N — total number of documents in the corpus.
- n — number of documents containing the term.
Work one out by hand — cat, which appears in 2 of our 5 documents (N = 5, n = 2):
IDF(cat) = log( 1 + (5 − 2 + 0.5) / (2 + 0.5) )
= log( 1 + 3.5 / 2.5 )
= log( 1 + 1.4 )
= log( 2.4 )
≈ 0.875
The fraction 3.5 / 2.5 is roughly “documents without the term ÷ documents with it” —
the rarer the term, the bigger that ratio. The +0.5 on top and bottom prevents division
by zero for terms not in the corpus and smooths the values. The log keeps IDF from
getting too large and gives less weight to very frequent terms. In code:
def idf(term):
n = df.get(term, 0)
return math.log(1 + (N - n + 0.5) / (n + 0.5))
for t in ["cat", "park", "the", "unknown"]:
print(f"IDF {t!r:8} n={df.get(t,0)} {idf(t):.3f}")
Real output:
IDF 'cat' n=2 0.875
IDF 'park' n=2 0.875
IDF 'the' n=4 0.288
IDF 'unknown' n=0 2.485
Read those numbers — they are the intuition:
catandparkeach appear in 2 of 5 docs → IDF 0.875. Moderately informative.theappears in 4 of 5 docs → IDF 0.288. Common, so nearly worthless.unknownappears in 0 docs → IDF 2.485. The rarer the term, the higher the weight (this is the smoothing at work — a missing term still gets a finite value, not a crash).
The rarer the word, the more a match means. That single idea is what makes search feel smart instead of literal.
Idea 3 — Term Frequency Saturation: stop keyword stuffing
Detective rule 3: the tenth repetition of the same clue adds little.
Raw counting has another flaw: a spammy document repeating cat 100 times would crush a
genuine one that says it 3 times. But a document isn’t 33× more relevant for saying a word
33× more. After a few mentions, we get the point.
BM25 makes each extra occurrence help less than the one before — it saturates. A
knob k1 controls how fast it flattens. Watch the term-frequency component grow as f
increases (k1 = 1.5):
k1 = 1.5
def tf_component(f): # simplified: length normalization added in Idea 4
return f * (k1 + 1) / (f + k1)
for f in [1, 2, 3, 5, 10, 50]:
print(f"f={f:<3} tf_component={tf_component(f):.3f}")
Real output:
f=1 tf_component=1.000
f=2 tf_component=1.429
f=3 tf_component=1.667
f=5 tf_component=1.923
f=10 tf_component=2.174
f=50 tf_component=2.427
The same numbers as a picture — a curve that climbs fast, then flattens against a ceiling:
tf_component
2.5 ┤·································· ceiling = k1 + 1 = 2.5
2.4 ┤ ● f=50
2.2 ┤ ● f=10
1.9 ┤ ● f=5
1.7 ┤ ● f=3
1.4 ┤ ● f=2
1.0 ┤ ● f=1
└────────────────────────────────────
occurrences f →
1 → 2 mentions jumps by 0.429, but 10 → 50 mentions barely adds 0.25. The value creeps
toward the ceiling of k1 + 1 = 2.5 and never passes it. That ceiling is why you
can’t win BM25 by keyword stuffing.
Check one row by hand (f = 2):
tf_component(2) = 2 × (1.5 + 1) / (2 + 1.5) = 5 / 3.5 ≈ 1.429
See why it saturates: f sits on both the top and the bottom of the fraction. When
f is huge, the fixed +1.5 on the bottom stops mattering, and the fraction is
essentially f × 2.5 / f = 2.5 — the ceiling. The bigger f gets, the closer it
creeps, never arriving.
Idea 4 — Document Length Normalization: don’t let long docs cheat
Detective rule 4: a clue in a one-page note beats the same clue in a 300-page report.
A long document naturally contains more of every word, just by being long. Without a
correction, long documents would win every query unfairly. BM25 compares each document’s
length |D| to the average avgdl: a match in a short, focused document counts more
than the same match buried in a long, rambling one. A knob b controls the strength
(b = 0.75 typical; b = 0 means no normalization, b = 1 means full).
Same single match (f = 1), one short doc vs one long doc:
b = 0.75; f = 1
def tf_component_full(f, dl):
return f * (k1 + 1) / (f + k1 * (1 - b + b * dl / avgdl))
print(f"avgdl = {avgdl:.1f}")
print("short doc (9 words) :", round(tf_component_full(1, 9), 3))
print("long doc (30 words) :", round(tf_component_full(1, 30), 3))
Real output:
avgdl = 9.4
short doc (9 words) : 1.020
long doc (30 words) : 0.503
Same word, same one occurrence — worth 1.020 in a short document but only 0.503 in a long one. The match is a bigger fraction of a smaller document, so it counts for more.
Walk the short doc through by hand, and you’ll see where avgdl = 9.4 earns its keep.
The new piece is a length penalty that sits on the bottom of the fraction:
length penalty = 1 − b + b · dl/avgdl (b = 0.75)
short doc, 9 words: 1 − 0.75 + 0.75 × ( 9 / 9.4) = 0.25 + 0.718 = 0.968
long doc, 30 words: 1 − 0.75 + 0.75 × (30 / 9.4) = 0.25 + 2.394 = 2.644
Read dl/avgdl as “how many times a normal document is this one?” The 9-word doc is
about average (9/9.4 ≈ 0.96) → penalty ≈ 0.97, basically neutral. The 30-word doc
is over 3× average → penalty 2.644, heavy. Then the penalty lands on the bottom of
the same fraction from Idea 3:
short: 1 × 2.5 / (1 + 1.5 × 0.968) = 2.5 / 2.452 ≈ 1.020
long: 1 × 2.5 / (1 + 1.5 × 2.644) = 2.5 / 4.966 ≈ 0.503
Bigger bottom → smaller score. That’s the entire mechanism: being longer than the corpus average inflates the denominator, shrinking every match’s value.
Putting it together: BM25 by composition
Instead of memorizing one scary formula, build BM25 by composing the pieces you already wrote. No new math — just assembly, in three lines that each build on the last.
Piece A — the term-frequency component (Ideas 3 + 4 combined into one). This is the
only fraction in the whole thing, and it’s exactly the tf_component_full you already ran:
TermFreqComponent(term, D) = f · (k1 + 1) / ( f + k1 · (1 − b + b · |D|/avgdl) )
└─ Idea 3 ─┘ └────── Idea 4 ──────┘
Piece B — one term’s score = its rarity times how much it appears. Compose IDF (Idea 2) with Piece A:
term_score(term, D) = IDF(term) × TermFreqComponent(term, D)
Piece C — the whole document’s score = add up every query term’s score (Idea 1 is the
f living inside Piece A):
BM25(query, D) = Σ term_score(term, D) for each term in query
So the entire algorithm, composed:
BM25 = sum over query terms of ( IDF × TermFreqComponent )
The symbols inside: f = term frequency in D, |D| = document length in words,
avgdl = average document length, k1 scales term frequency (typically 1.2–2.0),
b is length-normalization strength (typically 0.75).
And here’s the payoff: the code below is that composition, line for line — the
length penalty (doc_length_norm), the saturating fraction (term_freq_saturation),
then IDF × that, then the sum. Read the two together.
BM25 from scratch
The whole algorithm, ~15 more lines on top of the setup above:
def term_score(term, doc, k1=1.5, b=0.75):
freqs = Counter(doc)
if term not in freqs:
return 0.0
f = freqs[term] # Idea 1: term frequency
dl = len(doc)
doc_length_norm = 1 - b + b * dl / avgdl # Idea 4
term_freq_saturation = f * (k1 + 1) / (f + k1 * doc_length_norm) # Idea 3
return idf(term) * term_freq_saturation # Idea 2 × (Ideas 3+4)
def bm25_score(query, doc):
return sum(term_score(t, doc) for t in tokenize(query))
def search(query):
scored = [(bm25_score(query, d), corpus[i]) for i, d in enumerate(docs)]
scored.sort(reverse=True, key=lambda x: x[0])
return scored
for q in ["cat", "dog park", "garden tomatoes"]:
print(f"\nQuery: {q!r}")
for score, text in search(q):
if score > 0:
print(f" {score:.3f} {text}")
Real output:
Query: 'cat'
0.938 A dog chased the cat around the yard
0.851 The cat sat on the warm windowsill in the sun
Query: 'dog park'
1.486 A dog chased the cat around the yard
0.851 The park has a pond where ducks swim every morning
0.813 Dogs are loyal and love to play fetch in the park
Query: 'garden tomatoes'
2.972 She planted tomatoes and basil in her garden
Sanity check the top line by hand — cat in “A dog chased the cat around the yard”
(8 words, cat appears once):
doc_length_norm = 1 − 0.75 + 0.75 × (8 / 9.4) = 0.888 (short doc → mild)
term_freq_saturation = 1 × 2.5 / (1 + 1.5 × 0.888) = 1.072
term_score = IDF(cat) × 1.072 = 0.875 × 1.072 = 0.938 ✓ matches the output
Every number in that ranking is just Ideas 2–4, assembled.
What the results teach us
Every line of that output demonstrates one idea:
garden tomatoes= 2.972, by far the highest. Both words are rare (each in one doc) → huge IDF, both hitting the same document → Idea 2.- For
cat, the shorter “A dog chased the cat…” (0.938) beats the longer “The cat sat on the warm windowsill…” (0.851) — both say “cat” once, but the first is shorter, so length normalization rewards it → Idea 4. dog parkranks “A dog chased the cat…” first on the rare worddog. The third result, “Dogs are loyal…”, is clearly about dogs but says “Dogs”, not “dog” — a different token, so it only matches onpark. The tokenization limitation, live.
You didn’t just read how BM25 works — you watched it rank real text and can explain every number.
BM25 as a “sparse vector”
A mental model that matters for later blogs: picture each document as a giant vector with one slot for every possible word. Most slots are zero (the word isn’t in the document); only the words present get a non-zero weight (weights below illustrative):
vocabulary slot: a basil cat dog garden park the yard ...thousands more...
doc 1 weights: 0.3 0 0.9 0.9 0 0 0.3 0.9 0 0 0 0 0
doc 4 weights: 0 1.7 0 0 1.7 0 0 0 0 0 0 0 0
Because almost every slot is zero, we call this a sparse vector. BM25 is essentially the recipe for filling in those non-zero weights — which is why modern vector databases can store BM25 right alongside other kinds of vectors. It is a vector, just a sparse one.
Using BM25 in production: FastEmbed’s SparseTextEmbedding
You won’t hand-roll BM25 in a real system. A common modern choice is FastEmbed — a
lightweight embedding library from the Qdrant team (pip install fastembed). Its
SparseTextEmbedding class produces the BM25 sparse vector for you under the model name
"Qdrant/bm25". Real code, real output:
from fastembed import SparseTextEmbedding
model = SparseTextEmbedding(model_name="Qdrant/bm25")
docs = ["A dog chased the cat around the yard",
"She planted tomatoes and basil in her garden"]
embs = list(model.embed(docs))
e = embs[0]
print("type:", type(e).__name__) # SparseEmbedding
print("num nonzero terms in doc0:", len(e.indices)) # 5
print("sample values:", [round(float(v), 3) for v in e.values[:5]])
type: SparseEmbedding
num nonzero terms in doc0: 5
sample values: [1.67, 1.67, 1.67, 1.67, 1.67]
Two things straight from the numbers:
- Only 5 non-zero terms for a 7-word sentence — FastEmbed dropped the stop-words
aandthefor you. The “sparse vector” idea made real: mostly empty, only meaningful words carry a weight. - Each remaining word carries a BM25 weight (
values), ready to be compared against a query’s sparse vector. Search then means: build the query’s sparse vector the same way, and score each document by how their non-zero slots overlap.
One caveat worth knowing: FastEmbed’s weights won’t exactly equal our from-scratch scores — its tokenization (stemming, stop-words) and IDF details differ. The four ideas, though, are identical everywhere BM25 ships.
At scale you don’t compare sparse vectors by hand — you hand them to a vector database. In
my hybrid-search course code, this exact model is wired into Qdrant with a single setting,
fastembed_sparse_model="Qdrant/bm25", and Qdrant does the BM25 scoring across the whole
collection.
How BM25 improves recall
Recall = of all the truly relevant documents, how many did search actually retrieve? (One-liner: recall means don’t miss important information.) BM25 lifts recall in cases pure meaning-based (semantic) search stumbles on:
- Exact identifiers and rare terms. Product codes, error numbers, function names,
proper nouns — matching the literal token is unbeatable, and high IDF makes those rare
tokens dominate the score. A semantic model may “understand” the query yet drift to a
document that’s merely similar in topic; BM25 lands on the one that literally contains
the code. (Remember the
error 4042example this post opened with.) - Out-of-vocabulary words. New product names or jargon a semantic model never trained on still match by exact token.
That’s why production systems rarely pick one method. They run BM25 and semantic search together — hybrid search — because the two catch different relevant documents, so their union recalls more than either alone. In one measured run on my identifier-heavy test corpus, BM25 alone reached a retrieval recall of ≈ 0.85 — beating the tuned semantic-only retriever. That’s one corpus, one run, not a law: on prose-heavy data semantic search often wins. We’ll build hybrid search in a later blog and measure it properly.
When BM25 shines — and when it fails
Shines when the query and the document share the same words, especially exact
identifiers. Fails when meaning matters more than wording: search puppy and BM25 will
not find a document that only says dog — different tokens, and BM25 has no idea they
mean the same thing. It matches words, not meaning.
That single weakness is why the next blog exists. To search by meaning — so puppy finds
dog, and car finds automobile — we need a completely different tool: embeddings
and semantic vector search.
The whole post in four lines
The detective’s rules, now with their math names:
- Count the clues → Term Frequency:
f, how often the query word appears. - Rare clues matter more → IDF: weight each term by its rarity across the corpus.
- Repetition saturates → the
k1fraction: each extra occurrence adds less, ceiling atk1 + 1. - Short and focused beats long and rambling → the
bterm: length normalization againstavgdl.
Multiply rarity by (saturated, length-normalized) frequency; sum over query terms. That’s BM25 — every symbol accounted for.
(Every snippet and every output block in this post was executed for real — the numbers are
copied from actual runs, not illustrative. This is standard Okapi BM25 with the
non-negative IDF variant common libraries use; k1=1.5, b=0.75 are typical defaults.)
Next up (2b): What is vector search? — how a sentence becomes an embedding, a
vector that carries meaning, so puppy finally finds dog and car finds
automobile. The exact weakness we just watched BM25 hit, solved.
And then (2c): Hybrid search — wire BM25 and vector search together in one Qdrant query, and measure why their union retrieves more than either alone.