Keyed Safety Margins: Counterfactual Explanations That Stay Valid but Stop Teaching Thieves

A counterfactual explanation tells a person the smallest change to their input that would flip a model's decision ("with $4,000 more annual income, your loan would be approved"). Regulators increasingly expect such explanations. They are also a gift to attackers. A counterfactual lands almost exactly on the model's decision boundary, so a few hundred of them let an outsider copy the model. Model extraction from counterfactual explanations reaches 90% agreement with the target after 250 queries on Adult Income. A label-only attacker needs over 8,000 queries to reach about 81%. The obvious defense is to add differential-privacy noise to the explainer, but that makes the explanations useless to honest users. In On the Interplay of Explainability, Privacy and Predictive Performance with Explanation-assisted Model Extraction, the usefulness of counterfactuals ("Prediction Gain") collapses from 0.488 to 0.055. Worse, every published explanation defense has been tested only against attackers who ignore how the defense works. That is the error the adaptive-attack literature keeps exposing.

We propose a different kind of distortion, and a test regime that assumes the attacker knows everything except a secret key. Instead of zero-mean noise, the server pushes each counterfactual a little past the boundary, into the region where the decision really does flip. The size of the push varies smoothly across input space according to a keyed random field. Because the push always goes further into the region of the desired outcome, every explanation remains valid recourse on the true model. Honest users pay only a modest extra cost. Because the push is consistent across repeated queries and varies in a way the attacker cannot predict, averaging does not remove it. Neither does querying a counterfactual's own counterfactual, the trick introduced by DualCF. The goal is narrow and checkable: push explanation-assisted extraction back down to the label-only learning curve while keeping recourse valid and auditing cheap.

Core Claim

Explanation leakage should be measured against an attacker who knows the defense mechanism. Under that standard, what matters is not how much noise a defense adds but whether the distortion is (a) one-sided and (b) consistent yet unpredictable. One-sidedness keeps recourse valid. Consistency defeats statistical averaging. Unpredictability means the distortion cannot be learned as a fixed offset.

The information-theoretic result in Bits Leaked per Query supplies the lens. It proves that the number of queries an adaptive attacker needs scales as $\Theta(\log(1/\varepsilon)/I(Z;T))$, where $I(Z;T)$ is the mutual information between what the attacker observes and what they want to learn. It confirms the predicted slope of exactly −1.00 on LLM disclosure regimes. That paper studies passive disclosures (logits, reasoning traces) and proposes no defense. We apply the same reasoning to interactive recourse. A defense that lowers bits-per-query about the boundary location, without lowering bits about which direction to move, should slow extraction proportionally while sparing honest users.

Concretely, for a query $x$ with nearest boundary point $b(x)$ and unit normal $n(b)$ pointing toward the flipped class, the server returns

$$c(x) = b(x) + \big(m_0 + s\, g_K(b(x))\big)\, n(b(x)),$$

where $m_0 \ge 0$ is a base margin, $s$ is a spread, and $g_K$ is a smooth random field taking values in $[0,1]$, seeded by a secret key $K$. A second, independent field $h_K$ governs counterfactuals requested from the opposite side. This prevents the midpoint of a DualCF pair from cancelling the margins. For trees, $n$ is axis-aligned, and the margin hides the exact split thresholds that the Tree Reconstruction Attack reads off to clone trees with 100% fidelity.

We are not claiming protection below the label-only baseline. The attacker always sees the true label of each query point, so the honest target is to erase the extra advantage that counterfactuals confer.

Research Program

The work has three parts.

Adaptive-attack audit of existing defenses. For the dual-DP CounterGAN defense of Ezzeddine et al., we give the attacker the noise distribution and let them combine DualCF boundary pairs with a noise-aware surrogate loss. For XRand, the attacker decodes randomized-response feature rankings by maximum likelihood, pooling rankings from many nearby queries. The XRand authors explicitly left this adaptive case open. For ambiguity-set disclosure in the style of Ambiguous Strategic Classification, the attacker fits the disclosed set and then probes for the privately realized classifier. The audit motivates the rest. If these defenses survive adaptive attackers, the case for a new mechanism weakens and we will report that.

The keyed-margin mechanism and its adaptive attacker. We build the mechanism for linear models, multilayer perceptrons, and tree ensembles. Following the watermark-evasion work in Optimizing Adaptive Attacks against Content Watermarks for Language Models, where training against surrogate keys achieved 96–98% evasion, our attacker samples surrogate keys. It then jointly estimates the base margin, the spread, and the boundary by expectation-maximization, using hard labels at query points as anchors.

Measurement. We estimate bits-per-query empirically. For each defense, we fit the slope of log queries-to-target-fidelity against an estimate of $I(Z;T)$, obtained by comparing the surrogate learning curve with the label-only curve. The question is whether the Kaneko–Baldwin scaling transfers from LLMs to recourse APIs. The paper itself notes that non-adaptive attacks deviate wildly from the law, so this test is only meaningful with adaptive attackers.

Two constraints from prior work shape the design. Exploring Counterfactual Explanations Through the Lens of Adversarial Examples shows that counterfactuals and adversarial examples are near-identical (Spearman > 0.90). Our margins therefore also reduce the precision of explanation-derived adversarial examples, and we will measure this as a side effect. XAudit shows that exact counterfactuals let an auditor verify feature sensitivity in one query for linear models, and in about 54 queries versus about 905 for random testing on Credit. We must check that one-sided margins preserve the direction information auditors need even as they blur location.

