Graph of Thoughts (DE)

Graph-of-Thoughts (GoT) ist ein Konzept aus dem Bereich der Arbeit mit großen Sprachmodellen (LLM, Large Language Models), das vorschlägt, den Denkprozess eines Modells als einen beliebigen Graphen von miteinander verbundenen „Gedanken“ (intermediären Lösungsschritten) darzustellen. Dieser Ansatz wurde von einer Forschungsgruppe unter der Leitung von Maciej Besta von der ETH Zürich vorgeschlagen und 2024 auf der AAAI-Konferenz veröffentlicht. Das Ziel von Graph-of-Thoughts ist es, die Möglichkeiten des Prompt Engineering über bestehende Schemata wie Chain-of-Thought (Gedankenkette) und Tree-of-Thoughts (Gedankenbaum) hinaus zu erweitern. Im Gegensatz zu diesen Ansätzen ermöglicht GoT, dass jedes vom Modell generierte Fragment einer Argumentation (ein Gedanke) auf jedes andere verweisen kann, wodurch ein Netzwerk von Ideen anstelle einer streng linearen oder baumartigen Struktur entsteht. Dies, so die Autoren, spiegelt die komplexe, nichtlineare Natur des menschlichen Denkens genauer wider und nähert den Denkmechanismus von LLMs potenziell der Funktionsweise des menschlichen Gehirns an (mit seinen rekurrenten neuronalen Verbindungen).

Graph-of-Thoughts ist ein Prompting-Framework, das heißt, es erfordert kein zusätzliches Training oder eine Feinabstimmung des Modells selbst. Stattdessen organisiert es den Dialog mit dem LLM auf eine besondere Weise, indem es das Modell durch eine Reihe von „Gedanken“-Schritten führt, die in einer Graphenstruktur miteinander verbunden sind. Eine solche Struktur ermöglicht es, verschiedene Argumentationszweige zu kombinieren und wiederzuverwenden: Das Modell kann beispielsweise mehrere Hypothesen oder Teile eines Problems parallel betrachten und anschließend die erfolgreichsten davon zu einer einzigen Lösung zusammenführen. Im enzyklopädischen Stil kann Graph-of-Thoughts als Verallgemeinerung früherer Strategien für strukturiertes Schließen mit LLMs definiert werden, die maximale Flexibilität bei der Organisation von Denkprozessen innerhalb einer einzigen komplexen Anfrage bietet.

Grundlagen: Chain-of-Thought und Tree-of-Thoughts

Die Graph-of-Thoughts-Methode ist aus früheren Ansätzen hervorgegangen, die eine explizite Argumentationsstruktur bei der Arbeit mit Sprachmodellen verwenden. Der grundlegende Ansatz ist Chain-of-Thought (CoT) – die „Gedankenkette“. Bei der CoT-Methode wird dem Benutzer vorgeschlagen, in die Anfrage an das Modell nicht nur die Problemstellung, sondern auch die Zwischenschritte der Argumentation aufzunehmen, die zur Antwort führen. Studien haben gezeigt, dass diese Art der Informationsdarbietung die Fähigkeit von LLMs, komplexe Aufgaben wie mathematische oder logische Rätsel zu lösen, erheblich verbessert, ohne dabei die Parameter des Modells selbst zu ändern. Tatsächlich regt CoT das Modell an, ein komplexes Problem schrittweise in einfachere Etappen zu zerlegen und so einen sequenziellen Gedankengang zu imitieren.

Eine Weiterentwicklung dieser Idee ist die Technik der Self-Consistency: Anstelle einer einzigen Gedankenkette werden mehrere unabhängige Ketten generiert, woraufhin die überzeugendste ausgewählt wird. Dies ermöglicht es dem Modell, verschiedene Lösungsansätze zu betrachten und verringert das Risiko einer falschen Antwort, die aus dem Verfolgen einer einzigen fehlerhaften Argumentationslinie resultiert. Dennoch bieten selbst mehrere CoT-Ketten keine Möglichkeit, „Ideen zu kombinieren“: Jede Kette wird isoliert betrachtet, und das Modell wählt lediglich die beste aus, ohne deren Inhalte zu kombinieren.

