Equal-Evidence Neighborhoods for Multi-Label Abstention

A multi-label classifier, such as one that tags every object in a photo, can be wrapped in a statistical guarantee: "on average, you will miss at most 10% of the true tags." The strongest tool for this, Conformal Risk Control, achieves it on MS COCO without ever enumerating the $2^{80}$ possible tag combinations. The guarantee holds only on average over all images, though. Unusual images, which are rare in the data and therefore sit in sparse regions of the input space, can fail far more often than the average suggests. A second problem compounds this one. The guarantee assumes the labeled examples used to set the threshold (the calibration set) look like future data. When the calibration set comes from a public benchmark that the pretrained model has already seen during training, the model is overconfident on exactly those examples. The threshold then comes out too optimistic, and the guarantee can fail on fresh images without any visible sign.

We propose one mechanism aimed at both failures. For each test input, the method calibrates only on nearby calibration examples. The neighborhood is not a fixed radius or a fixed count. Its width is chosen so that every query is backed by the same effective number of calibration examples. This borrows the perplexity-matching rule from Stochastic Neighbor Embedding, where each point gets its own kernel width so that its neighbor distribution has a fixed entropy. The model then commits to confident tags, abstains on ambiguous ones, and controls the miss and false-alarm rates within each neighborhood. We test the method under calibration contamination whose extent we control and can measure.

Core Claim

The finite-sample analysis of localized conformal prediction in Beyond Marginal Validity splits the local coverage error into two terms. The first is a bias of order $h^\beta$, which grows with the neighborhood width $h$ ($\beta$ measures how smoothly the score distribution changes across the input space). The second is a variance term driven by the effective local sample size. With a fixed $h$, sparse queries get very few effective samples. This is the source of the 1.5× to 2.6× wider intervals that paper reports. Our claim is that if the width is set per query so that the entropy of the normalized calibration weights is held fixed, the variance term becomes uniform across the space. All the heterogeneity is then pushed into the bias term, which can be kept small by localizing in a low-dimensional coordinate system in which the loss varies smoothly.

We propose to localize in the model's own predicted-marginal vector, reduced by a projection fit on training data. We do not localize in raw features. This choice sidesteps the $1/h^d$ penalty on raw features that the same paper identifies.

Concretely, let $z(x)$ be the reduced prediction coordinates of input $x$, let $z_i$ be those of calibration point $i$, and let $K$ be a Gaussian kernel. The weights are $w_i(x)=K(\lVert z_i-z(x)\rVert/h(x))$, normalized to $\bar w_i$ with the test point included. The bandwidth function $h(\cdot)$ is fit on a separate split so that

$$\exp\Big(-\sum_i \bar w_i \log \bar w_i\Big) \approx n_{\text{eff}},$$

where $n_{\text{eff}}$ is a user-chosen evidence level. Because $h(\cdot)$ is fixed before calibration, the randomized-localization guarantees of the file's RLCP analysis apply as stated.

Given a per-label score $p_k(x)$, the prediction is ternary. Label $k$ is committed positive if $p_k>1-\mu$, committed negative if $p_k<\lambda$, and abstained otherwise. Define $L_i(\lambda)$ as the fraction of calibration point $i$'s true labels that are committed negative. This loss is monotone in $\lambda$. The local threshold is

$$\hat\lambda(x)=\sup\Big\{\lambda:\ \sum_{i\le n}\bar w_i L_i(\lambda)+\bar w_{n+1}\le \alpha_1\Big\},$$

where $\alpha_1$ is the miss budget. The loss is bounded by 1, so the test point's weight $\bar w_{n+1}$ enters at the worst case. An analogous rule sets $\mu$ against a false-alarm budget $\alpha_2$.

Validity requires no conditional-independence assumption among labels, and no pass over $2^K$ or $3^K$ label configurations. The base model can be a classifier chain or a Conditional Bernoulli Mixture that captures label dependencies. The guarantee only needs the per-label scores.

Relation to Prior Work

Three papers motivate the gap.

  • Beyond Marginal Validity supplies the localization analysis. It reports a +16.3% worst-slice coverage improvement over split conformal on Bike-Synth. It uses a single bandwidth, however, and is tested only on scalar tabular regression.
  • Conformal Risk Control supplies the monotone-loss calibration we localize. It is marginal only.
  • Act or Defer shows how badly marginal selection can fail. Standard conformal selection achieved only about 10% selected coverage for pancreatic cancer at $\alpha=0.10$, against more than 99% for its class-stratified STRATCP. That paper stratifies by label, not by input region, and does not treat full multi-label vectors.

The partial-abstention work of Nguyen and Hüllermeier and its Bayes-optimal follow-up supplies the ternary output. It derives optimal abstention bands under conditional label independence, using uncalibrated marginals and global costs. We keep the ternary form but replace the Bayes derivation with distribution-free local calibration.

Two papers constrain the design. Split Conformal Prediction under Data Contamination studies outlier-style contamination, which inflates quantiles and causes over-coverage (99% coverage and a mean set size of 5.47 on CIFAR-10N, against 91.7% and 2.18 for its CRCP correction). Our concern is the opposite direction. Memorized calibration items produce low scores, and the threshold becomes too permissive. On The Fragility of Benchmark Contamination Detection in Reasoning Models and the Naive-Trim failure in Robust Conformal Outlier Detection warn against relying on a detector to purge contaminated items. For this reason we treat contamination as a stress condition to measure, not a label to predict.

Localizing in prediction space is not a cure for contamination, and we state its expected failure mode openly. Memorized items tend to sit at near-zero output entropy, as Yax et al. observe for contaminated reasoning sequences. A fresh query with moderate entropy will therefore mostly draw fresh-looking neighbors. A fresh query that is confidently wrong will draw memorized neighbors and be under-covered.

