BM25 ranking

Deep dive

How it works

In: tokenized query, inverted index with (doc id, tf) postings and per-document lengths · Out: top-k documents with scores · State: postings, document lengths, N and total length · Cost: O(Σ posting lengths of the query terms) + O(k) heap

Index time (inverted index):

1. Tokenize each document (Unicode tokenization).
2. Per term, append (doc id, tf) to its posting list. Store each doc's length |d| (Lucene stores it lossily in one byte, called the "norm").
3. Keep N (doc count) and the total length for avgdl.

Query time:

1. Per distinct query term t: n = posting list length, IDF = ln(1 + (N − n + 0.5)/(n + 0.5)).
2. For each posting (d, tf): add IDF · tf·(k1+1)/(tf + k1·(1 − b + b·|d|/avgdl)) to d's score.
3. Top-k by score.

N = 5 docs, avgdl = 6.8, query "fox" (n = 3, IDF = ln(1 + 2.5/3.5) = 0.54)
doc 2: "fox fox fox and more fox"   tf 4, |d| 6   -> 0.93
doc 0: "the quick brown fox"         tf 1, |d| 4   -> 0.65
doc 3: 18 words with one fox         tf 1, |d| 18  -> 0.32
tf part: 1 -> 1.0, 2 -> 1.38, 4 -> 1.69, ∞ -> 2.2 (k1 + 1), at |d| = avgdl

Code

use std::collections::{BinaryHeap, HashMap};

pub struct Index {
    postings: HashMap<String, Vec<(u32, u32)>>, // term -> (doc id ascending, term frequency)
    doc_len: Vec<u32>,                          // tokens per doc
    total_len: u64,
}

pub const K1: f32 = 1.2; // tf saturation (Lucene default)
pub const B: f32 = 0.75; // length normalization strength (Lucene default)

impl Index {
    pub fn new() -> Self { Index { postings: HashMap::new(), doc_len: Vec::new(), total_len: 0 } }

    /// Adds an already tokenized document; returns its id.
    pub fn add(&mut self, terms: &[&str]) -> u32 {
        let id = self.doc_len.len() as u32;
        let mut tf: HashMap<&str, u32> = HashMap::new();
        for &t in terms { *tf.entry(t).or_default() += 1; }
        for (t, f) in tf { self.postings.entry(t.to_string()).or_default().push((id, f)); }
        self.doc_len.push(terms.len() as u32);
        self.total_len += terms.len() as u64;
        id
    }

    /// Lucene-style IDF: ln(1 + (N - n + 0.5) / (n + 0.5)), always > 0.
    pub fn idf(&self, df: usize) -> f32 {
        let n = self.doc_len.len() as f32;
        (1.0 + (n - df as f32 + 0.5) / (df as f32 + 0.5)).ln()
    }

    /// Term-at-a-time scoring with dense accumulators, then top-k. Returns (score, doc) best first.
    pub fn search(&self, query: &[&str], k: usize) -> Vec<(f32, u32)> {
        let n = self.doc_len.len();
        if n == 0 || k == 0 { return Vec::new(); }
        let avgdl = self.total_len as f32 / n as f32;
        let mut acc = vec![0f32; n];
        let mut q: Vec<&str> = query.to_vec();
        q.sort_unstable();
        q.dedup(); // repeated query terms would double count (BM25 has a separate query-tf factor)
        for t in q {
            let Some(list) = self.postings.get(t) else { continue };
            let idf = self.idf(list.len());
            for &(d, tf) in list {
                let tf = tf as f32;
                let norm = K1 * (1.0 - B + B * self.doc_len[d as usize] as f32 / avgdl);
                acc[d as usize] += idf * tf * (K1 + 1.0) / (tf + norm);
            }
        }
        // top-k by score; ties broken by smaller doc id. Scores are > 0, so f32 bits order correctly.
        let mut heap: BinaryHeap<std::cmp::Reverse<(u32, std::cmp::Reverse<u32>)>> = BinaryHeap::new();
        for (d, &s) in acc.iter().enumerate().filter(|(_, &s)| s > 0.0) {
            let item = std::cmp::Reverse((s.to_bits(), std::cmp::Reverse(d as u32)));
            if heap.len() < k { heap.push(item); }
            else if item < *heap.peek().unwrap() { *heap.peek_mut().unwrap() = item; }
        }
        let mut out: Vec<(f32, u32)> = heap.into_iter().map(|std::cmp::Reverse((s, std::cmp::Reverse(d)))| (f32::from_bits(s), d)).collect();
        out.sort_unstable_by(|a, b| b.0.total_cmp(&a.0).then(a.1.cmp(&b.1)));
        out
    }
}

Complexity and constants

