acceptodds
Under review as a conference paper at ICLR 2027

DASH: Fast, Valid Counterfactuals For Deep Networks Via Batched Directional Search

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 , , 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 of the best heuristic-observed valid distance in of cases, with a median CPU search runtime of  s. PGD-bisect, the baseline with the highest pooled within- coverage, meets this criterion in of cases, with a median runtime of  s. These results show that the proposed search maintains high valid proximity across norms while keeping its search runtime practical.

Primary area:
optimization
Keywords:
Counterfactual explanation, neural networks

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_at98OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes DASH, a batched directional search method for finding nearby counterfactuals that satisfy target predictions and specified actionability constraints in ReLU networks. It combines single-feature perturbations, local gradient steps, factual-origin boundary candidates, beam search, and final bisection refinement. Results demonstrate strong validity, proximity, and runtime performance on mixed-feature tabular tasks. However, baseline fairness, component contributions, and scalability require further validation.

Critical strengths

Clear and practically relevant objective. DASH considers target predictions, feature bounds, immutable features, permitted change directions, and valid categorical assignments, rather than treating a prediction change alone as sufficient.

Strong tabular results. Across 9,000 query–norm cases, DASH returns a valid counterfactual within 5% of the best heuristic-observed distance in 94.6% of cases, with a median search time of 0.061 seconds. Comparisons against certified optima provide additional evidence of proximity quality.

Clearly stated limitations and detailed reporting. The authors acknowledge that DASH does not guarantee global optimality or certify infeasibility. They distinguish failure types and provide implementation details and an ablation of factual-origin anchors.

Critical weaknesses

Inconsistent constraint handling weakens baseline fairness. Appendix B.5 states that FAB handles feature ranges but not other actionability constraints, while DeepFool is unconstrained. Several other baselines repair categorical assignments only after search. DASH enforces constraints throughout search, so validity differences may partly reflect constraint handling rather than search quality. Constraint-aware adaptations of FAB and PGD would provide stronger comparisons.

Novelty and component contributions are insufficiently isolated. Local affine boundary estimates and candidates originating from both the current point and the factual input are closely related to existing minimum-norm attack methods. The factual-origin ablation is useful, but the contributions of Lipschitz-based scales, directional exploration, beam ranking, and batching remain unclear. In particular, the weight-product Lipschitz bounds may become loose with depth; their advantage over simpler step-size schemes should be demonstrated.

Runtime evaluation does not fully measure time to a valid output. PBMC3k outputs undergo an additional marker-constraint completion procedure that may enumerate 28 gene pairs and reevaluate the model, but this cost is excluded from reported runtime. Although shared across methods, its frequency and cost may differ. End-to-end latency should include completion and verification, with precomputation costs reported separately.

Scalability claims need broader support. PGD-bisect achieves 100% valid-within-5% coverage under both ℓ2\ell_2 and ℓ∞\ell_\infty on PBMC3k, exceeding DASH. PBMC3k uses only 50 input features, and all evaluated predictors are fully connected ReLU binary classifiers. Broader applicability to high-dimensional inputs, multiclass tasks, and other architectures remains unestablished.

Specified actionability does not establish real-world feasibility. Feature bounds, directional constraints, and valid one-hot assignments do not ensure that counterfactuals respect feature relationships or feasible interventions. The authors appropriately acknowledge this for PBMC3k, but additional plausibility evaluation or richer joint constraints would strengthen the practical interpretation of the generated explanations.

Questions for authors

see weakness

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

DASH searches for close counterfactuals for ReLU neural networks under feature bounds, immutability, permitted changes, and categorical constraints. It combines coordinate-wise Lipschitz bounds and local affine models to generate anchors, ranks and expands them through beam search, and batches evaluations in CPU and GPU implementations. The evaluation covers four tabular datasets, network depths from 2 to 32, three distance norms, and supplementary PBMC3k and MNIST settings, with nine heuristic baselines and time-limited exact solvers. The authors report valid outputs within 5% of the best heuristic-observed distance on 94.6% of 9,000 tabular query–norm cases, with a median CPU search time of 0.061 seconds, and additional proximity comparisons on solver-certified subsets. These establish empirical performance in the tested settings, with varying results on the supplementary datasets; DASH does not certify global optimality or non-existence.

Critical strengths
  • The real-world examples, clean problem setup, and overview of the literature clearly motivate the problem and situate the approach (Lines 031–052, 054–064). These provide a clear foundation for understanding the intended contribution.
  • Providing both CPU and GPU implementations is a positive practical aspect (Lines 264–268). The paper also honestly acknowledges the absence of global optimality and non-existence guarantees (Lines 478–481).
