Resumo Técnico: Alocação de Computação em Busca Evolutiva

Enunciado do Problema

Sistemas de busca evolutiva guiados por Modelos de Linguagem de Grande Escala (LLMs) (por exemplo, FunSearch, AlphaEvolve, CodeEvolve) alcançaram resultados de última geração em descoberta matemática e otimização combinatória. No entanto, a literatura existente relata predominantemente o único melhor resultado de um número não especificado de execuções, deixando a distribuição entre execuções sem documentação. Além disso, os custos computacionais relatados variam em ordens de grandeza, tornando difícil avaliar a confiabilidade de uma única execução sob um orçamento fixo.

O problema central abordado é a alocação de computação: dado um orçamento fixo de chamadas de LLM ($C$), como esse orçamento deve ser distribuído entre profundidade (refinamento sequencial de uma única trajetória) e largura (exploração paralela de múltiplas trajetórias)? Sistemas atuais frequentemente fixam esses hiperparâmetros (por exemplo, tamanho da população e contagem de gerações) sem uma compreensão sistemática de como a alocação afeta o desempenho esperado e a confiabilidade.

Metodologia

1. Caracterização Empírica da Alocação Profundidade–Largura

Os autores conduziram um estudo empírico sistemático em três tarefas de otimização geométrica (Empacotamento de Círculos, MinMaxDist, Triângulo de Heilbronn) e quatro tamanhos de modelo (Qwen3-1.7B a 14B, mais Llama-3.1-8B). Eles definiram o problema de alocação como dividir o orçamento $C$ em $T$ gerações de $N$ filhos paralelos ($C = T \times N$).

• Envelope Aptidão–Computação: Eles analisaram a relação entre a aptidão alcançável e os FLOPs efetivos (considerando o tamanho do modelo e a eficiência de cache). Eles observaram que, embora modelos maiores liderem em contagens iguais de chamadas, sua ordenação de desempenho colapsa em grande parte quando medida contra FLOPs efetivos, desde que o par modelo-tarefa seja "capaz".
• Regularidade Profundidade–Largura: Eles ajustaram um modelo bilinear paramétrico à paisagem de aptidão:
  $$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$$
  onde $V$ é a aptidão. O coeficiente de interação $c$ determina a geometria da alocação ótima:
  • Ótimos de Canto ($|c| \approx 0$): Tarefas como Empacotamento de Círculos exibem planaltos amplos onde muitas alocações produzem resultados semelhantes, frequentemente favorecendo a profundidade.
  • Cristas Interiores ($c < 0$): Tarefas como MinMaxDist exibem uma crista aguda onde uma mistura equilibrada de profundidade e largura é necessária para o desempenho ótimo.
  • Portaria de Capacidade: Essas regularidades só se mantêm para modelos que cruzaram um limiar de capacidade para a tarefa específica; modelos fracos falham em exibir trocas estruturadas profundidade–largura.

2. BaSE: Auto-Evolução Baseada em Bandido

Motivados pela alta variância nos resultados das execuções (onde configurações idênticas produzem pontuações finais de aptidão amplamente diferentes devido à estocasticidade no processo de mutação do LLM), os autores propuseram o BaSE.

• Mecanismo: O BaSE trata a busca evolutiva como um problema de Bandido de Múltiplos Braços (MAB). Em vez de comprometer todo o orçamento a uma única trajetória (Guloso) ou a um conjunto fixo de ilhas (protocolo de Ilhas), o BaSE mantém $K$ trajetórias paralelas.
• Alocação Adaptativa: Em cada etapa, um algoritmo de bandido (UCB, EXP3.P ou Amostragem de Thompson) seleciona qual trajetória estender com a próxima chamada de LLM. Isso roteia dinamicamente a computação de execuções estagnadas para as promissoras.
• Ortogonalidade: O BaSE não altera o modelo base, o prompt ou a lógica de amostragem de pais dentro de uma trajetória. Ele opera estritamente no nível da alocação de recursos entre trajetórias.

Resultados Chave

1. Regularidades Empíricas

• Colapso de Capacidade: Para modelos capazes, o envelope de desempenho é determinado pelos FLOPs efetivos e não apenas pelo tamanho do modelo.
• Geometria Dependente da Tarefa: A divisão ótima profundidade–largura não é universal; depende da "família algorítmica" da tarefa (por exemplo, se a solução requer uma biblioteca específica como scipy ou uma construção analítica específica).
• Estocasticidade: Mesmo com alocação fixa, execuções individuais variam significativamente. Algumas execuções convergem para alta aptidão, enquanto outras estagnam cedo devido ao travamento em uma família algorítmica subótima.

2. Desempenho do BaSE

• Melhoria na Aptidão Média: Em 8 células (modelo, tarefa), o BaSE melhorou a melhor aptidão média em 12,3% sobre as bases mais fortes de protocolo de ilha (por exemplo, OpenEvolve, CodeEvolve, ShinkaEvolve) sem alterar o modelo ou o prompt.
• Ganhos de Confiabilidade: Os ganhos mais significativos foram observados em configurações de alta variância. Por exemplo, na tarefa Triângulo de Heilbronn com Llama-3.1-8B, métodos sem BaSE frequentemente falharam em produzir soluções válidas (aptidão $\approx 0$), enquanto o BaSE (Amostragem de Thompson) alcançou uma aptidão média de 0,4387.
• Eficiência de Amostragem: O BaSE atingiu limiares de aptidão alvo significativamente mais rápido (menos gerações e FLOPs) do que bases gulosa ou de alocação fixa. Por exemplo, em MinMaxDist, o UCB atingiu um limiar de 0,95 em 92 gerações, enquanto a base gulosa exigiu 485.
• Ablação: Tamanhos moderados de pool de braços ($K \in \{5, 10, 20\}$) forneceram o melhor compromisso entre diversidade e profundidade de refinamento.

Significado e Alegações

O artigo alega que a alocação de computação é uma alavanca distinta e crítica para melhorar a busca evolutiva guiada por LLMs, separada da escalabilidade do modelo ou da engenharia de prompts.

• Alocação vs. Engenharia: Os autores enfatizam que suas melhorias não se devem a prompts ou modelos melhores. De fato, eles observam que algumas bases (como ShinkaEvolve) alcançaram pontuações altas em tarefas específicas parcialmente devido a dicas induzidas por prompts (por exemplo, sugerir scipy.optimize), enquanto o BaSE alcança ganhos puramente através do roteamento adaptativo de recursos.
• Confiabilidade: A contribuição principal é deslocar o foco do relato de "melhor caso" para o desempenho "esperado". O BaSE fornece um ganho de confiabilidade, garantindo que um praticante tenha menos probabilidade de desperdiçar um orçamento fixo em uma trajetória que já estagnou.
• Complementaridade: O BaSE é apresentado como complementar aos mecanismos existentes dentro da execução (como amostragem de pais). Ele pode ser sobreposto a protocolos existentes (Guloso, Ilha) para melhorar ainda mais o desempenho, particularmente em configurações instáveis ou de alta variância.

O trabalho conclui que, embora a capacidade do modelo estabeleça o teto do que é alcançável, a alocação governa quão eficientemente um método se aproxima desse teto, e a alocação adaptativa via bandidos é uma estratégia robusta para busca com orçamento finito.