Pairwise relevance judgments constrain both the loss numerator and the ideal-ranking denominator of nDCG. We characterize the exact worst-case loss of replacing a ranking with a fixed proposal. Binary gains attain this loss and provide an inspectable witness. Threshold verification reduces to at most K+1 maximum-closure problems. Our exposure-flow ablation isolates denominator coupling: on shared judge trajectories, exact verification saves 2.34 comparisons per TREC-DL development query and 1.98 per confirmation query at a budget of 32. Savings transfer to BEIR and a second proposer. Predictive gates achieve higher deployment gains, while certificates expose the worst gains still permitted by accepted comparisons.
Figures & tables
Figure 1: A witness explains the next question. For K=4 , ε=.05 , and w≈(1,.6309,.5,.4307) , a set assigns gain one to its members and zero elsewhere, with v(S)=a(S)/Zmin(∣S∣,K) . (a) Four sets remain unsafe without evidence. (b) B→C excludes all four; the other shown assertions exclude two. (c) Accepting it yields worst set {B,C} : exact certifies while flow continues. The gray branch shows the next unsafe witness after B→D . B→A is illustrative: aA=0 , so it is outside the purchased support pairs.
Figure 2: Exact verification reduces evidence cost. (a) Optimal hindsight savings on 142 cases with correct comparisons. (b) Development and confirmation stopping. (c) Development release shares. (d) Savings at B=32 across four settings. (e) Development gain and cost at budgets 8, 16, and 32. (f) Savings depend on acquisition; the hollow point has Holm-adjusted p≥.05 . Shading and error bars show paired 95% bootstrap intervals.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Quantity
mean
median
p95
max
verifier construction (ms)
5.27
2.35
25.73
28.40
per accepted edge, risk update (ms)
1.20
0.50
5.58
7.07
cover planner, one call (ms)
154.01
176.28
213.29
224.27
verifier peak memory (MiB)
11.05
5.75
46.00
46.00
Appendix
Table 1: Recorded computation profile at K=10 . These component measurements exclude LLM inference and do not establish end-to-end speedups.
Panel
n
rP≤0
0<rP≤ε
rP>ε
Development
183
160
9
14
Appendix
Table 2: Signed proposal losses on the complete TREC-DL 2020–2022 development panel, including its 61 calibration and 122 test queries; ε=.05 . Positive loss means a worse proposal. The non-positive group includes 152 improvements and eight ties.
Panel
n
B
Δ nDCG
comparisons
diff.
pHolm
diff.
pHolm
Development
122
12
+0.0278
0.0015
-0.43
0.0023
16
+0.0550
0.0015
-1.11
0.0015
32
+0.0063
1.000
-2.34
0.0015
Confirmation
55
12
+0.0223
0.124
-0.53
0.0096
16
+0.0211
0.422
-1.15
0.0010
Appendix
Table 3: Exact minus flow gates on shared cover trajectories. Positive gain differences and negative comparison differences favor exact. Tests are corrected within the archived contrast families; these are secondary analyses.
Corpus
Gate
n
Δ nDCG
accept
viol.
cmp
saved (CI)
SciFact
flow
199
+0.0343
0.136
2/27
29.8
exact
+0.0361
0.146
2/29
29.2
+0.533 [+0.312,+0.784]
NFCorpus
flow
216
+0.0243
0.139
2/30
29.7
exact
+0.0325
0.194
5/42
28.7
+0.986 [+0.639,+1.389]
FiQA
flow
433
+0.0577
0.242
2/105
29.0
exact
+0.0673
0.282
4/122
27.8
+1.199 [+0.945,+1.485]
Appendix
Table 4: Per-corpus BEIR results at B=32 on shared cover trajectories. “Viol.” counts loss-budget exceedances among accepted proposals; the calibration guarantee is marginal over the pooled query distribution.
Exact certificate
BT / reference
Decision rule
Δ nDCG
Viol./acc.
Δ nDCG
Viol./acc.
Development, n=122
Counterexample cover
+0.1423
1/64
+0.1493
4/78
Greedy flow
+0.1363
1/60
+0.1593
4/84
Flow completion
+0.1399
1/62
+0.1570
4/81
Capacity static
+0.0162
1/12
+0.1400
2/64
Appendix
Table 5: Deployment at B=32 . Gains average over all test queries; “Viol./acc.” counts budget exceedances among accepted proposals. BT uses the same paid comparisons, with probability information beyond accepted assertions. References in the last two rows per panel do not buy comparisons.
Information Retrieval (IR) Evaluation measures how well search systems find, rank, and cover useful evidence across queries, collections, and settings.
Large Language Model judges are widely used to rank texts and text-generating systems through pairwise comparison, and their reliability is typically assessed via three proxies: position bias, transitivity, and pairwise agreement (self- or human-labeled). Because these proxies drive judge selection and benchmarking, a substantial literature reporting that judges perform poorly on them risks steering practitioners away from otherwise capable evaluators. We argue this assessment is misleading. Under the Bradley--Terry geometry underlying pairwise aggregation, each proxy is dominated by close-rank-gap pairs, where inconsistency is expected and errors cost little aggregate ranking accuracy; far-gap pairs determine the ranking accuracy but barely move the proxies. We formalize this argument and validate it in a controlled simulation and on two human-rated corpora: the proxies correlate only weakly with ranking accuracy against gold, and their predictive component concentrates in the far-gap regime. Judges should therefore be assessed on rank-gap-conditional metrics, ideally against human rankings. Code at https://github.com/brunobrocai/PairDifficulty
Pairwise Ranking Prompting (PRP) elicits pairwise preference judgments from an LLM, which are then aggregated into a ranking, usually via classical sorting algorithms. However, judgments are noisy, order-sensitive, and sometimes intransitive, so sorting assumptions do not match the setting. Because sorting aims to recover a full permutation, truncating it to meet a call budget does not produce a dependable top-K. We thus reframe PRP reranking as active learning from noisy pairwise comparisons and show that active rankers are drop-in replacements that improve NDCG@10 per call in the call-constrained regime. Our noise-robust framework also introduces a randomized-direction oracle that uses a single LLM call per pair. This approach converts systematic position bias into zero-mean noise, enabling unbiased aggregate ranking without the cost of bidirectional calls.
Jeremías Figueiredo Paschmann, Juan Kaplan, Francisco Nattero +3
ELIAS Lab, Departamento de Ingeniería, Universidad de San Andrés
Pairwise model comparisons drawn from foundation-model benchmarks ("A is safer than B") are read as quantitative verdicts but hinge on harness choices benchmark papers under-specify. We close one theory-benchmark loop on this primitive: a finite-envelope proposition tying a measurable pairwise-disagreement rate to whether the strict ordering admits a configuration-pair reversal, paired with a commit-stamped evaluation protocol that operationalises it on widely cited alignment benchmarks. On every benchmark we test, configuration choice alone can flip the pairwise verdict; the proposition isolates this strict-reversal failure mode.
Yanhang Li, Zhichao Fan, Zexin Zhuang
Northeastern University, Boston, MA, USA · University of Illinois Urbana-Champaign, Urbana, IL, USA · Southern Methodist University, Dallas, TX, USA