MARS^2: Scaling Multi-Agent Tree Search via Reinforcement Learning for Code Generation

arXiv:2604.14564v1 Announce Type: cross Abstract: Reinforcement learning (RL) paradigms have demonstrated strong performance on reasoning-intensive tasks such as code generation. However, limited trajectory diversity often leads to diminishing returns, which constrains the achievable performance ceiling. Search-enhanced RL alleviates this issue by introducing structured exploration, which remains constrained by the single-agent policy priors. Meanwhile, leveraging multiple interacting policies can acquire more diverse exploratory signals, but existing approaches are typically decoupled from structured search. We propose extbf{MARS^2} (Multi-Agent Reinforced Tree-Search Scaling), a unified RL framework in which multiple independently-optimized agents collaborate within a shared tree-structured search environment. MARS^2 models the search tree as a learnable multi-agent interaction environment, enabling heterogeneous agents to collaboratively generate and refine candidate solutions within a shared search topology. To support effective learning, we introduce a path-level group advantage formulation based on tree-consistent reward shaping, which facilitates effective credit assignment across complex search trajectories. Experiments on code generation benchmarks show that MARS^2 consistently improves performance across diverse model combinations and training settings, demonstrating the effectiveness of coupling multi-agent collaboration with tree search for enhancing reinforcement learning. Our code is publicly available at https://github.com/TsinghuaC3I/MARTI.

Related

• IG-Search: Step-Level Information Gain Rewards for Search-Augmented Reasoning
• From P(y|x) to P(y): Investigating Reinforcement Learning in Pre-train Space
• Cycle-Consistent Search: Question Reconstructability as a Proxy Reward for Search Agent Training
• Variance-Aware Prior-Based Tree Policies for Monte Carlo Tree Search

Source: arXiv cs.CL | 2026-04-17