Coverage Hides Churn: Auditing and Preserving Conformal Decisions as VLM Label Registries Grow

Jai Kumar Sharma, Peeyush Tapadiya

Vision-language models (VLMs) like CLIP and SigLIP have a superpower: they can learn new categories from text alone. If you're running an e-commerce catalog, you can add a "damaged packaging" category just by typing the name—no retraining required. To manage uncertainty, these models are often wrapped in conformal prediction, which returns a set of plausible labels rather than a single guess, guaranteeing that the true label is included with high probability (e.g., 90%).

But there’s a hidden cost to this flexibility. A new paper from researchers at Virginia Tech and Accenture reveals that as you add new labels to your registry, the system silently changes its mind about the old ones. This phenomenon, called churn, means a product previously flagged for review might suddenly drop out of the set simply because you added a new subcategory elsewhere.

TL;DR

Adding new labels to vision-language models silently changes previous conformal decisions—a phenomenon called "churn" that standard coverage metrics fail to detect. This paper introduces PrefixCP, which preserves old decisions by fixing the label registry for each class at its time of addition, ensuring system stability while maintaining rigorous class-conditional coverage guarantees.

What Problem Does This Paper Address?

The core issue lies in how we score labels. Most conformal methods for VLMs use a shared "normalizer" (like the denominator in a softmax function). This normalizer is calculated across the entire current label registry.

When you add a new label, the normalizer changes for every image. Consequently, the score for an old label like "macarons" might drop below the inclusion threshold even if the image and the model’s internal representation haven't changed at all.

Adding labels raises the shared normalizer, which can push an old, correct label out of the prediction set.

The authors show that standard evaluation metrics are blind to this. "Coverage"—the gold standard for conformal prediction—only checks if the true label is in the set. It doesn't care if the rest of the set is constantly shifting. The paper demonstrates that you can maintain a perfect 90% coverage while changing decisions on over 60% of your images.

Methods

The authors propose two main contributions:

  1. A Lifecycle Audit: A new evaluation protocol that measures churn (how many old decisions change) alongside traditional metrics like coverage and set size.
  2. PrefixCP (Prefix Conformal Prediction): A simple but effective fix. Instead of scoring every class against the current full registry, PrefixCP ensures that each class is scored against the registry that existed when that class was first "onboarded" (added to the system).

To make this efficient, the authors leverage the fact that registries typically grow by appending. This means every historical registry is just a prefix of the current one. They use a "prefix scan" algorithm to compute all historical normalizers in a single pass, ensuring that the computational cost remains nearly as low as standard methods.

Figure 1. Recalibrating can revoke old decisions. For this Food-101/SigLIP image, HPS-Refresh rescores and refits the old classes after 51 labels are added, and drops both previously included labels, including the true class. PrefixCP lets each class keep the registry it was added with, so both old decisions survive. Both methods also include the new label, shown dashed. It is the first evaluation image, in identifier order, whose sets are small enough to show and whose true old label HPS-Refresh drops (supplement Sec. M); it was scored blurred, as in all Food-101 settings, and is shown clean for legibility.

Datasets

The researchers evaluated their approach across eleven different settings using:

  • Food-101: For fine-grained food classification.
  • Stanford Cars: For vehicle type identification.
  • CUB-200-2011: The classic "birds" dataset.
  • ImageNet-R & ImageNet-Sketch: To test robustness against distribution shifts.
  • GeoDE: A geographically diverse dataset used to test how well the findings transfer to new domains.
  • Encoders: They used both CLIP and SigLIP (ViT-B/16) architectures.

Key Insights and Ideas

  • Coverage is a "leaky" metric for stability: High coverage does not imply a stable system. Churn is a "silent" failure mode that can break downstream logic (like manual review triggers).
  • Recalibration isn't a silver bullet: Even if you "refit" your conformal thresholds after adding labels (a method called HPS-Refresh), you still experience massive churn (53–90% of images affected).
  • The Stability-Efficiency Trade-off: There is no free lunch. By forcing old decisions to stay fixed, PrefixCP results in slightly larger prediction sets than a fully recalibrated system. However, it is significantly more efficient than never updating the reference registry at all.
  • Release History Matters: Because PrefixCP ties a class's score to its "birth" registry, the order and grouping of how you release new labels will affect the final set sizes.

Key Results

  • Zero Churn: By design, PrefixCP achieves 0% churn on old labels. Once a decision is made for an image/label pair, it never changes as the registry grows.
  • Closing the Gap: PrefixCP recovers 40.9–58.5% of the set-size gap between a "frozen" baseline (never updating) and a "refresh" baseline (recalibrating everything).
  • Minimal Overhead: The prefix scan computation adds only a small overhead—roughly 4.7% to 18.3% increase in the time spent on similarities and normalization for realistic batch sizes.
  • Audit Findings: In controlled tests, while old-class coverage moved by less than 0.01, between 60% and 67% of images saw their prediction sets change under standard methods.

Limitations and Future Work

  • Append-Only Constraint: PrefixCP assumes the registry only grows. Deleting labels or changing existing prompts would break the mathematical guarantees of Theorem 2 (decision equality).
  • Onboarding Requirement: Every new class requires a small set of labeled examples for calibration; it is not a "zero-shot" conformal method in the strictest sense.
  • Model/Prompt Updates: If the underlying VLM or the prompt templates are updated, the entire system must be recalibrated, losing the stability benefits for that transition.
  • Future Directions: The authors suggest exploring "periodic refresh" policies that might offer a better middle ground between absolute stability and minimal set size.

For more details, you can find the full paper at arXiv:2611.07502v1.

Summary updated

Abstract

Vision-language classifiers can learn new labels from text alone, so the label lists they serve keep growing. We show that this growth silently changes conformal decisions about old labels. Common softmax-based conformal scores compare each label with an average over all labels; adding labels changes that average, and with it the score of every old label, even when the model, the image, and the old calibration data stay the same. Recalibrating after the update keeps the coverage guarantee, yet across eleven settings it changes at least one old decision on 53-90% of new images. Coverage cannot reveal this, because it checks only the true label: in five controlled settings that keep the old calibration, so that only the normalizer changes, old-class coverage moves by at most 0.01 while 60-67% of images change. We propose a lifecycle audit that measures these changes alongside coverage and set size, and a simple fix, PrefixCP: each class keeps the label registry that existed when it was added. Its old decisions then never change, each class keeps exact class-conditional coverage under exchangeability, and one prefix scan computes all historical normalizers at once. PrefixCP recovers 40.9-58.5% of the set-size gap between never updating the reference and recalibrating, which gives smaller sets but changes old decisions.
BibTeX
@misc{sharma2026coverage,
  author = {Jai Kumar Sharma and Peeyush Tapadiya},
  title = {{Coverage Hides Churn: Auditing and Preserving Conformal Decisions as VLM Label Registries Grow}},
  year = {2026},
  eprint = {2611.07502},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07502},
}
Figure