Search by keywords with BM25
Build an inverted index and rank passages with BM25, the workhorse of keyword search.
- 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.
k1controls how fast it saturates. - Length normalization - a match in a short, focused passage beats one in a rambling page.
bcontrols how strongly length is penalized.
Try it
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. Reset your password1.99
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. Router reset1.01
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.01password: tf 0 · idf 0.88 → 0.00 - 3. Password rules0.94
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.94 - 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. 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
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}")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.
Build an inverted index
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
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.
Score with BM25
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.2 and b = 0.75:
- idf = ln(1 + (N − n + 0.5) / (n + 0.5)), where n is how many documents contain the term;
- term score = idf × tf × (k1 + 1) / (tf + k1 × (1 − b + b × length / average length)).
Sum over the distinct query terms. Print id score (3 decimals) for scores above 0, highest first.
- Reset password
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…