Generalized Priority-Aware Shapley Value¶

会议: NeurIPS 2026
arXiv: 2605.15018
代码: https://github.com/KiljaeL/GPASV
领域: 可解释性
关键词: 优先级感知Shapley值、循环偏好图、随机序值、数据估值、LLM集成评测

一句话总结¶

针对传统优先级感知Shapley值强制依赖二元无环DAG的问题，本文提出广义优先级感知Shapley值（GPASV），通过有向加权图对排列冲突施加可调软惩罚并融合个体软优先级，成功将合作博弈估值拓展至包含循环与置信强度的现实场景。

研究背景与动机¶

Shapley值作为机器学习中进行数据贡献度评估、特征归因和模型组件赋权的核心工具，其公理化基础牢固且模型无关。然而，其赖以立足的对称性公理在现实应用中常常遭遇“抄袭者攻击”：当一个参与者通过简单复制另一个参与者的成果来瓜分收益时，对称性会无差别地给予两者完全相同的报酬。为了保护原创性并融入数据谱系、因果前序或提供商信任度等先验结构，近期研究相继提出了序约束Shapley值（PSV）、加权Shapley值（WSV）以及结合了两者的优先级感知Shapley值（PASV）。

然而，这一系列工作均严格依赖于一个核心假设：参与者之间的成对优先级必须构成一个二元有向无环图（DAG）。这一假设包含两个硬性限制：图内部绝对禁止存在环结构，且成对偏好的强度被粗暴地二值化为“必须前置”或“毫无约束”。在现代人工智能场景中，这种假设被普遍违背。例如在基于人类偏好的大语言模型评测中，众所周知的孔多塞循环（Condorcet cycles，如模型 $i$ 胜过 $j$、$j$ 胜过 $k$、但 $k$ 胜过 $i$）在群体偏好聚合后频繁且不可避免地出现；同时，对战胜率、Bradley-Terry对数几率差或Elo积分本身蕴含了置信强弱，若强行二值化为绝对禁止边，不仅丢失了权重幅度，还会对微小的数据扰动极其敏感。

本文的核心思路是放弃将成对优先级作为不可逾越的硬约束，转而在全部排列空间上统计每种排列对优先级图的总违规惩罚，进而以Gibbs风格的衰减权重进行软约束加权。核心 idea：将硬约束DAG推广至任意有向加权图，通过违规惩罚指数加权与两阶段Softmax构造广义优先级感知分布，统一兼容循环偏好、加权优先级与个体软权重，并基于局部交换MCMC与偏好扫描实现可扩展的高效估值。

方法详解¶

整体框架¶

GPASV的整体流程从输入的联盟效用函数 $U$、成对有向加权优先级图矩阵 $\omega$ 以及个体软优先级向量 $\lambda$ 出发。方法首先在全排列空间 $\Pi$ 上建立一个平滑惩罚违规项的逆序概率分布 $p^{(\lambda, \omega)}$；随后通过具有局部状态抵消性质的相邻对换Metropolis-Hastings（MH）采样器生成排列样本；最后利用直接蒙特卡洛或代理回归模型对各参与者的边际贡献进行期望聚合。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据<br/>联盟效用 U, 加权优先图 ω, 软权重 λ"] --> B["阶段1：有向加权惩罚建模<br/>统计排列总违规代价 V_ω(π) 与阶段代价"]
    B --> C["阶段2：广义状态-选择分布分解<br/>结合软优先级 λ 构造逆序生成分布 p^(λ,ω)"]
    C --> D["阶段3：贪心初始化与局部MH采样<br/>逆序逐位贪心快启动 + 相邻对换MCMC高效采样"]
    D --> E["阶段4：子集缓存与SNIS加速估值<br/>复用已评估子集效用 + 重要性采样跨温度扫描"]
    E --> F["输出：各参与者GPASV公理化归因值"]

关键设计¶

