Tree of Thoughts

Tree of Thoughts (ToT) ist eine Denk-Technik für Sprachmodelle (Large Language Models, LLMs; die Systeme hinter ChatGPT und Claude): Das Modell zerlegt eine Aufgabe in Zwischen-Gedanken und probiert für jeden Schritt mehrere Fortsetzungen aus. Diese Möglichkeiten spannen einen Suchbaum auf (verzweigte Struktur wie ein Stammbaum). Das Modell bewertet jeden Zwischen-Gedanken selbst und verfolgt nur die vielversprechenden Zweige weiter; schwache Pfade werden verworfen. Die Technik wurde 2023 von [Yao et al.](https://arxiv.org/abs/2305.10601) an der Princeton University und Google DeepMind vorgestellt und erweitert Chain-of-Thought (schrittweises Denken in einer Kette) um Verzweigung und Selbstbewertung.

Was ist Tree of Thoughts?

Tree of Thoughts modelliert den Denk-Prozess eines Sprachmodells als Suchbaum (verzweigte Struktur mit einem Startpunkt oben und Verästelungen nach unten). Die Wurzel ist die ursprüngliche Aufgabe, jeder Knoten (Verzweigungspunkt) steht für einen Zwischen-Gedanken, also einen Teilschritt, ein Zwischenergebnis oder eine Teilantwort. Die Blätter ganz unten enthalten die Kandidaten für die Endlösung. Statt einer einzelnen Gedankenkette entstehen viele parallele Denk-Pfade, die das Modell selbst bewertet und wieder beschneidet.

Das Framework definiert vier Bausteine. Thought Decomposition zerlegt die Aufgabe in Zwischen-Schritte passender Granularität (bei Game of 24 etwa ein Rechenschritt pro Ebene, bei Kreativem Schreiben ein Absatzplan). Der Thought Generator erzeugt pro Knoten mehrere Kinder, entweder durch Sampling desselben Prompts oder durch einen Prompt, der explizit k Vorschläge fordert. Der State Evaluator bewertet Zwischenzustände, indem das Modell entweder einen Value-Score pro Knoten schätzt oder mehrere Knoten gegeneinander votet. Ein Search Algorithm wählt aus, welche Knoten weiter expandiert werden; im Paper Breitensuche (BFS) mit fester Breite pro Ebene und Tiefensuche (DFS) mit Backtracking bei niedrigen Scores.

Der Begriff geht auf Yao et al. 2023 zurück („Tree of Thoughts: Deliberate Problem Solving with Large Language Models", Princeton und Google DeepMind, NeurIPS 2023). Die Referenz-Implementierung liegt als [Open-Source-Bibliothek auf GitHub](https://github.com/princeton-nlp/tree-of-thought-llm). Die Autoren beschreiben ToT als Verallgemeinerung von Chain-of-Thought um zwei Achsen: Verzweigung (mehrere Fortsetzungen pro Schritt) und Bewertung mit Rückverfolgung (schwache Pfade werden verworfen, das Modell kehrt zu einem früheren Knoten zurück).

Der Begriff existiert, weil eine lineare Reasoning-Kette bei kombinatorischen Aufgaben systematisch scheitert. Sobald das Modell auf einem frühen Zwischenschritt in eine ungünstige Richtung läuft, ist der Endzustand kaum noch zu retten. Ein Suchbaum trennt das Erzeugen von Hypothesen vom Bewerten und erlaubt Backtracking als First-Class-Operation. Architektonisch ist ToT ein Orchestrator-Pattern oberhalb der LLM-API: Das Modell kennt den Baum nicht, es sieht pro Knoten nur einen Prompt. Suchalgorithmus und Evaluator laufen außerhalb, typischerweise in einem Agent-Framework oder in der Referenz-Bibliothek.

Abgrenzung zu Chain-of-Thought, Self-Consistency, Self-Refine, ReAct und Graph of Thoughts

Der Begriff wird häufig mit angrenzenden Reasoning-Techniken vermischt. Die relevanten Trennlinien:

[Chain-of-Thought](/insights/glossar/chain-of-thought/) ([Wei et al. 2022](https://arxiv.org/abs/2201.11903)) erzeugt einen einzelnen Reasoning-Pfad. Tree of Thoughts ist die strukturelle Erweiterung: Statt einer Kette entsteht ein Baum verzweigter Pfade, ergänzt um einen Evaluator, der Zwischenzustände bewertet. Ohne Chain-of-Thought als Baustein pro Knoten funktioniert ToT nicht.

[Self-Consistency](/insights/glossar/self-consistency/) ([Wang et al. 2022](https://arxiv.org/abs/2203.11171)) sampelt viele CoT-Pfade parallel und wählt die häufigste Endantwort per Mehrheitsentscheid. Die n Pfade laufen unabhängig, es gibt keinen gemeinsamen Suchbaum und keine Bewertung von Zwischenzuständen. ToT dagegen bewertet jeden Knoten und entscheidet dynamisch, welche Zweige weiter expandiert werden.

[Self-Refine](/insights/glossar/self-refine/) verbessert eine einzelne Antwort iterativ durch Selbstkritik und Revision. Es bleibt ein einzelner Pfad, nur seriell verfeinert; kein Suchraum, keine Verzweigung. [ReAct](/insights/glossar/react-pattern/) beantwortet eine andere Frage: was innerhalb eines einzelnen Schritts geschieht (Denken plus Tool-Aufruf). ToT und ReAct schließen sich nicht aus, ein ToT-Knoten kann intern ein ReAct-Schritt sein.

[Graph of Thoughts](/insights/glossar/graph-of-thoughts/) ([Besta et al. 2023](https://arxiv.org/abs/2308.09687)) verallgemeinert ToT zu einem gerichteten Graph mit Aggregations-Operation: Ein Knoten kann mehrere Elternteile haben, sodass Teil-Ergebnisse zusammengeführt werden können. In einem Baum hat jeder Knoten genau einen Elternteil, ein Merge-Schritt ist strukturell ausgeschlossen.

Beispiel: Game of 24 und Kreatives Schreiben

Das kanonische Beispiel aus dem Yao-Paper ist Game of 24. Aufgabe: Aus vier vorgegebenen Zahlen soll per Grundrechenarten die Zahl 24 erzeugt werden (jede Zahl genau einmal). Für die Zahlen 4, 9, 10, 13 lautet eine Lösung (10 - 4) * (13 - 9) = 24. In der Paper-Auswertung löst Chain-of-Thought mit GPT-4 rund 4 Prozent der Instanzen korrekt, Self-Consistency mit 100 CoT-Samples rund 9 Prozent. Tree of Thoughts mit BFS über drei Ebenen (pro Ebene ein Rechenschritt, Breite 5, Evaluator gibt pro Zwischen-Zustand ein „sure/maybe/impossible"-Rating) erreicht rund 74 Prozent.

Die Mechanik im Detail: Auf Ebene 1 schlägt der Generator mehrere erste Rechenschritte vor (etwa 13 - 9 = 4, 10 - 4 = 6, 4 + 9 = 13). Der Evaluator prüft für jeden Zwischen-Zustand, ob mit den verbleibenden Zahlen die 24 noch erreichbar ist. Aussichtslose Zweige (etwa 4 + 13 = 17, wenn danach nur noch 9 und 10 zur Verfügung stehen) werden mit „impossible" markiert und beschnitten. Nur die Top-Kandidaten pro Ebene werden weiter expandiert. Die Suche endet, sobald ein Blatt die 24 exakt trifft.

Im Paper werden zwei weitere Aufgaben untersucht. Beim Kreativen Schreiben soll ein Text aus vier Absätzen entstehen, wobei jeder Absatz mit einem vorgegebenen Satz endet. ToT generiert pro Ebene mehrere Plan-Vorschläge, bewertet ihre Konsistenz und wählt den stabilsten Plan aus, bevor der Text geschrieben wird. Beim 5x5 Mini-Crossword dient jeder Wortkandidat als Knoten, der Evaluator prüft Buchstaben-Konsistenz zwischen kreuzenden Wörtern. Der Kostenpunkt bleibt in allen drei Fällen: ToT ist gegenüber CoT um Faktor 5 bis 100 teurer, weil pro Knoten mindestens ein Modellaufruf und pro Zwischen-Zustand ein Evaluator-Aufruf anfällt.