Counterfactually Fair Conformal Prediction

AI summary

Overview

• Research area: Fair machine learning, uncertainty quantification, and conformal prediction (distribution-free prediction sets with coverage guarantees).
• Technical level: Advanced. The paper combines structural causal models (SCMs), counterfactual fairness definitions, and split conformal prediction theory with proofs in the appendices.
• Scope: The paper defines counterfactual fairness for set-valued predictors and proposes Counterfactually Fair Conformal Prediction (CF-CP), a training-free procedure that symmetrizes conformity scores across protected-attribute interventions, with proofs of marginal coverage and set-level counterfactual fairness plus experiments on synthetic and real regression and classification datasets.

What This Paper Is About

Conformal prediction produces prediction sets that contain the true label with a target probability 1−α, but those sets are not inherently fair: they can differ across factual and counterfactual values of a protected attribute such as gender or race. Existing work on fair prediction sets targets group-level criteria, so this paper asks whether an individual-level notion, counterfactual fairness, can be enforced on prediction sets. The goal is a simple, post-training method that makes prediction sets counterfactually fair while keeping the standard marginal coverage guarantee.

Key Contributions

1. The paper extends counterfactual fairness from point predictors to set-valued predictors, defining "set-level counterfactual fairness" as invariance of the probability that any label y is included in the set under counterfactual interventions on the protected attribute A.
2. It proposes Counterfactually Fair Conformal Prediction (CF-CP), a post-training (training-free) split conformal procedure that aggregates conformity scores across protected-attribute interventions using a permutation-invariant operator (mean, max, or min).
3. It proves that under an invertible structural causal model (Assumption 4.1) plus exchangeability, CF-CP achieves both set-level counterfactual fairness (Lemma 4.1 and Corollary 4.1) and the standard split-CP marginal coverage guarantee (Theorem 4.1 and Corollary 4.2), even when the underlying point predictor is not counterfactually fair.
4. It empirically shows on synthetic and real datasets, across regression and classification, that CF-CP reduces counterfactual unfairness in prediction sets relative to standard split CP with only a modest increase in average set size.

Main Findings

• Standard split CP is not counterfactually fair. On synthetic regression at α = 0.1 the split CP baseline had Counterfactual Set Disparity (CSD) of 0.713 ± 0.009 and Total Effect (TE) of 1.219 ± 0.014; on synthetic classification (K = 10 classes) CSD was 0.642 ± 0.043 and TE 0.543 ± 0.037.
• CF-CP drives CSD to zero. All three CF-CP aggregators achieved CSD = 0.000 ± 0.000 on the synthetic regression task and on the synthetic classification task (except CF-CP-max, which had CSD 0.038 ± 0.008 in classification), while retaining coverage close to the 1 − α = 0.9 target.
• Coverage is preserved with a modest set-size increase. On synthetic regression, CF-CP-mean had coverage 0.899 ± 0.010 with average set size 2.971 ± 0.050 versus 2.032 ± 0.038 for split CP; CF-CP-min had set size 2.897 ± 0.058 and CF-CP-max 3.275 ± 0.053.
• CF-CP avoids the overcoverage of post-hoc union. The post-hoc union baseline also obtained CSD = 0.000 but over-covered (0.944 ± 0.005 on synthetic regression, 0.936 ± 0.010 on synthetic classification, 0.944 ± 0.007 on Law School, 0.978 ± 0.002 on Bios) and produced larger sets (3.251 ± 0.043, 3.123 ± 0.255, 3.570 ± 0.078, and 3.884 ± 0.227 respectively).
• CF-CP keeps the base predictor's accuracy, unlike retraining baselines. On synthetic regression, CF-CP variants kept MSE at 0.377 ± 0.012, the same as split CP, while counterfactually fair retraining approaches degraded it: CFU 1.112 ± 0.017, CFR 0.832 ± 0.014, PCF 0.826 ± 0.013. On synthetic classification, CF-CP kept accuracy 0.730 ± 0.011 versus 0.589 ± 0.017 (CFU and CFR) and 0.571 ± 0.017 (PCF).
• Law School regression (α = 0.1). Split CP had MSE 0.758 ± 0.005, coverage 0.898 ± 0.009, set size 2.847 ± 0.070, CSD 0.405 ± 0.010; CF-CP variants had the same MSE 0.758 ± 0.005, coverage 0.900 ± 0.013, set size 3.106 ± 0.100, and CSD 0.000 ± 0.000, versus retraining approaches with MSE 0.829 ± 0.007 (CFU), 0.827 ± 0.007 (CFR), and 0.828 ± 0.007 (PCF).
• Bias in Bios classification (α = 0.025). Split CP had accuracy 0.801 ± 0.001, coverage 0.975 ± 0.003, set size 3.311 ± 0.199, and CSD 0.199 ± 0.005; CF-CP-mean reached CSD 0.000 with accuracy 0.801 ± 0.001, coverage 0.974 ± 0.003, and set size 3.486 ± 0.191. CF-CP-max had coverage 0.975 ± 0.003 and set size 3.700 ± 0.208; CF-CP-min had coverage 0.974 ± 0.003 and set size 3.508 ± 0.199. The CFU baseline was not reported ("-") for this dataset.
• Aggregator choice matters. The paper states that max leads to larger calibration thresholds but test-time intersections of per-intervention sets, min leads to smaller thresholds but test-time unions, and mean is a compromise in both phases; empirically mean and min produced smaller sets than max.
• Counterfactual estimation noise is studied. The paper reports a separate table (Table 3) for results with noisy estimation of counterfactuals, where bold and underlined values mark the best and second-best CSD; the numerical contents of that table are not available in the provided excerpt.

