acceptodds
Under review as a conference paper at ICLR 2027

When Features Don't Move Alone: Relational Constraint Satisfaction for Counterfactual Explanations

Abstract

Counterfactual explanations (CEs) explain model predictions by identifying input changes that alter the predicted outcome. CE quality spans multiple properties, including validity, proximity, confidence, sparsity, and constraints on feature changes. While boundary and immutability constraints have received considerable attention, relational constraints encoding dependencies among features remain largely unaddressed. We introduce relational constraints as a third constraint type and propose MARBLE, a gray-box method that assembles candidates from observed nearest unlike neighbors values, deterministically repairs constraints, and refines them through an -constrained multi-objective evolutionary search, returning only CEs satisfying all stated constraints and abstaining otherwise. We evaluate MARBLE on four high-stakes real-world use cases: URL phishing detection, credit scoring, ICU survival prediction, and botnet attack detection. On the hardest dataset, MARBLE returns a valid CE satisfying all stated constraints for 91% of queries, compared with at most 4% for five state-of-the-art methods. Across the benchmark, MARBLE outperforms these methods in validity and constraint satisfaction while remaining competitive in confidence, sparsity, and proximity.

Primary area:
interpretability and explainable AI
Keywords:
explainable AI, counterfactual explanations, constraints

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_UcbSOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper looks at relational constraints in counterfactual (CF) explanations and proposes MARBLE to generate CFs that satisfy them alongside the existing requirements. The method builds candidates from nearest unlike neighbors, repairs constraint violations, and refines them with a constrained multi-objective search, and it is evaluated on four tabular datasets across several model families.

Critical strengths
  1. The paper looks into a crucial problem in counterfactual generation;
  2. The empirical study covers a broad range of topics.
Critical weaknesses
  1. It is hard to see the contribution relative to existing work. There is no comparison with SCM or causal-recourse methods, so the empirical comparison only covers methods that do not model relational constraints. There is one direct and close competitor CFM-FW but is not evaluated since the code is not public, which is not a convincing reason in this era of strong AI-assisted coding.
  2. The paper itself has relational constraints highlighted in the title, while it has limited discussion of what relational constraints should look alike, how they should be defined clearly, or other critical issues.
  3. More importantly, MARBLE does not seem tied to relational constraints closely. It looks like a generic constrained optimizer, so the same pipeline could be applied to any task with fitted constraint set, not just CF generation with relational constraints. The paper does not show what is specific to relational constraints here, so it is unclear why MARBLE is the chosen method for the task.
Questions for authors
  1. There are math symbol typos, e.g. X1\mathcal{X}1 (should be X1\mathcal{X}_1?) and vϕv\phi.
  2. "Nearest unlike neighbours (NUNs)" is not a standard concept; please define it explicitly.
  3. In Eq. (1), o1 and g0 look like the same quantity. Is the constraint redundant with the first objective?
  4. Eq. (4) needs more justification: why do we design this decay schedule (from ϵ0\epsilon_0 to zero)?
  5. In Table 1, Val and CS are identical for MARBLE. If they are not mis-recorded, it needs an explanation. The same happens in Table 3 again.
  6. A few pages appear to be changed in rendering, which makes the formatting inconsistent.
  7. The writing is somewhat disjointed; it lacks coherence between some paragraphs/sections.

The rebuttal discussions include new experiments and clarifications to my concerns. However, the contributions are still not clear to me so that I change my score to 2, weak rejection.

4 comments

[W1]: Comparison against CFM-FW

We did include a causal-recourse method in our benchmark: FastAR (Verma et al., 2022) generates recourse with a structural causal model, so its actions respect the causal relations it encodes. Despite this, FastAR reaches a coverage CS of 0.00 on both CTU-13 and LCLD (Table 1). A causal model does not express the inequalities, boolean conditions, and algebraic identities (e.g., derived ratio features) that these datasets require. More generally, SCM-based methods need a causal graph and structural equations, which are not available for these datasets and cannot in general be recovered from observational data (Karimi et al., 2020; Uhler et al., 2013). MARBLE instead takes the domain constraints as stated by the practitioner.

AI-assisted tools can facilitate reimplementation, but they cannot verify details omitted from the published paper. We usually follow the practice of avoiding baseline reimplementations when the official code, exact hyperparameter settings, or data preprocessing pipeline are unavailable, since undocumented choices can affect baseline performance and bias the comparison. Although we understand the value of this comparison, we implemented CFM-FW based on the paper’s description. We have also thus selected and included new and most-recent baselines in our benchmark suggested by other reviewers: i) CERTIFAI (Sharma et al.) (a heuristic-search based CE method), ii) MCCE (Redelmeier et al.) (an instance-based method), and iii) L2C (Vo et al.) (a generative method).

