Tree of Thoughts: Resolució Deliberada de Problemes amb Cerca de LLM

Després de dedicar les darreres dues entrades als agents que s'autocorregeixen mitjançant la reflexió (Reflexion) i la crítica interactiva amb eines (CRITIC), he volgut fer un pas enrere i analitzar un enfocament més estructural: i si l'agent mai no es comprometés a un sol camí de raonament d'entrada? Tree of Thoughts (ToT) de Yao et al. (NeurIPS 2023) proposa precisament això: un marc de cerca on l'LLM explora un espai ramificat de passos de raonament intermedis en lloc d'una sola cadena lineal. L'he llegit ara perquè representa la formulació més clara de cerca deliberada per al raonament de LLM, i la cerca deliberada és el que es necessita quan un sol pas intermedi incorrecte en un càlcul financer pot corrompre silenciosament tot el procés posterior.

L'article

Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao i Karthik Narasimhan presenten Tree of Thoughts com una generalització del prompting de cadena de pensament (chain-of-thought). El moviment clau és tractar els passos de raonament intermedis com a "pensaments" —unitats de text coherents que es poden avaluar de manera independent— i organitzar-los en un arbre en lloc d'una cadena. A cada node, el model genera múltiples pensaments candidats, avalua cadascun d'ells (mitjançant una crida a l'LLM independent que puntua els estats com a "segur / potser / impossible") i després aplica un algoritme de cerca estàndard (BFS o DFS) per recórrer l'arbre. Si una branca sembla morta, el model pot podar-la o fer retrocés (backtrack), una cosa que ni CoT ni CoT-SC poden fer.

L'article avalua el mètode en tres tasques: el Joc del 24 (combinar quatre números per arribar a 24 mitjançant l'aritmètica), l'Escriptura Creativa (produir un passatge coherent utilitzant quatre finals de frase aleatoris) i els Mini Mots Encreuats (resoldre un trencaclosques de 5×5). Totes tres requereixen un raonament que es pot beneficiar de l'exploració i el retrocés, que és precisament l'escenari per al qual els autors l'han dissenyat.

Idees clau

• Al Joc del 24, el ToT amb una amplada de feix (beam width) b=5 aconsegueix un 74% d'èxit, davant del 4% del GPT-4 amb CoT estàndard i el 9% del CoT-SC amb 100 mostres. Aquesta diferència és sorprenent.
• El GPT-3.5 + ToT arriba només al 19% en la mateixa tasca; el benefici del mètode depèn totalment del model. La qualitat de la generació de pensaments del GPT-4 és el que impulsa la major part del guany: la generació amb GPT-4 + l'avaluació amb GPT-3.5 aconsegueix un 64%, mentre que la generació amb GPT-3.5 + l'avaluació amb GPT-4 només arriba al 31%.
• Per a l'Escriptura Creativa, el ToT puntua 7,56 enfront del 6,93 del CoT en una escala de coherència del GPT-4, i els anotadors humans prefereixen els resultats del ToT en 41/100 casos davant del 21/100 del CoT.
• Mini Mots Encreuats: el ToT aconsegueix una precisió a nivell de paraula del 60% (CoT: 40,6%, IO: 15,6%), però només resol 4 de cada 20 jocs complets (20%). La bretxa entre l'èxit a nivell de paraula i a nivell de joc revela que, fins i tot amb el retrocés, la satisfacció de restriccions globals continua sent difícil.
• El pas d'avaluació és, en si mateix, una crida a l'LLM. En els mots encreuats, l'article assenyala que els avaluadors de vegades consideren "impossibles" estats parcials correctes a causa d'un vocabulari poc familiar, un mode de fallada en cadena on els errors de l'avaluador enverinen la cerca.
• Cost de computació: el ToT costa aproximadament 0,74 $ per cas al Joc del 24, enfront dels 0,47 $ de la millor de 100 CoT. Els propis autors adverteixen que per a tasques que el GPT-4 ja gestiona bé, la despesa addicional no val la pena.

Què es manté dempeus — i què no

El resultat principal —que la cerca en arbre sobre pensaments intermedis supera massivament la CoT seqüencial en tasques que requereixen retrocés— és real i reproduïble. La diferència del 74% vs 4% al Joc del 24 no és soroll. L'explicació és mecànicament sòlida: una sola equació intermèdia dolenta en CoT fa que la resta de la cadena caigui pel precipici, mentre que el ToT pot podar aquesta branca i provar una descomposició diferent.

