Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints

Die vorgestellte Arbeit stellt ein robustes, batch-basiertes Routing-Framework für Large Language Models vor, das unter Berücksichtigung von Kosten- und Kapazitätsbeschränkungen die Zuweisung von Anfragen optimiert und dabei im Vergleich zu herkömmlichen Methoden sowohl die Genauigkeit als auch die Effizienz unter adversariellen Bedingungen signifikant steigert.

Das Wesentliche

Das große Problem: Der überforderte Kellner

Stell dir vor, du betreibst ein riesiges Restaurant mit vielen verschiedenen Köchen (das sind die KI-Modelle).

• Es gibt den Super-Koch (ein sehr großes, teures KI-Modell), der die besten Gerichte macht, aber extrem teuer ist und lange braucht.
• Es gibt den Schnellkoch (ein kleines, günstiges Modell), der einfache Gerichte schnell hinbekommt, aber bei komplizierten Rezepten versagt.

Bisher haben die meisten Restaurants so gearbeitet: Jeder Gast (jede Anfrage) wurde einzeln betrachtet. Wenn ein Gast kam, schaute der Kellner: „Ist das eine einfache Bestellung? Dann zum Schnellkoch. Ist es kompliziert? Zum Super-Koch."

Das Problem:
In der echten Welt kommen die Gäste nicht einzeln, sondern in Gruppen (Batches).

1. Die Kosten-Explosion: Wenn plötzlich 50 Gäste gleichzeitig kommen und alle wollen das komplizierteste Gericht, schickt der Kellner alle zum Super-Koch. Plötzlich ist die Küche überfüllt, die Rechnung explodiert, und die Wartezeit wird lang. Der Kellner hatte zwar für jeden Gast einzeln „gut" entschieden, aber für die Gruppe war es ein Desaster.
2. Die Unsicherheit: Manchmal denkt der Kellner, ein Gast sei einfach, aber der Gast stellt doch eine sehr schwierige Frage. Der Schnellkoch versagt dann.

Die Lösung: Der kluge Gruppen-Manager

Die Autoren dieses Papers schlagen vor, den Kellner zu ersetzen durch einen intelligenten Gruppen-Manager, der nicht nur auf den einzelnen Gast schaut, sondern auf die ganze Gruppe, die gerade hereinkommt.

Hier ist, wie ihr System funktioniert, mit ein paar Metaphern:

1. Der Gruppen-Planer (Batch-Level Routing)

Statt jeden Gast einzeln zu entscheiden, nimmt der Manager die ganze Gruppe (z. B. 100 Anfragen) und sagt:

„Okay, wir haben ein festes Budget und nur 5 Arbeitsplätze im Super-Koch-Bereich. Wir müssen die 100 Gäste so verteilen, dass alle zufrieden sind, aber wir das Budget nicht sprengen."

Er nutzt ein mathematisches Werkzeug (wie einen sehr schnellen Rechner), um die perfekte Mischung zu finden:

• Die 20 schwierigsten Gäste kommen zum Super-Koch.
• Die 80 einfachen Gäste kommen zum Schnellkoch.
• Ergebnis: Niemand wartet zu lange, das Budget wird nicht überschritten, und die Gesamtqualität ist höher als wenn jeder einzeln entschieden hätte.

2. Der Vorsichtsmann (Robustheit)

Manchmal ist der Manager nicht 100 % sicher, wie schwer eine Frage wirklich ist. Er könnte sich täuschen.

• Normaler Manager: „Ich denke, dieser Gast ist einfach." -> Schickt ihn zum Schnellkoch. -> Oh nein, der Gast war doch schwer!
• Robuster Manager (die neue Idee): „Ich bin mir nicht sicher. Wenn ich mich täusche, will ich nicht, dass der Gast unzufrieden ist."
  • Er schaut auf das schlechteste Szenario: „Was ist, wenn dieser Gast doch schwer ist?"
  • Er entscheidet dann lieber sicherheitshalber, den Gast zum besseren Koch zu schicken, oder verteilt die Gruppe so, dass auch im schlimmsten Fall niemand im Stich gelassen wird.
  • Vergleich: Es ist wie beim Packen eines Rucksacks für eine Wanderung. Ein optimistischer Wanderer packt nur Regenjacken, wenn die Sonne scheint. Ein robuster Wanderer packt trotzdem eine Jacke ein, falls es doch regnet – besser sicher als nass.

3. Der Chef-Küchenplaner (Ressourcen-Verteilung)

Bevor die Gäste überhaupt kommen, muss der Restaurantbesitzer entscheiden: Wie viele Arbeitsplätze (GPUs) stellen wir für welche Köche bereit?

• Sollen wir 10 Arbeitsplätze für den Schnellkoch und 1 für den Super-Koch haben?
• Oder umgekehrt?

