6 ms·

Understanding the BM25 full text search algorithm

305 points by rrampage 2y ago

jankovicsandras 2y ago
Shameless plug: https://github.com/jankovicsandras/plpgsql_bm25 https://github.com/jankovicsandras/plpgsql_bm25 https://github.com/jankovicsandras/bm25opt https://github.com/jankovicsandras/bm25opt
- mark_l_watson 2y ago
  Thanks, yesterday I was thinking of adding BM25 to a little side project, so a well timed plug! Do you know of any pure Python wrapper projects for managing large numbers of text and PDF documents? I thought of using Solr or ElasticSearch but that seems too heavy weight for what I am doing. I am considering using SQLite with pysqlite3 and PyPDF2 since SQLite uses BM25. Sorry to be off topic, but I imagine many people are looking at tools for building hybrid BM25 / vector store / LLM applications.
  - rogerbinns 2y ago
    My project APSW may have exactly what you need. It wraps SQLite proving a Python API, and that includes the FTS5 full text search functionality. https://rogerbinns.github.io/apsw/textsearch.html https://rogerbinns.github.io/apsw/textsearch.html You can store your text and PDFs in SQLite (or their filenames) and use the FTS5 infrastructure to do tokenization, query execution, and ranking. You can write your own tokenizer in Python, as well as ranking functions. A pure Python tokenizer for HTML is included, as well as a pure Python implementation of BM25. You can chain tokenizers so it is just a few lines of code to call pypdf's extract_text method, and then have the bundled UnicodeWords tokenizer properly extract tokens/words, and Simplify to do case folding and accent stripping if desired. There is a lot more useful functionality, all done from Python. You can see code in action in the example/tour at https://rogerbinns.github.io/apsw/example-fts.html https://rogerbinns.github.io/apsw/example-fts.html
    - radiator 2y ago
      Thank you for publishing your work. Do you know of any similar projects with examples of custom tokenizers, e.g. for synonyms, snowball, but written in C?
      - rogerbinns 2y ago
        SQLite itself is in C so you can use the API directly https://www.sqlite.org/fts5.html#custom_tokenizers https://www.sqlite.org/fts5.html#custom_tokenizers The text is in UTF8 bytes so any C code would have to deal with that and mapping to Unicode codepoints, plus lots of other text processing so some kind of library would also be needed. I don't know of any.
    - mark_l_watson 2y ago
      Thank you, your project meets my requirements. I want to build a long memory RAG system for my personal data. I like the commercial offerings like Google Gemini integrated with Workplace data, but I think I would be happier with my own system.
- softwaredoug 2y ago
  If we're shameless plugging passion projects, SearchArray is a pandas extension for fulltext (BM25) search for dorking around with things in google colab https://github.com/softwaredoug/searcharray https://github.com/softwaredoug/searcharray I'll also plug Xing Han Lu's BM25S which is very popular with similar goals: https://github.com/xhluca/bm25s https://github.com/xhluca/bm25s
