📊 statistics

ST-BCP: Tightening Coverage Bound for Backward Conformal Prediction via Non-Conformity Score Transformation

This paper introduces ST-BCP, a novel method that employs a data-dependent transformation of non-conformity scores to significantly tighten the coverage bound in Backward Conformal Prediction, thereby reducing the gap between estimated and empirical coverage from 4.20% to 1.12%.

Original authors: Junxian Liu, Hao Zeng, Hongxin Wei

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Junxian Liu, Hao Zeng, Hongxin Wei

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

The Big Picture: The "Guessing Game" Problem

Imagine you are playing a game where a computer tries to guess what object is in a photo.

Standard AI: Usually, the computer says, "I'm 90% sure this is a dog." But in high-stakes situations (like medical diagnosis or self-driving cars), being "pretty sure" isn't enough. You need to know exactly how sure it is.
Conformal Prediction (CP): This is a safety net. Instead of saying "It's a dog," the computer gives you a list of possibilities (e.g., "It's either a dog, a cat, or a wolf"). It guarantees that the correct answer is in that list 90% of the time.
- The Problem: To be safe, the list often gets too long. If the list says "It could be any animal," it's not very helpful.
Backward Conformal Prediction (BCP): This flips the script. Instead of asking, "How big is the list to be 90% safe?", it asks, "I want the list to be small (e.g., only 2 options). How safe is that?"
- The Problem: The math used to calculate "how safe" is very conservative. It's like a safety inspector who assumes the worst-case scenario so aggressively that they tell you, "This bridge is only 40% safe," even though it's actually 90% safe. This gap between the estimated safety and the real safety is called the Coverage Gap.

The Solution: ST-BCP (The "Score Reshaper")

