💻 computer science

GraphPO: Graph-based Policy Optimization for Reasoning Models

GraphPO introduces a novel graph-based reinforcement learning framework that represents reasoning rollouts as directed acyclic graphs to merge semantically equivalent paths and share information across branches, thereby reducing redundant exploration and advantage-estimation variance while outperforming existing chain- and tree-based methods on reasoning benchmarks.

Original authors: Yuliang Zhan, Xinyu Tang, Jian Li, Dandan Zheng, Weilong Chai, Jingdong Chen, Jun Zhou, Ge Wu, Wenyue Tang, Hao Sun

Published 2026-06-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuliang Zhan, Xinyu Tang, Jian Li, Dandan Zheng, Weilong Chai, Jingdong Chen, Jun Zhou, Ge Wu, Wenyue Tang, Hao Sun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a very smart but slightly repetitive student how to solve a complex math problem or write a piece of code. You don't give them step-by-step instructions; instead, you let them try different approaches, and you only tell them at the very end: "Correct!" or "Incorrect."

This is how current AI models (called Large Reasoning Models) learn. They guess, guess, and guess until they get the right answer. But there are two big problems with this method, which the paper calls GraphPO aims to fix.

The Problem: The "Lonely Explorer" and the "Branching Tree"

1. The Wasted Effort (Chain Method)
Imagine sending 100 students into a maze. Each student walks a completely separate path.

The Issue: Even though they are on different paths, 50 of them might get stuck in the exact same dead end or walk through the same confusing hallway. They are wasting time and energy doing the exact same thing over and over. In AI terms, this is "redundant exploration."

2. The "Tree" Method (The Improvement, but not perfect)
To fix the waste, researchers tried a "Tree" method. Imagine the students start together, and at the first fork in the road, they split up. If two students take the same first turn, they walk together for a bit.

The Issue: This helps a little, but once they split at a second fork, they are on their own again. If two different branches of the tree eventually lead to the same confusing hallway (even if they got there via different routes), the students don't know they are in the same place. They keep exploring that hallway separately, wasting more time. They also can't share the "good news" if one student finds the exit from that hallway; the others keep guessing.

The Solution: The "Smart Map" (GraphPO)

The authors propose GraphPO, which is like giving the students a living, shared map instead of just a tree.

How it works:

The Map (The Graph): Instead of just drawing lines (branches), the AI draws a map where every "room" (a step in the reasoning) is a node.
Spotting Twins (Semantic Merging): As the AI explores, it looks at the "rooms" different paths have reached. If two different paths arrive at a room that feels the same (even if the words used to get there were slightly different), the AI says, "Hey, you two are in the same place!" and merges them into a single spot on the map.
Sharing the Good News (Suffix Sharing): Once two paths are merged, they share everything that comes after that point. If one path finds the correct answer from that merged spot, the other path instantly gets credit for that success without having to walk the rest of the way again.
The "Efficiency" Bonus: The AI also learns to prefer the shortest path to get to a specific "room." If Path A takes 10 steps to get to a good spot, and Path B takes 15 steps to get to the same spot, the AI learns to favor Path A. It's like rewarding the student who takes the shortcut.

The Result: Smarter, Faster, and Less Wasteful

By using this "Smart Map" approach, GraphPO achieves three main things:

No More Wasted Steps: It stops the AI from exploring the same dead ends twice. It redirects the "budget" (computing power) to explore new areas instead of repeating old ones.
Better Learning from Mistakes: Because it merges similar paths, it can tell the AI, "This specific step was good," much earlier than before, even if the final answer wasn't perfect yet. It turns a vague "You got it right at the end" into a clear "This specific move was smart."
Shorter Answers: Since it rewards the shortest path to a solution, the AI learns to be more concise and efficient, cutting out unnecessary chatter.

The Bottom Line

The paper tested this on three different AI models across math problems, coding, and search tasks. The results showed that GraphPO consistently beat the old methods (both the lonely explorers and the branching trees). It solved more problems, used fewer words to do it, and learned faster, all while using the same amount of computing power.

In short, GraphPO teaches AI to stop walking in circles and start sharing a map, making the learning process much smarter and less wasteful.

Technical Summary: GraphPO - Graph-based Policy Optimization for Reasoning Models

1. Problem Statement

Reinforcement Learning with Verifiable Rewards (RLVR) has become the standard paradigm for enhancing Large Reasoning Models (LRMs). However, current RLVR methods face two primary limitations:

Redundant Exploration: Independent sampling of responses often results in different trajectories containing similar intermediate reasoning steps. This leads to wasted computation and limits exploration diversity.
Sparse Reward Signals: RLVR typically relies on binary final-answer rewards. This sparsity makes it difficult to assign credit to specific intermediate reasoning steps that contribute to the final answer.

While tree-based methods (e.g., TreeRL, PROS) address some redundancy by sharing prefixes and providing fine-grained signals at branching points, they still treat diverged branches as independent paths. Consequently, if different branches reach semantically similar intermediate states, they cannot share information, leading to repeated exploration and higher variance in advantage estimation.