1. 有向加权图违规惩罚与广义分布分解：将硬性DAG约束软化为连续惩罚 传统PASV通过指示函数 $\mathbbm{1}_{[\pi \in \Pi^G]}$ 严格排除任何违反DAG拓扑序的排列，导致其面对循环图时可行排列集合为空。GPASV首先定义非负加权有向图矩阵 $(\omega_{ij})_{i,j\in[n], i\neq j}$，其中 $\omega_{ij} \geq 0$ 显式表示参与者 $i$ 应当先于 $j$ 的证据强度。对于排列 $\pi$，总违规代价定义为所有逆序边的权重和： $$V_\omega(\pi) := \sum_{i\neq j} \omega_{ij} \cdot \mathbbm{1}_{[j\text{ 出现在 }i\text{ 之前}]}$$ 当无个体软偏好（$\lambda_i \equiv 1$）时，排列分布服从Gibbs形式 $p_\beta^\omega(\pi) \propto \exp\{-\beta \cdot V_\omega(\pi)\}$，其中 $\beta \ge 0$ 为惩罚温度。为了将个体软优先级 $\lambda$ 阶段化融入，GPASV定义前缀集合 $S_t := \{\pi_1, \dots, \pi_t\}$ 下将参与者 $k$ 置于位置 $t$ 所引发的阶段违规成本 $V_\omega(k; S_t) := \sum_{j\in S_t} \omega_{kj}$。GPASV的完备概率密度定义为： $$p^{(\lambda,\omega)}(\pi) \propto \prod_{t=1}^{n}\left[\frac{\lambda_{\pi_{t}}\exp\{-\beta\cdot V_{\omega}(\pi_{t};S_{t})\}}{\sum_{k\in S_{t}}\lambda_{k}\exp\{-\beta\cdot V_{\omega}(k;S_{t})\}} \cdot \sum_{k\in S_{t}}\exp\{-\beta\cdot V_{\omega}(k;S_{t})\}\right]$$ 式中Part 1为连续打折后的软选择因子，Part 2为状态重缩放因子，不仅严格保证了广义状态-选择因子分解（GSCF）公理，而且在 $\beta \to \infty$ 且图无环时无缝退化为经典PASV。

