Resumo Técnico: LLaMEA-SAGE

Declaração do Problema

O Design de Algoritmos Automatizado (AAD - Automated Algorithm Design) utilizando Grandes Modelos de Linguagem (LLMs) emergiu como um paradigma promissor para a descoberta de algoritmos de otimização diretamente a partir de prompts de linguagem natural. No entanto, as abordagens baseadas em LLM existentes, como o LLaMEA, dependem quase exclusivamente de feedback de aptidão (desempenho em benchmarks) para guiar a busca evolutiva. Este ciclo de feedback de "caixa-preta" deixa uma quantidade substancial de informação dentro do código gerado sem uso. Consequentemente, as estratégias de busca frequentemente lutam para equilibrar exploração e explotação em espaços de código grandes e heterogêneos, levando à estagnação prematura ou ao uso ineficiente de consultas caras a LLMs. Além disso, há uma compreensão limitada de como melhorar sistematicamente algoritmos gerados por LLM após a geração inicial e como essas melhorias se comparam aos métodos de estado da arte (SOTA) sob benchmarks controlados.

Metodologia: LLaMEA-SAGE

O artigo propõe o LLaMEA-SAGE, um framework que integra feedback de Inteligência Artificial Explicável (XAI) estruturado ao processo de design de algoritmo evolutivo do LLaMEA. O mecanismo central envolve a extração de características estruturais do código dos algoritmos candidatos e o uso delas para guiar mutações subsequentes.

1. Extração de Características Estruturais

Cada algoritmo candidato é representado como código Python executável. O sistema analisa o código em uma Árvore de Sintaxe Abstrata (AST) para construir um grafo direcionado. A partir deste grafo, o sistema extrai um conjunto rico de características, incluindo:

• Estatísticas de teoria dos grafos: Contagens de nós/arestas, estatísticas de grau (média, variância, entropia), profundidade da árvore, coeficientes de agrupamento e métricas baseadas em caminhos (diâmetro, caminho médio mais curto).
• Indicadores de complexidade: Complexidade ciclomática, contagem de tokens de funções e contagem de parâmetros agregados entre funções.

2. Modelagem de Surrogacia Baseada em Arquivo

Durante o processo evolutivo, todas as soluções avaliadas, seus escores de aptidão e suas características de código extraídas são armazenados em um arquivo. Uma vez atingido um tamanho mínimo de arquivo, um modelo de árvore de regressão de boosting de gradiente (XGBoost) é treinado para aproximar a relação entre as características do código e a aptidão observada. Este modelo de surroga aprende relações não lineares entre a estrutura algorítmica e o desempenho.

3. IA Explicável (SHAP) para Orientação

Para derivar instruções acionáveis, o sistema aplica SHAP (SHapley Additive exPlanations) ao modelo de surroga treinado. Os valores SHAP quantificam a contribuição de cada característica para a aptidão prevista. A característica com a maior atribuição absoluta é selecionada, e o sinal de seu valor SHAP determina se o valor da característica deve ser aumentado ou diminuído para melhorar o desempenho.

4. Prompt de Mutação Guiada

A orientação estrutural é traduzida em uma instrução de linguagem natural que aumenta o prompt de mutação padrão fornecido ao LLM. Por exemplo, se a análise sugere que aumentar a complexidade ciclomática correlaciona-se com melhor desempenho, o prompt é modificado para: "Com base na análise do arquivo, tente aumentar a complexidade ciclomática total da solução."
Crucialmente, esta orientação enviesa a geração do LLM em direção a regiões estruturais empiricamente benéficas sem impor restrições sintáticas rígidas ou templates predefinidos, preservando a expressividade do LLM.

Principais Contribuições

1. Framework LLaMEA-SAGE: A proposta de um novo mecanismo que guia o AAD usando feedback baseado em características derivadas de AST e análise de complexidade, mediado por um modelo de surroga e análise SHAP.
2. Benchmarking Sistemático: Uma comparação experimental abrangente contra métodos de design de heurística baseados em LLM de estado da arte (SOTA), especificamente o MCTS-AHD (Busca em Árvore Monte Carlo para Design de Heurística de Algoritmo) e o LHNS (Busca de Vizinhança de Heurística Impulsionada por LLM), juntamente com a linha de base vanilla LLaMEA.
3. Validação Empírica: Demonstração de que a orientação estruturada melhora a qualidade e a robustez dos algoritmos em benchmarks de otimização de caixa-preta, apoiada por uma análise extensiva de Grafos de Evolução de Código (CEGs) e testes estatísticos.

