CS Paper Radar

When Does an AUROC Comparison Survive a Change in Population Mix?

Mahtab Movahhedrad, Hamidreza Hasani Balyani, Seyed Pouyan Mousavi Davoudi

cs.LG cs.CV ·submitted 2026-11-15 03:42 UTC · v1
theory

Abstract

Does an AUROC comparison survive a change in the proportions of tasks, populations, or image corruptions? A pooled-AUROC ranking of failure detectors or uncertainty scores describes one particular mix of groups. We study two fixed scores for a common binary target under mixtures of fixed group-conditional laws. Using the cross-group AUC decomposition, we prove that every rational symmetric quadratic comparison geometry is realizable by finite scalar-score distributions. Universal dominance is thus coNP-hard, and even exhaustive checks of every mixture on fewer than $K$ groups can miss a $K$-group reversal. A grid bound gives a dimension-uniform approximation certificate with sharp $1/m$ order. Common score marginals across groups make the comparison numerator linear, with an error envelope for imperfect alignment. These results yield exact finite-bank audits, explicit reversal mixtures and distances, and simultaneous population statements. For failure detection with a frozen ResNet-50 on ImageNet-C, 15 of 18 confidence-score comparisons win in every corruption family on a discovery split, and all 15 are finite-bank certified over all family mixtures on a held-out split; over all 15 corruption types, of 14 discovery winners the corrected grid certifies 10, leaves 3 unresolved, and finds one confirmation reversal of at least 0.05 AUROC. An audit of all 11,019 released Stable LM 2 12B outputs and 35 uncertainty methods finds 66 confirmation-set comparisons that win within all four tasks yet reverse under mixing. Discovery-fitted marginal rank alignment removes all 66; an alignment-error envelope certifies 83 comparisons. Label checks also change several selected reversals. The findings distinguish robustness of frozen scores from robustness after calibration; they do not establish human-error detection, robustness to unseen corruptions, or generalization beyond the evaluated banks.

Comment
30 pages, 5 figures. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Closest papers

Nearest neighbours by meaning across the whole index.

Identities, Not Pairs: Distribution-Free False-Accept Control for Embedding-Based Verification

cs.LG stat.ML ·2026-10-26 ·Salim Khazem
code/data similarity 0.57
Abstract

Embedding-based verification often calibrates a false-accept threshold from all impostor pairs among $m$ identities, although these pairs share identities. We characterize a worst-case limit: when hub identities score highly against a fraction $ρ$ of the population, a calibration-only threshold with marginal false-accept rate (FAR) at most $α$ under every identity-exchangeable law reaches the hub score on hub-free calibration sets with probability at most $(m+2)α/(2ρ)$. Uniformly accepting near that score at levels well below $ρ/m$ therefore requires trial information. We propose COVE, which ranks the trial pair among all $N=\binom{m+2}{2}$ pairs formed by augmenting the calibration units with the probe and reference. Under identity exchangeability, its marginal FAR is at most $\lfloorαN\rfloor/N$, with first possible acceptance at $1/N=O(1/m^2)$. The rule also retains this guarantee with a fixed symmetric cohort-normalized score using an independent cohort. On 6 benchmarks and 8 frozen encoders, realised FAR was consistent with the exact bound. Where both valid calibration-only baselines accepted nothing, COVE retained a median $100\%$ of the sampled oracle's true-accept rate over reliable comparisons. In contrast, an empirical quantile over dependent pairs reached 2.87$\,α$ FAR, and a binomial upper confidence bound over pairs missed its nominal 95\% conditional-FAR target in up to 55\% of calibration draws. Symmetric CSLS raised COVE's true-accept rate by up to 4.3-fold in the tested settings. The code is available in https://github.com/salimkhazem/Cove.git

0.37

Anytime-Valid PAC-Bayes Certificates for Adaptive Test-Time Scaling

cs.LG cs.CLstat.ML ·2026-11-16 ·Xiaoyu Li, Jiangxuan Long
top venue similarity 0.57
Abstract · Accepted at NeurIPS 2026. Xiaoyu Li and Jiangxuan Long contributed equally. 31 pages, 7 figures, 15 tables

