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

• URL: http://arxiv.org/abs/2605.08037v1
• Date: Fri, 08 May 2026 17:26:14 GMT
• Title: Beyond Pairs: Your Language Model is Secretly Optimizing a Preference Graph
• Abstract summary: We propose a principled generalization of DPO that operates over directed acyclic preference graphs induced by rollout rankings.<n>GraphDPO encodes dominance relations as edges and optimize a graph-structured Plackett--Luce-inspired objective.<n> Experiments on reasoning and program tasks demonstrate superior performance, suggesting that graph-structured preference modeling is a scalable and robust alternative to pairwise and listwise alignment objectives.
• Score: 17.030746750590758
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Direct Preference Optimization (DPO) aligns language models using pairwise preference comparisons, offering a simple and effective alternative to Reinforcement Learning (RL) from human feedback. However, in many practical settings, training data consists of multiple rollouts per prompt, inducing rich preference structure that pairwise DPO fails to exploit. Collapsing such data into independent pairs discards transitivity, introduces redundant or conflicting supervision, and can lead to unstable optimization. We propose Graph Direct Preference Optimization (GraphDPO), a principled generalization of DPO that operates over directed acyclic preference graphs induced by rollout rankings. GraphDPO encodes dominance relations as edges and optimizes a graph-structured Plackett--Luce-inspired objective that aggregates supervision over graph neighborhoods, enforcing transitivity while recovering standard DPO as a special case. To handle discrete or sparse signals, we introduce an equivalence-class construction where responses with identical preferences form graph layers, and intra-layer edges contribute zero loss, preventing spurious gradients. Despite leveraging full graph structure, GraphDPO maintains linear per-prompt complexity via efficient log-sum-exp aggregation. We further incorporate optional ground-truth anchoring by inserting verified solutions as dominant nodes and applying an annealed schedule that stabilizes early training while gradually relaxing oracle supervision. Experiments on reasoning and program synthesis tasks demonstrate superior performance, suggesting that graph-structured preference modeling is a scalable and robust alternative to pairwise and listwise alignment objectives.

Related papers

• Adaptive Graph Refinement and Label Propagation with LLMs for Cost-Effective Entity Resolution [16.32872612569802]
  Dirty entity resolution (ER) identifies records referring to the same real-world entity from a single, messy dataset.<n>We propose Alper, a unified framework that integrates matching and clustering steps into an iterative probabilistic label propagation process.<n>Our experiments over eight benchmark datasets demonstrate that Alper is consistently superior to state-of-the-art cascaded pipelines.
  arXiv  Detail & Related papers  (2026-05-25T13:11:33Z)
• Matching Features, Not Tokens: Energy-Based Fine-Tuning of Language Models [102.20309135516186]
  Cross-entropy (CE) training provides dense and scalable supervision for language models.<n>We introduce a feature-matching objective for language-model fine-tuning.<n>To optimize this objective efficiently, we propose energy-based fine-tuning.
  arXiv  Detail & Related papers  (2026-03-12T17:57:50Z)
• Agentic Planning with Reasoning for Image Styling via Offline RL [66.10749901925941]
  Direct prompt-based editing fails on complex transformations because vague and subjective prompts often require nuanced understanding of what should be changed in the image.<n>We present a tool-based agentic RL post-training framework that addresses this through structured planning with chain-of-thought reasoning.
  arXiv  Detail & Related papers  (2026-03-07T11:14:37Z)
• Graph-GRPO: Stabilizing Multi-Agent Topology Learning via Group Relative Policy Optimization [7.961090665261694]
  We propose Graph-GRPO, a novel topology optimization framework that integrates Group Relative Policy Optimization.<n>By normalizing rewards across the sampled group, our method effectively mitigates the noise derived from task difficulty variance and enables fine-grained credit assignment.
  arXiv  Detail & Related papers  (2026-03-03T07:45:40Z)
• Linear Preference Optimization: Decoupled Gradient Control via Absolute Regularization [13.97375970293678]
  DPO (Direct Preference Optimization) has become a widely used offline preference optimization algorithm due to its simplicity and training stability.<n>We propose Linear Preference Optimization (LPO), a novel alignment framework featuring three key innovations.<n>First, we introduce gradient decoupling by replacing the log-sigmoid function with an absolute difference loss, thereby isolating the optimization dynamics.<n>Second, we improve stability through an offset constraint combined with a positive regularization term to preserve the chosen response quality.<n>Third, we implement controllable rejection suppression using gradient separation with straightforward estimation and a tunable coefficient that linearly regulates the descent of the rejection probability.
  arXiv  Detail & Related papers  (2025-08-20T10:17:29Z)
• VAGPO: Vision-augmented Asymmetric Group Preference Optimization for Graph Routing Problems [27.70647397895125]
  Graph routing problems play a vital role in web-related networks, where finding optimal paths across graphs is essential.<n>Recent data-driven optimization methods have made significant progress, yet they often face limitations in training efficiency and generalization to large-scale instances.<n>We propose a novel Vision-augmented Asymmetric Group Preference Optimization (VAGPO) approach, which captures both spatial structure and temporal dependencies.
  arXiv  Detail & Related papers  (2025-08-03T14:19:12Z)
• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing [58.52119063742121]
  Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model performance.<n>This paper addresses the question of how to optimally combine the model's predictions and the provided labels.<n>Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels.
  arXiv  Detail & Related papers  (2025-05-21T07:16:44Z)
• Bridging and Modeling Correlations in Pairwise Data for Direct Preference Optimization [75.1240295759264]
  We propose an effective framework for Bridging and Modeling Correlations in pairwise data, named BMC.<n>We increase the consistency and informativeness of the pairwise preference signals through targeted modifications.<n>We identify that DPO alone is insufficient to model these correlations and capture nuanced variations.
  arXiv  Detail & Related papers  (2024-08-14T11:29:47Z)
• Self-Augmented Preference Optimization: Off-Policy Paradigms for Language Model Alignment [104.18002641195442]
  We introduce Self-Augmented Preference Optimization (SAPO), an effective and scalable training paradigm that does not require existing paired data. Building on the self-play concept, which autonomously generates negative responses, we further incorporate an off-policy learning pipeline to enhance data exploration and exploitation.
  arXiv  Detail & Related papers  (2024-05-31T14:21:04Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.