🤖 machine learning

Multi-Bin Batching for Increasing LLM Inference Throughput

This paper proposes Multi-Bin Batching, a control policy that groups LLM requests with similar predicted execution times into predetermined bins to provably maximize inference throughput under static batching, thereby significantly reducing resource underutilization caused by varying generation lengths.

Original authors: Ozgur Guldogan, Jackson Kunde, Kangwook Lee, Ramtin Pedarsani

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ozgur Guldogan, Jackson Kunde, Kangwook Lee, Ramtin Pedarsani

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital age, large language models have become the engines behind a new wave of intelligent tools, capable of writing stories, debugging code, and answering complex questions. These systems work by predicting the next word in a sequence, one token at a time, a process that requires immense computing power. To make these systems useful for many people at once, servers must handle thousands of requests simultaneously. The standard way to do this is through a technique called batching, where the computer groups several requests together and processes them all at the same time, much like a bus carrying multiple passengers to the same destination. This parallel processing is essential for speed, but it introduces a subtle inefficiency: the entire group must wait for the slowest passenger to finish before the bus can depart for the next trip. If one person in a group of ten needs a long time to get ready while the others are ready instantly, the computer sits idle, waiting for that single slow request, wasting valuable time and energy.

Researchers have long sought a way to fix this waiting game without abandoning the efficiency of batching. A new study proposes a solution called multi-bin batching, a method that organizes incoming requests into separate waiting lines based on how long they are expected to take. Instead of throwing every request into a single mixed queue, the system predicts the length of the answer each user wants and sorts them into different "bins." Requests that are likely to be short go into one bin, while those likely to be long go into another. Batches are then formed within these bins, ensuring that the requests in any single group have similar durations. This prevents the fast requests from being held up by the slow ones, allowing the computer to finish its work on a group much sooner and start the next one.

The researchers tested this idea using a mathematical framework that treats the server as a single machine processing a steady stream of requests. They proved that by increasing the number of bins, the system can get closer and closer to a theoretical maximum speed where no time is wasted waiting for stragglers. In their analysis, they showed that if the bins are set up correctly, the time the computer spends waiting for a group to finish decreases significantly. The study also explored how this works when the time it takes to generate an answer follows a specific statistical pattern, confirming that the logic holds up even when the timing is unpredictable. The core finding is that simply grouping similar tasks together, rather than processing them in the order they arrive, can dramatically reduce the idle time that plagues current systems.

To see if this theory works in the real world, the team ran experiments using a popular open-source model on a high-end graphics card. They compared their new method against the standard way of batching requests and against a more advanced system called continuous batching, which allows new requests to jump into a group as soon as a spot opens up. In a controlled test where the researchers knew exactly how long each answer would take, their multi-bin method with sixteen bins outperformed the standard approach by more than 150 percent. In this specific scenario, it even slightly beat the continuous batching system, suggesting that if you can perfectly predict how long a task will take, sorting them into tight groups is a highly effective strategy.

However, the real world is rarely so predictable. When the researchers applied the method to a dataset of real user questions, where they had to estimate the length of the answer rather than knowing it for sure, the results were still impressive but more modest. Using a lightweight tool to guess the length of the response, the multi-bin system improved throughput by 150 percent over the standard method, a massive gain. Yet, it still fell short of the continuous batching system, which remained the fastest overall. The gap between the estimated results and the ideal "perfect knowledge" results showed that the accuracy of the prediction matters greatly; when the system guessed the length correctly, the performance jumped significantly. This indicates that while the sorting strategy is powerful, its full potential depends on having a very good way to predict how long a task will take before it even starts.

The study concludes that this binning approach is not a replacement for the sophisticated systems already in use, but rather a powerful tool that could be added to them. By acting as a smart sorting mechanism before requests hit the main processing queue, it could help modern servers handle traffic more efficiently. The researchers found that the number of bins acts as a tuning knob: too few, and the system still suffers from mismatched speeds; too many, and the time spent sorting requests might slow things down. The sweet spot depends on the specific workload and how accurately the system can predict task lengths. Ultimately, the work demonstrates that a simple change in how requests are grouped—treating similar tasks as neighbors rather than strangers—can unlock significant speed improvements for the artificial intelligence systems that power our daily digital lives.

Technical Summary: Multi-Bin Batching for Increasing LLM Inference Throughput

Problem Statement

Large Language Model (LLM) inference systems rely on batching to maximize hardware utilization and throughput. However, standard static batching suffers from significant inefficiencies due to heterogeneous execution times. In a static batch, the serving unit remains locked until the request with the longest generation time (the "straggler") completes. This causes resource underutilization, as requests with shorter execution times finish early but must wait for the entire batch to conclude before the next batch can begin. While continuous batching (iteration-level scheduling) mitigates this by allowing requests to leave and enter batches dynamically, the authors aim to optimize the static-batching framework specifically by addressing the straggler effect caused by varying output lengths.