Die Autoren haben eine Methode entwickelt, die vorher berechnet: „Basierend auf den typischen Bestellungen, die wir erwarten, lohnt es sich, mehr Arbeitsplätze für den Schnellkoch zu bauen." Das spart Geld und verhindert, dass der Super-Koch im Leerlauf steht oder der Schnellkoch überlastet ist.

Was haben sie herausgefunden? (Die Ergebnisse)

Sie haben das System an zwei großen Datensätzen getestet (wie zwei verschiedene Restaurant-Ketten) und folgende Dinge festgestellt:

1. Gruppenentscheidungen sind besser: Wenn man die ganze Gruppe plant, spart man bis zu 24 % an Kosten oder bekommt bei gleichem Budget viel bessere Ergebnisse als wenn man jeden Gast einzeln behandelt. Das ist besonders wichtig, wenn die Gäste „bösartig" gruppiert sind (alle schweren Fragen auf einmal).
2. Vorsicht zahlt sich aus: Der „vorsichtige" (robuste) Manager macht weniger Fehler. Wenn die Vorhersagen unsicher sind, verbessert er die Qualität um bis zu 14 %, weil er keine riskanten Entscheidungen trifft.
3. Ressourcen-Planung hilft: Wenn man vorher genau berechnet, wie viele Arbeitsplätze man braucht, gewinnt man nochmal 3 % an Qualität dazu.

Zusammenfassung für den Alltag

Stell dir vor, du organisierst eine große Party.

• Die alte Methode: Du sagst jedem Gast einzeln: „Geh zu dieser Musikgruppe." Wenn plötzlich alle zur teuren Band wollen, hast du ein Problem.
• Die neue Methode: Du schaust auf die ganze Liste der Gäste, weißt, wie viel Geld du hast und wie viele Plätze die Bands haben. Du planst im Voraus, wer zu welcher Band geht, damit die Party läuft, das Geld reicht und niemand unzufrieden ist – selbst wenn du nicht genau weißt, wie die Stimmung wird.

Dieses Paper zeigt also, wie man KI-Systeme nicht nur für den einzelnen Moment, sondern für den ganzen Tag (die ganze Gruppe von Anfragen) effizient, günstig und sicher betreibt.

Technische Zusammenfassung

1. Problemstellung

Große Sprachmodelle (LLMs) erfordern erhebliche Rechenressourcen für die Inferenz. Das Ziel des LLM-Routings ist es, einfache Anfragen an günstigere Modelle und komplexe Anfragen an leistungsfähigere Modelle zu leiten, um eine Balance zwischen Antwortqualität und Kosten zu finden.

Bisherige Ansätze operieren jedoch meist anfragebasiert (per-query). Das Paper identifiziert fundamentale Mängel dieser Methoden im praktischen Einsatz:

• Fehlende Batch-Kontrolle: In der Praxis werden Anfragen gebündelt (Batching), um Hardware effizient zu nutzen. Per-Query-Routing ignoriert die Interdependenzen innerhalb eines Batches. Dies führt dazu, dass bei nicht-uniformer oder adversarischer Verteilung schwieriger Anfragen die Kosten pro Batch stark schwanken und Budgets überschritten werden können.
• Ressourcenbeschränkungen: Herkömmliche Methoden berücksichtigen oft nicht strikte Kapazitätsgrenzen (z. B. Anzahl verfügbarer GPU-Instanzen für lokale Modelle) oder die Unterschiede zwischen lokalen und Cloud-basierten Bereitstellungen.
• Unsicherheit: Die Schätzung der Modellleistung ($l(q, m_j)$) ist fehlerbehaftet. Per-Query-Methoden führen oft zu übermütigen Entscheidungen, wenn die Schätzungen ungenau sind.

2. Methodik

Die Autoren schlagen einen Batch-Level-Routing-Framework vor, das auf Integer Linear Programming (ILP) basiert und drei Hauptkomponenten umfasst:

A. Batch-Level-Optimierung (Online)

Statt jede Anfrage einzeln zu optimieren, wird für einen Batch von $N$ Anfragen und $M$ Modellen ein ILP gelöst:

• Zielfunktion: Maximierung der durchschnittlichen Routing-Qualität über den gesamten Batch.
• Nebenbedingungen:
  1. Kosten: Die Gesamtkosten des Batches dürfen ein festes Budget $C$ nicht überschreiten.
  2. Kapazität: Die Anzahl der Anfragen pro Modell darf die Kapazität der verfügbaren Instanzen ($l_j \cdot I_j$) nicht überschreiten.
  3. Zuweisung: Jede Anfrage wird genau einem Modell zugewiesen.
