Resumo Técnico: GraphPO - Otimização de Política Baseada em Grafos para Modelos de Raciocínio

1. Declaração do Problema

O Aprendizado por Reforço com Recompensas Verificáveis (RLVR) tornou-se o paradigma padrão para aprimorar Grandes Modelos de Raciocínio (LRMs). No entanto, os métodos atuais de RLVR enfrentam duas limitações primárias:

1. Exploração Redundante: A amostragem independente de respostas frequentemente resulta em diferentes trajetórias contendo etapas de raciocínio intermediárias semelhantes. Isso leva ao desperdício de computação e limita a diversidade da exploração.
2. Sinais de Recompensa Esparsos: O RLVR normalmente depende de recompensas de resposta final binárias. Essa esparsidade torna difícil atribuir crédito a etapas de raciocínio intermediárias específicas que contribuem para a resposta final.

Embora métodos baseados em árvores (ex: TreeRL, PROS) abordem parte da redundância ao compartilhar prefixos e fornecer sinais refinados em pontos de ramificação, eles ainda tratam ramos divergentes como caminhos independentes. Consequentemente, se diferentes ramos alcançarem estados intermediários semanticamente similares, eles não podem compartilhar informações, levando a uma exploração repetitiva e maior variância na estimativa de vantagem.

2. Metodologia: GraphPO

Os autores propõem o GraphPO, um novo framework de RL que modela os rollouts de raciocínio como um Grafo Acíclico Dirigido (DAG), em vez de uma cadeia ou uma árvore.

2.1 Construção e Fusão de Grafos

• Estrutura: No GraphPO, as etapas de raciocínio são representadas como arestas, e os estados semânticos intermediários (resumidos a partir do caminho de raciocínio iniciado pelo prompt) são representados como nós.
• Classes de Equivalência: O framework constrói incrementalmente o grafo detectando estados semanticamente similares entre diferentes caminhos usando embeddings de nós (via similaridade de cosseno). Quando a similaridade excede um limiar $\kappa$, os nós são fundidos em classes de equivalência.
• Realocação de Orçamento: Quando um caminho atinge uma classe de equivalência existente, a expansão adicional é considerada provavelmente redundante. O GraphPO reduz pela metade o orçamento da próxima camada para esse caminho (mantendo pelo menos uma continuação) e realoca a computação economizada para novos estados de fronteira, incentivando assim uma exploração mais ampla.

2.2 Recompensa de Grafo (Supervisão de Processo a partir de Resultado)

O GraphPO converte recompensas de resultado esparsas em recompensas densas por etapa sem exigir rótulos de processo anotados:

• Pontuação de Estado: Cada nó recebe uma pontuação baseada em respostas verificáveis alcançáveis a partir dele. Se um nó pertence a uma classe de equivalência, sua pontuação é agrupada com as pontuações de outros nós nessa classe, ponderada por um coeficiente de agrupamento $w$.
• Recompensas de Etapa: A recompensa para uma aresta específica (etapa) é calculada como a diferença nas pontuações de estado entre os nós de destino e origem, descontada pela similaridade entre os endpoints. Isso permite que ramos interrompidos precocemente recebam crédito de parceiros equivalentes que alcançaram com sucesso uma resposta correta.

2.3 Vantagem de Grupo Duplo (Dual-Group Graph Advantage)

Para melhorar tanto a eficiência do raciocínio quanto a atribuição de crédito, o GraphPO introduz uma estimativa de vantagem de grupo duplo:

1. Grupo de Correção ($A_{cor}$): Compara as etapas de saída do mesmo estado semântico. Ele calcula a vantagem de uma etapa específica em relação a outras etapas que saem do mesmo estado, fornecendo atribuição de crédito refinada.
2. Grupo de Eficiência ($A_{eff}$): Compara os caminhos de entrada que alcançam o mesmo estado fundido. Ele recompensa caminhos mais curtos (menos tokens/etapas) que alcançam um estado semântico útil, incentivando a política a encontrar trajetórias de raciocínio mais eficientes.

2.4 Otimização da Política

