The order in which requests land on the GPU doesn't stop mattering at TTFT (Time to First Token). Even after decode begins, the scheduler re-decides every iteration whether to keep a request in the current batch. The path from that decision to a TPOT (Time Per Output Token) SLO violation is more direct than it looks, and the way priority policies interact with that path is considerably more complex than most initial designs account for.
TPOT SLO violations happen in the middle of generation
The moment a decoding request gets bumped from the batch, its next-token generation stalls. Running Llama-3 8B on an A100, a healthy decode request produces tokens roughly every 40 ms per iteration. Hit that request with a preemption and the inter-token gap immediately climbs past 200 ms. Route through a KV cache CPU swap and recovery, and the gap widens further.
The majority of TPOT p99 SLO breaches follow this pattern — not because the model is slow, but because the scheduler evicted a request. Users experience the stream freezing for hundreds of milliseconds; the cause is an interrupted decode phase.
The vLLM scheduler selects preemption candidates based on KV block availability. Under the default FCFS policy, it evicts from the tail of the queue — the most recently arrived requests first. Preemption carries two costs: the wall-clock gap until the evicted request resumes, and, when using the recompute path, the redundant cost of re-running prefill from scratch.
How the iteration-level scheduler makes decisions
Before Orca (Yu et al., 2022) introduced iteration-level scheduling, LLM serving systems built batches at the request level: once a batch was formed, those requests held the GPU until they emitted an EOS token. Orca broke that granularity down to the iteration. At the end of every forward pass, the scheduler assembles the next batch from scratch.
In this structure, the scheduler runs the following sequence at the start of each iteration:
1. Check KV blocks needed by running requests for the next iteration
2. If free blocks are insufficient, select preemption candidates (running → waiting)
3. Select requests to promote from the waiting queue ← where the priority policy intervenes
4. Assemble batch from running + newly promoted requests → execute forward pass
Step 3 is where FCFS, SJF, and Priority diverge. Which request gets pulled from the waiting queue — and who gets evicted in step 2 — differs by policy.
FCFS processes the queue in arrival order. It is simple to implement and guarantees fairness by arrival time, but a long request at the head of the queue blocks shorter requests that arrived later — classic head-of-line blocking. Orca itself used FCFS as its default, and vLLM does as well.
SJF (Shortest Job First) schedules requests with the shortest predicted output length first. The theoretical advantage is that clearing short requests quickly reduces queue depth and improves average latency.
Priority Scheduling assigns priority labels to requests and processes higher tiers first. This maps naturally onto paid-tier differentiation or separating interactive from batch traffic.
Why priority scheduling cannot avoid starvation
Consider a scenario where high-priority requests arrive continuously. Each iteration, the scheduler scans the waiting queue in descending priority order to fill the batch. Low-priority requests, even ones already running, become preemption candidates the moment KV blocks run short. A decoding low-priority request gets bumped to make room for an incoming high-priority one.
When a low-priority request is preempted and its KV blocks are reclaimed, it goes one of two ways. With swap, the KV blocks are moved to CPU memory for later resumption, at the cost of memory bandwidth. With recompute, prefill runs from scratch. In both cases, that request's TPOT has already logged a spike.
Aging can be used as a mitigation. As a request waits longer, its effective priority rises until the scheduler is forced to process it. The vLLM SJF RFC formalizes this as a TimeAndLengthScorer — queue order is determined by a score combining a wait-time weight (default 0.5) and the reciprocal of predicted length. Fairness scheduling research shows aging policies can reduce mean end-to-end latency by more than 10% compared to FCFS.
However, while aging is busy raising a low-priority request's effective priority, that request may already be holding KV blocks — and eviction can fire before aging kicks in. KV cache capacity contention is resolved before the aging weight calculation has any effect. Aging adjusts queue order; KV block reclamation is a separate decision. When these two decisions conflict, a low-priority request can find itself promoted in the queue by aging yet still unable to run because no blocks are available.
Under sustained high-priority load at λ_high = 2 req/s, low-priority requests exhibit a pattern of experiencing preemption after tens of iterations — which in production manifests as TPOT spikes of seconds to tens of seconds.
Why SJF doesn't work as well in LLM serving as theory predicts
SJF's premise is that job length is known in advance. In LLM serving, output token count is not known at prefill time. Without a user-specified max_tokens, the count is unknown until the model emits EOS. Even with max_tokens set, whether generation actually stops before that limit is unknowable.
A prediction model can work around this — estimate output length from input length and context features, then use that estimate to order the SJF queue. The problem is prediction error. A request classified as short gets scheduled early; if it turns out to be much longer than predicted, the batch slot and KV blocks it occupies degrade TPOT for every other request. In this scenario, SJF yields higher p99 TPOT than FCFS.
In the vLLM SJF RFC experiments, SJF improved throughput by 6.2% on variable-length input scenarios. That figure is a mean-performance metric. On heavy-tail traffic distributions with large prediction error, the outcome reverses. The exact condition under which SJF makes p99 TPOT worse than FCFS is high variance in request length — which is precisely the condition where predictions are most likely to be wrong.
TPOT distribution across three policies under identical traffic
With identical Poisson arrival rate (λ = 4 req/s), the TPOT distribution diverges across the three policies depending on the request-length distribution. The throughput figure (+6.2%) comes from the vLLM RFC experiments; the remaining entries reflect relative trends across distribution conditions.
| Policy | Uniform dist. p99 TPOT | Heavy-tail dist. p99 TPOT | Starvation risk | Throughput (uniform) |
|---|---|---|---|---|
| FCFS | Baseline | Large increase over baseline | Low | Baseline |
| SJF | Slight decrease | Increases above baseline | High for long requests | +6.2% |
| Priority (high-priority) | Decrease | Decrease maintained | Low | Similar |
| Priority (low-priority) | Large increase | Very large increase | Very high | Similar |
The larger the variance in request length, the more policy choice matters. Under a uniform distribution, differences between the three policies are on the order of tens of milliseconds. Under a heavy-tail distribution, p99 TPOT can differ by hundreds of milliseconds depending on policy. The reason low-priority p99 spikes most under Priority Scheduling is that preemptions accumulate through repeated eviction cycles.
The conflict between fairness SLO and throughput SLO
Maximizing throughput requires keeping batches full. A full batch leaves no KV block headroom, and no headroom means existing requests must be evicted to admit new ones. Honoring a fairness SLO — guaranteeing all requests stay within some TPOT bound — requires reducing preemptions, which means capping batch size conservatively and accepting lower throughput. There is no single policy that simultaneously achieves both objectives.
Sarathi-Serve (Agrawal et al., OSDI 2024) partially mitigates this conflict with chunked prefill. It splits prefill into fixed-size chunks and runs them alongside decoding requests in the same iteration (decode-first). New requests are brought into the batch incrementally without interrupting in-progress decodes, yielding 2.6× serving capacity improvement on Mistral-7B and 3.7× on Yi-34B. The scope of what this solves is the throughput-latency tradeoff; starvation caused by priority bias remains a separate, unresolved problem.
The SGLang scheduler integrates prefix caching into scheduling. It groups requests that share a common prefix to maximize KV cache hits, and in doing so, cache locality functions as a de facto priority independent of arrival order — a different form of scheduling bias from vLLM's FCFS or Priority policies.
For operators choosing a policy, the decision reduces to the service's objective. A single-tier API that must guarantee uniform TPOT across all requests should treat FCFS as the safest baseline. If fast completion for short requests matters and some latency increase for long requests is acceptable, SJF is worth considering — provided output length prediction quality is sufficient to support it. If Priority Scheduling is required, aging must be configured alongside it, and the p99 TPOT SLO for low-priority requests should be treated as a soft target rather than a hard guarantee when setting thresholds.