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

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

Source-linked AI summary

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

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

arXiv:2608.26209v1Aug 26, 2026cs.SEcs.AIcs.LG

TL;DR

Existing fairness explanations target single decisions, not the paired original-counterfactual comparisons needed to localize individual discrimination. REMI treats fairness as relational invariant discovery, learns interpretable rules from counterfactual pairs, and uses them as guardrails; across symbolic, scoring, and neural programs, it effectively outperforms state-of-the-art baselines.

Problem
Existing methods largely explain single-input decisions, while individual fairness requires explaining relational labels that compare original and counterfactual outcomes.
Method
REMI curates original-counterfactual pairs, learns interpretable rule-based fairness invariants, and applies them as guardrails to mitigate discriminatory predictions.
Results
Across symbolic, scoring, and deep neural network programs, REMI effectively localized discriminatory regions and outperformed state-of-the-art baselines.
Takeaways & Limitations
Extracted fairness invariants provide interpretable explanations and a real-time mitigation strategy for individual discrimination.
Takeaways & Limitations
For DNN benchmarks, incompletely known causal dependencies between features may make some generated counterfactuals invalid.

Abstract

from arXiv · show

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%.

1 Introduction

Fairness bugs arise when automated decision systems produce unjustified disparities between similarly qualified individuals who differ in protected attributes. REMI addresses the lack of relational explanations and effective mitigation by inferring fairness invariants and using them as guardrails for rule-based and neural programs.

Motivation: Automated decision systems used in high-stakes domains can encode and amplify historical biases involving protected attributes, making fairness a critical requirement.The cited domains include criminal justice, healthcare, financial lending, and hiring.
Problem: Fairness bugs are unjustified outcome disparities between individuals identical in relevant qualifications but different in a protected characteristic.The introduction gives higher FICO risk scores for black non-defaulters than white counterparts as an example.
Problem: Existing decision explanations address single inputs but cannot explain why similar individuals receive different outcomes or localize the relational logic causing the disparity.The missing capability is to analyze multiple similar inputs simultaneously, such as an original loan applicant and a counterfactual counterpart.
Problem: Without compact relational constraints characterizing counterfactual unfairness, developers have limited and ineffective mitigation strategies.The introduction identifies localization to specific relational constraints as necessary for mitigation.
Approach and Contributions: Inspired by loop-invariant synthesis, REMI infers fairness invariants from data and applies them through guardrails to detect, localize, explain, and mitigate individual fairness bugs.The framework is evaluated on rule-based symbolic programs and data-driven neural network programs, and its experiments compare relational curation techniques and rule inference algorithms.

2 Overview

REMI frames individual fairness as a relational property of original and counterfactual inputs differing only in protected attributes. It generates and labels such pairs, curates relational datasets, and learns interpretable rules describing discriminatory regions.

A. Counterfactual generation and finding discriminatory instances: Individual fairness is assessed relationally by comparing original and counterfactual inputs that differ only in protected attributes.A decision is discriminatory when the program produces different outcomes for the paired inputs.
A. Counterfactual generation and finding discriminatory instances: REMI generates counterfactual instances by changing protected attributes and labels pairs as unfair when the program’s outcomes differ.Agreeing outcomes receive a positive relational label, while differing outcomes receive a negative label.
B. Relational dataset construction and curation: DCNE retains the original point with its relational label, whereas DCVE adds the counterfactual as a separate instance sharing that label.DCVE therefore doubles the number of training instances.
C. Interpretable learning and rule extraction: The learner targets the relational label L(x,x′) using non-protected attributes, so extracted rules identify where the program is unfair.REMI instantiates the explainer with tree-based algorithms including CART, C4.5, TaoTree, RulesFit, and FIGS.
Overview Example: In the hiring example, ethnicity causally affects college rank, so REMI generates counterfactual applicants by changing ethnicity and adjusting affected attributes.The example uses 30,000 applicant samples and labels pairs whose hiring decision flips as unfair.

3 Relational Explanation and Mitigation Problem

