Beyond Pairs: Your Language Model is Secretly Optimizing a Preference Graph¶

会议: NeurIPS 2026
arXiv: 2605.08037
OpenReview: https://openreview.net/forum?id=eIAc9sNGjK
领域: LLM对齐
关键词: 偏好优化, 直接偏好优化, 图结构偏好, 等价类掩码, 语言模型对齐

一句话总结¶

针对传统 DPO 强行将多采样候选切解为独立样本对而丢弃偏好传递性的缺陷，本文提出 GraphDPO，将采样候选项构建为有向无环偏好图并沿被支配邻域执行基于 Plackett–Luce 的局部归一化损失，在等价类分层下实现线性时间复杂度并显著提升数学推理与程序合成性能。

研究背景与动机¶

在大语言模型（LLM）的对齐流程中，直接偏好优化（DPO）通过对隐式奖励函数进行重参数化，消除了显式奖励模型训练与强化学习策略采样的不稳定因素，成为 RLHF 的核心轻量化替代方案。然而，主流 DPO 及其变体本质上依赖于孤立的成对比较（pairwise comparisons），即假设训练样本由单独的优选-劣选二元对组成。这种假设与实际数据采集场景存在显著脱节：在复杂推理和程序合成任务中，通常针对同一输入 prompt 采样多个候选解（rollouts），并通过代码执行测试、单元测试通过率或符号判定对其进行联合评估。

当面对同一 prompt 下的 $K$ 个多路候选时，标准做法是将其笛卡尔积强行拆解为 $O(K^2)$ 个独立的二元样本对分别施加约束。这种朴素的二元还原带来了三大严重瓶颈：第一，它割裂了候选集内部固有的传递性与全局偏好拓扑，导致模型在局部成对约束中陷入优化震荡；第二，大量高度相似或重复的二元对引入了冗余甚至冲突的监督梯度；第三，现有尝试利用列表级排序（Listwise LTR，如 PRO 或 LiPO）的方法通常强行假设严格的全序排列（total ordering），然而在基于离散执行信号（如测试通过与否）的实际场景中，数据往往呈现为偏序（partial order）或等价类，列表级方法强行对平局样本进行伪全序排序，反而注入了虚假的噪声梯度。

本文的切入视角是跳出成对和严格列表的二元对立，将每个 prompt 下的全部候选及其优劣关系形式化为有向无环图（DAG），并以等价类构造消除平局样本之间的冗余计算。核心 idea：将多候选采样构建为有向无环偏好图（DAG），在等价类掩码下自然包容平局与不可比样本，并通过在各节点的被支配邻域上聚合 Plackett–Luce 局部对数和指数目标，实现保传递性、抗噪声且具有线性计算复杂度的结构化偏好对齐。

方法详解¶

整体框架¶

GraphDPO 的整体管线围绕单一 prompt 下的 $K$ 个生成候选展开。对于给定的输入 prompt $x$，策略模型采样得到 $K$ 个候选响应 $\{y_1, \dots, y_K\}$，验证器（如单元测试执行器或数学规则校验器）为每个响应赋予离散或连续的质量信号。算法首先将具有相同质量信号的候选划归为同一个等价类，由此诱导出一个天然的分层有向无环图 $\mathcal{G}_x=(V, E)$。图中节点代表候选响应，有向边仅存在于严格优胜的等价类向劣质等价类之间，同一等价类内的候选之间不设边。随后，GraphDPO 以每个节点及其所有被支配后代构成的局部子集为基准，计算局部 Plackett–Luce 似然损失，并沿分层结构进行线性时延的前缀聚合更新。当存在经由外部验证的真实解（Ground-Truth）时，还可将其作为全局支配锚点插入图中，通过退火加权引导早期训练的快速收敛。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入 Prompt 及多路采样候选<br/>采样 K 个 Rollouts"] --> B["等价类划分与偏好 DAG 构建<br/>离散信号分层 + 平局与不可比无边掩码"]
    B --> C["被支配邻域局部选择似然<br/>基于 Plackett-Luce 的 Softmax 归一化"]
    C --> D["三趟扫描线性复杂度聚合<br/>Class Sums + 后缀和累加 Z_g"]
    D --> E["动态退火真实解锚定<br/>lambda_gt 早期引导与渐进放松"]
    E --> F["策略参数更新<br/>结合 Token 级 KL 正则化防漂移"]

关键设计¶

1. 等价类掩码与偏好有向无环图构建

