LATS: Language Agent Tree Search — Schlussfolgern, Handeln und Planen in einem Framework

Ich habe darüber nachgedacht, was nach Tree of Thoughts kommt – wenn man über Denkschritte suchen kann, warum dann nicht auch über Aktionen? Genau das tut LATS (Language Agent Tree Search), und deshalb lese ich es gerade. Das Paper von Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang und Yu-Xiong Wang (ICML 2024, arXiv:2310.04406) ist die bisher klarste Synthese aus Schlussfolgern (Reasoning), Handeln (Acting) und Planen (Planning) in einem einzigen Agenten-Framework, und die Ergebnisse sind wirklich schwer von der Hand zu weisen.

Das Paper

Das Kernproblem, das LATS adressiert, ist eine strukturelle Lücke in früheren Arbeiten zu Agenten. ReAct verzahnt Reasoning und Acting, hat aber keinen Mechanismus, um umzukehren und einen anderen Pfad zu versuchen, wenn eine Trajektorie schiefläuft. Tree of Thoughts ermöglicht Verzweigungen über Denkschritte, operiert aber auf internem LM-Wissen – es kann keine Tools aufrufen oder externes Feedback innerhalb der Suche empfangen. Reflexion fügt verbale Selbstkorrektur hinzu, aber seine lineare Retry-Schleife bedeutet, dass es sich auf eine neue Trajektorie festlegt, ohne Alternativen zu erkunden. LATS verschmilzt alle drei Ideen mit einem echten Monte Carlo Tree Search (MCTS) Rückgrat, was es LLM-Agenten ermöglicht, mehrere Zweige zu erkunden, echtes Umweltfeedback zu erhalten und zurückzukehren (Backtracking), wenn ein Pfad fehlschlägt.

Die technische Maschinerie ist ein sechsstufiger MCTS-Loop: Selection (Auswahl des nächsten zu explorierenden Knotens via UCT-Formel), Expansion (Sampling von n Kandidatenaktionen aus dem LM), Evaluation (Bewertung jedes Knotens mit einer hybriden Value-Funktion), Simulation (Rollout bis zu einem Endzustand), Backpropagation (Aktualisierung der Ahnenwerte) und Reflection (bei Fehlern Generierung einer verbalen Zusammenfassung des Problems und Speicherung als Kontext). Die Value-Funktion verdient Beachtung: V(s) = λ·LM(s) + (1−λ)·SC(s), wobei LM(s) die eigene Schätzung des LMs über die Qualität der Trajektorie nach Erhalt des Umweltfeedbacks ist und SC(s) ein Self-Consistency-Score basierend darauf, wie oft diese Aktion über Geschwisterknoten hinweg gesampelt wird. Dies ist kein trainiertes Reward-Modell – die Value-Funktion ist vollständig Prompt-gesteuert.

Kernideen

• Bei HumanEval erreicht GPT-4 + LATS einen Pass@1 von 92,7 %, gegenüber 91,0 % für GPT-4 + Reflexion und 56,9 % für GPT-3.5 + ReAct allein. GPT-3.5 + LATS springt auf 83,8 %.
• Bei HotPotQA erreicht LATS (CoT + ReAct) ein Exact Match von 0,71 gegenüber 0,32 für die ReAct-Baseline – eine mehr als verdoppelte Genauigkeit beim Multi-Hop Reasoning.
• Bei WebShop (Web-Navigation + Einkauf) erzielt LATS 75,9 Punkte (Erfolgsquote 38,0 %) gegenüber Reflexion mit 64,2 (35,0 %) – eine bedeutende Lücke bei einer Aufgabe, die das Verwalten von Zuständen über viele Seiten hinweg erfordert.
• Beim Game of 24 (ein reines Logikrätsel) erreicht LATS eine Erfolgsquote von 0,44 gegenüber 0,20 bei ToT, trotz Verwendung desselben GPT-4-Backbones.
• Überraschenderweise expandiert LATS weniger Knoten, um eine Lösung zu finden, als ToT (durchschnittlich 66,65 vs. 84,05 Knoten bei HotPotQA mit k=50), und verbraucht weniger Token (173.290 vs. 210.215), obwohl es theoretisch teurer aussieht.

Was Bestand hat — und was nicht

Die Benchmark-Zahlen sind real und das Framework ist konzeptionell sauber. Die UCT-Formulierung bietet einen prinzipiellen Exploration-Exploitation-Tradeoff, der dem Ad-hoc-BFS/DFS in ToT fehlt. Die Integration von externem Umweltfeedback in die Value-Funktion – anstelle von reiner LM-Introspektion – ist der richtige Schritt, und die Ergebnisse zeigen es.

