Classical Retrieval: BM25 and the Inverted Index
Fifty years of search engineering in one week — and the baseline every later technique must beat.
- Build an inverted index and explain why it makes search fast
- Derive TF-IDF and BM25 from first principles
- Evaluate retrieval with Recall@k, Precision@k, and MRR
- Establish a measured baseline over your capstone corpus
Open the full Week 2 study material → Complete lesson: concepts in depth, the full lab with all code, and troubleshooting.
Concepts
1. The inverted index
Instead of scanning every document per query, map each term to the documents containing it. Every search engine since the 1970s — including Elasticsearch today — is built on this structure.
2. From counting to TF-IDF
Term frequency says a document mentioning your term often is probably relevant. Inverse document frequency says rare terms carry signal and common ones don't. Multiply them and search 'just works' surprisingly often.
3. BM25: TF-IDF grown up
Two refinements made BM25 the 25-year industry standard: term-frequency saturation (the 50th occurrence shouldn't count like the 2nd — parameter k1) and length normalization (long documents match everything by accident — parameter b).
4. Measuring retrieval
Recall@k: of the relevant documents, how many made the top k? MRR: how high does the first relevant one rank? You cannot improve what you do not measure — these metrics become the spine of Week 5.
Lab — live session
- Build an inverted index + TF-IDF scorer in pure Python (~60 lines) over your corpus
- Swap in
rank_bm25; compare rankings against your hand-rolled version - Write 10 test queries with known-relevant documents
- Compute Recall@5 and MRR — your official course baseline
bm25_baseline.py, eval_queries.json, and a metrics table, committed. Every later week must beat these numbers or justify itself.
Reading
Watch
Reflection — bring answers to the next session
- Why does IDF alone explain most of why keyword search works?
- When would you tune k1 and b rather than accept the defaults?
- Which of your failure queries do you predict embeddings will fix — and which won't they?
Challenge 2: Break BM25 — The fastest way to understand a system is to find its edges. Your mission: make your own search engine fail, on purpose, five different ways.