Keyword Search and BM25

An index of words

A library's back-of-book index maps a word to the pages it appears on. Search engines do the same at scale: an inverted index maps every term to the documents containing it, with counts. To answer a query, look up its few terms and score only the documents on those lists. If you've built a database index on a column, you already know the idea.

Rare words count for more

"The" appears in almost every document, so matching it says nothing. "MinHash" appears in one or two, so matching it says a lot. Karen Spärck Jones proposed in 1972 weighting a term by its specificity, more for terms that occur in fewer documents Established, which became inverse document frequency:

$$\text{IDF}(t) = \log\left(1 + \frac{N - n_t + 0.5}{n_t + 0.5}\right),$$

where $N$ is the number of documents and $n_t$ the number containing term $t$.

BM25

BM25 adds two corrections to raw counts. The tenth mention of a word is less informative than the first, so term frequency saturates, controlled by $k_1$. A long document contains more words by chance, so its counts are normalised by length, controlled by $b$:

$$\text{score}(q, d) = \sum_{t \in q} \text{IDF}(t)\,\frac{f_{t,d}\,(k_1 + 1)}{f_{t,d} + k_1\left(1 - b + b\,\frac{|d|}{\text{avgdl}}\right)}.$$

Robertson and Zaragoza note that the model gives no guidance on setting these parameters, but that experiments suggest values such as 0.5 < b < 0.8 and 1.2 < k₁ < 2 are reasonably good in many circumstances Established. This chapter's labs use k₁ = 1.2 and b = 0.75.

Tiny example. 100 documents; "cache" appears in 5 of them, "memory" in 40. IDF(cache) = log(1 + 95.5/5.5) ≈ 2.91; IDF(memory) = log(1 + 60.5/40.5) ≈ 0.91. A document of average length that mentions "cache" twice gets, from that term, 2.91 × (2 × 2.2)/(2 + 1.2) ≈ 4.0; mentioning it ten times would give only 2.91 × 22/11.2 ≈ 5.7, not five times as much.

Why it's still here

Keyword search needs no training, explains itself (these words matched) and handles things embeddings blur: product codes, error messages, function names, people's names, version numbers. The BEIR benchmark, comparing ten retrieval systems zero-shot on 18 datasets, found BM25 a robust baseline, and many approaches that outperform BM25 in-domain performed poorly on BEIR's datasets Established. Its blind spot is vocabulary: a question that uses different words from the answer finds nothing. That's what semantic search is for.