A Geometric Theory of Robust Fairness Audits

Binita Maity

cs.LGAug 25, 2026

A Geometric Theory of Robust Fairness Audits

Authors: Binita Maity

Organizations: Indian Institute of Technology, Gandhinagar

Abstract

Neighborhood-based fairness audits evaluate individual fairness by comparing predictions among similar individuals in feature space. Despite their widespread use, little is known about the robustness of the auditing procedure itself. Because these audits rely on nearest neighbor relationships, small perturbations in feature space can alter local neighborhoods and produce different fairness assessments even when model predictions remain unchanged. We develop a geometric framework for analyzing the robustness of neighborhood-based fairness audits under bounded perturbations. Our analysis establishes sufficient conditions for neighborhood invariance, quantifies how neighborhood replacement propagates to audit instability, and introduces audit volatility, a measure of the expected sensitivity of fairness audits under repeated perturbations. Experiments on benchmark datasets support the theoretical analysis and show that the proposed framework explains the observed stability of neighborhood-based fairness audits.

Figures & tables

Dataset	$\max\|d^{\prime}-d\|$	Theory( $2\epsilon$ )	$\max(\gamma-\gamma^{\prime})$	Theory( $4\epsilon$ )
Adult	0.033	0.100	0.032	0.200
Bank	0.038	0.100	0.047	0.200
COMPAS	0.066	0.100	0.025	0.200

Table 1: Empirical validation of the geometric stability bounds established in Lemmas 1 and 2 under

\ell_{2}

perturbations with

\epsilon=0.05

. Across all datasets, the observed maxima remain below the corresponding theoretical upper bounds.

Figure 1: Neighborhood Preservation Rate (NPR) as a function of the perturbation radius

\epsilon

. Larger perturbations progressively reduce neighborhood stability, consistent with Theorem 3.

Figure 2: Expected neighborhood replacement

\mathbb{E}[|R_{i}|]

as a function of the perturbation radius

\epsilon

. Neighborhood replacement increases monotonically across all datasets, with COMPAS exhibiting substantially greater geometric sensitivity than Adult and Bank.

Figure 3: Neighborhood replacement (left) and audit volatility (right) under four perturbation models with identical perturbation budgets. Despite differences in the perturbation distributions, audit volatility consistently follows neighborhood replacement across all datasets.

Figure 5: Audit volatility under different aggregation operators. Robust aggregators (trimmed mean and median) consistently exhibit lower volatility than the worst neighbor operator, supporting Theorem 6.

Figure 6: Effect of the local separation margin on audit robustness. Left: Expected neighborhood replacement

\mathbb{E}[|R_{i}|]

decreases with increasing separation margin. Right: Audit volatility

\kappa

exhibits the same trend, approaching zero for well-separated neighborhoods.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Dataset	NPR	$\mathbb{E}[\|R_{i}\|]$	$\kappa$	Bound	$\kappa/\mathrm{Bound}$
Adult	0.765	0.520	0.00238	0.052	0.046
Bank	0.705	0.634	0.001504	0.063	0.024
COMPAS	0.515	2.196	0.004333	0.220	0.020

Appendix

Table 2: Empirical validation of Theorem 8 at the largest perturbation radius (

\epsilon=0.20

). Across all datasets, the observed audit volatility remains below the theoretical upper bound, with no per-individual violations.

Algorithmic Fairness

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

See all 424 papers

Fairness Auditing: Lower Bounds on Company Manipulation
Aug 1, 2026Rachit Verma, Padala Manisha, Sujit GujarAlgorithmic Auditing Algorithmic Fairness
Indian Institute of Technology Gandhinagar · International Institute of Information Technology Hyderabad
Sequential Fairness Auditing with Limited Output Access
Jun 29, 2026Ioannis Pitsiorlas, Martha V. Sourla, Marios KountourisAlgorithmic Fairness Group Fairness
EURECOM, France · DaSCI, University of Granada, Spain
Tolerance-Based Fairness Auditing: Violation Certification and Sensitivity Screening
Oct 1, 2026Jie Tang, Chuanlong Xie, Lixing ZhuAlgorithmic Auditing Algorithmic Fairness
School of Statistics, Beijing Normal University, Zhuhai, Guangdong 519087, China

Aug 1, 2026J/K move · Enter open · S save

Fairness Auditing: Lower Bounds on Company Manipulation

Rachit Verma, Padala Manisha, Sujit Gujar

Indian Institute of Technology Gandhinagar · International Institute of Information Technology Hyderabad

Algorithmic Auditing Algorithmic Fairness Group Fairness

Open paper AskPDF arXiv

Fairness audits are increasingly mandated in high-stakes applications such as hiring, lending, and automated decision-making. Recent work has established fundamental impossibility results for black-box fairness auditing, showing that sufficiently expressive models can evade any auditing strategy. We complement these results by quantifying the extent of unavoidable post-audit manipulation under finite audit resources. We formulate fairness auditing as a min-max optimization between a computationally unbounded company and a budget-constrained auditor. We study two auditing regimes: (i) a budgeted auditor that certifies fairness using a fixed-size audit set, and (ii) a budgeted α-tolerant auditor that additionally requires the audit set to estimate the fairness of the certified model within an α approximation. For both settings, we derive explicit lower bounds on the worst-case post-audit demographic parity deviation as functions of the audit budget, group imbalance, and fairness tolerance. Finally, we empirically illustrate these theoretical limits using simple audit-set construction heuristics with linear and neural network classifiers. Our results demonstrate that increasing audit resources reduces, but does not eliminate, the scope for post-audit manipulation, highlighting fundamental limitations of finite-budget fairness certification.

Abstract

Algorithmic Fairness

Explore similar work

Fairness Auditing: Lower Bounds on Company Manipulation

Sequential Fairness Auditing with Limited Output Access

Tolerance-Based Fairness Auditing: Violation Certification and Sensitivity Screening