DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search

1. O Problema

O artigo identifica um gargalo fundamental no treinamento de Modelos de Linguagem (LLMs) para raciocínio complexo utilizando Aprendizado por Reforço com Recompensas Verificáveis (RLVR).

• Estagnação de Desempenho: Estudos recentes mostram que, após milhares de passos de otimização, os ganhos de desempenho diminuem drasticamente (plateau), mesmo com aumento massivo no investimento computacional.
• Exploração Esparsa: As práticas atuais de RLVR dependem de "rollouts" (rolagens) diretos e limitados do modelo. Isso resulta em uma exploração esparsa do espaço de soluções, onde o modelo frequentemente perde caminhos de raciocínio críticos e falha em cobrir sistematicamente as possibilidades de solução.
• Separação Treino-Inferência: Métodos existentes geralmente tratam a busca estruturada (como Tree Search) apenas como uma ferramenta de inferência, não integrando a exploração sistemática no próprio processo de treinamento.

2. Metodologia: DeepSearch

O DeepSearch é um framework que integra diretamente o Monte Carlo Tree Search (MCTS) no loop de treinamento do RLVR. A ideia central é mudar o foco de "escalar a profundidade do treinamento" (mais passos) para "escalar a largura do treinamento" (exploração sistemática).

O framework opera através de três componentes principais:

A. Seleção de Fronteira Global (Global Frontier Selection)

Diferente do MCTS tradicional que usa a regra UCT (Upper Confidence Bounds for Trees) para travessias raiz-folha (que podem ser miope e computacionalmente custosas), o DeepSearch utiliza uma seleção global:

• Mantém uma visão global de todos os nós de fronteira (folhas) na árvore de busca.
• Prioriza nós promissores com base em uma pontuação composta por:
  1. Potencial de Qualidade: Baseado no valor Q do nó pai (transformado por tanh).
  2. Bônus de Incerteza: Baseado na entropia da política do modelo (para explorar regiões onde o modelo é confiante, mas pode estar errado).
  3. Bônus de Profundidade: Incentiva a exploração de cadeias de raciocínio mais longas.

B. Expansão com Guia de Entropia e Backup de Pontuação

• Seleção de Trajetórias Negativas: Se nenhuma solução correta for encontrada, o sistema seleciona a trajetória incorreta com a menor entropia média (o erro mais "confiante" do modelo). Isso permite supervisionar e corrigir erros sistemáticos onde o modelo tem alta certeza, mas está errado.
• Backup de Q-Value Assimétrico: O sistema atualiza os valores Q dos nós intermediários. Uma regra de restrição garante que nós que já levaram a uma solução correta mantenham valores não negativos, enquanto nós que levam apenas a erros acumulam penalidades. Isso evita a propagação destrutiva de ruído.

C. Treinamento Adaptativo com Replay Buffer

Para lidar com a ineficiência computacional de aplicar MCTS em todos os exemplos:

• Filtragem Progressiva: O conjunto de treinamento é iterativamente refinado para incluir apenas problemas difíceis onde a taxa de sucesso do modelo é baixa (abaixo de um limiar $\delta$).
• Buffer de Replay e Cache de Soluções: Soluções corretas descobertas pelo MCTS em iterações anteriores são armazenadas. Se um problema já tiver uma solução cacheada, o sistema evita a busca completa do MCTS e usa a solução armazenada, combinada com novos rollouts diretos. Isso reduz drasticamente a redundância computacional.

D. Objetivo de Treinamento: Tree-GRPO

O modelo é otimizado usando uma variante do GRPO (Grouped Relative Policy Optimization) adaptada para árvores:

• Utiliza normalização de média apenas (mean-only normalization) para calcular a vantagem, evitando instabilidades numéricas.
• Aplica soft clipping (função tanh) nos valores Q intermediários para prevenir explosão de gradientes, mantendo a ordem relativa dos valores.

3. Contribuições Chave

1. Integração MCTS no Treino: É a primeira abordagem a embutir a busca estruturada diretamente no loop de RLVR, permitindo que o modelo aprenda não apenas com a resposta final, mas com o processo de exploração sistemática.
2. Estratégia de Seleção de Fronteira Global: Substitui a travessia local UCT por uma seleção global que equilibra melhor a exploração entre sub-árvores, evitando armadilhas locais.
3. Seleção de Erros Confiáveis: A estratégia de priorizar trajetórias incorretas com baixa entropia (alta confiança) para supervisão, provando ser mais eficaz do que escolher erros aleatórios ou de baixa confiança.
4. Eficiência Computacional: O uso de cache de soluções e filtragem adaptativa permite que o modelo aprenda com problemas difíceis sem desperdiçar recursos em problemas já dominados.

4. Resultados Experimentais

Os experimentos foram realizados em benchmarks de raciocínio matemático (AIME 2024/2025, AMC2023, MATH500, Minerva, Olympiad) usando um modelo base de 1.5B parâmetros (Nemotron-Research-Reasoning-Qwen-1.5B v2).

• Desempenho de Precisão: O DeepSearch alcançou uma acurácia média de 62,95%, estabelecendo um novo estado da arte (SOTA) para modelos de 1.5B, superando o modelo anterior (61,70%) e outras abordagens de RL avançadas.
• Eficiência Computacional:
  • O DeepSearch alcançou esses resultados usando 5,7 vezes menos horas de GPU do que as abordagens de treinamento estendido (extended training) que tentam escalar apenas o número de passos.
  • Enquanto o treinamento estendido exigiu ~1.883 horas de GPU para atingir ~62,02% de precisão, o DeepSearch atingiu 62,95% com apenas ~330 horas de GPU.
• Análise de Ablação: A remoção da seleção de fronteira global ou da estratégia de seleção de erros confiáveis resultou em quedas significativas de desempenho, confirmando a importância de cada componente.

5. Significado e Implicações

O trabalho do DeepSearch desafia a premissa comum de que o aprimoramento do RLVR depende exclusivamente do aumento linear do orçamento computacional (mais passos de treino ou modelos maiores).

• Mudança de Paradigma: Demonstra que a exploração sistemática durante o treinamento é mais valiosa do que a simples expansão da profundidade do treino.
• Escalabilidade: Oferece um caminho mais prático e escalável para melhorar as capacidades de raciocínio de modelos de linguagem, sugerindo que a inovação algorítmica (como a integração de busca) pode superar a escalagem bruta de recursos.
• Qualidade vs. Quantidade: Os resultados indicam que a qualidade da exploração (cobertura do espaço de soluções e atribuição de crédito granular) é o fator limitante atual no RLVR, e não a quantidade de dados ou tempo de treino.

Em resumo, o DeepSearch estabelece uma nova direção para o desenvolvimento de modelos de raciocínio, onde a estrutura do processo de aprendizado (espelhando padrões de raciocínio sofisticados via busca) é tão crucial quanto os dados ou a arquitetura do modelo.