Algorithmic algorithm development with LLMs: A Case Study on LLM-Usage for Contraction Order Optimization in Tensor Networks

Resumo Técnico: Desenvolvimento de Algoritmos Algorítmicos com LLMs

Definição do Problema
O artigo investiga a aplicação de Modelos de Linguagem de Grande Escala (LLMs) à tarefa científica central de desenvolvimento e melhoria de algoritmos, focando especificamente na otimização da ordem de contração para redes de tensores. Determinar uma sequência de contração ótima para uma rede de tensores (TN) é um problema NP-difícil onde o objetivo é minimizar o número de operações de ponto flutuante (FLOPs) e os requisitos de memória intermediária. Embora existam heurísticas e meta-heurísticas (ex: algoritmos gulosos, simulated annealing), os autores exploram se agentes evolutivos baseados em LLM podem descobrir algoritmos superiores sem a automação de ponta a ponta do ciclo de pesquisa. O estudo utiliza o OpenEvolve, um agente de codificação evolutiva de código aberto, para evoluir código Python que determina ordens de contração.

Metodologia
Os autores empregam um framework experimental controlado usando o OpenEvolve, que combina mutações de código geradas por LLM com busca evolutiva baseada em ilhas e um arquivo de diversidade de qualidade no estilo MAP-Elites. A configuração envolve:

• Estado Inicial: Um algoritmo de linha de base guloso "muito estúpido" que contrai índices em ordem decrescente de tamanho.
• Avaliação: Um avaliador automatizado calcula a contagem de FLOPs para uma determinada ordem de contração em um conjunto de redes de tensores (geradas como produtos escalares de Matrix Product States periódicos). A avaliação baseia-se em contagens teóricas de FLOPs em vez de execução real para garantir estabilidade e reprodutibilidade.
• Métricas: O alvo principal de otimização é o log10 de aceleração (speedup) relativo a uma linha de base "cotengra cheap" (uma heurística padrão). As métricas secundárias incluem mediana, máximo, mínimo e redução total de FLOPs.
• Variáveis Experimentais: O estudo varia sistematicamente:
  1. Escolha do LLM: Testando vários modelos de pesos abertos (ex: GPT-OSS-20B/120B, Qwen3.5, MiniMax, Gemma-4) com diferentes esforços de raciocínio.
  2. Reprodutibilidade: Executando 20 ensaios independentes com diferentes sementes aleatórias para avaliar a estocasticidade.
  3. Métricas de Otimização: Alterando a função objetivo (ex: otimizando para aceleração média vs. mínima).
  4. Dados de Teste: Treinando em diferentes subconjuntos de redes de tensores ("pequenas", "médias", "grandes") para observar a generalização.

Principais Resultados

• Sensibilidade do Modelo: A escolha do LLM impacta significativamente os resultados. O GPT-OSS-20B com esforço de raciocínio "alto" foi o único modelo a superar consistentemente a linha de base em redes de tensores "pequenas" (alcançando uma aceleração média de log10 de +0,06, uma redução de ~1,15x nos FLOPs) e mostrou melhoria significativa em redes "médias" (+1,67, uma redução de ~47x). Modelos maiores (ex: GPT-OSS-120B) e outros modelos abertos frequentemente falharam em melhorar ou performaram pior que a linha de base.
• Estocasticidade: As execuções evolutivas são altamente estocásticas. Embora as execuções individuais variem amplamente, conjuntos de execuções mostram tendências de convergência, particularmente com maiores esforços de raciocínio.
• Influência de Métricas e Dados: A definição do "escore combinado" e a seleção dos casos de teste são críticas. Otimizar para a aceleração "média" teve melhor desempenho do que otimizar para a aceleração "mínima" ou "redução total de FLOPs". Além disso, otimizar em redes de tensores "pequenas" rendeu a melhor generalização entre todos os tamanhos de rede, enquanto otimizar em redes "médias" teve o pior desempenho.
• Descoberta Algorítmica: O "melhor" algoritmo evoluído (do GPT-OSS-20B) não descobriu um novo paradigma fundamental, mas refinou uma abordagem conhecida. Ele utilizou uma estratégia de min-fill gulosa com atualizações explícitas de preenchimento (fill-in) e refinamento local (troca de posições adjacentes). Notavelmente, introduziu um peso substituto (surrogate weighting) não padrão para arestas de preenchimento prospectivas: penalizando por min(log dim a, log dim b) em vez das medidas multiplicativas (aditivas no espaço logarítmico) padrão. Essa heurística rendeu resultados razoáveis, apesar de carecer de justificativa teórica prévia na literatura.
• Restrições de Tempo de Execução: Embora o algoritmo evoluído tenha reduzido os FLOPs significativamente, seu próprio tempo de execução para determinar a ordem foi alto. Em redes de tensores "grandes", o tempo de execução do algoritmo excedeu limites razoáveis, destacando o trade-off entre a qualidade da ordem de contração e o tempo necessário para computá-la.

Significância e Alegações
Os autores afirmam explicitamente que este trabalho não é uma "história de sucesso" alegando uma descoberta algorítmica revolucionária. Em vez disso, o artigo serve como um estudo de caso para analisar os fatores que contribuem para o sucesso ou fracasso da engenharia de algoritmos baseada em LLM.

• Necessidade de Humano no Ciclo (Human-in-the-Loop): O estudo enfatiza que, embora os LLMs possam gerar código, o cientista humano permanece responsável pela tomada de intenção (intentmaking — definir o problema, selecionar métricas e escolher dados de teste) e pela tomada de sentido (sensemaking — interpretar, validar e compreender os resultados). O design do sistema de avaliação e a seleção do LLM são decisões de design críticas que influenciam fortemente os resultados.
• Mudança nos Objetos de Engenharia: O artigo argumenta que, no desenvolvimento de software científico assistido por IA, o objeto de engenharia estende-se além do código executável para incluir "artefatos semi-executáveis", tais como prompts, fluxos de trabalho, métricas de avaliação e rotinas organizacionais.
• Limitações: Os autores reconhecem limitações, incluindo o uso de um único framework (OpenEvolve), a dependência do conhecimento interno do LLM sem recuperação externa, e o uso de modelos de pesos abertos em vez de modelos comerciais de fronteira. Eles observam que a rápida evolução do campo pode tornar configurações experimentais específicas obsoletas rapidamente.

Em conclusão, o artigo postula que agentes evolutivos baseados em LLM são ferramentas promissoras para escalar a busca algorítmica, mas seu deployment eficaz requer supervisão humana rigorosa no design do espaço de busca e na validação dos artefatos resultantes contra restrições específicas do domínio.