Tie-Aware Partial AUC for Low-Precision Scorers

Many deployed classifiers, including fraud filters, cancer screens and compound triage, are judged by how many positives they catch while the false-alarm rate stays under a hard cap such as 1%. That quantity is the partial AUC: the area under the ROC curve restricted to the low-false-positive window. Every training method for it assumes that each example gets a distinct score. On real hardware the assumption fails. Quantized models emit one of a few dozen or a few hundred score levels, ReLU networks with many dead units give thousands of inputs the same output, and rounded calibrated probabilities collide. When a block of tied negatives straddles the false-positive cap, the partial AUC depends on how the software happened to order that block. The value is then not a single number but a range.

We propose a remedy that fixes both evaluation and training. For evaluation, partial AUC under uniform random tie-breaking has a simple closed form, which we pair with its pessimistic and optimistic bounds. For training, the same discreteness that causes ties also removes the main obstacle to optimizing partial AUC. Once scores take only $L$ levels, the metric depends exactly on $2L$ counts: positives and negatives per level. The global top-$\beta$ negatives can then be tracked with running histograms instead of sorting. This lets us train a quantized scorer for exactly the operating window it will be deployed at, with the tied boundary block handled analytically rather than arbitrarily.

Core Claim

For a scorer whose outputs are discrete, the expected one-way partial AUC over false-positive rates $[0,\beta]$ under uniform tie-breaking can be computed in closed form from per-level counts. Write $P_{>}$ for the number of positives scored strictly above a tie block. Write $p$ and $q$ for the numbers of positives and negatives inside the block, and $k$ for how many of the block's negatives fall inside the window. A standard order-statistics fact gives the expected number of block positives ranked above the $i$-th block negative as $ip/(q+1)$. So the block contributes

$$ C = k\,P_{>} + \frac{p\,k(k+1)}{2(q+1)} $$

pairs to the partial-area numerator. The pessimistic and optimistic conventions replace the second term with $0$ and $kp$ respectively. Two consequences follow. First, linear interpolation of the ROC curve through the block contributes $pk^2/(2q)$, which differs from the expectation unless the block is fully inside the window ($k=q$). So the trapezoid rule that makes global AUROC tie-robust, as the AUPRC software audit Commonly used software tools produce conflicting and overly-optimistic AUPRC values observed, does not carry over to the truncated case. Second, if the per-level counts are replaced by soft counts from a differentiable binning of scores, the formula becomes a smooth training objective. That objective equals the deployed metric exactly once the binning hardens.

The new part is the combination of three things. The first is a truncation-aware tie expectation, which existing tie-aware metrics lack. The second is the observation that a discrete score space makes partial AUC decomposable through global histograms. The third is a training procedure built on that observation for quantized deployment.

Relation to Prior Work

Two lines of work motivate the problem. The embedding audit Non-deterministic Behavior of Ranking-based Metrics when Evaluating Embeddings found that real continuous embeddings collide about 10,000 times more often than white noise and that a collapsed all-zero model could reach 10.32–18.68% mAP by reordering inputs. The knowledge-graph re-evaluation A Re-evaluation of Knowledge Graph Completion Methods traced ties to 87.3–92.2% neuron death and showed CapsE's MRR on FB15k-237 falling from 0.523 to 0.150 when optimistic tie-breaking was replaced by random tie-breaking. Both are evaluation audits of full-list metrics. We extend the audit to partial AUC and then go further, into training.

Two evaluation conventions supply our reporting protocol. The embedding audit defined pessimistic and optimistic mAP bounds, and PyKEEN 1.0 institutionalized logging of optimistic, pessimistic and average ranks. We report all three for partial AUC. Our "expected" value differs from PyKEEN's average rank, which averages the two bounds; for a truncated metric that average is not the expectation under random tie-breaking.

The training mechanism borrows from Hashing as Tie-Aware Learning to Rank. That work computed closed-form expectations of AP and NDCG over tie permutations and trained hashing networks through soft histogram binning. Its expectations cover the full retrieval list and have no term for a block cut by a truncation point. The straddle term above is exactly what it lacks.

