HEXGEN-FLOW: Optimizing LLM Inference Request Scheduling for Agentic Text-to-SQL

Die Arbeit stellt HEXGEN-FLOW vor, ein Framework, das durch einen hierarchischen Scheduler und eine adaptive Prioritätswarteschlange die Latenz verringert und den Durchsatz für agentic Text-to-SQL-Anfragen auf heterogenen GPU-Clustern signifikant verbessert.

Das Wesentliche

Stell dir vor, du hast einen sehr klugen, aber etwas langsamen Koch (den KI-Modell-LLM), der dir helfen soll, eine komplexe Bestellung in einer Datenbank zu verstehen und in eine präzise Anweisung (SQL) zu übersetzen. Das Problem ist: Dieser Koch arbeitet nicht in einem Schritt. Er muss erst das Menü lesen, dann verschiedene Rezepte vorschlagen, diese ausprobieren, Fehler korrigieren und am Ende das beste Rezept auswählen.

Das ist wie eine Kette von Aufgaben, bei der der nächste Schritt erst beginnen kann, wenn der vorherige fertig ist.

Jetzt stell dir vor, du betreibst ein riesiges Restaurant mit vielen verschiedenen Küchen (heterogene GPUs). Manche Küchen sind hochmoderne Luxus-Küchen mit schnellen Herden (starke Grafikkarten wie A100), andere sind etwas ältere, gemütliche Küchen (ältere Grafikkarten wie L40).

Das Problem:
Bisherige Systeme (wie vLLM oder Ray) behandeln jeden Auftrag wie einen einzelnen, unabhängigen Burger. Sie sagen: "Nächster Kunde, bitte an die nächste freie Küche!" Das funktioniert gut für einfache Bestellungen, aber bei unserer komplexen Datenbank-Anfrage führt das zu Chaos:

1. Ein wichtiger Schritt landet in einer langsamen Küche und verzögert den ganzen Prozess.
2. Wichtige, dringende Anfragen warten, weil eine langsame Anfrage gerade den Herd blockiert.
3. Die Kunden (Nutzer) warten zu lange, bis sie ihre Antwort bekommen.

Die Lösung: HEXGEN-FLOW
Die Autoren dieses Papers haben HEXGEN-FLOW entwickelt. Man kann sich das wie einen super-organisierten Restaurantmanager vorstellen, der zwei Ebenen hat:

1. Der globale Manager (Der Dispatcher)

Statt einfach nur "nächste freie Küche" zu rufen, schaut sich dieser Manager genau an:

• Was muss getan werden? Ist es eine schwere Aufgabe (wie das Erstellen von SQL-Vorschlägen) oder eine leichte (wie das Überprüfen)?
• Welche Küche ist geeignet? Die schwere Aufgabe wird sofort in die Luxus-Küche (A100) geschickt. Die leichte Aufgabe darf in die gemütlichere Küche (L40), damit die teure Küche nicht mit Kleinigkeiten blockiert wird.
• Wie voll ist die Küche? Er schaut, wo gerade Stau ist, und leitet den Auftrag dorthin, wo er am schnellsten durchkommt.

Analogie: Stell dir vor, du hast einen Paketdienst. Ein schwerer Kühlschrank wird nicht zu einem kleinen Lieferwagen geschickt, der ihn kaum tragen kann. Er geht zum großen LKW. Ein kleiner Brief geht zum kleinen Boten. HEXGEN-FLOW macht genau das für KI-Aufgaben.

2. Der lokale Küchenchef (Die lokale Warteschlange)

Sobald ein Auftrag in einer Küche ist, gibt es dort eine Warteschlange. Früher warteten alle einfach in der Reihenfolge ihres Eintreffens (First-Come-First-Served).
HEXGEN-FLOW ändert das: Der Küchenchef schaut auf die Dringlichkeit.

• Wenn ein Auftrag schon lange wartet und bald sein Zeitlimit (SLO) verpasst, rutscht er nach vorne, auch wenn er später gekommen ist als andere.
• Er berechnet ständig: "Wie viel Zeit haben wir noch? Wie lange dauert der nächste Schritt?" und passt die Reihenfolge dynamisch an.

Analogie: Stell dir eine Warteschlange beim Arzt vor. Normalerweise wartet man in der Reihenfolge des Eintreffens. Aber wenn jemand einen Herzinfarkt hat (hohe Dringlichkeit), wird er sofort behandelt, auch wenn er erst vor 5 Minuten kam. HEXGEN-FLOW erkennt, welche KI-Aufgabe "Herzinfarkt" hat (Zeitdruck) und lässt sie vor.

Das Besondere: Der "Selbstlern-Modus" (Alpha-Tuning)

