acceptodds
Under review as a conference paper at ICLR 2027

Certified Counterfactuals for Neural Networks

Abstract

Counterfactual explanations aim to identify minimal changes that alter a model’s prediction. Unlike adversarial perturbations, however, these changes should correspond to plausible, interpretable, and actionable modifications of the input. Existing approaches broadly fall into two categories: data-based and model-based methods. Data-based methods search among reference points, favoring plausibility but potentially sacrificing proximity and disclosing individual reference points. Model-based methods require query-time model access and generally provide no formal guarantee that the target prediction persists throughout a neighborhood of the returned point or that the point lies in a well-supported region of the input space. We introduce CertCF, a counterfactual explanation method for neural network classifiers that bridges these two families by linking counterfactual generation with neural network verification. CertCF uses a reference dataset to construct a certified under-approximation of the target-class preimages as a union of convex regions, and uses this structure at query time to enable fast, plausible, and valid-by-design counterfactual search. Additionally, it can guarantee bounded robustness to input perturbations and restrict changes to a designated subset of features. We evaluate CertCF on seven tabular datasets commonly used in the counterfactual explanations literature, comparing it against four representative methods, and show that CertCF achieves 100% validity and strong robustness while remaining competitive on the main quality metrics.

Primary area:
interpretability and explainable AI
Keywords:
counterfactual explanations, explainable AI, neural network verification, certified robustness, preimage approximation, formal methods, algorithmic recourse

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_HhvYOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CertCF, a counterfactual explanation method for neural network classifiers. Offline, it uses a verification tool to build small regions around reference points that are guaranteed to be classified as the target class. Online, it answers a query by finding the closest point within the nearest regions, without calling the model again. Experiments on seven tabular datasets show 100% validity and strong robustness and plausibility, while proximity and sparsity remain behind model-based methods.

Critical strengths

1.Validity by construction. Every returned counterfactual lies inside a verified region, so it is guaranteed to reach the target class, and the method achieves 100% validity.

2.Reusable verification. The costly verification is done once offline and reused across queries, so query time does not depend on model size.

3.Each design choice is tested. Removing verification, adaptive shrinking, or top-k retrieval leads to lower validity, poorer coverage, or much slower queries, showing that each component is useful.

Critical weaknesses

1.Poor proximity. Counterfactual explanations aim for minimal changes, but certified regions are small balls around reference points, so CertCF requires large changes, with an L1 distance even larger than simply returning the nearest reference point.

2.Certified robustness is not evaluated. Certified robustness to input perturbations is claimed in the abstract and contributions, but this option is never enabled in the experiments, which report only empirical robustness, so its cost on proximity and success rate remains unknown.

3.Actionability is not evaluated. Restricting changes to selected features is claimed in the abstract and contributions, yet the Limitations section states that quality evaluation is limited to unconstrained tasks.

4.Missing comparison with verification-based methods. The paper motivates CertCF as a faster alternative to verification-based methods such as MACE and Maragno et al., but includes none of them in the experiments, so neither its speed advantage nor its quality relative to these methods is shown.

Questions for authors

(1)Quality is evaluated only on a two-layer network with 64 and 32 hidden units. How does proximity change as the network becomes deeper or wider?

(2)The paper only compares variants within the LiRPA family on regions of the same size. Since certification is done once offline, could more precise methods, such as PREMAP’s region splitting, certify larger regions and improve proximity?

1 comment

Weakness 1

We agree that CertCF does not have the best proximity. It is designed as a trade-off between data-based and model-based methods (Figure 3a), and optimizing proximity alone yields points that barely cross the decision boundary.

MethodL1 ↓Changed features ↓Emp. robustness ↑log10 LOF ↓Certified L1 radius ↑
CertCF7.658.0394.3%0.0650.467
NN6.9210.7090.3%0.0670.292
FACE9.3312.4291.3%0.1010.463
GS2.573.7278.6%0.2360.073
DiCE4.376.2093.3%0.2590.375

The gap to NN is not caused by the sparsity penalty (without it, L1 is 7.54), and we attribute it to certification and to the finite atlas. In return, CertCF changes fewer features, has a larger post-hoc certified neighborhood and higher robustness, with similar plausibility, and never returns real records. GS and DiCE are closer but much less supported by the data. More anchors improve proximity. On synthetic data, going from 10 to 500 anchors lowers the mean L1 from 28.64 to 23.75 (still decreasing).

Weakness 2

The guarantee follows from the closed form of the eroded region (Eq. 11), and we will state it as a theorem with full proof. We measured its cost on the synthetic benchmark of Appendix F.2 (1,000 queries), and attacked the counterfactuals found without erosion at the same L1 radius (three seeds).

