Resumo Técnico: Descoberta de Algoritmos com LLMs: Busca Evolutiva encontra Aprendizado por Reforço

Declaração do Problema

A descoberta de algoritmos eficientes para problemas complexos, particularmente em matemática e otimização combinatória, historicamente dependeu de expertise humana substancial. Embora avanços recentes em Modelos de Linguagem de Grande Escala (LLMs) combinados com busca evolutiva (por exemplo, o método FunSearch) tenham mostrado promessa na automação dessa descoberta, abordagens existentes tratam o LLM como um gerador estático. Esses métodos utilizam o LLM para propor novos programas com base em sucessos anteriores, mas falham em atualizar os parâmetros internos do modelo com base nos sinais obtidos durante a exploração evolutiva. Consequentemente, eles perdem a oportunidade de aproveitar a natureza paramétrica do LLM para refinar sua política de busca ao longo do tempo, potencialmente levando a convergência subótima ou exploração ineficiente do espaço de soluções.

Metodologia: EvoTune

Os autores propõem o EvoTune, um framework que integra estreitamente busca evolutiva com Aprendizado por Reforço (RL) para refinar continuamente o operador de busca do LLM. O método opera em um loop iterativo consistindo de duas fases alternadas:

1. Busca Evolutiva (Exploração):

   • O LLM gera programas candidatos em Python (algoritmos) com base em prompts construídos a partir de programas de alta pontuação descobertos em iterações anteriores.
   • Esses programas são avaliados em tarefas específicas de otimização combinatória (por exemplo, Bin Packing, Problema do Caixeiro Viajante, Flatpack) para obter pontuações de recompensa (tipicamente o gap de otimalidade negativo).
   • Programas válidos e suas pontuações são armazenados em um banco de dados de programas, organizados em "ilhas" para manter a diversidade e prevenir convergência prematura.
   • A busca emprega uma estratégia de "bootstrapping", onde o LLM analisa as diferenças entre programas de alto e baixo desempenho para guiar a geração de novos candidatos.

2. Treinamento RL (Refinamento):

   • Periodicamente (a cada $f_{RL}$ iterações), a política de geração do LLM ($\pi_\theta$) é atualizada usando os dados acumulados da busca evolutiva.
   • Os autores formulam isso como um problema de Otimização de Preferência. Eles constroem um conjunto de dados de preferência $D_{pref}$ consistindo de tripletos $(x, y^+, y^-)$, onde $x$ é o prompt, $y^+$ é um programa com recompensa mais alta e $y^-$ é um programa com recompensa mais baixa.
   • O modelo é ajustado finamente usando Otimização Direta de Preferência (DPO). Diferentemente do DPO offline padrão, o EvoTune opera em um cenário off-policy onde os dados são gerados dinamicamente pelo próprio modelo em evolução.
   • Preservação de Diversidade: Uma escolha de design crítica é o uso de regularização Forward KL (em oposição ao Reverse KL mais comum) dentro do objetivo DPO. Isso encoraja comportamento de "cobertura de massa", prevenindo que o modelo colapse em um único modo e preservando a diversidade de saída essencial para a busca evolutiva eficaz.

Contribuições Principais

1. Integração de RL na Busca Evolutiva: O artigo afirma ser o primeiro a demonstrar o potencial de integrar estreitamente a busca evolutiva baseada em LLM com ajuste fino via RL no loop. Diferentemente de métodos anteriores que usam LLMs apenas como geradores estáticos, o EvoTune atualiza os pesos do modelo para melhor utilizar insights ganhos da exploração.
2. Descoberta Acelerada de Algoritmos: Ao refinar a política de busca via RL, o método acelera a descoberta de algoritmos superiores. Experimentos em três LLMs ajustados para instruções (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) mostram ganhos de desempenho consistentes sobre o método FunSearch de base.
3. Alinhamento que Preserva Diversidade: Os autores demonstram a vantagem de usar um objetivo de alinhamento modificado (DPO regularizado com Forward KL) para preservar a diversidade de saída. Isso é crítico para estratégias evolutivas, pois o colapso de modos pode impedir a descoberta de soluções novas.
4. Ampla Aplicabilidade: O método é validado em benchmarks diversos, incluindo problemas combinatórios padrão (Bin Packing, TSP, Flatpack), desafios do mundo real do Google Hash Code (Otimização de Datacenter, Viagens de Motorista Autônomo) e tarefas de regressão simbólica (LLM-SR).

Resultados Experimentais

Os autores avaliaram o EvoTune contra uma base de estilo FunSearch (busca evolutiva sem treinamento de modelo) em múltiplas tarefas e modelos:

• Ganhos de Desempenho: O EvoTune consistentemente alcançou pontuações de recompensa finais mais altas (gaps de otimalidade mais baixos) para os 50 programas descobertos superiores em comparação com a base. A diferença de desempenho frequentemente aumentou conforme o orçamento de amostragem aumentou, sugerindo que orçamentos maiores amplificam as vantagens do método.
• Generalização: Os programas evoluídos demonstraram robustez em conjuntos de validação perturbados e conjuntos de teste extraídos da mesma distribuição, indicando que as políticas aprendidas generalizam além das instâncias específicas vistas durante o treinamento.
• Benchmarks do Mundo Real:
  • Na tarefa de Otimização de Datacenter do Google Hash Code, o EvoTune alcançou uma pontuação de 418, superando a pontuação humana máxima de 407 e superando a base FunSearch (414).
  • Em tarefas de Regressão Simbólica (LLM-SR), o EvoTune superou a base evolutiva e, notavelmente, superou bases usando modelos maiores ou proprietários (por exemplo, Mixtral 8x7B, GPT-3.5-turbo) enquanto usava um modelo menor (Phi-3.5 Mini, 3,8 bilhões de parâmetros).
• Estudos de Ablação:
  • Forward vs. Reverse KL: Experimentos confirmaram que a regularização Forward KL produz recompensas mais altas e um maior número de soluções únicas em comparação com o Reverse KL, validando a importância da preservação de diversidade.
  • RL Alternativo: Os autores testaram o ReSTEM (Ajuste Fino Supervisionado em saídas de alta pontuação) como alternativa ao DPO. Os resultados indicaram que o DPO consistentemente superou o ReSTEM e foi menos sensível ao ajuste de hiperparâmetros.

Significado e Alegações

O artigo posiciona o EvoTune como um passo significativo para frente no design automatizado de algoritmos ao abordar a "Lição Amarga" (Sutton, 2019), que argumenta que busca e aprendizado são sinérgicos. Os autores afirmam que:

• Sinergia: A busca gera novos dados, enquanto o aprendizado destila padrões desses dados para guiar a exploração futura de forma mais eficaz.
• Eficiência: Integrar RL permite que o sistema vá além de meramente aumentar a pontuação média de uma população; ele guia ativamente a busca evolutiva em direção a soluções superiores (medidas pelo desempenho top-k) enquanto mantém a diversidade necessária para inovação.
• Escalabilidade: O método demonstra potencial para escalar para configurações do mundo real, como evidenciado pelo seu sucesso em problemas complexos e não sintéticos, como otimização de datacenter e modelagem de tensão-deformação.

Os autores modestamente reconhecem limitações, notando que seus experimentos foram conduzidos com modelos variando de 1 bilhão a 3,8 bilhões de parâmetros e que maior escalabilidade do tamanho do modelo e orçamentos de amostragem são necessários para entender plenamente o potencial do método. Eles também destacam o trade-off entre os custos computacionais adicionais da fase de treinamento RL e os ganhos em eficiência de inferência e qualidade da solução.