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

cs.LGApr 1, 2025

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

Authors: Ruoyu Chen, Siyuan Liang, Jingzhi Li, Shiming Liu, Li Liu, Hua Zhang, Xiaochun Cao

Organizations: Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China · University of Chinese Academy of Sciences, Beijing 100049, China · College of Computing and Data Science, Nanyang Technological University, 639798, Singapore · School of Artificial Intelligence, University of Science and Technology Beijing, Beijing 100083, China ·

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.

Figures & tables

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.

Fig. 2: The framework of the proposed LiMA method. We first divide the input into interpretable sub-regions using a superpixel- or semantic-based strategy. A composite objective and bidirectional greedy search then identify important and non-critical sub-regions and arrange them into an ordered sequence. Finally, consistency- and collaboration-based marginal changes are used to assign attribution scores. The resulting prefixes provide explanations at different region budgets and are evaluated using faithfulness metrics.

Fig. 3: Statistics of large response transitions along the insertion trajectory. A. Results for models with different pre-training scales and sizes. B. Results for correctly and incorrectly predicted samples.

Methods	CLIP (ViT-L) [ 31 ]					ImageBind (Huge) [ 32 ]					LanguageBind (Large) [ 33 ]
Methods	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	$\mu$ Fid. ( $\uparrow$ )	F/B	Time	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	$\mu$ Fid. ( $\uparrow$ )	F/B	Time	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	$\mu$ Fid. ( $\uparrow$ )	F/B	Time
Saliency [ 41 ]	0.3040	0.1938	0.1010	1/1	$0.095{\pm}0.002$	0.3857	0.3473	0.1807	1/1	$0.127{\pm}0.002$	0.2237	0.2379	0.2395	1/1	$0.402{\pm}0.002$
Integrated Gradients [ 22 ]	0.1600	0.3560	0.0881	80/80	$1.498{\pm}0.929$	0.1405	0.5577	0.1919	80/80	$5.059{\pm}0.033$	0.0699	0.2733	0.1422	80/80	$29.11{\pm}0.63$
iGOS++ [ 24 ]	0.2934	0.4467	0.2313	16,426.7/1,600	$85.48{\pm}11.13$	0.2658	0.4417	0.2371	17,253.3/1,600	$447.3{\pm}22.6$	–	–	–	–	–
RISE [ 20 ]	0.1615	0.5345	0.3244	500/0	$2.041{\pm}0.102$	0.1528	0.4699	0.3459	500/0	$11.23{\pm}0.10$	0.1145	0.4750	0.2764	500/0	$67.49{\pm}0.44$
HSIC-Attribution [ 12 ]	0.1565	0.4397	0.3232	500/0	$2.454{\pm}0.746$	0.1875	0.4407	0.3413	500/0	$11.46{\pm}0.04$	0.1034	0.4070	0.4132	500/0	$68.25{\pm}0.12$

TABLE I: Faithfulness, absolute query counts, and wall-clock time for multimodal ViT backbone foundation models on ImageNet. F/B denotes forward queries/backward passes; time is mean

\pm

sample standard deviation in seconds.

Fig. 4: Visual explanations of the CLIP model using various attribution mechanisms, with our approach effectively reducing noise and eliminating redundant regions, leading to more interpretable attribution results.

Fig. 5: Attribution visualizations of decision results for different multimodal foundation models on the ImageNet dataset. The first row shows the interpretation results from the state-of-the-art baseline attribution methods, while the second row displays the interpretation results from our method. Each interpretation result includes the saliency map, the highest confidence score, and its corresponding region, as well as the Insertion AUC curve. The red line in the curve represents the highest confidence of the model’s response during the search.

Methods	CLIP (ResNet-101) [ 31 ]
Methods	Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )	$\mu$ Fidelity ( $\uparrow$ )	F/B	Time
Saliency [ 41 ]	0.0801	0.1540	0.3648	1/1	$0.084{\pm}0.005$
Integrated Gradients [ 22 ]	0.0482	0.0804	0.1141	80/80	$0.588{\pm}0.212$
Kernel SHAP [ 26 ]	0.1198	0.1766	0.0923	1,000/0	$2.454{\pm}0.342$
RISE [ 20 ]	0.0719	0.4034	0.3355	500/0	$0.744{\pm}0.011$
HSIC-Attribution [ 12 ]	0.0659	0.3574	0.4373	500/0	$0.831{\pm}0.021$

TABLE II: Faithfulness, absolute query counts, and wall-clock time for CLIP with a ResNet-101 backbone on ImageNet.

