The recording

From probabilistic IDF to BM25

Information Retrieval for AI

Session 4 - Wed 09 Sep 2026

KAIST AI - Seong Joon Oh

Announcements

Groups. Propose your own on the first-day survey by Mon 14 Sep. Remaining places are filled at random after that.
Discussion sessions begin Wed 30 Sep. The first review is due Tue 29 Sep, 18:00.
Recording. Lectures are recorded. Discussion sessions and project workshops are not.

Course syllabus

The roadmap

Build BM25, learn how to use it, then question its limits.

Derive term-frequency saturation and length normalisation.
Inspect BM25 rankings in the live demo.
Choose starting values for k₁ and b, predict their effects in quizzes, and tune them with relevance judgements.
Discuss failures that need more than parameter changes.

We will work through the practical examples as far as the hour allows.

Bayes’ rule, conditional term independence and a shared absence reference gave a score over distinct query terms:

score (d, q) = \sum_{t \in q,t \in d} w_{t}

The per-term weight is the RSJ log odds ratio of presence, where pₜ and uₜ are the probabilities that t is present in relevant and non-relevant documents for this query:

w_{t} = \log \frac{p_{t} (1 - u_{t})}{u_{t} (1 - p_{t})}

With no relevance labels, we set pₜ = 0.5 and estimated uₜ = (df(t) + 0.5)/(N + 1).

{idf}_{RSJ} (t) = \log \frac{1 - u_{t}}{u_{t}} = \log \frac{N - d f (t) + 0.5}{d f (t) + 0.5}

N is the number of documents; df(t) counts those that contain t.

IIR §11.3, pp. 222-227

From presence to frequency

One occurrence and twenty currently receive the same IDF weight. To distinguish them, replace binary presence xₜ with the observed count fₜ.

Keep conditional term independence and the query-term restriction. The same log-evidence construction becomes

U_{t} (f) := \log \frac{P (F_{t} = f ∣ R = 1, q)}{P (F_{t} = f ∣ R = 0, q)}

w_{t} (f) := U_{t} (f) - U_{t} (0)

Sum these contributions over query terms. We now need a model of how repetitions arise to determine the count likelihoods.

First compare equal-length documents; length variation is handled after the count model.

Robertson & Zaragoza (2009), pp. 343-345 and 352-355

Introduce “aboutness”

To model P(Fₜ = f ∣ R, q), there are two ways of explaining term frequency in a document.

Query relevance R gives rise to term frequency Fₜ directly.
Query relevance R first gives rise to “aboutness” Eₜ for each t, which is latent variable determining whether a document is “about” the term t. The term frequency Fₜ is determined by the “aboutness” Eₜ of the term t.

First model is problematic: all relevant documents will have the same term frequency profile. Second model allows for diversified possibilities for term frequencies for each term t, which is more realistic.

Eₜ is a binary RV: Eₜ = 1 means about the term’s concept; Eₜ = 0 means not about it.

Robertson & Zaragoza (2009), pp. 352-356, §§3.4-3.4.2

Quick quiz - aboutness and relevance

A user wants to make a search system respond faster. A tutorial explains retrieval algorithms but contains no information about their speed.

Which description fits this tutorial?

Modelling count given aboutness: a Poisson count model

For each aboutness state e, model a term across L independent token positions, with occurrence probability aₑ. Then, the frequency RV is binomial:

F_{t} ∣ E_{t} = e ~ Binomial (L, a_{e})

For large L and small aₑ with λₑ:=Laₑ fixed, we have

(\binom{L}{f}) a_{e}^{f} (1 - a_{e})^{L - f} \approx e^{- λ_{e}} \frac{λ_{e}^{f}}{f!} .

λ is the expected term count. The two rates are illustrative, with λ₁ > λ₀ > 0.

Unbounded counts and independence across terms approximate fixed-length text.

Robertson & Zaragoza (2009), pp. 354-355, §3.4.1
Further explanation: Poisson refresher and binomial-limit proof (ProbabilityCourse, “Poisson as an approximation for binomial”).

Marginalise out the hidden variable

For one term, suppress its subscript. Let ρᵣ = P(E = 1 ∣ R = r, q).

The law of total probability gives

