Odds-Shift Slippage in One-vs-Rest Rankers: Diagnosing and Repairing Reweighting-Induced Top-K Errors

Akifumi Goto

cs.IRSep 12, 2026

Odds-Shift Slippage in One-vs-Rest Rankers: Diagnosing and Repairing Reweighting-Induced Top-K Errors

Authors: Akifumi Goto

Organizations: Graduate School of Data Science, Shiga University Hikone, Shiga, Japan

Abstract

One-vs-rest rankers that show each user the top- $K$ of many rare labels usually counter imbalance with a per-label positive-class weight, scale_pos_weight $= n_-/n_+$ . Elkan's identity says such a weight shifts label $j$ 's log-odds by $\ln w_j$ , so the model ranks by weighted odds rather than by the marginal that is Bayes-optimal for precision@ $K$ , and suggests inverting the shift afterwards; what a finite learner does with a weight in the thousands, and which repair then works, has not been measured. We call the gap between the promised and the realized shift odds-shift slippage and measure it on matched pairs of LightGBM and MLP models that differ only in the weights. On Santander the weight takes MAP@7 from 0.808 to 0.117; for the boosted pairs the ideal odds shift accounts for 23% of that loss (32% on Instacart; 98% for an MLP pair on the same rows) and slippage for the rest. We prove that a booster whose leaf steps are capped at $c$ realizes at most $Tηc$ nat of shift in $T$ rounds at rate $η$ , which a cap sweep confirms, and show that without a cap saturated cells tie at exactly 1.0, beyond the reach of any separable map. The analytic inversion therefore pays only where the shift was realized and nothing saturated, whereas per-label isotonic regression returns the Santander model to 0.784 (0.780 with the calibrator fitted on the validation period), but only if labels without calibration positives are mapped to their prior rather than passed through. On 11 public MULAN benchmarks and 5 learners the weighted model loses more than half of its MAP@ $K$ in 8 of 55 cells, and on delicious and Corel5k the same repair returns it to the unweighted level; per-label calibration hurts where positives are scarce, a harm that a cross-validated rule removes. The recipe is released as oddslip.

Figures & tables

Panel of Figure 1 — Figure 1. Schematic (no data). (a) Elkan’s identity puts the realized per-label shift $b_{j}$ on the diagonal. A booster with leaf-step cap $c$ cannot exceed $T\eta c$ ( Proposition 2.4 ); without a cap the cells of rare labels saturate at a stored probability of exactly $1.0$ , where $b_{j}$ is not identifiable ( Lemma 2.3 ). (b) The inversion returns the odds-shift part only where $b_{j}=\ln w_{j}$ ( Corollary 2.5 ); a per-label monotone map also returns the slippage; nothing separable reorders the ties ( Remark 1 ). (c) A label with no calibration positives has no map; passed through, its raw score outranks every calibrated label of the row ( Remark 2 ). Three schematic panels: realized against intended shift with a shortfall regime under a cap and a saturation regime without one; a bar of the top-K loss split into odds shift, slippage and ties with the reach of each repair; and a row of scores in which a dead label passed through the identity fallback outranks every calibrated label.

Figure 2. The textbook odds shift accounts for a minority of a weighted LightGBM ranker’s top-

K

loss on both benchmarks; the rest is slippage, most of which a per-label monotone map recovers and the analytic inversion does not. A.

\mathrm{MAP}@7

of the unweighted LightGBM (

w{=}1

); the loss to the ideal odds shift, i.e.

\ln w_{j}

added to its logits ( Proposition 2.1 ); the further loss to the weighted model trained with the identical configuration (

w_{j}{=}n_{-}/n_{+}

), which we call slippage; and what its analytic inversion with the known

w_{j}

and its per-label isotonic repair with the prior fallback return (tick: in-sample per-label ceiling; open marker: the

w{=}1

model under the same calibrator). On Santander the shift is 23% of the loss

0.808-0.117

and the repair returns 97% of it; on Instacart the shift is 32% of

0.131-0.001

and the same calibrator lifts the unweighted model to

0.250

. One matched pair per dataset; over 3 train-row draws the weighted Santander bar is

0.092\pm 0.052

(Robustness), its repaired level stable. B. Largest realized per-label shift

\max_{j}|b_{j}|

(label-free prevalence matching) against the leaf-step cap