On the partial AUC side, A Structural SVM Based Approach for Optimizing Partial AUC and Support Vector Algorithms for Optimizing the Partial Area Under the ROC Curve derive the most-violated-constraint search under an explicit no-ties assumption and name ties as future work. That leaves the open problem we take up. The deep methods supply our baselines and the tracking machinery we adapt:

All of these assume continuous scores. Under CVaR-style formulations, a mass of negatives sitting exactly at the threshold makes the threshold's subgradient set-valued. We do not claim that the KL-smoothed variant breaks under ties, since it assigns equal weights to tied negatives. Our claim against it is narrower: it optimizes a soft surrogate rather than the exact quantized metric at $\beta$.

Finally, stochastic queuing in Large-scale Collaborative Ranking in Near-Linear Time reshuffles ties every iteration. Removing it dropped Precision@1 on MovieLens1M from 0.736 to 0.627. We treat it as the Monte Carlo counterpart of our closed form and test it directly.

Research Program

Evaluation tool. The first piece is a small, exact evaluation library. It sorts scores once, groups them into tie blocks, and returns expected, pessimistic and optimistic one-way partial AUC for any $\beta$. Two-way partial AUC is computed by applying the same block logic on the positive axis. Everything runs in $O(n\log n)$. We will verify the closed form against brute-force permutation averaging on small instances.

Audit. Using that library, we run an audit. We take models trained in 32-bit floating point with SOPA, UPAUCI and cross-entropy. We quantize their score heads, and separately whole networks, to 8, 6, 4 and 3 bits. We then measure how wide the pessimistic-to-optimistic interval becomes at $\beta \in \{0.01, 0.05, 0.1\}$, and how often model rankings flip across conventions. This is the partial-AUC analogue of the AUPRC software audit.

Training objective. The second piece is the objective itself. The scorer outputs a value that a quantizer maps to $L$ levels. During training, each score is softly assigned to neighbouring levels with a temperature-controlled kernel, as in the hashing work. This yields soft per-level counts of positives and negatives. Because $L$ is small, we keep exponential-moving-average estimates of the global negative histogram across mini-batches. From that histogram we locate the level where the cumulative negative mass crosses $\beta n_-$. That level's block receives the fractional straddle term from the closed form.

The objective is a smooth nonlinear function of running counts, so its stochastic gradient is compositional. We handle this the way SOPA handles its running threshold: gradients are taken through current-batch soft counts, plugged into moving-average estimates of the global ones.

Two variants and annealing. We build two variants. One maximizes the expected metric, matching a randomized-threshold deployment. The other maximizes the pessimistic metric, matching a deterministic hard-cap deployment that must reject a whole straddling block. The gap between them is itself a penalty that pushes mass out of the boundary level. The binning temperature is annealed to zero, so at convergence the objective coincides with the deployed metric.

Theory. We will analyse stationarity under the moving-average estimates, following the compositional arguments of the DRO paper. We will also characterize when the expected and pessimistic optima differ.

Baselines

Floating-point training, quantized afterwards. The naive reference point is the strongest floating-point method, quantized post hoc with no further adaptation. For that method we take UPAUCI. Its paper reports one-way partial AUC at $\beta=0.3$ of 0.9587 on iNaturalist2021, against 0.9283 for an AUC-margin baseline (Closing the Approximation Gap). We also run SOPA, both the CVaR and KL-smoothed versions. For the two-way metric on CIFAR-10 subsets, the end-to-end framework reports roughly 18% for standard AUC training and 31% for its minimax method (Optimizing Two-Way Partial AUC). We first reproduce these floating-point figures so our implementations are trusted. No reported result was found on Lacuna for partial AUC of quantized or low-bit scorers, so the quantized-regime baseline numbers come from our own runs.

Quantization-aware training with an existing partial AUC loss. The strongest competitor is quantization-aware training with a straight-through estimator under the UPAUCI or SOPA loss. Here the forward pass sees quantized, tied scores, but the loss handles the boundary block by whatever order the sort returns. This competitor shares everything with our method except the treatment of ties and the histogram tracking, so beating it isolates our contribution. All quantization-aware methods share one protocol:

  • the same backbones, quantizers, epochs and data splits;
  • an equal hyperparameter search budget of 20 configurations per method on the validation split, covering learning rate, smoothing temperature and DRO temperature;
  • five seeds each.