Methodology in Plain English

The starting point is split conformal prediction: a pre-trained predictor produces a "conformity score" for each candidate label, scores are computed on a held-out calibration set, and a quantile of those scores becomes the threshold that defines the prediction set at test time.

CF-CP changes only the scoring function. For a given instance, the method imagines intervening on the protected attribute to each possible value a′ in the finite set A, produces the corresponding counterfactual features, and computes the conformity score for each intervention. These per-intervention scores are then combined with a symmetric, permutation-invariant aggregator (mean, max, or min) into a single counterfactually fair score. Standard split conformal prediction then runs on this aggregated score, so the same machinery and the same finite-sample quantile correction apply.

The theoretical argument rests on Assumption 4.1: the mapping from exogenous variables U to features X is invertible for each fixed value of A, and U is independent of A. Under invertibility, the factual features plus the factual A recover U, so the whole multiset of counterfactual features depends only on U, not on the factual value of A. Combined with permutation invariance of the aggregator, this makes the symmetrized score identical across interventions (Lemma 4.1), which makes the prediction sets identical across interventions (Corollary 4.1). Because the symmetrized score is a measurable, coordinate-wise transformation of exchangeable tuples, the exchangeability needed for the conformal coverage proof is retained (Theorem 4.1), so coverage ≥ 1 − α still holds (Corollary 4.2).

The method is training-free: it does not retrain the model, does not restrict features to non-descendants of A, does not impose invariance penalties, and does not require the distribution Pr(A). The extra computational cost is a factor of O(|A|) relative to standard split CP.

Experiments use a linear model as the base predictor for both regression and classification. Score functions are the absolute residual for regression and the Least Ambiguous Classifier (LAC) score, 1 − f̂_y(x, a), for classification. Datasets are a synthetic nonlinear SCM with binary A for regression (adopted from Zuo et al., 2023), a multi-class synthetic SCM with K = 10 classes inspired by Zhou et al., 2024b, Law School regression (predict first-year average from LSAT, UGPA, race, and gender, with race as the binary protected attribute; counterfactuals via a LiNGAM-based fitted SCM), and Bias in Bios classification (predict profession among 28 classes from biography text, with binary gender as A; counterfactuals from BERT embeddings decomposed into an A-aligned and an A-independent component). Metrics are MSE/Accuracy, Total Effect (TE) of the base predictor, empirical coverage, average set size, and Counterfactual Set Disparity (CSD), the latter based on Jaccard distance between factual and counterfactual sets (0 means identical sets, 1 means non-overlapping). Results are averaged over 10 random train/calibration/test splits, reported as mean ± standard deviation. Except for Bios, α = 0.1 is used; Bios uses α = 0.025 because α = 0.1 leads to near-singleton sets given the base predictor's high accuracy. For classification, empty prediction sets are filled with the highest-probability label. Code is available at github.com/guldoganozgur/cf_cp.

