Technische Samenvatting: MURPHY – Feedback-bewuste GRPO met Retrospectieve Krediettoewijzing

Probleemstelling

Versterkt Leren met Verifieerbare Beloningen (RLVR) is een standaardaanpak geworden voor het post-trainen van Large Language Models (LLM's) op redeneertaken, waarbij Group Relative Policy Optimization (GRPO) naar voren is gekomen als een toonaangevende methode. Echter, standaard GRPO en zijn varianten zijn inherent single-turn: ze optimaliseren op basis van terminale beloningen van geïsoleerde prompt-responsparen. Deze architectuur is ongeschikt voor agente omgevingen, met name in codegeneratie, waar modellen oplossingen iteratief moeten verfijnen als reactie op omgevingsfeedback (bijvoorbeeld uitvoeringsfouten, stacktraces, mislukte testcases).

Bestaande multi-turn methoden vertrouwen vaak op complexe hulpapparatuur, zoals geleerde verifiers (µCODE), PPO-achtige critici (RLEF) of aparte verificatiebeleid (REVEAL). Een natuurlijke baseline, GRPO-MT, breidt GRPO uit naar multi-turn door feedback-geconditioneerde interacties te behandelen als trajecten. GRPO-MT lijdt echter aan grove krediettoewijzing: het wijst dezelfde terminale beloning toe aan alle tokens in een traject, ongeacht of tussenliggende mislukte pogingen informatieve feedback leverden die een latere succesvolle verfijning mogelijk maakte. In codegeneratie is een mislukte poging niet uniform negatief; het kan een specifieke edge case of runtime-fout blootleggen die cruciaal is voor de uiteindelijke oplossing. Huidige methoden maken geen onderscheid tussen "informatieve mislukkingen" en "oninformatieve mislukkingen" wanneer ze dezelfde terminale uitkomst delen.

Methodologie: MURPHY

De auteurs introduceren MURPHY (Multi-turn Update with Retrospective Policy Optimization), een minimale uitbreiding van GRPO die is ontworpen om de standaard post-trainingreceptie feedback-bewust te maken zonder geleerde critici of hulpverifiers in te voeren.

1. Feedback-geconditioneerde Rolloutbomen

MURPHY construeert voor elke invoerprompt een boomstructuur in plaats van een lineair traject:

• Beurt 1: Het model steekt een groep kandidaatprogramma's.
• Uitvoering & Feedback: Elke kandidaat wordt uitgevoerd tegen een testset, wat een scalair beloning (bijvoorbeeld slaagpercentage) en kwalitatieve feedback (bijvoorbeeld foutberichten) oplevert.
• Uitbreiding:
  • Opgeloste kandidaten worden beëindigd en worden bladknopen.
  • Gefaalde kandidaten worden uitgebreid. Een nieuwe prompt wordt gevormd door de originele taak, de gefaalde output en de uitvoeringsfeedback te concateneren. Het model wordt opnieuw opgeroepen op deze feedback-geconditioneerde prompt om een nieuwe groep verfijningen te genereren.
• Dit proces wordt herhaald voor een vast aantal beurten, waardoor een boom ontstaat waarbij randen verfijningsstappen vertegenwoordigen die geconditioneerd zijn op specifieke feedback.

2. Retrospectieve Krediettoewijzing

De kerninnovatie is retrospectieve krediettoewijzing. Nadat de rolloutboom compleet is, worden beloningen achterwaarts doorgegeven van de bladeren naar de wortel. Dit laat toe dat latere succesvolle verfijningen "krediet" toekennen aan eerdere gefaalde pogingen die nuttige feedback produceerden. Het artikel stelt twee propagatiestrategieën voor:

• Max Beloning (MARS): Een optimistische backup. Voor een knoop $v$ is de aangepaste beloning $\tilde{r}(v)$ het maximum van zijn directe beloning $r(v)$ en het maximum van de aangepaste beloning van zijn kinderen:
  $$\tilde{r}(v) = \max\left(r(v), \max_{u \in C(v)} \tilde{r}(u)\right)$$
  Dit krediteert een gefaalde poging als een van zijn nakomelingen uiteindelijk de taak oplost.
• Gemiddelde Beloning (MERS): Een op verwachting gebaseerde backup. Het geeft een afgevlakte gemiddelde van toekomstige beloningen door:
  $$\tilde{r}(v) = r(v) + \gamma \cdot \frac{\text{mean}_{u \in C(v)} \tilde{r}(u)}{Z(v)}$$
  waarbij $\gamma$ een discontofactor is en $Z(v)$ een normalisatieterm.

3. Lokale GRPO-update

Zodra de beloningen zijn aangepast, past MURPHY de standaard GRPO-doelfunctie lokaal toe op elke responsgroep binnen de boom. In plaats van directe beloningen te gebruiken, maakt het gebruik van de krediet-geadjasteerde beloningen ($\tilde{r}$) om voordelen te berekenen. Dit behoudt de groepsrelatieve basisstructuur van GRPO terwijl het temporale krediet uit de boomstructuur integreert.

4. Snoeistrategieën

Om de rekenkosten van het uitbreiden van bomen (die exponentieel kunnen groeien) aan te pakken, introduceert MURPHY post-rollout snoeimechanismen die informatieve trajecten behouden voordat beloningspropagatie plaatsvindt:

• Intra-Groep Snoeien (INTRAP): Behoudt een vast aantal trajecten binnen elke responsgroep, specifiek die selecteren die het meest bijdragen aan beloningsvariatie (waarmee diverse leersignalen worden behouden).
• Inter-Groep Snoeien (INTERP): Behoudt volledige verfijningsgroepen op basis van hun binnen-groep beloningsvariatie. Dit wijst het optimalisatiebudget toe aan feedbackcontexten die de meest diverse en informatieve kandidaatverfijningen opleveren.

Belangrijkste Bijdragen

1. MURPHY-algoritme: Een multi-turn GRPO-uitbreiding die code-LLM's traint om uitvoeringsfeedback te benutten via gestructureerde temporale krediettoewijzing, waardoor de noodzaak voor geleerde verifiers of critici wordt geëlimineerd.
2. Beloningspropagatiestrategieën: De introductie van MARS (optimistisch) en MERS (op verwachting gebaseerd) strategieën om krediet toe te wijzen van succesvolle verfijningen terug naar eerdere, informatieve mislukkingen.
3. Snoeimechanismen: Ontwerp van INTRAP en INTERP strategieën die multi-turn optimalisatie haalbaar maken door oninformatieve trajecten te filteren terwijl het leersignaal behouden blijft.
4. Empirische Validatie: Omvattende evaluatie over drie benchmarks (HumanEval, MBPP, LiveCodeBench-v6) en twee model families (Qwen, OLMo), waarbij significante winsten worden aangetoond ten opzichte van eerdere multi-turn methoden.

Experimentele Resultaten

De auteurs evalueerden MURPHY op HumanEval, MBPP en LiveCodeBench-v6 met behulp van Qwen3 (1.7B, 4B) en OLMo-2-7B modellen.

• Prestatiewinsten: MURPHY behaalde tot 6% absolute winst in pass@1 ten opzichte van de sterkste eerdere multi-turn uitvoeringsfeedback-methoden (waaronder GRPO-MT, µCODE en REVEAL).
• Schaling met Moeilijkheidsgraad: Winsten waren het meest uitgesproken op Medium en Hard subsets. Bijvoorbeeld, op LiveCodeBench-v6 (Medium subset) toonde MURPHY een +4,38% winst bij Iter-5, en op de Hard subset een +4,20% winst. Dit suggereert dat de methode bijzonder effectief is waar iteratieve zelfcorrectie kritiek is.
• Vergelijking met Baselines:
  • Op OLMo-2-7B presteerde MURPHY +6,20 pp beter dan de sterkste baseline op HumanEval en +6,07 pp op MBPP in de Iter-3 setting.
  • Op Qwen3-4B (LiveCodeBench-v6) overtrof MURPHY REVEAL (een methode met een gezamenlijk getrainde self-verifier) over alle moeilijkheidsgraden, ondanks de complexere architectuur van REVEAL.
• Ablatiestudies:
  • MARS vs. MERS: MARS presteerde over het algemeen beter dan MERS, met name in settings met schaarse beloningen, door het sterkste resultaat door te geven in plaats van het signaal te verdunnen door middel van gemiddelden.
  • Snoeien: De INTERP snoeistrategie bood de beste kosten-kwaliteit trade-off, waarbij de optimalisatietijd met 74,1% werd gereduceerd (wat resulteerde in een 21,4% reductie in totale trainingstijd per stap) terwijl de prestaties binnen 0,8% van het niet-gepoetste model bleven. INTRAP, hoewel het de single-turn prestaties verbeterde, veroorzaakte een regressie in multi-turn prestaties.

Betekenis en Claims

Het artikel beweert dat MURPHY aantoont dat de standaard GRPO post-trainingreceptie feedback-bewust kan worden gemaakt door uitsluitend een structurele wijziging in krediettoewijzing.

• Architecturale Minimalisme: In tegenstelling tot eerdere werken die hulpwaardefuncties, geleerde verifiers of expliciete verificatiebeleid vereisen, is MURPHY een "minimale, architectuurbehoudende uitbreiding". Het vertrouwt uitsluitend op de uitvoeringsfeedback inherent aan de codegeneratietaken.
• Mismatch in Krediettoewijzing: Het werk adresseert een fundamentele mismatch in agente codegeneratie: het falen om onderscheid te maken tussen oninformatieve fouten en informatieve mislukkingen. Door beloningen achterwaarts door te geven, leert MURPHY het model dat "vergissen en weer vergissen" (zoals geciteerd uit Piet Hein) waardevol is als de fouten het noodzakelijke signaal voor correctie bieden.
• Schaalbaarheid: De voorgestelde snoeistrategieën maken multi-turn training rekenkundig haalbaar, waarbij de optimalisatiebelasting wordt verminderd zonder in te leveren op de kwaliteit van het leersignaal.

De auteurs concluderen dat hoewel multi-turn rollouts de trainingkosten verhogen ten opzichte van single-turn GRPO, de winsten in zelfcorrectiecapaciteiten, met name bij moeilijke problemen, de aanpak rechtvaardigen. Zij merken beperkingen op met betrekking tot de verhoogde trainingkosten en de afhankelijkheid van schone uitvoeringsfeedback, en suggereren dat toekomstig werk kan onderzoeken naar ruwere feedbacksignalen en adaptieve beurtbudgetten.