TF-IDF term weighting

A candidate set is not a ranking. Once an inverted index has produced the 2,914 documents containing both authentication and timeout, the simplest scoring rule anyone would write — count how many query terms each document contains — ties all 2,914 of them at two out of two, and the engine returns them in document id order, so the top result is whichever chunk happened to be indexed first. Scoring is what turns that set into an order, and TF-IDF is the scoring function the rest of the field is measured against, including the one modern engines actually ship.

Its two halves have separate origins and separate jobs. Term frequency (tf) is the number of times a term appears inside one particular document, stored alongside the document id in the postings list for exactly this purpose. Inverse document frequency (idf) is a weight derived from document frequency (df), the count of documents containing the term at least once, which is the number already sitting next to every entry in the term dictionary. Multiply them, sum over the query's terms, and you have a score.

Rarity is information, and Spärck Jones made it measurable#

Counting occurrences helps immediately and fails instructively. The missing ingredient is that not all query terms are worth the same, and a rule that counts occurrences has no place to record that. Hans Peter Luhn had proposed counting term occurrences as a relevance signal in 1957, and it took until 1972 for Karen Spärck Jones to publish the other half in "A statistical interpretation of term specificity and its application in retrieval": the weight of a term should fall as the number of documents containing it rises. A term occurring in almost every document distinguishes nothing, so a match on it carries almost no evidence, while a term occurring in one document out of millions nearly identifies that document on its own.

Inverse document frequency turns that observation into a number by taking a logarithm of the ratio between the collection size and df:

import math

N = 4_400_000  # chunks in one engineering corpus

def idf(df: int) -> float:
    return math.log(N / df)

Work one term through it before trusting the general form. authentication appears in 41,000 of those 4.4 million chunks, so the ratio inside the logarithm is 4.4 million over 41,000, a little over a hundred, and its natural logarithm is 4.68. timeout appears in 180,000, a smaller ratio, and lands at 3.20. A term in almost every document produces a ratio just above 1, whose logarithm is very close to zero, which is the whole point of the construction.

The logarithm is doing real work in that expression. Without it, the weight would be the raw ratio: 4.4 million for a term in a single document, 4.4 for a term with df = 1,000,000, and a hair over 1 for a term appearing in 4,180,000 of them. A single mention of a rare token would swamp everything else in a document no matter how irrelevant the rest of it was. Taking the log compresses that four-million-to-one spread to a factor of about 300, which reflects how the evidence actually behaves: the difference between a term in one document and a term in ten is large, and the difference between a term in 100,000 documents and one in 110,000 is negligible.

That factor of about 300 is not an approximation, and it is worth checking because the same number appears again two paragraphs below for the same reason. The largest weight the table produces is 15.30 and the smallest is 0.05, and one divided by the other is a little over three hundred. The reason the check works at all is a property of logarithms worth naming: a difference of logarithms is the logarithm of a ratio. So the gap between any two rows of the last column is the logarithm of the ratio of their document frequencies, and nothing else. Subtract the top row's weight from the bottom row's and the answer is just over fifteen and a quarter, which is the natural logarithm of 4,180,000 — the ratio between the two terms' document frequencies, since the rarer of them has a frequency of one. Two rows chosen at random will do the same thing, which is what makes the column checkable rather than merely plausible.

The middle column and the last one are the same fact written twice, which is what makes the table verifiable without a calculator. The percentage is df as a share of the collection, so the collection over df is one hundred divided by that percentage — and the weight is the natural logarithm of exactly that. Take the timeout row: one hundred divided by 4.1 is a little over twenty-four, and the natural logarithm of twenty-four is a little under 3.2. Every row does this. A row whose weight did not follow from its percentage would be a row whose document frequency came from a different corpus than the rest of the table.

