BM𝒳: A Freshly Baked Take on BM25

We are proud to announce that researchers from Mixedbread and the Hong Kong Polytechnic University have developed a new lexical search algorithm, BMX, that outperforms the current standard BM25 across the board and is easy to use via Mixedbread's open-source Baguetter library.

Read on to learn about BMX, how it works, our benchmarks, and how to use it in practice. If you want to jump right in, you can look into the paper and the library right here:

• BMX Paper: Our research paper covering the approach in more academic detail.
• Baguetter: Our reference implementation of BMX and an easy to hack testing framework for information retrieval.

What is BMX?

Most text search engines are powered by lexical (keyword) search algorithms, the most prominent of which is BM25. It powers search engines for web search, e-commerce, legal search engines, and many more applications. A key strength of BM25 is that it performs really well in an out of distribution setting, meaning that it generalizes well on data it has not seen before. However, the keyword search approach comes with its own limitations:

1. BM25 does not consider the similarity between the query and any given document, which could enable a more accurate assessment of this document's relevance to the query.
2. Lexical search algorithms lack semantic understanding and are therefore unable to deal with linguistic nuances like synonyms and homonyms. This limitation is a key factor in the underperformance of lexical search compared to domain-specific text embedding-based semantic search.

To tackle these challenges, we propose BMX, a lexical search algorithm that incorporates both similarity and semantics. It comes with these key innovations:

1. Entropy-weighted similarity: We adjust the similarity scores between query tokens and related documents based on the entropy of each token. This approach reduces the influence of common tokens, allowing less frequent but more meaningful tokens to have a greater impact on the similarity score.

2. Weighted query augmentation (WQA): To incorporate semantics into lexical search, we developed a method that processes both the original query and its augmented versions simultaneously within BMX. This approach removes the need for multiple retrievals and reranking steps, leading to increased efficiency.

How does BMX work?

Now, we will explore the core scoring algorithm in BMX as well as weighted query augmentation (WQA). This will be a math-heavy section, but please bear with us!

Performance and Benchmarking

To validate our ideas and assess the performance of BMX, we evaluated it extensively on different benchmarks including BEIR, BRIGHT, and some multilingual benchmarks. You can find a full overview of our benchmarking in the BMX paper. Our results show that BMX outperforms BM25 across the board and can offer a significant improvement in retrieval quality.

BEIR

BEIR is a benchmark focused on out-of-domain information retrieval. It covers datasets for different domains, document or query lengths, and tasks. After evaluation on the 15 available benchmarks, we compare BMX to the implementations of BM25 in Baguetter and the bm25s library:

As the table shows, BMX generally outperforms all BM25 variants, achieving the best results on 11 out of 15 datasets. In our view, this underscores the importance of incorporating query-document similarity in our search algorithm.

Other than that, we also observe that embedding-based models consistently outperform lexical models, which can be attributed to their powerful semantic understanding. However, due to their significant advantage regarding resource requirements, lexical search algorithms still remain much more widely used.

BRIGHT

BRIGHT was introduced as the first text retrieval benchmark requiring intensive reasoning to retrieve the relevant documents. The benchmark includes 1,385 real-world queries across diverse domains such as StackExchange, LeetCode, and math competitions. These queries are paired with, for example, relevant web pages linked in StackExchange answers and theorems tagged in math Olympiad questions, all of which necessitate deliberate reasoning to identify their connections to the respective queries. For this evaluation, we also took a look at the performance of BMX with WQA.

The table demonstrates that BMX with weighted query augmentation outperforms all baselines, including embedding models and other lexical models. We attribute this to BMX's ability to generalize effectively across various domains, while embedding models often struggle with out-of-domain data. The results highlight that the WQA mechanism successfully enhances BMX’s semantic understanding, enabling it to handle realistic retrieval scenarios more effectively than alternative solutions. Also, BMX achieves this without the need for costly training on massive high-quality datasets, as would be required for embedding models.

Multilingual Benchmark

To verify the performance of BMX on multilingual data, we also performed benchmarking on datasets for Chinese, Japanese, Korean, German, and French retrieval tasks.

The table presents the evaluation results, demonstrating that BMX consistently outperforms BM25 across these multilingual datasets. This suggests the increased effectiveness of BMX in handling diverse multilingual information retrieval tasks.

Try it out

Installation

Before you start, make sure to install the Baguetter library:

pip install baguetter

Usage

The following examples show how to use BMX in practice:

from baguetter.indices import BMXSparseIndex
 
# Initialize BM𝒳 index
bmx = BMXSparseIndex()
 
# Add bakery items to the index
docs = [
    "Freshly crusty baked sourdough bread with a crispy crust",
    "Flaky croissants made with French butter",
    "Chocolate chip cookies with chunks of dark chocolate",
    "Cinnamon rolls with cream cheese frosting",
    "Artisanal baguettes with a soft interior and crusty exterior"
]
keys = list(range(len(docs)))
 
bmx.add_many(keys=keys, values=docs)
 
# Search for bread
query = "crusty bread"
results = bmx.search(query, top_k=2)
 
print(results)
# SearchResults(keys=[0, 4], scores=array([2.5519667 , 0.97304875], dtype=float32), normalized=False)

Why does this matter?

Improving the quality of lexical search without a significant increase in complexity or computational resource requirements could lead to a range of beneficial outcomes. Using BMX could improve the user experience of any application that relies on search algorithms. We also expect performance benefits for natural language processing applications that include our algorithm as part of their pipeline.

We're excited to hear about the community's opinions on BMX and where this algorithm could be used in the future. If you want to give us feedback or discuss anything search- or machine learning-related, please come join our Discord community.

@article{li2024bmx,
      title={BMX: Entropy-weighted Similarity and Semantic-enhanced Lexical Search},
      author={Xianming Li and Julius Lipp and Aamir Shakir and Rui Huang and Jing Li},
      year={2024},
      eprint={2408.06643},
      archivePrefix={arXiv},
      primaryClass={cs.IR},
      url={https://arxiv.org/abs/2408.06643},
}