Graph of Thoughts (CS)

Graph-of-Thoughts (GoT) — je koncepce v oblasti práce s velkými jazykovými modely (LLM, Large Language Models), která předpokládá reprezentaci procesu uvažování modelu ve formě libovolného grafu vzájemně propojených „myšlenek" (mezikroků řešení). Tento přístup byl navržen skupinou výzkumníků pod vedením Maceje Besty (Maciej Besta) z ETH Zurich a publikován v roce 2024 na konferenci AAAI. Cílem Graph-of-Thoughts je rozšířit možnosti prompt engineeringu (tvorby dotazů) za hranice stávajících schémat, jako jsou Chain-of-Thought (řetězec myšlenek) a Tree-of-Thoughts (strom myšlenek). Na rozdíl od nich umožňuje přístup GoT libovolnému fragmentu úvah vygenerovanému modelem (myšlence) odkazovat na jakýkoli jiný, čímž vzniká síť nápadů, nikoli striktně lineární nebo stromová struktura. To, jak tvrdí autoři, přesněji odráží složitý, nelineární charakter lidského myšlení a potenciálně přibližuje mechanismus uvažování LLM fungování lidského mozku (s jeho rekurentními nervovými spojeními).

Graph-of-Thoughts je metodou tvorby dotazů (prompting framework), tedy nevyžaduje žádné dodatečné trénování ani dolaďování samotného modelu — místo toho organizuje dialog s LLM zvláštním způsobem a vede model prostřednictvím série kroků-„myšlenek" propojených podle schématu grafu. Taková struktura umožňuje kombinovat a opakovaně využívat různé větve úvah: model může například paralelně uvažovat o několika hypotézách nebo částech úlohy a poté z nich nejzdařilejší sloučit do jediného řešení. V encyklopedickém stylu lze Graph-of-Thoughts definovat jako zobecnění předchozích strategií strukturovaného uvažování s LLM, poskytující maximální flexibilitu při organizaci myšlenkových procesů v rámci jednoho komplexního dotazu.

Předpoklady: Chain-of-Thought a Tree-of-Thoughts

Metoda Graph-of-Thoughts vyrostla ze starších přístupů využívajících explicitní strukturu uvažování při práci s jazykovými modely. Základním přístupem je Chain-of-Thought (CoT) – „řetězec myšlenek". V metodě CoT je uživateli navrhováno, aby do dotazu modelu zahrnoval nejen zadání úlohy, ale také mezikroky uvažování vedoucí k odpovědi. Výzkumy ukázaly, že takové podání materiálu výrazně zlepšuje schopnost LLM řešit složité úlohy, například matematické nebo logické hádanky, přičemž parametry samotného modelu se nemění. CoT fakticky pobízí model, aby krok za krokem rozložil složitý problém na jednodušší etapy a napodoboval tak postupný tok myšlenek.

Rozvíjením této myšlenky se stala technika Self-Consistency: místo jednoho řetězce myšlenek je generováno několik nezávislých řetězců, přičemž je poté vybrán nejpřesvědčivější z nich. To umožňuje modelu zvážit různé přístupy k řešení a snižuje riziko chybné odpovědi způsobené sledováním jediné nesprávné linie úvah. Ani množství řetězců CoT však nedává možnost „slučovat nápady": každý řetězec je posuzován izolovaně a model pouze vybírá ten nejlepší, aniž by kombinoval jejich obsah.

Pro překonání tohoto omezení bylo navrženo schéma Tree-of-Thoughts (ToT) – „strom myšlenek". V ToT je proces uvažování organizován jako strom: v každém bodě může model generovat několik variant rozvoje myšlenky (větvení), poté jsou tato mezilehlá stádia hodnocena a jsou vybrána ta nejslibnější pro další prohlubování. Díky prohledávání stromu (například do šířky — BFS, nebo do hloubky — DFS) a možnosti vracet se k uzlům a rozvíjet jinou větev poskytuje Tree-of-Thoughts jazykovému modelu výkonnější mechanismus pro řešení složitých úloh než lineární CoT. Objevují se nové možnosti, jako je návrat a přehodnocení: pokud jedna větev vede do slepé uličky, lze se vrátit k předchozímu uzlu a vyzkoušet jinou cestu. Tato metoda prokázala svou účinnost při řešení logických a prohledávacích úloh, kde hraje velkou roli procházení variant a plánování.

