Multi-Bin Batching for Increasing LLM Inference Throughput
Ozgur Guldogan, Jackson Kunde, Kangwook Lee, Ramtin Pedarsani · 2024
Read Multi-Bin Batching for Increasing LLM Inference Throughput by Ozgur Guldogan, Jackson Kunde, Kangwook Lee, Ramtin Pedarsani (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04504.txt.
Introduction
Ozgur Guldogan and three co-authors proposed a scheduling method to speed up language model serving in a 2024 paper. Servers group requests into batches to use hardware fully, but requests end at different times. Under fixed batching, the hardware waits for the longest job in each batch, wasting capacity. The team formalized the problem with queueing theory and sought a policy that provably maximizes throughput.
Their method, Multi-Bin Batching, sorts requests by predicted length into preset bins so each batch holds similar jobs. Theory and experiments, including real serving scenarios, show large throughput gains over plain fixed batching. A measured gap to continuous batching remains, under both perfect and estimated length knowledge. The scheme is simple enough to drop into existing systems.
Catalog record
| CREATOR | Ozgur Guldogan, Jackson Kunde, Kangwook Lee, Ramtin Pedarsani |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-04504
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Bin Batching for Increasing LLM Inference Throughput Ozgur Guldogan, Jackson Kunde, Kangwook Lee, Ramtin Pedarsani Abstract As large language models (LLMs) grow in popularity for their diverse capabilities, improving the efficiency of their inference systems has become increasingly critical. Batching LLM requests is a critical step in scheduling the inference jobs on servers (e.g. GPUs), enabling the system to maximize throughput by allowing multiple requests to be processed in parallel. However, requests often have varying generation lengths, causing resource underutilization, as hardware must wait for the longest-running request in the batch to complete before moving to the next batch. We formalize this problem from a queueing-theoretic perspective, and aim to design a control policy which is throughput-optimal under a static-batching framework. We propose Multi-Bin Batching, a simple yet effective method that can provably improve LLM inference throughput under this framework by grouping requests with similar (predicted) execution times into predetermined bins. Through a combination of theoretical analysis and experiments, including real-world LLM inference scenarios with static and continuous-batching baselines, we demonstrate that multi-bin batching substantially improves throughput over static batching and quantify the remaining gap to native continuous batching under both oracle and estimated length information. 1 Introduction Large Language Model (LLM) inference systems are becoming increasingly popular due to their various abilities, such as text generation ( Li et al., 2024 ) , coding assistance ( Du et al., 2024 ) , and question answering ( Jiang et al., 2021 ) . As the demand for LLM inference systems grows, so does the need to optimize their efficiency. Several techniques have been proposed to improve the efficiency of LLM inference systems, and batched inference ( Sheng et al., 2023 ; Kwon et al., 2023 ; Jin et al., 2023 ) is one of the most promising techniques among them. With batched inference, multiple requests are processed simultaneously, using the underlying hardware’s parallelism to improve throughput. Figure 1(a) shows the measured throughput of the Phi-3.5 Mini Instruct model ( Abdin et al., 2024 ) for various batch sizes on an NVIDIA A100 80G GPU. Throughput is calculated as the number of total tokens generated across all requests divided by time. However, batched inference comes with some critical drawbacks. The execution time of each request depends on the number of tokens generated, which varies across requests. In standard batched inference systems, a computing unit remains locked until all requests in the batch are completed, leading to resource underutilization when requests within a batch have widely differing execution times. This inefficiency offsets the throughput gains achieved through parallelism 1 1 1 With some low-level system engineering, one could potentially allow for dispatch of waiting requests in the queue to a partially busy computing node ( Yu et al., 2022 ) . We assume such fine-grained request dispatching is not available in this paper. See Section 2 for more details. . (a) (b) Figure 1 : 1(a) Batch serving improves the throughput for the LLM inference systems. 1(b) Standard batching causes underutilization of resources due to varying answer sizes. Inspired by this, a natural question arises: can we achieve near-optimal throughput from batched inference? We propose a novel control policy to optimize batched inference by introducing multi-bin batching that can provably improve LLM inference throughput in the static-batching model by grouping requests based on their predicted output lengths. Instead of placing all requests into a single queue, we create multiple “bins”, each serving as a waiting area for requests with similar (predicted) output lengths. This binning policy ensures that requests with comparable execution times are grouped together, minimizing inefficiencies due to varying execution times. Batches are then formed within each bin and dispatched to a central queue to be processed. To see why this approach is beneficial, consider the example illustrated in Figure 1(b) , where four requests arrive at nearly the same time, with execution times of 1, 5, 2, and 6 seconds, respectively. In a standard batching system with a batch size of B=2 , the requests would be grouped based on their arrival time, forming two batches: (Request 1: 1s , Request 2: 5s ) and (Request 3: 2s , Request 4: 6s ). The total execution time would be 11 seconds (5 seconds for the first batch and 6 seconds for the second). On the other hand, two-bin batching (one bin for service time between 1 to 3 seconds and another for those between 4 to 6 seconds) will result in different batches: (Request 1: 1s , Request 3: 2s ) and (Request 2: 5s , Request 4: 6s ). This will reduce the total execution time to 8 seconds, demonstrating how multi-bin batching can improve LLM inference throughput. Our analysis shows that, within the static-batching framework, increasing the number of bins makes the throughput approach the idealized static-batching capacity by reducing inefficiencies caused by heterogeneous execution times within batches. On the Dolly dataset workload, estimated-length multi-bin batching improves generated-token throughput by 150.1% over static batching at k=8 , but remains 43.0% below the continuous-batching baseline. The corresponding oracle-length result improves over static batching by 253.1%, while remaining 19.5% below continuous batching. These results show that length-aware grouping substantially mitigates static-batching inefficiency, but also that native continuous batching remains a strong practical baseline on this workload. Although our presentation is motivated by LLM inference, the underlying queueing formulation also applies more broadly to autoregressive batch-serving systems in which heterogeneous completion times create straggler effects within fixed batches. To summarize, our contributions are as follows: • We propose a novel binning-based scheduling strategy that dynamically groups requests into bins based on output lengths, minimizing inefficiencies from varying execution times and optimizing throughput for LLM inference systems. • We use queueing-theoretical analysis to show that our multi-bin batching strategy achieves asymptotic throughput optimality under the static batching model as the number of bins grows. Additionally, we characterize the number of bins required to achieve a desired throughput improvement. • Our experiments on real LLM inference workloads show that estimated-length multi-bin batching substantially improves generated-token throughput over static batching, reaching 150.1% improvement on the Dolly dataset workload, while remaining below the continuous-batching baseline. 2 Related Work LLM Inference and Scheduling Recent research has focused on optimizing large language model (LLM) inference through scheduling techniques and queueing-theoretic tools. FastServe ( Wu et al., 2023 ) utilizes a preemptive scheduling algorithm, skip-join Multi-Level Feedback Queue, to improve job completion time in LLM inference systems. Prior work on dynamic batching ( Inoue, 2021 ) studies a setting where the system serves up to B jobs depending on queue occupancy and derives closed-form upper bounds for the mean latency. Slice-level scheduling ( Cheng et al., 2024b ) splits the maximum output length into slices and serves batches slice by slice, improving memory utilization and response time. Llumnix ( Sun et al., 2024 ) addresses heterogeneous and unpredictable LLM inference requests through runtime rescheduling across multiple model instances, improving tail latency and resource utilization. Recent systems further exploit the two-phase structure of LLM inference: Sarathi-Serve ( Agrawal et al., 2024 ) uses chunked prefills and stall-free scheduling to improve the throughput–latency tradeoff, while Splitwise ( Patel et al., 2024 ) separates prompt computation and token generation across