L1 radius δSuccess with erosionMean L1Vulnerable without erosion
0.2100%24.002.3%
1100%25.307.8%
2100%29.3731.5%

Success stays at 100%, at a cost of +1% L1 at δ = 0.2 and +23.7% at δ = 2 (23.75 without erosion), while without erosion attacks flip up to 31.5% of counterfactuals.

Weakness 3

We ran two experiments with the main-benchmark classifiers, queries and hyperparameters. In CertCF, constraints are hard constraints in the projection and hold by construction. With immutable features (sex and race on Adult and COMPAS, age on German Credit and Give Me Some Credit, 2,717 queries), CertCF loses one query (0.04 points of validity, paired L1 +0.73) and NN and FACE lose 0.44 and 0.55 points, with no constraint violations. Adding directional constraints on Give Me Some Credit (DebtRatio and credit utilization may only decrease, 1,000 queries), CertCF keeps 100% success (L1 +24.9%), NN and FACE drop to 89.0% and 88.0%, and GS and DiCE stay at 100% and 99.7%. We will add these results and update the Limitations section.

Weakness 4

We excluded verification-based methods because they cannot answer queries at interactive latency, which we consider essential in practice. MACE and Maragno et al. (2024) solve a new problem over the encoded network for every query. We ran the official MACE implementation on our benchmark classifiers (20 random queries per dataset). With a 10-second budget, all 140 attempts timed out in the first SMT call, so no quality comparison is possible, while CertCF answers every query in 0.35 s on average without model access. This reflects our setup, not MACE's general infeasibility. CertCF's median latency stays near 87.5 ms from 562 to 272,130 parameters and near 0.44 s on CIFAR-10 ResNets up to 532,480 ReLUs (Appendix F). The certified radius in our answer on proximity shows that pointwise validity does not imply a certified neighborhood.

Question 1

We analyzed the 25 networks of Appendix F.2 (depth 1 to 5, width 16 to 256, 1,000 queries each). From depth 1 to 5, mean L1 grows by only 5% (23.04 to 24.19) although the median region radius roughly halves (2.53 to 1.28). Width matters even less (+2% from 16 to 256). Success stays at 100%, and the trend holds without sparsity refinement. We will add these results to the appendix.

Question 2

We tested PREMAP2, which splits on ReLU states. Its branch conditions must be exported as input-space polytopes, which we did under a fixed budget (seven datasets, three repetitions). We compare it with the standard CROWN atlas (all anchors) and, to separate certification precision from anchor loss, with CROWN restricted to the anchors PREMAP2 retains (box domains, mean L1).

DatasetAnchors kept / 300CROWN fullCROWN same anchorsPREMAP2
Adult337.6410.4010.23
COMPAS2171.471.641.63
German1510.7117.7717.61
GMSC611.422.001.94
HELOC3311.0013.7512.01
Lending Club75.4510.7810.28
WBC118.9125.2421.89

At equal atlas size (same anchors), PREMAP2 improves proximity on all datasets (0.5% to 13%), but the export budget loses many anchors, so it remains worse than the full CROWN atlas. On WBC a single anchor survives, so queries to the other class fail (PREMAP2 success 28.6%, 100% elsewhere).

Reviewer_hfJLOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes CertCF, a counterfactual explanation (CE) method for ReLU neural network classifiers that moves the cost of formal verification offline. In an offline phase, it places a ball around each reference point (anchor) predicted as the target class and uses LiRPA, a standard bound-propagation verifier, to cut the ball down to a convex region in which every point is guaranteed to receive the target class. The collection of these regions is stored as an "atlas." At query time, the method retrieves the regions whose anchors are closest to the query and solves a convex projection onto each one under feasibility and actionability constraints, without calling the model. Shrinking each region by a margin δ additionally guarantees robustness to input perturbations of size δ. On seven binary tabular datasets with a small two-layer network, the authors compare against Nearest Neighbor, FACE, Growing Spheres, and DiCE, and report 100% validity over 4,773 queries together with the best plausibility and empirical robustness, while Growing Spheres and DiCE remain better on proximity and sparsity. Ablations and scalability tests, including a CIFAR-10 stress test, are given in the appendix.

Critical strengths
  • The method is clearly described, with honest statements about its limits, for example that the atlas covers only part of the target region and that the robustness guarantee is disabled in the main benchmark.
  • The ablations are thorough and isolate the main design choices: adaptive shrinkage, the certification step against an uncertified and a gradient-based alternative, the projection norm, and the number of retrieved regions.
