Resumo Técnico: Raciocínio Semelhante à Otimização Passo a Passo em LLMs sobre Espaços de Busca em Expansão

1. Declaração do Problema

Embora os Grandes Modelos de Linguagem (LLMs) tenham demonstrado sucesso no raciocínio matemático e de codificação via treinamento de recompensa verificável, eles permanecem frágeis em tarefas de tomada de decisão passo a passo sob restrições. Nesses cenários, um passo localmente plausível pode tornar o restante do problema inviável ou forçar uma conclusão de baixa qualidade. Ao contrário dos cenários padrão de correção de resposta, onde existe uma única resposta correta, muitas tarefas do mundo real (ex: alocação de recursos, escalonamento, roteamento) envolvem muitas soluções viáveis, onde o objetivo é construir uma solução de alto valor sob restrições.

Os métodos de escala atuais enfrentam dois obstáculos:

1. Gerar tarefas diversas que exijam de forma confiável um raciocínio não trivial é difícil.
2. Obter supervisão para passos intermediários é caro, pois requer identificar quais ações parciais levam a resultados ótimos.

O artigo aborda o desafio de treinar LLMs para realizar raciocínio semelhante à otimização sobre espaços de busca em expansão, onde a dificuldade é controlada por um parâmetro de complexidade $\alpha$ sem exigir novas etiquetas humanas.

2. Metodologia: O Framework OPT⋆

Os autores introduzem o OPT⋆ (OPTimization-based Scalable Tasks for Auto-verifiable Reasoning), uma família de tarefas projetadas para treinar e avaliar o raciocínio passo a passo.

2.1 Definição da Tarefa

Uma instância de tarefa OPT⋆ $t$ é um processo de decisão restrito definido por:

• Geração Escalável: As instâncias são geradas por um procedimento $Build_\alpha(\cdot)$ controlado por um parâmetro de complexidade $\alpha$ (ex: número de cidades no TSP, número de itens no Knapsack). Aumentar $\alpha$ expande o espaço de busca $M(t)$, mas não aumenta o custo de anotação.
• Verificação Barata: Cada tarefa expõe duas rotinas de baixo custo:
  • Verificador de Viabilidade ($chkt$): Valida ações parciais (ex: garantir que limites de carga não sejam excedidos).
  • Avaliador de Resultado ($evalt$): Pontua soluções terminais completas (ex: comprimento total do tour).
• Auto-verificabilidade: Tanto $chkt$ quanto $evalt$ são computáveis em tempo polinomial, mesmo que encontrar a solução ótima seja difícil.

2.2 Regimes de Treinamento

O artigo propõe duas abordagens de treinamento complementares baseadas na disponibilidade de solvers:

A. Otimização de Política Online Guiada por Solver (RL Online)

Quando um solver rápido está disponível para computar o melhor valor de conclusão a partir de um estado parcial:

• Mecanismo: O solver atua como um oráculo de valor. Para um dado estado, candidatos a próximos passos são amostrados, e cada um é pontuado pelo melhor valor terminal alcançável sob um orçamento fixo de solver.
• Modelagem de Recompensa (Reward Shaping): A política é atualizada usando recompensas baseadas em ranking (ex: GRPO, GSPO, PPO), onde ações que levam a conclusões de maior valor recebem classificações mais altas.
• Objetivo: Reforçar passos que levam a melhores resultados finais, destilando efetivamente heurísticas de solver para a política.

B. RL Offline Baseado em Busca

Quando solvers estão indisponíveis ou são caros demais para estados parciais:

• Mecanismo: O modelo gera trajetórias candidatas. Um algoritmo de busca (ex: MCTS, Beam Search) explora o espaço, usando $chkt$ para podar caminhos inválidos e $evalt$ para pontuar nós terminais.
• Componentes Chave de Busca:
  1. Poda de Viabilidade: Descartar filhos onde $chkt(s, a) = 0$.
  2. Mesclagem de Duplicatas: Agrupar saídas de texto distintas que mapeiam para a mesma ação estruturada para evitar desperdício de orçamento de busca.
• Treinamento: O modelo é ajustado (SFT) nas melhores trajetórias descobertas pelo processo de busca, aprendendo efetivamente a imitar traços de raciocínio de alto valor.

2.3 Fundamentação Teórica

O artigo estabelece um limite informacional (Teorema A.3) relacionando o sucesso em grandes espaços de busca ao interesse extraído por unidade de orçamento de busca. À medida que a complexidade $\alpha$ aumenta, o número de ótimos efetivos cresce. Para manter uma probabilidade de sucesso fixa, um raciocinador deve aumentar o orçamento de busca ou extrair mais informação por passo. O fator de ramificação efetivo ($b_{eff}$) é introduzido como uma métrica para medir a eficiência da busca; um $b_{eff}$ menor indica que um orçamento de busca coloca mais massa em estados terminais de alto valor.