P (F = f ∣ R = r, q) = \sum_{e \in {0, 1}} P (F = f ∣ E = e, q) P (E = e ∣ R = r, q)

= ρ_{r} Pois (f; λ_{1}) + (1 - ρ_{r}) Pois (f; λ_{0}) .

The two classes share the count components. Their mixture weights ρ₁ and ρ₀ differ.

Robertson & Zaragoza (2009), pp. 353-355, eq. 3.6 and §3.4.1
Further explanation: Why sum over the aboutness states? (ProbabilityCourse, law of total probability with proof and examples).

Factor the mixture likelihood ratio

Recall U(f): the log-likelihood ratio for count f in relevant versus non-relevant documents, for a fixed query q. Substitute the two class mixtures:

U (f) = \log \frac{P (F = f | R = 1, q)}{P (F = f | R = 0, q)} = \log \frac{ρ_{1} Pois (f; λ_{1}) + (1 - ρ_{1}) Pois (f; λ_{0})}{ρ_{0} Pois (f; λ_{1}) + (1 - ρ_{0}) Pois (f; λ_{0})}

Define z(f) = Pois(f; λ₁) / Pois(f; λ₀). The factorial cancels:

z (f) = \frac{e^{- λ_{1}} λ_{1}^{f} / f!}{e^{- λ_{0}} λ_{0}^{f} / f!} = e^{- (λ_{1} - λ_{0})} {(\frac{λ_{1}}{λ_{0}})}^{f} .

Divide both mixtures by Pois(f; λ₀). Then,

U (f) = \log \frac{ρ_{1} z (f) + 1 - ρ_{1}}{ρ_{0} z (f) + 1 - ρ_{0}} .

The zero-referenced weight remains w(f) = U(f) − U(0).

Robertson & Zaragoza (2009), pp. 353-356, §§3.4.1-3.4.2; factored mixture derived here.

Prove that the evidence increases

Assume 0 < ρ₀ < ρ₁ < 1. Since λ₁ > λ₀, z(f) increases with f.

For the ratio inside the logarithm,

\frac{d}{d z} (\frac{ρ_{1} z + 1 - ρ_{1}}{ρ_{0} z + 1 - ρ_{0}}) = \frac{ρ_{1} - ρ_{0}}{(ρ_{0} z + 1 - ρ_{0})^{2}} > 0 .

The logarithm is increasing too. Hence U(f) increases, and subtracting U(0) makes w(f) increase from zero.

The conclusion follows under the stated parameter inequalities.

Robertson & Zaragoza (2009), pp. 355-356, §3.4.2; derivative shown here.
Further explanation: Calculus refresher for the derivative above (Paul’s Online Notes, quotient rule with worked examples).

Take the limit: repetitions have bounded evidence

As f → ∞, z(f) → ∞. Divide the mixture ratio by z(f).

{lim}_{f \to \infty} U (f) = \log \frac{ρ_{1}}{ρ_{0}} .

Therefore the exact limit of the zero-referenced weight is

A = {lim}_{f \to \infty} w (f) = \log \frac{ρ_{1}}{ρ_{0}} - U (0) .

Keep U(0). Zero occurrences do not determine the hidden aboutness state.

If we assume that z(0) is very small, we may write:

A \approx \log \frac{ρ_{1} (1 - ρ_{0})}{ρ_{0} (1 - ρ_{1})} .

Robertson & Zaragoza (2009), pp. 355-356, §3.4.2; exact mixture limit retains the zero-reference term.

Aboutness occurs in both relevance classes

Repeated occurrences increasingly identify the about-term state. That state also occurs in non-relevant documents, so repetitions provide bounded relevance evidence.

Illustrative model: ρ₁ = 0.8, ρ₀ = 0.2, λ₁ = 3, λ₀ = 0.5. The exact limit is A ≈ 2.509.

Original plot, computed from the displayed mixture; Robertson & Zaragoza (2009), pp. 355-356, §3.4.2

Choose a tractable saturation curve

h (f) = \frac{f}{k_{1} + f}, k_{1} > 0 .

It starts at 0, approaches 1, and reaches half-height at f = k₁. Robertson and Zaragoza describe this family as a parametric approximation used in BM25.

