Phase 14 - Lesson 04

Tree of Thoughts e LATS: Busca Deliberada

Uma única trajetória de chain-of-thought não tem espaço para retroceder (backtrack). O ToT (Yao et al., 2023) transforma o raciocínio em uma árvore com autoavaliação em cada nó. O LATS (Zhou et al., 2024) unifica o ToT com ReAct e Reflexion sob Monte Carlo Tree Search. O Game of 24 vai de 4% (CoT) para 74% (ToT); o LATS atinge 92,7% de pass@1 no HumanEval.

Tipo: Build Idiomas: Python (stdlib) Pré-requisitos: Phase 14 · 01 (Agent Loop), Phase 14 · 03 (Reflexion) Tempo: ~75 minutos

Objetivos de Aprendizado

• Estruturar o raciocínio como busca: nós são "pensamentos" (thoughts), arestas são "expansões" e o valor é "o quão promissor" o nó é.
• Implementar uma busca em árvore BFS no estilo ToT usando apenas a biblioteca padrão (stdlib) com pontuação de autoavaliação.
• Estender para um loop MCTS LATS simplificado com as etapas select / expand / simulate / backpropagate.
• Decidir quando a busca vale o multiplicador de tokens (Game of 24, geração de código) e quando uma única trajetória é suficiente (Q&A simples).

O Problema

O chain-of-thought é um caminho linear. Se o primeiro passo estiver errado, todos os passos subsequentes funcionarão a partir de uma premissa ruim. No Game of 24 (use quatro dígitos com + − × ÷ para resultar em 24), o CoT com GPT-4 alcança apenas 4% de acurácia. O modelo escolhe a subexpressão errada logo no início e não consegue se recuperar.

O que o raciocínio precisa é da capacidade de propor múltiplos candidatos, avaliá-los, escolher os mais promissores e retroceder quando encontrar caminhos sem saída. Isso é busca. Tree of Thoughts e LATS são as duas formulações canônicas.

O Conceito

Tree of Thoughts (Yao et al., NeurIPS 2023)

Cada nó é um passo intermediário coerente ("um pensamento" ou "thought"). Cada nó pode se expandir para K pensamentos filhos. O LLM autoavalia cada nó com um prompt de pontuação. A busca explora a árvore — via BFS, DFS ou beam search.

                     (root: "find 24 from 4 6 4 1")
                    /               |            \
           ("6 - 4 = 2")    ("4 + 1 = 5")    ("4 * 6 = 24")  <- Score: HIGH
              /   \              |                  |
          ...    ...          ...                finish

A autoavaliação é a engrenagem principal. O artigo apresenta três variantes: classificação em sure / likely / impossible, pontuação numérica de 1..10 e votação entre candidatos. Todas as três superam o CoT substancialmente no Game of 24 (4% -> 74% com GPT-4).

LATS (Zhou et al., ICML 2024)

O LATS unifica ToT, ReAct e Reflexion sob o MCTS. O LLM desempenha três papéis:

• Policy: propor candidatas a próximas ações (estilo ReAct).
• Value function: pontuar uma trajetória parcial (autoavaliação no estilo ToT).
• Self-reflector: em caso de falha, escrever uma reflexão em linguagem natural (estilo Reflexion) e usá-la para orientar rollouts futuros.

O feedback do ambiente (observações) é integrado à value function para que a busca seja informada por resultados reais de ferramentas, e não apenas por opiniões do modelo. Resultados na época de publicação do artigo: 92,7% de pass@1 no HumanEval com GPT-4 (SOTA), média de 75,9 no WebShop com GPT-3.5 (próximo ao ajuste fino baseado em gradiente).

MCTS Simplificado

Quatro fases por iteração:

1. Select — caminhar da raiz até uma folha usando UCT (upper confidence bound for trees).
2. Expand — gerar K filhos por meio da policy.
3. Simulate — realizar um rollout a partir de um filho usando a policy e pontuar a folha com a value function (ou recompensa do ambiente).
4. Backpropagate — atualizar a contagem de visitas e as estimativas de valor ao longo do caminho de volta.

