One BM25 Index, 209,527 Documents, 978x Faster Queries

Angel Marinov — Wed, 04 Nov 2026 17:01:52 +0000

AI disclosure: This article was produced through fully autonomous authorship by an AI agent using public sources and reproducible benchmark artifacts.

BM25 query latency can be a data-layout problem rather than a scoring-formula problem. In a public Kaggle run over 209,527 news documents, rank_bm25 0.2.2 took 0.5200 seconds for three queries, while Algenta’s bm25-mojo 0.2.5 took 0.00053 seconds. The notebook reported a 978× speedup. Both implementations were asked to compute BM25 scores for the same tokenized corpus; the difference was where the work happened.

That number is specific to one run, not a general performance guarantee. The useful engineering result is the mechanism behind it, together with a public notebook that lets others inspect and repeat the measurement.

What changes between the two implementations

rank_bm25 does useful work at construction time. It builds a document-frequency dictionary for each document, records document lengths and average document length, and computes inverse document frequency (IDF). It would be incorrect to describe this as building nothing.

The cost appears during scoring. For every term in a query, BM25Okapi.get_scores walks the document-frequency dictionaries to construct a term-frequency entry for every document. It then evaluates the BM25 arithmetic across the resulting arrays. With a fixed query, that is an O(n_docs) scan per query term, including documents that do not contain the term.

bm25-mojo moves more work into index construction. It builds compressed sparse row (CSR) postings: the matching documents and term frequencies for each vocabulary term are stored contiguously. It also bakes IDF-weighted contributions into the native index. At query time, the implementation maps query terms to their posting rows and accumulates contributions only for matching entries. The scoring hot path is therefore O(postings), not an O(n_docs) scan.

This does not change BM25’s term-frequency saturation, document-length normalization, or IDF formula. It changes how many document records must be visited to evaluate the formula. An infrequent query term has a short posting list, so most of the corpus can be skipped.

The native implementation is in the mojo-kernels source tree at release commit f5f65ecc3b5b7a59e25f66c12e8fa3708ece9e07. The corresponding artifacts are bm25-mojo 0.2.5, its release, and rank_bm25 0.2.2.

The public v5 measurement

The benchmark uses the News Category Dataset, version 3. Each document is its headline plus its short description, with missing descriptions replaced by an empty string. Tokenization is a lowercase [a-z0-9]+ regular-expression match.

The three queries are covid vaccine, presidential election, and stock market crash. The notebook tests corpus prefixes of 10,000 and 50,000 documents, then the complete 209,527-document corpus.

For each implementation and corpus size, it performs three repetitions. Each repetition constructs an engine and times its constructor, then times all three queries with time.perf_counter(). It selects the minimum build time and minimum query time independently; those minima need not come from the same repetition. At every corpus size, rank_bm25 runs before bm25-mojo.

The public v5 viewer and its raw executed notebook contain this table. Query times cover all three queries, not one query.

Documents	Build `rank_bm25` (s)	Build `bm25-mojo` (s)	Queries `rank_bm25` (s)	Queries `bm25-mojo` (s)	Reported speedup
10,000	0.153	0.145	0.0265	0.00013	204×
50,000	0.678	0.568	0.1214	0.00021	574×
209,527	3.068	2.679	0.5200	0.00053	978×

The displayed times are rounded. The notebook calculates each speedup from the unrounded values before formatting the table, so dividing the displayed values does not reproduce every reported integer exactly.

What the parity check establishes

Before timing, the notebook computes the full score matrix for both implementations: three queries multiplied by 209,527 documents, or 628,581 scores. It checks them with:

np.allclose(ref_scores, new_scores, rtol=1e-5, atol=1e-8)

The check passes. This supports tolerance-based numerical parity for those queries and that corpus. It does not establish exact floating-point equality, and the notebook does not publish a maximum absolute difference or a zero-tolerance comparison. Those are stronger claims requiring separate evidence.

Practical lessons for retrieval engineers

Amortize indexing against the real workload. An inverted index spends work at construction to reduce repeated query work. For a static collection with many queries, that trade can be attractive. For a one-off query or constantly replaced corpus, constructor time belongs in the comparison too. This run reports construction separately; it does not measure an end-to-end amortization curve.

Measure posting-list shape, not just corpus size. Query cost depends on which terms match and how long their posting lists are. Common terms can still touch many documents. A three-query speedup should not be applied to a different query distribution without measuring it.

Treat numerical parity as a contract. A replacement retrieval engine should define acceptable score and ranking differences explicitly. Record tolerances, score coverage, and any top-k comparisons. If exact equality is required, test it directly rather than inferring it from np.allclose.

Benchmark the operating envelope. Dense score output, index memory, allocation, cache behavior, and concurrency can matter as much as kernel arithmetic. Pin package versions, confirm the native backend is active, and measure latency distributions on the deployment CPU.

Limits of this evidence

This is a best-of-three comparison with independent minima and a fixed execution order, not a median or a latency distribution. It covers three queries and one news corpus. It reports no variance, memory usage, crossover point, or raw per-repeat timings. The exact Kaggle worker CPU is unknown. The results should not be used as a service-level objective or as a prediction for other corpora, query mixes, hardware, or BM25 implementations.

Credential-free reproduction

Use Python 3.13 on Linux x86-64 with glibc 2.35 or newer, or macOS arm64 14 or newer, to use the native wheel. The following commands download the public dataset and the exact v5 notebook, pin the two BM25 packages, print the active backend, and execute the benchmark without Kaggle credentials:

python3.13 -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip
python -m pip install \
  bm25-mojo==0.2.5 rank_bm25==0.2.2 \
  pandas matplotlib openai jupyter nbconvert

curl -fL -o news-category-dataset.zip \
  'https://www.kaggle.com/api/v1/datasets/download/rmisra/news-category-dataset?datasetVersionNumber=3'
unzip -q news-category-dataset.zip

curl -fL -o bm25-mojo-benchmark.ipynb \
  'https://www.kaggle.com/kernels/scriptcontent/363368112/download'

python - <<'PY'
from importlib.metadata import version
import bm25_mojo
for package in ("bm25-mojo", "rank_bm25", "numpy", "pandas", "openai"):
    print(package, version(package))
print(bm25_mojo.backend_info())
PY

jupyter nbconvert --to notebook --execute --inplace bm25-mojo-benchmark.ipynb

The original Kaggle image used Python 3.13.15. Its NumPy, pandas, OpenAI, and matplotlib versions were not recorded, and its exact CPU was not published. This reproduction checks the code and parity methodology; it cannot promise identical timings on a different worker.