Prompt Perturbation for Reliable LLM Evaluation over Comparison Graphs¶

讲者: Dong Huang
会场: Advances in Machine Learning for Large Language Models and Matrix Methods
报告题目: Prompt Perturbation for Reliable LLM Evaluation over Comparison Graphs
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的子方向是基于成对比较的大语言模型（LLM）评估与排名。其根本问题是：在开放任务中，如何通过收集模型对同一提示的响应之间的成对偏好（由人类或一个“评判模型”给出），并将这些局部判断聚合为一个全局排名，从而可靠地评估和比较不同LLM的能力。当前该方向正处于从“单一提示/单一基准”向“多提示、多比较、图结构聚合”演进的阶段，核心挑战在于成对比较中普遍存在的非传递性（intransitivity）——即比较结果可能无法支持任何一致的全局排名（如出现A≻B≻C≻A的循环）。

发展脉络（history）¶

奠基工作：基准测试与LLM-as-a-judge的兴起。早期LLM评估依赖固定基准（如MMLU [HBB+20]、GSM8K [CKB+21]、BIG-bench [SRR+23]），但作者指出这些基准“often fail to capture the full range of model capabilities, especially in open-ended and domain-specific settings”。随后，LLM-as-a-judge范式出现 [WLM+23, LIX+23]，即用一个强LLM（如GPT-4）来评判其他模型的输出。Zheng et al. [ZCS+23] 报告GPT-4与人类判断的一致性“comparable to human annotators themselves”，这为大规模自动评估铺平了道路。同时，专用评判模型如JudgeLM [ZWW23] 和Prometheus [KSL+24] 被开发出来。
主要进展：成对比较与排名聚合。为克服单一基准的局限，成对比较成为主流策略 [ZCS+23, CZS+24, DGLH24]。经典排名方法如Elo [Elo78]、Bradley-Terry [BT52]、Davidson [Dav70]、Rank Centrality [NOS17] 被引入LLM评估。Daynauth et al. [DCF+25] 比较了这些方法在头对头LLM评估中的“transitivity, stability, and sensitivity”。Gao et al. [GLH+25] 进一步分解了自动排名流水线，显示最终排行榜不仅取决于评判模型，还取决于聚合方法本身。
当前frontier：非传递性与提示敏感性。近期工作揭示了成对LLM评估中的严重非传递性。Xu et al. [XRRK25] 显示AlpacaEval中的非传递偏好使系统排名对参考基线的选择敏感，并倡导更广泛的成对比较设计。Wang et al. [WSZ+25] 识别了LLM-as-a-judge流水线中的系统不一致性，包括循环偏好和涉及平局的矛盾。同时，提示敏感性被广泛研究：Mizrahi et al. [MKM+24] 和 Maia Polo et al. [MPXW+24] 表明单一提示评估是脆弱的，多提示评估更可靠。PromptRobust [ZWZ+23] 等基准也证实了LLM对对抗性提示的脆弱性。
本文的位置：本文提出一个提示扰动框架，通过生成每个提示的语义等价变体，利用由此产生的多个比较图的结构一致性（以短循环计数衡量）来过滤掉高度不一致的图，然后再进行排名聚合。作者将这一方法定位为“incorporate graph-level structural consistency explicitly into the LLM evaluation pipeline before ranking aggregation”，即从图构造层面而非仅从聚合层面解决非传递性问题。

子线索聚类¶

LLM-as-a-judge与评判模型：包括GPT-4 [AAA+23]、G-Eval [LIX+23]、JudgeLM [ZWW23]、Prometheus [KSL+24]、JudgeLRM [CHZ+25]。这一簇关注如何构建和使用LLM作为评估者，包括其偏差（位置偏差、冗长偏差等）和校准。
排名方法与聚合：包括Elo [Elo78]、Bradley-Terry [BT52]、Davidson [Dav70]、Rank Centrality [NOS17]、HodgeRank [JLYY11]。这一簇研究如何从成对比较数据中估计全局排名，以及不同方法的传递性、稳定性和敏感性。
提示鲁棒性与多提示评估：包括PromptRobust [ZWZ+23]、多提示评估 [MKM+24, MPXW+24]、PromptEval [MPXW+24]、长度控制AlpacaEval [DGLH24]。这一簇关注提示变化对LLM行为的影响，并倡导通过多提示或扰动来提高评估可靠性。
非传递性与图结构一致性：包括Xu et al. [XRRK25]、Wang et al. [WSZ+25]。这一簇直接研究成对比较中的非传递性现象及其对排名可靠性的影响。本文属于此簇，但引入了图级结构一致性作为过滤标准。