Robertson & Zaragoza (2009), pp. 357-358, eq. 3.10; original illustrative plot, same mixture as the preceding slide. k₁ = 1.2 matches the demo setting; it was not fitted to this mixture.

Choose an observable proxy for the amplitude

For term t, pₜ and uₜ are presence probabilities in relevant and non-relevant documents. ρ₁ and ρ₀ are the corresponding latent aboutness probabilities.

Substitute the absence probabilities into the exact saturation limit:

U_{t} (0) = \log \frac{P (F_{t} = 0 ∣ R = 1, q)}{P (F_{t} = 0 ∣ R = 0, q)} = \log \frac{1 - p_{t}}{1 - u_{t}}

A_{t} = \log \frac{ρ_{1}}{ρ_{0}} - U_{t} (0) = \log \frac{ρ_{1} (1 - u_{t})}{ρ_{0} (1 - p_{t})}

Use presence as a proxy for aboutness: ρ₁ ≈ pₜ and ρ₀ ≈ uₜ. This is an additional modelling approximation.

A_{t} \approx \log \frac{p_{t} (1 - u_{t})}{u_{t} (1 - p_{t})} = w_{t}^{RSJ}

Recall the definition: wₜ(f) is the log-likelihood ratio relative to zero occurrences. Then apply the chosen saturation curve and the amplitude proxy:

w_{t} (f) = U_{t} (f) - U_{t} (0) \approx A_{t} \frac{f}{k_{1} + f} \approx w_{t}^{RSJ} \frac{f}{k_{1} + f}

Robertson & Zaragoza (2009), pp. 357-358, eqs. 3.10-3.11; zero-count substitution and proxy steps shown here.

Choose the scale for one occurrence

Choose the scale so one occurrence carries the RSJ weight before length normalisation. Multiply the preceding slide’s term contribution by k₁ + 1:

w_{t}^{RSJ} \frac{(k_{1} + 1) f}{k_{1} + f}

With a fixed k₁ shared across terms, this scale convention preserves document ordering.

Robertson & Zaragoza (2009), p. 361, §3.5.1

What does a longer document mean?

The count model began with equal-length documents. Real documents vary in length.

Interpretation	Thought experiment	Suggested treatment
Verbosity	Say the same thing with twice as many words	Reduce the credit for higher counts
Broader scope	Cover an additional topic in the same document	Retain more of the raw count evidence

Length alone does not identify which explanation applies. BM25 makes an adjustable modelling choice between these endpoints.

Robertson & Zaragoza (2009), pp. 358-359, §3.4.5

Choose a relative-length interpolation

Let dl be the document’s token count and avgdl the collection mean. Define

B_{d} = (1 - b) + b \frac{d l}{a v g d l}, 0 \leq b \leq 1 .

This is a linear interpolation between 1 and relative document length.

b	B_d	Interpretation
0	1	No length adjustment
1	dl / avgdl	Full relative-length adjustment

The linear form is a choice; Bayes’ rule does not determine it.

Robertson & Zaragoza (2009), pp. 359, eq. 3.12

Substitute before saturation

Let g(f) be the length-adjusted frequency factor, with f the raw term count.

g (f) = \frac{(k_{1} + 1) (f / B_{d})}{k_{1} + f / B_{d}} .

Multiply numerator and denominator by B_d.

g (f) = \frac{(k_{1} + 1) f}{k_{1} B_{d} + f} = \frac{(k_{1} + 1) f}{k_{1} (1 - b + b \frac{d l}{a v g d l}) + f} .

This algebra produces BM25’s denominator once the length model is chosen. Saturating first and then dividing by length would give a different function.

Robertson & Zaragoza (2009), pp. 359-360, eqs. 3.12-3.15

Check the substitution at its limits

Setting	B_d	Frequency factor
b = 0	1	(k₁ + 1)f / (k₁ + f)
b = 1	dl / avgdl	(k₁ + 1)f / (k₁ dl/avgdl + f)
dl = avgdl	1, for any b	(k₁ + 1)f / (k₁ + f)

For example, when b = 0.75 and dl = 2 avgdl,

B_{d} = 0.25 + 0.75 \times 2 = 1.75, f / B_{d} = f / 1.75 .

