Tree of Thoughts (ToT) (CS)

Tree of Thoughts (ToT) (Strom myšlenek) — je inovativní framework pro řízení uvažování velkých jazykových modelů (LLM), který jim umožňuje provádět vědomé řešení úloh prostřednictvím systematického prozkoumávání mnoha cest uvažování. Koncept byl představen v roce 2023 výzkumníky z Princetonské univerzity a Google DeepMind.

ToT je rozšířením a zobecněním populární techniky „řetězce myšlenek" (Chain of Thought, CoT). Na rozdíl od CoT, kde uvažování představuje jedinou lineární posloupnost kroků, ToT organizuje proces myšlení ve formě stromu, kde každý uzel je mezistav („myšlenka") a větve jsou možné cesty rozvoje uvažování. To umožňuje modelu prozkoumávat několik variant paralelně, hodnotit jejich perspektivnost, vracet se k předchozím krokům při odhalení slepých uliček (backtracking) a provádět vědomou volbu.

Princip fungování

Framework ToT organizuje proces řešení úlohy jako prohledávání stavového stromu. Jeho fungování je založeno na cyklické interakci čtyř klíčových komponent:

1. Dekompozice úlohy na „myšlenky": Původní problém je rozdělen na menší dílčí kroky zvané „myšlenky". Na rozdíl od CoT, kde „myšlenka" je pouze dalším tokenem, v ToT je „myšlenka" sémanticky významnou jednotkou (například rovnice v matematické úloze nebo odstavec v plánu textu), která přibližuje k řešení.

2. Generování myšlenek: V každém kroku pro aktuální stav (uzel stromu) model generuje několik potenciálních následujících „myšlenek" (větví). K tomu se používají dvě strategie:

• Vzorkování (sample): Model nezávisle generuje několik variant pokračování. Vhodné pro kreativní úlohy, kde je užitečné široké spektrum nápadů.
• Návrh (propose): Model postupně generuje varianty, což je efektivnější pro úlohy s omezeným prostorem řešení.

3. Hodnocení stavů: Vygenerované „myšlenky" jsou hodnoceny samotným LLM za účelem určení jejich perspektivnosti. Hodnocení může být číselné (například na škále od 0 do 1) nebo kategoriální („jistě", „možná", „nemožné"). Jde o heuristickou funkci, která směruje prohledávání k perspektivním větvím.

4. Vyhledávací algoritmus: Pro systematické prozkoumávání stromu myšlenek se používají klasické vyhledávací algoritmy:

• Prohledávání do šířky (BFS): Prozkoumává všechny uzly na jedné úrovni, než přejde na další. Zaručuje nalezení nejkratší cesty, ale vyžaduje více paměti.
• Prohledávání do hloubky (DFS): Prozkoumává jednu větev až do konce, než se vrátí a vyzkouší jinou. Je úspornější z hlediska paměti a vhodný pro úlohy s hlubokým, ale ne příliš širokým prostorem prohledávání.

Tento framework napodobuje lidské myšlení při řešení problémů, kombinuje intuitivní generování nápadů (pomocí LLM) s vědomým, systematickým plánováním a procházením variant.

Srovnání s jinými metodami uvažování

ToT ve srovnání s Chain of Thought (CoT)

ToT je přímým zobecněním CoT. Pokud lze CoT představit jako strom s faktorem větvení rovným 1, pak ToT umožňuje prozkoumávat strom s libovolným faktorem větvení. To přináší klíčové výhody:

• Prozkoumávání alternativ: ToT může uvažovat o více cestách řešení, zatímco CoT je omezen na jednu lineární cestu.
• Možnost návratu: ToT umožňuje modelu „vrátit se zpět", pokud se větev uvažování dostala do slepé uličky, což v CoT není možné.
• Globální plánování: ToT umožňuje strategickou volbu na základě hodnocení několika budoucích kroků.

ToT ve srovnání se Self-Consistency

Self-Consistency generuje mnoho nezávislých „řetězců myšlenek" a vybírá nejčastější odpověď hlasováním. Tato metoda zlepšuje spolehlivost CoT, avšak stejně jako CoT neumožňuje prozkoumávat rozvětvenou strukturu řešení. ToT naproti tomu může vykazovat výraznější zlepšení u složitých plánovacích úloh, kde jsou důležité nejen nezávislé pokusy, ale i jejich vzájemné vztahy.

Experimentální výsledky

Autoři ToT prokázali jeho účinnost na třech úlohách vyžadujících netriviální plánování nebo prohledávání.

• Hra 24: Matematická hádanka, kde je třeba získat číslo 24 ze čtyř zadaných čísel pomocí základních aritmetických operací. Standardní prompting s GPT-4 vykázal úspěšnost 7,3 %, Chain of Thought — 4 %. ToT s prohledáváním do šířky (b=5) dosáhl úspěšnosti 74 %, což je 18,5krát lepší než CoT.
• Kreativní psaní: V úloze generování koherentního textu ze čtyř odstavců se zadanými posledními větami získaly texty vytvořené pomocí ToT průměrné skóre koherence 7,56 z 10, zatímco CoT — 6,15. Ve 41 ze 100 srovnání lidé upřednostnili text vygenerovaný ToT, oproti 21 pro CoT.
• Mini křížovky (5x5): ToT správně doplnil 60 % slov, zatímco CoT — pouze 1 %.

Omezení a budoucí směry

Navzdory působivým výsledkům má framework ToT řadu omezení:

• Výpočetní náročnost: ToT vyžaduje výrazně více výpočetních zdrojů (5–100krát více tokenů) než standardní metody, kvůli nutnosti generovat a hodnotit velké množství „myšlenek".
• Složitost implementace: Nasazení ToT vyžaduje značné inženýrské úsilí při vytváření a ladění všech komponent: generátoru myšlenek, hodnotitele stavů a vyhledávacího algoritmu.
• Závislost na kvalitě hodnocení: Účinnost celého frameworku silně závisí na schopnosti LLM adekvátně hodnotit mezilehlé stavy, což není vždy zaručeno.

Budoucí výzkum je zaměřen na zvýšení efektivity, automatizaci optimalizace a integraci ToT s jinými metodami, jako je Reinforcement Learning, za účelem vytvoření inteligentnějších a autonomnějších agentů.

Odkazy

• Oficiální repozitář Tree of Thoughts na GitHubu.
• Tree of Thoughts (ToT) — průvodce na Prompt Engineering Guide.

Literatura

• Yao, S. et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601.
• Wei, J. et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. arXiv:2201.11903.
• Wang, X. et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. arXiv:2203.11171.
• Kojima, T. et al. (2022). Large Language Models are Zero-Shot Reasoners. arXiv:2205.11916.
• Zhang, Z. et al. (2022). Automatic Chain of Thought Prompting in Large Language Models. arXiv:2210.03493.
• Lyu, Q. et al. (2023). Faithful Chain-of-Thought Reasoning. arXiv:2301.13379.
• Ling, Z. et al. (2023). Deductive Verification of Chain of Thought Reasoning. arXiv:2306.03872.
• Yao, S. et al. (2022). ReAct: Synergizing Reasoning and Acting in Language Models. arXiv:2210.03629.
• Besta, M. et al. (2023). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. arXiv:2308.09687.
• Lightman, H. et al. (2023). Let's Verify Step by Step. arXiv:2305.20050.
• Lanham, T. et al. (2023). Measuring Faithfulness in Chain-of-Thought Reasoning. arXiv:2307.13702.
• Yang, B. et al. (2025). Hallucination Detection in Large Language Models with Metamorphic Relations. arXiv:2502.15844.