Um diese Einschränkung zu überwinden, wurde das Schema Tree-of-Thoughts (ToT) – der „Gedankenbaum“ – vorgeschlagen. Bei ToT ist der Denkprozess als Baum organisiert: An jedem Punkt kann das Modell mehrere Varianten der Gedankenentwicklung (Verzweigungen) erzeugen, woraufhin diese Zwischenzustände bewertet und die vielversprechendsten für eine weitere Vertiefung ausgewählt werden. Durch die Verwendung von Suchalgorithmen im Baum (z. B. Breitensuche – BFS, oder Tiefensuche – DFS) und die Möglichkeit, zu Knoten zurückzukehren und einen anderen Zweig zu entwickeln, bietet Tree-of-Thoughts dem Sprachmodell einen leistungsfähigeren Mechanismus zur Lösung komplexer Aufgaben als das lineare CoT. Es entstehen neue Möglichkeiten wie Rückverfolgung und Neubewertung: Wenn ein Zweig in eine Sackgasse führt, kann man zum vorherigen Knoten zurückkehren und einen anderen Weg versuchen. Diese Methode hat sich bei der Lösung von Logik- und Suchaufgaben bewährt, bei denen das Durchspielen von Varianten und die Planung eine große Rolle spielen.

Der Gedankenbaum legt jedoch auch starre Beschränkungen auf: Jeder Gedanke (Knoten des Baumes) gehört nur zu einem Zweig, Interaktionen finden nur zwischen Eltern- und Kindknoten statt, und verschiedene Zweige können nicht zusammenlaufen oder Informationen austauschen. Mit anderen Worten, ein gegenseitiger Austausch von Ideen (Cross-Pollination) zwischen verschiedenen Hypothesen im Rahmen einer einzigen Lösung ist erschwert: Die Zweige des Baumes entwickeln sich unabhängig voneinander und werden erst an der Wurzel zusammengeführt, wenn die beste Argumentationskette ausgewählt wird. Im realen kreativen oder analytischen Denken kehrt ein Mensch jedoch oft zu einer zuvor betrachteten Idee zurück und kombiniert sie mit einem anderen Argumentationszweig. Eine solche Verflechtung von Gedanken sprengt die Struktur eines Baumes.

Diese Beobachtungen führten Forscher zu der Idee einer flexibleren Struktur – einem Graphen, in dem die Verbindungen zwischen den Gedanken nicht eingeschränkt sind und ein komplexes Netzwerk bilden können. Wie in einer analytischen Übersicht aus dem Jahr 2024 festgestellt wird, spiegelt das Aufkommen von Gedankenkett-en, -bäumen und -graphen die Entstehung einer neuen Klasse von Methoden wider, die die Fähigkeiten von LLMs durch die explizite Strukturierung des Denkprozesses erheblich erweitern können. Insbesondere haben strukturierte Prompts es ermöglicht, die Ergebnisse von LLMs in vielen Bereichen spürbar zu verbessern – von der Lösung mathematischer Aufgaben und logischer Rätsel bis hin zur Planung und sogar zum kreativen Schreiben. Auf diesem allgemeinen Hintergrund entstand das Graph-of-Thoughts-Schema als nächster Schritt in der Entwicklung strukturierter Prompting-Methoden.

Konzept des Graph-of-Thoughts: Graphenstruktur der Gedanken