Test-time scaling systems often choose how much to sample, which prompt to use, and which verifier or aggregation rule to trust after repeatedly inspecting a calibration set. Standard validation error bars are not valid after this adaptive selection. We model a test-time scaling recipe as a randomized predictor with a random cost and prove a time-uniform PAC-Bayes certificate that holds simultaneously over all calibration times, all posterior mixtures over recipes, and all data-dependent stopping rules. Thus the same event covers the recipe search that precedes deployment, not merely the fixed recipe finally reported. For a finite grid of budgets and verifiers, the penalty is the familiar $\log M/n$, which in the worst case no certificate valid after selection can avoid, while non-uniform priors and localized posterior mixtures can give sharper certificates for structured searches. We specialize the result to self-consistency and show a complementary margin law: plurality voting improves exponentially in the sample budget only on examples where the correct answer is the generator's unique mode; otherwise more compute can provably amplify errors. The same margin analysis yields an oracle water-filling law for compute allocation. A synthetic audit quantifies the optimism caused by adaptive budget selection, and a 192-example GSM8K audit using gpt-4.1-mini generations illustrates risk-cost reporting for a real inference pipeline. At scale, with two models on GSM8K and MATH-500, selected-best error bars fall below the out-of-split GSM8K risk in up to 22.5% of random splits at a nominal 5% while the certificate never does, and on the full GSM8K test split it tightens to 0.109 (held-out risk 0.039). The results give a lightweight, distribution-free way to report risk and compute claims for adaptive inference systems.

0.51

Strength Is Not Value: Rethinking Approximate Functional Dependency Measures for Error Detection

cs.DB ·2026-10-06 ·Xiaolong Wan, Xixian Han
benchmark similarity 0.56
Abstract

Approximate functional dependency (AFD) strength measures are commonly used to prioritize candidate dependencies, including when selected dependencies support downstream tasks such as error detection. This practice implicitly assumes that dependencies ranked higher by strength are also better candidates for the task they are intended to support. We test this assumption directly for error detection. We evaluate detection value through precision and recall without imposing a single weighting on different error types, and introduce an explicit false-positive/false-negative cost only when a single candidate-selection objective is required. Across three real-world relations from an established AFD benchmark, $1{,}155$ corruption-and-detection runs, and $513{,}480$ candidate-level evaluations, we find a clear asymmetry. Strength measures tend to track precision positively, but their associations with recall are substantially less stable, with both magnitude and direction varying across measures and experimental settings. Strength-based prioritization is also unreliable at the ranking level: top-$k$ sets chosen by strength often have little overlap with those favored by actual detection performance, and strength-based selections can incur substantial regret. An important part of the recall mismatch is associated with structural detection opportunity under the candidate equivalence-class partition, which tracks recall more consistently overall than the strength measures we evaluate. Corruption mechanism and several static structural properties account for selected effects but do not provide a common explanation across settings, leaving part of the mismatch unresolved. Overall, AFD strength and detection value are distinct and should be evaluated separately.

0.38

VFR-Audit: Verdict-Level Reliability for Fairness Audits in Hospital Length-of-Stay Prediction

cs.AI ·2026-08-31 ·Md Jannatul Rakib Joy, Viet Vo, Caslon Chua
top venue similarity 0.56
Abstract · 12 pages, 5 figures. Accepted at the 35th ACM International Conference on Information and Knowledge Management (CIKM 2026)

Fairness audits in clinical Artificial Intelligence convert continuous fairness metrics into binary pass-or-fail verdicts against operational thresholds, where hospital governance boards, payers, and regulators act on the resulting verdicts. Such audits are repeated over time and across hospital sites, thus the same verdict can flip between pass and fail across audits. Existing uncertainty methods such as Bayesian posteriors, bootstrap confidence intervals, and permutation tests address verdict instability only at the continuous-metric level. Converting metric-level uncertainty into a verdict-stability claim remains a manual step that scales poorly across the (model, metric, attribute) cells an audit covers. Existing uncertainty methods also leave open whether bias-mitigation steps, such as reweighing or per-group threshold shifts, yield a stable passing verdict at the cost of model discrimination measured as AUROC or AUPRC.To address this verdict-stability gap, we propose VFR-Audit, a framework built around the Verdict Flip Rate (VFR), a scalar bounded between 0 and 0.5 that measures the probability of verdict reversal under stratified bootstrap resampling. VFR-Audit reports VFR alongside three reliability axes, namely within-cohort resampling stability, audit-size sensitivity, and cross-hospital verdict agreement via Fleiss' kappa.

0.36

Exact Dice Degradation Envelopes for Label-Free Segmentation Update Selection

eess.IV cs.LG ·2026-10-01 ·Yuvraj Verma
similarity 0.56
Abstract · 18 pages, 7 figures, 6 tables. Includes mathematical proofs and a three-seed study on ClinicDB, Massachusetts Buildings, and Kvasir-SEG

