Search and Retrieval, lesson 1
Keyword search with TF-IDF and BM25
Score documents by the words they share with the query.
Before a model can answer from your documents, something has to find the right passage. The oldest way needs no model at all: score each passage by the words it shares with the question. You need a little Python, and a calculator with a natural log key (ln).
By the end, you can:
Part 1. Rare words count more
Weigh each search word by how rare it is across the collection.
The simplest search counts the words a passage shares with the question. But words aren't equal. A word that's in every passage, like "the", tells you nothing about which one to pick. A word that's in only one passage points straight at it.
Example 1.1
Three passages, three words
A help centre has three passages. d1: "Refund rules for every plan: one refund per order. Each refund goes to your card. A refund takes five days." d2: "Enterprise plan: a full refund within 60 days of purchase." d3: "You can move to a bigger plan at any time, right from the billing page." Someone searches "enterprise plan refund". How much should each word count?
- Count the passages with each wordenterprise 1, refund 2, plan 3
"enterprise" is only in d2, "refund" is in d1 and d2, and "plan" is in all three.
- Divide the 3 passages by each count3 ÷ 1 = 3, 3 ÷ 2 = 1.5, 3 ÷ 3 = 1
The rarer the word, the bigger the ratio. A word in every passage gets 1.
- Take the natural loglog 3 = 1.099, log 1.5 = 0.405, log 1 = 0
Here log is the natural log:
lnon a calculator,math.login Python. It keeps a very rare word from swamping the rest, and sends a word in every passage to exactly 0.
Answerenterprise 1.099, refund 0.405, plan 0.
The weight answers one question: if a passage has this word, how much does that narrow things down? "plan" is in all three, so finding it narrows nothing. "enterprise" is in one, so finding it picks out d2. In a million passages, a code that appears once would weigh log 1,000,000, about 14.
Document frequency and IDF
A word's document frequency, n, is the number of passages that contain it. Its inverse document frequency, IDF, turns that into a weight that grows as the word gets rarer. With N passages in all:
IDF = log(N ÷ n)
Two edges. A word in no passage has no IDF, since you can't divide by 0, but it matches nothing either, so it adds nothing to any score. And IDF belongs to the whole collection: add a fourth passage and every weight moves.
Your turn
A help centre has 8 passages. "invoice" appears in 2 of them and "your" in all 8. What are their IDFs?
Part 2. Adding up the matches
Score a passage with TF-IDF, and spot how repeating a word games it.
A weight per word is half a score. The other half is how often the passage uses the word. Multiply the two for each search word, add them up, and every passage gets a score.
Example 2.1
Scoring the three passages
Score d1, d2 and d3 for "enterprise plan refund", with the weights from part 1: enterprise 1.099, plan 0, refund 0.405.
- Score d21.099 + 0 + 0.405 = 1.50
d2 says each search word once.
- Score d14 × 0.405 = 1.62
d1 never says "enterprise", says "plan" once (worth 0) and says "refund" four times.
- Score d31 × 0 = 0
Its only match is "plan", which every passage has.
Answerd1 1.62, d2 1.50, d3 0.
d2 is the answer: it's the only passage about enterprise refunds. d1 wins anyway, because it says "refund" four times, and here every repeat pays as much as the first. Four mentions of a common word outweigh one mention of a rare one.
Term frequency and TF-IDF
A word's term frequency, tf, is how many times it appears in one passage. TF-IDF scores a passage by adding up tf × IDF over the search words.
score = tf₁ × IDF₁ + tf₂ × IDF₂ + …
Repeats aren't the only problem. A long passage holds more words, so it matches more searches by chance: a 5,000-word manual will say "refund" somewhere. TF-IDF has no idea how long a passage is. The next part fixes both.
Your turn
The search words "invoice" and "account" have IDFs 1.4 and 0.3. Passage A says "invoice" once. Passage B says "account" five times and never "invoice". Which wins under TF-IDF?
Part 3. BM25 caps repeats and long passages
Score a passage with BM25, and say what its two settings, k1 and b, do.
BM25 keeps TF-IDF's idea and adds two fixes. Each extra mention of a word adds less than the one before. And a match in a long passage counts for less than one in a short passage. Two settings control them: k1 and b.
Example 3.1
BM25 for the same passages
Score d2 and d1 for "enterprise plan refund" with k1 = 1.2 and b = 0.75. d1 is 20 words long, d2 10 and d3 15, so the average is 15.
- Length factor for d20.25 + 0.75 × 10 ÷ 15 = 0.75
1 − b + b × length ÷ average. Below 1 means shorter than average, so its matches count for more.
- What one mention earns in d22.2 ÷ (1 + 1.2 × 0.75) = 1.158
tf × (k1 + 1) ÷ (tf + k1 × length factor), with tf = 1. Each match earns 1.158 times its IDF.
- Score d21.158 × (1.099 + 0.405) = 1.74
"plan" still adds 0.
- Four mentions in d14 × 2.2 ÷ (4 + 1.2 × 1.25) = 1.6
d1's length factor is 0.25 + 0.75 × 20 ÷ 15 = 1.25. Four mentions earn 1.6 times the IDF, not 4 times.
- Score d11.6 × 0.405 = 0.65
"refund" is its only match that counts.
Answerd2 1.74, d1 0.65, d3 0.
Follow one word in a passage of average length. The first mention earns its IDF. The second adds 0.38 times the IDF, the third 0.20, and no number of mentions gets past 2.2 times, which is k1 + 1. Repeating a word stops paying, so d2 comes first.
BM25
A keyword score that adds, for each search word, its IDF times a capped count. k1 sets how fast repeats stop paying; b sets how much length matters, from 0 (not at all) to 1 (fully). L is the length factor, 1 − b + b × length ÷ average.
IDF × tf × (k1 + 1) ÷ (tf + k1 × L)
Engines differ in the small print. Lucene, the library under Elasticsearch, defaults to k1 = 1.2 and b = 0.75, with a smoothed IDF, log(1 + (N − n + 0.5) ÷ (n + 0.5)), that never reaches 0. The numbers move; the two fixes don't.
Your turn
With k1 = 1.2 and b = 0.75, a passage of exactly average length says "enterprise" twice. Its IDF is 1.099. What does the word add to the passage's BM25 score?
Part 4. BM25 matches spellings
Predict which searches BM25 misses, and which it gets exactly right.
BM25 only sees spellings. That makes it sharp on exact strings and blind to anything said in other words. Ask the three passages a question the way a customer would.
Example 4.1
Can I get my money back?
Someone types "can I get my money back". Score d1, d2 and d3 with BM25, as in part 3.
- Look up each wordcan: d3 only; the rest: none
"i", "get", "my", "money" and "back" appear in no passage, so they add nothing to any score.
- Score d31.099 × 2.2 ÷ 2.2 = 1.10
"can" is in 1 passage of 3, so its IDF is 1.099. d3 is exactly average length, so its length factor is 1 and one mention earns exactly the IDF.
- Score d1 and d20 and 0
Neither shares a single word with the question.
Answerd3 first, with 1.10. Both refund passages score 0.
A person sees at once that "money back" means a refund. BM25 sees six words. Five appear nowhere, and the sixth, "can", happens to sit in the page about moving to a bigger plan. It matched the one word that says nothing about refunds.
Vocabulary mismatch
When a question and the passage that answers it use different words for the same thing. To keyword search the passage has no matching words, so it scores 0 however well it answers.
Partial fixes exist. Stemming cuts words to a root, so "refunds" matches "refund". A synonym list can map "money back" to "refund", one pair at a time. Searching by meaning, the next lesson, is the general fix.
The same blindness is a strength. To BM25, the error codes E-4012 and E-4021 are different words, and a code that appears in one passage of a million gets an IDF near 14. Product names, part numbers and function names work the same way.
Your turn
A help page says "Reset your password from the sign-in screen." Which search gives it a BM25 score of 0?
Where you'll meet it
Asked to explain BM25, name its three parts: IDF, so rare words count more; a capped count, so repeats stop paying (k1); and a length factor, so long passages don't win by size (b). Then say where it fails: a question worded differently from the text scores 0.
Elasticsearch scores text with BM25 by default, with k1 = 1.2 and b = 0.75. On BEIR, a benchmark of 18 search datasets from different fields, BM25 proved a hard baseline: dense retrievers trained on other data often scored below it. Much of the tuning goes into the analyzer, the step that lowercases, splits and stems text.
import math, re
docs = {
"d1": "Refund rules for every plan: one refund per order. "
"Each refund goes to your card. A refund takes five days.",
"d2": "Enterprise plan: a full refund within 60 days of purchase.",
"d3": "You can move to a bigger plan at any time, right from the billing page.",
}
words = {d: re.findall(r"[a-z0-9]+", text.lower()) for d, text in docs.items()}
N = len(words)
avg = sum(len(w) for w in words.values()) / N # 15.0
def idf(term):
n = sum(term in w for w in words.values())
return math.log(N / n) if n else 0.0
def bm25(query, d, k1=1.2, b=0.75):
L = 1 - b + b * len(words[d]) / avg
score = 0.0
for term in query.lower().split():
tf = words[d].count(term)
score += idf(term) * tf * (k1 + 1) / (tf + k1 * L)
return score
for q in ["enterprise plan refund", "can I get my money back"]:
print(q, {d: round(bm25(q, d), 2) for d in docs})
# enterprise plan refund {'d1': 0.65, 'd2': 1.74, 'd3': 0.0}
# can I get my money back {'d1': 0.0, 'd2': 0.0, 'd3': 1.1}re.findall lowercases and splits the text: a tiny analyzer. Set b to 0 and length stops counting: d2 drops to 1.50 and d1 rises to 0.69, though d2 still wins.
Check yourself
Four questions from across the lesson. Try each one before you look back.
1
You set b to 0. What changes?
2
A support log has 200,000 passages, and only one contains the code "E-4012". Someone searches for exactly that code. Why does BM25 put that passage first?
3
A customer types "can I get my money back". Which passage would BM25 miss, even though it answers the question?
4
Under plain TF-IDF, a passage that says "refund" ten times gets ten times the credit of one that says it once. What goes wrong?
What to remember
1Rare words count more
IDF = log(N ÷ n) weighs a word by its rarity: in 1 passage of 3 it's 1.099, in all 3 it's 0.
2Adding up the matches
TF-IDF adds tf × IDF per search word, so four mentions of "refund" (1.62) beat one each of "enterprise" and "refund" (1.50).
3BM25 caps repeats and long passages
BM25 caps repeats, so no word earns more than k1 + 1 = 2.2 times its IDF, and marks down long passages with b = 0.75: that put d2 first, 1.74 to 0.65.
4BM25 matches spellings
BM25 matches spellings: "can I get my money back" scores 0 against both refund passages, while an exact code like E-4012 is found at once.
Recap and going further
The lesson on one page
- IDF = log(N ÷ n)
- A word in every passage weighs 0
- Mentions times IDF, added up
- Repeating a word keeps paying
- Repeats pay less and less: never past (k1 + 1) × IDF
- Long passages are marked down (b)
- No model, fast on millions of passages
- Exact codes such as E-4012
- Different words for the same idea
- "money back" never matches "refund"
Try this
Run BM25 on text you know
Install rank_bm25 and split a long page you know well (a product FAQ, a policy, your own notes) into 50 to 200 paragraphs. Lowercase and split each into words, build a BM25Okapi index, and ask it ten questions you'd really ask. Then try b = 0 and b = 1, and add stemming (for example with NLTK's Porter stemmer).
You need: Python with rank_bm25 (pip install rank_bm25).
Look for
- Which questions fail because they use different words from the text.
- How the top results change when b goes from 0 to 1.
- Plural and singular forms missing each other until you add stemming.
- Whether an exact code or name in a question finds its paragraph first time.
- That the scores differ from the lesson's:
BM25Okapiuses k1 = 1.5 and its own form of IDF.
The words, in plain language
- Document frequency and IDF
- A word's document frequency, n, is the number of passages that contain it. Its inverse document frequency, IDF, turns that into a weight that grows as the word gets rarer. With N passages in all:
- Term frequency and TF-IDF
- A word's term frequency, tf, is how many times it appears in one passage. TF-IDF scores a passage by adding up tf × IDF over the search words.
- BM25
- A keyword score that adds, for each search word, its IDF times a capped count. k1 sets how fast repeats stop paying; b sets how much length matters, from 0 (not at all) to 1 (fully). L is the length factor, 1 − b + b × length ÷ average.
- Vocabulary mismatch
- When a question and the passage that answers it use different words for the same thing. To keyword search the passage has no matching words, so it scores 0 however well it answers.
Read next
- Practical BM25 - Part 2: The BM25 Algorithm and its VariablesElastic blogHow k1 and b behave in a real search engine, and when to change them.
- The Probabilistic Relevance Framework: BM25 and BeyondRobertson and Zaragoza, 2009The full account of where BM25 comes from, by one of its authors.
- BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval ModelsThakur and colleagues, 2021Eighteen search datasets from different fields, where BM25 proves a hard baseline to beat.
Search and Retrieval overviewSpotted a mistake? Tell us.