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.