The librarian does not count every word equally

A reader asks for “the apple pie.” Imagine a librarian hearing the words one at a time.

• the appears in almost every document and barely narrows the shelves;
• apple removes much of the room;
• pie may leave one small neighborhood.

The useful question is not “did the term occur?” but “how much should seeing this term change belief that the document is relevant?”

Raw term frequency answers a different question. A 40-page history of orchards might mention apple 80 times. A one-page recipe that directly answers the query might mention it 4 times. Counting alone rewards the long document for having more opportunities to repeat.

Odds turn evidence into addition

Let $R$ mean that a document is relevant to the query. For one query term $t$, define

$$p_t=P(t\text{ occurs}\mid R)$$

and

$$q_t=P(t\text{ occurs}\mid \neg R).$$

Seeing $t$ changes the odds of relevance by the likelihood ratio

$$\frac{p_t}{q_t}.$$

But absence also carries information. Compare the odds for a document where the term occurs with the odds for a document where it does not. The resulting binary-independence weight is

$$w_t=\log\frac{p_t(1-q_t)}{q_t(1-p_t)}.$$

The logarithm is not cosmetic compression. Under the model's conditional- independence assumption, likelihood ratios for query terms multiply. Logs turn that product into a sum:

$$\log\prod_{t\in q}\Lambda_t =\sum_{t\in q}\log\Lambda_t.$$

That additive form will later let term contributions be accumulated in any grouping and bounded before every document is fully scored.

The sign has meaning:

• $p_t>q_t$ gives positive evidence;
• $p_t=q_t$ gives zero evidence;
• $p_t<q_t$ gives negative evidence under the model.

Ranking by any positive-base logarithm gives the same order. The base changes units, not winners.

Estimating the weight without relevance judgments

Suppose the corpus has:

• $N$ documents;
• $n_t$ documents containing term $t$;
• $R$ judged-relevant documents;
• $r_t$ judged-relevant documents containing $t$.

With half-count smoothing, estimate

$$p_t=\frac{r_t+0.5}{R+1}$$

and

$$q_t=\frac{n_t-r_t+0.5}{N-R+1}.$$

Substitution into the log-odds ratio yields the Robertson–Spärck Jones relevance weight

$$w_t=\log \frac{(r_t+0.5)(N-n_t-R+r_t+0.5)} {(R-r_t+0.5)(n_t-r_t+0.5)}.$$

Most first-pass searches have no query-specific relevance judgments. A common neutral estimate takes $p_t=0.5$ and estimates nonrelevant occurrence from the whole collection. The weight reduces to

$$\operatorname{RSJ}(t)= \log\frac{N-n_t+0.5}{n_t+0.5}.$$

Now rarity has emerged from an odds model. When $n_t$ is small, the numerator dominates and the weight is positive. At about half the corpus it crosses zero. Above half, the raw RSJ weight is negative: under these assumptions, presence is more characteristic of nonrelevant documents than relevant ones.

There is more than one formula called IDF

Implementations often need nonnegative term contributions for pruning, explanation, or product behavior. Two common alternatives are

$$\operatorname{IDF}_{\mathrm{ratio}}(t)=\log\frac{N}{n_t}$$

and

$$\operatorname{IDF}_{+}(t)= \log\left(1+\frac{N-n_t+0.5}{n_t+0.5}\right).$$

Both approach zero as $n_t$ approaches $N$. Neither is algebraically identical to the signed RSJ weight. Flooring negative RSJ values at zero is another policy. These choices can change rankings and whether an upper-bound algorithm is legal, so an index and query engine must name the exact variant rather than store a field called merely idf.

For $N=1000$:

The last row exposes an often-repeated but incorrect simplification: the raw RSJ expression does not tend to zero for a ubiquitous term. Nonnegative variants do. A careful system says which one it uses and why.

The tenth occurrence is not ten first occurrences

Document frequency measures how widely a term is distributed. Term frequency $f_{t,d}$ measures how often it occurs in one document. Linear frequency would give every repetition the same increment:

$$\operatorname{tf}(f)=f.$$

That rewards verbosity and repetition without limit. BM25 uses a saturating shape. Start with

$$s(f)=\frac{f}{k_1+f},$$

where $k_1>0$. Its asymptote is

$$\lim_{f\to\infty}s(f)=1,$$

and its derivative is

$$s'(f)=\frac{k_1}{(k_1+f)^2}.$$

The derivative is positive and decreases toward zero. Every additional occurrence helps, but each helps less than the previous one.

BM25 commonly multiplies by $k_1+1$:

$$\operatorname{sat}(f)= \frac{(k_1+1)f}{k_1+f}.$$

This makes the contribution equal to 1 when $f=1$ while preserving the ranking shape for fixed $k_1$. The asymptote becomes $k_1+1$. A smaller $k_1$ saturates sooner; a larger $k_1$ behaves more like linear frequency across the observed range.

