Tree of Thoughts (ToT)

Tree of Thoughts (ToT) ist ein Rahmenwerk für Prompt Engineering, bei dem ein großes Sprachmodell (LLM) ein Problem löst, indem es einen Baum aus Teillösungen durchsucht. In jedem Schritt schlägt das Modell mehrere mögliche nächste Schritte vor, die Gedanken genannt werden, bewertet die Erfolgsaussichten jedes daraus entstehenden Zustands und lässt einen Suchalgorithmus entscheiden, welche Zweige erweitert, beibehalten oder verworfen werden. Während Chain-of-Thought-Prompting sich ab dem ersten Token auf eine einzige Gedankenkette festlegt, kann ToT vorausschauend suchen und zurückgehen. Shunyu Yao und Kollegen von der Princeton University und Google DeepMind stellten das Verfahren in Tree of Thoughts: Deliberate Problem Solving with Large Language Models vor, das bei NeurIPS 2023 präsentiert wurde. Im selben Monat schlug Jieyi Long ein ähnliches Baumsuchsystem vor, um Sudoku mit einem LLM zu lösen. Beim Spiel „Game of 24“ steigerte ToT die Erfolgsquote von GPT-4 von 4 % mit Chain-of-Thought-Prompting auf 74 %.

So funktioniert Tree of Thoughts#

Yao et al. definieren ToT anhand von vier Designentscheidungen:

• Gedankenzerlegung: Was als einzelner Schritt gilt. Bei Game of 24 ist ein Gedanke eine Gleichung, bei der kreativen Textgenerierung ein Plan für den Textabschnitt und bei einem Kreuzworträtsel ein einzusetzendes Wort.
• Gedankengenerator: Wie Vorschläge erzeugt werden. Das Modell zieht entweder unabhängig voneinander mehrere Gedanken, was sich für offene Schritte eignet, oder schlägt in einem Prompt eine Liste unterschiedlicher Optionen vor. Das vermeidet Duplikate, wenn die Auswahl begrenzt ist.
• Zustandsbewerter: Wie der Fortschritt beurteilt wird. Das Modell bewertet jeden Zustand für sich, etwa danach, ob das Ziel „sicher“, „vielleicht“ oder „unmöglich“ erreichbar ist, oder stimmt für den besten von mehreren Zuständen. Diese Bewertungen dienen als Suchheuristik. Bei klassischer Suche übernimmt eine von Hand geschriebene Bewertungsfunktion diese Aufgabe.
• Suchalgorithmus: Wie der Baum durchsucht wird. Bei der Breitensuche bleiben auf jeder Ebene die besten b Zustände erhalten. Bei der Tiefensuche wird der vielversprechendste Zweig verfolgt, vom Bewerter ausgeschlossene Zustände werden verworfen und der Algorithmus geht bei Bedarf zurück.

Beispiel: Game of 24#

Bei Game of 24 müssen vier Zahlen mithilfe von +, -, x und / zu 24 kombiniert werden, wobei jede Zahl genau einmal verwendet wird. ToT teilt die Lösung in drei Schritte auf, jeweils eine Gleichung, die zwei Zahlen zusammenführt. Für die Eingabe 4 9 10 13 schlägt ein Prompt zur Kandidatengenerierung unter anderem Folgendes vor:

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

Der Bewertungs-Prompt fragt dann, ob jede verbleibende Zahlenmenge noch 24 ergeben kann. „4 4 10“ ist sicher, da (10 - 4) x 4 = 24 gilt. Das Gleiche gilt für „6 9 13“, da (13 - 9) x 6 = 24 gilt. „10 13 13“ und „9 10 52“ sind dagegen unmöglich. Deshalb erweitert die Suche nur die ersten beiden Zweige. Beim ersten ergibt 10 - 4 = 6 (übrig: 4 6), dann 4 x 6 = 24.

In den Experimenten der Arbeit mit 100 schwierigen Aufgaben behielt die Breitensuche pro Schritt die fünf besten Zustände bei und bewertete jeden Zustand dreimal. ToT mit GPT-4 löste 74 % der Aufgaben, verglichen mit 7,3 % bei direktem Prompting, 4,0 % bei Chain-of-Thought und 9,0 % bei Chain-of-Thought mit Selbstkonsistenz. Selbst die beste von 100 gezogenen Gedankenkette erreichte nur 49 %. ToT, bei dem pro Schritt nur ein Zustand erhalten blieb, erreichte 45 %.

Wo Tree of Thoughts zum Einsatz kommt#

ToT hilft bei Problemen, bei denen frühe Entscheidungen spätere einschränken und sich ein falscher erster Schritt nur schwer korrigieren lässt: Rätsel, Planung und mehrstufige Mathematik. Bei 5x5-Minikreuzworträtseln füllte ToT mit Tiefensuche und Zurückschneiden 60 % der Wörter korrekt aus und löste 4 von 20 Rätseln. Der Nachteil ist der Rechenaufwand: Jede Ebene des Baums erfordert mehrere Aufrufe für Generierung und Bewertung. Eine einzige Antwort kann daher Dutzende oder mehr Modellaufrufe und deutlich mehr Tokens als eine einzelne Gedankenkette benötigen, was die Inferenzlatenz entsprechend erhöht.

Dieselbe Schleife aus Generieren, Bewerten und Erweitern findet sich in deutlich gröberer Form bei der automatisierten Suche nach Experimenten, zum Beispiel bei der Hyperparameteroptimierung. Mit Ask AI in Ultralytics Platform AutoTrain (Ultralytics Platform AutoTrain) lassen sich mehrere Ultralytics-YOLO-Modelle trainieren, die sich in einer Einstellung unterscheiden, etwa bei Bildgrößen von 640, 800 und 960. Anschließend können die abgeschlossenen Trainingsläufe anhand ihrer Validierungs-mAP50-95 verglichen und auf Grundlage des besten Ergebnisses weitere Experimente vorgeschlagen werden.

Tree of Thoughts und verwandte Methoden#

• Chain-of-Thought-Prompting: Ein einzelner Gedankengang, gleichbedeutend mit einem Baum, der pro Ebene nur einen Zweig hat.
• ReAct-Prompting: Verknüpft Schlussfolgerungen mit Aktionen in einer externen Umgebung, etwa Suchvorgängen oder Tool-Aufrufen, und setzt den Vorgang anhand der zurückgegebenen Ergebnisse fort. ToT durchsucht die eigenen Gedankenvorschläge des Modells.
• Selbstkonsistenz: Zieht mehrere vollständige Gedankengänge und ermittelt die endgültige Antwort durch Mehrheitsentscheid, ohne die einzelnen Schritte unterwegs zu bewerten.
• Graph of Thoughts: Verallgemeinert den Baum zu einem Graphen, in dem Gedanken auch zusammengeführt und verfeinert werden können, und erzielte eine um 62 % bessere Sortierqualität als ToT bei über 31 % niedrigeren Kosten.
• Monte-Carlo-Baumsuche (MCTS): Der Suchalgorithmus hinter AlphaGo, der das Erkunden neuer Zweige gegen das Ausnutzen vielversprechender Zweige abwägt und die Breitensuche oder Tiefensuche über Gedanken ersetzen kann.
• Reasoning-Modelle: Sie werden mit bestärkendem Lernen darauf trainiert, lange Schlussfolgerungsketten in einem einzigen Generierungsschritt zu schreiben. ToT bezieht Verzweigungen und Rücksprünge dagegen über ein externes Suchprogramm, das ein gewöhnliches Modell ergänzt.