Strom myšlenek však ukládá i přísná omezení: každá myšlenka (uzel stromu) patří pouze jedné větvi, interakce probíhá pouze mezi rodičovskými a dceřinými uzly a různé větve se nemohou slučovat ani si vyměňovat informace. Jinými slovy, křížové sdílení nápadů (cross-pollination) mezi různými hypotézami v rámci jednoho řešení je obtížné: větve stromu se vyvíjejí nezávisle a spojují se teprve v kořenu, kdy je vybrán nejlepší řetězec úvah. V reálném tvůrčím nebo analytickém myšlení se člověk však často vrací k dříve uvažované myšlence a kombinuje ji s jinou větví úvah. Takové propletení myšlenek přesahuje rámec stromové struktury.

Tato pozorování přivedla výzkumníky k myšlence flexibilnější struktury — grafu, kde vazby mezi myšlenkami nejsou omezeny a mohou tvořit složitou síť. Jak je uvedeno v analytickém přehledu z roku 2024, vznik řetězců, stromů a grafů myšlenek odráží zrod nové třídy metod, schopných výrazně posílit možnosti LLM prostřednictvím explicitního strukturování procesu uvažování. Strukturované podněty (prompty) zejména umožnily citelně zlepšit výsledky LLM v mnoha oblastech — od řešení matematických úloh a logických hádanek až po plánování a dokonce tvůrčí psaní. Na tomto obecném pozadí vzniklo schéma Graph-of-Thoughts jako další krok ve vývoji metod strukturovaného promptingu.

Koncepce Graph-of-Thoughts: grafová struktura myšlenek

Graph-of-Thoughts navrhuje reprezentovat průběh plnění úloh jazykovým modelem ve formě libovolného orientovaného grafu. Formálně je graf myšlenek v GoT množina vrcholů (myšlenek) a hran (závislostí mezi myšlenkami). Vrcholem grafu je jednotlivá myšlenka modelu — pod tímto pojmem se rozumí jakákoli obsahová jednotka závislá na kontextu úlohy: může jít o jednotlivé tvrzení, krok řešení, fragment textu, odstavec, blok kódu apod., který model formuluje v odpovědi na dotaz. Hrana mezi vrcholy znamená, že jedna myšlenka byla použita při generování jiné — tj. v podnětu je explicitně uvedeno, že model se má opřít o určitý předchozí výsledek, aby získal nový. Hrany tak zaznamenávají závislosti: na jakých dříve získaných datech závisí aktuální krok uvažování.

Nejdůležitějším rozdílem GoT oproti jednodušším strukturám je možnost agregace a slučování myšlenek. V grafu je přípustné, aby vrchol (nová myšlenka) měl více předchůdců. To odpovídá situaci, kdy se dva nebo více samostatných řetězců uvažování spojí: model obdrží na vstupu hned několik dříve vygenerovaných fragmentů a na jejich základě formuluje syntetizovaný závěr. Při řešení úlohy může model například paralelně uvažovat o dvou hypotézách a poté vytvořit novou myšlenku, která spojuje pozitivní stránky obou hypotéz a odstraňuje jejich nedostatky. Takové operace agregace nebyly v rámci stromového schématu možné (kde má každý uzel pouze jednoho rodiče), ale v grafovém schématu se realizují přirozeně. Kromě slučování nápadů umožňuje graf zavádět i zpětné vazby (feedback loops): struktura GoT v zásadě cykly nezakazuje, tj. model může vrátit určitý výsledek do dřívější fáze uvažování k opětovnému zpracování nebo upřesnění. Autoři to spojují s analogií rekurentních spojení v neuronových sítích mozku, kde výstup jedné skupiny neuronů může zpětně působit na předchozí vrstvy a vytvářet uzavřené okruhy uvažování.

