Request Scheduling and Priorities — Advanced LLM Inference

1. What the scheduler decides, restated#

Every iteration:

1. which waiting requests to admit
2. how to allocate the token budget between prefill and decode
3. whether to preempt anyone
4. in what order to serve them

Section V.09 covered the mechanism. This file covers policy — the part that determines whether your multi-tenant platform is fair, whether your SLO tiers mean anything, and whether long requests starve.

2. The policies#

FCFS
  ✓ fair in the simplest sense; no starvation
  ✗ head-of-line blocking (mitigated by chunked prefill)
  ✗ no way to express priority
  → the default in most engines

PRIORITY (static classes)
  admit higher-priority requests first
  ✓ expresses SLO tiers
  ✗ starvation without aging
  → necessary for multi-tenant platforms

SHORTEST-JOB-FIRST
  ✓ provably minimizes average latency
  ✗ requires knowing the job length — you don't
  ✗ starves long requests
  → approximable; see section 4

WEIGHTED FAIR QUEUEING (Section XII.05)
  each tenant gets a share proportional to its weight
  ✓ the right answer for multi-tenancy
  ✗ more bookkeeping

EARLIEST-DEADLINE-FIRST
  ✓ directly optimizes SLO attainment
  ✗ needs deadlines and cost estimates
  → good when clients supply deadlines

Practical recommendation: priority classes with aging, weighted fair queueing within a class, and chunked prefill to eliminate head-of-line blocking.

3. Priority with aging#

THE PROBLEM: pure priority starves low-priority requests indefinitely
             under sustained high-priority load.

THE FIX: a request's effective priority increases with its wait time.

  effective_priority = base_priority + (wait_time / aging_rate)

  base_priority:  premium=100, standard=50, free=10
  aging_rate:     e.g. 1 point per 200 ms of waiting

  → a free request waiting 10 seconds has effective priority 60,
    ahead of a newly-arrived standard request
  → bounded starvation: max wait ≈ (max_base - min_base) × aging_rate
                                 = 90 × 200 ms = 18 seconds

func effectivePriority(r *Request, now time.Time) float64 {
	wait := now.Sub(r.ArrivalTime).Seconds()
	return r.BasePriority + wait/agingRateSeconds // waiting raises priority: nobody starves
}

func scheduleAdmissions(waiting []*Request, budget *Budget, kv *BlockManager, now time.Time) (admitted []*Request) {
	slices.SortFunc(waiting, func(a, b *Request) int {
		return cmp.Compare(effectivePriority(b, now), effectivePriority(a, now)) // highest first
	})
	for _, r := range waiting {
		if !budget.CanFit(r) || !kv.CanAllocate(r) {
			break
		}
		admitted = append(admitted, r)
		budget.Consume(r)
	}
	return admitted
}

Setting AGING_RATE sets your maximum starvation bound explicitly, which is what you want: a number you can state in an SLO rather than an emergent property.

4. Approximating shortest-job-first#

You can’t know the output length, but you can estimate it.

