TLDR: FairBatching is a new LLM inference scheduler that resolves unfair resource allocation between prefill and decode tasks, a common issue in existing systems. By using adaptive batch capacity, dynamic batch formation, and fine-grained SLO tracking, it significantly reduces Time-to-First-Token (TTFT) latency and improves overall throughput while maintaining Time-Per-Output-Token (TPOT) guarantees, leading to substantial capacity improvements in both single-node and cluster-level deployments.
Large Language Models (LLMs) are at the heart of many modern AI services, and making them run efficiently is a significant challenge. When an LLM processes a request, it typically goes through two main phases: a ‘prefill’ phase, where it processes your initial input prompt, and a ‘decode’ phase, where it generates the output tokens one by one. To keep GPUs busy and maximize performance, multiple requests are often grouped together, a technique known as batching.
However, there’s a fundamental conflict in LLM inference systems. They need to quickly deliver the first token of a new request (known as Time-to-First-Token, or TTFT) while also maintaining a smooth and consistent rate of generating subsequent tokens for ongoing requests (Time-Per-Output-Token, or TPOT). Existing batching methods, like the “stall-free batching” proposed by Sarathi, try to prevent delays in token generation. While effective at this, they often create a significant problem: computational unfairness.
This unfairness arises because these systems tend to excessively prioritize the ‘decode’ tasks. This leads to a situation where decode tasks accumulate unnecessary “slack” (meaning they are ahead of their schedule), while new ‘prefill’ tasks experience long delays in queues, severely impacting the overall quality of service. The core issue, as identified by new research, is that the metric used for scheduling (Time-Between-Tokens, or TBT) is not always straightforward, and the rigid decode-prioritizing policy struggles to adapt to sudden influxes of new requests.
Introducing FairBatching
To address these critical issues, researchers Hongtao Lyu, Boyue Liu, Mingyu Wu, and Haibo Chen from the Institute of Parallel and Distributed Systems at Shanghai Jiao Tong University have introduced FairBatching, a novel LLM inference scheduler. FairBatching is designed to ensure a fair allocation of computational resources between prefill and decode tasks. It moves away from the strict decode-prioritizing approach, allowing resources to be dynamically reallocated from decode tasks (especially those with accumulated slack) to handle surges in prefill requests. This dynamic approach aims for global fairness and improved system efficiency.
FairBatching incorporates several key innovations:
- Adaptive Batch Capacity Determination: Instead of static token budgets, FairBatching dynamically adjusts the computational budget for each batch. It uses a more accurate time-based model to estimate execution time, considering factors like new tokens and total context length, which significantly improves GPU utilization without violating service level objectives (SLOs).
- Fair and Dynamic Batch Formation: This is where FairBatching truly shines. It employs a three-phase strategy for forming batches. First, it prioritizes decode tasks that are genuinely at risk of missing their deadlines. Next, it immediately schedules prefill tasks, recognizing their time-critical nature and unpredictable arrival. Finally, any remaining capacity is allocated to non-urgent decode tasks. This intelligent prioritization ensures a balance between fairness and efficiency.
- Fine-grained SLO Attainment Tracking: FairBatching uses an “envelope-line-based” mechanism to track the progress of each request against its TTFT and TPOT requirements. This allows the system to precisely understand how far ahead or behind each task is, enabling more informed and fairer scheduling decisions.
- Integration with Cluster-Level Schedulers: For large-scale deployments, FairBatching provides a novel load estimation method called Prefill Admission Budget (PAB). This allows higher-level cluster schedulers to accurately balance the load across multiple inference nodes, preventing any single node from becoming overloaded and ensuring consistent SLO adherence across the entire cluster.
Also Read:
- xLLM: A New Framework for High-Performance AI Serving
- FIRST: Bringing AI Inference to Scientific High-Performance Computing
Performance Impact
The evaluation of FairBatching on realistic workloads and various LLM models demonstrates significant improvements. In single-node setups, FairBatching substantially reduces TTFT tail latency by up to 2.29 times while reliably maintaining TPOT SLOs. This translates to an overall 20.0% improvement in single-node capacity. When integrated with a load balancer that utilizes FairBatching’s PAB mechanism, the cluster-level capacity sees an even more impressive boost of 54.3%.
The detailed latency analysis shows that while traditional systems either excel at TTFT (at the cost of TPOT) or TPOT (at the cost of TTFT), FairBatching-vanilla achieves strong performance in both. The FairBatching-PAB variant, with its proactive admission control, further refines this by preventing system overload, leading to near-ideal SLO compliance for admitted requests.
This research highlights that by explicitly managing fairness in resource allocation at a fine-grained level, FairBatching unlocks higher efficiency and better quality of service for modern LLM serving systems, ensuring a smoother and more responsive experience for users.
