Tree of Thoughts (ToT)

Tree of Thoughts (ToT) é uma estrutura de engenharia de prompts em que um grande modelo de linguagem (LLM) resolve um problema ao pesquisar uma árvore de soluções parciais. Em cada passo, o modelo propõe vários passos seguintes candidatos, chamados pensamentos, avalia a promissoridade de cada estado resultante e um algoritmo de pesquisa decide que ramos expandir, manter ou abandonar. Enquanto o prompting com cadeia de pensamento se compromete com uma linha de raciocínio desde o primeiro token, o ToT pode antecipar e retroceder. Shunyu Yao e colegas da Universidade de Princeton e da Google DeepMind apresentaram-no em Tree of Thoughts: Deliberate Problem Solving with Large Language Models, apresentado na NeurIPS 2023; no mesmo mês, Jieyi Long propôs um sistema semelhante de pesquisa em árvore para resolver Sudoku com um LLM. No desafio Game of 24, o ToT aumentou a taxa de sucesso do GPT-4 de 4%, com prompting de cadeia de pensamento, para 74%.

Como funciona o Tree of Thoughts#

Yao et al. definem o ToT através de quatro opções de conceção:

• Decomposição do pensamento: O que constitui um passo. No Game of 24, um pensamento é uma equação; na geração de texto criativo, é um plano para o texto; nas palavras cruzadas, é uma palavra a colocar.
• Gerador de pensamentos: Como são produzidos os candidatos. O modelo pode amostrar vários pensamentos de forma independente, o que é adequado para passos abertos, ou propor uma lista de opções distintas num único prompt, evitando duplicados quando as escolhas são limitadas.
• Avaliador de estados: Como se avalia o progresso. O modelo avalia cada estado individualmente, por exemplo, como «certo», «talvez» ou «impossível» de alcançar o objetivo, ou vota no melhor de vários estados. Estas avaliações servem de heurística de pesquisa, uma função geralmente desempenhada por uma função de pontuação escrita manualmente na pesquisa clássica.
• Algoritmo de pesquisa: Como se explora a árvore. A pesquisa em largura mantém os b melhores estados em cada nível; a pesquisa em profundidade segue o ramo mais promissor, poda os estados rejeitados pelo avaliador e retrocede.

Exemplo: Game of 24#

O Game of 24 apresenta quatro números que têm de ser combinados com +, -, x e / para obter 24, utilizando cada número uma vez. O ToT divide a solução em três passos, cada um consistindo numa equação que combina dois números. Para a entrada 4 9 10 13, um prompt de proposta apresenta candidatos como:

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

O prompt de avaliação pergunta, então, se cada conjunto de números restantes ainda pode chegar a 24. «4 4 10» é uma opção certa, uma vez que (10 - 4) x 4 = 24; o mesmo se aplica a «6 9 13», uma vez que (13 - 9) x 6 = 24. Já «10 13 13» e «9 10 52» são impossíveis, pelo que a pesquisa expande apenas os dois primeiros ramos. Seguindo o primeiro, obtém-se 10 - 4 = 6 (restam: 4 6) e, depois, 4 x 6 = 24.

Nas experiências do artigo com 100 desafios difíceis, a pesquisa em largura manteve os 5 melhores estados em cada passo, avaliando cada estado três vezes. O ToT com GPT-4 resolveu 74% dos desafios, em comparação com 7,3% com prompting direto, 4,0% com cadeia de pensamento e 9,0% com cadeia de pensamento e consistência própria. Mesmo a melhor de 100 cadeias de pensamento amostradas atingiu apenas 49%, e o ToT que mantinha um único estado por passo atingiu 45%.

Onde se enquadra o Tree of Thoughts#

O ToT é útil em problemas nos quais as escolhas iniciais condicionam as seguintes e é difícil corrigir um primeiro passo errado: quebra-cabeças, planeamento e problemas matemáticos com várias etapas. Em mini-palavras cruzadas de 5x5, o ToT em profundidade com poda preencheu corretamente 60% das palavras e resolveu 4 dos 20 desafios. O custo é computacional: cada nível da árvore requer várias chamadas de geração e avaliação, pelo que uma única resposta pode exigir dezenas de chamadas ao modelo ou mais, além de muitos mais tokens do que uma cadeia, com uma latência de inferência correspondente.

O mesmo ciclo de gerar, avaliar e expandir ocorre numa escala muito maior na pesquisa automatizada de experiências, como o ajuste de hiperparâmetros. No AutoTrain da Ultralytics Platform, o Ask AI pode treinar vários modelos Ultralytics YOLO que diferem numa única configuração, como tamanhos de imagem de 640, 800 e 960, comparar as execuções concluídas pela mAP50-95 de validação e propor a experiência seguinte com base no melhor resultado.

Tree of Thoughts e métodos relacionados#

• Prompting com cadeia de pensamento: Um único percurso de raciocínio, equivalente a uma árvore com um ramo por nível.
• Prompting ReAct: Intercala o raciocínio com ações num ambiente externo, como pesquisas ou chamadas de ferramentas, e avança com base nos resultados dessas ações. O ToT pesquisa entre os pensamentos candidatos do próprio modelo.
• Consistência própria: Amostra várias cadeias completas e decide por maioria as respostas finais, sem avaliar os passos parciais durante o processo.
• Graph of Thoughts: Generaliza a árvore para um grafo no qual os pensamentos também podem ser combinados e refinados, e relatou uma qualidade de classificação 62% superior à do ToT com um custo mais de 31% menor.
• Busca em árvore de Monte Carlo (MCTS): O algoritmo de busca por trás do AlphaGo, que equilibra a exploração de novos ramos com o aproveitamento dos bons e pode substituir a busca em largura ou em profundidade por pensamentos.
• Modelos de raciocínio: Treinados com aprendizagem por reforço para gerar longas cadeias de raciocínio em uma única geração, enquanto o ToT obtém ramificações e retrocessos de um programa de busca externo em torno de um modelo comum.