LLM Serving Optimization with Variable Prefill and Decode Lengths

Technische Samenvatting: Optimalisatie van LLM-serving met variabele prefill- en decode-lengtes

Probleemformulering
Dit artikel behandelt het offline-schedulingprobleem voor Large Language Model (LLM) inferentie op een enkele computationele worker met een vast budget aan Key-Value (KV) cachegeheugen. Het systeem verwerkt een wachtrij van $n$ verzoeken die gelijktijdig arriveren op $t=0$. Elk verzoek $i$ wordt gekenmerkt door een heterogene prompt-lengte (prefill-grootte, $s_i$) en een respons-lengte (decode-grootte, $o_i$).

De kernuitdaging komt voort uit de dynamische aard van het geheugengebruik tijdens autoregressieve decodering. Terwijl de prefill-fase geheugen consumeert dat proportioneel is aan $s_i$, consumeert de decode-fase geheugen dat lineair groeit met elk gegenereerd token ($s_i + j$ voor de $j$-de token). Bijgevolg fluctueert het aantal gelijktijdige verzoeken dat een worker kan afhandelen dynamisch op basis van de generatieprogressie van actieve verzoeken. Het doel is om de Totale End-to-End Latentie (TEL) te minimaliseren, gedefinieerd als de som van de voltooiingstijden van alle verzoeken, onder de voorwaarde dat het geaggregeerde geheugengebruik van elke batch op elk tijdstap de capaciteit $M$ niet overschrijdt.

De auteurs verruimen de aanname van uniforme inputgroottes die in eerder werk (Jaillet et al., 2025) werd gehanteerd, door een realistisch scenario te overwegen waarin workloads een mix vormen van korte conversationele prompts en taken voor het samenvatten van lange documenten.

Theoretische bevindingen en uitdagingen
Het artikel stelt vast dat het versoepelen van de aanname van uniforme inputgroottes de complexiteit van het schedulingprobleem fundamenteel verandert:

1. NP-hardheid: Het gegeneraliseerde schedulingprobleem met heterogene $s_i$ en $o_i$ is bewezen NP-hard via reductie van het beperkte 3-Partition probleem.
2. Falen van standaard heuristieken: Standaard beleidsregels, inclusief First-Come-First-Served (FCFS), Shortest-Output-First (MC-SF) en Total-Size-Based prioritering, blijken in deze heterogene setting een onbegrensde benaderingsratio te hebben. Specifiek kan een verzoek met een grote input maar een kleine output kortstondig veel geheugen consumeren, terwijl een verzoek met een kleine input maar een lange output gedurende een langere periode geheugen in beslag neemt, wat trade-offs creëert die eenvoudige heuristieken niet kunnen oplossen.

Methodologie: Het Sorted-F Algoritme
Om deze uitdagingen aan te pakken, stellen de auteurs Sorted-F voor, een schedulingalgoritme dat ontworpen is om een constante-factor benaderingsgarantie te behalen. Het algoritme werkt in twee fasen:

1. Batchconstructie (Fase 1): Het algoritme selecteert iteratief haalbare batches van verzoeken om een geordende lijst te vormen. De selectie wordt gestuurd door een nieuwe kwaliteitsmetriek, $F(X)$, gedefinieerd voor een verzameling verzoeken $X$ als:
   $$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$$
   Deze metriek balanceert de batchgrootte ($|X|$) tegen de geaggregeerde downstream decode-kosten ($\sum o_i$). Het minimaliseren van $F(X)$ is equivalent aan het maximaliseren van de "throughput density" (voltooide verzoeken per eenheid van gemiddelde decode-tijd). Binnen elke geselecteerde batch worden de verzoeken gesorteerd op niet-afnemende outputlengte.
2. Executie (Fase 2): Het systeem voert het schema uit over discrete tijdstappen, waarbij verzoeken uit de geordende lijst in de huidige batch worden toegelaten zolang aan de geheugenhaalbaarheidsrestricties wordt voldaan, gebruikmakend van continuous batching en prefill/decode mixing.

