DISCOVER: A Solver for Distributional Counterfactual Explanations

Yikai Gu, Lele Cao, Bo Zhao, Lei Lei, Lei You · 2026

Read DISCOVER: A Solver for Distributional Counterfactual Explanations by Yikai Gu, Lele Cao, Bo Zhao, Lei Lei, Lei You (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16436.txt.

Introduction

Gu and co-authors explain model decisions for whole input distributions at once. Most counterfactual methods work one case at a time. The distributional version balances closeness in inputs against a target output shift. Its gradient method fails on non-differentiable models, though. Their DISCOVER solver swaps gradient descent for a budgeted search. Per-row impact scores focus edits on the samples that matter most. Tests show strong alignment of input and output distributions.

Catalog record

CREATORYikai Gu, Lele Cao, Bo Zhao, Lei Lei, Lei You
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79027
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.16436

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

DISCOVER: A Solver for Distributional Counterfactual Explanations Yikai Gu, Lele Cao, Bo Zhao, Lei Lei, Lei You Abstract 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 sparse 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 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/understanding-ml/DCE . 1]Technical University of Denmark 2]Scholar7 3]Aalto University 4]Xi’an Jiaotong University \correspondence 1 Introduction 1.1 Background and Motivations Counterfactual explanations (CE) are widely used in explainable artificial intelligence (XAI) to provide actionable insights for automated decision systems Dwivedi et al. 2023 ; Verma et al. 2024 . They describe minimal and feasible changes to the input that would lead a model to produce a desired outcome Wachter et al. 2017 . Most CE methods operate at the instance level and are designed to provide recourse for a single instance, often incorporating feasibility constraints and user-specific costs Ustun et al. 2019 ; Karimi et al. 2020 or returning multiple diverse alternatives Mothilal et al. 2020 . However, many real-world applications require population-level interventions rather than isolated edits. For example, policy makers may ask how to shift the risk distribution of a subgroup, or financial institutions may seek systematic recourse strategies that remain consistent with the overall data manifold. Existing global or group-level recourse toolkits partially address this issue by aggregating or organizing per-instance actions Rawal and Lakkaraju 2020 ; Ley et al. 2023 , but their objectives remain defined over individual edits rather than distributions, and they do not directly optimize the shape of the model’s output distribution that stakeholders aim to control. These settings call for distributional counterfactual explanations, where the goal is to generate a counterfactual distribution that both remains close to the factual input distribution and achieves a desired shift in model outcomes. Distributional Counterfactual Explanations (DCE) provides an elegant formulation of this problem using optimal transport You et al. 2025 . DCE balances an input-side transport cost that preserves plausibility with an output-side transport cost that enforces target predictions, together with statistical certification via chance-constrained bounds. This distributional perspective offers a principled alternative to instance-level recourse by explicitly reasoning about population structure and group-level feasibility. Despite its appeal, the practical adoption of DCE solver remains limited by its optimization machinery. This gradient-based algorithm relies on differentiability assumptions and computation graphs, which restrict its applicability to smooth predictive models. While gradient-based optimization is well supported for differentiable models Glorot et al. 2011 ; Baydin et al. 2018 , practical tabular systems are often non-differentiable or black-box systems, including tree ensembles, rule-based preprocessing, and mixed discrete-continuous feature constraints Breiman 2001 ; Friedman 2001 ; Shwartz-Ziv and Armon 2022 ; Erickson et al. 2025 . In such settings, gradient-driven distributional optimization becomes unreliable or infeasible. More importantly, simply replacing gradients with random sampling is not sufficient. Distributional counterfactual generation is a highly non-convex problem over mixed-type spaces, where naive derivative-free search can be prohibitively inefficient and unstable at the population scale. This motivates the need for a solver that is model-agnostic while still exploiting the structure of optimal transport objectives. 1.2 Main Contributions In this work, we propose DISCOVER , a model-agnostic solver for distributional counterfactual explanations that preserves the certified DCE objective while rethinking the optimization paradigm. Our key insight is that optimal transport based distributional objectives admit a practical sample-level structure: global transport shifts can often be attributed to a small subset of influential samples. A comparison of existing counterfactual paradigms and their properties is summarized in Table 1 . DISCOVER operationalizes this insight through per-sample impact scoring and a top- k budget that localizes and edits the most influential individuals, yielding a sparse and interpretable form of distribution-level intervention. Building on this structure, DISCOVER formulates distributional counterfactual generation as an iterative propose-and-select search over candidate counterfactual distributions, where multiple candidate updates are generated and the candidate minimizing the certified DCE objective is selected. DISCOVER further improves black-box search by introducing an input-side OT guidance primitive that exploits the geometry induced by the input-side transport discrepancy to steer proposals toward high-plausibility regions without querying predictor gradients. • Sparse Distributional Editing via OT Decomposition : We reformulate the distributional alignment problem by uncovering a sample-wise decomposition of the OT objective. This allows us to introduce a top- k impact budget, localizing interventions to the most influential samples for sparse and interpretable updates. • Modular Propose-and-Select Architecture : We propose a solver-agnostic framework that separates candidate generation from objective certification. This design enables certified distributional counterfactual generation in non-smooth and mixed-type spaces where traditional gradient-based methods fail. • Predictor-Gradient-Free Geometric Guidance : We introduce an OT-guided cone sampling primitive that leverages input-side transport gradients. This mechanism provides directed, geometry-aware proposals for black-box models, significantly improving search efficiency over naive derivative-free methods. • Unified Solution for Black-Box Pipelines : We demonstrate that DISCOVER achieves strong joint alignment of input and output distributions across differentiable as well as non-differentiable predictors, effectively extending certified distributional reasoning to modern tabular pipelines. Table 1: Comparison of counterfactual paradigms. DISCOVER keeps DCE’s distribution-level objective and certification, while enabling model-agnostic optimization with explicit top- k budgeted editing. Method Dist. goal Certified Model-Agnostic Top- k Instance CE No No Often Yes No Group/Global CE Partial No No No DCE You et al. 2025 Yes Yes No No DISCOVER (ours) Yes Yes Yes Yes 2 Distributional Counterfactual Formulation and Limitations Here we briefly review the distributional counterfactual formulation introduced by DCE to establish notation and certification semantics. We then describe the combined objective used to operationalize the chance constraints, before discussing why the original gradient-based optimization becomes problematic in realistic tabular pipelines. This sets the stage for the solver redesign introduced in the next section. 2.1 Problem Formulation Let b:\mathcal{R}^{d}\to\mathcal{R} be a black-box model. Given a factual input distribution \mathbf{x}^{\prime} with outputs y^{\prime}=b(\mathbf{x}^{\prime}) and a target output distribution y^{\ast} , DCE seeks a counterfactual input distribution \mathbf{x} that remains close to \mathbf{x}^{\prime} while aligning the model output distribution b(\mathbf{x}) with y^{\ast} . The problem is formulated over empirical samples and enforces robustness through chance constraints on both the input and output sides. To measure input proximity, DCE employs the sliced Wasserstein distance \mathcal{SW}^{2} , which remains scalable in high dimensions, while output alignment is measured using the Wasserstein distance \mathcal{W}^{2} , capturing discrepancies at the distributional level rather than

Read the complete text