Resumo Técnico: Busca Evolutiva Guiada por LLM para Reformulação de Modelos de Restrição

Definição do Problema

Problemas combinatórios são onipresentes em aplicações industriais, frequentemente modelados usando Programação de Restrições (CP). Embora os Grandes Modelos de Linguagem (LLMs) tenham demonstrado a capacidade de gerar modelos de restrição declarativos corretos a partir de linguagem natural, a correção por si só não garante eficiência. Um modelo que é semanticamente correto pode ainda ser computacionalmente caro de resolver devido a escolhas de modelagem subótimas (ex: pontos de vista de variáveis, formulações de restrições ou codificações). Reformular esses modelos manualmente para melhorar o desempenho do solver é um gargalo crítico. As abordagens de automação existentes frequentemente dependem de transformações baseadas em regras ou de anexar "streamliners" (restrições adicionais) a uma estrutura de modelo fixa, em vez de realizar reformulações holísticas que alteram o ponto de vista ou as codificações das variáveis.

Metodologia

Os autores propõem um framework de busca evolutiva guiada por LLM para a reformulação de modelos de restrição orientada ao desempenho. Inspirado no Design Automático de Heurísticas (AHD), o sistema gera, avalia e seleciona iterativamente reformulações de modelos.

Fluxo de Trabalho Central

1. Inicialização: Um modelo de linha de base ($B$) é estabelecido, e seu desempenho de tempo de execução é medido em um conjunto de treinamento ($D_{tr}$).
2. Loop Iterativo: Para $T$ iterações:
   • Seleção de Contexto: Uma estratégia de busca ($\sigma$) seleciona um subconjunto de tentativas anteriores (racional, modelo e feedback) para formar o contexto do prompt ($R_t$).
   • Geração: O LLM recebe um prompt contendo a descrição da tarefa, o modelo de linha de base, o histórico de tempo de execução e o contexto selecionado. Ele produz um racional ($\rho_t$) e um modelo candidato ($m_t$).
   • Avaliação: O candidato é executado em $D_{tr}$. O avaliador verifica a validade da solução (garantindo que a resposta do candidato coincida com a resposta da linha de base para a mesma instância) e mede o tempo de execução total.
   • Atualização de Histórico: A tentativa é registrada no histórico $H_t$.
3. Seleção Final: Após o término da busca, todos os modelos incumbentes de solução válida são avaliados em um conjunto de validação separado ($D_{val}$). O modelo com o menor tempo de execução total em $D_{val}$ é selecionado como a saída final. Esta etapa é crucial para evitar o overfitting aos instâncias de treinamento.

Estratégias de Busca

O artigo compara dez estratégias para selecionar o contexto $R_t$ fornecido ao LLM:

• Baselines: Sampling (sem contexto), Full-history (histórico completo), Last-k (recência) e Top-k (qualidade/mais rápido).
• Híbrida: Combina recência e qualidade.
• Evolução de Heurísticas (EoH): Mantém uma população de modelos e utiliza operadores específicos (ex: "abordagem distinta", "combinação compatível") para guiar a geração, com e sem feedback de desempenho.
• Retenção de Perfil Diverso (PDR): Uma estratégia novel introduzida neste trabalho. A PDR busca explicitamente a diversidade comportamental. Ela representa cada modelo como um vetor de tempos de execução normalizados através das instâncias de treinamento. Utiliza a Relevância Marginal Máxima (MMR) para selecionar um conjunto de tentativas que sejam rápidas (alta qualidade) e comportamentalmente distintas (baixa similaridade nos perfis de tempo de execução) entre si.

Configuração Experimental

• Benchmarks: Oito problemas de satisfação do CSPLib (ex: Atribuição de Tripulação, Sequenciamento de Carros, Matrizes de Cobertura).
• Modelo: DeepSeek V4 Flash (contexto de 1M de tokens).
• Solver: OR-Tools CP-SAT via CPMpy.
• Métricas: Média Geométrica (GM) de acelerações (speedups) em instâncias de teste retidas ($D_{test}$), usando PAR2 (tempo de execução médio penalizado) para timeouts.

Principais Contribuições

1. Framework Evolutivo: Uma adaptação do AHD especificamente para a reformulação de modelo completo de modelos de CP declarativos, permitindo que o LLM altere pontos de vista, variáveis e codificações, não apenas anexe restrições.
2. Retenção de Perfil Diverso (PDR): Uma estratégia de seleção de contexto que aplica MMR a vetores de tempo de execução por instância. Ela retém tentativas que são rápidas, mas exibem comportamentos de resolução distintos, visando diversificar o espaço de busca além de métricas simples de recência ou qualidade.
3. Avaliação Sistemática: Uma comparação abrangente de dez estratégias de busca através de oito problemas, demonstrando que a retenção de contexto diversa (PDR) supera estratégias que retêm apenas o mais recente ou o mais rápido.
4. Seleção Baseada em Validação: A introdução de uma etapa de seleção de modelo final baseada em validação (frequentemente ausente em pipelines AHD) mostra-se consistente em melhorar o desempenho em dados retidos e mitigar o overfitting.

Resultados

• Ganhos de Desempenho: A busca evolutiva produz acelerações substanciais em instâncias de teste retidas. A melhor estratégia (PDR) alcançou uma média geométrica de aceleração de 2,26× em todos os problemas, com instâncias específicas mostrando ganhos de até 250,7× (em Matrizes de Cobertura).
• Diversidade Importa: Estratégias que mantêm um contexto diverso (PDR, EoH com feedback) geralmente superam aquelas que dependem apenas de recência (Last-1) ou qualidade (Top-1). A PDR superou a estratégia de qualidade pura Top-5 por um fator de 1,30×.
• Modelo Completo vs. Streamliners: A abordagem proposta de reformulação de modelo completo superou significativamente uma baseline adaptada que apenas gera streamliners aditivos (StreamLLM-single), que alcançou apenas 1,02× de aceleração.
• Eficiência de Custo: Enquanto o Sampling gerou mais tokens, o Full-history permaneceu custo-efetivo devido ao cache de KV. A PDR entregou a maior aceleração com um custo menor que o Sampling.
• Confiabilidade: Nenhum dos modelos selecionados retornou respostas inválidas ou resultados de insatisfação falsos nas instâncias de teste. A seleção baseada em validação filtrou com sucesso candidatos que sofreram overfitting aos dados de treinamento.

Significância e Alegações

O artigo afirma que a reformulação iterativa guiada por LLMs pode automatizar a descoberta de modelos de restrição de alto desempenho, alcançando acelerações significativas sem intervenção humana. Destaca que a diversidade comportamental no contexto de busca é um fator crítico para o sucesso, superando métricas tradicionais como recência ou velocidade bruta.

Os autores observam modestamente que, embora os resultados sejam promissores, o estudo é limitado a um único LLM, uma única configuração de solver e oito problemas específicos de satisfação. Eles sugerem que trabalhos futuros poderiam explorar problemas de otimização, diferentes solvers e o uso mais explícito de feedback rico do solver (ex: contagens de conflitos, profundidade da árvore de busca) para refinar ainda mais as métricas de diversidade. O trabalho posiciona-se como um passo em direção à automação do "santo graal" da modelagem de restrições, indo além da mera correção para a automação orientada ao desempenho.