TF-IDF and BM25

Elasticsearch holds an index of 50 billion documents and answers in 200 milliseconds. BM25 - an algorithm from 1994 - is still inside. Not because nobody had time to replace it. Because nothing matches it at that scale for speed. BERT processes one document in 10 ms. BM25 does it in microseconds. Understanding why this 30-year-old formula still wins means understanding the architecture of every modern search engine.

• **Elasticsearch** and **Apache Solr** use BM25 as the default ranking algorithm for millions of applications
• **Amazon Product Search** combines BM25 over title, description, and reviews to rank products
• **GitHub Code Search** uses field weighting: a match in the filename weighs more than one in the content

Предварительные знания

• Inverted Index

Robertson and the Birth of BM25

1994. Stephen Robertson and colleagues at City University London publish Okapi BM25 as part of the Okapi system for the TREC competition. BM stands for "Best Match" - a probabilistic ranking model. "25" is the formula's iteration number. Before BM25 came BM1, BM11, BM15 - each version patching problems in the previous one. TF saturation (parameter k1) and length normalization (parameter b) are the key wins over Karen Sparck Jones's 1972 TF-IDF. Thirty years later BM25 still ships as the default in Elasticsearch, Solr, and virtually every search system on the planet.

TF-IDF

Not all words pull equal weight in search. "The" shows up in every English document - it tells nothing about topic. But "quantum" is rare and instantly narrows the field. **TF-IDF** turns this intuition into numbers: a word's weight rises with its frequency in the document (TF) and its rarity across the collection (IDF).

In practice, **smoothed IDF** is the norm: `log(1 + N/df)` - dodges division by zero and tames extreme weights. TF often gets logarithmic scaling too: `1 + log(TF)`, because 10 occurrences of a word are not 10 times more useful than one.

TF-IDF is not one algorithm but a whole **family** of variants. SMART notation captures combinations: `lnc.ltc` means log TF + no IDF + cosine norm for the document, log TF + IDF + cosine norm for the query. Dozens of variants exist.

BM25

TF-IDF has problems: TF grows linearly (a document with a word 100 times gets 100x more weight than one with a single occurrence - wrong). **Okapi BM25** is a probabilistic ranking model that fixes these issues and has stayed the gold standard of search for 30 years.

The **k1** parameter controls TF saturation. At k1 = 0 the weight ignores frequency (binary model). As k1 → ∞ BM25 collapses back to linear TF-IDF. k1 = 1.2 means: the first few occurrences of a word matter, but the 100th barely moves the needle.

The **b** parameter controls document length normalization. b = 0 ignores length. b = 1 hammers long documents. b = 0.75 is the compromise: a long document can still be relevant, but length should not buy an unfair edge by simply containing more words.

Field Weighting

Real documents come structured: title, body, URL, meta description. A word in the **title** signals the document's topic far more loudly than the same word buried in the body. **Field weighting** assigns different weights to different document fields.

**BM25F** (BM25 with Field weighting) is a BM25 extension that computes a weighted sum of TF across fields. In Elasticsearch this is implemented via a **multi_match** query with boost parameters:

**Anchor text** - the text of hyperlinks pointing to a page - is a particularly valuable signal. If 1,000 pages link to a site with the text "best Python course", the site is probably exactly that. Google leans heavily on anchor text for ranking.

Boost coefficients are empirical work. In practice they get tuned through **A/B tests** and **learning to rank**: a model trains on labeled data (query-document pairs with relevance scores) and learns optimal field weights.

Document Length Normalization

A long document carries more words - and statistically more chances that any query word lands inside it. Without normalization, long documents would unfairly dominate the results. **Document length normalization** offsets this effect.

In BM25 the **b** parameter dials the strength of normalization. b = 1 hammers long documents. b = 0 ignores length entirely. Optimal b depends on the collection: homogeneous documents (scientific abstracts) call for lower b; heterogeneous (web) calls for higher.

An alternative: **cosine normalization** (divide the TF-IDF vector by its magnitude). Used in TF-IDF, not in BM25. Another approach - **pivoted document length normalization**: set a "pivot" point; documents shorter than it get a bonus, longer ones take a penalty.

Length normalization is just one piece. Modern systems also factor in **query length** (long queries need different handling), **coordination factor** (bonus for matching more query words), and **proximity** (query words clustering close together in a document is a good signal).

Key Ideas

• **TF-IDF** = frequency in document × rarity in collection: rare words matter more than common ones
• **BM25** solves TF-IDF problems: TF saturation (parameter k1) and length normalization (parameter b)
• **Field weighting** (BM25F): a word in the title is ×5 more important than in the body ×1
• **Retrieve-then-rerank** architecture: BM25 quickly selects top-1000, neural models rerank

Related Topics

TF-IDF and BM25 connect information retrieval with machine learning and NLP:

• Inverted Index — BM25 scores are computed from TF and DF stored in posting lists
• Introduction to Information Retrieval — BM25 is a concrete implementation of the ranking concept from the first lesson

Вопросы для размышления

• Why does BM25 use a saturation constraint on TF instead of linear TF? In what cases would linear TF be better?
• How should the k1 and b parameters be tuned for an online store search engine (products with short descriptions vs reviews)?
• If BERT is so good at understanding meaning, why can't we simply replace BM25 with BERT for all 100B documents?

Связанные уроки

• ir-02 — Inverted index stores TF and DF that BM25 needs
• ir-01 — Core IR concepts: relevance and ranking
• ir-04 — Vector space model and cosine similarity follow from TF-IDF
• aie-13-advanced-rag — Hybrid search in RAG combines BM25 with dense retrieval
• nlp-03 — NLP preprocessing: stemming and stopwords affect TF-IDF quality
• rec-03 — TF-IDF and matrix factorization both extract signal from sparse data
• stat-03-mle