A counterfactual explanation tells a person what minimal change would flip an automated decision, for example "raise your savings by X and the loan is approved." Naive versions choose the geometrically shortest change, which often lands on impossible feature combinations. The standard remedy is to pull the search toward realistic data using a generative model, meaning a model trained to assign high probability, or "density," to data that looks real. The same model is then usually used to report how realistic the answer is. That is the problem this note targets. The recourse search is an optimizer, and it runs against that density model. Density models are known to be easy to fool: Pope et al. showed that tiny input changes can move a flow model's likelihood by orders of magnitude, and that noise can be nudged to look highly likely (Adversarial Robustness of Flow-Based Generative Models). "On-manifold" recourse may therefore be partly an attack on its own plausibility checker. It would look realistic to the model that produced it and to nothing else.
We propose to measure this effect directly and to fix it where it exists. The measurement uses semi-synthetic tabular benchmarks in which the true data density and the true label are known exactly. On these benchmarks we can compare, for every counterfactual, the plausibility the search model claims with its actual plausibility, and whether the model's prediction flipped with whether the true label flipped. The fix is a search that is scored by one set of density models, drawn from different families, and certified by a separate density model that the search never saw. In two sentences: generative recourse methods report plausibility using the same density model they optimize against, so they can "win" by exploiting that model's blind spots. We quantify that gap against known ground truth and test whether separating the model that guides the search from the model that certifies the result closes it.
Core Claim
Our hypothesis is that, for density-guided recourse methods on standard tabular tasks, a measurable share of reported plausibility is an artifact of optimizing against the plausibility model. We call this share the exploitation gap. For a counterfactual $x'$, let $q_M(x')$ be its density percentile under the search-time model $M$, relative to real data, and let $q_\star(x')$ be its percentile under the true density. The gap is
$$ G(x') = q_M(x') - q_\star(x'), $$
averaged over test individuals. A method that is honestly on-manifold has $G \approx 0$. A method that is hacking its density model has large positive $G$. We expect the gap to grow with optimizer strength and with how expressive and unhardened $M$ is.
The corpus gives three reasons to expect this.
- Manifold methods already resemble attacks. Exploring Counterfactual Explanations Through the Lens of Adversarial Examples found that VAE-based recourse (C-CHVAE) produces solutions even closer to on-manifold adversarial examples than gradient methods do, with Spearman correlations above 0.90 between the two. That paper compares outputs statically. It never asks whether the density model was fooled.
- Likelihood is easy to move. Pope et al. show flow likelihoods can be moved almost arbitrarily. Their study stops at unsupervised likelihood and does not examine recourse built on flows, such as CeFlow.
- The same pattern appears in explanation benchmarks. Goodhart's Law Applies to NLP's Explanation Benchmarks shows that evaluation metrics built from the same perturbations being evaluated get gamed.
The clearest instance is MIP-Live-DM. It encodes a Local Outlier Factor score (a nearest-neighbor measure of how isolated a point is) as a constraint and then reports 0% outliers on FICO and German Credit, measured by that same Local Outlier Factor. That number cannot, by construction, tell us whether the counterfactuals are realistic under any independent standard.
This work differs from the closest prior work in its target. We do not ask whether counterfactuals resemble adversarial examples (Exploring CFEs vs AEs; The Intriguing Relation Between Counterfactual Explanations and Adversarial Examples). We also do not use a nearest-neighbor stand-in for ground truth, as Towards Non-Adversarial Algorithmic Recourse does. We ask whether the realism guarantee itself is being attacked, and we answer with exact ground truth rather than a proxy.
Research Program
Stage one: ground-truth benchmarks. For Adult, COMPAS, German Credit and HELOC, we fit a tractable class-conditional mixture model $p(x \mid y)$ to the real data. This model has mixed discrete and continuous components with enough components to reproduce pairwise correlations. We then sample a synthetic replica dataset from it. On these replicas the true density $p(x)$ and the true posterior $p(y \mid x)$ are computable in closed form. Two quantities follow for any counterfactual: its true density percentile, and whether it truly changed the outcome or only fooled the classifier.
Classifiers and all generative models are trained only on samples, never on the mixture parameters. The synthetic distribution is simpler than reality. That is acceptable here, because the question is whether the optimizer exploits the learned density model. A simpler truth makes exploitation easier to detect, not harder.
Stage two: audit. We run the main density-guided methods through the CARLA interface on each replica:
- CeFlow (a flow-based method);
- C-CHVAE and REVISE (VAE-based methods);
- CountARFactuals (based on adversarial random forests, paper);
- MIP-Live-DM (Local Outlier Factor constraints).
For each output we record:
- the exploitation gap $G$;
- true-label flip rate, a ground-truth version of non-adversarialness;
- validity, meaning whether the classifier's prediction flips;
- cost, measured as the L1 distance (total size of the change) and the L0 count (number of features changed).
We then sweep optimizer strength, the latent step scale $\alpha$ in CeFlow and the penalty weights in the VAE methods, to see whether $G$ rises as the search pushes harder. A rising gap under a stronger optimizer is the signature of exploitation, as opposed to plain modeling error.
Stage three: separated certification. The proposed method keeps two roles apart.
- Guidance. A small panel of density models from different families (a flow, a VAE, an adversarial random forest density) guides the search. The search maximizes the minimum percentile across the panel, so no single model's blind spot can be exploited alone.
- Certification. A density model from a family outside the panel certifies the result and is never touched during search. We use a hybrid-adversarially-trained flow in the style of Pope et al., or a kernel density estimate.
The underlying bet is that heterogeneous model families share fewer exploitable directions than retrained copies of one family. That bet can fail, since adversarial examples are known to transfer across models. Stage three is built to show whether it does fail.
Stage four: gatekeeper check. This connects to the out-of-distribution (OOD) detection literature, which studies filters that flag inputs unlike the training data. We deploy a density detector hardened by the hybrid adversarial training of Pope et al. as a gatekeeper in front of the classifier. Two failure modes from Robust Out-of-distribution Detection in Neural Networks apply. First, it may reject honest recourse, a denial-of-service against the individual; we measure this as its false rejection rate on counterfactuals whose true percentile is high. Second, it may admit density-hacked recourse.
Baselines
Naive reference. The do-nothing reference is Wachter-style distance-minimizing recourse, using gradient descent on the L2 distance plus a prediction loss. It uses no density model, so it has no claimed plausibility to hack. Its true percentile shows how off-manifold unconstrained recourse lands, and its true-label flip rate shows how adversarial it is. On the Adversarial Robustness of Causal Algorithmic Recourse shows that such minimum-cost recourse sits exactly on the decision boundary and can be invalidated by perturbations as small as $10^{-6}$. Beating it is necessary but not impressive.
CeFlow, the strongest existing generative method. CeFlow is the strongest competitor on speed and stability. It reports near 100% target-class success, about 0.8 seconds per explanation on Adult against 7 to 12 seconds for C-CHVAE and DiCE, and L1-variance across runs of $1.0\times10^{-5}$. We found no reported result on Lacuna for CeFlow's log-density values or for its plausibility under an independent density model. That missing number is exactly what this project supplies. We rerun CeFlow with its published flow architecture, retrained on each replica. Its step scale $\alpha$ gets the same tuning budget as our method: the same grid, selected on validation validity.
MIP-Live-DM, the strongest plausibility claim. MIP-Live-DM reports 0% outliers on FICO and German Credit with an optimality gap of about 2%. We rerun it with the same network sizes and solver time limits it reports, on the same replicas.
Instance-based reference. FACE-EPS, which CARLA reports as having the highest nearest-neighbor data support, returns near-real points. It shows what true plausibility costs when exploitation is impossible.
What counts as beating these. Our method beats them if it achieves both of the following at matched validity and matched tuning budget:
- a mean exploitation gap $G$ that is statistically lower, together with a higher true percentile, than CeFlow and C-CHVAE;
- L1/L0 cost clearly below FACE-EPS.
Ablations. Four ablations isolate the key ingredient, heterogeneity.
- The same min-over-panel search with three retrained flows instead of three model families.
- Guiding with the hardened certifier itself, which puts it back in the loop.
- Guiding with a single hardened flow.
- A heterogeneous panel whose members are all unhardened.
All methods use the same data splits, the same classifier weights, and the same wall-clock budget per explanation.
Why not just…?
Why not just check nearest-neighbor data support instead of building ground-truth replicas? Nearest-neighbor support, as in CARLA's measure or the nearest-neighbor stand-in in Towards Non-Adversarial Algorithmic Recourse, is a model the search did not optimize against. For low-dimensional tabular data it might be enough, and this is a real threat to the value of the project's method component. The replicas settle it. We will report the rank correlation between nearest-neighbor support and true percentile. If that correlation is high and nearest-neighbor support already exposes the gap, the contribution narrows to "report held-out plausibility, not in-loop plausibility." We would then say so plainly, and that recommendation would still invalidate current reporting practice.
Why not just adversarially train the flow, as Pope et al. did? Their hybrid training stabilized attacked likelihood between 3.6 and 5.9 on CIFAR-10, where an unhardened GLOW model could be pushed from 3.4 to 2,000,000. Hardening the guidance model may by itself close the gap, and the single-hardened-flow ablation tests exactly that. Pope et al. also show that robustness costs clean fit. On the replicas we can measure whether a hardened flow trades exploitation for misplaced density, meaning a lower true percentile for honest points. If a single hardened flow matches the panel, we adopt it as the recommendation.
Why not just use instance-based recourse, which cannot hack a density model? Returning real points guarantees plausibility, but CARLA documents that such methods sacrifice sparsity and cost. Instance-Based Counterfactual Explanations for Time Series Classification buys feasibility by anchoring to observed points in the same way. We include FACE-EPS so the cost of that guarantee appears on the same axes. Our method is only worthwhile if it lies strictly between the two extremes: nearly FACE-level true plausibility at clearly lower cost.
Proposed Experiments
Decisive audit. The first experiment is the audit. The hypothesis fails if, for CeFlow and C-CHVAE on the Adult and German Credit replicas, the exploitation gap $G$ does not rise with optimizer strength and stays within seed-to-seed noise. In that case, generative recourse is honest, and the project reduces to a validation of it.
If the gap does rise, three follow-up tests decide the rest.
True-label flips. We test whether exploited counterfactuals are also the ones that flip the classifier's prediction but not the true posterior. This would give a ground-truth confirmation of the adversarial-recourse link that Exploring CFEs vs AEs inferred only from similarity. We also test whether plausible counterfactuals remain more stable under noise when plausibility is measured by the true density, as Evaluating Robustness of Counterfactual Explanations found using model-based plausibility. That paper reported a median instability of 1.87 against 10.16 on Wine.
Heterogeneity. We test whether the heterogeneous panel lowers $G$ more than the same-family panel. If the two are indistinguishable, exploitable directions transfer across model families, and separated certification offers no protection beyond hardening.
Gatekeeper. We compare the hardened gatekeeper's false rejection rate on high-true-percentile counterfactuals with its acceptance rate on high-gap counterfactuals. This shows whether hardened OOD filters penalize honest recourse, the denial-of-service mode described by ALOE, while letting density-hacked recourse through.
Real data. On the real, non-synthetic datasets, where ground truth is unavailable, we report the held-out-certifier gap alongside the in-loop gap for every method. This makes it visible how much of the plausibility reported in the literature survives an independent check.
References
- Adversarial Robustness of Flow-Based Generative Models
- Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis
- CeFlow: A Robust and Efficient Counterfactual Explanation Framework for Tabular Data Using Normalizing Flows
- Goodhart's Law Applies to NLP's Explanation Benchmarks
- Manifold-Aligned Counterfactual Explanations for Neural Networks
- The Intriguing Relation Between Counterfactual Explanations and Adversarial Examples
- Towards Non-adversarial Algorithmic Recourse
- CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms
- CountARFactuals - Generating Plausible Model-Agnostic Counterfactual Explanations with Adversarial Random Forests
- Robust Out-of-distribution Detection for Neural Networks
- On the Adversarial Robustness of Causal Algorithmic Recourse
- Instance-Based Counterfactual Explanations for Time Series Classification
- Evaluating Robustness of Counterfactual Explanations