# TreeRPO: Tree Relative Policy Optimization

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 36 of its 44 references that are in the map.
- First posted on arXiv 5 Jun 2025.

## Placed in

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

## Builds on (most cited first, 30 of 36)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [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)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [OlympiadBench: A Challenging Benchmark for Promoting AGI with Olympiad-Level Bilingual Multimodal Scientific Problems](https://mlsanity.com/paper/2402.14008/) (2024)
- [Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Improvement](https://mlsanity.com/paper/2409.12122/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Models](https://mlsanity.com/paper/2309.12284/) (2023)
- [Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2506.01939/) (2025)
- [SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild](https://mlsanity.com/paper/2503.18892/) (2025)
- [Open-Reasoner-Zero: An Open Source Approach to Scaling Up Reinforcement Learning on the Base Model](https://mlsanity.com/paper/2503.24290/) (2025)
- [Scaling Relationship on Learning Mathematical Reasoning with Large Language Models](https://mlsanity.com/paper/2308.01825/) (2023)
- [Step-DPO: Step-wise Preference Optimization for Long-chain Reasoning of LLMs](https://mlsanity.com/paper/2406.18629/) (2024)
- [VinePPO: Refining Credit Assignment in RL Training of LLMs](https://mlsanity.com/paper/2410.01679/) (2024)
- [DART-Math: Difficulty-Aware Rejection Tuning for Mathematical Problem-Solving](https://mlsanity.com/paper/2407.13690/) (2024)
- [Cumulative Reasoning with Large Language Models](https://mlsanity.com/paper/2308.04371/) (2023)
- [Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models](https://mlsanity.com/paper/2505.23564/) (2025)
- [MathGenie: Generating Synthetic Data with Question Back-translation for Enhancing Mathematical Reasoning of LLMs](https://mlsanity.com/paper/2402.16352/) (2024)
- [OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling](https://mlsanity.com/paper/2407.09887/) (2024)
- [SPC: Evolving Self-Play Critic via Adversarial Games for LLM Reasoning](https://mlsanity.com/paper/2504.19162/) (2025)

## Built on by (most cited first, 30 of 46)

- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [Tree Search for LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2509.21240/) (2025)
- [Beyond Pass@1: Self-Play with Variational Problem Synthesis Sustains RLVR](https://mlsanity.com/paper/2508.14029/) (2025)
- [Towards a Unified View of Large Language Model Post-Training](https://mlsanity.com/paper/2509.04419/) (2025)
- [TreeGRPO: Tree-Advantage GRPO for Online RL Post-Training of Diffusion Models](https://mlsanity.com/paper/2512.08153/) (2025)
- [Exploiting Tree Structure for Credit Assignment in RL Training of LLMs](https://mlsanity.com/paper/2509.18314/) (2025)
- [XRPO: Pushing the limits of GRPO with Targeted Exploration and Exploitation](https://mlsanity.com/paper/2510.06672/) (2025)
- [EnvFactory: Scaling Tool-Use Agents via Executable Environments Synthesis and Robust RL](https://mlsanity.com/paper/2605.18703/) (2026)
- [Attention as a Compass: Efficient Exploration for Process-Supervised RL in Reasoning Models](https://mlsanity.com/paper/2509.26628/) (2025)
- [Tree-OPO: Off-policy Monte Carlo Tree-Guided Advantage Optimization for Multistep Reasoning](https://mlsanity.com/paper/2509.09284/) (2025)
- [Scheduling Your LLM Reinforcement Learning with Reasoning Trees](https://mlsanity.com/paper/2510.24832/) (2025)
- [MAPO: Mixed Advantage Policy Optimization](https://mlsanity.com/paper/2509.18849/) (2025)
- [SpatialDreamer: Incentivizing Spatial Reasoning via Active Mental Imagery](https://mlsanity.com/paper/2512.07733/) (2025)
- [GRPO is Secretly a Process Reward Model](https://mlsanity.com/paper/2509.21154/) (2025)
- [Why Tree-Style Branching Matters for Thought Advantage Estimation in GRPO](https://mlsanity.com/paper/2509.24494/) (2025)
- [TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning](https://mlsanity.com/paper/2606.11119/) (2026)
- [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)
- [Reinforced Efficient Reasoning via Semantically Diverse Exploration](https://mlsanity.com/paper/2601.05053/) (2026)
- [Learning Decentralized LLM Collaboration with Multi-Agent Actor Critic](https://mlsanity.com/paper/2601.21972/) (2026)
- [Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimization](https://mlsanity.com/paper/2604.07165/) (2026)
- [Credit Where It is Due: Cross-Modality Connectivity Drives Precise Reinforcement Learning for MLLM Reasoning](https://mlsanity.com/paper/2602.11455/) (2026)
- [Efficient RLVR Training via Weighted Mutual Information Data Selection](https://mlsanity.com/paper/2603.01907/) (2026)
- [PBSD: Privileged Bayesian Self-Distillation for Long-Horizon Credit Assignment](https://mlsanity.com/paper/2606.09348/) (2026)
- [CARL: Criticality-Aware Agentic Reinforcement Learning](https://mlsanity.com/paper/2512.04949/) (2025)
- [EMO-R3: Reflective Reinforcement Learning for Emotional Reasoning in Multimodal Large Language Models](https://mlsanity.com/paper/2602.23802/) (2026)
- [AMIR-GRPO: Inducing Implicit Preference Signals into GRPO](https://mlsanity.com/paper/2601.03661/) (2026)
- [VeriGate: Verifier-Gated Step-Level Supervision for GRPO](https://mlsanity.com/paper/2605.30451/) (2026)
- [IAPO: Information-Aware Policy Optimization for Token-Efficient Reasoning](https://mlsanity.com/paper/2602.19049/) (2026)
- [GraphPO: Graph-based Policy Optimization for Reasoning Models](https://mlsanity.com/paper/2606.18954/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have shown remarkable reasoning capabilities through Reinforcement Learning with Verifiable Rewards (RLVR) methods. However, a key limitation of existing approaches is that rewards defined at the full trajectory level provide insufficient guidance for optimizing the intermediate steps of a reasoning process. To address this, we introduce name, a novel method that estimates the mathematical expectations of rewards at various reasoning steps using tree sampling. Unlike prior methods that rely on a separate step reward model, name directly estimates these rewards through this sampling process. Building on the group-relative reward training mechanism of GRPO, name innovatively computes rewards based on step-level groups generated during tree sampling. This advancement allows name to produce fine-grained and dense reward signals, significantly enhancing the learning process and overall performance of LLMs. Experimental results demonstrate that our name algorithm substantially improves the average Pass@1 accuracy of Qwen-2.5-Math on test benchmarks, increasing it from 19.0% to 35.5%. Furthermore, name significantly outperforms GRPO by 2.9% in performance while simultaneously reducing the average response length by 18.1%, showcasing its effectiveness and efficiency. Our code will be available at hrefhttps://github.com/yangzhch6/TreeRPOhttps://github.com/yangzhch6/TreeRPO.