Graph-O1 : Monte Carlo Tree Search with Reinforcement Learning for Text-Attributed Graph Reasoning

Lihui Liu

TL;DR

Graph-O1 is a new agentic framework that enables Large Language Models (LLMs) to perform deep, stepwise reasoning over text-attributed graphs. By combining Monte Carlo Tree Search (MCTS) with Group Relative Policy Optimization (GRPO), the system learns to selectively explore complex graph structures, overcoming the context-length limitations and "fragmented reasoning" common in traditional Graph RAG approaches.

What Problem Does This Paper Address?

Reasoning over Text-Attributed Graphs (TAGs)—where nodes and edges contain rich textual data (like a citation network or an e-commerce product graph)—is notoriously difficult for LLMs.

Current approaches usually fall into two traps:

  1. Text RAG: Treats retrieved nodes as isolated text snippets, ignoring the structural "connect-the-dots" relationships that provide vital context.
  2. Naive Graph RAG: Attempts to "linearize" large subgraphs into the LLM's prompt. As the search depth increases, the number of nodes grows exponentially, quickly exhausting the LLM's context window and introducing irrelevant noise that degrades accuracy.

The authors identify a need for an agent that doesn't just retrieve data, but interactively explores the graph, deciding which hop to take next based on a deliberate "thinking" process.

Methods

Graph-O1 treats graph reasoning as a Markov Decision Process (MDP) and introduces a three-phase cycle inspired by the "thinking" behavior of models like OpenAI’s o1.

1. The Agentic Framework

The agent uses four core functions to interact with the graph:

  • RetrieveNode: Finds entry points via semantic search.
  • NodeFeature: Extracts specific text (titles, abstracts).
  • NeighborCheck: Lists connections (citations, co-authors).
  • NodeDegree: Gauges node importance.

2. MCTS-Guided Planning

Instead of a single "greedy" path, the model uses MCTS to simulate multiple hypothetical reasoning trajectories. It uses the Upper Confidence Bound (UCB) to balance exploring new paths versus exploiting known promising ones. This allows the model to "look ahead" before committing to a final answer.

3. End-to-End RL (GRPO)

To fine-tune the agent, the authors use Group Relative Policy Optimization (GRPO)—the same efficient RL algorithm used by DeepSeek-V3/R1. They reward the model for:

  • Format: Following the "Thought-Action-Observation" structure.
  • Reasoning: Executing valid graph operations and arriving at the correct answer.
  • Efficiency: Reaching the target without unnecessary hops.

Datasets

The model was evaluated on GRBENCH, a comprehensive benchmark for text-attributed graph QA. It covers five diverse domains:

  • Academic: CS, Biology, Chemistry, Physics, Medicine.
  • E-commerce: Amazon product data.
  • Literature: Goodreads.
  • Healthcare: Disease networks.
  • Legal: Freelaw.

The dataset includes roughly 1,770 questions requiring multi-hop navigation across millions of nodes and edges.

Key Insights and Ideas

  • Selective Exploration vs. Brute Force: The "aha moment" is that LLMs perform better when they choose their own context. By selectively retrieving only the most relevant neighbors rather than a full 2-hop ego-graph, Graph-O1 avoids "context drowning."
  • The Power of "Thinking": The inclusion of a Thought step before every Action allows the model to synthesize current evidence and plan the next retrieval step, significantly reducing hallucinations.
  • RL for Strategy, Not Just Knowledge: The RL process doesn't just teach the model facts; it teaches the model how to search a graph. This makes the reasoning strategy generalizable across different domains.

Key Results

Graph-O1 was tested using backbones like Mixtral-8x7b and LLaMA-2-13b. Key findings include:

  • Superior Accuracy: Graph-O1 consistently outperformed state-of-the-art baselines like Graph-COT and GraphMCTS. In the Healthcare domain, it achieved a GPT-4 evaluation score of 33.70, compared to just 14.07 for standard Graph RAG.
  • Efficiency over Hops: While standard RAG performance often drops when moving from 1-hop to 2-hop retrieval (due to noise), Graph-O1’s performance improves with depth because its MCTS-guided search filters out the "garbage" nodes.
  • Backbone Sensitivity: The choice of LLM matters; models with stronger native instruction-following (like Mixtral) saw much larger gains from the Graph-O1 framework than smaller, weaker models.

Limitations and Future Work

  • Computational Overhead: Running MCTS with multiple simulations and rollouts is significantly more expensive and slower than a single-shot RAG query.
  • Cold Start Problem: The agent relies on RetrieveNode to find a good starting point; if the initial semantic search fails to find the "topic node," the entire reasoning chain may fail.
  • Future Directions: The authors suggest exploring multi-agent collaboration where different agents specialize in different sub-graphs or domains. There is also potential to optimize the "rollout" phase to be more computationally efficient.

Summary updated

Abstract

ChatGPT said: Text-attributed graphs, where nodes and edges contain rich textual information, are widely used across diverse domains. A central challenge in this setting is question answering, which requires jointly leveraging unstructured text and the structured relational signals within the graph. Although Large Language Models (LLMs) have made significant advances in natural language understanding, their direct use for reasoning over text-attributed graphs remains limited. Retrieval-augmented generation methods that operate purely on text often treat passages as isolated units, ignoring the interconnected structure of the graph. Conversely, graph-based RAG methods that serialize large subgraphs into long textual sequences quickly become infeasible due to LLM context-length constraints, resulting in fragmented reasoning and degraded accuracy. To overcome these limitations, we introduce Graph-O1, an agentic GraphRAG framework that enables LLMs to conduct stepwise, interactive reasoning over graphs. Our approach integrates Monte Carlo Tree Search (MCTS) with end-to-end reinforcement learning, allowing the model to selectively explore and retrieve only the most informative subgraph components. The reasoning procedure is framed as a multi-turn interaction between the agent and the graph environment, and the agent is trained through a unified reward mechanism. Extensive experiments across multiple LLM backbones demonstrate that Graph-O1 consistently surpasses state-of-the-art baselines, producing answers that are more accurate, reliable, and interpretable.
BibTeX
@misc{liu2025graph,
  author = {Lihui Liu},
  title = {{Graph-O1 : Monte Carlo Tree Search with Reinforcement Learning for Text-Attributed Graph Reasoning}},
  year = {2025},
  eprint = {2512.17912},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.17912},
}
Figure