Multi-Bin Batching for Increasing LLM Inference Throughput

1. The experiments in this paper are limited and do not fully support the claims of "various settings" (L87) or "comprehensive experiments" (L103). The experiments are confined to a single model, a single device, and a fixed batch size, which limits the ability to demonstrate the robustness and generalization of the approach across diverse scenarios. The baseline for comparison is restricted to standard batching inference, without evaluating the proposed approach against existing methods that improve LLM inference throughput by batching, such as those mentioned in the related works (e.g., [1]). Additionally, the details of experiment 6.2 are ambiguous, lacking clear information about the requests' sources, attributes (e.g., prompt length, output length), or how inference times are estimated.

2. The experiment in Section 6.2 is limited to a simulated environment rather than a real-world LLM inference system and is performed under the strong assumption that all requests arrive at once. This assumption has not been validated through providing sufficient evidence to demonstrate most real-world scenarios satisfy this requirement. As a result, the exploration of how latency from waiting for requests impacts response times is constrained to theoretical analysis.

3. The novelty of the proposed approach is limited by insufficient differentiation from prior work. The paper does not clearly explain the differences or relationships between this method and existing approaches that leverage batching, weakening its contribution. For instance, the paper claims that continuous batching is unsuitable for distributed or cloud-based environments (L45) while the proposed method works in these scenarios, yet no experiments are conducted in such environments to substantiate this claim, nor is the proposed method compared against approaches using continuous batching.

[1] Ke Cheng, Wen Hu, Zhi Wang, Hongen Peng, Jianguo Li, and Sheng Zhang. Slice-level scheduling for high throughput and load balanced llm serving. arXiv preprint arXiv:2406.13511, 2024b

I truly enjoyed reading the paper. However, I could not help but wonder on a few more practical questions:

1. When you do the latency derivation, you assume you are operating at the low utilization regime. However, in your simulations, e.g., in Fig.4 you show results mostly on the high utilization regime (as \lambda increases). You also derive a model when the system is at maximum throughput. I am afraid that as you basically get into the higher regimes, the assumptions do not hold and all of a sudden your remark 5.1 is the truth. In addition, in fact, unless your average utilization is extremely low, queuing delays do occur at the low-utilization regime. For an M/M/1 queue, the theoretical average waiting time is actually ρ/(μ − λ) for a single queue system. So I am afraid that the latency in Figures 4 and 6 is a gross underestimate for higher λ which will lead to also higher ρ. I think what would be interesting is to study when: the k=n queuing delays+bin-filling delays < k=1 queuing delays The queuing delays for the k=n is probably lower than those k=1, but this will depend on the distribution of the sizes of the arriving tasks

2. Looking at eq.5, one main issue I see is that you really need large batch sizes for this to pay off. In addition, l_max and l_min will highly influence the perofrmance. There is an added complexity with multiple bins to manage and there is a huge risk of starvation which can really weaken the results. If you basically have dynamic batching to make sure that starvation does not happen, then there is a risk that your waiting time before you decide to schedule the tasks anyways even with no similarly sized batch will be extremely hard to tune, and will introduce worse tails response times.

3. How small is small for the context sizes for your simulated results to hold?

4. The simulated results in Fig. 6 are a bit odd in my opinion. I am not really sure how the latency for larger k can be lower than k=1 at low λ. Even from the theory point-of-view, your queuing theory models do not support such a result as in essence it says that the time you need to wait to fill the bins does not matter. I think I would love to see more analysis on why is this happening.

1 - The proposed approach has a significant gap: how do you predict the output lengths or prompt service time? I can only find the term "Output Length Predictor" in Figure 2, but I have no idea how you implemented this module. Note that this is actually a significant challenge that most of the works in Paragraph 2, Section 2 focused on.

2 - In the introduction, the paper mentioned that "continuous batching requires fine-grained control of hardware, which is not always feasible." This assumption is somewhat ambiguous, as continuous batching can be supported by various modern and common hardwares. Specifically, vLLM has a lot of quick examples of deploying in cloud-based environments.

3 - Generally, I understand the idea that the paper models the LLM serving system as a server queuing system. However, the theory or technique behind such modeling is not new or novel. Once again, the more challenging problem here may be the output length prediction or service time estimation, as related works pointed out [1]. If the LLm serving system has high-confident output length predictions, optimizing the prompt batching would be relatively easy. How would the proposed method differ from existing classic server queuing systems without addressing the output length prediction problem?

4 - The evaluation is somewhat naive. Most of the experiments are conducted using simulations, as the only experiments on real testbeds are provided in Section 6.2. The evaluation simply uses a burst of requests for measuring the throughput. It would be better to have more realistic evaluations on the testbeds, such as using the real-world LLM inference traces [2] and presenting more metrics (e.g., latency and resource utilization).

5 - The evaluation lacks baseline comparison. A set of batching optimization works is mentioned in Section 2, yet the paper didn't compare the multi-bin batching with any of the state-of-the-art/practice solutions.

[1] Fu, Yichao, et al. "Efficient LLM Scheduling by Learning to Rank." arXiv preprint arXiv:2408.15792 (2024).

[2] Wang, Yuxin, et al. "Towards Efficient and Reliable LLM Serving: A Real-World Workload Study." arXiv preprint arXiv:2401.17644 (2024).

1. Some assumptions made in the paper seem to be far from realistic scenario.
2. Lack of evaluation on more realistic use cases of multi-bin batching algorithm.
3. Lack of sensitivity analysis on the effects of accuracy of length prediction.