Dennoch steckt in dem Paper eine kritische Annahme, die die Autoren zwar anerkennen, aber nicht vollständig stresstesten: LATS erfordert die Fähigkeit, die Umgebung in einen früheren Zustand zurückzusetzen. Ohne Checkpointing kann man den Baum nicht verzweigen – sobald eine Aktion ausgeführt wurde, ist man festgelegt. Die Autoren merken an, dass dies bei LM-Aufgaben oft durch „Copy-Pasting historischer Texteingaben“ machbar ist, aber für reale Aktionsumgebungen (Datenbanken, Dateisysteme, APIs mit Seiteneffekten) ist dies eine harte Anforderung, die viele Produktionssysteme nicht erfüllen können. Die WebShop-Ergebnisse, obwohl besser als die Baselines, zeigen, dass in komplexen Umgebungen die Selbstreflexionen dazu neigen, generisch statt gezielt zu werden – Agenten können stecken bleiben und oberflächlich verschiedene, aber strukturell identische Fehler wiederholen. Das Paper stellt dies fest, bietet aber keine Lösung an.

Es gibt auch keine Ablationsstudie, die den Beitrag der MCTS-Struktur gegenüber dem Design der Value-Funktion isoliert. Es ist plausibel, dass ein einfacherer Verzweigungsansatz mit derselben hybriden Value-Funktion einen Großteil der Lücke schließen würde, und die Autoren testen dies nicht direkt.

Warum das für Finance-KI wichtig ist

Beancount-Hauptbücher sind aus einem Hauptgrund eine fast ideale Umgebung für LATS-ähnliche Baumsuche: Jedes Hauptbuch ist durch ein Git-Repository gesichert. Die Zustandsrückführung – die harte Anforderung, die LATS in vielen realen Szenarien unpraktisch macht – wird trivial durch git checkout oder git stash erfüllt. Ein Write-Back-Agent könnte Kandidaten für Journaleinträge über mehrere Zweige hinweg vorschlagen, sie gegen Bilanzbeschränkungen (die Value-Funktion) prüfen und nur den Pfad mit der höchsten Punktzahl committen. Fehlgeschlagene Zweige erhalten eine verbale Reflexion: „Der gebuchte Eintrag verletzte die Invariante Aktiva = Passiva + Eigenkapital, da der Kontotyp falsch klassifiziert wurde.“

Das hybride Design der Value-Funktion ist ebenfalls direkt anwendbar. Für einen Ledger-Agenten würde LM(s) einen vorgeschlagenen Eintrag basierend auf der semantischen Passgenauigkeit bewerten (sieht das nach der richtigen Kategorie aus?), während SC(s) verfolgen würde, wie konsistent der Agent ähnliche vergangene Transaktionen klassifiziert – ein natürlicher Self-Consistency-Check, der in der Historie des Hauptbuchs selbst verwurzelt ist.

Die Annahme der Zustandsrückführung ist der eine Punkt, an dem ich der Finanzanalogie widersprechen würde. Reale Hauptbücher haben oft nachgelagerte Effekte: Ein gebuchter Eintrag löst eine Rechnung aus, die wiederum einen Zahlungsworkflow auslöst. In diesen Fällen bricht die Annahme von LATS. Speziell für Beancount, wo das Hauptbuch eine reine Textdatei unter Git-Kontrolle ist und Änderungen lokal erfolgen, bevor ein nachgelagerter Trigger ausgelöst wird, hält die Annahme – aber dies ist eine Designeinschränkung, die man explizit im Auge behalten sollte.

Was man als Nächstes lesen sollte

• Planen auf MCTS-Basis ohne Umgebungsmodelle: „Reasoning with Language Model is Planning with World Model“ (Hao et al., 2023, arXiv:2305.14992) – RAP, auf dem LATS direkt aufbaut und das es übertrifft.
• Wie gut generalisiert die LM-Value-Funktion? „Let's Verify Step by Step“ (Lightman et al., 2023, arXiv:2305.20050) – Prozess-Reward-Modelle als Alternative zu Prompt-basierten Value-Funktionen.
• Sicheres mehrstufiges Planen unter Irreversibilität: „Decision-Making with Language Models via Successive Prompting“ (Creswell et al., 2023) – ein einfacherer Planungsansatz, der die Anforderung der Zustandsrückführung vermeidet.