传统方法在面对得分相同的候选时，要么随意丢弃，要么人为引入随机排序导致模型对本质相同的输出学习到虚假的相对偏好。GraphDPO 将偏好关系 $\succ_x$ 表示为有序等价类序列 $\mathcal{C}_1 \succ_x \mathcal{C}_2 \succ_x \dots \succ_x \mathcal{C}_G$。在邻接矩阵 $A$ 中，若 $y_i \in \mathcal{C}_g$ 且 $y_j \in \mathcal{C}_h$，则边权定义为： $$A_{ij} = \begin{cases} 1 & g < h \\ 0 & g = h \end{cases}$$ 该掩码设计确保同一等价类内的样本之间不存在有向边，因而在后续梯度反向传播中贡献严格为零的损失。对于无法直接对比的候选（例如在 APPS 评测中通过了相同数量但不同用例集合的代码），它们被一视同仁地放入同一等价层级，彻底规避了因虚假排序引入的破坏性梯度。

2. 基于被支配邻域的局部 Plackett–Luce 损失

为了在无需进行全排列排列概率归一化的前提下捕获图拓扑传递性，GraphDPO 定义每个节点 $i$ 的被支配邻域为 $\mathcal{N}^-(i) = \{j \in V : A_{ij} = 1\}$。记模型相对于参考策略的居中隐式奖励分数为 $\tilde{s}_i = s_\theta(x, y_i) - \frac{1}{K}\sum_{j=1}^K s_\theta(x, y_j)$，其中 $s_\theta(x, y) = \beta (\log \pi_\theta(y \mid x) - \log \pi_{\text{ref}}(y \mid x))$。每个具备非空劣势邻域的节点定义一个多项 Logit 选择任务：候选 $y_i$ 应当在其自身与所有劣势候选所组成的候选池中被选为最优，其对应的局部损失为： $$\ell_i = -\tilde{s}_i + \log \sum_{k \in \{i\} \cup \mathcal{N}^-(i)} \exp(\tilde{s}_k)$$ 全图损失 $\mathcal{L}_{\text{graph}}(x)$ 则对所有具备非空被支配邻域的节点取平均。该目标在数学上诱导了自适应梯度重加权：一个劣质节点被越多祖先节点支配，其接收到的负梯度就越多；而在 Softmax 归一化中，当前打分极低的噪声样本仅贡献按指数级衰减的小幅权重，形成天然的课程学习效应。

3. 三趟扫描线性时间复杂度算法

显式遍历成对边或对各节点的支配集合分别计算 Log-Sum-Exp 会耗费 $O(|E|) \le O(K^2)$ 的开销。鉴于等价类分层结构的天然嵌套性质——即同一层级的所有节点共享完全相同的劣质邻域 $\mathcal{N}^-(i) = \bigcup_{g' > g} \mathcal{C}_{g'}$，GraphDPO 提出了三趟扫描算法将其压缩至 $O(K)$ 复杂度： - 第一趟（分桶与组内求和）：遍历 $K$ 个响应，计算各等价层级的得分指数和 $S_g = \sum_{k \in \mathcal{C}_g} \exp(\tilde{s}_k)$，开销为 $O(K)$； - 第二趟（后缀累加扫描）：自底向上计算后缀和 $Z_g = S_g + Z_{g+1}$（其中 $Z_{G+1} = 0$），每个层级 $g$ 的后代集合指数和即为 $Z_{g+1}$，开销为 $O(G) \le O(K)$； - 第三趟（节点损失赋值）：每个节点直接利用其所属层级对应的预计算后缀和计算 $\ell_i = -\tilde{s}_i + \log(\exp(\tilde{s}_i) + Z_{g+1})$，单节点开销 $O(1)$，总开销 $O(K)$。整体计算开销严格为 $O(K)$，使得在大 rollout 数量下训练依然具备极致吞吐。

4. 动态退火真实解锚定机制