Methodology: Multi-Bin Batching

The paper proposes Multi-Bin Batching, a control policy that groups incoming requests into multiple "bins" based on their predicted (or oracle) output lengths before forming batches.

Core Algorithm

Binning: The range of possible service times (output lengths) is divided into $k$ bins with boundaries $[l_{i-1}, l_i]$ .
Assignment: Incoming requests are assigned to a specific bin based on an estimated or known service time.
Batch Formation: Batches of size $B$ are formed within each bin.
Dispatch: Completed batches are dispatched to a central queue for processing.

By grouping requests with similar execution times, the method minimizes the variance within a batch, thereby reducing the "waste of computation" caused by the maximum service time dominating the batch duration.

Theoretical Framework

The authors model the system as a single-server queueing system with Poisson arrivals. They analyze the expected service time of a batch under the assumption that service times are independent and identically distributed (i.i.d.).

Uniform Distribution: For service times uniformly distributed in $[l_{min}, l_{max}]$ , the authors derive that throughput is maximized when bins have equal probability mass. The optimal decision boundaries are linear: $l_i = l_{min} + \frac{i}{k}(l_{max} - l_{min})$ .
Exponential Distribution: For exponentially distributed service times, the authors derive an upper bound on the expected service time and corresponding optimal boundaries using order statistics of truncated exponential distributions.
Throughput Analysis: Theoretical analysis proves that as the number of bins $k$ increases, the expected service time of a batch decreases, and the system throughput approaches the idealized static-batching capacity (where batch service time equals the average single-request service time). The number of bins required to achieve a throughput within $\epsilon$ of the maximum capacity scales as $O(1/\epsilon)$ .

Key Contributions

Novel Scheduling Strategy: Introduction of a length-aware binning policy that dynamically groups requests to minimize straggler effects in static batching.
Theoretical Optimality: Proof that multi-bin batching achieves asymptotic throughput optimality under the static batching model as $k \to \infty$ , along with characterization of the number of bins needed for specific throughput gains.
Empirical Validation: Comprehensive experiments on real LLM inference workloads (using llama.cpp and Llama-3.2-3B-Instruct) comparing static batching, native continuous batching, and multi-bin batching with both oracle and estimated lengths.

Experimental Results

The authors evaluated the method on two workloads: a controlled uniform-length workload and the Dolly dataset (with varying lengths).

1. Controlled Oracle-Length Workload

Setup: 1,024 requests, batch size 32, uniform distribution of target lengths (500–2000 tokens).
Results: Multi-bin batching with $k=16$ achieved 1,380.48 tokens/s, a 158.4% improvement over standard static batching (534.23 tokens/s).
Comparison: This result slightly exceeded the native continuous batching baseline (1,348.49 tokens/s), demonstrating that sufficiently fine-grained length grouping can approach or surpass continuous batching under controlled heterogeneity.

2. Dolly Dataset (Oracle Lengths)

Setup: 1,478 requests, batch size 64, real-world length distribution.
Results: With $k=8$ , oracle-based multi-bin batching achieved 965.97 tokens/s, a 253.1% improvement over static batching (273.53 tokens/s).
Gap: Despite the massive gain over static batching, it remained 19.5% below the native continuous batching baseline (1,200.07 tokens/s).

3. Dolly Dataset (Estimated Lengths)

Setup: Used a lightweight predictor based on prompt-prefill hidden states to estimate lengths.
Results: Estimated-length multi-bin batching ( $k=8$ ) achieved 684.02 tokens/s, a 150.1% improvement over static batching.
Accuracy: The predictor achieved high adjacent-bin accuracy (94.89% for $k=8$ ), meaning most errors were localized to neighboring bins.
Gap: The estimated result remained 43.0% below the continuous batching baseline, highlighting the impact of prediction error but confirming that practical estimators still yield substantial gains.

4. Robustness to Errors

Simulations with symmetric adjacent-bin errors showed that throughput degrades gracefully as prediction error probability increases, but the multi-bin policy remains robust to moderate noise.

Significance and Claims

The paper positions Multi-Bin Batching not as a replacement for modern continuous-batching systems (like vLLM or SGLang), but as a complementary scheduling principle.

Mitigation of Static Inefficiency: The method substantially mitigates the inefficiencies inherent in static batching caused by heterogeneous execution times.
Role of Length Information: The results emphasize that accurate length information is a powerful scheduling signal. Even with imperfect estimation, significant throughput gains are possible.
Integration Potential: The authors suggest that length-aware grouping can be integrated into modern serving systems via queue classes, admission-control decisions, or replica-routing policies to further optimize the trade-off between throughput and latency.
Limitations: The authors acknowledge that while multi-bin batching narrows the gap to continuous batching, it does not fully close it in complex, real-world workloads without further integration or adaptive strategies. The theoretical analysis isolates the effect of output-length heterogeneity and does not model all costs of a production system (e.g., prefill/decode interaction complexities), though empirical results include these factors.