Resumo Técnico: Maximização da Informatividade de Rollouts sob Orçamento Fixo

1. Formulação do Problema

O artigo aborda um gargalo estrutural no Aprendizado por Reforço (RL) para Grandes Modelos de Linguagem (LLMs) aumentados por ferramentas, sob recompensas terminais esparsas (ex.: $R \in \{-1, +1\}$). A questão central é a Informatividade de Rollouts sob Orçamento Fixo (RIFB).

Na Otimização de Política Relativa em Grupo (GRPO) padrão, o sinal de vantagem é normalizado pelo desvio padrão das recompensas dentro de um grupo de $B$ rollouts. Se todos os $B$ rollouts independentes para um determinado prompt produzirem o mesmo resultado (todos sucesso ou todos falha), o desvio padrão torna-se zero, fazendo com que a vantagem colapse para zero. Consequentemente, nenhuma massa de gradiente é injetada na política, tornando o computo gasto nesses rollouts inútil.

Os autores formalizam isso como um resultado de impossibilidade para amostragem independente:

• Teorema 1: Para qualquer amostrador independente agnóstico ao orçamento, a probabilidade de colapso (variância zero) é $p^B + (1-p)^B$, onde $p$ é a probabilidade de sucesso por prompt.
• Implicação: À medida que $p \to 0$ ou $p \to 1$ (prompts difíceis), a probabilidade de não colapso cresce no máximo linearmente com o orçamento ($B \cdot \min(p, 1-p)$). Assim, simplesmente aumentar o orçamento de rollout $B$ não pode escapar do regime de gradiente zero para prompts difíceis; a taxa de colapso permanece afastada de zero, independentemente do tamanho do orçamento.

2. Metodologia: INFOTREE

Para superar as limitações da amostragem independente, os autores propõem o INFOTREE, um framework de busca em árvore durante o treinamento que otimiza quais estados expandir, em vez de quantos amostrar.

2.1 Formulação Submodular

A ideia central é que o problema de selecionar qual estado intermediário expandir para maximizar a informatividade da árvore pode ser formulado como um problema de maximização submodular monótona. A função objetivo $F$ é composta por três termos:

1. Cobertura: Rastreia o valor de backup $\bar{Q}(s)$ das folhas.
2. Novidade: Rastreia o termo de exploração baseado em contagens de visitas (termo UCB clássico).
3. Contraste: Rastreia a diversidade de resultados entre nós irmãos, derivada da entropia ao nível de token.

Os autores provam que $F$ é monótona e submodular. Isso permite o uso de um seletor guloso com uma garantia teórica de aproximação de $(1 - 1/e)$ para o cronograma de expansão ótimo.

2.2 O Seletor UUCB

A solução gulosa para o problema submodular produz a pontuação Upper Confidence Bound Consciente de Incerteza (UUCB), que não é uma heurística ad hoc, mas um ganho marginal de forma fechada da função objetivo:
$$\text{UUCB}(v) = \bar{Q}(v) + c\sqrt{\frac{\ln N(p_a(v))}{N(v)+1}} + \lambda_H \tilde{H}(v) - \lambda_C \tilde{C}(v) - \lambda_D \tilde{d}(v)$$

• $\bar{Q}(v)$: Ganho de cobertura.
• Segundo termo: Ganho de novidade (exploração UCB padrão).
• $\lambda_H \tilde{H}(v)$: Ganho de contraste, representando entropia ao nível de token estratificada por profundidade (normalizada para ser comparável entre profundidades).
• Penalizações: $\lambda_C$ e $\lambda_D$ penalizam custos de chamada de ferramenta e profundidade de expansão, respectivamente, para respeitar a restrição de orçamento.

2.3 Componentes do Sistema

O INFOTREE integra o seletor UUCB com dois mecanismos adicionais para abordar fraquezas práticas:

