Resumo Técnico: Além da Busca no Tempo de Inferência

1. Declaração do Problema

Os Modelos de Linguagem de Grande Escala (LLMs) atuais tipicamente tratam a otimização combinatória como um procedimento no tempo de inferência, resolvendo cada instância de problema separadamente por meio de amostragem, busca ou prompts repetidos. Esse paradigma incorre em um "custo marginal" de raciocínio para cada nova consulta. Os autores investigam se o Aprendizado por Reforço (RL) pode deslocar esse custo de raciocínio para os pesos do modelo, permitindo a síntese de um resolvedor reutilizável para uma família inteira de problemas, em vez de gerar soluções por instância.

O estudo foca na Seleção de Dependências Sinérgicas (SDS), uma variante controlada e fortemente NP-difícil do Problema da Mochila Quadrática. A SDS é projetada como um cenário de otimização "enganoso" onde:

• Sinais locais contradizem a otimalidade global: Termos de interação quadrática dominam os pesos lineares, fazendo com que heurísticas gananciosas falhem.
• Restrições estritas de viabilidade: As soluções devem satisfazer limites de cardinalidade, precedência, exclusão mútua e limites de grupo.
• Recuperação de templates vs. operacionalização: Embora modelos base frequentemente consigam recuperar a sintaxe de resolvedores apropriados (por exemplo, Recozimento Simulado), eles frequentemente falham em implementar a lógica executável corretamente (por exemplo, aplicando incorretamente regras de aceitação).

O artigo aborda três perguntas de pesquisa centrais:

1. Parede de Competência: A amostragem extensiva no tempo de teste (Best-of-N) pode recuperar o desempenho de uma política treinada com RL em paisagens enganosas, ou o modelo base atinge um teto?
2. Reparo Semântico: Quando o RL tem sucesso, ele apenas afina a frequência de soluções corretas, ou repara a lógica algorítmica executável que a amostragem ingênua não consegue recuperar?
3. Síntese de Resolvedor Amortizado: A otimização no tempo de treinamento pode destilar o raciocínio em um programa leve e reutilizável que supera a busca repetida por instância?

2. Metodologia

Os autores propõem o Hero, uma política ajustada usando Otimização de Política Relativa em Grupo (GRPO) no modelo Qwen2.5-Coder-14B-Instruct. A abordagem é intencionalmente minimalista, removendo estabilizadores comuns (por exemplo, penalidades KL, ancoragem de oráculo) para isolar os efeitos de uma receita focada primeiro na viabilidade.

Componentes Chave:

• Prompt de Sistema com Suporte: O prompt impõe um loop de raciocínio "Desconstruir-Hipotetizar-Criticar". Ele alerta explicitamente o modelo contra heurísticas gananciosas e incentiva o design de estratégias de busca que equilibrem exploração e exploração.
• Design de Recompensa Hierárquica: Uma recompensa composta $r(o)$ prioriza a conformidade estrutural sobre a otimalidade bruta:
  • Formato e Execução ($R_{exec}$): Garante sintaxe Python válida, conformidade com o esquema e estrutura de teoria dos grafos. Crucialmente, inclui uma penalidade anti-classificação preguiçosa para suprimir a tendência do modelo pré-treinado de usar heurísticas lineares gananciosas que ignoram interações quadráticas.
  • Otimalidade Portada por Viabilidade ($R_{nom}$): O sinal primário de otimização é estritamente portado. Se uma solução violar qualquer restrição rígida (cardinalidade, precedência, etc.), a recompensa é zero, independentemente da pontuação do objetivo. Isso força a política a priorizar a satisfação de restrições antes de otimizar o objetivo.
• Regime de Treinamento: O modelo é treinado por 90 passos globais em 12 GPUs NVIDIA GH200, observando apenas ~4,5% de uma época completa em nível de prompt, mas gerando 23.040 traços de raciocínio.

3. Contribuições Principais

As contribuições do artigo são empíricas e mecânicas, em vez de algorítmicas:

1. Identificação de uma Parede de Competência: Sob prompts idênticos, a amostragem Best-of-64 do modelo base satura em uma lacuna de 28,7% em relação ao Resolvedor Virtual Melhor (VBS). Apesar de recuperar templates de resolvedores superficialmente apropriados (por exemplo, 21,9% dos códigos base únicos se assemelham a Recozimento Simulado), o modelo base falha em operacionalizá-los corretamente.
2. Demonstração de Reparo Semântico: A política treinada com RL (Hero) converge para um template de Recozimento Simulado consciente de restrições em 99,8% das saídas viáveis. Ela repara o "Bug do Melhor Global" prevalente nas amostras do modelo base, onde a lógica de aceitação compara incorretamente vizinhos ao melhor global em execução em vez do estado atual. Essa correção permite o comportamento verdadeiro de recozimento.
3. Validação da Síntese de Resolvedor Amortizado:
   • Desempenho: Hero alcança uma taxa de aprovação de 97,8% e uma lacuna de 5,0% em relação ao VBS, superando significativamente o modelo base e heurísticas clássicas como Busca Local (lacuna de 10,0%).
   • Eficiência: Hero é 91× mais barato em custo de execução/busca pós-geração em comparação com o custo cumulativo da avaliação Best-of-64.
   • Reutilizabilidade: Uma avaliação de "compilar uma vez" mostra que um único resolvedor congelado gerado por semente permanece altamente competitivo (taxa de aprovação de 97,87%, lacuna de 4,34%) quando reutilizado inalterado em todo o conjunto de testes, provando que o modelo sintetiza um artefato reutilizável em vez de um gerador por instância.

4. Resultados e Ablações

• Desempenho Principal: Hero alcança uma taxa de aprovação de 97,8% e uma lacuna de 5,0% em relação ao VBS. Supera a linha de base ShinkaEvolve atualizada (que usa modelos proprietários fortes no momento da implantação) e aproxima-se do desempenho do CP-SAT (lacuna de 1,0%) enquanto é 6,3× mais rápido na execução.
• Estudos de Ablação:
  • Suporte Estrutural: Remover a recompensa estrutural (classificação anti-preguiçosa e verificações de estrutura de grafo) faz o desempenho colapsar para uma lacuna de 34,7%, pois o modelo reverte para heurísticas gananciosas frágeis.
  • Porta de Viabilidade: Substituir a porta de viabilidade rígida por uma penalidade suave degrada significativamente o desempenho (57,4% de taxa de aprovação vs. 97,8%), confirmando que a porta rígida é necessária para evitar o colapso de modo em soluções inválidas.
  • Oráculo/Diversidade: Adicionar ancoragem de oráculo ou penalidades de diversidade degrada o desempenho, sugerindo que feedback esparsos, focados primeiro na viabilidade, são mais eficazes do que a modelagem densa de resultados neste domínio.
• Generalização:
  • Sem Esquecimento Catastrófico: O modelo mantém capacidades gerais de codificação (HumanEval Pass@1: 80,9% vs. Base 82,3%).
  • Cross-Domínio: Aplicar a mesma receita ao Problema de Agendamento de Job Shop (JSSP) produz resultados positivos (99,3% de taxa de aprovação, lacuna de 6,12%), embora os autores observem que isso é evidência mais estreita de transferência em vez de prova de robustidade agnóstica ao domínio.

5. Significado e Alegações

O artigo afirma demonstrar que o RL pode mover um LLM de código de um regime de busca por instância para síntese de resolvedor reutilizável. O significado reside na descoberta de que o RL atua não apenas como um "afinador de distribuição" (melhorando a eficiência de encontrar soluções existentes), mas como um compilador funcional que repara a lógica executável (por exemplo, corrigindo a regra de aceitação de Metropolis) que a amostragem ingênua não pode recuperar de forma confiável.

Os autores enfatizam que esse sucesso depende de um suporte disciplinado, focado primeiro na viabilidade, e não de uma receita universal. O método depende de escolhas de design específicas, como a porta de viabilidade rígida e penalidades estruturais, e é sensível à normalização de recompensas. O trabalho sugere que, para paisagens de otimização complexas e enganosas, o "raciocínio" necessário para construir um resolvedor pode ser destilado nos pesos do modelo, criando um artefato implantável que é significativamente mais eficiente do que a busca repetida no tempo de inferência.