Graph-of-Thoughts schlägt vor, den Ablauf der Aufgabenbearbeitung durch ein Sprachmodell in Form eines beliebigen gerichteten Graphen darzustellen. Formal ist ein Gedankengraph in GoT eine Menge von Knoten (Gedanken) und Kanten (Abhängigkeiten zwischen Gedanken). Ein Knoten des Graphen ist ein einzelner „Gedanke“ des Modells – unter diesem Begriff wird jede bedeutungsvolle Einheit verstanden, die vom Kontext der Aufgabe abhängt: Dies kann eine einzelne Aussage, ein Lösungsschritt, ein Textfragment, ein Absatz, ein Codeblock usw. sein, der vom Modell als Antwort auf eine Anfrage generiert wird. Eine Kante zwischen Knoten bedeutet, dass ein Gedanke bei der Erzeugung eines anderen verwendet wurde – d. h., im Prompt wird explizit angegeben, dass das Modell sich auf ein bestimmtes vorheriges Ergebnis stützen soll, um ein neues zu erhalten. Somit halten die Kanten die Abhängigkeiten fest: von welchen zuvor erhaltenen Daten der aktuelle Argumentationsschritt abhängt.

Der entscheidende Unterschied von GoT zu einfacheren Strukturen ist die Möglichkeit der Aggregation und Verschmelzung von Gedanken. In einem Graphen ist es zulässig, dass ein Knoten (ein neuer Gedanke) mehrere Vorgänger hat. Dies entspricht der Situation, in der zwei oder mehr separate Argumentationsketten zusammengeführt werden: Das Modell erhält als Eingabe mehrere zuvor generierte Fragmente und bildet auf deren Grundlage eine synthetisierte Ausgabe. Beispielsweise kann das Modell bei der Lösung einer Aufgabe parallel zwei Hypothesen betrachten und dann einen neuen Gedanken schaffen, der die positiven Aspekte beider Hypothesen vereint und deren Nachteile beseitigt. Solche Aggregationsoperationen waren im Rahmen eines baumartigen Schemas (wo jeder Knoten nur einen Elternteil hat) unmöglich, lassen sich aber in einer Graphenstruktur natürlich realisieren. Neben der Verschmelzung von Ideen ermöglicht ein Graph auch die Einführung von Rückkopplungsschleifen (Feedback Loops): Prinzipiell verbietet die GoT-Struktur keine Zyklen, das heißt, das Modell kann ein Ergebnis an eine frühere Argumentationsstufe zur erneuten Verarbeitung oder Verfeinerung zurückgeben. Die Autoren ziehen hier eine Analogie zu rekurrenten Verbindungen in den neuronalen Netzen des Gehirns, wo der Output einer Neuronengruppe auf vorhergehende Schichten zurückwirken kann und so geschlossene Denkkreisläufe bildet.

Die praktische Umsetzung von Graph-of-Thoughts erfordert eine spezielle Organisation des Dialogs mit dem Modell. Die Forscher haben ein modulares Architektur-Framework für GoT entwickelt. Es enthält Komponenten für: (1) die feingranulare Steuerung einzelner Schritte (Gedanken) – ein „Controller“ steuert die Reihenfolge und Logik der Gedankengeneration; (2) die dynamische Erstellung von Prompts – für jeden Schritt bildet ein spezielles Modul einen Prompt auf der Grundlage des aktuellen Kontexts und der ausgewählten Graphenknoten (Vorgänger); (3) das Parsen und Bewerten der Antworten des Modells – die vom LLM erhaltenen Fragmente werden analysiert und auf Qualität, Nützlichkeit oder Übereinstimmung mit den Aufgabenkriterien bewertet. Die GoT-Architektur ermöglicht somit den interaktiven Aufbau eines Argumentationsgraphen: Nach jedem Schritt wird entschieden, welche neuen Knoten hinzugefügt, wie sie mit den vorherigen verbunden, welche Zweige fortgesetzt oder zusammengeführt werden sollen. Dank der Modularität kann ein solches Framework um neue Arten von „Gedankentransformationen“ (z. B. spezielle Operationen am Graphen) erweitert und an verschiedene Modelle angepasst werden (die Autoren testeten GoT erfolgreich mit LLMs der Familien GPT-3.5, GPT-4, LLAMA 2 u. a.). Eine wichtige Eigenschaft ist, dass GoT keine Änderung der Parameter des Sprachmodells selbst erfordert – alle Verbesserungen werden durch eine intelligentere Konstruktion von Anfragen und Verarbeitung von Antworten erreicht. Das bedeutet, dass bestehende leistungsstarke LLMs „as is“ verwendet werden können, während Graph-of-Thoughts als eine übergeordnete Steuerungsebene fungiert.

