A Good Initialization is All You Need 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. textscCoPAIR uses a PhaseWin--Greedy gap diagnosis to construct coarse singleton/pair candidates that warm-start full-ordering search. textscTRACE 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, textscTRACE+Greedy gives the strongest search-based MLLM attribution results. Direct textscTRACE 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.