A política é otimizada usando um objetivo estilo PPO que combina a vantagem de grupo duplo ($A_{dual} = A_{cor} + \lambda_{eff} A_{eff}$). A função objetivo maximiza o retorno esperado enquanto mantém uma restrição de divergência KL em relação a uma política de referência.

3. Principais Contribuições

• Framework de Rollout Baseado em Grafos: O GraphPO é o primeiro framework de RL que representa rollouts de raciocínio como um DAG, agregando explicitamente estados de raciocínio equivalentes para permitir o compartilhamento de sufixos e a realocação de orçamento.
• Estimativa de Vantagem de Grupo Duplo: O artigo propõe um método para otimizar simultaneamente a correção do raciocínio (comparando etapas de saída) e a eficiência do raciocínio (comparando caminhos de entrada), reduzindo a variância da estimativa de vantagem.
• Supervisão de Processo sem Anotações: O método deriva supervisão densa por etapa a partir de recompensas de resultado esparsas, aproveitando a estrutura do grafo e as classes de equivalência, eliminando a necessidade de anotações custosas de Modelos de Recompensa de Processo (PRM).

4. Resultados Experimentais

Experimentos foram conduzidos em três LLMs (Qwen2.5-7B-Math, Qwen3-8B-Base, Deepseek-R1-Distill-Qwen-7B) através de benchmarks de raciocínio matemático (AIME24/25, MATH500, GPQA, LiveCodeBench) e tarefas de busca agêntica.

• Desempenho: O GraphPO superou consistentemente os baselines baseados em cadeia (GRPO, DAPO) e em árvore (TreeRL, SPO, PROS, TreePO) em todos os modelos e conjuntos de dados sob os mesmos orçamentos de tokens e respostas. Por exemplo, no modelo Qwen2.5-7B-Math, o GraphPO alcançou uma precisão média de 40,9%, superando o melhor baseline baseado em árvore (PROS com 37,7%).
• Eficiência de Exploração: O GraphPO demonstrou maior eficiência de exploração, significando que uma maior proporção da computação foi alocada para progresso de raciocínio útil em vez de expansões redundantes. Ele manteve uma entropia mais alta durante o treinamento em comparação com métodos baseados em árvore, que tendem a colapsar em padrões de raciocínio específicos mais rapidamente.
• Comprimento de Resposta: O GraphPO produziu respostas mais curtas do que os métodos baseados em árvore ao fundir estados equivalentes e recompensar caminhos mais curtos, melhorando assim a eficiência de inferência.
• Tarefas Agênticas: O método mostrou desempenho superior em tarefas de busca profunda e agênticas (General AI Assistant, WebWalker, BrowseComp, XBench), validando sua aplicabilidade a processos de tomada de decisão sequencial.
• Comparação com PRMs: O GraphPO superou métodos baseados em PRM (ReasonFlux-PRM) sem utilizar quaisquer dados de processo anotados adicionais.

5. Significância e Alegações

O artigo afirma que o GraphPO fornece um mecanismo prático para obter supervisão de processo auto-emergente a partir de recompensas de resultado isoladamente. Ao modelar os rollouts como um grafo, ele aborda as limitações estruturais das árvores, que não conseguem representar estados equivalentes alcançados por diferentes caminhos.

Os autores asseguram que o GraphPO:

1. Reduz a Variância: Fundir estados equivalentes e agrupar evidências a jusante reduz a variância da estimativa de vantagem.
2. Aumenta a Eficiência: Ele realoca orçamentos computacionais de expansões redundantes para uma exploração diversa e recompensa caminhos de raciocínio mais curtos.
3. Melhora a Utilização: Ele estabiliza as atualizações da política ao permitir que ramos interrompidos precocemente recebam crédito de parceiros bem-sucedidos equivalentes, melhorando a utilização do orçamento de rollout.

O trabalho sugere que rollouts estruturados em grafos oferecem uma alternativa robusta aos métodos baseados em árvore para escalar as capacidades de raciocínio de grandes modelos de linguagem sob configurações de recompensa verificável.