{'fraction_non_alphanumeric': 0.03754721804084183, 'fraction_numerical': 0.008605754210571161, 'mean_word_length': 4.595994914176733, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Solvability of Interpretability Evaluation Metrics

Feature attribution methods are popular for explaining neural network predictions, and they are often evaluated on metrics such as comprehensiveness and sufficiency, which are motivated by the principle that more important features -- as judged by the explanation -- should have larger impacts on model prediction. In this paper, we highlight an intriguing property of these metrics: their solvability. Concretely, we can define the problem of optimizing an explanation for a metric and solve it using beam search. This brings up the obvious question: given such solvability, why do we still develop other explainers and then evaluate them on the metric? We present a series of investigations showing that this beam search explainer is generally comparable or favorable to current choices such as LIME and SHAP, suggest rethinking the goals of model interpretability, and identify several directions towards better evaluations of new method proposals.


Introduction
For neural network models deployed in high stakes domains, the explanations for predictions are often as important as the predictions themselves. For example, a skin cancer detection model may work by detecting surgery markers (Winkler et al., 2019) and an explanation that reveals this spurious correlation is highly valuable. However, evaluating the correctness (or faithfulness) of explanations is fundamentally ill-posed: because the explanations are used to help people understand the reasoning of the model, we cannot check it against the ground truth reasoning, as the latter is not available.
As a result, correctness evaluations typically employ proxy metrics. For feature attribution explanations, they work under a shared principle: changing an important feature should have a large impact on the model prediction. Thus, the quality of the explanation is defined by aspects of the model prediction change, such as comprehensiveness and sufficiency  ( DeYoung et al., 2020). To develop new explanation methods (Fig. 1, left), people generally identify a specific notion of feature importance (e.g. local sensitivity), propose the corresponding explainer (e.g. gradient saliency (Simonyan et al., 2014)), evaluate it on one or more metrics, and claim its superiority based on favorable results vs. baseline explainers. As they are motivated by notions of feature importance, we call them heuristic explainers.
In this paper, we show that all these metrics are solvable, in that we can define an explanation as the one that optimizes a metric value and search for it. The elephant-in-the-room question is then: if we take a specific target metric to represent correctness, why don't we just search for the metricoptimal explanation (Fig. 1, right) but take the more convoluted route of developing heuristic explanations and then evaluating them (Fig. 1, left)?
There are several possible reasons. First, the optimization problem may be so hard that we cannot find an explanation better than the heuristic ones. The bigger concern, however, is that of the Goodhart's Law. In other words, as soon as a metric is used in explicit optimization, it ceases to be a good metric. Concretely, the explanation may overfit to the particular metric and perform much worse on closely related ones (Chan et al., 2022), or overfit to the model and effectively adversarially attack the model when assigning word importance (Feng et al., 2018). It may also perform poorly on evaluations not based on proxy metrics, such as ground truth alignment (Zhou et al., 2022a).
We assess these concerns, taking the widely used comprehensiveness and sufficiency metrics (DeYoung et al., 2020) as the optimization target. Our findings, however, largely dispel every concern. A standard beam search produces explanations that greatly outperform existing one such as LIME and SHAP on the target metric. On several other metrics, the search-based explainer also performs favorably on average. There is no strong evidence of it adversarially exploiting the model either. Last, it achieves competitive performances on a suite of ground truth-based evaluations.
Hence, we argue that we should rethink the development of novel explainers. First, the searchbased explainer should be considered as a strong baseline. In addition, Sec. 6 presents the lack of privileged information as the fundamental reason for metric solvability: the beam searcher knows exactly how to produce an (approximately) optimal solution. This loophole is fixed in the ground truth-based evaluations. Finally, we advocate for evaluations that can demonstrate concrete utilities of explanations in real-world scenarios.

Background and Related Work
In this section, we give a concise but unified introduction to the popular feature attribution explainers and evaluation metrics studied in this paper.

Feature Attribution Explainers
We focus on feature attribution explanations, which explains an input x = (x 1 , ..., x L ) by a vector e = (e 1 , ..., e L ) where e l represents the "contribution" of x l to the prediction. Many different definitions for contribution have been proposed and we consider the following five. • Vanilla gradient (Grad) (Simonyan et al., 2014;Li et al., 2016a) is the L2 norm of gradient of the prediction (in logit, following standard practice) with respect to the token embedding. • Integrated gradient (IntG) (Sundararajan et al., 2017) is the path integral of the embedding gradient along the line segment between the zero embedding value and the actual value. • LIME (Ribeiro et al., 2016) is the coefficient of a linear regression in the local neighborhood.
• SHAP (Lundberg and Lee, 2017) computes the Shapley value (Roth, 1988) for each word. • Occlusion (Occl) (Li et al., 2016b) is the change in prediction when a word is removed from the input while all other words remain.

Feature Attribution Evaluations
Naturally, different definitions of contribution result in different explanation values. As findings (e.g. Adebayo et al., 2018;Nie et al., 2018) suggest that some explanations are not correct (i.e. faithfully reflecting the model's reasoning process), many evaluations are proposed to quantify the correctness of different explanations. Not having access to the ground truth model working mechanism (which is what explanations seek to reveal in the first place), they are instead guided by one principle: changing an important feature (according to the explanation) should have a large impact on the prediction, and the impact size is taken as explanation quality. However, there are different ways to quantify the impact, leading to different evaluations, and we consider six in this paper.
Let f : X → R be the function to compute model prediction. We define it as the scalar function, such as the probability for the predicted class. For an input x = (x 1 , ..., x L ) of L words and a feature explanation e, we can create a sequence of L + 1 input deletionsx (0) ,x (1) , ...,x (L) where that x (l) is the the input but with l most important features removed. Thus, we havex (0) = x andx (L) being the empty string. The comprehensiveness κ (DeYoung et al., 2020) is defined as It measures the deviation from the original model prediction when important features (according to e) are successively removed, and therefore a larger value is desirable. It was also proposed earlier for computer vision models as the area over perturbation curve (AoPC) by Samek et al. (2016).
Analogously, we can define the sequence of input insertions x (0) , x (1) , ..., x (L) , where x (l) is the input with the l most important features present. Thus, x (0) is the empty string and x (L) = x, but otherwise the sequences of input insertions and deletions do not mirror each other. The sufficiency σ (DeYoung et al., 2020) is defined as It measures the gap to the original model prediction that remains (i.e. convergence to the model prediction) when features are successively inserted from the most important to the least. Therefore, a smaller value is desirable.
Another interpretation of prediction change just considers decision flips. Let g : X → {0, ..., K} be the function that outputs the most likely class of an input. The decision flip by removing the most important token (Chrysostomou and Aletras, 2021) is defined as which measures whether removing the most important token changes the decision. Across a dataset, its average value gives the overall decision flip rate, and a higher value is desirable.
The fraction of token removals for decision flip (Serrano and Smith, 2019) is defined as and we define DF Frac = 1 if no value of l leads to the decision flip. This metric represents the fraction of feature removals that is needed to flip the decision, and hence a lower value is desirable. Last, two metrics evaluate correlations between model prediction and feature importance. For an input x and explanation e, we define the sequence of marginal feature deletions x where ρ(·, ·) is the Spearman rank correlation coefficient between the two input vectors. Intuitively, this metric asserts that suppressing a more important feature should have a larger impact to the model prediction. A higher correlation is desirable. The insertion rank correlation (Luss et al., 2021) and recall thatx (L) , ...,x (0) is the sequence of inputs with increasingly more important features inserted, starting from the empty stringx (L) to the full inputx (0) . This metric asserts that the model prediction on this sequence should increase monotonically to the original prediction. Also a higher correlation is desirable.

The Solvability of Evaluation Metrics
Now we establish the central observation of this paper: the solvability of these evaluation metrics. Observe that each evaluation metric, e.g. comprehensiveness κ, is defined on the input x and the explanation e, and its computation only uses the model prediction function f (or g derived from f for the two decision flip metrics). In addition, the form of feature attribution explanation constrains e to be a vector of the same length as x, or e ∈ R L .
Without loss of generality, we assume that the metrics are defined such that a higher value means a better explanation (e.g. redefining the sufficiency to be the negative of its original form). We formalize the concept of solvability as follows: Definition 3.1. For a metric m and an input x, an explanation e * solves the metric m if m(x, e * ) ≥ m(x, e) for all e ∈ R L . We also call e * the msolving explanation.
Notably, there are already two explanationsolving-metric cases among the ones in Sec. 2.
Theorem 1. The occlusion explainer solves the DF MIT and Rank Del metrics.
The proof follows from the definition of the explainer and the two metrics. Occlusion explainer defines token importance as the prediction change when each the token is individually removed, thus the most important token is the one that induces the largest change, which makes it most likely to flip the decision under DF MIT . In addition, because token importance is defined as the model prediction change, its rank correlation with the latter (i.e. Rank Del ) is maximal at 1.0.
Thm. 1 highlights an important question: if we take DF MIT or Rank Del as the metric (i.e. indicator) of explanation quality, why should we consider any other explanation, when the occlusion explanation provably achieves the optimum? A possible answer is that the metrics themselves are problematic. For example, one can argue that the DF MIT is too restrictive for overdetermined input: when redundant features (e.g. synonyms) are present, removing any individual one cannot change the prediction, such as for the sentiment classification input of "This movie is great, superb and beautiful." Nonetheless, the perceived quality of a metric can be loosely inferred from its adoption by the community, and the comprehensiveness and sufficiency metrics (DeYoung et al., 2020) are by far the most widely used. They overcome the issue of DF MIT by also considering inputs with more than one token removed. Since a metric value is scalar, we combine comprehensiveness κ and sufficiency σ into comp-suff difference ∆, defined as (recall that a lower sufficiency value is better): Again, we face the same question: if ∆ is solvable, why should any heuristic explainers be used instead of the ∆-solving e * ? In the next two sections, we seek to answer it by first proposing a beam search algorithm to (approximately) find e * and then explore its various properties.

Solving Metrics with Beam Search
We first define two properties -value agnosticity and additivity -satisfied by some metrics.
Definition 4.1. For an input x = (x 1 , ..., x L ) with explanation e = (e 1 , ..., e L ), we define the ranked importance as r( In other word, the x l with r(x l ) = L is the most important, and that with r(x l ) = 1 is the least. A metric m is value-agnostic if for all e 1 and e 2 that induce the same ranked importance, we have A value-agnostic metric has at most L! unique values across all possible explanations for an input of length L. Thus, in theory, an exhaustive search over the L! permutations of the list [1, 2, ..., L] is guaranteed to find the e * that solves the metric. h(x, e (l) ), for some function h, where e (l) reveals the attribution values of l most important features according to e but keeps the rest inaccessible.
Theorem 2. Comprehensiveness, sufficiency and their difference are value-agnostic and additive.
The proof is straightforward, by observing that bothx (l) and x (l) can be created from x and the ordering of e (l) . In fact, all metrics in Sec. 2 are value-agnostic (but only some are additive).
A metric satisfying these two properties admits an efficient beam search algorithm to approximately solve it. As e (l) can be considered as a partial explanation that only specifies the top-l important features, we start with e (0) , and attempt each feature to extend to obtain e (1) . With beam size B, if there are more than B features, we keep the top-B according to the partial sum. This extension procedure continues until all features are added, and top extension is then e * . Alg. 1 documents the procedure, where extend(e, v) creates a set of explanations in which each element has a value of v in a previously empty location of e.
Algorithm 1: Beam search for finding e * .
1 Input: beam size B, metric m, sentence x of length L; 2 Let e (0) be an empty length-L explanation; extend(e, L − l + 1); 6 beam ← choose_best(beam, B); 7 end 8 return choose_best(beam, 1); Without the additive property, beam search is not feasible due to the lack of partial metric values. However, Zhou et al. (2021) presented a simulated annealing algorithm (Kirkpatrick et al., 1983) to search for the optimal data acquisition order in active learning, and we can use a similar procedure to search for the optimal feature importance order. If the metric is value-sensitive, assuming that it is continuous and differentiable with respect to the explanation value, we can use techniques such as gradient descent to search for e * . Since we focus on comprehensiveness and sufficiency in this paper, the development and evaluation of these approaches are left to future work.

Experiments
We investigate various properties of the beam search explainer vs. existing heuristic explainers, using the publicly available textattack/roberta-base-SST-2 model on the SST dataset (Socher et al., 2013) as a case study. The sentiment value for each sentence is a number between 0 (very negative) and 1 (very positive), which we binarize into two classes of [0, 0.4] and [0.6, 1]. Sentences with sentiment values in middle are discarded. The average sentence length is 19, making the exhaustive search impossible. We use a beam size of 100 to search for ∆-solving explanation E * . All reported statistics are computed on the test set.

Qualitative Inspection
Fig. 2 presents two explanations, with additional ones in Fig. 6 of App. A. While we need more quan-titative analyses (carried out below) for definitive conclusions on its various properties, E * explanations at least looks reasonable and could plausibly help people understand the model.
A worthy tribute to a great humanitarian and her vibrant ' co-stars . ' So stupid , so ill-conceived , so badly drawn , it created whole new levels of ugly .

Performance on the Target Metric
We compare E * to heuristic explainers on the ∆ metric, with results shown in Tab. 1 along with the associated κ and σ. A random explanation baseline is included for reference. We can see that E * achieves the best ∆, often by a large margin. It also tops the ranking separately for κ and σ, which suggests that an explanation could be optimally comprehensive and sufficient at the same time. To get a visual understanding about how the model prediction changes during feature removal and insertion, we plot in Fig. 3 the values of f (x)− f (x (l) ) and f (x) − f ( x (l) ) (i.e. the summands in Eq. 1 and 2), as a function of l/L. The left panel shows the curves averaged across all test set instances, and the right panel shows those for a specific instance. κ and σ are thus the areas under the solid and dashed curves respectively. We can see that the curves for E * dominate the rest, and, on individual inputs, are also much smoother than those for other explanations.
Admittedly, beam search is slower than most other explainers, especially those that only require a single pass of the model such as the vanilla gradient. However, we note that explanations, unlike model predictions, are rarely used in real-time decision making. Instead, they are mostly used for debugging and auditing purposes, and incurring a  longer generation time to obtain a higher-quality explanation is often beneficial. On a single RTX3080 GPU card without any in-depth code optimization, the metric values and time costs for various beam sizes are presented in Tab. 2, with statistics for the best explainer LIME also listed for comparison.  We have two observations. First, the metric values increase with increasing beam size, but the improvement is meager after 10 beams. Second, even the greedy search with a single beam outperforms LIME by a decent margin, while being almost 10 times faster. Thus, these results establish that if we take comprehensiveness and sufficiency as the quality metrics, there is really no reason not to use beam search directly as the explainer.

Performance on Other Metrics
Sec. 2 lists many metrics that all operationalize the same principle that changing important features should have large impact on model prediction, but in different ways. A potential argument against the explicit beam search optimization is the fulfillment of the Goodhart's Law: E * overfits to the metric by exploiting its realization (i.e. Eq. 1 and 2) of this principle and not truly reflecting its "spirit." To establish the legitimacy of this opposition, we evaluate all the explainers on the remaining four metrics in Sec. 2, and present the results in Tab. 3.
Since the occlusion explainer solves DF MIT and Rank Del (Thm. 1), it ranks the best on these two metrics, as expected. Nonetheless, E * still ranks  competitively on these two metrics and comes out ahead on DF Frac . The only exception is Rank Ins , on which the random explanation surprisingly performs the best. We carefully analyze it in App. B and identify a fundamental flaw in it. Last, note that we can also incorporate any of these metrics into the objective function(which already contains two metrics: κ and σ), and search for E * that performs overall the best, if so desired. We leave this investigation to future work.

Explainer "Attacking" the Model
Another concern is that the search procedure may overfit to the model. Specifically, removing a word w in a partial sentencex (l) drastically changes the model prediction but does not have the same effect for most otherx (l ) . This makes E * assign w an overly high attribution, as w only happens to have a high impact in one particular case. By contrast, explainers like LIME and SHAP automatically avoid this issue by computing the average contribution of w on many different partial sentences.
We test this concern by locally perturbing the explanation. If E * uses many such "adversarial attacks," we should expect its metric values to degrade sharply under perturbation, as the highimportance words (according to E * ) will no longer be influential in different partial sentence contexts.
To perturb the explanation, we first convert the each explanation e to its ranked importance version e r using r(·) in Def. 4.1, which does not affect any metric as they are value-agnostic. Then we define the perturbed rank by adding to each entry of e r an independent Gaussian noise: e r = e r + n with n ∼ N (0, s 2 ). Thus, two words x i and x j with r(x i ) > r(x j ) have their ordering switched if the r(x i ) − r(x j ) < n(x j ) − n(x i ). A visualization of the switching with different s is in Fig. 7 of App. C. extents. Although E * degrades slightly faster than the rest on κ and DF Frac (and on par on others), it still achieves best results even at s = 4, with many order switchings (Fig. 7), and a faster degradation is reasonable anyway for metrics with better starting values (c.f. occlusion on Rank Del ). The evidence suggests that there is at most a slight model overfitting phenomenon, as E * remains comparable to other explainers under quite severe perturbation. Furthermore, we can incorporate perturbation robustness into metric solving to obtain an E * that degrade less, similar to adversarial training (Madry et al., 2018). We leave the exploration of this idea to future work.
App. D describes another assessment of model overfitting, though with a mild assumption and relying on word-level sentiment scores provided by the SST dataset. Similar conclusions are reached.

Ground Truth Recovery
For a model trained on a natural dataset, its ground truth working mechanism is rarely available -in fact, it could be argued that the very purpose of interpretability methods is to uncover it. Thus, a series of work (Adebayo et al., 2020;Bastings et al., 2021;Zhou et al., 2022a) proposed methods to modify the dataset such that a model trained on the new dataset has to follow a certain working mechanism to achieve high performance, which allows for evaluations against the known mechanism. Ground Truth Definitions We construct three types of ground truth features -short additions, long additions and replacements. First, we randomize the label to y ∼ Unif{0, 1} so that the original input features are no longer predictive, following the advice by Zhou et al. (2022a).
For the two addition types, a word or a sentence is inserted randomly to either the beginning or the end of the input. The inserted text is randomly chosen from the the corresponding set in Tab  is are (all punctuation marks) (period) (comma) We call these modifications symmetric since inputs corresponding to both y = 0 and y = 1 are modified. We also define the asymmetric modification, where only inputs with y = 1 are modified, and those with y = 0 are left unchanged. Metrics We use the two metrics proposed by Bastings et al. (2021): precision and normalized rank. First, we define the ground truth correlated words. For the two addition types, they are the inserted words. In the asymmetric case, instances with y = 0 does not have any words added, so we exclude them in metric value computation 1 . For the replacement type, they are the words that are in to the replacement set (but not necessarily replaced).
Let W be the set of ground truth correlated words. Using ranked importance r(·) in Def. 4.1, precision and normalized rank are defined as Precision is the fraction of ground truth words among the the top-|W | ranked words, and normalized rank is the lowest rank among ground truth words, normalized by the length L of the input. Both values are in [0, 1], and higher precision and lower normalized rank values are better.
Results Tab. 6 presents the average values across the test set. Many explainers including E * score perfectly on short additions, but all struggle on other types. Nonetheless, E * still ranks comparably or favorably to other methods. Its largest advantage happens on the asymmetric long addition, because this setup matches with the computation of κ and σ: E * searches for the most important words to remove/add to maximally change/preserve the original prediction, and those words are exactly the ground truth inserted ones. For replacement and symmetric addition, the search procedure does not "reconstruct" inputs of the other class, and hence optimizing ∆ fails to uncover the ground truth. This finding also suggests a mismatch between metric computation and certain ground truth types.
Conversely, vanilla gradient performs decently on ground truth types other than short addition, yet ranks at the bottom on most quality metrics (Tab. 1 and 3), again likely due to the mismatch.  Table 6: Average values of precision and normalized rank of the ground truth correlated words for each explainer.

Discussion
We now turn to the root cause of the solvability, its (un)desirability and circumvention.

Evaluations with Privileged Information
Compared to the evaluation of explanation, that of prediction (e.g. test set accuracy) is much more straightforward without the solvability loophole. The difference, as we point out, is the use of "privileged information" in the latter. Fig. 5 shows the workflow of evaluating prediction and explanation, making every dependency explicit. When evaluating model prediction, the evaluator runs the model on the input, receives the prediction, and compares it with the ground truth label, which is emphatically not available to the model under evaluation. By contrast, no such privileged information is used for evaluating model explanation, allowing the explainer to solve for the interpretability metric. Notably, prediction evaluation (e.g. accuracy) uses the ground truth label y not accessible to the model, but no such privileged information is used by the interpretability evaluation.
One way to avoid solvability is to introduce certain privileged information. In fact, this is exactly what the ground truth evaluation of Sec. 5.5 does: the ground truth correlated words are analogous to the ground truth labels in evaluating predictions, and are not available to the explainer, but it requires dataset modification and model retraining, and cannot evaluate models trained on datasets in the wild. Above all, however, the "real goal" of explanation should not be high metric values in the first place, but instead concrete instances of demonstrable utility, as discussed below. Demonstrable Utility Fundamentally, local explanations are means to an end -the end of a better understanding of the model (Zhou et al., 2022b;Zheng et al., 2022). Thus, we argue that a defini-tive evaluation should exhibit its demonstrable utility: the presence of explanation compared to its absence, or the newly proposed explanation compared to existing ones, should lead to a measurable difference in some practically beneficial aspect.
During model development, a major concern is that the model may pick up spurious correlations, and explanations are hoped to identify them, but such capability has been called into question recently (Zhou et al., 2022a;Adebayo et al., 2022).
Before model deployment, understanding the safety and reliability of models is crucial, especially for when models take physical actions in the world such as medication prescription. Jia et al. (2021) found that model explanations are promising but currently insufficient to achieve it.
For deployed models, Bansal et al. (2021) found that existing explanation methods rarely help a human decision maker assisted by a non-perfect model (e.g. in computer-aided diagnosis), but instead exacerbate the overtrust issue. Evidence for improved human performance is another demonstration of the concrete utilities of explanations.
Demonstrating that explanations help in such scenarios would bypass discussions of solvability and directly assert their usefulness. The three listed here are by no means comprehensive, and a systematic taxonomy is valuable. Furthermore, it is likely that no single explainer is a one-size-fit-all solution. More refined knowledge of the strengths and weaknesses of each method in supporting different aspects of model understanding is highly desirable.

Conclusion
We demonstrate that the many interpretability evaluation metrics are solvable, in that there is an explicit search procedure to find the explanation that achieves the optimal metric value. Given that these metrics are used to represent explanation quality, it is not clear why heuristic explainers such as LIME and SHAP are needed.
In this paper, we use a beam search to find the explanation E * that optimizes for comprehensiveness and sufficiency (DeYoung et al., 2020), and find E * performing comparably or favorably in all evaluations. Thus, we advocate for more investigations into this search-based paradigm and recommend future proposals of heuristic explainers to clearly establish the ways in which they are better than E * . We additionally discuss how to resolve the solvability issue and make evaluations more convincing and grounded in real-world setups.

Limitations
The focus of our paper is to investigate the search-based explanation that explicitly optimizes a target quality metric. While the results suggest that it is comparable or favorable to existing heuristic explainers on various technical aspects, its societal properties have not been studied. For example, Ghorbani et al. (2019) showed that many heuristic explanations can be easily manipulated and Slack et al. (2020) demonstrated that discriminative models can be carefully modified such that their discrimination is hidden by heuristic explanations. It is possible that same issues exist for the searchbased explanation, and thus we advise to carefully study them before deployment.
A Additional Qualitative Examples of the E * Explanation Fig. 6 presents more visualizations of E * explanations. These examples suggest that E * mostly focus on words that convey strong sentiments, which is a plausible working mechanism of a sentiment classifier.
A triumph , relentless and beautiful in its downbeat darkness .
Ranks among Willams ' best screen work .
Behind the snow games and lovable Siberian huskies ( plus one sheep dog ) , the picture hosts a parka-wrapped dose of heart .
... a haunting vision , with images that seem more like disturbing hallucinations .
Suffocated at conception by its Munchausen-by-proxy mum .
A dreadful live-action movie .
It 's an awfully derivative story .

B An Analysis on the Rank Ins Metric
As introduced in App. 2, this metric evaluates the monotonicity of the model prediction curve when more important features are successively inserted into an empty input. While this expectation seems reasonable, it suffers from a critical issue due to the convention in ranking features: if a feature contributes against the prediction, such as a word of sentiment opposite to the prediction (e.g. a positive prediction on "Other than the story plot being a bit boring, everything else is actually masterfully designed and executed."), it should have negative attribution and the convention is to put them lower in the rank (i.e. less important) than those have zero contributions. This implementation leads to the correct interpretation of all other metric values.
However, under this convention, the first few words added to the empty input should decrease the model prediction and then increase it, leading to a U-shaped curve. In fact, it is the comprehensiveness curve shown in Fig. 3, flipped both horizontally (because features are inserted rather than removed) and vertically (because the plotted quantity is the model prediction rather than change in prediction). Thus, a deeper U-shape should be preferred, but it is less monotonic. This also explains why the random attribution baseline achieves such a high ranking correlation: as we randomly add features from the empty string to the full input, on average the curve should be a more or less monotonic interpolation between model predictions on empty and full inputs, which has better monotonicity rank correlation than the U-shape.
It is not clear how to fix the metric. Previous works that proposed (Luss et al., 2021) or used (Chan et al., 2022) this metric often ignored the issue. One work (Arya et al., 2019) filtered out all features of negative attribution values and evaluate the rank correlation only on the rest. This, however, is easily manipulatable by an adversary. Specifically, an explainer could shift all attribution values down such that only the most positive one has a non-negative value. This change results in a perfect correlation as long as removing most positive feature induces a decrease in model prediction -an especially low requirement to satisfy. Empirically, we found that inserting features based on their (unsigned) magnitude barely affects the result either. Thus, we argue that this metric is not a good measurement of explanation quality.

D Another Assessment on the Explainer-Attacking-Model Behavior
We describe another experiment to assess whether the explanations exploit the adversarial vulnerability of the model. While it is possible that the model could use some shortcuts (Geirhos et al., 2020), we would expect it to predominantly use sentiment-conveying words, as it achieves high accuracy and no such shortcuts are known for the dataset. In this case, we should expect an explainer that do not adversarially exploit the model to give attributions for words correlated with their sentiment values, while an explainer that attacks the model would rate words that are "adversarial bugs" to be more important.
Conveniently, the SST dataset provides human annotations of the polarity score between 0 and 1 for each word, where 0 means very negative, 1 means very positive, and 0.5 means neutral. We compute the alignment between the attribution values (for the positive class) and this score for each word. Given a sentence x = (x 1 , ..., x L ) with explanation e = (e 1 , ..., e L ) and word polarity score s = (s 1 , ..., s L ), the alignment is defined as the Spearman rank correlation coefficient ρ(e, s). Since the vanilla gradient only produces non-negative values, it is impossible to identify whether a word contributes to or against the positive class, and we exclude it from the analysis. Fig. 8 plots the distribution of rank correlations among the test set instances, with the average shown as the bar and also annotated on the horizontal axis. Although no method achieves very high alignment, E * is the second-highest, after LIME. Thus, giving out assumption that high-polarity words are the indeed genuine signals used by the model for making predictions, we can conclude that E * does not adversarially exploit the model for its vulnerability more severely than the heuristic explainers.