Resumo Técnico: Formalize, Não Otimize: A Armadilha Heurística em Solucionadores Combinatórios Gerados por LLMs

Declaração do Problema

Os Modelos de Linguagem de Grande Escala (LLMs) têm dificuldade em resolver problemas combinatórios complexos por meio de raciocínio autoregressivo direto devido ao "gargalo de raciocínio" inerente à navegação em grandes espaços de busca e à manutenção da consistência global ao longo de restrições de longo horizonte. Embora abordagens neuro-simbólicas recentes tentem mitigar isso fazendo com que LLMs sintetizem solucionadores executáveis, duas questões críticas de design permanecem sem resolução:

1. Representação: Como o LLM deve representar o solucionador? Uma abordagem algorítmica nativa (Python) é superior à modelagem declarativa (MiniZinc) ou à integração com API de solucionador (Python + OR-Tools)?
2. Otimização: O LLM deve ser instruído a otimizar ativamente o processo de busca (por exemplo, via heurísticas, poda ou limites), ou deve estritamente formalizar o problema para um backend verificado?

Trabalhos anteriores frequentemente avaliam essas configurações de forma isolada ou em agregado ao nível do problema, falhando em decompor os resultados ao nível da instância em correção, validade do esquema e fidelidade. Além disso, o impacto do direcionamento focado em eficiência na confiabilidade dos solucionadores gerados não foi auditado sistematicamente.

Metodologia

Os autores introduzem o CP-SynC-XL, uma extensão do conjunto de dados CP-SynC que inclui 100 Problemas de Satisfação de Restrições (CSPs) e Problemas de Otimização de Restrições (COPs) heterogêneos, totalizando 4.577 instâncias parametrizadas. O estudo avalia três LLMs de ponta (GPT-5.3-CODEX, GEMINI 3.1 PRO, DEEPSEEK-V3.2) em três paradigmas de construção de solucionadores:

1. Busca Algorítmica Nativa (Python): O LLM gera um algoritmo Python autônomo usando apenas a biblioteca padrão, projetando o procedimento completo de busca (por exemplo, branch-and-bound, DP).
2. Modelagem de Restrições via API Python (Python + OR-Tools): O LLM codifica variáveis, restrições e objetivos usando a API Python CP-SAT do OR-Tools, delegando a busca ao solucionador.
3. Modelagem Declarativa de Restrições (MiniZinc + OR-Tools): O LLM gera um modelo MiniZinc, que é então compilado e resolvido pelo mesmo backend CP-SAT do OR-Tools.

O estudo emprega um design fatorial controlado comparando um prompt de base (pedindo apenas correção) contra um prompt heurístico (solicitando explicitamente design focado em eficiência, como limites mais apertados, poda ou anotações de busca).

O pipeline de avaliação inclui:

• Protocolo de Refinamento: Um loop iterativo de quatro rodadas onde execuções falhas (falhas, timeouts, erros de formato) são realimentadas ao LLM.
• Métricas:
  • Fornecido: Fração de instâncias retornando uma saída conforme o esquema.
  • Correto: Fração de saídas fornecidas que passam no verificador de referência.
  • Fidelidade: A razão de Correto/Fornecido (a parcela de soluções retornadas que são realmente válidas).
• Auditoria em Nível de Código: Uma análise pareada de solucionadores de base versus heurísticos para identificar modos de falha específicos e padrões de código.

Principais Contribuições

1. O Benchmark CP-SynC-XL

Os autores introduzem um benchmark de grande escala (4.577 instâncias) projetado para avaliar solucionadores sintetizados por LLMs ao nível da instância, separando saídas fornecidas da correção verificada para medir a fidelidade condicional.

2. Divergência Representacional

O estudo revela uma divergência significativa no desempenho do solucionador com base na superfície de modelagem, mesmo quando o backend do solucionador subjacente (OR-Tools CP-SAT) é idêntico:

• Python + OR-Tools alcança a maior correção absoluta em todos os LLMs.
• MiniZinc + OR-Tools exibe menor cobertura absoluta (mais timeouts de "sem solução") apesar de ter o mesmo backend, sugerindo um gargalo na fluência do LLM com a superfície declarativa em vez da capacidade do solucionador.
• Python Nativo tem a maior taxa de "falhas silenciosas"—retornando soluções válidas de esquema que falham na verificação—indicando que os LLMs lutam para projetar algoritmos de busca completos e sólidos do zero.

3. A Armadilha Heurística

O artigo identifica uma "armadilha heurística" onde instruir LLMs a otimizar a busca produz resultados não confiáveis:

• Ganhos Marginais, Alto Risco: Prompts heurísticos produzem apenas pequenos aumentos medianos de velocidade (1,03–1,12×), mas induzem um efeito fortemente bimodal. Enquanto algumas instâncias aceleram, muitas outras desaceleram, e a correção cai drasticamente em uma cauda longa de problemas.
• Seis Modos de Falha: Uma auditoria em nível de código identifica seis modos de falha específicos do paradigma desencadeados por prompts heurísticos:
  • Limites Não Verificados (Python + OR-Tools): LLMs injetam limites "apertados" que não são teoremas, causando inviabilidade.
  • Propagação Enfraquecida (Python + OR-Tools): Reescritas semanticamente equivalentes (por exemplo, Big-M) que paralisam o motor de propagação do solucionador.
  • Sementeamento Rígido (Python + OR-Tools): Converter candidatos heurísticos em restrições rígidas, removendo regiões viáveis.
  • Perda de Completude (Python): Substituir busca completa por busca local incompleta ou limites de iteração.
  • Colapso COP→SAT (MiniZinc): Assumir incorretamente um valor ótimo e converter otimização em satisfação.
  • Mecanismo Redundante (MiniZinc): Adicionar restrições auxiliares excessivas que sobrecarregam o processo de achatamento do solucionador.

Resultados

• Classificação de Correção: Python + OR-Tools > Python ≳ MiniZinc + OR-Tools. Delegar a busca a um backend verificado (CP-SAT) supera significativamente o design algorítmico nativo.
• Classificação de Fidelidade: MiniZinc + OR-Tools > Python + OR-Tools > Python. Quando uma solução é fornecida, os modelos MiniZinc têm maior probabilidade de estar corretos (maior fidelidade condicional) porque o sistema de tipos da linguagem e as verificações de bem-formação filtram muitos erros de codificação antes da execução do solucionador. Python nativo é o menos fiel, frequentemente retornando soluções confiantes, mas incorretas.
• Impacto Heurístico: Em LLMs mais fortes (GPT-5.3-CODEX, GEMINI 3.1 PRO), prompts heurísticos produzem ganhos marginais e inconsistentes (±3,6 pontos percentuais). Em LLMs mais fracos (DEEPSEEK-V3.2), prompts heurísticos causam degradação significativa (por exemplo, -7,4 pp de correção em Python + OR-Tools).
• Análise de Falha: O modo de falha dominante da base é UNSAT (o solucionador retorna uma solução que o verificador de referência rejeita), causado principalmente por traduções incorretas de linguagem natural para linguagem formal (por exemplo, omitir restrições, interpretar mal esquemas de saída). Prompts heurísticos exacerbam isso ao introduzir limites não verificados e superconstranger o modelo.

Significado e Princípios de Design

O artigo argumenta que o principal gargalo para solucionadores combinatórios gerados por LLMs é a fluência na superfície de modelagem, não a capacidade do solucionador subjacente. As descobertas apoiam um princípio de design conservador:

"Formalize, Não Otimize."

Os LLMs devem ser usados principalmente para formalizar variáveis, restrições e objetivos para solucionadores verificados. Tentativas de fazer com que LLMs gerem otimizações de busca (heurísticas, limites, estratégias de poda) devem ser tratadas com ceticismo. O artigo conclui que qualquer otimização de busca autorizada por LLM deve ser validada independentemente antes do uso, pois a "armadilha heurística" frequentemente introduz limites não verificados ou substituições algorítmicas que reduzem tanto a correção quanto a fidelidade. A estratégia mais confiável é manter o LLM próximo à interface de formalização e confiar na maquinaria nativa do solucionador para a busca.