Exact Risk Certificates for Pairwise-Judged Reranking

Xinyu Wang; Jingrui Tian; Sicheng Lyu; Yu Gu; Ziyang Song; Xiao-Wen Chang; Lei Ding

cs.LGOct 17, 2026

Exact Risk Certificates for Pairwise-Judged Reranking

Authors: Xinyu Wang, Jingrui Tian, Sicheng Lyu, Yu Gu, Ziyang Song, Xiao-Wen Chang, Lei Ding

Organizations: McGill University · Ohio University · University of Manitoba

Abstract

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

\varepsilon=.05

, and

w\approx(1,.6309,.5,.4307)

, a set assigns gain one to its members and zero elsewhere, with

v(S)=a(S)/Z_{\min(|S|,K)}

. (a) Four sets remain unsafe without evidence. (b)

B\to 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\to D

B\to A

is illustrative:

a_{A}=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\geq.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$	$r_{P}\leq 0$	$0<r_{P}\leq\varepsilon$	$r_{P}>\varepsilon$
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;

\varepsilon=.05

. Positive loss means a worse proposal. The non-positive group includes 152 improvements and eight ties.

Panel	$n$	$B$	$\Delta$ nDCG		comparisons
			diff.	$p_{\mathrm{Holm}}$	diff.	$p_{\mathrm{Holm}}$
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$	$\Delta$ 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.

Development, $n=122$
	Exact certificate		BT / reference
Decision rule	$\Delta$ nDCG	Viol./acc.	$\Delta$ nDCG	Viol./acc.
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.

IR Evaluation

Information Retrieval (IR) Evaluation measures how well search systems find, rank, and cover useful evidence across queries, collections, and settings.

See all 188 papers

Pair Difficulty Matters: Rethinking Pairwise LLM-as-a-Judge Evaluation and Consistency
Sep 29, 2026Bruno Brocai, Maria BeckerLLM-as-a-Judge Pairwise Preference Evaluation
Heidelberg University, German Department
Active Learners as Efficient PRP Rerankers
May 14, 2026Jeremías Figueiredo Paschmann, Juan Kaplan, Francisco Nattero +3Pairwise Preference Learning Pairwise Comparison
ELIAS Lab, Departamento de Ingeniería, Universidad de San Andrés
SafetyRepro: Configuration-Conditional Rank Instability on Alignment Benchmarks
May 25, 2026Yanhang Li, Zhichao Fan, Zexin ZhuangPairwise Comparison Pairwise Preference Evaluation
Northeastern University, Boston, MA, USA · University of Illinois Urbana-Champaign, Urbana, IL, USA · Southern Methodist University, Dallas, TX, USA

Sep 29, 2026J/K move · Enter open · S save

Pair Difficulty Matters: Rethinking Pairwise LLM-as-a-Judge Evaluation and Consistency

Bruno Brocai, Maria Becker

Heidelberg University, German Department

LLM-as-a-Judge Pairwise Preference Evaluation LLM Reliability

Open paper AskPDF arXiv

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

Abstract

IR Evaluation

Explore similar work

Pair Difficulty Matters: Rethinking Pairwise LLM-as-a-Judge Evaluation and Consistency

Active Learners as Efficient PRP Rerankers

SafetyRepro: Configuration-Conditional Rank Instability on Alignment Benchmarks