Multi-Bin Batching for Increasing LLM Inference Throughput

arXiv:2412.04504 · cs.CL, cs.DC, cs.LG, cs.SY, eess.SY · Submitted 2026-08-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Multi-Bin Batching for Increasing LLM Inference Throughput".

Jane: The paper was written by Ozgur Guldogan, Jackson Kunde, Kangwook Lee and Ramtin Pedarsani from University of California, Santa Barbara and University of Wisconsin-Madison.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: Welcome back to the show, everyone. Today we’re digging into a paper that’s got a very practical title: “Multi-Bin Batching for Increasing LLM Inference Throughput.” Jane, when you first saw that title, what jumped out at you?

Jane: Honestly, Tom, the word “batching” caught my eye. Anyone who’s run a big language model knows that batching is how you get any speed out of a GPU at all. But the “multi-bin” part is what makes this interesting — it’s not just throwing requests together, it’s sorting them first.

Tom: Right, and that sorting is the whole trick. The authors are from UC Santa Barbara and UW-Madison, and they’re looking at a really annoying problem: when you batch requests together, the whole batch has to wait for the slowest request to finish.

Jane: Exactly. Imagine you’re at a checkout line with four people, and one person has a cart full of groceries while everyone else has just a loaf of bread. You all wait for the cart. That’s wasted time, and in LLM inference, that wasted time is real money.

Tom: So their idea is to group requests by how long they’re going to take — put the short ones together, put the long ones together. They call these groups “bins,” and then they form batches within each bin. It’s almost too simple to be a paper, but the math behind it is surprisingly deep.

Jane: And that’s what I love about it. The title sounds like a small tweak, but the implications are huge. If you can get even ten or twenty percent more throughput out of the same hardware, that changes the economics of serving these models.

Tom: For sure. And they’re not just hand-waving — they actually prove that as you add more bins, your throughput approaches the theoretical maximum. That’s a strong claim, and we’re going to spend the rest of the show unpacking it.

Jane: I’m already excited to see how they handle the real-world experiments. Because theory is one thing, but GPUs are another.

Tom: Stick around — next segment we’re going to talk about the core problem they’re solving and why standard batching leaves so much performance on the table.

Summary: Tom: So we’ve got the title, we’ve got the idea — let’s talk about what the paper actually does. Jane, can you walk us through the setup they’re using?

Jane: Sure. They model an LLM inference system as a queue. Requests come in at some rate, they get grouped into batches of a fixed size, and each batch is processed on a server. The key assumption is that a batch’s service time is the maximum of the service times of the individual requests in it.

Tom: And that’s the crux of the problem. If you have a batch where one request generates five hundred tokens and another generates fifty the whole batch runs until the five hundred-token request is done. The fifty-token request just sits there, and the GPU is doing work that doesn’t need to be done.

Jane: Right. So they propose this multi-bin batching algorithm. You divide the range of possible service times into k bins, assign each incoming request to a bin based on its predicted service time, and then form batches within each bin. Once a batch is full, it goes into a service queue.

Tom: And the beautiful part is that they prove the optimal bin boundaries are just equal-width intervals — if your service times are uniformly distributed, you split the range into k equal parts. That’s it.

Jane: It’s elegant because it’s so simple. No fancy optimization, no adaptive learning — just equal-width bins. And then they show that the expected service time of a batch decreases as you add more bins.

Tom: Let me jump in with a concrete number from the paper. With a batch size of one hundred twenty-eight and service times ranging from one to twenty seconds, they show that going from one bin to five bins gets you very close to the theoretical maximum throughput. That’s a massive gain for such a simple change.

Jane: And they don’t stop at theory. They run simulations with real request data from the GSM8K dataset, and they see throughput improvements of up to seventy percent when they know the exact output length ahead of time.

Tom: Seventy percent is huge. That’s the difference between serving a model and not serving it, in some cases. But I know you’re going to ask about the catch — what happens when you don’t know the output length perfectly?

Jane: That’s exactly the next segment. They do test with a predictor, and the gains shrink, but they don’t disappear. So the idea is robust, even with imperfect information.