Research Program

The work has three parts.

The first is theoretical. We will restate the RLCP coverage bound for monotone bounded losses under a fixed bandwidth function. We will show that the perplexity constraint makes the variance term constant across $x$. We will then characterize the residual bias as a function of the dimension of the projection $z$.

The second part is a contamination model for calibration. A fraction $\epsilon$ of calibration points are "seen" points, whose loss distribution is stochastically smaller than that of fresh points, and the seen points are concentrated in a region of $z$-space. Under this model we will bound the local under-coverage suffered by fresh queries. The bound depends on the local seen-fraction $\epsilon(x)$, not the global $\epsilon$. This yields a testable prediction: localization helps when contamination is spatially concentrated and fresh test points fall outside it, and hurts in the reverse case.

The third part is an estimator. We will estimate $\epsilon(x)$ from a small audit budget in the spirit of Label-Trim, which reported near-oracle power with 40 to 50 inspected points. In our setting, auditing means verifying whether an item appears in training data. We will then apply a CRCP-style inflation of $\alpha_1$ locally rather than globally.

Baselines

The naive reference point is binary relevance with a fixed abstention band $[0.5-\delta,0.5+\delta]$ on uncalibrated marginals, following the partial-abstention formulation of Nguyen and Hüllermeier. We tune $\delta$ on the calibration split to match our average abstention rate. This baseline shows what happens with no statistical guarantee at all.

The strongest existing method is global Conformal Risk Control applied separately to the miss and false-alarm budgets, using the same base model and the same calibration pool. Conformal Risk Control reports a mean false negative rate of 0.0996 at a target of 0.10 on MS COCO. We will reproduce that marginal figure first. Beating it does not mean lower marginal risk, since both methods should hit the target. It means a lower worst-slice miss rate on density-defined and contamination-defined slices, at equal or lower abstention and set size.

The second strong competitor is label-stratified global CRC, which calibrates each label separately in the manner of STRATCP (Act or Defer). It targets rare labels without any spatial localization.

We then run two localization ablations that isolate the key ingredient. The first is fixed-bandwidth RLCP, with $h$ tuned by cross-validation on the bandwidth split. The second is fixed-$k$ nearest-neighbor calibration with $k=n_{\text{eff}}$. These separate the gain from localizing at all from the gain from matching evidence.

A third ablation localizes on raw backbone features instead of prediction coordinates, which tests the dimensionality argument.

Global CRCP from Split Conformal Prediction under Data Contamination serves as the contamination-aware baseline.

All methods share the same base model, the same splits, and the same budget of 20 settings for their single hyperparameter. That hyperparameter is $\delta$, $h$, $k$, or $n_{\text{eff}}$, and each is tuned on the bandwidth split only.

Why not just…?

Why not just calibrate each label separately with global CRC? This is the most serious threat. The dramatic STRATCP gains came from stratifying by label, and in multi-label data much of the rare-region failure may simply be rare-label failure. The experiments settle this directly. We define slices by input density, holding label frequency fixed within strata. If label-stratified CRC matches our worst-slice miss rate on those slices, the localization component is unnecessary. We would then narrow the claim to the contamination setting.

Why not just cluster the inputs and calibrate within each cluster? Fixed clusters are a coarse form of localization with a hard bandwidth. Sparse clusters still end up with tiny calibration pools, which produces the same wide sets that Beyond Marginal Validity reports for fixed bandwidths. The fixed-$k$ ablation is the smooth version of this alternative. If k-means clustering with a matched minimum cluster size performs as well as our method, the perplexity machinery adds nothing, and we will report that.

Why not just filter contaminated calibration items, or collect a fresh calibration set? Filtering relies on detectors that the fragility study shows break under post-training. Loss-based trimming removes legitimately hard points, which is the Naive-Trim failure in Robust Conformal Outlier Detection. A fresh, post-cutoff calibration set is the correct fix when one is affordable. We treat it as the oracle upper bound, not as a competitor. The question we address is how much of the oracle's coverage a contaminated pool plus a 50-item audit can recover.

Proposed Experiments

The main testbed is MS COCO, which gives continuity with CRC. We add NUS-WIDE and Mediamill from the MULAN collection used by Nguyen and Hüllermeier. No reported numbers were found on Lacuna for partial abstention on those two datasets, so we will establish our own references.

Contamination is injected so that the true $\epsilon$ is known. Starting from a base model trained on a disjoint split, we fine-tune it for a few epochs on a chosen subset of calibration images with their labels, at $\epsilon\in\{0,0.05,0.2,0.5\}$. We run two variants: the memorized subset is either spatially concentrated (one region of $z$-space) or spread uniformly. Test sets are always drawn only from never-seen images.

We report three sets of metrics:

  • marginal miss and false-alarm rates;
  • worst-decile miss rate over density slices, and over slices defined by distance to the memorized region;
  • abstention fraction and committed-set size.

The decisive checks are these. First, at $\epsilon=0$, our method should match global CRC's marginal risk of about 0.0996 on COCO while reducing the worst-slice miss rate below both label-stratified CRC and fixed-bandwidth RLCP, at no more than their abstention rate. Second, under concentrated contamination, global CRC should under-cover fresh test points as $\epsilon$ grows. Our method should cover fresh points outside the memorized region and fail inside it, as the bound predicts. The audited local correction should close most of the remaining gap relative to the fresh-calibration oracle. Third, under uniform contamination, localization should offer no advantage over global CRCP. If this holds, it confirms the mechanism rather than a generic gain.

If the first check fails against label-stratified CRC, the neighborhood idea does not earn its place.