Methods	ResNet-101 [ 78 ]
Methods	Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )	$\mu$ Fidelity ( $\uparrow$ )	F/B	Time
Saliency [ 41 ]	0.1148	0.2613	0.4556	1/1	$0.087{\pm}0.004$
Integrated Gradients [ 22 ]	0.0521	0.1482	0.1822	80/80	$0.602{\pm}0.056$
iGOS++ [ 24 ]	0.1934	0.3779	0.3377	14,346.7/1,600	$19.96{\pm}0.37$
Kernel SHAP [ 26 ]	0.1944	0.2878	0.1399	1,000/0	$2.212{\pm}0.271$
RISE [ 20 ]	0.1101	0.4920	0.3827	500/0	$0.839{\pm}0.042$

TABLE III: Faithfulness, absolute query counts, and wall-clock time for the single-modal ResNet-101 backbone on ImageNet.

Methods	ViT-L [ 79 ]				Swin-L [ 80 ]
Methods	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	F/B	Time	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	F/B	Time
Saliency [ 41 ]	0.3499	0.3544	1/1	$0.096{\pm}0.002$	0.2888	0.4178	1/1	$0.213{\pm}0.088$
Integrated Gradients [ 22 ]	0.1530	0.2402	80/80	$2.029{\pm}0.015$	0.3074	0.4198	80/80	$1.506{\pm}0.032$
Kernel SHAP [ 26 ]	0.4155	0.4942	1,000/0	$9.250{\pm}0.191$	0.4300	0.4794	1,000/0	$6.788{\pm}0.110$
RISE [ 20 ]	0.1947	0.6177	500/0	$4.335{\pm}0.052$	0.3338	0.5655	500/0	$3.273{\pm}0.030$
HSIC-Attribution [ 12 ]	0.1898	0.5253	500/0	$4.423{\pm}0.022$	0.3589	0.5531	500/0	$3.377{\pm}0.043$

TABLE IV: Faithfulness, absolute query counts, and wall-clock time for single-modal vision transformer backbones on ImageNet.

Methods	Vision Mamba (base) [ 81 ]				MambaVision (L2) [ 82 ]
Methods	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	F/B	Time	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	F/B	Time
Saliency [ 41 ]	0.2793	0.1938	1/1	$0.127{\pm}0.009$	0.1681	0.1494	1/1	$0.099{\pm}0.005$
Integrated Gradients [ 22 ]	0.0914	0.2323	80/80	$1.319{\pm}0.022$	0.1067	0.2202	80/80	$1.236{\pm}0.015$
Kernel SHAP [ 26 ]	0.2947	0.3603	1,000/0	$5.878{\pm}0.351$	0.2030	0.2345	1,000/0	$5.827{\pm}0.149$
RISE [ 20 ]	0.2008	0.5352	500/0	$2.789{\pm}0.425$	0.1419	0.2937	500/0	$2.511{\pm}0.027$
HSIC-Attribution [ 12 ]	0.2067	0.4872	500/0	$2.854{\pm}0.361$	0.1541	0.2753	500/0	$2.725{\pm}0.048$

TABLE V: Faithfulness, absolute query counts, and wall-clock time for single-modal Mamba backbones on ImageNet.

	Celeb-A (ArcFace ResNet-101)			VGGFace2 (ArcFace ResNet-101)
Methods	Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )	$\mu$ Fidelity ( $\uparrow$ )	Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )	$\mu$ Fidelity ( $\uparrow$ )
Saliency [ 41 ]	0.1453	0.4632	0.3258	0.1907	0.5612	0.5034
Grad-CAM [ 23 ]	0.2865	0.3721	0.0672	0.3103	0.4733	0.2773
Integrated Gradients [ 22 ]	0.0680	0.3578	0.3352	0.0749	0.5399	0.3853
LIME [ 49 ]	0.1484	0.5246	0.1985	0.2034	0.6185	0.4856
Kernel SHAP [ 26 ]	0.1409	0.5246	0.2722	0.2119	0.6132	0.4905

TABLE VI: Deletion, Insertion AUC scores, and

\mu

Fidelity on the Celeb-A and VGG-Face2 validation sets.

	CUB-200-2011
Methods	Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )	$\mu$ Fidelity ( $\uparrow$ )
Saliency [ 41 ]	0.0682	0.6585	0.1409
Grad-CAM [ 23 ]	0.0810	0.7224	0.1486
Integrated Gradients [ 22 ]	0.1693	0.5263	0.2832
LIME [ 49 ]	0.1070	0.6812	0.0948
Kernel SHAP [ 26 ]	0.1016	0.6763	0.1452