jll29 2y ago
Nice write-up. A few more details/background that are harder to find: "BM25" stands for "Best Matching 25", "best matching" becaue it is a formula for ranking and term weighting (the matching refers to the term in the query versus the document), and the number 25 simply indicates a running number (there were 24 earlier formula variants and some later ones, but #25 turned out to work best, so it was the one that was published). It was conceived by Stephen Robertson and Karen Spärck Jones (the latter of IDF fame) and first implemented in the former's OKAPI information retrieval (research) system. The OKAPI system was benchmarked at the annual US NIST TREC (Text Retrieval Conference) for a number of years, the international "World Champtionship" of search engine methods (although the event is not about winning, but about compariing notes and learning from each other, a highly recommended annual event held every November in Gaithersburg, Maryland, attended by global academic and industry teams that conduct research on improving search - see trec.nist.gov). Besides the "bag of words" Vector Space Model (sparse vectors of terms), the Probabilistic Modles (that BM25 belongs to), there are suprising and still growing number of other theoretical frameworks how to rank a set of documents, given a query ("Divergence from Randomness", "Statistical Language Modeling, "Learning to Rank", "Quantum Information Retrieval", "Neural Ranking" etc.). Conferences like ICTIR and SIGIR still publish occasionaly entirely new paradigms for search. Note that the "Statistical Language Modeling" paradigm is not about Large Language Models that are on vogue now (that's covered under the "Neural Retrieval" umbrella), and that "Quantum IR" is not going to get you to a tutorial about Quantum Information Retrieval but to methods of infrared spectroscopy or a company with the same name that produces cement; such are the intricacies of search technology, even in the 21st century. If you want to play with BM25 and compare it with some of the alternatives, I recommend the research platform Terrier, and open-source search engine developed at the University of Glasgow (today, perhaps the epicenter of search research). BM25 is over a quarter century old, but has proven to be a hard baseline to beat (it is still often used as a reference point for comparing new nethods against), and a more recent variant, BM24F, can deal with multiple fields and hypertext (e.g. title, body of documents, hyperlinks). The recommended paper to read is: Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). "A probabilistic model of information retrieval: Development and comparative experiments: Part 1". Information Processing & Management 36(6): 779–808, and its successor, Part 2. (Sadly they are not open access.)
- 2y ago
sidcool 2y ago
Good article. I am genuinely interested to learn about how to think of problems in such a mathematical form. And how to test it. Any resources?
RA_Fisher 2y ago
BM25 is an ancient algo developed in the 1970s. It’s basically a crappy statistical model and statisticians can do far better today. Search is strictly dominated by learning (that yes, can use search as an input). Not many folks realize that yet, and / or are incentivized to keep the old tech going as long as possible, but market pressures will change that.
- netdur 2y ago
  While BM25 did emerge from earlier work in the 1970s and 1980s (specifically building on the probabilistic ranking principle), I'm curious about your perspective on a few things: What specific modern statistical approaches are you seeing as superior replacements for BM25 in practical applications? I'm particularly interested in how they handle edge cases like rare terms and document length normalization that BM25 was explicitly designed to address. While I agree learning-based approaches have shown impressive results, could you elaborate on what you mean by search being "strictly dominated" by learning methods? Are you referring to specific benchmarks or real-world applications?
  - RA_Fisher 2y ago
    BM25 can be used as a starting point for a statistical learning model and more readily built on. A key advantage is that one gains a systematic way to reduce edge cases, instead of handling a couple, bc they’re so large as to be noticeable.
- simplecto 2y ago
  Those are some really spicy opinions. It would seem that many search experts might not agree. David Tippet (formerly opensearch and now at Github) A great podcast with David Tippet and Nicolay Gerold entitled: "BM25 is the workhorse of search; vectors are its visionary cousin" https://www.youtube.com/watch?v=ENFW1uHsrLM https://www.youtube.com/watch?v=ENFW1uHsrLM
  - dumb1224 2y ago
    Agreed. In the 2000s it was all about BM25 in the NLP community. I hardly see any paper that did not mention it in my opinion.
hubraumhugo 2y ago
Given the recent advances in vector-based semantic search, what's the SOTA search stack that people are using for hybrid keyword + semantic search these days?
- emschwartz 2y ago
  Most of the commercial and open source offerings for hybrid search seem to be using BM25 + vector similarity search based on embeddings. The results are combined using Reciprocal Rank Fusion (RRF). The RRF paper is impressive in how incredibly simple it is (the paper is only 2 pages): https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
  - TeenGirlza17 2y ago
    [flagged]
  - softwaredoug 2y ago
    A warning that RRF is often not Enough, as it can just drag a good solution down towards the worse solution :) https://softwaredoug.com/blog/2024/11/03/rrf-is-not-enough https://softwaredoug.com/blog/2024/11/03/rrf-is-not-enough
    - emschwartz 2y ago
      Ah, that's great! Thanks for sharing that. I had actually implemented full text search + vector search using RRF but I kept it disabled by default because it wasn't meaningfully improving my results. This seems like a good hypothesis as to why.
