PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xing Han Lù

arXiv:2407.03618v1cs.IRcs.CL

TL;DR

BM25S addresses slow Python-based BM25 search with eager score computation and sparse-matrix storage. It achieves over 100x higher throughput than Rank-BM25 on 10 of 14 BEIR datasets, with one 500x speedup.

  • Problem

    Existing Python-based BM25 implementations leave room for substantial speedups in lexical search.

    Source: §1 · p. 1

  • Method

    BM25S eagerly computes token-document scores during indexing and stores them in sparse matrices, extending the approach to variants with nonzero scores for absent terms.

    Source: §1 · p. 1, §2.1 · p. 3

  • Results

    Over 100x higher throughput than Rank-BM25 on 10 of 14 BEIR datasets, with a 500x speedup in one dataset.

    Source: §3 · p. 3

  • Takeaways & Limitations

    BM25S offers a focused Python implementation for sparse, mathematically accurate BM25 retrieval that can be used directly inside Python.

    Source: §4 · p. 4

    Its readable, extensible, fast implementation may not achieve the highest possible performance.

    Source: Limitations · p. 5

Abstract

from arXiv · show

We introduce BM25S, an efficient Python-based implementation of BM25 that only depends on Numpy and Scipy. BM25S achieves up to a 500x speedup compared to the most popular Python-based framework by eagerly computing BM25 scores during indexing and storing them into sparse matrices. It also achieves considerable speedups compared to highly optimized Java-based implementations, which are used by popular commercial products. Finally, BM25S reproduces the exact implementation of five BM25 variants based on Kamphuis et al. (2020) by extending eager scoring to non-sparse variants using a novel score shifting method. The code can be found at https://github.com/xhluca/bm25s

1 Background

BM25S seeks to speed Python-based BM25 by eagerly calculating scores during indexing and storing them in sparse matrices. It builds on BM25-PT while simplifying the implementation and extending it to other BM25 variants.

1 Background

  • BM25S eagerly calculates scores for future query tokens during indexing and stores them in sparse matrices to enable faster slicing and summation.This avoids computing token-document scores at query time, apart from straightforward summations.Source: §1 · p. 1
  • Unlike BM25-PT, BM25S uses SciPy sparse matrices and slices relevant indices and sums across the token dimension instead of multiplying matrices.BM25-PT precomputes scores with PyTorch and multiplies them by a bag-of-words query encoding.Source: §1 · p. 1
  • BM25S simplifies BM25-PT’s initial idea and introduces a strategy for generalizing eager scoring to other BM25 variants.Source: §1 · p. 1
  • BM25S provides a Python tokenizer combining Scikit-Learn text splitting, Elastic stopwords, and optional Snowball stemming, with better performance than BM25-PT’s subword tokenizers.Source: §1 · p. 1
  • BM25S selects top-k results in average O(n) time, with optional sorting of the selected results.Source: §1 · p. 1

2 Implementation

BM25S moves token-document scoring to indexing and stores scores sparsely, so retrieval can score documents through query-token selection and summation. The method also extends sparse scoring to BM25 variants with nonzero scores for absent tokens.

2 Implementation

  • BM25S defaults to Lucene’s BM25 scoring and eagerly computes token-document scores during indexing, avoiding query-time score calculations beyond summation.Tokens absent from a document have zero term frequency and therefore a zero score.Source: §2 · pp. 1–2
  • Retrieval selects query-token rows from the |V| × |C| sparse matrix and sums them across columns to produce document scores.CSC is chosen for column-wise slicing and summation, and the sparse operations are also replicated directly with NumPy arrays.Source: §2 · p. 2
  • Tokenization uses Scikit-Learn’s UTF-8-aware word-splitting pattern, optionally stems vocabulary words, and maps unique words to integer indices.Integer indices reduce memory use and support slicing Scipy matrices and NumPy arrays.Source: §2 · p. 2
  • Top-k selection uses partitioning in average O(n) time instead of sorting all n documents, with an additional O(k log k) sort when ordered results are requested.The implementation offers NumPy and JAX options; JAX performs better in practice, and optional pooled threading can further speed retrieval.Source: §2 · pp. 2–3

