- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies local sensitivity. Previous work defined global sensitivity which searches for sensitive pairs of inputs that differ only in a subset of features but receive a different prediction. This paper defines local sensitivity where one of the two inputs of a sensitive pair has its values fixed. The paper proves that this problem is difficult. Local sensitivity algorithms can be used for other tasks: contrastive explanations and robustness checking. The difference between the existing concept of robustness (Chen et al. 2019) is the limitation in the number of features that are modified.
Critical strengths
The paper studies an interesting and relevant problem. The complexity analyses provided in the paper are interesting.
Critical weaknesses
The introduced concepts are different from existing concepts (robustness, counterfactual explanations) only in minor details.
Similarly, the algorithms introduced in this paper (RegEnum and the MILP encoding) are minor adaptations of existing techniques (RegEnum: Martens et al. ICML'26, MILP: Varshney et al ICLR'26 (as cited in paper)).
The monitoring application does not mention the high (or exact) similarity to empirical robustness evaluation (eg. Kantchelian et al. 2016 and others). The link to the monitoring problem studied by Gupta et al. 2025 seems somewhat forced, maybe in an attempt to make the application seem more novel than it is.
Questions for authors
- Adversarial examples are typically unrestricted in what features can be modified. Does the restriction of the feature set S make the problem easier? That is, could you take any existing adversarial example generator to find sensitive pairs by "fixing" the features not in S by pruning the decision trees?
- For the contrastive explanations, the focus seems to be on finding the smallest subset of features S that all require a change of value in order to flip the prediction. As far as I understand, Local-Sens takes an S as input and you use an additional routine on top of Local-Sens to find this minimal S. Couldn't you use any other verification tool instead of local sense in that routine, and hence, isn't the subroutine the novelty here?
- How is the monitoring problem of RQ3 different from robustness checking? And if it isn't different, why do you not compare to other robustness checking approaches?
Q1. … could you take any existing adversarial example generator to find sensitive pairs …
We thank the reviewer for this suggestion. Local sensitivity indeed reduces to local robustness: fixing the features outside S to their values in v (equivalently, pruning the DTE with the box $Nbd_{S,\varepsilon}(v) $) yields a robustness query over the remaining features, and local robustness is the special case S = F. Restricting S does not make the problem easier in general: local sensitivity remains NP-complete and is W[1]-hard parameterized by |S| (Section 4), though it is in XP.
We will make it clear that the focus of our article was to establish the problem of local sensitivity and how it can help solve other relevant problems, in particular the problem of explainability.
Q2. … Couldn't you use any other verification tool instead of local sense in that routine …
A CXp is a subset-minimal set of features S such that changing only the features in S, can flip the prediction. This condition is exactly the definition of the ensemble being (0,S,∞)-sensitive at v (Lemma 7). Every query in the routine is therefore a local sensitivity query, and any verifier used as the oracle has to solve local sensitivity. This makes local sensitivity the natural primitive for computing CXps.
Q3. How is the monitoring problem of RQ3 different from robustness checking? …
In RQ3, we run the local sensitivity check on each input with varying all features. Local sensitivity is exactly ε-robustness (Lemma 1). What RQ3 compares is two ways of monitoring a stream of inputs. Any sound and complete robustness checker applied to each input would raise the same alarms as ours. RQ3 is about which violations can be detected, not about how fast a single check runs, so we compare against the monitor rather than against other robustness checkers. We will clarify this in the final version.