🤖 AI

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

O artigo apresenta o GATS, um framework de planejamento que substitui a custosa inferência de LLM por um modelo de mundo em camadas e uma busca em árvore baseada em UCB1 para alcançar taxas de sucesso de 100% e planejamento determinístico de chamada zero através de diversas tarefas complexas, superando significativamente métodos existentes como LATS e ReAct.

Autores originais: Maureese Williams, Dymitr Nowicki

Publicado 2026-07-13

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Maureese Williams, Dymitr Nowicki

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando resolver um labirinto gigante e complicado. Você tem um amigo superinteligente (um Grande Modelo de Linguagem, ou LLM) que pode conversar com você e sugerir para qual direção virar. Mas aqui está o detalhe: toda vez que você pede um conselho ao seu amigo, ele precisa tirar um longo cochilo para pensar e, às vezes, ele adivinha algo diferente cada vez que você faz a mesma pergunta. Se o labirinto tiver becos sem saída ou exigir uma longa sequência de curvas, pedir ajuda ao seu amigo em cada passo torna tudo caro e confuso.

Este é o problema que os pesquisadores Maureese Williams e Dymitr Nowicki abordaram com seu novo sistema, GATS (Busca em Árvore Aumentada por Grafos). Eles encontraram uma maneira de navegar pelo labirinto de forma tão eficiente que mal precisam acordar seu amigo superinteligente.

O Jeito Antigo: A Abordagem de "Perguntar a Cada Passo"

Métodos anteriores, como o ReAct e o LATS, eram um pouco como um trilheiro que para em cada bifurcação da estrada para perguntar ao guia: "Para que lado devo ir?".

ReAct apenas pergunta uma vez e segue em frente. É rápido, mas frequentemente entra em becos sem saída. Em seus testes, esse método teve sucesso em apenas 64% dos cenários complicados de labirinto.
LATS é mais inteligente; ele pergunta ao guia, depois pergunta novamente sobre o próximo passo, e novamente, construindo uma árvore de possibilidades. Mas, como ele pede ao guia (o LLM) para cada uma das ramificações dessa árvore, o guia fica cansado e o processo se torna caro. Nos testes, o LATS teve sucesso 92% das vezes, mas teve que consultar o guia cerca de 37 vezes por tarefa. Além disso, como o guia às vezes adivinha aleatoriamente, você pode obter um caminho diferente se tentar o mesmo labirinto duas vezes.

O Novo Jeito: GATS (A Estratégia do "Criador de Mapas")

O GATS muda o jogo. Em vez de pedir ao guia a cada curva, o GATS constrói seu próprio mapa interno usando um Modelo de Mundo em Camadas. Pense neste mapa como tendo três camadas de conhecimento:

Camada 1 (O Livro de Regras Exato): Para ações que o sistema já conhece perfeitamente (como "se eu apertar este botão, a porta abre"), ele usa uma verificação simples e instantânea. Sem necessidade de pensar. É como saber que 2+2 sempre é igual a 4.
Camada 2 (O Registro de Experiências): Se o sistema vivenciou uma ação antes, mas não possui uma regra perfeita para ela, ele consulta seu diário de viagens passadas. "Da última vez que fiz isso, funcionou 9 de cada 10 vezes". Isso é aprendido através de dados, não por suposição.
Camada 3 (O Amigo Supergênio): Somente quando o sistema encontra algo totalmente novo e desconhecido é que ele acorda o guia LLM. Mas aqui está a mágica: assim que o guia responde, o GATS escreve a resposta no mapa. Na próxima vez que essa situação específica surgir, o GATS apenas consulta o mapa. Ele nunca pergunta ao guia novamente sobre aquela coisa específica.

Os Resultados: Velocidade, Certeza e Sucesso

Os pesquisadores testaram isso em 100 tarefas de planejamento sintéticas que foram desenhadas para serem complicadas, com caminhos ramificados e becos sem saída.

GATS obteve uma taxa de sucesso perfeita de 100%.
LATS obteve 92%.
ReAct obteve 64%.

Mas o ponto crucial? O GATS fez zero chamadas ao LLM durante o planejamento real dessas tarefas. Ele fez todo o pensamento usando seu próprio mapa e regras. Como não dependeu das suposições aleatórias do LLM, o GATS produziu exatamente o mesmo plano perfeito toda vez que era executado. Houve zero variância.

Eles também realizaram um "teste de estresse" massivo com 120 tarefas em 12 categorias difíceis, como fluxos de trabalho de programação, reserva de voos e navegação em labirintos complexos.

GATS manteve 100% de sucesso.
LATS caiu para 88,9%.
ReAct desabou para 23,9%.

Por Que Funciona (O Ingrediente Secreto)

O artigo sugere que o GATS vence porque utiliza uma busca sistemática (chamada UCB1) em vez de suposições aleatórias. Imagine um detetive que verifica cada pista metodicamente em vez de apenas seguir uma intuição.