Benaderingsgarantie
De auteurs bewijzen dat Sorted-F een constante benaderingsratio van maximaal 48 bereikt ten opzichte van het optimale offline schema. Het bewijs maakt gebruik van een reeks structurele transformaties (separatie, groepering en uitlijning) die het Sorted-F schema en het optimale schema in vergelijkbare vormen converteren, waarmee wordt aangetoond dat de toename in latentie bij elke stap begrensd is door een constante factor.

Praktische Implementaties
In het besef dat de combinatorische optimalisatie vereist voor Fase 1 computationeel duur is voor grote $n$, stelt het artikel drie praktische solvers voor:

• Exacte Dynamische Programmering: Biedt een exacte oplossing voor kleine instanties ($n \le 100$) met $O(n^2 M)$ complexiteit.
• Local Swap Search: Een heuristiek voor gemiddelde schalen ($n \le 500$) die een initiële greedily oplossing iteratief verbetert via paarwijze uitwisselingen ($O(n^2)$).
• Quantile Greedy Selection: Een lineaire-tijd heuristiek ($O(n)$) voor grootschalige systemen ($n \ge 1000$) die statistische sampling gebruikt om uitschieters te filteren en de capaciteit greedily invult.

Daarnaast introduceren de auteurs Sorted-LP, een heuristiek die gebruikmaakt van de oplossing van een Lineair Programmeren (LP) relaxatie van het probleem om verzoeken te ordenen, en Sorted-F+Amin, een adaptieve variant die omgaat met voorspellingsonzekerheid in outputlengtes door tijdens de inferentie dynamisch schattingen te verfijnen.

Experimentele Resultaten
Numerieke experimenten op gemengde workloads (een combinatie van de LMSYS-Chat dataset en Arxiv lange-document samenvattingen) laten het volgende zien:

• Reductie in Latentie: Sorted-F (gebruikmakend van Local Swap Search) presteert consistent beter dan FCFS, MC-SF en LP-gestuurde baselines. In een 80/20 kort/lang mengsel met 2000 verzoeken verminderde Sorted-F de gemiddelde latentie met 4,87$\times$ vergeleken met FCFS en met 2,09$\times$ vergeleken met MC-SF.
• Optimaliteitskloof: Op behapbare instanties is de empirische kloof tussen Sorted-F en de LP-relaxatie ondergrens klein (ongeveer 1,03–1,09), wat suggereert dat het algoritme in de praktijk bijna optimaal presteert ondanks de ruime theoretische bovengrens.
• Gevoeligheid voor Workload: De voordelen van Sorted-F zijn het meest uitgesproken in heterogene, overbelaste regimes waar geheugen een beperkende factor is. In homogene of licht belaste regimes neemt het voordeel af.
• Online Prestaties: Een receding-horizon variant (Sorted-F-Online) getest onder Poisson-aankomsten vertoont significante verbeteringen ten opzichte van MC-SF en FCFS in overbelaste online regimes, hoewel het minder voordeel biedt in stabiele, lage-latentie regimes.

Betekenis en Claims
Het artikel claimt dat variabele prefill-lengtes geen kleine modelleringsdetails zijn, maar een fundamentele factor die standaard scheduling-heuristieken ineffectief maakt en het probleem NP-hard maakt. De primaire bijdrage is het Sorted-F algoritme, dat de eerste constante-factor benaderingsgarantie biedt voor LLM-scheduling onder heterogene input/output restricties. Het werk overbrugt de kloof tussen theoretische scheduling-limieten en praktische LLM-serving, en biedt een schaalbaar, geheugenbewust framework dat de latentie in gemengde workload-scenario's aanzienlijk vermindert zonder dat perfecte voorspelling van outputlengtes vereist is. De auteurs benadrukken dat hoewel de theoretische bovengrens 48 is, de empirische resultaten suggereren dat het algoritme in realistische settings veel dichter bij de optimale oplossing ligt.