- d4rkp4ttern 2y ago
  In the Langroid[1] LLM library we have a clean, extensible RAG implementation in the DocChatAgent[2] -- it uses several retrieval techniques, including lexical (bm25, fuzzy search) and semantic (embeddings), and re-ranking (using cross-encoder, reciprocal-rank-fusion) and also re-ranking for diversity and lost-in-the-middle mitigation: [1] Langroid - a multi-agent LLM framework from CMU/UW-Madison researchers https://github.com/langroid/langroid https://github.com/langroid/langroid [2] DocChatAgent Implementation - https://github.com/langroid/langroid/blob/main/langroid/agent/special/doc_chat_agent.py https://github.com/langroid/langroid/blob/main/langroid/agen... Start with the answer_from_docs method and follow the trail. Incidentally I see you're the founder of Kadoa -- Kadoa-snack is one of favorite daily tools to find LLM-related HN discussions!
deleted 2y ago
[deleted]
DavidPP 2y ago
We use https://typesense.org/ https://typesense.org/ for regular search, but it now has support for doing hybrid search, curious if anyone has tried it yet?
- kkielhofner 2y ago
  I've used it for hybrid search and it works quite well. Overall I'm really happy to see Typesense mentioned here. A lot of the smaller scale RAG projects, etc you see around would be well served by Typesense but it seems to be relatively unknown for whatever reasons. It's probably one of the easiest solutions to deploy, has reasonable defaults, good docs, easy clustering, etc while still be very capable, performant, and powerful if you need to dig in further.
- fogx 2y ago
  we use it and are fairly happy. but provider latency is insanely high (500ms+) for embedding models. best to host on-cluster. hybrid quality is good but modification options are extremely limited and the score very obscure for anything but ranking within the set.
tselvaraj 2y ago
Hybrid search solves the long-standing challenge of relevance with search results. We can use ranking fusion between keyword and vector to create a hybrid search that works in most scenarios.
MPSimmons 2y ago
Does anyone know if the average document length mentioned in the document length normalization is median? It seems like it would need to be to properly deweight excessively long documents, otherwise the excessively long documents would unfairly weight the average, right?
- softwaredoug 2y ago
  It’s the mean. At least in Lucene. Using median would be an interesting experiment. Do you know of a search dataset with very large document length differences? MSMarco for example is pretty consistent in length.
  - MPSimmons 2y ago
    Was just thinking about some of the docs we have at work, and how most are relatively short ( probably < 10 pages) and some are like... 200+ page government things

305 points by rrampage 2y ago

Shameless plug: https://github.com/jankovicsandras/plpgsql_bm25 https://github.com/jankovicsandras/plpgsql_bm25 https://github.com/jankovicsandras/bm25opt https://github.com/jankovicsandras/bm25opt

mark_l_watson 2y ago
Thanks, yesterday I was thinking of adding BM25 to a little side project, so a well timed plug! Do you know of any pure Python wrapper projects for managing large numbers of text and PDF documents? I thought of using Solr or ElasticSearch but that seems too heavy weight for what I am doing. I am considering using SQLite with pysqlite3 and PyPDF2 since SQLite uses BM25. Sorry to be off topic, but I imagine many people are looking at tools for building hybrid BM25 / vector store / LLM applications.
- rogerbinns 2y ago
  My project APSW may have exactly what you need. It wraps SQLite proving a Python API, and that includes the FTS5 full text search functionality. https://rogerbinns.github.io/apsw/textsearch.html https://rogerbinns.github.io/apsw/textsearch.html You can store your text and PDFs in SQLite (or their filenames) and use the FTS5 infrastructure to do tokenization, query execution, and ranking. You can write your own tokenizer in Python, as well as ranking functions. A pure Python tokenizer for HTML is included, as well as a pure Python implementation of BM25. You can chain tokenizers so it is just a few lines of code to call pypdf's extract_text method, and then have the bundled UnicodeWords tokenizer properly extract tokens/words, and Simplify to do case folding and accent stripping if desired. There is a lot more useful functionality, all done from Python. You can see code in action in the example/tour at https://rogerbinns.github.io/apsw/example-fts.html https://rogerbinns.github.io/apsw/example-fts.html
  - radiator 2y ago
    Thank you for publishing your work. Do you know of any similar projects with examples of custom tokenizers, e.g. for synonyms, snowball, but written in C?
    - rogerbinns 2y ago
      SQLite itself is in C so you can use the API directly https://www.sqlite.org/fts5.html#custom_tokenizers https://www.sqlite.org/fts5.html#custom_tokenizers The text is in UTF8 bytes so any C code would have to deal with that and mapping to Unicode codepoints, plus lots of other text processing so some kind of library would also be needed. I don't know of any.
  - mark_l_watson 2y ago
    Thank you, your project meets my requirements. I want to build a long memory RAG system for my personal data. I like the commercial offerings like Google Gemini integrated with Workplace data, but I think I would be happier with my own system.
