Chapter 3 of 10
Lexical retrieval and BM25 from first principles
Formal model
About 4 minutes · includes examples, an exercise, and references
Chapter at a glance
- •BM25 combines inverse document frequency, saturated term frequency, and length normalization.
- •Tokenization and field design are part of the retrieval model.
- •Raw BM25 scores are implementation-specific ranking signals, not calibrated probabilities.
Lexical retrieval represents documents through terms and answers a query by locating documents that contain those terms. Its central data structure is the inverted index: for each term, store a postings list of document identities and term statistics. Query evaluation touches postings for query terms rather than scanning the corpus. This makes exact terms, names, codes, and phrases cheap to retrieve and makes score contributions inspectable.
The simplest ranking signal is term frequency, but repeating a word indefinitely should not increase relevance linearly. Common words should also contribute less than rare discriminative words. BM25 combines saturating term frequency, inverse document frequency, and document-length normalization. A common single-field form scores document d for query q by summing over query terms t:
score(d,q) = Σ IDF(t) × tf(t,d)(k1 + 1) / [tf(t,d) + k1(1 - b + b|d|/avgdl)].
The parameter k1 controls how quickly term frequency saturates. The parameter b controls length normalization: zero ignores length and one applies the full document-to-average ratio. Implementations differ in inverse-document-frequency smoothing and treatment of negative values, so scores are not portable probabilities. Rank behavior and evaluation matter more than comparing raw scores across engines.
An inverted index needs a defined analyzer. Tokenization identifies terms; normalization may case-fold or normalize Unicode; optional stemming maps inflections; stopword policies may remove frequent function words. Phrase and proximity search require positions in postings. Fielded retrieval usually maintains separate statistics for title, heading, body, code, and tags, then combines weighted field scores. BM25F extends the idea across fields with field-specific boosts and length behavior.
Query parsing should preserve intent. Quoted text can become a phrase clause. Identifiers such as HTTP_429, CVE-2026-1234, and dotted package names need analyzer rules that retain useful forms. Boolean filters enforce tenant, time, language, or version constraints. Synonyms can expand recall but also create false matches; version them and test by query slice. A learned sparse model such as SPLADE predicts weighted vocabulary dimensions, providing expansion while retaining an inverted-index-compatible representation, but it adds model and calibration complexity.
The runnable implementation below deliberately scans documents so the scoring equation is visible. A production engine instead constructs postings, document frequencies, lengths, and field statistics during indexing. Still, the small implementation exposes important invariants: document frequency counts documents, not occurrences; repeated query terms need an explicit policy; empty documents are handled; and tokenization is part of the model.
BM25 failure modes are predictable. Vocabulary mismatch causes misses when the query and document use different words. Very short fields can dominate if boosted excessively. Boilerplate terms can inflate many documents. Long documents containing several unrelated sections can receive diluted scores. Rare typos may look highly discriminative. Exact matching can also overvalue a copied query phrase in an irrelevant context. Dense retrieval and reranking can address some failures, while better corpus units and analyzers address others.
Debug lexical ranking with contribution traces. For each result, expose which query terms matched, document and collection frequencies, field, term-frequency factor, length factor, filter outcome, and phrase match. Compare a missed relevant document with an incorrectly high result. If the relevant document never entered the candidate set, inspect analysis and filters. If it entered but ranked poorly, inspect field boosts and score contribution. Do not change k1 and b blindly on a handful of examples; tune on a representative judged set and confirm critical slices.
Lexical retrieval remains a strong baseline because it is fast, transparent, update-friendly, and difficult to beat on exact entities. Hybrid search should earn its additional complexity by measuring rescued relevant results. Keep the lexical component independently observable so an embedding or model upgrade cannot hide regression on identifiers and phrases.
Key points
- BM25 combines inverse document frequency, saturated term frequency, and length normalization.
- Tokenization and field design are part of the retrieval model.
- Raw BM25 scores are implementation-specific ranking signals, not calibrated probabilities.
- Contribution traces make lexical misses and ranking errors diagnosable.
A runnable BM25 scorer
Read the expected behavior in the surrounding walkthrough, then copy and run this reference implementation.
import math, re
from collections import Counter
def tokens(text):
return re.findall(r"[a-z0-9_]+", text.lower())
def bm25(query, documents, k1=1.2, b=0.75):
docs = [tokens(d) for d in documents]
avgdl = sum(map(len, docs)) / max(len(docs), 1)
df = Counter(term for doc in docs for term in set(doc))
scores = []
for i, doc in enumerate(docs):
counts = Counter(doc)
score = 0.0
for term in tokens(query):
n = df[term]
idf = math.log(1 + (len(docs) - n + 0.5) / (n + 0.5))
tf = counts[term]
denom = tf + k1 * (1 - b + b * len(doc) / max(avgdl, 1))
score += idf * tf * (k1 + 1) / denom if tf else 0.0
scores.append((score, i, documents[i]))
return sorted(scores, reverse=True)
corpus = ["retry HTTP_429 twice", "authentication token expiry", "rate limits and retries"]
for row in bm25("HTTP_429 retry", corpus): print(row)Exercise
Diagnose lexical ranking
Build a small BM25 experiment for support articles containing codes, prose, and version labels.
- Implement token contribution reporting and phrase-aware analysis.
- Evaluate at least three slices: exact code, paraphrase, and version-constrained queries.
- Vary unit boundaries, k1, b, and title weight one factor at a time.
Success criteria
- Document frequency and length statistics are computed correctly.
- Every rank change can be explained through a recorded treatment.
- The report identifies misses that parameter tuning cannot solve.
Reflect: Which query type should lexical retrieval dominate in your corpus?