DASH: Fast, Valid Counterfactuals for Deep Networks via Batched Directional Search

Shraman Pal; Gabriel Medeiros; Clayton Escouper das Chagas; Can Li

cs.LGOct 3, 2026

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

Abstract

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 $\ell_1$ , $\ell_2$ , and $\ell_\infty$ 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

Panel of Figure 1 — 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 $x^{1}$ and $x^{2}$ are in different regions. The gradient at each anchor is illustrated with colored dashed lines. center: Solid arrows show local gradient-based anchors from $x^{1}$ and $x^{2}$ ; dashed arrows show factual-origin anchors from the factual input $x^{0}$ . The latter use radii $r_{\mathrm{fac}}(x^{1})$ and $r_{\mathrm{fac}}(x^{2})$ , 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 $x^{\mathrm{best}}$ .

Figure 2: Tabular performance profiles. Columns show the

\ell_{1}

\ell_{2}

, and

\ell_{\infty}

objectives; rows show

W_{m}(\alpha)

and

J_{m}(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

\times

depth

\times

seed).

Figure 3: Tabular robustness and output outcomes. Left: Percentage-point difference in $W_{m}(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

\ell_{1}

\ell_{2}

, and

\ell_{\infty}

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 $K_{\mathrm{beam}}$	$16$
Directional-selection capacity $K_{\mathrm{dir}}$	$16$
Iteration limit $T$	$10$
Verification margin $\mu$	$10^{-4}$
CPU tabular directional-screening fraction $\gamma$	$1$
Axis multipliers $\Lambda_{\mathrm{ax}}$	$\{1,2,4,8,16,32\}$

Appendix

Table 1: DASH search settings.

Dataset	Dim.	Groups	Factual $\rightarrow$ target	Train / test
Adult	108	8	$\leq\$ 50\mathrm{K}\rightarrow>$50\mathrm{K}$	30,162 / 15,060
COMPAS	13	3	recidivated $\rightarrow$ not recidivated	4,938 / 1,234
GMC	10	0	delinquent $\rightarrow$ not delinquent	120,000 / 30,000
HELOC	23	0	Bad $\rightarrow$ Good	7,897 / 1,974
MNIST $3,8$	784	0	$3\rightarrow 8$	11,982 / 1,984
PBMC3k	50	0	other $\rightarrow$ 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.

Method	Configuration
Wachter	10 restarts, learning rate $10^{-3}$ , 100 inner steps, $\lambda$ -growth 5
DiCE	proximity weight $0.5$ , Adam ( Kingma and Ba, 2015 ) learning rate $0.05$ , at most 5,000 iterations
NICE	target-side training pool, norm-specific nearest neighbor, grouped one-hot copying
Growing Spheres	1,000 samples per shell, shell width $0.2$ , 1,000 shells
PGD-bisect	10 restarts, 100 gradient steps, bisection tolerance $10^{-4}$
FMN	1,000 steps, $\alpha:1\rightarrow 0.01$ , $\gamma:0.05\rightarrow 0.001$

Appendix

Table 4: Baseline implementation settings.

Figure 5: MNIST joint quality-search-runtime profiles. Columns show the

\ell_{1}

\ell_{2}

, and

\ell_{\infty}

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
$\ell_{1}$	300	97.3	97.7	6/290/4	1.000	0.095	0.092
$\ell_{2}$	300	96.3	88.7	25/181/94	1.034	0.110	0.105
$\ell_{\infty}$	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,

\ell_{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+\tau)\times

the best heuristic-observed valid distance of Table 11 (

\tau=\alpha-1

in the notation of Section 4.2 ; at

\tau=0

the

10^{-3}

tie band applies), as

\tau

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,

\ell_{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 $\ell_{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

\ell_{1}

(top) and median runtime (bottom, log scale) of the valid counterfactuals per arm as network depth grows,

\ell_{1}

objective. DASH + data seed is omitted (it overlaps DASH).

dataset	depth	method	success %	valid %	$\ell_{1}$	l0	redund.	yNN-dist	time (s)	$\ell_{2}$	$\ell_{\infty}$
adult	2	DASH	100	100	0.237	1.0	0.0	0.344	0.0411	0.237	0.237
adult	2	DASH + data seed	100	100	0.237	1.0	0.0	0.344	0.0462	0.237	0.237
adult	2	Wachter	100	97	2.229	4.0	1.0	1.426	0.9827	1.424	1.000
adult	2	DiCE	100	100	0.475	3.0	0.0	0.401	0.0007	0.293	0.190
adult	2	Greedy*	100	100	0.300	1.0	0.0	0.400	0.0003	0.300	0.300
adult	2	GS*	100	73	0.388	1.0	0.0	0.417	0.0589	0.388	0.388

Appendix

Table 15: All tabular cells,

\ell_{1}

objective (medians over valid rows; bold = best per column within a cell among arms with validity

\geq

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,

\ell_{2}

objective (see Figure 6 for the definition).

Figure 11: Runtime-quality trade-off,

\ell_{2}

objective (see Figure 7 for the definition).

Figure 12: Per-instance paired comparison, $\ell_{2}$ objective (see Figure 8 for the definition).

Figure 13: Median

\ell_{2}

and runtime versus depth,

\ell_{2}

objective.

dataset	depth	method	success %	valid %	$\ell_{2}$	l0	redund.	yNN-dist	time (s)	$\ell_{1}$	$\ell_{\infty}$
adult	2	DASH	100	100	0.225	3.0	0.0	0.333	0.0448	0.287	0.216
adult	2	DASH + data seed	100	100	0.227	3.0	0.0	0.333	0.0502	0.282	0.218
adult	2	Wachter	97	96	1.420	5.0	3.0	1.425	0.8565	2.224	1.000
adult	2	DiCE	100	99	0.292	3.0	0.0	0.408	0.0007	0.500	0.190
adult	2	Greedy*	100	100	0.300	1.0	0.0	0.400	0.0003	0.300	0.300
adult	2	GS*	100	41	0.220	1.0	0.0	0.296	0.0082	0.220	0.220

Appendix

Table 23: All tabular cells,

\ell_{2}

objective (medians over valid rows; bold = best per column within a cell among arms with validity

\geq

Figure 14: Performance profile,

\ell_{\infty}

objective (see Figure 6 for the definition).

Figure 15: Runtime-quality trade-off,

\ell_{\infty}

objective (see Figure 7 for the definition).

Figure 16: Per-instance paired comparison, $\ell_{\infty}$ objective (see Figure 8 for the definition).

Figure 17: Median

\ell_{\infty}

and runtime versus depth,

\ell_{\infty}

objective.

dataset	depth	method	success %	valid %	$\ell_{\infty}$	l0	redund.	yNN-dist	time (s)	$\ell_{1}$	$\ell_{2}$
adult	2	DASH	100	100	0.171	3.0	0.0	0.407	0.0435	0.553	0.300
adult	2	DASH + data seed	100	100	0.171	3.0	0.0	0.407	0.0486	0.552	0.300
adult	2	Wachter	96	95	1.000	5.0	3.0	1.425	0.6108	2.258	1.421
adult	2	DiCE	100	99	0.191	3.0	0.0	0.411	0.0007	0.451	0.294
adult	2	Greedy*	100	100	0.300	1.0	0.0	0.400	0.0003	0.300	0.300
adult	2	GS*	100	71	0.228	1.0	0.0	0.339	0.0041	0.251	0.251

Appendix

Table 31: All tabular cells,

\ell_{\infty}

objective (medians over valid rows; bold = best per column within a cell among arms with validity

\geq

Counterfactual Explanations

Counterfactual explanations show how changing an input could alter a model’s prediction, supporting model understanding, auditing, and actionable recourse.

See all 117 papers

DISCOVER: A Solver for Distributional Counterfactual Explanations
Mar 17, 2026Yikai Gu, Lele Cao, Bo Zhao +2Counterfactual Explanations Black-Box Optimization
Technical University of Denmark · Scholar7 · Aalto University +1
FCx: An algorithm for finding Feasible Counterfactual Explanations
Sep 16, 2026Kleopatra Markou, Vana Kalogeraki, Dimitrios GunopulosCounterfactual Explanations
National and Kapodistrian University of Athens, Department of Informatics and Telecommunications, Greece · Athens University of Economics and Business, Department of Informatics, Greece
MaskDiME: Adaptive Masked Diffusion for Precise and Efficient Visual Counterfactual Explanations
Feb 21, 2026Changlu Guo, Anders Nymark Christensen, Anders Bjorholm Dahl +1Counterfactual Image Generation Counterfactual Explanations
Technical University of Denmark, Denmark

Mar 17, 2026J/K move · Enter open · S save

DISCOVER: A Solver for Distributional Counterfactual Explanations

Yikai Gu, Lele Cao, Bo Zhao, Lei Lei+1

Technical University of Denmark · Scholar7 · Aalto University+1

Counterfactual Explanations Black-Box Optimization

Open paper AskPDF arXiv

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.

Abstract

Counterfactual Explanations

Explore similar work

DISCOVER: A Solver for Distributional Counterfactual Explanations

FCx: An algorithm for finding Feasible Counterfactual Explanations

MaskDiME: Adaptive Masked Diffusion for Precise and Efficient Visual Counterfactual Explanations