PaperlayerView exact revision on arXiv

Source-linked AI summary

APPO: Agentic Procedural Policy Optimization

Xucong Wang, Ziyu Ma, Yong Wang, Yuxiang Ji, Shidong Yang, Guanhua Chen, Pengkun Wang, Xiangxiang Chu

arXiv:2606.12384v2cs.LGcs.AI

TL;DR

Agentic RL often assigns credit at coarse tool-call or workflow boundaries, limiting attribution of outcomes to intermediate decisions. APPO branches and assigns credit at fine-grained sequence decision points, improving strong baselines by approximately 3 points across 13 benchmarks while keeping tool-calls efficient and behavior interpretable.

  • Problem

    Agentic RL provides trajectory-level feedback, making it difficult to attribute success or failure to specific intermediate decisions.

  • Method

    APPO uses a Branching Score combining token uncertainty with future-continuation likelihood gains to select fine-grained branching points and apply procedure-level credit scaling.

  • Results

    Approximately 3 points: APPO outperforms existing approaches across 13 benchmarks while achieving comparable tool-calls and maintaining interpretability.

  • Takeaways & Limitations

    Modeling procedural decisions offers a practical direction for improving exploration and credit assignment in agentic RL.

  • Takeaways & Limitations

    The theoretical guarantees rely on assumptions about conditional reward variance, policy divergence, and bounded future advantages.

Abstract

from arXiv · show

Recent advances in agentic Reinforcement Learning (RL) have substantially improved the multi-turn tool-use capabilities of large language model agents. However, most existing methods assign credit over coarse heuristic units, such as tool-call boundaries or fixed workflows, making it difficult to identify which intermediate decisions influence downstream outcomes. In this work, we study agentic RL from two perspectives: \textit{where to branch and how to assign credit after branching}. Our pilot analysis shows that influential decision points are broadly distributed throughout the generated sequence rather than concentrated at tool calls, while token entropy alone does not reliably reflect their impact on final outcomes. Motivated by these observations, we propose \textbf{Agentic Procedural Policy Optimization (APPO)}, which shifts branching and credit assignment from coarse interaction units to fine-grained decision points in the sequence. APPO selects branching locations using a Branching Score that combines token uncertainty with policy-induced likelihood gains of subsequent continuations, enabling more targeted exploration while filtering out spurious high-entropy positions. It further introduces procedure-level advantage scaling to better distribute credit across branched rollouts. Experiments on 13 benchmarks show that APPO consistently improves strong agentic RL baselines by nearly 4 points, while keeping efficient tool-calls and maintaining behavior interpretability.

1 Introduction

The introduction identifies coarse rollout units and token entropy as inadequate for assigning credit in long-horizon agent reasoning. It presents APPO, which branches at fine-grained procedural decision points and improves agentic RL performance across benchmarks while preserving tool-call efficiency and interpretability.

  • Problem: Existing methods assign credit using coarse units such as tool-call boundaries, <thinking> tags, or fixed workflows, overlooking procedural knowledge within reasoning.These designs partially densify sparse outcome supervision but compress non-tool-call reasoning into heuristic structures.
  • Motivation: Pilot analyses show that neither tool-call boundaries nor raw token entropy reliably identifies informative branching locations for credit assignment.High-uncertainty positions are not concentrated at tool-call boundaries, motivating criteria that account for procedural information throughout the sequence.
  • Method: APPO shifts branching and credit assignment from coarse heuristic units to fine-grained procedures across the entire generated sequence.Its Branching Score combines token entropy with policy-induced likelihood gains from subsequent continuations, while procedure-level advantage scaling distributes credit across branched rollouts.
  • Results: Approximately 3 points across 13 benchmarks: APPO outperforms existing approaches while achieving comparable tool-calls and maintaining interpretability.The evaluation spans deep information seeking, knowledge-intensive reasoning, and computational problem solving.

2 Related Work

