graphpo-policy-optimization-reasoning

name	graphpo-policy-optimization-reasoning
description	Graph-based Policy Optimization (GraphPO) for reasoning models. Represents rollouts as DAGs, merges semantically equivalent paths, and improves advantage estimation variance through graph structure.
version	1.0.0
tags	["reinforcement-learning","reasoning","graph-optimization","policy-optimization","DAG","RLVR"]
activation_keywords	["graph-based policy","DAG rollouts","semantic equivalence","reasoning graph","advantage variance","process supervision","token budget","reasoning optimization"]

GraphPO: Graph-based Policy Optimization

Overview

Reinforcement Learning framework for reasoning models that represents rollouts as directed acyclic graphs (DAGs). Merges semantically equivalent reasoning paths, reallocates budget to diverse exploration, and provides finer-grained advantage estimation than tree-based methods.

Problem Context

Traditional RLVR (Reinforcement Learning with Verifiable Rewards) limitations:

1. Independent sampling: Similar intermediate steps → redundant exploration
2. Sparse rewards: Final-answer only → hard to identify useful steps
3. Tree limitations: Independent branch expansion, no cross-branch sharing
4. High variance: Local comparisons within separate branches

Core Methodology

1. DAG Representation of Rollouts

Traditional: Chain → Tree → DAG

Chain: step1 → step2 → step3 → step4
Tree:  step1 → [step2a, step2b] → [step3a, step3b, step3c]
DAG:   nodes (semantic states) + edges (reasoning steps)

Graph Construction

# Nodes: Semantic states (summarized from reasoning paths)
node = summarize_semantic_state(reasoning_path)

# Edges: Individual reasoning steps
edge = reasoning_step

# Directed Acyclic Graph structure
graph = {
    nodes: [state_1, state_2, ..., state_n],
    edges: [(state_i, step, state_j)]
}

2. Semantic Equivalence Merging

Key Innovation

When different branches reach similar reasoning states:

• Tree: Continue independently (duplicate work)
• Graph: Merge into equivalence classes, share suffixes

def merge_equivalent_states(graph, similarity_threshold=0.95):
    # Identify semantically equivalent nodes
    equivalence_classes = {}
    
    for node in graph.nodes:
        # Semantic similarity check
        for existing_class in equivalence_classes:
            if semantic_similarity(node, existing_class) > threshold:
                equivalence_classes[existing_class].add(node)
                break
        else:
            equivalence_classes[node] = {node}
    
    # Merge paths, share suffixes
    merged_graph = merge_paths(equivalence_classes)
    return merged_graph

3. Budget Reallocation Strategy

Redundant budget → Diverse exploration

# Before: Multiple branches explore same state
for branch in branches:
    if same_state:
        explore_branch(state)  # Repeated work

# After: Single exploration + share
merged_state = merge_equivalent(states)
explore_once(merged_state)
share_to_all_origins(merged_state)

4. Advantage Assignment

Efficiency Advantages (Incoming Edges)

# Edges leading to efficient reasoning
efficiency_score = path_length / token_count

# Incoming edges get efficiency advantage
for edge in incoming_edges(node):
    advantage_efficiency = efficiency_score * edge_weight

Correctness Advantages (Outgoing Edges)

# Edges leading to correct answers
correctness_score = answer_accuracy

# Outgoing edges get correctness advantage
for edge in outgoing_edges(node):
    advantage_correctness = correctness_score * edge_weight

5. Variance Reduction Theorem

Theory: GraphPO reduces advantage-estimation variance vs. tree methods.

# Tree: Independent branch comparisons
variance_tree = σ² / n_branches

# Graph: Cross-branch comparisons (merged states)
variance_graph = σ² / (n_equivalence_classes)

Since n_equivalence_classes < n_branches:
    variance_graph < variance_tree

Implementation Pattern

class GraphPOPolicy:
    def __init__(self, reasoning_model, reward_fn):
        self.model = reasoning_model
        self.reward = reward_fn
        self.graph = ReasoningGraph()
        
    def optimize(self, query, token_budget):
        # Generate rollouts
        rollouts = self.model.sample_rollouts(query, n_samples)
        
        # Build DAG
        self.graph.build_from_rollouts(rollouts)
        
        # Merge equivalent states
        self.graph.merge_semantic_states(threshold=0.95)
        
        # Reallocate budget
        self.graph.reallocate_budget(token_budget)
        
        # Compute graph advantages
        advantages = self.compute_graph_advantages()
        
        # Update policy
        self.update_policy(advantages)
        
    def compute_graph_advantages(self):
        # Efficiency advantages (incoming)
        for edge in self.graph.incoming_edges():
            efficiency = self.graph.get_path_efficiency(edge)
            edge.advantage += efficiency
        
        # Correctness advantages (outgoing)
        for edge in self.graph.outgoing_edges():
            correctness = self.reward(edge.destination)
            edge.advantage += correctness
        
         .graph.get_advantages()

Key Benefits

1. Reduced variance: Cross-branch comparisons via merged states
2. Efficient exploration: Budget reallocation to diverse paths
3. Process supervision: Derive from outcome via edge advantages
4. Token-budget control: Explicit budget management

Performance

• Consistent improvements over chain/tree baselines
• Same token budget or response budget
• Tested on 3 LLMs across reasoning + agentic search benchmarks

Use Cases

• Reasoning model fine-tuning
• Agentic search optimization
• Multi-path reasoning
• RLVR improvements
• Efficient policy optimization

Reference

• Paper: "GraphPO: Graph-based Policy Optimization for Reasoning Models" (arXiv:2606.18954v1)
• Authors: Yuliang Zhan et al. (2026-06-17)