# Auditing Fairness under Model Updates: Fundamental Complexity and Property-Preserving Updates

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 47 references that are in the map.
- First posted on arXiv 9 Jan 2026.

## Builds on (most cited first, 25 of 25)

- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [BBQ: A Hand-Built Bias Benchmark for Question Answering](https://mlsanity.com/paper/2110.08193/) (2021)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Are Emergent Abilities of Large Language Models a Mirage?](https://mlsanity.com/paper/2304.15004/) (2023)
- [Learning under Concept Drift: A Review](https://mlsanity.com/paper/2004.05785/) (2020)
- [Measuring Robustness to Natural Distribution Shifts in Image Classification](https://mlsanity.com/paper/2007.00644/) (2020)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Closing the AI Accountability Gap: Defining an End-to-End Framework for Internal Algorithmic Auditing](https://mlsanity.com/paper/2001.00973/) (2020)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [How is ChatGPT's behavior changing over time?](https://mlsanity.com/paper/2307.09009/) (2023)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [Verifying Individual Fairness in Machine Learning Models](https://mlsanity.com/paper/2006.11737/) (2020)
- [Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information](https://mlsanity.com/paper/2104.09460/) (2021)
- [Active Fairness Auditing](https://mlsanity.com/paper/2206.08450/) (2022)
- [Auditing Fairness by Betting](https://mlsanity.com/paper/2305.17570/) (2023)
- [Algorithmic Auditing and Social Justice: Lessons from the History of Audit Studies](https://mlsanity.com/paper/2109.06974/) (2021)
- [Algorithmic audits of algorithms, and the law](https://mlsanity.com/paper/2203.03711/) (2022)
- [Active Fourier Auditor for Estimating Distributional Properties of ML Models](https://mlsanity.com/paper/2410.08111/) (2024)
- [Data Amplification: Instance-Optimal Property Estimation](https://mlsanity.com/paper/1903.01432/) (2019)
- [Under manipulations, are some AI models harder to audit?](https://mlsanity.com/paper/2402.09043/) (2024)
- [Data Amplification: A Unified and Competitive Approach to Property Estimation](https://mlsanity.com/paper/1904.00070/) (2019)
- [Distribution-Specific Auditing For Subgroup Fairness](https://mlsanity.com/paper/2401.16439/) (2024)
- [Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits](https://mlsanity.com/paper/2211.01743/) (2022)
- [FairSense: Long-Term Fairness Analysis of ML-Enabled Systems](https://mlsanity.com/paper/2501.01665/) (2025)

## Built on by (most cited first, 1 of 1)

- [Evaluating Model Retraining under Drift: Paired Comparisons of Cumulative Subgroup Disparity](https://mlsanity.com/paper/2609.09788/) (2026)

## Abstract (arXiv)

As machine learning models become increasingly embedded in societal infrastructure, auditing them for bias is of growing importance. However, in real-world deployments, auditing is complicated by the fact that model owners may adaptively update their models in response to changing environments, such as financial markets. These updates can alter the underlying model class while preserving certain properties of interest, raising fundamental questions about what can be reliably audited under such shifts. In this work, we study group fairness auditing under arbitrary updates. We consider general shifts that modify the pre-audit model class while maintaining invariance of the audited property. Our goals are two-fold: (i) to characterize the information complexity of allowable updates, by identifying which strategic changes preserve the property under audit; and (ii) to efficiently estimate auditing properties, such as group fairness, using a minimal number of labeled samples. We propose a generic framework for PAC auditing based on an Empirical Property Optimization (EPO) oracle. For statistical parity, we establish distribution-free auditing bounds characterized by the SP dimension, a novel combinatorial measure that captures the complexity of admissible strategic updates. Finally, we demonstrate that our framework naturally extends to other auditing objectives, including prediction error and robust risk.