STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks

Die Arbeit stellt STRUCTUREDAGENT vor, ein hierarchisches Planungsframework, das dynamische UND/ODER-Bäume und ein strukturiertes Gedächtnis nutzt, um die Leistung von LLM-basierten Agenten bei komplexen Web-Aufgaben mit langem Zeithorizont durch verbesserte Planung und Nachverfolgung von Lösungen zu steigern.

Das Wesentliche

🌐 Der digitale Detektiv mit einem perfekten Plan: STRUCTUREDAGENT

Stell dir vor, du beauftragst einen sehr intelligenten, aber etwas vergesslichen und ungeduldigen Assistenten, eine komplexe Aufgabe im Internet zu erledigen. Zum Beispiel: „Finde mir ein veganes Schokoladenbrownie-Rezept mit mindestens 4 Sternen, das unter 10 Minuten Zubereitungszeit liegt und glutenfrei ist."

Ein normaler KI-Assistent (ein sogenannter „Web-Agent") würde wahrscheinlich so vorgehen:

1. Er sucht nach „veganes Brownie".
2. Er klickt auf das erste Ergebnis.
3. Oh nein, es ist nicht glutenfrei.
4. Der Assistent wird verwirrt, vergisst, dass er eigentlich glutenfrei suchte, und klickt vielleicht auf etwas anderes, das gar nichts damit zu tun hat. Oder er gibt frustriert auf, weil er den Überblick verloren hat.

Das Problem ist: Der Assistent hat kein gutes Gedächtnis für den gesamten Weg, keinen echten Plan und neigt dazu, voreilig aufzugeben, sobald er auf ein Hindernis stößt.

Hier kommt STRUCTUREDAGENT ins Spiel. Es ist wie ein erfahrener Architekt und Bauleiter, der den Assistenten anleitet.

1. Der Bauplan: Der AND/OR-Baum 🌳

Statt einfach drauflos zu klicken, baut STRUCTUREDAGENT einen riesigen, gedanklichen Baum aus Plänen.

• Der Stamm (Das Ziel): „Finde das perfekte Brownie-Rezept."
• Die Äste (UND-Knoten): Damit der Stamm steht, müssen alle Äste stark sein. Das bedeutet: Das Rezept muss gleichzeitig vegan SEIN UND glutenfrei SEIN UND schnell sein. Wenn einer fehlt, ist der ganze Plan gescheitert.
• Die Gabelungen (ODER-Knoten): Hier hat der Assistent die Wahl. „Wie finde ich glutenfreie Rezepte?"
  • Option A: Suche direkt auf einer glutenfreien Seite.
  • Option B: Filtere die normalen Ergebnisse nach „glutenfrei".
  • Der Assistent probiert erst Option A. Wenn das scheitert, geht er sofort zu Option B über, ohne zu verzweifeln.

Die Metapher: Stell dir das wie ein Labyrinth vor. Ein normaler Agent läuft blind in eine Sackgasse und bleibt dort stecken. STRUCTUREDAGENT zeichnet eine Karte. Wenn er eine Sackgasse sieht, streicht er sie auf der Karte durch (das nennt man „Pruning") und läuft sofort den nächsten markierten Pfad weiter. Er weiß genau, wo er war und welche Wege nicht funktionieren.

2. Das Notizbuch: Strukturiertes Gedächtnis 📓

Normalerweise schreiben KI-Assistenten ihre Gedanken in einen langen, unordentlichen Textblock. Das ist wie ein Notizblock, auf dem jemand wild herumgekritzt hat.

STRUCTUREDAGENT nutzt eine strukturierte Tabelle (wie ein Excel-Sheet).

• Spalte 1: Kandidaten (Rezept A, Rezept B).
• Spalte 2: Ist es vegan? (Ja/Nein).
• Spalte 3: Ist es glutenfrei? (Ja/Nein).
• Spalte 4: Bewertung.

Wenn der Assistent ein neues Rezept findet, trägt er es sofort ein. Wenn er sieht, dass Rezept A nicht glutenfrei ist, streicht er es in der Tabelle durch. So vergisst er nie, dass er eigentlich glutenfrei sucht. Er behält den Überblick über alle Kandidaten, die er gesehen hat, nicht nur über den, auf dem er gerade steht.

3. Der menschliche Eingriff: Wenn der Assistent feststeckt 🛑

Manchmal ist die Aufgabe so knifflig, dass die KI den Plan falsch versteht.

• Beispiel: Die KI denkt, sie müsse erst die Zutaten kaufen, bevor sie das Rezept findet.
• Die Lösung: STRUCTUREDAGENT erlaubt es einem Menschen, in den Baum einzugreifen. Der Mensch kann sagen: „Moment, das ist falsch! Streiche diesen Ast und füge hier einen neuen ein: 'Finde zuerst das Rezept'."
  Das ist wie ein Bauleiter, der auf die Baustelle kommt, sieht, dass die Mauern schief stehen, und den Plan korrigiert, bevor das ganze Haus einstürzt.

Warum ist das so wichtig?

Frühere KIs waren wie Autofahrer ohne Navi: Sie fahren los, wenn sie in eine Sackgasse kommen, drehen sie oft im Kreis oder geben auf.

STRUCTUREDAGENT ist wie ein Autofahrer mit einem perfekten Navi und einem Co-Piloten:

1. Er plant die Route im Voraus (der Baum).
2. Er merkt sich, welche Straßen gesperrt sind (das strukturierte Gedächtnis).
3. Er kann die Route dynamisch ändern, wenn eine Straße gesperrt ist (Reparatur des Plans).
4. Er gibt nicht auf, bis er das Ziel erreicht hat.

Das Ergebnis

In Tests (wie beim Einkaufen auf Amazon oder beim Suchen von Informationen im Web) hat sich gezeigt, dass dieser strukturierte Ansatz viel besser funktioniert als die alten Methoden. Die KI macht weniger Fehler, findet die richtigen Produkte auch bei vielen Einschränkungen und kann komplexe Aufgaben lösen, bei denen andere Assistenten längst aufgegeben hätten.

Kurz gesagt: STRUCTUREDAGENT macht aus einem chaotischen, vergesslichen KI-Assistenten einen disziplinierten, planenden und lernfähigen Profi, der genau weiß, wohin er geht und was er tun muss.

Technische Zusammenfassung

1. Problemstellung

Trotz der Fortschritte bei Large Language Models (LLMs) stoßen bestehende Web-Agenten bei komplexen, langfristigen Aufgaben (Long-Horizon Tasks) im Internet an ihre Grenzen. Die Hauptprobleme sind:

• Begrenztes Kontextgedächtnis: Agenten können alternative Lösungspfade über mehrere Webseiten hinweg nicht effektiv verfolgen, da Webseiten oft sehr umfangreich sind (bis zu 20.000 Tokens) und Agenten meist nur den aktuellen Kontext berücksichtigen.
• Schwache Planungsfähigkeiten: Es fehlt die Fähigkeit, komplexe Pläne über lange Zeiträume zu konstruieren und auszuführen.
• Fehlende Fehlerbehandlung: Agenten haben oft keine robusten Mechanismen, um von Fehlern zu erholen oder alternative Lösungen zu erkunden.
• Greedy-Verhalten: Agenten neigen dazu, Aufgaben vorzeitig abzubrechen, ohne alle Benutzerbedingungen erfüllt zu haben, da sie oft nur den nächsten optimalen Schritt wählen, anstatt das globale Ziel zu verfolgen.

Menschliches Problemlösen basiert hingegen auf heuristischer Suche und Mittel-Ziel-Analyse (Means-Ends Analysis), bei der komplexe Aufgaben rekursiv in handhabbare Teilprobleme zerlegt werden. Diese Fähigkeit fehlt aktuellen Web-Agenten.

2. Methodik: STRUCTUREDAGENT

Das Paper stellt STRUCTUREDAGENT vor, ein hierarchisches Planungsframework, das Planung und Ausführung interleaved (verschachtelt) durchführt. Es basiert auf zwei Kernkomponenten:

A. Dynamische AND/OR-Bäume (Hierarchischer Planer)

Der Agent konstruiert und verwaltet dynamisch einen Planungsbaum während der Ausführung. Dieser Baum besteht aus drei Knotentypen:

• AND-Knoten: Repräsentieren konjunktive Teilziele. Alle Kinder müssen erfolgreich sein, damit der Elternknoten erfolgreich ist. Die Ausführung kann eine feste Reihenfolge erfordern.
• OR-Knoten: Repräsentieren alternative Strategien für ein Teilziel. Sobald ein Kind erfolgreich ist, gilt der OR-Knoten als erfüllt.
• ACTION-Knoten: Blätter des Baums, die konkrete Browser-Aktionen darstellen (z. B. Tippen, Klicken, Scrollen, Notizen machen).

Suchalgorithmus:
Der Agent verwendet eine modifizierte, gierige Tiefensuche (Greedy Depth-First Search, DFS) zur Expansion des Baums. Im Gegensatz zur klassischen DFS auf einem statischen Graphen wird der Baum hier inkrementell aufgebaut und angepasst.

• Zustände: Knoten durchlaufen drei Zustände: ENTERING (noch nicht verarbeitet), EXITING (Verarbeitung abgeschlossen) und FAILED (Fehler aufgetreten).
• Fehlerbehandlung: Wenn ein Knoten fehlschlägt, wird er in den FAILED-Zustand versetzt. Das System versucht dann, den Knoten zu reparieren (z. B. durch Hinzufügen neuer Kinder oder Änderung der Strategie) oder ihn zu beschneiden (Pruning), wenn keine Reparatur möglich ist. Fehler propagieren nach oben im Baum.
• Rolle des LLM: Das LLM fungiert nicht als alleiniger Planer, sondern wird nur für spezifische, lokal definierte Operationen aufgerufen (z. B. Knotenerweiterung, Reparatur, Überprüfung der Vollständigkeit). Das Framework verwaltet die Baumstruktur selbst. Dies erhöht die Interpretierbarkeit und Robustheit.

B. Strukturiertes Gedächtnis (Structured Memory)

Für informationsorientierte Aufgaben (z. B. Produktsuche mit mehreren Constraints) führt das Framework ein strukturiertes Gedächtnismodul ein.

• Es extrahiert Constraints aus der Aufgabenbeschreibung und organisiert potenzielle Kandidaten (z. B. Produkte) in einer dynamischen Tabelle.
• Jede Zeile repräsentiert eine Entität mit Spalten für Constraints, Attribute und Notizen.
• Während der Exploration fügt, aktualisiert oder löscht das LLM Einträge basierend auf neuen Beobachtungen.
• Bei Entscheidungen (z. B. in OR-Knoten) werden die Top-K Kandidaten abgerufen, die die meisten Constraints erfüllen, um redundante Exploration zu vermeiden.

3. Wichtige Beiträge

1. Hierarchisches Planungsframework: Einführung eines Systems, das Inferenzzeit-Planung über geordnete AND/OR-Bäume ermöglicht. Dies unterstützt zusammengesetztes Schlussfolgern, dynamische Planrevision und Fehler-Rückpropagation.
2. Interpretierbarkeit: Durch die explizite Baumstruktur sind die Entscheidungswege des Agents transparent. Dies ermöglicht menschliches Eingreifen (Human-in-the-Loop), um fehlerhafte Teilziele zu korrigieren, bevor die Ausführung fortgesetzt wird.
3. Strukturiertes Gedächtnis: Entwicklung eines Moduls zur Verfolgung von Kandidaten-Entitäten und deren Constraint-Erfüllung, was die Erfolgsrate bei komplexen Suchaufgaben signifikant erhöht.
4. Robuste Fehlerbehandlung: Das System unterstützt systematische Revision und Beschneidung von Plänen, was Agenten befähigt, aus Fehlern zu lernen und alternative Pfade zu erkunden, anstatt abzubrechen.

4. Ergebnisse

Die Autoren evaluieren STRUCTUREDAGENT auf drei Benchmarks:

• WebVoyager: Ein Datensatz mit 129 realen Web-Aufgaben.
• WebArena: Ein realistisches Web-Umfeld mit 630 Aufgaben (Kategorien: Map, Shopping, Reddit, GitLab).
• Custom Shopping Benchmark: 60 komplexe Amazon-Shopping-Aufgaben mit detaillierten natürlichen Sprach-Constraints.

Ergebnisse:

• Leistung: STRUCTUREDAGENT übertrifft starke Baselines (wie AgentOccam, BasicClaudeAction, SteP) konsistent.
  • Auf Amazon Easy erreicht es eine Erfolgsrate von 83,3 % (vs. 69,2 % bei AgentOccam).
  • Auf Amazon Hard (schwierige, mehrstufige Aufgaben) liegt es bei 35,6 % (vs. 28,4 % bei AgentOccam) und schneidet bei menschlicher Evaluation noch besser ab.
  • Auf WebArena erreicht es die höchste Gesamtleistung (52,6 %), mit besonderer Stärke bei Shopping- und Reddit-Aufgaben.
• Robustheit: Das System zeigt eine bessere Fähigkeit, komplexe Constraints über lange Trajektorien hinweg zu erfüllen.
• Effizienz: Zwar benötigt STRUCTUREDAGENT auf sehr schwierigen Aufgaben etwas mehr Aktionen (Exploration), aber dies führt zu einer höheren Erfolgsquote im Vergleich zu Agenten, die frühzeitig scheitern.
• Generalisierung: Die Vorteile des Frameworks bleiben auch bei Verwendung verschiedener Backbone-Modelle (Claude 3.5, Claude 3.7, Kimi-k2) erhalten.

5. Bedeutung

STRUCTUREDAGENT adressiert eine kritische Lücke in der Entwicklung autonomer Web-Agenten. Es beweist, dass die Kombination aus expliziter hierarchischer Planung (AND/OR-Bäume) und strukturierter Informationsverwaltung (Structured Memory) die Grenzen aktueller LLM-basierter Agenten überwinden kann.

Die Arbeit zeigt, dass die Trennung von Planungslogik (Framework) und Ausführung (LLM) zu robusteren, fehlertoleranteren und interpretierbaren Systemen führt. Dies ist ein wichtiger Schritt hin zu zuverlässigen Agenten für reale Anwendungen wie E-Commerce, Forschung und Workflow-Automatisierung, wo die Einhaltung komplexer Constraints und die Fähigkeit, aus Fehlern zu lernen, entscheidend sind. Zudem bietet das Framework eine Schnittstelle für menschliche Intervention, was die Sicherheit und Kontrolle in kritischen Szenarien erhöht.