Praktická realizace Graph-of-Thoughts vyžaduje zvláštní organizaci dialogu s modelem. Výzkumníci vyvinuli modulární architektonický rámec pro GoT. Ten zahrnuje komponenty pro: (1) jemnou kontrolu nad jednotlivými kroky (myšlenkami) — „kontrolér" řídí pořadí a logiku generování myšlenek; (2) dynamické formování podnětů — pro každý krok speciální modul vytváří prompt na základě aktuálního kontextu a vybraných vrcholů grafu (předchůdců); (3) parsování a hodnocení odpovědí modelu — fragmenty přijaté od LLM jsou analyzovány a hodnoceny z hlediska kvality, užitečnosti nebo souladu s kritérii úlohy. Architektura GoT tak umožňuje interaktivně budovat graf úvah: po každém kroku je rozhodnuto, které nové vrcholy přidat, jak je propojit s předchozími, které větve pokračovat nebo spojit. Díky modularitě lze takový framework rozšiřovat o nové typy „transformací myšlenek" (například speciální operace s grafem) a přizpůsobovat jej různým modelům (autoři úspěšně testovali GoT s LLM z rodin GPT-3.5, GPT-4, LLAMA 2 a dalšími). Důležitou vlastností je, že GoT nevyžaduje změnu parametrů samotného jazykového modelu — veškerá zlepšení jsou dosažena důmyslnější konstrukcí dotazů a zpracováním odpovědí. To znamená, že stávající výkonné LLM lze použít „tak jak jsou" a Graph-of-Thoughts plní roli nadstavby řídící jejich fungování.

Je třeba poznamenat, že termín Graph-of-Thought se objevil také v jiném, nezávislém vývojovém projektu odlišném od přístupu Besty a jeho kolegů. V roce 2023 navrhli Yao Yao a spoluautoři metodu zlepšení reasoning u LLM prostřednictvím dodatečného modulu-enkodéru grafu myšlenek, která vyžadovala doladění modelu. Jejich práce s názvem „Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models" popisuje dvoustupňovou architekturu: nejprve je vygenerován graf vzájemně provázaných mezilehlých tvrzení, poté je transformován speciálním enkodérem a integrován do modelu prostřednictvím mechanismu gated fusion. Tento hybridní přístup s trénováním prokázal určité zvýšení přesnosti na úlohách — například na multimodální sadě otázek ScienceQA vzrostla přesnost z 85,2 % na 87,6 % při použití modelu T5-base. Tento přístup, ačkoli je svým názvem podobný, se však zásadně liší: vyžaduje změnu modelu (fine-tuning) a není schématem prompt engineeringu. Autoři původního přístupu GoT (AAAI 2024) přímo uvádějí, že ve své práci nepracují s modelem Yao et al., protože se zaměřují právě na metody bez aktualizace parametrů LLM. Graph-of-Thoughts je tedy v kontextu tohoto přehledu framework na úrovni podnětů, nikoli modifikace architektury neuronové sítě.

Aplikace a výsledky

Autoři GoT demonstrovali jeho přednosti na řadě úloh, které je obtížné řešit pomocí jediného přímého podnětu (input-output prompting) nebo dokonce pomocí řetězce myšlenek. Charakteristickým rysem takových úloh je, že je lze rozložit na několik částí (dílčích úloh), tyto části řešit odděleně a poté syntetizovat úplnou odpověď z dílčích výsledků. Mezi uvažovanými příklady jsou: třídění neuspořádaného seznamu, počítání klíčových slov v textu (například pro sumarizaci dokumentu), provádění operací nad množinami (sjednocení, průnik seznamů apod.), jakož i slučování textových dokumentů (spojování informací z více zdrojů). Ve všech těchto případech umožňuje Graph-of-Thoughts přirozeně dekompozici úlohy. Například pro třídění je seznam rozdělen na části, každá část je tříděna samostatně jako nezávislá větev myšlenek a výsledky jsou poté sloučeny (napodobujíce algoritmus jako merge sort); nebo při analýze textů může model paralelně extrahovat informace z různých dokumentů a poté je sjednocovat.

