PACE: A Neuro-Symbolic Framework for Plausible and Actionable Counterfactual Explanations

# PACE: A Neuro-Symbolic Framework for Plausible and Actionable Counterfactual Explanations
Source: [https://arxiv.org/html/2607.01306](https://arxiv.org/html/2607.01306)
Liyanapathiranage Sudeepika Wajirakumari Samarathunga2Martin Thomas Horsch2Fadi Al Machot2 1University of Klagenfurt, Universitätsstraße 65/67, 9020 Klagenfurt am Wörthersee, Austria 2Norwegian University of Life Sciences, Elizabeth Stephansens v\. 15, 1433 Ås, Norway

###### Abstract

Counterfactual explanations have emerged as a practical approach for explaining machine learning predictions by identifying minimal changes to an input instance that would alter a model’s decision\. Although many existing methods successfully generate prediction\-changing alternatives, they often produce unrealistic or infeasible recommendations because they lack explicit mechanisms for incorporating domain knowledge and intervention constraints\. Neuro\-symbolic artificial intelligence offers a promising direction by combining data\-driven predictive models with symbolic reasoning capable of representing human\-understandable rules and feasible actions\. This paper presents PACE, a modular neuro\-symbolic framework for generating feasibility\-aware counterfactual explanations\. The framework separates prediction and reasoning into two complementary components: a neural predictive model responsible for classification and a symbolic reasoning layer that enforces domain\-specific constraints during counterfactual generation\. By explicitly modeling feasible interventions, the framework aims to produce explanations that are more consistent with domain knowledge while remaining interpretable and actionable\. The proposed approach is model\-agnostic and can be adapted to application domains where realistic decision support is required\. To demonstrate the applicability of the framework, a case study is conducted on the Adult Income dataset\. A multilayer perceptron classifier is combined with Answer Set Programming \(ASP\) rules that encode feasible modifications to education, occupation, and working hours while preserving immutable attributes\. Experimental results highlight the trade\-off between counterfactual validity and plausibility and show that incorporating symbolic constraints yields explanations that better satisfy domain\-specific feasibility requirements\. These findings illustrate the potential of neuro\-symbolic methods for supporting the generation of transparent, feasibility\-aware counterfactual explanations in explainable AI systems\.

## 1Introduction

The increasing use of machine learning models in decision\-support systems has intensified the demand for explanations that are transparent, actionable, and trustworthy\[[12](https://arxiv.org/html/2607.01306#bib.bib10),[13](https://arxiv.org/html/2607.01306#bib.bib1),[7](https://arxiv.org/html/2607.01306#bib.bib2)\]\. Among the many approaches proposed in Explainable Artificial Intelligence \(XAI\), counterfactual explanations have attracted particular attention because they provide actionable recommendations by identifying how an instance could be modified to obtain a different prediction\[[9](https://arxiv.org/html/2607.01306#bib.bib15)\]\. Such explanations are especially valuable in domains such as healthcare, finance, education, and public administration, where decisions directly affect individuals\.

Despite their appeal, generating useful counterfactual explanations remains challenging\. A desirable counterfactual should be*valid*,*minimal*, and*plausible*\. However, many existing methods primarily optimize for prediction change and proximity, often producing recommendations that violate domain constraints or cannot realistically be implemented\[[8](https://arxiv.org/html/2607.01306#bib.bib8)\]\. As a result, there is growing interest in approaches that incorporate domain knowledge directly into the explanation process, enabling explanations that are not only valid but also feasible in practice\.

Neuro\-Symbolic Artificial Intelligence \(NeSy\) provides a promising foundation for addressing this challenge by combining the representation\-learning capabilities of neural networks with the reasoning capabilities of symbolic systems\[[4](https://arxiv.org/html/2607.01306#bib.bib9)\]\. Recent work has demonstrated the value of neuro\-symbolic methods for integrating logical constraints, fairness requirements, and domain knowledge into machine learning systems\[[6](https://arxiv.org/html/2607.01306#bib.bib4)\]\. These characteristics make neuro\-symbolic reasoning a natural candidate for feasibility\-aware counterfactual explanation generation\.

This work investigates how symbolic knowledge can be incorporated into the generation of counterfactual explanations through explicit representations of admissible interventions and domain constraints\. We formulate counterfactual generation as a constrained search problem in which candidate explanations must satisfy both predictive objectives and symbolic feasibility requirements\. To explore this idea, we develop PACE, a neuro\-symbolic framework that combines machine learning prediction with symbolic reasoning over a domain\-specific knowledge base\.

A case study is conducted on the Adult Income dataset using a multilayer perceptron \(MLP\) classifier and Answer Set Programming \(ASP\) for symbolic reasoning\. The proposed framework is compared with representative counterfactual generation approaches from different paradigms, including Random Search, Diverse Counterfactual Explanations \(DiCE\)\[[10](https://arxiv.org/html/2607.01306#bib.bib3)\], Wachter\[[14](https://arxiv.org/html/2607.01306#bib.bib12)\], Variational Counterfactual Network \(VCNet\)\[[5](https://arxiv.org/html/2607.01306#bib.bib14)\], and Counterfactual Conditional Heterogeneous Variational Autoencoder \(C\-CHVAE\)\[[11](https://arxiv.org/html/2607.01306#bib.bib13)\]\. The results highlight the trade\-off between validity and plausibility in counterfactual generation and demonstrate the effect of explicitly enforcing symbolic feasibility constraints during the search process\.

The main contributions of this work are as follows:

1. 1\.A modular neuro\-symbolic framework that integrates machine learning models with symbolic reasoning for constrained counterfactual explanation generation\.
2. 2\.A feasibility\-aware formulation of counterfactual generation in which symbolic constraints explicitly define the admissible intervention space\.
3. 3\.An ASP\-based implementation that enforces domain\-specific feasibility constraints during counterfactual generation\.
4. 4\.An empirical evaluation on the Adult Income dataset comparing the proposed framework with Random Search, DiCE, Wachter, VCNet, and C\-CHVAE, highlighting the trade\-off between validity and plausibility\.

The remainder of this paper is organized as follows\. Section[2](https://arxiv.org/html/2607.01306#S2)reviews related work\. Sections 3–5 present the proposed framework, architecture, and implementation\. Section 6 reports the experimental results, Section 7 discusses the findings and limitations, and Section 8 concludes the paper\.

## 2Related Work

Existing counterfactual generation methods can be broadly grouped into three categories\. The first category comprises optimization\-based approaches, such as the method of Wachter et al\.\[[14](https://arxiv.org/html/2607.01306#bib.bib12)\]and DiCE\[[10](https://arxiv.org/html/2607.01306#bib.bib3)\]\. These methods search for prediction\-changing instances while minimizing changes to the original input and, in the case of DiCE, encouraging diversity among the generated explanations\. Although effective at finding counterfactuals, feasibility is typically handled as a soft constraint rather than being explicitly guaranteed\. The second category includes generative approaches that learn the data manifold and generate realistic candidate explanations\. Representative examples include C\-CHVAE\[[11](https://arxiv.org/html/2607.01306#bib.bib13)\], which searches in a latent representation space, and more recent generative methods such as VCNet\[[5](https://arxiv.org/html/2607.01306#bib.bib14)\]\. These approaches improve realism by constraining counterfactuals to remain close to the data distribution, but they generally rely on statistical regularities rather than explicit domain knowledge\. A third line of research incorporates symbolic reasoning and domain constraints into counterfactual generation\. Bertossi and Reyes\[[3](https://arxiv.org/html/2607.01306#bib.bib5)\]demonstrate that answer\-set programs can be used to declaratively specify counterfactual interventions on entities under classification, reason about them, and include domain knowledge through query answering\. More broadly, neuro\-symbolic AI combines the representation\-learning capabilities of neural networks with the transparency and reasoning capabilities of symbolic systems\[[1](https://arxiv.org/html/2607.01306#bib.bib6)\]\. Recent work has integrated counterfactual fairness into the neurosymbolic framework of Logic Tensor Networks \(LTN\), demonstrating advantages including intrinsic interpretability and flexibility in handling subgroup fairness\[[6](https://arxiv.org/html/2607.01306#bib.bib4)\]\. Despite these advances, a gap remains between high\-validity counterfactual generation methods and approaches that explicitly enforce feasibility\. Optimization\-based and generative techniques often treat actionability as a secondary objective, while symbolic approaches frequently focus on intervention analysis rather than explanation generation for predictive models\. Consequently, many existing methods may generate counterfactuals that successfully change predictions but violate domain\-specific requirements\.

## 3Methodology

### 3\.1Problem Formulation

We formalize the generation of a plausible counterfactual explanation as a constrained search problem over a domain\-restricted input space\. Letf:𝒳→𝒴f:\\mathcal\{X\}\\to\\mathcal\{Y\}denote a trained, black\-box predictive model that maps an input instance𝐱∈𝒳\\mathbf\{x\}\\in\\mathcal\{X\}to a discrete categorical outcomey∈𝒴y\\in\\mathcal\{Y\}\. Given a specific factual instance𝐱\\mathbf\{x\}for which the model yields an initial predictionf​\(𝐱\)=yf\(\\mathbf\{x\}\)=y, the objective is to find a counterfactual instance𝐱c​f\\mathbf\{x\}^\{cf\}that alters the model’s classification to a target outcomeyc​f≠yy^\{cf\}\\neq y\.

To ensure the explanation is practical for an end user, the transition from𝐱\\mathbf\{x\}to𝐱c​f\\mathbf\{x\}^\{cf\}must minimize a distance metric that quantifies the magnitude of the applied modifications while remaining strictly within the set of valid states\. Formally, the counterfactual explanation𝐱c​f\\mathbf\{x\}^\{cf\}is defined as the solution to the following constrained formulation:

𝐱c​f=arg⁡min𝐱′∈Ω⁡d​\(𝐱,𝐱′\)\\mathbf\{x\}^\{cf\}=\\arg\\min\_\{\\mathbf\{x\}^\{\\prime\}\\in\\Omega\}d\(\\mathbf\{x\},\\mathbf\{x\}^\{\\prime\}\)\(1\)
subject to the prediction\-flip condition:

f​\(𝐱c​f\)≠f​\(𝐱\)f\(\\mathbf\{x\}^\{cf\}\)\\neq f\(\\mathbf\{x\}\)\(2\)
whereΩ⊆𝒳\\Omega\\subseteq\\mathcal\{X\}represents the feasible intervention space determined by domain\-specific rules\. In this work, the distanceddis instantiated as the number of modified features,

d​\(𝐱,𝐱′\)=∑j𝟙​\[xj≠xj′\],d\(\\mathbf\{x\},\\mathbf\{x\}^\{\\prime\}\)=\\sum\_\{j\}\\mathbb\{1\}\\\!\\left\[x\_\{j\}\\neq x^\{\\prime\}\_\{j\}\\right\],\(3\)so that minimizingddcorresponds to minimizing the number of interventions \(the minimality criterion\)\. The budgetKKin the search procedure directly bounds this count\. In this formulation, the predictive modelffis treated as an oracle that evaluates candidates generated within the valid subspaceΩ\\Omega\. The objective separates the verification of semantic consistency, which is handled implicitly via restriction toΩ\\Omega, from the minimization of feature modifications, which is handled by the search metricdd\.

### 3\.2Symbolic Constraint Modeling

The feasible intervention spaceΩ\\Omegais defined by a declarative symbolic knowledge base that encodes background information, logic rules, and structural dependencies governing the domain attributes\. In practical explanation contexts, features cannot be modified uniformly or independently\. We partition the feature space into immutable attributes𝒳I\\mathcal\{X\}\_\{I\}and editable attributes𝒳E\\mathcal\{X\}\_\{E\}, such that𝒳=𝒳I∪𝒳E\\mathcal\{X\}=\\mathcal\{X\}\_\{I\}\\cup\\mathcal\{X\}\_\{E\}and𝒳I∩𝒳E=∅\\mathcal\{X\}\_\{I\}\\cap\\mathcal\{X\}\_\{E\}=\\emptyset\. Immutable attributes represent inherent properties that cannot be changed by user intervention or environmental drift, enforcing a hard constraint where𝐱i′=𝐱i\\mathbf\{x\}^\{\\prime\}\_\{i\}=\\mathbf\{x\}\_\{i\}for alli∈𝒳Ii\\in\\mathcal\{X\}\_\{I\}\. Editable attributes represent features that are susceptible to modification, subject to directional constraints and relational dependencies\.

The symbolic knowledge base maps these attributes to logical predicates and evaluates candidates against a system of constraints\. Letℛ=\{R1,R2,…,Rm\}\\mathcal\{R\}=\\\{R\_\{1\},R\_\{2\},\\dots,R\_\{m\}\\\}be a set of symbolic rules representing domain knowledge\. A rule can represent a directional invariant, preventing a feature from changing in an impossible direction, or a relational invariant, specifying that a change in one feature necessitates a corresponding change in another\. The feasible space is therefore defined as:

Ω=\{𝐱′∈𝒳∣∀i∈𝒳I,𝐱i′=𝐱i∧∀Rk∈ℛ,𝐱′⊧Rk\}\\Omega=\\\{\\mathbf\{x\}^\{\\prime\}\\in\\mathcal\{X\}\\mid\\forall i\\in\\mathcal\{X\}\_\{I\},\\mathbf\{x\}^\{\\prime\}\_\{i\}=\\mathbf\{x\}\_\{i\}\\;\\wedge\\;\\forall R\_\{k\}\\in\\mathcal\{R\},\\mathbf\{x\}^\{\\prime\}\\models R\_\{k\}\\\}\(4\)
where𝐱′⊧Rk\\mathbf\{x\}^\{\\prime\}\\models R\_\{k\}denotes that the candidate instance satisfies the logical constraintRkR\_\{k\}\. By utilizing a symbolic reasoning engine to construct and evaluate Equation[4](https://arxiv.org/html/2607.01306#S3.E4), the framework eliminates invalid areas of the unconstrained space𝒳\\mathcal\{X\}\. This symbolic filtering restricts the downstream evaluation exclusively to candidates that respect the causal and logical axioms of the application domain\.

### 3\.3Counterfactual Search Procedure

The framework operates via an iterative generate\-and\-verify search loop that systematically expands the intervention distance until an optimal prediction\-changing instance is identified\. The procedure begins by translating the factual instance𝐱\\mathbf\{x\}into a set of symbolic facts\. The symbolic reasoner utilizes these facts along with the rule baseℛ\\mathcal\{R\}to establish the immutable baseline and map out valid paths of modification within the editable subspace𝒳E\\mathcal\{X\}\_\{E\}\.

The search space is structured incrementally based on an explicit budget constraintKK, which restricts the maximum number of simultaneous feature alterations or the maximum allowable distance metric value\. At each iteration, the symbolic engine acts as a generator, producing a set of candidate interventions that satisfy all constraints inΩ\\Omegawithin the current budgetKK\. Because the framework prioritizes sparse explanations, the search starts with a minimal budget, targeting single\-attribute modifications before exploring multi\-attribute combinations\.

Once a batch of feasible candidates is generated, they are mapped back into the format required by the predictive model\. The modelffperforms a forward evaluation on each candidate to check the prediction\-flip condition specified in Equation[2](https://arxiv.org/html/2607.01306#S3.E2)\. If a single candidate or multiple candidates satisfy the condition, the search terminates, and the framework returns the candidate𝐱c​f\\mathbf\{x\}^\{cf\}that minimizesd​\(𝐱,𝐱′\)d\(\\mathbf\{x\},\\mathbf\{x\}^\{\\prime\}\)\. If none of the generated candidates succeed in flipping the prediction offf, the search budgetKKis incrementally increased, expanding the search radius withinΩ\\Omegato allow for broader or more complex attribute modifications\. This process repeats until a valid counterfactual is found or the maximum search bound is reached, ensuring that the returned explanation represents the sparsest possible intervention that achieves the target classification\.

## 4Case Study: Counterfactual Explanations for Income Classification

To demonstrate the practical applicability of the proposed neuro\-symbolic framework, we consider a counterfactual explanation task based on the Adult Income dataset\[[2](https://arxiv.org/html/2607.01306#bib.bib11)\]\. The objective is to generate feasible and interpretable counterfactual explanations for a binary income classification model while respecting domain\-specific constraints on feature modifications\.

The Adult Income dataset is a widely used benchmark for tabular classification and explainable artificial intelligence \(XAI\) research\. The prediction task consists of determining whether an individual’s annual income exceeds $50,000 based on demographic and employment\-related attributes\. Following data cleaning and the removal of records containing missing categorical values, the resulting dataset contains 30,718 instances\. The target variable is represented as a binary class indicating whether income is less than or equal to $50K or greater than $50K\.

The dataset is partitioned using a stratified train\-test split, yielding 24,574 training instances and 6,144 testing instances\. Stratification preserves the original class distribution, where approximately 75% of instances belong to the lower\-income category\. To maintain interpretability and facilitate symbolic reasoning, only a subset of five features is used in this case study, as detailed in Table[1](https://arxiv.org/html/2607.01306#S4.T1)\. These features represent different attribute types commonly encountered in counterfactual generation problems, including immutable personal characteristics, categorical variables, and continuous variables\.

Table 1:Features used in the case study\.Numerical attributes are standardized prior to model training, while categorical variables are transformed using one\-hot encoding\. The symbolic component, however, operates on the original human\-readable feature values to preserve interpretability during counterfactual generation\.

### 4\.1Predictive Model

The neural component of the framework is implemented as a multilayer perceptron \(MLP\) classifier\. The model is trained once and subsequently treated as a fixed predictive function during counterfactual generation; model parameters remain unchanged throughout the explanation process\.

Formally, let

fθ:𝒳→𝒴f\_\{\\theta\}:\\mathcal\{X\}\\rightarrow\\mathcal\{Y\}\(5\)denote the trained classifier parameterized byθ\\theta, where𝒳\\mathcal\{X\}is the feature space and𝒴=\{0,1\}\\mathcal\{Y\}=\\\{0,1\\\}represents the two income classes\. Given an instance𝐱∈𝒳\\mathbf\{x\}\\in\\mathcal\{X\}, the model prediction is defined as

y=fθ​\(𝐱\)\.y=f\_\{\\theta\}\(\\mathbf\{x\}\)\.\(6\)The structural and training configuration of this predictive model is summarized in Table[2](https://arxiv.org/html/2607.01306#S4.T2)\. The classification accuracy is 0\.82\.

Table 2:Configuration of the predictive model\.
### 4\.2Symbolic Knowledge Base

The symbolic component defines the space of admissible interventions\. Rather than allowing arbitrary feature modifications, the framework incorporates domain knowledge through explicit symbolic constraints\. These constraints determine which attributes may be modified and how such modifications may occur\.

Let𝒞=\{c1,c2,…,cm\}\\mathcal\{C\}=\\\{c\_\{1\},c\_\{2\},\\ldots,c\_\{m\}\\\}denote the set of symbolic constraints\. The feasible intervention spaceΩ\\Omegais defined as

Ω=\{𝐱′\|cj​\(𝐱′\)=1,∀cj∈𝒞\}\.\\Omega=\\left\\\{\\mathbf\{x\}^\{\\prime\}\\;\\middle\|\\;c\_\{j\}\(\\mathbf\{x\}^\{\\prime\}\)=1,\\forall c\_\{j\}\\in\\mathcal\{C\}\\right\\\}\.\(7\)Here,𝒞\\mathcal\{C\}is the case\-study instantiation of the general rule baseℛ\\mathcal\{R\}defined in Section 3, specialized to the constraints of the Adult Income task\. As a result, only candidate counterfactuals belonging toΩ\\Omegaare considered valid during the search process\. The concrete symbolic rules used in this case study are summarized in Table[3](https://arxiv.org/html/2607.01306#S4.T3)\.

Table 3:Symbolic constraints used for counterfactual generation\.The education attribute is modeled as an ordered progression structure in which transitions are allowed only between neighboring educational levels\. Similarly, occupation changes are restricted to predefined transition pairs representing plausible career movements\. Weekly working hours may increase or decrease only within a limited range, preventing unrealistic recommendations \(see Appendix for additional details\)\.

### 4\.3Counterfactual Search Process

For the income classification task, counterfactual generation follows the constrained formulation introduced in Section 3 \(Equations[1](https://arxiv.org/html/2607.01306#S3.E1)and[2](https://arxiv.org/html/2607.01306#S3.E2)\): given an original instance𝐱\\mathbf\{x\}and its predictionfθ​\(𝐱\)f\_\{\\theta\}\(\\mathbf\{x\}\), we search for the closest instance𝐱c​f∈Ω\\mathbf\{x\}^\{cf\}\\in\\Omegathat flips the prediction, whereΩ\\Omegais the feasible intervention space defined by the symbolic knowledge base of Section 4\.2\.

The search procedure follows a budget\-based strategy\. Candidate explanations are first generated with the smallest possible intervention budget\. If no prediction\-changing counterfactual is found, the budget is gradually increased\. This process prioritizes sparse explanations that require only a small number of feature modifications\.

### 4\.4Experimental Setup

The proposed framework is compared against several representative counterfactual generation approaches\. DiCE is evaluated using its official implementation, while Wachter\-style, VCNet\-style, and C\-CHVAE\-style baselines are simplified implementations designed to capture the core search principles of their respective methods rather than exact reproductions of the original algorithms\. An unconstrained random\-search baseline is also included for comparison\. All methods operate under comparable evaluation settings on the same test instances\. The evaluation focuses on five complementary performance metrics:

Validity:The proportion of instances for which a prediction\-changing counterfactual is successfully discovered\.

Minimality:The average number of features modified across the generated counterfactuals\.

Plausibility:The proportion of generated explanations that strictly satisfy the defined symbolic constraints\.

Runtime:The average computational time required to generate an explanation per instance\.

Iterations to Flip:The average number of candidate evaluations required before a valid prediction change is achieved\.

This case study provides a concrete instantiation of the proposed neuro\-symbolic framework, enabling an empirical investigation into the trade\-offs between counterfactual validity and symbolic plausibility in realistic decision\-support scenarios\.

## 5Results

The experimental evaluation compares the proposed PACE framework against five baselines: an unconstrained Random Search strategy, DiCE, a Wachter\-style optimization method, and two generative approaches \(VCNet\-style and C\-CHVAE\-style\)\. A total of 1,000 unseen test instances were evaluated\. The quantitative results are summarized in Table[4](https://arxiv.org/html/2607.01306#S5.T4)\.

Table[4](https://arxiv.org/html/2607.01306#S5.T4)reveals a clear trade\-off between validity and plausibility in counterfactual generation\. Random Search and DiCE achieve the highest validity scores \(0\.778 and 0\.742, respectively\), indicating a greater ability to identify prediction\-changing interventions\. However, both methods exhibit very low plausibility scores \(0\.027 and 0\.042\), suggesting that many generated counterfactuals violate the domain\-specific feasibility constraints defined for this case study\.

In contrast, PACE achieves perfect plausibility by restricting the search process to interventions that satisfy the symbolic constraints\. As a result, all generated explanations remain consistent with the admissible intervention space defined by the knowledge base\. PACE also generates relatively compact counterfactuals, requiring 1\.242 feature modifications on average, fewer than Random Search, DiCE, VCNet\-style, and C\-CHVAE\-style methods\.

Among the baseline methods, VCNet\-style achieves the strongest combination of validity and plausibility, while C\-CHVAE\-style provides intermediate performance\. The Wachter\-style baseline achieves the lowest validity and plausibility scores, reflecting the difficulty of unconstrained optimization in producing feasible interventions within this domain\.

As a descriptive summary of the trade\-off between validity and plausibility, Table[4](https://arxiv.org/html/2607.01306#S5.T4)also reports the product of these two metrics\. This composite metric is reported only as a descriptive summary of the observed trade\-off\. Under this criterion, PACE achieves the highest score \(0\.240\), reflecting its strong compliance with the symbolic constraints despite lower validity than unconstrained approaches\.

Table 4:Comparison of counterfactual generation methods on 1,000 Adult Income test instances\.
## 6Discussion and Additional Analysis

Plausibility in this study is defined with respect to the symbolic constraints encoded in the knowledge base\. Consequently, the perfect plausibility achieved by PACE is expected by construction\. To separate the contribution of the constraints from that of symbolic search, we evaluated all methods on the same feasible intervention spaceΩ\\Omega\.

Table 5:Matched\-constraint comparison on 200 Adult Income test instances \(budgetK=2K\{=\}2,500500candidates per instance\)\. All three methods are restricted to the same feasible setΩ\\Omega:*blind \+ reject*proposes constraint\-unaware candidates and discards infeasible ones,*search inΩ\\Omega*samples only feasible candidates, and*PACE*enumeratesΩ\\Omegaexhaustively\.*Feasible rate*is the fraction of proposals lying inΩ\\Omega\. Plausibility is1\.01\.0for all methods by construction once they shareΩ\\Omega\.As shown in Table[5](https://arxiv.org/html/2607.01306#S6.T5), plausibility becomes identical once all methods share the same feasible set, and random search restricted toΩ\\Omegaachieves the same validity and minimality as PACE\. This suggests that the plausibility gains primarily arise from explicit constraint specification, while the low feasible rate of unconstrained search explains the poor compliance of unconstrained baselines\.

The contribution of symbolic search becomes apparent when the feasible intervention space grows\. Figure[1](https://arxiv.org/html/2607.01306#S6.F1)and Table[6](https://arxiv.org/html/2607.01306#S6.T6)compare exhaustive search with random sampling under a fixed candidate budget\.

![Refer to caption](https://arxiv.org/html/2607.01306v1/omega.png)Figure 1:Validity versus feasible\-set size\|Ω\|\|\\Omega\|\.Table 6:Validity as the feasible set grows, for exhaustive search \(a verified proxy for PACE\) versus random search with a fixed budget ofN=80N\{=\}80candidates\. The feasible set is enlarged by widening the admissible transition neighbourhoods to graph distanceww;*Mean\|Ω\|\|\\Omega\|*is the resulting average feasible\-set size and*Gap*is the validity difference \(exhaustive−\-random\)\. Thew=1w\{=\}1row corresponds to the base constraints of Table[4](https://arxiv.org/html/2607.01306#S5.T4); it is computed here on the scalability sample and is not directly comparable to the 200\-instance matched run in Table[5](https://arxiv.org/html/2607.01306#S6.T5)\.For small feasible sets, exhaustive and random search perform similarly\. As\|Ω\|\|\\Omega\|increases, exhaustive search achieves higher validity, indicating that symbolic search contributes completeness through systematic exploration of the admissible intervention space\.

Finally, we evaluated plausibility using an external criterion independent of the symbolic rules\. The mean distance to thek=5k=5nearest training neighbours was0\.3540\.354for PACE counterfactuals and0\.9440\.944for unconstrained search, indicating that the imposed constraints produce counterfactuals substantially closer to the empirical data manifold\.

Several limitations should be acknowledged\. The evaluation was conducted on a single benchmark dataset and relied on manually specified constraints\. Future work should investigate additional datasets, richer forms of domain knowledge, automated constraint acquisition, and more complex relational and temporal constraints\.

## 7Conclusion

This paper presented PACE, a neuro\-symbolic framework for generating feasibility\-aware counterfactual explanations through the integration of machine learning and symbolic reasoning\. Counterfactual generation was formulated as a constrained search problem in which candidate explanations must satisfy both predictive objectives and domain\-specific intervention constraints\.

The framework was evaluated on the Adult Income dataset using a multilayer perceptron classifier and Answer Set Programming\. A comparison with Random Search, DiCE, Wachter\-style, VCNet\-style, and C\-CHVAE\-style baselines on 1,000 test instances revealed a clear trade\-off between validity and plausibility\. While unconstrained and generative approaches achieved higher validity, they frequently produced explanations that violated the symbolic feasibility constraints\. In contrast, PACE generated counterfactuals that satisfied all specified constraints and required relatively few feature modifications on average, reflecting the explicit enforcement of feasibility requirements during the search process\.

Future work will explore richer forms of symbolic knowledge, automated constraint acquisition, and evaluation across additional datasets and application domains\.

## References

- \[1\]K\. Acharya and H\. Song\(2025\)A comprehensive review of neuro\-symbolic ai for robustness, uncertainty quantification, and intervenability\.Arabian Journal for Science and Engineering,pp\. 1–33\.Cited by:[§2](https://arxiv.org/html/2607.01306#S2.p1.1)\.
- \[2\]B\. Becker and R\. Kohavi\(1996\)Adult\.Note:UCI Machine Learning RepositoryDOI:https://archive\.ics\.uci\.edu/dataset/2/adultCited by:[§4](https://arxiv.org/html/2607.01306#S4.p1.1)\.
- \[3\]L\. Bertossi and G\. Reyes\(2021\)Answer\-set programs for reasoning about counterfactual interventions and responsibility scores for classification\.InInternational Conference on Inductive Logic Programming,pp\. 41–56\.Cited by:[§2](https://arxiv.org/html/2607.01306#S2.p1.1)\.
- \[4\]A\. d\. Garcez and L\. C\. Lamb\(2023\)Neurosymbolic ai: the 3 rd wave\.Artificial Intelligence Review56\(11\),pp\. 12387–12406\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p3.1)\.
- \[5\]V\. Guyomard, F\. Fessant, T\. Guyet, T\. Bouadi, and A\. Termier\(2022\)VCNet: a self\-explaining model for realistic counterfactual generation\.InJoint European Conference on Machine Learning and Knowledge Discovery in Databases,pp\. 437–453\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p5.1),[§2](https://arxiv.org/html/2607.01306#S2.p1.1)\.
- \[6\]X\. Heilmann, C\. Manganini, M\. Cerrato, L\. Kestel, and V\. Belle\(2026\)A neurosymbolic approach to counterfactual fairness\.Neurosymbolic Artificial Intelligence2,pp\. 29498732261443184\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p3.1),[§2](https://arxiv.org/html/2607.01306#S2.p1.1)\.
- \[7\]A\. Karimi, G\. Barthe, B\. Schölkopf, and I\. Valera\(2022\)A survey of algorithmic recourse: contrastive explanations and consequential recommendations\.ACM Computing Surveys55\(5\),pp\. 1–29\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p1.1)\.
- \[8\]D\. Mahajan, C\. Tan, and A\. Sharma\(2019\)Preserving causal constraints in counterfactual explanations for machine learning classifiers\.arXiv preprint arXiv:1912\.03277\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p2.1)\.
- \[9\]T\. Miller\(2019\)Explanation in artificial intelligence: insights from the social sciences\.Artificial intelligence267,pp\. 1–38\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p1.1)\.
- \[10\]R\. K\. Mothilal, A\. Sharma, and C\. Tan\(2020\)Explaining machine learning classifiers through diverse counterfactual explanations\.InProceedings of the 2020 conference on fairness, accountability, and transparency,pp\. 607–617\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p5.1),[§2](https://arxiv.org/html/2607.01306#S2.p1.1)\.
- \[11\]M\. Pawelczyk, K\. Broelemann, and G\. Kasneci\(2020\)Learning model\-agnostic counterfactual explanations for tabular data\.InProceedings of the web conference 2020,pp\. 3126–3132\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p5.1),[§2](https://arxiv.org/html/2607.01306#S2.p1.1)\.
- \[12\]C\. Rudin, C\. Chen, Z\. Chen, H\. Huang, L\. Semenova, and C\. Zhong\(2022\)Interpretable machine learning: fundamental principles and 10 grand challenges\.Statistics Surveys16,pp\. 1–85\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p1.1)\.
- \[13\]I\. Stepin, J\. M\. Alonso, A\. Catala, and M\. Pereira\-Fariña\(2021\)A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence\.Ieee Access9,pp\. 11974–12001\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p1.1)\.
- \[14\]S\. Wachter, B\. Mittelstadt, and C\. Russell\(2017\)Counterfactual explanations without opening the black box: automated decisions and the gdpr\.Harv\. JL & Tech\.31,pp\. 841\.Cited by:[§1](https://arxiv.org/html/2607.01306#S1.p5.1),[§2](https://arxiv.org/html/2607.01306#S2.p1.1)\.

## Appendix AASP Knowledge Base for Counterfactual Generation

The complete Answer Set Programming \(ASP\) knowledge base used in the PACE framework is reported in Listing[1](https://arxiv.org/html/2607.01306#LST1)\. The program encodes immutable and editable features, admissible education and occupation transitions, feasibility constraints, candidate generation rules, and the minimality objective used during neuro\-symbolic counterfactual search\.

Listing 1:Complete ASP program used by the PACE framework%Neuro\-symboliccounterfactualsearchfortheAdultIncomedataset\.

%

%ThisASPfilecontainsthesymbolicknowledgebase:

%\-whichfeaturesareeditableorfixed

%\-whichchangesarelegal

%\-whichvaluesarerealistic

%\-howtominimizethenumberofchangedfeatures

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

%Editableandfixedfeatures

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

editable\(hours\)\.

editable\(education\)\.

editable\(occupation\)\.

fixed\(age\)\.

fixed\(sex\)\.

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

%Legalvaluedomains

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

%Weeklyhourscanonlymoveinsmallsteps\.

delta\_hours\(\-10;\-5;0;5;10\)\.

%Occupationchangesarealsolocaltransitions\.

can\_change\_occupation\("Adm\-clerical","Exec\-managerial"\)\.

can\_change\_occupation\("Exec\-managerial","Adm\-clerical"\)\.

can\_change\_occupation\("Adm\-clerical","Sales"\)\.

can\_change\_occupation\("Sales","Adm\-clerical"\)\.

can\_change\_occupation\("Sales","Tech\-support"\)\.

can\_change\_occupation\("Tech\-support","Sales"\)\.

can\_change\_occupation\("Tech\-support","Prof\-specialty"\)\.

can\_change\_occupation\("Prof\-specialty","Tech\-support"\)\.

can\_change\_occupation\("Prof\-specialty","Exec\-managerial"\)\.

can\_change\_occupation\("Exec\-managerial","Prof\-specialty"\)\.

can\_change\_occupation\("Craft\-repair","Machine\-op\-inspct"\)\.

can\_change\_occupation\("Machine\-op\-inspct","Craft\-repair"\)\.

can\_change\_occupation\("Craft\-repair","Transport\-moving"\)\.

can\_change\_occupation\("Transport\-moving","Craft\-repair"\)\.

can\_change\_occupation\("Craft\-repair","Farming\-fishing"\)\.

can\_change\_occupation\("Farming\-fishing","Craft\-repair"\)\.

can\_change\_occupation\("Handlers\-cleaners","Other\-service"\)\.

can\_change\_occupation\("Other\-service","Handlers\-cleaners"\)\.

can\_change\_occupation\("Other\-service","Priv\-house\-serv"\)\.

can\_change\_occupation\("Priv\-house\-serv","Other\-service"\)\.

can\_change\_occupation\("Protective\-serv","Armed\-Forces"\)\.

can\_change\_occupation\("Armed\-Forces","Protective\-serv"\)\.

%Educationchangesarelocaltransitionsonly\.

%ThispreventsunrealisticjumpssuchasBachelors\-\>Doctorate\.

can\_change\_education\("Preschool","1st\-4th"\)\.

can\_change\_education\("1st\-4th","Preschool"\)\.

can\_change\_education\("1st\-4th","5th\-6th"\)\.

can\_change\_education\("5th\-6th","1st\-4th"\)\.

can\_change\_education\("5th\-6th","7th\-8th"\)\.

can\_change\_education\("7th\-8th","5th\-6th"\)\.

can\_change\_education\("7th\-8th","9th"\)\.

can\_change\_education\("9th","7th\-8th"\)\.

can\_change\_education\("9th","10th"\)\.

can\_change\_education\("10th","9th"\)\.

can\_change\_education\("10th","11th"\)\.

can\_change\_education\("11th","10th"\)\.

can\_change\_education\("11th","12th"\)\.

can\_change\_education\("12th","11th"\)\.

can\_change\_education\("12th","HS\-grad"\)\.

can\_change\_education\("HS\-grad","12th"\)\.

can\_change\_education\("HS\-grad","Some\-college"\)\.

can\_change\_education\("Some\-college","HS\-grad"\)\.

can\_change\_education\("Some\-college","Assoc\-voc"\)\.

can\_change\_education\("Assoc\-voc","Some\-college"\)\.

can\_change\_education\("Assoc\-voc","Assoc\-acdm"\)\.

can\_change\_education\("Assoc\-acdm","Assoc\-voc"\)\.

can\_change\_education\("Assoc\-acdm","Bachelors"\)\.

can\_change\_education\("Bachelors","Assoc\-acdm"\)\.

can\_change\_education\("Bachelors","Masters"\)\.

can\_change\_education\("Masters","Bachelors"\)\.

can\_change\_education\("Masters","Prof\-school"\)\.

can\_change\_education\("Prof\-school","Masters"\)\.

can\_change\_education\("Prof\-school","Doctorate"\)\.

can\_change\_education\("Doctorate","Prof\-school"\)\.

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

%Candidategeneration

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

1\{choose\_hours\(Delta\):delta\_hours\(Delta\)\}1\.

%Hoursmoveinsmallstepsandareclampedtothevalidrange\[1,80\]\.

raw\_hours\(Raw\):\-old\_value\(hours,Hours\),choose\_hours\(Delta\),Raw=Hours\+Delta\.

new\_value\(hours,1\):\-raw\_hours\(Raw\),Raw<1\.

new\_value\(hours,80\):\-raw\_hours\(Raw\),Raw\>80\.

new\_value\(hours,Raw\):\-raw\_hours\(Raw\),Raw\>=1,Raw<=80\.

new\_value\(education,Education\):\-

old\_value\(education,Education\),

notchanged\_education\.

0\{changed\_education\}1\.

1\{new\_value\(education,NewEducation\):

can\_change\_education\(Education,NewEducation\)\}1:\-

old\_value\(education,Education\),

editable\(education\),

changed\_education\.

new\_value\(occupation,Occupation\):\-

old\_value\(occupation,Occupation\),

notchanged\_occupation\.

0\{changed\_occupation\}1\.

1\{new\_value\(occupation,NewOccupation\):

can\_change\_occupation\(Occupation,NewOccupation\)\}1:\-

old\_value\(occupation,Occupation\),

editable\(occupation\),

changed\_occupation\.

new\_value\(Feature,Value\):\-

old\_value\(Feature,Value\),

fixed\(Feature\)\.

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

%Validityconstraints

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

%Fixedfeaturescannotchange\.

:\-fixed\(Feature\),

old\_value\(Feature,Old\),

new\_value\(Feature,New\),

Old\!=New\.

%Hoursarekeptinrangebytheclampingrulesabove\.

%EarliervariantusedfortheTable1comparisondiscardedout\-of\-range

%hoursinsteadofclamping;thetwoagreeexceptatthehoursboundaries:

%:\-new\_value\(hours,Hours\),Hours<1\.

%:\-new\_value\(hours,Hours\),Hours\>80\.

%Changedoccupationsmustfollowtheallowedtransitiongraph\.

:\-old\_value\(occupation,Old\),

new\_value\(occupation,New\),

Old\!=New,

notcan\_change\_occupation\(Old,New\)\.

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

%Changecountingandminimality

%\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

changed\(hours\):\-

old\_value\(hours,Old\),

new\_value\(hours,New\),

Old\!=New\.

changed\(education\):\-

old\_value\(education,Old\),

new\_value\(education,New\),

Old\!=New\.

changed\(occupation\):\-

old\_value\(occupation,Old\),

new\_value\(occupation,New\),

Old\!=New\.

%ASPensuresthatgeneratedcandidatesrespectthebudget\.

:\-change\_budget\(Budget\),

Budget\!=\#count\{Feature:changed\(Feature\)\}\.

\#minimize\{1,Feature:changed\(Feature\)\}\.

\#shownew\_value/2\.

\#showchanged/1\.

## Appendix BOnline Resources

The source code is available via

- •