Algos, Information Retrieval, BM25

Abstract

BM25 (Okapi Best Match 25) scores how well a document matches a keyword query. It was developed by Robertson and Spärck Jones in the 1990s and is still the default ranking in Lucene, Elasticsearch, OpenSearch and SQLite FTS5. It combines three ideas:

Rare terms matter more (IDF, inverse document frequency).

Repeats help, but with diminishing returns (term-frequency saturation, set by $k_{1}).$

Long documents get no free credit for being long (length normalisation, set by $b).$

It needs no training and no embeddings, and it is very good at the exact words, names and ids that vector search tends to blur.

Cue

What are BM25’s three ingredients? → IDF (rarity), saturating term frequency $(k_{1}),$ and length normalisation $(b)$

What do the defaults $k_{1} = 1.2$ and $b = 0.75$ do? → A term’s contribution levels off near $k_{1} + 1 = 2.2 \times$ IDF, and length counts at 75%

Why can the classic IDF go negative? → A term in more than half the docs gives $ln (< 1) < 0 .$ FTS5 clamps it to a tiny positive number and Lucene adds 1 inside the log

Where does BM25 beat vectors? → Exact ids, names and rare terms, such as FR-012

How is it combined with vectors? → Reciprocal rank fusion (RRF) of the two ranked lists, usually with $k = 60$

Formula

For a query $Q$ with terms $q_{1} \dots q_{n}$ and a document $D :$

score (D, Q) = i = 1 \sum n IDF (q_{i}) \cdot \frac{f ( q _{i} , D ) ( k _{1} + 1 )}{f ( q _{i} , D ) + k _{1} ( 1 - b + b \cdot \frac{∣ D ∣}{avgdl} )}

IDF (q) = ln \frac{N - n ( q ) + 0.5}{n ( q ) + 0.5}

where:

$f (q, D)$ is how many times term $q$ appears in $D$
$∣ D ∣$ is the document length in tokens, and $avgdl$ is the average length across the collection
$N$ is the number of documents, and $n (q)$ is how many of them contain $q$
$k_{1}$ (usually 1.2–2.0) controls saturation, and $b$ (usually 0.75) controls length normalisation

The three ideas

1. IDF: rare terms are worth more. IDF stands for inverse document frequency. A term’s document frequency $n (q)$ is how many documents contain it. IDF is that figure turned upside down, so the fewer documents a term appears in, the higher its weight. A term in 1 document of 1,000 gives $ln (999.5/1.5) \approx 6.5 .$ A term in half of them gives about 0. Stopwords fall out on their own.

IDF variants

The classic formula goes negative for terms in more than half the documents, so matching them would lower a score. Engines patch this differently:

SQLite FTS5 clamps IDF ≤ 0 to $1 0^{- 6} .$

Lucene / Elasticsearch use $ln (1 + \frac{N - n + 0.5}{n + 0.5}),$ which is always positive.

Scores from different engines aren’t comparable, but the rankings are usually close.

2. Saturation: the 10th repeat adds little. With $b = 0,$ a term’s contribution is $IDF \cdot \frac{f ( k _{1} + 1 )}{f + k _{1}},$ which approaches $(k_{1} + 1) \cdot IDF$ but never reaches it. With $k_{1} = 1.2 :$

Occurrences $f$	1	2	3	5	10	100
× IDF	1.00	1.38	1.57	1.77	1.96	2.17

This is the main improvement over raw TF-IDF (term frequency × inverse document frequency), where repeating a word 100 times gives 100 times the score. Keyword stuffing doesn’t pay.

3. Length normalisation: long documents don’t win by default. A document twice the average length is treated as if its term counts were lower. $b = 1$ normalises fully and $b = 0$ ignores length. For element-sized units, such as one requirement each, lengths vary less, so $b$ matters less than it does for whole pages.

Worked example

Six one-line documents, query “search index”, $k_{1} = 1.2,$ $b = 0.75,$ avgdl ≈ 8.8 tokens:

Doc	Text	Tokens	”search"	"index”	Score
d3	A citation must resolve to the committed document, not to the search index.	13	1	1	0.985
d6	Search the archive, then search again.	6	2	–	0.888
d1	The index is never the source of record.	8	–	1	0.611
d2, d4, d5	(no query terms)		–	–	0

Both terms appear in 2 of 6 documents, so each has IDF $= ln (4.5/2.5) \approx 0.588 .$

d3 is the longest document, so each of its matches is discounted. It still wins because it matches both terms.
d6 matches “search” twice in a short document. Saturation means the two occurrences are worth 1.5 times one occurrence, not 2.
d1 has one match of average weight.

