Search benchmarks judge only a small "pool" of documents, usually the top results of the systems that existed when the benchmark was built. Every unjudged document is then scored as non-relevant. New kinds of systems surface relevant documents nobody judged, so they get penalized. On TREC Deep Learning 2019, ranking neural systems with a pool built only from traditional systems produced rankings uncorrelated or even anti-correlated with the truth. We propose a simple fix taken from distributed hypothesis testing. Before any system is evaluated, the benchmark publishes one short random seed. The seed assigns every query–document pair a fixed lottery number in [0,1). Any system, past or future, has a document judged exactly when that number falls below a threshold set by the rank at which the system placed it. Each system's score can then be estimated without bias from a known, system-specific inclusion probability that no other system can change. Because all systems share the same lottery numbers, the documents two systems both rank are sampled identically, and their estimation errors cancel when the systems are compared.
The idea rests on a clean result from distributed statistics. Shared randomness, meaning random bits that every party sees, greatly reduces the samples needed to test a hypothesis. It does not reduce the samples needed to estimate a distribution, because it lets parties align their measurements along the direction in which two hypotheses differ. Deciding whether system A beats system B is a test, not an estimation problem. We therefore predict that coordinated coins will greatly reduce the judgments needed for correct pairwise decisions, while leaving the precision of each system's absolute score unchanged. Seeing both halves of that prediction together would show that the mechanism is the one claimed.
Core Claim
Fix a query $q$ and a corpus. A short public seed $s$ defines a hash $u_{qd}=h_s(q,d)\in[0,1)$ for every document $d$. A rate function $\pi(r)$, non-increasing in the rank $r$ and equal to 1 for the top few ranks, sets how often a document at rank $r$ gets judged. Document $d$ is judged if, for at least one evaluated system $S$, $u_{qd}<\pi(r_S(d))$, where $r_S(d)$ is the rank $S$ gave $d$. Judgments accumulate over time, and a new system only triggers judgments for documents that pass its own threshold and are not already judged. For a rank-weighted metric with weights $w(r)$ (for example nDCG-style discounts, or the relevance-weighted sum behind deep metrics), the score of $S$ is estimated by weighting each judged relevant document by the inverse of its inclusion probability:
$$\hat M_S=\sum_{d}\frac{w(r_S(d))\,\mathrm{rel}(d)\,\mathbf{1}[u_{qd}<\pi(r_S(d))]}{\pi(r_S(d))}.$$
Here $\mathrm{rel}(d)$ is the judged relevance and $\mathbf{1}[\cdot]$ is an indicator. This estimator is unbiased for every system, including systems submitted years later, because $S$'s own threshold guarantees that the judgments it needs exist. Its inclusion probability does not depend on which other systems contributed. This is the property that the closed-world assumption and run-dependent sampling both lack.
The comparison $\hat\Delta=\hat M_A-\hat M_B$ is where coordination pays off. Under independent coins, $\mathrm{Var}(\hat\Delta)=\mathrm{Var}(\hat M_A)+\mathrm{Var}(\hat M_B)$. Under shared coins, a document placed at the same rank by both systems has the same indicator in both sums, so its contribution to $\hat\Delta$ is exactly zero. Documents at nearby ranks are strongly positively correlated. To first order, the variance of the difference depends only on the documents on which the two rankings actually disagree:
$$\mathrm{Var}_{\text{shared}}(\hat\Delta)=\mathrm{Var}(\hat M_A)+\mathrm{Var}(\hat M_B)-2\,\mathrm{Cov}_{\text{shared}}(\hat M_A,\hat M_B).$$
The covariance term is zero under independent coins and large under shared ones when the rankings overlap. Strong systems on a mature benchmark overlap heavily, so this is exactly the regime where leaderboard decisions are hardest.
Relation to Prior Work
The method comes from the distributed-testing literature. Communication-Constrained Inference and the Role of Shared Randomness proves that public-coin hashing speeds up identity testing by a $\sqrt{k/2^\ell}$ factor and gives no advantage for learning the distribution. The trilogy Inference Under Information Constraints I, II and III, together with Test without Trust, establishes the same separation under privacy constraints. We do not reuse their bounds, since our setting has no communication limit. We reuse their central lesson: shared randomness is a resource for comparison, not for reconstruction. We turn that lesson into a falsifiable prediction about benchmark judging.
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit maps a size-$k$ alphabet into a small domain with a limited shared-seed budget. It shows how few random bits suffice when a hash only needs to preserve distances with useful probability. That paper constrains our design rather than supplying it. Our hash compresses a corpus of millions of document identifiers into lottery numbers, and the question it raises becomes ours too: how much independence must the hash family have? Unbiasedness needs only uniform marginals. The variance identity above needs pairwise independence. Variance estimates that concentrate, which the significance tests need, need roughly 4-wise independence. Communication-Constrained Inference and the Role of Shared Randomness notes that 4-wise independence costs only $O(\log k)$ seed bits. A benchmark can therefore publish a seed of a few hundred bits instead of a sampling plan. Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness uses a shared seed so that agents sample the same query points without sending them. That is the same "coordinate without metadata" move, and here it lets systems that never interact share judgments.
On the pooling side, On the Reliability of Test Collections for Evaluating Systems of Different Types motivates the work. Its simulated pools give Kendall's τ of −0.12 (documents) and 0.004 (passages, MRR) when traditional pools rank neural systems. Systematic Evaluation of Neural Retrieval Models on the Touché 2020 Argument Retrieval Subset of BEIR shows that holes alone can move a model's nDCG@10 from 0.162 to 0.682 once data cleaning and over 1,000 post-hoc judgments are added. Million Query Track 2007 Overview supplies the closest method, statAP's probability-proportional-to-size sampling. Our estimator is in the same family of inverse-probability estimators. The difference is that statAP's inclusion probabilities are computed from the set of contributing runs, so they change when a run is added and are effectively zero for a later system's unique documents. Ours are fixed per system and coordinated across systems through one seed. Hard Negatives or False Negatives applies propensity weighting to ranker training, not evaluation, and estimates its propensities. Ours are known by construction. Can We Use Large Language Models to Fill Relevance Judgment Holes? constrains the design. It finds that mixing human judgments with LLM-filled holes distorts rankings, and that LLM re-judging should cover the whole pool. Our protocol is agnostic about who the judge is, but it requires one consistent judge per collection, and it reduces how many judge calls are needed.
Coordinated sampling with fixed per-unit random numbers is a known tool in survey statistics. The file records no use of it in retrieval evaluation, and no work linking shared-randomness theory to pooling bias.
Research Program
The work has three parts. The first is the estimator and its analysis: unbiasedness for late-arriving systems, the variance of $\hat M_S$ and of $\hat\Delta$, and a plug-in variance estimator that supports paired significance tests. We will also derive how the coordination gain depends on how much the two rankings overlap. We will choose $\pi(r)$ to minimize the variance of differences under a fixed expected judging budget. The natural first choice is $\pi(r)\propto w(r)$, clipped at 1, which matches the rank weights. We will also analyze the incremental cost of a new system: the expected number of new judgments is $\sum_r \pi(r)$ minus the mass already judged, so a system resembling existing ones costs almost nothing.
The second part concerns the seed. We will study which independence level of the hash family the guarantees require, and test empirically whether a pairwise-independent or 4-wise-independent family behaves like a fully random hash.
The third part is the threat model. A system that knows the seed can game the estimator. For example, it could place likely-relevant documents exactly where they will be sampled, which breaks the requirement that rankings not depend on $u$. We will use commit-and-reveal: the organizer publishes a hash commitment to the seed and reveals the seed only after a submission round closes. Seeds rotate between rounds, and prior rounds' judgments are reused through the overlap of inclusion sets. This mirrors the malicious-client concern left open by Hash-Prune-Invert. We will measure how much a seed-aware adversarial reranker can inflate its score with and without commit-and-reveal.
Baselines
The naive reference point is the closed-world depth-k pool. Systems are scored with the official judgments, and unjudged documents count as non-relevant. On TREC DL 2019 with traditional-only pools, On the Reliability of Test Collections for Evaluating Systems of Different Types reports τ = −0.12 (documents) and τ = 0.004 (passages, MRR). Any credible method must beat this by a wide margin at equal judging cost.
The strongest existing method is statAP-style sampling from Million Query Track 2007 Overview. It reports Kendall's τ ≈ 0.80–0.82 against the Terabyte gold standard on GOV2, at roughly 40 judgments per query. No reported result was found on Lacuna for statAP on TREC DL 2019, so we will reimplement it. We will run it in two fair modes, both at exactly the same per-query judging budget as our method and with the same held-out systems. In the frozen mode, inclusion probabilities come from the original contributing runs. In the recomputed mode, each new run is added to the sampling distribution and fresh samples are drawn. Beating it means higher pairwise decision accuracy and lower bias for held-out systems at equal budget. Alternatively, it means the same accuracy with substantially fewer judgments.
Minimal Test Collections from the same overview is the strongest adaptive competitor. It greedily picks documents that resolve uncertainty in differences between systems. Because it targets differences directly, it is the most direct test of whether a fixed, non-adaptive public-coin rule loses much against adaptive selection. It gets the same budget.
Depth-k hole filling judges every unjudged top-k document of each new system. It is exact for metrics with cutoff k, and it is compared at equal total judgments across a growing leaderboard.
The key ablation keeps everything identical except coordination. It uses the same $\pi(r)$, the same budget and the same estimator, but draws independent coins for each system. This isolates the contribution of shared randomness. A second ablation replaces the fully random hash with pairwise-independent and 4-wise-independent families, to test the seed-budget claim.
Why not just…?
Why not just re-run statAP whenever a new system arrives? This is the most serious competitor, and we treat it as one. Recomputing the sampling distribution changes the inclusion probabilities of documents that were already judged. Old judgments then either must be discarded or their weights become inconsistent. Fresh, independent draws also lose the covariance term, so pairwise comparisons pay the full $\mathrm{Var}(\hat M_A)+\mathrm{Var}(\hat M_B)$. The allocation experiment below measures both effects directly. If recomputed statAP matches coordinated sampling at equal cumulative judgments, the coordination claim fails.
Why not just judge each new system's top-k holes? For shallow metrics and a handful of new systems this is cheaper and exact, and we expect it to win there. Its cost, however, grows with every submission and every query. It also covers deep metrics poorly, because holes multiply below the cutoff. Judging later with different assessors also brings the mixing problem that Can We Use Large Language Models to Fill Relevance Judgment Holes? documents. We will report the crossover point in number of systems and metric depth at which coordinated sampling becomes cheaper for the same decision accuracy.
Why not just re-judge everything with an LLM? A fine-tuned Llama-3 judge reached binary κ = 0.729 and τ > 0.80 on TREC iKAT 2023 in Can We Use Large Language Models to Fill Relevance Judgment Holes?. The same paper shows the LLM must cover the whole pool, and full pools grow with every submission. This is complementary to our proposal rather than a replacement. Our protocol decides which documents an LLM judge sees. We will measure how many LLM calls coordinated sampling needs to reproduce the rankings obtained from full-pool LLM judging.
Proposed Experiments
The main testbed is TREC DL 2019, which has 38 document runs, 37 passage runs and 43 deeply judged queries. Following On the Reliability of Test Collections for Evaluating Systems of Different Types, we treat the official judgments as an oracle and build each collection from a subset of runs. The hardest split uses traditional runs only. We then score the held-out neural runs under each method. We will report Kendall's τ against the oracle ranking, the accuracy of pairwise significant-difference decisions, the bias and variance of nDCG@10, nDCG@100 and AP for held-out systems, and the judgments per query needed to reach τ ≥ 0.9. We will also run a sequential-arrival simulation in which systems join in random order. It tracks cumulative judging cost and whether earlier systems' rankings stay stable.
GOV2 with the Million Query 2007 setup gives a direct comparison against statAP at its published operating point. The Touché 2020 split of BEIR serves as a stress test, since holes there are extreme. As reported in Systematic Evaluation of Neural Retrieval Models on the Touché 2020 Argument Retrieval Subset of BEIR, BM25 still leads DRAGON+ there (0.785 vs. 0.718). This is a useful check that the method does not simply favor neural systems.
Two checks are decisive. First, the testing-versus-learning signature: relative to the independent-coin ablation, shared coins should leave the error of absolute scores essentially unchanged. At the same time they should reduce the variance of pairwise differences roughly in proportion to how much the two rankings overlap. A gain in both, or in neither, would mean the claimed mechanism is not what is operating. Second, at matched budget, coordinated sampling must beat recomputed statAP on held-out-system pairwise accuracy in the traditional-only split. If it does not, the remaining contribution reduces to bookkeeping convenience, and we would report that plainly.
References
- Communication-Constrained Inference and the Role of Shared Randomness
- Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction
- Inference under Information Constraints II: Communication Constraints and Shared Randomness
- Inference Under Information Constraints III: Local Privacy Constraints
- Test without Trust: Optimal Locally Private Distribution Testing
- Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
- Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness
- On the Reliability of Test Collections for Evaluating Systems of Different Types
- Systematic Evaluation of Neural Retrieval Models on the Touché 2020 Argument Retrieval Subset of BEIR
- Million Query Track 2007 Overview
- Hard Negatives or False Negatives: Correcting Pooling Bias in Training Neural Ranking Models
- Can We Use Large Language Models to Fill Relevance Judgment Holes?
- Hash-Prune-Invert: Improved Differentially Private Heavy-Hitter Detection in the Two-Server Model
- BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models