Tree of Thoughts (ToT)

Tree of Thoughts (ToT) è un framework di prompt engineering in cui un modello linguistico di grandi dimensioni (LLM) risolve un problema esplorando un albero di soluzioni parziali. A ogni passaggio, il modello propone diversi possibili passaggi successivi, chiamati pensieri, valuta quanto sia promettente ogni stato risultante e un algoritmo di ricerca decide quali rami ampliare, mantenere o abbandonare. Mentre il prompting a catena di ragionamento si impegna su un'unica linea di ragionamento fin dal primo token, ToT può guardare avanti e tornare sui propri passi. Shunyu Yao e i suoi colleghi della Princeton University e di Google DeepMind l'hanno presentato in Tree of Thoughts: Deliberate Problem Solving with Large Language Models, presentato a NeurIPS 2023; nello stesso mese, Jieyi Long ha proposto un sistema simile basato sulla ricerca ad albero per risolvere il sudoku con un LLM. Nel rompicapo Game of 24, ToT ha portato il tasso di successo di GPT-4 dal 4% ottenuto con il prompting a catena di ragionamento al 74%.

Come funziona Tree of Thoughts#

Yao et al. definiscono ToT attraverso quattro scelte progettuali:

• Scomposizione del pensiero: Che cosa costituisce un passaggio. In Game of 24, un pensiero è un'equazione; nella generazione di testo creativo, un piano per il brano; in un cruciverba, una parola da inserire.
• Generatore di pensieri: Come vengono prodotte le opzioni. Il modello campiona diversi pensieri indipendenti, una scelta adatta ai passaggi aperti, oppure propone in un unico prompt un elenco di opzioni distinte, evitando duplicati quando le possibilità sono limitate.
• Valutatore dello stato: Come viene giudicato il progresso. Il modello valuta ogni stato singolarmente, ad esempio come "sicuro", "possibile" o "impossibile" da ricondurre all'obiettivo, oppure vota per il migliore tra più stati. Queste valutazioni fungono da euristica di ricerca, un ruolo che nella ricerca classica è svolto da una funzione di punteggio scritta a mano.
• Algoritmo di ricerca: Come viene esplorato l'albero. La ricerca in ampiezza mantiene i b stati migliori a ogni livello; la ricerca in profondità segue il ramo più promettente, elimina gli stati che il valutatore esclude e torna indietro.

Esempio: Game of 24#

Game of 24 fornisce quattro numeri da combinare con +, -, x e / per ottenere 24, usando ogni numero una sola volta. ToT suddivide la soluzione in tre passaggi, ciascuno dei quali è un'equazione che combina due numeri. Per l'input 4 9 10 13, un prompt di proposta elenca opzioni come:

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)

Il prompt di valutazione chiede poi se ciascun insieme rimanente può ancora arrivare a 24. "4 4 10" è una soluzione sicura, perché (10 - 4) x 4 = 24; lo stesso vale per "6 9 13", perché (13 - 9) x 6 = 24. Invece, "10 13 13" e "9 10 52" sono impossibili, quindi la ricerca amplia solo i primi due rami. Seguendo il primo, si ottiene 10 - 4 = 6 (restano: 4 6), poi 4 x 6 = 24.

Negli esperimenti dell'articolo su 100 partite difficili, la ricerca in ampiezza ha mantenuto i 5 stati migliori per passaggio e ha valutato ogni stato tre volte. ToT con GPT-4 ha risolto il 74% delle partite, contro il 7,3% del prompting diretto, il 4,0% della catena di ragionamento e il 9,0% della catena di ragionamento con autoconsistenza. Anche la migliore tra 100 catene di ragionamento campionate ha raggiunto solo il 49%; ToT, mantenendo un solo stato per passaggio, ha raggiunto il 45%.

Il ruolo di Tree of Thoughts#

ToT è utile per i problemi in cui le prime scelte vincolano quelle successive e un primo passaggio sbagliato è difficile da correggere: rompicapi, pianificazione e matematica a più passaggi. Nei mini cruciverba 5x5, ToT in profondità con potatura ha completato correttamente il 60% delle parole e risolto 4 partite su 20. Il prezzo è il calcolo: ogni livello dell'albero richiede diverse chiamate di generazione e valutazione, quindi una singola risposta può richiedere decine o più chiamate al modello e molti più token di una singola catena, con una corrispondente latenza di inferenza.

Lo stesso ciclo di generazione, valutazione ed espansione compare su scala molto più ampia nella ricerca automatizzata di esperimenti, ad esempio nell'ottimizzazione degli iperparametri. In Ultralytics Platform AutoTrain, Ask AI può addestrare diversi modelli Ultralytics YOLO che differiscono per un'impostazione, come le dimensioni delle immagini di 640, 800 e 960, confrontare le esecuzioni completate in base alla mAP50-95 di convalida e proporre l'esperimento successivo a partire dal risultato migliore.

Tree of Thoughts e metodi correlati#

• Prompting a catena di ragionamento: Un singolo percorso di ragionamento, equivalente a un albero con un solo ramo per livello.
• Prompting ReAct: Alterna il ragionamento alle azioni in un ambiente esterno, come ricerche o chiamate a strumenti, e procede in base ai risultati di tali azioni. ToT esplora i pensieri candidati generati dal modello stesso.
• Autoconsistenza: Campiona diverse catene complete e sceglie le risposte finali a maggioranza, senza valutare i passaggi parziali lungo il percorso.
• Graph of Thoughts: Generalizza l'albero trasformandolo in un grafo in cui i pensieri possono anche essere uniti e perfezionati; ha riportato una qualità di ordinamento superiore del 62% rispetto a ToT, con un costo inferiore di oltre il 31%.
• Ricerca ad albero Monte Carlo (MCTS): L'algoritmo di ricerca alla base di AlphaGo, che bilancia l'esplorazione di nuovi rami con lo sfruttamento di quelli promettenti e può sostituire la ricerca in ampiezza o in profondità sui pensieri.
• Modelli di ragionamento: Addestrati con l'apprendimento per rinforzo per generare lunghe tracce di ragionamento in un'unica generazione; ToT, invece, ottiene ramificazioni e backtracking grazie a un programma di ricerca esterno che opera attorno a un modello standard.