Es sei darauf hingewiesen, dass der Begriff Graph-of-Thought auch in einer anderen, unabhängigen Entwicklung auftauchte, die sich vom Ansatz von Besta und Kollegen unterscheidet. Im Jahr 2023 schlugen Yao Yao und Co-Autoren eine Methode zur Verbesserung des Reasonings von LLMs durch ein zusätzliches Modul – einen Encoder für Gedankengraphen – vor, was ein Nachtraining des Modells erforderte. Ihre Arbeit mit dem Titel „Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models“ beschreibt eine zweistufige Architektur: Zuerst wird ein Graph von miteinander verbundenen Zwischenaussagen generiert, dann wird dieser von einem speziellen Encoder transformiert und über einen Gated-Fusion-Mechanismus in das Modell integriert. Ein solcher hybrider Ansatz mit Training zeigte eine gewisse Genauigkeitssteigerung bei Aufgaben, z. B. stieg die Genauigkeit bei dem multimodalen Fragensatz ScienceQA von 85,2 % auf 87,6 % bei Verwendung des T5-base-Modells. Dieser Ansatz unterscheidet sich jedoch, obwohl er namentlich ähnlich ist, grundlegend: Er erfordert eine Änderung des Modells (Fine-Tuning) und ist kein Prompt-Engineering-Schema. Die Autoren des ursprünglichen GoT-Ansatzes (AAAI 2024) weisen ausdrücklich darauf hin, dass sie das Modell von Yao et al. in ihrer Arbeit nicht betrachten, da sie sich ausschließlich auf Methoden ohne Aktualisierung der LLM-Parameter konzentrieren. Somit ist Graph-of-Thoughts im Kontext dieser Übersicht ein Framework auf der Ebene der Prompts und keine Modifikation der neuronalen Netzwerkarchitektur.

Anwendung und Ergebnisse

Die Autoren von GoT haben dessen Vorteile bei einer Reihe von Aufgaben demonstriert, die mit einer einfachen direkten Anfrage (Input-Output-Prompting) oder sogar mit einer Gedankenkette schwer zu lösen sind. Ein charakteristisches Merkmal solcher Aufgaben ist, dass sie in mehrere Teile (Teilaufgaben) zerlegt, diese Teile separat gelöst und dann die Teilergebnisse zu einer vollständigen Antwort synthetisiert werden können. Zu den untersuchten Beispielen gehören: Sortierung einer unsortierten Liste, Zählung von Schlüsselwörtern in einem Text (z. B. zur Zusammenfassung eines Dokuments), Durchführung von Mengenoperationen (Vereinigung, Schnittmenge von Listen usw.) sowie die Zusammenführung von Textdokumenten (Kombination von Informationen aus mehreren Quellen). In all diesen Fällen ermöglicht Graph-of-Thoughts eine natürliche Dekomposition der Aufgabe. Zum Beispiel wird bei der Sortierung die Liste in Teile zerlegt, jeder Teil wird separat als unabhängiger Gedankenzweig sortiert, woraufhin die Ergebnisse zusammengeführt werden (in Anlehnung an einen Algorithmus wie Merge Sort); oder bei der Textanalyse kann das Modell parallel Informationen aus verschiedenen Dokumenten extrahieren und diese anschließend zusammenfassen.