At an average length, one occurrence has multiplier 1. For a longer document with b > 0, it has a smaller multiplier.

Live demo - pad or duplicate a document

Algebraic checks of the preceding definition; example length ratio is illustrative.

Assemble the BM25 score

Sum the frequency-adjusted term weights.

B M 25 (q, d) = \sum_{t \in q} idf (t) \frac{(k_{1} + 1) tf (t, d)}{tf (t, d) + k_{1} (1 - b + b \frac{d l}{a v g d l})} .

Here q denotes distinct query terms, k₁ > 0, and document lengths are positive. Absent terms contribute zero. Query-frequency weighting is a separate variant.

IIR §11.4.3, pp. 232-233; Robertson & Zaragoza (2009), pp. 360, eq. 3.15
Further explanation: BM25 formula and parameter explanation (Introduction to Information Retrieval, online textbook).

Choose the IDF convention used in the demo

The derived RSJ weight is negative when df(t) > N/2 under pₜ = 0.5. The demo chooses the positive variant:

{i d f}_{+} (t) = \log (1 + \frac{N - d f (t) + 0.5}{d f (t) + 0.5})

For N = 10 and df(t) = 8:

Convention	Calculation	Weight
Signed RSJ	log(2.5/8.5)	−1.224
Demo	log(1 + 2.5/8.5)	0.258

The positive variant changes relative term weights, so it can change multi-term rankings. This is an implementation choice beyond the signed derivation.

Live demo - make a query word common

IIR §11.3.3, p. 227; positive convention from the course demo

The score fits the inverted index

Needed by BM25	Stored or computed from the index
Matching documents and tf(t, d)	Term-frequency postings: (docID, count)
df(t)	Number of documents in the term’s postings
dl	One stored length per document
N and avgdl	Collection totals

Visit each query term’s postings and add its contribution. Unvisited documents have score 0. With signed IDF, they can outrank negative-scoring matches; the demo uses positive IDF.

The result is a ranking score. Dropped constants and model approximations mean we cannot read it directly as a calibrated relevance probability.

IIR §7.1, pp. 133-134; Robertson & Zaragoza (2009), pp. 345-346, §2.5

Live demo - TF-IDF and BM25

Scores stay visible as you change the query, term counts or BM25 parameters. The four presets run here.

Open the demo in a full page

Which values do people use?

We have a score. Now choose how strongly it rewards repetition and discounts length.

Starting point	k₁	b
Elasticsearch default; our demo	1.2	0.75
Pyserini published BM25 baseline (2021)	0.9	0.4
IIR textbook’s suggested starting range	1.2-2.0	0.75

Start with your implementation’s documented defaults and record them. A setting used on one collection is a candidate to test on yours.

What matters next: are repetitions useful evidence, and are long documents unfairly favoured or penalised?

Elasticsearch similarity reference

Lin et al., Pyserini (SIGIR 2021), Tables 1-2

IIR §11.4.3, p. 233

k₁ - how much more evidence is another occurrence?

Compare documents of the same length, with b fixed.

What you observe	Direction to test
Repeated template or boilerplate words receive too much credit	Decrease k₁: saturate sooner
Repeated on-topic mentions provide useful evidence that the score underweights	Increase k₁: saturate later

At the average document length, a term’s factor is (k₁ + 1)f / (f + k₁). Lower k₁ reduces the reward for multiple occurrences relative to one.

k₁ = 0 gives each present term its IDF contribution, regardless of its count. It also removes the effect of b.

The direction is a hypothesis about relevance. Confirm it on judged queries.

IIR §11.4.3, p. 233

Quick quiz - repeated words add little value

A one-term query matches two documents at the fixed collection-average length. A contains the term 8 times; B contains it once. Their IDF and length factor are the same.

Assessors say the repetitions add little value. We want to reduce A’s score advantage over B. Start at k₁ = 1.2 and keep b fixed.

Which change should we make?

b - when should extra length count against a document?

Hold the query-term counts, collection statistics and positive k₁ fixed.

What longer documents contain	Direction to test
Extra unrelated text or verbose boilerplate	Increase b to strengthen length normalisation
Useful detail, but relevant long documents lose through the length penalty	Decrease b to weaken length normalisation

