💬 NLP

On Time, Within Budget: Constraint-Driven Online Resource Allocation for Agentic Workflows

Dieser Artikel stellt Monte Carlo Portfolio Planning (MCPP) vor, einen leichtgewichtigen Closed-Loop-Planer, der die Wahrscheinlichkeit optimiert, agentische Workflows innerhalb expliziter Budget- und Fristenbeschränkungen abzuschließen, indem er Modelle und parallele Stichproben basierend auf simulierten Ergebnissen dynamisch zuweist.

Ursprüngliche Autoren: Xinglin Wang, Zishen Liu, Shaoxiong Feng, Peiwen Yuan, Yiwei Li, Jiayi Shi, Yueqi Zhang, Chuyi Tan, Ji Zhang, Boyuan Pan, Yao Hu, Kan Li

Veröffentlicht 2026-05-08

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Xinglin Wang, Zishen Liu, Shaoxiong Feng, Peiwen Yuan, Yiwei Li, Jiayi Shi, Yueqi Zhang, Chuyi Tan, Ji Zhang, Boyuan Pan, Yao Hu, Kan Li

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Manager eines Bauarbeitsteams, das mit dem Bau eines komplexen Hauses betraut ist (der Agente Workflow). Sie haben eine strikte Regel: Das Haus muss bis Freitag um 17 Uhr fertiggestellt sein (die Frist), und Sie dürfen nicht mehr als 10.000 Dollar ausgeben (das Budget).

Ihr Team besteht aus verschiedenen Spezialisten (den Modellen): einige sind schnell, aber teuer, andere langsam, aber billig, und wieder andere sind ein Glücksspiel. Der Bauplan ist eine Karte, die zeigt, welche Räume vor anderen gebaut werden müssen (die Abhängigkeiten).

Der alte Weg: „Optimierung des Durchschnitts"

Früher versuchten Forscher, den „perfekten" Spezialisten für jede Aufgabe basierend auf einem Durchschnittswert zu finden. Sie fragten: „Welcher Arbeiter bietet im Durchschnitt das beste Gleichgewicht aus Geschwindigkeit, Kosten und Qualität?"

Das Problem: Dies ist so, als würde man ein Team basierend auf seinem Lebenslauf einstellen und es dann ohne Plan für den Fall, dass es regnet oder ein Arbeiter kündigt, zur Baustelle schickt. Selbst wenn Sie die „besten Durchschnittsarbeiter" einstellen, könnten Sie bis Mittwoch das Geld ausgegeben haben oder die Freitag-Frist verpassen, weil Sie das spezifische Chaos dieses Auftrags nicht berücksichtigt haben.

Der neue Weg: „Einschränkungsgetriebene Online-Allokation"

Diese Arbeit stellt einen neuen Ansatz vor, der MCPP (Monte Carlo Portfolio Planning) genannt wird. Anstatt nur den „besten" Arbeiter auszuwählen, agiert MCPP wie ein superkluger, Echtzeit-Projektmanager, der ständig basierend auf dem, was tatsächlich passiert, neu plant.

So funktioniert MCPP, unter Verwendung einfacher Analogien:

1. Der „Was-wäre-wenn"-Simulator (Monte Carlo)

Bevor eine Entscheidung getroffen wird, rätselt MCPP nicht einfach. Es führt Tausende von simulierten Filmen des restlichen Bauprojekts in seinem Kopf durch.

Szenario A: „Wenn ich den teuren, schnellen Arbeiter für die Küche einsetze, habe ich dann noch genug Geld übrig, um das Dach rechtzeitig fertigzustellen?"
Szenario B: „Wenn ich den billigen, langsamen Arbeiter für die Küche einsetze, werden wir dann die Frist verpassen?"

Es simuliert diese Ergebnisse immer wieder, um zu sehen, welcher Pfad die höchste Wahrscheinlichkeit hat, das gesamte Haus innerhalb der 10.000 Dollar und der Freitag-Frist fertigzustellen.

2. Das „Portfolio" von Strategien

MCPP betrachtet nicht nur eine Art, Dinge zu tun. Es hält ein Portfolio verschiedener Strategien bereit:

Die konservative Strategie: „Setze den billigen Arbeiter ein und hoffe auf das Beste."
Die aggressive Strategie: „Gib jetzt viel Geld aus, um Geschwindigkeit zu garantieren."
Die hybride Strategie: „Setze den schnellen Arbeiter für die schwierigen Teile und den billigen Arbeiter für die einfachen Teile ein."

