Executive Summary

Key Numbers

Source: Godinot et al., arXiv:2608.04365 (AIES 2026)

A Reuters report from late 2025, based on internal Meta documents, shows exactly the problem this paper is built around. Japanese regulators checking for scam ads on Facebook and Instagram searched the ad library that Meta publishes. Meta worked out which search terms and celebrity names regulators and journalists tended to use, ran those same searches itself first, and removed the scam ads that came up.

The goal written into the internal documents was to keep problem ads from being findable by regulators, investigators, and reporters. One memo records fewer than 100 ads found over a week and zero on the final four days. Japan ultimately did not impose the advertiser identity verification requirement Meta had been worried about, and the approach became what the documents describe as a global playbook covering the United States, Europe, India, Australia, and Brazil. Meta responded that the drop in scam ads visible in search results reflected real enforcement.

What broke here was not the institution of the ad library. Article 39 of the EU Digital Services Act places a legal obligation on very large online platforms to publish an ad repository, and the repository was in fact open. What broke was the condition that the way anyone looks inside it is visible to the other side. When audit queries are observable, the audited party does not have to fix the system. It only has to tidy the places the queries reach. Opening a transparency window and making that window hold up under manipulation are two different tasks.

Fairness evaluation has the same shape. A provider can infer sensitive attributes such as sex or race from the input with considerable accuracy, and by equalizing approval rates across groups only in the range likely to be audited, it passes a metric like demographic parity. The deployed service stays unfair. Whether the requirement is an explainability report or voluntary disclosure of fairness metrics, the gap remains as long as the method leans on the provider's cooperation and on the audit being predictable.

The respir protocol proposed by Godinot and co-authors splits an audit into four steps. First the auditor and the provider agree on a candidate set, a body of data in the thousands or tens of thousands, far larger than the sample the audit will actually use. Then the provider runs its model over that entire candidate set and builds a database of input and output pairs. It has to answer for every item, including the ones the audit will never touch.

The third step is the important one. The auditor pulls out only the subset it needs from that database using a cryptographic technique called private information retrieval. The technique is built so that the party holding the database cannot learn which items were retrieved. The provider knows what is in the candidate set but not which of those items went into the actual assessment. Finally the auditor computes the gap between groups from the outputs it recovered and decides whether that gap falls within the allowed tolerance.

The provider this design assumes is a fairly strong one. It can leave its deployed model untouched and flip as many predictions on audit queries as it likes, and it chooses which inputs to flip. It knows from the start what the candidate set contains. The protocol hides exactly one thing: which of those items were used in the assessment. Security comes from that single information asymmetry rather than from the provider's good faith.

The way this structure raises the price of manipulation is simple. Under standard black-box auditing, the provider only has to touch the minority-group responses that fall inside the audit sample. Under respir it does not know which items will land in the sample, so hiding unfairness means twisting answers consistently across the whole candidate set. The paper's theorem states that the lower bound on forgery cost shifts from the size of the minority group inside the audit sample to its size inside the candidate set. The diagram below renders that difference conceptually.

A detection mechanism comes with it. The auditor mixes canary queries, whose correct answers it already knows, into the candidate set. The wider the provider spreads its forgeries, the higher the chance of hitting one of those canaries. Instead of blocking manipulation outright, the design makes manipulation take more work, and the more work it takes the more likely it is to be caught.

What stands out in practice is that nothing has to change on the model side. The provider does not need to touch its training procedure or its inference pipeline. It answers the candidate set and that is all. The cryptography is not newly invented either. The authors take VeriSimplePIR, a verifiable extension of SimplePIR, off the shelf. The load on the auditor is modest as well. On an 8GiB database the online lookup took about 3.6 seconds and about 2.4MiB of traffic. At 128MiB the figures are 28 milliseconds and 290KiB. For a regulatory audit that runs once a year or once a quarter, that is close to nothing.

The authors ran the protocol in three audit settings. Credit card default prediction (CCD) with sex as the protected attribute, recidivism risk prediction (COMPAS) with race, and hate speech detection (HateDay) with language. The benchmark stayed the same in each case. How many responses must be flipped to hide half of the unfairness that was there to begin with?

The multiple is what deserves a second look. The candidate set is only twice the audit sample, yet the cost rose fourfold rather than twofold. The theorem guarantees a lower bound and nothing more, and the forgery actually required came out well above that bound. The larger the candidate set an auditor chooses, the wider the gap grows.

That hands auditors a lever for raising the price of manipulation without enlarging the audit, and the lever comes with a bill attached. Growing the candidate set also grows the number of answers the provider must produce. Only half of them are used in the audit, yet inference has to run on the other half too, so the harder an auditor pushes on manipulation cost, the sooner the provider's compute burden rises. Where reasonable demands end is something the audit regime itself will have to settle.

The detection figures are more intuitive. On the race attribute in COMPAS, with five canaries planted, standard black-box auditing caught manipulation 10.74% of the time and respir 20.53%. Raise the canaries to 50 and the rates go from 67.89% to 89.96%. The same number of canaries catches more, because the surface the provider had to touch got wider.

The authors name three limits themselves. First, hiding the audit set is necessary but not always sufficient. The candidate set is public to the provider, so a uniform strategy applied across all candidates remains available. The protocol does not close that route. It makes the route expensive.

Second, when the protected group is an extremely small share, the defense weakens sharply. Minority languages made up roughly 8% of the candidate set in HateDay, and under that condition the detection rate stayed low even with 50 canaries. The flips needed to hide manipulation did rise from 7 to 26, but the absolute quantity is small to begin with. Protecting structurally small minorities remains the weakest point in this design too.

Third, if the candidate set does not represent the real operating environment, passing an audit says nothing about actual fairness. What the auditor put forward as candidates decides the conclusion. Cryptography that hides the queries does not repair a badly drawn sample.

This paper is not alone in working on the question. Research on which models are relatively harder to audit when a provider attempts manipulation (arXiv:2402.09043), on catching fairwashing with only imperfect auxiliary data (arXiv:2305.13883), and on making audits more robust using prior knowledge the auditor already holds (arXiv:2505.04796) has all appeared over the past few years. What they share is treating the audit procedure itself, rather than the audit result, as the thing to be verified. Among those routes, this paper chose to hide what the auditor asked.

So what the paper actually moves is the location of the argument. Debate about audit regimes has mostly stayed on the question of what to mandate. Whether to require disclosure of fairness metrics, whether to grant third-party access, how often reports should be filed. This paper takes the same obligations and asks how an audit procedure has to be designed for the result to hold value without the audited party's cooperation. Manipulation cost has become a design variable.

Academic Papers

• 1.Godinot, A., Azogagh, S., Ferry, J., Gambs, S. (2026). "Manipulation-Proof Oblivious Audits against Deceptive Model Providers." AIES 2026.
• 2.Godinot, A., Tredan, G., Le Merrer, E., Penzo, C., Taïani, F. (2024). "Under Manipulations, Are There Traceable Differences in Fairness Audit?" arXiv:2402.09043.
• 3.Garcia Bourrée, J., Le Merrer, E., Tredan, G., Rottembourg, B. (2023). "Leveraging Imperfect Sources to Detect Fairwashing in Black-Box Auditing." arXiv:2305.13883.
• 4.Garcia Bourrée, J. et al. (2025). "Robust ML Auditing using Prior Knowledge." ICML 2025.

Industry & Reporting

• 5.Reuters (2026). "'Not findable': Meta devised global 'playbook' to stall scam-ad regulations in Japan, Europe, US and beyond, documents show."