DASH: Fast, Valid Counterfactuals for Deep Networks via Batched Directional Search
Authors: Shraman Pal, Gabriel Medeiros, Clayton Escouper das Chagas, Can Li
Organizations: Davidson School of Chemical Engineering, Purdue University, West Lafayette, IN 47907, USA · Computer Engineering Department, Instituto Militar de Engenharia, Rio de Janeiro - RJ, Brazil
Counterfactual explanations are most useful when they can be generated with low latency, remain close to the factual input, and satisfy input-domain, categorical, and actionability constraints. Achieving these objectives simultaneously is challenging for deep neural networks. Heuristic methods are often fast but may return invalid counterfactuals, whereas exact methods can certify global proximity but may not finish within practical time limits. We introduce DASH, a batched heuristic search method for finding close, valid, and actionable counterfactuals for deep neural networks under ℓ1, ℓ2, and ℓ∞ objectives. DASH uses directional Lipschitz bounds and local affine models to generate anchors, then ranks and expands promising regions with batched network evaluations. We compare DASH against nine prior heuristic methods and time-limited exact mixed-integer baselines on four tabular datasets, with network depths from 2 to 32, and evaluate scalability on PBMC3k. Across 9,000 tabular query-norm cases, DASH returns a valid counterfactual within 5% of the best heuristic-observed valid distance in 94.6% of cases, with a median CPU search runtime of 0.061 s. PGD-bisect, the baseline with the highest pooled within-5% coverage, meets this criterion in 41.1% of cases, with a median runtime of 0.298 s. These results show that the proposed search maintains high valid proximity across norms while keeping its search runtime practical.
Figures & tables
Figure 1: Anchor generation across ReLU regions. Black dashed lines separate activation regions, the green line is the target boundary, and the shaded region is target-valid. left: One-directional anchors x1 and x2 are in different regions. The gradient at each anchor is illustrated with colored dashed lines. center: Solid arrows show local gradient-based anchors from x1 and x2 ; dashed arrows show factual-origin anchors from the factual input x0 . The latter use radii rfac(x1) and rfac(x2) , as estimates to the target boundary (Eq. 9 ). right: The red anchor will be used for further anchor generation. The blue anchor is the new incumbent xbest .
Figure 2: Tabular performance profiles. Columns show the ℓ1 , ℓ2 , and ℓ∞ objectives; rows show Wm(α) and Jm(t,1.05) . Results pool four datasets, five network depths, and three training seeds. Top-row shading gives 95% bootstrap intervals clustered by trained model (dataset × depth × seed).
Figure 3: Tabular robustness and output outcomes. Left: Percentage-point difference in Wm(1.05) between DASH and the cell-wise best prior heuristic. Parentheses identify that heuristic (W: Wachter, D: DiCE, N: NICE, P: PGD-bisect; FAB is written in full). Right: Final verification outcomes for the methods in the outcome analysis on tabular and PBMC3k queries, pooled across norms. “Only target-valid” denotes a target-valid but constraint-invalid output. MIP-EXP ⋆ covers tabular depths 2 , 4 , and 8 only.
Figure 4: PBMC3k runtime and tabular certified distance. Columns show the ℓ1 , ℓ2 , and ℓ∞ objectives. The upper row reports PBMC3k joint quality-search-runtime profiles after the same output-only marker completion for every method; recorded times exclude completion. The lower row reports the fraction of tabular queries with a valid output within each relative gap to a certified optimum. Certification covers depths 2 , 4 , and 8 ; unsuccessful returns remain in the denominator.
Appendix figures & tables21 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
Value
Beam capacity Kbeam
16
Directional-selection capacity Kdir
16
Iteration limit T
10
Verification margin μ
10−4
CPU tabular directional-screening fraction γ
1
Axis multipliers Λax
{1,2,4,8,16,32}
Appendix
Table 1: DASH search settings.
Dataset
Dim.
Groups
Factual → target
Train / test
Adult
108
8
\leq\50\mathrm{K}\rightarrow>$50\mathrm{K}$
30,162 / 15,060
COMPAS
13
3
recidivated → not recidivated
4,938 / 1,234
GMC
10
0
delinquent → not delinquent
120,000 / 30,000
HELOC
23
0
Bad → Good
7,897 / 1,974
MNIST 3,8
784
0
3→8
11,982 / 1,984
PBMC3k
50
0
other → CD14+ monocyte
2,110 / 528
Appendix
Table 2: Processed datasets and query directions.
Dataset
Immutable features
Directional constraints
Additional constraints
Adult
Age, fnlwgt, race, sex, and native-country features
Education-num is nondecreasing
Categorical groups retain valid one-hot assignments
COMPAS
None beyond feature bounds
Age and priors-count are nondecreasing
Categorical groups retain valid one-hot assignments
GMC
Age, NumberOfTime30-59DaysPastDueNotWorse, NumberOfTime60-89DaysPastDueNotWorse, NumberOfTimes90DaysLate, and NumberOfDependents
RevolvingUtilizationOfUnsecuredLines and DebtRatio are nonincreasing. MonthlyIncome is nondecreasing
None
HELOC
None beyond feature bounds
ExternalRiskEstimate is nondecreasing. NetFractionRevolvingBurden and NetFractionInstallBurden are nonincreasing
None
MNIST
None beyond pixel bounds
None
Every pixel remains in [0,1]
PBMC3k
All genes outside the marker panels are immutable
CD14, LYZ, FCN1, LST1, CTSS, TYROBP, S100A8, and S100A9 are nondecreasing. CD3D, CD3E, LCK, CD2, CD7, IL7R, LTB, and PTPRCAP are nonincreasing
At least two monocyte-marker genes must increase by at least 0.05
Appendix
Table 3: Actionability specifications used in the experiments.
Figure 5: MNIST joint quality-search-runtime profiles. Columns show the ℓ1 , ℓ2 , and ℓ∞ objectives. Each curve gives the fraction of all matched queries returning a valid counterfactual within 5% of the best heuristic-observed valid distance by the indicated search-time threshold.
queries
DASH
no factual-origin
B/T/L
90th
median s: DASH
median s: no factual-origin anchors
ℓ1
300
97.3
97.7
6/290/4
1.000
0.095
0.092
ℓ2
300
96.3
88.7
25/181/94
1.034
0.110
0.105
ℓ∞
300
93.0
84.0
24/194/82
1.051
0.117
0.113
Adult
225
100.0
90.2
15/157/53
1.035
0.159
0.152
COMPAS
225
99.6
100.0
5/209/11
1.000
0.052
0.048
GMC
225
90.2
92.0
17/194/14
1.000
0.057
0.054
Appendix
Table 7: Factual-origin anchor ablation: DASH against the same search without factual-origin anchors (all other components unchanged), tabular datasets, depths 2-32, seed 17, the first 15 factuals of each model (900 queries per arm), paper settings; both arms return a valid counterfactual on every query. Within 5% = valid and within 5% of the best-known distance of Table 5 (DASH and the nine prior methods, full paper run). B/T/L = queries where removing the factual-origin anchors gives a better/tied/worse distance (relative tie band 10−3 ); 90th = 90th percentile of the distance ratio (no factual-origin anchors / DASH). Both arms ran on the same machine, each in its own process, so their runtimes are comparable with each other but not with the other tables.
Figure 6: Performance profile, ℓ1 objective: share of the tabular queries (750 per dataset panel, 3,000 in the pooled panel) where the arm is valid and within (1+τ)× the best heuristic-observed valid distance of Table 11 ( τ=α−1 in the notation of Section 4.2 ; at τ=0 the 10−3 tie band applies), as τ ranges from 0 (the heuristic reference) to 1 (twice that reference). The right end of a curve cannot exceed the arm’s validity. The reference excludes the exact solvers; Table 9 compares with the certified optimum where it exists.
Figure 7: Runtime-quality trade-off, ℓ1 objective, tabular datasets, all depths and seeds pooled. Horizontal axis: median runtime per query (25th-75th percentile whiskers). Vertical axis: mean failure-penalized ratio to the best heuristic-observed valid distance - a valid counterfactual scores its distance divided by the smallest valid distance DASH or any of the nine prior methods found on that query (the reference of Table 11 ); a failure, or a ratio above 5, scores 5. The staircase is the Pareto front, drawn to the axis edges; the shaded region is dominated.
Figure 8: The paired comparison behind Table 12 : for each baseline, one point per instance valid for both arms, DASH’s ℓ1 against the baseline’s (log-log). Points below the diagonal are instances where DASH is closer; the vertical streaks are instances where the baseline returns the same distance for many factuals (a fixed step size or a one-hot flip) while DASH finds a closer point.
Figure 9: Median ℓ1 (top) and median runtime (bottom, log scale) of the valid counterfactuals per arm as network depth grows, ℓ1 objective. DASH + data seed is omitted (it overlaps DASH).
dataset
depth
method
success %
valid %
ℓ1
l0
redund.
yNN
yNN-dist
time (s)
ℓ2
ℓ∞
adult
2
DASH
100
100
0.237
1.0
0.0
0.000
0.344
0.0411
0.237
0.237
adult
2
DASH + data seed
100
100
0.237
1.0
0.0
0.000
0.344
0.0462
0.237
0.237
adult
2
Wachter
100
97
2.229
4.0
1.0
0.000
1.426
0.9827
1.424
1.000
adult
2
DiCE
100
100
0.475
3.0
0.0
0.000
0.401
0.0007
0.293
0.190
adult
2
Greedy*
100
100
0.300
1.0
0.0
0.000
0.400
0.0003
0.300
0.300
adult
2
GS*
100
73
0.388
1.0
0.0
0.000
0.417
0.0589
0.388
0.388
Appendix
Table 15: All tabular cells, ℓ1 objective (medians over valid rows; bold = best per column within a cell among arms with validity ≥ 80%). Medians are over each arm’s own valid rows; an arm with low validity is summarised on an easier subset, so compare arms with different validity through the paired table (Table 12 ) and the best-known table (Table 11 ).
Figure 10: Performance profile, ℓ2 objective (see Figure 6 for the definition).
Figure 11: Runtime-quality trade-off, ℓ2 objective (see Figure 7 for the definition).
Figure 12: Per-instance paired comparison, ℓ2 objective (see Figure 8 for the definition).
Figure 13: Median ℓ2 and runtime versus depth, ℓ2 objective.
dataset
depth
method
success %
valid %
ℓ2
l0
redund.
yNN
yNN-dist
time (s)
ℓ1
ℓ∞
adult
2
DASH
100
100
0.225
3.0
0.0
0.000
0.333
0.0448
0.287
0.216
adult
2
DASH + data seed
100
100
0.227
3.0
0.0
0.000
0.333
0.0502
0.282
0.218
adult
2
Wachter
97
96
1.420
5.0
3.0
0.000
1.425
0.8565
2.224
1.000
adult
2
DiCE
100
99
0.292
3.0
0.0
0.000
0.408
0.0007
0.500
0.190
adult
2
Greedy*
100
100
0.300
1.0
0.0
0.000
0.400
0.0003
0.300
0.300
adult
2
GS*
100
41
0.220
1.0
0.0
0.000
0.296
0.0082
0.220
0.220
Appendix
Table 23: All tabular cells, ℓ2 objective (medians over valid rows; bold = best per column within a cell among arms with validity ≥ 80%). Medians are over each arm’s own valid rows; an arm with low validity is summarised on an easier subset, so compare arms with different validity through the paired table (Table 20 ) and the best-known table (Table 19 ).
Figure 14: Performance profile, ℓ∞ objective (see Figure 6 for the definition).
Figure 15: Runtime-quality trade-off, ℓ∞ objective (see Figure 7 for the definition).
Figure 16: Per-instance paired comparison, ℓ∞ objective (see Figure 8 for the definition).
Figure 17: Median ℓ∞ and runtime versus depth, ℓ∞ objective.
dataset
depth
method
success %
valid %
ℓ∞
l0
redund.
yNN
yNN-dist
time (s)
ℓ1
ℓ2
adult
2
DASH
100
100
0.171
3.0
0.0
0.000
0.407
0.0435
0.553
0.300
adult
2
DASH + data seed
100
100
0.171
3.0
0.0
0.000
0.407
0.0486
0.552
0.300
adult
2
Wachter
96
95
1.000
5.0
3.0
0.000
1.425
0.6108
2.258
1.421
adult
2
DiCE
100
99
0.191
3.0
0.0
0.000
0.411
0.0007
0.451
0.294
adult
2
Greedy*
100
100
0.300
1.0
0.0
0.000
0.400
0.0003
0.300
0.300
adult
2
GS*
100
71
0.228
1.0
0.0
0.000
0.339
0.0041
0.251
0.251
Appendix
Table 31: All tabular cells, ℓ∞ objective (medians over valid rows; bold = best per column within a cell among arms with validity ≥ 80%). Medians are over each arm’s own valid rows; an arm with low validity is summarised on an easier subset, so compare arms with different validity through the paired table (Table 28 ) and the best-known table (Table 27 ).
Counterfactual explanations show how changing an input could alter a model’s prediction, supporting model understanding, auditing, and actionable recourse.
Counterfactual explanations (CE) explain model decisions by identifying input modifications that lead to different predictions. Most existing methods operate at the instance level. Distributional Counterfactual Explanations (DCE) extend this setting by optimizing an optimal transport objective that balances proximity to a factual input distribution and alignment to a target output distribution, with statistical certification via chance constrained bounds. However, DCE relies on gradient based optimization, while many real-world tabular pipelines are dominated by non-differentiable models. We propose DISCOVER, a model-agnostic solver for distributional counterfactual explanations. DISCOVER preserves the original DCE objective and certification while replacing gradient descent with a budgeted propose-and-select search paradigm. It exploits a sample-wise decomposition of the transport objective to compute per-row impact scores and enforce a top-k intervention budget, focusing edits on the most influential samples. To guide candidate generation without predictor gradients, DISCOVER introduces an OT-guided cone sampling primitive driven by input-side transport geometry. Experiments on multiple tabular datasets demonstrate strong joint alignment of input and output distributions, extending distributional counterfactual reasoning to modern black box learning pipelines. A code repository is available at: https://github.com/VALHALLA9/Discover.
Yikai Gu, Lele Cao, Bo Zhao +2
Technical University of Denmark · Scholar7 · Aalto University +1
Counterfactual (CF) explanations identify changes that alter an input's classification. While existing methods produce realistic and low-cost CFs, they often fail to ensure feasibility, by suggesting non-constructive modifications or incompatible with future changes (e.g., changing an individual's race to secure a job offer). We introduce a refinement of CF explanations that explicitly enforces feasibility. Our approach is the first to efficiently generate CFs that are realistic, low-cost and feasible. We accommodate both hard feasible constraints, specified by domain knowledge users, and soft feasible constraints, inferred automatically via causal inference from the dataset. Our method, Feasible Counterfactual Explanations (FCx), is based on a modified Variational Autoencoder (VAE) optimized with a multi-factor loss function. We measure the cost of a change based on the absolute change in values (proximity) as well as the number of features changed (sparsity) while realism is measured based on the LOF for density estimation, guaranteeing that CFs reside in densely populated regions. Extensive experiments on four public datasets show that our approach matches state-of-the-art performance across multiple metrics while guaranteeing feasibility.
Kleopatra Markou, Vana Kalogeraki, Dimitrios Gunopulos
National and Kapodistrian University of Athens, Department of Informatics and Telecommunications, Greece · Athens University of Economics and Business, Department of Informatics, Greece
Visual counterfactual explanations aim to reveal the minimal semantic modifications that can alter a model's prediction, providing causal and interpretable insights into deep neural networks. However, existing diffusion-based counterfactual generation methods are often computationally expensive, slow to sample, and imprecise in localizing the modified regions. To address these limitations, we propose MaskDiME, a simple, fast, yet effective diffusion framework that unifies semantic consistency and spatial precision through localized sampling. Our approach adaptively focuses on decision-relevant regions to achieve localized and semantically consistent counterfactual generation while preserving high image fidelity. Our training-free framework, MaskDiME, performs inference over 30x faster than the baseline and achieves comparable or state-of-the-art performance across five benchmark datasets spanning diverse visual domains, establishing a practical and generalizable solution for efficient counterfactual explanation.
Changlu Guo, Anders Nymark Christensen, Anders Bjorholm Dahl +1