GraphDPO: Your Language Model is Secretly Optimizing a Preference Graph

TL;DR

While Direct Preference Optimization (DPO) revolutionized LLM alignment by replacing RL with a simple classification-style objective, it remains bottlenecked by its "pairwise" view of the world. GraphDPO breaks this bottleneck by treating multiple model rollouts not as isolated pairs, but as a Directed Acyclic Graph (DAG). By leveraging the full transitive structure of rankings and introducing ground-truth anchoring, GraphDPO achieves superior performance in mathematical reasoning and coding, setting new benchmarks on GSM8K and MATH-500.

Probing the Pairwise & Listwise Bottleneck

Modern alignment often involves sampling $K$ responses per prompt. Standard DPO breaks these into $O(K^2)$ pairs. This approach is fundamentally flawed for two reasons:

1. Transitivity Loss: Treating $(A\succ B)$ and $(B\succ C)$ as independent updates ignores the global structure that $A$ must dominate $C$.
2. The "Ties" Dilemma: In tasks like coding (APPS) or math (GSM8K), multiple responses often share the same reward (e.g., both are "Correct"). DPO and strict listwise methods (like PRO) struggle to handle these equivalence classes without introducing "spurious gradients"—forcing the model to prefer one correct answer over another nearly identical one.

Methodology: The Graph-Structured Insight

GraphDPO proposes that for every prompt $x$, there exists a latent Preference Graph ${\mathcal{G}}_x$. Instead of a list, the model optimizes against neighborhoods.

1. Preference Graph Representation

The core idea is Equivalence-class Masking. Responses with identical preference signals (e.g., same correctness) form a "Layer" in the DAG. Edges only exist between layers, never within them. This mathematically prevents the model from trying to distinguish between equally good outputs.

2. The Objective Function

GraphDPO uses a local Plackett–Luce model. For a node $i$, the loss is: ${\ell }_i=-ilde{s}_i+\log {\sum }_{k\in \{i\}\cup {\mathcal{N}}^{-}(i)}\exp (ilde{s}_k)$ Where ${\mathcal{N}}^{-}(i)$ is the set of all nodes $i$ dominates. This captures the intuition that a response should be "better" than the pool of everything it outranks.

Figure 1: The GraphDPO pipeline. Note how rollouts are grouped into equivalence classes, forming a layered DAG structure.

3. Ground-Truth Anchoring

To stabilize training, the authors introduce a "Stell-Global Anchor"—the ground truth. By inserting the oracle solution as a dominant node and using an Annealed Schedule, the model is "pulled" towards the right answer heavily in the beginning, with the constraint relaxing as the policy matures.

Experiments: Superior Scaling and Robustness

The researchers tested GraphDPO against a formidable battery of baselines including GRPO, SPIN, and listwise methods like LiPO and PRO.

Key Result: GSM8K & MATH-500

On MATH-500, a benchmark notorious for long reasoning chains, GraphDPO reached 88.87%, significantly outperforming LiPO (85.60%).

Table 1: Performance comparison across mathematical and programming benchmarks.

Ablation: Why Graphs Matter

As shown in the ablation studies, increasing the number of rollouts ($K$) significantly boosts GraphDPO's performance. Because the graph becomes richer with more nodes, the "transitive constraints" become more powerful, allowing the model to learn a more coherent reward landscape.

Critical Analysis & Conclusion

Takeaway: GraphDPO is a elegant bridge between simple pairwise DPO and complex RLHF. It proves that the "secret" to efficient alignment isn't just more data, but better relational structure between the data points we already have.

Limitations:

• The method still relies on the quality of initial rollouts. If the base model fails to generate any correct samples, the internal graph structure (excluding anchoring) provides less signal.
• While $O(K)$ in layered settings, highly irregular partial orders could increase computational overhead.

In conclusion, GraphDPO suggests that our language models are indeed "secretly optimizing preference graphs," and by making that graph explicit, we can unlock significantly higher reasoning capabilities.