Resumo Técnico: Empirical-MCTS

1. Definição do Problema

As atuais estratégias de escalonamento em tempo de inferência, particularmente a Busca em Árvore Monte Carlo (MCTS) e a amostragem "Best-of-N", melhoraram significativamente as capacidades de raciocínio de Grandes Modelos de Linguagem (LLMs). No entanto, uma limitação crítica persiste: essas abordagens são sem estado (stateless). Uma vez que um processo de busca é concluído para um problema específico, os padrões de raciocínio bem-sucedidos e as estratégias válidas são descartados. Isso contrasta fortemente com a resolução de problemas humana, que é empírica, baseando-se na acumulação tanto de conhecimento de domínio de longo prazo quanto de feedback imediato de curto prazo. Tentativas existentes de integrar memória, como o FLEX (que separa a recuperação do raciocínio) ou o Training-Free GRPO (que carece de busca em árvore estruturada), falham em unificar a acumulação contínua de experiência com a exploração estruturada. Consequentemente, agentes não conseguem evoluir suas estratégias de busca dinamicamente através de instâncias de problemas sem atualizações de parâmetros dispendiosas.

2. Metodologia: O Framework Empirical-MCTS

Os autores propõem o Empirical-MCTS, um framework de loop duplo projetado para transformar a busca sem estado em um processo de aprendizado não paramétrico contínuo. O sistema unifica a exploração local com a otimização de memória global através de dois mecanismos centrais:

A. Pairwise-Experience-Evolutionary Meta-Prompting (PE-EMP)

O PE-EMP atua como um otimizador reflexivo dentro do loop de busca local. Em vez de usar prompts de sistema estáticos para a expansão de nós, o PE-EMP evolui dinamicamente o meta-prompt em tempo real com base no feedback pareado.

• Mecanismo: Ao expandir um nó, o sistema compara um estado candidato ($S_c$) contra um estado de referência ($S_p$). Um modelo Juiz processa a consulta, as experiências prévias e os dois estados para gerar uma saída triádica: um vetor de pontuação bruta, novos insights empíricos e um meta-prompt evoluído ($P_{evolved}$).
• Processo Cognitivo de Sete Estágios: O módulo PE-EMP executa uma sequência rigorosa:
  1. Geração de Critérios Adaptativos: O modelo gera dimensões de avaliação específicas adaptadas à consulta (inspirado em Self-Principled Critique Tuning).
  2. Cadeia de Pensamento Comparativa (Comparative CoT): Uma crítica passo a passo contrasta o candidato e a referência em relação a esses critérios.
  3. Alocação Dinâmica de Pesos: Pesos são atribuídos aos critérios com base na relevância do contexto.
  4. Pontuação Ponderada: Pontuações quantitativas são calculadas.
  5. Geração de Pontuação Bruta: Um valor escalar preciso (0–10) é derivado.
  6. Síntese de Insights Contextuais: O feedback imediato é sintetizado com a sabedoria histórica recuperada para destilar insights empíricos de ordem superior ($E_{new}$).
  7. Evolução Estratégica de Prompt: O modelo analisa as diferenças de execução para sintetizar um meta-prompt mais avançado, codificando fatores críticos de sucesso e lições de falha.
• Recuperação: Para evitar o desvio semântico, o sistema recupera experiências ($E_{prior}$) de uma biblioteca global apenas se estas compartilharem a mesma taxonomia de tarefa (ex: prova geométrica) que a consulta atual.

B. Agente de Otimização de Memória

Este componente gerencia um repositório de experiência global como um prior de política dinâmico, funcionando como um otimizador no espaço do contexto em vez de um banco de dados estático.

• Operações Atômicas: Ao receber novos insights ($E_{new}$) do PE-EMP, o agente executa quatro operações atômicas para atualizar a biblioteca ($D_t$):
  • Adicionar (Add): Anexa experiências distintas e de alta qualidade.
  • Modificar (Modify): Refina experiências existentes com base em novas vantagens semânticas.
  • Mesclar (Merge): Sintetiza experiências fragmentadas em princípios coesos para reduzir a redundância.
  • Excluir (Delete): Podar experiências obsoletas ou de baixa qualidade (um mecanismo de "esquecimento").
• Atualização Não Paramétrica: Este processo desloca a distribuição de saída $\pi(y|q, D)$ em direção a recompensas mais altas ao longo do tempo, sem treinamento baseado em gradiente.

