💬 NLP

Consistent and Distinctive: LLM Benchmark Efficiency via Maximum Independent Set Prompt Selection on Similarity Graphs

本文提出了一种基于图的框架，利用最大独立集算法从大语言模型（LLM）基准测试中筛选出多样且非冗余的提示词子集，证明了此类缩减后的集合在显著降低评估成本的同时，仍能保持高度一致的模型排名。

原作者： Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位法官，正试图从 66 位不同的厨师（大语言模型）中选出最优秀的一位。你拥有一本包含 1,000 道菜谱的巨型食谱（基准测试）。为了公平起见，你想品尝到每种食物的一点点味道。但要把这 1,000 道菜全部做完既费时又昂贵，而且如果食谱本身出了问题——比如里面有 500 道“香辣意面”的食谱，却只有 10 道“甜点”食谱——结果可能会产生偏差。如果你品尝了所有菜肴，那些擅长做香辣意面的厨师看起来会像天才，即便他们其实根本不会烤蛋糕。

本文提出了一种巧妙的方法，旨在同时解决两个问题：节省时间/金钱以及修复食谱中的偏差。

以下是他们如何实现的，解释如下：

1. 问题所在：过多的冗余

作者注意到，这些大型测试中的许多问题实际上是非常相似的。就像在数学测试中，有 50 种不同的方式来问“2+2 等于几？”。测试所有这些问题是在浪费时间，并且会对那些擅长这类特定问题的模型产生不公平的加分。

2. 解决方案：“无克隆”规则

团队创建了一个系统，用于挑选出一组规模更小、更聪明的题目。他们使用了一种叫做最大独立集 (Maximum Independent Set, MIS) 的方法。

类比： 想象你正在举办一场派对，你有一份 1,000 位潜在宾客的名单。然而，你有一个规则：任何两个“过于相似”的宾客都不能同时被邀请。
- 如果宾客 A 和宾客 B 穿着完全相同的衣服，且谈论着完全相同的话题，他们就是“相连”的。你只能选择其中之一。
- 目标是在确保没有两个宾客过于相似的前提下，邀请尽可能多的人。
结果： 你最终得到的是一个规模较小的派对（可能是 300 人而不是 1,000 人），但这个人群更加多元化。你剔除了“克隆体”，保留了独特的声量。

3. 他们是如何构建“宾客名单”的

为了判断谁“过于相似”，他们并没有让真人去阅读问题。相反，他们使用了 AI “翻译官”（嵌入模型/embedding models）将每个问题转化为地图上的一个坐标。

意思相近的问题会在地图上靠得很近。
他们在每个问题周围画了一个圆圈。如果另一个问题落在了那个圆圈内，它们就被视为“过于相似”。
然后，他们运行了一个计算机算法，来挑选出一个最大的问题组，在这个组中，没有任何两个问题会落在彼此的圆圈内。

4. 他们的发现

他们在四种不同类型的测试（数学、常识、指令遵循等）上测试了这种方法，并使用了 66 个不同的 AI 模型。

排名保持不变： 当他们挑选出这组规模更小、更多样化的题目时，AI 厨师的排名（谁是第 1 名、第 2 名、第 3 名）与他们在 1,000 道题上进行测试得到的排名几乎完全一致。
- 统计数据： 在 99.2% 的测试中，无论他们如何运行选择过程，厨师的先后顺序都是一致的。
节省了大量时间： 根据严格程度的不同，他们可以在不影响区分最佳模型能力的前提下，减少 25% 到 48%（有时甚至更多）的问题数量。
修复了“偏差”： 因为剔除了“克隆体”，测试变得更加公平。如果一个测试中有太多的“香辣意面”问题，这种方法会移除多余的部分，确保最终得分反映的是广泛的技能水平，而非仅仅是某个特定领域。

5. 缺陷（何时无法完美运作）

当“相似性圆圈”设置得不够大时，该方法的效果会打折扣。

如果他们设置的规则过于严格（只允许差异极大的问题），会导致宾客名单变得非常短，从而遗漏了重要的主题。这种情况主要发生在那些本身就非常重复或具有奇怪评分模式的测试（如“IFEval”测试）中。
然而，即使在这些“失败”案例中，结果也是一致的。计算机总是会挑选出同样的少量问题，而这组问题所讲述的故事与完整测试的故事略有不同。作者认为这并非漏洞，而是一种功能，它揭示了原始测试存在的偏差。