• Alocador de Orçamento Adaptativo (ABA): Um MLP leve treinado offline para prever se um prompt com uma árvore de resultados uniformes (provável de colapsar) pode ser "resgatado" por um único rollout de alta temperatura. Se a probabilidade de resgate prevista exceder um limiar, um rollout extra é acionado. Isso eleva a razão de resultados mistos de ~58% para ~76% com sobrecarga de orçamento <5%.
• Expansão Especulativa: Para reduzir a latência de tempo real, os trabalhadores avaliam as pontuações UUCB usando valores-Q potencialmente desatualizados (desatualização limitada). Uma etapa de reconciliação aceita ou reverte expansões com base em tags de versão. Isso reduz a sobrecarga de 14,3% para 4,8%.
• Vantagem Hierárquica: Um sinal de gradiente derivado do contraste entre irmãos ao longo do caminho da raiz à folha, fornecendo um mecanismo alternativo de atribuição de crédito que complementa a vantagem GRPO normalizada por grupo.

3. Contribuições Principais

1. Formalização Teórica: O artigo define a RIFB e prova que a amostragem independente sofre de colapso persistente em prompts difíceis, independentemente do tamanho do orçamento.
2. Redução Submodular: Estabelece que a construção de árvores sob um orçamento fixo é um problema de maximização submodular, fornecendo uma garantia teórica de $(1-1/e)$ para o seletor UUCB guloso.
3. Derivação Analítica: Demonstra que o bônus de entropia no UUCB é uma consequência analítica da função objetivo submodular (termo de Contraste), e não um truque empírico.
4. Design de Sistema: A introdução do ABA e da Expansão Especulativa cria um framework prático que equilibra informatividade com eficiência computacional.
5. Ortogonalidade: Os autores mostram que seu mecanismo de seleção opera em um eixo ortogonal ao re-ponderamento de trajetórias (ex.: CW-GRPO) e à reutilização de rollouts (ex.: compartilhamento de prefixo Tree-GRPO), permitindo ganhos composicionais.

4. Resultados Experimentais

O método foi avaliado em nove benchmarks de raciocínio matemático, busca na web e agentes de codificação/SO ricos em ferramentas.

• Desempenho: O INFOTREE supera consistentemente o GRPO plano, DeepSearch, Tree-GRPO, AT2PO, CW-GRPO e RC-GRPO.
  • No AIME 2025, o INFOTREE atinge uma Média@32 de 30,2 (vs. 27,7 para GRPO Plano e 29,1 para Tree-GRPO).
  • No GAIA, atinge 56,0% de precisão (vs. 44,8% para GRPO Plano).
• Composabilidade: Combinar o INFOTREE com compartilhamento de prefixo Tree-GRPO ou pesos de contribuição CW-GRPO produz ganhos adicionais, confirmando a ortogonalidade das abordagens.
• Robustez: Uma grade de hiperparâmetros $5 \times 5 \times 5$ sobre os coeficientes UUCB ($\lambda_H, \lambda_C, \lambda_D$) mostra que >75% do espaço está dentro de 2,1 pontos do ótimo, indicando que o método não é frágil ao ajuste de hiperparâmetros.
• Eficiência: Apesar da busca em árvore, a sobrecarga de tempo real é reduzida para 4,8% via Expansão Especulativa. O "passos-para-alvo" (passos para atingir Média@32 de 28) cai de 248 (GRPO Plano) para 138 (INFOTREE), uma melhoria de 1,57x no tempo de execução.
• Informatividade de Gradiente: Medição direta da norma quadrada do gradiente mostra que o INFOTREE produz uma RIFB 3,9x maior que o GRPO plano.

5. Significado e Alegações

O artigo afirma reposicionar o design de estratégias de rollout de uma preferência de engenharia para um problema de otimização formalmente fundamentado.

• De Heurística para Teoria: O trabalho transforma o bônus de entropia de um truque empírico em um componente necessário de uma função objetivo submodular, fornecendo uma justificativa teórica para sua inclusão.
• Resolvendo o Colapso: Ao mirar explicitamente o regime de "gradiente zero" através de seleção submodular e orçamento adaptativo, o INFOTREE aborda uma limitação fundamental dos agentes atuais baseados em GRPO em prompts difíceis.
• Complementaridade: Os resultados sugerem que maximizar a informatividade de rollouts via construção de árvores é um eixo distinto e complementar aos métodos existentes que focam em re-ponderação ou diversificação de amostras independentes.

Os autores notam limitações, incluindo a suposição de uma política fixa dentro de um episódio de construção de árvore e a natureza preliminar dos resultados em tarefas abertas sem recompensas verificáveis. No entanto, o framework é apresentado como uma solução robusta para o treinamento de agentes aumentados por ferramentas sob recompensas esparsas.