TF-IDF and BM25 From Scratch: Searching Our Own Blog

This is for developers who want to understand what sits under "search" before reaching for embeddings and RAG, and who would rather measure it on their own documents than read about it. We built a search engine over this blog's own posts (86 per language, in English, Japanese and Korean) using only the Python 3.9 standard library: an inverted index, TF-IDF with cosine similarity, and BM25. BM25 found the right post in the top 3 for every one of our 60 labelled queries, answered in under 0.1 ms (median), and fell apart in a predictable way when the query used different words from the post.

This is lecture 5 of Machine learning from scratch (Python stdlib only), and it is the bridge to retrieval-augmented generation. The earlier lectures fitted a line with gradient descent, grouped points with k-means, classified text with Naive Bayes and trained a perceptron and a small neural network. Naive Bayes counted words to pick a label. Here the same word counts pick a document.

Environment: Python 3.9.6 standard library only, Apple Silicon Mac (M1 Pro). Nothing was installed and no model was downloaded. The corpus is a snapshot of the blog's Markdown files taken on 2026-11-11, before this series was added.

Why keyword search comes before embeddings and RAG

A RAG system has two halves: find the passages, then let a language model write from them. The first half is retrieval, and retrieval is older than neural networks. Three reasons to build keyword search first:

1. It is the baseline. If an embedding model cannot beat BM25 on your queries, it is not earning its cost. You cannot know that without a BM25 number.
2. It is exact where embeddings blur. Developers paste error codes and identifiers: CS8509, WM_COPYDATA, max_connections_per_hour, exit code 139. To a keyword index those are rare, high-weight tokens. To an embedding model they are a handful of sub-word pieces that may land near other error codes.
3. It is the keyword half of hybrid search. Most production RAG stacks run BM25 and a vector search side by side and merge the two ranked lists. You need the first half either way.

We do not implement embeddings here. They need a pretrained model, and model downloads were off the table for this series. The decision table near the end covers when to add them.

Step 1: an inverted index

A naive search reads every document for every query. An inverted index turns that around: for each term, store the documents that contain it and how often. A query then touches only the posting lists of its own terms.

The whole engine is one file. load_posts keeps the title and description from the front matter and drops the rest (dates, tags), then appends the body, code blocks included, because code is where identifiers live.

# search.py - inverted index + TF-IDF (cosine) + BM25, Python standard library only
import math, re, sys, unicodedata
from collections import Counter, defaultdict
from pathlib import Path

WORD = re.compile(r"[a-z0-9_]+|[぀-ヿ㐀-鿿가-힯]+")

def tok_bigram(text):
    """Latin/digit runs become words; CJK/Hangul runs become character bigrams."""
    out = []
    for w in WORD.findall(unicodedata.normalize("NFKC", text).lower()):
        if w[0] < "぀":
            out.append(w)
        elif len(w) == 1:
            out.append(w)
        else:
            out.extend(w[i:i + 2] for i in range(len(w) - 1))
    return out

def tok_space(text):
    """The naive tokenizer: lowercase and split on whitespace."""
    return unicodedata.normalize("NFKC", text).lower().split()

def load_posts(folder):
    """Return {slug: (title, text)}; front matter is dropped except title and description."""
    posts = {}
    for p in sorted(Path(folder).glob("*.md")):
        raw = p.read_text(encoding="utf-8")
        _, fm, body = raw.split("---", 2)
        meta = dict(re.findall(r"^(title|description): *['\"]?(.*?)['\"]?$", fm, re.M))
        posts[p.stem] = (meta["title"], meta["title"] + "\n" + meta.get("description", "") + "\n" + body)
    return posts