The bottom row is worth sitting with, because the whole practical argument of this topic rests on it. A single occurrence of ERR_CONN_REFUSED contributes 15.3 to a document's score. To match it, a document would need to accumulate 300 occurrences of the, or four of authentication. Both of those follow from one division. Fifteen point three divided by 0.05 is a little over three hundred, which is the same three hundred as the compression factor above, arrived at from the same two rows. Fifteen point three divided by 4.68 is a little over three, and since term counts are whole numbers the answer is four. The engine has not been told that error codes are important; the corpus statistics say so, and IDF reads them off.

Multiplying the two, and summing over the query#

TF-IDF is the product of term frequency and inverse document frequency, summed over the terms in the query. Written out for a collection small enough to inspect:

from collections import Counter
import math

docs = {
    "auth-timeouts":  "authentication timeout authentication timeout "
                      "authentication settings idle session",
    "release-notes":  "timeout timeout timeout timeout release notes "
                      "authentication ... " * 40,
    "network-guide":  "connection refused firewall timeout network",
}

tokens = {d: text.split() for d, text in docs.items()}
N = len(tokens)
df = Counter(t for toks in tokens.values() for t in set(toks))

def tfidf(query: str, doc: str) -> float:
    tf = Counter(tokens[doc])
    return sum(tf[t] * math.log(N / df[t]) for t in query.split() if df[t])

for d in tokens:
    print(f"{d:>14}  {tfidf('authentication timeout', d):6.2f}  "
          f"({len(tokens[d])} tokens)")

 auth-timeouts    1.62  (8 tokens)
 release-notes   64.28  (280 tokens)
 network-guide    0.41  (5 tokens)

The shape of that toy output is the whole lesson in miniature. The 280-token document scores about forty times the 8-token one, and it is thirty-five times as long. Score and length have moved together almost exactly, which is what a formula with no length term in it does when the query terms are ordinary words.

On real corpus statistics the arithmetic is identical and the numbers are larger. Take two documents that both answer to authentication timeout: a 180-word reference page with three occurrences of authentication and one of timeout, and a 6,200-word quarterly release-notes page with one occurrence of authentication and eleven of timeout spread across eleven changelog bullets. Using the IDF values from the table, the reference page scores three times 4.68, which is a little over fourteen, plus one times 3.20, for a total of 17.24. The release notes score 4.68 plus eleven times 3.20, which is a little over thirty-five, for a total of 39.88.

The release notes win by more than a factor of two, and TF-IDF has not fixed anything a user would complain about. It has changed the failure from arbitrary to explicable, which is progress of a specific kind: the ranking is now wrong for a reason you can point at and argue with.

Neither of the two reasons for that is a subtle theoretical concern. Between them they account for the large majority of complaints about a page that has no business being first, and both are visible in the two rows of the table.

The first of the two reasons is that eleven mentions are not eleven times the evidence of one mention. Term frequency enters the formula linearly and without a ceiling, so a document mentioning a term 60 times scores sixty times as much for it as a document mentioning it once, and 60 times a moderate IDF beats one occurrence of almost anything. In practice the relationship between occurrence count and relevance is steeply diminishing: the second mention of "timeout" tells you a lot more than the fortieth. Any page long enough to repeat a term dozens of times incidentally can outscore a page written specifically to answer the question.

The second is that the score has no idea how long the document is. A 6,200-word page has roughly 34 times as many chances to accumulate term occurrences as a 180-word page, and TF-IDF rewards every one of them. Nothing in tf * idf compensates for that, so on any collection where document lengths vary by an order of magnitude the ranking drifts toward long documents regardless of what they are about. The two defects reinforce each other, because the way a document accumulates a high term frequency is usually by being long.

Comparing the two ratios sharpens what length blindness actually gives a long document, and it is less than it first sounds. The release notes have thirty-four times the opportunity and win by a little over two. They used eleven of those thirty-four chances rather than all of them, because a document does not repeat a term in proportion to its length — it repeats it in proportion to how often the subject comes up. So length blindness hands out opportunity, and the document converts as much of it as its content allows. That is why the failure is common without being universal, and why it is worst on documents assembled from many small independent parts. A changelog is exactly that shape: eleven bullets written by eleven people, each with its own reason to say timeout.

