📊 statistics

Conformal Prediction Sets for Instance Segmentation

This paper introduces a conformal prediction algorithm that generates adaptive confidence sets for instance segmentation, providing provable guarantees that at least one prediction within the set achieves high Intersection-Over-Union with the ground truth while effectively capturing structural uncertainty across diverse applications.

Original authors: Kerri Lu, Dan M. Kluger, Stephen Bates, Sherrie Wang

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kerri Lu, Dan M. Kluger, Stephen Bates, Sherrie Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are looking at a complex map of a city, and you point to a specific spot on the screen. You ask a computer, "What is this?"

In the world of Instance Segmentation (a fancy term for finding and outlining individual objects in a picture), current AI models are like overconfident tour guides. They will point to a spot and say, "That is definitely a park," drawing a single, sharp line around it. They might be right most of the time, but they never admit, "Actually, this area looks a bit blurry; it could be a park, or maybe a golf course, or perhaps two small parks merged together." They give you one answer with high confidence, even when they are unsure.

This paper introduces a new way to ask the computer: "Give me a list of possibilities, and promise me that one of them is correct."

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "One-and-Done" Guide

Current AI models try to pick the single "best" answer. But in real life, things are often ambiguous.

The Issue: If you ask an AI to outline a farm field in a satellite image, it might draw a line that cuts the field in half (thinking it's two fields) or merges two fields into one.
The Flaw: The model doesn't know it's confused. It just gives you one mask (a digital outline) and says, "Here is the truth." If it's wrong, you have no warning.

2. The Solution: The "Safety Net" of Options

The authors created a method called Conformal Prediction. Instead of asking the AI for one answer, they ask it to generate a Confidence Set—a small basket of different possible outlines for that same spot.

Think of it like a weather forecast.

Old Way: "It will rain at 2 PM." (If it doesn't, the forecast was wrong).
New Way: "There is a 90% chance that the rain will happen between 1 PM and 3 PM." (Even if you don't know the exact minute, you have a guaranteed window where the truth lies).

In this paper, the "window" is a set of different shapes. The algorithm promises: "I will give you a list of 3 or 4 different outlines. I guarantee that at least one of these outlines matches the real object with high accuracy."

3. How It Works: The "Tuning Knob" Strategy

The secret sauce is how they generate these different options. They use a "tunable parameter" (like a volume knob or a slider) on the AI model.

The Analogy: Imagine a radio with a slightly fuzzy signal. If you turn the dial slightly left, you hear the music clearly but with some static. If you turn it slightly right, the static is gone, but the music is muffled. No single setting is perfect for every song.
The Method: The researchers take a calibration dataset (a practice set of images with known answers). They test the AI with many different "dial settings."
- Setting A works great for Field 1 but fails on Field 2.
- Setting B fails on Field 1 but works perfectly on Field 2.
The Magic: The algorithm looks at all these settings and picks a minimal group of them that, when used together, cover almost every possible scenario in the practice set.

When a new, unknown image comes in, the AI doesn't just pick the "best" setting. It runs the image through that specific group of settings and gives you the resulting list of masks.

4. The "Duplicate" Filter

Sometimes, different settings produce almost identical outlines. To keep the list useful and not overwhelming, the system has a "duplicate remover."

The Analogy: If you ask for a list of restaurants and get "The Pizza Place," "The Pizza Place (Downtown)," and "The Pizza Place (Main St)," and they are all the same place, you just want one entry.
The system removes near-duplicates, so if the AI is very sure, you might only get 1 or 2 options. If the image is very confusing (ambiguous), the list grows to include more distinct possibilities.

5. Real-World Tests

The authors tested this on three very different tasks:

Farm Fields: Distinguishing between adjacent fields in satellite images (often very hard to tell where one ends and another begins).
Cells: Outlining individual cells in a microscope image (where cells often overlap).
Vehicles: Identifying cars in street scenes.

The Results:

Coverage: Their method successfully hit their target guarantee (e.g., "90% of the time, one of our masks is correct") much better than the standard "best guess" method.
Adaptability: When the image was clear, the list was short (efficient). When the image was messy and confusing, the list got longer (safe), ensuring the user wasn't left with a wrong answer.
Structure: Unlike older methods that just "fuzzed" the edges of a single shape, this method provided structurally different shapes (e.g., one shape saying "it's one big field," another saying "it's two small fields").

Summary

This paper doesn't just make the AI smarter; it makes the AI honest. It admits that sometimes there isn't one single right answer. Instead of forcing a single, potentially wrong outline, it provides a curated list of possibilities and guarantees that the truth is hiding somewhere in that list. It turns a "guess" into a "safety net."

Technical Summary: Conformal Prediction Sets for Instance Segmentation

Problem Statement
Current instance segmentation models achieve high average performance but lack principled uncertainty quantification. Their outputs, such as logits or confidence scores, are often uncalibrated, offering no guarantee that a predicted mask is close to the ground truth. Existing uncertainty metrics (e.g., boundary probabilities) are frequently uncalibrated and difficult to interpret. Furthermore, recent conformal prediction approaches for segmentation are constrained to modifying a single model-predicted mask (e.g., via dilation or boundary expansion). These methods capture local boundary uncertainty but fail to address structural uncertainty—the ambiguity regarding whether adjacent regions should be treated as a single object or split into multiple objects. This limitation is critical in real-world applications where a single "best" parameter setting may not exist for all queries.

Methodology
The authors propose a conformal prediction algorithm that generates adaptive confidence sets of instance predictions for a given image and pixel coordinate query. The method operates under the following framework:

Setting: The input consists of an image $I$ and a query point $(z_1, z_2)$ . The goal is to predict a binary mask $Y$ for the object instance containing the query. The method utilizes an instance segmentation model $f$ that accepts a tunable parameter $T$ (e.g., watershed thresholds, logit thresholds, or mask indices) to produce diverse predictions $\hat{Y} = f(X, T)$ .
Calibration: Using a calibration dataset of $n$ image-query pairs with ground truth masks, the algorithm evaluates the Intersection-over-Union (IoU) of predictions generated by a grid of $k$ parameter values $\{t_1, \dots, t_k\}$ .
Set Construction (Set Cover): For a target IoU threshold $\tau$ and error rate $\alpha$ , the algorithm identifies a minimal subset of parameter indices $J_{\alpha, \tau}$ such that the union of successful predictions (those with IoU $> \tau$ ) covers at least $(1-\alpha)n$ calibration examples. This step is formulated as a Set Cover problem, solved via a greedy algorithm followed by brute-force refinement to minimize the set size.
Prediction: For a new test input, the algorithm generates predictions using the selected parameter subset $J_{\alpha, \tau}$ , forming the initial confidence set $C_{\alpha, \tau}(X_{test})$ .
Adaptive Refinement (Duplicate Removal): To avoid redundancy, the algorithm removes near-duplicate masks (defined by a secondary IoU threshold $\eta$ ) using a Dominating Set approach. This results in an adaptive set size that varies based on query difficulty.
Guarantees: The method provides asymptotic guarantees that, with probability $\ge 1-\alpha$ , the final confidence set contains at least one mask with IoU greater than a recalibrated threshold $\tilde{\theta}$ . A finite-sample version is also provided using sample splitting and Conformal Risk Control (CRC).

Key Contributions

Novel Formulation: The paper introduces the first conformal prediction formulation for instance segmentation that captures structural uncertainty. Unlike prior methods that perturb a single mask, this approach constructs set-valued predictions over multiple model configurations.
Feasibility in Non-Monotone Settings: The method does not require a monotone loss function (a requirement for standard Conformal Risk Control and Learn Then Test frameworks). This allows the use of IoU-based loss functions, which are inherently non-monotone with respect to segmentation parameters.
Adaptive Confidence Sets: The algorithm produces prediction sets that vary in size based on the difficulty of the query, removing duplicates to provide a more informative representation of uncertainty without overwhelming the user.
Theoretical Guarantees: The work provides both asymptotic and finite-sample theoretical guarantees for coverage, ensuring that at least one prediction in the set achieves high IoU with the ground truth.

Experimental Results
The algorithm was evaluated on three distinct tasks: agricultural field delineation, cell segmentation, and vehicle detection.

Coverage: The method achieved empirical coverage close to the target $(1-\alpha)$ , significantly outperforming baselines. For example, in vehicle detection, coverage improved from 66.1% (naive best parameter baseline) to 84.3%.
Baseline Comparison: The "naive best parameter" baseline (selecting a single global parameter) and the "morphological dilation" baseline (expanding a single mask) failed to capture structural ambiguity. The proposed method successfully recovered cases where the baseline either over-segmented or under-segmented objects.
Adaptivity: The size of the prediction sets adapted to query difficulty. In ambiguous scenarios (e.g., field boundaries), sets expanded to include multiple plausible masks (up to 5), while in clear cases (e.g., distinct cells), sets collapsed to size one or two.
Thresholds: The recalibrated IoU threshold $\tilde{\theta}$ remained close to or greater than the original target $\tau$ , indicating that duplicate removal did not significantly degrade the coverage guarantee.

Significance and Claims
The authors claim this work is the first to capture structural uncertainty in instance segmentation by constructing confidence sets of diverse segmentation predictions. The significance lies in shifting the paradigm from providing a single "best" prediction (which may be structurally incorrect) to providing a provable set of diverse hypotheses. This approach acknowledges that in ambiguous imagery (e.g., low-contrast fields, overlapping cells), a single mask is often insufficient. The method formalizes the reliability of segmentation models by explicitly quantifying the probability that the true object is represented within the set.

The paper modestly notes that conformal prediction cannot overcome the inherent limitations of the underlying segmentation model; if the base model cannot achieve a certain IoU, the confidence set cannot guarantee it. Furthermore, the method relies on the existence of a tunable parameter that induces meaningful diversity. The authors identify future work in developing training strategies that explicitly incentivize mask diversity and in creating scalable approximations for the combinatorial optimization steps (set cover and duplicate removal) to handle larger parameter spaces.