1 Introduction↩︎

Faithful visual attribution asks which image regions actually support a model prediction. Because explanations are used as evidence of model reliance, a plausible heatmap is insufficient: faithfulness should be tested by intervening on the image and measuring how the model response changes. Insertion and deletion curves provide this operational test by asking whether selected regions recover the prediction and whether removing them destroys it  [1]–[3].

Most strong attribution benchmarks assume a full-ordering contract: a method ranks all image regions so that every prefix can be evaluated by insertion or deletion. This is useful for full-curve evaluation, but many downstream uses only need a compact evidence set. In MLLM hallucination attribution and repair, the practical question is often not how to rank every region, but which small set of visual evidence supports a generated answer or intervention. We therefore treat the fixed-size top-\(k\) evidence mask as a primary attribution object, while retaining compatibility with full-ordering evaluation.

This mask-first contract changes the optimization problem. The best \(k\)-region mask need not be a prefix of a greedy ranking, since its value can depend on interactions among fine regions. One-step scores can miss evidence that is only useful in combination, while coarse grouping can stabilize search but may aggregate redundant content. The challenge is to find a sparse, high-value fine-region evidence set under a black-box, forward-only evaluation budget.

Search-based perturbation is the right foundation for this goal because it evaluates masked inputs and directly optimizes quantities aligned with faithfulness, unlike gradient-based explanations such as Grad-CAM [4] and Integrated Gradients [5]. LIMA [2] showed that Greedy region search gives strong insertion faithfulness, and later work extended this view to object-level foundation models  [3] and autoregressive MLLM token generation [6]. However, Greedy costs \(O(n^2)\) forward passes. PhaseWin [7] reduces this cost, but its extended analysis shows that the residual gap to Greedy concentrates on partition-sensitive samples  [8]. This suggests that early evidence quality is also a granularity problem: fine regions can fragment evidence that would be more stable at a coarser scale. This diagnosis motivates CoPAIR (Coarse Pairwise Attribution Initializer with Release). CoPAIR clusters fine regions into coarse spatial groups, evaluates strong coarse singletons and pairs, and releases the selected candidate back into fine-region continuation search. It is therefore a principled initializer for Greedy or PhaseWin derived from the PhaseWin–Greedy gap. Its limitation is the same aggregation that makes it useful: a coarse group can merge object parts, background fragments, and redundant fine regions, so it is not a minimal compact explanation. Thus CoPAIR improves full-ordering initialization, but does not solve the mask-first problem.

We therefore introduce TRACE (Top-\(k\) Region Attribution via Cross-Entropy), a forward-only method that directly optimizes fixed-cardinality fine-region masks. TRACE samples \(k\)-hot candidate masks, evaluates them by the model response, keeps elite samples, and updates the sampling distribution toward high-scoring evidence combinations. The returned mask can be used directly as the attribution object, or used to initialize Greedy or PhaseWin when a complete ordering is required. We also provide a finite-budget recovery analysis showing how the cross-entropy updates increase probability mass on near-optimal evidence basins. Figure 1 illustrates this shift from stepwise full-curve attribution to an actionable top-\(k\) evidence anchor.

Empirically, CoPAIR and TRACE establish a new state-of-the-art frontier for faithful visual attribution under a black-box, forward-only interface. On ImageNet-derived classification splits with SLICO-64 regions  [9], CLIP ViT-L/14, CLIP RN101 [10], and ResNet-101 [11], our initialized search methods improve task-relevant full-ordering faithfulness over raw search under inclusive forward-call accounting. On POPE [12] and RePOPE [13] with Qwen2.5-VL-3B-Instruct [14] and LLaVA-v1.5-7B  [15], TRACE+Greedy gives the strongest search-based MLLM attribution results. Direct TRACE masks further repair \(94.44\%\) and \(96.00\%\) of RePOPE cases, respectively, using a single mask intervention rather than a full repair curve.

Our contributions are:

• We formulate compact top-\(k\) evidence masks as a primary output contract for faithful visual attribution, while preserving full-ordering evaluation.

• We derive CoPAIR from the PhaseWin–Greedy gap diagnosis as a coarse-pair initializer, and address its aggregation limitation with TRACE, a cross-entropy search method for fixed-size fine-region masks.

• We establish a new state-of-the-art frontier for forward-only faithful visual attribution across ImageNet classification, POPE, and RePOPE, and show that direct TRACE masks enable effective single-point MLLM repair.

2 Related Work↩︎

2.0.0.1 Visual attribution methods.

Gradient and activation saliency methods [4], [5], [16]–[28] are computationally efficient but require white-box access and do not directly measure the causal relationship between input regions and model outputs, a concern also reflected in saliency sanity checks [29]. Perturbation-based methods [1], [30]–[34] and Shapley-style attribution [35]–[39] evaluate the model on masked inputs and are therefore applicable to any black-box model, but achieve only moderate faithfulness due to their unstructured or approximate nature. Search-based attribution [2], [3] achieves the highest faithfulness by casting region ranking as combinatorial optimization: a greedy algorithm iteratively selects the region with the greatest marginal score gain, producing a provably high-quality ordering at \(O(n^2)\) cost. PhaseWin [7], [8] reduces this to \(O(n)\) via partition-dominant structure, but the remaining gap to Greedy concentrates on partition-sensitive tail cases. Our work targets a complementary object: a compact evidence mask that can be returned directly when no full ranking is needed, or used as the initial state for Greedy and PhaseWin when a complete ordering is required.

2.0.0.2 Attribution tasks.

The dominant benchmark for visual attribution is image classification on ImageNet [40] with CNN, ViT, and CLIP backbones [10], [11], [41], where attribution identifies which image regions drive the classifier’s top-class prediction. Faithful attribution for multimodal large language models (MLLMs) and adjacent vision-language systems such as LLaVA-v1.5-7B [15], [42], BLIP-2 [43], Grounding DINO [44], Florence-2 [45], and Qwen2.5-VL-3B-Instruct [14] is far less explored, despite recent MLLM explanation work [28], [46]–[49]. Because answer generation depends on the interplay of visual tokens and language context, gradient signals through the visual encoder are unreliable proxies for causal influence. Defining the attribution score as the first-token probability of the generated answer makes perturbation-based search directly applicable, but the \(O(n^2)\) cost of Greedy has historically made this impractical at scale. EAGLE [6] adapts greedy search to autoregressive MLLM attribution and introduces hallucination attribution and repair evaluation on POPE and RePOPE [12], [13]. TRACE keeps the same black-box scoring interface while directly searching for a fixed-size visual evidence mask; this mask can either support repair directly or warm start the full search protocol.

3 Method↩︎

3.1 Search-Based Attribution Setup↩︎

We build on the search-based visual attribution framework of Greedy [2], VPS [3], and PhaseWin [7]. The input image is partitioned into fine regions \[U=\{u_1,\ldots,u_n\}.\] For a target \(y\), let \(f_y(x)\in[0,1]\) denote the normalized model response on image \(x\), such as a class probability or an MLLM answer-token probability under a fixed prompt. For any subset \(S\subseteq U\), its retained image is \[x_S = m(S)\odot x + \bigl(1-m(S)\bigr)\odot x_0 , \label{eq:masked-image}\tag{1}\] where \(m(S)\) is the binary mask induced by \(S\) and \(x_0\) is a baseline image. We use the same proxy family as prior faithful attribution search: \[F(S)=\operatorname{Suff}(S) \quad \text{or} \quad F(S)=\alpha \operatorname{Suff}(S) +(1-\alpha)\operatorname{Necc}(S), \label{eq:proxy}\tag{2}\] where \[\operatorname{Suff}(S)=f_y(x_S), \qquad \operatorname{Necc}(S)=1-f_y(x_{U\setminus S}).\]