The results are shown in the table below and will be added to the manuscript.

DatasetMethodVal ↑\uparrowConf ↑\uparrowSpars ↓\downarrowProx ↓\downarrowCS ↑\uparrow
URLCERTIFAI1.000.890.9910.470.00
L2C0.980.540.5714.340.28
MCCE1.000.750.334.581.00
CFM-FW1.000.810.121.730.98
MARBLE1.000.920.081.201.00
WIDSCERTIFAI1.000.640.9916.220.00
L2C1.000.970.8137.430.00
MCCE1.000.770.7117.910.30
CFM-FW1.000.770.4510.990.05
MARBLE1.000.920.175.341.00
LCLDCERTIFAI1.000.770.9810.180.00
L2C0.950.850.445.710.00
MCCE1.000.540.351.510.58
CFM-FW1.000.630.160.710.09
MARBLE0.930.750.221.001.00
CTU-13CERTIFAI1.000.830.9937.050.00
MCCE0.800.820.021.170.01
L2C0.940.980.2536.650.00
CFM-FW1.000.770.001.550.10
MARBLE0.910.870.023.341.00

Note: Val refers to validity; Conf to the counterfactual confidence; Spars the sparsity metric using l1l_1 distance; Prox the proximity metric and CS to the constraint satisfaction metric for valid CEs metric.

As shown in the table, while CFM-FW's generic NSGA-II search can find nearby points that flip the classifier (scoring high Validity and low Proximity), it systematically fails to satisfy the relational constraints on complex datasets (e.g., CS = 0.05 on WIDS, 0.09 on LCLD, and 0.10 on CTU-13). It cannot randomly mutate its way onto strict mathematical manifolds without MARBLE's directed repair.

[W2]: Discussion on relational constraints

We agree that the paper should define relational constraints formally, and we will add this definition to Sec. 3.1 with the full grammar in a new appendix section. A relational constraint ϕ\phi is a formula over two or more features. Its terms are arithmetic expressions over features and constants, including sums, products, powers, logarithms, and safe divisions with a fallback value when the denominator is zero. These terms are compared with ≤\leq, <<, or == (optionally within a tolerance τ\tau) and combined with ∧\wedge and ∨\vee. Single-feature bounds are boundary constraints and are handled separately. Each ϕ\phi has a violation function vϕ≥0v_\phi \geq 0 that is zero exactly when ϕ\phi holds (see our answer to Reviewer 2vi2, [W2, Q2], for the per-construct forms).

The five subtypes in Sec. 2 all fall within this grammar. For example, LCLD contains:

  • open_acc <= total_acc — linear inequality
  • (term == 36) || (term == 60) — boolean
  • ratio_open_acc_total_acc = open_acc / total_acc — non-linear
  • ratio_pub_rec_bankruptcies_pub_rec = safediv(pub_rec_bankruptcies, pub_rec, -1) — safe division
  • Loan-amortization formula linking installment, loan amount, interest rate, and term (non-linear, τ=0.01\tau = 0.01)

In practice these constraints come from domain rules and from feature engineering. Derived features computed by the deployment pipeline must stay consistent with their inputs (App. A.2).

[W3]: Contribution on relational constraints

Regarding MARBLE being a "generic" optimizer: MARBLE is explicitly tied to tabular relational constraints. Stage 1 (Admission) uses Nearest Unlike Neighbors (NUN) to assemble candidate features directly from observed tabular data manifolds. Stage 2 (Repair) uses a directed greedy repair operator designed specifically to parse and repair tabular functional dependency graphs. As our ablation study (Table 24) shows, removing these tabular-specific mechanisms causes constraint satisfaction to collapse on complex datasets like CTU-13, proving MARBLE is highly specialized for tabular constraints.

[Q1]: Math typo

We thank the reviewer for catching the math typos. We will fix all typographic errors in the revised manuscript.

[Q2]: Definition of NUN

"Nearest Unlike Neighbor (NUN)" is a concept in counterfactual literature which we cite in the manuscript (Wexler et al., 2019). Furthermore, we defined it in Algorithm 1, Line 5 as {r∈R:f(r)≠f(x)}\{r \in R : f(r) \neq f(x)\}. We agree with the reviewer, that it should be in the main text of Section 3.2 and we will update the manuscript accordingly.

[Q3]: Clarification on o1o_1 and g0g_0

g0g_0 and o1o_1 serve entirely different and non-redundant purposes. While g0g_0 is a hard feasibility boundary constraint requiring the counterfactual to cross the decision boundary (e.g., confidence ≥θ\ge \theta) to be considered valid, o1o_1 is a Pareto optimization objective that pushes valid counterfactuals deeper into the target class to maximize margin robustness.

