Technical Summary: MURPHY – Feedback-Aware GRPO with Retrospective Credit Assignment

Problem Statement

Reinforcement Learning with Verifiable Rewards (RLVR) has become a standard approach for post-training Large Language Models (LLMs) on reasoning tasks, with Group Relative Policy Optimization (GRPO) emerging as a leading method. However, standard GRPO and its variants are inherently single-turn: they optimize based on terminal rewards from isolated prompt-response pairs. This architecture is ill-suited for agentic settings, particularly in code generation, where models must iteratively refine solutions in response to environmental feedback (e.g., execution errors, stack traces, failing test cases).

Existing multi-turn methods often rely on complex auxiliary machinery, such as learned verifiers (µCODE), PPO-style critics (RLEF), or separate verification policies (REVEAL). A natural baseline, GRPO-MT, extends GRPO to multi-turn by treating feedback-conditioned interactions as trajectories. However, GRPO-MT suffers from coarse credit assignment: it assigns the same terminal reward to all tokens in a trajectory, regardless of whether intermediate failed attempts provided informative feedback that enabled a later successful refinement. In code generation, a failed attempt is not uniformly negative; it may expose a specific edge case or runtime error that is crucial for the eventual solution. Current methods fail to distinguish between "informative failures" and "uninformative failures" when they share the same terminal outcome.

Methodology: MURPHY

The authors introduce MURPHY (Multi-turn Update with Retrospective Policy Optimization), a minimal extension of GRPO designed to make the standard post-training recipe feedback-aware without introducing learned critics or auxiliary verifiers.

1. Feedback-Conditioned Rollout Trees

MURPHY constructs a tree structure for each input prompt rather than a linear trajectory:

• Turn 1: The model samples a group of candidate programs.
• Execution & Feedback: Each candidate is executed against a test suite, yielding a scalar reward (e.g., pass rate) and qualitative feedback (e.g., error messages).
• Expansion:
  • Solved candidates terminate and become leaf nodes.
  • Failed candidates are expanded. A new prompt is formed by concatenating the original task, the failed output, and the executor feedback. The model is re-invoked on this feedback-conditioned prompt to generate a new group of refinements.
• This process repeats for a fixed number of turns, creating a tree where edges represent refinement steps conditioned on specific feedback.

2. Retrospective Credit Assignment

The core innovation is retrospective credit assignment. After the rollout tree is complete, rewards are propagated backward from the leaves to the root. This allows later successful refinements to "credit" earlier failed attempts that produced useful feedback. The paper proposes two propagation strategies:

• Max Reward (MARS): An optimistic backup. For a node $v$, the adjusted reward $\tilde{r}(v)$ is the maximum of its immediate reward $r(v)$ and the maximum adjusted reward of its children:
  $$\tilde{r}(v) = \max\left(r(v), \max_{u \in C(v)} \tilde{r}(u)\right)$$
  This credits a failed attempt if any of its descendants eventually solve the task.
• Mean Reward (MERS): An expectation-based backup. It propagates a discounted average of future rewards:
  $$\tilde{r}(v) = r(v) + \gamma \cdot \frac{\text{mean}_{u \in C(v)} \tilde{r}(u)}{Z(v)}$$
  where $\gamma$ is a discount factor and $Z(v)$ is a normalization term.

3. Local GRPO Update

Once rewards are adjusted, MURPHY applies the standard GRPO objective locally to each response group within the tree. Instead of using immediate rewards, it uses the credit-adjusted rewards ($\tilde{r}$) to compute advantages. This preserves the group-relative baseline structure of GRPO while incorporating temporal credit from the tree structure.

4. Pruning Strategies

To address the computational cost of expanding trees (which can grow exponentially), MURPHY introduces post-rollout pruning mechanisms that retain informative trajectories before reward propagation:

• Intra-Group Pruning (INTRAP): Retains a fixed number of trajectories within each response group, specifically selecting those that contribute most to reward variance (preserving diverse learning signals).
• Inter-Group Pruning (INTERP): Retains entire refinement groups based on their within-group reward variance. This allocates the optimization budget to feedback contexts that yield the most diverse and informative candidate refinements.

Key Contributions

1. MURPHY Algorithm: A multi-turn GRPO extension that trains code LLMs to utilize execution feedback through structured temporal credit assignment, eliminating the need for learned verifiers or critics.
2. Reward Propagation Strategies: The introduction of MARS (optimistic) and MERS (expectation-based) strategies to assign credit from successful refinements back to earlier, informative failures.
3. Pruning Mechanisms: Design of INTRAP and INTERP strategies that make multi-turn optimization tractable by filtering uninformative trajectories while preserving the learning signal.
4. Empirical Validation: Comprehensive evaluation across three benchmarks (HumanEval, MBPP, LiveCodeBench-v6) and two model families (Qwen, OLMo), demonstrating significant gains over prior multi-turn methods.

Experimental Results

The authors evaluated MURPHY on HumanEval, MBPP, and LiveCodeBench-v6 using Qwen3 (1.7B, 4B) and OLMo-2-7B models.

• Performance Gains: MURPHY achieved up to 6% absolute pass@1 gains over the strongest prior multi-turn execution-feedback methods (including GRPO-MT, µCODE, and REVEAL).
• Difficulty Scaling: Gains were most pronounced on Medium and Hard subsets. For example, on LiveCodeBench-v6 (Medium subset), MURPHY showed a +4.38% gain at Iter-5, and on the Hard subset, a +4.20% gain. This suggests the method is particularly effective where iterative self-correction is critical.
• Comparison to Baselines:
  • On OLMo-2-7B, MURPHY outperformed the strongest baseline by +6.20 pp on HumanEval and +6.07 pp on MBPP in the Iter-3 setting.
  • On Qwen3-4B (LiveCodeBench-v6), MURPHY surpassed REVEAL (a method with a co-trained self-verifier) across all difficulty subsets, despite REVEAL's more complex architecture.
• Ablation Studies:
  • MARS vs. MERS: MARS generally outperformed MERS, particularly in sparse-reward settings, by propagating the strongest outcome rather than diluting the signal through averaging.
  • Pruning: The INTERP pruning strategy offered the best cost-quality trade-off, reducing optimization time by 74.1% (yielding a 21.4% reduction in total per-step training time) while maintaining performance within 0.8% of the unpruned model. INTRAP, while improving single-turn performance, caused a regression in multi-turn performance.

Significance and Claims

The paper claims that MURPHY demonstrates that the standard GRPO post-training recipe can be made feedback-aware through a structural change to credit assignment alone.

• Architectural Minimalism: Unlike prior works that require auxiliary value functions, learned verifiers, or explicit verification policies, MURPHY is a "minimal, architecture-preserving extension." It relies solely on the execution feedback inherent to the code generation task.
• Credit Assignment Mismatch: The work addresses a fundamental mismatch in agentic code generation: the failure to distinguish between uninformative errors and informative failures. By propagating rewards backward, MURPHY teaches the model that "err and err again" (as quoted from Piet Hein) is valuable if the errors provide the necessary signal for correction.
• Scalability: The proposed pruning strategies make multi-turn training computationally feasible, reducing the optimization burden without sacrificing the quality of the learning signal.

The authors conclude that while multi-turn rollouts increase training costs relative to single-turn GRPO, the gains in self-correction capabilities, particularly on difficult problems, justify the approach. They note limitations regarding the increased training cost and the reliance on clean execution feedback, suggesting future work could explore noisier feedback signals and adaptive turn budgets.