Sistemático vs. Aleatório: O LATS depende do LLM para adivinhar qual caminho parece ser bom. Se a "intuição" do LLM estiver errada, todo o plano falha. O GATS verifica todas as opções sistematicamente, garantindo que não perderá o caminho certo apenas porque o guia teve um dia ruim.
Determinístico vs. Estocástico: Como o GATS usa seu próprio mapa para a maioria das etapas, o resultado é sempre o mesmo. O LATS, dependendo do LLM, pode dar uma resposta diferente se você executar a mesma tarefa duas vezes.

O Que Isso Significa (E o Que Não Significa)

Os autores são muito claros sobre os limites de seu sucesso. Esses resultados baseiam-se em simulações e tarefas sintéticas onde as regras do jogo (as "especificações de ação") eram conhecidas antecipadamente. Nesses ambientes controlados, o GATS é um campeão.

No entanto, o artigo descarta explicitamente a ideia de que o GATS seja uma solução mágica para tudo no momento. Se você lançar o GATS em um mundo completamente selvagem e aberto, onde não há regras e nem registros de experiências para aprender, ele teria que depender mais pesadamente do LLM (Camada 3), o que o tornaria mais lento e menos eficiente. Os autores sugerem que, para o GATS brilhar no mundo real, precisamos construir melhores mapas (modelos de mundo) primeiro, talvez aprendendo com registros de como os humanos realmente utilizam ferramentas.

Em resumo, o artigo mostra que para tarefas de planejamento onde podemos definir as regras, não precisamos pedir ajuda a uma IA superinteligente a cada passo. Podemos construir um mapa inteligente e autoatualizável que nos permite navegar por problemas complexos com 100% de sucesso, zero custo e zero confusão.

Resumo Técnico: GATS (Graph-Augmented Tree Search with Layered World Models)

Declaração do Problema

Agentes de Grandes Modelos de Linguagem (LLMs) demonstraram potencial em planejamento de múltiplos passos e uso de ferramentas, mas as abordagens atuais como ReAct e LATS (Language Agent Tree Search) enfrentam duas limitações críticas:

Custo Computacional: Os métodos existentes dependem de inferência dispendiosa de LLM em cada passo de planejamento ou nó de busca, levando a alta latência e consumo de recursos.
Estocasticidade: A amostragem de LLM introduz variância, resultando em planos não reproduzíveis e desempenho inconsistente entre execuções.

O desafio central é desenvolver um framework de planejamento que mantenha as capacidades de raciocínio dos LLMs, eliminando simultaneamente as chamadas de inferência de LLM para predição de estado, alcançando assim um planejamento de agente determinístico, eficiente e escalável.

Metodologia: Framework GATS

Os autores propõem o GATS (Graph-Augmented Tree Search), uma arquitetura de planejamento que desacopla o modelo de mundo do LLM. O GATS combina busca em árvore sistemática baseada em UCB1 com um Modelo de Mundo em Camadas (Layered World Model) e um Grafo de Transição de Estados persistente.

1. Modelo de Mundo em Camadas ( $W$ )

