# Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimization

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

## Key facts

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

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)
- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2504.20073/) (2025)
- [Reinforcement Learning for Reasoning in Large Language Models with One Training Example](https://mlsanity.com/paper/2504.20571/) (2025)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [LLM Post-Training: A Deep Dive into Reasoning Large Language Models](https://mlsanity.com/paper/2502.21321/) (2025)
- [Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models](https://mlsanity.com/paper/2505.23564/) (2025)
- [TreeRPO: Tree Relative Policy Optimization](https://mlsanity.com/paper/2506.05183/) (2025)
- [Semantic-Aware Logical Reasoning via a Semiotic Framework](https://mlsanity.com/paper/2509.24765/) (2025)
- [Think-While-Generating: On-the-Fly Reasoning for Personalized Long-Form Generation](https://mlsanity.com/paper/2512.06690/) (2025)
- [ARISE: Agent Reasoning with Intrinsic Skill Evolution in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2603.16060/) (2026)
- [Logical Phase Transitions: Understanding Collapse in LLM Logical Reasoning](https://mlsanity.com/paper/2601.02902/) (2026)
- [EvoTool: Self-Evolving Tool-Use Policy Optimization in LLM Agents via Blame-Aware Mutation and Diversity-Aware Selection](https://mlsanity.com/paper/2603.04900/) (2026)
- [Learning Global Hypothesis Space for Enhancing Synergistic Reasoning Chain](https://mlsanity.com/paper/2602.09794/) (2026)
- [Reasoning with Reinforced Functional Token Tuning](https://mlsanity.com/paper/2502.13389/) (2025)
- [Tree-OPO: Off-policy Monte Carlo Tree-Guided Advantage Optimization for Multistep Reasoning](https://mlsanity.com/paper/2509.09284/) (2025)
- [Text summarization via global structure awareness](https://mlsanity.com/paper/2602.09821/) (2026)
- [InSPO: Unlocking Intrinsic Self-Reflection for LLM Preference Optimization](https://mlsanity.com/paper/2512.23126/) (2025)
- [When Right Meets Wrong: Bilateral Context Conditioning with Reward-Confidence Correction for GRPO](https://mlsanity.com/paper/2603.13134/) (2026)
- [PERM: Psychology-grounded Empathetic Reward Modeling for Large Language Models](https://mlsanity.com/paper/2601.10532/) (2026)
- [Inclusion-of-Thoughts: Mitigating Preference Instability via Purifying the Decision Space](https://mlsanity.com/paper/2604.04944/) (2026)
- [Red Teaming Large Reasoning Models](https://mlsanity.com/paper/2512.00412/) (2025)

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

- [NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search](https://mlsanity.com/paper/2605.00751/) (2026)
- [OPPO: Bayesian Value Recursion for Token-Level Credit Assignment in LLM Reasoning](https://mlsanity.com/paper/2605.21851/) (2026)
- [Does Compression Preserve Uncertainty? A Unified Benchmark for Quantized and Sparse LLMs via Conformal Prediction](https://mlsanity.com/paper/2606.01850/) (2026)
- [A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling](https://mlsanity.com/paper/2606.01720/) (2026)
- [Customer-Agent: Overcoming Context Limitations in Ultra-Long Shopping Trajectories via Tool-Augmented Agents and RLVR](https://mlsanity.com/paper/2606.07995/) (2026)
- [FlowEdit: Information-Theoretic Control of LLM Reasoning Flows for Ill-posed Problems Involving Conflicts](https://mlsanity.com/paper/2607.20500/) (2026)
- [Characterizing a Configuration Where Inference-Time PRM-Pruned Fragment Grafting Is Inert: Evidence from Three Reasoning LMs](https://mlsanity.com/paper/2610.00047/) (2026)
- [Tropical Reinforcement Learning](https://mlsanity.com/paper/2610.02478/) (2026)

## Abstract (arXiv)

Reinforcement learning for Large Language Model agents is often hindered by sparse rewards in multi-step reasoning tasks. Existing approaches like Group Relative Policy Optimization treat sampled trajectories as independent chains, assigning uniform credit to all steps in each chain and ignoring the existence of critical steps that may disproportionally impact reasoning outcome. In this paper, we propose T-STAR(Tree-structured Self-Taught Agent Rectification), a framework that recovers the latent correlated reward structure across seemingly independent trajectories. Specifically, we consolidate trajectories into a unified Cognitive Tree by identifying and merging functionally similar steps/nodes. It enables an Introspective Valuation mechanism that back-propagates trajectory-level rewards through the tree to obtain a new notion of variance-reduced relative advantage at step-level. Using the Cognitive Tree, we also develop In-Context Thought Grafting to synthesize corrective reasoning by contrasting successful and failed branches at critical divergence points/steps. Our proposed Surgical Policy Optimization then capitalizes on the rich policy gradient information concentrated at these critical points/steps through a Bradley-Terry type of surgical loss. Extensive experiments across embodied, interactive, reasoning, and planning benchmarks demonstrate that T-STAR achieves consistent improvements over strong baselines, with gains most pronounced on tasks requiring extended reasoning chains.