在数学推理与程序合成等高难度任务中，初始策略往往生成质量极差，全部 $K$ 个候选可能均属错误解，导致偏好图退化为单层甚至无有效监督信号。当存在可用的真实参考答案 $y_{\text{gt}}$ 时，GraphDPO 将其作为独立显式主导节点接入图拓扑，构建针对所有劣于真实解集合 $V_{\text{worse}} = \{j \in V : y_{\text{gt}} \succ_x y_j\}$ 的单向锚定损失： $$\mathcal{L}_{\text{anchor}}(x) = -\tilde{s}_{\text{gt}} + \log \sum_{k \in \{\text{gt}\} \cup V_{\text{worse}}} \exp(\tilde{s}_k)$$ 为避免模型对静态参考答案产生过拟合从而限制自身推理多样性，锚定权重采用线性退火策略 $\lambda_{\text{gt}}(t)$。在训练初期设置较高的权重（初始化建议为 $K/4$ 至 $K/3$ 范围），以对齐梯度规模并稳定冷启动；随着策略探索能力的提升，权重平滑衰减至 $1.0$，将主要优化空间让渡给自采样图结构。

损失函数 / 训练策略¶

除图偏好损失与锚定项外，为防止策略生成分布过度偏离基座模型，GraphDPO 引入了序列平均标记级（token-level）反向 KL 散度正则项 $\mathcal{L}_{\text{KL}}(x)$。最终的单步训练总目标形式为： $$\mathcal{L}(x) = \mathcal{L}_{\text{graph}}(x) + \lambda_{\text{gt}}(t) \mathcal{L}_{\text{anchor}}(x) + \lambda_{\text{KL}}(t) \mathcal{L}_{\text{KL}}(x)$$ 其中 $\lambda_{\text{KL}}(t)$ 采用预热-衰减调度直至归零。当 $K=2$ 且存在严格偏好时，由于 $\mathcal{L}_{\text{graph}}(x) = -\tilde{s}_1 + \log(\exp(\tilde{s}_1) + \exp(\tilde{s}_2)) = -\log \sigma(\tilde{s}_1 - \tilde{s}_2)$，GraphDPO 完美退化为标准的二元 DPO 目标。

实验关键数据¶

主实验¶

实验选用数学推理基准 GSM8K、MATH-500 以及程序代码合成基准 APPS，在推理专用模型 Qwen3-4B-Thinking-2507 及指令通用模型 Qwen3-4B-Instruct-2507 上进行验证，各偏好对齐方法统一在每个 prompt 采用 $K=8$ 个 rollouts。测试结果汇总如下表：

方法	GSM8K 准确率 (%)	MATH-500 准确率 (%)	APPS 单元测试通过率 (%)	说明
OTS (Off-the-shelf)	80.89	32.80	44.22	零样本未对齐基座模型
SFT	84.15	54.80	59.08	仅在正样本轨迹上监督微调
GRPO	85.59 ± 0.30	84.00 ± 0.28	68.67 ± 1.18	组内奖励归一化强化学习
DPO	87.05 ± 0.78	82.70 ± 0.42	68.35 ± 1.06	采用 top-1/bottom-1 极值二元对
SPIN	88.10 ± 0.86	79.80 ± 0.57	65.20 ± 1.13	迭代自博弈成对更新
PRO	88.82 ± 0.16	82.30 ± 1.84	68.84 ± 0.37	严格列表 Plackett-Luce 排序
LiPO	89.65 ± 0.59	85.40 ± 0.28	68.96 ± 0.51	LambdaLoss 列表排序对齐
MPO	89.98 ± 0.35	84.50 ± 0.42	67.72 ± 0.73	集合级对比多样本 DPO
SWEPO	91.29 ± 0.11	85.00 ± 0.85	67.38 ± 1.44	加权组级 DPO 变体
GraphDPO (无真实解锚定)	92.42 ± 0.33	87.40 ± 0.20	72.93 ± 0.72	仅利用生成候选项构造偏好 DAG
GraphDPO (带真实解锚定)	92.75 ± 0.09	88.87 ± 0.61	73.76 ± 0.19	引入退火真实解节点作为全局锚点

消融实验¶

针对候选样本采样数 $K$ 以及真实解锚定（GT）机制在 GSM8K 上的消融分析如下表所示：

采样组大小 ($K$)	无真实解锚定 (w/o GT) (%)	带真实解锚定 (w/ GT) (%)	锚定增益 ($\Delta$)	说明
$K=2$	88.78	91.81	+3.03	退化为单边图，GT 提供强有力的正向锚点
$K=4$	92.04	92.12	+0.08	图结构初步成型，锚定依赖减弱
$K=6$	92.13	92.65	+0.52	拓扑渐趋丰富
$K=8$	92.42	92.75	+0.33	增益趋于饱和，充分利用自生成图拓扑

