Semantic Evolution over Populations for LLM-Guided Automated Program Repair

1. O Problema

O artigo aborda as limitações atuais das abordagens de Reparo de Programas Automatizado (APR) baseadas em Grandes Modelos de Linguagem (LLMs), especificamente nos métodos de refinamento iterativo.

Embora os LLMs tenham mostrado potencial para gerar e melhorar correções de código, os métodos de ponta (como REx e ChatRepair) enfrentam desafios críticos:

• Convergência Prematura e Falta de Diversidade: Estratégias ganancias tendem a convergir rapidamente para uma única hipótese estrutural, descartando direções alternativas de reparo.
• Incapacidade de Identificar Famílias Semânticas: Diferentes candidatos podem parecer sintaticamente distintos, mas representar a mesma estratégia de reparo (ou vice-versa). Os métodos atuais não conseguem agrupar ou raciocinar sobre essas famílias.
• Dificuldade em Combinar Correções Parciais: A correção correta muitas vezes requer múltiplas mudanças complementares que raramente são descobertas simultaneamente em uma única geração. Métodos de trajetória única não conseguem preservar e recombinar insights parciais de diferentes candidatos.
• Otimização Local Estrutural: Quando uma hipótese de reparo é fundamentalmente incorreta (ex: assumir que um lado de um array está sempre ordenado), o refinamento local apenas produz variações superficiais do mesmo erro, sem escapar do ótimo local.
• Dependência de Sinais Escalares: A maioria dos métodos depende apenas da taxa de aprovação de testes (um número), ignorando a estrutura rica das falhas (quais testes específicos falharam).

2. Metodologia: EvolRepair

Os autores propõem o EvolRepair, um framework que formula o APR baseado em LLMs como um algoritmo evolutivo semântico. Em vez de refinar um único candidato, o sistema mantém e evolui uma população de hipóteses de reparo.

Componentes Principais:

1. Formulação Baseada em População:

   • O sistema mantém um conjunto de candidatos de reparo ($P$) em cada geração.
   • A busca avança da refinamento de nível de candidato para a exploração de nível populacional.

2. Operadores Evolutivos Conscientes de Semântica:

   • Mutação Semântica: O LLM atua como um operador de mutação, mas em vez de perturbações sintáticas cegas, ele gera edições condicionais baseadas no contexto do programa e no feedback estruturado de falhas (relatórios de erro, entradas que falharam).
   • Agrupamento Comportamental (Behavioral Grouping): Os candidatos são agrupados com base nos subconjuntos de testes que passam, e não apenas na pontuação de aptidão (pass rate). Isso identifica "famílias" de reparos que lidam com as mesmas regiões comportamentais do programa.
   • Recombinação em Nível de População (Cross-over): Diferente do crossover clássico de dois pais, o EvolRepair usa o LLM para sintetizar um novo reparo a partir de um pool de candidatos (um grupo inteiro). O LLM integra lógicas complementares descobertas em diferentes candidatos dentro do grupo para criar uma solução mais forte.

3. Seleção e Sobrevivência:

   • Os candidatos são avaliados e classificados. A seleção de sobreviventes prioriza a taxa de aprovação, mas o processo de agrupamento e recombinação garante que a diversidade semântica seja preservada.
   • O sistema decide dinamicamente se deve refinar uma família de reparo existente ou mudar para uma abstração alternativa se as falhas indicarem que a hipótese atual é estruturalmente falha.

Fluxo de Trabalho (Algoritmo):

1. Inicialização: Geração de uma população inicial de candidatos via LLM.
2. Agrupamento: Classificação dos candidatos em grupos comportamentais baseados na similaridade dos testes aprovados (usando sobreposição de Jaccard).
3. Amostragem Cruzada: Criação de grupos mistos para garantir diversidade.
4. Recombinação: O LLM gera novos candidatos combinando insights de grupos inteiros.
5. Mutação: Refinamento individual de candidatos selecionados com base em relatórios de falha específicos.
6. Seleção: Formação da próxima geração mantendo os melhores e mais diversos candidatos.

3. Contribuições Chave

1. Evolução Semântica Baseada em População: Eleva o reparo de um refinamento de trajetória única para uma exploração populacional, permitindo raciocínio sobre famílias de hipóteses e composição de correções parciais.
2. Operadores Evolutivos Conscientes de Semântica: Substitui os operadores baseados em sintaxe dos algoritmos genéticos clássicos (como GenProg) por componentes acionados por LLMs que entendem o contexto e o feedback de execução.
3. Avaliação Empírica Robusta: Demonstra que o EvolRepair supera significativamente as abordagens existentes de APR baseadas em LLM.

4. Resultados Experimentais

Os experimentos foram realizados em um conjunto de dados sintético derivado do LiveCodeBench (326 soluções defeituosas em 120 problemas) e comparados com REx e ChatRepair usando três backbones de LLMs diferentes (Llama 3.3, Kimi K2, DeepSeek V3.1).

• Desempenho Geral (RQ1): O EvolRepair alcançou consistentemente as melhores taxas de sucesso (Pass@1 e Pass@3).
  • No modelo DeepSeek V3.1, alcançou 96.63% (Pass@1) e 98.18% (Pass@3), superando o REx (94.48% / 95.32%) e o ChatRepair (93.25% / 95.27%).
  • As melhorias foram consistentes em todos os modelos base, indicando que o ganho vem da estratégia de busca e não apenas do LLM subjacente.
• Cobertura Comportamental (RQ2): O EvolRepair apresentou a maior Taxa de Cobertura de Testes (TCC) e a menor Lacuna de Cobertura ($\Delta$). Isso significa que ele explora regiões comportamentais mais amplas e consegue consolidar correções parciais em um único candidato final melhor do que os métodos de trajetória única.
• Eficácia do Crossover Semântico (RQ3): O estudo mostrou que o operador de recombinação consegue efetivamente combinar correções parciais complementares de diferentes pais. Em Llama 3.3, a taxa de combinação foi de 61.72%, provando que o sistema não apenas recria trajetórias existentes, mas sintetiza novas soluções a partir de partes de várias.
• Estudo de Ablação (RQ4):
  • Remover a mutação causou a maior queda de desempenho, destacando a importância do refinamento guiado por feedback.
  • Remover o crossover também reduziu o desempenho, confirmando a necessidade de combinar comportamentos.
  • Agrupamento baseado em comportamento superou agrupamento baseado apenas em pontuação de aptidão ou aleatório.

5. Significado e Conclusão

O EvolRepair representa uma mudança de paradigma no APR guiado por LLMs. Ao tratar o reparo como um processo evolutivo populacional consciente de semântica, o framework resolve o problema de "cegueira" dos métodos iterativos atuais, que frequentemente ficam presos em ótimos locais estruturais.

A principal lição é que a diversidade de hipóteses e a capacidade de compor correções parciais distribuídas em diferentes candidatos são essenciais para encontrar soluções corretas em problemas complexos. O trabalho sugere que o futuro do APR não está apenas em melhorar os prompts de um único modelo, mas em arquiteturas de busca que gerenciam e evoluem coletivamente múltiplas estratégias de reparo.