Experimentální výsledky potvrzují účinnost schématu GoT. Podle zprávy Besty a kolegů umožnil graf myšlenek při úloze třídění výrazně zvýšit kvalitu řešení ve srovnání s předchozími přístupy. Přesnost třídění při použití GoT byla o 70 % vyšší než při prostém řetězci myšlenek CoT a o 62 % vyšší než při stromu myšlenek ToT. Metoda zároveň snižuje náklady na výpočetní zdroje: počet dotazů modelu (a tedy tokenizovaný objem dotazů) se snížil o 31 % ve srovnání s Tree-of-Thoughts pro tutéž úlohu. To znamená, že grafová organizace úvah nejenže zlepšila výsledný výsledek, ale učinila řešení také úspornějším — díky promyšlenému kombinování mezilehlých závěrů se vyhnula zbytečným výpočtům. Podobné zisky byly získány i u dalších testovacích úloh, zejména tam, kde je třeba agregovat různorodé informace. Výzkumníci uvádějí, že GoT je nejúčinnější právě pro kompozitní úlohy skládající se z více prvků: „Graph-of-Thoughts se zvláště hodí pro úlohy, které se přirozeně rozkládají na menší dílčí úlohy řešitelné samostatně s následným sloučením výsledků". V takových případech je graf myšlenek schopen pokrýt všechny aspekty problému a syntetizovat komplexnější řešení než při sledování jediné linie úvah.

Pro hlubší pochopení toho, proč je jeden způsob sestavení podnětu lepší než jiný, byla v práci z roku 2024 navržena speciální metrika — „objem myšlenky" (volume of a thought). Objem je definován pro každou jednotlivou myšlenku (vrchol grafu) jako počet jiných myšlenek, z nichž lze po orientovaných hranách dosáhnout dané myšlenky (jednoduše řečeno, kolika mezilehlým krokům vděčí za svou informaci). V Chain-of-Thought se každá myšlenka opírá pouze o jednoho předchůdce, takže její objem je roven 1 (lineární řetězec). Ve stromu myšlenek může být objem větší, stále je však omezen strukturou jednotlivé větve. V grafu však může díky agregaci jednotlivý vrchol akumulovat příspěvky mnoha jiných — jeho „objem" je podstatně vyšší. Je ukázáno, že GoT umožňuje konečným závěrům opírat se o výrazně větší objem předchozích myšlenek a slučovat jejich obsah. Tento fakt odráží hlubší pokrytí prostoru řešení a slouží jako kvantitativní vysvětlení výhod grafového uvažování oproti jednodušším schématům.

Srovnání a význam

Graph-of-Thoughts v současnosti představuje nejobecnější formu strukturovaného promptingu pro LLM. V tabulkách porovnávajících různá schémata (CoT, CoT se self-consistency, ToT a GoT) je zdůrazňováno, že pouze GoT podporuje libovolnou topologii myšlenkového procesu. Zahrnuje možnosti všech předchozích přístupů: může fungovat jako jeden řetězec, jako strom s větvením i jako kombinace více řetězců, pokud to odpovídá řešení úlohy. Hlavní předností je absence přísných omezení vazeb mezi kroky, což teoreticky maximálně rozšiřuje prostor možných strategií uvažování.