Test-time segmentation updates can improve an unlabeled input while damaging another. Confidence and transformation consistency can rank candidates, but do not in themselves bound the loss caused by returning a changed mask. We derive the exact largest decrease in binary Dice between a baseline and a candidate, maximized over every possible unknown reference mask on the same pixels. A maximizing reference always lies inside baseline foreground: three observable mask counts reduce the problem to at most four reference-cardinality checks. Accepting an output only when its envelope is below a budget gives a deterministic, per-case Dice degradation limit relative to the baseline. A finite grid of logit interpolations permits partial candidate outputs without extra network forwards. Exhaustive and randomized validation checks 5,026,592 reference masks with no discrepancy. We evaluate six independently trained MK-UNet sources, three seeds per task, on ClinicDB, Massachusetts Buildings and the external Kvasir-SEG cohort, including appearance corruptions. Across 17,808 case-condition-seed evaluations, 0 certificate violations occur in the checked candidate comparisons. At a one-point Dice budget, exact versus loose interpolation changes the returned mask in the following fractions of episodes (ClinicDB: 51.0% versus 38.7%; Buildings: 62.1% versus 53.1%; Kvasir-SEG: 52.3% versus 34.9%). Mean Dice effects and useful-update rejection are reported separately from admissibility. An exploratory oracle-presence-bit ablation examines how weak supervision relaxes the empty-baseline restriction. The envelope quantifies relative mask-change risk; it does not certify anatomical correctness, preserve other metrics, or guarantee adaptation benefit.

0.33

Beyond Mean Foils: Auditing Worst-Foil Specificity in Frozen CLIP Region Explanations

cs.CV ·2026-09-23 ·Kaixin Liu, Zhipeng Ye, Feng Jiang, Zhenghao Wang, Qihang Wu
similarity 0.56
Abstract · 5 pages, 2 figures, 6 tables

A region can overlap a target object yet contribute more to another class. We test regions selected by Cluster-based Concept Importance (CCI) in frozen CLIP. Across COCO and VOC with two checkpoints, 41.08-64.78% of regions that pass overlap and mean-contrast checks fail against the strongest competing class. Removing competitors annotated in the image leaves 39.69-63.64% failing. We then test all eight candidate regions per image. An alternative passes the test for 6.25-7.84% of failures on COCO and 27.40-31.15% on VOC. Requiring it to preserve the original target-score drop within $ε= 0.02$ reduces these rates to 0.16-0.98%. Available regions and target-drop tolerance constrain repair; relaxing the tolerance increases repair opportunities.

0.27

Certifying the Error-Detection Value of Functional Dependencies without Ground Truth

cs.DB ·2026-11-09 ·Xiaolong Wan, Xixian Han
similarity 0.55
Abstract

Functional dependencies are used to flag erroneous cells, but without error labels the value of these flags is unknown. Dependency strength cannot settle it, because identical data and flags can have positive value in one clean state and negative value in another. We treat this value as partially identified and certify a fixed detector when its value is positive in every clean state compatible with the observation under an error model and budget. The largest such budget is the certification radius. For a detector that flags departures from the unique mode of each class, the worst case reduces to a 0/1 knapsack over class flips, yielding sharp bounds on true positives and the exact radius in polynomial time. Allowing bounded legitimate exceptions in the clean data, we derive an exact threshold for the existence of a positive certificate and compute the radius with the same knapsack. Across five relations and 21,981 candidate dependencies, rules with nearly equal $g_3$ and flag rate can have certification margins differing tenfold. Error injection confirms sound certification and shows that, at equal error counts, changing the organization of errors reverses certification outcomes for every tested rule.

0.33

Common-Witness Certificates and Sharp Feature Bounds for Counterfactual Image Auditing

cs.AI ·2026-09-03 ·Usef Faghihi, Amir Saki
similarity 0.55
Abstract

An image editor may satisfy every regional plausibility constraint separately even when no single latent explanation fits the complete output. We formalize this local-to-global failure using a common witness grade and witness nerve. The framework separates auditing from causal identification: shared exogeneity alone allows every coupling of the regime marginals, whereas an externally justified witness relation yields sharp partial-identification bounds for prespecified image features. Helly-type arguments provide short incompatibility certificates for quasiconvex losses, heterogeneous action strata, and finite witness atlases; a blocker-hypergraph formula gives exact repair counts. Simultaneous confidence regions for the regime marginals give finite-sample outer coverage of the complete identified interval. Controlled MNIST, Morpho-MNIST, and smallNORB studies demonstrate the predicted local-global separation, while synthetic experiments test sharp bounds, certificate recovery, and structured computation. The method audits a declared feature relation and does not identify unrestricted pixel-level counterfactuals.

0.26