📊 statistics

Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

Dieses Papier legt die mathematischen Warteschlangengrundlagen für LLM-Inferenz fest, beweist, dass arbeitserhaltende Scheduling-Algorithmen sowohl für individuelle als auch für KI-Agenten-Workloads den maximalen Durchsatz erreichen, und bewertet reale Systeme, um die Optimalität von Orca und Sarathi-Serve zu bestätigen sowie vor der Instabilität von FasterTransformer und vanilla vLLM zu warnen.

Ursprüngliche Autoren: J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

Veröffentlicht 2026-05-19

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

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 betreiben eine Hochgeschwindigkeitsfabrik, die maßgeschneiderte Roboter herstellt. In dieser Fabrik durchläuft jede Bestellung (eine „Anfrage") zwei klar getrennte Phasen:

Die Einrichtungsphase (Prefill): Sie lesen die Baupläne und sammeln alle notwendigen Teile. Dies ist eine schwere Arbeit, die viel Rechenkraft (Compute) erfordert, aber gleichzeitig in einem Durchgang erledigt wird.
Die Montagephase (Decode): Sie beginnen mit dem Zusammenbau des Roboters und fügen ein Teil nach dem anderen hinzu. Dies ist eine langsamere, speicherintensive Aufgabe, die schrittweise erfolgt.

Ihre Fabrik verfügt über einen riesigen, superschnellen Roboterarm (die GPU), der gleichzeitig an mehreren Bestellungen arbeiten kann. Der Arm hat jedoch eine Grenze: Er kann nur eine bestimmte Gesamtgewichtsmenge an Teilen gleichzeitig in seinem Greifer halten (das Token-Budget).

Das von Ihnen bereitgestellte Papier ist eine mathematische Studie darüber, wie man die Bestellungen organisiert, damit Ihre Fabrik niemals stillsteht und die maximal mögliche Anzahl von Robotern produziert, ohne dass es zu Verstopfungen kommt.

Hier ist die Aufschlüsselung ihrer Erkenntnisse mit einfachen Analogien:

1. Die Goldene Regel: „Lassen Sie den Arm nicht untätig warten"

Die wichtigste Entdeckung in diesem Papier ist ein Konzept namens „Work-Conserving" (Arbeitskonservierend).

Stellen Sie sich vor, Ihr Roboterarm ist bereit, Teile zu greifen.

Der schlechte Weg: Sie lassen den Arm nur dann „Einrichtungs"-Teile greifen, wenn ausschließlich Einrichtungs-Bestellungen warten. Wenn „Montage"-Bestellungen warten, ignoriert man sie, selbst wenn der Arm freien Platz hat. Oder man lässt ihn nur dann „Montage"-Teile greifen, wenn ausschließlich Montage-Bestellungen vorhanden sind.
- Ergebnis: Der Arm sitzt halb leer da und wartet auf eine bestimmte Art von Bestellung, während sich ein riesiger Haufen der anderen Art von Bestellung aufstaut. Die Fabrik verlangsamt sich oder stürzt ab.
Der gute Weg (Work-Conserving): Wenn der Arm Platz hat, füllen Sie ihn mit dem, was gerade verfügbar ist. Sie mischen Einrichtungs-Teile und Montage-Teile in derselben Charge. Sie lassen den Arm niemals untätig warten, wenn Arbeit zu erledigen ist.

Die Behauptung des Papiers: Algorithmen, die dieser „Fülle den Eimer"-Regel folgen (wie Orca und Sarathi-Serve), sind mathematisch bewiesen als die effizientesten. Sie können die maximal mögliche Arbeitsmenge bewältigen, ohne dass das System zusammenbricht.

2. Die „alten" vs. „neuen" Fabrikmanager

Die Autoren testeten vier beliebte „Manager" (Scheduling-Algorithmen), um zu sehen, wer der Goldenen Regel folgt:

FasterTransformer & Vanilla vLLM (Die strengen Manager): Diese Manager sind zu wählerisch.
- FasterTransformer greift nur Montage-Teile. Wenn keine Montage-Bestellungen vorhanden sind, ignoriert es die wartenden Einrichtungs-Bestellungen, selbst wenn der Arm leer ist.
- Vanilla vLLM greift nur Einrichtungs-Teile. Wenn keine Einrichtungs-Bestellungen vorhanden sind, ignoriert es die wartenden Montage-Bestellungen.
- Urteil: Diese sind nicht optimal. Unter hoher Last führen sie dazu, dass die Fabrik verstopft und instabil wird.
Orca & Sarathi-Serve (Die flexiblen Manager): Diese Manager mischen die beiden Arbeitsarten. Sie füllen den Arm mit dem, was passt.
- Urteil: Diese sind optimal. Sie halten die Fabrik bei maximaler Geschwindigkeit reibungslos am Laufen.

3. Die „KI-Agenten"-Fabrik (Komplexe Workflows)

Manchmal ist eine Bestellung nicht nur ein einzelner Roboter, sondern ein ganzes Team von Robotern, das zusammenarbeitet.

Der DAG (Gerichteter azyklischer Graph): Stellen Sie sich einen Workflow vor, bei dem Bestellung A zur Station 1, dann zur Station 2, dann zur Station 3 geht und niemals zurückkehrt.
- Erkenntnis: Solange der Workflow eine gerade Linie ist (keine Schleifen), funktioniert die Regel „Lassen Sie den Arm nicht untätig warten" auch über alle Stationen hinweg perfekt.
Die Gabel-Verbindung (Fork-Join): Stellen Sie sich vor, Bestellung A spaltet sich in drei Teilaufgaben auf, die zu drei verschiedenen Stationen gehen, und alle müssen fertig sein, bevor der letzte Schritt erfolgen kann.
- Erkenntnis: Die Regel „Lassen Sie den Arm nicht untätig warten" funktioniert auch hier.
Der Zyklus (Die Falle): Stellen Sie sich vor, Bestellung A geht zur Station 1, dann zur Station 2, aber Bestellung B geht von Station 2 zurück zur Station 1. Sie jagen sich in einem Kreis.
- Erkenntnis: Hier kann die Regel „Lassen Sie den Arm nicht untätig warten" versagen. Selbst wenn die Manager ihr Bestes geben, kann der kreisförmige Verkehr einen Stau verursachen, der sich nie auflöst. Das Papier zeigt, dass wenn Ihre Fabrik diese kreisförmigen Schleifen hat, Sie einen viel intelligenteren, vorsichtigeren Manager benötigen, nicht nur einen „Fülle-den-Eimer"-Manager.

4. Die „Eimer-Größe"-Überraschung

Es gibt eine zweite Grenze in der Fabrik: die Batch-Größe. Dies ist die maximale Anzahl an Bestellungen, die der Arm halten kann, unabhängig davon, wie schwer sie sind.

Die Überraschung: Die Autoren stellten fest, dass es manchmal tatsächlich eine schlechte Idee ist, den Arm bis zur absoluten Gewichtsgrenze (das Token-Budget) zu füllen.
Die Analogie: Stellen Sie sich einen Eimer vor, der 100 Pfund fasst. Sie haben 100 winzige Kieselsteine (Einrichtung) und 100 schwere Ziegelsteine (Montage).
- Wenn Sie versuchen, den Eimer mit Ziegelsteinen bis zu 100 Pfund zu füllen, passen vielleicht nur 5 Ziegelsteine hinein. Die Zeit, die zum Heben dieser schweren Last benötigt wird, ist lang.
- Wenn Sie jedoch bei 50 Pfund aufhören (eine kleinere Last), können Sie diese vielleicht viel schneller heben, was es Ihnen ermöglicht, mehr Fahrten pro Stunde zu unternehmen.
Die Erkenntnis: In bestimmten Situationen ist die effizienteste Strategie, das Füllen des Eimers vor dem Vollstand zu stoppen, um die Verarbeitungsgeschwindigkeit hoch zu halten. Das bedeutet, dass selbst die „guten Manager" (Work-Conserving) versagen können, wenn die Fabrikregeln (Batch-Größenlimits) zu streng sind und die Mischung der Bestellungen genau richtig ist, um einen Stau zu verursachen.

Zusammenfassung

Das Papier sagt uns:

Mischen Sie Ihre Arbeit: Trennen Sie Einrichtungs- und Montageaufgaben nicht. Mischen Sie sie in derselben Charge, um die GPU beschäftigt zu halten.
Orca und Sarathi-Serve sind die Gewinner: Sie folgen der „Mischen und Füllen"-Regel, was sie zur stabilsten und effizientesten Wahl für die meisten Situationen macht.
Achten Sie auf Schleifen: Wenn Ihre KI-Agenten Aufgaben zwischen Servern hin und her in einem Kreis senden, funktionieren einfache „Fülle-den-Eimer"-Regeln möglicherweise nicht; Sie benötigen eine spezielle Verkehrsregelung.
Voll ist nicht immer am besten: Manchmal ist es schlauer, etwas leeren Raum in Ihrer Charge zu lassen, als sie bis zum Rand zu füllen, abhängig davon, wie groß die einzelnen Aufgaben sind.

Das Ziel all dieser Mathematik ist es, Ingenieuren zu helfen, KI-Systeme zu bauen, die nicht abstürzen, wenn Millionen von Menschen gleichzeitig Fragen stellen.

Technische Zusammenfassung: Durchsatzoptimierte Scheduling-Algorithmen für LLM-Inferenz und KI-Agenten

Problemstellung

Da die Nachfrage nach Large Language Models (LLMs) und KI-Agenten wächst, ist die Optimierung von Inferenzsystemen hinsichtlich der Effizienz von entscheidender Bedeutung. Während erhebliche Ingenieursanstrengungen auf systemweite Verbesserungen gerichtet waren, fehlt es an einem kohärenten mathematischen Modellierungs- und Warteschlangentheorie-Rahmen zur Bewertung von Scheduling-Algorithmen. Insbesondere adressiert die Arbeit die fundamentale Frage: Was ist die maximale Durchsatzrate für ein LLM-Inferenzsystem, und welche Klassen von Scheduling-Algorithmen können dieses Limit erreichen?

Die LLM-Inferenz stellt im Vergleich zu klassischen Warteschlangensystemen einzigartige Herausforderungen dar:

Zweiphasige Verarbeitung: Anfragen durchlaufen eine rechenintensive Prefill-Phase (Verarbeitung von Eingabetokens zum Aufbau des KV-Caches), gefolgt von einer speicher-I/O-limitierten Decode-Phase (autoregressive Token-Generierung).
Batching-Beschränkungen: Um die GPU-Auslastung zu maximieren, werden Anfragen gebündelt. Das Mischen von Prefill- und Decodetokens erzeugt jedoch Interferenzen, und die Hardware setzt ein Token-Budget ( $b_{max}$ ) und oft eine Batch-Größenbeschränkung ( $k_{max}$ ) durch.
KI-Agenten-Workloads: Moderne Anwendungen umfassen Netzwerke von LLM-Servern, die komplexe Agentenaufgaben verarbeiten, welche Directed-Acyclic-Graph-(DAG)-Topologien, Fork-Join-Muster oder zyklisches Routing beinhalten können.

Bestehende Systeme setzen diverse Strategien ein (z. B. FasterTransformer, vLLM, Orca, Sarathi-Serve) mit unterschiedlichen Prioritäten (Prefill-first vs. Decode-first) und Batching-Fähigkeiten (gemischt vs. getrennt). Praktiker verlassen sich derzeit auf kostspielige, workloadspezifische Benchmarks, um Systeme auszuwählen, und verfügen über keine theoretische Garantie für Stabilität oder Durchsatzoptimalität.

Methodik

Die Autoren entwickeln ein rigoroses warteschlangentheoretisches Rahmenwerk, um LLM-Inferenzsysteme zu modellieren.

1. Stochastische Modellierung

Basis-Modell: Das System wird als diskreter Markov-Kette (DTMC) modelliert, die eine Batch-Service-Warteschlange mit zwei Klassen darstellt.
- Klassen: Anfragen existieren entweder in einer Prefill-Warteschlange oder einer Decode-Warteschlange.
- Batching: Der Server verarbeitet einen Batch von Tokens aus beiden Warteschlangen gleichzeitig, unterliegt jedoch einem Token-Budget $b_{max}$ .
- Asymmetrie: Prefill-Tokens einer einzelnen Anfrage können im Bulk verarbeitet werden, während Decodetokens strikt sequenziell sind (einer pro Anfrage pro Batch).
Verarbeitungszeit-Modell: Unter Ausnutzung empirischer Spuren wird die Batch-Verarbeitungszeit $t_b$ durch eine stückweise konstante Funktion angenähert, die von der Token-Last $b$ abhängt:
$t_b = c + a \cdot \lceil b/b_0 \rceil$
wobei $c$ die Grundkosten und $a$ die Grenzkosten pro Block von $b_0$ Tokens darstellen. Dieses Modell erfasst die Dominanz linearer Schichtberechnungen in der LLM-Inferenz.

2. Analytisches Rahmenwerk

Fluid-Limit-Technik: Die Autoren nutzen das Fluid-Limit-Rahmenwerk (Dai 1995, Stolyar 1995), um die Stabilität zu analysieren. Sie beweisen, dass unter spezifischen Bedingungen der skalierte stochastische Prozess gegen ein deterministisches Fluid-Modell konvergiert.
Stabilitätsdefinition: Ein System ist stabil (positiv rekurrent), wenn die Gesamtzahl der unverarbeiteten Tokens nicht divergiert, wenn die Zeit gegen Unendlich geht.
Scheduling-Klasse: Die Analyse konzentriert sich auf arbeitserhaltende (work-conserving) Algorithmen (die den Batch so weit wie möglich auf die Kapazität $b_{max}$ auffüllen) und führt die K-FCFS-Bedingung (First-Come-First-Served mit begrenztem Überholen) ein, um die Komplexitäten des gemischten Batchings zu handhaben.

3. Erweiterungen

Das Rahmenwerk wird erweitert auf:

Parallele Server: Systeme mit Lastverteilung (Random oder Join-the-Shortest-Queue).
Multi-Klassen-Netzwerke: Einzelne Server, die mehrere Anfrageklassen verarbeiten (z. B. verschiedene Agentenschritte).
Netzwerk-Topologien: Multi-Server-Netzwerke mit DAG-Routing und Fork-Join-Synchronisation.
Zyklisches Routing: Analyse von Netzwerken mit Feedback-Schleifen (Rybko–Stolyar-Typ).
Batch-Größenbeschränkungen: Analyse von Systemen, die sowohl durch ein Token-Budget ( $b_{max}$ ) als auch durch eine maximale Batch-Größe ( $k_{max}$ ) eingeschränkt sind.

Hauptbeiträge und Ergebnisse

1. Durchsatzoptimalität arbeitserhaltender Scheduling-Verfahren

Die Arbeit etabliert ein fundamentales Designprinzip: Arbeitserhaltende Scheduling-Algorithmen erreichen den maximalen Durchsatz für Single-Server-LLM-Inferenz und Netzwerke mit DAG- oder Fork-Join-Topologien.

Satz 2: Für einen einzelnen Server stabilisiert jeder arbeitserhaltende K-FCFS-Algorithmus das System, wenn die Ankunftsbelastung $\lambda(m_p + m_d)$ kleiner ist als die maximale Verarbeitungsrate $b_{max}/t_{b_{max}}$ . Umgekehrt ist das System unter jedem Algorithmus instabil, wenn die Last diesen Schwellenwert überschreitet.
Implikation: Dies liefert eine theoretische Obergrenze ( $b_{max}/t_{b_{max}}$ ) und validiert den Wandel in der Industrie hin zu arbeitserhaltenden Schedulern.

2. Bewertung bestehender Systeme

Die Anwendung des theoretischen Rahmens auf reale Algorithmen ergibt klare Klassifizierungen:

Durchsatzoptimal (Arbeitserhaltend):
- Orca: Unterstützt gemischtes Batching (Prefill + Decode) mit Prefill-Priorität.
- Sarathi-Serve: Unterstützt chunked Prefill mit Decode-Priorität und gemischtem Batching.
- Neuestes vLLM (mit chunked Prefill): Arbeitserhaltend.
Suboptimal/Instabil (Nicht arbeitserhaltend):
- FasterTransformer: Priorisiert Decode, verbietet aber gemischtes Batching. Es lässt die GPU untätig, wenn Decod-Anfragen nicht ausreichen, um einen Batch zu füllen, selbst wenn Prefill-Anfragen warten.
- Vanilla vLLM: Priorisiert Prefill, verbietet aber gemischtes Batching. Es lässt Decod-Anfragen warten, während es nur Prefill-Batches verarbeitet.
Experimentelle Validierung: Reale Spuren bestätigen, dass nicht arbeitserhaltende Algorithmen (FasterTransformer, Vanilla vLLM) unter moderaten Lasten instabil werden (Warteschlangen-Explosion), während arbeitserhaltende Algorithmen (Sarathi-Serve, Orca) stabil bleiben.

3. KI-Agenten-Workloads und Netzwerk-Topologien

DAG und Fork-Join: Die Arbeit beweist, dass arbeitserhaltendes Scheduling für Netzwerke von LLM-Servern in DAGs oder Fork-Join-Topologien durchsatzoptimal bleibt, sofern die Lastbedingung an jedem Server erfüllt ist.
Zyklisches Routing (Rybko–Stolyar-Gegenbeispiel): Die Autoren zeigen, dass arbeitserhaltendes Scheduling für Netzwerke mit zyklischem Routing nicht ausreicht. Sie konstruieren ein Zwei-Server-Netzwerk, bei dem spezifische Prioritätszuweisungen unter einer arbeitserhaltenden Politik zu Instabilität führen, selbst wenn die Gesamtlast unter der Kapazität liegt. Dies unterstreicht die Notwendigkeit sorgfältigen Prioritätsdesigns oder nicht arbeitserhaltender Politiken (z. B. Back-Pressure) in zyklischen Topologien.

4. Auswirkungen von Batch-Größenbeschränkungen

Wenn eine maximale Batch-Größenbeschränkung ( $k_{max}$ ) zusätzlich zum Token-Budget ( $b_{max}$ ) auferlegt wird:

Wird der Stabilitätsbereich zu einem zweidimensionalen konvexen Hüllkörper in der $(\lambda_{prefill}, \lambda_{decode})$ -Ebene, anstatt eines einfachen skalaren Schwellenwerts.
Gegenintuitive Erkenntnis: In bestimmten Regimen (insbesondere nahe einem Eckpunkt des Stabilitätsbereichs, der gemischte Batches betrifft), können strikt arbeitserhaltende Algorithmen, die immer bis $b_{max}$ auffüllen, das System nicht stabilisieren. Für optimale Stabilität kann es erforderlich sein, bei einer niedrigeren Token-Last (z. B. $b_0$ ) zu operieren, um die Verarbeitungsraten von Prefill- und Decodetokens auszugleichen. Dies legt nahe, dass unter engen Batch-Größenbeschränkungen adaptive Scheduling-Strategien notwendig sind.

Bedeutung und Behauptungen

Die Arbeit beansprucht, die erste rigorose warteschlangentheoretische Grundlage für LLM-Inferenz-Scheduling zu liefern. Ihre Bedeutung liegt in:

Designprinzip: Sie identifiziert „arbeitserhaltend" als ein Schlüsselprinzip für Praktiker, bietet theoretische Sicherheit, dass Algorithmen wie Sarathi-Serve und Orca durchsatzoptimal sind, und warnt vor nicht gemischten Batching-Ansätzen wie FasterTransformer und Vanilla vLLM.
Überbrückung von Communities: Sie senkt die Hürde für die Warteschlangentheorie-Community, zu LLM-Systemen beizutragen, indem sie ein formales Modell bereitstellt, das die einzigartigen zweiphasigen und Batching-Eigenschaften von LLMs erfasst.
Leitfaden für KI-Agenten: Sie erweitert die Stabilitätsanalyse auf KI-Agenten-Workloads und zeigt auf, dass zwar DAG-Topologien robust sind, zyklische Topologien jedoch anspruchsvollere Scheduling-Mechanismen als einfache arbeitserhaltende Politiken erfordern.
Nuancierte Beschränkungen: Sie offenbart, dass praktische Beschränkungen wie Batch-Größenlimits die Stabilitätsbereiche fundamental verändern können und die Annahme herausfordern, dass das „Auffüllen des Batches" immer optimal ist.

Die Autoren schließen, dass ihre Arbeit zwar eine Basis für Durchsatzoptimalität schafft, zukünftige Arbeiten jedoch die Latenzoptimierung, reichhaltigere Verarbeitungszeitmodelle (unter Einbeziehung von Attention-Schichten) und das Design adaptiver Algorithmen für komplexe Beschränkungen und Netzwerk-Topologien adressieren müssen.