The information retrieval literature accumulated patches for both before BM25 settled the question. The standard fix for unbounded term frequency was sublinear scaling, replacing tf with 1 + log(tf), which turns 60 occurrences into 5.1 and 1 occurrence into 1. That is a real improvement with an awkward property: the logarithm has no ceiling either, so a sufficiently repetitive document still climbs, just more slowly, and the curve has no parameter with which to say how quickly the returns should diminish for this collection. The standard fix for length was pivoted length normalisation, proposed by Singhal, Buckley and Mitra in 1996 after they measured that cosine normalisation over-corrected — it made short documents win too often relative to how often they were actually judged relevant — and introduced a tunable pivot to correct the correction. Both ideas survive in BM25 in compressed form, one as a saturating ratio and one as a single parameter between zero and one.

import math

def tf_variants(tf: int) -> tuple[float, float]:
    return float(tf), 1 + math.log(tf)

for n in (1, 2, 5, 20, 60):
    raw, sub = tf_variants(n)
    print(f"tf={n:<3} raw={raw:5.1f}  sublinear={sub:5.2f}")

tf=1   raw=  1.0  sublinear= 1.00
tf=2   raw=  2.0  sublinear= 1.69
tf=5   raw=  5.0  sublinear= 2.61
tf=20  raw= 20.0  sublinear= 3.996
tf=60  raw= 60.0  sublinear= 5.09

Running that curve over the two real documents is the fastest way to see why one patch was not enough, and the answer is not the one the curve's shape suggests. Under sublinear scaling the reference page's three occurrences of authentication become a little over two, so its authentication contribution falls from over fourteen to under ten, and its total lands a little under thirteen. The release notes' single occurrence stays at one, and their eleven occurrences of timeout become under three and a half, so their total lands a little over fifteen and a half. The release notes still win. What changed is the margin: a gap of more than double becomes a gap of under a fifth.

That is a useful result and a discouraging one, and it is worth naming why. Sublinear scaling attacks the term count and leaves the length alone, and the two documents differ on both. Squeezing the count narrows the gap in proportion to how much of the long document's advantage came from repetition, and it cannot touch the part that came from having thirty-four times as much room. Any fix that addresses one of the two defects will land somewhere in this range — better, and still ranking the wrong page first — which is the argument for a formula that carries a term for each.

Where the statistics come from, and when they lie#

Where df comes from is a detail that bites in production. A Lucene index is a set of immutable segments, and each segment carries its own term dictionary with its own document frequencies; a search across a shard sums them, which is correct. A search across a distributed index does not, by default: each shard — one self-contained slice of the index, holding its own segments and therefore its own term statistics — scores its own candidates using its own local df and N, and the coordinating node merges the already-scored results. With evenly distributed data the local statistics approximate the global ones closely enough that nobody notices, and with skewed routing they do not. A corpus where one customer's documents all land on shard 3 will give a term that is common for that customer a high IDF on the other four shards and a low one on shard 3, so the same document scores differently depending on where it lives. Elasticsearch's search_type=dfs_query_then_fetch fixes it by gathering global term statistics in a preliminary round trip, at the cost of one extra network hop per query, and it is the setting to reach for when relevance is inexplicably inconsistent across a small index with many shards.

Why the coordinating node cannot repair this after the fact is the step that makes the extra round trip unavoidable. Each shard sends back documents with scores already computed, and each shard computed its score against its own N and its own df. A score of 12 from one shard and a score of 12 from another are not the same quantity, in the way two prices quoted in unnamed currencies are not the same amount, and nothing in the returned payload says what the exchange rate is. The coordinator would need every shard's document frequency for every query term to convert them, which is precisely the information the preliminary round trip goes and fetches. The choice is therefore between one extra hop and comparing numbers that are not comparable, and the second option is what a default configuration is quietly doing.

