mirth/msmarco-expansion-tables

MS MARCO click-translation expansion tables

A document-expansion table for BM25, estimated by counting. Each row maps a document term to the query terms that users actually typed when they clicked on passages containing it, learned from 532,761 (query, relevant passage) pairs in MS MARCO. Adding the top 20 predicted query terms to every passage at index time turns BM25+stemming's 0.186 MRR@10 / 0.854 R@1000 into 0.200 / 0.892 on the full 8.84M-passage MS MARCO dev set, at 1.5× the postings — the same recall as the original doc2query, with no neural model, no GPU, a table that builds in ~3 seconds and expands the whole corpus in ~20 CPU-minutes.

It is a statistical translation model in the lineage of Berger & Lafferty (1999) and the click-through translation models of Gao, He & Nie (2010), with three estimation details that turned out to matter more than the choice of association measure: a background-lift normalisation, a consensus boost, and no frequency cutoff on candidate terms.

TL;DR

MS MARCO passage, full corpus (8,841,823 passages), official dev-small (6,980 queries), TREC DL 2019/2020. All expansion rows use m = 20 expansions per passage unless stated.

system	MRR@10	R@100	R@1000	DL19 nDCG@10 / R@1000	DL20 nDCG@10 / R@1000	postings
BM25, unstemmed	0.182	0.628	0.818	0.485 / 0.714	0.506 / 0.752	1.00×
BM25, Snowball stems	0.186	0.666	0.854	0.512 / 0.760	0.485 / 0.780	1.00×
↳ + unsupervised co-occurrence table (control)	0.186	0.672	0.860	0.517 / 0.764	0.479 / 0.801	1.51×
↳ + stem/ table	0.200	0.706	0.892	0.525 / 0.802	0.518 / 0.816	1.51×
↳ + stem/ table, m = 50	0.202	0.710	0.893	0.526 / 0.807	0.518 / 0.826	2.27×
BM25 unstemmed + words/ table	0.201	0.683	0.866	0.529 / 0.757	0.537 / 0.779	1.50×
BM25 over BERT wordpieces	0.178	0.629	0.831	0.457 / 0.739	0.468 / 0.765	1.00×
↳ + wordpiece/ table	0.198	0.679	0.876	0.498 / 0.784	0.518 / 0.807	1.41×

Two things to notice. The unsupervised control — the identical pipeline fed within-document co-occurrence instead of query–document pairs — gets essentially none of the MRR gain and a sixth of the recall gain: the click signal is the whole story. And BERT wordpieces plus the table beat stemmed BM25 outright, i.e. the table learns the morphology itself, which is the pitch for languages without a good stemmer.

What is in this repository

Three variants of the same table, one per analyzer. Pick the one that matches your engine's analyzer exactly.

folder	analyzer contract	rows	entries	gzip size
stem/	NFKC → lowercase → \w+ → Snowball English		527,458

Each folder contains:

file	contents
config.json	analyzer contract, estimation parameters, expansion recipe, scoring parameters, stats
table.jsonl.gz	one line per document-side term: its candidate query terms with weights
candidates.jsonl	one line per candidate term: background vote mass bg and training-query frequency qf
examples.jsonl	50 passages with their analysed units and expected expansions — test vectors for ports
expand_reference.py	dependency-light reference implementation; this file is the specification

How the tables were built

Data. MS MARCO passage ranking, training qrels (msmarco-passage/train/judged): 532,761 pairs of a query and a passage judged relevant to it, over 502,939 distinct queries. No dev or test data was used for estimation.

Estimation. For every (passage term u, query term v) pair, count the number of training pairs in which u occurs in the passage and v occurs in the query (set semantics). Keep pairs with count ≥ 5, u occurring in ≥ 5 training passages, v occurring in ≥ 5 training queries, and u ≠ v. Score each pair with Dunning's log-likelihood ratio (G²), keep positive associations only, keep the top 50 candidates per u, and L1-normalise each row so that the weights read as an estimate of P(v in query | u in passage). No upper frequency cutoff is applied to candidates: what, is, how, long, cost, definition are all legitimate candidates (see What the table learned).

Expansion recipe (what expand_reference.py implements):

