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

arXiv: https://arxiv.org/abs/2512.17912 · HTML: https://mlsanity.com/paper/2512.17912/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 25 of its 34 references that are in the map.
- First posted on arXiv 26 Nov 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 25 of 25)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [REPLUG: Retrieval-Augmented Black-Box Language Models](https://mlsanity.com/paper/2301.12652/) (2023)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [Self-Rewarding Language Models](https://mlsanity.com/paper/2401.10020/) (2024)
- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs](https://mlsanity.com/paper/2404.07103/) (2024)
- [From LLMs to LLM-based Agents for Software Engineering: A Survey of Current, Challenges and Future](https://mlsanity.com/paper/2408.02479/) (2024)
- [Large Language Models Are Semi-Parametric Reinforcement Learning Agents](https://mlsanity.com/paper/2306.07929/) (2023)
- [Dipping PLMs Sauce: Bridging Structure and Text for Effective Knowledge Graph Completion via Conditional Soft Prompting](https://mlsanity.com/paper/2307.01709/) (2023)
- [KG-GPT: A General Framework for Reasoning on Knowledge Graphs Using Large Language Models](https://mlsanity.com/paper/2310.11220/) (2023)
- [GenTKG: Generative Forecasting on Temporal Knowledge Graph with Large Language Models](https://mlsanity.com/paper/2310.07793/) (2023)
- [ECOLA: Enhanced Temporal Knowledge Embeddings with Contextualized Language Representations](https://mlsanity.com/paper/2203.09590/) (2022)

## Built on by (most cited first, 7 of 7)

- [GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning](https://mlsanity.com/paper/2603.01410/) (2026)
- [GraphDancer: Training LLMs to Explore and Reason over Graphs via Two-Stage Curriculum Post-Training](https://mlsanity.com/paper/2602.02518/) (2026)
- [Mixture of Demonstrations for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2603.23554/) (2026)
- [Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables](https://mlsanity.com/paper/2605.25985/) (2026)
- [WDL-OPD: Weak-Driven On-Policy Distillation via Mixture-Constrained Co-Training](https://mlsanity.com/paper/2608.09447/) (2026)
- [Robust Conformal Consensus: Multi-Agent LLM-as-a-Judge Interval Evaluation with Conformal Prediction](https://mlsanity.com/paper/2609.06367/) (2026)
- [GraphCert: Bootstrap Agentic Graph Reasoning with Certified Evidence Rubrics](https://mlsanity.com/paper/2609.38798/) (2026)

## Abstract (arXiv)

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.