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

• URL: http://arxiv.org/abs/2604.07165v2
• Date: Wed, 15 Apr 2026 15:01:41 GMT
• Title: Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimization
• Abstract summary: Reinforcement learning for Large Language Model agents is often hindered by sparse rewards in multi-step reasoning tasks.<n>We propose T-STAR, a framework that recovers the latent correlated reward structure across seemingly independent trajectories.
• Score: 10.86007023031758
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• ChainPrune: Evaluating and Reducing Redundancy in Long Chain-of-Thought Reasoning [48.3829293800053]
  We propose ChainPrune, a novel reasoning path semantic structural optimization method.<n>We consolidate self-generated reasoning paths into a tree-based structure, followed by a multi-criteria dominant path selection process.<n>We incorporate a DPO-based preference learning method combined with supervised loss, effectively mitigating false reward suppression.
  arXiv  Detail & Related papers  (2026-08-22T09:09:05Z)
• Advantage-Guided Gate: Reshaping Open-Ended Reasoning for Vision-Based Spatial Intelligence [70.8951332710039]
  Multimodal large language models (MLLMs) have demonstrated significant potential in complex spatial scene understanding and reasoning tasks.<n>However, their open-ended reasoning process is prone to decision errors and error accumulation, leading to instability in answer quality.<n>We propose an advantage-guided gating framework that dynamically intervenes in and corrects deviations during the reasoning process.
  arXiv  Detail & Related papers  (2026-08-08T07:46:04Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• Segment-Aligned Policy Optimization for Multi-Modal Reasoning [55.29606572822562]
  We propose a novel reinforcement learning paradigm that treats coherent reasoning steps, rather than tokens or full sequences as fundamental units of policy update.<n>Experiments on representative reasoning benchmarks demonstrate that SAPO consistently outperforms token-level and sequence-level policy optimization methods.<n>Our work underscores the importance of aligning reinforcement learning updates with the structure of reasoning, paving the way for more efficient and semantically grounded policy optimization in complex reasoning tasks.
  arXiv  Detail & Related papers  (2026-05-02T08:47:45Z)
• TopoCurate:Modeling Interaction Topology for Tool-Use Agent Training [53.93696896939915]
  Training tool-use agents typically rely on Supervised Fine-Tuning (SFT) on successful trajectories and Reinforcement Learning (RL) on pass-rate-selected tasks.<n>We propose TopoCurate, an interaction-aware framework that projects multi-trial rollouts from the same task into a unified semantic quotient topology.<n>TopoCurate achieves consistent gains of 4.2% (SFT) and 6.9% (RL) over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-03-02T10:38:54Z)
• Learning Structured Reasoning via Tractable Trajectory Control [99.75278337895024]
  Ctrl-R is a framework for learning structured reasoning via tractable trajectory control.<n>We show that Ctrl-R enables effective exploration and internalization of previously unattainable reasoning patterns.
  arXiv  Detail & Related papers  (2026-03-02T09:18:19Z)
• Training Multi-Turn Search Agent via Contrastive Dynamic Branch Sampling [29.182538022605627]
  Branching Relative Policy Optimization (BranPO) is a value-free method that provides step-level contrastive supervision without dense rewards.<n>BranPO truncates trajectories near the tail and resamples alternative continuations to construct contrastive suffixes over shared prefixes.<n>To further boost efficiency and stabilize training, we introduce difficulty-aware branch sampling to adapt branching frequency across tasks, and redundant step masking to suppress uninformative actions.
  arXiv  Detail & Related papers  (2026-02-03T16:43:09Z)
• Search-R2: Enhancing Search-Integrated Reasoning via Actor-Refiner Collaboration [49.9937230730202]
  We propose Search-R2, a novel Actor-Refiner collaboration framework that enhances reasoning through targeted intervention.<n>Our approach decomposes the generation process into an Actor, which produces initial reasoning trajectories.<n>We show that Search-R2 consistently outperforms strong RAG and RL-based baselines across model scales.
  arXiv  Detail & Related papers  (2026-02-03T15:32:09Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• Reinforced Efficient Reasoning via Semantically Diverse Exploration [73.41112984160992]
  Reinforcement learning with verifiable rewards (RLVR) has proven effective in enhancing the reasoning of large language models (LLMs)<n>We propose reinforced efficient reasoning via semantically diverse explorations, i.e., ROSE, for LLMs.<n>Our method incorporates a semantic-entropy-based branching strategy and an $varepsilon$-exploration mechanism.
  arXiv  Detail & Related papers  (2026-01-08T15:56:44Z)
• Know your Trajectory -- Trustworthy Reinforcement Learning deployment through Importance-Based Trajectory Analysis [6.7842735984907465]
  We introduce a novel framework that ranks entire trajectories by defining and aggregating a new state-importance metric.<n>We demonstrate that our method successfully identifies optimal trajectories from a heterogeneous collection of agent experiences.<n>Our experiments in standard OpenAI Gym environments validate that our proposed importance metric is more effective at identifying optimal behaviors.
  arXiv  Detail & Related papers  (2025-12-07T16:52:08Z)
• Tree Search for LLM Agent Reinforcement Learning [23.7084695563981]
  Tree-based Group Relative Policy Optimization (Tree-GRPO) is a grouped agent RL method based on tree search.<n>By sharing common prefixes, the tree search sampling increases the number of rollouts achievable.<n>We demonstrate that the objective of intra-tree level group relative policy optimization is equivalent to that of step-level direct preference learning.
  arXiv  Detail & Related papers  (2025-09-25T14:37:09Z)
• Fine-Tuning on Diverse Reasoning Chains Drives Within-Inference CoT Refinement in LLMs [63.36637269634553]
  We introduce a novel approach where LLMs are fine-tuned to generate a sequence of Diverse Chains of Thought (DCoT) within a single inference step.<n>We show that fine-tuning on DCoT improves performance over the CoT baseline across model families and scales.<n>Our work is also significant because both quantitative analyses and manual evaluations reveal the observed gains stem from the models' ability to refine an initial reasoning chain.
  arXiv  Detail & Related papers  (2024-07-03T15:01:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.