The authors of this paper created a new method called ST-BCP to fix this gap. They realized the "safety inspector" (the math) was using a blunt tool (Markov's inequality) that didn't fit the shape of the data.

Here is how they fixed it, using three analogies:

1. The "Loose Net" vs. The "Tailored Net"

Imagine the computer assigns a "suspicion score" to every possible answer. High scores mean "very unlikely," low scores mean "very likely."

Old Way (BCP): The computer uses these raw scores to build a safety net. But the scores are scattered all over the place. The safety math (Markov's inequality) has to assume the net is huge to catch everything, leading to that overly pessimistic "40% safe" estimate.
New Way (ST-BCP): Before building the net, ST-BCP reshapes the scores. It takes the scattered scores and squashes them into a specific shape that fits the safety math perfectly.
- Analogy: Imagine you are trying to fit a pile of irregular rocks into a box.
  - Old Way: You just throw the rocks in. The box looks huge and messy.
  - New Way: You chip the rocks into uniform cubes first. Now they fit tightly into a much smaller, more efficient box. The "safety estimate" (how full the box is) becomes much more accurate.

2. The "Two-Point" Trick

The paper mentions a cool mathematical insight: The safety math works best when the data looks like a two-point distribution (like a light switch that is either fully ON or fully OFF).

The original scores are like a dimmer switch with hundreds of settings. The safety math struggles to calculate the risk with so many settings.
ST-BCP transforms the scores so they act like a light switch: either the score is "low" (safe) or "high" (unsafe), with very little in between. By forcing the data into this simple "On/Off" structure, the safety math can give a much tighter, more accurate guarantee.

3. The "Symmetric Mirror"

You might wonder: "If you change the scores based on the data, doesn't that break the rules of the game?"

The paper uses a clever trick called Symmetric Parameterization. Imagine you are judging a contest. To make sure the judging is fair, you don't just look at the current contestant; you pretend every past contestant was the current one, one by one.
ST-BCP does this mathematically. It ensures that no matter which "fake" test point you use, the rules stay the same. This keeps the statistical guarantees valid while still allowing the scores to be reshaped for better accuracy.

What Did They Achieve?

The authors tested this on famous image datasets (like CIFAR-10 and Tiny-ImageNet) using various AI models.

The Result: They drastically reduced the "Coverage Gap."
- Before: The estimated safety was often 4.20% lower than the actual safety. (The computer thought it was less safe than it really was).
- After: The gap shrank to just 1.12%.
The Impact: In real-world terms, this means the system stops being overly paranoid.
- Example from the paper: Imagine a medical AI that automatically handles routine cases if it's "safe enough." With the old method, the AI might think a routine case is risky (because of the loose math) and send it to a human doctor for a second look. With ST-BCP, the AI correctly identifies the case as safe, saving the doctor time and reducing unnecessary human intervention.

Summary

ST-BCP is a method that takes the "safety scores" of an AI, reshapes them to fit the mathematical rules better, and creates a much tighter, more accurate estimate of how safe the AI's predictions are. It stops the system from being unnecessarily conservative, allowing it to work more efficiently without losing its safety guarantees.

Technical Summary: ST-BCP

Problem Statement

Conformal Prediction (CP) offers a distribution-free framework for uncertainty quantification, constructing prediction sets with guaranteed coverage. However, standard CP often yields excessively large prediction sets, limiting its practical utility. Backward Conformal Prediction (BCP) addresses this by inverting the paradigm: it pre-defines an upper bound on the prediction set size and estimates the resulting coverage guarantee.

Despite this innovation, BCP suffers from a significant "coverage gap"—a discrepancy between the estimated coverage bound and the empirical coverage. This looseness arises because BCP relies on Markov's inequality applied to e-variables to derive coverage guarantees. Markov's inequality utilizes only the first-order moment (expectation) of the miscoverage level, making the bound insensitive to the specific shape or tail behavior of the non-conformity score distribution. Consequently, the theoretical bound is often overly conservative, leading to unnecessary manual interventions in high-stakes applications (e.g., medical diagnosis) even when the system is reliable.

Methodology: ST-BCP

The authors propose ST-BCP (Score Transformation for Backward Conformal Prediction), a method that introduces a data-dependent transformation of non-conformity scores to tighten the coverage bound.

1. Core Mechanism

The central idea is to reshape the distribution of non-conformity scores to better align with the assumptions of Markov's inequality, thereby reducing the looseness of the bound. The method employs a transformation function $h(s; D, X)$ , where $s$ is the score, and $D$ and $X$ represent the dataset and feature information, respectively.

2. Preserving Validity (Exchangeability)

A critical challenge in data-dependent transformations is maintaining exchangeability, the mathematical foundation of CP validity. ST-BCP resolves this via a symmetric parameterization strategy:

For a candidate label $y$ , the transformation parameters are constructed by combining the leave-one-out calibration set with a pseudo-test point $(X_{n+1}, y)$ .
This ensures that the sequence of transformed scores remains mathematically symmetric, strictly preserving exchangeability even when the transformation depends on the data.

3. Theoretical Optimization

The authors frame the reduction of the coverage gap as a functional optimization problem.

Optimal Transformation: Under a monotonicity constraint, the theoretically optimal transformation is derived. It takes the form of a step function: $h_{opt}(s) \propto I(s \ge w(D, X))$ , where $w(D, X)$ is a threshold derived from the size constraint.
Computable Approximation ( $I_w$ ): Since the optimal solution requires unknown conditional distributions, the authors derive a computable approximation called $I_w$ . This transformation sets the score to zero if it is below the threshold $w(D, X)$ and to a constant value otherwise.
Improvement Operator: The paper defines an improvement operator $G$ such that applying $G$ to the baseline identity transformation yields $I_w$ . Theoretically, $I_w$ is guaranteed to outperform the baseline identity transformation.

4. Estimation Consistency

The paper establishes that the Leave-One-Out (LOO) estimator remains a consistent estimator for the coverage bound under the proposed transformation. Despite the complex statistical dependencies introduced by the data-dependent transformation, the estimator maintains a convergence rate of $O_P(1/\sqrt{n})$ , comparable to the original BCP framework.

Key Contributions

Theoretical Formalization: The authors formalize the conditions under which data-dependent transformations preserve score exchangeability and establish criteria for the LOO estimator to remain consistent.
Optimal Transformation Derivation: They analytically derive the optimal transformation under monotonicity constraints and provide a computable approximation ( $I_w$ ) that does not require inaccessible distributional information.
Empirical Validation: Extensive experiments demonstrate that ST-BCP significantly narrows the coverage gap while maintaining estimation precision and stability comparable to the baseline.

Experimental Results

Experiments were conducted on CIFAR-10, CIFAR-100, and Tiny-ImageNet using various architectures (ResNet, DenseNet, EfficientNet, MobileNet) and different size constraint rules (constant, feature-dependent, and feature/calibration-set-dependent).

Coverage Gap Reduction: ST-BCP drastically reduces the gap between the LOO estimator and empirical coverage.
- On CIFAR-10 with a constant size constraint ( $T=2$ ), the gap reduced from 5.38% (baseline) to 0.72%.
- Across all benchmarks and constraint rules, the average coverage gap decreased from 4.20% to 1.12%.
Stability and Efficiency: The method achieves lower Mean Squared Error (MSE) and standard deviation (STD) for the LOO estimator compared to the baseline, indicating improved estimation stability.
Prediction Set Invariance: Theoretical results (Theorem 3.2) and empirical observations confirm that the prediction sets remain invariant under the proposed transformation when the size constraint depends only on features, not the full calibration set.

Significance and Claims

The paper claims that ST-BCP offers a practical solution for uncertainty quantification in scenarios requiring controlled prediction set sizes. By tightening the coverage bound, the method reduces the inherent conservatism of BCP.

The authors highlight a specific practical implication: in safety-critical domains like medical diagnosis, overly conservative bounds often trigger unnecessary human reviews for cases that are actually safe. ST-BCP allows the estimated coverage lower bound to more accurately reflect the system's true reliability, thereby reducing unwarranted human intervention without compromising statistical validity.

The work is presented as a refinement of the BCP framework, improving the efficiency of the coverage estimation process while strictly adhering to the theoretical guarantees of conformal prediction. The authors note limitations regarding the complexity of theoretical assumptions when size constraints depend on both features and the calibration set, and they suggest future work could focus on relaxing these assumptions or optimizing estimation efficiency further.