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

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.

Faithful visual attribution identifies which image regions support a model prediction. Search-based perturbation methods lead the insertion--deletion faithfulness frontier by masking regions and measuring score changes, but they usually output a complete ordering of all regions. Many applications, especially MLLM attribution and repair, only need a compact top-$k$ evidence mask. We study this mask-first attribution problem. An exactly $k$-region mask is combinatorial: useful evidence can depend on interactions among fine regions. Coarse grouping can stabilize early search but aggregates redundant content, whereas one-step scoring can miss high-value combinations. We introduce two forward-only methods. CoPAIR uses a PhaseWin--Greedy gap diagnosis to construct coarse singleton/pair candidates that warm-start full-ordering search. TRACE directly searches fixed-cardinality fine-region masks with cross-entropy sampling, elite retention, and distribution updates, with a finite-budget recovery analysis. The resulting evidence set can be returned as a compact attribution mask or used to initialize Greedy or PhaseWin when a complete ranking is required. Across ImageNet classification with CLIP ViT-L/14, CLIP RN101, and ResNet-101, our initialized search methods establish a new state-of-the-art frontier for faithful full-ordering attribution under inclusive forward-call accounting. On POPE and RePOPE with Qwen2.5-VL-3B-Instruct and LLaVA-v1.5-7B, TRACE+Greedy gives the strongest search-based MLLM attribution results. Direct TRACE masks further achieve single-point RePOPE repair rates of $94.44\%$ and $96.00\%$, showing that compact evidence masks can be actionable attribution outputs, not merely prefixes of full rankings.

Current visual models often make predictions based on a limited set of discriminative visual cues. As a result, they may become unreliable when the distribution shifts or when these cues are missing. Faithful attribution methods can reveal such problematic reliance through localized explanations, but they are typically used post hoc and are not fed back into the model. To address this limitation, we propose Subset-Selected Counterfactual Augmentation (SS-CA), a training strategy that masks decision-relevant regions to construct counterfactual samples and guide the model toward more robust decision boundaries. Specifically, we extend LIMA, a subset-selection-based faithful attribution method, to Counterfactual LIMA to identify regions whose removal shifts the model toward a competing class. SS-CA then selects near-boundary masks that reduce the logit gap while preserving the original semantics, and applies an adaptive counterfactual filling strategy to replace the masked regions without introducing external semantics. Feeding these counterfactual samples back into training encourages the model to exploit the remaining informative evidence and shifts the decision boundary toward a more robust one. Extensive experiments across five ImageNet variants show that SS-CA effectively improves ID accuracy, OOD generalization, and perturbation robustness, achieving gains of 5.70%/18.04% on ImageNet-1k/ImageNet-R with CLIP ViT/32b, 9.52%/11.33% on ImageNet-R/ImageNet-S on TinyImageNet-200 with ResNet-101, and about 4% under Gaussian Noise corruption. The code will be released soon.