Batched Generation in LLM Serving: How Request Scheduling Impacts Performance
The core problem is that Large Language Models generate text one token at a time. Some requests result in a one-sentence answer, while others trigger a five-page essay. When you group these together, the shortest request is often held hostage by the longest one. This "long-tail problem" is why advanced batched generation and request scheduling have become the secret sauce for companies trying to scale their AI without burning through their entire cloud budget.
The Shift from Static to Continuous Batching
For a while, the industry relied on static batching. In this setup, the server waits until it has a group of requests (say, 32), processes them all together, and doesn't start a new group until every single request in the current batch is finished. The problem? If 31 requests finish in two seconds but one request takes twenty seconds, your GPU sits mostly idle for eighteen seconds. It's a massive waste of compute.
Enter Continuous Batching. Instead of waiting for the whole group to finish, the scheduler treats the batch as a fluid queue. As soon as one sequence hits its stop token or reaches its length limit, it's kicked out of the batch, and a new request from the waiting line is slid right into its place. This happens at the iteration level-literally token-by-token. According to data from the Machine Learning at Scale analysis, this shift alone can increase throughput by 3-5x compared to the old static way. It transforms the GPU from a stop-and-go traffic jam into a high-speed conveyor belt.
How vLLM and PagedAttention Solve the Memory Gap
Batching isn't just about timing; it's about memory. Every time an LLM generates a token, it stores a "KV cache" (Key-Value cache) to remember previous parts of the conversation. In traditional systems, this memory is allocated in large, contiguous blocks. This leads to massive fragmentation-think of it like a parking lot where you can't park a small car unless you have a spot specifically sized for a semi-truck.
vLLM changed the game by introducing PagedAttention. This technology is heavily inspired by virtual memory in operating systems. Instead of one giant block, PagedAttention partitions the KV cache into small blocks (typically 16KB). If the model needs more space, the scheduler just assigns another block from a pool, regardless of where it is in physical memory. Research from UCSD published in June 2024 shows this reduces memory fragmentation by up to 70%, allowing servers to fit significantly more requests into a single batch without crashing from "out-of-memory" errors.
| Strategy | GPU Utilization | Latency Profile | Best For... |
|---|---|---|---|
| Static Batching | Low (40-60% waste) | High tail latency | Simple, low-traffic apps |
| Continuous Batching | High | Predictable average | General production use |
| Learning-to-Rank | Very High | Optimized throughput | High-scale enterprise APIs |
The Impact of Scheduling Algorithms on Output
Not all schedulers are created equal. How you pick which request enters the batch next directly impacts how long a user waits. The simplest method is First-In-First-Out (FIFO), but that often leads to "starvation," where a massive request blocks everyone else. To fix this, developers use more sophisticated logic:
- Length-Aware Scheduling: This groups requests with similar prompt lengths together. It's better than FIFO, but it has a blind spot: it doesn't know how long the *output* will be.
- Learning-to-Rank (LTR): Pioneered by the Hao AI Lab at UCSD, this approach uses a small model to predict the generation length based on the user's input and the type of application. By predicting the future, the scheduler can organize the batch to maximize tokens per second. Their experiments showed a 23.7% throughput increase over FIFO on an NVIDIA A100 GPU.
- SLA-Aware Scheduling (SLAI): This is for when deadlines matter. If a request is about to miss its per-token latency target, the scheduler boosts its priority. This can slash tail latency (the 99th percentile of slowest requests) by as much as 34%.
There is a trade-off here. A complex scheduler like Magnus-which uses a generation length predictor and a serving time estimator-can lower average latency by 22.8%, but it adds overhead. You're spending a few extra milliseconds of CPU time to save seconds of GPU time. In a high-traffic environment, that's a trade you make every single time.
Practical Tuning for Production
If you're deploying a framework like vLLM, you can't just hit "start" and walk away. Two parameters will dictate your success: max_num_seqs and max_num_batched_tokens. The first controls how many separate requests can be in the batch at once, while the second limits the total number of tokens processed in one iteration.
Set max_num_seqs too high, and you'll risk memory overflows during long-running requests. Set it too low, and your GPU will be underutilized. Most production engineers spend a few days tuning these based on their specific workload. For example, if your users mostly ask for short summaries, you can crank up the number of sequences. If they're asking for full-length code implementations, you'll need to lean more heavily on the max_num_batched_tokens limit to keep the system stable.
One pro tip: always send your prompts as a single list to the generate function rather than calling the API in a loop. This allows the internal scheduler to see the full queue and make the most efficient batching decisions from the start.
What is the difference between static and continuous batching?
Static batching processes a fixed group of requests and waits for all of them to finish before starting the next batch. Continuous batching dynamically adds new requests to the batch as soon as any single request in the current group finishes, drastically increasing GPU utilization and throughput.
How does PagedAttention reduce memory fragmentation?
PagedAttention treats the KV cache like virtual memory in an OS, breaking it into small, non-contiguous blocks. This prevents the system from needing to reserve huge, unbroken chunks of memory for every request, which can reduce fragmentation by up to 70%.
Which scheduling algorithm is the fastest for throughput?
Learning-to-rank (LTR) schedulers generally offer the highest throughput because they use predictive models to group requests based on expected output length, avoiding the efficiency drops seen in simple FIFO or basic length-aware scheduling.
Can batched generation affect the quality of the model output?
No. Batching and scheduling only affect the speed and efficiency of how tokens are delivered. They do not change the underlying weights of the model or the mathematical process of token prediction, so the actual content of the answer remains the same.
What is the 'long-tail problem' in LLM serving?
The long-tail problem occurs when a small number of requests require significantly more tokens than the average. In static batching, these few long requests force all other shorter requests in the batch to wait, leading to wasted GPU cycles and poor user experience.
Next Steps for Optimization
If you're just starting, stick with vLLM or TensorRT-LLM; their default continuous batching is a massive leap over anything manual. Once you hit a scale where every millisecond counts, look into implementing a length-prediction layer to feed your scheduler. If you're dealing with a mix of high-priority and low-priority users, moving toward an SLA-aware scheduler like SLAI will help you keep your 99th percentile latency under control. The next frontier is the WAIT and nested WAIT algorithms, which use fluid-flow approximations to handle extreme traffic spikes without collapsing.
- Apr, 17 2026
- Collin Pace
- 0
- Permalink
Written by Collin Pace
View all posts by: Collin Pace