TreeAdv: Tree-Structured Advantage Redistribution for Group-Based RL

Lang Cao * Hui Ruan * Yongqian Li * Peng Chao Wu Ning Haonan Song Renhong Chen † Yitong Li † Huawei Technologies Co., Ltd., China {caolang4,liyitong3}@huawei.com · 2026

Read TreeAdv: Tree-Structured Advantage Redistribution for Group-Based RL by Lang Cao * Hui Ruan * Yongqian Li * Peng Chao Wu Ning Haonan Song Renhong Chen † Yitong Li † Huawei Technologies Co., Ltd., China {caolang4,liyitong3}@huawei.com (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03703.txt.

Introduction

Lang Cao and seven co-authors improve group-based reinforcement learning for language models, the family that includes GRPO. In these methods, a group of sample answers is scored, but standard practice treats each answer as a flat sequence and gives every token the same advantage value. That wastes samples and rewards long, redundant chains of thought that add words without adding logic.

Their method, TreeAdv, makes the shared tree structure of grouped rollouts explicit. Sampling branches at high-uncertainty decisions while sharing calm stretches across rollouts. Advantages from full rollouts are then redistributed down to internal tree segments, so credit lands on the steps that diverged. The design targets both better exploration and fairer credit, two needs for training reasoning models efficiently.

Catalog record

CREATORLang Cao * Hui Ruan * Yongqian Li * Peng Chao Wu Ning Haonan Song Renhong Chen † Yitong Li † Huawei Technologies Co., Ltd., China {caolang4,liyitong3}@huawei.com
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-03703

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

TreeAdv: Tree-Structured Advantage Redistribution for Group-Based RL Lang Cao * Hui Ruan * Yongqian Li * Peng Chao Wu Ning Haonan Song Renhong Chen † Yitong Li † Huawei Technologies Co., Ltd., China {caolang4,liyitong3}@huawei.com Abstract Reinforcement learning with group-based objectives, such as Group Relative Policy Optimization (GRPO), is a common framework for aligning large language models on complex reasoning tasks. However, standard GRPO treats each rollout trajectory as an independent flat sequence and assigns a single sequence-level advantage to all tokens, which leads to sample inefficiency and a length bias toward verbose, redundant chains of thought without improving logical depth. We introduce TreeAdv (Tree-Structured Advantage Redistribution for Group-Based RL), which makes the tree structure of group rollouts explicit for both exploration and advantage assignment. Specifically, TreeAdv builds a group of trees (a forest) based on an entropy-driven sampling method where each tree branches at high-uncertainty decisions while sharing low-uncertainty tokens across rollouts. Then, TreeAdv aggregates token-level advantages for internal tree segments by redistributing the advantages of complete rollouts (all leaf nodes), and TreeAdv can easily apply to group-based objectives such as GRPO or GSPO. Across 10 10 math reasoning benchmarks, TreeAdv consistently outperforms GRPO and GSPO, while using substantially fewer generated tokens under identical supervision, data, and decoding budgets. † † footnotetext: * Equal contribution † † footnotetext: †Corresponding authors 1 Introduction Reinforcement learning (RL) post-training has become a key mechanism for eliciting reliable and multi-step reasoning behavior in large language models (LLMs), especially in mathematics and formal problem-solving tasks 32 ; 16 . As pure next-token prediction reaches diminishing returns 23 , RL provides a way to move beyond surface-level pattern matching toward more deliberate problem solving 14 . Within the broad landscape of post-training methods, including supervised fine-tuning, RL with Proximal Policy Optimization (PPO; 15 ; 20 ), and offline preference optimization such as DPO 17 , group-based RL methods, in particular Group Relative Policy Optimization (GRPO; 21 ) and Group Sequence Policy Optimization (GSPO; 33 ), have emerged as a practical foundation for training reasoning-oriented LLMs 27 . By estimating baselines from group-wise statistics instead of a separate value network, these methods substantially reduce memory overhead, enabling the training of large, long-context reasoning models such as DeepSeek-R1 5 . Despite this progress, GRPO-style methods still rely on sequence-level advantage assignment where supervision is aggregated across entire generated sequences 10 . Each sampled output y_{i} receives a single scalar reward, which is converted to a sequence-level advantage A_{i} and applied uniformly to all tokens, sometimes after collapsing finer-grained scores into one objective. This induces a fundamental limitation for reasoning that any segment appearing in a successful trajectory is rewarded, regardless of whether it is actually helpful 30 ; 32 . Concretely, this leads to (i) degraded reasoning behavior, where long, redundant, or logically inconsistent chains of thought are treated as equally desirable as concise, sound ones; and (ii) noisy optimization signals, since genuinely useful decisions, early mistakes that are later corrected, and exploratory detours all share the same scalar reward. These issues motivate a token-level view of advantages, where intermediate reasoning fragments are evaluated rather than inheriting a single score determined only by the final outcome 10 ; 30 . However, assigning such token-level advantages is non-trivial. Rather than introducing an additional reward model or requiring dense process supervision, we obtain fine-grained learning signals from terminal scalar rewards via Monte Carlo advantage assignment 29 ; 6 ; 28 . Specifically, we aggregate outcomes across multiple sampled continuations to estimate the expected return of intermediate prefixes, and convert these estimates into structure-aware, segment-level advantages that are redistributed to corresponding tokens. Consequently, policy updates reflect how intermediate decisions affect downstream outcomes instead of applying a single sequence-level score uniformly. To address these challenges, we propose TreeAdv (Tree-Structured Advantage Redistribution for Group-Based RL), a training framework for token-level advantage assignment in reasoning models. At a high level, TreeAdv explicitly models the reasoning process as a tree of alternative continuations and uses this structure to assign advantages to individual reasoning tokens while correcting for shared prefixes. Rather than viewing highly correlated rollouts as a source of gradient noise, TreeAdv turns their tree-like topology into a source of informative signal about which local decisions truly contribute to success. Empirically, TreeAdv improves post-training performance on long-form reasoning benchmarks. It maintains the stability and computational practicality of Group-Based RL baselines while delivering higher accuracy and substantially reduced token usage, suggesting that token-level structure-aware optimization is an effective lever for training compact and efficient reasoning behaviors in LLMs. Our main contributions are threefold: 1. We introduce TreeAdv, a drop-in modification to GRPO-style group-based RL that adds structure-aware token-level advantages while keeping the training pipeline and memory footprint essentially unchanged. 2. On long-form mathematical reasoning benchmarks, TreeAdv achieves higher final accuracy than GRPO-style baselines and significantly reduces reasoning length, without degrading training stability in large-scale runs. 3. We analyze how sequence-level rewards lead to undesirable reasoning behavior and noisy optimization signals, as well as how tree-structured and token-level advantage can alleviate these issues from both behavioral and optimization perspectives. Standard GRPO x Rollout 1 x Rollout 2 x Rollout 3 Independent Sampling (Redundant Prefixes) TreeAdv Tree x H>\tau Leaf y_{1} R(y_{1}) Leaf y_{2} R(y_{2}) Shared Prefix Figure 1: Comparison of trajectory generation. Left: Standard GRPO samples independent rollouts that redundantly repeat prefixes. Right: TreeAdv constructs a tree by sharing prefixes and branching only at high-entropy states ( H>\tau ). 2 Related Work 2.1 Group-based Policy Optimization The computational and memory cost of PPO 20 , with its separate value network and GAE-style estimators 19 , has motivated group-based 4 ; 13 alternatives for training large reasoning-oriented LLMs. Group Relative Policy Optimization (GRPO) 21 estimates the baseline from the mean reward of a group of sampled outputs, removing the critic and substantially reducing memory usage in practice, which has enabled large long-context reasoning models such as DeepSeek-R1 5 . However, GRPO still assigns a single scalar reward to each sampled response and applies it uniformly to all tokens, making supervision inherently sequence-level and prone to reinforcing locally suboptimal reasoning whenever the final answer is correct 30 ; 32 . GSPO 33 refines this paradigm while preserving the same linear sampling scheme as GRPO. Instead of directly using one per-sequence advantage, GSPO smooths token-level signals by averaging token-wise weights along each sequence, which reduces gradient variance and improves training stability for large reasoning models 27 . Nonetheless, supervision is still aggregated at the level of whole sequences: all tokens in a response are ultimately updated according to one trajectory-level signal, and highly correlated tokens are treated as if they provided independent evidence. Our work is motivated by these sequence-level failure modes and recent token-level RL studies 10 . We depart from GRPO- and GSPO-style objectives by performing token-level reward assignment, so different parts of a trajectory receive qualitatively different advantages even within the same response. Rather than merely smoothing a single sequence-level signal over tokens, we organize overlapping reasoning paths into a tree and modulate token-level advantages using the induced topology (shared prefixes and branching structure). This yields a structure-aware objective that directly addresses the two issues identified in our Introduction: rewarding only segments that genuinely contribute to success,

Read the complete text