Related work develops agentic reinforcement learning through more efficient policy variants and refined optimization terms, while tree-based RL organizes exploration around branching trajectories and preference data. These approaches provide the broader methodological context for APPO’s fine-grained branching and credit assignment.

  • Agentic Reinforcement Learning: Agentic RL builds on actor-critic PPO to improve long-horizon reasoning and acting through more efficient policy variants and refined policy-gradient, advantage, or regularization terms.Representative methods include GRPO, DAPO, GSPO, GPG, and Dr. GRPO.
  • Tree-based RL: Tree-based RL includes offline training, where branches from a shared point become preference data for later DPO training.MCTS-DPO compares candidate-node rewards, while SPORT uses step-wise sampling and automatic verification to construct step-wise preference data.
  • Tree-based RL: MCTS-DPO separates candidate nodes into chosen and rejected samples by comparing their estimated rewards.This is presented as an example of offline tree-based RL training.

3 APPO: Agentic Procedural Policy Optimization

APPO replaces coarse tool-call branching and credit assignment with fine-grained sequence decision points. It combines uncertainty with future influence for branching, then uses branched rollouts for procedure-level advantages.

  • Branching Procedure: APPO selects the top-B scored tokens in each rollout and resamples continuations there instead of branching only at fixed tool-call boundaries.Initial full rollouts form independent tree roots, and expansion continues under the global rollout budget.
  • Motivation: APPO targets latent decision points because token entropy can reflect lexical uncertainty rather than choices that alter downstream reasoning.Its goal is to identify positions where alternative continuations induce divergent reasoning paths.
  • Branching Score: The Branching Score multiplies normalized token entropy by normalized future influence, selecting tokens that are both uncertain and consequential.Future influence is computed using accumulated decayed importance-sampling ratios, with clipping and rollout-level z-score normalization.
  • Credit Assignment: APPO assigns localized procedural credit by estimating group-relative advantages separately for initial rollouts and branches, while treating branches as auxiliary signals.Generated tokens instantiate latent decision points, and the future-aware term scales the base advantage through a coefficient b.
  • Theoretical Guarantees: Under its stated assumptions, APPO’s BS-guided branching reduces gradient-estimator variance and its advantage design admits a policy improvement bound.The variance result compares APPO with random branching under the same computational budget, while the policy bound assumes bounded KL divergence and future-aware advantages.

4 Experiments

APPO is evaluated across mathematical, knowledge-intensive, and deep-search benchmarks against vanilla and agentic RL methods, language-model backbones, and search-agent baselines. Results and analyses show stronger performance, efficient exploration, and benefits from decision-point branching, procedural credit assignment, and balanced rollout allocation.

  • Experimental Setup: APPO evaluates mathematical reasoning, knowledge-intensive reasoning, and long-term complex tool-use benchmarks, including GSM8K, MATH, AIME24, AIME25, MATH500, and multi-hop Wikipedia question answering.The benchmark suite covers three task categories for comprehensive evaluation of complex tool usage.
  • Experimental Setup: The comparison includes vanilla RL methods, agentic RL methods, generalized and larger language-model backbones, search agents, RAG, and ReAct.Baselines include GRPO, Reinforce++, DAPO, GPPO, CISPO, GIGPO, ARPO, Search-o1, and Webthinker.
  • Main Results: 2.45 points: APPO improves over the previous best agentic RL method on mathematical reasoning tasks and surpasses all baselines across the mathematical and knowledge-intensive groups.F1-score evaluates four question-answering tasks; other tasks use LLM-as-a-Judge with pass@1.
  • Main Results: 42.7 and 46.6: APPO scores on GAIA with Qwen3-8B and Qwen3-14B, respectively, establishing state-of-the-art results at both model scales while improving HLE.The gains occur in deep-search tasks involving long horizons and intricate tool-use patterns.
  • Additional Analyses: APPO’s advantage persists and grows from Pass@1 to higher k across four datasets, improving both top-1 correctness and the diversity of valid reasoning paths.The analysis attributes this broader candidate-trajectory improvement to APPO’s effect on the overall sampling distribution, not only its best trajectory.
  • Additional Analyses: 58.1: under M = 16, the balanced configuration (N = 4, B = 3) outperforms (N = 8, B = 1) at 57.9 and the stated extreme alternative.The result shows that effectiveness depends on allocating rollout budget between initial trees and selected tokens.
  • Additional Analyses: 1.7 and 0.9 points: replacing the Branching Score with entropy reduces performance on the two backbones, while disabling dual-group advantage estimation also degrades results.The ablation indicates that the components contribute complementary rather than redundant gains.
  • Additional Analyses: APPO reaches a higher final reward with a more stable training trajectory than ARPO and produces more compact, better-separated reasoning-strategy clusters.Its Branching Score also avoids many rare high-entropy nouns whose uncertainty reflects vocabulary rarity rather than reasoning difficulty.