b = 0 ignores length. b = 1 uses the full relative-length correction before saturation.

For a matched term, increasing b lowers the contribution for an above-average-length document; it raises it for a below-average one. At exactly average length, b has no effect.

If chunks have nearly equal lengths, b may have little influence. Recheck settings after changing the retrieval unit or chunk sizes.

Elastic, Practical BM25 Part 3 (2018); rules of thumb to test

Quick quiz - unrelated padding

A and B each contain the single query term twice. A has 100 tokens; B has 400 tokens, including unrelated padding. The fixed collection average is 100 tokens.

Keep k₁ = 1.2, query-term counts and IDF fixed. We want to penalise B more relative to A.

From b = 0.5, which direction should we try?

Tune for the task, not for a larger BM25 score

Fix the experiment. Choose document or passage retrieval, tokenisation, query set and collection snapshot. Keep the default run.
Judge relevance on representative development queries. Include different query types and document lengths. Choose a ranking metric and cutoff that fit the task, such as recall at the candidate budget.
Try a joint grid, then refine promising regions. An illustrative coarse grid is k₁ ∈ {0.3, 0.6, 0.9, 1.2, 2.0}, b ∈ {0, 0.25, 0.4, 0.75, 1}.
Inspect gains and regressions by query. Prefer a stable region to an isolated peak. Lock the choice and evaluate on held-out queries; with few judgements, use cross-validation within development data.

Raw BM25 scores change scale with parameters. Optimise judged ranking quality. Without labels, keep a documented baseline and collect judgements before claiming an improvement.

IIR §11.4.3, p. 233

Elastic, Practical BM25 Part 3; grid and protocol here are teaching recommendations

What is wrong with BM25’s view of meaning?

Assume plain unigram BM25, with no synonym expansion, phrase features or filters. These are constructed examples.

User need and candidate	What the score misses
Query `car repair`; document `automobile maintenance`	No shared tokens, despite related meaning
Query `dog bites man`; documents `dog bites man` and `man bites dog`	Same term counts and length, opposite roles
Need a laptop under 1 kg; document describes a 1.4 kg laptop	A numeric requirement needs a comparison, beyond word matching

Discussion: can any choice of k₁ or b fix each example? What representation, query operation or constraint would we need to add?

A search system can add these capabilities around BM25. The term-weighting formula itself does not provide them.

What is missing when retrieval serves an AI task?

The score uses word counts, document frequencies and length. Consider needs that depend on something else.

Current evidence: two equally matching policy pages disagree. One is obsolete. Where should validity dates enter the decision?
Reliable evidence: an official notice and an unsupported repost match the same words. What evidence of authority do we need?
Sufficient evidence: the top results repeat the same fact, but the answer requires a second fact from another document. How should we assess the retrieved set?

Pick one case. Propose a change, then say what you would measure to show that it helps.

BM25 provides a lexical relevance signal. Parameter tuning cannot by itself establish freshness, authority or whether a set of documents supports the answer.

Thank you

Questions and feedback

Course materials - irai.stai-lab.org

Group formation - First-day survey, by Mon 14 Sep

The recording

From probabilistic IDF to BM25

Information Retrieval for AI

Announcements

The roadmap

From presence to frequency

Introduce “aboutness”

Quick quiz - aboutness and relevance

Modelling count given aboutness: a Poisson count model

Marginalise out the hidden variable

Factor the mixture likelihood ratio

Prove that the evidence increases

Take the limit: repetitions have bounded evidence

Aboutness occurs in both relevance classes

Choose a tractable saturation curve

Choose an observable proxy for the amplitude

Choose the scale for one occurrence

What does a longer document mean?

Choose a relative-length interpolation

Substitute before saturation

Check the substitution at its limits

Assemble the BM25 score

Choose the IDF convention used in the demo

The score fits the inverted index

Live demo - TF-IDF and BM25

Which values do people use?

k₁ - how much more evidence is another occurrence?

Quick quiz - repeated words add little value

b - when should extra length count against a document?

Quick quiz - unrelated padding

Tune for the task, not for a larger BM25 score

What is wrong with BM25’s view of meaning?

What is missing when retrieval serves an AI task?

Thank you

Feedback