A Geometric Theory of Robust Fairness Audits: The Auditor Can Be the Fragile Part

Paper: 2608.24818 Authors: Binita Maity Categories: cs.LG

The Gap

Individual fairness is often audited by neighbourhood comparison: find pairs of individuals who are similar in feature space, and check whether the model treats them similarly. It is a natural operationalisation of the fairness notion that like cases should be treated alike, and it is widely used.

But the audit has a dependency that its users rarely examine. It relies on nearest neighbour relationships. Those relationships are determined by the geometry of the feature space, not by the model. So a small perturbation in feature space can alter local neighbourhoods and produce a different fairness assessment even when the model’s predictions remain unchanged.

This inverts the usual assumption about where fragility lives. Fairness auditing research largely studies the model — is the model unfair, is the model robust. The paper points out that the auditing procedure itself has a robustness question, and it can fail independently of the model being audited. If the verdict depends on which neighbours happen to be nearest, then two analysts running the same audit on the same model, with slightly different feature representations, can publish opposite conclusions while both being correct about what they measured.

   NEIGHBOURHOOD-BASED FAIRNESS AUDIT
   for each individual x:
     find nearest neighbours N(x) in feature space
     compare predictions on {x} U N(x)
        |
        v
   verdict: are similar people treated similarly?

   WHERE THE FRAGILITY LIVES
        |
        +-- model predictions: unchanged  <-- what people study
        |
        +-- neighbourhoods N(x): determined by GEOMETRY,
                                  not by the model
                                  |
                                  +-- small perturbation
                                  -> N(x) reshuffles
                                  -> DIFFERENT verdict
                                     with the SAME model
        |
        v
   [GAP] the robustness of the AUDITING PROCEDURE
         itself was never analysed

The Increment

One sentence: Before this paper, a fairness verdict was treated as a property of the model; after it, a geometric framework gives sufficient conditions under which neighbourhoods survive perturbation, quantifies how neighbourhood replacement propagates into audit instability, and defines audit volatility as the expected sensitivity under repeated perturbation.

Core Mechanism

The contribution is analytic, and each piece answers a question a practitioner would ask.

Sufficient conditions for neighbourhood invariance. Under bounded perturbations, when does the neighbourhood of a point stay the same? This is the constructive half: it tells you when an audit verdict is stable by construction, which is more useful than a post hoc stability check. Invariance conditions are exactly the kind of result that lets someone build an audit they can defend.

How neighbourhood replacement propagates to audit instability. When invariance fails, a neighbour gets replaced, and the question is what that does to the verdict. Deriving the propagation is what connects a geometric event — a point crossing a Voronoi-like boundary — to a statistical outcome. It is the step that turns “geometric fragility exists” into “here is how much a verdict can move”.

Audit volatility. A measure of the expected sensitivity of the fairness audit under repeated perturbations. This is the deliverable that makes the work usable: a single quantity summarising how much a given audit’s verdict should be expected to move under the perturbations it will actually experience in deployment. Volatility is the right shape of answer because it is comparable across audits and datasets, and because it is defined in the units of the audit output rather than of the geometry.

The empirical work on benchmark datasets supports the theory and, importantly, does something more specific than confirm it: the framework explains the observed stability of neighbourhood-based audits. Explaining why existing audits have often been stable is a meaningful result, because it suggests the fragility is not universal — it appears under conditions the theory identifies, which is more useful than a blanket warning.

   THE FRAMEWORK

   feature space geometry + bounded perturbation
        |
        v
   [1] SUFFICIENT CONDITIONS for neighbourhood
       invariance
       -> when is a verdict stable BY CONSTRUCTION?
        |
        v
   [2] PROPAGATION of neighbourhood replacement
       -> a point crosses a boundary
       -> how far can the verdict move?
        |
        v
   [3] AUDIT VOLATILITY
       -> EXPECTED sensitivity under repeated perturbation
       -> one number, in the audit's own units,
          comparable across audits and datasets
        |
        v
   experiments on benchmarks:
     the framework EXPLAINS the observed stability
     -> fragility is conditional, not universal