class Index:
    def __init__(self, docs, tokenize=tok_bigram):
        self.tokenize = tokenize
        self.ids = list(docs)
        self.postings = defaultdict(dict)            # term -> {doc number: term frequency}
        self.length = []                             # tokens per document
        for n, slug in enumerate(self.ids):
            tf = Counter(tokenize(docs[slug]))
            self.length.append(sum(tf.values()))
            for term, c in tf.items():
                self.postings[term][n] = c
        self.N = len(self.ids)
        self.avgdl = sum(self.length) / self.N
        # TF-IDF document vector norms, computed once at build time
        self.norm = [0.0] * self.N
        for term, plist in self.postings.items():
            idf = math.log(self.N / len(plist))
            for n, c in plist.items():
                self.norm[n] += ((1 + math.log(c)) * idf) ** 2
        self.norm = [math.sqrt(x) or 1.0 for x in self.norm]

    def tfidf(self, query, k=10):
        q = Counter(t for t in self.tokenize(query) if t in self.postings)
        scores = defaultdict(float)
        for term, qc in q.items():
            plist = self.postings[term]
            idf = math.log(self.N / len(plist))
            wq = (1 + math.log(qc)) * idf
            for n, c in plist.items():
                scores[n] += wq * (1 + math.log(c)) * idf
        qn = math.sqrt(sum(((1 + math.log(c)) * math.log(self.N / len(self.postings[t]))) ** 2
                           for t, c in q.items())) or 1.0
        return self._top({n: s / (self.norm[n] * qn) for n, s in scores.items()}, k)

    def bm25(self, query, k=10, k1=1.2, b=0.75):
        scores = defaultdict(float)
        for term in set(self.tokenize(query)):
            plist = self.postings.get(term)
            if not plist:
                continue
            df = len(plist)
            idf = math.log(1 + (self.N - df + 0.5) / (df + 0.5))
            for n, c in plist.items():
                norm = k1 * (1 - b + b * self.length[n] / self.avgdl)
                scores[n] += idf * c * (k1 + 1) / (c + norm)
        return self._top(scores, k)

    def _top(self, scores, k):
        best = sorted((x for x in scores.items() if x[1] > 0), key=lambda x: -x[1])[:k]
        return [(self.ids[n], round(s, 3)) for n, s in best]

if __name__ == "__main__":
    folder, query = sys.argv[1], " ".join(sys.argv[2:])
    posts = load_posts(folder)
    idx = Index({s: t for s, (_, t) in posts.items()})
    for name, hits in (("TF-IDF", idx.tfidf(query, 3)), ("BM25", idx.bm25(query, 3))):
        print(name)
        for slug, s in hits:
            print(f"  {s:7.3f}  {posts[slug][0]}")

The index is just dict[str, dict[int, int]]. For the English posts it holds 8,412 distinct terms and 47,875 postings, so the average term appears in about 6 of the 86 posts. That sparsity is the reason an inverted index is fast.

Step 2: TF-IDF with cosine similarity

TF-IDF gives each term in a document a weight of (1 + log tf) × log(N / df):

• tf (term frequency) is the count of the term in the document. The logarithm stops a word that appears 30 times from counting 30 times as much as one that appears once.
• df (document frequency) is how many documents contain the term. log(N / df) is zero for a term in every post and large for a rare one. That is the whole trick: the and です weigh nothing, wm_copydata weighs a lot.

The query gets the same treatment, and the score is the cosine of the angle between the two weight vectors. Dividing by the vector lengths (computed once at build time, in self.norm) stops long posts from winning just by containing more words. The dot product only needs terms the query and the document share, which is exactly what the posting lists hand us.

Step 3: BM25, and what k1 and b actually do

BM25 keeps the idea and changes two things. Its idf is log(1 + (N − df + 0.5) / (df + 0.5)), which behaves like TF-IDF's but never goes negative. The bigger change is in how term counts and document length enter:

score += idf × tf × (k1 + 1) / (tf + k1 × (1 − b + b × doclen / avgdoclen))

k1 controls saturation: how quickly extra occurrences stop adding score. knobs.py prints the per-term contribution in a document of average length as tf grows, next to TF-IDF's 1 + log(tf):