2. Methodology: GraphPO

The authors propose GraphPO, a novel RL framework that models reasoning rollouts as a Directed Acyclic Graph (DAG) rather than a chain or a tree.

2.1 Graph Construction and Merging

Structure: In GraphPO, reasoning steps are represented as edges, and intermediate semantic states (summarized from the reasoning path starting from the prompt) are represented as nodes.
Equivalence Classes: The framework incrementally constructs the graph by detecting semantically similar states across different paths using node embeddings (via cosine similarity). When similarity exceeds a threshold $\kappa$ , nodes are merged into equivalence classes.
Budget Reallocation: When a path reaches an existing equivalence class, further expansion is deemed likely redundant. GraphPO halves the next-layer budget for that path (keeping at least one continuation) and reallocates the saved computation to novel frontier states, thereby encouraging broader exploration.

2.2 Graph Reward (Process Supervision from Outcome)

GraphPO converts sparse outcome rewards into dense step-level rewards without requiring annotated process labels:

State Scoring: Each node is assigned a score based on verified answers reachable from it. If a node belongs to an equivalence class, its score is pooled with the scores of other nodes in that class, weighted by a pooling coefficient $w$ .
Step Rewards: The reward for a specific edge (step) is calculated as the difference in state scores between the destination and source nodes, discounted by the similarity between the endpoints. This allows early-stopped branches to receive credit from equivalent partners that successfully reached a correct answer.

2.3 Dual-Group Graph Advantage

To improve both reasoning efficiency and credit assignment, GraphPO introduces a dual-group advantage estimation:

Correctness Group ( $A_{cor}$ ): Compares outgoing steps from the same semantic state. It calculates the advantage of a specific step relative to other steps leaving the same state, providing fine-grained credit assignment.
Efficiency Group ( $A_{eff}$ ): Compares incoming paths that reach the same merged state. It rewards shorter paths (fewer tokens/steps) that reach a useful semantic state, encouraging the policy to find more efficient reasoning trajectories.

2.4 Policy Optimization

The policy is optimized using a PPO-style objective that combines the dual-group advantage ( $A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$ ). The objective function maximizes the expected return while maintaining a KL-divergence constraint relative to a reference policy.

3. Key Contributions

Graph-Based Rollout Framework: GraphPO is the first RL framework to represent reasoning rollouts as a DAG, explicitly aggregating equivalent reasoning states to enable suffix sharing and budget reallocation.
Dual-Group Advantage Estimation: The paper proposes a method to simultaneously optimize for reasoning correctness (by comparing outgoing steps) and reasoning efficiency (by comparing incoming paths), reducing advantage estimation variance.
Process Supervision without Annotations: The method derives dense step-level supervision from sparse outcome rewards by leveraging the graph structure and equivalence classes, eliminating the need for costly Process Reward Model (PRM) annotations.

4. Experimental Results

Experiments were conducted on three LLMs (Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B) across mathematical reasoning benchmarks (AIME24/25, MATH500, GPQA, LiveCodeBench) and agentic search tasks.

Performance: GraphPO consistently outperformed chain-based (GRPO, DAPO) and tree-based baselines (TreeRL, SPO, PROS, TreePO) across all models and datasets under the same token and response budgets. For instance, on the Qwen2.5-7B-Math model, GraphPO achieved an average accuracy of 40.9%, surpassing the best tree-based baseline (PROS at 37.7%).
Exploration Efficiency: GraphPO demonstrated higher exploration efficiency, meaning a larger proportion of computation was allocated to useful reasoning progress rather than redundant expansions. It maintained higher entropy during training compared to tree-based methods, which tend to collapse into specific reasoning patterns faster.
Response Length: GraphPO produced shorter responses than tree-based methods by merging equivalent states and rewarding shorter paths, thereby improving inference efficiency.
Agentic Tasks: The method showed superior performance in deep search and agentic tasks (General AI Assistant, WebWalker, BrowseComp, XBench), validating its applicability to sequential decision-making processes.
Comparison with PRMs: GraphPO outperformed PRM-based methods (ReasonFlux-PRM) without using any additional annotated process data.

5. Significance and Claims

The paper claims that GraphPO provides a practical mechanism to obtain self-emergent process supervision from outcome rewards alone. By modeling rollouts as a graph, it addresses the structural limitations of trees, which cannot represent equivalent states reached by different paths.

The authors assert that GraphPO:

Reduces Variance: Merging equivalent states and pooling downstream evidence lowers the variance of advantage estimation.
Enhances Efficiency: It reallocates computational budgets away from redundant expansions toward diverse exploration and rewards shorter reasoning paths.
Improves Utilization: It stabilizes policy updates by allowing early-stopped branches to receive credit from equivalent successful partners, improving the utilization of the rollout budget.

The work suggests that graph-structured rollouts offer a robust alternative to tree-based methods for scaling the reasoning capabilities of large language models under verifiable reward settings.