Es testet jede mögliche Kombination dieser Strategien gegen die verbleibende Zeit und das verbleibende Geld.

3. Die „Neu-Plan"-Schleife (Geschlossener Regelkreis)

Dies ist der wichtigste Teil. MCPP erstellt nicht zu Beginn einen Plan und hält sich daran.

Schritt 1: Es wählt die beste Aktion jetzt sofort basierend auf den Simulationen aus.
Schritt 2: Es führt diese Aktion in der realen Welt aus.
Schritt 3: Es beobachtet, was passiert. Hat der Arbeiter Erfolg gehabt? Hat es länger gedauert als erwartet? Hat es mehr gekostet?
Schritt 4: Es führt die Simulationen sofort mit der neuen Realität neu durch und wählt die neue beste Aktion für den nächsten Schritt aus.

Es ist wie ein Navi, das Ihnen nicht nur einmal eine Route gibt, sondern den gesamten Pfad jedes Mal neu berechnet, wenn Sie in einen Stau geraten oder eine Umleitung nehmen, und sicherstellt, dass Sie trotzdem um 17 Uhr mit dem verbleibenden Geld ankommen.

Warum dies wichtig ist

Die Arbeit testete dies an zwei Arten von „Bauvorhaben":

CodeFlow: Schreiben von Computercode, bei dem ein Schritt vom vorherigen abhängt.
ProofFlow: Lösen komplexer mathematischer Beweise, bei denen Schritte einer logischen Kette folgen müssen.

