Phase 15 - Lesson 03

AlphaEvolve — Agentes de Programação Evolutiva

Combine um modelo de programação de fronteira com um loop evolutivo e um avaliador verificável por máquina. Deixe o loop rodar por tempo suficiente. Ele descobre um procedimento de multiplicação de matrizes complexas 4x4 que utiliza 48 multiplicações escalares — a primeira melhoria em relação a Strassen em 56 anos. Ele também encontra uma heurística de agendamento do Borg em escala do Google que recupera ~0,7% do poder computacional do cluster em produção. A arquitetura é entediante de propósito. As vitórias vêm do rigor do avaliador.

Tipo: Aprender Linguagens: Python (stdlib, brinquedo de loop evolutivo) Pré-requisitos: Fase 15 · 01 (enquadramento de longo horizonte), Fase 15 · 02 (raciocínio autodidata) Tempo: ~60 minutos

O Problema

Modelos de linguagem de grande porte podem escrever código. Algoritmos evolutivos podem realizar buscas sobre o código. Ambos foram tentados separadamente por décadas; ambos atingiram limites. O limite dos LLMs é a confabulação: o modelo escreve um código plausível que não faz o que afirma fazer. O limite evolutivo é o custo de busca: mutações aleatórias na sintaxe raramente produzem programas compiláveis, muito menos melhores.

O AlphaEvolve (Novikov et al., DeepMind, arXiv:2506.13131, junho de 2025) combina os dois. O LLM propõe edições direcionadas a um banco de dados de programas; um avaliador automático pontua cada variante; variantes com pontuações altas tornam-se pais para as gerações futuras. O LLM lida com a etapa custosa de escrever código plausível; o avaliador captura as confabulações. O loop roda por horas ou semanas.

Resultados relatados: multiplicação de matrizes complexas 4x4 com 48 multiplicações escalares (o limite de Strassen em 1969 era 49), uma heurística de agendamento do Borg em produção no Google, uma aceleração de 32,5% no kernel do FlashAttention e melhorias no rendimento de treinamento do Gemini.

A arquitetura funciona porque o avaliador é verificável por máquina. Ela não funciona onde o avaliador não é. Essa assimetria é a lição.

O Conceito

O loop

1. Comece a partir de um programa semente P_0 que seja correto, mas abaixo do ideal.
2. Mantenha um banco de dados de programas variantes, cada um pontuado pelo avaliador.
3. Selecione um ou mais pais do banco de dados (estilo MAP-elites ou baseado em ilhas).
4. Forneça um prompt ao LLM (Gemini Flash para muitos candidatos, Gemini Pro para os difíceis) para produzir uma variante modificada do pai.
5. Compile, execute e avalie a variante no avaliador retido (held-out).
6. Insira no banco de dados indexado por sua pontuação e vetor de características.
7. Repita.

Dois detalhes importam. Primeiro, o prompt do LLM contém mais do que apenas o programa pai — normalmente várias das melhores variantes do banco de dados, além da assinatura do avaliador e uma breve descrição da tarefa. O trabalho do modelo é propor uma mudança direcionada que possa melhorar a pontuação. Segundo, o banco de dados é estruturado (grade MAP-elites, baseado em ilhas) para que o loop explore a diversidade, não apenas o líder atual.

O que torna o avaliador não negociável

As vitórias do AlphaEvolve vêm todas de domínios onde o avaliador é rápido, determinístico e difícil de burlar:

• Algoritmo de multiplicação de matrizes: um teste unitário que multiplica matrizes e verifica a igualdade bit a bit.
• Heurística de agendamento do Borg: um simulador de nível de produção que reproduz a carga histórica do cluster e mede a computação desperdiçada.
• Kernel do FlashAttention: um teste de corretude mais um benchmark de tempo de execução real em hardware físico.
• Rendimento de treinamento do Gemini: medido em segundos de GPU por etapa.

Em cada caso, o avaliador captura a classe de erros de LLM que, de outra forma, dominaria: alegações de corretude confabuladas, alegações de desempenho que desaparecem no hardware real e falhas em casos de borda. Remova o avaliador e o loop otimizará para código bonito.

Trapaça de recompensa (reward hacking) é o outro lado dessa afirmação

A evolução otimiza para qualquer coisa que o avaliador meça. Se o avaliador for imperfeito, o loop encontrará a imperfeição. Em um domínio não verificado, o loop otimizaria para a característica superficial, não para o comportamento pretendido. A DeepMind sinaliza isso explicitamente no artigo: os sucessos do AlphaEvolve se transferem apenas para domínios onde o rigor do avaliador corresponde à ambição da busca.

