A Geometric Theory of Robust Fairness Audits

Fairness auditing evaluates whether machine learning systems treat individuals equitably. We study whether neighborhood-based individual fairness audits remain stable when data are perturbed while predictions remain fixed. We model audits as Lipschitz aggregations of pairwise fairness scores over $k$-nearest neighbors. Under an $\varepsilon$-bounded perturbation, pairwise distances change by at most $2\varepsilon$, and the local separation margin decreases by at most $4\varepsilon$; thus, margins exceeding $4\varepsilon$ guarantee neighborhood preservation. We bound audit deviation by neighborhood replacement and aggregation sensitivity, and introduce audit volatility for stochastic perturbations. Experiments on Adult, Bank, and COMPAS validate these guarantees and their dependence on local geometry.