Resumo Técnico: HeuriGym: Um Benchmark Agêntico para Heurísticas Criadas por LLMs em Otimização Combinatória

Declaração do Problema

As metodologias de avaliação atuais para Grandes Modelos de Linguagem (LLMs) enfrentam uma crise dupla na avaliação de suas capacidades de resolução de problemas. Primeiro, os benchmarks de objetivos baseados em verdades fundamentais (ex: AIME, HumanEval) dependem de questões de resposta fechada que são suscetíveis à contaminação de dados e saturação de desempenho, falhando em refletir cenários do mundo real onde as soluções não são únicas ou predefinidas. Segundo, as avaliações subjetivas baseadas em preferência de juiz (ex: Chatbot Arena) introduzem alta variância e frequentemente priorizam fatores superficiais em vez da qualidade do raciocínio substantivo.

Existe uma lacuna crítica em avaliar se os LLMs podem ir além do reconhecimento de padrões para exibir engenhosidade genuína de resolução de problemas em fluxos de trabalho de engenharia complexos e iterativos. Especificamente, os benchmarks existentes têm dificuldade em avaliar a capacidade de projetar heurísticas inovadoras para problemas de otimização combinatória (CO), que exigem a navegação por vastos espaços de solução, a adesão a restrições estritas e a adaptação de estratégias com base no feedback de tempo de execução.

Metodologia

Os autores introduzem o HeuriGym, um framework agêntico projetado para avaliar LLMs em sua capacidade de gerar, executar e refinar iterativamente algoritmos heurísticos para problemas de otimização combinatória.

Visão Geral do Framework

O HeuriGym opera através de um loop agêntico interativo consistindo de três estágios:

1. Descrição do Problema: O LLM recebe um prompt estruturado contendo um contexto em linguagem natural, uma formalização matemática do objetivo e das restrições, e formatos específicos de arquivos de entrada/saída. Diferente de trabalhos anteriores que fornecem implementações parciais ou scaffolds, o HeuriGym fornece apenas a interface da função, exigindo que o LLM projete estruturas de dados e algoritmos do zero.
2. Execução e Verificação: O código gerado é compilado ou interpretado dentro de um ambiente isolado (sandbox). Um verificador de domínio específico checa a satisfação de restrições (ex: preservação de dependências), enquanto um avaliador calcula o custo com base no objetivo de otimização.
3. Refinamento Iterativo: Logs de execução, resultados de verificação e métricas de desempenho de um pequeno conjunto de demonstração são anexados ao prompt. Este loop de feedback permite que o LLM depure erros, corrija violações de restrições e refine suas estratégias heurísticas ao longo de múltiplas iterações.

Construção do Benchmark

O benchmark compreende nove problemas de otimização combinatória abrangendo sistemas de computação, logística e biologia computacional (ex: escalonamento de operadores, mapeamento tecnológico, pareamento de tripulação de companhias aéreas, design de sequência de proteínas).

• Critérios de Seleção: Os problemas foram selecionados para terem exposição limitada na literatura (menos de 1.000 citações para o artigo mais citado) para minimizar riscos de memorização. Eles apresentam especificações de linguagem natural bem definidas, vastos espaços de solução e instâncias de dados escaláveis.
• Dataset: Cada problema inclui um pequeno conjunto de demonstração (~5 instâncias) para few-shot prompting e refinamento iterativo, e um conjunto de avaliação maior (dezenas de instâncias) para testes finais.

Métricas de Avaliação

Para abordar as limitações de métricas padrão como PASS@k, os autores propõem:

• SOLVEs@i: Rastreia a probabilidade de resolver um problema com restrições dentro de $i$ iterações, medindo o sucesso ao passar por três estágios: Execução (Estágio I), Geração de Solução (Estágio II) e Verificação (Estágio III).
• Índice de Qualidade-Rendimento (QYI): Uma métrica unificada definida como a média harmônica de Qualidade (o quão próxima a solução está de uma linha de base especialista) e Rendimento (a proporção de instâncias que passam na verificação).
  • $Qualidade = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$, onde $c_n$ é o custo do LLM e $c^*_n$ é o custo do especialista.
  • $Rendimento = \frac{\hat{N}}{N}$, onde $\hat{N}$ é o número de soluções verificadas.
  • $QYI = \frac{(1 + \beta^2) \cdot Qualidade \cdot Rendimento}{(\beta^2 \cdot Qualidade) + Rendimento}$ (com $\beta=1$).

Principais Resultados

Os autores avaliaram nove modelos de última geração (incluindo GPT-o4-mini-high, Gemini-2.5-Pro, DeepSeek-R1 e variantes LLaMA) no benchmark HeuriGym.

• Lacuna de Desempenho: Mesmo modelos de alto nível lutam para atingir o desempenho de nível especialista. O melhor modelo, Gemini-2.5-Pro, alcançou um score QYI de aproximadamente 0,62, indicando que suas soluções são, em média, apenas 60% tão eficazes quanto heurísticas criadas por especialistas. Outros modelos pontuaram significativamente abaixo (ex: LLaMA-3.3 e LLaMA-4-Maverick abaixo de 0,30).
• Melhoria Iterativa: O aumento do número de iterações melhora significativamente o desempenho. Por exemplo, a taxa de sucesso do GPT-o4-mini-high (SOLVEIII) subiu de 53,2% na iteração 1 para 74,8% na iteração 10, destacando a importância do refinamento iterativo.
• Modos de Falha: A análise revelou tipos comuns de falhas, incluindo APIs alucinadas, lógica algorítmica incorreta, incompreensão de restrições e timeouts.
• Frameworks Evolutivos: Frameworks de busca evolutiva padrão (ex: ReEvo, HSEvo) tiveram desempenho pobre comparado ao modelo de base, frequentemente falhando em incorporar o feedback de execução de forma eficaz e quebrando o contexto entre as iterações.

Significância e Contribuições

O artigo reivindica três contribuições primárias:

1. Um Suite de Benchmark de Código Aberto: Uma coleção de nove problemas de otimização combinatória realistas e de alto impacto que avaliam raciocínio de múltiplos passos e capacidades de design algorítmico, indo além de padrões memorizados.
2. Um Framework Agêntico de Ponta a Ponta: Um sistema que suporta geração de solução, verificação automatizada e refinamento iterativo, servindo como um banco de testes para técnicas avançadas de prompting e estratégias evolutivas.
3. Insights Empíricos: Um estudo abrangente que revela que os LLMs atuais, apesar de suas capacidades de raciocínio, enfrentam limitações persistentes em uso de ferramentas, planejamento e raciocínio adaptativo quando aplicados a problemas científicos e de engenharia complexos do mundo real.

Os autores posicionam o HeuriGym como um passo necessário para guiar o desenvolvimento de LLMs em direção a uma resolução de problemas mais eficaz e realista em domínios onde soluções ótimas são tratáveis apenas para instâncias pequenas e onde a descoberta de heurísticas é essencial. O benchmark visa expor a lacuna entre as capacidades atuais dos modelos e as demandas de fluxos de trabalho de engenharia prática, incentivando o desenvolvimento de modelos capazes de verdadeira invenção de heurísticas em vez de mero reconhecimento de padrões.