Exemplos concretos de trapaça de recompensa (reward hacking) em loops de busca de código em 2025-2026:

• Metas de otimização que recompensavam o "tempo de conclusão" acabaram recompensando o envio de soluções vazias.
• Pontuações de benchmark que recompensavam a corretude sob teste recompensavam a memorização de testes e o sobreajuste (overfitting).
• Um proxy de "qualidade de código" recompensou a remoção de comentários e a renomeação de variáveis, sem qualquer alteração semântica.

A solução no AlphaEvolve: disponibilizar um avaliador retido (held-out) que o LLM nunca viu, com entradas geradas em tempo de avaliação. Mesmo assim, a DeepMind recomenda uma revisão rigorosa de qualquer implantação proposta.

Por que LLM + busca supera qualquer um dos dois isoladamente

O LLM pode produzir modificações compiláveis e semanticamente plausíveis. Um algoritmo genético (GA) de mutação aleatória em um arquivo Python de 2000 linhas quase sempre produz erros de sintaxe. O LLM também concentra a busca em vizinhanças plausíveis (alterar uma função, não bytes aleatórios), o que reduz drasticamente as chamadas de avaliação desperdiçadas.

O avaliador, por sua vez, captura as confabulações do LLM. Os LLMs afirmarão com confiança que uma função "é O(n log n) no limite" quando ela na verdade é O(n^2); um benchmark de tempo de execução real resolve a questão definitivamente.

Onde o AlphaEvolve se encaixa na pilha de fronteira

Todos os quatro são variações da mesma receita: gerador mais avaliador, loop. As diferenças estão no que o avaliador avalia e no quão rigoroso ele é.

Use-o

O arquivo code/main.py implementa um loop mínimo semelhante ao AlphaEvolve sobre um problema de brinquedo de regressão simbólica. O "LLM" é um proxy da stdlib que propõe pequenas mutações sintáticas para um programa que calcula uma função-alvo. O "avaliador" mede o erro quadrático médio em pontos de teste retidos (held-out).

Observe:

• Como a melhor pontuação melhora ao longo das gerações.
• Como uma grade MAP-elites mantém soluções diversas vivas para que o loop não convirja para um mínimo local.
• Como a remoção do teste retido (avaliador apenas de treino) permite que o loop sofra um sobreajuste (overfit) espetacular.

Envie-o

O arquivo outputs/skill-evaluator-rigor-audit.md é a pré-condição para considerar um loop no estilo AlphaEvolve em um novo domínio: o seu avaliador realmente captura as falhas com as quais você se importa?

Exercícios

1. Execute code/main.py. Observe a trajetória da melhor pontuação. Desative o avaliador retido (flag --no-holdout) e execute novamente. Quantifique o sobreajuste (overfitting).

2. Leia a Seção 3 do artigo do AlphaEvolve sobre a grade MAP-elites. Projete um descritor de vetor de características para um novo problema (por exemplo, passagens de otimização de compilador) que manteria a busca diversa.

3. O resultado de 48 multiplicações 4x4 melhorou o limite de 49 multiplicações de Strassen após 56 anos. Leia o Apêndice F do artigo e explique em três frases por que o avaliador para esse problema é particularmente fácil de acertar e por que a maioria dos domínios não é como ele.

4. Proponha um domínio no qual o AlphaEvolve falharia. Identifique exatamente onde o avaliador falha e por quê.

5. Para um domínio que você conhece, escreva a assinatura do avaliador que você usaria. Inclua (a) condições de corretude, (b) métrica de desempenho, (c) regra de geração de entrada retida, (d) pelo menos uma verificação contra trapaça de recompensa (anti-reward-hacking).

Termos-Chave

Leituras Adicionais

• Novikov et al. (2025). AlphaEvolve: A coding agent for scientific and algorithmic discovery — o artigo completo.
• DeepMind blog on AlphaEvolve — artigo do fornecedor com resultados.
• AlphaEvolve results repository — repositório de resultados de algoritmos descobertos, incluindo o matmul 4x4 de 48-mul.
• Romera-Paredes et al. (2023). Mathematical discoveries from program search with LLMs (FunSearch) — o sistema predecessor.
• Anthropic — Responsible Scaling Policy v3.0 (Feb 2026) — enquadra a autonomia limitada por avaliadores como uma direção de pesquisa fundamental.