Baselines

Undefended counterfactual API (the naive reference point). This is the undefended counterfactual API attacked by the strongest applicable extractor: Aïvodji et al.'s surrogate training, DualCF pairing, and TRA for trees. Reported numbers include 90% fidelity at 250 queries on Adult and 93–98% at 1,000 queries across datasets (Model extraction from counterfactual explanations). TRA reports 100% fidelity on a depth-9 COMPAS tree with an average of 153 queries (From Counterfactuals to Trees). DualCF reports nearly 95% agreement on GMSC; the file gives no query count for Heloc or Housing.

Label-only API. This is the floor we aim to reach. The reported figure is about 81% after more than 8,000 queries on Adult.

Dual-DP defense. This is the strongest existing defense against counterfactual extraction (Ezzeddine et al.). It is the most direct competitor because it targets exactly this threat. Its reported cost is Prediction Gain falling from 0.488 to 0.055 on Housing and accuracy falling from 0.94 to 0.85 on EEG. We rerun it on the same Housing and EEG data, plus Adult and Credit. Each defense's privacy parameter is tuned to equal compute on a held-out validation split, then evaluated against both static and adaptive attackers.

XRand. We include it for the feature-attribution threat on EMBER, where it reports attack success dropping from 77.8% to 10.2% at $\epsilon=1.0$ on LightGBM.

Ambiguity-set recourse. This returns counterfactuals valid for every member of a disclosed set of $k$ classifiers. It is the closest conceptual neighbor, since it also yields conservative but valid recourse. The ambiguity-set paper reports about 88% accuracy under full transparency rising to 99.2% with $k=3$ on synthetic data, but that measures gaming, not extraction.

Ablations. Two ablations isolate the key ingredient: a fixed constant margin (one-sided but predictable) and an independent random margin redrawn per query (one-sided but inconsistent).

What counts as beating the baselines. At matched mean recourse cost, keyed margins must yield lower adaptive-attacker fidelity than every baseline at 250 and 1,000 queries. They must also keep recourse validity on the true model at or above 99%, where the DP baseline cannot guarantee validity at all.

Why not just…?

Why not just add differential-privacy noise to the explainer? The reported utility collapse (0.488 to 0.055 Prediction Gain) is the main evidence against it. Zero-mean noise also produces counterfactuals that fail to flip the decision, which harms honest users in a way margins never do. The open question is whether DP at least resists adaptive attackers. Our audit tests this directly. If DP holds up adaptively at a privacy level with tolerable utility, it remains the simpler choice, and we will say so.

Why not just rate-limit or monitor queries? The attacks need too few queries for volume limits to bite: 250 queries for 90% fidelity, 153 for a full tree, and one query to recover a linear model's weights in XAudit. Attackers can also interleave probes with benign traffic. Rate-limiting is complementary, and we report fidelity at small budgets precisely because that is the regime monitoring cannot reach.

Why not just return counterfactuals with a fixed safety margin, or a fresh random margin each time? This is the real threat to the proposal, because both are simpler and both keep recourse valid. A fixed margin should be estimable as a single offset from a handful of labeled anchors. A per-query random margin should be removable by re-querying and taking the minimum or mean. These are exactly our two ablations. If either matches keyed margins against the adaptive attacker, the keyed field is unnecessary and the contribution reduces to "always overshoot," which we would report.

Why not just disclose an ambiguity set? Ambiguity sets were designed against rational strategic users solving a max-min problem, not against automated extractors. An extractor that fits the set and then locates the realized classifier may recover the boundary quickly. We run this attack. If ambiguity sets match keyed margins on fidelity, recourse cost, and audit cost, they are the better-motivated option.

Proposed Experiments

We use the datasets on which reported numbers exist: Adult, COMPAS, German and Default Credit, GMSC, Heloc, Housing, and EEG Eye State, with EMBER for the attribution threat. Target models are logistic regression, two-layer MLPs, depth-9 decision trees, and random forests. Metrics are:

  • extraction fidelity on held-out inputs as a function of queries (50 to 2,000);
  • recourse validity on the true model;
  • recourse cost, as mean extra L1 distance relative to the exact counterfactual;
  • XAudit query complexity for sensitivity detection on Gender/Sex;
  • for EMBER, backdoor attack success.

Every defense faces both a static attacker and the mechanism-aware adaptive attacker with surrogate keys.

Three outcomes are decisive.

  1. Under the adaptive attacker, keyed margins must bring 1,000-query fidelity within a few points of the label-only curve on Adult and COMPAS, with mean recourse cost rising by a reported, bounded amount and validity staying near 100%.
  2. Both ablations must leak substantially more, which confirms that consistency combined with unpredictability is what matters.
  3. XAudit's sensitivity detection must keep a query count close to the undefended case.

A secondary check is whether log queries against estimated bits-per-query gives a slope near −1 for adaptive attackers across all defenses, as Kaneko and Baldwin found for LLMs. That would turn the defense comparison into a single measurable quantity. Failure on the first outcome falsifies the mechanism. Failure on the second falsifies the need for keying. Failure on the third shows that the auditing–theft tension cannot be resolved this way.