TABLE VII: Deletion, Insertion AUC scores, and

\mu

Fidelity on the CUB-200-2011 validation set.

Methods	ImageBind [ 32 ]				LanguageBind [ 33 ]
Methods	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	F/B	Time	Del. ( $\downarrow$ )	Ins. ( $\uparrow$ )	F/B	Time
Saliency [ 41 ]	0.0999	0.1823	1/1	$0.089{\pm}0.001$	0.1024	0.2184	1/1	$0.136{\pm}0.005$
Gradient-Input [ 89 ]	0.0326	0.1257	1/1	$0.079{\pm}0.003$	0.0243	0.1388	1/1	$0.134{\pm}0.004$
SmoothGrad [ 90 ]	0.0734	0.0955	80/80	$2.549{\pm}0.167$	0.0535	0.1664	80/80	$6.605{\pm}0.018$
Integrated Gradients [ 22 ]	0.0313	0.1292	80/80	$2.180{\pm}0.012$	0.0165	0.2153	80/80	$8.668{\pm}0.715$
VarGrad [ 91 ]	0.0755	0.2121	80/80	$2.298{\pm}0.030$	0.0955	0.2643	80/80	$6.548{\pm}0.052$

TABLE VIII: Faithfulness, absolute query counts, and wall-clock time for multimodal ViT backbones on VGG-Sound.

Fig. 6: Attribution visualizations for audio classification on ImageBind and LanguageBind, highlighting the most critical spectrogram regions attributed to the model. Additionally, we provide the corresponding Insertion AUC curve.

Fig. 7: Visualization of failure attribution for CLIP on representative misclassified samples. In the attribution maps, green regions tend to support the ground-truth (GT) class, whereas red regions tend to support the originally predicted incorrect class. In the insertion curves, the green and red lines denote the recognition scores of the GT and incorrect classes, respectively. Failure attribution aims to identify a compact region whose revelation changes the prediction from the incorrect class back to the GT class, i.e., the GT recognition score becomes higher than that of the incorrect class. The searched region corresponds to the image content revealed at the turning point (dashed vertical line), representing the minimal region required to recover the correct prediction.

		Average highest confidence ( $\uparrow$ )
Backbones	Methods	(0-25%)	(0-50%)	(0-75%)	(0-100%)	Insertion ( $\uparrow$ )
	RISE [ 20 ]	0.2710	0.3985	0.4558	0.4879	0.1827
	HSIC-Attribution [ 12 ]	0.2148	0.2723	0.3051	0.3462	0.1062
	ViT-CX [ 45 ]	0.1268	0.2367	0.3137	0.3902	0.1236
	EAC [ 27 ] (w/ Segment Anything)	0.1004	0.1861	0.2561	0.3397	0.1086
	Grad-ECLIP [ 25 ]	0.2202	0.3404	0.3767	0.4123	0.1397

TABLE IX: Evaluation of failure attribution for different multimodal models on the ImageNet dataset.

		Average highest confidence ( $\uparrow$ )
Backbones	Methods	(0-25%)	(0-50%)	(0-75%)	(0-100%)	Insertion ( $\uparrow$ )
	Integrated Gradients [ 22 ]	0.0081	0.0318	0.0776	0.3904	0.0460
	RISE [ 20 ]	0.0064	0.0533	0.1547	0.2546	0.0385
	HSIC-Attribution [ 12 ]	0.0107	0.0441	0.0609	0.1657	0.0201
ImageBind [ 32 ]	LiMA ( $10\times 10$ )	0.0955	0.1978	0.3992	0.5028	0.1813
	Integrated Gradients [ 22 ]	0.0574	0.1092	0.1747	0.4254	0.1153

TABLE X: Evaluation of failure attribution for different multimodal models on the VGG-Sound dataset.

Fig. 8: Visualization of failure attribution for representative incorrect audio predictions.

		Average highest confidence ( $\uparrow$ )
Backbone	Methods	(0-25%)	(0-50%)	(0-75%)	(0-100%)	Insertion ( $\uparrow$ )
	Integrated Gradients [ 22 ]	0.2989	0.2989	0.2989	0.3012	0.1344
	Kernel SHAP [ 26 ]	0.1957	0.1962	0.1965	0.2024	0.1359
	RISE [ 20 ]	0.4986	0.5109	0.5163	0.5171	0.1470
	HSIC-Attribution [ 12 ]	0.4858	0.4927	0.5005	0.5013	0.1468
	ViT-CX [ 45 ]	0.3497	0.3595	0.3637	0.3658	0.1419

