Queues, Scheduling, and Admission Control

★ More production incidents are caused by bad queueing than by bad kernels. This is where tail latency lives.

1. What is it?#

Three related decisions:

QUEUEING    where do requests wait, and for how long?
SCHEDULING  which waiting request runs next?
ADMISSION   which requests do we accept at all?

The third is the one people omit, and its omission is the direct cause of most LLM serving outages.

Diagram — Admission: reject early, or queue with a bound#

flowchart LR
  R["Request"] --> V{"Valid and within<br/>context limit?"}
  V -->|"no"| E400["400"]
  V -->|"yes"| QF{"Queue full, or<br/>deadline unreachable?"}
  QF -->|"yes"| E429["429 + Retry-After<br/>fail fast"]
  QF -->|"no"| Q["Bounded queue<br/>priority / fair ordering"]
  Q --> ADM{"Slot + KV memory<br/>available?"}
  ADM -->|"not yet"| Q
  ADM -->|"yes"| RUN["Running batch"]

  class V,QF,ADM,Q queue
  class E400,E429 warn
  class RUN compute
  class R neutral

2. Problem → Why → Optimization#

PROBLEM   Under load, latency grows without bound and the system can enter a
          state it cannot recover from even after load subsides.
WHY       Unbounded queues + client retries + no cancellation = the system
          spends all its capacity on work nobody will use.
OPTIMIZE  Bound the queue, reject early, prioritize deliberately, and
          propagate cancellation.

3. Simple analogy#

A restaurant with no maximum party size and no waiting-list limit.

At 8pm, 200 people are waiting. The kitchen serves 40/hour. The 200th person will be seated at 1am and has already left. The kitchen is cooking meals for people who aren’t there.

The fix isn’t a faster kitchen. It’s a door policy: “we’re full, come back at 9” — said at the door, immediately, rather than after a three-hour wait.

Rejecting a request in 5 ms is a better user experience than serving it in 90 seconds.

4. Tiny example — the failure#

// queue.go — what happens to latency as arrival rate approaches capacity.
package main

import (
	"container/heap"
	"fmt"
	"math"
	"math/rand"
	"slices"
)