Das System ist nicht starr. Es hat einen kleinen Simulator im Hintergrund, der wie ein Testkochen funktioniert.

• Das System probiert aus: "Was passiert, wenn wir mehr Gewicht auf die Geschwindigkeit der Küche legen und weniger auf die Warteschlange?"
• Es misst, ob die Kunden zufriedener sind (weniger Wartezeit).
• Wenn es regnet (hoher Andrang) oder die Küche wechselt, passt sich der Manager automatisch an und ändert seine Strategie, ohne dass jemand eingreifen muss.

Das Ergebnis

In Tests hat sich gezeigt, dass HEXGEN-FLOW viel schneller ist als die bisherigen Systeme:

• Die Wartezeit für die langsamsten Anfragen (die "Schwänze" der Verteilung) wurde um fast 50% bis 60% reduziert.
• Die Anzahl der bearbeiteten Anfragen pro Sekunde (Durchsatz) stieg um fast das Doppelte.

Zusammenfassend:
HEXGEN-FLOW ist wie ein intelligenter Verkehrsleiter für KI-Aufgaben. Er sorgt dafür, dass schwere Lasten auf starke Schultern gelegt werden, dringende Aufgaben Vorrang haben und sich das System ständig selbst optimiert. So können auch komplexe Datenbank-Fragen von KI-Agenten schnell und zuverlässig beantwortet werden, egal wie unterschiedlich die Hardware im Hintergrund ist.

Technische Zusammenfassung

1. Problemstellung

Die Einführung von agentic Large Language Models (LLMs) hat die Text-to-SQL-Fähigkeit (Übersetzung natürlicher Sprache in SQL) erheblich verbessert, indem sie nicht-Experten den Zugriff auf Datenbanken ermöglicht. Ein typischer agenter Workflow besteht jedoch aus mehreren voneinander abhängigen Stufen (Schema-Linking, SQL-Kandidatengenerierung, Selbstkorrektur, Evaluation), die eine sequenzielle Abfolge von LLM-Inferenzanfragen erfordern.

Das zentrale Problem liegt in der Bereitstellung (Serving) dieser Workflows in Produktionsumgebungen:

• Abhängigkeiten: Spätere Stufen können erst beginnen, wenn vorherige abgeschlossen sind. Verzögerungen in frühen Stufen kaskadieren und gefährden die End-to-End-Latenz.
• Heterogenität: Enterprise-Cluster nutzen oft gemischte GPU-Hardware (z. B. A100, L40, A6000) mit unterschiedlichen Rechenkapazitäten.
• Service Level Objectives (SLOs): Verschiedene Benutzer haben unterschiedliche Latenzanforderungen. Bestehende Frameworks (wie vLLM, TGI) sind primär für unabhängige, einzelne Inferenzaufgaben ausgelegt und berücksichtigen weder die Workflow-Abhängigkeiten noch die End-to-End-Deadlines effektiv. Dies führt zu suboptimaler Leistung und häufigen SLO-Verletzungen.

2. Methodik: HEXGEN-FLOW

HEXGEN-FLOW ist ein Framework, das speziell für die Scheduling und Ausführung von agentic Text-to-SQL-Workflows auf heterogenen GPU-Clustern entwickelt wurde. Es basiert auf einer zweistufigen Architektur:

A. Globale Koordination (Workload-Balanced Dispatching)

Ein zentraler Koordinator verteilt eingehende LLM-Inferenzanfragen auf verschiedene Modell-Instanzen.

• Ziel: Ausgewogene Lastverteilung unter Berücksichtigung der Hardware-Heterogenität.
• Mechanismus: Der Koordinator schätzt die Ausführungszeit einer Anfrage auf jeder Instanz (basierend auf Input/Output-Token-Längen) und berücksichtigt die aktuelle Warteschlangenlänge.
• Dispatching-Strategie: Eine nicht-lineare Heuristik bewertet Instanzen basierend auf einem Score, der die geschätzte Rechenzeit und die Warteschlangenverzögerung gewichtet. Ein Hyperparameter $\alpha$ steuert das Gleichgewicht zwischen schneller Ausführung (Wahl der leistungsstärksten Hardware) und Lastverteilung (Vermeidung von Staus).

B. Lokale Prioritätswarteschlangen (Urgency-Driven Scheduling)

Jede GPU-Instanz verwaltet ihre eigene lokale Warteschlange.

