PhaseWin: An Efficient Search Algorithm for Faithful Visual Attribution

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. \textsc{CoPAIR} uses a PhaseWin--Greedy gap diagnosis to construct coarse singleton/pair candidates that warm-start full-ordering search. \textsc{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, \textsc{TRACE}+Greedy gives the strongest search-based MLLM attribution results. Direct \textsc{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.

Attribution methods are widely used to characterize the evidence underlying model predictions, yet their potential to improve model behavior remains underexplored. Attribution inconsistency under label-preserving geometric transformations may indicate transformation-sensitive evidence reliance, motivating attribution regularization. However, such supervision is valid only when attribution faithfully reflects the evidence driving predictions. Existing self-supervised methods typically align gradient-based maps such as Grad-CAM, whose limited faithfulness means that attribution consistency need not imply consistency of the underlying decision process, leaving transformation robustness unresolved. We propose an annotation-free attribution regularization framework based on submodular search over image regions. By measuring how candidate subsets affect model outputs, the search extracts compact, class-discriminative evidence as search-derived supervision. We further introduce a submodular ranking loss with path-consistency and termination-alignment terms that respectively align spatially corresponding candidate rankings along paired search trajectories and encourage the transformed trajectory to satisfy the stopping criterion at the target terminal step. The loss provides a differentiable surrogate for regularizing both final attributions and the otherwise discrete evidence-selection process. Experiments on ImageNet-100 show that our method substantially improves attribution stability, Insertion, and Deletion on ViT-B/16 with only a 0.28-point accuracy drop, with similar gains on ViT-L/16. On ImageNet-1K, it improves transformed-input accuracy on ResNet-50 and ConvNeXt-B while limiting the clean-accuracy drop to 0.30 points, demonstrating more consistent evidence reliance with minimal performance loss. Code will be released soon.

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.