Die Ergebnisse:
Wenn Budget und Zeit knapp waren (die „harten" Einschränkungen), war MCPP viel besser darin, den Auftrag zu beenden als die alten Methoden.

Alte Methoden liefen oft aus Geld oder Zeit aus, weil sie sich nicht an die spezifische Situation anpassten.
MCPP navigierte erfolgreich durch die engen Einschränkungen, indem es Geld für die „Engpass"-Aufgaben (die schwierigsten Teile des Hauses) sparte und weniger für die einfachen Teile ausgab.

Das Fazit

Die Arbeit argumentiert, dass wir in der realen Welt nicht nur einen Agenten wollen, der „allgemein effizient" ist. Wir wollen einen Agenten, der ein spezifisches Ergebnis garantiert: „Können Sie diesen spezifischen Auftrag bis Freitag für unter 100 Dollar fertigstellen?"

MCPP antwortet öfter mit „Ja" als frühere Methoden, indem es ständig die Zukunft simuliert, sich an die Realität anpasst und bei jedem einzelnen Schritt des Prozesses kluge Kompromisse zwischen Geschwindigkeit, Kosten und Risiko trifft. Es verwandelt einen starren Plan in eine flexible, lebendige Strategie, die das Chaos der realen Ausführung übersteht.

Technische Zusammenfassung: Constraint-gesteuerte Online-Ressourcenzuweisung für agentische Workflows

Problemdefinition

Die Arbeit adressiert eine kritische Lücke beim Einsatz agentischer Systeme: den Übergang von der Optimierung durchschnittlicher Performance-Kosten-Latenz-Frontiers zur Erfüllung harter, instanzspezifischer Constraints. Während neuere Arbeiten die Effizienz von Agenten durch Optimierung des Trade-offs zwischen Performance, Kosten und Latenz verbessern, erfordern reale Einsätze oft, dass ein spezifischer Workflow innerhalb eines strikten Budgets ( $B$ ) und einer festen Frist ( $D$ ) abgeschlossen wird.

Das Kernproblem ist die constraint-gesteuerte Online-Ressourcenzuweisung. Gegeben ein von Abhängigkeiten strukturierter Workflow (ein gerichteter azyklischer Graph, bei dem Knoten Teilaufgaben und Kanten Abhängigkeiten darstellen), muss ein Executor Ressourcen (Wahl der Basismodelle und paralleler Sampling-Breiten) dynamisch für aktuell ausführbare Teilaufgaben zuweisen. Das Ziel ist nicht die Minimierung durchschnittlicher Kosten oder Latenz, sondern die Maximierung der Wahrscheinlichkeit, dass der gesamte Workflow erfolgreich abgeschlossen wird, sodass die Gesamtkosten $\le B$ und die Gesamtzeit $\le D$ sind.

Dies wird als stochastisches Online-Zuweisungsproblem mit endlichem Horizont formuliert. Der Zustand wird durch die Menge der abgeschlossenen Teilaufgaben, das verbleibende Budget und die verbleibende Zeit definiert. Die Herausforderung liegt in der kombinatorischen Explosion möglicher Ausführungspfade, stochastischer Ergebnisse (Erfolg/Misserfolg von Teilaufgaben) und der Interdependenz des Ressourcenverbrauchs über den gesamten Workflow hinweg. Eine statische Zuweisung von Modellen oder Sampling-Strategien ist unzureichend, da die optimale Entscheidung vom sich entwickelnden Zustand, den verbleibenden Constraints und beobachteten stochastischen Ereignissen abhängt.

Methodik: Monte-Carlo-Portfolio-Planung (MCPP)

Um dieses unlösbare Optimierungsproblem zu bewältigen, schlagen die Autoren Monte-Carlo-Portfolio-Planning (MCPP) vor, einen leichten, geschlossenen Regelkreis-Planer.

1. Problemformulierung

Der Workflow wird modelliert als $I = (G, M, \Phi, B, D)$ , wobei $G$ der Teilaufgaben-Graph ist, $M$ die Menge verfügbarer Modelle darstellt und $\Phi$ geschätzte Erfolgswahrscheinlichkeiten ( $p_{v,m}$ ) und erwartete Generierungslängen ( $\ell_{v,m}$ ) für jedes Teilaufgaben-Modell-Paar enthält.
Das Ziel ist es, eine Policy $\pi$ zu finden, die maximiert:
$J(\pi) = \Pr_{\pi} (T_{solve} \le D, C_{\pi} \le B)$
Exakte dynamische Programmierung ist theoretisch möglich, aber aufgrund des exponentiellen Zustandsraums (Kombinationen abgeschlossener Teilaufgaben) und des Aktionsraums (Modell- und Sampling-Breiten-Wahlen für alle bereiten Knoten) rechnerisch unlösbar.

2. Der MCPP-Algorithmus

MCPP approximiert die optimale Entscheidungsregel mittels eines einstufigen Portfolio-Rollout-Backups:

Kandidaten-Aktionsmenge: In jedem Zustand konstruiert der Planer eine Menge von Kandidatenaktionen $\tilde{A}(s)$ . Diese Menge umfasst spezifische Zuweisungen für bereite Knoten und wird durch ein Portfolio einfacher Fortsetzungspolicies $\Pi_0$ erweitert. Jede Policy im Portfolio ist eine „Retry- $k$ "-Strategie, die einem bestimmten Modell $m$ und einer Sampling-Breite $k$ alle zukünftigen ausführbaren Teilaufgaben zuweist.
Monte-Carlo-Schätzung: Für jede Kandidaten-Aktions $a$ schätzt der Planer ihren Wert, indem er die Workflow-Ausführung simuliert. Er wendet $a$ an, sampelt das stochastische Ergebnis (welche Teilaufgaben erfolgreich sind), aktualisiert den Zustand und folgt dann jeder Fortsetzungspolicy $\mu \in \Pi_0$ , bis der Workflow abgeschlossen ist oder Constraints verletzt werden.
Auswahl: Der Wert der Aktion $a$ wird als maximale Erfolgswahrscheinlichkeit über alle Fortsetzungspolicies im Portfolio geschätzt: $\hat{Q}_{\Pi_0}(s, a) = \max_{\mu \in \Pi_0} \hat{Q}_{\mu}(s, a)$ . Die Aktion mit dem höchsten geschätzten Wert wird zur Ausführung ausgewählt.
Geschlossener Regelkreis-Wiederplanung: Nach Ausführung der gewählten Aktion und Beobachtung der tatsächlichen Ergebnisse aktualisiert der Planer den Zustand (verbleibendes Budget, Zeit und abgeschlossene Teilaufgaben) und plant neu. Dies ermöglicht dem System, sich in Echtzeit an stochastische Ausfälle und Ressourcenverbrauch anzupassen.

3. Theoretische Garantien

Die Arbeit liefert eine „Safe-Improvement"-Analyse. Sie beweist, dass die MCPP-Policy, bis auf Fehler durch endliche Monte-Carlo-Stichproben, Approximationsfehler der Kandidatenmenge und Schätzfehler bei Erfolgsraten/Längen, eine constrained completion probability liefert, die mindestens so hoch ist wie die der besten Baseline-Policy im Portfolio. Dies stellt sicher, dass der Planer niemals schlechter abschneidet als eine einfache, statische Strategie (wie die durchgängige Verwendung desselben Modells und derselben Sampling-Breite), während er gleichzeitig das Potenzial für signifikante Gewinne durch Vorausplanung bietet.

Hauptbeiträge

Problemformulierung: Die Autoren führen das Setting der constraint-gesteuerten Online-Ressourcenzuweisung ein und verschieben das Ziel von der Optimierung durchschnittlicher Effizienz-Frontiers hin zur Maximierung der Wahrscheinlichkeit, harte Budget- und Frist-Constraints für spezifische Workflow-Instanzen zu erfüllen.
Algorithmus-Vorschlag: Sie schlagen MCPP vor, einen geschlossenen Regelkreis-Planer, der die constrained completion probability direkt durch simulierte Rollouts schätzt und basierend auf beobachteten Ergebnissen neu plant. Er vermeidet exhaustive dynamische Programmierung, indem er ein Portfolio einfacher Fortsetzungspolicies zur Approximation zukünftiger Werte nutzt.
Empirische Validierung: Die Methode wird an zwei von Abhängigkeiten strukturierten Benchmarks evaluiert: CodeFlow (Code-Generierung und -Verifikation) und ProofFlow (formales Schließen und Beweisgenerierung).
Robustheitsanalyse: Die Arbeit zeigt, dass MCPP auch dann effektiv bleibt, wenn die Eingabeschätzungen (Erfolgswahrscheinlichkeiten und Generierungslängen) verrauscht sind, ein häufiges Szenario in realen Einsätzen.

Experimentelle Ergebnisse

Experimente wurden an den Benchmarks CodeFlow und ProofFlow unter verschiedenen Budget- ( $B$ ) und Frist- ( $D$ ) Constraints durchgeführt.

Performance: MCPP übertraf konsistent starke Baselines, darunter Uniform (statische Budgetzuweisung über Teilaufgaben) und Retry (lokales Online-Wiederholen ohne Downstream-Planung).
Strikte Constraints: Die Verbesserung war unter strengen Constraints am signifikantesten (z. B. $B = \$ 0,05$). MCPP konnte hohe Erfolgsraten schnell erreichen, sobald die Frist moderat machbar wurde, während Baselines deutlich niedriger blieben.
Aktionsvielfalt: Ablationsstudien zeigten, dass sich die Performance mit größeren Modell-Portfolios (Nutzung mehrerer Modelle) und reichhaltigeren Rollout-Breiten-Portfolios (Variation der Sampling-Breiten) verbessert. Dies unterstreicht die Bedeutung der Auswahl des richtigen Modells und der richtigen Rechenintensität für spezifische Knoten und Zustände anstelle der Verwendung einer einzigen globalen Strategie.
Robustheit: Unter verrauschten Schätzungen der Erfolgsraten (Gaußsches Rauschen mit $\sigma=0,3$ ) zeigte MCPP eine Degradation von nur ca. 6 Prozentpunkten und demonstrierte somit Resilienz gegenüber unvollkommenen Profil-Schätzungen.
Skalierbarkeit: Die Methode skaliert effektiv auf größere Workflows (mehr Teilaufgaben) und behält ihren Vorteil gegenüber Baselines, insbesondere in eingeschränkten Szenarien, in denen statische Zuweisungen versagen, sich an Zwischenresultate anzupassen.
Effizienz: Der Online-Planungsaufwand ist moderat (typischerweise unter 5 Sekunden für Standardkonfigurationen), was sie für die Echtzeit-Ausführung praktikabel macht.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass ihre primäre Bedeutung in der Adressierung der instanzspezifischen Erfolgsbedingung realer agentischer Einsätze liegt. Während frühere Arbeiten auf die Verbesserung der „Performance-Kosten-Latenz-Frontier" (durchschnittliche Effizienz) fokussierten, behandelt diese Arbeit Budget und Zeit als harte Constraints, die Erfolg oder Misserfolg definieren.

Die Autoren argumentieren, dass eine bessere Frontier nicht automatisch zu einer besseren Aktionspolicy unter spezifischen Constraints führt. MCPP überbrückt diese Lücke, indem es direkt die Wahrscheinlichkeit optimiert, die spezifischen $B$ - und $D$ -Anforderungen des Nutzers zu erfüllen. Die Arbeit bescheiden behauptet, dass MCPP eine sichere Verbesserung gegenüber Baseline-Policies bietet und konsistente Gewinne in eingeschränkten Umgebungen demonstriert, ohne globale Optimalität zu beanspruchen oder das allgemeine Problem der Workflow-Generierung zu lösen (was als separate vorgelagerte Aufgabe behandelt wird). Die Arbeit wird als praktischer Löser für die Ausführungsphase agentischer Systeme positioniert, unter der Annahme, dass die Workflow-Struktur und statistische Profile verfügbar sind.