A count needs a denominator

Four occurrences in a 100-token note are denser than four occurrences in a 100,000-token book. Let

• $|d|$ be the indexed length of document $d$;
• $\overline{|d|}$ be the corpus average indexed length;
• $b\in[0,1]$ control length normalization.

Define the length factor

$$K_d=k_1\left(1-b+b\frac{|d|}{\overline{|d|}}\right).$$

Replace $k_1$ in the saturation denominator with $K_d$:

$$\operatorname{tfNorm}(t,d)= \frac{(k_1+1)f_{t,d}} {f_{t,d}+k_1\left(1-b+b\frac{|d|}{\overline{|d|}}\right)}.$$

The endpoints explain the parameter:

• at $b=0$, $K_d=k_1$ and document length has no effect;
• at $b=1$, $K_d=k_1|d|/\overline{|d|}$ and the count is fully normalized by relative length in this formula;
• when $|d|=\overline{|d|}$, every $b$ gives $K_d=k_1$.

This is an interpolation between two assumptions, not a universal correction. Some long documents cover many topics and need normalization. Others are long because the answer itself is detailed. Tuning $b$ changes that judgment.

The “document length” must be measured after the analyzer choices that define the index. If one side counts stopwords and the other does not, the formula's symbols agree while its data does not.

Assemble BM25 from the three decisions

For query $q$ and document $d$, a common BM25 form is

$$\operatorname{BM25}(q,d)= \sum_{t\in q} \operatorname{IDF}(t) \frac{(k_1+1)f_{t,d}} {f_{t,d}+k_1\left(1-b+b\frac{|d|}{\overline{|d|}}\right)}.$$

Every factor is now inspectable:

1. document frequency supplies corpus rarity;
2. term frequency supplies within-document evidence;
3. $k_1$ sets how quickly repetition saturates;
4. relative length and $b$ control verbosity normalization;
5. the sum combines per-term evidence under the independence approximation.

BM25-SCORE(queryTerms, document, corpus, k1, b, idfPolicy)
Input:  analyzed query terms, document statistics, corpus statistics, parameters
Output: additive relevance score and per-term explanation

score ← 0
explanation ← empty sequence
for each distinct term t in queryTerms
    n ← documents in corpus containing t
    f ← occurrences of t in document
    if f = 0
        continue
    idf ← IDF(idfPolicy, corpus.documentCount, n)
    lengthRatio ← document.length / corpus.averageDocumentLength
    denominator ← f + k1 × (1 - b + b × lengthRatio)
    tfWeight ← (k1 + 1) × f / denominator
    contribution ← idf × tfWeight
    append (t, n, f, idf, tfWeight, contribution) to explanation
    score ← score + contribution
return (score, explanation)

The algorithm takes $O(|q|)$ statistic lookups per candidate document when query terms have already been deduplicated and the index supplies $n_t$, $f_{t,d}$, $|d|$, and $\overline{|d|}$. Candidate generation and postings traversal are separate costs. Its auxiliary working space is $O(1)$ without an explanation and $O(|q|)$ when the explanation is retained.

Query term frequency is omitted here deliberately. Some BM25 variants include a second saturation factor for it; many short web queries treat each distinct query term once. Again, “BM25” names a family unless every factor and parameter is pinned.

Work one ranking by hand

Take $N=1000$, use the nonnegative $\operatorname{IDF}_{+}$ variant, and query apple pie. Suppose:

The pie contribution receives much larger IDF. Compare two documents at $k_1=1.2$ and $b=0.75$:

The history's 80 repetitions do not become 80 times the evidence of one occurrence, and its length raises the saturation denominator. The rare pie match dominates the distinction. This is exactly the behavior raw frequency could not express.

The explanation should expose the actual numbers rather than say “matched better.” A ranking bug becomes diagnosable when a reader can see n, f, relative length, IDF variant, saturation, and final contribution for each term.

Stopwords: cheap evidence is not absent evidence

A stoplist deletes selected tokens during analysis. Low or nonpositive IDF reduces their ranking contribution without deleting them. Those operations are not equivalent.

Consider the query

how was this website built

A stoplist containing how, was, and this leaves only website built. That remainder describes a broad topic. The removed words carried the query's interrogative shape, phrase positions, and potential exact-match evidence even if their standalone ranking weights were small.

Keeping a common term allows:

• exact phrase and proximity checks;
• literal page find;
• quoted-query semantics;
• explanations that preserve what the reader typed;
• later analyzers or tasks to make a different choice.

This does not prove that every deployment should index every token. Storage, privacy, language, and latency can justify exclusions. It proves that deletion is a semantic decision, while IDF is a graded scoring decision. One cannot be described as merely a faster implementation of the other.