Je důležité pochopit, že flexibilita GoT přichází za cenu větší složitosti řízení. Realizace grafu myšlenek vyžaduje zewnętrzní algoritmus-orchestrátor, který bude rozhodovat, kdy a které myšlenky generovat, které z nich vybírat nebo kombinovat, kdy proces zastavit a vydat odpověď. U jednoduchého CoT taková rozhodnutí přijímat není třeba — model sám generuje lineární úvahu až do konce. V ToT část řízení spočívá na algoritmu prohledávání stromu (například výběr uzlu k rozvíjení). V GoT je stupeň volnosti vyšší a účinnost metody závisí na kvalitě heuristik hodnotících mezilehlé výsledky a na správné konstrukci podnětů v každém kroku. Graph-of-Thoughts tak lze chápat nejen jako formát dotazu, ale jako strukturu uvažování nakládanou na proces interakce s LLM — jakýsi dynamický plán, podle nějž model řeší úlohu, přičemž uživatel (nebo program-kontrolér) tento proces řídí.

Vznik Graph-of-Thoughts odráží snahu učinit práci velkých jazykových modelů více interpretovatelnou a řiditelnou. Explicitním zadáváním struktury řešení výzkumníci nejen dosahují lepší kvality, ale také získávají možnost analyzovat, jak model dospěl k tomu či onomu závěru. To sbližuje přístupy v NLP s klasickými metodami algoritmického prohledávání a plánování, avšak provádění kroků je nyní svěřeno neuronovému modelu. Řada odborníků považuje strukturované podněty (řetězce, stromy, grafy myšlenek) za perspektivní směr, schopný překonat omezení „černé skříňky" v hlubokých modelech a zvýšit spolehlivost jejich fungování při řešení složitých úloh.

Metodologie Graph-of-Thoughts se nadále aktivně rozvíjí. Autoři zpřístupnili kód a příklady implementace GoT, což umožnilo komunitě experimentovat s novým přístupem. Objevují se také rozšíření: například multimodální verze grafu myšlenek kombinující text s obrazy a dalšími druhy dat, jakož i pokusy o integraci myšlenek GoT přímo do architektury modelů (jako ve zmíněné práci Yao et al., 2023). V roce 2025 vyšel podrobný přehled-taxonomie metod Chain-of-Thought, Tree-of-Thoughts a Graph-of-Thoughts, systematizující nashromážděné poznatky a popisující teoretické základy těchto přístupů. To vše svědčí o velkém zájmu vědecké komunity o strukturované řízení uvažování LLM. Graph-of-Thoughts si již vydobyl pověst účinného nástroje pro řešení složitých úloh a pravděpodobně se stane základem pro další inovace v oblasti řešení AI, kombinujících výkon velkých jazykových modelů s transparentností a logikou klasických algoritmů.

Odkazy

• Původní článek „Graph of Thoughts: Solving Elaborate Problems with Large Language Models" na arXiv
• HTML verze původního článku
• Přehled „Demystifying Chains, Trees, and Graphs of Thoughts" na arXiv
• Článek „Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models" na arXiv
• Multimodal Graph-of-Thoughts — článek Deepgram
• LLMs Graph of Thoughts Framework — článek na Medium

Literatura

• Besta, M. et al. (2024). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. arXiv:2308.09687.
• Yao, S. et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601.
• Yao, Y. et al. (2023). Beyond Chain-of-Thought: Effective Graph-of-Thought Reasoning in Language Models. arXiv:2305.16582.
• 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.
• Wei, J. et al. (2024). Demystifying Chains, Trees, and Graphs of Thoughts. arXiv:2401.14295.
• Huang, S. et al. (2023). Language Is Not All You Need: Aligning Perception with Language Models (Kosmos-1). arXiv:2302.14045.
• Mitra, C. et al. (2024). Compositional Chain-of-Thought Prompting for Large Multimodal Models. In CVPR 2024. PDF.
• Zheng, G. et al. (2023). DDCoT: Duty-Distinct Chain-of-Thought Prompting for Multimodal Reasoning in Language Models. arXiv:2310.16436.
• Mu, J. et al. (2023). Learning to Compress Prompts with Gist Tokens. arXiv:2304.08467.