c

; the dashed line is the step budget

T\eta c

of Proposition 2.4 . Every point lies below the line (5 of 5 caps on each dataset) and no cell saturates under any cap; without a cap the shift runs into the search bound (triangle) and 16.6% (Santander) and 19.4% (Instacart) of cells sit at exactly

1.0

. A: repair on the 70% evaluation split, else all test rows; 95% intervals are narrower than the markers. Two panels. Panel A: a waterfall of MAP at 7 per dataset from the unweighted model down through the ideal odds shift and the slippage to the trained weighted model, then up by the analytic inversion and by the per-label isotonic repair. Panel B: the largest realized per-label shift against the leaf-step cap, with the step-budget line.

	Santander (24 labels)				Instacart (top-4,000 products)
	LightGBM		MLP		LightGBM		MLP
	$w{=}r$	$w{=}1$	$w{=}r$	$w{=}1$	$w{=}r$	$w{=}1$	$w{=}r$	$w{=}1$
raw score	0.117	0.808	0.112	0.766	0.001	0.131	0.008	0.056
analytic inversion with $w_{j}$	0.151	–	0.247	–	0.017	–	0.070	–
per-label iso, dead $\to$ prior	0.784	0.819	0.549	0.787	0.225	0.250	0.081	0.056
pooled (shared) isotonic	0.261	0.808	0.178	0.766	0.004	0.149	0.008	0.055

Table 1. Repair ladder on two datasets and two learners (

\mathrm{MAP}@7

, test-split protocol, 70% evaluation split; the ceiling row is fitted and evaluated on all test rows; the deployment protocol, Supplement Table S3, differs by at most

0.004

on the bold rung). Columns: the same configuration trained with the recommended per-label weight (

w{=}r

r_{j}=n_{-,j}/n_{+,j}

) and without it (

w{=}1

), for LightGBM and for a shared-trunk MLP with per-label pos_weight , on Santander (24 products) and Instacart (top-4,000 products). “–”: an unweighted model has no

w_{j}

to invert. Bold = per-label isotonic regression with the prior fallback. On all four pairs the weighted model ranks below the popularity baseline and the bold rung returns it to its in-sample ceiling (where that ceiling is below the unweighted raw score, the gap is consistent with the tied cells); the inversion recovers little except on the Instacart MLP, the one pair that realized its shift without saturating ( Corollary 2.5 ). (WGBoost and the identity and exclusion fallbacks: Supplement Table S1.)

Figure 3. Inverting by the known

\ln w_{j}

pays only where the learner realized the shift and no cell saturated. One marker per weighted model: both datasets, both learners, and each leaf-step cap. Horizontal: the median of

b_{j}/\ln w_{j}

over the labels with no saturated cell, the only ones on which it is identified. Vertical: what the inversion returns as a share of that model’s

\mathrm{MAP}@7

loss against its own unweighted twin, so

100\%

would restore the unweighted ranking (the losses differ by more than an order of magnitude across models). Filled markers have essentially no cell at exactly

1.0

; open ones carry the share shown. The uncapped Santander booster separates the two conditions: it realized

0.98

of its intended shift and the inversion still returns only 5%, because 16.6% of its cells sit at exactly

1.0

. Omitted: the Santander MLP (shift identifiable on 1 of 24 labels) and two Instacart caps with no loss to return. The two conditions are an empirical association, not a proven characterization. Scatter of every trained weighted model: the median realized-over-intended per-label shift on a logarithmic horizontal axis against the share of the top-K loss that the analytic inversion returns. Every model sits at or near a ratio of one or well to its left. The small caps sit well left of one and return nothing or less; the largest Santander cap sits just left of one and returns almost all of the loss, as does the Instacart MLP just right of one; the two uncapped, saturated models sit near one on the horizontal axis but only just above zero.

Figure 4. On public data the recommended weight is benign or mildly harmful on most datasets and collapses the ranking where the labels are many; on delicious and Corel5k per-label calibration with the prior fallback returns the collapsed models to the unweighted level.

\mathrm{MAP}@K

