New AI Algorithm Delivers Realistic, Optimal Explanations for Black-Box Decisions

When a bank’s algorithm denies someone a loan, the most useful answer is not an abstract account of the model’s internal mathematics. It is a concrete, actionable statement: change these specific things about your application and the outcome would flip. That is the promise of counterfactual explanations, one of the most actively pursued ideas in explainable artificial intelligence. Yet a persistent problem has haunted the field: the suggested alternatives that algorithms produce are often unrealistic, describing applicants who could never exist in the real world. A new study published in the journal Machine Learning introduces an algorithm called P2CE that promises to close this gap, generating explanations that are simultaneously plausible, optimal across multiple criteria, and computable for any model, no matter how complex.

The research, conducted by Arthur Hendricks Mendes de Oliveira, Giovani Valdrighi, and Marcos Medeiros Raimundo of the Institute of Computing at the State University of Campinas in Brazil, addresses a tension at the heart of counterfactual explanation methods. An explanation must be feasible, meaning the suggested changes are achievable by the individual concerned, and plausible, meaning the resulting profile would be a probable observation within the data distribution. Suggesting that a loan applicant increase their income tenfold might technically satisfy a model, but it is neither achievable nor believable. Similarly, an explanation that requires twenty simultaneous small changes across dozens of features may be less useful than one moderate change to a handful of attributes.

The team’s earlier work, an algorithm known as MAPOCAM, used a branch-and-bound search strategy to find Pareto-optimal counterfactual explanations, meaning solutions for which no other candidate is better across all cost measures at once. This matters because different people weigh feasibility differently: one person may prefer the smallest total change, another the fewest features touched, another the smallest single modification. Rather than collapsing these preferences into a single weighted score, multi-objective optimization returns a diverse set of trade-offs. But MAPOCAM had two significant weaknesses. Its solutions could fall outside the data distribution, producing profiles that are statistically improbable, and its efficiency relied on an assumption that the model’s predictions increase or decrease monotonically with each input feature, an assumption violated by popular models such as neural networks and support vector machines.

P2CE, which stands for Plausible Pareto-optimal Counterfactual Explanations, tackles both weaknesses with two key ingredients. The first is an auxiliary outlier detector based on the isolation forest algorithm. Isolation forests work by building an ensemble of decision trees optimized to isolate individual samples quickly; points that lie far outside the data distribution get isolated in fewer splits, yielding shorter paths and higher outlier scores. Whenever P2CE’s search finds a candidate counterfactual, it checks whether that candidate would be classified as an outlier. If so, the solution is discarded, even if it looks attractive on the distance metrics. Crucially, the algorithm prunes outlier solutions during the search itself rather than generating a full set of optimal solutions and filtering afterward, which would yield a fundamentally different and less useful result set.

The second ingredient is more technically inventive. To prune the enormous search space of possible counterfactuals efficiently, the algorithm needs an upper bound on the best prediction any completion of a partial solution could achieve. MAPOCAM computed this bound using monotonicity, which fails for non-linear models. P2CE instead exploits a mathematical property of SHAP values, the widely used feature attribution method: SHAP attributions are additive, so a model’s prediction equals the average prediction plus the sum of each feature’s contribution. By precomputing the maximum attribution each feature can attain across a large dataset, the algorithm can bound how high the prediction could climb if the remaining free features were set to their most favorable values. If even this optimistic bound stays below the decision threshold, the entire branch of the search can be abandoned without ever querying the model.

The authors also show that this bound can be tightened. Because counterfactual searches typically limit how many features may change, only the few open features with the largest maximum attributions need to be considered, producing a sharper bound and more aggressive pruning. The residual error in the bound, which reflects how much the attributions of fixed features might shift, stays small when the changed features are few, a property the authors connect to recent theoretical work on the probabilistic Lipschitzness of explanation methods: nearby inputs tend to receive nearby explanations, particularly for well-regularized tree ensembles and neural networks.

The empirical evaluation spanned five benchmark datasets, including German Credit, Taiwan credit card default, Home Credit, Adult income, and the newer ACS Income dataset from the US Census, with classifiers including logistic regression, LightGBM gradient boosting, and a multi-layer perceptron. Compared against MAPOCAM and two popular alternatives, DiCE and NICE, P2CE consistently produced the lowest-cost solutions with competitive computing times and the smallest fraction of outlier explanations, generally below five percent. In one ablation experiment on the Adult dataset, MAPOCAM produced 22 percent outlier solutions while full P2CE produced only 3 percent. The speed gains were dramatic for neural networks: on the Taiwan dataset with a multi-layer perceptron, MAPOCAM needed roughly 100 seconds to generate multi-objective explanations while P2CE finished in under one second.

A qualitative example illustrates why these differences matter to real people. For one individual in the Adult dataset rejected by the neural network classifier, the DiCE algorithm suggested raising capital gains from zero to as much as 54,000 dollars, a change few applicants could make. P2CE instead offered three alternatives with far smaller capital gains, one combining a modest gain with a change in marital status, and two trading off an increase of roughly 13 to 17 weekly working hours against capital gains of 9,000 to 10,000 dollars. That last pair gives the individual a genuine choice between two attainable paths, exactly the kind of decision-support the technique is meant to provide.

The authors are candid about limitations. The method depends on SHAP approximations, which carry their own computational cost and approximation error, and the search operates on a discretized grid of feature values, so the granularity of that grid limits how precisely solutions can be tuned. They suggest adaptive grids that automatically refine resolution for influential features as a future direction. The implementation has been released as open source, and the researchers argue that the combination of distribution awareness, multi-objective guarantees, and model-agnostic design makes P2CE well suited for deployment in high-stakes domains such as credit scoring, hiring, and healthcare, where regulators, including the EU’s General Data Protection Regulation, increasingly demand that automated decisions come with explanations people can actually act upon.

Subject of Research: A model-agnostic algorithm for generating plausible Pareto-optimal counterfactual explanations in machine learning.

Article Title: P(^{2})CE: Model-Agnostic Plausible Pareto-Optimal Counterfactual Explanations

Article References: de Oliveira, A. H. M., Valdrighi, G., & Raimundo, M. M. (2026). P$$^{2}$$CE: Model-Agnostic Plausible Pareto-Optimal Counterfactual Explanations. Machine Learning, 115(9), Article 213. https://doi.org/10.1007/s10994-026-07143-6

Image Credits: AI Generated

DOI: 10.1007/s10994-026-07143-6

Keywords: counterfactual explanations, explainable AI, machine learning, multi-objective optimization, SHAP values, outlier detection, isolation forest, algorithmic recourse, Pareto optimality, branch-and-bound, model-agnostic explanations, fairness and transparency