Tree of Thoughts: Bewusste Problemlösung mit LLM-Suche

Nachdem ich mich in den letzten zwei Beiträgen mit Agenten befasst habe, die sich durch Reflexion (Reflexion) und tool-interaktives Kritisieren (CRITIC) selbst korrigieren, wollte ich einen Schritt zurücktreten und einen strukturelleren Ansatz betrachten: Was wäre, wenn der Agent sich erst gar nicht auf einen einzigen Argumentationspfad festlegen würde? Tree of Thoughts (ToT) von Yao et al. (NeurIPS 2023) schlägt genau das vor – ein Such-Framework, bei dem das LLM einen verzweigten Raum von Zwischenschritten der Argumentation erkundet, anstatt einer linearen Kette zu folgen. Ich lese es jetzt, weil es die klarste Formulierung bewusster Suche für LLM-Argumentation darstellt. Und bewusste Suche ist genau das, was man braucht, wenn ein einzelner falscher Zwischenschritt in einer Finanzkalkulation alle nachgelagerten Prozesse unbemerkt korrumpieren kann.

Das Paper

Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao und Karthik Narasimhan führen Tree of Thoughts als Generalisierung des Chain-of-Thought-Prompting ein. Der entscheidende Schritt besteht darin, Zwischenschritte der Argumentation als „Gedanken“ (Thoughts) zu behandeln – kohärente Texteinheiten, die unabhängig voneinander bewertet werden können – und diese in einem Baum statt in einer Kette zu organisieren. An jedem Knoten generiert das Modell mehrere Kandidaten-Gedanken, bewertet jeden einzelnen (über einen separaten LLM-Aufruf, der Zustände als „sicher / vielleicht / unmöglich“ einstuft) und wendet dann einen Standard-Suchalgorithmus (BFS oder DFS) an, um den Baum zu durchlaufen. Wenn ein Zweig aussichtslos erscheint, kann das Modell ihn beschneiden (Pruning) oder zurückgehen (Backtracking) – etwas, das weder CoT noch CoT-SC leisten können.

Das Paper evaluiert drei Aufgaben: Game of 24 (vier Zahlen kombinieren, um mittels Arithmetik 24 zu erreichen), Kreatives Schreiben (einen kohärenten Text aus vier zufälligen Satzenden erstellen) und Mini-Kreuzworträtsel (Lösen eines 5×5 Kreuzworträtsels). Alle drei erfordern eine Argumentationsweise, die von Exploration und Backtracking profitiert – genau das Szenario, für das die Autoren das System entwickelt haben.

Kernideen

• Beim Game of 24 erreicht ToT mit einer Beam-Breite b=5 eine Erfolgsquote von 74 %, gegenüber 4 % bei GPT-4 mit Standard-CoT und 9 % bei CoT-SC mit 100 Samples. Diese Lücke ist frappierend.
• GPT-3.5 + ToT erreicht bei derselben Aufgabe nur 19 %; der Nutzen der Methode ist stark modellabhängig. Die Qualität der Gedanken-Generierung von GPT-4 ist der Haupttreiber für den Gewinn – GPT-4 Generierung + GPT-3.5 Evaluierung erreicht 64 %, während GPT-3.5 Generierung + GPT-4 Evaluierung nur 31 % erreicht.
• Beim kreativen Schreiben erzielt ToT auf einer GPT-4-Kohärenzskala 7,56 Punkte gegenüber 6,93 bei CoT; menschliche Bewerter bevorzugen ToT-Ergebnisse in 41 von 100 Fällen gegenüber 21 von 100 bei CoT.
• Mini-Kreuzworträtsel: ToT erreicht eine Genauigkeit auf Wortebene von 60 % (CoT: 40,6 %, IO: 15,6 %), löst aber nur 4 von 20 vollständigen Spielen (20 %). Die Kluft zwischen dem Erfolg auf Wort- und Spielebene zeigt, dass die Erfüllung globaler Constraints selbst mit Backtracking schwierig bleibt.
• Der Evaluierungsschritt ist selbst ein LLM-Aufruf. Bei den Kreuzworträtseln stellt das Paper fest, dass Evaluatoren korrekte Teilzustände aufgrund unbekannten Vokabulars manchmal als „unmöglich“ einstufen – ein kumulativer Fehlermodus, bei dem die Fehler des Evaluators die Suche vergiften.
• Rechenkosten: ToT kostet im Game of 24 etwa 0,74 $ pro Fall, verglichen mit 0,47 $ für Best-of-100 CoT. Die Autoren weisen selbst darauf hin, dass sich der Mehraufwand für Aufgaben, die GPT-4 bereits gut beherrscht, nicht lohnt.

Was Bestand hat – und was nicht

Das Kernergebnis – dass die Baumsuche über Zwischengedanken bei Aufgaben, die Backtracking erfordern, das sequentielle CoT massiv übertrifft – ist real und reproduzierbar. Die Lücke von 74 % zu 4 % beim Game of 24 ist kein Zufallsrauschen. Die Erklärung ist mechanisch schlüssig: Eine einzige schlechte Zwischengleichung bei CoT führt die gesamte Kette ins Leere, während ToT diesen Zweig kappen und eine andere Zerlegung versuchen kann.

Weniger überzeugend finde ich den Anspruch auf Generalisierbarkeit. Alle drei Evaluationsaufgaben sind relativ synthetisch: ein Mathe-Rätsel, eine kreative Schreibaufgabe mit strukturellen Einschränkungen und ein Wortspiel. Keine davon ähnelt den offen gestalteten, zweideutigen Problemen, die in produktiven Finanz-Workflows auftreten. Zudem evaluieren die Autoren nur auf GPT-4 (und GPT-3.5 als Ablation), sodass wir nicht wissen, wie ToT mit kleineren oder fein abgestimmten Modellen abschneidet – und der Wert von 19 % für GPT-3.5 deutet darauf hin, dass die Antwort „nicht gut“ lautet.

