🤖 machine learning

Benchmarking non-conformity score functions in conformal prediction

This paper provides an overview and introduces modifications to non-conformity score functions in conformal prediction, proposing a novel evaluation method to benchmark their effectiveness in generating prediction sets, particularly under class-imbalanced conditions.

Original authors: Sol Erika Boman

Published 2026-05-26

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Sol Erika Boman

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: From "Guessing One Thing" to "Making a Safe List"

Imagine you are playing a game of "Guess the Animal." A standard machine learning model is like a confident friend who points at a picture and says, "That's definitely a Cat." Sometimes they are right, but sometimes they are wrong, and they never admit uncertainty.

Conformal Prediction is a different approach. Instead of guessing just one animal, the model gives you a list of possibilities. It might say, "This is likely a Cat, but it could also be a Dog or a Fox."

The magic of this method is that it guarantees a safety net. If you tell the model, "I want to be 95% sure my answer is in the list," the model will adjust its list size to ensure that, over time, the real animal is inside that list 95% of the time.

The Problem: How Big Should the List Be?

The paper asks a crucial question: How do we decide what goes on that list?

If the list is too small (e.g., just "Cat"), you might miss the real answer. If the list is too big (e.g., "Cat, Dog, Fox, Hamster, Goldfish"), you are safe, but the list is useless because it includes everything.

The tool the model uses to decide what to put on the list is called a Non-conformity Score. Think of this score as a "Weirdness Meter."

Low Score: The data point looks very normal for that class (e.g., a fluffy picture looks very much like a Cat).
High Score: The data point looks strange or "non-conforming" for that class (e.g., a picture of a rock looks very weird if you are trying to call it a Cat).

The paper's goal was to test different types of "Weirdness Meters" to see which one creates the most useful lists (lists that are small but still safe).

The "Weirdness Meters" Tested

The authors tested several ways to measure "weirdness" across different types of data (like images of animals). Here are the main ones they compared, using analogies:

Label Distance (The "Target Practice" Meter):
- How it works: It measures how far the model's guess is from the "perfect" answer. Imagine throwing a dart at a bullseye. If the dart is close to the bullseye, the score is low (not weird). If it's far away, the score is high.
- The Paper's Finding: This worked very well, especially when using a specific way of measuring distance called "Cosine Distance" (which looks at the direction of the guess rather than just the raw distance).
Margin Distance (The "Border Patrol" Meter):
- How it works: Instead of measuring distance to the perfect answer, it measures how close the guess is to the border between two answers. If you are standing right on the line between "Cat" and "Dog," you are very confused (high weirdness). If you are deep in the "Cat" territory, you are confident (low weirdness).
- The Paper's Finding: This was a superstar performer, often creating the smallest, most efficient lists, especially when looking at the raw numbers before they are turned into percentages.
Mean Distance (The "Group Hug" Meter):
- How it works: It compares a new picture to the "average" of all the pictures it has seen before for that class. If a new cat picture looks like the average cat, it's a good fit. If it looks like a dog, it's weird.
- The Paper's Finding: This was the best method for complex datasets with many categories (like CIFAR100).
APS/RAPS/SAPS (The "Ranking" Meters):
- How it works: These are more complex methods that look at the ranking of the answers. They say, "Let's add the top guess, then the second guess, then the third..." until we feel safe enough to stop. They add some math tricks (regularization) to keep the lists from getting too big.
- The Paper's Finding: These were good, but often created slightly larger lists than the "Distance" meters. Interestingly, the paper found that the random "noise" usually added to these methods to make them fair wasn't actually necessary for the safety guarantee; a simple fixed number worked just as well.
Gradient/Feature Distance (The "Deep Dive" Meters):
- How it works: These try to measure weirdness deep inside the computer's brain (the feature layers) rather than just at the final output.
- The Paper's Finding: These were computationally heavy (slow) and didn't always perform better than the simpler methods.

The "Unfair" Test: Imbalanced Classes

The authors also tested what happens when the data is unfair. Imagine a dataset where 90% of the pictures are Cats, and only 1% are Tigers.

The Challenge: The model is great at spotting Cats but terrible at spotting Tigers.
The Result: When the model is forced to be 95% sure, it often includes the "Tiger" in the list for almost every single picture, even if the picture is clearly a Cat.
Why? The model is so unsure about Tigers that it plays it safe. It's like a security guard who is so afraid of missing a tiger that they stop everyone entering the building. The paper notes that while this makes the prediction "honest" (it admits it doesn't know), it makes the list huge and less useful for the common items.

The Main Takeaways

No Single Winner: There isn't one "best" Weirdness Meter for every situation.
- For simple tasks, Label Distance or Margin Distance worked best.
- For complex tasks with many categories, Mean Distance was the champion.
Direction Matters: Using Cosine Distance (measuring the angle/direction of the data) was often better than standard distance, especially in high-dimensional spaces (like deep learning models).
Simplicity Wins: The most complex methods (like the deep feature gradients) didn't necessarily give better results and were much slower.
Architecture Matters: The type of computer model used (e.g., ResNet vs. EfficientNet) changed which "Weirdness Meter" worked best, suggesting that the choice of meter depends on the specific model you are using.

In short, the paper provides a "menu" of tools for building safer AI lists. It shows that by picking the right "Weirdness Meter" for your specific problem, you can keep your prediction lists small and useful without sacrificing safety.

Technical Summary: Benchmarking Non-Conformity Score Functions in Conformal Prediction

Problem Statement