SIGNALS
  max_tokens (the client's cap)          — an upper bound
  prompt length                           — weakly correlated
  task type (from the system prompt)      — moderately predictive
  tenant's historical distribution        — quite predictive
  model-predicted length                  [RESEARCH]

PRACTICAL ESTIMATOR
  estimated_output = min(max_tokens,
                         tenant_historical_p80(task_type))

  → good enough to distinguish "probably 50 tokens" from
    "probably 2,000 tokens"

USE IT FOR:
  ✓ admission decisions (will this fit in the remaining KV budget?)
  ✓ queue ordering (a light preference for shorter jobs)
  ✓ routing (segregate long-generation requests)
  ✗ NOT for hard scheduling decisions — the estimate is too noisy

A light preference, not a strict ordering. Strict SJF with a noisy estimator produces starvation for the requests you estimated badly.

5. Preemption policy#

WHEN: KV memory is exhausted and a running sequence needs another block.

VICTIM SELECTION
  LIFO (most recently admitted)
    ✓ preserves progress of long-running requests
    ✓ the victim has the least work to redo
    → the usual choice
  Largest KV
    ✓ frees the most memory per preemption
    ✗ preempts long-context requests repeatedly
  Lowest priority
    ✓ respects tiers
    → combine with LIFO within a priority class

RECOVERY
  RECOMPUTE: discard the KV; re-prefill when re-admitted
    cost = prefill(prompt + generated_so_far)
  SWAP: copy KV to CPU, copy back later
    cost = 2 × KV_bytes / PCIe_bandwidth

  Section XIII.07's arithmetic: recompute is often competitive or
  cheaper, and much simpler.
  → vLLM defaults to recompute.

PREEMPTION IS A SIGNAL, NOT JUST A MECHANISM

  preemption rate > 1% of steps → you are memory-starved
  → reduce max_num_seqs, or add capacity
  → do NOT just tolerate it; preemption wastes work

6. Deadline-aware scheduling#

IF CLIENTS SUPPLY DEADLINES (gRPC deadlines, or a header):

  1. reject at admission if the deadline cannot be met
       estimated_completion = now + queue_wait_estimate
                            + prefill_estimate + output_estimate × ITL
       if estimated_completion > deadline: reject immediately
     → far better than accepting and missing it

  2. drop queued requests whose deadline has passed
     → they're pure waste

  3. order by earliest deadline among admitted requests

VALUE: converts "we missed the SLO" into "we told you we couldn't
       do it, in 5 ms"

Deadline propagation is under-used and valuable, especially for agentic workloads where a step has a natural deadline derived from the overall task.

7. Scheduling for specific workloads#

INTERACTIVE CHAT
  priority: latency
  → small token budget per step (good ITL)
  → aggressive admission (low queue wait)
  → chunked prefill
  → preempt rarely (users notice)

BATCH / OFFLINE
  priority: throughput
  → huge token budget (max prefill efficiency)
  → large batch
  → preemption is free (nobody's waiting)
  → run in the traffic trough (Section XI.03)

AGENTIC (many short turns, long shared prefix)
  priority: per-step latency, and prefix reuse
  → prefix-aware routing (Section XII.07) matters more than scheduling
  → short outputs → TTFT dominates → admission speed matters
  → deadline propagation works well here

RAG (long prompts, short outputs)
  priority: prefill throughput
  → larger token budget
  → prefix caching if documents recur
  → segregate from chat traffic

Different workloads want different schedulers. If you serve several, segregate them into pools with different configurations (Section XII.06) rather than compromising one scheduler.

8. Production implications#

Priority classes with aging. Set the aging rate to bound starvation explicitly.
Weighted fair queueing within a class for multi-tenancy (Section XII.05).
Chunked prefill eliminates head-of-line blocking; do it before anything else here.
Estimate output length from tenant history; use it for admission and routing, not for strict ordering.
LIFO preemption with recompute recovery is the sensible default.
Monitor preemption rate. > 1% means memory-starved.
Deadline propagation if your clients can supply deadlines.
Segregate workload types into pools rather than compromising one scheduler.

9. Common mistakes#

Pure priority without aging. Starvation.

Strict SJF with a noisy length estimator. Starvation for mis-estimated requests.

Tolerating a high preemption rate. It wastes work; fix the cause.

One scheduler configuration for all workload types.

Not bounding the waiting queue (Section VIII.03).

Preempting the longest-running request. It has the most work to redo.

Ignoring deadlines that clients supply.

10. Hands-on exercise#

A. Implement priority with aging. Add priority classes and aging to your engine from Project 08. Verify: high-priority requests get better latency, and low-priority requests’ maximum wait is bounded by your aging rate.

B. Measure starvation. With pure priority (no aging), run sustained high-priority load and measure the low-priority p99 wait. Add aging and re-measure.

C. Length estimation. From request logs, build a per-tenant per-task-type output length estimator. Measure its accuracy (correlation, p50 and p90 error). Is it good enough for admission decisions?

D. Preemption policies. Implement LIFO and largest-KV victim selection. Under memory pressure, measure: total work wasted, p99 latency, and the distribution of which requests get preempted.

E. Deadline scheduling. Implement deadline-based admission rejection. Compare against accept-everything under overload: how many requests meet their deadline in each case?

F. Workload-specific tuning. Configure two pools — one for chat, one for RAG — with different token budgets and admission policies. Measure each workload’s SLO attainment in a shared pool versus segregated pools.

11. Interview questions#

What does the scheduler decide each iteration?
How do you prevent starvation with priority scheduling?
Why not use shortest-job-first, and how would you approximate it?
How do you choose a preemption victim, and how do you recover?
What does a preemption rate above 1% tell you?
What is deadline-aware admission and what does it buy?
Why would you segregate workload types into separate pools?

12. Further reading#

[ESTABLISHED] Yu et al., “Orca” (OSDI 2022)
[ESTABLISHED] Agrawal et al., “Sarathi-Serve” (2024)
[FUNDAMENTAL] Scheduling theory: SJF optimality, aging, EDF
[REFERENCE] vLLM core/scheduler.py and its priority scheduling support
Next: 09 — Speculative decoding variants