🤖 machine learning

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

Original authors: Yiheng Tao, Yihe Zhang, Matthew Dearing, Xin Wang, Yuping Fan, Michael E. Papka, Zhiling Lan

Published 2026-06-29

📖 4 min read☕ Coffee break read

Original authors: Yiheng Tao, Yihe Zhang, Matthew Dearing, Xin Wang, Yuping Fan, Michael E. Papka, Zhiling Lan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a busy coffee shop. You have a line of customers (the requests) waiting to order drinks, and you have a single barista (the Large Language Model or LLM) who makes the drinks one by one.

The Problem: The "Long Order" Bottleneck

In a traditional coffee shop, you use a "First Come, First Served" rule. If the first person in line orders a complex, 20-minute latte, everyone behind them—even the person who just wants a quick espresso—has to wait 20 minutes. This is called Head-of-Line (HOL) blocking.

In the world of AI, this is a huge problem. Some AI questions are simple and take a second to answer. Others, especially the new "reasoning" AI models that think through math problems or code step-by-step, can take minutes to generate a response. If a long, thinking-heavy request gets stuck at the front of the line, it delays everyone else, making the whole system feel slow and sluggish.

The Solution: The "Smart Predictor" (PARS)

The paper introduces a new system called PARS (Prompt-Aware Ranking Scheduler). Think of PARS as a super-smart, invisible manager standing behind the counter who can look at a customer's order slip (the prompt) and instantly guess how long the drink will take to make, before the barista even starts.

Instead of serving people in the order they arrived, this manager rearranges the line so that the "quick espresso" orders go first, followed by the "medium" orders, and the "20-minute latte" orders go to the back. This is known as Shortest-Job-First (SJF) scheduling.

How It Works: The "Pairwise" Trick

The tricky part is that AI is unpredictable. Sometimes the same question gets a short answer, and sometimes a long one, just by chance. If the manager tried to guess the exact time (e.g., "This will take 42 seconds"), they might get it wrong and mess up the line.

To solve this, PARS uses a clever trick called Pairwise Learning.

Old Way: Try to guess the exact time for every single order. (Like guessing the exact weight of a watermelon).
PARS Way: Just compare two orders at a time. Ask: "Is Order A likely to take longer than Order B?" (Like saying, "This watermelon is definitely heavier than that apple").

The system is trained to ignore the tiny, confusing differences and only focus on the obvious ones (e.g., "This math problem is way harder than this simple greeting"). By focusing on these clear comparisons, the manager becomes very good at sorting the line without getting confused by the AI's random fluctuations.

The Results: Faster Service for Everyone

The researchers tested this system in a real-world setting using a popular AI serving tool called vLLM. They found that:

Massive Speedups: By letting the short tasks go first, they reduced the average wait time for users by up to 15.7 times compared to the standard "First Come, First Served" method.
No Extra Cost: The "manager" (the predictor) is very lightweight. It takes almost no time to sort the line, so it doesn't slow down the barista.
Works on Any Model: The system is so good at guessing that if you train it on one type of AI (like GPT-4), it can still sort the line effectively for a completely different AI (like Llama or DeepSeek) without needing to be retrained. It's like a manager who learned to sort orders at a coffee shop and can immediately do the same job at a tea house.
Fairness: To make sure the "20-minute latte" orders don't wait forever, the system has a safety valve. If a long order has been waiting too long, it gets bumped up the line so no one starves.

In Summary

The paper presents PARS, a smart scheduling system that acts like a traffic cop for AI requests. Instead of letting a long, complicated request block the line, it uses a smart, comparison-based guessing game to let the quick requests zip through first. This makes the whole AI system feel much faster and more responsive, especially when dealing with the new generation of AI that likes to "think" for a long time before answering.

Technical Summary: PARS – Prompt-Aware Ranking Scheduler for Low-Latency LLM Serving

Problem Statement

The deployment of Large Language Models (LLMs), particularly the emerging generation of reasoning-capable models (e.g., DeepSeek R1, GPT-o1), faces a critical challenge in inference scheduling: Head-of-Line (HOL) blocking. Traditional serving systems, such as vLLM and Orca, predominantly rely on First Come, First Serve (FCFS) policies. In FCFS, long-running inference tasks (often characterized by highly variable and extensive Chain-of-Thought reasoning traces) block shorter tasks queued behind them, leading to significant latency spikes and reduced throughput.

While the Shortest-Job-First (SJF) policy is theoretically optimal for minimizing average latency, its application to LLMs is hindered by the stochastic and auto-regressive nature of token generation. Exact output lengths cannot be known prior to execution. Existing attempts to approximate SJF via length prediction suffer from three main limitations:

Noise Sensitivity: Pointwise (regression) and listwise ranking methods struggle with the inherent variability of LLM outputs, where similar prompts may yield fluctuating lengths across runs, introducing noisy training signals.
Reasoning Complexity: Standard predictors often fail to account for the full complexity of multi-step reasoning traces common in modern models.
Lack of Generalization: Many approaches require model-specific retraining, making them impractical for diverse or proprietary model deployments.