• Lösung: Das Problem wird effizient mit Standard-ILP-Lösern (z. B. SCIP) in Millisekunden gelöst, was für den Echtzeiteinsatz geeignet ist.

B. Robuste Optimierung (Uncertainty-Aware)

Um Unsicherheiten in den Leistungsschätzungen zu adressieren, wird eine robuste Variante eingeführt:

• Anstatt mit Punktschätzungen zu arbeiten, werden Vorhersageintervalle (z. B. durch Bootstrap-Resampling geschätzt) verwendet.
• Das Optimierungsziel wird geändert: Statt der erwarteten Leistung wird die untere Schranke des Intervalls (Worst-Case-Szenario) maximiert.
• Dies verhindert katastrophale Fehler, wenn die Leistungsschätzung zu optimistisch war, und bevorzugt Modelle mit geringerer Vorhersagevarianz.

C. Offline-Instanzen-Allokation

Bevor die Inferenz beginnt, wird ein separates Optimierungsproblem gelöst, um die Anzahl der zu deployenden Modellinstanzen ($I_j$) für lokale Modelle zu bestimmen:

• Ziel ist es, die GPU-Ressourcen so auf verschiedene Modelle zu verteilen, dass die erwartete Gesamtleistung über zukünftige Batches maximiert wird, unter Einhaltung des GPU-Budgets.
• Dies schließt die Lücke zwischen der statischen Ressourcenplanung und dem dynamischen Routing.

3. Wichtige Beiträge

1. Identifikation von Schwächen: Nachweis, dass Per-Query-Routing unter Batch-Bedingungen und strikten Ressourcenbeschränkungen versagt (hohe Kostenvarianz, Budget-Überschreitungen).
2. Robustes Framework: Einführung eines ILP-basierten Frameworks, das Kosten- und Kapazitätsbeschränkungen explizit erzwingt und Unsicherheiten durch robuste Optimierung berücksichtigt.
3. Ressourcen-Allokation: Untersuchung und Optimierung der Zuweisung lokaler Rechenressourcen (GPUs) zu Modellen vor der Inferenz.
4. Modellunabhängigkeit: Das Framework ist kompatibel mit beliebigen Leistungsschätzern (z. B. XGBoost, kNN, MIRT).

4. Ergebnisse

Die Experimente wurden auf zwei Multi-Task-LLM-Benchmarks durchgeführt:

• Robustheit: Robuste Routings (basierend auf XGBoost oder kNN mit Bootstrap) verbesserten die Genauigkeit um 1–14 % gegenüber nicht-robusten Gegenstücken, abhängig vom verwendeten Schätzer. Robuste Methoden wählten konsistent Modelle mit geringerer Unsicherheit aus.
• Batch-Level vs. Per-Query:
  • Unter zufälliger Batch-Bildung erzielte das Batch-Level-Optimierung bis zu 4 % (Dataset 1) bzw. 1,7 % (Dataset 2) bessere Leistung.
  • Unter adversarieller Batch-Bildung (gezielt schwierige Anfragen gebündelt) übertraf das Batch-Level-Verfahren Per-Query-Methoden um bis zu 24 %, da es Budgets effizienter über den Batch verteilt und Spitzenkosten vermeidet.
• Optimierte Instanzen-Allokation: Die datenabhängige Optimierung der GPU-Instanzen führte zu weiteren Gewinnen von bis zu 3 % im Vergleich zu festen Allokationen, insbesondere bei knappen Budgets.
• Gesamtoptimierung: Das kombinierte System (Offline-Allokation + Online-Robust-Routing) übertraf State-of-the-Art-Baselines wie MIRT und einzelne starke Modelle (z. B. DeepSeek_Chat), während es gleichzeitig weniger GPUs und geringere Kosten benötigte.

5. Bedeutung und Fazit

Das Paper demonstriert, dass LLM-Routing nicht als isoliertes Per-Query-Problem betrachtet werden darf, sondern als systemisches Optimierungsproblem unter Batch-Bedingungen.

• Praktische Relevanz: Der Ansatz ermöglicht es Unternehmen, strikte Budgets und Hardware-Limits einzuhalten, ohne Qualitätseinbußen zu riskieren, selbst bei unvorhersehbaren Anfrageströmen.
• Robustheit: Durch die Berücksichtigung von Unsicherheit wird das System widerstandsfähiger gegen Fehlschätzungen der Modellleistung.
• Effizienz: Die Kombination aus Offline-Ressourcenplanung und Online-Batch-Optimierung maximiert den Nutzen vorhandener Hardware (GPUs) und reduziert die Abhängigkeit von teuren Cloud-APIs.

Zusammenfassend bietet das vorgestellte Framework einen systematischen Weg, um LLM-Inferenz in industriellen Umgebungen kosteneffizient, ressourcenbewusst und qualitativ hochwertig zu skalieren.