Conformal prediction (CP) offers a rigorous alternative to model calibration in machine learning classification by generating prediction sets rather than single-class predictions. While CP guarantees that the true class is contained within the prediction set with a probability at least equal to $1 - \alpha$ (where $\alpha$ is a pre-specified error rate), the practical utility of these sets depends heavily on their size. A prediction set that is too large is uninformative.

The size and usefulness of these sets are determined by the choice of the non-conformity score function. Despite the existence of numerous score functions in the literature, there is a lack of systematic studies examining their properties, effectiveness, and interaction with model architectures and class imbalance. This paper addresses the gap in understanding how different score functions perform across various conformal domains (probability space, logit space, and feature space) and under different conditions, including imbalanced datasets.

Methodology

Evaluation Metric

The authors introduce a novel evaluation metric, $I_1$ , to assess score functions independent of an arbitrary choice of error rate $\alpha$ . Traditional metrics report mean prediction set size at a fixed $\alpha$ , which can be misleading if $\alpha$ is not aligned with model accuracy.
The metric is defined as:
$I_k = \frac{1}{1 - A_k} \int_{0}^{1 - A_k} \bar{|P|}(\alpha) \, d\alpha$
where $A_k$ is the top- $k$ model accuracy (specifically $A_1$ for top-1 accuracy), and $\bar{|P|}(\alpha)$ is the mean prediction set size at error rate $\alpha$ . This integral constrains the evaluation to the "interesting" range of error rates (from 0 to the model's inherent error rate), providing a single, objective number where lower values indicate better performance (smaller prediction sets).

Experimental Setup

Datasets: ImageNet (1000 classes), CIFAR-100 (100 classes), and CIFAR-10 (10 classes).
Models: ResNet50 (primary), ResNet18, and EfficientNet-B0.
Conformal Domains: The study evaluates score functions across three distinct spaces:
1. Probability Space: The output of the softmax function ( $\Delta_{n-1}$ ).
2. Logit Space: The raw output vectors prior to softmax ( $\mathbb{R}^n$ ).
3. Feature Space: The final feature vectors before the linear output layer.
Score Functions Benchmarked:
- Label Distance: Distance between the prediction and the one-hot encoded label.
- Margin Distance: Distance to the decision boundary between the true class and the most probable incorrect class.
- Mean Distance: Distance to the mean of calibration examples belonging to the same class.
- Nearest Neighbor: Ratio of distances to nearest same-class vs. different-class examples.
- APS/RAPS/SAPS: Adaptive Prediction Sets and their regularized variants (Rank-based methods).
- Gradient/Fast Gradient: Feature-based methods approximating the distance to the decision boundary in feature space.
Imbalance Testing: A class-conditional setting was tested where minority classes were reduced to 10% prevalence to evaluate how well different score functions handle class imbalance.

Key Results

Performance of Score Functions

The benchmarking results, summarized by the $I_1$ metric, reveal distinct performance patterns:

Distance-Based vs. Rank-Based: Distance-based score functions generally outperformed rank-based methods (APS, RAPS, SAPS) in terms of prediction set size, particularly when using cosine distance.
Optimal Domains and Metrics:
- Margin Distance in Logit Space using Cosine Distance achieved the lowest $I_1$ values for ImageNet across ResNet models.
- Mean Distance performed exceptionally well on CIFAR-100, particularly in Feature Space with Cosine Distance.
- Label Distance in Probability Space with Cosine Distance was also highly competitive.
Euclidean vs. Cosine: Euclidean distance was found to be less suitable for high-dimensional spaces (like feature vectors in ResNet50), whereas cosine distance performed robustly, suggesting that these models organize classes into approximately orthogonal clusters.
Randomization in APS/RAPS: The study found that the randomized term ( $u$ ) in APS and RAPS is not strictly necessary for coverage guarantees in calibrated settings. Setting $u$ to a small constant (serving as a tie-breaker) often yielded better performance than the standard randomized approach.
Gradient Methods: The Gradient and Fast Gradient methods were computationally expensive and, in the case of Fast Gradient, performed significantly worse than other methods on the tested datasets.

Impact of Model Architecture

While ResNet50 and ResNet18 showed similar relative ordering of score function performance, EfficientNet-B0 exhibited a different ranking. This suggests that model architecture (e.g., activation functions like ReLU vs. Swish) influences the geometric properties of the conformal domain and thus the optimal choice of score function, potentially more than the model's raw accuracy.

Class Imbalance

In the imbalanced setting, minority classes were often included in prediction sets at frequencies much higher than their true prevalence (e.g., 27% inclusion for a 0.1% true prevalence class). The authors note that while this reduces the precision of the predictor, it is an "honest" reflection of the underlying model's uncertainty regarding rare classes. Mean Distance in feature space again showed the best ability to minimize this over-inclusion while maintaining coverage.

Significance and Claims

The paper claims to fill a knowledge gap regarding the properties and effectiveness of non-conformity score functions. Its primary contributions are:

Systematic Benchmarking: Providing a comprehensive comparison of diverse score functions across multiple datasets, models, and conformal domains.
Evaluation Metric: Introducing $I_1$ as a robust, single-number metric that accounts for model accuracy and avoids arbitrary error rate selection.
Domain and Metric Insights: Demonstrating that cosine distance is superior to Euclidean distance in high-dimensional conformal domains and that logit space often outperforms the probability simplex.
Practical Guidance: Offering a starting point for practitioners to select score functions based on their specific model architecture and dataset characteristics, rather than relying on a single "best" universal method.

The authors conclude that no single score function is universally superior; rather, the optimal choice depends on the specific context of the model and data. However, the benchmark provides a clear, data-driven foundation for making these selections.