El que trobo menys convincent és la pretensió de generalització. Totes tres tasques d'avaluació són relativament sintètiques: un trencaclosques matemàtic, una proposta d'escriptura creativa amb restriccions estructurals i un joc de paraules. Cap d'elles s'assembla als problemes oberts i ambigus que apareixen en els fluxos de treball financers de producció. Els autors també avaluen només el GPT-4 (i el GPT-3.5 com a ablació), de manera que no sabem com es comporta el ToT amb models més petits o ajustats (fine-tuned), i la xifra del 19% per al GPT-3.5 suggereix que la resposta és "no gaire bé".

La fallada en els mots encreuats a nivell de joc (20% malgrat el 60% de precisió en paraules) apunta a un problema més profund: el ToT és una cerca local guiada per un avaluador local. No manté un model de restriccions globals, que és precisament el que es necessita per a problemes on les interaccions entre subsolucions són denses. L'article posterior Graph of Thoughts (Besta et al., AAAI 2024) fa explícita aquesta crítica i demostra una millora de qualitat del 62% respecte al ToT en tasques d'ordenació, reduint el cost en més d'un 31%, permetent que els pensaments es fusionin i formin cicles en lloc d'estar limitats a un arbre.

Finalment, l'estructura de costos importa en la pràctica. Amb b=5 i crides repetides a l'avaluador, el ToT és aproximadament entre 15 i 20 vegades més car en crides a l'API que una sola passada de CoT. Per a aplicacions sensibles a la latència o al cost, això no és trivialment acceptable.

Per què això és important per a la IA financera

La resposta sincera és: el ToT és més rellevant per a una petita part de l'espai de problemes de Beancount, però aquesta part és real.

La tasca financera canònica on vull retrocés és la classificació de comptes en diversos passos amb transaccions ambigües. Quan un LLM està assignant un extracte bancari importat a un pla de comptes, una sola assignació incorrecta al principi de la cadena (per exemple, tractar el desemborsament d'un préstec com a ingressos) pot derivar en una comprovació de saldo errònia diversos passos després. En un agent CoT, quan falla el saldo, el model no té cap mecanisme per revisar la classificació original. Un agent ToT podria retrocedir fins a aquell node i provar Liabilities:Loans en el seu lloc.

De la mateixa manera, l'optimització fiscal durant tot un any fiscal és un problema genuí de cerca en arbre: desglossar deduccions vs. aplicar la deducció estàndard, planificar la realització de guanys de capital, agrupar contribucions benèfiques. Aquestes decisions interactuen de forma no lineal, i cal avaluar múltiples branques abans de decidir-se. L'estructura BFS/DFS del ToT s'adapta naturalment a aquesta estructura.

En el que el ToT no ajuda és en el cas dominant a Beancount: l'entrada i conciliació de transaccions rutinàries. Per a una transacció que té una contrapartida clara al llibre major, la CoT + PAL (delegar l'aritmètica a un intèrpret de codi) és més ràpida, barata i ja és prou precisa. Aplicar el ToT a la classificació de expenses:groceries és com fer servir un mall per a una xinxeta.

La preocupació més urgent per a la seguretat de l'escriptura de dades és el problema de la fiabilitat de l'avaluador. Si l'avaluador de l'estat també és un LLM, es pot equivocar; i les avaluacions errònies no només frenen la cerca, sinó que poden podar camins correctes. Qualsevol agent financer de producció que utilitzi ToT necessitaria un oracle extern (una comprovació de saldo, un validador d'esquema, un motor de regles) per actuar com a avaluador, no una altra crida a l'LLM.

Què llegir a continuació

• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., AAAI 2024) — arXiv:2308.09687. Estén el ToT d'arbres a grafs arbitraris, permetent la fusió de pensaments i bucles de retroalimentació. La afirmació de reducció de costos (>31%) és directament rellevant si es vol un raonament basat en cerca sense la càrrega del ToT.
• Large Language Models Cannot Self-Correct Reasoning Yet (Huang et al., ICLR 2024) — arXiv:2310.01798. Un contrapunt crític: sense retroalimentació externa, l'autocorrecció intrínseca degrada el rendiment del raonament. Això qüestiona la hipòtesi que l'avaluador basat en LLM del ToT sigui prou fiable per guiar la cerca.
• RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation (arXiv:2409.09584) — aplica MCTS en lloc de BFS/DFS a la cerca de pensaments, amb la retroalimentació de l'execució com a oracle extern. L'escenari de generació de codi és estructuralment similar a l'escriptura en el llibre major: es té una veritat verificable (s'executa el codi? passa la comprovació de saldo?), que és exactament on les simulacions de Monte Carlo aporten valor.