Fair Conformal Classification via Learning Representation-Based Groups
Authors: Senrong Xu
Yanke Zhou
Yuhao Tan
Zenan Li
Yuan Yao
Taolue Chen
Feng Xu
Xiaoxing Ma
Venue: ICLR 2026 Poster (2026)
Keywords: Classification; Conformal Prediction; Equalized Coverage; Fairness
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Conformal prediction methods provide statistically rigorous marginal coverage guarantees for machine learning models, but such guarantees fail to account for algorithmic biases, thereby undermining fairness and trust. This paper introduces a fair conformal inference framework for classification tasks. The proposed method constructs prediction sets that guarantee conditional coverage on adaptively identified subgroups, which can be implicitly defined through nonlinear feature combinations. By balancing effectiveness and efficiency in producing compact, informative prediction sets and ensuring adaptive equalized coverage across unfairly treated subgroups, our approach paves a practical pathway toward trustworthy machine learning. Extensive experiments on both synthetic and real-world datasets demonstrate the effectiveness of the framework.

Published as a conference paper at ICLR 2026
FAIR CONFORMAL CLASSIFICATION VIA LEARNING REPRESENTATION-BASED GROUPS
Senrong Xu', Yanke Zhou', Yuhao Tan', Zenan Li?, Yuan Yao', Taolue Chen Feng Xu', Xiaoxing Ma
1 State Key Lab of Novel Software Technology, Nanjing University, China, 2 ETH Zürich, Birkbeck, University of London
s rxxu, yankezhou, y @ jj edu en, zenan. www.:liiinfehhhee y yao, xf, xxm) @n ju. edu. cn, t. ccen@bbk..cc .ukku
ABSTRACT
Conformal prediction methods provide statistically rigorous marginal coverage guarantees for machine learning models, but such guarantees fail to account for al- gorithmic biases, thereby undermining fairness and trust. This paper introduces a fair conformal inference framework for classification tasks. The proposed method constructs prediction sets that guarantee conditional coverage on adaptively iden- tified subgroups, which be implicitly defined through nonlinear feature binations. By balancing effectiveness and efficiency in producing compact, infor- mative prediction sets and ensuring adaptive equalized coverage across unfairly treated subgroups, our approach paves a practical pathway toward trustworthy ma- chine learning. Extensive experiments both synthetic and real-world datasets demonstrate the effectiveness of the framework.
INTRODUCTION
The rapid advancement of modern machine learning models, especially deep neural networks, has enabled their deployment in high-stake decision-makinn situations such medical diagnoses (Kaur al. 2020), resume filtering (Deshpande et al. 22200) and financial fraud detection (Kamuangu, 2024 Despite their strong average performance, real-world deployment raises critical challenges, notably in uncertainty quantification (Guo et al. 2017 Ahmed et al. 2023) and algorithmic fair-
ness (Berk et al. 2024 Almasoud & Idowu 2025)
Ensuring reliable decision-making necessitates the development of unbiased uncertainty mea- sures, even highly accurate models are prone to producing over-confident and erroneous pre- dictions (Ovadia et al. 2019). Conformal Prediction (CP, (Vovk et al.] 2005; Smith 2024)) has emerged as key framework for providing distribution-free, model-agnostic prediction sets with user-specified (marginal) coverage guarantees. These sets provide reliable uncertainty information for decision-maken especially when the set size is small (i.e.. with high efficiency).
On the other hand, algorithmic biases often manifest as disproportionately poor performance on the subgroup defined by specific feature conditions (e.g., Race=Black & Gender=Female), which may arise from imbalanced data distribution or model inherent limitations (Hellman) 2020). These biases underscore the need for algorithmic fairness mechanisms that extend beyond average performance to ensure equitable treatment across all groups (Fabris et al.) 2022 Das et al. (023). However, there may exist tensions between the efficiency of CP and algorithmic fairness, because the former desires
small prediction set, while the latter may necessitate larger sets for equal conditional coverage across all subgroups (Gibbs et al. 2025).
Conformal prediction with equalized coverage (Romano al. 2020a) provides pragmatic ap- proach to the sarciencyyfairmen trade-off. This approach ensures that the target coverage level (e.g., 90%) is satisfied not only marginally the entire population, but also conditionally on each protected group of interest. However, acquiring prediction sets with equalized coverage challeng- ing, the number of all plausible groups of interest is exponential in the number of features. A

---

