TF-IDF and BM25 Are Exact KL Divergences

Paper: 2609.14016 Author: Ivan Silajev Categories: cs.IR, cs.CL

The Gap

TF-IDF and BM25 are two of the most widely used methods for scoring query-document relevance, decades old and deployed everywhere. And neither has a standard probabilistic derivation that justifies it as a statistical method within a unified framework.

That absence has consequences that are easy to underrate. A heuristic that works can be tuned, combined and used, but it cannot be reasoned about. You cannot say what it estimates, so you cannot say when it should fail, what a sensible variant would be, or how it relates to a method derived from different principles. And comparison is stuck at the experimental level: two scorers can be benchmarked against each other indefinitely without any account of whether they are measuring the same quantity.

   TWO UBIQUITOUS SCORERS WITHOUT A DERIVATION

   TF-IDF and BM25: TWO OF THE MOST WIDELY USED METHODS for scoring
   query-document relevance
     decades old, deployed everywhere
        |
        v
   AND NEITHER HAS A STANDARD PROBABILISTIC DERIVATION that justifies it
   as a STATISTICAL METHOD WITHIN A UNIFIED FRAMEWORK
        |
        v
   [WHY THAT ABSENCE MATTERS, AND IS EASY TO UNDERRATE]
     a heuristic that works can be TUNED, COMBINED and USED
     but it CANNOT BE **REASONED ABOUT**:
       YOU CANNOT SAY WHAT IT ESTIMATES
       -> so you cannot say WHEN IT SHOULD FAIL
       -> nor what a SENSIBLE VARIANT would be
       -> nor HOW IT RELATES to a method derived from DIFFERENT PRINCIPLES
        |
        v
   AND COMPARISON IS STUCK AT THE EXPERIMENTAL LEVEL
     -> two scorers can be BENCHMARKED AGAINST EACH OTHER INDEFINITELY
        without any account of WHETHER THEY ARE MEASURING THE SAME
        QUANTITY

The Increment

One sentence: Before this paper, TF-IDF and BM25 were heuristics with no probabilistic interpretation; after it, both are exact KL divergences between two probability models, giving them a shared basis and making theoretical comparison possible.

Core Mechanism

The claim is that both scoring methods admit an exact interpretation as Kullback-Leibler divergences between two probability models. Two properties of that result are worth isolating, because they determine what it is good for.

It is exact, not approximate. An asymptotic or approximate derivation would explain why the scorers behave sensibly in some limit; an exact identification says the score is the divergence, so statements about the divergence are statements about the scorer. That is the difference between a heuristic with an explanation and a statistic.

And it is a shared basis, which is the part that unlocks comparison. The paper’s stated payoff is a common theoretical basis for TF-IDF and BM25 that clarifies what they measure and allows them to be compared theoretically with other information retrieval methods rather than only experimentally. So the contribution is not two separate derivations that happen to exist; it is that both land in the same framework, which is what makes them commensurable.

One detail deserves emphasis because it is the kind of thing that decides whether a derivation applies to reality: the paper treats the BM25 variant that includes the plus-one correction in the IDF term, which is the one used in practice, and also discusses the original formulation without that correction. That is a deliberate choice to derive the deployed method rather than the published idealisation. Derivations of a formula nobody runs are of theoretical interest; deriving the variant in production is what lets the theory bear on actual systems — and the fact that the paper covers both means the difference between them becomes visible rather than assumed away.

   THE CLAIM
     BOTH scoring methods admit an EXACT INTERPRETATION AS
     KULLBACK-LEIBLER DIVERGENCES BETWEEN TWO PROBABILITY MODELS

   TWO PROPERTIES DETERMINE WHAT THE RESULT IS GOOD FOR

     [1] IT IS **EXACT**, NOT APPROXIMATE
           <- an ASYMPTOTIC or APPROXIMATE derivation would explain why
              the scorers behave sensibly IN SOME LIMIT
           <- an EXACT IDENTIFICATION says THE SCORE **IS** THE
              DIVERGENCE
           -> statements about the DIVERGENCE are statements about THE
              SCORER
           <- the difference between a HEURISTIC WITH AN EXPLANATION and
              a STATISTIC

     [2] IT IS A **SHARED BASIS** -- the part that UNLOCKS COMPARISON
           the stated payoff: a COMMON THEORETICAL BASIS FOR TF-IDF AND
           BM25 that
             CLARIFIES WHAT THEY MEASURE
             ALLOWS THEM TO BE COMPARED THEORETICALLY with other
             information retrieval methods RATHER THAN ONLY EXPERIMENTALLY
           <- the contribution is NOT two separate derivations that happen
              to exist
           <- it is that BOTH LAND IN THE SAME FRAMEWORK
           -> which is what makes them COMMENSURABLE

   ONE DETAIL DESERVES EMPHASIS -- it decides whether a derivation APPLIES
   TO REALITY
     the paper treats THE BM25 VARIANT THAT INCLUDES THE PLUS-ONE
     CORRECTION IN THE IDF TERM, WHICH IS THE ONE USED IN PRACTICE
     and ALSO discusses the ORIGINAL FORMULATION WITHOUT THAT CORRECTION
       <- a DELIBERATE CHOICE to derive THE DEPLOYED METHOD rather than
          THE PUBLISHED IDEALISATION
       <- derivations of a formula NOBODY RUNS are of THEORETICAL interest
       <- deriving THE VARIANT IN PRODUCTION is what lets the theory BEAR
          ON ACTUAL SYSTEMS
       -> and covering BOTH means the DIFFERENCE BETWEEN THEM becomes
          VISIBLE rather than ASSUMED AWAY