A full-ordering attribution method returns a permutation \(\Pi=(\pi_1,\ldots,\pi_n)\) of regions, so any prefix \(\{\pi_1,\ldots,\pi_t\}\) can be evaluated by insertion or deletion curves. However, many downstream uses of attribution do not require the whole ordering. They need a compact top-\(k\) evidence mask \(S\) with \(|S|=k\), for example to highlight the visual evidence behind an MLLM token or to perform a single repair intervention. We therefore separate two output contracts: initialization for full-ordering search, and direct fixed-size fine-region mask attribution. Furthermore, the greedy nature of seeking a local optimum at each step—while yielding excellent ranking performance—often results in a loss of the ability to explore the global optimum. If we can directly output a high-value top-k prefix, the attribution performance of search-based algorithms will also be correspondingly enhanced.

Search with initialization framework. Given an initialized fine-region prefix \[\Pi_0=(\pi_1,\ldots,\pi_r), \qquad S_{\mathrm{init}}=\{\pi_1,\ldots,\pi_r\},\] a continuation algorithm \(\mathcal{A}\) completes the remaining ordering as \[\Pi_{\mathrm{tail}} = \mathcal{A}\bigl(F; S_{\mathrm{init}}, U\setminus S_{\mathrm{init}}\bigr), \qquad \Pi=\Pi_0\oplus \Pi_{\mathrm{tail}} . \label{eq:initialized-search}\tag{3}\] Regions not included in \(S_{\mathrm{init}}\) are released back to the live pool and can be selected later by the continuation search.

3.1.0.1 Internal ordering and release.

For any candidate set \(C\subseteq U\), we order its fine regions by greedy marginal rescoring inside \(C\): \[\pi_t = \arg\max_{u\in C\setminus P_{t-1}} F(P_{t-1}\cup\{u\}), \qquad P_{t-1}=\{\pi_1,\ldots,\pi_{t-1}\}. \label{eq:internal-greedy}\tag{4}\] Given a partial-release ratio \(\gamma\in(0,1]\), we keep the shortest prefix satisfying \[r = \min\left\{ t: F(P_t)\ge \gamma F(C) \right\}, \qquad S_{\mathrm{init}}=P_r. \label{eq:release-rule}\tag{5}\] The remaining regions \(C\setminus S_{\mathrm{init}}\) are released to \(U\setminus S_{\mathrm{init}}\) before downstream search.

3.2 CoPAIR: Coarse Pairwise Attribution Initializer with Release↩︎

We derive our initial design strategy by contrasting the PhaseWin algorithm with the greedy approach. As detailed in [8], the greedy method’s apparent advantage in handling the long tail can be reinterpreted as repeated early-prefix recovery: when an unfavorable fine partition fragments visual evidence, global rescoring lets the model recover decisive fragments as the context evolves. Coarser partitions aggregate these fragments into more stable attribution units, mitigating this tail behavior directly. This observation motivates CoPAIR (Algorithm 2), a deterministic coarse-spatial initializer that evaluates coarse singleton and pair candidates first, then integrates the selected evidence into the fine-region continuation search.

Let \(\mathcal{G}=\{G_1,\ldots,G_c\}\) denote a deterministic centroid-based coarse partition of the fine regions, \[G_i\subseteq U,\quad G_i\cap G_j=\emptyset\;(i\ne j), \qquad \bigcup_{i=1}^c G_i=U, \label{eq:coarse-partition}\tag{6}\] with coarse count \[c = \operatorname{clip} \bigl(\operatorname{round}(\beta\sqrt{|U|}),c_{\min},c_{\max}\bigr). \label{eq:copair-count}\tag{7}\]

CoPAIR’s working assumption is that, once local evidence has been absorbed within coarse groups, the early cross-group value is dominated by singleton and pairwise terms. Formally, for \(I\subseteq[c]\), \[F\Bigl(\bigcup_{i\in I}G_i\Bigr) = \phi_\emptyset +\sum_{i\in I}\phi_i +\sum_{\substack{i<j\\i,j\in I}}\phi_{ij} +\sum_{\substack{J\subseteq I\\ |J|\ge 3}}\phi_J, \label{eq:coarse-interactions}\tag{8}\] where the higher-order remainder \(\sum_{|J|\ge 3}\phi_J\) is assumed small for the early coarse candidates the initializer considers. Pair enumeration is therefore not an independent scoring heuristic but an explicit search over coarse-level interactions.

CoPAIR evaluates every coarse singleton and retains the top-\(q\) candidates as a high-sufficiency pool, \[\mathcal{P} = \operatorname{TopQ}_{G_i\in\mathcal{G}} F(G_i), \label{eq:copair-pool}\tag{9}\] then exhaustively searches pairs within that pool, \[(a,b) = \arg\max_{G_i,G_j\in\mathcal{P},\, i<j} F(G_i\cup G_j). \label{eq:copair-pair}\tag{10}\] Writing \(G_s=\arg\max_{G_i\in\mathcal{G}}F(G_i)\), \(C_{\mathrm{pair}}=G_a\cup G_b\), and \(\Delta=F(C_{\mathrm{pair}})-F(G_s)\), the pair-gain margin \(\delta\) and sufficiency threshold \(\tau\) select the initial coarse candidate \[C_0 = \begin{cases} G_s, & \Delta < \delta \;\land\;F(G_s)\ge\tau,\\ C_{\mathrm{pair}}, & \text{otherwise}. \end{cases} \label{eq:copair-fallback}\tag{11}\]

If \(F(C_0)<\tau\), CoPAIR absorbs one additional coarse group by greedy sufficiency improvement, \[\begin{align} G_h = \arg\max_{G\in\mathcal{P}:\,G\cap C_0=\emptyset} F(C_0\cup G), \\ C_0 \leftarrow C_0\cup G_h . \end{align} \label{eq:copair-third-block}\tag{12}\] applied at most once regardless of whether \(C_0\) initially holds one group (\(G_s\)) or two (\(C_{\mathrm{pair}}\)), so the candidate never exceeds three coarse groups.

Finally, CoPAIR applies the internal greedy ordering and release rules defined in Eqs. 4 –5 to \(C_0\), yielding \((\Pi_0, S_{\mathrm{init}})\) as a starting point for continuation search — the return step of Algorithm 2. CoPAIR thus serves as a structured initializer for both Greedy and PhaseWin. Notably, it is not intended to solve the fixed-\(k\) fine-region mask problem directly; that objective requires stepping outside this specific search framework, a task the core TRACE algorithm described below addresses directly.

3.3 TRACE: Top-k Region Attribution via Cross-Entropy↩︎

TRACE (Algorithm 3) directly targets the fixed-cardinality fine-region mask problem. A candidate mask is represented by \[\begin{align} z\in\{0,1\}^{|U|}, \; \|z\|_0=k, \; S(z)=\{u_i:z_i=1\}. \label{eq:trace-mask} \end{align}\tag{13}\]

Unlike CoPAIR, which constructs a coarse candidate for continuation search, TRACE searches the exactly-\(k\) fine-region mask space directly. The returned mask is the best candidate observed under the finite forward budget, not a certified global optimum; Appendix 6 gives the finite-budget recovery analysis and the notation used for this probabilistic view.

TRACE adapts the cross-entropy method [50] to the discrete \(k\)-hot space: it maintains logits \(\theta\in\mathbb{R}^{|U|}\), samples candidate masks, retains elite candidates, and updates the distribution toward regions that repeatedly appear in high-scoring masks.

At round \(r\), each candidate is sampled by Gumbel-top-\(k\) perturbation [51]: for sample \(m\), draw \(g_i^{(m)}\sim\operatorname{Gumbel}(0,1)\) i.i.d.and select \[{!}{ \begin{align} z_i^{(m)} = \mathbf{1}\left[ i\in \operatorname{TopK} \left\{ \theta_j/T+g_j^{(m)} \right\}_{j=1}^{|U|} \right], \label{eq:trace-sampling} \end{align} }\tag{14}\] where \(T\) is the temperature. The candidate score is \[b^{(m)} = F(S(z^{(m)})). \label{eq:trace-score}\tag{15}\] Let \(\mathcal{E}\) be the top \(\lceil\rho_{\mathrm e}M\rceil\) samples by \(b^{(m)}\), where \(\rho_{\mathrm e}\) is the elite ratio. The empirical elite inclusion frequency is \(\hat{p}_i = \frac{1}{|\mathcal{E}|} \sum_{z\in\mathcal{E}} z_i .\)