# knobs.py - what k1 and b actually do
import math, sys
from search import Index, load_posts

# 1) k1: contribution of one term as its count grows, in a document of average length (idf left out)
print("tf   " + "  ".join(f"k1={k1:<4}" for k1 in (0.3, 1.2, 3.0)) + "  TF-IDF 1+log(tf)")
for tf in (1, 2, 5, 10, 30):
    row = [tf * (k1 + 1) / (tf + k1) for k1 in (0.3, 1.2, 3.0)]
    print(f"{tf:<4} " + "  ".join(f"{v:7.2f}" for v in row) + f"  {1 + math.log(tf):7.2f}")

# 2) b: the same query with length normalisation off, default and full
folder, query = sys.argv[1], " ".join(sys.argv[2:])
posts = load_posts(folder)
idx = Index({s: t for s, (_, t) in posts.items()})
length = dict(zip(idx.ids, idx.length))
print(f"\nquery: {query}   (average length {idx.avgdl:.0f} tokens)")
for b in (0.0, 0.75, 1.0):
    print(f"b={b}")
    for slug, s in idx.bm25(query, 3, 1.2, b):
        print(f"  {s:6.2f}  {length[slug]:5} tokens  {slug}")

$ python3 knobs.py content/en mobile apps keep getting stale data after a deploy
tf   k1=0.3   k1=1.2   k1=3.0   TF-IDF 1+log(tf)
1       1.00     1.00     1.00     1.00
2       1.13     1.38     1.60     1.69
5       1.23     1.77     2.50     2.61
10      1.26     1.96     3.08     3.30
30      1.29     2.12     3.64     4.40

query: mobile apps keep getting stale data after a deploy   (average length 1777 tokens)
b=0.0
    9.77   1755 tokens  legacy-php-sqli-xss-audit-byte-identical
    9.26   1535 tokens  remove-wordpress-files-safely-410
    8.53   1193 tokens  admob-remote-ad-config-server
b=0.75
    9.80   1755 tokens  legacy-php-sqli-xss-audit-byte-identical
    9.57   1535 tokens  remove-wordpress-files-safely-410
    9.47   1193 tokens  admob-remote-ad-config-server
b=1.0
    9.92    941 tokens  cdn-caches-api-responses-and-redirects
    9.84   1193 tokens  admob-remote-ad-config-server
    9.80   1755 tokens  legacy-php-sqli-xss-audit-byte-identical

With k1 = 0.3, the 30th occurrence of a word is worth barely more than the first (1.29 vs 1.00). With k1 = 3.0 it behaves almost like TF-IDF. The usual default, 1.2, sits between.

b controls length normalisation. At b = 0 a document's length is ignored; at b = 1 the count is fully scaled by length relative to the average. The query above describes the CDN caching post without using its words. That post is our second-shortest English post (941 tokens against an average of 1,777). At b = 0 it is rank 7 and at the default 0.75 rank 4. At b = 1 its few matching words count for more because the post is short, and it moves to rank 1. Length normalisation can also push a long relevant post down, which is why b is a dial and not a switch.

Should you tune them? We swept k1 × b over all 28 queries per language (20 labelled and 8 paraphrased, explained below):

# sweep.py - how k1 and b change MRR@10 (labelled + paraphrase queries)
import sys
from search import Index, load_posts
from queries import QUERIES, PARAPHRASE
from evaluate import metrics

root = sys.argv[1]
K1 = (0.3, 0.6, 0.9, 1.2, 1.5, 2.0, 3.0)
B = (0.0, 0.25, 0.5, 0.75, 1.0)
for lang in ("en", "ja", "ko"):
    posts = load_posts(f"{root}/{lang}")
    idx = Index({s: t for s, (_, t) in posts.items()})
    qs = QUERIES[lang] + PARAPHRASE[lang]
    print(f"[{lang}] MRR@10, n={len(qs)}   b=" + "  ".join(f"{b:5}" for b in B))
    for k1 in K1:
        row = [metrics(lambda q: idx.bm25(q, 10, k1, b), qs)[0] for b in B]
        print(f"  k1={k1:<4}" + " " * 17 + "  ".join(f"{m:.3f}" for m in row))