Cross-entropy reference. Class-balanced cross-entropy with the same quantization serves as the pointwise reference. The DRO paper reports that partial AUC methods improve "dramatically" over cross-entropy on Melanoma and ogbg-molmuv, but gives no numbers in the file.

Ablations. Two ablations isolate the key ingredient. The first keeps the histogram objective but assigns the straddling block wholly in or wholly out of the window, so the fractional term is dropped. The second replaces the closed form with per-iteration random shuffling of tied items, in the spirit of stochastic queuing.

What counts as beating a baseline. At 4 bits or fewer, we must exceed quantization-aware UPAUCI on pessimistic partial AUC at $\beta \le 0.05$ by more than two seed standard deviations, on at least three of the benchmarks below. Our pessimistic-to-optimistic interval must also be narrower. At 8 bits we expect parity and would report parity as such.

Why not just…?

Why not just train in floating point and quantize afterwards? This is a real threat. If the score head has enough levels, the boundary block may hold only a handful of negatives and the straddle term becomes negligible. The audit settles it directly by measuring partial AUC loss and interval width as a function of bit depth. If the loss vanishes at 6 bits and above, we will restrict our claims to the very low-bit regime and to collapsed networks, rather than argue otherwise.

Why not just use quantization-aware training with SOPA or UPAUCI? It already exposes the loss to tied forward scores. However, its boundary handling is still arbitrary, and its threshold or dual variables were derived for continuous scores. The no-ties assumption flagged in A Structural SVM Based Approach for Optimizing Partial AUC is the clearest statement of that gap. The second baseline above is designed so that it differs from our method only in tie handling, and the comparison will show whether that matters.

Why not just add small random noise to scores to break ties, during training and evaluation? Noise narrower than the gap between quantization levels reproduces random tie-breaking in distribution. In expectation, then, it optimizes the same quantity as our closed form, but with sampling variance. The embedding audit found that random tie-breaking makes metrics run-dependent (Non-deterministic Behavior of Ranking-based Metrics when Evaluating Embeddings). Noise also cannot target the pessimistic metric that a hard-cap deployment actually earns. Our shuffling ablation measures both the gradient variance and the final metric. If noise matches the closed form, the training contribution reduces to cheaper, deterministic gradients. In that case we would say so and lead with the evaluation tool and the pessimistic-objective result.

Why not just log optimistic and pessimistic bounds, as PyKEEN does? Logging reveals ambiguity but does not reduce it. Moreover, the midpoint of the bounds is not the expected partial AUC once truncation cuts a block. The audit will report how far the midpoint and the expectation diverge on real quantized models.

Proposed Experiments

Benchmarks. We use the benchmarks on which the partial AUC methods were themselves evaluated:

  • binary splits of CIFAR-10-LT and CIFAR-100-LT, and Tiny-ImageNet-200-LT, following UPAUCI's protocol;
  • Melanoma and ogbg-molmuv, following SOPA;
  • iNaturalist2021, as the scale test;
  • the KDD Cup 2008 and protein-protein interaction tasks, for a linear-model check against Support Vector Algorithms for Optimizing the Partial Area Under the ROC Curve. On protein interactions, the structural SVM reported 51.79 versus 39.72 for full-AUC training.

Metrics. We report one-way partial AUC at $\beta \in \{0.01, 0.05, 0.1\}$ and two-way partial AUC, each under expected, pessimistic and optimistic conventions. We also report true-positive rate at a deterministic threshold that respects the false-positive cap, the fraction of negatives in the boundary level, and standard deviation across seeds.

Decisive checks. The first check is whether, at 4 bits, the expected and pessimistic partial AUC of post-hoc-quantized UPAUCI differ by more than seed noise. If they do not, ties are not the bottleneck there. The second is whether our pessimistic-objective model closes that gap and beats quantization-aware UPAUCI on deployed true-positive rate at the cap. The third is whether the fractional straddle term helps beyond the whole-block ablation, which tests the specific mathematical contribution. The fourth is whether the closed form matches or beats random shuffling with lower gradient variance.

Stress test. A separate test checks for masking. We deliberately induce ReLU unit death with a high learning rate. We then ask whether our objective's boundary penalty avoids the collapsed solutions that optimistic evaluation would otherwise reward, as happened to CapsE.