Resumo Técnico: Busca Árvore-de-Pensamento Baseada em Novidade para Raciocínio e Planejamento de LLMs

Declaração do Problema

Embora os Grandes Modelos de Linguagem (LLMs) tenham demonstrado capacidades significativas em tarefas baseadas em linguagem, eles permanecem frágeis em raciocínio complexo e planejamento de longo prazo. O prompting ingênuo frequentemente falha, e abordagens estruturadas como a Árvore-de-Pensamento (ToT) sofrem com custos exponenciais de tempo de execução e de tokens devido à busca de ramificação não podada. Por outro lado, algoritmos de planejamento clássicos, especificamente planejadores baseados em largura como o Iterative Width (IW), alcançam eficiência ao podar estados com base em uma medida de "novidade", mas exigem estruturas de problemas rígidas e formalizadas (por exemplo, PDDL) que não se traduzem bem para cenários de linguagem natural. O desafio central abordado por este trabalho é definir uma noção análoga de novidade dentro do domínio de linguagem não estruturado para permitir a poda eficiente na ToT sem sacrificar a flexibilidade dos LLMs.

Metodologia

Os autores propõem um algoritmo de planejamento que integra a poda baseada em novidade ao framework ToT. A abordagem decompõe o processo de planejamento em quatro subtarefas:

1. Geração de Ações: O LLM propõe possíveis próximas ações a partir de um estado atual.
2. Mapeamento de Estados Sucessores: O LLM mapeia ações para os estados resultantes.
3. Verificação do Plano: O modelo determina se uma sequência de estados satisfaz o objetivo.
4. Estimativa de Novidade: A contribuição novel, onde o LLM atua como um estimador de novidade.

Estimativa de Novidade e Poda

Diferentemente dos planejadores clássicos que calculam a novidade como um inteiro baseado em subconjuntos de características booleanas, este método adapta a novidade à linguagem natural. O LLM é consultado com uma pergunta binária "sim/não" para determinar se um novo estado é novel em comparação com uma lista de estados visitados anteriormente. Isso aproveita o conhecimento geral pré-treinado e a compreensão semântica do modelo para identificar estados únicos sem exigir definições explícitas de átomos ou exemplos few-shot.

A árvore de busca pode ser percorrida usando Busca em Largura (BFS) ou Busca em Profundidade (DFS). Embora o IW clássico geralmente use BFS, os autores observam que, em contextos de LLM, o BFS pode levar a um crescimento exponencial de custos; assim, as compensações entre BFS e DFS são avaliadas. O método é projetado para ser agnóstico ao domínio, dependendo apenas de um prompt de contexto criado manualmente que explica as regras do domínio, evitando engenharia de prompts específica do domínio para o próprio estimador de novidade.

Principais Contribuições

1. Adaptação de Novidade para LLMs: O artigo propõe um conceito mensurável de novidade para domínios de linguagem, utilizando o conhecimento semântico internalizado do LLM para podar ramos de busca com base na unicidade do estado, em vez de correspondência rígida de características.
2. Framework Agnóstico ao Domínio: Uma implementação geral é desenvolvida que permite experimentação flexível em diferentes domínios (planejamento e raciocínio) com esforço manual mínimo, exigindo apenas uma alteração no prompt de contexto para as regras do domínio.
3. Avaliação de Subtarefas: Os autores introduzem um framework de avaliação dedicado, inspirado no Plan-Bench, para testar as quatro subtarefas (geração de ações, mapeamento de estados, verificação e estimativa de novidade) independentemente contra verdades-terrenas geradas por planejadores clássicos.
4. Análise Empírica de Prompting: O trabalho destaca a sensibilidade do planejamento de LLMs ao design de prompts, identificando especificamente pontos de falha recorrentes (por exemplo, distinguir entre "pegar" e "desempilhar" em Blocksworld) e demonstrando como extensões de prompts direcionadas podem melhorar significativamente o desempenho.

Resultados Experimentais

A abordagem foi avaliada nos domínios de planejamento Blocksworld e Logistics, bem como no benchmark MATH (nível de dificuldade 5).

• Desempenho de Subtarefas: Usando o modelo Qwen3 14B, o "Modo de Pensamento" (tokens de raciocínio) e o prompting em linguagem natural geralmente produziram os melhores resultados. O modelo executou com sucesso a poda de novidade em cenários padrão, mas lutou com uma variante mais difícil envolvendo estados não duplicados que exigiam raciocínio estrito baseado em largura.
• Eficiência de Tokens: Em configurações bem ajustadas (especificamente usando "Modo de Pensamento" e mapeamento de ação/estado "Direto"), a ToT podada por novidade reduziu os custos de tokens em até 20 vezes em comparação com a ToT padrão, mantendo taxas de sucesso semelhantes. Por exemplo, em Blocksworld com DFS e Modo de Pensamento, a ToT base teve uma média de 330 mil tokens, enquanto a versão podada por novidade teve uma média de 18 mil tokens.
• Generalização: O método transferiu-se efetivamente para o domínio Logistics e para o benchmark MATH sem re-ajustar os prompts de estimativa de novidade, embora a eficiência ótima de tokens em domínios de raciocínio distintos (como MATH) pareça exigir ajuste de prompts específico do domínio.
• Limitações: Em configurações mal ajustadas, o desempenho degradou significativamente, com taxas de resolução próximas de zero e custos de tokens aumentando em mais de 100% devido à sobrecarga das consultas de novidade. O método depende fortemente do desempenho base da configuração ToT subjacente.

Significado e Alegações

O artigo afirma que a poda baseada em novidade pode melhorar com sucesso a eficiência do raciocínio Árvore-de-Pensamento, tornando-o viável para tarefas de planejamento complexas ao reduzir drasticamente o espaço de busca e o consumo de tokens. Os autores enfatizam que, embora o método se desvie do planejamento clássico baseado em largura pela falta de garantias formais sobre a qualidade da solução ou cálculo preciso de novidade, ele oferece uma alternativa prática e flexível que aproveita a adaptabilidade dos LLMs.

No entanto, os autores permanecem modestos quanto à robustez da abordagem. Eles observam que a instabilidade do prompting recursivo de LLMs permanece um desafio fundamental, tornando a configuração laboriosa e imprevisível. O comportamento de poda é observado como sendo impulsionado largamente pela detecção de duplicatas, em vez de raciocínio de "novidade" verdadeiro em cenários complexos. Consequentemente, o trabalho é apresentado como um passo em direção a um planejamento de LLM mais eficiente, sugerindo direções futuras como serialização de objetivos, estimadores de novidade alternativos ou o uso de modelos base maiores para aprimorar a compreensão de estados.