Why Conservative max_new_tokens Kills Throughput

Autoregressive generation has no way of knowing how many tokens the output will be until the EOS token appears. At the moment prefill finishes, there is no way to determine how many KV slots the decode phase will need. The serving system must make some assumption about this uncertainty, and that assumption is the max_new_tokens setting.

How Reservation-Based Memory Management Works

vLLM manages the KV cache at the block (page) granularity. With the default block_size=16, when a request enters the scheduler, pages are reserved upfront based on that request's max_new_tokens:

num_reserved_pages = ceil(max_new_tokens / block_size) × batch_size

max_new_tokens=128 reserves 8 pages per request; max_new_tokens=2048 reserves 128. With a KV pool of 1,000 pages total, the maximum number of concurrently served requests changes as follows:

Reservations stay locked until decode finishes, regardless of actual usage. According to an analysis of the ShareGPT output-length distribution, the median actual output length is 21 tokens. Setting max_new_tokens=512 means more than half of all requests occupy 32 pages while using less than 5% of the reserved space.

The problem PagedAttention solved is internal fragmentation — unused memory scattered within a single request, reduced by page-granularity allocation. But external fragmentation caused by over-reservation — physical memory that other requests could use, locked out by reservations — remains. Even though pages are carved into 16-token chunks, any page preemptively claimed for anticipated future decode steps cannot be assigned to another request.

How max_new_tokens Directly Cuts GPU Utilization

In LLM serving, throughput scales nearly linearly with batch size. The more requests in the same forward pass, the more tokens are generated in the same compute time. Fewer maximum concurrent requests means smaller batches, and smaller batches mean proportionally lower throughput.

Iteration-level scheduling has been the standard since Orca (Yu et al., OSDI 2022), but even this scheduler needs free space in the KV pool every iteration to admit new requests into the batch. A large max_new_tokens saturates the KV pool quickly, leaving new requests waiting in the queue. This is the mechanism that drives up TTFT.

Sarathi-Serve (Agrawal et al., OSDI 2024) addresses this bottleneck through chunked prefill. Long prefills are split into equal-sized chunks that are interleaved with decode batches, allowing the scheduler to add new requests without stalling. This approach yielded 2.6× higher serving capacity than vLLM on Mistral-7B, 3.7× on Yi-34B, and up to 5.6× on Falcon-180B — all from changing only the scheduler and prefill strategy, not the model or the GPU.

The ShareGPT output-length distribution makes this configuration problem concrete:

• median: 21 tokens
• P90: ~4.6× the median ≈ 97 tokens
• P99: ~10.8× the median ≈ 226 tokens

Setting max_new_tokens=2048 as the default for a workload whose P99 is 226 tokens means 99% of requests reserve more than 9× the space they actually need.

When the Scheduler Reaches for Preemption

Setting max_new_tokens conservatively reduces the upfront reservation, but when actual output exceeds the reservation, the scheduler triggers preemption. vLLM has two strategies.

recompute: The request's KV cache blocks are freed and the request is sent back to the WAITING queue. On re-entry, prefill runs from scratch to regenerate the KV state. Cost is O(s²) in sequence length s.

swap-out: KV blocks are copied over PCIe to CPU DRAM and the request moves to the SWAPPED queue. On re-entry, the blocks are copied back and execution resumes. Cost is O(s).

vLLM's analysis shows that recompute is faster below sequence lengths of ~4,000 tokens and swap becomes advantageous above that. Both strategies carry real cost: the moment preemption fires, that request's latency increases by the time spent on prefill recomputation or PCIe transfer.

There is a reason preemption hits tail latency hardest. Requests that generate long outputs are most likely to exceed their reservation, and those requests already hold a large number of KV blocks when they get preempted, making recomputation expensive. p50 requests typically finish within their reservation; p99 requests cycle through preemption and recomputation, causing latency to blow up.

Fitting Length Prediction into the Pipeline

Predicting output length before prefill and using that prediction to set per-request KV reservation sizes relaxes this constraint. Instead of applying the same max_new_tokens to every request, you estimate expected output length from prompt features and reserve less for short requests and more for long ones.

Uncertainty-Aware Output Length Prediction (arXiv 2604.00499) proposes modeling the output-length distribution with a log-t distribution. Using predicted μ (R² = 0.82) and σ (R² = 0.76) parameters to adjust per-request reservation sizes, the authors report a 2.31× improvement in per-token latency over a FIFO scheduler and a 1.42× increase in offline throughput.

Sarathi-Serve's chunked prefill is an orthogonal approach. Rather than reducing reservations themselves, it lets the scheduler fill batches efficiently within the existing reservation structure. Combining the two techniques produces cumulative gains.

Predictions are never perfect, so how you design the error margin determines the real trade-off. Reserving at the p75 confidence interval of the prediction increases preemption frequency; reserving at p95 leaves some over-reservation. Which cost you're more willing to absorb depends on the variance of output lengths in your workload and your latency SLO.

Setting max_new_tokens to Match Your Traffic Distribution

The practical approach starts with measuring the actual output-length distribution:

import numpy as np
output_lengths = [len(r.outputs[0].token_ids) for r in responses]
p50, p90, p95, p99 = np.percentile(output_lengths, [50, 90, 95, 99])
print(f"p50={p50:.0f}, p90={p90:.0f}, p95={p95:.0f}, p99={p99:.0f}")

For workloads with short, light-tailed output distributions — conversational QA, summarization — setting max_new_tokens to p95 is reasonable. Preemption will occur for 5% of requests, but KV utilization improves significantly and concurrent request count rises. Code generation and long document outputs have high variance in their distributions, so either target p99 or above, or introduce a length-prediction layer to set reservation sizes per request.

Specify the preemption strategy explicitly at server startup:

vllm serve <model> --preemption-mode recompute   # default (since vLLM v1)
vllm serve <model> --preemption-mode swap        # better when sequences exceed ~4,000 tokens

Aligning max_new_tokens to p95 raises throughput, but what happens to the 5% that exceed it — recompute, swap, or request rejection — is not something the serving engine decides automatically. If you do not configure this policy explicitly, preemption will silently eat your p99 latency.