5 Conclusion · Appendix APPO: Agentic Procedural Policy Optimization

APPO moves branching and credit assignment to fine-grained sequence decision points, using a Branching Score and future-aware advantage scaling, and outperforms strong baselines across 13 benchmarks while retaining efficient tool-calls. The appendices provide proofs, experimental resources, implementation details, metric and budget studies, prompts, limitations, case studies, the algorithm, and related statements.

  • 5 Conclusion: APPO shifts branching and credit assignment from coarse tool- or workflow-level units to fine-grained decision points in generated sequences.Its Branching Score selects high-value branching locations, while extra future-aware advantage scaling targets credit assignment.
  • 5 Conclusion: 13 benchmarks show that APPO consistently outperforms strong baselines while keeping efficient tool-calls.The conclusion presents these results as evidence for APPO’s effectiveness and efficiency.
  • Appendix APPO: Agentic Procedural Policy Optimization: Appendix A gives proofs of theorems, and Appendix B introduces datasets and baselines.These appendices document the paper’s theoretical foundations and experimental resources.
  • Appendix APPO: Agentic Procedural Policy Optimization: Appendices C–E report full implementation details, alternative designs of the BS metric, and studies of the branching budget.Together, these appendices cover implementation and design analyses for APPO.
  • Appendix APPO: Agentic Procedural Policy Optimization: Appendices F–H report the prompts used, limitations, and case studies.These materials document prompting, limitations, and qualitative analyses.
  • Appendix APPO: Agentic Procedural Policy Optimization: Appendices I–K report the APPO algorithm, impact statement, and declaration of LLM usage.These appendices provide algorithmic documentation and required disclosures.

A Mathematical Proof · A.1 Proof of Theorem 3.1 · A.2 Proof of Theorem 3.2

The proofs establish that APPO’s proportional branching allocation minimizes gradient-estimator variance under i.i.d. branch rewards, while its surrogate-objective analysis bounds policy-improvement errors from distribution and weighting mismatch. Together, the arguments justify variance reduction and controlled updates under a KL constraint.

  • A.1 Proof of Theorem 3.1: APPO distributes a total branch budget across fine-grained decision points, assigning more branches to locations with higher Branching Scores.The proof denotes candidate locations by D_i, branch counts by n_i, and uses proportional allocation; top-BS selection approximates this rule in practice.
  • A.1 Proof of Theorem 3.1: Under i.i.d. branch rewards, the variance of each local gradient estimator decreases inversely with its assigned branch count.The conditional variance is specified as Var(g_i | D_i) = σ_i^2/n_i.
  • A.1 Proof of Theorem 3.1: Lagrange multipliers or Cauchy–Schwarz show that proportional allocation minimizes the summed estimator-variance term under the fixed branch budget.The minimizing allocation is strict unless all σ_i are equal.
  • A.1 Proof of Theorem 3.1: APPO therefore cannot increase estimator variance relative to the baseline allocation, with ΔΩ(BS) := Var(g_base) − Var(g_APPO) ≥ 0.The proof concludes the theorem by defining the variance difference and establishing its nonnegativity.
  • A.2 Proof of Theorem 3.2: The second proof begins from the performance difference J(π_new) − J(π_old) and analyzes the APPO surrogate optimized on the branching-mixture distribution ρ_q.The surrogate uses weighted advantages, so the proof tracks how the optimized objective differs from the target performance expression.
  • A.2 Proof of Theorem 3.2: The surrogate analysis separates two discrepancies: occupancy mismatch and weighting mismatch between the branching-mixture objective and the target policy-improvement expression.These terms are explicitly labeled in the proof’s decomposition.
  • A.2 Proof of Theorem 3.2: With bounded advantages and ∥ω∥∞ ≤ 1 + b(1 + ϵ′), the simulation lemma controls the mismatch terms; under KL(π_new∥π_old) ≤ ϵ, the total-variation contribution is O(√ϵ).The proof absorbs policy and occupancy errors into a single constant C to obtain the final bound.