$ python3 sweep.py content
[en] MRR@10, n=28   b=  0.0   0.25    0.5   0.75    1.0
  k1=0.3                  0.899  0.904  0.910  0.910  0.928
  …
  k1=1.2                  0.901  0.903  0.905  0.905  0.932
  …
  k1=3.0                  0.905  0.909  0.910  0.908  0.905
[ja] MRR@10, n=28   b=  0.0   0.25    0.5   0.75    1.0
  k1=0.3                  0.777  0.777  0.795  0.789  0.789
  …
  k1=1.2                  0.830  0.830  0.848  0.848  0.834
  …
  k1=3.0                  0.812  0.812  0.807  0.824  0.828
[ko] MRR@10, n=28   b=  0.0   0.25    0.5   0.75    1.0
  k1=0.3                  0.827  0.851  0.833  0.851  0.833
  …
  k1=1.2                  0.820  0.819  0.821  0.860  0.863
  …
  k1=3.0                  0.808  0.830  0.854  0.858  0.858

The whole grid spans 0.899–0.932 in English, 0.777–0.848 in Japanese and 0.808–0.869 in Korean. With 28 queries, one query moving from rank 1 to rank 2 changes MRR by 0.018, so most of these differences are one or two queries. The default k1 = 1.2, b = 0.75 was best or within 0.03 of best in every language. With a query set this small, tuning k1 and b fits the queries, not the problem. Keep the defaults until you have hundreds of judged queries.

Japanese and Korean without a tokenizer library

English has spaces between words. Japanese does not, and a whitespace split turns a whole sentence into one token. We counted the whitespace tokens in the Japanese posts that contain 後方参照 (backreference), then ran the same query through both tokenizers:

# tokdemo.py - whitespace tokens vs character bigrams on real posts
import sys
from collections import Counter
from search import Index, load_posts, tok_bigram, tok_space

folder, word, query = sys.argv[1], sys.argv[2], sys.argv[3]
posts = load_posts(folder)
docs = {s: t for s, (_, t) in posts.items()}
forms = Counter(t for text in docs.values() for t in tok_space(text) if word in t)
print(f"whitespace tokens containing {word!r}: {len(forms)} distinct forms")
for t, c in forms.most_common(5):
    print(f"  {c:3}  {t[:40]}")
for name, tok in (("whitespace", tok_space), ("bigram", tok_bigram)):
    idx = Index(docs, tok)
    print(f"{name}: {tok(query)}")
    for slug, s in idx.bm25(query, 3) or [("(no results)", 0)]:
        print(f"  {s:6.2f}  {slug}")

$ python3 tokdemo.py content/ja 後方参照 "正規表現 後方参照"
whitespace tokens containing '後方参照': 26 distinct forms
    1  正規表現の後方参照\\1:.net・python・php・jsで検証
    1  正規表現の後方参照(\\1、\\k<name>)を.net・python・php
    1  regexp)で、同じ入力のまま実行し直しました。2つの例のマッチ結果はどのエン
    1  に移したら後方参照の書き方で詰まった人向けの記事です。先に結論を書くと、後方参照
    1  後方参照:グループが捕まえた文字列をもう一度探す
whitespace: ['正規表現', '後方参照']
    0.00  (no results)
bigram: ['正規', '規表', '表現', '後方', '方参', '参照']
   20.77  regex-what-is-regular-expression
   20.77  regex-backreferences
   18.75  regex-repeated-characters

The word appears in 26 different whitespace "tokens", each a fragment of a sentence, and none of them is the bare word. The query finds nothing at all, although the regex backreferences post is about exactly that.

