Researchers present Graph-Enhanced Policy Optimization (GEPO), a new training framework for multi-step LLM agents that improves credit assignment by analyzing state-transition graphs and task relevance. The method achieves 1.1-3.8% performance gains across multiple benchmarks by differentiating the importance of individual steps and trajectories based on their structural and semantic roles.
GEPO addresses a fundamental problem in reinforcement learning for language model agents: the inability to distinguish which steps and trajectories actually contributed to successful outcomes. Traditional group-based reinforcement learning treats all steps equally within trajectories and assigns identical credit to trajectories with identical terminal rewards, missing crucial information about decision quality and state importance.
The framework combines two key innovations. It calculates a Task-Conditioned Criticality score by measuring topological betweenness in state-transition graphs—identifying bottleneck states that many paths depend on—and correlating these with semantic similarity to task objectives. This dual approach captures both structural importance in decision sequences and relevance to specific goals.
The practical impact manifests in measurable improvements: 1.1% on ALFWorld, 3.2% on WebShop, and 3.8% average on search-augmented QA tasks. Beyond raw performance, GEPO reduces variance across training seeds and concentrates learning signals on genuinely critical decision points. This has implications for AI agent reliability and sample efficiency, reducing wasted computation on less meaningful decisions.
For the broader AI landscape, this work advances multi-step reasoning capabilities essential for autonomous agents operating in complex interactive environments. As LLMs move toward real-world deployment in tasks requiring sequential decision-making, improving credit assignment directly impacts training efficiency and performance ceiling. The method is model-agnostic and could apply across various agent architectures, making it relevant for ongoing efforts to scale autonomous reasoning systems.
- →GEPO improves LLM agent training by assigning differentiated credit based on state importance in decision graphs
- →Combines topological analysis with task semantic similarity to identify critical decision points
- →Achieves 1.1-3.8% performance improvements across multiple interactive task benchmarks
- →Reduces training variance and concentrates gradient signals on meaningful steps rather than irrelevant ones
- →Advances sample-efficient training for autonomous agents in complex multi-step decision environments