Critical weaknesses
  • The methodology becomes vague and difficult to follow. Terms and notation such as “beam,” the anchor sets, the actionability map, “small” interventions, and categorical “vertices” need clearer introduction (Lines 134–162). Key explanations of the Lipschitz-bound computation and actionability enforcement are relegated to the appendix; these should be explained in the main text, ideally with a simple network example (Lines 147–152, 234–237). This makes it harder to understand how the core method works.
  • The presentation of the comparisons and efficiency claims needs clarification. The abstract’s transition from “deep neural networks” to “heuristic” versus “exact” methods is confusing; clarify that this distinction concerns counterfactual search methods applied to the networks, including methods such as DiCE (Lines 013–016, 054–064). The abstract should also clarify the role of batching and state the relative runtime improvement, as the introduction does, so readers can assess its significance (Lines 018–026, 073–076).
Questions for authors
  • Clarification: What challenges or limitations arise in enforcing actionability? Appendix A.3 describes feature-wise clipping and permitted one-hot assignments; please clarify the scope and limitations of this enforcement in the main text and limitations discussion (Lines 234–240, 478–482, 726–735).
  • Clarification: How should “small” interventions be understood relative to feature type and domain, and how do the coordinate-wise Lipschitz bounds determine the resulting search scales? Please make this connection clearer in the main text, ideally with a simple worked example (Lines 136, 147–168, 693–699).
Reviewer_oP6yOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes DASH, a heuristic search for counterfactual explanations (CEs) of ReLU networks that tries to find the closest valid CE under ℓ1, ℓ2, or ℓ∞ distance while respecting actionability constraints (feature bounds, immutable features, allowed directions of change, and categorical features). DASH keeps a small set of candidate points and, at each iteration, generates new candidates in three ways: moving one feature at a time by a step sized using a per-feature Lipschitz bound, stepping toward the locally linearized decision boundary from the current candidate, and stepping from the original input toward that same linearized boundary. Every candidate is mapped into the actionable set (by clipping features and using only allowed categories), candidates are ranked by estimated total distance, and a final bisection reduces the distance of the best valid point. DASH is compared with nine heuristic baselines and two time-limited exact solvers on four tabular datasets (HELOC, Give Me Some Credit, Adult, COMPAS), plus PBMC3k and MNIST. The main metric is the share of queries for which a method returns a valid CE within 5% of the best distance found by any heuristic. Pooled over the four tabular datasets, DASH scores highest on this metric under each of the three norms (94.6% across norms vs. 41.1% for the next best, PGD-bisect), but it leads in only 36 of the 60 dataset, norm, and depth settings. On PBMC3k it is best under ℓ1 only, and on MNIST it is outperformed by FAB.

Critical strengths
  • The evaluation is thorough: nine heuristic baselines, exact solvers for certified optima, three distance norms, five network depths, three training seeds, and confidence intervals.
  • The limitations are stated clearly (no optimality guarantee, ReLU networks only), and code, trained models, and all result rows are released.
Critical weaknesses
  • The novelty is limited. No single component is novel: the boundary steps come from DeepFool and FAB (FAB also steps from the original input), the step sizes use standard per-feature Lipschitz bounds, the actionability enforcement is ordinary clipping plus category swaps, and beam search and bisection are standard tools. The new part is combining them into one batched search with a simple distance-plus-progress ranking rule, and only one component is ablated. Therefore, this reads to me as proposing an engineering solution built on existing methods, rather than foundational contribution.
  • The work is not relevant to what CE literature need today. The paper treats CE generation purely as minimum-distance search. Plausibility is never discussed (only a weak proxy appears in appendix tables), diversity is not considered (one CE per query), and robustness of the CEs to model changes is not evaluated. These are all recent topics in CE literature, and the metrics optimized in the paper (validity, proximity/distance, actionability, time) are simply too narrow. Even on distance alone, the advantage is inconsistent, with prior methods matching or beating DASH on HELOC, MNIST, and PBMC3k under ℓ2 and ℓ∞. A faster distance-only solver adds little to the current CE literature, and .
Questions for authors
  • How do DASH's CEs compare with baselines on plausibility measures based on data density (for example LOF), on diversity, and on robustness to model retraining?
  • What is the contribution of each candidate type and of the final bisection step? The appendix only removes the steps taken from the original input and tests one added variant.
1 comment

Thank you for the response. I appreciate the extra experiments evaluating the additional properties including plausibility and robustness (against model retraining), which help to compare DASH against existing methods. However, my main concerns about novelty and relevance (little addition to the current CE literature) remain unaddressed. They are more about the problem studied in the paper and the proposed method itself, rather than the evaluation metrics included. I will keep my current score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.