1. Analyse the document into its set of unique units U.
2. Scale every table weight by bg[v]^-α (α = 0.5), where bg[v] = Σ_u P(u ∈ passage)·w(u,v) is the vote mass a random MS MARCO passage would send to v — a background-lift normalisation that stops frequent query words from dominating every document.
3. Aggregate votes over the document: e[v] = Σ_{u ∈ U} w'(u,v), support[v] = |{u ∈ U : w'(u,v) > 0}|.
4. Score e[v]·support[v]^β (β = 0.75) — a consensus boost that favours candidates several units agree on (jews, camps, deported, warsaw → auschwitz) over single-unit polysemy (nick → saban).
5. Drop candidates already present in the document, keep the top m (= 20), divide by the maximum so weights lie in (0, 1].

Scoring. An expansion term with weight w enters BM25 (k1 = 0.9, b = 0.4) as a fractional term frequency λ·w (λ = 1), using the document's original length and the original field's IDF. Expansion terms never coincide with body terms (step 5), so a two-field implementation can simply add the two scores.

Cost: the table takes ~3 s to estimate from cached co-occurrence counts (one sparse matrix product); expanding the 8.84M-passage corpus takes ~20 min on 12 CPU cores.

How to use

Python

from huggingface_hub import snapshot_download
import sys

folder = snapshot_download("mirth/msmarco-expansion-tables", allow_patterns=["stem/*"])
sys.path.insert(0, f"{folder}/stem")
from expand_reference import ExpansionTable, units      # needs: pip install PyStemmer

table = ExpansionTable(f"{folder}/stem")                 # loads config, candidates, table (~0.5 s)
doc = "Hyaluronic acid injection is used to treat knee pain caused by osteoarthritis (OA) in patients " \
      "who have already been treated with pain relievers (e.g., acetaminophen)."
table.expand(doc)      # -> [(stem, weight), ...] up to 20, weights in (0, 1], sorted; e.g. tylenol, arthritis, knee, ...
units(doc)             # -> the document's analysed units, for checking analyzer parity

Verify a checkout (and any port) against the test vectors:

python stem/expand_reference.py stem      # prints: 0 mismatches out of 50

Inside a BM25 engine

At index time, run expand on each document's unique analysed terms and write the result to a second field (exp), quantised if you like (round(255·w) fits a byte). At query time:

score(q, d) = Σ_{t ∈ q ∩ body(d)} BM25(t, d)
            + Σ_{t ∈ q ∩ exp(d)}  idf_body(t) · (λ·w_t·(k1+1)) / (λ·w_t + k1·(1 − b + b·|d|/avgdl))

with |d| the body length and idf_body the body field's IDF (fall back to the exp field's df for terms the body never contains). m and λ are runtime parameters of your engine, not baked into the files: m = 20 costs 1.5× the postings of a ~40-term passage and retains ~95% of the gain of m = 50; λ = 1 is a sharp optimum (λ = 2 loses 1.7 MRR points, λ = 3 loses 4.3).

Porting to other languages

The format was designed to be consumed without Python. Requirements for a faithful port:

• Analyzer parity is everything. stem/ requires NFKC normalisation, Unicode lowercasing, \w+ tokenisation (Unicode-aware, underscore included) and the Snowball English stemmer — in Rust: unicode-normalization, regex, rust-stemmers (Algorithm::English); the same implementations tantivy uses.
• Load candidates.jsonl first (assign ids, compute bg^-α), then table.jsonl.gz (string-keyed rows), then apply steps 3–5 above per document. A Rust loader + expander is ~60 lines with serde_json and flate2.
• Test against examples.jsonl: analysed units must match exactly; expansions must match as a set with weights within 1e-3 (order among ties is unspecified).

File formats

table.jsonl.gz — one JSON object per line. Invariants: weights are non-negative, sum to 1 within a row, sorted descending; weights are not background-scaled (do that at load time with bg and your chosen α).

{"u": "bank", "expansions": [["rout", 0.3104], ["number", 0.2311], ["account", 0.0712], ["credit", 0.0398]]}

candidates.jsonl — one line per candidate term. bg as defined above, computed over the 8.84M MS MARCO passages; qf is the fraction of training queries containing the term, provided so you can apply your own cutoffs.

