Warum klassisches Load Balancing bei LLM-Inference versagt

Warum Round Robin und Least Connections bei LLM-Inference scheitern

Traditionelle Load-Balancing-Verfahren wie Round Robin und Least Connections wurden für Umgebungen entwickelt, in denen Anfragen ungefähr gleich groß, kurzlebig und die Server dahinter austauschbar sind. Für klassische Webdienste mag das zutreffen, für die Inferenz großer Sprachmodelle (LLMs) ist es falsch. Zwei LLM-Requests können sich im Rechen- und Speicheraufwand um mehr als das Hundertfache unterscheiden: Der eine belegt einen Server eine Minute lang, der andere ist nach zwei Sekunden fertig. Round Robin verteilt nach der reinen Anzahl der Anfragen, nicht nach der tatsächlichen Last. Stehen zwei identische Backends hinter einem solchen Load Balancer, kann eines im Durchschnitt Anfragen erhalten, die zehnmal länger dauern als die des anderen – das eine staut sich, das andere steht leer. Least Connections zählt offene Verbindungen und wählt den Server mit den wenigsten. Bei gleichartigen, kurzen Requests ist das ein sinnvoller Indikator für die Last. Bei LLM-Requests, deren Kosten pro Verbindung extrem variieren, kann die Verbindungszahl jedoch irreführend sein, da zehn kurze Requests weniger Last bedeuten können als zwei lange. Beide Verfahren sind nicht defekt, sie lösen nur das falsche Problem: Sie optimieren auf Gleichverteilung der Anfragen, nicht auf Gleichverteilung der Arbeit. Bei LLM-Inference, wo die Kosten pro Request extrem heterogen sind, führt das zwangsläufig zu Schieflagen.

Die wahren Engpässe: KV-Cache, Token-Queue und Cache-Lokalität

Für das Routing von LLM-Anfragen sind nicht Verbindungszahl oder CPU-Auslastung entscheidend, sondern drei andere Signale: die Auslastung des KV-Cache, die Tiefe der Token-Queue und die Cache-Lokalität. Der KV-Cache speichert den Zustand bereits verarbeiteter Kontext-Tokens; ist er auf einem Server bereits gefüllt, kann eine Anfrage dort schneller weiterverarbeitet werden. Die Token-Queue gibt an, wie viele Tokens noch auf Verarbeitung warten – ein besserer Indikator für echte Last als die Zahl offener Verbindungen. Cache-Lokalität beschreibt, ob der für einen Request benötigte Zustand bereits auf einem bestimmten Server liegt. Diese Signale stehen jedoch in Konflikt: Lokalität zieht eine Anfrage zu dem Server, auf dem ihr Präfix schon gecacht ist, während die Lastverteilung sie eher zu einem entlasteten Server schicken würde. Ein Router muss beide Ziele gegeneinander abwägen. Konkret kann das über eine gewichtete Scoring-Funktion geschehen, die für jeden Server einen Score aus KV-Cache-Auslastung, Token-Queue-Tiefe und Cache-Lokalität berechnet. Beispielsweise erhält ein Server mit hoher Cache-Lokalität einen Bonus, der gegen den Nachteil einer bereits tiefen Token-Queue aufgewogen wird. Der Router wählt dann den Server mit dem besten Gesamtscore, nicht den mit den wenigsten Verbindungen. Die Konsequenz: Anfragen werden nicht gleichmäßig verteilt, sondern dorthin geschickt, wo der erwartete Nutzen – schnelle Verarbeitung durch Cache-Treffer bei vertretbarer Wartezeit – am höchsten ist. Erschwerend kommt hinzu, dass die Output-Länge zum Zeitpunkt des Routings unbekannt ist – jede Entscheidung ist eine Entscheidung unter Unsicherheit. Zudem besteht LLM-Inference aus zwei Phasen mit gegensätzlichen Anforderungen: einer rechenintensiven Prompt-Berechnung und einer speicherintensiven Token-Generierung. Eine einzige Platzierungsentscheidung muss also zwei inkompatible Workloads bedienen.

Kosten der Fehlallokation: Von 0,21 bis 15,25 Dollar pro Million Token

Ineffiziente Auslastung schlägt sich direkt in den Kosten nieder. Auf identischer H100-Hardware können die effektiven Kosten pro Million Output-Tokens zwischen 0,21 und 15,25 US-Dollar liegen – ein Unterauslastungs-Nachteil von Faktor 2,5 bis 24 bei moderater Last, nahe dem Leerlauf sogar bis Faktor 36,3. Die Ursache ist eine vom Betreiber gesteuerte Variable: die angebotene Request-Rate, die über Little's Law die parallele Last bestimmt. Gleichzeitig ist Data-Parallel Load Balancing ein Engpass erster Ordnung im LLM-Serving: Zuweisungen sind sticky, weil das Migrieren von KV-Caches teuer ist, die Last pro Request wächst über die Zeit, und Ankünfte sind nicht stationär. Längensensitives Scheduling kann hier gegensteuern: Das System L4 reduziert die End-to-End-Latenz um bis zu 67 Prozent und die Tail-Latenz um bis zu 69 Prozent, während der Durchsatz um den Faktor 2,89 steigt. Diese Zahlen stammen aus einer Evaluation gegen State-of-the-Art-Multi-Instance-Scheduling-Systeme. Sie zeigen, dass die Wahl des Routing-Verfahrens nicht nur eine Frage der Performance, sondern auch der Betriebskosten ist.

Neue Ansätze: BalanceRoute und L4 als Wegweiser

Zwei Forschungsansätze adressieren das Problem direkt. BalanceRoute ist eine Familie praktischer Online-Routing-Algorithmen für das Data-Parallel Load Balancing. Die erste Variante, BR-0, benötigt keine Vorhersage-Infrastruktur und nutzt einen stückweise linearen F-Score, der die Asymmetrie zwischen sicheren Zuweisungen und Überläufen abbildet. Eine zweistufige Zerlegung hält die Kosten pro Schritt im Millisekundenbereich. Die erweiterte Variante BR-H ergänzt einen kurzen, konstanten Lookahead und eine leichte Terminierungs-Klassifizierer-Schnittstelle. Das System wurde auf einem Cluster mit 144 NPUs eingesetzt. L4 verfolgt einen anderen Weg: Es partitioniert mehrere Instanzen desselben Modells in längenspezialisierte Gruppen, die jeweils Anfragen innerhalb eines bestimmten Längenbereichs verarbeiten. Ein dynamischer Programmieralgorithmus findet die beste Partitionierung, zur Laufzeit werden die Bereiche verfeinert und die Last dezentral zwischen und innerhalb der Gruppen ausbalanciert. Beide Ansätze nutzen die zuvor beschriebenen Signale – KV-Cache-Auslastung, Token-Queue-Tiefe und Cache-Lokalität – und berücksichtigen die Unsicherheit über die Output-Länge, um bessere Routing-Entscheidungen zu treffen als klassische Verfahren.