type minHeap []float64

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(float64)) }
func (h *minHeap) Pop() any          { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

// simulate: Poisson arrivals, 64 concurrent slots, log-normal service time (mean ≈ 1.65 s),
// so the system can complete about 64 / 1.65 ≈ 39 requests per second.
// maxQueue < 0 means an unbounded queue.
func simulate(arrivalRate float64, maxQueue int, simTime float64) (p50, p99 float64, rejected, completed int) {
	rng := rand.New(rand.NewSource(1))
	slots := make(minHeap, 64) // the time each slot becomes free
	var latencies, starts []float64
	queued := 0 // index of the first accepted request that has not started by "now"

	for t := rng.ExpFloat64() / arrivalRate; t < simTime; t += rng.ExpFloat64() / arrivalRate {
		for queued < len(starts) && starts[queued] <= t {
			queued++
		}
		if maxQueue >= 0 && len(starts)-queued >= maxQueue {
			rejected++ // queue full: fail fast instead of waiting
			continue
		}
		start := math.Max(t, slots[0]) // FIFO: take the slot that frees first
		done := start + math.Exp(rng.NormFloat64())
		slots[0] = done
		heap.Fix(&slots, 0)
		starts = append(starts, start)
		if done <= simTime {
			latencies = append(latencies, done-t)
		}
	}
	slices.Sort(latencies)
	n := len(latencies)
	return latencies[n/2], latencies[n*99/100], rejected, n
}

func main() {
	for _, rate := range []float64{20, 30, 35, 38, 40, 45} {
		p50, p99, _, done := simulate(rate, -1, 600)
		fmt.Printf("λ=%3.0f unbounded: p50=%6.1fs p99=%7.1fs completed=%d\n", rate, p50, p99, done)
	}
	for _, rate := range []float64{40, 45} {
		p50, p99, rej, done := simulate(rate, 100, 600)
		fmt.Printf("λ=%3.0f bounded:   p50=%6.1fs p99=%7.1fs completed=%d rejected=%d\n", rate, p50, p99, done, rej)
	}
}

The result (capacity is about 39 requests/second):

λ= 20 unbounded: p50=   1.0s p99=   10.8s completed=11922
λ= 30 unbounded: p50=   1.0s p99=   10.7s completed=17955
λ= 35 unbounded: p50=   1.1s p99=   10.4s completed=20964
λ= 38 unbounded: p50=   3.2s p99=   12.6s completed=22732
λ= 40 unbounded: p50=  18.2s p99=   30.7s completed=22973    ← collapse begins
λ= 45 unbounded: p50=  49.2s p99=   88.2s completed=23000    ← and keeps growing with time
λ= 40 bounded:   p50=   3.2s p99=   12.6s completed=22777 rejected=1198
λ= 45 bounded:   p50=   3.5s p99=   12.8s completed=22965 rejected=3920

Read the last four rows. With a bounded queue, the system completes the same number of requests, but the ones it serves get good latency and the rest get a fast, honest rejection. Without bounds, everyone gets terrible latency and no more work gets done.

Bounding the queue does not reduce throughput. It converts unusable latency into honest rejection.

5. Technical explanation#

Where LLM requests queue#

1. TCP accept backlog          (kernel)
2. API layer request queue     (asyncio)
3. Engine waiting queue        (scheduler) ← the important one
4. Within a step: prefill budget contention

Queue 3 is where TTFT is decided under load.

Bounding: three mechanisms#

A. QUEUE LENGTH LIMIT
   if len(waiting) > max_waiting: reject with 503
   Simple. But length is a poor proxy for wait time when request costs vary.

B. ESTIMATED WAIT TIME (better)
   estimated_wait = queued_tokens / current_throughput
   if estimated_wait > SLO: reject
   Requires estimating output length, which is hard — but even a crude estimate
   (use max_tokens, or a per-tenant historical mean) beats a length limit.

C. DEADLINE PROPAGATION (best, if clients cooperate)
   Client sends a deadline. Server rejects if it cannot meet it, and drops
   requests whose deadline passes while queued.
   gRPC has this natively; with HTTP use a header.

Use B at minimum. A queue of 50 short requests and a queue of 50 requests with 100k prompts are completely different situations that A cannot distinguish.

Scheduling policies#

FCFS
  ✓ fair, simple, no starvation
  ✗ one 100k-token prefill delays everyone behind it (head-of-line blocking)

SHORTEST-JOB-FIRST
  ✓ minimizes average latency (provably)
  ✗ requires knowing the length (you don't)
  ✗ starves long requests
  → approximable using prompt length + max_tokens as a proxy

PRIORITY
  ✓ necessary for multi-tenancy and tiering
  ✗ starvation without aging

WEIGHTED FAIR QUEUEING
  Each tenant gets a share of throughput proportional to its weight.
  ✓ the right answer for multi-tenant platforms
  ✗ more complex; needs per-tenant accounting

DEADLINE / EDF
  ✓ directly optimizes SLO attainment
  ✗ needs deadlines and cost estimates

Practical recommendation: FCFS within a priority class, with 2-3 priority classes, plus aging to prevent starvation, plus chunked prefill to eliminate head-of-line blocking.

Chunked prefill as a scheduling tool#

Head-of-line blocking is a scheduling problem with a mechanism solution:

Without chunking:
  one 32k prefill = 500 ms of GPU
  every decoding sequence sees a 500 ms ITL spike

With chunking (chunk = 512 tokens):
  the prefill is split into 64 chunks
  each chunk rides along with a decode step, adding ~8 ms
  every decoding sequence sees a smooth ~8 ms increase per step
  TTFT for the long request is slightly worse; ITL for everyone is much better

This is the single most valuable scheduler feature for mixed workloads (Section XIII.05).

Admission control needs a cost model#

estimated_cost(request) =
      prefill_tokens × prefill_cost_per_token
    + expected_output_tokens × decode_cost_per_token
    + kv_blocks_needed × slot_occupancy_time

expected_output_tokens: use min(max_tokens, historical_p80_for_this_tenant)

You don’t need precision. You need to distinguish “cheap” from “will occupy a slot for four minutes.”

Preemption policy#

When KV memory runs out mid-flight:

Victim selection:
  LIFO (most recently admitted)   preserves progress of long-running requests
  Largest KV                       frees the most memory per preemption
  Lowest priority                  respects tiering

Recovery:
  Recompute (re-prefill)  usually cheaper — prefill is fast, PCIe is slow
  Swap to CPU             only if the KV is large and PCIe is fast

Monitor the preemption rate. Above ~1% of steps, you’re thrashing: reduce max_num_seqs or add capacity.

6-9. Under the hood, performance, production, mistakes#

Under the hood — the metrics that matter:

queue_depth                       requests waiting
queue_wait_seconds (histogram)    THE tail-latency signal
admission_rejections_total        by reason (queue full, over quota, too long)
preemptions_total                 by reason
running_batch_size (gauge)        actual utilization
kv_cache_usage_ratio              capacity signal
time_to_first_token (histogram)   bucketed by prompt length

queue_wait separated from prefill_time is the single most useful pair of metrics in LLM serving. With them, “TTFT is bad” becomes “we’re overloaded” or “prefill got slower” — completely different fixes.

Performance: the queueing formula from Section I.05:

W_queue ≈ W_service × ρ/(1-ρ)

ρ=0.7 → 2.3× service time of waiting
ρ=0.9 → 9× 
ρ=0.95 → 19×

Target 60-75% utilization for latency-sensitive services. Higher for batch workloads.

Production:

• Always bound the queue. By estimated wait, not just length.
• Reject with 503 + Retry-After, fast.
• Separate priority classes for interactive vs batch traffic.
• Enable chunked prefill.
• Propagate cancellation on client disconnect (Section V.04).
• Alert on queue_wait p95, not on queue depth.
• Load-test to find your knee — the utilization at which latency turns up.

Mistakes:

• Unbounded queues. The root cause of metastable collapse.
• Rejecting late instead of early.
• Queue length as the admission signal when request costs vary 1000x.
• No priority classes — a batch job starves interactive users.
• No cancellation — serving abandoned work.
• Targeting 95% utilization with a latency SLO.
• Alerting on queue depth rather than wait time.

10. Hands-on exercise#

A. Reproduce the collapse. Run the simulation in section 4. Find the arrival rate at which unbounded queueing collapses. Add the bounded queue and confirm throughput is preserved while latency is not.

B. Estimated wait admission. Implement admission control based on estimated wait rather than queue length, using a crude output-length estimate. Compare rejection rates and p99 latency against the length-based policy on a heavy-tailed workload.

C. Head-of-line blocking. On a real server without chunked prefill, start 8 streaming requests then send one with a 32k prompt. Plot the streaming requests’ ITL over time. Enable chunked prefill and repeat.

D. Priority classes. Implement two priority classes with aging. Verify that (i) high-priority requests get better latency, and (ii) low-priority requests don’t starve.

E. Find your knee. Load-test a real server at increasing arrival rates. Plot p50 and p99 TTFT vs utilization. Where does p99 turn up? That’s your operating limit.

11. Interview questions#

1. Why does bounding the queue not reduce throughput?
2. What’s wrong with using queue length as an admission signal for LLM serving?
3. Explain head-of-line blocking in LLM serving and its fix.
4. What is a metastable failure and how does queueing cause one?
5. Which two metrics let you distinguish “overloaded” from “prefill got slower”?
6. Why target 70% utilization rather than 95%?
7. Design an admission control policy for a multi-tenant LLM service.
8. When you must preempt, how do you choose the victim and how do you recover?

12. Further reading#

• [FUNDAMENTAL] Google SRE Book, “Handling Overload” and “Addressing Cascading Failures”
• [FUNDAMENTAL] Bronson et al., “Metastable Failures in Distributed Systems” (HotOS 2021)
• [ESTABLISHED] Agrawal et al., “Sarathi-Serve” (2024) — chunked prefill as a scheduling tool
• [REFERENCE] vLLM core/scheduler.py
• Next: 04 — Batching in servers