Without g0g_0, invalid solutions would dominate the Pareto front (by having 0 sparsity and 0 distance). Conversely, as shown in our Objective-space ablation (Table 26), removing o1o_1 causes target confidence to collapse (e.g., from 0.989→0.5910.989 \to 0.591 on URL). They are not redundant.

[Q4]: Justification on Eq. 4

Equation 4 defines an ϵ\epsilon-constrained decay schedule that is a standard and necessary technique in evolutionary optimization. Starting with a larger ϵ\epsilon allows the search to explore slightly infeasible regions, which is crucial for crossing the decision boundary early in the search. Decaying ϵ→0\epsilon \to 0 forces the population to strictly converge onto the feasible manifold by termination.

[Q5]: Clarification on Val and CS in Table 1

In Table 1, Val and CS are identical for MARBLE because MARBLE's archive design guarantees that 100% of its valid counterfactuals satisfy all constraints and MARBLE will fail to generate a counterfactual if it is not valid and do not satisfy all the constraints.

[Q6, Q7]: Rendering and writing

We will address the formatting and rendering issues (such as the varying table font sizes due to \resizebox commands across the appendix) and improve paragraph transitions for better overall coherence.

Reviewer_UcbSOpenReview ↗

Thanks for the response

We thank the authors for the response.

After adding the new experiments, the experimental part looks way better. Also, a few discussions can really help the paper be self-contained and more clear to a broad audience. Thus, I will raise my score to 2.

However, the contribution part, in my opinion, is still weak. I personally still cannot see the non-triviality of the framework. Or, say, the strong indication of why this framework is a breakthrough fit for the problem is not clear.

Thank you for your constructive feedback and for raising your score after reviewing our new experiments and clarifications. Please see our Summary above for how we will foreground MARBLE’s constrained decoding formulation in the Introduction and Section 3 to make the methodological contribution unmistakable in the final manuscript.

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

The authors introduce MARBLE, a gray-box method for generating CEs that satisfy relational constraints between features (linear and non-linear relations, boolean combinations, safe division), on top of the usual immutability and boundary constraints. Candidates are assembled from values observed in the query’s nearest unlike neighbors, then passed through three stages: admission, greedy repair, and an ε-constrained NSGA-III search over confidence, sparsity and proximity with an elite archive. Evaluated on 4 datasets, 5 architectures and 2 tabular foundation models, with stage ablations, a per-category constraint analysis and a sensitivity study. On CTU-13 and LCLD it reports much higher valid, constraint-satisfying coverage than the five baselines.

Critical strengths
  1. The paper addresses a real limitation of existing CE methods. The credit-scoring example makes a good point: editing features independently gives you CEs that flip the prediction but break the relation between open accounts, total accounts and their ratio. Treating relational constraints as a first-class constraint type alongside immutability and boundaries is the right framing when CEs are supposed to describe states that could occur, and it is what makes the paper worth discussing even with the comparison gap below.
  2. The post-hoc repair experiment is the most informative result. Repairing baseline CEs does raise constraint satisfaction, but it often pushes the point back across the decision boundary. DiCE on CTU-13 goes from 0.85 validity to 0.17. That is good evidence that constraints cannot simply be applied after generation, which is the paper’s central design argument and the part I would want kept regardless of the outcome.
Critical weaknesses
  1. I am not sure the baselines show what MARBLE contribution is. None of the five was built to enforce general relational constraints, and in Tab. 4 only FastAR is marked as supporting any of them, so their constraint satisfaction on CTU and LCLD, between 0.00 and 0.34, is close to what one would expect, and the gaps are measured against methods with little or no mechanism for the property being measured. I do expect the results to hold, but as they stand they show that enforcing relational constraints helps, not that MARBLE’s particular design is what produces the gain. A baseline that searches under constraints would separate the two. Runtime is not reported either. Tab. 2 has no timings or query counts, and the only numbers are the donor-pool sweep in App. H for MARBLE alone, where CTU goes from about three minutes to 4.5 hours. Per-query cost next to the baselines would be helpful for reading the coverage gains.
  2. The sparsity objective and the sparsity metric measure different things. Eq. (1) counts nonzero genome entries, App. C.2 counts changed features in the decoded CE, and the two come apart whenever repair touches features the genome left alone, so the optimizer is not minimizing what the benchmark reports. The violation functions also seem underspecified: §3.1 only requires vϕv_\phi to be zero exactly when the constraint holds, and Algorithm 1 takes them as given.

Inconsistencies: Sec. 4 preserves class proportions while App. C.4 says equal representation per predicted class, and C.4 draws the ablation sample from within the benchmark split while App. G says the two do not overlap. Do not affect the suggestion as they are fixable, but as written they affect reproducibility.