Exact maximum-likelihood fitting of a Gumbel-top-\(k\) distribution to elite sets has no closed-form componentwise update, so TRACE instead uses an inclusion-moment surrogate: the smoothed marginal target \[\tilde{p}_i = (1-\lambda_{\mathrm{sm}})\hat{p}_i +\lambda_{\mathrm{sm}}\frac{k}{|U|}, \label{eq:trace-smooth}\tag{16}\] drives the logit update \[\theta_i \leftarrow \operatorname{clip} \left( (1-\eta)\theta_i + \eta\operatorname{logit} \bigl(\operatorname{clip}(\tilde{p}_i,\epsilon,1-\epsilon)\bigr), -\theta_{\max},\theta_{\max} \right), \label{eq:trace-update}\tag{17}\] where \(\eta\) is the update rate, \(\epsilon\) prevents saturated logits, and \(\theta_{\max}\) bounds the logits.

As shown in Algorithm 3, TRACE tracks the best observed mask incrementally as each candidate is scored, equivalently \(S^\star = \arg\max_{S(z)\;\text{evaluated}} F(S(z)).\) When the task only needs a compact evidence set, \(S^\star\) is returned directly as the final attribution mask. When a complete ordering is required, TRACE applies the same internal greedy ordering and release rule from Eqs. 4 –5 to \(S^\star\), obtaining \((\Pi_0,S_{\mathrm{init}})\), and then uses the continuation interface in Eq. 3 .

The nominal TRACE search evaluates \(RM\) candidate masks before duplicate caching. Under the sufficiency-only proxy used in the main experiments, each uncached candidate requires one model forward, and masks from the same round can be evaluated as a batch. If the combined sufficiency–necessity proxy in Eq. 2 is used instead, each uncached candidate requires both the retained and complement evaluations. The default TRACE budget is thus independent of the number of fine regions once \(R\), \(M\), and \(k\) are fixed, while the continuation cost depends on the remaining live pool.

4 Experiments↩︎

We evaluate two attribution contracts. When a complete ordering is required, TRACE and CoPAIR initialize Greedy (G) or PhaseWin (PW) and are evaluated by insertion–deletion replay. When only a compact evidence set is required, the selected mask is applied directly as a single repair intervention. All tables report task-matched metrics and, for forward-only methods, inclusive selection cost. All initializer hyperparameters, including CoPAIR coarse-pair settings, TRACE sampling settings, duplicate caching, internal greedy ordering, and the \(0.8\) partial-release rule, are reported in Appendix 8.1. Additional protocol details and table conventions are given in Appendix 8.

4.1 Setup and Baselines↩︎

For image classification, we follow the faithful visual attribution protocol used by LIMA, VPS, and PhaseWin [2], [3], [7]. We evaluate CLIP ViT-L/14 and CLIP RN101 [10], and supervised ResNet-101 [11], on ImageNet-derived Correct, Cause, and Repair splits [40] with SLICO-64 regions [9]. The non-search classification baselines include RISE [1], HSIC [34], vanilla gradient saliency [16], Grad-ECLIP [25], IG2 [5], and IGOS++ [49]. For MLLMs, we evaluate the POPE decision-faithfulness and RePOPE repair settings [12], [13] with Qwen2.5-VL-3B-Instruct [14] and LLaVA-v1.5-7B [15]. The MLLM attribution and repair protocol follows EAGLE [6]; its non-search references include LLaVA-CAM [48] and IGOS++ [49].

4.2 Metrics and Accounting↩︎

All scores use normalized target responses \(f_y(x)\in[0,1]\). For ordered attribution, we report insertion AUC (Ins; higher is better), deletion AUC (Del; lower is better), the insertion score at 50% released area (50?), and the maximum insertion score (High). Correct, Cause, and POPE emphasize Ins; classification Repair and RePOPE emphasize High. For single-point RePOPE repair, direct masks are evaluated by Repair Rate, with Correct/Total and Failed reporting the corresponding counts. Full ordered repair metrics such as AMCR, CSR@10, and CorrectionRate are deferred to Appendix 8. MEC(k) reports thousands of selection-time model forwards and excludes insertion/deletion replay. For initialized rows, MEC is inclusive: it includes uncached initializer calls and downstream continuation calls. Under the default sufficiency-only TRACE scoring, each uncached sampled mask uses one forward; using the combined sufficiency–necessity proxy would require both retained and complement evaluations. MEC is compared only within the forward-only family and is left blank for gradient, CAM, and forward-backward optimization methods.

4.3 Image Classification Attribution↩︎

2.1pt

Table 1 gives the full CLIP ViT-L/14 landscape, including perturbation, gradient, optimization-based, and search-based methods. Superscripts on initialized rows report the absolute gain over the corresponding raw search in the emphasized metric; MEC subscripts report the cost change against the same raw search. The search family is already much stronger than non-search baselines, but initialization still moves the frontier. TRACE+G gives the best task-relevant score in all three splits: Correct Ins improves from 0.8431 to 0.8679, Cause Ins from 0.7237 to 0.7527, and Repair High from 0.8009 to 0.8190. These gains are not obtained by spending more search: the inclusive MEC for TRACE+G is lower than raw Greedy in each split. PW-based continuation also benefits from initialization, although its inclusive MEC can increase slightly on Repair when the seed cost is not fully offset by the smaller continuation problem. Figure 4 shows representative Correct-split cases behind Table 1: the initialized curve recovers the class score earlier, and the displayed masks concentrate the early evidence on the object regions that support the prediction.

Table 2 checks whether the pattern depends on the CLIP ViT-L/14 backbone. We only show the search family here, and defer the full baseline landscape for CLIP RN101 and ResNet-101 to Appendix 9.3. The result is useful precisely because it is not a single-method sweep. On CLIP RN101, CoPAIR+G is the strongest variant for the emphasized metrics, suggesting that coarse spatial pairing can be valuable when the backbone favors coarser evidence units. On ResNet-101, TRACE+G is strongest on Correct Ins, Cause Ins, and Repair High. Across both backbones, at least one initialized search variant improves the emphasized metric over its raw continuation baseline, showing that initialization changes the attribution search frontier rather than merely reformatting the same ranking.

Furthermore, we conducted ablation studies on \(k\) and various hyperparameters of TRACE using classification scenarios. We also performed comparative experiments to demonstrate the necessity of the probabilistic mask. These experimental results validate the robustness of TRACE. Detailed experimental results are provided in Appendix 9.

1.8pt

4.4 MLLM Hallucination Attribution↩︎

Table 3 keeps the full MLLM attribution landscape in the main text, because hallucination attribution is the setting where compact evidence masks are most directly actionable. The table groups results by model and dataset. LLaVA-CAM and IGOS++ provide useful non-search references, but they are far below search-based methods on insertion faithfulness. On POPE, TRACE+G gives the best Ins for both Qwen2.5-VL-3B and LLaVA-v1.5-7B. On RePOPE, raw Greedy remains competitive in Ins for Qwen, but the repair-relevant High metric is highest for TRACE+G on both models. This distinction matters: RePOPE asks whether the selected evidence can recover the corrected answer, so the peak confidence along the insertion trajectory is the more direct signal for repair.

3.2pt

4.5 Direct Evidence Masks for RePOPE Repair↩︎

