🤖 machine learning

Ranking Before Serving: Low-Latency LLM Serving via Pairwise Learning-to-Rank

Ursprüngliche Autoren: Yiheng Tao, Yihe Zhang, Matthew Dearing, Xin Wang, Yuping Fan, Michael E. Papka, Zhiling Lan

Veröffentlicht 2026-06-29

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

Ursprüngliche Autoren: Yiheng Tao, Yihe Zhang, Matthew Dearing, Xin Wang, Yuping Fan, Michael E. Papka, Zhiling Lan

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie führen ein geschäftiges Café. Sie haben eine Schlange von Kunden (die Anfragen), die darauf warten, Getränke zu bestellen, und Sie haben einen einzelnen Barista (das Large Language Model oder LLM), der die Getränke nacheinander zubereitet.

Das Problem: Der „Lange Bestellung“-Engpass

In einem traditionellen Café verwenden Sie die Regel „Wer zuerst kommt, mahlt zuerst“ (First Come, First Served). Wenn die erste Person in der Schlange einen komplexen, 20 Minuten dauernden Latte bestellt, müssen alle hinter ihr – selbst die Person, die nur einen schnellen Espresso möchte – 20 Minuten warten. Dies wird als Head-of-Line (HOL) Blocking bezeichnet.

In der Welt der KI ist dies ein riesiges Problem. Einige KI-Fragen sind einfach und dauern nur eine Sekunde, um beantwortet zu werden. Andere, insbesondere die neuen „Reasoning“-KI-Modelle, die mathematische Probleme oder Code Schritt für Schritt durchdenken, können Minuten benötigen, um eine Antwort zu generieren. Wenn eine lange, denkintensive Anfrage am Anfang der Schlange feststeckt, verzögert dies alle anderen, was das gesamte System langsam und träge wirken lässt.

Die Lösung: Der „Smarte Prädiktor“ (PARS)

Das Paper stellt ein neues System namens PARS (Prompt-Aware Ranking Scheduler) vor. Stellen Sie sich PARS wie einen super-smarten, unsichtbaren Manager vor, der hinter dem Tresen steht und den Bestellschein eines Kunden (den Prompt) lesen kann und sofort errät, wie lange die Zubereitung des Getränks dauern wird, bevor der Barista überhaupt anfängt.

Anstatt die Leute in der Reihenfolge ihres Eintreffens zu bedienen, ordnet dieser Manager die Schlange neu, sodass die „schnellen Espresso“-Bestellungen zuerst gehen, gefolgt von den „mittleren“ Bestellungen, und die „20-Minuten-Latte“-Bestellungen nach hinten geschoben werden. Dies ist bekannt als Shortest-Job-First (SJF) Scheduling.

Wie es funktioniert: Der „Pairwise“-Trick

Der schwierige Teil ist, dass KI unvorhersehbar ist. Manchmal erhält dieselbe Frage eine kurze Antwort und manchmal eine lange, einfach durch Zufall. Wenn der Manager versuchen würde, die exakte Zeit zu erraten (z. B. „Das wird genau 42 Sekunden dauern“), könnte er sich irren und die Schlange durcheinanderbringen.

Um dies zu lösen, nutzt PARS einen cleveren Trick: das Pairwise Learning.

Der alte Weg: Versuchen, die exakte Zeit für jede einzelne Bestellung zu erraten. (Wie das exakte Gewicht einer Wassermelone zu schätzen).
Der PARS-Weg: Einfach zwei Bestellungen gleichzeitig vergleichen. Fragen: „Ist Bestellung A wahrscheinlich länger als Bestellung B?“ (Wie zu sagen: „Diese Wassermelone ist definitiv schwerer als dieser Apfel“).

Das System wird darauf trainiert, die winzigen, verwirrenden Unterschiede zu ignorieren und sich nur auf die offensichtlichen zu konzentrieren (z. B. „Dieses Matheproblem ist viel schwieriger als diese einfache Begrüßung“). Indem es sich auf diese klaren Vergleiche konzentriert, wird der Manager sehr gut darin, die Schlange zu sortieren, ohne durch die zufälligen Schwankungen der KI verwirrt zu werden.