2.1 Extending sparsity via non-occurrence adjustments

  • Sparse scoring applies directly to Robertson’s original design, ATIRE, and Lucene, while BM25L, BM25+, and TFl◦δ◦p×IDF require non-occurrence score shifting.The method subtracts each token’s non-occurrence score before sparse storage, then adds the query-level sum of those scores during retrieval to recover exact scores.Source: §2 · p. 3, §2.1 · p. 3

3 Benchmarks

BM25S substantially outpaces Rank-BM25 on BEIR throughput, while tokenization choices and implementation variants are associated with differences in retrieval scores.

Throughput

  • Over 100x higher throughput in 10 of 14 BEIR datasets, with one 500x speedup, is reported for BM25S versus Rank-BM25.The benchmark uses publicly available BEIR datasets.Source: §3 · p. 3

Impact of Tokenization

  • Adding a stemmer improves average scores, while stopword effects are usually minimal but larger on TREC-COVID and ArguAna.The comparison uses BM25S Lucene with k1 = 1.5 and b = 0.75 across four tokenization settings.Source: §3 · p. 3, Table 2 · p. 4

Comparing model variants

  • Most implementations average between 39.7 and 40, while Elastic scores marginally higher; tokenizer differences may explain some variation.The comparison includes Elasticsearch, Pyserini, and five BM25 variants; Pyserini’s average is estimated because CQADupStack experiments ended with OOM errors.Source: §3 · p. 4, Table 3 · p. 4

4 Conclusion

BM25S uses eager sparse scoring to calculate BM25 scores, alongside fast tokenization and top-k selection. Its low-dependency Python implementation complements other retrieval tools and may make lexical search more accessible.

Conclusion

  • BM25S introduces a method for calculating BM25 scores and combines it with fast tokenization and efficient top-k selection.The implementation minimizes dependencies and runs directly inside Python.Source: §4 · p. 4
  • BM25S complements other tools: BM25-PT uses PyTorch, Rank-BM25 permits inference-time k1 changes, and Pyserini offers broader retrieval algorithms.BM25S focuses on sparse, mathematically accurate BM25 implementations using eager sparse scoring.Source: §4 · p. 4
  • The authors identify storage-limited settings and browser use through WebAssembly frameworks as potential applications for BM25S.They connect these possibilities to minimizing dependencies.Source: §4 · pp. 4–5

Limitations

The authors identify limits in tokenizer performance and benchmark coverage, and recommend considering other lexical search implementations when reporting results.

Limitations

  • The customized Python tokenizer prioritizes readability and extensibility, so it may not achieve the highest possible performance.The analyzer supports stemming and stopwords.Source: Limitations · p. 5
  • Benchmark reports should consider lexical search implementations beyond BM25S.The authors advise this in light of the tokenizer’s performance scope.Source: Limitations · p. 5
  • Experiments used free, readily available hardware, and less memory-efficient experiments terminated with OOM errors.This constrains which experiments completed under the reported setup.Source: Limitations · p. 5

A Appendix

The appendix describes a single-threaded, reproducible hardware setup and lists the BEIR datasets used in the experiments.

Hardware

  • Throughput was measured single-threaded on Kaggle free CPU instances with an Intel Xeon CPU at 2.20GHz and 30GB RAM.The authors describe this as reflecting consumer devices, which tend to have fewer cores and rarely exceed 32GB RAM.Source: A Appendix · p. 6

BEIR Datasets

  • The listed BEIR datasets include Arguana, Climate-FEVER, DBpedia-Entity, FEVER, FiQA, HotpotQA, MS MARCO, NQ, Quora, SciDocs, SciFact, TREC-COVID, and Touche-2020.The dataset names are accompanied by bibliography references in the appendix.Source: A Appendix · p. 6
  • The appendix identifies the Quora dataset with the First Quora Dataset Release.The dataset entry is linked to its source.Source: A Appendix · p. 6

Related papers

Loading 2407.03618v1…