Published as a conference paper at ICLR 2026
Gender
White Female
A
White Male
Race
A Hard Sample
O
Easy Sample
Black Female
Black Male
Figure 1: An illustrative example. The group space divided into four parts by the feature Race and Gender. Hard samples (red triangles) unfairly treated by the classifier, and easy samples (green circles) are normally treated. Note that a single feature (either Race or Gender) cannot discover the unfair subgroups (both have four triangles and four circles). Stronger expressiveness desirable to capture the unfair subgroup "White Female or Black Male".
straightforward enumeration is practically infeasible both statistically and computationally. espe- cially multi-dimensional (continuous) features. Indeed, Romano et al. (2020a) only takes each single feature as the condition of groups (c.g., group defined by Gender=Femall), which is an arguably insufficient representation of the entire space of groups.
Later, Zhou & Sesia (2024) observe that algorithmic biases often concentrate on a minority of sub- groups, and propose adaptively fair conformal prediction (AFCP) to identify these potentially disad- vantaged subgroups. In a nutshell, AFCP computes the conditional coverage score for each discrete feature and selects the top-k sensitive features with greedy strategy (where k is hyperparameter), However, this group identification method still has limited expressiveness. For example, it cannot capture groups defined by nonlinear combination of features, such as Exclusive OR (see the sub- group "White Female or Black Male" in Fig. D Additionally, AFCP is based on Naive Bayes, which incurs a high computational cost and restricts its applicability continuous features.
1.1 OUR CONTRIBUTIONS
In this paper, propose new group-fair conformal prediction method, fair conformal prediction for representation-based groups (FAREG), which accommodates both group expressiveness and time efficiency. Different from existing work (Romano et al., 2020a Zhou & Sesia 2024) which directly extracts groups from the raw input feature X, our approach encodes X into a latent rep- resentation Z via mapping Z f(X), and learns unfair groups characterized by the low group coverage based on Z. The introduction of Z as a high-level representation of features strengthens the expressiveness of models, allowing thorough exploration of groups. Mcanwhile, we can enhance the interpretability by reconstructing input X from the encoding Z. To this end, we carefully design an eecoder- architecture and the optimization objective, based on the principle of variational inference.
In addition, we propose nonlinear version of the conditional coverage metric WSC (Cauchois al., 2021], namely WSC", aiming evaluate the conditional coverage of unfairly treated groups more precisely. This allows users to check conformal procedure and compare multiple alternative conformal procedures.
The main contributions of this paper are summarized as follows. First, we propose a new confor- mal prediction method to enhance the expressiveness of unfair group identification. Second, we extend the traditional conditional coverage metric WSC to a nonlinear version WSC* for more ac- curate evaluation. Comprehensive experiments both synthetic and real-worle datasets confirm the effectiveness and efficiency of our proposed method.
PRELIMINARY
For any natural number n, we write [n] == [l....,n). We work with the most widely-used ver- sion of conformal prediction, i.e., split conformal prediction, where assume calibration set
2

---

Published as a conference paper at ICLR 2026
(XX, i.id. (or simply exchangeable) observations sampled from (unknown) dis- tribution Pxy. In standard classification, X; X' represents the input feature from a feature space X IRd and Y E [L] is a categorical label. A given classifier f is trained (on a training set) to predict the conditional distribution P(Y X)). Furthermore, X XN-1 is a YN-1 sampled by Pxy. CP constructs prediction set C(XN+1) ) for YN+1 based on D. The output C(XN+1) guarantees marginal coverage at user-specified level, i.e.
instance with an unknown label
P[YN+1 C(XN+1)] 21-a,
where a (0,1) a predefined miscoverage rate.
Typically, CP proceeds in three steps: (1) computing the predefined conformity score V( (i) for
each sample (Ii, M/) 'D using the predictive results of the classifier f; (2) setting (1-a) 1/N) quantile score DD as a threshold vi; (3) constructing the prediction set Cm (XN-1, {y [K]]V(X,,9) f which is used as C(XN-1) for XN-1-
can be shown that C' (XN+1, D) meets the desirable marginal coverage. Intuitively, marginal coverage implies that the prediction set is guaranteed to contain the true label with the average 1 probability over the population. However, this guarantee is deemed to be insufficient, especially when miscoverage exhibits systematic bias, disproportionately affecting individuals belonging to groups characterized by certain features.
By contrast, conditional coverage requires P[Yx-1 C((Nx1)) = xx] 2
for each x X.
This is much stronger as it demands correct coverage across all regions of the feature space, not just on average. However, achieving conditional coverage is impossible without imposing extra assumptions on the underlying distribution P'xy (such as the smoothness of Pxy (Cai et al. 2014
Lei & Wasserman 2014) and strictly limiting the size of feature space X' (Lee & Barber 202 p) As these strong assumptions are often violated, conditional coverage is less meaningful in practice.
Equalized coverage (Romano et al., 2020a) represents a pragmatic compromise to ensure validity across predefined sample groups that need to be protected. Given a group & s X, it is required that
P[YN+1 e C(XN-) XN+1 G] 2 a
for all G of interest. In particular, these groups are typically related to some specific features called sensitive features.
However, the requirement for rigorous equalized coverage is localized, as algorithmic biases dispro- portionately affect only minority subgroups (Zhou & Sesia 2024), as mentioned in Seciton [ Therefore, AFCP further proposes adaptive equalized coverage based on equalized coverage, for- malized by
P[YN-1 E E((XN=1) XN+11 E G 1-
(1)
where g is adaptively selected corresponding to sensitive features. Eq. indicates that C(X ((xN))) is well-calibrated for the selected group 9 defined by these sensitive features.
METHODOL.OGY
This section presents FAREG, a learning-based method that adaptively identifies groups affected by algorithmic bias and adjusts their prediction sets to achieve equalized coverage while preserving high informativeness.
3.1 LEARNING REPRESENTATION--E BASED GROUPS
Optimization Objective. For any feature x X, we write its encoding : = f(x) E Z, where Z is a latent representation space. Intuitively, z denotes the latent representations of feature combinations of xr We introduce a random binary variable S and Z taking values in 2 to formalize the member- ship of a group. Naturally, we consider conditional distribution P(S Z) such that the probability of x 9 for group 9 is equal to P(S = 1| Z= f()).. Our goal is twofold: (1) to learn encoding
-= fXX that is maximally informative about S and X, while (2) Z does not reveal the identity of any individual in the sample (e.g., the calibration set).
3

---

Published as a conference paper at ICLR 2026
We apply the deep variational information bottleneck (Deep VIB) method (Alemi al. 2017
Specifically, for two random variables and Y with the joint pdf (parameterized by 8), pe [z y) ((),Y:0) f (a(x, v) log po(z)ro(1) objective can be formalized as
pu((.y) dzdy denotes their mutual information. The optimization
max / S:0) + (Z2 (000))33((2ii0 (z,;);,
where is random variable to take any instance from the sample (c.g.. in this paper. the calibration D) with uniform distribution, 0 is the model parameter, and / is weight hyperparameter. (We abbreviate I(Z, S), ((2,
i) as I1 I2, I3 for convenience.)
By introducing 9o (s]2), go (z)2)) r(z) ) as the variational upproximation to pe (ol)))) in respective terms, we perform variational inference and obtain
1 + 12- fIz 2 f po p x))o log 9s dr ds dæ
f
dr N Σ
po (3) (=) (e))log log p)(21x;) dz. r(2)
(The details given in Appendix A.1
In practice, we can approximate po(x,s) po (x) (s/z) and po(x) using the empirical distri- bution the observations (e.g., the calibration set D). As for (2(2)=) the reparameterization trick (Kingma & Welling 2013) forces z to conform to a normal distribution which relies on F;, and hence its deterministic function can be rewritten
f(x, e) with an (auxiliary) noise variable e.
Substituting all of these into the above equation, we obtain the following loss function
=
Σ N
[log + log ( (x,1 [)] (
(2)
Intuitively, the expected log-likelihood Es-s(e,,,) [log go (0; (3)+=)))+000))) E to predict and regenerate simultaneously, whereas the Kullback-Leibler (KL. divergence aims to compress the remaining useless information of 2.
[)] allows the encoding
Instantiation. Eq. suggggss natural design of the Encoder-Decode architecture. In our method, the stochastic encoder with parameter has the form (= æ)) = (2 fy and fz) are two MLP networks to output the mean and variance of normal distribution. We set r(2) as a standard normal distribution. N(0, 1) and directly minimize the KL divergence term in Eq. using the reparameterization trick.
where fu (z)
We now concentrate on two decoders with parameters o and yp The instantiation of decoder with parameter yo is trivial. For the expected log- lgeliikl fg-f(x..)) [log (2; [rra [)] in Eq. utilize the standard Mean Squared Error (MSE) as the reconstruction loss (Kingma & Welling 2013).
Decoder with parameter é aims at predicting S. which indicates whether the sample X belongs to group & not. Assume set of observations, e.g., the calibration set D {(X,, YO) The distribution P(S|X) can be viewed as binary classifier h comprising an encoder with parameter A and a decoder with the parameter Φb. The result of on D is a vector = [ svv] E (0, 1)
Let &. = DD denote the group determined by s on D and H. be the family of all plausible h. We extend an inequality (Cauchois et al. (22II) measure the deviation between the empirical coverage probability P,, on 'D and the oracle coverage probability P.
Proposition 1. Let the VC-dimension VC(H) R and 5 = 1/.l/N be the proportion of G. to the entire dataset. Then the gap between the empirical coverage probability F,, on the observations and the oracle coverage probability IP is upper bounded, i.e., there exists some constant C1 for all
Rlog N +
sup ([P, ((X))())))) X G.1 PPY e C(X) G s & SiV
8N
heH
holds with probability at least 1 TT.
Proposition Appendix(A.2) for proof) highlights two key directions for reducing the discrepancy between Ir,, and P. First, lower VC-dimension VC(h) leads
more precise estimation P...
4

---

Published as a conference paper at ICLR 2026
implying that the classifier h should exhibit limited complexity. Second, the selected group must be sufficiently large to ensure reliable estimation.
We maximize the expected log- liglliielhood Ez-s(=,,c)) [log (sss)) [a]] in Eq. via minimizing the ex- pected empirical conditional coverage of the selected group g. The group & on D is determined by a random vector S, sampled from a joint Bernoulli distribution B = I1 Bernoulliggd) (go(S, = 1 1
Hence, given D, we formulate the following optimization problem:
min ( C(X) X Gs]]
s.t. (
(3)
In the above minimization problem, d | denotes the the proportion of the selected group size to the whole dataset D. and the decoder with parameter & is a simple logistic regression model of the form ( 2) ass fm (3)), where a is the sigmoid function and fm is MLP network.
To solve the constrained optimization problem, we employ the Projected Gradient Descent (PGD), an iterative optimization algorithm (Madry et al.] (017). to optimize the parameter Φb In each training step, PGD performs a gradient descent update and then projects the new point onto the feasible set ensure all constraints are satisfied. Specifically, when the predictive distribution ( ž) does not meet the constraint + Ei= (s, 1 1 2 8 after one back propagation process. we project it back onto the constraint frieendlt space. Such a projection is equivalent to an &g distance minimization problem. Let (5 (2) ... ( () be the descending order of (s: {)) and the projection results in
(s B) min (o E)+ 2
(4)
where w (6-k- Ein ())[(///NNNN 2 k [NV] is the greatest index to satisfy (s 2)++ w/2 2 and 93 (sk+1 8) w/2 < 1. (The details are given in Appendix A.3
Overall, we employ the empirical conditional coverage loss Lcc, the reconstruction loss LMSE, and the KL divergence loss CKL to replace the corresponding terms in Eq, 2 resulting in
L = Lcc LMSE BLKI.
(5)
3.2 CONSTRUCTING THE ADAPTIVE PREDICTION SETS
After selecting the unfair group J. we proceed to construct the final prediction set with G. First, standard conformal prediction set C' (_ D) is constructed using classic adaptive conformal prediction. Then, we perform T sampling of the vector St (t E [T]) from the joint Bernoulli dis- tribution B learned by models in Eq. calibration set to build prediction set Cm (XN+1, 9n,) as mentioned in Section 2 The final predic- tion set for YN+1 is given by the union of all these sets:
Each 8, defines a group Go.- and such group is used as a
C(XN+)) = Cm (X D) u Cn
[=1
Our approach FAREG is summarized in Algorithm To analyze its time complexity, assume we have M test instances and the complexity of conducting classic conformal prediction is O(N + +M) Then, training the model to select groups is OEEN + [o| + (())), where E is the number of epochs. For all M test instances, the time of selecting groups and constructing prediction sets is O(TN TM). The overall complexity of FAREG is D(EN(()) + |o] 1(]) T(N M)), which O(N M), disregarding constant multiplicative factors. In contrast, the complexity of AFCP ON log N + NM) (Zhou & Sesial 2024).
The following result, proved in Appendix A.4 ensures that the prediction set C(XN.I) ) generated by FAREG achieves adaptive equalized coverage (Eq. I over the selected group set (9x, )
Theorem 1. If( H are exchangeable, the prediction set C(X and the selected group set (G..)% VT, output by Algorithm I satisfy the adaptive equalized coverage defined in Eq. 1 and this guarantee still holds when the selected groups are defined by a more complex combination of features (e.g., non-linear) compared to AFCP.
5

---

Published as a conference paper at ICLR 2026
Algorithm The overall framework of FAREG.
Input:
calibration dataset D ()) test instance with feature XN+1; list of K sensitive features; pre-trained classifier f; fixed rule to compute nonconformity scores; level a (0, selected group size proportion 6; hyperparameter B: sampling times T';
Output: prediction set C(1N=1); selected group set (9,,) )
1: Construct classic conformal prediction set Cm (XN+1, D) based on the output of
2: for each batch do
3: Calculate KL divergence loss LKL with reparameterization trick;
4: Sample ह f(x,c);
5: Calculate conditional coverage loss Lee and reconstruction loss LASE using ä;
6: Put all losses together in L defined in Eq. 5
7:
Update parameters 0, 6 and yp via the gradient descent of C;
8:
if Ei (S; 1 1| <6 8 N then
Project each (S: 1 2) satisfy minimum set constraint using Eq. 10: end if
9:
end for
12: for e [T] do
Sample 8; B: Construct C. (X N+1, 9;
a joint Bernoulli distribution mentioned Eq.
14:
15:
end for
16: Construct prediction set C(XN+1) following Eq.
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Baselines. We select the classic CP method Marginal (Romano al. 2020b) for classification, the initial CP method Partial (Romano et al.) 2020a) considering equalized coverage, and the state- of-the-art method AFCP (Zhou & Sesia] 2024) as our baselines. The vanilla version of AFCP is designed to pick at most one sensitive feature (referred to as AFCPI), We also extend AFCPI to select two sensitive features (referred to as AFCP2), given unreal, strong prior knowledge. Note that in real-world applications, it is typically unknown exactly how many features the unfair group may correspond to.
Evaluation Metrics. To evaluate the prediction sets C(XN+1) produced by different CP meth- ods, we use the coverage conditional on a specific group (referred to as Group Coverage), Average Coverage (viz., marginal coverage), and Average Size (viz., efficiency) as the metrics.
Additionally, we propose a new conditional coverage metric, viz., WSC* to capture groups defined by complicated (nonlinear) feature relationships. Traditional conditional coverage metric (Cauchois) et al. 202[) considers the worst coverage over all slabs containing ó mass on the observations, which defined as
WSC, = inf (P ((())aas' s.t. P.
where v d and a < be R.
To strengthen the WSC metric, we replace the linear mapping T in the above equation with an arbitrary non-linear function giving rise to WSC* i.e.
WSC, (C, == inf (P. ((X)lasm(())
s.t. (X)
asb
Assume quadratic function (x) x Wx xxx where W Raddd and v Rdd We uniformly draw 1,000 samples π, [ j. v to compute the worst-slab coverage for each π, on the test instances. Following Cauchois et al. (2021). we use the grid search to achieve the optimal a satisfying the desiderata as well. this case, we have lower bound for our metric WSC

---

Published as a conference paper at ICLR 2026
Cumulative probability
1.00
WSC, v)
METRIC
6= 0.1
6 0.2
0.3
6
6= 0.5
0.75
WSC," m)) m)
0.616
0.748
0.793
0.822
0,842
WSC,
0.50
(0.053)
(0.037)
(0.025)
(0.023)
(0.023)
0.582
0.674
0.750
0.800
0.829
0.25
WSC,
(0.047)
(0.048)
(0.034)
(0.028)
(0.024)
0.00
IMP.
-5.52%
-9.89%
-5.42%
-2.68%
-1.54%
0.82
0.84
0.86
0.88
Worst coverage probability
Figure 2: CDF of Conditional Coverage Table I: Performance of WSC,, and WSC,, metrics w.r.t. different 6. We repeat the experiment 10 times, and report the average results (the value in () is the standard deviation). Smaller coverage is better. Our metric WSC, performs better than WSC,, by up to 9.89% to mine the group with the minimum worst-
(Ó = 0.5), which plots the respective cumula- tive probability curves of different worst-slab coverage discovered by WSC, (C,v) and WSC, (C, x) over 1,000 samplings. The red curve is always above the blue curve, indicat- ing that our WSC (C, x) finds more groups slab coverage (defined in Eq. 8 with the poor coverage than WSC,, (C.v).
Proposition 2. Let (x)
W vT be quadratic function and II be parameter space of т. Then, if C effectively provides conditional coverage at level - Or, we have
Ogg 6N
WSC; inf (C,) xell
(8)
The proof is given in Appendix A.5
To demonstrate the advantages of the new metric WSC*, we randomly draw the features X e [0, 1] from a uniform distribution and create a simple dataset for classification as described in Ap- pendix [.1 Note that we define the group needed to be protected to satisfy (X[0) 2 0.1) (X[]
0.1) = True. We respectively plot the Cumulative Distribution Functions (CDF) of WSC
n C.
and WSC (C, (C,x)) over 1,000 samples 5 when 0.5 in Fig. 2 and observe that our WSC (C, always reveals the groups with the worse coverage than that of WSC,, vC, which can be attributed to representational capability of the nonlinear function x WSC (C, x).
Moreover, we also list the average results of two metrics, WSC,, and WSC,, as 5 increases over 10 repeated experiments in Table [ Similar to Fig. 2 the minimum worst-slab coverage found by our WSC; is smaller than that found by WSC,, by up 9.89%. As ô increases, the condition coverage tends to the marginal coverage (0.9), and the gap between WSC, and WSC; narrows, as expected.
Implementations!! All the experiments are carried out on NVIDIA GeForce RTX 3090. We re- peat each experiment 10 times and report the average to suppress randomness. We set 8 0.5 for WSCt by default. More implementation details, such as hyperparameters and training settings, are presented in Appendix B.
4.2 SYNTHETIC DATA
We evaluate our method on synthetic data designed to mimic mental illness diagnosis scenario. The dataset includes six possible labels: Depression, Anxiety Disorders, Bipolar Disorder, Schizophre- nia, Anorexia, and Post- Traumatiiiic Stress Disorder (PTSD). Each sample contains four sensitive features-Age Group, Region, Gender, and Color-along with six non-sensitive features indepen- dently sampled from uniform distribution within a value range [0, 1]. The sensitive features generated as follows: (I) Gender is uniformly drawn from (Female, Male]: (2) Color is uniformly drawn from (Red, Blue); (3) Age Group is drawn from (Child, Youth, Middle, Elder) with equal probability; (4) Region follows a fixed cyclical sequence: Asia, Europe, Africa, America, Oceania.
We then generate true labels Y for the dataset, where diagnosis more challenging for a specific subgroup defined by the Exclusive NOR (XNOR) operation (cf. Appendix B.I)). Specifically, we assume X[O] is Color, [1] Gender, and X[2] is any non-sensitive feature, and define Y based
Our code is publicly available http://github..co/Xust/ 123/FaReG.

---

Published as a conference paper at ICLR 2026
0..00
Fanud ARCFS
SPOP
Coverage
0:90
AFCP2
Puncr Size
Fahes
AROP2
ArOR)
Gruu Cove
Porka
0.0
Perts
0.90
Portee
Hurghil
0.80
0.0
302
1000
2000
3000
4000
500
2000
3300
4002
302 3200
2200
4000
500
2002
2000
3000
4000
Sample si20
Samppe $20
Sample 5520
Samppe 5120
(a) Group Coverage
(b) WSC,
(c) Average Coverage
(d) Average Size
Figure 3: Performance of prediction sets produced by different CP methods on synthetic data w.rt. the total number of training and calibration data instances. Only our FAREG achieves the ideal conditional coverage (0.9), and meanwhile, does not sacrifice too much information (set sizes) com- pared baselines.
4000
0.0
0.3
Serecion troquergg
Sundes sis
2000
0.0
8200
Kikas MON
Selection
Faleen APCH)
Falte
3000
FaRro AROM
82
62
500
APOF
Time Cost (4)
Sample
Sumplesize
Sample slz0
(a) Time Cost
(b) Selects X[0]
(c) Selects X[1]
(d) Selects X[O]&X[[]]
Figure 4: Fig. (a) reports the running time of different CP methods with the increasing total number of training and calibration data instances. Fig. (b)-(d are the results of the selection frequency of target features [[]] and X [[]]. As the sample size increases, our method becomes more consistent with target features.
solely on these three attributes. Through the label generation, we have the following subgroup [ o X[1]= = True: Color=Red (True) & Gender=Female (True) or Color=Blue (False) & Gen- der=Male (False), simulating a real-world situation that algorithmic biases occur on this subgroup.
Fig. 3 depicts the results of conditional coverage, average coverage (marginal coverage), and aver- age prediction set size (efficiency), respectively. For conditional coverage, Group Coverage the coverage the subgroups defined by XNOR operation as mentioned in data construction, and we compute WSC on four predefined sensitive features. Fig, 3a and 3b our FAREG is the only one that always achieves valid coverage (greater than 0.9) for the targeted group with varying sample sizes. Although the conditional coverage of AFCP2 also exceeds 0.9 when the sample size reaches 500, shown in Fig. 3d it produces considerably larger prediction sets, which is less informative for decision-makinn.
In Fig. 4a compare the average running time of different CP methods (e.g., the wall-clock time of the entire FAREG pipeline) over 10 repeated experiments, and FAREG significantly reduces the time cost. Actually, the training of the encoder-decoder network occupies most of the time cost (e.g., in one trial with a sample size of 2,000, the training step required 161.3 seconds, while the rest took only 0.8 seconds). Additionally, the training time of the encoder-decoder network scales linearly w.r.t the sample size since we fix the epoch number and batch size in our algorithm. This result is consistent with the analysis in Section 3.2
To determine which features are selected by our method, we analyze the predictive variable S and the reconstructed feature X by perturbing the latent representation Z, following the Beta-VAE ap- proach (Higgins al. 2017). Specifically, we impose a slight perturbation (e.g., +0.001) on each dimension of Z and identify the dimension that most influences S. Given this influential dimension and prior knowledge (as in AFCP2) that there are exactly two target features, we compute the change ratios for each dimension of X before and after perturbation, and select the two features with the 2 maximum change ratios.
Figures 4b 4c and respecciiv report the frequency of selecting X or X[1] individually, and that of selecting both X(0] and X [[]] simultaneously. The results demonstrate that approach
8

---

Published as a conference paper at ICLR 2026
0..0
Fanud ARCFS
SPCP
Coverage
0:90
AFCP2
Muucragg Size
Fahes
AROP2
ArOm
Group Cove
Porka
0.0
Perisl
0.90
Porte
Hurghal
0:22
0.80
0.0
302
1000
2000 Sample size
3000
4000
500
2000
3300
4002
302
3200
2200
3000
4000
500
2002
2000
3000
4000
Samppe $20
Sample 5i20
Sampp 5120
(a) Group Coverage
(b) WSC,
(c) Average Coverage
(d) Average Size
Figure 5: Performance of prediction sets produced by different CP methods on the Nursery data w.r.t. the total number of training and calibration data instances. Only FAREG achieves the ideal conditional coverage (0.9) and keeps most of the uncertainty information sets.
captures target features than the baselines, and this advantage becomes more pronounced as the sample size increases.
Additionally, we present the results of parameter sensitivity and group visualization in Appendix B.2 and B.3 respectively.
4.3 NURSERY DATA
We evaluate our FAREG and baseline methods on the publicly available Nursery data (Rajkovic 1989), originally constructed from hierarchical decision model developed to rank applications for nursery schools. The dataset comprises 12,960 instances, each described by eight categorical fea- tures:
Parents' occupation (3 levels, Parent:= [ [usual, pretentious, (reat)-rer)), Child's nursery (5 levels), Family form (4 levels), Number of children (4 levels), Housing conditions (3 levels), Fi- nancial standing (2 levels, Finance:= (conveniec,,,,,,nn,, inconv)). Social conditions (3 levels) and Health status (3 levels). The task to classify applications into one five priority ranks. We take all features into account (as sensitive features) except Housing conditions.
In data preprocessing, we strictly follow Zhou Sesia (2024). and consider a group defined by Parent=usual & Finance=inconv Purent=pretentious & Finance=inconv. To make the issue more interesting and control the degree of algorithmic bias, we corrupt the labels of instances in such a group by adding independent, uniform noise and rounding to the nearest integer (label) as similar as /hoo & Sesia (2024). This perturbation amplifies the intrinsic unpredictability of the group defined before, thereby increasing its vulnerability algorithmic bias.
Fig. 5 presents the results. Our method consistently achieves the valid coverage under both condi- tional coverage metrics, i.e., Group Coverage and WSC,, outperforming all baselines. Partial and AFCP2 perform better than the other CP methods, but FAREG still achieves superior results.
5 RELATED WORK
Conformal Prediction (CP) has seen vigorous development in recent years (ovk et al., 2005 Smith 2024). Its applications span diverse domains, from image classification (Sadinle et 2019 and
object detection (Teng et al. 2023) to large language models (Kumar et al. 2023).
Some CP work, building the split conformal framework (Papadopoulos al. 2002 Lei al.
2018), introduces advanced nonconformity scores to ensure valid marginal coverage on the empir- ical data distribution. For example, [Romano et al. (2019) gives nonconformity score based on quantile regression, while Romano et al. (2020b) and Angelopoulos et al. (2020) design nonconfor-
mity scores for classification. Additionally, Hoff (2023) proposes a nonconformity score to achieve Bayes optimal coverage.
Another line work has explored various notions equalized coverage (Romano et al. 2020a) and empirically evaluated the corresponding conformal predictors in real-world applications (Lu et al. 2022). For regression tasks, Wang et al. (2023) guarantees equal coverage rates across more fine grained groups continuous features, and Liu et al.) (202) propose to learn rellev quantile function with respect to sensitive features. They address a distinct notion equalized coverage tailored continuous outcomes. In classification, label-conditional coverage is common

---

Published as a conference paper at ICLR 2026
alternative to equalized coverage (Vovk et al. 2003 Löfström et al. 2015 Ding al. 2023 This work defines the groups to be protected based on the label N+1 instead of the features N Jung et al. (2022) Vadlamani et al. (2025), and Gibbs al. 2025 adopt couup-conditonal coverage, which is analogous to equalized coverage, to improve prediction sets. Different from the previous work, our approach FAREG can adaptively identify unfairly treated groups without the assumption that such groups are pre-defined. AFCP (Zhou & Sesial (2024) develops an algorithm to construct CP sets with valid equalized coverage for adaptively selected groups, which establishes the current thate-of-the--ee for equalized coverage tasks.
CONCLUSION
In this paper, we propose FAREG, a fair conformal prediction method that learns latent groups to achieve adaptive equalized coverage. By leveraging variational encoder-decoder to discover sub- groups wih poor coverage in a high-level feature space, our approach captures complex algorithmic biases that linear methods may neglect and can adapted different fairness notions. We also propose WSC", nonlinear metric for evaluating the conditional coverage of unfair groups more ac- curately. Extensive experiments confirm that FAREG efficiently offers stronger fairness guarantees, showing a more expressive and practical path toward fair, reliable conformal inference.
Limitations. The enhanced expressivity of representation-base terpretability partially, compared to groups explicitly defined on manifest features. However, the encoder-decoder structure compensates this shortcoming well via reconstructing the input X, which is empirically confirmed by Section 4.2 and Appendix B.3
groups may sacrifice model in-
ACKNOWLEDGMENT
We appreciate anonymous reviewers for their valuable comments. This work is supported by the Frontier Technologies R&D Program of Jiangsu (BF2024059). National Natural Science Founda- tion of China (Grants #62025202). and the Collaborative Innovation Center of Novel Software Tech- Chen partially supported by overseas grants from the State Key
nology and Industrialization. Laboratory of Novel Software Technology. Nanjing University (KFKT2023A04, KFKT2025A05). Yuan Yao is the corresponding author.
REPRODUCIBILITY STATEMENT
To facilitate the reproducibility our work, we have made our source code available online through public repository. All experimental details, including dataset partitions, hyperparameter config- urations, and model details, are fully documented Appendix [B.T are confident that these materials provide the necessary information to replicate our findings.
USAGE OF LLMS
Large Language Models (LLMs) were utilized exclusively writing assistants to enhance the lin- guistic quality this manuscript, focusing on improving clarity, grammar, and readability. Their involvement was strictly limited to this editorial function. LLMs played no role in any substantive research components, including conceptualization, experimental design, data analysis, interpreta- tion of results, or scientific content creation. All intellectual contributions, methodological develop- ments, findings, and conclusions originate solely from the authors.
REFERENCES
Shams Forruque Ahmed, Md Sakib Bin Alam, Maruf Hassan, Mahtabin Rodela Rozbu, Taoseef Ish- tiak. Nazifa Rafa, M Mofijur, ABM Shawkat Ali, and Amir H Gandomi. Deep learning modelling techniques: current progress, applications, advantages, and challenges. Artificial Intelligence Re- view, 56(( 13:11121-13617 2023.
10

---

Published as a conference paper at ICLR 2026
Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, and Kevin Murphy. Deep variational informa- tion bottleneck. In International Conference on Learning Representations (ICLR), 2017. URL https: /tt::////xiivi. wwt./bg.///ooooooottttoott..errt ICLR 2017.
abs
arXiv preprint arXiv:1612.00410, accepted to
Ahmed S Almasoud and Jamiu Adekunle Idowu. Algorithmic faireess in predictive policing. Al and Ethics, 5(3):2323-233 2025.
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. 2020.
Richard A Berk, Arun Kumar Kuchibhotla, and Eric Tchetgen Tchetgen. Improving faimesss in criminal justice algorithmic risk assessments using optimal transport and conformal prediction sets. Sociological Methods Research, 53(4):1629-1675, 2024.
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-378 2005.
T Tony Cai, Mark Low, and Zongming Ma. Adaptive confidence bands for nonparametric regression
functions. Journal of the American Statistical Association, 109(507):1054-1000 2014.
Maxime Cauchois, Suyash Gupta, and John C Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of machine learning research, 22 (81):1-42, 2021.
Sanjiv Das. Richard Stanton, and Nancy Wallace. Algorithmic faimess. Annual Review of Financial Economicx, 15(1):565-533 593,,55533200 2023.
Ketki V Deshpande, Shimei Pan, and James R Foulds. Mitigating demographic bias in ai-based resume filtering. In Adjunct publication of the 28th ACM conference user modeling, adaptation and personalization, pp. 268-275, 2020.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair
machine learning. Advances neural information processing systems, 34:6478 1798,6690,00 2021.
Tiffany Ding, Anastasios Angelopoulos, Stephen Bates, Michael Jordan, and Ryan Tibshirani. Class-conditional conformal prediction with many classes, Advances neural information pro- cessing systems, 36:64555 66664555-64576. 2023.
Alessandro Fabris, Stefano Messina, Gianmaria Silvello, and Gian Antonio Susto. Algorithmic fairness datasets: the story far. Data Mining and Knowledge Discovery, 3666):2774-2522,
2022.
Isaac Gibbs, John Cherian, and Emmanuel Candès. Conformal prediction with conditional guar- antees. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp. qkaf008, 2025.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Deborah Hellman. Measuring algorithmic faimess. Virginia Law Review, 106(4):811-866 2020.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with a constrained variational framework. In International conference on learning representations, 2017.
Peter Hoff. Bayes-optimal prediction with frequentist coverage control. Bernoulli, 29(2):901-928, 2023.
Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid confor- mal prediction. arXiv preprint arXiv:2209.15143 2022.
Paulin Kamuangu. A review on financial fraud detection using ai and machine learning. Journal of Economics, Finance, and Accounting Studies, 6(1):67, 2024.

---

Published as a conference paper at ICLR 2026
Simarjeet Kaur, Jimmy Singla, Lewis Nkenyereye, Sudan Jha, Deepak Prashar, Gyanendra Prasad Joshi, Shaker El-Sappagh, Md Saiful Islam, and SM Riazul Islam. Medical diagnostic systems using artificial intelligence (ai) algorithms: principles and perspectives. leee Access, 8:228049- 228069, 2020.
Diederik P Kingma and Max Welling. arXiv:1312.6114, 2013.
Auto-encoding
variational
bayes.
arXiv preprint
Bhawesh Kumar, Charlie Lu, Gauri Gupta, Anil Palepu, David Bellamy, Ramesh Raskar, and An- drew Beam. Conformal prediction with large language models for multi-choice question answer- ing. arXiv preprint arXiv:230S. 18404, 2023.
Yonghoon Lee and Rina Barber. Distribution-free inference for regression: discrete, continuous, and in between. Advances Neural Information Processing Systems, 34:7448-7459, 2021.
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):71-96, 2014.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113
(523):1094-111, 2018.
Meichen Liu, Lei Ding, Dengdeng Yu, Wulong Liu, Linglong Kong, and Bei Jiang. Conformalized fairness via quantile regression. Advances in Neural Information Processing Systems, 1561- 11572, 2022.
Tuve Löfström, Henrik Boström, Henrik Linusson, and Ulf Johansson. Bias reduction through conditional conformal prediction. Intelligent Data Analysis, 1966): 2015.
Charles Lu, Andréanne Lemay, Ken Chang, Katharina Höbel, and Jayashree Kalpathy-Crannn Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 12008-12016 2022.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.066 2017.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, Sebastian Nowozin, Joshua Dillon, Balaji Lak- shminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European conference on machine learning, pp. 345-356, Springer, 2002.
Vladislav Rajkovic. http://dd..oorro10244333/3//////
Nursery.
UCI Machine Learning Repository, 1989.
DOI:
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Ad-
vances neural information processing systems, 32, 2019.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2020a.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive cover- age. Advances in neural information processing systems, 13:3581-33991, 2020b.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223 2244244, 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Ralph C Smith. Uncertainty quantification: theory, implementation, and applications. SIAM, 2024.
12

---

Published as a conference paper at ICLR 2026
Jiaye Teng, Chuan Wen, Dinghuai Zhang, Yoshua Bengio, Yang Gao, and Yang Yuan. Predictive in- ference with feature conformal prediction. In The Eleventh International Conference on Learning Representations, 2023.
Aditya T Vadlamani, Anutam Srinivasan, Pranav Maneriker, Ali Payani, and Srinivasan Parthasarathy. A generic framework for conformal fairness. arXiv preprini vrXiv:2505.16111 2025.
Vladimir Vovk, David Lindsay, Ili Nouretdinov, and Alex Gammerman. Mondrian confidence machine. Technical Report, 2003.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer, 2005.
Fangxin Wang, Lu Cheng, Ruocheng Guo, Kay Liu, and Philip S Yu. Equal opportumity of coverage in fair regression. Advances in Neural Information Processing Systems, 36:7743-7755, 2023..
Yanfei Zhou and Matteo Sesia. Conformal classification with equalized coverage for adaptively selected groups. Advances in Neural Information Processing Systems, 17:108760-18882,, 2024.
13

---

Published as a conference paper at ICLR 2026
A TECHNICAL PROOFS
A.1 VARIATIONAL INFERENCE
As mentioned in Section 3.1
optimization objective is follows, max ((Z,5)) I( -3,(),))
First of all, we consider SZ, and
pe(3,2) ds f po(s, 2) log po(s(2) dsdz. po())po(z)
I(Z,S)= = po log
po(s)
Since the KI. divergence between two conditional probability distribution po(s and ts (s( =) non-negative, we have
(po [+)==)<=<)((==)))))))))))))))))) 2 f (og f (o((s, ( ds,
where yo (5 =) is variational approximation to the intractable distribution po(s|z).
Plugging the above inequality into Eq. we obtain
1(Z,S) f Po(s, log (s(s]2) ds da po(s)
f po(s, 2) log g
(5| (s) dsdz+ f (os) ds
(10)
f po(s. 2) log (s dsde,
where the second inequality is derived by the non-negativity of entropy. Since S Z| X holds, we have
po(s,2) f po(x,8,2)ddr f po(x))o(s) x))p(= (a)) da.
Hence, we get
I(2,5)2
log dr) drdsde.
(11)
Similar to Eq. 10 we also have
I(2,X) f pa(x, (z dr
(12)
f po(=))po())))) log dr.
As for i(Z,i), we have
1(2,)) Σ f pa p=(2)i)po(i) log
Po(212) de
po (2)
N Σ f po(2|2;) log
1
( 2 [x;)
de
(13)
(=
N Σ f po(2|2;)) log
(= (x;)) de, r(z)
where r(z) is a variational approximation to the posterior distribution (=):). We usually set r(z) as standard normal distribution (0, 1) in practice.
Combining Eq. with Eq. 12 and Eq. 13 we obtain
((2,)) + + -I(X)) f Po
(s(22) dz dsdz
+ f po (z)))))22) dx 8 po(2) 24) log
p=(21x)) dz.
Σ N
r(z)
14