Die Ergebnisse: Schnellerer Service für alle

Die Forscher haben dieses System in einem realen Umfeld mit einem populären KI-Serving-Tool namens vLLM getestet. Sie fanden heraus, dass:

Massive Beschleunigungen: Indem sie die kurzen Aufgaben zuerst durchlaufen ließen, reduzierten sie die durchschnittliche Wartezeit für Nutzer um bis zu das 15,7-fache im Vergleich zur Standardmethode „First Come, First Served“.
Keine Zusatzkosten: Der „Manager“ (der Prädiktor) ist sehr leichtgewichtig. Es kostet fast keine Zeit, die Schlange zu sortieren, sodass er den Barista nicht ausbremst.
Funktioniert mit jedem Modell: Das System ist so gut darin zu raten, dass es, wenn man es für eine Art von KI (wie GPT-4) trainiert, immer noch effektiv die Schlange für eine völlig andere KI (wie Llama oder DeepSeek) sortieren kann, ohne neu trainiert werden zu müssen. Es ist wie ein Manager, der gelernt hat, Bestellungen in einem Café zu sortieren, und sofort denselben Job in einem Teehaus erledigen kann.
Fairness: Um sicherzustellen, dass die „20-Minuten-Latte“-Bestellungen nicht ewig warten müssen, gibt es ein Sicherheitsventil. Wenn eine lange Bestellung zu lange gewartet hat, wird sie in der Schlange nach vorne geschoben, damit niemand hungrig bleibt.

Zusammenfassend

Das Paper präsentiert PARS, ein smartes Scheduling-System, das wie ein Verkehrspolizist für KI-Anfragen fungiert. Anstatt eine lange, komplizierte Anfrage die Schlange blockieren zu lassen, nutzt es ein cleveres, vergleichendes Ratespiel, um die schnellen Anfragen zuerst durchzuwinken. Dies macht das gesamte KI-System viel schneller und reaktionsschneller, besonders im Umgang mit der neuen Generation von KIs, die gerne lange „nachdenken“, bevor sie antworten.

Technisches Resümee: PARS – Prompt-Aware Ranking Scheduler für Low-Latency LLM-Serving

Problemstellung

Die Bereitstellung von Large Language Models (LLMs), insbesondere der aufkommenden Generation von reasoning-fähigen Modellen (z. B. DeepSeek R1, GPT-o1), steht vor einer kritischen Herausforderung im Inference-Scheduling: dem Head-of-Line (HOL) Blocking. Traditionelle Serving-Systeme wie vLLM und Orca verlassen sich überwiegend auf First-Come, First-Serve (FCFS)-Policies. Bei FCFS blockieren langlaufende Inferenzaufgaben (die oft durch hochvariable und umfangreiche Chain-of-Thought-Reasoning-Spuren charakterisiert sind) kürzere Aufgaben, die dahinter in der Warteschlange stehen, was zu signifikanten Latenzspitzen und reduziertem Durchsatz führt.

Obwohl die Shortest-Job-First (SJF)-Policy theoretisch optimal zur Minimierung der durchschnittlichen Latenz ist, wird ihre Anwendung auf LLMs durch die stochastische und autoregressive Natur der Token-Generierung erschwert. Exakte Ausgabelängen können vor der Ausführung nicht bekannt sein. Bestehende Versuche, SJF mittels Längenprognose zu approximieren, leiden unter drei Hauptbeschränkungen:

Rauschempfindlichkeit: Pointwise (Regression) und Listwise-Ranking-Methoden haben Schwierigkeiten mit der inhärenten Variabilität von LLM-Outputs, bei denen ähnliche Prompts über verschiedene Durchläufe hinweg schwankende Längen erzeugen können, was verrauschte Trainingssignale einführt.
Reasoning-Komplexität: Standard-Prädiktoren berücksichtigen oft nicht die volle Komplexität der bei modernen Modellen üblichen mehrstufigen Reasoning-Spuren.
Mangelnde Generalisierung: Viele Ansätze erfordern modellspezifisches Retraining, was sie für diverse oder proprietäre Modell-Deployments unpraktikabel macht.