B Datasets and Baselines.

The experiments cover mathematical reasoning, multi-hop question answering, web traversal, and practical agent evaluation through diverse benchmarks. They compare APPO against critic-free, PPO-derived, industrial-scale, gradient-stabilized, and open-source reasoning baselines.

  • Datasets: AIME24 and AIME25 each contain 30 competition-level problems, with AIME25 offering a relatively contamination-resistant test of mathematical reasoning.AIME24 performance is typically averaged across multiple runs because its small size makes it sensitive to variance; AIME25 was released in February 2025.
  • Datasets: MATH500 and MATH provide broad mathematical reasoning coverage, spanning seven subject categories and five difficulty levels in MATH500 and 12,500 competition problems in MATH.MATH includes step-by-step solutions, supporting both process-level and answer-level evaluation.
  • Datasets: GAIA, HLE, WebWalker, and XBench extend evaluation to tool-assisted problem solving, frontier knowledge, web navigation, and profession-aligned workplace tasks.GAIA contains 466 questions, HLE contains 2,500 questions, and WebWalkerQA contains 680 questions.
  • Baselines: Baselines include GRPO, REINFORCE++, DAPO, and GPPO, representing critic-free relative-reward optimization, PPO-derived stabilization, industrial-scale RL, and bounded-gradient policy updates.GRPO uses intra-group performance comparisons; REINFORCE++ uses token-level KL penalties and reward normalization; DAPO targets entropy collapse and instability; GPPO addresses gradient vanishing from hard clipping.
  • Baselines: QwQ is an open-source reasoning-model baseline whose flagship QwQ-32B uses extended chain-of-thought reasoning and achieves competitive performance against DeepSeek-R1 and OpenAI o1-mini.The QwQ series was first released in November 2024 by the Qwen team.

C Implementation Details

APPO uses a two-stage training pipeline combining ToolStar and STILL supervised fine-tuning with VERL-based reinforcement learning. The implementation masks tool execution outputs from loss computation and uses task-specific rollout, sequence-length, and training settings.

  • Supervised fine-tuning: APPO first trains its backbone with ToolStar’s 54K SFT dataset and 0.8K additional STILL samples.SFT uses LLAMA-Factory, a 7e-6 learning rate, DeepSpeed ZeRO-3, batch size 128, weight decay 0.1, 3 epochs, BF16 precision, and a 4096-token maximum input length.
  • Reinforcement learning: The RL stage implements APPO in VERL and excludes tool execution results from the loss, retaining textual reasoning and tool-call tokens.This masking avoids bias toward tool outputs.
  • DeepReasoning Tasks: For 7B DeepReasoning Tasks, training uses batch size 128, PPO mini-batch size 16, rollout size 16, initial sampling size 4, and a 4096-token response limit.APPO rollouts use entropy coefficient 0.2, parameter b 0.5, threshold 0.5, and clipping coefficient ϵ with non-symmetric setting [1,1.2].
  • Training and evaluation: The RL stage runs for 2 epochs on 8 NVIDIA H100 GPUs, with GRPO’s KL divergence coefficient fixed at 0 for training stability.The implementation also reports dataset-level averages alongside pass@3 and pass@5 results.
  • DeepSearch Tasks: DeepSearch Tasks increase the maximum response length to 8192 tokens for 8B models, retain the hyperparameters for 14B models, and train for 5 epochs on the 1K-sample dataset.The 14B experiments use 16 NVIDIA H100 GPUs.

D Alternative Designs of the BS metric