Experimentelle Ergebnisse bestätigen die Wirksamkeit des GoT-Schemas. Laut dem Bericht von Besta und Kollegen konnte der Gedankengraph bei der Sortieraufgabe die Lösungsqualität im Vergleich zu früheren Ansätzen erheblich steigern. So war die Sortiergenauigkeit bei Verwendung von GoT um 70 % höher als bei einer einfachen Chain-of-Thought (CoT) und um 62 % höher als bei einem Tree-of-Thoughts (ToT). Gleichzeitig reduziert die Methode den Rechenaufwand: Die Anzahl der Modellaufrufe (und damit das tokenisierte Volumen der Anfragen) sank bei derselben Aufgabe um 31 % im Vergleich zu Tree-of-Thoughts. Dies bedeutet, dass die graphenbasierte Organisation der Argumentation nicht nur das Endergebnis verbesserte, sondern die Lösung auch wirtschaftlicher machte, indem überflüssige Berechnungen durch geschicktes Kombinieren von Zwischenergebnissen vermieden wurden. Ähnliche Vorteile wurden auch bei anderen Testaufgaben erzielt, insbesondere dort, wo heterogene Informationen aggregiert werden müssen. Die Forscher stellen fest, dass GoT besonders effektiv für zusammengesetzte Aufgaben ist, die aus mehreren Elementen bestehen: „Graph-of-Thoughts eignet sich besonders gut für Aufgaben, die sich natürlich in kleinere Teilaufgaben zerlegen lassen, die separat gelöst und deren Ergebnisse anschließend zusammengeführt werden“. In solchen Fällen ist der Gedankengraph in der Lage, alle Aspekte eines Problems zu erfassen und eine umfassendere Lösung zu synthetisieren, als dies bei der Verfolgung einer einzigen Argumentationslinie möglich wäre.

Um genauer zu verstehen, warum eine Methode zur Erstellung von Prompts besser ist als eine andere, wurde in einer Arbeit aus dem Jahr 2024 eine spezielle Metrik eingeführt – das „Volumen eines Gedankens“ (volume of a thought). Das Volumen ist für jeden einzelnen Gedanken (Knoten des Graphen) definiert als die Anzahl anderer Gedanken, von denen aus dieser über gerichtete Kanten erreichbar ist (einfach ausgedrückt, wie vielen Zwischenschritten er seine Informationen verdankt). Bei Chain-of-Thought stützt sich jeder Gedanke nur auf einen einzigen Vorgänger, daher ist sein Volumen gleich 1 (lineare Kette). In einem Gedankenbaum kann das Volumen größer sein, ist aber immer noch durch die Struktur eines einzelnen Zweiges begrenzt. In einem Graphen hingegen kann ein einzelner Knoten dank der Aggregation den Beitrag vieler anderer akkumulieren – sein „Volumen“ ist wesentlich höher. Es wurde gezeigt, dass GoT es ermöglicht, dass die Endergebnisse auf einem wesentlich größeren Volumen an vorangegangenen Gedanken basieren, indem deren Inhalte zusammengeführt werden. Diese Tatsache spiegelt eine tiefere Abdeckung des Lösungsraums wider und dient als quantitative Erklärung für die Vorteile der graphenbasierten Argumentation gegenüber einfacheren Schemata.

Vergleich und Bedeutung

Graph-of-Thoughts stellt derzeit die allgemeinste Form des strukturierten Promptings für LLMs dar. In Vergleichstabellen verschiedener Schemata (CoT, CoT mit Selbstkonsistenz, ToT und GoT) wird betont, dass nur GoT eine beliebige Topologie des Denkprozesses unterstützt. Es umfasst die Fähigkeiten aller vorherigen Ansätze: Es kann als eine einzige Kette, als ein Baum mit Verzweigungen oder als eine Kombination aus mehreren Ketten arbeiten, wenn dies zur Lösung der Aufgabe geeignet ist. Das Wichtigste ist, dass es keine starren Beschränkungen für die Verbindungen zwischen den Schritten gibt, was den Raum möglicher Argumentationsstrategien theoretisch maximal erweitert.