The raw signed RSJ weight adds another reason for precision: a ubiquitous term does not automatically receive “almost zero” there; it becomes negative. Systems that want common terms to contribute zero or a small positive amount choose a nonnegative IDF variant or a floor. The policy belongs in the scoring contract.

The false assumption that still helps

The binary independence model assumes query terms are conditionally independent given relevance or nonrelevance. Natural language violates this constantly. new and york are not independent in documents about New York; machine and learning form a concept together.

Why can an approximation built on a false assumption work?

• The score needs a useful ordering, not calibrated posterior probabilities.
• Log-odds rarity captures a strong marginal signal even when dependencies remain.
• Saturation and length normalization repair two major failures of binary term presence for ordinary text.
• Parameters can be evaluated on held-out judgments for the actual task.
• Phrase, field, proximity, and learned features can add evidence the independence model omits.

That is an empirical defense, not a proof of universal superiority. The model earns deployment by beating alternatives on named judgments and latency budgets, not by having a probabilistic ancestry.

Engineering reality

For each indexed field and segment, a production scorer must pin:

• the exact analyzer and document-length definition;
• the IDF expression, smoothing, sign or floor policy;
• $k_1$, $b$, and any query-frequency factor;
• whether document frequency is global, per shard, or approximated;
• how deletions and newly committed documents update $N$, $n_t$, and average length;
• the numeric type and deterministic tie-break order.

Distributed statistics create a subtle failure. If each shard computes IDF from only its local $N$ and $n_t$, identical documents can receive different scores solely because of placement. Merging shard top-k lists then compares numbers built from different corpora. A coordinator needs common statistics, a correction phase, or an explicitly approximate contract.

Very common terms can also dominate traversal cost even when their score is small. Keeping them semantically does not require decoding their entire postings list for every query. Phrase anchors, shortest-list-first planning, impact ordering, and later upper-bound algorithms can avoid much of that work. Storage policy and query execution are separate levers.

What not to do

The differential oracle for the arithmetic is a direct mathematical implementation over small exact statistics. Ranking tests should pin both the total order and the per-term decomposition. Property checks should establish that, under nonnegative IDF, contribution is nondecreasing in frequency, bounded by its stated asymptote, and decreases as document length grows when $b>0$ and other values are fixed.

The field changes the meaning of an occurrence

BM25 has treated a document as one bag of analyzed tokens. Real documents have titles, paths, headings, tags, captions, and bodies. One occurrence in a title often carries more editorial authority than one in a footnote. The fields also have different typical lengths.

A tempting extension scores every field with BM25 and adds the already- saturated answers. That gives the same term several “first occurrences,” one per field, and can overreward documents that scatter weak evidence across the schema.

The next chapter derives BM25F's answer: normalize and weight field frequencies, combine them into one pseudo-frequency, and saturate once.

Lessons

• The binary-independence term weight is a log-odds ratio comparing term presence with term absence under relevance and nonrelevance.
• Without relevance judgments, a neutral estimate yields the signed Robertson–Spärck Jones weight $\log((N-n_t+0.5)/(n_t+0.5))$.
• Signed RSJ, $\log(N/n_t)$, nonnegative log-one-plus, and floored variants are different scoring policies.
• Saturation is monotone with a decreasing derivative: repetition helps, but each occurrence contributes less.
• $b$ interpolates between no document-length normalization and the formula's full relative-length normalization.
• BM25 combines corpus rarity, within-document frequency, saturation, and length. It is a family until every variant and parameter is fixed.
• Low ranking weight is not token deletion. Stopword removal can destroy phrase, literal, and query-shape evidence.
• Conditional term independence is false for language; BM25 remains an approximation whose value must be established by evaluation.

Practice

1. Starting from $p_t$ and $q_t$, derive $\log(p_t(1-q_t)/(q_t(1-p_t)))$ as the difference between the log-odds when a term is present and absent.
2. Compute signed RSJ and nonnegative log-one-plus IDF for $N=1000$ and $n_t\in\{1,100,500,900,1000\}$. Identify every ordering difference.
3. Differentiate $(k_1+1)f/(k_1+f)$ and prove that it is increasing and concave for $f\ge0$.
4. Hold term frequency fixed and compare the BM25 term-frequency factor at $b=0$ and $b=1$ for documents half, equal to, and twice the average length.
5. Construct a query where deleting stopwords changes an exact phrase answer even though the same stopwords would receive almost no weight under your chosen nonnegative IDF policy.

References

1. Stephen E. Robertson and Karen Spärck Jones. “Relevance Weighting of Search Terms.” Journal of the American Society for Information Science 27, no. 3, 1976.
2. Stephen Robertson and Hugo Zaragoza. “The Probabilistic Relevance Framework: BM25 and Beyond.” Foundations and Trends in Information Retrieval 3, no. 4, 2009.
3. Karen Spärck Jones. “A Statistical Interpretation of Term Specificity and Its Application in Retrieval.” Journal of Documentation 28, no. 1, 1972.