Tree of Thoughts (ToT) (DE)

Tree of Thoughts (ToT) (Baum der Gedanken) ist ein innovatives Framework zur Steuerung der Denkprozesse von großen Sprachmodellen (LLMs), das es ihnen ermöglicht, Probleme bewusst zu lösen, indem es systematisch eine Vielzahl von Denkpfaden erkundet. Das Konzept wurde 2023 von Forschern der Princeton University und Google DeepMind vorgestellt.

ToT ist eine Erweiterung und Verallgemeinerung der populären Technik „Chain of Thought“ (CoT). Im Gegensatz zu CoT, bei dem der Denkprozess eine einzelne lineare Abfolge von Schritten ist, organisiert ToT den Denkprozess in Form eines Baumes, bei dem jeder Knoten ein Zwischenzustand („Gedanke“) und die Äste mögliche Entwicklungswege des Gedankengangs sind. Dies ermöglicht es dem Modell, mehrere Optionen parallel zu untersuchen, ihre Erfolgsaussichten zu bewerten, bei Sackgassen zu früheren Schritten zurückzukehren (Backtracking) und eine bewusste Wahl zu treffen.

Funktionsprinzip

Das ToT-Framework organisiert den Problemlösungsprozess als eine Suche in einem Zustandsbaum. Seine Funktionsweise basiert auf dem zyklischen Zusammenspiel von vier Schlüsselkomponenten:

1. Zerlegung des Problems in „Gedanken“: Das ursprüngliche Problem wird in kleinere Teilschritte, sogenannte „Gedanken“, zerlegt. Im Gegensatz zu CoT, wo ein „Gedanke“ einfach das nächste Token ist, ist ein „Gedanke“ in ToT eine semantisch bedeutsame Einheit (z. B. eine Gleichung in einer mathematischen Aufgabe oder ein Absatz in einer Textgliederung), die der Lösung näher kommt.

1. Gedankengenerierung: In jedem Schritt generiert das Modell für den aktuellen Zustand (Knoten des Baumes) mehrere potenzielle nächste „Gedanken“ (Äste). Dafür werden zwei Strategien verwendet:

• Sampling: Das Modell generiert unabhängig voneinander mehrere Fortsetzungsvarianten. Dies eignet sich für kreative Aufgaben, bei denen ein breites Spektrum an Ideen nützlich ist.
• Vorschlagen (Propose): Das Modell generiert sequenziell Varianten, was bei Aufgaben mit einem begrenzten Lösungsraum effizienter ist.

1. Zustandsbewertung: Die generierten „Gedanken“ werden vom LLM selbst bewertet, um ihre Erfolgsaussichten zu bestimmen. Die Bewertung kann numerisch (z. B. auf einer Skala von 0 bis 1) oder kategorial („sicher“, „möglich“, „unmöglich“) sein. Dies ist eine heuristische Funktion, die die Suche in Richtung vielversprechender Zweige lenkt.

1. Suchalgorithmus: Zur systematischen Untersuchung des Gedankenbaums werden klassische Suchalgorithmen verwendet:

• Breitensuche (BFS): Untersucht alle Knoten auf einer Ebene, bevor zur nächsten übergegangen wird. Garantiert das Finden des kürzesten Weges, benötigt aber mehr Speicher.
• Tiefensuche (DFS): Untersucht einen Zweig vollständig, bevor zurückgekehrt und ein anderer versucht wird. Ist speichereffizienter und eignet sich für Aufgaben mit einem tiefen, aber nicht zu breiten Suchraum.

Dieses Framework imitiert das menschliche Denken bei der Problemlösung, indem es die intuitive Ideengenerierung (mithilfe des LLM) mit bewusster, systematischer Planung und dem Durchspielen von Varianten kombiniert.

Vergleich mit anderen Reasoning-Methoden

ToT im Vergleich zu Chain of Thought (CoT)

