Less is More: Efficient Black-box Attribution via Minimal Interpretable Subset Selection

arXiv:2504.00470v3 Announce Type: replace 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.