- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies how predictions change under feasible input interactions. It defines responsiveness as the probability of attaining a target output, estimated through constrained sampling and assessed using binomial statistical tests. The authors propose a unified auditing framework and demonstrate applications to recourse, gaming, and LLM safety.
Critical strengths
- This paper proposes a useful common interface for specifying actionable changes, joint constraints, and stochastic downstream effects.
- The evaluation is under black-box setting and the reuse of sampled inputs across models is a practical design.
Critical weaknesses
- There seems to be a limited distinction from the closest prior work:"Feature Responsiveness Scores: Model-Agnostic Explanations for Recourse ICLR 2025", already introduces responsiveness probabilities, rejection sampling for continuous features with downstream effects. The statistical guarantees largely apply standard binomial inference rather than establish a substantial new theoretical result.
- The guarantees do not support several safety interpretations. Low responsiveness under uniformly sampled actions does not establish that a prediction is fixed or that recourse is impossible. Similarly, low random-action gaming probability does not establish robustness against a strategic attacker. The conclusions should distinguish distribution-dependent probabilities from existential or worst-case guarantees.
- Sampling correctness is insufficiently established (in Alg.1). The statistical results require i.i.d. samples, but set union discards duplicates in discrete spaces and can prevent termination when fewer than (n) distinct points are reachable. The algorithm does not justify the claimed generality or the assumptions underlying certification.
- The main algorithmic advantage is not demonstrated. No runtime, acceptance-rate, scaling, or partitioning ablation establishes efficient sampling under complex constraints. Fig. 2 evaluates statistical accuracy versus sample count, rather than the computational cost of generating samples. This leaves the framework’s principal computational contribution insufficiently supported.
Questions for authors
- Does retraining without age or drug-abuse features reduce preclusion as claimed in Sec. 4.2? Allowing these features to change during an audit does not establish the effect of removing them from model training.
3 comments
The guarantees do not support several safety interpretations [...] conclusions should distinguish distribution-dependent probabilities from existential or worst-case guarantees.
Our guarantees are exact for existential claims (some feasible action attains the target). A single sampled action that is responsive proves that recourse exists, or that a prediction can be gamed.
Universal claims (no feasible action attains the target) are different. With only black-box query access, no finite procedure can certify this, since the region that attains the target prediction can be arbitrarily small. Instead, we provide a statistical certificate with a clear interpretation: when we reject the null hypothesis (i.e., ), with confidence , fewer than of feasible actions attain the target. Practitioners choose and to match the stakes of their application, and our sample-size results (Proposition 3, Remark 4) tell them how many samples they need.
We default to uniform sampling because it does not require a cost model nor an attacker model, which we rarely know. When practitioners need stronger claims, our framework offers two options:
- Enumeration (Section 4.1) gives exact responsiveness when the action set is discrete.
- Importance sampling (Section 3.3) concentrates samples on actions a strategic attacker is likely to take.
Sampling correctness is insufficiently established (in Alg.1)
Thank you for catching this. Our implementation retains duplicate samples, but the set union notation in Algorithm 1 did not reflect that. We have revised Algorithm 1 to be precise (most notably, it now returns an indexed sequence ). We have also clarified in Section 2 that we repeat the sampling procedure independently. In Appendix C.1, we now state the assumptions required for the algorithm to terminate almost surely and return i.i.d. samples from the specified distribution.
The main algorithmic advantage is not demonstrated
With the extra space, we added an additional experiment in Section 4.1 that evaluates runtime and the benefit of partitioning when generating reachable points. In short, our sampling method with partitioning reduces the total runtime by at least 66% and 34% over naive sampling and enumeration, respectively. Thus, our sampling procedure can make verification practical when constructing the full reachable set is too costly. We can also apply our sampling procedure to continuous or mixed (discrete and continuous) settings, which enumeration cannot handle.
Does retraining without age or drug-abuse features reduce preclusion as claimed in Sec. 4.2?
This is a great question and yes, it does reduce preclusion! When we train without the two features, only 2.7% of defendants predicted to recidivate remain effectively fixed. We have added this detail at the end of Section 4.2 in our revision.
[1] Cheon, Seung Hyun, et al. "Feature responsiveness scores: Model-agnostic explanations for recourse." International Conference on Learning Representations 2025.
Response to authors
Thanks for the detailed answers to my concerns and questions. I believe much of my concerns have been well responded and addressed. I will raise my rating from 2 to 3.
Thank you for your time and feedback! We appreciate your comments and concerns, which have helped us to refine our paper. We would like to address them below:
We would like to highlight two main differences:
Purpose: Cheon et al. [1] propose Feature Responsiveness Scores as an explanation method for algorithmic recourse. We propose an auditing framework for safety with statistical guarantees. These two methods are typically useful at different stages of the model lifecycle. Practitioners would use a post-hoc explanation method like Feature Responsiveness Scores after they deploy a predictive model (e.g., to provide explanations that are compliant with regulations). In contrast, one would use our testing framework before deployment to ensure that their models assign safe predictions under interactions.
Scope of interactions (1-D vs. n-D): Feature Responsiveness Scores aim to measure the responsiveness of each feature; it only considers changes in a single feature (see Definition 3 in [1]). We work with a superset of interactions considered in [1] --- feasible interactions across all features.
Feature Responsiveness Scores asks the question:
How responsive is feature j?
In contrast, we ask:
How responsive is f(x)?
All features of x may have responsiveness scores of 0 while f(x) still has positive responsiveness. This happens when no single-feature action attains the target, but at least one multi-feature action does.
Therefore, feature responsiveness scores in [1] are a special case/application of our definition of responsiveness, where we only consider single-feature interactions. Hence, our sampling algorithm and the optimization problem associated with the algorithm is more complex than the ones in [1]. Because we are dealing with a much larger space of interactions, the partitioning step (lines 1–3 in Algorithm 1) is necessary for the sampling to be computationally tractable.
We have clarified this in lines 100-110 of the related work section in our revision (new text in bold, citations in here correspond to references in the paper):
“On the technical front, our proposal is most closely related to research on algorithmic recourse. Existing methods find recourse actions [see e.g., 24, 39, 53], often for specific model classes [39, 50], or certify the feasibility of recourse only over discrete feature spaces [25]. We generalize the notion of responsiveness proposed by Cheon et al. [7], who introduce Feature Responsiveness Scores to explain opportunities for recourse through changes to individual features. Our framework instead tests responsiveness under feasible interactions across all features. To verify responsiveness, we build on the model-agnostic machinery of Kothari et al. [25], who construct the set of all points reachable through interactions. We extend their approach to be compatible with any dataset and replace enumeration with sampling, which makes verification computationally viable for complex interaction models with probabilistic downstream effects. As a result, our approach can certify the feasibility of recourse over any dataset, requires only black-box access, and returns practical guarantees.”
Section 3 indeed uses classical statistical results. This is by design, as our contribution is not a new statistical test, but rather a new object to test. Responsiveness unifies a broad class of safety failures as a single testable quantity. The technical work is what makes standard inference possible here:
This lets us rely on standard statistical inference, which gives practitioners exact guarantees that they are already familiar with.