Classical Retrieval: BM25 and the Inverted Index

Fifty years of search engineering, built by hand over your own corpus. By the end you'll have a working search engine, understand every number it computes, and — most importantly — have a measured baseline that every later technique in this course must beat.

Part 1 — The inverted index: why search is fast

The naive way to search: for each query, scan every document. That's O(corpus size) per query — fine for 20 documents, absurd for 20 million. The fix, unchanged since the 1970s, is to do the scanning once, in advance, and flip the direction of the map:

Forward:  doc1 → ["retrieval", "systems", "need", "evaluation", ...]
Inverted: "retrieval" → [doc1, doc4, doc9]
          "evaluation" → [doc1, doc7]

At query time you look up each query term — a hash-table hit — and intersect or union the document lists. Query cost now scales with the number of matching documents, not the corpus. Elasticsearch, Lucene, and every web search engine are, at their core, this data structure plus decades of engineering around it.

Part 2 — Scoring: from counting to TF-IDF

The index finds candidates; scoring ranks them. Two intuitions, each one formula:

Term frequency (TF). A document that mentions "chunking" ten times is more likely about chunking than one that mentions it once. Count occurrences.

Inverse document frequency (IDF). Not all terms are equal. "The" appears in every document — matching it carries zero information. "Multihop" appears in two — matching it is gold. Weight each term by how rare it is: idf(t) = log(N / df(t)), where N is total documents and df(t) is how many contain t.

TF-IDF multiplies the two. It's crude — and it's the reason search "just worked" for decades. The deep insight to keep: rarity is signal. Most of what feels like intelligence in a search engine is IDF quietly ignoring the noise words.

Part 3 — BM25: TF-IDF grown up

BM25 (Best Matching 25, from the Okapi system) fixes TF-IDF's two blind spots and has been the industry-standard lexical ranker for ~25 years:

Saturation (parameter k1, default ≈1.5). Under raw TF, a document saying "chunking" 50 times scores 5× one saying it 10 times. Really 5× more relevant? No — after a few occurrences, you're convinced. BM25 makes the TF contribution level off: tf·(k1+1)/(tf+k1) approaches a ceiling instead of growing forever. Low k1 → saturates fast; high k1 → closer to raw counting.

Length normalization (parameter b, default ≈0.75). Long documents mention everything eventually — raw counting systematically favors them. BM25 scales the score by document length relative to the corpus average. b=1 fully normalizes, b=0 ignores length. The default 0.75 says: penalize length, but not completely.

Together, per term, per document:

score(t, d) = idf(t) · tf(t,d)·(k1+1) / ( tf(t,d) + k1·(1 − b + b·|d|/avg_len) )

Sum over query terms. That one line — readable now, piece by piece — powers more production search than any neural model yet deployed.

Part 4 — Measuring retrieval: the numbers that rule this course

From this week on, no retrieval claim is accepted without measurement. Three metrics, all computed against queries whose relevant documents you've labeled by hand:

For RAG, Recall@k is usually king: if the right chunk isn't in the top-k that enters the context window, nothing downstream can save the answer. MRR matters when the window is tight and order counts. In Week 5 these three grow into a full evaluation discipline — this week they just need to become reflexes.

Lab — build the baseline

All files go in your ragcourse repo from Week 1. We assume your corpus is a folder of .txt/.md files at corpus/ — export/convert your documents into that shape first (plain text is fine; PDFs can wait for a later week).

Step 1 · An inverted index + TF-IDF, from scratch

Create classic_search.py. No libraries — the point is that there's no magic:

import math, re
from pathlib import Path
from collections import Counter, defaultdict

def tokenize(text):
    return re.findall(r"[a-záéíóúüñ0-9]+", text.lower())

class TfIdfIndex:
    def __init__(self, docs):                 # docs: {name: text}
        self.docs = {n: tokenize(t) for n, t in docs.items()}
        self.N = len(self.docs)
        self.index = defaultdict(set)         # term -> {doc names}
        self.tf = {}                          # doc -> Counter(term)
        for name, toks in self.docs.items():
            self.tf[name] = Counter(toks)
            for t in set(toks):
                self.index[t].add(name)

    def idf(self, term):
        df = len(self.index.get(term, ()))
        return math.log(self.N / df) if df else 0.0

    def search(self, query, k=5):
        scores = Counter()
        for t in tokenize(query):
            for doc in self.index.get(t, ()):
                scores[doc] += self.tf[doc][t] * self.idf(t)
        return scores.most_common(k)

if __name__ == "__main__":
    docs = {p.name: p.read_text(errors="ignore")
            for p in Path("corpus").glob("*") if p.suffix in (".txt", ".md")}
    print(f"Indexed {len(docs)} documents")
    ix = TfIdfIndex(docs)
    while True:
        q = input("\nquery> ").strip()
        if not q: break
        for doc, score in ix.search(q):
            print(f"  {score:7.2f}  {doc}")

Run uv run python classic_search.py and interrogate your corpus. Watch the scores: search for a rare domain term, then for a common word, and see IDF doing the work.

Step 2 · Swap in BM25

Create bm25_baseline.py using the library version (which implements the full formula from Part 3):

from pathlib import Path
from rank_bm25 import BM25Okapi
from classic_search import tokenize

docs = {p.name: p.read_text(errors="ignore")
        for p in Path("corpus").glob("*") if p.suffix in (".txt", ".md")}
names = list(docs)
bm25 = BM25Okapi([tokenize(docs[n]) for n in names])

def search(query, k=5):
    scores = bm25.get_scores(tokenize(query))
    ranked = sorted(zip(names, scores), key=lambda x: -x[1])
    return ranked[:k]

if __name__ == "__main__":
    while True:
        q = input("\nquery> ").strip()
        if not q: break
        for doc, score in search(q):
            print(f"  {score:7.2f}  {doc}")

Run the same queries against both engines. Where do the rankings differ? Long documents are the usual culprits — that's length normalization visibly earning its keep.

Step 3 · The golden queries

Create eval_queries.json: 10 realistic queries against your corpus, each with the documents you judge relevant (this hand-labeling is real evaluation work — it will feel slow; it's the most valuable artifact of the week):

[
  {"query": "how do I enroll in the program",
   "relevant": ["enrollment.md", "faq.md"]},
  {"query": "refund and cancellation policy",
   "relevant": ["terms.md"]}
]

Mix easy queries (exact vocabulary from the docs) with hard ones (your own words for the same idea). The hard ones are tomorrow's ammunition.

Step 4 · Score the baseline

Create evaluate.py:

import json
from bm25_baseline import search

queries = json.load(open("eval_queries.json"))
K = 5
recalls, rrs = [], []
for item in queries:
    top = [doc for doc, _ in search(item["query"], k=K)]
    rel = set(item["relevant"])
    recalls.append(len(rel & set(top)) / len(rel))
    rr = 0.0
    for rank, doc in enumerate(top, 1):
        if doc in rel:
            rr = 1 / rank
            break
    rrs.append(rr)
    flag = "  ⚠" if rr == 0 else ""
    print(f"R@{K}={recalls[-1]:.2f}  RR={rr:.2f}  {item['query']}{flag}")

print(f"\nBASELINE — Recall@{K}: {sum(recalls)/len(recalls):.3f}   MRR: {sum(rrs)/len(rrs):.3f}")

Run it, record the two numbers in your README, and commit everything: git commit -m "Week 2: BM25 baseline — R@5=…, MRR=…". These are the numbers to beat for the next six weeks.