2. 贪心逆序初始化与局部相邻对换MH采样：克服循环图无法拓扑排序的冷启动难题 在一般有向图或循环图中，由于不存在拓扑排序或合法线性扩展，MCMC链如果从均匀随机排列冷启动，需要极其漫长的预烧（burn-in）期才能漂移到低违规的高概率区域。GPASV基于选择因子的结构特性，提出了自后向前的贪心初始化策略：初始化剩余集合 $R = [n]$，在每一步 $t = n, n-1, \dots, 1$ 中，按局部权重 $w(i; R) \propto \lambda_i \exp\{-\beta \sum_{j\in R} \omega_{ij}\}$ 采样候选人置于当前最右端位置并从 $R$ 中剔除。这使得链条天然从极小化局部违规状态出发。在采样迭代过程中，算法采用对称的相邻元素对换提议。对于排列 $\pi$ 与对换相邻位置 $(i, i+1)$ 元素 $(a, b)$ 后的 $\pi'$，作者从理论上证明了绝大多数全局项均被对消，转移接受率简化为仅依赖于局部邻域的极简比值： $$\frac{p^{(\lambda,\omega)}(\pi')}{p^{(\lambda,\omega)}(\pi)} = \exp\{-\beta(\omega_{ab} - \omega_{ba})\} \cdot \frac{\zeta_{\lambda,\omega}(S_i)}{\zeta_{\lambda,\omega}(S_i')}$$ 其中 $\zeta_{\lambda,\omega}(S) := \frac{\sum_{k\in S}\lambda_k \exp\{-\beta V_\omega(k;S)\}}{\sum_{k\in S}\exp\{-\beta V_\omega(k;S)\}}$，这一高度局部化的形式彻底免除了全排列重新扫描的沉重代价。

3. 子集效用缓存与自归一化重要性采样（SNIS）：压降黑盒效用调用的计算瓶颈 在许多下游任务中（如LLM集成评测），评估黑盒效用 $U(S)$ 的开销远远超过排列采样本身。GPASV通过两项机制实现了实质性的计算复用： - 前缀子集全局缓存：相邻对换每次仅微调局部前缀，大量排列在MCMC步进中共享相同的初始段或子集。算法建立全局字典缓存 $U(S)$，确保任何子集仅需评估一次即可永久复用； - 跨扫描轨迹的SNIS复用：在评估敏感性与超参数扫描时，目标分布沿 $(\alpha, \beta)$ 轨迹平滑变化。算法无须在每个参数点重新运行全量采样，而是利用未归一化密度之比计算重要性权重 $w^{(m)} = \widetilde{p}'(\pi^{(m)}) / \widetilde{p}(\pi^{(m)})$，通过自归一化重要性采样估计新参数下的值： $$\widehat{\psi}_i^{\mathrm{SNIS}}(U) := \frac{\sum_{m=1}^N w^{(m)} \Delta_i(\pi^{(m)}; U)}{\sum_{m=1}^N w^{(m)}}$$ 同时动态监控有效样本量 $\mathrm{ESS} = (\sum w^{(m)})^2 / \sum (w^{(m)})^2$。只有当有效样本量不足时，才按差额补充采样新的独立排列，从而大幅削减了多参数网格扫描的重复开销。

损失函数 / 训练策略¶

作为公理化博弈论归因方法，GPASV本身无需网络参数反向传播，其计算流程主要由MCMC链的采样与重要性再加权驱动。在超参数扫描中，软优先级通过指数温度调节：$\lambda_i = \exp\{-\alpha z_i\}$（$z_i$ 为参与者属性指示，$\alpha \ge 0$），硬优先级强度由 $\beta \ge 0$ 控制。在大型应用（如LLM评估）中，MCMC设置预烧期为 $10^5$ 步，抽样间隔（thinning）为 $10^3$ 步；而在敏感性分析中，每个新参数节点若满足 $\mathrm{ESS} \ge 500$ 则优先复用已有排列池，不足部分增量采样至 $N_{\mathrm{MC}} = 1000$。

实验关键数据¶

主实验¶

为了验证GPASV在大规模博弈估值中的有效性，论文在合成基准游戏（包含理论解析解的线型DAG场景Scenario 1与包含局部循环块的Scenario 2）以及真实的Chatbot Arena人类循环偏好图与MT-Bench评测基准上进行了全面测试。

在合成场景（Scenario 1线型DAG与Scenario 2循环块DAG，Case 2强优先级设定下），论文比较了直接置换蒙特卡洛（Permutation）、线性代理辅助（Linear Surrogate）与二次代理辅助（Quadratic Surrogate）在匹配效用预算下的非效用计算运行耗时与训练内存：

参与者数 $n$	Permutation 耗时 (s)	Linear 耗时 (s)	Linear 内存 (GB)	Quadratic 耗时 (s)	Quadratic 内存 (GB)
64 (Scen. 1)	4.94 (0.01)	26.51 (0.15)	0.001 (0.000)	26.49 (0.10)	0.002 (0.000)
64 (Scen. 2)	4.69 (0.02)	35.50 (0.38)	0.093 (0.000)	36.08 (0.24)	0.290 (0.001)
128 (Scen. 1)	8.53 (0.02)	46.72 (0.19)	0.002 (0.000)	46.89 (0.26)	0.012 (0.000)
128 (Scen. 2)	8.15 (0.04)	61.27 (0.28)	0.194 (0.000)	63.95 (0.22)	0.986 (0.003)
256 (Scen. 1)	15.94 (0.03)	91.73 (0.17)	0.009 (0.000)	92.30 (0.28)	0.081 (0.001)
256 (Scen. 2)	15.99 (0.07)	120.17 (0.39)	0.592 (0.000)	138.65 (0.88)	5.620 (0.008)
512 (Scen. 1)	36.45 (0.16)	191.07 (0.65)	0.031 (0.000)	194.82 (0.74)	0.566 (0.006)
512 (Scen. 2)	34.36 (0.06)	231.47 (1.18)	1.158 (0.001)	317.75 (3.33)	21.000 (0.027)
1024 (Scen. 1)	195.76 (2.46)	663.81 (6.91)	0.106 (0.001)	700.01 (6.31)	3.724 (0.031)
1024 (Scen. 2)	205.55 (0.51)	725.34 (4.64)	2.312 (0.002)	1378.02 (9.58)	108.276 (0.155)

消融实验¶

在包含20个真实LLM的Chatbot Arena人类偏好图与MT-Bench效用评测中，针对跨参数扫描开销，作者消融了子集效用缓存机制（Cache）与重要性排列复用（SNIS）对真实计算量的缩减效果：

实验场景配置	子集缓存 (Cache)	排列复用 (SNIS)	全流程需采样排列总数	每Prompt评估独立子集数
A. 无任何复用 (Naive)	✗	✗	19,000	380,000
B. 仅启用子集缓存	✓	✗	19,000	78,220
C. 仅启用排列复用 (SNIS)	✗	✓	15,840	316,800
D. 完整方案 (Cache + SNIS)	✓	✓	15,840	70,511

在此实际任务中，完整方案将需要调用的独立效用子集评估数从380,000大幅削减至70,511，带来了 5.4× 的实际计算量压缩，在SNIS扫描中总共节省了3,160个新鲜排列的昂贵生成开销。

关键发现¶

优先级权衡的主导效应（$\alpha$ vs $\beta$）：在无先验的基准点 $(\alpha, \beta) = (0,0)$ 下，传统Shapley值完全由效用驱动，5款付费API模型包揽前4名（GPT-4以1.26领跑）。当单独增加图偏好惩罚 $\beta$ 时，归因值高度极化聚敛于图中心枢纽（$\beta=32$ 时 GPT-4 单独冲至 6.85，占主导地位）；而一旦开启对开源模型的软偏好 $\alpha$，开源模型普遍获得乘性抬升，并在联合扫描 $\alpha=\beta$ 路径上全面压制图先验，使开源模型（如Guanaco-33B跃升至3.98，GPT-4跌至1.05）。
软约束放大了个体权重的调节灵敏度：相比于经典PASV因硬性DAG拓扑序限制而导致 $\lambda$ 仅能在极窄的线性扩展子空间内微调，GPASV软化了冲突惩罚，允许在较小 $\beta$ 下突破微弱的弱序关系，使个体软优先级对最终排名的调控杠杆作用显著放大。
代理估计器在通用图上的代价陷阱：虽然二次代理在复杂协同博弈中能进一步降低估计误差，但在GPASV下由于无法像PASV那样直接剪除DAG禁止的交互项，其回归参数必须完整保留，导致内存随着参与者数量增长极快（在 $n=1024$ 时内存膨胀至 108.3 GB），因此直接蒙特卡洛结合效用缓存反而是综合效益最高的可扩展基准。

亮点与洞察¶

从“硬性剪枝”跃迁至“软性度规”：将难以满足的无环DAG偏好泛化为全空间上的Gibbs能量模型，完美解决了社会选择中普遍存在的孔多塞循环与现实置信权重丢失问题，填补了博弈归因方法论的空白。
优雅的局部MCMC抵消构造：推导出的相邻对换Metropolis-Hastings接受比完全消除了非局部项，使得单步对换判决的时间复杂度与排列总长度解耦，极大提升了高维状态采样的可扩展性。
直面主观权衡的非确定性：明确指出优先级感知归因不是一个自动化“一键运行”的任务；在模型选择与数据确权中，成对群体胜率与个体策略偏好本身就存在潜在张力，GPASV将这一权衡透明化为可扫描的连续谱系。

局限与展望¶

黑盒效用调用的本征下界：虽然缓存与SNIS减少了5倍以上的重复查询，但在组合空间庞大、单次效用评估昂贵的场景（如复杂的多Agent演练或超大模型微调验证）中，黑盒边际评估仍面临巨大的计算压力。
输入优先级图的噪声敏感度：当前框架将成对胜率图视为无误差的确定性输入，但在极限硬边界 $\beta \to \infty$ 处，相近边权重的细微波动可能引发极小违规排列集合的跃变，亟需进一步建立具有统计置信区间与鲁棒性界的误差分析理论。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破长期阻碍图结构Shapley值发展的DAG无环假设，公理化完备且理论自洽。
实验充分度: ⭐⭐⭐⭐⭐ 既有理论精确解的合成验证，又有基于H200集群、20个LLM及80个真实评测任务的大规模落地实验。
写作质量: ⭐⭐⭐⭐⭐ 逻辑推导丝丝入扣，图表详实，对局限性与权衡维度的讨论极其深刻坦诚。
价值: ⭐⭐⭐⭐⭐ 为大模型集成归因、数据要素市场确权与带有争议偏好的复杂系统评估提供了全新的标准工具。