Think of it as a census whose district boundaries were drawn on a map with slightly wrong coordinates. Everyone’s answers are honest and unchanged; the questionnaire has not changed; the interviewer has not changed. But the boundary line moved by a few metres, some households are now counted in a different district, and the per-district statistics come out different. The people who study survey methodology spend their time on the respondents — are they answering truthfully, is the sample biased — and reasonably little on whether the map itself is stable. This paper is the analysis of the map: when do boundary shifts leave the totals alone, how large a total shift does one boundary crossing cause, and how much should you expect the numbers to wobble if the coordinates are redrawn? That last quantity is what a census needs before anyone quotes its district figures.

Key Concepts

• Audit volatility: the expected sensitivity of a fairness audit’s verdict under repeated perturbation. Defining it in the audit’s own output units is what makes it a practical quantity rather than a geometric curiosity.
• Neighbourhood invariance: the property that a point’s neighbourhood does not change under a bounded perturbation. It is the sufficient condition to design for, because it gives stability by construction rather than by hope.
• Fragility independent of the model: the central observation. The audit’s sensitivity is a property of the feature-space geometry and the auditing procedure, so it can vary between two analyses of the same model with the same predictions.

Framework Shift

Before (audit verdict as a property of the model):
  run the neighbourhood audit -> verdict
  robustness question asked only of the model
  -> implicit assumption: the procedure is a neutral lens
  -> two analysts with different representations can
     disagree while both measuring correctly

After (audit verdict as a property of geometry AND model):
  neighbourhood invariance conditions -> stable by design
  propagation of neighbourhood replacement -> magnitude
  audit volatility -> expected wobble under perturbation
  -> the procedure's robustness is reported alongside
     the verdict

From reporting a fairness verdict as a property of the model, to reporting it together with how much that verdict would move under perturbation, the core shift is that the auditing instrument is part of the measurement and its stability must be characterised.

Expert Assessment

Problem choice: Very good, and a useful corrective. Fairness auditing is a governance activity — verdicts get reported to people who act on them — and a verdict that is stable only by luck is a liability. Treating the auditing procedure as an object of study rather than as a neutral lens is the right framing and it is surprisingly rare.

Method maturity: The three-part structure is well chosen, since each piece has a distinct consumer: conditions for someone designing an audit, propagation for someone estimating sensitivity, volatility for someone reporting a result. Developing this geometrically is appropriate, because the mechanism really is geometric — neighbourhood replacement is a boundary-crossing event. The limitation is scope: the analysis is for bounded perturbations in feature space, which models representation noise but not every way an audit can be unstable, such as changes in the comparison metric or in the sampling of individuals.

Experimental integrity: The claim that the framework explains observed stability, rather than merely detecting instability, is the most valuable result and it is more falsifiable than a generic warning would have been — a theory that predicted universal fragility would have been refuted by existing stable audits. Restricting the empirical work to supporting the theory on benchmark datasets is proportionate for an analytic paper. The step that would strengthen it is a demonstration on a real audit where stability was previously assumed rather than measured.

Writing quality: The framing that the auditor can be the fragile component is stated clearly and is memorable. The paper would be more actionable with a worked example: one dataset, two slightly different feature representations, and the audit verdicts that result — showing the disagreement in practice rather than only in principle.

Verdict: accept — it analyses a component of the fairness pipeline that is normally treated as transparent, and it produces a reportable stability measure along with conditions to design for.

Takeaways

• Report audit volatility alongside any fairness verdict. A verdict whose stability under perturbation is unmeasured cannot be distinguished from one that happened to hold.
• Check whether your audit is stable by construction before trusting it by repetition. Sufficient conditions for neighbourhood invariance are the design target; re-running with the same neighbours proves nothing.
• Ask which parts of your evaluation procedure are geometry-dependent. Nearest-neighbour and clustering-based comparisons inherit the fragility of the feature space, independently of the model being judged.
• Treat representation choice as part of the finding. If two defensible feature encodings yield different audit verdicts, the verdict is a property of the pair, not of the model alone.