• Work per query = Σ posting lengths of the query terms, plus O(N) for dense accumulators. Measured (code above, 100k synthetic Zipf docs, 7 M postings, one Apple M-series core): 2 common terms (df 84k and 77k) take 297 µs; 3 mid-frequency terms 71 µs; rare terms 30 µs, which is the floor of allocating and scanning 100k accumulators.
• Postings compressed with delta + bit packing take order of 1-2 bytes per posting; decoding runs at order of 1 billion integers per second with SIMD.
• WAND / MaxScore / block-max WAND on top-10 queries typically score only a small fraction of the postings of common terms and run several times faster than exhaustive evaluation.
• Per-term upper bound for pruning: IDF · (k1 + 1) globally, or a tighter bound from the block's maximum tf and minimum length (block-max).

Efficiency

• Cost: work per query = Σ posting lengths of the query terms, plus O(N) for dense accumulators. Measured with the code above (100k synthetic Zipf docs, 7 M postings, one Apple M-series core): 2 common terms 297 µs, 3 mid-frequency terms 71 µs, rare terms 30 µs (the accumulator floor). Compressed postings take order of 1-2 bytes each. Bound: memory bandwidth over the posting lists.
• Levers:
  • WAND / MaxScore / block-max WAND — scores only a small fraction of common-term postings, several times faster than exhaustive scoring (Broder 2003, Ding & Suel 2011) — top-k queries with common terms
  • delta + bit packing of postings — order of 1-2 bytes per posting, SIMD decode order of 1 G ints/s — any large index
  • 256-entry length-norm table (Lucene) — no division in the inner loop — exhaustive scoring
  • sparse or doc-at-a-time accumulators — removes the O(N) floor — large N, selective queries
• Naive → standard → state of the art:
  • scan every document's text per query · O(corpus bytes)
  • inverted index, term-at-a-time, dense accumulators · 30-297 µs on 100k docs (above)
  • block-max WAND over compressed postings · small fraction of postings scored (Ding & Suel 2011)

Implementation notes

• Precompute the length factor: Lucene quantizes |d| to one byte and builds a 256-entry table of k1·(1 − b + b·len/avgdl) per query, so the inner loop has no division.
• Accumulators: dense Vec<f32> for large result sets (as above); sparse (hash map) or doc-at-a-time for selective queries. Doc-at-a-time over sorted postings uses O(query terms) memory and enables WAND.
• WAND: sort the term cursors by current doc id; add up the terms' max scores until the sum exceeds the current k-th score (the threshold). The doc at that cursor is the next candidate, and every cursor before it can skip to it.
• Fields: BM25F combines fields (title, body) by weighting tf per field before the saturation, not by adding per-field BM25 scores.
• Distributed IDF: each shard sees a different N and n. Scores across shards differ unless you use global statistics (Elasticsearch dfs_query_then_fetch) or have large, random shards.
• Phrase and proximity: BM25 is bag-of-words. Add a proximity bonus or phrase matches as extra clauses.
• Stop words: with BM25, common terms get near-zero IDF anyway, and dropping them breaks phrase queries.

Pitfalls

• Using the raw Robertson-Spärck Jones IDF ln((N − n + 0.5)/(n + 0.5)): terms in over half the docs score negative and push matching documents below non-matching ones.
• Comparing BM25 scores across queries or indexes as if absolute: they are unnormalized; only the ranking within one query is meaningful.
• Counting repeated query terms twice (fox fox) without meaning to.
• Changing avgdl or N on every insert in a live index: scores shift. Engines use per-segment statistics and accept this.
• "Which BM25?": Lucene, Okapi, ATIRE and other variants differ in IDF and length details. Reproduce the exact variant when you compare with published results.
• Recall problems that are really tokenizer problems (case, accents, plurals): fix the analyzer, not k1 and b.

Variants and alternatives

In production

Search engines: Lucene (BM25Similarity, default since Lucene 6), Elasticsearch and OpenSearch (default similarity since Elasticsearch 5.0), Solr, Tantivy, SQLite FTS5 (bm25() with k1 = 1.2, b = 0.75), Vespa (bm25 rank feature), and ParadeDB pg_search for PostgreSQL (whose built-in ts_rank is not BM25). Retrieval research and RAG: BM25 is the lexical baseline in BEIR, where it stays robust across 18 heterogeneous datasets and domains; hybrid RAG pipelines pair it with dense retrieval.

Implementations

Sources

• S. Robertson, H. Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond, Foundations and Trends in Information Retrieval, 2009. paper
• S. E. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, M. Gatford, Okapi at TREC-3, TREC, 1994. paper
• C. Kamphuis, A. P. de Vries, L. Boytsov, J. Lin, Which BM25 Do You Mean? A Large-Scale Reproducibility Study of Scoring Variants, ECIR, 2020. paper
• A. Z. Broder, D. Carmel, M. Herscovici, A. Soffer, J. Zien, Efficient Query Evaluation Using a Two-Level Retrieval Process, CIKM, 2003. paper
• S. Ding, T. Suel, Faster Top-k Document Retrieval Using Block-Max Indexes, SIGIR, 2011. paper
• N. Thakur et al., BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models, NeurIPS Datasets and Benchmarks, 2021. paper
• SQLite documentation, FTS5 Extension (bm25() auxiliary function). docs