Character bigrams avoid the problem without a dictionary: every run of kana, kanji or Hangul becomes its overlapping two-character windows, so 後方参照 becomes 後方 / 方参 / 参照, and the same windows appear inside every sentence that contains the word. The cost is noise (方参 is not a word) and a bigger index: the Japanese index has 21,457 terms and 114,836 postings, against 8,412 and 47,875 for English. A morphological analyser such as MeCab gives cleaner tokens, but it is a dependency with a dictionary, and for a blog-sized corpus bigrams were enough.

Korean puts spaces between phrases, but particles attach to the noun: 방침은, 방침을. Whitespace splitting mostly worked on our labelled Korean queries; it failed where the post only ever used an inflected form. The Japanese and Korean articles of this lecture walk through that case.

Exact error codes and identifiers

This is where keyword search earns its place in a RAG stack. The tokenizer keeps [a-z0-9_]+ together, so identifiers survive as single rare terms:

$ python3 search.py content/en WM_COPYDATA
TF-IDF
    0.172  SendMessage vs PostMessage: Timeouts and WM_COPYDATA
BM25
    8.351  SendMessage vs PostMessage: Timeouts and WM_COPYDATA

$ python3 search.py content/en "exit code 139"
TF-IDF
    0.063  Bubble, Insertion and Quick Sort in C, Measured
    0.062  Tree Traversal in C++: When Recursion Overflows
    0.059  DFS in C++ and C#: Recursion Limits, Cycles, Topo Sort
BM25
    5.824  Bubble, Insertion and Quick Sort in C, Measured
    5.741  DFS in C++ and C#: Recursion Limits, Cycles, Topo Sort
    5.513  Tree Traversal in C++: When Recursion Overflows

WM_COPYDATA occurs in one post, so there is exactly one result. exit code 139 (a segfault, here from stack overflow) brings up the sorting post, where quicksort crashed on sorted input, followed by the two posts about recursion depth. All three are reasonable answers.

Evaluation: a labelled query set, and its bias

A search engine without a measured query set is a demo. We wrote 20 queries per language, each with exactly one post that counts as correct, plus 8 harder "paraphrase" queries per language:

