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.
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:
- A Lifecycle Audit: A new evaluation protocol that measures churn (how many old decisions change) alongside traditional metrics like coverage and set size.
- 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.
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