The previous tables evaluate ordered insertion curves. Table 4 tests the mask-first use case directly: a single selected evidence mask is applied as one repair intervention on RePOPE. This setting does not require ranking every region. Direct TRACE masks repair 94.44% of Qwen cases and 96.00% of LLaVA cases, substantially above the LLaVA-CAM and IGOS++ full-curve repair rates. CoPAIR Direct is also stronger than these non-search baselines, but the gap between CoPAIR and TRACE is large, matching our method design: coarse pairing is a useful initializer, whereas direct fine-region mask search is the more appropriate tool when the output itself is a compact evidence mask. The full ordered repair protocol, including CSR@10, is reported in Appendix 9.6; the memory-saving deployment used for the parenthesized engineered memory numbers in Table 4 is detailed in Appendix 8.4. Figure 5 visualizes representative cases where full-curve LLaVA-CAM and IGOS++ do not find a repairing prefix, while TRACE Direct returns a compact mask that repairs the model answer.

3.4pt

5 Conclusion↩︎

We presented TRACE, a forward-only method for faithful top-\(k\) visual attribution. It directly searches fixed-size fine-region evidence masks and delivers two operating modes: a standalone binary-mask mode for tasks that require only a compact evidence set, and an initialization mode that improves full-ordering Greedy or PhaseWin search. CoPAIR provides a complementary deterministic initializer based on coarse spatial grouping and pairwise evidence enumeration, but the central contribution is the TRACE mask: it handles non-geometric fine-region combinations, can support repair directly, and reduces redundant early search when a complete ranking is required. Both are model-agnostic and validated on image classification (ImageNet-1K, SLICO-64; CLIP ViT-L/14, CLIP RN101, ResNet-101), MLLM decision-faithfulness attribution on POPE, and repair-oriented evidence recovery on RePOPE (Qwen2.5-VL-3B-Instruct and LLaVA-v1.5-7B).

5.0.0.1 Limitations.

The initialization overhead (\(c^2\) for CoPAIR or \(RM\) for TRACE) is negligible for large \(n\) but may dominate when \(n\) is small. TRACE’s stochastic sampling introduces run-to-run variance, which is small in practice but non-zero. The fixed-\(k\) constraint in TRACE requires choosing mask size \(k\) in advance.

6 Additional TRACE Notes↩︎

Section 3.3 gives the TRACE objective, Gumbel-top-\(k\) sampling rule, elite update, and continuation interface. This appendix avoids restating those equations and records only the implementation-level conventions and scope limitations that are useful when interpreting the experiments.

6.1 Candidate Masks and Returned Objects↩︎

TRACE samples only fixed-cardinality fine-region masks. Every evaluated candidate therefore contains exactly \(k\) distinct regions, and no rejection step or post-hoc cardinality repair is needed. In the implementation, a candidate mask is identified by the sorted set of selected region indices. This representation is used for duplicate detection and for storing the best observed candidate during the cross-entropy rounds.

The returned mask is empirical rather than certified: it is the highest-scoring candidate observed under the allocated model-evaluation budget. This distinction matters because the proxy \(F(S)\) is a black-box, nonconvex set objective induced by masked model responses. We therefore do not claim that TRACE solves the global optimum over all \(\binom{n}{k}\) masks; the method is a budgeted search procedure that concentrates samples around regions repeatedly appearing in elite fixed-size masks.

When the downstream task is mask-oriented, this best observed set is returned directly as the attribution or repair mask. When the downstream task requires a full ordering, the same set is used as the initialized prefix described in Eq. 3 . Thus the direct-mask and full-ordering uses share one searched object, rather than using separate attribution procedures.

6.2 Why Not Independent Region Scores?↩︎

A one-step score for each region is cheaper, but it does not model the interaction among selected regions. In visual attribution, this interaction is common: two object parts may be redundant, a background fragment may only matter together with an object region, and an MLLM answer token may depend on a specific combination of local visual cues. Independent scores also do not enforce the output contract that many downstream uses require: a compact mask of exactly \(k\) regions.

Independent Bernoulli sampling has the opposite issue. It can model uncertainty over regions, but the sampled cardinality varies unless an extra constraint or projection is introduced. TRACE uses Gumbel-top-\(k\) sampling because the sampled object is already feasible for the target mask family. This keeps the optimization distribution, the evaluated candidates, and the final output in the same fixed-cardinality space.

6.3 Budget and Caching Scope↩︎

The nominal TRACE budget is \(RM\) candidate masks for \(R\) rounds and \(M\) samples per round. Duplicate masks can occur, especially after the sampling distribution becomes concentrated. In that case, the implementation reuses the stored score instead of issuing another model call. The MEC values reported for initialized rows are inclusive: they include the initializer calls that survive caching and the subsequent continuation calls made by Greedy or PhaseWin.

This accounting is deliberately narrower than wall-clock runtime. MEC is a forward-call count for comparable forward-only selection procedures; it does not attempt to price backward passes, optimizer steps, KV-cache memory, or hardware placement. Those runtime and memory details are reported separately where they matter, especially for the MLLM repair comparison in Table 4.

6.4 Probabilistic Recovery Under a Phase-Structured Attribution Model↩︎

We next record a finite-budget recovery bound for TRACE. The structural assumptions used in this subsection are not new modeling claims of this paper. They are inherited from the extended PhaseWin analysis [8], which interprets the hard tail of search-based visual attribution through partition-sensitive semantic evidence blocks. This inheritance includes the block-level monotonicity assumption used below: adding activated semantic evidence blocks should not decrease the dominant attribution value. We use the same phase-structured view only to make explicit when the cross-entropy updates in TRACE can improve over non-adaptive random search.

Let \(U=\{u_1,\ldots,u_n\}\) be the fine-region set and let \[\mathcal{C}_k(U)=\{S\subseteq U: |S|=k\}\] be the feasible family of exactly-\(k\) masks. For a nonnegative attribution proxy \(F:2^U\to\mathbb{R}_+\), define the fixed-\(k\) optimum and the best TRACE value observed under a budget of \(R\) rounds and \(M_{\mathrm{samp}}\) masks per round as \[\mathrm{opt} = \max_{S\in\mathcal{C}_k(U)}F(S), \qquad \mathrm{opt}_{\mathrm{trace}} = \max_{\substack{0\le r\le R-1\\1\le j\le M_{\mathrm{samp}}}} F(S_{r,j}), \label{eq:app-trace-opt-values}\tag{18}\] where \(\mathrm{opt}>0\). We write \(M_{\mathrm{samp}}\) in this subsection to avoid confusing the per-round sample count with the optimum value; it is the same quantity denoted by \(M\) in Algorithm 3. For an approximation ratio \(\mu\in(0,1)\), define the near-optimal mask set \[\mathcal{G}_\mu = \{S\in\mathcal{C}_k(U): F(S)\ge \mu\,\mathrm{opt}\}. \label{eq:app-trace-near-optimal-set}\tag{19}\] Then \(\mathrm{opt}_{\mathrm{trace}}/\mathrm{opt}\ge \mu\) holds exactly when at least one evaluated mask lies in \(\mathcal{G}_\mu\).

Let \(Q_{\theta_r}\) be the Gumbel-top-\(k\) sampling distribution used by TRACE in round \(r\), and define \[p_r^\mu = Q_{\theta_r}(\mathcal{G}_\mu). \label{eq:app-trace-round-hit-prob}\tag{20}\] Conditioned on the round-\(r\) sampling distribution, the probability that all \(M_{\mathrm{samp}}\) masks miss \(\mathcal{G}_\mu\) is \((1-p_r^\mu)^{M_{\mathrm{samp}}}\). Therefore, \[\Pr\left[ \frac{\mathrm{opt}_{\mathrm{trace}}}{\mathrm{opt}} \ge \mu \right] \ge 1- \prod_{r=0}^{R-1}(1-p_r^\mu)^{M_{\mathrm{samp}}}. \label{eq:app-trace-generic-hit-bound}\tag{21}\] This identity is correct but hides the attribution geometry inside \(p_r^\mu\). The PhaseWin-structured model makes this term more interpretable.

