o problema
Um language model gera token por token, da esquerda para a direita, e cada token escolhido é definitivo. Isso funciona para escrever texto e funciona surpreendentemente bem para raciocinar, desde que o raciocínio seja uma linha reta: chain-of-thought só insere passos intermediários em linguagem no meio do caminho, mas continua sendo uma sequência amostrada para a frente, sem volta.
Existem tarefas em que a primeira decisão é a que mata. No jogo do 24 — quatro números, as quatro operações, chegar a 24 — o GPT-4 com CoT resolve 4,0% dos casos, pior que os 7,3% do prompt direto de input-output. A análise de erro explica: em cerca de 60% das amostras, o passo inicial já era irrecuperável, o equivalente às três primeiras palavras geradas. Self-consistency não conserta isso; amostrar cem cadeias e votar na resposta mais frequente sobe para 9,0%, porque a votação só age no fim e nenhuma das cadeias explorou alternativas por dentro. É a diferença que a literatura de cognição chama de Sistema 1 e Sistema 2: associação rápida contra deliberação com lookahead e backtracking.
a ideia
Newell, Shaw e Simon descreveram resolução de problemas nos anos 1950 como busca num espaço combinatório representado por uma árvore: nós são soluções parciais, ramos são operadores. O Tree of Thoughts pega essa formulação e usa o próprio modelo para preencher as duas peças que faltavam.
Um nó é um estado s = [x, z1..zi]: o enunciado mais os pensamentos até ali. Um pensamento é um pedaço coerente de linguagem — uma equação intermediária, uma palavra do cruzadinha, um plano de redação. Grande o bastante para ser avaliado, pequeno o bastante para o modelo gerar variantes diversas. A novidade está na heurística: em busca clássica ela é programada (Deep Blue) ou aprendida (AlphaGo); aqui o modelo lê o estado parcial e dá uma nota em linguagem. Nenhum treino, nenhum modelo de valor extra.
como funciona
Uma instância de ToT responde quatro perguntas, e cada uma é um knob independente.
Decomposição. Quantos passos e de que tamanho. Jogo do 24: três equações intermediárias. Redação criativa: um passo, o plano. Cruzadinha 5x5: de 5 a 10 palavras.
Gerador G(pθ, s, k). Duas estratégias. Amostrar k pensamentos i.i.d. de um prompt de CoT, bom quando o espaço é rico e a diversidade vem de graça (redação). Ou um propose prompt, que produz os k candidatos de uma vez no mesmo contexto — melhor quando o espaço é apertado e amostras independentes se repetiriam.
Avaliador V(pθ, S). Também duas. Valorar cada estado sozinho: no jogo do 24, o prompt pede “sure/maybe/impossible” quanto a chegar em 24, misturando lookahead curto (5, 5, 14 dá 24) com senso comum (1, 2, 3 é pequeno demais). Ou votar entre estados, comparando-os num único prompt — o que se usa quando não dá para atribuir nota absoluta, como coerência de um texto. Nos dois casos vale amostrar o julgamento várias vezes e agregar.
Busca. BFS mantém os b melhores estados por passo; usada no jogo do 24 com b=5 e T=3. DFS desce pelo candidato mais promissor e poda a subárvore quando o avaliador considera o estado impossível, voltando ao pai; usada na cruzadinha, com limite de 100 passos.
Nessa moldura, IO, CoT, CoT-SC e self-refinement são casos particulares — árvores de profundidade ou largura degeneradas.
o que isso custou
Tokens. No jogo do 24, o ToT consome 5,5 mil tokens de saída por problema, na mesma ordem das cem tentativas de CoT (6,7 mil), e custa US$ 0,74 contra US$ 0,47 — para 74% contra 49%. Na redação criativa é cerca de 5x o custo do CoT. Os autores estimam que ToT pede de 5 a 100 vezes mais tokens gerados.
E só vale onde o CoT trava. Com ToT zero-shot, GSM8K vai de 86 para 90 e StrategyQA de 82 para 83 — o modelo já resolvia. O paper admite que testa apenas três tarefas inventadas para desafiar o GPT-4, e que o método depende de um modelo forte: o mesmo jogo do 24 com GPT-3.5 dá 19%.
A heurística também erra para o lado errado. Na cruzadinha, o avaliador às vezes poda jogos que estavam resolvidos, porque não reconhece palavras raras (“agend” é forma obsoleta de “agendum”, e o GPT-4 acha que é erro de digitação). Tirar a poda piora no geral, mas encontra a solução de três jogos que a versão com poda não alcança. E sair do estado escolhido pela heurística para o melhor estado visitado sobe de 4 para 7 jogos em 20: a saída é pior que a busca.
onde isso aparece hoje
O paper deixa A* e MCTS explicitamente para trabalho futuro, e cita RAP como trabalho concorrente que já fazia MCTS sobre raciocínio. O que sobreviveu foi menos a árvore específica e mais o vocabulário: separar geração de pensamento, avaliação de estado e algoritmo de busca em três componentes trocáveis, todos rodando por prompt em cima de um modelo pronto. É por isso que ToT vive na camada de aplicação, como loop de agente, e não dentro do modelo.
O achado sobre o gargalo é o mais reaproveitável. GPT-4 gerando com GPT-3.5 avaliando dá 64%; GPT-3.5 gerando com GPT-4 avaliando, 31%. Julgar é mais barato que propor — a base do padrão de usar um modelo pequeno como crítico e reservar o grande para gerar.