T ext G en SHAP : Scalable Post-Hoc Explanations in Text Generation with Long Documents (2024)

Abstract: Large language models (LLMs) have attracted great interest in many real-world applications; however, their “black-box” nature necessitates scalable and faithful explanations. Shapley values have matured as an explainability method for deep learning, but extending them to LLMs is difficult due to long input contexts and autoregressive output generation. We introduce , an efficient post-hoc explanation method incorporating LLM-specific techniques, which leads to significant runtime improvements: token-level explanations in minutes not hours, and document-level explanations within seconds. We demonstrate how such explanations can improve end-to-end performance of retrieval augmented generation by localizing important words within long documents and reranking passages collected by retrieval systems. On various open-domain question answering benchmarks, we show TextGenSHAP improves the retrieval recall and prediction accuracy significantly.

## introduction large language models (llms) continue to rapidly excel at different text-generation tasks alongside the continued growth of resources dedicated to training text-based models @xcite @xcite ). llm's impressive capabilities have led to their widespread adoption throughout academic and commercial applications. their capacity to reason cohesively on a wide range of natural language processing (nlp) tasks has motivated further efforts to enable a single model to automatically ingest increasingly large contexts. these long-context models have been shown to improve zero-shot, few-shot, and retrieval-augmented performance via in-context learning @xcite ; huang * enouen@usc.edu @xcite and to reduce the need for training task-specific models, empowering non-experts to readily use llms. despite their remarkable text generation capabilities, llms which are trained to model statistical correlations in language can offer only limited insight into their internal mechanisms. accordingly, llms are widely considered black-box models which are incredibly difficult to explain and understand. in the wake of widespread adoption amongst the general population, challenges beyond llm prediction performance including safety, security, and truthfulness have gained increasing prominence. growing reports of hallucinated material, harmful counseling, prejudiced content, and other real-world consequences continue to raise concerns. often, explainability is hailed as a crucial avenue for addressing these concerns, enabling insights into the model's decision-making process and allowing stakeholders to directly scrutinize the reasoning behind unsafe or untruthful responses. recent surveys in explainability for nlp juxtapose the two main criteria for model explanations: understandability and faithfulness @xcite @xcite . understandability refers to how easily an explanation is understood by a human user, whereas faithfulness measures how accurately it reflects the model's reasoning process. effectively balancing these objectives for a given explanation technique remains an ongoing challenge @xcite . popular explanation approaches like attention scores, gradient saliency, and self-explained reasoning are generally considered to be understandable; however, ongoing debates question whether these approaches also provide high-fidelity explanations @xcite @xcite @xcite . for tabular and image data, the shapley value (lundberg and @xcite stands out due to its strong theoretical foundations, grounded in the gorgeously elaborate continuation of "the lord of the rings" trilogy is so huge that a column of words can not adequately describe co-writer/director peter jackson's expanded vision of j.r.r. tolkien's middle-earth. axioms guaranteeing: symmetry, efficiency, nullity, and linearity @xcite . in the nlp domain, however, faithful approaches like the shapley value suffer greatly in their ability to scale to larger models and longer inputs, leading to impractically long wait times for explanations in llm workflows. to address the limitations of current explainability methods in the realm of nlp, we introduce textgenshap, a novel approach to extend shapley values for text generation while keeping a computational speed more suitable for real-world llm use cases. we focus on explanations in the challenging scenario of open-ended text generation using long inputs as prompts, specifically focusing on the task of abstractive question answering from retrieval-augmented documents. we leverage wellfounded historical works in game theory to support our new shapley score's definition, and then develop an efficient algorithm designed specifically for transformer models. accordingly, we demonstrate our method's scalability to new applications across three key aspects shown in fig. 1 : (a) handling longer contexts with thousands of input tokens using the hierarchical structure of natural text; (b) accommodating larger models with billions of parameters using hardware-aware speedups; and (c) explaining free-form text generation, instead of only discriminative tasks like classification (which were the focus of previous work.) furthermore, we demonstrate how the explanations generated by our textgenshap can enhance the performance of open-domain question answer-ing on both miracl and nq-open, enhancing the recall of document retrieval systems by multiple points and closing the accuracy gap of opendomain question answering with a 5-10% point improvement. ## explainability framework notation. consider an llm using a vocabulary of size @xmath0:= [v ] d and output sequences @xmath1:= [v ] m with input length @xmath2, where [v ] := {1, . . . , v }. broadly, a textgeneration model takes an input sequence of tokens and defines a probability vector over all possible outputs, f : @xmath3, 1] y . hence, we have f (x) y denote y's probability of being generated given x. to enable explanation via feature attribution methods like the shapley value, we need to be able to mask certain subsets of the input tokens. let @xmath4:= {0, 1} d be a binary mask on the input tokens. we next define a masked text-generation model, f : x × @xmath5, 1] y , which takes both an input sequence and an input mask. in practice, we replace all input tokens which are not in the mask s by @xmath6. if we assume @xmath7, then we can write this as f (x, s) := f (x s + p (1s)). ## textgenshap: faster explanations input hierarchy we leverage the hierarchical structure within natural text to also reduce the time complexity required for model explanation, following the theoretical foundations of the owen-winter value. we first break each long input document into its passages and measure the shapley value of each passage, allowing us to select only those passages more important than some threshold to continue on to the sentence level and then word level. 2 in our experiments, we consider thresholds of both 10% and 30% for the required importance for both paragraph and sentence level. this enables us to not waste computational effort on tokens which do not warrant further investigation. a full description is available in algorithm 1. speculative decoding another major improvement in explanation speed is gained through utilizing speculative decoding similar to what was recently explored in @xcite ; @xcite . speculative decoding, similar to branch prediction in computer architectures, uses one or multiple guesses of the generated output sequence to reduce the time taken up by repeatedly applying the decoder model. since mistakes are corrected by reapplying the decoder model, exact output probabilities are ultimately calculated, but speed is only enhanced when guessing correctly. fig. 3 depicts our speculative decoding approach which is tailored to the explainability application. existing approaches can only speculate 2-10 tokens ahead and face relatively high error rates; however, our approach speculates the entire output sequence with lower error rates. while existing methods are designed for model inference which only gets 'one guess' at the full generated output, our application is perturbation-based resampling methods like the shapley value. this means many of our generated outputs will be similar and allows us to gradually construct a bank of speculative outputs (using a tree structure) due to the redundancies of generating similar outputs. in our experiments, we verify that a large amount of total computation can be saved by speculatively decoding full outputs rather than sequentially running the decoder model. specifically, for each new sample (mask) coming from the shapley distribution, we first verify (fig. 3b ) whether the argmax decoding exists or not within our speculative decoding calculation (if so we are already done with this sample). if not, then we need to generate the new candidate answer using autoregressive decoding. afterwards, we graft the new answer to the existing causal decoding tree so we can generate this response in the future, making sure to update the causal attention matrix in order to respect the graph structure of the decoding tree (fig. 3d ). in all experiments, we use greedy decoding consistent with prior work on open-domain qa @xcite . however, we emphasize that the speculative decoding tree can further support other popular sampling methods like beam search and nucleus generation (top-k and top-p) @xcite . ## architecture-specific accelerations in this section, we include further details about the architectural implementations which we used to achieve the best wall-clock performance. the first section is about the widely adopted flash attention @xcite which is used for all experiments within this paper and is what allowed for tens of thousands of tokens to be run on a single gpu. the second and third sections are additional tricks specific for the t5-fid architecture, focusing on efficiency under the massive context sizes pursued by the long-document and open-domain communities. flash attention to better address the challenges for long inputs, especially with limited compute resources, we follow recent adoptions of the flash attention mechanism @xcite to improve both the memory efficiency and the runtime performance of lms. such approaches compute the attention matrix with the memory requirement scaling linearly with input size o(n ) instead of quadratically o(n 2 ) @xcite . ## experimental results datasets we focus on publicly-available datasets for the task of open-domain or long-document question answering: natural questions (nq) @xcite and miracl (english subset) @xcite . we follow nq as redesigned for open-domain question answering following @xcite called nq-open. in this setting, answers must be found from within all of wikipedia, rather than a single wikipedia page. the original nq dataset provides short text answers and passages are rated as relevant so long as they contain the ground-truth answer. miracl is instead designed for information retrieval and for each query it provides binary relevance ground-truth for the ten most related passages in the corpus. 3 models for passage ranking of the corpus (retriever model) we use the recent contriever (izacard et al., 2022a) architecture following litm. for question answering (reader models) we use different members of the t5 family @xcite . we use the available flan tuned models at the large and xxl sizes ('t5-large' and 't5-xxl') @xcite and the fine-tuned t5 large model from fid ('t5-fid') @xcite . ## conclusion in this paper, we introduce textgenshap for enhancing the shapley value, a trusted explainability method, to address the challenges in modern nlp applications featuring long inputs, large model sizes, and text generation. we introduce modifica-tions to adapt the shapley value for hierarchicallystructured input text and autoregressively-decoded output generations, drawing on insights from the game theory literature to support their theoretical motivations. additionally, we incorporate multiple transformer-specific architecture modifications which significantly accelerate explanation generation. our approach not only speeds up shapley value computation for generated text but also demonstrates its effectiveness in improving performance at challenging question-answering tasks. we expect that such explanation methods will continue to find broad applicability in a variety of llm use cases.