This section formulates individual counterfactual fairness as a relational explanation problem over original–counterfactual pairs. It learns interpretable rules identifying disagreement regions and uses them as guardrails to withhold or relabel potentially discriminatory decisions.

Problem Setting: A DPuT maps individual inputs to binary decisions, while protected and non-protected attributes are distinguished because protected attributes should not affect outcomes.Non-protected attributes include factors such as income, age, or education; protected attributes include race or gender.
Fairness Definition: Individual counterfactual unfairness occurs when changing protected attributes, with logically dependent updates when necessary, flips the DPuT outcome.The original and counterfactual inputs are evaluated to compare their outcomes.
Relational Labeling: The relational dataset labels each original–counterfactual pair + when outcomes agree and − when they disagree, shifting explanation from f(x) to the relational label L(x,x′).The dataset contains original datapoints and their counterfactual counterparts, with relation R assigning fair or unfair labels to pairs.
Explanation: The explanation model E learns human-interpretable rules that characterize non-protected-attribute regions where the DPuT exhibits counterfactual unfairness.E is instantiated as a decision-tree-based binary classifier predicting agreement or disagreement labels.
Mitigation: The disagreement rules become guardrails: decisions are returned outside flagged regions, while flagged cases are withheld for human review or alternatively relabeled to restore pairwise consistency.The guarded function uses f(x) when the guardrail predicate is 0 and ⊥ when it is 1.

4 Approach

REMI treats counterfactual fairness as outcome invariance between original and protected-attribute-flipped inputs, using relational pairs to localize discriminatory regions. It curates these pairs into supervised datasets, trains interpretable rule models, and deploys extracted rules as guardrails that deny potentially discriminatory predictions.

4.1–4.4 Approach: REMI defines a region as fair when outcomes remain invariant under protected-attribute changes and uses an interpretable decision tree to characterize unfair regions.The tree captures feature interactions and extracts decision rules describing discriminatory input space.
4.1 Generating counterfactuals to detect IDIs: For each original instance, REMI generates a protected-attribute counterfactual, obtains both outcomes, and labels the pair as an individual discriminatory instance when outcomes change.The protected attribute is treated in a binary privileged-versus-unprivileged setting; unchanged outcomes form fair or agreement pairs.
4.2 Curating relational datasets: REMI converts relational data into supervised datasets using DCNE, DCVE, or DCHE curation operators that preserve fair-versus-discriminatory pair labels.DCNE retains only the original instance, DCVE treats both pair elements as separate rows, and DCHE merges both inputs into one row with differing features.
4.3 Training an interpretable model: REMI trains a complexity-constrained interpretable model, such as a decision tree, to classify fair versus unfair pairs and localize discriminatory feature interactions.Rule strength is assessed using impurity, Confidence_leaf, and Coverage_leaf; confidence measures the fraction of captured instances that are IDIs, while coverage measures the fraction of all IDIs captured.
4.4 Deploying rules as guardrails: Extracted discriminatory rules operate as guardrails: inputs matching a rule are withheld from the decision-making program and denied an output.This abstention mechanism avoids making decisions that could lead to discriminatory behavior without retraining the underlying program.

5 Experiments

REMI is evaluated on symbolic and black-box neural benchmarks using relational data curation, interpretable rule extraction, and guardrail mitigation. It outperforms localization baselines, identifies fairness invariants accurately, and substantially reduces discriminatory instances without retraining.