on the standard test split of 11 MULAN datasets ( Tsoumakas et al., 2011 ) (rows, sorted by label count

L

;

K=\min(7,L)

) for 5 one-vs-rest learners (panels), each trained without weights (

w{=}1

, filled blue) and with the recommended weight (

w_{j}=n_{-,j}/n_{+,j}

, filled orange); the open circle is the weighted model after per-label isotonic regression with the prior fallback, and the grey tick the popularity baseline. Shaded rows are the 8 of 55 cells in which the weighted model keeps less than half of its unweighted

\mathrm{MAP}@K

(a threshold chosen for the figure; at

0.3

0.7

and

0.9

the count is 4, 10 and 16): all 5 learners on delicious (

L=983

), 2 on Corel5k (

L=374

), 1 on genbase. Calibration split: 30% of the training file (seed 42); Supplement S6 has every cell and four weight magnitudes. Five panels, one per learner, each with eleven rows of MULAN datasets sorted by label count. In each row a blue dot marks the unweighted model, an orange dot the weighted model and an open orange circle the weighted model after per-label isotonic calibration; a grey tick marks the popularity baseline. Rows where the weighted dot falls below half of the blue dot are shaded: all five learners on delicious, two on Corel5k, XGBoost on genbase.

									$w{=}1$		$w{=}r$					distinct
dataset	$L$	$K$	$n_{\mathrm{fit}}$	$n_{\mathrm{test}}$	cal. pos.	$\min r$	$\max r$	pop.	raw	pl-iso	raw	what-if	inversion	pl-iso	ceiling	$w{=}1$	$w{=}r$
emotions	6	6	274	202	32	1.5	3	0.588	0.764	0.776	0.760	0.757	0.763	0.775	0.805	202	202
scene	6	6	848	1196	60	3.5	6	0.430	0.874	0.873	0.873	0.877	0.871	0.870	0.883	1195	1195
flags	7	7	79	65	22	0.3	6	0.802	0.829	0.805	0.788	0.762	0.838	0.823	0.870	58	59
yeast	14	7	1050	917	126	0.3	80	0.626	0.694	0.695	0.688	0.683	0.691	0.689	0.704	917	917
birds	15	7	226	323	5	7.7	112	0.392	0.593	0.549	0.601	0.593	0.593	0.500	0.675	322	321

Table 2. At moderate imbalance the sign of the weight’s effect is dataset-dependent; where the labels are many (bottom two rows) the weighted model collapses and per-label calibration returns it to the unweighted level. Default LightGBM one-vs-rest on 11 MULAN datasets,

\mathrm{MAP}@K

with

K=\min(7,L)

on the standard test split.

n_{\mathrm{fit}}

: training rows after removing the calibration split (30% of the training file, at least 50 rows, seed 42); “cal. pos.”: median calibration positives per label; “pop.”: ranking by training prevalence. Unweighted model (

w{=}1

): raw and per-label isotonic with prior fallback. Weighted model (

w_{j}=n_{-}/n_{+}

): raw, what-if prediction (unweighted logits

+\ln w_{j}

), analytic inversion, per-label isotonic with prior fallback, in-sample ceiling. Last columns: mean number of distinct scores per label.

\min r<1

marks a majority-positive label; a label with no positive in the fit split is recorded as

r=1

(genbase, medical, Corel5k).

Learning to Rank

Learning to rank develops models that order items by relevance or utility for search, recommendations, and other decisions.

See all 273 papers

Apr 2, 2026

Beyond Logit Adjustment: A Residual Decomposition Framework for Long-Tailed Reranking

Long-tailed classification, where a small number of frequent classes dominate many rare ones, remains challenging because models systematically favor frequent classes at inference time. Existing post-hoc methods such as logit adjustment address this by adding a fixed classwise offset to the base-model logits. However, the correction required to restore the relative ranking of two classes need not be constant across inputs, and a fixed offset cannot adapt to such variation. We study this problem through Bayes-optimal reranking on a base-model top-k shortlist. The gap between the optimal score and the base score, the residual correction, decomposes into a classwise component that is constant within each class, and a pairwise component that depends on the input and competing labels. When the residual is purely classwise, a fixed offset suffices to recover the Bayes-optimal ordering. We further show that when the same label pair induces incompatible ordering constraints across contexts, no fixed offset can achieve this recovery. This decomposition leads to testable predictions regarding when pairwise correction can improve performance and when cannot. We develop REPAIR (Reranking via Pairwise residual correction), a lightweight post-hoc reranker that combines a shrinkage-stabilized classwise term with a linear pairwise term driven by competition features on the shortlist. Experiments on nine benchmarks confirm that the decomposition explains where pairwise correction helps and where classwise correction alone suffices. These span text classification, visual recognition, and multimodal rare-disease diagnosis.

