What is BM25, and how does it differ from TF-IDF?

TF-IDF. Weight a term by its frequency in the document times its inverse document frequency, so rare terms matter more. Two problems: score grows linearly with term frequency, so keyword stuffing wins, and long documents accumulate more matches.

BM25. It comes from the probabilistic relevance framework of Robertson and colleagues and is described in Introduction to Information Retrieval. For each query term it multiplies an IDF factor by a saturating term-frequency factor with length normalisation:

• IDF: Lucene's BM25Similarity implements it as log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5)), which stays positive even for very common terms.
• Term frequency: tf / (tf + k1 * (1 - b + b * docLen / avgDocLen)). As tf grows, the factor approaches 1, so extra occurrences add less and less.
• Parameters: the Lucene Javadoc says k1 "controls non-linear term frequency normalization (saturation)" and b "controls to what degree document length normalizes tf values"; the no-argument constructor uses k1 = 1.2 and b = 0.75. These are Lucene's defaults, not universal constants, and Elasticsearch lets you configure them per field.

The textbook form also multiplies by (k1 + 1); it does not change the ranking, so Lucene leaves it out.

import java.util.*;

public class Bm25TopK {
    // One term's BM25 contribution in Lucene's form; k1 and b are passed in, not hard-coded.
    static double bm25(long docCount, long docFreq, int tf, int docLen, double avgLen, double k1, double b) {
        if (tf == 0 || docFreq == 0) return 0;
        double idf = Math.log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5));
        double norm = k1 * (1 - b + b * docLen / avgLen);
        return idf * tf / (tf + norm);
    }

    record Hit(int doc, double score) {}

    // Keep the K best hits in a min-heap: O(n log K) time, O(K) memory.
    static List<Hit> topK(List<Hit> hits, int k) {
        PriorityQueue<Hit> heap = new PriorityQueue<>(
            Comparator.comparingDouble(Hit::score).thenComparing(Hit::doc, Comparator.reverseOrder()));
        for (Hit h : hits) {
            if (heap.size() < k) heap.add(h);
            else if (heap.comparator().compare(h, heap.peek()) > 0) { heap.poll(); heap.add(h); }
        }
        List<Hit> out = new ArrayList<>(heap);
        out.sort(heap.comparator().reversed());
        return out;
    }

    public static void main(String[] args) {
        double k1 = 1.2, b = 0.75;                          // Lucene's BM25Similarity defaults
        long n = 1_000, df = 10;
        System.out.printf("tf=1:%.3f tf=5:%.3f tf=50:%.3f%n",
            bm25(n, df, 1, 10, 10, k1, b), bm25(n, df, 5, 10, 10, k1, b), bm25(n, df, 50, 10, 10, k1, b));
        System.out.printf("short doc:%.3f long doc:%.3f%n",
            bm25(n, df, 2, 5, 10, k1, b), bm25(n, df, 2, 40, 10, k1, b));
        var hits = List.of(new Hit(1, 0.4), new Hit(2, 2.1), new Hit(3, 1.7), new Hit(4, 2.1), new Hit(5, 0.9));
        System.out.println(topK(hits, 3));
    }
}

Verified with OpenJDK 21.0.13. It prints tf=1:2.072 tf=5:3.675 tf=50:4.451 (saturation), then short doc:3.314 long doc:1.545 (length normalisation), then the top three hits.

Product catalogs. Titles are short and equally long, so length normalisation matters less than in articles; some teams lower b on title fields. Change it only with a judgment set and the explain output. In e-commerce, text score is usually one signal among many, such as popularity, availability and personalisation, combined in a later ranking stage.