TABLE XI: Evaluation of failure attribution for the medical multimodal model QuiltNet on the LC25000 (Lung) dataset.

Fig. 9: Visualization of failure attribution for medical foundation model QuiltNet on representative misclassified samples.

		Average highest confidence ( $\uparrow$ )
Backbones	Methods	(0-25%)	(0-50%)	(0-75%)	(0-100%)	Insertion ( $\uparrow$ )
	Grad-CAM++ [ 43 ]	0.1988	0.2447	0.2544	0.2647	0.1094
	Score-CAM [ 44 ]	0.1896	0.2323	0.2449	0.2510	0.1073
	Kernel SHAP [ 26 ]	0.0083	0.0247	0.0574	0.2642	0.1008
	RISE [ 20 ]	0.2406	0.3032	0.3316	0.3807	0.2238
	HSIC-Attribution [ 12 ]	0.1709	0.2091	0.2250	0.2493	0.1446

TABLE XII: Evaluation of failure attribution for incorrect predictions across convolutional neural network backbones on the CUB-200-2011 dataset.

Bi-directional subset	Candidate pool size $n_{p}$	Faithfulness metrics			Exec. time (s)
Bi-directional subset	Candidate pool size $n_{p}$	Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )	$\mu$ Fidelity ( $\uparrow$ )	Exec. time (s)
✗	0	0.1260	0.8099	0.3669	32
✓	1	0.2048	0.6445	0.3344	16
✓	4	0.1309	0.7303	0.3508	18
✓	8	0.1280	0.7463	0.3526	20
✓	12	0.1271	0.7517	0.3551	22

TABLE XIII: Ablation study on the bidirectional greedy search algorithm for ImageBind on the ImageNet dataset.

Objective Function				Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )
Cons. Score	Colla. Score	Conf. Score	Eff. Score
(Equation 3 )	(Equation 4 )	(Equation 5 )	(Equation 7 )
✓	✗	✗	✗	0.2567	0.6324
✗	✓	✗	✗	0.1031	0.5598
✗	✗	✓	✗	0.3416	0.3609
✗	✗	✗	✓	0.3267	0.3909

TABLE XIV: revisionAblation study of the composite objective components for ImageBind on the ImageNet dataset.

Cons. Score	Colla. Score	Average highest confidence ( $\uparrow$ )				Insertion ( $\uparrow$ )
(Equation 3 )	(Equation 4 )	(0-25%)	(0-50%)	(0-75%)	(0-100%)	Insertion ( $\uparrow$ )
✗	✓	0.0821	0.3075	0.5869	0.6113	0.2691
✓	✗	0.5033	0.6087	0.6183	0.6392	0.2949
✓	✓	0.5351	0.6816	0.7445	0.7557	0.4681

TABLE XV: Ablation study of the composite objective components for incorrectly predicted samples using ImageBind on ImageNet.

Strategies	$\mu$ Fidelity ( $\uparrow$ )
Strategies	CLIP (ViT-L)	ImageBind (Huge)	LanguageBind (Large)
Consistent subset difference	0.3208	0.3378	0.3889
Importance Assessment	0.3334	0.3551	0.4096

TABLE XVI: Ablation study on importance assessment for ImageBind on the ImageNet dataset.

Fig. 10: An example of attribution results. A. Search region at the Insertion curve inflection point. B. Visualization using our strategy. C. Visualization using the baseline.

Sub-region Number $\|V\|$	Deletion ( $\downarrow$ )	Insertion ( $\uparrow$ )	$\mu$ Fidelity	Execution time (s)
49	0.1280	0.7463	0.3551	20
64	0.1230	0.7506	0.3473	39
77	0.1216	0.7532	0.3407	59
100	0.1199	0.7492	0.3291	158

TABLE XVII: Ablation study on the effect of sub-region division number

|V|

for ImageBind on the ImageNet dataset.

Sub-region Number $\|V\|$	Average highest confidence ( $\uparrow$ )				Insertion ( $\uparrow$ )
Sub-region Number $\|V\|$	(0-25%)	(0-50%)	(0-75%)	(0-100%)	Insertion ( $\uparrow$ )
49	0.5351	0.6816	0.7445	0.7557	0.4681
64	0.5579	0.7100	0.7689	0.7803	0.4934
77	0.5731	0.7194	0.7765	0.7884	0.5004
100	0.5987	0.7418	0.7958	0.8100	0.5144
121	0.6167	0.7599	0.8094	0.8247	0.5285