Questions for authors
  1. Would it be possible to compare against a constraint-aware search method? The closest I know of is MoEvA2, a multi-objective search over misclassification, distance and constraint violation, which seems to have been run on the same datasets and constraints. It predates the CAA work the appendix cites, and it is an attack rather than a CE method, so it would need adapting. If that is unfair or not feasible, saying why would help, since the appendix sets this work aside because CE generation also optimizes confidence and sparsity, which does not quite address what Table 1 measures. This would most change my assessment.
  2. How far do the two sparsity measures diverge in practice, and why is the objective defined on the genome? Could you also give the form of vϕv_\phi per constraint type with the tolerances used?
  3. Constraint satisfaction is used in two ways: the metrics appendix computes it over valid CEs only, while the abstract and Section 5 report it as the fraction of queries that get a valid, constraint-satisfying CE. These seem to be the same number for MARBLE but not for the baselines, so which one do the reported gaps use?
9 comments

[W1]:

Baselines

We thank the reviewer for this insight. To prove MARBLE's value we first include additional baselines. We included methods that claim to deal with constraints: i) CERTIFAI (Sharma et al.), which uses a genetic algorithm, ii) MCCE (Redelmeier et al.) which uses CART decision trees to sample from the conditional data distribution; iii) L2C (Vo et al.) a generative feature learning and iv) CFM-FW (Liu et al.) a multi-objective counterfactual framework that claims to search under "causal constraints".

The results (in the Table below) prove that despite yielding valid CEs, these baselines fail to satisfy relational constraints on complex datasets.

DatasetMethodVal ↑\uparrowConf ↑\uparrowSpars ↓\downarrowProx ↓\downarrowCS ↑\uparrow
URLCERTIFAI1.000.890.9910.470.00
L2C0.980.540.5714.340.28
MCCE1.000.750.334.581.00
CFM-FW1.000.810.121.730.98
MARBLE1.000.920.081.201.00
WIDSCERTIFAI1.000.640.9916.220.00
L2C1.000.970.8137.430.00
MCCE1.000.770.7117.910.30
CFM-FW1.000.770.4510.990.05
MARBLE1.000.920.175.341.00
LCLDCERTIFAI1.000.770.9810.180.00
L2C0.950.850.445.710.00
MCCE1.000.540.351.510.58
CFM-FW1.000.630.160.710.09
MARBLE0.930.750.221.001.00
CTU-13CERTIFAI1.000.830.9937.050.00
MCCE0.800.820.021.170.01
L2C0.940.980.2536.650.00
CFM-FW1.000.770.001.550.10
MARBLE0.910.870.023.341.00

Note: Val refers to validity; Conf to the counterfactual confidence; Spars the sparsity metric using l1l_1 distance; Prox the proximity metric and CS to the constraint satisfaction for valid CEs only .

  • [CERTIFAI]: Sharma, Shubham, et al. "Certifai: Counterfactual explanations for robustness, transparency, interpretability, and fairness of artificial intelligence models." arXiv preprint arXiv:1905.07857 (2019).
  • [L2C]: Vo, Vy, et al. "Feature-based learning for diverse and privacy-preserving counterfactual explanations." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.
  • [MCCE]: Redelmeier, Annabelle, et al. "MCCE: Monte Carlo sampling of valid and realistic counterfactual explanations for tabular data: A. Redelmeier et al." Data Mining and Knowledge Discovery 38.4 (2024): 1830-1861.
  • [CFM-FW]: Liu, Jinping, et al. "Model-agnostic counterfactual explanation: A feature weights-based comprehensive causal multi-objective counterfactual framework." Expert Systems with Applications 266 (2025): 126063.

Runtimes

We thank the reviewer for this suggestion. We have computed the per-query execution times and will update Table 1 and Appendix D. While MARBLE requires more compute time per query than simple gradient approaches like DiCE, the table below demonstrates it remains highly competitive with generative and tree-based baselines (like L2C and MCCE), while uniquely guaranteeing constraint feasibility.

MethodURL (Val / CS / Time (s))WIDS (Val / CS / Time (s))CTU-13 (Val / CS / Time (s))LCLD (Val / CS / Time (s))
DiCE0.98 / 0.81 / 0.41.00 / 0.54 / 0.90.85 / 0.05 / 42.20.92 / 0.37 / 1.5
NNCE1.00 / 1.00 / 0.11.00 / 0.99 / 0.30.00 / 0.00 / --0.00 / 0.00 / --
C-CHVAE1.00 / 0.00 / 16.891.00 / 0.91 / 18.240.00 / 0.00 / --0.81 / 0.00 / 49.89
CERTIFAI1.00 / 0.00 / 23.91.00 / 0.00 / 23.91.00 / 0.00 / 361.91.00 / 0.00 / 2.1
COUNTERGAN0.85 / 0.56 / 2.00.87 / 0.00 / 0.40.10 / 0.00 / 1.30.08 / 0.00 / 0.4
FastAR0.75 / 0.87 / 63.50.07 / 0.57 / 20.40.40 / 0.00 / 105.00.44 / 0.00 / 42.1
CFM-FW1.00 / 0.98 / 28.951.00 / 0.05 / 49.961.00 / 0.10 / 44.181.00 / 0.09 / 18.20
L2C0.98 / 0.28 / 1.081.00 / 0.00 / 9.850.94 / 0.00 / 353.430.95 / 0.00 / 36.13
MCCE1.00 / 1.00 / 0.461.00 / 0.30 / 3.240.80 / 0.01 / 14.191.00 / 0.58 / 1.12
MARBLE1.00 / 1.00 / 1.21.00 / 1.00 / 2.00.91 / 1.00 / 30.60.93 / 1.00 / 6.2