Assume, following the extended PhaseWin abstraction, that the fine regions admit a semantic block partition \[\mathcal{H}=\{H_1,\ldots,H_q\}, \qquad H_a\cap H_b=\emptyset\;(a\ne b), \qquad \bigcup_{j=1}^q H_j=U .\] For a mask \(S\), let \[\mathsf{B}(S) = \{j\in[q]: S\cap H_j\ne\emptyset\}\] be its activated block set. Following the PhaseWin extended model, the proxy has a dominant monotone block-level component plus a bounded nonnegative residual: \[F(S)=\Phi(\mathsf{B}(S))+\Delta(S), \qquad 0\le \Delta(S)\le |S|\epsilon_\Delta, \label{eq:app-phase-decomposition}\tag{22}\] where the monotonicity of \(\Phi\), namely \(J\subseteq J'\Rightarrow \Phi(J)\le\Phi(J')\), is the PhaseWin block-evidence monotonicity assumption rather than an additional assumption introduced by TRACE. Define the best block-level value attainable by at most \(k\) blocks: \[\Phi_k^\star = \max_{J\subseteq[q],\, |J|\le k}\Phi(J).\] Because an exactly-\(k\) mask activates at most \(k\) blocks, \[\mathrm{opt} \le \Phi_k^\star+k\epsilon_\Delta . \label{eq:app-opt-upper-phase}\tag{23}\]

Define the block-certificate family \[\mathcal{A}_\mu = \left\{ J\subseteq[q]: |J|\le k,\; \Phi(J)\ge \mu(\Phi_k^\star+k\epsilon_\Delta) \right\}. \label{eq:app-block-certificate-family}\tag{24}\] Every \(J\in\mathcal{A}_\mu\) certifies a \(\mu\)-near-optimal basin: if \(\mathsf{B}(S)\supseteq J\), then by monotonicity and Eq. 23 , \[F(S) \ge \Phi(\mathsf{B}(S)) \ge \Phi(J) \ge \mu(\Phi_k^\star+k\epsilon_\Delta) \ge \mu\,\mathrm{opt}.\] Hence \[\{S: \mathsf{B}(S)\supseteq J\} \subseteq \mathcal{G}_\mu . \label{eq:app-certificate-implies-good}\tag{25}\] This converts exact-mask recovery into semantic basin recovery.

Under the equivalent Plackett–Luce view of Gumbel-top-\(k\) sampling, let \[w_{r,i}=\exp(\theta_{r,i}/T), \qquad W_r=\sum_{i\in U}w_{r,i}, \qquad \eta_{r,j} = \frac{\sum_{i\in H_j}w_{r,i}}{W_r} \label{eq:app-block-mass}\tag{26}\] be the normalized mass assigned to semantic block \(H_j\) in round \(r\). For a certificate \(J\in\mathcal{A}_\mu\) with \(h=|J|\), a sufficient event for activating all blocks in \(J\) is that the first \(h\) sampled positions hit the \(h\) blocks in \(J\) in some order. Thus, \[Q_{\theta_r}\bigl(\mathsf{B}(S)\supseteq J\bigr) \ge h!\prod_{j\in J}\eta_{r,j}. \label{eq:app-prefix-block-bound}\tag{27}\] The events in Eq. 27 are disjoint across certificates of the same cardinality. A complementary all-\(k\) lower bound follows from a union bound over missing blocks: \[Q_{\theta_r}\bigl(\mathsf{B}(S)\supseteq J\bigr) \ge \left[ 1-\sum_{j\in J}(1-\eta_{r,j})^k \right]_+, \qquad [x]_+=\max\{x,0\}. \label{eq:app-union-block-bound}\tag{28}\] Let \(\mathcal{A}_{\mu,h}=\{J\in\mathcal{A}_\mu: |J|=h\}\). Combining Eqs. 25 –28 , define \[\underline p_r^\mu = \max \left\{ \max_{1\le h\le k} \sum_{J\in\mathcal{A}_{\mu,h}} h!\prod_{j\in J}\eta_{r,j}, \; \max_{J\in\mathcal{A}_\mu} \left[ 1-\sum_{j\in J}(1-\eta_{r,j})^k \right]_+ \right\}. \label{eq:app-structured-pr-lower}\tag{29}\] Then \[Q_{\theta_r}(\mathcal{G}_\mu) \ge \underline p_r^\mu.\] Substitution into Eq. 21 gives the phase-structured recovery guarantee: \[\Pr\left[ \frac{\mathrm{opt}_{\mathrm{trace}}}{\mathrm{opt}} \ge \mu \right] \ge 1- \prod_{r=0}^{R-1}(1-\underline p_r^\mu)^{M_{\mathrm{samp}}}. \label{eq:app-phase-structured-guarantee}\tag{30}\] This bound is more informative than a uniform exact-mask bound because it depends on semantic block-basin mass rather than only on the fraction of good masks inside the full \(\binom{n}{k}\) combinatorial space.

The cross-entropy update enters by increasing the block-basin mass across rounds. For a certificate \(J\in\mathcal{A}_\mu\), define \[\eta_{r,J}=\sum_{j\in J}\eta_{r,j}.\] Assume the update amplifies the odds of this basin: \[\frac{\eta_{r+1,J}}{1-\eta_{r+1,J}} \ge \lambda_{r,J} \frac{\eta_{r,J}}{1-\eta_{r,J}}, \qquad \lambda_{r,J}\ge 1. \label{eq:app-odds-amplification}\tag{31}\] With \[\Lambda_{r,J}=\prod_{\ell=0}^{r-1}\lambda_{\ell,J}, \qquad \Lambda_{0,J}=1,\] we obtain \[\eta_{r,J} \ge z_{r,J} := \frac{\Lambda_{r,J}\eta_{0,J}}{1-\eta_{0,J}+\Lambda_{r,J}\eta_{0,J}}. \label{eq:app-z-basin-mass}\tag{32}\] If the mass inside a certificate is not collapsed onto a single block, namely \[\eta_{r,j}\ge b_J\eta_{r,J}, \qquad \forall j\in J, \qquad 0<b_J\le |J|^{-1}, \label{eq:app-internal-balance}\tag{33}\] then, for \(h_J=|J|\), \[Q_{\theta_r}(\mathcal{G}_\mu) \ge \max \left\{ h_J! b_J^{h_J} z_{r,J}^{h_J}, \left[ 1-h_J(1-b_J z_{r,J})^k \right]_+ \right\}. \label{eq:app-balanced-certificate-bound}\tag{34}\] Consequently, \[\begin{align} \Pr\left[ \frac{\mathrm{opt}_{\mathrm{trace}}}{\mathrm{opt}} \ge \mu \right] \ge 1- \prod_{r=0}^{R-1} \Bigg( 1 - \max_{J\in\mathcal{A}_\mu} \max \Big\{ h_J! b_J^{h_J} z_{r,J}^{h_J}, \left[ 1-h_J(1-b_J z_{r,J})^k \right]_+ \Big\} \Bigg)^{M_{\mathrm{samp}}}. \end{align} \label{eq:app-ce-aware-guarantee}\tag{35}\] In the homogeneous case \(\lambda_{r,J}=\lambda>1\), \[z_{r,J} = \frac{\lambda^r\eta_{0,J}}{1-\eta_{0,J}+\lambda^r\eta_{0,J}}. \label{eq:app-homogeneous-z}\tag{36}\] Thus, under the PhaseWin-style block-basin model, the cross-entropy update improves the recovery probability by increasing the probability mass assigned to near-optimal semantic basins over successive rounds.

6.4.0.1 Numerical estimate.

For the setting used in the estimate, take \(R=5\), \(M_{\mathrm{samp}}=32\), total budget \(B_{\mathrm{eval}}=160\), and \(\mu=0.8\). If no cross-entropy improvement is assumed and \(p_r^{0.8}=p_0\) is fixed, then \[P_{\mathrm{hit}} = 1-(1-p_0)^{160}.\] Representative values are

With homogeneous cross-entropy odds amplification, \[p_r = \frac{\lambda^r p_0}{1-p_0+\lambda^r p_0}, \qquad P_{\mathrm{hit}} = 1-\prod_{r=0}^{4}(1-p_r)^{32}.\] For \(\lambda=1.5\), the same initial probabilities yield

