BM25 and hybrid search, explained

BM25 is a ranking function that scores how well a document matches a query from the query words the document contains. Robertson and Zaragoza's monograph, The Probabilistic Relevance Framework: BM25 and Beyond, published in 2009, calls it the best-known instantiation of the classical probabilistic model of retrieval, a model developed over about 30 years with a precursor in 1960. Vector search compares meanings instead of words. Hybrid search runs both and merges the two ranked lists, and the merge rule decides which passage a reader, or a language model, sees first.

What BM25 scores

The score for a document is a sum over the query terms. Each term's contribution has three parts.

• Rarity. With no relevance information, the term weight reduces to a form of inverse document frequency (IDF): log((N - n + 0.5) / (n + 0.5)), where N is the number of documents in the collection and n is the number containing the term. A word found in few documents counts for more.
• Repetition, with a ceiling. The monograph calls this saturation: one term's contribution cannot exceed a saturation point, however often it occurs. With a high k1, extra occurrences keep adding to the score; with a low k1, each new occurrence adds little.
• Length. A soft normalization, B = (1 - b) + b × dl / avdl, compares the document's length dl with the collection average avdl. Setting b to 1 gives full length normalization; setting it to 0 switches normalization off.

The authors state that the model gives no guidance on setting these parameters. Experiments suggest values of b between 0.5 and 0.8 and k1 between 1.2 and 2 work reasonably well in many circumstances, with the best values depending on the documents and queries. Common defaults sit outside both ranges: the BEIR benchmark and the Dense Passage Retriever (DPR) paper both ran BM25 with k1 = 0.9 and b = 0.4.

Why keyword search still wins on exact terms

BEIR, by Thakur and colleagues, evaluated 10 retrieval systems on 18 datasets from varied tasks and domains, mostly without training on the target data, a setting the authors call zero-shot. They conclude that BM25 remains a strong baseline for zero-shot text retrieval. BM25 trailed the neural methods by 7 to 18 points on the in-domain dataset most of them were trained on, yet outperformed many of them elsewhere. Dense retrievers underperformed on datasets with a large shift in domain or task from their training data.

The DPR authors explain the difference. BM25 is sensitive to highly selective keywords and phrases, while a dense retriever may lack the capacity to represent salient phrases that appear rarely; in one example, DPR missed the name "Thoros of Myr". Sciavolino and colleagues built EntityQuestions, a set of simple questions about named entities, and found DPR's top-20 retrieval accuracy averaged 49.7% against 72.0% for BM25.

Part numbers, equipment designations, and acronyms are rare, selective strings of this kind, though none of these benchmarks tests them directly. The Sentence Transformers documentation states the other side: lexical search "will not recognize synonyms, acronyms or spelling variations." Both hold. Keyword matching wins when the same string appears in the query and the passage, and misses when one side uses an acronym and the other spells it out.

What the benchmark numbers leave out

BEIR cautions about its own results. Many of its datasets were annotated from candidates found by keyword systems, and a relevant passage with no word overlap that no annotator saw counts as irrelevant. That disfavors dense retrieval.

Pooling is one remedy. The Text REtrieval Conference (TREC), started in 1992 and co-sponsored by the National Institute of Standards and Technology (NIST) and the U.S. Department of Defense, pools the results that participants' systems return and judges the retrieved documents. BEIR's TREC-COVID set was built by pooling, and the bias remained. In that set, 31.8% of one dense model's top-10 results had never been judged, against 6.4% for BM25. After the BEIR authors judged the gaps, another dense model's normalized discounted cumulative gain at rank 10 (nDCG@10) rose from 0.654 to 0.735. A high keyword score can partly reflect how the judgments were collected.

Hybrid search and reciprocal rank fusion

Hybrid search merges keyword and vector results. The DPR paper used a weighted sum, reranking the union of each method's top 2,000 passages by the BM25 score plus 1.1 times the vector similarity. Results improved "in some cases": top-20 accuracy on CuratedTREC rose from 79.8% to 85.2%, but on Natural Questions fell from 78.4% to 76.6%.

Reciprocal rank fusion (RRF), presented by Cormack, Clarke, and Büttcher in July 2009, uses ranks only, ignoring the arbitrary scores of each method. A document's score is the sum over all input lists of 1 / (k + rank), with k = 60 fixed during a pilot study and not altered afterward. In the pilot, 60 was near-optimal, and values from 10 to 100 gave mean average precision between .2123 and .2147. The constant limits the pull of an outlier system. Across the pilot and TREC experiments, RRF beat the best single system and two established fusion methods by 4% to 5% on average.

The arithmetic shows the effect. A passage ranked first by BM25 and third by vector search scores 1/61 + 1/63, about 0.0323. A passage ranked first by one method and missing from the other scores 1/61, about 0.0164. Agreement outweighs a single first place.

Bruch, Gai, and Ingber, in a 2022 study revised in May 2023, found RRF sensitive to its parameters, contrary to existing studies, and a tuned weighted sum better both in and out of domain, needing only a small set of training examples.

What to check

• Which BM25 variant is used, with which k1 and b, and were they tuned on these documents?
• Does the test set include exact part numbers and acronyms, and the same items spelled out?
• How are keyword and vector results merged: RRF with which k, or a weighted sum with which weight, tuned on which queries?
• Were the relevance judgments pooled from both keyword and vector results, or from one kind only?
• Are results reported per dataset or query type? BEIR found no single approach consistently best on all datasets.

Azcuna's BABEL reads, translates, and searches foreign-language documents entirely on-device, with no cloud and no connection, and keeps every claim tied to the passage it came from.

Sources

1. 1The Probabilistic Relevance Framework: BM25 and Beyond · Foundations and Trends in Information Retrieval, vol. 3, no. 4 (2009); author copy archived by the Internet Archive
2. 2BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models · arXiv (Thakur et al., NeurIPS 2021 Datasets and Benchmarks track)
3. 3Dense Passage Retrieval for Open-Domain Question Answering · arXiv (Karpukhin et al., 2020)
4. 4Simple Entity-Centric Questions Challenge Dense Retrievers · arXiv (Sciavolino et al., EMNLP 2021)
5. 5Retrieve & Re-Rank · Sentence Transformers documentation
6. 6Text REtrieval Conference (TREC) Overview · National Institute of Standards and Technology
7. 7Reciprocal Rank Fusion outperforms Condorcet and individual Rank Learning Methods · Cormack, Clarke, and Büttcher (SIGIR 2009), University of Waterloo copy
8. 8An Analysis of Fusion Functions for Hybrid Retrieval · arXiv (Bruch, Gai, and Ingber; revised May 2023)

Where this shows up in our work

• TRACE, the offline S1000D and IETM viewer opens S1000D, MIL-STD-3001 and PDF technical manuals on a tablet with every marking intact.
• BABEL, offline multilingual translation and search translates and searches foreign-language documents on-device, every fact tied to its source passage.