Note: -- means the method failed to find valid counterfactuals. Val refers to validity; CS refers to Per-CE CS (constraint satisfaction over valid CEs only), and Time refers to the per-query runtime in seconds.

[Q1]: Comparison against MoEvA2

As requested, we evaluated MoEvA2. The results are shown below:

DatasetMethodVal ↑\uparrowConf ↑\uparrowSpars ↓\downarrowProx ↓\downarrowPer-CE CS ↑\uparrowCoverage CS ↑\uparrowRuntime (s) ↓\downarrow
URLMoEvA20.750.910.150.881.000.750.80
MARBLE1.000.920.081.201.001.001.20
WIDSMoEvA20.200.720.301.041.000.200.83
MARBLE1.000.920.175.341.001.002.00
LCLDMoEvA20.450.810.250.410.000.000.91
MARBLE0.930.750.221.001.000.936.20
CTU-13MoEvA20.210.790.010.340.170.041.96
MARBLE0.910.870.023.341.000.9130.60

Val refers to validity; Conf to the counterfactual confidence; Spars the sparsity metric using l1l_1 distance; Prox the proximity metric and CS to the constraint satisfaction metric.

The results show that MoEvA2 struggles with Validity (ranging from 0.20 to 0.75). Furthermore, while it handles simple constraints well (CS = 1.00 on URL/WIDS), it fails on the complex functional identities in LCLD and CTU-13 (CS = 0.00 and 0.17). We will include this discussion in the appendix.

[W2, Q2]: Sparsity objective and sparsity measure different things

We thank the reviewer for this careful reading.

Why the objective is defined on the genome. For each feature jj, the value set VjV_j contains the distinct donor values that differ from the query value xjx_j, so γj≠0\gamma_j \neq 0 holds if and only if the genome changes feature jj. So o2o_2 counts exactly the features the genome substitutes. The two measures can only diverge in one case: the decoding projection recomputes a derived feature whose gene is 0, for example a ratio whose numerator was substituted. The decoded CE then changes that feature, but o2o_2 does not count it.

We define the objective on the genome on purpose. Derived features are consequences of the substituted ones, not independent edits, and counting them would penalize the optimizer for keeping the CE internally consistent. The reported sparsity metric (App. C.2) is computed on the decoded CE for every method, including MARBLE, so the benchmark comparison is not affected. We will state this explicitly in Sec. 3.2.

... Could you also give the form of vϕv_\phi per constraint type with the tolerances used?

Violation functions and tolerances. We follow the constraint grammar and executor of TabularBench. Expressions are built from features, constants, +,−,×,/+,-,\times,/, powers, sums, logarithms, and safe divisions (which return a fallback value when the denominator is zero). The violation functions are:

Constraintvϕ(x)v_\phi(x)
e1≤e2e_1 \leq e_2max⁡(0, e1−e2)\max(0,\, e_1 - e_2)
e1<e2e_1 < e_2max⁡(0, e1−e2+η)\max(0,\, e_1 - e_2 + \eta)
e1=e2e_1 = e_2∣e1−e2∣\lvert e_1 - e_2\rvert
e1=e2e_1 = e_2 with tolerance τ\taumax⁡(0, ∣e1−e2∣−τ)\max(0,\, \lvert e_1 - e_2\rvert - \tau)
ϕ1∧ϕ2\phi_1 \wedge \phi_2vϕ1+vϕ2v_{\phi_1} + v_{\phi_2}
ϕ1∨ϕ2\phi_1 \vee \phi_2min⁡(vϕ1,vϕ2)\min(v_{\phi_1}, v_{\phi_2})

Here η\eta is a small margin for strict inequalities (10−810^{-8} during search, 10−610^{-6} in the TabularBench evaluator). Each case is non-negative and zero exactly when the constraint holds, so vϕ(x)=0v_\phi(x)=0 iff xx satisfies ϕ\phi.