Es ist wichtig zu verstehen, dass die Flexibilität von GoT mit einer größeren Komplexität der Steuerung einhergeht. Die Implementierung eines Gedankengraphen erfordert einen externen Orchestrierungs-Algorithmus, der entscheidet, wann und welche Gedanken generiert, welche davon ausgewählt oder kombiniert, wann der Prozess gestoppt und eine Antwort ausgegeben werden soll. Bei einem einfachen CoT müssen solche Entscheidungen nicht getroffen werden – das Modell generiert selbst eine lineare Argumentation bis zum Ende. Bei ToT liegt ein Teil der Steuerung beim Suchalgorithmus im Baum (z. B. die Wahl des zu erweiternden Knotens). Bei GoT ist der Freiheitsgrad höher, und die Effektivität der Methode hängt von der Qualität der Heuristiken ab, die Zwischenergebnisse bewerten, sowie von der richtigen Konstruktion der Prompts in jedem Schritt. Somit kann Graph-of-Thoughts nicht nur als ein Anfrageformat, sondern als eine Argumentationsstruktur betrachtet werden, die dem Interaktionsprozess mit dem LLM überlagert wird – eine Art dynamischer Plan, nach dem das Modell eine Aufgabe löst, während der Benutzer (oder ein steuerndes Programm) diesen Prozess lenkt.

Das Aufkommen von Graph-of-Thoughts spiegelt das Bestreben wider, die Arbeit großer Sprachmodelle interpretierbarer und steuerbarer zu machen. Indem Forscher die Lösungsstruktur explizit vorgeben, erzielen sie nicht nur eine bessere Qualität, sondern erhalten auch die Möglichkeit zu analysieren, wie das Modell zu einer bestimmten Schlussfolgerung gelangt ist. Dies nähert die Ansätze im NLP den klassischen Methoden der algorithmischen Suche und Planung an, wobei die Ausführung der Schritte nun einem neuronalen Netzwerkmodell obliegt. Eine Reihe von Experten betrachtet strukturierte Prompts (Gedankenkett-en, -bäume und -graphen) als eine vielversprechende Richtung, die die Beschränkungen der „Black Box“ in tiefen Modellen überwinden und deren Zuverlässigkeit bei komplexen Aufgaben erhöhen kann.

Die Methodologie von Graph-of-Thoughts wird aktiv weiterentwickelt. Die Autoren haben den Code und Beispiele zur Implementierung von GoT als Open Source zur Verfügung gestellt, was der Community ermöglichte, mit dem neuen Ansatz zu experimentieren. Es entstehen auch Erweiterungen: zum Beispiel multimodale Versionen des Gedankengraphen, die Text mit Bildern und anderen Datentypen kombinieren, sowie Versuche, die Ideen von GoT direkt in die Architektur der Modelle zu integrieren (wie in der erwähnten Arbeit von Yao et al., 2023). Im Jahr 2024 erschien eine detaillierte Übersicht und Taxonomie der Methoden Chain-of-Thought, Tree-of-Thoughts und Graph-of-Thoughts, die das gesammelte Wissen systematisiert und die theoretischen Grundlagen solcher Ansätze beschreibt. All dies zeugt von einem großen Interesse der wissenschaftlichen Gemeinschaft an der strukturierten Steuerung des Denkens von LLMs. Graph-of-Thoughts hat sich bereits als wirksames Werkzeug zur Lösung komplexer Aufgaben etabliert und wird wahrscheinlich die Grundlage für weitere Innovationen im Bereich der KI-Lösungen bilden, die die Leistungsfähigkeit großer Sprachmodelle mit der Transparenz und Logik klassischer Algorithmen verbinden.

Links

• Originalartikel „Graph of Thoughts: Solving Elaborate Problems with Large Language Models“ auf arXiv
• HTML-Version des Originalartikels
• Übersicht „Demystifying Chains, Trees, and Graphs of Thoughts“ auf arXiv
• Artikel „Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models“ auf arXiv
• Multimodal Graph-of-Thoughts — Artikel von Deepgram
• LLMs Graph of Thoughts Framework — Artikel auf Medium

Literatur

• 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.