Small corpora behave oddly

With only four documents, a term in two of them gets IDF $= ln (2.5/2.5) = 0,$ so it adds nothing. Check a toy example’s IDFs before drawing conclusions from it.

Weighted fields (how FTS5 does it)

Real documents have structure, such as a title, an id and a body. A match in the id should count for more than a match in the body. SQLite FTS5’s bm25(table, w1, w2, …) multiplies each column’s term count by its weight before saturating. Document length stays the unweighted total across columns:

f_{w} (q, D) = c \sum w_{c} \cdot f (q, D_{c})

(BM25F, from the research literature, goes further and normalises each field’s length separately.)

For example, an index of specification requirements, one row per requirement, might use three columns:

Column	Holds	Weight
`title`	Page title, heading path, the element’s heading	5
`ident`	The element id, e.g. `FR-012`	10
`body`	The requirement text	1

CREATE VIRTUAL TABLE version_fts USING fts5(title, ident, body, tokenize = 'unicode61');
SELECT rowid, -bm25(version_fts, 5, 10, 1) AS score   -- FTS5 returns lower-is-better
FROM version_fts WHERE version_fts MATCH '"FR-012" OR "retries"'
ORDER BY score DESC;

Practical gotchas with FTS5:

The tokenizer splits on -. unicode61 turns FR-012 into fr 012, so quote every query term to make it a phrase. Unquoted, - is FTS5 syntax.
OR the terms. FTS5’s default is AND, which drops any document missing a single word.
Strip stopwords from the question, including corpus-specific words that appear in nearly every document.
Keep status out of the indexed text. A record’s status changes, but its text doesn’t.

Implementation (Rust)

Plain BM25 is the one-field case of the weighted version, so this is the FTS5-style weighted version, with FTS5’s IDF clamp:

use std::collections::HashMap;
 
const K1: f64 = 1.2; // how fast repeated terms stop adding score
const B: f64 = 0.75; // how much long documents are penalised (0 = not at all, 1 = fully)
 
/// Lowercase, split on anything that isn't a letter or digit.
/// Like FTS5's `unicode61`, so "FR-012" becomes ["fr", "012"].
fn tokenize(text: &str) -> Vec<String> {
    text.split(|c: char| !c.is_alphanumeric())
        .filter(|t| !t.is_empty())
        .map(str::to_lowercase)
        .collect()
}
 
struct Doc {
    tf: HashMap<String, f64>, // term → weighted count across fields
    len: f64,                 // total tokens across fields, unweighted
}
 
pub struct Bm25 {
    docs: Vec<Doc>,
    df: HashMap<String, usize>, // term → number of docs containing it
    avgdl: f64,
}
 
impl Bm25 {
    /// Each doc is a list of fields, each field scored with `weights[i]`.
    /// One field with weight 1.0 is plain BM25.
    pub fn new(docs: &[Vec<&str>], weights: &[f64]) -> Self {
        let mut df = HashMap::new();
        let docs: Vec<Doc> = docs
            .iter()
            .map(|fields| {
                let mut tf = HashMap::new();
                let mut len = 0.0;
                for (field, w) in fields.iter().zip(weights) {
                    for t in tokenize(field) {
                        *tf.entry(t).or_insert(0.0) += w;
                        len += 1.0;
                    }
                }
                for t in tf.keys() {
                    *df.entry(t.clone()).or_insert(0) += 1;
                }
                Doc { tf, len }
            })
            .collect();
        let avgdl = docs.iter().map(|d| d.len).sum::<f64>() / docs.len().max(1) as f64;
        Bm25 { docs, df, avgdl }
    }
 
    /// Robertson–Spärck Jones IDF. Negative for terms in more than half the docs,
    /// so clamp it the way FTS5 does.
    fn idf(&self, term: &str) -> f64 {
        let n = self.docs.len() as f64;
        let df = *self.df.get(term).unwrap_or(&0) as f64;
        let idf = ((n - df + 0.5) / (df + 0.5)).ln();
        if idf <= 0.0 { 1e-6 } else { idf }
    }
 
    pub fn score(&self, query: &str, doc: usize) -> f64 {
        let d = &self.docs[doc];
        let norm = K1 * (1.0 - B + B * d.len / self.avgdl);
        tokenize(query)
            .iter()
            .filter_map(|t| d.tf.get(t).map(|&f| (t, f)))
            .map(|(t, f)| self.idf(t) * f * (K1 + 1.0) / (f + norm))
            .sum()
    }
 
