Technische Samenvatting: PARS – Prompt-Aware Ranking Scheduler voor Low-Latency LLM Serving

Probleemstelling

De implementatie van Large Language Models (LLM's), met name de opkomende generatie redeneerbare modellen (bijv. DeepSeek R1, GPT-o1), staat voor een kritieke uitdaging in inference-scheduling: Head-of-Line (HOL) blocking. Traditionele serving-systemen, zoals vLLM en Orca, vertrouwen voornamelijk op First Come, First Serve (FCFS) beleid. Bij FCFS blokkeren langlopende inference-taken (vaak gekenmerkt door zeer variabele en uitgebreide Chain-of-Thought redeneersporen) kortere taken die erachter in de wachtrij staan, wat leidt tot significante latentiepieken en verminderde throughput.

Hoewel het Shortest-Job-First (SJF) beleid theoretisch optimaal is voor het minimaliseren van de gemiddelde latentie, wordt de toepassing ervan op LLM's gehinderd door de stochastische en autoregressieve aard van token-generatie. Exacte outputlengtes kunnen niet vooraf worden gekend vóór uitvoering. Bestaande pogingen om SJF te benaderen via lengtevoorspelling lijden aan drie belangrijke beperkingen:

1. Gevoeligheid voor Ruis: Pointwise (regressie) en listwise ranking-methoden worstelen met de inherente variabiliteit van LLM-outputs, waarbij vergelijkbare prompts tijdens verschillende runs fluctuerende lengtes kunnen opleveren, wat ruisgevoelige trainingssignalen introduceert.
2. Redeneercomplexiteit: Standaard voorspellers houden vaak geen rekening met de volledige complexiteit van multi-step redeneersporen die gebruikelijk zijn bij moderne modellen.
3. Gebrek aan Generalisatie: Veel benaderingen vereisen modelspecifieke hertraining, wat hen onpraktisch maakt voor diverse of propriëtaire model-implementaties.

Methodologie: PARS Framework

De auteurs introduceren PARS (Prompt-Aware Ranking Scheduler), een lichtgewicht framework ontworpen om HOL blocking te mitigeren door SJF-scheduling te benaderen via pairwise learning-to-rank. PARS bestaat uit twee primaire componenten:

1. Pairwise-getrainde Predictor

In plaats van absolute outputlengtes te voorspellen (pointwise) of volledige lijsten te ranken (listwise), richt PARS zich op pairwise vergelijkingen met behulp van een margin ranking loss.

• Trainingsdoel: Het model wordt getraind op paren van prompts $(A, B)$ met binaire labels die aangeven welke prompt een langere respons wordt verwacht te genereren.
• Ruisfiltering: Om stochastiek aan te pakken, wordt de trainingsdata gefilterd om alleen promptparen op te nemen met een significant verschil in ground-truth responslengtes (gedefinieerd door een relatieve variantiedrempel $\delta = 0.2$). Dit zorgt ervoor dat het model leert van "informatieve" paren waar de relatieve ordening robuust is tegen sampling-ruis, in plaats van te worstelen met vergelijkingen die bijna gelijk zijn.
• Architectuur: De predictor maakt gebruik van een lichtgewicht BERT-base-uncased backbone. Deze extraheert de [CLS] token embedding uit de prompt en stuurt deze door een lineaire laag om een scalaire score te generen die de verwachte respons-kosten vertegenwoordigt.
• Loss-functie: Het model wordt geoptimaliseerd met margin ranking loss: $L(s_A, s_B, y) = \max(0, -y \cdot (s_A - s_B) + \text{margin})$, wat een scheidingstussen de scores van correct gerankte paren afdwingt.

2. Predictor-gestuurde Scheduler

De getrainde predictor wordt geïntegreerd in het vLLM serving-systeem om de Waiting Queue (W) en de Running Queue (R) te beheren.

• Scheduling Logica: Bij aankomst worden verzoeken gescoord door de predictor. De wachtrij wordt gesorteerd op basis van deze scores (oplopende volgorde van verwachte lengte) om kortere taken te prioriteren, wat effectief SJF benadert.
• Preventie van Starvation: Om te voorkomen dat langlopende taken oneindig worden uitgesteld, is er een mechanisme dat de prioriteit verhoogt voor elk verzoek dat langer heeft gewacht dan een configureerbare drempel (standaard: 2 minuten).
• Implementatie: De scheduler werkt op iteratieniveau, is compatibel met continuous batching en vereist geen wijzigingen in de onderliggende C++/CUDA backends van vLLM.

Belangrijkste Bijdragen

1. Nieuwige Pairwise Benadering: Het artikel stelt een pairwise learning-to-rank methode voor met margin ranking loss en datafiltering, die een grotere stabiliteit vertoont tegen de stochastische aard van LLM-generatie vergeleken met pointwise en listwise baselines.
2. Reasoning-Aware Design: Het framework bevat expliciet volledige redeneersporen (tussenliggende gedachten en rechtvaardigingen) in de definitie van de responslengte, waardoor het geschikt is voor moderne redeneer-LLM's.
3. Naadloze Integratie: PARS is geïmplementeerd als een open-source module binnen vLLM (ongeveer 1.000 regels code) en vereist geen wijzigingen in de kern van de inference engine.
4. Cross-Model Generalisatie: De auteurs demonstreren dat een predictor getraind op één model (bijv. GPT-4) effectief taken kan schedulen voor andere diverse modellen (bijv. Llama 3.1, DeepSeek-R1) zonder hertraining.

Experimentele Resultaten

Uitgebreide evaluaties werden uitgevoerd over meerdere datasets (Alpaca, LMSYS-Chat-1M, MATH-plus, Evolved Codealpaca) en modellen (Llama 3.1, GPT-4, DeepSeek-R1).

• Predictor Accuratesse: PARS behaalde de hoogste Kendall's Tau ($\tau_b$) ranking accuratesse over alle datasets, met een waarde tot 0.96 op de Alpaca dataset. Het presteerde significant beter dan pointwise en listwise baselines, met name op redeneermodellen (bijv. een 5,5× verbetering ten opzichte van pointwise SJF op LMSYS-Chat-1M met DeepSeek-R1).
• Latentie Reductie: In real-world workloads verminderde PARS de gemiddelde per-token latentie met wel 15,7× vergeleken met de standaard vLLM FCFS scheduler op Llama 3.1. Onder bursty load condities (2.000 gelijktijdige verzoeken) bereikte het een versnelling van tot wel 7,7× op Llama en meer dan 2× op DeepSeek-R1.
• Tail Latency: PARS verbeterde de p90 latentie aanzienlijk, met een reductie van tot wel 12,3× vergeleken met FCFS, waardoor de prestaties dicht bij de geïdealiseerde "Oracle SJF" (die ground-truth lengtes gebruikt) kwamen.
• Throughput & Overhead: De methode behield of verbeterde zelfs de systeemthroughput (verzoeken per seconde) door de batch homogeniteit te vergroten. De runtime overhead voor scoring en sorteren was verwaarloosbaar (ongeveer 0,08% van de totale serving tijd), zonder extra latentie toe te voegen aan de uitvoering van verzoeken.
• Generalisatie: De "Cross-Model PARS" variant, uitsluitend getraind op GPT-4 data, slaagde erin taken voor Llama en DeepSeek-R1 te schedulen, waarbij het de modelspecifieke pointwise baselines overtrof en de listwise benaderingen evenaarde.

Betekenis en Claims

Het artikel stelt dat naarmate redeneerbare LLM's prevalenter worden, de variabiliteit in inference-tijden FCFS steeds inefficiënter zal maken. De betekenis van PARS ligt in het vermogen om een praktische, inzetbare en lichtgewicht alternatief te bieden voor zware of modelspecifieke scheduling-oplossingen.

De auteurs claimen dat:

• Pairwise ranking superieur is voor LLM-scheduling omdat het zich richt op robuuste relatieve vergelijkingen in plaats van instabiele absolute voorspellingen.
• Generalisatie haalbaar is zonder hertraining, waardoor een enkele predictor een heterogene vloot van LLM's kan beheren.
• Minimale overhead de benadering levensvatbaar maakt voor productieomgevingen waar responsiviteit cruciaal is.

Het werk concludeert dat hoewel de omvang van de winst afhangt van de taaklengte-variabiliteit, PARS een robuust mechanisme biedt om relatieve executiekosten te vangen, waardoor HOL blocking effectief wordt gemitigeerd en low-latency serving mogelijk wordt gemaakt voor de volgende generatie AI-applicaties. De software en datasets worden als open-source vrijgegeven om adoptie in zowel onderzoek als real-world implementaties te faciliteren.