Methodology: PARS Framework

The authors introduce PARS (Prompt-Aware Ranking Scheduler), a lightweight framework designed to mitigate HOL blocking by approximating SJF scheduling through pairwise learning-to-rank. PARS consists of two primary components:

1. Pairwise-Trained Predictor

Instead of predicting absolute output lengths (pointwise) or ranking entire lists (listwise), PARS focuses on pairwise comparisons using a margin ranking loss.

Training Objective: The model is trained on pairs of prompts $(A, B)$ with binary labels indicating which prompt is expected to generate a longer response.
Noise Filtering: To address stochasticity, the training data is filtered to include only prompt pairs with a significant difference in ground-truth response lengths (defined by a relative variance threshold $\delta = 0.2$ ). This ensures the model learns from "informative" pairs where the relative ordering is robust against sampling noise, rather than struggling with near-tie comparisons.
Architecture: The predictor utilizes a lightweight BERT-base-uncased backbone. It extracts the [CLS] token embedding from the prompt and passes it through a linear layer to generate a scalar score representing the expected response cost.
Loss Function: The model is optimized using margin ranking loss: $L(s_A, s_B, y) = \max(0, -y \cdot (s_A - s_B) + \text{margin})$ , enforcing a separation margin between scores of correctly ranked pairs.

2. Predictor-Guided Scheduler

The trained predictor is integrated into the vLLM serving system to manage the Waiting Queue (W) and Running Queue (R).

Scheduling Logic: Upon arrival, requests are scored by the predictor. The waiting queue is sorted by these scores (ascending order of expected length) to prioritize shorter tasks, effectively approximating SJF.
Starvation Prevention: To prevent long-running tasks from being indefinitely deferred, a mechanism boosts the priority of any request that has waited beyond a configurable threshold (default: 2 minutes).
Implementation: The scheduler operates at the iteration level, is compatible with continuous batching, and requires no modification to the underlying C++/CUDA backends of vLLM.

Key Contributions

Novel Pairwise Approach: The paper proposes a pairwise learning-to-rank method with margin ranking loss and data filtering, which demonstrates greater stability against the stochastic nature of LLM generation compared to pointwise and listwise baselines.
Reasoning-Aware Design: The framework explicitly includes full reasoning traces (intermediate thoughts and justifications) in the definition of response length, making it suitable for modern reasoning LLMs.
Seamless Integration: PARS is implemented as an open-source module within vLLM (approx. 1,000 lines of code), requiring no changes to the core inference engine.
Cross-Model Generalization: The authors demonstrate that a predictor trained on one model (e.g., GPT-4) can effectively schedule tasks for other diverse models (e.g., Llama 3.1, DeepSeek-R1) without retraining.

Experimental Results

Extensive evaluations were conducted across multiple datasets (Alpaca, LMSYS-Chat-1M, MATH-plus, Evolved Codealpaca) and models (Llama 3.1, GPT-4, DeepSeek-R1).

Predictor Accuracy: PARS achieved the highest Kendall's Tau ( $\tau_b$ ) ranking accuracy across all datasets, reaching up to 0.96 on the Alpaca dataset. It significantly outperformed pointwise and listwise baselines, particularly on reasoning models (e.g., a 5.5× improvement over pointwise SJF on LMSYS-Chat-1M with DeepSeek-R1).
Latency Reduction: In real-world workloads, PARS reduced average per-token latency by up to 15.7× compared to the default vLLM FCFS scheduler on Llama 3.1. Under bursty load conditions (2,000 simultaneous requests), it achieved up to 7.7× speedup on Llama and over 2× on DeepSeek-R1.
Tail Latency: PARS significantly improved p90 latency, reducing it by up to 12.3× compared to FCFS, bringing performance close to the idealized "Oracle SJF" (which uses ground-truth lengths).
Throughput & Overhead: The method maintained or slightly improved system throughput (requests per second) by increasing batch homogeneity. The runtime overhead for scoring and sorting was negligible (approx. 0.08% of total serving time), with no additional latency added to request execution.
Generalization: The "Cross-Model PARS" variant, trained solely on GPT-4 data, successfully scheduled tasks for Llama and DeepSeek-R1, outperforming model-specific pointwise baselines and matching listwise approaches.

Significance and Claims

The paper posits that as reasoning-capable LLMs become prevalent, the variability in inference times will render FCFS increasingly inefficient. The significance of PARS lies in its ability to provide a practical, deployable, and lightweight alternative to heavyweight or model-specific scheduling solutions.

The authors claim that:

Pairwise ranking is superior for LLM scheduling because it focuses on robust relative comparisons rather than unstable absolute predictions.
Generalization is achievable without retraining, allowing a single predictor to manage heterogeneous fleets of LLMs.
Minimal overhead makes the approach viable for production environments where responsiveness is critical.

The work concludes that while the magnitude of gains depends on task length variability, PARS offers a robust mechanism to capture relative execution costs, effectively mitigating HOL blocking and enabling low-latency serving for the next generation of AI applications. The software and datasets are released as open-source to facilitate adoption in both research and real-world deployments.