    /// (doc index, score), best first; docs matching no term are left out.
    pub fn search(&self, query: &str) -> Vec<(usize, f64)> {
        let mut hits: Vec<_> = (0..self.docs.len())
            .map(|i| (i, self.score(query, i)))
            .filter(|&(_, s)| s > 0.0)
            .collect();
        hits.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
        hits
    }
}
 
#[cfg(test)]
mod tests {
    use super::*;
 
    fn plain(texts: &[&'static str]) -> Bm25 {
        let docs: Vec<Vec<&str>> = texts.iter().map(|t| vec![*t]).collect();
        Bm25::new(&docs, &[1.0])
    }
 
    #[test]
    fn rare_terms_outweigh_common_ones() {
        let ix = plain(&["rust rust code", "rust code", "rust", "rust", "borrow"]);
        assert!(ix.idf("borrow") > ix.idf("code"));
        assert_eq!(ix.idf("rust"), 1e-6); // in 4 of 5 docs: clamped
    }
 
    #[test]
    fn repeats_saturate() {
        let ix = plain(&["cat", "cat cat cat cat cat cat cat cat", "dog", "dog", "dog"]);
        let (one, eight) = (ix.score("cat", 0), ix.score("cat", 1));
        assert!(eight > one && eight < 2.2 * one); // 8x the count, nowhere near 8x the score
    }
 
    #[test]
    fn shorter_doc_wins_on_equal_counts() {
        let ix = plain(&["index", "index of the whole archive", "x", "y", "z"]);
        assert!(ix.score("index", 0) > ix.score("index", 1));
    }
 
    #[test]
    fn id_field_weight_pins_the_element() {
        // fields: [title, ident, body], with the id field weighted highest
        let docs = vec![
            vec!["Spec 040", "FR-012", "Requests are retried three times."],
            vec!["Spec 040", "FR-013", "See FR-012 for retries."],
            vec!["Spec 041", "FR-001", "Nothing about it."],
        ];
        let ix = Bm25::new(&docs, &[5.0, 10.0, 1.0]);
        assert_eq!(ix.search("FR-012")[0].0, 0);
    }
}

Notes on the Rust:

tf holds weighted counts (f64), while len counts tokens unweighted. That’s the FTS5 split: weights change how much a match is worth, not how long the document is.
total_cmp gives a total order on f64, so sorting can’t panic on NaN. Ties break by doc index, matching FTS5’s ORDER BY s, rowid.
The search scores every document. That’s fine for a note but not for a real index. Real engines walk an inverted index (term → postings list of docs) and touch only the documents containing a query term, using tricks like WAND to skip low scorers.

BM25 vs vectors

	BM25 (sparse)	Embeddings (dense)
Matches	Exact tokens, after stemming	Meaning, including paraphrase
Strong on	Ids (`FR-012`), names, rare jargon, numbers	”Notes about this idea” when you don’t know the words
Weak on	Synonyms and paraphrase (vocabulary mismatch)	Exact identifiers, negation, rare terms the model never saw
Needs	A tokenizer	An embedding model, vectors, re-embedding on a model change
Explainable	Yes, every term’s contribution is visible	Mostly no

They fail in different places, so hybrid search runs both and fuses the ranked lists. The usual choice is reciprocal rank fusion, $\sum_{lists} \frac{1}{60 + rank} .$ It only uses ranks, so the two score scales never have to be calibrated against each other. qmd does the same over this vault (search is BM25, vsearch is vectors, and query is both plus a reranker).


✅ Strong baseline	Often hard to beat on keyword-heavy corpora, and a common reference point in IR benchmarks (BEIR).
✅ Cheap and local	Builds in seconds, runs in SQLite, needs no GPU.
✅ Exact	Identifiers and rare terms rank where you expect.
❌ Vocabulary mismatch	”retries” won’t match “attempts again”. Stemming helps a little, vectors or query expansion help more.
❌ Bag of words	Word order and negation are ignored, so “MUST” and “MUST NOT” look nearly identical.
❌ Tokenizer-dependent	Results hinge on how `FR-012`, `40-file` or `C++` are split. Stemming can over-match (`rust` → rustle).

RRF: fusing BM25 with vector search
Hit@K, MRR, Partial@K, Recall@K: how to measure whether BM25 helped
Bytes, AI, QMD, Semantic search over an Obsidian vault
Robertson & Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond (2009)
SQLite FTS5: the bm25() function

Algos, Information Retrieval, BM25

Formula

The three ideas

Worked example

Weighted fields (how FTS5 does it)

Implementation (Rust)

BM25 vs vectors

Strengths and blind spots

Related