The scheduler doesn't know one thing at the moment a request arrives: how many tokens this request will generate.
It knows the input length. The prompt is already there, so it can calculate how many KV cache blocks prefill requires. The problem is decode. The output length isn't determined until the model emits EOS, but the scheduler has to claim KV cache memory, assemble a batch, and decide processing order before that happens. This asymmetry is the structural cause of throughput loss in LLM serving. No matter how sophisticated the scheduling algorithm, you can't build an optimal batch without knowing output lengths.
What the Scheduler Doesn't Know When Assembling a Batch
Orca (Yu et al., OSDI 2022) changed the LLM serving paradigm by introducing iteration-level scheduling. The older static batching approach waited for every request in a batch to finish before moving on. The numbers make this problem concrete.
Assume a batch size of 32. Thirty-one requests complete at 100 tokens and one runs all the way to 2,000 tokens. If each decode step takes T ms:
- Static batching: the entire batch waits for 2,000 steps. TPOT (Time Per Output Token) for the 31 short requests = 2000T / 100 = 20T ms. Batch-average TPOT = (31 × 20T + 1 × T) / 32 ≈ 19.4T ms.
- Uniform batch (all 100 tokens): TPOT = T ms.
A single straggler drives batch-average TPOT up by nearly 20×. Orca's iteration-level scheduling targets exactly this. At every step, completed requests are evicted and new ones are admitted. If 31 requests finish at step 100 and 31 new ones join, the GPU keeps processing 32 requests even though the one straggler is still running.
Continuous batching doesn't fully solve the problem, though. The straggler's KV cache still occupies GPU memory until step 2,000. When 31 slots open up at step 100, those slots come from memory left over after the straggler's allocation. KV cache blocks stay pinned as long as the straggler lives, and the effective batch-size ceiling drops.
Three Paths Through Which Output-Length Variance Erodes Throughput
Early-completion waste. Requests that finish much shorter than average free their slots quickly. When there are new requests waiting, those slots get filled immediately, so this isn't a problem under sufficient load. But when arrival rate is low or the queue has drained right after a traffic peak, those fast completions translate directly to lower GPU utilization. The higher the variance in the output-length distribution, the more frequently short requests return their slots early.
Straggler memory lock-in. The heavier the tail of the output-length distribution (p95, p99), the higher the probability that an extremely long request is in the batch at any given moment. The longer that request holds KV cache, the less free memory is available for incoming requests. Even if GPU cores aren't idle, memory becomes the bottleneck and effective batch density falls. Throughput loss here is a memory-allocation problem, not an algorithm problem.
Conservative batch sizing. When the scheduler doesn't know the output-length distribution, it keeps batch sizes low to avoid OOM. vLLM's max_num_scheduled_tokens is this control knob — the larger the safety margin operators configure, the more they under-fill batches relative to what the GPU could actually handle. That conservatism directly cuts throughput. The higher the variance of the workload, the harder it is to set an appropriate margin, and operators inevitably drift toward lower values.
How Serving Frameworks Handle This Uncertainty
vLLM's approach is reactive. It doesn't pre-reserve KV cache blocks based on max_tokens at request arrival. Instead, it allocates blocks one at a time each decode step, and when GPU memory runs out it preempts some in-flight requests and sends them back to the waiting queue. Preempted requests have to recompute their KV cache, which costs time. The max_num_scheduled_tokens parameter sets a per-batch token cap that proactively prevents OOM, and how that value is tuned determines actual throughput.
Sarathi-Serve (OSDI 2024) attacks the interference between prefill and decode rather than output-length variance itself. It addresses "prefill stalls" — long prefill computations that block in-progress decode steps — using chunked prefill: splitting prefill computation into small chunks interleaved between decode steps. On Mistral-7B on a single A100, this achieved 2.6× the serving capacity of vLLM, with up to 5.6× improvement across all model and hardware combinations. It's not a direct answer to output-length variance, but stall-free decode batches do reduce the impact of stragglers to some extent.
SGLang's radix attention specializes in KV cache prefix reuse. It improves memory efficiency for requests that share the same system prompt or few-shot examples, and delivers meaningful gains for services with high prefix cache hit rates — but it doesn't structurally address output-length variance.
How Much Does Prepending Output-Length Prediction Help?
If the scheduler can know the output-length distribution ahead of time, two things change: it can reserve memory more precisely, and it can co-schedule requests of similar length in the same batch to reduce the straggler effect.
Zheng et al. (2023), "Response Length Perception and Sequence Scheduling," used the LLM itself to predict response length and grouped similarly-sized requests into micro-batches. The result was an 86% throughput improvement. In a batch with a homogeneous length distribution, stragglers rarely form, and GPU resources are distributed across the full batch without waste.
Fu et al. (2024), "Efficient LLM Scheduling by Learning to Rank," took a different angle: instead of predicting exact lengths, predict relative rank. "Which request in this batch will be the longest?" is a much easier problem than predicting exact token counts. This approach approximates shortest-job-first (SJF) scheduling and achieved 2.8× latency reduction on chatbot serving and 6.5× throughput improvement on synthetic data generation.
S3 (Jin et al.) places a lightweight DistilBERT-based classifier in front of the serving stack to bucket each request as short, medium, or long, then builds batches within each bucket. The practical insight is that you don't need an exact length — a rough category is enough to capture the benefits of a homogeneous batch.
The direction of prediction error matters. Over-prediction (estimating longer than actual) means some reserved KV cache blocks go unused and are returned. Slots are wasted, but the system stays safe. Under-prediction (estimating shorter than actual) means a full batch ends up needing more memory than reserved, triggering OOM or preemption. Because the two error types have asymmetric costs, allowing a slight over-prediction bias when calibrating a predictor is the safer choice.
There's also a common tradeoff across all prediction-based approaches: the predictor's inference latency gets added to the request-handling pipeline. Using an LLM as the predictor adds a full extra inference call; even a lightweight model like DistilBERT introduces one more hop in the inference pipeline. If traffic patterns shift, the classifier needs retraining, and that maintenance overhead accumulates as an operational burden.
What You Can Do Right Now in Production
You can control the distribution even without an output-length prediction model.
A max_new_tokens cap is the most direct lever. Trimming the tail of the distribution reduces the probability of straggler formation and makes batches more predictable. The downside is that actual generation can be cut short — fine for QA or short summarization tasks, but a quality problem for code generation or long-form document work.
Routing by request type is often more practical. QA, short conversation, code generation, and document summarization have very different output-length distributions. Mixing these in the same batch raises the coefficient of variation (CV). Keeping them in separate queues or behind separate serving endpoints makes the length distribution inside each batch much more uniform, improving batch quality without any prediction model.
SLA design also needs to make output-length assumptions explicit. A target like "TPOT ≤ 50 ms" means nothing unless the document states which output-length distribution that assumes. Leave it implicit and your observed SLA attainment on real traffic will diverge from expectations — especially for task types where p99 output length is more than 10× the mean.