PhaseWin: An Efficient Search Algorithm for Faithful Visual Attribution
作者: Zihan Gu, Ruoyu Chen, Junchi Zhang, Li Liu, Xiaochun Cao, Hua Zhang
分类: cs.CV
发布日期: 2026-06-16
备注: 26 pages, 29 figures
🔗 代码/项目: GITHUB
💡 一句话要点
提出PhaseWin以解决视觉归因中的高计算成本问题
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 视觉归因 高效搜索 贪婪算法 模型解释 计算复杂度
📋 核心要点
- 现有的视觉归因方法在处理图像区域时，计算成本高且效率低，尤其是穷举搜索和贪婪搜索方法。
- 本文提出PhaseWin，通过阶段性窗口搜索程序优化贪婪区域选择，减少了模型评估的次数。
- 实验表明，PhaseWin在图像分类、目标检测等任务中实现了高忠实度，前向传递次数显著减少。
📝 摘要（中文）
视觉归因是解释现代视觉和视觉-语言模型的重要工具，旨在通过对图像局部区域的重要性排序来解释模型决策。现有的穷举搜索方法计算成本高，而广泛使用的贪婪搜索仍需进行大量模型评估。为此，本文提出PhaseWin，一种高效的子集搜索算法，通过阶段性窗口搜索程序重组贪婪区域选择，避免每一步都重新评估所有候选区域。我们在单调证据累积条件下分析PhaseWin，证明其在特征级结构假设下可实现可控的线性评估复杂度，并提供接近贪婪的忠实性保证。实验结果表明，PhaseWin在多个任务中以最少的前向传递实现了高忠实度，验证了从O(n²)到O(n)的复杂度降低。
🔬 方法详解
问题定义：本文旨在解决视觉归因中的高计算成本问题，现有方法如穷举搜索和贪婪搜索在效率上存在明显不足，尤其是在需要大量模型评估的情况下。
核心思路：PhaseWin通过重组贪婪区域选择为阶段性窗口搜索程序，避免每一步都重新评估所有候选区域，从而提高效率。该方法在全局候选筛选、适应性修剪和局部窗口细化之间交替进行，保持贪婪搜索的区域排名特性。
技术框架：PhaseWin的整体架构包括三个主要模块：全局候选筛选、适应性修剪和局部窗口细化。首先进行全局筛选以减少候选区域，然后通过适应性修剪进一步缩小范围，最后在局部窗口中进行精细化选择。
关键创新：PhaseWin的核心创新在于其阶段性窗口搜索程序，显著降低了计算复杂度，从O(n²)减少到O(n)，同时保持了接近贪婪的忠实性保证。
关键设计：在设计中，PhaseWin采用了特征级结构假设，以确保在不同阶段的选择中能够有效地进行区域评估和排名。
🖼️ 关键图片
📊 实验亮点
实验结果显示，PhaseWin在图像分类、目标检测、视觉定位和图像描述等任务中，达到了最高的忠实度，同时前向传递次数显著减少，验证了其从O(n²)到O(n)的复杂度降低，展现了优越的性能。
🎯 应用场景
PhaseWin在视觉归因领域具有广泛的应用潜力，尤其是在需要解释模型决策的场景，如图像分类、目标检测和视觉问答等。其高效的计算性能和高忠实度使其在实际应用中具备重要价值，能够帮助研究人员和工程师更好地理解和优化模型。
📄 摘要（原文）
Visual attribution is a fundamental tool for interpreting modern vision and vision-language models, particularly when their decisions must be inspected, diagnosed, or audited. Its goal is to explain how a model's decision depends on local regions of the visual input, typically by assigning an importance ordering over candidate image regions. Given an image partitioned into $n$ regions, faithful attribution can be cast as an ordered subset-search problem, in which progressively inserting the selected regions should recover the target model response as early as possible. Exhaustive search over region subsets incurs exponential cost, while the widely used greedy search still requires a quadratic number of model evaluations, because every selection step rescores all remaining candidates. We propose PhaseWin, an efficient subset-search algorithm for faithful visual attribution. PhaseWin reorganizes greedy region selection into a phased window-search procedure: rather than re-evaluating the full candidate set at every step, it alternates between global candidate screening, adaptive pruning, and localized window refinement, while preserving the essential region-ranking behavior of greedy search. We analyze PhaseWin under monotone evidence-accumulation conditions and show that, under feature-level structural assumptions, it attains controllable linear evaluation complexity together with near-greedy faithfulness guarantees. Extensive experiments on image classification, object detection, visual grounding, and image captioning show that, among all compared attribution methods, PhaseWin reaches high faithfulness with the fewest forward passes, empirically realizing the predicted reduction from $O(n^2)$ to $O(n)$. The code is available at https://github.com/Qihuai27/phasewin-va.