Technische Samenvatting: Beyond Prediction: Tail-Aware Scheduling for LLM Inference

1. Probleemstelling

Het serveren van Large Language Models (LLM's) staat voor een kritieke uitdaging bij het beheren van extreme variabiliteit in de lengte van verzoeken, met name door de opkomst van reasoning-augmented modellen die multi-step generatie, zelfreflectie en adaptieve terminatie vertonen. Deze variabiliteit maakt op grootte gebaseerde scheduling-policies (zoals Shortest Job First - SJF, of Shortest Remaining Processing Time - SRPT) fragiel.

Huidige state-of-the-art schedulers vertrouwen op het voorspellen van outputlengtes of resterende tokens om SJF/SRPT te benaderen. Echter, het artikel identificeert drie fundamentele problemen bij deze aanpak:

1. Voorspellingsfragiliteit: Het voorspellen van de outputlengte is inherent moeilijk vanwege de hoge variantie in tokengeneratie (stochastiek en niet-determinisme), wat beleid kwetsbaar maakt onder distributieverschuivingen en bursty aankomsten.
2. Metrische Mismatch: Policies die geoptimaliseerd zijn voor gemiddelde latentie (bijv. gemiddelde TTFT/TBT) vertonen vaak een slechte tail-latentie (P90–P99). Bij LLM-serving wordt de gebruikerservaring bepaald door tail-latenties (Time-To-Last-Token, TTLT), die vaak de beperkende factor zijn voor Service Level Objectives (SLO's).
3. Geheugen-gekoppelde Dynamiek: In tegenstelling tot klassieke wachtrijen is LLM-inferentie stateful. Verzoeken accumuleren grote Key-Value (KV) caches tijdens de decoding-fase. Naïeve preëmptie om korte jobs te prioriteren kan leiden tot dure cache-evictie, recomputatie en "thrashing", wat de tail-latentie potentieel verhoogt ondanks het verminderen van de wachtrijvertraging.

De kernvraag die gesteld wordt is of schedulers expliciete joblengte-voorspellingen nodig hebben om tail-latentie te optimaliseren. De auteurs stellen dat dit niet nodig is en stellen in plaats daarvan een distributie-bewuste, voorspellingsvrije aanpak voor.

2. Methodologie: UNIBOOST

Het artikel introduceert UNIBOOST, een distributie-bewust, voorspellingsvrij scheduling-framework dat expliciete lengtevoorspelling vervangt door "soft" priority boosting gedreven door lichtgewicht statistische signalen. Het ontwerp is een co-optimalisatie van scheduling en cache-bewuste preëmptie, gestructureerd in vier fasen:

Fase 1: Strawman (DISTBOOST)

De initiële aanpak behandelt de prefill- en decode-fasen als disjuncte problemen. Het gebruikt een $\gamma$-Boost priority functie (geïnspireerd door wachtrijtheorie) voor prefill-verzoeken, maar geeft prioriteit aan de decode-wachtrij. Hoewel dit de tail-metrieken voor decoding verbetert, leidt het tot Head-of-Line (HoL) blocking waarbij prefill-verzoeken worden uitgehongerd door langlopende decode-jobs.

Fase 2: Unified Prioritization (UNIBOOST-BASE)

Om HoL-blocking aan te pakken, verenigen de auteurs de prefill- en decode-wachtrijen in een enkele priorititeitsruimte.

• Priority Score: Verzoeken worden gescoord op basis van $\phi_i(t) = a_i - b_\gamma(\tilde{w}_i(t))$, waarbij $a_i$ de aankomsttijd is en $\tilde{w}_i(t)$ de effectieve arbeid (maximaal van de verkregen arbeid en de prefill-lengte).
• Boost Function: $b_\gamma(w) = \frac{1}{\gamma} \log(\frac{1}{1 - e^{-\gamma w}})$. Deze functie biedt een "soft" priority boost aan verzoeken met minder verkregen service, waardoor de harde preëmptie van klassieke SRPT wordt vermeden.
• Mechanisme: De scheduler selecteert het verzoek met de minimale score, waardoor preëmptie tussen fasen mogelijk is, maar gecontroleerd wordt door een hysteresis-parameter om oscillatie te voorkomen.

Fase 3: Stabiliteit via MEMGUARD (KV-Aware Hysteresis)

Om de hoge kosten van KV-cache evictie en recomputatie te mitigeren, introduceren de auteurs MEMGUARD.

• Gekwantiseerde Prioriteiten: In plaats van prioriteiten continu bij te werken, discretiseert het systeem de verkregen arbeid metriek ($\hat{w}_i$) met behulp van geometrische kwantisatie (bijv. drempelwaarden bij $k, 2k, 4k...$).
• Minimum Run: Zodra een verzoek is gedispatched, kan het niet worden geëvicteerd totdat de verkregen arbeid de volgende kwantisatiedrempel overschrijdt. Dit amortiseert de kosten van KV-beweging en beperkt het aantal preëmptiemogelijkheden tot een logaritmische bovengrens ten opzichte van de joblengte.

Fase 4: Adaptieve Parameter Schatting ($\gamma$-Ada)

De boost-parameter $\gamma$ heeft een significante impact op het tail-gedrag. Een statische $\gamma$ is suboptimaal onder variërende belastingen.

• Online Schatting: Het systeem schat een effectieve tail-helling ($\gamma_{eff}$) door een log-lineaire helling te fitten op de bovenste staart van de geobserveerde responstijd-distributie (tussen P95 en P_P99).
• Adaptatie: De scheduler past $\gamma$ dynamisch aan om te interpoleren tussen FCFS (bescherming van de tail) en LAS (optimalisatie van het gemiddelde), waardoor het zich aanpast aan verschuivingen in de workload zonder expliciete voorspelling.

3. Belangrijkste Bijdragen

1. Voorspellingsvrije Tail-Optimalisatie: Toont aan dat expliciete joblengte-voorspelling niet vereist is om de tail-latentie te optimaliseren. In plaats daarvan volstaan lichtgewicht statistische signalen en soft boosting.
2. Co-Design van Scheduling en Evictie: Introduceert een framework dat scheduling-beslissingen en KV-cachebeheer gezamenlijk optimaliseert. Door boost-gebaseerde scheduling te koppelen aan eviction-bewuste executiecontrole (MEMGUARD), voorkomt het systeem de prestatieverslechtering door KV-thrashing.
3. Robuustheid tegen Distributieverschuivingen: De voorgestelde methode past zich aan variërende workloads aan (heavy-tailed vs. light-tailed, reasoning vs. chat) zonder hertraining of complexe voorspellingsmodellen.
4. Theoretische Onderbouwing: Past de $\gamma$-Boost policy uit de wachtrijtheorie aan de specifieke beperkingen van LLM-inferentie aan (statefulness, geheugenkoppeling).

4. Experimentele Resultaten

Geëvalueerd op productie- en open-source traces (Azure, ShareGPT, S1K) met modellen zoals Llama-3-8B, CodeLlama-34B en Qwen-72B op NVIDIA A100 GPU's:

• Reductie van Tail-Latentie: UNIBOOST bereikt een P99 TTLT die tot 35–50% lager is dan SRPT met perfecte lengtevoorspelling (TRAIL+). Het vermindert ook de P99 TTFT met 34–47% over diverse workloads.
• Doorvoersnelheid (Throughput): De methode verbetert de throughput met 1.01–1.12$\times$ onder bursty belastingen vergeleken met baselines.
• SLO Attainment: UNIBOOST stelt systemen in staat om 2.9–8.7$\times$ striktere SLO's voor TTFT te tolereren terwijl 99% attainment behouden blijft vergeleken met SJF-gebaseerde benaderingen.
• Ablatie-studies:
  • Het verwijderen van de uniforme prioriteit (Fase 2) leidt tot prefill-starvation.
  • Het verwijderen van MEMGUARD (Fase 3) veroorzaakt significante pieken in de tail-latentie door KV-thrashing.
  • Het verwijderen van adaptieve $\gamma$ (Fase 4) vermindert de robuustheid onder verschuivingen in de workload.
• Vergelijking: De methode presteert beter dan state-of-the-art baselines inclusief vLLM's Sarathi (chunked prefill), LTR (learning-to-rank SJF), en TRAIL (voorspellingsgebaseerde SRPT), met name in reasoning-zware workloads waar voorspelling het meest onbetrouwbaar is.

5. Betekenis en Claims

Het artikel claimt dat UNIBOOST een robuust alternatief biedt voor voorspellingszware scheduling-policies voor online LLM-serving. De betekenis ligt in:

• Ontkoppeling van Voorspelling: Het verwijdert de afhankelijkheid van nauwkeurige lengtevoorspelling, wat een belangrijke bottleneck is in reasoning-zware en variabel-lengte workloads.
• Holistische Optimalisatie: Het adresseert tegelijkertijd de "mean vs. tail" trade-off en de "scheduling vs. memory" trade-off, waardoor een oplossing wordt geboden die effectief is zelfs wanneer de kwaliteit van de voorspelling verslechtert.
• Practicaliteit: Het ontwerp is eenvoudig te integreren in bestaande continuous-batching stacks (zoals vLLM en SGLang) en vertrouwt op lichtgewicht runtime-statistieken in plaats van complexe ML-modellen.

De auteurs concluderen dat distributie-bewuste, eviction-bewuste scheduling essentieel is voor de volgende generatie LLM-serving, vooral naarmate modellen in staat worden tot meer variabele-lengte reasoning.