TABLE XVIII: Ablation study on the effect of sub-region division number

|V|

in incorrect sample attribution for ImageBind on the ImageNet dataset.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Fig. 11: Additional attribution visualizations for different multimodal foundation models on the ImageNet dataset.

Fig. 12: Additional interpretation visualization for CLIP (ResNet-101) on the ImageNet dataset.

Fig. 13: Additional interpretation visualization for single-modal ResNet-101 on the ImageNet dataset.

Fig. 14: Additional interpretation visualization for single-modal vision transformer (Large) and swin-transformer (Large) on the ImageNet dataset.

Fig. 15: Additional interpretation visualization for single-modal vision mamba (base) and mambavision (L2) on the ImageNet dataset.

Fig. 16: Visualization of failure attribution on the CUB-200-2011 dataset. The first row shows the results of HSIC-Attribution and the previous version, and the second row shows the current method. The insertion curve reports the relationship between progressively revealed regions and the ground-truth response. The highlighted prefix provides model-level evidence associated with prediction reversal under this intervention; the visualization is not interpreted as formal causal identification.

Fig. 17: Visualization of failure attribution on the CUB-200-2011 dataset across different recognition models. The insertion curve reports the relationship between progressively revealed regions and the ground-truth response. The highlighted prefix provides model-level evidence associated with prediction reversal under this intervention; the visualization is not interpreted as formal causal identification.

Fig. 18: Controlled analysis of SLICO- and SAM-based sub-regions. A. oversized or decision-heterogeneous SAM masks delay recognition. B. boundary-aligned SAM masks isolate the object or its discriminative parts more effectively than low-level superpixels.

Feature Attribution

Feature attribution estimates which input features or internal components contribute to a model’s predictions.

See all 231 papers

Hide and Seek: HIDE Concepts to SEEK explanations for black box models
Oct 9, 2026Bhanu Tokas, Rahul Nair, Rockwell Jackson +1Interpretable ML Concept-Based Explanations
Arizona State University
A Good Initialization is All You Need for Faithful Visual Attribution
Jul 7, 2026Zihan Gu, Jiayu Wang, Hua Zhang +1Feature Attribution Perturbation-Based Feature Attribution
Institute of Information Engineering, Chinese Academy of Sciences · School of Cyber Security, University of Chinese Academy of Sciences
Did Models Learn Sufficiently? Attribution-Guided Training via Subset-Selected Counterfactual Augmentation
Nov 15, 2025Yannan Chen, Ruoyu Chen, Wei Wang +6Adversarial Robustness OOD Generalization
School of Cyber Science and Technology, Sun Yat-Sen University, Guangdong Province, China · Institute of Perception, PC Laboratory, Guangdong Province, China · University of Chinese Academy of Sciences, Beijing, China +3

Oct 9, 2026J/K move · Enter open · S save

Hide and Seek: HIDE Concepts to SEEK explanations for black box models

Bhanu Tokas, Rahul Nair, Rockwell Jackson, Hannah Kerner

Arizona State University

Interpretable ML Concept-Based Explanations

Open paper AskPDF arXiv

Interpreting machine learning model predictions is a central challenge, particularly for black-box vision models. Concept-based attribution methods interpret models using human-understandable concepts. Existing concept-based methods can only interpret classification and regression models. They require access to model weights or large concept-annotated datasets, and most methods cannot provide image-level attribution. We propose Hide and Seek (HnS), a new method for concept-level attribution that does not require access to model weights or labeled concept datasets. HnS can interpret a wide range of vision models. Given a concept and image set, HnS retrieves concept-aligned images using a vision-language model, localizes the concept within each image, masks the localized region, and measures attribution from the change in the black-box model's output between the original and masked images. This enables faithful attribution by directly measuring the model's behavior and supporting local attributions. We validated HnS on CelebA and COCO-Stuff. Compared to existing methods, HnS showed better agreement with ground-truth attributions. We demonstrated the applicability of HnS on diverse tasks, including image captioning and satellite image segmentation, where no existing concept attribution method can be used. We provided our anonymous code in the supplementary material.

Abstract

Feature Attribution

Explore similar work

Hide and Seek: HIDE Concepts to SEEK explanations for black box models

A Good Initialization is All You Need for Faithful Visual Attribution

Did Models Learn Sufficiently? Attribution-Guided Training via Subset-Selected Counterfactual Augmentation