Source-linked AI summary
Contrastive Branch Policy Optimization
Ying Wang, Changlin Qiu, Bang Lin, Linbo Jin, Wen Jiang, Zhe Sun, Jingli Yang
TL;DR
RLVR and branch-based reinforcement learning lack precise signals for identifying which intermediate decisions drive successful tool interactions. CBPO separates branch-budget allocation from local credit assignment using full-response entropy scanning, decayed budget allocation, and exact-prefix outcome contrasts. Across ten benchmarks and two model scales, it consistently outperforms policy-optimization and branch-based baselines, achieving the highest macro average in both mathematical reasoning and knowledge-intensive search.
Problem
RLVR commonly provides sparse outcome rewards that do not identify which intermediate decisions are responsible for success, while branch methods conflate rollout-budget allocation with token-level credit assignment.
Method
CBPO scans generation entropy across complete responses to select branches and allocate budget with path- and node-level decay, then uses exact-prefix reward variation as bounded CBV credit without changing advantage signs.
Results
CBPO consistently outperforms state-of-the-art policy-optimization and branch-based methods across ten benchmarks and two model scales, attaining the highest macro average in both domains.
Takeaways & Limitations
Within the evaluated models, tasks, and budgets, uncertainty identifies alternative continuations while observed outcome variation provides the local credit signal.
Takeaways & Limitations
The independent contribution of full-response scanning still requires a controlled tool-boundary-only ablation, and the experiments evaluate benchmark accuracy rather than deployment safety.
Abstract
from arXiv · showhide
Reinforcement learning with verifiable rewards (RLVR) enables language models to learn multi-turn interaction with external tools, yet its sparse outcome rewards provide no signal for identifying which intermediate decisions are responsible for success. Branch sampling induces local comparisons among alternative continuations, but existing methods tend to conflate two distinct problems: allocating a fixed rollout budget and translating branch outcomes into token-level credit. We introduce Contrastive Branch Policy Optimization (CBPO), which disentangles these two problems and assigns a dedicated mechanism to each. Generation entropy screens candidate branch positions across the entire response, while path-level and node-level decay distribute a fixed budget across trajectories and positions to prevent exploration from collapsing onto a few paths or adjacent tokens. A parent trajectory together with the branches that share an identical token prefix forms an exact-prefix group, and the reward variation within this controlled group defines the Contrastive Branch Value (CBV), an outcome-based estimate of local decision sensitivity that rescales continuation advantages without altering their sign. When multiple nodes are selected along the same trajectory, CBPO partitions it into non-overlapping credit segments, thereby avoiding duplicated gradients on shared tokens. Requiring only outcome rewards and no process-level annotation, CBPO provides a practical solution for fine-grained credit assignment in tool-integrated agent training. Extensive experiments on ten benchmarks, including five for mathematical reasoning and five for knowledge-intensive search, show that CBPO consistently outperforms state-of-the-art policy-optimization and branch-based methods, attaining the highest macro-average accuracy in both domains and across two model scales.
1 Introduction
RLVR and branch-based methods improve tool-integrated reasoning but provide limited localization of decisive intermediate choices. CBPO separates budgeted branch discovery from outcome-based local credit assignment and performs strongly across ten benchmarks and two model scales.
- Motivation: RLVR commonly assigns one terminal reward uniformly across trajectory tokens, obscuring which intermediate decisions determine success.Process supervision and step-wise preference optimization provide finer signals but require intermediate labels or preferences.
- Motivation: Branch sampling compares continuations from shared histories using outcome rewards, but still needs principled branch placement and local policy updates under limited budgets.Entropy-only selection can cluster branches at adjacent positions, miss consequential decisions outside tool boundaries, or emphasize changes that do not affect final answers.
- CBPO: CBPO scans entropy across the response and uses path-level and node-level decay to distribute a fixed branch budget across trajectories and positions.This separates candidate discovery from credit assignment and prevents exploration from collapsing onto a few paths or adjacent tokens.
- CBPO: CBPO defines Contrastive Branch Value from reward variation within exact-prefix groups and uses bounded scaling to change continuation-advantage magnitude without changing its sign.Prefix masking and non-overlapping segmentation prevent duplicated credit on shared tokens.
- Results: CBPO consistently outperforms strong policy-optimization and branch-based methods across ten benchmarks and two model scales, achieving the highest macro average in both domains.The evaluation covers five tool-augmented mathematical benchmarks and five knowledge-intensive search benchmarks.
2 Related Work
Prior work improves tool-integrated reasoning through outcome optimization, process supervision, entropy signals, and tree-based comparisons. These approaches leave a need for finer credit assignment because decisive positions may occur before, during, or after tool interactions rather than only at tool-return boundaries.
- Outcome-based optimization: Trajectory-level policy optimization derives advantages from completed responses, assigning the same outcome-based signal across intermediate decisions.PPO and GRPO optimize from trajectory returns, while GSPO changes the optimization unit from tokens to sequences.
- Local signals: Process rewards and step-wise preferences offer denser intermediate supervision but require annotations, while entropy avoids annotation yet measures uncertainty rather than empirical outcome sensitivity.Learned value estimates can also introduce estimation error.
- Branch-based methods: Tree-based methods reuse prefixes to compare several continuations from intermediate states, enabling local contrasts at controlled cost.Online variants derive advantages from descendants, within-tree contrasts, or recurring histories.
- Tool-integrated reasoning: Tool-integrated reasoning requires selecting tools, constructing requests, timing calls, verifying responses, integrating results, and terminating appropriately.Search supplies open-world evidence, whereas code interpreters support calculation and programmatic verification.
- Credit-assignment gap: Tool-return boundaries capture only a subset of potentially decisive positions in long trajectories, where success may depend on pre-call reasoning, request construction, feedback interpretation, or post-call synthesis.This limits the coverage of methods that branch only after tool feedback.
- Knowledge-intensive reasoning: Knowledge-intensive agents must determine where additional computation or evidence can alter the final outcome, linking retrieval timing to the broader credit-assignment challenge.Adaptive retrieval studies address retrieval and verification rather than token-level credit assignment.
3 Preliminaries
The preliminaries formulate tool-integrated rollouts as autoregressive model-token generation conditioned on environmental observations and trained with bounded terminal rewards. They then describe GRPO's uniform trajectory advantage and entropy as a generation-uncertainty signal.
- Tool-integrated rollout: A tool-integrated trajectory interleaves model tokens, tool requests, and environmental observations, while autoregressive factorization applies to model-generated tokens.The model-token sequence is conditioned on tool observations available before each position.
- Tool-integrated rollout: Environmental observations condition subsequent generation but contribute neither likelihood terms nor policy gradients, and a verifier assigns a bounded terminal reward after termination.Training maximizes a KL-regularized expected reward relative to a frozen reference policy.
- Group-relative optimization: GRPO samples multiple trajectories for a problem and standardizes each trajectory's reward relative to its within-group mean and standard deviation.An epsilon term provides numerical stability.
- Group-relative optimization: Standard GRPO assigns each trajectory advantage to every model-generated token, making update magnitude uniform regardless of which intermediate decisions determine the outcome.This is the coarse credit-assignment setting that CBPO refines.
- Generation uncertainty: At each generation position, Shannon entropy measures dispersion in the next-token distribution, with larger entropy indicating greater uncertainty.Entropy reflects distributional uncertainty rather than confidence in the particular sampled token.
4 Contrastive Branch Policy Optimization
CBPO separates budgeted branch exploration from outcome-based token credit assignment. It scans entire responses for candidates, balances branch allocation, compares exact-prefix continuations through CBV, and constructs non-overlapping token advantages while preserving advantage signs.
- Entropy-Guided Balanced Branch Exploration: CBPO scans complete responses for high-entropy candidate positions rather than restricting branching to predefined tool boundaries.Fixed-interval entropy windows rank candidate locations, using truncated entropy only as a screening signal.
- Entropy-Guided Balanced Branch Exploration: Path-level and node-level decay distribute a fixed branch budget across less-explored trajectories and positions.Eligibility caps and fallback sampling of independent complete trajectories preserve the total rollout budget.
- Hierarchical Policy Optimization with CBV: Exact-prefix groups hold the preceding token history fixed while resampling continuations, enabling outcome comparisons that isolate continuation variation.The parent and its branches share the same prefix before reward comparison.
- Hierarchical Policy Optimization with CBV: CBPO uses bounded outcome rewards, including binary correctness for mathematical tasks and normalized token-level F1 or LLM-as-a-Judge scores for search tasks.All rewards are constrained to the interval [0, 1].
- Hierarchical Policy Optimization with CBV: Prefix masking and non-overlapping segmentation prevent copied prefixes and repeatedly shared intervals from receiving duplicated branch credit.Intermediate intervals shared by adjacent selected nodes receive equal weight rather than repeated suffix updates.
- Hierarchical Policy Optimization with CBV: CBV measures reward variation within exact-prefix groups and modulates continuation-advantage magnitude without changing its sign.Standardization provides a comparable signed signal, while bounded modulation preserves the local PPO gradient direction.
5 Experiments
Across ten benchmarks and two model scales, CBPO is evaluated under matched protocols, with results, qualitative analyses, and ablations testing its performance and design choices. CBPO achieves the strongest overall averages while balanced branching, full-response candidate selection, and CBV-based credit contribute to its behavior.
- Main Results: CBPO attains mathematical macro-average Pass@1 scores of 66.0% and 69.3% for Qwen3-1.7B and Qwen3-4B, respectively.These exceed ARPO by 1.7 and 2.2 percentage points.
- Main Results: CBPO attains search macro averages of 53.2 and 57.5, exceeding ARPO by 1.8 points at both model scales.Relative to OPD, the gains are 8.7 and 9.0 points.
- Main Results: CBPO consistently outperforms policy-optimization and branch-based methods across five mathematical and five knowledge-intensive search benchmarks.It achieves the highest macro average in both domains and leads four of five search benchmarks at each scale.
- Pass@K Extension: CBPO exceeds ARPO at every reported macro-average Pass@1, Pass@3, and Pass@5 value for both model scales.Pass@3/5 uses five independent samples per problem; the 1.7B scores are 66.0%, 74.6%, and 77.9%, while the 4B scores are 69.3%, 76.9%, and 80.2%.
- Training Dynamics and Branch Selection: CBPO achieves higher final mean reward than GIGPO and ARPO while averaging fewer tool calls per trajectory.Qualitative branch-selection examples show that decay can reorder high-entropy candidates before allocation.
- Ablation Study: Removing either decay level reduces the mathematical macro average by 1.5 points at both model scales, while removing both reduces it by 2.2 points.Removing CBV produces the largest losses: 3.0 points for Qwen3-1.7B and 2.9 points for Qwen3-4B.
- Branching Configuration: The highest macro average occurs with N=6 and B=10, balancing independent trajectory coverage against exact-prefix branch comparisons.Increasing the total budget M from 4 to 16 improves the macro average at both model scales.
6 Conclusion
CBPO separates branch-budget allocation from outcome-based credit assignment, using entropy and decay for exploration and CBV for local continuation weighting. Across ten benchmarks and two model scales, it consistently outperforms policy-optimization and branch-based baselines, while evidence remains bounded to the evaluated settings.
- 6 Conclusion: CBPO separates fixed-budget branch allocation from local credit assignment.Full-response entropy scanning with path-level and node-level decay allocates branches, while exact-prefix reward variation assigns continuation credit.
- 6 Conclusion: CBV modulates continuation contributions using reward variation within exact-prefix groups without changing advantage signs.Prefix masking and hierarchical segmentation also prevent duplicated credit on shared tokens.
- 6 Conclusion: 66.0% and 69.3% mathematical macro averages and 53.2 and 57.5 search averages are reported for Qwen3-1.7B and Qwen3-4B, respectively.Cross-scale ablations attribute distinct gains to balanced allocation and CBV.
- 6 Conclusion: The evidence supports a bounded design principle within the evaluated models, tasks, and budgets.Full-response scanning still requires a controlled boundary-only ablation to establish its independent contribution.
Ethical Considerations
The study uses public benchmarks without collecting new personal or human-subject data, but tool-integrated evaluation carries retrieval, code-execution, cost, and deployment-safety boundaries. High-stakes use therefore requires additional safeguards beyond benchmark accuracy.
- Ethical Considerations: The study uses public benchmarks and collects no new personal or human-subject data.
- Ethical Considerations: Open-web retrieval may expose models to inaccurate, biased, offensive, or privacy-sensitive material.Benchmark accuracy does not establish the reliability or social neutrality of retrieved sources.
- Ethical Considerations: Branch sampling incurs additional generation cost, although fixed rollout budgets and matched rollout slots bound and compare that cost.The experiments evaluate benchmark accuracy rather than deployment safety.
- Ethical Considerations: High-stakes applications require domain-specific testing, content filtering, access controls, and human oversight.Generated Python code runs in a sandbox, and tool calls are capped to limit security and resource risks.