softwaredoug 2y ago
If we're shameless plugging passion projects, SearchArray is a pandas extension for fulltext (BM25) search for dorking around with things in google colab https://github.com/softwaredoug/searcharray https://github.com/softwaredoug/searcharray I'll also plug Xing Han Lu's BM25S which is very popular with similar goals: https://github.com/xhluca/bm25s https://github.com/xhluca/bm25s

jll29 2y ago

Nice write-up. A few more details/background that are harder to find: "BM25" stands for "Best Matching 25", "best matching" becaue it is a formula for ranking and term weighting (the matching refers to the term in the query versus the document), and the number 25 simply indicates a running number (there were 24 earlier formula variants and some later ones, but #25 turned out to work best, so it was the one that was published). It was conceived by Stephen Robertson and Karen Spärck Jones (the latter of IDF fame) and first implemented in the former's OKAPI information retrieval (research) system. The OKAPI system was benchmarked at the annual US NIST TREC (Text Retrieval Conference) for a number of years, the international "World Champtionship" of search engine methods (although the event is not about winning, but about compariing notes and learning from each other, a highly recommended annual event held every November in Gaithersburg, Maryland, attended by global academic and industry teams that conduct research on improving search - see trec.nist.gov). Besides the "bag of words" Vector Space Model (sparse vectors of terms), the Probabilistic Modles (that BM25 belongs to), there are suprising and still growing number of other theoretical frameworks how to rank a set of documents, given a query ("Divergence from Randomness", "Statistical Language Modeling, "Learning to Rank", "Quantum Information Retrieval", "Neural Ranking" etc.). Conferences like ICTIR and SIGIR still publish occasionaly entirely new paradigms for search. Note that the "Statistical Language Modeling" paradigm is not about Large Language Models that are on vogue now (that's covered under the "Neural Retrieval" umbrella), and that "Quantum IR" is not going to get you to a tutorial about Quantum Information Retrieval but to methods of infrared spectroscopy or a company with the same name that produces cement; such are the intricacies of search technology, even in the 21st century. If you want to play with BM25 and compare it with some of the alternatives, I recommend the research platform Terrier, and open-source search engine developed at the University of Glasgow (today, perhaps the epicenter of search research). BM25 is over a quarter century old, but has proven to be a hard baseline to beat (it is still often used as a reference point for comparing new nethods against), and a more recent variant, BM24F, can deal with multiple fields and hypertext (e.g. title, body of documents, hyperlinks). The recommended paper to read is: Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). "A probabilistic model of information retrieval: Development and comparative experiments: Part 1". Information Processing & Management 36(6): 779–808, and its successor, Part 2. (Sadly they are not open access.)

2y ago

sidcool 2y ago

Good article. I am genuinely interested to learn about how to think of problems in such a mathematical form. And how to test it. Any resources?

RA_Fisher 2y ago

BM25 is an ancient algo developed in the 1970s. It’s basically a crappy statistical model and statisticians can do far better today. Search is strictly dominated by learning (that yes, can use search as an input). Not many folks realize that yet, and / or are incentivized to keep the old tech going as long as possible, but market pressures will change that.

netdur 2y ago
While BM25 did emerge from earlier work in the 1970s and 1980s (specifically building on the probabilistic ranking principle), I'm curious about your perspective on a few things: What specific modern statistical approaches are you seeing as superior replacements for BM25 in practical applications? I'm particularly interested in how they handle edge cases like rare terms and document length normalization that BM25 was explicitly designed to address. While I agree learning-based approaches have shown impressive results, could you elaborate on what you mean by search being "strictly dominated" by learning methods? Are you referring to specific benchmarks or real-world applications?
- RA_Fisher 2y ago
  BM25 can be used as a starting point for a statistical learning model and more readily built on. A key advantage is that one gains a systematic way to reduce edge cases, instead of handling a couple, bc they’re so large as to be noticeable.
simplecto 2y ago
Those are some really spicy opinions. It would seem that many search experts might not agree. David Tippet (formerly opensearch and now at Github) A great podcast with David Tippet and Nicolay Gerold entitled: "BM25 is the workhorse of search; vectors are its visionary cousin" https://www.youtube.com/watch?v=ENFW1uHsrLM https://www.youtube.com/watch?v=ENFW1uHsrLM
- dumb1224 2y ago
  Agreed. In the 2000s it was all about BM25 in the NLP community. I hardly see any paper that did not mention it in my opinion.

hubraumhugo 2y ago

Given the recent advances in vector-based semantic search, what's the SOTA search stack that people are using for hybrid keyword + semantic search these days?

emschwartz 2y ago
Most of the commercial and open source offerings for hybrid search seem to be using BM25 + vector similarity search based on embeddings. The results are combined using Reciprocal Rank Fusion (RRF). The RRF paper is impressive in how incredibly simple it is (the paper is only 2 pages): https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
- TeenGirlza17 2y ago
  [flagged]
- softwaredoug 2y ago
  A warning that RRF is often not Enough, as it can just drag a good solution down towards the worse solution :) https://softwaredoug.com/blog/2024/11/03/rrf-is-not-enough https://softwaredoug.com/blog/2024/11/03/rrf-is-not-enough
  - emschwartz 2y ago
    Ah, that's great! Thanks for sharing that. I had actually implemented full text search + vector search using RRF but I kept it disabled by default because it wasn't meaningfully improving my results. This seems like a good hypothesis as to why.
