TextGenSHAP: Scalable Post-hoc Explanations in Text Generation with Long Documents

lack of readability

We deeply apologize for how the lack of readability significantly detracted from the contributions made by the work. We have updated Section 3 to be much more friendly to readers without background knowledge in Shapley-based explanations and appreciate your specific feedback. In particular, we have decided to make explicit the distinction between $v_\ell$ and $v_p$, highlighting the log-probabilities earlier and more gradually motivating our contribution, among other changes.

No diagram or algorithm in the main text

We have updated the diagram for Figure 2 to focus on detailing the speculative decoding methodology we employ in our sampling algorithm. We hope that this can give much greater insights into how the speculative decoding works, but also give some basic insights into how our sampling algorithm proceeds. In particular, the algorithm proceeds by continuing to sample random subsets, compute the model output, and update the Shapley values. This can be continued until convergence, but for our work we stop after a fixed number of samples.

elaborate more on the “causal decoding tree”

Hopefully after the introduction of the new illustration in Figure 2, it is easier to understand how the `causal decoding tree’ works. Essentially, we are just constructed a data structure which holds on to all possible outputs we could want to generate (in a fashion similar to a trie) and are then also keeping track of all the necessary causal attention and position bias matrices needed to make this computation an exact copy of what would happen if we decoded autoregressively.

how closely do perturbed inputs need to resemble…

From this description, we can now say that: when we say that the “perturbed inputs resemble one another”, we mean that their generated outputs will be exactly the same. We mean resemblance in the sense that (compared to existing literature applying speculative decoding) our application in explainability will have a much much higher likelihood that two inputs generate the same output than in other possible applications.

introduction of several techniques

An important detail of the several techniques which we implement is that they are fortunately decoupled from one another. All of our other methods can be applied with or without Flash Attention and block sparsity. Hopefully after our Figure 2 and responses, the speculative decoding method is clearer to understand, and it can also be seen how it is independent from everything else. The in-place encoding is extremely simple to implement and FlashAttention is quickly becoming standard in a variety of machine learning packages. We moreover plan to release the code for our work which should even further facilitate the ease of implementation.

less pronounced on the MIRACL dataset

Here, we actually believe that this does not represent a shortcoming of our method as discussed briefly in the results section. As mentioned in the response to everyone, we have updated the appendix with specific MIRACL examples showing case scenarios where our method clearly answers correctly, but receives no AUC points because of the methodology used to construct the MIRACL dataset. In particular, the MIRACL dataset human annotators only annotate 10 labels, specifically the top ten retrieved by an existing retrieval system. Accordingly, our method’s ability to find a more diverse set of passages amongst extremely long contexts is not effectively captured by the “MIRACL (Original)” AUC metrics. To address this, we explore using psuedolabels for the MIRACL dataset, and in this scenario our method consistently outperforms the baseline, emphasizing the effectiveness of our approach.

performs with sampling techniques other than argmax

Assuming we are asked about the quantitative performance in terms of time, methods like K-beam will scale the memory linearly although the speculation aspect should not take any more time complexity. If the question refers to the qualitative performance in terms of how the explanations will change, as we make the distribution less sharp by increasing K, we will consequently make the explanations less sharp as well. We would be happy to try to answer further if you had a more specific interest.

We greatly appreciate your helpful and specific feedback and hope that these changes as well as our responses can help further clarify the contributions that we have made.

I would like to thank the authors for addressing my concerns, and for the updates made to the paper, in particular Figure 2.

I have read the other reviews, and while I still think there are parts of the paper that could be improved e.g. the algorithm is still deferred to the appendix (I understand the difficulties with space constraints but this is not ideal in my opinion), overall I am raising my score to vote for acceptance of this paper (from 5 to 6).

Notations are not fully explained and are hard to parse

First, we hope that the updated Section 3 will be easier to parse than the previous version, but we still answer your specific questions directly here. The input space of a masked text generation model defined as $\mathbb{R}^d \times \mathcal{P}([d])$, is now written as $[V]^d \times \\{0,1\\}^d$ which hopefully makes it clearer that ${x}\in \mathcal{X}=[V]^d$ represents the input sequence and ${s}\in\mathcal{M} = \\{ 0,1 \\}^d$ represents the binary input masks. $[\cdot]_+$ is now moved to be introduced right after it is used for the first and only time.

I do not understand why Eq (2) is better than Eq (1)

We have now further delineated Eq (1) and Eq (2) by forcing the different choice of $v_\ell(\cdot)$ and $v_p(\cdot)$ respectively. The major difference is as follows. It is computationally infeasible to compute the full probability vector over the exponentially large space $[0,1]^{[V]^m}$, so we will instead turn to greedy decoding or K-beam decoding. But using these algorithms will make the probability of generating certain outputs exactly zero, meaning we can no longer consider their log-probabilities and the entire Eq (1) becomes an ill-defined quantity. In contrast, Eq (2) can set some probabilities to zero without taking the logarithm, and the defined quantity is not only well-defined but should additionally be close to the Shapley-Shubik value as if we were to have the full exponentially-sized vector.

not always better than an extremely simple baseline (i.e., similarity score), especially on MIRACL

In the discussion of the results, we actually mention why we think this demonstrates the potential usefulness of our method, rather than a downside. Because the MIRACL dataset was constructed using the same similarity-score based approaches, there is a higher likelihood that a human annotator will give a positive label to the passages preferred by existing similarity-score approaches. We have further added Section E to show exactly what we mean by this on specific examples from the MIRACL corpus and give further motivation for the pseudo-label approach as a fair comparison of the different methods.

Lack of baselines

To the best of our knowledge, there are no existing feature attribution methods which can be directly applied to seq-to-seq text generation. The main category of explanations available for text-to-text generation are natural language explanations designed for end users. We are now trying to adapt existing feature attribution methods to enable comparison and are currently running experiments to try to compare AUC results. We hope to update you once they are completed.

output quality of LLMs usually highly depends on the instructions given to LLMs

identical tokens in the starting prompt … could have varying importance ratings

We apologize for the confusion regarding this. Indeed, our method can easily be applied to the instructions or prompt of the LLM. In our application, we are focusing on the explanations for the documents because it is meaningful for the QA task. For future work, as you mention, an important aspect of LLMs to focus on is understanding the prompt. For example, imagine an application where you are trying to design a good set of instructions. Maybe you have five different prompts and they are all giving the same performance. Using our method, you can see that prompt #1 is important for certain data samples while prompt #2 is important for other data samples. Here, we believe it is a feature and not a bug that the importance rating will change for different data samples. One can imagine that after seeing TextGenSHAP’s explanation, you will be able to design a new prompt which has the important parts of prompt #1 and the important parts of prompt #2, or perhaps a pipeline which automatically selects the correct prompt to be used for each specific example. (similar to how we automatically select the relevant documents in our application)

token-wise explanations … offer only superficial clarity

Although we agree that tokens are sometimes not readable words, we believe that the tokens are a critical ingredient to providing an accurate explanation. For example, the same English word can be tokenized in multiple different ways, and it is possible that the model prediction will change with different tokens, meaning our explanations should also change. If your major issue is with tokens being too small and unreadable words, we think you will appreciate our hierarchy we used going from paragraphs → sentences → words, which puts less emphasis on small unreadable tokens. We encourage you to check out our linked visualization.

TextGenSHAP claims to estimate Shapley Values.

We add some more detailed discussion on the Shapley value and typical approaches to the appendix, mentioning why this approximation is standard. For greater details on this approximation and for L1 and L2 errors on toy datasets one can refer to [1,2]. We emphasize that such L2 metrics can only be calculated on toy datasets since for real datasets it is computationally infeasible to get the exact value. Hopefully this can help explain why these sampling algorithms are standard in the first place.

Some annotations are not stated clearly

Hopefully our revamped notation and background section can alleviate these concerns. The ‘value function’ terminology is standard for the Shapley value, but now we have changed from the one-hot output generation to writing $v(\cdot)$ as a probability vector. We have also delineated the log-likelihood value function and the probability value function to make the distinction clearer.

T5 is limited to 512 tokens

The original T5 model was trained on 512 input tokens. First, it should be mentioned that because of the relative position biases, it is possible to run the T5 model on any sized input text. But moreover, the models which we used in our experiments are the T5-flan variants, which were trained on input contexts of 2048 tokens. The vast majority of our experiments are run on 2K-4K tokens. In any case, our major contributions also do not depend on a particular context length and can be applied regardless.

influenced by various samplings

Indeed various search strategies can affect the output generations. Although temperature scaling will have a trivial linear effect on the output generations, other methods like K-beam and top-P sampling will affect the support of the generated output, consequently influencing the final output distribution. We mention this briefly in Section 4.1, reiterating that our approach can easily be extended to handle any of these decoding methods, but we stick with greedy decoding which is standard for ODQA.

[1] “Explaining by Removing: A Unified Framework for Model Explanation”, 2021. Covert et al.

[2] “Sampling Permutations for Shapley Value Estimation”, 2022. Mitchell et al.

I appreciate the authors for their thorough and detailed responses to my questions. While some of my concerns have been addressed, there remain aspects that are still unclear to me.

• TextGenSHAP claims to estimate Shapley Values.

  • The purpose of this question is to assess the faithfulness of the generated importance values and to understand how users can benefit from the highlighted heatmap of words or sentences. From my perspective, the case studies presented offer limited evidence to substantiate the high quality of the generated explanations from the proposed framework. Empirical studies focusing on both word-level and sentence-level explanations are strongly recommended. Such investigations would significantly enhance the framework's persuasiveness instead of purely providing case studies.

  • If L2 metrics are not applicable in your scenario (possibly due to constraints from extended contexts), then considering the fidelity or faithfulness metric would be an excellent choice, as it effectively demonstrates the faithfulness of the explanations.

• T5 is limited to 512 tokens

  • Please provide the references or official documents of Flan-T5 that reveal Flan-T5 can handle up to 2048 context length. Please correct me if I am wrong. I did not find any comprehensive experiments or evidence in the original Flan-T5 paper that demonstrate its effectiveness with up to 2048 token contexts. Random case studies with few examples are not persuasive.
  • How do the paper manage input sizes of 2k-4k tokens to produce valid outputs in Flan-T5? Considering that such token counts exceed Flan-T5's context length capacity (regardless of the length constraint being 512 or 2048 tokens), this excess can lead to inferior performance and cause invalid output values from LLMs [1,2]. Notably, the estimation of Shapley value in this work is based on the calculation of output values from Flan-T5. When the context length is exceeded, the output values from the value functions of Flan-T5 may become unreliable and inferior, consequently diminishing the reliability of the generated importance scores, which means the generated important scores are calculated based on random and chaotic outputs from Flan-T5. If the paper truncates the input context before processing it through Flan-T5, the resulting explanations could be even less faithful and reliable. This approach may risk eliminating key features or words that are essential for accurate explanations.

[1] Press, Ofir, Noah A. Smith, and Mike Lewis. "Train short, test long: Attention with linear biases enables input length extrapolation." ICLR 2022.

[2] Chen, Shouyuan, et al. "Extending context window of large language models via positional interpolation." arXiv preprint arXiv:2306.15595 (2023).

I appreciate the authors' clarification and feedback, addressing some of my questions and concerns. However, I was not convinced by the statements from the authors to my follow-up questions. I will discuss these parts with other reviewers.

• Metrics:

  I think there may be some misunderstanding. Please refer to [1] for more introduction to fidelity and faithfulness metrics. From my understanding, fidelity or faithfulness metrics are precisely proposed for the situation when Shapley values or other explanation scores are not able to be calculated. Thus, fidelity and faithfulness metrics are applicable in the scenario of this paper. In my opinion, case studies are not convincing enough to prove the faithfulness of the generated explanation scores.

• Exceed context length:

  The consensus and observation from several advanced studies [2,3,4] are clear: LLMs are ineffective when inputs exceed their limited context length. The effective ways of solving this problem are neither the case I want to emphasize nor the case that this paper is focused on. I want to underscore the potential risks of directly using the value functions of LLMs, particularly in scenarios involving input lengths exceeding 2k tokens, as mentioned by the authors. The generated TextSHAP "values" may be severely impacted by LLMs' inferior and unreliable output value, leading to non-faithful explanation generation. Ensuring the faithfulness of generated Shapley-based "values" is the primary focus from my perspective.

[1] Liu, Yang, et al. "Synthetic benchmarks for scientific research in explainable machine learning." NeurIPS 2021.

[2] Press, Ofir, Noah A. Smith, and Mike Lewis. "Train short, test long: Attention with linear biases enables input length extrapolation." ICLR 2022.

[3] Chen, Shouyuan, et al. "Extending context window of large language models via positional interpolation." arXiv preprint arXiv:2306.15595 (2023).

[4] Xiao, Guangxuan, et al. "Efficient streaming language models with attention sinks." arXiv preprint arXiv:2309.17453 (2023).

In sum, despite not being completely convinced by the responses, the authors address some of my primary concerns, and I will increase my score accordingly. Please be sure to conclude the updated details in your latest draft, especially the misunderstanding on the context length limitation of Flan-T5.

What's the limitation of the proposed method?

It is first important to recognize that this work is seemingly the first work to yield feature-based explanations for a text-to-text generative model. Accordingly, we cannot directly compare its limitations to other currently available feature attribution methods. Nevertheless, the primary constraint of high-fidelity explanations like the Shapley value is usually their time complexity. Accordingly, a limitation of the current work is the need to further verify on a wider variety of models and tasks. In particular, multi-GPU and multi-TPU workbenches are left unexplored in the current work.

speculative decoding is not clear to me

We first emphasize that speculative decoding is an exact computation of the originally decoded likelihoods, but just decodes in a more efficient way. We have now clarified this in the text and updated Figure 2 to focus on explaining how the speculative decoding method gradually constructs a tree of possible outputs which can then all be computed in a single pass of the decoder (instead of needing multiple autoregressive passes when decoding one-by-one). We are happy to answer further details which are still unclear after our new figure.