Loading
0x20Lesson 3 of 11

Search by keywords with BM25

Build an inverted index and rank passages with BM25, the workhorse of keyword search.

22 min 5-question quiz 2 code exercises
By the end of this lesson you can
  • Build an inverted index from words to documents
  • Explain how BM25 rewards rare terms and repeated terms, and penalizes long documents
  • Tune BM25’s k1 and b parameters

Before embeddings, there was keyword search - and it’s still essential. Search engines build an inverted index: for every word, the list of documents containing it, like the index at the back of a book. Looking up a query is then just reading a few lists.

To rank the matches, most engines (Elasticsearch, OpenSearch, Lucene) use BM25. For each query term it multiplies:

  • IDF - how rare the term is across all documents. “the” is everywhere and counts for almost nothing; “restocking” is rare and counts a lot.
  • Term frequency with saturation - a term appearing twice helps more than once, but the 10th repeat adds little. k1 controls how fast it saturates.
  • Length normalization - a match in a short, focused passage beats one in a rambling page. b controls how strongly length is penalized.

Try it

Up to 15 XP

BM25 explorer

Try each query and read the per-term scores. Then: set b to 0 and watch the long “Router reset” page’s score rise for “reset password” (its length is no longer penalized); set k1 to 0 and see repeats stop mattering; search for “the”.

  1. 1. Reset your password2.00

    Reset your password from the login page. Click Forgot password and follow the email link.

    reset: tf 1 · idf 0.88 → 0.83password: tf 2 · idf 0.88 → 1.16
  2. 2. Router reset1.02

    Reset the router by holding the button for ten seconds, then reset the network settings and reconnect every device to the network.

    reset: tf 2 · idf 0.88 → 1.02password: tf 0 · idf 0.88 → 0.00
  3. 3. Password rules0.91

    Passwords need at least 15 characters. Password managers can generate long passwords.

    reset: tf 0 · idf 0.88 → 0.00password: tf 1 · idf 0.88 → 0.91
  4. 4. Change email0.00

    Change your email address in account settings.

    reset: tf 0 · idf 0.88 → 0.00password: tf 0 · idf 0.88 → 0.00
  5. 5. Error E40120.00

    Error E4012 means the payment card was declined by the bank.

    reset: tf 0 · idf 0.88 → 0.00password: tf 0 · idf 0.88 → 0.00
idf.py
1import math
2documents = 1000
3for term, containing in [("the", 990), ("password", 40), ("restocking", 2)]:
4    idf = math.log(1 + (documents - containing + 0.5) / (containing + 0.5))
5    print(f"{term}: {idf:.2f}")
Output
the: 0.01
password: 3.21
restocking: 5.99

Key takeaways

  • An inverted index maps each word to the documents that contain it.

  • BM25 = rare terms × saturating term frequency × length normalization.

  • Keywords excel at exact identifiers; they miss synonyms and paraphrases.

Lesson quiz

5 questions · pass with 4 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: write Python

Write Python in the editor and run it against sample inputs. Python runs locally in your browser using a WebAssembly runtime.

Exercise 1

Build an inverted index

+25 XP

Lines before --- are documents: id text. Lines after are queries. Build an index from lowercase words (re.findall(r"[a-z0-9]+", ...)) to document IDs. For each query print query: ids - the IDs containing all its words, sorted - or query: none.

  • Help center
main.py
Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Exercise 2

Score with BM25

+25 XP

The first line is a query; each following line is id text. Using lowercase words from re.findall(r"[a-z0-9]+", ...) (excluding the id), compute BM25 with k1=1.2k_1 = 1.2 and b=0.75b = 0.75. For each query term, where nn is how many documents contain it:

idf=ln⁡(1+N−n+0.5n+0.5)\text{idf} = \ln\left(1 + \frac{N - n + 0.5}{n + 0.5}\right)
term score=idf⋅tf⋅(k1+1)tf+k1(1−b+b⋅lengthaverage length)\text{term score} = \text{idf} \cdot \frac{\text{tf} \cdot (k_1 + 1)}{\text{tf} + k_1 \left(1 - b + b \cdot \frac{\text{length}}{\text{average length}}\right)}

Sum over the distinct query terms. Print id score (3 decimals) for scores above 0, highest first.

  • Reset password
main.py
Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…