The section compares alternative Branching Score formulations that combine normalized entropy and future value, including future value alone. Additive designs identify reasoning-relevant tokens, whereas excessive emphasis on future value surfaces influential but training-irrelevant special tokens.

  • Alternative Branching Score formulations: The study evaluates four Branching Score settings, varying additive weights between normalized entropy and future value and including future value alone.Figure 7 presents word clouds for these formulations.
  • Alternative Branching Score formulations: Additive Branching Score designs capture tokens significant to reasoning, including “calculate”, “verify”, and “break”.These tokens are identified in the word clouds discussed for the alternative formulations.
  • Future-value bias: Future-value-biased metrics capture special tokens such as “’ll”, which may influence subsequent rollouts but do not reflect actual training value or fine-grained supervision.The passage attributes these tokens to positions where the model reaffirms existing conclusions.

E More Sensitivity Analysis of Key Hyper-parameters · F Prompts

The sensitivity analysis examines branching-loop depth and rollout-tree size, while the prompt specifies step-by-step reasoning, optional tool use, and structured reasoning and answer tags. A highlighted result reports weaker performance for one-branch initial rollouts in a multi-layer tree.

  • E More Sensitivity Analysis of Key Hyper-parameters: The main experiments use a single-layer rollout tree, applying all branching operations only to the initial rollout.
  • E More Sensitivity Analysis of Key Hyper-parameters: For multi-layer rollout trees, the rollout count is M = B · (N + 1)^L when L > 1.
  • E More Sensitivity Analysis of Key Hyper-parameters: 54.1% overall performance occurs for (N = 1, B = 2, L = 3, M = 16), approximately 1.1 points below the Table 3 case.The comparison case is (N = 2, B = 3, L = 1, M = 8).
  • E More Sensitivity Analysis of Key Hyper-parameters: The analysis attributes the weaker N = 1 result to insufficient diversity in the initial rollout.
  • F Prompts: APPO’s prompt instructs the assistant to solve questions step by step using the wikipedia search tool and python interpreter tool.
  • F Prompts: The prompt permits tool invocation during thinking and encloses the reasoning process and final response within <think> and <answer> tags.
  • F Prompts: The prompt formats Python code and interpreter output with <python> and <result> tags before the final answer.
  • F Prompts: The final exact answer is enclosed in LaTeX format in the last part of the response.

G Limitations … J Impact Statement

The paper reports APPO’s empirical limitations, illustrates its corrective branching behavior, specifies its training pipeline, and highlights its research and application impact. Its branching criterion lacks theoretical optimality guarantees, while the algorithm combines score-based token selection, continuation resampling, advantage estimation, and policy optimization.

  • G Limitations: APPO’s branching-point selection is validated only experimentally and lacks theoretical guarantees that the Branching Score is optimal.Fully quantifying a point’s branching value would require a more systematic framework and exploration of intrinsic LLM properties.
  • H Case Study: The case study covers branching-stage recoveries from initially wrong rollouts and inference cases where APPO solves tasks that ARPO fails.
  • I Algorithm: APPO’s training algorithm initializes with N full rollouts sampled through agent–environment interaction under the behavior policy.The pipeline takes a policy, reference policy, toolset, training set, rollout budget, rollout count, branching budget, PPO epochs, clipping thresholds, procedural weight, and decay factor as inputs.
  • J Impact Statement: APPO is presented as broadly valuable for research and applications including search systems, AI-assisted healthcare, and education, alongside commitments to regulatory compliance and safety governance.The impact statement also emphasizes broader efficacy improvements and increased automated behaviors.
  • I Algorithm: For each valid token position, APPO computes token entropy, future value, and Branching Score, then selects the top-B tokens for branching.This procedure evaluates every valid position in a sampled rollout and updates the rollout tree with selected branches.
  • I Algorithm: APPO resamples continuations from selected prefixes using the current policy and adds the resulting branches to the rollout trees.
  • I Algorithm: The method evaluates rewards across initial and branched rollouts and computes separate group-relative advantages for the two rollout groups.
  • I Algorithm: APPO applies future-aware procedural advantage scaling before optimizing the initial rollouts with KL regularization to the reference policy.

K Declaration of LLM Usage

LLMs were used only to polish the paper’s writing, not for other purposes.

  • LLMs are used only for polishing the writing of the paper.
Loading 2606.12384v2…