# queries.py (excerpt) - (query, the one slug that counts as the right answer)
QUERIES = {
"en": [
    ("mysql error 1226 too many connections per hour", "mysql-max-connections-per-hour-shared-hosting"),
    ("quicksort stack overflow on sorted input", "algorithm-sorting"),
    ("CS8509 switch expression not exhaustive", "csharp-if-else-switch"),
    ("WM_COPYDATA send a string to another process", "winapi-sendmessage"),
    …
],
PARAPHRASE = {
"en": [
    ("database refuses logins after too many in an hour", "mysql-max-connections-per-hour-shared-hosting"),
    ("mobile apps keep getting stale data after a deploy", "cdn-caches-api-responses-and-redirects"),
    ("keep only one copy of my desktop program running", "winforms-single-instance-form"),
    …

How they were made, and why that matters:

• We wrote the queries while looking at the post titles. The labelled set therefore shares a lot of vocabulary with the right answer. That is close to how people search for a known error message, but it flatters any keyword method. That is why the scores are above 0.9.
• The paraphrase set deliberately avoids the title's words, describing the symptom instead ("stale data" for a post about CDN caching). It is closer to a user who does not know the term yet. It is also small (8 per language), so one query is 0.125 of recall.
• One relevant post per query. Several queries have two defensible answers (二分探索 matches both the binary search post and the linear-vs-binary-search post), and we score only one. That understates every method a little.
• Japanese and Korean queries were written for those posts, not translated from the English list, so the three languages are not directly comparable.

We report MRR@10 (mean of 1/rank of the right post, 0 if it is not in the top 10) and recall@3 (share of queries whose right post is in the top 3).

# evaluate.py - MRR@10 and recall@3 for TF-IDF vs BM25, plus build/query cost
import pickle, statistics, sys, time
from search import Index, load_posts, tok_space
from queries import QUERIES, PARAPHRASE

def metrics(rank_fn, qs):
    rr, hit3, ranks = 0.0, 0, []
    for q, want in qs:
        ids = [s for s, _ in rank_fn(q)]          # top 10
        r = ids.index(want) + 1 if want in ids else None
        ranks.append(r)
        rr += 1 / r if r else 0
        hit3 += bool(r and r <= 3)
    return rr / len(qs), hit3 / len(qs), ranks

def main(root):
    for lang in ("en", "ja", "ko"):
        posts = load_posts(f"{root}/{lang}")
        docs = {s: t for s, (_, t) in posts.items()}
        builds = []
        for _ in range(5):
            t0 = time.perf_counter(); idx = Index(docs); builds.append(time.perf_counter() - t0)
        size = len(pickle.dumps((dict(idx.postings), idx.length, idx.norm)))
        npost = sum(len(p) for p in idx.postings.values())
        print(f"[{lang}] docs={idx.N} chars={sum(map(len, docs.values())):,} terms={len(idx.postings):,} "
              f"postings={npost:,} pickle={size/1024:.0f}KiB build={statistics.median(builds)*1000:.0f}ms")
        ws = Index(docs, tok_space)
        for setname, qs in (("labelled", QUERIES[lang]), ("paraphrase", PARAPHRASE[lang])):
            for name, fn in (("TF-IDF", idx.tfidf), ("BM25", idx.bm25), ("BM25/space", ws.bm25)):
                mrr, r3, ranks = metrics(fn, qs)
                print(f"  {setname:10} {name:10} MRR@10={mrr:.3f} recall@3={r3:.2f} ranks={ranks}")
        for name, fn in (("TF-IDF", idx.tfidf), ("BM25", idx.bm25)):
            lat = []
            for _ in range(20):
                for q, _ in QUERIES[lang] + PARAPHRASE[lang]:
                    t0 = time.perf_counter(); fn(q); lat.append(time.perf_counter() - t0)
            lat.sort()
            print(f"  latency {name:6} median={statistics.median(lat)*1000:.3f}ms "
                  f"p95={lat[int(len(lat) * .95)]*1000:.3f}ms (n={len(lat)})")

if __name__ == "__main__":
    main(sys.argv[1])

$ python3 evaluate.py content
[en] docs=86 chars=967,286 terms=8,412 postings=47,875 pickle=301KiB build=76ms
  labelled   TF-IDF     MRR@10=0.933 recall@3=1.00 ranks=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1]
  labelled   BM25       MRR@10=0.942 recall@3=1.00 ranks=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1]
  labelled   BM25/space MRR@10=0.942 recall@3=1.00 ranks=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1]
  paraphrase TF-IDF     MRR@10=0.806 recall@3=0.75 ranks=[1, 1, 4, 5, 1, 1, 1, 1]
  paraphrase BM25       MRR@10=0.812 recall@3=0.75 ranks=[1, 1, 4, 4, 1, 1, 1, 1]
  paraphrase BM25/space MRR@10=0.781 recall@3=0.88 ranks=[1, 1, 4, 2, 2, 1, 1, 1]
  latency TF-IDF median=0.078ms p95=0.143ms (n=560)
  latency BM25   median=0.086ms p95=0.195ms (n=560)
