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

arXiv: https://arxiv.org/abs/2608.26209 · HTML: https://mlsanity.com/paper/2608.26209/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 69 references that are in the map.
- First posted on arXiv 26 Aug 2026.

## Builds on (most cited first, 30 of 36)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Mitigating Unwanted Biases with Adversarial Learning](https://mlsanity.com/paper/1801.07593/) (2018)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [AI Fairness 360: An Extensible Toolkit for Detecting, Understanding, and Mitigating Unwanted Algorithmic Bias](https://mlsanity.com/paper/1810.01943/) (2018)
- [Fairness Testing: Testing Software for Discrimination](https://mlsanity.com/paper/1709.03221/) (2017)
- [Bias in Machine Learning Software: Why? How? What to do?](https://mlsanity.com/paper/2105.12195/) (2021)
- [Automated Directed Fairness Testing](https://mlsanity.com/paper/1807.00468/) (2018)
- [Verifying Individual Fairness in Machine Learning Models](https://mlsanity.com/paper/2006.11737/) (2020)
- [Causality-based Neural Network Repair](https://mlsanity.com/paper/2204.09274/) (2022)
- [Perfectly Parallel Fairness Certification of Neural Networks](https://mlsanity.com/paper/1912.02499/) (2019)
- [NeuronFair: Interpretable White-Box Fairness Testing through Biased Neuron Identification](https://mlsanity.com/paper/2112.13214/) (2021)
- [Exploring and Interacting with the Set of Good Sparse Generalized Additive Models](https://mlsanity.com/paper/2303.16047/) (2023)
- [Fairness-aware Configuration of Machine Learning Libraries](https://mlsanity.com/paper/2202.06196/) (2022)
- [Latent Imitator: Generating Natural Individual Discriminatory Instances for Black-Box Fairness Testing](https://mlsanity.com/paper/2305.11602/) (2023)
- [Fairify: Fairness Verification of Neural Networks](https://mlsanity.com/paper/2212.06140/) (2022)
- [Automated Test Generation to Detect Individual Discrimination in AI Models](https://mlsanity.com/paper/1809.03260/) (2018)
- [FairNeuron: Improving Deep Neural Network Fairness with Adversary Games on Selective Neurons](https://mlsanity.com/paper/2204.02567/) (2022)
- [Software Engineering for Fairness: A Case Study with Hyperparameter Optimization](https://mlsanity.com/paper/1905.05786/) (2019)
- [Adaptive Fairness Improvement Based on Causality Analysis](https://mlsanity.com/paper/2209.07190/) (2022)
- [VerifyMed -- A blockchain platform for transparent trust in virtualized healthcare: Proof-of-concept](https://mlsanity.com/paper/2005.08804/) (2020)
- [Fast Interpretable Greedy-Tree Sums](https://mlsanity.com/paper/2201.11931/) (2022)
- [NeuFair: Neural Network Fairness Repair with Dropout](https://mlsanity.com/paper/2407.04268/) (2024)
- [Fix Fairness, Don't Ruin Accuracy: Performance Aware Fairness Repair using AutoML](https://mlsanity.com/paper/2306.09297/) (2023)
- [Certifying the Fairness of KNN in the Presence of Dataset Bias](https://mlsanity.com/paper/2307.08722/) (2023)
- [Attention Pruning: Automated Fairness Repair of Language Models via Surrogate Simulated Annealing](https://mlsanity.com/paper/2503.15815/) (2025)

## Abstract (arXiv)

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