Tom: Alright, let’s get into the improvements they’re suggesting — because the binning is just the start.

Improvements: Tom: Welcome back. We’ve established that multi-bin batching helps, but let’s talk about what the paper suggests as improvements over the standard approach. Jane, what’s the big one?

Jane: The big one is that they show the throughput increases monotonically with the number of bins. More bins means tighter grouping, which means less wasted time waiting for the slowest request in a batch.

Tom: And they even give you a formula for how many bins you need to hit a target throughput. That’s practical — you can plug in your numbers and know exactly how many bins to use.

Jane: Right. But there’s a trade-off they’re honest about. More bins means you have to wait longer to fill a batch within each bin, especially if requests are arriving slowly. So there’s a latency cost.

Tom: And that’s where the latency analysis comes in. They derive a lower bound on the expected latency, and they show that in an underloaded system, the latency increase is pretty small. But as you push the system toward its maximum throughput, the latency can spike.

Jane: Let me bring in Lu here — Lu, you’ve been quiet. What do you think about the trade-off between throughput and latency in this paper?

Lu: I think the trade-off is real, but the paper handles it well. They’re not claiming you get something for nothing. They’re saying, here’s how to get more throughput, and here’s what it costs you in latency. And the cost is often worth it, especially if you’re running a service where throughput is the bottleneck.

Meng: From an engineering standpoint, I’m curious about the predictor. They mention using a BERT-based model to estimate output length. How accurate does that need to be for the gains to hold up?

Jane: That’s a great question. They test with symmetrical prediction errors — meaning the predictor is equally likely to overestimate or underestimate by one bin. And even with error probabilities up to fifty percent, the throughput still improves as you add bins.

Meng: So the system is robust to noisy predictions. That’s reassuring. But what about the actual end-to-end test with the predictor? I saw they got only eight percent improvement there, compared to seventy percent with oracle lengths.

Jane: Right, that’s the honest number. With a real predictor, the gains are smaller — around eight percent going from one bin to four bins. But that’s still a meaningful improvement, and the paper suggests that better predictors would close the gap.

Tom: So the improvements are real, but they depend on the quality of your length prediction. That’s a fair caveat.

Lu: And I’d add that the theoretical framework is the real contribution here. Even if the predictor is imperfect, the analysis gives you a way to think about the problem that you didn’t have before.

Jane: Exactly. And that brings us to the conclusion — let’s wrap this up.

Conclusion: Tom: Alright, let’s bring it home. We’ve been talking about “Multi-Bin Batching for Increasing LLM Inference Throughput” all episode, and I think we’ve covered a lot of ground.

Jane: We have. The core idea is simple: group requests by their expected service time, form batches within those groups, and you waste less time waiting for the slowest request. The paper proves this improves throughput, and the experiments back it up.

Tom: And the numbers are striking — up to seventy percent throughput improvement with perfect length predictions, and still meaningful gains with a real predictor. That’s not a rounding error; that’s a different service tier.

Jane: The trade-off is latency, especially as you add more bins. But the paper gives you the tools to find the right balance for your system.

Lu: I’d say the biggest impact is that this gives system designers a principled way to think about batching. It’s not just “batch everything” — it’s “batch smart.”

Meng: And from a practical standpoint, it’s a relatively easy change to implement. You’re not rewriting the inference engine; you’re just changing how you group requests before they hit the GPU.

Tom: That’s what makes this paper exciting. It’s not a moonshot — it’s a practical improvement that could help a lot of people running LLM services right now.

Jane: And the future work is clear: better length predictors, adaptive binning strategies, and extending this to continuous batching systems. There’s a lot of room to build on this.

Tom: So that’s “Multi-Bin Batching for Increasing LLM Inference Throughput.” Thanks for joining us, everyone. We’ll see you next time with another paper.

Jane: Take care, everyone.

Ozgur Guldogan, Jackson Kunde, Kangwook Lee, Ramtin Pedarsani

University of California, Santa Barbara · University of Wisconsin-Madison

cs.CL, cs.DC, cs.LG, cs.SY, eess.SY

Submitted: 2026-08-17