All equalities in the four datasets are exact (τ=0\tau = 0). The one exception is the LCLD amortization identity installment=loanamnt⋅r(1+r)term/((1+r)term−1)\mathrm{installment} = \mathrm{loan_amnt}\cdot r(1+r)^{\mathrm{term}}/((1+r)^{\mathrm{term}}-1), for which TabularBench sets τ=0.01\tau = 0.01. At evaluation, a CE satisfies the relational constraints only if the summed violation is exactly 0. We will add this table, with one example per constraint subtype, as a new appendix section.

[W3]: Inconsistencies

Sec. 4 preserves class proportions while App. C.4 says equal representation per predicted class, and C.4 draws the ablation sample from within the benchmark split while App. G says the two do not overlap.

We thank the reviewer for catching these inconsistencies and will correct these writing bugs. App. C.4 describes the actual protocol; Sec. 4 and App. G are wrong.

  • The 1000-query benchmark sample is stratified with equal representation per predicted class, not proportional to the class distribution.
  • The 100-query ablation sample is drawn from within the benchmark sample, so ablation results are reported on rows the benchmark also covers.
  • The hyperparameter-tuning queries are disjoint from the benchmark sample.

[Q3]: Discrepancy in CS calculation

We thank the reviewer for pointing out this ambiguity. Both quantities appear in the paper, and we will define both explicitly:

  • Coverage CS (all queries). This is used in the abstract, Sec. 5, Table 1 (Val/CS benchmark), Table 3 (per-model) and Table 33 (post-hoc repair). It is the fraction of all 1000 queries for which a method returns a valid CE whose returned valid CEs satisfy every constraint (immutability, boundary, relational). A query a method fails to solve counts as 0, so coverage never exceeds validity.
  • Per-CE CS (valid CEs only). This is used in the per-model tables (App. D), Fig. 2, and the per-subcategory tables. It is the fraction of valid CEs that satisfy the constraints, as defined in App. C.2. It describes how feasible a method's flips are, regardless of how many queries it solves.

All reported gaps use coverage, for every method. For example, "91% vs. at most 4%" on CTU compares MARBLE's coverage (0.91) with DiCE's coverage (0.04). DiCE's per-CE CS on CTU is also low, ranging from 0.00 to 0.10 across models. Every baseline returns one CE per query, so for the baselines coverage equals validity times per-CE CS: DiCE on LCLD has Val 0.92, per-CE CS between 0.35 and 0.40 across models, and coverage 0.34. The two definitions coincide for MARBLE because it only returns constraint-satisfying CEs, which is why Val = CS for MARBLE in Tables 1 and 3. We will state both formulas in Sec. 4 and App. C.2 and in the table captions.

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

The paper addresses the problem of generating counterfactual explanations of tabular data for classification tasks. The key contribution is MARBLE, a method that generates CFs that obey relational constraints between features. The framework combines candidate construction from observed feature values, constraint repair, and multi-objective evolutionary search to find feasible explanations that satisfying domain rules and constraints. Experiments across several datasets and model architectures demonstrate substantially improved constraint satisfaction over the baselines, while achieving competitive explanation quality. Additional ablations and sensitivity studies also investigate the impact of the framework’s components and search settings.

Critical strengths
  1. The paper addresses a well-motivated and practically important problem.
Counterfactual explanations can be misleading when individually reasonable feature changes produce an inconsistent overall sample. The paper clearly motivates why immutability and feature bounds alone are insufficient and why relationships between features should be enforced during generation. Supporting explicit algebraic and logical constraints is valuable for applications where explanations must satisfy known domain rules.

  2. The empirical evaluations are extensive and broadly supports the central feasibility claim.
The main experiments cover four datasets and five neural architectures, with additional results on two tabular foundation models. Additional ablation studies consistently support the benefit of explicit constraint handling in the tested settings and help explain when the different components matter.

Critical weaknesses
  1. Comparisons with the closest existing approaches are insufficient.
The paper considers relatively old baselines, from 2019–2022. While Section 4 explains why methods like MOC, CERTIFAI, and CFM-FW are excluded, some recent relevant works have been omitted, such as PROPLACE [1], MCCE [2], L2C [3], or GeCo [4], which already incorporates user-specified constraints into genetic counterfactual search. These methods may differ in their assumptions and supported relationships, but they would help provide a more direct assessment of where MARBLE provides additional capability or better performance.

  2. The advantage of the complete framework over extensions of existing methods remains unclear.
 Counterfactual generation is essentially a search problem, and additional relational constraints can be incorporated into the search procedures of existing methods. Alternatively, an existing counterfactual method could first generate candidate explanations to narrow the search space, after which MARBLE could refine those candidates while enforcing the constraints. It thus remains unclear whether MARBLE’s complete pipeline offers advantages over these approaches. A more thorough analysis and empirical comparison would help establish the benefits of the full framework and strengthen the justification for the proposed design.