Methodik: PARS-Framework

Die Autoren führen PARS (Prompt-Aware Ranking Scheduler) ein, ein leichtgewichtiges Framework, das darauf ausgelegt ist, HOL-Blocking durch die Approximation von SJF-Scheduling mittels Pairwise Learning-to-Rank zu mildern. PARS besteht aus zwei primären Komponenten:

1. Pairwise-Trainierter Prädiktor

Anstatt absolute Ausgabelängen vorherzusagen (Pointwise) oder ganze Listen zu ranken (Listwise), konzentriert sich PARS auf Paarvergleiche unter Verwendung eines Margin Ranking Loss.

Trainingsziel: Das Modell wird auf Paaren von Prompts $(A, B)$ trainiert, die binäre Labels besitzen, welche angeben, welcher Prompt eine längere Antwort generieren wird.
Rauschfilterung: Um der Stochastizität zu begegnen, werden die Trainingsdaten gefiltert, um nur Prompt-Paare einzuschließen, die eine signifikante Differenz in den Ground-Truth-Antwortlängen aufweisen (definiert durch eine relative Varianzschwelle $\delta = 0,2$ ). Dies stellt sicher, dass das Modell aus „informativen“ Paaren lernt, bei denen die relative Ordnung gegenüber dem Sampling-Rauschen robust ist, anstatt mit Beinahe-Gleichstand-Vergleichen zu kämpfen.
Architektur: Der Prädiktor nutzt ein leichtgewichtiges BERT-base-uncased Backbone. Er extrahiert das [CLS] Token-Embedding aus dem Prompt und leitet es durch einen Linear Layer, um einen Skalarwert zu generieren, der die erwartete Antwortkosten repräsentiert.
Loss-Funktion: Das Modell wird mittels Margin Ranking Loss optimiert: $L(s_A, s_B, y) = \max(0, -y \cdot (s_A - s_B) + \text{margin})$ , was eine Trennungsmarge zwischen den Scores korrekt gerankter Paare erzwingt.

2. Prädiktor-gesteuerter Scheduler

Der trainierte Prädiktor wird in das vLLM Serving-System integriert, um die Waiting Queue (W) und die Running Queue (R) zu verwalten.

Scheduling-Logik: Bei Ankunft werden die Requests durch den Prädiktor bewertet. Die Warteschlange wird nach diesen Scores sortiert (aufsteigende Reihenfolge der erwarteten Länge), um kürzere Aufgaben zu priorisieren, was effektiv SJF approximiert.
Starvation-Prävention: Um zu verhindern, dass langlaufende Aufgaben unendlich lange aufgeschoben werden, verfügt PARS über einen Mechanismus, der die Priorität jedes Requests erhöht, der ein konfigurierbares Zeitintervall (Standard: 2 Minuten) überschritten hat.
Implementierung: Der Scheduler operiert auf Iterationsebene, ist kompatibel mit Continuous Batching und erfordert keine Modifikation der zugrunde liegenden C++/CUDA Backends von vLLM.

Zentrale Beiträge

Neuartiger Pairwise-Ansatz: Das Paper schlägt eine Pairwise Learning-to-Rank-Methode mit Margin Ranking Loss und Datenfilterung vor, die im Vergleich zu Pointwise- und Listwise-Baselines eine größere Stabilität gegenüber der stochastischen Natur der LLM-Generierung zeigt.
Reasoning-bewusstes Design: Das Framework schließt explizit vollständige Reasoning-Spuren (Zwischengedanken und Begründungen) in die Definition der Antwortlänge ein, wodurch es für moderne Reasoning-LLMs geeignet ist.
Nahtlose Integration: PARS ist als Open-Source-Modul innerhalb von vLLM implementiert (ca. 1.000 Zeilen Code) und erfordert keine Änderungen am Kern des Inference-Engines.
Cross-Modell-Generalisierung: Die Autoren zeigen, dass ein auf einem Modell (z. B. GPT-4) trainierter Prädiktor effektiv Aufgaben für andere diverse Modelle (z. B. Llama 3.1, DeepSeek-R1) steuern kann, ohne ein Retraining durchzuführen.

