Resumo Técnico: MURPHY – GRPO Consciente de Feedback com Atribuição de Crédito Retrospectiva

Declaração do Problema

A Aprendizagem por Reforço com Recompensas Verificáveis (RLVR) tornou-se uma abordagem padrão para o pós-treinamento de Modelos de Linguagem de Grande Escala (LLMs) em tarefas de raciocínio, com a Otimização de Política Relativa de Grupo (GRPO) emergindo como um método líder. No entanto, a GRPO padrão e suas variantes são inerentemente de turno único: otimizam com base em recompensas terminais de pares isolados de prompt-resposta. Essa arquitetura é inadequada para ambientes agênticos, particularmente na geração de código, onde os modelos devem refinar soluções iterativamente em resposta a feedback ambiental (por exemplo, erros de execução, rastros de pilha, casos de teste falhos).

Métodos de múltiplos turnos existentes frequentemente dependem de maquinário auxiliar complexo, como verificadores aprendidos (µCODE), críticos no estilo PPO (RLEF) ou políticas de verificação separadas (REVEAL). Uma linha de base natural, GRPO-MT, estende a GRPO para múltiplos turnos tratando interações condicionadas a feedback como trajetórias. No entanto, a GRPO-MT sofre de atribuição de crédito grosseira: atribui a mesma recompensa terminal a todos os tokens em uma trajetória, independentemente de tentativas intermediárias falhas terem fornecido feedback informativo que permitiu um refinamento posterior bem-sucedido. Na geração de código, uma tentativa falha não é uniformemente negativa; ela pode expor um caso de borda específico ou um erro de tempo de execução que é crucial para a solução eventual. Os métodos atuais falham em distinguir entre "falhas informativas" e "falhas não informativas" quando compartilham o mesmo resultado terminal.

Metodologia: MURPHY

Os autores introduzem o MURPHY (Atualização de Múltiplos Turnos com Otimização de Política Retrospectiva), uma extensão mínima da GRPO projetada para tornar a receita padrão de pós-treinamento consciente de feedback sem introduzir críticos aprendidos ou verificadores auxiliares.

1. Árvores de Rolagem Condicionadas a Feedback

O MURPHY constrói uma estrutura de árvore para cada prompt de entrada, em vez de uma trajetória linear:

• Turno 1: O modelo amostra um grupo de programas candidatos.
• Execução e Feedback: Cada candidato é executado contra uma suíte de testes, gerando uma recompensa escalar (por exemplo, taxa de aprovação) e feedback qualitativo (por exemplo, mensagens de erro).
• Expansão:
  • Candidatos resolvidos terminam e tornam-se nós folha.
  • Candidatos falhos são expandidos. Um novo prompt é formado concatenando a tarefa original, a saída falha e o feedback do executor. O modelo é reinvocado neste prompt condicionado a feedback para gerar um novo grupo de refinamentos.
• Este processo se repete por um número fixo de turnos, criando uma árvore onde as arestas representam etapas de refinamento condicionadas a feedback específico.

2. Atribuição de Crédito Retrospectiva

A inovação central é a atribuição de crédito retrospectiva. Após a conclusão da árvore de rolagem, as recompensas são propagadas para trás, das folhas até a raiz. Isso permite que refinamentos bem-sucedidos posteriores "creditem" tentativas falhas anteriores que produziram feedback útil. O artigo propõe duas estratégias de propagação:

• Recompensa Máxima (MARS): Um backup otimista. Para um nó $v$, a recompensa ajustada $\tilde{r}(v)$ é o máximo de sua recompensa imediata $r(v)$ e o máximo da recompensa ajustada de seus filhos:
  $$\tilde{r}(v) = \max\left(r(v), \max_{u \in C(v)} \tilde{r}(u)\right)$$
  Isso credita uma tentativa falha se qualquer de seus descendentes eventualmente resolver a tarefa.
• Recompensa Média (MERS): Um backup baseado em expectativa. Propaga uma média descontada de recompensas futuras:
  $$\tilde{r}(v) = r(v) + \gamma \cdot \frac{\text{média}_{u \in C(v)} \tilde{r}(u)}{Z(v)}$$
  onde $\gamma$ é um fator de desconto e $Z(v)$ é um termo de normalização.

3. Atualização Local GRPO

Uma vez que as recompensas são ajustadas, o MURPHY aplica o objetivo padrão da GRPO localmente a cada grupo de respostas dentro da árvore. Em vez de usar recompensas imediatas, utiliza as recompensas ajustadas por crédito ($\tilde{r}$) para calcular vantagens. Isso preserva a estrutura de linha de base relativa ao grupo da GRPO, incorporando crédito temporal da estrutura da árvore.

4. Estratégias de Poda

Para abordar o custo computacional da expansão de árvores (que pode crescer exponencialmente), o MURPHY introduz mecanismos de poda pós-rolagem que retêm trajetórias informativas antes da propagação de recompensas:

• Poda Intra-Grupo (INTRAP): Mantém um número fixo de trajetórias dentro de cada grupo de respostas, selecionando especificamente aquelas que contribuem mais para a variância da recompensa (preservando sinais de aprendizado diversos).
• Poda Inter-Grupo (INTERP): Mantém grupos inteiros de refinamento com base em sua variância de recompensa dentro do grupo. Isso aloca o orçamento de otimização para contextos de feedback que geram os refinamentos candidatos mais diversos e informativos.

Contribuições Principais

1. Algoritmo MURPHY: Uma extensão de GRPO de múltiplos turnos que treina LLMs de código para utilizar feedback de execução através de atribuição de crédito temporal estruturada, eliminando a necessidade de verificadores ou críticos aprendidos.
2. Estratégias de Propagação de Recompensa: A introdução de estratégias MARS (otimista) e MERS (baseada em expectativa) para atribuir crédito de refinamentos bem-sucedidos de volta a falhas anteriores e informativas.
3. Mecanismos de Poda: Projeto de estratégias INTRAP e INTERP que tornam a otimização de múltiplos turnos tratável, filtrando trajetórias não informativas enquanto preservam o sinal de aprendizado.
4. Validação Empírica: Avaliação abrangente em três benchmarks (HumanEval, MBPP, LiveCodeBench-v6) e duas famílias de modelos (Qwen, OLMo), demonstrando ganhos significativos sobre métodos de múltiplos turnos anteriores.

Resultados Experimentais

Os autores avaliaram o MURPHY no HumanEval, MBPP e LiveCodeBench-v6 usando modelos Qwen3 (1.7B, 4B) e OLMo-2-7B.

• Ganhos de Desempenho: O MURPHY alcançou até 6% de ganhos absolutos em pass@1 sobre os métodos de feedback de execução de múltiplos turnos anteriores mais fortes (incluindo GRPO-MT, µCODE e REVEAL).
• Escalonamento de Dificuldade: Os ganhos foram mais pronunciados nos subconjuntos Médio e Difícil. Por exemplo, no LiveCodeBench-v6 (subconjunto Médio), o MURPHY mostrou um ganho de +4,38% na Iter-5, e no subconjunto Difícil, um ganho de +4,20%. Isso sugere que o método é particularmente eficaz onde a auto-correção iterativa é crítica.
• Comparação com Linhas de Base:
  • No OLMo-2-7B, o MURPHY superou a linha de base mais forte em +6,20 pp no HumanEval e +6,07 pp no MBPP na configuração Iter-3.
  • No Qwen3-4B (LiveCodeBench-v6), o MURPHY superou o REVEAL (um método com um auto-verificador co-treinado) em todos os subconjuntos de dificuldade, apesar da arquitetura mais complexa do REVEAL.
• Estudos de Ablação:
  • MARS vs. MERS: O MARS geralmente superou o MERS, particularmente em configurações de recompensa esparsa, propagando o resultado mais forte em vez de diluir o sinal através da média.
  • Poda: A estratégia de poda INTERP ofereceu o melhor compromisso custo-qualidade, reduzindo o tempo de otimização em 74,1% (resultando em uma redução de 21,4% no tempo total de treinamento por etapa) enquanto mantinha o desempenho dentro de 0,8% do modelo não podado. O INTRAP, embora tenha melhorado o desempenho de turno único, causou uma regressão no desempenho de múltiplos turnos.

Significado e Alegações

O artigo afirma que o MURPHY demonstra que a receita padrão de pós-treinamento GRPO pode ser tornada consciente de feedback através de uma mudança estrutural na atribuição de crédito apenas.

• Minimalismo Arquitetural: Diferentemente de trabalhos anteriores que exigem funções de valor auxiliares, verificadores aprendidos ou políticas de verificação explícitas, o MURPHY é uma "extensão mínima, preservadora de arquitetura". Ele depende exclusivamente do feedback de execução inerente à tarefa de geração de código.
• Incompatibilidade de Atribuição de Crédito: O trabalho aborda uma incompatibilidade fundamental na geração de código agêntica: a falha em distinguir entre erros não informativos e falhas informativas. Ao propagar recompensas para trás, o MURPHY ensina ao modelo que "errar e errar de novo" (como citado de Piet Hein) é valioso se os erros fornecerem o sinal necessário para a correção.
• Escalabilidade: As estratégias de poda propostas tornam o treinamento de múltiplos turnos computacionalmente viável, reduzindo o ônus de otimização sem sacrificar a qualidade do sinal de aprendizado.

Os autores concluem que, embora as rolagens de múltiplos turnos aumentem os custos de treinamento em relação à GRPO de turno único, os ganhos nas capacidades de auto-correção, particularmente em problemas difíceis, justificam a abordagem. Eles notam limitações relacionadas ao aumento do custo de treinamento e à dependência de feedback de execução limpo, sugerindo que trabalhos futuros poderiam explorar sinais de feedback mais ruidosos e orçamentos de turnos adaptativos.