Resultados Experimentais

Os autores avaliaram o LLaMEA-SAGE através de dois experimentos primários usando a toolbox de benchmarking IOH-BLADE.

Experimento 1: Comparação Controlada (SBOX-COST)

• Configuração: Comparou o LLaMEA vanilla contra o LLaMEA-SAGE em um subconjunto do suite SBOX-COST (10 dimensões, 5 instâncias).
• Descobertas: O LLaMEA-SAGE alcançou um desempenho melhor mais rapidamente do que o LLaMEA vanilla, particularmente nas fases iniciais do processo evolutivo. Embora ambos os métodos tenham atingido um desempenho final semelhante dentro do orçamento, a abordagem guiada mostrou menos variância entre as execuções.
• Significância Estatística: O LLaMEA-SAGE mostrou uma melhoria média de 11,1 unidades de Área Sob a Curva de Convergência (AUC) com um grande tamanho de efeito (Cliff's $\delta$ = 0,60). No entanto, devido ao número limitado de execuções independentes (5 sementes), a diferença não atingiu significância estatística ($p=0,44$).
• Análise Comportamental: Os Grafos de Evolução de Código revelaram que a orientação conseguiu enviesar a exploração estrutural. Notavelmente, o prompt de "refinar" levou a um aumento na complexidade do código quando guiado, enquanto o prompt de "novo aleatório" frequentemente ignorava a orientação ou resultava em menor complexidade.

Experimento 2: Benchmark de Larga Escala (MA-BBOB)

• Configuração: Avaliado no suite Many Affine BBOB (MA-BBOB), um padrão para competições GECCO, comparando LLaMEA-SAGE contra LLaMEA vanilla, MCTS-AHD e LHNS.
• Descobertas: O LLaMEA-SAGE superou consistentemente todos os baselines, incluindo os métodos SOTA MCTS-AHD e LHNS. Ele atingiu níveis de aptidão que o LLaMEA vanilla não conseguiu alcançar mesmo após o orçamento total de avaliação.
• Eficiência: Em termos de uso de tokens, o LLaMEA-SAGE foi marginalmente mais caro que o LLaMEA vanilla, mas significativamente mais eficiente que o MCTS-AHD (que consulta o LLM múltiplas vezes por solução).
• Generalização: A validação final em instâncias não vistas (diferentes dimensões e instâncias de problemas) mostrou que o melhor algoritmo descoberto pelo LLaMEA-SAGE superou outros algoritmos desenhados automaticamente e o vencedor da competição MA-BBOB de 2025 em tarefas de 10 e 20 dimensões, embora não tenha superado o vencedor da competição ajustado para a tarefa de 5 dimensões para a qual foi especificamente otimizado.

Significância e Alegações

O artigo afirma que o LLaMEA-SAGE consegue preencher a lacuna entre a estrutura do código e o feedback de desempenho compreensível por humanos no design de algoritmos automatizados. Ao traduzir sinais estruturais em linguagem natural, o método fornece um viés indutivo baseado em dados que direciona a evolução impulsionada por LLM sem restringir a capacidade criativa do modelo.

Os autores enfatizam que mesmo correlações imperfeitas e ruidosas derivadas de características de código são suficientes para beneficiar o viés da exploração nos estágios iniciais do AAD. O trabalho demonstra que sinais derivados de código podem efetivamente melhorar a eficiência e a estabilidade da descoberta de algoritmos, oferecendo uma alternativa escalável e livre de templates às abordagens existentes centradas em heurísticas.

Limitações e Trabalhos Futuros

Os autores notam modestamente algumas limitações:

• Dependência de LLM: Os experimentos foram conduzidos com um único backend de LLM (GPT-5-mini), embora uma ablação preliminar com Gemini tenha mostrado tendências consistentes.
• Escopo: A avaliação foi limitada à otimização de caixa-preta contínua em dimensões moderadas; a generalização para problemas de alta dimensão, ruidosos ou fundamentalmente diferentes permanece uma questão aberta.
• Análise Estática: O conjunto atual de características captura apenas propriedades estruturais estáticas, ignorando o comportamento de execução dinâmica ou efeitos de interação durante as execuções de otimização.

Trabalhos futuros são propostos para combinar características estruturais com descritores de tempo de execução, explorar orientação de múltiplas características adaptativas e integrar o mecanismo em outros frameworks de AAD baseados em LLM.