ToT ist eine direkte Verallgemeinerung von CoT. Während CoT als Baum mit einer Verzweigungsbreite von 1 betrachtet werden kann, ermöglicht ToT die Untersuchung eines Baumes mit beliebiger Breite. Dies bietet entscheidende Vorteile:

• Untersuchung von Alternativen: ToT kann mehrere Lösungswege betrachten, während CoT auf einen einzigen linearen Pfad beschränkt ist.
• Möglichkeit zum Backtracking: ToT ermöglicht es dem Modell, „zurückzugehen“, wenn ein Gedankengang in eine Sackgasse führt, was bei CoT nicht möglich ist.
• Globale Planung: ToT ermöglicht strategische Entscheidungen auf der Grundlage der Bewertung mehrerer zukünftiger Schritte.

ToT im Vergleich zu Self-Consistency

Self-Consistency generiert mehrere unabhängige „Chains of Thought“ und wählt die häufigste Antwort durch eine Abstimmung aus. Diese Methode verbessert die Zuverlässigkeit von CoT, aber wie CoT erlaubt sie keine Untersuchung einer verzweigten Lösungsstruktur. ToT hingegen kann bei komplexen Planungsaufgaben, bei denen nicht nur unabhängige Versuche, sondern auch ihre Wechselbeziehungen wichtig sind, deutlichere Verbesserungen zeigen.

Experimentelle Ergebnisse

Die Autoren von ToT haben seine Wirksamkeit bei drei Aufgaben demonstriert, die eine nichttriviale Planung oder Suche erfordern.

• Game of 24: Ein mathematisches Rätsel, bei dem aus vier gegebenen Zahlen mithilfe der Grundrechenarten die Zahl 24 gebildet werden muss. Standard-Prompting mit GPT-4 erreichte eine Erfolgsquote von 7,3 %, Chain of Thought 4 %. ToT mit Breitensuche (b=5) erreichte 74 % Erfolgsquote, was 18,5-mal besser ist als CoT.
• Kreatives Schreiben: Bei der Aufgabe, einen zusammenhängenden Text aus vier Absätzen mit vorgegebenen letzten Sätzen zu generieren, erhielten die mit ToT erstellten Texte eine durchschnittliche Kohärenzbewertung von 7,56 von 10, während CoT auf 6,15 kam. In 41 von 100 Vergleichen bevorzugten Menschen den von ToT generierten Text, gegenüber 21 für CoT.
• Mini-Kreuzworträtsel (5x5): ToT füllte 60 % der Wörter korrekt aus, während CoT nur 1 % schaffte.

Einschränkungen und zukünftige Richtungen

Trotz der beeindruckenden Ergebnisse hat das ToT-Framework eine Reihe von Einschränkungen:

• Rechenaufwand: ToT benötigt erheblich mehr Rechenressourcen (5- bis 100-mal mehr Tokens) als Standardmethoden, da viele „Gedanken“ generiert und bewertet werden müssen.
• Implementierungskomplexität: Die Implementierung von ToT erfordert einen erheblichen technischen Aufwand, um alle Komponenten zu erstellen und zu konfigurieren: den Gedankengenerator, den Zustandsbewerter und den Suchalgorithmus.
• Abhängigkeit von der Bewertungsqualität: Die Effektivität des gesamten Frameworks hängt stark von der Fähigkeit des LLM ab, Zwischenzustände adäquat zu bewerten, was nicht immer gewährleistet ist.

Zukünftige Forschungen zielen darauf ab, die Effizienz zu steigern, die Optimierung zu automatisieren und ToT mit anderen Methoden wie dem Verstärkenden Lernen zu integrieren, um intelligentere und autonomere Agenten zu schaffen.

Weblinks

• Offizielles Tree of Thoughts Repository auf GitHub.
• Tree of Thoughts (ToT) — Ein Leitfaden im Prompt Engineering Guide.

Literatur

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