Technische Samenvatting: Online Lineair Programmeren voor Multi-Objective Routing in LLM Serving

1. Probleemstelling

Het artikel behandelt de uitdaging van online verzoekroutering in systemen voor het serveren van Large Language Models (LLM's). In deze systemen moeten binnenkomende verzoeken worden gedispatched naar parallelle decode-workers onder strikte beperkingen:

• Tijdsgekoppelde beperkingen: Verzoeken consumeren middelen (batch slots en KV-cache geheugen) continu gedurende hun gehele decode-duur. Een verzoek dat op tijdstip $t$ wordt toegelaten, bezet capaciteit tot het voltooid is, wat leidt tot een complex, tijdsafhankelijk probleem voor de toewijzing van middelen.
• Multi-Objective Trade-offs: Systemen moeten concurrerende Service-Level Objectives (SLO's) balanceren, waaronder throughput, end-to-end latency (EEL), time-to-first-token (TTFT) en tail latency (bijv. de 99e percentiel). Deze doelstellingen staan vaak in spanning met elkaar; bijvoorbeeld kan het maximaliseren van de throughput via agressieve batching de latency negatief beïnvloeden.
• Beperkingen van huidige heuristieken: Bestaande productiesystemen (zoals vLLM) en simulators (zoals Vidur) vertrouwen op heuristieken zoals Round-Robin, Join-Shortest-Queue (LOR), of Power-of-$d$ keuzes. Deze methoden missen expliciete optimalisatiedoelen, bieden beperkte controle over SLO-trade-offs en houden geen rekening met de heterogene en onzekere aard van LLM decode-lengtes.

2. Methodologie

De auteurs stellen een framework voor dat LLM-routering formuleert als een Online Lineair Programmeringsprobleem (OLP), waarbij technieken uit de operations research worden ingezet om een computationeel efficiënt controlebeleid af te leiden.

A. Wiskundige Formulering

• Model: Het systeem wordt gemodelleerd over een discrete tijdhorizon met parallelle decode-devices. Verzoeken arriveren sequentieel met bekende prefill-voetafdrukken en voorspelde (maar potentieel onnauwkeurige) decode-lengtes.
• Beperkingen: De formulering handhaaft twee cruciale beperkingen per device per tijdstap:
  1. Batch Grootte: Een maximaal aantal actieve verzoeken ($B$).
  2. KV-Cache Capaciteit: Een maximaal geheugenbudget ($M$) voor actieve verzoeken.
• Doelfunctie: De auteurs definiëren een lineaire beloningsfunctie voor elke routeringsbeslissing $(j, g, k)$ (het toewijzen van verzoek $j$ aan device $g$ op tijdstip $k$). Deze beloning is een gewogen som van:
  • Throughput (verwerkte tokens).
  • Negatieve latency (minimaliseren van EEL en TTFT).
  • Queries Per Second (QPS).
  • Tail metrics (gemodelleerd via indicator-beloningen voor verzoeken die aan specifieke latency-grenzen voldoen).
  • Kerninzicht: Geaggregeerde metrieken zoals tail latency worden gedecomposeerd in per-verzoek prikkels met behulp van indicatorfuncties, waardoor ze geoptimaliseerd kunnen worden binnen een lineair framework.

B. Algoritme Ontwerp: Bid-Price Control

Het oplossen van de volledige OLP bij elke milliseconde is computationeel onhaalbaar. In plaats daarvan leiden de auteurs een Bid-Price Control beleid af op basis van LP-dualiteit:

1. Dual Variables (Shadow Prices): De duale variabelen $p_i$ vertegenwoordigen de "schaduwprijs" of opportuniteitskosten van middelen (batch slots en KV-cache) op specifieke tijdstippen en devices. Hoge schaduwprijzen duiden op een verwachte congestie.
2. Beslisregel: Een verzoek wordt toegelaten als de SLO-gewogen voordelen groter zijn dan de geïmputeerde kosten van de middelen (berekend als het dot product van de resource-gebruik vector en de huidige schaduwprijzen).
3. Online Learning (SAA): Om de stochastische aard van aankomsten en voorspellingen op te vangen, worden de schaduwprijzen online geleerd met behulp van een Sample-Average Approximation (SAA) benadering. Het duale doel wordt geminimaliseerd over een geschiedenis van geobserveerde acties.
4. Efficiënte Updates: Om de milliseconde-beslissingslatencies te halen, maken de auteurs gebruik van warm-gestarte, geprojecteerde mini-batch gradiëntafdaling. In plaats van het duale probleem vanaf nul op te lossen, werkt het algoritme de prijsvector incrementeel bij op basis van een kleine batch historische data. Dit zorgt voor een voorspelbare runtime (1–2 ms per periode op een CPU).

3. Belangrijkste Bijdragen

1. Multi-Objective Optimalisatie Framework: Het eerste framework dat LLM-routering formuleert als een OLP met expliciete, tijdsgekoppelde batch en KV-cache beperkingen. Het deelt geaggregeerde SLO's (inclusclusief tail latency) op in per-verzoek beloningen die geschikt zijn voor online optimalisatie.
2. Efficiënt Bid-Price Algoritme: Een computationeel hanteerbaar beleid dat evoluerende duale schaduwprijzen online bijhoudt zonder in elke stap een volledige LP op te lossen, waarmee aan de strikte latency-eisen van LLM serving wordt voldaan.
3. Interpreteerbare Trade-off Controle: Het framework biedt operators transparante "knoppen" (doelgewichten) om prestaties systematisch langs de Pareto-front te verschuiven. Schaduwprijzen dienen ook als diagnostische instrumenten om te identificeren of batch slots of KV-cache de huidige bottleneck vormen.

4. Experimentele Resultaten

De auteurs hebben hun router geïntegreerd in de Vidur simulator en deze geëvalueerd tegen standaard baselines (Round-Robin, LOR, Random, Power-of-2) onder diverse workloads (real-world LMSYS-Chat-1M data en synthetische P/D ratio's).

• Prestatiewinsten: De voorgestelde methode vertoonde substantiële verbeteringen ten opzichte van de baselines in verschillende SLO-regimes.
  • In scenario's met ruis in voorspellingen (20% fout), bereikte het algoritme een reductie van 45,75% in gemiddelde EEL en een reductie van 42,49% in P95 EEL vergeleken met Round-Robin.
  • Het presteerde aanzienlijk beter dan heuristieken in tail latency metrieken (P99 EEL en TTFT).
• Robuustheid: Het beleid bleef effectief, zelfs met imperfecte decode-lengte voorspellingen, omdat de online prijsupdates zich aanpassen aan de schattingsfouten.
• Adaptiviteit: In niet-stationaire workloads (plotselinge pieken in de belasting) paste de router zich snel aan via een rolling-window mechanisme voor historie-updates, waarbij superieure prestaties werden behouden.
• Gewichtsafstemming: Experimenten bevestigden dat het aanpassen van de doelgewichten operators in staat stelt om specifieke metrieken te prioriteren (bijv. het minimaliseren van gemiddelde latency versus het strikt controleren van tail latency) met voorspelbare uitkomsten.

5. Betekenis en Claims

Het artikel beweert dat een wetenschappelijk onderbouwde optimalisatiebenadering beter presteert dan heuristiek-gebaseerde routering in LLM serving.

• Overbrugging van Communities: Het vestigt een fundamentele brug tussen de operations research community (online resource allocatie, bid-price control) en de LLM systems community.
• Inzichten in Systeemontwerp: Het framework onthult structurele inzichten, zoals het gebruik van schaduwprijzen om resource-bottlenecks (batch vs. geheugen) te diagnosticeren en het mogelijk maken van SLO-bewuste admission control tijdens overbelasting.
• Praktische Toepasbaarheid: Hoewel volledige productie-integratie als toekomstig werk wordt genoteerd, tonen de resultaten aan dat optimalisatie-gebaseerde routering haalbaar is op milliseconde-schaal en een fundament biedt voor systematisch beleidsontwerp in plaats van ad-hoc tuning.

De auteurs blijven bescheiden over directe productie-implementatie en erkennen uitdagingen zoals integratie met serving engines (bijv. vLLM), het afhandelen van preemption en coördinatie in gedistribueerde omgevingen. Ze stellen echter dat het framework een noodzakelijke basis vormt voor toekomstig onderzoek op het snijvlak van operations research en machine learning systemen.