For a block-basin interpretation, suppose the \(\mu=0.8\) certificate consists of \(h\) semantic blocks, its initial basin mass is \(\eta_0\), the amplification is \(\lambda=1.5\), and the certificate mass is approximately balanced across its blocks, \(b\approx 1/h\). Using the simplified lower bound \[h_r \approx h!b^h z_r^h, \qquad z_r= \frac{\lambda^r\eta_0}{1-\eta_0+\lambda^r\eta_0}, \qquad P_{\mathrm{hit}} \approx 1-\prod_{r=0}^{4}(1-h_r)^{32},\] we obtain

These estimates suggest that, under moderate cross-entropy amplification, five rounds with 32 samples per round are sufficient to obtain high recovery probability when the \(0.8\)-near-optimal basin is controlled by one or two dominant semantic blocks. A conservative operating estimate, \(p_0^{0.8}=0.5\%\) and \(\lambda=1.5\), gives \(P_{\mathrm{hit}}\approx 87.8\%\). A more favorable estimate, \(p_0^{0.8}=1.0\%\) and \(\lambda=1.5\), gives \(P_{\mathrm{hit}}\approx 98.5\%\). Without adaptive amplification, the same budget gives \(P_{\mathrm{hit}}\approx 55\%\)–\(80\%\) for \(p_0^{0.8}\in[0.5\%,1.0\%]\).

6.5 Notation for the Recovery Bound↩︎

7 Extended Attribution Background↩︎

This appendix expands the compact Related Work in Section 2. The goal is not to provide another short list of baselines, but to make explicit the historical shift behind our problem formulation: visual attribution has moved from producing visually plausible heatmaps, to testing evidence by perturbation, to modeling region-level coalitions and ordered subsets under the cost constraints of modern vision-language models. Following the terminology used throughout this paper, we refer to the LIMA/VPS/PhaseWin line as ordered subset search: these methods construct an ordering of image regions so that its prefixes can be replayed by insertion or deletion.

7.1 From Heatmaps to Evidence Search↩︎

The earliest visual-attribution interface is a saliency map: each pixel or region is assigned an importance score. This interface is intuitive, but a heatmap alone does not answer whether the highlighted evidence is sufficient for the model output. Faithful attribution therefore adds a behavioral test. If the most important regions are inserted first, the target response should recover quickly; if they are deleted first, the target response should drop quickly. RISE [1] made this insertion–deletion evaluation protocol central to black-box visual explanation, and the same operational view underlies later search-based methods.

The combinatorial nature of the problem is immediate. A pixel-level mask over \(N\) pixels has \(2^N\) possible retained subsets. Practical methods reduce this to a region set \(U=\{u_1,\ldots,u_n\}\) defined by superpixels, patches, proposals, or semantic masks, but the retained-subset family still has size \(2^n\). This reduction creates the main design axis in modern faithful attribution: should we infer independent region scores, estimate average coalition contribution, optimize a continuous mask, or search directly for high-value region subsets and prefixes?

7.2 Gradient and Activation Saliency↩︎

Gradient saliency starts from local sensitivity. Simonyan et al. [16] computed the target class score gradient with respect to the input image and used it as an image-specific saliency map. Zeiler and Fergus [17] developed DeconvNet visualizations and occlusion sensitivity to inspect CNN feature hierarchies from the complementary perspective of internal activation and localized input removal. Layer-wise Relevance Propagation [18] then framed explanation as redistributing the prediction score backward through the network to obtain pixel-level relevance. Guided Backpropagation, introduced through the all convolutional network analysis of Springenberg et al. [19], modified the backward ReLU signal to produce sharper edge-like maps. SmoothGrad [20] reduced visual noise by averaging saliency maps over noisy input copies, while Integrated Gradients [5] introduced an axiomatic path-integral attribution from a baseline input to the observed input.

Activation-map methods moved the saliency interface from input gradients to spatial feature maps. CAM [21] showed that CNNs with global average pooling can localize class-discriminative image regions from image-level supervision. Grad-CAM [4] generalized this idea by weighting convolutional feature maps with target gradients, making class-discriminative localization applicable to a broader range of architectures and tasks. Grad-CAM++ [22] improved multi-instance localization through a weighted combination of positive gradients, and Score-CAM [23] replaced gradient weights with forward-score weights over activation-map masks, partly bridging activation maps and perturbation testing.

The same gradient/activation logic was later adapted to new architectures and outputs. ViT-CX [24] argued that attention weights over ViT patches are not enough and instead modeled the causal effect of patch embeddings. Grad-ECLIP [25] adapted gradient explanation to transformer-based CLIP [10]. For object detectors, Spatial Sensitive Grad-CAM++ [26] extended Grad-CAM++ style weighting to detector-specific heatmaps, while ODAM [27] produced instance-specific detector activation maps from gradients of detection targets. For MLLMs, TAM [28] further changed the explanation unit from a single class score to generated tokens, explicitly addressing context interference among autoregressive tokens.

This line solves the speed problem. With white-box access, a small number of backward passes can produce a heatmap, making gradient and activation saliency useful for rapid inspection and model debugging. Its limitation is that local sensitivity and internal activation are not the same as evidence sufficiency. The sanity checks of Adebayo et al. [29] showed that visually appealing saliency maps can fail to reflect model parameters or data dependence. This is precisely why faithful attribution requires perturbation replay or subset search when the goal is to test what the model actually relies on.

7.3 Perturbation Testing and Black-Box Attribution↩︎

Perturbation methods treat attribution as an input-output experiment. LIME [30] samples local perturbations around an input, fits an interpretable surrogate model, and uses the surrogate coefficients as an explanation; in images, the interpretable units are usually superpixels. Meaningful Perturbation [31] optimized a mask that removes or blurs a small image region while reducing the target response, making explanation explicitly testable by editing the input. Extremal Perturbations [32] refined this idea with fixed-area constraints and smooth masks, turning perturbation analysis into a more controlled optimization problem.

RISE [1] took a simpler black-box route: sample many random binary masks, evaluate the target score under each masked image, and aggregate the masks weighted by their scores. D-RISE [33] extended the same idea to object detectors by defining a detection-similarity score that combines classification and localization behavior. HSIC Attribution [34] then used a dependence measure to estimate input-output relationships more efficiently than plain random-mask averaging.

These methods are closer to faithful attribution than pure gradients because they measure model behavior under retained or removed evidence. They also make black-box explanation possible. Their remaining weakness is the output contract: random masks, optimized continuous masks, or local surrogate coefficients usually collapse into a per-region saliency score. That score can be replayed by insertion or deletion, but it was not necessarily learned to optimize the insertion prefix itself.

7.4 Shapley-Style Region Contribution↩︎

Shapley value [35] provides a principled way to assign average coalition contribution to players. In visual attribution, the players can be superpixels, patches, object proposals, or semantic masks, and the coalition value is a model score \(G(S)\) under a retained region set \(S\). SHAP [36] made Shapley-style additive feature attribution a standard model-explanation framework. Compared with one-region occlusion or local gradients, this view explicitly recognizes that an image region may matter differently depending on which other regions are present.

The cost and semantics of Shapley-style explanation are also important. Exact Shapley values require averaging over exponentially many coalitions, so image applications rely on sampling or approximations. Kumar et al. [37] further argued that Shapley-based feature importance has nontrivial mathematical and semantic limits, especially when feature dependence and causal interpretation matter. Nevertheless, Shapley-style ideas have shaped region-level visual diagnosis: Explain to Fix [38] used approximate Shapley feature importance to interpret and correct object detector failures, and Explain Any Concept [39] combined SAM-style concept regions with concept-based explanation, reflecting a broader shift from raw pixels to semantically meaningful attribution units.

For insertion and deletion, however, average coalition contribution is not identical to the best early prefix. A region may have strong average contribution but be redundant with another early region; conversely, a region may only become decisive in a specific combination. This gap motivates ordered subset search.

7.5 Ordered Subset Search↩︎