3. Principais Contribuições

1. Conceitual (OPT⋆): Formalização de uma família de tarefas escaláveis e auto-verificáveis para raciocínio semelhante à otimização. Este framework desacopla a dificuldade do raciocínio do esforço de anotação ao usar parâmetros de complexidade para expandir espaços de busca mantendo a verificação barata.
2. Algorítmica:
   • Desenvolvimento de componentes de busca plug-and-play (verificação de viabilidade e mesclagem de duplicatas) que melhoram significamente a eficiência da busca em configurações offline.
   • Introdução de $\nu$PO (Solver-Guided Policy Optimization), um método que utiliza solvers para fornecer recompensas de nível de passo para RL online, permitindo o treinamento em estados parciais.
3. Empírica:
   • Demonstração de que o treinamento em OPT⋆ melhora o raciocínio passo a passo em tarefas de otimização.
   • Evidência de que o aprendizado por currículo (treinar de um $\alpha_1$ fácil para um $\alpha_4$ difícil) produz melhor generalização do que treinar apenas em tarefas difíceis.
   • Demonstração de que o treinamento de otimização transfere para capacidades de raciocínio espacial (ex: rotação, reflexão, cobertura) e melhora o desempenho em benchmarks matemáticos (AMC, AIME).

4. Resultados Experimentais

Os autores avaliaram o framework em tarefas incluindo Atribuição de Papéis (Role Assignment), MaxSAT, Escalonamento de Máquina Única, TSP, Empacotamento 2D e Problema de Atribuição Quadrática (QAP).

• Eficiência de Busca (RL Offline):
  • Habilitar a poda de viabilidade e a mesclagem de duplicatas reduziu significamente o fator de ramificação efetivo ($b_{eff}$). Por exemplo, no QAP, o $\nu$MCTS alcançou $b_{eff} \approx 24$ com esses componentes, comparado a $b_{eff} \approx 728$ para um baseline de referência de solver que não usa propostas de LLM.
  • Esses componentes foram os principais impulsionadores da eficiência de busca, aumentando o pass@16 de ~13% para ~85% no QAP.
• Melhoria do Modelo:
  • Modelos treinados em tarefas OPT⋆ (Role Assignment, MaxSAT) mostraram melhorias substanciais sobre os modelos base. Por exemplo, o Qwen2.5-3B melhorou o pass@1 em Role Assignment de 32.5% para 44.5% (Nível 1) e de 17.8% para 31.1% (Nível 4).
  • O RL online guiado por solver superou consistentemente os baselines de transferência de domínio (ex: treinar em tarefas de Matemática ou Código não transferiu bem para tarefas de otimização).
• Generalização:
  • O treinamento em tarefas de otimização melhorou o desempenho em tarefas de QA espacial fora da distribuição (OOD) (ex: rotação, simetria, sobreposição) e em benchmarks matemáticos padrão (AMC'23, AIME'24/25).
  • Efeitos de currículo: O treinamento de currículo misto ($\alpha_1 \to \alpha_4$) superou tanto as estratégias de treinamento "apenas fáceis" quanto as "apenas difíceis", particularmente em níveis mais difíceis e tarefas OOD.

5. Significância e Alegações

O artigo afirma que o OPT⋆ fornece um ambiente de teste principiado para estudar o raciocínio passo a passo sob restrições, abordando a lacuna entre o treinamento de recompensa verificável (eficaz para matemática/código) e tarefas de otimização do mundo real.

• Valor Científico: Oferece um ambiente controlado para estudar como espaços de busca em expansão afetam as capacidades de raciocínio, apoiado por uma análise informacional que mostra que o sucesso requer a extração de mais informação por unidade de orçamento conforme a complexidade cresce.
• Valor Prático: Os métodos propostos (componentes de busca plug-and-play e RL guiado por solver) oferecem formas escaláveis de treinar modelos em fluxos de trabalho complexos (escalonamento, roteamento) onde solvers exatos podem não estar disponíveis ou serem lentos demais para chamadas repetidas.
• Escopo Modesto: Os autores observam que, embora os solvers possam verificar ou resolver instâncias específicas, o objetivo é destilar heurísticas reutilizáveis em modelos de uso geral. O trabalho foca em tarefas de otimização sintéticas motivadas por problemas tradicionais, reconhecendo que trabalhos futuros poderiam escalar a geração de tarefas usando priors de LLM para criar cenários ainda mais diversos e complexos.

Em resumo, o artigo demonstra que, ao aproveitar tarefas de otimização auto-verificáveis e estratégias complementares de RL offline/online, os LLMs podem aprender a navegar em espaços de busca em expansão de forma mais eficaz, melhorando tanto seu desempenho de otimização quanto suas habilidades subjacentes de raciocínio espacial e lógico.