Beyond Pairs：基于有向无环偏好图的 Direct Preference Optimization 推广
> 2026 年 5 月，Liu 等人揭示了标准 DPO 在处理多 rollout 偏好数据时的结构性信息损失，并提出了 GraphDPO。该框架将成对比较推广至有向无环偏好图，通过 Plackett-Luce 启发的图结构目标函数聚合图邻域监督，强制传递性约束，同时通过等价类构造处理质量相同的响应。尽管利用全图结构，GraphDPO 通过高效的 log-sum-exp 聚合保持线性 per-prompt 复杂度。实验表明，GraphDPO 在推理和程序合成任务上全面优于标准 DPO 和列表排序方法。
---
1. 背景：DPO 的信息瓶颈
1.1 多 Rollout 场景的数据结构
实际对齐训练中，每个 prompt 通常产生多个 rollout：
$$\{y_1, y_2, \ldots, y_N\} \sim \pi_{\text{ref}}(\cdot | x)$$
这些响应天然形成全序或偏序关系。
1.2 标准 DPO 的信息损失
DPO 将多 rollout 数据折叠为独立成对比较：
| 原始结构 | DPO 处理 | 信息损失 |
|---|---|---|
| 全序/偏序 | C(N,2) 个独立对 | 传递性约束丢失 |
| 等价关系（质量相同） | 强制胜负判定 | 虚假梯度引入 |
| 全局一致性 | 局部成对优化 | 冲突可能 |
---
2. GraphDPO：方法
2.1 偏好图构造
| 图元素 | 定义 | 语义 |
|---|---|---|
| 节点 | $V = \{y_1, \ldots, y_N\}$ | 候选响应 |
| 有向边 | $(y_i, y_j) \in E$ iff $y_i \succ y_j$ | 支配关系 |
| 传递闭包 | 自动蕴含 | 逻辑一致性 |
| 等价类 | $\{y_i : y_i \sim y_j\}$ | 质量相同的响应 |
2.2 图结构优化目标
GraphDPO 优化 Plackett-Luce 启发的图目标：
$$\mathcal{L}_{\text{GraphDPO}} = -\sum_{(i,j) \in E} \log \sigma\left(\beta \log \frac{\pi_\theta(y_i|x)}{\pi_{\text{ref}}(y_i|x)} - \beta \log \frac{\pi_\theta(y_j|x)}{\pi_{\text{ref}}(y_j|x)}\right)$$
> 与 DPO 的兼容性：当图为链式结构（仅相邻比较）时，GraphDPO 退化为标准 DPO。
2.3 等价类构造
| 关系类型 | 图表示 | 损失处理 |
|---|---|---|
| 严格偏好 $y_i \succ y_j$ | 层间有向边 | 正常损失 |
| 等价 $y_i \sim y_j$ | 层内无向边/同层 | 零损失 |
2.4 计算效率
通过 log-sum-exp 技巧实现高效聚合：
| 方法 | Per-prompt 复杂度 | 空间复杂度 |
|---|---|---|
| 全图暴力 | $O(N^2)$ | $O(N^2)$ |
| GraphDPO | $O(N)$ | $O(N)$ |
---
3. Ground-Truth 锚定与退火调度
3.1 训练不稳定性问题
早期训练中，低质量 rollouts 占主导，排序信号噪声大。
3.2 锚定机制
| 组件 | 功能 |
|---|---|
| 验证解插入 | 将 ground-truth 解作为图中最优节点 |
| 退火调度 | 早期强锚定，逐步放松 |
| 训练阶段 | 锚定强度 | 监督来源 |
|---|---|---|
| 早期 | 高 | 主要依赖验证解 |
| 中期 | 中 | 混合 |
| 晚期 | 低 | 主要依赖模型自主排序 |
4. 实验结果
4.1 任务配置
| 任务 | 领域 | 评估重点 |
|---|---|---|
| 推理任务 | 数学/逻辑 | 正确性 |
| 程序合成 | 代码生成 | 功能正确性 + 效率 |
4.2 性能对比
| 方法 | 相对表现 | 信息利用 |
|---|---|---|
| 标准 DPO | 基准 | 成对，无传递性 |
| 列表排序 | 稍好 | 列表级，部分传递性 |
| GraphDPO | 最优 | 全图，完整传递性 |
4.3 消融分析
| 组件 | 贡献 |
|---|---|
| 图结构（vs 成对） | 显著 |
| 等价类构造 | 中等 |
| Ground-truth 锚定 | 训练稳定性 |
5. 理论分析
5.1 信息论视角
标准 DPO 的信息量：
$$I_{\text{DPO}} = \sum_{\text{pairs}} I(y_w \succ y_l)$$
GraphDPO 的信息量：
$$I_{\text{GraphDPO}} = I_{\text{DPO}} + I_{\text{transitivity}} + I_{\text{equivalence}}$$
> 信息增益：传递性约束和等价关系提供了额外的结构化信息。
5.2 优化稳定性
GraphDPO 的图结构提供了额外的正则化：
- 传递性约束防止循环偏好（A>B>C>A）
- 等价类消除虚假梯度方向
- 邻域聚合降低单对噪声的影响
6. 与相关工作的联系
6.1 与 Rubric-Grounded RL（Round 19）
Rubric-Grounded RL 用多维评分替代二元奖励。GraphDPO 用图结构替代成对比较——两者都从"更丰富的数据结构"中获得优势。
6.2 与 ExpThink（Round 25）
ExpThink 追踪个人最佳作为动态标准。GraphDPO 的偏好图可以整合这些个人最佳作为主导节点。
6.3 与 Prune-OPD（Round 18）
Prune-OPD 根据兼容性截断蒸馏轨迹。GraphDPO 可以整合兼容性作为边权重——高兼容性对之间的偏好关系更可靠。
---
7. 局限性与未来方向
7.1 动态图更新
当前偏好图基于静态排序。探索在线更新：
- 随着模型能力提升重新评估 rollout 质量
- 增量更新图结构而非重建
7.2 与在线 RL 的整合
GraphDPO 目前主要用于离线数据。与在线 RL 结合：
- PPO/GRPO 中的实时图构建
- 探索-利用权衡在图结构中的形式化
7.3 多维偏好图
当偏好涉及多维度（正确性、简洁性、可读性）时：
- 多维图结构
- Pareto 最优前沿在图中的表示
7.4 不确定性加权
整合 Round 17 的不确定性轮廓：
- 高不确定性 rollout 的边权重降低
- 形成"置信度感知"的偏好图
8. 结论
GraphDPO 揭示了标准 DPO 在处理多 rollout 数据时的结构性信息损失，并通过偏好图提供了原则性的解决方案。其核心贡献在于：
1. 图结构建模：捕获成对方法丢失的传递性和等价关系 2. 等价类构造：消除质量相同响应之间的虚假梯度 3. 线性复杂度：高效的 log-sum-exp 聚合 4. 退火锚定：稳定的早期训练 5. 实证优势：推理和程序合成上的性能提升
在 LLM 对齐日益依赖多 rollout 数据的背景下，GraphDPO 代表了从"成对思维"向"结构化思维"的重要演进。
---
论文详情
| 项目 | 内容 |
|---|---|
| 标题 | Beyond Pairs: Your Language Model is Secretly Optimizing a Preference Graph |
| 作者 | Ning Liu, Chuanneng Sun, Kristina Klinkner, Shervin Malmasi |
| arXiv ID | 2605.08037 |
| 日期 | 2026-05-08 |
| 核心贡献 | GraphDPO；图结构偏好优化；Plackett-Luce 目标；等价类构造；传递性利用；线性复杂度；退火锚定 |
| 关键结果 | 推理和程序合成上优于标准 DPO 和列表排序；全面利用多 rollout 偏好结构 |