Priority scheduling decides whose request runs next when demand exceeds the tokens-per-second an engine can produce. A pure first-come-first-served queue treats a paying customer’s 20-token chat turn and an anonymous user’s 4,000-token batch job identically — and the long job, arriving first, makes everyone behind it wait. Priority scheduling breaks that tie deliberately: it assigns each request a priority, serves higher priorities first, and adds guardrails so the losers are not starved forever. This piece works through the mechanics that matter for an LLM server — priority classes, weighted fair queuing, preemption of in-flight low-priority work, the priority-inversion trap, aging to prevent starvation, SLO-tiered priority, and the tension between latency for the favored and fairness for everyone else.
Why serving needs priority at all
An inference engine has a fixed budget: some number of tokens per second, set by the model, the hardware, and the batch size the KV cache can hold. When the arrival rate of work exceeds that budget, requests queue, and something must choose the order. FIFO is the default, and it is quietly unfair — it optimizes for arrival time, which nobody cares about.
Two forces make ordering matter. First, LLM requests are wildly unequal: output length varies by orders of magnitude, so one long generation can hold a batch slot for seconds while short turns pile up behind it. Second, requests are worth unequal amounts: a paid interactive session and a free-tier bulk job have different latency needs and different value. Priority scheduling encodes those differences into the run order — protecting the requests that matter from the ones that do not.
Priority classes and the strict-priority queue
The simplest model assigns every request an integer priority class — say p = 0 (highest) through p = 3 — and keeps one queue per class. The scheduler pulls from the lowest-numbered non-empty queue. Formally, a request in class k runs only when every queue j < k is empty. This is strict (preemptive) priority.
The appeal is predictability: as long as high-priority load stays below capacity, class 0 sees latency as if the lower classes did not exist. The math is a priority M/G/1 result — the expected wait for class k depends only on the load from classes 0..k, so higher classes are insulated from everything beneath them. The danger is symmetric: if class-0 demand alone saturates the engine (utilization ρ_0 → 1), every lower class waits indefinitely. Strict priority gives the top tier perfect isolation and the bottom tier no floor at all.
How priority acts inside a continuous batch
On an LLM server, priority is not applied to a single-server queue but to admission into the running batch. Continuous batching keeps a set of active sequences and, whenever a slot frees or KV memory allows, admits a waiting request. Priority scheduling governs that admission choice: when a slot opens, take the highest-priority waiter, not the oldest.
This matters because the batch is where the tokens-per-second budget is spent. A sequence already decoding consumes a slot and KV cache every step until it ends, so admission decisions are sticky — a low-priority request admitted now may occupy resources for hundreds of steps. Pure admission-time priority controls who gets in but not who stays in. If high-priority traffic arrives after the batch is full of low-priority long generations, ordering the wait queue does nothing; you need preemption to reclaim committed resources.
Weighted fair queuing: sharing instead of dominating
Strict priority is all-or-nothing. Often you want the top tier to get more throughput, not all of it. Weighted fair queuing (WFQ) assigns each class a weight w_k and divides capacity in proportion: class k receives a share w_k / Σ_j w_j of the tokens-per-second budget whenever it has work.
WFQ is usually implemented with virtual times. Each request is stamped with a virtual finish time F = max(virtual_now, F_prev) + cost / w_k, and the scheduler always dispatches the smallest F. Dividing the request’s cost by its weight means a heavier class advances its virtual clock more slowly and so gets served more often. With weights w = (8, 2, 1) across three tiers, the premium tier draws roughly 8/11 ≈ 73% of throughput under contention — but the lowest tier still gets its 1/11 and never starves. WFQ is the workhorse when you want tiered service with a floor.
Preempting low-priority requests
When a high-priority request arrives and the batch is full, admission ordering is too late — the resources are already spent. Preemption evicts an in-flight low-priority sequence to make room. The evicted sequence’s state is its KV cache, and there are two ways to preserve it.
Swapping copies the KV cache out to host RAM (or disk) and restores it when the sequence resumes; cost is the memory-bandwidth transfer of 2 · layers · heads · d_head · tokens values in and out. Recomputation discards the cache and reruns the prefill when resumed; cost is compute, scaling with length. Recompute wins for short sequences and swap wins for long ones, since transfer grows linearly with tokens while prefill FLOPs grow faster. Either way, preemption is what lets strict priority mean what it says: the top tier can reclaim capacity from work already running, not merely jump the queue.
Priority inversion
Priority inversion is when a high-priority request is effectively blocked by a lower-priority one — the failure the whole scheme is meant to prevent, sneaking back in through shared resources. In classic OS scheduling it happens when a low-priority task holds a lock the high-priority task needs. In LLM serving the shared resource is usually KV-cache memory or a batch slot.
Concretely: the batch is packed with low-priority long generations that have consumed all KV memory. A premium request arrives, but there is no free block to admit it — so despite its priority it waits behind work it outranks. Ordering the queue did not help, because the contention is over committed memory, not queue position. Two fixes restore the intended order: reservation (hold a pool of KV blocks for high tiers) and preemption (evict a low-priority sequence to free blocks). Recognizing inversion means looking past the queue to every resource it contends for.
Starvation and aging
Strict priority’s dark side is starvation: if high-priority work keeps arriving, low-priority requests may never run. On a public endpoint that is a failure mode, not a corner case — free-tier users time out while premium traffic flows. The standard cure, borrowed straight from operating-system schedulers, is aging.
Aging raises a request’s effective priority the longer it waits. A simple linear form is p_eff = p_base − α · wait, where smaller means more urgent and α tunes how fast a starving request climbs. A class-3 request that has waited long enough eventually reaches class-0 urgency and is forced through. This converts a hard guarantee (‘class 0 always wins’) into a soft one (‘class 0 usually wins, but nobody waits past a bound’). The knob α sets the ceiling on worst-case wait: larger α tightens the fairness floor at the cost of occasionally delaying a premium request.
SLO-tiered priority
Priority classes are most defensible when they derive from service-level objectives rather than arbitrary labels. An interactive tier might target a time-to-first-token under 200 ms, a batch tier only ‘within an hour’ — SLO-tiered priority turns those targets into scheduling order.
The clean formulation borrows earliest-deadline-first (EDF). Give each request a deadline d = arrival + SLO and always run the nearest deadline. EDF is optimal in the sense that if any ordering can meet all deadlines, EDF does. In practice servers use a hybrid: coarse priority classes for isolation, with deadline or slack (slack = d − now − remaining_service) breaking ties inside a class. This is really aging with a principled α — a request’s urgency rises automatically as its deadline nears. Tying priority to SLOs also makes the system self-documenting: the schedule provably reflects the promises you sold, and a missed deadline points at a capacity problem, not the ordering logic.
The latency-versus-fairness tradeoff
Every priority policy sits on one axis: latency for the favored versus fairness for the rest. Strict priority sits at the latency extreme — it minimizes high-tier wait and offers the low tier no guarantee. Plain FIFO sits at the fairness extreme — perfectly equal treatment, blind to value or urgency. Every useful policy lives between them.
The tension is real because capacity is conserved: total wait is roughly fixed by utilization, so time you save the premium tier is time you add to someone else. Shortest-job-style ordering can lower mean wait, but it does so by penalizing long requests. WFQ weights, aging’s α, and reserved KV pools are all knobs for choosing a point on this curve. The honest way to set them is to state the fairness floor first — the worst-case latency the lowest tier must never exceed — then push premium latency as low as that floor permits.
Practical notes for CPU-hosted small models
On a CPU-served small language model the budget is tight and preemption is cheap, which shifts the design. Batch sizes are small, so a single long generation blocks proportionally more of your capacity — making priority ordering more valuable, not less. Because sequences and KV caches are modest, recomputation is often the better preemption strategy: rerunning a short prefill costs little, and you skip the memory traffic of swapping.
Keep the mechanism simple. Two or three priority classes with a reserved slot for the interactive tier, plus linear aging to bound the worst case, captures most of the benefit without an elaborate virtual-time scheduler. Watch two pitfalls: setting α so low that starvation returns, and forgetting that priority governs admission while the batch governs residence — without preemption, a full batch of low-priority work silently inverts every guarantee you have.