Ordered subset search directly optimizes the object that insertion and deletion replay. For an ordering \(\pi\), define \(P_t^\pi=\{\pi_1,\ldots,\pi_t\}\). Instead of first estimating a static saliency score for each region, a search method chooses regions so that the prefix response \(G(P_t^\pi)\) recovers quickly for small \(t\). LIMA/Greedy [2] follows this principle by repeatedly selecting the remaining region with the largest marginal gain. Its strength is that each decision is made in the context of the prefix already chosen; its weakness is the quadratic scan cost \(n+(n-1)+\cdots+1=O(n^2)\).

VPS [3] extended search-based attribution to object-level foundation models, where the explained target may be a detection or grounding output rather than a classification logit. PhaseWin [7] made ordered subset search more scalable by reusing phase-wise structure instead of rescoring every remaining region after every accepted step. Its extended analysis [8] is especially relevant to this paper: the residual gap to Greedy concentrates on partition-sensitive tail cases, suggesting that early prefix quality and region granularity remain central even when the search algorithm is efficient.

This is the immediate predecessor line of our work. It establishes that perturbation replay and ordered search can outperform map-based attribution when the evaluation metric is insertion/deletion faithfulness. Our departure is the output object. Many applications do not need a complete ordering of all \(n\) regions; they need the top \(k\) decisive regions as a compact evidence mask. TRACE therefore treats the fixed-cardinality mask itself as the primary object, and uses it as an initialized prefix only when a downstream benchmark demands a full ordering.

7.6 Attribution in Multimodal Foundation Models↩︎

The cost and target definition of attribution change sharply in modern multimodal models. Vision backbones moved from CNNs such as ResNet [11] to ViTs [41] and CLIP-style language-supervised encoders [10]. Multimodal systems such as LLaVA [15], [42], BLIP-2 [43], Grounding DINO [44], Florence-2 [45], and Qwen2.5-VL [14] further change the scoring problem: a candidate mask may have to be evaluated through a visual encoder, multimodal fusion, region localization, prompt-conditioned decoding, and autoregressive language generation.

This shift affects both access and semantics. Many high-performing MLLMs expose only a forward interface, making black-box perturbation more realistic than gradient methods. Even when gradients are available, the target response is not a single class logit: captioning, VQA, grounding, and hallucination repair involve token probabilities, generated strings, object boxes, or corrected answers. Recent MLLM explanation work reflects this change. MLLMs Know Where to Look [46] studied small visual-detail perception and attention/gradient-based visual intervention. Where do Large Vision-Language Models Look [47] extended heatmap analysis to open-ended LVLM question answering. TAM [28] treated token-level MLLM activation as the attribution target, while LLaVA-CAM [48] and IGOS++ [49] provide strong non-search references in our MLLM experiments.

EAGLE [6] is the closest MLLM-side search protocol to our setting: it adapts greedy region search to autoregressive generation and evaluates both attribution and repair. POPE [12] and RePOPE [13] provide the object-hallucination and corrected adversarial settings in which visual evidence can be tested by decision faithfulness or repair. In this regime, the central question is no longer whether we can draw a heatmap. The question is whether we can find a compact visual evidence set that survives behavioral testing under an acceptable number of expensive multimodal model evaluations.

7.7 Summary↩︎

The development history can be summarized as a sequence of increasingly behavioral and combinatorial formulations: \[\begin{align} &\text{gradient saliency} \rightarrow \text{activation maps} \rightarrow \text{perturbation testing} \rightarrow \text{coalition contribution} \\ &\rightarrow \text{ordered subset search} \rightarrow \text{compact evidence search for MLLMs}. \end{align}\] Gradient and activation methods solve the efficiency problem but rely on internal signals. Perturbation and Shapley-style methods test model behavior but often return independent scores or average contributions. Ordered subset search aligns directly with insertion/deletion replay but can be expensive when \(n\) is large. TRACE is positioned at the next step: it keeps the black-box behavioral test, but makes the compact top-\(k\) evidence mask the primary output, which is the object many classification, hallucination attribution, and repair applications actually need.

8 Runtime and Implementation Details↩︎

The main text contains the experimental setup, task definitions, metrics, and MEC accounting convention. Full numerical tables are reported in Appendix 9, and supplementary qualitative examples are included in Section 9.4. This appendix records the additional implementation details needed to reproduce the ablation suite and the MLLM runtime profiling.

8.1 Initializer Hyperparameters and Release Convention↩︎

All main experiments use SLICO-64 fine regions. The target response \(f_y(x)\) is normalized to \([0,1]\), and the initializer optimization score is the sufficiency proxy \(F(S)=\operatorname{Suff}(S)=f_y(x_S)\) unless explicitly stated otherwise. Both CoPAIR and TRACE use the same internal fine-region ordering and release convention: the selected seed candidate is internally ordered by greedy marginal rescoring, and only the shortest prefix reaching \(0.8\) of the candidate score is kept as the initialized prefix. The remaining candidate regions are released to the continuation pool.

For CoPAIR, let \(m=|U|\) be the number of fine regions and \(c\) be the number of coarse centroid clusters. When no explicit pair-pool size is given, the candidate pair pool is derived from the pool fraction, minimum size, and reserve: \[q = \min\left\{ c,\, \max\left(q_{\min},\left\lceil \rho_{\mathrm{pool}}c\right\rceil\right) +q_{\mathrm{res}} \right\}.\] The main CoPAIR settings are listed in Table 6.

The area cap and the SLICO-64 setting keep the selected fine-region seed below the internal ordering threshold in the main experiments, so the internal ordering is exact greedy within the selected seed candidate. If the selected coarse singleton or pair does not reach the minimum sufficiency threshold, CoPAIR may absorb a third coarse region by greedy sufficiency improvement, subject to the maximum selected coarse-region and area-fraction limits.

The main TRACE settings are listed in Table 7. TRACE uses Gumbel-top-\(k\) sampling over exactly-\(k\) fine-region masks. The direct-mask output is the best observed exactly-\(k\) mask. When TRACE is used as an initializer for full-ordering search, this mask is internally ordered and partially released using the same \(0.8\) rule as CoPAIR.

Duplicate sampled masks are cached by their sorted region-index tuple. Cached duplicates reuse the stored score and do not issue additional model forwards. The MEC values for initialized rows include the uncached initializer calls and the downstream continuation calls.

8.2 Ablation Suite Setup↩︎

The ablations in Appendix 9.1 are run on 100 samples drawn from the first 2,000 correctly classified CLIP ViT-L/14 samples. All images use SLICO-64 regions [9]. We report insertion AUC, deletion AUC, insertion scores at 30% and 50% region budgets, the best insertion score along the curve, and MEC. In this ablation suite, MEC is reported as the raw forward-call count from the logs, not divided by \(1000\). It includes selection, filtering, and initialization cost, but excludes the later insertion/deletion replay used only for evaluation. The ablation jobs were run with 8 shards, and scores are rounded to four decimals while MEC is rounded to two decimals.

8.3 Ablated Initializers↩︎

The standard TRACE ablation setting is \(\mathrm{\small TRACE}(k=8,M=32,R=5)+\)Greedy. The TRACE initializer uses sufficiency scoring, Gumbel-top-\(k\) sampling with temperature \(1.0\), elite ratio \(0.2\), EMA update rate \(\eta=0.7\), smoothing \(0.05\), logit clipping \(8.0\), and random seed \(0\). After the final round, the best sampled set is used as the seed set for the downstream Greedy ordering; selected regions are placed first and the remaining regions are ranked by the learned logits before continuation.

CoPAIR uses centroid coarsening. When the target coarse-region count is set to \(0\), it is resolved adaptively from the fine-region count with minimum 8, maximum 32, and scale \(2.0\). Coarse seed candidates are selected by sufficiency. The seed pool uses a 0.15 top-group fraction with minimum size 10. The default thresholds are minimum initial sufficiency \(0.1\), pair minimum gain \(0.05\), maximum initial fraction \(0.2\), and partial-release ratio \(0.8\). After the initial coarse seed is chosen, the selected fine regions are partially ordered and released according to the same initialization interface used in Section 3.2.