Experimentelle Ergebnisse

Umfangreiche Evaluierungen wurden über mehrere Datensätze (Alpaca, LMSYS-Chat-1M, MATH-plus, Evolved Codealpaca) und Modelle (Llama 3.1, GPT-4, DeepSeek-R1) durchgeführt.

Prädiktor-Genauigkeit: PARS erreichte die höchste Kendall's Tau ( $\tau_b$ ) Ranking-Genauigkeit über alle Datensätze hinweg und erreichte bis zu 0,96 auf dem Alpaca-Datensatz. Es übertraf Pointwise- und Listwise-Baselines signifikant, insbesondere bei Reasoning-Modellen (z. B. eine 5,5-fache Verbesserung gegenüber Pointwise SJF auf LMSYS-Chat-1M mit DeepSeek-R1).
Latenzreduktion: In realen Workloads reduzierte PARS die durchschnittliche Per-Token-Latenz um bis zu 15,7× im Vergleich zum Standard-vLLM FCFS-Scheduler auf Llama 3.1. Unter Burst-Lastbedingungen (2.000 simultane Requests) erzielte es eine bis zu 7,7× Beschleunigung auf Llama und über 2× auf DeepSeek-R1.
Tail-Latenz: PARS verbesserte die p90-Latenz signifikant und reduzierte sie um bis zu 12,3× im Vergleich zu FCFS, womit es eine Performance nahe an dem idealisierten „Oracle SJF“ (welches die Ground-Truth-Längen verwendet) erreichte.
Durchsatz & Overhead: Die Methode hielt den Systemdurchsatz (Requests pro Sekunde) aufrecht oder verbesserte ihn leicht, indem sie die Batch-Homogenität erhöhte. Der Laufzeit-Overhead für Scoring und Sorting war vernachlässigbar (ca. 0,08 % der gesamten Serving-Zeit), ohne zusätzliche Latenz zur Request-Ausführung hinzuzufügen.
Generalisierung: Die Variante „Cross-Model PARS“, die ausschließlich auf GPT-4-Daten trainiert wurde, konnte Aufgaben für Llama und DeepSeek-R1 erfolgreich steuern und übertraf dabei modellspezifische Pointwise-Baselines sowie entsprach den Listwise-Ansätzen.

Signifikanz und Behauptungen

Das Paper postuliert, dass mit der Verbreitung von reasoning-fähigen LLMs die Variabilität der Inferenzzeiten FCFS zunehmend ineffizient machen wird. Die Signifikanz von PARS liegt in seiner Fähigkeit, eine praktische, einsatzbereite und leichtgewichtige Alternative zu schwergewichtigen oder modellspezifischen Scheduling-Lösungen zu bieten.

Die Autoren behaupten:

Pairwise Ranking ist überlegen für das LLM-Scheduling, da es sich auf robuste relative Vergleiche statt auf instabile absolute Vorhersagen konzentriert.
Generalisierung ist ohne Retraining erreichbar, was es einem einzelnen Prädiktor ermöglicht, heterogene Flotten von LLMs zu verwalten.
Minimaler Overhead macht den Ansatz für Produktionsumgebungen, in denen Reaktionsfähigkeit kritisch ist, lebensfähig.

Die Arbeit kommt zu dem Schluss, dass, obwohl die Magnitude der Gewinne von der Variabilität der Aufgabenlänge abhängt, PARS einen robusten Mechanismus bietet, um relative Ausführungskosten zu erfassen, das HOL-Blocking effektiv zu mildern und ein Low-Latency-Serving für die nächste Generation von KI-Anwendungen zu ermöglichen. Die Software und die Datensätze werden als Open-Source zur Verfügung gestellt, um die Adoption in Forschung und realer Weltanwendung zu fördern.