Tree of Thoughts — Come i LLM Imparano a Esplorare Spazi di Soluzioni

Cos'è: Tree of Thoughts (ToT) è un framework di prompting introdotto da Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao e Karthik Narasimhan (Princeton University e Google DeepMind) a maggio 2023. Estende il Chain-of-Thought (Wei et al., 2022) da una sequenza lineare di passaggi intermedi a una struttura ad albero in cui ogni nodo rappresenta un "thought" — uno stato intermedio nel ragionamento — e si esplorano più rami in parallelo, valutandone la promettività via voting o scoring del LLM stesso. Su problemi di ricerca strutturata come Game of 24 la performance balza da 4% (CoT con GPT-4) a 74% (ToT con GPT-4), un miglioramento di 18x al costo di un consumo computazionale 100x+ superiore. È il precursore concettuale dell'inference-time compute che ha portato a OpenAI o1.

Il limite del Chain-of-Thought: lineare e irreversibile

Il Chain-of-Thought prompting (Wei et al., NeurIPS 2022) ha dimostrato che permettere al LLM di scrivere passaggi intermedi prima della risposta finale migliora drasticamente il ragionamento. Su GSM8K (problemi matematici elementari), CoT porta PaLM 540B da 17.9% a 56.9% di accuratezza. Ma il CoT ha due limiti strutturali. Primo, è lineare: il modello produce una singola catena di pensiero da sinistra a destra, senza possibilità di esplorare alternative. Secondo, è irreversibile: una volta che il modello commette un errore al passo 3, tutti i passi successivi ereditano l'errore e non c'è meccanismo di backtracking.

Yao et al. osservano che la cognizione umana su problemi complessi non funziona così. Risolvendo un puzzle, un'equazione difficile o pianificando una strategia, una persona genera ipotesi, le valuta, scarta quelle non promettenti, torna a punti di scelta precedenti, prova rami alternativi. È un processo di ricerca su uno spazio di soluzioni, non un'unica passata lineare. ToT impianta esplicitamente questa struttura di ricerca sopra il LLM, usando il modello stesso sia come generatore di stati che come valutatore.

Quattro componenti: thought, generation, evaluation, search

ToT è specificato in quattro elementi configurabili per task. Primo, thought decomposition: si definisce cos'è un "thought" — un singolo passo intermedio. Per Game of 24 (combinare 4 numeri con operazioni base per ottenere 24), un thought è una singola operazione che combina due numeri intermedi. Per Creative Writing un thought è un paragrafo di piano narrativo. Per Mini Crosswords è una candidata per una parola dell'incrocio. La granularità del thought è cruciale: troppo fine moltiplica i nodi e i costi, troppo grossa elimina i vantaggi della struttura ad albero.

Secondo, thought generator: data una posizione corrente nell'albero, il LLM viene proposto a generare k thought candidati per il passo successivo. Tipicamente k è 5-10. Si può fare via "propose" (un prompt che chiede al modello di elencare candidate proposte) o via "sample" (k campionamenti indipendenti dal modello con temperatura alta). Terzo, state evaluator: un'altra chiamata al LLM valuta ogni stato candidato. Yao et al. propongono due varianti: "value" (chiedere al LLM di assegnare un punteggio numerico) e "vote" (presentare gli stati candidati al LLM e chiedere quale è più promettente).

Quarto, search algorithm: una procedura di ricerca classica orchestra l'esplorazione. ToT supporta BFS (mantieni i migliori b stati a ogni livello, espandi tutti) e DFS (espandi in profondità con backtracking quando il valutatore segnala stato non promettente). La profondità massima dell'albero è limitata dal task. È esattamente l'inquadramento dell'AI classica della pianificazione e dei giochi: il LLM è insieme la policy (genera mosse) e la value function (valuta posizioni), il search algorithm è esterno.

Risultati: Game of 24, Creative Writing, Crosswords

I tre task del paper esplorano regimi diversi di ragionamento. Game of 24 è puramente combinatorio: dati 4 numeri, costruire un'espressione aritmetica che valga 24. Con GPT-4 e CoT standard la pass rate è solo il 4%. Con ToT (b=5, profondità 3, BFS) sale al 74% — un miglioramento di quasi 20x. È il risultato più citato del paper perché la natura del task (search ben definita) è ideale per ToT.

Creative Writing chiede di scrivere un breve testo coerente con vincoli su come deve concludersi ogni paragrafo. Qui il guadagno è più modesto ma reale: ToT migliora la coerenza valutata da GPT-4-as-judge da 6.19/10 (CoT) a 7.56/10 (ToT). Mini Crosswords richiede di completare un crucipuzzle 5x5 dati gli indizi: CoT risolve il 14% delle parole, ToT (con DFS e backtracking) il 60%. L'efficacia di ToT è maggiore proprio sui task con struttura di ricerca evidente.

Il costo: inference-time compute moltiplicato per cento

ToT ha un prezzo computazionale notevole che il paper riporta esplicitamente. Risolvere un singolo problema di Game of 24 con CoT costa circa 1 chiamata GPT-4. Con ToT richiede ~100 chiamate (b=5 candidati × 3 livelli di profondità × valutazioni × multiple expansions con backtracking). Su Creative Writing il rapporto è simile. È un cambio paradigmatico: non si paga più solo per la dimensione del modello, si paga anche per il tempo di ragionamento al query time.

Questa è esattamente l'idea che OpenAI ha portato a maturazione un anno dopo. OpenAI o1 (settembre 2024) e successori non usano ToT esplicitamente come framework esterno, ma internalizzano il concetto: il modello genera lunghe catene di ragionamento, valuta percorsi, fa backtracking, tutto come parte del proprio decoding. La scaling law dichiarata da OpenAI per o1 — performance migliora come funzione del compute di inferenza — è la formalizzazione industriale del tradeoff che Yao et al. hanno per primi misurato in modo controllato. ToT è anche stato implementato in LangGraph e LlamaIndex come pattern di orchestrazione, e ha generato varianti come Graph of Thoughts (Besta et al., 2023), Algorithm of Thoughts (Sel et al., 2023) e Forest of Thoughts.

---