BM25S: Orders of magnitude faster lexical search via eager sparse scoring

🌈 Abstract

The article introduces BM25S, an efficient Python-based implementation of the BM25 lexical search algorithm that achieves significant speedups compared to existing Python-based and Java-based implementations. The key points are:

• BM25S eagerly computes BM25 scores during indexing and stores them in sparse matrices, enabling faster slicing and summations at query time.
• BM25S reproduces the exact implementation of five BM25 variants by extending the eager scoring approach to non-sparse variants using a novel score shifting method.
• BM25S includes a fast Python-based tokenizer that combines Scikit-Learn's text splitting, Elastic's stopword list, and an optional C-based Snowball stemmer.
• BM25S achieves up to 500x speedup compared to popular Python-based frameworks and considerable speedups compared to highly optimized Java-based implementations.

🙋 Q&A

[01] Background

1. What are the key advantages of sparse lexical search algorithms like BM25 compared to other approaches?

• Sparse lexical search algorithms like BM25 do not need to be trained, can be applied to multiple languages, and are generally faster, especially when using highly efficient Java-based implementations.

2. What are the limitations of existing Python-based BM25 implementations?

• Existing Python-based BM25 implementations, such as Rank-BM25, are slower compared to the highly optimized Java-based implementations used by popular commercial products like Lucene and Elasticsearch.

3. What are the key ideas behind the BM25S approach proposed in this work?

• BM25S achieves significant speedups by:
  • Eagerly calculating all possible BM25 scores during indexing and storing them in sparse matrices.
  • Using a novel score shifting method to extend the eager scoring approach to non-sparse BM25 variants.
  • Implementing a fast Python-based tokenizer that combines Scikit-Learn's text splitting, Elastic's stopword list, and an optional C-based Snowball stemmer.

[02] Implementation

1. How does BM25S calculate the BM25 score for a given query and document?

• BM25S reformulates the BM25 score equation to enable eager calculation of the term frequency (TF) and inverse document frequency (IDF) during indexing, rather than at query time.
• This allows BM25S to store the pre-computed scores in sparse matrices, which can be efficiently sliced and summed at query time.

2. How does BM25S handle non-occurrence scores for variants like BM25L and BM25+?

• For variants where the score is non-zero when a term does not occur in a document, BM25S uses a novel "score shifting" method to maintain sparsity.
• It subtracts the non-occurrence score from each token and document in the score matrix, and then adds the non-occurrence score back during retrieval.

3. What techniques does BM25S use for efficient top-k selection during querying?

• BM25S implements top-k selection using the Quickselect algorithm, which has an average time complexity of O(n), compared to O(n log n) for sorting.
• It provides two implementations: one based on NumPy's argpartition and another using JAX's top-k implementation, with the JAX version performing better in practice.

[03] Benchmarks

1. How does the throughput of BM25S compare to other Python-based BM25 implementations?

• BM25S achieves over 100x higher throughput compared to Rank-BM25 in 10 out of the 14 BEIR benchmark datasets, with a maximum speedup of 500x.

2. What is the impact of different tokenization options on the performance of BM25S?

• Adding a stemmer improves the performance of BM25S on average, while the impact of stopwords is more dataset-dependent.

3. How do the different BM25 implementation variants (Lucene, ATIRE, BM25-PT, etc.) compare in terms of retrieval performance?

• Most implementations achieve similar average performance, with the exception of Elasticsearch, which achieves a marginally higher score.
• The differences in performance can be attributed to the varying tokenization schemes used by the different implementations.

</output_format>