Less is More: Efficient Black-box Attribution via Minimal Interpretable Subset Selection
Ruoyu Chen, Siyuan Liang, Jingzhi Li, Shiming Liu, Li Liu, Hua Zhang, Xiaochun Cao · 2025
Read Less is More: Efficient Black-box Attribution via Minimal Interpretable Subset Selection by Ruoyu Chen, Siyuan Liang, Jingzhi Li, Shiming Liu, Li Liu, Hua Zhang, Xiaochun Cao (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-2504-00470.txt.
Introduction
Ruoyu Chen and six co-authors proposed LiMA in twenty twenty-five, a method for explaining which parts of an input drive a model's decision. Attribution matters for trust, but with inputs like images the combinations of regions explode, making exact answers hopeless. They recast attribution as choosing an ordered, minimal set of interpretable sub-regions.
LiMA ranks regions by their marginal gain as subsets grow, allowing for redundancy, teamwork, and interference between regions. A combined score weighs semantic consistency, collaboration, confidence, and effectiveness. A two-way greedy search finds both the key regions and the dead weight quickly. Across eight foundation models and six data sets, LiMA gave more faithful explanations with fewer regions, improving standard scores by over a third and running faster than naive greedy search.
Catalog record
| CREATOR | Ruoyu Chen, Siyuan Liang, Jingzhi Li, Shiming Liu, Li Liu, Hua Zhang, Xiaochun Cao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 109 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-00470
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Less is More: Efficient Black-box Attribution via Minimal Interpretable Subset Selection Ruoyu Chen, Siyuan Liang, Jingzhi Li, Shiming Liu, Li Liu, Hua Zhang, Xiaochun Cao Abstract To develop a trustworthy AI system, it is essential to understand its behavior using attribution methods, which aim to identify the input regions that most influence the model’s decisions. For discrete inputs such as images, however, accurately identifying input–prediction interactions is particularly challenging because of combinatorial explosion. We formulate black-box attribution as an ordered interpretable subset-selection problem. Inspired by the marginal-gain principle of submodular optimization, the formulation permits redundancy, positive complementarity, and negative interference among input sub-regions. We propose LiMA ( Less input is More faithful for Attribution ), which ranks sub-regions by their contributions along a sequence of selected subsets. LiMA employs a composite objective that evaluates subsets through semantic consistency, collaboration, prediction confidence, and semantic effectiveness. We further design a bidirectional greedy search to efficiently identify important and non-critical sub-regions. Experiments on eight foundation models (CLIP, ImageBind, LanguageBind, QuiltNet, etc. ) and six datasets (ImageNet, VGG-Sound, CUB-200-2011, etc. ) demonstrate strong generalization and faithful interpretations with fewer sub-regions. LiMA achieves state-of-the-art Insertion, Deletion, and average highest confidence, with average improvements of 36.3% in Insertion and 39.6% in Deletion; it is also 1.6 times faster than naive greedy search. For failure attribution on incorrect predictions, LiMA improves average highest confidence by 86.1% over state-of-the-art methods. The code is available at https://github.com/RuoyuChen10/LIMA . I Introduction Explainable AI (XAI) techniques have gained significant attention for enabling the transparent and reliable deployment of trustworthy AI systems in real-world applications [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] , particularly in high-stakes domains such as healthcare [ 3 ] and autonomous driving [ 9 , 10 ] . The primary objective of XAI is to enhance our understanding of intelligent models, particularly by uncovering the relationships between predictions and input data [ 11 , 12 , 13 , 14 , 15 ] . To elucidate these associations, attribution-based methods [ 16 , 17 , 18 , 19 ] have been developed to interpret black-box deep neural networks by identifying the contribution of each input feature to the model’s predictions. In attribution evaluation, faithfulness refers to the extent to which the importance assigned to input regions is consistent with their actual influence on the model output. Accordingly, a faithful attribution should rank influential regions highly, such that progressively inserting these regions rapidly restores the corresponding model response, whereas removing them causes a pronounced decrease in that response [ 12 , 20 ] . However, faithful attribution for black-box AI systems remains an open problem. Several advanced attribution methods have been developed, including propagation-based [ 21 ] , gradient-based [ 22 , 23 , 24 , 25 ] , Shapley value-based [ 26 , 27 ] , and perturbation-based [ 20 , 12 ] mechanisms. The primary challenge in achieving perfect fidelity in attribution methods lies in accurately capturing the interactive relationships between inputs and predictions [ 28 , 29 ] . While existing attribution methods have yielded notable results, they still face several limitations that restrict their applicability in specific scenarios: 1) Computational efficiency, evaluating input-prediction interactions is a combinatorial explosion problem, making it challenging to achieve both efficient and faithful attribution. 2) Inaccurate contribution estimation, many attribution methods use sampling-based approximation strategies to estimate input contributions, which can lead to noisy attribution maps. 3) Region redundancy, when certain sub-regions are misattributed, either contributing less to, or even negatively affecting, the model’s response to the correct category. This issue becomes more pronounced in the case of erroneous predictions. Fig. 1: The left panel illustrates the Insertion and Average Highest Confidence metrics for various attribution mechanisms when attributing the model’s correct and incorrect predictions. Our method shows significant improvements across different datasets and models. The right panel shows the attribution maps of different methods, where our approach avoids noise and unnecessary region redundancy. The core of the attribution problem is to determine the importance of individual sub-regions and identify the subset of sub-regions that has the most significant impact on the final decision. Inspired by submodular optimization [ 30 ] , which evaluates candidate elements through their marginal gains to a selected subset, we seek to enhance model interpretability by selecting and ordering fewer sub-regions. However, attribution objectives induced by modern neural networks need not satisfy the classical diminishing-returns assumption. Redundant sub-regions may exhibit overlapping utility, whereas complementary sub-regions may produce positive synergy, such that their joint response is greater than the sum of their individual responses. Background or distractor sub-regions may also produce negative marginal gains. We therefore formulate attribution as an ordered subset-selection problem and use submodular optimization as a design inspiration for marginal-gain-based search, without assuming that the resulting attribution objective is globally submodular or monotone. Fig. 1 shows the attribution results of several popular methods across different models and images, highlighting issues such as background noise and region redundancy. In this paper, we propose LiMA ( Less input is More faithful for Attribution ), a novel and efficient black-box attribution mechanism based on ordered interpretable subset selection. LiMA first sparsifies an input into a limited set of fine-grained sub-regions using a semantic- or patch-based division method. It then uses a composite objective function to evaluate candidate subsets from four complementary perspectives: semantic consistency, collective effect, prediction confidence, and semantic effectiveness. A bidirectional greedy search algorithm simultaneously identifies important and non-critical sub-regions, producing an ordered sequence whose prefixes provide explanations at different region budgets. Extensive experiments on eight foundation models (CLIP [ 31 ] , ImageBind [ 32 ] , LanguageBind [ 33 ] , QuiltNet [ 34 ] , etc. ) and six datasets (ImageNet [ 35 ] , VGG-Sound [ 36 ] , CUB-200-2011 [ 37 ] , Celeb-A [ 38 ] , VGG-Face2 [ 39 ] , and LC25000 [ 40 ] ) demonstrate that our method achieves state-of-the-art attribution faithfulness evaluation metrics (Insertion, Deletion, and average highest confidence) with fewer regions and exhibits strong generalization, shows an average improvement of 36.3% in Insertion and 39.6% in Deletion. As shown in the radar chart in Fig. 1 , compared to the most advanced attribution methods, our approach shows an average improvement of 36.3% in Insertion. For failure attribution on incorrect predictions, the average highest confidence achieved by our method is, on average, 86.1% higher than that of state-of-the-art attribution algorithms. Furthermore, our attribution efficiency is 1.6 times greater than that of the naive greedy search. Our contributions can be summarized as follows: • We formulate black-box attribution as an ordered interpretable subset-selection problem inspired by the marginal-gain-based search principle of submodular optimization, while allowing both complementary and interfering interactions among sub-regions. • We introduce a composite objective function to evaluate subset importance and a bidirectional greedy search algorithm that balances attribution efficiency and empirical faithfulness. • Our analysis shows that as the pre-training scale and model parameters increase, or when models make incorrect predictions, the interaction between input elements becomes more complex, which makes accurate attribution more challenging. • The proposed method demonstrates strong faithfulness across various models and datasets. It provides faithful attribution