C. Estimativa de Valor e Estratégia de Busca

• Integração de Preferência Híbrida: Para converter insights discretos em recompensas contínuas, o framework utiliza um sinal de Recompensa Híbrida (Hybrid-Reward). Ele mapeia pontuações pareadas brutas para probabilidades de transição local via modelo de Bradley-Terry e emprega um Enhanced Borda Count (EBC) para construir um ranking global, abordando a não-transitividade inerente às preferências de LLMs.
• Busca: O framework utiliza UCB (Upper Confidence Bound) para seleção de nós e uma regra de retropropagação baseada em decaimento para garantir que insights de alta recompensa se propaguem eficientemente para cima na árvore.

3. Principais Contribuições

1. Paradigma Empirical-MCTS: Um novo framework que une busca estruturada e aprendizado contínuo, transformando o MCTS de uma técnica de inferência sem estado em um agente de aprendizado online não paramétrico capaz de acumular "sabedoria" através de problemas díspares sem atualizações de pesos.
2. Mecanismo PE-EMP: Um otimizador reflexivo que sintetiza "princípios próprios" a partir de feedback pareado para evoluir dinamicamente meta-prompts, permitindo que agentes refinem políticas de raciocínio em tempo real.
3. Validação Empírica: Demonstração de que o Empirical-MCTS supera o MCTS padrão e modelos anteriores baseados em experiência em benchmarks de alta dificuldade, provando que "lembrar" padrões de raciocínio é crítico para resolver problemas de lógica complexos e de múltiplos passos.

4. Resultados Experimentais

O framework foi avaliado no AIME25, MathArena Apex e ARC-AGI-2 utilizando modelos incluindo DeepSeek-V3.1-Terminus, gpt-oss-120b e Gemini 3 Flash.

• Raciocínio Matemático (AIME25): O Empirical-MCTS alcançou 73,3% de precisão, superando o LLaMA-Berry sem estado (63,3%) e o agente FLEX aumentado por memória (66,6%).
• Dificuldade Extrema (MathArena Apex): O modelo base obteve pontuação de 0,00%. Enquanto o LLaMA-Berry atingiu 2,08%, o Empirical-MCTS alcançou 4,17%, demonstrando a capacidade de sintetizar novos caminhos de solução através da acumulação empírica onde métodos padrão falharam.
• Eficiência de Custo (ARC-AGI-2 & MathArena): Usando o eficiente Gemini 3 Flash, o Empirical-MCTS alcançou 38,33% no ARC-AGI-2 e 35,42% no MathArena Apex. Este desempenho superou modelos muito mais caros (ex: GPT-5.2 a um custo de \12,00 vs. o Nosso a \5,24), estabelecendo uma nova fronteira de Pareto para eficiência de raciocínio.
• Estudos de Ablação: Remover o PE-EMP reduziu o desempenho para 56,7% (igualando a amostragem repetida ingênua), confirmando que a evolução de prompts impulsionada por sinais pareados é o motor central de melhoria. Remover o meta-prompting mantendo a memória reduziu o desempenho para 66,7%, destacando a necessidade de instrução dinâmica.

5. Significância e Alegações

O artigo afirma que o Empirical-MCTS estabelece um novo paradigma onde a busca estruturada é acoplada à acumulação empírica. Os autores argumentam que a necessidade crítica para dominar tarefas de raciocínio complexas e abertas não reside apenas na capacidade de busca em si, mas na habilidade de "lembrar" e refinar padrões de raciocínio passados.

Ao converter o histórico de busca em priors de política acionáveis, o framework permite que modelos significativamente menores superem baselines maiores e sem estado. Os resultados sublinham que o aprendizado contínuo e não paramétrico via otimização de memória e evolução de meta-prompt é uma alternativa viável e eficaz ao treinamento tradicional baseado em gradiente para o aprimoramento do raciocínio de LLMs.

Limitações Reconhecidas: Os autores observam que o framework assume que o modelo base pode verificar passos de raciocínio com precisão. Para tarefas que excedem o limite de verificação do modelo, há o risco de integrar "sabedoria alucinada", levando potencialmente a uma evolução degenerativa. Trabalhos futuros visam introduzir verificações de consistência robustas e quantificação de incerteza para mitigar isso.