• SLO-Budget-Allokation: Das End-to-End-SLO eines gesamten Text-to-SQL-Queries wird dynamisch auf die einzelnen Stufen verteilt. Das verbleibende Budget wird basierend auf der verstrichenen Zeit und den geschätzten Kosten der verbleibenden Stufen neu berechnet.
• Dringlichkeitsmetrik (Urgency): Anfragen werden nicht nach „First-Come-First-Served" (FCFS), sondern nach ihrer Dringlichkeit sortiert. Die Dringlichkeit $U$ berechnet sich aus der Differenz zwischen der geschätzten Ausführungszeit und dem verbleibenden SLO-Budget. Anfragen, die kurz vor einem SLO-Verstoß stehen, erhalten Vorrang.
• Dynamische Anpassung: Sobald eine Stufe abgeschlossen ist, wird das verbleibende Budget für die nachfolgenden Stufen neu berechnet, um den Druck auf nachgelagerte Aufgaben zu erhöhen, falls Verzögerungen aufgetreten sind.

C. Simulation-basierte Feinabstimmung ($\alpha$-Tuning)

Um den optimalen Wert für den Dispatching-Hyperparameter $\alpha$ zu finden, nutzt HEXGEN-FLOW einen leichten, trace-getriebenen Simulator.

• Der Simulator repliziert historische Workloads, um verschiedene $\alpha$-Werte zu testen.
• Basierend auf der P95-Latenz (Tail Latency) wird $\alpha$ online angepasst, um sich an wechselnde Workloads und Hardware-Konfigurationen anzupassen.

3. Schlüsselbeiträge

1. Formalisierung von Designprinzipien: Die Autoren identifizieren drei Kernprinzipien für das Serving agenter Text-to-SQL-Workflows: explizites Management von Mehrstufen-Abhängigkeiten, heterogenitätsbewusste Ressourcenallokation und End-to-End-SLO-Garantien in Multi-Tenant-Umgebungen.
2. Entwicklung von HEXGEN-FLOW: Ein neues Framework, das globale Lastverteilung mit lokaler, dringlichkeitsgesteuerter Priorisierung kombiniert, um SLOs auf heterogenen Clustern einzuhalten.
3. Umfassende Evaluation: Demonstration der Überlegenheit gegenüber dem State-of-the-Art durch Experimente mit realistischen Workloads (BIRD-Bench, Spider) und verschiedenen Hardware-Setups.

4. Ergebnisse

Die Evaluation wurde auf realistischen Traces (Financial, Formula1, Spider) mit verschiedenen GPU-Konfigurationen (heterogen und homogen) durchgeführt und verglichen mit Baselines wie vLLM, VTC, QLM, LLF und Ray Serve.

• Latenzreduktion: HEXGEN-FLOW reduziert die P95-Tail-Latenz um den Faktor 1,42 bis 1,56 im Vergleich zu bestehenden Frameworks.
• Durchsatzsteigerung: Der Systemdurchsatz steigt um den Faktor 1,49 bis 1,81.
• SLO-Einhaltung: Unter strengen SLO-Bedingungen erreicht HEXGEN-FLOW eine deutlich höhere SLO-Einhaltungsrate (SLO Attainment) als alle Vergleichssysteme.
• Robustheit: Das System zeigt starke Leistung auch bei schwankenden Workloads (nicht-stationäre Ankunftsraten), hoher Last (bis zu 30 QPS) und in Multi-Tenant-Szenarien mit unterschiedlichen SLOs für verschiedene Benutzer.
• Ablationsstudie: Sowohl die globale Lastverteilung (WB) als auch die lokale Prioritätswarteschlange (PQ) tragen signifikant zur Gesamtverbesserung bei. Der Wegfall einer Komponente führt zu messbaren Einbußen.

5. Bedeutung und Fazit

HEXGEN-FLOW adressiert eine kritische Lücke in der Infrastruktur für generative KI: Die effiziente Bereitstellung komplexer, mehrstufiger Agenten-Workflows auf heterogener Hardware.

• Praktische Relevanz: Da Unternehmen zunehmend auf gemischte GPU-Cluster setzen, bietet HEXGEN-FLOW einen Weg, diese Ressourcen optimal zu nutzen, ohne die Latenzanforderungen zu verletzen.
• Skalierbarkeit: Der Ansatz ist skalierbar und kann auf andere agentic DAGs (Directed Acyclic Graphs) übertragen werden.
• Innovation: Durch die Kombination von globalem Load-Balancing mit lokaler Deadline-Awareness und dynamischer Budget-Neuzuweisung bietet das System einen neuen Standard für das Serving von LLM-basierten Anwendungen, die über einfache Textgenerierung hinausgehen.

Zusammenfassend beweist HEXGEN-FLOW, dass eine spezialisierte Scheduling-Strategie, die die spezifischen Abhängigkeiten und Anforderungen von agentic Text-to-SQL-Workflows berücksichtigt, signifikant bessere Leistung und Zuverlässigkeit im Vergleich zu generischen LLM-Serving-Frameworks erzielt.