Why This Matters

• Research impact: The paper opens a line of work on individual-level fairness for prediction sets, complementing the existing group-level notions (demographic parity, equalized coverage) used in fair conformal prediction, and it connects counterfactual fairness with uncertainty quantification.
• Healthcare: The paper motivates the setting with laboratory medicine, where a patient's recommended treatment should not be systematically influenced by protected attributes; counterfactually fair sets would be identical whether a protected attribute were flipped.
• Education and testing: The paper's own example is an SAT score prediction set that should be identical for a student whether or not their gender is intervened upon.
• Criminal justice and other high-stakes decisions: The paper cites criminal justice alongside healthcare and test score estimation as applications where quantifying and mitigating bias is crucial.
• Decision-making under uncertainty: The paper cites prior work showing that conformal prediction sets improve decision quality in high-stakes tasks, and cites human-subject studies suggesting that enforcing equalized coverage can inadvertently increase disparate impact, which motivates alternative fairness notions.
• Industry relevance: The method is training-free, requires no access to Pr(A), and adds only an O(|A|) factor, which makes it practical when retraining a fair model is infeasible—relevant to insurers and other regulated industries (the authors are affiliated with Munich RE).

Future Directions

• Relaxing the invertibility assumption: Assumption 4.1 is described as strong though commonly used; the paper states that approximate counterfactual fairness is still achievable without it and demonstrates this empirically, leaving a formal treatment of approximate guarantees open.
• Noisy counterfactual estimation: The paper reports a separate experiment (Table 3) on imperfect counterfactuals, and the reported highlighting convention there focuses on CSD rather than the coverage-versus-size tradeoff, suggesting more work is needed on how fairness degrades under estimation error.
• High-cardinality protected attributes: Because the overhead is O(|A|) relative to split CP and the paper assumes A is finite, scaling to larger or continuous protected attributes is a natural question.
• Choosing and analyzing aggregators: The paper compares mean, max, and min and notes that more complex permutation-invariant aggregators are possible; principled selection criteria relating aggregator choice to set size, coverage tightness, and fairness remain open.

Target Audience

Researchers and practitioners in fair machine learning, conformal prediction, and uncertainty quantification, particularly those working on individual-level fairness notions and on causal methods for prediction sets. It also suits applied data scientists and risk or actuarial modelers in regulated sectors (healthcare, insurance, education, criminal justice) who need coverage-valid prediction sets that do not change when a protected attribute is counterfactually altered, and who cannot or do not want to retrain their underlying model. Readers should be comfortable with split conformal prediction, structural causal models, and basic quantile-based coverage arguments.

Authors’ abstract

While counterfactual fairness of point predictors is well studied, its extension to prediction sets--central to fair decision-making under uncertainty--remains underexplored. On the other hand, conformal prediction (CP) provides efficient, distribution-free, finite-sample valid prediction sets, yet does not ensure counterfactual fairness. We close this gap by developing Counterfactually Fair Conformal Prediction (CF-CP) that produces counterfactually fair prediction sets. Through symmetrization of conformity scores across protected-attribute interventions, we prove that CF-CP results in counterfactually fair prediction sets while maintaining the marginal coverage property. Furthermore, we empirically demonstrate that on both synthetic and real datasets, across regression and classification tasks, CF-CP achieves the desired counterfactual fairness and meets the target coverage rate with minimal increase in prediction set size. CF-CP offers a simple, training-free route to counterfactually fair uncertainty quantification.