admitctl

Put a scheduler in front of a real, memory-constrained LLM server and ask: under KV-slot pressure, does admitting short requests ahead of long ones beat first-come-first-served on the measured latency-throughput-SLO frontier?

The metrics are real wall-clock latencies against a live llama.cpp server. No model judges anything.

The finding (a near-Pareto win for short requests under load)

Qwen2.5-1.5B-Instruct Q4_K_M, real llama-server, 2 decode slots, workload of 70% short (<=24 tok) and 30% long (<=256 tok) with Poisson arrivals. Full numbers in bench_results/frontier.md.

The server saturates near 2 to 3 requests/second (about 195 tok/s over a mean request of ~94 tokens). Deep in underload (lambda=1) the queue is shallow, both policies meet the SLO (0.99), and the short-p99 gap is small (~1s). The gap then grows monotonically as load crosses saturation: short-p99 delta +1s (lambda=1) -> +2.3s (2) -> +10s (3) -> +18s (4) -> +38s (22). Above saturation a real queue builds and the admission order decides who waits:

• SJF cuts short-request tail latency by roughly 16x and holds it flat under load. At lambda=22 req/s, short-request p99 is 2.5s under SJF versus 40.8s under FCFS. Across the overloaded sweep (lambda 6 to 22) SJF keeps short p99 near 2.4s while FCFS grows from 29s to 41s.
• SLO attainment is about 5x better (0.74 under SJF vs 0.12 to 0.15 under FCFS at a 4s deadline), and median latency is about 10x lower (1 to 2s vs 12 to 17s).
• It costs nothing. Throughput is matched or slightly better (SJF 199 vs FCFS 197 tok/s), and the long requests are not starved: long-request p99 is 41.3s under SJF vs 42.0s under FCFS. Under a finite overload the makespan is bounded by total work, so the last long finishes at about the same time either way.

So under KV-slot saturation, size-aware admission is close to a free win for the short requests: much lower tail and SLO for them, no worse for the long ones, no throughput cost. The mechanism is plain head-of-line blocking: with two slots held by long generations, a 2-token request stuck in a FCFS queue waits behind the entire backlog; SJF lets it jump.

Why it works, and where it stops working

• Underload: the queue is shallow, so there is little to reorder and both policies meet the SLO; the short-p99 gap is small (~1s at lambda=1) and grows steeply only as load crosses the ~2 to 3 req/s saturation point.
• Finite vs unbounded overload: here the workload is a finite batch, so the queue drains and long requests finish at the makespan regardless of policy. Under an UNBOUNDED arrival stream held above saturation, SJF would starve the long requests indefinitely. That is the honest boundary of this result, not a property it claims to have solved.

What would falsify or change this

• Preemption or more slots. More decode slots, or preemptive scheduling, shrink the FCFS head-of-line penalty; the SJF gap should narrow. If it does not, blocking is deeper than slot count.
• A different length mix. A workload with few long requests, or uniform lengths, leaves little for SJF to reorder. The 70/30 mix is where the effect is large.
• A starvation-aware policy. SJF is the aggressive extreme. An aging or deadline-aware policy would trade a little short-latency for a long-starvation guarantee; this repo measures the extremes (FCFS and SJF), not that middle.

Limitations (named, not hidden)

• One model and size (Qwen2.5-1.5B-Instruct Q4_K_M), one node, CPU/Metal, one synthetic 70/30 length mix, two decode slots, non-preemptive policies, finite-batch overload.
• Latency is real wall-clock on one machine; absolute milliseconds are hardware-specific. The policy comparison is paired (same workload per seed) so the deltas transfer better than the absolutes.

How it is measured

1. Workload (workload/). Deterministic Poisson arrivals with a length mix, seeded so every policy replays identical arrivals and prompts.
2. Scheduler (sched/). Holds arrivals in a queue, admits up to the slot budget concurrently, picks the next by policy (FCFS or SJF), and records real queue-wait and end-to-end latency. Race-clean under -race.
3. Backend (backend/). Each admitted request is a real chat completion against the llama-server.
4. Metrics and sweep (metrics/, cmd/). Percentile latencies, throughput, SLO attainment, bootstrap CIs; the sweep replays every policy across arrival rates and seeds.

Build and test

go test -race ./...          # all packages, race-clean
./scripts/gate.sh            # gofmt + vet + race tests + ASCII

Reproduce the frontier

Needs a local llama-server on a Qwen2.5-1.5B-Instruct GGUF with a bounded slot count:

llama-server -m qwen2.5-1.5b-instruct-q4_k_m.gguf --alias qwen-admit \
  --parallel 2 --ctx-size 2048 --port 8092 --metrics &
./reproduce.sh 8092

Numbers here are Qwen2.5-1.5B-Instruct Q4_K_M on Apple M4 Pro.

License

MIT. See LICENSE.