The same effect explains why IDF is unstable on small collections. With N = 300, a term moving from df = 2 to df = 3 changes its weight from 5.01 to 4.61, an 8 percent swing from one document being added, and rankings shuffle as documents arrive. IDF is a statistical estimate of term specificity, and estimates from tiny samples are noisy; on a few hundred documents the ordering is being decided partly by which documents happened to be written.

The mechanism there is more specific than "small collections are noisy", and pinning it down tells you when the problem stops. Because a difference of logarithms is the logarithm of a ratio, the change in a term's weight when its document frequency goes from two to three is the natural logarithm of three halves, and that value does not depend on the collection size at all. A term already sitting at 41,000 documents, gaining one more, changes by the logarithm of a ratio barely above one, which is a few hundred-thousandths. So the instability is driven by df being small, not by N being small — a rare term on a large corpus is exactly as jumpy as any term on a tiny one. The practical form of the rule is that the weights you can trust are the weights of terms appearing in enough documents that one more document does not move the count by a noticeable fraction.

Variants of the formula differ in how they handle edge cases. log(N/df) goes to zero when a term is in every document and is undefined at df = 0, so implementations use log(1 + N/df) or log((N - df + 0.5)/(df + 0.5)) to keep the weight positive and bounded. Those choices shift the numbers by a few percent and change nothing about the ordering, which is why the table above uses the plain form. That claim holds where the query's terms are ordinary words and needs a condition attached at the rare end. For the, the smoothed ratio is the shortfall between the collection size and that document frequency, divided by the document frequency, plus one — and its logarithm is the same 0.05 the plain form gives — the variants agree almost exactly wherever df is large, because subtracting df from N and adding a half to df barely move a ratio near one. At df = 1 they visibly disagree, since subtracting one document from the numerator and adding a half to a denominator of one changes that ratio materially. The variants therefore differ exactly where the weights are largest, so a query mixing a near-unique identifier with a very common word is the one case where the choice of form can reorder results.

One further confusion is worth heading off. TF-IDF is frequently taught as one half of the vector space model, in which each document becomes a vector of TF-IDF weights over the vocabulary, the query becomes such a vector too, and relevance is the cosine of the angle between them. Salton's SMART system worked this way, and the cosine denominator divides by the Euclidean norm of the document vector, which does give long documents some protection. BM25 is not that model: it builds no document vectors and uses no cosine normalisation. It comes from a different tradition — Robertson and Spärck Jones's probabilistic ranking framework, developed at City University London through the 1980s and tuned at the TREC evaluations of the 1990s, which is where the name Okapi BM25 comes from, Okapi being the system it was implemented in. TREC is the Text REtrieval Conference, the evaluation NIST has run annually since 1992, and what it contributed here was shared corpora with shared relevance judgments, so that competing ranking functions could be compared on identical queries rather than on their authors' descriptions of them.

TF-IDF is worth understanding in its own right rather than as a historical curiosity, because one of its two factors is still in production everywhere. Term frequency counts evidence inside a document; inverse document frequency measures how much a match is worth across the collection, and it is the factor that makes an error code beat a topical page by an order of magnitude. What BM25 keeps, essentially untouched, is exactly that factor. The formula picks up the +0.5 smoothing terms that come out of the probabilistic derivation, so it is written ln((N - df + 0.5)/(df + 0.5) + 1) rather than ln(N/df), and for a term with df = 1 in a 4.4-million-document corpus that yields 14.6 instead of 15.3 — the exact figure depending on whether N is taken as every document in the collection or only those with the field populated, which is what an engine actually counts. The shape is identical and the intuition transfers completely.

The refinement is entirely on the other factor. Where TF-IDF multiplies by the raw count, BM25 pushes that count through a saturating curve, and where TF-IDF ignores length, BM25 divides by a length ratio under the control of a parameter. Those two modifications are what turn a formula that ranks the release notes first into one that does not.