Fórmula do UCT: Q(s, a) + c * sqrt(ln N(s) / N(s, a)). O primeiro termo representa exploitation (aproveitamento); o segundo representa exploration (exploração). Ajuste c por tarefa.

A Realidade dos Custos

A busca consome uma quantidade explosiva de tokens. O ToT no Game of 24 usa de 100 a 1000 vezes mais tokens do que o CoT. O LATS segue uma linha semelhante. Isso não é de graça; reserve a busca para:

• Tarefas onde uma única trajetória é comprovadamente insuficiente (Game of 24, código complexo).
• Tarefas onde o tempo de execução é menos importante do que a corretude.
• Tarefas com uma value function barata e confiável (testes unitários para código, alvo explícito para matemática).

Se a sua tarefa tem uma única resposta correta e um avaliador com ruído, a busca frequentemente piora as coisas — ela encontra uma resposta errada com "boa pontuação".

Posicionamento em 2026

A maioria dos agentes em produção não executa LATS. Eles rodam ReAct com verificação baseada em ferramentas (CRITIC, Lesson 05). A busca aparece em nichos especializados:

• Agentes de codificação que executam testes como value function (estilo HumanEval).
• Agentes de pesquisa profunda (deep-research) que exploram múltiplos caminhos de consulta.
• Workflows focados em planejamento dentro de subgrafos do LangGraph.

O AlphaEvolve (Lesson 11) é o extremo de 2025: busca evolucionária sobre código, fitness verificável por máquina e ganhos de fronteira (primeira melhoria em multiplicação de matrizes 4x4 em 56 anos).

Build It

code/main.py implementa:

• Um BFS ToT minúsculo em uma tarefa estilizada de "escolha de operações aritméticas".
• Um loop MCTS LATS simplificado na mesma tarefa (Select / Expand / Simulate / Backpropagate) com seleção baseada em UCT.
• Uma value function que compõe uma pontuação simbólica somada a uma pontuação de autoavaliação.

Run it:

python3 code/main.py

O trace mostra o ToT expandindo três candidatos por nó com BFS, em comparação com o LATS convergindo para o melhor rollout via MCTS. As contagens de tokens são exibidas para ambos.

Use It

O LangGraph fornece exploração no estilo ToT como padrões de subgrafo; o blog da equipe do LangChain sobre LATS (maio de 2024) é o tutorial de referência. O LlamaIndex fornece um agente TreeOfThoughts. Para a maioria dos agentes de produção em 2026, esse padrão reside por trás de uma validação if task_complexity > threshold: use_search() — veja o padrão avaliador-otimizador na Lesson 05.

Ship It

outputs/skill-search-policy.md seleciona entre ReAct linear, ToT, LATS e busca evolucionária considerando o formato da tarefa, orçamento e fidelidade do avaliador.

Exercícios

1. Execute o LATS simplificado com UCT c=0.1 vs c=2.0. O que muda no trace?
2. Substitua a value function por um pontuador com mais ruído (adicione uma variação aleatória). O MCTS ainda encontra a melhor folha? Qual é a relação sinal-ruído mínima que ele tolera?
3. Implemente o ToT com beam search (mantenha os top-k em cada nível) e compare com a busca em largura (BFS). Qual é melhor em um orçamento de tokens limitado?
4. Leia a Seção 5.1 do LATS. Reproduza a contagem de trajetória do HumanEval: quantos rollouts são necessários para atingir o pass@1 relatado?
5. Leia a discussão do artigo do LATS sobre "quando o LATS ajuda menos". Escreva uma regra de decisão de um parágrafo mapeando o formato da tarefa para a estratégia de busca.

Termos-Chave

Leituras Adicionais

• Yao et al., Tree of Thoughts (arXiv:2305.10601) — the canonical paper
• Zhou et al., LATS (arXiv:2310.04406) — MCTS with Reflexion feedback
• LangGraph overview — subgraph patterns for search
• AlphaEvolve (arXiv:2506.13131) — evolutionary search with programmatic evaluators