Benchmarks: REMI is evaluated on six symbolic DPuTs with known decision logic and 20 black-box DNNs spanning multiple benchmark datasets.The symbolic programs support ground-truth validation, while the DNNs assess generalization to black-box models.
RQ1: Data curation: Pair-alignment and decision-tree inference approaches outperform baselines in 80% of cases, with horizontal and no-extension alignments similarly effective.The evaluation prioritizes #IDI_Loc and precision because of class imbalance.
RQ2: Learner selection: C4.5, FIGS, and CART achieve top-tier fairness-invariant synthesis performance in 83% of benchmarks.Nine tree-based learners are evaluated; ensemble models such as XGB are less directly interpretable despite fast training.
RQ3: Invariant characteristics: Remi outperforms AFT in 83% of cases and identifies all discrimination regions in more than 66% of symbolic cases.For PG1, extracted trees achieve approximately 0.98 discriminatory coverage and localize about 2,233 IDIs, while AFT finds none.
RQ4: Mitigation: Rule-based guardrails reduce #IDI in 100% of mitigation cases.They reduce discriminatory instances from 2,250 to 2 in one case and from hundreds or thousands to 0 in four of six cases.
RQ5: DNN generalization: On DNNs, extracted rules have confidence of 0.83–0.88 and discrimination coverage of 41–84%, while mitigation reduces IDIs by at least 40% and up to 84%.Across Adult Census models, reductions are 42–56% for Themis IDIs, 71–85% for ExpGA-based IDIs, and 87–95% for LIMI-based IDIs; BM reductions are around 61–69%.

6 Discussions

The discussion reports Remi’s runtime and evaluation scope while identifying limitations in semantic validity, scalability, and ground-truth availability. It also describes safeguards for reproducibility and evidence that extracted rules reduce individual discriminatory decisions.

Runtime and Performance Overhead: Under 120 seconds per symbolic program, the full Remi pipeline completes its stages from IDI finding through guardrail application.For DNN benchmarks, Stage 1 IDI finding is capped at 60 minutes, but the passage identifies it as the primary overhead.
Limitations: Remi does not claim to directly address fairness debugging for all large-scale systems, especially natural-language or vision systems requiring domain-specific counterfactual generators and semantic-validity filters.Protected-attribute changes can affect semantics subtly in these settings.
Threats to Validity: Repeated experiments report averages and standard deviations, while fixed seeds improve reproducibility but introduce seed dependency.The framework is evaluated on 20 DNNs and diverse symbolic programs, including logic-based and scoring-based models.
Semantic Validity: Counterfactual generation flips the protected attribute within its valid domain and updates causally dependent non-protected attributes using domain-specific symbolic rules.For symbolic programs, the constraints come from benchmark logic; for DNNs, input domains and preprocessing constraints come from the corresponding dataset.
Rule Correctness: Applying extracted rules as guardrails reduces IDIs, supporting their practical correctness even though DNN ground-truth discriminatory logic is unknown.For symbolic programs, qualitative correctness is additionally checked against ground-truth symbolic logic; rule quality is measured using impurity, confidence, and coverage.
Case Study: 206 IDIs found among 6,908 COMPAS individuals were captured by the extracted rule {age ≤20.5 ∧ priors_count ≤3.5}.The IDIs were generated by flipping sex, and the rule was extracted from relational labels produced through DCNE curation.

7 Related Work

Prior work on individual fairness testing has largely focused on discovering discriminatory inputs at scale under causal fairness definitions, including black-box techniques that do not require classifier internals.

Fairness Testing: Causal fairness testing motivated extensive research on discovering discriminatory inputs (IDIs) through large-scale testing.This line of work followed the individual fairness definition proposed and popularized by Galhotra et al.
Fairness Testing: Black-box tools such as Themis, AEQUITAS, SG, ExpGA, LIMI, and AFT searched for discriminatory inputs without requiring knowledge of classifier internals.The cited tools were designed for black-box settings where the inner workings of classifiers were unnecessary for finding IDIs.

8 Conclusion and Future Work

Remi treats individual fairness as relational invariant discovery, using counterfactual pairs and interpretable rule-based explainers to localize discriminatory regions. Its extracted fairness invariants explain discrimination’s root causes and support mitigation through real-time guardrails.

Remi treats individual fairness as a relational invariant discovery problem.
Transforming counterfactual pairs into a relational dataset enables Remi to localize discriminatory regions with interpretable, rule-based explainers.
Extracted fairness invariants provide precise explanations of discrimination’s root causes and a robust mitigation strategy through real-time guardrails.