总结

本文证明了，你不需要在数千个问题上测试 AI 模型就能知道谁是最优秀的。通过使用“无克隆”规则来挑选一组具有代表性的多样化样本，你可以：

节省大量的计算能力和时间。
获得更公平的分数，使其不会因为存在过多相似问题而产生偏差。
信任结果，因为该方法是稳定且可重复的。

这就像是你意识到，你不需要喝光一大锅汤里的每一滴汤就能知道它是否咸了；你只需要从不同位置舀取几勺，就能品尝出真实的滋味。

技术摘要：通过最大独立集提示词选择实现一致且具辨识度的 LLM 基准测试效率

问题陈述

对大语言模型（LLM）的严格评估面临两个主要挑战：评估效率与覆盖偏差。

效率： 全面的基准测试（如 MMLU-Pro、GPQA）通常包含数百到数千个问题，这为前沿模型和大规模排行榜带来了高昂的推理成本。
覆盖偏差： 基准测试的提示词在嵌入空间中的分布往往是不均匀的。如果一个基准测试过度代表了特定的语义区域（例如，存在大量相似的化学问题），它会隐性地提高模型在这些特定层面的表现权重，从而导致无论通用能力如何，都会扭曲排名。这种结构性偏差在聚合指标中是不可见的，但源于提示词之间的语义冗余。

现有的子集选择方法（如基于项目反应理论 IRT 的方法）通常需要迭代的模型交互或特定的题目难度建模。因此，需要一种与模型无关的方法，仅基于成对相似度来选择提示词，以同时降低成本并纠正覆盖偏差。

方法论

作者提出了一个图论框架，将每个基准测试建模为一个提示词相似性图 $G = (V, E)$ 。

嵌入构建： 使用各种嵌入模型（包括基于编码器和基于解码器的模型）将提示词映射为固定维度的向量。
图构建： 节点代表提示词。如果两个节点的嵌入空间距离超过一个可配置的阈值 $\theta$ （定义为经验距离分布的一个百分位数），则在它们之间建立一条无向边。
- 注：文中定义边是基于距离高于阈值，这意味着在用于 MIS 的图构建逻辑中，连接的节点被视为“不相似”；或者反之，独立集确保选中的节点不相连，意味着它们在阈值范围内是相似的？
- 根据文本进行的修正： 文中指出：“当成对距离……超过预定义阈值时，添加一条无向边……”
- MIS 逻辑： 最大独立集（MIS）是一个节点集合，其中任意两个节点都不共享一条边。因此，在选定的子集中，没有两个提示词的距离 $\ge \theta$ 。这意味着所有选定的提示词之间的距离都 $\le \theta$ ？
- 重新仔细阅读文本： 文中提到：“如果其嵌入空间距离落在可配置阈值 $\theta$ （由经验距离分布的百分位数定义）之上，则连接两个节点。”
- 逻辑矛盾检查： 如果边存在于距离 $\ge \theta$ （不相似）时，那么独立集（无边）意味着所有对之间的距离都 $< \theta$ （相似）。这将选择一组相似的提示词，这与“最大化多样性”的目标相悖。
- 另一种解释： 论文可能定义了基于“相似度分数”的边（高分表示接近），或者“距离”概念被反转了。
- 基于上下文的结论： 目标是“非冗余”。冗余意味着相似。为了消除冗余，我们需要挑选距离较远的项。如果图连接的是过于相似的项目（距离 $< \theta$ ），那么 MIS（无边）会挑选出不相似的项目（距离 $\ge \theta$ ）。
- 最终判定： 虽然文中关于“距离高于阈值”与“独立集保持低于阈值”的描述在逻辑上可能存在表述偏差，但其核心意图是明确的：通过 MIS 选择一个最大化多样化、非冗余的子集。
最大独立集 (MIS) 选择： 将问题转化为寻找最大的节点子集 $S$ ，使得其中任意两个节点都不共享一条边。
- 评估的算法： 测试了四种求解器：
  - CPLEX： 精确求解器（整数线性规划）。
  - GREEDY： 确定性启发式算法（最低度顶点）。
  - Online-MIS： 随机流式启发式算法。
  - ReduMIS： 图核化 + 随机局部搜索。