---

Published as a conference paper at ICLR 2026
With Monte Carlo sampling, (p (s z) and po()), where S; computed by minimizing the conditional coverage groups
the empirical dataset S,,
estimate
defined by S = {s1,..., sN i.e., Pn C(X)) Xx Gs on {X,, S.. Y We leverage the
reparameterization trick (Kingma Welling 2013) as mentioned in Section 3.1 and finally obtain
L Σ (B log (x, -
A.2 PROOF OF PROPOSITION
1
Proof. We first present technical lemma, where P, N EN h(X,) and Ph I h(=)dP(x), given an observed dataset (X;, Yi]
Lemma
[Boucheron et al. (2005)). There exists numerical constant C₁ such that for any T > O,
VC(h) log N +
VC(h) log N +
PP,h- PM s Ci
V min (ihh, Pnh, Ph}
N
N
holds with probability at least eT
By this Lemma, we have
[P E
(14)
sai
cCi[/min( CCiN
xe()) VC(h) log
VC(h) log N+r
Similarly, get
Pa 9a) &
(15)
s Cc ( E.)))
log
Io(h) Nor
N
N
Then, remains to show that
[P P
P.(YEC(X) (() 9a)
Pa(X 9.)
P(XE
Let a= P. e C(X), b=),b= P(Y e ( (Pn - P) E (x) and d P(X
G.). We can derive s d, and observe that
b s c+
b b-c 6 la bl ldl
(16)
c+d c+d c+ d c d'
c+d
Substitute Eq. 14 and Eq.
15 into Eq. 16 and use 8 Px Ga), we obtain
PaYY e ((X) G.)
P(Y X(Y
P))
P(
C(X)) X - P(Y ((X)) [Pa(X E - P(X e Ga) P G.)
(((ee..)
VC(hi log Nog VC(h) log +
s C3
8N
8N
which completes the proof.
15

---

Published as a conference paper at ICLR 2026
A.3 OPTIMIZATION PROCESS OF EQ. 4
The projection operation of the PGD algorithm described in Section 3.1 requires solving the follow- ing optimization to minimize the 82 distance:
min (v, (v. u,)² s.t. 1=1
Us u [0.1] I,
(17)
[=1
where U1,.... u are given and u, E [0, 1J holds for each i [N].
With the above constraints, we compute the Lagrangian as
N Clus ((s;)e)He:w)) (v: u.)² Σ A-()))) Σ
N
N Mu w(6
U)),
where
(Nr ( and w are the Lagrange multipliers. Let the partial derivatives vanish, and
we have
dc
-0) (4)== X 2(v; u,) - x M4 - 2(U; -
Du.
For the complementary relaxation conditions, there are four different cases:
If' 0; 0, constraint 0 2 is activated and we have A 2 0, = O;
If 2; 1, constraint 2 $ is activated and we have 14 2 0, A = O; If 04 I, we have 14, X; 0 and then v, u, w/2;
If v4 6, constraint Σ U/ 2 is not activated and then w O; otherwise, w 0.
When Σu 2 6, we have u4 which is an optimal solution to the minimization problem in Eq. 17
When Σ u; < 6, let 0/2 min(1, u, + w/2). where w 2 0 and ΣN min u, w/2) 2 6. this case, we resort (v:) ( descending order, i.e., ((1) 2 v(2) 2 ... 2 V(N). Let & E [N] is the greatest index satisfy ((K) + w/2 2 and U(++1) w/2 < Then, constraint Σ U2 can be written
N Σ
k 1
(u() + w/2) 6.
Hence, we obtain
2 h: Eisk+l v(3))
N k
In practice, compute & and w via traversing the value of & from maximum N to minimum 1.
A.4 PROOF OF THEOREMI 1
Proof. When making the similar assumption as Theorem 1 in AFCP (Zhou & Sesia 2024]. for each group Ga (9x,77 we can substitute XN+1 E Ga for A(Xxi)((xx))) and XN+1 E 9g for 6(XN+1, (x(Xx=)) conditions, where Gg is an imaginary oracle group. Then, according to Theorem (Zhou & Sesia 2024), we have
P[YN+1 e C(XN+)) |NN1) 1.]21-1 1-a
AFCP assumes that the group selection algorithm can always achieve the oracle group Gg. which means that the algorithm must have enough expressiveness include GJ into the candidate group space. However, this necessary condition could be violated, AFCP's candidate group space is limited to linear groups defined by individual features. contrast, our method, FAREG, employs more expressive model that extends its candidate group space into the nonlinear realm. Conse- quently, the guarantee for FAREG remains valid for groups defined by complex, nonlinear feature combinations.
Next, we formally analyze the expressiveness of AFCP and our FAREG based on the VC-dimension. As described in Section AFCP computes the group coverage scores for each feature and greedily
16

---

Published as a conference paper at ICLR 2026
picks the most sensitive feature with the lowest group coverage The essence of such process a decision stump dividing all features into two parts (sensitive or not sensitive) using a threshold, and thus its VC-dimension is 2. In contrast, based established theory (Shalev-Shwattz & Ben- David 2014), the VC-dimension of FAREG scales with its parameter size M,,.e., VC(AFCP) = 2, VC(FAREG) O(M).
Hence, the VC-dimension of FAREG is typically far larger than that of AFCP, indicating the stronger expressiveness of our method, i.e., our candidate group space serves as superset of AFCP's candidate group space.
A.5 PROOF OF PROPOSITION
2
Proof. According to Proposition 1 and the definition of WSC, (Eq. 7
obtain
Vg(
-PY x(X)) V
5N
well
by omitting Then, we eliminate the absolute value
(Cgg))ogNN
VC(T) log
-0(1)
ON & -) (
6N
which holds for all TE II. Hence, (C()) <b) = a, we can observe
0(1) ICgT)
(S, P(Y (
5N
for any IT.
Next, we only need to prove O(d)) 2 VC(T). Recall that VC(T) denotes the VC-dimension of the binary classifier т, and क x Wx v quadratic function, where W e R and IRd Therefore, the VC-dimension of is equal the dimension of its expanded feature space M = d(d+ 1)/2 d, i.e., (dd), which completes the proof.
B FURTHER EXPERIMENT DETAILS
B. DATASET CONSTRUCTION AND HYPERPARAMETERR
Table 2: Hyperparameters of FAREG.
DATASET
SYNTHETIC DATA
NURSERY DATA
MODEL
MLP
MLP
NUMBER OF LAYERS
3
3
HIDDEN DIMENSION
[64.32]
[64,32]
EPOCH
2000
800
BATCH SIZE
500
500
LEARNING RATE
0.001
0.01
3
2.0
0.1
8
0.3
0.1
T
20
100
For the dataset we use to evaluate two metrics in Section 4.1 only X[1], and X[2] influence label and we define the conditional distribution P(Y as
1 0,000, (X[ 0.1) (X[1] 0.1) and X 0.5,
3 3133
(.
(X 2 0.1) e (X[1] 0.1) and [ 2 0.5,
(1,0,0,0,0,0), nft (X[0) 0.1) @ (X[1] 2 0.1) and X[2] < g
X(Y
(0,1,0,0,0,0), not (X[0) e (X[1] > 0.1) and 186 X
6
(0,0,0,0,0,1), if X = (x[0) > 0.1) e (x[1) 2 0.1) and
J $ x < 1.
17

---

Published as a conference paper at ICLR 2026
FAR60
Fatee
0.40
Coveroue
0:45
Auerage Size
2.8
0.8
0.85
0.55
7.2
0.
(a) Group Coverage
(b) WSC
(c) Average Coverage
(d) Average Size
Figure 6: Performance of prediction sets produced by our FAREG on synthetic data w.r.t the
selected group size proportion 8.
2-
FaRaC
Group Coverops
Conarage
Awargg Size
0.9
0.9
0.9
0.4
0.85
0.35
50
100
750
(a) Group Coverage
(b) WSC,
(c) Average Coverage
(d) Average Size
Figure 7: Performance of prediction sets produced by our FAREG on synthetic data w.r.t. the
sampling times T.
For the classification models the input of conformal prediction, strictly follow the settings in (Zhou & Sesia 2024) on both synthetic and real-world data. To train FAREG to mine unfair groups, randomly split the calibration set D into the training set and validation set with the ratio 5:5. We list the hyperparameters of FAREG in Table 2 Note that we use the same network structure for encoders and decoders, i.e., a simple 3-layer MLP, which is consistent with Proposition [ Since there are three optimization objectives in Eq. S which may conflict with each other to some extent, divide the training into two stages. At the first stage, we train the encoder with the parameter and the decoder with the parameter ø by fixing the decoder with the parameter yp in practice, i.c., the first term LCe and third term LKL Eq. Then, we use LMSE to reconstruct based on Z at the second stage.
Recall from Section 4.2 that Color denoted as X[0]. Gender is denoted as X[1], and the first standard feature is denoted as X[2). The conditional distribution of Y | X is determined by simple decision tree, where only X()). [[]]. and X[2] provide valuable predictive information for Y, formulated as follows.
3,0,0,
i[] Red and [ Female and X[2] < 0.5,
(0,0,0, 313:3
X Red and [ Female and X 2 0.5,
(,,00)0
i[ Blue and X[1] = Male and [[2] < 0.5,
(0.0,0.3-33.))
X Blue and X(1] = Male and X[2] 2 0.5,
(1,0,0,0,0,0),
i Red and [[1] Male and [[2] !
x)Y
(0.1,0,0.0.0),
if X Red and X [ Male and
X[2] 2.
X Red and X Male and (0,0,0,0,0,1),
5 S xX[] S 1, 3
(1.0,0,0,0.0),
if X Blue and X[1] Female and X[2] < .
(0,0,0,0,0,1),
if X ] Blue and X[1] = Female and
X[2] 1
B.2 PARAMETER SENSITIVITY
In this section, we first investigate the sensitivity of two key parameters: the selected group size proportion and the number of sampling iterations T. The results for 8 and 7 are presented in Fig. b
18

---

Published as a conference paper at ICLR 2026
Table 3: Performance of prediction sets produced by our FAREG w.r. the hyperparameter 3.
B
0.1
0.2
0.5
1.0
2.0
GROUP COVERAGE
0.902
0.898
0.909
0.906
0.904
AVERAGE SIZE
2.738
2.722
2.714
2.721
2.761
1.0
1.0
1.0
0.6
0.6
0.6
0.4
0.4
0.0
0.6
0.0
0.8
0.0
0.0
0.4
1.0
X[0]
X[0]
(a) G.l/NN - 0.31
(b) G.1/N 0.39
(c) / 0.47
Figure 8: The visualization results of reconstruction when //a/N increases. The latent represen- tation generally captures XNOR relationship between X X[0] and X[1).
and Fig. 7 respectively. Overall, the metrics Group Coverage and WSC show relative insensitivity to the number of sampling iterations T, illustrated in Fig. 7a and 7b In contrast, both Group Coverage and WSC,, increase with the proportion ó of the selected group size relative to the entire dataset. This trend empirically provides implicit support for Proposition 1
We further conduct a sensitivity analysis of the hyperparameter (Eq. 5) on synthetic data with sample size of 2,000 and report the average results across 10 runs. The experimental results in show that, as 3 varies, FAREG consistently achieves valid adaptive equalized coverage (0.9) with relatively steady efficiency.
B.3 GROUP VISUALIZATION
To analyze how features X[0] and X[1] contribute to group membership in Go, we perturb the encoding and examine the resulting reconstructions X. Taking the sample size of 4,000 on the synthetic dataset as an example, we randomly select one run from 10 repeated trials and add pertur- bations of +0.003 and +0.006 to the fourth dimension of z, respectively. The reconstructed features X are visualized in Fig-
Fig. 8a shows that, without perturbation, the latent representation generally captures an XNOR relationship between X[0] and X[1], indicating that the encoder effectively filters out irrelevant feature information. After applying perturbations (see Fig. Sb and [c), the XNOR pattern becomes more pronounced as //el/N increases, revealing positive correlation between X[0] @ X[1] and membership in G.. This result strengthens the interpretability of our approach by demonstrating that the representation-bant based groups reflect meaningful feature interactions.
B.4 OTHER SYNTHETIC SETUPS BEYOND XNOR
In this part, we construct
complicated setup by partitioning the synthetic data in Section 4.2 into eight diverse subgroups: Male Child, Male Youth, Male Middle-Aged, Male Elderly, Female Child, Female Youth, Female Middle-Aged, and Female Elderly. We then impose algorithmic bi- ases, using a procedure analogous to that in Section 4.2 on four of these subgroups: Male Child, Male Youth, Female Middle Aged, and Female Elderly. In experiments with a sample size of 2,000, we compare our method, FAREG, with the SOTA method AFCP2. The experimental results in Ta- 4le averaged over 10 runs, also demonstrate that FAR achieves the ideal conditional coverage (0.9) while sacrificing very little efficiency.
B.5 CP METHODS WITHOUT ADAPTIVE GROUP SELECTIONS
We next build FAREG upon the results CondCP (Gibbs et al. 2025), which does not consider
the automatic selection of the sensitive groups discussed in Section 5 As shown in Table
19

---

Published as a conference paper at ICLR 2026
Performance of prediction sets produced by different CP methods on the other synthetic setups beyond XNOR.
Table 4:
METHOD
GROUP COVERAGE
WSC,
AVERAGE COVERAGE
AVERAGE SIZE
AFCP2
0.849
0.866 0.902
0.926
2.68
FAREG
0.901
0.942
2.74
experiments on synthetic data with sample size of 2,000 reveal that CondCP may lack the ex- pressiveness needed to capture complex unfairly treated groups. Consequently, our FAREG method further improves conditional coverage based on CondCP.
Table Performance of prediction sets produced by different CP methods with and without adaptive group selections.
METHOD
GROUP COVERAGE
WSC,
AVERAGE COVERAGE
AVERAGE SIZE
CONDCP
0.819
0.815
0.899
2.53
FAREG
0.904
0.899
0.944
2.76
CONDCP + FAREG
0.903
0.897
0.940
2.72
B.6 MORE REAL-WORLDS DATASETS
In this part, we evaluate our method using the standard ACSIncome dataset from Folktables (Ding ctt al. 2021), which comprises nine features: Age. Class of worker, Educational attainment, Marital status, Occupation, Place of birth, Relationship. Working hours, Gender, and Race. Among these, Age, Marital status, Sex, and Race are designated as sensitive features. The target variable, i.c., a person's income, is evenly divided into four brackets, forming 4-class classification task. We fur- ther partition the Age feature into four intervals: [17-26, 27-36, 37-46,6,44 47-56). A specific subgroup defined by the condition (Age 17-26 & Sex Male) (Age 47-56 & Sex Female), into which we manually inject algorithmic biases, following a procedure similar to that in Section 4.3 For time and cost constraints, particularly given the high complexity of the baseline AFCP method, we randomly sample 20,000 instances from the combined datasets of CA, NY. TX, AK, and AL. The proposed FAREG then compared against the ofte--of-the-rr approach, AFCP2. Experimental sults in Table 6 (averaged over 10 independent runs) show that FAREG still consistently achieves the valid conditional coverage of 0.9 while maintaining competitive efficiency.
Table Performance prediction sets produced by different methods on the ACSIncome data.
METHOD
GROUP COVERAGE
WSC
AVERAGE COVERAGE
AVERAGE SIZE
AFCP2
0.839 0.898
0.883 0.907
3.17 0.918
FAREG
0.936
3.31
20


Reviews:
[{"review_id": "op9LKbLzYs", "reviewer": "Reviewer_eNWr", "summary": "The authors introduce FAREG, a method to employ variational information bottleneck to achieve fair conformal prediction by identifying worst performing subgroups. They also propose an improvement over the WSC metric to capture non-linear slabs. They perform experiments on a self-constructed synthetic dataset and the Nursery dataset, comparing against standard baselines. The authors also provide code supporting the reproducibility of their method.", "questions": "- **[Q1] ** See [W1]. Can you provide a more detailed and fair comparison of the wallclock time of FAREG and AFCP, showing the entire training, processing and postprocessing steps.\n- **[Q2]** See [W2]. Would be curious to see applications of FAREG on other synthetic setups, which are slightly more complicated than XNOR for example.\n- **[Q3]** See [W3]. Could you clarify the confusion about the interpretability of the algorithm and state what the effect of the encoder-decoder architecture is?\n- **[Q4]** See [W4]. Could you provide a more formal proof for Theorem 1, clearly highlighting the superiority over AFCP and the effects of that?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- **[S1]** The authors do a great job of motivating the paper well. Figure 1 is a great example of how the current set of conformal prediction methods struggle in certain data settings. There is a clear gap in the literature that needs to be addressed and the manuscript is an attempt at that.\n- **[S2]** The core idea of FAREG is quite novel, I haven’t come across works using variational information bottlenecks in this context and it feels like a natural fit for potentially non-linear subgroups.\n- **[S3]** The synthetic experiment in Section 4.2 is designed perfectly to highlight the proposed method's strength compared to the baselines and is a great way to show the applicability of the approach.\n- **[S4]** The code seems succinct and sufficient, supporting the neat empirical claims in the paper.", "weaknesses": "- **[W1]** Figure 4(a) and the claims in Line 374 that the time complexity of FAREG is linear in the number of data instances seems misleading, given that this does not account for the training of the encoder-decoder network which is a non-trivial computation. ACP is a post-processing algorithm which does not involve training of any such network and therefore a fairer comparison would be to compute the wallclock times of the entire algorithms from start to end.\n- **[W2]** While the synthetic experiment is a great demonstration of the algorithm's strength, it feels like the perfect application in terms of the XNOR-like bias but the authors do not include any other synthetic constructions that could help understand the algorithm's utility in general situations. \n- **[W3]** It’s unclear to me how the following statements all hold true together: Line 87: The interpretability is enhanced; Line 483: Expressivity may sacrifice interpretability; Line 941: This result strengthens the interpretability. Intuitively, it seems that the 2nd statement in the limitations is true, so what do the other two statements mean?\n- **[W4]** The proof for Theorem 1 in Section A.4 is extremely handwavy. It uses the Theorem 1 from (Zhou & Sesia, 2024) but never establishes how it is better than it formally. There’s a strange argument about the VC Dimension and higher expressivity written in words, but no formal proof of the statistical consequences on learning the groups on the same data used for calibration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ssWaot7IIo", "reviewer": "Reviewer_LJHP", "summary": "The paper introduces FAREG, a fair conformal classification method that finds and fixes under-covered subgroups so that they reach the target coverage, without blowing up prediction-set size. Here are the mains steps of the method.\n1. Learn a compact representation Z of the features X.\n2. On this Z, train a small classifier that scores how likely each sample belongs to an “unfair subgroup” (i.e., tends to be under-covered).\n3. Encourage this classifier to pick the samples with the lowest conditional coverage while keeping the subgroup at least a fraction δ of the data (for statistical reliability).\n4. Build a standard conformal prediction set for everyone, then build extra subgroup-specific sets for the selected groups, and take the union. This guarantees adaptive equalized coverage for those groups.", "questions": "What is the hypothesis class $\\mathcal{H}$ in the proposed algorithm? What is the VC dimension of $\\mathcal{H}$ in this setting?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The problem is meaningful and important. \n2. The method appears technically sound. \n3. Although the full pipeline is more involved than the summary above, the paper is mostly readable.", "weaknesses": "First, the goal of this work is a subset of existing objectives. Prior work has focused on conditional coverage\n$$\n\\mathbb{P}\\!\\left(Y \\in C(X_{n+1}) \\mid X_{n+1}=x\\right)=1-\\alpha,\n$$\nwhich is stronger than\n$$\n\\mathbb{P}\\!\\left(Y \\in C(X_{n+1}) \\mid X_{n+1}\\in \\widehat{\\mathcal{G}}\\right)=1-\\alpha.\n$$\nIf a conformal method attains (approximate) conditional validity, the proposed method may be less useful. It would be helpful to show that results still improve when FAREG is built on top of conditionally valid conformal methods such as~[1]. Second, based on Figures 2 and 5, gains in coverage appear to come at the cost of efficiency: the proposed method achieves higher coverage but also larger prediction sets.\n\n[1] Isaac Gibbs, John J Cherian, and Emmanuel J Cand`es. Conformal prediction with conditional guarantees. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp. qkaf008, 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JQ8d0wJAE0", "reviewer": "Reviewer_9Zja", "summary": "This paper proposes FAREG, a conformal prediction method that ensures fairness by adaptively identifying “unfair” subgroups in a learned latent representation space. Unlike prior conformal predictors with equalized coverage that only consider simple or pre-defined groups (e.g. single sensitive features), FAREG learns a representation $Z = f(X)$ via a variational encoder–decoder and discovers complex subgroups (even defined by nonlinear feature combinations like XOR) associated with low coverage. The method then adjusts prediction sets to guarantee adaptive equalized coverage for these discovered subgroups. Additionally, the paper introduces WSC+, a “nonlinear” worst-case conditional coverage metric extending the worst-slab coverage (WSC) metric of Cauchois et al. (2021)", "questions": "- Could you elaborate on how exactly the $T$ samples of $S$ (Algorithm 1, lines 12–16) are used to form the final prediction set $C(X_{N+1})$?\n\n\n- Under what assumptions does FAREG guarantee $P(Y \\in C(X) \\mid X \\in \\hat G) \\ge 1-\\alpha$ for the discovered group $\\hat G$? Is this guarantee exact finite-sample (with sample splitting) or only asymptotic/high-probability?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper tackles the important intersection of uncertainty quantification and algorithmic fairness. Ensuring no subgroup is underserved by predictive uncertainty is crucial for trustworthy AI. The work is timely and relevant to high-stakes domains. FAREG’s combination of representation learning with conformal prediction is novel. It significantly extends prior fair conformal methods (from single-feature groups to rich latent groups).", "weaknesses": "- The proposed algorithm is complex, involving a custom VAE training and Monte Carlo sampling of groups. Some steps (the PGD projection and the final aggregation of prediction sets) are not explained in depth in the main text. \n\n- FAREG focuses on one subgroup (or a mixture of one) to protect. If there are multiple distinct biased subgroups, it’s unclear if FAREG can handle them simultaneously.\n\n- some relevant baselines and related works are not mentioned. for instance  (https://arxiv.org/pdf/2505.16115) or (https://arxiv.org/abs/2305.12616)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2UwSbDxbKY", "reviewer": "Reviewer_hizj", "summary": "This paper proposes a framework for fair conformal inference in classification tasks. The method adaptively identifies subgroups and enforces conditional coverage guarantees on these learned groups. To evaluate subgroup fairness, the authors introduce a nonlinear variant of the Worst Slab Coverage (WSC) metric, designed to better capture coverage deficiencies in complex or non-linearly defined groups. Experiments are conducted on synthetic data and one real-world dataset.", "questions": "See weaknesses.\n\n- The paper focuses on **equalized coverage** as the fairness notion for conformal prediction. However, other fairness notions—such as those derived from popular ML fairness metrics—have been considered in related work ([3]). Does your method naturally extend to these alternative definitions, and if so, how?\n\nReferences\n\n[3] AT. Vadlamani et al: A Generic Framework for Conformal Fairness [ICLR 2025]", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The approach is **novel**: instead of enumerating or greedily constructing subgroups, the authors learn subgroup structure via representation learning—allowing for more complex group definitions (for instance, XOR-type interactions) that are hard to capture with feature-based heuristics.\n- It **improves over the baseline AFCP** in terms of achieving fairer conditional coverage, with only a modest reduction in efficiency (prediction set size). The substantial runtime improvement makes it a much more practical alternative.\n- The **methodology is theoretically sound**, supported by clear formulations and proofs that establish its coverage guarantees.", "weaknesses": "- The **empirical evaluation is limited**, with most experiments conducted on synthetic data and only a single real-world dataset (Nursery). Including larger and more commonly used datasets—such as the *Folktables* benchmarks used in prior fairness/conditional conformal prediction work ([1]–[3])—would strengthen the experimental evidence.\n- The paper does not discuss the **sensitivity of the hyperparameter β** in the final loss function, which may affect the fairness–efficiency trade-off.\n- A few parts of the **writing could be polished for clarity**, including the caption for Figure 2/Table 1 and the paragraph starting at line 405.\n\nReferences\n\n[1] O. Bastani et al: Practical adversarial multivalid conformal prediction [NeurIPS 2022]\n\n[2] C. Jung et al: Batch Multivalid Conformal Prediction [ICLR 2023]\n\n[3] AT. Vadlamani et al: A Generic Framework for Conformal Fairness [ICLR 2025]", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)