Fairness Invariants: A Relational Approach to Explaining and Mitigating Fairness Bugs

Ranit Debnath Akash; Ashish Kumar; Gang Tan; Saeid Tizpaz-Niari

cs.SEAug 26, 2026

Fairness Invariants: A Relational Approach to Explaining and Mitigating Fairness Bugs

Authors: Ranit Debnath Akash, Ashish Kumar, Gang Tan, Saeid Tizpaz-Niari

Organizations: University of Illinois at Chicago, Chicago, USA · Pennsylvania State University, University Park, USA

Abstract

Data-driven software systems are increasingly deployed in high-stakes socio-economic domains, from criminal justice to financial lending. However, these systems often exhibit individual discrimination---unjustified disparities in which a program yields different outcomes for similar individuals who differ only in their protected attributes (e.g., race, gender, age). While existing research has focused on detecting and quantifying these bugs, there remains a critical lack of principled mechanisms to explain and localize individual fairness bugs. Current explanation techniques are largely designed for single-input decisions rather than the relational nature of discrimination, which inherently involves a comparison between an original and a counterfactual pair. We present REMI, a framework for the automated localization, explanation, and mitigation of individual discrimination. Inspired by loop-invariant synthesis in formal methods, we treat counterfactual fairness as a relational invariant discovery problem. We introduce a bidirectional relational explanation framework that learns over paired examples $(x, x')$ to identify regions of the input space where fairness is violated. Unlike traditional one-way implication pairs used in invariant inference, our approach enforces bidirectional constraints: requiring identical outcomes for both original and counterfactual samples. REMI utilizes three data-alignment techniques to infer interpretable rule-based models that act as "fairness invariants." These rules serve as guardrails to selectively block or relabel unfair predictions without requiring model retraining. Our evaluation on symbolic and neural network programs demonstrates that REMI localizes ground-truth fairness bugs in over 83% of cases, significantly outperforming state-of-the-art baselines and reducing discriminatory decisions in black-box models by up to 70%.

Figures & tables

DPuT	Dataset	Prot. Feat	#Inst.	#Feat.	Source
Pg1	( Albarghouthi et al., 2017 )	ethnicity	30000	4	( Albarghouthi et al., 2017 )
Pg2	( ProPublica, 2021 ; Zhong et al., 2023 ; Larson et al., 2016 )	sex	6908	4	( Rudin, 2019 )
Pg3	( Albarghouthi et al., 2017 )	ethnicity	30000	4	( Zhang et al., 2022 )
Pg4	( Albarghouthi et al., 2017 )	ethnicity	30000	4	( Zhang et al., 2022 )
Pg5	( ProPublica, 2021 ; Zhong et al., 2023 ; Larson et al., 2016 )	age	6908	4	( Rudin and Ustun, 2018 )
Pg6	( ProPublica, 2021 ; Zhong et al., 2023 ; Larson et al., 2016 )	age	6908	5	( Rudin and Ustun, 2018 )

Table 1. The dataset and benchmark (symbolic DPuT, left; DNN, right).

Prog	Appr	Depth	Acc	Prec	Rec	F1	ROC AUC	$T_{Train}$	$\#IDI_{Loc}$
Pg1 (SMB)	most-freq	NA	0.92 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	0.5 ( $\pm$ 0.0)	NA	0.0 ( $\pm$ 0.0)
	AFT ( Zhao et al., 2024 )	11.2 ( $\pm$ 1.14)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0.32 ( $\pm$ 0.02)	0.0 ( $\pm$ 0.0)
	DCNE	18.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0.38 ( $\pm$ 0.01)	2233.5 ( $\pm$ 1.18)
	DCVE	30.0 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.95 ( $\pm$ 0.0)	0.96 ( $\pm$ 0.0)	0.95 ( $\pm$ 0.0)	0.98 ( $\pm$ 0.0)	4.17 ( $\pm$ 0.05)	4329.6 ( $\pm$ 2.32)
	DCHE	17.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0.37 ( $\pm$ 0.01)	2231.5 ( $\pm$ 1.65)
Pg2 (SMB)	most-freq	NA	0.97 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	0.5 ( $\pm$ 0.0)	NA	0.0 ( $\pm$ 0.0)

Table 2. Comparison between different data pre-processing training approaches

Prog	Mod	Acc	Prec	Rec	F1	ROC AUC	$T_{Tr}$	$\#ID_{Loc}$
Pg1 SMB	CART	1.0 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0.38 ( $\pm$ 0.01)	2233.5 ( $\pm$ 1.18)
	GBC	1.0 ( $\pm$ 0.0)	0.98 ( $\pm$ 0.0)	0.98 ( $\pm$ 0.0)	0.98 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.89 ( $\pm$ 0.02)	2196.1 ( $\pm$ 9.52)
	XGBoost	1.0 ( $\pm$ 0.0)	0.98 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.98 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.15 ( $\pm$ 0.19)	2233.0 ( $\pm$ 0.0)
	RuleFit	0.98 ( $\pm$ 0.0)	0.93 ( $\pm$ 0.01)	0.8 ( $\pm$ 0.01)	0.86 ( $\pm$ 0.01)	0.9 ( $\pm$ 0.01)	64.75 ( $\pm$ 1.45)	1807.7 ( $\pm$ 27.51)
	FIGS	0.95 ( $\pm$ 0.01)	0.61 ( $\pm$ 0.06)	0.84 ( $\pm$ 0.05)	0.7 ( $\pm$ 0.03)	0.9 ( $\pm$ 0.02)	0.61 ( $\pm$ 0.01)	1898.8 ( $\pm$ 110.81)
	C4.5Tree	1.0 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	0.99 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	20.36 ( $\pm$ 1.33)	2232.0 ( $\pm$ 4.06)

Table 3. Comparison among different interpretable models with training approach with relational dataset.

Prog	Appr	Depth	$Rule.Len$	Imp	Conf	Tot.Disc.Cov	Tot. $\#IDI_{Loc}$	Bst.Lf.Rule.Len	Bst.Lf.Disc.Cov	Bst.Lf.Conf	Bst.Lf. $\#IDI_{Loc}$
Pg1 SMB	DCNE	18.0 ( $\pm$ 0.0)	11.56 ( $\pm$ 2.77)	0.0 ( $\pm$ 0.0)	0.97 ( $\pm$ 0.09)	0.98 ( $\pm$ 0.0)	2233.5 ( $\pm$ 1.18)	16.0 ( $\pm$ 0.0)	0.13 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	301.0 ( $\pm$ 0.0)
	DCHE	17.0 ( $\pm$ 0.0)	10.67 ( $\pm$ 2.69)	0.0 ( $\pm$ 0.0)	0.98 ( $\pm$ 0.09)	0.98 ( $\pm$ 0.0)	2231.5 ( $\pm$ 1.65)	15.0 ( $\pm$ 0.0)	0.13 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	301.0 ( $\pm$ 0.0)
	AFT ( Zhao et al., 2024 )	11.0 ( $\pm$ 0.0)	7.23 ( $\pm$ 1.79)	0.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	3.4 ( $\pm$ 0.52)	0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	0 ( $\pm$ 0.0)
Pg2 SMB	DCNE	2.0 ( $\pm$ 0.0)	2.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	206.0 ( $\pm$ 0.0)	2.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	206.0 ( $\pm$ 0.0)
	DCHE	2.0 ( $\pm$ 0.0)	2.0 ( $\pm$ 0.0)	0.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	206.0 ( $\pm$ 0.0)	2.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	206.0 ( $\pm$ 0.0)
	AFT ( Zhao et al., 2024 )	4.0 ( $\pm$ 0.0)	2.67 ( $\pm$ 1.53)	0.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	100.0 ( $\pm$ 0.0)	4 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	1.0 ( $\pm$ 0.0)	100.0 ( $\pm$ 0.0)

Table 4. Comparison between the strength of the extracted rules of using proposed relational dataset (RQ3)

Prog	Appr	Acc	Prec	Rec	F1	ROC AUC	$\#IDI$	$\#FP_{IDI}$
Pg1 SMB	Ini. Pg	1.00	1.00	1.00	1.00	1.00	2250	-
	DT w IDI	0.99	0.99	0.99	0.99	0.99	2430	-
	Ini.Pg + Remi	1.00	1.00	1.00	1.00	1.00	2	2670
Pg2 SMB	Init. Pg	1.00	1.00	1.00	1.00	1.00	206	-
	DT w IDI	1.00	1.00	1.00	1.00	1.00	206	-
	Ini.Pg + Remi	1.00	1.00	1.00	1.00	1.00	0	0

Table 5. Comparing performance during Mitigation

Model	Depth	$Rule.Len$	$Tot.Rules$	Imp	Conf	Tot.Disc.Cov	Tot. $\#IDI_{Loc}$	Bst.Lf.Rule.Len	Bst.Lf.Disc.Cov	Bst.Lf.Conf	Bst.Lf. $\#IDI_{Loc}$
AC1	35.0 ( $\pm$ 0.0)	18.77 ( $\pm$ 7.08)	449	0.1 ( $\pm$ 0.17)	0.85 ( $\pm$ 0.18)	0.69	11496	4	0.5	1.0	7793
AC2	24.0 ( $\pm$ 0.0)	14.17 ( $\pm$ 3.98)	467	0.12 ( $\pm$ 0.18)	0.85 ( $\pm$ 0.18)	0.77	15583	7	0.43	1.0	8287
AC3	29.0 ( $\pm$ 0.0)	15.54 ( $\pm$ 4.73)	439	0.11 ( $\pm$ 0.18)	0.83 ( $\pm$ 0.19)	0.78	20531	5	0.66	1.0	16291
AC4	24.0 ( $\pm$ 0.0)	14.45 ( $\pm$ 3.91)	436	0.09 ( $\pm$ 0.16)	0.87 ( $\pm$ 0.17)	0.7	13864	2	0.58	1.0	10738
AC5	30.0 ( $\pm$ 0.0)	15.47 ( $\pm$ 4.51)	464	0.11 ( $\pm$ 0.18)	0.85 ( $\pm$ 0.19)	0.76	18223	5	0.64	1.0	14384
AC6	30.0 ( $\pm$ 0.0)	16.35 ( $\pm$ 4.83)	455	0.1 ( $\pm$ 0.17)	0.85 ( $\pm$ 0.19)	0.53	5333	2	0.23	1.0	2215

Table 6. DNN rule extraction results using ExpGA ( Fan et al., 2022 ) as the IDI source under DCNE curation strategy (RQ5).

Model Mitigation Acc F1

\#\text{IDI}_{\text{bef}}

\#\text{IDI}_{\text{aft}}

Red. (%)

\#FP_{IDI}

AC1 Themis ( Angell et al., 2018 ) 0.85 0.66 7,173 7,571 -5.55 – Remi 0.85 0.64 7,173 4,111 42.69 1,323 Themis ( Angell et al., 2018 ) + Remi 0.85 0.66 7,571 4,370 42.28 1,208 ExpGA ( Fan et al., 2022 ) 0.84 0.61 26,647 15,687 41.13 – Remi 0.85 0.64 26,647 4,234 84.11 1,187 ExpGA ( Fan et al., 2022 ) + Remi 0.84 0.61 15,687 4,191 73.28 1,310 LIMI ( Xiao et al., 2023 ) 0.85 0.65 38,049 13,338 64.95 – Remi 0.85 0.64 38,049 4,294 87.84 1,901 LIMI ( Xiao et al., 2023 ) + Remi 0.85 0.65 13,338 4,515 66.15 1,468 AC2 Themis ( Angell et al., 2018 ) 0.84 0.60 7,532 7,891 -4.77 – Remi 0.85 0.61 7,532 4,140 45.03 1,309 Themis ( Angell et al., 2018 ) + Remi 0.84 0.60 7,891 4,236 46.32 1,259 ExpGA ( Fan et al., 2022 ) 0.77 0.65 27,002 19,148 29.09 – Remi 0.85 0.61 27,002 4,101 84.81 1,377 ExpGA ( Fan et al., 2022 ) + Remi 0.77 0.65 19,148 3,565 81.38 2,497 LIMI ( Xiao et al., 2023 ) 0.82 0.42 29,132 16,940 41.85 – Remi 0.85 0.61 29,132 3,838 86.83 2,179 LIMI ( Xiao et al., 2023 ) + Remi 0.82 0.42 16,940 3,922 76.85 1,999 AC3 Themis ( Angell et al., 2018 ) 0.85 0.64 7,525 7,094 5.73 – Remi 0.85 0.66 7,525 4,290 42.99 1,244 Themis ( Angell et al., 2018 ) + Remi 0.85 0.64 7,094 4,754 32.99 988 ExpGA ( Fan et al., 2022 ) 0.84 0.62 20,481 24,652 -20.37 – Remi 0.85 0.66 20,481 4,235 79.32 1,317 ExpGA ( Fan et al., 2022 ) + Remi 0.84 0.62 24,652 4,121 83.28 1,495 LIMI ( Xiao et al., 2023 ) 0.85 0.64 46,081 11,014 76.10 – Remi 0.85 0.66 46,081 4,233 90.81 2,478 LIMI ( Xiao et al., 2023 ) + Remi 0.85 0.64 11,014 4,120 62.59 1,749 AC4 Themis ( Angell et al., 2018 ) 0.84 0.65 7,491 7,999 -6.78 – Remi 0.85 0.62 7,491 3,957 47.18 1,512 Themis ( Angell et al., 2018 ) + Remi 0.84 0.65 7,999 4,151 48.11 1,363 ExpGA ( Fan et al., 2022 ) 0.84 0.66 21,503 18,465 14.13 – Remi 0.85 0.62 21,503 4,094 80.96 1,420 ExpGA ( Fan et al., 2022 ) + Remi 0.84 0.66 18,465 4,601 75.08 1,096 LIMI ( Xiao et al., 2023 ) 0.83 0.67 38,043 34,463 9.41 – Remi 0.85 0.62 38,043 3,683 90.32 2,480 LIMI ( Xiao et al., 2023 ) + Remi 0.83 0.67 34,463 4,142 87.98 3,008 AC5 Themis ( Angell et al., 2018 ) 0.84 0.65 7,206 7,202 0.06 – Remi 0.85 0.66 7,206 4,054 43.74 1,358 Themis ( Angell et al., 2018 ) + Remi 0.84 0.65 7,202 4,331 39.86 1,229 ExpGA ( Fan et al., 2022 ) 0.83 0.62 21,798 22,543 -3.42 – Remi 0.85 0.66 21,798 4,293 80.31 1,140 ExpGA ( Fan et al., 2022 ) + Remi 0.83 0.62 22,543 4,320 80.84 1,518 LIMI ( Xiao et al., 2023 ) 0.82 0.66 41,114 21,810 46.95 – Remi 0.85 0.66 41,114 4,066 90.11 2,433 LIMI ( Xiao et al., 2023 ) + Remi 0.82 0.66 21,810 4,244 80.54 2,351 AC6 Themis ( Angell et al., 2018 ) 0.84 0.67 7,559 10,522 -39.20 – Remi 0.85 0.61 7,559 3,851 49.05 1,666 Themis ( Angell et al., 2018 ) + Remi 0.84 0.67 10,522 3,042 71.09 2,495 ExpGA ( Fan et al., 2022 ) 0.85 0.63 25,959 9,502 63.40 – Remi 0.85 0.61 25,959 3,803 85.35 1,665 ExpGA ( Fan et al., 2022 ) + Remi 0.85 0.63 9,502 4,169 56.13 1,249 LIMI ( Xiao et al., 2023 ) 0.85 0.67 34,822 15,302 56.06 – Remi 0.85 0.61 34,822 3,854 88.93 2,206 LIMI ( Xiao et al., 2023 ) + Remi 0.85 0.67 15,302 4,338 71.65 1,854 BM1 Themis ( Angell et al., 2018 ) 0.88 0.00 3,136 3,788 -20.79 – Remi 0.89 0.48 3,136 1,076 65.69 479 Themis ( Angell et al., 2018 ) + Remi 0.88 0.00 3,788 1,161 69.35 499 BM2 Themis ( Angell et al., 2018 ) 0.88 0.00 3,291 3,638 -10.54 – Remi 0.89 0.54 3,291 1,063 67.70 489 Themis ( Angell et al., 2018 ) + Remi 0.88 0.00 3,638 1,073 70.51 512 BM3 Themis ( Angell et al., 2018 ) 0.88 0.00 3,506 3,573 -1.91 – Remi 0.88 0.58 3,506 1,082 69.14 513 Themis ( Angell et al., 2018 ) + Remi 0.88 0.00 3,573 1,076 69.89 513 BM4 Themis ( Angell et al., 2018 ) 0.23 0.23 3,121 3,445 -10.38 – Remi 0.90 0.53 3,121 1,060 66.04 470 Themis ( Angell et al., 2018 ) + Remi 0.23 0.23 3,445 1,034 69.99 486

Model Mitigation Acc F1

\#\text{IDI}_{\text{bef}}

\#\text{IDI}_{\text{aft}}

Red. (%)

\#FP_{IDI}

AC7 Themis ( Angell et al., 2018 ) 0.84 0.68 7,445 8,140 -9.34 – Remi 0.85 0.64 7,445 4,058 45.49 1,437 Themis ( Angell et al., 2018 ) + Remi 0.84 0.68 8,140 3,996 50.91 1,826 ExpGA ( Fan et al., 2022 ) 0.76 0.00 23,326 12,311 47.22 – Remi 0.85 0.64 23,326 4,105 82.40 1,425 ExpGA ( Fan et al., 2022 ) + Remi 0.76 0.00 12,311 3,369 72.63 1,842 LIMI ( Xiao et al., 2023 ) 0.76 0.00 37,705 11,208 70.27 – Remi 0.85 0.64 37,705 4,001 89.39 2,419 LIMI ( Xiao et al., 2023 ) + Remi 0.76 0.00 11,208 3,094 72.39 2,112 AC8 Themis ( Angell et al., 2018 ) 0.84 0.56 7,566 7,689 -1.63 – Remi 0.83 0.66 7,566 4,302 43.14 1,277 Themis ( Angell et al., 2018 ) + Remi 0.84 0.56 7,689 3,927 48.93 1,645 ExpGA ( Fan et al., 2022 ) 0.84 0.64 20,053 11,306 43.62 – Remi 0.83 0.66 20,053 4,411 78.00 1,093 ExpGA ( Fan et al., 2022 ) + Remi 0.84 0.64 11,306 4,075 63.96 1,451 LIMI ( Xiao et al., 2023 ) 0.85 0.67 24,386 17,034 30.15 – Remi 0.83 0.66 24,386 4,188 82.83 2,346 LIMI ( Xiao et al., 2023 ) + Remi 0.85 0.67 17,034 4,362 74.39 1,733 AC9 Themis ( Angell et al., 2018 ) 0.84 0.68 8,348 8,260 1.05 – Remi 0.83 0.56 8,348 3,642 56.37 1,927 Themis ( Angell et al., 2018 ) + Remi 0.84 0.68 8,260 3,691 55.31 1,980 ExpGA ( Fan et al., 2022 ) 0.84 0.65 20,006 8,120 59.41 – Remi 0.83 0.56 20,006 3,776 81.13 1,727 ExpGA ( Fan et al., 2022 ) + Remi 0.84 0.65 8,120 4,391 45.92 1,168 LIMI ( Xiao et al., 2023 ) 0.83 0.58 51,399 22,330 56.56 – Remi 0.83 0.56 51,399 3,696 92.81 2,379 LIMI ( Xiao et al., 2023 ) + Remi 0.83 0.58 22,330 4,160 81.37 2,054 AC10 Themis ( Angell et al., 2018 ) 0.85 0.63 7,509 7,250 3.45 – Remi 0.78 0.33 7,509 4,357 41.98 1,164 Themis ( Angell et al., 2018 ) + Remi 0.85 0.63 7,250 4,129 43.05 1,339 ExpGA ( Fan et al., 2022 ) 0.84 0.57 28,342 27,314 3.63 – Remi 0.85 0.66 28,342 4,220 85.11 1,218 ExpGA ( Fan et al., 2022 ) + Remi 0.84 0.57 27,314 3,610 86.78 1,803 LIMI ( Xiao et al., 2023 ) 0.83 0.65 42,942 21,551 49.81 – Remi 0.85 0.66 42,942 4,141 90.36 2,175 LIMI ( Xiao et al., 2023 ) + Remi 0.83 0.65 21,551 4,512 79.06 1,932 AC11 Themis ( Angell et al., 2018 ) 0.84 0.62 7,808 7,481 4.19 – Remi 0.81 0.67 7,808 4,529 42.00 1,171 Themis ( Angell et al., 2018 ) + Remi 0.84 0.62 7,481 3,957 47.11 1,596 ExpGA ( Fan et al., 2022 ) 0.80 0.63 16,445 24,718 -50.31 – Remi 0.81 0.67 16,445 4,746 71.14 931 ExpGA ( Fan et al., 2022 ) + Remi 0.80 0.63 24,718 3,739 84.87 1,844 LIMI ( Xiao et al., 2023 ) 0.76 0.00 65,598 11,209 82.91 – Remi 0.81 0.67 65,598 3,677 94.39 4,723 LIMI ( Xiao et al., 2023 ) + Remi 0.76 0.00 11,209 3,264 70.88 1,968 AC12 Themis ( Angell et al., 2018 ) 0.76 0.00 7,667 11,208 -46.18 – Remi 0.84 0.65 7,667 3,972 48.19 1,580 Themis ( Angell et al., 2018 ) + Remi 0.76 0.00 11,208 3,092 72.41 2,115 ExpGA ( Fan et al., 2022 ) 0.83 0.61 23,401 18,645 20.32 – Remi 0.84 0.65 23,401 4,209 82.01 1,432 ExpGA ( Fan et al., 2022 ) + Remi 0.83 0.61 18,645 3,820 79.51 1,642 LIMI ( Xiao et al., 2023 ) 0.76 0.00 74,169 11,208 84.89 – Remi 0.84 0.65 74,169 3,927 94.71 2,898 LIMI ( Xiao et al., 2023 ) + Remi 0.76 0.00 11,208 3,086 72.47 2,120 BM5 Themis ( Angell et al., 2018 ) 0.15 0.21 3,288 3,862 -17.46 – Remi 0.89 0.58 3,288 1,028 68.73 582 Themis ( Angell et al., 2018 ) + Remi 0.15 0.21 3,862 908 76.49 578 BM6 Themis ( Angell et al., 2018 ) 0.87 0.01 3,175 3,862 -21.64 – Remi 0.89 0.53 3,175 1,232 61.20 361 Themis ( Angell et al., 2018 ) + Remi 0.87 0.01 3,862 1,032 73.28 572 BM7 Themis ( Angell et al., 2018 ) 0.57 0.27 3,244 3,692 -13.81 – Remi 0.89 0.56 3,244 1,074 66.89 471 Themis ( Angell et al., 2018 ) + Remi 0.57 0.27 3,692 1,058 71.34 516 BM8 Themis ( Angell et al., 2018 ) 0.81 0.09 3,244 3,859 -18.96 – Remi 0.89 0.43 3,244 1,074 66.89 471 Themis ( Angell et al., 2018 ) + Remi 0.81 0.09 3,859 1,006 73.93 528

Table 7. Comparison of mitigation techniques using IDIs generated by black-box DNN fairness testing tools.

Algorithmic Fairness

Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.

See all 420 papers

Do Fair Models Reason Fairly? Counterfactual Explanation Consistency for Procedural Fairness in Credit Decisions
May 12, 2026Gideon Popoola, John SheppardFeature Attribution Counterfactual Explanations
Gianforte School of Computing Montana State University Bozeman, MT, USA, 59715
Procedural Fairness via Group Counterfactual Explanation
Mar 11, 2026Gideon Popoola, John SheppardAlgorithmic Fairness Group Fairness
Gianforte School of Computing, Montana State University, Bozeman, MT, USA
FairLint-DL: An IDE-Native Tool for Fairness Debugging of Deep Learning Software
Sep 14, 2026Archit Rathod, Saeid Tizpaz-NiariAlgorithmic Fairness
University of Illinois at Chicago Chicago, USA

May 12, 2026J/K move · Enter open · S save

Do Fair Models Reason Fairly? Counterfactual Explanation Consistency for Procedural Fairness in Credit Decisions

Gideon Popoola, John Sheppard

Gianforte School of Computing Montana State University Bozeman, MT, USA, 59715

Feature Attribution Counterfactual Explanations Algorithmic Fairness Credit Scoring

Open paper AskPDF arXiv

Machine learning algorithms in socially sensitive domains (e.g., credit decisions) often focus on equalizing predictive outcomes. However, satisfying these metrics does not guarantee that models use the same reasoning for different groups. We show that existing outcome-fair models can still apply fundamentally different reasoning to individuals, a

hidden procedural bias'' missed by standard fairness metrics and algorithms. We propose Counterfactual Explanation Consistency (CEC), a framework that detects and mitigates this bias by aligning feature attributions between individuals and their counterfactual counterparts. Key contributions include a nearest-neighbor counterfactual generation method, a modified baseline for integrated gradient comparisons, an individual-level procedural fairness metric, and a corresponding training loss. We introduce a taxonomy identifying

Regime B'' (same outcome, different reasoning) as a critical blind spot. Experiments on synthetic data, German Credit, Adult Income, and HMDA mortgage data demonstrate that outcome-fair baselines exhibit substantial hidden bias, while CEC substantially reduces it with modest utility cost.

Abstract

Algorithmic Fairness

Explore similar work

Do Fair Models Reason Fairly? Counterfactual Explanation Consistency for Procedural Fairness in Credit Decisions

Procedural Fairness via Group Counterfactual Explanation

FairLint-DL: An IDE-Native Tool for Fairness Debugging of Deep Learning Software