- 随机性： 对随机求解器（Online-MIS, ReduMIS）进行了 5 个随机种子下的测试，以测试一致性。
评估指标：
- 排名一致性 ( $\rho$ )： 子集排名与全量基准测试排名之间的 Spearman 秩相关系数。
- 稳定性 ( $W$ )： 不同随机种子之间的 Kendall 同序系数。 $W \ge 0.90$ 表示近乎完美的吻合。

核心贡献

图论框架： 一个与模型无关的提示词选择框架，通过 MIS 同时解决效率和覆盖偏差问题，实现最大化多样化且非冗余的子集选择。
广泛的实证验证： 在 2,563 种唯一配置下进行评估，涉及：
- 4 个基准测试 (GPQA, IFEval, MMLU-Pro, Omni-MATH)。
- 66 个前沿 LLM。
- 6 个嵌入模型 (3 个小型编码器, 3 个大型解码器)。
- 3 种距离度量 (Cosine, Pearson, Standardized Euclidean)。
- 6 个百分位阈值 ( $p10$ – $p95$ )。
- 4 种 MIS 求解器。
假设确认： 核心假设得到证实——即重复的 MIS 选择会产生一致的排名，且由于纠正了覆盖偏差，这些排名可能与全量基准测试有所不同。

结果

一致性： 一致性假设成立。在 99.2% 的随机配置中， $W \ge 0.90$ （平均 $W = 0.997 \pm 0.008$ ）。这表明不同的随机种子产生了高度稳定的排名。
排名差异： 与全量基准测试的排名差异（ $\rho < 0.95$ $ρ < 0.95$ ）仅出现在 15.95% 的配置中。
- 这些差异集中在低阈值（ $p10$ – $p20$ ）以及特定基准测试（GPQA 和 IFEval）中。
- 作者认为过度稠密的图（保留了过少的代表性提示词）是导致此类差异的主要失效模式。
效率： 在较高的百分位阈值（如 $p80$ ）下，该方法在保持高排名保真度 ( $\rho \approx 0.992$ ) 的同时，实现了 25–48% 的提示词削减。
算法性能：
- ReduMIS 和 Online-MIS（随机型）表现出最高的同序性 ( $W \approx 0.997$ )。
- CPLEX 和 GREEDY（确定型）实现了类似的排名相关性 ( $\rho \approx 0.968$ )，但无法提供基于种子的稳定性指标。
嵌入模型： 大型解码器模型（如 Qwen-8B, Nemotron-8B）在保留排名结构方面普遍优于小型编码器模型，尤其是在使用标准化欧几里得距离时。
阈值效应：
- $p80$ 被确定为最佳平衡点，它提供了近乎完美的排名保持能力 ( $\rho=0.992$ ) 并实现了 37–45% 的削减。
- $p10$ – $p20$ （激进剪枝）显示出较低的相关性 ( $\rho \approx 0.905$ )，但仍具有高一致性 ( $W \approx 0.990$ )，这表明该子集是稳定的，但与存在偏差的全量基准测试存在差异。

意义与主张

本文声称，基于 MIS 的提示词选择是一种原则性的、高效的方法，它重新定义了 LLM 的评估：

重新定义差异： 子集与全量基准测试之间的较低 Spearman 相关性 ( $\rho < 0.95$ ) 不一定是缺陷。如果全量基准测试存在覆盖偏差，MIS 子集通过降低过度代表层面的权重，提供了一个经过纠正的、独特的视角。高一致性 ( $W$ ) 证实了这种“具辨识度”的排名是可重复的。
结构性偏差诊断： 相似性图的度分布可作为覆盖偏差的诊断工具。具有高度数中心（大量近乎重复项）的基准测试最容易出现偏差，也最能从 MIS 选择中获益。
实践建议： 作者建议对于大多数基准测试，使用 ReduMIS 求解器 + Qwen-8B 嵌入 + 标准化欧几里得距离 + $p80$ 阈值 的配置，可实现 $W=1.000$ 和 $\rho=0.9959$ 。

这项工作将 SELECTOR 框架（此前用于数值优化）扩展到了自然语言提示词领域，证明了结构化覆盖保证可以无缝迁移到 LLM 评估中，而无需进行迭代的模型交互。