Zhanliang Wang, Hongzhuo Chen, Quan Minh Nguyen +2

University of Pennsylvania, Philadelphia, PA, USA · Children’s Hospital of Philadelphia, Philadelphia, PA, USA

Long-Tailed Classification Learning to Rank Residual Learning Pairwise Ranking

Ask PDF

May 28, 2026

Calibrated Preference Learning: The Case of Label Ranking

Calibration, the alignment of predicted probabilities with true outcome frequencies, is essential for reliable decision-making. While extensively studied for classification and regression, calibration has not been formally addressed for probabilistic label ranking, where the goal is to predict a distribution over orderings of a label set. Naively treating rankings as classes ignores their structure and fails to capture important modalities such as pairwise and top-k predictions. We formalize calibration for label ranking and develop a hierarchy of notions covering full rankings, sub-rankings, and top-k rankings. We prove that full-rank calibration implies the others but not conversely, and sub-ranking and top-k calibration are incomparable. Empirically, we find popular label ranking models are often poorly calibrated, with substantial differences between sub-ranking and top-k metrics. Applying our framework to RLHF reward models, we find that calibration correlates strongly but not perfectly with benchmark accuracy, suggesting it captures a meaningful quality dimension beyond top-1 accuracy. These findings motivate future work on understanding the downstream effects of miscalibration and developing methods to correct it.

Santo M. A. R. Thies, Viktor Bengs, Timo Kaufmann +2

Data Science and its Applications, Deutsches Forschungsinstitut für Künstliche Intelligenz (DFKI), Kaiserslautern, Germany · Munich Center for Machine Learning, Munich (MCML), Germany · Ludwig Maximilian Universität München, Munich, Germany

Probability Calibration Learning to Rank Preference Learning

Ask PDF

Jul 12, 2026

Exact and Certified Data Shapley for Weighted k-Nearest-Neighbor Regression and Soft-Label Prediction

Data Shapley is the standard principled answer to which training points are worth what, and its k-nearest-neighbor (KNN) specialization is the version deployed in practice: the exact estimator shipped by toolkits such as pyDVL and OpenDataVal. Exact algorithms are known for unweighted KNN and for weighted KNN classification, but weighted KNN regression and soft-label prediction have resisted: the only exact method is an O(N^K) brute force, exponential in neighborhood size K. The obstruction: the weighted regression prediction is a ratio of two coalition-dependent sums, whose normalization denominator breaks the additive, threshold, and duplication structures the prior polynomial algorithms rely on. We close this gap. We give (i) the first pseudo-polynomial-time exact algorithm (polynomial in N and K at fixed lattice precision) for weighted KNN-regression Data Shapley, a counting dynamic program over the joint integer state (sum of w, sum of w*y), verified against exhaustive enumeration with zero mismatch on 12,716 adversarial instances; (ii) a certified FPTAS for continuous weights and targets, with a machine-checkable per-value error certificate never violated across 86,400 checks; (iii) a complexity landscape, including an unconditional Omega(D_w) output-size lower bound and access-model hardness results; and (iv) a weighted soft-label multi-class extension. We release an open-source, CPU-only library and the first exact weighted-regression Data Shapley ground truth. On downstream mislabel detection our exact values are statistically equivalent to Monte-Carlo Data Shapley (dataset-level TOST, n=8, p<10^-4), the pre-registered outcome; the value of exactness is instead determinism, a certified error bound, and an exact reference for auditing estimators: Monte-Carlo did not reproduce the exact top-10% ranking at any budget tested, up to 3,000 permutations (~1.28e6 utility evaluations).

Zongye Lyu

Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia

Shapley Value Attribution k-Nearest Neighbors Approximation Algorithms

Ask PDF

Abstract

Learning to Rank

Explore similar work

Beyond Logit Adjustment: A Residual Decomposition Framework for Long-Tailed Reranking

Calibrated Preference Learning: The Case of Label Ranking

Exact and Certified Data Shapley for Weighted k-Nearest-Neighbor Regression and Soft-Label Prediction