Continuous Batching Starvation: When Long Requests Choke Out the Short Ones

Continuous batching was supposed to be the thing that saved inference utilization. Instead of waiting for a static batch to fill and finish together, the scheduler slots new requests into the batch as old ones finish their tokens, keeping the GPU busy instead of idle between waves. vLLM popularized this pattern, TGI adopted something similar, and most serving stacks built after 2023 lean on some variant of it.

Photo by panumas nikhomkhai on Pexels.

But continuous batching has a starvation problem that doesn't show up in throughput benchmarks, only in your p99 latency dashboards at 2am.

Here's the mechanism. A batching scheduler has a fixed slot budget, usually bounded by KV cache memory rather than compute. Say you can fit 64 concurrent sequences given your cache size and model dimensions. When a short request comes in asking for 50 tokens, it occupies a slot for a handful of decode steps and frees up fast. A long request asking for 4,000 tokens occupies that same slot for potentially minutes. If your admission policy is pure FIFO with no regard for expected output length, you end up with slots dominated by long-runners while short requests queue behind them, even though the short requests would finish almost instantly if admitted.

I saw this on a production chat endpoint handling a mix of simple Q&A (short outputs) and document summarization (long outputs). Median latency looked fine on paper: around 800ms. But p99 was sitting at 14 seconds, and when we traced individual requests, the slow ones were short completions stuck in queue behind summarization jobs that had claimed slots 90 seconds earlier and weren't done.

The naive fix, prioritizing by request age, doesn't help: it just changes which class of request starves. What actually worked was a few layered changes.

First, separate your pools. Route long-context or long-output workloads to a dedicated set of replicas with their own slot budget, so a document summarization job never competes with a quick lookup for cache space. This costs you some fleet flexibility but buys predictability, which for an SLA-backed endpoint matters more than marginal utilization.

Second, if pooling isn't practical, add expected-length-aware admission. Most requests declare a max_tokens parameter anyway. Use it. A scheduler that weights admission by remaining budget (tokens generated so far versus max requested) can preempt or deprioritize slots that are clearly going long, freeing cache for requests likely to finish fast. vLLM's scheduler exposes hooks for this kind of policy injection; it is not automatic out of the box.

Third, set a hard per-request token ceiling tied to your latency SLA, not just a global max_tokens default. If your p99 target is 2 seconds and your decode throughput is roughly 40 tokens/sec per sequence under load, anything requesting more than ~80 output tokens needs to go to a different queue class entirely. Don't let your default config pretend all requests are equal citizens.

graph TD
    A[Incoming Request] --> B{Expected Output Length?}
    B -->|Short| C[Fast Pool: Low Slot Count, High Turnover]
    B -->|Long| D[Batch Pool: Reserved Slots, Relaxed SLA]
    C --> E[Continuous Batch Scheduler]
    D --> E
    E --> F[GPU Decode Step]

The deeper lesson here is that continuous batching solves a utilization problem, not a fairness problem. The scheduler happily keeps your GPU at 95% occupancy while your tail latency distribution quietly rots, because occupancy and fairness are measuring completely different things. If you only watch throughput and utilization graphs, starvation hides in plain sight. You have to trace individual request lifetimes, specifically time-in-queue versus time-in-batch, to see it at all.

Worth checking today: pull your last 1,000 completed requests, bucket them by requested max_tokens, and plot queue wait time against that bucket. If short requests show a long tail of wait time correlated with concurrent long-runners in the fleet, you have this problem right now and your dashboards aren't telling you.