GraphPO: Graph-based Policy Optimization for Reasoning Models

• URL: http://arxiv.org/abs/2606.18954v1
• Date: Wed, 17 Jun 2026 11:37:54 GMT
• Title: GraphPO: Graph-based Policy Optimization for Reasoning Models
• Abstract summary: Reinforcement Learning with Verifiable Rewards (RLVR) has become a standard paradigm for enhancing the capability of large reasoning models.<n>Tree-based methods partly address this problem by sharing prefixes and comparing branches from the same prefix to provide fine-grained signals.<n>We propose GraphPO, a novel RL framework that represents rollouts as a directed acyclic graph, with reasoning steps as edges and semantic states summarized from the reasoning paths as nodes.
• Score: 39.010538168884786
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement Learning with Verifiable Rewards (RLVR) has become a standard paradigm for enhancing the capability of large reasoning models. RLVR typically samples responses independently and optimizes the policy using from final answers. This paradigm has two limitations. First, independently responses often contain similar intermediate reasoning steps, causing redundant exploration and wasted computation. Second, sparse final-answer rewards make it hard to identify useful steps. Tree-based methods partly address this problem by sharing prefixes and comparing branches from the same prefix to provide fine-grained signals. However, tree branches are still expanded independently. When different branches reach similar reasoning states, they cannot share information and repeat similar exploration. Moreover, tree-based methods ignore such dispersion and only perform local comparisons within separate branches, which can lead to higher variance in advantage estimation. To address this challenge, we propose GraphPO (Graph-based Policy Optimization), a novel RL framework that represents rollouts as a directed acyclic graph, with reasoning steps as edges and semantic states summarized from the reasoning paths as nodes. GraphPO merges semantically equivalent reasoning paths into equivalence classes, allowing them to share suffixes and reallocating budget away from redundant expansions to diverse exploration. Furthermore, we assign efficiency advantages to incoming edges and correctness advantages to outgoing edges, thereby improving inference efficiency while deriving process supervision from outcome. Theory shows that GraphPO reduces advantage-estimation variance and enhances reasoning efficiency. Experiments on three LLMs across reasoning and agentic search benchmarks show that GraphPO consistently outperforms chain- and tree-based baselines with the same token budgets or response budgets.

Related papers

• Branching Policy Optimization: Sandbox-Native Language Agent Reinforcement Learning [14.640786318359709]
  Branching Policy Optimization (BPO) is a sandbox-native RL algorithm that snapshots the sandbox at high-entropy decision points along a backbone trajectory.<n>We prove this estimator is unbiased and has strictly lower variance than the trajectory-level baseline.<n>BPO improves success by 3.6--6.1 absolute points over GRPO and RLOO at matched compute, halves gradient-norm variance, and matches the best baseline using 38% fewer policy updates.
  arXiv  Detail & Related papers  (2026-07-15T09:37:36Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• Graph-GRPO: Dependency-Aware Credit Assignment for Generative E-commerce Search Relevance [7.682863634260091]
  We present Graph-GRPO, a graph-structured extension of GRPO for relevance reasoning.<n>It propagates outcome-level rewards over the graph to derive step-level credit signals.<n>We also introduce a main-loss-driven controller that adaptively adjusts edge-wise credit-propagation coefficients.
  arXiv  Detail & Related papers  (2026-05-29T08:36:08Z)
• Graph-Based Chain-of-Thought Pruning for Reducing Redundant Reflections in Reasoning LLMs [4.494151943799445]
  In this work, we argue that a major source of such redundancy is inefficient reflection, which often manifests in two problematic patterns.<n>Specifically, we convert each linear CoT into a directed acyclic graph (DAG) with explicit dependency edges.<n>Experiments show that our approach reduces the average reasoning tokens by 42% while maintaining or improving accuracy.
  arXiv  Detail & Related papers  (2026-04-07T09:46:03Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• Reinforced Efficient Reasoning via Semantically Diverse Exploration [73.41112984160992]
  Reinforcement learning with verifiable rewards (RLVR) has proven effective in enhancing the reasoning of large language models (LLMs)<n>We propose reinforced efficient reasoning via semantically diverse explorations, i.e., ROSE, for LLMs.<n>Our method incorporates a semantic-entropy-based branching strategy and an $varepsilon$-exploration mechanism.
  arXiv  Detail & Related papers  (2026-01-08T15:56:44Z)
• TeaRAG: A Token-Efficient Agentic Retrieval-Augmented Generation Framework [62.66056331998838]
  TeaRAG is a token-efficient agentic RAG framework capable of compressing both retrieval content and reasoning steps.<n>Our reward function evaluates the knowledge sufficiency by a knowledge matching mechanism, while penalizing excessive reasoning steps.
  arXiv  Detail & Related papers  (2025-11-07T16:08:34Z)
• ThoughtProbe: Classifier-Guided LLM Thought Space Exploration via Probing Representations [22.84446651161078]
  ThoughtProbe is a novel inference framework that leverages the hidden reasoning features of Large Language Models (LLMs) to improve their reasoning performance.<n>We harness these hidden representations as discriminative signals to guide the tree structured response space exploration.<n>Our framework's comprehensive exploration not only covers valid reasoning chains but also effectively identifies them, achieving significant improvements across multiple arithmetic reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-10-31T10:40:19Z)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)

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.