References

[1] Jiang, J., Lan, J., Leofante, F., Rago, A., & Toni, F. (2024, February). Provably robust and plausible counterfactual explanations for neural networks via robust optimisation. In Asian Conference on Machine Learning (pp. 582-597). PMLR.

[2] Redelmeier, A., Jullum, M., Aas, K., & Løland, A. (2024). MCCE: Monte Carlo sampling of valid and realistic counterfactual explanations for tabular data: A. Redelmeier et al. Data Mining and Knowledge Discovery, 38(4), 1830-1861.

[3] Vo, V., Le, T., Nguyen, V., Zhao, H., Bonilla, E. V., Haffari, G., & Phung, D. (2023, August). Feature-based learning for diverse and privacy-preserving counterfactual explanations. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 2211-2222).

[4] Maximilian Schleich, Zixuan Geng, Yihong Zhang, and Dan Suciu. 2021. GeCo: quality counterfactual explanations in real time. Proc. VLDB Endow. 14, 9 (May 2021), 1681–1693. https://doi.org/10.14778/3461535.3461555

Questions for authors

Clarifications on weaknesses would be substantially helpful for the assessment.

4 comments

[W1]: Additional baselines

We thank the reviewer for the suggestions regarding additional and more recent baselines. While MCCE was previously categorized and discussed in our related work (Appendix A.1 and Table 4), we agree that empirical comparisons against these recent methods strengthen the evaluation. We have thus selected and included new and most-recent baselines in our benchmark: i) CERTIFAI (a heuristic-search based CE method), ii) MCCE (an instance-based method), and iii) L2C (a generative method) and iv) CFM-FW (a heuristic-search based method with causal constraints)

The results are shown in the table below and will be added to the manuscript.

DatasetMethodVal ↑\uparrowConf ↑\uparrowSpars ↓\downarrowProx ↓\downarrowCS ↑\uparrow
URLCERTIFAI1.000.890.9910.470.00
L2C0.980.540.5714.340.28
MCCE1.000.750.334.581.00
CFM-FW1.000.810.121.730.98
MARBLE1.000.920.081.201.00
WIDSCERTIFAI1.000.640.9916.220.00
L2C1.000.970.8137.430.00
MCCE1.000.770.7117.910.30
CFM-FW1.000.770.4510.990.05
MARBLE1.000.920.175.341.00
LCLDCERTIFAI1.000.770.9810.180.00
L2C0.950.850.445.710.00
MCCE1.000.540.351.510.58
CFM-FW1.000.630.160.710.09
MARBLE0.930.750.221.001.00
CTU-13CERTIFAI1.000.830.9937.050.00
MCCE0.800.820.021.170.01
L2C0.940.980.2536.50.00
CFM-FW1.000.770.001.550.10
MARBLE0.910.870.023.341.00

Note: Val refers to validity; Conf to the counterfactual confidence; Spars the sparsity metric using l1l_1 distance; Prox the proximity metric and CS to the constraint satisfaction for valid CEs metric.

As shown in the table, while the additional baselines can occasionally optimize specific metrics (such as CERTIFAI and CFM-FW achieving perfect validity, or L2C reaching high confidence on WIDS and LCLD), they consistently fail to satisfy relational constraints on complex datasets. On WIDS and CTU-13, for example, the constraint satisfaction (CS) of CERTIFAI, L2C, and CFM-FW collapses to near zero. In contrast, MARBLE is the only method that robustly enforces strict feasibility (CS ≥0.91\ge 0.91 across all datasets) while simultaneously maintaining highly competitive sparsity, target-class confidence, and proximity. This confirms that MARBLE successfully balances the competing objectives of counterfactual generation without sacrificing the real-world actionability of the resulting explanations.

[W2]: Enforcing constraint satisfaction to baseline candidates

We agree that refining existing baseline candidates is an intuitive alternative, which is why we actually evaluated this exact approach in the submitted manuscript. In Appendix I (Table 33), we tested applying MARBLE's constraint-repair operator as a post-hoc refinement to the counterfactuals generated by all five baselines (DiCE, NNCE, C-CHVAE, CounterGAN, and FastAR).

The results demonstrate that while applying constraints after generation can improve constraint satisfaction in a few simple cases (e.g., C-CHVAE on URL), it generally harms the validity of the counterfactuals. Adjusting feature values to satisfy relational constraints shifts the counterfactual away from the model's decision boundary, causing the prediction to revert to the original class. For example, when repairing DiCE's candidates on the CTU-13 dataset, validity collapses from 0.85 to 0.17. Similarly, C-CHVAE's validity on LCLD drops from 0.81 to 0.24. This experiment proved that relational constraints must be enforced continuously throughout the search process to ensure the final counterfactual remains both valid and feasible. This necessity justifies MARBLE's complete multi-stage design. We will highlight Appendix I more prominently in the main text to ensure this is clear to readers.