Das Scheitern auf Spielebene beim Kreuzworträtsel (20 % trotz 60 % Wortgenauigkeit) deutet auf ein tieferliegendes Problem hin: ToT ist eine lokale Suche, die von einem lokalen Evaluator geleitet wird. Es unterhält kein globales Constraint-Modell, was genau das ist, was man für Probleme braucht, bei denen die Interaktionen zwischen Teillösungen dicht sind. Das nachfolgende „Graph of Thoughts“-Paper (Besta et al., AAAI 2024) übt explizit diese Kritik und demonstriert eine Qualitätsverbesserung von 62 % gegenüber ToT bei Sortieraufgaben bei gleichzeitiger Kostensenkung um über 31 % – indem es Gedanken erlaubt, zu verschmelzen und Zyklen zu bilden, anstatt sie auf einen Baum zu beschränken.

Schließlich spielt die Kostenstruktur in der Praxis eine Rolle. Bei b=5 mit wiederholten Evaluator-Aufrufen ist ToT bei API-Aufrufen etwa 15–20-mal teurer als ein einzelner CoT-Durchgang. Für latenz- oder kostenempfindliche Anwendungen ist dies nicht ohne Weiteres akzeptabel.

Warum das für Finanz-KI wichtig ist

Die ehrliche Antwort lautet: ToT ist vor allem für einen schmalen Ausschnitt des Beancount-Problemraums relevant, aber dieser Ausschnitt ist real.

Die kanonische Finanzaufgabe, bei der ich Backtracking wünsche, ist die mehrstufige Kontenklassifizierung bei zweideutigen Transaktionen. Wenn ein LLM einen importierten Kontoauszug einem Kontenplan zuordnet, kann eine einzige falsche Zuweisung zu Beginn der Kette (z. B. die Behandlung einer Darlehensauszahlung als Einkommen) mehrere Schritte später in einer fehlgeschlagenen Saldo-Prüfung kaskadieren. Bei einem CoT-Agenten hat das Modell zu dem Zeitpunkt, an dem der Saldo fehlschlägt, keinen Mechanismus, um die ursprüngliche Klassifizierung zu revidieren. Ein ToT-Agent könnte zu diesem Knoten zurückkehren (Backtracking) und stattdessen Passiva:Darlehen versuchen.

Ebenso ist die Steueroptimierung über ein gesamtes Geschäftsjahr ein echtes Baumsuche-Problem: Einzelnachweis vs. Pauschalbetrag, Timing von Kapitalertragsrealisierungen, Bündelung von Spenden. Diese Entscheidungen interagieren nicht-linear, und man muss mehrere Zweige evaluieren, bevor man sich festlegt. Das BFS/DFS-Framing von ToT lässt sich natürlich auf diese Struktur übertragen.

Wobei ToT nicht hilft, ist der dominante Fall in Beancount: die routinemäßige Erfassung und Abstimmung von Transaktionen. Für eine Transaktion, die ein klares Gegenstück im Ledger hat, ist CoT + PAL (Auslagerung der Arithmetik an einen Code-Interpreter) schneller, billiger und bereits genau genug. ToT für die Klassifizierung von Ausgaben:Lebensmittel einzusetzen, hieße, mit Kanonen auf Spatzen zu schießen.

Die dringlichere Sorge für die Sicherheit beim Zurückschreiben (Write-back-Sicherheit) ist das Problem der Zuverlässigkeit des Evaluators. Wenn der Zustands-Evaluator ebenfalls ein LLM ist, kann er irren – und falsche Evaluierungen verlangsamen nicht nur die Suche, sie beschneiden korrekte Pfade. Jeder produktive Finanz-Agent, der ToT verwendet, bräuchte ein externes Orakel (eine Saldo-Prüfung, einen Schema-Validator, eine Regel-Engine) als Evaluator, nicht einen weiteren LLM-Aufruf.

Was man als Nächstes lesen sollte

• Graph of Thoughts: Solving Elaborate Problems with Large Language Models (Besta et al., AAAI 2024) – arXiv:2308.09687. Erweitert ToT von Bäumen auf beliebige Graphen und ermöglicht die Zusammenführung von Gedanken sowie Rückkopplungsschleifen. Der Anspruch auf Kostensenkung (>31 %) ist direkt relevant, wenn man suchbasierte Argumentation ohne den Overhead von ToT wünscht.
• Large Language Models Cannot Self-Correct Reasoning Yet (Huang et al., ICLR 2024) – arXiv:2310.01798. Ein kritischer Gegenpol: Ohne externes Feedback verschlechtert intrinsische Selbstkorrektur die Argumentationsleistung. Dies stellt die Annahme infrage, dass der LLM-basierte Evaluator von ToT zuverlässig genug ist, um die Suche zu leiten.
• RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation (arXiv:2409.09584) – wendet MCTS anstelle von BFS/DFS auf die Gedankensuche an, mit Ausführungs-Feedback als externem Orakel. Das Szenario der Codegenerierung ist strukturell ähnlich zum Zurückschreiben ins Ledger: Man hat eine überprüfbare Wahrheit (Läuft der Code? Besteht die Saldo-Prüfung?), was genau der Punkt ist, an dem Monte-Carlo-Rollouts einen Mehrwert bieten.