Context Attribution with Multi-Armed Bandit Optimization
Deng Pan, Keerthiram Murugesan, Nuno Moniz, Nitesh Chawla · 2025
Read Context Attribution with Multi-Armed Bandit Optimization by Deng Pan, Keerthiram Murugesan, Nuno Moniz, Nitesh Chawla (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-19977.txt.
Introduction
Deng Pan and co-authors find which context parts drive a chat answer by bandit search in a 2025 paper. Search fed models cite long contexts, but which parts matter is murky. Clear credit matters for trust in such systems.
Their frame casts credit hunting as a multi armed bandit game. A linear Thompson sampling arm picks context subsets to test. Reward reads how well a subset backs the answer's odds. Smart picks beat the uniform sampling of past perturbation tools. Query counts fell by up to thirty percent at matched quality. The method fits both open and closed API models.
Catalog record
| CREATOR | Deng Pan, Keerthiram Murugesan, Nuno Moniz, Nitesh Chawla |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-19977
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Context Attribution with Multi-Armed Bandit Optimization Deng Pan, Keerthiram Murugesan, Nuno Moniz, Nitesh Chawla Abstract Understanding which parts of the retrieved context contribute to a large language model’s generated answer is essential for building interpretable and trustworthy generative QA systems. We propose a novel framework that formulates context attribution as a combinatorial multi-armed bandit (CMAB) problem. Each context segment is treated as a bandit arm, and we employ Combinatorial Thompson Sampling (CTS) to efficiently explore the exponentially large space of context subsets under a limited query budget. Our method defines a reward function based on normalized token likelihoods, capturing how well a subset of segments supports the original model response. Unlike traditional perturbation-based attribution methods (e.g., SHAP), which sample subsets uniformly and incur high computational costs, our approach adaptively balances exploration and exploitation by leveraging posterior estimates of segment relevance. This leads to substantially improved query efficiency while maintaining high attribution fidelity. Extensive experiments on diverse datasets and LLMs demonstrate that our method achieves competitive attribution quality with fewer model queries. 1 Introduction Retrieval-Augmented Generation (RAG) has emerged as the de facto method for knowledge-intensive question answering tasks, augmenting Large Language Models (LLMs) with external context to improve factual accuracy and credibility Gao et al. 2023b . Despite its effectiveness, ensuring that generated answers are genuinely grounded in the provided context remains challenging. LLMs frequently produce hallucinations or incorporate ungrounded information, making it essential to verify and attribute precisely which context segments are responsible for their responses Gao et al. 2023a . Existing approaches to enhancing attribution primarily follow two paradigms. The first involves training models to explicitly cite context segments during generation Nakano et al. 2021 ; Menick et al. 2022 ; Zhang et al. 2024 ; Huang et al. 2024 . While such techniques improve self-attribution, their reliability is contingent on the model’s internal mechanisms. The second paradigm focuses on post-hoc methods, such as ContextCite Cohen-Wang et al. 2024 , which systematically perturb or mask context segments and evaluate their impact on the output. Although these methods offer greater fidelity by probing the actual input-output behavior of models, they often incur prohibitive computational costs as they incorporate subroutines like LIME Ribeiro et al. 2016 and SHAP Lundberg and Lee 2017 , which rely on extensive sampling and surrogate modeling, can become impractical for real-world, long-context scenarios due to their high query overhead. Motivated by the need for a more efficient yet faithful attribution method, we propose framing context attribution as a Combinatorial Multi-Armed Bandit (CMAB) problem. This perspective treats each context segment as a "bandit arm" whose inclusion or exclusion in the context constitutes a combinatorial action, aiming to identify the subset that best supports the generated answer within a limited query budget. Specifically, we define a reward function based on token-level likelihoods, measuring how closely a given subset of context preserves the model’s original output distribution. The problem thus becomes selecting the context subset that maximizes this reward with minimal exploration. To efficiently navigate this combinatorial space, we introduce Combinatorial Thompson Sampling (CTS), a Bayesian bandit method renowned for balancing exploration and exploitation Wang and Chen 2018 . CTS maintains and updates posterior beliefs about each segment’s utility, adaptively guiding queries toward subsets most likely to yield informative outcomes. Unlike exhaustive or uniformly random perturbation strategies, CTS significantly reduces the number of model evaluations required, making it especially suited for long-context applications and scenarios demanding interpretability alongside computational efficiency. Our key contributions are summarized as follows: • New Problem Formulation: We introduce a novel formulation of segment-level context attribution as a combinatorial multi-armed bandit (CMAB) problem. • Combinatorial Thompson Sampling for Attribution: We propose a Combinatorial Thompson Sampling (CTS) algorithm specifically designed for efficient context attribution. By maintaining posterior estimates over segment importance, CTS adaptively selects informative context subsets under tight query budgets. • Extensive Empirical Validation: We conduct comprehensive experiments on two diverse datasets—SST2 Socher et al. 2013 and HotpotQA Yang et al. 2018 —using two open-source LLMs, LLaMA3-8B Grattafiori et al. 2024 and SmolLM-1.7B Allal et al. 2024 . Results show that CAMAB consistently delivers competitive or superior attribution performance while requiring significantly fewer model queries than existing baselines. In summary, our approach offers a scalable, principled, and computationally efficient method for context attribution in generative QA systems. Through extensive empirical evaluations, we demonstrate that our CMAB-based framework achieves attribution fidelity comparable to or exceeding state-of-the-art methods, all while drastically reducing the computational demands inherent in traditional perturbation-based techniques. We believe our work represents a significant step towards more interpretable and trustworthy AI assistants, particularly crucial as applications scale to increasingly complex contexts and high-stakes environments. 2 Related Work 2.1 Perturbation-Based Attribution Methods A large number of works on model interpretability uses input perturbations to infer feature importance. Techniques like LIME Ribeiro et al. 2016 and SHAP Lundberg and Lee 2017 interpret model predictions by evaluating the model on perturbations of an input and observing how the output changes. LIME fits a local surrogate model (e.g. a linear model) around the neighborhood of the input to estimate each feature’s influence. SHAP uses a game-theoretic approach to approximate Shapley values, which quantify each feature’s contribution to the prediction in a way that satisfies fairness axioms. These methods are model-agnostic and fairly faithful in a local sense, but they are notoriously expensive: they require sampling a large number of perturbations for each instance to obtain stable estimates. This cost grows with input dimensionality, making them difficult to apply to settings like long text sequences without sparing accuracy. 2.2 Attribution Methods in LLM Settings In the context of large language models (LLMs), token-level attribution faces significant challenges due to (1) the combinatorially large perturbation space induced by extensive input contexts, and (2) substantial computational costs associated with individual model queries. Therefore, effective attribution methods must carefully balance explanation fidelity against computational efficiency. Broadly, three strategies have emerged to tackle these challenges: (i) Reducing Perturbation Space : Methods in this category aggregate tokens into higher-level semantic units, such as phrases, sentences, or paragraphs, effectively decreasing the perturbation space. Different granularity levels inherently capture varying degrees of semantic meaning, naturally supporting hierarchical attribution structures. For example, Chen et al. 2020 propose a divide-and-conquer strategy that progressively attributes importance from sentence-level down to token-level in text classification. Similarly, MExGen Paes et al. 2024 systematically extends perturbation-based methods like LIME and SHAP to generative LLMs, efficiently identifying influential text spans in a hierarchical manner. ContextCite Cohen-Wang et al. 2024 specifically targets segment-level attribution in generative QA scenarios by using SHAP-based perturbation techniques. (ii) Pretrained Global Explainers : Another strategy involves training a global surrogate model as a pretrained explainer, trading upfront training costs for reduced inference latency during explanations. Examples include FEX Pan et al. 2025 , which employs policy gradient methods to optimize a Bernoulli surrogate explainer, and FastSHAP Jethani et al. 2021 , which fits a neural network using pseudo-labels derived from SHAP values. Despite their inference efficiency, these methods demand substantial pretraining resources and extensive datasets, and like typical machine learning models, they often encounter generalization challenges when confronted with out-of-distribution samples. (iii) Optimizing Perturbation Strategies : A relatively nascent direction focuses on explicitly optimizing perturbation strategies to reduce