Reviewer_JHraOpenReview ↗

Thanks for your response!

Thank the authors for their clarifications and efforts in providing additional empirical evidence. The problem is well-defined and important, and the proposed solution is technically sound. The overall approach follows fairly standard optimization recipes, hence I however still find the methodological novelty somewhat limited, which also seems to be a concern shared by other reviewers. Overall, I consider the paper solid and well-executed, but its contribution appears to be primarily a careful application and combination of existing methods rather than a substantial methodological advance.

Thank you for clarifying your assessment. We understand your view that MARBLE’s use of standard optimization components limits its methodological novelty. Regarding the suggestion that other reviewers share this assessment, Reviewer UcbS asked what makes MARBLE specific to relational constraints, and Reviewer 2vi2 requested a constraint-aware baseline to isolate the contribution of MARBLE’s design. We address both concerns in our responses. Neither reviewer explicitly concluded that the paper’s methodological novelty was insufficient.

Thank you again for your thoughtful feedback and for confirming the importance, technical soundness, and solid execution of our work. Please see our Closing Summary above for how we will sharpen the framing of MARBLE’s methodological contribution in the revised manuscript alongside all new baseline comparisons.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the rebuttal and contribution

Dear Area Chair and Reviewers,

We sincerely thank all three reviewers (2vi2, JHra, and UcbS) and the Area Chair for their thorough engagement throughout the discussion period. By adding five new constraint-aware and evolutionary baselines (CERTIFAI, MCCE, L2C, CFM-FW, and MoEvA2), reporting complete per-query runtimes, formalizing the relational constraint grammar and violation functions, auditing genome sparsity vs. decoded sparsity correlation, and harmonizing all metric definitions (Coverage CS vs. Per-CE CS), we resolved every technical, empirical, and reproducibility question raised during review.

At the end of the discussion, Reviewer 2vi2 raised their score to Weak Accept (3), Reviewer UcbS raised their score after noting that the experimental evaluation and clarifications substantially improved the paper, and Reviewer JHra confirmed that the problem is well-defined and important, the solution is technically sound, and the empirical execution is solid.

Clarifying MARBLE’s Methodological Contribution

The sole remaining concerns from Reviewers JHra and UcbS are methodological novelty: specifically, whether MARBLE represents a substantive methodological advance rather than a combination of standard optimization tools. We clarify this point below for the Area Chair and reviewers, and will update the final manuscript accordingly:

  • Three of our newly evaluated baselines (CERTIFAI, MoEvA2, and CFM-FW) also rely on genetic algorithms or NSGA-based search (NSGA-II, R-NSGA-III). However, their constraint satisfaction (Per-CE CS) collapses to 0.00–0.17 on complex datasets (LCLD and CTU-13). When tabular datasets enforce non-linear algebraic equalities (such as ratios or loan-amortization identities), the valid solution region forms a non-convex submanifold, and our empirical experiments show that standard evolutionary mutations almost never land on this submanifold. Conversely, repairing constraints after search pushes valid counterfactuals back across the decision boundary (e.g., DiCE validity collapses from 0.85 to 0.17 on CTU-13 in Table 33). This highlights the failure of standard optimization recipes to produce feasible, actionable counterfactuals.
  • MARBLE solves this bottleneck by embedding domain constraints directly into the candidate decoding step inside the evolutionary loop. Specifically, it combines two mechanisms: (i) a discrete NUN-donor search representation, which restricts feature edits to observed values from Nearest Unlike Neighbors, and (ii) an in-loop directed repair operator, which deterministically updates dependent features during candidate decoding while ε\varepsilon-constrained NSGA-III drives all remaining relational constraint violations to zero. As established in constrained and gray-box evolutionary optimization (Salcedo-Sanz, 2009; Whitley, 2019), general-purpose black-box optimizers struggle when severe, tightly coupled equality constraints shrink the feasible region to a negligible fraction of the search space; embedding domain-specific repair operators directly into candidate decoding is therefore essential.

In the updated version of the manuscript, we will foreground this constrained decoding formulation in the Introduction and Section 3. We will also include all new baseline tables, runtime comparisons, formal constraint definitions, and metric clarifications so that MARBLE’s methodological and empirical contributions are clear to readers.

We thank the Area Chair and reviewers once again for their time and constructive feedback that substantially improve the paper.

Best regards,

The authors.

References

  • Salcedo-Sanz, Sancho. "A survey of repair methods used as constraint handling techniques in evolutionary algorithms." Computer Science Review 3.3 (2009): 175–192.
  • Whitley, Darrell. "Next generation genetic algorithms: a user’s guide and tutorial." Handbook of Metaheuristics (2019): 245–274.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.