Critical weaknesses
  • The baselines are few and outdated. All four (Nearest Neighbor, FACE from 2020, Growing Spheres from 2017, DiCE from 2020) are early methods. The most relevant competitors, which the paper itself discusses, are missing: methods with formal validity or robustness guarantees (MACE, PROPLACE, Maragno et al. 2024), robust CE methods (PROBE, CROCO), and generative methods (CCHVAE, VCNet). The main claimed advantage, certified validity and robustness, is therefore only shown against methods that do not aim for it. Also, the proposed method's quality cost (worse performance in distance metrics) is substantial compared with the baselines in the paper.
  • The novelty is limited, as the problem is largely solved and the method mainly applies existing components: Certified validity for ReLU networks is already achieved by exact solver-based methods (MACE; Mohammadi et al. 2021), and certified robustness by PROPLACE and Maragno et al. (2024). Pointwise validity is also easy for any method to guarantee by checking the model's output at the returned point; the Nearest Neighbor baseline reaches 100% as well. Shrinking a region to guarantee robustness to bounded perturbations is a standard step, and region-based or precomputed CE search has been explored before.
Questions for authors

See weaknesses

2 comments

We selected baselines representing the two families CertCF bridges: data-based methods that answer queries without the model (Nearest Neighbor, FACE) and model-based methods that search the input space at query time (Growing Spheres, DiCE).

Verification-based methods. In our view, these methods cannot answer queries at interactive latency, which we consider essential for practical use. They provide formal guarantees, but solve a new problem over the encoded network for every query: MACE through SMT solving, PROPLACE through mixed-integer programming, and Maragno et al. (2024) through query-specific robust optimization. We ran MACE on our frozen benchmark classifiers, with 20 random queries per dataset: under a 10-second per-query budget, all 140 attempts timed out during the first SMT call, whereas CertCF answers every benchmark query in 0.35 s on average. This illustrates the cost of exact verification at every query, which CertCF pays once offline (see our answer on novelty for scalability).

Robust and generative methods. These target different properties. PROPLACE certifies robustness to changes of the model parameters, and PROBE and CROCO provide probabilistic robustness to noisy implementation of the recommended changes. VCNet trains the predictor jointly with the generator, so it cannot explain an already-trained classifier, which is our post-hoc setting. CCHVAE searches the latent space of a separately trained VAE and provides only pointwise validity.

Guarantees against the current baselines. Since pointwise validity can be obtained by any method that checks the model output, we measured the post-hoc certified L1 radius around each returned counterfactual, i.e., the largest neighborhood on which LiRPA certifies the target class.

MethodL1 ↓Changed features ↓Emp. robustness ↑log10 LOF ↓Post-hoc certified L1 radius ↑
CertCF7.658.0394.3%0.0650.467
Nearest Neighbor6.9210.7090.3%0.0670.292
FACE9.3312.4291.3%0.1010.463
Growing Spheres2.573.7278.6%0.2360.073
DiCE4.376.2093.3%0.2590.375

With erosion enabled, CertCF also guarantees a prescribed radius by construction: on our synthetic benchmark (mean L1 about 24), it keeps 100% success up to L1 radius 2, while without erosion up to 31.5% of counterfactuals are changed by attacks at that radius.