{"v": "long", "bg": 1.270411, "qf": 0.021337}

examples.jsonl — {"text": ..., "units": [...], "expansions": [[term, weight], ...]}, produced by the original pipeline and cross-checked against the reference implementation.

config.json — everything above as machine-readable fields (unit, table, background, expansion, scoring, stats), plus format_version.

Terms are shipped as strings rather than integer ids on purpose: any consuming engine has its own term dictionary, and string keys make the files self-describing and greppable (zcat table.jsonl.gz | grep '"u": "mortgag"').

Evaluation

Protocol

All design decisions and hyper-parameters were tuned on a 1M-passage random subset of the corpus (plus all judged passages), using one half of the official dev-small queries (dev_tune, 3,490 queries). The other half (dev_test), TREC DL 2019 (43 queries, graded) and TREC DL 2020 (54 queries, graded) were held out. The full-corpus numbers in this card were produced by applying the frozen configuration to all 8,841,823 passages with no further tuning. The BM25 baseline in this pipeline reproduces Anserini's published BM25 within 0.2 MRR / 0.4 R@1000 (0.186 / 0.854 vs 0.187 / 0.857), and DL19/DL20 nDCG@10 within 0.6 points.

Against published systems (MS MARCO dev, full corpus; numbers as reported in the respective papers)

system	MRR@10	R@1000	corpus-side cost
BM25 (Anserini)	0.187	0.857	—
BM25 + RM3	0.166	0.861	query-time feedback
BM25 + this table (m = 20)	0.200	0.892	3 s table, ~20 CPU-min expansion, 1.5× postings
doc2query (Nogueira et al., 2019)	0.218	0.891	seq2seq inference over the corpus (GPU)
DeepCT (Dai & Callan, 2019)	0.243	0.913	BERT inference over the corpus (GPU)
docTTTTTquery	0.277	0.947	T5 inference, GPU-days
SPLADE++	≈0.37	≈0.98	learned sparse model

The table matches doc2query's recall and takes ~40% of its MRR gain, at roughly zero compute. It does not approach the BERT-scale expanders on early precision, and the gap on the densely judged TREC DL sets (+1.4 / +3.3 nDCG@10) is much wider than on dev: a word-level table has no notion of context.

What mattered (ablations on the 1M subset, dev_tune, MRR@10)

decision	effect
supervised (query↔passage) vs unsupervised (within-passage) co-occurrence	+2.9 vs +0.5 over the stem baseline at 1M; +1.5 vs +0.05 at full scale
per-document voting vs union of per-term top-k lists	0.436 vs 0.426; the uncapped union costs 10× postings for a worse result
association measure	LLR 0.430 > conditional probability 0.427 > NPMI 0.418 ≈ PMI 0.417
background lift exponent α	0 → 0.430, 0.5 → 0.436, 1.0 → ≈ baseline (pure lift over-rewards rare noise)
consensus exponent β	0 → 0.430, 0.5 → 0.436, 0.75 → 0.439, 1.0 → 0.438; positive for every measure, unit and policy tested
candidate frequency cutoff	forbidding query words in > 2% of queries: 0.427; > 10%: 0.441; no cutoff: 0.453
expansions per document m	20 / 30 / 50 / 100: flat on MRR (0.438–0.439), +0.2 R@1000 at 5× the postings
co-occurrence min count	5 → 3 → 2 doubles the table and changes nothing
capping how many documents a term may expand into	−0.3 to −0.7 MRR: the "hub" expansions are weak but real answer-type features
query-side expansion with the same table	+0.3 R@1000 for −1 to −7 MRR
λ	0.25 → 0.5 → 1.0 monotone up, then 1.5 / 2 / 3 down

What the table learned

Two different kinds of knowledge, both estimated from the same counts (rows from the words/ variant, weights approximate):

Topical translation — what people call things:

bank     → routing .31, number .23, account .07, credit .04, check .04, union .03, fdic, fargo, wells, pnc
python   → snake .33, programming .10, longest .08, language .04, software .03
mortgage → loan .27, home .08, fha .07, refinance .07, interest .05, pmi .04, escrow .02
cancer   → prostate .12, causes .09, colon .07, lung .06, leukemia .04, hpv .04, psa .04, chemotherapy .03
located  → where .41, county .32, city .03, zip .02, airport .02
stages   → stage .14, cycle .13, life .08, cancer .08, symptoms .08, sleep .06, erikson .04, grief .03, piaget .03

Answer-type priors — what kind of question a passage answers. The candidates receiving the most vote mass across the corpus are long, cost, definition, where, county, can, who, you, causes, much: a passage about a procedure gets long (how long does it take), a passage about a place gets where and county, a definitional passage gets definition, what, is. These are near-useless for topical matching and yet carry a large share of the MRR gain — forbidding candidates that occur in more than 2% of queries costs 2.6 MRR points at 1M. Any use on keyword-style (non-question) queries should expect only the topical component to transfer.

Where it still fails

On the 1M subset (dev_test), expansion repaired 63 of the stem baseline's 161 recall@1000 misses and broke 11. Of the 109 remaining misses: 47% already receive a matching query term through expansion but are outranked by passages that contain it literally (a ranking-depth problem); 41% have literal overlap but no helpful expansion — recurring Snowball gaps such as producers/production, weigh/weight, treat/treatment, man/men, and paraphrase such as started/began; 12% share no term with the query at all (typos such as jabodatek, abbreviations such as nfcu, label noise). A character-level matching field would address the last slice; nothing table-shaped addresses the first.

Limitations and intended use

• English, web-passage, question-shaped queries. Estimated from MS MARCO click-derived pairs; domain and query style transfer has not been measured (a BEIR zero-shot evaluation is the obvious next step and is not part of this release).
• Not a semantic model. Word-level, context-free: chapter → bankruptcy, nick → saban, joints → shock absorbers are the failure mode; the consensus boost reduces but does not remove it.
• Requires analyzer parity. Using stem/ with a different stemmer, or words/ with stemming, silently degrades the result. Use the test vectors.
• Intended as a first-stage recall booster for lexical search where a GPU-based expander is unavailable or disproportionate, as a strong cheap baseline, and as a teaching example of what a translation model learns from clicks. Not intended as a replacement for learned sparse or dense retrieval where those are affordable.

License and terms

The tables are derived from the MS MARCO dataset, whose terms restrict use to non-commercial research purposes (see the MS MARCO terms). The tables inherit that restriction. The reference implementation (expand_reference.py) is released under the MIT license.

Reproducing

Code, sweeps and results log: . The full pipeline is pure Python (numpy, scipy, ir_datasets, ir_measures, PyStemmer); a 1M-passage run takes ~2 minutes on a laptop, the full corpus ~30 minutes per run on a 12-core server. Tables were exported with:

python export_hf.py tokenizer=words_stem q_max_df_frac=1.0 topk=50 m=20 bg_alpha=0.5 support_beta=0.75 \
                    corpus_size=9000000 -- hf_export/stem mirth/msmarco-expansion-tables

Lineage and citation

This is not a new idea. It is Berger & Lafferty's translation model estimated by counting, in the tradition of click-through translation models, made competitive by three estimation details. Relevant prior work:

• A. Berger, J. Lafferty. Information Retrieval as Statistical Translation. SIGIR 1999.
• J. Gao, X. He, J.-Y. Nie. Clickthrough-based translation models for web search: from word models to phrase models. CIKM 2010.
• M. Karimzadehgan, C. Zhai. Estimation of statistical translation models based on mutual information for ad hoc information retrieval. SIGIR 2010.
• P.-S. Huang et al. Learning deep structured semantic models for web search using clickthrough data. CIKM 2013 (the model this table is a "poor man's" version of).
• R. Nogueira, W. Yang, J. Lin, K. Cho. Document Expansion by Query Prediction. 2019.
• P. Bajaj et al. MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. 2016.

If you use these tables, please cite this repository:

@misc{mirth2026ttde,
  title  = {MS MARCO click-translation expansion tables: count-based document expansion for BM25},
  author = {huggingface.co/mirth},
  year   = {2026},
  url    = {https://huggingface.co/mirth/msmarco-expansion-tables}
}