BM25
- Lesson 9
- 40 min
- Module 3: Lexical search: the baseline to beat
Where we are
An inverted index finds every product that has our words. It does not say which product is best. In this lesson, we score products with BM25, see each part of the score, and give the title more weight than the description.
Lesson 9 of 30 · Search and Ranking: Find the Best MatchBM25
1. The search problem
2. Measure relevance before you change anything
3. Lexical search: the baseline to beat
4. Understand the query
5. Dense and hybrid retrieval
6. Re-rank the top results
7. The parts of search that people see
8. Run search in production
What you will be able to do
Put the best products first among the hundreds that match a query, with a score that you can explain word by word.
NotebookDo the calculations of this lesson in a notebook
The notebook computes BM25 by hand for six products and checks it with the bm25s library. Then it explains a real score, part by part, and you tune the title weight on the validation queries. Its setup cells download the data, so it needs no local setup. About 25 minutes.
Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.
Before you startWhat to know and to have ready
What you need to know
- Tokens, postings and “any word may match”, from The inverted index.
- NDCG@10, from Ranking measures.
- Validation and test queries, and the 95% interval of a difference, from Build a test set that represents your users.
What you need on your computer
- The project
larkfield-searchwith its virtual environment active, and the labs repository next to it, as in the earlier modules. This lesson adds four files and the README from the snapshotend-of-m03.
Three clues that a shop assistant uses
Section titled “Three clues that a shop assistant uses”A customer gives the shop assistant a note: “garden hose”. She looks at two product labels. The first label is short: “garden hose with reel”. The second is a long catalogue page about a planter. It says “garden” twice and, near the end, “connects to your garden hose”.
She uses three clues.
- A rare word is a strong clue. Almost every garden product says “garden”. Few products say “hose”. So “hose” tells her more than “garden”.
- A repeated word is a clue, but less each time. A label that says “hose” three times is probably about hoses. But the third “hose” adds less than the first.
- A word in a short label means more than the same word lost in a long page. On a short label, every word is about the product.
She picks the short label. BM25 is a formula with the same three clues.
The problem: many products, no order
Section titled “The problem: many products, no order”The last lesson ended with a problem. “garden hose” with “any word may match” finds 1,439 products. A person reads ten.
A first idea: count the query words in each product. But 24 products have both words, and they all get 2: a tie. The 1,415 others all get 1: another tie. The count treats “garden” and “hose” as equal, and a 7-word title like a 300-word description.
The idea: BM25
Section titled “The idea: BM25”BM25 gives each product a score for a query, and the highest scores come first. BM25 means “Best Matching 25”: a ranking formula from the 1990s, named after the versions that its authors tried. It is still the default ranking of the common open-source search engines.
The score is a sum. Each query word adds one part. The part of a word is its rarity, multiplied by a share between 0 and 1. The share grows when the word appears more often in the product, and falls when the product is long. A word that is not in the product adds 0.
Clue 1: rarity, or IDF
Section titled “Clue 1: rarity, or IDF”The rarity of a word is its IDF, the inverse document frequency. The document frequency (df) of a word is the number of products that contain it: the size of its postings list. “Inverse” means that a small df gives a large IDF. With N products in the catalogue:
ln is the natural logarithm. It makes the IDF grow slowly: a word in 10 times fewer products gets about 2.3 more, not 10 times more. In Larkfield’s catalogue, with N = 40,066:
| Word | In how many products (df) | IDF |
|---|---|---|
| the | 28,152 | 0.353 |
| chair | 4,293 | 2.233 |
| garden | 1,352 | 3.389 |
| headboard | 1,089 | 3.605 |
| hose | 111 | 5.884 |
| emma | 6 | 8.727 |
“the” is almost worthless. “hose” is worth almost twice “garden”. “emma”, a name in six products, is worth the most.
Clue 2: repeats, with saturation
Section titled “Clue 2: repeats, with saturation”The number of times a word appears in a product is its term frequency (tf). BM25 does not multiply by tf. It uses a share that grows quickly at first, then slowly:
For a product of average length, the norm is 1. With the usual setting k1 = 1.2, one appearance gives a share of 1 ÷ 2.2 = 0.455. Two give 0.625, and ten give 0.893. The share never reaches 1. This is saturation: after a few repeats, more repeats add almost nothing. So a seller cannot win by writing “hose hose hose”.
k1 sets how fast the share saturates. A small k1 (such as 0.5) means that the first appearance is almost all that counts. A large k1 (such as 3) gives repeats more weight.
Clue 3: length
Section titled “Clue 3: length”The norm depends on the product’s length, compared with the average length of the catalogue:
A short product has a norm below 1, so the same tf gives a larger share. A long product has a norm above 1. b sets how much length counts: b = 0 ignores length, and b = 1 counts it fully. The usual setting is b = 0.75.
The chart shows the share for three products of Larkfield’s catalogue: a short one, one of average length (71.7 words), and a long one.
Text description of the chart
The x-axis is tf, from 0 to 10. The y-axis is the share of the IDF, from 0 to 1. There are three curves. All three start at 0 for tf 0, rise steeply, then flatten. A short product of 7 words gets 0.721 for one appearance and 0.963 for ten. A product of average length, 72 words, gets 0.455 for one appearance, 0.714 for three and 0.893 for ten. A long product of 200 words gets less for each tf: the curve is the lowest of the three. For every length, the step from tf 1 to tf 2 is much larger than the step from tf 9 to tf 10.
The whole score
Section titled “The whole score”Put the three clues together. For each query word in a product:
The score of the product is the sum of the parts of the query words. Many books write an extra factor (k1 + 1) on top. It multiplies every score by the same number, so the order of the products does not change. The project’s library, bm25s, leaves it out, like the Lucene search library.
A tiny example with every value
Section titled “A tiny example with every value”Take the six products of the last lesson and the query “outdoor hose”. There are N = 6 products, with an average length of 20 ÷ 6 = 3.333 tokens. “outdoor” is in 3 products, so its IDF is ln(1 + 3.5 ÷ 3.5) = 0.693. “hose” is in 2 products, so its IDF is ln(1 + 4.5 ÷ 2.5) = 1.030. Every word appears once, so tf = 1.
| Product | Length | k1 × norm | “outdoor” part | “hose” part | Score | Rank |
|---|---|---|---|---|---|---|
| F hose reel cart | 3 | 1.110 | 0 | 1.030 × 1 ÷ 2.110 = 0.488 | 0.488 | 1 |
| C garden hose with reel | 4 | 1.380 | 0 | 1.030 × 1 ÷ 2.380 = 0.433 | 0.433 | 2 |
| A grey outdoor cushion | 3 | 1.110 | 0.693 × 1 ÷ 2.110 = 0.329 | 0 | 0.329 | 3 |
| B blue outdoor cushion cover | 4 | 1.380 | 0.291 | 0 | 0.291 | 4 |
| E outdoor sofa with cushions | 4 | 1.380 | 0.291 | 0 | 0.291 | 4 |
| D grey sofa | 2 | 0.840 | 0 | 0 | 0 | — |
The hose products come first, because “hose” is rarer than “outdoor”. F beats C, because F has 3 words and C has 4. The notebook computes this table and checks it against bm25s.
Larkfield: explain a real score
Section titled “Larkfield: explain a real score”The project’s run bm25 is this formula, with k1 1.2 and b 0.75, on the title and the description together. You measured it in Module 1: NDCG@10 0.429 on the test queries. Now you look inside one of its scores.
-
Copy this module’s files from the snapshot
end-of-m03. They are the field runs, the commandsearch explain, the product-code rule of the next lesson, their tests and the README:Terminal window S=../nextia-learning-labs/C38/snapshots/end-of-m03for f in larkfield_search/runs/fields.py larkfield_search/rules.py larkfield_search/commands/explain.py tests/test_fields.py README.md; docp "$S/$f" "$f"doneTerminal window $S = "..\nextia-learning-labs\C38\snapshots\end-of-m03"foreach ($f in 'larkfield_search\runs\fields.py', 'larkfield_search\rules.py', 'larkfield_search\commands\explain.py', 'tests\test_fields.py', 'README.md') { Copy-Item "$S\$f" $f } -
Run the tests:
Terminal window python -m pytest -q................... [100%]19 passed in 1.01sThree tests are new. One checks that the parts of
search explainadd up to the library’s score. Your time will differ. -
Search “emma headboard” with BM25. It is a real WANDS validation query:
Terminal window search query "emma headboard" --run bm25 -k 7bm25: "emma headboard" -> 7 results (query W-481: judged results are marked)1. LK-97580 emma large wooden playground bird activity center Bird Play Stand & Playce 51.99 [irrelevant]2. LK-33434 emma body pillowcase Sheets And Sheet Sets 173.99 [irrelevant]3. LK-78778 emma-lea solid wood low profile storage platform bed 113.99 [irrelevant]4. LK-39071 multicolor reversible floral cotton 4 piece quilt set Bedding Sets 14.99 [not judged]5. LK-19417 cumulus landscape ii by emma scarvey - wrapped canvas painti Wall Art 250.99 [out of stock] [irrelevant]6. LK-53888 neutral arrangement i by emma scarvey - wrapped canvas paint Wall Art 147.99 [out of stock] [irrelevant]7. LK-45931 bali hai open-frame headboard Headboards 11.99 [partial]A bird activity centre comes first. The first headboard is at rank 7.
-
Ask for the parts of the first product’s score, then of the headboard’s:
Terminal window search explain "emma headboard" LK-97580search explain "emma headboard" LK-45931BM25 of LK-97580 "emma large wooden playground bird activity center" for "emma headboard" (field all, k1 1.2, b 0.75)word tf df IDF length avg partemma 1 6 8.727 7 71.7 6.288headboard 0 1089 3.605 7 71.7 0.000sum of the parts 6.288; the index's score 6.288BM25 of LK-45931 "bali hai open-frame headboard" for "emma headboard" (field all, k1 1.2, b 0.75)word tf df IDF length avg partemma 0 6 8.727 48 71.7 0.000headboard 5 1089 3.605 48 71.7 3.054sum of the parts 3.054; the index's score 3.054Each row is one query word, with its tf, df and IDF, the product’s length in tokens, and the catalogue’s average length. The last line checks the sum of the parts against the index’s own score.
The diagram puts the two scores side by side.
Text description of the diagram
The query is “emma headboard”. On the left is product LK-97580, “emma large wooden playground bird activity center”. “emma” is in 6 products, so its IDF is 8.73. It appears once in a product of 7 words, which gives a share of 0.72. 0.72 × 8.73 = 6.29. “headboard” is not in this product and adds 0. The score is 6.29: rank 1, and the judges graded it irrelevant. On the right is LK-45931, “bali hai open-frame headboard”. “emma” adds 0. “headboard” is in 1,089 products, so its IDF is 3.60. It appears 5 times in 48 words, which gives a share of 0.85. 0.85 × 3.60 = 3.05: rank 7, graded partial. Under each product, a bar shows its score on the same scale. The bar of the bird centre is about twice as long.
The bird activity centre has no description, so its text is only its 7-word title. One rare “emma” in 7 words gives 72% of a very large IDF. The headboard gets 85% of a much smaller IDF, because 1,089 products say “headboard”.
BM25 did exactly what its three clues say. But the clues do not know what the person wants. In “emma headboard”, “headboard” is the kind of product, and “emma” is only a name. Module 4 detects the kind of product in the query, and Module 6 learns from judged queries which signals matter.
The settings k1 and b
Section titled “The settings k1 and b”The project uses k1 = 1.2 and b = 0.75 for every BM25 run, the usual defaults. You can tune them on validation queries. Expect small gains: they change how much repeats and length count, not which words match. In the notebook, change K1 and B in the first cell and run it again.
Fields with weights
Section titled “Fields with weights”So far, the title and the description are one block of text. But a product has fields: separate parts with different roles. Larkfield’s products have four that matter here:
- title: a few words that name the product;
- description: a long text from the seller;
- category: the product class and the category path, such as “Headboards” and “Furniture / Bedroom Furniture / Headboards”;
- attributes: colour, style, material and other details.
With one BM25 index for each field, the score becomes a weighted sum. If the title weight is 3, a title match counts three times as much as a description match:
The run bm25-fields uses weights. Try it on the same query:
search query "emma headboard" --run bm25-fields -k 4bm25-fields: "emma headboard" -> 4 results (query W-481: judged results are marked) 1. LK-33434 emma body pillowcase Sheets And Sheet Sets 173.99 [irrelevant] 2. LK-19612 phirun bookcase headboard Headboards 30.99 [partial] 3. LK-77778 prepac storage bookcase headboard Kids Headboards 605.99 [partial] 4. LK-83984 driftwood panel headboard Headboards 44.99 [partial]The category field says “Headboards”, so headboards now fill ranks 2 to 10. A pillowcase named “emma” still comes first. But one query is a story, not a measurement.
Choose the weights on the validation queries
Section titled “Choose the weights on the validation queries”Which weights are best? The project tried a grid of 96 settings: title 1, 2, 3 or 5; description 0.5 or 1; category 0, 0.5, 1 or 2; attributes 0, 0.5 or 1. It measured each one on the 121 validation queries, never on the test queries. The best was title 1, description 1, category 0.5, attributes 0: NDCG@10 0.459. This is the setting of bm25-fields:
search eval --run bm25-fields --split validationbm25-fields on 121 validation queries: NDCG@10 0.459 (95% interval 0.388 to 0.529)recall@100 0.400, MRR 0.392, zero results 11.6%, judged in the top 10 69.9%; 0.2 ms a query (p50), 0.8 ms (p95)--set changes one weight for one command, without editing code. Try the setting that many people would pick by hand, with the title first:
search eval --run bm25-fields --set title=3 --set category=1 --set attributes=0.5 --split validationbm25-fields on 121 validation queries: NDCG@10 0.453 (95% interval 0.383 to 0.521)recall@100 0.416, MRR 0.377, zero results 11.6%, judged in the top 10 71.1%; 0.2 ms a query (p50), 0.5 ms (p95)The hand-picked setting scores 0.453, so the tuned one wins on validation by 0.006. Notice that the title needs no extra weight here. Most titles repeat in the descriptions, so a title word is already counted twice.
Then measure on the test queries, once
Section titled “Then measure on the test queries, once”The chart shows five settings on both sets of queries. The top panel is what we could see when we chose. The bottom panel is the test, measured once, after the choice.
Text description of the chart
Two panels show NDCG@10 with 95% intervals. Validation (121 queries): one field 0.432 (0.363 to 0.502); title only 0.428; equal weights 0.416; hand-picked 3, 1, 1, 0.5 0.453 (0.383 to 0.521); tuned 1, 1, 0.5, 0 0.459 (0.388 to 0.529). Test (243 queries): one field 0.429 (0.381 to 0.476); title only 0.423; equal weights 0.400; hand-picked 0.447 (0.397 to 0.497); tuned 0.423 (0.375 to 0.471). The tuned row is highlighted. Every interval overlaps the others.
On the test queries, the order changes: tuned 0.423, hand-picked 0.447, one field 0.429. Is the change real? A paired comparison answers this, query by query, as in Build a test set that represents your users. Hand-picked minus tuned:
| Queries | Difference in NDCG@10 | 95% interval | Better / worse / the same |
|---|---|---|---|
| Validation (121) | −0.006 | −0.029 to +0.014 | 33 / 36 / 52 |
| Test (241 that have a right product) | +0.024 | +0.009 to +0.038 | 89 / 50 / 102 |
On validation, the difference of 0.006 is noise: its interval includes 0. In fact, 19 of the 96 settings scored within 0.01 of the best. The grid picked a winner among near-ties. On test, the hand-picked weights are better, and the interval does not include 0.
Why we keep the tuned weights
Section titled “Why we keep the tuned weights”Priya keeps the tuned weights in the project. Tomás asks: “But the hand-picked ones are clearly better on test. Why not switch?”
Then the test queries would choose the weights. The reported score would look better than the search really is.
So the rule stays: choose on validation, report test once, and do not go back. The report is honest: “Per-field BM25 with tuned weights: 0.423 on test. It is not better than one field (−0.006, interval −0.025 to +0.012).”
Two lessons for next time:
- A small win on validation is not a win. With 121 queries, differences below about 0.02 are noise. When many settings tie, prefer the simplest one, or get more validation queries.
- “Title over description” is not a law. It depends on the catalogue. Here, title words are in the description too.
The machine learning course explains the same rule for models in Train, validation and test sets.
When to use BM25, when not, and what it costs
Section titled “When to use BM25, when not, and what it costs”Use BM25 as the first ranking of any word search, and as the baseline that every later method must beat. It needs no training data and no model. In this course, it more than doubles NDCG@10 against Larkfield’s search today: 0.429 against 0.195.
What it costs. Very little. A query takes 0.6 milliseconds at the median, on one thread (measured in Module 8). All the lexical indexes of this module take 80.9 MB on the disk.
When it fails. It ranks by words, so it fails where words mislead:
- a rare name pulls up anything with that name (“emma headboard”);
- a misspelt word adds nothing (“grey outdor cushion”);
- another word for the same thing adds nothing (“couch” and “sofa”);
- a product code is not a word of the text (next lesson).
Try it yourself
Section titled “Try it yourself”This is the module’s independent task. Choose your own field weights on the validation queries only, with --set and --split validation. For example:
search eval --run bm25-fields --set title=2 --set category=1 --split validationKeep a table of your settings and their NDCG@10. Run your best setting once on the test queries, without --split. Report it against the one-field bm25 row (0.429 on test), with both intervals. Was your validation win larger than the noise?
What we got: title 2, description 1, category 1, attributes 0 scores 0.448 on validation (interval 0.378 to 0.515). That is below the tuned setting’s 0.459, so we would keep the tuned setting, and its test score of 0.423. The difference of 0.011 is also inside the noise.
Common mistake
Choosing the weights on the test queries
Symptom: you try ten weight settings with search eval and no --split. The best scores 0.447 on test, and you report 0.447. Next month, a new set of queries gives 0.42, and nobody understands why the search got worse.
Cause: search eval measures on the test queries by default. Ten tries on test are ten chances to find a setting that is lucky on these 243 queries. The reported score includes that luck.
Diagnosis: look at your notes or your terminal history. If any setting was chosen after a run on the test split, the test score is optimistic. There is no way to remove the luck afterwards.
Fix: choose with --split validation only. Run the chosen setting on test once and report it, even if it is lower. For a fresh, unbiased check later, keep a held-out set that nobody uses to choose, as in Build a test set that represents your users.
Consequence in AI work: every tuned weight, threshold or prompt carries this risk. A team that tunes on its test set reports progress that users never see.
Knowledge check
Section titled “Knowledge check”Check your understanding
Compute the BM25 part of “hose” in product C “garden hose with reel” of the six products. Use N = 6, df = 2, tf = 1, length 4, average length 3.333, k1 1.2 and b 0.75.
Show the answer
IDF = ln(1 + (6 − 2 + 0.5) ÷ (2 + 0.5)) = ln(2.8) = 1.030. Norm = 1 − 0.75 + 0.75 × 4 ÷ 3.333 = 1.15, so k1 × norm = 1.38. Share = 1 ÷ (1 + 1.38) = 0.420. Part = 1.030 × 0.420 = 0.433. Product F is one word shorter, so its share is larger (0.474) and its part is 0.488.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
Explain, with the parts of the score, why BM25 puts a bird activity centre above a headboard for “emma headboard”.
Show the answer
The bird activity centre gets only the part of “emma”. “emma” is in 6 of 40,066 products, so its IDF is very high (8.727). The product has only 7 words, far below the average of 71.7, so one appearance gives 72% of that IDF: 6.288. The headboard gets only the part of “headboard”. Its share is 85% (5 times in 48 words), but of a small IDF (3.605, in 1,089 products): 3.054. BM25 cannot know that “headboard” is the kind of product and “emma” only a name.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
Omar says: “The hand-picked weights scored 0.447 on test, and our tuned ones 0.423. Switch to the hand-picked weights and report 0.447.” What do you answer?
Show the answer
We do not switch, and we report 0.423. If the test queries choose the weights, they stop being a fair test, and 0.447 would include the luck of that choice. On validation, where we could choose, the two settings differed by only −0.006 (interval −0.029 to +0.014): a tie. Next time, treat such small wins as ties, and prefer the simpler setting or get more validation queries.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Recap
- BM25 scores a product as a sum of parts, one per query word. Each part is the word’s IDF (rarity) times a share that grows with tf (with saturation) and falls with the product’s length.
- k1 sets how fast repeats saturate, and b how much length counts. The project uses the usual 1.2 and 0.75.
search explainshows every part. “emma headboard” puts a bird activity centre first. One rare word in a 7-word product (6.288) beats a common word five times in a 48-word product (3.054).- Fields with weights score the title, the description, the category and the attributes apart. Tuned on validation, they won by 0.006, which is noise, and lost on test (0.423 against 0.447). We keep them and report 0.423, because the test queries must not choose.
You can now rank any product by its words, and explain each score. But some queries have no useful words at all: “LK-91857” is a product code, and BM25 finds nothing for it. Next, you add an exact-match rule, and measure when a rule beats any score.
Next: Exact matches and rules