8.4 Memory-Saving Settings for Runtime Profiling↩︎

For the timing and memory results in Table 4, LLaVA-CAM and IGOS++ were deployed on an RTX 5090 using memory-saving settings to make the comparison easy to reproduce on widely available hardware. The original, uncompressed peak-memory measurements reported outside the parentheses were run on an RTX PRO 6000. The parenthesized engineered measurements were obtained on the 5090 with the following settings.

• Profiling isolation. We used score_batch_size=1, one profiling process per method/sample stream, and PYTORCH_CUDA_ALLOC_CONF=``expandable_segments:True. Before each measured method call, the profiler ran Python garbage collection, torch.cuda.empty_cache(), CUDA synchronization, and peak-memory reset, so the reported peak corresponds to the current method execution under the already loaded model.

• Common forward settings. All scoring, generation, and gradient-attribution forward passes used use_cache=False, so KV-cache memory was not retained during attribution. The segmentation and search configuration was fixed to SLICO-64 with target_length=64.

• Qwen2.5-VL-3B. We used bfloat16, FlashAttention-2 when available, and image-size caps of max image side 448, min pixels 3136, and max pixels 401408.

• LLaVA-v1.5-7B. We used float16, FlashAttention-2 when available, frozen model parameters via requires_grad_(False), gradient checkpointing, model.config.use_cache=False, and image-size caps of max image side 336, min pixels 3136, and max pixels 200704. These LLaVA-specific settings are the memory-saving changes that allowed LLaVA-CAM and IGOS++ to run on the 5090.

9 Additional Results and Ablations↩︎

This appendix provides the detailed tables that support the compact presentation in Section 4. We first report a focused ablation suite on CLIP ViT-L/14 Correct samples with SLICO-64 regions. This subset is intended for method-design questions, not for claiming the final leaderboard. We then report additional metrics for the remaining classification backbones, full MLLM attribution metrics, and the full repair protocol results. Implementation and cost-accounting details are reported in Appendix 8; qualitative examples are included in Section 9.4.

9.1 CLIP ViT-L/14 Correct-100 Ablation Suite↩︎

All ablations in this subsection use the same 100-sample subset drawn from correctly classified CLIP ViT-L/14 samples. The purpose is to isolate method-design choices under a small, reproducible evaluation budget before running full-scale tables. Unless otherwise stated, metrics follow the ordered-attribution setup in Section 4.2: InsAUC is the primary faithfulness metric for Correct, DelAUC and High are secondary, and MEC is the raw selection/filter/initializer call count excluding curve replay.

9.1.1 Initializer Comparison↩︎

Table 8 compares raw Greedy, random fixed-size seeds, relaxed ASN seeds, CoPAIR, and the standard \(\mathrm{\small TRACE}(k=8,M=32,R=5)+\)Greedy configuration. TRACE gives the best InsAUC, @30, @50, and High values. CoPAIR is the strongest non-TRACE initializer and substantially improves over Greedy. Random and ASN seeds reduce MEC but do not improve insertion faithfulness, indicating that the gain is not explained by simply shortening the continuation problem.

The ASN rows are included as a targeted negative control for traditional relaxed-mask initialization. ASN optimizes continuous region variables under a combined sufficiency and necessity objective, \[\operatorname{SN} = \alpha\,\operatorname{Suff} + (1-\alpha)\,\operatorname{Necc},\] then hardens the relaxed mask into a seed for Greedy. We test a fixed top-10 rule, an SN-knee rule over sizes 5–16, and an SN-plateau rule over the same range. All three use dark_defocus perturbations, topk_suff objective, \(\gamma_s=\gamma_n=0.8\), score margin, 25 optimization steps, area budget \(0.6\), \(\mu=0.01\), \(\nu=0.05\), and \(\lambda_{\mathrm{area}}=0.0\). Their weaker InsAUC shows that a conventional relaxed mask, even when converted into a Greedy seed, does not substitute for discrete fixed-\(k\) TRACE search.

3.5pt

9.1.2 TRACE Sampling Budget↩︎

Table 9 varies the number of sampled masks per round and the number of cross-entropy rounds. Increasing samples from 8 to 32 gives a clear InsAUC gain. Increasing to 64 gives only a small additional gain while increasing MEC. For rounds, moving from 1 to 5 improves InsAUC, while 8 rounds yields nearly the same quality as larger sampling budgets at additional cost. The \(M=32,R=5\) configuration is therefore used as the balanced default.

4pt

9.1.3 TRACE Mask Size↩︎

Table 10 varies the fixed mask size \(k\). The default \(k=8\) gives the best InsAUC, @50, and High values. Smaller masks are close but slightly weaker; larger masks reduce MEC because more regions are initialized before continuation, but they also reduce InsAUC. This supports treating \(k\) as an output contract rather than a free cost-reduction knob.

4pt

9.1.4 Mask-Size Overlap↩︎

Table 11 compares the selected regions across different \(k\) values. For example, top4_of_k6_vs_k4 measures the overlap between the top four regions from a \(k=6\) run and the selected \(k=4\) mask. The overlaps are moderate rather than near-identical, so changing \(k\) does not merely append extra regions to a stable core set; it can change the seed composition.

8pt

9.2 CLIP RN101 Fixed-\(k\) Extension↩︎

The CLIP RN101 block in Table 2 is the main case where CoPAIR+Greedy is slightly stronger than the default \(\mathrm{\small TRACE}(k=8)+\)Greedy configuration. We attribute this to the convolutional ResNet visual encoder: compared with ViT patch tokens, RN101 features more readily align broad spatial regions with the CLIP semantic space. This makes insertion curves partly redundant and weakens the insertion/deletion agreement of a small fixed-size seed. To test whether this is a failure of TRACE or a mismatch in the output cardinality, we reran the CLIP RN101 comparison with larger TRACE masks. All TRACE rows use the same inner partial-greedy completion before the backend Greedy continuation, and we abbreviate this pipeline as \(\mathrm{\small TRACE}(k)+\)Greedy.

Table 12 shows that increasing \(k\) consistently improves deletion behavior and reduces MEC relative to \(k=8\). On Cause and Repair, \(k=16\) already exceeds CoPAIR+Greedy on the primary metric for the split (InsAUC for Cause and High for Repair). Correct remains harder because its positive evidence often covers larger semantic regions: CoPAIR still has the best InsAUC, while larger TRACE masks improve DelAUC, High, and cost. The Correct-only \(k=12,16,20\) sweep also matches the trend in Table 10: larger fixed masks shorten the remaining Greedy continuation and lower MEC, without making TRACE collapse as the number of selected regions grows.

2.5pt

9.3 Full Classification Tables for Additional Backbones↩︎

Tables 13 and 14 report the full classification metrics for CLIP ResNet-101 and supervised ResNet-101. Correct and Cause are interpreted primarily through InsAUC, while Repair is interpreted primarily through Highest.

2pt

2pt

9.4 Additional CLIP RN101 Visualizations↩︎

Figure 6 provides representative CLIP RN101 Correct-split cases corresponding to the CLIP RN101 block in Table 2, the full metrics in Table 13, and the larger-mask check in Table 12. These examples mirror the CLIP ViT-L/14 qualitative analysis in Figure 4.

9.5 Full MLLM Attribution Metrics↩︎

Tables 15 and 16 report the full POPE and RePOPE attribution metrics for the two MLLMs. Forward calls are reported only for forward-only methods; backward and optimization-based methods are marked with “–” in the cost column.

3pt

3pt

9.6 Full EAGLE Repair Protocol Results↩︎

Table 17 reports the full keep-prefix repair results under the protocol from Where MLLMs Attend and What They Rely On: Explaining Autoregressive Token Generation. AMCR and CSR@10 are defined only for ordered trajectories. Direct CoPAIR/TRACE masks are therefore reported only by repair rate, failed sample count, and MEC where available.

3pt

References↩︎