d4rkp4ttern 2y ago
In the Langroid[1] LLM library we have a clean, extensible RAG implementation in the DocChatAgent[2] -- it uses several retrieval techniques, including lexical (bm25, fuzzy search) and semantic (embeddings), and re-ranking (using cross-encoder, reciprocal-rank-fusion) and also re-ranking for diversity and lost-in-the-middle mitigation: [1] Langroid - a multi-agent LLM framework from CMU/UW-Madison researchers https://github.com/langroid/langroid https://github.com/langroid/langroid [2] DocChatAgent Implementation - https://github.com/langroid/langroid/blob/main/langroid/agent/special/doc_chat_agent.py https://github.com/langroid/langroid/blob/main/langroid/agen... Start with the answer_from_docs method and follow the trail. Incidentally I see you're the founder of Kadoa -- Kadoa-snack is one of favorite daily tools to find LLM-related HN discussions!

deleted 2y ago

[deleted]

DavidPP 2y ago

We use https://typesense.org/ https://typesense.org/ for regular search, but it now has support for doing hybrid search, curious if anyone has tried it yet?

kkielhofner 2y ago
I've used it for hybrid search and it works quite well. Overall I'm really happy to see Typesense mentioned here. A lot of the smaller scale RAG projects, etc you see around would be well served by Typesense but it seems to be relatively unknown for whatever reasons. It's probably one of the easiest solutions to deploy, has reasonable defaults, good docs, easy clustering, etc while still be very capable, performant, and powerful if you need to dig in further.
fogx 2y ago
we use it and are fairly happy. but provider latency is insanely high (500ms+) for embedding models. best to host on-cluster. hybrid quality is good but modification options are extremely limited and the score very obscure for anything but ranking within the set.

tselvaraj 2y ago

Hybrid search solves the long-standing challenge of relevance with search results. We can use ranking fusion between keyword and vector to create a hybrid search that works in most scenarios.

MPSimmons 2y ago

Does anyone know if the average document length mentioned in the document length normalization is median? It seems like it would need to be to properly deweight excessively long documents, otherwise the excessively long documents would unfairly weight the average, right?

softwaredoug 2y ago
It’s the mean. At least in Lucene. Using median would be an interesting experiment. Do you know of a search dataset with very large document length differences? MSMarco for example is pretty consistent in length.
- MPSimmons 2y ago
  Was just thinking about some of the docs we have at work, and how most are relatively short ( probably < 10 pages) and some are like... 200+ page government things