O modelo de mundo prevê o próximo estado ( $s'$ ) e a confiança ( $p$ ) dado um estado atual ( $s$ ) e uma ação ( $a$ ). Ele consulta três camadas em ordem crescente de generalidade e custo computacional:

L1 (Simbólica): Correspondência exata de pré-condição-efeito para ações com especificações conhecidas do tipo STRIPS. Esta camada fornece predições determinísticas ( $p=1.0$ ) com custo computacional mínimo (busca simbólica).
L2 (Estatística Aprendida): Predições estatísticas derivadas de logs de execução. Para ações observadas durante a execução, mas que carecem de especificações formais, ela retorna o efeito mais frequente com confiança $p = \min(\text{contagem}(a)/10, 1.0)$ .
L3 (Generativa/LLM): Predição baseada em LLM para ações genuinamente novas ou ambíguas. Crucialmente, as predições da L3 são armazenadas em cache para evitar chamadas de inferência repetidas para a mesma transição.

O sistema prioriza L1 e L2 para maximizar a cobertura, invocando L3 apenas quando necessário. Isso "amortiza" o custo do LLM, transformando-o de um requisito de inferência por passo em um custo de bootstrapping único.

2. Grafo de Transição de Estados Persistente

Ao contrário da busca em árvore tradicional, que expande nós independentemente, o GATS mantém um grafo explícito $G = (V, E)$ onde os nós representam chaves de estado canônicas $k(s)$ .

Fusão de Estados (State Merging): Se diferentes sequências de ações atingirem o mesmo estado, elas se fundem em um único nó. Isso permite o reuso de predições de transição, contagens de visitas e estimativas de valor entre caminhos.
Persistência: O grafo persiste através dos passos de planejamento. Após uma ação ser executada, o planejamento retoma do respectivo nó do grafo em vez de reiniciar a busca, amortizando a estimativa de valor e as estatísticas de busca ao longo de todo o episódio.
Detecção de Becos Sem Saída (Dead-End Detection): Nós sem caminho para um objetivo são marcados como becos sem saída, permitindo que o planejador atribua valores baixos a ações que levam a essas regiões.

3. Busca Baseada em UCB1

O GATS emprega uma estratégia de seleção UCB1 (Upper Confidence Bound) sobre as arestas do grafo.

Seleção de Ação: Em cada estado, o algoritmo seleciona a ação $a$ que maximiza $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ . Isso garante a exploração sistemática de todas as ações aplicáveis antes de se comprometer com caminhos de alto valor.
Estimativa de Valor: O valor de um estado é derivado da distância prevista mais curta até o objetivo ( $d_G$ ) usando uma heurística baseada em BFS: $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ .
Integração de Confiança: O valor de backup incorpora a confiança do modelo de mundo: $v = p \cdot StateValue(s') - \lambda(1-p)$ , penalizando predições incertas.

Principais Contribuições

Arquitetura de Modelo de Mundo em Camadas: Uma integração inovadora de componentes simbólicos, aprendidos e generativos que permite a predição eficiente de estados enquanto minimiza a dependência de LLM.
Busca UCB1 Sistemática com Memória de Grafo: Um algoritmo de planejamento que supera a exploração guiada por LLM aleatória ao aproveitar um grafo persistente para reutilizar evidências de busca e garantir resultados determinísticos.
Avaliação Abrangente: Testes extensivos em 100 tarefas de planejamento sintético e um teste de estresse de 12 categorias (120 tarefas) cobrindo codificação, navegação web e cenários de longo horizonte.
Zero Chamadas de LLM Durante o Planejamento: Demonstrou que o GATS pode alcançar taxas de sucesso de 100% com zero chamadas de LLM durante a fase de planejamento, contrastando fortemente com baselines que exigem dezenas de chamadas por tarefa.

Resultados Experimentais

Tarefas de Planejamento Sintético (100 Tarefas)

Taxa de Sucesso: O GATS alcançou 100% de sucesso (com orçamento $b=10$ ), superando o LATS (92%) e o ReAct (64%).
Eficiência: O GATS exigiu 0 chamadas de LLM por tarefa durante o planejamento, enquanto o LATS exigiu aproximadamente 37 chamadas.
Determinismo: O GATS produziu planos com 0% de variância entre sementes aleatórias, enquanto o LATS e o ReAct exibiram 1–5% de variância devido à estocasticidade do LLM.
Otimalidade: O GATS alcançou uma razão de otimalidade de 1.00, igualando-se ao Oracle.

Teste de Estresse (12 Categorias, 120 Tarefas)

O teste de estresse incluiu cenários desafiadores como fluxos de trabalho de codificação, navegação web, tarefas de horizonte profundo e tomada de decisão irreversível (becos sem saída).

Desempenho Geral: O GATS manteve 100% de sucesso em todas as categorias.
Desempenho Comparativo: O LATS caiu para 88,9% no total, com dificuldades significativas em tarefas de codificação (63,3%), navegação web (63,3%) e horizonte profundo (63,3%). O ReAct falhou catastroficamente com 23,9%.
Ganhos Específicos: O GATS mostrou as maiores melhorias (+36,7%) em tarefas de codificação, navegação web e horizonte profundo em comparação ao LATS.

Estudos de Ablação

Orçamento de Busca: O desempenho saturou com um orçamento de $b=10$ ; aumentar além disso proporcionou retornos decrescentes.
Camadas do Modelo de Mundo: Remover L1 ou L3 individualmente não impactou as taxas de sucesso nas tarefas sintéticas onde a L2 forneceu cobertura suficiente, validando a degradação graciosa do sistema. Em projeções de domínio aberto, espera-se que a L3 (LLM) lide com cerca de 10% das ações novas.

Significância e Alegações

O artigo argumenta que a busca sistemática com modelos de mundo aprendidos pode superar substancialmente a exploração guiada por LLM para o planejamento de agentes. A principal significância do GATS reside em sua capacidade de:

Eliminar Custos de Inferência de LLM em Tempo de Execução: Ao fazer o cache das predições e confiar em camadas simbólicas/aprendidas, o GATS remove o gargalo computacional das chamadas repetidas de LLM.
Garantir Reprodutibilidade: A natureza determinística do modelo de mundo em camadas e da busca UCB1 elimina a variância estocástica inerente à amostragem de LLM.
Lidar com Planejamento Complexo: O framework navega com sucesso por caminhos ramificados, becos sem saída e dependências de longo horizonte onde métodos puramente baseados em LLM (ReAct) e busca em árvore pesada em LLM (LATS) falham ou performam abaixo do esperado.

Os autores posicionam o GATS como uma solução otimizada para domínios onde a semântica das ações pode ser formalizada (ex: APIs, uso de ferramentas estruturadas), oferecendo um caminho para agentes autônomos mais eficientes e confiáveis. Eles reconhecem que em domínios abertos com efeitos de ação desconhecidos, a dependência da camada L3 aumentaria, reduzindo, mas não eliminando, a vantagem de eficiência sobre o LATS.