核心问题与已知瓶颈¶

核心问题1：如何设计成对比较流程，使得产生的比较图尽可能支持一个一致的全局排名？
核心问题2：如何检测和量化比较图中的非传递性（循环）？
核心问题3：在存在非传递性的情况下，如何聚合局部判断以获得一个稳定且有意义的全局排名？
已知瓶颈：非传递性是内在的，可能源于评判模型的不一致性、提示敏感性、或模型能力之间的真实非传递关系。现有方法主要在聚合阶段处理它（如使用更鲁棒的排名模型），但很少在比较图构造阶段主动减少它。

⚠️ 作者的framing¶

作者将缺口frame成：现有工作主要研究如何聚合给定的成对结果，而本文关注的是在聚合之前改进比较图本身，通过减少循环不一致性来提高排名可靠性。作者在1.1节明确写道：“This line of work mainly studies how to aggregate a given set of pairwise outcomes, whereas our focus is on improving the comparison graph itself before aggregation by reducing cyclic inconsistency.” 竞争路线（如更好的聚合方法、更复杂的偏差校正）被淡化——作者承认ScoreWin40等基线“remains a competitive baseline”，但认为“the best overall results still come from combining semantic perturbation with cycle-aware filtering before the final ranking step”。明显该被引或该存在、却没出现在intro里的：本文未引用任何关于统计-计算权衡或低度多项式障碍的文献，也未引用关于高阶U统计量或张量网络复杂度的工作。考虑到研究者（陈星宇）的背景，这些缺失可能意味着该问题目前尚未从计算复杂度的角度被分析，或者作者认为该问题的计算瓶颈不在排名聚合本身。这是一个值得研究者去查的问题。

张力¶

未见明显对立引用。各工作基本在同一个框架下推进，共识是：非传递性是一个核心挑战，需要更好的方法来解决。分歧主要在于解决方案的侧重点（聚合 vs. 图构造）。

二、最核心、最简单的例子 / 数学问题¶

第一步：符号、模型、可观测数据交代清楚¶

符号：
M = {M_1, ..., M_n}：待排名的n个LLM的集合。
X = {x_1, ..., x_t}：t个评估提示的集合。
G_i：由提示x_i诱导的比较图。顶点集V(G_i) = {1, ..., n}（对应n个模型）。有向边(j, j') ∈ E(G_i)表示在提示x_i下，评判模型偏好模型M_j胜过M_{j'}。平局由双向边(j, j')和(j', j)表示。
W ∈ R^{n×n}：胜场矩阵，W_{ij} = 模型M_i胜过M_j的总次数。
T ∈ R^{n×n}：平局矩阵，T_{ij} = 模型M_i与M_j平局的总次数。
θ = (θ_1, ..., θ_n)：潜在能力得分向量，决定成对比较概率。
p：理论模型中的噪声参数，1/2 + p是正确方向被保留的概率（0 < p ≤ 1/2）。
q = (1/2 - p) / (1/2 + p)：Mallows分布的尺度参数。
G*：潜在的真实比较图（由真实排名诱导）。
˜G：多数投票集成图。
C_3(G), C_4(G)：图G中3-循环和4-循环的数量。
C^{bad}_3(G), C^{bad}_4(G)：排除纯平局循环后的“坏”循环数量。
S_µ(G) = C^{bad}_3(G) + µ C^{bad}_4(G)：截断分数。
K：保留的比较图数量。
t：提示数量（或理论模型中的样本图数量）。
n：模型数量。
m：每个提示的扰动变体数量。
模型：
Bradley-Terry模型：假设存在潜在得分θ，模型M_i胜过M_j的概率为P_{i≻j}(θ_i, θ_j) = e^{θ_i} / (e^{θ_i} + e^{θ_j})。不允许平局。
Davidson模型：扩展Bradley-Terry，引入平局参数ν ≥ 0，允许平局概率P_{i∼j}(θ_i, θ_j) = ν√(e^{θ_i}e^{θ_j}) / (e^{θ_i} + e^{θ_j} + ν√(e^{θ_i}e^{θ_j}))。
理论模型（第5节）：假设存在一个潜在的真实比较图G*（由真实排名1 ≻ 2 ≻ ... ≻ n诱导）。每个观测图G_k独立于G*，对于每对(i, j)（i < j），G_k中的边方向与G*一致的概率为1/2 + p，相反的概率为1/2 - p。这等价于一个噪声翻转模型。
可观测数据：
可观测：对于每个提示x_i（及其扰动变体x_{i,j}），以及每对模型(M_a, M_b)，我们可以通过评判模型获得一个比较结果：M_a ≻ M_b、M_a ≺ M_b或M_a ∼ M_b。这些结果构成有向比较图G_i（或G_{i,j}）。我们还可以计算每个图的循环计数C_3, C_4。
潜在/不可观测：模型的真实能力得分θ（或真实排名）是潜在且不可观测的。真实比较图G*也是潜在的。我们只能通过可观测的比较结果来推断它们。

