# Tree-OPO: Off-policy Monte Carlo Tree-Guided Advantage Optimization for Multistep Reasoning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 18 of its 26 references that are in the map.
- First posted on arXiv 11 Sep 2025.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)

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

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [On-Policy Distillation of Language Models: Learning from Self-Generated Mistakes](https://mlsanity.com/paper/2306.13649/) (2023)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizes](https://mlsanity.com/paper/2305.02301/) (2023)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [DistiLLM: Towards Streamlined Distillation for Large Language Models](https://mlsanity.com/paper/2402.03898/) (2024)
- [Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers](https://mlsanity.com/paper/2408.06195/) (2024)
- [DistiLLM-2: A Contrastive Approach Boosts the Distillation of LLMs](https://mlsanity.com/paper/2503.07067/) (2025)
- [TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling](https://mlsanity.com/paper/2508.17445/) (2025)
- [Enhancing LLM Reasoning with Reward-guided Tree Search](https://mlsanity.com/paper/2411.11694/) (2024)
- [TreeRPO: Tree Relative Policy Optimization](https://mlsanity.com/paper/2506.05183/) (2025)
- [Pangu-Agent: A Fine-Tunable Generalist Agent with Structured Reasoning](https://mlsanity.com/paper/2312.14878/) (2023)

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

- [Exploiting Tree Structure for Credit Assignment in RL Training of LLMs](https://mlsanity.com/paper/2509.18314/) (2025)
- [Generate, Filter, Control, Replay: A Comprehensive Survey of Rollout Strategies for LLM Reinforcement Learning](https://mlsanity.com/paper/2605.02913/) (2026)
- [Multi-GRPO: Multi-Group Advantage Estimation for Text-to-Image Generation with Tree-Based Trajectories and Multiple Rewards](https://mlsanity.com/paper/2512.00743/) (2025)
- [Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimization](https://mlsanity.com/paper/2604.07165/) (2026)
- [The Model Knows, the Decoder Finds: Future Value Guided Particle Power Sampling](https://mlsanity.com/paper/2605.02427/) (2026)
- [TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG](https://mlsanity.com/paper/2601.06922/) (2026)
- [V0.5: Generalist Value Model as a Prior for Sparse RL Rollouts](https://mlsanity.com/paper/2603.10848/) (2026)
- [GraphPO: Graph-based Policy Optimization for Reasoning Models](https://mlsanity.com/paper/2606.18954/) (2026)
- [Advantage Scale Calibration Imbalance in Group-Relative Optimization under Low-Variance Rewards: Diagnosis and Bounded Recovery](https://mlsanity.com/paper/2609.19164/) (2026)
- [CATPO: Critique-Augmented Tree Policy Optimization](https://mlsanity.com/paper/2606.08346/) (2026)
- [The Weakest Link: Distilling LLM Reasoning with Worst-Case Constrained Reinforcement Learning](https://mlsanity.com/paper/2610.00332/) (2026)
- [A Safe Action Is Not Enough: Feasible-Future Decoding for Vision-Language-Action Policies](https://mlsanity.com/paper/2610.05166/) (2026)

## Abstract (arXiv)

Recent advances in reasoning with large language models (LLMs) have shown the effectiveness of Monte Carlo Tree Search (MCTS) for generating high quality intermediate trajectories, particularly in math and symbolic domains. Inspired by this, we explore how MCTS derived trajectories, traditionally used for training value or reward models, can be repurposed to improve policy optimization in verifier guided reinforcement learning (RL). Specifically, we focus on Group Relative Policy Optimization (GRPO), a recent algorithm that enables consistent policy learning from group relative judgments. We reframe GRPO into a staged training paradigm, leveraging a teacher's MCTS rollouts to construct a tree structured curriculum of prefixes. This introduces the novel challenge of computing advantages for training samples that originate from different prefixes, each with a distinct expected return. To address this, we propose Staged Advantage Estimation (SAE), a framework for computing low variance, prefix aware advantages by projecting rewards onto a constraint set that respects the tree's hierarchy. Our empirical results on mathematical reasoning tasks show that SAE improves final accuracy over standard GRPO. This outcome is grounded in our theoretical analysis, which confirms that SAE reduces gradient variance, a principled path to improved sample efficiency. We demonstrate this through practical SAE implementations, comparing efficient heuristics against a formal quadratic program.