[ja] docs=86 chars=676,624 terms=21,457 postings=114,836 pickle=717KiB build=166ms
  labelled   TF-IDF     MRR@10=0.942 recall@3=1.00 ranks=[1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  labelled   BM25       MRR@10=0.975 recall@3=1.00 ranks=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  labelled   BM25/space MRR@10=0.338 recall@3=0.35 ranks=[1, 1, 1, 1, None, None, None, None, None, None, 1, None, 4, None, None, 2, None, 1, None, None]
  paraphrase TF-IDF     MRR@10=0.521 recall@3=0.50 ranks=[1, 6, None, None, 1, 1, 1, None]
  paraphrase BM25       MRR@10=0.531 recall@3=0.50 ranks=[1, 4, None, None, 1, 1, 1, None]
  paraphrase BM25/space MRR@10=0.000 recall@3=0.00 ranks=[None, None, None, None, None, None, None, None]
  …
[ko] docs=86 chars=699,588 terms=13,818 postings=78,244 pickle=480KiB build=118ms
  labelled   TF-IDF     MRR@10=0.925 recall@3=1.00 ranks=[1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1]
  labelled   BM25       MRR@10=0.967 recall@3=1.00 ranks=[1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  labelled   BM25/space MRR@10=0.933 recall@3=0.95 ranks=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 1, 1, 1, 1]
  paraphrase TF-IDF     MRR@10=0.557 recall@3=0.50 ranks=[1, 1, 8, 6, None, 1, 1, 6]
  paraphrase BM25       MRR@10=0.594 recall@3=0.50 ranks=[1, 1, 4, 4, None, 1, 1, 4]
  paraphrase BM25/space MRR@10=0.420 recall@3=0.38 ranks=[1, 4, None, None, None, 1, 1, 9]
  …

What the numbers say:

• BM25 beats TF-IDF in every row, by a little. The gain is a few queries moving from rank 2 or 3 to rank 1. Recall@3 is identical (1.00) on the labelled sets.
• Paraphrase is the real weakness. English drops from 0.942 to 0.812, Japanese from 0.975 to 0.531, Korean from 0.967 to 0.594. In Japanese, 3 of 8 paraphrased queries never reached the top 10. One of them, "アプリに古いデータが返る" (the app gets old data), never says キャッシュ (cache), so the CDN post has almost nothing to match. This is the gap embeddings are for.
• Whitespace tokens destroy Japanese (0.338 labelled, 0.000 paraphrase) and cost Korean on paraphrases (0.420 vs 0.594). English whitespace splitting scored the same as our regex tokenizer on the labelled set and even reached a higher recall@3 on paraphrases (0.88 vs 0.75), so do not assume your tokenizer is better without measuring it.

Cost: build time, index size, query latency

Build time includes tokenizing every post; it does not include reading the files. Latency is measured over 560 queries per language (28 queries × 20 rounds) on an M1 Pro. At this size the index is a few hundred kilobytes and queries take less than a millisecond in pure Python. The Japanese index is 2.4× the English one because bigrams generate more distinct terms. For a static blog, that is small enough to export as JSON and search in the browser.

BM25 vs embeddings vs hybrid: when to use which

Rule of thumb: start with BM25, measure it on queries you labelled, then add embeddings only when the misses look like our paraphrase misses.

Honest limits

• The query set is small and written by the same people who wrote the posts. 28 queries per language is enough to show large effects (whitespace vs bigrams in Japanese) and too few to rank close ones (TF-IDF vs BM25, or k1/b settings). The labelled half is biased toward title words.
• One relevant document per query understates every method when two posts are both right.
• Bigrams are noisy. They match across word boundaries and cannot tell 京都 (Kyoto) inside 東京都 (Tokyo Metropolis) from the real city. A morphological analyser fixes that at the cost of a dependency.
• No stemming, no synonyms, no spelling correction. "redirect" does not match "redirects"; "stale" does not match "cache".
• Whole posts are the unit. For RAG you would index passages of a few hundred tokens, so the length statistics, and the best b, would change.
• Timings are for one machine and an in-memory index in CPython 3.9; they exclude file reading and say nothing about a corpus of millions of documents, where you would use a real search engine.

What comes next

The lecture series stops here, at the point where RAG starts. A retriever like this one returns the top passages; a language model then answers from them, and the hybrid version adds an embedding search and merges the two lists. Whatever you add, keep evaluate.py: the labelled queries are what tell you whether the new component actually helps on your documents.

Earlier lectures: linear regression, k-means, Naive Bayes, perceptron to neural network. If the posting lists remind you of binary search and trees, that is where large search engines go next: sorted, compressed postings instead of Python dicts.