第二步：讲最小内核¶

本文的核心思路可以浓缩为以下最简特例：n=3个模型，t=1个原始提示，m=1个扰动变体。

设定：我们有三个模型A、B、C，一个原始提示x，以及它的一个语义等价扰动x'。评判模型对x和x'分别进行所有三对比较。
可观测数据：
从x得到比较图G：假设结果为A≻B, B≻C, C≻A。这是一个3-循环，C_3(G) = 1。
从x'得到比较图G'：假设结果为A≻B, B≻C, A≻C。这是一个传递性图，C_3(G') = 0。
问题：如果直接使用G进行排名，由于存在循环，任何基于得分的模型（如Bradley-Terry）都无法完美拟合，排名可能不稳定。如果只使用G'，则排名是A > B > C，但可能丢失了G中C≻A所反映的某些真实信息（或噪声）。
本文方法：
计算循环：S_µ(G) = 1，S_µ(G') = 0。
截断：如果我们设置保留图数量K=1，那么我们会保留G'（循环更少），丢弃G。
排名：基于保留的G'，使用Bradley-Terry模型得到排名A > B > C。
核心思路：通过生成扰动变体，我们获得了多个“视角”的比较图。然后，我们使用图级结构一致性（即短循环数量）作为过滤器，优先选择那些更可能反映真实传递性偏好的图。在这个例子中，G'被认为是更“一致”的，因此被保留。这个最小内核揭示了论文的核心数学操作：将“排名可靠性”问题转化为“图结构一致性”问题，并通过一个简单的计数-截断流程来解决。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：如何通过提示扰动和基于循环的图截断来提高成对LLM评估中排名的一致性和可靠性。
核心工具/方法：提出一个四阶段流水线：(i) 为每个原始提示生成多个语义等价的扰动变体；(ii) 从每个变体构建比较图；(iii) 根据每个图的“坏循环”数量（C^{bad}_3 + µ C^{bad}_4）进行截断，仅保留循环最少的K个图；(iv) 在保留的图上拟合Bradley-Terry或Davidson模型以获得最终排名。
主要结论：在MT-Bench上使用GPT-5和Prometheus作为评判模型的实验中，所提出的截断方法（Trunc25→20）在宏观平均归一化Spearman距离上优于所有基线（包括无截断、随机子集、仅采样等），表明图级结构一致性过滤能有效提高排名质量。理论分析在一个随机有向图模型下证明了截断可以降低精确恢复真实排名的样本复杂度。

关键设定与假设¶

设定：n=20个目标LLM，t=80个MT-Bench问题（8个类别，每类10题），每个问题生成m=4个扰动变体（共5个图/问题），每个评判模型产生8×10×5=400个比较图。评判模型为GPT-5和M-Prometheus-14B。
假设：
语义等价性：生成的扰动变体在语义上与原始提示等价。作者通过一个两阶段流程（生成+过滤）来保证这一点。
比较图的可比性：不同提示（包括原始和扰动）诱导的比较图是可比的，并且可以一起用于排名聚合。
Bradley-Terry/Davidson模型的适用性：在截断后，保留的比较图足够“传递性”，以至于可以用这些基于得分的模型很好地拟合。作者通过模型诊断（表3）来验证这一点，发现截断确实减少了模型误设警告。
理论模型假设（第5节）：每个观测图G_k独立于潜在真实图G*，且边方向以概率1/2 + p与G*一致。这是一个强假设，忽略了提示异质性和评判偏差。作者在讨论中承认了这一点。

主要结果¶

实证结果（表2）：
Trunc25→20在两种评判模型下均取得最低宏观平均归一化Spearman距离：GPT-5为0.056，Prometheus为0.070。
在GPT-5下，Trunc25→20在8个任务中的5个（Coding, Extraction, Math, Roleplay, Writing）取得最低距离；在Prometheus下，在4个任务中（Coding, Extraction, Math, Roleplay）取得最低。
与无截断基线（NoTrunc boot）的比较：Trunc25→20在多数任务上优于NoTrunc boot，表明改进来自循环过滤而非仅使用更多数据。
与仅采样基线（Sample25→20）的比较：Trunc25→20显著优于Sample25→20（GPT-5: 0.056 vs 0.120），表明语义扰动本身比随机采样更重要。
成本-损失权衡（图3）：在相同的评估预算（相同数量的源图和成对评判调用）下，截断方法始终优于无截断方法，证明改进来自图质量而非预算增加。
K的选择（图4）：排名损失随K呈现U形曲线，最佳K在中间范围（约25），表明存在偏差-方差权衡：K太小则信息不足，K太大则引入噪声图。
µ的敏感性（图5）：排名损失对µ（3-循环和4-循环的相对权重）不敏感，表明主要信号来自短循环的存在本身，而非精确计数。
理论结果（定理1-3）：
定理1（无截断）：在噪声翻转模型下，精确恢复真实排名所需的样本图数量t的下界为(4+ϵ) log n / log(1/(1-4p^2))。若t低于此阈值，则˜G几乎必然包含有向三角形。
定理2（有截断）：在条件于图无有向三角形的分布下，所需样本图数量降至(2+ϵ) log n / log(1/(1-4p^2))。这证明了循环截断可以降低样本复杂度。
定理3（MLE下界）：在截断模型下，MLE的精确恢复阈值与˜G相同（至常数），但˜G的计算复杂度为O(t n^2)，远低于MLE的穷举搜索。

证明路线与技术技巧（理论型）¶

整体路线（定理1证明）：
上界（正结果）：对于每对模型(i, j)，使用Chernoff界（[Che52]）来界定多数投票˜G中边方向错误的概率。然后使用联合界（union bound）对所有O(n^2)对进行控制。当t足够大时，所有边都以高概率正确，从而˜G = G*。
下界（负结果）：首先证明当t较小时，特定边（如(i, j)，其中i ≤ n/3且j ≥ 2n/3）错误的概率˜p足够大，使得n^2 ˜p / 9 → ∞。然后利用这些边的独立性，证明存在一个i和j使得边方向错误。接着，通过构造一个中间顶点k，证明存在一个i → k → j → i的有向三角形。关键跳跃点在于：不是直接计算所有三角形的期望，而是通过构造一个特定结构（i在低排名区，j在高排名区，k在中间）来证明至少存在一个三角形。
技术技巧：
Chernoff界：用于控制二项式分布尾部概率。
联合界：用于处理多个事件同时发生的概率。
大偏差理论：KL散度D_KL(1/2 || 1/2 + p)出现在指数衰减率中。
组合构造：在下界证明中，通过选择特定范围的顶点来构造三角形，而非枚举所有可能。
定理2证明路线：
引理4：证明无有向三角形的完全有向图必然是传递的（即存在一个全序）。
命题5：在条件于无三角形的分布下，边方向概率不再是常数1/2 + p，而是依赖于顶点在真实排名中的距离d = j-i。具体地，α_d = P[(i,j) ∈ E(G) | A]随d增加而增加。这意味着距离越远的模型对，其比较结果越可靠。
上界证明：利用α_d的性质，特别是α_1 = 1/2 + p和α_2 > α_1，以及I_2 ≥ 2 I_1（其中I_d = D_KL(1/2 || α_d)），将联合界中的项数从O(n^2)降低到O(n)主导，从而得到更紧的阈值(2+ϵ) log n / log(1/(1-4p^2))。
技术技巧：
Mallows分布：用于刻画条件于无三角形时的图分布。
组合恒等式：用于计算Mallows分布的归一化常数和边概率。
KL散度的单调性：利用α_d的单调性推导I_d的下界。

真实例子与应用¶

数据/场景：MT-Bench，一个包含80个多轮对话问题的基准，覆盖8个类别。20个目标LLM（包括Gemma、GPT、Granite、Mistral、OLMo、Phi、Qwen等系列）。
方法应用：
对MT-Bench中的每个问题，使用GPT-5.2生成4个语义等价的扰动变体。
对每个原始问题和扰动变体，使用评判模型（GPT-5或Prometheus）对所有190对模型进行成对比较，构建400个比较图。
计算每个图的坏循环分数S_1(G) = C^{bad}_3(G) + C^{bad}_4(G)。
在每个类别内，保留分数最低的25个图。
从这25个图中无放回地抽取20个，重复100次，每次拟合Bradley-Terry模型得到排名。
将得到的排名与从Chatbot Arena排行榜快照中提取的参考排名进行比较，计算归一化Spearman距离。
结果：Trunc25→20在宏观平均上取得最低距离（GPT-5: 0.056, Prometheus: 0.070），优于所有基线。
例子想说明什么：该例子旨在验证所提方法在真实LLM评估场景中的有效性。它展示了：(1) 循环计数与排名误差正相关（图2）；(2) 循环过滤能提高排名质量（表2）；(3) 改进来自图质量而非预算增加（图3）；(4) 方法对超参数（K, µ）具有一定的鲁棒性（图4, 5）。

🔎 结论是否比证明窄¶

是。论文的实证结论是“Trunc25→20在MT-Bench上优于基线”，但理论证明（定理1-3）是在一个非常简化的随机有向图模型下建立的，该模型假设所有边独立且同分布地以概率1/2 + p与真实图一致。这个模型忽略了：
提示异质性：不同提示可能具有不同的噪声水平p。
评判偏差：位置偏差、冗长偏差等系统性偏差。
模型间的相关性：不同模型对的比较结果可能相关。
非传递性的真实来源：理论模型中的非传递性完全来自随机噪声，而实际中可能源于模型能力的真实非传递性。
作者在讨论中承认了这一点：“Our current analysis is based on a simple random directed graph model. An important direction is to establish theoretical guarantees under more realistic models that capture heterogeneous prompts, judge bias, and dependence across comparisons.” 因此，理论结果提供了一个概念性验证，表明在理想化条件下截断是有益的，但不能直接推广到实际场景。实证结果的有效性依赖于MT-Bench这个特定数据集和评判模型。

四、开放问题¶

更丰富的集成方法：本文使用简单的多数投票作为集成规则。作者在讨论中提出“develop more refined aggregation procedures that better exploit the structure of pairwise comparison graphs”。这扎根于论文第6节“Richer integration methods”。一个具体问题是：能否设计一个加权投票方案，其中每个图的权重取决于其循环计数或其他结构属性，而不是简单地截断？
更现实的理论模型：当前理论模型假设同质噪声和独立边。作者呼吁“establish theoretical guarantees under more realistic models that capture heterogeneous prompts, judge bias, and dependence across comparisons”。这扎根于论文第6节“More realistic theoretical models”。一个具体问题是：能否在存在评判偏差（如位置偏差）的情况下，证明截断方法的有效性？
软截断与硬截断的权衡：论文理论部分考虑了硬截断（保留0个三角形的图）和无截断（保留所有图）两个极端，并指出中间情况（保留最多N个三角形的图）可能有一个有趣的权衡。这扎根于第5.2节：“one may consider soft truncation rather than imposing the hard constraint of excluding all graphs with directed triangles... A precise characterization of this trade-off is an interesting open problem”。一个具体问题是：能否刻画保留图数量K和允许的最大循环数N之间的最优关系？
与统计-计算权衡的连接：本文未从计算复杂度角度分析。一个开放问题是：是否存在一个统计-计算权衡，即为了达到某个排名精度，所需的最小图数量（统计阈值）与多项式时间算法所能达到的（计算阈值）之间存在差距？这扎根于研究者（陈星宇）的兴趣，但论文本身未提及。一个具体问题是：能否将低度多项式障碍或SQ下界技术应用于本文的随机图模型，以证明某些排名问题在多项式时间内是困难的？

Maintained by 陈星宇 · Homepage · Source on GitHub