Quality cost. We agree that CertCF does not have the best proximity. It is designed as a trade-off between data-based and model-based methods (Figure 3a). Growing Spheres and DiCE are closer, but much less supported by the data, and Growing Spheres is the least robust method, with a certified radius close to zero. Compared with Nearest Neighbor, CertCF is farther on average, but changes fewer features, has a larger certified neighborhood, higher robustness and similar plausibility, and never returns real records. The sparsity penalty does not cause this gap (without it, CertCF's L1 is 7.54), and proximity improves with more anchors: on synthetic data, going from 10 to 500 anchors per class lowers the mean L1 from 28.64 to 23.75, with the curve still decreasing.

Thank you for the response. My concerns regarding novelty and more recent baselines were both unaddressed. The problem targeted in this work, searching counterfactual explanations which satisfy the most fundamental few desirable properties (validity, distance, feasibility), had been well-studied in the literature a few years ago, and the results presented do not clearly distinguish the proposed method from the baselines (which are outdated as mentioned in the review). Therefore, I will keep my score.

Reviewer_i2cpOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes CertCF, which precomputes certified target-class regions using the classifier and a reference dataset, then generates counterfactuals by projecting queries onto these regions without further model access. The authors evaluate the method on seven tabular datasets and provide ablation and scalability studies.

Critical strengths
  • The reusable certified atlas amortizes verification across queries, enabling counterfactual generation without query-time model access.
  • Projection onto certified regions guarantees target validity, while region erosion additionally supports robustness guarantees for prescribed perturbation radii.
Critical weaknesses
  • First, the experiments do not include verification-based or robust counterfactual methods as baselines. Comparisons with these closely related methods under comparable validity and robustness requirements would help clarify the advantages of the proposed approach.
  • Second, the finite atlas restricts the search to precomputed regions and may miss closer counterfactuals. It would be helpful to understand how the number and selection of anchors affect coverage and counterfactual quality.
  • Third, proximity to reference data does not necessarily imply actionable recommendations. Although the method supports feasibility and actionability constraints, the experiments do not show how well it performs when certain features are immutable or subject to directional constraints.
Questions for authors
  • Could the authors clarify the choice of baselines, particularly the omission of verification-based and robust counterfactual methods?
  • Could the authors clarify how the number and selection of anchors affect atlas coverage and counterfactual quality?
  • Do the authors have results evaluating CertCF under feasibility and actionability constraints? For example, in the loan application setting, some attributes such as age and past defaults may need to remain fixed, while debt may only be allowed to decrease.
1 comment

Question 1

We chose baselines representing the two families CertCF bridges: data-based (Nearest Neighbor, FACE) and model-based (Growing Spheres, DiCE). We excluded verification-based methods because they cannot answer queries at interactive latency, which we consider essential in practice. MACE (SMT), PROPLACE (mixed-integer programming) and Maragno et al. (2024) (robust optimization) solve a new problem over the encoded network for every query. We ran MACE on our benchmark classifiers (20 random queries per dataset): with a 10-second budget, all 140 attempts timed out in the first SMT call, while CertCF answers every query in 0.35 s on average without model access, with median latency near 87.5 ms from 562 to 272,130 parameters (Appendix F.2).

Robust methods target other notions: PROPLACE covers model-parameter changes, PROBE and CROCO noisy implementation of the recommended changes. To compare all baselines under this requirement, we measured the post-hoc certified L1 radius (the largest neighborhood on which LiRPA certifies the target class):

MethodValidityPost-hoc certified L1 radius ↑Empirical robustness ↑
CertCF100%0.46794.3%
Nearest Neighbor100%0.29290.3%
FACE98.1%0.46391.3%
Growing Spheres99.6%0.07378.6%
DiCE93.2%0.37593.3%

Pointwise validity thus does not imply a certified neighborhood. With erosion, CertCF guarantees a prescribed radius by construction: on synthetic data (mean L1 about 24) it keeps 100% success up to L1 radius 2, while without erosion attacks flip up to 31.5% of counterfactuals at that radius.

Question 2

Number of anchors. On the synthetic 32-dimensional benchmark (1,000 queries, ten seeds, a different scale from Table 1), we subsampled the full atlas (500 anchors per class) without recertifying the regions. Proximity improves monotonically, with diminishing returns: half the atlas costs about 3% in mean L1, 10 anchors per class 21% (random). Success stays at 100%.

Anchors per classRandom mean L1Farthest-point mean L1
1028.6432.44
2527.2430.52
5026.1828.95
10025.3727.41
25024.4225.47
500 (full atlas)23.7523.75

Selection of anchors. Random selection beats farthest-point sampling at every budget, likely because it follows the data distribution, where the queries also lie. This supports the random selection used in the paper.

Coverage. In volume terms, coverage is tiny: no held-out test point falls inside a certified region. This does not limit success, since a query only needs to be projected onto a region. What the finite atlas limits is optimality: closer counterfactuals may exist outside it. We cannot quantify this gap exactly, but it shrinks as the atlas grows and is still decreasing at 500 anchors per class, while the benchmark uses at most 500 of up to 10,000 reference points per class.

Question 3

We agree that these are different properties: data support comes from the anchors, actionability from hard constraints in the query-time projection, which CertCF satisfies by construction. We ran two experiments with the classifiers, queries and hyperparameters of the main benchmark.

Immutable features. On four datasets (2,717 queries) we fixed sex and race (Adult, COMPAS) or age (German Credit, Give Me Some Credit). CertCF loses one query (0.04 points of validity, paired L1 +0.73), Nearest Neighbor and FACE 0.44 and 0.55 points. No method violates the constraints.

Directional constraints. Following the reviewer's loan example, on Give Me Some Credit (1,000 queries) we fixed age and allowed DebtRatio and credit utilization only to decrease.

MethodSuccess (age fixed)Success (+ directional)Paired L1
CertCF100%100%2.29 → 2.86
Nearest Neighbor99.1%89.0%1.08 → 1.89
FACE98.2%88.0%1.10 → 1.88
Growing Spheres100%100%0.23 → 0.22
DiCE99.6%99.7%0.87 → 0.95

CertCF keeps 100% success (L1 +24.9%), while Nearest Neighbor and FACE lose about 10 points, likely because few reference points satisfy all constraints at once. Past-default features, not fixed here, would use the same equality constraints as age.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.