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

1. Problem Statement

Current alignment methods for Large Language Models (LLMs), particularly Direct Preference Optimization (DPO), predominantly rely on pairwise preference comparisons. While DPO offers a stable alternative to Reinforcement Learning from Human Feedback (RLHF) by eliminating explicit reward modeling, it faces a fundamental bottleneck when applied to practical data collection regimes.

In many real-world scenarios (e.g., reasoning, program synthesis), training data consists of multiple rollouts per prompt that are ranked via human judgment, execution-based verification, or heuristics. Standard DPO handles this by decomposing these multi-sample rankings into independent pairwise comparisons ($O(K^2)$ instances). This reductionist approach introduces three critical limitations:

1. Loss of Transitivity: It discards the global transitive structure inherent in ranked lists (e.g., if $A \succ B$ and $B \succ C$, standard DPO does not explicitly enforce $A \succ C$).
2. Redundant/Conflicting Supervision: It treats isolated pairs as separate constraints, potentially introducing noise when samples are tied or when the ranking is partial.
3. Incompatibility with Partial Orders: Many evaluation signals (e.g., correctness in math or code) produce equivalence classes or partial orders that cannot be faithfully represented as strict total-order lists required by existing listwise methods (e.g., PRO, LiPO).

2. Methodology: Graph Direct Preference Optimization (GraphDPO)

The authors propose GraphDPO, a principled generalization of DPO that shifts preference modeling from isolated pairs or strict lists to directed acyclic preference graphs (DAGs).

2.1 Preference Graph Representation

For a given prompt $x$ and a set of $K$ candidate responses $\{y_1, \dots, y_K\}$, GraphDPO constructs a DAG $G_x = (V, E)$:

• Nodes: Represent the sampled responses.
• Edges: Encode dominance relations. An edge $i \to j$ exists if response $y_i$ is preferred over $y_j$ ($y_i \succ_x y_j$).
• Equivalence Classes: To handle discrete signals (e.g., correct/incorrect) where multiple responses share the same preference level, the method groups responses into equivalence classes $C_1 \succ C_2 \succ \dots \succ C_G$. Edges are only permitted between different classes; intra-class edges are masked. This prevents spurious gradients from arbitrarily ordering tied samples.

2.2 Graph-Structured Objective

GraphDPO optimizes a likelihood defined over dominated neighborhoods. For each response $y_i$, the model is trained to assign a higher score than all responses it dominates ($N^-(i)$).

• Local Loss: Using a Plackett–Luce (PL) inspired formulation, the loss for node $i$ is:
  $$\ell_i = -\tilde{s}_i + \log \sum_{k \in \{i\} \cup N^-(i)} \exp(\tilde{s}_k)$$
  where $\tilde{s}_i$ is the centered log-ratio score relative to a reference policy.
• Global Aggregation: The total loss aggregates these local terms. This formulation enforces global transitivity: if $y_i$ dominates $y_j$, the objective encourages $s_i > s_j$, and transitive relations propagate naturally through shared neighborhoods.
• Complexity: Despite leveraging the full graph, the method maintains linear complexity $O(K)$ per prompt under the equivalence-class (layered DAG) construction, avoiding the $O(K^2)$ enumeration of pairwise comparisons or the permutation normalization of listwise methods.

2.3 Ground-Truth Anchoring

When verified solutions (oracle responses) are available, GraphDPO integrates them as dominant nodes in the graph.

• Anchoring Loss: A separate term encourages the oracle response to dominate all generated responses.
• Annealed Schedule: To stabilize early training while preserving flexibility later, the weight of the anchoring term $\lambda_{gt}(t)$ is initialized high and gradually decayed to 1.0. This prevents the policy from overfitting to the oracle too early while ensuring consistent preference propagation.

2.4 Training Objective

The final objective combines the graph loss, optional ground-truth anchoring, and a token-level KL regularization term to prevent deviation from the reference policy:
$$L(x) = L_{graph}(x) + \lambda_{gt}(t) L_{anchor}(x) + \lambda_{KL}(t) L_{KL}(x)$$
Standard pairwise DPO is recovered as a special case when $K=2$ with a strict preference.

3. Key Contributions

1. Graph-Structured Preference Optimization: GraphDPO reformulates preference learning to construct a globally consistent preference DAG over multiple rollouts, enforcing transitivity and recovering standard DPO as a special case.
2. Groupwise Ranking with Tied-Preference Handling: It naturally supports equivalence classes, performing comparisons only across preference groups to avoid spurious gradients from near-identical samples.
3. Linear-Time Full-Graph Learning: The method captures global ranking information via efficient log-sum-exp aggregation over dominated sets, avoiding the computational overhead of pairwise enumeration or listwise permutation normalization.
4. Stabilizing Ground-Truth Anchoring: It introduces an annealed anchoring mechanism that stabilizes early optimization using verified solutions without sacrificing policy diversity in later stages.

4. Experimental Results

The authors evaluated GraphDPO on mathematical reasoning (GSM8K, MATH-500) and program synthesis (APPS) benchmarks using Qwen3 base models.

• Performance: GraphDPO consistently outperformed baselines including Supervised Fine-Tuning (SFT), GRPO, SPIN, and listwise methods (PRO, LiPO).
  • GSM8K: Achieved 92.42% (without anchoring) and 92.75% (with anchoring), surpassing the best listwise baseline (LiPO: 89.23%).
  • MATH-500: Achieved 87.40% (w/o GT) and 88.87% (w/ GT), showing a larger gap over listwise methods compared to GSM8K, suggesting benefits scale with task complexity.
  • APPS: Achieved 72.93% (w/o GT) and 73.76% (w/ GT), outperforming group-based (GRPO) and listwise methods.
• Ablation Findings:
  • Graph vs. Listwise: The performance gap between GraphDPO and PRO (which removes graph edge encoding) confirms that modeling partial orders and transitive structure is superior to strict total-order assumptions.
  • Rollout Count ($K$): Increasing $K$ generally improved performance by inducing richer preference graphs, allowing the model to leverage transitive dominance relations not observable in pairwise sampling.
  • Anchoring: Ground-truth anchoring provided consistent gains, particularly for smaller rollout budgets and harder tasks (MATH-500), where it stabilized preference propagation.

5. Significance and Claims

The paper claims that modeling preference structure as graphs provides a scalable and robust alternative to both pairwise and listwise alignment objectives.

• Scalability: By maintaining linear complexity while capturing global structure, GraphDPO is suitable for rollout-heavy alignment settings common in reasoning and coding tasks.
• Robustness: The method handles partial orders, equivalence classes, and sparse comparability relations that break strict listwise assumptions.
• Inductive Bias: The results suggest that explicitly modeling structured relationships among rollouts (transitivity and dominance) is critical for scaling alignment to complex problem domains where simple ordering assumptions fail.

The authors conclude that GraphDPO offers a simple, effective inductive bias for LLM alignment, bridging the gap between the simplicity of DPO and the structural richness of multi-sample rankings.