CATPO: Critique-Augmented Tree Policy Optimization
CATPO uses tree informativeness scoring and critique-guided repair to improve mathematical reasoning accuracy to 37.5%.
Key Findings
Methodology
This paper introduces CATPO, combining dense step-level reward propagation over tree-structured rollouts, a novel tree informativeness score F(T) based on leaf outcome diversity and policy-reward decorrelation, and critique-guided healing for dead-wrong trees. The informativeness score is computed without extra cost during sampling, classifying trees into regimes. Dead-wrong trees are located at shallow failure points, critiqued via natural language prompts, and grafted with refined continuations. The normalized F(T) scales the policy advantage, focusing updates on informative trees. Experiments on Qwen2.5-Math-1.5B demonstrate a 37.5% macro accuracy, surpassing TreeRPO by 1.9% and GRPO by 4.8% across four benchmarks.
Key Results
- CATPO achieves 37.5% macro accuracy on four math benchmarks, outperforming TreeRPO (35.6%) and GRPO (32.7%) with improvements of 1.9% and 4.8%. The method significantly enhances training efficiency, especially on challenging datasets like AIME24 and OlympiadBench.
- Tree informativeness score F(T) correlates strongly with per-tree gradient norms (Pearson r=0.54, p=4.1e-5), validating its role as a proxy for gradient utility.
- Critique-guided healing improves dead-wrong trees in 88.1% of cases, raising their F(T) scores and recovering training signals otherwise lost, demonstrating the repair mechanism's effectiveness.
Significance
This work addresses the inefficiency in tree-based reinforcement learning by identifying and repairing uninformative trees, leading to better sample efficiency and reasoning performance. It introduces a theoretically grounded, zero-cost tree scoring mechanism and a practical critique-based repair strategy, paving the way for more scalable and effective training of large language models in complex reasoning tasks. The approach enhances both academic understanding and industrial applications, enabling models to learn more transferable reasoning skills with less wasted compute.
Technical Contribution
The core technical innovation lies in defining the tree informativeness score F(T), which combines leaf outcome diversity and policy-reward decorrelation, computed at zero additional cost. The critique-guided healing locates the earliest failure point, generates targeted natural language critiques, and grafts refined continuations, effectively transforming uninformative trees into informative ones. The normalized F(T) then weights the policy gradient, focusing updates on valuable samples. This integrated framework advances tree-structured RL by enabling dynamic filtering and repair, unlike prior methods that treat all trees equally.
Novelty
This is the first work to explicitly quantify tree informativeness in RL over tree-structured rollouts, integrating natural language critique to repair dead-wrong trees dynamically. Unlike previous approaches that uniformly weight trees, CATPO adaptively identifies and enhances the most informative trees, significantly improving training efficiency and model reasoning capabilities. The combination of zero-cost scoring and critique-based repair introduces a new paradigm in tree-based RL for large language models.
Limitations
- The critique-guided repair depends on the model’s own ability to generate accurate critiques; in cases of complex or ambiguous errors, repair effectiveness diminishes.
- The method's computational overhead increases with tree depth and branching factor, potentially limiting scalability in very large trees.
- In tasks beyond mathematical reasoning, the effectiveness of critique repair remains to be validated, especially where error signals are less explicit or harder to diagnose.
Future Work
Future directions include integrating external knowledge sources for more accurate critique generation, developing adaptive thresholds for tree classification, and extending the framework to multi-modal reasoning tasks. Additionally, exploring more efficient sampling strategies and scalable repair mechanisms will further enhance applicability to real-world large-scale models and complex multi-task scenarios.
AI Executive Summary
In recent years, large language models (LLMs) have achieved remarkable progress in reasoning tasks, driven by reinforcement learning techniques such as RLHF. However, existing tree-based sampling methods like TreeRPO and GRPO, while providing dense step-level rewards, suffer from inefficiencies due to uninformative trees—such as all-correct or all-failed branches—that contribute little to training updates. These inefficiencies waste computational resources and limit model performance improvements.
This paper introduces CATPO, a novel approach that enhances tree-structured reinforcement learning by assessing the informativeness of each sampled tree and selectively focusing training efforts. The core innovation is the tree informativeness score F(T), which combines leaf outcome diversity with the correlation between policy confidence and propagated rewards, computed at negligible cost during sampling. Trees with low scores—particularly dead-wrong trees—are targeted for critique-guided healing, where the model identifies the earliest failure point, generates a natural language critique, and grafts refined continuations to recover training signals.
The final step involves weighting each tree’s gradient contribution by its normalized informativeness score, effectively concentrating updates on the most valuable samples. Extensive experiments on the Qwen2.5-Math-1.5B model across four benchmarks demonstrate that CATPO achieves a macro accuracy of 37.5%, surpassing prior methods by significant margins. The results validate the effectiveness of the scoring and repair mechanisms, showing improved sample efficiency and reasoning accuracy.
Overall, CATPO offers a scalable, theoretically grounded framework for improving tree-based RL, with broad implications for advancing large-scale reasoning systems. Future work will explore external knowledge integration, adaptive thresholds, and multi-modal reasoning to further enhance robustness and applicability in real-world scenarios.
Deep Analysis
Background
随着大规模语言模型（LLMs）在自然语言处理中的广泛应用，强化学习（RL）逐渐成为提升模型推理能力的重要工具。早期方法如RLHF通过人类偏好引导训练，但面临样本效率低、奖励信号稀疏的问题。树结构探索技术如TreeRPO和TreeRL通过多分支采样提供更丰富的奖励信息，但未能区分有用与无用的树，导致大量计算资源浪费。近年来，研究者开始关注树的有效性评估与修复，试图提升样本利用率和训练效率。本文在此基础上，提出树信息评分机制和批判修复策略，旨在解决树中不信息树的低效问题，为树结构RL的实际应用提供新思路。
Core Problem
现有树结构强化学习方法在训练过程中，未能有效识别和利用有信息的树，导致大量无效或低效的树结构浪费计算资源。尤其是在复杂推理任务中，死错树（全失败）和死对树（全正确）占据大量采样，未能贡献有效梯度，限制模型性能提升。如何在保证训练效率的同时，筛选出最具潜力的树结构，成为亟需解决的问题。此外，死错树的训练信号难以利用，限制了模型的学习能力，亟需引入机制修复或重塑这些树结构。
Innovation
本文的核心创新在于引入树信息评分F(T)，结合叶子多样性和策略-奖励的相关性，零成本评估树的潜在信息价值。对全失败树采用自然语言批判引导修复，定位错误节点并 graft修正分支，有效恢复训练信号。最后，将归一化的F(T)作为梯度加权因子，集中训练资源于最有潜力的树。这一机制区别于传统的平面采样和全树采样，提供了树级别的筛选与修复策略，显著提升样本利用率和模型性能。
Methodology
- �� 树采样：从模型策略中采样N叉树，深度D，生成多分支推理路径。
- �� 树信息评分：定义F(T) = ˆp(1−ˆp) · (1−ρ²π,r)，结合叶子成功率与策略-奖励相关性，评估树的潜在信息价值。
- �� 树分类：根据F(T)值，将树划分为死正确、死错误、陈旧和有信息四类，采用不同策略处理。
- �� 批判修复：对死错树定位最浅错误节点，生成自然语言批评， graft修正分支，重新评分和传播奖励。
- �� 梯度加权：利用F(T)归一化后作为梯度贡献的权重，调整训练焦点。
- �� 优化目标：在TREERPO基础上引入树信息加权，结合剪切的代理优势函数，进行策略优化。
Experiments
采用MATH数据集的训练集（7.5k题）进行训练，测试在MATH-500、OlympiadBench、MinervaMath和AIME24四个基准上。模型使用Qwen2.5-Math-1.5B，参数设置包括温度0.6、分支因子8、深度3、最大步长384。对比基线为GRPO和TreeRPO，评估指标为Pass@1（平均8次采样正确率）。通过调节阈值τlow、τhigh，验证树信息评分的有效性。还进行了梯度相关性分析和死错树修复效果验证，确保方法的有效性。
Results
实验结果显示，CATPO在四个基准上的宏平均准确率达到37.5%，优于TreeRPO（35.6%）和GRPO（32.7%），提升幅度分别为1.9%和4.8%。树信息评分F(T)与梯度范数显著相关（r=0.54），验证了其作为梯度贡献代理的有效性。批判修复显著改善死错树的训练信号，88.1%的死错树F值获得提升，验证了修复机制的实用性。这些结果表明，信息筛选与修复机制有效提升了树结构RL的训练效率和模型性能。
Applications
该方法适用于需要高效推理与学习的自动问答、数学推理、逻辑推断等场景。特别适合大规模模型在复杂任务中的训练，能显著提升样本利用率和推理准确性。未来可结合多模态信息，扩展到多任务、多模态推理系统，推动智能系统的自主学习能力。
Limitations & Outlook
方法依赖模型自身的批判能力，面对复杂或边界问题时，修复效果有限。极端困难任务可能无法通过修复改善性能。计算成本在树深度和分支数较大时增加，限制了大规模应用。此外，修复机制对模型的依赖较强，未来需结合外部知识或多模态信息增强修复效果。
Plain Language Accessible to non-experts
想象你在做一道复杂的数学题，就像在一个迷宫中寻找出口。每次你尝试不同的路径（树的分支），有些路径明显走错了（死错树），浪费了时间。这个方法就像有个聪明的助手，能告诉你哪些路径更有希望（树信息评分），还会帮你修正错误的路（批判修复），让你更快找到正确的出口。通过不断评估和修正，整个过程变得更高效，最后你能更快解决难题。这就像在迷宫里，有个聪明的指南针，不仅指示方向，还能帮你修正错误，节省大量时间和精力。
ELI14 Explained like you're 14
想象你在玩一个超级复杂的拼图游戏。每次你拼一部分，有些拼块拼错了（死错树），浪费了很多时间。这个方法就像有个聪明的朋友，能告诉你哪些拼图更重要（树信息评分），还会帮你修正错误的拼图（批判修复），让你更快完成拼图。它会评估每一块拼图的价值，优先处理那些能带来最大帮助的部分。如果发现某个拼图完全错了，它会帮你找到错误的地方，给出建议，然后帮你修正。这样，你就能用更少的时间，拼出完整的图，比以前快多了！
Abstract
Reinforcement learning with verifiable rewards (RLVR) has become a dominant paradigm for improving the reasoning capabilities of large language models (LLMs). Recent tree-based methods such as TreeRPO extend flat trajectory sampling with tree-structured rollouts to obtain dense, step-level reward signals without a separate process reward model. However, not all trees are equally informative: trees where all leaves succeed, all leaves fail, or the policy already predicts the reward distribution contribute little to gradient updates, wasting compute. We introduce CATPO (Critique-Augmented Tree Policy Optimization), which diagnoses and addresses this waste at the tree level. CATPO first scores each tree via a tree informativeness score, F(T), combining leaf-outcome diversity with policy-reward decorrelation at zero extra compute. For dead-wrong trees where all branches fail, CATPO applies critique-guided healing: it locates the shallowest failure point, generates a natural-language critique, and grafts refined continuations to recover training signal. Finally, an informativeness-weighted loss scales each tree's gradient contribution by its normalized score, concentrating parameter updates on the most informative trees while preserving overall gradient magnitude. Experiments on Qwen2.5-Math-1.5B trained with the MATH dataset show that CATPO achieves 37.5% macro accuracy across four benchmarks (AIME24, MATH-500, OlympiadBench, and MinervaMath), improving over TreeRPO by 1.9% and GRPO by 4.8%.