ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets
Authors: Bohdan Turbal
Iryna Voitsitska
Lesia Semenova
Venue: NeurIPS 2025 spotlight ()
Keywords: Algorithmic recourse
Rashomon set
Model multiplicity
Counterfactual explanations
Robustness
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: ElliCE generates counterfactual explanations with theoretical guarantees that remain valid across Rashomon set by approximating it with an ellipsoid. The method is faster than existing robust baselines and ensures meaningful explanations.

Abstract: Machine learning models now influence decisions that directly affect people’s lives, making it important to understand not only their predictions, but also how individuals could act to obtain better results. Algorithmic recourse provides actionable input modifications to achieve more favorable outcomes, typically relying on counterfactual explanations to suggest such changes.
However, when the Rashomon set - the set of near-optimal models - is large, standard counterfactual explanations can become unreliable, as a recourse action valid for one model may fail under another.
We introduce ElliCE, a novel framework for robust algorithmic recourse that optimizes counterfactuals over an ellipsoidal approximation of the Rashomon set.
The resulting explanations are provably valid over this ellipsoid, with theoretical guarantees
on uniqueness, stability, and alignment with key feature directions.
Empirically, ElliCE generates counterfactuals that are not only more robust but also more flexible, adapting to user-specified features constraints  while being substantially faster than existing baselines.
This provides a principled and practical solution for reliable recourse under model uncertainty, ensuring stable recommendations for users even as models evolve.

ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets
Bohdan Turbal'
Iryna Voitsitska"
Lesia Semenova"
Princeton University 2 Ukrainian Catholic University Rutgers University
bt48118princeton. edu, voitsitska, wtw.tsaaaaauuuuuuuuueuuuuu edu. ua, lesia. Semenova@rutgers.eee edu
Abstract
Machine learning models now influence decisions that directly affect people's lives, making important to understand not only their predictions, but also how individuals could act to obtain better results. Algorithmic recourse provides ac- tionable input modifications to achieve more favorable outcomes, typically rely- ing on counterfactual explanations to suggest such changes. However, when the Rashomon the set of near-optimal models is large, standard counterfactual explanations can become unreliable, as a recourse action valid for one model may fail under another. We introduce ElliCE, novel framework for robust algorith- mic recourse that optimizes counterfactuals over an ellipsoidal approximation the Rashomon set. The resulting explanations are provably valid this ellip- soid, with theoretical guarantees on uniqueness, stability, and alignment with key feature directions. Empirically, ElliCE generates counterfactuals that not only more robust but also more flexible, adapting to user-specified feature constraints while being substantially faster than existing baselines. This provides princi- pled and practical solution for reliable recourse under model uncertainty, ensuring stable recommendations for users even as models evolve.
Introduction
When algorithmic decision denies someone loan, a job, or insurance coverage, a natural ques- tion follows: What could change to obtain a better outcome next time? Algorithmic recourse an- swers this question by providing concrete, actionable changes that could lead to a more favorable de- cision. A common way to generate such recommendations through counterfactual explanations- small modifications to individual's features that flip the model's prediction. Yet, even when the recommendation looks specific (c.g. "increase your income by $5000"), one must ask: "Would that same change still work tomorrow the institution retrains replaces its model?" or "How stable are these suggestions across equally good models that explain the data in different ways?"
Most existing counterfactual generation methods that the underlying model fixed and perfectly known. practice, models evolve: banks regu- larly retrain risk predictors, healthcare institutions update diagnostic classifiers, and regulators may require model re-validation under new privacy or transparency constraints. Small shifts in data or models. This phenomenon, known as the Rashomon Effect 9 23 54 56) implies that many distinct predictors achieve nearly optimal performance. In such settings, a counterfactual valid for one model can fail under another, undermining the reliability and consistency of algorithmic recourse.
55
59
63
implicitly assume
regularization can result in very iifferent-yet--qually-aacu
'The majority of this work was conducted while Bohdan was Taras Shevehenko National University of Kyiv and Lesia at Microsoft Research NYC.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Recent approaches have attempted to produce robust counterfactuals, meaning counterfactuals that are valid under small parameter perturbations or across predefined ensembles [9
26
33
38 61 However, these methods either rely on heavy-weight mixed-integer solvers, restrict robustness to local neighborhoods around a single model, or lack formal guarantees of validity across the full space of near-optimal solutions known as the Rashomon set. None of them directly leverages the geometry of this Rashomon set itself.
R4
We introduce ElliCE, an efficient and provably robust framework for algorithmic recourse that works over an ellipsoidal approximation of the Rashomon set. By modeling the space of near-optimal mod- els as an ellipsoid derived from the curvature (Hessian) of the loss landscape, ElliCE reformulates robust counterfactual generation as a tractable convex optimization problem. The resulting counter- factuals are valid for every model inside the ellipsoid, ensuring that a user's recommended action remains meaningful even if the deployed model is replaced by another equally accurate one from the approximated Rashomon set.
Our contributions are fourfold: (1) Theoretical foundation. We derive a closed-form expression for the worst-case prediction, which allows us to formulate the robust recourse problem as a con- vex optimization and establish formal guarantees of validity, uniqueness, and stability for ElliCE's counterfactuals. (2) Geometric intuition. We show that ElliCE's robustness term connects the coun- terfactual's 's stability with the importance of the features it modifies as the optimization naturally aligns recourse directions with the principal curvature axes of the loss landscape. (3) Actionability. ElliCE supports feature-level constraints, such as sparsity constraints, immutable or range-restricted attributes, allowing users to generate realistic, actionable recourse tailored to specific application or user settings. (4) Empirical validation. Across multiple high-stakes tabular datasets, ElliCE achieves higher robustness and remains one to three orders of magnitude faster than competing baselines, while maintaining proximity and plausibility.
Ultimately, ElliCE looks at algorithmic recourse through the lens of model multiplicity. Instead of relying on a single model's decision boundary, it offers explanations that stay consistent across many models that fit the data almost equally well. This perspective treats the Rashomon Effect not as a flaw to eliminate, but as an inherent source of uncertainty to account for, leading to stable recourse in the presence of model diversity.
Related works
The Rashomon Effect, term popularized by Breiman g in the context of ma- chine learning, describes the phenomenon where multiple distinct models can achieve near-optimal empirical risk (these models form a Rashomon set). This effect also referred to as model mul- The existence of the Rashomon set has implications for the trustworthiness and
Rashomon Effect.
tiplicity
1 45
reliability of machine learning systems, influencing feature importance 16 21 49), fairness
[4
22
47
the existence of simple yet accurate models 7
56 57
to name few. Significant
research has focused on measuring and characterizing the Rashomon set for different model classes 160. Our work leverages insights into the geometry of the Rashomon set, explored by works like Donnelly et al. [18), Zhong et al. (66), but applies them to the distinct challenge of generating robust algorithmic recourse across this set.
28
20
30
(4
Counterfactual Explanations (CEs). Counterfactual Explanations have emerged as promi- nent tool for providing algorithmic recourse. Numerous approaches exist for generating CEs. Proximity-based methods aim for counterfactuals requiring minimal feature space perturbations
[C
48
62 63 Sparsity techniques prioritize modifying the fewest features possible to enhance ac-
59 while some methods attempt to balance both objectives 43] Another research direction emphasizes plausibility, ensuring generated CEs represent realistic instances by constrain- ing them to the data manifold, for example, using guidance from generative models [ 50 [TT)
tionability 46.
encoding feasibility rules [37] or tracing density- paths [52] Recent extensions also incor-
porate temporal reasoning 122 and fairness objectives 5 40 65 A key limitation across these
approaches (which ElliCE directly addresses) is the assumption of fixed, perfectly known predic- tive model, as counterfactuals constructed near a specific decision boundary can become unstable under model updates perturbations.
Robustness to Local Model Perturbations. Building upon the limitation of fixed models, one line of work has focused specifically on achieving robustness against small, local changes or per-

---

turbations in the model's parameters. For instance, ROAR 6 optimizes CEs considering local A A-perturbations the model. Jiang et al. [3I] introduced A-robustness, formal metric assess CE validity under bounded parameter perturbations in neural networks, with subsequent works de- veloping provably robust MIL.--bsse methods 32 While these methods offer formal guarantees for A-robustness, MIL.-based approaches can face scalability challenges, and the focus is generally on local parameter stability rather than the broader implications of the Rashomon Effect.
Robustness under the Rashomon Effect. A growing body of work addresses counterfactual ro- bustmess under model multiplicity, aligning closely with the Rashomon Effect. Several approaches evaluate stability across predefined sets or ensembles of models, introducing heuristic stability mea-
sures (e.g., T:Rex [26 and RobX (19)), probabilistic frameworks (22 [8), or guarantees under specific norms and conditions like distribution shift [24 39, AT]. Foundational work by Pawelczyk et al. [51] conceptually linked the Rashomon Effect to counterfactuals, though primarily enhancing input perturbation robustness. More recent methods use argumentative ensembling 34 or aggregate explanations across AutoMI--generated sets 11 to handle model multiplicity.
Our work takes a distinct approach. Rather than relying on ensemble agreement, heuristic stability metrics, local perturbations, or argumentative aggregation, ElliCE leverages the local geometry of the Rashomon set, approximated by an ellipsoid, to derive theoretically grounded, robust recourse valid across all models within the approximation.
3 Background and Notation
Dataset and hypothesis space. Consider n i.i.d. samples Sn = fz; = (x, Wi) where x, e X C Rd and y E y = {0. 1} are generated from an unknown distribution D on X x y. Let Vered be an output space, where ) predd R for scores (logits) pred S [0, for probabilities. Then F = {fo : E }} is a hypothesis space of functions fo : X + Ypreed parameterized by a vector E θ IRP For example, F represent linear models or multilayer perceptrons. We denote specific function by fo. As our analysis focuses on the parameter space O, we will often refer to the model directly by its parameter vector 9.
Loss and objective function. Let Φ) Vpreed x + R., be a loss function. this work, we consider binary cross-entropy (logistic) loss (()o(x), = (Iy log(o(fo(x))) (1-y) log(1 afo (x)))] which is applied to the model's raw score (logit), 8 - fo(x), where a(s) = T-exp(-s] is the sigmoid function. However, our results generalize to other convex losses. The true risk is the expected loss (0) EE [x]((((( v)] that we approximate with the empirical risk, which is the average loss, ((O) n E (Xo((x)) v:). We also define an fz-regularized objective function: L(0) = (()) + 0|l where A 2 0 is the regularization strength. The empirical risk minimizer (ERM) i e arg mingee i(0).. When
0, the ERM i E arg mingee j()).
Rashomon set. Following 211 56 64], we define the e-Rashomon set within the parameter space O as the set of parameter vectors whose corresponding models fo have objective value close the minimum:
R(e) = ( e (0) < L(()) +c},
where e 2 is the Rashomon parameter defining the allowable tolerance in objective compared to the ERM, Í.()) It is typically a small value. The existence of the Rashomon set with multiple, distinct parameter vectors O (corresponding to potentially distinct functions fo) achieving similar performance implies that different underlying logic (how features contribute to predictions) can explain the data equally well. is important to be aware of this variability among near-optimal models when generating explanations for individual predictions, as different models in R(e) might suggest different ways an outcome could be changed.
Counterfactual explanations. Let g Ypred + {0.1) be the decision function that converts a model's score output = fx(x) to final binary class label by applying threshold such that g(s) = 1[s 2 t). For an ERM Ô and for an input vector Xo with prediction g g(fxxxo) a counterfactual explanation x is data point such that its predicted class is the opposite, i.e., (xx)) 1 50- The set of all counterfactual explanations for xo under the model Ô and decision function y is defined as:
fo-
C(xo, 0) (xx E X x(f = -9(f((x)))
3

---

For instance. in a credit loan application scenario, if an applicant X, is denied loan (e.g., g(fg(x))) 0). a counterfactual explanation x, would be a modified version of their ap- plication details (e.g., increased income, reduced debt) such that the model predicts approval, (x)) = 1. While many such x might exist, practical algorithmic recourse aims find expla- nations that require minimal change for the user. This means finding the "closest" counterfactual: x = arg min x. (xt,, 6) v( Xo). where v(.,-) : Rd x IR + IR is a defined distance function or cost metric that we discuss next.
Distance Metrics. In our framework, we primarily focus on the two distance metrics for generating actionable and interpretable counterfactuals: l or Fuclidean distance and mixed distance fmir- Note that Eg is a natural geometric measure of proximity, that penalizes large differences in any feature, v(x,, Xo) (x xx) = ||x, xol12 - Fog)². For practical applications where features have different natures (continuous and categorical),
can also consider the mixed distance v(.,)) = min: inspired by Gower's distance. Assuming that the data are standardized, is defined as: (X,,
V EjEInons (Ies xo,)² + EjeI... ūÿ 1 [Fes * moy], where Toont and Teat denote the sets of continuous and categorical feature indices respectively, 1[:] is the indicator function, and ùi are optional weights reflecting the cost of changing feature j. We use & distance for our theoretical analysis in the subsequent sections.
Next, we describe our approximating framework and outline the optimization process.
Framework for Robust Recourse over the Rashomon Set
We focus theoretical analysis on linear predictors of the form fo(x) = x. However, the same methodology applies in the final embedding space of multilayer perceptrons (MLPs) by writing the embedding and are the last-
model as fx) = e h(x), where h(x) is the penultimate- layer parameters. We freeze h(.) and apply the same ellipsoidal procedure 0 as in the linear case (equivalently, replace x by h(x) in the formulas below).
Approximated Rashomon set. For certain objectives, such as fg-regularized mean-squared error on linear models, the Rashomon set is exactly an ellipsoid in the parameter space [56]: R(()) = {0: (0 T (X + (0,) - 0) < e). where X E Raxd is the data matrix, whose i-th row is the feature vector x,_ T is an identity matrix of size p x p, and À E R4 is the regularization parameter. Because mean-squared error provides local quadratic approximation losses, the exact ellipsoidal form of its Rashomon set serves as strong motivation for the Rashomon set approximation. Building on this and on similar geometric intuition [66], we approximate the e- e-Rashomon set with an ellipsoid defined by the local geometry of the loss landscape:
other convex
R(E) = (0 1 -0) HO 0) Sc),
where H = X + Mp is the Hessian of the reguulalrd loss function, evaluated at ô. For diagonal matrix of weights where ww (xf((x))(( o (Ja(x:)))
logistic loss, W is an Recall from Section that (.) is the sigmoid function.
The Hessian matrix H of the regularized objective L(0) is strictly positive definite. This is because is the sum of the positive semidefinite (PSD) Hessian from the convex logistic loss and the positive definite (PD) Hessian from the & regularization term (Alp), assuming À >> 0. A positive definite Hessian important for our framework, as it guarantees the approximating ellipsoid is well-defined and bounded, and ensures that H is invertible for our closed-form solution.
In cases where the unregularized risk (() is minimized (c.g., for neural networks), the resulting Hessian is only guaranteed to be PSD and may be singular. For these models, we ensure positive definiteness in practice by adding small stabilization term, adg, > 0, to the computed Hessian, which is a standard technique to guarantee invertibility.
Optimization. To find robust counterfactual explanation, we want to compute an explanation x, that closest to the original point X9 while ensuring that its predicted outcome is above a target threshold / for all models within the approximated Rashomon set. In other words, for given Xo- we look for minimally modified (measured some distance; we will use & here) x., such that its predicted outcome achieves t even when evaluated by the least favorable model 0 within the

---

approximated Rashomon set R(c). Formally, this requirement leads to the following optimization problem:
min xx--xol13
0 x t. (ER(+)
min
The inner minimization problem admits a closed-form solution, as we show next in Theorem || By reformulating the problem in this way, we get tractable optimization framework that supports more efficient computation and analytical analysis of solution properties.
Theorem (Closed-form solution). For positive-defmite Hessian H, the inner minimization problem over the allpssidd-aprroximmee Rashomon set RR(e) has the closed-form solution DER() 0 Xc. = - Xe - /2 x H-1xc. Moreover, for a given No. the worst-case model Qwerst (Xe) that achieves this minimum is: Oworst (Xc) = 0 /2e 1x'x.
H-xx
As direct consequence of Theorem [ we obtain a practical criterion for verifying the robustness of potential counterfactual. Specifically, since the theorem provides an explicit characterization of the output generated by the least favorable model 0 E R(e) for given X., we can immediately determine this x, achieves the target across the entire set as we show in the following corollary.
We prove Theorem [ Appendix A.1
Corollary 1. A given counterfactual explanation x. is robust with respect to all models in the ellixsoid-apprxximated Rashomon set R(+)) against a target score L if and only if: 0 X 22 N.Cxx--Ix.. x- 2t.
By substituting the closed-form solution from Theorem ! into the original optimization problem ( the robust counterfactual optimization problem becomes:
min X
xx 1
s.t. 0xx,
2ex H
H 2 t.
The resulting problem quadratically constrained quadratic program (QCQP), which class of tractable convex optimization problems. We solve it efficiently using gradient-basee method. Leveraging the formulation 4 we implement two approaches for generating counterfactuals: search-based method for generating data-supported counterfactuals lying on the data manifold, and a continuous optimization method for exploring potentially novel non-data supported solutions.
Continuous CE generation. For non-data supported counterfactuals, we solve the convex optimiza- tion problem in Equation 2 using gradient- based approach for both linear models and multilayer perceptrons. This method directly optimizes for counterfactual x. in the input space. For neural networks, the process is guided by the worst-case model @worst (xe) identified in the final layer's embedding space using Theorem [ with the resulting gradients mapped back to the input features. The full details of this procedure are available Appendix [..4
Data-supported CE generation. For practical applications where counterfactuals should remain on the data manifold, we generate data-supported explanations based the training set. Specifically,
we evaluate the robust logit θ x,x - 2ex H H for each training data point x; using Theorem | Then, we compute the subset Sttable by filtering out points where this robust prediction exceeds the target threshold t. Finally, we use k-d tree nearest neighbor search within Satable to identify the points closest to the input point in terms of defined distance (for example, f2), which gives us counterfactual that is both robust and lies on the data manifold.
The continuous approach offers flexibility by exploring the entire feature space for new solutions, while the data-supported approach guarantees plausibility by restricting solutions observed amples. We evaluate the performance of both approaches in Section o and focus on theoretical guarantees our framework next.
Theoretical Guarantees of ElliCE Counterfactuals
In this section, we explore key theoretical properties of the counterfactual explanations generated under our framework. Note that we use & distance as target distance between Xg and x,- We show that the counterfactual explanations generated by our method are valid, unique, stable, and align
5

---

with important directions in the feature space. We focus on each of these properties separately and proofs of theorems provided in this section are in Appendix A.2
Validity. By explicitly optimizing for the worst-case model I worsst within the defined ellipsoid, any counterfactual x generated by ElliCE is, by construction, valid for all models in the approximated Rashomon set. This inherent validity ensures that the provided recourse is faithful, regardless of which model from the approximated Rashomon set was selected.
Uniqueness. By Theorem 2 that we state next, any solution x, to the optimization problem P is unique. Because objective is strictly convex and the approximated Rashomon set is character- ized as an ellipsoid, for a given Xu, there can never be two distinct counterfactuals at the same & distance from the original Xo. In practical terms, this uniqueness guarantees that ElliCE provides single solution for a given input and desired robustness level. This directly addresses and resolves "explanation multiplicity" (25), where multiple, distinct explanation paths might exist for a single input (at least for lg distance).
Theorem (Uniqueness). If solution x. to the optimization problem exists, then x. is unique.
Stability. The input data X6 is often subject to noise or minor variations. A desirable property is that such small changes in the input do not lead drastically different counterfactuals. Our framework ensures this stability. Theorem 3 formally states that the process of generating robust counterfactuals Lipschitz continuous with a constant of This means that if the original input xo is perturbed by a small amount ò to become Xy, the resulting robust counterfactual x will not deviate from the original counterfactual x. by more than the magnitude of the initial perturbation ||0||2- This property guarantees the reliability of the explanations.
Theorem (Stability). Given an input Xa, let x be the robust counterfactual solution for Xo. If the input is perturbed to x/ Xo + d, where d E RR, and Xg is the robust counterfactual solution for Xy, then [xx- - -xx12 122 1 ||8|2-
Alignment with Important Feature Directions. An insightful explanation should not only pro- vide a path to a different outcome but also highlight which features are most critical in achieving that change, particularly under model uncertainty. The robustness penalty term, Cros(c, x.)
V2ex. H 'x,, plays key role in this alignment. Theorem 4 formalizes the intuition that to mini- mize this penalty (and thus find an efficient robust counterfactual), the recourse direction x, should align with directions in the feature space that are most sensitive or influential, eigenvectors of the Hessian matrix H. Specifically, under reasonable conditions, the penalty is min- imized when the counterfactual aligns with the leading eigenvector of H, which often corresponds to the direction of greatest sensitivity. This encourages the counterfactual to suggest changes along features that have significant impact, making the explanation more informative.
captured by the
Theorem 4 (Alignment with Important Feature Directions). Define the robustness penalty as Crosle, 22xx H-lxe for symmetric positive definite Hessian H. Let X be the largest eigenvalue of H with corresponding eigenvector Qi, and assume that X is unique. Then, for a fixed non-zero norm [|xel]2, the robustness penalty term Crob(e, xc) is minimized when the counterfactual vector Xx is aligned (i.e., collinear) with the eigenvector qı-
Price of robustness. Previous literature has observed the trade-off between robustness and prox- imity (22). Indeed, intuitively, increasing robustness and ensuring validity across larger set of potential models may require more changes to the input features, effectively increasing the proxim- ity. This implies a "cost" for greater robustness that Theorem formalizes.
Theorem 5 "Robustness-Proxinii
Trade-off). For an input Xy such that @ S t, where â is ERM, let (c) be the optimal robust counterfactual for a given robustness level O, and let ((e) (e) - Xollž be its l2 distance from Xo. If v(ei) > 0 and (=(e1) + O, then for any two robustness levels 0 El < 62, u(e1) v(e2).
Xo
The practical impact of this trade-off is significant. Overly robust counterfactuals may become distant and unactionable, while insufficient robustness compromises recourse reliability under model shifts. This underscores the need for methods that efficiently explore this trade-off by achieving substantial robustness with reasonable proximity-a. goal that ElliCE effectively meets (Figure 2
When applying our theoretical results to MIPss, the validity guarantee fully preserved in the input space, which is key result. The formal guarantees for uniqueness (Theorem 2 stability

---

(Theorem B) and the robustness proteesitt trade-off (Theorem 5). however, depend on the convexity of the feasible set (see proof of Theorem 2) While this convexity guaranteed in the embedding space (x),, the nonlinear mapping from the input space (x < h(x)) means it is not guaranteed to hold there. This distinction highlights a fundamental challenge for robust recourse in deep models and underscores that extending these formal guarantees to the input space is promising direction for future work. Nonetheless, these theorems provide a principled geometric foundation for our approach and hold for linear models and embedding spaces. Next, we present empirical results showing that ElliCE's performance is consistent with its theoretical guarantees.
Evaluation Pipeline and Experimental Results
In our evaluation pipeline, we work with the hypothesis space of linear models and multi-layer perceptrons (MLPs). However, our results can be extended to other hypothesis spaces that can be optimized with gradient descent, such as neural additive models [. In this section, we empiri-
cally show that ElliCE is faster and more robust as compared to other methods that produce robust counterfactuals. Please see Appendix B for additional details and results.
Datasets. We consider nine datasets from high-stakes decision domains such lending (Aus- tralian Credit [53] FICO 200), German Credit
27 Banknote [d4),, healthcare (Parkinson's 660
Diabetes [8 and recidivism (COMPAS 22). as well as benchmark datasets (Wine Quality [3],
Extended Iris [3] ) Please see Table S for detailed dataset descriptions and preprocessing notes. We
used datasets with predominantly categorical features (FICO, Australian Credit, COMPAS, German Credit, Diabetes) for data- supported CE generation, and datasets with continuous features (Diabetes, Parkinson's, s, Banknote, Iris, and Wine Quality) for continuous methods. We balanced the datasets, standardized continuous features, and, for some datasets, dropped rows with missing values.
Baselines. We compare EliCE other methods that are designed generate robust counterfactual explanations, such as T:Rex, Interval Abstractions (we refer to it as Delta-robustness (1)), PRO- PLACE, and ROAR. T:Rex 26 generates robust counterfactuals for neural networks using Stabil- ity measure that depends on variance. It quantifies robustness to naturally occurring model changes, providing probabilistic validity guarantees. It is successor of RobX [1] which targets tree-based ensembles. Interval Abstractions 333) ensures that counterfactuals are robust to bounded changes in model parameters (weights and biases). It uses interval neural networks and mixed-integer linear programming. PROPLACE (32) formulates counterfactual generation as a bi-level robust optimiza- tion problem: it enforces plausibility by restricting solutions to the convex hull of realistic samples and uses interval bounds on neural networks to ensure robustness. ROAR [6] optimizes counter- factual validity under bounded model parameter perturbations using a formulation. Most implementations of our baselines follow Jiang et al. 35
loss
Evaluators. Precisely computing the entire Rashomon set for the hypothesis spaces that we con- sider is intractable. Therefore, to evaluate the robustness and validity of counterfactual explanations generated by ElliCE and the baselines, we rely on established techniques that approximate or char- acterize this set. These approaches generate diverse collections of near-optimal models, each serving as a proxy for the actual Rashomon set. Our evaluators include: Random Retrain, which retrains models multiple times with different random seeds to capture procedural variability. Rashomon Dropout 30, which applies binary dropout masks single trained neural network's 's weights dur- ing inference, creating ensemble of thinned sub-models. Adversarial Weight Perturbation (AWP) (8). which generates diverse models from an initially trained model by applying small perturba- tions to its weights. We define the objective tolerance (Rashomon parameter) for the evaluators as Etarget. which is distinct from e. This separation ensures that the Rashomon set used for evaluation is controlled independently from the robustness tolerance used by ElliCE.
Metrics. We evaluate the generated counterfactual explanations based on four metries: validity, proximity, robustness, and plausibility. Validity measures whether a generated counterfactual x, for a given input Xa successfully achieves the desired outcome e when evaluated on the original model foasetine for which it was generated, Validity = > [[fometine = c]. Proximity mea- sures the closeness of a counterfactual x, to the original instance Xo. We primarily report the & distance: ||x,- Xoll2. Lower values indicate less change required and are thus better. Pluusibil- ity checks whether the generated counterfactuals lie in realistic regions of the feature space. Our data supprrup counterfactuals are inherently plausible, as they lie the data manifold. For con-
7

---

tinuous approach, because ElliCE enforces robustness by pushing counterfactuals away from the decision boundary, the resulting counterfactuals might shift toward higher-density regions of the tar- get class. Nevertheless, we evaluate plausibilityy using the Local Outlier Factor (LOF) [2) stan- dard outlier-detcctoon metric. LOF values close to 1 indicate high plausibility, whereas larger values suggest the counterfactual is in low-density region. Robusiness computes whether the generated counterfactual x, remains valid (i.e., still achieves the desired outcome c) for all models within an evaluator ensemble R(Eurgee). Total is calculated as the average across all counterfactual points:
Robustness Σi=1 Vfo R(Eurge)) (xx.) = =c]-
higher robustness score (closer to 1) is better, indicating that more counterfactual explanations are robust to model changes.
Experimental Setup. For evaluators, we define target multiplicity tolerance globally in range étarget E [0, 0.1J. We provide discussion on how to choose ElliCE's in Appendix B For every dataset, we performed 4-fold stratified cross-validation. Within each fold, the training data are further split into 80% for training and 20% for validation. The procedure within each inner fold is as follows: (1) We train a base model fusseline. which serves as reference model for all counterfactual generation methods. (2) Using fiuseline as a reference (if required by the evaluation method), we generate urgee Eurget-Rashonee Rashomon set. (3) Multiplicity parameters for each baseline (c for ElliCE, for Delta Robustness, ROAR and PROPLACE, or 7 for T:Rex) are tuned via grid search on the validation set with a goal of maximizing validity. We allocate approximately the same amount of time for each method to tune its parameters with a hard maximum of 8 hours per method per data fold (as a result, we could not run PROPLACE for Parkinsons dataset). (4) Final performance metrics are reported on the held-out split of the outer fold. Note that due to our tuning procedure, we expect high validity metric for ElliCE and baselines. Indeed, for supposup methods validity is consistently 100% across datasets, we do not report it.
We conducted experiments on logistic regression and multilayer perceptrons. Consistent with prior work 32 611 we focus on generating counterfactuals that change predicted labels from 0 to 1. Linear models are trained using Scikit-learn's 's LBFGS solver with an & penalty (regularization pa- rameter 0.001). MLPs are trained with the Adam optimizer (learning rate 0.001), early stopping, and le regularization parameter 0.001. For evaluation, we generate one counterfactual per method for each data point in the held-out set. Each counterfactual is then evaluated against the three evaluators (Random Retrain, Rashomon Dropout, AWP). The exact construction algorithms for these evalua- tors are described in Appendix B. Reported metrics are averaged across data points and folds, with plots displaying the mean and standard error.
Data-supported (FICO)
Continuous (Diabetes)
LMs
MLPs
LMs
MLPs
1.0
1.0
0.8
0.8
Dropout
Dropout
0.5
0.5
0.2
0.2
0.0
0.0
0.02
0.04
0.06 0.00 0.10
0.02 0.04 0.06 0.00 0.10
0.02
0.04
0.06
0.08 0.10
0.02 0.04 0.06 0.08 0.10
1.0
1.0
0.8
0.8
AWP R
AWP R
0.5
0.5
0.2
0.2
0.0
0.0
0.02 0.04
0.02 0.04 0.06
0.02 0.05 0.10
0.02 0.04
Target
Target E
Target
Target
T.Rex - Delta Robustness
PROPLACE - ROAR
T:Rexl
EIlICE+R (Ours) ElliCE (Ours)
EIliCE+R (Ours)
EIIICE (Ours)
Figure 1: Robustness evaluation of ElliCE against baselines. The plot displays the robustness metric (y-axis) as a function of the target robustness level Etarget for the evaluators (x-axis). ElliCE consis- tently outperforms all baselines across all robustness levels. See Appendix B for more figures. For ElliC+RR for MLPs, we apply additional regularization to the Hessian, using À = 0.1 instead of 0.001.
8

---

Table 1: Performance of counterfactual methods on MLPs. For evaluators, we set Earget 10% of
the training objective (Etarget = 0.1 x [asselinee ))
R here stands for Robustness, L2 for proximity,
and PROP stands for PROPLACE. See Appendix B
for results on other datasets.
Evaluation Metric
Data
Method
Retrain
Dropout Rashomon
AWP
R1
1.2.]
R1
L22
R1
L2
Data-supported (IS)
ElICCE
1.00 + 0.00
3.53
0.17
1.00
0.00
4.91=0.2.
1.00 - 0.00
5,06 = 0.29
FICO
DeltaRob
1.00 + 0.00
4.00
0.10
1.00
0.00
5.67 0.58
0.96 0.07
5.70 = 0.72
T.Rex
0.83 0.08
3.12
0.07
0.01
0.00
3.07
2.77 = 0.19
ElliCE
1.00 0.00
3.48
0.10
1.00
0.00
4.32
1.00
1.00
4.00
= 0.24
German
DeltaRob
0.98 =
3,45
0.06
0.99
0.02
4.00 0.15
1.00 - 0.00
3.99
= 0.22
T.Rex
0.99 + 0.01
3,47
0.04
0.97 0.02
4.03 = 0.20
0.99
0.01
4.23 = 0.24
Continuous
(CNT)
ElliCE
0.98 0.01
2.15 - 0.39
0.99 0.02
3.05 = 0,34
0.98
- 0.02
3.22 = 0.40
0.40
PROP
0.48 + 0.48
2.01 + 0.05
0.19 = 0.28
2.01
= 0.05
0.08
0.19
2.01
= 0.05
Diabetes
ROAR
0.86 + 0.11
1.86 + 0.24
0.40 0.28
1.86 - 0.24
0.31
+ 0.26
1.86
- 0.24
T.Rex
0.94 0.03
2.47
+ 0.86
0.90 0.08
4.18 + 0.36
0.94
0.04
4.18 + 0.36
Table 2: Runtime performance and speedups for data-supported CE for MLPs.
Absolute (seconds)
Relative (speedup)
Dataset
EMICE
T:Rex
Delta Rob
Over T:Rex
Over Delta Rob
FICO
1.792 + 0.123
7,006 = 0.058
242.035 = 1.161
3.91x
135.04x 685.34x
COMPAS
0.526 0.011
3.534 = 0.128
360.480 6.701
6.72x
Australian
0.057 0.011
0.281 + 0.006
2.783 = 0.032
4.92x
48. 64
Diahetes
0.053 + 0.001
0.296
+ 0.006
1.922 = 0.032
5.60x
x
German
0.101 0.001 0.432 + 0.013
9.905 = 0.068
4.27x
97.88x
6.1 ElliCE Generates Robust Counterfactuals
Figure D Iillustrates the relationship between the evaluators' multiplicity level Starget and the achieved robustness for the baselines. We report results for both linear models and MLPs for data-supported and continuous methods. Across different settings, we observe that ElliCE consistently produces more robust counterfactuals than baselines. Notably, ElliCE's counterfactuals generally do not hibit a decrease in robustmess as Eureet increases, demonstrating stability under different levels of target multiplicity. This robustness, however, can sometimes come with greater distance from the original instance (i.e., longer CEs), a trade-off that we saw in Section 5 and report in Table I For the MIP setting, empirical results in Figure [ and Table I suggest that ElliCE's ellipsoidal approximation offers good flexibility, allowing it to adapt to the underlying loss function's 's shape.
6.2 EliiE is Efficient
Tables and S clearly demonstrate ElliCE's advantage computational efficiency. Our method is consistently faster than baselines with speedups of up three orders of magnitude. The runtimes of both T.Rex and Delta Robustness tend to grow substantially with the dataset size. In contrast, ElliCE remains lightweight and exhibits better scalability. Across all datasets tested, ElliCE's abso- lute runtimes for generating a counterfactual remain under two seconds. This efficiency comes from closed-form solution for the inner optimization problem (Theorem 1). The primary preprocess- ing cost involves computing and inverting the Hessian matrix H, requiring O(pp²) for computation and (pp²) for inversion, performed once per model (where is the training set size and is the parameter dimension). Per-instance counterfactual generation then requires only O(p²) operations.
6.3 Sensitivity Analysis
Figure (a.b) shows an empirical sensitivity analysis of ElliCE's robustness with respect to its ternal Rashomon parameter The plots show how the achieved robustness (evaluated against the Random Retrain and Ellipsoidal Rashomon set evaluators, respectively) varies as ElliCE's internal changes. These results illustrate that ElliCE can achieve high levels of robustness even for rel-

---

Target é = 0.02
ELLIPSOIE LIIPOIDD Rob ustnnss
Target 0.02
Rashomon Dropout
Diabetes
Diabetes
1.0
1.6
Retrain Robustnes
0.3
0.8
0.6
0.8-
1.4
Australian Credit
0.-
Fico
Diebetes
Compas
02-
Asatra lan Crock
Compas
0.0
0.2
0
1.0
1.2
0.05 0.08
0.0
distance (c)
Target
2,006 Rashomone
Rashomone
0.04
ELLiCE (ours)
Delta Robustness
(a)
(b)
(d)
Figure 2: (a.b) Sensitivity ElliCE's robustness (y-axis) to its internal e hyperparameter (x-axis).
Robustness is evaluated against Random Retrain (a) and an Ellipsoidal Rashomon set approximation defined with a fixed Eurget (b). (c, d) Robustness vs. l2 proximity trade-off (c) and plausibility (d) of
counterfactuals generated by ElIiC and baselines on Diabetes dataset.
atively small values of its internal when evaluated against the Retrain ensemble. For the middle plot (Ellipsoidal evaluator), while initial robustness may be lower for smaller internal e values, the performance increases sharply, as approaches the targeted robustness level.
6.4 Mabustness-Proximiis Trade-off and Plausibility
Figure 2 cc) illustrates the inherent trade-off between robustmess and proximity for CEs generated by ElliCE, supporting our discussion in Section 5 While the trade-off occurs for all baselines, ElliCE achieves the highest robustness at given length level. Understanding this trade-off is key to selecting counterfactuals that balance reliability under model shifts with practical user actionability. ElliCE provides mechanism navigate this by allowing control over its Rashomon parameter. We also observed good plausibility across all baselines and datasets, supported by Figure d) and All LOF values tend to be close thus the generated counterfactuals lie on the data manifold.
6.5 Actionability
To ensure that generated recourse remains realistic and feasible, we incorporate actionability con- straints that specify which features can change and within what ranges. ElliCE supports restrictions on features, including immutable features (c.g., age, citizenship) as well as range and direction con- straints such as income or loan duration. It also allows for sparse counterfactuals by adding an optional penalty on the number of modified features. For instance, before applying actionability, one robust counterfactual on the German Credit dataset suggested changing the applicant's 's age, an immutable feature. After enforcing immutability and sparsity constraints, ElliCE instead adjusted the credit amount and credit length, reducing both and thus lowering the predicted credit risk, which is reasonable in the lending context. Further details are provided in Appendix D
7 Conclusions, Implications and Limitations
Standard algorithmic recourse is fragile. A recommendation given to a user today may become invalid tomorrow if the underlying model is retrained or replaced-a common scenario under the Rashomon Effect. This paper addressed this reliability gap by introducing ElliCE, a framework that provides recourse with provable robustness guarantees. ElliCE approximates the set of near-optimal models with an ellipsoid and computes counterfactuals that remain valid across this approximated Rashomon set. strength of ElliCE its support for actionability. Users can specify immutable features, range or direction constraints, and optional sparsity penalties, ensuring that the resulting recourse is both robust and realistic. This flexibility might help prevent impractical or unethical rec- ommendations and gives users greater control over actions. While robustness alone does not ensure fairness, user-specified actionability constraints can help ensure that counterfactuals remain feasi- ble and ethically sound. A comprehensive fairness analysis remains an important direction for future work. The ellipsoidal approximation, while efficient, simplification of the true Rashomon set, and for neural networks our analysis currently captures local rather than global model multiplicity. Despite these limitations, EIIiCE offers a practical and theoretically grounded tool for robust and actionable recourse, providing stable and trustworthy advice.
10

---

Acknowledgments
We thank the RAI for Ukraine program, led by the Center for Responsible AI New York University in collaboration with Ukrainian Catholic University in Lviv, for supporting Bohdan's and Iryna's participation in this research.
Code Availability
Implementations of ElliCE are available htte://ggtabb.cco/ppddatrtttttll
EXPERTMENTS
References
[1] Rishabh Agarwal, Levi Melnick, Nicholas Frosst, Xuezhou Zhang, Ben Lengerich, Rich Caru- ana, and Geoffrey Hinton. Neural additive models: Interpretable machine learning with neural nets. Advances in Neural Information Processing Systems (NeurIPS), 14:4699-4711 2021.
[2] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's 's software used across the country predict future criminals. And it's biased against blacks. ProPublica, May 2016.
[3] Samy Baladram. Iris dataset extended, 2023.
[4] Michelle Bao, Angela Zhou, Samantha Zottola, Brian Brubach, Sarah Desmarais, Aaron Horowitz, Kristian Lum, and Suresh Venkatasubramanian. It's compaslicated: The messy relationship between rai datasets and algorithmic faimess benchmarks. arXiv preprint arXiv:2106.05499 2021.
[5] Ainhize Barrainkua, Giovanni De Toni, Jose Antonio Lozano, and Novi Quadrianto. Who pays for fairness? Rethinking recourse under social burden. arXiv preprint arXiv:2509.04128, 2025.
[6] Emily Black, Manish Raghavan, and Solon Barocas. Model multiplicity: Opportunities. con- cems, and solutions. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 350-863, 2022.
[7] Zachery Boner, Harry Chen, Lesia Semenova, Ronald Parr, and Cynthia Rudin. Using noise to infer aspects of simplicity without learning. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[8] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[9] Leo Breiman. Statistical modeling: The two cultures (with comments and a rejoinder by the author). Statistical Science, 199-23,,,, 2001.
[10] Dieter Brughmans, Pieter Leyman, and David Martens. Nice: An algorithm for nearest in- stance counterfactual explanations. Data mining and knowledge discovery, 3865):6655-2733 2024.
[11] Mustafa Cavus, Jan N van Rijn, and Przemyslaw Biecek. Beyond the single-best model: Rashomon partial dependence profile for trustworthy explanations in AutoMI.. Interna- tional Conference on Discovery Science, pages 445 459. Springer, 2025.
[12] Marina Ceccon, Alessandro Fabris, Goran Radanović, Asia Biega, and Gian Antonio Susto. Reinforcement learning for durable algorithmic recourse. arXiv preprint 12Xiv2259.22202., 2025.
[13] Paulo Cortez, Cerdeira, Almeida, T. Matos, J. Reis. Wine Quality. UCI Machine Learning Repository, 2009.

---

[14] Gordon Dai, Pavan Ravishankar, Rachel Yuan, Emily Black, and Daniel B Neill. Be intentional about fairness:: Fairness, size, and multiplicity the Rashomon set. Proceedings of the Sth ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 42-73, 2025.
[15] Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al. Un- derspecification presents challenges for credibility in modern machine learning. Journal of Machine Learning Research, 23(226):1-61, 2022.
[16] Jiayun Dong and Cynthia Rudin. Exploring the cloud of variable importance for the set of all good models. Nature Machine Intelligence, 2(12):8 10-824, 2020.
[17] Jon Donnelly, Srikar Katta, Cynthia Rudin, and Edward P Browne. The Rashomon importance distribution: Getting RID of unstable, single model-based variable importance. In Neural Information Processing Systems (NeurIPS), 2023.
[18] Jon Donnelly, Zhicheng Guo, Alina Jade Barnett, Hayden McTavvsh, Chaofan Chen, and Cyn- thia Rudin. Rashomon sets for prototypical-po networks: Editing interpretable models in real-time. In Proceedings of the Computer Vision and Pattern Recognition Conference, pages 4528 4538, 2025.
[19] Sanghamitra Dutta, Jason Long, Saumitra Mishra, Cecilia Tilli, and Daniele Magazzeni. Ro- bust counterfactual explanations for tree-based ensembles. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 5742-5756. PMLR, Jul 2022.
[20] Fair Isaac Corporation (FICO). FICO explainable machine learning challenge: Home equity line of credit (heloc) dataset, 2018.
[21] Aaron Fisher, Cynthia Rudin, and Francesca Dominici. All models wrong, but many useful: Learning a variable's ' importance by studying an entire class of prediction models si- multancously. Journal of Machine Learning Research, 201
[22] Alexandre Forel, Axel Parmentier, and Thibaut Vidal. Don't explain noise: Robust coun- terfactuals for randomized ensembles. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 293-309. Springer, 2024.
[23] Prakhar Ganesh, Afaf Taik, and Golnoosh Farnadi. Systemizing multiplicity: The curious case of arbitrariness in machine learning. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, volume 8, pages 1032-1048, 2025.
[24] Prateek Garg, Lokesh Nagalapatti, and Sunita Sarawagi. From search to sampling: Generative models for robust algorithmic recourse. arXiv preprini arXiv:2505.07351, 2025.
[25] Abirami Gunasekaran, Pritesh Mistry, and Minsi Chen. Which explanation should be selected: A method agnostic model class reliance explanation for model and explanation multiplicity.
SN Computer Science, 5:503, 2024.
[26] Faisal Hamman, Erfaun Noorani, Saumitra Mishra, Danicle Magazzeni, and Sanghamitra Dutta. Robust counterfactual explanations for neural networks with probabilistic guarantees. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[27] Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994.
[28) Hsiang Hsu and Flavio Calmon. Rashomon capacity: A metric for predictive multiplicity in classification. In Neural Information Processing Systems (NeurIPS), volume 35, pages 28988- 29000, 2022.
[29] Hsiang Hsu, Ivan Brugere, Shubham Sharma, Freddy Lecue, and Richard Chen. RashomonGB: Analyzing the Rashomon Effect and mitigating predictive multiplicity in gra- dient boosting. Advances in Neural Information Processing Systems (NeurIPS), 37:121265-
121303, 2024.
12

---

[30] Hsiang Hsu, Guihong Li, Shaohan Hu, and Chun-Fu Chen. Dropout-base Rashomon set exploration for efficient predictive multiplicity estimation. In The Twelfth International Con- ference on Learning Representations, 2024.
[31] Junqi Jiang, Francesco Leofante, Antonio Rago, and Francesca Toni. Formalising the robust- ness of counterfactual explanations for neural networks. In Proceedings the AAAI conference on artificial intelligence, volume 37, pages 14901-14909, 2023.
[32] Junqi Jiang, Jianglin Lan, Francesco Leofante, Antonio Rago, and Francesca Toni. Provably robust and plausible counterfactual explanations for neural networks via robust optimisation. In Berrin Yanıkoğlu and Wray Buntine, editors, Proceedings of the 15th Asian Conference on Machine Learning. volume 222 of Proceedings of Machine Learning Research, pages 582-
597. PMLR, 11-14 Nov 2024.
[33] Junqi Jiang, Francesco Leofante, Antonio Rago, and Francesca Toni. Interval abstractions for robust counterfactual explanations. Artificial Intelligence, 336: 104218, 2024.
[34] Junqi Jiang. Francesco Leofante, Antonio Rago, and Francesca Toni. Recourse under model multiplicity via argumentative ensembling. In Proceedings of the 23rd International Confer- ence on Autonomous Agents and Multiagent Systems, pages 954-964, 2024.
[35] Junqi Jiang, Luca Marzari, Aaryan Purohit, and Francesco Leofante. RobustX: Robust coun- terfactual explanations made easy. arXiv preprint arXiv:2502. 13751, 2025.
[36] Shalmali Joshi, Oluwasammi Koyejo, Warut Vijitbenjaronk, Been Kim, and Joydeep Ghosh. Towards realistic individual recourse and actionable explanations in black-box decision making systems. arXiv preprint arXiv: /00::/907999955 2019.
[37] Moiir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic coun- terfactual explanations for consequential decisions. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the 23rd International Conference on Artificial Intelligence and Statis- ties (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 895-905. PMLR, Aug 2020.
[38] Keita Kinjo. Robust counterfactual explanations under model multiplicity using multi- objective optimization. arXiv preprint arXiv:2501.05795, 2025.
[39] Gunnar König, Hidde Fokkema, Timo Freiesleben. Celestine Mendler- Dünner, and Ulrike von Luxburg. Performative validity of recourse explanations. arXiv preprint arXiv:2506. 2025.
[40] Alejandro Kuratomi, Zed Lee, Panayiotis Tsaparas, Evaggelia Pitoura, Tony Lindgren, Guil- herme Dinis Junior, and Panagiotis Papapetrou. Subgroup fairness based on shared counter- factuals. Knowledge and Information Systems, pages 1-39, 2025.
[41] Phone Kyaw, Kshitij Kayastha, and Shahin Jabbari. Optimal robust recourse with [P- bounded model change. arXiv preprint arXiv:2509.21293, 2025.
[42] Lucas Langlade, Julien Ferry, Gabriel Laberge, and Thibaut Vidal. Fairness and sparsity within Rashomon sets: Enumeration-free exploration and characterization. arXiv preprint arXiv:2502.05286. 2025.
[43] Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin De- tyniecki. Inverse classification for comparison-based interpretability in machine learning. arXiv preprint arXiv: 2017.
[44] Volker Lohweg. Banknote Authentication. UCI Machine Learning Repository, 2012.
[45] Charles Marx, Flavio Calmon, and Berk Ustun. Predictive multiplicity in classification. In Proceedings of the International Conference on Machine Learning (ICML), pages 6765-6774, 2020.
13

---

[46] Rory Mc Grath, Luca Costabello, Chan Le Van, Paul Sweeney, Farbod Kamiab, Zhao Shen, and Freddy Lecue. Interpretable credit application predictions with counterfactual explana- tions. In NIPS 2018-Woor Workshop Challenges and Opportunities for Al in Financial Services: the Impact of Fairness, Explainahility, Accuracy, and Privacy, 2018
[47] Anna P Meyer, Yea-Seul Kim, Loris D' Antoni, and Aws Albarghouthi. Perceptions of the fair- ness impacts of multiplicity in machine learning. In Proceedings of the 2025 CHI Conference on Human Factors in Computing Systems, pages 1-15, 2025.
[48] Kiarash Mohammadi, Amir-Hossein Karimi, Gilles Barthe, and Isabel Valera. Scaling guaran- tees for nearest counterfactual explanations. In Proceedings of the Thirty-Fifth AAAI Confer- ence on Artificial Intelligence, 2021.
[49] Sebastian Müller, Vanessa Toborek, Katharina Beckh, Matthias Jakobs, Christian Bauckhage, and Pascal Welke. An empirical evaluation of the Rashomon Effect in explainable machine learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 462-478. Springer, 2023.
[50] Daniel Nemirovsky, Nicolas Thiebaut, Ye Xu, and Abhishek Gupta. CounteRGAN: Generat- ing counterfactuals for real-time recourse and interpretability using residual GANs. In James Cussens and Kun Zhang, editors, Proceedings of the Thirty-Eighth Conference Uncertainty Artificial Intelligence, volume 180 of Proceedings of Machine Learning Reseurch, pages 1488 1497. PMLR, Aug 2022.
[51] Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic coun- terfactual explanations for tabular data. In Proceedings of The Web Conference 2020 (WWW 200,, pages 3126-3133 3132. ACM/ IW3C2, 2020.
[52] Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodrrguez, Tijl De Bie, and Peter Flach. Face: Feasible and actionable counterfactual explanations. Proceedings of the AAAI/ACM Con- ference on AI, Ethics, and Society, pages 344-350, 2020.
[53] Ross Quinlan. Statlog (Australian Credit Approval). UCI Machine Learning Repository, 1987.
[54] Cynthia Rudin, Chudi Zhong, Lesia Semenova, Margo Seltzer, Ronald Parr, Jiachang Liu, Srikar Katta, Jon Donnelly, Harry Chen, and Zachery Boner. Amazing things come from hav- ing many good models. In Proceedings of the International Conference on Machine Learning (ICML), 2024.
[55] Chris Russell. Efficient search for diverse coherent explanations. In Proceedings of the con- ference on fairness, accountability, and transparency, pages 20-28, 2019.
(56) Lesia Semenova, Cynthia Rudin, and Ronald Parr. On the existence of simpler machine learn- ing models. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1827-1858, 2022.
[57] Lesia Semenova, Harry Chen, Ronald Parr, and Cynthia Rudin. A path to simpler models starts with noise. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[58] John W. Smith, William A. Everhart, William C. Dickson, William C. Knowler, and Richard S. Johannes. Pima Indians Diabetes Database, 1988.
[59] Yiyang Sun, Zhi Chen, Vittorio Orlandi, Tong Wang, and Cynthia Rudin. Sparse and faithful explanations without sparse models. In Proc. Artificial Intelligence and Statistics (AISTATS), 2024.
[60] Athanasios Tsanas and Max Little. Parkinsons Telemonitoring. UCI Machine Learning Repos- itory, 2009.
[61] Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. Advances Neural Information Processing Systems (NeurIPS), 34: 16926-16937, 2021.
14

---

[62] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the conference on fairness, accountability, and transparency, pages 10-19, 2019.
[63] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harv. JL & Tech., 31:841, 2017.
[64] Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi, Margo Seltzer, and Cynthia Rudin. Ex- ploring the whole Rashomon set of sparse decision trees. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, 2022.
[65] Jayanth Yetukuri, Ian Hardy, Yevgeniy Vorobeychik, Berk Ustun, and Yang Liu. Providing fair recourse over plausible groups. Proceedings of the AAAI Conference on Artificial Intelligence, (8(19)221533-2120 Mar 2024.
[66] Chudi Zhong, Zhi Chen, Jiachang Liu, Margo Seltzer, and Cynthia Rudin. Exploring and interacting with the set of good sparse generalized additive models. Neural Information Processing Systems (NeurIPS), 2023.
15

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims in the abstract and introduction are consistent with the paper's scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitation in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
We provide the theorems in the main paper and proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental setups are detailed the Experimental Section and the Ap- pendix. The code is available in the supplement.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (e.g., registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
17

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets used are publicly available (Australian Credit, COMPAS, Dia- betes, FICO, German Credit, etc.). The paper provides sufficient algorithmic details and experimental settings reproduce results. Code is available the supplements.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
wwtpiiicgguieeeeeee http:/guuuieeeeeeeeuuuuteeeee Ctte///oeeeeeeeieeeeee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Section D and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We report and standard deviation multiple runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
18

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our work adheres to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have mentioned the broader impact in the introduction and conclusion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper doesn't 't release models that have the potential to cause harm.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use open access datasets and baselines and cite the sources all the datasets and baselines we used in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, haperswithcooe www.co///aaaooo com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
We provide the code for this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We used LLM for editing and improving the clarity of wording.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy httppe///eerripsss.cooefeeeeeeee for what should or should not be described.
22


Reviews:
[{"review_id": "S8Te5n7VpE", "reviewer": "Reviewer_qf5X", "summary": "The paper introduces **ElliCE**, a framework for generating robust counterfactual explanations under the Rashomon effect. By approximating the Rashomon set as an ellipsoid derived from loss landscape geometry, ElliCE frames robust counterfactual generation as a convex optimization problem. The method claims theoretical guarantees on uniqueness, stability, and alignment with feature importance directions, and empirically outperforms baselines in robustness and computational efficiency across diverse datasets.", "questions": "1. How does your method perform when the true Rashomon set has non-convex or disjoint regions like multiple local optima? For example, in cases where models cluster into distinct subspaces, would the ellipsoidal approximation catastrophically fail? Could this lead to overly conservative counterfactuals that sacrifice proximity for robustness?\n2. The experiments focus on linear models and neural networks with final-layer linearization. How does ElliCE handle deeper architectures? Does linearizing intermediate layers compromise the geometric intuition of the Rashomon set, leading to less robust counterfactuals? What trade-offs arise in non-linear regimes?\n3. Section 4 mentions \"feature-level constraints\". How are these constraints integrated into the optimization?\n4. The method assumes a positive definite Hessian for closed-form solutions. What happens when this assumption fails? For example for non-convex losses or high-dimensional data? How is numerical stability maintained in such cases?", "limitations": "The authors acknowledge the ellipsoidal approximation’s simplification of complex Rashomon sets but do not address critical limitations:\n1. The method lacks analysis under non-convex or disjoint model geometries, which could break theoretical guarantees.\n2. There is no discussion on whether counterfactuals might suggest unethical or harmful feature modifications. While the paper mentions \"actionable\" constraints, these are not explained.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Quality\n### Strength\n1. The work is technically rigorous, with well-formulated theorems. Authors provide closed-form solutions for worst-case models via ellipsoidal approximation. Authors present thorough empirical validation.\n2. Claims are substantiated by experiments showing robustness improvements over baselines like T:Rex and Delta Robustness across linear models and neural networks.\n3. The convex optimization formulation enables significant efficiency gains.\n### Weaknesses:  \n1. The ellipsoidal approximation of the Rashomon set is a simplification that may fail in real-world scenarios where the true set has non-convex or disjoint geometry like multiple local optima. The authors acknowledge this but do not quantify error margins or evaluate performance under such conditions.\n2. Experiments focus on linear models and neural networks with linearized final layer, leaving scalability to deep architectures untested.\n\n---\n## Clarity\n### Strength\n1. The paper is well-structured, with clear sections for background, methodology, theory, and evaluation. Mathematical formulation of ellipsoid derivation is precise.\n### Weaknesses:  \n1. The Background and Notation section would benefit from better structure by splitting it into subsections and adding equation numbers, as it currently explains mathematical foundations in mostly plain text.\n2. The transition from theoretical analysis to empirical validation in Section 6 is abrupt. A clearer roadmap connecting theorems to experimental results would enhance readability.\n3. Technical intuition behind the Hessian-based approximation of the Rashomon set and how it captures model uncertainty is underdeveloped, leaving non-experts struggling to grasp the geometric reasoning.\n\n---\n## Significance\n### Strength\n1. The problem of robust counterfactual generation under model multiplicity is critical for high-stakes domains.\n### Weaknesses:  \n1. While the paper emphasizes technical robustness, it lacks discussion on real-world deployment challenges, such as ensuring that suggested feature changes (e.g., increasing income) are actionable for users.\n2. The societal implications of counterfactuals, particularly in cases where they might reinforce biases or suggest unethical modifications, are not addressed.\n\n---\n## Originality\n### Strength\n1. The method novel contribution lies in integrating convex geometry and robust optimization to generate theoretically guaranteed explanations under model uncertainty, a departure from ensemble-based or MILP methods. \n2. The closed-form solution for worst-case models (Theorem 1) is particularly innovative.\n### Weaknesses:  \n1. While the framework is original in its formulation, some ideas like parameter perturbation robustness [1], are inspired by prior work. \n2. Authors could better explain how the method advances over existing methods that rely on ensembles or MILP [2], rather than geometry-based approximations.\n\n[1] Jiang, Junqi, et al. \"Formalising the robustness of counterfactual explanations for neural networks.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 37. No. 12. 2023.\n\n[2] Leofante, Francesco, Elena Botoeva, and Vineet Rajani. \"Counterfactual explanations and model multiplicity: a relational verification view.\" Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning. Vol. 19. No. 1. 2023.", "was_revised": true, "final_justification": "In the rebuttal discussion, the authors successfully resolved all concerns. I increased the score to 5, conditionally on the improved writing in the camera-ready version.", "rebuttal": "Thank you very much for the review and feedback.\n\n> Quality W1. The ellipsoidal approximation of the Rashomon set is a simplification that may fail in real-world scenarios\n\nThe ellipsoidal approximation is a simplification of the Rashomon set that can be hard to find and fully approximate for a lot of datasets. However, our experiments are not limited to convex geometry only and effectively demonstrate that the approximation works and delivers robust results. More specifically, in Figure 1b, Table 1 and in Appendix C Figure 6 (Figure 11 for non data-supported) we use neural networks with cross-entropy loss and do not expect the loss to be convex. Therefore, we provide empirical evaluation in non-convex scenarios. \n\n>Q2 and  Quality W2. Experiments focus on linear models and neural networks with linearized final layer, leaving scalability to deep architectures untested.\n\nOur methodology is designed to apply to deep architectures by focusing its theoretical guarantees on the network's final linear layer. This layer operates on the embedding created by the preceding deep layers. This allows us to keep the robustness calculation tractable and fast.\n\nOnce a worst-case model is computed in the embedding space using Theorem 1, the framework uses an optimization technique, such as the cutting-plane or gradient descent (we support both), to find the corresponding counterfactual in the original input space. This two-stage process allows the method to scale to deep networks, as our experiments confirm. \nWe will explain this in more detail in the paper.\n\n> Clarity W1: The Background and Notation section would benefit from better structure.\n\nThe background and notation section is only one page long, however, we will apply a modular structure and emphasize changes in the definitions better. We will add equation numbers to improve the paper's clarity.\n\n> Clarity W2: The transition from theoretical analysis to empirical validation in Section 6 is abrupt. \n\nThank you, we will add better smoothing text when transitioning from Section 5 to 6.\n\n> Clarity W3: Technical intuition behind the Hessian-based approximation of the Rashomon set and how it captures model uncertainty is underdeveloped, leaving non-experts struggling to grasp the geometric reasoning.\n\nThe core idea is to view the set of good models (the Rashomon set) as a \"valley\" in the loss landscape. Our method uses the Hessian matrix to mathematically describe the curvature or shape of this valley at its lowest point. A flat valley signifies high model uncertainty (many different models are good), while a steep valley indicates low uncertainty. The ellipsoid is a direct, geometric map of this curvature, providing a tractable representation of the model uncertainty that we use to find a provably robust counterfactual. We will add this more detailed explanation to the paper.\n\nPlease note that Hessian-based approximations are a common technique used in various settings (see [1]-[3]).\n\n[1] Dinh, Laurent, et al. \"Sharp minima can generalize for deep nets.\" International Conference on Machine Learning. PMLR, 2017.\n\n[2] Zhong, Chudi, et al. \"Exploring and interacting with the set of good sparse generalized additive models.\" Advances in neural information processing systems 36 (2023): 56673-56699.\n\n[3] Sagun, Levent, et al. \"Empirical analysis of the hessian of over-parametrized neural networks.\" arXiv preprint arXiv:1706.04454 (2017).\n\n> Limitation2 and Significance W1: While the paper emphasizes technical robustness, it lacks discussion on real-world deployment challenges, such as ensuring that suggested feature changes are actionable for users.\n\nThank you for mentioning this. For the specific case when the users can not change some feature or they are immutable, such as for example, date of birth, we allow the users to select a set of features that they do not want to change (please see Appendix C.5.1 for more details). Technically, to obtain such counterfactuals, we block the gradient when optimizing with gradient descent for non-data-supported counterfactuals and search for counterfactuals that do not change immutable features for the data-supported version.\n\nBecause we are focused on providing a robust and actionable recourse, we also **introduced a series of changes in order to make counterfactuals more actionable**.\n\nMore specifically, we now additionally allow users to \n\n1) Change of the feature in one direction (as if the value can only increase but not decrease, say if a person plans to increase income or spending amount when applying for a credit). \n\n2) Fixed range for the feature. \n\n3) Model for sparsity of the counterfactual explanations. We additionally employ L0 and L1 regularizations to allow for more sparse explanations for the cases when the user wants to change a small number of features. \n\nWe believe that these changes should significantly improve the actionability of our explanations as well as user-experience while working with ElliCE.\n\n> Limitation2 and Significance W2: The societal implications of counterfactuals, particularly in cases where they might reinforce biases or suggest unethical modifications, are not addressed.\n\nWhile our work focuses on the technical challenge of providing reliable recourse, the resulting counterfactuals should be carefully audited in deployment to ensure they do not reinforce systemic biases. We will add this to our paper discussion and conclusions.\n\n> Originality W1: While the framework is original in its formulation, some ideas like parameter perturbation robustness [1], are inspired by prior work.\n\nThank you for your comment. We carefully studied $Delta$-robustness in our paper both empirically and theoretically. Note that $Delta$-robustness works for neural networks only and introduces the perturbation to the whole neural network, while ElliCE uses ellipsoidal approximation in the embedding space for neural networks. In Appendix D (Proposition 1 and Theorem 6) , we theoretically show the limitations of the approach that $Delta$-robustness takes and show that it has limited ability to capture meaningful model multiplicity. Empirically, Ellice achieves better robustness guarantees, please see Figures 4, 6, 10, 11 in Appendix C. \n\n>  Originality W2: How the method advances over existing methods that rely on ensembles or MILP [2], rather than geometry-based approximations.\n\nWe do not rely on ensembles or MIP. Instead, we propose a new method that relies on ellipsoidal approximation for the model multiplicity, gradient optimization for non-data supported counterfactuals and KD-tree and Ball-tree search for data-supported counterfactuals. Our method is much faster (Table 2) and more robust (Figures 4, 6, 10, 11 and Table 4 in Appendix C). \n\n> Limitation1 and Q1. How does your method perform when the true Rashomon set has non-convex or disjoint regions like multiple local optima? \n\nWhile the ellipsoidal approximation simplifies complex Rashomon sets, our empirical results show it remains effective even for non-convex cases. Our experiments with neural networks using cross-entropy loss (Figure 1b, Table 1, Appendix C Figures 6 and 11) demonstrate that ElliCE delivers robust counterfactuals despite non-convex loss landscapes. \n\nIn cases with disjoint regions of good models, the ellipsoidal approximation doesn't fail but provides a local approximation around one optimum . In the worst case, this locality can lead to more conservative counterfactuals (due to the \"price of robustness\") or overly optimistic ones (which are not robust to the true, larger Rashomon set) . To account for multiple local minima, one could consider an ensemble of models trained with different random initializations. Note that we compared ElliCE against such a \"Random Retrain\" evaluation baseline and found ElliCE’s performance to be consistently strong, demonstrating its practical effectiveness even in the mentioned case.\n\n\n\n\n> Q3: Section 4 mentions \"feature-level constraints\". How are these constraints integrated into the optimization?\n\nIn our framework, we allow for mutable and immutable features to handle feature-level constraints. More specifically, the user can tell the algorithms to fix some features and not change their values. We described this in Appendix C7. Implementation-based, we fix gradient flow for the gradient-based method and select counterfactuals that do not change the feature for tree-search optimization. \n\nAfter submission, we further improved our algorithms, and now we also handle: \n\n1) change of the feature in one direction. This is implemented by blocking gradient components that would move features in the prohibited direction.  For the data-supported method, we do prefiltering.\n\n2) fixed range for the feature. This is achieved by restricting gradient flow to stay within bounds and pruning KD-tree searches to exclude out-of-range solutions.\n\n3) sparsity of the counterfactual explanations.  For data-supported counterfactuals, this is implemented by defining a custom distance metric for Ball tree search that combines sparsity and proximity ($metric = C \\times \\ell_0 + \\ell_1$, where a coefficient C prioritizes minimizing the number of changed features). \n\n> Q4: What happens when a positive definite Hessian assumption fails (e.g. for for non-convex losses or high-dimensional data).\n\nThe positive definite Hessian assumption is satisfied by design through regularization. If the Hessian is not positive definite, for instance, due to non-convexity or numerical issues, we perform additional regularization by adding a small multiple of the identity matrix, $\\alpha*I$, to the computed Hessian. This standard technique guarantees the matrix becomes positive definite, ensuring numerical stability. This approach is effective regardless of data dimensionality or the non-convexity of the loss. We will make these details more explicit in the manuscript. \n\n> Formatting issues.\n\nThank you for pointing out the formatting issues. We will fix them."}, {"review_id": "xqHy4JNdY7", "reviewer": "Reviewer_WWfa", "summary": "The authors propose an algorithm for generating counterfactual explanations which are robust to model multiplicity. This is done by employing an ellipsoidal approximation for the Rashomon set, into which the considered model belongs. The trade-off between the Rashomon parameter $\\epsilon$ and the cost of the generated counterfactual (L2 distance to be specific) is analytically derived in case of linear models. Other important properties of the generated counterfactuals such as the uniqueness and monotonicity of the cost w.r.t. the Rashomon parameter are theoretically established. Experiments, conducted over five real-world datasets, demonstrating the performance of the algorithm are presented.", "questions": "1. How does the proposed method compare with the baselines w.r.t. the robustness to changes in training data or re-training on initially unseen data?\n2. Does Theorem 1 still hold in case of a non-linear models (with the assumption of local linearity or linearization in the final layer in case of MLPs)?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths:*\n1. The idea of quantifying robustness of counterfactual explanations w.r.t. an ellipsoidal approximation of the Rashomon set is novel and interesting. Moreover, the experiments demonstrate that this approximation works well enough for other scenarios where the theoretical guarantee does not directly apply.\n2. Experiments are well-detailed and the results are clear. The proposed algorithm shows a significant improvement in counterfactual generating time compared to the baselines (not considering the Hessian and Hessian-inverse computations, which are done once for a training set and a model).\n3. The paper is clearly written and well-organized.\n\n*Weaknesses:*\n1. The main weakness that I am concerned about is the suitability of this approximation of the Rashomon set for characterizing the kind of model multiplicity which can occur in the potential real-world applications. Most of the baselines considered in this paper (e.g.: Trex, Argumentative Ensembling) construct the multiplicity set by changing the training data--hence robustness to changes in training data and retraining on newly arrived data--which is not a scenario considered in this paper. \n\n2. As the authors have already acknowledged, the theoretical analysis is only valid for linear models (or models which allow for such simplifications) which is very restrictive given the domain of potential applications of the algorithm. Moreover, although the authors have mentioned \"Without loss of generality we focus our theoretical analysis on linear predictors...\" in the beginning of Section 4, I do not see how the analysis applies to other non-linear models.\n\nAs I see, the above two factors largely impact the significance of the theoretical and empirical contributions of the paper.\n\n*Minor comments on clarity:*\n1. Cited appendix numbers are missing in the main text.\n2. Reference [51] and [52] looks the same.", "was_revised": true, "final_justification": "I thank the authors for the detailed response. The rebuttal has addressed all my concerns. I believe that it is extremely important to highlight the correspondence of the Rashomon set and the set of models robust to different types of naturally-occurring multiplicities. The additional experiments done by the authors showcase this correspondence, and hence I am happy to raise the rating. I also acknowledge the proposed revisions to the theorem statement and hope that it would be incorporated in the final version.", "rebuttal": "> **W1: Multiplicity computing approach**\n\nThe ellipsoid-based Rashomon sets will contain models that occur due to slight changes in the training data that T:Rex, Argumentative Ensembling are considering, especially for convex losses, such as logistic loss. This is because this Rashomon set contains different coefficient vectors (and thus feature weighting), allowing for diversity of the models. Therefore, if the data shift occurred, there are other models to choose from the ellipsoidal Rashomon set to account for the changes. To support this, we run a simple experiment to show the stability of the ellipsoid-based Rashomon set (see table below). More specifically, we add noise to the data that comes from a Gaussian distribution with 0 mean and variance $\\sigma$ that ranges from 0.1 to 2. \n\nWe consider the hypothesis space of linear models and the German Credit dataset. First, we compute the Rashomon set on the original data (we use 10% of the optimal loss as epsilon and standardize the data). For each variance value, for 100 times, we do the following: 1) sample noise, 2) create a new dataset with added noise, 3) train logistic regression on this new data, 4) check if the Rashomon set contains models with similar performance as this optimal model. Finally, we compute the percentage of cases when the Rashomon set contained a similar performing model on this new data as the optimal one in the table below. We find that the Rashomon set is stable, even for higher levels of noise. Therefore, we expect the ellipsoid to contain models that perform similarly to optimal models on data folds (if not directly containing these optimal models).\n\nTable. Fraction of cases when the Rashomon set trained on original data contains optimal models trained on noise data, with noise $\\sim \\mathcal{N}(0, \\sigma)$.\n| **Applied Variance**, $\\sigma$ | **% Models Inside Ellipsoid** |\n|----------------------|-------------------------------|\n| 0.1                  | 100.0%                        |\n| 0.2                  | 100.0%                        |\n| 0.3                  | 100.0%                        |\n| 0.4                  | 100.0%                        |\n| 0.5                  | 100.0%                        |\n| 0.6                  | 100.0%                        |\n| 0.7                  | 100.0%                        |\n| 0.8                  | 100.0%                        |\n| 0.9                  | 100.0%                        |\n| 1.0                  | 100.0%                        |\n| 1.1                  | 100.0%                        |\n| 1.2                  | 100.0%                        |\n| 1.3                  | 100.0%                        |\n| 1.4                  | 100.0%                        |\n| 1.5                  | 100.0%                        |\n| 1.6                  | 97.0%                         |\n| 1.7                  | 98.0%                         |\n| 1.8                  | 96.0%                         |\n| 1.9                  | 87.0%                         |\n\n> **Q1. How does the proposed method compare with the baselines w.r.t. the robustness to changes in training data or re-training on initially unseen data?**\n\nTo further support that the Rashomon set handles re-training scenarios, we followed a similar setup that T:Rex and Argumentative Ensembling are using. More specifically, we split the data in 2 parts. We use first data part to train our Rashomon set (ElliCE) and train baselines (STCE, RNCE). Second data part we use to train evaluators (random retraining, adversarial weight perturbation, and Rashomon dropout). This, similar to T:Rex and Argumentative Ensembling, considers different data for the methods we evaluate and baselines with which we do the evaluation. For this new evaluation, we still found that ElliCE outperforms or performs on par with the baselines. Since we can not report images, please see the tables below. Here we use Target Epsilon 0.02.\n\nTable: Re-train evaluation of ElliCE for the hypothesis space of linear models \n\n| Dataset    | Method   | Retrain | ROB | AWP     |\n|-----------|-----------|-----------|---------|---------|\n| **COMPAS**     | ElliCE   | 1.0000 ± 0.0000          | 1.0000 ± 0.0000        | 1.0000 ± 0.0000 |\n|            | RNCE     | 1.0000 ± 0.0000          | 0.3377 ± 0.2214        | 0.1121 ± 0.033 |\n|            | STCE     | 0.9982 ± 0.0032          | 0.9994 ± 0.0010        | 1.0000 ± 0.0000 |\n||||||\n| **AustrC**     | ElliCE   | 0.9604 ± 0.0495          | 1.0000 ± 0.0000        | 1.0000 ± 0.0000 |\n|            | RNCE     | 0.9074 ± 0.1604          | 0.7145 ± 0.2481        | 0.7305 ± 0.2320 |\n|            | STCE     | 0.9564 ± 0.0392          | 0.9030 ± 0.0891        | 0.9195 ± 0.0804 |\n||||||\n| **GermanC**    | ElliCE   | 0.9938 ± 0.0108          | 0.9688 ± 0.0541        | 0.9688 ± 0.0541 |\n|            | RNCE     | 0.7880 ± 0.1982          | 0.6239 ± 0.2200        | 0.6614 ± 0.2082 |\n|            | STCE     | 0.7230 ± 0.1399          | 0.5727 ± 0.1416        | 0.6219 ± 0.1305 |\n\nTable: Re-train evaluation of ElliCE for the hypothesis space of multi-layer perceptrons.\n| Dataset    | Method   | Retrain | ROB | AWP     |\n|-----------|-----------|-----------|---------|---------|\n| **COMPAS**     | ElliCE   | 0.9994 ± 0.0010          | 0.9994 ± 0.0010        | 1.0000 ± 0.0000 |\n|            | RNCE     | 0.9994 ± 0.0010          | 0.9988 ± 0.0021        | 0.9994 ± 0.0010 |\n|            | STCE     | 0.9989 ± 0.0020          | 0.7522 ± 0.1958        | 0.9193 ± 0.1326 |\n||||||\n| **AustrC**     | ElliCE   | 0.9305 ± 0.0696          | 0.9865 ± 0.0234        | 0.9527 ± 0.0819 |\n|            | RNCE     | 0.9643 ± 0.0619          | 0.9459 ± 0.0936        | 0.9459 ± 0.0936 |\n|            | STCE     | 0.9554 ± 0.0773          | 1.0000 ± 0.0000        | 1.0000 ± 0.0000 |\n||||||\n| **GermanC**    | ElliCE   | 1.0000 ± 0.0000          | 0.9167 ± 0.1443        | 1.0000 ± 0.0000 |\n|            | RNCE     | 0.8910 ± 0.1887          | 0.9038 ± 0.1665        | 0.9038 ± 0.1665 |\n|            | STCE     | 1.0000 ± 0.0000          | 1.0000 ± 0.0000        | 1.0000 ± 0.0000 |\n\n> **W2 and Q2: The applicability of the results to the non-linear case.**\n\nThank you for pointing this out. “Without loss of generality” in the paragraph on line 146 applies to the second sentence, as our results apply to the embedding space of the neural networks (penultimate layer). In this layer, we do the Rashomon set approximation and use our theory from Theorem 1 to compute the worst-case model for our Rashomon set. Then we can use 2 methods to find counterfactuals in the feature space:\n1) gradient-descent method that is described in Appendix C7. On each step of the algorithm, we compute the weighted sum of the worst base model (based on the formula in Theorem and the optimal model, then do the gradient step\n\n2) cutting-place method that is described on line 187. \n\nWe found the cutting plane method to work very well and better than baselines for smaller Rashomon set epsilons. This method tends to converge faster than gradient descent for smaller epsilons as well. For larger epsilon, we found that the gradient-based method is more stable.\n\nBoth of these methods work for neural networks and allow for robust counterfactuals as our results suggest in the experimental section and appendix. For both, we use our theoretical results from Section 4. So no, *our theory does not apply only to linear models*.\n\nWe will explain the methods and how we use our theoretical results more clearly in the paper. We will also remove “Without loss of generality” at the start of line 146 to not confuse the readers, as it refers to the second sentence. Our new paragraph will say: “We focus our theoretical analysis on linear predictors of the form $f_{\\theta}(x)=\\theta^{\\top}x$. However, the methodology presented here is also applicable to the embedding space of the multilayer perceptrons.”\n\nWe will also fix minor formatting concerns. Thank you again for your review."}, {"review_id": "Nlkp6k5FEM", "reviewer": "Reviewer_MTx2", "summary": "The paper proposes a new method to generate robust counterfactual explanations targeting linear models and MLP for binary classification. This is done by modelling the rashomon set as an ellipsoid in the weight space and formulating an optimization problem for finding robust and closest counterfactuals. Theoretical results on robustness and stability are given for linear models. Experiments involved many tabular datasets with linear models and MLPs. Quality of counterfactuals is evaluated using robustness and proximity metrics, and experiments show better results in these two aspects than two strong baselines.", "questions": "1. Can you comment on the plausibility performance of the proposed method?\n2. Does the proposed method also apply beyond the binary classification setting?\n3. It appears in the code that baseline implementations are taken from the ROBUSTX library, which is not mentioned in the paper.\n\nPlease also see weakness section above.", "limitations": "Limitations are discussed in the paper.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is very well-written. Motivations and problem settings are clear, mathematical definitions are easy to follow, and assumptions are clearly stated.\n2. The proposed method makes sense and works well for the defined scope (robustness for rashomon set + proximity + time). The accompanying theoretical results provide clear evidence of why it works. The way to represent Rashomon set with an ellipsoid is novel.\n3. A good number of baselines and datasets are involved in the experiments (incl. Appendix). Diverse forms of rashomon set construction are included too.\n\nWeakness:\n1. Quality and Significance: The **main concern I have** is the fact that there is no quantitative evaluation about plausibility (data manifold). The two baselines for the evaluation section (RNCE and TREX) are both designed for robustness, proximity, AND plausibility. It is known that there is a proximity-plausibility trade-off for counterfactuals, indicating that both baselines might not have the best proximity in order to achieve plausibility. Therefore, in order to show that the proposed method is indeed better than those two, I think better, or at least comparable, quantitative results in plausibility are also essential, in addition to evaluating robustness and proximity.\n2. Significance: The method applies only to the linear classifier case (line 98 $\\theta \\in \\mathbb{R}^d$) and to binary classification. This is a minor inherent limitation since some previous published works also target such scenarios.\n3. Significance and originality: while the ellipsoid idea is novel (strength No.2), the optimization approach in line 167 and Equation 1 which is the main part of computing the counterfactual, has been quite standard in the literature. The same formulation was used in, e.g., reference [48], [23], and a similar formulation was used in Dominguez-Olmedo et al., 2022 ICML, and Maragno et al., 2023 INFORMS Journal on Computing.", "was_revised": true, "final_justification": "The paper proposes a new method that targets the robustness of counterfactual explanations for recourse purposes. Only a few works in the literature provide provable robustness guarantees in the literature, and this work has it, which is very nice. The biggest concern I had was the lack of detailed quantitative evaluations for the plausibility aspect, and this was addressed in the rebuttal, along with some other minor concerns. I hence raise my rating to 5 and recommend accept.", "rebuttal": "Thank you very much for your review and feedback.\n\n> **W1 and Q1: Can you comment on the plausibility performance of the proposed method?**\n\nThank you for asking about plausibility. Our data-supported counterfactuals are inherently plausible, as they lie on the data manifold. \nAs you mentioned, for non-data supported counterfactuals, there are possible cases when the resulting counterfactuals for continuous data may be in low-density (not plausible) areas. Very often, it happens when the resulting counterfactual is too close to the decision boundary. Note that due to our robustness requirements, we push counterfactuals away from the decision boundary. We can illustrate this on the synthetic examples, based on two Gaussian distributions, where each class $P(y|x)$ comes from a separate Gaussian. Visually, we observe that the resulting ElliCE counterfactuals are pushed towards the mean of the Gaussian of the target class. Visually, they also look in good density regions, where other points are also present. We will add this illustration on the synthetic data to the paper. Also, note that we observe a robustness-proximity trade-off, as we report in Theorem 5.\n\nCounterfactuals might not be plausible when we push too far away from the decision boundary. In case of ElliCE, its hyperparameter epsilon allows us to control for this, as we seek for closest examples for some robustness level.\n\nTo provide more rigorous analysis, we evaluated the plausibility of the counterfactuals using LOF metric (as in [1]). LOF is used for outlier detection, and values close to 1 are preferred. Please see our results in the table below. For data-supported counterfactuals, we have small values comparable to baselines. For non-data supported counterfactuals, ElliCE performs slightly better than TREX and better than ROAR on the diabetes dataset. PROPLACE, which is designed for plausibility, achieves better results on LOF. However, please also note that ElliCE achieved better robustness results as compared to PROPLACE.\nWe will add a more comprehensive study of the plausibility to the paper, if accepted.\n\nTable: Plausibility study of Ellice and baselines under different evaluation strategies.\n| **AWP**               | **Evaluator** |             |             |             |             |\\|     |        |             |             |             |\n|-----------------------|:-------------:|:-----------:|:-----------:|:-----------:|:-----------:|-----|:--------------------:|:-----------:|:-----------:|:-----------:|\n| **Non Data-supported**|               |             |             |             |             |   \\|    | **Data-supported**   |             |             |             |\n| **Dataset**           | **ElliCE**    | **PROPLACE**| **ROAR**    | **TRexI**   |            |  \\|     | **Dataset**          | **ElliCE**  | **RNCE**    | **STCE**    |\n| Bank                  | 1.493±0.046   | 1.106±0.029 | 1.310±0.066 | 1.492±0.075 |             |   \\|    | Austr                | 1.048±0.015 | 1.090±0.040 | 1.077±0.038 |\n| Diab                  | 1.197±0.045   | 1.076±0.027 | 1.249±0.113 | 1.558±0.098 |                |   \\|    | Germ                 | 1.023±0.003 | 1.026±0.001 | 1.032±0.006 |\n| **ROB**               | **Evaluator** |             |             |             |             |    \\|   |        |             |             |             |\n||||||||||||\n| **Non Data-supported**|               |             |             |             |             |   \\|    | **Data-supported**    |             |             |             |\n| **Dataset**           | **ElliCE**    | **PROPLACE**| **ROAR**    | **TRexI**   |             |  \\|     | **Dataset**           | **ElliCE**  | **RNCE**    | **STCE**    |\n| Bank                  | 1.488±0.033   | 1.097±0.033 | 1.310±0.066 | 1.492±0.075 |             |  \\|     | Austr                 | 1.039±0.016 | 1.082±0.040 | 1.067±0.036 |\n| Diab                  | 1.194±0.047   | 1.076±0.020 | 1.274±0.134 | 1.558±0.098 |             |  \\|     | Germ                  | 1.024±0.005 | 1.027±0.002 | 1.031±0.006 |\n| **Retrain**           | **Evaluator** |             |             |             |             |   \\|    |         |             |             |             |\n||||||||||||\n| **Non Data-supported**|               |             |             |             |             | \\|      | **Data-supported**    |             |             |             |\n| **Dataset**           | **ElliCE**    | **PROPLACE**| **ROAR**    | **TRexI**   |             |    \\|   | **Dataset**           | **ElliCE**  | **RNCE**    | **STCE**    |\n| Bank                  | 1.450±0.045   | 1.136±0.023 | 1.319±0.074 | 1.478±0.071 |             |   \\|    | Austr                 | 1.052±0.013 | 1.057±0.015 | 1.051±0.016 |\n| Diab                  | 1.145±0.042   | 1.039±0.014 | 1.338±0.092 | 1.207±0.050 |             |  \\|     | Germ                  | 1.024±0.006 | 1.017±0.005 | 1.020±0.003 |\n\nTo further help to control counterfactuals' actionability and plausibility, we did a series of updates to our algorithm. Besides having immutable features, we now allow:\n\n1) Change of the feature in one direction (as if the value can only increase but not decrease, say if a person plans to increase income or spending amount when applying for a credit). This is implemented by blocking gradient components that would move features in the prohibited direction.  For the data-supported method we do prefiltering.\n\n2) Fixed range for the feature. This is achieved by restricting gradient flow to stay within bounds and pruning KD-tree searches to exclude out-of-range solutions.\n\n3) sparsity of the counterfactual explanations. We additionally employ L0 and L1 regularizations to allow for more sparse explanations for the cases when the user wants to change a small number of features.  For data-supported counterfactuals, this is implemented by defining a custom distance metric for Ball tree search that combines sparsity and proximity ($metric = C \\times \\ell_0 + \\ell_1$, where a coefficient C prioritizes minimizing the number of changed features). \nWe hope that these changes will help the users to find more plausible and actionable counterfactuals and overall contribute to the flexibility of our framework.\n\n[1] Jiang, Junqi, et al. \"Provably robust and plausible counterfactual explanations for neural networks via robust optimisation.\" Asian Conference on Machine Learning. PMLR, 2024.\n\n> **W2: The method applies only to the linear classifier case (line 98 ) and to binary classification.**\n\nElliCE works beyond linear models and works for non-linear hypothesis spaces that can be optimized with gradient descent.\nIn our experimental section, we included results for the multi-layer perceptrons and show that our algorithm effectively works for this case. We describe in the Appendix in Algorithms 1 and 2 the method that we use to compute counterfactuals for the neural network space. Our theoretical section applies to the penultimate layer of the MLP. In this layer, we do the Rashomon set approximation and use our theory in Theorem 1 to compute the worst-case model for the Rashomon set. \nPlease note that a lot of counterfactual generation methods known to us focus on binary classification (except PROPLACE), as it is very popular in tabular data settings. However, it is easy to extend ElliCE to the multiclass setting. We describe this extension below.\n\n> **Q2: Does the proposed method also apply beyond the binary classification setting?**\n\nThere is a simple way to extend our framework to handle one-versus-one multiclass classification. For one versus one, we will assume that we know the target class for the counterfactual. Our task succeeded if, for the resulting counterfactual, the target class’s $y$ logit is higher than each logit of some other class $c$ individually, under the worst-case model within the Rashomon set. \n\nFormally, for a counterfactual point $x_c$: \n$$\n\\min_{\\hat{\\mathcal{R}}(\\epsilon)} (f_{\\theta}^{y} (x_c) - f_{\\theta}^{c} (x_c)) \\ge \\tau, \\qquad \\forall \\space c \\neq y\n$$\n\nwhere $\\hat{\\mathcal{R}}(\\epsilon)$ is our ellipsoidal approximation of the Rashomon set, and $\\tau$ is a margin hyperparameter that we can set to 0. This guarantees that the explanation remains valid across all models within the Rashomon set.\n\nThis way, we get $K−1$ second-order constraints (one for each rival class) and can use the same closed-form inner optimization as in the binary case. The overall optimization problem remains a convex second-order cone program (SOCP). The runtime grows roughly linearly in $K$.\n\nFor neural networks, we apply the same approach using a Rashomon set approximation in the embedding space and a gradient descent or cutting-plane approach, as in our binary case. \n\n> **Q3: It appears in the code that baseline implementations are taken from the ROBUSTX library, which is not mentioned in the paper.**\n\nThank you for pointing this out. You are correct, we used baseline implementations from the ROBUSTX library [2]. We will update the manuscript to include a proper citation and clarify that baselines implementation was done using ROBUSTX.\n\n[2] Jiang, Junqi, et al. \"RobustX: Robust Counterfactual Explanations Made Easy.\" arXiv preprint arXiv:2502.13751 (2025).\n\n> **W3: The optimization approach in line 167 and Equation 1 is standard.**\n\nWe actually think it is a good thing that the definition and high-level optimization problem for the counterfactual explanation is standardized in the literature and community. Note that the optimization problems that you mentioned are quite general: minimize the distance with respect to some constraints. And here is where ElliCE shines, as we provide new way of handling constraints: using the Rashomon set that we approximate with an ellipse. Our experiments show that this approximation of the Rashomon set is effective when we use multiplicity evaluation baselines such as AWP and random retrain."}, {"review_id": "zuGyniZ33H", "reviewer": "Reviewer_cC5H", "summary": "This paper proposes a method that computes counterfactual explanations (CEs) that are robust to changes in the model if the changed model’s performance is within some bound of the original model. This is achieved by computing an ellipsoidal approximation of the Rashomon set (the set of all near-optimal models). This creates a quadratically constrained quadratic program that is solved as a second-order cone program. This formulation guarantees robustness to models in the Rashomon set (defined by some distance epsilon from the optimal solution), and also guarantees uniqueness and stability of the CE. The experiment results show that the proposed method is more robust than baselines, and significantly faster.", "questions": "1. Line 148, for MLPs, is the CE given in terms of the original feature space, or of the output values of the last MLP layer?\n2. Line  154, is this approximation an over or under approximation?\n3. Line 159, 160, how likely is the assumption that the Hessian matrix H is positive definite?\n4. Line 198 states that the data-supported CE generation is used in section 6. Is the non-data supported CE generation also empirically tested? Or if not, why is it included in the text?\n5. Line 251-254 mentions the trade-off between robustness and proximity of the CE. How, in practice, is the right value for epsilon chosen? \n6. Why are two different target epsilon values used in Fig. 2? How are these values chosen?\n7. Line 308-309, why is validity maximized in the grid search? Why not robustness or proximity or a trade-off?\n8. Line 308-309, how can validity be used in the grid search for ElliCE if by line 206-209 validity is guaranteed, and line 322-323 also confirm 100% validity? Fig. 1, why is ElliCE’s robustness not always 100%?\n9. Line 320-321, why does ElliCE operate on the features of the penultimate layer of a neural network? What guarantees does this provide?\n10. How are the datasets presented in Table 1 selected? And why are robustness results in Table 4 much lower for the baselines?", "limitations": "The theoretical guarantees assume that the Hessian is positive definite. This is mentioned, but not reflected on how restrictive this assumption is.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The proposed method improves on baselines in terms of runtime, robustness, and proximity of the explanation.\n\nWeaknesses:\n- The motivation for robustness under the Rashomon effect is weak\n- The paper contains many notation and typographic mistakes, see the list below.\n- The paper leaves too many open questions (see below)\n\nSmall comments:\n- Missing space on line 73 after Perturbations.\n- In line 98, the parameter vector is defined as an element of the (strict) subset of R^d, but if the hypothesis space is a multi-layer perceptron, this is not correct. Also, why is this Theta a strict subset?\n- Line 116, R(epsilon) has a hat, while it was defined without one in line 109. Also line 296, or is this the approximated Rashomon set defined in line 278-289?\n- Line 120, “an data point”\n- Appendix ?? several times\n- Line 134, the full stop between l_mix and l_2 can easily be mistaken for a multiplication dot.\n- Line 138, why switch from x_c and x_0 to x and x’? Similarly, line 139 switches to accessing x by one index i (or j), whereas line 136 uses two indices. This is inconsistent.\n- Line 135 defines v_l_2, whereas  line 138 defines l_mix. Why not define either both v_l_2 and v_l_mix, or both l_2 and l_mix?\n- Line 151 uses p for the number of features, while this d is used in line 95, and even the very next line 152 uses d also. Line 225 uses p again.\n- Line 151 missing a closing bracket } before ([44]) also, why () around [44]?\n- Line 216, x_c is not bold (twice)\n- Line 293, double usage of the symbol c\n- Line 293, switched from using the big one notation (line 139-140) to big I for the indicator function. Line 298 switches back again.\n- The fonts in Fig. 1 are too small\n- Table 1 and Fig. 1 appear two pages before they are mentioned in the text\n- Table 1, R is not defined. Probably the robustness?\n- Fig. 2 ROB robustness is not defined\n- Figures use a different epsilon symbol than the main text (\\epsilon vs \\varepsilon)\n- Links in the appendix don’t work\n- Table 3 in the appendix extends into the margins\n- Table 4 in the appendix does not describe what the dash means\n- Table 4 does not consistently mark lowest proximity values bold", "was_revised": true, "final_justification": "My original score (2) was mainly based on (a) the paper's quality and clarity of writing, and (b) the amount of questions were triggered, specifically in the empirical section, which both did not reflect a high-quality submission.\nDespite this, I actually agree with the other reviewers that the paper is well-written, as in comprehensible, but somewhat sloppy, and lacking important details.\n\nThe strength of the paper is that it proposes a strong method with useful theoretical and empirical analysis. If the current version of the paper gets rejected, I am sure that a future improved version will find publication.\n\nMost of my questions have been answered well in the rebuttal. Specifically, my concern about the assumptions on the Hessian and on how the experiments were run are solved.\n\nThe question remains if the authors will succeed in improving the clarity or whether an updated version requires another round of review. \n\nGiven the strength of the method, and the other reviewer's positive appreciation of the work I ended up at a borderline accept.", "rebuttal": "Thank you so much for your review and feedback.\n\n> **W1: The motivation for robustness under the Rashomon effect is weak.**\n\nThe robustness under the Rashomon effect is a critical and practical motivation for our work. Most counterfactual explanation methods operate on the assumption that the underlying predictive model is fixed. They generate explanations, often very close to the decision boundary, that are valid for one specific model. In practice, this assumption rarely holds. In many real-world applications, especially on tabular data, numerous distinct models can achieve similar, near-optimal performance. This is known as the Rashomon effect, or model multiplicity. Institutions may switch between these equally good models as part of regular maintenance, retraining cycles, or to adapt to minor shifts in data. This leads to a significant reliability problem. A counterfactual action guaranteed to work for one model may fail completely if another one is deployed. This undermines the entire purpose of algorithmic recourse, which is to provide reliable and actionable paths to a desired outcome.\n\nOur work, ElliCE, directly confronts this failure point. Instead of generating an explanation for a single model, we produce recourse that is provably valid across an entire ellipsoidal approximation of the Rashomon set. This ensures the explanation given to individuals is a robust and reliable action, closing a gap in providing trustworthy algorithmic recourse under real-world model uncertainty.\n\n> **Small comments**\n\nThank you for such a detailed list of typos and suggestions. We will incorporate them, including fixing typos, notation, increasing fonts, improving margins, and so on. Next, we focus on clarifying questions and details.\n\n> **In line 98, the parameter vector is defined as an element of the (strict) subset of R^d, but if the hypothesis space is a multi-layer perceptron, this is not correct. Also, why is this Theta a strict subset?**\n\nThe notation is a general formalization. For MLP, d represents the total number of weights and biases across all layers. The strictness is not necessary. It is a common formality used for the convenience of theoretical results. \n\n> **Line 116, R(epsilon) has a hat, while it was defined without one in line 109. Also line 296, or is this the approximated Rashomon set defined in line 278-289?**\n\nWe used a hat to show that the Rashomon set is empirical, as constructed on the empirical data and not on the distribution. We will improve the consistency of the notation.\n\n> **Line 148, for MLPs, is the CE given in terms of the original feature space, or of the output values of the last MLP layer?**\n\nThe counterfactual explanations are given in the original feature space. While we construct the ellipsoidal approximation of the Rashomon set in the embedding space produced by the penultimate layer of the neural network, we map this information back to the original feature space. Our algorithms (both gradient-based and cutting plane methods) operate directly in the input space while using the worst-case model identification from the embedding space to guide the search for robust counterfactuals. This approach allows us to provide explanations in terms of the original features that users can understand and act upon.\n\n> **Line 154, is this approximation an over or under approximation?**\n\nUsing the Hessian matrix to define the set generally results in an under-approximation of the Rashomon set. The ellipsoidal set can be understood as a tractable geometric approximation based on the local curvature of the loss function.\n\nPlease note that for L2 regularized mean-squared error, the Rashomon set can be computed exactly as an ellipsoid, meaning it is not an approximation in that scenario.\n\n> **Limitations and Line 159, 160, how likely is the assumption that the Hessian matrix H is positive definite?**\n\nThe positive definiteness of the Hessian matrix is a reasonable assumption in our context. For linear models with convex losses, the Hessian is positive definite by definition. For neural networks, where the loss landscape may be non-convex, we ensure numerical stability by adding a small regularization term to the computed Hessian (equivalent to L2 regularization with a parameter). This practice is standard in optimization literature and guarantees that our ellipsoidal approximation remains well-defined. Our experiments confirm that this approach works effectively across diverse datasets and different model classes. Therefore, the positive definite Hessian assumption is a standard condition in the context of regularized models and is satisfied within our paper’s framework.\n\n> **Line 198 states that the data-supported CE generation is used in section 6. Is the non-data supported CE generation also empirically tested? Or if not, why is it included in the text?**\n\nYes, we provide the results for non-data supported counterfactual generation in Appendix C.7. We couldn’t include these results in the main paper due to space constraints, so we moved a lot of empirical findings to Appendix.\n\n> **Line 251-254 mentions the trade-off between robustness and proximity of the CE. How, in practice, is the right value for epsilon chosen?**\n\nAs we state in Section 6, all multiplicity parameters ($\\epsilon$ for ElliCE, $\\delta$ for Delta Robustness, or $\\tau$ for T:Rex)  for each baseline are tuned via grid search on the validation set, basically maximizing validity. Given the robustness-proximity trade-off, this approach ensures that the counterfactual explanations are long enough to ensure the basic requirement, which is validity, but still satisfy the proximity requirement. We use grid search to provide each method the capacity to be robust, as the parameters of the baselines are not interpretable, and the papers of the baseline method often do not provide details on how to choose them. We provide guidelines on selecting a suitable epsilon in Appendix C4\n\n> **Why are two different target epsilon values used in Fig. 2? How are these values chosen?**\n\nThe target epsilon defines the allowable tolerance in empirical loss used to construct the evaluator baselines (Random Retrain, AWP, and Rashomon Dropout). For the analyses in Figure 2, the values of 0.02 and 0.04 were chosen arbitrarily from within a predefined range of [0, 0.1] as representative examples of possible loss increases due to model multiplicity.\n\n> **Line 308-309, why is validity maximized in the grid search? Why not robustness or proximity or a trade-off?**\n\nWe maximize validity during grid search because it's the fundamental prerequisite for counterfactual explanations. Optimizing directly for robustness would create circular reasoning since our evaluators depend on the same parameters we're tuning. Validity provides a fair comparison baseline across methods, after which the inherent robustness-proximity trade-offs of each method can be meaningfully compared.\n\n> **Line 308-309, how can validity be used in the grid search for ElliCE if by line 206-209 validity is guaranteed, and line 322-323 also confirm 100% validity? Fig. 1, why is ElliCE’s robustness not always 100%?**\n\nFor a given data point, a valid counterfactual might not exist if the robustness constraint ($\\epsilon$) is too large, making the problem infeasible. The grid search tunes epsilon to maximize the number of data points for which a valid counterfactual can be found.\nElliCE's robustness is not always 100% because it is guaranteed for its internal ellipsoidal approximation, but it is evaluated against different evaluators (e.g., Random Retrain, AWP, Dripout) . Since these approximation sets are not identical, a counterfactual proven robust for one set may not be valid for all models in the other.\n\n> **Line 320-321, why does ElliCE operate on the features of the penultimate layer of a neural network? What guarantees does this provide?**\n\nElliCE operates on the penultimate layer to treat the neural network's final layer as a simple linear model. This makes the problem tractable and allows the same convex optimization framework to be applied directly.\n\n> **How are the datasets presented in Table 1 selected? And why are robustness results in Table 4 much lower for the baselines?**\n\nTable 1 or the main text is a subtable of Table 4 from the Appendix. The choice of datasets is random. The robustness results for the baselines are lower because ElliCE performs better."}]

Author rebuttal:

Meta-review: The paper proposes ElliCE, a method for generating counterfactual explanations robust to model multiplicity by approximating the Rashomon set with an ellipsoid, offering provable guarantees and strong empirical results.  Its main strengths are the novel geometric formulation, clear theoretical contributions, and efficiency gains.  Weaknesses include reliance on simplifying assumptions, limited theoretical scope beyond linearized models, and incomplete treatment of plausibility and societal implications, alongside clarity issues.  The decision to accept rests on the significance of providing provably robust and efficient recourse, which outweighs these shortcomings.  During discussion, concerns about non-convexity, scalability, plausibility, and clarity were largely resolved by the rebuttal, with reviewers raising their scores.
Decision: Accept (spotlight)