Updated: 2026-08-18

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 64/100

Key concepts

Batching
In LLM inference, batching is the process of grouping multiple requests together to utilize GPU resources efficiently. The standard method can waste time because the entire batch must wait for the slowest individual request to complete.
Multi-Bin Batching
This technique improves standard batching by dividing possible service times into 'bins.' Requests are assigned to a bin based on their predicted service time, and batches are formed within each bin to reduce idle waiting time.
Inference Throughput
Throughput refers to how many requests an LLM system can process over a given period. The paper demonstrates that multi-bin batching significantly increases this rate by minimizing the wait time caused by varying request lengths.

Terminology

Summary

Summary

This paper introduces Multi-Bin Batching, a novel control policy designed to increase the throughput of Large Language Model (LLM) inference systems. The core problem addressed is the inefficiency of standard batching, where requests with varying generation lengths are grouped together, causing hardware to remain idle while waiting for the longest-running request in a batch to complete. The paper formalizes this issue from a queueing-theoretic perspective and proposes a method to group requests with similar predicted execution times into predetermined bins.

The proposed algorithm, k-Bin Batching, works by first dividing the range of possible service times into k bins with boundaries determined by prior knowledge or system profiling. Incoming requests are assigned to bins based on their estimated service times and grouped into batches of size B. Completed batches are added to a service queue and processed using a first completed batch, first served policy. This ensures that requests with comparable execution times are batched together, minimizing inefficiencies from varying execution times.

The paper provides a rigorous theoretical analysis. Under the assumption that service times are uniformly distributed in the range [lmin, lmax], the authors prove that throughput is maximized when each bin has equal probability mass, with optimal decision boundaries given by li-1 = lmin + (i-1)/k (lmax - lmin). The expected throughput for k bins is derived as Throughputk = B / E[tservice, k], where E[tservice, k] is the expected service time of a batch. The analysis shows that this throughput is an increasing function of the number of bins k. The standard batching system is a special case of this model with k = 1. The paper proves that as k approaches infinity, the throughput converges to the theoretical maximum capacity of the system, cmax = B / ((lmax + lmin)/2), achieving asymptotic throughput optimality. A theorem is also provided to characterize the minimum number of bins required to achieve a desired throughput level within a margin ϵ of the maximum.

The paper also includes a latency analysis. It decomposes latency into queuing time and service time, and provides a lower bound for latency under an idealized assumption of infinite servers. The expected latency is given by E[tlatency] = (1/2)(lmax + lmin) + (1/k)(B/(B+1)lmax + 1/(B+1)lmin - (lmax + lmin)/2) + ((B-1)/(2λ))k. The analysis shows that while multi-bin batching can increase throughput, it introduces a trade-off by potentially increasing latency as the number of bins grows.

The experimental evaluation is comprehensive and uses Microsoft's Phi-3.5-mini-instruct model on an NVIDIA A100-80G GPU. The experiments are conducted in three stages with increasing realism:

  1. Simulated LLM Inference: The service time is modeled as a linear function of the number of generated tokens, and requests are binned using oracle (known) length information. Results show that throughput increases with the number of bins, approaching the maximum capacity. Interestingly, for small k (e.g., 2-4 bins), the minimum latency is superior to the standard batching case (k=1).

  2. End-to-End LLM Inference: The linear model is replaced with actual inference times from the LLM. With a single server and all requests arriving simultaneously, throughput improves by approximately 70% from no binning to 32 bins with oracle length information.

  3. Effect of Symmetrical Prediction Errors: The robustness of the policy is tested by simulating errors in bin assignment, where a request is placed in a neighboring bin with a certain probability. Results show that even with prediction errors, throughput increases with the number of bins, and systems with more bins demonstrate higher resilience to inaccuracies.

The paper concludes that multi-bin batching provides a provable throughput improvement and can be readily integrated into existing systems. Future work is suggested to focus on improving bin prediction models and developing adaptive binning strategies.

Improvements for AI systems

Based on the paper, here are the specific improvements I can implement in an AI system, and what the improved system can do:

Improvements to the AI System:

  1. Add a multi-bin batching scheduler module to the inference serving layer. This module:

  • Divides the output length range (e.g., 1–1024 tokens) into k equiprobable bins (e.g., k=4, 8, 16, or 32).

  • For each incoming request, predicts its output length using a lightweight BERT-based predictor (fine-tuned with L1 loss) or a linear model based on input length.

  • Assigns the request to the bin whose range contains the predicted length.

  • Within each bin, accumulates requests until a batch of size B (e.g., 8 or 128) is formed, then dispatches that batch to the GPU server queue.

  1. Replace the current first-come-first-served batching with a first-formed-batch, first-served policy. This ensures that batches with similar execution times are processed together, reducing idle GPU time caused by stragglers.

  2. Add an adaptive bin-count controller that dynamically adjusts k based on system load and prediction accuracy. The controller:

  • Monitors the throughput and latency in real-time.

  • Increases k when the system is underutilized (e.g., arrival rate < 80% of capacity) to approach the theoretical maximum throughput.

  • Decreases k when latency exceeds a QoS threshold (e.g., p99 latency > 2 seconds) to reduce batch formation waiting time.

  1. Integrate a prediction-error robustness layer that handles misclassification. If a request is assigned to the wrong bin, the system:

  • Re-bins the request if the error is detected before batch formation (e.g., using a confidence score from the predictor).

  • If not detected, the batch still benefits because the error is symmetric (i.e., it only shifts to adjacent bins), and the throughput degradation is bounded (as shown in Figure 8 of the paper).

What the Improved AI System Can Do:

  • Increase inference throughput by up to 70% (with oracle length information) and by 8% with a real BERT-based predictor, compared to standard batching. For example, on an NVIDIA A100-80G with Phi-3.5-mini, the system can process 35–40 requests/second instead of 22–25 requests/second at high load.

  • Achieve near-optimal throughput (within 5% of the theoretical maximum) when using 16–32 bins, even with imperfect length predictions. This is because the binning reduces the variance of execution times within each batch, minimizing GPU idle time.

  • Maintain low latency under moderate load. The system's average latency increases only slightly (e.g., from 3.2s to 3.8s for k=4) while throughput improves by 20–30%. This is a favorable trade-off for throughput-sensitive workloads like batch processing or offline inference.

  • Handle variable-length requests gracefully without requiring continuous batching or complex preemption. The system groups similar-length requests, so the GPU is never idle waiting for a single long request to finish.

  • Provide a tunable knob (number of bins k) that operators can adjust based on their specific latency-throughput requirements. For example, if latency is critical, use k=2; if throughput is critical, use k=32.

  • Scale to multi-server setups by extending the same binning logic across servers, where each server processes batches from its own queue, and the binning reduces cross-server load imbalance.

  • Work with any LLM (e.g., Phi-3, Vicuna, Llama) because the length predictor is trained on the specific model's output distribution, and the bin boundaries are computed from that distribution.

Specific Implementation Details:

  • For the predictor: Use a BERT-base model with a single linear head, trained on 120k samples from LMSYS-Chat-1M with L1 loss. The predictor achieves 86% accuracy for 2 bins, 63% for 4 bins, and 42% for 8 bins (with ±1 bin accuracy of 96% and 79% respectively).

  • For the bin boundaries: Compute them as l i = l min + (i/k)*(l max - l min) for uniform distributions, or use the recursive formula for exponential distributions (as in Lemma A.1).

  • For the batch size: Use B=8 for real-time serving (to keep latency low) and B=128 for batch processing (to maximize throughput).

Example Scenario:

  • Before improvement: A server processes 1000 requests with variable lengths (1–20 seconds). Standard batching groups them randomly, causing the server to be idle for 30% of the time waiting for stragglers. Throughput is 22 requests/second.

  • After improvement: The same server uses 8 bins. Requests are grouped by predicted length (e.g., 1–3s, 3–6s, etc.). Batches are formed within each bin. The server is idle for only 10% of the time. Throughput increases to 31 requests/second (a 40% improvement). Latency increases from 2.5s to 3.0s, which is acceptable for most applications.

Sources

Related papers