acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Text-attributed graphs, where nodes and edges are enriched with textual informa- tion, are widely used across various domains. A central challenge in this setting is question answering, which requires effectively integrating unstructured text with the structured relationships in the graph. Although Large Language Models (LLMs) have achieved remarkable progress in natural language understanding, their direct application to reasoning over text-attributed graphs remains limited. Existing text retrieval–augmented generation methods often treat text passages as independent units, overlooking the rich interconnections within the graph. Similarly, conven- tional graph RAG approaches that encode large subgraphs as text quickly become impractical due to LLM context-length constraints, leading to fragmented reason- ing and reduced accuracy. To address these challenges, we propose GRAPH-O1, an agentic GraphRAG framework that enables LLMs to perform stepwise, interactive reasoning over graphs. Our approach combines Monte Carlo Tree Search (MCTS) with end-to-end reinforcement learning, allowing the model to selectively explore and retrieve only the most relevant subgraph elements. The reasoning process is modeled as a multi-turn agent–environment interaction, and the agent is opti- mized via an end-to-end reward mechanism. Extensive experiments across multiple LLM backbones show that GRAPH-O1 consistently outperforms state-of-the-art baselines, delivering more accurate, reliable, and interpretable answers.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Knowledge Graph Reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_eT78OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This work focuses on multi-hop QA on text-attributed graphs, where generic (text-targeted) RAG approaches do not effectively utilize graph structure and serialize subgraphs. It introduces Graph-O1 as an LLM agent with 4 callable functions over graphs with a Thought-Action-Observation loop. It explores multiple trajectories with Monte Carlo tree search scored by an LLM evaluator, where the policy is fine-tuned with GRPO on MCTS traces, using format and graph-operation rewards.

Critical strengths

None

Critical weaknesses
  1. The technical novelty is limited. The first contribution claims that it is "the first agentic text-attributed graph RAG framework" is not true. The prior work Graph-CoT (Jin et al., 2024), which the paper builds on and compares against, is already an agentic framework on the same benchmark with the same four graph functions. The claim of being the first to apply o1-style reasoning with GRPO to graph reasoning also overlooks prior RL-trained graph and search agents, such as Graph-R1 (Luo et al., 2026), Search-R1 (Jin et al., 2025) and R1-Searcher (Song et al., 2025).

  2. The reward described in Section 3.2 includes a +1.0/-0.5 answer-correctness term and a format term summed over steps and capped at 1.0, whereas Appendix B.3 states that answer fidelity is not scored at all, that the format reward lies in [0, 1.5] per completion, and that completions are capped at 256 tokens. This is a fundamental inconsistency: as implemented, the RL stage appears to be per-step GRPO on format and tool-call rewards over trajectories filtered for success, which is closer to rejection-sampling fine-tuning than to the "end-to-end" outcome-based RL claimed in the abstract and contributions.

Questions for authors

N/A

Reviewer_ynWrOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

GRAPH-O1 formulates text-attributed graph QA as sequential interaction between an LLM and graph tools. It adds Monte Carlo Tree Search to Graph-CoT-style stepwise retrieval and trains the policy using GRPO. Evaluation spans multiple GRBENCH domains, with search ablations, cost measurements, and path diagnostics. An important distinction is that the main text describes answer-correctness rewards, whereas Appendix B.3 explicitly states that the implemented completion reward does not directly score answer fidelity or retrieval relevance.

Critical strengths

Combining graph tools with branching search is reasonably motivated, and relation-chain agreement and invalid-action rates provide useful reasoning diagnostics.

Critical weaknesses

1.The main text includes answer-correctness rewards, but Appendix B.3’s implementation rewards format, graph-operation use, and avoidance of reported errors. Filtering successful traces does not reward correctness of new answers, leaving the claimed end-to-end semantic optimization unsupported. 2.Training/test splits and the standard-error calculation are unclear. If binary accuracy is computed over independent questions, the uncertainty reported for the Legal domain appears inconsistent with its sample size; the statistical units and repetition scheme need clarification.

Questions for authors

1.Which reward produced the main results: Section 3.2 or Appendix B.3? Are training samples complete interactive trajectories, or short completions generated from states extracted from successful traces? If correctness is not rewarded, what is GRPO’s independent benefit over supervised fine-tuning on the same successful traces and over format-only optimization? 2.Please provide the training, validation, and test question counts and identifiers for each domain, including any overlap in templates or answer entities. Clarify the units, denominator, and repetition counts used for the standard errors, and provide paired question-level confidence intervals against GRAPH-MCTS to show which gains are reliable at the available sample sizes. 3.Under the stated stopping rule, search returns the first completed branch’s answer. How are node or branch values computed and used to guide search before stopping? Please specify the evaluator model, prompts, and invocation procedure, confirm whether all evaluator calls are included in the reported costs, and provide a budget-matched repeated-sampling control.

Reviewer_T2cmOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the question-answering task on text-attributed graphs, requiring multi-step reasoning that combines node text and graph structure. The authors introduce Monte Carlo Tree Search (MCTS) to explore candidate reasoning trajectories within a Graph-COT style graph interaction framework. Agents obtain information through four types of graph operations: node retrieval, attribute value reading, neighbor queries, and adjacent node count queries, with trajectory values evaluated using an LLM. Finally, successful search trajectories are used to construct training data, and the policy model is updated via GRPO strategy and LoRA fine-tuning. Experiments on the GRBENCH benchmark compare GRAPH-O1 with multiple baselines and show that it consistently outperforms existing methods across all five domains.

Critical strengths
  1. The research problem and motivation are practically relevant. GRAPH-O1 addresses the fragmented reasoning and limited scalability that arise when RAG techniques are applied directly to graph-structured data. Its ability to integrate textual content with relational information in graphs makes this a meaningful research direction.

  2. The method demonstrates strong empirical performance. Table 1 provides a comprehensive comparison with standard LLMs, text retrieval-augmented LLMs (Text RAG), graph retrieval-augmented LLMs (Graph RAG), and Graph-COT. The results show that the proposed combination of MCTS-based search and GRPO-based policy training outperforms existing baselines.

Critical weaknesses
  1. The technical novelty is limited. The four graph operations are similar to those used in Graph-COT, and the main contribution appears to be a combination of existing components. Being the first to combine GRPO and MCTS for graph reasoning is not a sufficiently substantial methodological contribution.

  2. The paper lacks controlled comparisons that establish the need for MCTS. The current results show that additional search is helpful, but they do not provide sufficient evidence that UCT-guided MCTS is more effective than simpler search-budget allocation strategies.

Questions for authors

The reward formulation in Section 3.2 appears inconsistent with the implementation described in Appendix B.3. The main text states that the model receives a reward for using graph-related functions, with an additional reward if the answer is clearly correct. However, the appendix omits the operation-correctness reward described in the main text, and the two sections specify different maximum values for the format reward. Could the authors verify the reward formulation against the actual code and make the descriptions consistent throughout the paper?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.