此外，在针对 APPS 基准按实际生成的偏好图深度（Realized Layers）进行分层评测时，模型相对于基座策略的收益呈现单调递增趋势：在仅形成 2 层（二元对立）的样本上，增益为 +16.8%；在形成 3 层的样本上增益跃升至 +25.9%；而在实现 $\ge 4$ 个精细等价层级的子集上，增益高达 +36.2%（样本数 $n=13$）。

关键发现¶

平局掩码是克服列表排序瓶颈的核心：对比 PRO 与 GraphDPO（无 GT），两者均基于 Plackett-Luce 选择机制，但在 GSM8K 上 GraphDPO 取得了 +3.60% 的显著领先。原因在于 GSM8K 的验证信号是二元的，多个正确解之间以及多个错误解之间是等价平局；PRO 强行对同等样本引入假想全序，而 GraphDPO 通过等价类掩码清除了同层内的无意义竞争与噪声梯度。
任务难度越大，图拓扑优势越明显：在推理深度显著增加的 MATH-500 上，GraphDPO 超越前序最强基线 LiPO 达 3.47 个百分点；在具备多层连续通过率反馈的 APPS 代码生成上，领先优势进一步扩大至 4.80 个百分点。
GT 锚定在小采样与高难度冷启动阶段最具价值：在 $K=2$ 时真实解锚定带来 +3.03% 的暴涨；而在 MATH-500 这种错误率极高的复杂任务上，真实解锚定同样贡献了 +1.47% 的净提升，证明其在缺乏优质自生成样本时具有出色的防策略崩溃功能。

亮点与洞察¶

将对齐建模范式从有序列表推广至偏好有向图：指出了成对（Pairwise）与列表式（Listwise）对齐方法在处理离散评测信号时的理论缺陷，将经典 DPO、完全链式全序、等价平局以及不可比样本在统一图拓扑公式下进行了优雅的数学统一。
后缀扫描实现线性复杂度 Log-Sum-Exp 聚合：巧妙利用了等价类层级结构的嵌套性，设计出仅需三趟数组扫描的纯矩阵向量化计算流程，使整图在 $K$ 个节点下的损失计算时间由 $O(K^2)$ 降低至 $O(K)$，兼具极高的工程执行效率与理论严谨性。
天然的课程学习与自适应抗噪机制：梯度理论推导表明，最劣质的解由于处于更多节点的被支配邻域中，天然累积了更大幅度的修正梯度；而基于 Softmax 的指数权重又自动衰减了远离决策边界的异常解影响，使得模型在复杂探索中极为稳定。

局限与展望¶

依赖离散评测环境下的分层结构假设：当前所证明的 $O(K)$ 线性算法严格建立在能够将样本划分为全序等价层级的图结构上；对于通用复杂非层级偏序图或带不确定性权重的图拓扑，算法复杂度仍会退化至 $O(|E|)$。
真实解轨迹的格式先验偏差：实验中构造的 Ground-Truth 轨迹是通过将参考答案用模型私有的 <think>...</think> 标签包装而成，这种合成方式与模型原生策略分布较为接近，在参考答案格式与模型策略风格差异巨大的真实场景下，锚定增益可能面临衰减。
长程 Agent 轨迹对齐扩展空间：未来工作可进一步探索将 GraphDPO 拓展至多步智能体交互场景，利用子目标执行的局部图结构来解决更长流程的信用分配难题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将多候选偏好学习系统化形式化为等价类分层偏好图，并推导出与 DPO 兼容的线性时间局部 Plackett-Luce 损失。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖 GSM8K、MATH-500、APPS 三大数学与代码推理基准，对比 8 类强基准并配以详尽的图深度与采样规模消融。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密自洽，理论分析深入，算法设计与实现细节极其清晰。
价值: ⭐⭐⭐⭐⭐ 为大模型推理阶段的探索对齐提供了一种计算开销低、抗平局噪声且理论上限更高的结构化新范式。

采样组大小 (\(K\))	无真实解锚定 (w/o GT) (%)	带真实解锚定 (w/ GT) (%)	锚定增益 (\(\Delta\))	说明
\(K=2\)	88.78	91.81	+3.03	退化为单边图，GT 提供强有力的正向锚点
\(K=4\)	92.04	92.12	+0.08	图结构初步成型，锚定依赖减弱
\(K=6\)	92.13	92.65	+0.52	拓扑渐趋丰富
\(K=8\)	92.42	92.75	+0.33	增益趋于饱和，充分利用自生成图拓扑