retrieval-lab
BM25 and dense retrieval in Go, where BM25, exact dense search and fusion are each accepted against a number that Pyserini publishes for BEIR. BM25 equals the published nDCG@10 and Recall@100 to four decimals on six datasets. BGE-base with exact search is within 0.0006 in nDCG@10 on all six, and within 0.0004 on all but TREC-COVID. A pre-registered study on it found that HNSW's loss in nDCG@10 depends on the model at equal ef, and not once each model is searched to the same neighbour recall of 0.95.
Key metrics
- BEIR test sets on which BM25's nDCG@10 and Recall@100 equal Pyserini's published values to four decimals. The six run files reproduce byte for byte from their committed SHA-256
- 6 of 6
- nDCG@10 of Bleve's own BM25 scorer minus the same anchors, with k1 and b set alike. Its rankings are not deterministic across index builds
- −0.243 to +0.148
- the largest gap in nDCG@10 between BGE-base-en-v1.5 with exact search and Pyserini's flat condition, over six datasets, found on TREC-COVID. On the other five it is at most 0.0004
- 0.0006
- documents of SciFact and ArguAna whose vector had a cosine below 0.9999 to Pyserini's, the lowest 0.9936. Every one held Unicode format characters; with those removed, none is below
- 28
The anchors are the four-decimal values in Pyserini's beir.yaml at one commit, and for fusion the numbers of its BEIR fusion page at that commit. The tolerance of 0.005 in nDCG@10 was fixed for BM25 before any BM25 result existed; for BGE it was committed together with the first BGE results. The BM25 checksums hold on amd64. The BGE, HNSW and fused figures come from one machine; the vectors depend on the CPU in their last bits, so exact values can differ on another. Pyserini's own run files were not compared line by line. Approximate search uses recserve's HNSW graph over the same vectors: at ef 200, 400 and 800, it holds on average at least 0.9912 of a query's exact top 10 on every dataset. Fusing the BM25 and BGE runs as Pyserini does, by RRF and by the sum of min-max normalised scores (Normalize), gives nDCG@10 within 0.005 of Pyserini's published fusion numbers on all six datasets; the largest differences, 0.0036 and 0.0043 above, are on ArguAna. Against the BGE run alone, neither fused run's 95% bootstrap interval lies above zero on any dataset; it lies below zero for RRF on FiQA, ArguAna and SCIDOCS and for Normalize on ArguAna and SCIDOCS. Reranking is not built yet. Benchmarks
Problem and goals
Two implementations of one BM25 configuration still differ in details of tokenization and stemming, and can differ in stop words, in how title and text are joined, in how the document length is encoded and in how tied scores are ordered.
This project builds its retrieval components in Go. BM25, exact dense search and fusion are each accepted against a published number that a third party can reproduce with public commands and data: the BEIR test sets with fewer than 200,000 documents, and the numbers on Pyserini's BEIR reproducibility page and, for fusion, on its BEIR fusion page. A dataset outside the tolerance is not tuned toward the anchor. Its cause is found and recorded. HNSW is measured against exact search on the same vectors and has no pass threshold.
Done so far: the evaluation harness, BM25, dense retrieval with exact search and with recserve's HNSW graph, and fusion of the BM25 and BGE runs. Cross-encoder reranking is not built yet.
On this harness a pre-registered study compared eight embedding models on seven BEIR datasets, searching four HNSW graphs per model and dataset. A model's loss is its nDCG@10 under exact search minus that under HNSW, and a difference below 0.005 counts as negligible. At equal search parameters, ef 40, the loss depends on the model (H1 supported): averaged over the datasets it runs from 0.0040 to 0.0193, and the registered test separates 19 of the 28 pairs of models, 8 of them by more than 0.005. With each graph searched at the smallest ef that finds 0.95 of the exact top 10, it does not (H2 supported): on the six datasets where every model can be matched to that recall within 0.01, the test separates no pair and the 90% interval of the spread between models ends at 0.0047, while each model loses 0.0101 to 0.0120. There HNSW keeps the exact-search order (H3 supported): of the 21 pairs that exact search orders, none is reversed and one is left unordered. At the recall-0.95 setting the build alone moves a model's nDCG@10 on a dataset by 0.005 or more in 15 of 49 cases, by up to 0.0203 across four builds (H4 not supported). Fusing with BM25 by RRF at ef 100 removes 0.24 of the loss, with a 95% interval of 0.16 to 0.33, short of the half that H5 required (not supported).
Architecture
scripts/data.sh downloads the six BEIR datasets and checks them by SHA-256. cmd/bm25 indexes the title and text of each document with Bleve and ranks the test queries with Lucene's BM25, computed from Bleve's postings. cmd/embed encodes each corpus with BGE-base-en-v1.5 on ONNX Runtime, and cmd/dense encodes the queries and searches every vector. cmd/bm25 and cmd/dense each write a TREC run file of the top 1000 per query. cmd/eval scores a run as trec_eval -c does, and scripts/check-eval.sh compares its output with trec_eval v10.0 as text. cmd/table computes the metric tables from the run files and sets each figure beside Pyserini's published value; with -dense it also compares each document vector of SciFact, NFCorpus and ArguAna with the one in Pyserini's prebuilt index.
Key decisions
-
D004 The anchors and the tolerance come first
The anchors are the BM25 values in Pyserini's
beir.yamlat one commit, to four decimals. The tolerance is 0.005 in nDCG@10 per dataset, fixed before any BM25 result existed: two implementations of one configuration differ in details of tokenization and stemming, which should move nDCG@10 far less than a change of method does. -
D003 Metrics in Go, checked against trec_eval
The anchors are trec_eval numbers, so its rules decide ties, grades and which queries count. The metrics are written in Go, and trec_eval v10.0 is built from source only to check them: a script compares the per-query output of the two as text. Owning the code keeps a C binary out of the pipeline, and the check keeps the code honest.
-
D005 Bleve holds the index; the scoring is Lucene's
Bleve does the analysis and holds the inverted index. The score is a port of Lucene's
BM25Similarity, computed from Bleve's postings, with Lucene's lossy one-byte encoding of the document length. In v2.6.3 Bleve's own BM25 differs from Lucene's in at least seven ways: among them, it takes the square root of the term frequency, and its average length is built from per-segment counts of distinct terms, not from lengths, so it changes when segments merge. -
D010 Document text and length, read off Pyserini's vectors
Pyserini publishes no encoding command for its prebuilt BGE indexes, and its own encoder defaults to 256 tokens. Its indexes hold the document vectors, so the choice was read off them: title and text joined by a space, at most 512 tokens, gave cosines of at least 0.999999 on the first 160 SciFact documents, where 256 tokens gave a lowest of 0.960.
-
D012 CI checks the dense results by tolerance, not by checksum
ONNX Runtime chooses its kernels by the CPU's instruction set, so vectors can differ in their last bits from one machine to another, and a checksum would fail on another runner with nothing wrong. On every push CI encodes NFCorpus and fails if nDCG@10 is more than 0.005 from the anchor or if any document vector has a cosine below 0.9999 to Pyserini's.
Challenges
-
Bleve's BM25 is not Lucene's, and varies between builds
With k1 and b set alike, Bleve's own scorer is 0.243 below the anchor on TREC-COVID and 0.148 above it on ArguAna. Its run files also differ between two builds of the same index, even merged into one segment: on five of the six datasets in the pair of builds behind the table, and in a rerun ArguAna's nDCG@10 came out 0.5448 and 0.5442. The cause was not investigated. These runs are a reference, not this project's retrieval path, and are not checked in CI.
-
A logarithm one unit in the last place lower
Go's
math.Log2is one unit in the last place lower than C's for 3 and 9, which can move the fourth decimal trec_eval prints. The discounts of ranks 1 to 10 are therefore C's correctly rounded values. Beyond rank 10 they still come frommath.Log2, so nDCG@k for k above 10 can differ from trec_eval in the fourth decimal in rare cases. -
Twenty-eight documents with characters nobody sees
With the document encoding settled, 28 documents of SciFact and ArguAna still had a cosine below 0.9999 to Pyserini's vector, and every one held soft hyphens, zero-width spaces or left-to-right marks. Hugging Face's BERT normalizer, which Pyserini's encoder uses, removes such characters; the Go tokenizer library removes only control characters. Documents now lose every character of Unicode category C but tab, newline and carriage return before encoding. Queries keep format characters, as the anchor's query tokenizer does.
-
What the study leaves out
The study covers one HNSW implementation, corpora of up to 2.7 million documents, English text and these eight models. It does not report latency: equal ef means equal search parameters, not equal cost. The spread of four builds understates that of all builds. The vectors are not archived, so a rerun encodes again and its graphs and runs differ in detail. BEIR's judgements are sparse, and a document nobody judged counts as not relevant.