Think of it as discovering that two folk remedies are, in fact, dosing the same active ingredient. Two traditions each arrived at a working preparation by trial and error, and practitioners can compare which works better on which ailment — but only experimentally, and only for the ailments tried. Identifying the common active ingredient converts the comparison: now you can reason about dose-response, predict where each preparation should fail, and relate both to a compound derived from first principles. The detail about the plus-one variant is the equivalent of checking that the ingredient is present in the preparation people actually take, not only in the historical recipe.

Key Concepts

• A missing derivation as a real limitation: without knowing what a scorer estimates, you cannot say when it fails or what a sensible variant would be. It is what makes the gap more than a matter of tidiness.
• Exactness rather than approximation: the score is the divergence, so theory about the divergence transfers to the scorer without an intervening limit.
• A shared framework as the enabler of comparison: both scorers landing in one basis is what makes them commensurable with each other and with other methods.
• Deriving the deployed variant: the plus-one IDF correction is what runs in practice. Theory aimed at the published idealisation can miss the systems it is meant to explain.
• Covering both formulations: it makes the difference between them a result rather than an assumption.

Framework Shift

Before (heuristics with no stated quantity):
  score relevance with TF-IDF or BM25
  -> no probabilistic derivation
  -> cannot say what either estimates
  -> cannot predict failures or justify variants
  -> comparison is only experimental

After (exact divergences in a shared framework):
  both are exact KL divergences between two probability models
  -> the plus-one BM25 variant in practice is the one derived, with the
     uncorrected original discussed alongside
  -> a common basis clarifies what they measure
  -> theoretical comparison with other IR methods becomes possible

From two effective scorers whose properties can only be observed, to two exact divergences in one framework whose properties can be reasoned about, the core shift is that a widely used heuristic can turn out to have been measuring something all along.

Expert Assessment

Problem choice: Excellent, and the framing of the gap is more useful than “this has no theory”. The paper identifies what is lost specifically — the ability to state what is estimated, and therefore to predict failure and compare theoretically — which is what makes the derivation worth having rather than merely satisfying.

Method maturity: Two choices raise this above a formal exercise. Deriving the deployed variant rather than the published formula is the decision that makes the theory applicable, and it is the kind of detail that is easy to skip and fatal to usefulness. And treating the two scorers as landing in one framework, rather than producing two independent derivations, is what delivers the comparison payoff. Whether the KL interpretation is the most natural one is a separate question, but an exact identification in a standard framework is a strong result regardless.

Experimental integrity: This is a theory contribution, so the claims are mathematical and the reading is of definitions. The identification is exact, which means it can be checked directly rather than tested statistically, and the inclusion of both BM25 variants means the result does not depend on silently choosing a convenient formulation. The limitation is scope of interpretation: an exact KL divergence says what the score computes, not that ranking by it is optimal for retrieval — usefulness to a user is a separate question the derivation does not answer, and the paper’s claim of clarifying “what they measure” is appropriately limited to that.

Writing quality: The abstract states the result, names the pragmatic variant choice, and states the payoff in one sequence, which is the right order for a derivation with a practical detail. Because the value depends on the specific form, writing out the two probability models explicitly in the paper’s own presentation would let a reader check the identification at a glance.

Verdict: strong accept — it supplies the missing probabilistic basis for two ubiquitous scorers, derives the version actually deployed rather than the idealised formula, and places both in one framework so theoretical comparison becomes possible.

Takeaways

• Distinguish useful heuristics from understood ones. A method can be tuned and deployed for decades without anyone being able to say what it estimates.
• Prefer exact identifications to asymptotic ones when available. If the score is the quantity, theory about the quantity transfers without a limit.
• Derive the variant that runs. A derivation of the published formula can leave the deployed system unexplained.
• Ask whether two methods measure the same thing. Placing them in a common framework turns an endless benchmark competition into a comparison.